《南京大学《数据结构》试卷(含答案)》由会员分享，可在线阅读，更多相关《南京大学《数据结构》试卷(含答案)（12页珍藏版）》请在金锄头文库上搜索。
1、第 1 页 共 12 页 考试科目名称 数据结构数据结构 （A1 卷） 1、填空题。、填空题。 （每小题 2 分，本题满分 20 分） (1) C+语言中，数组是按行优先顺序存储的，假设定义了一个二维数组 A2030，每个元 素占两个字节，其起始地址为 2140，则二维数组 A 的最后一个数据元素的地址为 2140+2*(30*20-1) = 3338(3338,3339) 。 (2) 若 A，B 是两个单链表，链表长度分别为 n 和 m，其元素值递增有序，将 A 和 B 归并成一个按元素值递增有序的单链表，并要求辅助空间为 O(1)，则实现该功能的算法的时间复杂度为 O(m+n) 。 (3)
2、 快速排序的平均时间复杂度是_n*lg n_。 (4) 假设有一个包含 9 个元素的最小堆，存放在数组 A 中，则一定比 A3大的元素有_ _2 (A7,A8) _个； 一定比 A3小的元素有_2 (A0,A1)_个。 （元素从第 0 个位置开始存放） (5) 广义表(A),(B,C), D, (A), (E,F) 的长度是 4 ，深度是 4 。 (6) 有 10 个元素的有序表， 采用折半查找， 需要比较 4 次才可找到的元素个数为_3_。 (7）当两个栈共享一存储区时，栈利用一维数组 An表示，两栈顶指针为 top0与 top1，则栈满时的判断条件为_top0+1=top1_ 或者 top
3、0 = top1+1 _。 (8) 假设计算斐波那契数的函数 Fib(long n)定义如下： long Fib(long n) if(nrightchild-rightchild_。假设二叉树的结点结构为： 2、选择题。、选择题。 （每小题 2 分，本题满分 20 分） (1) 如果能够在只知道指针 p 指向链表中任一结点， 不知道头指针的情况下，将结点*p 从链表中删除，则这个链表结构应该是： ( B,C )（多选题） A. 单链表 B. 循环链表 C. 双向链表 D. 带头结点的单链表 (2) 以下哪种矩阵压缩存储后会失去随机存取的功能?( A ) A. 稀疏矩阵 B. 对称矩阵 C.
4、对角矩阵 D. 上三角矩阵 (3) 下面哪一方法可以判断出一个有向图是否有环（回路） ：( B ) (选 A，B 也对) A. 广度优先遍历 B. 拓扑排序 C. 求最短路径 D.求关键路径 (4) n 个结点的线索二叉树(没有头结点)上含有的线索数为（ B ） 得分 得分 leftchild data rightchild 第 2 页 共 12 页 A. 2n B. nl C. nl D. n (5) 循环队列存储在数组 A0.m中，则入队时队尾指针 rear 的操作为（ D ） A. rear=rear+1 B. rear=(rear+1) mod (m-1) C. rear=(rear+
5、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/-，其前
6、缀形式为：( 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 算法，写出从顶点
7、1 到其它各个顶点的最短路径和最短 路径长度。 1 3 5 2 4 6 结点编号 1 2 3 4 5 6 路径长度 0 11 7 12 14 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 得分 7 10 5 8 6 9 11 7 第 3 页 共 12 页 300 100 200 350 400 20 40 150 180 240 260 310 320 360
8、 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；且 相互之间不形成前缀关系就 是正确的。 (4)在 AVL 树的插入操作中，假设插入一个结点后，当前节点 p 的平衡因子是-2，其左子结点的平衡因子是+1，左子结
9、点的右子结点的平衡因子是-1。如图所示，请给出旋转调整之后的结构。 4 15 19 16 35 25 60 40 100 A B C t1 t2 t3 t4 -2 +1 -1 p A C B t1 t2 t3 t4 0 +1 -1 第 4 页 共 12 页 4、已知输入关键码序列为（10,90,20,60,78,35,42,31,15） ，地址区间为 011。 (1) 请设计一个散列函数，把上述关键码散到 011 中。画出散列表，冲突用线性探测法解 决。 （5 分） 散列函数为： f(x) = x % 12 允许其它的散列函数 0 1 2 3 4 5 6 7 8 9 10 11 60/1 31
10、/7 15/1 90/1 78/2 20/1 42/4 10/1 35/1 (2) 搜索元素 31 需要比较的次数是多少？（2 分） 7 (78-9-10-11-0-1 (成功） ） (3) 计算在等概率情况下查找成功的平均查找长度 ASLsucc。 （3 分） (1+7+1+1+2+1+4+1+1) / 9 = 19/9 5、 程序设计题。程序设计题。 （每小题 15 分，本题满分 30 分） 1. 设计一个算法，根据一棵二叉树的前序序列和中序序列，构造出这棵二叉树。 二叉树的结点都用字符表示。前序序列和中序序列都是字符串。二叉树的结点定义如下： struct binTreeNode cha
11、r 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 midEnd)coutdata
12、 = rt; int lLen = j - midSt; root-leftChild = treeRecursive(pre, preSt+1, preSt+lLen - 1, 得分 得分 第 5 页 共 12 页 mid, midSt,midSt+lLen-1); root-rightChild=treeRecursive(pre, preSt+lLen+1, preEnd, mid, midSt+lLen+1, midEnd); return root; 要点在于根据 preOrder 的第一个字符，在 midOrder 中找到左右子树的分界；然后递归调用生成左右子树；做到这一点，就可以
13、给出大部分分数。 可能有很多细节上不一样的地方，比如这里的 preEnd 指向的字符在相应的树中；但是有些人可能是 preEnd 指向下一个位置。或者传递参数时直接使用字符串传递。都是可以的。 如果使用别的办法，参考其效率，酌情给分。只要效率过得去，也可以得满分。但是纯粹枚举则得分不高。 2. 设计非递归算法实现图的深度优先遍历。 （图用邻接表表示，已经定义了一个顺序栈stacktop，top 为栈顶指针，使用 visit(node)来表示对顶点 node 的访问。 ） 图的邻接表结构定义如下： struct Edge int dest; Edge *link; /下一条边链指针 struct
14、 Vertex int data; Edge *adj; /边链表的头指针 class Graph private: Vertex *Nodetable; /顶点表 int cnt 解：解： Graph : : DFS(int v)/从 v 开始搜索； bool visitedMAXVert; Edge nextEdgeMAXVert; stack0 = v; nextEdge0 = graph.Nodetablev.adj; top = 0; visited(stacktop); 第 6 页 共 12 页 visitedstacktop = true; while(top = 0) while(nextEdgetop if(nextEdgetop != NULL) int nextVert = nextEdgetop-dest; visite(nextVert); /访问下一个邻接结点；保证了被压入栈中的顶点都被访问； visitednextVert = true; stacktop+1 = nextVert; /压栈，进入下一个结点； nextEdgetop+1 = Nodetabl
