南昌大学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)完成上述算法填空. (2)矩阵adj 的初值是什么?算法结束时,adj[I,j] 和path[I,j]的值表示什么意义?(14分)
2. 写出按对放序线索化以t 为根指针的二叉树的非递归算法.假定用负指针表示线索,并且对栈的基本运算均可调用(12分)
3. 写一算法,重排实型数组R[1..n]中元素的顺序,使得所有负数均排在非负数之前.(要求:不排序,附加空间0(1))(10分)
4. 有一个带有头结点的循环双链表,表头指针为head,结点有四个域,data ,flreg ,llink ,rlink ,其中flreg记录结点数据的访问次数.假定链表的结点已按访问次数不增序排列.(1)画出此链表的结构示意图.(2)写一算法查找链表中是否有值为x的结点,如有,则让该结点的访问次数加1 ,并且要使链表仍保持不增序,如没有,则不作任何工作.(14分)
