二、数据结构部分（40分）
第一章绪论
1.考核知识点
（1）数据、数据元素、数据项、数据对象、数据结构、逻辑结构、物理结构、元素、结点等基本概念，抽象数据类型的定义、表示和实现方法。
（2）算法设计的基本要求以及计算语句频度和估算算法时间复杂度的方法。
2.考核要求
（1）识记：有关数据结构的基本概念，四种基本数据结构的特点。
（2）理解：四种基本数据结构的基本运算，算法复杂度度量的基本概念。
第二章线性表
1.考核知识点
（1）线性表的定义和基本操作。
（2）线性表顺序存储结构的表示和基本运算。
（3）线性表链式存储，单链表的表示和查找、插入、删除等基本操作。
（4）线性表两种存储结构优缺点的比较。2.考核要求
（1）识记：线性表基本概念、基本运算，单链表的表示。
（2）理解：顺序存储和链式存储的比较，各种链表的基本操作算法。
第三章栈和队列
1.考核知识点
（1）栈和队列的定义及其存储结构、循环队列结构及其存储。
（2）栈和队列的主要操作。
（3）栈的应用举例，如：数制转换等。2.考核要求
（1）识记：栈和队列的概念、功能、操作特点、主要运算。
（2）理解：栈和队列与一般线性表对比的特殊性，栈和队列的顺序存储和链式存储。
（3）应用：栈和队列的常见的使用场合。
第四章串、数组
1.考核知识点
（1）数组（二维数组）基本概念与存储方式。
（2）串的基本概念和基本操作，串的存储方式和BF算法。2.考核要求
（1）识记：数组的顺序存储结构，串的有关概念。
（2）理解：二维数组的地址计算，串的基本操作，串的顺序存储结构及其基本操作。
第五章树和二叉树
1.考核知识点
（1）树的定义和术语。
（2）二叉树(完全二叉树、满二叉树)的定义和性质、二叉树的存储结构
（顺序表示法和二叉链表表示法）。
（3）二叉树遍历算法（先序、中序、后序、层次）。2.考核要求
（1）识记：树的基本概念。
（2）理解：二叉树的存储结构、遍历算法。
第六章图
1.考核知识点
（1）图的定义，基本术语。
（2）图的存储结构，图的遍历，图的连通性与生成树，有向无环图及应用。
2.考核要求
（1）识记：图的基本概念和术语，最小生成树的概念。
（2）理解：图的存储方式和基于该存储方式的基本操作（求入度、出度、下一条边等）。
第七章查找
1.考核知识点
（1）查找、关键字、平均查找长度等概念。
（2）静态查找表的查找算法(顺序查找、折半查找)。2.考核要求
（1）识记：有关查找的基本概念，静态查找表和动态查找表的概念。
（2）理解：各种静态查找算法的比较次数分析。
第八章排序
1.考核知识点
（1）排序的目的、分类和排序方法的稳定性的定义。
（2）插入排序的思想，直接插入排序的算法。
（3）交换排序（冒泡排序的算法，快速排序的思想）。
（4）简单的选择排序的算法。2.考核要求
（1）了解：直接插入排序、冒泡排序、简单选择排序算法的特点和适用范围。
（2）理解：直接插入排序、冒泡排序、简单选择排序的思想，上述排序方法的稳定性、平均比较次数、平均移动次数。
（3）应用：用类C或者C语言编写直接插入排序、冒泡排序、简单选择排序等排序算法。
Ⅳ.参考书目
《C语言程序设计(第4版）》，何钦铭、颜晖、张泳主编，高等教育出版社，2020年9月第4版。
《数据结构(C语言第2版)》（双色版），严蔚敏、李冬梅、吴伟民编著，人民邮电出版社，2022年1月。
Ⅴ.题型示例
一、单项选择题（每小题备选答案中，只有一个符合题意的正确答案。请将选定的答案，填入表格中，多选、错选、不选均不得分。）
1.C语言程序的3种基本结构是顺序结构、选择结构和结构。
A．循环B．递归C．转移D．嵌套
2.对于栈操作的原则是。
A.先进先出B.后进先出C.后进后出D.不分顺序
二、填空题
1.当a=0，b=2，c=3时，则表达式c+b>0&&b==a的值是。
2.一棵深度为3（根的层次号为1）的满二叉树有个叶子结点。
三、判断题
1.C语言中，表达式1/2与1.0/2的结果相同。（）
2.数据结构中队列是非线性结构。（）
四、程序分析题
1.下列程序的运行结果是。#include<stdio.h>
int main(void){
int x=8;
do{
printf("%d",x);
}while(!x);return 0;
}
五、算法设计题
1.求整数的位数及各位数字之和，对于给定的正整数N，求它的位数及其各位数字之和。
输入示例：
9875
输出示例：
4 29
2.简单选择排序也称作直接选择排序，请简述选择排序算法的基本思想并编写相应程序：输入一个正整数n(1<n≤10)，再输入n个整数，将它们从小到大排序后输出。
输入示例：
Please input n:5
Please input 5 number:12 7 5 8 10
输出示例：
Select Sort：5 7 8 10 12
六、应用题
1.设一棵二叉树的先序序列：ABDFCEGH，中序序列BFDAGEHC。请画出这棵二叉树。
2.设待排序的关键字序列为{3，7，5，12，9，2}，试分别写出使用以下排序方法，每趟排序结束后关键字序列的状态。
直接插入排序
冒泡排序
简单选择排序

展开全文