《数据结构及应用》考核大纲

数据结构及应用课程考核大纲

一'适应对象2.1掌握应用顺序表的建立、插

修读完本课程规定内容的电子信息工程专入、删除操作

业学生；2.2掌握应用单链表的建立、插

提出并获准免修本课程、申请进行课程水入、删除操作

平考核的通信工程专业学生；2.3掌握应用线性表完成一元多

提出并获准副修第二专业、申请进行课程项式的相加运算

水平考核的非电子信息工程专业学生。

第三章栈和队列

二、考核目的1.考核知识点：

检查学生是否掌握数据结构的四种基1.1栈的表示和实现

本数据关系以及算法的思想和抽象描述和1.2队列的表示和实现

基本应用；用高级语言对数据结构的操作1.3栈的应用

能做算法设计并实现。2.考核要求：

2.1理解栈和队列的特点

三'考核形式与方法2.2掌握栈、队列在完成插入、

笔试删除元素时指针的变化

2.3掌握栈进行数制转换和表达

四、课程考核成绩构成式求值的算法

期评成绩=考试成绩(70%)+平时成绩2.4理解顺序队列和循环队列在

(30%)队满时的区别

平时成绩：考勤10%+作业20%

第四章串

五'考核内容与要求1.考核知识点：

1.1串的表示和实现

第一章绪论1.2模式匹配

1.考核知识点：2.考核要求：

1.1数据结构的定义，四种基本2.1理解串与线性表的区别

结构2.2掌握应用模式匹配算法

1.2基本概念和术语

2.考核要求：第五章数组和广义表

2.1掌握基本概念和计算时间复1.考核知识点：

杂度1.1数组的顺序存储

1.2广义表的定义和存储

第二章线性表2.考核要求：

1.考核知识点：2.1掌握数组的顺序存储

1.1顺序表的表示的实现2.2理解特殊矩阵、稀疏矩阵的

1.2链式表的表示和实现概念

2.考核要求：2.3掌握应用广义表的计算和存

储结构2.1理解图的基本术语：有向图

和无向图

第六章树和二叉树2.2掌握图的存储结构

1.考核知识点：2.3掌握应用邻接矩阵表示法和

1.1树的基本术语：孩子结点、邻接表的算法

双亲结点、结点的度、深度、连通分量2.4掌握应用图的遍历方式以及

1.2二叉树的性质算法实现

1.3二叉树的存储：二叉链表、2.5掌握应用最小生成树的算法

三叉链表2.6掌握应用最短路径的算法

1.4二叉树的遍历方式

1.5线索二叉树第八章查找

1.6树的存储结构1.考核知识点：

1.7树和森林的遍历1.1静态查找表

1.8哈夫曼树1.2动态查找表

2.考核要求：1.3二叉排序树

2.1理解树的基本术语，二叉树1.4哈希表

的性质2.考核要求：

2.2掌握遍历二叉树和线索二叉2.1理解静态查找表和动态查找

树，以及用算法实现遍历二叉树表的区别

2.3理解应用树、二叉树的存储2.2理解应用顺序查找和折半查

结构找的思想

2.4理解应用树、森林与二叉树2.3掌握应用二叉排序树的建立

的相互转换2.4掌握哈希表的构造和解决冲

2.5掌握哈夫曼树的构造以及算突的方法

法实现

第九章排序

第七章图1.考核知识点：

1.考核知识点：1.1插入排序、快速排序、选择

1.1图的基本术语排序、堆排序、归并排序和基数排序

1.2图的存储结构1.2几种排序方法的比较

1.3图的遍历2.考核要求：

1.4图的连通性问题2.1掌握应用排序方法

1.5最小生成树2.2理解排序方法的区别和各自

1.6拓扑结构的特点

1.7最短路径

2.考核要求：六、样卷

电子信息工程专业《数据结构及应用》课程考试试题

XXX年2学期XX-XX班级

时量：120分钟，总分100分

一、判断题（每小题1分，共10分对的9、采用顺序查找方法查找长度为n的线性表时,

打。，错的打X）每个元素的平均查找长度为—o（2分）

1、栈和队列逻辑上都是线形表。10、有一个有序表为｛2,5,10,20,38,40,

2、线性表中有且仅有一个结点没有前驱以及50,65,75,80,82,90,100）,当二分查找

有且仅有一个结点没有后继。值为82的元素时，次比较后查找成功。

3、完全二叉树一定是满二叉树。（3分）

4、网络的邻接矩阵不是唯一的，而邻接表是三、选择题（共20分，每小题2分）

唯一的。1、一个队列的入队列序列是1,2,3,4,则

5、线性表数据结构，物理上可以采用顺序存队列的输出序列是。

储结构，也可以采用链式存储结构。A、4,3,2,IB、I,2,3,4

6、在希尔排序、选择排序、快速排序、堆排C、1,4,3,2D、3,2,4,1

序和基数排序中，只有快速排序是不稳定2,已知二叉树的后序序列为dabec,它的中序

的。序列为debac,它的前序序列为。

7、包含两个结点的所有二叉树都是相同的。A、acbedB、decabC、deabcD、cedba

8、若有向图G中包含一个环，则G的结点间3、二维数组M的元素是4个字符组成的串，

不存在拓扑排序。行下标I的范围从0到4,列下标的范围从0

9、设串S的长度为n,则S的真子串个数n*到5,M按行存储时元素M[3][5]的起始地址与

（n+1）/2。M按列存储时元素的起始地址相同。

10、因为队列只允许在一端插入而在另一端删A、M[2][4]B、M[3][4]

除，所以一定是顺序表。C、M[3][5]D、M[4J[4]

二、填空题（每空1分，共20分）4、一组记录的关键码为（46,79,56,38,40,

1、数据结构课程主要是研究数据的结构,84）,则利用快速排序的方法，以第一记录为基

结构，并给出一组—及其相应算法，并用准得到的一次快排结果为1

和来衡量算法的效率。A、38,40,46,56,79,84

2、输入序列ABC,通过一个堆栈，可能得到B、40,38,46,79,56,84

的输出序列有种。C、40,38,46,56,79,84

3、已知二叉树的高度为h,该树的第k层最多有D、40,38,46,84,56,79

个结点，该树最多结点个数为。5、设有两个串p和q,求q在p中首次出现的

4、按照二叉树的定义，具有3个结点的二叉树位置的运算称作为。

有种。A、连接B、模式匹配

5、在图中，常用的遍历方法为—和—两C、求子串D、求串长

种形式。6、在线索化二叉树中，p所指结点没有右子树

6、栈是一种的线性表，而队列是一种的充要条件是o

的线性表。A、p->Rchild=null

7、已知一个图用邻接矩阵表示，计算第i个结B、p->Rtag=1

点的入度的方法是oC、p->Rtag=l&&p->Rchild=null

8、在二叉树中，度为零的结点个数为no,度为D^p->Rtag=O

2的结点个数为血,则有no和血的关系为。7、设高度为h的二叉树上只有度为0和度为2

的结点，则此类二叉树中所包含的结点至01,68,20,84,27,55,11,10,79},共有

少个数为o12个元素，已知散列函数为h（key）=key%7

A、2h-lB、2h+lC、2hD、h+1采用链地址法处理冲突。设计这种链表结构，

8,在一个具有n个顶点的无向图中，要连通全并求对该表成功查找的平均查找长度。（8分）

部顶点至少需要条边。4、给出下列二叉树的中序序列和中序线索二叉

A^nB、n+1C>n-1D、n/2树（6分）

9、下述几种排序方法中，平均查找长度最小的

是O

A、插入排序B、选择排序

C、快速排序D、归并排序

10、对于一个具有n个顶点和e条边的无向图，

若采用邻接表表示，则表头向量的大小和所有

邻接表的中结点总数分别是o

A、n,2eB、n+1,e/25、给定一组实数集{8,5,12,4,3}。试构造

C、n-1，eD、n+e,n+e哈夫曼树，并求出该树的带权路径长度。（4分）

四、简单应用题（共29分）

五、算法设计（共21分）

1、下图

①用邻接表表示1、有一个有序单链表（从小到大排列），表头

②写出图的邻接矩阵指针为head,编写一个函数向该单链表中插

③写出从结点vl开始，