大学（计算机科学与技术）数据结构2026年阶段测试题.doc

大学（计算机科学与技术）数据结构2026年阶段测试题

（考试时间：90分钟 满分100分） 班级______ 姓名______

一、单项选择题（总共10题，每题3分，每题只有一个正确答案，请将正确答案填写在括号内）
1. 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。
A. 顺序表 B. 双链表 C. 带头结点的双循环链表 D. 单循环链表
2. 设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（ ）。
A. 13 B. 33 C. 18 D. 40
3. 若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ）。
A. 9 B. 11 C. 15 D. 不确定
4. 对有n个记录的表作快速排序，在最坏情况下，算法的时间复杂度是（ ）。
A. O(n) B. O(n^2) C. O(nlog2n) D. O(n^3)
5. 设哈希表长为14，哈希函数是H(key)=key%11，表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的元素加到表中，用二次探测再散列法解决冲突，则放入的位置是（ ）。
A. 8 B. 3 C. 5 D. 9
6. 一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（ ）。
A. 2 3 4 1 5 B. 5 4 1 3 2 C. 2 3 1 4 D. 1 5 4 3 2
7. 对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（ ）。
A. O(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1)
8. 若串S='software'，其子串的数目是（ ）。
A. 8 B. 37 C. 36 D. 9
9. 深度为5的完全二叉树的结点数不可能是（ ）。
A. 15 B. 16 C. 17 D. 18
10. 对n个关键字作快速排序，在最坏情况下，算法的时间复杂度是（ ）。
A. O(n) B. O(n^2) C. O(nlog2n) D. O(n^3)

二、多项选择题（总共5题，每题4分，每题至少有两个正确答案，请将正确答案填写在括号内）
1. 以下哪些是数据结构研究的内容（ ）。
A. 数据的逻辑结构 B. 数据的存储结构 C. 数据的运算 D. 数据的类型
2. 下列关于栈的叙述中正确的是（ ）。
A. 栈顶元素最先能被删除 B. 栈底元素最后才能被删除 C. 栈底元素是最先被插入的元素 D. 栈按先进后出组织数据
3. 一棵二叉树的前序遍历序列为ABCDEFG，中序遍历序列为CBDAFGE，则其后序遍历序列为（ ）。
A. CDBGFEA B. CDBFGEA C. CDBAGFE D. CDBFEGA
4. 下列排序方法中，哪些是稳定的排序方法（ ）。
A. 直接插入排序 B. 冒泡排序 C. 快速排序 D. 归并排序
5. 以下哪些是哈希表解决冲突的方法（ ）。
A. 开放定址法 B. 链地址法 C. 再哈希法 D. 建立公共溢出区

三、判断题（总共10题，请判断对错，对的打√，错的打×，每题2分）
1. 数据元素是数据的最小单位。（ ）
2. 线性表的链式存储结构优于顺序存储结构。（ ）
3. 完全二叉树一定是满二叉树。（ ）
4. 快速排序在所有情况下的时间复杂度都是O(nlog₂n)。（ ）
5. 哈希表的平均查找长度与哈希函数、哈希表的装填因子有关。（ ）
6. 栈和队列都是操作受限的线性表。（ ）
7. 顺序存储的线性表可以随机存取。（ ）
8. 二叉排序树的中序遍历序列是一个有序序列。（ ）
9. 二路归并排序是一种稳定的排序方法。（ ）
10. 数据的逻辑结构是指数据在计算机中的存储形式。（ ）

四、简答题（总共3题，每题10分）
1. 简述顺序表和链表的优缺点。
2. 什么是平衡二叉树？简述平衡二叉树的插入和删除操作。
3. 简述哈希表的基本概念，并说明哈希函数的设计原则。

五、算法设计题（总共1题，20分）
已知一个整数数组A，设计一个算法将数组中的元素按从小到大的顺序排列。要求使用快速排序算法，并描述算法的基本思想和步骤。

答案：
一、单项选择题
1. A
2. B
3. B
4. B
5. D
6. B
7. C
8. B
9. A
10. B

二、多项选择题
1. ABC
2. ABCD
3. A
4. ABD
5. ABCD

三、判断题
1. ×
2. ×
3. ×
4. ×
5. √
6. √
7. √
8. √
9. √
10. ×

四、简答题
1. 顺序表优点：随机存取效率高，存储密度大；缺点：插入和删除操作效率低，可能需要移动大量元素。链表优点：插入和删除操作效率高；缺点：随机存取效率低，需要额外的指针空间。
2. 平衡二叉树是一棵空树或它的左右两个子树的高度差的绝对值不超过为1，并且左右两个子树都是一棵平衡二叉树。插入操作：先按二叉排序树插入，再调整平衡因子；删除操作：先按二叉排序树删除，再调整平衡因子。
3. 哈希表是一种根据关键字直接访问数据的数据结构。哈希函数设计原则：计算简单、均匀分布、冲突尽可能少。

五、算法设计题
快速排序基本思想：选择一个基准元素将数组分为两部分，小于基准的放在左边，大于基准的放在右边，然后对左右两部分分别递归排序。步骤：1. 选择基准元素；2. 进行划分操作；3. 对左右子数组递归排序。