數(shù)據(jù)結(jié)構(gòu)復習題23601

1、一、選擇題1、在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成（）A、動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu) B、緊湊結(jié)構(gòu)和非緊湊結(jié)C、線性結(jié)構(gòu)和非線性結(jié)構(gòu) D、內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)1、 若進棧序列為1、2、3、4，進棧過程中可以出棧，則下列不可能的一個出棧序是（）A、1，4，3，2 B、2，3，4，1 C、3，1，4，2 D、3，4，2，12、 棧和隊列的共同點是（）A、 都是先進先出 B、都是先進后出 C、只允許在端點處插入和刪除元素 D、沒有共同點4、一個隊列的入隊列序列是1，2，3，4，則隊列的輸出序列是（）A、4，3，2，1 B、1，2，3，4 C、1，4，3，2 D、3，2，4，15、設棧S的初始狀態(tài)為空，6個

2、元素入棧的順序為e1，e2，e3，e4，e5和e6。若出棧的順序是e2，e4，e3，e6，e5，e1，則棧S的容量至少應該是（）A、6 B、4 C、3 D、26、算法的時間復雜度是指（）A、執(zhí)行算法程序所需要的時間 B、算法程序的長度 C、算法執(zhí)行過程中所需要的基本運算次數(shù) D、算法程序中的指令條數(shù)7、鏈表不具有的特點是（）A、可隨機訪問任一元素 B、插入和刪除不需要移動元素 C、不必事先估計存儲空間 D、所需空間與線性表長度成正8、數(shù)據(jù)的存儲結(jié)構(gòu)是指（）A、數(shù)據(jù)所占的存儲空間量 B、數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機中的表示C、數(shù)據(jù)在計算機中的順序存儲方式 D、存儲在外存中的數(shù)據(jù)9、線性表是( ) 。A

3、、一個有限序列，可以為空； B、一個有限序列，不能為空； C、 一個無限序列，可以為空； D、一個無序序列，不能為空。 10、對順序存儲的線性表，設其長度為n，在任何位置上插入或刪除操作都是等概率的。插入一個元素時平均要移動表中的（ ）個元素。A、 n/2 B、 n+1/2 C、 n -1/2 D、 n 11、線性表采用鏈式存儲時，其地址( ) 。A、必須是連續(xù)的； B、部分地址必須是連續(xù)的； C、一定是不連續(xù)的； D、連續(xù)與否均可以。 12、用鏈表表示線性表的優(yōu)點是 （ ）。A、便于隨機存取 B、花費的存儲空間較順序存儲少 C、便于插入和刪除 D、數(shù)據(jù)元素的物理順序與邏輯順序相同13、循環(huán)鏈

4、表的主要優(yōu)點是( ) 。A、不在需要頭指針了 B、已知某個結(jié)點的位置后，能夠容易找到他的直接前趨C、在進行插入、刪除運算時，能更好的保證鏈表不斷開D、從表中的任意結(jié)點出發(fā)都能掃描到整個鏈表14、下面關(guān)于線性表的敘述錯誤的是( )。A、線性表采用順序存儲，必須占用一片地址連續(xù)的單元； B、線性表采用順序存儲，便于進行插入和刪除操作；C、線性表采用鏈式存儲，不必占用一片地址連續(xù)的單元； D、線性表采用鏈式存儲，不便于進行插入和刪除操作；15.在長度為n的順序表中，向第i個元素(1in+1)之前插入一個新元素時，需向后移動 個元素。A、 n-1 B、 n-i+1 C、n-i-1 D、i16、若某線性

5、表中最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素，則采用（ ）存儲方式最節(jié)省運算時間。A、單鏈表 B、僅有頭指針的單循環(huán)鏈表 C、 雙鏈表 D、僅有尾指針的單循環(huán)鏈表17、若某線性表中最常用的操作是取第i個元素和找第i個元素的前趨元素，則采用（ ）存儲方式最節(jié)省運算時間（ ）。A、 單鏈表 B、 順序表 C、 雙鏈表 D、 單循環(huán)鏈表18.以下不是棧的基本運算的是（ ）A、刪除棧頂元素 B、刪除棧底元素 C、判斷棧是否為空 D、將棧置為空棧19在一個鏈式隊列中，f 和 r分別為隊頭和隊尾指針，則刪除結(jié)點的運算是（ ）A、r=f->next; B、r=r->next

6、C、f=f->next D、f=r->next20在表達式求值算法中，需要用幾個棧？（ ）A、0 B、1 C、2 D、3二、判斷題1線性表的邏輯順序與存儲順序總是一致的。 （ ）2順序存儲的線性表可以按序號隨機存取。 （ ）3順序表插入和刪除操作不需要付出很大時間代價，因為每次操作平均有近一半元素需要移動。（ ）4線性表中元素可以是各種各樣，但同一線性表中數(shù)據(jù)元素具有相同特性，因此屬于同一數(shù)據(jù)對象。（ ）5在線性表的順序存儲結(jié)構(gòu)中，邏輯上相鄰的兩個元素在物理位置上并不一定緊鄰。（ ）6在線性表的鏈式存儲結(jié)構(gòu)中，邏輯上相鄰的元素在物理位置上不一定相鄰。（ ）7線性表的鏈式存儲結(jié)構(gòu)優(yōu)于

7、順序存儲結(jié)構(gòu)。（ ） 8在線性表的順序存儲結(jié)構(gòu)中，插入和刪除時，移動元素的個數(shù)與該元素的位置有關(guān)。（ ）9線性表的鏈式存儲結(jié)構(gòu)是用一組任意的存儲單元來存儲線性表中數(shù)據(jù)元素的。（ ）10單鏈表中要取得某個元素，只要知道該元素的指針即可，因此，單鏈表是隨機存取的存儲結(jié)構(gòu)。（ ）11基于某種邏輯結(jié)構(gòu)之上的運算，其實現(xiàn)是唯一的。（ ）12數(shù)據(jù)元素是最小的單位。（ ）三、填空題1線性結(jié)構(gòu)的順序存儲結(jié)構(gòu)是一種_的存儲結(jié)構(gòu)，線性結(jié)構(gòu)的鏈式存儲是一種_的存儲結(jié)構(gòu)。2線性結(jié)構(gòu)中元素的關(guān)系是_，樹形結(jié)構(gòu)中元素的關(guān)系是_，圖形結(jié)構(gòu)中元素的關(guān)系是_。3算法的5個重要特性是_、_、_、_、_。4.已知具有n個元素的一維

8、數(shù)組采用順序存儲結(jié)構(gòu)，每個元素占k個存儲單元，第一個元素的地址為LOC(a1)，那么，第i個元素LOC(ai)=_。 5在順序表中做插入操作時首先檢查_。6線性表、棧和隊列都是_結(jié)構(gòu)，可以在線性表的_位置插入和刪除元素，對于棧只能在_位置插入和刪除元素，對于隊只能在_位置插入和_位置刪除元素。7非空單循環(huán)鏈表L中*p是尾結(jié)點的條件是_。8在一個單鏈表中已知q所指結(jié)點是p所指結(jié)點的前驅(qū)結(jié)點，若在q和p之間插入一個由指針s所指結(jié)點，應執(zhí)行q=L; while(_) q=_; s->next=_; q->next=_。9帶頭結(jié)點的單鏈表H為空的條件是_。10不帶頭結(jié)點的單鏈表H為空的條件是_。四、算法設計題1 編寫一個函數(shù)，從一給定的順序表A中刪除值在xy(x<=y)之間的所有元素，要求以較高的效率來實現(xiàn)。提示：可以先將順序表中所有值在xy之間的元素置成一個特殊的值，并不立即刪除它們，然后從最后向前依次掃描，發(fā)現(xiàn)具有特殊值的元素后，移動其后面的元素將其刪