【精品】数据结构概论

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

2、。A.线性结构B.树结构C.图结构D.集合结构5.链栈与顺序栈相比，比拟明显的优点是D A.插入操作更加方便B.删除操作更加方便C.不会出现下溢的情况D.不会出现上溢的情况6.二叉树中第5层上的结点个数最多为C A.8B.15C.16D.327.在表长为n的链表中进行线性查找，查找成功时，它的平均查找长度为A.ASL=nB.ASL=( n+1)/2C.ASL=D.ASL Iog2(n+1)-18. 对22个记录的有序表进行折半查找，当查找失败时，至少需要比拟 B 次关键字。A.3B.4C.5D.69. 图的邻接表如下所示，根据算法，那么从顶点0出发按广度优先遍历的结点序列是A A. 0 3 2

3、 1B. 0 1 2 3C. 0 1 3 2D.O 3 1 2第 9题配图：数组的下标为 0,1,2,3 10. 对于哈希函数 Hkey=key%13,被称为同义词的关键字是D A.35 和 41B.23和 39C.15 和 44D.25和 5111. 图的深度优先遍历类似于二叉树的A A.先序遍历B.中序遍历C.后序遍历D.层次遍历12. 下述几种排序方法中，稳定的排序算法是A A.直接插入排序B.快速排序C.堆排序D.希尔排序13. 依次取出元素与已排序序列初始时为空 置上的方法，称为C A.希尔排序B.C.插入排序D.中的元素进行比拟，将其放入已排序序列的正确位冒泡排序 选择排序14.

4、二叉树是非线性数据结构，所以A.它不能用顺序存储结构存储C.顺序存储结构和链式存储结构都能存储A )B.它不能用链式存储结构存储D.顺序存储结构和链式存储结构都不能使用15. 有8个结点的无向图最多有 B 条边。A.14C.56B.28D.112、填空题每题 1分，共15 分1当问题的规模n趋向无穷大时，算法执行时间Tn的数量级被称为算法的_时间复杂度_2设数组aMM为最大空间个数作为循环队列 Q的存储空间，front为队头指针指向第一个存放数据的位置)，rear为队尾指针(指向最后一个存放数据位置的下一个)，那么判定Q队列的队满条件是 front=rear 。3假设一棵二叉树的前序序列是BE

5、FCGDH中序序列是FEBGCH那么它的后序序列必是_ FEGHDCB_4假设S和X分别表示进栈和出栈操作， 由输入序列“ABC得到输出序列“BCA的操作序列为SSXSXX 那么由a*b+c/d 得到“ ab*cd/+ 的操作序列为b, c, d , a 。5在一棵度为3的树中，度为2的结点个数是1,度为0的结点个数是6,那么度为3的结点个数是2。6在数据的存放无规律而言的线性表中进行检索的最正确方法是_线性查找 。7n个顶点e条边的图采用邻接矩阵存储，深度优先遍历算法的时间复杂度为1;假设采用邻接表存储时，该算法的时间复杂度为 2。8在堆排序和快速排序中，假设初始记录接近正序或反序，那么选用

6、堆排序 ;假设初始记录根本无序，那么最好选用快速排序 。9假设要求一个稠密图 G的最小生成树，最好用普里姆算法来求解。10 一棵深度为6的满二叉树有 1 个分支结点和 2个叶子。11在各种查找方法中，平均查找长度与结点个数n无关的查找方法是散列表法。12有向图G用邻接矩阵存储，其第i行的所有元素之和等于顶点i的 岀度。1.解答题(每题用普里姆(prim)8分，共40分)算法从右图中的顶点 1开始逐步构造最小生成树，要求画出构造的每一步。95答：假设N=(V,E)是一个具有n个顶点的连通网，T=(U,TE)是所求的最小生成树，其中U是T的顶点集，TE是T的边集。(1) 初始 U=u0(u0 V)

7、,TE= 0;(2) 在所有u U, v V-U的边中选一条代价最小的边(u0, v0)并入集合TE,同时将v0并入U ;(3) 重复(2),直到U=V为止。此时，TE中必含有n-1条边，那么T= (V, TE)为N的最小生成树。O11Q2.假设通信电文使用的字符集为a,b,c,d,e,f,g，假设这些字符在电文中出现的频度分别为：3,H.4I) (1.00fij 1 l d：HH 13待排序的序列为：25,47,36,21,90,84,62,78,15,32 。写出用(小根)堆排序的每一趟的结果。int main (i nt argc, char *argv) int array10 = 2

8、4, 17, 85, 13, 9, 54, 76, 45, 5, 63;int num = sizeof(array)/sizeof( in t);for(i nt i = 0; i nu m-1; i+) for(i nt j = 0; j num - 1 - i; j+) if(arrayj arrayj+1) int tmp = arrayj;arrayj = arrayj+1;arrayj+1 = tmp;for(i nt i = 0; i num; i+) prin tf(%d, arrayi);if(i = nu m-1) prin tf(n);4.一棵树的前序序列为：abefcg

9、dhijk，后序序列为：efbgcijkhda 。画出这棵树。5.闭散列表的长度为10(散列地址空间为0.9)，散列函数为H(K)=K%8,采用线性重新散列技术解决冲突，将以下一组数据25,17,39,47,83,55,99,34依次插入到散列表中，请画出散列表。答：(1) H(25) = 1(2) H(16) = 0(3) H(38) = 6 h(47) = 7H(79) = 7 与(4)冲突，于是线性重新散列即查找7后面的空槽，此时8为空，因此将79放入8(第九个位置)中(6) H(82) = 2 H(51) = 3(8) H(39) = 7 与(4)冲突，于是线性重新散列即查找7后面的空

10、槽，此时8已经有元素(5) ,9为空，因此将39放入9 (第十个位置)中，所以最终闭散列表的存储情况如下所示：位置：(0)( 1)( 2)( 3)( 4)( 5)( 6)( 7)( 8)( 9)值： 16258251空空 38477939。四、算法阅读、设计(共5分)1阅读以下函数algo,并答复以下问题：(5分)void algo(Queue *Q)Stack S;In itStack(&S);while (!QueueEmpty(Q)Push(&S, DeQueue(Q);while (! StackEmpty(&S)E nQueue(Q,Pop(&S);(1)假设队列q中的元素为(2,4,5,7,8), 其中“ 2为队头元素。写出执行函数调用algo(