数据结构试题汇编带答案

1、数据结构习题汇编一、单项选择题1 .在数据结构中，从逻辑上可以把数据结构分成（）。A.动态结构和静态结构B.紧凑结构和非紧凑结构C.线性结构和非线性结构D.内部结构和外部结构）。B.数据结构D.数据元素之间的关系2 .数据结构在计算机内存中的表示是指（A.数据的存储结构C.数据的逻辑结构3 .在数据结构中，与所使用的计算机无关的是数据的（）结构。A.逻辑B.存储C.逻辑和存储D.物理4 .计算机算法指的是（）,它必须具备输入、输出和（）等5个特性。A.计算方法B.排序方法C.解决问题的有限运算序列D.倜度方法A.可行性、可移植性和可扩充性B.可行性、确定性和后穷性C.确定性、有穷性和稳定性D.

2、易读性、稳定性和安全性5 .在一个长度为n的顺序表中向第i个元素（1wiwn+1）位置插入一个新元素时，需要从后向前依次后移（）个元素。A.n-iB.n-i+1C.n-i-1D.i6 .在一个长度为n的顺序表中删除第i个元素（1Wiwn）时，需要从前向后依次前移（）个元素。A.n-iB.n-i+1C.n-i-1D.i7 .在一个长度为n的顺序表的表尾插入一个新元素的渐进时间复杂度为（）。A.O（n）B.O（1）C.O（n2）D.O（log2n）8 .在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为（）。A.O（n）B.O（n/2）C.O（1）D.O（n2）9 .不带头结点的单链

3、表first为空的判定条件是：（）A.first=NULL;B.first->next=NULL;C.first->next=first;D.first!=NULL;10 .带头结点的单链表first为空的判定条件是：（）A.first=NULL;B.first->next=NULL;C.first->next=first;D.first!=NULL;11 .设单链表中结点的结构为（data,next）。已知指针p所指结点不是尾结点，若在*p之后插入结点*s,A.s->next=p;p->next=s;C.s->next=p->next;p=s;

4、则应执行下列哪一个操作？（）B. p->next=s;s->next=p;D.s->next=p->next;p->next=s;12.设单链表中结点的结构为（data,next）。若想摘除结点*p（*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.非空的循环单链表firstA.p

5、->next=NULL;C.p->next=first;的尾结点（由p所指向）满足：（）B.p=NULL;D. p=first;14 .若让元素1,2,3依次进栈，则出栈次序不可能出现（）种情况。A.3,2,1B.2,1,3C.3,1,2D.1,3,215 .当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为（）。A.n-2B.n-1C.nD.n+116 .从一个顺序存储的循环队列中删除一个元素时，需要（）。A.队头指针加一B.队头指针减一C.取出队头指针所指的元素D.取出队尾指针所指的元素17 .假定一个顺序存储的循环队列的队头和队尾指针分别为front和rear，则判断

6、队空的条件为（）。A.front+1=rearB.rear+1=frontC.front=0D.front=rear18 .树中所有结点的度等于所有结点数加（）。A.0B.1C.-1D.219 .在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加（）。A.2B.1C.0D.-120 .在一棵具有n个结点的二叉树中，所有结点的空子树个数等于（）。A.nB.n-1C.n+1D.2*n21 .在一棵具有n个结点的二叉树的第i层上（假定根结点为第1层，i大于等于1而小于等于树的高度）：最多具有（）个结点。A.2iB.2i+1C.2i-1D.2n22 .在一棵高度为h（假定根结点的层号为1）的完全二

7、叉树中，所含结点个数不小于（）。A.2h-1B.2h+1C.2h-1D.2h。假定空树的高度为0。D.8）。假定树根结点的编号为1。D.M/2-123 .在一棵具有35个结点的完全二叉树中，该树的高度为（A.5B.6C.724 .在一棵具有n个结点的完全二叉树中，分支结点的最大编号为（A.H（n-1）/2B.M/2C.n/2)。假定根结点25 .在一棵完全二叉树中，若编号为i的结点存在左孩子，则左子女结点的编号为(的编号为1A.2iB.2i-1C.2i+1D.2i+226.27.28.29.30.31.32.33.34.35.36.37.在一棵完全二叉树中，假定根结点的编号为1,则对于编号为i

8、(i>1)的结点，其双亲结点的编号为()。A.|l(i+1)/2B.|l(i-1)/2C.|li/2D.|li/2-1设无向图的顶点个数为n,则该图最多后()条边。A.n-1B.n(n-1)/2C.n(n+1)/2D.n(n-1)n个顶点的连通图至少有()条边。A.n-1B.nC.n+1D.0在一个无向图中，所有顶点的度数之和等于所有边数的()倍。A.3B.2C.1D.1/2图的深度优先搜索类似于树的()次序遍历。A.先根B.中根C.后根D.层次图的广度优先搜索类似于树的()次序遍历。A.先根B.中根C.后根D.层次n(n>1)个顶点的强连通图中至少含有()条有向边。A.n-1B.

9、nC.n(n-1)/2D.n(n-1)具有n个顶点的有向尢坏图最多可包含()条有向边。A.n-1B.nC.n(n-1)/2D.n(n-1)一个有n个顶点和n条边的无向图一te是()。A.连通的B.不连通的C.无环的D.后环的在n个顶点的有向无环图的邻接矩阵中至少有()个零兀素。A.nB.n(n-1)/2C.n(n+1)/2D.n(n-1)为了实现图的广度优先遍历，BFS算法使用的一个辅助数据结构是()。A.栈B.队列C.二叉树D.树若搜索每一个元素的概率相等，则在长度为n的顺序表上搜索到表中任一元素的平均搜索长度为()。A.nB.n+1C.(n-1)/2D.(n+1)/238.对长度为10的顺

10、序表进行搜索(从表头开始搜索)，若搜索前面5个元素的概率相同，均为1/8,搜索后面5个元素的概率相同，均为3/40,则搜索到表中任一元素的平均搜索长度为()。A.5.5B.5C.39/8D.19/439 .对于长度为n的有序顺序表，若采用折半搜索，则对所有元素的搜索长度中最大的为()的值的向上取整。A.log2(n+1)B.log2nC.n/2D.(n+1)/240 .对于长度为n的有序顺序表，若采用折半搜索，则对所有元素的搜索长度中最大的为()的值的向下取整加一。A.log2(n+1)B.log2nC.n/2D.(n+1)/241 .对于长度为9的有序顺序表，若采用折半搜索，在等概率情况下搜

11、索成功的平均搜索长度为()的值除以9。A.20B.18C.25D.2242 .对于长度为18的有序顺序表，若采用折半搜索，则搜索第15个元素的搜索长度为()。A.3B.4C.5D.643 .对具有n个元素的有序顺序表进行折半搜索，则搜索任一元素的时间复杂度为()。A.O(n)B.O(n2)C.O(1)D.O(log2n)44 .对5个不同的数据元素进行直接插入排序，最多需要进行()次比较？A.8B.10C.15D.2545 .如果输入序列是已经排好顺序的，则下列算法中()算法最快结束？A.起泡排序B.直接插入排序C.直接选择排序D.快速排序46 .如果输入序列是已经排好顺序的，则下列算法中()

12、算法最慢结束？A.起泡排序B.直接插入排序C.直接选择排序D.快速排序二、填空题1 .算法的五个重要特性是有穷性、确定性、可行性、输入和输出。2 .设单链表中结点的结构为(data,next)。若想摘除结点*p本身，则应执行操作：q=p->next;p->data=q->data;p->next=q->nextfree(q),3 .设循环队列Q的队头和队尾指针分别为front和rear，队列的最大容量为MaxSize，且规定判断队空的条件为Q.front=Q.rear,则判断队满的条件为(Q.rear+1)%MaxSize=Q.front,而计算队列长度的表达式为

13、(Q.rear-Q.front+MaxSize)%MaxSize。4 .设有一个顺序栈S,元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素的出栈顺序为s2,s3,s4,s6,s5,s1,则顺序栈的容量至少应为_3。5 .如果进栈序列是1,2,3,4,5,6,7,8。则可能的出栈序列有1430种。6 .用简单的模式匹配算法在主串"aaaaaab"中检索子串"aab”,则总的比较次数为15。7 .用简单的模式匹配算法在主串"data_structure"中检索子串”string”，总的比较次数为12。8 ,假定一棵三叉科(即度为3的树)

14、的结点个数为50,则它的最小高度为5。假定根结点的高度为1。9 .在一棵高度为3的四叉树中，最多含有21结点。10 .在一棵三叉树中，度为3的结点数有2个，度为2的结点数有1个，度为1的结点数为2个，那么度为0的结点数有6个。11 .一棵高度为5的完全二叉树中，最多包含有31个结点。假定根结点的高度为1。12 .在一棵二叉树中，假定度为2的结点个数为5个，度为1的结点个数为6个，则叶结点数为6个。13 .假定一棵二叉树的结点个数为18,则它的最小高度为5。假定根结点的高度为1。14 .按照二叉树的定义，具有5个结点的二叉树有42种形态。15 .以顺序搜索方法从长度为n的顺序表或单链表中搜索一个

15、元素时，其时间复杂度为O(n)。16 .对长度为n的搜索表进行搜索时，假定搜索第i个元素的概率为pi,搜索长度(即在搜索过程中依次同有关元素比较的总次数)为ci,则在搜索成功情况下的平均搜索长度的计算公式为ASL="rg17 .假定一个顺序表的长度为40,并假定搜索每个元素的概率都相同，则在搜索成功情况下的平均搜索长度为20.5。18 .以折半搜索方法从长度为n的有序表中搜索一个元素时，时间复杂度为O(log2n)。19 .从有序表(12,18,30,43,56,78,82,95)中折半搜索元素56时，其搜索长度为3。20 .假定对长度n=50的有序表进行折半搜索，则对应的判定树中最

16、后一层的结点数为19个。21 .直接插入排序在最好情况下的比较次数为,最坏情况下为。(正序最好C=n-1,逆序最坏C=n*(n-1)/2)22 .直接插入排序在最好情况下的移动次数为,最坏情况下为。(最好M=0,最坏M=(n+4)*(n-1)/2)23 .简单选择法排序时比较数据的次数为。(任何情况下C=n*(n-1)/2)24 .简单选择法排序在最好情况下的移动次数为,最坏情况下为。(最好正序M=0,最坏(非逆序，如6,1,2,3,4,5)M=3*(n-1)25 .起泡排序在最好情况下的比较次数为,最坏情况下为(最好正序C=n-1,最坏逆序C=n*(n-1)/2)26 .起泡排序在最好情况下

17、的移动次数为,最坏情况下为(最好正序M=0,最坏(逆序)M=3*n*(n-1)/2)27 .在直接选择排序中，排序码比较次数的时间复杂度为O(n2)。28 .在直接选择排序中，数据对象移动次数的时间复杂度为0(n)。29 .快速排序在平均情况下的时间复杂度为0(nlog即)。30 .快速排序在最坏情况下的时间复杂度为O(n2)。三、简答题1 .下面程序段的时间复杂度是O(n*m)。for(i=0;i<n;i+)for(j=0;j<m;j+)Aij=0；2 .下面程序段的时间复杂度是O(n0.5)。i=s=0;while(s<n)i+;s+=i;3 .下面程序段的时间复杂度是O

18、(nA2)qs=0;for(i=0;i<n;i+)for(j=0;j<n;j+)s+=Bij;sum=s;4 .下面程序段的时间复杂度是O(log3n)oi=1;while(i<=n)i=i*3;5 .写出下列程序段的输出结果:514263。voidmain()SqStackS;SqQueueQ;inti,j,n=6,e;for(i=1;i<=n;+i)Push(&S,i);for(i=1;i<=n;+i)Pop(&S,&e);EnQueue(&Q,e);DeQueue(&Q,&e);EnQueue(&Q,e

19、);for(i=1;i<=n;+i)DeQueue(&Q,&e);Push(&S,e);for(i=1;i<=n;+i)Pop(&S,&e);printf("%d",e);6,已知一棵二叉树的前序和中序序列，画图并求该二叉树的后序序列。前序序列：A,B,C,D,E,F,G,H,I,J中序序列：C,B,A,E,F,D,I,H,J,G后序序列：7,已知一棵二叉树的中序和后序序列如下，画图并求该二叉树的前序序列。中序序列：c,b,d,e,a,g,i,h,j,f后序序列：c,e,d,b,i,j,h,g,f,a前序序列：,试以它们为

20、叶结点生成一棵赫夫曼树,8.有7个带权结点，其权值分别为3,7,8,2,6,10,14求出该树的带权路径长度：9,设连通图G如图所示。试给出对它执行从顶点广度优先遍历：012345678深度优先遍历：013256784V0开始的广度优先遍历和深度优先遍历的结果。10,设有一个连通网络如图所示。试采用集合S和选择边Edge的顺序）prim算法从顶点0开始构造最小生成树。（写出加入生成树顶点顶点集合边（顶点，顶点，权值）0(0,1,9)011(1,3,5)013(1,2,7)0132(2,4,6)01324(2，5,7)01324511 .设带权有向图如图所示。试采用Dijkstra算法求从顶点0

21、到其他各顶点的最短路径和最短路径长度。顶点号路径长度路径1401370328012410012412 .试对下图所示的AOE网络(1) 这个工程最早可能在什么时间结束。(2)确定哪些活动是关键活动。画出由所有关键活动构成的图，指出哪些活动加速可使整个工程提前完成。拓扑序列132456每个顶点的最早发生时间、最迟发生时间：1(0,0),3(15,15),2(19,19),4(29,37),5(38,38),6(43,43)工期：43天每个活动的最早开始时间、最迟开始时间：1-2(0,17),1-3(0,0),3-2(15,15),3-5(15,27),2-5(19,19),2-4(19,27)5-6(38,38),4-6(29,37)13 .一个一维数组a10中存储着一个有序表，该有序表为：(15,26,34,39,45,56,58,63,74,76),画出折半搜索所对应的判定树，并求出在等概率情况下搜索成功的平均搜索长度。平均搜索长度：2.9,对其进行一趟快速排序,14 .给定一组数据对象的排序码为46,79,56,38,40,84)结果为40,38,46,56,79,84。四、算法设计题1 .设有一个顺序表(e0,e1,，en-2,en-1)。请编写一个函数将这个顺序表原地逆置，即顺序表的内容置换为(en-1,en-2,，e1,e0)。voidReverse(Sq