数据结构试题.docx
《数据结构试题.docx》由会员分享，可在线阅读，更多相关《数据结构试题.docx（9页珍藏版）》请在冰点文库上搜索。
数据结构试题
数据结构试题
2004年03月20日
一、是非题（下列各题，你认为正确的，请在题干的括号内打“√”，错的打“×”。
每题1分，
共10分）
1、顺序表中所有结点的类型必须相同。
……………………………………………………（ ）
2、链接表中所有灵活利用存储空间，所以链表都是紧凑结构。
…………………………（ ）
3、用Ch1，Ch2表示两个字符，若Ord（Ch1）＜Ord（Ch2），则称Ch1＜Ch2。
………………（ ）
4、Shell排序方法是不稳定的。
……………………………………………………………（ ）
5、只允许最下面的二层结点的度数小于2的二叉树是完全二叉树。
……………………（ ）
6、若检索所有结点的概率相等，则内部路径长度大的二叉树其检索效率高。
…………（ ）
7、n个结点的有向图，若它有n（n－1）条边，则它一定是强连通的。
……………………（ ）
8、广义表中，若限制表中成分的共享和递归所得到的结构是树结构。
…………………（ ）
9、多维数组元素之间的关系是线性的。
……………………………………………………（ ）
10、任何无环的有向图，其结点都可以排在一个拓扑序列里。
…………………………（ ）
二、填空题（每题2分，共20分）
1、数据的逻辑结构可形式地用一个二元组B＝（K，R）来表示，其中K是（ ），R是（ ）。
2、采用（ ）的方法，可以把对不等长表目线性表的处量转化为对等长表目的目录来处理。
3、一个串，除自身之外的所有子串都是该串的（ ）。
4、树形选择排序总的时间开销为（ ）。
5、按先根次序法周游树林正好等同于按（ ）周游对应的二叉树。
6、外部路径长度E定义为从扩充二叉树的（ ）到每个（ ）的路径长度之和。
7、在图结构中，如果一个从Vp到Vq的路径上除Vp和Vq可以相同外，其它结点都不相同，则称此路
径为一（ ）称为回路。
8、栈是一种（ ）表。
9．带权的（ ）又称为网络。
10、n×n的三对角矩阵按“行优先顺序”存储其三对角元素，已和a11的存储地址为LOC（a11），矩
阵的每个元素占一个存储单元，则aij（i＝1，j=1，2或1＜i＜n，j＝i－1，i，i＋1或i＝n，
j＝n－1，n）的存储地址为LOC（aij）＝（ ）。
三、单选题（在本题的每一小题的备选答案中，只有一个答案是正确的，请把你认为正确答案的题号，
填入题干的括号内。
多选不给分。
第1、2题各2分，第3、4题各3分，共10分）
1、对于单链表形式的队列，队空的条件是………………………………………………（ ）
①F＝R＝nil ②F＝R ③F≠nil且R＝nil ④R－F＝1
2、下述排序算法中，稳定的是……………………………………………………………（ ）
①直接选择排序 ②表插入排序 ③快速排序 ④堆排序
3、四组含C1～C7的结点序列中，哪一种是下列有向图的拓扑序列 …………………（ ）
①C1，C2，C6，C7，C5，C4，C3 ②C1，C2，C6，C3，C4，C5，C7
③C1，C4，C2，C3，C5，C6，C7 ④C5，C7，C4，C1，C2，C6，C3
4、下列广义表中，长度为2的有 …………………………………………………………（ ）
A＝（a，b） B＝（（c，（a，b）），d）
C＝（c，（a，b）） D＝（（a，b），（c，（a，b）））
①A ②A，C ③A，B ④A，B，C，D
四、简答、应用题（每题5分，共30分）
1、在双链表中，要在指针变量P所指结点之后插入一个新结点，请按顺序写出必要的算法步骤。
（设：
P所指结点不是链表的首尾结点，q是与p同类型的指针变量）
2、具有共享后备区组织的可利用空间表技术为什么并没有真正解决共享问题？
3、已知待排序文件各记录的排序码顺序如下
72 73 71 23 94 16 05 68
请列出快速排序过程中每一趟的排序结果。
4、设有如下关键码
2， 4， 6， 9， 11， 16
基本区域长度为8，散列函数采用除余法，用结合的同义词子表处理碰撞。
试画出其存储图，
并说明是否产生堆积现象。
5、画出下列网络的最小生成树。
6、画出广义表W（X（W，a，Y（W）），Y（W））的双链图表示。
五、算法设计题（每题10分，共30分）
1、下面给出了起泡排序算法，请填写算法中的空框，使算法正确。
TYPEnode＝RECORD
key：
integer；
info：
datatype
END；
VAR i，j：
integer；
flag：
0..1；
X：
node；
R：
ARRAR[1..n]OFnode；
①[每循环一次作一次起泡]
循环i以1为步长，从1到n－1，执行下列语句
（1）（ ）
（2）循环j以1为步长，（ ），执行
若（ ）＜R[j].key
则flag←1；
X←R[j]；（ ）；R[j＋1]←X
（3）若（ ）
则跳出循环
②算法结束
2、下面给出了在对称序穿线树中找指定结点在后序下的前驱算法，请填写算法中的空框，使算法
正确。
TYPEnode＝RECORD
info：
datatype；
llink，rlink：
↑node
END；
VARp：
↑node； [p指向指定结点]
q：
↑node； [q指向指定结点在后序下的前驱]
① 若p↑.rlink＞0
则（ ），算法结束
否则q←p
②
（1） 循环当（ ）时，反复执行
（ ）
（2） （ ）
③ 算法结束
3、下面是求带权的外部路径长度最小的扩充二叉树的Huffman算法，设数组tree中前m个是外部结
点，后m－1个是内部结点，请填写算法中的空框，使算法正确。
算法结束时，整个扩充二叉树
已形成，顺序存放在tree中，tree（2m－1）是根结点。
TYPEnode＝RECORD
tag：
0..1
WW：
real；
llink，rlink：
0..2m－1
END；
VARtree：
ARRAY[1..2m－1]OFnode；
W：
ARRAY[1..m]OFreal； [外部结点的权]
m1，m2：
real；
x1，x2，i，j：
1..2m－1；
①初始化
循环i以1为步长，从1到m，执行
tree[i].WW←W[i]
②[逐步构造扩充的二叉树]
循环i以1为步长，从1到m－1，执行
（1）[准备找两个最小的权]
m1←＋∞；m2←＋∞；[＋∞表比所有W[i]都大的实数]
x1←0；x2←0
（2）[找两个最小的权]
循环j以1为步长，从1到（ ），算法结束
若tree[j].WW＜m1且tree[j].tag＝0
则m2←m1：
x2←x1；
m1←tree[j].WW；（ ）
否则若tree[j].WW＜m2且（ ）
则（ ）；x2←j
（3）[标记]
tree[x1].tag←1；tree[x2].tag←1
（4）[构造子树]
（ ）
tree[m＋i].llink←x1；
tree[m＋i].rlink←x2
（5）[算法结束]
③[算法结束]
答 案
一．是非题
1．× 2．× 3．√ 4．√ 5．×
6．× 7．√ 8．√ 9．× 10．√
二．填空题
1．结点的有穷集合、 K上关系的有穷集合；
2．索引；
3．真子串；
4．O（n·log2n）；
5．前序法；
6．根、 外部结点
7．简单路径；
8．线性表；
9．连通图；
10．Loc（a11）＋2*（i－1）＋j－1。
三．多选题
1．①； 2．②； 3．④； 4．④；
四、
1．答：
new（q）；
q↑.llink←p；
q↑.rlink←p↑.rlink；
p↑.rlink↑.llink←q；
p↑.rlink←q。
评分细则：
按顺序每对一个给1分，全对计5分。
2．答：
有两点理由：
①两个不同可利用空间表的结点空间不能共享；
②后备空间一经分配，就不再释放到后备区共享。
评分细则：
答对1点，给3分，全对计5分。
3．答：
各趟结果如下：
[68 05 71 23 16] 72 [94 73]
[16 05 23]68[71] 72 [94 73]
[05]16[23]68[71] 72 [94 73]
05 16[23]68[71] 72 [94 73]
05 16 23 68 71 72 [94 73]
05 16 23 68 71 72 [73]94
05 16 23 68 71 72 73 94
4．答：
node k1 k2 k3 k4 k5 k6
key 2 4 6 9 11 16
keymod7 2 4 6 2 4 2
node link
0
1
2
3
4
5
6
7
k1
7
k6
∧
k2
5
k5
∧
k3
∧
k4
3
5．答：
6．答：
五、（类Pascal实现的答案）
1．
（1） flag←0；
（2） 1到n-1；
（3） R[j＋1].key；
（4） R[j]←R[j＋1]；
（5） flag＝0
2．
（1） q←p↑.rlink
（2） q.↑link＜0
（3） q←（－1）*（q↑.llink）
（4） q←q↑.llink
评分细则：
第三空框填写正确计4分，其余每正确一个计2分。
3．
（1） m＋i－1
（2） x1←j
（3） tree[j].tag＝0
（4） m2←tree[j].ww
（5） tree[m＋i].ww←tree[x1].ww＋tree[x2].ww
升级会员 