数据结构期终考试复习课件

1011年度第一学期数据结构总复习

1011年度第一学期数据结构1复习资料：

《数据结构》（面向对象方法与c++语言描述）（第2版）殷人昆编著，清华大学出版社，2007年6月第2版授课讲义（PPT电子讲稿）课程指定参考书和有关参考书网上有关资料

复习资料：2数据结构的考察内容自然界分析、思考模拟ADT（抽象）计算机CPUmemory存储处理（算法）数据结构概述（典型结构的相关概念及算法）典型线（非）性结构的表示（ADT）上结构的存储（重点顺序和链式）应用（栈、队列、树、图等）简单的算法设计本次考察范围数据结构的考察内容自然界分析、思考模拟ADT（抽3《数据结构》期终考试复习讲解期终考试题型说明一、填空题（20分）二、单项选择题（20分）三、简答题（20分）四、应用题（20分）五、算法设计题（20分）《数据结构》期终考试复习讲解期终考试题型说明一、填空题（204《数据结构》期终考试复习讲解一、填空题（20分）二、单项选择题（20分）三、简答题（20分）四、应用题（20分）五、算法设计题（20分）期终考试题型说明本部分将以最基本概念为主，测试范围：第1、2、3、4、5、8章的最基本内容：数据结构概论；线性表栈和队列数组、串和广义表的概念树的基本概念图的基本概念《数据结构》期终考试复习讲解一、填空题（20分）期终考试题型51、在线性结构、树形结构和图形结构中，直接前驱和直接后继结点之间分别存在着______________、______________和______________的关系。

2、如果加尾指针rear，给出带头结点的非空循环单链表的循环判别条件是______________________（头结点指针为first）。

3、为了保证递归过程的正确执行，必须通过系统工作栈来保存相应的重要参数如：局部变量、参数和返回地址，它们构成一个______________记录。4、如果结点A共3个兄弟，而且B是A的双亲，则B的度是______。5、有向图的邻接矩阵第i行的元素之和为顶点vi的________，第j列的元素之和为顶点vj的________。一、填空题：（每题1分，共20分）在以下各小题中画有_______处填上答案。《数据结构》期终考试复习1；nm：n1：1

递归工作

3

期终考试题型说明____一、填空题示例：rear—>link=first

出度

入度

1、在线性结构、树形结构和图形结构中，直接前驱和直接后继结点6《数据结构》期终考试复习一、填空题（20分）二、单项选择题（20分）三、简答题（20分）四、简单应用题（20分）五、算法设计题（20分）期终考试题型说明本部分将以最基本概念为主，测试范围：第1、2、3、4、5、8章的最基本内容：数据结构概论；线性表栈和队列数组、串和广义表的概念树的基本概念图的基本概念《数据结构》期终考试复习一、填空题（20分）期终考试题型说明7《数据结构》期终考试复习期终考试题型说明____二、选择题示例：二、选择题（每题2分，共20分

选择正确答案的编号，填在各题前的括号内）（）1、对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是：A、head==NULL；B、head→next==NULL；C、head→next==head；D、head!=NULL；（）2、在一个单链表中，若要在指针q所指结点的后面插入一个由指针P所指向的结点，则下列语句哪个正确。A、q—＞next＝p—＞next；p—＞next＝q；

B、p—＞next＝q—＞next；q＝p；

C、q—＞next＝p—＞next；p—＞next＝q；

D、p—＞next＝q—＞next；q—＞next＝p；（）3、在顺序表类中的插入成员函数intInsert(Type&x,inti)的算法效率是：A、O（n+n2）；B、O（n2）；C、O（C）；C是常数；D、O（n）；（）4、有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为：A、求子串；B、联接；C、匹配；D、求串长;（）5、有关二叉树下列说法正确的是：

A、二叉树的度为2；B、一棵二叉树的度可以小于2；

C、二叉树中至少有一个结点的度为2；D、二叉树中任何一个结点的度都为2；《数据结构》期终考试复习期终考试题型说明____二、选择题示8《数据结构》期终考试复习讲解期终考试题型说明本部分将以最基本概念为主，测试范围：第2、3、5章的最基本内容：线性表；栈与队列；

树；一、填空题（20分）二、单项选择题（20分）三、简答题（20分）四、简单应用题（20分）五、算法设计题（20分）《数据结构》期终考试复习讲解期终考试题型说明本部分将以最基本9《数据结构》期终考试复习讲解期终考试题型说明____三、简答题示例：三、简单回答下列问题（每题5分，共20分）1、给出二叉树的带权路径长度的定义，给出其公式；简述哈夫曼树（最优二叉树）的定义。。2、简要说明队列的顺序存储结构产生的“假溢出”及解决方案？简述如何判断循环队列的空和满？3、……4、……答（参考答案）：设二叉树有n个带权值得叶结点，定义从二叉树的根结点到二叉树中所有叶结点的路径长度与相应叶结点权值的乘积之和为二叉树的带权路径长度。WPL(T)=wklk(对所有叶子结点)对于一组具有权值确定权值的叶结点可以构造出多个具有不同带权路径长度的二叉树，把其中最小带权值路径长度的二叉树称作哈夫曼树（或最优二叉树）。《数据结构》期终考试复习讲解期终考试题型说明____三、简答10《数据结构》期终考试复习讲解期终考试题型说明____三、简答题示例：三、简单回答下列问题（每题5分，共20分）1、给出二叉树的带权路径长度的定义，给出其公式；简述哈夫曼树（最优二叉树）的定义。。2、简要说明队列的顺序存储结构产生的“假溢出”及解决方案？简述如何判断循环队列的空和满？3、……4、……答（参考答案）：随着元素不断入队列、出队列，rear和front指针会不断向后移动，最终会指向数组的最大下标位置。由于rear和front指针只能单方向移动，这时元素无法入队列，但是队列中仍有大量空闲位置。这种情况称为假溢出。而在命题逻辑中的归结则不需要。解决的方法：1）采用平移元素法，效率低。2）循环队列方法。（2分）采用如下方法判断循环队列的空或满：1）计数器；2）设标志；3）人为浪费一个存储单元）《数据结构》期终考试复习讲解期终考试题型说明____三、简答11《数据结构》期终考试复习讲解期终考试题型说明一、填空题（20分）二、单项选择题（20分）三、简答题（20分）四、应用题（20分）五、算法设计题（20分）本部分将以最基本概念为主，测试范围：第5、8章的最基本内容：树的基本概念及应用；图基本概念与简单应用；期终考试题型说明____四、应用题示例：略《数据结构》期终考试复习讲解期终考试题型说明一、填空题（2012《数据结构》期终考试复习讲解期终考试题型说明本部分将以最基本概念为主，测试范围：第2、3及5章的最基本内容：第二章涉及的有关基本编程第三章涉及的有关基本编程第五章涉及的有关基本编程一、填空题（20分）二、单项选择题（20分）三、简答题（20分）四、简单应用题（20分）五、算法设计题（20分）《数据结构》期终考试复习讲解期终考试题型说明本部分将以最基本13五、算法设计题（共20分）1、试编写一个函数，在一个顺序表A中查找出具有最大值和最小值的整数。#include“SeqList．h”template<classT>voidFindMaxMin(SeqList<int>&A，int&Max，int&Min)；说明：原型的参数表中给出顺序表对象为A，通过算法执行，从参数表中的引用参数Max中得到表中的最大整数，Min中得到表中的最小整数。注意，函数中可使用顺序表的如下两个公有函数：intLength()；求表的长度；

intgetData(intk)；提取第k个元素的值。《数据结构》期终考试复习解答（参考）期终考试题型说明VoidFindMaxMin(SeqList<int>&A，int&Max，inl&Min){Max=Min=A．getData(0)；

for(inti=l；i<A．Length()；i++){

if(A．getData(i)>Max)Max=A．getData(i)；

elseif(A.getData(i)<Min)Min=A.geyData(i)；}}五、算法设计题（共20分）《数据结构》期终考试复习解答（参考14五、算法设计题（共20分）2、数据结构是数据之间的关系，简单说明单链表这种形式的数据结构是递归的。采用递归算法编写搜索单链表最后一个结点的算法：LinkNode*FindRear(LinkNode*f)解答（参考）《数据结构》期终考试复习期终考试题型说明先讨论单链表的结构是递归的，说明如下：first为NULL，是一个单链表（空表）；first≠NULL，一个结点，它的指针域为NULL，是一个单链表;first≠NULL，一个结点，它的指针域指向单链表，仍是一个单链表;五、算法设计题（共20分）解答（参考）《数据结构》期终考试复15五、算法设计题（共20分）2、数据结构是数据之间的关系，简单说明单链表这种形式的数据结构是递归的。采用递归算法编写搜索单链表最后一个结点的算法：LinkNode*FindRear(LinkNode*f)解答（参考）《数据结构》期终考试复习期终考试题型说明参考程序如下：LinkNode*FindRear(LinkNode*f){if(f==NULL)returnNULL;elseif(f->link==NULL)returnf;elsereturnFindRear(f->link);};

五、算法设计题（共20分）解答（参考）《数据结构》期终考试复16祝同学们考试祝同学们考试171011年度第一学期数据结构总复习

1011年度第一学期数据结构18复习资料：

《数据结构》（面向对象方法与c++语言描述）（第2版）殷人昆编著，清华大学出版社，2007年6月第2版授课讲义（PPT电子讲稿）课程指定参考书和有关参考书网上有关资料

复习资料：19数据结构的考察内容自然界分析、思考模拟ADT（抽象）计算机CPUmemory存储处理（算法）数据结构概述（典型结构的相关概念及算法）典型线（非）性结构的表示（ADT）上结构的存储（重点顺序和链式）应用（栈、队列、树、图等）简单的算法设计本次考察范围数据结构的考察内容自然界分析、思考模拟ADT（抽20《数据结构》期终考试复习讲解期终考试题型说明一、填空题（20分）二、单项选择题（20分）三、简答题（20分）四、应用题（20分）五、算法设计题（20分）《数据结构》期终考试复习讲解期终考试题型说明一、填空题（2021《数据结构》期终考试复习讲解一、填空题（20分）二、单项选择题（20分）三、简答题（20分）四、应用题（20分）五、算法设计题（20分）期终考试题型说明本部分将以最基本概念为主，测试范围：第1、2、3、4、5、8章的最基本内容：数据结构概论；线性表栈和队列数组、串和广义表的概念树的基本概念图的基本概念《数据结构》期终考试复习讲解一、填空题（20分）期终考试题型221、在线性结构、树形结构和图形结构中，直接前驱和直接后继结点之间分别存在着______________、______________和______________的关系。

2、如果加尾指针rear，给出带头结点的非空循环单链表的循环判别条件是______________________（头结点指针为first）。

3、为了保证递归过程的正确执行，必须通过系统工作栈来保存相应的重要参数如：局部变量、参数和返回地址，它们构成一个______________记录。4、如果结点A共3个兄弟，而且B是A的双亲，则B的度是______。5、有向图的邻接矩阵第i行的元素之和为顶点vi的________，第j列的元素之和为顶点vj的________。一、填空题：（每题1分，共20分）在以下各小题中画有_______处填上答案。《数据结构》期终考试复习1；nm：n1：1

递归工作

3

期终考试题型说明____一、填空题示例：rear—>link=first

出度

入度

1、在线性结构、树形结构和图形结构中，直接前驱和直接后继结点23《数据结构》期终考试复习一、填空题（20分）二、单项选择题（20分）三、简答题（20分）四、简单应用题（20分）五、算法设计题（20分）期终考试题型说明本部分将以最基本概念为主，测试范围：第1、2、3、4、5、8章的最基本内容：数据结构概论；线性表栈和队列数组、串和广义表的概念树的基本概念图的基本概念《数据结构》期终考试复习一、填空题（20分）期终考试题型说明24《数据结构》期终考试复习期终考试题型说明____二、选择题示例：二、选择题（每题2分，共20分

选择正确答案的编号，填在各题前的括号内）（）1、对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是：A、head==NULL；B、head→next==NULL；C、head→next==head；D、head!=NULL；（）2、在一个单链表中，若要在指针q所指结点的后面插入一个由指针P所指向的结点，则下列语句哪个正确。A、q—＞next＝p—＞next；p—＞next＝q；

B、p—＞next＝q—＞next；q＝p；

C、q—＞next＝p—＞next；p—＞next＝q；

D、p—＞next＝q—＞next；q—＞next＝p；（）3、在顺序表类中的插入成员函数intInsert(Type&x,inti)的算法效率是：A、O（n+n2）；B、O（n2）；C、O（C）；C是常数；D、O（n）；（）4、有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为：A、求子串；B、联接；C、匹配；D、求串长;（）5、有关二叉树下列说法正确的是：

A、二叉树的度为2；B、一棵二叉树的度可以小于2；

C、二叉树中至少有一个结点的度为2；D、二叉树中任何一个结点的度都为2；《数据结构》期终考试复习期终考试题型说明____二、选择题示25《数据结构》期终考试复习讲解期终考试题型说明本部分将以最基本概念为主，测试范围：第2、3、5章的最基本内容：线性表；栈与队列；

树；一、填空题（20分）二、单项选择题（20分）三、简答题（20分）四、简单应用题（20分）五、算法设计题（20分）《数据结构》期终考试复习讲解期终考试题型说明本部分将以最基本26《数据结构》期终考试复习讲解期终考试题型说明____三、简答题示例：三、简单回答下列问题（每题5分，共20分）1、给出二叉树的带权路径长度的定义，给出其公式；简述哈夫曼树（最优二叉树）的定义。。2、简要说明队列的顺序存储结构产生的“假溢出”及解决方案？简述如何判断循环队列的空和满？3、……4、……答（参考答案）：设二叉树有n个带权值得叶结点，定义从二叉树的根结点到二叉树中所有叶结点的路径长度与相应叶结点权值的乘积之和为二叉树的带权路径长度。WPL(T)=wklk(对所有叶子结点)对于一组具有权值确定权值的叶结点可以构造出多个具有不同带权路径长度的二叉树，把其中最小带权值路径长度的二叉树称作哈夫曼树（或最优二叉树）。《数据结构》期终考试复习讲解期终考试题型说明____三、简答27《数据结构》期终考试复习讲解期终考试题型说明____三、简答题示例：三、简单回答下列问题（每题5分，共20分）1、给出二叉树的带权路径长度的定义，给出其公式；简述哈夫曼树（最优二叉树）的定义。。2、简要说明队列的顺序存储结构产生的“假溢出”及解决方案？简述如何判断循环队列的空和满？3、……4、……答（参考答案）：随着元素不断入队列、出队列，rear和front指针会不断向后移动，最终会指向数组的最大下标位置。由于rear和front指针只能单方向移动，这时元素无法入队列，但是队列中仍有大量空闲位置。这种情况称为假溢出。而在命题逻辑中的归结则不需要。解决的方法：1）采用平移元素法，效率低。2）循环队列方法。（2分）采用如下方法判断循环队列的空或满：1）计数器；2）设标志；3）人为浪费一个存储单元）《数据结构》期终考试复习讲解期终考试题型说明____三、简答28《数据结构》期终考试复习讲解期终考试题型说明一、填空题（20分）二、单项选择题（20分）三、简答题（20分）四、应用题（20分）五、算法设计题（20分）本部分将以最基本概念为主，测试范围：第5、8章的最基本内容：树的基本概念及应用；图基本概念与简单应用；期终考试题型说明____四、应用题示例：略《数据结构》期终考试复习讲解期终考试题型说明一、填空题（2029《数据结构》期终考试复习讲解期终考试题型说明本部分将以最基本概念为主，测试范围：第2、3及5章的最基本内容：第二章涉及的有关基本编程第三章涉及的有关基本编程第五章涉及的有关基本编程一、填空题（20分）二、单项选择题（20分）三、简答题（20分）四、简单应用题（20分）五、算法设计题（20分）《数据结构》期终考试复习讲解期终考试题型说明本部分将以最基本30五、算法设计题（共20分）1、试编写一个函数，在一个顺序表A中查找出具有最大值和最小值的整数。#include“SeqList．h”template<classT>voidFindMaxMin(SeqList<int>&A，int&Max，int&Min)；说明：原