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

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

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

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

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

5、.在一棵度為數(shù)為（）A. 4的結(jié)點(diǎn)個(gè)數(shù)為1則度為0的結(jié)點(diǎn)個(gè)11.在含n個(gè)頂點(diǎn)和e條邊的無(wú)向圖的鄰接矩陣中，零元素的個(gè)數(shù)為（）2 2A . eB. 2eC . n eD . n 2e12 假設(shè)一個(gè)有n個(gè)頂點(diǎn)和e條弧的有向圖用鄰接表表示，則刪除與某個(gè)頂點(diǎn) Vi相關(guān)的所有弧的時(shí)間復(fù)雜度是（）A . 0( n)B . 0(e)C . O(n+e)D . O(n*e)13 .用某種排序方法對(duì)關(guān)鍵字序列（ 序列的變化情況如下：15，27，68，35，20）進(jìn)行排序時(shí),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 .適于對(duì)動(dòng)態(tài)查找表進(jìn)行高效率查找的組織結(jié)構(gòu)是（）A.有序表B .分塊有序表C .三叉排序樹(shù)D .線性鏈表15 .不定長(zhǎng)文件是指（）A.文件的長(zhǎng)度不固定C.字段的長(zhǎng)度不固定B .記錄的長(zhǎng)度不固定 D .關(guān)鍵字項(xiàng)的長(zhǎng)度不固定第二部分非選擇題（共70分）二、填空題（本大題共 10小題，每小題2分，若有兩個(gè)空格，每個(gè)空格1分，共20分）不寫(xiě)解答過(guò)程，將正確的答案寫(xiě)在每小題的空格內(nèi)。錯(cuò)填或不填均無(wú)分。16 .數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的 無(wú)關(guān)，是獨(dú)立于計(jì)

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

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

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

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

11、流，資料共享平臺(tái)30. 下列算法的功能是比較兩個(gè)鏈串的大小，其返回值為：表。comstr(si,S2)=、0!i請(qǐng)?jiān)诳瞻滋幪钊脒m當(dāng)?shù)膬?nèi)容。當(dāng)S當(dāng)3當(dāng)si:s=S2S2int comstr(LinkString s1,LinkString s2)/si和s2為兩個(gè)鏈串的頭指針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是不帶頭結(jié)點(diǎn)的單鏈表的頭指針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; 請(qǐng)回答下列問(wèn)題：（1）說(shuō)明語(yǔ)句S1的功能;說(shuō)明語(yǔ)句組S2的功能;(3)設(shè)鏈表表示的線性表為（ai,a2, , ,an），寫(xiě)出算法執(zhí)行后的返回值所表示的線性32.假設(shè)兩個(gè)隊(duì)列共享一個(gè)循環(huán)向量空間（參見(jiàn)右下圖）其類(lèi)型Queue2定義如下：typedef structDateType dataM

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

14、隊(duì)操作。int En Queue (Queue2*Q,i nt i,DateType x)/若第i個(gè)隊(duì)列不滿，則元素x入隊(duì)列，并返回1;否則返回0if(i<0|i>1)return 0 ;if(Q >reari=Q >front return0;Q >data =x;Q >reari= ;return1;33. 已知二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)為二叉鏈表，閱讀下面算法。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);對(duì)于如下所示的二叉樹(shù)俱樂(lè)部名稱(chēng)：自考樂(lè)園；俱樂(lè)部id : 5346389 （請(qǐng)牢記它哦在百度貼吧的搜索框中輸入俱樂(lè)部i

16、d，可以直接進(jìn)入俱樂(lè)部）；俱樂(lè)部url地址： （您也可以通過(guò)此 url進(jìn)入俱樂(lè)部。）自考樂(lè)園-心境隨緣，誠(chéng)與天下自考人共勉！ ！自考樂(lè)園-分享快樂(lè)，你的快樂(lè)老家！! 自考樂(lè)園-引領(lǐng)成功，你的精神樂(lè)園！ ！自考樂(lè)園俱樂(lè)部，專(zhuān)注于自考，致力于成為全國(guó)最全，最優(yōu)的自考學(xué)習(xí)交流，資料共享平臺(tái)(1畫(huà)出執(zhí)行上述算法后所建立的結(jié)構(gòu)；(2) 說(shuō)明該算法的功能。五、算法設(shè)計(jì)題(本題共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) 寫(xiě)出該函數(shù)的功能；(2) 寫(xiě)一個(gè)調(diào)用上述函數(shù)實(shí)現(xiàn)下列功能的算法：對(duì)一整型數(shù)組bn中的元素進(jìn)行重新排列，將所有負(fù)數(shù)均調(diào)整到數(shù)組的低下標(biāo)端，將所有正數(shù)均調(diào)整到數(shù)組的高下標(biāo)端，若有零值，則置于兩者之間，并返回?cái)?shù)組中零元素的個(gè)數(shù)。全國(guó)2001年10月高等教育自學(xué)考試數(shù)據(jù)結(jié)構(gòu)試題參考答案課程代碼：02331、單項(xiàng)選擇題

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.存儲(chǔ)(或存儲(chǔ)結(jié)構(gòu))17.p> next > next18.進(jìn)棧和退棧19. 1220. a4,821. 38422. abefcdg23. 快速排序、堆排序、希爾排序24.225.多關(guān)鍵字三、解答題(本大題共 4小題，每小題5分，共20分) 請(qǐng)牢記它哦在百度貼吧的搜索框中輸入俱樂(lè)部 id，可以直接 (您也可以通過(guò)此url進(jìn)入俱樂(lè)部。) Jvzy x自考樂(lè)園-心境隨緣，誠(chéng)與天下

19、自考人共勉！ ！自考樂(lè)園-分享快樂(lè)，你的快樂(lè)老家！! 自考樂(lè)園-引領(lǐng)成功，你的精神樂(lè)園！ ！自考樂(lè)園俱樂(lè)部，專(zhuān)注于自考，致力于成為全國(guó)最全，最優(yōu)的自考學(xué)習(xí)交流，資料共享平臺(tái)27.28.深度優(yōu)先遍歷序列為：abdce廣度優(yōu)先遍歷序列為：abedc29. (1)對(duì)關(guān)鍵字 35、20、33和48進(jìn)行查找的比較次數(shù)為3、2、1、1;(2)平均查找長(zhǎng)度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)查詢鏈表的尾結(jié)點(diǎn)(2) 將第一個(gè)結(jié)點(diǎn)鏈接到鏈表的尾部，作為新的尾結(jié)點(diǎn)(3) 返回的線性表為(a2,a3”，an,a1)32. (i + 1)%2(或 1 i) Q >reari(Q >reari + )%Maxsize33.(1)Leafhead*DA(2)中序遍歷二叉樹(shù)，按遍歷序列中葉子結(jié)點(diǎn)數(shù)據(jù)域的值構(gòu)建一個(gè)以Leafhead為頭指針的逆序單鏈表(或按二叉樹(shù)中葉子結(jié)點(diǎn)數(shù)據(jù)自右至左鏈接成一個(gè)鏈表)。五、算法設(shè)計(jì)題(本題共10分)34. (1)該函數(shù)的功能是：調(diào)整整數(shù)數(shù)組a中的元素并返回分界值i，使所有v x的元素均落

21、在a1.i上，使所有x的元素均落在ai + 1.h上。俱樂(lè)部名稱(chēng)：自考樂(lè)園；俱樂(lè)部id : 5346389 (請(qǐng)牢記它哦在百度貼吧的搜索框中輸入俱樂(lè)部id，可以直接進(jìn)入俱樂(lè)部)；俱樂(lè)部url地址： (您也可以通過(guò)此 url進(jìn)入俱樂(lè)部。)自考樂(lè)園-心境隨緣，誠(chéng)與天下自考人共勉！ ！自考樂(lè)園-分享快樂(lè)，你的快樂(lè)老家！! 自考樂(lè)園-引領(lǐng)成功，你的精神樂(lè)園！ ！ ！自考樂(lè)園俱樂(lè)部，專(zhuān)注于自考，致力于成為全國(guó)最全，最優(yōu)的自考學(xué)習(xí)交流，資料共享平臺(tái)（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ù)結(jié)構(gòu)試題一、單項(xiàng)選擇題（本大題共15小題，每小題2分，共30分。在每小題的四個(gè)備選答案中, 選出一個(gè)正確答案，并將正確答案的序號(hào)填在題干的括號(hào)內(nèi)）1下面程序段的時(shí)間復(fù)雜度是（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、的結(jié)點(diǎn)，實(shí)現(xiàn)“刪除 x的后繼”的語(yǔ)句是（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且表長(zhǎng)大于1的單循環(huán)鏈表中，指針p指向表中某個(gè)結(jié)點(diǎn)，若p-& gt; next-& gt ;n ext=head 則（D ）A.p指向頭結(jié)點(diǎn)B.p指向尾結(jié)點(diǎn)C.*p的直接后繼是頭結(jié)點(diǎn)D.*P的直接后繼是尾結(jié)點(diǎn)4. 判定“帶頭結(jié)點(diǎn)的鏈隊(duì)列為空”的條件是（C ）A. Q

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

25、0. 已知一個(gè)圖如下所示，從頂點(diǎn)C.DEBCFAD.DEBFCA（B ）B.與該頂點(diǎn)相鄰接的頂點(diǎn)數(shù)D.與該頂點(diǎn)連通的頂點(diǎn)數(shù)a出發(fā)進(jìn)行廣度優(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. 在下列排序方法中，平均時(shí)間性能為0（ nlog n）且空間性能最好的是（B ）A.快速排序B.堆排序C.歸并排序12. 已知一組關(guān)鍵字為25,48,36,72,79,82,23,40,16,35些子序列進(jìn)行一趟兩兩歸并的結(jié)果是（A ）A.25,36,48,72,23,40,79,82,16,35C.25,36,48,72

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

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

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

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

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

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

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

33、個(gè)循環(huán)隊(duì)列的入隊(duì)操作。int En Queue(Queue2*Q,i nt i,DataType x)/若第i個(gè)隊(duì)列不滿，則元素 x入隊(duì)列，并返回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. 某二叉樹(shù)的線索鏈表存儲(chǔ)結(jié)構(gòu)如圖(b)所示，其中p為指向根結(jié)點(diǎn)的指針，圖(a)為結(jié)點(diǎn)結(jié)構(gòu)。閱讀下列算法，并回答問(wèn)題：(1) 寫(xiě)出執(zhí)行函數(shù)調(diào)用f(p)的輸出結(jié)果；(2) 簡(jiǎn)述函數(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)的功能是，對(duì)一個(gè)采用鄰接表作存儲(chǔ)結(jié)構(gòu)的有向圖G，利用深度優(yōu)先搜索策

35、略尋找一條經(jīng)過(guò)頂點(diǎn)vi的簡(jiǎn)單回路。數(shù)組cycle_path用于保存搜索過(guò)程中形成的回路，cycle_pathk=j(j > 0)表示在回路中頂點(diǎn) vk的下一個(gè)頂點(diǎn)是 vj。請(qǐng)?jiān)诳杖碧幪钊牒线m的內(nèi)容，使其成為一個(gè)完整的算法。vertex firstedge已知鄰接表的頂點(diǎn)表結(jié)點(diǎn)結(jié)構(gòu)為：adjvex n ext邊表結(jié)點(diǎn)EdgeNode結(jié)構(gòu)為：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);自考樂(lè)園-心境隨緣，誠(chéng)與天下自考人共勉！ ！自考樂(lè)園-分享快樂(lè)，你的快樂(lè)老家！ ! 自考樂(lè)園-引領(lǐng)成功，你的精神樂(lè)園！ ！自考樂(lè)園俱樂(lè)部，專(zhuān)注于自考，致力于成為全國(guó)最全，最優(yōu)的自考學(xué)習(xí)交流，資料共享平臺(tái)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，并回答問(wèn)題。(1)假設(shè)整型數(shù)組 A1.8中的元素依次為(3，8，9, 1，乙4, 2, 6)。執(zhí)行函數(shù)調(diào)用algo(A,8) 時(shí)，外層while的循環(huán)體執(zhí)行多少次？函數(shù)的返回值是多少？簡(jiǎn)述函數(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的元素進(jìn)行遞增排序，如

39、調(diào)用algo(A,8)時(shí)最終排序結(jié)果為自考樂(lè)園-心境隨緣，誠(chéng)與天下自考人共勉！ ！自考樂(lè)園-分享快樂(lè)，你的快樂(lè)老家！! 自考樂(lè)園-引領(lǐng)成功，你的精神樂(lè)園！ ！ ！自考樂(lè)園俱樂(lè)部，專(zhuān)注于自考，致力于成為全國(guó)最全，最優(yōu)的自考學(xué)習(xí)交流，資料共享平臺(tái)2 1 3 4 6 7 8 9五、算法設(shè)計(jì)題(本大題共10分)34.假設(shè)以帶頭結(jié)點(diǎn)的單循環(huán)鏈表作非遞減有序線性表的存儲(chǔ)結(jié)構(gòu)。請(qǐng)?jiān)O(shè)計(jì)一個(gè)時(shí)間復(fù)雜 度為0(n)的算法，刪除表中所有數(shù)值相同的多余元素，并釋放結(jié)點(diǎn)空間。例如：(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月全國(guó)數(shù)據(jù)結(jié)構(gòu)試題(2006-7-25 2:07:00 )1.計(jì)算機(jī)識(shí)別、存儲(chǔ)和加工處理的對(duì)象被統(tǒng)稱(chēng)為(b )A.數(shù)據(jù)B.C.數(shù)據(jù)結(jié)構(gòu)D.數(shù)據(jù)元素?cái)?shù)據(jù)類(lèi)型2. 在具

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

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

43、)D.(a,b,c)A :門(mén)門(mén) 的存儲(chǔ)地址為8. 二維數(shù)組A按行優(yōu)先順序存儲(chǔ)，其中每個(gè)元素占420， A :31個(gè)存儲(chǔ)單元。若:3的存儲(chǔ)地址為 446，則A : 5 5的存儲(chǔ)地址為B.471C.4729.二叉樹(shù)中第D.473A.85層上的結(jié)點(diǎn)個(gè)數(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. 如果某圖的鄰接矩陣是對(duì)角線元素均為零的上三角矩陣，則此圖是A.有向完全圖B.連通圖C.強(qiáng)連通圖D.有向無(wú)環(huán)圖12. 對(duì)n個(gè)關(guān)鍵字的序列進(jìn)行快速排序，平均情況下的空間復(fù)

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

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

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

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

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

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

50、您也可以通過(guò)此 url進(jìn)入俱樂(lè)部。)自考樂(lè)園-心境隨緣，誠(chéng)與天下自考人共勉！ ！自考樂(lè)園-分享快樂(lè)，你的快樂(lè)老家！! 自考樂(lè)園-引領(lǐng)成功，你的精神樂(lè)園！ ！自考樂(lè)園俱樂(lè)部，專(zhuān)注于自考，致力于成為全國(guó)最全，最優(yōu)的自考學(xué)習(xí)交流，資料共享平臺(tái)E nQueue(Q,Pop(&S);87542(2)隊(duì)列倒置31. 閱讀下列函數(shù) F,并回答問(wèn)題：(1) 已知如圖所示的二叉樹(shù)以二叉鏈表作存儲(chǔ)結(jié)構(gòu)，rt為指向根結(jié)點(diǎn)的指針。寫(xiě)岀執(zhí)行函數(shù)調(diào)用F(rt)的輸岀結(jié)果。說(shuō)明函數(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. 已知鄰接表的頂點(diǎn)表結(jié)點(diǎn)結(jié)構(gòu)為adjvex n ext邊表結(jié)點(diǎn)EdgeNode的結(jié)構(gòu)為下列算