2018年-2018數(shù)據(jù)結構?？茝土曨}資料全

...wd......wd......wd...數(shù)據(jù)構造課程復習資料一、填空題：1.設需要對5個不同的記錄關鍵字進展排序，那么至少需要比較4次，至多需要比較10次。2.設二叉排序樹的高度為h，那么在該樹中查找關鍵字key最多需要比較n次。3.設在長度為20的有序表中進展二分查找，那么比較一次查找成功的結點數(shù)有1個，比較兩次查找成功有結點數(shù)有2個。4.數(shù)據(jù)構造從邏輯上劃分為三種基本類型：線性構造、樹型構造和圖型構造。5.在一個具有n個頂點的無向完全圖中，包含有n(n-1)/2條邊，在一個具有n個頂點的有向完全圖中，包含有n(n-1)條邊。6.向一棵B_樹插入元素的過程中，假設最終引起樹根結點的分裂，那么新樹比原樹的高度增加1。7.在堆排序的過程中，對任一分支結點進展篩運算的時間復雜度為O(log2n)，整個堆排序過程的時間復雜度為O(nlog2n)。8.在快速排序、堆排序、歸并排序中，歸并排序是穩(wěn)定的。9.在有n個葉子結點的哈夫曼樹中，總結點數(shù)是n-1。評卷人得分10.一棵樹T采用二叉鏈表存儲，如果樹T中某結點為葉子結點，那么在二叉鏈表BT中所對應的結點一定左右子樹空。11.數(shù)組A［１０］［１０］為對稱矩陣，其中每個元素占5個單元。現(xiàn)將其下三角局部按行優(yōu)先次序存儲在起始地址為1000的連續(xù)的內存單元中，那么元素A［5，6］對應的地址是1225。12.在有n個結點的無向圖中，其邊數(shù)最多為n(n-1)/2。13.取出廣義表A=(x,(a,b,c,d))中原子x的函數(shù)是head(A)。14.對矩陣采用壓縮存儲是為了節(jié)省空間。15.帶頭結點的雙循環(huán)鏈表L為空表的條件是L->next=L->prior或L->next=L。16.設線性表中元素的類型是實型，其首地址為1024，那么線性表中第6個元素的存儲位置是1044。17.對于順序存儲的棧，因為棧的空間是有限的，在進展入?！膊迦搿尺\算時，可能發(fā)生棧的上溢，在進展出?！矂h除〕運算時，可能發(fā)生棧的下溢。18.在雙向鏈表中，每個結點有兩個指針域，一個指向前驅結點，另一個指向后繼結點。19.由一棵二叉樹的前序序列和中序序列可唯一確定這棵二叉樹。20.折半查找的存儲構造僅限于順序存儲構造，且是有序的。21.對于一個順序存儲的線性表，在表頭插入元素的時間復雜度為O(n),在表尾插入元素的時間復雜度為O(1)。22.在稀疏距陣所對應的三元組線形表中，每個三元組元素按行號為主序，列號為輔序的次序排列。23.中綴表達示3+X*〔2.4/5-6〕所對應的后綴表達示為3x2.45／6－*＋。24.在一棵高度為h的3叉樹中，最多含有(3h-1)/2結點。25.分析下面算法〔程序段〕，給出最大語句頻度n3，該算法的時間復雜度是O(n3)。for(i=0;i<n;i++)for(j=0;j<n;j++)A[i][j]=0;26.空串是零個字符的串，其長度等于零。27.一個圖的鄰接矩陣表示法是唯一的，而鄰接表表示法是不唯一的。28.在一個單鏈表中p所指結點之前插入一個s(值為e)所指結點時，可執(zhí)行如下操作：q=head;while(q->next!=p)q=q->next;s=newNode;s->data=e;q->next=s;//填空s->next=p;//填空29.在一個單鏈表中刪除p所指結點的后繼結點時，應執(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.求以下廣義表操作的結果：(1)GetTail[GetHead[((a,b),(c,d))]];(b)(2)GetTail[GetHead[GetTail[((a,b),(c,d))]]](d)34.一個有向圖的鄰接矩陣表示，計算第i個結點的入度的方法是求矩陣第i列非零元素之和。35.一個圖的鄰接矩陣表示，刪除所有從第i個結點出發(fā)的邊的方法是將矩陣第i行全部置為零。36.在利用快速排序方法對一組記錄〔54，38，96，23，15，72，60，45，83〕進展快速排序時，遞歸調用而使用的棧所能到達的最大深度為2，共需遞歸調用的次數(shù)為4，其中第二次遞歸調用是對〔23，38，15〕組記錄進展快速排序。37.在堆排序，快速排序和歸并排序中，假設只從存儲空間考慮，那么應首先選取堆排序方法，其次選取快速排序方法，最后選取歸并排序方法；假設只從排序結果的穩(wěn)定性考慮，那么應選取歸并排序方法；假設只從平均情況下排序最快考慮，那么應選取快速排序方法；假設只從最壞情況下排序最快并且要節(jié)省內存考慮，那么應選取堆排序方法。38.稱算法的時間復雜度為O(f(n))，其含義是指算法的執(zhí)行時間和f(n)的數(shù)量級一樣。39.在一個長度為n的單鏈表L中，刪除鏈表中*p的前驅結點的時間復雜度為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ù)構造一般包括三個方面內容：數(shù)據(jù)的邏輯構造，數(shù)據(jù)的存儲構造及數(shù)據(jù)的運算。44.在包含n個結點的順序表上做等概率插入運算，平均要移動n/2個結點。45.隊列的特性是先進先出。46.二叉樹中葉子數(shù)為30，僅有一個孩子的結點數(shù)為20，那么總結點數(shù)為79。47.中序遍歷二叉排序樹中的結點可以得到一個遞增的關鍵字序列〔選填“先序〞、“中序〞或“后序〞〕。48.n個節(jié)點的連通圖至少有n-1條邊。49.在堆排序和快速排序中，如果從平均情況下排序的速度最快的角度來考慮，應最好選擇快速排序排序。50.帶有一個頭結點的單鏈表head為空的條件是〔假設指針域的名稱為next〕head->next==NULL。51.設一組初始關鍵字序列為(38，65，97，76，13，27，10)，那么第3趟簡單項選擇擇排序后的結果為10,13,27,76,65,97,38。52.在拓撲排序中，拓撲序列的第一個頂點必定是入度為零的頂點。53.數(shù)據(jù)的邏輯構造分為兩大類，它們是線性構造和非線性構造。54.在單鏈表中〔假設結點指針域名稱為next〕，刪除指針P所指結點的后繼結點的語句是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ū)，應是一個隊列構造。二、單項選擇題：1.隊列的特點是[B]A.先進后出B.先進先出C.任意位置進出D.前面都不正確2.[B]A.nB.dC.rD.n-d3.在二叉樹結點的先序序列、中序序列和后序序列中，所有葉子結點的先后順序[B]A.都不一樣B.完全一樣C.先序和中序一樣，而與后序不同D.中序和后序一樣，而與先序不同4.設有198個初始歸并段，如采用K-路平衡歸并三遍完成排序，那么K值最大為[C]A.12B.13C.14D.155.下面關于廣義表的表達中，不正確的選項是[B]A.廣義表可以是一個多層次的構造B.廣義表至少有一個元素C.廣義表可以被其他廣義表所共享D.廣義表可以是一個遞歸表6.設二叉樹根結點的層次為0，一棵深度〔高度〕為k的滿二叉樹和同樣深度完全二叉樹各有f個結點和c個結點，以下關系式不正確的選項是[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.以下文件的物理構造中，不利于文件長度動態(tài)增長的文件物理構造是[A]A.順序構造B.鏈接構造C.索引構造D.Hash構造9.在數(shù)據(jù)構造中，數(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〔1〕B.O〔log2n〕C.O〔n〕D.O〔n2〕12.哈夫曼樹中一定不存在[B]A.度為0的結點B.度為1的結點C.度為2的結點D.帶權的結點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.以下關于二叉樹遍歷的表達中，正確的選項是[A]A.假設一個葉子是某二叉樹的中序遍歷的最后一個結點，那么它必是該二叉樹的前序遍歷最后一個結點B.假設一個結點是某二叉樹的前序遍歷最后一個結點，那么它必是該二叉樹的中序遍歷的最后一個結點C.假設一個結點是某二叉樹的中序遍歷的最后一個結點，那么它必是該二叉樹的前序最后一個結點D.假設一個樹葉是某二叉樹的前序最后一個結點，那么它必是該二叉樹的中序遍歷最后一個結點16.第K層二叉樹的結點總數(shù)最多為[A]A.2k-1B.2k+1C.2K-1D.2k-117.線性表進展二分法查找，其前提條件是[C]A.線性表以鏈接方式存儲，并且按關鍵碼值排好序B.線性表以順序方式存儲，并且按關鍵碼值的檢索頻率排好序C.線性表以順序方式存儲，并且按關鍵碼值排好序D.線性表以鏈接方式存儲，并且按關鍵碼值的檢索頻率排好序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.以下關于數(shù)據(jù)構造的表達中，正確的選項是[D]A.數(shù)組是不同類型值的集合B.遞歸算法的程序構造比迭代算法的程序構造更為精煉C.樹是一種線性構造D.用一維數(shù)組存儲一棵完全二叉樹是有效的存儲方法21.以下數(shù)據(jù)構造中哪一個是線性構造[B]A.有向圖B.隊列C.線索二叉樹D.B樹22.在一個單鏈表HL中，假設要在當前由指針p指向的結點后面插入一個由q指向的結點，那么執(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ù)存放在存儲器內，該數(shù)組按列存放時，元素A[4][7]的起始地址為[B]A.SA+141B.SA+180C.SA+222D.SA+22528.某二叉樹的前序遍歷結點訪問順序是abdgcefh，中序遍歷的結點訪問順序是dgbaechf，那么其后序遍歷的結點訪問順序是[D]A.bdgcefhaB.gdbecfhaC.bdgaechfD.gdbehfca29.在一非空二叉樹的中序遍歷序列中，根結點的右邊[A]A.只有右子樹上的所有結點B.只有右子樹上的局部結點C.只有左子樹上的局部結點D.只有左子樹上的所有結點30.具有6個頂點的無向圖至少應有〔〕條邊才能確保是一個連通圖。[A]A.5B.6C.7D.831.二分查找和二叉排序樹的時間性能[B]A.一樣B.不一樣32.采用二分查找方法查找長度為n的線性表時，每個元素的平均查找長度為[B]A.O〔n2〕B.O(nlog2n)C.O(n)D.O(log2n)33.在待排序的元素序列基本有序的前提下，效率最高的排序方法是[A]A.插入排序B.選擇排序C.快速排序D.歸并排序34.下述幾種排序方法中，要求內存量最大的是[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ù)存放在存儲器內，該數(shù)組按列存放時，元素A[4][7]的起始地址為[B]A.SA+141B.SA+180C.SA+222D.SA+22537.某二叉樹的前序遍歷結點訪問順序是abdgcefh，中序遍歷的結點訪問順序是dgbaechf，那么其后序遍歷的結點訪問順序是[D]A.bdgcefhaB.gdbecfhaC.bdgaechfD.gdbehfca38.在一非空二叉樹的中序遍歷序列中，根結點的右邊[A]A.只有右子樹上的所有結點B.只有右子樹上的局部結點C.只有左子樹上的局部結點D.只有左子樹上的所有結點39.具有6個頂點的無向圖至少應有〔〕條邊才能確保是一個連通圖。[A]A.5B.6C.7D.840.二分查找和二叉排序樹的時間性能[B]A.一樣B.不一樣C.可能一樣D.不確定41.采用二分查找方法查找長度為n的線性表時，每個元素的平均查找長度為[B]A.O〔n2〕B.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.對一個算法的評價，不包括如下〔〕方面的內容。[B]A.強健性和可讀性B.并行性C.正確性D.時空復雜度45.在帶有頭結點的單鏈表HL中，要向表頭插入一個由指針p指向的結點，那么執(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.在稀疏矩陣的帶行指針向量的鏈接存儲中，每個單鏈表中的結點都具有一樣的[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個結點，現(xiàn)要求插入一個新結點后使得單鏈表仍然保持有序，那么該操作的時間復雜度為[D]A.O(log2n)B.O(1)C.O(n2)D.O(n)55.設一棵m叉樹中度數(shù)為0的結點數(shù)為N0，度數(shù)為1的結點數(shù)為Nl，……，度數(shù)為m的結點數(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ù)存放在存儲器內，該數(shù)組按行存放時，數(shù)組元素A[7][4]的起始地址為[C]A.SA+141B.SA+144C.SA+222D.SA+22557.如果某二叉樹的前根次序遍歷結果為stuwv，中序遍歷為uwtvs，那么該二叉樹的后序為[B]A.uwvtsB.vwutsC.wuvtsD.wutsv58.深度為5的二叉樹至多有〔〕個結點。[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〔n2〕B.O(nlog2n)C.O(n)D.O(log2n)62.下述幾種排序方法中，要求內存量最大的是[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個表項的散列表，用線性探查法解決沖突，按關鍵碼查詢時找到一個表項的平均探查次數(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ù)構造形式定義為二元組(K，R)，其中K是數(shù)據(jù)元素的有限集合，那么R是K上[B]A.操作的有限集合B.映象的有限集合C.類型的有限集合D.關系的有限集合71.以以下列圖示的順序存儲構造表示的二叉樹是[A]72.由同一關鍵字集合構造的各棵二叉排序樹[B]A.其形態(tài)不一定一樣，但平均查找長度一樣B.其形態(tài)不一定一樣，平均查找長度也不一定一樣C.其形態(tài)均一樣，但平均查找長度不一定一樣D.其形態(tài)均一樣，平均查找長度也都一樣73.ISAM文件和VSAM文件的區(qū)別之一是[C]A.前者是索引順序文件，后者是索引非順序文件B.前者只能進展順序存取，后者只能進展隨機存取C.前者建設靜態(tài)索引構造，后者建設動態(tài)索引構造D.前者的存儲介質是磁盤，后者的存儲介質不是磁盤74.以下描述中正確的選項是[D]A.線性表的邏輯順序與存儲順序總是一致的B.每種數(shù)據(jù)構造都具備三個基本運算：插入、刪除和查找C.數(shù)據(jù)構造實質上包括邏輯構造和存儲構造兩方面的內容D.選擇適宜的數(shù)據(jù)構造是解決應用問題的關鍵步驟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.區(qū)分數(shù)據(jù)構造的合理性B.評價算法的效率C.研究算法中輸入與輸出的關系D.鑒別算法的可讀性78.在線性表的以下運算中，不改變數(shù)據(jù)元素之間構造關系的運算是[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個結點的單鏈表中查找其值等于x的結點，在查找成功的情況下，平均需要比較〔〕個結點。[C]A.nB.n/2C.(n+1)/2D.(n-1)/283.在任意一棵二叉樹的前序序列和后序序列中，各葉子之間的相對次序關系[D]A.不一定一樣B.互為逆序C.都不一樣D.都一樣84.高度為5的二叉樹至多有結點數(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ù)元素的關系進展查找的方法。[C]A.有序表的查找B.二叉排序樹的查找C.平衡二叉樹D.散列查找91.下述幾種排序方法中，要求內存量最大的是[B]A.插入排序B.快速排序C.歸并排序D.選擇排序92.在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的〔〕倍。[B]A.1/2B.1C.2D.493.在帶有頭結點的單鏈表HL中，要向表頭插入一個由指針p指向的結點，那么執(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.在稀疏矩陣的帶行指針向量的鏈接存儲中，每個單鏈表中的結點都具有一樣的[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個結點，現(xiàn)要求插入一個新結點后使得單鏈表仍然保持有序，那么該操作的時間復雜度為[D]A.O(log2n)B.O(1)C.O(n2)D.O(n)103.設一棵m叉樹中度數(shù)為0的結點數(shù)為N0，度數(shù)為1的結點數(shù)為Nl，……，度數(shù)為m的結點數(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.帶權有向圖B.連通無向圖C.有向無環(huán)圖D.無向圖107.在一個具有n個結點的有序單鏈表中插入一個新結點并仍然保持有序的時間復雜度是[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.一棵二叉樹的先序、中序和后序序列分別如下，其中有一局部未顯示出來。試求出空格處的內容，并畫出該二叉樹。先序序列：BFICEHG中序序列：DKFIAEJC后序序列：KFBHJGA3.畫出以下樹對應的二叉樹，并寫出其先根遍歷序列：BBDFCAEG4.將關鍵字序列為{54，29，37，86，71，91，8，31，44，26}進展歸并排序，寫出各趟詳細過程。5.試列出如以以下列圖中全部可能的拓撲排序序列。6.設某通信系統(tǒng)使用A，B，C，D，E，F(xiàn)，G，H八個字符，他們出現(xiàn)的概率w={5，29，7，8，14，23，3，11}，試構造對應的哈夫曼樹〔請按左子樹根結點的權小于右子樹樹根結點的權的次序構造〕。7.給定表〔119，14，22，1，66，21，83，27，56，13，10〕,請按表中元素的順序構造一棵平衡二叉樹，并求其在等概率情況下查找成功的平均長度。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，給定的關鍵碼序列為19，14，23，01，68，20，84，27。試畫出用線性探查法解決沖突時所構成的散列表。012345678910111210.對7個關鍵字進展快速排序，在最好的情況下僅需進展10次關鍵字的比較。(1)假設關鍵字集合為{1,2,3,4,5,6,7}，試舉出能到達上述結果的初始關鍵字序列；(2)對所舉序列進展快速排序，寫出排序過程。11.如以下列圖二叉樹，答復以下問題。12.畫出在一個初始為空的AVL樹中依次插入3,1,4,6,9,8,5,7時每一插入后AVL樹的形態(tài)。假設做了某種旋轉，說明旋轉的類型。然后，給出在這棵插入后得到的AVL樹中刪去根結點后的結果。13.一組記錄的排序碼為〔46，79，56，38，40，80,95，24〕，寫出對其進展快速排序的每一次劃分結果。14.一個線性表為B=〔12，23，45，57，20，03，78，31，15，36〕，設散列表為HT[0..12]，散列函數(shù)為H〔key〕=key%13并用線性探查法解決沖突，請畫出散列表，并計算等概率情況下查找成功的平均查找長度。15.一棵二叉樹的前序遍歷的結果序列是ABECDFGHIJ，中序遍歷的結果是EBCDAFHIGJ，試寫出這棵二叉樹的后序遍歷結果。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.試畫出下面帶權無向圖的一棵最小生成樹。55768432997abdcef19.關鍵字序列為：{03,87,12,61,98,70,61*，97,27,53,42，56，77，}請采用希爾(Shell)排序法對該序列作非遞減排序.按5，3，1分組，寫出以下標明的趟的結果。初始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;}對于結點類型為LNode的單鏈表，以上算法的功能為：2.intAA(LNode*HL,ElemTypex){intn=0;LNode*p=HL;while(p!=NULL){if(p->data==x)n++;p=p->next;}returnn;}對于結點類型為LNode的單鏈表，以上算法的功能為：3.假定從鍵盤上輸入一批整數(shù)，依次為：786345309134–1，請寫出輸出結果。#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;}該算法的輸出結果為：_____________。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//結點構造structSnode//結點構造{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);}假定調用該算法時以HL為表頭指針的單鏈表中的內容為〔15，26，48，55〕，那么調用返回后該單鏈表中的內容為：____________。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//結點構造structSnode//結點構造{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，針對以以下列圖所示二叉樹，運行以下算法，輸出是什么比較幾次得到結果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查找失敗，無此結點！\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;}對于結點類型為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]);}調用該算法后，生成的二叉搜索數(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;}調用該算法后，輸出結果為：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;}}對于結點類型為SeqList的順序表，以上算法的功能為：算法設計題：1.編寫復制一棵二叉樹的非遞歸算法。aaHeadbbc^ed77Head97b15^5026boolFind〔BtreeNode*BST，ElemType&item〕數(shù)據(jù)構造課程復習參考答案一、填空題：1.4，102.n3.1，24.線性構造樹型構造圖型構造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.入?！膊迦搿吵鰲！矂h除〕18.前驅結點后繼結點19.中序序列20.順序存儲構造有序的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，15〕37.堆排序、快速排序、歸并排序、歸并排序、快速排序、堆排序38.f(n)39.O(n)40.1041.棧頂42.343.邏輯構造44.n/245.先進先出46.7947.中序48.n-149.快速排序50.head->next==NULL51.10,13,27,76,65,97,3852.入度為零53.非線性構造54.p->next=p->next->next55.(rear-front+n)%n56.〔n-m+1〕×m57.(((b),j,(((d)))))58.16659.隊列二、單項選擇題：1.B2.B3.B4.C5.B