数据结构概论期末考核试卷
一、单项选择题 (每小题2分，共30分)
1.下列编码中属前缀码的是( )
A.{1,01,000,001} B.{1,01,011,010}
C.{0,10,110,11} D.{0,1,00,11}
2. 设栈S和队列Q的初始状态为空，元素a,b,c,d,e,f依次进栈，一个元素退栈后即进入队列Q，若6个元素的出队的序列是b,d,c,f,e,a，则栈S的容量至少应当是( )
A.6 B.4 C.3 D.2
3.在具有n个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是( )
A.O(1) B.O(n)
C.O(nlogn) D.O(n2)
4.要表示省，市，区，街道的有关数据及其关系，选择( )比较合适。
A.线性结构 B.树结构
C.图结构 D.集合结构
5.链栈与顺序栈相比，比较明显的优点是( )
A.插入操作更加方便 B.删除操作更加方便
C.不会出现下溢的情况 D.不会出现上溢的情况
6.二叉树中第5层上的结点个数最多为( )
A.8 B.15
C.16 D.32
7.在表长为ｎ的链表中进行线性查找，查找成功时，它的平均查找长度为( )
A.ASL=n B.ASL=(n+1)/2
C.ASL= +1 D.ASL≈log2(n+1)-1
8.对22个记录的有序表进行折半查找，当查找失败时，至少需要比较( )次关键字。
A.3 B.4
C.5 D.6
9.已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是( )
A. 0 3 2 1 B. 0 1 2 3
C. 0 1 3 2 D.0 3 1 2
（第9题配图：数组的下标为0,1,2,3）
10.对于哈希函数H(key)=key%13,被称为同义词的关键字是( )
A.35和41 B.23和39
C.15和44 D.25和51
11.图的深度优先遍历类似于二叉树的( )
A.先序遍历 B.中序遍历
C.后序遍历 D.层次遍历
12.下述几种排序方法中，稳定的排序算法是( )
A.直接插入排序 B.快速排序
C.堆排序 D.希尔排序
13.依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为( )
A.希尔排序 B.冒泡排序
C.插入排序 D.选择排序
14.二叉树是非线性数据结构，所以 ( )
A.它不能用顺序存储结构存储 B.它不能用链式存储结构存储
C.顺序存储结构和链式存储结构都能存储 D.顺序存储结构和链式存储结构都不能使用
15.有8个结点的无向图最多有( )条边。
A.14 B.28
C.56 D.112
二、填空题（每小题1分，共15分）
1 当问题的规模n趋向无穷大时，算法执行时间T(n)的数量级被称为算法的________。
2 设数组a[M](M为最大空间个数)作为循环队列Q的存储空间，front为队头指针(指向第一个存放数据的位置)，rear为队尾指针(指向最后一个存放数据位置的下一个)，则判定Q队列的队满条件是_____________。
3 若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列必是________。
4假设S和X分别表示进栈和出栈操作，由输入序列“ABC”得到输出序列“BCA”的操作序列为SSXSXX，则由“a*b+c/d”得到“ab*cd/+”的操作序列为___________。
5 在一棵度为3的树中，度为2的结点个数是1，度为0的结点个数是6，则度为3的结点个数是________。
6 在数据的存放无规律而言的线性表中进行检索的最佳方法是____________。
7 n个顶点e条边的图采用邻接矩阵存储，深度优先遍历算法的时间复杂度为_______________；若采用邻接表存储时，该算法的时间复杂度为______________ 。
8 在堆排序和快速排序中，若初始记录接近正序或反序，则选用______________；若初始记录基本无序，则最好选用_______________。
9 若要求一个稠密图G的最小生成树，最好用______________算法来求解。
10 一棵深度为6的满二叉树有 ________________ 个分支结点和____________个叶子。
11 在各种查找方法中，平均查找长度与结点个数n无关的查找方法是_____________。
12 有向图G用邻接矩阵存储，其第i行的所有元素之和等于顶点i的____________。
三、解答题(每小题8分，共40分)
1. 用普里姆(prim)算法从右图中的顶点1开始逐步构造最小生成树，要求画出构造的每一步。
2. 假设通信电文使用的字符集为{a,b,c,d,e,f,g}，若这些字符在电文中出现的频度分别为：3，35，13，15，20，5和9，分别求出这些字符的等长编码以及哈夫曼编码，并比较他们的编码长度。
3. 待排序的序列为：25,47,36,21,90,84,62,78,15,32。写出用（小根）堆排序的每一趟的结果。
4. 已知一棵树的前序序列为：abefcgdhijk，后序序列为：efbgcijkhda。画出这棵树。
5. 已知闭散列表的长度为10(散列地址空间为0..9)，散列函数为H(K)=K%8，采用线性重新散列技术解决冲突，将下列一组数据{25,17,39,47,83,55,99,34}依次插入到散列表中，请画出散列表。
四、算法阅读、设计(共5分)
1 阅读下列函数algo,并回答问题：(5分)
void algo(Queue *Q)
{
Stack S;
InitStack(&S);
while (!QueueEmpty(Q))
Push(&S, DeQueue(Q));
while (! StackEmpty(&S))
ＥnQueue(Q,Pop(&S));
}
(1)假设队列q中的元素为(2,4,5,7,8),其中“2”为队头元素。写出执行函数调用algo(&q)后的队列q；
(2)简述算法algo的功能。
五、程序设计题（共10分）
1、已知r[]为一维数组，其中r[0]到r[n-1]为待排序的n个元素，排序好的元素仍放在r[0]到r[n-1]中，请写出对该数组进行非递归的直接插入排序算法，取名为insertsort(elemtype r[],int n)。 (10分)
