第2章 线性表
一、 选择题 1.
表长为N 的顺序表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均次数为（ ），删除一个元素需要移动的元素个数为（ ）。【＊＊，★】
A. (N-1)/2 B. N C. N+1 D. N-1 E. N/2 F. (N+1)/2 G. (N-2)/2
2. 3. 4.
线性表是具有N 个（ ）的有限序列。【＊】
A、表元素 B、字符 C、数据元素 D、数据项 E、信息 “线性表的逻辑顺序和物理顺序总是一致的。”这个结论是（ ）。【＊】 A、正确的 B、错误的 C、不一定，与具体结构有关。
线性表采用链式存储结构时，要求内存中可用存储单元的地址（ ）。【＊，★】 A、必须是连续的 B、部分地址必须是连续的 C、一定是不连续的 D、连续或不连续都可以。
5.
带头结点的单链表为空的判定条件是（ ）。【＊】 A、head==NULL B、head->next==NULL C、head->next==head D、head!=NULL
6.
不带头结点的单链表head 为空的判定条件是（ ）。【＊】 A、head==NULL B、head->next==NULL C、head->next==head D、head!=NULL
7.
非空的循环单链表head 的尾结点P 满足（ ）。（注:带头结点）【＊】 A、P->NEXT=NULL B、p=NULL C、p->next==head D、p==head
8. 9.
在一个具有n 个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（ ）。【＊，★】 A、O(1) B、O(n) C、O(n2) D、O(nlog2n)
在一个单链表中，若删除P 所指结点的后继结点，则执行（ ）。【＊，★】 A、p->next=p->next->next B、p=p->next;p->next=p->next->next C、p->next=p->next; D、p=p->next->next;
10. 在一个单链表中，若在Ｐ所指结点之后插入Ｓ所指结点，则执行（ ）。【＊，★】
A、s->next=p;p->next=s; B、s->next=p->next;p->next=s; C、s->next=p->next;p=s; D、p->next=s;s->next=p;
11. 在一个单链表中，已知q 是p 的前趋结点，若q 和p 之间插入结点s，则执行（ ）。【＊】
A、s->next=p->next;p->next=s; B、p->next=s->next;s->next=p; C、q->next=s;s->next=p; D、p->next=s;s->next=q;
12. 假设双链表结点的类型如下：【＊＊，★】
typedef struct linknode{
int data; //数据域
struct linknode *llink; //指向前趋结点的指针域 struct linknode *rlink; //指向后继结点的指针域 }bnode;
现将一个q 所指新结点作为非空双向链表中的p 所指结点的前趋结点插入到该双链表中，能正确完成此要求的语句段是（ ）。 A、q->rlink=p;q->llink=p->llink;p->llink=q;p->llink->rlink=q; B、p->llink=q;q->rlink=p;p->llink->rlink=q;q->llink=p->llink C、q->llink=p->rlink;q->rlink=p;p->llink->rlink=q;p->llink=q; D、以上都不对
13. 如上题结点结构，如在此非空循环双向链表的结点 p 之后插入结点s 的操作序列是（ ）。【＊＊】
A、p->rlink=s;s->llink=p;p->rlink->llink=s;s->rlink=p->rlink; B、p->rlink=s;p->rlink->llink=s;s->llink=p;s->rlink=p->rlink; C、s->llink=p;s->rlink=p->rlink;p->rlink=s;p->rlink->llink=s; D、s->llink=p;s->rlink=p->rlink;p->rlink->llink=s;p->rlink=s;
14. 在一个长度为n 的单链表上，设有头和尾两个指针，执行（ ）操作与链表的长度有关。【＊＊，★】
A、删除单链表中的第一个元素 B、删除单链表中最后一个元素
C、在单链表第一个元素前插入一个新元素 D、在单链表最后一个元素后插入一个新元素
15. 线性结构中的一个结点代表一个（ ）【＊】
A、数据元素 B、数据项 C、数据 D、数据结构
16. 非空线性表L=(a1,a2,…,ai,…,an)，下列说法正确的是（ ）【＊】
A、每个元素都有一个直接前驱和直接后继 B、线性表中至少要有一个元素
C、表中诸元素的排列顺序必须是由小到大或由大到小的
D、除第一个元素和最后一个元素外其余每个元素都有一个且仅有一个直接前驱和直接后继
17. 顺序表是线性表的（ ）【＊＊，★】
A、链式存储结构 B、顺序存储结构 C、索引存储结构 D、散列存储结构
18. 对于顺序表，以下说法错误的是（ ）【＊，★】
A、顺序表是用一维数组实现的线性表，数组的下标可以看成是元素的绝对地址 B、顺序表的所有存储结点按相应数据元素间的逻辑关系决定的次序依次排列 C、顺序表的特点是:逻辑结构中相邻的结点在存储结构中仍相邻
D、顺序表的特点是:逻辑上相邻的元素，存储在物理位置也相邻的单元中
19. 对顺序表上的插入、删除算法的时间复杂性分析来说，通常以（ ）为标准操作。【＊】
A、插入操作 B、结点移动 C、算术表达式 D、删除操作
20. 对于顺序表的优缺点，以下说法错误的是（ ）【＊】
A、无需为表示结点间的逻辑关系而增加额外的存储空间 B、可以方便地随机存取表中的任一结点 C、插入和删除运算较方便
D、由于顺序表要求占用连续的空间，存储分配只能预先进行(静态分配)
21. 若某线性表中最常用的操作是取第i 个元素和找第i 个元素的前趋元素，则采用（ ）存储方式最节省时间。【＊】
A、顺序表 B、单链表 C、双链表 D、单循环链表
22. 循环链表主要优点是（ ）【＊】
A、不再需要头指针了
B、已知某个结点的位置后，能够容易找到它的直接前趋 C、在进行插入、删除运算时，能更好地保证链表不断开 D、从表中任一结点出发都能扫描到整个链表
23. 在线性表的下列存储结构中，读取元素花费时间最少的是（ ）【＊，★】
A、单链表 B、双链表 C、循环链表 D、顺序表
二、 填空题 1. 2. 3.
在线性结构中，第一个结点（ ）前趋结点，其余每个结点有且只有（ ）个前趋结点。【＊】 在顺序表中插入或删除一个元素，需要平均移动（ ）元素，具体移动的元素个数与（ ）有关。【＊】 已知Ｌ是无表头结点的单链表，试从下列提供的答案中选择合适的语句序列，分别实现：【＊＊，★】 （１）表首插入Ｓ结点的语句序列是（ ）。 （２）表尾插入Ｓ结点的语句序列是（ ）。 Ａ、Ｐ->next=S; Ｂ、P=L; Ｃ、L=S;
Ｄ、P->next=S->next; Ｅ、S->next=P->next; Ｆ、S->next=L; Ｇ、S->next=NULL;
Ｈ、while(P->next!=Q)p=p->next; Ｉ、while(P->next!=NULL)P=P->next; 4.
已知L 是带表头结点的非空单链表，试从下列提供的答案中选择合适的语句序列。【＊＊＊，★】 （1）删除首元结点的语句序列是（ ） , （2）删除尾元结点的语句序列是（ ） A、P=P->next;
B、P->next=P->next->next; C、while(P!=NULL) P=P->next;
D、while(Q->next!=NULL){P=Q;Q=Q->next;} E、while(P->next!=Q) P=P->next; F、Q=P; G、Q=P->next; H、P=L; I、L=L->next; J、free(Q); 5.
已知L 是带表头结点的非空单链表，且P 结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。【＊＊】
（1）删除P 结点的直接后继结点的语句序列是（ ）, （2）删除P 结点的直接前趋结点的语句序列是（ ） A、P->next=P->next->next; B、P=P->Pnext->next;
C、while(P->next!=Q)P=P->next; D、while(P->next->next!=Q)P=P->next; E、Q=P; F、Q=P->next; G、P=L; H、L=L->next;
I、free(Q); 6. 7. 8. 9.
已知结点编号，在各结点查找概率相等的情况下，从n 个结点的单链表中查找一个结点，平均要访问（ ）个结点，从n 个结点的双链表中查找一个结点，平均要访问（ ）个结点。【＊＊，?】
对于一个具有n 个结点的单链表，在已知p 所指结点后插入一个新结点的时间复杂度是（ ）；在值域为给定值的结点后插入一个新结点的时间复杂度是（ ）。【＊，★】 单链表是（ ）的链接存储表示。【＊】 单链表中设置头结点的作用是（ ）。【＊＊】
10. 在单链表中，除首元结点外，任一结点的存储位置由（ ）指示。【＊】 11. 在非空双向循环链表中，在结点q 的前面插入结点p 的过程如下：【＊】
p->prior=q->prior; q->prior->next=p; p->next=q; ( );
12. 在双向链表中，每个结点有两个指针域，一个指向（ ），另一个指向（ ）。【＊】
13. 顺序表中逻辑上相邻的元素的物理位置（ ）相邻。单链表中逻辑上相邻的元素的物理位置（ ）相邻。【＊】
14. 为了便于讨论，有时将含n(n≥0)个结点的线性结构表示成(a1，a2,…,an)，其中每个ai 代表一个______。a1 称为______结点，an 称
为______结点，i 称为ai 在线性表中的________。对任意一对相邻结点ai、ai┼1(1≤i 点没有直接______外，其它结点有且仅有一个直接______.【＊】 16. 所有结点按1对1的邻接关系构成的整体就是______结构。【＊】 17. 线性表的逻辑结构是______结构。其所含结点的个数称为线性表的__________。【＊】 18. 在单链表中，指针p 所指结点为最后一个结点的条件是___________。【＊】 三、 判断题 1. 顺序存储的线性表可以随机存取。【＊】 2. 顺序存储的线性表的插入和删除操作不需要付出很大的代价，因为平均每次操作只有近一半的元素需要移动。【＊】 3. 线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。【＊】 4. 在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上不一定相邻。【＊】 5. 在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。【＊】 6. 在单链表中，可以从头结点进行查找任何一个元素。【＊】 7. 线性表的链式存储结构优于顺序存储结构。【＊】 8. 在线性表的顺序存储结构中，插入和删除元素时，移动元素的个数与该元素的位置有关。【＊】 9. 在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。【＊】 10. 顺序存储方式只能用于存储线性结构。【＊＊, ★】 四、 简答题 1. 2. 若较频繁地对一个线性表进行插入和删除操作，该线性表宜采用哪种存储结构？为什么？【＊】 描述概念：头指针、头结点、首元结点的区别？【＊＊，★】 3. 设 A 是一个线性表（a1a2…an），采用顺序存储结构，则在等概率的前提下，平均每插入一个元素需要移动的元素个数为多少？若元素插在ai 与ai+1 之间（0<=I<=n-1）的概率为2(n-i)/(n(n+1))，则平均每插入一个元素所要移动的元素个数又是多少？【＊＊，★】 4. 5. 6. 为什么在单循环链表中设置尾指针比设置头指针更好？【＊＊＊，★】 双链表和单循环链表中，若仅知道指针p 指向某个结点，不知道头指针，能否将结点*p 从相应的链表中删除？若可以，其时间复杂度各为多少？【＊＊】 下列算法的功能是什么？【＊＊，★】 LinkedList test1(LinkedList L) { //L 是无头结点的单链表 ListNode *q,*p; if(L&&L->next) { q=L ; L=L->next; p=L; while(p->next) p=p->next; p->next=q; q->next=NULL; } return L; } 7. 8. 9. 如果有n 个线性表同时共存，并且在处理过程中各表的长度会发生动态变化，线性表的总长度也会自动地改变。在此情况下，应选择哪一种存储结构。为什么？【＊＊】 若线性表的总数基本稳定，且很少进行插入删除操作，但要求以最快的方式存取线性表的元素，应该用哪种存储结构。为什么？【＊】 设有多项式a(x)=9+8x+9x4+5x10 b(x)=-2x+22x7-5x10 （1） 用单链表给出a(x)、b(x)的存储表示； （2） 设c (x)=a(x)+b(x)，求得c(x)并用单链表给出其存储表示。【＊，★】 五、 设计题 1. 2. 3. 编写一个函数将一个顺序表A（有多个元素且任何元素不为0）分拆成两个顺序表，使A 中大于0的元素存放在B 中，小于0 的元素存放在C 中。【＊＊】 设顺序表L 中的数据元素递增有序。试写一算法，将e插入到顺序表的适当位置，插入后保持该表的有序性。【＊＊】 A、B 为元素递增有序排列的单链表（同一表中可能有相同元素），编写算法另建一单链表C，保存两个表的公共元素，要求C 的元素值各不相同且递增有序。【＊＊】 4、设有一个由正整数组成的无序单链表，编写算法实现下列功能：【＊＊】 （1） 找出最小值结点，且显示该数值。 （2） 若该数值为奇数，则将其与直接后继结点的数值交换。 （3） 若为偶数，则将其直接后继结点删除。 六、 编程附加题 1. 2. 3. 4. 5. 6. 7. 8. 第2章 线性表参考答案 试分别用顺序表和单链表作为存储结构，实现将线性表（a0,a1,a2,….an-1）就地逆置的操作，所谓“就地”指辅助空间为O(1)。【＊＊＊，★】 设单链表 L 是一个非递减有序表，试写一个算法将x 插入其中后仍保持L 的有序性。【＊＊】 设 A、B 是两个线性表，其表中元素递增有序，长度分别为m 和n。试写一算法分别以顺序存储和链式存储将A 和B 归并成一个仍按元素值递增有序的线性表C，请分析算法的时间复杂度。【＊＊＊，★】 单链表 L 是一个递减有序表，试写一高效算法，删除表中值大于mink 且小于maxk 的结点（若表中有这样的结点），同时释放被删结点空间，这里mink 和maxk 是两个给定的参数, 它们可以和表中元素相同，也可以不同。【＊＊】 假设以两个元素依值递增有序排列的线性表A,B 分别表示两个集合，先要求另辟空间构造一个线性表C,其元素为两集合的交集，且表C 中的元素也依值递增有序排列。是对顺序表编写求C 的算法。【＊＊】 假设在长度大于 1 的单循环链表中，既无头结点也无头指针。S 为指向链表中某个结点的指针，试编写算法删除结点*s 的直接前驱结点。【＊＊】 计算带头结点的单循环链表的结点个数。【＊】 给定一个不带头结点的单链表，编写计算此链表长度的算法。【＊】 七、 选择题 1、E，A 2、C 3、B 4、D 5、B 6、A 7、C 8、B 9、A 10、B 11、C 12、D 龚注:(2012-4-25)。修改4个指针，按顺序(1)->(2)->(3)->(4)。或(1),(2),(3)顺序任意，(4)最后。 (4)p(3)(1)(2)q 13、D 14、B 头指针尾指针A.删除第一个元素：只需移动头指针----与长度n无关B.删除最后一个元素：尾指针需移动上一个结点，需搜索整个链表。----与长度n有关C.在头插入一个元素：新结点的next=头指针；头指针赋新结点指针。----与长度n无关D.在尾部插入一个元素：尾指针的next=新结点;尾指针=新结点指针----与长度n无关 15、A 16、D 17、B 18、A 19、B 20、C 21、A 22、D 23、D 八、 填空题 1、没有；1 2、表中一半；该元素的位置 3、（1）FC （2）BIAG 4、（1）HGBJ （2）HFDBJ 5、（1）FAI （2）EGDFAI 6、 n/2, n/4（此题有误！另作说明） 7、O(1 ) O(n) 8、线性表 9、插入和删除首元素时不必进行特殊处理 10、其直接前趋结点的链域 11、q->prior=p; 12、前趋结点，后继结点 13、必定，不一定 14、结点、第一个、最后一个、位置、前驱、后继 15、前驱、前驱、后继、后继 16、线性17、线性、长度18、p→next==NULL; 九、 判断题 1.√ 2.X 3.√ 4.X 5.√ 6.√ 7.X 8.√ 9.X 10.X 十、 简答题 1、宜采用链式存储结构，因为它使线性表的插入和删除操作的时间复杂度为O（1），而顺序存储结构的为O（n）。 2、首元结点是指链表中存储线性表中第一个数据元素的结点。为了操作方便，通常在链表的首元结点之前附设一个结点，称为头结点，该结点的数据域中不存线性表的数据元素，其作用是为了对链表进行操作时，可以对空表非空表的情况以及对首元结点进行统一的处理。头指针是指向链表第一个结点（头结点或首元结点）的指针。若链表中附设头结点，则不管线性表是否为空表，头指针均不为空，否则表示空表的链表的头指针为空。这三个概念对单链表、双向链表和循环链表均适用。 4、解答：单循环链表中无论设置尾指针还是头指针都可以任一结点从遍历表中其它结点，但设置尾指针时，若在表尾进行插入或删除操作时可在O(1)时间内完成，同样在表头进行插入或删除操作时也可在O(1)时间内完成。但设置的是头指针，表尾进行插入或删除操作，需要遍历整个链表，时间复杂度为O(n)。 5、解答：能删除。双链表上删除p 所指向的结点的时间复杂度为O(1)，单循环链表上删除p 所指向的结点的时间复杂度为O(n)。 6、解答：如果长度大于 1，则将首元结点删除并插入到表尾。 7、解答：应选用链式存储结构。因为顺序表是静态存储结构，只能预先分配存储单元，不能随着线性表长度的改变而变化。而链表则可根据需要动态的申请空间，因此适用于动态变化表长的线性表。 8、解答：应该用顺序存储结构。因为顺序存储结构存取元素操作的时间复杂度为 O(1)。 9、解答：用单链表表示多项式，除指针域外需设置两个数据域，一个用来存储系数，一个用来存储指数。 十一、 1、 设计题 void split(SqList A,SqList &B,SqList &C){//采用顺序存储结构实现 int I; B.length=C.length=0; for(I=0;I B.elem[B.length]=A.elem[i]; B.length++; } else{ C.elem[C.length]=A.elem[i]; C.length++; } } } 2、 status ListInsert(SqList &L,ElemType e){ ElemType *p,*q,*newbase; int j; if(L.length>=L.listsize){ newbase=(ElemType )realloc(L.elem,(L.listsize+LISTINCRMENT)*sizeof(ElemType)); if(!newbase) exit(OVERFLOW); L.elem=newbase; L.listsize=+LISTINCRMENT; } For(j=L.length-1;j>=0&&e return OK; } 3、提示：两个表的公共元素指的是既存在于A 表中，也存在于B 表中的元素，为了操作方便，先让单链表C 带有一个头结点c，再后将其删除。 LinkList Inter_eq(LinkList a,LinkList b){ LinkList p,q,r,c; c=(LinkList)malloc(sizeof(LNode));//建立单链表C 的头指针 r=c; p=a; q=b; while(p&&q){ if(p.data q=q.next; else //找到元素值相同的结点 {s=(LinkList)malloc(sizeof(LNode)); s.data=p.data;r.next=s;r=s; //把s 结点链到c 的末尾，r 始终指向链表C 的最后一个结点 while(p.data==p.next.data) p=p.next; //跳过相同的值的结点 p=p.next; while(q.data==q.next.data) q=q/next; q=q.next; } } r.next=NULL; s=c;c=c.next;free(c); //删除C 链表的头结点 return (c); } 4、参考程序： void outmin(LinkList L){ LinkList p=L,q=L; int temp; while(q){ if(p.data>q.data)p=q; q=q.next; } printf(“%d”,p.data); if(p.next){ if(p.data%2==1){ temp=p.data; p.data=p.next.data; p.next.data=temp; } else{ q=p.next;p.next=q.next; free(q); } } } 十二、 编程附加题 略 倚窗远眺，目光目光尽处必有一座山，那影影绰绰的黛绿色的影，是 春天的颜色。周遭流岚升腾，没露出那真实的面孔。面对那流转的薄雾，我会幻想，那里有一个世外桃源。在天阶夜色凉如水的夏夜，我会静静地，静静地，等待一场流星雨的来临… 许下一个愿望，不乞求去实现，至少，曾经，有那么一刻，我那还未枯萎的，青春的，诗意的心，在我最美的年华里，同星空做了一次灵魂的交流… 秋日里，阳光并不刺眼，天空是一碧如洗的蓝，点缀着飘逸的流云。偶尔，一片飞舞的落叶，会飘到我的窗前。斑驳的印迹里，携刻着深秋的颜色。在一个落雪的晨，这纷纷扬扬的雪，飘落着一如千年前的洁白。窗外，是未被污染的银白色世界。我会去迎接，这人间的圣洁。在这流转的岁月里，有着流转的四季，还有一颗流转的心，亘古不变的心。 因篇幅问题不能全部显示，请点此查看更多更全内容