南京大学《数据结构》试卷(含答案)

《南京大学《数据结构》试卷(含答案)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、考试科目名称数据结构（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*lgn_________

2、__。(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]_

3、或者top[0]=top[1]+1___。(8)假设计算斐波那契数的函数Fib(longn)定义如下：longFib(longn){if(n<=1)returnn;elsereturnFib(n-1)+Fib(n-2)}计算Fib(5)时的递归调用树（即指明函数调用关系的树）的高度是___4_____。假设叶子结点所在的高度为0。(9)完全二叉树按照层次次序，自顶向下，同层从左到右顺序从0开始编号时，编号为i的结点的左子结点的编号为___2*i+1______。(10)假设用子女—兄弟链表方式表示森林，对应的二叉树的根结点是p，那么森林的第三棵树的根结点在

4、二叉树中对应的结点是：___p->rightchild->rightchild____________。假设二叉树的结点结构为：leftchilddatarightchild得分2、选择题。（每小题2分，本题满分20分）(1)如果能够在只知道指针p指向链表中任一结点，不知道头指针的情况下，将结点*p从链表中删除，则这个链表结构应该是：(B,C)（多选题）A.单链表B.循环链表C.双向链表D.带头结点的单链表(2)以下哪种矩阵压缩存储后会失去随机存取的功能?(A)A.稀疏矩阵B.对称矩阵C.对角矩阵D.上三角矩阵(3)下面哪一方法可以判断出一个有向图是否有环

5、（回路）：(B)(选A，B也对)A.广度优先遍历B.拓扑排序C.求最短路径D.求关键路径(4)n个结点的线索二叉树(没有头结点)上含有的线索数为（B）第1页共12页A.2nB.n－lC.n＋lD.n(5)循环队列存储在数组A[0..m]中，则入队时队尾指针rear的操作为（D）A.rear=rear+1B.rear=(rear+1)mod(m-1)C.rear=(rear+1)modmD.rear=(rear+1)mod(m+1)(6)使用加权规则得到改进的Union操作WeightedUnion，其目的是：(B)A.提高Union操作的时间性能B.提高F

6、ind操作的时间性能C.减少Union操作的空间存储D.减少Find操作的空间存储(7)使用Kruscal算法求解最小生成树时，为了设计效率较高的算法,数据结构方面可以选择：(A)A.利用最小堆存储边B.利用栈存储结点C.利用二维数组存储结点D.利用并查集存储边(8)已知一算术表达式的后缀形式为ABC*+DE/-，其前缀形式为：(D)A.-A+B*C/DEB.-A+B*CD/EC.-+*ABC/DED.-+A*BC/DE(9)n个关键码排序，如果选用直接插入排序方法，则元素的移动次数在最坏情况下可以达到(B)。A.n*n/2B.n*(n-1)/2C.n/2

7、D.(n-1)/2(10)关键路径是AOE网络中AC。（多选）A.从源点到汇点的最长路径B.从源点到汇点的最短路径C.所有活动都是关键活动的路径D.最短回路得分３、简答题。（每小题5分，本题满分20分）(1)对如下无向图，按照Dijkstra算法，写出从顶点1到其它各个顶点的最短路径和最短路径长度。7713511108562469结点编号123456路径长度0117121415最短路径11-21-31-3-41-3-51-3-6(2）请画出在如下图所示的5阶B树中插入一个关键码360后得到的B树。100200300400204015018024026031

8、0320350370420430第2页共12页3001002003