数据结构本科复习提要.docx
《数据结构本科复习提要.docx》由会员分享，可在线阅读，更多相关《数据结构本科复习提要.docx（23页珍藏版）》请在冰点文库上搜索。
数据结构本科复习提要
《数据结构》复习提要
清华大学计算机系殷人昆
《数据结构》课程是计算机科学与技术专业的一门重要的专业基础课。
用数字计算机解决任何应用问题都离不开数据表示和数据处理，使用面向对象技术开发软件，数据表示更成为软件构成的基础。
而数据表示和数据处理的核心问题之一就是数据结构及其操作的实现。
这正是《数据结构》课程的内容。
从这个意义上来说,《数据结构》课程在知识学习和技能培养两个方面都处于关键地位。
一、课程要求
《数据结构》是电大计算机科学与技术专业本科生的专业基础课程之一，该课程是后续课程如操作系统、计算机网络等课程的先修课程，在整个教学体系中占据非常重要的地位。
该课程主要讨论在软件开发中如何进行数据结构和算法的设计。
因此，用抽象数据类型以及面向对象的方法组织、存储各种类型的数据是本课程的重点，也是学员需要掌握的重点。
面向对象方法以及结构化技术都是建立高质量软件的技术，通过《数据结构》课程的学习和实践，可以加深对这些先进软件开发方法的理解和体会。
因此，《数据结构》课程的任务是按照软件工程思想，介绍用面向过程和面向对象方法进行数据设计和程序设计的基本思想，在必要的课程实践中逐步熟练掌握。
通过本课程的学习，应达到知识和技能两方面的目标：
1、知识方面：
从数据结构的类定义和对象的使用，以及存储表示和操作的实现两个层次，系统地学习和掌握常用的基本数据结构（包括数组、顺序表、多项式、字符串、链表、栈与队列、优先级队列、广义表、树与森林、二叉树、堆、集合、图、搜索结构、索引结构、散列结构等）及其不同的实现，了解并掌握分析、比较和选择不同数据结构、不同存储结构、不同算法的原则和方法，为后续课程的学习打好基础。
2、技能方面：
系统地学习和掌握对象类的设计方法和面向对象的程序设计风格，在不同的存储结构上实现的算法的设计思想，从中体会和掌握选择结构的方法和算法设计的思考方式及技巧，提高分析问题和解决问题的能力。
二、考核要求
1、命题依据
命题依据是电大计算机科学与技术专业本科生《数据结构教学大纲》。
2、考核要求
本课程考核的重点是考察学员对各种数据结构的理解程度和基于这些数据结构进行算法设计的能力。
具体考核要求分为几个层次：
理解：
要求学员理解各种数据结构的层次、各种数据结构的特点、各种数据结构设计的基本思想。
掌握：
要求学员能较好地理解和运用一两个知识点进行简单的算法设计。
综合应用：
要求学员能综合运用多个知识点的内容进行比较复杂的应用程序开发。
3、命题原则
在教学大纲和考核说明所规定的目的、要求和内容范围之内命题。
试题的考察要求覆盖面广，并适当突出重点。
试题兼顾各个能力层次，理解占40%，简单运用占40%，综合运用占20%。
试题的难易程度和题量适当，按难易程度分为四个层次：
容易占20%，较易占30%，较难占30%，难占20%。
4、试题题型
单选题：
给出一些有关数据结构性质、特点及一些简单算法性能的不完全叙述，要求学员从题后给出的供选择的答案中选择合适的答案，补足这些叙述。
填空题：
给出程序说明及一段部分语句缺失的程序，让学员补充成为完整的程序。
简答题：
应用作图方法或简单计算，使用给定数据建立或操作一些数据结构。
理解问答题：
给出一段程序，就程序回答一些问题，如给出程序运行结果、根据要求进行适当修改等。
综合算法题：
给出算法设计要求，编制出部分算法程序，用来考察几个知识点的综合应用。
具体形式见后面所附“试题类型及规范解答举例”。
5、考核形式
采用期末考核与平时成绩相结合的方式。
其中
✧平时考核：
视平时作业（包括笔做题和上机题）的完成情况给分，占考核总成绩的20%，能够按时、按质、按量完成平时作业者方可得满分；
✧期末考核：
采用笔试，它占总成绩的80%，考试方式为闭卷，答题时限120分钟。
以上两个成绩累计60分以上（包括60分）算考核通过。
附录：
试题类型及规范解答举例
一、单选题[从供选择的答案中选出正确的答案，将其编号填入括号（）中]
1、在数据结构的讨论中把数据结构从逻辑上分为（A）。
2、采用线性链表表示一个向量时，要求占用的存储空间地址（B）。
3、采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为（C）。
4、在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点s，则执行（D）。
5、如果想在4092个数据中只需要选择其中最小的5个，采用（E）方法最好。
6、设有两个串t和p，求p在t中首次出现的位置的运算叫做（F）。
7、在数组A中，每一个数组元素A[i][j]占用3个存储字，行下标i从1到8，列下标j从1到10。
所有数组元素相继存放于一个连续的存储空间中，则存放该数组至少需要的存储字数是（G）。
8、将一个递归算法改为对应的非递归算法时，通常需要使用（H）。
9、一个队列的进队列顺序是1,2,3,4，则出队列顺序为（I）。
10、在循环队列中用数组A[0..m-1]存放队列元素，其队头和队尾指针分别为front和rear，则当前队列中的元素个数是（J）。
【供选择的答案】
A：
内部结构与外部结构静态结构与动态结构
线性结构与非线性结构紧凑结构与非紧凑结构
B：
必须是连续的部分地址必须是连续的
一定是不连续的可连续可不连续
C：
nn/2（n-1）/2（n+1）/2
D：
s→link=p→link;p→link=s;p→link=s;s→link=q;
p→link=s→link;s→link=p;q→link=s;s→link=p;
E：
起泡排序堆排序锦标赛排序快速排序
F：
求子串模式匹配串替换串连接
G：
80100240270
H：
栈队列循环队列优先队列
I：
4,3,2,12,4,3,11,2,3,43,2,1,4
J：
（front-rear+1）%m（rear-front+1）%m
（front-rear+m）%m（rear-front+m）%m
二、阅读理解题[给出下列递归过程的执行结果]
（1）voidunknown（intw）{
if（w）{
unknown（w-1）;
for（inti=1;i<=w;i++）cout<cout<}
}
调用语句为unknown（4）。
（2）voidunknown（intn）{
cout<if（int（n/10））unknown（int（n/10））;
}
调用语句为unknown（582）。
（3）intunknown（intm）{
intvalue;
if（!
m）value=3;
elsevalue=unknown（m-1）+5;
returnvalue;
}
执行语句为cout<三、填空题
设单链表结构为structListNode{
intdata;
ListNode*link;
};
下面的程序是以单链表为存储结构,实现二路归并排序的算法,要求链表不另外占用存储空间,排序过程中不移动结点中的元素,只改各链结点中的指针,排序后r仍指示结果链表的第一个结点。
在初始状态下,所有待排序记录链接在一个以r为头指针的单链表中。
例如,
在算法实现时，利用了一个队列做为辅助存储,存储各有序链表构成的归并段的链头指针。
初始时,各初始归并段为只有一个结点的有序链表。
队列的数据类型为Queue,其可直接使用的相关操作有
置空队列操作：
makeEmpty（）;
将指针x加入到队列的队尾操作：
EnQueue（ListNode*x）;
退出队头元素,其值由函数返回的操作：
ListNode*DlQueue（）;
判队列空否的函数,空则返回1,不空则返回0：
intIsEmpty（）。
解决方法提示：
程序首先对待排序的单链表进行一次扫描,将它划分为若干有序的子链表,其表头指针存放在一个指针队列中。
当队列不空时,从队列中退出两个有序子链表,对它们进行二路归并,结果链表的表头指针存放到队列中。
如果队列中退出一个有序子链表后变成空队列,则算法结束。
这个有序子链表即为所求。
在算法实现时有6处语句缺失，请阅读程序后补上。
（1）两路归并算法
voidmerge（ListNode*ha,ListNode*hb,,ListNode*&hc）{
ListNode*pa,*pb,*pc;
if（ha→data<=hb→data）{hc=ha;pa=ha→link;pb=hb;}
else{hc=hb;pb=hb→link;pa=ha;}
pc=hc;
while（pa&&pb）
if（
）
{pc→link=pa;pc=pa;
;
}
else
{pc→link=pb;pc=pb;
;
}
if（pa）pc→link=pa;
elsepc→link=pb;
};
（2）归并排序主程序
voidmergesort（ListNode*r）{
ListNode*s,t;QueueQ;
if（!
r）return;
s=r;
;
while（s）{
t=s→link;
while（t!
=0&&s→data<=t→data）{s=t;t=t→link;}
if（t）{
s→link=0;s=t;
;
}
}
while（!
Q.IsEmpty（））{
r=Q.DlQueue（）;
if（Q.IsEmpty（））break;
s=Q.DlQueue（）;
merge（r,s,t）;
;
}
}
四、简答题
（1）在一个有n个元素的顺序表的第i个元素（1in）之前插入一个新元素时，需要向后移动多少个元素？
（2）当一个栈的进栈序列为时，可能的出栈序列有多少种？
是否是合理的出栈序列？
（3）简单（直接）选择排序是一种稳定的排序方法吗？
试举例说明？
（4）设有序顺序表为{10,20,30,40,50,60,70}，采用折半搜索时，搜索成功的平均搜索长度是多少？
五、综合算法题
试设计一个实现下述要求的查找运算函数Locate。
设有一个带表头结点的双向链表L，每个结点有4个数据成员：
指向前驱结点的指针llink、指向后继结点的指针rlink，存放字符数据的成员data和访问频度freq。
所有结点的freq初始时都为0。
每当在链表上进行一次Locate（L,x）操作时，令元素值为x的结点的访问频度freq加1，并将该结点前移，链接到与它的访问频度相等的结点后面，使得链表中所有结点保持按访问频度递减的顺序排列，以使频繁访问的结点总是靠近表头。
【试题答案】
一、答案:
A：
B：
C：
D：
E：
F：
G：
H：
I：
J：
二、答案：
（1）1
22
333
4444
（2）285
（3）18
三、答案：
pa→data<=pb→datapa=pa→linkpb=pb→link
Q.EnQueue（r）Q.EnQueue（s）Q.EnQueue（t）
四、答案：
（1）n-i+1
（2）可能的出栈序列有
种，不是合理的出栈序列。
（3）是不稳定的排序方法。
下面就是不稳定的例子。
只要能举出反例即可。
{275275*512061}i=1
{061275*512275}i=2
{061275*512275}i=3
{061275*275512}
（4）ASLsucc=（1*1+2*2+3*4）/7=17/7
五、答案：
（1）定义链表结构
structDoubleListNode{
chardata;
intfreq;
DoubleListNode*llink,*rlink;
};
初始时，所有结点的freq域的值都为0。
（2）定义函数
DoubleListNode*locate（DoubleListNode*f;char&x）{
DoubleListNode*p,*q;
p=f→rlink;/*跳过表头结点*/
while（p!
=NULL&&p→data!
=x）p=p→rlink;/*搜索*/
if（p）{
p→freq++;q=p→llink;
p→rlink→llink=q;q→rlink=p→rlink;/*从链中摘下p*/
while（q!
=f&&q→freqp→llink=q;
p→rlink=q→rlink;q→rlink→llink=p;
q→rlink=p;/*在q后面插入p*/
}
returnp;
}
三、数据结构复习提要
第一章有关数据结构和算法分析的基本知识
本章主要讨论贯穿和应用于整个《数据结构》课程始终的基本概念和性能分析方法。
学习本章的内容，将为后续章节的学习打下良好的基础。
本章复习的要点：
1、基本知识点
要求理解的概念包括：
数据，数据对象，数据元素或数据成员，数据结构，数据类型，数据抽象，抽象数据类型，数据结构的抽象层次，面向对象，对象与类的关系，类的继承关系，对象间的消息通信等。
需要对各个概念进行区分与比较。
例如，按照面向对象建模技术的要求，把建立对象类作为一个层次，把建立对象间的关系（即建立结构）作为另外的层次。
因此，在软件开发中做数据结构设计时，不但要设计对象–类，类的属性，类的操作，还要建立类的实例之间的关系。
从这个角度考虑，把数据结构定义为数据对象及对象中各数据成员之间关系的集合是合理的。
又例如，对象–类class或struct与C中的结构类型struct的区别在于前者不但有对象的状态描述（数据成员），还加入了操作（成员函数），描述对象的行为，这样可以体现一个完整的实体概念，而后者不行。
再例如，传统的数据结构概念从数据结构的逻辑结构、物理结构和相关操作等3个方面进行讨论。
它反映了数据结构设计的不同层次：
逻辑结构属于问题解决范畴，物理结构是逻辑结构在计算机中的存储方式。
但在面向对象开发模式中，本课程中涉及的数据结构都属于基本数据结构，但有的属于应用级的数据结构，如稀疏矩阵，字符串，栈与队列，优先级队列，图等；有的属于实现级的数据结构，如数组，链表，堆，索引，散列表等。
2、有关算法的概念和简单的算法性能分析方法
算法的5个特性表明算法的实现属于面向过程的开发模式，即传统的“输入―计算―输出”模式。
算法的应用要求明确算法的时间和空间代价。
因此，必须理解算法的定义和算法的5个特性，掌握简单的时间复杂度估计和空间复杂度估计方法（不讨论程序复杂性）。
3、描述语言
要求数据结构的描述既要体现算法的逻辑，又要体现面向对象的概念，需要一种能够兼有面向对象和面向过程双重特性的描述语言。
传统的Pascal语言和C语言只是面向过程的语言，不能适应面向对象的开发模式。
因此，采用C++语言描述。
要求学员基本掌握C++语言的基本概念和用C++语言编写应用程序的基本技术。
例如，用类定义抽象数据类型的方式，定义模板类、抽象类的方法，函数与参数的定义，建立类（公有、私有）继承的方法，例外与异常的处理等等，都需要掌握。
4、复习参考题：
1-1，1-2，1-4，1-7，1-8，1-9
第二章数组
本章主要讨论数组抽象数据类型及利用数组实现的顺序表、字符串等数据结构。
它们都是线性结构。
但数组是直接存取结构，可以根据数组元素的下标直接在数组中存取该元素，而利用它实现的顺序表是顺序存取结构，所有数据元素集中存储于表的前端。
字符串是顺序表的特化。
本章复习的要点：
1、基本知识点
理解作为抽象数据类型定义的数组类，掌握在C++中数组的定义和初始化方法，明确静态数组和动态数组的不同特点和使用，特别需要注意的是数组的存储结构不一定是一个连续的存储空间，当数组存放于一个连续的存储空间时叫做数组的顺序存储方式。
要求掌握一维数组、二维数组、三维数组的地址计算方法。
需要明确：
数组是一种实现级的结构。
其次，需要理解顺序表的定义和特点，顺序表的类定义及其主要操作，如搜索、插入和删除的实现，掌握对它们的性能估计，包括搜索算法的平均搜索长度，插入与删除算法中的对象平均移动次数。
还要掌握顺序表实例的定义和使用事例。
此外，需要理解字符串的定义，字符串抽象数据类型的类定义，字符串中各种重载操作的实现和使用，简单的模式匹配算法和匹配事例。
2、算法设计
静态数组对象的定义，动态数组对象的定义
数组中数组元素的原地逆置
递归计算数组长度、数组中所有元素的和及平均值
在顺序表中搜索值为item的元素，在有序顺序表中搜索值为item的元素
在有序顺序表中插入新元素item到第i个位置
在有序顺序表中删除第i个元素
两个有序顺序表的合并，m个有序顺序表的合并
3、复习参考题：
2-3，2-5，2-7，2-8，2-9，2-10，2-13，2-14，2-15，2-16
第三章链接表
本章主要讨论最简单的链表结构―单链表。
详细地介绍了单链表的抽象数据类型，单链表的类定义，相应操作的实现，引入了带表头结点的单链表结构。
进一步定义了用模板描述的单链表类。
作为一种应用，讨论了一元多项式的类定义及其加法操作的实现。
此外，讨论了循环链表和双向链表。
在复习这一章时需要对C++语言中的指针和引用类型的使用有清楚的理解。
对带表头结点的链表和不带表头结点的链表在插入、删除、搜索时的差别有清楚的认识。
而且需要明确：
链表是一种实现级的结构。
本章复习的要点：
1、基本知识点
单链表是一种线性结构，链表各结点的物理存储可以是不连续的，因此各结点的逻辑次序与物理存放次序可以不一致。
必须理解单链表的定义和特点，单链表的抽象数据类型和类定义，单链表成员函数，如构造函数、搜索、插入、删除等操作的实现，对比带表头结点单链表的搜索、插入、删除操作，比较其优缺点。
其次是循环链表的定义和特点，它与单链表的差别，它的搜索、插入、删除操作的实现。
最后是双向链表的定义，它的插入与删除操作的实现。
2、算法设计
单链表的迭代求解算法，包括统计链表结点个数，在链表中寻找与给定值value匹配的结点，在链表中寻找第i个结点，在链表中第i个位置插入新结点，删去第i个结点，单链表各结点顺序逆转算法，在单链表中按从左到右和从右到左的顺序遍历的逆转链算法。
带表头结点的单链表的迭代算法，包括统计链表结点个数，在链表中寻找与给定值value匹配的结点，在链表中寻找第i个结点，在链表中第i个位置插入新结点，删去第i个结点，连续删除链表中含有value值的结点，两个有序链表的合并。
单链表的递归算法，包括统计链表结点个数，在链表中寻找与给定值value匹配的结点，在链表中寻找第i个结点，求链表各结点值的和，求链表各结点的值的平均值。
循环链表的迭代算法：
包括统计链表结点个数，在链表中寻找与给定值value匹配的结点，在链表中寻找第i个结点，在链表中第i个位置插入新结点，删去第i个结点，将循环链表链入单链表的表头。
多项式的建立，两个多项式的相加，两个多项式的相减。
用单链表实现字符串操作，每个结点仅存一个字符。
3、复习参考题：
3-1，3-2，3-6，3-8，3-9，3-10
第四章栈与队列
本章主要讨论3种线性结构：
栈、队列与优先级队列。
这3种结构都是顺序存取的表，而且都是限制存取点的表。
栈限定只能在表的一端（栈顶）插入与删除，其特点是先进后出。
队列和优先级队列限定只能在表的一端（队尾）插入在另一端（队头）删除，不过优先级队列在插入和删除时需要根据数据对象的优先级做适当的调整，令优先级最高的对象调整到队头，其特点是优先级高的先出。
而队列不调整，其特点是先进先出。
这几种结构在开发各种软件时非常有用。
本章复习的要点：
1、基本知识点
要求理解栈的定义和特点，栈的抽象数据类型和在递归和表达式计算中的使用，在栈式铁路调车线上当进栈序列为1,2,3,,n时，可能的出栈序列计数，栈的顺序存储表示和链接存储表示，特别要注意，链式栈的栈顶应在链头，插入与删除都在链头进行。
另外，需要理解队列的定义和特点，队列的抽象数据类型和在分层处理中的使用，队列的顺序存储表示（循环队列）和链接存储表示，需要注意的是，链式队列的队头应在链头，队尾应在链尾。
还需要理解优先级队列的定义和特点。
优先级队列的最佳存储表示是堆（heap），本章介绍的表示看懂即可。
2、算法设计
栈的5种操作（进栈、退栈、取栈顶元素、判栈空、置空栈）的在顺序存储表示下的实现，以及在链接存储表示下的实现。
使用栈的后缀表达式计算算法
双栈共用一个数组的进栈、退栈、置空栈、判栈空算法及栈满、栈空条件
使用两个栈模拟一个队列时的进队列和出队列算法
循环队列的进队列、出队列、取队头元素、判队列空、置空队列操作的实现
使用tag区分队列空和队列满的循环队列的进队列和出队列操作的实现
链式队列的进队列、出队列、取队头元素、判队列空、置空队列操作的实现
使用队尾指针rear和队列长度length的链式队列的进队列、出队列、取队头元素、判队列空、置空队列操作的实现
队列在分层处理中的使用事例（杨辉三角形按层次打印）
双端队列的顺序存储表示及其进队列、出队列算法及队空、队满条件
3、复习参考题：
4-2，4-4，4-9，4-10，4-12，4-14
第五章递归与广义表
本章主要讨论递归过程和广义表。
一个递归的定义可以用递归的过程计算，一个递归的数据结构可以用递归的过程实现它的各种操作，一个递归问题也可以用递归的过程求解。
因此，递归算法的设计是必须掌握的基本功。
递归算法的一般形式：
voidp（参数表）{
if（递归结束条件）
可直接求解步
升级会员 