数据结构综合题参考答案

1、 数据结构综合题部分参考答案(仅供参考)一、填空1、一个算法的效率可分为时间效率和空间效率。，TOC o 1-5 h z2、栈的特点是先讲后出.队列的特点是先进先出。、3、在线性表的顺序存储结构中，若每个元素占L个存储单元，则第i个元素ai的存储位置为L0C(ai)=L0C(a1)+(i-1)*L。4、已知一棵完全二叉树共139个结点，按照层次从左到右进行编号，根结点编号为1，则编号为60的左孩子编号为120右孩子编号为双亲编号为_30_。、5、已知P为单链表中的非首尾结点，在P结点后插入S结点的语句为：s-next=p-next;p-next=s;。6、在各种查找方法中，平均查找长度与结点个

2、数n无关的查法方法是哈希表査找法。7、算法时间复杂度的分析通常有两种方法，即事后统计和事前估计的方法,通常我们对算法求时间复杂度时，采用后一种方法。8、已知元素序列E,F,GH,I,J,K,L,M,N经过操作XXYXXYXYXYYXXYXYYYXY以后的出栈序列(注X表示入栈，Y表示出栈)FHIJGLMKEN。9、设数组A1.10,1.8的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存储，则元素A4,5的存储地址为_2056；若以列序为主序顺序存储,则元素A4,5的存储地址为2086。10、一个二叉树中叶子结点3个，度为1的结点4个，则该二叉树共有9个结点。11、在图G的邻接表

3、表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的度,对于有向图来说等于该顶点的出度_。12、二分查找的存储结构仅限于顺序存储结构，且是有序的。13、设顺序循环队列Q0：m-1的队头指针和队尾指针分别为F和R，其中队头指针F指向当前队头元素的前一个位置，队尾指针R指向当前队尾元素所在的位置，则出队列的语句为F=(F+1)%m。14、设线性表中有n个数据元素，则在顺序存储结构上实现顺序查找的平均时间复杂度为OM_,在链式存储结构上实现顺序查找的平均时间复杂度为15、设一棵二叉树中有n个结点，则当用二叉链表作为其存储结构时，该二叉链表中共有个指针域，个空指针域。16、设指针变量p指向

4、单链表中结点A，指针变量s指向被插入的结点B，则在结点A的后面插入结点B的操作序列为s-next=p-next;p-next=s;。17、设无向图G中有n个顶点和e条边，则其对应的邻接表中有_n_个表头结点和个表结点。18、设无向图G中有n个顶点e条边，所有顶点的度数之和为m，则e和m有m=2e_关系。19、设一棵二叉树的前序遍历序列和中序遍历序列均为ABC，则该二叉树的后序遍历序列为CBA。20、设一棵完全二叉树中有21个结点，如果按照从上到下、从左到右的顺序从1开始顺序编号，则编号为8的双亲结点的编号是4_，编号为8的左孩子结点的编号是。21、下列程序段的功能实现子串t在主串s中位置的算法

5、，要求在下划线处填上正确语句。intindex(chars,chart)i=j=0;while(i3-2-41v-1-3TOC o 1-5 h z28、设某无向图G的邻接表为21/，则从顶点V开始的深度优先遍历序列为(1，3,v-1-4-213v-1-344,2)_；广度优先遍历序列为_(1，3，2,4)。29、设指针变量p指向双向链表中的结点A,指针变量s指向被插入的结点X,则在结点A的后面插入结点X的操作序列为_S-left=p；s-right=p-right；P-right=s；p-right-left=s；(设结点中的两个指针域分别为left和right)。30、设完全有向图中有n个顶

6、点，则该完全有向图中共有n(n-1)条有向条；设完全无向图中有n个顶点，则该完全无向图中共有n(n-1)/2条无向边。31、设关键字序列为(K,K，K),则用筛选法建初始堆必须从第n/2一个元素开始进行筛选。l2n32、设一棵三叉树中有50个度数为0的结点,21个度数为2的结点,则该二叉树中度数为3的结点数有_坦_个。33、高度为h的完全二叉树中最少有_2k1_个结点，最多有_2h=1_个结点。34、设有一组初始关键字序列为(24,35,12,27,18,26)，则第3趟直接插入排序结束后的结果的是_12,24,35,27,18,26。35、设有一组初始关键字序列为(24,35,12,27,1

7、8,26),则第3趟简单选择排序结束后的结果的是_12,18,24,27,35,26。36、下面程序段的功能是实现一趟快速排序,请在下划线处填上正确的语句。structrecordintkey;datatypeothers;voidquickpass(structrecordr,ints,intt,int&i)intj=t;structrecordx=rs;i=s;while(ij)while(ix.key)j=j-1;if(ij)ri=rj;i=i+1;while(_ij&ri.keyx.key_)i=i+1；if(ij)rj=ri；j=j-1；ri=x；,37、for(i=1,t=1,s=

8、0；irj+1)temp=rj+1;一rj+1=rj一;rj=temp;exchange=1;if(exchange=0)return；39下面程序段的功能是实现二分查找算法，请在下划线处填上正确的语句。structrecordintkey;intothers;intbisearch(structrecordr,intk)intlow=0,mid,high=n-1;while(lownext=p;p-next=s;B、s-next=p-next;p-next=s;C、s-next=p-next;p=s;D、p-next=s;s-next=p;一个栈的入栈序列是a,b,c,d,e,则栈的不可能的

9、输出序列是（）。A、edcbaB、decbaC、dceabD、abcde判定一个栈ST（最多元素为m0）为空的条件是（）。B、ST-top=0D、ST-top=m0B、都是先进先出A、ST-top!=0C、ST-top!=m0栈和队列的共同点是（）A、都是先进后出C、只允许在端点处插入和删除元素D、没有共同点稀疏矩阵一般的压缩存储方法有两种,即（）。A、二维数组和三维数组B、三元组和散列C、三元组和十字链表D、散列和十字链表在线索化二叉树中,t所指结点没有左子树的充要条件是（）A、t-left=NULLB、t-ltag=1C、t-ltag=l且t-left=NULLD、以上都不对已知某二叉树的

10、后序遍历序列是dabec。中序遍历序列是debac，它的前序遍历序列是（）。A、acbedB、decabC、deabcD、cedba在一非空二叉树的中序遍历序列中,根结点的右边（）A、只有右子树上的所有结点B、只有右子树上的部分结点C、只有左子树上的部分结点D、只有左子树上的所有结点任何一棵二叉树的叶子结点在先序、中序和后序遍历序列中的相对次序（）A、不发生改变B、发生改变C、不能确定D、以上都不对对一个满二叉树,m个树叶,n个结点，深度为h,则（）A、n=h+mB、h+m=2nC、m=h-1D、n=2h-1在一个图中，所有顶点的度数之和等于所有边数的（）倍。TOC o 1-5 h zA、1/

11、2B、1C、2D、4具有6个顶点的无向图至少应有（）条边才能确保是一个连通图。B、6A、5C、7D、8对于一个具有n个顶点的无向图,若采用邻接矩阵表示，则该矩阵的大小（）A、nB、（n-1）2C、n-1D、n2采用邻接表存储的图的深度优先遍历算法类似于二叉树的（）。A、先序遍历B、中序遍历C、后序遍历D、按层遍历顺序查找法适合于存储结构为（）的线性表。A、散列存储B、顺序存储或链接存储C、压缩存储D、索引存储采用顺序查找方法查找长度为n的线性表时,每个元素的平均查找长度为A、nB、n/2C、（n+1）/2D、（n-1）/2下述几种排序方法中,平均查找长度最小的是（）答案A、插入排序B、选择排序

12、C、快速排序D、归并排序算法分析的两个主要方面是（）A、正确性和简单性B、可读性和文档性C、数据复杂性和程序复杂性D、时间复杂度和空间复杂度线性表采用链式存储结构时，其地址（）。A、必须是连续的B、部分地址必须是连续的C、一定是不连续的D、连续与否均可以向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（）个元素A、64B、63C、63.5D、7在一个单链表中，若删除p所指结点的后续结点，则执行（）A、p-next=p-next-next;B、p=p-next;p-next=p-next-next;C、p-next=p-next;D、p=p-next-next;一个队列

13、的入列序列是1,2,3,4,则队列的输出序列是（）。A、4,3,2,1B、1,2,3,4C、1,4,3,2D、3,2,4,1判定一个栈ST（最多元素为mO）为栈满的条件是（）。A、ST-top!=0B、ST-top=0C、ST-top!=mO-1D、ST-top=mO-1线性表是具有n个（）的有限序列（nMO）A、表元素B、字符C、数据元素D、数据项常对数组进行的两种基本操作是（）A、建立与删除B、索引和修改C、查找和修改D、查找与索引设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（）。A、2hB、2h-1C、2h+1D、h+130.某二叉树的前序遍历结点访问

14、顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf,则其后序遍历的结点访问顺序是（）。A、bdgcefhaB、gdbecfhaC、bdgaechfD、gdbehfca31.树最适合用来表示（）。A、有序数据元素B、无序数据元素C、元素之间具有分支层次关系的数据D、元素之间无联系的数据实现任意二叉树的后序遍历的非递归算法而不使用栈结构,最佳方案是二叉树采用（）存储结构A、二叉链表B、广义表存储结构C、三叉链表D、顺序存储结构具有五层结点的二叉平衡树至少有（）个结点。TOC o 1-5 h zA、10B、12C、15D、17在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和的（

15、）倍。A、1/2B、1C、2D、4在一个具有n个顶点的无向图中，要连通全部顶点至少需要（）条边。A、nB、n+1C、n-1D、n/2对于一个具有n个顶点和e条边的无向图,若采用邻接表表示,则表头向量的大小为()。A、nB、n+1C、n-1D、n+e采用邻接表存储的图的宽度优先遍历算法类似于二叉树的()。A、先序遍历B、中序遍历C、后序遍历D、按层遍历对线性表进行二分查找时,要求线性表必须()。A、以顺序方式存储B、以链接方式存储C、以顺序方式存储，且结点按关键字有序排序D、以链接方式存储，且结点按关键字有序排序有一个有序表为1,3,9,12,32,41,45,62,75,77,82,95,10

16、0,当二分查找值为82的结点时,()次比较后查找成功。B、2D、8A、1C、440、下述几种排序方法中,要求内存量最大的是()。答案A、插入排序B、选择排序C、快速排序D、归并排序41组成数据的基本单位是(C)。数据项(B)数据类型(C)数据元素(D)数据变量42设数据结构A=(D,R),其中D=1,2,3,4,R=r,r=l,2,next=0(C)head-next=head(D)head!=077设某棵二叉树的高度为10,则该二叉树上叶子结点最多有(C)。(A)20(B)256(C)512(D)102478设一组初始记录关键字序列为(13,18,24,35,47,50,62,83,90,1

17、15,134),则利用二分法查找关键字90需要比较的关键字个数为(B)。(A)1(B)2(C)3(D)479设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为(D)。(A)top=top+1;(B)top=top-1;(C)top-next=top;(D)top=top-next;80设输入序列是1、2、3、n,经过栈的作用后输出序列的第一个元素是n,则输出序列中第i个输出元素是(C)。(A)n-i(B)n-1-i(C)n+1-i(D)不能确定81为查找某一特定单词在文本中出现的位置，可应用的串运算是(D)A.插入B.删除C.串联接D.子串定位82设有序表中有1000个元素，则用

18、二分查找查找元素X最多需要比较(B)次。(A)25(B)10(C)7(D)183对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为(C)A.顺序表B.用头指针表示的单循环链表C.用尾指针表示的单循环链表D.单链表84设某完全无向图中有n个顶点，则该完全无向图中有(B)条边。(A)n(n-1)/2(B)n(n-1)(C)n2(D)n2-185设某棵二叉树中有2000个结点，则该二叉树的最小高度为(C)(A)9(B)10(C)11(D)12在数据结构中，从逻辑上可以把数据结构分为(D)A.动态结构和静态结构B.紧凑结构和非紧凑结构C.内部结构和外部结构线性结构和非线性结构已知图的邻接表

19、如下所示，根据算法，则从顶点V出发按广度优先遍历的结点序列是(A)D.若进栈序列为a,b,c,d,e，则栈的不可能的输出序列是(B)A.edcbaB.dceabC.decbaD.abcde把一棵树转换为二叉树后，这棵二叉树的形态是(A)。A.唯一的B.有多种C.有多种，但根结点都没有左孩子D.有多种，但根结点都没有右孩子为查找某一特定单词在文本中出现的位置，可应用的串运算是(D)A.插入B.删除C.串联接D.子串定位ALV树是一种平衡的二叉树，树中任一结点的(B)A.左、右子树的高度均相同B.左、右子树高度差的绝对值不超过1C.左子树的高度均大于右子树的高度D.左子树的高度均小于右子树的高度二

20、叉树是非线性数据结构，所以(C)。A.它不能用顺序存储结构存储；B.它不能用链式存储结构存储；C.顺序存储结构和链式存储结构都能存储;D.顺序存储结构和链式存储结构都不能使用用邻接表表示图进行广度优先遍历时，通常是采用(B)来实现算法的。A.栈B.队列C.树D.图94数据的最小单位是(A)。(A)数据项(B)数据类型(C)数据元素(D)数据变量函数substr(“DATASTRUCTURE”，5，9)的返回值为(A)。(A)“STRUCTURE”(B)“DATA”(C)“ASTRUCTUR”(D)“DATASTRUCTURE”深度为k的完全二叉树中最少有(D)个结点。(A)2k-1-1(B)2

21、k-1(C)2k-1+1(D)2k-197设哈夫曼树中的叶子结点总数为m若用二叉链表作为存储结构，则该哈夫曼树中总共有(B)个空指针域。(A)2m-1(B)2m(C)2m+1(D)4m四、应用题1、下图所示的森林的先根序列和后根序列；(1)(2)(3)求树(a)求森林先序序列和中序序列；将此森林转换为相应的二叉树BDEFCA；(2)先序序列：ABCDEFGHIJK;中序序列：参考答案：(1)先根序列：ABCDEF;后根序列:2、已知二叉树的前序遍历序列是AEFBGCDHIKJ,出它的后序线索二叉树。参考答案：中序遍历序列是EFAGBCHKIJD，画出此二叉树，并画NULLBDEFCAIJKHG

22、(3)森林转换为相应的二叉树；参考答案：拓扑序列如下：l2458910376ll125、已知一个图的顶点集V和边集E分别为：V=1,2,3,4,5,6,7;E=(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25;用普里姆算法、克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边，并计算最小生成树各边上的权值之和。参考答案：普里姆算法:(1,2)3,(1,3)5,(1,4)8,(4,6)4,(2,5)10,(4,7)20克鲁斯卡尔算法:(1,2)3,(4,

23、6)4,(1,3)5,(1,4)8,(2,5)10,(4,7)20最小生成树各边上的权值之和:3+5+8+4+10+20=506、设一组初始记录关键字序列为(45，80，48，40，22，78)，则分别给出第4趟简单选择排序和第4趟直接插入排序后的结果。(22，40，45，48，80，78)，(40，45，48，80，22，78)7、设一组有序的记录关键字序列为(13，18，24，35，47，50，62，83，90)，查找方法用二分查找，要求计算出查找关键字62时的比较次数并计算出查找成功时的平均查找长度。参考答案：2,ASL=(1*1+2*2+3*4+4*2)/9=25/98、画出向小顶堆中

24、加入数据4,2,5,8,3时，每加入一个数据后堆的变化。参考答案：9、已知待散列的线性表为（36，15，40，63，22），散列用的一维地址空间为0.6，假定选用的散列函数是H（K）=Kmod7，若发生冲突采用线性探查法处理，试：（1）计算出每一个元素的散列地址并在下图中填写出散列表：0123456（2）求出在查找每一个元素概率相等情况下的平均查找长度。参考答案：1)H(36)=36mod7=1;H(15)=15mod7=1;冲突H(15)=(1+1)mod7=2;H(40)=40mod7=5;H(63)=63mod7=0;H(22)=22mod7=1;.冲突H(22)=(1+1)mod7=2

25、;.冲突H2(22)=(2+1)mod7=3;012345663361522401+2+1+1+3(2)ASL=L6设完全二叉树的顺序存储结构中存储数据ABCDE，要求给出该二叉树的链式存储结构并给出该二叉树的前序、中序和后序遍历序列。设给定一个权值集合W=（3，5，7，9，11），要求根据给定的权值集合构造一棵哈夫曼树并计算哈夫曼树的带权路径长度WPL。设一组初始记录关键字序列为（19，21，16，5，18，23），要求给出以19为基准的一趟快速排序结果以及第2趟直接选择排序后的结果。13设无向图G（所右图所示），要求给出该图的深度优先和广度优先遍历的序列，并画给相应的生成树14、设一棵树T

26、中边的集合为(A,B),(A,C),(A,D),(B,E),(C,F),(C,G),要求用孩子兄弟表示法(二叉链表)表示出该树的存储结构并将该树转化成对应的二叉树。15、给出如图所示的无向图G的邻接矩阵和邻接表两种存储结构。16、简单选择排序275275*512061i=1061275*512275i=2061275*512275i=3061275*275512(2)快速排序512275275*275*275512(3)堆排序275275*061170已经是最大堆,交换275与170170275*061275对前3个调整275*170061275前3个最大堆,交换275*与0610611702

27、75*275对前2个调整170061275*275前2个最大堆,交换170与061061170275*275简单选择排序、快速排序和堆排序是不稳定的排序方法,试举例说明。(1)17、给出下图邻接矩阵和邻接表两种存储结构；写出图的拓扑序列。18设给定权集W=5,7,2,3,6,8,10,请构造画出关于W的一棵赫夫曼树，并求出其加权路径长度WPL。19已知一棵二叉树的先序序列是ABCDEFGHIJK,中序序列是CDBGFEAHJIK，请构造出该二叉树。20设有一组初始记录关键字为(45,80,47,40,22,68),要求构造一棵二叉排序树并给出构造过程;画出删除45后的二叉排序树。21、(1)求

28、树三棵树的先根序列和后根序列求森林先序序列和中序序列；把森林转换为对应的二叉树。22、把下面的二叉树转换为相应的森林。五、算法题1、编写算法实现将单链表就地逆置，即不另外开辟结点空间，而将链表元素翻转顺序。思路：从链上依次取下结点，按照逆序建表的方法重新建表。voidReverse(LinkList&L)p=L-next;/原链表L-next=NULL;/新表(空表)while(p)/从原链表中取下结点ss=p;p=p-next;/插入L新表表头s-next=L-next;L-next=s;2、设计在链式结构上实现简单选择排序算法。voidsimpleselectsorlklist(lklis

29、t*&head)lklist*p,*q,*s;intmin,t;if(head=0|head-next=0)return;for(q=head;q!=0;q=q-next)min=q-data;s=q;for(p=q-next;p!=0;p=p-next)if(minp-data)min=p-data;s=p;if(s!=q)t=s-data;s-data=q-data;q-data=t;3、设计在链式存储结构上合并排序的算法。voidmergelklist(lklist*ha,lklist*hb,lklist*&hc)lklist*s=hc=0;while(ha!=0&hb!=0)if(ha

30、-datadata)if(s=0)hc=s=ha;elses-next=ha;s=ha;ha=ha-next;elseif(s=0)hc=s=hb;elses-next=hb;s=hb;hb=hb-next;if(ha=0)s-next=hb;elses-next=ha;4、设计在二叉排序树上査找结点X的算法。bitree*bstsearch1(bitree*t,intkey)bitree*p=t;while(p!=0)if(p-key=key)return(p);elseif(p-keykey)p=p-lchild;elsep=p-rchild;return(0);5、设有两个单链表A、B,其中元素递增有序，编写算法将A、B归并成一个按元素值递减(允许有相同值)有序的链表C,要求用A、B中的原结点形成，不能重新申请结点。算法思路：利用A、B两表有序的特点，依次进行比较，将当前值较小者摘下，插入到C表的头部，得到的C表则为递减有序的。算法如下：LinkListmerge(LinkListA,LinkListB)/*设A、B均为带头结点的单链表*/LinkListC;LNode*p,*q;p=A-next;q=B-next;C=A;/*C表的头结点*/C-next=NULL;free(B);while(p&q)if(p-datadata)s=p;p=p-next;elses=q