復(fù)習(xí)題1[共12頁]

《復(fù)習(xí)題1[共12頁]》由會員分享，可在線閱讀，更多相關(guān)《復(fù)習(xí)題1[共12頁]（12頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、一、選擇題 1-1 下列關(guān)于數(shù)據(jù)和邏輯結(jié)構(gòu)的敘述中，哪一個是不正確的（ ）。 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) C 1-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)沒有影響 B 二、簡答題

2、1-1 數(shù)據(jù)結(jié)構(gòu)的存儲方式有哪幾種？ 1-2 算法的時間復(fù)雜度僅與問題的規(guī)模相關(guān)嗎 ? 1-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)信息外，

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

4、下程序段的時間復(fù)雜度。 int i ， j ， k ； for （ i=0 ； i 〈 n ； i++ 〉 // ① for （ j=0 ； j 〈 n ； j++ 〉 // ② { c[i][j]=0 ； // ③ for （ k=0 ； k 〈 n ； k++ 〉 // ④ c[i][j]=c[i][j]+a[i][k]+b[k][j] ； // ⑤ } 【解析】 語句①的循環(huán)控制變量 i 要增加到 n ，測試到 i=n 成立才會終止，故它的頻度為 n+1 ； 語句②作為語句①循環(huán)體內(nèi)的語句應(yīng)該執(zhí)行 n 次，但語句②本身要執(zhí)行 n+1 次，故語句

5、②的頻度是 n （ n+1 ）； 同理可得語句③、④和⑤的頻度分別是 n 2 ， n 2 （ n+1 ）和 n 3 。該程序段所有語句的頻度之和為： T （ n ） =2n3 +3n 2 +2n+1 其復(fù)雜度為 O （ n 3 ）。 一、簡答 1 何時選用順序表、何時選用鏈表作為線性表的存儲結(jié)構(gòu)為宜? 2 在順序表中插入和刪除一個結(jié)點(diǎn)需平均移動多少個結(jié)點(diǎn)?具體的移動次數(shù)取決于哪兩個因素? 3 為什么在單循環(huán)鏈表中設(shè)置尾指針比設(shè)置頭指針更好? 4 在單鏈表、雙鏈表和單循環(huán)鏈表中，若僅知道指針p指向某結(jié)點(diǎn)，不知道頭指針，能否將結(jié)點(diǎn)*p從相應(yīng)的鏈表中刪去?若可以，其

6、時間復(fù)雜度各為多少? 5 下述算法的功能是什么? LinkList Demo(LinkList L){ // L 是無頭結(jié)點(diǎn)單鏈表 ListNode *Q,*P; if(L&&L->next){ Q=L;L=L->next;P=L; while (P->next) P=P->next; P->next=Q; Q->next=NULL; } return L; } // Demo 6、試描述頭指針、頭結(jié)點(diǎn)、開始結(jié)點(diǎn)的區(qū)別、并說明頭指針和頭結(jié)點(diǎn)的作用。 二、下列函數(shù)的功能是，對以帶頭結(jié)點(diǎn)的單鏈表作為存儲結(jié)構(gòu)的兩個遞增有

7、序表（表中不存在值相同的數(shù)據(jù)元素）進(jìn)行如下操作：將所有在Lb表中存在而La表中不存在的結(jié)點(diǎn)插入到La中，其中La和Lb分別為兩個鏈表的頭指針。請?jiān)诳杖碧幪钊牒线m內(nèi)容，使其成為一個完整的算法。 void union (LinkList La, LinkList Lb){ /*本算法的功能是將所有Lb表中存在而La表中不存在的結(jié)點(diǎn)插入到La表中*/ LinkList pre = La, q; LinkList pa = La -> next; LinkList pb = Lb -> next; free (Lb); while (pa && pb){ if (pa ->

8、data data) { pre = pa; pa = pa -> next;} else if (pa -> data > pb ->data) { (1) ; pre = pb; pb = pb -> next; (2) ; } else { q = pb; pb = pb -> next; free (q); } } if (pb) (3) ; } （1）pre->next=pb; （2）pre->next=pa; （3）pre->next=pb; 三、已知一個線性表有n（n≤30）個元素，其中每個元素的數(shù)據(jù)占8個字節(jié)。假設(shè)一個

9、指針的大小為4個字節(jié)。如果采用有30個元素的數(shù)組存儲，那么當(dāng)數(shù)組中有效元素個數(shù)n滿足什么條件時，數(shù)組的存儲效率比不帶頭結(jié)點(diǎn)的單鏈表更高。 數(shù)組總的空間240個字節(jié)，數(shù)組的效率為8n/240；鏈表的總空間為12n，效率為8n/12n。故可得：n〉20 四、畫出執(zhí)行下列各語句后各指針及鏈表的示意圖。 L=(LinkList)malloc(sizeof(Lnode)); P=L; for(i=1;i<=4;i++){ p->next=(LinkList) malloc(sizeof(Lnode)); p=p->next; P->data=i*2-1;} P

10、->next=NULL; for(i=4;i>=1;i--) InsertList (L,i+1,i*2); for(i=1;i<=3;i++) DeleteList (L,i); 2、順序隊(duì)列一般應(yīng)該組織成為循環(huán)隊(duì)列的形式，而且一般隊(duì)列頭或?yàn)殛?duì)列尾其中之一虛指一位，滿隊(duì)列時實(shí)際上數(shù)組中還有一個空閑位置。請分析這樣設(shè)置的理由。 有利于判斷隊(duì)列是空還是滿。因?yàn)殛?duì)列有n+2種狀態(tài)：空，1個元素， 2個元素，…, n個元素，滿。但實(shí)際上rear只有n種可能的取值，故必須尋求其他途徑解決隊(duì)空和隊(duì)滿。當(dāng)然也有其他方法。 3、隊(duì)列可以用循環(huán)單鏈表來實(shí)現(xiàn)，故可以只設(shè)置一

11、個頭指針或者只設(shè)置一個尾指針。請分析對于循環(huán)單鏈表實(shí)現(xiàn)的隊(duì)列，用那種方案更合適。 設(shè)置尾指針。因?yàn)槭茄h(huán)單鏈表，設(shè)置尾指針，可以在O(1)的時間內(nèi)找到頭；如果只設(shè)置頭指針，要在O(n)時間內(nèi)找到尾。設(shè)置尾指針，入隊(duì)和出隊(duì)的時間復(fù)雜度均為O(1)，設(shè)置頭指針，出隊(duì)O(1)，入隊(duì)O(n)。 一、單項(xiàng)選擇題 1、由于二叉樹中每個結(jié)點(diǎn)的度最大為2，所以二叉樹是一種特殊的樹，這種說法 （A）正確 （B）錯誤 2、某二叉樹的先序遍歷序列和后序遍歷序列正好相反，則該二叉樹一定是 (A)空或只有一個結(jié)點(diǎn) (B) 完全二叉樹 (C)二叉排序樹 (D) 高度等于其節(jié)點(diǎn)數(shù)

12、3、深度為5的二叉樹至多有 多少個結(jié)點(diǎn) (A)16 (B)32 (C)31 (D)10 4、根據(jù)使用頻率為5個字符設(shè)計(jì)的哈夫曼編碼不可能是 （A）111，110，10，01，00 （B）000，001，010，011，1 （C）100，11，10，1，0 （D）001，000，01，11，10 二、填空題 1、樹和二叉樹的主要差別是 ， 。 2、深度為k的完全二叉樹至少有 個結(jié)點(diǎn)，至多有 個結(jié)點(diǎn)。 3、一棵二叉樹的第i(i1)層最多有 個結(jié)點(diǎn)；一棵有n（n>0）個結(jié)點(diǎn)的滿二叉樹共有

13、 個葉子結(jié)點(diǎn)和 個非葉子結(jié)點(diǎn)。 1、 （1）每個結(jié)點(diǎn)最多有兩棵子樹； （2）子樹有左右之分 2、2k-1,2k-1, 3、2i-1, 2 log2n ， n- 2 log2n 1、一棵度為2的樹與一棵二叉樹有何區(qū)別？ 2、具有三個結(jié)點(diǎn)的樹和具有三個結(jié)點(diǎn)的二叉樹它們的所有不同形態(tài)有哪些？ 3、請說明一棵二叉樹進(jìn)行先序、中序和后序遍歷，其葉結(jié)點(diǎn)的次序是否會發(fā)生變化？為什么？ 1、解答：度為2的樹結(jié)點(diǎn)有兩個分支，沒有左右之分；一棵二叉樹的結(jié)點(diǎn)也可有兩個分支，但有左右之分，且左右不能交換。 3.解答：二叉樹中葉結(jié)點(diǎn)必在某結(jié)點(diǎn)的左或

14、右子樹中，三種遍歷方法對左右子樹的遍歷都是按先左后右的原則進(jìn)行。所以在三種遍歷序列中葉結(jié)點(diǎn)的相對次序是不會發(fā)生變化的。 4、假設(shè)一棵二叉樹的結(jié)點(diǎn)數(shù)為33個，則它的最小高度為（ ），最大高度為（ ）。 5、一個高度為h的滿m叉樹，第k層最多有（ ）個結(jié)點(diǎn)，整棵樹最多有（ ）個結(jié)點(diǎn)。 4、最小高度為：6，最大高度為：33 5、第k層最多有 mk-1,整棵樹最多有(mk-1)/(m- 1) 6、一個二叉樹的對稱序列和后序序列分別是DCBAEFG和DCBGFEA，請給出該二叉樹的前序序列。 6、ABCDEFG 7 有7個帶權(quán)結(jié)點(diǎn)，其權(quán)值分別為4，7，8，2，5，16，

15、30，以它們?yōu)槿~子結(jié)點(diǎn)構(gòu)造一顆哈夫曼樹（要求按每個結(jié)點(diǎn)的左子樹根結(jié)點(diǎn)的權(quán)值小于或等于右子樹根結(jié)點(diǎn)的權(quán)值的次序構(gòu)造），并計(jì)算出其帶權(quán)路徑長度WPL。 可得帶權(quán)路徑長度： WPL=(2+4)5+(5+7+8)4+162+301=172 1、一個n個頂點(diǎn)的無向圖最多有 條邊。 (A)n (B)n(n-1) (C)n(n-1)/2 (D)2n 2、 （A）1/2 （B）1 （C）2 （D）4 3.兩種遍歷算法。 1、設(shè)線性表（a1，a2，…，a500）元素的值由小到大排列，對一個給定的k值用折半法查找線性表，在查找不成功的情況下至多

16、需比較 次 1. log2n+1 2 試述順序查找法、折半查找法和分塊查找法對被查找的表中元素的要求。對長度為n的表來說，三種查找法在查找成功時的查找長度各是多少？ 查找要求:順序查找法：表中元素可以任意存放,(n+1)/2 折半查找法：有序存放 log2(n+1)-1 分塊查找法：分塊有序(n/s+s)/2+1,b為塊數(shù)，s為塊中記錄數(shù) 1.數(shù)據(jù)的基本單位是（　C?。? A.數(shù)據(jù)項(xiàng) B.數(shù)據(jù)類型 C.數(shù)據(jù)元素　 D.數(shù)據(jù)變量 2.下列程序的時間復(fù)雜度為（　C?。? 　　i=0；s=0； 　　while（s

17、

18、） A.s.elem［top］=e； B.s.elem［top+1］=e； s.top=s.top+1； s.top=s.top+1； C.s.top=s.top+1； D.s.top=s.top+1； s.elem［top+1］=e； s.elem［top］=e； 6.循環(huán)隊(duì)列sq中，用數(shù)組elem［0??25］存放數(shù)據(jù)元素，sq.front指示隊(duì)頭元素的前一個位置，sq.rear指示隊(duì)尾元素的當(dāng)前位置，設(shè)當(dāng)前sq.front為20，sq.rear為12，則當(dāng)前隊(duì)列中的元素個數(shù)為（　D?。? A.8 B.16 C.17 D.18 8.含有10個結(jié)點(diǎn)的二叉樹中，度為

19、0的結(jié)點(diǎn)數(shù)為4，則度為2的結(jié)點(diǎn)數(shù)為（A　） A.3 B.4 C.5 D.6 10.有n個結(jié)點(diǎn)的有向完全圖的弧數(shù)是（　C　?。? A.n2　　　　 B.2n C.n(n-1) D.2n(n+1) 11.設(shè)圖的鄰接鏈表如題12圖所示，則該圖的邊的數(shù)目是（B?。? A.4 B.5 C.10 D.20 12.已知一個有序表為（13，18，24，35，47，50，62，83，90，115，134），當(dāng)二分檢索值為90的元素時，檢索成功需比較的次數(shù)是（　B　） A.1 B.2 C.3 D.4 13.排序算法中，第一趟排序后，任一元素都不能確定其最終位置的算法是（　　　

20、） A.選擇排序 B.快速排序 C.冒泡排序 D.插入排序 14．?dāng)?shù)據(jù)結(jié)構(gòu)是（　D　） A．一種數(shù)據(jù)類型 B．?dāng)?shù)據(jù)的存儲結(jié)構(gòu) C．一組性質(zhì)相同的數(shù)據(jù)元素的集合 D．相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合 15．算法分析的目的是（　B?。? A．辨別數(shù)據(jù)結(jié)構(gòu)的合理性 B．評價算法的效率 C．研究算法中輸入與輸出的關(guān)系 D．鑒別算法的可讀性 16．在線性表的下列運(yùn)算中，不改變數(shù)據(jù)元素之間結(jié)構(gòu)關(guān)系的運(yùn)算是（　D?。? A．插入 B．刪除 C．排序 D．定位 17．若進(jìn)棧序列為1，2，3，4，5，6，且進(jìn)棧和出?？梢源┎暹M(jìn)行，則可能出現(xiàn)的出棧序列為（　B?。?

21、A．3，2，6，1，4，5 B．3，4，2，1，6，5 C．1，2，5，3，4，6 D．5，6，4，2，3，1 18．二維數(shù)組A[8][9]按行優(yōu)先順序存儲，若數(shù)組元素A[2][3]的存儲地址為1087，A[4][7]的存儲地址為1153，則數(shù)組元素A[6][7]的存儲地址為（　A?。? A．1207 B．1209 C．1211 D．1213 19．在按層次遍歷二叉樹的算法中，需要借助的輔助數(shù)據(jù)結(jié)構(gòu)是（　A?。? A．隊(duì)列 B．棧 C．線性表 D．有序表 20．在任意一棵二叉樹的前序序列和后序序列中，各葉子之間的相對次序關(guān)系（B?。? A．不一定相同 B．都相同 C．都不相同 D

22、．互為逆序 1．稱算法的時間復(fù)雜度為O(f(n))，其含義是指算法的執(zhí)行時間和___ f(n)____的數(shù)量級相同。 2．假設(shè)為循環(huán)隊(duì)列分配的向量空間為Q[20]，若隊(duì)列的長度和隊(duì)頭指針值分別為13和17，則當(dāng)前尾指針的值為_10___。 3．一棵含999個結(jié)點(diǎn)的完全二叉樹的深度為_______。 4．含n個頂點(diǎn)的無向連通圖中至少含有______條邊。 6．在數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)的邏輯結(jié)構(gòu)分為集合、________、樹形結(jié)構(gòu)和圖狀結(jié)構(gòu)等四類。 7. 順序表的存儲密度為________，而鏈表的存儲密度為________。 是指一個結(jié)點(diǎn)中數(shù)據(jù)域所占的存儲單元和整個結(jié)點(diǎn)所占的存儲

23、單元之比 8. 對于棧只能在________插入和刪除元素。 9. 在循環(huán)隊(duì)列中，存儲空間為0～n-1,設(shè)隊(duì)頭指針front指向隊(duì)頭元素前一個空閑元素，隊(duì)尾指針指向隊(duì)尾元素，那么隊(duì)滿標(biāo)志為front=(rear+1)%n，隊(duì)空標(biāo)志為________。 10. 三個結(jié)點(diǎn)可構(gòu)成________種不同形態(tài)的二叉樹。 1.若對具有n個元素的有序的順序表和無序的順序表分別進(jìn)行順序查找，試在下述兩種情況下分別討論兩者在等概率時的平均查找長度： 　(1)查找不成功，即表中無關(guān)鍵字等于給定值K的記錄； 　(2)查找成功，即表中有關(guān)鍵字等于給定值K的記錄。 答：查找不成功時，需進(jìn)行n+1次

24、比較才能確定查找失敗。因此平均查找長度為n+1，這時有序表和無序表是一樣的。 　　查找成功時，平均查找長度為(n+1)/2,有序表和無序表也是一樣的。因?yàn)轫樞虿檎遗c表的初始序列狀態(tài)無關(guān)。 2．給出樹如下圖所示，請寫出先序遍歷和中序遍歷的節(jié)點(diǎn)次序。 3．一棵度為2的有序樹與一棵二叉樹有何區(qū)別? 答： 　　一棵度為二的有序樹與一棵二叉樹的區(qū)別在于:有序樹的結(jié)點(diǎn)次序是相對于另一結(jié)點(diǎn)而言的，如果有序樹中的子樹只有一個孩子時，這個孩子結(jié)點(diǎn)就無須區(qū)分其左右次序，而二叉樹無論其孩子數(shù)是否為2，均需確定其左右次序，也就是說二叉樹的結(jié)點(diǎn)次序不是相對于另一結(jié)點(diǎn)而言而是確定的。 4．設(shè)將整數(shù)

25、1，2，3，4依次進(jìn)棧，但只要出棧時棧非空，則可將出棧操作按任何次序夾入其中，請回答下述問題： 　　(1)若入、出棧次序?yàn)镻ush(1), Pop(),Push(2),Push(3), Pop(), Pop( ),Push(4), Pop( ),則出棧的數(shù)字序列為何(這里Push(i)表示i進(jìn)棧，Pop( )表示出棧)? 　　(2)能否得到出棧序列1423和1432?并說明為什么不能得到或者如何得到。 答：　(1)出棧序列為：1324 (2)不能得到1423序列。因?yàn)橐玫?4的出棧序列，則應(yīng)做Push(1),Pop(),Push(2),Push (3),Push(4),Pop()。

26、這樣，3在棧頂，2在棧底，所以不能得到23的出棧序列。能得到1432的出棧序列。具體操作為：Push(1), Pop(),Push(2),Push(3),Push(4),Pop(),Pop(),Pop()。 1．指出下述程序段的功能是什么? void Demo1(SeqStack *S){ 　　　　int i; arr[64] ; n=0 ; 　　　　while ( StackEmpty(S)) arr[n++]=Pop(S); 　　　　for (i=0, i< n; i++) Push(S, arr[i]); 　　　} //Demo1 程序段的功能是將一棧中的元素按反序

27、重新排列，也就是原來在棧頂?shù)脑胤诺綏５祝瑮５椎脑胤诺綏ｍ?。此棧中元素個數(shù)限制在64個以內(nèi)。 2.已知二叉樹的先序序列和中序序列分別為HDACBGFE和ADCBHFEG,畫出該二叉樹. 3.以二叉鏈表為存儲結(jié)構(gòu)， 寫一算法交換各結(jié)點(diǎn)的左右子樹。 答： 　　要交換各結(jié)點(diǎn)的左右子樹，最方便的辦法是用后序遍歷算法，每訪問一個結(jié)點(diǎn)時把兩棵子樹的指針進(jìn)行交換，最后一次訪問是交換根結(jié)點(diǎn)的子樹。 　void ChangeBinTree(BinTree *T) 　　{ //交換子樹 　　　if(*T) 　　　　{ //這里以指針為參數(shù)使得交換在實(shí)參的結(jié)點(diǎn)上進(jìn)行后序遍歷 　　　

28、　　BinTree temp; 　　　　　ChangeBinTree(&(*T)->lchild); 　　　　　ChangeBinTree(&(*T)->rchild); 　　　　　temp=(*T)->lchild; 　　　　　(*T)->lchild=(*T)->rchild; 　　　　　(*T)->rchild=temp;信道容量 1. 假設(shè)用于通信的電文由字符集{a,b,c,d,e,f,g,h}中的字母構(gòu)成，這8個字母在電文中出現(xiàn)的概率分別為{0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10}.為這8個字母設(shè)計(jì)哈夫曼編碼。 (1)哈夫曼編碼 根據(jù)上圖可得編碼表： 　　　a:1001 　　　b:01 　　　c:10111 　　　d:1010 　　　e:11 　　　f:10110 　　　g:00 　　　h:1000 2.給出下圖的從結(jié)點(diǎn)a開始的遍歷次序，1）深度優(yōu)先；2）廣度優(yōu)先。