A.希尔排序 B.插入排序
C.冒泡排序 D.快速排序得分
二、填空题(本大题共13小题，每小题2分，共26分)
请在每小题的空格中填上正确答案。错填、不填均无分。
16.数据的逻辑结构通常包括集合、线性结构、____________和图状结构。
17.设双链表中结点的前趋指针和后继指针的域名分别为t1和r1，指针s指向双链表中的一个结点（该结点既非头结点，也非尾结点），则删除s指针所指向结点的操作为“s->tl->r1=s->r1；”和“____________”。
18.对稀疏矩阵进行压缩存储的目的是节省____________。
19.在一个具有n个结点的单链表中查找值为m的某结点，若查找成功，则需平均比较的结点数为____________。
20.深度为15的满二叉树上，第11层有____________个结点。
21.对一棵有100个结点的完全二叉树按层编号，则编号为49的结点，它的左孩子的编号为____________。
22.一个具有4个顶点的无向完全图有____________条边。
23.一个有向图G中若有孤i，Vj>、j，Vk>和i，Vk>，则在图G的拓扑序列中，顶点Vi，Vj和Vk的相对位置为____________。
24.在一棵二叉排序树上按____________遍历得到的结点序列是一个有序序列。
25.实现二分查找的存储结构仅限于顺序存储结构，且其中元素排列必须是____________的。
26.文件的检索有三种方式，它们是顺序存取、直接存取和____________存取。
27.在插入排序和选择排序中，若原始记录已基本有序，则较适合选用____________。
28.对n个元素的序列进行冒泡排序时，最多需进行____________趟。
三、应用题(本大题共5小题，每小题6分，共30分)
29.写出利用直接选择排序方法对一组关键码为（54，38，96，23，15，72，60）的记录进行排序时，每趟排序的结果。
30.已知一棵二叉树的中根遍历序列和后根遍历序列分别为BDAFEHGC和DBFHGECA，试画出这棵二叉树。
31.设闭散列表容量为7（散列地址空间0..6），给定表（30，36，47，52，34），散列函数H（K）=K mod 6，采用线性探测法解决冲突，要求：
（1）构造散列表；
（2）求查找数34需要比较的次数。
32.如题32图所示，在栈的输入端有6个元素，顺序为A，B，C，D，E，F。能否在栈的输出端得到序列DCFEBA及EDBFCA？若能，给出栈操作的过程，若不能，简述其理由。
题32图
33.已知无向图G的邻接表如题33图所示，请画出该无向图，并写出其按广度优先搜索时的访问序列。其中nil表示空。
题33图
四、算法设计题(本大题共2小题，每小题7分，共14分)
34.编写一个函数void insert(int *p，int size，int a)，其功能是将a插入指针变量p指向的长度为size的数组中。设数组中的数据已按升序排序。该函数要求实现的功能是：首先采用折半查找的方法，找出要插入数据的位置；然后按升序将数据插入该数组中。
35.某带头结点的单链表的结点结构说明如下：
typedef struct node1
{
int data;
struct node1 *next
}node；
试设计一个算法int copy(node *head1， node *head2)，将以head1为头指针的单链表复制到一个不带头结点且以head2为头指针的单链表中。
