第2章 線性表
1．選擇題
(1)順序表中第一個元素的存儲位址是100，每個元素的長度為2，則第5個元素的位址是( )。
A．110 B．108 C．100 D．120
答案：B
解釋：順序表中的資料連續存儲，是以第5個元素的位址為：100+2*4=108。
(2)在n個結點的順序表中，算法的時間複雜度是O(1)的操作是( )。 A．通路第i個結點(1≤i≤n)和求第i個結點的直接前驅(2≤i≤n) B．在第i個結點後插入一個新結點(1≤i≤n) C．删除第i個結點(1≤i≤n) D．将n個結點從小到大排序
答案：A
解釋：在順序表中插入一個結點的時間複雜度都是O(n2)，排序的時間複雜度為O(n2)
或O(nlog2n)。順序表是一種随機存取結構，通路第i個結點和求第i個結點的直接前驅都可以直接通過數組的下标直接定位，時間複雜度是O(1)。
(3) 向一個有127個元素的順序表中插入一個新元素并保持原來順序不變，平均要移動 的元素個數為( )。
A．8 B．63.5 C．63 D．7
答案：B
解釋：平均要移動的元素個數為：n/2。
(4)連結存儲的存儲結構所占存儲空間( )。
A．分兩部分，一部分存放結點值，另一部分存放表示結點間關系的指針 B．隻有一部分，存放結點值
C．隻有一部分，存儲表示結點間關系的指針
D．分兩部分，一部分存放結點值，另一部分存放結點所占單元數
答案：A
(5)線性表若采用鍊式存儲結構時，要求記憶體中可用存儲單元的位址( )。 A．必須是連續的 B．部分位址必須是連續的 C．一定是不連續的 D．連續或不連續都可以
答案：D
(6)線性表Ｌ在( )情況下适用于使用鍊式結構實作。
A．需經常修改Ｌ中的結點值 Ｂ．需不斷對Ｌ進行删除插入 C．Ｌ中含有大量的結點 Ｄ．Ｌ中結點結構複雜
答案：B
V
解釋：連結清單最大的優點在于插入和删除時不需要移動資料，直接修改指針即可。
(7)單連結清單的存儲密度( )。
A．大于1 B．等于1 C．小于1 D．不能确定
答案：C
解釋：存儲密度是指一個結點資料本身所占的存儲空間和整個結點所占的存儲空
間之比，假設單連結清單一個結點本身所占的空間為D，指針域所占的空間為N，則存儲密度為：D/(D+N)，一定小于1。
(8)将兩個各有n個元素的有序表歸并成一個有序表，其最少的比較次數是( )。 A．n B．2n-1 C．2n D．n-1
答案：A
解釋：當第一個有序表中所有的元素都小于(或大于)第二個表中的元素，隻需
要用第二個表中的第一個元素依次與第一個表的元素比較，總計比較n次。
(9)在一個長度為n的順序表中，在第i個元素(1≤i≤n+1)之前插入一個新元素時須向後移動( )個元素。
A．n-i B．n-i+1 C．n-i-1 D．I
答案：B
(10) 線性表L=(a1，a2,??an)，下列說法正确的是( )。 A．每個元素都有一個直接前驅和一個直接後繼 B．線性表中至少有一個元素
C．表中諸元素的排列必須是由小到大或由大到小
D．除第一個和最後一個元素外，其餘每個元素都有一個且僅有一個直接前驅和直接
後繼。
答案：D
(11) 建立一個包括n個結點的有序單連結清單的時間複雜度是( )。
A．O(1) B．O(n) C．O(n2) D．O(nlog2n)
答案：C
解釋：單連結清單建立的時間複雜度是O(n)，而要建立一個有序的單連結清單，則每生成一個新結點時需要和已有的結點進行比較，确定合适的插入位置，是以時間複雜度是O(n2)。
(12) 以下說法錯誤的是( )。 構時實作的效率低
B．順序存儲的線性表可以随機存取
C．由于順序存儲要求連續的存儲區域，是以在存儲管理上不夠靈活 D．線性表的鍊式存儲結構優于順序存儲結構
A．求表長、定位這兩種運算在采用順序存儲結構時實作的效率不比采用鍊式存儲結
答案：D
解釋：鍊式存儲結構和順序存儲結構各有優缺點，有不同的适用場合。
(13) 在單連結清單中，要将s所指結點插入到p所指結點之後，其語句應為( )。
VI
A．s->next=p+1; p->next=s; B．(*p).next=s; (*s).next=(*p).next; C．s->next=p->next; p->next=s->next; D．s->next=p->next; p->next=s;
答案：D。先連後段
(14) 在雙向連結清單存儲結構中，删除p所指的結點時須修改指針( )。 A．p->next->prior=p->prior; p->prior->next=p->next; B．p->next=p->next->next; p->next->prior=p; C．p->prior->next=p; p->prior=p->prior->prior; D．p->prior=p->next->next; p->next=p->prior->prior; 答案：A。
(15) 在雙向循環連結清單中，在p指針所指的結點後插入q所指向的新結點，其修改指針的操作是( )。
A．p->next=q; q->prior=p; p->next->prior=q; q->next=q; B．p->next=q; p->next->prior=q; q->prior=p; q->next=p->next; C．q->prior=p; q->next=p->next; p->next->prior=q; p->next=q; D．q->prior=p; q->next=p->next; p->next=q; p->next->prior=q;
答案：C 2．算法設計題
(1)将兩個遞增的有序連結清單合并為一個遞增的有序連結清單。要求結果連結清單仍使用原來兩個連結清單的存儲空間, 不另外占用其它的存儲空間。表中不允許有重複的資料。
[題目分析]
合并後的新表使用頭指針Lc指向，pa和pb分别是連結清單La和Lb的工作指針,初始化為相應連結清單的第一個結點，從第一個結點開始進行比較，當兩個連結清單La和Lb均為到達表尾結點時，依次摘取其中較小者重新連結在Lc表的最後。如果兩個表中的元素相等，隻摘取La表中的元素，删除Lb表中的元素，這樣確定合并後表中無重複的元素。當一個表到達表尾結點，為空時，将非空表的剩餘元素直接連結在Lc表的最後。
[算法描述]
void MergeList(LinkList &La,LinkList &Lb,LinkList &Lc) {//合并連結清單La和Lb，合并後的新表使用頭指針Lc指向 pa=La->next; pb=Lb->next;
//pa和pb分别是連結清單La和Lb的工作指針,初始化為相應連結清單的第一個結點 Lc=pc=La; //用La的頭結點作為Lc的頭結點 while(pa && pb)
{if(pa->datadata){pc->next=pa;pc=pa;pa=pa->next;} //取較小者La中的元素，将pa連結在pc的後面，pa指針後移 else if(pa->data>pb->data) {pc->next=pb; pc=pb; pb=pb->next;} //取較小者Lb中的元素，将pb連結在pc的後面，pb指針後移
VII
else //相等時取La中的元素，删除Lb中的元素
{pc->next=pa;pc=pa;pa=pa->next;
q=pb->next;delete pb ;pb =q; //把要删除的元素指派給q
}
}
pc->next=pa?pa:pb; //插入剩餘段 delete Lb; //釋放Lb的頭結點 }
(2)将兩個非遞減的有序連結清單合并為一個非遞增的有序連結清單。要求結果連結清單仍使用原來兩個連結清單的存儲空間, 不另外占用其它的存儲空間。表中允許有重複的資料。
[題目分析]
合并後的新表使用頭指針Lc指向，pa和pb分别是連結清單La和Lb的工作指針,初始化為相應連結清單的第一個結點，從第一個結點開始進行比較，當兩個連結清單La和Lb均為到達表尾結點時，依次摘取其中較小者重新連結在Lc表的表頭結點之後，如果兩個表中的元素相等，隻摘取La表中的元素，保留Lb表中的元素。當一個表到達表尾結點，為空時，将非空表的剩餘元素依次摘取，連結在Lc表的表頭結點之後。
[算法描述]
void MergeList(LinkList& La, LinkList& Lb, LinkList& Lc, ) {//合并連結清單La和Lb，合并後的新表使用頭指針Lc指向 pa=La->next; pb=Lb->next;
//pa和pb分别是連結清單La和Lb的工作指針,初始化為相應連結清單的第一個結點 Lc=pc=La; //用La的頭結點作為Lc的頭結點 Lc->next=NULL; while(pa||pb )
{//隻要存在一個非空表，用q指向待摘取的元素 if(!pa) {q=pb; pb=pb->next;} //La表為空，用q指向pb，pb指針後移 else if(!pb) {q=pa; pa=pa->next;} //Lb表為空，用q指向pa，pa指針後移
else if(pa->data<=pb->data) {q=pa; pa=pa->next;} //取較小者(包括相等)La中的元素，用q指向pa，pa指針後移 else {q=pb; pb=pb->next;}
//取較小者Lb中的元素，用q指向pb，pb指針後移 q->next = Lc->next; Lc->next = q; //将q指向的結點插在Lc 表的表頭結點之後 }
delete Lb; //釋放Lb的頭結點 }
VIII