数据结构与算法考试模拟题与答案

数据结构与算法考试模拟题与答案一、单选题（共76题，每题1分，共76分）1.斐波那契数列FN的定义为：F0=0,F1=1,FN=FN−1+FN−2,N=2,3,…。用递归函数计算FN的时间复杂度是：A、O(N)B、NlogN2和NlogNC、O(logN)D、O(N!)正确答案：B2.对一棵二叉树的结点从1开始顺序编号。要求每个结点的编号大于其左子树所有结点的编号、但小于右子树中所有结点的编号。可采用▁▁▁▁▁实现编号。A、中序遍历B、后序遍历C、先序遍历D、层次遍历正确答案：A3.将键值1到15顺序插入一个初始为空的斜堆。则下列句子中哪句是错的？A、共有6个叶结点B、11是7的右孩子C、6是2的左孩子D、结果是一棵完全二叉树正确答案：A4.下列代码if(A>B){for(i=0;i<N;i++)for(j=N*N;j>i;j--)A+=B;}else{for(i=0;i<N*2;i++)for(j=N*2;j>i;j--)A+=B;}A、O(N)B、O(N2)C、O(N3)D、O(N4)正确答案：C答案解析：这段代码是一个条件语句，根据A和B的大小关系执行不同的循环。当A>B时，外层循环执行N次，内层循环每次执行N*N-i次，总共执行的次数约为N*(N*N)=N^3次；当A<=B时，外层循环执行N*2次，内层循环每次执行N*2-i次，总共执行的次数约为N*2*(N*2)=4N^2次，整体时间复杂度为O(N^3)。5.如果AVL树的深度为6（空树的深度定义为−1），则此树最少有多少个结点？A、12B、20C、33D、64正确答案：C答案解析：对于高度为\(h\)的AVL树，其最少节点数的计算公式为\(N(h)=N(h-1)+N(h-2)+1\)，其中\(N(0)=1\)，\(N(1)=2\)。通过递推计算可得：\(N(2)=N(1)+N(0)+1=2+1+1=4\)；\(N(3)=N(2)+N(1)+1=4+2+1=7\)；\(N(4)=N(3)+N(2)+1=7+4+1=12\)；\(N(5)=N(4)+N(3)+1=12+7+1=20\)；\(N(6)=N(5)+N(4)+1=20+12+1=33\)。所以深度为\(6\)的AVL树最少有\(33\)个节点。6.给定散列表大小为11，散列函数为H(Key)=Key%11。按照线性探测冲突解决策略连续插入散列值相同的5个元素。问：此时该散列表的平均不成功查找次数是多少？A、不确定B、5/11C、26/11D、1正确答案：C7.一棵高度为8的完全二叉树至少有（）叶子节点A、63B、128C、64D、127正确答案：C8.线性表若采用链式存储结构时，要求内存中可用存储单元的地址A、必须是连续的B、连续或不连续都可以C、一定是不连续的D、部分地址必须是连续的正确答案：B答案解析：链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素，这些存储单元可以是连续的，也可以是不连续的，只要通过指针将它们按逻辑关系链接起来即可。9.KMP算法下，长为n的字符串匹配长度为m的字串的时间复杂度为A、O（N）B、O（M+N）C、O(M+LOGN)D、O(N+LOGM)正确答案：B答案解析：KMP算法的时间复杂度为O(n+m)。在KMP算法中，需要对主串（长度为n）和模式串（长度为m）进行遍历比较。通过利用部分匹配表（最长相同前缀后缀长度），可以避免一些不必要的字符比较，从而使得整体时间复杂度为线性时间，即O(n+m)。所以长为n的字符串匹配长度为m的字串的时间复杂度为O(M+N)。10.一个具有1025个节点的二叉树的高h为（）A、11B、10C、11～1025D、12～1024正确答案：C答案解析：二叉树的高度与节点数的关系：对于一棵二叉树，其节点数\(n\)与高度\(h\)满足\(n\leq2^{h+1}-1\)。当\(n=1025\)时，\(2^{h+1}-1\geq1025\)，即\(2^{h+1}\geq1026\)，求解\(h\)可得\(h\geq\log_2{1026}-1\)，\(\log_2{1024}=10\)，\(\log_2{1026}>10\)，所以\(h>10\)；同时，二叉树高度最小为\(0\)（只有一个根节点时），但题目中节点数较多，所以高度至少要大于\(10\)，最大为节点数减\(1\)（单链二叉树），即\(1025-1=1024\)，所以高度\(h\)的范围是大于\(10\)到\(1025\)之间，选项C符合。11.在散列表中，所谓同义词就是：A、两个意义相近的单词B、具有相同散列地址的两个元素C、被映射到不同散列地址的一个元素D、被不同散列函数映射到同一地址的两个元素正确答案：B答案解析：同义词是指在散列表中具有相同散列地址的两个元素。当不同元素通过散列函数计算得到相同的散列值时，这些元素就互为同义词。选项A说的是单词意义，与散列表同义词概念无关；选项C中被映射到不同散列地址不符合同义词定义；选项D强调被不同散列函数映射到同一地址不准确，通常是同一散列函数下产生相同散列地址的元素才是同义词。12.数组A[0..6,0..5]的每个元素占5个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5,5]的地址是()。A、1175B、1180C、1200D、1205正确答案：C13.稀疏矩阵采用三元组存储的时候，一般需要一个行逻辑链接的顺序表，用以指出每一行的第一个非零元素在三元组中的位置。用这个顺序表的主要目的是为了___。A、节省存储空间B、更清晰表示每行元素所在位置C、加快算法运行效率D、更清晰表示每列元素所在位置正确答案：C答案解析：稀疏矩阵采用三元组存储时，虽然三元组能存储非零元素信息，但在查找某一行元素时效率较低。而行逻辑链接的顺序表可以直接指出每一行第一个非零元素在三元组中的位置，通过这个位置信息可以快速定位该行其他非零元素，大大加快了算法运行效率，例如在按行查找元素等操作时，不需要从头遍历三元组，而是直接通过该顺序表提供的位置信息快速找到对应行的起始位置进而查找该行元素。它主要目的不是节省存储空间，存储该顺序表也不是为了更清晰表示每行或每列元素所在位置，而是为了提升算法运行效率。14.从一个具有N个结点的单链表中查找其值等于X的结点时，在查找成功的情况下，需平均比较多少个结点？A、(N+1)/2B、(N−1)/2C、N/2D、N正确答案：A15.下列几组概念中，那一组不完全跟搜索引擎有关？A、分布式索引，回溯法，查询B、倒排表，阈值设置，召回率C、倒排文件索引，停用词，准确率D、词干提取，哈希散列，压缩正确答案：A16.令P代表入栈，O代表出栈。若利用堆栈将中缀表达式3*2+8/4转为后缀表达式，则相应的堆栈操作序列是：A、PPOOPOB、POPOPOC、PPPOOOD、POPPOO正确答案：D17.两个有相同键值的元素具有不同的散列地址A、有万分之一的可能会B、一定不会C、一定会D、可能会正确答案：D答案解析：在散列函数设计不合理或发生冲突处理不当等情况下，两个有相同键值的元素可能会具有不同的散列地址。比如散列函数的取值范围有限，或者在处理冲突时采用的方法导致了这种情况出现。18.对n个互不相同的符号进行哈夫曼编码。若生成的哈夫曼树共有115个结点，则n的值是：A、56B、57C、58D、60正确答案：C答案解析：1.首先要知道哈夫曼树中只有度为0和度为2的结点。-设度为0的结点（即叶子结点，也就是符号个数）有n个，度为2的结点有m个。-根据树的性质，树中结点总数\(N=n+m\)。-又因为树的边数\(E\)满足\(E=n\times0+m\times2\)（度为0的结点无出边，度为2的结点有2条出边），且树中边数\(E=N-1\)。2.已知生成的哈夫曼树共有\(115\)个结点，即\(N=115\)，所以\(n+m=115\)，那么\(m=115-n\)。-又因为\(E=N-1=114\)，且\(E=2m\)，所以\(2m=114\)，即\(m=57\)。3.把\(m=57\)代入\(m=115-n\)，可得：-\(57=115-n\)。-解得\(n=115-57=58\)。-因为\(n\)是互不相同的符号个数，也就是叶子结点个数，叶子结点个数一定大于度为2的结点个数，而度为2的结点个数为57，所以\(n>57\)，即\(n>58\)（因为\(n\)为整数且要满足大于度为2的结点个数）。所以\(n\)的值大于\(58\)，答案选C。19.设有一组关键字{29，01，13，15，56，20，87，27，69，9，10，74}，散列函数为H(key)=key%17，采用线性探测方法解决冲突。试在0到18的散列地址空间中对该关键字序列构造散列表，则成功查找的平均查找长度为__A、1.17B、1.25C、1.33D、0.33正确答案：C答案解析：1.首先计算每个关键字的散列地址：-\(H(29)=29\%17=12\)-\(H(01)=1\%17=1\)-\(H(13)=13\%17=13\)-\(H(15)=15\%17=15\)-\(H(56)=56\%17=5\)-\(H(20)=20\%17=3\)-\(H(87)=87\%17=2\)-\(H(27)=27\%17=10\)-\(H(69)=69\%17=1\)，冲突，线性探测后存放在\(2\)-\(H(9)=9\%17=9\)-\(H(10)=10\%17=10\)，冲突，线性探测后存放在\(11\)-\(H(74)=74\%17=6\)2.然后计算每个关键字的查找长度：-关键字\(29\)，查找长度为\(1\)-关键字\(01\)，查找长度为\(1\)-关键字\(13\)，查找长度为\(1\)-关键字\(15\)，查找长度为\(1\)-关键字\(56\)，查找长度为\(1\)-关键字\(20\)，查找长度为\(1\)-关键字\(87\)，查找长度为\(1\)-关键字\(27\)，查找长度为\(1\)-关键字\(69\)，第一次冲突，查找长度为\(2\)-关键字\(9\)，查找长度为\(1\)-关键字\(10\)，第一次冲突，查找长度为\(2\)-关键字\(74\)，查找长度为\(1\)3.最后计算平均查找长度：-平均查找长度\(ASL=(1+1+1+1+1+1+1+1+2+1+2+1)/12=16/12\approx1.33\)所以成功查找的平均查找长度大于\(1.33\)，答案选[D、]>1.3320.下面四种排序算法中，稳定的算法是：A、快速排序B、堆排序C、归并排序D、希尔排序正确答案：C答案解析：归并排序是稳定的排序算法。在归并排序中，合并两个有序子数组时，相等的元素会按照原来的顺序依次放入新数组中，不会改变相同元素之间的相对顺序。而堆排序、希尔排序和快速排序都不是稳定的排序算法。堆排序在调整堆的过程中可能会改变相同元素的相对顺序；希尔排序是基于插入排序的改进，在分组插入过程中会破坏稳定性；快速排序在选择基准元素并划分区间时，也可能导致相同元素相对顺序改变。21.对二叉搜索树进行什么遍历可以得到从小到大的排序序列？A、层次遍历B、中序遍历C、后序遍历D、前序遍历正确答案：B答案解析：二叉搜索树的特点是左子树所有节点的值小于根节点的值，右子树所有节点的值大于根节点的值。中序遍历的顺序是先遍历左子树，再访问根节点，最后遍历右子树。因此，对二叉搜索树进行中序遍历可以得到从小到大的排序序列。前序遍历是先访问根节点，再遍历左子树和右子树；后序遍历是先遍历左子树和右子树，最后访问根节点；层次遍历是按照层次依次访问节点，它们都不能直接得到从小到大的排序序列。22.一棵度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T的叶子结点个数是()。A、41B、82C、113D、122正确答案：B答案解析：首先，根据树的性质，树中结点的度之和等于树中边的数量，而树中边的数量又比结点总数少\(1\)。设叶子结点个数为\(x\)。已知有\(20\)个度为\(4\)的结点，\(10\)个度为\(3\)的结点，\(1\)个度为\(2\)的结点，\(10\)个度为\(1\)的结点。那么度之和为\(20\times4+10\times3+1\times2+10\times1=80+30+2+10=122\)。所以边的数量为\(122\)，结点总数为\(122+1=123\)。则\(x=123-20-10-1-10=82\)，即叶子结点个数是\(82\)。23.给定散列表大小为11，散列函数为H(Key)=Key%11。采用平方探测法处理冲突：hi(k)=(H(k)±i2)%11将关键字序列{6，25，39，61}依次插入到散列表中。那么元素61存放在散列表中的位置是：A、6B、7C、8D、5正确答案：D24.设一棵非空完全二叉树T的所有叶节点均位于同一层，且每个非叶结点都有2个子结点。若T有k个叶结点，则T的结点总数是：A、k2B、2k−1C、2kD、2k−1正确答案：D答案解析：1.首先设完全二叉树的高度为\(h\)。-因为所有叶节点均位于同一层，所以叶节点所在层为第\(h\)层。-又因为每个非叶结点都有\(2\)个子结点，所以第\(h-1\)层是满二叉树。2.对于高度为\(h\)的满二叉树，其节点数为\(2^{h}-1\)。-而第\(h\)层的节点数为\(2^{h-1}\)，已知叶节点数\(k=2^{h-1}\)。3.那么这棵完全二叉树的节点总数\(N\)为：-第\(h-1\)层满二叉树的节点数加上第\(h\)层的叶节点数，即\(N=2^{h-1}+2^{h-1}=2\times2^{h-1}-1\)。-由\(k=2^{h-1}\)，可得\(N=2k-1\)。-但是题目说这棵树是非空完全二叉树，所以节点总数一定大于\(2k-1\)。所以答案是A。25.若用平方探测法解决冲突，则插入新元素时，以下陈述正确的是A、插入一定不能成功B、插入一定可以成功C、插入不一定能成功D、若散列表容量为质数，插入就一定可以成功正确答案：C答案解析：平方探测法在插入元素时，可能会出现探测序列形成循环的情况，导致无法找到合适的空位来插入新元素，所以插入不一定能成功。26.若top为指向栈顶元素的指针，判定栈S（最多容纳m个元素）为空的条件是：A、S->top==0B、S->top==-1C、S->top!=m-1D、S->top==m-1正确答案：B答案解析：栈的初始状态下，栈顶指针top的值通常被设置为-1，表示栈为空。当元素入栈时，top的值会增加；当元素出栈时，top的值会减少。所以当S->top==-1时，栈为空。27.一棵非空二叉树，若后序遍历与中序遍历的序列相同，则该二叉树▁▁▁▁▁。A、所有结点均无左孩子B、所有结点均无右孩子C、只有一个叶子结点D、为任意二叉树正确答案：C答案解析：后序遍历是先左子树、再右子树、最后根节点；中序遍历是先左子树、再根节点、最后右子树。若后序遍历与中序遍历序列相同，说明该二叉树没有左子树，只有右子树，并且一直递归下去，最后只有一个叶子结点。例如：若二叉树只有一个右孩子的单支树，它的后序遍历和中序遍历序列是相同的，都是先访问左子树（这里无左子树），然后访问右子树，最后访问根节点，这种情况下整棵树就只有一个叶子结点。28.若将n个顶点e条弧的有向图采用邻接表存储，则拓扑排序算法的时间复杂度是：A、O(n)B、O(n+e)C、O(n2)D、O(n×e)正确答案：B答案解析：拓扑排序算法的时间复杂度主要取决于邻接表的遍历。在采用邻接表存储的有向图中，拓扑排序需要遍历每个顶点和每条弧。对于n个顶点e条弧的有向图，遍历顶点的时间复杂度为O(n)，遍历弧的时间复杂度为O(e)，所以总的时间复杂度是O(n+e)。29.在一个不带头结点的非空链式队列中,假设f和r分别为队头和队尾指针,则插入s所指的结点运算是()。A、f->next=s;f=s;B、r->next=s;r=s;C、s->next=s;r=s;D、s->next=f;f=s;正确答案：B答案解析：对于不带头结点的非空链式队列，插入操作是在队尾进行。首先将新节点s的next指针指向当前队尾节点r的next，即r->next=s，然后将队尾指针r指向新节点s，即r=s。选项A是在队头插入，不符合要求；选项C逻辑错误；选项D也是在队头插入，不符合在队尾插入的操作。30.下列函数中，哪两个函数具有相同的增长速度：A、2N和NNB、N2logN和NlogN2C、NlogN2和NlogND、N和2/N正确答案：C31.采用递归方式对顺序表进行快速排序，下列关于递归次数的叙述中，正确的是：A、每次划分后，先处理较长的分区可以减少递归次数B、每次划分后，先处理较短的分区可以减少递归次数C、递归次数与每次划分后得到的分区处理顺序无关D、递归次数与初始数据的排列次序无关正确答案：C答案解析：快速排序的递归次数取决于递归树的深度，而递归树的深度主要由每次划分后两个分区的长度差异决定。每次划分都是将数组分为两个子数组，无论先处理哪个分区，最终递归树的深度是固定的，即递归次数与每次划分后得到的分区处理顺序无关。对于选项A和B，先处理较长或较短的分区并不能改变递归树的深度，所以不能减少递归次数。选项D，初始数据的排列次序会影响每次划分的结果，进而影响递归树的深度，也就是影响递归次数。32.由分别带权为9、2、5、7的四个叶子结点构成一棵哈夫曼树，该树的带权路径长度为：A、23B、37C、44D、46正确答案：C答案解析：首先构建哈夫曼树，将权值9、2、5、7的叶子节点构建哈夫曼树的过程如下：先选取权值最小的2和5构建一个新节点，其权值为7；然后再将7与7构建一个新节点，权值为14；最后将9与14构建一个新节点，权值为23。该哈夫曼树的带权路径长度为(2+5)×3+7×2+9×1=44。所以答案是C。33.设有100个元素的有序序列，如果用二分插入排序再插入一个元素，则最大比较次数是：A、50B、25C、10D、7正确答案：D34.用S表示入栈操作，X表示出栈操作，若元素入栈的顺序为1234，为了得到1342出栈顺序，相应的S和X的操作串为()。A、SSSSXXXXB、SXSXSXSXC、SXSSSXXXD、SXSSXSXX正确答案：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)正确答案：B答案解析：对于程序P1：设\(N=2^k\)，则\(T(2^k)=T(2^{k-1})+1\)。依次类推可得\(T(2^k)=k+T(1)\)，因为\(k=\log_2N\)，所以\(T(N)=\log_2N+1\)，时间复杂度为\(O(\logN)\)。对于程序P2：设\(N=2^k\)，则\(T(2^k)=2T(2^{k-1})+1\)。通过迭代可得\(T(2^k)=2^k-1+T(1)\)，即\(T(N)=N-1\)，时间复杂度为\(O(N)\)。36.在N个结点的顺序表中，算法的时间复杂度为O(1)的操作是：A、访问第i个结点（1≤i≤N）和求第i个结点的直接前驱（2≤i≤N）B、在第i个结点后插入一个新结点（1≤i≤N）C、删除第i个结点（1≤i≤N）D、将N个结点从小到大排序正确答案：A答案解析：对于顺序表，访问第i个结点可以直接通过数组下标直接计算得到存储位置，时间复杂度为O(1)。求第i个结点的直接前驱（2≤i≤N），可以通过顺序表的存储结构直接得到，时间复杂度也为O(1)。在第i个结点后插入一个新结点（1≤i≤N），需要移动大量元素，时间复杂度为O(N)。删除第i个结点（1≤i≤N），同样需要移动大量元素，时间复杂度为O(N)。将N个结点从小到大排序，一般排序算法的时间复杂度都大于O(1)，如快速排序平均时间复杂度为O(nlogn)。所以答案是A。37.树最适合于用来表示A、无序数据元素B、有序数据元素C、元素之间具有分支层次关系的数据D、元素之间无联系的数据正确答案：C答案解析：树是一种非线性数据结构，它的每个节点可以有多个子节点，这种结构非常适合用来表示元素之间具有分支层次关系的数据。例如家族树、文件目录结构等都是典型的具有分支层次关系的数据，用树来表示非常直观和方便。而有序数据元素可以用数组或链表等线性结构来表示；无序数据元素同样可以用合适的线性结构表示；元素之间无联系的数据不适合用树来表示，树强调元素之间的层次关系。38.对N个记录进行堆排序，需要的额外空间为：A、O(1)B、O(logN)C、O(N)D、O(NlogN)正确答案：A答案解析：堆排序是一种原地排序算法，它在排序过程中只需要常数级别的额外空间，即O(1)。在堆排序过程中，通过不断调整堆结构来进行排序，不需要额外开辟与记录数N相关的大量空间。所以对N个记录进行堆排序，需要的额外空间为O(1)，答案选A。39.设有1000个元素的有序序列，如果用二分插入排序再插入一个元素，则最大比较次数是：A、999B、500C、10D、1000正确答案：C40.二叉树中第5层（根的层号为1）上的结点个数最多为：A、8B、15C、16D、32正确答案：C答案解析：二叉树中第\(n\)层上的结点个数最多为\(2^{n-1}\)。当\(n=5\)时，\(2^{5-1}=2^4=16\)，所以二叉树中第5层上的结点个数最多为16。41.栈和队列的共同点是（）。A、都是先进先出B、都是先进后出C、只允许在端点处插入和删除元素D、没有共同点正确答案：C答案解析：栈和队列都是操作受限的线性表，栈只能在栈顶进行插入和删除操作，队列只能在队头删除元素，在队尾插入元素，它们都只允许在端点处插入和删除元素。选项A中先进先出是队列的特点；选项B中先进后出是栈的特点；所以栈和队列是有共同点的，选项D错误。42.下列关于栈的叙述中，错误的是：采用非递归方式重写递归程序时必须使用栈函数调用时，系统要用栈保存必要的信息只要确定了入栈次序，即可确定出栈次序栈是一种受限的线性表，允许在其两端进行操作A、仅1、2、3B、仅1、3、4C、仅1、3、4D、仅1正确答案：C43.循环队列的队满条件为()。A、(sq.rear+1)%maxsize==(sq.front+1)%maxsizeB、(sq.front+1)%maxsize==sq.rearC、(sq.rear+1)%maxsize==sq.frontD、sq.rear==sq.front正确答案：C答案解析：循环队列队满的条件是队尾指针在循环意义下加1后等于队头指针，即(sq.rear+1)%maxsize==sq.front。A选项中(sq.rear+1)%maxsize==(sq.front+1)%maxsize是错误的；B选项(sq.front+1)%maxsize==sq.rear是队空的条件；D选项sq.rear==sq.front只是队空的一种情况，不是队满条件。44.给定一个堆栈的入栈序列为{1,2,⋯,n}，出栈序列为{p1,p2,⋯,pn}。如果p2=n，则存在多少种不同的出栈序列？A、1B、2C、n−1D、n正确答案：C答案解析：当\(p2=n\)时，意味着\(n\)是第二个出栈的元素。那么在\(n\)入栈之前，必须有一个元素先入栈，且这个元素在\(n\)入栈之后紧接着就出栈了，所以第一个出栈的元素有\(n-1\)种可能（可以是\(1\)到\(n-1\)中的任意一个）。而对于剩下的\(n-2\)个元素，它们的出栈顺序是一个标准的\(n-2\)个元素的堆栈出栈序列问题。根据卡特兰数公式\(C(n)=\frac{1}{n+1}C_{2n}^n\)，这里\(n\)变为\(n-2\)，其出栈序列的种类数是固定的。所以总的出栈序列数为\(n-1\)种。因此，存在\(n-1\)种不同的出栈序列，答案选C。45.利用大小为n的数组（下标从0到n-1）存储一个栈时，假定栈从数组另一头开始且top==n表示栈空，则向这个栈插入一个元素时，修改top指针应当执行：A、top=0B、top++C、top--D、top不变正确答案：C答案解析：栈从数组另一头开始且top==n表示栈空，插入元素时栈顶位置应该减小，所以执行top--。46.对N个不同的数据采用冒泡算法进行从大到小的排序，下面哪种情况下肯定交换元素次数最多？A、元素基本有序B、从小到大排好的C、元素无序D、从大到小排好的正确答案：B47.将一系列数字顺序一个个插入一棵初始为空的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正确答案：D48.将10、12、1、14、6、5、8、15、3、9、7逐个按顺序插入到初始为空的最小堆（小根堆）中，然后连续执行两次删除最小元素操作（DeleteMin），此后堆顶的元素是什么？A、5B、6C、7D、9正确答案：A49.若结点p与q在二叉树T的中序遍历序列中相邻，且p在q之前，则下列p与q的关系中，不可能的是I.q是p的双亲II.q是p的右孩子III.q是p的右兄弟IV.q是p的双亲的双亲A、仅II、IVB、仅IC、仅IIID、仅II、III正确答案：C答案解析：1.首先分析选项I：-若q是p的双亲，在中序遍历中，双亲节点会在其左子树节点之后被访问，所以p和q不可能在中序遍历序列中相邻且p在q之前，该选项不可能。2.接着看选项II：-若q是p的右孩子，那么在中序遍历中，p会先被访问，然后是p的左子树节点，最后才是q，所以p和q可能在中序遍历序列中相邻且p在q之前，该选项可能。3.再看选项III：-二叉树节点之间的兄弟关系与中序遍历顺序无关，因为中序遍历是按照左子树、根节点、右子树的顺序访问，所以q是p的右兄弟不影响中序遍历中p和q的相邻顺序，该选项可能。4.最后看选项IV：-若q是p的双亲的双亲，那么在中序遍历中，q会在p之前被访问，不符合p在q之前的条件，该选项不可能。-所以不可能的是选项I和IV，而选项III是可能的，答案选B。50.下列程序的时间复杂度为（）。i=0;s=0;while(s<n){i++;s=s+i;}A、Θ(n½)B、Θ(1)C、Θ(n)D、Θ(n2)正确答案：A答案解析：首先分析循环条件，每次循环s的值增加i，i从1开始每次加1。设循环执行了k次结束，此时s的值为1+2+3+...+k。根据等差数列求和公式，s=k(k+1)/2。当s>=n时循环结束，即k(k+1)/2>=n，解这个不等式得到k的量级是Θ(n½)，所以程序的时间复杂度为Θ(n½)，答案选A。51.将M个元素存入用长度为S的数组表示的散列表，则该表的装填因子为：A、S+MB、M−SC、M×SD、M/S正确答案：D答案解析：装填因子的定义是散列表中已存入元素的个数与散列表长度的比值。题目中已存入元素个数为M，散列表长度为S，所以装填因子为M/S。52.具有5个顶点的有向完全图有多少条弧？A、10B、16C、20D、25正确答案：C答案解析：有向完全图的弧数公式为\(n(n-1)\)，\(n\)为顶点数。对于具有\(5\)个顶点的有向完全图，弧数为\(5\times(5-1)=20\)条。所以答案选[C、]>20。53.对于一个具有N个结点的单链表，在给定值为x的结点后插入一个新结点的时间复杂度为A、O(1)B、O(N/2)C、O(N)D、O(N2)正确答案：C答案解析：首先要在单链表中找到值为x的结点，这需要遍历链表，平均情况下时间复杂度为O(N)。找到该结点后，在其后面插入新结点的操作时间复杂度为O(1)。所以总的时间复杂度取决于查找的过程，为O(N)。54.被计算机加工的数据元素不是孤立的，它们彼此之间一般存在某种关系，通常把数据元素之间的这种关系称为A、结构B、集合C、规则D、运算正确答案：A答案解析：数据元素之间的关系称为结构。结构描述了数据元素之间的逻辑关系，它决定了数据的组织方式和访问方式等。规则通常是关于行为、操作等方面的规定；集合是具有某种特定性质的具体的或抽象的对象汇总成的集体；运算则是对数据进行的操作。所以数据元素之间的关系用结构来描述更为合适。55.设有一个12×12的对称矩阵M，将其上三角部分的元素mi,j（1≤i≤j≤12）按行优先存入C语言的一维数组N中，元素m6,6在N中的下标是：A、50B、51C、55D、66正确答案：A56.下面描述中正确的为()。A、线性表的逻辑顺序与物理顺序总是一致的B、线性表的顺序存储表示优于链式存储表示。C、线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。D、二维数组是其数组元素为线性表的线性表。正确答案：C57.下面说法中哪个是错误的：A、任何AVL树的中序遍历结果是有序的（从小到大）B、任何最小堆的前序遍历结果是有序的（从小到大）C、任何搜索树中同一层的结点从左到右是有序的（从小到大）D、任何最小堆中从根结点到任一叶结点路径上的所有结点是有序的（从小到大）正确答案：B答案解析：最小堆的前序遍历结果并不一定是有序的（从小到大）。前序遍历是先访问根节点，再递归访问左子树和右子树，它不会保证得到从小到大的有序序列。而AVL树中序遍历结果是有序的（从小到大）；搜索树中同一层的结点从左到右是有序的（从小到大）；最小堆中从根结点到任一叶结点路径上的所有结点是有序的（从小到大）。58.数据元素在计算机存储器内表示时，物理相对位置和逻辑相对位置相同并且是连续的，称之为（）。A、逻辑结构B、顺序存储结构C、链式存储结构D、以上都不对正确答案：B答案解析：顺序存储结构是把数据元素存放在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的，并且数据元素在存储器内是连续存放的，符合题目描述。而逻辑结构是数据元素之间的逻辑关系，与物理存储位置无关；链式存储结构中数据元素的存储位置是任意的，不要求连续。59.设h为不带头结点的单向链表。在h的头上插入一个新结点t的语句是：A、h=t;t->next=h;B、h=t;t->next=h->next;C、t->next=h;h=t;D、t->next=h->next;h=t;正确答案：C答案解析：1.首先分析选项D：-语句“t->next=h;”的作用是将新节点t的next指针指向原来链表的头节点h。-语句“h=t;”的作用是将头指针h指向新插入的节点t，这样就完成了在链表头部插入新节点的操作。2.再看选项A：-先执行“h=t;”，此时头指针h指向新节点t。-再执行“t->next=h->next;”，因为h已经指向t，这里的h->next是原来链表的头节点，这一步会导致新节点t的next指向原来链表的头节点，然后h又指向t，相当于没有完成在头部插入新节点的正确逻辑，应该是先让新节点指向原来的头节点，再让头指针指向新节点。3.看选项B：-先执行“t->next=h->next;”，这一步使得新节点t的next指向原来链表的第二个节点（如果有）。-再执行“h=t;”，此时头指针h指向新节点t，但是新节点的next并没有正确指向原来的头节点，不符合在头部插入新节点的逻辑。4.看选项C：-先执行“h=t;”，头指针h指向新节点t。-再执行“t->next=h;”，这会导致新节点t形成一个自环，即t的next指向自己，而不是指向原来链表的头节点，不符合在头部插入新节点的要求。60.二叉树的形态由3个结点可以构造出▁▁▁▁▁种不同形态的二叉树。A、5B、4C、2D、3正确答案：A61.已知一个长度为16的顺序表L，其元素按关键字有序排列。若采用二分查找法查找一个L中不存在的元素，则关键字的比较次数最多是：A、7B、6C、5D、4正确答案：C答案解析：二分查找每次比较都将查找区间缩小一半。对于长度为16的有序顺序表，第一次比较在中间位置（第8个元素），若未找到继续在另一半查找。最坏情况下，查找过程如下：第一次在第8个元素比较，第二次在第4或第12个元素比较，第三次在第2或第6或第10或第14个元素比较，第四次在第1或第3或第5或第7或第9或第11或第13或第15个元素比较，第五次会超出边界（因为不存在该元素，继续比较下去会超出表的范围），所以最多比较5次。62.现有长度为7、初始为空的散列表HT，散列函数H(k)=k%7，用线性探测再散列法解决冲突。将关键字22,43,15依次插入到HT后，查找成功的平均查找长度是：A、3B、1.5C、1.6D、2正确答案：D答案解析：1.首先插入关键字22：-计算散列地址：\(H(22)=22\%7=1\)，此时\(HT[1]\)为空，所以\(22\)插入到\(HT[1]\)。2.接着插入关键字43：-计算散列地址：\(H(43)=43\%7=1\)，此时\(HT[1]\)已被\(22\)占用，发生冲突。-采用线性探测再散列法，计算下一个地址：\(H_1=(1+1)\%7=2\)，\(HT[2]\)为空，所以\(43\)插入到\(HT[2]\)。3.然后插入关键字15：-计算散列地址：\(H(15)=15\%7=1\)，\(HT[1]\)被占用。-计算下一个地址：\(H_1=(1+1)\%7=2\)，\(HT[2]\)被占用。-计算下一个地址：\(H_2=(1+2)\%7=3\)，\(HT[3]\)为空，所以\(15\)插入到\(HT[3]\)。4.计算查找成功的平均查找长度：-查找22时，比较1次就找到，查找长度为1。-查找43时，比较2次找到，查找长度为2。-查找15时，比较3次找到，查找长度为3。-平均查找长度\(ASL=(1+2+3)/3=2\)。所以查找成功的平均查找长度大于2，答案选[C]。63.在决定选取何种存储结构时，一般不考虑（）A、结点个数的多少B、各结点的值如何C、结点个数的多少D、所用的编程语言实现这种结构是否方便正确答案：B答案解析：存储结构的选取主要考虑存储数据的特点（如数据量大小、数据之间的关系等）、运算需求以及实现的便利性等。各结点的值如何并不直接影响存储结构的选取，而结点个数的多少会影响存储结构的选择，如数据量较大时可能更适合采用链式存储结构；运算需求也很关键，不同的运算对存储结构有不同要求；所用编程语言实现这种结构是否方便也是需要考虑的因素。所以一般不考虑各结点的值如何。64.在有n（>1）个元素的最大堆（大根堆）中，最小元的数组下标可以是：A、⌊n/2⌋−1B、1C、⌊n/2⌋+2D、⌊n/2⌋正确答案：C65.给定N×N×N的三维数组A，则在不改变数组的前提下，查找最小元素的时间复杂度是：A、O(N2)B、O(NlogN)C、O(N2logN)D、O(N3)正确答案：D答案解析：要在不改变数组的前提下查找N×N×N三维数组A中的最小元素，需要遍历整个三维数组，其元素个数为N×N×N=N³，所以时间复杂度为O(N³)。66.设一个堆栈的入栈顺序是1、2、3、4、5。若第一个出栈的元素是4，则最后一个出栈的元素必定是：A、3B、5C、1D、1或者5正确答案：D67.若已知一队列用单向链表表示，该单向链表的当前状态（含3个对象）是：1->2->3，其中x->y表示x的下一节点是y。此时，如果将对象4入队，然后队列头的对象出队，则单向链表的状态是：A、1->2->3B、2->3->4C、4->1->2D、答案不唯一正确答案：B答案解析：1.首先分析入队操作：-入队是在链表尾部添加元素。当对象4入队时，原来的链表1->2->3，在3的后面添加4，此时链表变为1->2->3->4。2.然后分析出队操作：-出队是删除队列头的元素。队列头是1，删除1后，链表变为2->3->4。所以单向链表的状态是2->3->4，答案选B。68.采用多项式的非零项链式存储表示法，如果两个多项式的非零项分别为N1和N2个，最高项指数分别为M1和M2，则实现两个多项式相加的时间复杂度是：A、O(N1+N2)B、O(M1×M2)C、O(N1×N2)D、O(M1+M2)正确答案：A69.若二叉搜索树是有N个结点的完全二叉树，则不正确的说法是：A、所有结点的平均查找效率是O(logN)B、最小值一定在叶结点上C、最大值一定在叶结点上D、中位值结点在根结点或根的左子树上正确答案：C70.Forthefollowingpieceofcodefor(i=0;i<n;i++)for(j=i;j>0;j/=2)printf(“%d\n”,j);thetimecomplexityis:A、O(N2)B、O(N×i)C、O(NlogN)D、O(N)正确答案：C71.创建一个初始堆，含有N个记录，其时间复杂度是：A、O(logN)B、O(N)C、O(NlogN)D、O(N2)正确答案：B答案解析：创建一个初始堆，含有N个记录，其时间复杂度是O(N)。因为在创建初始堆时，需要从最后一个非叶子节点开始，依次对每个节点进行调整操作，使其满足堆的性质。每个节点的调整操作时间复杂度为O(logN)，而总的节点数为N，但是只需要对大约N/2个非叶子节点进行调整，所以总体时间复杂度为O(N)。72.在单链表中，若p所指的结点不是最后结点，在p之后插入s所指结点，则执行A、p->next=s;s->next=p;B、s->next=p->next;p=s;C、s->next=p;p->next=s;D、s->next=p->next;p->next=s;正确答案：D73.若AVL树的深度是6（空树的深度定义为-1），则该树的最少结点数是：A、13B、17C、20D、33正确答案：D74.对于给定的有权无向图G，下列哪个说法是正确的？A、G的最小生成树中，任意一对顶点间的路径必是它们在G中的最短路径B、设顶点V到W的最短路径为P。若我们将G中每条边的权重都加1，则P一定仍然是V到W的最短路径C、单源最短路问题可以用O(∣E∣+∣V∣)的时间解决D、以上都不对正确答案：D答案解析：1.对于选项A：-最小生成树中任意一对顶点间的路径不一定是它们在G中的最短路径。例如，在一个带权无向图中，最小生成树的边构成的路径可能会因为最小生成树的构造方式而不是最短路径。最小生成树主要关注的是连接所有顶点且总权值最小，而不是路径的最短性。2.对于选项B：-当将G中每条边的权重都加1时，原来顶点V到W的最短路径P不一定仍然是最短路径。因为最短路径是基于边的权重计算的，权重增加后，可能会有其他路径成为更短的路径。3.对于选项C：-单源最短路问题如果使用Dijkstra算法，时间复杂度是\(O((|V|+|E|)\log|V|)\)，只有使用一些特殊的数据结构（如斐波那契堆）优化后的Dijkstra算法时间复杂度才是\(O(|E|+|V|\log|V|)\)，而Bellman-Ford算法时间复杂度是\(O(|V||E|)\)，所以说单源最短路问题可以用\(O(|E|+|V|)\)的时间解决是错误的。所以以上选项都不对，答案是D。75.如果A和B都是二叉树的叶结点，那么下面判断中哪个是对的？A、存在一种二叉树结构，其前序遍历结果是…A…B…，而中序遍历结果是…B…A…B、存在一种二叉树结构，其中序遍历结果是…A…B…，而后序遍历结果是…B…A…C、存在一种二叉树结构，其前序遍历结果是…A…B…，而后序遍历结果是…B…A…D、以上三种都是错的正确答案：D答案解析：前序遍历是根左右，中序遍历是左根右，后序遍历是左右根。对于叶节点A和B，若前序遍历结果是…A…B…，那么A是根节点或者A的父节点是根节点，若中序遍历结果是…B…A…，那么B是根节点或者B的父节点是根节点，二者矛盾，所以A选项错误；同理，若中序遍历结果是…A…B…，而后序遍历结果是…B…A…，也会产生矛盾，B选项错误；若前序遍历结果是…A…B…，而后序遍历结果是…B…A…，同样会产生矛盾，C选项错误。所以以上三种都是错的，选D。76.设最小堆（小根堆）的层序遍历结果为{1,3,2,5,4,7,6}。用线性时间复杂度的算法将该堆调整为最大堆（大根堆），则该树的中序遍历结果为：A、4,1,3,7,6,2,5B、3,5,4,7,2,6,1C、1,4,3,7,2,6,5D、3,5,4,2,6,1,7正确答案：B答案解析：首先，已知最小堆的层序遍历结果为{1,3,2,5,4,7,6}，对应的最小堆结构为：1/\32/\/\5476要将其调整为最大堆，从最后一个非叶子节点开始调整。最后一个非叶子节点是2，它有两个子节点5和4，由于5大于4，所以不需要调整。接着看节点3，它有两个子节点5和2，由于5大于2，需要交换3和5，得到：5/\32/\/\1476再看节点1，它有两个子节点3和2，由于3大于2，需要交换1和3，得到：5/\32/\/\1476继续调整，节点3有子节点1和4，不需要调整。此时最大堆结构为：5/\32/\/\1476最大堆的中序遍历结果为：3,5,4,7,2,6,1。所以答案选C。二、多选题（共3题，每题1分，共3分）1.根据数据元素之间的关系的不同特性，通常分为哪几类基本结构？A、集合B、树形结构C、图状结构D、线性结构正确答案：ABCD答案解析：集合是数据元素之间除了“同属于一