数据结构期终考试复习

《数据结构期终考试复习》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1011年度第一学期数据结构总复习复习资料：《数据结构》（面向对象方法与c++语言描述）（第2版）殷人昆编著，清华大学出版社，2007年6月第2版授课讲义（PPT电子讲稿）课程指定参考书和有关参考书网上有关资料数据结构的考察内容自然界分析、思考模拟ADT（抽象）计算机CPUmemory存储处理（算法）数据结构概述（典型结构的相关概念及算法）典型线（非）性结构的表示（ADT）上结构的存储（重点顺序和链式）应用（栈、队列、树、图等）简单的算法设计本次考察范围《数据结构》期终考试复习讲解期终考试题型说明一、填空题（20分）二、单项选择题（20分）三、简答题（20分）四、应用题（20分）

2、五、算法设计题（20分）《数据结构》期终考试复习讲解一、填空题（20分）二、单项选择题（20分）三、简答题（20分）四、应用题（20分）五、算法设计题（20分）期终考试题型说明本部分将以最基本概念为主，测试范围：第1、2、3、4、5、8章的最基本内容：数据结构概论；线性表栈和队列数组、串和广义表的概念树的基本概念图的基本概念1、在线性结构、树形结构和图形结构中，直接前驱和直接后继结点之间分别存在着______________、______________和______________的关系。2、如果加尾指针rear，给出带头结点的非空循环单链表的循环判别条件是___________

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

4、数据结构》期终考试复习一、填空题（20分）二、单项选择题（20分）三、简答题（20分）四、简单应用题（20分）五、算法设计题（20分）期终考试题型说明本部分将以最基本概念为主，测试范围：第1、2、3、4、5、8章的最基本内容：数据结构概论；线性表栈和队列数组、串和广义表的概念树的基本概念图的基本概念《数据结构》期终考试复习期终考试题型说明____二、选择题示例：二、选择题（每题2分，共20分选择正确答案的编号，填在各题前的括号内）（）1、对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是：A、head==NULL；B、head→next==NULL；C、head→n

5、ext==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中首次出现的位

6、置的算法称为：A、求子串；B、联接；C、匹配；D、求串长;（）5、有关二叉树下列说法正确的是：A、二叉树的度为2；B、一棵二叉树的度可以小于2；C、二叉树中至少有一个结点的度为2；D、二叉树中任何一个结点的度都为2；《数据结构》期终考试复习讲解期终考试题型说明本部分将以最基本概念为主，测试范围：第2、3、5章的最基本内容：线性表；栈与队列；树；一、填空题（20分）二、单项选择题（20分）三、简答题（20分）四、简单应用题（20分）五、算法设计题（20分）《数据结构》期终考试复习讲解期终考试题型说明____三、简答题示例：三、简单回答下列问题（每题5分，共20分）1、给出二叉树的带权

7、路径长度的定义，给出其公式；简述哈夫曼树（最优二叉树）的定义。。2、简要说明队列的顺序存储结构产生的“假溢出”及解决方案？简述如何判断循环队列的空和满？3、……4、……答（参考答案）：设二叉树有n个带权值得叶结点，定义从二叉树的根结点到二叉树中所有叶结点的路径长度与相应叶结点权值的乘积之和为二叉树的带权路径长度。WPL(T)=wklk(对所有叶子结点)对于一组具有权值确定权值的叶结点可以构造出多个具有不同带权路径长度的二叉树，把其中最小带权值路径长度的二叉树称作哈夫