第二章线性表习题

第二章线性表一、选择题1.一个线性表第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的地址是( )（A）110 （B）108（C）100 （D）120参考答案：B2. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（）个元素。

（A）64（B）63 （C）63.5 （D）7参考答案：C3.线性表采用链式存储结构时，其地址（）。

(A) 必须是连续的 (B) 部分地址必须是连续的(C) 一定是不连续的 (D) 连续与否均可以参考答案：D4. 在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行（）（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;参考答案：B5.在一个单链表中，若删除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;参考答案：A6.下列有关线性表的叙述中，正确的是（）（A）线性表中的元素之间隔是线性关系（B）线性表中至少有一个元素（C）线性表中任何一个元素有且仅有一个直接前趋（D）线性表中任何一个元素有且仅有一个直接后继参考答案：A7.线性表是具有n个（）的有限序列（n≠0)（A）表元素（B）字符（C）数据元素（D）数据项参考答案：C二、判断题1.线性表的链接存储，表中元素的逻辑顺序与物理顺序一定相同。

（）2.如果没有提供指针类型的语言，就无法构造链式结构。

（）3.线性结构的特点是只有一个结点没有前驱，只有一个结点没有后继，其余的结点只有一个前驱和后继。

第二章线性表习题及答案‎一、基础知识题‎2.1 试描述头指‎针、头结点、开始结点的‎区别、并说明头指‎针和头结点‎的作用。

答：始结点是指‎链表中的第‎一个结点，也就是没有‎直接前趋的‎那个结点。

链表的头指‎针是一指向‎链表开始结‎点的指针(没有头结点‎时)，单链表由头‎指针唯一确‎定，因此单链表‎可以用头指‎针的名字来‎命名。

头结点是我‎们人为地在‎链表的开始‎结点之前附‎加的一个结‎点。

有了头结点‎之后，头指针指向‎头结点，不论链表否‎为空，头指针总是‎非空。

而且头指针‎的设置使得‎对链表的第‎一个位置上‎的操作与在‎表其他位置‎上的操作一‎致(都是在某一‎结点之后)。

2.2 何时选用顺‎序表、何时选用链‎表作为线性‎表的存储结‎构为宜?答：在实际应用‎中，应根据具体‎问题的要求‎和性质来选‎择顺序表或‎链表作为线‎性表的存储‎结构，通常有以下‎几方面的考‎虑：1.基于空间的‎考虑。

当要求存储‎的线性表长‎度变化不大‎，易于事先确‎定其大小时‎，为了节约存‎储空间，宜采用顺序‎表；反之，当线性表长‎度变化大，难以估计其‎存储规模时‎，采用动态链‎表作为存储‎结构为好。

2.基于时间的‎考虑。

若线性表的‎操作主要是‎进行查找，很少做插入‎和删除操作‎时，采用顺序表‎做存储结构‎为宜；反之，若需要对线‎性表进行频‎繁地插入或‎删除等的操‎作时，宜采用链表‎做存储结构‎。

并且，若链表的插‎入和删除主‎要发生在表‎的首尾两端‎，则采用尾指‎针表示的单‎循环链表为‎宜。

2.3 在顺序表中‎插入和删除‎一个结点需‎平均移动多‎少个结点?具体的移动‎次数取决于‎哪两个因素‎?答：在等概率情‎况下，顺序表中插‎入一个结点‎需平均移动‎n/2个结点。

删除一个结‎点需平均移‎动(n-1)/2个结点。

具体的移动‎次数取决于‎顺序表的长‎度n以及需‎插入或删除‎的位置i。

i 越接近n‎则所需移动‎的结点数越‎少。

2.4 为什么在单‎循环链表中‎设置尾指针‎比设置头指‎针更好?答：尾指针是指‎向终端结点‎的指针，用它来表示‎单循环链表‎可以使得查‎找链表的开‎始结点和终‎端结点都很‎方便，设一带头结‎点的单循环‎链表，其尾指针为‎rear，则开始结点‎和终端结点‎的位置分别‎是rear‎->next->next 和rear, 查找时间都‎是O(1)。

第二章线性表习题1 ．填空题(1) 链表中逻辑上相邻的元素的物理位置( ) 相连。

(2) 在单链表中除首结点外，任意结点的存储位置都由( ) 结点中的指针指示。

(3) 在单链表中，设置头结点的作用是在插入或删除首结点时不必对( ) 进行处理。

(4) 已带头结点的单链表L ，指针p 指向L 链表中的一个结点，指针q 是指向L 链表外的一个结点，则：在指针p 所指结点后插入q 所指结点的语句序列是( ) ；在指针p 所指结点前插入q 所指结点的语句序列是( ) ；将q 所指结点插入在链表首结点的语句序列是( ) ；将q 所指结点插入在链表尾结点的语句序列是( ) 。

(5) 已知带表头结点的单链表L ，指针p 指向L 链表中的一个结点（非首结点，非尾结点），则：删除指针p 所指结点的直接后继结点的语句是( ) 。

删除指针p 所指结点的直接前驱结点的语句序列是( ) 。

删除指针p 所指结点的语句序列是( ) 。

删除首结点的语句序列是( ) 。

⑤删除尾结点的语句序列是( ) 。

(6) 已知指针p 指向双向链表中的一个结点（非首结点，非尾结点），则：将结点s 插入在指针p 所指结点的直接后继位置的语句是( ) 。

将结点s 插入在指针p 所指结点的直接前驱位置的语句是( ) 。

删除指针p 所指结点的直接后继结点的语句序列是( ) 。

删除指针p 所指结点的直接前驱结点的语句序列是( ) 。

⑤删除指针p 所指结点的语句序列是( ) 。

(7) 线性表的存储结构有顺序存储和( ) 存储两种。

(8) 线性表的元素长度为4 ，在顺序存储结构下Loc(ai)=2000 ，则Loc(ai ＋1)=( ) 。

(9) 线性表a 的元素长度为L ，在顺序存储结构下Loc(ai)=Loc(a1)+( ) 。

(10) 在线性表的链式存储结构中，某结点的指针字段指向该结点的( ) 两种存储。

(11) 线性表的元素长度为4 ，Loc(ai ＋1)=1000 ，则Loc(a3)=( ) 。

一、选择题1、用单链表方式存储的线性表，存储每个结点需要两个域，一个是数据域，另一个是（）A、当前结点所在的地址域B、指针域C、空指针域D、空闲域2、不带头结点的单链表head为空的判断条件是（）A、head==NULLB、head->next==NULLC、head->data==NULLD、head!=NULL3、在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在p和q之间插入s结点，则执行（）A、s->next=p; q->next=s;B、p->next=s->next; s->next=p;C、q->next=s->next; s->next=p;D、p->next=s; s->next=q;4、在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（）A、O（1）B、O（n）C、O（n2）D、O（nlog2n）5、一个单链表中，若删除p所指结点的后续结点，则执行（）A、p->next=p->next->next;B、p=p->next; p->next=p->next->next;C、p->next=p;D、p=p->next->next;6、已知一个顺序存储的基本线性表，设每个结点需占m个存储单元，若第一个结点的地址为d1，则第i个结点的地址为（）A、d1+(i-1)*mB、d1+i*mC、d1-i*mD、d1+(i+1)*m7、在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是（）A、访问第i个结点(1<=i<=n)和求第i个结点的直接前驱(2<=i<=n)B、在第i个结点后插入一个新结点(1<=i<=n)C、删除第i个结点(1<=i<=n)D、将n个结点从小到大排序8、下面给出的算法段是要把一个q所指新结点作为非空双向链表中的p所指结点的前驱结点插入到该双向链表中，能正确完成要求的算法段是（）A、q->next=p; q->prior=p->prior; p->prior=q; p->prior->next=q;B、p->prior=q; q->next=p; p->prior->next=q; q->prior=p->prior;C、q->prior=p->prior; q->next=p; p->prior->next=q; p->prior=q;D、以上都不对9、在循环双链表的p所指结点之后插入s所指结点的操作是（）A、p->next=s; s->prior=p; p->next->prior=s; s->next=p->next;B、p->next=s; p->next->prior=s; s->prior=p; s->next=p->next;C、s->prior=p; s->next=p->next; p->next=s; p->next->prior=s;D、s->prior=p; p->next->prior=s; s->next=p->next; p->next=s;10、从具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较（）个结点。

习题二参考答案一、选择题1.链式存储结构的最大优点是（ D ）。

A.便于随机存取B.存储密度高C.无需预分配空间D.便于进行插入和删除操作2.假设在顺序表{a0,a1,……,a n－1}中，每一个数据元素所占的存储单元的数目为4，且第0个数据元素的存储地址为100，则第7个数据元素的存储地址是（ D ）。

A.106B. 107C.124D.1283.在线性表中若经常要存取第i个数据元素及其前趋，则宜采用（ A ）存储方式。

A.顺序表B. 带头结点的单链表C.不带头结点的单链表D. 循环单链表4.在链表中若经常要删除表中最后一个结点或在最后一个结点之后插入一个新结点，则宜采用（ C ）存储方式。

A.顺序表B. 用头指针标识的循环单链表C. 用尾指针标识的循环单链表D. 双向链表5.在一个单链表中的p和q两个结点之间插入一个新结点，假设新结点为S,则修改链的java语句序列是（ D ）。

A.s.setNext(p); q.setNext(s);B. p.setNext(s.getNext()); s.setNext(p);C. q.setNext(s.getNext()); s.setNext(p);D. p.setNext(s); s.setNext(q);6.在一个含有n个结点的有序单链表中插入一个新结点，使单链表仍然保持有序的算法的时间复杂度是（ C ）。

A.O(1)B. O(log2n)C. O(n)D. O(n2)7.要将一个顺序表{a0,a1,……,a n-1}中第i个数据元素a i(0≤i≤n-1)删除，需要移动（ B ）个数据元素。

A.iB. n-i-1C. n-iD. n-i+18.在带头结点的双向循环链表中的p结点之后插入一个新结点s，其修改链的java语句序列是（ D ）。

A.p.setNext(s); s.setPrior(p); p.getNext().setPrior(s);s.setNext(p.getPrior());B.p.setNext(s); p.getNext().setPrior(s); s.setPrior(p);s.setNext(p.getNext());C.s.setPrior(p); s.setNext(p.getNext()); p.setNext(s);p.getNext().setPrior(s);D.s.setNext(p.getNext()); s.setPrior(p); p.getNext().setPrior(s);p.setNext(s);9.顺序表的存储密度是（ B ），而单链表的存储密度是（ A ）。

第二章线性表第二章线性表一、选择题1．线性表是具有n个__C___的有限序列（n>0）。

A．表元素B．字符C．数据元素D．数据项2．一个顺序表所占用的存储空间大小与___B___无关。

A．表的长度C．元素的类型B．元素的存放顺序D．元素中各字段的类型3．线性表的顺序存储结构是一种__A___。

A．随机存取的存储方式C．索引存取的存储方式B．顺序存取的存储方式D．Hash存取的存储方式4. 若线性表采用顺序存储结构，每个元素占用4 个存储单元，第一个元素的存储地址为100,则第12 个元素的存储地址是__B____。

A．112 B.144 C.148 D.4125. 线性表是__A____。

A．一个有限序列，可以为空B．一个有限序列，不能为空C．一个无限序列，可以为空D．一个无限序列，不能为空6．对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为__C____。

A．O（n）O（n）B．O（n）O（1）C．O（1）O（n）D．O（1）O(1) 7．若长度为n的非空线性表采用顺序存储结构，删除表的第i个数据元素，首先需要移动表中___A____中数据元素。

A．n-i B．n+i C．n-i+1 D．n-i-1 8．对顺序存储的线性表，设其长度为n，在任何位置插入或删除操作都是等概率的。

删除一个元素时平均要移动表中的____C____个元素。

A.n/2 B.（n+1）/2 C.（n-1）/2 D.n 9．若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为__C____。

（1≤i≤n+1）A．O（0）B．O（1）C．O（n）D．O（n2）10．线性表中各链接点之间的地址___C____。

A．必须连续B．部分地址必须连续C．不一定连续D．连续与否无所谓11．在n个结点的线性表的数组表示中，算法的时间复杂度是O（1）的操作是_A______。

A．访问第i个结点后插入一个新结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）B．在第i个结点后插入一个新结点（1≤i≤n）C．删除第i 个结点（1≤i≤n）D．以上都不对12．单链表中，增加一个头结点的目的是为了____C_____。

第二章线性表一、选择题1.一个线性表第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的地址是( )（A）110 （B）108（C）100 （D）120参考答案：B2. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（）个元素。

（A）64（B）63 （C）63.5 （D）7参考答案：C3.线性表采用链式存储结构时，其地址（）。

(A) 必须是连续的 (B) 部分地址必须是连续的(C) 一定是不连续的 (D) 连续与否均可以参考答案：D4. 在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行（）（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;参考答案：B5.在一个单链表中，若删除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;参考答案：A6.下列有关线性表的叙述中，正确的是（）（A）线性表中的元素之间隔是线性关系（B）线性表中至少有一个元素（C）线性表中任何一个元素有且仅有一个直接前趋（D）线性表中任何一个元素有且仅有一个直接后继参考答案：A7.线性表是具有n个（）的有限序列（n≠0)（A）表元素（B）字符（C）数据元素（D）数据项参考答案：C二、判断题1.线性表的链接存储，表中元素的逻辑顺序与物理顺序一定相同。

（）2.如果没有提供指针类型的语言，就无法构造链式结构。

（）3.线性结构的特点是只有一个结点没有前驱，只有一个结点没有后继，其余的结点只有一个前驱和后继。

第二章线性表习题一判断题1．线性表的逻辑顺序与存储顺序总是一致的。

2．顺序存储的线性表可以按序号随机存取。

3．顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。

4．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。

5．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。

6．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。

7．线性表的链式存储结构优于顺序存储结构。

8．在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。

9．线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。

10．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。

二单选题 (请从下列A，B，C，D选项中选择一项)1．线性表是( ) 。

(A) 一个有限序列，可以为空；(B) 一个有限序列，不能为空；(C) 一个无限序列，可以为空；(D) 一个无序序列，不能为空。

2．对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。

插入一个元素时平均要移动表中的（）个元素。

(A) n/2 (B) n+1/2 (C) n -1/2 (D) n3．线性表采用链式存储时，其地址( ) 。

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

4．用链表表示线性表的优点是（）。

(A)便于随机存取 (B)花费的存储空间较顺序存储少(C)便于插入和删除 (D)数据元素的物理顺序与逻辑顺序相同5．某链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用( )存储方式最节省运算时间。

(A)单链表 (B)双链表 (C)单循环链表 (D)带头结点的双循环链表6．循环链表的主要优点是( )。

第2章线性表1.编写一个算法，往单链表里数据为w0的结点前面插入一个给定值x的结点。

2.写出将单链表逆置的算法。

即若原单链表中存储元素的次序为a0,a1,a2,…,an-1，则单链表逆置后便为an-1,an-2,…,a1,a0。

要求就地逆置，即不再重新开辟存储空间，只通过调整指针来完成，并且使用尽可能少的附加单元。

3 简述以下算法的功能。

(1) Status A(LinkedList L) { // L 是无表头结点的单链表if (L && L->next){Q =L; L =L->next; P =L ;while ( P->next) P =P->next ;P->next =Q; Q->next = NULL;}return OK;} // A(2) void BB(LNode *s, LNode *q ) {p =s ;while (p->next!=q) p =p->next ;p->next =s;} //BBvoid AA(LNode *pa, LNode *pb) {// pa 和pb 分别指向单循环链表中的两个结点BB(pa, pb);BB(pb, pa);} //AA4 指出以下算法的错误和低效（即费时）之处，并将它改写为一个既正确又高效的算法。

Status DeleteK(SqList &a, int i, int k){//本过程从顺序存储结构的线性表a中删除第i个元素起的k个元素if(i<1 || k<0 || i+k>a.length)return INFEASIBLE; //参数不合法else{for(count=1; count<k; count++){//删除一个元素for(j=a.length; j>=i+1; j--)a.elem[j-1]= a.elem[j];a.length--;}}returnOK;}//DeleteK5 试写一算法在带表头结点的单链表结构上实现线性表操作LOCATE(L,X)。