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

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

2、法指的是（ ）</p><p>　　A．計(jì)算機(jī)程序 B．解決問題的計(jì)算方法</p><p>　　C．排序算法 D．解決問題的有限運(yùn)算序列</p><p>　　2．線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，結(jié)點(diǎn)的存儲(chǔ)地址（ ）</p><p><b>　　A．必須是不連續(xù)

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

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

5、溢發(fā)生的機(jī)率</p><p>　　D．節(jié)省存儲(chǔ)空間，降低下溢發(fā)生的機(jī)率</p><p>　　5．設(shè)數(shù)組data[m]作為循環(huán)隊(duì)列SQ的存儲(chǔ)空間，front為隊(duì)頭指針，rear為隊(duì)尾指針，則執(zhí)行出隊(duì)操作后其頭指針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．串的長(zhǎng)度必須大于零</p><p>　　C．串中元素只能是字母 D．空串就是空白串

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

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

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

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

11、序時(shí)，序列的變化情況如下：</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．適于對(duì)動(dòng)態(tài)查找表進(jìn)行高效率查找的組織結(jié)構(gòu)是（ ）</p><p>　　A．有序表 B．分塊有序表 C．三叉排序樹 D．線性鏈表</p><p>　　15．不定長(zhǎng)文件是指（ ）</p><p>　　A．文件的長(zhǎng)度不固定

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

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

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

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

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

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．請(qǐng)畫出與下列二叉樹對(duì)應(yīng)的森林。</p>

19、;<p>　　28．已知一個(gè)無(wú)向圖的頂點(diǎn)集為{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ù)鄰接矩陣從頂點(diǎn)a出發(fā)進(jìn)行深度優(yōu)先遍歷和廣度優(yōu)先遍歷，寫出相應(yīng)的遍歷序列。</p><p>　　29．已知一個(gè)散列表如下圖所示：</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>　　（1）對(duì)表中關(guān)鍵字35，20，33和48進(jìn)行查找時(shí)，所需進(jìn)行的比較次數(shù)各為多少？</p><p>　?。?）該散列表在等概率查找時(shí)查找成功的平均查找長(zhǎng)度為多少？</p><p&g

23、t;　　四、算法閱讀題（本大題共4小題，每小題5分，共20分）</p><p>　　30．下列算法的功能是比較兩個(gè)鏈串的大小，其返回值為：</p><p>　　comstr(s1,s2)= </p><p>　　請(qǐng)?jiān)诳瞻滋幪钊脒m當(dāng)?shù)膬?nèi)容。</p><p>　　int comstr(LinkString s1,LinkString s2)

24、 </p><p>　　{//s1和s2為兩個(gè)鏈串的頭指針</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>　?、?lt;/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é)點(diǎn)的單鏈表的頭指針</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>　　請(qǐng)回答下列問題：</b></p><p>　　（1）說(shuō)明語(yǔ)句S1的功能；</p><p>　　（2）說(shuō)明語(yǔ)句組

30、S2的功能；</p><p>　?。?）設(shè)鏈表表示的線性表為（a1,a2, …,an）,寫出算法執(zhí)行后的返回值所表示的線性表。</p><p>　　32．假設(shè)兩個(gè)隊(duì)列共享一個(gè)循環(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>　　對(duì)于i=0或1，front[i]和rear[i]分別為第i個(gè)隊(duì)列的頭指針和尾指針。請(qǐng)對(duì)以下算法填空，實(shí)現(xiàn)第i個(gè)隊(duì)列的入隊(duì)操作。</p>&l

32、t;p>　　int EnQueue (Queue2*Q,int i,DateType x)</p><p>　　{//若第 i個(gè)隊(duì)列不滿，則元素x入隊(duì)列，并返回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>　?、?lt;/b></p><p>　　33．已知二叉樹的存儲(chǔ)結(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>　　對(duì)于如下所示的二叉樹</p><p

39、>　?。?）畫出執(zhí)行上述算法后所建立的結(jié)構(gòu)；</p><p>　?。?）說(shuō)明該算法的功能。</p><p>　　五、算法設(shè)計(jì)題（本題共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>　?。?）寫一個(gè)調(diào)用上述函數(shù)實(shí)現(xiàn)下列功能的算法：對(duì)一整型數(shù)組b[n]中的元素進(jìn)行重新排列，將所有負(fù)數(shù)均調(diào)整到數(shù)組的低下標(biāo)端，將

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

44、７．Ｃ８，Ｄ９，Ａ10．Ｃ11．Ｄ12．Ｃ13．Ｄ14．Ｃ15．Ｂ</p><p>　　二、填空題（本大題共10小題，每小題2分，共20分）</p><p>　　16．存儲(chǔ)（或存儲(chǔ)結(jié)構(gòu)）17.p－＞next－＞next18．進(jìn)棧和退棧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．（１）對(duì)關(guān)鍵字35、20、33和48進(jìn)行查找的比較次數(shù)為３、２、１、１；<

47、;/p><p><b>　?。ǎ玻┢骄檎议L(zhǎng)度</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>　　④s1(或s1!=NULL或s1&&!s2)</p><p><b>　?、輗eturn 0</b></p><p>　　31.（1）查詢鏈表的尾結(jié)點(diǎn)</p><p>　?。?）將第一個(gè)結(jié)點(diǎn)鏈接到鏈表的尾部，作為新的尾結(jié)點(diǎn)</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>　?。?）中序遍歷二叉樹，按遍歷序列中葉子結(jié)點(diǎn)數(shù)據(jù)域的值構(gòu)建一個(gè)以Leafhead為頭指

50、針的逆序單鏈表（或按二叉樹中葉子結(jié)點(diǎn)數(shù)據(jù)自右至左鏈接成一個(gè)鏈表）。</p><p>　　五、算法設(shè)計(jì)題（本題共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月高等教育自學(xué)考試</p><p>&l

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

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

55、D.快速排序</p><p>　　3.下列排序算法中，( )算法可能會(huì)出現(xiàn)下面情況：初始數(shù)據(jù)有序時(shí)，花費(fèi)的時(shí)間反而最多。</p><p>　　A.堆排序B.冒泡排序</p><p>　　C.快速排序D.SHELL排序</p><p>　　4.一個(gè)棧的輸入序列為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)隊(duì)列中數(shù)組的下標(biāo)范圍是1～n，其頭尾指針分別為f和r，則其元素個(gè)數(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.若某鏈表最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)和刪除最后一個(gè)結(jié)點(diǎn)，則采用( )存儲(chǔ)方式最節(jié)省時(shí)間。</p><p>　　A.單鏈表B.雙鏈表</p><p

58、>　　C.帶頭結(jié)點(diǎn)的雙循環(huán)鏈表D.單循環(huán)鏈表</p><p>　　7.在有n個(gè)結(jié)點(diǎn)的二叉鏈表中，值為非空的鏈域的個(gè)數(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［５］［６］的每個(gè)元素占5個(gè)單元，將其按行優(yōu)先次序存儲(chǔ)在起始地址為1000的連續(xù)的內(nèi)存單元中，則元素A［５，５］的地址為( )</p><p>　　A. 1140

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

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

62、t;p>　　A. O(n)B. O(nlog2n)</p><p>　　C. O(n2)D. O(log2n)</p><p>　　13.下列排序算法中，某一趟結(jié)束后未必能選出一個(gè)元素放在其最終位置上的是( )</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算法的時(shí)間復(fù)雜度為( )</p><p>　　A. O(n)B. O(n3)</p><p>　　C. O(n2)D. O(n+e)</p><p>　　16.隊(duì)列操作的原則是( )</p><p>　　A.先進(jìn)先出B.后進(jìn)先出<

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

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

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

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

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

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

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

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

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

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

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

76、樹及對(duì)應(yīng)的二叉樹。(滿分7分)。</p><p>　　2.計(jì)算二叉樹的深度的算法。(10分)</p><p>　　浙江省2002年1月高等教育自學(xué)考試</p><p>　　數(shù)據(jù)結(jié)構(gòu)試題參考答案</p><p>　　課程代碼：02331</p><p>　　一、單項(xiàng)選擇題(每小題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>　　四、簡(jiǎn)答題(每小題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>　　五、綜合應(yīng)用題(共17分)</p><p>　　從森林轉(zhuǎn)換為二叉樹：(7分)</p><p>　　2.計(jì)算二叉樹的深度的

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>　　全國(guó)2003年10月高等教育自學(xué)考試</p><p><b>　　數(shù)據(jù)結(jié)構(gòu)試題</

85、b></p><p>　　課程代碼：02331</p><p>　　一、單項(xiàng)選擇題(在每小題的四個(gè)備選答案中，選出一個(gè)正確答案，并將正確答案的序號(hào)填在題干的括號(hào)內(nèi)。每小題2分，共30分)</p><p>　　1.計(jì)算機(jī)識(shí)別、存儲(chǔ)和加工處理的對(duì)象被統(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個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并使鏈表仍然有序的時(shí)間復(fù)雜度是( )</p><p>　　A.O(1) B.O(n)</p><

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

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

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

90、″進(jìn)行子串定位操作的結(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)先順序存儲(chǔ)，其中每個(gè)元素占1個(gè)存儲(chǔ)單元。若A［1］［1］的存儲(chǔ)地址為420，A［3］［3］的存儲(chǔ)地址為446，則A［5］［5］的存儲(chǔ)地址為( )</p&g

92、t;<p>　　A.470 B.471</p><p>　　C.472 D.473</p><p>　　9.二叉樹中第5層上的結(jié)點(diǎn)個(gè)數(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.如果某圖的鄰接矩陣是對(duì)角線元素均為零的上三角矩陣，則此圖是( )</p><p>　　A.有向完全圖 B.連通圖</p><p>　　C.強(qiáng)連通圖 D.有向無(wú)環(huán)圖</p>&

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

96、概率相等的情況下，查找成功的平均查找長(zhǎng)度為( )</p><p>　　A. B.</p><p>　　C. D.n</p><p>　　14.對(duì)于哈希函數(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.為每個(gè)記錄建立一個(gè)索引項(xiàng) B.為每個(gè)頁(yè)塊建立一個(gè)索引項(xiàng)</p><

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

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

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

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

102、gt;　　26.對(duì)于單鏈表、單循環(huán)鏈表和雙向鏈表，如果僅僅知道一個(gè)指向鏈表中某結(jié)點(diǎn)的指針p，能否將p所指結(jié)點(diǎn)的數(shù)據(jù)元素與其確實(shí)存在的直接前驅(qū)交換?請(qǐng)對(duì)每一種鏈表作出判斷，若可以，寫出程序段；否則說(shuō)明理由。</p><p>　　單鏈表和單循環(huán)鏈表的結(jié)點(diǎn)結(jié)構(gòu)為</p><p>　　雙向鏈表的結(jié)點(diǎn)結(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)請(qǐng)根據(jù)哈夫曼編碼畫出此哈夫曼樹，并在葉子結(jié)點(diǎn)中標(biāo)注相應(yīng)字符；</p><p>　　(2)若這些字符在電文中出現(xiàn)的頻度分別為：3，35，13，15，20，5和9，求該哈夫曼樹的帶權(quán)路徑長(zhǎng)度。</p><p>　　28.當(dāng)采用鄰接表作為圖的存儲(chǔ)結(jié)構(gòu)時(shí)，也可將鄰接表中的頂點(diǎn)表由順序結(jié)構(gòu)改為鏈表結(jié)構(gòu)。</p><p>　　(1)請(qǐng)分別畫出這種鄰接表的頂點(diǎn)鏈表結(jié)點(diǎn)和邊表結(jié)

105、點(diǎn)，并說(shuō)明結(jié)點(diǎn)中各個(gè)域的作用；</p><p>　　(2)對(duì)如圖所示的有向圖畫出這種鄰接表。</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è)隊(duì)列q中的元素為(2,4,5,7,8),其中“2”為隊(duì)頭元素。寫出執(zhí)行函數(shù)調(diào)用algo(&q)后的隊(duì)列q；</p><p>　　(2)簡(jiǎn)述算法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>　?。舗Queue(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)已知如圖所示的二叉樹以二叉鏈表作存儲(chǔ)結(jié)構(gòu)，rt為指向根結(jié)點(diǎn)的指針。寫出執(zhí)行函數(shù)調(diào)用F(rt)的輸出結(jié)果。</p><p>　　(2)說(shuō)明函數(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.已知鄰接表的頂點(diǎn)表結(jié)點(diǎn)結(jié)構(gòu)為 </p><p>　　邊表結(jié)點(diǎn)EdgeNode的結(jié)構(gòu)為</

114、p><p>　　下列算法計(jì)算有向圖G中頂點(diǎn)vi的入度。請(qǐng)?jiān)诳杖碧幪钊牒线m的內(nèi)容，使其成為一個(gè)完整的算法。</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é)點(diǎn)結(jié)構(gòu)為</p><p>　　下列算法對(duì)帶頭結(jié)點(diǎn)的單鏈表L進(jìn)行簡(jiǎn)單選擇排序，使得L中的元素按值從小到大排列。</p><p>　　請(qǐng)?jiān)诳杖碧幪钊牒线m的內(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è)計(jì)題(本題10分)</p><p>　　34.設(shè)線性表A=(a1,a2,a3,…,an)以帶頭結(jié)點(diǎn)的單鏈表作為存儲(chǔ)結(jié)構(gòu)。編寫一個(gè)函數(shù)，對(duì)A進(jìn)行調(diào)整，使得當(dāng)n為奇數(shù)時(shí)A=(a2,a4,…,an-1,a1,a3,…,an)，當(dāng)n為偶數(shù)時(shí)A=(a2,a4,…,an,a

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

126、分，共30分)</p><p>　　在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其代碼填寫在題后的括號(hào)內(nèi)。錯(cuò)選、多選或未選均無(wú)分。</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. 在長(zhǎng)度為n的順序表中刪除第i個(gè)元素(1≤i≤n)時(shí)，元素移動(dòng)的次數(shù)為( )</p><p>　　A. n-i+1 B.

128、 i</p><p>　　C. i+1 D. n-i</p><p>　　3. 若不帶頭結(jié)點(diǎn)的單鏈表的頭指針為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)隊(duì)列隊(duì)頭位置發(fā)生變化的操作是( )</p><p>　　A. 出隊(duì) B. 入隊(duì)</p><p>　　C. 取隊(duì)頭元素 D. 取隊(duì)尾元素&l