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

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