數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題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、 若進(jìn)棧序列為1、2、3、4，進(jìn)棧過程中可以出棧，則下列不可能的一個出棧序是（）A、1，4，3，2 B、2，3，4，1 C、3，1，4，2 D、3，4，2，12、 棧和隊列的共同點(diǎn)是（）A、 都是先進(jìn)先出 B、都是先進(jìn)后出 C、只允許在端點(diǎn)處插入和刪除元素 D、沒有共同點(diǎn)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、設(shè)棧S的初始狀態(tài)為空，6個

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

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

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

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

6、C、f=f->next D、f=r->next20在表達(dá)式求值算法中，需要用幾個棧？（ ）A、0 B、1 C、2 D、3二、判斷題1線性表的邏輯順序與存儲順序總是一致的。 （ ）2順序存儲的線性表可以按序號隨機(jī)存取。 （ ）3順序表插入和刪除操作不需要付出很大時間代價，因?yàn)槊看尾僮髌骄薪话朐匦枰苿印＃?）4線性表中元素可以是各種各樣，但同一線性表中數(shù)據(jù)元素具有相同特性，因此屬于同一數(shù)據(jù)對象。（ ）5在線性表的順序存儲結(jié)構(gòu)中，邏輯上相鄰的兩個元素在物理位置上并不一定緊鄰。（ ）6在線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中，邏輯上相鄰的元素在物理位置上不一定相鄰。（ ）7線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)優(yōu)于

7、順序存儲結(jié)構(gòu)。（ ） 8在線性表的順序存儲結(jié)構(gòu)中，插入和刪除時，移動元素的個數(shù)與該元素的位置有關(guān)。（ ）9線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)是用一組任意的存儲單元來存儲線性表中數(shù)據(jù)元素的。（ ）10單鏈表中要取得某個元素，只要知道該元素的指針即可，因此，單鏈表是隨機(jī)存取的存儲結(jié)構(gòu)。（ ）11基于某種邏輯結(jié)構(gòu)之上的運(yùn)算，其實(shí)現(xiàn)是唯一的。（ ）12數(shù)據(jù)元素是最小的單位。（ ）三、填空題1線性結(jié)構(gòu)的順序存儲結(jié)構(gòu)是一種_的存儲結(jié)構(gòu)，線性結(jié)構(gòu)的鏈?zhǔn)酱鎯κ且环N_的存儲結(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é)點(diǎn)的條件是_。8在一個單鏈表中已知q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在q和p之間插入一個由指針s所指結(jié)點(diǎn)，應(yīng)執(zhí)行q=L; while(_) q=_; s->next=_; q->next=_。9帶頭結(jié)點(diǎn)的單鏈表H為空的條件是_。10不帶頭結(jié)點(diǎn)的單鏈表H為空的條件是_。四、算法設(shè)計題1 編寫一個函數(shù)，從一給定的順序表A中刪除值在xy(x<=y)之間的所有元素，要求以較高的效率來實(shí)現(xiàn)。提示：可以先將順序表中所有值在xy之間的元素置成一個特殊的值，并不立即刪除它們，然后從最后向前依次掃描，發(fā)現(xiàn)具有特殊值的元素后，移動其后面的元素將其刪