2025年大学一年级（计算机科学与技术）数据结构基础试题及答案.doc

2025年大学一年级（计算机科学与技术）数据结构基础试题及答案

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

第I卷（选择题，共40分）
每题给出的四个选项中，只有一个选项是符合题目要求的。(总共20题，每题2分，在每小题给出的四个选项中，选出最符合题目要求的一项)
1. 以下关于数据结构的说法，正确的是
A. 数据结构只研究数据的逻辑结构
B. 数据结构只研究数据的存储结构
C. 数据结构研究数据的逻辑结构和存储结构
D. 数据结构与数据的逻辑结构和存储结构无关
2. 线性表的顺序存储结构中，元素之间的逻辑关系是通过
A. 指针表示
B. 相邻存储位置表示
C. 数组下标表示
D. 以上都不对
3. 在一个长度为n的顺序表中，删除第i个元素（1≤i≤n）时，需要移动的元素个数是
A. n - i
B. n - i + 1
C. i
D. i - 1
4. 栈的特点是
A. 先进先出
B. 后进先出
C. 随机进出
D. 以上都不对
5. 若进栈序列为1，2，3，4，进栈过程中可以出栈，则下列不可能的一个出栈序列是
A. 1，4，3，2
B. 2，3，4，1
C. 3，1，4，2
D. 3，4，2，1
6. 队列的特点是
A. 先进先出
B. 后进先出
C. 随机进出
D. 以上都不对
7. 循环队列中，队满的条件是
A. （rear + 1）% maxsize == front
B. rear == front
C. rear + 1 == front
D. 以上都不对
8. 对于一棵具有n个结点的二叉树，若一个结点的编号为i（1≤i≤n），则它的左孩子结点的编号为
A. 2i
B. 2i + 1
C. 2i - 1
D. 不确定
9. 深度为5的满二叉树中，叶子结点的个数为
A. 15
B. 16
C. 31
D. 32
10. 已知二叉树的前序序列为ABDECF，中序序列为DBEAFC，则后序序列为
A. DEBFCA
B. DEFBCA
C. DBEACF
D. ABCDEF
11. 以下哪种排序算法的平均时间复杂度为O(n^2)
A. 快速排序
B. 冒泡排序
C. 归并排序
D. 堆排序
12. 对关键字集合K={60，40，49，23，25，13，95}进行排序，当一趟排序结束后，结果为23，40，49，25，13，60，95，则采用的排序方法是
A. 冒泡排序
B. 选择排序
C. 插入排序
D. 快速排序
13. 哈希表的平均查找长度主要取决于
A. 哈希表的大小
B. 数据元素的多少
C. 哈希函数和处理冲突的方法
D. 以上都不对
14. 顺序查找法适用于查找
A. 有序表
B. 无序表
C. 哈希表
D. 二叉排序树
15. 折半查找法适用于查找
A. 有序表
B. 无序表
C. 哈希表
D. 二叉排序树
16. 一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小为
A. n n
B. (n - 1) (n - 1)
C. n (n - 1)
D. (n - 1) n
17. 一个具有n个顶点的有向图，其边数最多为
A. n (n - 1)
B. n (n + 1)
C. n n
D. (n +
18. 图的深度优先搜索类似于树的
A. 前序遍历
B. 中序遍历
C. 后序遍历
D. 层次遍历
19. 图的广度优先搜索类似于树的
A. 前序遍历
B.中序遍历
C. 后序遍历
D. 层次遍历
20. 以下关于数据结构应用的说法，错误的是
A. 栈可用于实现表达式求值
B. 队列可用于实现广度优先搜索
C. 二叉排序树可用于实现快速排序
D. 哈希表可用于实现查找功能

第II卷（非选择题，共60分）
21. （10分）简述线性表的两种存储结构及其优缺点。
22. （10分）已知一个栈的进栈序列为1，2，3，4，5，写出所有可能的出栈序列。
23. （10分）画出一棵具有5个结点的二叉树，要求其前序序列为ABCDE，中序序列为CBAED。
24. （15分）阅读以下材料：
给定关键字集合K={30，10，40，20，50}，采用快速排序算法进行排序。
快速排序的基本思想是选择一个基准元素，将数组分为两部分，使得左边部分的元素都小于等于基准元素，右边部分的元素都大于等于基准元素，然后对左右两部分分别进行排序。
请回答以下问题：
（1）第一次划分后，数组的状态是怎样的？
（2）简述快速排序的递归过程。
25. （15分）阅读以下材料：
有一个无向图G，其顶点集合V={v1，v2，v3，v4，v5}，边集合E={(v1,v2),(v1,v3),(v2,v3),(v2,v4),(v3,v4),(v3,v5),(v4,v5)}。
请回答以下问题：
（1）画出该无向图。
（2）写出该图的邻接矩阵。
（3）从顶点v1出发，进行深度优先搜索和广度优先搜索，分别写出搜索序列。

答案：1.C 2.B 3.A 4.B 5.C 6.A 7.A 8.B 9.B 10.A 11.B 12.D 13.C 14.B 15.A 16.A 17.A 18.A 19.D 20.C