(電大復(fù)習(xí))數(shù)據(jù)結(jié)構(gòu)（本）期末綜合練習(xí)13c

1 數(shù)據(jù)結(jié)構(gòu)（本）期末綜合練習(xí) 期末綜合練習(xí)一 一、單項選擇題 1 數(shù)據(jù)的物理結(jié)構(gòu)（ D ）。 A與數(shù)據(jù)的邏輯結(jié)構(gòu)無關(guān) B僅僅包括數(shù)據(jù)元素的表示 C只包括數(shù)據(jù)元素間關(guān)系的表示 D包括數(shù)據(jù)元素的表示和關(guān)系的表示 2數(shù)據(jù)元素是數(shù)據(jù)的基本單位，它（ C ）。 A只能有一個數(shù)據(jù)項組成 B至少有二個數(shù)據(jù)項組成 C可以是一個數(shù)據(jù)項也可以由若干個數(shù)據(jù)項組成 D至少有一個數(shù)據(jù)項為指針類型 3從 n 個數(shù)中選取最大元素 ， （ C ）。 A基本操作是數(shù)據(jù)元素間的交換 B算法的時間復(fù)雜度是 O(n2) C算法的時間復(fù)雜度是 O(n) D需要進行 (n+1)次數(shù)據(jù)元素間的比較 4線性表的順序結(jié)構(gòu)中，（ C ）。 A邏輯上相鄰的元素在物理位置上不一定相鄰 B數(shù)據(jù)元素是不能隨機訪問的 C邏輯上相鄰的元素在物理位置上也相鄰 D進行數(shù)據(jù)元素的插入、刪除效率較高 5以下表中可以隨機訪問的是（ D ）。 A單向鏈表 B雙向鏈表 C單向循環(huán)鏈表 D順序表 6帶頭結(jié)點的單向鏈表為空的判斷條件是（ B ）（設(shè)頭指針為 head）。 A head = =NULL B head-next= =NULL C head-next= =head D head!=NULL 7 .設(shè)順序存儲的線性表長度為 n，對于刪除操作，設(shè)刪除位置是等概率的，則刪除一個元素平均移動元素的次數(shù)為（ A ）。 A (n+1)/2 B n C 2n D n-i 8線性結(jié)構(gòu)中數(shù)據(jù)元素的位置之間存在（ A ）的關(guān)系。 A一對一 B一對多 C多對多 D每一個元素都有一個直接前驅(qū)和一個直接后繼 9 設(shè) top 是一個鏈棧的棧頂指針，棧中每個結(jié)點由一個數(shù)據(jù)域 data 和指針域 next 組成，設(shè)用 x接收棧頂元素，則出棧操作為 （ A ）。 A x=top-data；top=top-next； B top=top-next；x=top-data； C x=top- next；top=top- data； D top-next =top； x=top-data； 10設(shè)順序存儲的線性表長度為 n，要刪除第 i 個元素，按課本的算法，當 i=（ C ）時，移動元素的次數(shù)為 3 A 3 B n/2 C n-3 D 4 11以下說法正確的是（ C ）。 A隊列是后進先出 B棧的特點是后進后出 C棧的刪除和插入操作都只能在棧頂進行 D隊列的刪除和插入操作都只能在 隊頭進行 12 .以下說法不正確的是（ C ）。 A棧的特點是后進先出 B隊列的特點是先進先出 C棧的刪除操作在棧底進行，插入操作在棧頂進行 D隊列的插入操作在隊尾進行，刪除操作在隊頭進行 13串函數(shù) StrCmp(“abA”,”aba”)的值為（ D ）。 A 1 B 0 C“ abAaba” D -1 14 一個棧的進棧序列是 a， b， c， d，則棧的不可能的出棧序列是 （ A ）。 2 a b e c d h g f A adbc B bcad C cbad D dcba 15設(shè)有一個 12 階的對稱矩陣 A，采用壓縮存儲方式將其下三角部分以行序為主序存儲到一維數(shù)組 b 中（矩陣 A 的第一個元素為 a1,1，數(shù)組 b 的下標從 1 開始），則矩陣 A 中第 4 行的元素在數(shù)組 b 中的下標 i 一定有（ A ）。 A 7 i 10 B 11 i 15 C 9 i 14 D 6 i 9 16已知一個圖的邊數(shù)為 m，則該圖的所有頂點的度數(shù)之和為（ A ）。 A 2m B m C 2m+1 D m/2 17設(shè)有一個帶頭結(jié)點的鏈隊列， 隊列中每個結(jié)點由一個數(shù)據(jù)域 data 和指針域 next 組成， front 和 rear 分別為鏈隊列的頭指針和尾指針，要執(zhí)行出隊操作，用 x保存出隊元素的值， p 為指向結(jié)點類型的指針，可執(zhí)行如下操作： p=front-next；x=p-data； 然后執(zhí)行 （ B ）。 A front=p-next； B front-next=p-next； C front=p； D front-next =p； 18以下說法不正確的是（ D ）。 A連通圖 G 一定存在生成樹 B連通圖 G 的生成樹中一定包含 G 的所有頂點 C連通圖 G 的生成樹中不一定包含 G 的所有邊 D連通圖 G 的生成樹可以是不連通的 19散列查找的原理是（ A ）。 A在待查記錄的關(guān)鍵字值與該記錄的存儲位置之間建立確定的對應(yīng)關(guān)系 B按待查記錄的關(guān)鍵字有序的順序方式存儲 C按關(guān)鍵字值的比較進行查找 D基于二分查找的方法 20空串的長度為（ A ）。 A 0 B 1 C 2 D 3 21排序過程中，每一趟從無序子表中將一個待排序的記錄按其關(guān)鍵字的大小放置到已經(jīng)排好序的子序列的適當位置，直到全部排好序為止，該排序算法是 ( D )。 A 選擇排序 B快速排序 C冒泡排序 D 直接插入排序 22采用順序查找法對長度為 n 的線性表進行查找（不采用表尾設(shè)監(jiān)視哨的方法），最壞的情況下要進行（ B ）次元素間的比較。 A n+2 B n C n-1 D n/2 23設(shè)有一個 10 階的對稱矩陣 A，采用壓縮存儲方式將其下三角部分以行序為主序存儲到一維數(shù)組 b 中。（矩陣 A 的第一個元素為 a1,1，數(shù)組 b 的下標從 1 開始），則矩陣元素 a5,3對應(yīng)一維數(shù)組 b 的數(shù)組元素是（ C ）。 A b18 B b8 C b13 D b10 24如圖 1 若從頂點 a 出發(fā)按廣度優(yōu) 先搜索法進行遍歷，則可能得到的頂點序列為（ D ）。 A acebdfgh B aebcghdf C aedfbcgh D abecdfgh 圖 1 25已知如圖 2 所示的一個圖，若從頂點 a 出發(fā)，按深度優(yōu)先搜索法進行遍歷，則可能得到的一種頂點序列為（ D ）。 A abecdf B acfebd C aebcfd D aedfcb 3 圖 2 26一棵哈夫曼樹總共有 23 個結(jié)點，該樹共有（ D ）個葉結(jié)點（終端結(jié)點） 。 A 10 B 13 C 11 D 12 二、填空題 1通常數(shù)據(jù)的邏輯結(jié)構(gòu)包括集合、線性、 _樹形 _、 _ 圖狀 四種類型。 2通常可以把某城市中各公交站點間的線路圖抽象成 _圖狀 _結(jié)構(gòu)。 3設(shè)有一個單向鏈表，結(jié)點的指針域為 next，頭指針為 head， p 指向尾結(jié)點，為了使該單向鏈表改為單向循環(huán)鏈表，可用語句 _ p-next=head；_ _。 4設(shè)有一個單向循環(huán)鏈表，頭指針為 head，鏈表中結(jié)點的指針域為 next， p 指向尾結(jié)點的直接前驅(qū)結(jié)點，若要刪除尾結(jié)點，得到一個新的單向循環(huán)鏈表，可執(zhí)行操作 _ _ p-next=head 。 5循環(huán)隊列的隊頭指針為 f，隊尾指針為 r，當 _ r=f _時表明隊列已空。 6在一個鏈隊中， f 和 r 分別為隊頭和隊尾指針，隊結(jié)點的指針域為 next，則插入一個 s 所指結(jié)點的操作為 _ r-next=s _； r=s； 7設(shè)有一個鏈棧，棧頂指針為 hs，現(xiàn)有一個 s 所指向的結(jié)點要入棧，則可執(zhí)行操作 _ s-next=hs 和 hs=s； 8循環(huán)隊列的隊頭指針為 f，隊尾指針為 r，當 _ r= =f _時表明隊列為空。 9在一個鏈隊中， f 和 r 分別為隊頭和隊尾指針，隊結(jié)點的指針域為 next，則插入一個 s 所指結(jié)點的操作為 _ r-next=s _； r=s； 10“ A”在存儲時占 _2_個字節(jié)。 11串的兩種最基本的存儲方式分別 是 _順序存儲 _和 _鏈式存儲 _。 12一棵二叉樹沒有單分支結(jié)點，有 6 個葉結(jié)點，則該樹總共有 _11_個結(jié)點。 13一棵二叉樹中順序編號為 i 的結(jié)點，若它存在左、右孩子，則左、右孩子編號分別為 _2i _、 _2i+1_。 14按照二叉樹的遞歸定義，對二叉樹遍歷的常用算法有 _先序 、 _中序 _、 _后序 _三種。 15 兩個串相等的充分必要條件是 串長度相等且對應(yīng)位置的字符相等 。 16把數(shù)據(jù)存儲到計算機中 ,并具體體現(xiàn)數(shù)據(jù)之間的邏輯結(jié)構(gòu)稱為 _物理（存儲） _結(jié)構(gòu)。 17一棵二叉 樹葉結(jié)點（終端結(jié)點）數(shù)為 5，單分支結(jié)點數(shù)為 2，該樹共有 _11_個結(jié)點。 18如圖 3 所示的二叉樹，其后序遍歷序列為 gdbeihfca 。 圖 3 b d f e c a e f g i b a c h d 4 a b c e d 40 28 72 3 100 54 6 19根據(jù)搜索方法的不同，圖的遍歷有 _深度優(yōu)先搜索遍歷 _、 _廣度優(yōu)先搜索遍歷 方法。 20二叉樹為二叉排序的充分必要條件是其任一結(jié)點的值均大于其左孩子的值、小于其右孩子的值。這種說法是 _錯誤 _的。 (回答正確或不正確 ) 21一個有 序表 3， 4， 10， 14， 34， 43， 46， 64， 75， 78， 90， 96， 130用折半查找法查找值為 90 的結(jié)點，經(jīng) _4_次比較后查找成功。 三、綜合題 1（ 1）已知某二叉樹的后序遍歷序列是 debca，中序遍歷序列是 dbeac，試畫出該二叉樹 （ 2）若上述二叉樹的各個結(jié)點的字符分別代表不同的整數(shù)（其中沒有相等的），并恰好使該樹成為一棵二叉排序樹，試給出 a、 b、c、 d、 e 的大小關(guān)系。 答： dbeac （ 3）給出該樹的前序遍歷序列 答： abdec 2（ 1）一組記錄的關(guān)鍵字序列為 45， 40， 65， 43， 35， 95，寫出利用快速排序的方法，以第一個記錄為基準得到的一趟劃分的結(jié)果（要求給出一趟劃分中每次掃描和交換的 結(jié)果） 答： 45 40 65 43 35 95 35 40 65 43 35 95 35 40 65 43 65 95 35 40 43 43 65 95 35 40 43 45 65 95 （ 2）對序列 45， 40， 65， 43， 35， 95利用直接插入排序，寫出逐次插入過程（從第一個元素一直到第六個元素）。 答 40 45 65 43 35 95 40 43 45 65 35 95 35 40 43 45 65 95 3（ 1）設(shè)有一個整數(shù)序列 40， 28， 6， 72， 100， 3， 54依次取出序列中的數(shù)，構(gòu)造一棵二叉排序樹 （ 2）對上述二叉排序樹，在等概率條件下，求成功查找的平均查找長度 答： ASL=（ 1x1+2x2+3x3+4） /7=18/7 4 (1) 設(shè)有查找表 5,14,2,6,18,7,4,16,3,依次取表中數(shù)據(jù)，構(gòu)造一棵二叉排序樹 . 5 42 82 67 52 57 32 16 102 16 42 32 52 57 67 82 102 （ 2）說明如何通過序列的二 叉排序樹得到相應(yīng)序列的排序結(jié)果。 答：中序遍歷 5（ 1）利用篩選過程把序列 42， 82， 67， 102， 16， 32， 57， 52建成堆（小根堆），畫出相應(yīng)的完全二叉樹（不要求中間過程） （ 2）寫出對上述堆對應(yīng)的完全二叉樹進行中序遍歷得到的序列 答： 102， 52， 42， 82， 16， 67， 32， 57 四、 程序填空題 1以下函數(shù)在 a0到 an-1中，用折半查找算法查找關(guān)鍵字等于 k的記錄，查找成功返回該記錄的下標，失敗時返回 -1，完成程序中的空格 typedef struct int key； NODE； int Binary_Search(NODE a,int n, int k) int low,mid,high； low=0； high=n-1； while(_low=high _) mid=(low+high)/2； if(amid.key=k) return _ mid _； else if(_amid.keydata=x； _ p-next=top _； _ top=p _； 3以下函數(shù)為鏈隊列的入隊操作， x為要入隊的結(jié)點的數(shù)據(jù)域的值， front、 rear 分別是鏈隊列的隊頭、隊尾指針 struct node ElemType data； struct node *next； ； struct node *front， *rear； void InQueue(ElemType x) struct node *p； p= (struct node*) _ malloc(sizeof (struct node)_； p-data=x； p-next=NULL； _ rear-next=p _； rear= _ p _； 期末綜合練習(xí)二 一、單項選擇題 1（ B ）是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的子集。 A數(shù)據(jù)元素 B數(shù)據(jù)對象 C數(shù)據(jù)結(jié)構(gòu) D數(shù) 據(jù)項 2 同一種邏輯結(jié)構(gòu)（ B ）。 A只能有唯一的存儲結(jié)構(gòu) B可以有不同的存儲結(jié)構(gòu) C只能表示某一種數(shù)據(jù)元素之間的關(guān)系 D以上三種說法均不正確 3設(shè)鏈表中的結(jié)點是 NODE 類型的結(jié)構(gòu)體變量，且有 NODE *p；為了申請一個新結(jié)點，并由 p 指向該結(jié)點，可用以下語句（ A ）。 A p=(NODE *)malloc(sizeof(NODE)； 7 B p=(*NODE)malloc(sizeof(NODE)； C p=(NODE )malloc(sizeof(p)； D p=(NODE *)malloc(sizeof(p)； 4鏈表所具備的特點是（ C ）。 A可以隨機訪問任一結(jié)點 B占用連續(xù)的存儲空間 C插入刪除元素的操作不需要移動元素結(jié)點 D可以通過下標對鏈表進行直接訪問 5設(shè)順序存儲的線性長度為 n，要在第 i 個元素之前插入一個新元素，按課本的算法當 i= （ D ）時，移動元素次數(shù)為 2 A n/2 B n C 1 D n-1 6數(shù)據(jù)的物理結(jié)構(gòu)（ D ）。 A與數(shù)據(jù)的邏輯結(jié)構(gòu)無關(guān) B僅僅包括數(shù)據(jù)元素的表示 C只包括數(shù)據(jù)元素間關(guān)系的表示 D包括數(shù)據(jù)元素的表示和關(guān)系的表示 7 一個棧的進棧序列是 1， 2， 3， 4，則棧的不可能的出棧序列是 （ B ）（進出棧操作可以交替進行） A 3， 2， 4， 1 B 1， 4， 2， 3 C 4， 3， 2， 1 D 3， 2， 1， 4 8線性結(jié)構(gòu)中數(shù)據(jù)元素的位置之間存在（ A ）的關(guān)系。 A一對一 B一對多 C多對多 D每一個元素都有一個直接前驅(qū)和一個直接后繼 9設(shè)有一個帶頭結(jié)點的鏈隊列， 隊列中每個結(jié)點由一個數(shù)據(jù)域 data 和指針域 next 組成， front 和 rear 分別為鏈隊列的頭指針和尾指針。設(shè) p 指向要入隊的新結(jié)點 (該結(jié)點已被賦值 )，則入隊操作為 （ A ）。 A rear-next=p；rear=p； B rear-next=p； p = rear； C p = rear-next；rear=p； D rear=p；rear-next=p； 10以下表中可以隨機訪問的是（ D ）。 A單向鏈表 B雙向鏈表 C單向循環(huán)鏈表 D順序表 11以下說法不正確的是（ C ）。 A順序棧中，棧滿時再進行進棧操作稱為“上溢” B順序棧中，?？諘r再作出棧棧操作稱為“下溢” C順序隊列中，當尾指針已經(jīng)超越隊列存儲空間的上界，則一定是隊列已滿 D順序隊列中，隊列的頭指針和尾指針均超越隊列存儲空間的上界，則隊列 已空 12算法的時間復(fù)雜度與（ C ）有關(guān)。 A所使用的計算機 B與計算機的操作系統(tǒng) C與算法本身 D與數(shù)據(jù)結(jié)構(gòu) 13設(shè)有一個 20 階的對稱矩陣 A，采用壓縮存儲方式，將其下三角部分以行序為主序存儲到一維數(shù)組中（矩陣 A 的第一個元素為 a11，數(shù)組 b 的下標從 1 開始），則矩陣元素 a8,5在一維數(shù)組 b 中的下標是（ D ）。 A 30 B 28 C 40 D 33 14設(shè)有一個長度 為 n 的順序表，要刪除第 i個元素需移動元素的個數(shù)為（ B ）。 A n-i+1 B n-i C n-i-1 D i 15深度為 5 的完全二叉樹第 5 層上有 4 個結(jié)點，該樹一共有（ D ）個結(jié)點。 A 28 B 30 C 31 D 19 16在一個單鏈表中， p、 q 分別指向表中兩個相鄰的結(jié)點，且 q 所指結(jié)點是 p 所指結(jié)點的直接后繼，現(xiàn)要刪除 q 所指結(jié)點，可用的語句是（ C ）。 A p=q-next B p-next=q C p-next=qnext D q-next=NULL 17已知一個圖的所有頂點的度數(shù)之和為 m，則 m 一定不可能是（ D ）。 A 4 B 8 C 12 D 9 18從一個棧頂指針為 top的鏈棧中刪除一個結(jié)點時，用變量 x 保存被刪結(jié)點的值，則執(zhí)行（ A ）。 A x=top-data； top=top-next； B x=top-data； C top=top-next； x=top-data； D top=top-next； x=data； 19以下說法正確的是（ D ）。 8 a b e c d f A連通圖 G 的生成樹中可以包含回路 B連通圖 G 的生成樹可以是不連通的 C連通圖 G 的生成樹一定是唯一的 D連通圖 G 的生成樹一定是連通而不包含回路的 20在一個鏈隊中，假設(shè) f 和 r 分別為隊頭和隊尾指針，則刪除一個結(jié)點的運算為（ C ）。 A r=f-next； B r=r-next； C f=f-next； D f=r-next； 21 對 n 個元素進行冒泡排序，通常要進行 n-1 趟冒泡，在第 j 趟冒泡中共要進行（ C ）次元素間的比較。 A j B j-1 C n-j D n-j-1 22一個棧的進棧序列是 a， b， c， d， e，則棧的不可能輸出序列是（ A ）（進棧出?？梢越惶孢M行）。 A dceab B edcba C decba D abcde 23在排序過程中，可以 有效地減少一趟排序過程中元素間的比較次數(shù)的算法是（ D ）。 A冒泡 B選擇 C直接插入 D折半插入 24 有一個長度為 10 的有序表，按折半查找對該表進行查找，在等概率情況下查找成功的平均比較次數(shù)為（ B ）。 A 26/10 B 29/10 C 29/9 D 31/10 25如圖 1 若從頂點 a 出發(fā)按深度優(yōu)先搜索法進行遍歷，則可能得到的頂點 序列為（ B ）。 A aebcfd B abedcf C acebdf D acfbde 圖 1 26 排序算法中，從未排序序列中依次取出元素與已排序序列（初始為空）中的元素進行比較（要求比較次數(shù)盡量少），然后將其 放入已排序序列的正確位置的方法是（ C ）。 A冒泡 B直接插入 C折半插入 D選擇排序 27一棵哈夫曼樹有 n 個葉子結(jié)點（終端結(jié)點），該樹總共有（ B ）個結(jié)點。 A 2n-2 B 2n-1 C 2n D 2n+2 28設(shè)有一個 10 階的對稱矩陣 A，采用壓縮存儲的方式，將其下三角部分以行序為主存儲到一維數(shù)組 B 中（數(shù)組下標從 1 開始），則矩陣中元素 A8,5在一維數(shù)組 B中的下標是（ A ）。 A 33 B 32 C 85 D 41 29 數(shù)據(jù)的 （ A ）結(jié)構(gòu)與所使用的計算機無關(guān)。 A邏輯 B物理 C存儲 D邏輯與存儲 30在一個無向圖中，所有頂點的度數(shù)之和等于邊數(shù)的（ D ）倍。 A 3 B 2.5 C 1.5 D 2 二、填空題 1通?？梢园岩槐竞胁煌鹿?jié)的書的目錄結(jié) 構(gòu)抽象成 _樹形 _結(jié)構(gòu)。 2棧和隊列的操作特點分別是 _先進后出 _和 _先進先出 _。 3要在一個單向鏈表中 p 所指向的結(jié)點之后插入一個 s 所指向的新結(jié)點，若鏈表中結(jié)點的指針域為 next，可執(zhí)行 _ s-next= p-next；_和 p-next=s；的操作。 4結(jié)構(gòu)中的數(shù)據(jù)元素存在多對多的關(guān)系稱為 _圖狀 （網(wǎng)狀） _結(jié)構(gòu)。 5設(shè)有一個非空的鏈棧，棧頂指針為 hs，要進行出棧操作，用 x保存出棧結(jié)點的值，棧結(jié)點的指針域為 next，則可執(zhí)行 x=hs-data； _ hs=hs-next；_ _。 6根據(jù)數(shù)據(jù)元素間關(guān)系的不同特性，通?？煞譃?集合、線性、 樹形 、 圖狀 四類基本結(jié)構(gòu)。 7在一個不帶頭結(jié)點的非空鏈隊中， f 和 r 分別為隊頭和隊尾指針，隊結(jié)點的數(shù)據(jù)域為 data，指針域為 next，若要進行出隊操作，并用變量 x存放出隊元素的數(shù)據(jù)值，則相關(guān)操作為 x=f-data； _ f=f-next；_ _。 9 8要求在 n 個數(shù)據(jù)元素中找其中值最大的元素，設(shè)基本操作為元素間的比較。則比較的次數(shù)和算法的時間復(fù)雜 度分別為 _和 _ n-1,O(n)_ 。 9循環(huán)隊列的最大存儲空間為 MaxSize=8，采用少用一個元素空間以有效的判斷?？栈驐M，若隊頭指針 front=4，則當隊尾指針 rear= _ 4 _時，隊列為空，當 rear= _ 2 _時，隊列有 6 個元素。 10 稀疏矩陣存儲時 ， 采用一個由 _行號 _ 、 _列號 _ 、 _非零元 _3 部分信息組成的三元組唯一確定矩陣中的一個非零元素。 11在二叉樹的鏈式存儲結(jié)構(gòu)中，通常每個結(jié)點中設(shè)置三個 域，它們是值域 左指針 、 右指針 。 12一棵二叉樹順序編號為 6 的結(jié)點（樹中各結(jié)點的編號與等深度的完全二叉中對應(yīng)位置上結(jié)點的編號相同），若它存在右孩子，則右孩子的編號為 _13_。 13向一個棧頂指針為 h 的鏈棧中插入一個 s 所指結(jié)點時，可執(zhí)行 s-next=h；和 _ h=s _。 14在一個鏈隊中，設(shè) f 和 r 分別為隊頭和隊尾指針，則插入 s 所指結(jié)點的操作為 _ r-next=s _和 r=s； (結(jié)點的指針域為 next) 15如圖 2 所示的二叉樹，其前序遍歷序列為 _ abdefcg _。 圖 2 16設(shè)有一棵深度為 4 的完全二叉樹，第四層上有 5 個結(jié)點，該樹共有 _12_個結(jié)點。（根所在結(jié)點為第 1 層） 17在隊列的順序存儲結(jié)構(gòu)中，當插入一個新的隊列元素時， 尾 指針的值增 1，當刪除一個元素隊列時， 頭 指針的值增 1。 18對稀疏矩陣進行壓縮存儲，矩陣中每個非零元素對應(yīng)的三元組包括該元素的 _行下標 _、 _列下標 _和 _非零元素值 _三項信息。 19循環(huán)隊列的引入，目的是為了克服 假上溢 。 20在對一組記錄 (55,39,97,22,16,73,65,47,88)進行直接插入排序時，當把第 7 個記錄 65 插入到有序表時，為尋找插入位置需比較_3_次。 三、綜合題 1（ 1）設(shè) head1和 p1分別是不帶頭結(jié)點的單向鏈表 A 的頭指針和尾指針， head2和 p2分別是不帶頭結(jié)點的單向鏈表 B 的頭指針和尾指針，若要把 B 鏈表接到 A 鏈表之后，得到一個以 head1 為頭指針的單向循環(huán)鏈表，寫出其中兩個關(guān) 鍵的賦值語句（不用完整程序，結(jié)點的鏈域為 next）。 答： p1-next= head2； p2-next= head1； （ 2）單向鏈表的鏈域為 next，設(shè)指針 p 指向單向鏈表中的某個結(jié)點，指針 s 指向一個要插入鏈表的新結(jié)點，現(xiàn)要把 s 所指結(jié)點插入 p所指結(jié)點之后，某學(xué)生采用以下語句： p-next=s； s-next=p-next； 這樣做正確嗎？若正確則回答正確，若不正確則說明應(yīng)如何改寫 答： 不對， s-next= p-next； p-next=s； 2 (1)以 2， 3， 4， 7， 8， 9 作為葉結(jié)點的權(quán)，構(gòu)造一棵哈夫曼樹 ( 要求每個結(jié)點的左子樹根結(jié)點的權(quán)小于等于右子樹根結(jié)點的權(quán) )，給出相應(yīng)權(quán)重值葉結(jié)點的哈夫曼編碼。 g f a b d e c 10 5 2 8 4 9 6 3 10 7 1 (1) 2： 1110 3: 1111 4： 110 7： 00 8： 01 9： 10 (2) 一棵哈夫曼樹有 n 個葉結(jié)點，它一共有多少個結(jié)點？簡述理由？ 答 : 2n-1 個，因為非葉結(jié)點數(shù)比葉結(jié)點數(shù)少一個。 3（ 1）畫出對長度為 10 的有序表進行折半查找的判定樹（以序號 1， 2， 10 表示樹 結(jié)點） （ 2）對上述序列進行折半查找，求等概率條件下，成功查找的平均查找長度 答： ASL=（ 1x1+2x2+3x4+4x3） /10=29/10 4一組記錄的關(guān)鍵字序列為（ 46， 79， 56， 38， 40， 84） （ 1）利用快速排序的方法，給出以第一個記錄為基準得到的一次劃分結(jié)果（給出逐次交換元素的過程，要求以升序排列） 初始序列 46， 79， 56， 38， 40， 84 40， 79， 56， 38， 40， 84 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）對上述序列用堆排序的方法建立大根堆，要求以二叉樹逐次描述建堆過程。 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 5（ 1）利用篩選法，把序列 37， 77， 62， 97， 11， 27， 52， 47建成堆（小根堆），畫出相應(yīng)的完全二叉樹 （ 2）寫出對上述堆所對應(yīng)的二叉樹進行前序遍歷得到的序列 答： 11， 37， 47， 97， 77， 27， 62， 52 6設(shè)查找表為 (50,60,75,85,96,98,105,110,120,130) (1) 說出進行折半查找成功查找到元素 120 需要進行多少 次元素間的比較？ 3 次 (2) 為了折半查找元素 95，經(jīng)過多少次元素間的比較才能確定不能查到？ 4 次 （ 3）畫出對上述有序表進行折半查找所對應(yīng)的判定樹 (要求以數(shù)據(jù)元素作為樹結(jié)點 ) 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 75 98 130 105 85 50 11005 120 60 12 四、 程序填空題 1以下函數(shù)為直接選擇排序算法，對 a1,a2, an中的記錄進行直接選擇排序，完成程序中的空格 typedef struct int key； NODE； void selsort(NODE a,int n) int i,j,k； NODE temp； for(i=1；ileft) ； printf(“ %c” ,BT-data) ； Inorder(BT-right) ； 13 期末綜合練習(xí)三 一、單項選擇題 1深度為 5 的完全二叉樹共有 20 個結(jié)點，則第 5 層上有（ C ）個結(jié)點 (根所在結(jié)點為第一層 )。 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復(fù)制 C賦值 D連接 5數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機無關(guān)的是數(shù)據(jù)的（ D ）結(jié)構(gòu)。 A物理 B存儲 C邏輯與物理 D邏輯 6 一棵有 n 個結(jié)點采用鏈式存儲的二叉樹中，共有（ A ）個指針域為空。 A n+1 B n C n-1 D n-2 7鏈表所具備的特點是（ C ）。 A可以隨機訪問任一結(jié)點 B占用連續(xù)的存儲空間 C插入刪除不需要移動元素結(jié)點 D可以通過下標對鏈表進行直接訪問 8設(shè)一棵哈夫曼樹共有 n 個非葉結(jié)點，則該樹有（ B ）個葉結(jié)點。 A n B n+1 C n-1 D 2n 9線性表只要以（ C ）方式存儲就能進行折半查找。 A鏈接 B順序 C關(guān)鍵字有序的順序 D二叉樹 10從一個棧頂指針為 top 的鏈棧中刪除一個結(jié)點時，用變量 x保存被刪結(jié)點的值，則執(zhí)行（ A ）。 A x=top-data； top=topnext； B x=top-data； C top=top-next； x=top-data； D top=top-next； x=data； 11散列查找的原理是（ A ）。 A在待查記錄的關(guān)鍵字值與該記錄的存儲位置之間建立確定的對應(yīng)關(guān)系 B按待查記錄的關(guān)鍵字有序的順序方式存儲 C按關(guān)鍵字值的比較進行查找 D基于二分查找的方法 12一棵完全二叉樹共有 5 層，且第 5層上有六個結(jié)點，該樹共有（ C ）個結(jié)點。 A 30 B 20 C 21 D 23 13對 n 個元素進行冒泡排序若某趟冒泡中只進行了（ C ）次元素間的交換，則表明序列 已經(jīng)排好序。 A 1 B 2 C 0 D n-1 14在一個無向圖中，所有頂點的度數(shù)之和等于邊數(shù)的（ D ）倍。 A 3 B 2.5 C 1.5 D 2 15排序過程中，每一趟從無序子表中將一個待排序的記錄按其關(guān)鍵字的大小放置到已經(jīng)排好序的子序列的適當位置，直到全部排好序為止，該排序算法是 ( A )。 A直接插 入排序 B快速排序 C冒泡排序 D選擇排序 16已知如圖 1所示的一個圖，若從頂點 V1出發(fā)，按深度優(yōu)先搜索法進行遍歷，則可能得到的一種頂點序列為（ A ）。 A V1V2V4V8V5V3V6V7 B V1V2V4V5V8V3V6V7 C V1V2V4V8V3V5V6V7 D V1V3V6V7V2V4V5V8 14 a b e c d f g 圖 1 17在對一組元素（ 64， 48， 106， 33， 25， 82， 70， 55， 93）進行直接插入排序時，當進行到要把第 7 個元素 70 插入到已經(jīng)排好序的子表時，為找到插入位置，需進行（ C ）次元素間的比較（指由小到大排序）。 A 6 B 2 C 3 D 4 18 已知如圖 2 所示的一個圖， 若從頂點 a 出發(fā)，按廣度優(yōu)先搜索法進行遍歷，則可能得到的一種頂點序列為（ B ）。 A abcedf B abcefd C aebcfd D acfdeb 圖 2 19采用順序查找法對長度為 n 的線性表進行查找（不采用表尾設(shè)監(jiān)視哨的方法），最壞的情況下要進行（ B ）次元素間的比較。 A n+2 B n C n-1 D n/2 20對二叉排序樹進行（ C ）遍歷，可以使遍歷所得到的序列是有序序列。 A按層次 B后序 C中序 D前序 21如圖 3，若從頂點 a 出發(fā)按廣度優(yōu)先搜索法進行遍歷，則可能得到的頂點序列為（ B ）。 A acebdgf B abecdgf C acfedgb D abecfdg 圖 3 22在有序表 2， 4， 7， 14， 34， 43， 47， 64， 75， 80， 90， 97， 120中，用折半查找法查找值 80時，經(jīng)（ B ）次比較后查找成功。 A 4 B 2 C 3 D 5 V6 V7 V1 V2 V3 V8 V4 V5 b d f e c a 15 23元素 2， 4， 6， 8 按順序依次進棧，則該棧的不可能輸出序列是（ D ）（進棧出棧可以交替進行）。 A 8， 6， 4， 2 B 2， 4， 6， 8 C 4， 2， 8， 6 D 8， 6， 2， 4 24有一個 長度為 9的有序表，按折半查找對該表進行查找，在等概率情況下查找成功的平均比較次數(shù)為（ B ）。 A 25/10 B 25/9 C 20/9 D 17/9 25排序方法中，從未排序序列中挑選元素，并將其依次放入已排序序列（初始為空）的一端的方法，稱為（ C ）排序。 A歸并 B插入 C選擇 D快速 26排序算法中，從未排序序列中依次取出元素與已排序序列（初始為空）中的元素進行比較（要求比較次數(shù)盡量少），然 后將其放入已排序序列的正確位置的方法是（ C ）。 A冒泡 B直接插入 C折半插入 D選擇排序 27一棵哈夫曼樹總共有 23 個結(jié)點，該樹共有（ D ）個葉結(jié)點（終端結(jié)點） A 10 B 13 C 11 D 12 28一組記錄的關(guān)鍵字序列為（ 46， 79， 56， 38， 40， 84），利用快速排序，以第一個關(guān)鍵字為分割元素，經(jīng)過一次劃分后結(jié)果為（ B ）。 A 40， 38， 46， 79， 56， 84 B 40， 38， 46， 56， 79， 84 C 40， 38， 46， 84， 56， 79 D 38， 40， 46， 56， 79， 84 29 隊列的插入操作在 （ B ）進行。 A隊頭 B隊尾 C隊頭或隊尾 D在任意指定位置 二、填空題（每小題 2 分，共 24 分） 1一棵二叉樹沒有單分支結(jié)點，有 6 個葉結(jié)點，則該樹總共有 _11_個結(jié)點。 2在二叉樹的鏈式存 儲結(jié)構(gòu)中，通常每個結(jié)點中設(shè)置三個域，它們是 _值域 _、 左指針 、 右指針。 3設(shè)一棵完全二叉樹，其最高層上最右邊的葉結(jié)點的編號為奇數(shù)，該葉節(jié)點的雙親結(jié)點的編號為 10，該完全二叉樹一共有 _21_個結(jié)點。 4一棵二叉樹中順序編號為 i 的結(jié)點，若它存在左、右孩子，則左、右孩子編號分別為 _2i _、 _2i+1_。 5按照二叉樹的遞歸定義，對二叉樹遍歷的常用算法有 _先序 _ 、 _中序 _、 _后序 _三種。 6串的兩種最基本的存儲方式是 _順序存儲 _和 _鏈式存儲 _。 7數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素存在一對多的關(guān)系稱為 _樹形 _結(jié)構(gòu)。 8一棵有 2n-1 個結(jié)點的二叉樹，其每一個非葉結(jié)點的度數(shù)都為 2，則該樹共有 _N_個葉結(jié)點。 9把數(shù)據(jù)存儲到計算機中 ,并具體體現(xiàn)數(shù)據(jù)之間的邏輯結(jié)構(gòu)稱為 _物理（存儲） _結(jié)構(gòu)。 10對于一棵具有 n 個結(jié)點的二叉樹，其相應(yīng)的鏈式存儲結(jié)構(gòu)中共有 _ n+1_個指針域為空。 11結(jié)構(gòu)中的數(shù)據(jù)元素存在一對一的關(guān)系稱為 _線性 _結(jié)構(gòu)。 12 _中序 _遍歷二叉排序樹可得到一個有序序列。 13如圖 4 所示的二叉樹，其后序遍歷序列為 gdbeihfca 。 e f g i b a c h d 16 16 42 32 52 5