数据结构期终考试复习.ppt

1011年度第一学期,数据结构 总复习,复习资料：,数据结构（面向对象方法与c+语言描述）（第2版） 殷人昆编著，清华大学出版社， 2007年6月 第2版 授课讲义（ PPT 电子讲稿） 课程指定参考书和有关参考书 网上有关资料,数据结构的考察内容,分析、思考,模 拟,ADT（抽象）,存储,处理（算法）,数据结构,概述 （典型结构的相关概念及算法） 典型线（非）性结构的表示（ADT） 上结构的存储（重点顺序和链式） 应用（栈、队列、树、图等） 简单的算法设计,本次考察范围,数据结构期终考试复习讲解,期终考试题型说明,数据结构期终考试复习讲解,一、填空题（20分） 二、单项选择题（20分） 三、简答题（20分） 四、应用题（20分） 五、算法设计题（20分）,期终考试题型说明,本部分将以最基本概念为主，测试范围：第1、2、3、4、5、8章 的最基本内容： 数据结构概论； 线性表 栈和队列 数组、串和广义表的概念 树的基本概念 图的基本概念,1、在线性结构、树形结构和图形结构中，直接前驱和直接后继结点之间分别存在着 _、_和_ 的 关系。 2、如果加尾指针rear，给出带头结点的非空循环单链表的循环判别条件是_（头结点指针为first）。 3、为了保证递归过程的正确执行，必须通过系统工作栈来保存相应的重要参数如：局部变量、参数和返回地址，它们构成一个_记录。 4、如果结点A共 3个兄弟，而且B是A的双亲，则B的度是_。 5、有向图的邻接矩阵第i行的元素之和为顶点vi的_，第j列的元素之和为顶点vj的_。,一、填空题：（每题1分，共20分）在以下各小题中画有_处填上答案。,数据结构期终考试复习,1；n,m：n,1：1,递归工作,3,期终考试题型说明_一、填空题示例：,rear link = first,出度,入度,数据结构期终考试复习,一、填空题（20分） 二、单项选择题（20分） 三、简答题（20分） 四、简单应用题（20分） 五、算法设计题（20分）,期终考试题型说明,本部分将以最基本概念为主，测试范围：第1、2、3、4、5、8章 的最基本内容： 数据结构概论； 线性表 栈和队列 数组、串和广义表的概念 树的基本概念 图的基本概念,数据结构期终考试复习,期终考试题型说明_二、选择题示例：,二、选择题（每题2分，共20分 选择正确答案的编号，填在各题前的括号内）,（ ）1、对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是： A、head=NULL； B、headnext=NULL； C、headnext=head； D、head!=NULL； （ ）2、在一个单链表中，若要在指针q所指结点的后面插入一个由指针P所指向的结点，则下列语句哪个正确。 A、qnextpnext；pnextq； B、pnextqnext；qp； C、qnextpnext；pnextq； D、pnextqnext；qnextp； （ ）3、在顺序表类中的插入成员函数int Insert ( Type （ ）5、有关二叉树下列说法正确的是： A、二叉树的度为2； B、一棵二叉树的度可以小于2； C、二叉树中至少有一个结点的度为2； D、二叉树中任何一个结点的度都为2；,数据结构期终考试复习讲解,期终考试题型说明,本部分将以最基本概念为主，测试范围：第2、3、5章 的最基本内容： 线性表； 栈与队列； 树；,一、填空题（20分） 二、单项选择题（20分） 三、简答题（20分） 四、简单应用题（20分） 五、算法设计题（20分）,数据结构期终考试复习讲解,期终考试题型说明_三、简答题示例：,三 、简单回答下列问题（每题5分，共20分） 1、给出二叉树的带权路径长度的定 义，给出其公式；简述哈夫曼树 （最优二叉树）的定义。 。 2、简要说明队列的顺序存储结构产 生的“假溢出”及解决方案？简述如 何判断循环队列的空和满？ 3、 4、,答（参考答案）： 设二叉树有n个带权值得叶结点，定义从二叉树的根结点到二叉树中所有叶结点的路径长度与相应叶结点权值的乘积之和为二叉树的带权路径长度。 WPL(T) = wklk (对所有叶子结点) 对于一组具有权值确定权值的叶结点可以构造出多个具有不同带权路径长度的二叉树，把其中最小带权值路径长度的二叉树称作哈夫曼树（或最优二叉树）。,数据结构期终考试复习讲解,期终考试题型说明_三、简答题示例：,三 、简单回答下列问题（每题5分，共20分） 1、给出二叉树的带权路径长度的定 义，给出其公式；简述哈夫曼树 （最优二叉树）的定义。 。 2、简要说明队列的顺序存储结构产 生的“假溢出”及解决方案？简述如 何判断循环队列的空和满？ 3、 4、,答（参考答案）： 随着元素不断入队列、出队列，rear和front指针会不断向后移动，最终会指向数组的最大下标位置。由于rear和front指针只能单方向移动，这时元素无法入队列，但是队列中仍有大量空闲位置。这种情况称为假溢出。 而在命题逻辑中的归结则不需要 。 解决的方法：1）采用平移元素法，效率低。2）循环队列方法。（2分） 采用如下方法判断循环队列的空或满： 1）计数器； 2）设标志； 3）人为浪费一个存储单元 ）,数据结构期终考试复习讲解,期终考试题型说明,一、填空题（20分） 二、单项选择题（20分） 三、简答题（20分） 四、应用题（20分） 五、算法设计题（20分）,本部分将以最基本概念为主，测试范围：第5、8章 的最基本内容： 树的基本概念及应用； 图基本概念与简单应用；,期终考试题型说明_四、应用题示例：,略,数据结构期终考试复习讲解,期终考试题型说明,本部分将以最基本概念为主，测试范围：第2、3及5章的最基本内容： 第二章涉及的有关基本编程 第三章涉及的有关基本编程 第五章涉及的有关基本编程,一、填空题（20分） 二、单项选择题（20分） 三、简答题（20分） 四、简单应用题（20分） 五、算法设计题（20分）,五、算法设计题（共20分） 1、试编写一个函数，在一个顺序表A中查找出具有最大值和最小值的整数。 #include“SeqListh” template void FindMaxMin(SeqList&A，int&Max，int&Min)； 说明：原型的参数表中给出顺序表对象为A，通过算法执行，从参数表中的 引用参数Max中得到表中的最大整数，Min中得到表中的最小整数。 注意，函数中可使用顺序表的如下两个公有函数：int Length()；求表的长度； int getData(int k)；提取第k个元素的值。,数据结构期终考试复习,解答（参考）,期终考试题型说明,Void FindMaxMin(SeqList&A，int&Max，inl&Min) Max=Min=AgetData(0)； for(int i=l；iMax)Max=AgetData(i)； else if(A.getData(i)Min)Min=A.geyData(i)； ,五、算法设计题（共20分） 2、数据结构是数据之间的关系，简单说明单链表这种形式的数据结构是递归的。 采用递归算法编写搜索单链表最后一个结点的算法： LinkNode* FindRear(LinkNode* f),数据结构期终考试复习,期终考试题型说明,先讨论单链表的结构是递归的，说明如下： first为NULL，是一个单链表（空表）； firstNULL，一个结点，它的指针域为NULL，是一个单链表; firstNULL，一个结点，它的指针域指向单链表，仍是一个单链表;,五、算法设计题（共20分） 2、数据结构是数据之间的关系，简单说明单链表这种形式的数据结构是递归的。 采用递归算法编写搜索单链表最后一个结点的算法： LinkNode* FindRear(LinkNode