第二章 线性表

第二章 线性表 一、选择题

1. 下面关于线性表的叙述错误的是（ ）。

A.线性表采用顺序存储必须占用一片连续的存储空间 B. 线性表采用链式存储不必占用一片连续的存储空间 C. 线性表采用链式存储便于插入和删除操作的实现 D. 线性表采用顺序存储便于插入和删除操作的实现 2. 设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为（ ）。

A.q=p->next；p->data=q->data；p->next=q->next；free(q)； B. q=p->next；q->data=p->data；p->next=q->next；free(q)； C. q=p->next；p->next=q->next；free(q)； D. q=p->next；p->data=q->data；free(q)；

3. 设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（ ）。

A. O(n) B. O(nlog2n) C. O(1) D. O(n2)

4．设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为（ ）。

2

A. O(log2n) B. O(1) C. O(n) D. O(n)

5．设一条单链表的头指针变量为head且该链表没有头结点，则其判空条件是（ ）。 A. head==0 B.head->next==0 C. head->next==head D.head!=0

6．设带有头结点的单向循环链表的头指针变量为head，则其判空条件是（ ）。 A. head==0 B. head->next==0 C. head->next==head D. head!=0

7．建立一个长度为n的有序单链表的时间复杂度为（ ） A. O(n) B. O(1) C. O(n2) D. O(log2n)

8．设顺序线性表中有n个数据元素，则删除表中第i个元素需要移动（ ）个元素。

A. n-i B. n+l -i C. n-1-i D. i

9．设指针变量p指向双向链表中结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X的操作序列为（ ）。 A. p->right=s； s->left=p； p->right->left=s； s->right=p->right； B. s->left=p；s->right=p->right；p->right=s； p->right->left=s；

C. p->right=s； p->right->left=s； s->left=p； s->right=p->right； D. s->left=p；s->right=p->right；p->right->left=s； p->right=s；

10．设某链表中最常用的操作是在链表的尾部插入或删除元素，则选用下列（ ）存储方式最节省运算时间。 A. 单向链表 B .单向循环链表 C. 双向链表 D. 双向循环链表

1

11．设指针q指向单链表中结点A，指针p指向单链表中结点A的后继结点B，指针s指向被插入的结点X，则在结点A和结点B插入结点X的操作序列为（ ）。

A. s->next=p->next；p->next=-s； B. q->next=s； s->next=p； C. p->next=s->next；s->next=p； D. p->next=s；s->next=q； 12．在一个长度为n的顺序存储的线性表中，向第i个元素（1≤i≤n+1）之前

插入一个新元素时，需要从后向前依次后移（ ）个元素。 A．n-i B．n-i+1 C．n-i-1 D．i

13．在一个单链表HL中，若要在指针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; 14．在单链表中，存储每个结点需要有两个域，一个是数据域，另一个是指针域，指针域指向该结点的（ ） A.直接前趋 B.直接后继 C.开始结点 D.终端结点

15．将两个各有n个元素的有序表合并成一个有序表，其最少的比较次数为

（ ）

A.n B.2n-1 C.2n D.n2

16．线性表采用链式存储结构时，要求内存中可用存储单元的地址( ) A. 必须是连续的 B. 必须是部分连续的 C. 一定是不连续的 D. 连续和不连续都可以

17．设h是指向非空带表头结点的循环链表的头指针，p是辅助指针。执行程序段

p=h;

while (p->next->next!=h) p=p->next;

p->next=h;

后（其中，p->next为p指向结点的指针域），则( ) A. p->next指针指向链尾结点 B. h指向链尾结点 C. 删除链尾前面的结点 D. 删除链尾结点

18．设顺序表有19个元素，第一个元素的地址为200，且每个元素占3个字节，则第14个元素的存储地址为( ) A.236 B.239 C.242 D.245 19．设顺序表有9个元素，则在第3个元素前插入一个元素所需移动元素的个数为( )

A.5 B.6 C.7 D.9

20．设p为指向双向循环链表中某个结点的指针，p所指向的结点的两个链域分别用p→llink和p→rlink表示，则同样表示p指针所指向结点的表达式是( ) A.p→llink B.p→rlink C.p→llink→llink D.p→llink→rlink

21．一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元

2

素的存储地址是( )

A. 110 B. 108 C. 100 D. 120 22．关于存储相同数据元素的说法中正确的是（ ） A．顺序存储比链式存储少占空间 B.顺序存储比链式存储多占空间

C.顺序存储和链式存储都要求占用整块存储空间 D.链式存储比顺序存储难于扩充空间

23．已知一个单链表中，指针q指向指针p的前趋结点，若在指针q所指结点和指针p所指结点之间插入指针s所指结点，则需执行（ ） A．q→next=s；p→next=s； B.q→next=s；s→next=p； C.q→next=s；q→next=p； D.q→next=s；s→next=q； 24．在长度为n的线性表中删除一个指针p所指结点的时间复杂度是（ ） A．O(n) B.O(1) C.O(log2n) D.O(n2) 25．若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则最节省运算时间的存储方式是（ ） A.单链表 B.仅有头指针的单循环链表 C.双链表 D.仅有尾指针的单循环链表

26．从一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，需向前移动的元素的个数是（ ）

A.n-i B.n-i+1 C.n-i-1 D.i

27．对于长度为n的顺序表执行删除操作，则其结点的移动次数（ ） A.最少为0，最多为n B.最少为1，最多为n C.最少为0，最多为n-1 D.最少为1，最多为n-1

28．在一个单链表中，若p所指结点是q所指结点的前驱结点，则删除结点q的正确操作是（ ） A. p->next=q B. p->next=q->next C. p=q->next D. p->next=q->next->next 29．在一个具有n个结点的有序单链表中插入一个新结点，并使插入后仍然有序，则该操作的时间复杂性量级为（ ）

A．O（1） B．O（n） C．O（nlog2n） D．O(n2)

30．顺序存储的线性表（a1,a2,?,an）,在任一结点前插入一个新结点时所需移动结点的平均次数为（ ）

A．n B．n/2 C．n+1 D．(n+1)/2

31．设单链表中指针p指向结点A，若删除A后的结点存在，则需要修改指针的操作为（ ）。

A．p->next=p->next->next B．p=p->next C．p=p->next->next D．p->next=p 32．线性表的链式存储实现有利于（ ）运算。 A．插入 B．读表元 C．查找 D．定位

33．从一个长度为n的顺序表中删除第i个元素(1≤i≤n)，需向前移动（ ）

3

个元素。

A．n-i B．n-i+1 C．n-i-1 D．i

34．在一个长度为n的顺序存储线性表中，向第i个元素(1≤i≤n+1)之前插入一个新元素时，需向后移动（ ）个元素。 A．n-i B．n-i+1 C．n-i-1 D．i

35．在一个单链表中，已知*q结点是*p结点的前趋结点，若在*q和*p之间插入*s结点，则需执行（ ）。

A．s->next=p->next; p->next=s; B．q->next=s; s->next=p; C．p->next=s->next; s->next=p; D．p->next=s; s->next=q;

36．在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行（ ）。

A.HL = p; p->next = HL; B.p->next = HL; HL = p; C.p->next = HL; p = HL;

D.p->next = HL->next; HL->next = p;

37．在一个单链表HL中，若要删除由指针q所指向结点的后继结点，则执行（ ）。

A.p = q->next ; p->next = q->next; B.p = q->next ; q->next = p;

C.p = q->next ; q->next = p->next;

D.q->next = q->next->next; q->next = q; 38．线性表采用链式存储时，其地址（ ）。

A．必须是连续的 B．部分地址必须是连续的 C．一定是不连续的 D．连续与否均可以

39．在一个长度为n的线性表中插入第i个元素的操作中，i的取值范围是 A．1≤i≤n B．0≤i≤n C．1≤i≤ n+1 D．1≤i≤n-1 40．如果要查找单链表中的第i个元素，应该从（ ）开始进行查找。 A．第i个结点 B． 头结点 C． 尾结点 D． 任意一个结点 41．在一个长度为n的线性表中顺序查找值为x的元素时，查找时的平均查找长度（即x同元素的平均比较次数，假定查找每个元素的概率都相等）为（ ）。 A.n B.n/2 C. (n+1)/2 D. (n-1)/2

42．在一个单链表HL中，若要在指针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;

43. 在一个单链表中,若q所指结点是p所指结点的前驱结点,若在q与p之间插入一个s所指的结点,则执行( )。

A. s→link=p→link; p→link=s; B. p→link=s; s→link=q; C . p→link=s→link; s→link=p; D. q →link=s; s→link =p; 44. 线性链表不具有的特点是（ ）。

4

A．随机访问 B．不必事先估计所需存储空间大小

C．插入与删除时不必移动元素 D．所需空间与线性表长度成正比

45. 下述哪一条是顺序存储结构的优点？（ ）。

A． 插入运算方便 B．可方便地用于各种逻辑结构的存储表示 C．存储密度大 D．删除运算方便

46. 下面关于线性表的叙述中，错误的是哪一个？（ ）。 A．线性表采用顺序存储，必须占用一片连续的存储单元。 B．线性表采用顺序存储，便于进行插入和删除操作。

C．线性表采用链接存储，不必占用一片连续的存储单元。 D．线性表采用链接存储，便于插入和删除操作。

47. 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。

A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表 48．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。

A. 单链表 B. 仅有头指针的单循环链表 C. 双链表 D. 仅有尾指针的单循环链表

49．设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( )最节省时间。

A. 带头结点的双循环链表 B.单循环链表 C. 带尾指针的单循环链表 D. 单链表 50．若线性表最常用的操作是存取第I个元素及其前驱和后继元素的值，为节省时间应采用的存储方式( )。

A.单链表 B.双向链表 C.单循环链表 D.顺序表 51．静态链表中指针表示的是( )

A.下一元素的地址 B.内存储器的地址

C.下一元素在数组中的位置 D.左链或右链指向的元素的地址 52．在n个结点的线性表的数组实现中，算法的时间复杂性是O(1)的操作是( ) A. 访问第i个结点(1≤i<=n)和求第i个结点的直接前驱(2≤i<=n) B. 在第i个结点后插入一个新结点(1≤i<=n) C. 删除第i个结点(1≤i<=n) D. 以上都不对

53．(1) 静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关。

(2) 静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。

(3) 静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。 以上错误的是（ ）。

A．（1），（2） B．（1） C．（1），（2）,(3) D.（2） 54．对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（ ）。 A．O(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1)

5

55．单链表中，增加一个头结点的目的是为了( ）。

A．使单链表至少有一个结点 B．标识表结点中首结点的位置 C．方便运算的实现 D．说明单链表是线性表的链式存储

56．对于双向循环链表,在p指针所指的结点之后插入s指针所指结点的操作应为（ ）。 A．p->right=s ; s->left=p; p->right->left=s ; s->right=p->right; B．p->right=s ; p->right->left=s ; s->left=p; s->right=p->right; C．s->left=p; s->right=p->right; p->right=s ; p->right->left=s ; ;

D．s->left=p; s->right=p->right; p->right->left=s ; p->right=s ; 57．对于一个线性表既要求能够进行较快速的插入和删除，又要求存储结构能反映数据之间的逻辑关系，则应该用( )。

A. 顺序存储方式 B. 链式存储方式 C. 散列存储方式 D. 以上均可以 58．在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（ ）。 A．p->next=s;s->next=p->next; B． s->next=p->next;p->next=s; C．p->next=s;p->next=s->next; D． p->next=s->next;p->next=s; 59．线性表的顺序存储结构是一种（ ）。

A. 随机存取的存储结构 B. 顺序存取的存储结构 C. 索引存取的存储结构 D. Hash存取的存储结构 60．顺序表是线性表的（B ）

A、链式存储结构 B、顺序存储结构 C、索引存储结构 D、散列存储结构 61．带头结点的单链表head为空的条件是（ B ） A、head=NULL B、head->next=NULL C、head->next=head D、head!=NULL 62．链表不具有的特点是（ B ）

A．插入、删除不需要移动元素 B．可随机访问任一元素

C．不必事先估计存储空间 D．所需空间与线性长度成正比 63．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ A ）存储方式最节省时间。 A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表

64．下面关于线性表的叙述中，错误的是哪一个？（ B ） A．线性表采用顺序存储，必须占用一片连续的存储单元。 B．线性表采用顺序存储，便于进行插入和删除操作。

C．线性表采用链接存储，不必占用一片连续的存储单元。 D．线性表采用链接存储，便于插入和删除操作。

二、填空题

1．设顺序线性表中有n个数据元素，则第i个位置上插入一个数据元素需要移动表中_______个数据元素；删除第i个位置上的数据元素需要移动表中_______个元素。n+1-i，n-i

2. 设指针变量p指向双向循环链表中的结点X，则删除结点X需要执行的语句序列为_________________________________________________________（设结点中的两个指针域分别为llink和rlink）。p>llink->rlink=p->rlink; p->rlink->llink=p->rlink

6

3．设指针变量p指向单链表中结点A，则删除结点A的语句序列为：

q=p->next；p->data=q->data；p->next=___________；feee(q)；q->next 4．在带头结点的单链表L中, 第一个元素所对应的结点的指针表达式是_____________。L->next

5．在双向循环链表中，在结点*Ｐ之前插入结点*Ｓ的语句序列是：

S-> prior = P-> prior ; S->next=P; P->prior=S; __________________。S-> prior->next=S;

6．在有n个元素的链队列中，入队和出队操作的时间复杂度分别为_____O(1)____和______O(1)____。

7．在双链表中，存储一个结点有三个域，一个是数据域，另两个是指针域，分别指向_ _和_ 。前驱、后继

8．在循环队列中，存储空间为0~n-1。设队头指针front指向队头元素前一个空闲元素，队尾指针指向队尾元素，那么其队空标志为rear=front，队满标志为_ ______。_(rear+1)%n=front

9．下面程序段的功能是利用从尾部插入的方法建立单链表的算法，请在下划线处填上正确的内容。

typedef struct node {int data; struct node *next;} lklist; void lklistcreate(_____________ *&head ) {

for (i=1;i<=n;i++) {

p=(lklist

*)malloc(sizeof(lklist));scanf(“%d”,&(p->data));p->next=0;

if(i==1)head=q=p;else {q->next=p;____________;} } }

lklist，q=p

10．设指针p指向单链表中结点A，指针s指向被插入的结点X，则在结点A的前面插入结点X时的操作序列为：

1) s->next=___________；2) p->next=s；3) t=p->data； 4) p->data=___________；5) s->data=t；p->next，s->data

11．设指针变量p指向单链表中结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X需要执行的语句序列：s->next=p->next; _________________;。p->next=s

12．设指针变量head指向双向链表中的头结点，指针变量p指向双向链表中的第一个结点，则指针变量p和指针变量head之间的关系是p=_________和head=__________（设结点中的两个指针域分别为llink和rlink）。head->rlink，p->llink

13．设指针变量p指向双向链表中的结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X的操作序列为_________=p；s->right=p->right；__________=s； p->right->left=s；（设结点中的两个指针域分别为left和right）。s->left=p，p->right

14．设指针变量p指向单链表中结点A，指针变量s指向被插入的新结点X，则进行插入操作的语句序列为__________________________（设结点的指针域为

7

next）。s->next=p->next; p->next=s

15．在一个单链表HL 中，若要向表头插入一个由指针p指向的结点，则应执行语句： 。p->next=HL; HL=p;

16．在采用独立结点构成的双向链表中，设p和q 分别是具有Dnode * 类型的指针变量。若双向链表中p结点之后插入一个q结点，其操作步骤为：

； ； ； ； q->right=p->right;

if (p->right) p->right->left=q; q->left=p; p->right=q; 17．对于一个顺序存储的线性表，在表头插入元素的时间复杂度为____________,在表尾插入元素的时间复杂度为________________。O(n) O(1)

18．在一个长度为n的顺序表中第i个元素（1≤i≤n）之前插入一个元素时，需向后移动___n-i+1_____个元素。

19．设双链表中结点的前趋指针和后继指针的域名分别为t1和r1，指针s指向双链表中的一个结点（该结点既非头结点，也非尾结点），则删除s指针所指向结点的操作为“s->tl->r1=s->r1；”和“__s->rl->tl=s->tl_______”。

20．设有指针head指向不带表头结点的单链表，用next表示结点的一个链域，指针p指向与链表中结点同类型的一个新结点。现要将指针p指向的结点插入表中，使之成为第一个结点，则所需的操作为“p→next=head；”和“__head=p________”。

21．单链表中逻辑上相邻的两个元素在物理位置上_____不一定_____相邻。 22．在一个长度为n的数组中删除第i个元素（1≤i≤n）时，需要向前移动的元素的个数是_____n-i_____。

23．在顺序表上读表元算法的时间复杂度为___O（1）____。

24．双链表中前驱指针为prior，后继指针为next，在指针P所指结点前插入指针S所指的结点，需执行下列语句：

S→next=P;S→prior=P→prior;P→prior=S;__p->prior->next=s_____;

next 25．设某非空双链表，其结点形式为prior data q所，若要删除指针 指向的结点，则需执行下述语句段：

q->prior->next＝q->next; _q->next->prionr=p->prior____。 26．对长度为n的顺序表执行删除操作，其删除算法在最坏情况下的时间复杂性为__O（n）。

27．在一个长度为n的顺序表中插入一个元素，最少需要移动 元素，最多需要移动 元素，0，n; 28．双向循环链表的优点是 既可以方便的找到后继结点又可以方便的找到前驱结点。

29．在一个长度为n的顺序表中删除一个元素，最少需移动 个元素，最多需移动________个元素。0 n－1

30．在长度为n的顺序表中插入第i个元素（假设i值可操作），要将元素从第

8

个到第 个元素向 （前或后）移动。 n 、 i+1 、 后 31．将指向单链表中的某个结点的指针p移动到该结点的后继结点表示为 。 p=p->next

32．在线性表的单链接存储结构中，每个结点包含有两个域，一个叫 域，另一个叫 域。元素值、指针

33．在下面数组a中链接存储着一个线性表，表头指针为a[0].next，则该线性表为 。

a 012345678 data605642387425

next4376201

( 38 , 56 , 25 , 60 , 42 , 74 )

34．对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为 ，在表尾插入元素的时间复杂度为 。O(n)、O(1)

35．对于一个长度为n的单链接存储的线性表，在表头插入元素的时间复杂度为 ，在表尾插入元素的时间复杂度为 。O (1)、O(n)

36．在线性表的顺序存储中，若一个元素的下标为i，则它的前驱元素的下标为 ，后继元素的下标为 。i-1、i+1

37．在线性表的单链接存储中，若一个元素所在结点的地址为p，则其后继结点的地址为 ，若假定p为一个数组a中的下标，则其后继结点的下标为 。p->next 、a[p].next

38．在循环单链表中，最后一个结点的指针指向 结点。表头

39．在双向链表中每个结点包含有两个指针域，一个指向其 结点，另一个指向其 结点。前驱、后继

40．在循环双向链表中表头结点的左指针域指向 结点，最后一个结点的右指针域指向 结点。表尾、表头

41．在以HL为表头指针的带表头附加结点的单链表和循环单链表中，链表为空的条件分别为 和 。HL->next = = NULL 、HL->next = = HL

42．队列的插入操作在 进行，删除操作在 进行。队尾、队首 43．栈又称为 表，队列又称为 表。后进先出(LIFO)、先进先出(FIFO)

44．向一个顺序栈插入一个元素时，首先使 后移一个位置，然后把待插入元素 到这个位置上。栈顶指针、存储

45．从一个栈中删除元素时，首先取出 ，然后再前移一位 。栈顶元素、栈顶指针

46．在一个循环顺序队列Q中，判断队空的条件为 ，判断队满的条件为 。front = = rear 、(rear+1)%QueueMaxSize = = front

47．在一个顺序栈中，若栈顶指针等于 ，则为空栈；若栈顶指针等于 ，则为满栈。–1 、StackMaxSize-1

48．在一个链栈中，若栈顶指针等于NULL，则为 ；在一个链队中，若队首指针与队尾指针的值相同，则表示该队列为 或该队列为 。栈

9

空、空队、队列只有一个元素

49．在下面的数组a中链接存储着一个线性表，表头指针为a[o].next，则该线性表为_________________________________________________。

a 0 1 2 3 4 5 6 7 8 dat

60 56 42 38 74 25 a

4 3 7 6 2 0 1 next

（38，56，25，60，42，74）；

50．在以HL为表头指针的带表头附加结点的单链表和循环单链表中，判断链表为空的条件分别为________________和____________________。HL→next =NULL； HL=HL→next； 51．用具有n个元素的一维数组存储一个循环队列，则其队首指针总是指向队首元素的___________，该循环队列的最大长度为__________。前一个位置； n-1； 52．当堆栈采用顺序存储结构时，栈顶元素的值可用———————表示；当堆栈采用链接存储结构时，栈顶元素的值可用_______________表示。S.stack [S.top]; HS→data;

53．设单链表的结点结构为(data,next)，next为指针域，已知指针px指向单链表中data为x的结点，指针py指向data为y的新结点 , 若将结点y插入结点x之后，则需要执行以下语句:_______； ______;【华中理工大学 2000 一.4（2分）】py->next=px->next; px->next=py

54．在一个长度为n的顺序表中第i个元素（1<=i<=n）之前插入一个元素时，需向后移动________个元素。【北京工商大学 2001 二.4（4分）】n-i+1 55．在单链表中设置头结点的作用是________。【哈尔滨工业大学 2000 二.1（1分）】有头结点后，插入元素和删除元素的算法统一了，不再需要判断是否在第一个元素之前插入和删除第一个元素。另外，不论链表是否为空，链表指针不变。

56．对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为________,在给定值为x的结点后插入一个新结点的时间复杂度为________。【哈尔滨工业大学 2001 一.1（2分）】 O(1)，O(n)

57．在双向循环链表中,向p所指的结点之后插入指针f所指的结点，其操作是_______、_______、_______、________。【中国矿业大学 2000 一.1（3分）】f->next=p->next; f->prior=p; p->next->prior=f; p->next=f;

58．顺序存储结构是通过________表示元素之间的关系的;链式存储结构是通过________表示元素之间的关系的。【北京理工大学 2001 七.2 （2分）】物理上相邻 指针

59．在单链表L中，指针p所指结点有后继结点的条件是：________ 【合肥工业大学 2001 三.3 （2分）】p->next!=null

60. 单链表与多重链表的区别是 。链域数目不同

三、判断题

10

1．（ ）线性表的顺序存储结构比链式存储结构更好。F 2．( )线性表就是顺序存储的表。× 3．（ ）线性表中的所有元素都有一个前驱元素和后继元素。F 4．（ ）非空的双向循环链表中任何结点的前驱指针均不为空。T 5．（ ）不论线性表采用顺序存储结构还是链式存储结构，删除值为X的结点的时间复杂度均为O(n)。T

6．( )对链表进行插入和删除操作时不必移动链表中结点。T 7．( )线性表只能用顺序存储结构实现。× 8．( )如果某数据结构的每一个元素都最多只有一个直接前驱和一个直接后继，则该数据结构必为线性表。×

9．( )进栈操作时，必须判断栈是否已满。× 10．( )进栈、出栈操作的时间复杂度是O(n)。×

11．( )采用链式结构存储线性表时，其地址可以是不连续的。√ 12．( )线性表中的每个元素都有一个前驱元素和后继元素。× 13．( )采用顺序结构存储线性表时，其地址可以是不连续的。× 14．（ ）如果某数据结构的每一个元素都最多只有一个直接前驱和一个直接后继，则该数据结构必为线性表。√ 15．（ ）线性表的唯一存储形式就是链表。× 16．（ ）线性表不能采用链式存储。× 17．（ ）在单链表中插入结点主要通过移动元素实现。× 18．( )所谓静态链表就是一直不发生变化的链表。× 19．( )集合与线性表的区别在于是否按关键字排序。× 20．（ ）用头部插入结点的方法建立单链表时，插入元素的顺序和链表中的元素顺序相同。× 21．（ ）线性表中的每个元素都有一个前驱元素和后继元素。 × 22．（ ）线性表中每个元素都有一个直接前驱和一个直接后继。× 23．（ ）线性表采用顺序存储表示时，必须占用一片连续的存储单元。√ 24．( )数据的逻辑结构说明数据元素之间的顺序关系，它依赖于计算机的存储结构。×

25．( )数据的逻辑结构是指数据的各数据项之间的逻辑关系。× 26．( )算法的优劣与算法描述语言无关，但与所用计算机有关。× 27．( )健壮的算法不会因非法的输入数据而出现莫名其妙的状态。√ 28．（ ）算法的运行时间涉及加、减、乘、除、转移、存、取、等基本运算。要想准确地计算总运算时间是不可行的。×

29．( )数据的物理结构是指数据在计算机内的实际存储形式。√ 30．( )数据结构的抽象操作的定义与具体实现有关。× 31．( )数据结构的基本操作的设置的最重要的准则是，实现应用程序与存储结构的独立。√ 32．（ ）算法独立于具体的程序设计语言，与具体的计算机无关。√ 33．（ ）Huffman树、平衡二叉树都是数据的逻辑结构。√ 34．（ ）抽象数据类型与计算机内部表示和实现无关。√ 35．（ ）在一个设有头指针和尾指针的单链表中,执行删除该单链表中最后一个元素的操作与链表的长度无关。×

36．( )顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。×

11

37．（ ）顺序存储方式只能用于存储线性结构。× 38．( ) 线性表只能用顺序方式存放。X

39．( ) 在带表头结点的双循环链表中，每个结点的前趋和后继指针均不为空。√

40．（ ）顺序存储的线性表的插入和删除操作不需要付出很大的代价，因为平均每次操作只有近一半的元素需要移动。×

41．( )顺序存储方式的优点是存储密度大，且插入、删除运算效率高。× 42．（ ）在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上不一定相邻。×

43. （ ）在单链表中，要取得某元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。× 四、简答题

1．线性结构与非线性结构的差别

前驱与后继之间通常为一对多或多对多的关系。 2．比较顺序表与单链表的优缺点。 顺序表优点：随机查找，存储密度大

顺序表缺点：插入、删除不便，静态分配，表长固定 单链表优点：插入、删除方便，动态分配，表长灵活

单链表缺点：查找不便，存储密度小 3．简要说明算法与程序的区别。

算法是解决特定问题的操作序列，可以用多种方式描述。程序是算法在计算机中的实现，与具体的计算机语言有关。

4．说明以下三个概念的关系：头指针，头结点，首元素结点。 头指针指向头结点，头结点的后继域指向首元素结点。

5．设有编码为A，B，C，D的4列火车，依次进入一个栈式结构的站台，试写出这4列火车开出站台的所有可能的顺序。

根据栈的数学性质，n个元素的出栈序列数目恰好符合卡塔南数列。 Cn=C2nn/(n+1)=1/n+1*(2n)!/n!(2n-n)! 这里:

1/n+1*(2n)!/n!(2n-n)!=1/5*8!/(4!*4!)=14 ABCD ABDC ACBD ACDB ADCB BACD BADC BCAD BCDA BDCA CBAD CBDA CDBA DCBA 分析解答：

6．写出在双向链表中，在指针p所指结点前插入一个结点*S的语句序列。 答： 答：（1）S->prior=P->prior; （2）P->prior->next=S; （3）S->next=P; （4）P->prior=S;

7．试叙述一维数组与有序表的异同。

一维数组属于特殊的顺序表，和有序表的差别主要在于有序表中的元素按值排列（非递增或非递减），而一维数组中的元素没有按元素值排列顺序的要求。 8．试比较顺序存储和链式存储的优缺点。

顺序存储查找效率高，插入和删除效率低；链式存储插入和删除效率高，查找效

12

率低。

9．写出线性表(26,45,12,20,30)采用快速排序算法排序后，第一趟排序过程及结果。

20 12 26 45 30。

10．试说明单链表采用头结点的优点。 解决单链表的“第一个结点问题”，使头指针变量不为空。 11. 画出带头结点的单链表、单循环链表和双向循环链表的示意图，并归纳三者的不同之处。

H a1 ??

an H L A B 单链表：只有从头结点出发，才能访问到所有结点。

单循环链表：从任意一结点出发，均可访问到其他结点。

双向循环链表：既可以方便的找到前趋结点，又可方便的找到后继结点。

12．有五个数依次进栈：1，2，3，4，5。在各种出栈的序列中，以3，4先出的序列有哪几个。（３在４之前出栈）。 【解答】34215 ，34251， 34521 13．铁路进行列车调度时，常把站台设计成栈式结构，若进站的六辆列车顺序为：1，2，3，4，5，6， 那么是否能够得到435612， 325641， 154623和135426的出站序列，如果不能，说明为什么不能； 如果能， 说明如何得到(即写出\进栈\或\出栈\的序列)。

【解答】输入序列为123456，不能得出435612和154623。不能得到435612的理由是，输出序列最后两元素是12，因为前面4个元素（4356）得到后，栈中元素剩12，且2在栈顶，不可能让栈底元素1在栈顶元素2之前出栈。不能得到154623的理由类似，当栈中元素只剩23，且3在栈顶，2不可能先于3出栈。 得到325641的过程如下：1 2 3顺序入栈，32出栈，得到部分输出序列32；然后45入栈，5出栈，部分输出序列变为325；接着6入栈并退栈，部分输出序列变为3256；最后41退栈，得最终结果325641。 得到135426的过程如下：1入栈并出栈，得到部分输出序列1；然后2和3入栈，3出栈，部分输出序列变为13；接着4和5入栈，5，4和2依次出栈，部分输出序列变为13542；最后6入栈并退栈，得最终结果135426。

14．若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？ 【解答】2和 4

15．设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过

13

栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e3，e5，e4，e6，e2，e1，则栈S的容量至少应该是多少？ 【解答】 4

16．循环队列的优点是什么，如何判断“空”和“满”。 【解答】循环队列解决了常规用0--m-1的数组表示队列时出现的“假溢出”（即队列未满但不能入队）。在循环队列中，我们仍用队头指针等于队尾指针表示队空，而用牺牲一个单元的办法表示队满：即当队尾指针加1（求模）等于队头指针时，表示队列满。也有通过设标记以及用一个队头或队尾指针加上队列中元素个数来区分队列的“空”和“满”的。

17．设长度为n的链队列用单循环链表表示，若只设头指针，则入队和出队的时间如何？若只设尾指针呢？

【解答】若只设头指针，则入队的时间为O(n），出队的时间为O(1)。若只设尾指针，则入队和出队的时间均为O(1)。 18．试将下列递推过程改写为递归过程。 void ditui(int n) {i=n;

while(i>0) printf(i--); }

【解答】void digui(int n) {if(n>0){printf(n); digui(n-1); } }

19．写出下列中缀表达式的后缀表达式：

(1)A*B*C (2)(A+B)*C-D (3)A*B+C/(D-E) (4)(A+B)*D+E/(F+A*D)+C 解答】 (1)ABC** (2)AB+C*D- (3)AB*CDE-/+

(4)AB+D*EFAD*+/+C+

20．线性表的顺序存储结构具有三个弱点：第一，在作插入或删除操作时，需要移动大量元素；第二，由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用；第三，表的容量难以扩充。试问，线性表的链式存储结构是否一定能够克服上述三个弱点？请简述之。【北京师范大学2003二.4(6分)】 链式存储结构一般说克服了顺序存储结构的三个弱点。首先，插入、删除不需移动元素，只修改指针，时间复杂度为O(1)；其次，不需要预先分配空间，可根据需要动态申请空间；其三，表容量只受可用内存空间的限制。其缺点是因为指针增加了空间开销，当空间不允许时，就不能克服顺序存储结构的缺点。

21．说明在线性表的链式存储结构中，头指针与头结点之间的根本区别；头结点与首元结点的关系。 【厦门大学 2000 五.1 （14%/3分）】 在线性表的链式存储结构中，头指针指链表的指针，若链表有头结点则是链表的头结点的指针，头指针具有标识作用，故常用头指针冠以链表的名字。头结点是为了操作的统一、方便而设立的，放在第一元素结点之前，其数据域一般无意义（当然有些情况下也可存放链表的长度、用做监视哨等等）。有头结点后，对在

14

第一元素结点前插入结点和删除第一结点，其操作与对其它结点的操作统一了。而且无论链表是否为空，头指针均不为空。首元结点也就是第一元素结点，它是头结点后边的第一个结点。

22. 如何通过改链的方法，把一个单向链表变成一个与原来链接方向相反的单向链表？

【中国人民大学 2001 二.4 （2分）】 本题是链表的逆置问题。设该链表带头结点，将头结点摘下，并将其指针域置空。然后从第一元素结点开始，直到最后一个结点为止，依次前插入头结点的后面，则实现了链表的逆置。

23．已知L是一个数据类型linkedlist的单循环链表，pa和pb是指向L中结点的指针。简述下列程序段的功能。【山东科技大学 2001 一.2 （5分）】 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;

mp是一个过程，其内嵌套有过程subp。

subp(s,q)的作用是构造从s到q的循环链表。

subp(pa,pb)调用结果是将pa到pb的前驱构造为循环链表。

subp(pb,pa)调用结果是将pb到pa的前驱（指在L链表中，并非刚构造的pa循环链表中）构造为循环链表。 总之，两次调用将L循环链表分解为两个。第一个循环链表包含从pa到pb的前驱,L中除刚构造的pa到pb前驱外的结点形成第二个循环链表。

24．阅读下面的算法，说明算法实现的功能 【东华大学2004二.1(10分)】 a) node *link(node *head1, *head2) {node *p, *q; p=head1;

while (p->next!=head1) p=p->next; q=head2;

while (q->next!=head2) q=q->next; p->next=head2; q->next=head1; return(head1); }

本算法功能是将两个无头结点的循环链表合并为一个循环链表。head1最后一个结点的链域指向head2， head2最后一个结点的链域指向head1，head1为结果循环链表的指针。 五、应用题

15

leavequeue (QUEUE *Q, int *e) {

if( ) { return 0; }

*e = Q->data[Q->front];

Q-front = ; return 1;

}1．Q->front == Q->rear;(Q->front+1)0;

13. 已知一个单链表的表头指针为h，每个结点含元素值data和下一个结点的地址next。链表一共有5个结点，其元素值分别为100,200,300,400,500，经过下列语句后，输出什么结果？。（3分）

for (p=h;p->data<300;p=p->next) { p->next = p->next->next;

}

printf(“%d”,p->data);

3．300

14. 指出下面程序段的功能是什么？ (1) void demo1(SeqStack S) {int i，arr[64]，n=0;

while(!StackEmpty(S)) arr[n++]=Pop(S); for(i=0;i

【解答】程序段的功能是实现了栈中元素的逆置。

(2) void demo2(SeqStack S，int m)∥设栈中元素类型为int型 {int x;SeqStack T; StackInit(T);

while(!StackEmpty(S))

if((x=Pop(S))!=m) Push(T，x);

while(!(StackEmpty(T)) {x=Pop(T); Push(S，x);} }

【解答】程序段的功能是删除了栈中值为m的元素。

(3) void demo3(SeQueue Q，int m)∥设队列中元素类型为int型 {int x;SeqStack S; StackInit(S);

while(!QueueEmpty(Q)){x=QueueOut(Q); Push(S，x);} while(!StackEmpty(S)){x=Pop(s); QueueIn(Q，x);} }

【解答】程序段的功能是实现了队列中元素的逆置。

15. 假定从键盘上输入一批整数，依次为：78 63 45 30 91 34 –1，请写出输出结果。

# include < iostream.h>

21

# include < stdlib.h >

consst int stackmaxsize = 30; typedef int elemtype; struct stack {

elemtype stack [stackmaxsize]; int top; };

# include “stack.h” Void main ( ) {

stack a;

initstack(a); int x; cin >>x;

while (x! = -1) { push (a, x ); cin >>x; }

while (!stackempty (a)) cout <

}

该算法的输出结果为：

__________________________________________________________. 该算法的输入结果是：34 91 30 45 63 78

16. 设有一个带表头结点的双向循环链表L，每个结点有4个数据成员：指向前驱结点的指针prior、指向后继结点的指针next、存放数据的成员data和访问频度freq。所有结点的freq初始时都为0。每当在链表上进行一次 L.Locate (x)操作时，令元素值x的结点的访问频度freq加1，并将该结点前移，链接到现它的访问频度相等的结点后面，使得链表中所有结点保持按访问频度递减的顺序排列，以使频繁访问的结点总是靠近表头。

函数中有些语句缺失，请将它们补上。（每一个空2分，共10分） template< class Type> void DblList ：： Locate ( Type & x) {

DblNode*p=first->next ;

While (p ! = frist && ① )p = ->next;

If (p ! =first){ //链表中存在x ② ； //该结点的访问频度加l

DblNode*current=p; //从链表中摘下这个结点 Current ?prior?next = current ?next; Current ?next?prior = current ?prior;

P=current?prior; //寻找重新插入的

位置

While (p !=first && ③ )

22

P=p ?prior ;

Current ?next= ④ ; //插入在p之后 Current ?prior=p ;

P ?next ?prior=current ; P ?next= ⑤ ; }

else cout<<”Sorry.Not find! \\n”; //没找到

}

缺失的内容为： ① ② ③ ④ ⑤

①p?data!=x ②p?freq++

③current?freq>p?freq ④p?next ⑤current

17. 已给如下关于单链表的类型说明： TYPE

list=^node ; node=RECORD

data: integer; next: list; END;

以下程序采用链表合并的方法，将两个已排序的单链表合并成一个链表而不改变其排序性（升序），这里两链表的头指针分别为p和q. PROCEDURE mergelink(VAR p,q:list): VAR h,r: list; BEGIN

（1）______

h^.next:= NIL; r:=h;

WHILE((p<>NIL) AND (q<>NIL)) DO IF (p^.data<=q^.data)

THEN BEGIN （2）___； r:=p; p:=p^.next； END ELSE BEGIN （3）____； r:=q; q:=q^.next; END; IF (p=NIL) THEN r^.next:=q; （4）__；

p:=h^.next; dispose(h);

END;【厦门大学 2000 三.2 （8分）】

(1)new(h);∥生成头结点，以便于操作。 (2)r^.next:=p;

(3) r^.next:=q; (4) IF q=NIL THEN r^.next:=p; 18. 已知双链表中结点的类型定义为： TYPE dpointer=^list;

23

list=RECORD

data:integer; left,right:dpointer; END;

如下过程将在双链表第i个结点（i>=0）之后插入一个元素为x的结点，请在答案栏给出题目中______处应填入的语句或表达式，使之可以实现上述功能。 PROCEDURE insert(VAR head:dpointer;i,x:integer); VAR s,p:dpointer; j: integer; BEGIN

new(s); s^.data:=x;

IF(i=0)THEN BEGIN s^.right:=head; (1)___ head:=s END{如果i=0,则将s结点插入到表头后返回}

ELSE BEGIN p:=head; (2)_______；{在双链表中查找第i个结点,由p所指向} WHILE ((p<>NIL) AND (jNIL THEN

IF （p^.right=NIL）

THEN BEGIN p^.right:=s; s^.right:=NIL; (4) __END

ELSE BEGIN s^.right:=p^.right; (5) _;p^.right:=s; (6) END ELSE writeln(‘can not find node!’) END END;

【厦门大学 2002 二 （12分）】

(1)head^.left:=s ∥head的前驱指针指向插入结点 (2)j:=1;

(3)p:=p^.right ∥工作指针后移 (4)s^.left:=p

(5)p^.right^.left:=s; ∥p后继的前驱是s (6)s^.left:=p;

19. 阅读以下算法，填充空格，使其成为完整的算法。其功能是在一个非递减的顺序存储线性表中，删除所有值相等的多余元素。 CONST maxlen=30 TYPE sqlisttp=RECORD

elem:ARRAY[1..maxlen] OF integer; last:0..maxlen END;

PROC exam21(VAR L:sqlisttp); j:=1; i:=2;

WHILE (1)______ DO

[ IF L.elem[i]<>L.elem[j] THEN [ (2)_______; (3)______]; i:=i+1 ]

(4) ________;

ENDP;【同济大学 2000 二.1 (10分)】 (1)i<=L.last ∥L.last 为元素个数 (2)j:=j+1 ∥有值不相等的元素

24

(3)L.elem[j]:=L.elem[i] ∥元素前移 (4)L.last:=j ∥元素个数

20. 对于给定的线性链表head , 下面的程序过程实现了按结点值非降次序输出链表中的所有结点，在每次输出一个结点时，就把刚输出的结点从链表中删去。请在划线处填上适当的内容，使之成为一个完整的程序过程，每个空框只填一个语句。

TYPE nodeptr =^ nodetype； nodetype = RECORD

data : integer；link : nodeptr END;

VAR head : nodeptr；

PROCEDURE sort_output_delete (head : nodeptr); VAR p,q,r,s: nodeptr;

BEGIN WHILE head <> NIL DO

BEGIN p:= NIL ；q:= head；r:= q ；s:=q^.link ； WHILE s <> NIL DO

BEGIN IF s^.data < q^.data THEN BEGIN (1)__; (2)___ END ； r:= s ； (3)___ END；

write(q^.data : 5) ；

IF p=NIL THEN (4)___ ELSE (5)____ ； dispose (q) ； END； writeln

END；【复旦大学 1996 七 （20分） 1995 一（12分）与本题相似】 (1)p:=r;∥r指向工作指针s的前驱，p指向最小值的前驱。 (2)q:=s;∥q指向最小值结点，s是工作指针 (3)s:=s^.link∥工作指针后移

(4)head:=head^.next;∥第一个结点值最小；

(5)p^link:=q^.link;∥跨过被删结点（即删除一结点） 21. 循环链表a和b的结点值为字母，其中a表非递减有序，下面的程序欲构造一个递增有序的循环链表c，其中结点的值为同时在a，b两链表中出现的字母，且c中字母不重复，请补上程序中空缺的部分，并估计算法的时间复杂度。（设a，b的结点数分别为m，n） TYPE

link=^node; node=RECORD

key:char; next:link END;

PROC jj(a,b:link; VAR c:link); VAR p,q,r,s:link; BEGIN

new(c);c^.next:=c; q:=a; p:=a^.next; WHILE p<>a DO

25

for(q=head,p=head->next; p!=0; q=p,p=p->next)if(q->data>p->data) return(0); return(1); 8．编写向类型为List的线性表L中第i个元素位置插入一个元素的算法，假定不需要对i的值进行有效性检查，同时不需要检查存储空间是否用完。

Void Insert(List& L，int i, ElemType x) 评分标准：请根据编程情况酌情给分。

vioid Insert(List& L,int i,ElemType x) {

for(int j=L.size-1;j>=i-1;j--) L.list[j+1]=L.list[j]; L.list[i-1]=x; L.size++; }

9．编写算法，求不带头结点的单链表的表表长。（7分） 已知单链表结点数据结构如下：

typedef struct node

{

int data;

struct node *next;

} LNode, *LinkList;

int length_LinkList(LinkList L) {

LNode *p=L;

int j = 0

while(p->next != NULL) { p = p->next; ++j; }

return j; }

10．编写算法，删除顺序表第i个元素。（8分） 已知顺序表的数据结构如下： typedef struct {

int data[100]; int last;

} SeqList;

int delete_SeqList(SeqList *L,int i) {

31

int j;

if (i <1 || i>L->last+1) {

printf(“不存在第i个元素”); return 0;

}

for (j=i; j<=L->L->last; ++j) { l->data[j-1] = L->data[j]; }

L->last--; return 1; }

11．编写算法查找不带头结点的单链表中的第i个结点，如找到返回1，否则返回0。（7分）

已知单链表结点数据结构如下：

typedef struct node

{

int data;

struct node *next;

} LNode, *LinkList;

LNode *Get_LinkList(inkList L, int i) {

LNode *p = L;

int j = 0;

while(p->next != NULL && j < i) { p = p->next; ++j; }

if (j == i) { return p; }

else {

return NULL; } }

12．编写算法，将任意十进制数转换成其他进制，要求写出完整代码，可采用顺序栈或链栈实现。（12分） #define Maxsize 100 typedef struct {

int data[Maxsize]; int top;

32

}SeqStack;

SeqStack *Init_SeqStack() {

SeqStack *s;

s=(SeqStack *)malloc(sizeof(SeqStack)); s->top=-1; return s; }

/*入栈*/

int Push_Seqstack(SeqStack *s,int x) {

if(s->top==Maxsize-1)return 0; else{

s->top++;

s->data[s->top]=x; return 1; } }

/*出栈*/

int Pop_SeqStack(SeqStack *s,int *x) {

if(Empty_SeqStack(s)) return 0; else{

*x=s->data[s->top]; s->top--; return 1; } }

/*判空栈*/

int Empty_SeqStack(SeqStack *s) {

if(s->top==-1) return 1; else return 0; }

void conversion(int N,int r) {

SeqStack *p; int y;

p=Init_SeqStack(); while(N) {

if(Push_Seqstack(p,N%r)==1) {N=N/r; } else

33

break; }

while(!Empty_SeqStack(p)) {

Pop_SeqStack(p,&y); printf(\ } }

void main() {

int M,t;

printf(\ scanf(\

printf(\ scanf(\ conversion(M,t); getch(); }

13．编写一算法完成瑟夫生死者游戏。（8分）

瑟夫生死者游戏的描述：N个旅客同乘一条船，因为严重超载，加上风浪大，危险万分；因此船长告诉乘客，只有将全船一半的旅客投入海中，其余人才能幸免遇难。无奈，大家只得同意这种办法，并拟定N个人围成一圈，由第一个人数起，依次报数，数到第r人，便把他投入海中，然后再从他的下一个人数起，数到第r人，再将他仍进海里，如此循环的进行，直到剩下N/2个乘客为止。问哪些位置是将被扔下大海的位置。

typedef struct node {

int data;

struct node *next; }ListNode,*LinkList;

LinkList CreateList(int n);

void DeleteNode(LinkList L,int n,int k); void PrintList(LinkList L); main() {

int n,k; LinkList H;

printf(\请输入总人数：\ scanf(\

printf(\请输入报数上限:\ scanf(\ H=CreateList(n);

34

DeleteNode(H,n,k); PrintList(H); getch(); }

LinkList CreateList(int n) {

int i;

LinkList L=NULL; ListNode *s,*R=NULL; for(i=1;i<=n;i++) {

s=(ListNode *)malloc(sizeof(ListNode)); s->data=i;

if(L==NULL) L=s; else R->next=s; R=s; }

if(L!=NULL) R->next=L; return L; }

void DeleteNode(LinkList L,int n,int k) {

int i,j=0;

ListNode *q,*p=L;

printf(\不幸投入大海的有：\ for(i=1;i<=n/2;i++) {

for(j=1;jnext; q=p->next;

p->next=q->next;

printf(\ if(i==0) printf(\ free(q); p=p->next; }

printf(\ L=p; }

void PrintList(LinkList L) {

35

ListNode *p=L; int i=1;

printf(\有幸逃生的有：\ while(p->next!=L) {

printf(\ if(i==0) printf(\ p=p->next; }

printf(\}

14．有顺序表A和B，其元素均按从小到大的升序排列，编写一个算法将它们合并成一个顺序表C，要求C的元素也是从小到大升序排列。要求写出完整代码。（12分） 1．

#define MAXSIZE 20 typedef int datatype; typedef struct {

datatype data[MAXSIZE]; int last; }SeqList;

SeqList *init_SeqList(); void input(SeqList *L); void output(SeqList *L);

void merge(SeqList *A,SeqList *B,SeqList *C); main() {

SeqList *A,*B,*C; datatype x; int i,n;

A=init_SeqList(); B=init_SeqList(); C=init_SeqList(); input(A); input(B); merge(A,B,C); output(C); getch(); }

SeqList *init_SeqList() {

36

SeqList *L;

L=(SeqList *)malloc(sizeof(SeqList)); L->last=-1; return L; }

void merge(SeqList *A,SeqList *B,SeqList *C) {

int i,j,k; i=0;j=0;k=0;

while(i<=A->last&&j<=B->last) if(A->data[i]data[j])

C->data[k++]=A->data[i++]; else

C->data[k++]=B->data[j++]; while(i<=A->last)

C->data[k++]=A->data[i++]; while(j<=B->last)

C->data[k++]=A->data[j++]; C->last=k-1; }

void input(SeqList *L) {

int n;

printf(\ for(n=0;;n++) {

scanf(\ if(L->data[n]==0) break; L->last=n; } }

void output(SeqList *L) {

int n;

for(n=0;n<=L->last;n++)

printf(\}

15．对于List类型的线性表，编写出下列每个算法。

(1) 从线性表中删除具有最小值的元素并由函数返回，空出的位置由最后一个元素填补，若线性表为空则显示出错信息并退出运行。 (2) 从线性表中删除第i个元素并由函数返回。 (3) 向线性表中第i个元素位置插入一个元素。

37

(4) 从线性表中删除具有给定值x的所有元素。 (1) ElemType DMValue( List & L ) {

if ( ListEmpty(L) ) { // 空线性表

cerr <<”List is Empty!”<

ElemType x; // x存放最小元素 x = L.list[0];

int k = 0; // k存放最小元素的下标 for ( int i = 1; i

if ( L.list[i] < x ) { x = L.list[i] ; k = i; }

L.list[k] = L.list[L.size-1]; // 最后一个元素填补最

小元素位置

L.size--; // 线性表长度减1 return x; // 返回最小元素

}

(2)ElemType Delete( List & L, int i ) {

if ( i<1 || i>L.size ) { // 判断i的合法性

cerr <<”Index is out range!”<

}

ElemType x = L.list[i-1]; // 保存被删除元素

for ( int j = i-1; j

L.size--; // 长度减1 return x; // 返回被删元素 }

(3)void Insert( List & L, int i, ElemType x ) {

if ( i<1 || i>L.size+1 ) { // 判断i的合法性

cerr <<”Index is out range!”<

}

if ( L.size == MaxSize ) { // 判断线性表满

cerr <<”List overflow!”<

}

for ( int j = L.size-1 ; j>=i-1 ; j-- ) // 元素后移，产生插入位置

L.list[j+1] = L.list[j];

L.list[i-1] = x; // 元素插入 L.size++; // 长度加1 }

(4) void Delete( List & L, ElemType x ) { int i = 0;

38

while ( i

if ( L.list[i] == x ) { // 删除x元素

for ( int j = i+1; j

}

else i++; // 寻找下一个x元素的位置 }

16．对于结点类型为LNode的单链表，编写出下列每个算法。

(1) 删除单链表中的第i个结点。

(2) 在有序单链表中插入一个元素x的结点。 (3) 从单链表中查找出所有元素的最大值，该值由函数返回，若单链表为空，则显示出错信息并停止运行。

(4)统计出单链表中结点的值等于给定值x的结点数。

(1)void Delete( LNode * & HL, int i ) {

if ( i<1 || HL==NULL ) { // 判断i的合法性或空链表

cerr <<”index is out range!”<

}

LNode * ap , * cp;

ap = NULL ; cp = HL ; // cp指向当前结点，ap指向其前驱结点

int j = 1;

while ( cp != NULL ) // 查找第i个结点 if ( j == i ) // 找到第i个结点

break; // cp指向的结点即为第i个结点

else { // 继续向后寻找

ap = cp;

cp = cp->next; j++;

}

if ( cp == NULL ) { // 没有找到第i个结点

cerr <<”Index is out range!”<

}

if ( ap == NULL ) // 删除第1个结点（即i=1） HL = HL->nextl else

ap->next = cp->next; // 删除第i个结点

delete cp; // 释放被删除结点的空间 }

(2)void Insert( LNode * & HL, const ElemType & x ) { LNode * newptr = new LNode; // 申请一个新结点

39

if ( newptr == NULL ) { // 分配失败

cerr <<”Memory allocation failare!”<

}

newptr->data = x;

if ( HL == NULL || xdata ) { // 空表 或 x小于表头结点，

newptr->next = HL; // 作为新表头结点插入 HL = newptr; return;

}

// 查找插入位置

LNode * cp = HL->next; // 用cp指向当前结点（即待查结点）

LNode * ap = HL; // 用ap作为指向当前结点的前驱结点指针

while ( cp != NULL )

if ( xdata) break; // 找到插入位置

else { ap = cp; cp = cp->next; } // 继续查找插入位置

newptr->next = cp; ap->next = newptr; // 插入新结点 }

(3)ElemType MaxValue( LNode * HL ) {

if ( HL == NULL ) { // 空表

cerr <<”Linked list is empty!”<

ElemType max = HL->data; LNode * p = HL->next;

while ( p != NULL ) { // 寻找最大值 if ( max < p->data ) max = p->data; p = p->next; }

return max;

}

(4)int Count( LNode * HL , ElemType x ) { int n = 0;

LNode * p = HL;

while ( p != NULL ) {

if ( p->data == x ) n++; p = p->next; }

return n; }

40

本文来源：https://www.bwwdw.com/article/8d9g.html