数据结构与算法试题库与参考答案

数据结构与算法试题库与参考答案一、单选题（共86题，每题1分，共86分）1.数据结构讨论问题的最小单元为A、数据对象B、数据项C、数据结构D、数据元素正确答案：B2.已知一棵二叉树的先序遍历结果是ABC，则以下哪个序列是不可能的中序遍历结果：A、ABCB、BACC、CBAD、CAB正确答案：D3.一棵高度为8的完全二叉树至少有（）叶子节点A、127B、128C、64D、63正确答案：C4.若一棵二叉树的后序遍历序列是{1,3,2,6,5,7,4}，中序遍历序列是{1,2,3,4,5,6,7}，则下列哪句是错的？A、2是1和3的父结点B、7是5的父结点C、这是一棵完全二叉树D、这是一棵二叉搜索树正确答案：C5.某二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树一定是（）A、空或只有一个节点B、完全二叉树C、二叉排序树D、高度等于其节点数正确答案：D6.下面代码段的时间复杂度是（）。for(i=0;i<n;i++)for(j=0;j<m;j++)a[i][j]=0;A、O(1)B、O(n2)C、O(mn)D、O(m2)正确答案：C7.两个有相同键值的元素具有不同的散列地址A、一定会B、一定不会C、有万分之一的可能会D、可能会正确答案：D8.适用于压缩存储稀疏矩阵的两种存储结构是：A、三元组表和十字链表B、邻接矩阵和十字链表C、三元组表和邻接矩阵D、十字链表和二叉链表正确答案：A9.给定散列表大小为11，散列函数为H(Key)=Key%11。采用平方探测法处理冲突：hi(k)=(H(k)±i2)%11将关键字序列{6，25，39，61}依次插入到散列表中。那么元素61存放在散列表中的位置是：A、6B、8C、7D、5正确答案：D10.若某二叉树有5个叶结点，其权值分别为10、12、16、21、30，则其最小的带权路径长度（WPL）是：A、89B、289C、208D、200正确答案：D11.在有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位于数组中间位置正确答案：B12.设有一组关键字{29，01，13，15，56，20，87，27，69，9，10，74}，散列函数为H(key)=key%17，采用线性探测方法解决冲突。试在0到18的散列地址空间中对该关键字序列构造散列表，则成功查找的平均查找长度为__A、1.25B、1.17C、0.33D、1.33正确答案：D13.现有长度为7、初始为空的散列表HT，散列函数H(k)=k%7，用线性探测再散列法解决冲突。将关键字22,43,15依次插入到HT后，查找成功的平均查找长度是：A、1.5B、3C、2D、1.6正确答案：C14.下列各种数据结构中属于线性结构的有()A、图B、集合C、树D、队列正确答案：D15.若结点p与q在二叉树T的中序遍历序列中相邻，且p在q之前，则下列p与q的关系中，不可能的是I.q是p的双亲II.q是p的右孩子III.q是p的右兄弟IV.q是p的双亲的双亲A、仅II、IIIB、仅IIIC、仅II、IVD、仅I正确答案：B16.以下说法正确的是（）。A、数据元素是数据的最小单位B、数据项是数据的基本单位C、一些表面上很不相同的数据可以有相同的逻辑结构D、数据结构是带有结构的各数据项的集合正确答案：C17.被计算机加工的数据元素不是孤立的，它们彼此之间一般存在某种关系，通常把数据元素之间的这种关系称为A、集合B、运算C、结构D、规则正确答案：C18.以下数据结构中，（）是非线性数据结构。A、字符串B、树C、栈D、队列正确答案：B19.假定有K个关键字互为同义词，若用线性探测法把这K个关键字存入散列表中，至少要进行多少次探测？A、K+1B、K−1C、K(K+1)/2D、K正确答案：C20.将线性表La和Lb头尾连接，要求时间复杂度为O(1)，且占用辅助空间尽量小。应该使用哪种结构？A、带尾指针的单循环链表B、单链表C、带头结点的双循环链表D、单循环链表正确答案：A21.设一段文本中包含4个对象{a,b,c,d}，其出现次数相应为{4,2,5,1}，则该段文本的哈夫曼编码比采用等长方式的编码节省了多少位数？A、2B、4C、5D、0正确答案：A22.数据采用链式存储结构时，要求()A、每个节点占用一片连续的存储区域B、所有节点占用一片连续的存储区域C、节点的最后一个数据域一定是指针类型D、每个节点有多少个后继就设多少个指针域正确答案：A23.将{28,15,42,18,22,5,40}依次插入初始为空的二叉搜索树。则该树的后序遍历结果是：A、5,22,15,40,18,42,28B、5,15,18,22,40,42,28C、5,22,18,15,40,42,28D、28,22,18,42,40,15,5正确答案：C24.对N个记录进行归并排序，归并趟数的数量级是：A、O(N2)B、O(N)C、O(logN)D、O(NlogN)正确答案：C25.设有图的数据逻辑结构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正确答案：C26.一棵度为4的树中有20个度为4的结点、10个度为3的结点、1个度为2的结点和10个度为1的结点，则树的叶子结点数为▁▁▁▁▁。A、122B、41C、82D、113正确答案：C27.在评价一个搜索引擎时，下列哪项不是我们关注的要点？A、界面的友好程度B、搜索结果集的相关性C、索引的速度D、搜索的速度正确答案：A28.堆的形状是一棵：A、非二叉树B、二叉搜索树C、满二叉树D、完全二叉树正确答案：D29.如果无向图G必须进行两次广度优先搜索才能访问其所有顶点，则下列说法中不正确的是：A、G中一定有回路B、G一定不是连通图C、G有2个连通分量D、G肯定不是完全图正确答案：A30.将10、12、1、14、6、5、8、15、3、9、7逐个按顺序插入到初始为空的最小堆（小根堆）中，然后连续执行两次删除最小元素操作（DeleteMin），此后堆顶的元素是什么？A、5B、6C、7D、9正确答案：A31.对于一个具有N个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是：A、N2B、N−1C、ND、(N−1)2正确答案：A32.一棵树有n1个孩子数为1的结点，n2个孩子数为2的结点，……，nm个孩子数为m的结点，则该树的叶结点数为：A、1+∑i=2m(i−1)niB、1+∑i=2m(i)niC、1+∑i=1m−1(i−1)niD、∑i=2m(i−1)ni正确答案：A33.数组A[0..6,0..5]的每个元素占5个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5,5]的地址是()。A、1175B、1180C、1200D、1205正确答案：C34.线性表L在什么情况下适用于使用链式结构实现？A、L中含有大量的结点B、L中结点结构复杂C、需不断对L进行删除插入D、需经常修改L中的结点值正确答案：C35.在决定选取何种存储结构时，一般不考虑（）A、所用的编程语言实现这种结构是否方便B、结点个数的多少C、结点个数的多少D、各结点的值如何正确答案：D36.在散列表中，所谓同义词就是：A、具有相同散列地址的两个元素B、被映射到不同散列地址的一个元素C、两个意义相近的单词D、被不同散列函数映射到同一地址的两个元素正确答案：A37.对二叉搜索树进行什么遍历可以得到从小到大的排序序列？A、前序遍历B、后序遍历C、层次遍历D、中序遍历正确答案：D38.下列关于栈的叙述中，错误的是：采用非递归方式重写递归程序时必须使用栈函数调用时，系统要用栈保存必要的信息只要确定了入栈次序，即可确定出栈次序栈是一种受限的线性表，允许在其两端进行操作A、仅1B、仅1、3、4C、仅1、2、3D、仅1、3、4正确答案：B39.给定散列表大小为11，散列函数为H(Key)=Key%11。按照线性探测冲突解决策略连续插入散列值相同的4个元素。问：此时该散列表的平均不成功查找次数是多少？A、1B、21/11C、不确定D、4/11正确答案：B40.如果G是一个有28条边的非连通无向图，那么该图顶点个数最少为多少？A、9B、10C、8D、7正确答案：A41.利用大小为n的数组（下标从0到n-1）存储一个栈时，假定栈从数组另一头开始且top==n表示栈空，则向这个栈插入一个元素时，修改top指针应当执行：A、top++B、top--C、top=0D、top不变正确答案：B42.AVL树是一种平衡的二叉搜索树，树中任一结点具有下列哪一特性：A、左、右子树的高度均相同B、左、右子树高度差的绝对值不超过1C、左子树的高度均大于右子树的高度D、左子树的高度均小于右子树的高度正确答案：B43.将1,2,3,6,5,4顺序一个个插入一棵初始为空的AVL树，会经历下列哪些旋转？A、两个“右-右”旋和一个“右-左”旋B、一个“右-右”旋、一个“右-左”旋、一个“左-右”旋C、一个“右-右”旋和两个“右-左”旋D、两个“右-右”旋和一个“左-右”旋正确答案：C44.采用递归方式对顺序表进行快速排序，下列关于递归次数的叙述中，正确的是：A、每次划分后，先处理较短的分区可以减少递归次数B、递归次数与初始数据的排列次序无关C、递归次数与每次划分后得到的分区处理顺序无关D、每次划分后，先处理较长的分区可以减少递归次数正确答案：C45.对于序列{49，38，65，97，76，13，27，50}，按由小到大进行排序，下面哪一个是初始步长为4的希尔排序法第一趟的结果？A、97,76,65,50,49,38,27,13B、13,27,38,49,50,65,76,97C、49,76,65,13,27,50,97,38D、49,13,27,50,76,38,65,97正确答案：D46.一棵满二叉树中127个节点，其中叶子节点的个数是（）A、63B、64C、65D、不确定正确答案：B47.对给定序列{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正确答案：C48.给定N×N×N的三维数组A，则在不改变数组的前提下，查找最小元素的时间复杂度是：A、O(N2)B、O(NlogN)C、O(N2logN)D、O(N3)正确答案：D49.采用多项式的非零项链式存储表示法，如果两个多项式的非零项分别为N1和N2个，最高项指数分别为M1和M2，则实现两个多项式相加的时间复杂度是：A、O(N1×N2)B、O(M1+M2)C、O(M1×M2)D、O(N1+N2)正确答案：D50.已知一棵二叉树的前序遍历结果为ABCDEFG,中序遍历结果为BCAEDGF,则后序遍历的结果为（）。A、CBAEGFDB、CBEGFDAC、BCEGFDAD、CBEFGDA正确答案：B51.中位值结点在根结点或根的左子树上A、3B、1C、4D、2正确答案：D52.令P代表入栈，O代表出栈。若利用堆栈将中缀表达式3*2+8/4转为后缀表达式，则相应的堆栈操作序列是：A、PPOOPOB、PPPOOOC、POPOPOD、POPPOO正确答案：D53.若一个栈的入栈序列为1、2、3、…、N，其输出序列为p1、p2、p3、…、pN。若p1=N，则pi为：A、n−i+1B、不确定C、iD、n−i正确答案：A54.数据元素在计算机存储器内表示时，物理相对位置和逻辑相对位置相同并且是连续的，称之为（）。A、逻辑结构B、顺序存储结构C、链式存储结构D、以上都不对正确答案：B55.对一棵二叉树的结点从1开始顺序编号。要求每个结点的编号都小于其子树所有结点的编号，且左子树所有结点的编号都小于右子树所有结点的编号。可采用▁▁▁▁▁实现编号。A、后序遍历B、层次遍历C、中序遍历D、先序遍历正确答案：D56.在计算机中存储数据时，通常不仅要存储各数据元素的值，而且还要存储()。A、数据的存储方法B、数据元素之间的关系C、数据元素的类型D、数据的处理方法正确答案：B57.将下列数（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正确答案：D58.如果循环队列用大小为m的数组表示，且用队头指针front和队列元素个数size代替一般循环队列中的front和rear指针来表示队列的范围，那么这样的循环队列可以容纳的元素个数最多为：A、m+1B、m-1C、mD、不能确定正确答案：C59.设森林F中有三棵树，第一、第二、第三棵树的结点个数分别为M1，M2和M3。则与森林F对应的二叉树根结点的右子树上的结点个数是：A、M2+M3B、M1C、M1+M2D、M3正确答案：A60.对初始数据序列{8,3,9,11,2,1,4,7,5,10,6}进行希尔排序。若第一趟排序结果为（1,3,7,5,2,6,4,9,11,10,8），第二趟排序结果为（1,2,6,4,3,7,5,8,11,10,9），则两趟排序采用的增量（间隔）依次是：A、5,3B、3,1C、3,2D、5,2正确答案：A61.将两个结点数都为N且都从小到大有序的单向链表合并成一个从小到大有序的单向链表，那么可能的最少比较次数是：A、2NB、1C、ND、NlogN正确答案：C62.设我们的内存可以一次处理12个数字，且磁带上有以下两条有序段：有序段1:1,3,5,7,8,9,10,12有序段2:2,4,6,15,20,25,30,32采用2路归并，并设置4块输入缓冲区和2块输出缓冲区，以便并行操作。则下列哪三个操作是不能并行的？A、将1和2写入第三条磁带；将3和4归并到一块输出缓冲区；将6和15读入一块输入缓冲区B、将7和8写入第三条磁带；将9和15归并到一块输出缓冲区；将10和12读入一块输入缓冲区C、将3和4写入第三条磁带；将5和6归并到一块输出缓冲区；将8和9读入一块输入缓冲区D、将5和6写入第三条磁带；将7和8归并到一块输出缓冲区；将20和25读入一块输入缓冲区正确答案：B63.已知二维数组A按行优先方式存储，每个元素占用1个存储单元。若元素A[0][0]的存储地址是100，A[3][3]的存储地址是220，则元素A[5][5]的存储地址是：A、295B、300C、301D、306正确答案：B64.给定无向图G，从V0出发进行深度优先遍历访问的边集合为：{(V0,V1),(V0,V4),(V1,V2),(V1,V3),(V4,V5),(V5,V6)}。则下面哪条边不可能出现在G中？A、(V0,V2)B、(V4,V6)C、(V1,V5)D、(V0,V6)正确答案：C65.对N个记录进行快速排序，在最坏的情况下，其时间复杂度是：A、O(N2)B、O(N2logN)C、O(NlogN)D、O(N)正确答案：A66.关于图的邻接矩阵，下列哪个结论是正确的？A、无向图的邻接矩阵可以是不对称的，也可以是对称的B、无向图的邻接矩阵总是不对称的C、有向图的邻接矩阵总是不对称的D、有向图的邻接矩阵可以是对称的，也可以是不对称的正确答案：D67.任何一个带权无向连通图的最小生成树——A、有可能不存在B、是唯一的C、有可能不唯一D、是不唯一的正确答案：C68.链表不具有的特点是：A、不必事先估计存储空间B、方便随机访问任一元素C、所需空间与线性长度成正比D、插入、删除不需要移动元素正确答案：B69.一个有N个顶点的强连通图至少有多少条边？A、NB、N+1C、N−1D、N(N−1)正确答案：A70.将M个元素存入用长度为S的数组表示的散列表，则该表的装填因子为：A、M−SB、M/SC、M×SD、S+M正确答案：B71.就排序算法所用的辅助空间而言，堆排序、快速排序、归并排序的关系是：A、堆排序>归并排序>快速排序B、堆排序<归并排序<快速排序C、堆排序>快速排序>归并排序D、堆排序<快速排序<归并排序正确答案：D72.二叉树的高度若根节点为高度1，一棵具有1025个结点的二叉树的高度为▁▁▁▁▁。A、11～1025之间B、11C、10D、10～1024之间正确答案：A73.对一组包含10个元素的非递减有序序列，采用直接插入排序排成非递增序列，其可能的比较次数和移动次数分别是：A、100,54B、45,44C、100,100D、54,63正确答案：B74.下面描述中正确的为()。A、线性表的逻辑顺序与物理顺序总是一致的B、线性表的顺序存储表示优于链式存储表示。C、线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。D、二维数组是其数组元素为线性表的线性表。正确答案：C75.由分别带权为9、2、5、7的四个叶子结点构成一棵哈夫曼树，该树的带权路径长度为：A、46B、44C、23D、37正确答案：B76.给定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正确答案：B77.对最小堆（小顶堆）{1,3,2,6,7,5,4,15,14,12,9,10,11,13,8}进行三次删除最小元的操作后，结果序列为：A、4,5,6,12,7,10,8,15,14,13,9,11B、4,5,6,7,8,9,10,11,12,13,14,15C、4,6,5,12,7,10,8,15,14,9,13,11D、4,6,5,13,7,10,8,15,14,12,9,11正确答案：D78.设一棵非空完全二叉树T的所有叶节点均位于同一层，且每个非叶结点都有2个子结点。若T有k个叶结点，则T的结点总数是：A、k2B、2k−1C、2k−1D、2k正确答案：B79.程序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)正确答案：B80.创建一个初始堆，含有N个记录，其时间复杂度是：A、O(logN)B、O(N2)C、O(N)D、O(NlogN)正确答案：C81.假设我们只有2条磁带Ta和Tb用于做外部排序。假设内存可以一次处理M条记录。初始状态下Ta上存有N条记录。下列简单算法的执行步骤为：第1步：从Ta一次读入M条记录到内存，做内部排序，然后将有序的结果写到Tb。第2步：从Ta一次读入M条记录到内存，做内部排序，然后将其与Tb上存储的有序列做归并，将有序的（2M条记录）结果写到Ta。第3步：从Ta一次读入M条记录到内存，做内部排序，然后将其与Tb上存储的2M条记录的有序列做归并，将有序的（3M条记录）结果写到Tb。重复第2、3步，直到全部记录有序。上述算法需要执行__轮。A、logMNB、⌈N/M⌉C、logND、⌈log(N/M)⌉正确答案：B82.具有5个顶点的有向完全图有多少条弧？A、16B、10C、20D、25正确答案：C83.下列程序的时间复杂度为（）。i=0;s=0;while(s<n){i++;s=s+i;}A、Θ(n2)B、Θ(1)C、Θ(n)D、Θ(n½)正确答案：D84.若借助堆栈将中缀表达式a+b*c+(d*e+f)*g转换为后缀表达式，当读入f时，堆栈里的内容是什么（按堆栈自底向上顺序）？A、abcdeB、+(*+C、+(+D、++(+正确答案：C85.下列关于无向连通图特征的叙述中，正确的是：所有顶点的度之和为偶数边数大于顶点个数减1至少有一个顶点的度为1A、1和3B、1和2C、只有1D、只有2正确答案：C86.为解决计算机主机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是？A、树B、堆栈C、队列D、图正确答案：C二、多选题（共3题，每题1分，共3分）1.以下说法错误的是（）。A、哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。B、若一个二叉树的树叶是某子树的中序遍历序列中的第一个结点，则它必是该子树的后序遍历序列中的第一个结点C、已知二叉树的前序遍历和后序遍历序列并不能唯一确定这棵树，因为不知道树的根结点是哪一个。D、在前序遍历二叉树的序列中，任何结点的子树的所有结点都是直接跟在该结点之后。正确答案：AC2.根据数据元素之间的关系的不同特性，通常分为哪几类基本结构？A、树形结构B、图状结构C、线性结构D、集合正确答案：ABCD3.排序算法的稳定性下列关于顺序表的排序算法中，▁▁▁▁▁是稳定的。A、快速排序B、冒泡排序C、选择排序D、归并排序正确答案：BD三、判断题（共26题，每题1分，共26分）1.无向连通图所有顶点的度之和为偶数。A、正确B、错误正确答案：A2.N2logN和NlogN2具有相同的增长速度。A、正确B、错误正确答案：B3.一棵有124个结点的完全二叉树，其叶结点个数是确定的。A、正确B、错误正确答案：A4.若图G有环，则G不存在拓扑排序序列。A、正确B、错误正确答案：A5.存在一棵总共有2016个结点的二叉树，其中有16个结点只有一个孩子。A、正确B、