C.冒泡排序 D.插入排序
15.排序算法中，不稳定的排序是（ ）
A.直接插入排序 B.冒泡排序
C.堆排序 D.归并排序
二、填空题(本大题共13小题，每小题2分，共26分)
请在每小题的空格中填上正确答案。错填、不填均无分。
16.在数据结构中，数据的逻辑结构分为集合、________、树形结构和图状结构等四类。
17.通常从正确性、易读性、________和高效率等4个方面评价算法（包括程序）的质量。
18.顺序表的存储密度为________，而链表的存储密度为________。
19.对于栈只能在________插入和删除元素。
20.在循环队列中，存储空间为0～n-1,设队头指针front指向队头元素前一个空闲元素，队尾指针指向队尾元素，那么队满标志为front=(rear+1)%n，队空标志为________。
21.三个结点可构成________种不同形态的二叉树。
22.对于一棵具有n个结点的二叉树，当进行链接存储时，其二叉链表中的指针域的总数为2n个，其中________个用于链接孩子结点。
23.有向图G用邻接矩阵A［1··n，1··n］存储，其第i列的所有元素之和等于顶点Vi的________。
24.对二叉排序树进行________遍历，可得到排好序的递增结点序列。
25.采用折半查找方法进行查找的数据序列应为________且________。
26.索引文件只能是________，因为索引文件的组织方式是为随机存取而设计的。
27.在插入和选择排序中，若初始数据基本正序，则选用________；若初始数据基本反序，则选用________。
28.快速排序最好情况下的时间复杂度为________，最坏情况下的时间复杂度为________。
三、应用题(本大题共5小题，每小题6分，共30分)
29.已知一棵二叉树的中根序列和后根序列分别为B、D、C、E、A、F、H、G和D、E、C、B、H、G、F、A，试画出这棵二叉树，并给出其先根序列。
30.已知如题30图所示，用普里姆（prim）算法从顶点A开始求最小生成树。在算法执行之初，顶点的集合U={A，B}，边的集合TE={（A，B）}。试按照最小生成树的生成过程，分步给出加入顶点和边以后的集合U和TE的值。
31.设散列函数H（key）=key mod 11，给定键值序列为13、41、15、44、6、68、17、26、39、46，试画出相应的开散列表，并计算在等概率情况下查找成功时的平均查找长度。
32.从一个空的二叉排序树开始，依次插入关键字25、13、15、34、7、20、37，试分别画出每次插入关键字后的二叉排序树。
33.画出对应于序列{10，20，7，75，41，67，3，9，30，45}的初始堆（堆顶元素取最小值）。
四、算法设计题(本大题共2小题，每小题7分，共14分)
本新闻共
6页,当前在第
5页
1 2 3 4 5 6 
