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

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

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

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

5、3 .用某種排序方法對關鍵字序列序列的變化情況如下：25,84,21,47,D.O(n*e)15,27,68,35,20)進行排序時,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 .適于對動態查找表進行高效率查找的組織結構是（A.有序表B.分塊有序表15 .不定長文件是指（）A.文件的長度不固定C.字段的長度不固定C.三叉排序樹D.快速排序）D.線性鏈表B.記錄的長度不固定D.關鍵字項的長度不固定第二部分非選擇題（共70

6、分）二、填空題（本大題共10小題，每小題2分，若有兩個空格，每個空格1分，共20分）不寫解答過程，將正確的答案寫在每小題的空格內。錯填或不填均無分。16 .數據的邏輯結構是從邏輯關系上描述數據，它與數據的無關，是獨立于計算17 .在一個帶頭結點的單循環鏈表中，p指向尾結點的直接前驅，則指向頭結點的指針head可用p表示為head=。18 .棧頂的位置是隨著操作而變化的。19 .在串S="structure”中，以t為首字符的子串有個。20 .假設一個9階的上三角矩陣A按列優先順序壓縮存儲在一維數組B中，其中B0存儲俱樂部名稱：自考樂園；俱樂部id:5346389（請牢記它哦在百度貼吧

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

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

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

10、領成功，你的精神樂園！自考樂園俱樂部，專注于自考，致力于成為全國最全，最優的自考學習交流，資料共享平臺30.下列算法的功能是比較兩個鏈串的大小，其返回值為：1當S<S2comstr(si,S2)=00當&=%1 當S|S2請在空白處填入適當的內容。intcomstr(LinkStrings1,LinkStrings2)/si和s2為兩個鏈串的頭指針while(s1&&s2)if(s1>date<s2>date)return1；if(s1>date>s2>date)return1；)if()return1;if()return1;

11、)31 .閱讀下面的算法LinkListmynote(LinkListL)/L是不帶頭結點的單鏈表的頭指針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;)請回答下列問題：(1)說明語句S1的功能;(2)說明語句組S2的功能；(3)設鏈表表示的線性表為(a1,a2,向)，寫出算法執行后的返回值所表示的線性表。32 .假設兩個隊列共享一個循環向量空間(參見右下圖)，5rMEj萬遨%/2"其類型Queue2

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

13、ue(Queue2*Q,inti,DateTypex)若第i個隊列不滿，則元素x入隊列，并返回1;否則返回0if(i<0|i>1)return0;if(Q>reari=Q>frontreturn0;Q>data=x;Q->reari=;return1;33 .已知二叉樹的存儲結構為二叉鏈表，閱讀下面算法。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);對于如下所示的二叉樹(1)畫出執行上述算法后所建立的結構；(2)說明該算法的功能。五、算法設計題(本題共10分)34.閱讀下列函數arrange()intarrange(inta,int1,inth,intx)/1和h分別為數據區的下界和上

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)寫出該函數的功能；(2)寫一個調用上述函數實現下列功能的算法：對一整型數組bn中的元素進行重新排列，將所有負數均調整到數組的低下標端，將所有正數均調整到數組的高下標端，若有零值，則置于兩者之間，并返回數組中零元素的個數。全國2001年10月高等教育自學考試數據結構試題參考答案一、

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

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

18、ad為頭(2)中序遍歷二叉樹，按遍歷序列中葉子結點數據域的值構建一個以指針的逆序單鏈表(或按二叉樹中葉子結點數據自右至左鏈接成一個鏈表)五、算法設計題(本題共10分)34.(1)該函數的功能是：調整整數數組a口中的元素并返回分界值i,使所有vx的元素均落在a1.i上，使所有x的元素均落在ai+1.h上。自考樂園一心境隨緣，誠與天下自考人共勉！!自考樂園一分享快樂，你的快樂老家！!自考樂園一引領成功，你的精神樂園！自考樂園俱樂部，專注于自考，致力于成為全國最全，最優的自考學習交流，資料共享平臺(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數據結構試題一、單項選擇題(本大題共15小題，每小題2分，共30分。在每小題的四個備選答案中，選出一個正確答案，并將正確答案的序號填在題干的括號內)1 .下面程序段的時間復雜度是(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的結點，實現

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且表長大于1的單循環鏈表中，指針p指向表中某個結點，若p-&gt;next-&gt;next=headJ(D)A.p指向頭結點B.p指向尾結點C.*p的直接后繼是頭結點D.*P的直接后繼是尾結點4 .判定“帶頭結點的鏈隊列為空”的條件是(C)A.Q.front=NULLB.Q.rear=NULLC.

21、Q.front=Q.rearD.Q.front!=Q.rear5 .設有兩個串T和P,求P在T中首次出現的位置的串運算稱作(D)A.聯接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.DEFBCAC.DEBCFAD.DEBFCA9 .無向圖中一個頂點的度是指圖中(B)A.通過該頂點的簡單路徑數B.與該頂點相鄰接的頂點數C.通過該頂點的回路數D.與該

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

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

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

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

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

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

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

29、間實現兩個隊列，其類型Queue2定義如下：'Q-IrnnijdJtypedefstructDataTypedataMaxSize;intfront2,length2;Queue2;對于i=0或1,fronti和lengthi分別為第i個隊列的頭指針和長度域。請在空缺處填入合適的內容，實現第i個循環隊列的入隊操作。intEnQueue(Queue2*Q,inti,DataTypex)若第i個隊列不滿，則元素x入隊列，并返回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.某二叉樹的線索鏈表存儲結構如圖(b)所示，其中p為指向根結點的指針，圖(a)為結點結構。閱讀下列算法，并回答問題：(1)寫出執行函數調用f(p)的輸出結果；(2)簡述函數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.下列函數FindCycle(G,i)的功能是，對一個采用鄰接表作存儲結構的有向圖G,利用深度優先搜索策略尋找一條經過頂點vi的簡單回路。數組cycle_path用于保存搜索過程中形成的回路，cycle_pathk=j(j>0)表示在回路中頂點vk的下一個頂點是vj。請在空缺處填入合適的內容，使其成為一個完整的算法。vertexfirstedge已知鄰接表的頂點表結點結構為：adjvexnext邊表結點EdgeNode結構為：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);自考樂園一心境隨緣，誠與天下自考人共勉！!自考樂園一分享快樂，你的快樂老家！!自考樂園一引領成功，你的精神樂園！自考樂園俱樂部，專注于自考，致力于成為全國最全，最優的自考學習交流，資料共享平臺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.閱讀下列函數algo,并回答問題。(1)假設整型數組A1.8中的元素依次為(3,8,9,1,7,4,2,6)。執行函數調用algo(A,

34、8)時，外層while的循環體執行多少次？函數的返回值是多少？(2)簡述函數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)外循環執行4次，函數返回值為3。(2)將A1至A8中不小于A1的元素進行遞增排序，如調用algo(A,8)時最終排序結果為俱樂部名稱：自考樂園；俱樂部id:5346389(請牢記它哦在百度貼吧的搜索*I中輸入俱樂部id,可以直接進入俱樂部)；俱樂部url地址：自考樂園-心境隨緣，誠與天下自考人共勉！!自考樂園-分享快樂，你的快樂老家！!自考樂園一引領成功，你的精神樂園！自考樂園俱樂部，專注于自考，致力于成為全國最全，最優的自考學習交流，資料共享平臺21346789五、算法設計題(本大題共10分)34.假設以帶頭結點的單循環鏈表作非遞減有序線性表的存儲

36、結構。請設計一個時間復雜度為O(n)的算法，刪除表中所有數值相同的多余元素，并釋放結點空間。例如：(7,10,10,21,30,42,42,42,51,70)經算法操作后變為(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月全國數據結構試題(2006-7-252:07:00)1 .計算機識別、存儲和加工處理的對象被統稱為(b)A.數據B.數據元素C.數據結構D.數據類型2 .在具有n個結點的有序單鏈表中插入一個新結點并彳鏈表仍然有序的時間復雜度是(b)A.O(1)B.O(n)C.O(nlogn)D.O(n2)3 .隊和棧的主要區別是(d)A.邏輯結構不同B.存儲結構不同C.所包含的運算個數不同D.限定插入和刪除的位置不同4 .鏈棧與順序棧相比，比較明顯的優點是(d)A.插入操作更加方便B.刪除操作更加方便C.不會出現下溢的情況D.不會出現上溢的情況5 .采用兩類不同存儲結構的字符串可

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

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

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

41、結點中，數據元素所占的存儲量和整個結點所占的存儲量之比稱作_(存儲密度)Odatenext18 .已知鏈棧的結點結構為棧頂指針為top,則實現將指針p所指結點插入棧頂的語句依次為和O19 .空串的長度是0;空格串的長度是(空格的數目_)o20 .假設一個6階的下三角矩陣B按列優先順序壓縮存儲在一維數組A中，其中A0存儲矩陣的第一個元素b11,則A14存儲的元素是b63一。21 .在一棵度為3的樹中，度為2的結點個數是1,度為0的結點個數是6,則度為3的結點個數是2。22 .如圖所示的有向無環圖可以排出種不同的拓撲序列。自考樂園一心境隨緣，誠與天下自考人共勉！!自考樂園一分享快樂，你的快樂老家！

42、!自考樂園一引領成功，你的精神樂園！自考樂園俱樂部，專注于自考，致力于成為全國最全，最優的自考學習交流，資料共享平臺23 .利用篩選法將關鍵字序列(37,66,48,29,31,75)建成的大根堆為(75,66,48,29,31,37)。24 .對長度為20的有序表進行二分查找的判定樹的高度為5o25 .在多重表文件中，次關鍵字索引的組織方式是將的記錄鏈接成一個鏈表。26 .對于單鏈表、單循環鏈表和雙向鏈表，如果僅僅知道一個指向鏈表中某結點的指針p,能否將p所指結點的數據元素與其確實存在的直接前驅交換？請對每一種鏈表作出判斷，若可以，寫出程序段；否則說明理由。datenext單鏈表和單循環鏈表

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

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

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

46、答問題：(1)已知如圖所示的二叉樹以二叉鏈表作存儲結構，rt為指向根結點的指針。寫出執行函數調用F(rt)的輸出結果。(2)說明函數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)前序遍歷二叉數vertexfirstedge32 .已知鄰

47、接表的頂點表結點結構為adjvexnext邊表結點EdgeNode的結構為下列算法計算有向圖G中頂點vi的入度。請在空缺處填入合適的內容，使其成為一個完整的算法。intFindDegree(ALGraph*G,inti)/ALGraph為圖的鄰接表類型intdgree,j;EdgeNode*p;degree=(1);for(j=0;j<G->n;j+)p=G->adjlistj.firstedge;while(2)自考樂園一心境隨緣，誠與天下自考人共勉！!自考樂園一分享快樂，你的快樂老家！!自考樂園一引領成功，你的精神樂園！自考樂園俱樂部，專注于自考，致力于成為全國最全，最優

48、的自考學習交流，資料共享平臺if(3)(degree+;break;)p=p->next;)returndegree;)(1)degree=0;p(3)p->adj=vidatanext33 .已知單鏈表的結點結構為下列算法對帶頭結點的單鏈表L進行簡單選擇排序，使得L中的元素按值從小到大排列。請在空缺處填入合適的內容，使其成為完整的算法。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五、算法設計題(本題10分)34 .設線性表A=(a1,a2,a3,an)以帶頭結點的單鏈表作為存儲結構。編寫一個函數，對A進行自考樂園一心境隨緣，誠與天下自考人共勉！!自考樂園一分享快樂，你的快樂老家！!自考樂園一引領成功，你的精神樂園！自考樂園俱樂部，專注于自考，致力于成為全國最全，最優的自考學習交流，資

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

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

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

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