数据结构与算法复习题

数据结构与算法复习题一、单选题（共86题，每题1分，共86分）1.在计算机中存储数据时，通常不仅要存储各数据元素的值，而且还要存储()。A、数据的处理方法B、数据元素之间的关系C、数据元素的类型D、数据的存储方法正确答案：B2.下面描述中正确的为()。A、线性表的逻辑顺序与物理顺序总是一致的B、线性表的顺序存储表示优于链式存储表示。C、线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。D、二维数组是其数组元素为线性表的线性表。正确答案：C3.设n、m为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是A、n在m左方B、n是m子孙C、n在m右方D、n是m祖先正确答案：A4.在单链表中，若p所指的结点不是最后结点，在p之后插入s所指结点，则执行A、s->next=p->next;p->next=s;B、p->next=s;s->next=p;C、s->next=p;p->next=s;D、s->next=p->next;p=s;正确答案：A5.若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用哪种存储方式最节省运算时间？A、带头结点的双循环链表B、单循环链表C、单链表D、双链表正确答案：A6.如果AVL树的深度为6（空树的深度定义为−1），则此树最少有多少个结点？A、12B、20C、33D、64正确答案：C7.斐波那契数列FN的定义为：F0=0,F1=1,FN=FN−1+FN−2,N=2,3,…。用递归函数计算FN的时间复杂度是：A、O(N!)B、O(logN)C、NlogN2和NlogND、O(N)正确答案：C8.对于任意一棵高度为5且有10个结点的二叉树，若采用顺序存储结构保存，每个结点占1个存储单元（仅存放结点的数据信息），则存放该二叉树需要的存储单元的数量至少是：A、15B、16C、10D、31正确答案：D9.将M个元素存入用长度为S的数组表示的散列表，则该表的装填因子为：A、M/SB、M×SC、M−SD、S+M正确答案：A10.求整数n(n>=0)的阶乘的算法如下，其时间复杂度为（）。longfact(longn){if(n<=1)return1；returnn*fact(n-1)；}A、Θ(n2)B、Θ(nlog2n)C、Θ(log2n)D、Θ(n)正确答案：D11.若二叉搜索树是有N个结点的完全二叉树，则不正确的说法是：A、所有结点的平均查找效率是O(logN)B、最小值一定在叶结点上C、最大值一定在叶结点上D、中位值结点在根结点或根的左子树上正确答案：C12.对一组包含10个元素的非递减有序序列，采用直接插入排序排成非递增序列，其可能的比较次数和移动次数分别是：A、54,63B、100,100C、45,44D、100,54正确答案：C13.堆的形状是一棵：A、非二叉树B、二叉搜索树C、完全二叉树D、满二叉树正确答案：C14.下列各种数据结构中属于线性结构的有()A、图B、队列C、集合D、树正确答案：B15.若数据元素序列{11，12，13，7，8，9，23，4，5}是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是：A、冒泡排序B、插入排序C、归并排序D、选择排序正确答案：B16.已知不相交集合用数组表示为{4,6,5,2,-3,-4,3}。若集合元素从1到7编号，则调用Union(Find(7),Find(1))（按规模求并，并且带路径压缩）后的结果数组为：A、{4,6,5,2,6,-7,3}B、{6,6,5,6,6,-7,5}C、{6,6,5,6,-7,5,5}D、{4,6,5,2,-7,5,3}正确答案：B17.设一个堆栈的入栈顺序是1、2、3、4、5。若第一个出栈的元素是4，则最后一个出栈的元素必定是：A、1或者5B、1C、3D、5正确答案：A18.下列说法不正确的是：A、图的深度遍历不适用于有向图B、遍历的基本算法有两种：深度遍历和广度遍历C、图的遍历是从给定的源点出发每一个顶点仅被访问一次D、图的深度遍历是一个递归过程正确答案：A19.对一棵二叉树的结点从1开始顺序编号。要求每个结点的编号都小于其子树所有结点的编号，且左子树所有结点的编号都小于右子树所有结点的编号。可采用▁▁▁▁▁实现编号。A、层次遍历B、后序遍历C、先序遍历D、中序遍历正确答案：C20.在将数据序列（6,1,5,9,8,4,7）建成大根堆时，正确的序列变化过程是：A、6,1,7,9,8,4,5→6,9,7,1,8,4,5→9,6,7,1,8,4,5→9,8,7,1,6,4,5B、6,9,5,1,8,4,7→9,6,5,1,8,4,7→9,6,7,1,8,4,5→9,8,7,1,6,4,5C、6,9,5,1,8,4,7→6,9,7,1,8,4,5→9,6,7,1,8,4,5→9,8,7,1,6,4,5D、6,1,7,9,8,4,5→7,1,6,9,8,4,5→7,9,6,1,8,4,5→9,7,6,1,8,4,5→9,8,6,1,7,4,5正确答案：A21.适用于压缩存储稀疏矩阵的两种存储结构是：A、十字链表和二叉链表B、三元组表和十字链表C、邻接矩阵和十字链表D、三元组表和邻接矩阵正确答案：B22.斐波那契数列FN的定义为：F0=0,F1=1,FN=FN−1+FN−2,N=2,3,…。用递归函数计算FN的空间复杂度是：A、O(FN)B、O(N)C、O(N!)D、O(logN)正确答案：B23.T(n)表示当输入规模为n时的算法效率，以下算法中效率最优的是()。A、T(n)=2n2B、T(n)=T(n/2)+1,T(1)=1C、T(n)=T(n-1)+1,T(1)=1D、T(n)=3nlog2n正确答案：B24.关于图的邻接矩阵，下列哪个结论是正确的？A、有向图的邻接矩阵可以是对称的，也可以是不对称的B、无向图的邻接矩阵总是不对称的C、无向图的邻接矩阵可以是不对称的，也可以是对称的D、有向图的邻接矩阵总是不对称的正确答案：A25.在一个有2333个元素的最小堆中，下列哪个下标不可能是最大元的位置？A、2047B、1116C、2232D、1167正确答案：B26.从一个具有N个结点的单链表中查找其值等于X的结点时，在查找成功的情况下，需平均比较多少个结点？A、N/2B、(N−1)/2C、ND、(N+1)/2正确答案：D27.若栈S1中保存整数，栈S2中保存运算符，函数F()依次执行下述各步操作：（1）从S1中依次弹出两个操作数a和b；（2）从S2中弹出一个运算符op；（3）执行相应的运算bopa；（4）将运算结果压入S1中。假定S1中的操作数依次是{5,8,3,2}（2在栈顶），S2中的运算符依次是{*,-,+}（+在栈顶）。调用3次F()后，S1栈顶保存的值是：A、-20B、15C、20D、-15正确答案：B28.已知求平方根函数sqrt(n)的计算在O(1)时间内完成，下面算法的时间复杂度是（）。AlgorithmPrimalityTestInput：n,n≥2Output：true/falses←sqrt(n)forj←2tosdoif(nmodj==0)thenreturnfalsereturntrueA、O(1)B、O(√￣n)C、Ω(n)D、Ω(n2)正确答案：B29.已知二维数组A按行优先方式存储，每个元素占用1个存储单元。若元素A[0][0]的存储地址是100，A[3][3]的存储地址是220，则元素A[5][5]的存储地址是：A、295B、300C、301D、306正确答案：B30.二叉树的形态由3个结点可以构造出▁▁▁▁▁种不同形态的二叉树。A、2B、4C、3D、5正确答案：D31.对于一个具有N个结点的单链表，在给定值为x的结点后插入一个新结点的时间复杂度为A、O(1)B、O(N2)C、O(N)D、O(N/2)正确答案：C32.Forthefollowingpieceofcodefor(i=0;i<n;i++)for(j=i;j>0;j/=2)printf(“%d\n”,j);thetimecomplexityis:A、O(N2)B、O(N)C、O(NlogN)D、O(N×i)正确答案：C33.对于序列{49，38，65，97，76，13，27，50}，按由小到大进行排序，下面哪一个是初始步长为4的希尔排序法第一趟的结果？A、49,13,27,50,76,38,65,97B、97,76,65,50,49,38,27,13C、49,76,65,13,27,50,97,38D、13,27,38,49,50,65,76,97正确答案：A34.设T是非空二叉树，若T的后序遍历和中序遍历序列相同，则T的形态是__A、只有一个根结点B、没有度为1的结点C、所有结点只有左孩子D、所有结点只有右孩子正确答案：C35.利用大小为n的数组（下标从0到n-1）存储一个栈时，假定栈从数组另一头开始且top==n表示栈空，则向这个栈插入一个元素时，修改top指针应当执行：A、top不变B、top++C、top=0D、top--正确答案：D36.设每个d叉树的结点有d个指针指向子树，有n个结点的d叉树有多少空链域？A、n(d−1)+1B、n(d−1)+1C、ndD、n(d−1)正确答案：A37.将两个结点数都为N且都从小到大有序的单向链表合并成一个从小到大有序的单向链表，那么可能的最少比较次数是：A、NlogNB、NC、1D、2N正确答案：B38.为解决计算机主机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是？A、图B、堆栈C、队列D、树正确答案：C39.AVL树是一种平衡的二叉搜索树，树中任一结点具有下列哪一特性：A、左、右子树的高度均相同B、左、右子树高度差的绝对值不超过1C、左子树的高度均大于右子树的高度D、左子树的高度均小于右子树的高度正确答案：B40.二叉树的高度若根节点为高度1，一棵具有1025个结点的二叉树的高度为▁▁▁▁▁。A、11B、11～1025之间C、10D、10～1024之间正确答案：B41.对N个记录进行归并排序，归并趟数的数量级是：A、O(N)B、O(N2)C、O(NlogN)D、O(logN)正确答案：D42.从栈顶指针为ST的链栈中删除一个结点且用X保存被删结点的值，则执行：A、X=ST->data;B、ST=ST->next;X=ST->data;C、X=ST;ST=ST->next;D、X=ST->data;ST=ST->next;正确答案：D43.将6、4、3、5、8、9顺序插入初始为空的最大堆（大根堆）中，那么插入完成后堆顶的元素为：A、5B、6C、9D、3正确答案：C44.在数据结构中，从逻辑上可以把数据结构分成（）。A、动态结构和静态结构B、内部结构和外部结构C、紧凑结构和非紧凑结构D、线性结构和非线性结构正确答案：D45.度量结果集相关性时，如果准确率很高而召回率很低，则说明：A、大部分检索出的文件都是相关的，但还有很多相关文件没有被检索出来B、大部分检索出的文件都是相关的，但基准数据集不够大C、大部分相关文件被检索到，但基准数据集不够大D、大部分相关文件被检索到，但很多不相关的文件也在检索结果里正确答案：A46.设数字{4371,1323,6173,4199,4344,9679,1989}在大小为10的散列表中根据散列函数h(X)=X%10得到的下标对应为{1,3,4,9,5,0,2}。那么继续用散列函数“h(X)=X%表长”实施再散列并用线性探测法解决冲突后，它们的下标变为：A、1,3,4,9,5,0,2B、1,12,17,0,13,8,14C、1,12,9,13,20,19,11D、11,3,13,19,4,0,9正确答案：C47.如果A和B都是二叉树的叶结点，那么下面判断中哪个是对的？A、存在一种二叉树结构，其前序遍历结果是…A…B…，而中序遍历结果是…B…A…B、存在一种二叉树结构，其中序遍历结果是…A…B…，而后序遍历结果是…B…A…C、存在一种二叉树结构，其前序遍历结果是…A…B…，而后序遍历结果是…B…A…D、以上三种都是错的正确答案：D48.下列几组概念中，那一组不完全跟搜索引擎有关？A、词干提取，压缩，召回率B、分布式索引，哈希散列，倒排文件索引C、阈值设置，动态规划，准确率D、停用词，倒排表，动态索引正确答案：C49.WhichoneofthefollowingisthelowestupperboundofT(n)forthefollowingrecursionT(n)=2T(n/2)+nlogn?A、O(nlogn)B、O(nlog2n)C、O(n2logn)D、O(n2)正确答案：B50.对N个不同的数据采用冒泡算法进行从大到小的排序，下面哪种情况下肯定交换元素次数最多？A、从小到大排好的B、元素无序C、从大到小排好的D、元素基本有序正确答案：A51.在作进栈运算时，应先判别栈是否(①)；在作退栈运算时应先判别栈是否(②)。当栈中元素为n个，作进栈运算时发生上溢，则说明该栈的最大容量为(③)。①:A.空B.满C.上溢D.下溢②:A.空B.满C.上溢D.下溢③:A.n-1B.nC.n+1D.n/2A、①C②D③BB、①B②A③BC、①B②B③AD、①B②A③A正确答案：B52.具有5个顶点的有向完全图有多少条弧？A、20B、10C、25D、16正确答案：A53.将{28,15,42,18,22,5,40}依次插入初始为空的二叉搜索树。则该树的后序遍历结果是：A、5,22,18,15,40,42,28B、5,15,18,22,40,42,28C、28,22,18,42,40,15,5D、5,22,15,40,18,42,28正确答案：A54.给定一个堆栈的入栈序列为{1,2,⋯,n}，出栈序列为{p1,p2,⋯,pn}。如果p2=n，则存在多少种不同的出栈序列？A、n−1B、2C、1D、n正确答案：A55.算法分析的目的是()A、找出数据结构的合理性B、研究算法中的输入和输出的关系C、分析算法的效率以求改进D、分析算法的易读性和文档性正确答案：C56.在拓扑排序算法中用堆栈和用队列产生的结果会不同吗？A、是的肯定不同B、肯定是相同的C、有可能会不同D、以上全不对正确答案：C57.设有一个12×12的对称矩阵M，将其上三角部分的元素mi,j（1≤i≤j≤12）按行优先存入C语言的一维数组N中，元素m6,6在N中的下标是：A、50B、51C、55D、66正确答案：A58.给定散列表大小为11，散列函数为H(Key)=Key%11。按照线性探测冲突解决策略连续插入散列值相同的4个元素。问：此时该散列表的平均不成功查找次数是多少？A、不确定B、4/11C、21/11D、1正确答案：C59.采用多项式的非零项链式存储表示法，如果两个多项式的非零项分别为N1和N2个，最高项指数分别为M1和M2，则实现两个多项式相乘的时间复杂度是：A、O(M1+M2)B、O(N1×N2)C、O(M1×M2)D、O(N1+N2)正确答案：B60.给定A[]={46,23,8,99,31,12,85}，调用非递归的归并排序加表排序执行第1趟后，表元素的结果是：A、1,2,3,4,5,6,7B、1,0,2,3,5,4,6C、3,6,1,5,2,7,4D、0,2,1,4,3,5,6正确答案：B61.在快速排序的一趟划分过程中，当遇到与基准数相等的元素时，如果左指针停止移动，而右指针在同样情况下却不停止移动，那么当所有元素都相等时，算法的时间复杂度是多少？A、O(N2)B、O(N)C、O(logN)D、O(NlogN)正确答案：A62.输入105个只有一位数字的整数，可以用O(N)复杂度将其排序的算法是：A、快速排序B、插入排序C、基数排序D、希尔排序正确答案：C63.循环队列的队满条件为()。A、(sq.front+1)%maxsize==sq.rearB、sq.rear==sq.frontC、(sq.rear+1)%maxsize==sq.frontD、(sq.rear+1)%maxsize==(sq.front+1)%maxsize正确答案：C64.关于存储结构▁▁▁▁▁的特点是借助指示元素存储地址的指针来表示数据元素之间的逻辑关系。A、索引存储结构B、链式存储结构C、散列存储结构D、顺序存储结构正确答案：B65.一棵二叉树中有7个度为2的结点和5个度为1的结点，其总共有（）个结点。A、18B、30C、16D、20正确答案：D66.下面四种排序算法中，稳定的算法是：A、快速排序B、希尔排序C、堆排序D、归并排序正确答案：D67.对10TB的数据文件进行排序，应使用的方法是：A、希尔排序B、堆排序C、归并排序D、快速排序正确答案：C68.一棵度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T的叶子结点个数是()。A、113B、41C、122D、82正确答案：D69.在有n（n>1000）个元素的升序数组A中查找关键字x。查找算法的伪代码如下所示：k=0;while(k<n且A[k]<x)k=k+3;if(k<n且A[k]==x)查找成功;elseif(k-1<n且A[k-1]==x)查找成功;elseif(k-2<n且A[k-2]==x)查找成功;else查找失败;本算法与二分查找（折半查找）算法相比，有可能具有更少比较次数的情形是：A、当x不在数组中B、当x接近数组开头处C、当x接近数组开头处D、当x位于数组中间位置正确答案：B70.链表-存储密度链表的存储密度▁▁▁▁▁。A、大于1B、小于1C、不能确定D、等于1正确答案：B71.设森林F中有三棵树，第一、第二、第三棵树的结点个数分别为M1，M2和M3。则与森林F对应的二叉树根结点的右子树上的结点个数是：A、M1B、M1+M2C、M3D、M2+M3正确答案：D72.给定N×N×N的三维数组A，则在不改变数组的前提下，查找最小元素的时间复杂度是：A、O(N2)B、O(NlogN)C、O(N2logN)D、O(N3)正确答案：D73.设有1000个元素的有序序列，如果用二分插入排序再插入一个元素，则最大比较次数是：A、1000B、10C、500D、999正确答案：B74.设有图的数据逻辑结构B=(K,R)，其中顶点集K={k1,k2,⋯,k9}，有向边集R={<k1,k3>,<k1,k8>,<k2,k3>,<k2,k4>,<k2,k5>,<k3,k9>,<k5,k6>,<k8,k9>,<k9,k7>,<k4,k7>,<k4,k6>}。以下哪个选项不是对应DAG图的拓扑序列？A、k1,k2,k3,k4,k5,k6,k8,k9,k7B、k2,k5,k1,k4,k6,k8,k3,k9,k7C、k2,k4,k5,k6,k7,k1,k3,k8,k9D、k1,k8,k2,k3,k9,k4,k7,k5,k6正确答案：C75.下面说法中哪个是错误的：A、任何AVL树的中序遍历结果是有序的（从小到大）B、任何最小堆的前序遍历结果是有序的（从小到大）C、任何搜索树中同一层的结点从左到右是有序的（从小到大）D、任何最小堆中从根结点到任一叶结点路径上的所有结点是有序的（从小到大）正确答案：B76.已知一棵二叉树的前序遍历结果为ABCDEFG,中序遍历结果为BCAEDGF,则后序遍历的结果为（）。A、CBAEGFDB、CBEGFDAC、BCEGFDAD、CBEFGDA正确答案：B77.用二分查找从100个有序整数中查找某数，最坏情况下需要比较的次数是：A、50B、10C、7D、99正确答案：C78.设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出栈的顺序是s2,s3,s4,s6,s5,s1,则栈的容量至少应该是()。A、5B、3C、2D、6正确答案：B79.以下说法正确的是（）。A、数据结构是带有结构的各数据项的集合B、一些表面上很不相同的数据可以有相同的逻辑结构C、数据项是数据的基本单位D、数据元素是数据的最小单位正确答案：B80.一个具有1025个节点的二叉树的高h为（）A、11～1025B、11C、10D、12～1024正确答案：A81.若采用带头、尾指针的单向链表表示一个堆栈，那么该堆栈的栈顶指针top应该如何设置？A、将链表尾设为topB、链表头、尾都不适合作为topC、将链表头设为topD、随便哪端作为top都可以正确答案：C82.对于外排序中的k路归并，k不取很大值的首要原因是：A、输入\输出的时间会增多B、k必须是一个有限的整数C、k的上界是有序段的个数D、归并时的比较次数会增多正确答案：A83.已知一个长度为16的顺序表L，其元素按关键字有序排列。若采用二分查找法查找一个L中不存在的元素，则关键字的比较次数最多是：A、7B、6C、4D、5正确答案：D84.中位值结点在根结点或根的左子树上A、4B、2C、1D、3正确答案：B85.设T是非空二叉树，若T的先序遍历和后序遍历序列相同，则T的形态是A、只有一个根结点B、没有度为1的结点C、所有结点只有左孩子D、所有结点只有右孩子正确答案：A86.下面的程序段违反了算法的（）原则。voidsam(){intn=2;while(n%2==0)n+=2;printf(“%d”,n);}A、有穷性B、可行性C、确定性D、健壮性正确答案：A二、多选题（共3题，每题1分，共3分）1.下面结构中适于表示稀疏有向图的是（）。A、邻接矩阵B、邻接多重表C、邻接表D、逆邻接表E、十字链表正确答案：CDE2.以下哪些项是栈元素操作的基本特点：A、先进先出B、后进先出C、先进后出D、后进后出正确答案：BC3.关于顺序查找算法顺序查找算法能适用于▁▁▁▁▁。A、元素有序的链表B、元素无序的链表C、元素无序的顺序表D、元素有序的顺序表正确答案：ABCD三、判断题（共26题，每题1分，共26分）1.关于《数据结构》学科《数据结构》是一门研究数值计算的程序设计问题的学科。A、正确B、错误正确答案：B2.在实现二项式队列时，每棵二项式树的子树是按规模递增的顺序链接的。A、正确B、错误正确答案：B3.将10个元素散列到100000个单元的哈希表中，一定不会产生冲突。A、正确B、错误正确答案：B4.若图G有环，则G不存在拓扑排序序列。A、正确B、错误正确答案：A5.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用顺序表存储最节省时间。A、正确B、错误正确答案：A6.若一个栈的输入序列为{1,2,3,4,5}，则不可能得到{3,