2025重庆大学计算机考研数据结构真题

一个n阶（n>1）三对角矩阵A按行优先顺序压缩存放在一维数组B中，则B中的元素个数是______。

A. 3n

B. n2

C. 2n

D. 3n-2

对稀疏矩阵进行压缩存储的目的是______。

A. 便于进行矩阵运算

B. 便于输入和输出

C. 节省存储空间

D. 降低运算的时间复杂度

下列排序算法中，最坏情况下元素移动最少的是（）

A.冒泡排序

B.直接插入排序

C.快速排序

D.简单选择排序

已知算法A用于检查字符串中各类括号是否匹配，A执行过程中使用初始为空的栈保存遇到的括号。若栈的容量是3，则下列选项中，A不能处理的是（）。

A.(a+[b+(c+d))/e]+f)+g-h

B.[a*((b+c)/(d-e)+f/g)-h]

C.[a*(b-(c-d)*e/(f+g))-h]

D.[a-(b+[c*(d+e)-f]+g+h)]

下列关于二叉树及森林的叙述中，正确的是（）。

A.完全二叉树中不存在度为1的结点

B.任意一个森林都可以转换为一棵二叉树

C.二叉树的分支结点个数比叶结点个数少

D.表达式树的根中保存的是最先计算的运算符

下列关于散列方法处理冲突的叙述中，正确的是（）。

A.只要散列表不满，线性探查再散列一定能找到一个空闲位置

B.只要散列表不满，二次探查再散列一定能找到一个空闲位置

C.线性探查再散列处理的冲突，一定是发生在同一空间的冲突

D.二次探查再散列处理的冲突，一定是发生在非同义词之间的冲突

给定7个不同的关键字，能够构成的不同4阶B树的个数最多是（）。

A.7    B.8    C.9    D.10

已知查找表中有400个元素，查找每个元素的概率相同，采用分块查找法进行查找，且均匀分块。若采用顺序查找法确定元素所在的块，且块内也采用顺序查找法，为使查找效率最高，则每块包含元素个数应为（）。

A.8    B.10    C.20    D.25

下列关于图的叙述中，正确的是（）。

A. 有向图必存在入度为0的顶点

B. 有向无环图的拓扑有序序列存在且唯一

C. 各顶点的度均大于等于2的无向图必有回路

D. 可用BFS算法求出带权图中每一对顶点间的最短路径