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

1、数据结构及应用 课程考核大纲一、适应对象修读完本课程规定内容的电子信息工程专业学生；提出并获准免修本课程、申请进行课程水平考核的通信工程专业学生；提出并获准副修第二专业、申请进行课程水平考核的非电子信息工程专业学生。二、考核目的检查学生是否掌握数据结构的四种基本数据关系以及算法的思想和抽象描述和基本应用；用高级语言对数据结构的操作能做算法设计并实现。三、考核形式与方法笔试四、课程考核成绩构成期评成绩考试成绩（70%）平时成绩（30%）平时成绩：考勤10% + 作业20%五、考核内容与要求 绪论 考核知识点：数据结构的定义，四种基本结构基本概念和术语考核要求：掌握基本概念和计算时间复杂度 线性表

2、考核知识点：顺序表的表示的实现链式表的表示和实现考核要求：掌握应用顺序表的建立、插入、删除操作掌握应用单链表的建立、插入、删除操作掌握应用线性表完成一元多项式的相加运算 栈和队列考核知识点：栈的表示和实现队列的表示和实现栈的应用考核要求：理解栈和队列的特点掌握栈、队列在完成插入、删除元素时指针的变化掌握栈进行数制转换和表达式求值的算法理解顺序队列和循环队列在队满时的区别 串 考核知识点：串的表示和实现模式匹配考核要求：理解串与线性表的区别掌握应用模式匹配算法 数组和广义表考核知识点：数组的顺序存储广义表的定义和存储考核要求：掌握数组的顺序存储理解特殊矩阵、稀疏矩阵的概念掌握应用广义表的计算和存

3、储结构 树和二叉树考核知识点：树的基本术语：孩子结点、双亲结点、结点的度、深度、连通分量二叉树的性质二叉树的存储：二叉链表、三叉链表二叉树的遍历方式线索二叉树树的存储结构树和森林的遍历哈夫曼树考核要求：理解树的基本术语，二叉树的性质掌握遍历二叉树和线索二叉树，以及用算法实现遍历二叉树理解应用树、二叉树的存储结构理解应用树、森林与二叉树的相互转换掌握哈夫曼树的构造以及算法实现 图 考核知识点：图的基本术语图的存储结构图的遍历图的连通性问题最小生成树拓扑结构最短路径考核要求：理解图的基本术语：有向图和无向图掌握图的存储结构掌握应用邻接矩阵表示法和邻接表的算法掌握应用图的遍历方式以及算法实现掌握应用

4、最小生成树的算法掌握应用最短路径的算法 查找考核知识点：静态查找表动态查找表二叉排序树哈希表考核要求：理解静态查找表和动态查找表的区别理解应用顺序查找和折半查找的思想掌握应用二叉排序树的建立掌握哈希表的构造和解决冲突的方法排序考核知识点：插入排序、快速排序、选择排序、堆排序、归并排序和基数排序几种排序方法的比较考核要求：掌握应用排序方法理解排序方法的区别和各自的特点 六、样卷电子信息工程专业数据结构及应用课程考试试题 XXX年 X学期XX-XX班级 时量：120 分钟，总分100 分一、判断题（每小题1分，共10分对的打，错的打）栈和队列逻辑上都是线形表。线性表中有且仅有一个结点没有前驱以及有

5、且仅有一个结点没有后继。完全二叉树一定是满二叉树。网络的邻接矩阵不是唯一的，而邻接表是唯一的。线性表数据结构，物理上可以采用顺序存储结构，也可以采用链式存储结构。在希尔排序、选择排序、快速排序、堆排序和基数排序中，只有快速排序是不稳定的。包含两个结点的所有二叉树都是相同的。若有向图G中包含一个环，则G的结点间不存在拓扑排序。设串S的长度为n，则S的真子串个数n*（n+1）/2。10、因为队列只允许在一端插入而在另一端删除，所以一定是顺序表。二、填空题（每空1分，共20分）1、数据结构课程主要是研究数据的 结构， 结构，并给出一组 及其相应算法，并用 和 来衡量算法的效率。2、输入序列ABC，通

6、过一个堆栈，可能得到的输出序列有 种 。3、已知二叉树的高度为h,该树的第k层最多有 个结点，该树最多结点个数为 。4、按照二叉树的定义，具有3个结点的二叉树有 种。5、在图中，常用的遍历方法为 和 两种形式。6、栈是一种 的线性表，而队列是一种 的线性表。7、已知一个图用邻接矩阵表示，计算第i个结点的入度的方法是 。8、在二叉树中，度为零的结点个数为n0，度为2的结点个数为n2，则有n0和n2的关系为 。 9、采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为 。（2分）10、有一个有序表为2，5，10，20，38，40，50，65，75，80，82，90，100，当二分查找值

7、为82的元素时， 次比较后查找成功。 （3分） 三、选择题（共20分，每小题2分）1、一个队列的入队列序列是1，2，3，4，则队列的输出序列是 。A、4，3，2，1 B、1，2，3，4 C、1，4，3，2 D、3，2，4，12、已知二叉树的后序序列为dabec，它的中序序列为debac,它的前序序列为 。A、acbed B、decab C、deabc D、cedba3、二维数组M的元素是4个字符组成的串，行下标I 的范围从0到4，列下标的范围从0到5，M按行存储时元素M35的起始地址与M按列存储时元素 的起始地址相同。A、M24 B、M34 C、M35 D、M44 4、一组记录的关键码为（46

8、，79，56，38，40，84），则利用快速排序的方法，以第一记录为基准得到的一次快排结果为 。A、38，40，46，56，79，84 B、40，38，46，79，56，84 C、40，38，46，56，79，84 D、40，38，46，84，56，795、设有两个串p和q，求q在p中首次出现的位置的运算称作为 。A、连接 B、模式匹配 C、求子串 D、求串长6、在线索化二叉树中，p所指结点没有右子树的充要条件是 。A、p-Rchild=null B、p-Rtag=1 C、p-Rtag=1 & p-Rchild=null D、p-Rtag=07、设高度为h的二叉树上只有度为0和度为2的结点，则

9、此类二叉树中所包含的结点至少个数为 。 A、2h-1 B、2h+1 C、2h D、h+18、在一个具有n个顶点的无向图中，要连通全部顶点至少需要 条边。 A、n B、n+1 C、n-1 D、n/29、下述几种排序方法中，平均查找长度最小的是 。A、插入排序 B、选择排序 C、快速排序 D、归并排序10、对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小和所有邻接表的中结点总数分别是 。A、n，2e B、n+1，e/2 C、n-1 ，e D、n+e，n+e四、简单应用题（共29分）1、下图 = 1 * GB3 用邻接表表示 = 2 * GB3 写出图的邻接矩阵 写出从结点v

10、1开始，按广度优先遍历次序得到的结点序列。 (6 分) v1 v2 v3 v4 v52、给出一组记录关键字：（5分）1，2，3，4，5，6，7，8，9，10。欲用堆排序算法将其按关键码从大到小排序，请画出用筛选法建立的第一个堆的完全二叉树。3、设线性表的关键字集合key=19，14，23，01，68，20，84，27，55，11，10，79，共有12个元素，已知散列函数为h（key）= key % 7采用链地址法处理冲突。设计这种链表结构，并求对该表成功查找的平均查找长度。（8分）4、给出下列二叉树的中序序列和中序线索二叉树（6分） - + / a - c d b 5、给定一组实数集8，5，12，4，3。试构造哈夫曼树，并求出该树的带权路径长度。（4分）五、算法设计（共21分）有一个有序单链表（从小到大排列），表头指针为head,编写一个函数向该单链表中插入一个元素为x的结点，使该单链表依然有序。（11分）定义如下：typede