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