（图片大小可自由调整）
2025年大学试题(计算机科学)-数据结构考试近5年真题荟萃附答案
第I卷
一.参考题库(共80题)
1.对于两棵具有相同记录集合而具有不同形态的二叉搜索树，按中序遍历得到的结点序列是相同的。
2.已知某哈希表的装载因子小于1，哈希函数H（key）为关键字（标识符）的第一个字母在字母表中的序号，处理冲突的方法为线性探测开放定址法。试编写一个按第一个字母的顺序输出哈希表中所有关键字的算法。
3.在数据结构的讨论中把数据结构从逻辑上分为（）
A、内部结构与外部结构
B、静态结构与动态结构
C、线性结构与非线性结构
D、紧凑结构与非紧凑结构
4.在一个有向图中，所有顶点入度之和等于所有顶点出度之和的（）倍。
5.简述顺序表示的二叉树中各结点的编号规则。
6.一棵二叉树的中序、后序遍历序列分别为：GLDHBEIACJFK和LGHDIEBJKFCA，请回答：
画出上题中二叉树的中序线索二叉树。
7.已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为（）。
A、n-i+1
B、i
C、n-i
D、不确定
8.数据结构里，shop是一个结构体普通变量，它有一个成员变量叫price，则下列选项中关于使用price变量格式正确的是（）。
A、shop-price
B、shop.price
C、shop（price）
D、shopprice
9.对n个结点的二叉树用递归程序进行中序遍历时，最坏情况下要附加n个辅助存储空间。
10.设一棵完全二叉树有700个结点，则共有（）个叶子结点。
11.散列表的查找效率主要取决于散列表造表时选取的散列函数和处理（）的方法。
12.给定一个二叉树的任意一种周游的序列，可以唯一确定这个二叉树。
13.顺序表的存储结构是顺序存储的，则其查找第i元素就很容易，其时间复杂度是（）。
A、O（1）
B、O（n）
C、O（nn）
D、O（log2n）
14.一组记录的关键码为{46，79，56，38，40，84}，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（）。
A、40，38，46，56，79，84}
B、40，38，46，79，56，84}
C、40，38，46，84，56，79}
D、84，79，56，46，40，38}
15.设有10阶矩阵A，其对角线以上的元素aij均取值为-3，其他矩阵元素为正整数，现在将矩阵A压缩存放在一维树组F[m]中，则m为（）。
A、45
B、46
C、55
D、56
16.允许对队列进行的操作有（）。
A、对队列中的元素排序
B、取出最近进队的元素
C、在队头元素之前插入元素
D、删除队头元素
17.数据结构里，图按照边的不同，可分为无向图和（）。
A、有向图
B、无向图
C、混合图
D、以上都不对
18.判定一个栈ST（最多元素为m0）为空的条件是（）
A、ST-top0
B、ST-top=0
C、ST-topm0
D、ST-top=m0
19.设某单位职工工资表ST由“工资”、“扣除”和“实发金额”三项组成，其中工资项包括“基本工资”、“津贴”和“奖金”，扣除项包括“水”、“电”和“煤气”。 ⑴请用广义表形式表示所描述的工资表ST，并用表头和表尾求表中的“奖金”项； ⑵画出该工资表ST的存储结构。
20.假定一棵二叉树顺序存储在一维数组a中，则a[i]元素的左孩子元素为（），右孩子元素为（），双亲元素（i1）为（）。
21.设有一个栈，按A、B、C的顺序进栈，则下列（）为不可能的出栈序列。
A、ABC
B、CBA
C、CAB
D、ACB
22.栈可以作为实现过程调用的一种数据结构。
23.什么是抽象数据类型？抽象数据类型和面向对象的程序设计方法有什么关系？
24.采用链接方式存储线性表的优点是（）
A、便于随机存取
B、花费的存储空间较顺序存储少
C、便于插入和删除