(一)数据结构部分.pdf

（一）数据结构部分
1.已知W=组数，且表示的邻接矩阵如下图所示，如下要求（1）画出有向图（2）画出邻接
表
解：
1234567
10111000
20010010
30001110
40000100
50000011
61100001
70000000
aij=1代表Vi到Vj有一条有向边
有向图：

邻接表：
1234
236
3456
45
567
6127
7

2.3阶B-树如图所示，分别画出插入关键字20后和150后得到的B-树

B-树结点树最小不能少于M/2（取整），最大不到大于M
M为阶
插入20后B-树为

3.给出一组关键字T=（12，2，16，30，8，28，4，10，20，6，18）写出用下列算法从小
到大排序时第一趟结束时的顺序
（1）希尔排序（第一趟排序的增量为5）
（2）快速排序（轴元素为5）
解：
※希尔排序(增量为5表示位置间5为一组）
（12，2，10，20，6，18，4，16，30，8，28）
※快速排序（从后面找大的，从前面找小的）
（6，2，10，4，8，12，28，30，20，16，18）
4.画出和下列已知序列对应的树T：树的先根次序
序访问序列为GFKDAIEBCHJ;后根次序访问序列为DIAEKFCJHBG
※先根序列：根→δ树→δ树
后根序列：α树→δ树→根
判断题
1.在具有头结点的链式存储结构中，头指针指向链表中的第一个数据结点（X）
2.在单链表中，要访问某个环节，只要知道该结点的指针即可，因此单链表是一种随机存
取结构（X）
3.广义表是线性表的推广，是一类线性数据结构（X）
4.广义表中原子个数为广义表的长度（X）
5.二叉树中用树的前序遍历和中序遍历可以到处树的后序遍历（√）
6.哈夫曼树是带权路径长度最短的树，路径上树值较大的结点离根较近（√）
7.若连通图上各边权值均不相同，则该图的最小生成树是唯一的（√）
8.邻接表只能用于存储有向图，而邻接矩阵则可存储有向图和无向图（X）
9.AVL树是一棵二叉树，该树上任一结点的平衡因δ绝对值不大于1（√）
10.内排序的快速排序方法，在任何情况下均可得到最快的排序效果（X）

三、
设有一组关键字{9,01,23,14,55,20,84,27}
采用哈希函数：H（key）=keyMOD7,表长为10，用开放地址法的二次探测散列方法
1+i=（H(key)+di)MOD10(di=1平方，2平方，3平方...)解决冲突。要求：对该关键字序列
结构哈希表，指出有哪些同义词，并计算查找成功的平均查找长度。
※ki≠kj但H(ki）=H（kj）则ki和kj为同义词

同义词：9和23，14和84，20，55和27
查找成功时的平均查找长度为：
ASL=(1+1+1+2+3+4+1+2)/8=1.875
四、证明题：
1.有一非空树，其度为5，已知度为i的节点数为i个，其中1<=i<=5，证明其终端
节点个数为41.
※证明：
若n为节点总数，ni为度i的节点数则
n=n0+n1+n2+n3+n4+n5①
令B为分支数目，B=n-1②
所有的分支是由度为1，2，3，4，5的节点所提供
故B=n-1=n1+2n2+3n3+4n4+5n5③
由①②③知
n0+n1+n2+n3+n4+n5-1=n1+2n2+3n3+4n4+5n5
n0=n2+2n3+3n4+4n5+1
∵n2=2,n3=3,n4=4,n4=5
∴n0=2+6+12+20+1=41
假设称正读和反读都相同的字符序列为"回文"
例如"abcba"是回文，"abcde"和"ababab"则不是回文，试写一个算法判别读入的一个
"@"为结束符的字符序列是否为回文。
※intpalindrome_Test()
{Initstack(s);InitQueue(Q);
while（c=getchar（）！="@"）
{push（s，c）;EnQueue(Q，c);
}
while(!stackEmpty(s))
{pop(s,a);DeQueue(Q,b));
if(a!=b)returnERROR;
}
erturnOK;
}//palindiome-Test
五、试编写一个高效算法，查找未排序文件A(1...n)中得第k个最小的元素
注：第k个最小的元素；若M是A（1），A(2)...A(n)中的第k个最小元素，则A(1),A(2)
,...A(n)中至少有k个元素小于等于M,并且最多有k-1个元素小于M
思想：调用一个快速排序以后，有p-1（p：轴元素位置）个元素小于等于轴元素，且
n-p个元素大于等于轴元素，若k小于p则第k个最小元素在A(1,...p-1）中；若k=p，则
A(p)就是第k个最小元素，若k>p,则A(1,..n）中的第k个最小元素就是A(p+