1、第2章 線性表一、單項選擇題1線性表是具有n個_的有限序列。a表元素 b字符c數(shù)據(jù)元素 d數(shù)據(jù)項2線性表是_。a一個有限序列，可以為空 b一個有限序列，不可以為空c一個無限序列，可以為空 d一個無限序列，不可以為空3線性表采用鏈表存儲時，其地址_。a必須是連續(xù)的 b一定是不連續(xù)的c部分地址必須是連續(xù)的 d連續(xù)與否均可以4鏈表不具備的特點是_。a可隨機訪問任一結點 b插入刪除不需要移動元素c不必事先估計存儲空間 d所需空間與其長度成正比5設線性表有n個元素，以下操作中，_在順序表上實現(xiàn)比在鏈表上實現(xiàn)效率更高。a輸出第i(1in)個元素值b交換第1個元素與第2個元素的值c順序輸出這n個元素的值d輸

2、出與給定值x相等的元素在線性表中的序號6設線性表中有2n個元素，以下操作中，_在單鏈表上實現(xiàn)要比在順序表上實現(xiàn)效率更高。a刪除指定的元素b在最后一個元素的后面插入一個新元素c順序輸出前k個元素d交換第i個元素和第2n-i-1個元素的值(i=0,1,n-1)7如果最常用的操作是取第i個結點及其前驅，則采用_存儲方式最節(jié)省時間。a單鏈表 b雙鏈表c單循環(huán)鏈表 d順序表8與單鏈表相比，雙鏈表的優(yōu)點之一是_。a插入和刪除操作更簡單 b可以進行隨機訪問c可以省略表頭指針或表尾指針 d訪問前后相鄰結點更靈活9帶頭結點的單鏈表l為空的判定條件是_。al= =null bl-next= =nullcl-nex

3、t= =l dl!=null10在一個具有n 個結點的有序單鏈表中插入一個新結點并仍然保持有序的時間復雜度是_。ao(1) bo(n)co(n2) do(nlog2n)11在一個長度為n(n1)的帶頭結點的單鏈表h上，另設有尾指針r（指向尾結點），執(zhí)行_操作與鏈表的長度有關。a刪除單鏈表中的第一個元素b刪除單鏈表中的最后一個元素c在單邏表第一個元素前插入一個新元素d在單鏈表最后一個元素后插入一個新元素12對于一個具有n個元素的線性表，建立其單鏈表的時間復雜度_。ao(log2n) bo(1)co(n2) do(n)二、填空題1在線性表的順序存儲中，元素之間的邏輯關系是通過_決定的；在線性表的鏈

4、式存儲中，元素之間的邏輯關系是通過_決定的。2向一個長度為n的順序表中的第i個元素(1in)之前插入一個元素時，需向后移動_個元素。3在一個長度為n的順序表中刪除第i個元素(1in)時，需向前移動_個元素。4為了設置一個空的順序表l，應采用的操作是_。5刪除順序表的_元素，不需要移動任何元素。6刪除順序表的_元素，需要移動的元素最多。7在順序表_元素后面插入一個元素，不需要移動任何元素。8在順序表的第_元素前插入元素1個元素，需要移動的元素最多。9 在長度為n的順序表l中查找與指定元素值相同的元素，其時間復雜度為_。10在單鏈表中設置頭結點的作用是_。11在單鏈表中，要刪除某一指定的結點，必須

5、找到該結點的_結點。12訪問單鏈表中的結點，必須沿著_依次進行。13求單鏈表長度的時間復雜度為_。14刪除單鏈表l中某結點*p之后的一個結點，其時間復雜度為_。15刪除單鏈表l中某結點*p之前的一個結點，其時間復雜度為_。16在一個單鏈表l中，指針p指向l的某個結點，在p之前插入一個指針s所指結點時的操作為：(1) s-next=_； (2) p-next=s；(3) t=p-data；(4) p-data=_；(5) s-data=_；17在一個單鏈表（已知每個結點含有數(shù)據(jù)域data和指針域next）中刪除p所指結點時的操作為：(1) q=p-next；(2) p-data=q-data；(

6、3) p-next=_；(4) free(q)；18在一個單鏈表l中，p指向l中的某個結點，在指針p指向的結點之后插入指針s指向的結點時，應執(zhí)行s-next=_和p-next=_的操作。19對于一個具有n個結點的單鏈表，在指針p指向結點之后插入一個新結點的時間復雜度是_；在給定值為x的結點后插入一個新結點的時間復雜度是_。三、判斷題1線性表中每個元素都有一個直接前驅和一個直接后繼。2線性表中所有元素的排列順序必須由小到大或由大到小。3線性表的順序存儲結構優(yōu)于鏈式存儲結構。4在循環(huán)單鏈表中，從表中任一結點出發(fā)都可以通過前后的移動操作掃描整個循環(huán)鏈表。5在單鏈表中，可以從頭結點開始查找任何一個結點

7、。6在雙鏈表中，可以從任一結點開始沿同一方向查找到任何其他結點。四、簡答題1簡述順序表和鏈表存儲方式的特點。2在什么情況下使用順序表比鏈表好。3若頻繁地對一個線性表進行插入和刪除操作，該線性表宜采用何種存儲結構，為什么？4對鏈表要設置頭結點的作用是什么？（至少說出兩條好處）5在單鏈表雙鏈表和單循環(huán)鏈表中，若僅知道指針p指向某結點，不知道頭指針，能否將結點*p從相應的鏈表中刪去（不允許進行結點之間數(shù)據(jù)域的復制）？若可以，其時間復雜度各為多少？五、算法設計題1設計一個求元素逆置的算法。(1) 將順序表的所有元素逆置，要求算法空間復雜度為o(1)。(2) 將帶頭結點的單鏈表的所以元素逆置，要求空間復

8、雜度為o(1)。2設計一些有關刪除元素的算法。(1) 從順序表中刪除所有元素值為x的元素，要求空間復雜為o(1)。(2) 從順序表中刪除元素值在x到y(tǒng)（xy）之間的所有元素，要求空間復雜度為o(1)。(3) 從順序表中刪除重復的元素，并使剩余元素間的相對次序保持不變。(4) 從單鏈表l中刪除值為x的結點的直接前驅結點。(5) 從帶頭結點的單鏈表l中刪除一個最小值的結點。(6) 從一個遞增單鏈表中，刪除值域重復的結點。并分析算法的時間復雜度。(7) 從一個非有序單鏈表（允許出現(xiàn)值域重復的結點）中，刪除值域重復的結點。(8) 從一個帶頭結點遞增有序表的單鏈表l中，刪除表中data值在大于或等于mi

9、n且小于或等于max之間的結點（若表中有這樣的結點），同時釋放被刪結點的空間，這里min和max是兩個給定的參數(shù)。(9) 從一個帶頭結點非有序表的單鏈表l中，刪除表中data值在大于或等于min且小于或等于max之間的結點（若表中有這樣的結點），同時釋放被刪結點的空間，這里min和max是兩個給定的參數(shù)。并分析算法的時間復雜度。3設計與集合運算有關的算法。(1) 用順序表表示集合，實現(xiàn)集合的交集、并集和差集的運算。(2) 用單鏈表表示集合，實現(xiàn)集合的交集、并集和差集的運算。4綜合問題的算法(1) 設有一個順序表，其元素為整型數(shù)據(jù)，設計一個算法將中所有小于的整數(shù)放在前半部分，大于的整數(shù)放在后半部分。 (2) 設c=a1,b1,a2,b2,an, bn 為