(南昌大学2001年数据结构考研试题和参考答案.docVIP

南昌大学2001年数据结构考研试题和参考答案 报考专业:计算机应用 考试科目:数据结构 (A) 一. 选择题(每题选择一个答案, 将序号填入下划线处,每题2分,共10分) 1. 假定初始序列是递增的,并且按递增序排列,则( )排序方法花时间最少. A.快速 B. shell C.直接插入 D.冒泡 2. 二维数组 a[0..8, 1..10]按行存放时元素 a[ 8,5 ]的起始地址与按列存放时元素( )的起始地址相同. A. a [8,5] B. a [3,10] C. A[5,8] D. A[0,9] 3. 有一棵平衡二叉树,根结点为A,A的右孩子为B,B的左孩为叶结点C,当A,B二结点的平衡因子分别为( )时,在结点C下, 插入一个新结点后得到的新树是不平衡的. A. 0,0 B. 1,0 C. –1,0 D. 0,1 4.在循环链表中设立一个头结点的理由是( ). A.便于找到链表的首结点 B.可以用头结点记录链表长度 C.可以使得作插入,删去时不必顾及插入的或删去的结点是否链表的首结点. D.可以把首结点与尾结点公开 5.非空的广义表可与有根有序的有向图对应,如果一个有根的有向图中含有回路,那么它对应的广义表是( ) A.线性表 B.纯表 C.再入表 D.递归表 二.填空题(每题2分,共10分) 1. 有20个元素的有序表按二分法查找,假定查找每个元素的概率是相等的,则查找成功的平均比较次数为________次. 2. 链接栈的结点有二个域: info, link ,栈顶指针为st, 下列程序段可以把元素x压入栈内: new(p); p?.inf=x; ______; 3. 一个好的散列函数的标准是________________. 4. 一个循环队列用数组Q[0..100]存贮其元素, 已知队头,队尾指针分别为80与50, 则当前队列中有_______个元素. 5. 用200个不同的数来构造二叉排序树, 其高度不会超过_______,但也不会少于_______(假定空二叉树的高度为0). 三.算法应用题(每题6分, 共30分) 1. 对下图表示的树林, (1)写出它的后根序序列.(2)画出与它对应的二叉树. A D G B E H C F I 2. 对序列(26,36,41,38,44,15,68,12,6,51,25)散列存贮于数组A[0..14]中,散列函数为H(R)=Rmod13, 用线性探测法解决冲突,请画出散列表的状况. 3.设有关键码序列: 51(1), 73, 47,95,49,51(2).试写出快速排序(从小到大)与堆排序(从大到小)的最终结果. 4.画出下图的邻接表(要求:出边表中的结点按序号由小到大排列),然后使用该邻接表手工执行深度优先算法(从结点6开始),请写出你得到的遍历序列. 1 2 6 3 5 4 5.对下图用用Prim算法从结点6开始构造最小生成树,(1)请用图表示构造的过程.(2)如果从其他结点开始,有没有可能构造出不相同的最小生成树? (图略) 四.算法设计题(共50分) 1. 求带权有向图中每对结点之间的最短路径的Floyd算法如下: (1)(Path数组置初态) for I:= 1 to n do for j:= 1 to n do if adj[I,j]? then path[I,j]:=(1) else path[I,j]:=(2); (2)(求最短路径) for k:= 1 to n do for I:= 1 to n do for j:= 1 to n do if adj[I,j]adj[I,k]+adj[k,j] then begin adj[I,j]:=(3);path[I,j]:=(4) end 请你解答如下问题(1)完成上