數(shù)據(jù)結構題集答案65692-資料下載頁
2025-06-24 00:44本頁面
【正文】 。，則表示該無向圖的鄰接表中有 2m 結點。四、簡答題，對于稠密圖和稀疏圖，采用鄰接矩陣和鄰接表那個更好些？答：從占用存儲空間看，稠密圖采用鄰接矩陣更好，稀疏圖采用鄰接表更好。，矩陣元素的個數(shù)與頂點個數(shù)是否相關？與邊的條數(shù)是否相關？為什么？。答：用鄰接矩陣表示圖，矩陣元素的個數(shù)與圖的頂點個數(shù)直接相關，與邊的條數(shù)無關。因為假設定點個數(shù)為n，則鄰接矩陣的大小為n2。 第九章 查找一、單選題【 B 】的查找表。 ，要求查找表必須【 B 】。 ，且結點按關鍵字有序排列 ，且結點按關鍵字有序排列，每個元素查找的平均查找長度為【 C 】。 (n+1)/2 D.(n1)/2，每個元素查找的平均查找長度為【 D 】。 (n2) (nlog2n) (n) (log2n)，若查找表中有625個元素，查找每個元素的概率相同，假設對索引表和塊都采用順序查找，每塊應分【 B 】個結點最佳。 ，最有效的查找方法是【 C 】。 ，又能適應動態(tài)變化的要求，可以采用【 A 】查找方法。 ，用二叉排序樹的方法進行查找，其查找長度與【 B】量級相當。 【 C 】。 ，若用線性探測再散列法把這k個關鍵字的紀錄插入到散列表中，至少要進行【 D 】次探測。 +1 (k+1)/2【 B 】。 ，不包含任何指針 ，它反映了散列表的裝填程度 【 A 】。 二、判斷題【 √】。【 】?！?】?！?】，每個結點的關鍵字比左孩子的關鍵字大，比右孩子的關鍵字小?！?】，比右孩子的關鍵字小，這樣的二叉樹都是二叉排序樹?！?√】，不能存儲數(shù)據(jù)元素之間的關系。【 】。三、填空題，若查找成功，則比較關鍵字的次數(shù)最多為 n 次；若查找不成功，則比較關鍵字的次數(shù)為 n+1 次。 ，最大的比較次數(shù)是 .235。log2n+1 。 ，該查找表必須具有的特點是 順序存儲且關鍵字有序 。 ，但塊與塊之間 關鍵字有序 。 ，首先查找 關鍵字表 ，然后再查找相應的 對應的塊 。 ，最壞情況下查找時間復雜度為 O(n) ，最好情況的查找時間復雜度為 O(log2n) 。 順序存儲結構 ，且是 關鍵字有序排列 。 二叉排序 樹而變成有序序列，構造樹的過程即是對無序序列進行排序的過程。，在最壞的情況下，平均查找長度為 （n+1）/2 ，最好的情況下，平均查找長度為 .(log2n+1)1 。(key)=key/p中，p最好取 小于或等于m的最大質數(shù) 。 哈希函數(shù) 和 沖突處理方法 ，把記錄按關鍵字轉換為地址進行存儲的存儲表，哈希方法的關鍵是 選擇好的哈希函數(shù) 和 沖突處理的方法 。一個好的哈希函數(shù)其轉換地址應盡可能 均勻 ，而且函數(shù)運算應盡可能 簡單 。四、解答題 畫出對長度為10的右序表進行折半查找的一棵判定樹，并求其等概率時查找成功的平均查找長度。25813749610 平均查找長度=(1+2*2+4*3+3*4)/10= 設有數(shù)據(jù)集合d={1，12，5，8，3，10，7，13，9}，回答下列問題： ① 依次取d中各數(shù)據(jù)，構造一棵二叉排序樹bt；② 如何依據(jù)此二叉排序樹得到d的一個有序序列。 答：①構造的二叉排序樹如下圖所示。711298313510②對該二叉排序樹進行中序遍歷，就可以得到d的一個有序序列： {1，3，5，7，8，9，10，12，13}，試在下列兩種情況下分別討論兩者在等概率時的平均查找長度：①查找不成功，即表中無關鍵字等于給定值k的記錄。②查找成功，即表中有關鍵字等于給定值k的記錄。 答：①對無序表的順序查找，需要進行n+1次比較才能確定查找失敗。 對有序表的順序查找，只要確定某個記錄關鍵字不等于且大于給定k值，就能確定查找失敗，即最少1次，最多n+1次，平均查找長度為（n+2）/2。 ②查找成功，其平均查找長度均為（n+1）/2，有序表和無序表是一樣的。 第十章 排序一、單選題【 A 】。 (n) (nlog2n) (n2) (log2n) ，從未排序序列中依次取出元素與已排序序列（初始時為1）中的元素進行比較，將其放入已排序序列的正確位置的方法，稱為【 B 】。 ，效率最高的排序方法是【 A 】。 ，【 C 】排序方法可能出現(xiàn)：在最后一趟開始前，所有元素都不在最終的位置上。 ，從未排序序列中挑選元素，并將其依次放入已排序序列（初始為空）的后面的方法，稱為【 D 】。 ，堆排序所需要的附加空間是【 A 】。 (1) (nlog2n) (n) (log2n)，效率最差的排序方法是【 C 】。 ，其最小的比較次數(shù)為【 A 】。 ，要求內(nèi)存量最大的方法【 D 】。 ，則進行一趟排序過程中，為尋找最小值元素所需要的時間復雜度為【 D 】。 (1) (log2n) (n2) (n)，堆排序、快速排序和歸并排序的關系是【 A 】。 快速排序歸并排序 歸并排序快速排序 歸并排序快速排序 快速排序歸并排序二、填空題，把它插入到有序子表中恰當位置，此種排序方法叫做 插入 排序；若每次從無序子表中挑選出最小或最大元素，把它交換到有序表的一端，此種排序方法叫做 直接選擇 排序。 ，不滿足約定要求時就交換位置，該排序方法叫做 快速 排序；每次使兩個相鄰有序表合并成一個有序表的排序方法叫做 歸并 排序。 3. 快速 排序方法采用二分法的思想， 堆 排序方法將數(shù)據(jù)的組織采用完全二叉樹的結構。 ，所需要的關鍵字的比較次數(shù)為 n(n1)/2 。 ，若原始記錄接近正序或反序，則選用 堆 ，若原始記錄無序，則選用 快速 。，若初始數(shù)據(jù)基本正序，則選用 插入 ，若初始數(shù)據(jù)基本反序，則選用 選擇 。 、快速排序和歸并排序中，若只從存儲空間考慮，則應首先選取 堆排序 方法，其次選擇 快速排序 方法，最后選擇 歸并排序 方法；若只從平均情況下排序最快考慮，則應選取 快速排序 方法；若只從最壞情況下排序最快并且要節(jié)省內(nèi)存考慮，則應選取 堆排序 方法。
研究報告相關推薦
鄂ICP備17016276號-1