南京大学《数据结构》试卷.pdf-资料库

考试科目名称数据结构（A1 卷）得分 1、填空题。（每小题 2 分，本题满分 20 分） (1) C++语言中，数组是按行优先顺序存储的，假设定义了一个二维数组 A[20][30]，每个元素占两个字节，其起始地址为 2140，则二维数组 A 的最后一个数据元素的地址为 2140+2*(30*20-1) = 3338(3338,3339) 。 (2) 若 A，B 是两个单链表，链表长度分别为 n 和 m，其元素值递增有序，将 A 和 B 归并成一个按元素值递增有序的单链表，并要求辅助空间为 O(1)，则实现该功能的算法的时间复杂度为 O(m+n) 。 (3) 快速排序的平均时间复杂度是____n*lg n___________。 (4) 假设有一个包含 9 个元素的最小堆，存放在数组 A 中，则一定比 A[3]大的元素有_ _2 (A[7],A[8]) ____个；一定比 A[3]小的元素有__2 (A[0],A[1])____个。（元素从第 0 个位置开始存放） (5) 广义表(((A)),(B,C), D, ((A), ((E,F)))) 的长度是 4 ，深度是 4 。 (6) 有 10 个元素的有序表，采用折半查找，需要比较 4 次才可找到的元素个数为____3_____。 (7）当两个栈共享一存储区时，栈利用一维数组 A[n]表示，两栈顶指针为 top[0]与 top[1]，则栈满时的判断条件为___top[0]+1=top[1]_ 或者 top[0] = top[1]+1 ___。 (8) 假设计算斐波那契数的函数 Fib(long n)定义如下： long Fib(long n){ if(n<=1) return n; else return Fib(n-1)+Fib(n-2) } 计算 Fib(5)时的递归调用树（即指明函数调用关系的树）的高度是___4 _____。假设叶子结点所在的高度为 0。 (9) 完全二叉树按照层次次序，自顶向下，同层从左到右顺序从 0 开始编号时，编号为 i 的结点的左子结点的编号为___2*i+1______。 (10) 假设用子女—兄弟链表方式表示森林，对应的二叉树的根结点是 p，那么森林的第三棵树的根结点在二叉树中对应的结点是： ___p->rightchild->rightchild____________。假设二叉树的结点结构为： leftchild data rightchild 得分 2、选择题。（每小题 2 分，本题满分 20 分） (1) 如果能够在只知道指针 p 指向链表中任一结点，不知道头指针的情况下，将结点*p 从链表中删除，则这个链表结构应该是： ( B,C )（多选题） A. 单链表 B. 循环链表 C. 双向链表 D. 带头结点的单链表 (2) 以下哪种矩阵压缩存储后会失去随机存取的功能?( A ) A. 稀疏矩阵 B. 对称矩阵 C. 对角矩阵 D. 上三角矩阵 (3) 下面哪一方法可以判断出一个有向图是否有环（回路）：( B ) (选 A，B 也对) A. 广度优先遍历 B. 拓扑排序 C. 求最短路径 D.求关键路径 (4) n 个结点的线索二叉树(没有头结点)上含有的线索数为（ B ）第 1 页共 12 页

A. 2n B. n－l C. n＋l D. n (5) 循环队列存储在数组 A[0..m]中，则入队时队尾指针 rear 的操作为（ D ） A. rear=rear+1 B. rear=(rear+1) mod (m-1) C. rear=(rear+1) mod m D. rear=(rear+1)mod(m+1) (6) 使用加权规则得到改进的 Union 操作 WeightedUnion，其目的是： ( B ) A. 提高 Union 操作的时间性能 B. 提高 Find 操作的时间性能 C. 减少 Union 操作的空间存储 D. 减少 Find 操作的空间存储 (7) 使用 Kruscal 算法求解最小生成树时，为了设计效率较高的算法, 数据结构方面可以选择： ( A ) A. 利用最小堆存储边 B. 利用栈存储结点 C. 利用二维数组存储结点 D. 利用并查集存储边 (8) 已知一算术表达式的后缀形式为 ABC*+DE/-，其前缀形式为：( D ) A. -A+B*C/DE B. -A+B*CD/E C. -+*ABC/DE D. -+A*BC/DE (9) n 个关键码排序，如果选用直接插入排序方法，则元素的移动次数在最坏情况下可以达到( B )。 A. n*n/2 B. n*(n-1)/2 C. n/2 D. (n-1)/2 (10) 关键路径是 AOE 网络中 A C 。（多选） A. 从源点到汇点的最长路径 B. 从源点到汇点的最短路径 C. 所有活动都是关键活动的路径 D. 最短回路得分３、简答题。（每小题 5 分，本题满分 20 分） (1) 对如下无向图，按照 Dijkstra 算法，写出从顶点 1 到其它各个顶点的最短路径和最短路径长度。 1 3 5 7 7 8 11 10 5 6 2 4 6 9 结点编号 1 路径长度 0 2 11 3 7 4 12 5 14 6 15 最短路径 1 1-2 1-3 1-3-4 1-3-5 1-3-6 (2）请画出在如下图所示的 5 阶 B 树中插入一个关键码 360 后得到的 B 树。 100 200 300 400 20 40 150 180 240 260 310 320 350 370 420 430 第 2 页共 12 页

300 100 200 350 400 20 40 150 180 240 260 310 320 360 370 420 430 (3) 假设有权值集合{16,40,15,4,25}，给出相应的 huffman 树。假设某类信息由符号 a,b,c,d,e, 组成，而上面的权值分别是符号 a,b,c,d,e 的出现频率。请给出各个符号的 Huffman 编码。 Huffman 编码： a: 001 b: 1 c: 0001 d: 0000 e: 01 注意：因为左右子树不同，所以编码可以有多种，但是只要其长度分别是 3，1，4，4，2；且相互之间不形成前缀关系就是正确的。 100 60 40 35 25 19 16 4 15 (4)在 AVL 树的插入操作中，假设插入一个结点后，当前节点 p 的平衡因子是-2，其左子结点的平衡因子是+1，左子结点的右子结点的平衡因子是-1。如图所示，请给出旋转调整之后的结构。 p -2 A +1 B t4 -1 C t1 C 0 B +1 A -1 t2 t3 t1 t2 t3 t4 第 3 页共 12 页

得分 4、已知输入关键码序列为（10,90,20,60,78,35,42,31,15），地址区间为 0～11。 (1) 请设计一个散列函数，把上述关键码散到 0～11 中。画出散列表，冲突用线性探测法解决。（5 分）散列函数为： f(x) = x % 12 允许其它的散列函数 0 1 2 3 4 5 6 7 8 9 10 11 60/1 31/7 15/1 90/1 (2) 搜索元素 31 需要比较的次数是多少？（2 分） 7 (7-->8->9->10->11->0->1 (成功）） (3) 计算在等概率情况下查找成功的平均查找长度 ASLsucc。（3 分） 78/2 20/1 42/4 10/1 35/1 (1+7+1+1+2+1+4+1+1) / 9 = 19/9 得分 5、程序设计题。（每小题 15 分，本题满分 30 分） 1. 设计一个算法，根据一棵二叉树的前序序列和中序序列，构造出这棵二叉树。二叉树的结点都用字符表示。前序序列和中序序列都是字符串。二叉树的结点定义如下： struct binTreeNode {char data; binTreeNode *leftChild, *rightChild; } 解： TreeNode * tree(char *preorder, *midorder) { return TreeRecursive(preorder, 0, strlen(preorder)-1, midorder, 0, strlen(midorder)-1); } TreeNode * TreeREcursive(char *pre, int preSt, int preEnd, { char* mid, int midSt, int midEnd) if (preEnd < preSt) return NULL; char rt = pre[preSt]; for(int j = midSt; j<=midEnd; j++) if(mid[j] == rt) break; if(j>midEnd){cout<<"Wrong input"; return NULL;} TreeNode root = new binTreeNode( ); root->data = rt; int lLen = j - midSt; root->leftChild = treeRecursive(pre, preSt+1, preSt+lLen - 1, 第 4 页共 12 页

mid, midSt,midSt+lLen-1); root->rightChild=treeRecursive(pre, preSt+lLen+1, preEnd, mid, midSt+lLen+1, midEnd); return root; } 要点在于根据 preOrder 的第一个字符，在 midOrder 中找到左右子树的分界；然后递归调用生成左右子树；做到这一点，就可以给出大部分分数。可能有很多细节上不一样的地方，比如这里的 preEnd 指向的字符在相应的树中；但是有些人可能是 preEnd 指向下一个位置。或者传递参数时直接使用字符串传递。都是可以的。如果使用别的办法，参考其效率，酌情给分。只要效率过得去，也可以得满分。但是纯粹枚举则得分不高。 2. 设计非递归算法实现图的深度优先遍历。（图用邻接表表示，已经定义了一个顺序栈 stack[top]，top 为栈顶指针，使用 visit(node)来表示对顶点 node 的访问。）图的邻接表结构定义如下： struct Edge { int dest; Edge *link; //下一条边链指针 } struct Vertex { int data; Edge *adj; //边链表的头指针 } class Graph { private: Vertex *Nodetable; //顶点表 int cnt ｝解： Graph : : DFS(int v)//从 v 开始搜索； { visited[MAXVert]; nextEdge[MAXVert]; bool Edge stack[0] = v; nextEdge[0] = graph.Nodetable[v].adj; top = 0; visited(stack[top]); 第 5 页共 12 页

visited[stack[top]] = true; while(top >= 0) { while(nextEdge[top] && visited[nextEdge[top]->dest]) //寻找下一个尚未访问的邻接节点 nextEdge[top] = nextEdge[top]->link; if(nextEdge[top] != NULL) { int nextVert = nextEdge[top]->dest; visite(nextVert); //访问下一个邻接结点；保证了被压入栈中的顶点都被访问； visited[nextVert] = true; stack[top+1] = nextVert; //压栈，进入下一个结点； nextEdge[top+1] = Nodetable[nextVert].adj; nextEdge[top] = nextEdge[top]->link; top ++; } else top --; } } 另一个数据结构试卷得分 1、填空题。（每小题 2 分，本题满分 20 分） (1) 假设用一个一维数组 B 来按行存放一个对称矩阵 A 的下三角部分，那么访问 A 的第 i 行第 j 列元素的语句是：_________________________________。(下标都从 0 开始) (2) 在单链表指针 P 所指结点后插入指针为 s 的结点操作是：。 (3) 线性表 L=(a0,a1,a2,…an-1)用数组表示，假设删除表中任一元素的概率相同，则删除一个元素所需的平均移动次数为。 (4) 在指针 L 指向一带头结点的双向循环链表，则判断该表中只有一个元素结点的条件是： (设结点结构为 . ) lLink data rLink (5）使用邻接矩阵表示图时，遍历一个顶点的所有相邻顶点的时间复杂度是：_____________。 (假设图的顶点个数为 n, 边的个数为 e) (6) 已知带权有向图如下，使用 Dijkstra 算法求解从顶点 1 到达各顶点的最短距离时，该算法将按照_______________________（列出顶点顺序）的顺序给出各个顶点的距离。 1 20 2 30 3 10 4 8 11 14 6 9 12 3 5 3 6 18 7 8 8 (7) 假设一组关键码为（20，41，22，17，19，56，35），则用堆排序的方法建立的初始最第 6 页共 12 页

大堆为。 (8) KMP 模式匹配算法的时间复杂度是：___________________________。 (9) 设循环队列存放在数组 A[0..m-1]中，若用牺牲一个单元的办法区分队列满和队列空(设队尾指针为 rear, 队头指针为 first)，则判断队满的条件是：。. (10) 对 n 个元素进行排序，如果用直接选择排序，所需的关键码比较次数最少为，如果用直接插入排序，则所需的关键码比较次数最少为。得分 2、选择题。（每小题 2 分，本题满分 20 分）（1）假设使用转换后的二叉树来表示森林，那么对该二叉树的前序遍历对应于对森林的 ______遍历。 A 先根次序遍历 B 后根次序遍历 C 广度优先遍历 D 以上都不是 (2) 假设我们将一个表达式表示为一棵二叉树。比如 a+b*c 对应的树的根为+，其左子树是一个叶子结点 a，右子树的根为*，左右子结点分别为 b 和 c。显然每个内部结点代表了一个运算。假设一个并行 CPU 有很多个 ALU 可以同时执行计算任务，且完成所有计算需要的时间都是一个时间单位。那么完成一个表达式计算的最短时间是_______。 A 树的高度 B 树的宽度 C 树的内部结点个数 D 树的分支数 (3) 假设在快速排序算法中总是选择被排序子序列的最后一个元素作为基准。那么这个算法的最坏情况出现在_______。 A 被排序的初始序列已经排好序时 B 被排序的初始序列是逆序时 C 被排序的初始序列呈现中间大，并逐次向两边减小的情况 D 以上都不是 (4) 散列方法中，线性探查法的“堆积”问题是指_______。 A 不同探查序列的关键码占据了可利用的空桶，使得寻找某一关键码需要经历很长的探查序列。 B 不同探查序列的关键码占据了可利用的空桶，使得插入某个关键码时找不到空桶。 C 不同探查序列的关键码占据了可利用的空桶，导致寻找某个关键码时出现错误。 D 不同探查序列的关键码占据了可利用的空桶，为了保证算法能够寻找到正确的关键码，不得不将装载因子限制在某个阀值之下。 (5) 在中序线索二叉树（使用 lTag，rTag）中，一个结点的中序后继是__________。（多选） A 如果其 rTag 为 0，则后继是其 rightChild 所指结点的最左后代； B 如果其 rTag 为 0，则后继是其 rightChild 所指结点； C 如果其 rTag 为 1，则后继是其 rightChild 所指结点的最左后代； D 如果其 rTag 为 1，则后继是其 rightChild 所指结点。 (6) 假设有一棵二叉树的结点前序排列是 1、2、3、4、5。下面的序列不可能是这棵二叉树的中序排列。 A 3、2、1、4、5 B 2、3、1、4、5 第 7 页共 12 页

C 2、1、4、5、3 D 2、1、5、3、4 (7) 有 11 个结点的 AVL 树的最大高度为_______。(假设叶结点的高度为 1，树的高度为根结点的高度) A 3 B 4 C 5 D 6 (8) 下面的排序算法中，时间复杂度不是 O(nlog2n)的算法是_______。（多选） A 折半插入排序 B 堆排序 C 快速排序 D 基数排序 (9) 使用 Prim 算法求解最小生成树时，使得算法效率较高的图的表示方式是_________。 A 邻接矩阵表示 B 邻接表表示 C 以上表示方法都一样 (10) 在 B 树的删除操作中，最坏情况下可能需要读写磁盘_________次。（假设内存工作区足够大，但操作之前各个结点都存放在磁盘上，B 树的高度为 h） A 2h-2 B 2h-1 C 3h-1 D 3h-2 次得分３、解答题。（每小题 5 分，本题满分 20 分） (1) 使用一个 32 位整数以位向量集合的方式来表示 0 到 31 之间的整数的子集。请写出打印集合 s 中所有元素的代码。 (2) 假设一棵二叉树 T 的中序遍历序列和层次遍历（按层次递增顺序排列，同一层次自左向右）序列分别是 ABCDGEF 和 CAEBDFG。请写出该二叉树的后序遍历序列。 (3) 已知图的邻接矩阵为: V2 V1 V3 V4 V5 V6 V1 V2 V3 V4 V5 V6 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 1 1 0 1 0 0 0 0 1 0 0 1 0 0 0 1 0 0 请写出全部拓扑排序序列。（4）对图 3－1 所示的 AOE 网络，求出每个活动的最早开始时间 e()和最迟开始时间 l(), 并确定哪些活动是关键活动。第 8 页共 12 页 ADBGFEa1:5a6:10a3:4a4:3a2:20a5:20a7:7图3－1

资料库

南京大学《数据结构》试卷.pdf

相关推荐

课程资源

热门标签

最新资料