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

1、一、選擇題 1-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ī)中的存儲(chǔ)方式 D) 數(shù)據(jù)的邏輯結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu) C1-2 以下關(guān)于數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)的敘述中哪一條是正確的（ ）。 A) 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)間關(guān)系的抽象描述 B) 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器中的實(shí)現(xiàn) C) 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu) D) 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)對(duì)數(shù)據(jù)運(yùn)算的具體實(shí)現(xiàn)沒(méi)有影響 B 二、簡(jiǎn)答題 1-1 數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)方式有哪幾種？ 1-2 算法的時(shí)間

2、復(fù)雜度僅與問(wèn)題的規(guī)模相關(guān)嗎 ? 1-1 數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)方式有哪幾種？ 【解析】 常用的存儲(chǔ)表示方法有四種 : 1 、順序存儲(chǔ)方法：它是把邏輯上相鄰的結(jié)點(diǎn)存儲(chǔ)在物理位置相鄰的存儲(chǔ)單元里，結(jié)點(diǎn)間的邏輯關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來(lái)體現(xiàn)。由此得到的存儲(chǔ)表示稱為順序存儲(chǔ)結(jié)構(gòu)，通常借助程序語(yǔ)言的數(shù)組描述。 2 、鏈接存儲(chǔ)方法：它不要求邏輯上相鄰的結(jié)點(diǎn)在物理位置上亦相鄰，結(jié)點(diǎn)間的邏輯關(guān)系是由附加的指針字段表示。由此得到的存儲(chǔ)表示稱為鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) , 通常借助于程序語(yǔ)言的指針類型描述。 3 、索引存儲(chǔ)方法：除建立存儲(chǔ)結(jié)點(diǎn)信息外，還建立附加的索引表來(lái)標(biāo)識(shí)結(jié)點(diǎn)的地址。組成索引表的索引項(xiàng)由結(jié)點(diǎn)的關(guān)鍵字和地址組成。若每

3、個(gè)結(jié)點(diǎn)在索引表中都有一個(gè)索引項(xiàng)，則該索引表稱之為稠密索引（ Dense Index ）。若一組結(jié)點(diǎn)在索引表中只對(duì)應(yīng)一個(gè)索引項(xiàng)，則該索引表稱為稀疏索引。 4 、散列存儲(chǔ)方法：就是根據(jù)結(jié)點(diǎn)的關(guān)鍵字直接計(jì)算出該結(jié)點(diǎn)的存儲(chǔ)地址。 1-2 算法的時(shí)間復(fù)雜度僅與問(wèn)題的規(guī)模相關(guān)嗎 ? 【解析】 算法的時(shí)間復(fù)雜度不僅與問(wèn)題的規(guī)模相關(guān)，還與輸入實(shí)例中的初始狀態(tài)有關(guān)。但在最壞的情況下，其時(shí)間復(fù)雜度就是只與求解問(wèn)題的規(guī)模相關(guān)的。我們?cè)谟懻摃r(shí)間復(fù)雜度時(shí)，一般就是以最壞情況下的時(shí)間復(fù)雜度為準(zhǔn)的。 三、應(yīng)用題: 分析以下程序段的時(shí)間復(fù)雜度。 int i ， j ， k ； for （ i=0 ； i n ； i+ / f

4、or （ j=0 ； j n ； j+ / cij=0 ； / for （ k=0 ； k n ； k+ / cij=cij+aik+bkj ； / 【解析】 語(yǔ)句的循環(huán)控制變量 i 要增加到 n ，測(cè)試到 i=n 成立才會(huì)終止，故它的頻度為 n+1 ； 語(yǔ)句作為語(yǔ)句循環(huán)體內(nèi)的語(yǔ)句應(yīng)該執(zhí)行 n 次，但語(yǔ)句本身要執(zhí)行 n+1 次，故語(yǔ)句的頻度是 n （ n+1 ）； 同理可得語(yǔ)句、和的頻度分別是 n 2 ， n 2 （ n+1 ）和 n 3 。該程序段所有語(yǔ)句的頻度之和為： T （ n ） =2n3 +3n 2 +2n+1 其復(fù)雜度為 O （ n 3 ）。 一、簡(jiǎn)答1 何時(shí)選用順序表、何時(shí)選用鏈

5、表作為線性表的存儲(chǔ)結(jié)構(gòu)為宜? 2 在順序表中插入和刪除一個(gè)結(jié)點(diǎn)需平均移動(dòng)多少個(gè)結(jié)點(diǎn)?具體的移動(dòng)次數(shù)取決于哪兩個(gè)因素? 3 為什么在單循環(huán)鏈表中設(shè)置尾指針比設(shè)置頭指針更好? 4 在單鏈表、雙鏈表和單循環(huán)鏈表中，若僅知道指針p指向某結(jié)點(diǎn)，不知道頭指針，能否將結(jié)點(diǎn)*p從相應(yīng)的鏈表中刪去?若可以，其時(shí)間復(fù)雜度各為多少? 5 下述算法的功能是什么?LinkList Demo(LinkList L) / L 是無(wú)頭結(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=NU

6、LL; return L; / Demo 6、試描述頭指針、頭結(jié)點(diǎn)、開(kāi)始結(jié)點(diǎn)的區(qū)別、并說(shuō)明頭指針和頭結(jié)點(diǎn)的作用。二、下列函數(shù)的功能是，對(duì)以帶頭結(jié)點(diǎn)的單鏈表作為存儲(chǔ)結(jié)構(gòu)的兩個(gè)遞增有序表（表中不存在值相同的數(shù)據(jù)元素）進(jìn)行如下操作：將所有在Lb表中存在而La表中不存在的結(jié)點(diǎn)插入到La中，其中La和Lb分別為兩個(gè)鏈表的頭指針。請(qǐng)?jiān)诳杖碧幪钊牒线m內(nèi)容，使其成為一個(gè)完整的算法。void union (LinkList La, LinkList Lb)/*本算法的功能是將所有Lb表中存在而La表中不存在的結(jié)點(diǎn)插入到La表中*/ LinkList pre = La, q; LinkList pa = La -

7、 next; LinkList pb = Lb - next; free (Lb); while (pa & pb)if (pa - 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;三、已知一個(gè)線性表有n（n30）個(gè)元素，其中每個(gè)元素的數(shù)據(jù)占8個(gè)字節(jié)。假設(shè)

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

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

10、歷都是按先左后右的原則進(jìn)行。所以在三種遍歷序列中葉結(jié)點(diǎn)的相對(duì)次序是不會(huì)發(fā)生變化的。4、假設(shè)一棵二叉樹(shù)的結(jié)點(diǎn)數(shù)為33個(gè)，則它的最小高度為（ ），最大高度為（ ）。5、一個(gè)高度為h的滿m叉樹(shù)，第k層最多有（ ）個(gè)結(jié)點(diǎn)，整棵樹(shù)最多有（ ）個(gè)結(jié)點(diǎn)。4、最小高度為：6，最大高度為：335、第k層最多有 mk-1,整棵樹(shù)最多有(mk-1)/(m- 1)6、一個(gè)二叉樹(shù)的對(duì)稱序列和后序序列分別是DCBAEFG和DCBGFEA，請(qǐng)給出該二叉樹(shù)的前序序列。 6、ABCDEFG7 有7個(gè)帶權(quán)結(jié)點(diǎn)，其權(quán)值分別為4，7，8，2，5，16，30，以它們?yōu)槿~子結(jié)點(diǎn)構(gòu)造一顆哈夫曼樹(shù)（要求按每個(gè)結(jié)點(diǎn)的左子樹(shù)根結(jié)點(diǎn)的權(quán)值小于或等

11、于右子樹(shù)根結(jié)點(diǎn)的權(quán)值的次序構(gòu)造），并計(jì)算出其帶權(quán)路徑長(zhǎng)度WPL?？傻脦?quán)路徑長(zhǎng)度：WPL=(2+4)5+(5+7+8)4+162+301=1721、一個(gè)n個(gè)頂點(diǎn)的無(wú)向圖最多有 條邊。(A)n (B)n(n-1) (C)n(n-1)/2 (D)2n2、（A）1/2 （B）1 （C）2 （D）43.兩種遍歷算法。1、設(shè)線性表（a1，a2，a500）元素的值由小到大排列，對(duì)一個(gè)給定的k值用折半法查找線性表，在查找不成功的情況下至多需比較 次 1. log2n+12 試述順序查找法、折半查找法和分塊查找法對(duì)被查找的表中元素的要求。對(duì)長(zhǎng)度為n的表來(lái)說(shuō)，三種查找法在查找成功時(shí)的查找長(zhǎng)度各是多少？查找要求:

12、順序查找法：表中元素可以任意存放,(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.下列程序的時(shí)間復(fù)雜度為（C）i=0；s=0；while（sn） i+；s=s+i； A.O（ ） B.O（ ） C.O（n） D.O（n2）3.若某線性表中最常用的操作是在最后一個(gè)元素之后插入一個(gè)元素和刪除第一個(gè)元素，則最節(jié)省運(yùn)算時(shí)間的存儲(chǔ)方式是（D）A.單鏈表 B.僅有頭指針的單循環(huán)鏈表C.雙鏈表 D.僅有尾指針的單循環(huán)鏈表4.從一個(gè)長(zhǎng)度為n的順序表中

13、刪除第i個(gè)元素（1in）時(shí)，需向前移動(dòng)的元素的個(gè)數(shù)是（A）A.n-i B.n-i+1C.n-i-1 D.i5.順序棧S中top為棧頂指針，指向棧頂元素所在的位置，elem為存放棧的數(shù)組，則元素e進(jìn)棧操作的主要語(yǔ)句為（C）A.s.elemtop=e； B.s.elemtop+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.elemtop+1=e； s.elemtop=e；6.循環(huán)隊(duì)列sq中，用數(shù)組elem025存放數(shù)據(jù)元素，sq.front指示隊(duì)頭元素的前一個(gè)位置，sq.rear指示隊(duì)尾元素的當(dāng)前位置，設(shè)

14、當(dāng)前sq.front為20，sq.rear為12，則當(dāng)前隊(duì)列中的元素個(gè)數(shù)為（D）A.8 B.16 C.17 D.188.含有10個(gè)結(jié)點(diǎn)的二叉樹(shù)中，度為0的結(jié)點(diǎn)數(shù)為4，則度為2的結(jié)點(diǎn)數(shù)為（A） A.3 B.4C.5 D.610.有n個(gè)結(jié)點(diǎn)的有向完全圖的弧數(shù)是（C）A.n2 B.2nC.n(n-1) D.2n(n+1)11.設(shè)圖的鄰接鏈表如題12圖所示，則該圖的邊的數(shù)目是（B） A.4 B.5 C.10 D.2012.已知一個(gè)有序表為（13，18，24，35，47，50，62，83，90，115，134），當(dāng)二分檢索值為90的元素時(shí)，檢索成功需比較的次數(shù)是（B）A.1 B.2C.3 D.413.排

15、序算法中，第一趟排序后，任一元素都不能確定其最終位置的算法是（）A.選擇排序 B.快速排序C.冒泡排序 D.插入排序14數(shù)據(jù)結(jié)構(gòu)是（D）A一種數(shù)據(jù)類型B數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)C一組性質(zhì)相同的數(shù)據(jù)元素的集合D相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合15算法分析的目的是（B）A辨別數(shù)據(jù)結(jié)構(gòu)的合理性B評(píng)價(jià)算法的效率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)棧和出棧可以穿插進(jìn)行，則可能出現(xiàn)的出棧序列為（B）A3，2，6，1，4，5 B3，4，2，1，6，5C1，2

16、，5，3，4，6 D5，6，4，2，3，118二維數(shù)組A89按行優(yōu)先順序存儲(chǔ)，若數(shù)組元素A23的存儲(chǔ)地址為1087，A47的存儲(chǔ)地址為1153，則數(shù)組元素A67的存儲(chǔ)地址為（A）A1207 B1209C1211 D121319在按層次遍歷二叉樹(shù)的算法中，需要借助的輔助數(shù)據(jù)結(jié)構(gòu)是（A）A隊(duì)列 B棧C線性表 D有序表20在任意一棵二叉樹(shù)的前序序列和后序序列中，各葉子之間的相對(duì)次序關(guān)系（B）A不一定相同 B都相同C都不相同 D互為逆序1稱算法的時(shí)間復(fù)雜度為O(f(n)，其含義是指算法的執(zhí)行時(shí)間和_ f(n)_的數(shù)量級(jí)相同。2假設(shè)為循環(huán)隊(duì)列分配的向量空間為Q20，若隊(duì)列的長(zhǎng)度和隊(duì)頭指針值分別為13和1

17、7，則當(dāng)前尾指針的值為_(kāi)10_。3一棵含999個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為_(kāi)。4含n個(gè)頂點(diǎn)的無(wú)向連通圖中至少含有_條邊。6在數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)的邏輯結(jié)構(gòu)分為集合、_、樹(shù)形結(jié)構(gòu)和圖狀結(jié)構(gòu)等四類。7. 順序表的存儲(chǔ)密度為_(kāi)，而鏈表的存儲(chǔ)密度為_(kāi)。是指一個(gè)結(jié)點(diǎn)中數(shù)據(jù)域所占的存儲(chǔ)單元和整個(gè)結(jié)點(diǎn)所占的存儲(chǔ)單元之比8. 對(duì)于棧只能在_插入和刪除元素。9. 在循環(huán)隊(duì)列中，存儲(chǔ)空間為0n-1,設(shè)隊(duì)頭指針front指向隊(duì)頭元素前一個(gè)空閑元素，隊(duì)尾指針指向隊(duì)尾元素，那么隊(duì)滿標(biāo)志為front=(rear+1)%n，隊(duì)空標(biāo)志為_(kāi)。10. 三個(gè)結(jié)點(diǎn)可構(gòu)成_種不同形態(tài)的二叉樹(shù)。1.若對(duì)具有n個(gè)元素的有序的順序表和無(wú)序的順序表

18、分別進(jìn)行順序查找，試在下述兩種情況下分別討論兩者在等概率時(shí)的平均查找長(zhǎng)度：(1)查找不成功，即表中無(wú)關(guān)鍵字等于給定值K的記錄；(2)查找成功，即表中有關(guān)鍵字等于給定值K的記錄。答：查找不成功時(shí)，需進(jìn)行n+1次比較才能確定查找失敗。因此平均查找長(zhǎng)度為n+1，這時(shí)有序表和無(wú)序表是一樣的。查找成功時(shí)，平均查找長(zhǎng)度為(n+1)/2,有序表和無(wú)序表也是一樣的。因?yàn)轫樞虿檎遗c表的初始序列狀態(tài)無(wú)關(guān)。2給出樹(shù)如下圖所示，請(qǐng)寫(xiě)出先序遍歷和中序遍歷的節(jié)點(diǎn)次序。3一棵度為2的有序樹(shù)與一棵二叉樹(shù)有何區(qū)別?答：一棵度為二的有序樹(shù)與一棵二叉樹(shù)的區(qū)別在于:有序樹(shù)的結(jié)點(diǎn)次序是相對(duì)于另一結(jié)點(diǎn)而言的，如果有序樹(shù)中的子樹(shù)只有一個(gè)孩子時(shí)，這個(gè)孩子結(jié)點(diǎn)就無(wú)須區(qū)分其左右次序，而二叉樹(shù)無(wú)論其孩子數(shù)是否為2，均需確定其左右次序，也就是說(shuō)二叉樹(shù)的結(jié)點(diǎn)次序不是相對(duì)于另一結(jié)點(diǎn)而言而是確定的。4設(shè)將整數(shù)1，2，3，4依次進(jìn)棧，但只要出棧時(shí)棧非空，則可將出棧操作按任何次序夾入其中，請(qǐng)回答下述問(wèn)題：(1)若入、出棧次序?yàn)镻ush(1), Pop(),Push(2),Push(3), Pop(), Pop( ),Push(4), Pop( ),則出棧的數(shù)字序列為何(這里Push(i)表示i進(jìn)棧，Pop( )表示出棧)?(2)能否得到出棧序列14