期末试卷A（有答案）
一、选择题
1、从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（ ）排序法。 A.插入 B.选择 C.希尔 D.二路归并
2、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储， a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（ ）。 A.13 B.33 C.18 D.40
3、线性表的顺序存储结构是一种（ ）。 A.随机存取的存储结构 B.顺序存取的存储结构 C.索引存取的存储结构 D.Hash存取的存储结构
4、最大容量为n的循环队列，队尾指针是rear，队头：front，则队空的条件是（ ）。 A.（rear+1）MOD n=front B.rear=front C.rear+1=front
D.（rear-1）MOD n=front
5、在下列表述中，正确的是（ ） A.含有一个或多个空格字符的串称为空格串
B.对n（n>0）个顶点的网，求出权最小的n-1条边便可构成其最小生成树 C.选择排序算法是不稳定的
D.平衡二叉树的左右子树的结点数之差的绝对值不超过l
6、已知字符串S为“abaabaabacacaabaabcc”，模式串t为“abaabc”，采用KMP算法进行匹配，第一次出现“失配”（s!＝t）时，i＝j＝5，则下次开始匹配时，i和j的值分别（ ）。
A．i＝1，j＝0 B．i＝5，j＝0 C．i＝5，j＝2 D．i＝6，j＝2 7、下列叙述中，不符合m阶B树定义要求的是（ ）。 A．根结点最多有m棵子树 B．所有叶结点都在同一层上
C．各结点内关键字均升序或降序排列 D．叶结点之间通过指针链接
8、设X是树T中的一个非根结点，B是T所对应的二叉树。在B中，X是其双亲的右孩子，下列结论正确的是（ ）。 A.在树T中，X是其双亲的第一个孩子 B.在树T中，X一定无右兄弟 C.在树T中，X一定是叶结点 D.在树T中，X一定有左兄弟
9、有关二叉树下列说法正确的是（ ）。 A.二叉树的度为2
B.一棵二叉树的度可以小于2 C.二叉树中至少有一个结点的度为2 D.二叉树中任何一个结点的度都为2
10、数据序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中的（ ）的两趟排序后的结果。
A.选择排序 B.起泡排序 C.插入排序 D.堆排序
二、填空题
11、对n个记录的表r[1..n]进行简单选择排序，所需进行的关键字间的比较次数为______。 12、属于不稳定排序的有______。
13、VSAM系统是由______、______、______构成的。
14、关键码序列（Q，H，C，Y，Q，A，M，S，R，D，F，X），要按照关键码值递增的次序进行排序，若采用初始步长为4的希尔排序法，则一趟扫描的结果是______；若采用以第一个元素为分界元素的快速排序法，则扫描一趟的结果是______。
15、应用Prim算法求解连通网络的最小生成树问题。（1）针对如图所示的连通网络，试按如下格式给出在构造最小生成树过程中顺序选出的各条边。
（2）下面是Prim算法的实现，中间有5个地方缺失，请阅读程序后将它们补上。
16、阅读下列程序说明和程序，填充程序中的______。
【程序说明】本程序完成将二叉树中左、右孩子交换的操作。交换的结果如下所示（编者略）。
本程序采用非递归的方法，设立一个堆栈stack存放还没有转换过的结点，它的栈顶指针为tp。交换左、右子树的算法为： （1）把根结点放入堆栈。
（2）当堆栈不空时，取出栈顶元素，交换它的左、右子树，并把它的左、右子树分别入栈。
（3）重复（2）直到堆栈为空时为止。
17、设有一个空栈，栈顶指针为1000H（十六进制），现有输入序列为 l，2，3，4，5，经过PUSH，PUSH，POP，PUSH，POP，PUSH， PUSH之后，输出序列是______，而栈顶指针值是______。设栈为顺序栈，每个元素占4个字节。
18、设有N个结点的完全二叉树顺序存放在向量A[1：N]中，其下标值最大的分支结点为______。
三、判断题
19、对处理大量数据的外存介质而言，索引顺序存取方法是一种方便的文件组织方法。（ ）
20、倒排序文件的优点是维护简单。（ ）
21、在链队列中，即使不设置尾指针也能进行入队操作。（ ） 22、二维以上的数组其实是一种特殊的广义表。（ ） 23、二叉树是一般树的特殊情形。（ ）
24、对于有n个结点的二叉树，其高度为log2n。（ ） 25、排序算法中的比较次数与初始元素序列的排列无关。（ ）
26、线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。（ ） 27、当改变网上某一关键路径上任一关键活动后，必将产生不同的关键路径。（ ） 28、采用线性探测法处理散列时的冲突，当从哈希表删除一个记录时，不应将这个记录的所在位置置空，因为这会影响以后的查找。（ ）
四、简答题
29、将下列由三棵树组成的森林转换为二叉树（只要求给出转换结果）。
30、假定对有序表：（3，4，5，7，24，30，42，54，63，72，87， 95）进行折半查找，试回答下列问题：
（1）画出描述折半查找过程的判定树。 （2）若查找元素54，需依次与哪些元素比较? （3）若查找元素90，需依次与哪些元素比较?
（4）假定每个元素的查找概率相等，求查找成功时的平均查找长度。
31、二叉树的带权路径长度（WPL）是二叉树中所有叶结点的带权路径长度之和，给定一棵二叉树T，采用二叉链表存储，节点结构为：
其中叶节点的weight域保存该结点的非负权值。设root为指向T的根节点的指针，设计求T的WPL的算法。要求： （1）给出算法的基本设计思想。
（2）使用C或C++语言，给出二叉树结点的数据类型定义。
（3）根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
五、算法设计题
32、已知字符串s1中存放一段英文，写出算法format（s1，s2，s3，n），将其按给定的长度n格式化成两端对齐的字符串s2，其多余的字符送 s3。
33、设从键盘输入一整数的序列：a1，a2，a3，…，an，试编写算法实现：用栈结构存储输入的整数，当ai≠-1时，将ai入栈；当ai=-l时，输出栈顶整数并出栈。算法应对异常情况（入栈满等）给出相应的信息。
34、设记录R[i]的关键字为R[i]。KEY（1≤i≤k），树结点T[i]（1≤i≤K-1）指向败者记录，T[0]为全胜记录下标。写一算法产生对应上述R[f]（1≤f≤k）的败者树，要求除R[1..k]和Tr[0..k-1]以外，只用O（1）辅助空间。
35、写出算法，求出中序线索二叉树中给定值为x的结点之后继结点，返回该后继结点的指针。线索树中结点结构为：（ltag，lc，data，rc， rtag）。其中，data存放结点的值；lc、rc为指向左、右孩子或该结点前驱、后继的指针，ltag、rtag为标志域，若值为0，则lc、rc为指向左、右孩子的指针；若值为1，则lc、rc为指向其前驱、后继结点的指针。
参考答案
一、选择题
1、【答案】A 2、【答案】B 3、【答案】A 4、【答案】B 5、【答案】C 6、【答案】C 7、【答案】D 8、【答案】D 9、【答案】B 10、【答案】C
二、填空题
11、【答案】n（n-1）/2
12、【答案】希尔排序、简单选择排序、快速排序、堆排序等 13、【答案】索引集；顺序集；数据集
14、【答案】（Q，A，C，S，Q，D，F，X，R，H，M ,Y）；（F，H， C，D，a，A，M，Q，R，S，Y，X） 15、【答案】
(1)(0，3，1)；(3，5，4)；(5，2，2)；(3，1，5)；(1，4，3)
(2)① T[k]；toVex=i② min=MaxInt;③ mispos=i④ exit(0)⑤ T[i]； fromVex=v
【解析】Prim算法的执行类似于寻找图的最短路径的Dijkstra算法。假设 N={V，E}是连通图，ET是N上最小生成树边的集合。算法从VT={u0}， ET开始，重复执行下述操作：在所有u属于VT，v属于V-VT的边（u， v）属于E中找一条代价最小的边（u0，v0）加入集合ET，同时将v0并入VT，直到VT=V为止。
16、【答案】stack[tp]=t；p=stack[tp--]；p；++tp
【解析】本题主要使用堆栈完成了二叉树左右子树交换的操作。首先根结点进栈，然后判断栈是否为空，如果不为空，则取栈顶元素，交换取出结点的左右指针。并将左右指针分别进栈，重复这一操作。完成二叉树左右孩子的交换。 17、【答案】23；100CH 18、【答案】
【解析】最大的分支结点是最后一个叶子结点的父结点。
三、判断题
19、【答案】× 20、【答案】× 21、【答案】√ 22、【答案】√ 23、【答案】× 24、【答案】× 25、【答案】× 26、【答案】× 27、【答案】× 28、【答案】√
四、简答题
29、答：森林转换为二叉树分以下三步：
（1） （2） （3）
连线（将兄弟结点相连，各树的根看作兄弟）。
切线（保留最左边子女为独生子女，将其他子女分支切掉）。 旋转（以最左边树的根为轴，顺时针向下旋转45度）。
所以由上面三棵树转换得到的二叉树如图所示：
30、答：（1）判定树如图所示：
（2） 若查找元素54，需依次和元素30、63、42、54比较，查找成功。 （3） 若查找元素90，需依次和元素30、63、87、95比较，查找失败。 （4）
31、答：（1）算法的基本思路是利用递归的思想来求解二叉树的带权路径长度，如果当前节点不是叶子节点，那么当前节点为根的树的带权路径长度便等于它的子树的带权路径长度之和，对于此函数要传入一个当前节点的树高的形参，那么递归调用孩子节点时只需要将这个形参加一即可。
（2）
五、算法设计题
32、答：算法如下：
33、答：算法如下：
34、答：算法如下：
35、答：算法如下：
因篇幅问题不能全部显示，请点此查看更多更全内容