数据结构第二章习题 - 下载本文

请填充算法中标出的空白处,完成其功能。 typedef struct node

{int data; struct node *next; }linknode,*link; void Insertsort(link L) { link p,q,r,u;

p=L->next; (1)______; while((2)________) { r=L; q=L->next;

while((3)________&& q->data<=p->data) {r=q; q=q->next;} u=p->next; (4)______; (5)______; p=u; } }

37.下面是一个求两个集合A和B之差C=A-B的程序,即当且仅当e是A的一个元素,但不是B中的一个元素时,e才是C中的一个元素。集合用有序链表实现,初始时,A,B集合中的元素按递增排列,C为空;操作完成后A,B保持不变,C中元素按递增排列。下面的函数append(last,e)是把值为e的新结点链接在由指针last指向的结点的后面,并返回新结点的地址;函数difference(A,B)实现集合运算A-B,并返回表示结果集合C的链表的首结点的地址。在执行A-B运算之前,用于表示结果集合的链表首先增加一个附加的表头结点,以便新结点的添加,当A-B运算执行完毕,再删除并释放表示结果集合的链表的表头结点。 程序(a)(编者略去这个PASCAL程序) 程序(b)

typedef struct node{ int element; struct node *link; }NODE; NODE *A,*B,*C;

NODE *append (NODE *last,int e)

{ last->link=(NODE*) malloc (sizeof(NODE)); last->link->element=e; return(last->link); }

NODE *difference(NODE *A,NODE *B) {NODE *C,*last;

C=last=(NODE*) malloc (sizeof(NODE)); while (1)___

if (A->elementelement) { last=append(last,A->element); A=A->link; } else if (2) ___ { A=A->link; B=B->link; } ELSE (3) ___ ; while (4) __

{ last=append(last,A->element); A=A->link; }

(5) ___; last=C; C=C->link; free (last); return (C); }

/*call form:C=difference(A,B);*/【上海大学 2000 一、4 (10分)】 四 应用题

1.线性表有两种存储结构:一是顺序表,二是链表。试问:

(1)如果有 n个线性表同时并存,并且在处理过程中各表的长度会动态变化,线性表的总

数也会自动地改变。在此情况下,应选用哪种存储结构? 为什么?

(2)若线性表的总数基本稳定,且很少进行插入和删除,但要求以最快的速度存取线性表中的元素,那么应采用哪种存储结构?为什么?

2.线性表的顺序存储结构具有三个弱点:其一,在作插入或删除操作时,需移动大量元素;其二,由于难以估计,必须预先分配较大的空间,往往使存储空间不能得到充分利用;其三,表的容量难以扩充。线性表的链式存储结构是否一定都能够克服上述三个弱点,试讨论之。 3.若较频繁地对一个线性表进行插入和删除操作,该线性表宜采用何种存储结构?为什么? 4.线性结构包括______、______、_______和_______。线性表的存储结构分成______和______。请用类PASCAL语言描述这两种结构。

5.线性表(a1,a2,?,an)用顺序映射表示时,ai和ai+1(1<=i

6. 说明在线性表的链式存储结构中,头指针与头结点之间的根本区别;头结点与首元结点的关系。

7. 试述头结点,首元结点,头指针这三个概念的区别. 8. 已知有如下定义的静态链表: TYPE component=RECORD data:elemtp; next:0..maxsize END

VAR stalist:ARRAY[0..maxsize] OF component;

以及三个指针:av指向头结点,p指向当前结点,pre指向前驱结点,现要求修改静态链表中next域中的内容,使得该静态链表有双向链表的功能,从当前结点p既能往后查找,也能往前查找:

(1) 定义next域中的内容。(用老的next域中的值表示); (2) 如何得到当前结点p的前驱(pre)的前驱,给出计算式; (3) 如何得到p的后继,给出计算式;

9. 在单链表和双向链表中,能否从当前结点出发访问到任何一个结点?

10. 如何通过改链的方法,把一个单向链表变成一个与原来链接方向相反的单向链表? 11. 下面是一算法的核心部分,试说明该算法的功能。 pre:=L↑.next;

{L是一单链表,结点有数据域 data和指针域 next} IF pre<>NIL THEN

WHILE pre↑.next<>NIL DO

BEGIN p:=pre↑.next; IF p↑.data>=pre↑.data THEN pre:=p ELSE return(false) END; return(true);

12. 设单链表结点指针域为next,试写出删除链表中指针p所指结点的直接后继的C语言语句。

13. 设单链表中某指针p所指结点(即p结点)的数据域为data,链指针域为next,请写出在p结点之前插入s结点的操作(PASCAL语句)。

14. 有线性表(a1,a2,?,an),采用单链表存储,头指针为H,每个结点中存放线性表中一个元素,现查找某个元素值等于X的结点。分别写出下面三种情况的查找语句。要求时间尽量少。

(1)线性表中元素无序。(2)线性表中元素按递增有序。 (3)线性表中元素按递减有序。 15.设pa,pb分别指向两个带头结点的有序(从小到大)单链表。仔细阅读如下的程序,

并回答问题: (1) 程序的功能。(2) s1,s2中值的含义。(3) pa,pb中值的含义。 PROCEDURE exam(pa,pb) BEGIN

p1:=pa↑.next; p2:=pb↑.next; pa↑.next:=∧; s1:=0; s2:=0; WHILE p1≠∧ AND p2≠∧ DO

[ CASE p1↑.datap2↑.data: p2:=p2↑.next;

p1↑.data=p2↑.data: [p:=p1; p1:=p1↑.next; p↑.next:= pa↑.next; pa↑.next:= p; p2:= p2↑.next;s1:=s1+1; ]; END ];

WHILE p1≠∧ DO [ p:=p1; p1:=p1↑.next; dispose(p); s2:=s2+1 ] END;

16.写出下图双链表中对换值为23和15的两个结点相互位置时修改指针的有关语句。 结点结构为:(llink,data,rlink)

17.按照下列题目中的算法功能说明,将算法描述片段中的错误改正过来。

(1) (4分)下面的算法描述片段用于在双链表中删除指针变量p所指的结点: p^.rlink←p^.llink^.rlink; p^.llink←p.^rlink^.llink dispose(p); (2) (6分)下面的算法描述片段用于在双链表中指针变量p所指结点后插入一个新结点: new(q);

q^.llink←p; p^.rlink←q;

q^.rlink←p^.rlink; q←p^.rlink^.llink;

18.已知L是一个数据类型linkedlist的单循环链表,pa和pb是指向L中结点的指针。简述下列程序段的功能。 TYPE linkedlist=↑node; node=RECORD data:datatype; next:linkedlist END; PROC Mp(pa,pb:linkedlist); PROC subp(s,q: linkedlist); p:=s;

WHILE p↑.next<>q DO p:=p↑.next; p↑.next:=s ENDP;

subp(pa,pb); subp(pb,pa); ENDP;

19.设双向循环链表中结点的数据域、前驱和后继指针域分别为data,pre和next,试写出在指针p 所指结点之前插入一s结点的C语言描述语句。

20.本题给出一个子程序的框图,如图2,试填空完善此算法框图。该子程序用来寻找第一个均出现在三个整数单向链表f1,f2,f3中的相同整数。假定在调用该子程序前,这三个整数链表已按从小到大的次序排序,单向链表的形式如下图1的例子所示。

注:在图2的框图中:found和exit均为布尔型的变量,可取值为true和false。val是整型变量,用来存放第一个均出现在f1,f2,f3中的相同整数。若f1,f2和f3中无相同的整数,found 的值为false,否则found的值为true。f1↑.link表示访问f1所指结点的link域。 TOP

21. 一线性表存储在带头结点的双向循环链表中,L为头指针。如下算法: (1)说明该算法的功能。(2)在空缺处填写相应的语句。 void unknown (BNODETP *L) { …

p=L->next; q=p->next; r=q->next; while (q!=L)

{ while (p!=L) && (p->data>q->data) p=p->prior; q->prior->next=r;(1) ______; q->next=p->next;q->prior=p;

(2) ______;(3) ______; q=r;p=q->prior; (4) ______; } }

五、算法设计题

1. 假设有两个按元素值递增次序排列的线性表,均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表,并要求利用原来两个单链表的结点存放归并后的单链表。 类似本题的另外叙述有: (1)设有两个无头结点的单链表,头指针分别为ha,hb,链中有数据域data,链域next,两链表的数据都按递增序存放,现要求将hb表归到ha表中,且归并后ha仍递增序,归并中ha表中已有的数据若hb中也有,则hb中的数据不归并到ha中,hb的链表在算法中不允许破坏。 PROCEDURE merge(ha,hb);

(2)已知头指针分别为la和lb 的带头结点的单链表中,结点按元素值非递减有序排列。写出将la 和 lb两链表归并成一个结点按元素值非递减有序排列的单链表(其头指针为 lc),并计算算法的时间复杂度。

2. 图(编者略)中带头结点且头指针为ha和hb的两线性表A和B 分别表示两个集合。两表中的元素皆为递增有序。请写一算法求A和B的并集AUB。要求该并集中的元素仍保持递增有序。且要利用A和B的原有结点空间。 类似本题的另外叙述有:

(1) 已知递增有序的两个单链表A,B分别存储了一个集合。设计算法实现求两个集合的并集的运算A:=A∪B

(2)已知两个链表A和B分别表示两个集合,其元素递增排列。编一函数,求A与B的交集,并存放于A链表中。 (3)设有两个从小到大排序的带头结点的有序链表。试编写求这两个链表交运算的算法(即L1∩L2)。要求结果链表仍是从小到大排序,但无重复元素。

(4)己知两个线性表A ,B均以带头结点的单链表作存储结构,且表中元素按值递增有序排列。设计算法求出A与B的交集C,要求C另开辟存储空间,要求C同样以元素值的递

增序的单链表形式存贮。

(5)已知递增有序的单链表A,B和C分别存储了一个集合,设计算法实现A:=A∪(B∩C),并使求解结构A仍保持递增。要求算法的时间复杂度为O(|A|+|B|+|C|)。其中,|A|为集合A的元素个数。

3. 知L1、L2分别为两循环单链表的头结点指针,m,n分别为L1、L2表中数据结点个数。要求设计一算法,用最快速度将两表合并成一个带头结点的循环单链表。 类似本题的另外叙述有:

(1)试用类Pascal语言编写过程PROC join(VAR la:link; lb:link) 实现连接线性表la和lb(lb在后)的算法,要求其时间复杂度为0(1), 占用辅助空间尽量小。描述所用结构。

(2)设有两个链表,ha为单向链表,hb为单向循环链表。编写算法,将两个链表合并成一个单向链表,要求算法所需时间与链表长度无关。

4. 顺序结构线性表LA与LB的结点关键字为整数。LA与LB的元素按非递减有序,线性表空间足够大。试用类PASCAL语言给出一种高效算法,将LB中元素合到LA中,使新的LA的元素仍保持非递减有序。高效指最大限度的避免移动元素。 5. 已知不带头结点的线性链表list,链表中结点构造为(data、link),其中data为数据域,link为指针域。请写一算法,将该链表按结点数据域的值的大小从小到大重新链接。要求链接过程中不得使用除该链表以外的任何链结点空间

6. 设L为单链表的头结点地址,其数据结点的数据都是正整数且无相同的,试设计利用直接插入的原则把该链表整理成数据递增的有序单链表的算法 类似本题的另外叙述有:

(1)设一单向链表的头指针为head,链表的记录中包含着整数类型的key域,试设计算法,将此链表的记录按照key递增的次序进行就地排序. 7. 设 Listhead为一单链表的头指针,单链表的每个结点由一个整数域DATA和指针域NEXT组成,整数在单链表中是无序的。编一PASCAL过程,将 Listhead链中结点分成一个奇数链和一个偶数链,分别由P,Q指向,每个链中的数据按由小到大排列。程序中不得使用 NEW过程申请空间。

类似本题的另外叙述有:

(1)设计算法将一个带头结点的单链表A分解为两个具有相同结构的链表B、C,其中B表的结点为A表中值小于零的结点,而C表的结点为A表中值大于零的结点(链表A的元素类型为整型,要求B、C表利用A表的结点)。 (2) 设L为一单链表的头指针,单链表的每个结点由一个整数域 data和指针域NEXT组成,整数在单链表中是无序的。设计算法,将链表中结点分成一个奇数链和一个偶数链,分别由P,Q指向,每个链中的数据按由小到大排列,算法中不得申请新的结点空间。

(3) 将一个带头结点的单链表A分解为两个带头结点的单链表A和B,使得A表中含有原表中序号为奇数的元素,而B表中含有原表中序号为偶数的元素,且保持其相对顺序不变。 1) 写出其类型定义: 2) 写出算法。

8. 已知线性表(a1 a2 a3 ?an)按顺序存于内存,每个元素都是整数,试设计用最少时间把所有值为负数的元素移到全部正数值元素前边的算法:例:(x,-x,-x,x,x,-x ?x)变为(-x,-x,-x?x,x,x)。

类似本题的另外叙述有:

(1)设有一元素为整数的线性表L=(a1,a2,a3,?,an),存放在一维数组A[N]中,设计一个算法,以表中an作为参考元素,将该表分为左、右两部分,其中左半部分每个元素小于等于an,右半