數(shù)據(jù)結(jié)構(gòu)題集答案65692(文件)
【正文】 【 C 】。 【 AB】。 【 C 】。 、中序和后序遍歷序列中的相對(duì)次序【 A 】。 +1 +1二、判斷題【 】?！尽?】，從上到下、從左到右用自然數(shù)對(duì)結(jié)點(diǎn)進(jìn)行編號(hào)，結(jié)點(diǎn)為i的結(jié)點(diǎn)的左孩子的編號(hào)為2i(2in)。三、填空題 2K1 個(gè)結(jié)點(diǎn)，至多有 2K1 個(gè)結(jié)點(diǎn)。，結(jié)點(diǎn)個(gè)數(shù)為n，則編號(hào)最大的分支結(jié)點(diǎn)的編號(hào)為 .235。log2i，共有 n+1 個(gè)空指針域。prchild==NULL 。③結(jié)點(diǎn)c的度為 2 。⑦這棵樹的度是 3 。答： 前序序列：eadcbifghj 中序序列：abcdiefhgj 后序序列：bcidahjgfeeafdigcjbh。0 5 10 15 20eafdgcjhib回答些列問(wèn)題：①畫出二叉樹表示。 【 C 】條邊。 B. (n1)2 C. (n1) D. n2，【 A 】?！?√】，沒(méi)有存儲(chǔ)頂點(diǎn)的信息?！?√】，則該圖一定是有向圖。 臨接矩陣 表示法是唯一的，而 鄰接表 表示法是不唯一的。，刪除所有從第i個(gè)結(jié)點(diǎn)出發(fā)的弧的方法是 將第i行對(duì)應(yīng)的1置成0 。，則表示該無(wú)向圖的鄰接表中有 2m 結(jié)點(diǎn)。因?yàn)榧僭O(shè)定點(diǎn)個(gè)數(shù)為n，則鄰接矩陣的大小為n2。 (n+1)/2 D.(n1)/2，每個(gè)元素查找的平均查找長(zhǎng)度為【 D 】。 ，用二叉排序樹的方法進(jìn)行查找，其查找長(zhǎng)度與【 B】量級(jí)相當(dāng)。 ，不包含任何指針 ，它反映了散列表的裝填程度 【 A 】。【 】，每個(gè)結(jié)點(diǎn)的關(guān)鍵字比左孩子的關(guān)鍵字大，比右孩子的關(guān)鍵字小。三、填空題，若查找成功，則比較關(guān)鍵字的次數(shù)最多為 n 次；若查找不成功，則比較關(guān)鍵字的次數(shù)為 n+1 次。 ，該查找表必須具有的特點(diǎn)是 順序存儲(chǔ)且關(guān)鍵字有序 。 順序存儲(chǔ)結(jié)構(gòu) ，且是 關(guān)鍵字有序排列 。 哈希函數(shù) 和 沖突處理方法 ，把記錄按關(guān)鍵字轉(zhuǎn)換為地址進(jìn)行存儲(chǔ)的存儲(chǔ)表，哈希方法的關(guān)鍵是 選擇好的哈希函數(shù) 和 沖突處理的方法 。 答：①構(gòu)造的二叉排序樹如下圖所示。 對(duì)有序表的順序查找，只要確定某個(gè)記錄關(guān)鍵字不等于且大于給定k值，就能確定查找失敗，即最少1次，最多n+1次，平均查找長(zhǎng)度為（n+2）/2。 ，效率最高的排序方法是【 A 】。 (1) (nlog2n) (n) (log2n)，效率最差的排序方法是【 C 】。 (1) (log2n) (n2) (n)，堆排序、快速排序和歸并排序的關(guān)系是【 A 】。 ，所需要的關(guān)鍵字的比較次數(shù)為 n(n1)/2 。，若初始數(shù)據(jù)基本正序，則選用 插入 ，若初始數(shù)據(jù)基本反序，則選用 選擇 。 ，不滿足約定要求時(shí)就交換位置，該排序方法叫做 快速 排序；每次使兩個(gè)相鄰有序表合并成一個(gè)有序表的排序方法叫做 歸并 排序。 ，要求內(nèi)存量最大的方法【 D 】。 ，從未排序序列中挑選元素，并將其依次放入已排序序列（初始為空）的后面的方法，稱為【 D 】。 第十章 排序一、單選題【 A 】。②查找成功，即表中有關(guān)鍵字等于給定值k的記錄。四、解答題 畫出對(duì)長(zhǎng)度為10的右序表進(jìn)行折半查找的一棵判定樹，并求其等概率時(shí)查找成功的平均查找長(zhǎng)度。，在最壞的情況下，平均查找長(zhǎng)度為 （n+1）/2 ，最好的情況下，平均查找長(zhǎng)度為 .(log2n+1)1 。 ，首先查找 關(guān)鍵字表 ，然后再查找相應(yīng)的 對(duì)應(yīng)的塊 。log2n【 √】，不能存儲(chǔ)數(shù)據(jù)元素之間的關(guān)系。【 】。 ，若用線性探測(cè)再散列法把這k個(gè)關(guān)鍵字的紀(jì)錄插入到散列表中，至少要進(jìn)行【 D 】次探測(cè)。 ，最有效的查找方法是【 C 】。 ，要求查找表必須【 B 】。，矩陣元素的個(gè)數(shù)與頂點(diǎn)個(gè)數(shù)是否相關(guān)？與邊的條數(shù)是否相關(guān)？為什么？。，采用鄰接矩陣表示，求圖中邊的方法是 計(jì)算鄰接矩陣中元素值為1的個(gè)數(shù) ，判斷任意兩個(gè)頂點(diǎn)是否有邊相連的方法是 判斷對(duì)應(yīng)鄰接矩陣元素的值是否為1 ，求任意頂點(diǎn)的度的方法是 求鄰接矩陣中對(duì)應(yīng)頂點(diǎn)所在行和列的元素值為1的個(gè)數(shù) 。 ，每個(gè)頂點(diǎn)的度最大可達(dá) n1 。 n 條邊?！?】，則該有向圖一定是完全有向圖。 ① +1 ②+e二、判斷題【 】(n1)條邊。 【 A 】條邊才能確保是一個(gè)連通圖。②先序序列為：eadcbjfghi 中序序列為：acbdjefhgi 后序序列為：bcjdahigfe③結(jié)點(diǎn)c的雙親結(jié)點(diǎn)是d，左孩子為b，無(wú)右孩子④該二叉樹對(duì)應(yīng)的森林為aefdjhbgci 第七章 圖一、單選題，所有頂點(diǎn)的度數(shù)之和等于所有邊的【 C 】倍。eadfcbhgijk：a,b,c,d,e,它們出現(xiàn)的頻率依次為4，7，5，2，9，構(gòu)造對(duì)應(yīng)的哈夫曼樹，求哈夫曼樹的帶權(quán)路徑長(zhǎng)度和每個(gè)字符的哈夫曼編碼。 0個(gè)或多個(gè)孩子 個(gè)孩子結(jié)點(diǎn)，除根結(jié)點(diǎn)之外，其余結(jié)點(diǎn)有 1 個(gè)雙親結(jié)點(diǎn)。⑤結(jié)點(diǎn)c的孩子結(jié)點(diǎn)是 e,f 。，回答下列問(wèn)題：①這棵樹的根結(jié)點(diǎn)是 a 。，指針p所指結(jié)點(diǎn)為葉結(jié)點(diǎn)的條件是 plchild==NULLamp。log2j 。 2i1 個(gè)結(jié)點(diǎn)，一棵有n個(gè)結(jié)點(diǎn)的滿二叉樹共有 2K1 個(gè)結(jié)點(diǎn)，共有 2K1 個(gè)葉結(jié)點(diǎn)?！尽?】，路經(jīng)上權(quán)值較大的結(jié)點(diǎn)離根最近?！?】，其高度為log2n。 =h+m +m=2n =h1 =2 h1 ，m是二叉樹上的兩個(gè)結(jié)點(diǎn)，在中序遍歷時(shí)，n在m之前的條件是【 C 】。 A. B.
研究報(bào)告相關(guān)推薦
鄂ICP備17016276號(hào)-1