02331自考全國2004年10月數(shù)據(jù)結(jié)構(gòu)試題

1、超越60自考網(wǎng)全國2004年10月高等教育自學(xué)考試數(shù)據(jù)結(jié)構(gòu)試題課程代碼：02331一、單項(xiàng)選擇題（本大題共15小題，每小題2分，共30分）在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請將其代碼填寫在題干的括號內(nèi)。錯(cuò)選、多選或未選均無分。1 .下列各式中，按增長率由小至大的順序正確排列的是（）n3/23/2 n .log n100A . V n , n! , 2 , nB . n, 2 , ng, 2nlog n 3/2C. 2 , logn, n g , n100D. 2,log n, 2n, nn2 若要在單鏈表中的結(jié)點(diǎn)*p之后插入一個(gè)結(jié)點(diǎn)*s，則應(yīng)執(zhí)行的語句是（）A . s->

2、;next=p->next;p->next=s;B . p->next=s;s->next=p->next;C. p->next=s->next;s->next=p;D . s->next=p;p->next=s->next;3. 若要在0（ 1）的時(shí)間復(fù)雜度上實(shí)現(xiàn)兩個(gè)循環(huán)鏈表頭尾相接，則應(yīng)對兩個(gè)循環(huán)鏈表各設(shè) 置一個(gè)指針，分別指向（）A .各自的頭結(jié)點(diǎn)B .各自的尾結(jié)點(diǎn)C .各自的第一個(gè)元素結(jié)點(diǎn)D. 一個(gè)表的頭結(jié)點(diǎn)，另一個(gè)表的尾結(jié)點(diǎn)4. 棧的兩種常用存儲(chǔ)結(jié)構(gòu)分別為（）A .順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)B .順序存儲(chǔ)結(jié)構(gòu)和散列存儲(chǔ)結(jié)

3、構(gòu)C .鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)和索引存儲(chǔ)結(jié)構(gòu)D .鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)和散列存儲(chǔ)結(jié)構(gòu)5 .已知循環(huán)隊(duì)列的存儲(chǔ)空間為數(shù)組data21，且當(dāng)前隊(duì)列的頭指針和尾指針的值分別為8和3，則該隊(duì)列的當(dāng)前長度為（）A . 5C . 166.已知在如下定義的鏈串結(jié)點(diǎn)中，每個(gè)字符占存儲(chǔ)密度為B . 6D . 171個(gè)字節(jié)，指針占4個(gè)字節(jié)，則該鏈串的typedefstruct no de chardata8; struct no de* next;Li nkStrNode;C2/3D3/47應(yīng)用簡單的匹配算法對主串s= BDBABDABDAB 與子串t= ” BDA 進(jìn)行模式匹配，在匹配成功時(shí)，進(jìn)行的字符比較總次數(shù)為 ()A7B9

4、C10D 128二維數(shù)組 A2010 采用列優(yōu)先的存儲(chǔ)方法，若每個(gè)元素占 2 個(gè)存儲(chǔ)單元，且第 1 個(gè)元 素的首地址為 200，則元素 A89 的存儲(chǔ)地址為 ()A 574B 576C578D 5809對廣義表 L=(a,b),c,d) 進(jìn)行操作 tail(head(L) 的結(jié)果是 ()A ( c,d )B (d)CbD (b)10.已知一棵樹的前序序列為 ABCDEF ，后序序列為 CEDFBA ，則對該樹進(jìn)行層次遍歷得 到的序列為 ()A ABCDEFB ABCEFDCABFCDED ABCDFE11一個(gè)含 n 個(gè)頂點(diǎn)和 e 條弧的有向圖以鄰接矩陣表示法為存儲(chǔ)結(jié)構(gòu)，則計(jì)算該有向圖中某個(gè)頂點(diǎn)

5、出度的時(shí)間復(fù)雜度為()A O(n)B O(e)CO(n+e)2D O(n2)12在關(guān)鍵字序列 (12，23， 34，45，56， 67，78，89，91)中二分查找關(guān)鍵字為 45、 89 和 12 的結(jié)點(diǎn)時(shí)，所需進(jìn)行的比較次數(shù)分別為 ()A4， 4， 3B 4， 3， 3C 3， 4， 4D 3 ， 3， 413下列排序方法中，最好與最壞時(shí)間復(fù)雜度不相同的排序方法是()A 冒泡排序B 直接選擇排序C 堆排序D 歸并排序14已知含 10 個(gè)結(jié)點(diǎn)的二叉排序樹是一棵完全二叉樹，則該二叉排序樹在等概率情況下 查找成功的平均查找長度等于 ()A 1.0B 2.915在下列各種文件中，不能進(jìn)行順序查找的文

6、件是()A 順序文件B 索引文件C .散列文件D.多重表文件二、填空題 (本大題共 10 小題，每小題 2分，共 20 分)16. 抽象數(shù)據(jù)類型是指數(shù)據(jù)邏輯結(jié)構(gòu)及與之相關(guān)的 。17. 已知在結(jié)點(diǎn)個(gè)數(shù)大于 1 的單循環(huán)鏈表中，指針p 指向表中某個(gè)結(jié)點(diǎn)，則下列程序段執(zhí)行結(jié)束時(shí)，指針 q 指向結(jié)點(diǎn) *p 的 結(jié)點(diǎn)。q=p; while(q->next!=p)q=q->next;18. 假設(shè) S 和 X 分別表示進(jìn)棧和出棧操作，由輸入序列“ ABC ”得到輸出序列“ BCA ”的操作序列為 SSXSXX，則由“ a*b+c/d ”得到“ ab*cd/+ ”的操作序列為 。19. 在文本編輯

7、程序中查找某一特定單詞在文本中出現(xiàn)的位置，可以利用串的 運(yùn)算。20. 假設(shè)以行優(yōu)先順序?qū)⒁粋€(gè)n 階的 5 對角矩陣壓縮存儲(chǔ)到一維數(shù)組 Q 中，則數(shù)組 Q 的大小至少為 。21. 在含 100 個(gè)結(jié)點(diǎn)的完全二叉樹中，葉子結(jié)點(diǎn)的個(gè)數(shù)為 。22. 在無向圖中，若從頂點(diǎn)a到頂點(diǎn)b存在，則稱a與b之間是連通的。23. 如果排序過程不改變 之間的相對次序，則稱該排序方法是穩(wěn)定的。24. 索引順序查找適宜對 的順序表進(jìn)行查找。25. 文件的檢索操作可按檢索條件不同分為下列四種詢問，它們是簡單詢問、范圍詢問、函數(shù)詢問及 。三、解答題 (本大題共 4 小題，每小題 5分，共 20分)26. 畫出下圖所示二叉樹的

8、中序線索鏈表的存儲(chǔ)表示。27. 已知圖G=( V，E)，其中：V=a,b,c,d,e,E=(a,b),(b,d),(c,b),(c,d),(d,e),(e,a),(e,c) 。( 1)畫出圖 G；( 2)畫出圖 G 的鄰接表。( 1 )( 2)28. 已知自頂向下的二路歸并排序的算法如下所示，按此算法對關(guān)鍵字序列 (55， 28， 73，并之后的關(guān)鍵字序列。voidMergeSorDC(SeqListR,i ntlow,i nthigh)/用分治法對Rlow.high進(jìn)行二路歸并排序 in tmid;/區(qū)間長度大于1/分解遞歸地對Rlow.mid排序遞歸地對Rmid+1.high排序/組合，將

9、兩個(gè)有序區(qū)歸并為一個(gè)有序區(qū)if(low<high)mid=(low+high)/2;MergeSortDC(R,low,mid);MergeSortDC(R,mid+1,high);Merge(R,low,mid,high); /MergeSortDC4棵含29. 因?yàn)樵氐牟迦胂群蟠涡虿煌?，所?gòu)成的二叉排序樹可能有多種形態(tài)。請畫出1, 2, 3, 4, 5, 6六個(gè)元素且以1為根、深度為4的二叉排序樹。四、算法閱讀題（本大題共4小題，每小題5分，共20分）30. L為一個(gè)帶頭結(jié)點(diǎn)的循環(huán)鏈表。函數(shù)f30的功能是刪除L中數(shù)據(jù)域data的值大于c的所有結(jié)點(diǎn)，并由這些結(jié)點(diǎn)組建成一個(gè)新的帶頭結(jié)點(diǎn)

10、的循環(huán)鏈表，其頭指針作為函數(shù)的返回值。請?jiān)诳杖碧幪钊牒线m的內(nèi)容，使其成為一個(gè)完整的算法。Lin kListf30(Li nkListL,i ntc)Lin kListLc,p,pre;pre=L;P=(1);Lc=(L in kList)malloc(sizeof(ListNode);Lc->n ext=Lc;while(p!=L)if(p->data>c)pre_>n ext=p->n ext;(2);Lc->n ext=p; p=pre _>n ext; elsepre=p;(3)；returnLc;(1)31. 設(shè)棧S=(1,2,3,4,5,6,

11、7),其中7為棧頂元素。 (1 )寫出調(diào)用(&S)后的S;(2)簡述函數(shù)f31中第1個(gè)循環(huán)語句的功能。voidf31(Stack*S)QueueQ;StackT;in ti=0;Ini tQueue(&Q);In itStack( &T);while(!StackEmpty(S)if(i=!t)!=O)Push( &T,Pop(S);elseE nQueue(&Q,Pop(S); while(!StackEmpty( &T)Push(S,PoP( &T);while(!QieueEmpty(&Q)Push(S,DeQueue(&a

12、mp;Q);(1)32. 圖的鄰接矩陣表示描述如下：typedefstructcharvexsMaxNum;字符類型的頂點(diǎn)表in tedgesMaxNumMaxNum;鄰接矩陣intn ,e;/圖的頂點(diǎn)數(shù)和邊數(shù)MGraph;/圖的鄰接矩陣結(jié)構(gòu)描述閱讀下列算法，并回答問題：(1) 對于下列圖G的鄰接矩陣，寫出函數(shù)調(diào)用f32(&G,3)的返回值；0 0 10 00 0 0 1 0110 0 00 0 110(2) 簡述函數(shù)f32的功能；(3) 寫出函數(shù)f32的時(shí)間復(fù)雜度。intf32(MGraph*G ,inti)in td=0,j;for(j=0;j<G-> n;j+)if(

13、G->edgesij)d+;if(G->edgesji)d+;returnd;(1)33 閱讀下列算法并回答問題：f33(L,8)(1) 設(shè)數(shù)組L1.8的初值為(4, -3, 7, -1 , -2, 2, 5, -8),寫出執(zhí)行函數(shù)調(diào)用 之后的L1.8中的元素值；(2) 簡述函數(shù)f33的功能。voidf33(i ntR,i ntn) in tx=R1;in tlow=1,high=n;while(low<high)while(low<high&&Rhigh>=0) high-;if(low>high)Rlow+=Rhigh;while(low<high&&Rlow<0)low+;Rhigh-=Rlow;Rlow=x;(1)五、算法設(shè)計(jì)題(本大題10分)34.