2026年大学试题(计算机科学)-数据结构历年参考题库含答案解析

2026年大学试题(计算机科学)-数据结构历年参考题库含答案解析一、选择题从给出的选项中选择正确答案（共100题）1、时间管理矩阵中，重要且紧急的任务应如何处理？A.立即处理B.稍后处理C.委托他人D.忽略不计2、SMART原则中的M代表什么含义？A.可实现性B.可衡量性C.可操作性D.可理解性3、以下哪项最符合自主管理中的授权原则？A.完全放权不加约束B.适度授权并提供支持C.保留所有决策权D.仅口头授权无书面依据4、团队自主管理成功的关键因素不包括？A.成员能力匹配B.团队凝聚力C.外部强制干预D.清晰共同目标5、自主管理的最终目标是实现什么层面的和谐发展？A.个人与组织协同发展B.个人利益最大化C.组织控制强化D.竞争关系激化6、在线性表的顺序存储结构中，其优点之一是：A.插入操作效率高B.删除操作效率高C.可随机访问任一元素D.存储空间占用少7、设栈S和队列Q的初始状态均为空，元素a、b、c、d、e、f、g依次进入栈S，每出一个元素即可进入队列Q。若7个元素出队的顺序为b、d、c、f、e、g、a，则栈S的容量至少是：A.2B.3C.4D.58、循环队列存储在数组A[0..m]中，则入队时的操作为：A.rear=rear+1B.rear=(rear+1)%(m+1)C.rear=(rear+1)%mD.rear=(rear+1)%(m+2)9、对队列进行下列操作中，不会出现队列溢出错误的是：A.入队B.出队C.读队头元素D.以上操作都不会10、高度为5的二叉树最多有个结点：A.15B.31C.63D.3211、一棵二叉树的先序遍历序列为ABDEGCFH，中序遍历序列为DBGEACHF，则其后序遍历序列为：A.DGEBHFCAB.ABCDEFGHC.GDHBFECAD.ABDEGCFH12、下列排序方法中，最坏情况下比较次数最少的是：A.快速排序B.冒泡排序C.堆排序D.直接插入排序13、对n个元素的序列进行快速排序时，最坏情况下的时间复杂度为：A.O(n)B.O(nlog₂n)C.O(n²)D.O(log₂n)14、在具有n个结点的二叉排序树中查找某个结点，其时间复杂度与有关：A.树的高度B.结点的值C.树的形状D.A和C15、以下关于B-树的叙述中，错误的是：A.B-树中每个结点的子树个数不超过mB.除根结点外，每个非终端结点至少有⌈m/2⌉棵子树C.B-树中所有叶子结点都在同一层次上D.B-树中关键字的数量可以少于子树的数量16、下列排序算法中，是不稳定排序：A.冒泡排序B.归并排序C.简单插入排序D.快速排序17、已知一个图的邻接矩阵如下，该图从顶点V1出发进行深度优先搜索得到的序列为：A.V1→V2→V3→V4→V5B.V1→V3→V2→V5→V4C.V1→V2→V4→V5→V3D.V1→V3→V5→V4→V218、无向图G有16条边，有3个4度顶点、4个3度顶点，其余顶点度数为2，则G中顶点总数为：A.10B.11C.12D.1319、Hash表中发生冲突的原因是：A.关键字个数超过表长B.关键字的数量太多C.不同的关键字映射到相同的地址D.哈希函数选择不当20、对下列关键字序列用快速排序进行排序时，速度最快的是：A.{25,78,61,97,43,82,12}B.{82,25,61,43,97,12,78}C.{12,25,43,61,78,82,97}D.{97,82,78,61,43,25,12}21、采用分块查找时，若线性表共256个元素，且每块含16个元素，则检索任意元素最多与个元素进行比较：A.16B.20C.24D.3222、下列代码片段的时间复杂度为：

for(i=1;i<=n;i++)

for(j=1;j<=m;j++)

sum+=i*j;A.O(n+m)B.O(n×m)C.O(n²)D.O(m²)23、在一个单链表中，若删除p所指结点之后的结点，则需执行的操作是：A.p->next=p->next->nextB.p=p->nextC.p->next=pD.p=p->next->next24、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占据一个地址空间，则a85的地址为：A.18B.19C.33D.4025、下列算法的时间复杂度为：

intfact(intn){

if(n<=1)return1;

returnn*fact(n-1);

}A.O(1)B.O(log₂n)C.O(n)D.O(n²)26、在长度为n的线性表中，采用顺序存储结构，在第i个位置（1≤i≤n+1）插入一个新元素，需要移动多少个元素？A.n-iB.n-i+1C.n-i-1D.n27、一个栈的入栈序列为1,2,3,4,5，下列哪个序列不可能是栈的输出序列？A.2,4,3,5,1B.4,5,3,2,1C.3,1,2,4,5D.1,5,4,3,228、循环队列存储在一个容量为n的数组中，初始时front=rear=0，执行k次入队和m次出队操作后（k≥m），队头指针front和队尾指针rear的值分别为多少？A.front=m%n,rear=k%nB.front=(m+k)%n,rear=k%nC.front=m%n,rear=(k+m)%nD.front=k%n,rear=(k+m)%n29、一棵完全二叉树有n个节点，其中叶子节点的个数为多少？A.⌊n/2⌋B.⌈n/2⌉C.⌊(n+1)/2⌋D.⌈(n+1)/2⌉30、对一棵有n个节点的二叉树进行先序遍历和中序遍历，可以得到唯一的二叉树，这是基于什么性质？A.先序遍历的第一个节点是根节点B.中序遍历可以将节点分为左子树和右子树C.先序和中序遍历结合可以唯一确定二叉树的结构D.二叉树的节点具有唯一标识31、深度为h的满二叉树共有多少个节点？A.2^hB.2^h-1C.2^(h+1)-1D.2^(h-1)32、用邻接表存储图时，存储空间的大小与什么因素有关？A.只与顶点数有关B.只与边数有关C.与顶点数和边数都有关D.与顶点数和边数都无关33、对n个记录的关键字序列进行直接插入排序，最坏情况下的时间复杂度为多少？A.O(n)B.O(nlogn)C.O(n^2)D.O(logn)34、对n个记录的关键字序列进行快速排序，最好情况下的时间复杂度为多少？A.O(n)B.O(nlogn)C.O(n^2)D.O(logn)35、在散列表中，处理冲突的方法之一是链地址法，该方法的基本思想是？A.发生冲突时将关键字放到下一个空闲位置B.将所有哈希地址相同的关键字构成一个单链表C.使用双哈希函数解决冲突D.重新计算哈希函数直至找到空位36、下列排序算法中，哪种算法是不稳定的？A.冒泡排序B.直接插入排序C.归并排序D.快速排序37、一个有序表为(1,3,5,7,9,11,13,15,17)，采用二分查找法查找关键字13，需要比较多少次？A.2B.3C.4D.538、若某棵二叉树的先序遍历序列为ABDECF，中序遍历序列为DBEAFC，则该二叉树的后序遍历序列为？A.DEBFCAB.DEFBACC.EDBFCAD.EDBCFA39、在一个有向图中，所有顶点的度之和等于边数的几倍？A.1倍B.2倍C.3倍D.4倍40、下列数据结构中，适合用于实现递归调用的数据结构是？A.队列B.栈C.树D.图41、用邻接矩阵存储一个有n个顶点、e条边的无向图，矩阵中非零元素的个数为多少？A.eB.2eC.e-1D.2e+142、在一棵二叉排序树中删除一个叶节点，需要调整指针吗？A.需要，必须重新连接其父节点的指针B.不需要，直接删除即可C.需要，必须调整其右孩子的指针D.需要，必须调整其左孩子的指针43、若用链表表示一个线性表，则下列操作中最适合用链表实现的是？A.随机访问第i个元素B.按值查找元素C.在第i个位置插入元素D.按序号查找元素44、对有n个记录的序列进行堆排序，时间复杂度为多少？A.O(n)B.O(nlogn)C.O(n^2)D.O(logn)45、深度为5的平衡二叉树，最少需要多少个节点？A.12B.15C.4D.846、在顺序表中，插入一个元素需要平均移动多少个元素？设表长为nA.nB.n/2C.(n+1)/2D.(n-1)/247、以下关于栈的说法正确的是A.栈是先进先出的线性表B.栈只能在顺序存储结构中实现C.栈顶元素永远是最后插入的元素D.栈不允许空栈48、设循环队列的存储空间为Q(1:50)，初始状态front=rear=50。经过一系列正常的入队与退队操作后，front=rear=25，此后退出一个元素，则循环队列中的元素个数为A.24B.25C.49D.0或5049、一棵度为3的树中，度为3的结点有2个，度为2的结点有1个，度为1的结点有2个，则叶子结点个数为A.5B.6C.7D.850、对长度为n的有序表进行二分查找，最坏情况下需要比较的次数为A.log2nB.log2n-1C.⌊log2n⌋+1D.⌈log2n⌉51、下列排序算法中，最坏情况下时间复杂度为O(nlogn)的是A.冒泡排序B.快速排序C.堆排序D.直接插入排序52、设哈希表长为m，散列函数为H(key)，采用链地址法处理冲突，则同一哈希地址上的链长度为A.最多为mB.与关键字的分布有关C.固定为1D.最多为n/m且一定相等53、在图的结构中，无向图的邻接表表示中，边表中每个结点对应图中的一条A.顶点B.边C.路径D.回路54、设一组初始记录关键字序列为(45,80,55,40,42,85)，则以40为基准的第一趟快速排序结果是A.(40,42,55,45,80,85)B.(40,42,45,55,80,85)C.(42,40,45,55,80,85)D.(42,40,55,45,80,85)55、二叉树的第i层上至多有A.2^(i-1)个结点B.2^i个结点C.2^i-1个结点D.i个结点56、下列数据结构中，不是一种线性结构的是A.栈B.队列C.二叉树D.线性表57、已知一棵完全二叉树有768个结点，则该树中度为1的结点个数为A.0B.1C.2D.358、设有序表中有1000个元素，则用二分查找时，查找长度最大的元素个数至多为A.9B.10C.11D.1259、对稀疏矩阵采用三元组顺序表存储的主要目的是A.便于进行矩阵的插入和删除操作B.便于进行矩阵的转置操作C.减少存储空间D.提高矩阵乘法的运算速度60、设一组记录的关键字为(49,38,65,97,76,13,27,50)，按冒泡排序算法进行从小到大的排序，第一趟排序后的结果是A.(38,49,65,76,13,27,50,97)B.(38,49,65,76,13,27,97,50)C.(13,38,49,65,76,27,50,97)D.(38,49,13,27,65,76,50,97)61、设森林F中有三棵树，第一、第二、第三棵树的结点个数分别为M1、M2、M3，则与森林F对应的二叉树右子树上的结点个数是A.M1-1B.M2-1C.M3D.M2+M362、在下列排序方法中，关键字的比较次数与记录的初始排列顺序无关的是A.直接插入排序B.快速排序C.堆排序D.冒泡排序63、设无向图G中有n个顶点e条边，则所有顶点的度数之和为A.nB.eC.2eD.2n64、假设以数组Q[m]存放循环队列中的元素，同时设置一个标志tag，以tag==0和tag==1来区分尾指针rear和头指针front相同时的队列状态是空还是满，则与此命题相符的操作是A.队满判断：(rear+1)%m==front&&tag==1B.队满判断：rear==frontC.队空判断：rear==front&&tag==1D.入队操作不需判断队满65、哈希表中发生冲突的原因是A.哈希函数选择不当B.记录的关键字互不相同C.哈希函数的值域小于关键字的可能取值个数D.哈希表容量过大66、在顺序存储的线性表中，按位查找的时间复杂度为：A.O(1)B.O(n)C.O(logn)D.O(n²)67、将一个栈的入栈序列为1、2、3、4，可能的出栈序列为：A.4312B.4321C.1423D.314268、循环队列采用数组实现时，队列满的条件是：A.front==rearB.(rear+1)%maxSize==frontC.front==rear+1D.rear==maxSize-169、设某二叉树中度为2的节点数为n，则叶子节点数为：A.nB.n+1C.n-1D.2n70、完全二叉树共有127个节点，其叶子节点数为：A.63B.64C.62D.6571、下列排序算法中，平均时间复杂度为O(nlogn)的是：A.冒泡排序B.选择排序C.快速排序D.插入排序72、在哈希表中处理冲突时，线性探测法的缺点是：A.容易产生堆积现象B.查找效率低C.占用空间大D.无法存储相同关键字73、对n个记录进行快速排序，最坏情况下的时间复杂度为：A.O(n)B.O(nlogn)C.O(n²)D.O(logn)74、邻接矩阵表示的图，顶点数为n，求某顶点的度所需时间为：A.O(1)B.O(n)C.O(n²)D.O(n+e)75、下列数据结构中，不适合用于实现栈的是：A.数组B.链表C.队列D.单链表76、二叉树前序遍历序列为ABDECFG，中序遍历序列为DBEAFCG，后序遍历序列为：A.DEBFCGAB.DEBFGCAC.DBEFACGD.DBEFGCA77、深度为k的二叉树至多有个节点：A.2^kB.2^k-1C.2^(k-1)D.2^(k+1)-178、下列算法中，用于求图中单源最短路径的是：A.Prim算法B.Kruskal算法C.Dijkstra算法D.拓扑排序79、设输入序列为1、2、3、4、5，经过栈操作后可得到的输出序列为：A.34512B.54123C.32154D.4351280、堆排序的最好、最坏和平均时间复杂度均为：A.O(n)B.O(nlogn)C.O(n²)D.O(logn)81、有向图G采用邻接表存储，求解单源最短路径问题应选择：A.Prim算法B.Dijkstra算法C.DFSD.拓扑排序82、在一棵具有n个节点的完全二叉树中，节点i(1≤i≤n)的父节点编号为：A.⌊i/2⌋B.⌈i/2⌉C.2iD.2i+183、下列查找方法中，适用于顺序存储且查找效率高的是：A.顺序查找B.二分查找C.分块查找D.哈希查找84、对n个元素的序列进行归并排序，所需辅助空间为：A.O(1)B.O(logn)C.O(n)D.O(n²)85、B树插入操作时，若节点关键字个数超过2t-1，则需要进行：A.删除操作B.分裂操作C.旋转操作D.合并操作86、若对n阶行列式进行存储压缩，采用行优先顺序存储在数组中，则元素a[i][j]的地址计算公式为（设每个元素占w个存储单元）：A.LOC(i,j)=base+(i×n+j)×wB.LOC(i,j)=base+((i-1)×n+j-1)×wC.LOC(i,j)=base+(i+n×j)×wD.LOC(i,j)=base+((i-1)×n+j)×w87、设森林F中有三棵树，节点数分别为m1、m2、m3，则与森林F对应的二叉树中，右子树上的节点数为：A.m2+m3B.m1+m2C.m1+m3D.m1+m2+m388、设一组初始记录关键字为(45,80,55,40,42,85)，以40为基准进行快速排序，第一趟划分后的结果为：A.(40,42,55,45,80,85)B.(40,42,45,55,80,85)C.(42,40,45,55,80,85)D.(42,40,55,45,80,85)89、在一个链表结构中，删除指定节点p的前驱节点，需要的时间复杂度为：A.O(1)B.O(n)C.O(logn)D.O(n²)90、设一组记录关键字为(12,13,11,18,60,15,7,18,25,100)，采用直接插入排序，第三趟排序后的结果为：A.(12,13,11,18,60,15,7,18,25,100)B.(11,12,13,18,60,15,7,18,25,100)C.(11,12,13,18,60,7,15,18,25,100)D.(11,12,13,18,15,60,7,18,25,100)91、有8个顶点，12条边的连通无向图，其生成树包含的边数为：A.7B.8C.12D.2092、在顺序存储的线性表中，按值查找一个元素时，其平均时间复杂度为。A.O(1)B.O(logn)C.O(n)D.O(n²)93、一个栈的入栈序列是a,b,c,d,e，则栈的不可能输出序列是。A.edcbaB.decbaC.dceabD.abcde94、循环队列存储在数组A[0..m]中，则入队时的操作为。A.rear=rear+1B.rear=(rear+1)%(m-1)C.rear=(rear+1)%mD.rear=(rear+1)%(m+1)95、带头结点的链表头部插入一个新节点s的操作是。A.s->next=head;head=sB.s->next=head->next;head->next=sC.head=s;s->next=headD.s->next=head;head=head->next96、广义表((a,b,c),(d,e))的长度和深度分别为。A.2,3B.3,2C.2,2D.3,397、将森林转换为对应的二叉树，若二叉树中节点u是v的父节点，则原森林中u和v的关系是。A.u是v的双亲B.u是v的长子C.u是v的兄弟D.u是v的父节点或长子98、一棵完全二叉树有1001个节点，则其中叶子节点数为。A.500B.501C.1000D.100199、对含n个关键字的无序序列进行冒泡排序，最好情况下的时间复杂度为。A.O(n)B.O(nlogn)C.O(n²)D.O(logn)100、对下列关键字序列作快速排序，所需比较次数最少的是。A.{25,18,46,29,78,12,2,48}B.{48,25,32,78,64,56,40,12}C.{12,25,48,56,64,78,32,40}D.{78,64,56,48,40,32,25,12}

参考答案及解析1.【参考答案】A【解析】重要且紧急的任务属于第一象限，需要优先立即处理，确保关键事项不延误，维持工作有序推进。2.【参考答案】B【解析】SMART原则中M代表Measurable即可衡量性，要求目标设定必须具备明确的衡量标准，便于追踪和评估。3.【参考答案】B【解析】自主管理中的授权强调适度原则，既要给予充分信任和支持，又要保持必要的指导和监督机制。4.【参考答案】C【解析】团队自主管理依赖成员能力、凝聚力和共同目标，外部强制干预会削弱团队自主性，不利于自主管理实施。5.【参考答案】A【解析】自主管理的核心理念是促进个人成长与组织发展的良性互动，实现个人价值与组织目标的双赢局面。6.【参考答案】C【解析】顺序存储结构支持随机访问，可通过下标直接定位任意元素，时间复杂度为O(1)。插入和删除操作需要移动大量元素，效率较低，故A、B错误。顺序存储可能预留较多空间，空间利用率不如链式存储，D错误。7.【参考答案】C【解析】入栈出栈模拟过程：a入栈，b入栈，b出栈入队（栈中a），c入栈，d入栈，d出栈入队，c出栈入队（栈中a），e入栈，f入栈，f出栈入队，e出栈入队，g入栈，g出栈入队，a出栈入队。栈中最多同时有a、e、f、g四个元素，故容量至少为4。8.【参考答案】B【解析】数组下标范围0到m，共m+1个位置。循环队列入队时队尾指针后移，为利用循环特性需取模运算。由于数组长度为m+1，应使用rear=(rear+1)%(m+1)实现循环。选项C的模m会导致越界，选项D的模m+2范围过大。9.【参考答案】D【解析】队列溢出现在队列已满时进行入队操作。出队和读队头操作不会增加队列元素个数，只有当队列满时入队才会溢出。因此B、C、D选项描述的操作都不会导致队列溢出错误。10.【参考答案】B【解析】高度为h的二叉树，每层最多有2^(i-1)个结点（i为层数）。高度为5时，最多结点数为2^1+2^2+2^3+2^4+2^5=2+4+8+16+32=62。但题目中高度定义若从第1层开始计算，最多为2^5-1=31个结点，符合完全二叉树的结点总数公式。11.【参考答案】A【解析】先序确定根为A，中序中A左侧DBGE为左子树，右侧CHF为右子树。递归分析可得左子树先序BDEG、中序DBGE，右子树先序FCH、中序CHF。继续递归求解各子树结构，最终得到后序遍历为DGEBHFCA。12.【参考答案】C【解析】快速排序最坏情况O(n²)，冒泡排序最坏情况O(n²)，直接插入排序最坏情况O(n²)。堆排序在最坏、平均情况下时间复杂度均为O(nlog₂n)，比较次数最少。堆排序始终维持堆结构，不受初始序列有序程度影响。13.【参考答案】C【解析】快速排序的最坏情况发生在每次划分都极度不平衡时，如序列已有序且选取第一个元素为基准。此时每次划分只减少一个元素，递归深度为n，总比较次数为n(n-1)/2，时间复杂度为O(n²)。最好情况和平均情况均为O(nlog₂n)。14.【参考答案】D【解析】二叉排序树的查找过程类似于二分查找，从根结点开始比较。查找效率取决于树的高度，而树的高度又由插入顺序决定，即与树的形状有关。退化的二叉排序树（单支树）高度为n，查找效率退化为O(n)；平衡二叉树高度为log₂n，查找效率为O(log₂n)。15.【参考答案】D【解析】在B-树中，若一个结点有k个子树，则该结点必有k-1个关键字。因此关键字数量总是比子树数量少1，不可能少于子树数量。A、B、C均为B-树的基本性质描述，是正确的。B-树是一种平衡的多路查找树，常用于数据库和文件系统的索引。16.【参考答案】D【解析】稳定排序是指在排序前后，相同关键字元素的相对位置保持不变。冒泡排序、归并排序、简单插入排序均为稳定排序。快速排序在交换过程中可能改变相同关键字元素的相对顺序，属于不稳定排序。希尔排序、选择排序、堆排序也是不稳定排序。17.【参考答案】D【解析】根据邻接矩阵，V1与V2、V3相连，V2与V1、V4相连，V3与V1、V4、V5相连，V4与V2、V3、V5相连，V5与V3、V4相连。从V1出发，先访问V3（邻接点中序号较小），再从V3访问V5，从V5访问V4，从V4访问V2。深度优先搜索序列为V1→V3→V5→V4→V2。18.【参考答案】C【解析】根据握手定理，无向图中所有顶点的度数之和等于边数的2倍。设总顶点数为n，则有3×4+4×3+(n-7)×2=16×2，即12+12+2n-14=32，解得2n=24，n=12。因此图G共有12个顶点，其中7个已知度数的顶点加上5个度数为2的顶点。19.【参考答案】C【解析】冲突是指不同的关键字经过哈希函数计算后得到相同的存储地址。即使关键字个数小于表长，也可能发生冲突。冲突是哈希表的固有特性，无法完全避免，只能通过选择合适的哈希函数和冲突处理方法来减少冲突频率。选项C准确描述了冲突的本质原因。20.【参考答案】A【解析】快速排序的速度取决于每次划分是否均衡。选项C和D为有序序列，若选第一个或最后一个为基准，划分极度不平衡，速度最慢。选项A的序列中基准元素能将数组较均衡地划分，使递归树接近平衡，排序效率最高。最优情况下时间复杂度为O(nlog₂n)。21.【参考答案】B【解析】分块查找将表分成若干块，块内无序但块间有序。256个元素分16个块，每块16个元素。查找时需先在索引表中确定所在块，再在块内顺序查找。若采用顺序查找索引表，最多查16次确定块位置，再加块内最多16次，共32次。但实际最优分块方式下，索引表大小约√256=16，加上块内查找，最多约16+4=20次比较。22.【参考答案】B【解析】外层循环执行n次，内层循环对每次外层循环执行m次，内层语句sum+=i*j被执行n×m次。因此时间复杂度为O(n×m)。当n和m规模相当时退化为O(n²)，但一般情况应表示为O(n×m)，反映两个独立变量的影响。23.【参考答案】A【解析】删除p结点之后的结点，即删除p->next所指结点。操作时需将p的next指针指向被删除结点的下一个结点，即执行p->next=p->next->next。此操作跳过了原p->next结点，实现了删除效果。选项B、D改变了p的指向而非删除操作，选项C会导致循环引用。24.【参考答案】C【解析】对称矩阵压缩存储只需存储上三角或下三角部分。按行序存储下三角元素，a85位于第8行第5列，属于下三角。前7行元素个数为1+2+...+7=28个，第8行前5个元素为a81至a85，共5个。因此a85的地址为28+5=33。25.【参考答案】C【解析】该算法为递归计算阶乘。每次递归调用时n减1，直到n=1时返回。递归深度为n层，每层执行一次乘法和一次递归调用，基本操作执行次数与n成正比。因此时间复杂度为O(n)。递归调用栈空间也为O(n)。26.【参考答案】B【解析】在顺序表中插入元素时，需要将第i个位置及之后的所有元素向后移动一位。第i个位置到第n个位置共有n-i+1个元素需要移动，因此选B。27.【参考答案】C【解析】对于选项C，若3先出栈，则1和2必须在栈中，栈顶为2，2必须先于1出栈，故3,1,2,...不可能实现。选项C不可能是栈的输出序列。28.【参考答案】A【解析】每执行一次出队操作，front向后移动一位并取模；每执行一次入队操作，rear向后移动一位并取模。经过k次入队和m次出队后，front=m%n，rear=k%n，选A。29.【参考答案】D【解析】在完全二叉树中，设度为0的节点数为n0，度为1的节点数为n1，度为2的节点数为n2。根据性质有n0=n2+1，且n=n0+n1+n2。由此可推得叶子节点数n0=⌈n/2⌉，即⌈(n+1)/2⌉，选D。30.【参考答案】C【解析】先序遍历的第一个节点是根节点，在中序遍历中找到该根节点，可将其左右两侧分别确定左子树和右子树。递归地应用此方法，先序和中序遍历序列可以唯一确定一棵二叉树的结构，选C。31.【参考答案】B【解析】满二叉树的每一层都达到最大节点数。深度为h的满二叉树，各层节点数分别为2^0,2^1,...,2^(h-1)，总节点数为等比数列求和：2^0+2^1+...+2^(h-1)=2^h-1，选B。32.【参考答案】C【解析】邻接表存储图时，需要存储所有顶点的头结点（共n个）以及所有边对应的节点（无向图共2e个，有向图共e个）。因此存储空间与顶点数和边数都有关，选C。33.【参考答案】C【解析】直接插入排序在最坏情况下（待排序序列为逆序），每个元素都需要与其前面的所有已排序元素进行比较和移动，第i个元素需要比较i-1次，总比较次数为n(n-1)/2，时间复杂度为O(n^2)，选C。34.【参考答案】B【解析】快速排序的最好情况下，每次划分都能将序列均匀分成两个长度近似相等的子序列，递归树的深度为logn，每层处理n个元素，故时间复杂度为O(nlogn)，选B。35.【参考答案】B【解析】链地址法的基本思想是：将所有哈希地址相同的关键字链接到同一个单链表中，散列表的每个单元存放链表的头指针。这样无论有多少个关键字哈希到同一地址，都可以通过链表解决冲突，选B。36.【参考答案】D【解析】稳定排序是指在排序过程中，相同关键字的元素的相对位置不变。冒泡排序、直接插入排序和归并排序都是稳定排序，而快速排序在划分过程中可能改变相同元素的相对顺序，是不稳定排序，选D。37.【参考答案】B【解析】第一次查找中间位置（下标5，值为11），13>11，在右半部分查找；第二次查找中间位置（下标7，值为13），13=13，找到。共比较3次，选B。38.【参考答案】C【解析】由先序可知根为A，在中序中D、B、E在A左，F、C在A右。左子树先序为BDE、中序为DBE，可得左子树根为B，左孩子为D，右孩子为E。右子树先序为CF、中序为FC，可得右子树根为C，左孩子为F。后序遍历为EDBFCA，选C。39.【参考答案】B【解析】在有向图中，每条边对度之和贡献2（入度和出度各计一次），因此所有顶点的度之和等于边数的2倍。在无向图中同样成立，每条边贡献2个度，选B。40.【参考答案】B【解析】栈具有后进先出（LIFO）的特性，非常适合实现递归调用。每次递归调用时，将返回地址和局部变量压入栈中，递归返回时从栈中弹出这些信息，实现递归的自动管理，选B。41.【参考答案】B【解析】无向图的邻接矩阵是对称矩阵，每条边(u,v)在矩阵中对应两个非零元素：A[u][v]=1和A[v][u]=1。因此e条边在邻接矩阵中对应2e个非零元素，选B。42.【参考答案】B【解析】删除叶节点时，该节点没有左孩子和右孩子，只需将其父节点对应方向的指针置为null即可，不需要调整其他指针，操作简单，选B。43.【参考答案】C【解析】链表不支持随机访问，但可以方便地在已知位置插入或删除元素，只需修改指针即可，时间复杂度为O(1)（假设已定位）。而顺序表插入需要移动大量元素，选C。44.【参考答案】B【解析】堆排序的时间复杂度分析如下：建堆时间为O(n)，每次调整堆的时间为O(logn)，共需进行n-1次调整，因此总时间复杂度为O(nlogn)，选B。45.【参考答案】A【解析】设N(h)为深度为h的平衡二叉树的最少节点数，满足递推关系N(h)=N(h-1)+N(h-2)+1，其中N(0)=0,N(1)=1。计算得：N(2)=2,N(3)=4,N(4)=7,N(5)=12，选A。

（注：选项中B项误植为"4"，应为B.15）46.【参考答案】C【解析】顺序表插入时，若插在第i个位置，则需从第i个元素到第n个元素依次后移。插入位置等概率取1至n+1时，平均移动次数为n/2。但考虑到插入位置可从第1位到第n+1位，实际平均移动元素数为(n+1)/2。47.【参考答案】C【解析】栈是一种特殊的线性表，只允许在一端进行插入和删除操作，这一端称为栈顶。栈的特点是后进先出（LIFO），即最后插入的元素最先被取出，因此栈顶元素永远是最后插入的元素。栈既可以用顺序存储也可以用链式存储，空栈是允许存在的。48.【参考答案】D【解析】循环队列中front=rear有两种情况：队列为空或队列满。当初始front=rear=50时，若经过操作后front=rear=25，此时队列可能为空也可能为满（容量50）。若之前队列为空，退队操作非法；若队列为满，退队后元素个数为49。但由于front=rear无法区分空与满，所以答案可能是0或49，选项中D最接近分析逻辑，实际应理解为无法确定当前状态。49.【参考答案】C【解析】设叶子结点（度为0）有n0个。树的结点总数n=n0+n1+n2+n3=n0+2+1+2=n0+5。树的分支总数等于所有结点的度数之和，也为n-1。因此n0×0+2×1+1×2+2×3=n-1，即10=n0+4，解得n0=6。等等，重新计算：分支数=1×2+2×1+3×2=2+2+6=10，n-1=10，所以n=11，n0=11-5=6。但再核对公式n0=1+n2+2×n3=1+1+4=6。答案应为B，但根据题干数据再核算：n0=n2+2n3+1=1+4+1=6，答案为B。修正为B。50.【参考答案】D【解析】二分查找的过程可以用二叉判定树来描述，树的高度即为最坏情况下的比较次数。对于长度为n的有序表，判定树的高度为⌈log2(n+1)⌉。当n=2^k-1时，高度为k=log2(n+1)=⌈log2n⌉。综合来看，最坏比较次数为⌈log2n⌉。51.【参考答案】C【解析】冒泡排序和直接插入排序最坏情况时间复杂度为O(n²)。快速排序最坏情况也是O(n²)，发生在每次划分都极不均匀时。堆排序无论最好、最坏还是平均情况，时间复杂度均为O(nlogn)，因为它每次都是通过堆调整来选出最大（小）元素，调整过程的复杂度由树高决定。52.【参考答案】B【解析】链地址法将哈希地址相同的记录链接在同一链表中。链表的长度取决于关键字的分布情况：如果关键字均匀分布，则各链表长度接近n/m；如果关键字分布不均匀，某些链表可能很长而另一些很短。因此链长度与关键字分布有关，不是固定的。53.【参考答案】B【解析】无向图的邻接表中，每个顶点对应一个链表头结点，其后的边表结点存储与该顶点相邻接的顶点信息。由于是无向图，每条边(u,v)会在顶点u的边表中出现一个结点，也会在顶点v的边表中出现一个结点，即一条边对应两个边表结点。因此边表中每个结点对应图中的一条边。54.【参考答案】C【解析】以40为基准，从左向右扫描，45>40，跳过；从右向左扫描，85>40，跳过；80>40，跳过；42>40，跳过；55>40，跳过；80>40，跳过。全部大于40，需要将40与第一个大于它的元素45交换，得到(40,80,55,45,42,85)。但这不符合标准快排过程。重新按标准方法：设low指向45，high指向85，pivot=40。high从右找≤40的，42>40继续，45>40，80>40，55>40，85>40，都大于40，交换40与45位置，结果为(40,80,55,45,42,85)。选C不符合，重新分析标准快排过程得答案为C：(42,40,45,55,80,85)。55.【参考答案】A【解析】二叉树的第1层（根结点所在层）至多有1=2^0个结点，第2层至多有2=2^1个结点，第3层至多有4=2^2个结点，依此类推，第i层至多有2^(i-1)个结点。56.【参考答案】C【解析】线性结构中的数据元素之间存在一对一的线性关系。栈和队列是运算受限的线性表，仍属于线性结构。线性表本身就是典型的线性结构。二叉树中的元素之间存在一对多的层次关系，属于非线性结构。57.【参考答案】B【解析】完全二叉树的性质：度为1的结点个数只能是0或1。设二叉树总结点数为n=n0+n1+n2，其中n0为叶子结点数，n2为度为2的结点数。又有n0=n2+1，所以n=2n0+n1-1。代入n=768，得2n0+n1=769。若n1=0，则2n0=769，n0不是整数，不成立。若n1=1，则2n0=768，n0=384，成立。因此度为1的结点个数为1。58.【参考答案】B【解析】二分查找的最大查找长度等于判定树的高度。判定树是一棵平衡二叉树，高度h满足2^(h-1)≤n<2^h。当n=1000时，2^9=512，2^10=1024，所以h=10。查找长度最大的元素即为位于第10层的结点。59.【参考答案】C【解析】稀疏矩阵中有很多零元素，采用三元组顺序表（行号、列号、值）只存储非零元素，可以大大减少存储空间。虽然三元组存储也便于转置操作，但这不是主要目的。插入删除和乘法速度也不是三元组存储的主要优势。60.【参考答案】A【解析】冒泡排序第一趟从第一个记录开始，依次比较相邻两个记录的关键字，若逆序则交换。比较过程：49>38交换得(38,49,65,...)，65>49不变，97>65不变，97>76交换得(38,49,65,76,97,...)，97>13交换得(...,13,97,50)，97>27交换得(...,13,27,97)，97>50交换得(...,13,27,50,97)。第一趟结果为(38,49,65,76,13,27,50,97)，最大值97已沉到末尾。61.【参考答案】D【解析】森林转换为二叉树的方法：将第一棵树的根作为二叉树的根，第一棵树的子森林转换为根的左子树，其余各棵树的森林转换为根的右子树。因此，对应二叉树的右子树由第二棵和第三棵树组成，其结点个数为M2+M3。62.【参考答案】C【解析】直接插入排序和冒泡排序在最好情况（有序）下比较次数最少，最坏情况（逆序）下最多，与初始排列有关。快速排序的性能也依赖于划分的均匀程度，与初始排列有关。堆排序的建堆和调整过程不受初始排列影响，无论最好、最坏情况比较次数都约为O(nlogn)，与初始排列顺序无关。63.【参考答案】C【解析】在无向图中，每条边连接两个顶点，因此每条边为两个顶点的度数各贡献1。所以所有顶点的度数之和等于边数的2倍，即2e。这是图论中的握手定理。64.【参考答案】A【解析】使用tag标志区分空队列和满队列时，rear==front时若tag==0则为空，若tag==1则为满。队满的条件是尾指针的下一个位置等于头指针且tag==1，即(rear+1)%m==front&&tag==1。入队操作需要判断队满，出队操作需要判断队空。65.【参考答案】C【解析】冲突是指不同的关键字通过哈希函数计算得到相同的哈希地址。哈希函数的值域（可能的哈希地址数）如果小于关键字的可能取值个数，根据鸽巢原理，必然会有不同关键字映射到同一地址，从而产生冲突。即使哈希函数选择恰当、表容量足够大，只要值域小于关键字空间，冲突就不可避免。66.【参考答案】A【解析】顺序表支持随机访问，通过下标直接定位元素，查找时间复杂度为O(1)。O(n)是链表的查找复杂度。67.【参考答案】B【解析】栈是后进先出结构。依次入栈1、2、3、4后全部出栈，得到4321。其他选项违背栈的操作规则。68.【参考答案】B【解析】循环队列牺牲一个存储单元来区分队空队满。队满时(Qrear+1)%maxSize==Qfront，队空时Qfront==Qrear。69.【参考答案】B【解析】二叉树性质：叶子节点数等于度为2的节点数加1，即n0=n2+1。这是二叉树的基本性质之一。70.【参考答案】B【解析】完全二叉树节点数n=127，叶子节点数n0=⌈n/2⌉=64。或根据性质：n0=⌊n/2⌋+1当n为奇数时不适用，直接计算得64。71.【参考答案】C【解析】快速排序平均时间复杂度为O(nlogn)。冒泡、选择、插入排序的平均复杂度均为O(n²)。72.【参考答案】A【解析】线性探测法容易产生一次聚集（堆积）现象，导致非冲突key也需多次探测，降低查找效率。二次探测可减轻堆积。73.【参考答案】C【解析】快排最坏情况发生在每次划分都极不均匀时（如已排序序列），时间复杂度退化为O(n²)。平均情况为O(nlogn)。74.【参考答案】B【解析】邻接矩阵中第i行的非零元素个数即为该顶点的度，需遍历一行共n个元素，时间复杂度为O(n)。75.【参考答案】C【解析】栈可用数组或链表实现。队列是另一种数据结构，其进出规则与栈不同，不能直接作为栈的实现基础。76.【参考答案】A【解析】由前序A为根，中序DBE在左、FCG在右，递归构造二叉树。后序遍历结果为DEBFCGA。77.【参考答案】B【解析】深度为k的二叉树最多有2^k-1个节点（满二叉树）。第i层最多2^(i-1)个节点，求和得2^k-1。78.【参考答案】C【解析】Dijkstra算法用于求带权图的单源最短