數(shù)據(jù)結(jié)構(gòu)02331

1、<p>　　全國2001年10月自考數(shù)據(jù)結(jié)構(gòu)試題</p><p>　　課程代碼：02331</p><p>　　第一部分 選擇題(30分)</p><p>　　單項選擇題（本大題共15小題，每小題2分，共30分）在每小題列出的四個選項中只有一個選項是符合題目要求的，請將正確選項前的字母填在題后的括號內(nèi)。</p><p>　　1．算

2、法指的是（ ）</p><p>　　A．計算機程序 B．解決問題的計算方法</p><p>　　C．排序算法 D．解決問題的有限運算序列</p><p>　　2．線性表采用鏈式存儲時，結(jié)點的存儲地址（ ）</p><p><b>　　A．必須是不連續(xù)

3、的</b></p><p><b>　　B．連續(xù)與否均可</b></p><p><b>　　C．必須是連續(xù)的</b></p><p>　　D．和頭結(jié)點的存儲地址相連續(xù)</p><p>　　3．將長度為n的單鏈表鏈接在長度為m的單鏈表之后的算法的時間復雜度為（ ）</p>

4、<p>　　A．O（1） B．O（n） C．O（m） D．O（m+n）</p><p>　　4．由兩個棧共享一個向量空間的好處是：（ ）</p><p>　　A．減少存取時間，降低下溢發(fā)生的機率</p><p>　　B．節(jié)省存儲空間，降低上溢發(fā)生的機率</p><p>　　C．減少存取時間，降低上

5、溢發(fā)生的機率</p><p>　　D．節(jié)省存儲空間，降低下溢發(fā)生的機率</p><p>　　5．設(shè)數(shù)組data[m]作為循環(huán)隊列SQ的存儲空間，front為隊頭指針，rear為隊尾指針，則執(zhí)行出隊操作后其頭指針front值為（ ）</p><p>　　A．front=front+1 B．front=(front+1)%(m-1)&

6、lt;/p><p>　　C．front=(front-1)%m D．front=(front+1)%m</p><p>　　6．如下陳述中正確的是（ ）</p><p>　　A．串是一種特殊的線性表 B．串的長度必須大于零</p><p>　　C．串中元素只能是字母 D．空串就是空白串

7、</p><p>　　7．若目標串的長度為n，模式串的長度為[n/3]，則執(zhí)行模式匹配算法時，在最壞情況下的時間復雜度是（ ）</p><p>　　A．O（） B．O（n） C．O（n2） D．O（n3）</p><p>　　8．一個非空廣義表的表頭（ ）</p><p>　　A．不可能是子表

8、 B．只能是子表</p><p>　　C．只能是原子 D．可以是子表或原子</p><p>　　9．假設(shè)以帶行表的三元組表表示稀疏矩陣，則和下列行表</p><p>　　對應的稀疏矩陣是（ ）</p><p>　　10．在一棵度為3的樹中,度為3的結(jié)點個數(shù)為2,度為2 的結(jié)點個數(shù)為

9、1,則度為0的結(jié)點個數(shù)為( )</p><p>　　A．4 B．5 C．6 D．7</p><p>　　11．在含n個頂點和e條邊的無向圖的鄰接矩陣中,零元素的個數(shù)為( )</p><p>　　A．e B．2e C．n2－e D．n2－2e&l

10、t;/p><p>　　12．假設(shè)一個有n個頂點和e條弧的有向圖用鄰接表表示,則刪除與某個頂點vi相關(guān)的所有弧的時間復雜度是( )</p><p>　　A．O(n) B．O(e) C．O(n+e) D．O(n*e)</p><p>　　13．用某種排序方法對關(guān)鍵字序列（25，84，21，47，15，27，68，35，20）進行排

11、序時，序列的變化情況如下：</p><p>　　20，15，21，25，47，27，68，35，84</p><p>　　15，20，21，25，35，27，47，68，84</p><p>　　15，20，21，25，27，35，47，68，84</p><p>　　則所采用的排序方法是（ ）</p><p>　

12、　A．選擇排序 B．希爾排序 C．歸并排序 D．快速排序</p><p>　　14．適于對動態(tài)查找表進行高效率查找的組織結(jié)構(gòu)是（ ）</p><p>　　A．有序表 B．分塊有序表 C．三叉排序樹 D．線性鏈表</p><p>　　15．不定長文件是指（ ）</p><p>　　A．文件的長度不固定

13、 B．記錄的長度不固定</p><p>　　C．字段的長度不固定 D．關(guān)鍵字項的長度不固定</p><p>　　第二部分 非選擇題（共70分）</p><p>　　二、填空題（本大題共10小題，每小題2分，若有兩個空格，每個空格1分，共20分）不寫解答過程，將正確的答案寫在每小題的空格內(nèi)。錯填或不填均無分。</p&

14、gt;<p>　　16．數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的 無關(guān)，是獨立于計算機的。</p><p>　　17．在一個帶頭結(jié)點的單循環(huán)鏈表中，p指向尾結(jié)點的直接前驅(qū)，則指向頭結(jié)點的指針head可用p表示為head= 。</p><p>　　18．棧頂?shù)奈恢檬请S著 操作而變化的。</p>&l

15、t;p>　　19．在串S=“structure”中，以t為首字符的子串有 個。</p><p>　　20．假設(shè)一個9階的上三角矩陣A按列優(yōu)先順序壓縮存儲在一維數(shù)組B中，其中B[0]存儲矩陣中第1個元素a1,1,則B[31]中存放的元素是 。</p><p>　　21．已知一棵完全二叉樹中共有768結(jié)點，則該樹中共有 個葉子結(jié)點。

16、 </p><p>　　22．已知一個圖的廣度優(yōu)先生成樹如右圖所示，則與此相 </p><p>　　應的廣度優(yōu)先遍歷序列為 。 </p><p>　　23．在單鏈表上難以實現(xiàn)的排序方法有

17、和 。 </p><p>　　24．在有序表（12，24，36，48，60，72，84）中二分查找關(guān)鍵字72時所需進行的關(guān)鍵字比較次數(shù)為 。 </p><p>　　25．多重表文件和倒排文件都歸屬于

18、 文件。 </p><p>　　三、解答題（本大題共4小題，每小題5分，共20分）</p><p>　　26．畫出下列廣義表的共享結(jié)構(gòu)圖形表示</p><p>　　P=（（（z）,(x,y)）,((x,y),x),(z)）</p><p>　　27．請畫出與下列二叉樹對應的森林。</p>

19、;<p>　　28．已知一個無向圖的頂點集為{a, b, c, d, e} ,其鄰接矩陣如下所示</p><p><b>　　a</b></p><p><b>　　b </b></p><p><b>　　c</b></p><p><b>　　d&

20、lt;/b></p><p><b>　　e</b></p><p>　　(1)畫出該圖的圖形；</p><p>　　（2）根據(jù)鄰接矩陣從頂點a出發(fā)進行深度優(yōu)先遍歷和廣度優(yōu)先遍歷，寫出相應的遍歷序列。</p><p>　　29．已知一個散列表如下圖所示：</p><p>　　0 1

21、 2 3 4 5 6 7 8 9 10 11 12 </p><p>　　其散列函數(shù)為h(key)=key%13, 處理沖突的方法為雙重散列法，探查序列為：</p><p>　　hi=(h(key)+*h1(key))%m =0,1,…，m－1</p><p><b>　　其中</b>&l

22、t;/p><p>　　h1(key)=key%11+1</p><p><b>　　回答下列問題：</b></p><p>　?。?）對表中關(guān)鍵字35，20，33和48進行查找時，所需進行的比較次數(shù)各為多少？</p><p>　　（2）該散列表在等概率查找時查找成功的平均查找長度為多少？</p><p&g

23、t;　　四、算法閱讀題（本大題共4小題，每小題5分，共20分）</p><p>　　30．下列算法的功能是比較兩個鏈串的大小，其返回值為：</p><p>　　comstr(s1,s2)= </p><p>　　請在空白處填入適當?shù)膬?nèi)容。</p><p>　　int comstr(LinkString s1,LinkString s2)

24、 </p><p>　　{//s1和s2為兩個鏈串的頭指針</p><p>　　while(s1&&s2){</p><p>　　if(s1－>date<s2－>date)return－1；</p><p>　　if(s1－>date>s2－>date)return1；</p>

25、<p><b>　?、?；</b></p><p><b>　?、?；</b></p><p><b>　　} </b></p><p>　　if( ③ )return－1；</p><p>　　if( ④ )return1；<

26、/p><p><b>　?、?；</b></p><p><b>　　}</b></p><p><b>　　①</b></p><p><b>　?、?lt;/b></p><p><b>　?、?lt;/b></

27、p><p><b>　?、?lt;/b></p><p><b>　?、?lt;/b></p><p>　　31．閱讀下面的算法</p><p>　　LinkList mynote(LinkList L)</p><p>　　{//L是不帶頭結(jié)點的單鏈表的頭指針</p><

28、;p>　　if(L&&L->next){</p><p>　　q=L；L=L－>next；p=L；</p><p>　　S1： while(p－>next) p=p－>next；</p><p>　　S2： p－>next=q；q－>next=NULL；</p><

29、p><b>　　}</b></p><p>　　return L；</p><p><b>　　}</b></p><p><b>　　請回答下列問題：</b></p><p>　?。?）說明語句S1的功能；</p><p>　?。?）說明語句組

30、S2的功能；</p><p>　?。?）設(shè)鏈表表示的線性表為（a1,a2, …,an）,寫出算法執(zhí)行后的返回值所表示的線性表。</p><p>　　32．假設(shè)兩個隊列共享一個循環(huán)向量空間（參見右下圖），</p><p>　　其類型Queue2定義如下：</p><p>　　typedef struct{</p><p>

31、;　　DateType data[MaxSize]；</p><p>　　int front[2],rear[2]；</p><p><b>　　}Queue2；</b></p><p>　　對于i=0或1，front[i]和rear[i]分別為第i個隊列的頭指針和尾指針。請對以下算法填空，實現(xiàn)第i個隊列的入隊操作。</p>&l

32、t;p>　　int EnQueue (Queue2*Q,int i,DateType x)</p><p>　　{//若第 i個隊列不滿，則元素x入隊列，并返回1；否則返回0</p><p>　　if(i<0||i>1)return 0；</p><p>　　if(Q－>rear[i]==Q－>front[ ① ]return

33、0；</p><p>　　Q－>data[ ② ]=x；</p><p>　　Q－>rear[i]=[ ③ ];</p><p><b>　　return1；</b></p><p><b>　　} </b></p><p><

34、b>　?、?lt;/b></p><p><b>　?、?lt;/b></p><p><b>　　③</b></p><p>　　33．已知二叉樹的存儲結(jié)構(gòu)為二叉鏈表，閱讀下面算法。</p><p>　　typedef struct node {</p><p>　　

35、DateType data；</p><p>　　Struct node * next；</p><p>　　}ListNode；</p><p>　　typedef ListNode * LinkList ；</p><p>　　LinkList Leafhead=NULL；</p><p>　　Void Inord

36、er (BinTree T)</p><p><b>　　{</b></p><p>　　LinkList s；</p><p><b>　　If(T){</b></p><p>　　Inorder(T－>lchild)；</p><p>　　If ((!T－>l

37、child)&&(!T－>rchild)){</p><p>　　s=(ListNode*)malloc(sizeof(ListNode))；</p><p>　　s－>data=T－>data；</p><p>　　s－>next=Leafhead；</p><p>　　Leafhead=s；<

38、/p><p><b>　　}</b></p><p>　　Inorder(T－>rchild)；</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　對于如下所示的二叉樹</p><p

39、>　?。?）畫出執(zhí)行上述算法后所建立的結(jié)構(gòu)；</p><p>　　（2）說明該算法的功能。</p><p>　　五、算法設(shè)計題（本題共10分）</p><p>　　34．閱讀下列函數(shù)arrange()</p><p>　　int arrange(int a[],int 1,int h,int x)</p><p>

40、;　　{//1和h分別為數(shù)據(jù)區(qū)的下界和上界</p><p>　　int i,j,t；</p><p><b>　　i=1；j=h；</b></p><p>　　while(i<j){</p><p>　　while(i<j && a[j]>=x)j--；</p><p

41、>　　while(i<j && a[j]>=x)i++；</p><p><b>　　if(i<j)</b></p><p>　　{ t=a[j]；a[j]=a[i]；a[i]=t；}</p><p><b>　　}</b></p><p>　　if(a[i

42、]<x) return i；</p><p>　　else return i－1；</p><p><b>　　}</b></p><p>　?。?）寫出該函數(shù)的功能；</p><p>　　（2）寫一個調(diào)用上述函數(shù)實現(xiàn)下列功能的算法：對一整型數(shù)組b[n]中的元素進行重新排列，將所有負數(shù)均調(diào)整到數(shù)組的低下標端，將

43、所有正數(shù)均調(diào)整到數(shù)組的高下標端，若有零值，則置于兩者之間，并返回數(shù)組中零元素的個數(shù)。</p><p>　　全國2001年10月自考數(shù)據(jù)結(jié)構(gòu)試題參考答案</p><p>　　課程代碼：02331</p><p>　　單項選擇題（本大題共15小題，每小題2分，共30分）</p><p>　　1．D２．Ｂ３．Ｃ４．Ｂ５．Ｄ６．Ａ

44、７．Ｃ８，Ｄ９，Ａ10．Ｃ11．Ｄ12．Ｃ13．Ｄ14．Ｃ15．Ｂ</p><p>　　二、填空題（本大題共10小題，每小題2分，共20分）</p><p>　　16．存儲（或存儲結(jié)構(gòu)）17.p－＞next－＞next18．進棧和退棧19．1220．a(chǎn)4,821．38422．a(chǎn)befcdg</p>

45、<p>　　23．快速排序、堆排序、希爾排序</p><p>　　24．２25.多關(guān)鍵字</p><p>　　三、解答題（本大題共4小題，每小題5分，共20分）</p><p><b>　　26．</b></p><p>　　圖1 圖2</p><p>

46、<b>　　27．</b></p><p>　　28．該圖的圖形為： </p><p>　　深度優(yōu)先遍歷序列為：abdce</p><p>　　廣度優(yōu)先遍歷序列為：abedc</p><p>　　29．（１）對關(guān)鍵字35、20、33和48進行查找的比較次數(shù)為３、２、１、１；<

47、;/p><p><b>　　（２）平均查找長度</b></p><p>　　四、算法閱讀題（本大題共4小題，每小題5分，共20分）</p><p>　　30． ①S1=S1－>next</p><p>　?、趕2=s2－>next</p><p>　?、踫2(或s2!=NULL或s2&a

48、mp;&!s1)</p><p>　?、躶1(或s1!=NULL或s1&&!s2)</p><p><b>　?、輗eturn 0</b></p><p>　　31.（1）查詢鏈表的尾結(jié)點</p><p>　　（2）將第一個結(jié)點鏈接到鏈表的尾部，作為新的尾結(jié)點</p><p&g

49、t;　　（3）返回的線性表為（a2,a3,…,an,a1）</p><p>　　32. ①(i＋1)%2(或1－i)</p><p>　　②Q－>rear[i]</p><p>　?、?Q－>rear[i]＋)%Maxsize</p><p>　　（2）中序遍歷二叉樹，按遍歷序列中葉子結(jié)點數(shù)據(jù)域的值構(gòu)建一個以Leafhead為頭指

50、針的逆序單鏈表（或按二叉樹中葉子結(jié)點數(shù)據(jù)自右至左鏈接成一個鏈表）。</p><p>　　五、算法設(shè)計題（本題共10分）</p><p>　　34．（1）該函數(shù)的功能是：調(diào)整整數(shù)數(shù)組a[]中的元素并返回分界值i，使所有＜x的元素均落在a[1..i]上，使所有≥x的元素均落在a[i＋1..h]上。</p><p>　?。?）int f(int b[],int n)

51、 或 int f(int b[],int n)</p><p>　　{ {</p><p>　　int p,q； int p,q；</p><p>　　p=arrange(b,0,n－1,0)； p=arrange(b,0,n－1,1)；</p><p>

52、;　　q= arrange(b,p+1,n－1,1)； q= arrange(b,0,p,0)；</p><p>　　return q－p； return p－q；</p><p>　　} }</p><p>　　浙江省2002年1月高等教育自學考試</p><p>&l

53、t;b>　　數(shù)據(jù)結(jié)構(gòu)試題</b></p><p>　　課程代碼：02331</p><p>　　一、單項選擇題(在每小題的四個備選答案中，選出一個正確答案，并將正確答案的序號填在題干的括號內(nèi)。每小題2分，共38分)</p><p>　　1.某二叉樹的先序序列和后序序列正好相同，則該二叉樹一定是( )的二叉樹。</p><

54、p>　　A.空或只有一個結(jié)點B.高度等于其結(jié)點數(shù)</p><p>　　C.任一結(jié)點無左孩子D.任一結(jié)點無右孩子</p><p>　　2.下列排序算法中，時間復雜度不受數(shù)據(jù)初始狀態(tài)影響，恒為O(log2n)的是( )</p><p>　　A.堆排序B.冒泡排序</p><p>　　C.直接選擇排序

55、D.快速排序</p><p>　　3.下列排序算法中，( )算法可能會出現(xiàn)下面情況：初始數(shù)據(jù)有序時，花費的時間反而最多。</p><p>　　A.堆排序B.冒泡排序</p><p>　　C.快速排序D.SHELL排序</p><p>　　4.一個棧的輸入序列為1 2 3 4 5，則下列序列中不可

56、能是棧的輸出序列的是( )</p><p>　　A. 2 3 4 1 5B. 5 4 1 3 2</p><p>　　C. 2 3 1 4 5D. 1 5 4 3 2</p><p>　　5.設(shè)循環(huán)隊列中數(shù)組的下標范圍是1～n，其頭尾指針分別為f和r，則其元素個數(shù)為( )</p><p>　　A.

57、 r-fB. r-f+1</p><p>　　C. (r-f) mod n+1D. (r-f+n) mod n</p><p>　　6.若某鏈表最常用的操作是在最后一個結(jié)點之后插入一個結(jié)點和刪除最后一個結(jié)點，則采用( )存儲方式最節(jié)省時間。</p><p>　　A.單鏈表B.雙鏈表</p><p

58、>　　C.帶頭結(jié)點的雙循環(huán)鏈表D.單循環(huán)鏈表</p><p>　　7.在有n個結(jié)點的二叉鏈表中，值為非空的鏈域的個數(shù)為( )</p><p>　　A. n-1B. 2n-1</p><p>　　C. n+1D. 2n+1</p><p>　　8.一棵左右子樹均不空的二叉樹在先序線索化后，其

59、空指針域數(shù)為( )</p><p>　　A. 0B. 1</p><p>　　C. 2D.不確定</p><p>　　9.數(shù)組A［５］［６］的每個元素占5個單元，將其按行優(yōu)先次序存儲在起始地址為1000的連續(xù)的內(nèi)存單元中，則元素A［５，５］的地址為( )</p><p>　　A. 1140

60、B. 1145</p><p>　　C. 1120D. 1125</p><p>　　10.求最短路徑的DIJKSTRA算法的時間復雜度為( )</p><p>　　A. O(n)B. O(n+e)</p><p>　　C. O(n2)D. O(n×e)</p>

61、<p>　　11.對有18個元素的有序表作二分查找，則查找A［3］的比較序列的下標依次為( )</p><p>　　A. 1，2，3B. 9，5，2，3</p><p>　　C. 9，5，3D. 9，4，2，3</p><p>　　12.快速排序算法在最好情況下的時間復雜度為( )</p>&l

62、t;p>　　A. O(n)B. O(nlog2n)</p><p>　　C. O(n2)D. O(log2n)</p><p>　　13.下列排序算法中，某一趟結(jié)束后未必能選出一個元素放在其最終位置上的是( )</p><p>　　A.堆排序B.冒泡排序</p><p>　　C.快速排序

63、D.直接插入排序</p><p>　　14.二叉樹在線索化后，仍不能有效求解的問題是( )</p><p>　　A.先序線索二叉樹中求先序后繼</p><p>　　B.中序線索二叉樹中求中序后繼</p><p>　　C.中序線索二叉樹中求中序前趨</p><p>　　D.后序線索二叉樹中求后序后繼&

64、lt;/p><p>　　15.DFS算法的時間復雜度為( )</p><p>　　A. O(n)B. O(n3)</p><p>　　C. O(n2)D. O(n+e)</p><p>　　16.隊列操作的原則是( )</p><p>　　A.先進先出B.后進先出<

65、/p><p>　　C.只能進行插入D.只能進行刪除</p><p>　　17.有64個結(jié)點的完全二叉樹的深度為( )(根的層次為1)。</p><p>　　A. 8B. 7</p><p>　　C. 6D. 5</p><p>　　18.在平衡二叉樹中插入一個結(jié)點后造成了不平衡

66、，設(shè)最低的不平衡結(jié)點為A，并已知A的左孩子的平衡因子為-1，右孩子的平衡因子為0，則應作( )型調(diào)整以使其平衡。</p><p>　　A. LLB. LR</p><p>　　C. RLD. RR</p><p>　　19.數(shù)據(jù)表A中有10000個元素，如果僅要求求出其中最大的10個元素，則采用( )排序算法最節(jié)省時間。&

67、lt;/p><p>　　A.堆排序B.希爾排序</p><p>　　C.快速排序D.直接選擇排序</p><p>　　二、判斷題(判斷下列各題，正確的在題后括號內(nèi)打“√”，錯的打“×”。每小題1分，共10分)</p><p>　　1.給出不同的輸入序列建造二叉排序樹，一定得到不同的二叉排序樹。( )<

68、;/p><p>　　2.由于希爾排序的最后一趟與直接插入排序過程相同，因此前者一定比后者花費的時間多。( )</p><p>　　3.在對鏈隊列作出隊操作時，不會改變front指針的值。( )</p><p>　　4.若一個棧的輸入序列為123…n，其輸出序列的第一個元素為n，則其輸出序列的每個元素ai一定滿足ai=n-i+1(i=1,2...,n)(

69、 )</p><p>　　5.二叉樹中的葉子結(jié)點就是二叉樹中沒有左右子樹的結(jié)點。( )</p><p>　　6.一棵樹中的葉子結(jié)點數(shù)一定等于與其對應的二叉樹中的葉子結(jié)點數(shù)。( )</p><p>　　7.有向圖用鄰接矩陣表示后，頂點i的人度等于鄰接矩陣中第i列的元素個數(shù)。( )</p><p>　　8.有向圖的鄰

70、接表和逆鄰接表中的結(jié)點數(shù)一定相同。( )</p><p>　　9.刪除二叉排序樹中一個結(jié)點，再重新插入上去，一定能得到原來的二叉排序樹。( )</p><p>　　10.圖G的拓撲序列唯一，則其弧數(shù)必為n-1(其中n為G的頂點數(shù))。( )</p><p>　　三、填空題(每空2分，共20分)</p><p>　　1.在

71、有n個葉子結(jié)點的哈夫曼樹中，總結(jié)點數(shù)是_______。</p><p>　　2.一棵樹T采用二叉鏈表存儲，如果樹T中某結(jié)點為葉子結(jié)點，則在二叉鏈表BT中所對應的結(jié)點一定_______。</p><p>　　3.已知數(shù)組A［１０］［１０］為對稱矩陣，其中每個元素占5個單元。現(xiàn)將其下三角部分按行優(yōu)先次序存儲在起始地址為1000的連續(xù)的內(nèi)存單元中，則元素A［５，６］對應的地址是_______。&

72、lt;/p><p>　　4.在有n個結(jié)點的無向圖中，其邊數(shù)最多為_______。</p><p>　　5.取出廣義表A=(x,(a,b,c,d))中原子x的函數(shù)是_______。</p><p>　　6.對矩陣采用壓縮存儲是為了_______。</p><p>　　7.帶頭結(jié)點的雙循環(huán)鏈表L為空表的條件是_______。</p>&

73、lt;p>　　8.在雙鏈表中，在指針P所指結(jié)點前面插入一個結(jié)點S∧時的語句序列是：</p><p>　　S->next=P;S->prior=P->prior;P->prior=S;</p><p><b>　　_______；</b></p><p>　　9.對廣義表A=(x,((a,b),c,d))的運算hea

74、d (head (tail (A)))的結(jié)果是______。</p><p>　　10.判斷線索二叉樹中某結(jié)點指針P所指結(jié)點有左孩子的條件是_______。</p><p>　　四、簡答題(每小題5分，共15分)</p><p>　　求出下圖的一棵最小生成樹。</p><p>　　2.將下面順序表建成一個小頭堆。</p><

75、;p>　　(70，12，20，31，1，5，44，66，61，200，30，80，150，4，28)</p><p>　　3.已知一棵二叉樹的先序序列是ABCDEFGHIJK，中序序列是CDBGFEAHJIK，請構(gòu)造出該二叉樹。</p><p>　　五、綜合應用題(共17分)</p><p>　　1.已知一樹的雙親表示法如下，其中各兄弟結(jié)點是依次出現(xiàn)的，畫出該

76、樹及對應的二叉樹。(滿分7分)。</p><p>　　2.計算二叉樹的深度的算法。(10分)</p><p>　　浙江省2002年1月高等教育自學考試</p><p>　　數(shù)據(jù)結(jié)構(gòu)試題參考答案</p><p>　　課程代碼：02331</p><p>　　一、單項選擇題(每小題2分，共38分)</p>&

77、lt;p>　　1.A 2.B 3.C 4.B 5.D</p><p>　　6.C 7.A 8.B 9.A 10.C</p><p>　　11.D 12.B 13.D 14.D 15.C</p><p>　　16.A

78、 17.B 18.A 19.C</p><p>　　二、判斷題(每小題1分，共10分)</p><p>　　1.√ 2.× 3√ 4.√ 5.×</p><p>　　6.× 7.√ 8.× 9.× 10

79、.×</p><p>　　三、填空題(每空2分，共20分)</p><p><b>　　1. n-1</b></p><p><b>　　2. 左右子樹空</b></p><p><b>　　3. 1225</b></p><p>　　4. n

80、(n-1)/2</p><p>　　5. head(A)</p><p><b>　　6. 節(jié)省空間</b></p><p>　　7. L->next=L->prior 或 L->next=L</p><p>　　8. S->prior->next=S</p><p&

81、gt;<b>　　9. (a)</b></p><p>　　10. P->ltag=1</p><p>　　四、簡答題(每小題5分，共15分)</p><p><b>　　最小生成樹：</b></p><p><b>　　2.小頭堆：</b></p><

82、;p>　　1 12 4 31 30 5 20 66 61 200 70 80 150 44 28</p><p><b>　　3.二叉樹：</b></p><p>　　五、綜合應用題(共17分)</p><p>　　從森林轉(zhuǎn)換為二叉樹：(7分)</p><p>　　2.計算二叉樹的深度的

83、算法：(10分)</p><p>　　int depth(tree *T)</p><p><b>　　{</b></p><p><b>　　if(!T)</b></p><p><b>　　return 0;</b></p><p><b>

84、;　　else</b></p><p>　　return 1+max(depth(T->Lchild),depth(->Rchild));</p><p><b>　　}</b></p><p>　　全國2003年10月高等教育自學考試</p><p><b>　　數(shù)據(jù)結(jié)構(gòu)試題</

85、b></p><p>　　課程代碼：02331</p><p>　　一、單項選擇題(在每小題的四個備選答案中，選出一個正確答案，并將正確答案的序號填在題干的括號內(nèi)。每小題2分，共30分)</p><p>　　1.計算機識別、存儲和加工處理的對象被統(tǒng)稱為( )</p><p>　　A.數(shù)據(jù)

86、 B.數(shù)據(jù)元素</p><p>　　C.數(shù)據(jù)結(jié)構(gòu) D.數(shù)據(jù)類型</p><p>　　2.在具有n個結(jié)點的有序單鏈表中插入一個新結(jié)點并使鏈表仍然有序的時間復雜度是( )</p><p>　　A.O(1) B.O(n)</p><

87、;p>　　C.O(nlogn) D.O(n2)</p><p>　　3.隊和棧的主要區(qū)別是( )</p><p>　　A.邏輯結(jié)構(gòu)不同 B.存儲結(jié)構(gòu)不同</p><p>　　C.所包含的運算個數(shù)不同 D.限定插入和

88、刪除的位置不同</p><p>　　4.鏈棧與順序棧相比，比較明顯的優(yōu)點是( )</p><p>　　A.插入操作更加方便 B.刪除操作更加方便</p><p>　　C.不會出現(xiàn)下溢的情況 D.不會出現(xiàn)上溢的情況</p><p>　　5.采用兩類不同

89、存儲結(jié)構(gòu)的字符串可分別簡稱為( )</p><p>　　A.主串和子串 B.順序串和鏈串</p><p>　　C.目標串和模式串 D.變量串和常量串</p><p>　　6.在目標串T［0..n-1］=″xwxxyxy″中，對模式串P［0..m-1］=″xy

90、″進行子串定位操作的結(jié)果是( )</p><p>　　A.0 B.2</p><p>　　C.3 D.5</p><p>　　7.已知廣義表的表頭為a，表尾為(b,c)，則此廣義表為( )</p><p>　　A.(a,(b,c))

91、 B.(a,b,c)</p><p>　　C.((a),b,c) D.((a,b,c))</p><p>　　8.二維數(shù)組A按行優(yōu)先順序存儲，其中每個元素占1個存儲單元。若A［1］［1］的存儲地址為420，A［3］［3］的存儲地址為446，則A［5］［5］的存儲地址為( )</p&g

92、t;<p>　　A.470 B.471</p><p>　　C.472 D.473</p><p>　　9.二叉樹中第5層上的結(jié)點個數(shù)最多為( )</p><p>　　A.8 B.15</p>

93、<p>　　C.16 D.32</p><p>　　10.下列編碼中屬前綴碼的是( )</p><p>　　A.{1,01,000,001} B.{1,01,011,010}</p><p>　　C.{0,10,110,11}

94、 D.{0,1,00,11}</p><p>　　11.如果某圖的鄰接矩陣是對角線元素均為零的上三角矩陣，則此圖是( )</p><p>　　A.有向完全圖 B.連通圖</p><p>　　C.強連通圖 D.有向無環(huán)圖</p>&

95、lt;p>　　12.對n個關(guān)鍵字的序列進行快速排序，平均情況下的空間復雜度為( )</p><p>　　A.O(1) B.O(logn)</p><p>　　C.O(n) D.O(n logn)</p><p>　　13.對表長為n的順序表進行順序查找，在查找

96、概率相等的情況下，查找成功的平均查找長度為( )</p><p>　　A. B.</p><p>　　C. D.n</p><p>　　14.對于哈希函數(shù)H(key)=key%13,被稱為同義詞的關(guān)鍵字是( )</p><p>　　A

97、.35和41 B.23和39</p><p>　　C.15和44 D.25和51</p><p>　　15.稠密索引是在索引表中( )</p><p>　　A.為每個記錄建立一個索引項 B.為每個頁塊建立一個索引項</p><

98、p>　　C.為每組記錄建立一個索引項 D.為每個字段建立一個索引項</p><p>　　二、填空題（每小題2分，若有兩個空格，每個空格1分，共20分）</p><p>　　16.當問題的規(guī)模n趨向無窮大時，算法執(zhí)行時間T(n)的數(shù)量級被稱為算法的________。</p><p>　　17.在鏈表的結(jié)點中，數(shù)據(jù)元素所占的存儲量和整個結(jié)點所占

99、的存儲量之比稱作________。</p><p>　　18.已知鏈棧的結(jié)點結(jié)構(gòu)為 棧頂指針為top，則實現(xiàn)將指針p所指結(jié)點插入棧頂?shù)恼Z句依次為________和________。</p><p>　　19.空串的長度是________；空格串的長度是________。</p><p>　　20.假設(shè)一個6階的下三角矩陣B按列優(yōu)先順序壓縮存儲

100、在一維數(shù)組A中，其中A［0］存儲矩陣的第一個元素b11,則A［14］存儲的元素是________。</p><p>　　21.在一棵度為3的樹中，度為2的結(jié)點個數(shù)是1，度為0的結(jié)點個數(shù)是6，則度為3的結(jié)點個數(shù)是________。</p><p>　　22.如圖所示的有向無環(huán)圖可以排出________種不同的拓撲序列。</p><p>　　23.利用篩選法將關(guān)鍵字序列

101、(37，66，48，29，31，75)建成的大根堆為(________)。</p><p>　　24.對長度為20的有序表進行二分查找的判定樹的高度為________。</p><p>　　25.在多重表文件中，次關(guān)鍵字索引的組織方式是將________的記錄鏈接成一個鏈表。</p><p>　　三、解答題(每小題5分，共20分)</p><p&

102、gt;　　26.對于單鏈表、單循環(huán)鏈表和雙向鏈表，如果僅僅知道一個指向鏈表中某結(jié)點的指針p，能否將p所指結(jié)點的數(shù)據(jù)元素與其確實存在的直接前驅(qū)交換?請對每一種鏈表作出判斷，若可以，寫出程序段；否則說明理由。</p><p>　　單鏈表和單循環(huán)鏈表的結(jié)點結(jié)構(gòu)為</p><p>　　雙向鏈表的結(jié)點結(jié)構(gòu)為 </p><p><b>　　(1)單鏈表</b&g

103、t;</p><p><b>　　(2)單循環(huán)鏈表</b></p><p><b>　　(3)雙向鏈表</b></p><p>　　27.假設(shè)通信電文使用的字符集為{a,b,c,d,e,f,g}，字符的哈夫曼編碼依次為：0110，10，110，111，00，0111和010。</p><p>　　(

104、1)請根據(jù)哈夫曼編碼畫出此哈夫曼樹，并在葉子結(jié)點中標注相應字符；</p><p>　　(2)若這些字符在電文中出現(xiàn)的頻度分別為：3，35，13，15，20，5和9，求該哈夫曼樹的帶權(quán)路徑長度。</p><p>　　28.當采用鄰接表作為圖的存儲結(jié)構(gòu)時，也可將鄰接表中的頂點表由順序結(jié)構(gòu)改為鏈表結(jié)構(gòu)。</p><p>　　(1)請分別畫出這種鄰接表的頂點鏈表結(jié)點和邊表結(jié)

105、點，并說明結(jié)點中各個域的作用；</p><p>　　(2)對如圖所示的有向圖畫出這種鄰接表。</p><p>　　29.已知4階B-樹如圖所示。</p><p>　　(1)分別畫出將關(guān)鍵字23和89相繼插入之后的B-樹。</p><p>　　(2)畫出從插入之前的B-樹中刪除關(guān)鍵字51之后的B-樹。</p><p>　

106、　四、算法閱讀題(每小題5分，共20分)</p><p>　　30.閱讀下列函數(shù)algo,并回答問題：</p><p>　　(1)假設(shè)隊列q中的元素為(2,4,5,7,8),其中“2”為隊頭元素。寫出執(zhí)行函數(shù)調(diào)用algo(&q)后的隊列q；</p><p>　　(2)簡述算法algo的功能。</p><p>　　void algo(Q

107、ueue *Q)</p><p><b>　　{</b></p><p><b>　　Stack S;</b></p><p>　　InitStack(&S);</p><p>　　while (!QueueEmpty(Q))</p><p>　　Push(&

108、S, DeQueue(Q));</p><p>　　while (! StackEmpty(&S))</p><p>　　ＥnQueue(Q,Pop(&S));</p><p><b>　　}</b></p><p><b>　　(1)</b></p><p>

109、;<b>　　(2)</b></p><p>　　31.閱讀下列函數(shù)F，并回答問題：</p><p>　　(1)已知如圖所示的二叉樹以二叉鏈表作存儲結(jié)構(gòu)，rt為指向根結(jié)點的指針。寫出執(zhí)行函數(shù)調(diào)用F(rt)的輸出結(jié)果。</p><p>　　(2)說明函數(shù)F的功能。</p><p>　　void F(BinTree T)&l

110、t;/p><p><b>　　{</b></p><p><b>　　Stack S;</b></p><p><b>　　if(T)</b></p><p><b>　　{</b></p><p>　　InitStack(&S

111、);</p><p>　　Push(&S,NULL);</p><p><b>　　while(T)</b></p><p><b>　　{</b></p><p>　　printf("%c", T->data);</p><p>　　if(

112、T->rchild) Push(&S,T->rchild);</p><p>　　if(T->lchild)T=T->lchild;</p><p>　　else T=Pop(&S);</p><p><b>　　}</b></p><p><b>　　}</b&g

113、t;</p><p><b>　　}</b></p><p><b>　　(1)</b></p><p><b>　　(2)</b></p><p>　　32.已知鄰接表的頂點表結(jié)點結(jié)構(gòu)為 </p><p>　　邊表結(jié)點EdgeNode的結(jié)構(gòu)為</

114、p><p>　　下列算法計算有向圖G中頂點vi的入度。請在空缺處填入合適的內(nèi)容，使其成為一個完整的算法。</p><p>　　int FindDegree(ALGraph *G,int i)//ALGraph為圖的鄰接表類型</p><p><b>　　{</b></p><p>　　int dgree, j;</p&

115、gt;<p>　　EdgeNode *p;</p><p>　　degree= (1) ;</p><p>　　for(j=0;j<G->n;j++)</p><p><b>　　{</b></p><p>　　p=G->adjlist［j］. firstedge;<

116、/p><p>　　while ( (2) )</p><p><b>　　{</b></p><p>　　if( (3) )</p><p><b>　　{</b></p><p><b>　　degree++;</b>

117、</p><p><b>　　break;</b></p><p><b>　　}</b></p><p>　　p=p->next;</p><p><b>　　}</b></p><p><b>　　}</b></p&

118、gt;<p>　　return degree;</p><p><b>　　}</b></p><p><b>　　(1)</b></p><p><b>　　(2)</b></p><p><b>　　(3)</b></p>

119、<p>　　33.已知單鏈表的結(jié)點結(jié)構(gòu)為</p><p>　　下列算法對帶頭結(jié)點的單鏈表L進行簡單選擇排序，使得L中的元素按值從小到大排列。</p><p>　　請在空缺處填入合適的內(nèi)容，使其成為完整的算法。</p><p>　　void SelectSort(LinkedList L)</p><p><b>　　{&l

120、t;/b></p><p>　　LinkedList p,q,min;</p><p>　　DataType rcd;</p><p>　　p= (1) ;</p><p>　　while(p!=NULL) {</p><p><b>　　min=p;</b></p>

121、<p>　　q=p->next;</p><p>　　while(q!=NULL){</p><p>　　if( (2) )min=q;</p><p>　　q=q->next;</p><p><b>　　}</b></p><p>　　if( (3)

122、 ){</p><p>　　rcd=p->data;</p><p>　　p->data=min->data;</p><p>　　min->data=rcd;</p><p><b>　　}</b></p><p><b>　　(4) ;</b&

123、gt;</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　(1)</b></p><p><b>　　(2)</b></p><p><b>　　(3)</b

124、></p><p><b>　　(4)</b></p><p>　　五、算法設(shè)計題(本題10分)</p><p>　　34.設(shè)線性表A=(a1,a2,a3,…,an)以帶頭結(jié)點的單鏈表作為存儲結(jié)構(gòu)。編寫一個函數(shù)，對A進行調(diào)整，使得當n為奇數(shù)時A=(a2,a4,…,an-1,a1,a3,…,an)，當n為偶數(shù)時A=(a2,a4,…,an,a

125、1,a3,…,an-1)。</p><p>　　2003年10月自考數(shù)據(jù)結(jié)構(gòu)試題答案</p><p>　　全國2005年10月高等教育自學考試</p><p><b>　　數(shù)據(jù)結(jié)構(gòu)試題</b></p><p>　　課程代碼：02331</p><p>　　一、單項選擇題(本大題共15小題，每小題2

126、分，共30分)</p><p>　　在每小題列出的四個備選項中只有一個是符合題目要求的，請將其代碼填寫在題后的括號內(nèi)。錯選、多選或未選均無分。</p><p>　　1. 若將數(shù)據(jù)結(jié)構(gòu)形式定義為二元組(K，R)，其中K是數(shù)據(jù)元素的有限集合，則R是K上</p><p><b>　　( ) </b></p><p>

127、　　A. 操作的有限集合 B. 映象的有限集合</p><p>　　C. 類型的有限集合 D. 關(guān)系的有限集合</p><p>　　2. 在長度為n的順序表中刪除第i個元素(1≤i≤n)時，元素移動的次數(shù)為( )</p><p>　　A. n-i+1 B.

128、 i</p><p>　　C. i+1 D. n-i</p><p>　　3. 若不帶頭結(jié)點的單鏈表的頭指針為head，則該鏈表為空的判定條件是( )</p><p>　　A. head==NULL B. head->next==NULL</p><p>

129、;　　C. head!=NULL D. head->next==head</p><p>　　4. 引起循環(huán)隊列隊頭位置發(fā)生變化的操作是( )</p><p>　　A. 出隊 B. 入隊</p><p>　　C. 取隊頭元素 D. 取隊尾元素&l