數(shù)據(jù)結(jié)構(gòu)第二章習(xí)題

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可隨機訪問任一結(jié)點 b插入刪除不需要移動元素c不必事先估計存儲空間 d所需空間與其長度成正比5設(shè)線性表有n個元素，以下操作中，_在順序表上實現(xiàn)比在鏈表上實現(xiàn)效率更高。a輸出第i(1in)個元素值b交換第1個元素與第2個元素的值c順序輸出這n個元素的值d輸

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

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

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

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

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

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

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

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