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