算法與數(shù)據(jù)課后題答案

1、文檔供參考，可復(fù)制、編制，期待您的好評與關(guān)注！ 一、選擇題 1、 下列關(guān)于數(shù)據(jù)和邏輯結(jié)構(gòu)的敘述中，哪一個(gè)是不正確的（ ）。 A ) 數(shù)據(jù)的邏輯結(jié)構(gòu)是數(shù)據(jù)間關(guān)系的描述 B) 數(shù)據(jù)的邏輯結(jié)構(gòu)抽象反映數(shù)據(jù)元素間的邏輯關(guān)系 C) 數(shù)據(jù)的邏輯結(jié)構(gòu)具體反映數(shù)據(jù)在計(jì)算機(jī)中的存儲方式 D) 數(shù)據(jù)的邏輯結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)2、 以下關(guān)于數(shù)據(jù)的存儲結(jié)構(gòu)的敘述中哪一條是正確的（ ）。 A) 數(shù)據(jù)的存儲結(jié)構(gòu)是數(shù)據(jù)間關(guān)系的抽象描述 B) 數(shù)據(jù)的存儲結(jié)構(gòu)是邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲器中的實(shí)現(xiàn) C) 數(shù)據(jù)的存儲結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu) D) 數(shù)據(jù)的存儲結(jié)構(gòu)對數(shù)據(jù)運(yùn)算的具體實(shí)現(xiàn)沒有影響3、由于二叉樹中每個(gè)結(jié)點(diǎn)的度最大為

2、2，所以二叉樹是一種特殊的樹，這種說法 B . （A）正確 （B）錯(cuò)誤4、某二叉樹的先序遍歷序列和后序遍歷序列正好相反，則該二叉樹一定是 (A)空或只有一個(gè)結(jié)點(diǎn) (B) 完全二叉樹(C)二叉排序樹 (D) 高度等于其節(jié)點(diǎn)數(shù)5、深度為5的二叉樹至多有 C 多少個(gè)結(jié)點(diǎn).(A)16 (B)32 (C)31 (D)106、根據(jù)使用頻率為5個(gè)字符設(shè)計(jì)的哈夫曼編碼不可能是 C（A）111，110，10，01，00 （B）000，001，010，011，1（C）100，11，10，1，0 （D）001，000，01，11，107、一個(gè)n個(gè)頂點(diǎn)的無向圖最多有條邊。(A) n (B) n(n-1) (C) n(

3、n-1)/2 (D) 2n8、在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的倍。（A）1/2 （B）1 （C）2 （D）49、關(guān)鍵路徑是事件結(jié)點(diǎn)網(wǎng)絡(luò)中 。（A）從源點(diǎn)到匯點(diǎn)的最長路徑 （B）最長的回路（C）從源點(diǎn)到匯點(diǎn)的最短路徑 (D）最短的回路10、下面不正確的說法是 。A、關(guān)鍵活動(dòng)不按期完成就會(huì)影響整個(gè)工程的完成時(shí)間B、任何一個(gè)關(guān)鍵活動(dòng)提前完成，將使整個(gè)工程提前完成C、所有關(guān)鍵活動(dòng)都提前，則整個(gè)工程提前完成D、某些關(guān)鍵活動(dòng)若提前完成，將使整個(gè)工程提前完成。11、采用順序查找法查找長度為n的線性表時(shí)，則查找成功時(shí)的平均查找長度為 C 。 (A) n (B) n/2 (C) (n+

4、1)/2 (D) (n-1)/212、在一個(gè)長度為12的有序表，按折半查找法對該表進(jìn)行查找，在表內(nèi)各元素等概率情況下查找成功所需的平均比較次數(shù)為 B 。（A）35/12 （B）37/12 （C）39/12 （D）43/1213、查找效率最高的二叉排序樹是 C 。 （A）所有結(jié)點(diǎn)的左子樹都為空的二叉排序樹 （B）所有結(jié)點(diǎn)的右子樹都為空的二叉排序樹 （C）平衡二叉樹 （D）沒有左子樹的二叉排序樹14、以下說法錯(cuò)誤的是 B 。A、散列法存儲的基本思想是由關(guān)鍵碼值決定數(shù)據(jù)的存儲地址B、散列表的結(jié)點(diǎn)中只包含數(shù)據(jù)元素自身的信息，不包含任何指針C、裝填因子是散列法的一個(gè)重要參數(shù)，它反映了散列表的裝填程度D、

5、散列表的查找效率主要取決于散列表造表時(shí)選取的散列函數(shù)和處理沖突的方法15、散列表的平均查找長度 A 。A.與處理沖突方法有關(guān)與表長無關(guān) B.與處理沖突方法無關(guān)與表的長度有關(guān)C.與處理沖突方法有關(guān)且與表的長度有關(guān) D.與處理沖突方法無關(guān)且與表的長度無關(guān)二、填空題1、樹和二叉樹的主要差別是，。（1）每個(gè)結(jié)點(diǎn)最多有兩棵子樹； （2）子樹有左右之分2、深度為k的完全二叉樹至少有個(gè)結(jié)點(diǎn)，至多有個(gè)結(jié)點(diǎn)。2k-1, 2k-1,3、一棵二叉樹的第i(i³1)層最多有 個(gè)結(jié)點(diǎn)；一棵有n（n>0）個(gè)結(jié)點(diǎn)的滿二叉樹共有個(gè)葉子結(jié)點(diǎn)和個(gè)非葉子結(jié)點(diǎn)。 (n+1)/2,(n-1)/24、假設(shè)一棵二叉樹的結(jié)點(diǎn)

6、數(shù)為33個(gè)，則它的最小高度為（ ），最大高度為（ ）。 最小高度為：6，最大高度為：335、一個(gè)高度為h的滿m叉樹，第k層最多有（ ）個(gè)結(jié)點(diǎn)，整棵樹最多有（ ）個(gè)結(jié)點(diǎn)。第k層最多有 mk-1,整棵樹最多有(mk-1)/m-16、一個(gè)圖的表示法是唯一的，而表示法是不唯一的。7、在有n個(gè)頂點(diǎn)的有向圖中，每個(gè)頂點(diǎn)的度最大可達(dá)8、設(shè)線性表（a1，a2，a500）元素的值由小到大排列，對一個(gè)給定的k值用折半法查找線性表，在查找不成功的情況下至多需比較 （ ëlog2nû+1 ）次9、一個(gè)無序序列可以通過構(gòu)造一棵 二叉排序樹 樹而變成一個(gè)有序序列，構(gòu)造樹的過程即為對無序序列進(jìn)行排序的過

7、程。10、在散列存儲中，裝填因子的值越大，則；的值越小，則.。 發(fā)生沖突的可能性就越大；發(fā)生沖突的可能性就越??；二、簡答題 1 數(shù)據(jù)結(jié)構(gòu)的存儲方式有哪幾種？ 常用的存儲表示方法有四種 : 1 、順序存儲方法：它是把邏輯上相鄰的結(jié)點(diǎn)存儲在物理位置相鄰的存儲單元里，結(jié)點(diǎn)間的邏輯關(guān)系由存儲單元的鄰接關(guān)系來體現(xiàn)。由此得到的存儲表示稱為順序存儲結(jié)構(gòu)，通常借助程序語言的數(shù)組描述。 2 、鏈接存儲方法：它不要求邏輯上相鄰的結(jié)點(diǎn)在物理位置上亦相鄰，結(jié)點(diǎn)間的邏輯關(guān)系是由附加的指針字段表示。由此得到的存儲表示稱為鏈?zhǔn)酱鎯Y(jié)構(gòu) , 通常借助于程序語言的指針類型描述。 3 、索引存儲方法：除建立存儲結(jié)點(diǎn)信息外，還建立

8、附加的索引表來標(biāo)識結(jié)點(diǎn)的地址。組成索引表的索引項(xiàng)由結(jié)點(diǎn)的關(guān)鍵字和地址組成。若每個(gè)結(jié)點(diǎn)在索引表中都有一個(gè)索引項(xiàng)，則該索引表稱之為稠密索引（ Dense Index ）。若一組結(jié)點(diǎn)在索引表中只對應(yīng)一個(gè)索引項(xiàng)，則該索引表稱為稀疏索引。 4 、散列存儲方法：就是根據(jù)結(jié)點(diǎn)的關(guān)鍵字直接計(jì)算出該結(jié)點(diǎn)的存儲地址。2 算法的時(shí)間復(fù)雜度僅與問題的規(guī)模相關(guān)嗎 ? 【解析】 算法的時(shí)間復(fù)雜度不僅與問題的規(guī)模相關(guān)，還與輸入實(shí)例中的初始狀態(tài)有關(guān)。但在最壞的情況下，其時(shí)間復(fù)雜度就是只與求解問題的規(guī)模相關(guān)的。我們在討論時(shí)間復(fù)雜度時(shí)，一般就是以最壞情況下的時(shí)間復(fù)雜度為準(zhǔn)的。3、設(shè)n為正整數(shù)，利用大"O"記號

9、，將下列程序段的執(zhí)行時(shí)間表示為n的函數(shù)。(1) i=1; k=0; while(i<n) k=k+10*i;i+; （1）分析：i=1; /1k=0; /1  while(i<n) /n k=k+10*i; /n-1i+; /n-1 由以上列出的各語句的頻度，可得該程序段的時(shí)間消耗：T(n)=1+1+n+(n-1)+(n-1)=3n可表示為T(n)=O(n)(2) i=0; k=0;dok=k+10*i; i+; while(i<n); （2）分析：i=0; /1k=0; /1do /nk=k+10*i; /ni+;

10、 /nwhile(i<n);/n 由以上列出的各語句的頻度，可得該程序段的時(shí)間消耗：T(n)=1+1+n+n+n+n=4n+2可表示為T(n)=O(n)(3) i=1; j=0; while(i+j<=n) if (i>j) j+;else i+;分析：通過分析以上程序段，可將i+j看成一個(gè)控制循環(huán)次數(shù)的變量，且每執(zhí)行一次循環(huán)，i+j的值加1。該程序段的主要時(shí)間消耗是while循環(huán)，而while循環(huán)共做了n次，所以該程序段的執(zhí)行時(shí)間為：T(n)=O(n)(4)x=n; / n>1 while (x>=(y+1)*(y+1)y

11、+;分析：由x=n且x的值在程序中不變，又while的循環(huán)條件(x>=(y+1)*(y+1)可知：當(dāng)(y+1)*(y+1)剛超過n的值時(shí)退出循環(huán)。由(y+1)*(y+1)<n得：y<n0.5-1所以，該程序段的執(zhí)行時(shí)間為：向下取整(n0.5-1)4、設(shè)三個(gè)函數(shù)f,g,h分別為 f(n)=100n3+n2+1000 , g(n)=25n3+5000n2 , h(n)=n1.5+5000nlgn 請判斷下列關(guān)系是否成立：(1) f(n)=O(g(n)  (2) g(n)=O(f(n)  (3) h(n)=O(n1.5) (4) h(n)=O(nlgn) 通俗地

12、說，就是當(dāng)n時(shí)，f(n)的函數(shù)值增長速度與T（n)的增長速度同階。一般，一個(gè)函數(shù)的增長速度與該函數(shù)的最高次階同階。即：O(f(n)=n3 O(g(n)=n3 O(h(n)=n1.5答：（1）成立。 （2）成立。（3）成立。（4）不成立。5 何時(shí)選用順序表、何時(shí)選用鏈表作為線性表的存儲結(jié)構(gòu)為宜? 6在順序表中插入和刪除一個(gè)結(jié)點(diǎn)需平均移動(dòng)多少個(gè)結(jié)點(diǎn)?具體的移動(dòng)次數(shù)取決于哪兩個(gè)因素? 7為什么在單循環(huán)鏈表中設(shè)置尾指針比設(shè)置頭指針更好? 尾指針是指向終端結(jié)點(diǎn)的指針，用它來表示單循環(huán)鏈表可以使得查找鏈表的開始結(jié)點(diǎn)和終端結(jié)點(diǎn)都很方便，設(shè)一帶頭結(jié)點(diǎn)的單循環(huán)鏈表，其尾指針為rear，則開始結(jié)點(diǎn)和終端

13、結(jié)點(diǎn)的位置分別是rear->next->next 和 rear, 查找時(shí)間都是O(1)。 若用頭指針來表示該鏈表，則查找終端結(jié)點(diǎn)的時(shí)間為O(n)。8在單鏈表、雙鏈表和單循環(huán)鏈表中，若僅知道指針p指向某結(jié)點(diǎn)，不知道頭指針，能否將結(jié)點(diǎn)*p從相應(yīng)的鏈表中刪去?若可以，其時(shí)間復(fù)雜度各為多少?下面分別討論三種鏈表的情況。1. 單鏈表。若指針p指向某結(jié)點(diǎn)時(shí)，能夠根據(jù)該指針找到其直接后繼，能夠順后繼指針鏈找到*p結(jié)點(diǎn)后的結(jié)點(diǎn)。但是由于不知道其頭指針，所以無法訪問到p指針指向的結(jié)點(diǎn)的直接前趨。因此無法刪去該結(jié)點(diǎn)。2. 雙鏈表。由于這樣的鏈表提供雙向指針，根據(jù)*p結(jié)點(diǎn)的前趨指針和后繼指針可以查找到其

14、直接前趨和直接后繼，從而可以刪除該結(jié)點(diǎn)。其時(shí)間復(fù)雜度為O(1)。3. 單循環(huán)鏈表。根據(jù)已知結(jié)點(diǎn)位置，可以直接得到其后相鄰的結(jié)點(diǎn)位置(直接后繼)，又因?yàn)槭茄h(huán)鏈表，所以我們可以通過查找，得到p結(jié)點(diǎn)的直接前趨。因此可以刪去p所指結(jié)點(diǎn)。其時(shí)間復(fù)雜度應(yīng)為O(n)。9、試描述頭指針、頭結(jié)點(diǎn)、開始結(jié)點(diǎn)的區(qū)別、并說明頭指針和頭結(jié)點(diǎn)的作用。開始結(jié)點(diǎn)是指鏈表中的第一個(gè)結(jié)點(diǎn)，也就是沒有直接前趨的那個(gè)結(jié)點(diǎn)。 鏈表的頭指針是一指向鏈表開始結(jié)點(diǎn)的指針(沒有頭結(jié)點(diǎn)時(shí))，單鏈表由頭指針唯一確定，因此單鏈表可以用頭指針的名字來命名。 頭結(jié)點(diǎn)是在鏈表的開始結(jié)點(diǎn)之前附加的一個(gè)結(jié)點(diǎn)。有了頭結(jié)點(diǎn)之后，頭指針指向頭結(jié)點(diǎn)，不論鏈表否為空

15、，頭指針總是非空。而且頭指針的設(shè)置使得對鏈表的第一個(gè)位置上的操作與在表其他位置上的操作一致(都是在某一結(jié)點(diǎn)之后)。10、已知一個(gè)順序表L，其中的元素遞增有序，設(shè)計(jì)一個(gè)算法插入一個(gè)元素x之后保持該順序表仍然遞增有序排列算法如下： void InsertIncreaseList( Seqlist *L , Datatype x ) if ( L->length>=ListSize)Error(“overflow"); for ( i=L -> length ; i>0 && L->data i-1 > x ; i-)L->data

16、 i =L->data i-1 ; / 比較并移動(dòng)元素L->data i =x;L -> length+; 11、設(shè)計(jì)算法，從給定的順序表L中刪除元素值在min到max(min£max)之間的所有元素，要求以較高的效率實(shí)現(xiàn)。void DeleteList ( LinkList L, DataType min , DataType max )ListNode *p , *q , *s;p=L;while( p->next && p->next->data <=min ) /找比min大的前一個(gè)元素位置 p=p->next;

17、q=p->next;/p指向第一個(gè)不大于min結(jié)點(diǎn)的直接前趨，q指向第一個(gè)大于min的結(jié)while(q &&q->data<max) s=q;q=q->next; free(s);/刪除結(jié)點(diǎn)，釋放空間 p->next=q;/將*p結(jié)點(diǎn)的直接后繼指針指向*q結(jié)點(diǎn)12、下列函數(shù)的功能是，對以帶頭結(jié)點(diǎn)的單鏈表作為存儲結(jié)構(gòu)的兩個(gè)遞增有序表（表中不存在值相同的數(shù)據(jù)元素）進(jìn)行如下操作：將所有在Lb表中存在而La表中不存在的結(jié)點(diǎn)插入到La中，其中La和Lb分別為兩個(gè)鏈表的頭指針。請?jiān)诳杖碧幪钊牒线m內(nèi)容，使其成為一個(gè)完整的算法。13、已知一個(gè)線性表有n（n30）個(gè)

18、元素，其中每個(gè)元素的數(shù)據(jù)占8個(gè)字節(jié)。假設(shè)一個(gè)指針的大小為4個(gè)字節(jié)。如果采用有30個(gè)元素的數(shù)組存儲，那么當(dāng)數(shù)組中有效元素個(gè)數(shù)n滿足什么條件時(shí)，數(shù)組的存儲效率比不帶頭結(jié)點(diǎn)的單鏈表更高。數(shù)組總的空間240個(gè)字節(jié)，數(shù)組的效率為8n/240；鏈表的總空間為12n，效率為8n/12n。故可得：n2013順序隊(duì)列一般應(yīng)該組織成為循環(huán)隊(duì)列的形式，而且一般隊(duì)列頭或?yàn)殛?duì)列尾其中之一虛指一位，滿隊(duì)列時(shí)實(shí)際上數(shù)組中還有一個(gè)空閑位置。請分析這樣設(shè)置的理由。有利于判斷隊(duì)列是空還是滿。因?yàn)殛?duì)列有n+2種狀態(tài)：空，1個(gè)元素， 2個(gè)元素，, n個(gè)元素，滿。但實(shí)際上rear只有n種可能的取值，故必須尋求其他途徑解決隊(duì)空和隊(duì)滿。當(dāng)

19、然也有其他方法。14隊(duì)列可以用循環(huán)單鏈表來實(shí)現(xiàn)，故可以只設(shè)置一個(gè)頭指針或者只設(shè)置一個(gè)尾指針。請分析對于循環(huán)單鏈表實(shí)現(xiàn)的隊(duì)列，用那種方案更合適設(shè)置尾指針。因?yàn)槭茄h(huán)單鏈表，設(shè)置尾指針，可以在O(1)的時(shí)間內(nèi)找到頭；如果只設(shè)置頭指針，要在O(n)時(shí)間內(nèi)找到尾。設(shè)置尾指針，入隊(duì)和出隊(duì)的時(shí)間復(fù)雜度均為O(1)，設(shè)置頭指針，出隊(duì)O(1)，入隊(duì)O(n)。15、假設(shè)一個(gè)單循環(huán)鏈表，其結(jié)點(diǎn)含有三個(gè)域pre,data和link。其中data為數(shù)據(jù)域;pre為指針域，它的值為空指針(NULL)；link為指針域，指向后繼結(jié)點(diǎn)。設(shè)計(jì)算法，將此表改為雙向循環(huán)鏈表設(shè)s為指向循環(huán)鏈表某一結(jié)點(diǎn)的指針，p,q中間結(jié)點(diǎn)；指針s

20、在搜索過程中保持不變，作為結(jié)束條件，每執(zhí)行一次就將指針p賦給q所指節(jié)電的pre，并修改p,q，保持p在后，q在前。doulink(s:dLinkList) /非空表 p=s; do q=p->next; q->pre=p; p=q; while(p!=s); 16、假設(shè)循環(huán)隊(duì)列只設(shè)rear和quelen來分別指示隊(duì)尾元素的位置和隊(duì)中元素的個(gè)數(shù)，試給出判斷此循環(huán)隊(duì)列的隊(duì)滿條件，并寫出相應(yīng)的入隊(duì)和出隊(duì)算法，要求出隊(duì)時(shí)需返回隊(duì)頭指針。隊(duì)滿條件： Q.quelen= MAX_QUEUE;入隊(duì):設(shè)Q.rear指向隊(duì)尾元素if(Q.quelen!= MAX_QUEUE) Q.rear= (Q.

21、rear+1)% MAX_QUEUEQ.dataQ.rear=x;Q.quelen+;出隊(duì)：設(shè)Q.rear指向隊(duì)尾元素if(Q.quelen!=0) /隊(duì)列非空 front=(Q.rear+ MAX_QUEUE- Q.quelen)%MAX_MAXSIZE; Q.quelen-; return(front); 17、請說明一棵二叉樹進(jìn)行先序、中序和后序遍歷，其葉結(jié)點(diǎn)的次序是否會(huì)發(fā)生變化？為什么？解答：二叉樹中葉結(jié)點(diǎn)必在某結(jié)點(diǎn)的左或右子樹中，三種遍歷方法對左右子樹的遍歷都是按先左后右的原則進(jìn)行。所以在三種遍歷序列中葉結(jié)點(diǎn)的相對次序是不會(huì)發(fā)生變化的。18、給定14各字母，假設(shè)它們的權(quán)都相等。采用HUFFMAN編碼，則每個(gè)字母的平均代碼長度是多少？（12*4+2*3）/14=54/14=3.857 19、有7個(gè)帶權(quán)結(jié)點(diǎn)，其權(quán)值分別為4，7，8，2，5，16，30，以它們?yōu)槿~子結(jié)點(diǎn)構(gòu)造一顆哈夫曼樹（要求按每個(gè)結(jié)點(diǎn)的左子樹根結(jié)點(diǎn)的權(quán)值小于或等于右子樹根結(jié)點(diǎn)的權(quán)值的次序構(gòu)造），并計(jì)算出其帶權(quán)路徑長度WPL。