數(shù)據(jù)結(jié)構(gòu)題集答案65692-閱讀頁
2025-07-09 00:44本頁面
【正文】 n個結(jié)點，深度為h，則【 D 】。 ，則此類二叉樹中包含的結(jié)點數(shù)最少為【 B 】?！尽?】?！尽?】，若一個沒有左孩子，則它必定是葉結(jié)點。【 】。【√ 】。 ，度為0的結(jié)點個數(shù)為n0，度為2的結(jié)點個數(shù)為n2,則有n0= n2+1 。，具有3個結(jié)點的二叉樹共有 5 種不同形態(tài)，它們分別是 。n/2，編號i和j的兩個結(jié)點處于同一層的條件是 .235。==.235。 。，如果有m個葉結(jié)點，則一定有 m1 個度為2的結(jié)點，有 n2m+1 個度為1的結(jié)點。amp。 任何結(jié)點至多只有右子樹 。②這棵樹的葉子結(jié)點是 b,e,g,d 。④這棵樹的深度是 4 。⑥結(jié)點c的雙親結(jié)點是 a 。abcdefg 樹中結(jié)點的最大度沒有限制，二叉樹結(jié)點的最大度限定為2 、 樹的結(jié)點無左右之分，二叉樹的的結(jié)點有左右之分 。四、簡答題，給出其前序、中序和后序遍歷結(jié)果。eafdigcjbhk答：下圖為其樹的二叉樹表示。117956421627 字符編碼： a：011 b：10 c：00 d：010 e：11，如下圖所示。②寫出先序、中序和后序遍歷結(jié)果③寫出結(jié)點c的雙親結(jié)點和左、右孩子結(jié)點④畫出此二叉樹還原成森林的圖aefdjhbgci答：①二叉樹表示如下圖所示。 ，所有頂點的入度數(shù)之和等于所有頂點的出度之和的【 B 】倍。 (n1) (n1)/2 【 A 】條邊。 ，若采用鄰接矩陣表示，則該矩陣的大小是【 D 】。 、第i列上非0元素個數(shù)等于頂點vi的度數(shù) ，若采用鄰接表表示，則表頭向量的大小為【① A 】；所有鄰接表中結(jié)點總數(shù)為【② C 】 。【 √】，各頂點的入度之和等于各頂點的出度之和?！?】。【 】，則該圖一定是無向圖。三、填空題 n(n1)/2 條邊。 n(n1) 條邊。 ，邊的總數(shù)最多為 45 。，計算第i個頂點的入度的方法是 求第i列非0元素個數(shù) 。，采用鄰接矩陣表示，求圖中邊的方法是 計算鄰接矩陣中元素值為1的個數(shù) ，判斷任意兩個頂點是否有邊相連的方法是 判斷對應(yīng)鄰接矩陣元素的值是否為1，再除以2 ，求任意頂點的度的方法是 求鄰接矩陣中對應(yīng)頂點所在行值為1 的元素個數(shù) 。 無向圖中最大連通子圖 。四、簡答題，對于稠密圖和稀疏圖，采用鄰接矩陣和鄰接表那個更好些？答：從占用存儲空間看，稠密圖采用鄰接矩陣更好，稀疏圖采用鄰接表更好。答：用鄰接矩陣表示圖，矩陣元素的個數(shù)與圖的頂點個數(shù)直接相關(guān)，與邊的條數(shù)無關(guān)。 第九章 查找一、單選題【 B 】的查找表。 ，且結(jié)點按關(guān)鍵字有序排列 ，且結(jié)點按關(guān)鍵字有序排列，每個元素查找的平均查找長度為【 C 】。 (n2) (nlog2n) (n) (log2n)，若查找表中有625個元素，查找每個元素的概率相同，假設(shè)對索引表和塊都采用順序查找，每塊應(yīng)分【 B 】個結(jié)點最佳。 ，又能適應(yīng)動態(tài)變化的要求，可以采用【 A 】查找方法。 【 C 】。 +1 (k+1)/2【 B 】。 二、判斷題【 √】。【 】。【 】，比右孩子的關(guān)鍵字小，這樣的二叉樹都是二叉排序樹?！?】。 ，最大的比較次數(shù)是 .235。+1 。 ，但塊與塊之間 關(guān)鍵字有序 。 ，最壞情況下查找時間復(fù)雜度為 O(n) ，最好情況的查找時間復(fù)雜度為 O(log2n) 。 二叉排序 樹而變成有序序列，構(gòu)造樹的過程即是對無序序列進行排序的過程。(key)=key/p中，p最好取 小于或等于m的最大質(zhì)數(shù) 。一個好的哈希函數(shù)其轉(zhuǎn)換地址應(yīng)盡可能 均勻 ，而且函數(shù)運算應(yīng)盡可能 簡單 。25813749610 平均查找長度=(1+2*2+4*3+3*4)/10= 設(shè)有數(shù)據(jù)集合d={1，12，5，8，3，10，7，13，9}，回答下列問題： ① 依次取d中各數(shù)據(jù)，構(gòu)造一棵二叉排序樹bt；② 如何依據(jù)此二叉排序樹得到d的一個有序序列。711298313510②對該二叉排序樹進行中序遍歷，就可以得到d的一個有序序列： {1，3，5，7，8，9，10，12，13}，試在下列兩種情況下分別討論兩者在等概率時的平均查找長度：①查找不成功，即表中無關(guān)鍵字等于給定值k的記錄。 答：①對無序表的順序查找，需要進行n+1次比較才能確定查找失敗。 ②查找成功，其平均查找長度均為（n+1）/2，有序表和無序表是一樣的。 (n) (nlog2n) (n2) (log2n) ，從未排序序列中依次取出元素與已排序序列（初始時為1）中的元素進行比較，將其放入已排序序列的正確位置的方法，稱為【 B 】。 ，【 C 】排序方法可能出現(xiàn)：在最后一趟開始前，所有元素都不在最終的位置上。 ，堆排序所需要的附加空間是【 A 】。 ，其最小的比較次數(shù)為【 A 】。 ，則進行一趟排序過程中，為尋找最小值元素所需要的時間復(fù)雜度為【 D 】。 快速排序歸并排序 歸并排序快速排序 歸并排序快速排序 快速排序歸并排序二、填空題，把它插入到有序子表中恰當位置，此種排序方法叫做 插入 排序；若每次從無序子表中挑選出最小或最大元素，把它交換到有序表的一端，此種排序方法叫做 直接選擇 排序。 3. 快速 排序方法采用二分法的思想， 堆 排序方法將數(shù)據(jù)的組織采用完全二叉樹的結(jié)構(gòu)。 ，若原始記錄接近正序或反序，則選用 堆 ，若原始記錄無序，則選用 快速 。 、快速排序和歸并排序中，若只從存儲空間考慮，則應(yīng)首先選取 堆排序 方法，其次選擇 快速排序 方法，最后選擇 歸并排序 方法；若只從平均情況下排序最快考慮，則應(yīng)選取 快速排序 方法；若只從最壞情況下排序最快并且要節(jié)省內(nèi)存考慮，則應(yīng)選取 堆排序 方
研究報告相關(guān)推薦
鄂ICP備17016276號-1