数据结构智慧树知到期末考试答案2024年

数据结构智慧树知到期末考试答案2024年数据结构设某棵二叉树中有2000个结点，则该二叉树的最小高度为（）。

A:11B:12C:9D:10答案:11下面算法时间复杂度最小的是（）。

A:冒泡排序B:直接插入排序C:快速排序D:简单选择排序答案:快速排序在一棵二叉排序树上按（）遍历得到的结点序列是一个有序序列。

A:中序B:先序C:后序D:层次答案:中序某二叉树结点中序序列为BDAECF，后序序列为DBEFCA，则该二叉树对应的森林包括（）棵树。

A:4B:1C:2D:3答案:3二维数组A[10][20]采用列序为主方式存储，每个元素占1个存储单元，并且A[0][0]的存储地址是200，则A[6][12]的地址是（）。

A:326B:256C:314D:288答案:326设有5000个待排序的记录关键字，如果需要用最快的方法选出其中最小的10个记录关键字，则用下列（）方法可以达到此目的。

A:快速排序B:归并排序C:堆排序D:插入排序答案:堆排序在长度为n的顺序表中，要删除第i（1≦i≦n）个元素时，则需要向前移动元素的个数为（）。

A:iB:n-iC:n-i-1D:n-i+1答案:n-i在单链表L中，指针p所指结点有后继结点的条件是（）。

A:p-＞next!=nullB:p=p-＞nextC:p-＞next=nullD:p-＞next=p-＞next.Next答案:p.next!=null判定一个环形队列qu（最多元素为MaxSize）为空的条件是（）。

A:qu-＞rear-qu-＞front==MaxSizeB:qu-＞front==qu-＞rear+1C:qu-＞front==qu-＞rearD:qu-＞rear-qu-＞front-1==MaxSize答案:qu-＞front==qu-＞rear设一棵m叉树中度数为0的结点数为N0，度数为1的结点数为Nl，……，度数为m的结点数为Nm，则N0=（）。

A:2Nl+3N2+……+(m+1)NmB:N2+2N3+3N4+……+(m-1)NmC:l+N2+2N3+3N4+……+(m-1)NmD:Nl+N2+……+Nm答案:l+N2+2N3+3N4+……+(m-1)Nm某程序的时间复杂度为（3n+nlog2n+n^2+8），其数量级表示为（）。

A:O(log2n)B:O(n)C:O(n^2)D:O(nlog2n)答案:O(n^2)设非空单链表的数据域为data，指针域为next，指针p指向单链表中第i个结点，s指向已生成的新结点，现将s结点插入到单链表中，使其成为第i+1个结点，下列算法段能正确完成上述要求的是（）。

A:s-＞next-＞p-＞next;p-＞next=sB:p=s;s-＞next=pC:p-＞next=s;s-＞next=p-＞next;D:s-＞next=p-＞next;p-＞next=s;答案:s-＞next-＞p-＞next;p-＞next=s在查找过程中，若同时还要增、删工作，这种查找称为（）。

A:静态查找B:外查找C:动态查找D:内查找答案:动态查找已知有序查找表（4,6,10,12,20,30,50,70,88,100）。若查找56，则需依次与查找表中（）进行比较，直到查找失败。

A:20,70,30,50B:30,88,50C:20,50D:30,88,70,50答案:20,70,30,50若串S=’software’，其子串的数目是（）。

A:36B:9C:37D:8答案:37设数组A行下标i从1到8，列下标j从1到10，每个元素占3个字节，首地址为SA则该数组按行存放时，元素A[8][5]的起始地址为（）。

A:SA+255B:SA+222C:SA+144D:SA+278答案:SA+222设串s1=”DataStructureswith”，s2=”it”，则子串定位函数index的值为（）。

A:18B:15C:16D:17答案:18设无向图的顶点个数为n，则该图最多有（）条边。

A:n(n+1)/2B:n(n-1)/2C:n-1D:n^2答案:n(n-1)/2冒泡排序是一种简单的排序方法，其时间复杂度为（）。

A:O(n)B:O(n^3)C:O(nlog2n)D:O(n^2)答案:O(n^2)判断一个环形队列qu（最多元素为Maxsize）为满队列的条件是（）。

A:qu.front!=(qu.rear+1)%MaxsizeB:qu.front!=qu.rearC:qu.front=qu.rearD:qu.front=(qu.rear+1)%Maxsize答案:qu.front=(qu.rear+1)%Maxsize在长度为n的顺序表中，若要在第i（1≦i≦n）个位置插入一个元素时，为留出插入位置需要移动的元素个数为（）。

A:iB:n-iC:n-i-1D:n-i+1答案:n-i+1用邻接表表示的图进行广度优先遍历时，通常是采用（）来实现算法的。

A:树B:队列C:栈D:图答案:队列某二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树一定是（）。

A:空或只有一个结点B:高度等于其结点的树C:完全二叉树D:二叉排序树答案:一个结点若串S=’computer’，其真子串的数目是（）。

A:9B:37C:8D:36答案:36设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（）。

A:BCDAB:CBDAC:BADCD:CDAB答案:BADC在一棵非空二叉树的中序遍历序列中，根结点的右边为（）。

A:只有右子树上部分结点B:只有右子树上所有结点C:只有左子树上所有结点D:只有左子树上部分结点答案:只有右子树上所有结点对一组记录的关键字(84，47，25，15，21)进行排序，在排序过程中，关键字序列变化为：（1）(84，47，25，15，21)（2）(47，25，15，21，84)（3）(25，15，21，47，84)（4）(15，21，25，47，84)则采用的排序方法为（）。

A:希尔排序B:直接插入排序C:冒泡排序D:快速排序答案:冒泡排序

计算机系统处理的表达式过程中，运算的中间结果值会（

）

A:存入运算符栈B:存入操作数栈C:返回给用户D:销毁答案:存入操作数栈将10个元素散列到1000000元的哈希表，则（）产生冲突。

A:一定会B:仍可能会C:答案都不对D:一定不会答案:仍可能会线性表是由n个相同数据类型的（）构成的有限序列。

A:数据元素B:字符C:表元素D:数据项答案:数据元素当待排序序列基本有序时，以下排序方法中，()最不利于其优势的发挥。

A:直接插入排序B:快速排序C:冒泡排序D:直接选择排序答案:快速排序下列数据中，（

）是非线性数据结构。

A:栈B:串C:队列D:完全二叉树答案:树从待排序的序列中选出关键字值最大的记录放到有序序列中，该排序方法称为()。

A:希尔排序B:冒泡排序C:快速排序D:直接选择排序答案:直接选择排序下列哪种数据结构常用于函数调用()。

A:链表B:数组C:队列D:堆栈答案:堆栈对线性表进行二分查找时，要求线性表必须()

A:以链接方式存储B:以顺序方式存储，且结点按关键字值有序排列C:以顺序方式存储D:以链接方式存储，且结点按关键字值有序排列答案:有序设主串的长度为n，模式串的长度为m，则串匹配的BF算法时间复杂度是()。

A:O(n×m)B:O(n+m)C:O(m)D:O(n)答案:O(n×m)链表适用于（）查找。

A:二分法B:顺序，也能二分法C:顺序D:随机答案:顺序下列关键字序列中，（）是堆。

A:94,23,31,72,16,53B:16,53,23,94,31,72C:16,23,53,31,94,72D:16,72,31,23,94,53答案:16,23,53,31,94,72算法分析的两个主要方面是：（)

A:可读性和文档性B:空间复杂性和时间复杂性C:正确性和简明性D:数据复杂性和程序复杂性答案:正确下列排序方法中，()所需的辅助空间最大。

A:快速排序B:希尔排序C:归并排序D:选择排序答案:归并对于一个头指针为head的带头结点的单链表，判断该链表为空的条件是（）。

A:head.next==headB:head==nullC:head!=nullD:head.next==null答案:head.next==null设长度为n的链队列采用单循环链表加以表示，若只设一个头指针指向队首元素，则入队操作的时间复杂度为（）。

A:O(1)B:O(n)C:O(log2n)D:O(n2)答案:O(n)循环顺序队列A[0...m-1]存放元素值，用front和rear分别表示队头和队尾，则当前队列中的元素个数是（）。

A:(rear-front+m)%mB:(rear-front+1)%mC:rear-frontD:rear-front+1答案:(rear-front+m)%m关键字序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中()的两趟排序后的结果。

A:插入排序B:堆排序C:选择排序D:冒泡排序答案:插入排序在哈夫曼树中，任何一个结点它的度都是（）。

A:0或2B:0或1或2C:1或2D:0或1答案:0或2有一个二维数组A，行下标的范围是0到8，列下标的范围是1到5，每个数组元素用相邻的4个字节存储。存储器按字节编址。假设存储数组元素A[0,1]的第一个字节的地址是0。存储数组A的最后一个元素的第一个字节的地址是（）。

A:180B:160C:216D:176答案:176下列语句段中，有标记符号“*”的语句行的语句频度（）。（其中n为正整数)a=1;m=1;while(a{m+=a;a*=3;//*}

A:log3nB:n-1C:nD:n1/2取整答案:log3n用邻接表表示图进行广度优先遍历时，通常是采用()来实现算法的。

A:树B:图C:栈D:队列答案:队列对图的深度优先遍历，类似于对树的（）遍历。

A:中根遍历B:层次遍历C:后根遍历D:先根遍历答案:先根遍历在顺序栈中，若栈顶指针top指向栈顶元素的下一个存储单元，且顺序栈的最大容量是maxSize，则顺序栈的判满条件是（）。

A:top==maxSizeB:top==maxSize-1C:top==-1D:top==0答案:top==maxSize若将字符a、b、c、d依次进栈，则不可能得到的出栈序列是（）。

A:adbcB:dcbaC:acbdD:abcd答案:adbc对一棵树进行后根遍历操作与对这棵树所对应的二叉树进行（）遍历操作相同。

A:中根B:层次C:后根D:先根答案:中根假设一棵二叉树中度为1的结点个数为5，度为2的结点个数为3，则这棵二叉树的叶结点的个数是（）。

A:5B:2C:3D:4答案:4设无向图Ｇ中有n个顶点e条边，则对应的邻接表中表头结点和表结点的个数分别为（）。

A:2n,eB:n,2eC:n,eD:e,n答案:n,2e假定一棵度为2的树中结点数为50，则其最小高度应为（）。

A:6B:4C:5D:3答案:6数据在计算机内存中的表示是指（）。

A:数据元素之间的关系B:数据的存储结构C:数据结构D:数据的逻辑结构答案:数据的存储结构4、栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5，e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队列的序列是e2，e4，e3，e6，e5，e1，则栈S的容量至少是（）。

A:6B:2C:3D:4答案:3具有5层结点的平衡二叉树至少有()个结点。

A:10B:15C:17D:12答案:12假如有一棵二叉树的后根遍历序列为DBEFCA，中根遍历序列为DBAECF，则这棵二叉树的先根遍历序列为（）。

A:ABDCEFB:ABDCFEC:ABDECFD:ABCDEF答案:ABDCEF如果含有n个顶点的图形成一个环,则它有棵（）生成树。

A:不确定B:nC:n-1D:n+1答案:n关键路径是事件结点网络中（）。

A:从源点到汇点的最短路径B:从源点到汇点的最长路径C:最短回路：D:最长回路答案:从源点到汇点的最长路径判断线索二叉树中某结点P有左孩子的条件是（）

A:p-＞LTag==0B:p!=NULLC:p-＞lchild!=NULLD:p-＞LTag==1答案:1算法分析的目的是（）。

A:找出数据的合理性B:分析算法效率以求改进C:分析算法的易懂性和文档型性D:研究算法中的输入和输出关系答案:效率任何一个无向连通网的最小生成树（）。

A:可能不存在B:一定有多棵C:只有1棵D:有一棵或多棵答案:有一棵或多棵顺序查找法适合于存储结构为()的线性表

A:压缩存储B:索引存储C:散列存储D:顺序存储或链式存储答案:顺序存储或链式存储串是一种特殊的线性表,其特殊性体现在()。

A:顺序存储B:逻辑结构是线性结构C:数据元素是字符D:链式存储答案:数据元素是字符假定一棵三叉树的结点数为50，则它的最小高度为（）。

A:5B:4C:3D:6答案:5一个有向图是有向树，当且仅当该有向图()。

A:没有有向圈。B:忽略边的方向后，是连通且没有圈的无向图。C:所有结点的出度之和等于入度之和。D:有一个结点可以到达任何其余结点。答案:忽略边的方向后，是连通且没有圈的无向图。下列陈述中不正确的是()。

A:二叉树是度为2的有序树B:二叉树中必有度为2的结点C:二叉树中最多只有两棵子树,且有左右子树之分D:二叉树中结点只有一个孩子时无左右之分答案:二叉树是度为2的有序树;二叉树中结点只有一个孩子时无左右之分;二叉树中必有度为2的结点在稀疏矩阵的三元组顺序表中,每个三元组表示()。

A:矩阵中数据元素的行号和列号B:矩阵中非零元素的数据值C:矩阵中非零元素的列号D:矩阵中非零元素的行号答案:矩阵中非零元素的行号;矩阵中非零元素的列号;矩阵中非零元素的数据值在下列排序算法中,()算法的效率与待排数据的原始状态有关。

A:冒泡排序B:插入排序C:快速排序D:基数排序答案:冒泡排序###快速排序###插入排序便于插入和删除操作的是（）。

A:静态链表B:单链表C:顺序表D:双链表答案:静态链表;单链表;双链表在数组上能做的操作有（）

A:取值操作B:删除C:插入D:赋值操作答案:取值操作###赋值操作线性表的两种存储结构叙述正确的是（）。

A:线性表顺序存储结构在插入或删除某一元素时，需要移动大量元素B:线性表顺序存储结构可以随机存取表中任一元素C:线性表链式存储结构在插入或删除某一元素时，不需要移动大量元素D:线性表链式存储结构只能顺序存取表中任一元素答案:线性表顺序存储结构可以随机存取表中任一元素;线性表链式存储结构只能顺序存取表中任一元素;线性表顺序存储结构在插入或删除某一元素时，需要移动大量元素;线性表链式存储结构在插入或删除某一元素时，不需要移动大量元素串是一种特殊的线性表，下列不能体现其特殊性的是（）。

A:可以顺序存储B:可以链接存储C:数据元素可以是多个字符D:数据元素是一个字符答案:数据元素是一个字符以下不适合用分块查的数据集是()。

A:数据分成若干块,块内数据必须有序,块间不必有序B:数据分成若干块,块内数据不必有序,但块间必须有序C:数据分成若干块,每块(除最后一块外)中数据个数需相同D:数据分成大小相等的若干块,块内数据有序答案:数据分成大小相等的若干块,块内数据有序###数据分成若干块,块内数据必须有序,块间不必有序###数据分成若干块,每块(除最后一块外)中数据个数需相同图的存储结构（）。

A:邻接矩阵B:邻接多重表C:十字链表D:邻接表答案:邻接矩阵;邻接表链表的性能优于顺序表。（）

A:错误B:正确答案:错误如果两个串含有相同的字符,则说明它们相等。（）

A:正确B:错误答案:错误顺序栈因为是顺序存储,所以可以随机存取栈中任意元素。（）

A:错B:对答案:错如果采用如下方法定义一维字符数组:intmaxSize=30;char*a=newchar[maxSize];则这种数组在程序执行过程中不能扩充。（）

A:正确B:错误答案:错串'student'和'Student'相等。（）

A:对B:错答案:错顺序表适宜于顺序存取,而链表适宜于随机存取。（）

A:错误B:正确答案:错误顺序存储方式的优点是存储密度大,且插入、删除运算效率高。（）

A:错B:对答案:错快速排序的最坏情况,可以通过适当选择中轴元素避免。（）

A:错B:对答案:对一个广义表可以为其它广义表所共享。（）

A:正确B:错误答案:正确图的深度优先搜索是一种典型的回溯搜索的例子，可以通过递归算法求解。（）

A:错误B:正确答案:正确如果一个串中所有的字母均在另一个串中出现,则说明前者是后者的子串。（）

A:错B:对答案:错从逻辑结构上看,n维数组的每个元素均属于n个向量。（）

A:错B:对答案:对按中序遍历二叉树时，某结点的直接后继是它的右子树中第1个被访问的结点。（）

A:对B:错答案:对关键路径上的活动都是关键活动,它们是否按时完成会影响工期。（）

A:错误B:正确答案:正确堆排序所需的时间与待排序的记录个数有关。（）

A:错误B:正确答案:正确一个数据结构在计算机中的表示(又称映像)称为存储结构。（）

A:错误B:正确答案:正确两顺序栈共享空间,也存在空间溢出问题。（）

A:正确B:错误答案:正确哈希表是一种将关键字转换为存储地址的存储方法。（）

A:对B:错答案:对采用分块查找,既能实现线性表所希望的查找速度,又能适应动态变化的需要。（）

A:正确B:错误答案:正确边数很多的稠密图，适宜用邻接矩阵表示。（）

A:对B:错答案:对如果结点A有3个兄弟B是A的双亲，则结点B的度为（）。

A:3B:4C:1D:2答案:3无向图的邻接矩阵中，第i顶点的度等于（）。

A:第i行非零元素个数或第i列非零元素个数B:邻接矩阵非零元素个数C:只与第i行非零元素个数相同，与第i列非零元素个数无关D:只与第i列非零元素个数相同，与第i行非零元素个数无关答案:第i行非零元素个数或第i列非零元素个数（）是讨论数据结构时涉及的最小数据单位。

A:基本单位B:数据项C:数据D:数据元素答案:数据元素;数据项设散列表的长m=14，散列函数为h（k）=k％11，表中已有4个记录（如图所示），如果采用二次探测再散列来处理冲突，则关键字为49的记录其存储地址是（）。

A:9B:3C:5D:8答案:9在哈夫曼树中，任何一个结点它的度都是（）。

A:1或2B:0或1或2C:0或1D:0或2答案:0或2栈和队列的主要区别在于()。

A:它们的逻辑结构不一样B:它们的存储结构不一样C:所包含的运算不一样D:插入、删除运算的限定不一样答案:插入删除运算的限定不一样对于只在表的首、尾进行插入操作的线性表，宜采用的存储结构为（）。

A:用头指针表示的单循环链表B:单链表C:用尾指针表示的单循环链表D:顺序表答案:用尾指针表示的单循环链表（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

A:数据元素B:基本单位C:数据D:数据项答案:数据元素设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（）。

A:2hB:h+1C:2h+1D:2h-1答案:2h-1讨论树、森林和二叉树的关系，目的是为了（）。

A:将树、森林按二叉树的存储方式进行存储B:将树、森林转换成二叉树C:体现一种技巧，没有什么实际意义D:借助二叉树上的运算方法去实现对树的一些运算答案:借助二叉树上的运算方法去实现对树的一些运算用克鲁斯卡尔(Kruskal)算法求具有n个顶点e条边的图的最小生成树的时间复杂度是（）。

A:O(e+n)B:O(eloge)C:O(n2)D:O(n)答案:O(eloge)树根的层次是1，则深度为8的完全二叉树至少有（）个结点。

A:126B:128C:129D:127答案:128下列关键字序列中，（）是堆。

A:16,72,31,23,94,53B:16,23,53,31,94,72C:94,23,31,72,16,53D:16,53,23,94,31,72答案:16,23,53,31,94,72任何一棵二叉树的叶子结点在先序、中序和后序遍历序列中的相对次序（）。

A:其余选项都不对B:不发生改变C:发生改变D:不能确定答案:不能确定一个以h为头的单循环链中，p指针指向链尾的条件是（）。

A:p-＞next=hB:p-＞data=-1C:p-＞next=NILLD:p-＞next-＞next=h答案:p-＞next=h在平衡二叉树中，进行查找的效率与（）有关。

A:二叉排序树的结点的个数B:判定树C:后序线索树D:二叉树的深度答案:二叉树的深度以下（）属于非线性结构。

A:树B:线性表C:栈D:数组答案:树数据结构在计算机内存中的表示是指（）。

A:数据结构B:数据的逻辑结构C:数据的存储结构D:数据元素之间的关系答案:数据的存储结构对22个记录的有序表作折半查找，当查找失败时，至少需要比较（）次关键字。

A:6B:3C:5D:4答案:4有13个结点的完全二叉树又是一棵（）。

A:二叉排序树B:平衡二叉树C:赫夫曼(Huffman)树D:深度为5的二叉树答案:平衡二叉树对n个不同的排序码进行冒泡排序，在元素无序的情况下比较的次数最多为（）。

A:n+1B:n(n-1)/2C:n-1D:n答案:n(n-1)/2深度为h的满m叉树的第k层有（）个结点。(1=A:mk-1B:mh-1C:mk-1D:mh-1答案:m^(k-1)下列序列之中，（）是执行第一趟快速排序后所得的序列。

A:[27，38，73]49[93，18]B:[93，38，18]49[27，73]C:[27，38，18]49[93，73]D:[27，38，93]49[18，73]答案:[27，38，18]49[93，73]在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。

A:1/2B:4C:1D:2答案:1有8个顶点的无向图最多有（）条边。

A:112B:56C:14D:28答案:28下列排序算法中，（）不能保证每趟排序至少能将一个元素放到其最终的位置上。

A:堆排序B:快速排序C:冒泡排序D:希尔排序答案:希尔排序设某棵二叉树的高度为10，则该二叉树上叶子结点最多有（）。

A:512B:1024C:20D:25答案:512用邻接表表示图进行广度优先遍历时，通常借助（）来实现算法。

A:图B:树C:栈D:队列答案:队列若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则X的前驱为（）。

A:X的右子树中最左的结点B:X的左子树中最右叶结点C:X的双亲D:X的左子树中最右结点答案:X的左子树中最右结点采用线性探测法处理冲突，可能要探测多个位置，在查找成功的情况下，所探测的这些位置上的关键字（）。

A:都相同B:一定都是同义词C:一定都不是同义词D:不一定都是同义词答案:不一定都是同义词对于数据结构，以下叙述中不正确的是（）。

A:数据项是数据的最小单位B:数据的逻辑结构是数据的各数据项之间的逻辑关系C:数据元素是数据的基本单位D:数据的逻辑结构与数据元素本身的形式和内容无关答案:数据的逻辑结构是数据的各数据项之间的逻辑关系在数据结构中，从逻辑上可以把数据结构分成（）

A:动态结构和静态结构B:线性结构和非线性结构C:内部结构和外部结构D:紧凑结构和非紧凑结构答案:线性结构和非线性结构在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是（）。

A:将n个结点从小到大排序B:访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）C:删除第i个结点（1≤i≤n）D:在第i个结点后插入一个新结点（1≤i≤n）答案:访问第i个结点（1≤i≤n）和求第i个结点的直接前驱在散列函数H(k)=k%m中，一般来讲，m应取（）。

A:偶数B:奇数C:充分大的数D:素数答案:素数线性表Ｌ在（）情况下适用于使用链式结构实现。

A:Ｌ中结点结构复杂B:需经常修改Ｌ中的结点值C:需不断对Ｌ进行删除插入D:Ｌ中含有大量的结点答案:需不断对Ｌ进行删除插入G是一个非连通无向图，共有28条边，则该图至少有（）个顶点。

A:9B:8C:10D:7答案:9引入二叉线索树的目的是（）。

A:为了能在二叉树中方便的进行插入与删除B:使二叉树的遍历结果唯一C:为了能方便的找到双亲D:加快查找结点的前驱或后继的速度答案:加快查找结点的前驱或后继的速度对n个关键字作快速排序，在最坏情况下，算法的时间复杂度是（）。

A:O(n2)B:O(n3)C:O(nlog2n)D:O(n)答案:O(n广度优先遍历类似于二叉树的（）。

A:后序遍历B:先序遍历C:层次遍历D:中序遍历答案:层次对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用（）遍历实现编号。

A:后序B:先序C:中序D:从根开始按层次遍历答案:后序计算机内部数据处理的基本单位是（）。

A:数据B:数据项C:数据库D:数据元素答案:数据元素当各边上的权值（）时，BFS算法可用来解决单源最短路径问题。

A:均相等B:均互不相等C:至少有两条边上的权不等D:不一定相等答案:均相等分别以下列序列构造二叉搜索树，与用其它三个序列所构造的结果不同的是（）。

A:（100，120，110，130，80，60，90）B:（100，80，60，90，120，130，110）C:（100，60，80，90，120，110，130）D:（100，80，90，60，120，110，130）答案:（100，60，80，90，120，110，130）无向图G=(V,E)，其中V={a，b，c，d，e，f}，E={(a，b)，(a，e)，(a，c)，(b，e)，(c，f)，(f，d)，(e，d)}。对该图进行深度优先遍历，下面不能得到的序列是（）。

A:aebdcfB:acfdebC:abedfcD:aedfcb答案:aebdcf用单链表表示的链式队列的队头在链表的（）位置。

A:表尾B:表头C:表中D:任意答案:表头一个顺序表所占用的存储空间大小与（）无关。

A:元素的类型B:元素中各字段的类型C:元素的存放顺序D:表的长度答案:元素的存放顺序下列（）结构中的数据元素的关系是“一对多”的关系。

A:图B:栈与队列C:二叉树D:线性表答案:树在完全二叉树中，若一个结点是叶结点，则它没（）。

A:左子结点和右子结点B:左子结点，右子结点和兄弟结点C:左子结点D:右子结点答案:左子结点和右子结点从具有n个结点的二叉搜索树中查找一个元素时，在最坏情况下的时间复杂度为（）。

A:O(1)B:O(n)C:O(n2)D:O(log2n)答案:O(n)线性表采用链式存储时，其地址（）。

A:部分地址必须是连续的B:连续与否均可以C:必须是连续的D:一定是不连续的答案:连续与否均可以在线索二叉树中，结点p没有左子树的充要条件是（）。

A:p->ltag=1B:其余选项都不对C:p->LeftChild=NULLD:p->ltag=1且p->LeftChild=NULL答案:=NULL给定有权无向图的邻接矩阵如下，其最小生成树的总权重是：（）

A:11B:12C:14D:10答案:14设用邻接矩阵A表示有向图G的存储结构，则有向图G中顶点i的入度为（）。

A:第i行0元素的个数之和B:第i列0元素的个数之和C:第i列非0元素的个数之和D:第i行非0元素的个数之和答案:第i列非0元素的个数之和算法分析的目的是（）

A:评价算法的效率B:辨别数据结构的合理性C:研究算法中输入与输出的关系D:鉴别算法的可读性答案:效率设有序表中有1000个元素，则用二分查找查找元素X最多需要比较（）次。

A:10B:1C:7D:25答案:10下列广义表用链表来表示时，分支结点最多的是（）。

A:L=((x,(a,B)),(x,(a,B),y))B:B=((x,(a,B),y))C:A=(s,(a,B))D:D=((a,B),(c,(a,B),D)答案:L=((x,(a,B)),(x,(a,B),y))数据的最小单位是（）。

A:数据变量B:数据项C:数据元素D:数据类型答案:数据项;数据元素设某无向图中有n个顶点e条边，则建立该图邻接表的时间复杂度为（）。

A:O(ne)B:O(n+e)C:O(n3)D:O(n2)答案:O(n+e)假定对长度n=50的有序表进行折半查找，则对应的树高度为（）。

A:5B:7C:8D:6答案:6假定一组记录为(46,74,53,14,26,38,86,65,27,34)，对其进行希尔排序，第一趟间隔为3，得到的排序结果为（）。

A:14,26,27,34,65,38,46,74,53,86B:14,26,27,38,34,46,53,65,74,86C:14,34,46,86,26,65,74,53,38,27D:26,34,54,14,27,38,86,65,46,74E:14,26,27,34,38,46,53,65,74,86F:53,74,14,34,65,46,26,86,27,38答案:5设二叉排序树上有n个结点，则在二叉排序树上查找结点的平均时间复杂度为（）。

A:O(n)B:O(nlog2n)C:O(1og2n)D:O(n2)答案:D二路归并排序的时间复杂度为（）。

A:O(1og2n)B:O(n)C:O(nlog2n)D:O(n2)答案:O(n)由树转化成二叉树，该二叉树的右子树不一定为空。（）

A:错误B:正确答案:正确分块查找的平均查找长度不仅与索引表的长度有关，而且与块的长度有关。（）

A:错误B:正确答案:正确有向图的邻接表和逆邻接表中表结点的个数不一定相等。（）

A:正确B:错误答案:错误对链表进行插入和删除操作时不必移动链表中结点。（）

A:对B:错答案:对中序遍历二叉排序树可以得到一个有序的序列。（）

A:正确B:错误答案:正确图的深度优先遍历算法中需要设置一个标志数组，以便区分图中的每个顶点是否被访问过。（）

A:错误B:正确答案:正确哈夫曼树中没有度数为1的结点。（）

A:正确B:错误答案:正确对连通图进行深度优先遍历可以访问到该图中的所有顶点。（）

A:对B:错答案:对不论是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情况。（）

A:对B:错答案:对层次遍历初始堆可以得到一个有序的序列。（）

A:正确B:错误答案:错误线性表L=(a1,a2,……,an)，下列说法正确的是（）。

A:线性表中至少要有一个元素B:每个元素都有一个直接前驱和一个直接后继C:除第一个和最后一个元素外，其余每个元素都由一个且仅有一个直接前驱和直接后继D:表中诸元素的排列顺序必须是由小到大或由大到小答案:除第一个和最后一个元素外，其余每个元素都由一个且仅有一个直接前驱和直接后继若让元素1，2，3，4，5依次进栈，则出栈次序不可能出现的是（）。

A:4，3，1，2，5B:5，4，3，2，1C:2，3，5，4，1D:2，1，5，4，3答案:4，3，1，2，5研究数据结构就是研究（）。

A:数据的逻辑结构、存储结构及其基本操作。B:数据的逻辑结构和存储结构C:数据的逻辑结构D:数据的存储结构答案:数据的逻辑结构、存储结构及其基本操作串“ababaabab”的nextval为（）。

A:010100011B:010104101C:010102101D:010101011答案:010104101在一个图中，所有顶点的度数之和等于图的边数的（）倍。

A:1/2B:2C:1D:4答案:2具有10个叶子结点的二叉树中有多少个度为2的结点（）。

A:11B:10C:8D:9答案:9循环队列存储在数组A【0，…，m】中，则入队时的操作为（）。

A:rear=(rear+1)%(m-1)B:rear=rear+1C:rear=(rear+1)%(m+1)D:rear=(rear+1)%m答案:rear=(rear+1)%(m+1)在下列排序方法中不需要对排序码值进行比较就能进行排序的是（）。

A:基数排序B:直接插入排序C:堆排序D:快速排序答案:基数排序串“ababaaababaa”的next数组为（）。

A:012121111212B:012345678999C:0123012322345D:011234223456答案:011234223456数据表中有10000个元素，如果仅要求求出其中最大的10个元素，则采用()算法最节省时间。

A:快速排序B:冒泡排序C:简单选择排序D:堆排序答案:堆排序广义表((a,b,c,d))表尾是（）。

A:()B:(b,c,d)C:aD:(a,b,c,d)答案:()数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素个数的公式为（）。

A:(n+f-r)%nB:r-fC:n+r-fD:（n+r-f)%n答案:（n+r-f)%n一棵深度为6的满二叉树有_____个叶子。

A:63B:32C:16D:31答案:32任何一个含两个或以上顶点的带权无向连通图()

A:只有一棵B:一定有多棵C:可能不存在D:有一棵或多棵答案:有一棵或多棵下面程序段的时间复杂度为____________。i=1;while(ii=i*3;

A:O(log2n)B:O(n)C:O(n2)D:O（log3n）答案:log3(n)设一棵完全二叉树具有1000个结点，有_____个度为2的结点。

A:500B:501C:499D:1000答案:499串是一种特殊的线性表，其特殊性体现在()。

A:可以链接存储B:数据元素是一个字符C:可以顺序存储D:数据元素可以是多个字符答案:数据元素是一个字符设哈希表长为14，哈希函数是H(key)=key%11，表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的元素加到表中，用二次探测法解决冲突，则放入的位置是（）。

A:3B:8C:9D:5答案:9以下关于广度优先遍历的叙述正确的是()

A:对一个强连通图调用一次广度优先遍历算法便可访问所有的顶点B:对任何非强连通图需要多次调用广度优先遍历算法才可访向所有的顶点C:广度优先遍历不适合有向图D:对任何有向图调用一次广度优先遍历算法便可访问所有的顶点答案:对一个强连通图调用一次广度优先遍历算法便可访问所有的顶点广义表((a,b,c,d))的表头是（）。

A:()B:aC:(a,b,c,d)D:(b,c,d)答案:(a,b,c,d)在一个无向图中，所有顶点的度之和等于边数的()

A:1/2B:2C:1D:4答案:2引入二叉线索树的目的是（）。

A:为了能在二叉树中方便的进行插入与删除B:为了能方便的找到双亲C:使二叉树的遍历结果唯一D:加快查找结点的前驱或后继的速度答案:加快查找结点的前驱或后继的速度链式栈结点为：(data,link)，top指向栈顶.若想摘除栈顶结点，并将删除结点的值保存到x中,则应执行操作（）。

A:x=top->data;top=top->link；B:x=top->link；C:top=top->link;x=top->link；D:x=top;top=top->link；答案:top表达式a*(b+c)-d的后缀表达式是()。

A:abc+*d-B:abc*+d-C:-+*abcdD:abcd*+-答案:abc+*d-用链接方式存储的队列，在进行插入运算时(

)。

A:仅修改头指针

B:仅修改尾指针

C:头、尾指针可能都要修改D:头、尾指针都要修改

答案:头、尾指针可能都要修改快速排序在下列（）情况下最易发挥其长处。

A:被排序的数据完全无序B:被排序的数据已基本有序C:被排序的数据中的最大值和最小值相差悬殊D:被排序的数据中含有多个相同排序码答案:被排序的数据完全无序采用邻接表存储的图的广度优先遍历算法类似于二叉树的算法()

A:先序遍历B:层次遍历C:后序遍历D:中序遍历答案:层次遍历叶子结点带权路径之和最小的二叉树称为。

A:二叉排序树B:哈夫曼树C:平衡树D:堆答案:哈夫曼树计算机算法具备输入、输出和____________。

A:可行性、可移植性和可扩充性B:可行性、确定性和有穷性C:可读性、稳定性和安全性D:确定性、稳定性和有穷性答案:可行性、确定性和有穷性判定一个有向图是否存在回路除了可以利用拓扑排序方法以外，还可以用()

A:广度优先遍历算法B:深度优先遍历算法C:求最短路径的Dijkstra方法D:求关键路径的方法答案:深度优先遍历算法队列的插入操作是在（）。

A:队列任意位置B:队头元素后C:队尾D:队头答案:队尾数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址是()。

A:1210B:1205C:1175D:1180答案:1175用5个权值{3,2,4,5,1}构造的哈夫曼（Huffman）树的带权路径长度是。

A:33B:34C:32D:15答案:33对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用（）遍历实现编号。

A:从根开始按层次遍历B:先序C:后序D:中序答案:后序对含有n个顶点、e条边的带权图求最短路径的Dijkstra算法的时间复杂度为()

A:O(n+e)B:O(n)C:(ne)D:(n2)答案:(n2)在下列存储形式中，（）不是树的存储形式？

A:孩子链表表示法B:双亲表示法C:孩子兄弟表示法D:三元组表示法答案:孩子兄弟表示法给出（）遍历序列，能够确定一棵二叉树。

A:后序和中序B:先序和层次C:先序和后序D:中序答案:后序和中序任何一个无向连通图的最小生成树有（）。

A:一定有多棵B:可能不存在C:只有一棵D:一棵或多棵答案:一定有多棵如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是（）。

A:连通图B:有回路C:完全图D:一棵树答案:连通图设环形队列的存储空间为A[0..20]，且当前队头指针（f指向队首元素的前一个位置）和队尾指针（r指向队尾元素）的值分别是8和3，则该队列中的元素个数是（）。

A:16B:5C:17D:6答案:16下列算法的时间复杂度是（

）。

i=1;k=0;while(iA:O（n+k）B:O（n2）C:O（n）D:O（1）答案:O（n）非空的循环链表head的尾结点（由指针p所指）满足（）。

A:p=NULL;B:p-＞next=NULL;C:p=head;D:p-＞next=head;答案:p-＞next=head;快速排序在最坏情况下的时间复杂度是（）。

A:O(log2n)B:O(n3)C:O(nlog2n)D:O(n2)答案:n2对称矩阵压缩存储是为了（）。

A:提高运算速度B:方便存储C:方便运算D:节省存储空间答案:节省存储空间若待排序序列已基本有序，要使它完全有序，从关键字比较次数和移动次数考虑，应当使用的排序方法是（）。

A:直接选择排序B:快速排序C:直接插入排序D:归并排序答案:直接插入排序顺序表的存储密度（）。

A:等于1B:小于1C:无法估算D:大于1答案:等于1下面关于哈希查找的说法正确的是（）。

A:除留余数法是所有哈希函数中最好的B:不存在特别好与坏的哈希函数，要视情况而定C:若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单地将该元素删去即可D:哈希函数构造得越复杂越好，因为这样随机性好，冲突小答案:不存在特别好与坏的哈希函数，要视情况而定数据结构被形式化定义为(K，R)，其中K是数据元素的有限集合，R是K上的（）有限集合。

A:关系B:操作C:映象D:存储答案:关系一个递归算法必须包括（）。

A:递归部分B:终止条件和迭代部分C:终止条件和递归部分D:迭代部分答案:终止条件和递归部分对n阶三角矩阵采用压缩存储时，需要顺序表的表长为（）。

A:n(n+1)/2B:n/2+1C:n2/2+1D:n(n+1)/2+1答案:n(n+1)/2+1在散列函数H(k)=kMODm中，一般来讲，m应取（）。

A:奇数B:充分大的数C:偶数D:素数答案:素数设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有()条有向边。

A:nB:m-1C:mD:n-1答案:m采用邻接表存储的图的广度优先遍历算法类似于二叉树的（）算法。

A:后序遍历B:层次遍历C:中序遍历D:先序遍历答案:层次遍历单链表中，增加一个头结点的目的是为了（）。

A:方便运算的实现B:标示表结点中首结点的位置C:说明单链表是线性表的链式存储D:使单链表至少有一个结点答案:方便运算的实现字符串采用结点大小为1的链表作为其存储结构，是指（）。

A:链表中只存放1个字符B:链表的长度为1C:链表的每个链结点的数据域中不仅只存放了一个字符D:链表的每个链结点的数据域中只存放了一个字符答案:链表的每个链结点的数据域中只存放了一个字符下面的说法中，只有（）是正确的。

A:若T包含在S中，则T一定是S的一个子串B:一个字符串不能说是其自身的一个子串C:字符串的长度是指串中包含的字母的个数D:字符串的长度是指串中包含的不同字符的个数答案:若T包含在S中，则T一定是S的一个子串设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为()。

A:O(n2)B:O(1)C:O(log2n)D:O(n)答案:O(n)一个具有n个顶点的图，最多有（）个连通分量。

A:nB:n-1C:0D:1答案:n采用邻接表存储的图的深度优先遍历算法类似于二叉树的（）算法。

A:中序遍历B:层次遍历C:后序遍历D:先序遍历答案:先序遍历树中所有结点的度之和等于所有结点总个数加（）。

A:0B:2C:-1D:1答案:-1具有3个结点的二叉树有（）种形态。

A:5B:3C:4D:7答案:5对线性表进行二分查找时，要求线性表必须（）。

A:以链接方式存储且元素有序B:以顺序方式存储且元素有序C:以顺序方式存储D:以链接方式存储答案:有序适用于折半查找的表的存储方式及元素排列要求为（）。

A:顺序方式存储，元素无序B:链接方式存储，元素无序C:顺序方式存储，元素有序D:链接方式存储，元素有序答案:顺序方式存储，元素有序散列文件使用散列函数将记录的关键字值计算转化为记录的存放地址，因为散列函数是一对一的关系，则选择好的（）方法是散列文件的关键。

A:散列函数和冲突处理B:散列函数C:冲突处理D:除余法中的质数答案:散列函数和冲突处理设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（）。

A:33B:18C:13D:40答案:33用冒泡排序的方法对n个数据进行排序，第一趟共比较（）对元素。

A:nB:n-1C:2D:1答案:n-1静态查找表与动态查找表两者的根本差别在于（）。

A:存储实现不同B:逻辑结构不同C:施加的操作不同D:数据元素的类型不同答案:施加的操作不同在链表中若经常在最后一个位置插入或删除元素，则宜采用（）存储方式。（）

A:带尾指针的循环单链表B:双向链表C:顺序表D:带头指针的循环单链表答案:带尾指针的循环单链表非空的循环单链表head的尾结点（由p所指向）满足（）。（）

A:p==NULLB:p.next==headC:p==headD:p.next==NULL答案:p-next==head在一个图中，所有顶点的度数之和等于所有边数的（）倍。（）

A:4B:2C:1/2D:1答案:2深度为5的二叉树，所含叶子结点的个数最多为（）。（）

A:10B:16C:31D:5答案:16带权有向图G用邻接矩阵A存储，则顶点i的入度等于A中()。（）

A:第i列非∞且非0的元素个数B:第i行非∞的元素之和C:第i行非∞且非0的元素个数D:第i列非∞的元素之和答案:第i列非∞且非0的元素个数设某棵二叉树中有2000个结点，则该二叉树的最小深度为（）。（）

A:12B:10C:11D:9答案:11每次直接比较两个相邻元素，若出现逆序排列时，就交换他们的位置，此种排序方法称为（）。（）

A:冒泡排序B:快速排序C:堆排序D:选择排序答案:冒泡排序以下算法的时间复杂度为（）。（）voidfun(intn){intx=1;while(x<=n){x=x*2;}

A:O(n)B:O(log2n)C:O(nlog2n)D:O(n1/2)答案:O(log2n)从空树开始，依次插入元素52,26,14,32,71,60,93,58,24和41后构成一棵二叉排序树。在该树查找60要进行比较的次数为（）。（）

A:5B:6C:4D:3答案:3对由n个元素的组成的序列，按关键字排序时，二路归并排序算法的关键字平均比较次数和所需的辅助存储空间分别为（）。（）

A:O(n),O(nlog2n)B:O(nlog2n)，O(n)C:O(1),O(n)D:O(nlog2n),O(n2)答案:O(n)对于顺序存储的线性表，访问结点和删除结点的时间复杂度为（）。（）

A:O(n)O(n)B:O(1)O(1)C:O(n)O(1)D:O(1)O(n)答案:O(1)O(n)将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为26的结点的左孩子编号为（）。（）

A:52B:48C:53D:50答案:48用单链表方式存储的线性表，存储每个节点需要两个域，一个数据域，另一个是（）。（）

A:空指针域B:空闲域C:当前节点所在地址域D:指针域答案:指针域一个有n个顶点的无向连通图，它所包含的连通分量个数为()。（）

A:0B:nC:n+1D:1答案:1用Prim算法和Kruskal算法构造图的最小生成树，所得到的的最小生成树（）。（）

A:无法比较B:相同C:可能相同，可能不同D:不相同答案:可能相同，可能不同折半查找和二叉排序树的时间性能（）。（）

A:相同B:完全不同C:无法比较D:有时不相同答案:不相同设带有头结点的单向循环链表的头指针变量为head，则其判空条件是（）。（）

A:head.next==headB:head.next==nullC:head==nullD:head!=null答案:head-next==head采用邻接表存储的图的广度优先遍历类似于二叉树的()。（）

A:按层次遍历B:先序遍历C:中序遍历D:后序遍历答案:层次遍历某二叉树结点的先序序列为：E、A、C、B、D、G、F，中序序列为：A、B、C、D、E、F、G，则其左子树中结点数目为（）。（）

A:3B:2C:4D:5答案:4以下数据结构中哪一个是非线性结构（）？（）

A:队列B:线性表C:栈D:二叉树答案:树深度为5的二叉树至多有（）个结点。（）

A:16B:31C:10D:32答案:31线性表采用顺序存储的缺点是（）。（）

A:元素的逻辑顺序与物理顺序不一致B:存储密度低C:插入、删除操作效率低D:只能顺序访问答案:插入、删除操作效率低线性表采用链式存储结构时，要求内存中可用存储单元的地址（）。（）

A:必须是连续的B:一定是不连续的C:连续不连续都可以D:部分地址必须是连续的答案:连续不连续都可以对于链式存储的线性表，访问结点和删除结点的时间复杂度为（）。（）

A:O(1)O(1)B:O(1)O(n)C:O(n)O(1)D:O(n)O(n)答案:O(1)O(n)构建N个记录的初始堆（heap），其时间复杂度为（）。（）

A:O(log2n)B:O(n2)C:O(n)D:O(nlog2n)答案:O(n)在含有n个结点的二叉排序树中查找某个关键字的结点时，最多进行（）次比较。（）

A:log2nB:log2n+1C:nD:n/2答案:n将10个元素散列到100000个单元的散列表中，则（）产生冲突。（）

A:不确定B:一定不会C:一定会D:仍可能会答案:仍可能会一个算法应该是（）。（）

A:要满足五个基本特征B:A和CC:程序D:问题求解步骤的描述答案:问题求解步骤的描述具有n个顶点的有向图最多有()条边。（）

A:2nB:n(n-1)C:nD:n(n+1)答案:n(n-1)一个排序算法的时间复杂度与（）什么有关。（）

A:排序算法的稳定性B:所需辅助存储空间的大小C:所需比较关键字的次数D:所采用的存储结构答案:所需比较关键字的次数假设一个有n个顶点和e条弧的有向图用邻接表表示，则删除与某个顶点vi相关的所有弧的时间复杂度是()。（）

A:O(e)B:O(n)C:O(n+e)D:O(n*e)答案:O(n+e)在有向图G的拓扑序列中，若顶点vi在顶点vj之前，则下列情况下不可能出现的是（）。（）

A:G中有一条从vj到vi的路径B:G中有一条从vi到vj的路径C:G中没有弧D:G中有弧答案:G中有一条从vj到vi的路径在一个具有n个顶点的有向图中，若所有顶点的出度之和为s，则所有顶点的入度之和为()。（）

A:nB:sC:s+1D:s-1答案:s任何一个无向图连通图的最小生成树（）。（）

A:一定有多棵B:只有一棵C:可能不存在D:有一棵或多棵答案:一定有多棵一个栈的入栈序列是a，b，c，d，e，则栈的不可能的输出序列是（）。

A:abcdeB:dceabC:decbaD:edcba答案:d设有序表中的元素为(13，18，24，35，47，50，62)，则在其中利用二分法查找值为24的元素需要经过（）次比较。

A:4B:1C:2D:3答案:3数据序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中的（）的两趟排序后的结果。

A:选择排序B:插入排序C:堆排序D:冒泡排序答案:插入排序设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用（）最节省时间。

A:带尾指针的单循环链表B:带头结点的双循环链表C:单循环链表D:单链表答案:带头结点的双循环链表假定一棵度为3的树中，结点数为50，则其最小高度为（）.

A:6B:4C:5D:3答案:5若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）。

A:快速排序B:直接插入排序C:堆排序D:归并排序答案:归并排序若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用（）遍历方法最合适。

A:后序B:中序C:前序D:按层次答案:后序把一棵树转换为二叉树后，这棵二叉树的形态是（）。

A:有多种B:有多种，但根结点都没有右孩子C:唯一的D:有多种，但根结点都没有左孩子答案:唯一设有序顺序表中有n个数据元素，则利用二分查找法查找数据元素X的最多比较次数不超过（）。

A:log2(n+1)B:log2nC:log2n-1D:log2n+1答案:log2(n+1)在作进栈运算时,应先判别栈是否(①),在作退栈运算时应先判别栈是否(②)。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为(③)。为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的内存空间时,应将两栈的(④)分别设在这片内存空间的两端,这样,当(⑤)时，才产生上溢。（）

A:满，空，n，栈底，两个栈的栈顶在栈空间的某一位置相遇.B:满，空，n+1，深度，两个栈的栈顶在栈空间的某一位置相遇.C:空，满，n/2，栈底，两个栈均不空,且一个栈的栈顶到达另一个栈的栈底.D:空，满，n，栈底，其中一个栈的栈顶到达栈空间的中心点.答案:空一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（）。

A:所有的结点均无右孩子B:只有一个叶子结点C:所有的结点均无左孩子D:是任意一棵二叉树答案:所有的结点均无右孩子在森林的二叉树表示中，结点M和结点N是同一父结点的左儿子和右儿子，则在该森林中（）。

A:M和N可能无公共祖先B:M和N有同一双亲C:M是N的左兄弟D:M是N的儿子答案:M和N可能无公共祖先下列四个序列中，哪一个是堆（）。

A:75,45,65,30,15,25,20,10B:75,65,30,15,25,45,20,10C:75,65,45,10,30,25,20,15D:75,45,65,10,25,30,20,15答案:75,45,65,30,15,25,20,10设F是一个森林，B是由F变换来的二叉树。若F中有n个非终端结点，则B中右指针城为空的结点有（）个。

A:n+2B:n+1C:nD:n-1答案:n设二叉排序树上有n个结点，则在二叉排序树上查找结点的平均时间复杂度为（）。

A:O(n)B:O(nlog2n)C:O(n2)D:O(1og2n)答案:D求解最短路径的Floyd算法的时间复杂度为（）。

A:O（n+c）B:O（n）C:O（n*n*n）D:O（n*n）答案:O（n*n*n）对线性表进行二分查找时，要求线性表必须（）

A:以链接方式存储B:以顺序方式存储,且数据元素有序C:以顺序方式存储D:以链接方式存储,且数据元素有序答案:有序适用于折半查找的表的存储方式及元素排列要求为（）

A:顺序方式存储，元素有序B:链接方式存储，元素无序C:顺序方式存储，元素无序D:链接方式存储，元素有序答案:顺序方式存储，元素有序由3个结点可以构造出多少种不同的二叉树？（）

A:2B:5C:3D:4答案:5一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（）。

A:108B:110C:120D:100答案:108有一组数据（15，9，7，8，20，-1，7，4），用堆排序的筛选方法建立的初始堆为（）。

A:-1，4，7，8，20，15，7，9B:-1，4，8，9，20，7，15，7C:其他均不对。D:-1，7，15，7，4，8，20，9答案:-1，4，7，8，20，15，7，9链表不具有的特点是（）

A:不必事先估计存储空间B:所需空间与线性长度成正比C:可随机访问任一元素D:插入、删除不需要移动元素答案:随机访问一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）。

A:250B:501C:254D:500答案:501向一个栈顶指针为Top的链栈中插入一个s所指结点时，其操作步骤为（）。

A:s->next=Top;Top=s;B:Top->next=s;C:s->next=Top->next;Top->next=s;D:s->next=Top;Top=Top->next;答案:s-＞＞next=Top；Top=Top-＞＞next设有序表中有1000个元素，则用二分查找查找元素X最多需要比较（）次。

A:10B:25C:7D:1答案:10在一个链队中，若f，r分别为队首、队尾指针，则插入s所指结点的操作为（）。

A:s->next=r;r=s;B:f->next=c;f=s;C:s->next=f;f=s;D:r->next=s;r=s;答案:r—＞next=s;r=s;设有一顺序栈已含3个元素（a1，a2，a3），元素a4正等待进栈。那么下列4个序列中不可能出现的出栈序列是（）。

A:a4，a3，a2，a1B:a3，a4，a2，a1C:a3，a1，a4，a2D:a3，a2，a4，a1答案:a3,a1,a4,a2设顺序线性表的长度为30，分成5块，每块6个元素，如果采用分块查找，则其平均查找长度为（）。

A:6.5B:11C:5D:6答案:6.5在具有n个单元的循环队列中，队满时共有（）个元素。

A:nB:n+1C:n+2D:n-1答案:n-1二叉堆的形状是一棵（）。

A:完全二叉树B:平衡二叉树C:二叉查找树D:满二叉树答案:完全二叉树栈和队列的不同点是（）。

A:访问对象的顺序不同B:删除和访问对象的顺序不同C:删除对象的顺序不同D:其他选项均不正确答案:正确下边四种排序算法中，（）的空间复杂度最大。

A:快速排序B:插入排序C:堆排序D:归并排序答案:快速排序不带头节点的单链表head为空的判定条件是（）。

A:head->next==NULLB:head->next==headC:head==NULLD:head!=NULL答案:head==NULLJava中long所占内存为（）。

A:2bytesB:16bytesC:4bytesD:8bytes答案:8已知一个单链表有n个节点，在已知p节点后插入一个新节点的时间复杂度是（）。

A:O(n-1)B:O(p)C:O(1)D:O(n)答案:O(n)在二叉查找树中，先遍历左子树，再遍历右子树，最后遍历父节点的遍历过程称为（）。

A:后序遍历B:前序遍历C:中序遍历D:其他选项都不对答案:后序遍历如果我们知道一个栈的入栈序列是1，2，3，4，……，n，输出序列的第一个为n，那么第i个为（）。

A:n-iB:n-i+1C:不能确定D:n-i-1答案:n-i+1在线性探测法散列表中，为了将key和val作为节点插入M大小的散列表，可以采用如下的代码，其中keys为散列表中用来保存key的数组，vals是保存key的数组：publicvoidput(Keykey,Valueval){inti;for(i=hash(key);keys[i]!=null;i=(i+1)%M)

{if(keys[i].equals(key)){(

？);}keys[i]=key;

vals[i]=val;}

A:keys=valsB:breakC:continueD:goto2答案:keys表达式a*(b+c)-d的后缀表达式是（）。

A:-+*abcdB:abcd+-C:abc+*d-D:abc*+d-答案:abc+*d-用邻接表表示图进行深度优先遍历时，通常借助（）来实现算法。

A:树B:图C:栈D:队列答案:栈用邻接表表示图进行广度优先遍历时，通常借助（）来实现算法。

A:栈B:树C:队列D:图答案:队列把一棵树转换为二叉树后，这棵二叉树的形态是（）。

A:有多种，但根结点都没有右孩子B:有多种C:有多种，但根结点都没有左孩子D:唯一的答案:唯一设单链表中指针p指向结点A，若要删除A的直接后继，则所需修改指针的操作为（）。

A:p->next=p->next->nextB:р=р-2neхtC:p=p->next->nextD:p->next=p答案:p-＞next＝(p-＞next)-＞next设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次进入栈S，一个元素出栈后即进入Q，若6个元素出队的序列是e2、e4、e3、e6、e5和e1，则栈S的容量至少应该是（）。

A:2B:4C:6D:3答案:3G是一个非连通无向图，共有28条边，则该图至少有（）个顶点。

A:7B:9C:8D:10答案:9折半查找与二叉排序树的时间性能（）。

A:完全不同B:有时不相同C:数量级都是O(log2n)D:相同答案:有时不相同数据对象是指（）

A:数据的基本单位B:性质相同的数据元素的集合C:相互之间存在一种或多种特定关系的数据元素的集合）。D:描述客观事物且由计算机处理的数值、字符等符号的总称答案:性质相同的数据元素的集合图的BFS生成树的树高比DFS生成树的树高（）。

A:小或相等B:大或相等C:小D:相等答案:小或相等连续存储设计时，存储单元的地址（）

A:部分连续，部分不连续B:一定连续C:不一定连续D:一定不连续答案:一定连续栈和队列的共同点是（）。

A:没有共同点B:都是先进后出C:只允许在端点处插入和删除元素D:都是先进先出答案:只允许在端点处插入和删除元素对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用（）遍历实现编号。

A:后序B:中序C:从根开始按层次遍历D:先序答案:后序算法的时间复杂度取决于（）。

A:A和BB:计算机的配置C:问题的规模D:待处理数据的初态答案:A和B一棵有n个结点的二叉树，叶子结点的数量为n0，度为2的结点数量为n2，则n0与n2的关系是（）

A:n=n0+n2B:n0=n+1C:n0=n2+1D:n0=n2-1答案:n0=n2＋1已知表头元素为c的单链表在内存中的存储状态如下表所示。地址

元素

链接地址1000H

a

1010H1004H

b

100CH1008H

c

1000H100CH

d

NULL1010H

e

1004H1014H现将f存放于1014H处并插入到单链表中，若f在逻辑上位于a和e之间，则a，e，f的“链接地址”依次是（）。

A:1014H,1004H,1010HB:1010Н,1014Н,1004НC:1014H,1010H,1004HD:1010Н,1004Н,1014Н答案:1014H,1004H,1010H构造一棵具有n个结点的二叉排序树，最理想情况下的深度为（）。

A:「log2(n+1)⌉B:nC:⌊log2(n+1)」D:n/2答案:n线性表的顺序存储结构是一种（）。

A:随机存取的存储结构B:Hash存取的存储结构C:索引存取的存储结构D:顺序存取的存储结构答案:随机存取###顺序存取设哈夫曼树中有199个结点，则该哈夫曼树中有（）个叶子结点。

A