數(shù)據(jù)結(jié)構(gòu)期末復(fù)習(xí)要點(diǎn)

1、若需要利用形參直接訪問(wèn)實(shí)參，則應(yīng)把形參變量說(shuō)明為A.指針B.引用C.傳值()參數(shù)。D.常值設(shè)有一個(gè)遞歸算法如下int fact(int n) /n 大于等于 0if(n<=0) retur n 1;else return n *fact( n-1);則計(jì)算fact(n)需要調(diào)用該函數(shù)的次數(shù)為(A. nB. n+1C. n+2)次。D. n-1向具有n個(gè)結(jié)點(diǎn)的、結(jié)構(gòu)均衡的二叉搜索樹(shù)中插入一個(gè)元素的時(shí)間復(fù)雜度大致為A. O(1) C. O(n)B. O(n Iog2 n).D. O(log2n )具有n個(gè)頂點(diǎn)的有向無(wú)環(huán)圖最多可包含()條有向邊。C . n(n-1)/2D . n(n-1)次序

2、遍歷。C.后根D.層次A . n-1B . n圖的廣度優(yōu)先搜索類(lèi)似于樹(shù)的(A.先根B.中根如果將所有中國(guó)人按照生日(不考慮年份，只考慮月、日)來(lái)排序，那么使用下列排序算法 中()算法最快。A.歸并排序B.希爾排序C.快速排序讓元素1若，2, 3依次進(jìn)棧，則出棧次序不可能出現(xiàn)(A. 3, 2, 1B. 2, 1 , 3C. 3, 1 , 2在一棵具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)中，所有結(jié)點(diǎn)的空子樹(shù)個(gè)數(shù)等于(A. n如果只想得到 A .起泡排序B. n-1C. n+11024個(gè)元素組成的序列中的前B .快速排序C .堆排序D.基數(shù)排序 )種情況。1, 3, 2)D.5個(gè)最小元素，那么用(D.直接選擇排序按關(guān)鍵

3、碼查詢(xún)時(shí)找到一個(gè)表項(xiàng)的)個(gè)表項(xiàng)。2*n)方法最快。設(shè)有一個(gè)含200個(gè)表項(xiàng)的散列表，用線(xiàn)性探查法解決沖突， 平均探查次數(shù)不超過(guò) 1.5,則散列表項(xiàng)應(yīng)能夠至少容納(設(shè)搜索成功的平均搜索長(zhǎng)度為SnI=1+1/(1- a )/2其中a為裝填因子)A . 400B . 526C . 624D . 676分配的數(shù)組。這種數(shù)組在聲明它時(shí)需要1、在程序運(yùn)行過(guò)程中可以擴(kuò)充的數(shù)組是使用數(shù)組指針。2、 棧是一種限定在表的一端進(jìn)行插入和刪除的線(xiàn)性表，又被稱(chēng)為表。3、 一棵樹(shù)按照左子女-右兄弟表示法轉(zhuǎn)換成對(duì)應(yīng)的二叉樹(shù)，則該二叉樹(shù)中樹(shù)根結(jié)點(diǎn)肯定沒(méi)有 子女。若元素的值小于根結(jié)點(diǎn)的值，則應(yīng)把它插入到根4、向一棵二叉搜索樹(shù)中插

4、入一個(gè)元素時(shí)，結(jié)點(diǎn)的上o5、每次直接或通過(guò)基準(zhǔn)元素間接比較兩個(gè)元素，若出現(xiàn)逆序排列就交換它們的位置，這種排序方法叫做排序。6、 快速排序在平均情況下的空間復(fù)雜度為 。20個(gè)7、若對(duì)長(zhǎng)度n=10000的線(xiàn)性表進(jìn)行二級(jí)索引存儲(chǔ)，每級(jí)索引表中的索引項(xiàng)是下一級(jí) 表項(xiàng)的索引，則一級(jí)索引表的長(zhǎng)度為1、 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)主要包括四種，順存存儲(chǔ)結(jié)構(gòu)、鏈接存儲(chǔ)結(jié)構(gòu)、。2、 設(shè)有一個(gè)順序棧 S,元素1, 2, 3, 4, 5, 6依次進(jìn)棧，如果 6個(gè)元素的出棧順序?yàn)?2,O來(lái)保存被調(diào)用程序內(nèi)分配3，4，6，5，1,則順序棧的容量至少應(yīng)為 3、 通常程序在調(diào)用另一個(gè)程序時(shí)，都需要使用一個(gè) 的局部變量、形式參數(shù)的存儲(chǔ)空

5、間以及返回地址。4、在對(duì)一組記錄22，56，44，13，25，62，50，34，42進(jìn)行堆排序時(shí)，根據(jù)初始記錄構(gòu)成初始堆（大根堆）后，最后四條記錄為 。5、 一棵樹(shù)的廣義表表示為 （a （ b（c，d（ e，f），g（ h），I（j，k（ x，y） ,u（v,w），結(jié)點(diǎn) k 的所有祖先的結(jié)點(diǎn)數(shù)為 個(gè)。6、 根據(jù)一組記錄（56, 42，50, 64, 48）依次插入結(jié)點(diǎn)生成一棵AVL樹(shù)（高度平衡的二叉搜索樹(shù)）時(shí)，當(dāng)插入到值為 的結(jié)點(diǎn)時(shí)需要進(jìn)行旋轉(zhuǎn)調(diào)整。已知一棵二叉樹(shù)的中序和后序序列，畫(huà)出二叉樹(shù).后序序列：A B C D E F G中序序列：A C B G E D F已知輸入結(jié)點(diǎn)的序列，構(gòu)造AVL

6、樹(shù).120,100,50,80,70,90,60指出每次旋轉(zhuǎn)操作已知一個(gè)帶權(quán)圖的頂點(diǎn)集V和邊集G分別為：V=0,1,2,3,4,5,6;E=（0,1）19,（0,2）10,（0,3）14,（1,2）6,（1,5）5,（2,3）26,（2,4）15,（3,4）18, （4,5）6,（4,6）6,（5,6）12;試根據(jù)迪克斯特拉（Dijkstra）算法求出從頂點(diǎn)0到其余各頂點(diǎn)的最短路徑，在下面填寫(xiě)對(duì)應(yīng)的路徑長(zhǎng)度。23456頂點(diǎn)：（用 C語(yǔ)言）給出順序存儲(chǔ)循環(huán)隊(duì)列給出初始化隊(duì)列InitSqQueue（）算法，設(shè)隊(duì)列初始化空間為大小為常數(shù)MaxSize （ 3分）給出入隊(duì)算法EnQueue（）。（ 3

7、分）對(duì)下述樹(shù)，請(qǐng)畫(huà)出其對(duì)應(yīng)的二叉樹(shù)及長(zhǎng)子兄弟存儲(chǔ)形式 給出長(zhǎng)子兄弟存儲(chǔ)節(jié)點(diǎn)類(lèi)型定義。（2分）編程只要編寫(xiě)算法，對(duì)二叉樹(shù)形式（即長(zhǎng)子兄弟存儲(chǔ)形式）存儲(chǔ)表示的樹(shù)，按層次周游， （提示，為了實(shí)現(xiàn)按層次周游樹(shù)，程序中可 a把根結(jié)點(diǎn)插入隊(duì)列；b:當(dāng)隊(duì)列不空時(shí)，取C：重復(fù)執(zhí)行第二步直至隊(duì)列空為止。）SqQueue的類(lèi)型定義。（2分）（2 分）。并打印樹(shù)的周游的序列，用算法實(shí)現(xiàn)上述過(guò)程。設(shè)立了一個(gè)隊(duì)列qu,周游的算法采用如下思想： 出隊(duì)列的頭，訪問(wèn)該結(jié)點(diǎn)，并把它的所有孩子插入隊(duì)列。（8分）(寫(xiě)出以下相應(yīng)類(lèi)型定義及算法，不要求寫(xiě)完整程序。(1)(2)(3)(4)(5)假定用二叉鏈表表示一棵二叉樹(shù);寫(xiě)出棧的存儲(chǔ)

8、類(lèi)型SqStack定義。寫(xiě)出在上述定義下的棧的初始化算法InitSqStackO。寫(xiě)出壓棧算法 P ush()。寫(xiě)出二叉鏈表的結(jié)點(diǎn)的類(lèi)型定義；設(shè)root為指向二叉樹(shù)的根結(jié)點(diǎn)的指針，試寫(xiě)一遞歸算法，求二叉樹(shù)中葉子結(jié)點(diǎn)的數(shù)目, 輸出結(jié)果。(用棧)。輸出所有的樹(shù)葉及樹(shù)(6) 試寫(xiě)出一個(gè)非遞歸算法，求二叉樹(shù)中的葉子結(jié)點(diǎn)的數(shù)目 葉總數(shù)?？紤]平衡題： 隊(duì)列在層次遍歷中的作用. 已知二叉樹(shù)中的結(jié)點(diǎn)類(lèi)型用BinTreeNode表示，被定義為：Typedef struct BinTreeNode ElemType data; struct BinTreeNode *leftChid, *rightChild;B

9、i nTreeNode;其中data為結(jié)點(diǎn)值域，leftChild和rightChild分別為指向左、右子女結(jié)點(diǎn)的指針域。下面函 數(shù)的功能是返回二叉樹(shù) BT中值為x的結(jié)點(diǎn)所在的層號(hào)，請(qǐng)?jiān)趧澯袡M線(xiàn)的地方填寫(xiě)合適的內(nèi) 容。Int NodeLevel(Bi nTreeNode *BT, ElemT ype x)Int c1,c2;lf(BT = =NULL)return -;Else if (BT ->data = =x)return 0Else cl=NodeLevel(BT ->leftChild,x);If (c1>=0)c2=If (c2>=0)Else return -1;II空樹(shù)的層號(hào)為-1II根結(jié)點(diǎn)的層號(hào)為0II向左子樹(shù)中查找結(jié)點(diǎn)在樹(shù)中不存在結(jié)點(diǎn)返回-1第一章: 數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、算法、時(shí)間復(fù)雜性計(jì)算 第二章：線(xiàn)性表 線(xiàn)性表定義，線(xiàn)性表順序存儲(chǔ)結(jié)構(gòu)、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 第三章：棧與隊(duì)列 棧的定義，后進(jìn)先出, 棧的基本操作 隊(duì)列的定義 隊(duì)列的基本操作第四章：串的定義，邏輯上的操作，模式匹配、樸素匹配與KMP匹配算法的時(shí)間復(fù)雜性 第五章：樹(shù)與二叉樹(shù) 樹(shù)的表示：樹(shù)的表示法（四種），樹(shù)的存儲(chǔ)法，雙親表