数据结构期末复习单选

1、数据结构(本科)期末综合练习一(单项选择题)单项选择题1.一个数组元素ai与()的表示等价.A.*(a+i)B.a+iC.*a+iD.&a+i2.假设需要利用形参直接访问实参,那么应把形参变量说明为()参数.A.指针B.引用C.传值D.常值3.下面程序段的时间复杂度为().for(inti=0;im;i+)for(intj=0;jn;j+)aij=i*j;A.O(m2)B.O(n2)C.O(m*n)D.O(m+n)4.执行下面程序段时,执行S语句的次数为().for(inti=1;i=n;i+)for(intj=1;jlink=NULL;C.first-link=first;D.first!=

2、NULL;29.带头结点的单链表first为空的判定条件是().A.first=NULL;B.first-link=NULL;C.first-link=first;D.first!=NULL;30.设单链表中结点的结构为(data,link).指针q所指结点是指针p所指结点的直接前驱,假设在*q与*p之间插入结点*s,那么应执行的操作是().A.s-link=p-link;p-link=s;B.q-link=s;s-link=p;C.p-link=s-link;s-link=p;D.p-link=s;s-link=q;31.设单链表中结点的结构为(data,link).指针p所指结点不是尾结点

3、,假设在*p之后插入结点*s,那么应执行的操作是().A.s-link=p;p-link=s;B.p-link=s;s-link=p;C.s-link=p-link;p=s;D.s-link=p-link;p-link=s;32.设单链表中结点的结构为(data,link).假设想摘除p-link所指向的结点,那么应执行的操作是().A.p-link=p-link-link;B.p=p-link;p-link=p-link-link;C.p-link=p;D.p=p-link-link;33.非空的尾结点(由p所指向)满足的条件是().A.p-lin循环单链表first的k=NULL;B.p=

4、NULL;C.p-link=first;D.p=first;34.设单循环链表中结点的结构为(data,link),且rear是指向非空的带表头结点的单循环链表的尾结点的指针.假设想删除链表第一个结点,那么应执行的操作是().A.s=rear;rear=rear-link;deletes;B.rear=rear-link;deleterear;C.rear=rear-link-link;deleterear;D.s=rear-link-link;rear-link-link=s-link;deletes;35.从一个具有n个结点的单链表中查找其值等于x结点时,在查找成功的情况下,需要平均B.n

5、/2D.(n+1)/2n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是).A.B.O(n)C.O(n2)D.O(nlog汨)37.给定有n个元素的向量,建立一个有序单链表的时间复杂度是().A.O(1)B.O(n)C.O(n2)D.O(nlog2n)38.单链表A长度为m单链表B长度为n,假设将B联接在A的末尾,其时间复杂度应为().A.O(1)B.O(m)C.O(n)D.O(m+n)39.利用双向链表作线性表的存储结构的优点是().A.便于单向进行插入和删除的操作B.便于双向进行插入和删除的操作比拟的结点数是(A.nC.(n-1)/236.在一个具有C.节省空间D.便于销毁结

6、构释放空间40.带表头的双向循环链表的空表满足.A.first=NULL;B.first-rLink=firstC.first-lLink=NULLD.first-rLink=NULL41.L是一个不带表头的单链表,在表首插入结点*p的操作是.A.p=L;p-link=L;C.p-link=L;L=p;42.L是带表头的单链表B.L-link=L-link-link;C.L=L;D.L-link=L;43.栈的插入和删除操作在进行.A.栈顶B.栈底C.任意位置44.当利用大小为n的数组顺序存储一个栈时,假定用个元素时,首先应执行语句彳改top指针.A.top+;B.top-;C.top=0;4

7、5.假设让元素1,2,3依次进栈,那么出栈次序不可能出现A.3,2,1B.2,1,3C.3,1,246.在一个顺序存储的循环队列中,队头指针指向队头元素的位置.A.前一个B.后一个C.当前D.后面47.当利用大小为n的数组顺序存储一个队列时,该队列的最大长度为A.n-2B.n-1C.nD.n+148.从一个顺序存储的循环队列中删除一个元素时,首先需要A.队头指针加一B.队头指针减一C.取出队头指针所指的元素D.取出队尾指针所指的元素49.假定一个顺序存储的循环队列的队头和队尾指针分别为front和rear,那么判断队空的条件为A.front+1=rearB.rear+1=frontC.fron

8、t=0D.front=rear50.假定一个链式队列的队头和队尾指针分别为front和rear,那么判断队空的条件为A.front=rearB.front!=NULLC.rear!=NULLD.front=NULL51.设链式栈中结点的结构为data,link,且top是指向栈顶的指针.假设想在链式栈的栈顶插入一个由指针s所指的结点,那么应执行操作.A.top-link=s;B.s-link=top-link;top-link=s;C.s-link=top;top=s;D.s-link=top;top=top-link;52.设链式栈中结点的结构为(data,link),且top是指向栈顶的指

9、针.假设想摘除链式栈的栈顶结点,并将被摘除结点的值保存到x中,那么应执行()操作.A.x=top-data;top=top-link;B.top=top-link;x=top-data;C.x=top;top=top-link;D.x=top-data;53.设循环队列的结构是typedefstructB.p-link=L;p=L;D.L=p;p-link=L;A.L=L-link;删除首元结点的语句是D.指定位置top=n表示栈空,那么向这个栈插入一D.top;种情况.D.1,3,2DataTypedataMaxSize;intfront,rear;Queue;假设有一个Queue类型的队列

10、Q试问判断队列?t的条件应为().A.Q.front=Q.rear;B.Q.front-Q.rear=MaxSize;C.Q.front+Q.rear=MaxSize;D.Q.front=(Q.rear+1)%MaxSize;54.设循环队列的结构是constintMaxSize=100;typedefintDataType;typedefstructDataTypedataMaxSize;intfront,rear;Queue;假设有一个Queue类型的队列Q那么应用表达式计算队列元素的个数.A.Q.rear-Q.front+MaxSize%MaxSize;C.Q.rear-Q.front-

11、1;D.Q.rear-Qfront;55.为增加内存空间的利用率和减少溢出的可能性,由两个栈共享一块连续的内存空间时应将两栈的分别设在这块内存空间的两端.A.长度B.深度C.栈顶D.栈底56.递归是将一个较复杂的规模较大的问题转化为一个稍为简单的规模较小的与原问题的问题来解决,使之比原问题更靠近可直接求解的条件.A.相关B.子类型相关C.同类型D.不相关57.递归调用时系统需要利用一个来实现数据的传递和限制的转移.A.队列B.优先级队列C.双端队列D.栈58.在系统实现递归调用时需利用递归工作记录保存,当递归调用程序执行结束时通过它将限制转到上层调用程序.A.调用地址B.递归入口C.返回地址D

12、.递归出口59.在递归执行过程中,当前执行的递归函数过程的递归工作记录一定是递归工作栈中的栈顶记录,称之为记录.A.活动B.当前C.日志D.标记60.将递归求解过程改变为非递归求解过程的目的是.A.提升速度B.改善可读性C.增强健壮性D.提升可维护性61.如果一个递归函数过程中只有一个递归语句,而且它是过程体的最后语句,那么这种递归属于,它很容易被改写为非递归过程.A.单向递归B.回溯递归C.间接递归D.尾递归62.设有一个递归算法如下intfactintn/n大于等于0ifn=0return1;elsereturnn*factn-1;那么计算factn需要函数调用的次数为次.A.nB.n+1

13、C,n+2D.n-163.设有一个递归算法如下intX(intn)if(n0的结点,其双亲结点的编号为.A.(i+1)/2B.(i-1)/2C.i/2D.i/2-179.在一棵树白左子女-右兄弟表示法中,一个结点的右子女是该结点的()结点.A.兄弟B.父子C.祖先D.子孙80.在一棵树的静态双亲表示中,每个存储结点包含()个域.A1B2C3D481.一棵二叉树的广义表表示为a(b(c),d(e(,g(h),f),那么该二叉树的高度为()假定树根结点的高度为0.A.3B.4C.5D.682.一棵树的边集表示为,那么该树的深度为().假定树根结点的高度为0.A.2B.3C.4D.583.利用n个值

14、作为叶结点的权生成的霍夫曼树中共包含有()个结点.A.nB.n+1C.2*nD.2*n-184.利用3,6,8,12这四个值作为叶子结点的权,生成一棵霍夫曼树,该树的带权路径长度为().A55B29C58D3885.一棵树的广义表表示为a(b,c(e,f(g),d),当用左子女-右兄弟链表表示时,右指针域非空的结点个数为().A1B2C3D486.向具有n个结点的堆中插入一个新元素的时间复杂度为().A.O(1)B.O(n)C.O(log2n)D.O(nlog2n)87.假设搜索每个元素的概率相等,那么在长度为n的顺序表上搜索任一元素的平均搜索长度为().A.nB.n+1C.(n-1)/2D.

15、(n+1)/288.对长度为10的顺序表进行搜索,假设搜索前面5个元素的概率相同,均为1/8,搜索后面5个元素的概率相同,均为3/40,那么搜索任一元素的平均搜索长度为().A.5.5B.5C.39/8D.19/489.对长度为3的顺序表进行搜索,假设搜索第一个元素的概率为1/2,搜索第二个元素的概率为1/3,搜索第三个元素的概率为1/6,那么搜索任一元素的平均搜索长度为().A.5/3B.2C.7/3D.4/390.对长度为n的单链有序表,假设搜索每个元素的概率相等,那么搜索任一元素的搜索成功的平均搜索长度为()A.n/2B.(n+1)/2C.(n-1)/2D.n/491.对于长度为n的顺序

16、存储的有序表,假设采用折半搜索,那么对所有元素的搜索长度中最大的为()的值向上取整.A.log2(n+1)B.log2nC.n/2D.(n+1)/292.对于长度为n的顺序存储的有序表,假设采用折半搜索,那么对所有元素的搜索长度中最大的为()的值的向下取整加1.A.log2(n+1)B.log2nC.n/2D.(n+1)/293.对于长度为9的顺序存储的有序表,假设采用折半搜索,在等概率情况下搜索成功的平均搜索长度为()除以9.A.20B.18C.25D.22|94.()A.395.对于长度为18的顺序存储的有序表,假设采用折半搜索,那么搜索第B.4C.5D.615个元素的搜索长度为对具有n个

17、元素的有序表进行折半搜索,那么搜索任一元素的时间复杂度为A.0(n)B.0(n96.()A.n97.在一棵高度为2的具有C.0(1)D.O(log2n)n个元素的二叉搜索树中,搜索一个元素的最大搜索长度为B.log2nC.(h+1)/2D.h+1从具有n个结点的二叉搜索树中搜索一个元素时,在等概率情况下进行成功搜索的时间复杂度大致为A.O(n)B.O(1)C.O(log2n)D.0(n2)98.向具有n个结点的二叉搜索树中插入一个元素的时间复杂度大致为A.0(1)B.O(log99.A.-12n)C.0(n)D.O(nlog2n)在一棵AVL树中,每个结点的平衡因子的取值范围是B.-22C.1

18、2D.0100.种旋转类型A.2101.向一棵B.3向一棵此时需要修改相关A.2B.3102.向一棵要修改相关A.2B.3103.设G=AVL树插入元素时,可能引起对最小不平衡子树的调整过程,此调整分为C.4D.5AVL树插入元素时,可能引起对最小不平衡子树的左单或右单旋转的调整过程,个指针域的值.C.D.5AVL树插入元素时,可能引起对最小不平衡子树的双向旋转的调整过程,此时需个指针域的值.C.4(V,E1).G是G的连通分量D.5和G=V2,E2为两个图,如果B.G是G的子图D.G是G的连通分量104.有向图的一个顶点的度数等于该顶点的入度B.出度C.入度与出度之和105.一个连通图的生成

19、树是包含图中所有顶点的一个.极小子图B.连通子图106.n个顶点的连通图中至少含有.n-1条边C.极小连通子图Vi.n(n-1)/2条边DV2,EiE2,那么称入度+出度/2n(n-1)条边107.n个顶点的强连通图中至少含有.n-1条有向边B.n条有向边C.n(n-1)/2条有向边D.nn-1条有向边108.在一个带权连通图G中,权值最小的边一定包含在6的中.A.最小生成树.广度优先生成树B.生成树D.深度优先生成树109.对于具有e条边的无向图,它的邻接表中有个边结点.eC.2(e-1)D110.具有n个顶点的有向无环图最多可包含.n(n-1)/2条有向边.nn-1111.一个有n个顶点和

20、n条边的无向图一定是.A.连通的B.不连通的C.无环的D.有环的112.在n个顶点的有向无环图的邻接矩阵中至少有个零元素.A.nB.nn-1/2C.nn+1/2D.nn-1113.对于有向图,其邻接矩阵表示比邻接表表示更易于.A.查找一条边B.求一个顶点的邻接点C.进行图的深度优先遍历D.进行图的广度优先遍历114.在一个有向图的邻接矩阵表示中,删除一条边需要消耗的时间是.A.O1B.OiC.OjD.Oi+j115.与邻接矩阵相比,邻接表更适合于存储.A.无向图B.连通图C.稀疏图D.稠密图116.设一个有n个顶点和e条边的有向图采用邻矩阵表示,要计算某个顶点的出度所消耗的时间是.一_一一一_

21、2A.OnB.OeC.On+eD.On117.为了实现图的广度优先遍历,BFS算法使用的一个辅助数据结构是.A.栈B.队列C.二叉树D.树118.设无向图的顶点个数为n,那么该图最多有条边.A.n-1B.nn-1/2C.nn+1/2D.nn-1119.在一个无向图中,所有顶点的度数之和等于所有边数的倍.A.3B.2C.1D.1/2120.假设采用邻接矩阵存储具有n个顶点的无向图,那么该邻接矩阵是一个.A.上三角矩阵B.稀疏矩阵C.对角矩阵D.对称矩阵121.图的深度优先搜索类似于树的次序遍历.A.先根B.中根C.后根D.层次122.图的广度优先搜索类似于树的次序遍历.A.先根B.中根C.后根D

22、.层次123.在用Kruskal算法求解带权连通图的最小代价生成树时,通常采用一个辅助结构,判断一条边的两个端点是否在同一个连通分量上.A.位向量B.堆C.并查集D.生成树顶点集合124.采用Dijkstra算法求解带权有向图的最短路径问题时,要求图中每条边所带的权值必须是数.A.非零B.非整C.非负D.非正125.设有向图有n个顶点和e条边,采用邻接表作为其存储表示,在进行拓扑排序时,总的计算时间为 .A.Onlog2eB.On+eC.OneD.On2126.假设待排序对象序列在排序前已根本按排序码递增顺序排列,那么采用方法比拟次数最少.A.直接插入排序B.快速排序C.归并排序D.直接选择排

23、序127.对待排序的元素序列进行划分,将其分为左、右两个子序列,再对两个子序列施加同样的排序操作,直到子序列为空或只剩一个元素为止.这样的排序方法是.A.直接选择排序B.直接插入排序C.快速排序D.起泡排序128.对5个不同的数据元素进行直接插入排序,最多需要进行次比拟.A.8B.10C.15D.25129.以下排序算法中,算法是不稳定的.A.起泡排序B.直接插入排序C.基数排序D.快速排序130.假设某文件经过内部排序得到100个初始归并段,那么如果要求利用多路平衡归并在3趟内完成排序,那么应取的归并路数至少是.A.3B.4C.5D.6131.在基于排序码比拟的排序算法中,算法在最坏情况下的

24、时间复杂度不高于Onlog2n.A.起泡排序B.希尔排序C.堆排序D.快速排序132.在以下排序算法中,算法使用的附加空间与输入序列的长度及初始排列无关.A.锦标赛排序B.快速排序C.基数排序D.归并排序133.一个对象序列的排序码为46,79,56,38,40,84,采用快速排序以位于最左位置的对象为基准所得到的第一次划分结果为.A.38,46,79,56,40,84B.38,79,56,46,40,84C.40,38,46,79,56,84D.38,46,56,79,40,84134.如果将所有中国人根据生日不考虑年份,只考虑月、日来排序,那么使用以下排序算法中算法最快.A.归并排序B.希

25、尔排序C.快速排序D.基数排序135.设有一个含有200个元素的表待散列存储,用线性探查法解决冲突,按关键码查询时找到一个元素的平均探查次数不能超过1.5,那么散列表的长度应至少为.注：平均探查次数的计算公式为S尸1+1/1-/2,其中a为装填因子140.当对一个线性表R60进行索引顺序搜索分块搜索时,假设共分成了10个子表,每个6个表项.假定对索引表和数据子表都采用顺序搜索,那么搜索每一个表项的平均搜索长度为141.当对一个线性表R60进行索引顺序搜索分块搜索时,假设共分成了8个子表,每个6个表项.假定对索引表和数据子表都采用顺序搜索,那么搜索每一个表项的平均搜索长度为.A.7B.8C.9D

26、.10142.既希望较快的搜索又便于线性表动态变化的搜索方法是.A.顺序搜索B.折半搜索C.散列搜索D.索引顺序搜索C.h+1D.h+2A.h-1B.hC.h+1D.h+2A.7B.8C.9D.10A.400B.526C.624D.676136. 5阶B树中,每个结点最多允许有个关键码.A.2B.3C.4D.5137.在10阶B树中根结点所包含的关键码个数最少为.A.0B.1C.3D.4138.在一棵高度为h的B树中,叶结点处于第层.注：树根结点为第度为失败结点所处层数.A.h-1B.h139.结点.在一棵高度为h的B树中,插入一个新关键码时,为搜索插入位置需读取0层,B树高143.散列函数应该有这样的性质,即函数值应当以概率取其值域范围内的每一个值.A.最大B.最小C.平均D.同等144.设散列地址空间为0m-1,k为表项的关键码,散列函数采用除留余数法,即Hashk=k%p.为了减少发生冲突的频率,一般取p为.A.mB.小于m的最大质数C.大于m的最小质数D.小于m的最大合数145.在采用开散列法解决冲突时,每一个散列地址所链接的同义词子表中各个表项的值相同.A.关键码B.非关键码C.散列函数D.某个域146.解决散列法中出现的冲突问题常采用的方法是.A.数字分析法、除留余数法、平方取中法B.数字分析法、除留余数法、线性探查法C.数字分析法、线性探查