2018年-2018數(shù)據(jù)結(jié)構(gòu)專科復習資料

.PAGE.《數(shù)據(jù)結(jié)構(gòu)》課程復習資料一、填空題：1.設需要對5個不同的記錄關(guān)鍵字進行排序,則至少需要比較4次,至多需要比較10次。2.設二叉排序樹的高度為h,則在該樹中查找關(guān)鍵字key最多需要比較n次。3.設在長度為20的有序表中進行二分查找,則比較一次查找成功的結(jié)點數(shù)有1個,比較兩次查找成功有結(jié)點數(shù)有2個。4.數(shù)據(jù)結(jié)構(gòu)從邏輯上劃分為三種基本類型：線性結(jié)構(gòu)、樹型結(jié)構(gòu)和圖型結(jié)構(gòu)。5.在一個具有n個頂點的無向完全圖中,包含有n<n-1>/2條邊,在一個具有n個頂點的有向完全圖中,包含有n<n-1>條邊。6.向一棵B_樹插入元素的過程中,若最終引起樹根結(jié)點的分裂,則新樹比原樹的高度增加1。7.在堆排序的過程中,對任一分支結(jié)點進行篩運算的時間復雜度為O<log2n>,整個堆排序過程的時間復雜度為O<nlog2n>。8.在快速排序、堆排序、歸并排序中,歸并排序是穩(wěn)定的。9.在有n個葉子結(jié)點的哈夫曼樹中,總結(jié)點數(shù)是n-1。評卷人得分10.一棵樹T采用二叉鏈表存儲,如果樹T中某結(jié)點為葉子結(jié)點,則在二叉鏈表BT中所對應的結(jié)點一定左右子樹空。11.已知數(shù)組A［１０］［１０］為對稱矩陣,其中每個元素占5個單元?，F(xiàn)將其下三角部分按行優(yōu)先次序存儲在起始地址為1000的連續(xù)的內(nèi)存單元中,則元素A［5,6］對應的地址是1225。12.在有n個結(jié)點的無向圖中,其邊數(shù)最多為n<n-1>/2。13.取出廣義表A=<x,<a,b,c,d>>中原子x的函數(shù)是head<A>。14.對矩陣采用壓縮存儲是為了節(jié)省空間。15.帶頭結(jié)點的雙循環(huán)鏈表L為空表的條件是L->next=L->prior或L->next=L。16.設線性表中元素的類型是實型,其首地址為1024,則線性表中第6個元素的存儲位置是1044。17.對于順序存儲的棧,因為棧的空間是有限的,在進行入?！膊迦脒\算時,可能發(fā)生棧的上溢,在進行出棧〔刪除運算時,可能發(fā)生棧的下溢。18.在雙向鏈表中,每個結(jié)點有兩個指針域,一個指向前驅(qū)結(jié)點,另一個指向后繼結(jié)點。19.由一棵二叉樹的前序序列和中序序列可唯一確定這棵二叉樹。20.折半查找的存儲結(jié)構(gòu)僅限于順序存儲結(jié)構(gòu),且是有序的。21.對于一個順序存儲的線性表,在表頭插入元素的時間復雜度為O<n>,在表尾插入元素的時間復雜度為O<1>。22.在稀疏距陣所對應的三元組線形表中,每個三元組元素按行號為主序,列號為輔序的次序排列。23.中綴表達示3+X*〔2.4/5-6所對應的后綴表達示為3x2.45／6－*＋。24.在一棵高度為h的3叉樹中,最多含有<3h-1>/2結(jié)點。25.分析下面算法〔程序段,給出最大語句頻度n3,該算法的時間復雜度是O<n3>。for<i=0;i<n;i++>for<j=0;j<n;j++>A[i][j]=0;26.空串是零個字符的串,其長度等于零。27.一個圖的鄰接矩陣表示法是唯一的,而鄰接表表示法是不唯一的。28.在一個單鏈表中p所指結(jié)點之前插入一個s<值為e>所指結(jié)點時,可執(zhí)行如下操作：q=head;while<q->next!=p>q=q->next;s=newNode;s->data=e;q->next=s;//填空s->next=p;//填空29.在一個單鏈表中刪除p所指結(jié)點的后繼結(jié)點時,應執(zhí)行以下操作：q=p->next;p->next=q->next;//填空deleteq;//填空30.兩個串相等的充分必要條件是兩個串的長度相等且對應位置的字符相同。31.二維數(shù)組A[10][20]采用列序為主方式存儲,每個元素占一個存儲單元并且A[0][0]的存儲地址是200,則A[6][12]的地址是200+〔6*20+12=326。32.二維數(shù)組A[10..20][5..10]采用行序為主方式存儲,每個元素占4個存儲單元,并且A[10][5]的存儲地址是1000,則A[18][9]的地址是1000+<<18-10>*6+<9-5>>*4=1208。33.求下列廣義表操作的結(jié)果：<1>GetTail[GetHead[<<a,b>,<c,d>>]];<b><2>GetTail[GetHead[GetTail[<<a,b>,<c,d>>]]]<d>34.已知一個有向圖的鄰接矩陣表示,計算第i個結(jié)點的入度的方法是求矩陣第i列非零元素之和。35.已知一個圖的鄰接矩陣表示,刪除所有從第i個結(jié)點出發(fā)的邊的方法是將矩陣第i行全部置為零。36.在利用快速排序方法對一組記錄〔54,38,96,23,15,72,60,45,83進行快速排序時,遞歸調(diào)用而使用的棧所能達到的最大深度為2,共需遞歸調(diào)用的次數(shù)為4,其中第二次遞歸調(diào)用是對〔23,38,15組記錄進行快速排序。37.在堆排序,快速排序和歸并排序中,若只從存儲空間考慮,則應首先選取堆排序方法,其次選取快速排序方法,最后選取歸并排序方法；若只從排序結(jié)果的穩(wěn)定性考慮,則應選取歸并排序方法；若只從平均情況下排序最快考慮,則應選取快速排序方法；若只從最壞情況下排序最快并且要節(jié)省內(nèi)存考慮,則應選取堆排序方法。38.稱算法的時間復雜度為O<f<n>>,其含義是指算法的執(zhí)行時間和f<n>的數(shù)量級相同。39.在一個長度為n的單鏈表L中,刪除鏈表中*p的前驅(qū)結(jié)點的時間復雜度為O<n>。40.假設為循環(huán)隊列分配的向量空間為Q[20],若隊列的長度和隊頭指針值分別為13和17,則當前尾指針的值為10。41.對于棧只能在棧頂插入和刪除元素。42.設有一個順序棧S,元素sl,s2,s3,s4,s5,s6依次進棧,如果6個元素的出棧順序為s2,s3,s4,s6,s5,sl,則順序棧的容量至少應為3。43.數(shù)據(jù)結(jié)構(gòu)一般包括三個方面內(nèi)容：數(shù)據(jù)的邏輯結(jié)構(gòu),數(shù)據(jù)的存儲結(jié)構(gòu)及數(shù)據(jù)的運算。44.在包含n個結(jié)點的順序表上做等概率插入運算,平均要移動n/2個結(jié)點。45.隊列的特性是先進先出。46.已知二叉樹中葉子數(shù)為30,僅有一個孩子的結(jié)點數(shù)為20,則總結(jié)點數(shù)為79。47.中序遍歷二叉排序樹中的結(jié)點可以得到一個遞增的關(guān)鍵字序列〔選填"先序"、"中序"或"后序"。48.n個節(jié)點的連通圖至少有n-1條邊。49.在堆排序和快速排序中,如果從平均情況下排序的速度最快的角度來考慮,應最好選擇快速排序排序。50.帶有一個頭結(jié)點的單鏈表head為空的條件是〔假設指針域的名稱為nexthead->next==NULL。51.設一組初始關(guān)鍵字序列為<38,65,97,76,13,27,10>,則第3趟簡單選擇排序后的結(jié)果為10,13,27,76,65,97,38。52.在拓撲排序中,拓撲序列的第一個頂點必定是入度為零的頂點。53.數(shù)據(jù)的邏輯結(jié)構(gòu)分為兩大類,它們是線性結(jié)構(gòu)和非線性結(jié)構(gòu)。54.在單鏈表中〔假設結(jié)點指針域名稱為next,刪除指針P所指結(jié)點的后繼結(jié)點的語句是p->next=p->next->next。55.已知循環(huán)隊列用數(shù)組data[n]存儲元素值,用front,rear分別作為頭尾指針,則當前元素個數(shù)為<rear-front+n>%n。56.若n為主串長,m為子串長,則串的樸素匹配算法最壞的情況下需要比較字符的總次數(shù)〔n-m+1×m。57.廣義表<<a>,<<b>,j,<<<d>>>>>的表尾是<<<b>,j,<<<d>>>>>。58.已知二叉樹有61個葉子節(jié)點,且僅有一個孩子的節(jié)點數(shù)為45,則總節(jié)點數(shù)為166。59.解決計算機與打印機之間速度不匹配問題,須要設置一個數(shù)據(jù)緩沖區(qū),應是一個隊列結(jié)構(gòu)。二、單項選擇題：1.隊列的特點是[B]A.先進后出B.先進先出C.任意位置進出D.前面都不正確2.[B]A.nB.dC.rD.n-d3.在二叉樹結(jié)點的先序序列、中序序列和后序序列中,所有葉子結(jié)點的先后順序[B]A.都不相同B.完全相同C.先序和中序相同,而與后序不同D.中序和后序相同,而與先序不同4.設有198個初始歸并段,如采用K-路平衡歸并三遍完成排序,則K值最大為[C]A.12B.13C.14D.155.下面關(guān)于廣義表的敘述中,不正確的是[B]A.廣義表可以是一個多層次的結(jié)構(gòu)B.廣義表至少有一個元素C.廣義表可以被其他廣義表所共享D.廣義表可以是一個遞歸表6.設二叉樹根結(jié)點的層次為0,一棵深度〔高度為k的滿二叉樹和同樣深度完全二叉樹各有f個結(jié)點和c個結(jié)點,下列關(guān)系式不正確的是[B]A.f>=c B.c>fC.f=2k+1-aD.c>sk-17.從L=<<apple,pear>,<orange,banana>>中,取出banana元素的表達式為[D]A.head<tail<L>>B.head<head<tail<L>>>C.tail<head<tail<L>>> D.head<tail<head<tail<L>>>>8.下列文件的物理結(jié)構(gòu)中,不利于文件長度動態(tài)增長的文件物理結(jié)構(gòu)是[A]A.順序結(jié)構(gòu)B.鏈接結(jié)構(gòu)C.索引結(jié)構(gòu)D.Hash結(jié)構(gòu)9.在數(shù)據(jù)結(jié)構(gòu)中,數(shù)據(jù)元素可由[C]A.實體B.域C.數(shù)據(jù)項D.字段10.,〔FloyD[D]A.O<1>B.O<n>C.O<n>D.O<n3>11.對n個記錄的文件進行快速排序,所需要的輔助存儲空間為[B]A.O〔1B.O〔log2nC.O〔nD.O〔n212.哈夫曼樹中一定不存在[B]A.度為0的結(jié)點B.度為1的結(jié)點C.度為2的結(jié)點D.帶權(quán)的結(jié)點13.下述哪一條是順序存儲方式的優(yōu)點？[A]A.存儲密度大B.插入和刪除運算方便C.獲取符合某種條件的元素方便D.查找運算速度快14.有一個二維數(shù)組A[m][n],假設A[0][0]存放位置在600<10>,A[3][3]存放位置在678<10>,每個元素占一個空間,問A[2][3]<10>存放在什么位置？〔腳注<10>表示用10進制表示,m>3[D]A.658B.648C.633D.65315.下列關(guān)于二叉樹遍歷的敘述中,正確的是[A]A.若一個葉子是某二叉樹的中序遍歷的最后一個結(jié)點,則它必是該二叉樹的前序遍歷最后一個結(jié)點B.若一個結(jié)點是某二叉樹的前序遍歷最后一個結(jié)點,則它必是該二叉樹的中序遍歷的最后一個結(jié)點C.若一個結(jié)點是某二叉樹的中序遍歷的最后一個結(jié)點,則它必是該二叉樹的前序最后一個結(jié)點D.若一個樹葉是某二叉樹的前序最后一個結(jié)點,則它必是該二叉樹的中序遍歷最后一個結(jié)點16.第K層二叉樹的結(jié)點總數(shù)最多為[A]A.2k-1B.2k+1C.2K-1D.2k-117.線性表進行二分法查找,其前提條件是[C]A.線性表以鏈接方式存儲,并且按關(guān)鍵碼值排好序B.線性表以順序方式存儲,并且按關(guān)鍵碼值的檢索頻率排好序C.線性表以順序方式存儲,并且按關(guān)鍵碼值排好序D.線性表以鏈接方式存儲,并且按關(guān)鍵碼值的檢索頻率排好序18.n個記錄進行堆排序,所需要的輔助存儲空間為[C]A.O<1og2n>B.O<n>C.O<1>D.O<n2>19.線性表〔7,34,77,25,64,49,20,14進行散列存儲時,若選用H〔K=K%7作為散列函數(shù),則散列地址為0的元素有〔個。[D]A.1B.2C.3D.420.下列關(guān)于數(shù)據(jù)結(jié)構(gòu)的敘述中,正確的是[D]A.數(shù)組是不同類型值的集合B.遞歸算法的程序結(jié)構(gòu)比迭代算法的程序結(jié)構(gòu)更為精煉C.樹是一種線性結(jié)構(gòu)D.用一維數(shù)組存儲一棵完全二叉樹是有效的存儲方法21.以下數(shù)據(jù)結(jié)構(gòu)中哪一個是線性結(jié)構(gòu)？[B]A.有向圖B.隊列C.線索二叉樹D.B樹22.在一個單鏈表HL中,若要在當前由指針p指向的結(jié)點后面插入一個由q指向的結(jié)點,則執(zhí)行如下〔語句序列。[D]A.p=q;p->next=q;B.p->next=q;q->next=p;C.p->next=q->next;p=q;D.q->next=p->next;p->next=q;23.〔不是隊列的基本運算。[A]A.在隊列第i個元素之后插入一個元素B.從隊頭刪除一個元素C.判斷一個隊列是否為空D.讀取隊頭元素的值24.若已知一個棧的入棧序列是1,2,3,…,n,其輸出序列為p1,p2,p3,…,pn,若p1=n,則pi為[C]A.iB.n=iC.n-i+1D.不確定25.棧的特點是〔B,隊列的特點是〔A。A.先進先出B.先進后出26.設有兩個串p和q,求q在p中首次出現(xiàn)的位置的運算稱作[B]A.連接B.模式匹配C.求子串D.求串長27.二維數(shù)組A中,每個元素A[i][j]的長度為3個字節(jié),行下標i從0到7,列下標j從0到9,從首地址SA開始連續(xù)存放在存儲器內(nèi),該數(shù)組按列存放時,元素A[4][7]的起始地址為[B]A.SA+141B.SA+180C.SA+222D.SA+22528.某二叉樹的前序遍歷結(jié)點訪問順序是abdgcefh,中序遍歷的結(jié)點訪問順序是dgbaechf,則其后序遍歷的結(jié)點訪問順序是[D]A.bdgcefhaB.gdbecfhaC.bdgaechfD.gdbehfca29.在一非空二叉樹的中序遍歷序列中,根結(jié)點的右邊[A]A.只有右子樹上的所有結(jié)點B.只有右子樹上的部分結(jié)點C.只有左子樹上的部分結(jié)點D.只有左子樹上的所有結(jié)點30.具有6個頂點的無向圖至少應有〔條邊才能確保是一個連通圖。[A]A.5B.6C.7D.831.二分查找和二叉排序樹的時間性能[B]A.相同B.不相同32.采用二分查找方法查找長度為n的線性表時,每個元素的平均查找長度為[B]A.O〔n2B.O<nlog2n>C.O<n>D.O<log2n>33.在待排序的元素序列基本有序的前提下,效率最高的排序方法是[A]A.插入排序B.選擇排序C.快速排序D.歸并排序34.下述幾種排序方法中,要求內(nèi)存量最大的是[D]A.插入排序B.選擇排序C.快速排序D.歸并排序35.設有兩個串p和q,求q在p中首次出現(xiàn)的位置的運算稱作[B]A.連接B.模式匹配C.求子串D.求串長36.二維數(shù)組A中,每個元素A[i][j]的長度為3個字節(jié),行下標i從0到7,列下標j從0到9,從首地址SA開始連續(xù)存放在存儲器內(nèi),該數(shù)組按列存放時,元素A[4][7]的起始地址為[B]A.SA+141B.SA+180C.SA+222D.SA+22537.某二叉樹的前序遍歷結(jié)點訪問順序是abdgcefh,中序遍歷的結(jié)點訪問順序是dgbaechf,則其后序遍歷的結(jié)點訪問順序是[D]A.bdgcefhaB.gdbecfhaC.bdgaechfD.gdbehfca38.在一非空二叉樹的中序遍歷序列中,根結(jié)點的右邊[A]A.只有右子樹上的所有結(jié)點B.只有右子樹上的部分結(jié)點C.只有左子樹上的部分結(jié)點D.只有左子樹上的所有結(jié)點39.具有6個頂點的無向圖至少應有〔條邊才能確保是一個連通圖。[A]A.5B.6C.7D.840.二分查找和二叉排序樹的時間性能[B]A.相同B.不相同C.可能相同D.不確定41.采用二分查找方法查找長度為n的線性表時,每個元素的平均查找長度為[B]A.O〔n2B.O<nlog2n>C.O<n>D.O<log2n>42.在待排序的元素序列基本有序的前提下,效率最高的排序方法是[A]A.插入排序B.選擇排序C.快速排序D.歸并排序43.下面的序列中〔是大頂堆。[D]A.1,2,8,5,3,9,10,4B.1,5,10,6,7,8,9,2C.9,8,7,6,4,8,2,1D.9,8,7,6,5,4,3,144.對一個算法的評價,不包括如下〔方面的內(nèi)容。[B]A.健壯性和可讀性B.并行性C.正確性D.時空復雜度45.在帶有頭結(jié)點的單鏈表HL中,要向表頭插入一個由指針p指向的結(jié)點,則執(zhí)行[A]A.p->next=HL->next;HL->next=pB.p->next=HL;HL=pC.p->next=HL;p=HLD.HL=p;p->next=HL46.對線性表,在下列哪種情況下應當采用鏈表表示？[B]A.經(jīng)常需要隨機地存取元素B.經(jīng)常需要進行插入和刪除操作C.表中元素需要占據(jù)一片連續(xù)的存儲空間D.表中元素的個數(shù)不變47.一個棧的輸入序列為123,則下列序列中不可能是棧的輸出序列的是[C]A.231B.321C.312D.12348.每一趟都能選出一個元素放在其最終位置上,并且不穩(wěn)定的排序算法是[B]A.冒泡排序B.簡單選擇排序C.希爾排序D.直接插入排序49.采用開放定址法處理散列表的沖突時,其平均查找長度[B]A.低于鏈接法處理沖突B.高于鏈接法處理沖突C.與鏈接法處理沖突相同D.高于二分查找50.若需要利用形參直接訪問實參時,應將形參變量說明為〔參數(shù)。[D]A.值B.函數(shù)C.指針D.引用51.在稀疏矩陣的帶行指針向量的鏈接存儲中,每個單鏈表中的結(jié)點都具有相同的[A]A.行號B.列號C.元素值D.非零元素個數(shù)52.快速排序在最壞情況下的時間復雜度為[D]A.O<log2n>B.O<nlog2n>C.O<n>D.O<n2>53.從二叉搜索樹中查找一個元素時,其時間復雜度大致為[C]A.O<n>B.O<1>C.O<log2n>D.O<n2>54.設一個有序的單鏈表中有n個結(jié)點,現(xiàn)要求插入一個新結(jié)點后使得單鏈表仍然保持有序,則該操作的時間復雜度為[D]A.O<log2n>B.O<1>C.O<n2>D.O<n>55.設一棵m叉樹中度數(shù)為0的結(jié)點數(shù)為N0,度數(shù)為1的結(jié)點數(shù)為Nl,……,度數(shù)為m的結(jié)點數(shù)為Nm,則N0=[B]A.Nl+N2+……+NmB.l+N2+2N3+3N4+……+<m-1>NmC.N2+2N3+3N4+……+<m-1>NmD.2Nl+3N2+……+<m+1>Nm56.二維數(shù)組A中,每個元素A的長度為3個字節(jié),行下標i從0到7,列下標j從0到9,從首地址SA開始連續(xù)存放在存儲器內(nèi),該數(shù)組按行存放時,數(shù)組元素A[7][4]的起始地址為[C]A.SA+141B.SA+144C.SA+222D.SA+22557.如果某二叉樹的前根次序遍歷結(jié)果為stuwv,中序遍歷為uwtvs,那么該二叉樹的后序為[B]A.uwvtsB.vwutsC.wuvtsD.wutsv58.深度為5的二叉樹至多有〔個結(jié)點。[C]A.16B.32C.31D.1059.在一個無向圖中,所有頂點的度數(shù)之和等于所有邊數(shù)的〔倍。[C]A.1/2B.1C.2D.460.采用順序查找方法查找長度為n的線性表時,每個元素的平均查找長度為[C]A.nB.n/2C.<n+1>/2D.<n-1>/261.采用二分查找方法查找長度為n的線性表時,每個元素的平均查找長度為[C]A.O〔n2B.O<nlog2n>C.O<n>D.O<log2n>62.下述幾種排序方法中,要求內(nèi)存量最大的是[D]A.插入排序B.選擇排序C.快速排序D.歸并排序63.排序方法中,從未排序序列中依次取出元素與已排序序列〔初始時為空中的元素進行比較,將其放入已排序序列的正確位置上的方法,稱為[C]A.希爾排序B.起泡排序C.插入排序D.選擇排序64.對于長度為9的有序順序表,若采用折半搜索,在等概率情況下搜索成功的平均搜索長度為〔的值除以9。[C]A.20B.18C.25D.2265.在有向圖中每個頂點的度等于該頂點的[C]A.入度B.出度C.入度與出度之和D.入度與出度之差66.在基于排序碼比較的排序算法中,〔算法的最壞情況下的時間復雜度不高于O<n10g2n>。[C]A.起泡排序B.希爾排序C.歸并排序D.快速排序67.當α的值較小時,散列存儲通常比其他存儲方式具有〔的查找速度。[B]A.較慢B.較快C.相同D.不清楚68.設有一個含200個表項的散列表,用線性探查法解決沖突,按關(guān)鍵碼查詢時找到一個表項的平均探查次數(shù)不超過1.5,則散列表項應能夠至少容納〔個表項。[A]<設搜索成功的平均搜索長度為Snl＝{1+l／<1一α>}／2,其中α為裝填因子>A.400B.526C.624D.67669.堆是一個鍵值序列{k1,k2,…..kn},對I=1,2,….|_n/2_|,滿足[C]A.ki≤k2i≤k2i+1B.ki<k2i+1<k2iC.ki≤k2i且ki≤k2i+1<2i+1≤n>D.ki≤k2i或ki≤k2i+1<2i+1≤n>70.若將數(shù)據(jù)結(jié)構(gòu)形式定義為二元組<K,R>,其中K是數(shù)據(jù)元素的有限集合,則R是K上[B]A.操作的有限集合B.映象的有限集合C.類型的有限集合D.關(guān)系的有限集合71.下列圖示的順序存儲結(jié)構(gòu)表示的二叉樹是[A]72.由同一關(guān)鍵字集合構(gòu)造的各棵二叉排序樹[B]A.其形態(tài)不一定相同,但平均查找長度相同B.其形態(tài)不一定相同,平均查找長度也不一定相同C.其形態(tài)均相同,但平均查找長度不一定相同D.其形態(tài)均相同,平均查找長度也都相同73.ISAM文件和VSAM文件的區(qū)別之一是[C]A.前者是索引順序文件,后者是索引非順序文件B.前者只能進行順序存取,后者只能進行隨機存取C.前者建立靜態(tài)索引結(jié)構(gòu),后者建立動態(tài)索引結(jié)構(gòu)D.前者的存儲介質(zhì)是磁盤,后者的存儲介質(zhì)不是磁盤74.下列描述中正確的是[D]A.線性表的邏輯順序與存儲順序總是一致的B.每種數(shù)據(jù)結(jié)構(gòu)都具備三個基本運算：插入、刪除和查找C.數(shù)據(jù)結(jié)構(gòu)實質(zhì)上包括邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)兩方面的內(nèi)容D.選擇合適的數(shù)據(jù)結(jié)構(gòu)是解決應用問題的關(guān)鍵步驟75.下面程序段的時間復雜度是[B]I=s=0While<s<n>{I++;s+=I;}A.O<1>B.O<n>C.O<log2n>D.O<n^2>76.如果只想得到1024個元素組成的序列中的前5個最小元素,那么用〔方法最快。[A]A.起泡排序B.快速排序C.堆排序D.直接選擇排序77.算法分析的目的是[B]A.辨別數(shù)據(jù)結(jié)構(gòu)的合理性B.評價算法的效率C.研究算法中輸入與輸出的關(guān)系D.鑒別算法的可讀性78.在線性表的下列運算中,不改變數(shù)據(jù)元素之間結(jié)構(gòu)關(guān)系的運算是[C]A.插入B.刪除C.定位D.排序79.若進棧序列為1,2,3,4,5,6,且進棧和出?？梢源┎暹M行,則可能出現(xiàn)的出棧序列為[D]A.3,2,6,1,4,5B.5,6,4,2,3,1C.1,2,5,3,4,6D.3,4,2,1,6,580.設串sl=″DataStructureswithJava″,s2=″it″,則子串定位函數(shù)index<s1,s2>的值為[A]A.15B.16C.17D.1881.一個順序存儲的線性表的第一個元素的存儲地址是100,每個元素的長度為4,則第4個元素的存儲地址是[B]A.108B.112C.116D.12082.從一個具有n個結(jié)點的單鏈表中查找其值等于x的結(jié)點,在查找成功的情況下,平均需要比較〔個結(jié)點。[C]A.nB.n/2C.<n+1>/2D.<n-1>/283.在任意一棵二叉樹的前序序列和后序序列中,各葉子之間的相對次序關(guān)系[D]A.不一定相同B.互為逆序C.都不相同D.都相同84.高度為5的二叉樹至多有結(jié)點數(shù)為[A]A.63B.32C.24D.6485.若用鄰接矩陣表示一個有向圖,則其中每一列包含的″1″的個數(shù)為[B]A.圖中每個頂點的出度B.圖中每個頂點的入度C.圖中弧的條數(shù)D.圖中連通分量的數(shù)目86.圖的鄰接矩陣表示法一般不太適用于表示[A]A.無向圖B.有向圖C.稠密圖D.稀疏圖87.循環(huán)隊列是空隊列的條件是[B]A.Q->rear==Q->frontB.<Q->rear+1>%maxsize==Q->frontC.Q->rear==0D.Q->front==088.設有一廣義表E=〔a,b,<c,d>,其長度為[A]A.2B.3C.4D.589.某二叉樹的前序遍歷序列為ABDEFC,中序遍歷序列為DBEFAC,則后序遍歷序列為[D]A.DFEBCAB.DBECFAC.BDAECFD.DBEFCA90.下列〔不是利用查找表中數(shù)據(jù)元素的關(guān)系進行查找的方法。[C]A.有序表的查找B.二叉排序樹的查找C.平衡二叉樹D.散列查找91.下述幾種排序方法中,要求內(nèi)存量最大的是[B]A.插入排序B.快速排序C.歸并排序D.選擇排序92.在一個有向圖中,所有頂點的入度之和等于所有頂點的出度之和的〔倍。[B]A.1/2B.1C.2D.493.在帶有頭結(jié)點的單鏈表HL中,要向表頭插入一個由指針p指向的結(jié)點,則執(zhí)行[A]A.p->next=HL->next;HL->next=pB.p->next=HL;HL=pC.p->next=HL;p=HLD.HL=p;p->next=HL94.對線性表,在下列哪種情況下應當采用鏈表表示？[B]A.經(jīng)常需要隨機地存取元素B.經(jīng)常需要進行插入和刪除操作C.表中元素需要占據(jù)一片連續(xù)的存儲空間D.表中元素的個數(shù)不變95.一個棧的輸入序列為123,則下列序列中不可能是棧的輸出序列的是[C]A.231B.321C.312D.12396.每一趟都能選出一個元素放在其最終位置上,并且不穩(wěn)定的排序算法是[B]A.冒泡排序B.簡單選擇排序C.希爾排序D.直接插入排序97.采用開放定址法處理散列表的沖突時,其平均查找長度[B]A.低于鏈接法處理沖突B.高于鏈接法處理沖突C.與鏈接法處理沖突相同D.高于二分查找98.若需要利用形參直接訪問實參時,應將形參變量說明為〔參數(shù)。[D]A.值B.函數(shù)C.指針D.引用99.在稀疏矩陣的帶行指針向量的鏈接存儲中,每個單鏈表中的結(jié)點都具有相同的[A]A.行號B.列號C.元素值D.非零元素個數(shù)100.快速排序在最壞情況下的時間復雜度為[D]A.O<log2n>B.O<nlog2n>C.O<n>D.O<n2>101.從二叉搜索樹中查找一個元素時,其時間復雜度大致為[C]A.O<n>B.O<1>C.O<log2n>D.O<n2>102.設一個有序的單鏈表中有n個結(jié)點,現(xiàn)要求插入一個新結(jié)點后使得單鏈表仍然保持有序,則該操作的時間復雜度為[D]A.O<log2n>B.O<1>C.O<n2>D.O<n>103.設一棵m叉樹中度數(shù)為0的結(jié)點數(shù)為N0,度數(shù)為1的結(jié)點數(shù)為Nl,……,度數(shù)為m的結(jié)點數(shù)為Nm,則N0=[B]A.Nl+N2+……+NmB.l+N2+2N3+3N4+……+<m-1>NmC.N2+2N3+3N4+……+<m-1>NmD.2Nl+3N2+……+<m+1>Nm104.設有序表中有1000個元素,則用二分查找查找元素X最多需要比較〔次。[B]A.25B.10C.7D.1105.設連通圖G中的邊集E={<a,b>,<a,e>,<a,c>,<b,e>,<e,d>,<d,f>,<f,c>},則從頂點a出發(fā)可以得到一種深度優(yōu)先遍歷的頂點序列為[B]A.abedfcB.acfebdC.aebdfcD.aedfcb106.拓撲排序運算只能用于[C]A.帶權(quán)有向圖B.連通無向圖C.有向無環(huán)圖D.無向圖107.在一個具有n個結(jié)點的有序單鏈表中插入一個新結(jié)點并仍然保持有序的時間復雜度是[B]A.O<1>B.O<n>C.O<n2>D.O<nlogn>計算與算法應用題：1.已知一個圖的頂點集V和邊集E分別為：V={1,2,3,4,5,6,7};E={<1,2>3,<1,3>5,<1,4>8,<2,5>10,<2,3>6,<3,4>15,<3,5>12,<3,6>9,<4,6>4,<4,7>20,<5,6>18,<6,7>25};按照普里姆算法從頂點1出發(fā)得到最小生成樹,試寫出在最小生成樹中依次得到的各條邊。2.一棵二叉樹的先序、中序和后序序列分別如下,其中有一部分未顯示出來。試求出空格處的內(nèi)容,并畫出該二叉樹。先序序列：BFICEHG中序序列：DKFIAEJC后序序列：KFBHJGA3.畫出下列樹對應的二叉樹,并寫出其先根遍歷序列：BBDFCAEG4.將關(guān)鍵字序列為{54,29,37,86,71,91,8,31,44,26}進行歸并排序,寫出各趟詳細過程。5.試列出如下圖中全部可能的拓撲排序序列。6.設某通信系統(tǒng)使用A,B,C,D,E,F,G,H八個字符,他們出現(xiàn)的概率w={5,29,7,8,14,23,3,11},試構(gòu)造對應的哈夫曼樹〔請按左子樹根結(jié)點的權(quán)小于右子樹樹根結(jié)點的權(quán)的次序構(gòu)造。7.給定表〔119,14,22,1,66,21,83,27,56,13,10,請按表中元素的順序構(gòu)造一棵平衡二叉樹,并求其在等概率情況下查找成功的平均長度。8.已知一個有向圖的頂點集V和邊集G分別為：V={a,b,c,d,e,f,g,h}E={<a,b>,<a,c>,<b,f>,<c,d>,<c,e>,<d,a>,<d,f>,<d,g>,<e,g>,<f,h>};假定該圖采用鄰接矩陣表示,則分別寫出從頂點a出發(fā)進行深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷得到的頂點序列。9.設散列表的長度為13,散列函數(shù)為H〔h=k%13,給定的關(guān)鍵碼序列為19,14,23,01,68,20,84,27。試畫出用線性探查法解決沖突時所構(gòu)成的散列表。012345678910111210.對7個關(guān)鍵字進行快速排序,在最好的情況下僅需進行10次關(guān)鍵字的比較。<1>假設關(guān)鍵字集合為{1,2,3,4,5,6,7},試舉出能達到上述結(jié)果的初始關(guān)鍵字序列；<2>對所舉序列進行快速排序,寫出排序過程。11.如圖所示二叉樹,回答下列問題。12.畫出在一個初始為空的AVL樹中依次插入3,1,4,6,9,8,5,7時每一插入后AVL樹的形態(tài)。若做了某種旋轉(zhuǎn),說明旋轉(zhuǎn)的類型。然后,給出在這棵插入后得到的AVL樹中刪去根結(jié)點后的結(jié)果。13.已知一組記錄的排序碼為〔46,79,56,38,40,80,95,24,寫出對其進行快速排序的每一次劃分結(jié)果。14.一個線性表為B=〔12,23,45,57,20,03,78,31,15,36,設散列表為HT[0..12],散列函數(shù)為H〔key=key%13并用線性探查法解決沖突,請畫出散列表,并計算等概率情況下查找成功的平均查找長度。15.已知一棵二叉樹的前序遍歷的結(jié)果序列是ABECDFGHIJ,中序遍歷的結(jié)果是EBCDAFHIGJ,試寫出這棵二叉樹的后序遍歷結(jié)果。16.假定對線性表<38,25,74,52,48,65,36>進行散列存儲,采用H<K>=K％9作為散列函數(shù),若分別采用線性探查法和鏈接法處理沖突,則計算對應的平均查找長度。17.已知哈希表地址空間為0..8,哈希函數(shù)為H<key>=key%7,采用線性探測再散列處理沖突,將數(shù)據(jù)序列{100,20,21,35,3,78,99,45}依次存入此哈希表中,列出插入時的比較次數(shù),并求出在等概率下的平均查找長度。18.試畫出下面帶權(quán)無向圖的一棵最小生成樹。55768432997abdcef19.已知關(guān)鍵字序列為：{03,87,12,61,98,70,61*,97,27,53,42,56,77,}請采用希爾<Shell>排序法對該序列作非遞減排序.按5,3,1分組,寫出下列標明的趟的結(jié)果。初始03,87,12,61,98,70,97,27,53,42,56,77第一趟第二趟每三趟四、閱讀下列算法,分析它的作用：1.intAA<LNode*HL,ElemTypex>{intn=0;LNode*p=HL;while<p!=NULL>{if<p->data==x>n++;p=p->next;}returnn;}對于結(jié)點類型為LNode的單鏈表,以上算法的功能為：2.intAA<LNode*HL,ElemTypex>{intn=0;LNode*p=HL;while<p!=NULL>{if<p->data==x>n++;p=p->next;}returnn;}對于結(jié)點類型為LNode的單鏈表,以上算法的功能為：3.假定從鍵盤上輸入一批整數(shù),依次為：786345309134–1,請寫出輸出結(jié)果。#include<iostream.h>#include<stdlib.h>constintstackmaxsize=30;typedefintelemtype;structstack{elemtypestack[stackmaxsize];inttop;};#include"stack.h"voidmain[]{stacka;initstack<a>;intx;cin>>x;while<x!=-1>{push<a,x>;cin>>x;}while<!stackempty<a>>cout<<pop<a><<"";cout<<end1;}該算法的輸出結(jié)果為：_____________。4.讀下述算法,說明本算法完成什么功能。template<calsstype>voidBinTree<Type>：：unknown<BinTreeNode<Type>*t>{BinTreeNode<Type>*p=t,*temp;if<p!=NULL>{temp=p→leftchild;p→leftchild=p→rightchild;p→rightchild=temp;unknown<p→leftchild>;undnown<p→rightchild>;}}該算法的功能是：______________。5.閱讀下列算法,說明該算法的作用。//類定義//類定義constintMAX=20;typedefcharElemType;classSqstack{private:ElemTypeelem[MAX];inttop;public:Sqstack<>{top=0};ElemTypepop<>;voidpush<ElemTypex>;//…….;};{if<top==MAX-1>cout<<"\n滿！"；else{top++;elem[top]=x;}}//pushstructSnode//結(jié)點結(jié)構(gòu)structSnode//結(jié)點結(jié)構(gòu){chardata;Snode*next;};classLink//鏈表類{private:Snode*Head;public:Link<>{Head=NULL};voidcreat<>;voidoutput<>;//…….;voidLink:output<>{p=Head->next;while<p!=NULL>{cout<<"\ndata="<<p->data;p=p->next;}}//output7.讀下述算法,說明本算法完成什么功能。voidBtree::inordern<bnode*p,int&n>{if<p!=NULL>{inordern<p->lch,n>;if<p->lch==NULL&&p->rch==NULL>n++;inordern<p->rch,n>;}}//inordern8.voidAD<Lnode*&HL>{Insert<HL,30>;Insert<HL,50>;Delete<HL,26>;Delete<HL,55>;}假定調(diào)用該算法時以HL為表頭指針的單鏈表中的內(nèi)容為〔15,26,48,55,則調(diào)用返回后該單鏈表中的內(nèi)容為：____________。9.voidAI<adjmatrrixGA,inti,intn>{cout<<i<<’’;visted[i]=true;for<intj=0;j<n;j++>if<Ga[I][j]!=0&&GA[i][j]!=MaxValue&&!visited[j]>AI<GA,j,n>;}該算法的功能為：_______________。//類定義//類定義constintMAX=20;typedefcharElemType;classSqstack{private:ElemTypeelem[MAX];inttop;public:Sqstack<>{top=0};ElemTypepop<>;voidpush<ElemTypex>;//…….;};ElemTtypeSqstack::pop[]{ElemTypex;if<top==0>x=-999;else{x=elem[top];top--;}returnx;}//popstructSnode//結(jié)點結(jié)構(gòu)structSnode//結(jié)點結(jié)構(gòu){chardata;Snode*next;};classLink//鏈表類{private:Snode*Head;public:Link<>{Head=NULL};voidcreat<>;voidreverse<>;voidoutput<>;//…….;voidLink::reverse<>{Snode*p,*q;p=Head->next;Head->next=NULL;while<p!=NULL>{q=p->next;p->next=Head->next;Head>next=p;p=q;}aHeadaHeadbc^ed12.下列函數(shù)是二叉排序樹的什么算法？如果K值為5,針對下圖所示二叉樹,運行下列算法,輸出是什么？比較幾次得到結(jié)果？VoidBstree::Search<KeyTypeK>{intflag=0;BstNode*q=root,*p=NULL;while<<q!=NULL>&&<flag==0>>7878524929elseif<K<q->key>{p=q;q=q->lch;}else{p=q;q=q->rch;}}if<flag==0>cout<<"\n查找失敗,無此結(jié)點！\n";elsecout<<"\n查找成功,找到："<<q->key<<endl;}13.voidAA<LNode*HL,constElemType&item>{LNode*newptr=newLnode;newptr->data=item;LNode*p=HL;while<p->next!=HL>p=p->next;newptr->next=HL;p->next=newptr;}對于結(jié)點類型為LNode的單鏈表,以上算法的功能為：14.voidBB<List&L>{inti=0;while<i<L.size>{intj=i+1;while<j<L.size>{if<L.list[j]==L.list>{for<intk=j+1;k<L.size;k++>L.list[k-1]=L.list[k];L.size--;}elsej++;}i++;}}以上算法的功能為：15.voidCC<BTreeNode*&BST>{ElemTypea[6]={45,23,78,35,77,25}；BST=NULL；for<inti=0,i<6;i++>Insert<BST,a[i]>;}調(diào)用該算法后,生成的二叉搜索數(shù)的中序序列為：16.voidDD<>{ElemTypeA[]={1,3,5,7,9,2,4,6,8,10},B[10];TwoMerge<A,B,0,4,9>;for<inti=0;i<10;i++>cout<<B[i]<<"";cout<<endl;}調(diào)用該算法后,輸出結(jié)果為：17.template<classType>intSeqList<Type>::Insert<Type&x,inti>{if<i<0||i>last+1||last==MaxSize-1>return0;else{Last++;for<intj=last;j<i;j-->data[j]=data[j-1];data[i]=x;return1;}}對于結(jié)點類型為SeqList的順序表,以上算法的功能為：算法設計題：1.編寫復制一棵二叉樹的非遞歸算法。aaHeadbbc^ed77Head97b15^5026boolFind〔BtreeNode*BST,ElemType&item《數(shù)據(jù)結(jié)構(gòu)》課程復習參考答案一、填空題：1.4,102.n3.1,24.線性結(jié)構(gòu)樹型結(jié)構(gòu)圖型結(jié)構(gòu)5.n<n-1>/2n<n-1>6.增加17.O<log2n>O<nlog2n>8.歸并9.n-110.左右子樹空11.122512.n<n-1>/213.head<A>14.節(jié)省空間15.L->next=L->prior或L->next=L16.104417.入棧〔插入出棧〔刪除18.前驅(qū)結(jié)點后繼結(jié)點19.中序序列20.順序存儲結(jié)構(gòu)有序的21.O<n>O<1>22.行號列號23.3x2.45／6－*＋24.<3h-1>/225.n3O<n3>26.零個字符的串零27.鄰接矩陣鄰接表28.sp29.q->nextq30.兩個串的長度相等且對應位置的字符相同31.200+〔6*20+12=32632.1000+<<18-10>*6+<9-5>>*4=120833.<1>.<b><2>.<d>34.求矩陣第i列非零元素之和35.將矩陣第i行全部置為零36.2.2;4;〔23,38,1537.堆排序、快速排序、歸并排序、歸并排序、快速排序、堆排序38.f<n>39.O<n>40.1041.棧頂42.343.邏輯結(jié)構(gòu)44.n/245.先進先出46.7947.中序48.n-149.快速排序50.head->next==NULL51.10,13,27,76,65,97,3852.入度為零53.非線性結(jié)構(gòu)54.p->next=p->next->next55.<rear-front+n>%n56.〔n-m+1×m57.<<<b>,j,<<<d>>>>>58.16659.隊列二、單項選擇題：1.B2.B3.B4.C5.B6.B7.D8.A9.C10.D11.B12.B13.A14.D15.A16.A17.C18.C19.D20.D21.B22.D23.A24.C25①.B25②.A26.B27.B28.D29.A30.A31.B32.B33.A34.D35.B36.B37.D38.A39.A40.B41.B42.A43.D44.B45.A46.B47.C48.B49.B5