数据结构概论

数据结构概论考核题一、单项选择题（每小题2分，共30分）TOC\o"1-5"\h\z下列编码中属前缀码的是（A ）{1,01,000,001} B.{1,01,011,010}C.{0,10,110,11} D.{0,1,00,11}设栈S和队列Q的初始状态为空，元素a,b,c,d,e,f依次进栈，一个元素退栈后即进入队列Q，若6个元素的出队的序列是b,d,c,f,e,a，则栈S的容量至少应当是（C ）A.6 B.4 C.3 D.2在具有n个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是（B）A.O（1） B.O（n）C.O（nlogn） D.O（n2）要表示省，市，区，街道的有关数据及其关系，选择（B ）比较合适。A.线性结构 B.树结构C.图结构 D.集合结构）B.删除操作更加方便D.不会出现上溢的情况）B.删除操作更加方便D.不会出现上溢的情况A.插入操作更加方便C.不会出现下溢的情况二叉树中第5层上的结点个数最多为（C）A.8 B.15C.16 D.32在表长为n的链表中进行线性查找，查找成功时，它的平均查找长度为（B）A.ASL=n B.ASL=（n+1）/2C.ASL='n+1 D.ASL^log2（n+1）-1对22个记录的有序表进行折半查找，当查找失败时，至少需要比较（B ）次关键字。A.3 B.4C.5 D.6已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是（A）A.0321 B.0123

C.0132（第9题配图：数组的下标为0,1,2,3）C.0132（第9题配图：数组的下标为0,1,2,3）对于哈希函数H（key）=key%13，被称为同义词的关键字是（D）A.35和41 B.23和39C.15和44 D.25和51图的深度优先遍历类似于二叉树的（A）A.先序遍历 B.中序遍历C.后序遍历 D.层次遍历下述几种排序方法中，稳定的排序算法是（A）A.直接插入排序 B.快速排序C.堆排序 D.希尔排序依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为（C）A.希尔排序 B.冒泡排序C.插入排序 D.选择排序二叉树是非线性数据结构，所以（A二叉树是非线性数据结构，所以（AA.它不能用顺序存储结构存储C.顺序存储结构和链式存储结构都能存储）它不能用链式存储结构存储D.顺序存储结构和链式存储结构都不能使用有8个结点的无向图最多有（B）条边。A.14 B.2856 D.112二、填空题（每小题1分，共15分）1当问题的规模n趋向无穷大时，算法执行时间T（n）的数量级被称为算法的时间复杂度一—。2设数组a[M]（M为最大空间个数）作为循环队列Q的存储空间，front为队头指针（指向第一个存放数据的位置)，rear为队尾指针(指向最后一个存放数据位置的下一个)，则判定Q队列的队满条件是__front==rear 。3若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列必是_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在堆排序和快速排序中，若初始记录接近正序或反序，则选用—;若初始记录基本无序，则最好选用。9若要求一个稠密图G的最小生成树，最好用_普里姆 算法来求解。10一棵深度为6的满二叉树有1个分支结点和2个叶子。11在各种查找方法中，平均查找长度与结点个数n无关的查找方法是—。12有向图G用邻接矩阵存储，其第i行的所有元素之和等于顶点i的出度 。三、解答题(每小题8分，共40分)用普里姆(prim)算法从右图中的顶点1开始逐步构造最小生成树，要求画出构造的每一步。答：假设N=(V,E)是一个具有n个顶点的连通网，T=(U,TE)是所求的最小生成树，其中U是T的顶点集，TE是T的边集。初始U={u0}(u0EV),TE5；在所有uEU,vEV-U的边中选一条代价最小的边(u0，v0)并入集合TE，同时将v0并入U；

(3)重复(2),直到U=V为止。此时，TE中必含有n-1条边，则T=(V,{TE})为N的最小生成树。假设通信电文使用的字符集为{a,b,c,d,e,f,g}，若这些字符在电文中出现的频度分别为：3，35，13，15，20，5和9，分别求出这些字符的等长编码以及哈夫曼编码，并比较他们的编码长度。11.如八八/\0.11«,17八八0.0!> 闻.〔〕了JO.1D/\JW口当恕嘤晤夫妾温码房从项结点开始.找IF子结点.也就呈祖关亭捋.款认注左为".拄右为L所以土’为希莅是mi,3舟1r：：u/e：ii]h^：idio4f：iouin[motionIL

待排序的序列为：25,47,36,21,90,84,62,78,15,32。写出用(小根)堆排序的每一趟的结果。intmain(intargc,char*argv[]){intarray[10]={24,17,85,13,9,54,76,45,5,63};intnum=sizeof(array)/sizeof(int);for(inti=0;i<num-1;i++){for(intj=0;j<num-1-i;j++){if(array[j]<array[j+1]){inttmp=array[j];array[j]=array[j+1];array[j+1]=tmp;}}}for(inti=0;i<num;i++){printf(〃％d〃，array[i]);if(i==num-1){printf(〃\n〃)；}已知一棵树的前序序列为：abefcgdhijk，后序序列为：efbgcijkhda。画出这棵树。答：前序序列为：abefcgdhijk，后序序列为：efbgcijkhda已知闭散列表的长度为10(散列地址空间为0..9)，散列函数为H(K)=K%8，采用线性重新散列技术解决冲突，将下列一组数据｛25,17,39,47,83,55,99,34｝依次插入到散列表中，请画出散列表。答：(1)H(25)=1H(16)=0H(38)=6H(47)=7⑸H(79)=7与(4)冲突，于是线性重新散列即查找7后面的空槽，此时8为空,因此将79放入8(第九个位置)中H(82)=2H(51)=3⑻H(39)=7与(4)冲突，于是线性重新散列即查找7后面的空槽，此时8已经有元素(5),9为空，因此将39放入9(第十个位置)中,所以最终闭散列表的存储情况如下所示：位置：(0)(1)(2)(3)(4)(5)(6) (7)(8)(9)值：16 25 82 51空空38 47 79 39。四、算法阅读、设计(共5分)1阅读下列函数algo,并回答问题：(5分)voidalgo(Queue*Q){StackS;InitStack(&S);while(!QueueEmpty(Q))Push(&S,DeQueue(Q));while(!StackEmpty(&S))EnQueue(Q,Pop(&S));}⑴假设队列q中的元素为(2,4,5,7,8),其中“2”为队头元素。写出执行函数调用algo(&