数据结构实践考试大纲 | AI生成和翻译
广东省高等教育自学考试
《数据结构（实践）》课程考试大纲
（课程代码：13182）
一、考核目标
《数据结构》是高等教育自学考试计算机应用（专科）专业的专业核心课程。“数据结构实践”课程旨在通过理论学习和上机实验，培养考生对实际问题进行数据结构应用的能力。
要求考生具备以下能力：
- 从实际问题和需求出发
- 选用合适的存储结构
- 设计相应的算法
- 使用C语言实现并验证算法
- 解决一般和中等复杂程度的应用问题
- 加深对数据结构理论的理解
- 掌握基本算法的实现技术，提高综合应用能力
二、使用教材
《数据结构》
全国高等教育自学考试指导委员会编
辛运帏 陈淑瑛主编
机械工业出版社，2023年版
三、考核内容
考生须掌握以下内容：
- 链表的结构与操作，并能运用链表操作来解决应用问题
- 顺序栈和循环队列的存储特点及基本操作
- 二维数组的存储及其下标随机访问特性，并能运用二维数组解决问题
- 二叉树的二叉链表存储，并能实现树的建立、遍历和哈夫曼算法
- 图的邻接矩阵和邻接表存储，并能实现图的建立、遍历及应用
- 实现基本的排序算法，并比较关键码的比较次数和移动次数
- 了解顺序查找和二分查找的原理，并实现查找过程
四、考试形式
闭卷笔试，考试时间120分钟，卷面总分100分
| 题型 | 说明 | 题量 | 分值 |
|---|---|---|---|
| 选择题 | 从4个选项中选择最佳答案 | 10题 | 20 |
| 代码填空题 | 补全给定程序中缺失的部分 | 2题（共10空） | 20 |
| 函数题 | 根据提供的接口和主函数编写所需函数 | 2题 | 20 |
| 编程题 | 根据要求编写完整的程序 | 3题 | 40 |
| 总计 | 100 |
五、考试要求
- 仅限闭卷纸质考试
- 考试时长：120分钟
- 必须覆盖第三部分的所有知识点
- 难度分布：容易20%，中等偏易35%，中等偏难35%，困难10%
六、网络环境
无需（线下纸质考试）
七、重要须知
- 答题必须使用黑色或蓝色钢笔（不允许使用铅笔）
- 所有代码（填空、函数和编程题）均须用C语言编写
八、参考题型
1. 选择题（10题，共20分）
Q1. 对表达式中括号是否配对进行检查，最适合采用的数据结构是：
A. 线性表 B. 队列 C. 树 D. 栈
答案： D
2. 代码填空题（2题，共20分）
Q1. 补全循环队列的实现（10分）
// 关键空及答案：
(1) (q->rear + 1) % MAX_SIZE == q->front
(2) isFull(q)
(3) (q->rear + 1) % MAX_SIZE
(4) q->data[i]
(5) initQueue(&q)
3. 函数题（2题，共20分）
Q1. 删除带头结点的单链表中第 i 个结点（10分）
int deli(Node* head, int i) {
if (head == NULL || i < 1) return 0;
Node* p = head->next;
Node* q = head;
int j = 1;
while (p != NULL && j < i) {
q = p;
p = p->next;
j++;
}
if (p != NULL && j == i) {
q->next = p->next;
free(p);
return 1;
}
return 0;
}
4. 编程题（3题，共40分）
Q1. 直接插入排序——每趟排序后输出数组（15分）
#include <stdio.h>
#define MAX_SIZE 100
void printArray(int arr[], int n) {
for (int i = 0; i < n - 1; i++) printf("%d ", arr[i]);
printf("%d\n", arr[n-1]);
}
void insertionSort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int temp = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > temp) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = temp;
printArray(arr, n);
}
}
int main() {
int arr[MAX_SIZE], n;
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d", &arr[i]);
insertionSort(arr, n);
return 0;
}