一、选择题（每题2分，共20分）
1. 在数据结构中，线性表的逻辑结构是（ ）
A. 非线性结构
B. 线性结构
C. 树形结构
D. 图状结构
2. 下列哪一种数据结构具有“先进先出”的特性？
A. 栈
B. 队列
C. 二叉树
D. 堆
3. 一个完全二叉树共有100个节点，则它的深度为（ ）
A. 6
B. 7
C. 8
D. 9
4. 在图的存储结构中，邻接矩阵适合表示（ ）
A. 无向图
B. 有向图
C. 稀疏图
D. 稠密图
5. 对于一个含有n个元素的数组，使用快速排序算法在最坏情况下的时间复杂度是（ ）
A. O(n)
B. O(n log n)
C. O(n²)
D. O(log n)
6. 下列哪种排序方法在平均情况下效率最高？
A. 冒泡排序
B. 快速排序
C. 插入排序
D. 选择排序
7. 在哈希表中，冲突指的是（ ）
A. 两个不同的键值被映射到同一个地址
B. 两个相同的键值被映射到不同的地址
C. 一个键值没有被正确插入
D. 表中没有足够的空间
8. 以下关于链表的说法中，错误的是（ ）
A. 链表的插入和删除操作比较高效
B. 链表的访问速度比数组快
C. 链表需要额外的空间来保存指针
D. 链表可以动态分配内存
9. 一棵二叉树的前序遍历序列为ABDECF，中序遍历序列为DBEACF，则该二叉树的后序遍历序列为（ ）
A. DEBFCA
B. DEBCFA
C. DBECFA
D. BDECFA
10. 下列哪一个不是图的遍历方式？
A. 深度优先搜索
B. 广度优先搜索
C. 前序遍历
D. 层次遍历
二、填空题（每空2分，共20分）
1. 数据结构包括_________、_________和_________三个方面的内容。
2. 在顺序表中，插入和删除操作的时间复杂度为_________。
3. 二叉树的第k层最多有_________个结点。
4. 在最小生成树算法中，Prim算法适用于_________图。
5. 排序方法中，稳定排序有_________、_________。
6. 哈希函数的设计应满足_________和_________。
7. 二叉排序树中，查找的时间复杂度在平均情况下为_________。
三、简答题（每题10分，共30分）
1. 请简述什么是栈，并说明其基本操作有哪些。
2. 什么是哈希冲突？常用的解决方法有哪些？
3. 请写出二叉树的三种遍历方式，并说明它们的适用场景。
四、应用题（每题10分，共30分）
1. 已知一个图的邻接矩阵如下，请画出该图的结构图，并写出其邻接表形式。
```
0 1 0 1
1 0 1 0
0 1 0 1
1 0 1 0
```
2. 假设有一个字符串“DATASTRUCTURE”，请使用KMP算法查找子串“TURE”是否存在于其中，并写出匹配过程。
3. 设有一组记录的关键字为{50, 30, 80, 20, 90, 40}，请用堆排序的方法对其进行排序，并写出每一趟排序后的结果。
参考答案与解析请自行查阅相关教材或资料。
