復(fù)習(xí)提綱：算法與數(shù)據(jù)結(jié)構(gòu)

1、1、算法的概念是為了解決某類問題而規(guī)定的一個有限長的操作序列。特性：有窮性確定性可行性輸入輸出評價標(biāo)準(zhǔn)：正確性可讀性健壯性高效性2、算法的復(fù)雜度：算法計算量所需資源的大小時間復(fù)雜度：T(n)=O(f(n),他表示隨問題規(guī)模n的增大，算法執(zhí)行時間的增長率和f(n)的增長率相同，稱作算法的時間復(fù)雜度空間復(fù)雜度：S(n)=O(f(n)，算法所需空間的度量。3、數(shù)據(jù)結(jié)構(gòu)中的邏輯結(jié)構(gòu)分為：線性和非線性結(jié)構(gòu)4、線性表的兩種存儲方式：順序存儲和鏈?zhǔn)酱鎯Φ奶攸c及比較。順序存儲：指用一組地址連續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)元素 鏈?zhǔn)酱鎯Γ河靡唤M任意的存儲單元存儲線性表的數(shù)據(jù)元素。5、線性表的特點存在唯一的一個

2、被稱作“第一個”的數(shù)據(jù)元素存在唯一的一個被稱作“最后一個”的數(shù)據(jù)元素除第一個之外，結(jié)構(gòu)中的每一個數(shù)據(jù)元素均只有一個前驅(qū)除最后一個之外，結(jié)構(gòu)中的每一個數(shù)據(jù)元素均只有一個后繼6、在長度為n的順序表中的第i個位置處插入一個元素，需要移動多少個元 素？n-i+17、理解算法：線性表La和Lb，將兩個表合并成一個新的線性表并存于La中。8、帶頭結(jié)點的單鏈表和不帶頭結(jié)點的單鏈表為空的條件分別是？帶頭結(jié)點的 循環(huán)單鏈表為空的條件是？帶頭結(jié)點的單鏈表為空的條件：沒有下一個節(jié)點L-next=NULL不帶頭結(jié)點的單鏈表為空的條件：L=NULL循環(huán)單鏈表為空的條件：head-next=head帶頭結(jié)點的循環(huán)單鏈表為

3、空的條件是9、在單鏈表中插入結(jié)點的算法中，指針如何修改。P3410、理解單鏈表中插入新結(jié)點的算法p3411、理解雙向鏈表中插入新結(jié)點的算法p4012、理解棧和隊列的操作特點：先進(jìn)后出，先進(jìn)先出。已知進(jìn)棧順序，求可 能的出棧順序。鏈棧相對于順序棧的優(yōu)點是什么？鏈棧在入棧前不需要判斷棧是否為滿，只需要為入棧元素動態(tài)分配一個節(jié)點 空間13、理解算法：執(zhí)行進(jìn)棧操作，則先要判斷棧S是否為滿，若不滿再將記錄 棧頂?shù)南聵?biāo)變量top加1，再將進(jìn)棧元素放進(jìn)棧頂位置上。P5914、循環(huán)單鏈表的特點：尾指針的next指向頭結(jié)點15、循環(huán)隊列中進(jìn)行插入和刪除操作后，其頭尾指針如何變化？根據(jù)循環(huán)隊 列的容量及頭尾指針，

4、求循環(huán)隊列中元素的個數(shù)。插入：Q.rear=(Q.rear+1)%MAXQSIZE /尾指針加 1刪除：Q.front=(Q.front+1)%MAXQSIZE /頭指針加 1元素個數(shù)：(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE16、用那種數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)括號匹配的算法？17、已知二維數(shù)組的行數(shù)和列數(shù)，及每個元素需要的存儲單元數(shù)，求其需要 的存儲容量。18、特殊矩陣進(jìn)行壓縮存儲的目的是為了節(jié)約存儲空間19、對稱矩陣的壓縮存儲，求某元素的存儲地址。P10120、稀疏矩陣的壓縮存儲方法一般有三元組法和十字鏈表法21、求某廣義表的表尾p103取出的表尾為除去表頭之外，由其余元

5、素構(gòu)成的表22、字串的定義，子串定位函數(shù)index(s1,s2)的理解串中任意個連續(xù)的字符組成的子序列稱為該串的字串23、已知樹的孩子鏈表，求樹及其帶雙親的孩子鏈表24、二叉樹的常用性質(zhì)的應(yīng)用：性質(zhì)1-性質(zhì)425、已知完全二叉樹中的結(jié)點個數(shù)，求葉子結(jié)點的個數(shù)26、算法設(shè)計：求二叉樹中度分別為0、1、2的結(jié)點個數(shù)27、已知二叉樹的中序遍歷序列和后序遍歷序列，或已知二叉樹的中序遍歷 序列和前序遍歷序列，求二叉樹的形態(tài)28、哈夫曼樹的特點，哈夫曼樹的應(yīng)用：給出權(quán)值，求哈夫曼樹及哈夫曼編 碼。29、根據(jù)圖的鄰接矩陣存儲，求某頂點的入度和出度。30、已知圖的頂點和邊，求該圖的深度優(yōu)先遍歷31、連通圖的特

6、點：n個頂點至少有多少條邊？32、根據(jù)圖的鄰接表求鄰接矩陣，根據(jù)鄰接矩陣求深度優(yōu)先遍歷。33、折半查找的條件：順序存儲，且本身有序。并理解折半查找的過程34、散列查找的查找過程:如何根據(jù)散列函數(shù)構(gòu)造散列表，解決沖突的方法？ 求散列查找的平均查找長度。35、排序中的穩(wěn)定性是指：關(guān)鍵字值相同的記錄，其相對位置在排序后不發(fā) 生變化。36、掌握冒泡排序的排序過程及算法實現(xiàn)。37、插入類排序的特點38、根據(jù)一組關(guān)鍵字序列，構(gòu)造二叉排序樹，并求平均情況下的平均查找長 度。39、已知一組關(guān)鍵字序列，求基數(shù)排序每趟的排序過程。40、給出一段代碼，對其進(jìn)行時間復(fù)雜度的分析。（關(guān)鍵語句的執(zhí)行次數(shù)，和 n的數(shù)量級的

7、關(guān)系）1、計算機算法主要是指（C ）。計算方法排序方法解決問題的有限運算序列數(shù)據(jù)的調(diào)度方法1、關(guān)于邏輯結(jié)構(gòu)，以下說法錯誤的是（D ）邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的形式，內(nèi)容無關(guān)邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的相對位置無關(guān)邏輯結(jié)構(gòu)與所含數(shù)據(jù)元素的個數(shù)無關(guān)邏輯結(jié)構(gòu)與數(shù)據(jù)元素的存儲有關(guān)，是不能獨立于計算機的2、樹形結(jié)構(gòu)的特點是，一個結(jié)點可以有（B ）A.多個直接前驅(qū)B.多個直接后繼C.多個前驅(qū)D.一個后繼2、數(shù)據(jù)結(jié)構(gòu)從邏輯上分為（C)。A.內(nèi)部結(jié)構(gòu)與外部結(jié)構(gòu)B.靜態(tài)結(jié)構(gòu)與動態(tài)結(jié)構(gòu)C.線性結(jié)構(gòu)與非線性結(jié)構(gòu)D.邏輯結(jié)構(gòu)與非邏輯結(jié)構(gòu)3、以下關(guān)于線性表說法正確的是(D )。每個元素都有一個前驅(qū)和一個后繼線性表至少有一個元

8、素線性表中的元素必須按由大到小排序除首尾元素之外，其他元素都僅有一個直接前驅(qū)和一個直接后繼3、設(shè)棧的入棧序列是a,b,c,d, e則不可能的出棧序列是（C ）。e,d,c,b,aB. d,e,c,b,aC. d,c,e,a,bD. a,b,c,d,e4、設(shè)棧的入棧序列是1,2,3,4，則不可能的出棧序列是（D ）。1,2,4,3B. 2,1,3,4C. 1,4,3,2D. 4,3,1,24、判定循環(huán)隊列Q （元素最多為m個，隊頭指針為front，對尾指針rear）為空 的條件是（C ）。rear-front=mC. rear二front4、判定循環(huán)隊列Q （元素最多為m個， 的條件是（D ）。

9、rear-front=mC. front二rear%m4、棧和隊列的共同點是（C）rear-front-1=mD. front=(rear+1)%m隊頭指針為front,隊尾指針rear)為滿rear-front-1=mD. front=(rear+1)%mB.都是先進(jìn)先出都是先進(jìn)后出只允許在端點處插入和刪除元素D.沒有共同點4、表達(dá)式a*（b+c）-d的后綴表達(dá)式為（B）A. abcd*+-B. abc+*d-abc*+d-D. +*abcd5、線性表在鏈?zhǔn)酱鎯χ懈鹘Y(jié)點之間的地址（D ）A.必須全部地址連續(xù)B.部分地址必須連續(xù)C.不能連續(xù)D.連續(xù)與否無要求5、不帶頭結(jié)點的單鏈表Head為空的

10、判定條件是（A ）。A. Head=NULLB. Head-next=NULLC. Head-next=HeadD. Head!=NULL6、在單鏈表中，若要在p所指向的結(jié)點之后插入一個新的結(jié)點，則需要相繼修改（B）個指針域的值。A. 1 B. 2 C. 3 D. 46、在單鏈表中，若P所指結(jié)點不是最后結(jié)點，在P之后插入、所指結(jié)點，則執(zhí) 行（B ）。A. S-next=P; P-next=s;C. S-next=P-next;P=S;7、鏈棧相較于順序棧而言，優(yōu)點為A-插入操作更簡單C.不會出現(xiàn)?？盏那闆r8、數(shù)組的兩種常用基本操作是（A.建立與刪除C.查找和修改8、一維數(shù)組與線性表的區(qū)別是（S

11、-next=P-next; P-next=S;P-next=S; S-next=P;（B ）。通常不會出現(xiàn)棧滿的情況刪除操作更方便）索引與修改D.查找與索引A ）。A.前者長度固定，后者長度可變可變 C.兩者長度都固定可變B.后者長度固定，前者長度D.兩者長度均9、數(shù)組A中，行下標(biāo)i為07,列下標(biāo)j為09,每個元素占用3個字節(jié)長度，從首地址PA開始連續(xù)連續(xù)存放數(shù)組A中元素于存儲器，則至少需要的單元數(shù)是（D )。A. 80B. 100C. 270D. 24010、設(shè)廣義表L=（A,B,C）,則L的長度和深度分別為（CA. 3,1B. 3,2C. 1,2D. 1,110、對稀疏矩陣進(jìn)行壓縮存儲的目

12、的是（C )。11、11、A.便于進(jìn)行矩陣運算C.節(jié)省存儲空間B.D.便于輸入輸出降低運算的時間復(fù)雜度C語言中 bcd321ABCD 的子串可以是（DA.abcdB.321AB串的長度是指（B ）A.串中所含不同字母的個數(shù)）。C. abcABC D. 21AB B.串中所含字符的個數(shù)串中所含不同字符的個數(shù)串中所含非空格字符的個數(shù)12、深度為4的二叉樹最多有（C個結(jié)點A. 8B. 16C. 15D. 1712、A.a,c,b,e,dB. d,e,c,a,bC.d,e,a,b,cD. c,e,d,b,a已知某二叉樹的后序遍歷序列為d,a,b,e,c，中序遍歷序列為d,e,b,a,c,則其先序遍歷序

13、列為（12、對n（nN2 ）個權(quán)值均不相同的字符構(gòu)成哈夫曼樹，則該樹表述錯誤的是(A )。該樹一定是一棵完全二叉樹樹中沒有度為1的結(jié)點樹中兩個權(quán)值最小的結(jié)點一定是兄弟結(jié)點樹中任一非葉節(jié)點的權(quán)值一定不小于下一層任一結(jié)點的權(quán)值13、連通具有n個頂點的無向圖至少需要（D ）條邊。A. nB.n+1C. n/2D. n-113、設(shè)無向圖G=(V,E)中含7個頂點，則在圖G在任何情況下都是聯(lián)通的，則至少需要的邊數(shù)為(C)。A. 6B.14C. 16D. 1814、散列函數(shù)值應(yīng)按(C )取其值域的每一個值。A.最大概率B.最小概率C.同等概率D.平均概率14、排序方法的穩(wěn)定性是指(D )。排序算法能在規(guī)定

14、時間內(nèi)完成排序排序算法能得到確定的結(jié)果排序算法不允許有相同關(guān)鍵字的元素對于關(guān)鍵字值相同的記錄，其相對位置在排序后不發(fā)生變化15、在有序表3,9,14,27,39,44,56,68,71,85,90中，用折半查找法查找關(guān)鍵值 碼27,所需關(guān)鍵碼的比較次數(shù)為(B )。A. 2B.3C. 4D.515、冒泡排序的時間復(fù)雜度為(B )A. O(n)B. O(n2)C. O(log n) D. O(nlog n)22二、填空題(10小題，每小題2分，共20分)1、算法計算量的資源大小稱之為計算的復(fù)雜性。1、一般而言，樹形結(jié)構(gòu)中元素之間存在1： n的對應(yīng)比例關(guān)系2、當(dāng)利用長度為n的數(shù)組順序存儲一個棧時，假

15、設(shè)用top=0表示?？眨瑒t向這個棧插入一個元素時，首先應(yīng)執(zhí)行top=top+1來修改top指針。2、循環(huán)隊列用數(shù)組Am(下標(biāo)從0至m-1)存放其元素值，已知其頭尾指針分別為front,rear，則當(dāng)前隊列中元素的個數(shù)是 (rear-font+m) %m。3、在以Head為表頭指針的帶有頭結(jié)點的循環(huán)單鏈表中，判斷循環(huán)鏈表為空的條 件為 Head-next=Head 。3、在帶有頭結(jié)點的單鏈表L中(頭指針為Head)，指向第1個元素結(jié)點的指針 是 Head-next4、一個n*n的對稱矩陣以行為主序放入內(nèi)存，其容量為n*(n+1)/24、稀疏矩陣的壓縮存儲方法一般有三元組法和十字鏈表法。5、廣義表

16、的深度是指表中所含 括號的層數(shù)。6、設(shè) si=Hello ”,s2=”，s3=laochen”，則 s1,s2,s3 連后的結(jié) 果是 Hello laochen 。6、設(shè) si=xiaochen ,s2= ,s3= nihao ”，則 s1,s2,s3 連后的結(jié) 果是 xiaochen nihao 。7、下列程序段的時間復(fù)雜度為_O(n)。i=s=0；whilei(in)(i+；s+=i;8、二叉樹第i (iNl)層上最多有2i-i個結(jié)點。8、深度為k (kNl)的二叉樹最多有2k-i個結(jié)點。9、一棵有n個頂點的生成樹有且僅有_n-1條邊。9、設(shè)有向圖G有n個頂點，采用鄰接矩陣作為存儲結(jié)構(gòu)，則

17、該矩陣中含有壁 個數(shù)據(jù)元素。10、高度為5 (葉子層除外)的三階B樹至少有 個結(jié)點。10、假設(shè)n個關(guān)鍵字均有相同的Hash函數(shù)值，若用線性探測再散列方法將 這n個關(guān)鍵字映射存儲到Hash表中時，則共需n*(n-1)/2次探測三、算法應(yīng)用題(3小題，每小題5分，共15分)1、設(shè)線性表La和Lb，將兩個表合并成一個新的線性表并存于La中，請在下劃線處補充正確的代碼。(5分)Void union(&Linear_list La, &Linear_list Lb)(La_len=Linear_ListLength(La);Lb_len=Linear_ListLength(Lb);/ 求線性表的長度Fo

18、r(i=1;iLb_len;i+)GetElem(Lb,i,e);/取 Lb中第i個元素賦值給eIf(!LocateElem(La,e)ListInsert(La,+La_len,e);1、若要刪除線性表L中的第i個結(jié)點元素，請在下劃線處補充正確的代碼。(5 分)Void Delete(Linear_list &L, int i, int &n) (/n 為線性表的實際長度If(in) return ERROR;For(j=i;jtop= MAXLEN-1 );(MAXLEN-1)return 0; ( printf(棧滿!);/標(biāo)記位為0，棧滿不能else進(jìn)棧棧不為滿 s-top=s-top+1;s-datas-top=x;3、設(shè)計算法：交換二叉樹每個結(jié)點的左孩子和右孩子。請補充完整下列函數(shù)的 函數(shù)體。提示：如果某結(jié)點左右子樹為空，返回，否則交換該結(jié)點左右孩子，然 后遞歸交換左右子樹。（8分）voi