2001年到2006年自考數(shù)據(jù)結構試題和答案

1、自考樂園-心境隨緣，誠與天下自考人共勉！ ！自考樂園-分享快樂，你的快樂老家！! 自考樂園-引領成功，你的精神樂園！ ！自考樂園俱樂部，專注于自考，致力于成為全國最全，最優(yōu)的自考學習交流，資料共享平臺全國2001年10月高等教育自學考試數(shù)據(jù)結構試題課程代碼：02331第一部分 選擇題（30分）一、單項選擇題（本大題共15小題，每小題2分，共30分）在每小題列出的四個選項中只 有一個選項是符合題目要求的，請將正確選項前的字母填在題后的括號內(nèi)。1 算法指的是（）A 計算機程序B.解決問題的計算方法C 排序算法D.解決問題的有限運算序列2 線性表采用鏈式存儲時，結點的存儲地址（）A 必須是不連續(xù)的B

2、 連續(xù)與否均可C 必須是連續(xù)的D .和頭結點的存儲地址相連續(xù)3. 將長度為n的單鏈表鏈接在長度為 m的單鏈表之后的算法的時間復雜度為（）A . O （1）B. O （n） C. O （ m）D. O （ m+n）4. 由兩個棧共享一個向量空間的好處是：（）A 減少存取時間，降低下溢發(fā)生的機率B 節(jié)省存儲空間，降低上溢發(fā)生的機率C 減少存取時間，降低上溢發(fā)生的機率D 節(jié)省存儲空間，降低下溢發(fā)生的機率5. 設數(shù)組datam作為循環(huán)隊列SQ的存儲空間，front為隊頭指針，rear為隊尾指針，則執(zhí)行出隊操作后其頭指針 front值為（）A . front=front+1C. front=（front

3、-1）%m6. 如下陳述中正確的是（A .串是一種特殊的線性表C .串中元素只能是字母B . front=(front+1)%(m-1)D . front=(front+1)%m)B. 串的長度必須大于零D .空串就是空白串俱樂部名稱：自考樂園；俱樂部id : 5346389 （請牢記它哦在百度貼吧的搜索框中輸入俱樂部id，可以直接進入俱樂部）；俱樂部url地址： （您也可以通過此 url進入俱樂部。）7. 若目標串的長度為n，模式串的長度為n/3，則執(zhí)行模式匹配算法時，在最壞情況下的時間復雜度是（）B. O (n)C . O (n2)D . O (n3)& 一個非空廣義表的表頭（A

4、.不可能是子表C. 只能是原子）B. 只能是子表D .可以是子表或原子9 .假設以帶行表的三元組表表示稀疏矩陣，則和下列行表02335自考樂園-心境隨緣，誠與天下自考人共勉！ ！自考樂園-分享快樂，你的快樂老家！! 自考樂園-引領成功，你的精神樂園！ ！自考樂園俱樂部，專注于自考，致力于成為全國最全，最優(yōu)的自考學習交流，資料共享平臺對應的稀疏矩陣是（700070000000B.-5040-50400000】00001i0300006110-8061000000000200D.7000040-5040000030061061£0-80A.C.的樹中度為3的結點個數(shù)為2,度為23一010

5、.在一棵度為數(shù)為（）A. 4的結點個數(shù)為1則度為0的結點個11.在含n個頂點和e條邊的無向圖的鄰接矩陣中，零元素的個數(shù)為（）2 2A . eB. 2eC . n eD . n 2e12 假設一個有n個頂點和e條弧的有向圖用鄰接表表示，則刪除與某個頂點 Vi相關的所有弧的時間復雜度是（）A . 0( n)B . 0(e)C . O(n+e)D . O(n*e)13 .用某種排序方法對關鍵字序列（ 序列的變化情況如下：15，27，68，35，20）進行排序時,20,15,21,25,47,27,68,35,8415,20,21,25,35,27,47,68,8415,20,21,25,27,35,

6、47,68,8425， 84， 21， 47,則所采用的排序方法是（）D .快速排序A .選擇排序B .希爾排序C .歸并排序14 .適于對動態(tài)查找表進行高效率查找的組織結構是（）A.有序表B .分塊有序表C .三叉排序樹D .線性鏈表15 .不定長文件是指（）A.文件的長度不固定C.字段的長度不固定B .記錄的長度不固定 D .關鍵字項的長度不固定第二部分非選擇題（共70分）二、填空題（本大題共 10小題，每小題2分，若有兩個空格，每個空格1分，共20分）不寫解答過程，將正確的答案寫在每小題的空格內(nèi)。錯填或不填均無分。16 .數(shù)據(jù)的邏輯結構是從邏輯關系上描述數(shù)據(jù)，它與數(shù)據(jù)的 無關，是獨立于計

7、算機的。17 .在一個帶頭結點的單循環(huán)鏈表中，p指向尾結點的直接前驅，則指向頭結點的指針 head可用 p表示為 head=。18 .棧頂?shù)奈恢檬请S著操作而變化的。19 .在串S= “ structure”中，以t為首字符的子串有 個。20 .假設一個9階的上三角矩陣 A按列優(yōu)先順序壓縮存儲在一維數(shù)組 B中，其中B0存儲 俱樂部名稱：自考樂園；俱樂部id : 5346389 （請牢記它哦在百度貼吧的搜索框中輸入俱樂部 id，可以直接 進入俱樂部）；俱樂部url地址： （您也可以通過此 url進入俱樂部。）自考樂園-心境隨緣，誠與天下自考人共勉！ ！自考樂園-分享快樂，你的快樂老家！! 自考樂園

8、-引領成功，你的精神樂園！ ！ ！自考樂園俱樂部，專注于自考，致力于成為全國最全，最優(yōu)的自考學習交流，資料共享平臺矩陣中第1個兀素ai,i,則B31中存放的兀素是 。21. 已知一棵完全二叉樹中共有768結點，則該樹中共有個葉子結點。22. 已知一個圖的廣度優(yōu)先生成樹如右圖所示，則與此相 應的廣度優(yōu)先遍歷序列為 。23. 在單鏈表上難以實現(xiàn)的排序方法有 和。24. 在有序表(12，24，36, 48，60，72，84)中二分查找關鍵字72時所需進行的關鍵字比較次數(shù)為。25. 多重表文件和倒排文件都歸屬于 文件。三、解答題(本大題共 4小題，每小題5分，共20分)26. 畫出下列廣義表的共享結構

9、圖形表示P= (z) ,(x,y) ,(x,y),x),(z)27. 請畫出與下列二叉樹對應的森林。28.已知一個無向圖的頂點集為abcde 01001100100001101101-10110a, b, c, d, e,其鄰接矩陣如下所示1(1) 畫出該圖的圖形；a出發(fā)進行深度優(yōu)先遍歷和廣度優(yōu)先遍歷,寫出相應的遍歷序(2) 根據(jù)鄰接矩陣從頂點 列。29.已知一個散列表如下圖所示:35203348590123456789101112其散列函數(shù)為h(key)=key%13,處理沖突的方法為雙重散列法，探查序列為：hi=(h(key)+ i *h1(key)%m i =0,1,， m 1其中h1(

10、key)=key%11+1回答下列問題：(1) 對表中關鍵字35，20，33和48進行查找時，所需進行的比較次數(shù)各為多少？(2) 該散列表在等概率查找時查找成功的平均查找長度為多少？四、算法閱讀題(本大題共4小題，每小題5分，共20分)俱樂部名稱：自考樂園；俱樂部id : 5346389 (請牢記它哦在百度貼吧的搜索框中輸入俱樂部id，可以直接進入俱樂部)；俱樂部url地址： (您也可以通過此 url進入俱樂部。)自考樂園-心境隨緣，誠與天下自考人共勉！ ！自考樂園-分享快樂，你的快樂老家！ ! 自考樂園-引領成功，你的精神樂園!自考樂園俱樂部，專注于自考，致力于成為全國最全，最優(yōu)的自考學習交

11、流，資料共享平臺30. 下列算法的功能是比較兩個鏈串的大小，其返回值為：表。comstr(si,S2)=、0!i請在空白處填入適當?shù)膬?nèi)容。當S當3當si:s=S2S2int comstr(LinkString s1,LinkString s2)/si和s2為兩個鏈串的頭指針while(s1 &&s2)if(s1 >date<s2 >date)retur n 1; if(s1 >date>s2 >date)retur n1 ;if()return 1;if()return1 ; ;閱讀下面的算法Lin kList myno te(L in kL

12、ist L)/L是不帶頭結點的單鏈表的頭指針if(L&&L-> next)q=L ; L=L >next; p=L ; while(p >n ext) p=p >next; p >next=q ; q >next=NULL ;S1:S2:return L; 請回答下列問題：（1）說明語句S1的功能;說明語句組S2的功能;(3)設鏈表表示的線性表為（ai,a2, , ,an），寫出算法執(zhí)行后的返回值所表示的線性32.假設兩個隊列共享一個循環(huán)向量空間（參見右下圖）其類型Queue2定義如下：typedef structDateType dataM

13、axSize;， -:./ raarhJfrontfnj可以直接俱樂部名稱：自考樂園；俱樂部id : 5346389 （請牢記它哦在百度貼吧的搜索框中輸入俱樂部id，進入俱樂部）；俱樂部url地址： （您也可以通過此 url進入俱樂部。）自考樂園-心境隨緣，誠與天下自考人共勉！ ！自考樂園-分享快樂，你的快樂老家！! 自考樂園-引領成功，你的精神樂園！ ！自考樂園俱樂部，專注于自考，致力于成為全國最全，最優(yōu)的自考學習交流，資料共享平臺int front2,rear2；Queue2 ；對于i=0或1, fronti和reari分別為第i個隊列的頭指針和尾指針。請對以下算法填空,實現(xiàn)第i個隊列的入

14、隊操作。int En Queue (Queue2*Q,i nt i,DateType x)/若第i個隊列不滿，則元素x入隊列，并返回1;否則返回0if(i<0|i>1)return 0 ;if(Q >reari=Q >front return0;Q >data =x;Q >reari= ;return1;33. 已知二叉樹的存儲結構為二叉鏈表，閱讀下面算法。typedef struct node DateType data;Struct node * next;ListNode ;typedef ListNode * Lin kList ;Lin kList

15、 Leafhead=NULL ;Void Ino rder (Bin Tree T)LinkList s ;If(T)Inorder(T >lchild);If (!T >lchild)&&(!T >rchild) s=(ListNode*)malloc(sizeof(ListNode); s >data=T >data ;s >next=Leafhead ;Leafhead=s ;Inorder(T >rchild);對于如下所示的二叉樹俱樂部名稱：自考樂園；俱樂部id : 5346389 （請牢記它哦在百度貼吧的搜索框中輸入俱樂部i

16、d，可以直接進入俱樂部）；俱樂部url地址： （您也可以通過此 url進入俱樂部。）自考樂園-心境隨緣，誠與天下自考人共勉！ ！自考樂園-分享快樂，你的快樂老家！! 自考樂園-引領成功，你的精神樂園！ ！自考樂園俱樂部，專注于自考，致力于成為全國最全，最優(yōu)的自考學習交流，資料共享平臺(1畫出執(zhí)行上述算法后所建立的結構；(2) 說明該算法的功能。五、算法設計題(本題共10分)34.閱讀下列函數(shù)arrange()int arran ge(i nt a,i nt 1,i nt h,i nt x)1和h分別為數(shù)據(jù)區(qū)的下界和上界int i,j,t ;i=1 ； j=h ；while(i<j)whi

17、le(i<j && aj>=x)j-；while(i<j && aj>=x)i+；if(i<j) t=aj ； aj=ai ； ai=t ； if(ai<x) return i ；else return i 1 ；(1) 寫出該函數(shù)的功能；(2) 寫一個調(diào)用上述函數(shù)實現(xiàn)下列功能的算法：對一整型數(shù)組bn中的元素進行重新排列，將所有負數(shù)均調(diào)整到數(shù)組的低下標端，將所有正數(shù)均調(diào)整到數(shù)組的高下標端，若有零值，則置于兩者之間，并返回數(shù)組中零元素的個數(shù)。全國2001年10月高等教育自學考試數(shù)據(jù)結構試題參考答案課程代碼：02331、單項選擇題

18、(本大題共15小題,每小題2分，共30分)1 . D2.B3.C4.B5.D6.A7.C8,D9，A10.C11.D12.C13.D14.C 15.B二、填空題(本大題共 10小題，每小題2分，共20分)16.存儲(或存儲結構)17.p> next > next18.進棧和退棧19. 1220. a4,821. 38422. abefcdg23. 快速排序、堆排序、希爾排序24.225.多關鍵字三、解答題(本大題共 4小題，每小題5分，共20分) 請牢記它哦在百度貼吧的搜索框中輸入俱樂部 id，可以直接 (您也可以通過此url進入俱樂部。) Jvzy x自考樂園-心境隨緣，誠與天下

19、自考人共勉！ ！自考樂園-分享快樂，你的快樂老家！! 自考樂園-引領成功，你的精神樂園！ ！自考樂園俱樂部，專注于自考，致力于成為全國最全，最優(yōu)的自考學習交流，資料共享平臺27.28.深度優(yōu)先遍歷序列為：abdce廣度優(yōu)先遍歷序列為：abedc29. (1)對關鍵字 35、20、33和48進行查找的比較次數(shù)為3、2、1、1;(2)平均查找長度ASL=3 2 1 1 2,55四、算法閱讀題(本大題共 4小題，每小題5分，共20分)30. S1=S1- >next s2=s2- >next s2(或 s2!=NULL 或 s2&&!s1) s1(或 s1!=NULL 或

20、 s1&&!s2) return 031. (1)查詢鏈表的尾結點(2) 將第一個結點鏈接到鏈表的尾部，作為新的尾結點(3) 返回的線性表為(a2,a3”，an,a1)32. (i + 1)%2(或 1 i) Q >reari(Q >reari + )%Maxsize33.(1)Leafhead*DA(2)中序遍歷二叉樹，按遍歷序列中葉子結點數(shù)據(jù)域的值構建一個以Leafhead為頭指針的逆序單鏈表(或按二叉樹中葉子結點數(shù)據(jù)自右至左鏈接成一個鏈表)。五、算法設計題(本題共10分)34. (1)該函數(shù)的功能是：調(diào)整整數(shù)數(shù)組a中的元素并返回分界值i，使所有v x的元素均落

21、在a1.i上，使所有x的元素均落在ai + 1.h上。俱樂部名稱：自考樂園；俱樂部id : 5346389 (請牢記它哦在百度貼吧的搜索框中輸入俱樂部id，可以直接進入俱樂部)；俱樂部url地址： (您也可以通過此 url進入俱樂部。)自考樂園-心境隨緣，誠與天下自考人共勉！ ！自考樂園-分享快樂，你的快樂老家！! 自考樂園-引領成功，你的精神樂園！ ！ ！自考樂園俱樂部，專注于自考，致力于成為全國最全，最優(yōu)的自考學習交流，資料共享平臺（2）int f（int b,int n）或 int f（int b,int n） int p,q ；int p,q ；p=arra nge(b, 0,n 1,

22、0); p=arra nge(b, 0,n 1,1); q= arra nge(b,p+1, n 1,1); q= arra nge(b,O,p,O);return q p;return p q;2003.1數(shù)據(jù)結構試題一、單項選擇題（本大題共15小題，每小題2分，共30分。在每小題的四個備選答案中, 選出一個正確答案，并將正確答案的序號填在題干的括號內(nèi)）1下面程序段的時間復雜度是（D ）for（i=0;i&lt ;n ;i+）for（j=1;j&lt;m;j+）A剛=0 ;A.O( n)B.O(m+n+1)C.O(m+n)D.O(m*n)2. 在單鏈表中，指針p指向元素為 x

23、的結點，實現(xiàn)“刪除 x的后繼”的語句是（B ）A.p=p-&gt ;n ext;B.p-&gt;next=p-&gt;next-&gt;next;C. p_&gt; next=p;D.p=p _&gt; next _&gt; next;3. 在頭指針為 head且表長大于1的單循環(huán)鏈表中，指針p指向表中某個結點，若p-& gt; next-& gt ;n ext=head 則（D ）A.p指向頭結點B.p指向尾結點C.*p的直接后繼是頭結點D.*P的直接后繼是尾結點4. 判定“帶頭結點的鏈隊列為空”的條件是（C ）A. Q

24、.fro nt=NULLB.Q.rear=NULLC.Q.front=Q.rearD.Q.fro nt!=Q.rear5. 設有兩個串T和P，求P在T中首次出現(xiàn)的位置的串運算稱作（D ）A. 聯(lián)接B.求子串C.字符定位D.子串定位6. 廣義表 A=（a,（b）,（）,（c,d,e）的長度為（ A ）A. 4B.5C.6D.77.棵含18個結點的二叉樹的高度至少為（C ）A. 3B.4C.5D.68.已知二叉樹的先序序列為ABDECF，中序序列為DBEAFC，則后序序列為 （D ）A.DEBAFCB.DEFBCA9. 無向圖中一個頂點的度是指圖中A.通過該頂點的簡單路徑數(shù)C.通過該頂點的回路數(shù)1

25、0. 已知一個圖如下所示，從頂點C.DEBCFAD.DEBFCA（B ）B.與該頂點相鄰接的頂點數(shù)D.與該頂點連通的頂點數(shù)a出發(fā)進行廣度優(yōu)先遍歷可能得到的序列為A.a c e f b d B.a c b d f e C.a c b d e f D.a c d b f e11. 在下列排序方法中，平均時間性能為0（ nlog n）且空間性能最好的是（B ）A.快速排序B.堆排序C.歸并排序12. 已知一組關鍵字為25,48,36,72,79,82,23,40,16,35些子序列進行一趟兩兩歸并的結果是（A ）A.25,36,48,72,23,40,79,82,16,35C.25,36,48,72

26、,16,23,35,40,79,82D.基數(shù)排序，其中每相鄰兩個為有序子序列。對這13. 設順序存儲的線性表共有123個元素，按分塊查找的要求等分成 順序查找來確定塊，并在確定的塊中進行順序查找， 成功時的平均查找長度為（A.21B.2314. 索引非順序文件的特點是A.主文件無序，索引表有序C.主文件有序，索引表有序15. 倒排文件的主要優(yōu)點是（A.便于進行插入和刪除運算C.便于進行多關鍵字查詢B )C.41D.62）B.主文件有序,D.主文件無序,B.25,36,48,72,16,23,40,79,82,35D.16,23,25,35,36,40,48,72,79,823塊。若對索引表采用

27、則在查找概率相等的情況下，分塊查找索引表無序索引表無序B.便于進行文件的恢復D.節(jié)省存儲空間1分，共20分）從而現(xiàn)實信息隱藏。前移 一個位置。二、填空題（本大題共10小題，每小題2分，若有兩個空格，每個空格16. 抽象數(shù)據(jù)類型的特點是將數(shù)據(jù)和_運算封裝在一起，17. 從順序表中刪除一個元素時，表中所有在被刪元素之后的元素均需.，允許進行刪除操作的一端稱為18. 在隊列中，允許進行插入操作的一端稱為 隊尾隊頭。19. 如圖兩個棧共享一個向量空間，top1和top2分別為指向兩個棧頂元素的指針，則“棧滿”的判定條件是_top1=top2-1。20. 設 S仁&quot;good&q

28、uot;,S2=&quot;&quot;,S3=&quot;book&quot;，貝U S1，S2 和 S3依次聯(lián)接后的結果是_ good book_o21. 假設三維數(shù)組 A1098按行優(yōu)先順序存儲，若每個元素占 3個存儲單元，且首地址為自考樂園-心境隨緣，誠與天下自考人共勉！ ！自考樂園-分享快樂，你的快樂老家！! 自考樂園-引領成功，你的精神樂園！ ！ ！自考樂園俱樂部，專注于自考，致力于成為全國最全，最優(yōu)的自考學習交流，資料共享平臺100，則元素 A987的存儲地址是_2257。22. 已知在一棵含有n個結點的樹中，只有度為 k的分支結點和度為 0的葉子

29、結點，則該樹中含有的葉子結點的數(shù)目為_(n-1)/k)*(k-1)+1_或n - (n-1)/k_。23能夠成功完全拓撲排序的圖一定是一個有向無環(huán)圖_。24. 如果在排序前，關鍵字序列已接近正序或逆序，則在堆排序和快速排序兩者之中，選用堆排序較為適當。25. 假設哈希表的表長為m，哈希函數(shù)為 H(key)，若用線性探查法解決沖突，則探查地址序列的形式表達為_hi=(H(key)+l)/m 。三、解答題(本大題共4小題，每小題5分，共20分)26. 假設通信電文使用的字符集為 a,b,c,d,e,f，名字符在電文中出現(xiàn)的頻度分別為：34，5，12，23，8，18,試為這6個字符設計哈夫曼編碼。請

30、先畫出你所構造的哈夫曼樹(要求樹中左孩子結點的權值 小于右孩子結點的權值)，然后分別寫出每個字符對應的編碼 。對應哈夫曼編碼;a： 11b: 1010c: 100d: 01e： 1011f: 0027. 已知一個圖如下所示，其頂點按a、b、c、d、e f順序存放在鄰接表的頂點表中，請畫出該圖的鄰接表，使得按此鄰接表進行深度優(yōu)先遍歷時得到的頂點序列為acbefd，進行廣度優(yōu)先遍歷時得到的頂點序列為acbdfe。題27用I答案:自考樂園-心境隨緣，誠與天下自考人共勉！ ！自考樂園-分享快樂，你的快樂老家！! 自考樂園-引領成功，你的精神樂園！ ！自考樂園俱樂部，專注于自考，致力于成為全國最全，最優(yōu)

31、的自考學習交流，資料共享平臺0 a甘13-11 1 -HI 3 h |1b2c7 1141號仔厘kl3d4e切b5f%28. 已知兩個4X 5的稀疏矩陣的三元組表分別如下:014160113212218122222342522569342283342544251請畫出這兩個稀疏矩陣之和的三元組表。解：29從空樹起，依次插入關鍵字 序樹。40，8，90，15，62，95，12，23，56，32,構造一棵二叉排（1）畫出該二叉排序樹（2）畫出刪去該樹中元素值為90的結點之后的二叉排序樹。40890)629512 23 5632(408 621&)(56)(95122332四、算法閱讀題（本

32、大題共4小題，每小題5分，共20分）1132141622-425694279俱樂部名稱：自考樂園；俱樂部id : 5346389 (請牢記它哦在百度貼吧的搜索框中輸入俱樂部id，可以直接進入俱樂部)；俱樂部url地址： (您也可以通過此 url進入俱樂部。)30. 如圖所示，利用同一循環(huán)向量空間實現(xiàn)兩個隊列，其類型Queue2定義如下：Q.IrnniKijtypedef struct DataType dataMaxSize;int fron t2,le ngth2; Queue2;對于i=0或1,fronti和lengthi分別為第i個隊列的頭指針和長度域。請在空缺處填入合適的內(nèi)容，實現(xiàn)第i

33、個循環(huán)隊列的入隊操作。int En Queue(Queue2*Q,i nt i,DataType x)/若第i個隊列不滿，則元素 x入隊列，并返回1,否則返回0if(i&lt;0|i&gt;1)return 0;if( (1)return 0;Q-&gt;data(2)=x;Q-&gt;le ngth(3)+;return 1;解：(1) (Q-&gt;fro nti+Q-& gt;le ngthi%Maxsize=Q-&gt;fro nt(i+1)%2(2) (Q-&gt;fro nti+-&gt;le ngthi%Ma

34、xsize(3) I31. 某二叉樹的線索鏈表存儲結構如圖(b)所示，其中p為指向根結點的指針，圖(a)為結點結構。閱讀下列算法，并回答問題：(1) 寫出執(zhí)行函數(shù)調(diào)用f(p)的輸出結果；(2) 簡述函數(shù)f的功能。void f(Bin ThrTree t)while(t)prin tf(t -&gt;data);if(t-& gt;lchild)t=t-& gt;lchild;elset=t-& gt;rchild;答案(1)ABDFCEGH (2)先根遍歷32.下列函數(shù)FindCycle(G,i)的功能是，對一個采用鄰接表作存儲結構的有向圖G，利用深度優(yōu)先搜索策

35、略尋找一條經(jīng)過頂點vi的簡單回路。數(shù)組cycle_path用于保存搜索過程中形成的回路，cycle_pathk=j(j > 0)表示在回路中頂點 vk的下一個頂點是 vj。請在空缺處填入合適的內(nèi)容，使其成為一個完整的算法。vertex firstedge已知鄰接表的頂點表結點結構為：adjvex n ext邊表結點EdgeNode結構為：in t cycle_pathMaxNum;int FindCycle(ALGraph*G ,int i)若回路存在，則返回1，否則返回0int j;for(j=0;j&lt;G-&gt;n ;j+)cycle_pathj=-1;retu

36、rn DFSPath(G,i,i);自考樂園-心境隨緣，誠與天下自考人共勉！ ！自考樂園-分享快樂，你的快樂老家！ ! 自考樂園-引領成功，你的精神樂園！ ！自考樂園俱樂部，專注于自考，致力于成為全國最全，最優(yōu)的自考學習交流，資料共享平臺int DFSPath(ALGraph*G ,int j,int i)EdgeNode *p;int cycled=0;for(p=G-&gt;adjlistj.firstedge;p&&! cycled;p=p-&gt; next)cycle_pathj=p-&gt;adjvex;if( (1 )cycled=1; 已

37、找到回路elseif(cycle_pathp-&gt;adjvex=-1)cycled=(2);return (3)(1) (2) (3)32 題答案：(1)p-&gt;adjvex=i(2) DFSpath(G,p-&gt;adjvex,i)(3) cycled33.閱讀下列函數(shù)algo，并回答問題。(1)假設整型數(shù)組 A1.8中的元素依次為(3，8，9, 1，乙4, 2, 6)。執(zhí)行函數(shù)調(diào)用algo(A,8) 時，外層while的循環(huán)體執(zhí)行多少次？函數(shù)的返回值是多少？簡述函數(shù)algo(L,n)的功能。int algo(i nt L,i ntn)int i=0,j,s

38、=1,t=n;while (i!=( n+1)/2)int x=Ls；i=s;j=t;while(i&lt;j)while(i&lt;j && Lj& gt;=x)j-;Li=Lj;while(i&lt;j && Li&lt;=x)i+;Lj=Li;Li=x;if(i&lt;( n+1)/2)s=i+1;else t=i-1;if(i=0)return 0;else return Li;(1) (2) (3)33題答案：(1) 外循環(huán)執(zhí)行4次，函數(shù)返回值為 3。(2) 將A1至A8中不小于A1的元素進行遞增排序，如

39、調(diào)用algo(A,8)時最終排序結果為自考樂園-心境隨緣，誠與天下自考人共勉！ ！自考樂園-分享快樂，你的快樂老家！! 自考樂園-引領成功，你的精神樂園！ ！ ！自考樂園俱樂部，專注于自考，致力于成為全國最全，最優(yōu)的自考學習交流，資料共享平臺2 1 3 4 6 7 8 9五、算法設計題(本大題共10分)34.假設以帶頭結點的單循環(huán)鏈表作非遞減有序線性表的存儲結構。請設計一個時間復雜 度為0(n)的算法，刪除表中所有數(shù)值相同的多余元素，并釋放結點空間。例如：(7，10,10，21, 30, 42，42, 42，51, 70) 經(jīng)算法操作后變?yōu)?7，10，21，30，42，51, 70) 34題答

40、案：Exam4(Li nklist,L)list node *p,*q;p=L _&gt ;n ext;while(p!=L)q=p-& gt; next;while( q&&q-&gt;data=p-&gt;data)p_& gt; next=q_&gt; next;free(q);q=p-&gt ;n ext;p-& gt; next;2003年10月全國數(shù)據(jù)結構試題(2006-7-25 2:07:00 )1.計算機識別、存儲和加工處理的對象被統(tǒng)稱為(b )A.數(shù)據(jù)B.C.數(shù)據(jù)結構D.數(shù)據(jù)元素數(shù)據(jù)類型2. 在具

41、有n個結點的有序單鏈表中插入一個新結點并使鏈表仍然有序的時間復雜度是(b )A.O(1)B.O( n)C.O( nl og n)D.O( n2)3. 隊和棧的主要區(qū)別是(d )A.邏輯結構不同B.C.所包含的運算個數(shù)不同D.4. 鏈棧與順序棧相比，比較明顯的優(yōu)點是A.插入操作更加方便B.C.不會岀現(xiàn)下溢的情況D.存儲結構不同限定插入和刪除的位置不同(d )刪除操作更加方便不會出現(xiàn)上溢的情況俱樂部名稱：自考樂園；俱樂部id : 5346389 （請牢記它哦在百度貼吧的搜索框中輸入俱樂部id，可以直接進入俱樂部）；俱樂部url地址： （您也可以通過此 url進入俱樂部。）5. 采用兩類不同存儲結構

42、的字符串可分別簡稱為(b )A.主串和子串B.C.目標串和模式串D.順序串和鏈串變量串和常量串6.在目標串T 0.n-1 =" xwxxyxy"中，對模式串P 0.m-1 =" xy"進行子串定位操作的結果是(c )A.0B.2C.3D.57.已知廣義表的表頭為a，表尾為(b,c)，則此廣義表為(b )自考樂園-心境隨緣，誠與天下自考人共勉！ ！自考樂園-分享快樂，你的快樂老家！! 自考樂園-引領成功，你的精神樂園！ ！自考樂園俱樂部，專注于自考，致力于成為全國最全，最優(yōu)的自考學習交流，資料共享平臺A.(a,(b,c)B.(a,b,c)C.(a),b,c

43、)D.(a,b,c)A :門門 的存儲地址為8. 二維數(shù)組A按行優(yōu)先順序存儲，其中每個元素占420， A :31個存儲單元。若:3的存儲地址為 446，則A : 5 5的存儲地址為B.471C.4729.二叉樹中第D.473A.85層上的結點個數(shù)最多為(d )B.15C.16D.3210. 下列編碼中屬前綴碼的是A.1,01,000,001C.0,10,110,11(a )B.1,01,011,010D.0,1,00,1111. 如果某圖的鄰接矩陣是對角線元素均為零的上三角矩陣，則此圖是A.有向完全圖B.連通圖C.強連通圖D.有向無環(huán)圖12. 對n個關鍵字的序列進行快速排序，平均情況下的空間復

44、雜度為A.O(1)C.O( n)13. 對表長為B.O(log n)D.O(n log n)n的順序表進行順序查找，在查找概率相等的情況下，查找成功的平均查找長度為(n/2 )A.B.C.D.n14. 對于哈希函數(shù) H(key)=key%13,被稱為同義詞的關鍵字是(d )A.35 和 41C.15 和 44B.23D.25和39和5115. 稠密索引是在索引表中(A.為每個記錄建立一個索引項C.為每組記錄建立一個索引項B.D.為每個頁塊建立一個索引項 為每個字段建立一個索引項 每個空格1分，共20 分)二、填空題(每小題 2分，若有兩個空格，16. 當問題的規(guī)模n趨向無窮大時，算法執(zhí)行時間T

45、(n)的數(shù)量級被稱為算法的 _(_時間復雜度A.47017. 在鏈表的結點中，數(shù)據(jù)元素所占的存儲量和整個結點所占的存儲量之比稱作_(存儲密度).date n ext18. 已知鏈棧的結點結構為棧頂指針為top，則實現(xiàn)將指針p所指結點插入棧頂?shù)恼Z句依次為和。19. 空串的長度是_0;空格串的長度是 (空格的數(shù)目_。20. 假設一個6階的下三角矩陣B按列優(yōu)先順序壓縮存儲在一維數(shù)組A中，其中A : 0存儲矩陣的第一個元素 b11,則A : 14存儲的元素是 b63_o21. 在一棵度為3的樹中，度為2的結點個數(shù)是1,度為0的結點個數(shù)是6，則度為3的結點個數(shù)是2o22. 如圖所示的有向無環(huán)圖可以排岀

46、種不同的拓撲序列。自考樂園-心境隨緣，誠與天下自考人共勉！ ！自考樂園-分享快樂，你的快樂老家！! 自考樂園-引領成功，你的精神樂園！ ！ ！自考樂園俱樂部，專注于自考，致力于成為全國最全，最優(yōu)的自考學習交流，資料共享平臺23. 利用篩選法將關鍵字序列(37，66，48，29，31，75)建成的大根堆為(_75,66,48,29,31,37)。24. 對長度為20的有序表進行二分查找的判定樹的高度為5。25. 在多重表文件中，次關鍵字索引的組織方式是將 的記錄鏈接成一個鏈表。26. 對于單鏈表、單循環(huán)鏈表和雙向鏈表，如果僅僅知道一個指向鏈表中某結點的指針p,能否將p所指結點的數(shù)據(jù)元素與其確實存

47、在的直接前驅交換？請對每一種鏈表作岀判斷，若可以，寫岀程序段；否則說明理由。date n ext單鏈表和單循環(huán)鏈表的結點結構為prior date n ext雙向鏈表的結點結構為(1) 單鏈表：(不可以，無法找到前驅接點)(2) 單循環(huán)鏈表(可以:q=p->next;while(q_>next!=p)q=q_>next;q_>data<_>p_>data; 雙向鏈表(可以：p->prior->data<->p->data;)27. 假設通信電文使用的字符集為a,b,c,d,e,f,g，字符的哈夫曼編碼依次為：0110, 1

48、0, 110，111，00，0111 和 010。(1) 請根據(jù)哈夫曼編碼畫岀此哈夫曼樹，并在葉子結點中標注相應字符； 若這些字符在電文中岀現(xiàn)的頻度分別為：3，35，13，15，20，5和9,求該哈夫曼樹的帶權路徑長度。28. 當采用鄰接表作為圖的存儲結構時，也可將鄰接表中的頂點表由順序結構改為鏈表結構。(1) 請分別畫岀這種鄰接表的頂點鏈表結點和邊表結點，并說明結點中各個域的作用；(2) 對如圖所示的有向圖畫岀這種鄰接表。29. 已知4階B-樹如圖所示。(1)分別畫岀將關鍵字 23和89相繼插入之后的B-樹。畫岀從插入之前的B-樹中刪除關鍵字 51之后的B-樹。四、算法閱讀題(每小題5分，共

49、20分)30. 閱讀下列函數(shù)algo,并回答問題：(1)假設隊列q中的元素為(2,4,5,7,8), 其中"2”為隊頭元素。寫岀執(zhí)行函數(shù)調(diào)用 algo(&q)后 的隊列q；簡述算法algo的功能。void algo(Queue *Q)Stack S;In itStack(&S);while (!QueueEmpty(Q)Push(&S, DeQueue(Q);while (! StackEmpty (&S)俱樂部名稱：自考樂園；俱樂部id : 5346389 (請牢記它哦在百度貼吧的搜索框中輸入俱樂部 id，可以直接進入俱樂部)；俱樂部url地址： (

50、您也可以通過此 url進入俱樂部。)自考樂園-心境隨緣，誠與天下自考人共勉！ ！自考樂園-分享快樂，你的快樂老家！! 自考樂園-引領成功，你的精神樂園！ ！自考樂園俱樂部，專注于自考，致力于成為全國最全，最優(yōu)的自考學習交流，資料共享平臺E nQueue(Q,Pop(&S);87542(2)隊列倒置31. 閱讀下列函數(shù) F,并回答問題：(1) 已知如圖所示的二叉樹以二叉鏈表作存儲結構，rt為指向根結點的指針。寫岀執(zhí)行函數(shù)調(diào)用F(rt)的輸岀結果。說明函數(shù)F的功能。void F(Bi nTree T)Stack S;if(T)Ini tStack(&S);Push(&S,NULL);while(T)prin tf("%c", T->data);if(T->rchild) Push(&S,T->rchild);if(T->lchild)T=T->lchild;else T=Pop(&S);(1)(2) 前序遍歷二叉數(shù)vertex firstedge32. 已知鄰接表的頂點表結點結構為adjvex n ext邊表結點EdgeNode的結構為下列算