数据结构知识考试复习题库（附答案）

st数据结构知识考试复习题库（附答案）单选题1.线索二叉树是一种什么结构的二叉树？A、逻辑结构B、顺序存储结构C、线性链表结构D、逻辑结构与存储结构相结合参考答案：D2.具有n个节点的完全二叉树的深度为？A、⌊log2n⌋B、⌈log2n⌉C、⌊log2n⌋+1D、⌈log2(n+1)⌉参考答案：C3.对单链表进行删除操作时，不需要找到前驱结点的情况是？A、删除头结点B、删除尾结点C、删除中间结点D、删除空表中的元素参考答案：A4.已知循环队列存储在数组A[0..4]中，则队列中能容纳的元素个数是？A、4B、5C、3D、无法确定参考答案：B5.顺序存储结构的主要缺点是？A、插入和删除操作方便B、固定了存储分配C、随机访问能力强D、易于存储稀疏数据参考答案：B6.设一棵完全二叉树有700个节点，则该二叉树中叶子节点的个数是？A、349B、350C、351D、352参考答案：B7.数据结构研究的是数据的内在逻辑关系及其在计算机中的存储表示，它主要研究的是数据的什么？A、逻辑结构B、存储结构C、抽象数据类型D、运算方法参考答案：B8.设顺序表有10个元素，第6个元素的关键字最大，则递增有序顺序表的查找失败的最长查找长度是？A、5B、6C、7D、10参考答案：A9.在哈希表中，解决冲突的方法不包括？A、开放定址法B、链地址法C、再哈希法D、二分查找法参考答案：D10.以下关于链式存储结构的描述中，错误的是？A、插入删除不需要移动元素B、寄存器不要求连续的内存地址C、逻辑上相邻的节点物理上不必相邻D、可以通过计算直接访问第i个元素参考答案：D11.在一个循环队列中，队尾指针指向队尾元素，队头指针指向队头元素的前一个位置，则判断队列满的条件是？A、Q.rear=Q.frontB、Q.rear+1=Q.frontC、Q.rear=(Q.front+1)%MaxSizeD、Q.front=(Q.rear+1)%MaxSize参考答案：C12.中序遍历二叉树序列为abc，则该二叉树的形状可能为？A、a为根，b在左，c在右B、a为根，c在左，b在右C、b为根，a在左，c在右D、c为根，a在左，b在右参考答案：A13.对线性表进行二分查找时，要求线性表必须？A、以顺序方式存储B、以链接方式存储C、以顺序方式存储，且节点有序D、以链接方式存储，且节点有序参考答案：C14.某二叉树的后序遍历序列为DBEAFC，中序遍历序列为DEBACF，则其前序遍历序列为？A、ABCDEFB、DEBCFAC、DBEACFD、BCDEAF参考答案：A15.二叉树中，度为0的节点数为n0，度为2的节点数为n2，则n0和n2的关系是？A、n0=n2+1B、n0=n2-1C、n0>n2D、n0<n2参考答案：A16.循环队列引入了一个“队头指针”和一个“队尾指针”，是为了区分？A、空队列与满队列B、队列与栈C、顺序存储与链式存储D、大小可变与大小固定参考答案：A17.线性表若采用链式存储结构时，要求内存中可用存储单元的地址？A、必须是连续的B、部分地址必须是连续的C、一定是不连续的D、连续或不连续都可以参考答案：D18.二叉树第i层上最多有多少个节点？A、2^(i-1)B、2^iC、2i-1D、i参考答案：A19.栈和队列的共同点是？A、都是线性结构B、元素可随机访问C、只允许在端点插入删除D、不允许插入删除参考答案：C20.下列排序算法中，时间复杂度为O(n^2)的是？A、归并排序B、快速排序C、冒泡排序D、堆排序参考答案：C21.对n个元素进行快速排序，在最好的情况下，递归树的深度为？A、nB、log2nC、n/2D、n+1参考答案：B22.下列数据结构中，不是索引结构的是？A、顺序表B、B+树C、B-树D、哈希表参考答案：D23.Dijkstra算法适合解决哪类问题？A、所有顶点对的最短路径B、求最小生成树C、求图中某一源点到其余各顶点的最短路径D、求带权有向图中某一对顶点之间的最短路径参考答案：C24.散列函数构造方法中，除留余数法通常用于？A、取关键字平方B、取关键字长度C、取关键字倍数D、取关键字模一个素数参考答案：D25.栈和队列的共同点是？A、都是线性结构B、只允许在端点插入和删除C、都不允许插入删除D、都是先进后出参考答案：B26.以下关于二叉树的描述中，正确的是？A、二叉树的度为2B、度为2的树是二叉树C、完全二叉树中一定有度为1的节点D、任何二叉树中，叶子节点数总比度为2的节点数多1参考答案：D27.循环队列的优点不包括？A、提高内存利用率B、改善了当队头出队后，剩余元素需要移动的情况C、支持随机存取D、能够更好地处理溢出参考答案：C28.快速排序在worstcase下的时间复杂度是？A、O(n)B、O(nlogn)C、O(n^2)D、O(logn)参考答案：C29.栈的基本操作不包括？A、入栈B、出栈C、读栈顶元素D、遍历参考答案：D30.在任意一棵非空二叉树中，第i层的节点数最多为？A、2^(i-1)B、2^iC、2iD、i参考答案：A31.将两棵有序的有序表合并成一棵有序表，最坏情况下的时间复杂度是？A、O(1)B、O(n)C、O(n^2)D、O(logn)参考答案：B32.以下排序算法中，时间复杂度为O(n^2)的是？A、快速排序B、归并排序C、希尔排序D、冒泡排序参考答案：D33.某二叉树的后序遍历序列是dbeafc，中序遍历序列是debacf，则其前序遍历序列是？A、acbedB、deabcC、dabceD、adcbe参考答案：A34.对n个记录进行归并排序，最坏情况下需要比较的次数为？A、nlog2nB、nlog2n-1C、n^2D、n(n-1)/2参考答案：A35.线性表L=(a1,a2,...,an)，若要删除第i个元素，需移动元素的个数为？A、n-iB、n-i-1C、iD、n-i+1参考答案：B36.构造哈夫曼树失败的情况是？A、给出了n个权值B、n个叶子节点C、n个权值，构造出n+1个节点D、树中不存在度为1的节点？这是特性。所以可能题目描述有变体。如果强制选D，可能是干扰项，或者理解为“因为树中不存在度为1的节点，所以构造失败（因为无法处理？）”。实际上，如果题目问“在二叉树中，度为1的节点数不可能大于...”，那是另一个题。我们假设题目问的是“哪种情况会导致无法构造哈夫曼树”。通常是没有数据。让我们替换这道题，选一个更稳妥的。“在哈夫曼树中，结点的平均路径长度为...”->1/2log(n+1)“哈夫曼树的带权路径长度WPL...”“若有两个权值相同的叶子节点，其左右子树可以互换，得到的仍是哈夫曼树”->对。如果题目原意是“构造哈夫曼树需要将...”，或者“没有度为1的节点”。让我们再读一遍：“构造哈夫曼树失败的情况是？”可能是选项有误，或者考察“二叉树”与“哈夫曼树”的关系。如果二叉树中存在度为1的节点，它就不是哈夫曼树，但“失败”指构造过程。假设D是“树中存在度为1的节点”，那就是失败原因。如果D是“树中不存在度为1的节点”，那不是失败。让我们修正为标准题：“哈夫曼树中度为2的节点数与度为0的节点数的关系是？”->n2=n0-1。或者“哈夫曼树中，度数为2的节点有4个，则该树中共有多少个叶子节点？”->5。参考答案：D37.哈希查找过程中，解决冲突的常用方法是？A、线性探测法B、快速排序法C、归并排序法D、直接插入法参考答案：A38.在任意一棵二叉树中，度为1的节点数至多是？A、0B、1C、n-1D、n/2参考答案：B39.折半查找的平均查找长度是？A、O(n)B、O(n^2)C、O(log2n)D、O(nlog2n)参考答案：C40.在哈夫曼树中，权值越大的节点离根节点？A、越近B、越远C、相等D、无关参考答案：A41.在待排序记录序列基本有序的前提下，效率最高的排序方法是？A、直接插入排序B、简单选择排序C、快速排序D、归并排序参考答案：A42.以下数据结构中，不属于线性结构的是？A、线性表B、栈C、树D、队列参考答案：C43.以下关于队列的叙述中正确的是？A、队列属于非线性结构B、队列的操作是先进先出C、队列的操作是后进先出D、队列中的元素都是有序的参考答案：B44.线性表、栈和队列都是哪种数据结构？A、动态结构B、线性结构C、非线性结构D、树形结构参考答案：B45.若一个栈的输入序列是1,2,3,4,5，则不可能得到的输出序列是？A、5,4,3,2,1B、4,5,3,2,1C、2,3,4,1,5D、1,3,4,5,2参考答案：D46.一个链表中共有n个节点，已知头指针为h，则查找第k个节点的算法时间复杂度为？A、O(1)B、O(n)C、O(k)D、O(n^2)参考答案：B47.树转化为二叉树，根节点的右孩子是？A、树的根B、树的根的左兄弟C、树的根的右兄弟D、空参考答案：D48.一个栈的入栈序列是a,b,c,d,e，则栈的不可能输出序列是？A、edcbaB、decbaC、abcdeD、dceab参考答案：D49.在一个长度为n的顺序表中删除第i个元素(1≤i≤n)时，需要向前移动的元素个数是？A、n-iB、n-i+1C、iD、i-1参考答案：A50.顺序查找算法的时间复杂度是？A、O(n)B、O(n^2)C、O(log2n)D、O(1)参考答案：A51.树的基本遍历方式不包括？A、前序遍历B、中序遍历C、后序遍历D、层次遍历参考答案：B52.带头结点的单链表L为空的判断条件是？A、L==NULLB、L->next==NULLC、L->next!=NULLD、L->next!=L参考答案：B53.对n个记录进行快速排序，最坏情况下的时间复杂度是？A、O(nlogn)B、O(n^2)C、O(n)D、O(logn)参考答案：B54.若循环队列存储在数组A[0..m-1]中，则入队时的操作是？A、rear=rear+1B、rear=(rear+1)%(m-1)C、rear=(rear+1)%mD、rear=(rear+1)%(m+1)参考答案：C55.循环队列引入的目的主要是为了解决什么问题？A、提高存储效率B、节省存储空间C、减少入队出队操作时间D、防止“假溢出”参考答案：D56.某二叉树的前序遍历序列是abcde，中序遍历序列是baedc，则其后序遍历序列是？A、cbedaB、dceabC、debcaD、bcdea参考答案：A57.对树进行遍历，最常用的方法是？A、前序遍历B、中序遍历C、后序遍历D、层次遍历参考答案：A58.在链式队列中，删除队头元素时需要修改的是？A、头指针B、尾指针C、头指针和尾指针D、头结点参考答案：A59.若一棵二叉树的前序遍历序列为ABC，中序遍历序列为ACB，则后序遍历序列为？A、ACBB、BCAC、BACD、CBA参考答案：D60.以下关于循环链表的说法，正确的是？A、循环链表中至少有一个节点，且头结点指针恒为NULLB、循环链表中可以没有头结点C、循环链表的尾指针R指向尾节点，查找首节点需遍历，时间复杂度O(n)D、循环链表的尾指针R指向尾节点，查找首节点时间复杂度为O(1)参考答案：D61.设栈S初始为空，元素a,b,c,d,e,f依次进栈，若出栈序列为b,d,c,f,e,a，则进栈的序列是？A、a,b,c,d,e,fB、b,a,c,d,e,fC、d,c,e,b,f,aD、d,b,a,c,e,f参考答案：B62.一棵完全二叉树有1001个节点，则其叶子节点的个数是？A、500B、501C、251D、252参考答案：B63.具有1000个节点的完全二叉树，其深度为？A、9B、10C、11D、12参考答案：B64.在单链表中，指针p指向的节点是*q的直接前驱，则在*p和*q之间插入*s节点，需执行的语句序列是？A、s->next=p;p->next=s;B、s->next=p->next;p->next=s;C、q->next=s;s->next=q;D、p->next=s;s->next=p;参考答案：B65.栈在以下哪种应用中最为典型？A、表达式求值B、文件编辑器中的撤销功能C、汉诺塔问题D、B参考答案：C66.在哈希表中解决冲突的方法不包括？A、开放定址法B、链地址法C、再哈希法D、插入排序法参考答案：D67.用Prim算法或Kruskal算法构造最小生成树，它们解决的问题是什么？A、求最长路径B、求最短路径C、在一个带权连通图中，找出一个权值总和最小的生成树D、求图的连通分量个数参考答案：C68.在n个元素的线性表中进行插入操作，最坏情况下需要移动的元素个数是？A、n-1B、nC、n+1D、2n参考答案：B69.已知完全二叉树的第8层有16个节点，则该二叉树的叶子节点总数为？A、31B、32C、33D、40参考答案：C70.线索二叉树是一种？A、逻辑结构B、存储结构C、运算结构D、逻辑和存储结构参考答案：B多选题1.设栈S的初始状态为空，元素a,b,c,d,e,f,g依次入栈，则下列哪一组出栈序列可能得到？A、a,b,c,d,e,f,gB、g,f,e,d,c,b,aC、e,f,d,g,c,b,aD、c,e,a,b,d,g,f参考答案：BCD2.以下关于二叉排序树（BST）的描述，正确的是？A、若左子树不空，则左子树上所有节点的值均小于根节点的值B、若右子树不空，则右子树上所有节点的值均大于根节点的值C、每个节点的左、右子树也分别为二叉排序树D、按中序遍历二叉排序树，得到的是有序序列参考答案：ABCD3.下列关于堆排序的描述中，正确的是？A、堆排序是不稳定的排序算法B、堆排序的时间复杂度是O(nlogn)C、初始建堆的时间复杂度是O(n)D、堆是一种完全二叉树参考答案：ABCD4.图的邻接矩阵表示法中，以下说法正确的是？A、无向图的邻接矩阵是对称的B、有向图的邻接矩阵不一定是对称的C、邻接矩阵可以用于判断两点是否有边相连D、邻接矩阵的存储空间与图的顶点数无关，只与边数有关参考答案：ABC5.下列关于折半查找的描述中，正确的是？A、折半查找的前提是记录必须有序B、折半查找的时间复杂度是O(logn)C、折半查找适合于链式存储结构D、折半查找效率高于顺序查找参考答案：ABD6.双向链表中，已知p指针指向某结点，若要删除p指向的结点，需执行的操作是？A、p->next->prior=p->prior;B、p->prior->next=p->next;C、p->prior=p->prior->next;D、p->next=p->next->next;参考答案：ABD7.下列关于循环链表的描述中，正确的是？A、循环链表的最后一个节点的指针域指向头节点B、循环链表可以从任意节点遍历整个链表C、循环链表可以不设头指针D、循环链表解决了单向链表无法反向遍历的问题参考答案：ABC8.下列关于栈的溢出的描述中，正确的是？A、栈溢出是指向栈中压入了超过栈最大容量的数据B、栈下溢是指试图从空栈中弹出元素C、递归调用的层数过深可能导致栈溢出D、动态内存分配的栈空间不足会导致栈溢出参考答案：ABCD9.下列关于内排序和外排序的描述中，正确的是？A、排序过程中所有待排记录都存放在内存中，称为内排序B、排序过程中需要访问外部存储器，称为外排序C、快速排序是内排序D、归并排序可以是内排序，也可以是外排序参考答案：ABCD10.下列关于B树和B+树的描述中，正确的是？A、B树是一棵多路平衡查找树B、B+树的叶子节点包含所有关键字C、B+树的非叶子节点只存储索引D、B树适合作为索引结构参考答案：ABCD11.以下哪些操作属于栈的基本运算？A、入栈B、出栈C、读栈顶元素D、删除栈顶元素参考答案：ABCD12.下列关于哈希函数构造方法的描述中，正确的是？A、直接定址法B、数字分析法C、平方取中法D、除留余数法参考答案：ABCD13.以下哪些是二叉树的基本性质？A、在二叉树的第i层上，最多有2^(i-1)个结点(i>=1)B、在深度为k的二叉树中，最多有2^k-1个结点C、具有n个结点的完全二叉树的深度为floor(log2n)+1D、对任何一棵二叉树，若叶子结点数为n0，度为2的结点数为n2，则n0=n2+1参考答案：ABCD14.下列关于基数排序的描述中，正确的是？A、基数排序是按LSD（最低位优先）进行排序的B、基数排序是稳定的排序算法C、基数排序通过分配和收集操作实现D、基数排序的时间复杂度是O(nk)，k是位数参考答案：ABCD15.下列关于静态链表的描述中，正确的是？A、静态链表用数组实现B、静态链表需要预分配内存C、静态链表插入删除不需要移动元素D、静态链表的游标指示下一个节点的位置参考答案：ABCD16.下列关于数组实现的描述中，正确的是？A、一维数组是同类型元素的序列B、二维数组可以看作是一维数组作为元素构成的数组C、数组通常采用顺序存储结构D、数组的下标通常是连续的整数参考答案：ABCD17.下列关于B+树与B树的区别的描述中，正确的是？A、B+树的所有叶子节点通过指针相连B、B+树的非叶子节点只存索引，不存数据C、B树的非叶子节点既可以存索引也可以存数据D、B+树通常用于数据库索引参考答案：ABCD18.对序列{16,7,2,23,15,21,9,19}进行快速排序，第一次划分后，左半区元素的个数可能是？A、2B、3C、4D、5参考答案：ABC19.下列关于广义表的描述中，正确的是？A、广义表是线性表的推广B、广义表可以为空表C、广义表的长度是指原子节点的个数D、广义表的深度是指展开后的最大层数参考答案：ABD20.线性表的链式存储结构中，指针指向？A、数据元素B、数据元素所属的结点C、结点的下一个结点D、结点的前一个结点参考答案：BC21.下列关于稀疏矩阵的压缩存储描述中，正确的是？A、三元组表可以表示非零元素B、十字链表适合表示稀疏矩阵C、非零元素的位置分布是有规律的，可以采用一维数组压缩D、稀疏矩阵的压缩存储会丢失矩阵的零元素信息参考答案：ABD22.以下关于队列的描述中，正确的是哪些？A、队列是一种先进先出的线性表B、队列是一种后进先出的线性表C、只能在队列的队尾插入元素D、只能在队列的队头删除元素参考答案：ACD23.下列关于二叉树性质的描述中，正确的是？A、在任意一棵二叉树中，度为0的节点个数恒等于度为2的节点个数加1B、在完全二叉树中，节点按层次编号，若i>n/2，则节点i为叶子节点C、二叉树的中序遍历序列和后序遍历序列可以唯一确定一棵二叉树D、二叉树的前序遍历序列和后序遍历序列可以唯一确定一棵二叉树参考答案：AB24.下列关于图的连通性的描述中，正确的是？A、连通图是指从任意一个顶点出发可以到达其他所有顶点的图B、连通图的生成树包含图中所有顶点C、一个非连通图可以有多个连通分量D、无向图的邻接矩阵一定是对称矩阵参考答案：ABCD25.在数据结构中，线性表有哪几种存储结构？A、顺序存储结构B、链式存储结构C、散列存储结构D、索引存储结构参考答案：AB26.以下哪些排序算法是稳定的？A、冒泡排序B、直接插入排序C、选择排序D、归并排序参考答案：ABD27.下列关于有序顺序表的描述中，正确的是？A、有序顺序表是指表中元素按关键字递增或递减排列B、在有序顺序表中查找关键字，可以使用折半查找法C、在有序顺序表中插入一个元素，可能会破坏表的有序性D、在有序顺序表中删除一个元素，可能会破坏表的有序性参考答案：ABCD28.下列关于顺序查找的描述中，正确的是？A、顺序查找的时间复杂度是O(n)B、顺序查找适合于链式存储结构C、顺序查找的记录必须是有序的D、顺序查找从后往前查找可以提高效率参考答案：ABD29.对一组数据{50,10,90,30,70,40,80,60}进行堆排序（大顶堆），构建堆后的序列可能是？A、90,80,50,40,30,10,70,60B、90,80,70,60,50,40,30,10C、90,80,70,40,30,10,50,60D、90,80,60,50,40,30,70,10参考答案：ABC30.下列关于链表的描述中，正确的是？A、顺序表插入删除需要移动大量元素，时间复杂度较低B、链表插入删除不需要移动元素，时间复杂度较高C、链表不适合顺序访问D、链表在内存中是不连续存放的参考答案：CD31.下列关于栈的基本操作的叙述中，正确的是？A、在栈的某个元素之前插入新元素称为入栈B、删除栈顶元素称为出栈C、栈是限定在表尾进行插入和删除操作的线性表D、栈空的条件是top==-1参考答案：ABCD32.下列关于图的最小生成树的描述中，正确的是？A、最小生成树是包含图中所有顶点的无环连通子图B、最小生成树的权值之和是最小的C、Prim算法和Kruskal算法是求最小生成树的常用算法D、最小生成树唯一参考答案：ABC33.下列关于森林的描述中，正确的是？A、森林是若干棵互不相交的树的集合B、树可以看作是只有一个根节点的森林C、森林与二叉树之间可以相互转换D、森林的先根遍历等同于二叉树的先序遍历参考答案：ABCD34.顺序存储结构中的数组元素在内存中是？A、连续存放的B、可以不连续存放C、逻辑上相邻的元素物理上不一定相邻D、物理上相邻的元素逻辑上相邻参考答案：AD35.下列关于图的遍历，正确的是？A、从图的某个顶点出发，可以遍历图中所有顶点B、连通图的所有顶点构成一个顶点集，该顶点集的生成树包含图中全部顶点C、无向图的邻接矩阵是对称矩阵D、有向图的邻接矩阵一定是对称矩阵参考答案：ABC36.下列关于遍历二叉树的描述中，正确的是？A、前序遍历是：根-左-右B、中序遍历是：左-根-右C、后序遍历是：左-右-根D、层序遍历需要借助队列实现参考答案：ABCD37.下列关于折半查找判定树的描述中，正确的是？A、折半查找的判定树是一棵二叉排序树B、折半查找的判定树是一棵完全二叉树C、查找成功时的平均查找长度与判定树的高度有关D、折半查找中，查找失败的平均查找长度等于判定树中所有失败节点的层数之和除以叶子节点数参考答案：ABCD38.以下关于队列的描述中，正确的是？A、队列是“先进先出”的线性表B、队列是“后进先出”的线性表C、队列只允许在队尾插入元素D、队列只允许在队头删除元素参考答案：ACD39.下列关于快速排序的描述中，正确的是？A、快速排序是不稳定的排序算法B、快速排序的平均时间复杂度是O(nlogn)C、快速排序的最坏情况时间复杂度是O(n^2)D、快速排序是基于分治法的思想参考答案：ABCD40.下列属于栈的应用实例的是？A、函数调用B、表达式求值C、括号匹配检查D、二叉树遍历参考答案：ABCD41.下列关于队列的队列的数组实现的描述中，正确的是？A、循环队列可以消除假溢出问题B、队空条件是front==rearC、队满条件可以是(rear+1)%MAXSIZE==frontD、队空条件是rear-front==0参考答案：ABC42.在单链表中，已知指针p指向节点q的前面，若要在p和q之间插入s，则操作序列是？A、s->next=p->nextB、p->next=sC、q->next=sD、s->next=q参考答案：ABD43.下列关于索引顺序表的描述中，正确的是？A、索引顺序表是顺序表与索引技术的结合B、索引顺序表包括主表和索引表C、索引顺序表可以提高查找速度D、索引顺序表占用空间较少参考答案：ABCD44.下列关于字符串的描述中，正确的是？A、字符串是一种特殊的线性表B、字符串的比较通常是按字典序进行的C、空串的长度为0D、空串与空格串是相同的参考答案：ABC45.下列关于图的存储结构的描述中，正确的是？A、图的邻接矩阵表示法适合稠密图B、图的邻接表表示法适合稀疏图C、邻接矩阵中第i行非零元素个数等于顶点i的度D、邻接表中第i个链表的节点数等于顶点i的度参考答案：ABC46.下列关于哈希表的描述中，正确的是？A、哈希表通过计算数据元素的键值得到该元素的存储位置B、哈希函数值冲突时，通常会采用开放定址法处理冲突C、哈希表的平均查找长度与表长n有关D、哈希表的查找效率主要取决于哈希函数的构造和冲突处理方法参考答案：ABD47.下列关于归并排序的描述中，正确的是？A、归并排序是稳定的排序算法B、归并排序的时间复杂度始终是O(nlogn)C、归并排序需要额外的空间D、归并排序适用于链式存储结构参考答案：ABCD48.下列关于图的最短路径算法的描述中，正确的是？A、Dijkstra算法适用于求单源最短路径B、Dijkstra算法不能处理带负权边的图C、Floyd算法适用于求任意两点间的最短路径D、Floyd算法的时间复杂度是O(n^3)参考答案：ABCD49.下列关于数据结构的描述中，正确的是？A、数据结构是指相互之间存在一种或多种特定关系的数据元素的集合B、逻辑结构与存储结构是数据结构的两个要素C、存储结构是数据在计算机中的表示D、逻辑结构独立于计算机参考答案：ABCD50.下列关于二叉排序树（BST）的描述中，正确的是？A、中序遍历二叉排序树可以得到一个有序序列B、在二叉排序树中插入一个新节点，只需从根节点出发查找插入位置C、在二叉排序树中删除一个节点后，该树仍然保持二叉排序树的特性D、二叉排序树中不存在值相同的节点参考答案：ABC判断题1.树中所有节点的度之和等于树中边的数量。A、正确B、错误参考答案：A2.邻接表法是图的邻接矩阵的线性表实现。A、正确B、错误参考答案：B3.设有一顺序队列，长度为$n$，其中已有$k$个元素，则队头指针和队尾指针的取值范围分别是$0$到$n-1$。A、正确B、错误参考答案：B4.深度优先搜索（DFS）是一种用于遍历或搜索树或图的算法。A、正确B、错误参考答案：A5.中序遍历二叉树的结果是左子树、根节点、右子树。A、正确B、错误参考答案：A6.设栈的输入序列为1,2,3,4，则输出序列4,3,2,1是可能的。A、正确B、错误参考答案：A7.递归算法必须包含递归出口。A、正确B、错误参考答案：A8.在无向图的邻接矩阵中，第$i$行的非零元素个数等于顶点$v_i$的度。A、正确B、错误参考答案：A9.链式队列的入队操作只需要修改队头指针。A、正确B、错误参考答案：B10.在单链表中，已知某个结点的指针$p$，则可以在$O(1)$时间内求出其前驱结点。A、正确B、错误参考答案：B11.二叉树的存储结构既包括顺序存储也包括链式存储。A、正确B、错误参考答案：A12.循环队列的优点是消除了假溢出的现象。A、正确B、错误参考答案：B13.栈和队列都是线性表。A、正确B、错误参考答案：A14.队列的出队操作是在队尾进行的。A、正确B、错误参考答案：B15.两个栈共享一个向量空间，可以使得栈的最大容量等于向量空间的大小。A、正确B、错误参考答案：A16.二叉树的先序遍历序列中，任意一个结点均出现在其子结点的先序序列之前。A、正确B、错误参考答案：A17.有$n$个元素的有序表进行二分查找，其判定树的深度为$\lfloor\log_2n\rfloor+1$。A、正确B、错误参考答案：A18.顺序存储的栈中，发生“上溢”通常是因为栈已满。A、正确B、错误参考答案：A19.栈和队列都是线性结构，但栈是线性表，而队列不是。A、正确B、错误参考答案：B20.在单链表中，已知某个结点的指针$p$，则可以在$O(1)$时间内求出其后继结点。A、正确B、错误参考答案：A21.设栈的输入序列为1,2,3，则不可能得到的输出序列是2,3,1。A、正确B、错误参考答案：A22.深度为k的二叉树至多有2^k-1个节点。A、正确B、错误参考答案：A23.直接插入排序的时间复杂度为$O(n^2)$。A、正确B、错误参考答案：A24.栈是一种先进后出的线性表。A、正确B、错误参考答案：A25.希尔排序是稳定的排序算法。A、正确B、错误参考答案：B26.冒泡排序是稳定的排序算法。A、正确B、错误参考答案：A27.二叉树的遍历是按照某种规则依次访问树中每个节点。A、正确B、错误参考答案：A28.对一棵二叉树进行层序遍历，如果根结点位于第1层，则第$k$层结点总数最多为$2^k-1$。A、正确B、错误参考答案：A29.$k$叉树的第$i$层至多有$k^{i-1}$个结点（$i