數(shù)據(jù)結(jié)構(gòu)題庫課后練習(xí)題答案章節(jié)測(cè)試題19章全

經(jīng)典word整理文檔，僅參考，雙擊此處可刪除頁眉頁腳。本資料屬于網(wǎng)絡(luò)整理，如有侵權(quán)，請(qǐng)聯(lián)系刪除，謝謝！和n2__________。A、>2>，__________。A、__________。A、__________________？________。__________？__________。n{}2__________。；）{；；})2)3)42)22__________。；A、)22__________。；；；；；；；；；；A、____________________？__________22)2Ddddd4，Rr，rdd2,dd3,dd4}{@}}{@}{@n是不小于1}{@{x}}n(n2iin2i11212121nnnniiii)ii=222i1i1i1i1111nn(nn(nn=n(n12412nnn}和Z{}一、選擇題1．線性表是具有n個(gè)__C_A．表元素B．字符C．?dāng)?shù)據(jù)元素D．?dāng)?shù)據(jù)項(xiàng)2．一個(gè)順序表所占用的存儲(chǔ)空間大小與___B___無關(guān)。A．表的長度B．元素的存放順序C．元素的類型D．元素中各字段的類型3．線性表的順序存儲(chǔ)結(jié)構(gòu)是一種__A___。A．隨機(jī)存取的存儲(chǔ)方式C．索引存取的存儲(chǔ)方式B．順序存取的存儲(chǔ)方式D．Hash存取的存儲(chǔ)方式4.4儲(chǔ)地址為100,則第12個(gè)元素的存儲(chǔ)地址是__B____。A．112B.144C.148D.4125.線性表是__A____。A．一個(gè)有限序列，可以為空B．一個(gè)有限序列，不能為空C．一個(gè)無限序列，可以為空D．一個(gè)無限序列，不能為空C____。A．O（n）O（n）B．O（n）O（1）C．O（1）O（n）D．O（1）O(1)7．若長度為n的非空線性表采用順序存儲(chǔ)結(jié)構(gòu)，刪除表的第i個(gè)數(shù)據(jù)元素，首先需要移動(dòng)表中___A____中數(shù)據(jù)元素。A．n-iB．n+iC．n-i+1D．n-i-18．對(duì)順序存儲(chǔ)的線性表，設(shè)其長度為n，在任何位置插入或刪除操作都是等概率的。刪除一個(gè)元素時(shí)平均要移動(dòng)表中的____C____個(gè)元素。A.n/2B.（n+1）/2C.（n-1）/2D.n9．若長度為n的線性表采用順序存儲(chǔ)結(jié)構(gòu)，在其第i個(gè)位置插入一個(gè)新元素的算法的時(shí)間復(fù)雜度為__CA．O（0）B．O（1）C．O（n）D．O（n）210．線性表中各鏈接點(diǎn)之間的地址___C____。A．必須連續(xù)B．部分地址必須連續(xù)D．連續(xù)與否無所謂C．不一定連續(xù)11．在n個(gè)結(jié)點(diǎn)的線性表的數(shù)組表示中，算法的時(shí)間復(fù)雜度是O（1）的操作是_A______。ii≤i≤n）B．在第i個(gè)結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)（1≤i≤n）C．刪除第i個(gè)結(jié)點(diǎn)（1≤i≤n）D．以上都不對(duì)12．單鏈表中，增加一個(gè)頭結(jié)點(diǎn)的目的是為了____C_____。A．使單鏈表至少有一個(gè)結(jié)點(diǎn)B．標(biāo)識(shí)表結(jié)點(diǎn)中首結(jié)點(diǎn)的位置C．方便運(yùn)算的實(shí)現(xiàn)D．說明單鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)13．對(duì)于一個(gè)頭指針為head的帶頭結(jié)點(diǎn)的單鏈表，判定該表為空表的條件是_B____。A．head==NULLB．head->next==NULLD．head!=NULLC．head->next==headn的單鏈表鏈接在長度為m的單鏈表后面的算法的時(shí)間復(fù)雜度采用大O形式表示應(yīng)該是___C____。A．O（1）15．靜態(tài)鏈表中指針表示的是___C____。A．下一個(gè)元素的地址B．內(nèi)存儲(chǔ)器的地址B．O（n）C．O（m）D．O（n+m）C．下一個(gè)元素在數(shù)組中的位置D．左鏈或右鏈指向的元素的地址16．非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)p滿足__A______。A．P->link=headB．P->link=NULLC．P=NULLD．P=head17某線性表用帶頭結(jié)點(diǎn)的循環(huán)單鏈表存儲(chǔ)，頭指針為head，當(dāng)．head->next->next==head成立時(shí)，線性表的長度是___B____。A．018．在什么情況下，應(yīng)使用鏈?zhǔn)浇Y(jié)構(gòu)存儲(chǔ)線性表L?___B____A．需經(jīng)常修改L中的結(jié)點(diǎn)值B．需不斷對(duì)L進(jìn)行刪除插入B．1C．2D．3C．需要經(jīng)常查詢L中的結(jié)點(diǎn)值D．L中結(jié)點(diǎn)結(jié)構(gòu)復(fù)雜19．與單鏈表相比較，雙向鏈表的優(yōu)點(diǎn)之一是___D_____。A．可以省略頭結(jié)點(diǎn)指針C．插入、刪除操作更簡(jiǎn)單B．可以隨機(jī)訪問D．順序訪問相鄰結(jié)點(diǎn)更靈活20．某線性表常發(fā)生的操作為刪除第一個(gè)數(shù)據(jù)元素和最后一個(gè)元素后添加新元素，采用__D__作為存儲(chǔ)結(jié)構(gòu)，能使其存儲(chǔ)效率和時(shí)間效率最高。A．單鏈表B．僅用頭指針的循環(huán)單鏈表D．僅用尾指針的循環(huán)單鏈表C．雙向循環(huán)鏈表點(diǎn)。則采用_D___存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。A．單鏈表B．雙鏈表C．單循環(huán)鏈表D．帶頭結(jié)點(diǎn)的雙循環(huán)鏈表映數(shù)據(jù)之間的邏輯關(guān)系，則應(yīng)用___C____。A．順序方式存儲(chǔ)B．散列方式存儲(chǔ)C．鏈接方式存儲(chǔ)D．以上方式均可除運(yùn)算，則利用___A___存儲(chǔ)方式最節(jié)省時(shí)間。A．順序表B．雙鏈表C．帶頭結(jié)點(diǎn)的雙循環(huán)鏈表D．單循環(huán)鏈表i時(shí)間應(yīng)采用的存儲(chǔ)方式為___D_____。A．單鏈表B．雙向鏈表C．單循環(huán)鏈表D．順序表25．下面哪一條是順序存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)？___C______A．插入運(yùn)算方便C．存儲(chǔ)密度大B．可方便地用于各種邏輯結(jié)構(gòu)的存儲(chǔ)表示D．刪除運(yùn)算方便26．下面關(guān)于線性表的敘述中，錯(cuò)誤的是___B_____。A.線性表采用順序存儲(chǔ)，必須占用一批連續(xù)的存儲(chǔ)單元B.線性表采用順序存儲(chǔ)，便于進(jìn)行插入和刪除的操作C.線性表采用鏈接存儲(chǔ)，不必占用一片連續(xù)的存儲(chǔ)單元D.線性表采用鏈接存儲(chǔ)，便于插入和刪除操作p所指的鏈接點(diǎn)后面插入一個(gè)由q所指的鏈接點(diǎn)的過程是依次執(zhí)行動(dòng)作__B____。A．q->link=p；p->link=q；C．q->link=p->link；p=q；B．q-link=p->link；p->link=q；D．p->link=q；q->link=p；q所指的鏈接點(diǎn)前面插入一個(gè)由p指的鏈接點(diǎn)的過程是依次執(zhí)行語句p->rlink=q；p->llink=q->llink;q->llink=p;____D____。A．q->rlink->llink=p;C．p->rlink->llink=p;B．q->llink->rlink=p;D．p->llink->rlink=p;q所指的鏈接點(diǎn)后面插入一個(gè)由p指的鏈接點(diǎn)的動(dòng)作依次為__D____。A．p->llink=q;p->rlink=q->rlink;q->rlink=p;q->rlink->llink=p；B．p->rlink=q->rlink;p->llink=q;q->rlink;q->rlink->llink=p；C．p->llink=q;p->rlink=q->rlink;q->rlink=p;p->llink->rlink=p；D．p->llink=q;p->rlink=q->rlink;q->rlink=p;p->rlink->llink=p；30．在雙向鏈表存儲(chǔ)結(jié)構(gòu)中，刪除p所指的結(jié)點(diǎn)時(shí)須修改指針__A____。A．p->llink->rlink=p->rlink;p->rlink->llink=p->llink;B．p->llink=p->llink->llink;p->llink->rlink=p;C．p->rlink->llink=p;p->rlink=p->rlink->rlink;D．p->rlink=p->llink->llink;p->llink=p->rlink->rlink;31．單鏈表的存儲(chǔ)密度為__C____。A．大于1B．等于5C．小于1D．不能確定二．判斷題1.線性表的邏輯順序與存儲(chǔ)順序總是一致的。2.線性表的順序存儲(chǔ)結(jié)構(gòu)比鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)更好。3.線性表中的所有元素都有一個(gè)前驅(qū)元素和后繼元素。（）（）（）4.不論線性表采用順序存儲(chǔ)結(jié)構(gòu)還是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，刪除值為X的結(jié)點(diǎn)的時(shí)間復(fù)雜度均為O(n)。（）5.線性的數(shù)據(jù)結(jié)構(gòu)可以順序存儲(chǔ)，也可以鏈接存儲(chǔ)。非線性的數(shù)據(jù)結(jié)構(gòu)只能鏈接存儲(chǔ)。（）6.）7.用一組地址連續(xù)的存儲(chǔ)單元存放的元素一定構(gòu)成線性表。（）8.（）9.順序表的每個(gè)結(jié)點(diǎn)只能是一個(gè)簡(jiǎn)單類型，而鏈表的每個(gè)結(jié)點(diǎn)可以是一個(gè)復(fù)雜類型。（）（）（）10.順序表中所有結(jié)點(diǎn)的類型必須相同。11.對(duì)鏈表進(jìn)行插入和刪除操作時(shí)不必移動(dòng)鏈表中結(jié)點(diǎn)。12.非空的雙向循環(huán)鏈表中任何結(jié)點(diǎn)的前驅(qū)指針均不為空。（）13.據(jù)元素之間的邏輯順序。（）（）14.單鏈表從任何一個(gè)結(jié)點(diǎn)出發(fā)，都能訪問到所有結(jié)點(diǎn)。15.符號(hào)p->next出現(xiàn)在表達(dá)式中表示p）16.帶表頭結(jié)點(diǎn)的雙向循環(huán)鏈表判空的條件是：first->rlink==（）三、綜合應(yīng)用題1.利用順序表的操作，實(shí)現(xiàn)以下函數(shù)：1）從順序表中刪除具有最小值的元素并由函數(shù)返回被刪除元素的值。空出的位置由最后一個(gè)元素填補(bǔ)，若順序表為空則顯示出錯(cuò)信息并退出運(yùn)行。2）從順序表中刪除第i個(gè)元素并由函數(shù)返回被刪除元素的值，如果i不合理或順序表為空則顯示出錯(cuò)信息并退出運(yùn)行。3）向順序表中第i個(gè)位置插入一個(gè)新元素x。如果i不合理則顯示出錯(cuò)信息并退出運(yùn)行4）從順序表中刪除具有給定值x的所有元素。5）從順序表中刪除其值在給定值s與t之間（要求s小于t）的所有元素。如果s或t不合理或者順序表為空，則顯示錯(cuò)誤信息并退出。6）從有序順序表中刪除其值在給定值s與t之間（要求s小于t）的所有元素，如果s或t不合理或順序表為空，則顯示錯(cuò)誤信息并退出。7）將兩個(gè)有序順序表合并成一個(gè)新的有序順序表并由函數(shù)返回結(jié)果順序表8）從有序順序表中刪除所有其值重復(fù)的元素，使表中所有元素的值均不相同。2.請(qǐng)?jiān)O(shè)計(jì)算法將不帶頭結(jié)點(diǎn)的單鏈表就地逆置。3.有一個(gè)單鏈表L（至少有1head，編寫一個(gè)過程將L結(jié)點(diǎn)，如此等等。找出最小值結(jié)點(diǎn)，且打印該數(shù)值。若該數(shù)值是奇數(shù)，則將其與直接后繼結(jié)點(diǎn)的數(shù)值交換。若該數(shù)值是偶數(shù)，則將其直接后繼結(jié)點(diǎn)刪除。5.給定（已生成）一個(gè)帶表頭結(jié)點(diǎn)的單鏈表，設(shè)head為頭指針，結(jié)點(diǎn)的結(jié)為指針，試寫出算法：按遞增次序的結(jié)點(diǎn)存放歸并后的單鏈表。表，設(shè)計(jì)算法去掉數(shù)值相同的元素，使表中不再有重復(fù)的元素。例如：8.試編寫在帶頭結(jié)點(diǎn)的單鏈表中刪除一個(gè)最小值結(jié)點(diǎn)的高效算法：voiddelete(Linklist&L)。9.已知兩個(gè)單鏈表A和B，其頭指針分別為heada和headb，編寫一個(gè)過程從單鏈表A中刪除自第i個(gè)元素起的共lenA插入到單鏈表B的第j個(gè)元素之前。10.已知非空線性表由list11.帶頭結(jié)點(diǎn)且頭指針為ha和hb的兩線性表A和B分別表示兩個(gè)集合，兩表中的元素皆為遞增有序。請(qǐng)寫一算法求A和B的并集AU元素仍保持遞增有序，且要利用A和B的原有結(jié)點(diǎn)空間。12.已知兩個(gè)鏈表A和B分別表示兩個(gè)集合，其元素遞增排列。編寫一函數(shù)程序，求A與B的交集，并存放于A鏈表中。13.設(shè)計(jì)一個(gè)求兩個(gè)集合A和B之差C=A-B的程序，即當(dāng)且僅當(dāng)e是A的一個(gè)元素，但不是B才是C中的一個(gè)元素。集合用有序鏈表實(shí)現(xiàn)，初始時(shí)，A、B集合中的元素按遞增排列，C為空；操作完成后，A、B保持不變，C中元素按遞增排列。下面的函數(shù)append（last，e）是把值為e的新結(jié)點(diǎn)鏈接在由指針last指向的結(jié)點(diǎn)的后面，并返回新結(jié)點(diǎn)的地址；在執(zhí)行A-B運(yùn)添加，當(dāng)A-B運(yùn)算執(zhí)行完畢后，再刪除并釋放表示結(jié)果集合的鏈表的表頭結(jié)點(diǎn)。typedefstructnode{intelement;structnode*link;}NODE;;NODE*A,*B,*C;NODE*append(NODE*last,inte){last->link=(NODE*)malloc(sizeof(NODE));last->link->element=e;return(last->link);}NODE*difference(NODE*A,NODE*B){………}14.設(shè)一單向鏈表的頭指針為key域，試設(shè)計(jì)算法，將此鏈表的記錄按照key遞增的次序進(jìn)行就地排序。15.設(shè)計(jì)算法將一個(gè)帶頭結(jié)點(diǎn)的單鏈表A分解為兩個(gè)具有相同結(jié)構(gòu)的鏈表B、C，其中B表的結(jié)點(diǎn)為A表中值小于零的結(jié)點(diǎn)，而C表的結(jié)點(diǎn)為A表中值大于等于零的結(jié)點(diǎn)（鏈表A的元素類型為整型，要求B、C表利用A16.將一個(gè)帶頭結(jié)點(diǎn)的單鏈表A分解為兩個(gè)帶頭結(jié)點(diǎn)的單鏈表A和AB保持其相對(duì)順序不變。1）寫出其類型定義。2）寫出算法。17.兩個(gè)整數(shù)序列A=a，a，a，…，a和B=b，b，b，…，b已經(jīng)存入兩2123m13n個(gè)單鏈表中，設(shè)計(jì)一個(gè)算法，判斷序列B是否是序列A的子序列。）按順序存于內(nèi)存，每個(gè)元素都是整數(shù)，312n0…,x）變?yōu)椋?x,-x,-x,coef，指數(shù)域exp和指針域next?，F(xiàn)對(duì)鏈表求一階導(dǎo)數(shù)，鏈表的頭指針為ha，頭結(jié)點(diǎn)的exp域?yàn)?1。20．設(shè)用帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表表示的線性表為L=（a，a,a,…,a312n寫出算法將L改造成：L=（a,a,…,a,…,a,a）.413n2結(jié)點(diǎn)和結(jié)點(diǎn)指針類型定義如下：typedefstructnode{ElemTypedata;Structnode*prior,next;}*DLinkList;21.設(shè)有一個(gè)頭指針為L的帶有表頭結(jié)點(diǎn)的非循環(huán)雙向鏈表，其每個(gè)結(jié)點(diǎn)中除有頻度域freq。在鏈表被起用前，其值均初始化為零。每當(dāng)在鏈表中進(jìn)行一次Locate（L，x）運(yùn)算時(shí)，令元素值為x的結(jié)點(diǎn)中freq域的值增1，并使此鏈表的Locate（L，x）運(yùn)算的算法，該運(yùn)算為函數(shù)過程，返回找到結(jié)點(diǎn)的地址，類型為指針型。第三章棧和隊(duì)列一．選擇題1.在一個(gè)具有ntop作為棧頂指針，則當(dāng)做退棧處理時(shí)，top變化為A．top不變B．top＝top-n。C．top＝top-1D．top=top+12.在一個(gè)順序存儲(chǔ)的循環(huán)隊(duì)列中，隊(duì)首指針指向隊(duì)首元素的A．前一個(gè)位置B．后一個(gè)位置C．隊(duì)首元素位置3.若進(jìn)棧序列為A．3,4,2,1B．2,4,3,1C．1,4,2,3。D．隊(duì)尾元素位置不可能是一個(gè)出棧序列。D．3,2,1,44.在具有n個(gè)單元的順序存儲(chǔ)的循環(huán)隊(duì)列中，假定front和rear分別為隊(duì)首指針和隊(duì)尾指針，則判斷隊(duì)空的條件是。=rear+1=rear=rear5.向一個(gè)棧項(xiàng)指針為hs的鏈棧中插入一個(gè)*s結(jié)點(diǎn)時(shí)，則執(zhí)行=0。A．hs->next=s;C．s->next=hs;hs=s;6.下列說法哪個(gè)正確：_______B．s->next=hs->next;hs->next=s;D．s->next=hs;hs=hs->next;A．堆棧是在兩端操作、先進(jìn)后出的線性表B．堆棧是在一端操作、先進(jìn)先出的線性表C．隊(duì)列是在一端操作、先進(jìn)先出的線性表D．隊(duì)列是在兩端操作、先進(jìn)先出的線性表7.棧和隊(duì)列的共同點(diǎn)_______A．都是先進(jìn)后出B．都是先進(jìn)先出C．只允許在端點(diǎn)處插入和刪除元素D．沒有共同點(diǎn)8.以下數(shù)據(jù)結(jié)構(gòu)中哪一個(gè)是非線性結(jié)構(gòu)？_______A．隊(duì)列B．棧C．線性表D．二叉樹9.若已知一個(gè)棧的入棧序列是，…，pn，若p1=n，則pi為_______A．iB．n=iC．n-i+1D．不確定10.當(dāng)利用大小為N的一維數(shù)組順序存儲(chǔ)一個(gè)棧時(shí)，假定用top==N表示?？眨瑒t向這個(gè)棧插入一個(gè)元素時(shí)，首先應(yīng)執(zhí)行_______語句修改top指針。A．top++11.4個(gè)元素進(jìn)S棧的順序是A,B,C,D,經(jīng)運(yùn)算POP(S)后棧頂元素是_______A．AB．BC．CD．D12.一個(gè)棧的輸入序列是a,b,c,d,e,則棧的不可能的輸出序列是_______B．top--C．top=0D．topA.edcbaB.decbaC.dceabD.abcde13．設(shè)用鏈表作為棧的存儲(chǔ)結(jié)構(gòu)則退棧操作_______。A．必須判別棧是否為滿C．判別棧元素的類型B．必須判別棧是否為空D．對(duì)棧不作任何判別14．設(shè)輸入序列是1、2、3、……、n，經(jīng)過棧的作用后輸出序列的第一個(gè)元素是n，則輸出序列中第i個(gè)輸出元素是_______。A．n-iB．n-1-iC．n+1-i15．遞歸函數(shù)f(n)=f(n-1)十n(n>1)的遞歸出口是_______。D．不能確定A．f(1)=016．中綴表達(dá)式A-(B+C／D)*E的后綴形式是_______。A．ABC+D／*E-B．ABCD／+E*-C．AB-C+D／E*B．f(1)=1C．f(0)=1D．f(n)=nD．ABC-+D/E*17.字符A、B、C、D依次進(jìn)入一個(gè)棧，按出棧的先后順序組成不同的字符串，至多可以組成_______個(gè)不同的字符串？A.15B.14C.16D.2118.字符A依次進(jìn)入一個(gè)棧，按出棧的先后順序組成不同的字符串，至多可以組成_______個(gè)不同的字符串？A.1419．判定一個(gè)循環(huán)隊(duì)列QU(最多元素為m0)為滿隊(duì)列的條件是_______A．QU->front==QU->rearB．QU->front!=QU->rearB.5C.6D.8C．QU->front==(QU->rear+1)％m0D．QU->front!=(QU->rear+1)％m020.以下哪一個(gè)不是隊(duì)列的基本運(yùn)算？_______A.在隊(duì)列第i個(gè)元素之后插入一個(gè)元素C.判斷一個(gè)隊(duì)列是否為空B.從隊(duì)頭刪除一個(gè)元素D.讀取隊(duì)頭元素的值21．設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素E1、E2、E3、E4、E5和E6依次通過棧S，一個(gè)元素出棧后即進(jìn)入隊(duì)列Q，若6個(gè)元素出列的順序?yàn)镋6、E5和E1，則棧S的容量至少應(yīng)該是_______。A．6B．4C．322.用鏈接方式存儲(chǔ)的隊(duì)列，在進(jìn)行插入運(yùn)算時(shí)_______。D．2A.僅修改頭指針C.僅修改尾指針B.頭、尾指針都要修改D.頭、尾指針可能都要修改23.若用一個(gè)大小為6rear和front的值分別為0和和front的值分別為_______？A.1和524．將一個(gè)遞歸算法改為對(duì)應(yīng)的非遞歸算法時(shí)，通常需要使用_______。A.棧B.隊(duì)列C.循環(huán)隊(duì)列D.優(yōu)先隊(duì)列B.2和4C.4和2D.5和125．在循環(huán)隊(duì)列中用數(shù)組A[0..m-1]存放隊(duì)列元素，其隊(duì)頭和隊(duì)尾指針分別為front和rear，則當(dāng)前隊(duì)列中的元素個(gè)數(shù)是_______。A.(front-rear+1)%mC．(front-rear+m)%m二．填空題B.(rear-front+1)%mD.(rear-front+m)%m1.棧和隊(duì)列分別稱為_____________的線性表。2.棧結(jié)構(gòu)允許進(jìn)行刪除操作的一端為_____________。3.向一個(gè)由HS指向的鏈棧中插入一個(gè)結(jié)點(diǎn)時(shí)p不空而且無需回收被刪除結(jié)點(diǎn)）。4.位置插入和刪除元素；對(duì)于棧只能在____________插入和刪除元素；對(duì)于隊(duì)列只能在________插入和_______刪除元素。5.棧是一種特殊的線性表，允許插入和刪除運(yùn)算的一端稱為___________。不允許插入和刪除運(yùn)算的一端稱為_____________。6.棧又稱為_______________表，隊(duì)列又稱為___________表。7.當(dāng)用長度為N滿的條件是_____________________。8.9.不論是順序存儲(chǔ)結(jié)構(gòu)的棧還是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的棧，其入棧和出棧操作的時(shí)間復(fù)雜度均為____________。10.(a+b)*c+(e*f-h)/(q+r)+3的后綴表達(dá)式為__________________________。11.后綴算式923+-102/-的值為__________。中綴算式（3+4X）-2Y/3對(duì)應(yīng)的后綴算式為_______________________________。三．判斷題1.棧是一種線性結(jié)構(gòu)。（）2.棧是一種對(duì)所有插入、刪除操作限于在表的一端進(jìn)行的線性表，是一種后進(jìn)先出型結(jié)構(gòu)。（）（）（）（）3.棧是一種插入和刪除操作在表的一端進(jìn)行的線性表。4.出棧序列為abcd，則入棧序列可能是bcda。5.一個(gè)棧的輸入序列是12345，則棧的輸出序列不可能是12345。6.兩個(gè)棧共享一片連續(xù)內(nèi)存空間時(shí)，為提高內(nèi)存利用率，減少溢出機(jī)會(huì)，應(yīng)把兩個(gè)棧的棧底分別設(shè)在這片內(nèi)存空間的兩端。（）7.不論是入隊(duì)列操作還是入棧操作，在順序存儲(chǔ)結(jié)構(gòu)上都需要考慮“溢出”情況。8.棧和隊(duì)列的存儲(chǔ)方式既可是順序方式，也可是鏈接方式。（）（）9.對(duì)于不同的使用者，一個(gè)表結(jié)構(gòu)既可以是棧，也可以是隊(duì)列，也可以是線性表。（）10.指針。（）（）11.高級(jí)語言中通常利用“遞歸工作?！眮硖幚磉f歸。四、簡(jiǎn)答題1.簡(jiǎn)述棧與隊(duì)列的相同點(diǎn)與不同點(diǎn)。隊(duì)列結(jié)構(gòu)？3.寫出下列程序段的輸出結(jié)果（棧的元素類型SElemType為char）。voidmain(){StackS;charx,y;InitStack(S);x=‘c’;y=‘k’;Push(S,x);Pop(S,x);Pop(S,x);Push(S,‘a(chǎn)’);Push(S,y);Push(S,‘t’);Push(S,x);Push(S,‘s’);while(!StackEmpty(S)){Pop(S,y);printf(y);}printf(x);}4.簡(jiǎn)述以下算法的功能（棧的元素類型SElemType為int）。(1)statusalgo1(StackS){inti,n,A[255];n=0;while(!StackEmpty(S)){n++;Pop(S,A[n]);}for(i=1;i<=n;i++)Push(S,A[i]);}(2)statusalgo2(StackS,inte){StackT;intd;InitStack(T);while(!StackEmpty(S)){Pop(S,d);if(d!=e)Push(T,d);}while(!StackEmpty(T)){Pop(T,d);Push(S,d);}}五．程序算法題1.設(shè)頭指針），試編寫相應(yīng)的入隊(duì)列、出隊(duì)列算法。2.設(shè)計(jì)一個(gè)輸出如下形式數(shù)值的遞歸算法。444433322pp1p3.試證明：若借助棧由輸入序列12…n得到的輸出序列為(它是輸入序n2列的一個(gè)排列)，則在輸出序列中不可能出現(xiàn)這樣的情形：存在著i<j<k使ppp<<。kij表達(dá)式求值時(shí)操作數(shù)棧和運(yùn)算符棧的變化過程：A-B×C/D+E↑F個(gè)函數(shù)decpair(exp,flag)；其中exp為表示算術(shù)表達(dá)式的字符串變量，flag用于返回是否匹配的結(jié)果。6.編寫一個(gè)算法，利用隊(duì)列的基本運(yùn)算返回指定隊(duì)列中的最后一個(gè)元素。7.如果用一個(gè)循環(huán)數(shù)組qu[0..m-1]表示隊(duì)列時(shí)，該隊(duì)列只設(shè)置一個(gè)頭指針0front，設(shè)置計(jì)數(shù)器count用以記錄隊(duì)列中的結(jié)點(diǎn)個(gè)數(shù)。要求：（1）編寫實(shí)現(xiàn)隊(duì)列的5個(gè)基本運(yùn)算；（2）隊(duì)列中能容納的元素最大個(gè)數(shù)為多少？8.假定用一個(gè)循環(huán)單鏈表表示隊(duì)列，該隊(duì)列只設(shè)置隊(duì)尾指針rear，編寫函數(shù)：（1）向循環(huán)鏈隊(duì)列中插入一個(gè)元素為x的結(jié)點(diǎn)；（2）從循環(huán)鏈隊(duì)列中刪除一個(gè)結(jié)點(diǎn)。第四章串一．選擇題1.如下陳述中正確的是________。A．串是一種特殊的線性表C．串中元素只能是字母2.字符串的長度是指________。A．串中不同字符的個(gè)數(shù)C．串中所含字符的個(gè)數(shù)B．串的長度必須大于零D．空串就是空白串B．串中不同字母的個(gè)數(shù)D．串中不同數(shù)字的個(gè)數(shù)3.兩個(gè)字符串相等的充要條件是________。A．兩個(gè)字符串的長度相等C．同時(shí)具備A和B兩個(gè)條件4.串是________。B．兩個(gè)字符串中對(duì)應(yīng)位置上的字符相等D．以上答案都不對(duì)A．不少于一個(gè)字母的序列C．不少于一個(gè)字符的序列B．任意個(gè)字母的序列D．有限個(gè)字符的序列5.下列關(guān)于串的敘述中，正確的是________。A．串長度是指串中不同字符的個(gè)數(shù)B．串是n個(gè)字母的有限序列C．如果兩個(gè)串含有相同的字符，則它們相等D．只有當(dāng)兩個(gè)串的長度相等，并且各個(gè)對(duì)應(yīng)位置的字符都相符時(shí)才相等6.串是一種特殊的線性表，其特殊性體現(xiàn)在________。A．可以順序存儲(chǔ)C．可以鏈接存儲(chǔ)7.設(shè)有兩個(gè)串p和q，求q在p中首次出現(xiàn)的位置的運(yùn)算稱作________。B．?dāng)?shù)據(jù)元素是一個(gè)字符D．?dāng)?shù)據(jù)元素可以是多個(gè)字符A．連接B．模式匹配C．求子串D．求串長8.設(shè)串s1="ABCDEFG",s2="PQRST",函數(shù)con(x,y)返回x和y串的連接串。s的從序號(hào)i的字符開始的j返回串s的長度，則的結(jié)果串是________。A．BCDEFB．BCDEFGC．BCPQRSTD.BCDEFEF9．函數(shù)substr("DATASTRUCTURE"，5，9)的返回值為________。B．"DATA"A．"STRUCTURE"C．"ASTRUCTUR"D."DATASTRUCTURE"10．設(shè)串S="IAMATEACHER",其長度是________。A.16B.11C.1411.設(shè)字符串s1="abcdefg",s2="pqrst"，則運(yùn)算s=concat(sub(s1,2,len(s2)),sub(s1,len(s2),2))后串值為________。A."bcdef"B."bcdefg"C."bcpqrst"D."bcdefef"1312.設(shè)有一個(gè)字符串S="windows"，求子串的數(shù)目是________。D.15A．25B．26C．27D.28二.填空題1._______________稱為空串；_______________________稱為空白串。2.一個(gè)串的任意個(gè)連續(xù)的字符組成的子序列稱為該串的______，包含該子串的串稱為____。三．簡(jiǎn)答題1．空串與空格串有什么區(qū)別？字符串中的空格有什么意思？空串在串的處理中有什么作用？2．串是由字符組成的，長度為1的串和字符是否相同？為什么？3．簡(jiǎn)述串的靜態(tài)順序存儲(chǔ)結(jié)構(gòu)與動(dòng)態(tài)順序存儲(chǔ)結(jié)構(gòu)有什么區(qū)別，分別寫出它們的結(jié)構(gòu)體定義。4．字符串采用靜態(tài)順序存儲(chǔ)結(jié)構(gòu)。編寫一個(gè)算法刪除S中第i個(gè)字符到第j個(gè)字符。5．編寫一個(gè)算法判斷s2是否是s1的子串。6.下列程序段的功能實(shí)現(xiàn)子串t在主串s中位置的算法，要求在下劃線處填上正確語句。intindex(chars[],chart[]){inti=0,j=0;while(i<strlen(s)&&j<strlen(t))if(s[i]==t[j]){i=i+l;j=j+l;}else{i=_______;j=______;}if(j==strlen(t))return(i-strlen(t));elsereturn(-1);}第五章數(shù)組和廣義表一．選擇題1．在二維數(shù)組A中引用A[i,j]的時(shí)間_________。A．與i、j的大小有關(guān)B．與i、j的大小無關(guān)C．與i的大小有關(guān)，與j的大小無關(guān)D．與i的大小無關(guān)，與j的大小有關(guān)2．在稀疏矩陣的帶行指針向量的鏈接存儲(chǔ)中，每一行單鏈表中的結(jié)點(diǎn)都具有相同的________。A．行號(hào)B．列號(hào)C．元素值D.地址3．二維數(shù)組A按行順序存儲(chǔ)，其中每個(gè)元素占1個(gè)存儲(chǔ)單元。若A[1][1]的存儲(chǔ)地址為420，A[3][3]的存儲(chǔ)地址為446，則A[5][5]的存儲(chǔ)地址為_______。A．4704．在稀疏矩陣的十字鏈接存儲(chǔ)中，每個(gè)列單鏈表中的結(jié)點(diǎn)都具有相同的_____。A．行號(hào)B．列號(hào)C．元素值D.地址5．下面的說法中，不正確的是________。B．471C．472D.473A．對(duì)稱矩陣中只須存放包括主對(duì)角線元素在內(nèi)的下(或上)三角部分的元素即可B．對(duì)角矩陣中只須存放的非零元素即可C．稀疏矩陣中值為零的元素較多，因此可以采用三元組表方法存儲(chǔ)D．稀疏矩陣中大量值為零的元素分布有規(guī)律，因此可以采用三元組表方法存儲(chǔ)6．對(duì)一些特殊矩陣采用壓縮存儲(chǔ)的目的主要是為了________。A．表達(dá)變得簡(jiǎn)單B．對(duì)矩陣元素的存取變得簡(jiǎn)單D．減少不必要的存儲(chǔ)空間的開銷C．去掉矩陣中的多余元素7．若將n階對(duì)稱矩陣A按照行序?yàn)橹餍蚍绞綄ㄖ鲗?duì)角線元素在內(nèi)的下三角形的所有元素依次存放在一個(gè)一維數(shù)組B中，則該對(duì)稱矩陣在B中占用了________個(gè)數(shù)組元素。A．n28.稀疏矩陣的三元組順序表表示的一個(gè)三元組中不包括________。A.行號(hào)B.列號(hào)C.元素值D.元素總數(shù)9．稀疏矩陣一般的壓縮存儲(chǔ)方法有兩種，即________。B．n*(n-1)C．n*(n+1)／2D．n*(n-1)A．二維數(shù)組和三維數(shù)組C.三元組和十字鏈表B．三元組和散列D．散列和十字鏈表10．有一個(gè)10階對(duì)稱矩陣A，采用壓縮存儲(chǔ)方式(以行序?yàn)橹鞔鎯?chǔ)，且A[0Ⅱ0]=1)，則A[8][5]的地址是________。A．5211.數(shù)組通常具有的兩種基本操作是________。A．建立與刪除B．索引和修改C．查找和修改B．48C．54D．53D．查找與索引12．二維數(shù)組M的成員是6個(gè)字符(每個(gè)字符占一個(gè)存儲(chǔ)單元)組成的串，行下標(biāo)i的范圍從0到j(luò)的范圍從1到M至少需要________個(gè)字節(jié)。A．90B．180C．240D．54013．二維數(shù)組M的元素是4個(gè)字符(每個(gè)字符占一個(gè)存儲(chǔ)單元)組成的串，行下標(biāo)i的范圍從0到4j的范圍從0到5,M按行存儲(chǔ)時(shí)元素M[3Ⅱ5]的起始地址與M按列存儲(chǔ)時(shí)元素________的起始地址相同。A．M[2][4]B．M[3][4]C．M[3][5]D.M[4][4]14．下面的說法中，不正確的是________。A．?dāng)?shù)組是一種線性表結(jié)構(gòu)B．?dāng)?shù)組是一種定長的線性表結(jié)構(gòu)，C．除了插入與刪除操作外，數(shù)組的基本操作還有存取、修改、檢索和排序等D．?dāng)?shù)組的基本操作有存取、修改、檢索和排序等，沒有插入與刪除操作15．?dāng)?shù)組的邏輯結(jié)構(gòu)不同于下列________的邏輯結(jié)構(gòu)。A．線性表B．棧C．隊(duì)列D.樹16．設(shè)有一個(gè)10階的下三角矩陣順序存儲(chǔ)到連續(xù)的55個(gè)存儲(chǔ)單元中，每個(gè)數(shù)組元素占1個(gè)字節(jié)的存儲(chǔ)空間，則A[5][4]地址與A[0][0]的地址之差為________。A．10B．19C．28D.5517．將10階對(duì)稱矩陣壓縮存儲(chǔ)到一維數(shù)組A中，則數(shù)組A的長度最少為________。A．100B．40C．55D.80A一維數(shù)組B[1，n(n+1)/2]中。下三角部分中任一元素A(i>=j),在一維數(shù)組Bij中的下標(biāo)位置是________。A．i(i-1)/2+j-1C．i(i+1)/2+j-1B．i(i-1)/2+jD.i(i+1)/2+j19.三維數(shù)組2個(gè)存A[3][4][5]的存儲(chǔ)地址為________。A．356B．358C．36020.二維數(shù)組Amn按行序?yàn)橹餍虼娣旁趦?nèi),每個(gè)數(shù)組元素占1個(gè)存儲(chǔ)單元,D.362則元素A的地址計(jì)算公式是:________。ijA．loc(A)=loc(A)+[(i-1)*m+(j-1)]ij11B．loc(A)=loc(A)+[(j-1)*m+(i-1)]ij11C．loc(A)=loc(A)+[(i-1)*n+(j-1)]ij11D.loc(A)=loc(A)+[(j-1)*n+(i-1)]ij1121.廣義表(a,b,c,d)的表頭是________。.A．a(chǎn)B．(a)C．a(chǎn),b,c22.若廣義表K滿足head(K)=tail(K),則K為________。A.()B.(())C.(()),(())D.((),(),())D.(a,b,c)23.設(shè)一個(gè)廣義表中結(jié)點(diǎn)的個(gè)數(shù)為n,則廣義表深度算法的時(shí)間復(fù)雜度為________。A.O(1)B.O(n)C.O(n)2D.O(logn)224.下列廣義表中，深度為2的有________。A.(a，b)B.((c，(a，b))，d)C.(c，(a，b))D.((a，b)，(c，(a，b)))25.廣義表A=(a,b,(c,d),(e,(f,g)))，則Head(Tail(Head(Tail(Tail(A)))))的值為________。A.(g)B.(d)C.cD.d二.填空題1.設(shè)有一個(gè)n階的下三角矩陣n(n+1)/2A[i][j]與A[0][0]之間有_______個(gè)數(shù)據(jù)元素。AA的長度為3i從1到j(luò)從1到10，從首地址100開始連續(xù)存放在存儲(chǔ)器內(nèi)，該數(shù)組若按行主序存放時(shí)，元素A[8][5]的起始地址為A[8][5]的起始地址為__________。3.假設(shè)有二維數(shù)組A[6][8]，每個(gè)元素用相鄰的6個(gè)字節(jié)存儲(chǔ)，存儲(chǔ)器按字節(jié)編址。已知A的起始存儲(chǔ)位置（基地址）為1000，則數(shù)組A的體積（存儲(chǔ)量）為________；末尾元素A的第一個(gè)字節(jié)地址為________；若按行存儲(chǔ)時(shí)，元57素A的第一個(gè)字節(jié)地址為_________；若按列存儲(chǔ)時(shí)，元素A的第一個(gè)字節(jié)14地址為__________。474.若一個(gè)n階矩陣A=A(0<=i,j<=n-1)則稱A為________jiij矩陣；若主對(duì)角線上方(或下方)的所有元素均為零時(shí)，稱該矩陣為__________。5.已知廣義表A=((a,b,c),(d,e,f)),則運(yùn)算head(head(tail(A)))=________。6.一個(gè)廣義表中的元素分為________元素和________元素兩類。7.稀疏矩陣中第2行3列的元素值是5，它的三元組是________。8.在稀疏矩陣所對(duì)應(yīng)的三元組線性表中，每個(gè)三元組元素按_________為主序、_________為輔序的次序排列。9.廣義表A=(a,(a,b),((a,b),c)),則它的深度為____________，它的長度為____________。10．設(shè)一個(gè)廣義表中結(jié)點(diǎn)的個(gè)數(shù)為n，則求廣義表深度算法的時(shí)間復(fù)雜度為____________。11．設(shè)一個(gè)具有t個(gè)非零元素的m*n大小的稀疏矩陣采用順序存儲(chǔ)，求其轉(zhuǎn)置矩陣的普通轉(zhuǎn)置算法的時(shí)間復(fù)雜度為___________。________優(yōu)先存儲(chǔ)。13.設(shè)廣義表L的長度是________；L的深度是________。14.設(shè)廣義表head(L)是______；tail(L)是___。三.判斷題1.在C）））4.已知廣義表A=((a,b,c),(d,e,f)),從A中取出原子e的運(yùn)算是head(tail(head(tail(A))))。（）5.）6.數(shù)組是一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，數(shù)組元素之間的關(guān)系既不是線性的也不是樹形）7.）8.）9.稀疏矩陣的壓縮存儲(chǔ)可以用一個(gè)三元組表來表示稀疏矩陣中的非0元素。（）10.）四.簡(jiǎn)答題1．什么叫二維數(shù)組的行序優(yōu)先存儲(chǔ)？什么叫二維數(shù)組的列序優(yōu)先存儲(chǔ)？2．什么樣的矩陣叫特殊矩陣？特殊矩陣壓縮存儲(chǔ)的基本思想是什么？3．什么樣的矩陣叫稀疏矩陣？稀疏矩陣壓縮存儲(chǔ)的基本思想是什么？4．已知稀疏矩陣如下：請(qǐng)寫出該稀疏矩陣三元組表示。5.請(qǐng)寫出下面鏈表表示的廣義表。6.畫出廣義表list=(5,(3,2,(14,9,3),(),4),2,(6,3,10))的鏈表表示。五.程序設(shè)計(jì)題1.設(shè)計(jì)一個(gè)算法求廣義表的深度。（1）求數(shù)組A靠邊元素之和；C.n+1A．207.一棵具有5層滿二叉樹中結(jié)點(diǎn)總數(shù)為________。A．31B.32C.3310.把一棵深度4的左單支二叉樹改造成完全二叉樹時(shí)，要增添A．10B．8C．6D．4個(gè)空結(jié)點(diǎn)。1編號(hào)為i結(jié)點(diǎn)的左孩子結(jié)點(diǎn)的編號(hào)為________。A．2i+1B.2iC.i/2D.2i-112.首先訪問結(jié)點(diǎn)的左子樹，然后訪問該結(jié)點(diǎn)，最后訪問結(jié)點(diǎn)的右子樹，這種遍歷稱為________。A.前序遍歷B.后序遍歷C.中序遍歷D.層次遍歷13.已知一棵二叉樹的前序遍歷結(jié)果為ABCDEF序遍歷的結(jié)果為________。A．CBEFDAB.FEDCBAC.CBEDFAD.不定14.已知某二叉樹的后序遍歷序列是dabec,中序遍歷序列是debac,它的前序遍歷序列是________。A．a(chǎn)cbedB．decabC．deabcD．cedba15.某二叉樹T有n個(gè)結(jié)點(diǎn)，設(shè)按某種遍歷順序?qū)中的每個(gè)結(jié)點(diǎn)進(jìn)行編號(hào)，編號(hào)值為1,2,…,n中任一結(jié)點(diǎn)號(hào)減1，而V的右子樹的結(jié)點(diǎn)中，其最小編號(hào)等于V左子樹上結(jié)點(diǎn)的最大編號(hào)加1。這時(shí)按編號(hào)。A.中序遍歷序列B.前序遍歷序列C.后序遍歷序列D.層次遍歷序列16.某非空二叉樹的前序序列和后序序列正好相反，則二叉樹一定是________的二叉樹。A.空或只有一個(gè)結(jié)點(diǎn)C.任一結(jié)點(diǎn)無左孩子B.高度等于其結(jié)點(diǎn)數(shù)D.任一結(jié)點(diǎn)無右孩子17.由前序序列和中序序列________唯一確定一棵二叉樹。A．能B.不能C.不一定18.樹的基本遍歷策略可分為先根遍歷和后根遍歷；二叉樹的基本遍歷策略可分棵樹對(duì)應(yīng)的二叉樹。下面結(jié)論正確的是________。A．樹的先根遍歷序列與其對(duì)應(yīng)的二叉樹的先序遍歷序列相同B．樹的后根遍歷序列與其對(duì)應(yīng)的二叉樹的后序遍歷序列相同C.樹的先根遍歷序列與其對(duì)應(yīng)的二叉樹的中序遍歷序列相同D．以上都不對(duì)19.對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹，對(duì)應(yīng)二叉鏈表中指針總數(shù)為2n個(gè)，其中________個(gè)用于指向孩子結(jié)點(diǎn)。A．n-1B.nC.n+1D.n-220.設(shè)F是由和T3F對(duì)應(yīng)的二叉樹為和T3的結(jié)點(diǎn)數(shù)分別為N1、N2和N3，則二叉樹B的根結(jié)點(diǎn)的左子樹的結(jié)點(diǎn)數(shù)為________。A．N1-1B.N2-1C.N2+N3D.N1+N321.由分別帶權(quán)為9、2、5、7的四個(gè)葉子結(jié)點(diǎn)構(gòu)造一棵哈夫曼樹，該樹的帶權(quán)路徑長度為__A.23___。B.37C.44D.4622.n個(gè)權(quán)構(gòu)成一棵Huffman樹，其結(jié)點(diǎn)總數(shù)為__________。A．2n-1B.2nC.2n+1D.不確定二、填空題1.在一棵二叉樹中，度為0的結(jié)點(diǎn)的個(gè)數(shù)為n，度為2的結(jié)點(diǎn)的個(gè)數(shù)為n，20則：n=0。2．結(jié)點(diǎn)數(shù)為7的二叉樹的高度最矮是_______，最高是_______。3．給定二叉樹的結(jié)點(diǎn)數(shù)，要使樹高為最大，那么該樹應(yīng)該是_______形狀。4．給定二叉樹的結(jié)點(diǎn)數(shù)，要使樹高為最矮，那么該樹應(yīng)該是_______形狀。5．如果一棵滿二叉樹的深度為7_______個(gè)葉結(jié)點(diǎn)。6．深度為5的二叉樹，至多有_______個(gè)結(jié)點(diǎn)。7．深度為k的完全二叉樹至少有_______個(gè)結(jié)點(diǎn)，至多有_______個(gè)結(jié)點(diǎn)。8．在樹形結(jié)構(gòu)中，樹根結(jié)點(diǎn)沒有前驅(qū)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有_______個(gè)9.設(shè)二叉樹中度數(shù)為0的結(jié)點(diǎn)數(shù)為1的結(jié)點(diǎn)數(shù)為總共有_______個(gè)結(jié)點(diǎn)。10.設(shè)二叉樹中結(jié)點(diǎn)的兩個(gè)指針域分別為lchild和rchild，則判斷指針變量p所指向的結(jié)點(diǎn)為葉子結(jié)點(diǎn)的條件是___________________________。11.在n個(gè)帶權(quán)葉子結(jié)點(diǎn)構(gòu)造出的所有二叉樹中，帶權(quán)路徑長度最小的二叉樹稱為________。12.設(shè)一棵完全二叉樹中有21個(gè)結(jié)點(diǎn)，如果按照從上到下、從左到右的順序從188的左孩子結(jié)點(diǎn)的編號(hào)是_______。13.設(shè)哈夫曼樹中共有n個(gè)結(jié)點(diǎn)，則該哈夫曼樹中有_____個(gè)度數(shù)為1的結(jié)點(diǎn)。14.Huffman樹為____，其帶權(quán)路徑長度為_________。15.設(shè)一棵Huffman樹有6個(gè)葉結(jié)點(diǎn)，權(quán)值分別為結(jié)點(diǎn)的權(quán)值是_______。16.設(shè)用于通信的電文僅由8個(gè)字母組成，字母在電文中出現(xiàn)的頻率分別為7、19、2、6、32、3、21、10，根據(jù)這些頻率作為權(quán)值構(gòu)造哈夫曼樹，則這棵哈夫曼樹的高度為_________。三、綜合應(yīng)用題1.這棵樹并回答下面問題：（1）樹的根節(jié)點(diǎn)是哪個(gè)，哪些是葉子結(jié)點(diǎn)，哪些是非終端結(jié)點(diǎn)。（2）樹的深度是多少，各個(gè)結(jié)點(diǎn)的層數(shù)是多少。（3）對(duì)于G結(jié)點(diǎn)，它的雙親結(jié)點(diǎn)、祖先結(jié)點(diǎn)、孩子結(jié)點(diǎn)、子孫結(jié)點(diǎn)、兄弟和堂兄弟分別是哪些結(jié)點(diǎn)。2.設(shè)二叉樹如下圖所示，分別寫出它的先序遍歷、中序遍歷、后序遍歷序列。ABECFGDHJI3.設(shè)一棵二叉樹的先序遍歷序列為abcde，中序遍歷序列為badce，請(qǐng)畫出對(duì)應(yīng)的二叉樹，并寫出對(duì)應(yīng)后序遍歷序列。4.某二叉樹結(jié)點(diǎn)的中序序列為HBCDEFG，后序序列為BDCHFGE，請(qǐng)據(jù)此畫出該二叉樹，再給該樹加上中序線索。5.請(qǐng)按照孩子-兄弟表示法，將下圖所示樹轉(zhuǎn)化為二叉樹。ABCDEFG6.若7個(gè)帶權(quán)結(jié)點(diǎn)，其權(quán)值分別為WPL及該樹的結(jié)點(diǎn)總數(shù)。7.在一段文字中，共出現(xiàn)a、b、c、d、e、f六種字符，每種字符出現(xiàn)的頻率分別為7,9,12,22,23,27。請(qǐng)回答下列問題：（1）什么是哈夫曼樹？（2）根據(jù)題目所給頻率值，畫出相應(yīng)的哈夫曼樹。（3）給出各個(gè)字符對(duì)應(yīng)的哈夫曼編碼。（4）該段文字經(jīng)過哈夫曼編碼后，長度是多少。四、算法設(shè)計(jì)題1.設(shè)計(jì)一個(gè)求結(jié)點(diǎn)x在二叉樹中的雙親結(jié)點(diǎn)的算法。2.設(shè)計(jì)判斷兩個(gè)二叉樹是否相同的算法。3.設(shè)計(jì)計(jì)算二叉樹中所有結(jié)點(diǎn)值之和的算法。4.設(shè)計(jì)求二叉樹中值為x的結(jié)點(diǎn)所在的層號(hào)的算法。第七章圖一．選擇題1．任何一個(gè)無向連通圖的最小生成樹________。A．只有一棵B．有一棵或多棵D．可能不存在C．一定有多棵2．下列算法中，________算法用來求圖中每對(duì)頂點(diǎn)之間的最短路徑。A．DijkstraB．FloyedC．PrimD．Kruskal3．由N個(gè)頂點(diǎn)組成的有向圖，最多可以有________條邊。A．N*NB．N（N+1）C．N（N-1）D．N(N-1)/24．關(guān)鍵路徑是結(jié)點(diǎn)網(wǎng)絡(luò)中________。A.從源點(diǎn)到匯點(diǎn)的最長路徑B.從源點(diǎn)到匯點(diǎn)的最短路徑C.最長的回路D.最短的回路5．在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的________倍。A．2B．3C．1D．1.56.下面關(guān)于圖的存儲(chǔ)的敘述中正確的是________。A．用鄰接表法存儲(chǔ)圖，占用的存儲(chǔ)空間大小只與圖中邊數(shù)有關(guān)，而與結(jié)點(diǎn)個(gè)數(shù)無關(guān)B．用鄰接表法存儲(chǔ)圖，占用的存儲(chǔ)空間大小與圖中邊數(shù)和結(jié)點(diǎn)個(gè)數(shù)都有關(guān)C.用鄰接矩陣法存儲(chǔ)圖，占用的存儲(chǔ)空間大小與圖中結(jié)點(diǎn)個(gè)數(shù)和邊數(shù)都有關(guān)D．用鄰接矩陣法存儲(chǔ)圖，占用的存儲(chǔ)空間大小只與圖中邊數(shù)有關(guān)，而與結(jié)點(diǎn)個(gè)數(shù)無關(guān)7.AOV網(wǎng)是一種________。A．有向圖B．無向圖C．無向無環(huán)圖D．有向無環(huán)圖8.在一個(gè)具有nn(n-1)/2n個(gè)頂點(diǎn)的有向完全圖中，包含有________條邊。A．n+29.設(shè)完全無向圖中有n個(gè)頂點(diǎn)，則該完全無向圖中有________條邊。A．n(n-1)/2B．n(n-1)C．n(n+1)/2D．(n-1)/2B．n(n-1)C．n2D．2n10.設(shè)有向無環(huán)圖G中的有向邊集合則下列屬于該有向圖G的一種拓?fù)渑判蛐蛄械氖莀_______。A．1，2，3，4C．1，4，2，3B．2，3，4，1D．1，2，4，311.設(shè)某無向圖有n個(gè)頂點(diǎn)，則該無向圖的鄰接表中有________個(gè)表頭結(jié)點(diǎn)。A．2nB．nC．n/2D．n(n-1)12.設(shè)無向圖G中有n個(gè)頂點(diǎn)，則該無向圖的最小生成樹上有________條邊。A．nB．n-1C．2nD．2n-113.設(shè)無向圖G中的邊的集合E={(a，(d，f)，(f，c)}，則從頂點(diǎn)a出發(fā)進(jìn)行深度優(yōu)先遍歷可以得到的一種頂點(diǎn)序列為________。A．a(chǎn)edfcbB．a(chǎn)cfebdC．a(chǎn)ebcfdD．a(chǎn)edfbc14.有n個(gè)頂點(diǎn)e條邊的無向圖G,它的鄰接表中的表結(jié)點(diǎn)總數(shù)是________。A．2nB．nC．2eD．e15.連通圖G中有n個(gè)頂點(diǎn),G的生成樹是________連通子圖。A．包含G的所有頂點(diǎn)B．包含G的所有邊C．不必包含G的所有頂點(diǎn)D．必須包含G的所有頂點(diǎn)和所有的邊16.下面關(guān)于求關(guān)鍵路徑的說法不正確的是________。A．求關(guān)鍵路徑是以拓?fù)渑判驗(yàn)榛A(chǔ)的B．一個(gè)事件的最早開始時(shí)間同以該事件為尾的弧的活動(dòng)最早開始時(shí)間相同C．一個(gè)事件的最遲開始時(shí)間同以該事件為尾的弧的活動(dòng)最遲開始時(shí)間相同與該活動(dòng)的持續(xù)時(shí)間的和D．關(guān)鍵活動(dòng)一定在關(guān)鍵路徑上17．設(shè)某強(qiáng)連通圖中有n個(gè)頂點(diǎn)，則該強(qiáng)連通圖中至少有________條邊。A．n(n-1)B．n+1C．nD．n(n+1)18．設(shè)某無向圖中有n個(gè)頂點(diǎn)e條邊，則該無向圖中所有頂點(diǎn)的入度之和為________。A．nB．eC．2nD．2e19.設(shè)某有向圖的鄰接表中有n個(gè)表頭結(jié)點(diǎn)和m條有向邊。A．nB．n-1C．mD．m-120．設(shè)用鄰接矩陣A表示有向圖G的存儲(chǔ)結(jié)構(gòu)，則有向圖G中頂點(diǎn)i的入度為________。A．第i行非0元素的個(gè)數(shù)之和C．第i行0元素的個(gè)數(shù)之和B．第i列非0元素的個(gè)數(shù)之和D．第i列0元素的個(gè)數(shù)之和21．設(shè)某無向圖中有n個(gè)頂點(diǎn)e條邊，則建立該圖鄰接表的時(shí)間復(fù)雜度為________。A．O(n+e)22．采用鄰接表存儲(chǔ)的圖的寬度優(yōu)先遍歷算法類似于二叉樹的________。A．先序遍歷B．中序遍歷C．后序遍歷D．按層遍歷23.可以判斷一個(gè)有向圖中是否含有環(huán)（回路）的方法為________。A．廣度優(yōu)先遍歷B．拓?fù)渑判駽．求最短路徑D．求關(guān)鍵路徑24.采用鄰接表存儲(chǔ)的圖的深度優(yōu)先遍歷算法類似于二叉樹的________。A．先序遍歷B．中序遍歷C．后序遍歷D．按層遍歷B．O(n)C．O(ne)D．O(n)225.一個(gè)具有8的差為________。A．16B．8C．026．在有向圖中每個(gè)頂點(diǎn)的度等于該頂點(diǎn)的________。D．2A.入度B.出度C.入度與出度之和D.入度與出度之差二．填空題1.在圖G于該頂點(diǎn)的________，對(duì)于有向圖來說等于該頂點(diǎn)的________。A出發(fā)按深度優(yōu)先搜索遍歷得到的頂點(diǎn)序列為________，按廣度優(yōu)先搜索遍歷得到的頂點(diǎn)序列為________。ABCDEF┏011010┓A┃100011┃B┃100100┃C┃001001┃D┃110001┃E┗010110┛F3.有n個(gè)頂點(diǎn)的有向連通圖最多有________條邊，最少有________條邊。4.具有n個(gè)頂點(diǎn)的完全無向圖有________條邊，完全有向圖有________條邊。5.設(shè)無向圖G中有n個(gè)頂點(diǎn)e條邊，所有頂點(diǎn)的度數(shù)之和為m，則e和m有______關(guān)系。6.設(shè)一個(gè)連通圖G中有n個(gè)頂點(diǎn)e7.表示圖的五種常用的存儲(chǔ)結(jié)構(gòu)為_______________________________。8.在有12個(gè)結(jié)點(diǎn)的無向圖中，其邊數(shù)最多為________條。9.設(shè)無向圖G中有n個(gè)頂點(diǎn)和e頭結(jié)點(diǎn)和_________個(gè)邊結(jié)點(diǎn)。10.n個(gè)頂點(diǎn)的連通圖至少____條邊。11.在無權(quán)圖G的鄰接矩陣A中，若(vi,vj)或＜vi,vj＞屬于圖G的邊集合，則對(duì)應(yīng)元素A[i][j]等于____，否則等于____。12.在無向圖G的鄰接矩陣A中，若A[i][j]等于1，則A[j][i]等于____。13.已知一個(gè)有向圖的鄰接矩陣表示，計(jì)算第i個(gè)結(jié)點(diǎn)的入度的方法是____。14.在一個(gè)具有10n個(gè)頂點(diǎn)的有向完全圖中，包含有________條邊。15.設(shè)無向圖G中有n個(gè)頂點(diǎn)，則該無向圖中每個(gè)頂點(diǎn)的度數(shù)最多是_________。16.對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e所含邊結(jié)點(diǎn)分別有_______個(gè)和________個(gè)。17.設(shè)某無向圖G中有n個(gè)頂點(diǎn)，用鄰接矩陣A作為該圖的存儲(chǔ)結(jié)構(gòu)，則頂點(diǎn)i和頂點(diǎn)j互為鄰接點(diǎn)的條件是______________________。18.設(shè)無向圖對(duì)應(yīng)的鄰接矩陣為A中第i行上非0元素的個(gè)數(shù)_________第i列上非019.設(shè)有向圖G用鄰接矩陣A[n][n]作為存儲(chǔ)結(jié)構(gòu)，則該鄰接矩陣中第i行上所有元素之和等于頂點(diǎn)i的________，第i列上所有元素之和等于頂點(diǎn)i的________。20.在圖的鄰接表中用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)表頭結(jié)點(diǎn)的優(yōu)點(diǎn)是____________________。21.設(shè)無向圖G中有n個(gè)頂點(diǎn)e度優(yōu)先或廣度優(yōu)先遍歷時(shí)的時(shí)間復(fù)雜度為_________；用鄰接表作為圖的存儲(chǔ)結(jié)構(gòu)進(jìn)行深度優(yōu)先或廣度優(yōu)先遍歷的時(shí)間復(fù)雜度為_________。22.設(shè)某無向圖G的鄰接表為V1->3->2->4;V2->1->3;V3->1->2->4;V4->1->3;則從頂點(diǎn)V1開始的深度優(yōu)先遍歷序列為___________；廣度優(yōu)先遍歷序列為____________。23.設(shè)有向圖G的二元組形式表示為G序列__________。24.AOV網(wǎng)以結(jié)點(diǎn)和有向邊分別代表____________25.AOV網(wǎng)是一種___________________的圖。三、判斷題1.如果某個(gè)有向圖的鄰接表中第i條單鏈表為空，則第i個(gè)頂點(diǎn)的出度為零。（）2.）3.用鄰接矩陣作為圖的存儲(chǔ)結(jié)構(gòu)時(shí)，則其所占用的存儲(chǔ)空間與圖中頂點(diǎn)數(shù)無關(guān)）4.）5.存儲(chǔ)圖的鄰接矩陣中，鄰接矩陣的大小不但與圖的頂點(diǎn)個(gè)數(shù)有關(guān)，而且與圖）6.n個(gè)結(jié)點(diǎn)的有向圖，若它有）7.））9.圖的深度優(yōu)先遍歷算法中需要設(shè)置一個(gè)標(biāo)志數(shù)組，以便區(qū)分圖中的每個(gè)頂點(diǎn)）10.）11.在AOV-網(wǎng)中，不應(yīng)該出現(xiàn)有向環(huán)，因?yàn)榇嬖诃h(huán)就意味著活動(dòng)可以以自己為）四．簡(jiǎn)答題1．對(duì)于一個(gè)有向圖，不用拓?fù)渑判?，如何判定圖中是否存在環(huán)？2．關(guān)？3.無向圖給出該圖的最小生成樹。6.一個(gè)網(wǎng)絡(luò)如下（2）求出它的一棵最小生成樹并畫出求解過程。7.已知一個(gè)無向圖的頂點(diǎn)集為{a,b,c,d,e},其鄰接矩陣如下所示（1）畫出該圖的圖形；（1）試畫出該網(wǎng)。五．算法設(shè)計(jì)題第八章查找A．n/2,nB．(n+1)/2，n-1C．(n+1)/2，nD．(n-1)/2，n-1C．13.4A．散列存儲(chǔ)C．壓縮存儲(chǔ)B．順序存儲(chǔ)或鏈接存儲(chǔ)D．索引存儲(chǔ)A．結(jié)點(diǎn)的輸入順序C.結(jié)點(diǎn)的取值范圍B．結(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu)D．計(jì)算機(jī)的硬件18．對(duì)包含n個(gè)元素的散列表進(jìn)行查找，平均查找長度________。A.O(logn)B.O(n)C.不直接依賴于nD.上述三者都不是219.設(shè)散列表中有m個(gè)存儲(chǔ)單元，散列函數(shù)H(key)=key%p，則p最好選擇________。A．小于等于m的最大奇數(shù)C．小于等于m的最大偶數(shù)B．小于等于m的最大素?cái)?shù)D．小于等于m的最大合數(shù)20．設(shè)某散列表的長度為100，散列函數(shù)H(k)=k%P，則P通常情況下最好選擇________。A．99B．97C．91D．9321.設(shè)有n個(gè)關(guān)鍵字具有相同的Hash函數(shù)值，則用線性探測(cè)法把這n個(gè)關(guān)鍵字映射到HASH表中需要做________次線性探測(cè)。A．n2B．n(n+1)C．n(n+1)/2D．n(n-1)/222.采用開放定址法處理散列表的沖突時(shí)，其平均查找長度________。A．低于鏈接法處理沖突B.高于鏈接法處理沖突C．與鏈接法處理沖突相同D．高于二分查找23.散列法存儲(chǔ)的基本思想是根據(jù)A來決定B，碰撞（沖突）指的是C，處理碰撞的兩類主要方法是D。供選擇的答案：A，B：①存儲(chǔ)地址②元素的符號(hào)③元素個(gè)數(shù)④關(guān)鍵碼值⑤非碼屬性⑥平均檢索長度⑦負(fù)載因子⑧散列表空間C:①兩個(gè)元素具有相同序號(hào)②兩個(gè)元素的關(guān)鍵碼值不同，而非碼屬性相同③不同關(guān)鍵碼值對(duì)應(yīng)到相同的存儲(chǔ)地址④負(fù)載因子過大⑤數(shù)據(jù)元素過多D：①線性探查法和雙散列函數(shù)法②建溢出區(qū)法和不建溢出區(qū)法③除余法和折疊法④拉鏈法和開地址法24._____是HASH查找的沖突處理方法。A．求余法25.當(dāng)αA.較慢B.較快C.相同B．平方取中法C．二分法D．開放地址法序查找，但前者比后者的查找速度________。A．必定快C．在大部分情況下要快B．不一定D．取決于表遞增還是遞減27.當(dāng)采用分塊查找時(shí)，數(shù)據(jù)的組織方式為________。A．?dāng)?shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)有序B．?dāng)?shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)不必有序，但塊間必須有序C．?dāng)?shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)有序，每塊內(nèi)最大（或最?。┑臄?shù)據(jù)組成索引塊D．?dāng)?shù)據(jù)分成若干塊，每塊（除最后一塊外）中數(shù)據(jù)個(gè)數(shù)需相同28．對(duì)二叉排序樹進(jìn)行_________遍歷，可以得到該二叉樹所有結(jié)點(diǎn)構(gòu)成的有序序列。A．前序B．中序C．后序D．按層次29．一個(gè)哈希函數(shù)被認(rèn)為是“好的”，如果它滿足條件_________。A．哈希地址分布均勻B．保證不產(chǎn)生沖突C．所有哈希地址在表長范圍內(nèi)D．滿足B和C30.哈希表的平均查找長度是__________的函數(shù)。B．表中元素的多少A．哈希表的長度C．哈希函數(shù)D．哈希表的裝滿程度31.平均查找長度最短的查找方法是____________。A．折半查找B．順序查找C．哈希查找D．其他二.判斷題1.）2.）3.）4.分塊查找的平均查找長度不僅與索引表的長度有關(guān)，而且與塊的長度有關(guān)。（）5.分塊查找的基本思想是首先在索引表中進(jìn)行查找，以便確定給定的關(guān)鍵字可）6.在散列存儲(chǔ)中，裝填因子α）7.如果兩個(gè)關(guān)鍵字的值不等但哈希函數(shù)值相等，則稱這兩個(gè)關(guān)鍵字為同義詞。（）8.在有序表的查詢過程中，設(shè)立“哨兵”的作用是為了提高效率。（）9.對(duì)于折半查找，其前提條件是待查找序列只要是有序的即可。（）三．填空題1.以二分查找方法從長度為10的有序表中查找一個(gè)元素時(shí)，平均查找長度為________。2.以折半（或二分）查找方法從長度為8的有序表中查找一個(gè)元素時(shí)，平均查找長度為________。3.設(shè)在長度為20的有序表中進(jìn)行二分查找，則比較一次查找成功的結(jié)點(diǎn)數(shù)有_______個(gè)，比較兩次查找成功有結(jié)點(diǎn)數(shù)有_________個(gè)。4.設(shè)查找表中有100個(gè)元素，如果用二分法查找方法查找數(shù)據(jù)元素X，則最多需要比較________次就可以斷定數(shù)據(jù)元素X是否在查找表中。5.假設(shè)在有序線性表A[1..20]上進(jìn)行二分查找，則比較一次查找成功的結(jié)點(diǎn)的結(jié)點(diǎn)數(shù)為________，則比較四次查找成功的結(jié)點(diǎn)數(shù)為________，比較五次________查找成功的結(jié)點(diǎn)數(shù)為，平均查找長度為________。6.對(duì)于長度為n分法查找，則時(shí)間復(fù)雜度為________。7.根據(jù)初始關(guān)鍵字序列(19，22，01，38，10)建立的二叉排序樹的高度為_________。8.向一棵B_樹插入元素的過程中，若最終引起樹根結(jié)點(diǎn)的分裂，則新樹比原樹的高度___________。9.設(shè)二叉排序樹的高度為h，則在該樹中查找關(guān)鍵字key最多需要比較_________次。10.對(duì)一棵二叉搜索樹進(jìn)行中序遍歷時(shí)，得到的結(jié)點(diǎn)序列是一個(gè)________。對(duì)一棵由算術(shù)表達(dá)式組成的二叉語法樹進(jìn)行后序遍歷得到的結(jié)點(diǎn)序列是該算術(shù)表達(dá)式的__________________。11.在一棵m階B_樹上，每個(gè)非樹根結(jié)點(diǎn)的關(guān)鍵字?jǐn)?shù)目最少為________個(gè)，最程的時(shí)間復(fù)雜度為____________，空間復(fù)雜度為___________。12.對(duì)一棵B_樹進(jìn)行刪除元素的過程中，若最終引起樹根結(jié)點(diǎn)的合并時(shí)，會(huì)使新樹的高度比原樹的高度___________。13.Hash技術(shù)關(guān)鍵是________和________兩個(gè)方面14.在散列存儲(chǔ)中，裝填因子a的值越大，則____；a的值越小，則____。15.在線性表的散列存儲(chǔ)中，處理沖突的常用方法有_______和_______兩種。四.簡(jiǎn)答題1.什么叫動(dòng)態(tài)查找？什么叫靜態(tài)查找？什么樣的存儲(chǔ)結(jié)構(gòu)適宜于進(jìn)行靜態(tài)查找？什么樣的存儲(chǔ)結(jié)構(gòu)適宜于進(jìn)行動(dòng)態(tài)查找？2．什么叫平均查找長度？寫出平均查找長度的定義.(2)依此二叉排序樹，如何得到一個(gè)從小到大的有序序列？4．若一棵排序二叉樹的關(guān)鍵字輸入序列為{80，6，10，7，8，25，100，90}，請(qǐng)畫出該二叉樹。H(key)=keyMOD13和鏈地址法處理沖突來構(gòu)造哈希表。（1）畫出所構(gòu)造的哈希表。（2）在記錄的查找概率相等的前提下，計(jì)算該表查找成功時(shí)的平均查找長度。序樹并給出構(gòu)造過程。7.設(shè)有一個(gè)輸入數(shù)據(jù)的序列是{46,25,78,62,12,80},試畫出從空樹起，逐個(gè)輸入各個(gè)數(shù)據(jù)而生成的二叉搜索樹。8.設(shè)散列表的長度為8，散列函數(shù)H(k)=kmod7，初始記錄關(guān)鍵字序列為(25，法的平均查找長度。9.設(shè)有一組關(guān)鍵字，其出現(xiàn)次序?yàn)椋?05，97，28，52，37，22，16，90，45，76，59，74，采用哈希函數(shù)為H(key)=keyMOD13,試在0~14的散列地址空間中對(duì)該關(guān)鍵字序列構(gòu)造哈希表。(1)采用線性探測(cè)再散列解決沖突。(2)采用二次探測(cè)再散列解決沖突。10．給定關(guān)鍵碼序列(11,81,23,59,17,19,68)，散列表長度為11，散列函數(shù)為H(key)=(5*key)%11，用二次探查法解決沖突，試畫出插入所有關(guān)鍵碼后得到的散列表，并計(jì)算查找成功與查找不成功時(shí)的平均搜索長度六．設(shè)計(jì)題1.設(shè)計(jì)在順序有序表中實(shí)現(xiàn)二分查找的算法(遞歸與非遞歸)。2.設(shè)計(jì)判斷二叉樹是否為二叉排序樹的算法。3.設(shè)計(jì)求結(jié)點(diǎn)在二叉排序樹中層次的算法。4.設(shè)計(jì)一個(gè)算法將二叉排序樹按遞減次序打印輸出。5.設(shè)計(jì)在二叉排序樹上查找結(jié)點(diǎn)X的算法。6.設(shè)計(jì)在有n個(gè)結(jié)點(diǎn)的順序表中查找最小的k（1≤k≤n）個(gè)結(jié)點(diǎn)。一、選擇題1.下述排序算法中，穩(wěn)定的是________。．直接選擇排序2.下列排序算法中，________需要的輔助存儲(chǔ)空間最大。．快速排序．插入排序C．希爾排序3.下列排序算法中，________是穩(wěn)定的。．插入、希爾．冒泡、快速4.下列各種排序算法中平均時(shí)間復(fù)雜度為O(n的是________。．直接插入排序C．快速排序．堆排序．歸并排序C．選擇、堆排序．基數(shù)、歸并2．快速排序5.在待排序的元素基本有序的前提下，效率最高的排序方法是________。．簡(jiǎn)單插入排序．簡(jiǎn)單選擇排序C．快速排序．歸并排序6.利用直接插入排序法的思想建立一個(gè)有序線性表的時(shí)間復(fù)雜度為_______。．O(n)．O(nlogn)C．O(n)．O(logn)7.對(duì)n個(gè)記錄進(jìn)行堆排序，所需要的輔助存儲(chǔ)空間為________。．O(1ogn)．O(n)C．O(1)．O(n)8.快速排序在最壞情況下的時(shí)間復(fù)雜度為________。．O(logn)B．O(nlogn)C．O(n)．堆排序C．歸并排序．冒泡排序22222．O(n)2229.設(shè)有序列12、42、37、19，當(dāng)使用直接插入排序從小到大排序時(shí)，其比較次數(shù)為________。．3．4C．5．610.對(duì)數(shù)據(jù)元素序列(49,72,68,13,38,50,97,27排序，前三趟排序結(jié)束時(shí)的結(jié)果依次為：第一趟：13,72,68,49,38,50,97,27；第二趟：13,27,68,49,38,50,97,72；第三趟：13,27,38,49,68,50,97,72；該排序采用的方法是_________。A.直接插入排序B.直接選擇排序C.冒泡排序D.堆排序11.發(fā)生顛倒，則稱該排序算法是不穩(wěn)定的。________就是不穩(wěn)定的排序方法。．起泡排序B．歸并排序C．直接插入排序．簡(jiǎn)單選擇排序12.設(shè)一組初始記錄關(guān)鍵字的長度為8，則最多經(jīng)過________趟插入排序可以得到有序序列。．6．7C．8．913.設(shè)一組初始記錄關(guān)鍵字序列為CPMSR，則按字母升序的第一趟冒泡排序結(jié)束后的結(jié)果是________。．，，C，，P，，M，，R，S，，X．P，，C，S，，，，，R，，M，YC．，，C，R，，，M，S，，P，，X．，C，，P，，M，S，R，，，，Y14.每次從無序表中取出一個(gè)元素，把它插入到有序表中的適當(dāng)位置，此種排序方法叫做________排序。．插入．堆C．快速．歸并15.每次從無序表中挑選出一個(gè)最小或最大元素，把它交換到有序表的一端，此種排序方法叫做________排序。．插入B．堆C．快速．歸并16.下列________種排序算法的平均時(shí)間復(fù)雜度為O(nlog。2．簡(jiǎn)單選擇排序17.下列________種排序算法更適合于外部排序。．選擇排序B．插入排序C．冒泡排序．簡(jiǎn)單插入排序C．冒泡排序D．歸并排序．歸并排序18.設(shè)一組初始記錄關(guān)鍵字序列，2，6，3，，以第一個(gè)記錄關(guān)鍵字5為基準(zhǔn)進(jìn)行一趟快速排序的結(jié)果為________。．2，3，5，8，6C．3，2，5，6，8．3，2，5，8，6．2，3，6，5，819.二路歸并排序的時(shí)間復(fù)雜度為________。．O(n)．O(n)C．O(nlogn)20.時(shí)間復(fù)雜度不受數(shù)據(jù)初始狀態(tài)影響而恒為O(nlog的是________。．O(logn)2222．堆排序21.一趟排序結(jié)束后不一定能夠選出一個(gè)元素放在其最終位置上的是________。．堆排序．冒泡排序C．快速排序．希爾排序．冒泡排序C．希爾排序．快速排序22.設(shè)有500010個(gè)記錄關(guān)鍵字，則用下列________方法可以達(dá)到此目的。．快速排序B．堆排序C．歸并排序．插入排序23.設(shè)一組初始關(guān)鍵字記錄關(guān)鍵字為(20，15，14，18，21，36，40，10)，則以20為基準(zhǔn)記錄的一趟快速排序結(jié)束后的結(jié)果為________。．10，15，14，18，20，36，40，21．10，15，14，18，20，40，36，21C．10，15，14，20，18，40，36，2l．15，10，14，18，20，36，40，2124.設(shè)一組初始記錄關(guān)鍵字序列為(345253674924627)，則用基數(shù)排序需要進(jìn)行________趟的分配和回收才能使得初始關(guān)鍵字序列變成有序序列。．3．4C．5．825．設(shè)一組初始記錄關(guān)鍵字序列為(5040952015706045)，則以增量d=4的一趟希爾排序結(jié)束后前4條記錄關(guān)鍵字為________。．40，50，20，95C．15，20，40，45．15，40，60，20．45，40，15，2026.設(shè)一組初始記錄關(guān)鍵字序列為(2550153580203670)，其中含有5個(gè)長度為2一趟歸并后的結(jié)果為________。．15，25，35，50，20，40，80，85，36，70．15，25，35，50，80，20，85，40，70，36C．15，25，35，50，80，85，20，36，40，70．15，25，35，50，80，20，36，40，70，8527.對(duì)于關(guān)鍵字值序列（12，13，11，18，60，15，7，18，25，100），用篩選法建堆，必須從關(guān)鍵字值為__________的結(jié)點(diǎn)開始。．100．12C．60D．1528.一組記錄的排序碼為（46，79，56，38，40，84），則堆排序時(shí)建立的初始大頂堆為________。．79，46，56，38，40，80C．84，79，56，38，40，46．38，46,56，79，40，84．84，56，79，40，46，38二、填空題1.為增量的一趟希爾排序結(jié)束后的結(jié)果為_______。2.對(duì)一組初始關(guān)鍵字序列（40，50，95，20，15，70，60，45，10）進(jìn)行冒泡多需要進(jìn)行______趟排序才可以完成。3.排序的平均時(shí)間復(fù)雜度為________。4.個(gè)堆排序過程的時(shí)間復(fù)雜度為________。5.對(duì)n個(gè)元素的序列進(jìn)行起泡排序時(shí)，最少的比較次數(shù)是_______。6.本反序，則選用_______。7.在對(duì)一組記錄（54，38，96，23，15，72，60，45，83）進(jìn)行直接插入排序時(shí)，當(dāng)把第7個(gè)記錄60插入到有序表時(shí)，為尋找插入位置需比較_______。8.序結(jié)束后的結(jié)果是________。9.序結(jié)束后的結(jié)果是_______。10.設(shè)一組初始關(guān)鍵字序列為(38，65，97，76，13，27，10)，則第3趟冒泡排序結(jié)束后的結(jié)果為_______。11.設(shè)一組初始記錄關(guān)鍵字為(72，73，71，23，94，16，5)，則以記錄關(guān)鍵字72為基準(zhǔn)的一趟快速排序結(jié)果為_________。12.排序；當(dāng)待排序的記錄數(shù)較大，存儲(chǔ)空間允許且要求排序是穩(wěn)定時(shí)