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