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

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

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

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

4、并使結(jié)點入隊的運算為p->data=e; p->next=NULL ; 和（ ）。A . 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è)有一個對稱矩陣A，采用壓縮存儲的方式，將其下三角部分以行序為主序存儲到一維數(shù)組B中（數(shù)組下標(biāo)從1開始），B數(shù)組共有45個元素,則該矩陣是（ ）階的對稱矩陣。A15 B11 C10 D9 12設(shè)有一個24階的對稱矩陣A，采用壓縮存儲的方式（矩陣的第一個元素為a1,1），將其下三角部分以行序為主序存儲到一維數(shù)組B中（數(shù)組下標(biāo)從1開始），

5、則數(shù)組中第30號元素對應(yīng)于矩陣中的元素是（ ）。Aa10,8 Ba9,2 C a8,2 Da8 ,5 13. 下列是C語言中abcd321ABCD的子串的選項是（ ）。 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 =“En

6、glish”; char *p=a; int n=0; while( *p!=0) n+; p+; 結(jié)果中,n的值是（ ）。 A. 6 B.8 C. 5 D.7 17一棵有20個結(jié)點采用鏈式存儲的二叉樹中，共有（ ）個指針域為空。 A21 B20 C19 D18 18在一棵二叉樹中，若編號為5的結(jié)點存在左孩子，則左孩子的順序編號為（ ）。 A9 B10 C11 D12 19設(shè)一棵哈夫曼樹共有18個葉結(jié)點，則該樹有（ ）個非葉結(jié)點。 A18 B19 C17 D16 20設(shè)一棵采用鏈式存儲的二叉樹，除葉結(jié)點外每個結(jié)點度數(shù)都為2，該樹結(jié)點中共有20個指針域為空。則該樹有（ ）個葉結(jié)點。A21 B22

7、 C9 D10 21如圖1所示的一個圖，若從頂點g出發(fā)，按深度優(yōu)先搜索法進行遍歷，則可能得到的一種頂點序列為（ ）。 Agabecdf Bgacfebd Cgaebcfd Dgaedfcb bdfeCag 圖122已知如圖2所示的一個圖，若從頂點a出發(fā)，按廣度優(yōu)先搜索法進行遍歷，則可能得到的一種頂點序列為（ ）。 Aabcedfg Babcefdg Caebcfdg Dacfdebg bdfecabdfecag 圖223線性表以（ ）方式存儲，能進行折半查找。 A關(guān)鍵字有序的 B關(guān)鍵字有序的順序 C鏈接 D順序 24在有序表10,23，32，36，53，66，68，76，87，90,101,1

8、20中，用折半查找值53時，經(jīng)（ ）次比較后查找成功。A6 B3 C8 D4 25有一個長度為8的有序表，按折半查找對該表進行查找，在等概率情況下查找成功的平均比較次數(shù)為（ ）。A22/8 B20/8 C23/8 D21/8 26有一個長度為11的有序表，按折半查找對該表進行查找，在等概率情況下查找成功的平均比較次數(shù)為（ ）。A29/11 B33/11 C26/11 D30/11 27. 排序算法中，從尚未排序序列中依次取出元素與已排序序列（初始為空）中的元素進行比較（要求比較次數(shù)盡量少），然后將其放入已排序序列的正確位置的方法是（ ）。 A折半插入排序 B直接插入排序 C歸并排序 D選擇排序

9、 28設(shè)已有m個元素有序，在未排好序的序列中挑選第m+1個元素，并且只經(jīng)過一次元素的交換就使第m+1個元素排序到位，該方法是（ ）。 A堆排序 B簡單選擇排序 C快速排序 D歸并排序 29排序方法中，從未排序序列中挑選元素，并將其依次放入已排序序列（初始為空）的一端的方法，稱為（ ）排序。 A堆 B冒泡 C選擇 D快速 30一組記錄的關(guān)鍵字序列為（32，65，42，24，26，80），利用快速排序，以第一個關(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，4

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

11、 6.廣義表的( a , (a ,b) , d , e ,( (i ,j ) ,k ) )深度是_。 7. 序列4,2,5,3,8,6,采用冒泡排序算法,經(jīng)一趟冒泡后,序列的結(jié)果是_。（按由小到大順序） 8. 廣義表( (a ,b) , d , e ,( (i ,j ) ,k ) )的長度是_ _。9.在對一組記錄（50，34，92，19，11，68，56，41，79）進行直接插入排序(由小到大排 序) ，當(dāng)把第7個記錄56插入到有序表時，為尋找插入位置需比較_次。10. 設(shè)順序隊列的類型為typedef struct ElemType dataMaxSise; int front,rear;

12、Squeue;Squeue *sq; sq為指向順序隊列的指針變量，要進行元素的出隊操作，并把元素賦給邊量x, 按教科書約定,可用語句x=sq->datasq->front;和_ 。11.數(shù)據(jù)結(jié)構(gòu)中, _可以由一個或多個數(shù)據(jù)項組成。 12. 設(shè)順序隊列的類型為typedef struct ElemType dataMaxSise; int front,rear;Squeue;Squeue *sq; sq為指向順序隊列的指針變量，要進行新元素x的入隊操作，按教課書約定,可用語句sq->datasq->rear=x;和_。 13循環(huán)隊列中，設(shè)front和rear分別為隊頭和

13、隊尾指針，(最多元素為MaxSize,采用少用一個元素的模式),判斷循環(huán)隊列為滿的條件為_為真 。 14. 序列14,12,15,13,18,16,采用冒泡排序算法,經(jīng)一趟冒泡后,序列的結(jié)果是_。（由小到大排序）15排序算法中，從尚未排序序列中依次取出元素與已排序序列（初始為空）中的元素依次進行比較，然后將其放入已排序序列的正確位置的方法是 。16. 數(shù)據(jù)結(jié)構(gòu)中, _ 之間的抽象關(guān)系稱為邏輯結(jié)構(gòu)。17對稀疏矩陣進行壓縮存儲,可采用三元組表，一個6行7列的稀疏矩陣A共有34個零元 素，其相應(yīng)的三元組表共有_個元素。 18. 循環(huán)隊列中，設(shè)front和rear分別為隊頭和隊尾指針，(最多元素為Ma

14、xSize,),判斷循環(huán)隊列為空的條件為_為真。19在雙向鏈表中，要刪除p所指的結(jié)點，可以先用語句（p->prior）->next=p->next；然后再用語句（p->next）->prior= _。 20. 排序算法中，從尚未排序序列中依次取出元素與已排序序列（初始為空）中的元素進行比較（要求比較次數(shù)盡量少），然后將其放入已排序序列的正確位置的方法是 。21.在雙向鏈表中，每個結(jié)點有兩個指針域，一個指向結(jié)點的直接后繼 ，另一個指向_。22. 對稀疏矩陣進行壓縮存儲,可采用三元組表,矩陣元素a3,4 對應(yīng)的三元組為_ 。23.把數(shù)據(jù)存儲到計算機中,并具體體現(xiàn)數(shù)據(jù)之

15、間的邏輯結(jié)構(gòu)稱為_結(jié)構(gòu)。24在雙向鏈表中，要刪除p所指的結(jié)點，其中所用的一條語句（p->next）->prior=p->prior; 的功能是：使P所指結(jié)點的直接后繼的左指針指向_ _。 三、 綜合題1.設(shè)數(shù)據(jù)集合a=1,12,5,8,3,10,7,13,9（1）依次取a中各數(shù)據(jù)，構(gòu)造一棵二叉排序樹。（2）說明如何依據(jù)此二叉樹得到a的有序序列。（3）對該二叉樹進行查找，成功查找到7要進行多少次元素間的比較？（4）給出對該二叉樹后序遍歷的序列。2.設(shè)數(shù)據(jù)集合a=62,74,30,15,56,48（1）依次取a中各數(shù)據(jù)，構(gòu)造一棵二叉排序樹。（2）為了成功查找到48需要進行多少次元

16、素間的比較?（3）給出對該二叉樹后序遍歷的序列。3設(shè)有序表為(2, 5, 11, 12, 30, 48, 58, 70, 78, 79, 90) ,元素的序號依次為 1,2,3,，11. （1）畫出對上述查找表進行折半查找所對應(yīng)的判定樹（樹中結(jié)點用序號表示） （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）畫出對上述有序表進行折半查找所對應(yīng)的判定樹（樹結(jié)點用序號表示）。 （2）

17、設(shè)查找5號元素(38)，需要進行多少次元素間的比較才能確定不能查到, 依次和 哪些元素進行了比較？（要求寫出具體元素）。 （3）給出后序遍歷該二叉樹的序列。 (4) 給出中序遍歷該二叉樹的序列。四、程序填空題1. 設(shè)有一個不帶頭結(jié)點的單向鏈表，頭指針為head, p 、prep 是指向結(jié)點類型的指針，該鏈表在輸入信息時不慎把相鄰兩個結(jié)點的信息重復(fù)輸入,以下程序段是在該單向鏈表中查找這相鄰兩個結(jié)點,，把該結(jié)點的數(shù)據(jù)域data打印出來，并把其中之一從鏈表中刪除，填寫程序中的空格。 prep=head; p=prep->next; while(p - > data!=prep- >

18、data) prep=p; _(1)_ printf(“min=%d”, _(2)_); prep->next= _(3)_ 2.學(xué)生信息存放在結(jié)構(gòu)數(shù)組中，每個數(shù)組元素存放一個學(xué)生的信息，下標(biāo)從0到n-1。數(shù)組元素按學(xué)號num由小到大有序排列，以下函數(shù)在a0到an-1中，用折半查找算法查找關(guān)鍵字num等于k的記錄，查找成功返回該記錄的下標(biāo)(數(shù)組元素的下標(biāo))。失敗時返回-1，完成程序中的空格。 typedef struct char sex; int num; NODE;int Binary_Search(NODE a,int n, int k) int low,mid,high; low

19、=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 . 以下程序是折半插入排序的算法(按記錄中關(guān)鍵字key排序) 設(shè)待排序的記錄序列存放在a1,an中，以a0作為輔助工作單元，以下程序是要把ai 插入到已經(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;

20、 x= ai.key; s=1; j=i-1; while (s<=j) m=_(2)_ if( x<am.key) _(3)_ else _(4)_ for ( k=i-1;k>=j+1;k- -) _(5)_=ak; aj+1=a0; 4以下函數(shù)是二叉排序樹的查找算法，若二叉樹為空，則返回根結(jié)點的指針，否則，返回值是指向樹結(jié)點的結(jié)構(gòu)指針p（查找成功p指向查找到的樹結(jié)點，不成功，則p指向為NULL），完成程序中的空格。struct bnode int key; struct bnode *left;struct bnode *right; ; typedef struct

21、bnode Bnode Bnode *BSearch(Bnode *bt, int k) /* bt用于接收二叉排序樹 的根結(jié)點的指針，k用以 接收要查找的關(guān)鍵字*/ Bnode *p; if(bt = = NULL) return (bt); _(1)_ while(p->key !=_(2)_) if(k<p->key) _(3)_; else _(4)_; if(p=NULL) break; return p ; 期末綜合練習(xí)一答案一、單項選擇題1C 2B 3C 4D 5A 6B 7D 8A 9C 10B 11D 12C 13A 14A 15B 16D 17A 18B

22、19.C 20D 21D 22B 23B 24D 25D 26B 27A 28B 29C 30A 二、填空題1. 52樹形3. 34先進后出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.818front= =rear19. p->prior；20折半插入排序21. 結(jié)點的直接前驅(qū)22(3,4, a3,4)23. 存儲24P所指結(jié)點的直接前驅(qū)三、綜合

23、應(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, 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(

24、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.num<k (4) high=mid-1;3.(1) n(2) (s+j)/2;(3) j=m-1;(4) s=m+1;(

25、5) ak+1 4 (1) p=bt; (2) k (3)p=p->left (4)p=p->right期末綜合練習(xí)二一、單項選擇題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)于線性表的敘述中,錯誤的是( )。A . 線性表采用順序存儲,必須占用一片連續(xù)的存儲空間B. 線性表采用順序存儲,進行插入和刪除操作,不需要進行數(shù)據(jù)元素間的移動C. 線性表采用鏈式存儲，不必占用連續(xù)的存儲空間D. 線性表采用鏈式存儲，進行插入刪除操作，不需要移動元素 3設(shè)有一個長度為22的順序表，要刪

26、除第8個元素需移動元素的個數(shù)為（ ）。 A15 B22 C14 D23 4 .設(shè)有一個長度為28的順序表，要在第12個元素之前插入一個元素（也就是插入元素作為新表的第12個元素），則移動元素個數(shù)為（ ）。 A12 B17 C. 13 D115元素2,6,10,14按順序依次進棧，按該棧的可能輸出序列依次入隊列，該隊列 的不可能輸出序列是是（ ）。（進棧出?？梢越惶孢M行）。 A14,10,6,2 B2,6,10,14 C14,10,2,6 D6,2,14,10 6元素2，4，6,8按順序依次進棧，則該棧的不可能輸出序列是（ ）（進棧出?？梢越惶孢M行）。 A8,6,4,2 B2,4,6,8C4,2

27、,8,6 D8,6,2,4 7對一個棧頂指針為top的鏈棧進行進棧操作，設(shè)P為指向待進棧的結(jié)點的指針，把e 的值賦值給該結(jié)點的數(shù)據(jù)域，然后使該結(jié)點進棧，則執(zhí)行（ ）。 Ap->data=e; p=top->next; top=topànext; Bp->data=e;p->next=top;top=p; Cp->data=e;top=p; Dp->data=e;p->next=top->next; top =p; 8對一個棧頂指針為top的鏈棧進行出棧操作，用變量e保存棧頂元素的值 ，則執(zhí)行 （ ）。 A. e= top->nex

28、t; top->data=e; Be=top->data; top=top->next; Ctop=top->next; e=top->data; Dtop=top->next; e=data; 9 .對不帶頭結(jié)點的單向鏈表,判斷是否為空的條件是（ ）（設(shè)頭指針為head）。Ahead=NULL Bhead->next= =NULL Chead->next= =head Dhead =NULL 10在一個尾指針為rear的不帶頭結(jié)點的單循環(huán)鏈表中,插入一個s所指的結(jié)點,并作為第一個結(jié)點，可執(zhí)行（ ）。 Arearànext= s; s&

29、#224;next=rearànext Brearànext=sànext; Crear=sànext Dsànext=rearànext ; rearànext=s;11設(shè)有一個25階的對稱矩陣A（矩陣的第一個元素為a1,1），采用壓縮存儲的方式，將其下三角部分以行序為主序存儲到一維數(shù)組B中（數(shù)組下標(biāo)從1開始），則矩陣中元素a7,5在一維數(shù)組B中的下標(biāo)是（ ）。A34 B14 C26 D27 12設(shè)有一個28階的對稱矩陣A（矩陣的第一個元素為a1,1），采用壓縮存儲的方式，將其下三角部分以行序為主序存儲到一維數(shù)組B中（數(shù)組

30、下標(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. 字符n B. 字符EC. n D. E 15 .設(shè)主串為“ABcCDABcdEFaBc”，以下模式串能與主串成功匹配的是（ ）。 A. aBc B. BCd C. ABC D .Abc 16. 程序段char a =“English”; char *p=a

31、; int n=0; while( *p!=0) n+; P+;結(jié)果中,P指向（ ）。A. 字符h B.aC. 字符串的結(jié)束符 D.7 17設(shè)一棵哈夫曼樹共有11個非葉結(jié)點，則該樹有（ ）個葉結(jié)點。 A22 B。10 C11 D12 18在一棵二叉樹中，編號為17的結(jié)點的雙親結(jié)點的的順序編號為（ ）。 A34 B7 C9 D8 19一棵具有38個結(jié)點的完全二叉樹，最后一層有（ ）個結(jié)點。 A7 B5 C6 D8 20設(shè)一棵采用鏈式存儲的二叉樹，除葉結(jié)點外每個結(jié)點度數(shù)都為2，該樹結(jié)點中共有20個指針域為空。則該樹共有（ ）個非葉子結(jié)點 A21 B22 C 9 D10 21已知如圖1所示的一個圖，

32、若從頂點V1出發(fā)，按廣度優(yōu)先搜索法進行遍歷，則可能得到的一種頂點序列為（ ）。 AV0V1V2V3V6V7V4V5V8 BV0V1V2V3V4V5V8V6V7 CV0V1V2V3V4V5V6V7V8 DV0V1V2V3V4V8V5V6V7 V6V7V1V2V3V8V4V5V0 圖122已知如圖1所示的一個圖，若從頂點V0出發(fā)，按深度優(yōu)先法進行遍歷，則可能得到的一種頂點序列為（ ）。 A. V0V1V2V4V8V5V3V6V7 BV0V1V2V4V5V8V3V6V7 CV0V1V2V4V8V3V5V6V7 DV0V1V3V6V7V2V4V5V8 23在有序表10,14，34，43，47，64，7

33、5，80，90中，用折半查找法查找值80時，經(jīng)（ ）次比較后查找成功。A4 B2 C3 D5 24對( )進行中序遍歷，可以使遍歷所得到的序列是有序序列。 A完全二叉樹 B二叉排序樹 C滿二叉樹排 D哈夫曼樹25排序算法中，從尚未排序序列中依次取出元素與已排序序列（初始為空）中的元素進行比較，然后將其放入已排序序列的正確位置的方法是（ ）。 A冒泡排序 B直接插入排序 C歸并排序 D選擇排序 26有一個長度為7的有序表，按折半查找對該表進行查找，在等概率情況下查找成功的平均比較次數(shù)為（ ）。A17/7 B18/7 C21/7 D20/7 27一組記錄的關(guān)鍵字序列為（22，55，32，14,16

34、，60），利用快速排序，以第一個關(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堆 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，5

35、7，80 D39，80，46，47，41，57 30一組記錄的關(guān)鍵字序列為（12，45，22，4,6，50），利用快速排序，以第一個關(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ù)存儲到計算機中,并具體體現(xiàn)數(shù)據(jù)之間的邏輯結(jié)構(gòu)稱為_結(jié)構(gòu)。2.結(jié)構(gòu)中的數(shù)據(jù)元素存在一對一的關(guān)系稱為_結(jié)構(gòu)。3.從一個棧頂指針為h的鏈棧中刪除一個結(jié)點時，用x保存被刪結(jié)點的值，可執(zhí)行x=h->data;和_。(結(jié)點的指針域為next) 。 4.向一個棧頂指針為h

36、的鏈棧中插入一個s所指結(jié)點時，可執(zhí)行_和h=s;操作。(結(jié)點的指針域為next) 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 ) )表頭是_。 8. 廣義表的( (a,c) , d ,( e ,i ,j ,k ) )表尾是_ _ 。 9. 設(shè)順序隊列的類型為typedef struct ElemType dataMaxSise; int front,rear;Squeue;Sq

37、ueue *sq; sq為指向順序隊列的指針變量，要進行元素的出隊操作，并把元素賦給變量x, 按教課書約定,可用語句x=sq->datasq->front;和_。 10. 設(shè)順序隊列的類型為typedef struct ElemType dataMaxSise; int front,rear;Squeue;Squeue *sq; sq為指向順序隊列的指針變量，要進行新元素x的入隊操作，按教科書約定,可用語句sq->datasq->rear=x;和_ 。 11. 對20個元素的序列用冒泡排法進行排序，第5趟冒泡共需要進行_次元素間的比較。 12.對16個元素的序列用冒泡排

38、法進行排序，共需要進行_趟冒泡。 13. 在對一組記錄（5,7,3,1,2,6,4,10,9,8,16,13,18,17）進行直接插入排序 (由小到大排序)， 當(dāng)把第10個記錄8插入到有序表時，為尋找插入位置需比較_次。 14.在對一組記錄（50，34，92，19，11，68，56，41，79）進行直接插入排序(由小到大排 序)，當(dāng)把第 8個記錄41插入到有序表時，為尋找插入位置需比較_次。15. 從數(shù)據(jù)結(jié)構(gòu)的角度，城市間的交通線路的關(guān)系屬于 _結(jié)構(gòu)。16. 數(shù)據(jù)的_在計算機中的表示稱為物理結(jié)構(gòu)。 17. 循環(huán)隊列用a0,a7的一維數(shù)組存放隊列元素,(采用少用一個元素的模式)，設(shè)front和r

39、ear分別為隊頭和隊尾指針，且front和rear 的值分別為2和7,當(dāng)前隊列中的元素個數(shù)是_。 18. 循環(huán)隊列用a0,a5的一維數(shù)組存放隊列元素,(采用少用一個元素的模式)，設(shè)front和rear分別為隊頭和隊尾指針，且front和rear 的值分別為3和0，當(dāng)前隊列中的元素個數(shù)是_。 19. 對n個整數(shù)用冒泡法進行排序，某趟冒泡中未進行元素間的 ，說明n個元素已排好序。 20設(shè)已有m個元素有序，在未排好序的序列中挑選第m+1個元素，并且只經(jīng)過一次元素的交換就使第m+1個元素排序到位，該方法是 。21. 對稀疏矩陣進行壓縮存儲,可采用三元組表,每個非零元素對應(yīng)的三元組包括的三項信息是行下標(biāo)、列下標(biāo)和_ _ 。 22對稀疏矩陣進行壓縮存儲,可采用三元組表，一個6行7列的稀疏矩陣A相應(yīng)的三元組表共有8個元素,則矩陣A共有_個零元素。 23. 在雙向鏈表中，要刪除p所指的結(jié)點，其中所用的一條語句（p->prior）->next=p->next； 的功能是：使P所指結(jié)點的直接前驅(qū)的右指針指向_。24在雙向鏈表中，要刪除p所指的結(jié)點，可以先用語句（p->next）->prior=（p->prior）；然后再用語句（p->prior）->next= _。 三、綜合題1.設(shè)數(shù)據(jù)集合a=52,20,46,38,5,64,40