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