《数据结构》试题汇编(带答案)

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

2、.在一个长度为n的顺序表中向第i个元素1wiwn+1位置插入一个新元素时，需要从后向前依次后移个元素。A.n-iB.n-i+1C.n-i-1D.i6 .在一个长度为n的顺序表中删除第i个元素iwiwn时，需要从前向后依次前移个元素。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 .不带头结点的单链表first为空的判定条件是：A.first=NU

3、LL;C.first-next=first;10 .带头结点的单链表first为空的判定条件/A.first=NULL;C.first-next=first;11 .设单链表中结点的结构为data,next,*s,则应执行以下哪一个操作？A.s-next=p;p-next=s;C.s-next=p-next;p=s;B.first-next=NULL;D.first!=NULL;1:B.first-next=NULL;D.first!=NULL;o已知指针p所指结点不是尾结点，假设在*p之后插入结点B.p-next=s;s-next=p;D.s-next=p-next;p-next=s;学习文

4、档仅供参考12.设单链表中结点的结构为data,next。假设想摘除结点*p（*p既不是第一个也不是最后一个结点）的直接后继，则应执行以下哪一个操作？A.p-next=p-next-next;C.p-next=p-next;B.p=p-next;p-next=p-next-next;D.p=p-next-next;13.非空的循环单链表firstA.p-next=NULL;C.p-next=first;的尾结点由p所指向满足：B.p=NULL;D.p=first;14.假设让元素1,2,3依次进栈，则出栈次序不可能出现种情况。15.16.17.18.19.20.21.22.23.24.A.3,

5、2,1B.2,1,3C.3,1,2D.1,3,2当利用大小为A.n-2n的数组顺序存储一个队列时，该队列的最大长度为B.n-1C.nD.n+1从一个顺序存储的循环队列中删除一个元素时,A.队头指针加一IC.取出队头指针所指的元素IB.队头指针减一D.取出队尾指针所指的元素假定一个顺序存储的循环队列的队头和队尾指针分别为A.front+1=rearC.front=0树中所有结点的度等于所有结点数加A.0B.1frontB.rear+1=frontD.front=rearC.-1在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加A.2B.1C.0在一棵具有A.n在一棵具有最多具有A.2i在一棵

6、高度为A.2h-1个结点的二叉树中，所有结点的空子树个数等于B.n-1C.n+1和rear,则判断队空的条件为D.2D.-1D.2*n个结点的二叉树的第i个结点。B.2i+1层上假定根结点为第C.2i-1层，i大于等于1而小于等于树的高度D.2n假定根结点的层号为B.2h+11的完全二叉树中，所含结点个数不小于C.2h-1D.2h在一棵具有35个结点的完全二叉树中，该树的高度为A.5B.6C.7。假定空树的高度为0。D.8在一棵具有n个结点的完全二叉树中，分支结点的最大编号为。假定树根结点的编号为A.(n-1)/2B.n/2C.n/2D.n/2-125.在一棵完全二叉树中，假设编号为i的结点存

7、在左孩子，则左子女结点的编号为点的编号为1。假定根结26.27.28.29.30.31.32.33.34.35.36.37.38.A.2iB.2i-1C.2i+1D.2i+2在一棵完全二叉树中,假定根结点的编号为1,则对于编号为i1的结点，其双亲结点的编号为A.(i+1)/2B.(i-1)/2C.i/2D.i/2-1设无向图的顶点个数为A.n-1n,则该图最多有B.n(n-1)/2n个顶点的连通图至少有条边。条边。C.n(n+1)/2D.n(n-1)A.n-1B.nC.n+1D.0在一个无向图中，所有顶点的度数之和等于所有边数的A.3B.2C.1图的深度优先搜索类似于树的A.先根B.中根次序遍

8、历。C.后根图的广度优先搜索类似于树的A.先根B.中根次序遍历。C.后根n(n1)个顶点的强连通图中至少含有A.n-1B.n具有n个顶点的有向无环图最多可包含A.n-1B.n一个有n个顶点和n条边的无向图一定是A.连通的B.不连通的在n个顶点的有向无环图的邻接矩阵中至少有A.nB.n(n-1)/2倍。D.1/2D.层次D.层次条有向边。C.n(n-1)/2条有向边。C.n(n-1)/2C.无环的个零元素。C.n(n+1)/2为了实现图的广度优先遍历，BFS算法使用的一个辅助数据结构是A.栈B.队列C.二叉树假设搜索每一个元素的概率相等，则在长度为A.nB.n+1D.n(n-1)D.n(n-1)

9、D.有环的D.n(n-1)D.树n的顺序表上搜索到表中任一元素的平均搜索长度为C.(n-1)/2D.(n+1)/2对长度为10的顺序表进行搜索(从表头开始搜索)，假设搜索前面5个元素的概率相同，均为索后面5个元素的概率相同，均为3/40,则搜索到表中任一元素的平均搜索长度为A.5.5B.5C.39/8D.19/4的值A.log 2(n+1) B.log2nC. n/2D.(n+1)/239 .对于长度为n的有序顺序表，假设采用折半搜索，则对所有元素的搜索长度中最大的为的向上取整。的值A. log 2(n+1) B.log 2nC. n/2D.(n+1)/240 .对于长度为n的有序顺序表，假设

10、采用折半搜索，则对所有元素的搜索长度中最大的为的向下取整加一。41 .对于长度为9的有序顺序表，假设采用折半搜索，在等概率情况下搜索成功的平均搜索长度为的值除以9。A.20B.18C.25D.2215个元素的搜索长度为D. 642 .对于长度为18的有序顺序表，假设采用折半搜索，则搜索第A.3B.4C.543 .对具有n个元素的有序顺序表进行折半搜索，则搜索任一元素的时间复杂度为A.O(n)B.O(n2)C.O(1)D.O(log2n)44 .对5个不同的数据元素进行直接插入排序，最多需要进行次比较？A.8B.10C.15D.2545 .如果输入序列是已经排好顺序的，则以下算法中算法最快结束？

11、A.起泡排序B.直接插入排序C.直接选择排序D.快速排序算法最慢结束?46 .如果输入序列是已经排好顺序的，则以下算法中A.起泡排序B.直接插入排序C.直接选择排序D.快速排序二、填空题1 .算法的五个重要特性是有穷性、确定性、可行I生、输入和输出。2 .设单链表中结点的结构为data,next。假设想摘除结点*p本身，则应执行操作:q=p-next;p-data=q-data;_p-next=q-next一free(q);3 .设循环队列Q的队头和队尾指针分别为front和rear，队列的最大容量为MaxSize，且规定判断队空的条件为Q.front=Q.rear,则判断队满的条件为(Q.r

12、ear+1)%MaxSize=Q.front,而计算队列长度的表达式为(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”,则总的比较次数为157 .用简单的模式匹配算法在主串data_structure中检索子串”string”，总的比较次数为12。8 .假定一棵三叉即度为3的树

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

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

15、个。21 .直接插入排序在最好情况下的比较次数为,最坏情况下为。正序最好C=n-1,逆序最坏C=n*(n-1)/222 .直接插入排序在最好情况下的移动次数为,最坏情况下为。最好M=0,最坏M=(n+4)*(n-1)/223 .简单项选择择法排序时比较数据的次数为。任何情况下C=n*(n-1)/224 .简单项选择择法排序在最好情况下的移动次数为,最坏情况下为。最好正序M=0,最坏非逆序，如6,1,2,3,4,5M=3*(n-1)25 .起泡排序在最好情况下的比较次数为,最坏情况下为最好正序C=n-1,最坏逆序C=n*(n-1)/2526 .起泡排序在最好情况下的移动次数为,最坏情况下为最好正

16、序M=0,最坏逆序M=3*n*(n-1)/227 .在直接选择排序中，排序码比较次数的时间复杂度为O(nA2)。28 .在直接选择排序中，数据对象移动次数的时间复杂度为0(n)。29 .快速排序在平均情况下的时间复杂度为0(nlog2n)。30 .快速排序在最坏情况下的时间复杂度为0(n2)。三、简答题1 .下面程序段的时间复杂度是0(n*m)。for(i=0;in;i+)for(j=0;jm;j+)Aij=0；2 .下面程序段的时间复杂度是0-人0.5)。i=s=0;while(sn)i+;s+=i;3 .下面程序段的时间复杂度是0(nA2)qs=0;for(i=0;in;i+)for(j=

17、0;jn;j+)s+=Bij；sum=s;4 .下面程序段的时间复杂度是O(log3n)。i=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);for(i=1;i=n;+i)DeQueue(&Q,&e);Push(&S,e);for(i=1;ilength-1;ElemTypet;for(;i勺+i,-j)t=L-elemi;L-elemi=L-elemj;L-elemj=t;2 .试编写一个函数，用以删除顺序表L中所有值为x的元素要求就地工作voidDeleteX(SqList*L,ElemTypex)intj=0;for(i=0;ilength;+i)if(L-elemi!=x)if(ij)L-elemj=L-elemi;+j;L-length=j;3 .试编写一个函数，在数组R已正序排列中进行折半查找某个值k,找到则返回其位置，否则返回0。intSearchBin(intR,intn,intk)k 为待查找的值/有序正序的顺序表的