《数据结构概论》A卷

1、数据结构概论期末考核试题一、单项选择题( 每小题 2 分，共 30 分 )1. 下列编码中属前缀码的是 (B) A.1,01,000,001B.1,01,011,010 C.0,10,110,11D.0,1,00,112. 设栈 S 和队列 Q的初始状态为空，元素a,b,c,d,e,f依次进栈，一个元素退栈后即进入队列若 6 个元素的出队的序列是b,d,c,f,e,a，则栈 S 的容量至少应当是(C)在具有 n 个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是(B)Q，(1)(n)(nlogn)(n2)4. 要表示省，市，区，街道的有关数据及其关系，选择A. 线性结构B. 树结

2、构C. 图结构 D. 集合结构5. 链栈与顺序栈相比，比较明显的优点是(D)A. 插入操作更加方便B. 删除操作更加方便C. 不会出现下溢的情况D.不会出现上溢的情况(B) 比较合适。6. 二叉树中第 5 层上的结点个数最多为 (C)在表长为的链表中进行线性查找，查找成功时，它的平均查找长度为(B)=(n+1)/2=+ log2(n+1)-18. 对 22 个记录的有序表进行折半查找，当查找失败时，至少需要比较(B) 次关键字。已知图的邻接表如下所示，根据算法，则从顶点0 出发按广度优先遍历的结点序列是（第 9 题配图：数组的下标为0,1,2,3）(A)10. 对于哈希函数 H(key)=ke

3、y%13, 被称为同义词的关键字是 (D)和和 39和和 5111. 图的深度优先遍历类似于二叉树的(A)A. 先序遍历B. 中序遍历12. 下述几种排序方法中，稳定的排序算法是(B)A. 直接插入排序B. 快速排序13. 依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为 (C)A. 希尔排序B. 冒泡排序C. 插入排序D. 选择排序14. 二叉树是非线性数据结构，所以(C)A. 它不能用顺序存储结构存储B. 它不能用链式存储结构存储C. 顺序存储结构和链式存储结构都能存储D.顺序存储结构和链式存储结构都不能使用15. 有 8 个结点的无向图最

4、多有(B) 条边。二、填空题（每小题1 分，共 15 分）1 当问题的规模n 趋向无穷大时，算法执行时间T(n) 的数量级被称为算法的_时间复杂度 _。2 设数组 aM(M 为最大空间个数) 作为循环队列Q的存储空间， front为队头指针 ( 指向第一个存放数据的位置 ) ， rear 为队尾指针 ( 指向最后一个存放数据位置的下一个) ，则判定Q 队列的队满条件是_front=(rear+1)%m_。3 若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列必是_FEGHDCB。4 假设S和 X 分别表示进栈和出栈操作，由输入序列“ABC”得到输出序列“BCA

5、”的操作序列为 SSXSXX，则由“ a*b+c/d ”得到“ ab*cd/+ ”的操作序列为 _SXSSXXSSXSSXXX。_5 在一棵度为3 的树中，度为2 的结点个数是1，度为0 的结点个数是6，则度为3 的结点个数是_2_。6 在数据的存放无规律而言的线性表中进行检索的最佳方法是_顺序查找_。7n 个顶点 e 条边的图采用邻接矩阵存储，深度优先遍历算法的时间复杂度为_O(n2)_；若采用邻接表存储时，该算法的时间复杂度为_O(n+e)_。8 在堆排序和快速排序中，若初始记录接近正序或反序，则选用_堆排序 _；若初始记录基本无序，则最好选用_快速排序_。9 若要求一个稠密图G的最小生成

6、树，最好用 _普里姆 _算法来求解。10一棵深度为 6 的满二叉树有 _63_个分支结点和_32_个叶子。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，分别求出这些字符的等长编码以及哈夫曼编码，

7、并比较他们的编码长度。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 分 )voidalgo(Queue*Q)StackS;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 为一维数组，其中r0 到