第2章 线性表习题及参考答案

1、第二章 线性表习题一 判断题1线性表的逻辑顺序与存储顺序总是一致的。2顺序存储的线性表可以按序号随机存取。3顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。 4线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。5在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。6在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。7线性表的链式存储结构优于顺序存储结构。8在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。9线性表的链式存储结构是用一组任意的存储单元

2、来存储线性表中数据元素的。10在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。二 单选题 (请从下列A，B，C，D选项中选择一项)1线性表是( ) 。(A) 一个有限序列，可以为空； (B) 一个有限序列，不能为空； (C) 一个无限序列，可以为空； (D) 一个无序序列，不能为空。 2对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。插入一个元素时平均要移动表中的（ ）个元素。 (A) n/2 (B) n+1/2 (C) n -1/2 (D) n 3线性表采用链式存储时，其地址( ) 。(A) 必须是连续的； (B) 部分地址必

3、须是连续的； (C) 一定是不连续的； (D) 连续与否均可以。 4用链表表示线性表的优点是 （ ）。(A)便于随机存取 (B)花费的存储空间较顺序存储少(C)便于插入和删除 (D)数据元素的物理顺序与逻辑顺序相同5 某链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用( )存储方式最节省运算时间。(A)单链表 (B)双链表 (C)单循环链表 (D)带头结点的双循环链表6 循环链表的主要优点是( ) 。(A)不再需要头指针了(B)已知某个结点的位置后，能够容易找到他的直接前趋(C)在进行插入、删除运算时，能更好的保证链表不断开(D)从表中的任意结点出发都能扫描到整个链

4、表7 下面关于线性表的叙述错误的是( )。(A) 线性表采用顺序存储，必须占用一片地址连续的单元；(B) 线性表采用顺序存储，便于进行插入和删除操作；(C) 线性表采用链式存储，不必占用一片地址连续的单元；(D) 线性表采用链式存储，不便于进行插入和删除操作；8 单链表中，增加一个头结点的目的是为了（）。(A) 使单链表至少有一个结点 (B)标识表结点中首结点的位置（C）方便运算的实现 (D) 说明单链表是线性表的链式存储9 若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。(A) 单链表 (B) 仅有头指针的单循环链表 (C) 双链

5、表 (D) 仅有尾指针的单循环链表10 若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（ ）存储方式最节省运算时间（ ）。(A) 单链表 (B) 顺序表 (C) 双链表 (D) 单循环链表三 填空题1带头结点的单链表H为空的条件是_。1 非空单循环链表L中*p是尾结点的条件是_。3在一个单链表中p所指结点之后插入一个由指针s所指结点，应执行s->next=_;和p->next=_的操作。4在一个单链表中p所指结点之前插入一个由指针s所指结点，可执行以下操作：s->next=_;p->next=s;t=p->data;p->data=_

6、;s->data=_;5在顺序表中做插入操作时首先检查_。四 算法设计题1 设线性表存放在向量Aarrsize的前elenum个分量中，且递增有序。试写一算法，将x 插入到线性表的适当位置上，以保持线性表的有序性。并且分析算法的时间复杂度。2 已知一顺序表A，其元素值非递减有序排列，编写一个函数删除顺序表中多余的值相同的元素。3 线性表用顺序存储，设计一个算法，用尽可能少的辅助存储空间将顺序表中前m个元素和后n个元素进行整体互换。即将线性表（a1, a2, , am, b1, b2, , bn） 改变为：（b1, b2, , bn , a1, a2, , am）。4 已知带头结点的单链表

7、L中的结点是按整数值递增排列的，试写一算法，将值为x 的结点插入到表L中，使得L仍然有序。并且分析算法的时间复杂度。5 假设长度大于1的循环单链表中，既无头结点也无头指针，p为指向该链表中某一结点的指针，编写一个函数删除该结点的前趋结点。五 上机实习题目1 Josephu 问题Josephu 问题为：设编号为1，2， n的n个人围坐一圈，约定编号为k（1<=k<=n）的人从1开始报数，数到m 的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。 提示：用一个不带头结点的循环链表来处理Josephu 问题：先构成一个

8、有n个结点的单循环链表，然后由k结点起从1开始计数，计到m时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从1开始计数，直到最后一个结点从链表中删除算法结束。2 一元多项式的相加 提示：（1） 一元多项式的表示问题：对于任意一元多项式：Pn(x)= P0+ P1X1+ P2X2+ + PiXi+ + PnXn可以抽象为一个由“系数-指数”对构成的线性表，且线性表中各元素的指数项是递增的： P=( ( P0,0), ( P1,1), ( P2,2), , ( Pn,n) )(2 ) 用一个单链表表示上述线性表，结点结构为：coef exp next typedef sturct nod

9、e float coef; /*系数域*/ int exp; /*指数域*/ struct node *next; /*指针域*/ Ploy Node; 约瑟夫环问题 约瑟夫环问题：设编号为1，2，3，n的n(n>0)个人按顺时针方向围坐一圈，每个人持有一个正整数密码。开始时任选一个正整数做为报数上限m，从第一个人开始顺时针方向自1起顺序报数，报到m是停止报数，报m的人出列，将他的密码作为新的m值，从他的下一个人开始重新从1报数。如此下去，直到所有人全部出列为止。令n最大值取30。要求设计一个程序模拟此过程，求出出列编号序列。源程序代码：（在Tubro C 2.0测试通过）#includ

10、e <stdlib.h>#include <alloc.h>struct node int number; /* 人的序号 */ int cipher; /* 密码 */ struct node *next; /* 指向下一个节点的指针 */;struct node *CreatList(int num) /* 建立循环链表 */ int i; struct node *ptr1,*head; if(ptr1=(struct node *)malloc(sizeof(struct node)=NULL) perror("malloc"); retur

11、n ptr1; head=ptr1; ptr1->next=head; for(i=1;i<num;i+) if(ptr1->next=(struct node *)malloc(sizeof(struct node)=NULL) perror("malloc"); ptr1->next=head; return head; ptr1=ptr1->next; ptr1->next=head; return head;main() int i,n=30,m; /* 人数n为30个 */ struct node *head,*ptr; ran

12、domize(); head=CreatList(n); for(i=1;i<=30;i+) head->number=i; head->cipher=rand(); head=head->next; m=rand(); /* m取随机数 */ i=0; /* 因为我没办法删除head指向的节点，只会删除head的下一节点，所以只能从0数起。*/ while(head->next!=head) /* 当剩下最后一个人时，退出循环 */ if(i=m) ptr=head->next; /* ptr记录数到m的那个人的位置 */ printf("num

13、ber:%dn",ptr->number); printf("cipher:%dn",ptr->cipher); m=ptr->cipher; /* 让m等于数到m的人的密码 */ head->next=ptr->next; /* 让ptr从链表中脱节，将前后两个节点连接起来 */ head=hea/d->next; /* head移向后一个节点 */ free(ptr); /* 释放ptr指向的内存 */ i=0; /* 将i重新置为0，从0再开始数 */ else head=head->next; i+; printf

14、("number:%dn",head->number); printf("cipher:%dn",head->cipher); free(head); /* 让最后一个人也出列 */ 第二章 线性表习题（参考答案）一 判断题12345678910´Ö´Ö´Ö´ÖÖ´二 单选题12345678910AADC DD BDCDC三 填空题1、H->next = NULL 2、p->next = L3、p->next s4、p->

15、;next s->data t5、表是否满了四 算法设计题（答案仅供参考）1、Status OrderInsert(ElemType A, int &elenum, ElemType x) if (elenum>= arrsize) return ERROR; /如果溢出 for(i=0; i<elenum && Ai<x; i+); /找插入位置 for(j=elenum-1; j>=i; j-) Aj+1 = Aj; /将数据元素后移 Ai = x; elenum+; return OK;时间复杂度：O(elenum)2、void Re

16、ElemDelete(SqList &A) if (A.length<=1) return; /少于一个元素不处理 i=2; /从第2个以后的元素开始处理 j=1; /删除重复值后的表的最后一个元素的位置，初始的位置为1 while (i<A.length ) if (A.elemj-1 = A.elemi-1) i+;/若待处理的元素和删除重复值后的表的最后一个元素相同，不插入，继续处理下一个元素 else A.elemj = A.elemi-1;/插入无重复值得表 j+; /指向无重复值得表的最后一个元素 i+; /继续处理下一个元素 A.length = j; /修改

17、表长度 3、算法思想：利用逆置的思想处理首先将表（a1, a2, , am, b1, b2, , bn）逆置为（bn, , b2, b1 ,am, , a2, a1），然后将前n个（bn, , b2, b1）和后m个（am, , a2, a1）分别逆置后即可得到（b1, b2, , bn , a1, a2, , am）。（请同学们自己设计算法）void InverseListSeq(SeqList &L,int iStart,int iEnd) ElemType *p, *q, temp ; for (p = L.elem+iStart-1, q = L.elem + iEnd - 1

18、; p < q; p +,q -) temp = *p ; *p = *q ; *q = temp ; Status Inverse(SeqList &L,int m) n=L.length-1;InverseListSeq(L,1,m+n); InverseListSeq(L,1,m ); InverseListSeq(L,m+1,m+n);Return Ok;4、void OrderInsert(LinkList L, ElemType x) pre = L; / 指向待插入位置的前驱 p = L->next; / 指向待插入位置 while ( p && p->data < x) /查找插入位置 pre = p; p = p->next; s = (LNode *)malloc(sizeof(LNode); /分