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

1、數(shù)據(jù)結(jié)構(gòu)本期末綜合練習(xí)綜合練習(xí)一一、單項選擇題1 .設(shè)有頭指針為head的帶有頭結(jié)點的非空單向循環(huán)鏈表,指針p指向其尾結(jié)點,要刪除頭結(jié)點,并使其仍為單 向循環(huán)鏈表,那么可利用下述語句head=head-next ;.A. p =head;B. p=NULL; C. p-next =head; D. head=p;2 .在一個單鏈表中p指向結(jié)點a, q指向結(jié)點a的直接后繼結(jié)點b,要刪除結(jié)點b,可執(zhí)行.A. p*next=q-next ;B. p=q-next;C. p-next=q;D. p-next=q;3 .以下說法不正確的選項是A.線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)不必占用連續(xù)的存儲空間B. 一種邏輯結(jié)

2、構(gòu)只能有唯一的存儲結(jié)構(gòu)C. 一種邏輯結(jié)構(gòu)可以有不同的存儲結(jié)構(gòu)D.線性表的順序存儲結(jié)構(gòu)必須占用連續(xù)的存儲空間4 .在一個單向鏈表中,在P所指結(jié)點之后插入一個s所指的結(jié)點時,可執(zhí)行；和p-next=s;A. p= s;B. p-next=s-next;C. p=snext;D. s*next=pnext;5 .把數(shù)據(jù)存儲到計算機(jī)中,并具體表達(dá)稱為物理結(jié)構(gòu).A.數(shù)據(jù)元素間的邏輯關(guān)系B.數(shù)據(jù)的處理方法C.數(shù)據(jù)的性質(zhì)D.數(shù)據(jù)的運算6.設(shè)有一個長度為23的順序表,要刪除第8個元素需移動元素的個數(shù)為.A. 16 B. 14 C. 157 .鏈表所具備的特點之一是 oA.可以隨機(jī)訪問任一結(jié)點C.插入元素的操作

3、不需要移動元素8 .設(shè)一棵有8個葉結(jié)點的二叉樹,度 個結(jié)點.D. 13B.需要占用連續(xù)的存儲空間D.刪除元素的操作需要移動元素 為1的結(jié)點有3個,那么該樹共有A. 20B. 18C. 17D. 169 .圖狀結(jié)構(gòu)中數(shù)據(jù)元素的位置之間存在的關(guān)系.B.多對多A. 一對一C. 一對多D.每一個元素都有一個直接前驅(qū)和一個直接后繼10 . 一棵具有5層的完全二叉樹,最后一層有4個結(jié)點,那么該樹總共有個結(jié)點.A. 14 B. 15C. 19D. 1811 .元素15, 9, 11, 13按順序依次進(jìn)棧,那么該棧的不可能輸出序列是進(jìn)棧出棧可以交替進(jìn)行.A. 13, 11, 9, 15B. 15, 9, 11

4、, 13C. 13, 11, 15, 9D. 9, 15, 13, 11A. EFaBeC. DABCC)o12 .設(shè)主串為FABcCDABcdEFaBc,以卜模式串能與主串成功匹配的是B. ABCdED FAbcC13 .設(shè)有一個14階的對稱矩陣A第一個元素為a,D,采用壓縮存儲的方式,將其下三角局部以行序為主序存儲到一維數(shù)組B中數(shù)組下標(biāo)從1開始,那么矩陣中元素a s在一維數(shù)組B中的下標(biāo)是.A. 9B. 10C. 11D. 814.元素111, 113, 115, 117按順序依次進(jìn)棧,那么該棧的不可能輸出序列是進(jìn)棧出棧可以交替進(jìn)行.A. 117, 115, 113,C. 113, 111

5、117,15.在一棵二叉樹中,A. 18111115B. Ill, 113, 115, 117D. 117, 115, 111, 113假設(shè)編號為8的結(jié)點存在右孩子,那么右孩子的順序編號為B. 16C. 15D. 17)oB.棧的特點是后進(jìn)先出D.隊列的特點是先進(jìn)先出那么該樹總共有個結(jié)點.C. 30D. 2816 .以下說法不正確的選項是oA.棧和隊列都是線性結(jié)構(gòu)C.棧和隊列的特點都是先進(jìn)后出17 .設(shè)一棵哈夫納樹共有11個非葉結(jié)點,B. 27A. 2918 .設(shè)有一個15階的對稱矩陣A第一個元素為采用壓縮存儲的方式,將其下三角局部以行序為主序存儲到一維數(shù)組B中數(shù)組卜標(biāo)從1開始,那么矩陣中元素

6、上,2在一維數(shù)組B中的下標(biāo)是 oA. 9B. 8C. 7D. 1019 .如圖1所示的一個圖,假設(shè)從頂點a出發(fā),按深度優(yōu)先搜索法進(jìn)行遍歷,那么可能得 到的一種頂點序列為.A. abecdfB. acfebdC. aebcfd D. aedbfc圖120.如圖2所示的一個圖,假設(shè)從頂點a出發(fā),按深度優(yōu)先搜索法進(jìn)行遍歷,那么可能得到的一種頂點序列為)oA. acedbfB. acebfdC. aebcfdD. aedfcb二、填空題1 .隊列的特點之一是：元素進(jìn)、出隊的次序是:先進(jìn).2 .序歹13,11,14,12,17,15,采用冒泡排序算法,經(jīng)一趟冒泡后,序歹U的結(jié)果是 o3 . 結(jié)構(gòu)中,數(shù)據(jù)

7、元素間存在一對多的關(guān)系.4 .對16個元素的序列用冒泡排法進(jìn)行排序,通常需要進(jìn)行 趟冒泡.5 .對稀疏矩陣進(jìn)行壓縮存儲,矩陣中每個非零元素對應(yīng)的三元組包括該元素的三項信息是 o6對9個元素的一組記錄(58, 35, 93, 20, 12, 78, 56, 41, 79)進(jìn)行直接插入排 序(由小到大排序),當(dāng)把第7個記錄56插入有序表,為尋找插入位置需比較次.7 .在對11個記錄的序列(12, 35,9,7,2, 11 ,56,95 ,37,58 ,60)進(jìn)行直接插入排序時,當(dāng)把第6個記錄11插入到有序表時,為尋找插入位置,元素間需比較 次.(由小到大排列)8 .結(jié)構(gòu)中的數(shù)據(jù)元素存在一對多的關(guān)系

8、稱為 結(jié)構(gòu).9 .哈希函數(shù)是記錄關(guān)鍵字的值與該記錄 之間所構(gòu)造的對應(yīng)關(guān)系.10 .設(shè)有一棵深度為5的完全二叉樹,第5層上有3個結(jié)點,該樹共有 個結(jié)點.(根所在結(jié)點為第1層)11 . 20個元索進(jìn)行冒泡法排序,通常需要進(jìn)行19趟冒泡,其中第10趟冒泡共需要進(jìn)行 次元素間的比較.12 . 一棵二叉樹中每一個非葉結(jié)點的度數(shù)都為2,共有10個非葉結(jié)點,那么該樹共有個結(jié)點.13 . 一棵有19個結(jié)點的二叉樹,采用鏈?zhǔn)浇Y(jié)構(gòu)存儲,該樹結(jié)構(gòu)中有 個指針 域為空.14 .序列3,1,7,18,6,9,13,12經(jīng)一趟歸并排序的結(jié)果為,15 .中序遍歷一棵 樹可得到一個有序序列.16 . 一棵有16個葉結(jié)點的哈夫

9、曼樹,那么該樹共有 個非葉結(jié)點.17 .二叉排序樹插入操作中,新插入的結(jié)點總是以樹的 結(jié)點被插入的18 . 遍歷二叉排序樹可得到一個有序序列.19 .廣義表的(a , (d,a ,b),h, (e ,(i ,j )上)深度是 020 廣義表(f,h,(a,b, d,c),d,e,(i j)Jc)的長度是.2L序列4,2,5,3,8,6,7, 9,采用歸并排序算法(升序),經(jīng)一趟歸并后戶列的結(jié)果22 .廣義表的h,c, &a,仆,1,3山上深度是23 .字符串 al= teijing* , a2 = tef , a3= *teifang* ,a4= *tefi* 最小的是.24 .設(shè)有串 pl=

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

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

12、9182560728455595. (1)以1, 2, 3 , 6, 7, 8作為葉結(jié)點的權(quán),構(gòu)造一棵哈夫曼樹 (2)給出具有相應(yīng)權(quán)重值的葉結(jié)點的哈夫曼編碼.四、程序填空題1 .以下函數(shù)在a0到an-l中,用折半查找算法查找關(guān)鍵字等于k的記錄,查找成功返回該記錄的下標(biāo),失敗時 返回1,完成程序中的空格typuduf struct int key；N()DE;int Binary_Scarch(N()DE a, int n, int k)int low, mid, high;low=0;high=n-l;whilc( (1)mid=( (2)if(amid.kcy=k)return (3);el

13、se if ()low=mid+l;else ；return -11. (1) I ow=h i gh(2) ( lo/high)/2(3) mid;(4) a m i d. keydata (2) p=p-next (3) p!=NULL3 .以卜程序是前序遍歷二叉樹的遞歸算法的程序,完成程序中空格局部(樹結(jié)構(gòu)中左、 右指針域分別為left和nght,數(shù)據(jù)域data為字符型,BT指向根結(jié)點).void Inorder (stmct BTreeNode *BT)(if(BT!=NULL);；Inorder(BT right);)利用上述程序?qū)τ覉D進(jìn)行前序遍歷,結(jié)果是(3);3.(1) prin

14、tf( a%c ,BT-data)(2) Inorder(BT-left)(3) a b d f e c4 .以卜.程序走后序遍歷二叉樹的遞歸算法的程序,完成程序中空格局部(樹結(jié)構(gòu)中左、 右指針域分別為left和right,數(shù)據(jù)域data為字符型,BT指向根結(jié)點).完成程序中 空格局部.void Inorder (stmct BTreeNode *BT) (if( BT!=NULL)Inorder(BT-left); )5 .(1) Inorder(BT-right) (2) printf( %c , BT-data)6 .順序查找算法如下,完成程序中空格局部.mt search (NODE

15、a ,int n , mt k)/*在中查找關(guān)鍵字等于k的記錄,行找成功返回記錄的卜標(biāo),失 敗時返回-1/ int 1=0;while( inext =NULLB. p=NULL C. p-next= =head D. p= =head2 .數(shù)據(jù)的存儲結(jié)構(gòu)包括數(shù)據(jù)元素的表示和oA .數(shù)據(jù)處理的方法C .相關(guān)算法D.數(shù)據(jù)元素的類型D.數(shù)據(jù)元素間的關(guān)系的表示3 . 一種邏輯結(jié)構(gòu) oA.可以有不同的存儲結(jié)構(gòu)B.只能有唯一的存儲結(jié)構(gòu)C.是指某一種數(shù)據(jù)元索之間的存儲關(guān)系D.是指某一種數(shù)據(jù)元索的性質(zhì)4.在一個頭指針為head的單向鏈表中,p指向尾結(jié)點,要使該鏈表成為單向循環(huán)鏈表 可執(zhí)行 oB. headn

16、ext=p;D. p-next=head;B.占用連續(xù)的存儲空間A. p= head-next;C. head-next=p-next;5 .鏈表所具備的特點之一是 oA.可以隨機(jī)訪問任一結(jié)點C.插入刪除元素的操作不需要移動元索結(jié)點D.可以通過卜標(biāo)對鏈表進(jìn)行直接訪問6 .元素111, 113, 115, 117按順序依次進(jìn)棧,那么該棧的不可能輸出序列是進(jìn)棧出?？梢越惶孢M(jìn)行.A. 117, 115, 113, 111B. 111, 113, 115, 117C. 117, 115, 111, 113D. 113, 111, 117, 1157 .線性結(jié)構(gòu)中數(shù)據(jù)元素的位置之間存在的關(guān)系.A. 一對

17、一B. 一對多C.多對多D.每一個元素都有一個直接前驅(qū)和一個直接后繼8 .以下說法正確的選項是.A.棧的特點是先進(jìn)后出B.棧的特點是先進(jìn)先出C.隊列的特點是先進(jìn)后出D.枝和隊列的特點都是先進(jìn)后出9 .在一個單向鏈表中p所指結(jié)點之后插入一個s所指的結(jié)點時,可執(zhí)行.A. p-next= s; s-next= p-next B. p-next=snext;C. p=s-nextD s-next=p-next; pnext=s;10 .設(shè)有一個20階的對稱矩陣A第一個元素為ar,采用壓縮存儲的方式,將其下三角局部以行序為主序存儲到一維數(shù)組B中數(shù)組卜標(biāo)從1開始,那么矩陣中元索aa2在一維數(shù)組B中的下標(biāo)是

18、A. 24B. 17C. 16D. 2311 .元索11, 13, 15, 17按順序依次進(jìn)棧,那么該棧的不可能輸出序列是進(jìn)棧出?？梢越惶孢M(jìn)行.A. 17, 15, 13, 11B, 11, 13, 15, 17C. 17, 15, 11, 13D. 13, 11, 17, 1512 .設(shè)一棵有2n+l個結(jié)點的二叉樹,除葉結(jié)點外每個結(jié)點度數(shù)都為2,那么該樹共有 個葉結(jié)點.A. nB. n+1I C. n+2D. nl13 .設(shè)有一個20階的對稱矩陣A第一個元素為采用壓縮存儲的方式,將其下三角局部以行序為主序存儲到一維數(shù)組B中數(shù)組下標(biāo)從1開始,那么矩陣中元素郎,2在一維數(shù)組B中的下標(biāo)是 oA.

19、11B. 12C. 13D. 1014 .如圖1所示的一個圖,假設(shè)從頂點a出發(fā),按廣度優(yōu)先搜索法進(jìn)行遍歷,那么可能得到的一種頂點序列為)oA. abecdfaebcfdD. aedfcbB. aecbdfC.15,設(shè)一棵哈夫曼樹共存11個非葉結(jié)點,那么該樹有A. 2216.線性表以B. 10C. 11個葉結(jié)點.D. 12方式存儲,能進(jìn)行折半查找.A.關(guān)健字有序的順序B.順序C.17. 一棵具有38個結(jié)點的完全二叉樹,最后一層有鏈接D.二叉樹 個結(jié)點.A. 7B. 5C. 618. 一棵具有38個結(jié)點的完全二叉樹,最后一層有A. 7B. 5C. 6D. 3)個結(jié)點.D. 8)o19.如圖2所示的

20、,個圖,假設(shè)從頂點a出發(fā),按深度優(yōu)先搜索法進(jìn)行遍歷,那么可能得到的一種頂點序列為A. abecdfB. acfebdC. aebcfdD. aedfcb20 .對一個棧頂指針為top的鏈棧進(jìn)行出戰(zhàn)操作.用變量e保存棧頂元素的值,那么執(zhí)行()oA. e= top-next; top-data=e;C. e=top-data; top=top-next;B. top=top-next, e=top-data;D. top=top-next; e=data;二、填空題1.字符串 al= BEIJING , a2 = BEF , a3= BEFANG* , al= BEI最小的是 o2 .數(shù)組a經(jīng)初始

21、化char a=English ； a7中存放的是 字符串的結(jié)束符.3 .把數(shù)據(jù)存儲到計算機(jī)中,并具體表達(dá)數(shù)據(jù)元素間的邏輯結(jié)構(gòu)稱為物理結(jié)構(gòu)(存儲結(jié)構(gòu),4 .設(shè)有串 pl二 ABADF,P2二 ABAFD,P3二 ABADFA P4= ABAF,四個串中最大的是5 .設(shè)有一個長度為22的順序表,要刪除第8個元素需移動元素的個數(shù)為.6 .在一棵二叉樹中,假設(shè)編號為i的結(jié)點存在右孩子,那么右孩子的順序編號為 o7 .在一棵二叉樹中,假設(shè)編號為i的結(jié)點存在左孩子,那么左孩子的順序編號為 o8 .設(shè)有一個長度為20的順序表,要插入一個元素,并作為第8個元素.需移動元素的個數(shù)為.9 .設(shè)一棵有n個葉結(jié)點的

22、二叉樹,除葉結(jié)點外每個結(jié)點度數(shù)都為2,那么該樹共有 個結(jié)點.10 .結(jié)構(gòu)中的數(shù)據(jù)元素存在多對多的關(guān)系稱為 結(jié)構(gòu).11 .在對一組序列(45,29,87,12,6,63,55,37,78)進(jìn)行直接插入排序時,當(dāng)把第8個記錄列插入到有序表時,為尋找插入位置需比較 次.(由小到大排序)12 .設(shè)有一棵深度為4的完全二叉樹,第四層上有5個結(jié)點,該樹共有 個結(jié)點.(根所在結(jié)點為第1層)13 . n個元素進(jìn)行冒泡法排序,通常需要進(jìn)行 趟冒泡.14 . 一棵二叉樹中有n個非葉結(jié)點,每一個非葉結(jié)點的度數(shù)都為2,那么該樹共有 個葉結(jié)點.15 . 一棵有21個結(jié)點的哈夫曼樹,該樹中有 個葉結(jié)點.16 .在對一組記

23、錄(55,39,97,22,16,73,65,47,88)進(jìn)行直接插入排序時,當(dāng)把第7個記錄65插入到有序表時,為尋找插入位置需比較 次.(由小到大排序17 . 遍歷二叉排序樹可得到一個有序序列.18 . n個元素進(jìn)行冒泡法排序,第J趟冒泡要進(jìn)行 次元素間的比較.19 .廣義表(a,(a,b),d,e,(ij)Jc)的長度是20 . 一棵有n個葉結(jié)點的哈夫曼樹,那么該樹共有 個結(jié)點.21 .廣義表的(a , (a ,b), d , e ,(I j ) ,k)深度是.22 .中序遍歷 可得到一個有序序列.23 .序列14,12,15,13,18,16,采用冒泡排序算法(升序),經(jīng)一趟冒泡后,序列

24、的結(jié)果是 O24 . r 義表(a ,b), d, e ,(i ,j) ,k)的長度是.三、綜合題1. .設(shè)查找表為(7,15,21,22,40,58,68,80,88,89,120),元素的下標(biāo)依次為 1,2,3,11(1)畫出對上述查找表進(jìn)行折半查找所對應(yīng)的判定樹(樹中結(jié)點用卜標(biāo)表示)(2)說明成功查找到元素40需要經(jīng)過多少次比較(3)求在等概率條件下,成功查找的平均比較次數(shù)2. (1)設(shè)有數(shù)據(jù)集合40, 29, 7, 73, 101, 4, 55, 2, 81, 92, 39,依次取集合 中各數(shù)據(jù)構(gòu)造一棵二叉排序樹.(2)一組記錄的關(guān)鍵字序列為(5, 8, 6, 3, 4, 7),利用堆

25、排序(堆頂元素走最 小元素)的方法建立初始堆.(要求用完全二叉樹表示)3. (1) 一組記錄的關(guān)鍵字序列為(47, 80, 57, 39, 41. 46),給出利用堆排序(堆頂 元素是最小元素)的方法建立的初始堆(要求以完全二叉樹描述)o(2)對關(guān)鍵字序列(47, 80, 57, 39, 41, 85)采用快速排序,給出以第一個關(guān)健字為分割 元素,經(jīng)過一次劃分后的結(jié)果.(3)如圖3所示的二叉樹,給出其前序遍歷序列.圖34. (1)以2, 3, 4, 7, 8, 9作為葉結(jié)點的權(quán),構(gòu)造一棵哈夫曼樹(2)給出上述哈夫曼樹葉結(jié)點的哈夫曼編碼.(3)一組記錄的關(guān)鍵字序列為(37, 70, 47, 29

26、, 31, 85),利用快速排序,以第一 個關(guān)鍵字為分割元素,給出經(jīng)過一次劃分后結(jié)果.(由小到大排序)四、程序填空題1.以下程序是中序遍歷二叉樹的遞歸算法的程序,完成程序中空格局部樹結(jié)構(gòu)中左、右指針域分別為left和right,數(shù)據(jù)域data為字符型,BT指向根結(jié)點.void Inorder stnict BTreeNode *BTifBT!=NULLIiiorderBT（1） ；（2） ；利用上述程序?qū)τ覉D進(jìn)行中序遍歷,結(jié)果是3四、程序填空題1.(1) printf( ,BT-data)(2) Inorder (BT-right)(3) dbeafc2.設(shè)線性表為(6, 10, 16, 4)

27、,以卜程序用說明結(jié)構(gòu)變量的方法建立單向鏈表,并輸出鏈表中各結(jié)點中的數(shù)據(jù). #defhie NULL 0 void main()NODE a,b,c,d,*head,*p;a.data=6;b.data=10;c.data=16;d.data=4; /*d 是尾結(jié)點*/ head= (1); a.next=&b;b.next=&c;c.next=&d;(2)； /*以上結(jié)束建表過程*/p=head;/*p為工作指針,準(zhǔn)備輸出鏈表*/ do(printf(fcfc%dnM, (3 );(4) ; while( (5);)2.(1) &a(2) d-next=NULL(3) p-data(4) p=

28、p-next(5) p!=NULL3.以下冒泡法程序?qū)Υ娣旁赼2,an中的序列進(jìn)行排序,完成程序中的空格局部,其中n是元素個數(shù),要求按升序排列.a , int n)void bsort (NODE NODE temp;int i, j, flag;for(j=l; (1)flag=0;for(i=l; (2);i+)if (a_i. keyai+lj. key)Iflag=l;temp=a_i;_L32；(4)；)if(flag= =0)break;)程序中flag的功能是(5)3.(1) (4) 當(dāng)某趟冒泡中沒有出現(xiàn)交換那么已排好序,結(jié)束循環(huán)j=n-1 i right);)利用上述程序?qū)τ覉D

29、進(jìn)行遍歷,結(jié)果是(3)4.(1)(2) printf (, BT-data)bedafc綜合練習(xí)二答案一、單項選擇題1. C 2. D 3. A 4. D 5. C 6. C 7. A 8. A 9. D 10. B 11. 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)存儲結(jié)構(gòu)4. p25. 146. 2i+l7. 218. 139. 2n-l10. 圖狀11. 512. 1213. nl14. n+115. 1116. 317. 中序18. n-j19. 520. 2n-l

30、21. 322. 二叉排序樹23, 12,14,13,15,16,1824. 4圖83(1)39, 41, 46, 80, 47, 57圖9(2) 41, 39, 47, 57, 80, 85(3)abdefcg圖10(2)2： 00004 00015 0018 109 1110 01 (3) 31,29,37,47,70,85綜合練習(xí)三一、單項選擇題1 .數(shù)據(jù)的存儲結(jié)構(gòu)包括數(shù)據(jù)元素的表示和.A .數(shù)據(jù)處理的方法B.數(shù)據(jù)元素的類型C .相關(guān)算法D.數(shù)據(jù)元素間的關(guān)系的表示2 .設(shè)有頭指針為head的不帶頭結(jié)點的非空的單向循環(huán)鏈表,指針p指向其尾結(jié)點,要 刪除第一個結(jié)點,那么可利用下述語句head

31、=head-next;和.A. p ;head; B. p=NULL; C. p-next =head; D. head=p;3 .樹狀結(jié)構(gòu)中數(shù)據(jù)元素的位置之間存在的關(guān)系.A.每一個元素都有一個直接前驅(qū)和一個直接后維B. 一對一C.多對多D. 一對多4 .以下說法正確的選項是 oA.線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)必須占用連續(xù)的存儲空間B. 一種邏輯結(jié)構(gòu)可以有不同的存儲結(jié)構(gòu)C. 一種邏軾結(jié)構(gòu)只能有唯一的存儲結(jié)構(gòu)D.線性表的順序存儲結(jié)構(gòu)不必占用連續(xù)的存儲空間5 .設(shè)有一個長度為26的順序表,要插入一個元素,并使它成為新表的第6個元素,需移動元素的個數(shù)為.A. 21B. 22C. 20D. 196 .把數(shù)據(jù)存

32、儲到計算機(jī)中,并具體表達(dá)稱為物理結(jié)構(gòu).A.數(shù)據(jù)的處理方法B.數(shù)據(jù)的性質(zhì)C.數(shù)據(jù)的運算D.數(shù)據(jù)元素間的邏輯關(guān)系7 .頭指針為head的帶頭結(jié)點的單向循環(huán)鏈表,p所指向尾結(jié)點,要使該鏈表成為 不帶頭結(jié)點的單向循環(huán)鏈表,可執(zhí)行head二head-nex;和.A. p= head-nextC. head-next=p-next8.順序表所具備的特點之一是A.可以隨機(jī)訪問任一結(jié)點C.插入元素的操作不需要移動元素B. head-next=pD. p-next=head;B.不需要占用連續(xù)的存儲空間D.刪除元素的操作不需要移動元素9.元素111, 113, 115, 117按順序依次進(jìn)棧,那么該棧的不可能輸

33、出序列是進(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. 一對一B. 一對多C.多對多D.每一個元素都有一個直接前驅(qū)和一個直接后繼11 .以下說法正確的選項是.A.棧的特點是先進(jìn)先出B.棧的特點是先進(jìn)后出C.隊列的特點是先進(jìn)后出12,元素20, 14, 16, 18按順序依次進(jìn)棧,那么該棧的不可能輸出序列是進(jìn)棧出棧可以交替進(jìn)行.A. 18, 16, 14, 20B. 20, 14, 16, 18C. 1

34、8, 16, 20, 14D. 14, 20, 18, 16D.棧和隊列的特點都是后進(jìn)后出13 .設(shè)有一個20階的對稱矩陣A笫一個元素為aj,采用壓縮存儲的方式,將其下三 角局部以行序為主序存儲到一維數(shù)組B中數(shù)組卜標(biāo)從1開始,那么矩陣元素a 在一維數(shù)組B中的下標(biāo)是 oA. 21B. 17C. 28D. 2314 .設(shè)有一個12階的對稱矩陣A左上角第一個元索為采用壓縮存儲的方式,將其卜.三角局部以行序為)o)o主序存儲到一維數(shù)組B中數(shù)組下標(biāo)從1開始,那么矩陣中元素a幣在一維數(shù)組B中的下標(biāo)是A. 14B. 12C. 13D. 1115 .設(shè)有串 pl=w ABADF,P2二 ABAFD,P3二 A

35、BADFA,P4= ABAF ,以下四個串中最大的是A. p3B. p2 C. plD. p416 .設(shè)有一個長度為22的順序表,要刪除第8個元素需移動元素的個數(shù)為 oA. 25B. 1417.數(shù)組a經(jīng)初始化char aA.字符串的結(jié)束符C.C. 15 D. 23=English ； a7中存放的是(B.字符hD.變量h)o18 .在一棵二叉樹中,假設(shè)編號為5的結(jié)點存在右孩子,那么右孩子的順序編號為oA. 12B. 9 C. 11D. 1019 .設(shè)主串為ABcCDABcdEFaBc,以卜模式串能與主串成功匹配的是.A. Bed B. BCdC. ABCD. Abe20 . 一棵具有5層的完全

36、二叉樹,最后一層有4個結(jié)點,那么該樹總共有個結(jié)點.A. 14B. 15C. 19D. 1821 .在一棵.二叉樹中,假設(shè)編號為i的結(jié)點存在左孩子,那么左孩子的順序編號為.A. 2i+lB. 2i-lC. 2iD. 2i+222 .如圖1所示,假設(shè)從頂點a出發(fā),按圖的廣度優(yōu)先搜索法進(jìn)行遍歷,那么可能得到的一種 頂點序列為A. abcdfgeB. abcedfg C. aebfedg D. abcfgde圖123 .如圖2所示,假設(shè)從頂點a出發(fā),按圖的廣度優(yōu)先搜索法進(jìn)行遍歷,那么可能得 到的一種頂點序列為0A. abecdfB. aecbdfC. aebefd D. aedfebec圖224.字符

37、串a(chǎn)bcd321ABCD的子串是)oA. 21ABCB. abcABCDC. abcDD. 321a25 .線性表以方式存儲,能進(jìn)行折半查找.A.鏈接 B.順序 C.關(guān)鍵字有序的順序 D.二叉樹26 .數(shù)組a經(jīng)初始化char aEnglish ; al中存放的是.A.字符nB.字符EC. %D. E27 . 一棵具有38個結(jié)點的完全二叉樹,最后一層有個結(jié)點.A. 7B. 5C. 6D. 828 .如圖3所示,假設(shè)從頂點a出發(fā),按圖的深度優(yōu)先搜索法進(jìn)行遍歷,那么可能得到的一種頂點序列為 oA. abecdfB. acfebd29.卜圖的拓?fù)湫虼?是(A. 5 2 3 4 6C. 5 6 2 3

38、4.C. aebcfdD. aedfcb30.以下圖的拓?fù)湫蛄惺?A. 5234GC.56423B. 5 2 36 4D. 2 3 45 6二、填空題1 .結(jié)構(gòu)中的數(shù)據(jù)元素存在多對多的關(guān)系稱為 結(jié)構(gòu).2 .棧的特點之一是：元素進(jìn)、出棧的次序是:先進(jìn) 03 . n個元素進(jìn)行冒泡法排序,第J趟冒泡要進(jìn)行次元素間的比較.4 .對稀疏矩陣進(jìn)行壓縮存儲,矩陣中每個非零元素對應(yīng)的三元組包括該元素的三項信息是 O5 .中序遍歷 樹可得到一個有序序列.6 .在對10個記錄的序列(9, 35,19, 77 ,2, 10 ,53,45,27,68)進(jìn)行直接插入排序時,當(dāng)把第6個記錄10插入到有序表時,為尋找插入位

39、置,元素間需比較 次.(按升序排序)7 .待排序的序列為8,341,2,5,9,采用直接選擇排序算法,當(dāng)進(jìn)行了兩趟選擇后,結(jié)果序列為()o8 .字符串 al= beijing* , a2 = bef* , a3= beifang , a4= befi 最小的 是.9 .廣義表(a ,b), d , e ,(i J )、k)的長度是.10 . 10個元索進(jìn)行冒泡法排序,其中第5趟冒泡共需要進(jìn)行 次元索間的比較.11.廣義表的(c, a,(a ,b),d,e ,(i J ) ,k)深度是.12 . 遍歷一棵二叉排序樹可得到一個有序序列.13 .灼稀疏矩陣進(jìn)行壓縮存儲,可采用三元組表,一個有10行1

40、0列的稀疏矩因A共行95個零元素,其相應(yīng)的 三元組表共有 個元素.14 .廣義表(c ,(a ,b,c) ,(d,e,f),(ij)Jc)的長度是.15 .在對一組記錄(50, 49, 97, 22, 16,73, 65, 47, 88)進(jìn)行直接插入排序時,當(dāng)把第7個記錄65插入到有序表時, 為尋找插入位置需比較 次.16 .廣義表的(c , (b,a ,b), f, e ,( (i j ) ,k)深度是.17 . 一棵有5個葉結(jié)點的哈夫曼樹,該樹中總共有個結(jié)點.18 .序列4,2,5,3,8, 6,采用冒泡排序算法(升序),經(jīng)一趟冒泡后,結(jié)果序列是 .19 .設(shè)有一棵深度為4的完全二叉樹,第

41、四層上有5個結(jié)點,該樹共有 個結(jié)點.(根所在結(jié)點為第1層).20 .待排序的序列為8,341,2,5,9,采用直接選擇排序算法,當(dāng)進(jìn)行了兩趟選擇后,結(jié)果序列為.021 .設(shè)有一個長度為40的順序表,要刪除第8個元素需移動元素的個數(shù)為 o22 .線性表用 方式存儲可以隨機(jī)訪問.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)過一趟(1,1)歸并后的結(jié)果序列為.三、綜合題1 .有一個長度為11的有序表(1,2,11, 15,24,28,30,56,69,70,80),元素的下標(biāo)依次為1.3.3, ,1b按折半查找對該表進(jìn)行查找.(1)商出對上述查找表進(jìn)行折半查找所對此的判定樹.(2)說出成功查找到元素56需要依次經(jīng)過與哪些元素的比較(3)說出不成功查找元素72,需要進(jìn)行元素比較的次數(shù)2 .設(shè)查找表