1、自考樂園-心境隨緣，誠與天下自考人共勉！!自考樂園-分享快樂，你的快樂老家！!自考樂園一引領(lǐng)成功，你的精神樂園！自考樂園俱樂部，專注于自考，致力于成為全國最全，最優(yōu)的自考學(xué)習(xí)交流，資料共享平臺(tái)全國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.解決問題的計(jì)算方法C.排序算法D.解決問題的有限運(yùn)算序列2 .線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，結(jié)點(diǎn)的存儲(chǔ)地址（）A.必須是不連續(xù)的B.連續(xù)與

2、否均可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-1）%m6.如下陳述中正確的是（A.串是一

3、種特殊的線性表C.串中元素只能是字母B.front=(front+1)%(m-1)D.front=(front+1)%mB.串的長(zhǎng)度必須大于零D.空串就是空白串7 .若目標(biāo)串的長(zhǎng)度為n,模式串的長(zhǎng)度為n/3,則執(zhí)行模式匹配算法時(shí)，在最壞情況下的時(shí)間復(fù)雜度是（）AO(n)B.O(n)C.O(n2)D.O(n3)38.一個(gè)非空廣義表的表頭（A.不可能是子表C.只能是原子8 .只能是子表D.可以是子表或原子9.假設(shè)以帶行表的三元組表表示稀疏矩陣，則和下列行表自考樂園-分享快樂，你的快樂老家！!自考樂園一引領(lǐng)成功，你的精神樂園!自考樂園俱樂部，專注于自考，致力于成為全國最全，最優(yōu)的自考學(xué)習(xí)交流，資料共

4、享平臺(tái)對(duì)應(yīng)的稀疏矩陣是（A.一。70-5：04000000040610000B.一。7-50一0-8000300400610000C.一0406110-8061000000000200D.70004040-504000001030010 .在一棵度為數(shù)為（）A. 4的樹中，度為3的結(jié)點(diǎn)個(gè)數(shù)為2,度為2的結(jié)點(diǎn)個(gè)數(shù)為1,則度為0的結(jié)點(diǎn)個(gè)B. 5C. 611 .在含n個(gè)頂點(diǎn)和e條邊的無向圖的鄰接矩陣中，零元素的個(gè)數(shù)為（）B. 2eC. n-e12.假設(shè)一個(gè)有n個(gè)頂點(diǎn)和e條弧的有向圖用鄰接表表示弧的時(shí)間復(fù)雜度是（）D. n22e，則刪除與某個(gè)頂點(diǎn)Vi相關(guān)的所有A.O(n)B.O(e)C.O(n+e)1

5、3 .用某種排序方法對(duì)關(guān)鍵字序列序列的變化情況如下：25,84,21,47,D.O(n*e)15,27,68,35,20)進(jìn)行排序時(shí),20,15,21,25,15,20,21,25,15,20,21,25,則所采用的排序方法是(47,35,27,27,27,35,)68,47,47,35,68,68,848484A.選擇排序B.希爾排序C.歸并排序14 .適于對(duì)動(dòng)態(tài)查找表進(jìn)行高效率查找的組織結(jié)構(gòu)是（A.有序表B.分塊有序表15 .不定長(zhǎng)文件是指（）A.文件的長(zhǎng)度不固定C.字段的長(zhǎng)度不固定C.三叉排序樹D.快速排序）D.線性鏈表B.記錄的長(zhǎng)度不固定D.關(guān)鍵字項(xiàng)的長(zhǎng)度不固定第二部分非選擇題（共70

6、分）二、填空題（本大題共10小題，每小題2分，若有兩個(gè)空格，每個(gè)空格1分，共20分）不寫解答過程，將正確的答案寫在每小題的空格內(nèi)。錯(cuò)填或不填均無分。16 .數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的無關(guān)，是獨(dú)立于計(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ǔ)俱樂部名稱：自考樂園；俱樂部id:5346389（請(qǐng)牢記它哦在百度貼吧

7、的搜索*I中輸入俱樂部id,可以直接進(jìn)入俱樂部）；俱樂部url地址：自考樂園-心境隨緣，誠與天下自考人共勉！!自考樂園-分享快樂，你的快樂老家！!自考樂園一引領(lǐng)成功，你的精神樂園！自考樂園俱樂部，專注于自考，致力于成為全國最全，最優(yōu)的自考學(xué)習(xí)交流，資料共享平臺(tái)矩陣中第1個(gè)元素a”,則B31中存放的元素是。21 .已知一棵完全二叉樹中共有768結(jié)點(diǎn)，則該樹中共有個(gè)葉子結(jié)點(diǎn)。22 .已知一個(gè)圖的廣度優(yōu)先生成樹如右圖所示，則與此相應(yīng)的廣度優(yōu)先遍歷序列為。萬、©©©23 .在單鏈表上難以實(shí)現(xiàn)的排序方法有和。24 .在有序表(12,24,36,48,60,72,84)中二分

8、查找關(guān)鍵字72時(shí)所需進(jìn)行的關(guān)鍵字比較次數(shù)為。25 .多重表文件和倒排文件都?xì)w屬于文件。三、解答題(本大題共4小題，每小題5分，共20分)26 .畫出下列廣義表的共享結(jié)構(gòu)圖形表示P=(z),(x,y),(x,y),x),(z)27 .請(qǐng)畫出與下列二叉樹對(duì)應(yīng)的森林。28.已知一個(gè)無向圖的頂點(diǎn)集為a,b,c,d,e,其鄰接矩陣如下所示a'010011b10010cd00011e0110110110(1)畫出該圖的圖形；寫出相應(yīng)的遍歷序(2)根據(jù)鄰接矩陣從頂點(diǎn)a出發(fā)進(jìn)行深度優(yōu)先遍歷和廣度優(yōu)先遍歷,列。29.已知一個(gè)散列表如下圖所示:35203348590123456789101112其散列函數(shù)

9、為h(key)=key%13,處理沖突的方法為雙重散列法，探查序列為：hi=(h(key)+i*h1(key)%mi=0,1,m1其中h1(key)=key%11+1回答下列問題：(1)對(duì)表中關(guān)鍵字35,20,33和48進(jìn)行查找時(shí)，所需進(jìn)行的比較次數(shù)各為多少？(2)該散列表在等概率查找時(shí)查找成功的平均查找長(zhǎng)度為多少？四、算法閱讀題(本大題共4小題，每小題5分，共20分)俱樂部名稱：自考樂園；俱樂部id:5346389(請(qǐng)牢記它哦在百度貼吧的搜索*I中輸入俱樂部id,可以直接進(jìn)入俱樂部)；俱樂部url地址：自考樂園-心境隨緣，誠與天下自考人共勉！!自考樂園-分享快樂，你的快樂老家！!自考樂園一引

10、領(lǐng)成功，你的精神樂園！自考樂園俱樂部，專注于自考，致力于成為全國最全，最優(yōu)的自考學(xué)習(xí)交流，資料共享平臺(tái)30.下列算法的功能是比較兩個(gè)鏈串的大小，其返回值為：1當(dāng)S<S2comstr(si,S2)=00當(dāng)&=%1 當(dāng)S|S2請(qǐng)?jiān)诳瞻滋幪钊脒m當(dāng)?shù)膬?nèi)容。intcomstr(LinkStrings1,LinkStrings2)/si和s2為兩個(gè)鏈串的頭指針while(s1&&s2)if(s1>date<s2>date)return1；if(s1>date>s2>date)return1；)if()return1;if()return1;

11、)31 .閱讀下面的算法LinkListmynote(LinkListL)/L是不帶頭結(jié)點(diǎn)的單鏈表的頭指針if(L&&L->next)q=L;L=L>next;p=L;51: while(p>next)p=p>next;S2：p>next=q;q>next=NULL;)returnL;)請(qǐng)回答下列問題：(1)說明語句S1的功能;(2)說明語句組S2的功能；(3)設(shè)鏈表表示的線性表為(a1,a2,向)，寫出算法執(zhí)行后的返回值所表示的線性表。32 .假設(shè)兩個(gè)隊(duì)列共享一個(gè)循環(huán)向量空間(參見右下圖)，5rMEj萬遨%/2"其類型Queue2

12、定義如下：',typedefstructDateTypedataMaxSize;打俱樂部名稱：自考樂園；俱樂部id:5346389(請(qǐng)牢記它哦在百度貼吧的搜索*I中輸穴值樂部id,可以直接進(jìn)入俱樂部)；俱樂部url地址：自考樂園-心境隨緣，誠與天下自考人共勉！!自考樂園-分享快樂，你的快樂老家！!自考樂園一引領(lǐng)成功，你的精神樂園！自考樂園俱樂部，專注于自考，致力于成為全國最全，最優(yōu)的自考學(xué)習(xí)交流，資料共享平臺(tái)intfront2,rear2;Queue2;對(duì)于i=0或1,fronti和reari分別為第i個(gè)隊(duì)列的頭指針和尾指針。請(qǐng)對(duì)以下算法填空,實(shí)現(xiàn)第i個(gè)隊(duì)列的入隊(duì)操作。intEnQue

13、ue(Queue2*Q,inti,DateTypex)若第i個(gè)隊(duì)列不滿，則元素x入隊(duì)列，并返回1;否則返回0if(i<0|i>1)return0;if(Q>reari=Q>frontreturn0;Q>data=x;Q->reari=;return1;33 .已知二叉樹的存儲(chǔ)結(jié)構(gòu)為二叉鏈表，閱讀下面算法。typedefstructnodeDateTypedata;Structnode*next;ListNode;typedefListNode*LinkList;LinkListLeafhead=NULL;VoidInorder(BinTreeT)LinkLi

14、sts;If(T)Inorder(T>lchild);If(!T>lchild)&&(!T>rchild)s=(ListNode*)malloc(sizeof(ListNode);5 >data=T>data;6 >next=Leafhead;Leafhead=s;Inorder(T>rchild);對(duì)于如下所示的二叉樹(1)畫出執(zhí)行上述算法后所建立的結(jié)構(gòu)；(2)說明該算法的功能。五、算法設(shè)計(jì)題(本題共10分)34.閱讀下列函數(shù)arrange()intarrange(inta,int1,inth,intx)/1和h分別為數(shù)據(jù)區(qū)的下界和上

15、界inti,j,t;i=1;j=h;while(i<j)while(i<j&&aj>=x)j-；while(i<j&&aj>=x)i+；if(i<j)t=aj;aj=ai;ai=t;if(ai<x)returni;elsereturni1;(1)寫出該函數(shù)的功能；(2)寫一個(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ù)。全國2001年10月高等教育自學(xué)考試數(shù)據(jù)結(jié)構(gòu)試題參考答案一、

16、單項(xiàng)選擇題(本大題共15小題,每小題2分，共30分)1.D2.B3.C4.B6.A7.C8,D9,A11.D12.C13.D二、填空題(本大題共10小題，每小題2分，共20分)16.存儲(chǔ)(或存儲(chǔ)結(jié)構(gòu))18.進(jìn)棧和退棧5.D10.C14.C15.B課程代碼：0233117.p>next>next19. 1220. a4,821.38422.abefcdg23.快速排序、堆排序、希爾排序24.225.多關(guān)鍵字三、解答題(本大題共4小題，每小題5分，共20分)26.俱樂部名稱:進(jìn)入俱樂部)28.該圖的圖形為:深度優(yōu)先遍歷序列為：abdce廣度優(yōu)先遍歷序列為：abedc29. (1)對(duì)關(guān)鍵

17、字35、20、33和48進(jìn)行查找的比較次數(shù)為3、2、1、1;(2)平均查找長(zhǎng)度ASL=3211U55四、算法閱讀題(本大題共4小題，每小題5分，共20分)30. S1=S1>nexts2=s2>nexts2(或s2!=NULL或s2&&!s1)s1(或s1!=NULL或s1&&!s2)return031. (1)查詢鏈表的尾結(jié)點(diǎn)(2)將第一個(gè)結(jié)點(diǎn)鏈接到鏈表的尾部，作為新的尾結(jié)點(diǎn)(3)返回的線性表為(出例,，an,a1)32. (i+1)%2(或1i)Q>reari(Q>reari+)%Maxsize33.(1)LeafheadLeafhe

18、ad為頭(2)中序遍歷二叉樹，按遍歷序列中葉子結(jié)點(diǎn)數(shù)據(jù)域的值構(gòu)建一個(gè)以指針的逆序單鏈表(或按二叉樹中葉子結(jié)點(diǎn)數(shù)據(jù)自右至左鏈接成一個(gè)鏈表)五、算法設(shè)計(jì)題(本題共10分)34.(1)該函數(shù)的功能是：調(diào)整整數(shù)數(shù)組a口中的元素并返回分界值i,使所有vx的元素均落在a1.i上，使所有x的元素均落在ai+1.h上。自考樂園一心境隨緣，誠與天下自考人共勉！!自考樂園一分享快樂，你的快樂老家！!自考樂園一引領(lǐng)成功，你的精神樂園！自考樂園俱樂部，專注于自考，致力于成為全國最全，最優(yōu)的自考學(xué)習(xí)交流，資料共享平臺(tái)(2)intf(intb,intn)或intf(intb,intn)intp,q;intp,q;p=ar

19、range(b,0,n1,0);p=arrange(b,0,n1,1);q=arrange(b,p+1,n1,1);q=arrange(b,0,p,0);returnqp;returnpq;)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+)Aij=0；A.O(n)B.O(m+n+1)C.O(m+n)D.O(m*n)2 .在單鏈表中，指針p指向元素為x的結(jié)點(diǎn)，實(shí)現(xiàn)

20、“刪除x的后繼”的語句是(B)A.p=p-&gt;next;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;next=headJ(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.front=NULLB.Q.rear=NULLC.

21、Q.front=Q.rearD.Q.front!=Q.rear5 .設(shè)有兩個(gè)串T和P,求P在T中首次出現(xiàn)的位置的串運(yùn)算稱作(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)的二叉樹的高度至少為(C)A.3B.4C.5D.68 .已知二叉樹的先序序列為ABDECF,中序序列為DBEAFC,則后序序列為(D)A.DEBAFCB.DEFBCAC.DEBCFAD.DEBFCA9 .無向圖中一個(gè)頂點(diǎn)的度是指圖中(B)A.通過該頂點(diǎn)的簡(jiǎn)單路徑數(shù)B.與該頂點(diǎn)相鄰接的頂點(diǎn)數(shù)C.通過該頂點(diǎn)的回路數(shù)D.與該

22、頂點(diǎn)連通的頂點(diǎn)數(shù)10 .已知一個(gè)圖如下所示，從頂點(diǎn)a出發(fā)進(jìn)行廣度優(yōu)先遍歷可能得到的序列為(C)自考樂園-分享快樂，你的快樂老家！!自考樂園一引領(lǐng)成功，你的精神樂園!自考樂園俱樂部，專注于自考，致力于成為全國最全，最優(yōu)的自考學(xué)習(xí)交流，資料共享平臺(tái)A.acefbdB.acbdfeC.acbdefD.acdbfe11 .在下列排序方法中，平均時(shí)間性能為O（nlogn）且空間性能最好的是（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,3

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

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

25、&quot;,S2=&quot;&quot;,S3=&quot;book&quot;,貝US1,S2和S3依次聯(lián)接后的結(jié)果是_goodbook_o21 .假設(shè)三維數(shù)組A1098按行優(yōu)先順序存儲(chǔ)，若每個(gè)元素占3個(gè)存儲(chǔ)單元，且首地址為俱樂部名稱：自考樂園；俱樂部id:5346389（請(qǐng)牢記它哦在百度貼吧的搜索*I中輸入俱樂部id,可以直接進(jìn)入俱樂部）；俱樂部url地址：自考樂園-心境隨緣，誠與天下自考人共勉！!自考樂園-分享快樂，你的快樂老家！!自考樂園一引領(lǐng)成功，你的精神樂園！自考樂園俱樂部，專注于自考，致力于成為全國最全，最優(yōu)的自考學(xué)習(xí)交流，資料共享平臺(tái)

26、100,則元素A987的存儲(chǔ)地址是_2257。22 .已知在一棵含有n個(gè)結(jié)點(diǎn)的樹中，只有度為k的分支結(jié)點(diǎn)和度為0的葉子結(jié)點(diǎn)，則該樹中含有的葉子結(jié)點(diǎn)的數(shù)目為（n-1）/k）*（仁1）+1_或n-（n-1）/k_。23 .能夠成功完全拓?fù)渑判虻膱D一定是一個(gè)有向無環(huán)圖。24 .如果在排序前，關(guān)鍵字序列已接近正序或逆序，則在堆排序和快速排序兩者之中，選用堆排序較為適當(dāng)。25 .假設(shè)哈希表白表長(zhǎng)為m,哈希函數(shù)為H（key）,若用線性探查法解決沖突，則探查地址序列的形式表達(dá)為hi=（H（key）+I）/m。三、解答題（本大題共4小題，每小題5分，共20分）26 .假設(shè)通信電文使用的字符集為a,b,c,d,

27、e,f,名字符在電文中出現(xiàn)的頻度分別為：34,5,12,23,8,18,試為這6個(gè)字符設(shè)計(jì)哈夫曼編碼。請(qǐng)先畫出你所構(gòu)造的哈夫曼樹（要求樹中左孩子結(jié)點(diǎn)的權(quán)值小于右孩子結(jié)點(diǎn)的權(quán)值），然后分別寫出每個(gè)字符對(duì)應(yīng)的編碼。對(duì)應(yīng)哈夫曼編碼；a：11b: 1010c: 100d: 01e：1011f:0027 .已知一個(gè)圖如下所示，其頂點(diǎn)按a、b、c、d、ef順序存放在鄰接表的頂點(diǎn)表中，請(qǐng)畫出該圖的鄰接表，使得按此鄰接表進(jìn)行深度優(yōu)先遍歷時(shí)得到的頂點(diǎn)序列為acbefd,進(jìn)行廣度優(yōu)先遍歷時(shí)得到的頂點(diǎn)序列為acbdfe。題27國答案:a1bcd1ef>>|八|27題圖01234E>l£.

28、1-KI11+13H多2r28 .已知兩個(gè)4X5的稀疏矩陣的三元組表分別如下:0141612218234-253422801132122-22225693342544251請(qǐng)畫出這兩個(gè)稀疏矩陣之和的三元組表。解:1jw1132141622-42569427922題圖29 .從空樹起，依次插入關(guān)鍵字40,8,90,15,62,95,12,23,56,32,構(gòu)造一棵二叉排序樹。（1）畫出該二叉排序樹（2）畫出刪去該樹中元素值為90的結(jié)點(diǎn)之后的二叉排序樹。1562951556951223561223（3露32、四、算法閱讀題（本大題共4小題，每小題5分，共20分）30 .如圖所示，利用同一循環(huán)向量空

29、間實(shí)現(xiàn)兩個(gè)隊(duì)列，其類型Queue2定義如下：'Q-IrnnijdJtypedefstructDataTypedataMaxSize;intfront2,length2;Queue2;對(duì)于i=0或1,fronti和lengthi分別為第i個(gè)隊(duì)列的頭指針和長(zhǎng)度域。請(qǐng)?jiān)诳杖碧幪钊牒线m的內(nèi)容，實(shí)現(xiàn)第i個(gè)循環(huán)隊(duì)列的入隊(duì)操作。intEnQueue(Queue2*Q,inti,DataTypex)若第i個(gè)隊(duì)列不滿，則元素x入隊(duì)列，并返回1,否則返回0if(i&lt;0|i&gt;1)return0;if(1)return0;Q-&gt;data(2)=x;Q-&gt;

30、length(3)+;return1;解：(1) (Q-&gt;fronti+Q-&gt;lengthi%Maxsize=Q-&gt;front(i+1)%2(2) (Q-&gt;fronti+-&gt;lengthi%Maxsize(3) I31.某二叉樹的線索鏈表存儲(chǔ)結(jié)構(gòu)如圖(b)所示，其中p為指向根結(jié)點(diǎn)的指針，圖(a)為結(jié)點(diǎn)結(jié)構(gòu)。閱讀下列算法，并回答問題：(1)寫出執(zhí)行函數(shù)調(diào)用f(p)的輸出結(jié)果；(2)簡(jiǎn)述函數(shù)f的功能。voidf(BinThrTreet)(while(t)(printf(t-&gt;data);if(t-&gt;l

31、child)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)先搜索策略尋找一條經(jīng)過頂點(diǎn)vi的簡(jiǎn)單回路。數(shù)組cycle_path用于保存搜索過程中形成的回路，cycle_pathk=j(j>0)表示在回路中頂點(diǎn)vk的下一個(gè)頂點(diǎn)是vj。請(qǐng)?jiān)诳杖碧幪钊牒线m的內(nèi)容，使其成為一個(gè)完整的算法。vertexfirstedge已知鄰接表的頂點(diǎn)表結(jié)點(diǎn)結(jié)構(gòu)為：adjvexnext邊表結(jié)點(diǎn)EdgeNode結(jié)構(gòu)為：intcycle_pat

32、hMaxNum;intFindCycle(ALGraph*G,inti)若回路存在，則返回1,否則返回0intj;for(j=0;j&lt;G-&gt;n;j+)cycle_pathj=-1;returnDFSPath(G,i,i);自考樂園一心境隨緣，誠與天下自考人共勉！!自考樂園一分享快樂，你的快樂老家！!自考樂園一引領(lǐng)成功，你的精神樂園！自考樂園俱樂部，專注于自考，致力于成為全國最全，最優(yōu)的自考學(xué)習(xí)交流，資料共享平臺(tái)intDFSPath(ALGraph*G,intj,inti)(EdgeNode*p;intcycled=0;for(p=G-&gt;adjlistj

33、.firstedge;p&&!cycled;p=p-&gt;next)(cycle_pathj=p-&gt;adjvex;if(1)cycled=1;/已找至U回路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)cycled33.閱讀下列函數(shù)algo,并回答問題。(1)假設(shè)整型數(shù)組A1.8中的元素依次為(3,8,9,1,7,4,2,6)。執(zhí)行函數(shù)調(diào)用algo(A,

34、8)時(shí)，外層while的循環(huán)體執(zhí)行多少次？函數(shù)的返回值是多少？(2)簡(jiǎn)述函數(shù)algo(L,n)的功能。intalgo(intL,intn)(inti=0,j,s=1,t=n;while(i!=(n+1)/2)(intx=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;elset=i-1;if(i=0)return0;elseretur

35、nLi;(1)(2)(3)33題答案：(1)外循環(huán)執(zhí)行4次，函數(shù)返回值為3。(2)將A1至A8中不小于A1的元素進(jìn)行遞增排序，如調(diào)用algo(A,8)時(shí)最終排序結(jié)果為俱樂部名稱：自考樂園；俱樂部id:5346389(請(qǐng)牢記它哦在百度貼吧的搜索*I中輸入俱樂部id,可以直接進(jìn)入俱樂部)；俱樂部url地址：自考樂園-心境隨緣，誠與天下自考人共勉！!自考樂園-分享快樂，你的快樂老家！!自考樂園一引領(lǐng)成功，你的精神樂園！自考樂園俱樂部，專注于自考，致力于成為全國最全，最優(yōu)的自考學(xué)習(xí)交流，資料共享平臺(tái)21346789五、算法設(shè)計(jì)題(本大題共10分)34.假設(shè)以帶頭結(jié)點(diǎn)的單循環(huán)鏈表作非遞減有序線性表的存儲(chǔ)

36、結(jié)構(gòu)。請(qǐng)?jiān)O(shè)計(jì)一個(gè)時(shí)間復(fù)雜度為O(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題答案：Exam4(Linklist,L)listnode*p,*q;p=L-&gt;next;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;next;p-&g

37、t;next;2003年10月全國數(shù)據(jù)結(jié)構(gòu)試題(2006-7-252:07:00)1 .計(jì)算機(jī)識(shí)別、存儲(chǔ)和加工處理的對(duì)象被統(tǒng)稱為(b)A.數(shù)據(jù)B.數(shù)據(jù)元素C.數(shù)據(jù)結(jié)構(gòu)D.數(shù)據(jù)類型2 .在具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并彳鏈表仍然有序的時(shí)間復(fù)雜度是(b)A.O(1)B.O(n)C.O(nlogn)D.O(n2)3 .隊(duì)和棧的主要區(qū)別是(d)A.邏輯結(jié)構(gòu)不同B.存儲(chǔ)結(jié)構(gòu)不同C.所包含的運(yùn)算個(gè)數(shù)不同D.限定插入和刪除的位置不同4 .鏈棧與順序棧相比，比較明顯的優(yōu)點(diǎn)是(d)A.插入操作更加方便B.刪除操作更加方便C.不會(huì)出現(xiàn)下溢的情況D.不會(huì)出現(xiàn)上溢的情況5 .采用兩類不同存儲(chǔ)結(jié)構(gòu)的字符串可

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

39、組A按行優(yōu)先順序存儲(chǔ)，其中每個(gè)元素占1個(gè)存儲(chǔ)單元。若A11的存儲(chǔ)地址為420,A33的存儲(chǔ)地址為446,則A55的存儲(chǔ)地址為(c)A.470B.471C.472D.4739 .二叉樹中第5層上的結(jié)點(diǎn)個(gè)數(shù)最多為(d)A.8B.15C.16D.3210 .下列編碼中屬前綴碼的是(a)A.1,01,000,001B.1,01,011,010C.0,10,110,11D.0,1,00,1111 .如果某圖的鄰接矩陣是對(duì)角線元素均為零的上三角矩陣，則此圖是(d)A.有向完全圖B.連通圖C.強(qiáng)連通圖D.有向無環(huán)圖12 .對(duì)n個(gè)關(guān)鍵字的序列進(jìn)行快速排序，平均情況下的空間復(fù)雜度為(d)A.O(1)B.O(lo

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

41、結(jié)點(diǎn)中，數(shù)據(jù)元素所占的存儲(chǔ)量和整個(gè)結(jié)點(diǎn)所占的存儲(chǔ)量之比稱作_(存儲(chǔ)密度)Odatenext18 .已知鏈棧的結(jié)點(diǎn)結(jié)構(gòu)為棧頂指針為top,則實(shí)現(xiàn)將指針p所指結(jié)點(diǎn)插入棧頂?shù)恼Z句依次為和O19 .空串的長(zhǎng)度是0;空格串的長(zhǎng)度是(空格的數(shù)目_)o20 .假設(shè)一個(gè)6階的下三角矩陣B按列優(yōu)先順序壓縮存儲(chǔ)在一維數(shù)組A中，其中A0存儲(chǔ)矩陣的第一個(gè)元素b11,則A14存儲(chǔ)的元素是b63一。21 .在一棵度為3的樹中，度為2的結(jié)點(diǎn)個(gè)數(shù)是1,度為0的結(jié)點(diǎn)個(gè)數(shù)是6,則度為3的結(jié)點(diǎn)個(gè)數(shù)是2。22 .如圖所示的有向無環(huán)圖可以排出種不同的拓?fù)湫蛄小Ｗ钥紭穲@一心境隨緣，誠與天下自考人共勉！!自考樂園一分享快樂，你的快樂老家！

42、!自考樂園一引領(lǐng)成功，你的精神樂園！自考樂園俱樂部，專注于自考，致力于成為全國最全，最優(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)行二分查找的判定樹的高度為5o25 .在多重表文件中，次關(guān)鍵字索引的組織方式是將的記錄鏈接成一個(gè)鏈表。26 .對(duì)于單鏈表、單循環(huán)鏈表和雙向鏈表，如果僅僅知道一個(gè)指向鏈表中某結(jié)點(diǎn)的指針p,能否將p所指結(jié)點(diǎn)的數(shù)據(jù)元素與其確實(shí)存在的直接前驅(qū)交換？請(qǐng)對(duì)每一種鏈表作出判斷，若可以，寫出程序段；否則說明理由。datenext單鏈表和單循環(huán)鏈表

43、的結(jié)點(diǎn)結(jié)構(gòu)為priordatenext雙向鏈表的結(jié)點(diǎn)結(jié)構(gòu)為(1)單鏈表：(不可以，無法找到前驅(qū)接點(diǎn))(2)單循環(huán)鏈表(可以：q=p->next;while(q->next!=p)q=q->next;q->data<->p->data;(3)雙向鏈表(可以：p->prior->data<->p->data;)27 .假設(shè)通信電文使用的字符集為a,b,c,d,e,f,g,字符的哈夫曼編碼依次為：0110,10,110,111,00,0111和010。(1)請(qǐng)根據(jù)哈夫曼編碼畫出此哈夫曼樹，并在葉子結(jié)點(diǎn)中標(biāo)注相應(yīng)字符；(2)若這些

44、字符在電文中出現(xiàn)的頻度分別為：3,35,13,15,20,5和9,求該哈夫曼樹的帶權(quán)路徑長(zhǎng)度。28 .當(dāng)采用鄰接表作為圖的存儲(chǔ)結(jié)構(gòu)時(shí)，也可將鄰接表中的頂點(diǎn)表由順序結(jié)構(gòu)改為鏈表結(jié)構(gòu)。(1)請(qǐng)分別畫出這種鄰接表的頂點(diǎn)鏈表結(jié)點(diǎn)和邊表結(jié)點(diǎn)，并說明結(jié)點(diǎn)中各個(gè)域的作用；(2)對(duì)如圖所示的有向圖畫出這種鄰接表。29 .已知4階B-樹如圖所示。(1)分別畫出將關(guān)鍵字23和89相繼插入之后的B-樹。(2)畫出從插入之前的B-樹中刪除關(guān)鍵字51之后的B-樹。四、算法閱讀題(每小題5分，共20分)30 .閱讀下列函數(shù)algo,并回答問題：(1)假設(shè)隊(duì)列q中的元素為(2,4,5,7,8),其中"2"

45、;為隊(duì)頭元素。寫出執(zhí)行函數(shù)調(diào)用algo(&q)后的隊(duì)列q；簡(jiǎn)述算法algo的功能。voidalgo(Queue*Q)StackS;InitStack(&S);while(!QueueEmpty(Q)Push(&S,DeQueue(Q);while(!StackEmpty(&S)自考樂園一心境隨緣，誠與天下自考人共勉！!自考樂園一分享快樂，你的快樂老家！!自考樂園一引領(lǐng)成功，你的精神樂園！自考樂園俱樂部，專注于自考，致力于成為全國最全，最優(yōu)的自考學(xué)習(xí)交流，資料共享平臺(tái)EnQueue(Q,Pop(&S);)87542(2)隊(duì)列倒置31 .閱讀下列函數(shù)F,并回

46、答問題：(1)已知如圖所示的二叉樹以二叉鏈表作存儲(chǔ)結(jié)構(gòu)，rt為指向根結(jié)點(diǎn)的指針。寫出執(zhí)行函數(shù)調(diào)用F(rt)的輸出結(jié)果。(2)說明函數(shù)F的功能。voidF(BinTreeT)StackS;if(T)InitStack(&S);Push(&S,NULL);while(T)printf("%c",T->data);if(T->rchild)Push(&S,T->rchild);if(T->lchild)T=T->lchild;elseT=Pop(&S);)(2)前序遍歷二叉數(shù)vertexfirstedge32 .已知鄰

47、接表的頂點(diǎn)表結(jié)點(diǎn)結(jié)構(gòu)為adjvexnext邊表結(jié)點(diǎn)EdgeNode的結(jié)構(gòu)為下列算法計(jì)算有向圖G中頂點(diǎn)vi的入度。請(qǐng)?jiān)诳杖碧幪钊牒线m的內(nèi)容，使其成為一個(gè)完整的算法。intFindDegree(ALGraph*G,inti)/ALGraph為圖的鄰接表類型intdgree,j;EdgeNode*p;degree=(1);for(j=0;j<G->n;j+)p=G->adjlistj.firstedge;while(2)自考樂園一心境隨緣，誠與天下自考人共勉！!自考樂園一分享快樂，你的快樂老家！!自考樂園一引領(lǐng)成功，你的精神樂園！自考樂園俱樂部，專注于自考，致力于成為全國最全，最優(yōu)

48、的自考學(xué)習(xí)交流，資料共享平臺(tái)if(3)(degree+;break;)p=p->next;)returndegree;)(1)degree=0;p(3)p->adj=vidatanext33 .已知單鏈表的結(jié)點(diǎn)結(jié)構(gòu)為下列算法對(duì)帶頭結(jié)點(diǎn)的單鏈表L進(jìn)行簡(jiǎn)單選擇排序，使得L中的元素按值從小到大排列。請(qǐng)?jiān)诳杖碧幪钊牒线m的內(nèi)容，使其成為完整的算法。voidSelectSort(LinkedListL)(LinkedListp,q,min;DataTypercd;p=(1);while(p!=NULL)min=p;q=p->next;while(q!=NULL)if(2)min=q;q=

49、q->next;)if(3)rcd=p->data;p->data=min->data;min->data=rcd;)(4);)(1)L->next(2)q->data<min->data(3)p!=min(4)p=p->next五、算法設(shè)計(jì)題(本題10分)34 .設(shè)線性表A=(a1,a2,a3,an)以帶頭結(jié)點(diǎn)的單鏈表作為存儲(chǔ)結(jié)構(gòu)。編寫一個(gè)函數(shù)，對(duì)A進(jìn)行自考樂園一心境隨緣，誠與天下自考人共勉！!自考樂園一分享快樂，你的快樂老家！!自考樂園一引領(lǐng)成功，你的精神樂園！自考樂園俱樂部，專注于自考，致力于成為全國最全，最優(yōu)的自考學(xué)習(xí)交流，資

50、料共享平臺(tái)調(diào)整，使得當(dāng)n為奇數(shù)時(shí)A=(a2,a4,an-1,a1,a3,an),當(dāng)n為偶數(shù)時(shí)A=(a2,a4,an,a1,a3,an-1)。typedefstructnode(intx;structnode*next;NODE;typedefNODE*LinkList;voidadjust(LinkListheader)(NODE*pTmp=header;/用來保存偶數(shù)鏈表尾指針NODE*pCur=header->next;/鏈表遍歷指針NODE*pOddHdr=header->next;/奇數(shù)鏈表頭指針NODE*pOddTail=header->next;/奇數(shù)鏈表尾指針i

51、ntbisOdd=true;/奇數(shù)結(jié)點(diǎn)標(biāo)志，第一個(gè)結(jié)點(diǎn)是奇數(shù)結(jié)點(diǎn)if(NULL=pCur)/空鏈表，不需要處理return;while(pCur->next!=NULL)/從第二個(gè)結(jié)點(diǎn)開始遍歷(pCur=pCur->next;bisOdd=!bisOdd;if(bisOdd)/(這步錯(cuò)誤，未將原鏈表的接點(diǎn)連接)/奇數(shù)結(jié)點(diǎn)，加入奇數(shù)鏈表表尾pOddTail->next=pCur;pOddTail=pCur;else/偶數(shù)結(jié)點(diǎn)，加入偶數(shù)鏈表表尾pTmp->next=pCur;pTmp=pCur;pOddTail->next=NULL;/奇數(shù)鏈表表尾結(jié)點(diǎn)的next置空p

52、Tmp->next=pOddHdr;/奇數(shù)鏈表插入偶數(shù)鏈表表尾(這步錯(cuò)誤，未考慮最后接點(diǎn)的奇偶性。)return;自考樂園一心境隨緣，誠與天下自考人共勉！!自考樂園一分享快樂，你的快樂老家！!自考樂園一引領(lǐng)成功，你的精神樂園！自考樂園俱樂部，專注于自考，致力于成為全國最全，最優(yōu)的自考學(xué)習(xí)交流，資料共享平臺(tái)全國2004年1月高等教育自學(xué)考試數(shù)據(jù)結(jié)構(gòu)試題課程代碼：02331一、單項(xiàng)選擇題(本大題共15小題，每小題2分，共30分)在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其代碼填寫在題后的括號(hào)內(nèi)。錯(cuò)選、多選或未選均無分。1 .在數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)的邏輯結(jié)構(gòu)可以分成()A.內(nèi)部結(jié)構(gòu)和

53、外部結(jié)構(gòu)B.線性結(jié)構(gòu)和非線性結(jié)構(gòu)C.緊湊結(jié)構(gòu)和非緊揍結(jié)構(gòu)D.動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)2 .在以單鏈表為存儲(chǔ)結(jié)構(gòu)的線性表中，數(shù)據(jù)元素之間的邏輯關(guān)系用()A.數(shù)據(jù)元素的相鄰地址表示B.數(shù)據(jù)元素在表中的序號(hào)表示C.指向后繼元素的指針表示D.數(shù)據(jù)元素的值表示3 .設(shè)p指向單鏈表中的一個(gè)結(jié)點(diǎn)，s指向待插入的結(jié)點(diǎn)，則下述程序段的功能是()s->next=p->next;p->next=s;t=p->data;p->data=s->data;s->data=t;A.結(jié)點(diǎn)*p與結(jié)點(diǎn)*s的數(shù)據(jù)域互換B.在p所指結(jié)點(diǎn)的元素之前插入元素C.在p所指結(jié)點(diǎn)的元素之后插入元素D.在結(jié)點(diǎn)*p之前插入結(jié)點(diǎn)*s4 .棧和隊(duì)列都是(