2018年-2018數(shù)據(jù)結(jié)構(gòu)專(zhuān)科復(fù)習(xí)題資料全

...wd......wd......wd...數(shù)據(jù)構(gòu)造課程復(fù)習(xí)資料一、填空題：1.設(shè)需要對(duì)5個(gè)不同的記錄關(guān)鍵字進(jìn)展排序，那么至少需要比較4次，至多需要比較10次。2.設(shè)二叉排序樹(shù)的高度為h，那么在該樹(shù)中查找關(guān)鍵字key最多需要比較n次。3.設(shè)在長(zhǎng)度為20的有序表中進(jìn)展二分查找，那么比較一次查找成功的結(jié)點(diǎn)數(shù)有1個(gè)，比較兩次查找成功有結(jié)點(diǎn)數(shù)有2個(gè)。4.數(shù)據(jù)構(gòu)造從邏輯上劃分為三種基本類(lèi)型：線性構(gòu)造、樹(shù)型構(gòu)造和圖型構(gòu)造。5.在一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向完全圖中，包含有n(n-1)/2條邊，在一個(gè)具有n個(gè)頂點(diǎn)的有向完全圖中，包含有n(n-1)條邊。6.向一棵B_樹(shù)插入元素的過(guò)程中，假設(shè)最終引起樹(shù)根結(jié)點(diǎn)的分裂，那么新樹(shù)比原樹(shù)的高度增加1。7.在堆排序的過(guò)程中，對(duì)任一分支結(jié)點(diǎn)進(jìn)展篩運(yùn)算的時(shí)間復(fù)雜度為O(log2n)，整個(gè)堆排序過(guò)程的時(shí)間復(fù)雜度為O(nlog2n)。8.在快速排序、堆排序、歸并排序中，歸并排序是穩(wěn)定的。9.在有n個(gè)葉子結(jié)點(diǎn)的哈夫曼樹(shù)中，總結(jié)點(diǎn)數(shù)是n-1。評(píng)卷人得分10.一棵樹(shù)T采用二叉鏈表存儲(chǔ)，如果樹(shù)T中某結(jié)點(diǎn)為葉子結(jié)點(diǎn)，那么在二叉鏈表BT中所對(duì)應(yīng)的結(jié)點(diǎn)一定左右子樹(shù)空。11.數(shù)組A［１０］［１０］為對(duì)稱(chēng)矩陣，其中每個(gè)元素占5個(gè)單元。現(xiàn)將其下三角局部按行優(yōu)先次序存儲(chǔ)在起始地址為1000的連續(xù)的內(nèi)存單元中，那么元素A［5，6］對(duì)應(yīng)的地址是1225。12.在有n個(gè)結(jié)點(diǎn)的無(wú)向圖中，其邊數(shù)最多為n(n-1)/2。13.取出廣義表A=(x,(a,b,c,d))中原子x的函數(shù)是head(A)。14.對(duì)矩陣采用壓縮存儲(chǔ)是為了節(jié)省空間。15.帶頭結(jié)點(diǎn)的雙循環(huán)鏈表L為空表的條件是L->next=L->prior或L->next=L。16.設(shè)線性表中元素的類(lèi)型是實(shí)型，其首地址為1024，那么線性表中第6個(gè)元素的存儲(chǔ)位置是1044。17.對(duì)于順序存儲(chǔ)的棧，因?yàn)闂５目臻g是有限的，在進(jìn)展入?！膊迦搿尺\(yùn)算時(shí)，可能發(fā)生棧的上溢，在進(jìn)展出棧〔刪除〕運(yùn)算時(shí)，可能發(fā)生棧的下溢。18.在雙向鏈表中，每個(gè)結(jié)點(diǎn)有兩個(gè)指針域，一個(gè)指向前驅(qū)結(jié)點(diǎn)，另一個(gè)指向后繼結(jié)點(diǎn)。19.由一棵二叉樹(shù)的前序序列和中序序列可唯一確定這棵二叉樹(shù)。20.折半查找的存儲(chǔ)構(gòu)造僅限于順序存儲(chǔ)構(gòu)造，且是有序的。21.對(duì)于一個(gè)順序存儲(chǔ)的線性表，在表頭插入元素的時(shí)間復(fù)雜度為O(n),在表尾插入元素的時(shí)間復(fù)雜度為O(1)。22.在稀疏距陣所對(duì)應(yīng)的三元組線形表中，每個(gè)三元組元素按行號(hào)為主序，列號(hào)為輔序的次序排列。23.中綴表達(dá)示3+X*〔2.4/5-6〕所對(duì)應(yīng)的后綴表達(dá)示為3x2.45／6－*＋。24.在一棵高度為h的3叉樹(shù)中，最多含有(3h-1)/2結(jié)點(diǎn)。25.分析下面算法〔程序段〕，給出最大語(yǔ)句頻度n3，該算法的時(shí)間復(fù)雜度是O(n3)。for(i=0;i<n;i++)for(j=0;j<n;j++)A[i][j]=0;26.空串是零個(gè)字符的串，其長(zhǎng)度等于零。27.一個(gè)圖的鄰接矩陣表示法是唯一的，而鄰接表表示法是不唯一的。28.在一個(gè)單鏈表中p所指結(jié)點(diǎn)之前插入一個(gè)s(值為e)所指結(jié)點(diǎn)時(shí)，可執(zhí)行如下操作：q=head;while(q->next!=p)q=q->next;s=newNode;s->data=e;q->next=s;//填空s->next=p;//填空29.在一個(gè)單鏈表中刪除p所指結(jié)點(diǎn)的后繼結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行以下操作：q=p->next;p->next=q->next;//填空deleteq;//填空30.兩個(gè)串相等的充分必要條件是兩個(gè)串的長(zhǎng)度相等且對(duì)應(yīng)位置的字符一樣。31.二維數(shù)組A[10][20]采用列序?yàn)橹鞣绞酱鎯?chǔ)，每個(gè)元素占一個(gè)存儲(chǔ)單元并且A[0][0]的存儲(chǔ)地址是200，那么A[6][12]的地址是200+〔6*20+12〕=326。32.二維數(shù)組A[10..20][5..10]采用行序?yàn)橹鞣绞酱鎯?chǔ)，每個(gè)元素占4個(gè)存儲(chǔ)單元，并且A[10][5]的存儲(chǔ)地址是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.一個(gè)有向圖的鄰接矩陣表示，計(jì)算第i個(gè)結(jié)點(diǎn)的入度的方法是求矩陣第i列非零元素之和。35.一個(gè)圖的鄰接矩陣表示，刪除所有從第i個(gè)結(jié)點(diǎn)出發(fā)的邊的方法是將矩陣第i行全部置為零。36.在利用快速排序方法對(duì)一組記錄〔54，38，96，23，15，72，60，45，83〕進(jìn)展快速排序時(shí)，遞歸調(diào)用而使用的棧所能到達(dá)的最大深度為2，共需遞歸調(diào)用的次數(shù)為4，其中第二次遞歸調(diào)用是對(duì)〔23，38，15〕組記錄進(jìn)展快速排序。37.在堆排序，快速排序和歸并排序中，假設(shè)只從存儲(chǔ)空間考慮，那么應(yīng)首先選取堆排序方法，其次選取快速排序方法，最后選取歸并排序方法；假設(shè)只從排序結(jié)果的穩(wěn)定性考慮，那么應(yīng)選取歸并排序方法；假設(shè)只從平均情況下排序最快考慮，那么應(yīng)選取快速排序方法；假設(shè)只從最壞情況下排序最快并且要節(jié)省內(nèi)存考慮，那么應(yīng)選取堆排序方法。38.稱(chēng)算法的時(shí)間復(fù)雜度為O(f(n))，其含義是指算法的執(zhí)行時(shí)間和f(n)的數(shù)量級(jí)一樣。39.在一個(gè)長(zhǎng)度為n的單鏈表L中，刪除鏈表中*p的前驅(qū)結(jié)點(diǎn)的時(shí)間復(fù)雜度為O(n)。40.假設(shè)為循環(huán)隊(duì)列分配的向量空間為Q[20]，假設(shè)隊(duì)列的長(zhǎng)度和隊(duì)頭指針值分別為13和17，那么當(dāng)前尾指針的值為10。41.對(duì)于棧只能在棧頂插入和刪除元素。42.設(shè)有一個(gè)順序棧S，元素sl，s2，s3，s4，s5，s6依次進(jìn)棧，如果6個(gè)元素的出棧順序?yàn)閟2，s3，s4，s6，s5，sl，那么順序棧的容量至少應(yīng)為3。43.數(shù)據(jù)構(gòu)造一般包括三個(gè)方面內(nèi)容：數(shù)據(jù)的邏輯構(gòu)造，數(shù)據(jù)的存儲(chǔ)構(gòu)造及數(shù)據(jù)的運(yùn)算。44.在包含n個(gè)結(jié)點(diǎn)的順序表上做等概率插入運(yùn)算，平均要移動(dòng)n/2個(gè)結(jié)點(diǎn)。45.隊(duì)列的特性是先進(jìn)先出。46.二叉樹(shù)中葉子數(shù)為30，僅有一個(gè)孩子的結(jié)點(diǎn)數(shù)為20，那么總結(jié)點(diǎn)數(shù)為79。47.中序遍歷二叉排序樹(shù)中的結(jié)點(diǎn)可以得到一個(gè)遞增的關(guān)鍵字序列〔選填“先序〞、“中序〞或“后序〞〕。48.n個(gè)節(jié)點(diǎn)的連通圖至少有n-1條邊。49.在堆排序和快速排序中，如果從平均情況下排序的速度最快的角度來(lái)考慮，應(yīng)最好選擇快速排序排序。50.帶有一個(gè)頭結(jié)點(diǎn)的單鏈表head為空的條件是〔假設(shè)指針域的名稱(chēng)為next〕head->next==NULL。51.設(shè)一組初始關(guān)鍵字序列為(38，65，97，76，13，27，10)，那么第3趟簡(jiǎn)單項(xiàng)選擇擇排序后的結(jié)果為10,13,27,76,65,97,38。52.在拓?fù)渑判蛑?，拓?fù)湫蛄械牡谝粋€(gè)頂點(diǎn)必定是入度為零的頂點(diǎn)。53.數(shù)據(jù)的邏輯構(gòu)造分為兩大類(lèi)，它們是線性構(gòu)造和非線性構(gòu)造。54.在單鏈表中〔假設(shè)結(jié)點(diǎn)指針域名稱(chēng)為next〕，刪除指針P所指結(jié)點(diǎn)的后繼結(jié)點(diǎn)的語(yǔ)句是p->next=p->next->next。55.循環(huán)隊(duì)列用數(shù)組data[n]存儲(chǔ)元素值，用front,rear分別作為頭尾指針，那么當(dāng)前元素個(gè)數(shù)為(rear-front+n)%n。56.假設(shè)n為主串長(zhǎng)，m為子串長(zhǎng)，那么串的樸素匹配算法最壞的情況下需要比較字符的總次數(shù)〔n-m+1〕×m。57.廣義表((a),((b),j,(((d)))))的表尾是(((b),j,(((d)))))。58.二叉樹(shù)有61個(gè)葉子節(jié)點(diǎn)，且僅有一個(gè)孩子的節(jié)點(diǎn)數(shù)為45，那么總節(jié)點(diǎn)數(shù)為166。59.解決計(jì)算機(jī)與打印機(jī)之間速度不匹配問(wèn)題，須要設(shè)置一個(gè)數(shù)據(jù)緩沖區(qū)，應(yīng)是一個(gè)隊(duì)列構(gòu)造。二、單項(xiàng)選擇題：1.隊(duì)列的特點(diǎn)是[B]A.先進(jìn)后出B.先進(jìn)先出C.任意位置進(jìn)出D.前面都不正確2.[B]A.nB.dC.rD.n-d3.在二叉樹(shù)結(jié)點(diǎn)的先序序列、中序序列和后序序列中，所有葉子結(jié)點(diǎn)的先后順序[B]A.都不一樣B.完全一樣C.先序和中序一樣，而與后序不同D.中序和后序一樣，而與先序不同4.設(shè)有198個(gè)初始?xì)w并段，如采用K-路平衡歸并三遍完成排序，那么K值最大為[C]A.12B.13C.14D.155.下面關(guān)于廣義表的表達(dá)中，不正確的選項(xiàng)是[B]A.廣義表可以是一個(gè)多層次的構(gòu)造B.廣義表至少有一個(gè)元素C.廣義表可以被其他廣義表所共享D.廣義表可以是一個(gè)遞歸表6.設(shè)二叉樹(shù)根結(jié)點(diǎn)的層次為0，一棵深度〔高度〕為k的滿二叉樹(shù)和同樣深度完全二叉樹(shù)各有f個(gè)結(jié)點(diǎn)和c個(gè)結(jié)點(diǎn)，以下關(guān)系式不正確的選項(xiàng)是[B]A.f>=c B.c>fC.f=2k+1-aD.c>sk-17.從L=((apple,pear),(orange,banana))中，取出banana元素的表達(dá)式為[D]A.head(tail(L))B.head(head(tail(L)))C.tail(head(tail(L))) D.head(tail(head(tail(L))))8.以下文件的物理構(gòu)造中，不利于文件長(zhǎng)度動(dòng)態(tài)增長(zhǎng)的文件物理構(gòu)造是[A]A.順序構(gòu)造B.鏈接構(gòu)造C.索引構(gòu)造D.Hash構(gòu)造9.在數(shù)據(jù)構(gòu)造中，數(shù)據(jù)元素可由[C]A.實(shí)體B.域C.數(shù)據(jù)項(xiàng)D.字段10.，〔FloyD[D]A.O(1)B.O(n)C.O(n)D.O(n3)11.對(duì)n個(gè)記錄的文件進(jìn)展快速排序，所需要的輔助存儲(chǔ)空間為[B]A.O〔1〕B.O〔log2n〕C.O〔n〕D.O〔n2〕12.哈夫曼樹(shù)中一定不存在[B]A.度為0的結(jié)點(diǎn)B.度為1的結(jié)點(diǎn)C.度為2的結(jié)點(diǎn)D.帶權(quán)的結(jié)點(diǎn)13.下述哪一條是順序存儲(chǔ)方式的優(yōu)點(diǎn)[A]A.存儲(chǔ)密度大B.插入和刪除運(yùn)算方便C.獲取符合某種條件的元素方便D.查找運(yùn)算速度快14.有一個(gè)二維數(shù)組A[m][n]，假設(shè)A[0][0]存放位置在600(10)，A[3][3]存放位置在678(10)，每個(gè)元素占一個(gè)空間，問(wèn)A[2][3](10)存放在什么位置〔腳注(10)表示用10進(jìn)制表示，m>3〕[D]A.658B.648C.633D.65315.以下關(guān)于二叉樹(shù)遍歷的表達(dá)中，正確的選項(xiàng)是[A]A.假設(shè)一個(gè)葉子是某二叉樹(shù)的中序遍歷的最后一個(gè)結(jié)點(diǎn)，那么它必是該二叉樹(shù)的前序遍歷最后一個(gè)結(jié)點(diǎn)B.假設(shè)一個(gè)結(jié)點(diǎn)是某二叉樹(shù)的前序遍歷最后一個(gè)結(jié)點(diǎn)，那么它必是該二叉樹(shù)的中序遍歷的最后一個(gè)結(jié)點(diǎn)C.假設(shè)一個(gè)結(jié)點(diǎn)是某二叉樹(shù)的中序遍歷的最后一個(gè)結(jié)點(diǎn)，那么它必是該二叉樹(shù)的前序最后一個(gè)結(jié)點(diǎn)D.假設(shè)一個(gè)樹(shù)葉是某二叉樹(shù)的前序最后一個(gè)結(jié)點(diǎn)，那么它必是該二叉樹(shù)的中序遍歷最后一個(gè)結(jié)點(diǎn)16.第K層二叉樹(shù)的結(jié)點(diǎn)總數(shù)最多為[A]A.2k-1B.2k+1C.2K-1D.2k-117.線性表進(jìn)展二分法查找，其前提條件是[C]A.線性表以鏈接方式存儲(chǔ)，并且按關(guān)鍵碼值排好序B.線性表以順序方式存儲(chǔ)，并且按關(guān)鍵碼值的檢索頻率排好序C.線性表以順序方式存儲(chǔ)，并且按關(guān)鍵碼值排好序D.線性表以鏈接方式存儲(chǔ)，并且按關(guān)鍵碼值的檢索頻率排好序18.n個(gè)記錄進(jìn)展堆排序，所需要的輔助存儲(chǔ)空間為[C]A.O(1og2n)B.O(n)C.O(1)D.O(n2)19.線性表〔7，34，77，25，64，49，20，14〕進(jìn)展散列存儲(chǔ)時(shí)，假設(shè)選用H〔K〕=K%7作為散列函數(shù)，那么散列地址為0的元素有〔〕個(gè)。[D]A.1B.2C.3D.420.以下關(guān)于數(shù)據(jù)構(gòu)造的表達(dá)中，正確的選項(xiàng)是[D]A.數(shù)組是不同類(lèi)型值的集合B.遞歸算法的程序構(gòu)造比迭代算法的程序構(gòu)造更為精煉C.樹(shù)是一種線性構(gòu)造D.用一維數(shù)組存儲(chǔ)一棵完全二叉樹(shù)是有效的存儲(chǔ)方法21.以下數(shù)據(jù)構(gòu)造中哪一個(gè)是線性構(gòu)造[B]A.有向圖B.隊(duì)列C.線索二叉樹(shù)D.B樹(shù)22.在一個(gè)單鏈表HL中，假設(shè)要在當(dāng)前由指針p指向的結(jié)點(diǎn)后面插入一個(gè)由q指向的結(jié)點(diǎn)，那么執(zhí)行如下〔〕語(yǔ)句序列。[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.〔〕不是隊(duì)列的基本運(yùn)算。[A]A.在隊(duì)列第i個(gè)元素之后插入一個(gè)元素B.從隊(duì)頭刪除一個(gè)元素C.判斷一個(gè)隊(duì)列是否為空D.讀取隊(duì)頭元素的值24.假設(shè)一個(gè)棧的入棧序列是1，2，3，…，n，其輸出序列為p1，p2，p3，…，pn，假設(shè)p1=n，那么pi為[C]A.iB.n=iC.n-i+1D.不確定25.棧的特點(diǎn)是〔B〕，隊(duì)列的特點(diǎn)是〔A〕。A.先進(jìn)先出B.先進(jìn)后出26.設(shè)有兩個(gè)串p和q，求q在p中首次出現(xiàn)的位置的運(yùn)算稱(chēng)作[B]A.連接B.模式匹配C.求子串D.求串長(zhǎng)27.二維數(shù)組A中，每個(gè)元素A[i][j]的長(zhǎng)度為3個(gè)字節(jié)，行下標(biāo)i從0到7，列下標(biāo)j從0到9，從首地址SA開(kāi)場(chǎng)連續(xù)存放在存儲(chǔ)器內(nèi)，該數(shù)組按列存放時(shí)，元素A[4][7]的起始地址為[B]A.SA+141B.SA+180C.SA+222D.SA+22528.某二叉樹(shù)的前序遍歷結(jié)點(diǎn)訪問(wèn)順序是abdgcefh，中序遍歷的結(jié)點(diǎn)訪問(wèn)順序是dgbaechf，那么其后序遍歷的結(jié)點(diǎn)訪問(wèn)順序是[D]A.bdgcefhaB.gdbecfhaC.bdgaechfD.gdbehfca29.在一非空二叉樹(shù)的中序遍歷序列中，根結(jié)點(diǎn)的右邊[A]A.只有右子樹(shù)上的所有結(jié)點(diǎn)B.只有右子樹(shù)上的局部結(jié)點(diǎn)C.只有左子樹(shù)上的局部結(jié)點(diǎn)D.只有左子樹(shù)上的所有結(jié)點(diǎn)30.具有6個(gè)頂點(diǎn)的無(wú)向圖至少應(yīng)有〔〕條邊才能確保是一個(gè)連通圖。[A]A.5B.6C.7D.831.二分查找和二叉排序樹(shù)的時(shí)間性能[B]A.一樣B.不一樣32.采用二分查找方法查找長(zhǎng)度為n的線性表時(shí)，每個(gè)元素的平均查找長(zhǎng)度為[B]A.O〔n2〕B.O(nlog2n)C.O(n)D.O(log2n)33.在待排序的元素序列基本有序的前提下，效率最高的排序方法是[A]A.插入排序B.選擇排序C.快速排序D.歸并排序34.下述幾種排序方法中，要求內(nèi)存量最大的是[D]A.插入排序B.選擇排序C.快速排序D.歸并排序35.設(shè)有兩個(gè)串p和q，求q在p中首次出現(xiàn)的位置的運(yùn)算稱(chēng)作[B]A.連接B.模式匹配C.求子串D.求串長(zhǎng)36.二維數(shù)組A中，每個(gè)元素A[i][j]的長(zhǎng)度為3個(gè)字節(jié)，行下標(biāo)i從0到7，列下標(biāo)j從0到9，從首地址SA開(kāi)場(chǎng)連續(xù)存放在存儲(chǔ)器內(nèi)，該數(shù)組按列存放時(shí)，元素A[4][7]的起始地址為[B]A.SA+141B.SA+180C.SA+222D.SA+22537.某二叉樹(shù)的前序遍歷結(jié)點(diǎn)訪問(wèn)順序是abdgcefh，中序遍歷的結(jié)點(diǎn)訪問(wèn)順序是dgbaechf，那么其后序遍歷的結(jié)點(diǎn)訪問(wèn)順序是[D]A.bdgcefhaB.gdbecfhaC.bdgaechfD.gdbehfca38.在一非空二叉樹(shù)的中序遍歷序列中，根結(jié)點(diǎn)的右邊[A]A.只有右子樹(shù)上的所有結(jié)點(diǎn)B.只有右子樹(shù)上的局部結(jié)點(diǎn)C.只有左子樹(shù)上的局部結(jié)點(diǎn)D.只有左子樹(shù)上的所有結(jié)點(diǎn)39.具有6個(gè)頂點(diǎn)的無(wú)向圖至少應(yīng)有〔〕條邊才能確保是一個(gè)連通圖。[A]A.5B.6C.7D.840.二分查找和二叉排序樹(shù)的時(shí)間性能[B]A.一樣B.不一樣C.可能一樣D.不確定41.采用二分查找方法查找長(zhǎng)度為n的線性表時(shí)，每個(gè)元素的平均查找長(zhǎng)度為[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.對(duì)一個(gè)算法的評(píng)價(jià)，不包括如下〔〕方面的內(nèi)容。[B]A.強(qiáng)健性和可讀性B.并行性C.正確性D.時(shí)空復(fù)雜度45.在帶有頭結(jié)點(diǎn)的單鏈表HL中，要向表頭插入一個(gè)由指針p指向的結(jié)點(diǎn)，那么執(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.對(duì)線性表，在以下哪種情況下應(yīng)當(dāng)采用鏈表表示[B]A.經(jīng)常需要隨機(jī)地存取元素B.經(jīng)常需要進(jìn)展插入和刪除操作C.表中元素需要占據(jù)一片連續(xù)的存儲(chǔ)空間D.表中元素的個(gè)數(shù)不變47.一個(gè)棧的輸入序列為123，那么以下序列中不可能是棧的輸出序列的是[C]A.231B.321C.312D.12348.每一趟都能選出一個(gè)元素放在其最終位置上，并且不穩(wěn)定的排序算法是[B]A.冒泡排序B.簡(jiǎn)單項(xiàng)選擇擇排序C.希爾排序D.直接插入排序49.采用開(kāi)放定址法處理散列表的沖突時(shí)，其平均查找長(zhǎng)度[B]A.低于鏈接法處理沖突B.高于鏈接法處理沖突C.與鏈接法處理沖突一樣D.高于二分查找50.假設(shè)需要利用形參直接訪問(wèn)實(shí)參時(shí)，應(yīng)將形參變量說(shuō)明為〔〕參數(shù)。[D]A.值B.函數(shù)C.指針D.引用51.在稀疏矩陣的帶行指針向量的鏈接存儲(chǔ)中，每個(gè)單鏈表中的結(jié)點(diǎn)都具有一樣的[A]A.行號(hào)B.列號(hào)C.元素值D.非零元素個(gè)數(shù)52.快速排序在最壞情況下的時(shí)間復(fù)雜度為[D]A.O(log2n)B.O(nlog2n)C.O(n)D.O(n2)53.從二叉搜索樹(shù)中查找一個(gè)元素時(shí)，其時(shí)間復(fù)雜度大致為[C]A.O(n)B.O(1)C.O(log2n)D.O(n2)54.設(shè)一個(gè)有序的單鏈表中有n個(gè)結(jié)點(diǎn)，現(xiàn)要求插入一個(gè)新結(jié)點(diǎn)后使得單鏈表仍然保持有序，那么該操作的時(shí)間復(fù)雜度為[D]A.O(log2n)B.O(1)C.O(n2)D.O(n)55.設(shè)一棵m叉樹(shù)中度數(shù)為0的結(jié)點(diǎn)數(shù)為N0，度數(shù)為1的結(jié)點(diǎn)數(shù)為Nl，……，度數(shù)為m的結(jié)點(diǎn)數(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中，每個(gè)元素A的長(zhǎng)度為3個(gè)字節(jié)，行下標(biāo)i從0到7，列下標(biāo)j從0到9，從首地址SA開(kāi)場(chǎng)連續(xù)存放在存儲(chǔ)器內(nèi)，該數(shù)組按行存放時(shí)，數(shù)組元素A[7][4]的起始地址為[C]A.SA+141B.SA+144C.SA+222D.SA+22557.如果某二叉樹(shù)的前根次序遍歷結(jié)果為stuwv，中序遍歷為uwtvs，那么該二叉樹(shù)的后序?yàn)閇B]A.uwvtsB.vwutsC.wuvtsD.wutsv58.深度為5的二叉樹(shù)至多有〔〕個(gè)結(jié)點(diǎn)。[C]A.16B.32C.31D.1059.在一個(gè)無(wú)向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的〔〕倍。[C]A.1/2B.1C.2D.460.采用順序查找方法查找長(zhǎng)度為n的線性表時(shí)，每個(gè)元素的平均查找長(zhǎng)度為[C]A.nB.n/2C.(n+1)/2D.(n-1)/261.采用二分查找方法查找長(zhǎng)度為n的線性表時(shí)，每個(gè)元素的平均查找長(zhǎng)度為[C]A.O〔n2〕B.O(nlog2n)C.O(n)D.O(log2n)62.下述幾種排序方法中，要求內(nèi)存量最大的是[D]A.插入排序B.選擇排序C.快速排序D.歸并排序63.排序方法中，從未排序序列中依次取出元素與已排序序列〔初始時(shí)為空〕中的元素進(jìn)展比較，將其放入已排序序列的正確位置上的方法，稱(chēng)為[C]A.希爾排序B.起泡排序C.插入排序D.選擇排序64.對(duì)于長(zhǎng)度為9的有序順序表，假設(shè)采用折半搜索，在等概率情況下搜索成功的平均搜索長(zhǎng)度為〔〕的值除以9。[C]A.20B.18C.25D.2265.在有向圖中每個(gè)頂點(diǎn)的度等于該頂點(diǎn)的[C]A.入度B.出度C.入度與出度之和D.入度與出度之差66.在基于排序碼比較的排序算法中，〔〕算法的最壞情況下的時(shí)間復(fù)雜度不高于O(n10g2n)。[C]A.起泡排序B.希爾排序C.歸并排序D.快速排序67.當(dāng)α的值較小時(shí)，散列存儲(chǔ)通常比其他存儲(chǔ)方式具有〔〕的查找速度。[B]A.較慢B.較快C.一樣D.不清楚68.設(shè)有一個(gè)含200個(gè)表項(xiàng)的散列表，用線性探查法解決沖突，按關(guān)鍵碼查詢(xún)時(shí)找到一個(gè)表項(xiàng)的平均探查次數(shù)不超過(guò)1.5，那么散列表項(xiàng)應(yīng)能夠至少容納〔〕個(gè)表項(xiàng)。[A](設(shè)搜索成功的平均搜索長(zhǎng)度為Snl＝{1+l／(1一α)}／2，其中α為裝填因子)A.400B.526C.624D.67669.堆是一個(gè)鍵值序列{k1,k2,…..kn},對(duì)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è)將數(shù)據(jù)構(gòu)造形式定義為二元組(K，R)，其中K是數(shù)據(jù)元素的有限集合，那么R是K上[B]A.操作的有限集合B.映象的有限集合C.類(lèi)型的有限集合D.關(guān)系的有限集合71.以以下列圖示的順序存儲(chǔ)構(gòu)造表示的二叉樹(shù)是[A]72.由同一關(guān)鍵字集合構(gòu)造的各棵二叉排序樹(shù)[B]A.其形態(tài)不一定一樣，但平均查找長(zhǎng)度一樣B.其形態(tài)不一定一樣，平均查找長(zhǎng)度也不一定一樣C.其形態(tài)均一樣，但平均查找長(zhǎng)度不一定一樣D.其形態(tài)均一樣，平均查找長(zhǎng)度也都一樣73.ISAM文件和VSAM文件的區(qū)別之一是[C]A.前者是索引順序文件，后者是索引非順序文件B.前者只能進(jìn)展順序存取，后者只能進(jìn)展隨機(jī)存取C.前者建設(shè)靜態(tài)索引構(gòu)造，后者建設(shè)動(dòng)態(tài)索引構(gòu)造D.前者的存儲(chǔ)介質(zhì)是磁盤(pán)，后者的存儲(chǔ)介質(zhì)不是磁盤(pán)74.以下描述中正確的選項(xiàng)是[D]A.線性表的邏輯順序與存儲(chǔ)順序總是一致的B.每種數(shù)據(jù)構(gòu)造都具備三個(gè)基本運(yùn)算：插入、刪除和查找C.數(shù)據(jù)構(gòu)造實(shí)質(zhì)上包括邏輯構(gòu)造和存儲(chǔ)構(gòu)造兩方面的內(nèi)容D.選擇適宜的數(shù)據(jù)構(gòu)造是解決應(yīng)用問(wèn)題的關(guān)鍵步驟75.下面程序段的時(shí)間復(fù)雜度是[B]I=s=0While(s<n){I++;s+=I;}A.O(1)B.O(n)C.O(log2n)D.O(n^2)76.如果只想得到1024個(gè)元素組成的序列中的前5個(gè)最小元素，那么用〔〕方法最快。[A]A.起泡排序B.快速排序C.堆排序D.直接選擇排序77.算法分析的目的是[B]A.區(qū)分?jǐn)?shù)據(jù)構(gòu)造的合理性B.評(píng)價(jià)算法的效率C.研究算法中輸入與輸出的關(guān)系D.鑒別算法的可讀性78.在線性表的以下運(yùn)算中，不改變數(shù)據(jù)元素之間構(gòu)造關(guān)系的運(yùn)算是[C]A.插入B.刪除C.定位D.排序79.假設(shè)進(jìn)棧序列為1，2，3，4，5，6，且進(jìn)棧和出?？梢源┎暹M(jìn)展，那么可能出現(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.設(shè)串sl=″DataStructureswithJava″,s2=″it″，那么子串定位函數(shù)index(s1,s2)的值為[A]A.15B.16C.17D.1881.一個(gè)順序存儲(chǔ)的線性表的第一個(gè)元素的存儲(chǔ)地址是100，每個(gè)元素的長(zhǎng)度為4，那么第4個(gè)元素的存儲(chǔ)地址是[B]A.108B.112C.116D.12082.從一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表中查找其值等于x的結(jié)點(diǎn)，在查找成功的情況下，平均需要比較〔〕個(gè)結(jié)點(diǎn)。[C]A.nB.n/2C.(n+1)/2D.(n-1)/283.在任意一棵二叉樹(shù)的前序序列和后序序列中，各葉子之間的相對(duì)次序關(guān)系[D]A.不一定一樣B.互為逆序C.都不一樣D.都一樣84.高度為5的二叉樹(shù)至多有結(jié)點(diǎn)數(shù)為[A]A.63B.32C.24D.6485.假設(shè)用鄰接矩陣表示一個(gè)有向圖，那么其中每一列包含的″1″的個(gè)數(shù)為[B]A.圖中每個(gè)頂點(diǎn)的出度B.圖中每個(gè)頂點(diǎn)的入度C.圖中弧的條數(shù)D.圖中連通分量的數(shù)目86.圖的鄰接矩陣表示法一般不太適用于表示[A]A.無(wú)向圖B.有向圖C.稠密圖D.稀疏圖87.循環(huán)隊(duì)列是空隊(duì)列的條件是[B]A.Q->rear==Q->frontB.(Q->rear+1)%maxsize==Q->frontC.Q->rear==0D.Q->front==088.設(shè)有一廣義表E=〔a,b,(c,d)〕，其長(zhǎng)度為[A]A.2B.3C.4D.589.某二叉樹(shù)的前序遍歷序列為ABDEFC，中序遍歷序列為DBEFAC，那么后序遍歷序列為[D]A.DFEBCAB.DBECFAC.BDAECFD.DBEFCA90.以下〔〕不是利用查找表中數(shù)據(jù)元素的關(guān)系進(jìn)展查找的方法。[C]A.有序表的查找B.二叉排序樹(shù)的查找C.平衡二叉樹(shù)D.散列查找91.下述幾種排序方法中，要求內(nèi)存量最大的是[B]A.插入排序B.快速排序C.歸并排序D.選擇排序92.在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的〔〕倍。[B]A.1/2B.1C.2D.493.在帶有頭結(jié)點(diǎn)的單鏈表HL中，要向表頭插入一個(gè)由指針p指向的結(jié)點(diǎn)，那么執(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.對(duì)線性表，在以下哪種情況下應(yīng)當(dāng)采用鏈表表示[B]A.經(jīng)常需要隨機(jī)地存取元素B.經(jīng)常需要進(jìn)展插入和刪除操作C.表中元素需要占據(jù)一片連續(xù)的存儲(chǔ)空間D.表中元素的個(gè)數(shù)不變95.一個(gè)棧的輸入序列為123，那么以下序列中不可能是棧的輸出序列的是[C]A.231B.321C.312D.12396.每一趟都能選出一個(gè)元素放在其最終位置上，并且不穩(wěn)定的排序算法是[B]A.冒泡排序B.簡(jiǎn)單項(xiàng)選擇擇排序C.希爾排序D.直接插入排序97.采用開(kāi)放定址法處理散列表的沖突時(shí)，其平均查找長(zhǎng)度[B]A.低于鏈接法處理沖突B.高于鏈接法處理沖突C.與鏈接法處理沖突一樣D.高于二分查找98.假設(shè)需要利用形參直接訪問(wèn)實(shí)參時(shí)，應(yīng)將形參變量說(shuō)明為〔〕參數(shù)。[D]A.值B.函數(shù)C.指針D.引用99.在稀疏矩陣的帶行指針向量的鏈接存儲(chǔ)中，每個(gè)單鏈表中的結(jié)點(diǎn)都具有一樣的[A]A.行號(hào)B.列號(hào)C.元素值D.非零元素個(gè)數(shù)100.快速排序在最壞情況下的時(shí)間復(fù)雜度為[D]A.O(log2n)B.O(nlog2n)C.O(n)D.O(n2)101.從二叉搜索樹(shù)中查找一個(gè)元素時(shí)，其時(shí)間復(fù)雜度大致為[C]A.O(n)B.O(1)C.O(log2n)D.O(n2)102.設(shè)一個(gè)有序的單鏈表中有n個(gè)結(jié)點(diǎn)，現(xiàn)要求插入一個(gè)新結(jié)點(diǎn)后使得單鏈表仍然保持有序，那么該操作的時(shí)間復(fù)雜度為[D]A.O(log2n)B.O(1)C.O(n2)D.O(n)103.設(shè)一棵m叉樹(shù)中度數(shù)為0的結(jié)點(diǎn)數(shù)為N0，度數(shù)為1的結(jié)點(diǎn)數(shù)為Nl，……，度數(shù)為m的結(jié)點(diǎn)數(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.設(shè)有序表中有1000個(gè)元素，那么用二分查找查找元素X最多需要比較〔〕次。[B]A.25B.10C.7D.1105.設(shè)連通圖G中的邊集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，那么從頂點(diǎn)a出發(fā)可以得到一種深度優(yōu)先遍歷的頂點(diǎn)序列為[B]A.abedfcB.acfebdC.aebdfcD.aedfcb106.拓?fù)渑判蜻\(yùn)算只能用于[C]A.帶權(quán)有向圖B.連通無(wú)向圖C.有向無(wú)環(huán)圖D.無(wú)向圖107.在一個(gè)具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并仍然保持有序的時(shí)間復(fù)雜度是[B]A.O(1)B.O(n)C.O(n2)D.O(nlogn)計(jì)算與算法應(yīng)用題：1.一個(gè)圖的頂點(diǎn)集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};按照普里姆算法從頂點(diǎn)1出發(fā)得到最小生成樹(shù)，試寫(xiě)出在最小生成樹(shù)中依次得到的各條邊。2.一棵二叉樹(shù)的先序、中序和后序序列分別如下，其中有一局部未顯示出來(lái)。試求出空格處的內(nèi)容，并畫(huà)出該二叉樹(shù)。先序序列：BFICEHG中序序列：DKFIAEJC后序序列：KFBHJGA3.畫(huà)出以下樹(shù)對(duì)應(yīng)的二叉樹(shù)，并寫(xiě)出其先根遍歷序列：BBDFCAEG4.將關(guān)鍵字序列為{54，29，37，86，71，91，8，31，44，26}進(jìn)展歸并排序，寫(xiě)出各趟詳細(xì)過(guò)程。5.試列出如以以下列圖中全部可能的拓?fù)渑判蛐蛄小?.設(shè)某通信系統(tǒng)使用A，B，C，D，E，F(xiàn)，G，H八個(gè)字符，他們出現(xiàn)的概率w={5，29，7，8，14，23，3，11}，試構(gòu)造對(duì)應(yīng)的哈夫曼樹(shù)〔請(qǐng)按左子樹(shù)根結(jié)點(diǎn)的權(quán)小于右子樹(shù)樹(shù)根結(jié)點(diǎn)的權(quán)的次序構(gòu)造〕。7.給定表〔119，14，22，1，66，21，83，27，56，13，10〕,請(qǐng)按表中元素的順序構(gòu)造一棵平衡二叉樹(shù)，并求其在等概率情況下查找成功的平均長(zhǎng)度。8.一個(gè)有向圖的頂點(diǎn)集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>};假定該圖采用鄰接矩陣表示，那么分別寫(xiě)出從頂點(diǎn)a出發(fā)進(jìn)展深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷得到的頂點(diǎn)序列。9.設(shè)散列表的長(zhǎng)度為13，散列函數(shù)為H〔h〕=k%13，給定的關(guān)鍵碼序列為19，14，23，01，68，20，84，27。試畫(huà)出用線性探查法解決沖突時(shí)所構(gòu)成的散列表。012345678910111210.對(duì)7個(gè)關(guān)鍵字進(jìn)展快速排序，在最好的情況下僅需進(jìn)展10次關(guān)鍵字的比較。(1)假設(shè)關(guān)鍵字集合為{1,2,3,4,5,6,7}，試舉出能到達(dá)上述結(jié)果的初始關(guān)鍵字序列；(2)對(duì)所舉序列進(jìn)展快速排序，寫(xiě)出排序過(guò)程。11.如以下列圖二叉樹(shù)，答復(fù)以下問(wèn)題。12.畫(huà)出在一個(gè)初始為空的AVL樹(shù)中依次插入3,1,4,6,9,8,5,7時(shí)每一插入后AVL樹(shù)的形態(tài)。假設(shè)做了某種旋轉(zhuǎn)，說(shuō)明旋轉(zhuǎn)的類(lèi)型。然后，給出在這棵插入后得到的AVL樹(shù)中刪去根結(jié)點(diǎn)后的結(jié)果。13.一組記錄的排序碼為〔46，79，56，38，40，80,95，24〕，寫(xiě)出對(duì)其進(jìn)展快速排序的每一次劃分結(jié)果。14.一個(gè)線性表為B=〔12，23，45，57，20，03，78，31，15，36〕，設(shè)散列表為HT[0..12]，散列函數(shù)為H〔key〕=key%13并用線性探查法解決沖突，請(qǐng)畫(huà)出散列表，并計(jì)算等概率情況下查找成功的平均查找長(zhǎng)度。15.一棵二叉樹(shù)的前序遍歷的結(jié)果序列是ABECDFGHIJ，中序遍歷的結(jié)果是EBCDAFHIGJ，試寫(xiě)出這棵二叉樹(shù)的后序遍歷結(jié)果。16.假定對(duì)線性表(38，25，74，52，48，65，36)進(jìn)展散列存儲(chǔ)，采用H(K)=K％9作為散列函數(shù)，假設(shè)分別采用線性探查法和鏈接法處理沖突，那么計(jì)算對(duì)應(yīng)的平均查找長(zhǎng)度。17.哈希表地址空間為0..8，哈希函數(shù)為H(key)=key%7，采用線性探測(cè)再散列處理沖突，將數(shù)據(jù)序列{100,20,21,35,3,78,99,45}依次存入此哈希表中，列出插入時(shí)的比較次數(shù)，并求出在等概率下的平均查找長(zhǎng)度。18.試畫(huà)出下面帶權(quán)無(wú)向圖的一棵最小生成樹(shù)。55768432997abdcef19.關(guān)鍵字序列為：{03,87,12,61,98,70,61*，97,27,53,42，56，77，}請(qǐng)采用希爾(Shell)排序法對(duì)該序列作非遞減排序.按5，3，1分組，寫(xiě)出以下標(biāo)明的趟的結(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;}對(duì)于結(jié)點(diǎn)類(lèi)型為L(zhǎng)Node的單鏈表，以上算法的功能為：2.intAA(LNode*HL,ElemTypex){intn=0;LNode*p=HL;while(p!=NULL){if(p->data==x)n++;p=p->next;}returnn;}對(duì)于結(jié)點(diǎn)類(lèi)型為L(zhǎng)Node的單鏈表，以上算法的功能為：3.假定從鍵盤(pán)上輸入一批整數(shù)，依次為：786345309134–1，請(qǐng)寫(xiě)出輸出結(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.讀下述算法，說(shuō)明本算法完成什么功能。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.閱讀以下算法，說(shuō)明該算法的作用。//類(lèi)定義//類(lèi)定義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é)點(diǎn)構(gòu)造structSnode//結(jié)點(diǎn)構(gòu)造{chardata;Snode*next;};classLink//鏈表類(lèi){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.讀下述算法，說(shuō)明本算法完成什么功能。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)用該算法時(shí)以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);}該算法的功能為：_______________。//類(lèi)定義//類(lèi)定義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é)點(diǎn)構(gòu)造structSnode//結(jié)點(diǎn)構(gòu)造{chardata;Snode*next;};classLink//鏈表類(lèi){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ù)是二叉排序樹(shù)的什么算法如果K值為5，針對(duì)以以下列圖所示二叉樹(shù)，運(yùn)行以下算法，輸出是什么比較幾次得到結(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查找失敗，無(wú)此結(jié)點(diǎ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;}對(duì)于結(jié)點(diǎn)類(lèi)型為L(zhǎng)Node的單鏈表，以上算法的功能為：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;}}對(duì)于結(jié)點(diǎn)類(lèi)型為SeqList的順序表，以上算法的功能為：算法設(shè)計(jì)題：1.編寫(xiě)復(fù)制一棵二叉樹(shù)的非遞歸算法。aaHeadbbc^ed77Head97b15^5026boolFind〔BtreeNode*BST，ElemType&item〕數(shù)據(jù)構(gòu)造課程復(fù)習(xí)參考答案一、填空題：1.4，102.n3.1，24.線性構(gòu)造樹(shù)型構(gòu)造圖型構(gòu)造5.n(n-1)/2n(n-1)6.增加17.O(log2n)O(nlog2n)8.歸并9.n-110.左右子樹(shù)空11.122512.n(n-1)/213.head(A)14.節(jié)省空間15.L->next=L->prior或L->next=L16.104417.入?！膊迦搿吵鰲！矂h除〕18.前驅(qū)結(jié)點(diǎn)后繼結(jié)點(diǎn)19.中序序列20.順序存儲(chǔ)構(gòu)造有序的21.O(n)O(1)22.行號(hào)列號(hào)23.3x2.45／6－*＋24.(3h-1)/225.n3O(n3)26.零個(gè)字符的串零27.鄰接矩陣鄰接表28.sp29.q->nextq30.兩個(gè)串的長(zhǎng)度相等且對(duì)應(yīng)位置的字符一樣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.邏輯構(gòu)造44.n/245.先進(jìn)先出46.7947.中序48.n-149.快速排序50.head->next==NULL51.10,13,27,76,65,97,3852.入度為零53.非線性構(gòu)造54.p->next=p->next->next55.(rear-front+n)%n56.〔n-m+1〕×m57.(((b),j,(((d)))))58.16659.隊(duì)列二、單項(xiàng)選擇題：1.B2.B3.B4.C5.B