数据结构与算法模拟练习题含答案

数据结构与算法模拟练习题含答案一、单选题（共86题，每题1分，共86分）1.数据元素在计算机存储器内表示时，物理相对位置和逻辑相对位置相同并且是连续的，称之为（）。A、逻辑结构B、顺序存储结构C、链式存储结构D、以上都不对正确答案：B2.对于给定的有权无向图G，下列哪个说法是正确的？A、G的最小生成树中，任意一对顶点间的路径必是它们在G中的最短路径B、设顶点V到W的最短路径为P。若我们将G中每条边的权重都加1，则P一定仍然是V到W的最短路径C、单源最短路问题可以用O(∣E∣+∣V∣)的时间解决D、以上都不对正确答案：D3.被计算机加工的数据元素不是孤立的，它们彼此之间一般存在某种关系，通常把数据元素之间的这种关系称为A、结构B、运算C、集合D、规则正确答案：A4.若栈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、-15B、15C、-20D、20正确答案：B5.关于存储结构▁▁▁▁▁的特点是借助指示元素存储地址的指针来表示数据元素之间的逻辑关系。A、链式存储结构B、索引存储结构C、顺序存储结构D、散列存储结构正确答案：A6.算法分析的目的是()A、找出数据结构的合理性B、研究算法中的输入和输出的关系C、分析算法的易读性和文档性D、分析算法的效率以求改进正确答案：D7.若一个栈的入栈序列为1、2、3、…、N，输出序列的第一个元素是i，则第j个输出元素是：A、j−i−1B、i−jC、不确定D、i−j−1正确答案：C8.给定初始待排序列{15，9，7，8，20，-1，4}。如果希尔排序第一趟结束后得到序列为{15，-1，4，8，20，9，7}，则该趟增量为：A、3B、2C、4D、1正确答案：C9.某二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树一定是（）A、空或只有一个节点B、完全二叉树C、二叉排序树D、高度等于其节点数正确答案：D10.二叉树的高度若根节点为高度1，一棵具有1025个结点的二叉树的高度为▁▁▁▁▁。A、11～1025之间B、10C、11D、10～1024之间正确答案：A11.在AOE网中，什么是关键路径？A、最短回路B、最长回路C、从第一个事件到最后一个事件的最短路径D、从第一个事件到最后一个事件的最长路径正确答案：D12.一棵有1001个结点的完全二叉树，其叶子结点数为▁▁▁▁▁。A、250B、500C、254D、501正确答案：D13.在将数据序列（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→6,9,7,1,8,4,5→9,6,7,1,8,4,5→9,8,7,1,6,4,5C、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,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正确答案：A14.设散列表的地址区间为[0,16]，散列函数为H(Key)=Key%17。采用线性探测法处理冲突，并将关键字序列{26，25，72，38，8，18，59}依次存储到散列表中。元素59存放在散列表中的地址是：A、11B、10C、8D、9正确答案：A15.在下列查找的方法中，平均查找长度与结点个数无关的查找方法是：A、二分法B、利用二叉搜索树C、顺序查找D、利用哈希（散列）表正确答案：D16.已知不相交集合用数组表示为{4,6,5,2,-3,-4,3}。若集合元素从1到7编号，则调用Union(Find(7),Find(1))（按规模求并，并且带路径压缩）后的结果数组为：A、{4,6,5,2,-7,5,3}B、{4,6,5,2,6,-7,3}C、{6,6,5,6,6,-7,5}D、{6,6,5,6,-7,5,5}正确答案：C17.若一棵AVL树有28个结点，则该树的最大深度为__。空树的深度定义为0。A、4B、5C、6D、7正确答案：C18.已知一棵二叉树的前序遍历结果为ABCDEFG,中序遍历结果为BCAEDGF,则后序遍历的结果为（）。A、CBAEGFDB、CBEGFDAC、BCEGFDAD、CBEFGDA正确答案：B19.有两个垃圾邮件检测系统，分别用带有10000封正常邮件和2000封垃圾邮件的数据集进行测试。系统A检测出了300封正常邮件和1600封垃圾邮件，系统B检测出了315封正常邮件和1800封垃圾邮件。如果我们重点关注的是保证重要邮件的安全，下列哪句陈述是正确的？A、我们应重点关注准确率，系统A更好一些。B、我们应重点关注召回率，系统B更好一些。C、我们应重点关注准确率，系统B更好一些。D、我们应重点关注召回率，系统A更好一些。正确答案：C20.已知字符集{a,b,c,d,e,f}，若各字符出现的次数分别为{6,3,8,2,10,4}，则对应字符集中各字符的哈夫曼编码可能是：A、00,100,110,000,0010,01B、00,1011,01,1010,11,100C、0011,10,11,0010,01,000D、10,1011,11,0011,00,010正确答案：B21.设一棵非空完全二叉树T的所有叶节点均位于同一层，且每个非叶结点都有2个子结点。若T有k个叶结点，则T的结点总数是：A、2k−1B、2kC、k2D、2k−1正确答案：D22.下列几组概念中，那一组不完全跟搜索引擎有关？A、分布式索引，回溯法，查询B、倒排文件索引，停用词，准确率C、词干提取，哈希散列，压缩D、倒排表，阈值设置，召回率正确答案：A23.一棵非空二叉树，若先序遍历与中序遍历的序列相同，则该二叉树▁▁▁▁▁。A、所有结点均无左孩子B、所有结点均无右孩子C、只有一个叶子结点D、为任意二叉树正确答案：A24.设T是非空二叉树，若T的后序遍历和中序遍历序列相同，则T的形态是__A、只有一个根结点B、没有度为1的结点C、所有结点只有左孩子D、所有结点只有右孩子正确答案：C25.对N个记录进行堆排序，最坏的情况下时间复杂度是：A、O(logN)B、O(N2)C、O(NlogN)D、O(N)正确答案：C26.将元素序列{18，23，11，20，2，7，27，33，42，15}按顺序插入一个初始为空的、大小为11的散列表中。散列函数为：H(Key)=Key%11，采用线性探测法处理冲突。问：当第一次发现有冲突时，散列表的装填因子大约是多少？A、0.27B、0.73C、0.64D、0.45正确答案：D27.已知有向图G=(V,E)，其中V={v1,v2,v3,v4,v5,v6}，E={<v1,v2>,<v1,v4>,<v2,v6>,<v3,v1>,<v3,v4>,<v4,v5>,<v5,v2>,<v5,v6>}。G的拓扑序列是：A、v1,v3,v4,v5,v2,v6B、v1,v3,v4,v5,v2,v6C、v3,v1,v4,v5,v2,v6D、v3,v4,v1,v5,v2,v6正确答案：C28.给定散列表大小为11，散列函数为H(Key)=Key%11。采用平方探测法处理冲突：hi(k)=(H(k)±i2)%11将关键字序列{6，25，39，61}依次插入到散列表中。那么元素61存放在散列表中的位置是：A、5B、6C、7D、8正确答案：A29.在下述结论中，正确的是：①只有2个结点的树的度为1；②二叉树的度为2；③二叉树的左右子树可任意交换；④在最大堆（大顶堆）中，从根到任意其它结点的路径上的键值一定是按非递增有序排列的。A、①④B、②③④C、①②③D、②④正确答案：A30.线性表L在什么情况下适用于使用链式结构实现？A、L中结点结构复杂B、需不断对L进行删除插入C、需经常修改L中的结点值D、L中含有大量的结点正确答案：B31.对于先序遍历与中序遍历结果相同的二叉树为（）A、一般二叉树B、任一结点均无右孩子的二叉树C、任一结点均无左子树的二叉树D、以上都不是正确答案：C32.将元素序列{18,23,4,26,31,33,17,39}按顺序插入一个初始为空的、大小为13的散列表中。散列函数为：H(Key)=Key%13，采用线性探测法处理冲突。问：当第一次发现有冲突时，散列表的装填因子大约是多少？A、0.63B、0.62C、0.31D、0.54正确答案：C33.给定散列表大小为11，散列函数为H(Key)=Key%11。按照线性探测冲突解决策略连续插入散列值相同的4个元素。问：此时该散列表的平均不成功查找次数是多少？A、4/11B、1C、不确定D、21/11正确答案：D34.下面代码段的时间复杂度是（）。for(i=0;i<n;i++)for(j=0;j<m;j++)a[i][j]=0;A、O(mn)B、O(n2)C、O(1)D、O(m2)正确答案：A35.下列说法不正确的是：A、遍历的基本算法有两种：深度遍历和广度遍历B、图的深度遍历不适用于有向图C、图的深度遍历是一个递归过程D、图的遍历是从给定的源点出发每一个顶点仅被访问一次正确答案：B36.堆的形状是一棵：A、满二叉树B、完全二叉树C、二叉搜索树D、非二叉树正确答案：B37.将9,8,7,2,3,5,6,4顺序插入一棵初始为空的AVL树。下列句子中哪句是错的？A、5是根结点B、2和5是兄弟C、有2个结点的平衡因子为-1D、最后得到的AVL树的高度是3正确答案：A38.任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序A、发生改变B、不发生改变C、不能确定D、以上都不对正确答案：B39.在一个有2333个元素的最小堆中，下列哪个下标不可能是最大元的位置？A、2047B、1116C、1167D、2232正确答案：B40.将下列数（88,70,61,96,120,90）按顺序插入初始为空的AVL中，所形成的AVL树的前序遍历结果是：A、61,70,88,90,96,120B、90,70,61,88,96,120C、88,70,61,90,96,120D、88,70,61,96,90,120正确答案：D41.单链表-插入结点在单链表中，将s所指新结点插入到p所指结点之后，其语句应该为▁▁▁▁▁。A、s->next=p->next;p->next=s->next;B、s->next=p->next;p->next=s;C、p->next=s->next;s->next=p->next;D、p->next=s;s->next=p->next;正确答案：B42.给定N×N×N的三维数组A，则在不改变数组的前提下，查找最小元素的时间复杂度是：A、O(N2)B、O(NlogN)C、O(N2logN)D、O(N3)正确答案：D43.单链表-删除结点在单链表中，删除p所指结点的后继结点，其语句应该为▁▁▁▁▁。A、s=p->next;p->next=s->next;B、s=p;p->next=s;C、s=p->next;p->next=s;D、s=p;p->next=s->next;正确答案：A44.设有一个12×12的对称矩阵M，将其上三角部分的元素mi,j（1≤i≤j≤12）按行优先存入C语言的一维数组N中，元素m6,6在N中的下标是：A、50B、51C、55D、66正确答案：A45.具有N（N>0）个顶点的无向图至多有多少个连通分量？A、N−1B、NC、1D、0正确答案：B46.表达式3*2^(4+2*2-6*3)-5求值过程中当扫描到6时，对象栈和算符栈为（），其中^为乘幂。A、3,2,4,2,2；(*^(-B、3,2,4,1,1；(^(+-C、3,2,8；(*^-D、3,2,8；(*^(-正确答案：D47.对一棵二叉树的结点从1开始顺序编号。要求每个结点的编号都大于其子树所有结点的编号，且左子树所有结点的编号都小于右子树所有结点的编号。可采用▁▁▁▁▁实现编号。A、后序遍历B、先序遍历C、中序遍历D、层次遍历正确答案：A48.若AVL树的深度是6（空树的深度定义为-1），则该树的最少结点数是：A、13B、17C、20D、33正确答案：D49.设数组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正确答案：C50.设有100个元素的有序序列，如果用二分插入排序再插入一个元素，则最大比较次数是：A、50B、10C、7D、25正确答案：C51.任何一个带权无向连通图的最小生成树——A、是唯一的B、是不唯一的C、有可能不存在D、有可能不唯一正确答案：D52.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、先序遍历正确答案：C53.对N个记录进行归并排序，归并趟数的数量级是：A、O(logN)B、O(N)C、O(N2)D、O(NlogN)正确答案：A54.若采用带头、尾指针的单向链表表示一个堆栈，那么该堆栈的栈顶指针top应该如何设置？A、链表头、尾都不适合作为topB、将链表尾设为topC、将链表头设为topD、随便哪端作为top都可以正确答案：C55.对包含N个元素的散列表进行查找，平均查找长度为：A、O(logN)B、O(N)C、不确定D、O(1)正确答案：C56.在用邻接表表示有N个结点E条边的图时，深度优先遍历算法的时间复杂度为：A、O(N2)B、O(N)C、O(N+E)D、O(N2×E)正确答案：C57.设h为不带头结点的单向链表。在h的头上插入一个新结点t的语句是：A、h=t;t->next=h;B、t->next=h->next;h=t;C、h=t;t->next=h->next;D、t->next=h;h=t;正确答案：D58.下列关于栈的叙述中，错误的是：采用非递归方式重写递归程序时必须使用栈函数调用时，系统要用栈保存必要的信息只要确定了入栈次序，即可确定出栈次序栈是一种受限的线性表，允许在其两端进行操作A、仅1、3、4B、仅1C、仅1、2、3D、仅1、3、4正确答案：D59.利用大小为n的数组（下标从0到n-1）存储一个栈时，假定栈从数组另一头开始且top==n表示栈空，则向这个栈插入一个元素时，修改top指针应当执行：A、top=0B、top++C、top不变D、top--正确答案：D60.WhichoneofthefollowingisthelowestupperboundofT(n)forthefollowingrecursionT(n)=2T(n/2)+nlogn?A、O(nlogn)B、O(n2)C、O(nlog2n)D、O(n2logn)正确答案：C61.下列关于无向连通图特征的叙述中，正确的是：所有顶点的度之和为偶数边数大于顶点个数减1至少有一个顶点的度为1A、1和3B、只有1C、1和2D、只有2正确答案：B62.下列几组概念中，那一组不完全跟搜索引擎有关？A、字典，准确率，倒排文件索引B、动态索引，停用词，回溯法C、分布式索引，搜索树，倒排表D、阈值设置，网页排名，词干提取正确答案：B63.若用大小为6的数组来实现循环队列，且当前front和rear的值分别为0和4。当从队列中删除两个元素，再加入两个元素后，front和rear的值分别为多少？A、2和2B、2和0C、2和4D、2和6正确答案：B64.对N个记录进行快速排序，在最坏的情况下，其时间复杂度是：A、O(N2)B、O(N)C、O(N2logN)D、O(NlogN)正确答案：A65.程序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)正确答案：B66.如果AVL树的深度为5（空树的深度定义为0），则此树最少有多少个结点？A、12B、20C、33D、64正确答案：A67.给定散列表大小为11，散列函数为H(Key)=Key%11。按照线性探测冲突解决策略连续插入散列值相同的5个元素。问：此时该散列表的平均不成功查找次数是多少？A、1B、26/11C、5/11D、不确定正确答案：B68.现有长度为7、初始为空的散列表HT，散列函数H(k)=k%7，用线性探测再散列法解决冲突。将关键字22,43,15依次插入到HT后，查找成功的平均查找长度是：A、1.6B、1.5C、3D、2正确答案：D69.将6、4、3、5、8、9顺序插入初始为空的最大堆（大根堆）中，那么插入完成后堆顶的元素为：A、6B、9C、3D、5正确答案：B70.对10TB的数据文件进行排序，应使用的方法是：A、希尔排序B、堆排序C、归并排序D、快速排序正确答案：C71.下面描述中正确的为()。A、线性表的逻辑顺序与物理顺序总是一致的B、线性表的顺序存储表示优于链式存储表示。C、线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。D、二维数组是其数组元素为线性表的线性表。正确答案：C72.采用递归方式对顺序表进行快速排序，下列关于递归次数的叙述中，正确的是：A、递归次数与初始数据的排列次序无关B、每次划分后，先处理较短的分区可以减少递归次数C、每次划分后，先处理较长的分区可以减少递归次数D、递归次数与每次划分后得到的分区处理顺序无关正确答案：D73.若将n个顶点e条弧的有向图采用邻接表存储，则拓扑排序算法的时间复杂度是：A、O(n)B、O(n2)C、O(n+e)D、O(n×e)正确答案：C74.设森林F中有三棵树，第一、第二、第三棵树的结点个数分别为M1，M2和M3。则与森林F对应的二叉树根结点的右子树上的结点个数是：A、M2+M3B、M1+M2C、M1D、M3正确答案：A75.对于有向图，其邻接矩阵表示比邻接表表示更易于：A、求一个顶点的入度B、进行图的深度优先遍历C、求一个顶点的出边邻接点D、进行图的广度优先遍历正确答案：A76.对一棵二叉树的结点从1开始顺序编号。要求每个结点的编号大于其左子树所有结点的编号、但小于右子树中所有结点的编号。可采用▁▁▁▁▁实现编号。A、层次遍历B、先序遍历C、中序遍历D、后序遍历正确答案：C77.设有图的数据逻辑结构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正确答案：C78.已知求平方根函数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)正确答案：B79.用S表示入栈操作，X表示出栈操作，若元素入栈的顺序为1234，为了得到1342出栈顺序，相应的S和X的操作串为()。A、SXSSSXXXB、SXSSXSXXC、SSSSXXXXD、SXSXSXSX正确答案：B80.对给定序列{110，119，7，911，114，120，122}采用次位优先（LSD）的基数排序，则两趟收集后的结果为：A、7,110,119,114,911,120,122B、7,110,119,114,911,122,120C、7,110,911,114,119,120,122D、110,120,911,122,114,7,119正确答案：C81.用二分查找从100个有序整数中查找某数，最坏情况下需要比较的次数是：A、7B、99C、10D、50正确答案：A82.如果A和B都是二叉树的叶结点，那么下面判断中哪个是对的？A、存在一种二叉树结构，其前序遍历结果是…A…B…，而中序遍历结果是…B…A…B、存在一种二叉树结构，其中序遍历结果是…A…B…，而后序遍历结果是…B…A…C、存在一种二叉树结构，其前序遍历结果是…A…B…，而后序遍历结果是…B…A…D、以上三种都是错的正确答案：D83.对任意给定的含n(n>2)个字符的有限集S，用二叉树表示S的哈夫曼编码集和定长编码集，分别得到二叉树T1和T2。下列叙述中，正确的是：A、T1的高度大于T2的高度B、出现频次不同的字符在T1中处于不同的层C、出现频次不同的字符在T2中处于相同的层D、T1与T2的结点数相同正确答案：C84.双链表-插入结点在双链表中，将s所指新结点插入到p所指结点之前，其语句应该为▁▁▁▁▁。A、s->prev=p->prev;s->next=p;p->prev->next=s;p->prev=s;B、p->prev->next=s;p->prev=s;s->prev=p->prev;s->next=p;C、s->prev=p->prev;s->next=p;p->prev=s;p->prev->next=s;D、p->prev=s;p->prev->next=s;s->prev=p->prev;s->next=p;正确答案：B85.线性表若采用链式存储结构时，要求内存中可用存储单元的地址A、一定是不连续的B、部分地址必须是连续的C、必须是连续的D、连续或不连续都可以正确答案：D86.从栈顶指针为ST的链栈中删除一个结点且用X保存被删结点的值，则执行：A、X=ST->data;B、ST=ST->next;X=ST->data;C、X=ST->data;ST=ST->next;D、X=ST;ST=ST->next;正确答案：C二、多选题（共3题，每题1分，共3分）1.非空线性表的结构特征非空线性表具有哪些结构特征？A、除终端结点外，每个结点只有一个后继结点B、可拥有多个的开始结点和多个终端结点C、除开始结点外，每个结点只有一个前驱结点D、只有唯一的开始结点和唯一的终端结点正确答案：ACD2.下面结构中适于表示稀疏有向图的是（）。A、邻接多重表B、邻接表C、十字链表D、邻接矩阵E、逆邻接表正确答案：BCE3.关于二分查找算法二分查找算法能适用于▁▁▁▁▁。A、元素有序的顺序表B、元素有序的链表C、元素无序的顺序表D、元素无序的链表正确答案：A三、判断题（共26题，每题1分，共26分）1.对一棵平衡二叉树，所有非叶结点的平衡因子都是0，当且仅当该树是完全二叉树。A、正确B、错误正确答案：B2.任何AVL树的中序遍历结果是有序的（从小到大）。A、正确B、错误正确答案：A3.在散列表中，所谓同义词就是具有相同散列地址的两个元素。A、正确B、错误正确答案：A4.若一个栈的输入序列为{1,2,3,4,5}，则不可能得到{3,4,1,2,5}这样的出栈序列。A、正确B、错误正确答案：A