南郵《數(shù)據(jù)結構》練習冊期末復習題

《數(shù)據(jù)結構》綜合練習南京郵電大學高等函授《數(shù)據(jù)結構》綜合練習習題與解答南京郵電大學繼續(xù)教育學院2021年2月《數(shù)據(jù)結構》綜合練習注：此版本的綜合練習冊對應教材是《數(shù)據(jù)結構》，嚴蔚敏、吳偉民主編，清華大學出版社，2007年3月第一版，ISBN9787302147510一、選擇題:1.若結點的存儲地址與其關鍵字之間存在某種映射關系，則稱這種存儲結構為()A.順序存儲結構 B.鏈式存儲結構C.索引存儲結構 D.散列存儲結構2.在長度為n的順序表的第i(1≤i≤n+1)個位置上插入一個元素，元素的移動次數(shù)為()A.n-i+1B.n-iC.i D.i-13.對于只在表的首、尾兩端進行插入操作的線性表，宜采用的存儲結構為()A.順序表 B.用頭指針表示的單循環(huán)鏈表C.用尾指針表示的單循環(huán)鏈表 D.單鏈表4.若進棧序列為a,b,c，則通過入出棧操作可能得到的a,b,c的不同排列個數(shù)為()A.4 B.5 C.6 D.75.為查找某一特定單詞在文本中出現(xiàn)的位置，可應用的串運算是()A.插入 B.刪除C.串聯(lián)接D.子串定位6.已知函數(shù)Sub(s,i,j)的功能是返回串s中從第i個字符起長度為j的子串，函數(shù)Scopy(s,t)的功能為復制串t到s。若字符串S=“SCIENCESTUDY”，則調用函數(shù)Scopy(P,Sub(S,1,7))后得到()A.P=″SCIENCE″ B.P=″STUDY″C.S=″SCIENCE″ D.S=″STUDY″7.無論采用何種遍歷方式，訪問序列均相同的非空二叉樹的結點個數(shù)是()A.0 B.1C.28.下列函數(shù)中對應的時間復雜度（n為問題規(guī)模）最小的是（）A.T1(n)=nlog2n+5000n B.T2(n)=n2-800nC.T3(n)=100000000log2n D.T4(n)=50n+98019.下列陳述中正確的是()A.二叉樹是度為2的有序樹B.二叉樹中結點只有一個孩子時無左右之分C.二叉樹中必有度為2的結點D.二叉樹中最多只有兩棵子樹，并且有左右之分10.n個頂點的有向完全圖中含有向邊的數(shù)目最多為()A.n-1B.nC.n(n-1)/2D.n(n-1)11.計算機識別、存儲和加工處理的對象被統(tǒng)稱為()A.數(shù)據(jù)B.數(shù)據(jù)元素C.數(shù)據(jù)結構D.數(shù)據(jù)類型12.在具有n個結點的有序單鏈表中插入一個新結點并使鏈表仍然有序的時間復雜度是()A.O(1) B.O(n)C.O(nlogn)D.O(n2)13.隊和棧的主要區(qū)別是()A.邏輯結構不同 B.存儲結構不同C.所包含的運算個數(shù)不同 D.限定插入和刪除的位置不同14.鏈棧與順序棧相比，比較明顯的優(yōu)點是()A.插入操作更加方便B.刪除操作更加方便C.不會出現(xiàn)下溢的情況D.不會出現(xiàn)上溢的情況15.采用兩類不同存儲結構的字符串可分別簡稱為()A.主串和子串B.順序串和鏈串C.目標串和模式串D.變量串和常量串16.在目標串T［0..n-1］=“xwxxyxy”中，對模式串P［0..m-1］=″xy″進行子串定位操作的結果是()A.0B.2C.417.以下排序方法中,平均時間復雜度為O(n2)的是（）A.歸并排序 B.直接選擇排序 C.堆排序 D.快速排序18.對于一個具有n個頂點的無向圖，若采用鄰接矩陣表示，則該矩陣的大小是（）A.n-1 B.n C.(n-1)2 D.n219.二叉樹中第5層上的結點個數(shù)最多為()A.8B.1520.若線性表最常用的操作是存取第i個元素及其前趨和后繼元素的值，為節(jié)省時間應采用的存儲方式是()A.順序表 B.單鏈表C.雙向鏈表 D.單循環(huán)鏈表21.如果某圖的鄰接矩陣是對角線上元素均為零的上三角矩陣，則此圖是()A.有向完全圖 B.連通圖C.無向圖 D.有向無環(huán)圖22.對n個關鍵字的序列進行快速排序，平均情況下的時間復雜度為()A.O(1)B.O(logn) C.O(n)D.O(nlog2n)23.對表長為n的順序表進行順序查找，在查找概率相等的情況下，查找成功的平均查找長度為()A. B.C.D.n24.以下排序方法中,最好情況下時間復雜度為O(n)的是（）A.直接插入排序 B.直接選擇排序 C.堆排序 D.快速排序25.稠密索引是在索引表中()A.為每個記錄建立一個索引項 B.為每個頁塊建立一個索引項C.為每組記錄建立一個索引項 D.為每個字段建立一個索引項26.設有兩個串p和q，求串q在串p中首次出現(xiàn)的位置的運算稱為（）A.連接 B.求子串C.模式匹配D.求串長27.棧S和隊列Q的初始狀態(tài)為空，元素1、2、3、4、5、6依次通過棧，一個元素出棧后即入隊，若六個元素出隊順序為2、4、3、6、5、1，則棧的容量至少是（） A.2 B.3 C.4 D.28.二叉樹結點的先序序列、中序序列、后序序列中，所有葉子結點的先后順序（） A.完全相同 B.都不相同 C.先序和中序相同，而與后序不同 D.中序和后序相同，與先序不同29.下面關于線性表的敘述中，錯誤的是（） A.線性表采用順序存儲，必須占用一片連續(xù)的存儲單元 B.線性表采用鏈接存儲，不必占用一片連續(xù)的存儲單元 C.線性表采用順序存儲，便于進行插入和刪除操作 D.線性表采用鏈接存儲，便于進行插入和刪除操作30.一個向量第一個元素的存儲地址是100，每個元素的長度是2，則第五個元素地址是（） A.110 B.108 C.100 D.31.在數(shù)據(jù)結構中，數(shù)據(jù)的基本單位是()A.數(shù)據(jù)項 B.數(shù)據(jù)類型C.數(shù)據(jù)元素 D.數(shù)據(jù)變量32.在最好和最壞情況下的時間復雜度均為O(nlogn)且穩(wěn)定的排序方法是()A.快速排序B.堆排序C.歸并排序D.插入排序33.數(shù)組的基本運算是（ ）A.插入數(shù)組元素 B.刪除數(shù)組元素C.只可以讀 D.讀和寫34.AVL樹是一種平衡的二叉排序樹，樹中任一結點的()A.左、右子樹的高度均相同B.左、右子樹高度差的絕對值不超過1C.左子樹的高度均大于右子樹的高度D.左子樹的高度均小于右子樹的高度35.在VSAM文件的控制區(qū)間中，記錄的存儲方式為()A.無序順序 B.有序順序C.無序鏈接 D.有序鏈接36.串是一種特殊的線性表，其特殊性體現(xiàn)在（）A.可以連續(xù)存儲 B.數(shù)據(jù)元素是字符C.可以鏈接存儲 D.數(shù)據(jù)元素可以是任意類型37.對下列四個序列用快速排序的方法進行排序，以序列的第一個元素為基礎進行劃分。在第一趟劃分過程中，元素移動次數(shù)最多的序列是（）A.70,75,82,90,23,16,10,68B.70,75,68,23,10,16,90,82C.82,75,70,16,10,90,68,23D.23,10,16,70,82,75,68,9038.若關鍵碼序列（K1,K2,…,Kn）是一個堆，序列中元素的關系是（）A.Ki≤K2i或Ki≥K2i（i=1,2,…[n/2]）Ki≤K2i+1Ki≥K2i+1B.K1≤K2≤…≤KnC.K1≥K2≥…≥KnD.元素之間的值沒有任何限制39.對關鍵碼Κ=｛53,30,37,12,45,24,96｝，從空二叉樹開始逐個插入每個關鍵碼，建立與集合Κ對應的二叉排序樹（又稱二叉查找樹）BST，若希望得到的BST高度最小，應選擇下列輸入序列（）A.45,24,53,12,37,96,30 B.37,24,12,30,53,45,96C.12,24,30,37,45,53,96 D.30,24,12,37,45,96,5340.鄰接矩陣是對稱矩陣的圖為（）A.有向圖 B.帶權有向圖C.帶權連通圖 D.無向圖41.計算機識別、存儲和加工處理的對象被統(tǒng)稱為()A.數(shù)據(jù)B.數(shù)據(jù)元素C.數(shù)據(jù)結構D.數(shù)據(jù)類型42.在具有n個結點的有序單鏈表中插入一個新結點并使鏈表仍然有序的時間復雜度是()A.O(1) B.O(n)C.O(nlogn)D.O(n2)43.隊和棧的主要區(qū)別是()A.邏輯結構不同 B.存儲結構不同C.所包含的運算個數(shù)不同 D.限定插入和刪除的位置不同44.鏈棧與順序棧相比，比較明顯的優(yōu)點是()A.插入操作更加方便B.刪除操作更加方便C.不會出現(xiàn)下溢的情況D.不會出現(xiàn)上溢的情況45.采用兩類不同存儲結構的字符串可分別簡稱為()A.主串和子串B.順序串和鏈串C.目標串和模式串D.變量串和常量串46.在目標串T［0..n-1］=“xwxxyxy”中，對模式串P［0..m-1］=″xy″進行子串定位操作的結果是()A.0B.2C.447.以下排序方法中,平均時間復雜度為O(n2)的是（）A.歸并排序 B.直接選擇排序 C.堆排序 D.快速排序48.對于一個具有n個頂點的無向圖，若采用鄰接矩陣表示，則該矩陣的大小是（）A.n-1 B.n C.(n-1)2 D.n249.二叉樹中第5層上的結點個數(shù)最多為()A.8B.15C50.若線性表最常用的操作是存取第i個元素及其前趨和后繼元素的值，為節(jié)省時間應采用的存儲方式是()A.順序表 B.單鏈表C.雙向鏈表 D.單循環(huán)鏈表51.如果某圖的鄰接矩陣是對角線上元素均為零的上三角矩陣，則此圖是()A.有向完全圖 B.連通圖C.無向圖 D.有向無環(huán)圖52.對n個關鍵字的序列進行快速排序，平均情況下的時間復雜度為()A.O(1)B.O(logn) C.O(n)D.O(nlog2n)53.對表長為n的順序表進行順序查找，在查找概率相等的情況下，查找成功的平均查找長度為()A. B.C.D.n54.以下排序方法中,最好情況下時間復雜度為O(n)的是（）A.直接插入排序 B.直接選擇排序 C.堆排序 D.快速排序55.稠密索引是在索引表中()A.為每個記錄建立一個索引項 B.為每個頁塊建立一個索引項C.為每組記錄建立一個索引項 D.為每個字段建立一個索引項56.設有兩個串p和q，求串q在串p中首次出現(xiàn)的位置的運算稱為（）A.連接 B.求子串C.模式匹配D.求串長57.棧S和隊列Q的初始狀態(tài)為空，元素1、2、3、4、5、6依次通過棧，一個元素出棧后即入隊，若六個元素出隊順序為2、4、3、6、5、1，則棧的容量至少是（） A.2 B.3 C.4 D.58.二叉樹結點的先序序列、中序序列、后序序列中，所有葉子結點的先后順序（） A.完全相同 B.都不相同 C.先序和中序相同，而與后序不同 D.中序和后序相同，與先序不同59.下面關于線性表的敘述中，錯誤的是（） A.線性表采用順序存儲，必須占用一片連續(xù)的存儲單元 B.線性表采用鏈接存儲，不必占用一片連續(xù)的存儲單元 C.線性表采用順序存儲，便于進行插入和刪除操作 D.線性表采用鏈接存儲，便于進行插入和刪除操作60.一個向量第一個元素的存儲地址是100，每個元素的長度是2，則第五個元素地址是（） A.110 B.108 C.100 D.二、判斷題:1.存在這樣的二叉樹，對它采用任何次序的遍歷，其結果相同。 （ ）2.完全二叉樹中，若一個結點沒有左孩子，則它必是樹葉。 （ ）3.若連通網(wǎng)絡上各邊的權值均不相同，則其最小生成樹是唯一的。（）4.隊列和棧都是運算受限的線性表。 （ ）5.算法DFS應用于一個連通圖時，所經(jīng)過的邊形成一棵樹。 （ ）6.當有序表中個記錄的查找概率相當時，其靜態(tài)最優(yōu)二叉排序樹就是折半查找判定樹。7.稀疏圖用鄰接表存儲表示比較好，稠密圖用鄰接矩陣表示比較好。（）8.在有向圖中，各頂點的入度之和等于各頂點的出度之和。（）9.無論是有向圖還是無向圖，其鄰接矩陣表示都是唯一的。（）10.連通圖的生成樹包含了圖中所有頂點。（）11.無環(huán)有向圖才能進行拓撲排序。（）12.連通圖的廣度優(yōu)先遍歷中一般要用隊列來暫存剛訪問過的頂點。（）13.圖的深度優(yōu)先遍歷中一般用棧來暫存剛訪問過的頂點。 （）14.度為m的樹中至少有一個度為m的結點。 （）15.在先序遍歷二叉樹的序列中，對于任何結點，其子樹的所有結點都是直接跟在該結點之后。 （）16.哈夫曼樹中不存在度為1的結點。 （）17.當二叉樹中結點樹多于1個時，不可能根據(jù)結點的先序遍歷序列和后序遍歷序列唯一的確定該二叉樹的邏輯結構。 （）18.存在這樣的二叉樹，對它采用任何次序的遍歷，結構相同。 （）19.對n個元素執(zhí)行直接選擇排序，關鍵字的比較次數(shù)總是n(n-1)/2次。（）20.只有在線性表的初始狀態(tài)為反序的情況下，直接插入排序過程中，元素的移動次數(shù)才會達到最大值。 （）21.只有在線性表的初始狀態(tài)為反序的情況下，冒泡排序過程中，元素的移動次數(shù)才會達到最大值（）22.對n個元素執(zhí)行快速排序，在進行第一次劃分時，關鍵字的比較次數(shù)總是n-1次。（）23.分塊查找的效率與線性表被分成多少塊有關。 （）24.在二叉排序樹中，新結點總是作為葉子來插入的。（）25.順序查找方法只能在順序存儲結構上進行。（） 26.二分查找可以在有序的雙向鏈表上進行。 （）27.二叉排序樹是用來進行排序的。 （）28.數(shù)據(jù)元素是數(shù)據(jù)的最小單位。（）29.數(shù)據(jù)的邏輯結構是指數(shù)據(jù)的各數(shù)據(jù)項之間的邏輯關系。 （）30.順序存儲方式只能用于存儲線性結構。（）31.將一顆樹轉換成二叉樹后，根結點沒有左子樹。（）32.快速排序在任何情況下均可得到最快的排序效果。（）三、名詞解釋：索引存儲：雙向循環(huán)鏈表：滿二叉樹：最小生成樹：交換排序：串相等：隊列：完全二叉樹：深度優(yōu)先搜索：AVL樹：棧：鄰接表：二分查找法：二叉排序樹：冒泡排序：平均時間復雜度：順序表：三叉鏈表：倒排文件：直接選擇排序：最壞情況時間復雜度：靜態(tài)雙親鏈表：哈夫曼樹：散列查找：ISAM文件：存儲密度：順序隊假溢出：結點的度：二次探測法：B+樹：判定樹：樹的深度：公共溢出區(qū)法：索引順序文件：多重表文件：單鏈表：稀疏矩陣：靜態(tài)查找表：索引順序表：先根遍歷：四、算法閱讀題：1.閱讀下面的鏈棧的退棧操作，棧頂元素通過參數(shù)返回，它的直接后繼成為新的棧頂，請在空缺處填入合適的內容，使其成為一個完整的算法。intPop(LStackTp*ls,DataType*x){LStackTp*p;if(ls!=NULL){p=ls;（1）_______________（2）_______________free(p);/*釋放原棧頂結點空間*/return（1）;}elsereturn（0）;}（1）_______________（2）_______________2.閱讀下面算法，回答問題：voidfun1(intn,listr){for(i=1;i=n-1;i++){flag=1;for(j=1;j=n－i;j++)if(r[j+1].key<r[j].key){flag=0;p=r[j];r[j]=r[j+1];r[j+1]=p;}if(flag)return;}｝說明算法fun1（）的功能。該算法的時間復雜度。3閱讀下面算法，回答問題：Intvisited[vnum];Count_Component(GraphTpg){intcount;for(v=0;v<g.vexnum;v++)/*初始化visited數(shù)組*/visited[v]=0;count=0;for(v=0;v<g.vexnum;v++)if(!visited=[v]){count++;printf("連通分量%d包含以下頂點：",count);Dfs(g,v);Printf("\n");}}如果用上面算法遍歷如下圖，看到輸出結果為：4.閱讀下面算法，回答問題：voidfun1(SeqStack*S){inti;arr[100];n=0;while(StackEmpty(S))arr[n++]=Pop(S);for(i=0,i<n;i++)Push(S,arr[i]);}（1）簡述fun1（）的功能（2）如果S的入棧順序為{A,B,C,D}，請畫出最終S棧內存儲情況。5.閱讀下面的鏈隊的出隊列算法，出隊元素由參數(shù)返回，請在空缺處填入合適的內容，使其成為一個完整的算法。OutQueue(QueptrTp*lq,DataType*x){LqueueTp*s;if(lq->front==lq->rear){error("隊空");return（0）;}else{（1）______________（2）______________（3）______________if(s->next==NULL)lq->rear=lq->front;free(s);return（1）;}}（1）______________（2）______________（3）______________6.已知下面算法，回答以下問題intcount=0;voidfun1(bitreptrt){if(t!=NULL){if((t->lchild==NULL)&&(t->rchild==NULL))count++;fun1(t->lchild,count);fun1(t->rchild,count);}}簡述fun1（）的功能如果程序遍歷的二叉樹如下，寫出最終count的結果7.閱讀下列算法并回答問題：voidfun3(listr);{for(i=2;i=n;i++){r[0]=r[i];j=i-1;while(r[0].key<r[j].key){r[j+1]=r[j];j――;}r[j+1]=r[0];}}簡述fun3（）的功能在程序中r[0]的功能8.閱讀下面算法，回答以下問題intfun1(StackS){intn=0;while(!StackEmpty(S)){n++;Pop(S);}return(n）;}如果現(xiàn)在{7,2,3,23,56,9}6個元素依次入棧，算法返回值是多少？簡述fun1（）的功能。9.閱讀下面的二分法查找的算法，請在空缺處填入合適的內容，使其成為一個完整的算法。intbinsearch(sqtableR,keytypeK){low=1;hig=R.n;while(low<=hig){（1）______________switch{caseK==R.item[mid].key:return(mid);caseK<R.item[mid].key:（2）______________；break;caseK>R.item[mid].key:（3）______________；break;}}return(0);}（1）______________（2）______________（3）______________10.有向圖的鄰接表類型定義如下，閱讀下面算法，要求回答下面問題：#definevnum5typedefstructarcnode{intadjvex;structarcnode*nexttarc;}ArcNodeTp;typedefstructvexnode{intvertex;ArcNodeTp*firstarc;}AdjList[vnum];typedefstructgraph{AdjListadjlist;intvexnum,arcnum;}Graphtp;voidIndegree(AdjListg){for(i=0;i<n;j++){num=0;for(j=0;j<n;j++)if(i!=j){p=g[j].firstarc;while(p){if(p->adjvex==i)num++;p=p->next;}}printf(“頂點%d：%d\n”,g[i].vexdata,num);}}已知有向圖如下，該算法的輸出結果為：該算法的功能。11.閱讀下面的單鏈表第i位置上插入一個以x為值的新結點的算法，請在空缺處填入合適的內容，使其成為一個完整的算法。voidins_lklist(lklisthead,inti){p=find_lklist(head,i-1);if(p==NULL)error('不存在第i個位置');else{s=malloc(size);s->data=x;（1）_______________。（2）_______________。}（1）_______________。（2）_______________。12.下面是在順序棧上實現(xiàn)的一個?；静僮?，該操作的功能是_________。typedefstruct{DataTypedata[100]；inttop；}SeqStack；DataTypefun1(SeqStack*S){if(StackEmpty(S))Error(”Stackisempty”)；return（S->data[S->top]）；}13.閱讀下面算法，回答問題。intfun2(MGraph*G,inti){intd=0,j;for(j=0;j<n;j++){if(G->edges[i][j])d++;if(G->edges[j][i])d++;}return

(d);}(1)簡述函數(shù)fun2（）的功能;(2)寫出函數(shù)fun2（）的時間復雜度。14.閱讀下面算法，回答問題：LinkListfun1(LinkListL)/*L是無頭結點單鏈表*/

{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;

}

returnL;

}簡述fun1（）的功能如果L的初始狀況如下，請畫出最終L的狀態(tài)15.閱讀下面算法，算法功能為往無向圖的鄰接矩陣中插入頂點，解釋（1）（2）兩句語句功能voidAddVertexMGraph(MGraph*G,VertexTypex){if(G->n>=MaxVertexNum)Error("頂點數(shù)太多")；G->vexs[G->n]=x;（1）G->n++；（2）}（1）______________（2）______________16.閱讀下面程序，回答問題：for(i=1;i<＝n;i++) for(j=1;j<＝i;j++) t=t+1;該程序段的時間復雜性量度是多少？（要求寫出運算步驟）17.閱讀下面算法借助棧將一個帶頭結點的單鏈表倒置，請在空缺處填入合適的內容，使其成為一個完整的算法。voidreverse_list(LkListTp*head){LStackTpls,p;datatypex;InitStack(&ls);/*初始化鏈棧*/p=(*head)->next;while(p!=NULL){Push(&ls,p->data);p=p->next;}（1）_____________while(!EmptyStack(ls)){Pop(&ls,&x);（2）_____________（3）_____________}（1）_____________（2）_____________（3）_____________18.閱讀下面算法，算法功能為向無向圖的鄰接表中插入一個頂點，解釋（1）（2）（3）的語句功能voidAddVertexALGraPh(ALGrahp*G,VertexTypex){if(G->n>=MaxVertexNum)Error("頂點數(shù)太多")；G->adjlist[G->n].vertex=x;（1）G->adjlist[G->n].firstedge=NULL;（2）G->n++；（3）}（1）_____________（2）_____________（3）_____________19.for(i=1；i<=n；i++){s=i+2;

for(j=1；j<=n；j++)

s=2*j；}該程序段的時間復雜度為多少？（寫出運算步驟）20.閱讀下面算法，要求回答下面問題：typedefstrutcycqueue{DataTypedata[maxsize];intrear,front;}CycqueueTp;CycqueueTpsq;intfun2(CycqueueTp*sq,DataTypex){if((sq->rear+1)%maxsize==sq->front){error("隊滿");return0;}else{sq->rear=(sq->rear+1)%maxsize;sq->data[sq->rear]=x;return1;}}intfun3(CycqueueTp*sq,DataType*x){if((sq->front==sq->rear){error("隊空");return0;}else{sq->front=(sq->front+1)%maxsize;*x=sq->data[sq->front];return1;}}intfun4(cycqueueTpsq,DataType*x){if(sq.rear==sq.front)return0;else{*x=sq.data[(sq.front+1)%maxsize];return1;}}（1）算法fun2（）的功能。（2）算法fun3（）的功能。（3）算法fun4（）的功能。21.閱讀下面廣度優(yōu)先搜索算法，請在空缺處填入合適的內容，使其成為一個完整的算法。Bfs(GraphTpg,intv){QueptrTpQ;ArcNodeTp*p;InitQueue(&Q);Printf("%d",v);Visited[v]=1;EnQueue(&Q,v);While(!EmptyQueue(Q)){（1）_____________p=g.adjlist[v].firstarc;while(p!=NULL){if(!visited[p->adjvex]){printf("%d",p->adjvex);（2）_____________EnQueue(&Q,p->adjvex);}p=p->nextarc;}}}（1）_____________（2）_____________22.已知下列程序是完成鏈隊lq中將數(shù)據(jù)元素x的入隊列運算，請在空缺處填入合適的內容，使其成為一個完整的算法。鏈隊類型定義如下typedefstructlinked_queue{DataTypedata;structlinked_queue*next;}LqueueTp;typedefstructqueuetr{LqueueTp*front,*rear;}QueptrTp;QueptrTplq;voidenqueue(QueptrTp*lq;DataTypex){LqueueTp*p;p=(LqueueTp*)malloc(sizeof(LqueueTp));p->data=x;p->next=NULL;（1）____________（2）____________}（1）____________（2）____________23.閱讀下面算法，回答問題：Intvisited[vnum];Count_Component(GraphTpg){intcount;for(v=0;v<g.vexnum;v++)/*初始化visited數(shù)組*/visited[v]=0;count=0;for(v=0;v<g.vexnum;v++)if(!visited=[v]){count++;printf("連通分量%d包含以下頂點：",count);Dfs(g,v);Printf("\n");}}如果用上面算法遍歷如下圖，看到輸出結果為：24.已知下面算法，回答以下問題intcount=0;voidfun1(bitreptrt){if(t!=NULL){if((t->lchild==NULL)&&(t->rchild==NULL))count++;fun1(t->lchild,count);fun1(t->rchild,count);}}簡述fun1（）的功能如果程序遍歷的二叉樹如下，寫出count的值五、簡答題：1.在單鏈表和雙向鏈表中，能否從當前結點出發(fā)訪問到任一結點？為什么？2．若較頻繁地對一個線性表進行插入和刪除操作，改線性表宜采用何種存儲結構？為什么？ 3.對關鍵字序列（72，87，61，23，94，16，05，58）進行堆排序，使之按關鍵字遞減次序排列。請寫出排序過程中得到的初始堆和前三趟的序列狀態(tài)。4.在關鍵字序列（07，12，15，18，27，32，41，92）中用二分查找和給定值92相等的關鍵字，請寫出查找過程中依次和給定值92比較的關鍵字。 5.若線性表的總數(shù)基本穩(wěn)定，且很少進行插入和刪除，但要求以最快的速度存取線性表在的元素，那么應采用哪種存儲結構？為什么？ 6．說明什么是順序隊的“假溢出”，并給出解決方法。7.如何判定循環(huán)隊列的空和滿？并給出循環(huán)隊列中元素個數(shù)的計算式（設隊長最大值為N，隊頭指針front,隊尾指針rear）。 8.請畫出具有三個結點的二叉樹所有可能的不同形態(tài)？9.簡述無向圖和有向圖有哪兩種主要的存儲結構，并說明各種結構在圖中的不同操作（如圖的遍歷，有向圖的拓撲排序等）中有什么樣的優(yōu)越性？ 10.試述順序查找法、二分查找法和分塊查找法對被查找的表中元素的要求。11.當實現(xiàn)插入排序過程中，可以用二分查找來確定第i個元素在前i-1個元素中的可能插入位置（二分插入排序），這樣做能否改善插入排序的時間復雜度？為什么？12.指出堆和二叉排序樹的區(qū)別。13.如果一棵哈夫曼樹T有n0個葉子結點，那么，樹T有多少個結點？要求給出求解過程。14.以關鍵字序列{265，301，751，129，937，863，742，694，76，438}為例，給出歸并排序算法的各趟排序結束時，關鍵字序列的狀態(tài)。15.設T是非空的二叉樹，則滿足以下特點的T分別應是什么形態(tài)？16.常用的散列函數(shù)構造法有哪些？17.什么是文件的存儲結構，常見的有哪幾種結構？ 18.簡述散列文件的特點。 19.已知關鍵字序列（49，38，65，97，76，13，27，49），寫出按升序進行快速排序的各趟劃分及最終的排序結果。 20.已知關鍵字序列（70，73，69，23，93，18，11，68），寫出按升序進行快速排序的各趟劃分及最終的排序結果。 21.什么是內排序？按排序過程中依據(jù)的不同原則對內部排序方法進行分類有哪些方法? 22.已知一棵二叉樹的后序遍歷序列是DABEC，中序遍歷序列是DEBAC，則（1）寫出先序遍歷系列（2）已知結點的前序序列和后序序列，能否唯一確定其中序遍歷序列。23.已知結點的前序遍歷序列是ABCDEFG，中序遍歷序列是CBEDAFG，畫出整棵二叉樹（2）已知結點的中序序列和后序序列，能否唯一確定一棵二叉樹。24.已知有向圖G=（V，E），其中V={V1，V2，V3，V4，}，E={<V2，V1>,<V3,V2>,<V4,V3>,<V4,V2>,<V1,V4>}，試畫出G的鄰接矩陣和鄰接表，并寫出深度優(yōu)先遍歷序列、廣度優(yōu)先遍歷序列（以V1為出發(fā)點）。25.一份電文中共使用5個字符：A,B,C,D,E他們的出現(xiàn)頻率為4、7、5、2、9，試畫出對應的哈夫曼樹（按左子樹根結點的權小于等于右子樹根結點的權的次序構造）。26.一份電文中共使用5個字符：H,M,N,K,P他們的出現(xiàn)頻率為4、7、5、2、9，求出每個字符的哈夫曼編碼。(構造對應的哈夫曼樹時按左子樹根結點的權小于等于右子樹根結點的權的次序構造）。28.現(xiàn)有按中序遍歷二叉樹的結果為ABC，問有幾種不同形態(tài)的二叉樹看可得到這一遍歷結果？

《數(shù)據(jù)結構》綜合練習參考答案：一、選擇題:1.D2.A3.C4.B5.D6.A7.B8.C9.D10.D11.A12.B13.D14.D15.B16.C17.B18.D19.C20.A21.D22.D23.C24.A25.A26.C27.B28.A29.C30.B31.C32.C33.D34.B35.B36.B37.A38.A39.B40.D41.A42.B43.D44.D45.B46.C47.B48.D49.C50.A51.D52.D53.C54.A55.A56.C57.B58.A59.C60.B二、判斷題:1.存在這樣的二叉樹，對它采用任何次序的遍歷，其結果相同。 （√）√2.完全二叉樹中，若一個結點沒有左孩子，則它必是樹葉。 （ ）√3.若連通網(wǎng)絡上各邊的權值均不相同，則其最小生成樹是唯一的。（）√4.隊列和棧都是運算受限的線性表。 （ ）√5.算法DFS應用于一個連通圖時，所經(jīng)過的邊形成一棵樹。 （ ）√6.當有序表中個記錄的查找概率相當時，其靜態(tài)最優(yōu)二叉排序樹就是折半查找判定樹。7.稀疏圖用鄰接表存儲表示比較好，稠密圖用鄰接矩陣表示比較好。（）√8.在有向圖中，各頂點的入度之和等于各頂點的出度之和。（）√9.無論是有向圖還是無向圖，其鄰接矩陣表示都是唯一的。（）√10.連通圖的生成樹包含了圖中所有頂點。（）√11.無環(huán)有向圖才能進行拓撲排序。（）√12.連通圖的廣度優(yōu)先遍歷中一般要用隊列來暫存剛訪問過的頂點。（）√13.圖的深度優(yōu)先遍歷中一般用棧來暫存剛訪問過的頂點。 （）√14.度為m的樹中至少有一個度為m的結點。 （）√15.在先序遍歷二叉樹的序列中，對于任何結點，其子樹的所有結點都是直接跟在該結點之后。 （）√16.哈夫曼樹中不存在度為1的結點。 （）√17.當二叉樹中結點樹多于1個時，不可能根據(jù)結點的先序遍歷序列和后序遍歷序列唯一的確定該二叉樹的邏輯結構。 （）√18.存在這樣的二叉樹，對它采用任何次序的遍歷，結構相同。 （）√19.對n個元素執(zhí)行直接選擇排序，關鍵字的比較次數(shù)總是n(n-1)/2次。（）√20.只有在線性表的初始狀態(tài)為反序的情況下，直接插入排序過程中，元素的移動次數(shù)才會達到最大值。 （）√21.只有在線性表的初始狀態(tài)為反序的情況下，冒泡排序過程中，元素的移動次數(shù)才會達到最大值。 （）√22.對n個元素執(zhí)行快速排序，在進行第一次劃分時，關鍵字的比較次數(shù)總是n-1次。（√）23.分塊查找的效率與線性表被分成多少塊有關。 （）√24.在二叉排序樹中，新結點總是作為葉子來插入的。（）√25.順序查找方法只能在順序存儲結構上進行。 （X）。正確：順序查找方法也可以在鏈式存儲結構上進行。26.二分查找可以在有序的雙向鏈表上進行。 （X）。正確：二分查找只能在可以進行隨機查找存儲結構上進行，即只能在順序存儲的有序表上進行。27.二叉排序樹是用來進行排序的。 （X）。正確：二叉排序樹主要用于改進一般二叉樹的查找效率。28.數(shù)據(jù)元素是數(shù)據(jù)的最小單位。 （X）。正確：數(shù)據(jù)項是數(shù)據(jù)的最小單位。29.數(shù)據(jù)的邏輯結構是指數(shù)據(jù)的各數(shù)據(jù)項之間的邏輯關系。 （X）。正確：數(shù)據(jù)的邏輯結構是指數(shù)據(jù)的各數(shù)據(jù)元素之間的邏輯關系。30.順序存儲方式只能用于存儲線性結構。（X）。正確：順序存儲方式也可以用于存儲樹性結構，如完全二叉樹可用一維數(shù)組存儲。31.將一顆樹轉換成二叉樹后，根結點沒有左子樹。 （X）。正確：通常有左子樹而無右子樹。32.快速排序在任何情況下均可得到最快的排序效果。（X）。正確：快速排序在待排序記錄關鍵字為隨機分布是效果最好，基本有序是效果最差。三、名詞解釋：索引存儲：每個存儲結點只含有一個數(shù)據(jù)元素，所有存儲結點連續(xù)存放，此外增設一個索引表，索引表中的索引指示各存儲結點的存儲位置或存儲位置區(qū)間端點。雙向循環(huán)鏈表：雙鏈表兩個鏈域prior和next分別指向本結點數(shù)據(jù)域data所含數(shù)據(jù)元素的直接前驅和直接后繼所在的結點。所有結點通過前驅指針和后繼指針鏈接在一起，再加上起標識作用的頭指針，就形成的了雙向循環(huán)鏈表。滿二叉樹：深度為k的且有2k－1個結點的二叉樹。最小生成樹：n個頂點的無向完全圖，共有n（n－1）/2條邊，構造一個權最小的n－1條邊并使這個圖仍然連通的樹。交換排序：根據(jù)序列中的兩個記錄鍵值的比較結果來對換這兩個記錄在序列中的位置。特點是：將鍵值較大的記錄向尾部移動，鍵值較小的記錄向序列的前部移動。串相等：兩個串相等當且僅當兩個串的長度相等并且各個對應位置上的字符都相同。隊列：在這種線性表上，插入限定在表的一段進行，刪除限定在表的另一端進行。完全二叉樹：在一棵深度為k的滿二叉樹上刪除第k層上最右邊的連續(xù)j（0≤j≤2k－1）個結點。深度優(yōu)先搜索：首先訪問出發(fā)點，然后任選一個vi的未訪問國的鄰接點vj，以vj為新的出發(fā)點繼續(xù)進行深度優(yōu)先搜索，直至所有頂點都被訪問過。AVL樹：平衡二叉排序樹，或者是空樹，或者是一個任一結點的左子樹和右子樹的高度至多差1的二叉排序樹。棧：一種特殊的線性表,進行插入和刪除的運算都只限定在表的一端進行。允許插入和刪除的這一端稱為棧頂，另一端稱為棧底。鄰接表：圖的一種鏈式存儲結構，在鄰接表中，對圖中每個頂點建立一個單鏈表，n個頂點就要建n個鏈表，無向圖中，單鏈表中的結點表示依賴于頂點vi的邊，對于有向圖，是以頂點vi為尾的弧。二分查找法：每次將處于查找區(qū)間中間位置上的數(shù)據(jù)元素的鍵值和給定值K比較，若不等則縮小查找區(qū)間并在新的區(qū)間內重復，知道查找成功或查找區(qū)間長度為0為止。二叉排序樹：或者是一棵空樹，或者是一棵滿足下列條件的二叉樹：若它的左子樹不空，則左子樹上所有結點的鍵值均小于它的根結點的鍵值。若它的右子樹不空，則右子樹上所有結點的鍵值均大于它的根結點的鍵值。它的左右子樹也分別是二叉排序樹。冒泡排序：先將第一和第二個鍵值比較交換，然后比較第二和第三個鍵值交換，以此類推，直到第n個和n－1個記錄比較交換，這稱為一趟起泡。每趟將鍵值最大的記錄換到最后。重復以上過程，每次移動都向最終目標前進，直至沒有記錄需要交換為止。平均時間復雜度：在算法所有輸入下的計算量的加權平均值作為算法的計算量。順序表：順序表的一個存儲結點存儲線性表的一個結點的內容，即數(shù)據(jù)元素，所有存儲結點按照相應數(shù)據(jù)元素間的邏輯關系決定的次序依次排列。三叉鏈表：每個數(shù)據(jù)元素含有一個data域和三個指針域，三個指針域分別指向雙親，左孩子和有孩子的鏈式存儲結構。倒排文件：和多重表文件的關鍵字索引的結構不同，稱倒排文件中的次關鍵字索引為倒排表，倒排表中次關鍵字的一項存放記錄的物理記錄號，同一關鍵字的記錄號有序排列。直接選擇排序：首先在所有記錄中選出鍵值最小的記錄，把它與第一個記錄交換，然后在其余的記錄中再選出鍵值最小的記錄與第二個記錄交換，直至所有記錄排序完成。最壞情況時間復雜度：以算法再所有輸入下的計算量的最大值作為算法的計算量。靜態(tài)雙親鏈表：由一個一維數(shù)組組成，數(shù)組的每個分量包含兩個域：數(shù)據(jù)域和雙親域。數(shù)據(jù)域用于存儲數(shù)據(jù)元素，雙親域用于存放本結點的雙親結點再數(shù)組中的序號。哈夫曼樹：給定一組值：p1,…pk,構造一棵有k個葉子且非別以這些值為權的判定樹,使得其平均比較次數(shù)最小散列查找：對于給定的動態(tài)查找表T,如果選定了某個理想的散列函數(shù)H及相應的散列表L,則對于T中的每個數(shù)據(jù)元素X,函數(shù)值H(X.Key)就是X在散列表中的存儲位置.ISAM文件：ISAM文件由多級主索引，柱面索引，磁道索引和主文件組成。文件的記錄在同一盤上存放時，應盡量先放在一個柱面上，然后再順序存放在相鄰的柱面上，對于同一柱面，則應按盤面的次序順序存放。存儲密度：存儲結點中數(shù)據(jù)域占用的存儲量與整個存儲結點占用存儲量之比。順序隊假溢出：在順序隊的存儲過程中，發(fā)現(xiàn)在數(shù)組高端不能入隊，但是數(shù)組的低端仍有空閑位置，即順序隊的存儲空間沒有被占滿。結點的度：結點擁有的子樹的樹木。二次探測法：生成的后繼散列地址不是連續(xù)的，而是跳躍式的，以便為后續(xù)數(shù)據(jù)元素留下空間而減少堆積。B+樹：m階B+樹滿足以下條件每個結點至多有m個孩子。根結點至少有2個孩子，其余每個結點至少有[m/2]個孩子。所有葉子都在同一層上有k個孩子的結點必有k個關鍵字。判定樹：用于描述分類過程的二叉樹稱為判定樹，判定樹的每個非終端結點包含一個條件，因而對應于一次比較或判斷，每個終端結點包含一個種類標記，對應于一種分類結果。樹的深度：一棵樹中所有結點層數(shù)的最大值。公共溢出區(qū)法：在構造后繼散列地址序列的過程中，散列表由兩個一維數(shù)組組成，一個是基本表，就是閉散列表，另一個稱為溢出表，插入首先在基本表上進行，假如發(fā)生沖突，則將同義詞存入溢出表。索引順序文件：由索引表和主文件組成，索引表指一張指示邏輯記錄和物理記錄之間對應關系的表。索引項按照關鍵字值順序排列，文件本身也是按照關鍵字順序排列。多重表文件：記錄按主關鍵字的順序構成一個串聯(lián)文件，并建立主關鍵字的索引，對每個次關鍵字建立此關鍵字索引，所有具有同一次關鍵字的記錄構成一個鏈表。單鏈表：單鏈表的一個存儲結點包含兩個部分：data域稱為數(shù)據(jù)域，next稱為指針域，存放一個指針，指向本結點所含數(shù)據(jù)元素的直接后繼所在的結點。稀疏矩陣：矩陣中零元素遠遠多于非零元素，并且非零元素的分布沒有規(guī)律的矩陣。靜態(tài)查找表：以集合為邏輯結構，包含建表，查找，讀表元三種基本運算的數(shù)據(jù)結構。索引順序表：索引順序表由兩部分組成：一個順序表和一個索引表，順序表組織形式和普通的順序表相同，而索引表本身在組織形式上也是一個順序表。先根遍歷：若需遍歷的二叉樹為空，執(zhí)行空操作，否則，依次執(zhí)行以下操作：訪問根結點先根遍歷左子樹先根遍歷右子樹四、算法閱讀題：1.閱讀下面的鏈棧的退棧操作，棧頂元素通過參數(shù)返回，它的直接后繼成為新的棧頂，請在空缺處填入合適的內容，使其成為一個完整的算法。intPop(LStackTp*ls,DataType*x){LStackTp*p;if(ls!=NULL){p=ls;（1）_______________（2）_______________free(p);/*釋放原棧頂結點空間*/return（1）;}elsereturn（0）;}（1）_______________（2）_______________（1）*x=p->data;（2）ls=ls->next;2.閱讀下面算法，回答問題：voidfun1(intn,listr){for(i=1;i=n-1;i++){flag=1;for(j=1;j=n－i;j++)if(r[j+1].key<r[j].key){flag=0;p=r[j];r[j]=r[j+1];r[j+1]=p;}if(flag)return;}｝說明算法fun1（）的功能。該算法的時間復雜度。（1）冒泡排序（2）O（n2）3閱讀下面算法，回答問題：Intvisited[vnum];Count_Component(GraphTpg){intcount;for(v=0;v<g.vexnum;v++)/*初始化visited數(shù)組*/visited[v]=0;count=0;for(v=0;v<g.vexnum;v++)if(!visited=[v]){count++;printf("連通分量%d包含以下頂點：",count);Dfs(g,v);Printf("\n");}}如果用上面算法遍歷如下圖，看到輸出結果為：連通分量1包含以下頂點：12354連通分量2包含以下頂點：6784.閱讀下面算法，回答問題：voidfun1(SeqStack*S){inti;arr[100];n=0;while(StackEmpty(S))arr[n++]=Pop(S);for(i=0,i<n;i++)Push(S,arr[i]);}（1）簡述fun1（）的功能（2）如果S的入棧順序為{A,B,C,D}，請畫出最終S棧內存儲情況。（1）程序段的功能是將一棧中的元素按反序重新排列，也就是原來在棧頂?shù)脑胤诺綏５祝瑮５椎脑胤诺綏ｍ?。此棧中元素個數(shù)限制在100個以內。（2）5.閱讀下面的鏈隊的出隊列算法，出隊元素由參數(shù)返回，請在空缺處填入合適的內容，使其成為一個完整的算法。OutQueue(QueptrTp*lq,DataType*x){LqueueTp*s;if(lq->front==lq->rear){error("隊空");return（0）;}else{（1）______________（2）______________（3）______________if(s->next==NULL)lq->rear=lq->front;free(s);return（1）;}}（1）______________（2）______________（3）______________（1）s=(lq->front)->next;（2）*x=s->data;（3）(lq->front)->next=s->next;6.已知下面算法，回答以下問題intcount=0;voidfun1(bitreptrt){if(t!=NULL){if((t->lchild==NULL)&&(t->rchild==NULL))count++;fun1(t->lchild,count);fun1(t->rchild,count);}}簡述fun1（）的功能如果程序遍歷的二叉樹如下，寫出最終count的結果（1）求二叉樹的葉子數(shù)目（2）37.閱讀下列算法并回答問題：voidfun3(listr);{for(i=2;i=n;i++){r[0]=r[i];j=i-1;while(r[0].key<r[j].key){r[j+1]=r[j];j――;}r[j+1]=r[0];}}簡述fun3（）的功能在程序中r[0]的功能（1）直接插入排序（2）a．在進入循環(huán)之前，存儲r[i]的值b．在while循環(huán)中監(jiān)視j是否越界（哨兵，監(jiān)視哨）8.閱讀下面算法，回答以下問題intfun1(StackS){intn=0;while(!StackEmpty(S)){n++;Pop(S);}return(n）;}如果現(xiàn)在{7,2,3,23,56,9}6個元素依次入棧，算法返回值是多少？簡述fun1（）的功能。（1）6（2）計算棧中的數(shù)的個數(shù)9.閱讀下面的二分法查找的算法，請在空缺處填入合適的內容，使其成為一個完整的算法。intbinsearch(sqtableR,keytypeK){low=1;hig=R.n;while(low<=hig){（1）______________switch{caseK==R.item[mid].key:return(mid);caseK<R.item[mid].key:（2）______________；break;caseK>R.item[mid].key:（3）______________；break;}}return(0);}（1）______________（2）______________（3）______________（1）mid=(low+hig)/2;（2）hig=mid-1;（3）low=mid+1；10.有向圖的鄰接表類型定義如下，閱讀下面算法，要求回答下面問題：#definevnum5typedefstructarcnode{intadjvex;structarcnode*nexttarc;}ArcNodeTp;typedefstructvexnode{intvertex;ArcNodeTp*firstarc;}AdjList[vnum];typedefstructgraph{AdjListadjlist;intvexnum,arcnum;}Graphtp;voidIndegree(AdjListg){for(i=0;i<n;j++){num=0;for(j=0;j<n;j++)if(i!=j){p=g[j].firstarc;while(p){if(p->adjvex==i)num++;p=p->next;}}printf(“頂點%d：%d\n”,g[i].vexdata,num);}}已知有向圖如下，該算法的輸出結果為：該算法的功能。（1）頂點1：2頂點2：1頂點3：1頂點4：1頂點5：1（2）求5個頂點有向圖每個頂點的入度.11.閱讀下面的單鏈表第i位置上插入一個以x為值的新結點的算法，請在空缺處填入合適的內容，使其成為一個完整的算法。voidins_lklist(lklisthead,inti){p=find_lklist(head,i-1);if(p==NULL)error('不存在第i個位置');else{s=malloc(size);s->data=x;（1）_______________。（2）_______________。}（1）_______________。（2）_______________。（1）s->next=p->next;（2）p->next=s;12.下面是在順序棧上實現(xiàn)的一個?；静僮?，該操作的功能是_________。typedefstruct{DataTypedata[100]；inttop；}SeqStack；DataTypefun1(SeqStack*S){if(StackEmpty(S))Error(”Stackisempty”)；return（S->data[S->top]）；}取棧頂元素（5分）13.閱讀下面算法，回答問題。intfun2(MGraph*G,inti){intd=0,j;for(j=0;j<n;j++){if(G->edges[i][j])d++;if(G->edges[j][i])d++;}return

(d);}(1)簡述函數(shù)fun2（）的功能;(2)寫出函數(shù)fun2（）的時間復雜度。（1）計算鄰接矩陣中第i結點的入度和出度之和（2）O（n）14.閱讀下面算法，回答問題：LinkListfun1(LinkListL)/*L是無頭結點單鏈表*/

{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;

}

returnL;

}簡述fun1（）的功能如果L的初始狀況如下，請畫出最終L的狀態(tài)（1）該算法的功能是：將開始結點摘下鏈接到終端結點之后成為新的終端結點，而原來的第二個結點成為新的開始結點，返回新鏈表的頭指針。（2）15.閱讀下面算法，算法功能為往無向圖的鄰接矩陣中插入頂點，解釋（1）（2）兩句語句功能voidAddVertexMGraph(MGraph*G,VertexTypex){if(G->n>=MaxVertexNum)Error("頂點數(shù)太多")；G->vexs[G->n]=x;（1）G->n++；（2）}（1）______________（2）______________（1）將新頂點輸入頂點表（2）頂點數(shù)加116.閱讀下面程序，回答問題：for(i=1;i<＝n;i++) for(j=1;j<＝i;j++) t=t+1;該程序段的時間復雜性量度是多少？（要求寫出運算步驟）計算頻度最大的語句為t=t+1，計算總的次數(shù)為1＋2＋3＋…+n=n*(n+1)/2所以時間復雜度為O(n2)17.閱讀下面算法借助棧將一個帶頭結點的單鏈表倒置，請在空缺處填入合適的內容，使其成為一個完整的算法。voidreverse_list(LkListTp*head){LStackTpls,p;datatypex;InitStack(&ls);/*初始化鏈棧*/p=(*head)->next;while(p!=NULL){Push(&ls,p->data);p=p->next;}（1）_____________while(!EmptyStack(ls)){Pop(&ls,&x);（2）_____________（3）_____________}（1）_____________（2）_____________（3）_____________（1）p=(*head)->next;（2）p->data=x;（3）p=p->next;18.閱讀下面算法，算法功能為向無向圖的鄰接表中插入一個頂點，解釋（1）（2）（3）的語句功能voidAddVertexALGraPh(ALGrahp*G,VertexTypex){if(G->n>=MaxVertexNum)Error("頂點數(shù)太多")；G->adjlist[G->n].vertex=x;（1）G->adjlist[G->n].firstedge=NULL;（2）G->n++；（3）}（1）_____________（2）_____________（3）_____________（1）將新頂點輸入頂點表（2）邊表置為空表（3）頂點數(shù)加119.for(i=1；i<=n；i++){s=i+2;

for(j=1；j<=n；j++)

s=2*j；}該程序段的時間復雜度為多少？（寫出運算步驟）賦值為頻度最高語句，執(zhí)行次數(shù)為n*n次所以時間復雜度為O（n2）20.閱讀下面算法，要求回答下面問題：typedefstrutcycqueue{DataTypedata[maxsize];intrear,front;}CycqueueTp;CycqueueTpsq;intfun2(CycqueueTp*sq,DataTypex){if((sq->rear+1)%maxsize==sq->front){error("隊滿");return0;}else{sq->rear=(sq->rear+1)%maxsize;sq->data[sq->rear]=x;return1;}}intfun3(CycqueueTp*sq,DataType*x){if((sq->front==sq->rear){error("隊空");return0;}else{sq->front=(sq->front+1)%maxsize;*x=sq->data[sq->front];return1;}}intfun4(cycqueueTpsq,DataType*x){if(sq.rear==sq.front)return0;else{*x=sq.data[(sq.front+1)%maxsize];return1;}}（1）算法fun2（）的功能。（2）算法fun3（）的功能。（3）算法fun4（）的功能。（1）循環(huán)隊元素入隊（2）循環(huán)隊元素出隊（3）循環(huán)隊元素取隊頭元素21.閱讀下面廣度優(yōu)先搜索算法，請在空缺處填入合適的內容，使其成為一個完整的算法。Bfs(GraphTpg,intv){QueptrTpQ;ArcNodeTp*p;InitQueue(&Q);Printf("%d",v);Visited[v]=1;EnQueue(&Q,v);Whi