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