【文章內(nèi)容簡介】 A ）結構與所使用的計算機無關。 A．邏輯 B．物理 C．存儲 D．邏輯與存儲 30．在一個無向圖中，所有頂點的度數(shù)之和等于邊數(shù)的（ D ）倍。 A． 3 B． C． D． 2 二、填空題 1．通?？梢园岩槐竞胁煌鹿?jié)的書的目錄結 構抽象成 ___樹形 __結構。 2．棧和隊列的操作特點分別是 __先進后出 ___和 ___先進先出 __。 9 3．要在一個單向鏈表中 p 所指向的結點之后插入一個 s 所指向的新結點，若鏈表中結點的指針域為 next，可執(zhí)行 __ snext= pnext； ______和 pnext=s。的操作。 4．結構中的數(shù)據(jù)元素存在多對多的關系稱為 ____圖狀 （網(wǎng)狀） __結構。 5．設有一個非空的鏈棧，棧頂指針為 hs，要進行出棧操作，用 x 保存出棧結點的值，棧結點的指針域為 next，則可執(zhí)行 x=hsdata。 ___ hs=hsnext。___ __。 6．根據(jù)數(shù)據(jù)元素間關系的不同特性，通常可分為 集合、線性、 樹形 、 圖狀 四類基本結構。 7．在一個不帶頭結點的非空鏈隊中， f 和 r 分別為隊頭和隊尾指針，隊結點的數(shù)據(jù)域為 data，指針域為 next，若要進行出隊操作，并用變量 x 存放出隊元素的數(shù)據(jù)值，則相關操作為 x=fdata。 __ f=fnext。____ __。 8．要求在 n 個數(shù)據(jù)元素中找其中值最大的元素，設基本操作為元素間的比較。則比較的次數(shù)和算法的時間復雜 度分別為 ________和 _ n1,O(n)_______ 。 9．循環(huán)隊列的最大存儲空間為 MaxSize=8，采用少用一個元素空間以有效的判斷?？栈驐M，若隊頭指針 front=4，則當隊尾指針rear= ____ 4 ____時，隊列為空，當 rear= ___ 2 _____時，隊列有 6 個元素。 10． 稀疏矩陣存儲時 ， 采用一個由 __行號 __ 、 ___列號 _ 、 __非零元 __3 部分信息組成的三元組唯一確定矩陣中的一個非零元素。 11．在二叉樹的鏈式存儲結構中，通常每個結點中設置三個 域，它們是值域 左指針 、 右指針 。 12．一棵二叉樹順序編號為 6 的結點（樹中各結點的編號與等深度的完全二叉中對應位置上結點的編號相同），若它存在右孩子，則右孩子的編號為 ___13_____。 13．向一個棧頂指針為 h 的鏈棧中插入一個 s 所指結點時，可執(zhí)行 snext=h。和 __ h=s __。 14．在一個鏈隊中，設 f 和 r 分別為隊頭和隊尾指針，則插入 s 所指結點的操作為 __ rnext=s __和 r=s。 (結點的指針域為 next) 15．如圖 2 所示的二叉樹，其前序遍歷序列為 ___ abdefcg __。 圖 2 16．設有一棵深度為 4 的完全二叉樹，第四層上有 5 個結點，該樹共有 ___12__個結點。（根所在結點為第 1 層） 17．在隊列的順序存儲結構中，當插入一個新的隊列元素時， 尾 指針的值增 1，當刪除一個元素隊列時， 頭 指針的值增 1。 18．對稀疏矩陣進行壓縮存儲，矩陣中每個非零元素對應的三元組包括該元素的 __行下標 _、 __列下標 _和 ___非零元素值 _三項信息。 19．循環(huán)隊列的引入，目的是為了克服 假上溢 。 20．在對一組記錄 (55,39,97,22,16,73,65,47,88)進行直接插入排序時，當把第 7 個記錄 65 插入到有序表時，為尋找插入位置需比較___3______次。 三、綜合題 1．（ 1）設 head1和 p1分別是不帶頭結點的單向鏈表 A 的頭指針和尾指針， head2和 p2分別是不帶頭結點的單向鏈表 B 的頭指針和尾指針，若要把 B 鏈表接到 A 鏈表之后，得到一個以 head1 為頭指針的單向循環(huán)鏈表，寫出其中兩個關 鍵的賦值語句（不用完整程序，結點的鏈域為 next）。 答： p1next= head2； p2next= head1； （ 2）單向鏈表的鏈域為 next，設指針 p 指向單向鏈表中的某個結點，指針 s 指向一個要插入鏈表的新結點，現(xiàn)要把 s 所指結點插入 p 所指結點之后，某學生采用以下語句： g f a b d e c 10 5 2 8 4 9 6 3 10 7 1 pnext=s。 snext=pnext。 這樣做正確嗎？若正確則回答正確，若不正確則說明應如何改寫 答： 不對， snext= pnext； pnext=s； 2． (1)以 2， 3， 4， 7， 8， 9 作為葉結點的權，構造一棵哈夫曼樹 ( 要求每個結點的左子樹根結點的權小于等于右子樹根結點的權 )，給出相應權重值葉結點的哈夫曼編碼。 (1) 2： 1110 3: 1111 4： 110 7： 00 8： 01 9： 10 (2) 一棵哈夫曼樹有 n 個葉結點，它一共有多少個結點？簡述理由？ 答 : 2n1 個，因為非葉結點數(shù)比葉結點數(shù)少一個。 3．（ 1）畫出對長度為 10 的有序表進行折半查找的判定樹（以序號 1， 2，?? 10 表示樹 結點） （ 2）對上述序列進行折半查找，求等概率條件下，成功查找的平均查找長度 答： ASL=（ 1x1+2x2+3x4+4x3） /10=29/10 4．一組記錄的關鍵字序列為（ 46， 79， 56， 38， 40， 84） （ 1）利用快速排序的方法，給出以第一個記錄為基準得到的一次劃分結果（給出逐次交換元素的過程，要求以升序排列） 初始序列 46， 79， 56， 38， 40， 84 40， 79， 56， 38， 40， 84 8 9 5 9 7 2 4 3 18 15 33 11 37 77 62 47 52 27 11 97 11 37 27 47 52 62 77 97 40， 79， 56， 38， 79， 84 40， 38， 56， 38， 79， 84 40， 38， 56， 56， 79， 84 40， 38， 46， 56， 79， 84 （ 2）對上述序列用堆排序的方法建立大根堆，要求以二叉樹逐次描述建堆過程。 5．（ 1）利用篩選法，把序列 {37， 77， 62， 97， 11， 27， 52， 47}建成堆（小根堆），畫出相應的完全二叉樹 （ 2）寫出對上述堆所對應的二叉樹進行前序遍歷得到的序列 答： 11， 37， 47， 97， 77， 27， 62， 52 6．設查找表為 (50,60,75,85,96,98,105,110,120,130) (1) 說出進行折半查找成功查找到元素 120 需要進行多少 次元素間的比較？ 3 次 (2) 為了折半查找元素 95，經(jīng)過多少次元素間的比較才能確定不能查到？ 4 次 （ 3）畫出對上述有序表進行折半查找所對應的判定樹 (要求以數(shù)據(jù)元素作為樹結點 ) 56 79 38 40 84 46 84 79 38 40 46 566 56 79 38 40 46 79 38 40 84 84 56 46 初始樹 堆 96 11005 60 12 四、 程序填空題 1．以下函數(shù)為直接選擇排序算法，對 a[1],a[2],? a[n]中的記錄進行直接選擇排序，完成程序中的空格 typedef struct { int key。 ?? }NODE。 void selsort(NODE a[],int n) { int i,j,k。 NODE temp。 for(i=1。i= __ n1___。i++) { k=i。 for(j=i+1。j= ___ n ___。j++) if(a[j].keya[k].key) __ k=j _____。 if(i!=k) { temp=a[i]。 __ a[i]=a[k]___。 ___ a[k]=temp _。 } } } 2．以下是用尾插法建立帶頭結點且有 n 個結點的單向鏈表的程序，結點中的數(shù)據(jù)域從前向后依次為 1,2,3,…… ,n，完成程序中空格部分。 NODE *create(n) {NODE *head , *p, *q。 int i。 p=(NODE*)malloc(sizeof(NODE))。 head= p 。 q=p 。p?next=NULL。 /*建立頭結點 */ for(i=1。 i=n。 i++) { p= (NODE*)malloc(sizeof(NODE)) 。 p?data=i。 p?next=NULL。 q?next= p 。 q=p 。 } return(head)。 } 13 3．以下程序是中序遍歷二叉樹的遞歸算法的程序，完成程序中空格部分（樹結構中左、右指針域分別為 left 和 right，數(shù)據(jù)域 data為字符型， BT 指向根結點）。 void Inorder (struct BTreeNode *BT) { if(BT!=NULL){ Inorder(BTleft) 。 printf(“ %c” ,BTdata) 。 Inorder(BTright) 。 } } 期末綜合練習三 一、單項選擇題 1．深度為 5 的完全二叉樹共有 20 個結點，則第 5 層上有（ C ）個結點 (根所在結點為第一層 )。 A． 3 B． 8 C． 5 D． 6 2．在 C 語言中，順序存儲長度為 3 的字符串，需要占用（ A ）個字節(jié)。 A． 4 B． 3 C． 6 D． 12 3．已知一個圖的邊數(shù)為 m，則該圖的所有頂點的度數(shù)之和為（ A ）。 A． 2m B． m C． 2m+1 D． m/2 4．串函數(shù) StrCat（ a,b）的功能是進行串（ D ）。 A．比較 B．復制 C．賦值 D．連接 5．數(shù)據(jù)結構中，與所使用的計算機無關的是數(shù)據(jù)的（ D ）結構。 A．物理 B．存儲 C．邏輯與物理 D．邏輯 6．一棵有 n 個結點采用鏈式存儲的二叉樹中，共有（ A ）個指針域為空。 A． n+1 B． n C． n1 D． n2 7．鏈表所具備的特點是（ C ）。 A．可以隨機訪問任一結點 B．占用連續(xù)的存儲空間 C．插入刪除不需要移動元素結點 D．可以通過下標對鏈表進行直接訪問 8．設一棵哈夫曼樹共有 n 個非葉結點，則該樹有（ B ）個葉結點。 A． n B． n+1 C． n1 D． 2n 9．線性表只要以（ C ）方式存儲就能進行折半查找。 A．鏈接 B．順序 C．關鍵字有序的順序 D．二叉樹 10．從一個棧頂指針為 top 的鏈棧中刪除一個結點時，用變量 x保存被刪結點的值，則執(zhí)行（ A ）。 A． x=topdata。 top=top?next。 B． x=topdata。 C． top=topnext。 x=topdata。 D． top=topnext。 x=data。 11．散列查找的原理是（ A ）。 A．在待查記錄的關鍵字值與該記錄的存儲位置之間建立確定的對應關系