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

1、. z.數(shù)據(jù)構(gòu)造本期末綜合練習(xí)綜合練習(xí)一一、單項選擇題1.對稀疏矩陣進(jìn)展壓縮存儲,可采用三元組表，一個10 行8列的稀疏矩陣A共有73 個零元素，其相應(yīng)的三元組表共有( C )個元素。 A8 B80 C7 D10 2. 對稀疏矩陣進(jìn)展壓縮存儲,可采用三元組表，一個10 行8列的稀疏矩陣A，其相應(yīng)的 三元組表共有6個元素，矩陣A共有( C )個零元素。A8 B72 C74 D10 3.字符串( A )是abcd321ABCD的子串。A. 21AB B. abcDC. aBCD D. 321a 4. 程序段 char a =abdcacdef; char *p=a; int n=0; while(

2、 *p!=0) n+; p+; 結(jié)果中,n的值是 D A. 6 B.8 C. 7 D.9 5.棧和隊列的共同特點(diǎn)是 A 。 A都是操作受限的線性構(gòu)造 B元素都可以隨機(jī)進(jìn)出 C都是先進(jìn)后出 D都是先進(jìn)先出 6. 10,6,2,1按順序依次進(jìn)棧，該隊列的可能輸出序列是 A 。 (進(jìn)棧出?？梢越惶孢M(jìn)展。 A6,10,1,2 B2,10,6,1 C6,1,10,1 D1,6,10,27. 在一個鏈隊中，假設(shè)f和r分別為隊頭和隊尾指針，p指向一個新結(jié)點(diǎn),要為結(jié)點(diǎn)p所指結(jié)點(diǎn)賦值*,并入隊的運(yùn)算為p-data=*; p-ne*t=NULL; B 。 A. f-ne*t=p; f=p; B r-ne*t=p;

3、r=p;C r=p; p-ne*t=r; D p-ne*t=f;f=p;8. 對一個棧頂指針為top的鏈棧進(jìn)展出棧操作，用變量e保存棧頂元素的值 ，則執(zhí)行 ( B 。 Ae= top-ne*t; top-data=e; Be=top-data; top=top-ne*t; Ctop=top-ne*t; e=top-data; Dtop=top-ne*t; e=data; 9. 數(shù)據(jù)構(gòu)造中，與所使用的計算機(jī)無關(guān)的是數(shù)據(jù)的( A ) 構(gòu)造。A.邏輯 B.存儲 C.邏輯與存儲 D.物理 10. 算法的時間復(fù)雜度與( A )有關(guān)。 A. 算法本身 B. 所使用的計算機(jī)C. 算法的程序設(shè)計 D. 數(shù)據(jù)構(gòu)

4、造11順序表所具備的特點(diǎn)之一是 A 。 A可以隨機(jī)訪問任一結(jié)點(diǎn) B不需要占用連續(xù)的存儲空間 C插入元素的操作不需要移動元素 D刪除元素的操作不需要移動元素12在一個單向鏈表中,在p所指結(jié)點(diǎn)之后插入一個s所指的結(jié)點(diǎn)時，可執(zhí)行 s-ne*t=p-ne*t; 和 D 。 Ap= s; B p-ne*t=s-ne*t; Cp=s-ne*t D p-ne*t=s; 13. 數(shù)據(jù)元素是數(shù)據(jù)的根本單位，它 C 。 A只能有一個數(shù)據(jù)項組成 B至少有二個數(shù)據(jù)項組成 C可以是一個數(shù)據(jù)項也可以由假設(shè)干個數(shù)據(jù)項組成 D至少有一個數(shù)據(jù)項為指針類型 14. 一種邏輯構(gòu)造在存儲時 C。A只要存儲數(shù)據(jù)元素間的關(guān)系 B只能采用

5、一種存儲構(gòu)造 C可采用不同的存儲構(gòu)造 D只要存儲數(shù)據(jù)元素的值 15設(shè)有頭指針為head的非空的單向鏈表, 指針p指向其尾結(jié)點(diǎn), 要使該單向鏈表成為單向循環(huán)鏈表,則可利用下述語句C 。 Ap =head; Bp=NULL; Cp-ne*t =head; Dhead=p; 16.單向鏈表所具備的特點(diǎn)是( C )。A.可以隨機(jī)訪問任一結(jié)點(diǎn) B.占用連續(xù)的存儲空間 C.插入刪除不需要移動元素 D.可以通過*結(jié)點(diǎn)的指針域訪問其前驅(qū)結(jié)點(diǎn) 17. 在線性表的順序構(gòu)造中，以下說法正確的選項是C 。 A邏輯上相鄰的元素在物理位置上不一定相鄰 B數(shù)據(jù)元素是不能隨機(jī)訪問的 C邏輯上相鄰的元素在物理位置上也相鄰 D進(jìn)

6、展數(shù)據(jù)元素的插入、刪除效率較高 18.數(shù)據(jù)構(gòu)造在計算機(jī)內(nèi)存中的表示是指 ( B ) 。 A數(shù)據(jù)元素之間的關(guān)系 B數(shù)據(jù)的存儲構(gòu)造 C數(shù)據(jù)元素的類型 D數(shù)據(jù)的邏輯構(gòu)造19.對鏈表, 以下表達(dá)中正確的選項是 A 。 A不能隨機(jī)訪問任一結(jié)點(diǎn) B結(jié)點(diǎn)占用的存儲空間是連續(xù)的 C插入刪除元素的操作一定要要移動結(jié)點(diǎn) D可以通過下標(biāo)對鏈表進(jìn)展直接訪問 20.下面關(guān)于線性表的表達(dá)中,錯誤的選項是( B )。 A . 線性表采用順序存儲,必須占用一片連續(xù)的存儲空間。 B. 線性表采用順序存儲,進(jìn)展插入和刪除操作,不需要進(jìn)展數(shù)據(jù)元素間的移動。 C. 線性表采用鏈?zhǔn)酱鎯?，不必占用連續(xù)的存儲空間。 D. 線性表采用鏈?zhǔn)酱?/p>

7、儲，進(jìn)展插入刪除操作，不需要移動元素21 .設(shè)有一個長度為35的順序表，要在第5個元素之前插入1個元素也就是插入元素 作為新表的第5個元素，則移動元素個數(shù)為B 。A30 B31 C. 5 D6 22 .設(shè)有一個長度為18的順序表，要在第5個元素之前插入1個元素也就是插入元素作為新表的第5個元素，則移動元素個數(shù)為B 。 A15 B14 C. 5 D6 23設(shè)有一個長度為40的順序表，要刪除第10個元素(下標(biāo)從1開場)需移動元素的個數(shù)為 C 。A11 B10 C30 D31 24設(shè)有一個長度為25的順序表，要刪除第10個元素(下標(biāo)從1開場)需移動元素的個數(shù)為 C 。 A10 B17 C15 D16

8、 25設(shè)有一個25階的對稱矩陣A，采用壓縮存儲的方式，將其下三角局部以行序為主序存儲到一維數(shù)組B中數(shù)組下標(biāo)從1開場，則矩陣中元素a7,5在一維數(shù)組B中的下標(biāo)是 C 。A25 B24 C26 D27 26設(shè)有一個18階的對稱矩陣A，采用壓縮存儲的方式，將其下三角局部以行序為主序存儲到一維數(shù)組B中數(shù)組下標(biāo)從1開場，則矩陣中元素a10,8在一維數(shù)組B中的下標(biāo)是 D 。A62, B63 C51 D53 27線性表在存儲后,如果相關(guān)操作中有要求:利用的指向*結(jié)點(diǎn)的指針或序號,訪問該結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，則采用A 的存儲方式是不可行的。A單向鏈表 B雙向鏈表 C單向循環(huán)鏈表 D順序表 28在一個尾指針為rear

9、的不帶頭結(jié)點(diǎn)的單循環(huán)鏈表中,插入一個s所指的結(jié)點(diǎn),并作為第一個結(jié)點(diǎn)，可執(zhí)行sne*t=rearne*t ;和 D 。 A rearne*t= sne*t; B rear =sne*t; C rear=s; D rearne*t=s;29在一棵二叉樹中，假設(shè)編號為i的結(jié)點(diǎn)存在左孩子,i結(jié)點(diǎn)的左孩子的順序編號為 B 。 Ai/2.0 B2*i C2*i+1 Di+2 30在一棵二叉樹中，假設(shè)編號為15的結(jié)點(diǎn)是其雙親結(jié)點(diǎn)的右孩子，則雙親結(jié)點(diǎn)的順序編號為D 。 A30 B8 C31 D7 二、填空題1. 廣義表( ( b,a,c) ,c ,d , f , e , ( (i , j ) , k ) )

10、的長度是_6_。2. 構(gòu)造中的元素之間存在一對多的關(guān)系是_樹形_構(gòu)造。3. 數(shù)據(jù)構(gòu)造中，數(shù)據(jù)元素之間的抽象關(guān)系稱為_邏輯_構(gòu)造。4. 構(gòu)造中的元素之間存在多對多的關(guān)系是 _圖狀_構(gòu)造 。5.棧的操作特點(diǎn)是后進(jìn)_先出_ 。 6.循環(huán)隊列的最大存儲空間為Ma*Size,假設(shè)隊頭指針front，隊尾指針rear，采用少用一個存儲空間以有效地判斷?？栈驐M，隊空的判定條件為_rear=front為真_。7. 廣義表( b,a,c) ,c ,d , f , e ,( (i , j ) , k ) ) 的表頭是_b,a,c_。8. 廣義表( ( b,a,c) ,c ,d , f , e , ( (i ,

11、j ) , k ) ) 的長度是_6_。9. 設(shè)有一個長度為18的順序表 , 第8號元素到第18號元素依次存放的值為8,9,18. *人想要刪除第8號元素，程序中他的做法是用語句for(i=18;i=9;i-)ai-1=ai; 即從第18號元素開場, 直到第9號元素,每個元素依次向前(左)移動1個位置.事實上這 樣做是錯誤的.其結(jié)果新表中第9號元素的值為_ 18 _。 10要求在n個數(shù)據(jù)元素中找值最大的元素，其根本操作為元素間的比擬。算法的時間復(fù)雜度為_O(n)_ 。11. 一棵二叉樹,有1個2度結(jié)點(diǎn),，2個1度結(jié)點(diǎn)，則該樹共有 _5_個結(jié)點(diǎn)。12一棵有8個葉結(jié)點(diǎn)的二叉樹，其1度結(jié)點(diǎn)的個數(shù)為3

12、，則該樹共有 _18_個結(jié)點(diǎn)。13設(shè)有一棵深度為5的完全二叉樹，該樹共有21個結(jié)點(diǎn),第5層上有6個結(jié)點(diǎn)。根所在結(jié)點(diǎn)為第1層 14.對于一棵具有n個結(jié)點(diǎn)的二叉樹，其相應(yīng)的鏈?zhǔn)酱鎯?gòu)造中共有_n+1_個指針域為空。15中序遍歷_二叉排序樹 _樹可得到一個有序序列。16. 對一組記錄5，8，9，2，12，7，56，44，39進(jìn)展直接插入排序(由小到大排序) ，當(dāng)把第6個記錄7插入有序表，為尋找插入位置需比擬_4_次。 17. 序列12,10,13,11,16,14,采用冒泡排序算法,經(jīng)一趟冒泡后,序列的結(jié)果是_ 10，12，11，13，14，16_。 按升序排序 18設(shè)有一棵深度為6的完全二叉樹，第

13、6層上有3個結(jié)點(diǎn)，該樹共有_34_個結(jié)點(diǎn)。根所在結(jié)點(diǎn)為第1層 19. 對16個元素的序列用冒泡排序法進(jìn)展排序，共需要進(jìn)展_ 15_趟冒泡。 20一棵有16個葉結(jié)點(diǎn)的哈夫曼樹，則該樹共有_31_個結(jié)點(diǎn)。21. 一棵有16個葉結(jié)點(diǎn)的哈夫曼樹，則該樹共有_15_個非葉結(jié)點(diǎn)。 22. 20個元素進(jìn)展冒泡法排序，通常第6趟冒泡要進(jìn)展_ _14_次元素間的比擬。 23. 在對一組記錄40，24，82，9，1，78，46，31，69進(jìn)展直接插入排序(由小到大排 序) ，當(dāng)把第7個記錄46插入到有序表時，為尋找插入位置需比擬_3_次。24對稀疏矩陣進(jìn)展壓縮存儲,可采用三元組表，一個6行7列的稀疏矩陣A共有38

14、個零 元素，其相應(yīng)的三元組表共有_4_個元素。 三、綜合題1設(shè)有序表為(5, 8, 14, 15, 33, 51, 61, 73, 81, 82, 93) ,元素的序號依次為 1,2,3,，11. 1畫出對上述查找表進(jìn)展折半查找所對應(yīng)的判定樹樹中結(jié)點(diǎn)可用序號表示 2說明成功查找到元素33需要經(jīng)過多少次比擬？ (3) 在等概率條件下, 給出成功查找的平均查找長度1圖4 51 14 81 5 15 61 82 8 33 73 93 (2) 4次 (3) ( 1+2*2+3*4+4*4)/11=33/11=32.設(shè)數(shù)據(jù)集合a=1,5,8,3,10,7,13,91依次取a中各數(shù)據(jù)，構(gòu)造一棵二叉排序樹。

15、2對該二叉樹進(jìn)展查找，成功查找到7要進(jìn)展多少次元素間的比擬？3給出對該二叉樹中序遍歷的序列。(1) 圖5 (2) 4次 (3) 中序遍歷 1, 3 , 5 ,7 , 8 , 9 , 10 , 133dcdceabfhe圖1(1) acdbfeh (2) 152364 或 152634 或 156234 (2)設(shè)有向圖如圖2所示下，寫出首先刪除頂點(diǎn)1的1種拓?fù)湫蛄?1234543465圖24設(shè)有序表為(30, 48, 58, 70, 78, 79, 90) ,元素的序號依次為 1,2,3,，7.1 畫出對上述查找表進(jìn)展折半查找所對應(yīng)的判定樹樹中結(jié)點(diǎn)用序號表示2 給出有序表中經(jīng)3次比擬成功查找到的

16、所有元素(3) 說明不成功查找元素59需要經(jīng)過多少次比擬？1圖6 70 48 79 30 58 78 90(2) 30 58 78 90 (3) 3次5.(1) 設(shè)數(shù)據(jù)集合a=7,4,9,8,6,5,3,依次取a中各數(shù)據(jù)，構(gòu)造一棵二叉排序樹。 (2)對該二叉樹進(jìn)展查找，成功查找到5要進(jìn)展多少次元素間的比擬？(3) 給出對上述二叉排序樹進(jìn)展中序遍歷的序列(1) 圖7(2) 4(3) 3,4,5,6,7,8,9 6(1) 如圖3所示，假設(shè)從頂點(diǎn)a出發(fā)，首先經(jīng)過c按廣度優(yōu)先搜索法進(jìn)展遍歷，給出可能得 到的一種頂點(diǎn)序列。2同圖3所示, 假設(shè)從頂點(diǎn)h出發(fā)，按深度優(yōu)先搜索法進(jìn)展遍歷，給出可能得到的2種頂點(diǎn)

17、 序列。aa阿decfhecdeccdeceec圖3 (3) 一組記錄的關(guān)鍵字序列為75，63，95，80，53，45，38，20，利用堆排序的方法建立小根堆(堆頂元素是最小元素,給出按篩選法建立的的初始堆。(1) acefdh (2) hdeacf hdfcae 3 20, 53，38，63，75，45，95，80四、程序填空題1以下函數(shù)在a0到an-1中，用折半查找算法查找關(guān)鍵字等于k的記錄，查找成功返回該記錄的下標(biāo)，失敗時返回-1，完成程序中的空格typedef struct int key;NODE;int Binary_Search(NODE a,int n, int k) int

18、low,mid,high; low=0; high=n-1; while(_(1)_) mid=(low+high)/2; if(amid.key=k) return _(2)_; else if(_(3)_) low=mid+1; else _(4)_; _(5)_; (1) low=high (2) mid (3) amid.key k (4) high=mid -1 (5) return -12以下函數(shù)為直接選擇排序算法，對a1,a2,an中的記錄進(jìn)展直接選擇排序，完成程序中的空格typedef struct int key; NODE;void selsort(NODE a ,int

19、n) int i,j,k; NODE temp; for(i=1;i= _(1)_;i+) k=i; for(j=i+1; _(2)_; j+) if(aj.keyak.key) _(3)_; if(i!=k) temp=ai;_(4)_; _(5)_; (1) n-1 (2) jdata=*; _(2)_; _(3)_; (1) sizeof(struct node)(2) pne*t=top (3) top=p4.以下函數(shù)為鏈隊列的入隊操作，*為要入隊的結(jié)點(diǎn)的數(shù)據(jù)域的值，front、 rear分別是鏈隊列的隊頭、隊尾指針struct node ElemType data;struct no

20、de *ne*t;struct node *front，*rear;void InQueue(ElemType *) struct node *p; p= (struct node*) _(1)_; p-data=*; p-ne*t=NULL; _(2)_; ; rear= _(3)_; (1) malloc(sizeof(struct node) (2) rear-ne*t=p; (3) rear=p;綜合練習(xí)二一、單項選擇題 1. 對稀疏矩陣進(jìn)展壓縮存儲,可采用三元組表，一個有10 行的稀疏矩陣A共有97個零元素，其相應(yīng)的三元組表共有3個元素。該矩陣A有( D )列。 A8 B9 C7 D

21、10 2 .單向鏈表所具備的特點(diǎn)是( C )。A.可以隨機(jī)訪問任一結(jié)點(diǎn) B.占用連續(xù)的存儲空間 C.插入刪除不需要移動元素 D.可以通過*結(jié)點(diǎn)的指針域訪問其前驅(qū)結(jié)點(diǎn) 3. 子串a(chǎn)cd在主串a(chǎn)bdcacdefac中的位置是( B ) 。 A3 B5 C7 D1 4 .設(shè)有一個長度為18的順序表，要在第6個元素之前插入一個元素也就是插入元素作為新表的第6個元素，則移動元素個數(shù)為 C 。 A12 B5 C. 13 D6 5. 序列12,16,8,4按順序依次進(jìn)棧，按該棧的可能輸出序列依次入隊列，該隊列的不可能輸出序列是 B 。 (進(jìn)棧、出?？梢越惶孢M(jìn)展。 A16,12,8,4 B4,8,12,16

22、C8,4,16,12 D16,12,4,8 6棧和隊列的共同特點(diǎn)是 A 。A都是線性構(gòu)造 B元素都可以隨機(jī)進(jìn)出C都是先進(jìn)后出 D都是先進(jìn)先出 7. 在一個不帶頭結(jié)點(diǎn)的鏈隊中，假設(shè)f和r分別為隊頭和隊尾指針，對該隊列進(jìn)展出隊 操作,并把結(jié)點(diǎn)的值保存在變量e中,其運(yùn)算為 C 。 Ae=f-data；r=r-ne*t; Be=f-data；r-ne*t=r; Ce=f-data；f=f-ne*t; De=f-data；f-ne*t=f; 8元素1，3，5，7按順序依次入隊列，按該隊列的出隊序列進(jìn)棧，該棧的可能輸出序列是 D 進(jìn)棧出棧可以交替進(jìn)展。 A7，5，1，3 B7，3，1，5 C5，1，3，7

23、 D7，5，3，1 9. 數(shù)據(jù)的邏輯構(gòu)造在計算機(jī)內(nèi)存中的表示是( B )。 A.給相關(guān)變量分配存儲單元 B.數(shù)據(jù)的存儲構(gòu)造 C.數(shù)據(jù)的邏輯構(gòu)造 D.算法的具體表達(dá) 10在一個不帶頭結(jié)點(diǎn)的鏈隊中，假設(shè)f和r分別為隊頭和隊尾指針，則對該隊列進(jìn)展出隊操作中并把結(jié)點(diǎn)的值保存在變量e中,其運(yùn)算為e=fdata；和 C 。 Ar=rne*t; Brne*t=r;Cf=fne*t; Dfne*t=f11. 以下說法正確的選項是( B )。 A. 線性表的鏈?zhǔn)酱鎯?gòu)造必須占用連續(xù)的存儲空間 B. 一種邏輯構(gòu)造可以有不同的存儲構(gòu)造 C一種邏輯構(gòu)造只能有唯一的存儲構(gòu)造 D線性表的順序存儲構(gòu)造不必占用連續(xù)的存儲空間

24、 12設(shè)有一個對稱矩陣A，采用壓縮存儲的方式，將其下三角局部以行序為主序存儲到一維數(shù)組B中數(shù)組下標(biāo)從1開場，B數(shù)組共有45個元素,則該矩陣是 D 階的對稱矩陣。A15 B11 C10 D9 13在一個單鏈表中要刪除p所指結(jié)點(diǎn)的后繼結(jié)點(diǎn)，可執(zhí)行q=p-ne*t; 和 A 。 Ap-ne*t=q-ne*t ; Bp=q-ne*t; Cp-ne*t=q; Dp-ne*t=q; 14. 以下是C語言中abcd321ABCD的子串的選項是 A 。A. 21ABC B.abcABCD C. abcD D. 321a 15. 在數(shù)據(jù)構(gòu)造和算法中，與所使用的計算機(jī)有關(guān)的是 B 。 A數(shù)據(jù)元數(shù)間的抽象關(guān)系 B數(shù)

25、據(jù)的存儲構(gòu)造 C算法的時間復(fù)雜度 D數(shù)據(jù)的邏輯構(gòu)造 16. 字符串a(chǎn)1=BEIJING,a2 =BEF, a3= BEFANG, a4=BEFI最小的是 B.A. a1 B. a2 C. a3 D. a4 17. 以下表中可以隨機(jī)訪問的是 D 。 A單向鏈表 B雙向鏈表 C單向循環(huán)鏈表 D順序表 18一棵有20個結(jié)點(diǎn)采用鏈?zhǔn)酱鎯Φ亩鏄渲?，共?A 個指針域為空。A21 B20 C19 D18 19.頭指針為head的不帶頭結(jié)點(diǎn)的單向鏈表為空的判定條件是邏輯表達(dá)式( A )為真。 A. head= =NULL B. head-ne*t= =NULL C. head-ne*t=NULL D. h

26、ead-ne*t!= NULL 20設(shè)一棵哈夫曼樹共有18個葉結(jié)點(diǎn)，則該樹有 C 個非葉結(jié)點(diǎn)。 A18 B19 C17 D16 21 .設(shè)有一個長度為32的順序表，要在第5個元素之前插入1個元素也就是插入元素 作為新表的第5個元素，需移動元素個數(shù)為 B 。 A25 B28 C. 5 D6 22如圖1所示的一個圖，假設(shè)從頂點(diǎn)g出發(fā)，按深度優(yōu)先搜索法進(jìn)展遍歷，則可能得到的一種頂點(diǎn)序列為D 。 Agabecdf Bgacfebd Cgaebcfd Dgaedfcb bbdfeCag 圖123設(shè)有一個長度為33的順序表，要刪除第10個元素(下標(biāo)從1開場)需移動元素的個數(shù) 為 C 。 A11 B10 C

27、23 D14 24線性表以 B 方式存儲，能進(jìn)展折半查找。 A關(guān)鍵字有序的 B關(guān)鍵字有序的順序C D順序25設(shè)有一個28階的對稱矩陣A，采用壓縮存儲的方式，將其下三角局部以行序為主序 存儲到一維數(shù)組B中數(shù)組下標(biāo)從1開場，則數(shù)組中第26號元素對應(yīng)于矩陣中的元素是 A 。 Aa7,5 , Ba7,6 Ca6,5 Da26有一個長度為8的有序表，按折半查找對該表進(jìn)展查找，在等概率情況下查找成功的平均比擬次數(shù)為 D 。A22/8 B20/8 C23/8 D21/8 27. 在一個不帶頭結(jié)點(diǎn)的單循環(huán)鏈表中，p、q分別指向表中第一個結(jié)點(diǎn)和尾結(jié)點(diǎn)，現(xiàn)要 刪除第一個結(jié)點(diǎn)，且p、q仍然分別指向新表中第一個結(jié)點(diǎn)和

28、尾結(jié)點(diǎn)。可用的語句是 p=p-ne*t;和 D 。 Ap=q-ne*t; Bp-ne*t=q ; C q=p; D q-ne*t=p; 28. 排序算法中，從尚未排序序列中依次取出元素與已排序序列初始為空中的元素進(jìn)展比擬要求比擬次數(shù)盡量少，然后將其放入已排序序列的正確位置的方法是A 。 A折半插入排序 B直接插入排序 C歸并排序 D選擇排序 29在一棵二叉樹中，假設(shè)編號為16的結(jié)點(diǎn)是其雙親結(jié)點(diǎn)的左孩子，則他的雙親結(jié)點(diǎn)的順序編號 為 B 。A7 B8 C32 D33 30排序方法中，從未排序序列中挑選元素，并將其依次放入已排序序列初始為空的一端的方法，稱為 C 排序。 A堆 B冒泡 C選擇 D快

29、速 二、填空題1.數(shù)據(jù)的邏輯構(gòu)造在計算機(jī)中的表示稱為_物理 (存儲)_構(gòu)造。2.構(gòu)造中的數(shù)據(jù)元素存在一對多的關(guān)系稱為_樹形_構(gòu)造。3.四類根本構(gòu)造分別為_集合 線性 樹形 圖狀_構(gòu)造。 4.棧的操作特點(diǎn)是_先進(jìn)后出_。5.隊列的操作特點(diǎn)是先進(jìn)_先出_。 6.廣義表的( a , (a ,b) , d , e ,( (i ,j ) ,k ) )深度是_ 3 _。7.廣義表( (b,a,c) , c,d ,( e ,i ,j ,k ) )的表尾是_(c,d,(e,i,j,k)_。8.廣義表( (a ,b) , d , e ,( (i ,j ) ,k ) )的長度是_ 4 _。 9.設(shè)有一個長度為20

30、的順序表 , 第8號元素到第20號元素依次存放的值為8,9,20。 *人想要在第8號元素前插入1個元素7也就是插入元素作為新表的第8個元素，程 序中他的做法是用語句for(i=8;idatasq-front;和_ sq-fronf+;_ 。 11設(shè)有一棵有38個結(jié)點(diǎn)的完全二叉樹，該樹共有_6 _層。根所在結(jié)點(diǎn)為第1層12. 設(shè)順序隊列的類型為typedef struct ElemType dataMa*Sise; int front,rear;Squeue;Squeue *sq; sq為指向順序隊列的指針變量，要進(jìn)展新元素*的入隊操作，按教課書約定,可用語句sq-datasq-rear=*;和

31、_ sq-rear+;_。 13 一棵有18個結(jié)點(diǎn)的二叉樹，其2度結(jié)點(diǎn)數(shù)的個數(shù)為8，則該樹共有 _1_個1度結(jié)點(diǎn)。 14. 序列14,12,15,13,18,16,采用冒泡排序算法,經(jīng)一趟冒泡后,序列的結(jié)果是_ 12,14,13,15,16,18_。由小到大排序15. 對一組記錄1，3，9，2，12，7，5，4，6進(jìn)展直接插入排序(由小到大排序) ，當(dāng)把第6個記錄7插入有序表，為尋找插入位置需比擬_3_次。 16. 數(shù)據(jù)構(gòu)造中, _數(shù)據(jù)元素_ 之間的抽象關(guān)系稱為邏輯構(gòu)造。 17. 序列5,3,8,4,7,6,采用冒泡排序算法,經(jīng)一趟冒泡后,序列的結(jié)果是_3,5,4,7,6,8_。(按升序排序)

32、 18. 循環(huán)隊列中，設(shè)front和rear分別為隊頭和隊尾指針，(最多元素為Ma*Size,),判斷循環(huán)隊列為空的條件為_ front= =rear_為真。19. 廣義表(b,a , (c ,b) , f , e ,( (i ,j ) ,k ) )的長度是_6_ 。 20. 排序算法中，從尚未排序序列中依次取出元素與已排序序列初始為空中的元素進(jìn)展比擬要求比擬次數(shù)盡量少，然后將其放入已排序序列的正確位置的方法是折半插入排序。21一棵有18個葉結(jié)點(diǎn)的哈夫曼樹，則該樹共有_17_個非葉結(jié)點(diǎn)。22. 對稀疏矩陣進(jìn)展壓縮存儲,可采用三元組表,矩陣元素a3,4對應(yīng)的三元組為_(3,4, a3,4)_ 。

33、23對稀疏矩陣進(jìn)展壓縮存儲,可采用三元組表，一個8行7列的稀疏矩陣A共有51個零元 素，其相應(yīng)的三元組表共有_5_個元素 24在雙向鏈表中，要刪除p所指的結(jié)點(diǎn)，其中所用的一條語句p-ne*t-prior=p-prior; 的功能是：使P所指結(jié)點(diǎn)的直接后繼的左指針指向_ P所指結(jié)點(diǎn)的直接前驅(qū)_。綜合題1.設(shè)數(shù)據(jù)集合a=6,17,10,13,8,15,12,18,14 1依次取a中各數(shù)據(jù)，構(gòu)造一棵二叉排序樹。 2給出對該二叉樹中序遍歷的序列 3對該二叉樹進(jìn)展查找，成功查找到14要進(jìn)展多少次元素間的比擬？圖2(2)中序遍歷 6 , 8 ,10,12 , 13 , 14 , 15 , 17 , 18

34、(3) 6次2.設(shè)數(shù)據(jù)集合a=62,74,30,15,56,481依次取a中各數(shù)據(jù)，構(gòu)造一棵二叉排序樹。2對該二叉樹進(jìn)展查找，不成功查找有多少種可能？畫出不成功查找樹的示意圖。3不成功查找的平均查找長度是多少4為了成功查找到48需要進(jìn)展多少次元素間的比擬5給出對該二叉樹后序遍歷的序列。(1)圖3 (2)圖4 7種可能 (3)(2*2+3*3+4*2)/7=21/7 (4)4次 (5)15,48,56,30,74,62 3設(shè)有序表為(2, 5, 11, 12, 30, 48, 58) ,元素的序號依次為 1,2,3,，7. 1畫出對上述查找表進(jìn)展折半查找所對應(yīng)的判定樹樹中結(jié)點(diǎn)用序號表示 2說明成

35、功查找到元素11需要經(jīng)過多少次比擬？ (3) 在等概率條件下, 給出成功查找的平均查找長度 1圖5 (2) 3次 (3) ( 1+2*2+3*4)/7=17/74設(shè)有序表為3，9，15，26，38，41，53，74，81，96，97，99，元素的 序號依 次為1,2,12。 1說出有哪幾個元素需要經(jīng)過3次元素間的比擬才能成功查到。 2畫出對上述有序表進(jìn)展折半查找所對應(yīng)的判定樹樹結(jié)點(diǎn)用序號表示。 3設(shè)查找5號元素(38)，需要進(jìn)展多少次元素間的比擬才能確定不能查到, 依次和 哪些元素進(jìn)展了比擬？要求寫出具體元素。 4給出后序遍歷該二叉樹的序列。 (5) 給出中序遍歷該二叉樹的序列。(1) 3,

36、26, 53, 97 (2)圖7 (3)4次41,15,26,38 (4) 2(9),1(3),5(38),4(26),3(15),8(74),7(53),10(96),12(99),11(97),9(81),6(41) 51( 3,2(9), 3(15),4(26),5(38),6(41),7(53),8(74),9(81),10(96),11(97),12(99)5 .(1)如圖1所示，假設(shè)從頂點(diǎn)a出發(fā)，首先經(jīng)過頂點(diǎn)c按廣度優(yōu)先搜索法進(jìn)展遍歷，給出可能得到的一種頂點(diǎn)序列。 (2) 如圖1所示，給出從頂點(diǎn)h出發(fā)，首先經(jīng)過頂點(diǎn)d和e按深度優(yōu)先搜索法進(jìn)展遍歷，給出可能得到的一種頂點(diǎn)序列。aa阿d

37、ecfhecdeccdeceecb圖13一組記錄的關(guān)鍵字序列為80,57,41,39,46,47，利用堆排序的方法的方法建立小根堆(堆頂元素是最小元素,給出按篩選法建立的的初始堆。(1) acefdbh(2) hdeacfb339 46 41 57 80 47四、程序填空題1以下冒泡法程序?qū)Υ娣旁赼1，a2，an中的序列進(jìn)展冒泡排序完成程序中的空格局部，其中n是元素個數(shù)，程序按升序排列。 void bsort (NODE a , int) NODE temp; int i,j,flag; for( j=1; jai+1.key) flag=1; (3) a i=ai+1; (4) ; if(f

38、lag= =0)break; 程序中flag的功能是 (5) 1. (1) j+ (2) i=n-j (3) temp=ai; (4) ai+1=temp; (5) 判斷*一趟排序中是否有元素交換 2.學(xué)生信息存放在構(gòu)造數(shù)組中，每個數(shù)組元素存放一個學(xué)生的信息，下標(biāo)從0到n-1。數(shù)組元素按*num由小到大有序排列，以下函數(shù)在a0到an-1中，用折半查找算法查找關(guān)鍵字num等于k的記錄，查找成功返回該記錄的下標(biāo)(數(shù)組元素的下標(biāo))。失敗時返回-1，完成程序中的空格。typedef struct char se*; int num; NODE;int Binary_Search(NODEa,int n

39、, int k) int low,mid,high; low=0; high=n-1; while(_(1)_) mid=(low+high)/2; if(amid.num =k)return _(2)_; else if(_(3)_) low=mid+1; else _(4)_;return -1 ; (1)low=high (2)mid (3)amid.numdata (3) top-ne*t4以下函數(shù)是二叉排序樹的查找算法，假設(shè)二叉樹為空，則返回根結(jié)點(diǎn)的指針，否則，返回值是指向樹結(jié)點(diǎn)的構(gòu)造指針p查找成功p指向查找到的樹結(jié)點(diǎn)，不成功，則p指向為NULL，完成程序中的空格。struct bn

40、ode int key;struct bnode *left;struct bnode *right; ; typedef struct bnode BnodeBnode *BSearch(Bnode *bt, int k) /* bt用于接收二叉排序樹 的根結(jié)點(diǎn)的指針，k用以 接收要查找的關(guān)鍵字*/ Bnode *p; if(bt=NULL) return (bt); _(1)_while(p-key!=_(2)_) if(kkey)_(3)_; else _(4)_; if(p=NULL) break; return p ; (1) p=bt; (2) k (3)p=p-left (4)p

41、=p-right綜合練習(xí)一答案一、單項選擇題1C 2C 3A 4D 5A 6A 7B 8B 9A 10A 11A 12D 13C 14C 15C 16C 17C 18B 19A 20B 21B 22B 23C 24C 25C 26D 27A 28D 29B 30D二、填空題1. 62. 樹形3. 邏輯4. 圖狀5. 先出6. rear=front為真7.b,a,c8. 69. 18 10.O(n)11. 512.1813. 614. n+115. 二叉排序樹 16., 417. 10，12，11，13，14，1618.3419. 1520.3121. 1522. 1423. 324. 4三、綜合應(yīng)用題11圖4447118521011311396圖4 51 14 81 5 15 61 82 8 33 73 93 (2) 4次 (3) ( 1+2*2+3*4+4*4)/11=33/11=3131310318579圖5