数据结构综合练习题

1、列Q若6个兀素出列的顺序为E2、E4、E&E6、E5和E1,则栈S的容量至少应该是(A)6(B)4(C)3(D)27.将10阶对称矩阵压缩存储到一维数组A中，则数组A的长度最少为(C)。(A)100(B)40(C)55(D)808.设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数数为(A)3(B)4(C)5(D)19.根据一叉树的定义可知一叉树共有(B)种不向的形态。(A)4(B)5(C)6(D)7一、选择题1.组成数据的基本单位是(6.设栈S和队列Q的初始状态为空，元素B)。(B)p=p->next(D)p->next=pE1、E2、E3、的空间复杂度最大

2、。(C)堆排序(D)希尔排序10.设有以下四种排序方法，则(B(A)冒泡排序(B)快速排序11、以下说法正确的是(A)数据结构(一)(A)数据项(B)数据类型(C)数据兀素(D)数据变量2.设数据结构A=(D,R),其中D=1,2,3,4,R=r,r=<1,2>,<2人是(C)。(A)线性结构(B)树型结构(C)图型结构(D)集合3.数组的逻辑结构不同于卜列(D)的逻辑结构。(A)线性表(B)栈(C)队列(D)树4.二叉树中第i(i>1)层上的结点数最多有(C)个。(A)2i(B)2i(C)2i-1(D)2i-1C)。,3>,<3,4>,<4,1

3、>,则数据结构5.设指针变量p指向单链表结点(A)p->next=p->next->next(C)p=p->next->nextA,则删除结点A的后继结点B需要的操作为(A)。E4、E5和E6依次通过栈S,一个元素出栈后即进入队C)。A.连通图的生成树，是该连通图的一个极小连通子图。B.无向图的邻接矩阵是对称的，有向图的邻接矩阵一定是不对称的。C.任何一个有向图，其全部顶点可以排成一个拓扑序列。D.有回路的图不能进行拓扑排序。12、以下说法错误的是(D)A.一般在哈夫曼树中，权值越大的叶子离根结点越近B.哈夫曼树中没有度数为1的分支结点C.若初始森林中共有n

4、裸二叉树，最终求得的哈夫曼树共有2n-1个结点D.若初始森林中共有n裸二叉树，进行2n-1次合并后才能剩下一棵最终的哈夫曼树13、如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是(B)A.完全图B.连通图C.有回路D.一棵树14、将一棵有50个结点的完全二叉树按层编号，则对编号为25的结点x,该结点(B)A.无左、右孩子B.有左孩子，无右孩子C.有右孩子，无左孩子D.有左、右孩子15、深度为6的二叉树最多有(B)个结点A.64B.63C.32D.3116、一个有序顺表有255个对象，采用顺序搜索法查表，搜索长度为(A)。A128B、127C、126D、25517、在

5、有向图中每个顶点的度等于该顶点的(C)。A.入度B.出度C.入度与出度之和D.入度与出度之差18、具有n个顶点的有向无环图最多可包含(D)条有向边。A.n-1B.nC.n(n-1)/2D.n(n-1)19、用邻接表作为有向图G的存储结构。设有n个顶点、e条弧，则拓扑排序的时间复杂度为(B)A.O(n)B.O(n+e)C.O(e)D.O(n*e)20、一个有序顺表有255个对象，采用顺序搜索法查表，搜索长度为(A)。A128B、127C、126D、25521、在有向图中，所有顶点的入度之和是所有顶点出度之和的(B)倍。A.0.5B.1C.2D.422、以下说法错误的是(B)A.用相邻矩阵法存储一

6、个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关。B.邻接表法只能用于有向图的存储，而相邻矩阵法对于有向图和无向图的存储都适用。C.存储无向图的相邻矩阵是对称的，因此只要存储相邻矩阵的下(或上)三角部分就可以了D.用相邻矩阵A表示图，判定任意两个结点Vi和Vj之间是否有长度为m的路径相连，则只要检查A的第i行第j列的元素是否为0即可。23、在图的邻接表存储结构上执行深度优先搜索遍历类似于二叉树上的(A)A.先根遍历B.中根遍历C.后根遍历D按层次遍历24、在一个无向图中，所有顶点的度数之和等于所有边数的(B)倍。A.3B.2C,1D.1/225、在无

7、向图中，所有顶点的度数之和是所有边数的(C)倍。A.0.5B.1C.2D.426、设有6个结点的无向图，该图至少应有(B)条边能确保是一个连通图。A.5B.6C.7D.827、以下说法正确的是(D)A.连通分量是无向图中的极小连通子图。B.强连通分量是有向图中的极大强连通子图。C.在一个有向图的拓扑序列中，若顶点a在顶点b之前，则图中必有一条弧<a,b>。D.对有向图G,如果从任意顶点出发进行一次深度优先或广度优先搜索能访问到每个顶点，则该图一定是完全图。二、填空题1 .设顺序循环队列Q0:m-1的队头指针和队尾指针分别为F和R,其中队头指针F指向当前队头元素的前一个位置，队尾指针

8、R指向当前队尾元素所在的位置，则出队列的语句为F=;。2 .设线性表中有n个数据元素，则在顺序存储结构上实现顺序查找的平均时间复杂度为，在链式存储结构上实现顺序查找的平均时间复杂度为。3 .设一棵二叉树中有n个结点，则当用二叉链表作为其存储结构时，该二叉链表中共有个指针域，个空指针域。4 .设指针变量p指向单链表中结点A,指针变量s指向被插入的结点B,则在结点A的后面插入结点B的操作序列为。5 .设无向图G中有n个顶点和e条边，则其对应的邻接表中有个表头结点和个表结点。6 .设无向图G中有n个顶点e条边，所有顶点的度数之和为m则e和m有关系。7 .设一棵二叉树的前序遍历序列和中序遍历序列均为A

9、BC则该二叉树的后序遍历序列为。8 .设一棵完全二叉树中有21个结点，如果按照从上到下、从左到右的顺序从1开始顺序编号，则编号为8的双亲结点的编号是，编号为8的左孩子结点的编号是。9 .下列程序段的功能实现子串t在主串s中位置的算法，要求在下划线处填上正确语句。intindex(chars,chart)i=j=0;while(i<strlen(s)&&j<strlen(t)if(si=tj)i=i+l;j=j+l;elsei=;j=;if(j=strlen(t)return(i-strlen(t);elsereturn(-1);10 .设一个连通图G中有n个顶点e条

10、边，则其最小生成树上有条边。三、应用题1.设完全二叉树的顺序存储结构中存储数据ABCDE要求给出该二叉树的链式存储结构并给出该二叉树的前序、2.3.4.中序和后序遍历序列。设给定一个权值集合W=(3,5,7,9,11),要求根据给定的权值集合构造一棵哈夫曼树并计算哈夫曼树的带权路径长度WPL设一组初始记录关键字序列为(19,21,16,5,18,23),要求给出以19为基准的一趟快速排序结果以及第2趟直接选择排序后的结果。设一组初始记录关键字集合为(25,10,8,27,32,68),散列表的长度为7,散列5.函数H(k)=kmod7,要求用线性探测法作为解决冲突的方法设计哈希表。设无向图G(

11、所右图所示)，要求给出该图的深度优先和广度优先遍历的序列给相应的生成树二、填空题1.2.3.4.5.6.7.8.9.10.(F+1)%mO(n),O(n)2n,n+1s->next=p->next;s->next=sn,2em=2eCBA4,16i-j+1,0n-11.2.3.、应用题链式存储结构略，前序哈夫曼树略，WPL=78(18,5,16,19,21,23)4.,01线性探测：2.3.4.5.ABDEC中序DBEAC后序DEBCA16,19,18,23)1025322768数据结构(二)、选择题下面关于线性表的叙述错误的是(A)(B)(C)(D)线性表采用顺序存储必须占

12、用一片连续的存储空间线性表采用链式存储不必占用一片连续的存储空间线性表采用链式存储便于插入和删除操作的实现线性表采用顺序存储便于插入和删除操作的实现设哈夫曼树中的叶子结点总数为m若用二叉链表作为存储结构，则该哈夫曼树中总共有(A)2m-1(B)2m(C)2m+1(D)4m设顺序循环队列Q0:M-1的头指针和尾指针分别为F和R,头指针针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为(A)R-F(B)F-R设某棵二叉树的中序遍历序列为(A)BADC(B)BCDA设某完全无向图中有n个顶点,(A)n(n-1)/2(B)n(n-1)(C)(R-F+M)%MABCD前序遍历序列为(C)CDAB

13、则该完全无向图中有(C)n2(D)(F-R+M)()个空指针域。F总是指向队头元素的前一位置，尾指)°%MCABD则后序遍历该二叉树得到序列为(D)CBDA)条边。(D)n2-16 .设某棵二叉树中有2000个结点，则该二叉树的最小高度为()。(A)9(B)10(C)11(D)127 .设某有向图中有n个顶点，则该有向图对应的邻接表中有()个表头结点。(A)n-1(B)n(C)n+1(D)2n-18 .设一组初始记录关键字序列(5,2,6,3,8),以第一个记录关键字5为基准进行一趟快速排序的结果为()。(A)2,3,5,8,6(B)3,2,5,8,6(C)3,2,5,6,8(D)2

14、,3,6,5,8二、填空题1 .为了能有效地应用HASH查找技术，必须解决的两个问题是和2 .下面程序段的功能实现数据x进栈，要求在下划线处填上正确的语句。typedefstructints100;inttop;sqstack;voidpush(sqstack&stack,intx)if(stack.top=m-1)printf("overflow");else;3 .中序遍历二叉排序树所得到的序列是序列(填有序或无序)。4 .快速排序的最坏时间复杂度为,平均时间复杂度为。5 .设某棵二叉树中度数为0的结点数为N0,度数为1的结点数为N,则该二叉树中度数为2的结点数

15、为;若采用二叉链表作为该二叉树的存储结构，则该二叉树中共有个空指针域。6 .设某无向图中顶点数和边数分别为n和e,所有顶点的度数之和为d,则e=。7 .设一组初始记录关键字序列为(55,63,44,38,75,80,31,56),则利用筛选法建立的初始堆为Vi-3-2-4一.一.vo-1-38.设某无向图G的邻接表为2,则从顶点Vi开始的深度优先遍历序列为;广度V3-1-54。、2v4-1-53优先遍历序列为。三、应用题1 .设一组初始记录关键字序列为(45,80,47,40,20,78),则分别给出第4趟简单选择排序和第4趟直接插入排序后的结果。2 .设指针变量p指向双向链表中结点A,指针变

16、量q指向被插入结点B,要求给出在结点A的后面插入结点B的操作序列(设双向链表中结点的两个指针域分别为llink和rlink)。3 .设一组有序的记录关键字序列为(13,18,24,35,47,50,62,83,90),查找方法用二分查找，要求计算出查找关键字62时的比较次数并计算出查找成功时的平均查找长度。4 .设一棵树T中边的集合为(A,B),(A,C),(A,D),(B,E),(C,F),(C,G),要求用孩子兄弟表示法(二叉链表)表示出该树的存储结构并将该树转化成对应的二叉树。5 .设有无向图G(如右图所示)，要求给出用普里姆算法构造最小生成树所走过的边的集合。6 .设有一组初始记录关键

17、字为(45,80,48,40,22,78),要求构造一棵二叉排序树并给出构造过程。7、给出如图所示的无向图G的邻接矩阵和邻接表两种存储结构。8、简单选择排序、快速排序和堆排序是不稳定的排序方法，试举例说明。9、给出下图邻接矩阵和邻接表两种存储结构；写出图的拓扑序列。(二)参考答案一、选择题1 .D2,B3.C4.A5.A6.C7.B8.C二、填空题2 .构造一个好的HAS阔数，确定解决冲突的方法3 .stack.top+,stack.sstack.top=x4 .有序2、4. O(n),O(nlog2n)5. N0-1,2N0+Ni6. d/27. (31,38,54,56,75,80,55,

18、63)8. (1,3,4,2),(1,3,2,4)三、应用题1. (20,40,45,47,80,78),(40,45,47,80,20,78)2. q->llink=p;q->rlink=p->rlink;p->rlink->llink=q;p->rlink=q;3. 2,ASL=91*1+2*2+3*4+4*2)=25/94. 树的链式存储结构略，二叉树略5. E=(1,3),(1,2),(3,5),(5,6),(6,4)6. 略8、简单选择排序、快速排序和堆排序是不稳定的排序方法，试举例说明。【解答】(2)简单选择排序275275*512061)i=1

19、061275*512275)i=2061275*512275)i:=3061275*275512)快速排序512275275*)275*275512)(4)堆排序275275*061170)已经是最大堆，交换275与170170275*061275)对前3个调整275*170061275)前3个最大堆，交换275*与061061170275*275)对前2个调整170061275*275)前2个最大堆，交换170与061061170275*275)数据结构(三)一、选择题1 .设某无向图有n个顶点，则该无向图的邻接表中有()个表头结点。(A)2n(B)n(C)n/2(D)n(n-1)2 .设无

20、向图G中有n个顶点，则该无向图的最小生成树上有()条边。(A)n(B)n-13.设一组初始记录关键字序列为排序结果是()。(C)2n(D)2n-1(A) 40,42,60,55,80,85(C)424055608085(B) 424555608580(D)424060855580(60,80,55,40,42,85),则以第一个关键字45为基准而得到的一趟快速4 .()二叉排序树可以得到一个从小到大的有序序列。(A)先序遍历(B)中序遍历(C)后序遍历(D)层次遍历5 .设按照从上到下、从左到右的顺序从1开始对完全二叉树进行顺序编号，则编号为i结点的左孩子结点的编号为()。(A)2i+16.程

21、序段s=i=0;(A)O(n)(B)2idoi=i+1；s=s+i(B) O(nlog2n)(C)i/2;while(i<=n)(C) O(n2)(D)2i-1;的时间复杂度为(D) O(n3/2)7.设带有头结点的单向循环链表的头指针变量为head,则其判空条件是()。(A)head=0(B)head->next=0(C)head->next=head(D)head!=08 .设某棵二叉树的高度为10,则该二叉树上叶子结点最多有()。(A)20(B)256(C)512(D)10249 .设一组初始记录关键字序列为(13,18,24,35,47,50,62,83,90,字90

22、需要比较的关键字个数为()。115,134),则利用二分法查找关键(A)1(B)2(C)3(D)410.设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为()。(A) top=top+1;(C)top->next=top;(B) top=top-1;(D)top=top->next;二、判断题1、数据的最小单位是数据项。,.(V)2、多重表文件中主索引为非稠密索引，次索引为稠密索引。，,.(V)3、通常数据结构在计算机中有四种不同的表示方法分为顺序存储结构、链式存储结构、索引存储、文件存储。，,，.,.(X)4、算法具有输入、输出、可行性、稳定性、有穷性五个特性。.(

23、X)5、数据的基本单位是数据项。,.(X)6、算法的复杂度分为时间复杂度和效率复杂度。,.(X)7、性质相同的数据元素的集合成为数据对象。.(V)8、所有结点按1对1的邻接关系构成的整体就是集合结构。,.(X)9、散列文件不能顺序存取、只能按关键字随机存取。，,，.(V)10、数据的基本单位是数据元素。,.(V)11 .不论是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情况。(，)12 .当向二叉排序树中插入一个结点，则该结点一定成为叶子结点。(，)13 .由树转化成二叉树，该二叉树的右子树不一定为空。（x）14 .线性表中的所有元素都有一个前驱元素和后继元素。（X）15 .带权

24、无向图的最小生成树是唯一的。（X）16 .具有12个结点的完全二叉树有5个度为2的结点。（）17 .关键路径是事件结点网络中的从源点到汇点的最短路径。（）18 .由树转化成二叉树，该二叉树的右子树不一定为空。（）19 .堆排序是不稳定的排序方法。（V）20 .查找表是由同一类型的数据元素（或记录）构成的集合（，）三、填空题1 .设指针变量p指向双向链表中的结点A,指针变量s指向被插入的结点X,则在结点A的后面插入结点X的操作序列为=p;s->right=p->right;=s;p->right->left=s;（设结点中的两个指针域分别为left和right）。2 .设

25、完全有向图中有n个顶点，则该完全有向图中共有条有向条；设完全无向图中有n个顶点，则该完全无向图中共有条无向边。3 .设关键字序列为（Kl,%,K）,则用筛选法建初始堆必须从第个元素开始进行筛选。4 .解决散列表冲突的两种方法是和。5 .设一棵三叉树中有50个度数为0的结点，21个度数为2的结点，则该二叉树中度数为3的结点数有个。6 .高度为h的完全二叉树中最少有个结点，最多有个结点。7 .设有一组初始关键字序列为（24,35,12,27,18,26）,则第3趟直接插入排序结束后的结果的是8 .设有一组初始关键字序列为（24,35,12,27,18,26）,则第3趟简单选择排序结束后的结果的是9

26、 .设一棵二叉树的前序序列为ABC则有种不同的二叉树可以得到这种序列。10 .下面程序段的功能是实现一趟快速排序，请在下划线处填上正确的语句。structrecordintkey;datatypeothers;voidquickpass(structrecordr,ints,intt,int&i)intj=t;structrecordx=rs;i=s;while(i<j)while(i<j&&rj.key>x.key)j=j-1;if(i<j)ri=rj;i=i+1;while()i=i+1;if(i<j)rj=ri;j=j-1;；数据结构

27、（三）一、选择题1.B2.B3.C4B5B6.A7.C8.C9B10.D三、填空题1. s->left=p,p->right2. n(n-1),n(n-1)/23. n/24. 开放定址法，链地址法5. 146. 2h-1,2h-17. (12,24,35,27,18,26)8. (12,18,24,27,35,26)9. 510. i<j&&ri.key<x.key,ri=x数据结构(四)一、选择题1 .设输入序列是1、2、3、，、n,经过栈的作用后输出序列的第一个元素是n,则输出序列中第i个输出元素是(c)。(A)n-i(B)n-1-i(C)n+1-

28、i(D)不能确定2 .为查找某一特定单词在文本中出现的位置，可应用的串运算是()A.插入B.删除C.串联接D.子串定位3 .设有序表中有1000个元素，则用二分查找查找元素X最多需要比较()次。(A)25(B)10(C)7(D)14 .对于只在表的首、尾两端进行插入操作白线性表，宜采用的存储结构为()A.顺序表B.用头指针表示的单循环链表C.用尾指针表示的单循环链表D.单链表5 .设某完全无向图中有n个顶点，则该完全无向图中有()条边。(A)n(n-1)/2(B)n(n-1)(C)n2(D)n2-16 .设某棵二叉树中有2000个结点，则该二叉树的最小高度为()。(A)9(B)10(C)11(

29、D)127 .在数据结构中，从逻辑上可以把数据结构分为()A.动态结构和静态结构B.紧凑结构和非紧凑结构C.内部结构和外部结构D.线性结构和非线性结构8 .已知图的邻接表如下所示，根据算法，则从顶点Vo出发按广度优先遍历的结点序列是()A.0321B.0123C.0132D.03129 .若进栈序列为a,b,c,d,e,则栈的不可能的输出序列是()A.edcbaB.dceabC.decbaD.abcde10 .把一棵树转换为二叉树后，这棵二叉树的形态是()。A.唯一的B.有多种C.有多种，但根结点都没有左孩子D.有多种，但根结点都没有右孩子11 .为查找某一特定单词在文本中出现的位置，可应用的

30、串运算是()A.插入B.删除C.串联接D.子串定位12 .ALV树是一种平衡的二叉树，树中任一结点的()A.左、右子树的高度均相同B.左、右子树高度差的绝对值不超过1C.左子树的高度均大于右子树的高度D.左子树的高度均小于右子树的高度13 .对于只在表的首、尾两端进行插入操作白线性表，宜采用的存储结构为()A.顺序表B.用头指针表示的单循环链表C.用尾指针表示的单循环链表D.单链表14 .二叉树是非线性数据结构，所以()。A.它不能用顺序存储结构存储；B.它不能用链式存储结构存储；C.顺序存储结构和链式存储结构都能存储；D.顺序存储结构和链式存储结构都不能使用15 .用邻接表表示图进行广度优先

31、遍历时，通常是采用()来实现算法的。A.栈B.队列C.树D.图16 .数据的最小单位是()。(A)数据项(B)数据类型(C)数据元素(D)数据变量17 .设某棵二叉树中有2000个结点，则该二叉树的最小高度为()。(A)9(B)10(C)11(D)1218 .函数substr("DATASTRUCTURE5,9)的返回值为()。(A)“STRUCTURE(B)“DATA(C)“astructUr(D)“datastructURe19 .设某完全无向图中有n个顶点，则该完全无向图中有()条边。(A)n(n-1)/2(B)n(n-1)(C)n2(D)n2-120 .深度为k的完全二叉树中

32、最少有()个结点。(A)2k-1-1(B)2k-1(C)2k-1+1(D)2k-121 .设连通图G中的边集E=(a,b),(a,e),(a,c),(b,e),(e,d),(d,f),(f,c),则从顶点a出发可以得到一种深度优先遍历的顶点序列为()。(A)abedfc(B)acfebd(C)aebdfc(D)aedfcb22 .下面关于线性表的叙述错误的是()。(A)线性表采用顺序存储必须占用一片连续的存储空间(B)线性表采用链式存储不必占用一片连续的存储空间(C)线性表采用链式存储便于插入和删除操作的实现(D)线性表采用顺序存储便于插入和删除操作的实现23 .设哈夫曼树中的叶子结点总数为m

33、,若用二叉链表作为存储结构，则该哈夫曼树中总共有()个空指针域。(A)2m-1(B)2m(C)2m+1(D)4m24 .设顺序循环队列Q0:M-1的头指针和尾指针分别为F和R,头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为()。(A)R-F(B)F-R(C)(R-F+M)%M(D)(F-R+M)%M25 .设某棵二叉树的中序遍历序列为ABCD前序遍历序列为CABD则后序遍历该二叉树得到序列为()。(A)BADC(B)BCDA(C)CDAB(D)CBDA二、填空题1 .1.for(i=1,t=1,s=0;i<=n;i+)t=t*i;s=s

34、+t;的时间复杂度为2 .下面程序段的功能是实现冒泡排序算法，请在下划线处填上正确的语句。voidbubble(intrn)for(i=1;i<=n-1;i+)for(exchange=0,j=0;j<j+)if(rj>rj+1)temp=rj+1;rj=temp;exchange=1;if(exchange=0)return;3 .下面程序段的功能是实现二分查找算法，请在下划线处填上正确的语句。structrecordintkey;intothers;intbisearch(structrecordr,intk)intlow=0,mid,high=n-1;while(low

35、<=high)J.if(rmid.key=k)return(mid+1);elseif()high=mid-1;elselow=mid+1;)return(0);)3 .根据二叉树的定义可知二叉树共有种不同的形态。4 .快速排序的最坏时间复杂度为,平均时间复杂度为。5 .设某棵二叉树中度数为0的结点数为NQ度数为1的结点数为N1,则该二叉树中度数为2的结点数为;若采用二叉链表作为该二叉树的存储结构，则该二叉树中共有个空指针域。6 .设某无向图中顶点数和边数分别为n和e,所有顶点的度数之和为d,则e=。7 .设一棵完全二叉树中有21个结点，如果按照从上到下、从左到右的顺序从1开始顺序编号，则编号为8的双亲结点的编号是,编号为8的左孩子结点的编号是。8 .设一个连通图G中有n个顶点e条边，则其最小生成树上有条边。9 .设一组初始记录关键字序列为(55,63,44,38,75,80,31,56),则利用筛选法建立的初始堆为。10 .设F和R分别表示顺序循环队列的头指针和尾指针，则判断该循环