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

《《数据结构及应用》考核大纲.docx》由会员分享，可在线阅读，更多相关《《数据结构及应用》考核大纲.docx（4页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

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

2、 掌握基本概念和计算时间复 杂度第二章线性表.考核知识点：1.1 顺序表的表示的实现链式表的表示和实现2 .考核要求：2.1 掌握应用顺序表的建立、插 入、删除操作2.2 掌握应用单链表的建立、插 入、删除操作2.3 掌握应用线性表完成一元多 项式的相加运算第三章栈和队列1 .考核知识点：1.1 栈的表示和实现队列的表示和实现1.2 栈的应用.考核要求：1.3 理解栈和队列的特点1.4 掌握栈、队列在完成插入、 删除元素时指针的变化1.5 掌握栈进行数制转换和表达 式求值的算法1.6 理解顺序队列和循环队列在 队满时的区别U!L考核知识点：1.1 串的表示和实现模式匹配2 .考核要求：2.1

3、理解串与线性表的区别掌握应用模式匹配算法第五章数组和广义表.考核知识点：1.1 数组的顺序存储广义表的定义和存储2 .考核要求：2.1 掌握数组的顺序存储2.2 理解特殊矩阵、稀疏矩阵的 概念2.3 掌握应用广义表的计算和存储结构第六章树和二叉树1 .考核知识点：1.1 树的基本术语：孩子结点、 双亲结点、结点的度、深度、连通分量1.2 二叉树的性质1.3 二叉树的存储：二叉链表、 三叉链表二叉树的遍历方式1.4 线索二叉树树的存储结构1.5 树和森林的遍历L8哈夫曼树2 .考核要求：2.1 理解树的基本术语，二叉树 的性质2.2 掌握遍历二叉树和线索二叉 树，以及用算法实现遍历二叉树2.3

4、理解应用树、二叉树的存储 结构2.4 理解应用树、森林与二叉树 的相互转换2.5 掌握哈夫曼树的构造以及算 法实现第七章图L考核知识点：1.1 图的基本术语图的存储结构1.2 图的遍历图的连通性问题1.3 最小生成树拓扑结构1.4 最短路径2.考核要求：2.1 理解图的基本术语：有向图 和无向图掌握图的存储结构2.2 掌握应用邻接矩阵表示法和 邻接表的算法2.3 掌握应用图的遍历方式以及 算法实现掌握应用最小生成树的算法2.4 掌握应用最短路径的算法第八章查找1 .考核知识点：1.1 静态查找表动态查找表1.2 二叉排序树哈希表2 .考核要求：2.1 理解静态查找表和动态查找 表的区别2.2

5、理解应用顺序查找和折半查 找的思想掌握应用二叉排序树的建立2.3 掌握哈希表的构造和解决冲 突的方法第九章排序L考核知识点：1.1 插入排序、快速排序、选择 排序、堆排序、归并排序和基数排序几种排序方法的比拟2.考核要求：2.1 掌握应用排序方法2.2 理解排序方法的区别和各自 的特点六、样卷电子信息工程专业数据结构及应用课程考试试题xxx年21学期xx-xx班级时量：120分钟，总分100分D、40,38, 46,84, 56, 79一、判断题（每题I分，共10分对的 打错的打义）1、栈和队列逻辑上都是线形表。2、线性表中有且仅有一个结点没有前驱以及 有且仅有一个结点没有后继。3、完全二叉树

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

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

8、）,当二分查找 值为82的元素时，次比拟后查找成功。（3分）三、选择题（共20分，每题2分）1、一个队列的入队列序列是1, 2, 3, 4,那么 队列的输出序列是 oA、4, 3, 2, 1 B、1, 2, 3, 4C、1, 4, 3, 2 D、3, 2, 4, 1 2、二叉树的后序序列为dabec,它的中序 序列为debac,它的前序序列为 oA、acbedB、decab C、deabc D、cedba3、二维数组M的元素是4个字符组成的串， 行下标I的范围从。到4,列下标的范围从。 至M按行存储时元素M的起始地址与 M按列存储时元素 的起始地址相同。A、M24B、M34C、M35D、M44

9、4、一组记录的关键码为（46, 79, 56, 38, 40,84）,那么利用快速排序的方法，以第一记录为基准得到的一次快排结果为 oA、38, 40, 46, 56, 79, 84B、40, 38, 46, 79, 56, 84C、 40, 38, 46, 56, 79, 84 5、设有两个串p和q,求q在p中首次出现的位置的运算称作为 oA、连接 B、模式匹配C、求子串 D、求串长 6、在线索化二叉树中，p所指结点没有右子树 的充要条件是 oA、p-Rchild=nullB、p-Rtag= 1C、p-Rtag=l & p-Rchild=nullD、p-Rtag=O7、设高度为h的二叉树上只

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

11、始，按广度优先遍历次 序得到的结点序列。（6分）2、给出一组记录关键字：（5分）1 2, 3, 4, 5, 6, 7, 8, 9, 10。欲用堆排序算法将其按关键码从大到小排序，请 画出用筛选法建立的第一个堆的完全二叉树。3、设线性表的关键字集合key=19, 14, 23,0b 68, 20, 84, 27, 55, 11, 10, 79,共有 12个元素，散列函数为h （key）二key % 7 采用链地址法处理冲突。设计这种链表结构， 并求对该表成功查找的平均查找长度。（8分） 4、给出以下二叉树的中序序列和中序线索二叉 树（6分）5、给定一组实数集8, 5, 12, 4, 3o试构造哈夫曼树，并求出该树的带权路径长度。（4分）五、算法设计（共21分）1、有一个有序单链表（从小到大排列），表头 指针为head,编写一个函数向该单链表中插 入一个元素为x的结点，使该单链表依然 有序。（11分） 定义如下：typedef struct nodeint data;struct node *next; node;2、二叉树采用链式存储结构，编写对二叉树 中根遍历的非递归算法。（10分） 定义如下：typedef struct node char data;struct node * Ich,* rchjnode;大纲制定人：李文彬大纲审定人：潘理