《数据结构导论》考纲、试题、答案
一、考试说明
本课程为闭卷考试（开卷考试、上交论文、上交作品等考查类课程无考试指导）（根据课程考核实际方式选择），考试时间90分钟，考试题型包括以下题型中的三种（根据每门课程的实际确定题型及分值所占比例）：
1、判断题（正确打√，错误打×，每题3分，共15分）
2、填空（每空2分，共20分）
3、选择题（每题3分，共15分）
4、名词解释（每小题4分，共20分）
5、简答题（每题6分，共30分）
备注：以上题型供参考
二、课程知识要点
第一章
◆数据结构
◆实例
第二章
◆银行排队顺序存储
◆学生健康登记表
第三章
◆栈和队列
◆回文
◆杨辉三角
第四章
◆串
◆文本加密
第五章
◆内部排序
◆查找
◆二叉树
第六章
◆树
◆图
◆数组
第七章
◆文件
◆外部排序
备注：根据教材实际章节汇总要点，突出需要掌握的重点内容
三、重点习题
1、判断题
◆具有n 个结点的线索二叉树上，含有n+1个线索。

◆三叉链表属于二叉树存储结构。

◆哈夫曼树不存在度为1的结点。

◆栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。

◆栈和队列的存储方式既可是顺序方式，也可是链接方式。

◆二叉树中每个结点的两棵子树是有序的。

2、填空
◆数据的逻辑结构指
◆一个算法的时间复杂度
◆单链表中，增加头结点的目的
◆表长为0的线性表
◆串的长度
◆若两个串的长度相等且对应位置上的字符也相等
◆常用的插入排序
◆常用的处理冲突的方法
◆常用的选择排序方法
◆衡量一个算法的优劣主要考虑
◆在有n个结点的二叉链表中，空链域的个数
◆常用的选择排序方法
◆具有10个顶点的无向图，边的总数最多为
◆堆排序
◆已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树中
有多少个叶子结点
◆树有三种常用形式
◆深度为5的二叉树至多有多少个结点
3、选择题
◆串是一种特殊的线性表，其特殊性体现在
◆数据的逻辑结构
◆算法
◆在数据结构中，从逻辑上可以把数据结构分成
◆算法分析的目的
◆链接存储的存储结构所占存储空间
◆链表
◆非线性结构是数据元素之间存在一种
4、名词解释
◆数据
◆运算与运算实现的相同点
◆串变量
◆连通分量
◆头指针
5、简答题
◆数据逻辑结构的特点
◆假定一棵二叉树广义表表示为a(b(c,d)),c(((,8))),分别给出先序，中序后序和后序的遍历
结果
◆假定一组记录的排序码为(46，79，56，38，40，84，50，42)，则利用堆排序方法建立的初
始堆为
◆从一维数组A[n)中二分查找关键字为K的元素的递归算法，若查找成功则返回对应元素的下
标，否则返回一1。

IntBinsch(ElemTypeA[]，Intlow，int high，KeyTypeK) { if(low<＝high) { int mid＝(low+high)／2； if(K＝＝A[mid].key)
——； else if (K<A[mid].key)——； else ； } else return—
l； }
◆按所给函数声明编写一个算法，从表头指针为HL的单链表中查找出具有最大值的结点，该最
大值由函数返回，若单链表为空则中止运行。

编写程序？ EIemType MaxValue(LNOde*HL);
◆假设以数组seqn［m］存放循环队列的元素，设变量rear和quelen分别指示循环队列中队尾
元素的位置和元素的个数。

(1) 写出队满的条件表达式； (2) 写出队空的条件表达式；
(3) 设m=40,rear=13,quelen=19,求队头元素的位置； (4) 写出一般情况下队头元素位置
的表达式。

备注：以上题型供参考，根据课程实际安排的题型，将重点考核内容进行整理，所列内容占期末考试内容的70%，不能将期末考试原题进行添加，需要局部进行调整，严禁任何授课教师提前泄题给学生，否则导致责任后果自负。

说明：本考试指导只适用于2013-2014学年度第一学期期末考试使用，包括正考和补考内容。

指导中的章节知识点涵盖考试所有内容，给出的习题为考试类型题，请全体同学认真复习。

祝大家考试顺利！。