大數(shù)據(jù)結(jié)構(gòu)(本)期末綜合練習(xí)

1、實(shí)用文檔數(shù)據(jù)結(jié)構(gòu)（本）期末綜合練習(xí)綜合練習(xí)一一、單項(xiàng)選擇題1 .設(shè)有頭指針為head的帶有頭結(jié)點(diǎn)的非空單向循環(huán)鏈表，指針p指向其尾結(jié)點(diǎn)，要?jiǎng)h除頭結(jié)點(diǎn)，并使其仍為單向循環(huán)鏈表,則可利用下述語(yǔ)句 head =head->next ;（）。A . p =head; B . p=NULL; C . p->next =head; D . head=p;2 .在一個(gè)單鏈表中p指向結(jié)點(diǎn)a, q指向結(jié)點(diǎn)a的直接后繼結(jié)點(diǎn)b,要?jiǎng)h除結(jié)點(diǎn)b,可執(zhí)行（）。A . p->next=q->next ;B. p=q->next;C. p->next=q;D. p->next=q;3

2、.以下說(shuō)法不正確的是A.線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)不必占用連續(xù)的存儲(chǔ)空間B . 一種邏輯結(jié)構(gòu)只能有唯一的存儲(chǔ)結(jié)構(gòu)C. 一種邏輯結(jié)構(gòu)可以有不同的存儲(chǔ)結(jié)構(gòu)D.線性表的順序存儲(chǔ)結(jié)構(gòu)必須占用連續(xù)的存儲(chǔ)空間4 .在一個(gè)單向鏈表中，在p所指結(jié)點(diǎn)之后插入一個(gè)s所指的結(jié)點(diǎn)時(shí)，可執(zhí)行（）；和p->next=s;A . p= s;B. p->next=s->next;C. p=s->next; D. s->next=p->next;5 .把數(shù)據(jù)存儲(chǔ)到計(jì)算機(jī)中，并具體體現(xiàn)（）稱為物理結(jié)構(gòu)。A.數(shù)據(jù)元素間的邏輯關(guān)系B.數(shù)據(jù)的處理方法C.數(shù)據(jù)的性質(zhì)D.數(shù)據(jù)的運(yùn)算6 .設(shè)有一個(gè)長(zhǎng)度為 23的

3、順序表，要?jiǎng)h除第 8個(gè)元素需移動(dòng)元素的個(gè)數(shù)為（）。A . 16 B . 14 C .15 D . 137 .鏈表所具備的特點(diǎn)之一是（）。A .可以隨機(jī)訪問(wèn)任一結(jié)點(diǎn)B .需要占用連續(xù)的存儲(chǔ)空間C .插入元素的操作不需要移動(dòng)元素D .刪除元素的操作需要移動(dòng)元素8 .設(shè)一棵有8個(gè)葉結(jié)點(diǎn)的二叉樹(shù)，度數(shù)為 1的結(jié)點(diǎn)有3個(gè)，則該樹(shù)共有（）個(gè)結(jié)點(diǎn)。A. 20B. 18 C .17 D . 169 .圖狀結(jié)構(gòu)中數(shù)據(jù)元素的位置之間存在（）的關(guān)系。A . 一對(duì)一B.多對(duì)多C. 一對(duì)多D.每一個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼10 . 一棵具有5層的完全二叉樹(shù)，最后一層有4個(gè)結(jié)點(diǎn)，則該樹(shù)總共有（）個(gè)結(jié)點(diǎn)。A .

4、14 B . 15 C . 19 D . 1811 .元素15, 9, 11, 13按順序依次進(jìn)棧，則該棧的不可能輸出序列是（）（進(jìn)棧出棧可以交替進(jìn)行）。A .13,11, 9, 15B.15, 9, 11, 13C .13,11, 15, 9D.9, 15 , 13, 1112 .設(shè)主串為“ FABcCDABcdEFaBq以下模式串能與主串成功匹配的是（）。A. EFaBcB. ABCdEC. DABCCD .FAbcC13 .設(shè)有一個(gè)14階的對(duì)稱矩陣A（第一個(gè)元素為ai,i）,采用壓縮存儲(chǔ)的方式，將其下三角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組B中（數(shù)組下標(biāo)從1開(kāi)始），則矩陣中元素 a4,3在一維

5、數(shù)組B中的下標(biāo)是（）。A . 9 B . 10 C . 11 D .814 .元素111, 113, 115, 117按順序依次進(jìn)棧，則該棧的不可能輸出序列是（）（進(jìn)棧出棧可以交替進(jìn)行）A .117,115, 113, 111B, 111, 113, 115,117C .113,111, 117, 115D, 117, 115, 111,11315 .在一棵二叉樹(shù)中，若編號(hào)為8的結(jié)點(diǎn)存在右孩子，則右孩子的順序編號(hào)為（）。A . 18B. 1616.以下說(shuō)法不正確的是（）。A .棧和隊(duì)列都是線性結(jié)構(gòu)C.棧和隊(duì)列的特點(diǎn)都是先進(jìn)后出C . 15 D . 17B .棧的特點(diǎn)是后進(jìn)先出D .隊(duì)列的特點(diǎn)是

6、先進(jìn)先出文案大全17 .設(shè)一棵哈夫曼樹(shù)共有 14個(gè)非葉結(jié)點(diǎn)，則該樹(shù)總共有（）個(gè)結(jié)點(diǎn)。A . 29B.27 C30 D . 2818 .設(shè)有一個(gè)15階的對(duì)稱矩陣A（第一個(gè)元素為a”），采用壓縮存儲(chǔ)的方式，將其下三角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組b中（數(shù)組下標(biāo)從1開(kāi)始），則矩陣中元素 a4,2在一維數(shù)組B中的下標(biāo)是（）。A. 9 B . 8 C . 7 D . 1019 .如圖1所示的一個(gè)圖，若從頂點(diǎn)a出發(fā)，按深度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為（）。A . abecdf B . acfebd C . aebcfd D . aedbfc圖120 .如圖2所示的一個(gè)圖，若從頂點(diǎn)a出發(fā)，

7、按深度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為（）。A . acedbf B . acebfd C . aebcfd D . aedfcb二、填空題1 .隊(duì)列的特點(diǎn)之一是：元素進(jìn)、出隊(duì)的次序是：先進(jìn)。2 .序列13,11,14,12,17,15，采用冒泡排序算法，經(jīng)一趟冒泡后，序列的結(jié)果是 。3 . 結(jié)構(gòu)中，數(shù)據(jù)元素間存在一對(duì)多的關(guān)系。4 .對(duì)16個(gè)元素的序列用冒泡排法進(jìn)行排序，通常需要進(jìn)行 趟冒泡。5 .對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)，矩陣中每個(gè)非零元素對(duì)應(yīng)的三元組包括該元素的 三項(xiàng)信息是。6 .對(duì)9個(gè)元素的一組記錄(58, 35, 93, 20, 12, 78, 56, 41, 79)進(jìn)行直

8、接插入排 序(由小到大排序)，當(dāng)把第7個(gè)記錄56插入有序表，為尋找插入位置需比較次。7 .在對(duì)11個(gè)記錄的序列(12, 35, 9, 7 ,2, 11 ,56,95 ,37,58 ,60)進(jìn)行直接插入排序時(shí)，當(dāng)把第6個(gè)記錄11插入到有序表時(shí)，為尋找插入位置，元素間需比較 次。(由小到大排列)8 .結(jié)構(gòu)中的數(shù)據(jù)元素存在一對(duì)多的關(guān)系稱為 結(jié)構(gòu)。9 .哈希函數(shù)是記錄關(guān)鍵字的值與該記錄 之間所構(gòu)造的對(duì)應(yīng)關(guān)系。10 .設(shè)有一棵深度為 5的完全二叉樹(shù)，第 5層上有3個(gè)結(jié)點(diǎn)，該樹(shù)共有 個(gè)結(jié)點(diǎn)。(根所在結(jié)點(diǎn)為第1層)11 . 20個(gè)元素進(jìn)行冒泡法排序，通常需要進(jìn)行19趟冒泡，其中第10趟冒泡共需要進(jìn)行次元素間

9、的比較。12 . 一棵二叉樹(shù)中每一個(gè)非葉結(jié)點(diǎn)的度數(shù)都為2,共有10個(gè)非葉結(jié)點(diǎn)，則該樹(shù)共有個(gè)結(jié)點(diǎn)。13 . 一棵有19個(gè)結(jié)點(diǎn)的二叉樹(shù)，采用鏈?zhǔn)浇Y(jié)構(gòu)存儲(chǔ)，該樹(shù)結(jié)構(gòu)中有 個(gè)指針 域?yàn)榭铡?4 .序列3,1,7,18,6,9,13,12經(jīng)一趟歸并排序的結(jié)果為 。15 .中序遍歷一棵 樹(shù)可得到一個(gè)有序序列。16 . 一棵有16個(gè)葉結(jié)點(diǎn)的哈夫曼樹(shù)，則該樹(shù)共有 個(gè)非葉結(jié)點(diǎn)。17 .二叉排序樹(shù)插入操作中，新插入的結(jié)點(diǎn)總是以樹(shù)的 結(jié)點(diǎn)被插入的18 . 遍歷二叉排序樹(shù)可得到一個(gè)有序序列。19 .廣義表的(a , (d,a ,b) , h , (e ,( (i ,j ) ,k )深度是 。20 .廣義表(f , h

10、 , (a ,b, d, c) , d , e ,( (i ,j ) ,k )的長(zhǎng)度是_。21 .序列4,2,5,3,8,6,7, 9,采用歸并排序算法(升序),經(jīng)一趟歸并后，序列的結(jié)果22 .廣義表的(h ,c, g, a , (a ,b) , d , e ,( (i ,j ) ,k )深度是 。23 .字符串 a1= ''teijing " , a2 =、'tef " , a3="teifang " , a4="tefi "最小的24 .設(shè)有串 p1=" ABADF ,P2=" ABAF

11、D, P3= ABADFA P4=" ABAF , 四個(gè)串中最 小的是 。三、綜合題1.設(shè)查找表為序號(hào)1234567891011序列4121819375565778586117(1)畫(huà)出對(duì)上述查找表進(jìn)行折半查找所對(duì)應(yīng)的判定樹(shù)(樹(shù)中結(jié)點(diǎn)用下標(biāo)表示)(2)說(shuō)明成功查找到元素 86需要經(jīng)過(guò)多少次比較？(3)求在等概率條件下，成功查找的平均比較次數(shù)？2. (1)設(shè)有數(shù)據(jù)集合50, 39, 17, 83, 111, 14, 65, 13, 91, 102, 49,依次取 集合中各數(shù)據(jù)構(gòu)造一棵二叉排序樹(shù)。(2)一組記錄的關(guān)鍵字序列為(6, 9, 7, 4, 5, 8),利用堆排序(堆頂元素是最小

12、元素)的方法建立初始堆。(要求用完全二叉樹(shù)表示)3.(1) 一組記錄的關(guān)鍵字序列為(26, 59, 36, 18, 20, 25),給出利用堆排序(堆頂 元素是最小元素)的方法建立的初始堆(要求以完全二叉樹(shù)描述)。(2)對(duì)關(guān)鍵字序列(26,59,36,18,20,64)采用快速排序，給出以第一個(gè)關(guān)鍵字為分割元素，經(jīng)過(guò)一次劃分后的結(jié)果。4. (1)如下表為一個(gè)長(zhǎng)度為 10的有序表，給出按折半查找對(duì)該表進(jìn)行查找的判定樹(shù)(2) 按折半查找對(duì)該表進(jìn)行查找，求在等概率情況下查找成功的平均比較次數(shù)。為了成功查找72 ,給出元素的比較次數(shù)。序號(hào)12345678910序列2349391825607284555

13、95. (1)以1, 2, 3 , 6, 7, 8作為葉結(jié)點(diǎn)的權(quán)，構(gòu)造一棵哈夫曼樹(shù) (2)給出具有相應(yīng)權(quán)重值的葉結(jié)點(diǎn)的哈夫曼編碼。實(shí)用文檔四、程序填空題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( (1)mid=( (2)if(amid.key=k)return (3)else if ( (4)l

14、ow=mid+1;else一(5);return -11.(1) low<=high文案大全(2)( low+high)/2 (3) mid; amid.key<k(5) high=mid-1;2.設(shè)線性表以不帶頭結(jié)點(diǎn)的單向鏈表存儲(chǔ)，鏈表頭指針為head,以下程序的功能是輸出鏈表中各結(jié)點(diǎn)中的數(shù)據(jù)域data。完成程序中空格部分。#define NULL 0 void main() NODE *head ,*p ;p=head; /*p為工作指針*/ doprintf("n% d,(1);_12)-；while( (3);2.(1) p->data(2) p=p->

15、;next (3) p!=NULL3.以下程序是前序遍歷二叉樹(shù)的遞歸算法的程序，完成程序中空格部分(樹(shù)結(jié)構(gòu)中左、 右指針域分別為left和right,數(shù)據(jù)域data為字符型，BT指向根結(jié)點(diǎn))。void Inorder (struct BTreeNode *BT)if(BT!=NULL)_；_；Inorder(BT- >right);利用上述程序?qū)τ覉D進(jìn)行前序遍歷，結(jié)果是(3);3.(1) printf( «%C ,BT->data) Inorder(BT->left)(3) a b d f e c4.以下程序是后序遍歷二叉樹(shù)的遞歸算法的程序，完成程序中空格部分(樹(shù)結(jié)

16、構(gòu)中左、 右指針域分別為left和right,數(shù)據(jù)域data為字符型，BT指向根結(jié)點(diǎn))。完成程序中 空格部分。void Inorder (struct BTreeNode *BT)if( BT!=NULL) Inorder(BT->left); _(1_(2)4. (1) Inorder(BT->right)(2) printf( "d ,BT->data)5.順序查找算法如下，完成程序中空格部分。 int search (NODE a ,int n , int k )/*在a0,a1an-1,中查找關(guān)鍵字等于 k的記錄，查找成功返回記錄的下標(biāo)，失 敗時(shí)返回-1*/

17、 int i=0; while( i< n && ai.key 11)_(2)if (_(3)_) return i; else return -1;)5.(1) !=k(2) i+;(3) ai.key= =k綜合練習(xí)一答案一、單項(xiàng)選擇題1 .C 2 , A 3 . B 4.D 5. A 6.C 7.C 8. B 9 . B 10 . C 11 . C 12 .A 13 .A實(shí)用文檔14. D 15 . D_16 . C 17 . A 18"". B 19 . D 20 . B二、填空題1 .先出2 . 11,13,12,14,15,17 3.樹(shù)型4

18、 . 15 5 ,行下標(biāo) 列下標(biāo) 數(shù)組元素6. 4次7.38.樹(shù)形9.存儲(chǔ)位置 10 .18 11 . 1012. 2113. 2014.1 , 3, 7, 18, 6, 9, 12, 1315. 二叉排序樹(shù) 16 . 1517.葉 18. 中序19.420. 621.2 , 4, 3, 5, 6, 8, 7, 922. 323.a224. P1文案大全三、綜合題(2) 3 次(3)平均查找長(zhǎng)度 =(1+2*2+3*4+4*4)/11=32.(3) 4,5,7,9,6,8495759658圖6(4) (1)18 , 20, 25, 59, 26, 36182025592636圖7(2) 20

19、, 18, 26, 36, 59, 644. (1)5281369471072(2)(1+2*2+3*4+4*3)/10=29/104 次5.(2)1 00002 000130016 017108 11綜合練習(xí)二、單項(xiàng)選擇題1 .設(shè)頭指針為head的非空的單向循環(huán)鏈表，指針p指向尾結(jié)點(diǎn)，則滿足表達(dá)式（）為真。A . p->next = =NULL B . p= =NULL C . p->next= =head D . p= =head2 .數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)包括數(shù)據(jù)元素的表示和（）。A .數(shù)據(jù)處理的方法C . 相關(guān)算法D.數(shù)據(jù)元素的類型D.數(shù)據(jù)元素間的關(guān)系的表示3 . 一種邏輯結(jié)構(gòu)（）

20、。.只能有唯一的存儲(chǔ)結(jié)構(gòu)D .是指某一種數(shù)據(jù)元素的性質(zhì)p指向尾結(jié)點(diǎn)，要使該鏈表成為單向循環(huán)鏈表head->next=p;p->next=head;.占用連續(xù)的存儲(chǔ)空間D .可以通過(guò)下標(biāo)對(duì)鏈表進(jìn)行直接訪問(wèn)則該棧的不可能輸出序列是（）（進(jìn)棧出?？梢越惶孢M(jìn)行）111, 113, 115, 117113, 111, 117, 115）的關(guān)系。A .可以有不同的存儲(chǔ)結(jié)構(gòu)BC.是指某一種數(shù)據(jù)元素之間的存儲(chǔ)關(guān)系4 .在一個(gè)頭指針為 head的單向鏈表中，可執(zhí)行（）。A . p= head->next;BC. head->next=p->next; D5 .鏈表所具備的特點(diǎn)之一是

21、（）。A .可以隨機(jī)訪問(wèn)任一結(jié)點(diǎn)BC .插入刪除元素的操作不需要移動(dòng)元素結(jié)點(diǎn)6 .元素111, 113, 115, 117按順序依次進(jìn)棧，A . 117, 115, 113, 111BC . 117, 115, 111 , 113D7 .線性結(jié)構(gòu)中數(shù)據(jù)元素的位置之間存在（ A . 一對(duì)一B. 一對(duì)多.每一個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼C.多對(duì)多D8 .以下說(shuō)法正確的是（）。A .棧的特點(diǎn)是先進(jìn)后出8 .棧的特點(diǎn)是先進(jìn)先出C .隊(duì)列的特點(diǎn)是先進(jìn)后出D.棧和隊(duì)列的特點(diǎn)都是先進(jìn)后出s所指的結(jié)點(diǎn)時(shí)，可執(zhí)行（ p->next=s->next;s->next=p->next;

22、 p->next=s;9 .在一個(gè)單向鏈表中 p所指結(jié)點(diǎn)之后插入一個(gè)A . p->next= s; s->next= p->next BC. p=s->nextD10 .設(shè)有一個(gè)20階的對(duì)稱矩陣a（第一個(gè)元素為 a1,1）,采用壓縮存儲(chǔ)的方式，將其下三角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組b中（數(shù)組下標(biāo)從1開(kāi)始），則矩陣中元素 a6,2在一維數(shù)組B中的下標(biāo)是（）。A. 24 B . 17 C . 16 D . 2311 .元素11, 13, 15, 17按順序依次進(jìn)棧，則該棧的不可能輸出序列是（）（進(jìn)棧出?？梢越惶孢M(jìn)行）。A . 17, 15, 13, 11B, 11,

23、 13, 15, 17C . 17, 15, 11, 13D, 13, 11, 17, 1512 .設(shè)一棵有2n+1個(gè)結(jié)點(diǎn)的二叉樹(shù)，除葉結(jié)點(diǎn)外每個(gè)結(jié)點(diǎn)度數(shù)都為2,則該樹(shù)共有（）個(gè)葉結(jié)點(diǎn)。A. nBn+1 C . n+2 D . n-113 .設(shè)有一個(gè)20階的對(duì)稱矩陣 A（第一個(gè)元素為 ai,i）,采用壓縮存儲(chǔ)的方式，將其下三角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組 b中（數(shù)組下標(biāo)從i開(kāi)始），則矩陣中元素 a5,2在一維數(shù)組b中的下標(biāo)是（）。A . 11 B . 12 C . 13 D . 1014 .已知如圖1所示的一個(gè)圖，若從頂點(diǎn)a出發(fā)，按廣度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為（）。A

24、. abecdf B . aecbdf C . aebcfd D . aedfcb15 .設(shè)一棵哈夫曼樹(shù)共有 11個(gè)非葉結(jié)點(diǎn)，則該樹(shù)有（）個(gè)葉結(jié)點(diǎn)。A . 22B. 10 C . 11 D . 1216 .線性表以（）方式存儲(chǔ)，能進(jìn)行折半查找。A .關(guān)鍵字有序的順序B .順序 C .鏈接 D .二叉樹(shù)17 . 一棵具有38個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，最后一層有（）個(gè)結(jié)點(diǎn)。A . 7B. 5 C.6 D .818 . 一棵具有38個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，最后一層有（）個(gè)結(jié)點(diǎn)。A . 7 B . 5 C . 6 D . 819 .已知如圖2所示的一個(gè)圖，若從頂點(diǎn)a出發(fā)，按深度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一

25、種頂點(diǎn)序列為（）。A . abecdf B . acfebd C . aebcfd D . aedfcb圖220 .對(duì)一個(gè)棧頂指針為top的鏈棧進(jìn)行出棧操作，用變量 e保存棧頂元素的值，則執(zhí)行( )。A. e= top->next; top->data=e;B. top=top->next; e=top->data;C. e=top->data; top=top->next;D. top=top->next; e=data;二、填空題1.字符串 a1= ''BEIJING" , a2 = ''BEF , a3=

26、''BEFANG , a4= "BEI "最小的2 .數(shù)組a經(jīng)初始化char a ="English ” ; a7中存放的是 字符串的結(jié)束符。3 .把數(shù)據(jù)存儲(chǔ)到計(jì)算機(jī)中，并具體體現(xiàn)數(shù)據(jù)元素間的邏輯結(jié)構(gòu)稱為物理結(jié)構(gòu)(存儲(chǔ)結(jié)構(gòu))。4,設(shè)有串 p1=" ABADF ,P2=" ABAFD, P3= ABADFA P4=" ABAF , 四個(gè)串中最大的是 5 .設(shè)有一個(gè)長(zhǎng)度為 22的順序表，要?jiǎng)h除第 8個(gè)元素需移動(dòng)元素的個(gè)數(shù)為 q6 .在一棵二叉樹(shù)中，若編號(hào)為 i的結(jié)點(diǎn)存在右孩子，則右孩子的順序編號(hào)為 。7 .在一棵二叉樹(shù)中，

27、若編號(hào)為i的結(jié)點(diǎn)存在左孩子，則左孩子的順序編號(hào)為。8 .設(shè)有一個(gè)長(zhǎng)度為 20的順序表，要插入一個(gè)元素，并作為第8個(gè)元素，需移動(dòng)元素的個(gè)數(shù)為。9 .設(shè)一棵有n個(gè)葉結(jié)點(diǎn)的二叉樹(shù)，除葉結(jié)點(diǎn)外每個(gè)結(jié)點(diǎn)度數(shù)都為2,則該樹(shù)共有 個(gè)結(jié)點(diǎn)。10 .結(jié)構(gòu)中的數(shù)據(jù)元素存在多對(duì)多的關(guān)系稱為 結(jié)構(gòu)。11 .在對(duì)一組序列 (45,29,87,12,6,63,55,37,78)進(jìn)行直接插入排序時(shí)，當(dāng)把第 8個(gè)記錄37插 入到有序表時(shí)，為尋找插入位置需比較 次。(由小到大排序)12 .設(shè)有一棵深度為 4的完全二叉樹(shù)，第四層上有5個(gè)結(jié)點(diǎn)，該樹(shù)共有 個(gè)結(jié)點(diǎn)。(根所在結(jié)點(diǎn)為第1層)13 . n個(gè)元素進(jìn)行冒泡法排序，通常需要進(jìn)行

28、趟冒泡。14 . 一棵二叉樹(shù)中有 n個(gè)非葉結(jié)點(diǎn)，每一個(gè)非葉結(jié)點(diǎn)的度數(shù)都為2,則該機(jī)共有 15 . 一棵有21個(gè)結(jié)點(diǎn)的哈夫曼樹(shù)，該樹(shù)中有 個(gè)葉結(jié)點(diǎn)。16 .在對(duì)一組記錄(55,39,97,22,16,73,65,47,88)進(jìn)行直接插入排序時(shí)，當(dāng)把第 7個(gè)記錄65插入到有序表時(shí)，為尋找插入位置需比較 次。(由小到大排序17 . 遍歷二叉排序樹(shù)可得到一個(gè)有序序列。18 . n個(gè)元素進(jìn)行冒泡法排序，第j趟冒泡要進(jìn)行 一次元素間的比較。19 .廣義表(a , (a ,b) , d , e ,( (i ,j ) ,k )的長(zhǎng)度是 。20 . 一棵有n個(gè)葉結(jié)點(diǎn)的哈夫曼樹(shù)，則該樹(shù)共有 個(gè)結(jié)點(diǎn)。21 .廣義表

29、的(a , (a ,b) , d , e ,( (i ,j ) ,k )深度是 。22 .中序遍歷 可得到一個(gè)有序序列。23 .序列14,12,15,13,18,16，采用冒泡排序算法(升序),經(jīng)一趟冒泡后，序列的結(jié)果24 .廣義表(a ,b) , d , e ,( (i ,j ) ,k )的長(zhǎng)度是 三、綜合題1. 設(shè)查找表為(7,15,21,22,40,58,68,80,88,89,120)，元素的下標(biāo)依次為1,2,3,11.(1)畫(huà)出對(duì)上述查找表進(jìn)行折半查找所對(duì)應(yīng)的判定樹(shù)(樹(shù)中結(jié)點(diǎn)用下標(biāo)表示)(2)說(shuō)明成功查找到元素 40需要經(jīng)過(guò)多少次比較?(3)求在等概率條件下，成功查找的平均比較次數(shù)？

30、2. (1)設(shè)有數(shù)據(jù)集合40, 29, 7, 73, 101, 4, 55, 2, 81, 92, 39,依次取集合 中各數(shù)據(jù)構(gòu)造一棵二叉排序樹(shù)。(2)一組記錄的關(guān)鍵字序列為(5, 8, 6, 3, 4, 7),利用堆排序(堆頂元素是最小元素)的方法建立初始堆。(要求用完全二叉樹(shù)表示)3. (1)一組記錄的關(guān)鍵字序列為(47, 80, 57, 39, 41, 46),給出利用堆排序(堆頂元素是最小元素)的方法建立的初始堆(要求以完全二叉樹(shù)描述)。(2)對(duì)關(guān)鍵字序列(47,80,57,39,41,85)采用快速排序，給出以第一個(gè)關(guān)鍵字為分割元素，經(jīng)過(guò)一次劃分后的結(jié)果。(3)如圖3所示的二叉樹(shù)，給

31、出其前序遍歷序列。4. (1)以2, 3, 4, 7, 8, 9作為葉結(jié)點(diǎn)的權(quán)，構(gòu)造一棵哈夫曼樹(shù)(2)給出上述哈夫曼樹(shù)葉結(jié)點(diǎn)的哈夫曼編碼。(3) 一組記錄的關(guān)鍵字序列為(37, 70, 47, 29, 31, 85),利用快速排序，以第個(gè)關(guān)鍵字為分割元素，給出經(jīng)過(guò)一次劃分后結(jié)果。(由小到大排序)四、程序填空題left1.以下程序是中序遍歷二叉樹(shù)的遞歸算法的程序，完成程序中空格部分（樹(shù)結(jié)構(gòu)中左、右指針域分別為和right,數(shù)據(jù)域data為字符型，BT指向根結(jié)點(diǎn))void Inorder (struct BTreeNode *BT)if(BT!=NULL)Inorder(BT->left);

32、(1) ;(2) ;利用上述程序?qū)τ覉D進(jìn)行中序遍歷，結(jié)果是(3)四、程序填空題1.(1) printf( "C ,BT->data)(2) Inorder(BT->right)(3) dbeafc并輸出鏈表中各結(jié)點(diǎn)中的數(shù)據(jù)。2.設(shè)線性表為(6, 10, 16, 4),以下程序用說(shuō)明結(jié)構(gòu)變量的方法建立單向鏈表,#define NULL 0void main()NODE a,b,c,d,*head,*p;a.data=6;b.data=10;c.data=16;d.data=4; /*d 是尾結(jié)點(diǎn) */head= (1);a.next=&b;b.next=&c

33、;c.next=&d;(2); /*以上結(jié)束建表過(guò)程*/p=head;/*p為工作指針，準(zhǔn)備輸出鏈表*/doprintf("r%d, (3);(4);while(5);2 .(1) &a(2) d->next=NULL(3) p->data(4) p=p->next(5) p!=NULL3 .以下冒泡法程序?qū)Υ娣旁赼1 , a2,，an中的序列進(jìn)行排序，完成程序中的空格部分，其中n是元素個(gè)數(shù)，要求按升序排列。void bsort (NODE a , int n) NODE temp;int i,j,flag;for(j=1; (1);j+);flag

34、=0;for(i=1; (2);i+)if(ai.key>ai+1.key)flag=1;temp=ai;(3) ;(4) ;if(flag= =0)break;程序中flag的功能是5_5)3.(1) j<=n-1 i<=n-j(3) ai=ai+1(4) ai+1=temp(5)當(dāng)某趟冒泡中沒(méi)有出現(xiàn)交換則已排好序，結(jié)束循環(huán)4.以下程序是中序遍歷二叉樹(shù)的遞歸算法的程序，完成程序中空格部分（樹(shù)結(jié)構(gòu)中左、BT指向根結(jié)點(diǎn)）右指針域分別為left和right,數(shù)據(jù)域data為字符型, void Inorder (struct BTreeNode *BT)if(BT!=NULL)(1

35、)；_C2;Inorder(BT->right);)利用上述程序?qū)τ覉D進(jìn)行遍歷，結(jié)果是(3)4.(1) Inorder(BT->left)(2) printf("d ,BT->data)(3) bedafc綜合練習(xí)二答案一、單項(xiàng)選擇題I .C 2. D 3 .A 4.D 5. C 6 .C 7. A 8"".A 9 . D 10 . BII . C 12 . B 13 . B 14 . B 15. D 16. A 17. A 18. A 19.D 20.C二、填空題1. a22. 字符串的結(jié)束符3. 物理結(jié)構(gòu)（存儲(chǔ)結(jié)構(gòu)）4. p25. 146.

36、2i+17. 2i8. 139. 2n-110. .圖狀11. 512. . 1213. n-114. n+115. 1116. 317. 中序18. n-j19. 520.2n-120. 322. 二叉排序樹(shù)23. 12,14,13,15,16,1824. 4三、綜合題圖6圖83(1) 39, 41, 46, 80, 47, 57圖9(2) 41 , 39, 47, 57, 80, 85(3) abdefcg4.2: 000040001500181091110 01(3) 31,29,37,47,70,85綜合練習(xí)三一、單項(xiàng)選擇題1 .數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)包括數(shù)據(jù)元素的表示和（）。A .數(shù)據(jù)處理的

37、方法B.數(shù)據(jù)元素的類型C .相關(guān)算法D.數(shù)據(jù)元素間的關(guān)系的表示2 .設(shè)有頭指針為head的不帶頭結(jié)點(diǎn)的非空的單向循環(huán)鏈表，指針p指向其尾結(jié)點(diǎn)，要?jiǎng)h除第一個(gè)結(jié)點(diǎn),則可利用下述語(yǔ)句 head=head->next;和（）。A . p =head; B . p=NULL; C . p->next =head; D . head=p;3 .樹(shù)狀結(jié)構(gòu)中數(shù)據(jù)元素的位置之間存在（）的關(guān)系。A .每一個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼B . 一對(duì)一C.多對(duì)多D. 一對(duì)多4 .以下說(shuō)法正確的是（）。A. 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)必須占用連續(xù)的存儲(chǔ)空間B. 一種邏輯結(jié)構(gòu)可以有不同的存儲(chǔ)結(jié)構(gòu)C . 一種邏

38、輯結(jié)構(gòu)只能有唯一的存儲(chǔ)結(jié)構(gòu)D .線性表的順序存儲(chǔ)結(jié)構(gòu)不必占用連續(xù)的存儲(chǔ)空間5 .設(shè)有一個(gè)長(zhǎng)度為26的順序表，要插入一個(gè)元素，并使它成為新表的第 6個(gè)元素，需移動(dòng)元素的個(gè)數(shù)為（）。A . 21 B . 22 C . 20（） 稱為物理結(jié)構(gòu)。.數(shù)據(jù)的性質(zhì)數(shù)據(jù)元素間的邏輯關(guān)系6 .把數(shù)據(jù)存儲(chǔ)到計(jì)算機(jī)中，并具體體現(xiàn)A .數(shù)據(jù)的處理方法BC .數(shù)據(jù)的運(yùn)算D.7 .頭指針為head的帶頭結(jié)點(diǎn)的單向循環(huán)鏈表，p所指向尾結(jié)點(diǎn)，要使該鏈表成為不帶頭結(jié)點(diǎn)的單向循環(huán)鏈表,可執(zhí)行 head=head->nex;和（）。A . p= head->nextBC. head->next=p->nex

39、t D8 .順序表所具備的特點(diǎn)之一是（）。A .可以隨機(jī)訪問(wèn)任一結(jié)點(diǎn)BC .插入元素的操作不需要移動(dòng)元素.head->next=p p->next=head;.不需要占用連續(xù)的存儲(chǔ)空間 D .刪除元素的操作不需要移動(dòng)元素)(進(jìn)9 .元素111, 113, 115, 117按順序依次進(jìn)棧，則該棧的不可能輸出序列是（棧出?？梢越惶孢M(jìn)行）A .117,115, 113, 111B, 111,113, 115, 117C .117,115, 111 , 113D, 113,111, 117, 11510 .圖狀結(jié)構(gòu)中數(shù)據(jù)元素的位置之間存在（）的關(guān)系。A . 一對(duì)一B. 一對(duì)多C.多對(duì)多D.

40、每一個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼11 .以下說(shuō)法正確的是（）。A .棧的特點(diǎn)是先進(jìn)先出B .棧的特點(diǎn)是先進(jìn)后出C .隊(duì)列的特點(diǎn)是先進(jìn)后出12 .元素20, 14, 16, 18按順序依次進(jìn)棧，則該棧的不可能輸出序列是（）（進(jìn)棧出?？梢越惶孢M(jìn)行）。A . 18, 16, 14, 20B . 20, 14, 16, 18C . 18, 16, 20, 14D . 14, 20, 18, 16D.棧和隊(duì)列的特點(diǎn)都是后進(jìn)后出13. 設(shè)有一個(gè)20階的對(duì)稱矩陣A（第一個(gè)元素為a”），采用壓縮存儲(chǔ)的方式，將其下三角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組b中（數(shù)組下標(biāo)從1開(kāi)始），則矩陣元素a6,2在一維數(shù)組B

41、中的下標(biāo)是（）。A. 21 B . 17 C . 28 D . 2314 .設(shè)有一個(gè)12階的對(duì)稱矩陣A（左上角第一個(gè)元素為曰,1）,采用壓縮存儲(chǔ)的方式，將其下三角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組 B中（數(shù)組下標(biāo)從1開(kāi)始），則矩陣中元素 a5,4在一維數(shù)組b中的下標(biāo)是A . 14 B . 12 C . 13 D . 1115 .設(shè)有串 p1=" ABADF ,P2=" ABAFD, P3=" ABADFA ,P4= " ABAF，以下四個(gè)串中最大的是A . p3 B . p2 C . p1 D . p416 .設(shè)有一個(gè)長(zhǎng)度為 22的順序表，要?jiǎng)h除第8個(gè)元素需

42、移動(dòng)元素的個(gè)數(shù)為（）。A . 25 B . 14 C . 15 D . 2317 .數(shù)組a經(jīng)初始化 char a ="English " ; a7中存放的是（）。A.字符串的結(jié)束符B.字符hC. '' h"D.變量 h18 .在一棵二叉樹(shù)中，若編號(hào)為5的結(jié)點(diǎn)存在右孩子，則右孩子的順序編號(hào)為（）。A . 12 B .9 C . 11 D . 1019 .設(shè)主串為“ ABcCDABcdEFaB'G以下模式串能與主串成功匹配的是（）。A. Bcd B. BCd C. ABC D. Abc20 . 一棵具有5層的完全二叉樹(shù)，最后一層有4個(gè)結(jié)點(diǎn)，則該

43、樹(shù)總共有（）個(gè)結(jié)點(diǎn)。A . 14B. 15 C . 19 D . 1821 .在一棵二叉樹(shù)中，若編號(hào)為i的結(jié)點(diǎn)存在左孩子，則左孩子的順序編號(hào)為（）。A . 2i+1B. 2i-1 C . 2i D . 2i+222 .如圖1所示，若從頂點(diǎn)a出發(fā)，按圖的廣度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種 頂點(diǎn)序列為（）。A . abcdfge B . abcedfg C . acbfedg D . abcfgde23.如圖2所示，若從頂點(diǎn) 到的一種頂點(diǎn)序列為（A . abecdf Ba出發(fā)，按圖的廣度優(yōu)先搜索法進(jìn)行遍歷，則可能得）°.aecbdf C . aebcfd D . aedfcb24.

44、字符串'' abcd321ABCD的子串是（）。A. ''21ABCB.abcABCDC. abcD D.321a25 .線性表以（）方式存儲(chǔ)，能進(jìn)行折半查找。A .鏈接 B .順序 C .關(guān)鍵字有序的順序D .二叉樹(shù)26 .數(shù)組a經(jīng)初始化 char a ="English ” ; a1中存放的是（）。A.字符nB.字符EC. "n"D.'E27 . 一棵具有38個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，最后一層有（）個(gè)結(jié)點(diǎn)。A . 7B.5 C . 6 D .828 .如圖3所示，若從頂點(diǎn) a出發(fā)，按圖的深度優(yōu)先搜索法進(jìn)行遍歷，則可能得 到的一

45、種頂點(diǎn)序列為（）。A . abecdf B . acfebd C . aebcfd D . aedfcb29 .下圖的拓?fù)湫蛄惺牵ˋ. 5 2 3 4 6C . 5 6 2 3 4）。BD. 2 3 5 6 430.下圖的拓?fù)湫蛄惺牵ǎ. 5 2 3 6 4D. 2 3 4 5 6A. 5 2 3 4 6C . 5 6 4 2 3二、填空題1 .結(jié)構(gòu)中的數(shù)據(jù)元素存在多對(duì)多的關(guān)系稱為 結(jié)構(gòu)。2 .棧的特點(diǎn)之一是：元素進(jìn)、出棧的次序是：先進(jìn)。3 . n個(gè)元素進(jìn)行冒泡法排序，第j趟冒泡要進(jìn)行 次元素間的比較。4 .對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)，矩陣中每個(gè)非零元素對(duì)應(yīng)的三元組包括該元素的三項(xiàng)信息5 .中

46、序遍歷 樹(shù)可得到一個(gè)有序序列。6 .在對(duì)10個(gè)記錄的序列(9, 35,19, 77 ,2, 10 ,53, 45,27,68)進(jìn)行直接插入排序時(shí)，當(dāng)把第6個(gè)記錄10插入到有序表時(shí)，為尋找插入位置，元素間需比較 次。(按升序排序)7 .待排序的序列為8,3,4,1,2,5,9,采用直接選擇排序算法，當(dāng)進(jìn)行了兩趟選擇后，結(jié)果序列 為()。8 .字符串 a1= ''beijing " , a2 =、'bef " , a3=''beifang " , a4="befi "最小的9 .廣義表(a ,b) , d ,

47、 e ,( (i ,j ) ,k )的長(zhǎng)度是 。10 . 10個(gè)元素進(jìn)行冒泡法排序，其中第5趟冒泡共需要進(jìn)行 次元素間的比較。11.廣義表的(c, a , (a ,b) , d , e ,( (i ,j ) ,k )深度是。12 . 遍歷一棵二叉排序樹(shù)可得到一個(gè)有序序列。13 .對(duì)稀疏矩陣進(jìn)彳T壓縮存儲(chǔ)，可采用三元組表，一個(gè)有10行10列的稀疏矩陣 A共有95個(gè)零元素，其相應(yīng)的三元組表共有 個(gè)元素。14 .廣義表(c , (a ,b,c) , ( d , e ,f ) , ( (i ,j ) ,k )的長(zhǎng)度是.15 .在對(duì)一組記錄(50, 49, 97, 22, 16, 73, 65, 47,

48、 88)進(jìn)行直接插入排序時(shí)，當(dāng)把第7個(gè)記錄65插入到有序表時(shí)，為尋找插入位置需比較 次。16 .廣義表的(c , (b,a ,b) , f , e ,( (i ,j ) ,k )深度是.17 . 一棵有5個(gè)葉結(jié)點(diǎn)的哈夫曼樹(shù)，該樹(shù)中總共有 個(gè)結(jié)點(diǎn)。18 .序列4,2,5,3 ,8, 6,采用冒泡排序算法(升序),經(jīng)一趟冒泡后，結(jié)果序列是 。19 .設(shè)有一棵深度為4的完全二叉樹(shù)，第四層上有5個(gè)結(jié)點(diǎn)，該樹(shù)共有 個(gè)結(jié)點(diǎn)。(根所在結(jié)點(diǎn)為第1層)。20 .待排序的序列為8,3,4,1,2,5,9,采用直接選擇排序算法，當(dāng)進(jìn)行了兩趟選擇后，結(jié)果序列為 .。21 .設(shè)有一個(gè)長(zhǎng)度為40的順序表，要?jiǎng)h除第8個(gè)元素

49、需移動(dòng)元素的個(gè)數(shù)為 。22 .線性表用 方式存儲(chǔ)可以隨機(jī)訪問(wèn)。23 .有以下程序段char a ="English "char *p=a; int n=0;while( *p!='0 ' ) n+; p+;結(jié)果中，n 的值是。24 .順序表，,6, 5, 1,2, 4, 3, 8, 7經(jīng)過(guò)一趟(1,1)歸并后的結(jié)果序列為 。三、綜合題1 .有一個(gè)長(zhǎng)度為 11的有序表(1,2, 11, 15, 24, 28, 30, 56, 69, 70, 80),元素的下標(biāo)依次為1.3.3, ，11,按折半查找對(duì)該表進(jìn)行查找。(1)畫(huà)出對(duì)上述查找表進(jìn)行折半查找所對(duì)應(yīng)的判定樹(shù)

50、。(2)說(shuō)出成功查找到元素56,需要依次經(jīng)過(guò)與哪些元素的比較？(3)說(shuō)出不成功查找元素72,需要進(jìn)行元素比較的次數(shù)？2 .設(shè)查找表為序號(hào)1234567891011序列81622234159698189901213 1)畫(huà)出對(duì)上述查找表進(jìn)行折半查找所對(duì)應(yīng)的判定樹(shù)。4 2)說(shuō)明成功查找到元素90需要經(jīng)過(guò)多少次比較？5 3)說(shuō)明不成功查找元素82,依次與哪些元素進(jìn)行了比較，需要經(jīng)過(guò)多少次比較？6 . (1) 一組記錄的關(guān)鍵字序列為(57, 90, 67, 50, 51, 56),利用堆排序(堆頂元素是 最小元素)的方法建立初始堆(要求以完全二叉樹(shù)描述)。(2)對(duì)關(guān)鍵字序列(56,51,71,54,4

51、6,106)利用快速排序，以第一個(gè)關(guān)鍵字為分割元素，給出經(jīng)過(guò)一次劃分后結(jié)果。(3) 一組記錄的關(guān)鍵字序列為(60,47 , 80, 57, 39, 41, 46,30 ),利用歸并排序的方法，分別給出(1,1)歸并、(2,2)歸并、(4,4)歸并的結(jié)果序列。7 .(1) 一組記錄的關(guān)鍵字序列為(36, 69, 46, 28, 30, 35),給出利用堆排序(堆頂元素是最小元素)的方法建立的初始堆(要求以完全二叉樹(shù)描述)。(2)對(duì)關(guān)鍵字序列(36,69,46,28,30,74)采用快速排序，給出以第一個(gè)關(guān)鍵字為分割元素，經(jīng)過(guò)一次劃分后的結(jié)果。(3)設(shè)有數(shù)據(jù)集合30,73,101,4,8,9,2,81,依次取集合中各數(shù)據(jù)構(gòu)造一棵二叉排序樹(shù)。四、程序填空題1 .設(shè)線性表為(16, 20, 26, 24),以不帶頭結(jié)點(diǎn)的單向鏈表存儲(chǔ)，鏈表頭指針為head,以下程序的功能是輸出鏈表中各結(jié)點(diǎn)中的數(shù)據(jù)域 dataStruct nodeint data;struct node *next;typedef struct node NODE;#define NULL