全國自考數(shù)據(jù)結(jié)構(gòu)2014-4

1、全國2014年4月自學(xué)考試數(shù)據(jù)結(jié)構(gòu)試題課程代碼：02331請(qǐng)考生按規(guī)定用筆將所有試題的答案涂、寫在答題紙上。選擇題部分注意事項(xiàng)：1.答題前，考生務(wù)必將自己的考試課程名稱、姓名、準(zhǔn)考證號(hào)用黑色字跡的簽字筆或鋼筆填寫在答題紙規(guī)定的位置上。2.每小題選出答案后，用2B鉛筆把答題紙上對(duì)應(yīng)題目的答案標(biāo)號(hào)涂黑。如需改動(dòng)，用橡皮擦干凈后，再選涂其他答案標(biāo)號(hào)。不能答在試題卷上。一、單項(xiàng)選擇題（本大題共15小題，每小題2分，共30分）在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其選出并將“答題紙”的相應(yīng)代碼涂黑。錯(cuò)涂、多涂或未涂均無分。1. 與數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)無關(guān)的概念是（ A ）P3-4A棧B鏈表C順

2、序表D二叉鏈表2. 順序表中有10個(gè)數(shù)據(jù)元素，若第一個(gè)元素的存儲(chǔ)地址是1000，則最后一個(gè)元素地址是1036，第5個(gè)元素的地址是（ B ）A1010B1016C1018D10193設(shè)棧的初始狀態(tài)為空，元素1、2、3、4、5、6依次入棧，得到的出棧序列是（2,4,3,6,5,1）,則棧的容量至少是（ B ）A2B3C4D64下列關(guān)于隊(duì)列的敘述中,錯(cuò)誤的是（ D ）P37A隊(duì)列是一種先進(jìn)先出的線性表B隊(duì)列是一種后進(jìn)后出的線性表C循環(huán)隊(duì)列中進(jìn)行出隊(duì)操作時(shí)要判斷隊(duì)列是否為空D在鏈隊(duì)列中進(jìn)行入隊(duì)操作時(shí)要判斷隊(duì)列是否為滿5對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)的目的是（ B ）P63A便于運(yùn)算B節(jié)省存儲(chǔ)空間C便于輸入輸出

3、D降低時(shí)間復(fù)雜度6一棵二叉樹的第7層上最多含有的結(jié)點(diǎn)數(shù)為（ B ）P72A14B64C127D1287下列選項(xiàng)為完全二叉樹的是（ A ）P738用鄰接表表示n個(gè)頂點(diǎn)e條邊的無向圖,其邊表結(jié)點(diǎn)的總數(shù)是（ C ）A neBeC2eDn+e9無向圖中所有頂點(diǎn)的度數(shù)之和與所有邊數(shù)之比是（ C ）P101A1/2B1C2D410采用鄰接矩陣存儲(chǔ)圖時(shí),廣度優(yōu)先搜索遍歷算法的時(shí)間復(fù)雜度為（ C ）P113AO（n）BO（n+e）CO（n2）DO（n3）11對(duì)序列（15,9,7,8,20,-1,4）進(jìn)行排序,若一趟排序后的結(jié)果為（-1,15,9,7,8,20,4）,則采用的排序方法是（ D ）A歸并排序B快速

4、排序C直接選擇排序D冒泡排序12比較次數(shù)與待排序列初始狀態(tài)無關(guān)的排序方法是（ D ）P151A快速排序B冒泡排序C直接插入排序D直接選擇排序13查找較快,且插入和刪除操作也比較方便的查找方法是（ A ）P174A分塊查找B二分查找C順序查找D折半查找14下列關(guān)于m階B樹的敘述中,錯(cuò)誤的是（ D ）P182A根結(jié)點(diǎn)至多有m棵子樹B所有葉子都在同一層次上C每個(gè)非根內(nèi)部結(jié)點(diǎn)至少有棵子樹D結(jié)點(diǎn)內(nèi)部的關(guān)鍵字可以是無序的15在散列查找中處理沖突時(shí),可以采用開放定址法。下列不是開放定址法的是（ D ）P196-197A線性探查法B二次探查法C雙重散列法D拉鏈法非選擇題部分注意事項(xiàng)：用黑色字跡的簽字筆或鋼筆將

5、答案寫在答題紙上,不能答在試題卷上。二、填空題（本大題共10小題,每小題2分,共20分）16數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)容包括數(shù)據(jù)的邏輯結(jié)構(gòu)、 存儲(chǔ)結(jié)構(gòu) 和數(shù)據(jù)的運(yùn)算。P117頭指針為L的帶頭結(jié)點(diǎn)的雙循環(huán)鏈表,結(jié)點(diǎn)的前趨指針域?yàn)閜rior,后繼指針域?yàn)閚ext,判斷該鏈表為空的條件是 L-prior=L 。P2718普里姆（Prim）算法完成的功能是求圖的 最小生成樹 。P11619若三維數(shù)組a456的基地址是100,每個(gè)元素占用2個(gè)存儲(chǔ)單元,則數(shù)組a中最后一個(gè)元素的存儲(chǔ)地址是 338 。P6020二叉樹的線索鏈表利用 空指針域 存放遍歷時(shí)得到的前趨或后繼結(jié)點(diǎn)的指針。P7921采用鄰接矩陣存儲(chǔ)n個(gè)頂點(diǎn)e條

6、邊的無向圖,其鄰接矩陣的大小為 n*n 。P10322若無向圖中任意兩個(gè)不同的頂點(diǎn)間都有路徑,則稱該圖為 連通圖 。P10223在直接插入排序、冒泡排序和快速排序中,平均時(shí)間性能最佳的是 快速排序 。P14924假設(shè)m個(gè)關(guān)鍵字互為同義詞,若用線性探查法把這m個(gè)關(guān)鍵字存入散列表中,至少要進(jìn)行的探查次數(shù)是 m(m+1)/2 。P19625順序查找算法的平均時(shí)間復(fù)雜度為 O(n) 。P170三、解答題（本大題共4小題,每小題5分,共20分）26用X代表進(jìn)棧操作,S代表出棧操作。給出利用棧將字符串a(chǎn)*b-c改變?yōu)閍b*c-的操作步驟。例如：將ABC改變?yōu)锽CA,則其操作步驟為XXSXSS。解：XSXX

7、SSXXSS27.假定電文字符集為A,B,C,D,E,F,G,H,它們?cè)陔娢闹谐霈F(xiàn)的次數(shù)分別為19,6,12,5,38,3,13,4）,為這8個(gè)字符設(shè)計(jì)哈夫曼編碼。畫出哈夫曼樹并給出編碼。要求在構(gòu)造哈夫曼樹的過程中,權(quán)值較小結(jié)點(diǎn)放在左側(cè),編碼時(shí)左分支生成代碼0,右分支生成代碼1。解：哈夫曼樹如下，90E52382537CG121318A19711FHDB3456 哈夫曼編碼： A：111 C：100 E：0 G：101 B：11011 D：11010 F：11000 H：1100128設(shè)圖以鄰接表存儲(chǔ),如題28圖所示。（1）寫出從頂點(diǎn)v1出發(fā)圖的深度優(yōu)先搜索遍歷序列。（2）寫出從頂點(diǎn)v1出發(fā)圖

8、的廣度優(yōu)先搜索遍歷序列。解：1 V1V2V5V3V4V6 2 V1V2V3V4V5V629（1）一個(gè)排序方法穩(wěn)定的含義是什么？P136（2）快速排序是穩(wěn)定的嗎？舉例說明。P145解：1 如果待排序的文件中，存在多個(gè)關(guān)鍵字相同的記錄，經(jīng)過排序后這些具有相同關(guān)鍵字的記錄之間的相對(duì)次序保持不變，則稱這種排序方法是穩(wěn)定的； 2 快速排序是不穩(wěn)定的，例如序列2,2,1四、算法閱讀題（本大題共4小題,每小題5分,共20分）30.閱讀下列算法,并回答問題：void f30（SeqStack S） int k=0；CirQueue Q；SeqStack T；InitQueue（&Q）； /初始化隊(duì)列QInit

9、Stack（&T）； /初始化棧Twhile （!StackEmpty（&S） k+;if （k%2!=0） Push（&T, Pop（&S）;else EnQueue（&Q, Pop（&S）; /第一個(gè)循環(huán)while （!QueueEmpty（&Q） /第二個(gè)循環(huán)Push（&S, DeQueue（&Q）;while（!StackEmpty（&T） /第三個(gè)循環(huán)Push（&S,Pop（&T）；設(shè)棧S=（1,2,3,4,5,6,7）,其中7為棧頂元素。調(diào)用函數(shù)f30（S）后,（1）第一個(gè)循環(huán)結(jié)束后,棧T和隊(duì)列Q中的內(nèi)容各是什么？（2）第三個(gè)循環(huán)語句結(jié)束后,棧S中的內(nèi)容是什么？解：1第一個(gè)循環(huán)結(jié)束

10、后T與Q內(nèi)容為 T：7 ,5,3,1 Q：6,4,22第三個(gè)循環(huán)結(jié)束后棧S的內(nèi)容為 S：6,4,2,1,3,5,7（7為棧頂元素）31.二叉樹的二叉鏈表類型定義如下：typedef struct node DataType data；struct node *lchild, *rchild; BinNode;typedef BinNode *BinTree；閱讀下列算法,并回答問題：void f31（BinTree BT） BinNode *s;if （BT） s=BT-lchild；BT-lchild=BT-rchild;BT-rchild=s；f31（BT-lchild）；f31（BT-r

11、child）；（1）該算法的功能是什么？（2）以下算法功能是否等價(jià)于上面的算法？void f3la（BinTree BT） BinNode *s;if（BT） f31a（BT-lchild）；f31a（BT-rchild）；s=BT-lchild;BT-lchild=BT-rchild;BT-rchild=s；解：1 交換二叉樹BT所有結(jié)點(diǎn)的左右子樹交換 2 功能等價(jià)32.單鏈表類型定義如下：typedef struct node int data;struct node *next; ListNode;typedef ListNode *LinkList;用不帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)待排數(shù)據(jù),鏈

12、表頭指針為head。下列直接選擇排序算法對(duì)鏈表按升序進(jìn)行排序,請(qǐng)?jiān)诖痤}紙相應(yīng)位置填寫適當(dāng)內(nèi)容使算法完整。void f32（LinkList head） ListNode *p, *q, *r;int tmp;p=head;while（p） q=p；r=q-next;while（ (1) ） if（ (2) ） q=r；r=r-next;tmp=q-data;q-data=p-data;p-data=tmp;p= (3) ；解：1 r！=NULL2 r-data data3 p-next33.實(shí)現(xiàn)二分查找的遞歸章法如下,在答題紙相應(yīng)位置填寫適當(dāng)?shù)膬?nèi)容使算法完整。P171typedef structKeyType key;InfoType otherinfo;NodeType;typedef NodeType SeqListn+l;int f33（SeqList R, int low, int high, KeyType K） int