數(shù)據(jù)結(jié)構(gòu)綜合練習(xí)題-資料下載頁(yè)
2025-03-25 03:01本頁(yè)面
【正文】 點(diǎn)a出發(fā)可以得到一種深度優(yōu)先遍歷的頂點(diǎn)序列為（ ）。 (A) abedfc (B) acfebd (C) aebdfc (D) aedfcb22．下面關(guān)于線(xiàn)性表的敘述錯(cuò)誤的是（ ）。(A) 線(xiàn)性表采用順序存儲(chǔ)必須占用一片連續(xù)的存儲(chǔ)空間 (B) 線(xiàn)性表采用鏈?zhǔn)酱鎯?chǔ)不必占用一片連續(xù)的存儲(chǔ)空間(C) 線(xiàn)性表采用鏈?zhǔn)酱鎯?chǔ)便于插入和刪除操作的實(shí)現(xiàn)(D) 線(xiàn)性表采用順序存儲(chǔ)便于插入和刪除操作的實(shí)現(xiàn)23．設(shè)哈夫曼樹(shù)中的葉子結(jié)點(diǎn)總數(shù)為m，若用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，則該哈夫曼樹(shù)中總共有（ ）個(gè)空指針域。 (A) 2m1 (B) 2m (C) 2m+1 (D) 4m24．設(shè)順序循環(huán)隊(duì)列Q[0：M1]的頭指針和尾指針?lè)謩e為F和R，頭指針F總是指向隊(duì)頭元素的前一位置，尾指針R總是指向隊(duì)尾元素的當(dāng)前位置，則該循環(huán)隊(duì)列中的元素個(gè)數(shù)為（ ）。 (A) RF (B) FR (C) (RF+M)％M (D) (FR+M)％M25．設(shè)某棵二叉樹(shù)的中序遍歷序列為ABCD，前序遍歷序列為CABD，則后序遍歷該二叉樹(shù)得到序列為（ ）。 (A) BADC (B) BCDA (C) CDAB (D) CBDA二、填空題1．1．for(i=1，t=1，s=0；i=n；i++) {t=t*i；s=s+t；}的時(shí)間復(fù)雜度為 。2．下面程序段的功能是實(shí)現(xiàn)冒泡排序算法，請(qǐng)?jiān)谙聞澗€(xiàn)處填上正確的語(yǔ)句。void bubble(int r[n]){for(i=1。i=n1。 i++){for(exchange=0,j=0。 j 。j++) if (r[j]r[j+1]){temp=r[j+1]。 。r[j]=temp。exchange=1。}if (exchange==0) return；}}3．下面程序段的功能是實(shí)現(xiàn)二分查找算法，請(qǐng)?jiān)谙聞澗€(xiàn)處填上正確的語(yǔ)句。struct record{int key。 int others。}。int bisearch(struct record r[ ], int k){ int low=0,mid,high=n1。 while(low=high){ 。 if(r[mid].key==k) return(mid+1)。 else if( ) high=mid1。else low=mid+1。 } return(0)。}3．根據(jù)二叉樹(shù)的定義可知二叉樹(shù)共有 種不同的形態(tài)。 4．快速排序的最壞時(shí)間復(fù)雜度為 ，平均時(shí)間復(fù)雜度為 。5．設(shè)某棵二叉樹(shù)中度數(shù)為0的結(jié)點(diǎn)數(shù)為N0，度數(shù)為1的結(jié)點(diǎn)數(shù)為N1，則該二叉樹(shù)中度數(shù)為2的結(jié)點(diǎn)數(shù)為 ；若采用二叉鏈表作為該二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)，則該二叉樹(shù)中共有 個(gè)空指針域。6．設(shè)某無(wú)向圖中頂點(diǎn)數(shù)和邊數(shù)分別為n和e，所有頂點(diǎn)的度數(shù)之和為d，則e= 。，如果按照從上到下、從左到右的順序從1開(kāi)始順序編號(hào)，則編號(hào)為8的雙親結(jié)點(diǎn)的編號(hào)是___________，編號(hào)為8的左孩子結(jié)點(diǎn)的編號(hào)是_____________。，則其最小生成樹(shù)上有________條邊。9．設(shè)一組初始記錄關(guān)鍵字序列為(55，63，44，38，75，80，31，56)，則利用篩選法建立的初始堆為 。10．設(shè)F和R分別表示順序循環(huán)隊(duì)列的頭指針和尾指針，則判斷該循環(huán)隊(duì)列為空的條件為 。三、判斷題1．調(diào)用一次深度優(yōu)先遍歷可以訪(fǎng)問(wèn)到圖中的所有頂點(diǎn)。（ ）2．分塊查找的平均查找長(zhǎng)度不僅與索引表的長(zhǎng)度有關(guān)，而且與塊的長(zhǎng)度有關(guān)。（ √ ）3．冒泡排序在初始關(guān)鍵字序列為逆序的情況下執(zhí)行的交換次數(shù)最多。（ √ ）4．滿(mǎn)二叉樹(shù)一定是完全二叉樹(shù)，完全二叉樹(shù)不一定是滿(mǎn)二叉樹(shù)。（ √ ）5．設(shè)一棵二叉樹(shù)的先序序列和后序序列，則能夠唯一確定出該二叉樹(shù)的形狀。（ ）6．設(shè)某堆中有n個(gè)結(jié)點(diǎn)，則在該堆中插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為O(log2n)。（ √ ）7．完全二叉樹(shù)中的葉子結(jié)點(diǎn)只可能在最后兩層中出現(xiàn)。（√ ）8．哈夫曼樹(shù)中沒(méi)有度數(shù)為1的結(jié)點(diǎn)。（ √ ）9．對(duì)連通圖進(jìn)行深度優(yōu)先遍歷可以訪(fǎng)問(wèn)到該圖中的所有頂點(diǎn)。（ √ ）10．先序遍歷一棵二叉排序樹(shù)得到的結(jié)點(diǎn)序列不一定是有序的序列。（√ ）四、應(yīng)用題1．對(duì)如下所示的帶權(quán)圖： 7v2v6v5v3v7v8v121113212241312v422 (1) 1) 分別按照克魯斯卡爾算法和普里姆算法，從頂點(diǎn)v1出發(fā)，生成最小生成樹(shù)，按生成次序依次寫(xiě)出各條邊；(2)畫(huà)出該圖最小生成樹(shù)，并求出它的權(quán)值。2．設(shè)給定權(quán)集W={5,7,2,3,6,8,10},請(qǐng)構(gòu)造畫(huà)出關(guān)于W的一棵赫夫曼樹(shù)，并求出其加權(quán)路徑長(zhǎng)度WPL。3．已知一棵二叉樹(shù)的先序序列是ABCDEFGHIJK，中序序列是CDBGFEAHJIK，請(qǐng)構(gòu)造出該二叉樹(shù)。4．設(shè)有一組初始記錄關(guān)鍵字為(45，80，47，40，22，68)，要求構(gòu)造一棵二叉排序樹(shù)并給出構(gòu)造過(guò)程；畫(huà)出刪除45后的二叉排序樹(shù)。(key)=key mod 7，散列表長(zhǎng)度為7(散列地址空間為0.....6)，待散列序列關(guān)鍵字依次為：(25，50，32，55，68)。要求(1)根據(jù)以上條件構(gòu)造一散列表，并用“線(xiàn)性探測(cè)再散列法”解決有關(guān)地址沖突（要求寫(xiě)出構(gòu)造過(guò)程）；(2)若要用該散列表查找元素68，試給出所需的比較次數(shù)和依次被比較的關(guān)鍵字。 (1) 求樹(shù)三棵樹(shù)的先根序列和后根序列； (2) 求森林先序序列和中序序列；（3）把森林轉(zhuǎn)換為對(duì)應(yīng)的二叉樹(shù)。KHEADCBIGJ把下面的二叉樹(shù)轉(zhuǎn)換為相應(yīng)的森林。五、算法設(shè)計(jì)題1．假設(shè)正讀和反讀都相同的字符序列為“回文”，例如，‘a(chǎn)bba’和‘a(chǎn)bcba’是回文，‘a(chǎn)bcde’ 和‘a(chǎn)babab’則不是回文。試寫(xiě)一個(gè)算法判別讀入的一個(gè)以‘@’為結(jié)束符的字符序列是否是“回文”。，設(shè)此二叉樹(shù)以二叉鏈表作存儲(chǔ)結(jié)構(gòu)。且樹(shù)中結(jié)點(diǎn)的關(guān)鍵字均不同。3. 編寫(xiě)按層次順序（同一層自左至右）遍歷二叉樹(shù)的算法。（6分），計(jì)算二叉樹(shù)中葉子結(jié)點(diǎn)的數(shù)目。（K1，K2，…，Kn），要求設(shè)計(jì)一個(gè)算法能夠在O(n)的時(shí)間復(fù)雜度內(nèi)將線(xiàn)性表劃分成兩部分，其中左半部分的每個(gè)關(guān)鍵字均小于Ki，右半部分的每個(gè)關(guān)鍵字均大于等于Ki。
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1