数据结构与算法练习题库（含答案）

数据结构与算法练习题库（含答案）一、单选题（共80题，每题1分，共80分）1、对一棵二叉树的结点从1开始顺序编号。要求每个结点的编号大于其左子树所有结点的编号、但小于右子树中所有结点的编号。可采用▁▁▁▁▁实现编号。A、中序遍历B、先序遍历C、层次遍历D、后序遍历正确答案：A2、设一段文本中包含4个对象{a,b,c,d}，其出现次数相应为{4,2,5,1}，则该段文本的哈夫曼编码比采用等长方式的编码节省了多少位数？A、5B、4C、2D、0正确答案：C3、两个有相同键值的元素具有不同的散列地址A、一定不会B、一定会C、可能会D、有万分之一的可能会正确答案：C4、将元素序列{18，23，11，20，2，7，27，33，42，15}按顺序插入一个初始为空的、大小为11的散列表中。散列函数为：H(Key)=Key%11，采用线性探测法处理冲突。问：当第一次发现有冲突时，散列表的装填因子大约是多少？A、0.73B、0.27C、0.64D、0.45正确答案：D5、对N个记录进行归并排序，归并趟数的数量级是：A、O(NlogN)B、O(logN)C、O(N)D、O(N2)正确答案：B6、下列说法不正确的是：A、图的遍历是从给定的源点出发每一个顶点仅被访问一次B、图的深度遍历不适用于有向图C、遍历的基本算法有两种：深度遍历和广度遍历D、图的深度遍历是一个递归过程正确答案：B7、二叉树的中序遍历也可以循环地完成。给定循环中堆栈的操作序列如下（其中push为入栈，pop为出栈）：push(1),push(2),push(3),pop(),push(4),pop(),pop(),push(5),pop(),pop(),push(6),pop()A、6是根结点B、2是4的父结点C、2和6是兄弟结点D、以上全不对正确答案：C8、设最小堆（小根堆）的层序遍历结果为{1,3,2,5,4,7,6}。用线性时间复杂度的算法将该堆调整为最大堆（大根堆），则该树的中序遍历结果为：A、3,5,4,7,2,6,1B、3,5,4,2,6,1,7C、1,4,3,7,2,6,5D、4,1,3,7,6,2,5正确答案：A9、以二叉链表作为二叉树的存储结构，在具有n个结点的二叉链表中（n>0），空链域的个数为__A、n+1B、无法确定C、n−1D、n正确答案：A10、链表不具有的特点是：A、所需空间与线性长度成正比B、插入、删除不需要移动元素C、不必事先估计存储空间D、方便随机访问任一元素正确答案：D11、已知求平方根函数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)正确答案：B12、一棵非空二叉树，若先序遍历与中序遍历的序列相同，则该二叉树▁▁▁▁▁。A、所有结点均无左孩子B、所有结点均无右孩子C、只有一个叶子结点D、为任意二叉树正确答案：A13、对最小堆（小顶堆）{1,3,2,6,7,5,4,15,14,12,9,10,11,13,8}进行三次删除最小元的操作后，结果序列为：A、4,5,6,7,8,9,10,11,12,13,14,15B、4,5,6,12,7,10,8,15,14,13,9,11C、4,6,5,12,7,10,8,15,14,9,13,11D、4,6,5,13,7,10,8,15,14,12,9,11正确答案：D14、双链表-删除结点在双链表中，删除p所指结点的后继结点，其语句应该为▁▁▁▁▁。A、s=p;s->next->prev=p->prev;p->next=s->next;B、s=p->next;s->next->prev=p;p->next=s->next;C、s=p->next;s->next->prev=p;p->next=s->next->next;D、s=p;s->next->prev=p;p->next=s->next;正确答案：B15、T(n)表示当输入规模为n时的算法效率，以下算法中效率最优的是()。A、T(n)=3nlog2nB、T(n)=T(n/2)+1,T(1)=1C、T(n)=2n2D、T(n)=T(n-1)+1,T(1)=1正确答案：B16、在快速排序的一趟划分过程中，当遇到与基准数相等的元素时，如果左指针停止移动，而右指针在同样情况下却不停止移动，那么当所有元素都相等时，算法的时间复杂度是多少？A、O(N2)B、O(N)C、O(NlogN)D、O(logN)正确答案：A17、一棵高度为8的完全二叉树至少有（）叶子节点A、128B、127C、63D、64正确答案：D18、已知不相交集合用数组表示为{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、{4,6,5,2,-7,5,3}D、{6,6,5,6,-7,5,5}正确答案：B19、从栈顶指针为ST的链栈中删除一个结点且用X保存被删结点的值，则执行：A、ST=ST->next;X=ST->data;B、X=ST->data;C、X=ST->data;ST=ST->next;D、X=ST;ST=ST->next;正确答案：C20、若一个栈的入栈序列为1、2、3、…、N，输出序列的第一个元素是i，则第j个输出元素是：A、i−j−1B、i−jC、不确定D、j−i−1正确答案：C21、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,5A、按层遍历B、先序遍历C、后序遍历D、中序遍历正确答案：D22、将键值1到15顺序插入一个初始为空的斜堆。则下列句子中哪句是错的？A、结果是一棵完全二叉树B、6是2的左孩子C、共有6个叶结点D、11是7的右孩子正确答案：C23、下列关于栈的叙述中，错误的是：采用非递归方式重写递归程序时必须使用栈函数调用时，系统要用栈保存必要的信息只要确定了入栈次序，即可确定出栈次序栈是一种受限的线性表，允许在其两端进行操作A、仅1、3、4B、仅1、3、4C、仅1、2、3D、仅1正确答案：A24、数组A[0..6,0..5]的每个元素占5个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5,5]的地址是()。A、1175B、1180C、1200D、1205正确答案：C25、对10TB的数据文件进行排序，应使用的方法是：A、希尔排序B、堆排序C、归并排序D、快速排序正确答案：C26、一棵满二叉树中127个节点，其中叶子节点的个数是（）A、64B、63C、65D、不确定正确答案：A27、树最适合于用来表示A、有序数据元素B、无序数据元素C、元素之间具有分支层次关系的数据D、元素之间无联系的数据正确答案：C28、若无向图G=（V，E）中含7个顶点，要保证图G在任何情况下都是连通的，则需要的边数最少是：A、15B、16C、6D、21正确答案：B29、一棵非空二叉树，若后序遍历与中序遍历的序列相同，则该二叉树▁▁▁▁▁。A、所有结点均无左孩子B、所有结点均无右孩子C、只有一个叶子结点D、为任意二叉树正确答案：C30、若二叉搜索树是有N个结点的完全二叉树，则不正确的说法是：A、平均查找效率是O(logN)B、最大值一定在最后一层C、最小值一定在叶结点上D、中位值结点在根结点或根的左子树上正确答案：B31、一棵有1001个结点的完全二叉树，其叶子结点数为▁▁▁▁▁。A、501B、500C、254D、250正确答案：A32、将10、12、1、14、6、5、8、15、3、9、7逐个按顺序插入到初始为空的最小堆（小根堆）中，然后连续执行两次删除最小元素操作（DeleteMin），此后堆顶的元素是什么？A、5B、6C、7D、9正确答案：A33、现有长度为7、初始为空的散列表HT，散列函数H(k)=k%7，用线性探测再散列法解决冲突。将关键字22,43,15依次插入到HT后，查找成功的平均查找长度是：A、1.5B、3C、1.6D、2正确答案：D34、在下列查找的方法中，平均查找长度与结点个数无关的查找方法是：A、顺序查找B、二分法C、利用二叉搜索树D、利用哈希（散列）表正确答案：D35、程序P1和P2时间复杂度的递推公式：P1:T(1)=1,T(N)=T(N/2)+1;P2:T(1)=1,T(N)=2T(N/2)+1;则下列关于两程序时间复杂度的结论中最准确的是：A、均为O(logN)B、P1是O(logN)，P2是O(N)C、均为O(N)D、P1是O(logN)，P2是O(NlogN)正确答案：B36、给定散列表大小为11，散列函数为H(Key)=Key%11。按照线性探测冲突解决策略连续插入散列值相同的4个元素。问：此时该散列表的平均不成功查找次数是多少？A、21/11B、1C、4/11D、不确定正确答案：A37、任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序A、发生改变B、不发生改变C、不能确定D、以上都不对正确答案：B38、若用平方探测法解决冲突，则插入新元素时，以下陈述正确的是A、插入不一定能成功B、插入一定不能成功C、若散列表容量为质数，插入就一定可以成功D、插入一定可以成功正确答案：A39、设森林F中有三棵树，第一、第二、第三棵树的结点个数分别为M1，M2和M3。则与森林F对应的二叉树根结点的右子树上的结点个数是：A、M2+M3B、M1+M2C、M1D、M3正确答案：A40、对N个记录进行堆排序，需要的额外空间为：A、O(N)B、O(NlogN)C、O(logN)D、O(1)正确答案：D41、图的深度优先遍历类似于二叉树的：A、后序遍历B、层次遍历C、先序遍历D、中序遍历正确答案：C42、若top为指向栈顶元素的指针，判定栈S（最多容纳m个元素）为空的条件是：A、S->top==-1B、S->top==0C、S->top==m-1D、S->top!=m-1正确答案：A43、在一个不带头结点的非空链式队列中,假设f和r分别为队头和队尾指针,则插入s所指的结点运算是()。A、s->next=f;f=s;B、r->next=s;r=s;C、s->next=s;r=s;D、f->next=s;f=s;正确答案：B44、在双向链表存储结构中，删除p所指的结点，相应语句为：A、p->next->prior=p;p->next=p->next->next;B、p->prior->next=p->next;p->next->prior=p->prior;C、p->next=p->prior->prior;p->prior=p->next->next;D、p->prior=p->prior->prior;p->prior->next=p;正确答案：B45、下列复杂度表示法中，（）表示算法复杂度渐近的紧的界，即一种算法的复杂度与某个函数的阶相等。A、大O表示法B、大Θ表示法C、大Ω标识符D、以上都不对正确答案：B46、若某二叉树有5个叶结点，其权值分别为10、12、16、21、30，则其最小的带权路径长度（WPL）是：A、200B、208C、89D、289正确答案：A47、链表-存储密度链表的存储密度▁▁▁▁▁。A、小于1B、等于1C、不能确定D、大于1正确答案：A48、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用哪种存储方式最节省时间？A、带头结点的双循环链表B、顺序表C、双链表D、单循环链表正确答案：B49、有六个元素以6、5、4、3、2、1的顺序进栈，问哪个不是合法的出栈序列？A、453126B、543612C、346521D、234156正确答案：C50、将一系列数字顺序一个个插入一棵初始为空的AVL树。下面哪个系列的第一次旋转是“右-左”双旋？A、1,2,3,4,5,6B、6,5,4,3,2,1C、4,2,5,6,3,1D、3,1,4,6,5,2正确答案：D51、下列几组概念中，那一组不完全跟搜索引擎有关？A、倒排文件索引，停用词，准确率B、词干提取，哈希散列，压缩C、倒排表，阈值设置，召回率D、分布式索引，回溯法，查询正确答案：D52、某二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树一定是（）A、空或只有一个节点B、完全二叉树C、二叉排序树D、高度等于其节点数正确答案：D53、采用线性探测法解决冲突时所产生的一系列后继散列地址：A、对地址在何处没有限制B、可以大于或小于但不等于原散列地址C、必须小于等于原散列地址D、必须大于等于原散列地址正确答案：B54、给定初始待排序列{15，9，7，8，20，-1，4}。如果希尔排序第一趟结束后得到序列为{15，-1，4，8，20，9，7}，则该趟增量为：A、2B、3C、1D、4正确答案：D55、有两个垃圾邮件检测系统，分别用带有10000封正常邮件和2000封垃圾邮件的数据集进行测试。系统A检测出了300封正常邮件和1600封垃圾邮件，系统B检测出了315封正常邮件和1800封垃圾邮件。如果我们重点关注的是保证重要邮件的安全，下列哪句陈述是正确的？A、我们应重点关注准确率，系统A更好一些。B、我们应重点关注召回率，系统B更好一些。C、我们应重点关注准确率，系统B更好一些。D、我们应重点关注召回率，系统A更好一些。正确答案：C56、设有1000个元素的有序序列，如果用二分插入排序再插入一个元素，则最大比较次数是：A、1000B、10C、999D、500正确答案：B57、下列哪个函数是O(N)的？A、N2/1000B、(NlogN)/1000C、(logN)2D、N(logN)2正确答案：C58、若采用带头、尾指针的单向链表表示一个堆栈，那么该堆栈的栈顶指针top应该如何设置？A、将链表尾设为topB、将链表头设为topC、随便哪端作为top都可以D、链表头、尾都不适合作为top正确答案：B59、数据结构中Dijkstra算法用来解决哪个问题？A、关键路径B、最短路径C、拓扑排序D、字符串匹配正确答案：B60、设有一个12×12的对称矩阵M，将其上三角部分的元素mi,j（1≤i≤j≤12）按行优先存入C语言的一维数组N中，元素m6,6在N中的下标是：A、50B、51C、55D、66正确答案：A61、Giventhefollowingfouralgorithmswiththeirruntimesforproblemsize100andtheirtimecomplexities:AlgorithmRuntimeTimeComplexityA100O(N)B50O(N2)C25O(N3)D10O(N4)Whichalgorithmisthefastestforproblemsize200?A、AB、BC、CD、D正确答案：D62、对n个互不相同的符号进行哈夫曼编码。若生成的哈夫曼树共有115个结点，则n的值是：A、56B、57C、58D、60正确答案：C63、设高为h的二叉树（规定叶子结点的高度为1）只有度为0和2的结点，则此类二叉树的最少结点数和最多结点数分别为：A、2h−1,2h−1−1B、2h−1,2h−1C、2h,2h−1D、2h−1+1,2h−1正确答案：B64、度量结果集相关性时，如果准确率很高而召回率很低，则说明：A、大部分相关文件被检索到，但基准数据集不够大B、大部分检索出的文件都是相关的，但基准数据集不够大C、大部分相关文件被检索到，但很多不相关的文件也在检索结果里D、大部分检索出的文件都是相关的，但还有很多相关文件没有被检索出来正确答案：D65、若结点p与q在二叉树T的中序遍历序列中相邻，且p在q之前，则下列p与q的关系中，不可能的是I.q是p的双亲II.q是p的右孩子III.q是p的右兄弟IV.q是p的双亲的双亲A、仅IIIB、仅II、IVC、仅ID、仅II、III正确答案：A66、Giventhefollowingfouralgorithmswiththeirruntimesforproblemsize100andtheirtimecomplexities:AlgorithmRuntimeTimeComplexityA100O(N)B30O(N2)C30O(N3)D10O(N4)A、AB、BC、CD、D正确答案：B67、数据结构讨论问题的最小单元为A、数据项B、数据对象C、数据结构D、数据元素正确答案：A68、AVL树是一种平衡的二叉搜索树，树中任一结点具有下列哪一特性：A、左、右子树的高度均相同B、左、右子树高度差的绝对值不超过1C、左子树的高度均大于右子树的高度D、左子树的高度均小于右子树的高度正确答案：B69、任何一个带权无向连通图的最小生成树——A、有可能不存在B、是唯一的C、有可能不唯一D、是不唯一的正确答案：C70、给定散列表大小为11，散列函数为H(Key)=Key%11。按照线性探测冲突解决策略连续插入散列值相同的5个元素。问：此时该散列表的平均不成功查找次数是多少？A、不确定B、5/11C、1D、26/11正确答案：D71、给定一个堆栈的入栈序列为{1,2,⋯,n}，出栈序列为{p1,p2,⋯,pn}。如果p2=n，则存在多少种不同的出栈序列？A、n−1B、2C、1D、n正确答案：A72、下面算法所执行的加法次数（）。输入：n，其中n=2t，t为正整数输出：kk←0whilen>=1doforj←1tondok=k+1n←n/2returnkA、2n-1B、nlognC、n2D、logn正确答案：A73、斐波那契数列FN的定义为：F0=0,F1=1,FN=FN−1+FN−2,N=2,3,…。用递归函数计算FN的空间复杂度是：A、O(logN)B、O(N!)C、O(N)D、O(FN)正确答案：C74、表达式3*2^(4+2*2-6*3)-5求值过程中当扫描到6时，对象栈和算符栈为（），其中^为乘幂。A、3,2,4,2,2；(*^(-B、3,2,8；(*^-C、3,2,8；(*^(-D、3,2,4,1,1；(^(+-正确答案：C75、将6、4、3、5、8、9顺序插入初始为空的最大堆（大根堆）中，那么插入完成后堆顶的元素为：A、3B、6C、5D、9正确答案：D76、下列排序算法中，哪种算法可能出现：在最后一趟开始之前，所有的元素都不在其最终的位置上？（设待排元素个数N>2）A、快速排序B、堆排序C、冒泡排序D、插入排序正确答案：D77、被计算机加工的数据元素不是孤立的，它们彼此之间一般存在某种关系，通常把数据元素之间的这种关系称为A、集合B、运算C、规则D、结构正确答案：D78、设数组S[]={93,946,372,9,146,151,301,485,236,327,43,892}，采用最低位优先（LSD）基数排序将S排列成升序序列。第1趟分配、收集后，元素372之前、之后紧邻的元素分别是：A、43，892B、236，301C、301，892D、485，301正确答案：C79、在有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位于数组中间位置正确答案：B80、线性表若采用链式存储结构时，要求内存中可用存储单元的地址A、连续或不连续都可以B、必须是连续的C、一定是不连续的D、部分地址必须是连续的正确答案：A二、判断题（共20题，每题1分，共20分）1、对N（≥2）个权值均不相同的字符构造哈夫曼树，则树中任一非叶结点的权值一