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

1、數(shù)據(jù)結(jié)構(gòu)期末綜合練習(xí)2014年12月期末綜合練習(xí)一一、單項(xiàng)選擇題1 .單向鏈表所具備的特點(diǎn)是( )。A.可以隨機(jī)訪問任一結(jié)點(diǎn) B.占用連續(xù)的存儲空間 C.插入刪除不需要移動元素 D.可以通過某結(jié)點(diǎn)的指針域訪問其前驅(qū)結(jié)點(diǎn) 2.頭指針為head的帶頭結(jié)點(diǎn)的單向鏈表為空的判定條件是( )為真。A. head= =NULL B. head-next= =NULLC. head-next=NULL; D. head-next!= NULL 3.設(shè)有一個(gè)長度為18的順序表，要在第6個(gè)元素之前插入一個(gè)元素（也就是插入元素作為新表的第6個(gè)元素），則移動元素個(gè)數(shù)為（ ）。 A12 B5 C. 13 D6 4設(shè)有

2、一個(gè)長度為32的順序表，要刪除第8個(gè)元素需移動元素的個(gè)數(shù)為（ ）。 A9 B8 C25 D24 5棧和隊(duì)列的共同特點(diǎn)是（ ）。 A都是線性結(jié)構(gòu) B元素都可以隨機(jī)進(jìn)出C都是先進(jìn)后出 D都是先進(jìn)先出 6一個(gè)棧的進(jìn)棧序列是2，4，6，8，10，則棧的不可能輸出序列是（ ）（進(jìn)棧出?？梢越惶孢M(jìn)行）。A2，4，6，8，10 B8，6，10，2，4C8，10，6，4，2 D10，8，6，4，2 7元素1，3，5，7按順序依次入隊(duì)列，按該隊(duì)列的出隊(duì)序列進(jìn)棧，該棧的可能輸出序列是（ ）（進(jìn)棧出?？梢越惶孢M(jìn)行）。 A7，5，1，3 B7，3，1，5 C5，1，3，7 D7，5，3，1 8一個(gè)隊(duì)列的入隊(duì)序列是a,

3、b,c,d,按該隊(duì)列的可能輸出序列使各元素依次入棧，該棧的可能輸出序列是 （ ）。（進(jìn)棧出棧可以交替進(jìn)行）。 Ad,c,b,a Bc,a,b,d Cd,b,a,c Dd,a,b,c 9在一個(gè)不帶頭結(jié)點(diǎn)的鏈隊(duì)中，假設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針，則對該隊(duì)列進(jìn)行出 隊(duì)操作中并把結(jié)點(diǎn)的值保存在變量e中,其運(yùn)算為e=fdata；和（ ）。 Ar=rnext; Brnext=r; Cf=fnext; Dfnext=f; 10在一個(gè)鏈隊(duì)中，假設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針，p指向一個(gè)已生成的結(jié)點(diǎn),現(xiàn)要為 該結(jié)點(diǎn)的數(shù)據(jù)域賦值e，并使結(jié)點(diǎn)入隊(duì)的運(yùn)算為p-data=e; p-next=NULL ; 和（ ）。A .

4、 f-next=p; f=p; B r-next=p;r=p; C p-next=r;r=p; D p-next=f;f=p; 11設(shè)有一個(gè)對稱矩陣A，采用壓縮存儲的方式，將其下三角部分以行序?yàn)橹餍虼鎯Φ揭痪S數(shù)組B中（數(shù)組下標(biāo)從1開始），B數(shù)組共有45個(gè)元素,則該矩陣是（ ）階的對稱矩陣。A15 B11 C10 D9 12設(shè)有一個(gè)24階的對稱矩陣A，采用壓縮存儲的方式（矩陣的第一個(gè)元素為a1,1），將其下三角部分以行序?yàn)橹餍虼鎯Φ揭痪S數(shù)組B中（數(shù)組下標(biāo)從1開始），則數(shù)組中第30號元素對應(yīng)于矩陣中的元素是（ ）。Aa10,8 Ba9,2 C a8,2 Da8 ,5 13. 下列是C語言中abcd

5、321ABCD的子串的選項(xiàng)是（ ）。 A. 21ABC B.abcABCD C. abcD D. 321a 14. 字符串a(chǎn)1=BEIJING, a2 =BEI , a3= BEFANG a4=“BEFI中最大的是（ ）。A. a1 B. a2 C. a3 D. a4 15. 字符串a(chǎn)1=BEIJING, a2 =BEF , a3= BEFANG, a4=“BEFI最小的是（ ）.A. a1 B. a2 C. a3 D. a4 16. 程序段char a =“English”; char *p=a; int n=0; while( *p!=0) n+; p+; 結(jié)果中,n的值是（ ）。 A.

6、6 B.8 C. 5 D.7 17一棵有20個(gè)結(jié)點(diǎn)采用鏈?zhǔn)酱鎯Φ亩鏄渲校灿校?）個(gè)指針域?yàn)榭铡?A21 B20 C19 D18 18在一棵二叉樹中，若編號為5的結(jié)點(diǎn)存在左孩子，則左孩子的順序編號為（ ）。 A9 B10 C11 D12 19設(shè)一棵哈夫曼樹共有18個(gè)葉結(jié)點(diǎn)，則該樹有（ ）個(gè)非葉結(jié)點(diǎn)。 A18 B19 C17 D16 20設(shè)一棵采用鏈?zhǔn)酱鎯Φ亩鏄洌~結(jié)點(diǎn)外每個(gè)結(jié)點(diǎn)度數(shù)都為2，該樹結(jié)點(diǎn)中共有20個(gè)指針域?yàn)榭铡t該樹有（ ）個(gè)葉結(jié)點(diǎn)。A21 B22 C9 D10 21如圖1所示的一個(gè)圖，若從頂點(diǎn)g出發(fā)，按深度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為（ ）。 Agabecd

7、f Bgacfebd Cgaebcfd Dgaedfcb bdfeCag 圖122已知如圖2所示的一個(gè)圖，若從頂點(diǎn)a出發(fā)，按廣度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為（ ）。 Aabcedfg Babcefdg Caebcfdg Dacfdebg bdfecabdfecag 圖223線性表以（ ）方式存儲，能進(jìn)行折半查找。 A關(guān)鍵字有序的 B關(guān)鍵字有序的順序 C鏈接 D順序 24在有序表10,23，32，36，53，66，68，76，87，90,101,120中，用折半查找值53時(shí)，經(jīng)（ ）次比較后查找成功。A6 B3 C8 D4 25有一個(gè)長度為8的有序表，按折半查找對該表進(jìn)行查找，

8、在等概率情況下查找成功的平均比較次數(shù)為（ ）。A22/8 B20/8 C23/8 D21/8 26有一個(gè)長度為11的有序表，按折半查找對該表進(jìn)行查找，在等概率情況下查找成功的平均比較次數(shù)為（ ）。A29/11 B33/11 C26/11 D30/11 27. 排序算法中，從尚未排序序列中依次取出元素與已排序序列（初始為空）中的元素進(jìn)行比較（要求比較次數(shù)盡量少），然后將其放入已排序序列的正確位置的方法是（ ）。 A折半插入排序 B直接插入排序 C歸并排序 D選擇排序 28設(shè)已有m個(gè)元素有序，在未排好序的序列中挑選第m+1個(gè)元素，并且只經(jīng)過一次元素的交換就使第m+1個(gè)元素排序到位，該方法是（ ）。

9、 A堆排序 B簡單選擇排序 C快速排序 D歸并排序 29排序方法中，從未排序序列中挑選元素，并將其依次放入已排序序列（初始為空）的一端的方法，稱為（ ）排序。 A堆 B冒泡 C選擇 D快速 30一組記錄的關(guān)鍵字序列為（32，65，42，24，26，80），利用快速排序，以第一個(gè)關(guān)鍵字為分割元素，經(jīng)過一次劃分后結(jié)果為（ ）。 A26，24，32，42，65，80 B24，26，32，42，65，80 C26，24，32，65，42，80 D26，24，32，80，42，65二、填空題1.廣義表( a , (a ,b) , d , e ,( (i ,j ) ,k ) )的長度是_ 。 2.結(jié)構(gòu)中的

10、數(shù)據(jù)元素存在一對多的關(guān)系稱為_結(jié)構(gòu)。3.廣義表的( c， a , (a ,b) , d , e ,( (i ,j ) ,k ) )深度是_ 。 4.棧的操作特點(diǎn)是_。5. 設(shè)順序隊(duì)列的類型為typedef struct ElemType dataMaxSise; int front,rear;Squeue;Squeue *sq; sq為指向順序隊(duì)列的指針變量，要進(jìn)行新元素x的入隊(duì)操作，按教課書約定,可用語句sq-datasq-rear=x;和_ 。 6.廣義表的( a , (a ,b) , d , e ,( (i ,j ) ,k ) )深度是_。 7. 序列4,2,5,3,8,6,采用冒泡排序

11、算法,經(jīng)一趟冒泡后,序列的結(jié)果是_。（按由小到大順序） 8. 廣義表( (a ,b) , d , e ,( (i ,j ) ,k ) )的長度是_ _。9.在對一組記錄（50，34，92，19，11，68，56，41，79）進(jìn)行直接插入排序(由小到大排 序) ，當(dāng)把第7個(gè)記錄56插入到有序表時(shí)，為尋找插入位置需比較_次。10. 設(shè)順序隊(duì)列的類型為typedef struct ElemType dataMaxSise; int front,rear;Squeue;Squeue *sq; sq為指向順序隊(duì)列的指針變量，要進(jìn)行元素的出隊(duì)操作，并把元素賦給邊量x, 按教科書約定,可用語句x=sq-da

12、tasq-front;和_ 。11.數(shù)據(jù)結(jié)構(gòu)中, _可以由一個(gè)或多個(gè)數(shù)據(jù)項(xiàng)組成。 12. 設(shè)順序隊(duì)列的類型為typedef struct ElemType dataMaxSise; int front,rear;Squeue;Squeue *sq; sq為指向順序隊(duì)列的指針變量，要進(jìn)行新元素x的入隊(duì)操作，按教課書約定,可用語句sq-datasq-rear=x;和_。 13循環(huán)隊(duì)列中，設(shè)front和rear分別為隊(duì)頭和隊(duì)尾指針，(最多元素為MaxSize,采用少用一個(gè)元素的模式),判斷循環(huán)隊(duì)列為滿的條件為_為真 。 14. 序列14,12,15,13,18,16,采用冒泡排序算法,經(jīng)一趟冒泡后,

13、序列的結(jié)果是_。（由小到大排序）15排序算法中，從尚未排序序列中依次取出元素與已排序序列（初始為空）中的元素依次進(jìn)行比較，然后將其放入已排序序列的正確位置的方法是 。16. 數(shù)據(jù)結(jié)構(gòu)中, _ 之間的抽象關(guān)系稱為邏輯結(jié)構(gòu)。17對稀疏矩陣進(jìn)行壓縮存儲,可采用三元組表，一個(gè)6行7列的稀疏矩陣A共有34個(gè)零元 素，其相應(yīng)的三元組表共有_個(gè)元素。 18. 循環(huán)隊(duì)列中，設(shè)front和rear分別為隊(duì)頭和隊(duì)尾指針，(最多元素為MaxSize,),判斷循環(huán)隊(duì)列為空的條件為_為真。19在雙向鏈表中，要刪除p所指的結(jié)點(diǎn)，可以先用語句（p-prior）-next=p-next；然后再用語句（p-next）-prio

14、r= _。 20. 排序算法中，從尚未排序序列中依次取出元素與已排序序列（初始為空）中的元素進(jìn)行比較（要求比較次數(shù)盡量少），然后將其放入已排序序列的正確位置的方法是 。21.在雙向鏈表中，每個(gè)結(jié)點(diǎn)有兩個(gè)指針域，一個(gè)指向結(jié)點(diǎn)的直接后繼 ，另一個(gè)指向_。22. 對稀疏矩陣進(jìn)行壓縮存儲,可采用三元組表,矩陣元素a3,4 對應(yīng)的三元組為_ 。23.把數(shù)據(jù)存儲到計(jì)算機(jī)中,并具體體現(xiàn)數(shù)據(jù)之間的邏輯結(jié)構(gòu)稱為_結(jié)構(gòu)。24在雙向鏈表中，要刪除p所指的結(jié)點(diǎn)，其中所用的一條語句（p-next）-prior=p-prior; 的功能是：使P所指結(jié)點(diǎn)的直接后繼的左指針指向_ _。 三、 綜合題1.設(shè)數(shù)據(jù)集合a=1,12

15、,5,8,3,10,7,13,9（1）依次取a中各數(shù)據(jù)，構(gòu)造一棵二叉排序樹。（2）說明如何依據(jù)此二叉樹得到a的有序序列。（3）對該二叉樹進(jìn)行查找，成功查找到7要進(jìn)行多少次元素間的比較？（4）給出對該二叉樹后序遍歷的序列。2.設(shè)數(shù)據(jù)集合a=62,74,30,15,56,48（1）依次取a中各數(shù)據(jù)，構(gòu)造一棵二叉排序樹。（2）為了成功查找到48需要進(jìn)行多少次元素間的比較?（3）給出對該二叉樹后序遍歷的序列。3設(shè)有序表為(2, 5, 11, 12, 30, 48, 58, 70, 78, 79, 90) ,元素的序號依次為 1,2,3,，11. （1）畫出對上述查找表進(jìn)行折半查找所對應(yīng)的判定樹（樹中結(jié)

16、點(diǎn)用序號表示） （2）說明成功查找到元素2需要經(jīng)過多少次比較？ (3) 說明不成功查找元素75需要經(jīng)過多少次比較？ (4) 給出中序遍歷該折半查找判定樹的序列4設(shè)有序表為（3，9，15，26，38，41，53，74，81，96，97，99），元素的 序號依 次為1,2,12。 （1）畫出對上述有序表進(jìn)行折半查找所對應(yīng)的判定樹（樹結(jié)點(diǎn)用序號表示）。 （2）設(shè)查找5號元素(38)，需要進(jìn)行多少次元素間的比較才能確定不能查到, 依次和 哪些元素進(jìn)行了比較？（要求寫出具體元素）。 （3）給出后序遍歷該二叉樹的序列。 (4) 給出中序遍歷該二叉樹的序列。四、程序填空題1. 設(shè)有一個(gè)不帶頭結(jié)點(diǎn)的單向鏈表，

17、頭指針為head, p 、prep 是指向結(jié)點(diǎn)類型的指針，該鏈表在輸入信息時(shí)不慎把相鄰兩個(gè)結(jié)點(diǎn)的信息重復(fù)輸入,以下程序段是在該單向鏈表中查找這相鄰兩個(gè)結(jié)點(diǎn),，把該結(jié)點(diǎn)的數(shù)據(jù)域data打印出來，并把其中之一從鏈表中刪除，填寫程序中的空格。 prep=head; p=prep-next; while(p - data!=prep- data) prep=p; _(1)_ printf(“min=%d”, _(2)_); prep-next= _(3)_ 2.學(xué)生信息存放在結(jié)構(gòu)數(shù)組中，每個(gè)數(shù)組元素存放一個(gè)學(xué)生的信息，下標(biāo)從0到n-1。數(shù)組元素按學(xué)號num由小到大有序排列，以下函數(shù)在a0到an-1中，

18、用折半查找算法查找關(guān)鍵字num等于k的記錄，查找成功返回該記錄的下標(biāo)(數(shù)組元素的下標(biāo))。失敗時(shí)返回-1，完成程序中的空格。 typedef struct char sex; int num; NODE;int Binary_Search(NODE a,int n, 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 ; 3 . 以下程序是折半插

19、入排序的算法(按記錄中關(guān)鍵字key排序) 設(shè)待排序的記錄序列存放在a1,an中，以a0作為輔助工作單元，以下程序是要把a(bǔ)i 插入到已經(jīng)有序的序列a1,ai-1中。 void binsort (NODE a ,int n) int x,i,j,s,k,m; for （i=2；i=_(1)_ ; i+） a0=ai; x= ai.key; s=1; j=i-1; while (s=j) m=_(2)_ if( x=j+1;k- -) _(5)_=ak; aj+1=a0; 4以下函數(shù)是二叉排序樹的查找算法，若二叉樹為空，則返回根結(jié)點(diǎn)的指針，否則，返回值是指向樹結(jié)點(diǎn)的結(jié)構(gòu)指針p（查找成功p指向查找到的

20、樹結(jié)點(diǎn)，不成功，則p指向?yàn)镹ULL），完成程序中的空格。struct bnode int key; struct bnode *left;struct bnode *right; ; typedef struct bnode Bnode Bnode *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) brea

21、k; return p ; 期末綜合練習(xí)一答案一、單項(xiàng)選擇題1C 2B 3C 4D 5A 6B 7D 8A 9C 10B 11D 12C 13A 14A 15B 16D 17A 18B 19.C 20D 21D 22B 23B 24D 25D 26B 27A 28B 29C 30A 二、填空題1. 52樹形3. 34先進(jìn)后出5. sq-rear+;63 7.2,4,3,5,6,8849. 310sq-fronf+;11. 數(shù)據(jù)元素12sq-rear+;13. front= =(rear+1)% MaxSize 1412,14,13,15,16,1815.直接插入排序 16數(shù)據(jù)元素17.818f

22、ront= =rear19. p-prior；20折半插入排序21. 結(jié)點(diǎn)的直接前驅(qū)22(3,4, a3,4)23. 存儲24P所指結(jié)點(diǎn)的直接前驅(qū)三、綜合應(yīng)用題1. (1)圖3 (2)中序遍歷 1 , 3 , 5 , 7 , 8 , 9 , 10 , 12 , 13 (3) 5次 (4) 3,7,9,10,8,5,13,12,1 圖31351213789102 (1)圖4 (4)4次 (5)15,48,56,30,74,62 627456481530圖43（1）圖5 4711852101311396圖5 (2) 3次 (3) 4次 (4) 1, 2, 3, 4, 5, 6, 7, 8, 9,

23、10, 11 （序號） 4.(1)圖6 (2)4次41,15,26,38 (3) 2(9),1(3),5(38),4(26),3(15),8(74),7(53),10(96),12(99),11(97),9(81),6(41) （4）1( 3）,2(9), 3(15),4(26),5(38),6(41),7(53),8(74),9(81),10(96),11(97),12(99) 471285211110639圖6四、程序填空題1. (1) p=p-next; (2)p-data或prep-data(3) p-next;2. (1)low=high (2)mid (3)amid.numleft

24、 (4)p=p-right期末綜合練習(xí)二一、單項(xiàng)選擇題1.數(shù)據(jù)的存儲結(jié)構(gòu)包括數(shù)據(jù)元素的表示和（ ）。 A . 數(shù)據(jù)處理的方法 B. 數(shù)據(jù)元素間的關(guān)系的表示 C . 相關(guān)算法 D. 數(shù)據(jù)元素的類型 2 .下面關(guān)于線性表的敘述中,錯(cuò)誤的是( )。A . 線性表采用順序存儲,必須占用一片連續(xù)的存儲空間B. 線性表采用順序存儲,進(jìn)行插入和刪除操作,不需要進(jìn)行數(shù)據(jù)元素間的移動C. 線性表采用鏈?zhǔn)酱鎯?，不必占用連續(xù)的存儲空間D. 線性表采用鏈?zhǔn)酱鎯?，進(jìn)行插入刪除操作，不需要移動元素 3設(shè)有一個(gè)長度為22的順序表，要刪除第8個(gè)元素需移動元素的個(gè)數(shù)為（ ）。 A15 B22 C14 D23 4 .設(shè)有一個(gè)長度

25、為28的順序表，要在第12個(gè)元素之前插入一個(gè)元素（也就是插入元素作為新表的第12個(gè)元素），則移動元素個(gè)數(shù)為（ ）。 A12 B17 C. 13 D115元素2,6,10,14按順序依次進(jìn)棧，按該棧的可能輸出序列依次入隊(duì)列，該隊(duì)列 的不可能輸出序列是是（ ）。（進(jìn)棧出?？梢越惶孢M(jìn)行）。 A14,10,6,2 B2,6,10,14 C14,10,2,6 D6,2,14,10 6元素2，4，6,8按順序依次進(jìn)棧，則該棧的不可能輸出序列是（ ）（進(jìn)棧出?？梢越惶孢M(jìn)行）。 A8,6,4,2 B2,4,6,8C4,2,8,6 D8,6,2,4 7對一個(gè)棧頂指針為top的鏈棧進(jìn)行進(jìn)棧操作，設(shè)P為指向待進(jìn)棧的

26、結(jié)點(diǎn)的指針，把e 的值賦值給該結(jié)點(diǎn)的數(shù)據(jù)域，然后使該結(jié)點(diǎn)進(jìn)棧，則執(zhí)行（ ）。 Ap-data=e; p=top-next; top=topnext; Bp-data=e;p-next=top;top=p; Cp-data=e;top=p; Dp-data=e;p-next=top-next; top =p; 8對一個(gè)棧頂指針為top的鏈棧進(jìn)行出棧操作，用變量e保存棧頂元素的值 ，則執(zhí)行 （ ）。 A. e= top-next; top-data=e; Be=top-data; top=top-next; Ctop=top-next; e=top-data; Dtop=top-next; e=d

27、ata; 9 .對不帶頭結(jié)點(diǎn)的單向鏈表,判斷是否為空的條件是（ ）（設(shè)頭指針為head）。Ahead=NULL Bhead-next= =NULL Chead-next= =head Dhead =NULL 10在一個(gè)尾指針為rear的不帶頭結(jié)點(diǎn)的單循環(huán)鏈表中,插入一個(gè)s所指的結(jié)點(diǎn),并作為第一個(gè)結(jié)點(diǎn)，可執(zhí)行（ ）。 Arearnext= s; snext=rearnext Brearnext=snext; Crear=snext Dsnext=rearnext ; rearnext=s;11設(shè)有一個(gè)25階的對稱矩陣A（矩陣的第一個(gè)元素為a1,1），采用壓縮存儲的方式，將其下三角部分以行序?yàn)橹餍?/p>

28、存儲到一維數(shù)組B中（數(shù)組下標(biāo)從1開始），則矩陣中元素a7,5在一維數(shù)組B中的下標(biāo)是（ ）。A34 B14 C26 D27 12設(shè)有一個(gè)28階的對稱矩陣A（矩陣的第一個(gè)元素為a1,1），采用壓縮存儲的方式，將其下三角部分以行序?yàn)橹餍虼鎯Φ揭痪S數(shù)組B中（數(shù)組下標(biāo)從1開始），則數(shù)組中第40號元素對應(yīng)于矩陣中的元素是（ ）。 Aa10,8 Ba9,4 Ca9,5 Da8,5 13.數(shù)組a經(jīng)初始化 char a =“English”; a7中存放的是（ ）。 A. 字符串的結(jié)束符 B. 字符hC. h D. h 14.數(shù)組a經(jīng)初始化 char a =“English”; a1中存放的是（ ）。 A. 字

29、符n B. 字符EC. n D. E 15 .設(shè)主串為“ABcCDABcdEFaBc”，以下模式串能與主串成功匹配的是（ ）。 A. aBc B. BCd C. ABC D .Abc 16. 程序段char a =“English”; char *p=a; int n=0; while( *p!=0) n+; P+;結(jié)果中,P指向（ ）。A. 字符h B.aC. 字符串的結(jié)束符 D.7 17設(shè)一棵哈夫曼樹共有11個(gè)非葉結(jié)點(diǎn)，則該樹有（ ）個(gè)葉結(jié)點(diǎn)。 A22 B。10 C11 D12 18在一棵二叉樹中，編號為17的結(jié)點(diǎn)的雙親結(jié)點(diǎn)的的順序編號為（ ）。 A34 B7 C9 D8 19一棵具有38

30、個(gè)結(jié)點(diǎn)的完全二叉樹，最后一層有（ ）個(gè)結(jié)點(diǎn)。 A7 B5 C6 D8 20設(shè)一棵采用鏈?zhǔn)酱鎯Φ亩鏄?，除葉結(jié)點(diǎn)外每個(gè)結(jié)點(diǎn)度數(shù)都為2，該樹結(jié)點(diǎn)中共有20個(gè)指針域?yàn)榭?。則該樹共有（ ）個(gè)非葉子結(jié)點(diǎn) A21 B22 C 9 D10 21已知如圖1所示的一個(gè)圖，若從頂點(diǎn)V1出發(fā)，按廣度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為（ ）。 AV0V1V2V3V6V7V4V5V8 BV0V1V2V3V4V5V8V6V7 CV0V1V2V3V4V5V6V7V8 DV0V1V2V3V4V8V5V6V7 V6V7V1V2V3V8V4V5V0 圖122已知如圖1所示的一個(gè)圖，若從頂點(diǎn)V0出發(fā)，按深度優(yōu)先法進(jìn)行遍

31、歷，則可能得到的一種頂點(diǎn)序列為（ ）。 A. V0V1V2V4V8V5V3V6V7 BV0V1V2V4V5V8V3V6V7 CV0V1V2V4V8V3V5V6V7 DV0V1V3V6V7V2V4V5V8 23在有序表10,14，34，43，47，64，75，80，90中，用折半查找法查找值80時(shí)，經(jīng)（ ）次比較后查找成功。A4 B2 C3 D5 24對( )進(jìn)行中序遍歷，可以使遍歷所得到的序列是有序序列。 A完全二叉樹 B二叉排序樹 C滿二叉樹排 D哈夫曼樹25排序算法中，從尚未排序序列中依次取出元素與已排序序列（初始為空）中的元素進(jìn)行比較，然后將其放入已排序序列的正確位置的方法是（ ）。 A

32、冒泡排序 B直接插入排序 C歸并排序 D選擇排序 26有一個(gè)長度為7的有序表，按折半查找對該表進(jìn)行查找，在等概率情況下查找成功的平均比較次數(shù)為（ ）。A17/7 B18/7 C21/7 D20/7 27一組記錄的關(guān)鍵字序列為（22，55，32，14,16，60），利用快速排序，以第一個(gè)關(guān)鍵字為分割元素，經(jīng)過一次劃分后結(jié)果為（ ）。 A16，14，22，55，32，60 B16，14，22，32，55，60 C16，14，22，60，32，55 D14，16，22，32，55，60 28排序方法中，從未排序序列中挑選元素，并將其依次放入已排序序列（初始為空）的一端的方法，稱為（ ）排序。 A堆

33、B冒泡 C選擇 D快速 29一組記錄的關(guān)鍵字序列為（80,57,41,39,46,47），利用堆排序（堆頂元素是最小元素）的方法建立的初始堆為（ ）。 A39，46，41,57,80，47 B39，47，46，80，41，57C41，39，46，47，57，80 D39，80，46，47，41，57 30一組記錄的關(guān)鍵字序列為（12，45，22，4,6，50），利用快速排序，以第一個(gè)關(guān)鍵字為分割元素，經(jīng)過一次劃分后結(jié)果為（ ）。 A6，4，12，45，22，50 B6，4，12，22，45，50 C6，4，12，50，22，45 D4，6，12，22，45，50 二、填空題1.把數(shù)據(jù)存儲到計(jì)算

34、機(jī)中,并具體體現(xiàn)數(shù)據(jù)之間的邏輯結(jié)構(gòu)稱為_結(jié)構(gòu)。2.結(jié)構(gòu)中的數(shù)據(jù)元素存在一對一的關(guān)系稱為_結(jié)構(gòu)。3.從一個(gè)棧頂指針為h的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí)，用x保存被刪結(jié)點(diǎn)的值，可執(zhí)行x=h-data;和_。(結(jié)點(diǎn)的指針域?yàn)閚ext) 。 4.向一個(gè)棧頂指針為h的鏈棧中插入一個(gè)s所指結(jié)點(diǎn)時(shí)，可執(zhí)行_和h=s;操作。(結(jié)點(diǎn)的指針域?yàn)閚ext) 5. 廣義表的( a , d , e , (i ,j ) ,k )表尾是_ 。 6.廣義表的( a , a ,b , d , e ,( (i ,j ) ,k ) )表頭是_ _。 7.廣義表的( a,c) , a ,b , d , e ,( (I ,j ) ,k ) )表

35、頭是_。 8. 廣義表的( (a,c) , d ,( e ,i ,j ,k ) )表尾是_ _ 。 9. 設(shè)順序隊(duì)列的類型為typedef struct ElemType dataMaxSise; int front,rear;Squeue;Squeue *sq; sq為指向順序隊(duì)列的指針變量，要進(jìn)行元素的出隊(duì)操作，并把元素賦給變量x, 按教課書約定,可用語句x=sq-datasq-front;和_。 10. 設(shè)順序隊(duì)列的類型為typedef struct ElemType dataMaxSise; int front,rear;Squeue;Squeue *sq; sq為指向順序隊(duì)列的指針變

36、量，要進(jìn)行新元素x的入隊(duì)操作，按教科書約定,可用語句sq-datasq-rear=x;和_ 。 11. 對20個(gè)元素的序列用冒泡排法進(jìn)行排序，第5趟冒泡共需要進(jìn)行_次元素間的比較。 12.對16個(gè)元素的序列用冒泡排法進(jìn)行排序，共需要進(jìn)行_趟冒泡。 13. 在對一組記錄（5,7,3,1,2,6,4,10,9,8,16,13,18,17）進(jìn)行直接插入排序 (由小到大排序)， 當(dāng)把第10個(gè)記錄8插入到有序表時(shí)，為尋找插入位置需比較_次。 14.在對一組記錄（50，34，92，19，11，68，56，41，79）進(jìn)行直接插入排序(由小到大排 序)，當(dāng)把第 8個(gè)記錄41插入到有序表時(shí)，為尋找插入位置需比

37、較_次。15. 從數(shù)據(jù)結(jié)構(gòu)的角度，城市間的交通線路的關(guān)系屬于 _結(jié)構(gòu)。16. 數(shù)據(jù)的_在計(jì)算機(jī)中的表示稱為物理結(jié)構(gòu)。 17. 循環(huán)隊(duì)列用a0,a7的一維數(shù)組存放隊(duì)列元素,(采用少用一個(gè)元素的模式)，設(shè)front和rear分別為隊(duì)頭和隊(duì)尾指針，且front和rear 的值分別為2和7,當(dāng)前隊(duì)列中的元素個(gè)數(shù)是_。 18. 循環(huán)隊(duì)列用a0,a5的一維數(shù)組存放隊(duì)列元素,(采用少用一個(gè)元素的模式)，設(shè)front和rear分別為隊(duì)頭和隊(duì)尾指針，且front和rear 的值分別為3和0，當(dāng)前隊(duì)列中的元素個(gè)數(shù)是_。 19. 對n個(gè)整數(shù)用冒泡法進(jìn)行排序，某趟冒泡中未進(jìn)行元素間的 ，說明n個(gè)元素已排好序。 20設(shè)

38、已有m個(gè)元素有序，在未排好序的序列中挑選第m+1個(gè)元素，并且只經(jīng)過一次元素的交換就使第m+1個(gè)元素排序到位，該方法是 。21. 對稀疏矩陣進(jìn)行壓縮存儲,可采用三元組表,每個(gè)非零元素對應(yīng)的三元組包括的三項(xiàng)信息是行下標(biāo)、列下標(biāo)和_ _ 。 22對稀疏矩陣進(jìn)行壓縮存儲,可采用三元組表，一個(gè)6行7列的稀疏矩陣A相應(yīng)的三元組表共有8個(gè)元素,則矩陣A共有_個(gè)零元素。 23. 在雙向鏈表中，要刪除p所指的結(jié)點(diǎn)，其中所用的一條語句（p-prior）-next=p-next； 的功能是：使P所指結(jié)點(diǎn)的直接前驅(qū)的右指針指向_。24在雙向鏈表中，要刪除p所指的結(jié)點(diǎn)，可以先用語句（p-next）-prior=（p-prior）；然后再用語句（p-prior）-next= _。 三、綜合題1.設(shè)數(shù)據(jù)集合a=52