數(shù)據(jù)結(jié)構(gòu)(本)期末綜合練習(2015年11月)

1、數(shù)據(jù)結(jié)構(gòu)（本）期末綜合練習2015年11月綜合練習一一、單項選擇題 1.對稀疏矩陣進行壓縮存儲,可采用三元組表，一個10 行8列的稀疏矩陣A共有73 個零元素，其相應(yīng)的三元組表共有( C )個元素。 A8 B80 C7 D10 2. 對稀疏矩陣進行壓縮存儲,可采用三元組表，一個10 行8列的稀疏矩陣A，其相應(yīng)的 三元組表共有6個元素，矩陣A共有( C )個零元素。 A8 B72 C74 D10 3.字符串( A )是“abcd321ABCD”的子串。A. “21AB” B. “abcD” C. “aBCD” D. “321a” 4. 程序段 char a =“abdcacdef”; char

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

3、NULL;（ B ）。 A. f->next=p; f=p; B r->next=p;r=p; C r=p; p->next=r; D p->next=f;f=p; 8. 對一個棧頂指針為top的鏈棧進行出棧操作，用變量e保存棧頂元素的值 ，則執(zhí)行 ( B ）。 Ae= top->next; top->data=e; Be=top->data; top=top->next; Ctop=top->next; e=top->data; Dtop=top->next; e=data; 9. 數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機無關(guān)的是數(shù)據(jù)的(

4、 A ) 結(jié)構(gòu)。A.邏輯 B.存儲 C.邏輯與存儲 D.物理 10. 算法的時間復雜度與( A )有關(guān)。 A. 算法本身 B. 所使用的計算機 C. 算法的程序設(shè)計 D. 數(shù)據(jù)結(jié)構(gòu)11順序表所具備的特點之一是（ A ）。 A可以隨機訪問任一結(jié)點 B不需要占用連續(xù)的存儲空間 C插入元素的操作不需要移動元素 D刪除元素的操作不需要移動元素12在一個單向鏈表中,在p所指結(jié)點之后插入一個s所指的結(jié)點時，可執(zhí)行 s->next=p->next; 和（ D ）。 Ap= s; B p->next=s->next; Cp=s->next D p->next=s; 13.

5、數(shù)據(jù)元素是數(shù)據(jù)的基本單位，它（ C ）。 A只能有一個數(shù)據(jù)項組成 B至少有二個數(shù)據(jù)項組成 C可以是一個數(shù)據(jù)項也可以由若干個數(shù)據(jù)項組成 D至少有一個數(shù)據(jù)項為指針類型 14. 一種邏輯結(jié)構(gòu)在存儲時 （ C）。 A只要存儲數(shù)據(jù)元素間的關(guān)系 B只能采用一種存儲結(jié)構(gòu) C可采用不同的存儲結(jié)構(gòu) D只要存儲數(shù)據(jù)元素的值 15設(shè)有頭指針為head的非空的單向鏈表, 指針p指向其尾結(jié)點, 要使該單向鏈表成為單向循環(huán)鏈表,則可利用下述語句（C ）。 Ap =head; Bp=NULL; Cp->next =head; Dhead=p; 16.單向鏈表所具備的特點是( C )。A.可以隨機訪問任一結(jié)點 B.占用

6、連續(xù)的存儲空間 C.插入刪除不需要移動元素 D.可以通過某結(jié)點的指針域訪問其前驅(qū)結(jié)點 17. 在線性表的順序結(jié)構(gòu)中，以下說法正確的是（C ）。 A邏輯上相鄰的元素在物理位置上不一定相鄰 B數(shù)據(jù)元素是不能隨機訪問的 C邏輯上相鄰的元素在物理位置上也相鄰 D進行數(shù)據(jù)元素的插入、刪除效率較高 18.數(shù)據(jù)結(jié)構(gòu)在計算機內(nèi)存中的表示是指 ( B ) 。 A數(shù)據(jù)元素之間的關(guān)系 B數(shù)據(jù)的存儲結(jié)構(gòu) C數(shù)據(jù)元素的類型 D數(shù)據(jù)的邏輯結(jié)構(gòu)19.對鏈表, 以下敘述中正確的是（ A ）。 A不能隨機訪問任一結(jié)點 B結(jié)點占用的存儲空間是連續(xù)的 C插入刪除元素的操作一定要要移動結(jié)點 D可以通過下標對鏈表進行直接訪問 20.下

7、面關(guān)于線性表的敘述中,錯誤的是( B )。 A . 線性表采用順序存儲,必須占用一片連續(xù)的存儲空間。 B. 線性表采用順序存儲,進行插入和刪除操作,不需要進行數(shù)據(jù)元素間的移動。 C. 線性表采用鏈式存儲，不必占用連續(xù)的存儲空間。 D. 線性表采用鏈式存儲，進行插入刪除操作，不需要移動元素21 .設(shè)有一個長度為35的順序表，要在第5個元素之前插入1個元素（也就是插入元素 作為新表的第5個元素），則移動元素個數(shù)為（B ）。 A30 B31 C. 5 D6 22 .設(shè)有一個長度為18的順序表，要在第5個元素之前插入1個元素（也就是插入元素作為新表的第5個元素），則移動元素個數(shù)為（B ）。 A15 B

8、14 C. 5 D6 23設(shè)有一個長度為40的順序表，要刪除第10個元素(下標從1開始)需移動元素的個數(shù)為（ C ）。 A11 B10 C30 D31 24設(shè)有一個長度為25的順序表，要刪除第10個元素(下標從1開始)需移動元素的個數(shù)為（ C ）。 A10 B17 C15 D16 25設(shè)有一個25階的對稱矩陣A，采用壓縮存儲的方式，將其下三角部分以行序為主序存儲到一維數(shù)組B中（數(shù)組下標從1開始），則矩陣中元素a7,5在一維數(shù)組B中的下標是（ C ）。A25 B24 C26 D27 26設(shè)有一個18階的對稱矩陣A，采用壓縮存儲的方式，將其下三角部分以行序為主序存儲到一維數(shù)組B中（數(shù)組下標從1開始

9、），則矩陣中元素a10,8在一維數(shù)組B中的下標是（ D ）。A62, B63 C51 D53 27線性表在存儲后,如果相關(guān)操作中有要求:利用已知的指向某結(jié)點的指針或序號,訪問該結(jié)點的前驅(qū)結(jié)點，則采用（A ）的存儲方式是不可行的。 A單向鏈表 B雙向鏈表 C單向循環(huán)鏈表 D順序表 28在一個尾指針為rear的不帶頭結(jié)點的單循環(huán)鏈表中,插入一個s所指的結(jié)點,并作為第一個結(jié)點，可執(zhí)行sànext=rearànext ;和（ D ）。 A rearànext= sànext; B rear =sànext; C rear=s; D rearà

10、next=s; 29在一棵二叉樹中，若編號為i的結(jié)點存在左孩子,i結(jié)點的左孩子的順序編號為（ B ）。 Ai/2.0 B2*i C2*i+1 Di+2 30在一棵二叉樹中，若編號為15的結(jié)點是其雙親結(jié)點的右孩子，則雙親結(jié)點的順序編號為（D ）。 A30 B8 C31 D7 二、填空題1. 廣義表( ( b,a,c) ,c ,d , f , e , ( (i , j ) , k ) ) 的長度是_ 6_。 2. 結(jié)構(gòu)中的元素之間存在一對多的關(guān)系是_樹形_結(jié)構(gòu)。3. 數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)元素之間的抽象關(guān)系稱為_邏輯_結(jié)構(gòu)。 4. 結(jié)構(gòu)中的元素之間存在多對多的關(guān)系是 _圖狀_結(jié)構(gòu) 。5. 棧的操作特點是

11、后進_先出_ 。 6. 循環(huán)隊列的最大存儲空間為MaxSize ,若隊頭指針front，隊尾指針rear，采用少用一個 存儲空間以有效地判斷棧空或棧滿，隊空的判定條件為_ 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 , j ) , k ) ) 的長度是_ 6_。 9. 設(shè)有一個長度為18的順序表 , 第8號元素到第18號元素依次存放的值為8,9,18. 某人想要刪除第8號元素，程序中他的做法是用語句for(

12、i=18;i<=9;i-)ai-1=ai; 即從第18號元素開始, 直到第9號元素,每個元素依次向前(左)移動1個位置.事實上這 樣做是錯誤的.其結(jié)果新表中第9號元素的值為_ 18 _。 10要求在n個數(shù)據(jù)元素中找值最大的元素，其基本操作為元素間的比較。算法的時間復雜 度為_ O(n)_ 。11. 一棵二叉樹,有1個2度結(jié)點,，2個1度結(jié)點，則該樹共有 _ 5_個結(jié)點。12一棵有8個葉結(jié)點的二叉樹，其1度結(jié)點的個數(shù)為3，則該樹共有 _ 18_個結(jié)點。13設(shè)有一棵深度為5的完全二叉樹，該樹共有21個結(jié)點,第5層上有 6 個結(jié)點。 （根所在結(jié)點為第1層） 14.對于一棵具有n個結(jié)點的二叉樹，

13、其相應(yīng)的鏈式存儲結(jié)構(gòu)中共有_ n+1_個指針域為空。 15中序遍歷_二叉排序樹 _樹可得到一個有序序列。 16. 對一組記錄（5，8，9，2，12，7，56，44，39）進行直接插入排序(由小到大排序) ，當把第6個記錄7插入有序表，為尋找插入位置需比較_ 4_次。 17. 序列12,10,13,11,16,14,采用冒泡排序算法,經(jīng)一趟冒泡后,序列的結(jié)果是_ 10，12，11，13，14，16_。 （按升序排序） 18設(shè)有一棵深度為6的完全二叉樹，第6層上有3個結(jié)點，該樹共有_ 34_個結(jié)點。（根所在結(jié)點為第1層） 19. 對16個元素的序列用冒泡排序法進行排序，共需要進行_ 15_趟冒泡。

14、 20一棵有16個葉結(jié)點的哈夫曼樹，則該樹共有_ 31_個結(jié)點。 21. 一棵有16個葉結(jié)點的哈夫曼樹，則該樹共有_ 15_個非葉結(jié)點。 22. 20個元素進行冒泡法排序，通常第6趟冒泡要進行_ _ 14_次元素間的比較。 23. 在對一組記錄（40，24，82，9，1，78，46，31，69）進行直接插入排序(由小到大排 序) ，當把第7個記錄46插入到有序表時，為尋找插入位置需比較_3_次。24對稀疏矩陣進行壓縮存儲,可采用三元組表，一個6行7列的稀疏矩陣A共有38個零 元素，其相應(yīng)的三元組表共有_4_個元素。 三、綜合題1設(shè)有序表為(5, 8, 14, 15, 33, 51, 61, 7

15、3, 81, 82, 93) ,元素的序號依次為 1,2,3,，11. （1）畫出對上述查找表進行折半查找所對應(yīng)的判定樹（樹中結(jié)點可用序號表示） （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,9（1）依次取a中各數(shù)據(jù)，構(gòu)造一棵二叉排序樹。（2）對該二叉樹進行查找，成功查找到7要進行多少次元素間的比較？（3）給出對該二叉樹中序遍歷的序列。 (1

16、) 圖5 (2) 4次 (3) 中序遍歷 1, 3 , 5 ,7 , 8 , 9 , 10 , 13 3dceabfhe圖1(1)如圖1所示,若從頂點a出發(fā)，首先經(jīng)過c按圖的深度優(yōu)先搜索法進行遍歷，給出可能得到的一種頂點序列。 (1) acdbfeh (2) 152364 或 152634 或 156234 (2)設(shè)有向圖如圖2所示下，寫出首先刪除頂點1的1種拓撲序列1234543465圖2 4設(shè)有序表為(30, 48, 58, 70, 78, 79, 90) ,元素的序號依次為 1,2,3,，7.（1） 畫出對上述查找表進行折半查找所對應(yīng)的判定樹（樹中結(jié)點用序號表示）（2） 給出有序表中經(jīng)3

17、次比較成功查找到的所有元素(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)對該二叉樹進行查找，成功查找到5要進行多少次元素間的比較？(3) 給出對上述二叉排序樹進行中序遍歷的序列 (1) 圖7 (2) 4(3) 3,4,5,6,7,8,9 6(1) 如圖3所示，若從頂點a出發(fā)，首先經(jīng)過c按廣度優(yōu)先搜索法進行遍歷，給出可能得 到的一種頂點序列。 （2）同圖3所示, 若從頂點h出發(fā)，按深度優(yōu)先搜索法進

18、行遍歷，給出可能得到的2種頂點 序列。a阿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的記錄，查找成功返回該記錄的下標，失敗時返回-1，完成程序中的空格typedef struct int key;NODE;int Binary_Search(NODE

19、 a,int n, int k) int 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中的記錄進行直接選擇排序 ，完成程序中的空格typedef struct int key;

20、 NODE; void selsort(NODE a ,int n) int i,j,k; NODE temp; for(i=1;i<= _(1)_;i+) k=i; for(j=i+1; _(2)_; j+) if(aj.key<ak.key) _(3)_; if(i!=k) temp=ai;_(4)_; _(5)_; (1) n-1 (2) j<=n (3) k=j (4) ai=ak (5) ak=temp3.以下函數(shù)為鏈棧的進棧操作，x是要進棧的結(jié)點的數(shù)據(jù)域，top為棧頂指針struct node ElemType data; struct node *next; ;

21、 struct node *top ; void Push(ElemType x) struct node *p; p=(struct node*)malloc(_(1)_); p->data=x; _ (2)_; _(3)_; (1) sizeof(struct node)(2) pànext=top (3) top=p4.以下函數(shù)為鏈隊列的入隊操作，x為要入隊的結(jié)點的數(shù)據(jù)域的值，front、 rear分別是鏈隊列的隊頭、隊尾指針struct node ElemType data;struct node *next;struct node *front，*rear; void

22、 InQueue(ElemType x) struct node *p; p= (struct node*) _(1)_; p->data=x; p->next=NULL; _(2)_; ; rear= _(3)_; (1) malloc(sizeof(struct node) (2) rear->next=p; (3) rear=p;綜合練習二一、單項選擇題 1. 對稀疏矩陣進行壓縮存儲,可采用三元組表，一個有10 行的稀疏矩陣A共有97個零元素，其相應(yīng)的三元組表共有3個元素。該矩陣A有( D )列。 A8 B9 C7 D10 2 .單向鏈表所具備的特點是( C )。A.可

23、以隨機訪問任一結(jié)點 B.占用連續(xù)的存儲空間 C.插入刪除不需要移動元素 D.可以通過某結(jié)點的指針域訪問其前驅(qū)結(jié)點 3. 子串“acd”在主串 “abdcacdefac”中的位置是( B ) 。 A3 B5 C7 D1 4 .設(shè)有一個長度為18的順序表，要在第6個元素之前插入一個元素（也就是插入元素作為新表的第6個元素），則移動元素個數(shù)為（ C ）。 A12 B5 C. 13 D6 5. 序列12,16,8,4按順序依次進棧，按該棧的可能輸出序列依次入隊列，該隊列的不可能輸出序列是（ B ）。 (進棧、出?？梢越惶孢M行）。 A16,12,8,4 B4,8,12,16 C8,4,16,12 D16

24、,12,4,8 6棧和隊列的共同特點是（ A ）。 A都是線性結(jié)構(gòu) B元素都可以隨機進出C都是先進后出 D都是先進先出 7. 在一個不帶頭結(jié)點的鏈隊中，假設(shè)f和r分別為隊頭和隊尾指針，對該隊列進行出隊 操作,并把結(jié)點的值保存在變量e中,其運算為（ C ）。 Ae=f->data；r=r->next; Be=f->data；r->next=r; Ce=f->data；f=f->next; De=f->data；f->next=f; 8元素1，3，5，7按順序依次入隊列，按該隊列的出隊序列進棧，該棧的可能輸出序列是（ D ）（進棧出?？梢越惶孢M行）。

25、 A7，5，1，3 B7，3，1，5 C5，1，3，7 D7，5，3，1 9. 數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機內(nèi)存中的表示是( B )。 A.給相關(guān)變量分配存儲單元 B.數(shù)據(jù)的存儲結(jié)構(gòu) C.數(shù)據(jù)的邏輯結(jié)構(gòu) D.算法的具體體現(xiàn) 10在一個不帶頭結(jié)點的鏈隊中，假設(shè)f和r分別為隊頭和隊尾指針，則對該隊列進行出隊操作中并把結(jié)點的值保存在變量e中,其運算為e=fàdata；和（ C ）。 Ar=rànext; Brànext=r;Cf=fànext; Dfànext=f 11. 以下說法正確的是( B )。 A. 線性表的鏈式存儲結(jié)構(gòu)必須占用連續(xù)的存儲空間 B.

26、 一種邏輯結(jié)構(gòu)可以有不同的存儲結(jié)構(gòu) C一種邏輯結(jié)構(gòu)只能有唯一的存儲結(jié)構(gòu) D線性表的順序存儲結(jié)構(gòu)不必占用連續(xù)的存儲空間 12設(shè)有一個對稱矩陣A，采用壓縮存儲的方式，將其下三角部分以行序為主序存儲到一維數(shù)組B中（數(shù)組下標從1開始），B數(shù)組共有45個元素,則該矩陣是（ D ）階的對稱矩陣。A15 B11 C10 D9 13在一個單鏈表中要刪除p所指結(jié)點的后繼結(jié)點，可執(zhí)行q=p->next; 和（ A ）。 Ap->next=q->next ; Bp=q->next; Cp->next=q; Dp->next=q; 14. 下列是C語言中abcd321ABCD的子串

27、的選項是（ A ）。 A. 21ABC B.abcABCD C. abcD D. 321a 15. 在數(shù)據(jù)結(jié)構(gòu)和算法中，與所使用的計算機有關(guān)的是 （ B ）。 A數(shù)據(jù)元數(shù)間的抽象關(guān)系 B數(shù)據(jù)的存儲結(jié)構(gòu) C算法的時間復雜度 D數(shù)據(jù)的邏輯結(jié)構(gòu) 16. 字符串a(chǎn)1=BEIJING, a2 =BEF , a3= BEFANG, a4=“BEFI最小的是（ B ）.A. a1 B. a2 C. a3 D. a4 17. 以下表中可以隨機訪問的是（ D ）。 A單向鏈表 B雙向鏈表 C單向循環(huán)鏈表 D順序表 18一棵有20個結(jié)點采用鏈式存儲的二叉樹中，共有（ A ）個指針域為空。 A21 B20 C19

28、D18 19.頭指針為head的不帶頭結(jié)點的單向鏈表為空的判定條件是邏輯表達式( A )為真。 A. head= =NULL B. head->next= =NULL C. head->next=NULL D. head->next!= NULL 20設(shè)一棵哈夫曼樹共有18個葉結(jié)點，則該樹有（ C ）個非葉結(jié)點。 A18 B19 C17 D16 21 .設(shè)有一個長度為32的順序表，要在第5個元素之前插入1個元素（也就是插入元素 作為新表的第5個元素），需移動元素個數(shù)為（ B ）。 A25 B28 C. 5 D6 22如圖1所示的一個圖，若從頂點g出發(fā)，按深度優(yōu)先搜索法進行遍歷

29、，則可能得到的一種頂點序列為（D ）。 Agabecdf Bgacfebd Cgaebcfd Dgaedfcb bdfeCag 圖1 23設(shè)有一個長度為33的順序表，要刪除第10個元素(下標從1開始)需移動元素的個數(shù) 為（ C ）。 A11 B10 C23 D14 24線性表以（ B ）方式存儲，能進行折半查找。 A關(guān)鍵字有序的 B關(guān)鍵字有序的順序 C鏈接 D順序 25設(shè)有一個28階的對稱矩陣A，采用壓縮存儲的方式，將其下三角部分以行序為主序 存儲到一維數(shù)組B中（數(shù)組下標從1開始），則數(shù)組中第26號元素對應(yīng)于矩陣中的元素是（ A ）。 Aa7,5 , Ba7,6 Ca6,5 Da7,4 26有

30、一個長度為8的有序表，按折半查找對該表進行查找，在等概率情況下查找成功的平均比較次數(shù)為（ D ）。A22/8 B20/8 C23/8 D21/8 27. 在一個不帶頭結(jié)點的單循環(huán)鏈表中，p、q分別指向表中第一個結(jié)點和尾結(jié)點，現(xiàn)要 刪除第一個結(jié)點，且p、q仍然分別指向新表中第一個結(jié)點和尾結(jié)點?？捎玫恼Z句是 p=p->next;和（ D ）。 Ap=q->next; Bp->next=q ; C q=p; D q->next=p; 28. 排序算法中，從尚未排序序列中依次取出元素與已排序序列（初始為空）中的元素進行比較（要求比較次數(shù)盡量少），然后將其放入已排序序列的正確位置

31、的方法是（A ）。 A折半插入排序 B直接插入排序 C歸并排序 D選擇排序 29在一棵二叉樹中，若編號為16的結(jié)點是其雙親結(jié)點的左孩子，則他的雙親結(jié)點的順序編號 為（ B ）。 A7 B8 C32 D33 30排序方法中，從未排序序列中挑選元素，并將其依次放入已排序序列（初始為空）的一端的方法，稱為（ C ）排序。 A堆 B冒泡 C選擇 D快速 二、填空題1.數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機中的表示稱為_物理 (存儲)_結(jié)構(gòu)。 2.結(jié)構(gòu)中的數(shù)據(jù)元素存在一對多的關(guān)系稱為_樹形_結(jié)構(gòu)。3.四類基本結(jié)構(gòu)分別為_ 集合 線性 樹形 圖狀 _結(jié)構(gòu)。 4.棧的操作特點是_先進后出_。5.隊列的操作特點是先進_先出_

32、。 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的順序表 , 第8號元素到第20號元素依次存放的值為8,9,20。 某人想要在第8號元素前插入1個元素7（也就是插入元素作為新表的第8個元素），程 序中他的做法是用語句for(i=8;i<=20;i+)ai+1=ai;a8=7;即從第8號元

33、素開始, 直到第20號元素,每個元素依次向后(右）移動1個位置,然后把7存放在第8號位置。 事實上這樣做是錯誤的.其結(jié)果是新表中第20號元素的值為_ 8_。 10. 設(shè)順序隊列的類型為typedef struct ElemType dataMaxSise; int front,rear;Squeue;Squeue *sq; sq為指向順序隊列的指針變量，要進行元素的出隊操作，并把元素賦給邊量x, 按教科書約定,可用語句x=sq->datasq->front;和_ sq->fronf+;_ 。 11設(shè)有一棵有38個結(jié)點的完全二叉樹，該樹共有_ 6 _層。（根所在結(jié)點為第1層）1

34、2. 設(shè)順序隊列的類型為typedef struct ElemType dataMaxSise; int front,rear;Squeue;Squeue *sq; sq為指向順序隊列的指針變量，要進行新元素x的入隊操作，按教課書約定,可用語句sq->datasq->rear=x;和_ sq->rear+;_。 13 一棵有18個結(jié)點的二叉樹，其2度結(jié)點數(shù)的個數(shù)為8，則該樹共有 _ 1_個1度結(jié)點。 14. 序列14,12,15,13,18,16,采用冒泡排序算法,經(jīng)一趟冒泡后,序列的結(jié)果是_ 12,14,13,15,16,18_。（由小到大排序）15. 對一組記錄（1，3，

35、9，2，12，7，5，4，6）進行直接插入排序(由小到大排序) ，當把第6個記錄7插入有序表，為尋找插入位置需比較_ 3_次。 16. 數(shù)據(jù)結(jié)構(gòu)中, _數(shù)據(jù)元素_ 之間的抽象關(guān)系稱為邏輯結(jié)構(gòu)。 17. 序列5,3,8,4,7,6,采用冒泡排序算法,經(jīng)一趟冒泡后,序列的結(jié)果是_ 3,5,4,7,6,8_。(按升序排序) 18. 循環(huán)隊列中，設(shè)front和rear分別為隊頭和隊尾指針，(最多元素為MaxSize,),判斷循環(huán)隊列為空的條件為_ front= =rear_為真。19. 廣義表(b,a , (c ,b) , f , e ,( (i ,j ) ,k ) )的長度是_ 6_ 。 20. 排

36、序算法中，從尚未排序序列中依次取出元素與已排序序列（初始為空）中的元素進行比較（要求比較次數(shù)盡量少），然后將其放入已排序序列的正確位置的方法是 折半插入排序 。21 一棵有18個葉結(jié)點的哈夫曼樹，則該樹共有_ 17_個非葉結(jié)點。 22. 對稀疏矩陣進行壓縮存儲,可采用三元組表,矩陣元素a3,4 對應(yīng)的三元組為_ (3,4, a3,4)_ 。23對稀疏矩陣進行壓縮存儲,可采用三元組表，一個8行7列的稀疏矩陣A共有51個零元 素，其相應(yīng)的三元組表共有_ 5_個元素 24在雙向鏈表中，要刪除p所指的結(jié)點，其中所用的一條語句（p->next）->prior=p->prior; 的功能

37、是：使P所指結(jié)點的直接后繼的左指針指向_ P所指結(jié)點的直接前驅(qū)_。 三、 綜合題1.設(shè)數(shù)據(jù)集合a=6,17,10,13,8,15,12,18,14 （1）依次取a中各數(shù)據(jù)，構(gòu)造一棵二叉排序樹。 （2）給出對該二叉樹中序遍歷的序列 （3）對該二叉樹進行查找，成功查找到14要進行多少次元素間的比較？圖2(2)中序遍歷 6 , 8 ,10,12 , 13 , 14 , 15 , 17 , 18 (3) 6次2.設(shè)數(shù)據(jù)集合a=62,74,30,15,56,48（1）依次取a中各數(shù)據(jù)，構(gòu)造一棵二叉排序樹。（2）對該二叉樹進行查找，不成功查找有多少種可能？畫出不成功查找樹的示意圖。（3）不成功查找的平均查找長度是多少?（4）為了成功查找到48需要進行多少次元素間的比較?（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）畫出對上述查找表進行折半查找所對應(yīng)的判定樹（樹中結(jié)點用序號表示） （2）說明成功查找到元素11需要經(jīng)過多少次比較？ (3) 在等概率條件下, 給出成功查找的平均查找長度 （1）圖5 (2)