三、填空题
设单链表结构为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→freq
p→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(递归结束条件)
可直接求解步