全國(guó)2014年4月高等教育自學(xué)考試數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題

　　課程代碼：02142

　　請(qǐng)考生按規(guī)定用筆將所有試題的答案涂、寫(xiě)在答題紙上。

　　選擇題部分

　　注意事項(xiàng)：

　　1.答題前，考生務(wù)必將自己的考試課程名稱(chēng)、姓名、準(zhǔn)考證號(hào)用黑色字跡的簽字筆或鋼筆填寫(xiě)在答題紙規(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ò)涂、多涂或未涂均無(wú)分。

　　1.下列幾種算法時(shí)間復(fù)雜度中，最小的是

　　A.O(log2n) B.O(n)

　　C.O(n2) D.O(1)

　　2.數(shù)據(jù)的存儲(chǔ)方式中除了順序存儲(chǔ)方式和鏈?zhǔn)酱鎯?chǔ)方式之外，還有

　　A.索引存儲(chǔ)方式和樹(shù)形存儲(chǔ)方式 B.線(xiàn)性存儲(chǔ)方式和散列存儲(chǔ)方式

　　C.線(xiàn)性存儲(chǔ)方式和索引存儲(chǔ)方式 D.索引存儲(chǔ)方式和散列存儲(chǔ)方式

　　3.表長(zhǎng)為n的順序表中做刪除運(yùn)算的平均時(shí)間復(fù)雜度為

　　A.O(1) B.O(log2n)

　　C.O(n) D.O(n2)

　　4.順序表中定位算法(查找值為x的結(jié)點(diǎn)序號(hào)最小值)的平均時(shí)間復(fù)雜度為

　　A.O(1) B.O(log2n)

　　C.O(n) D.O(n2)

　　5.元素的進(jìn)棧次序?yàn)锳，B，C，D，E，出棧的第一個(gè)元素為E，則第四個(gè)出棧的元素為

　　A.D B.C

　　C.B D.A

　　6.帶頭結(jié)點(diǎn)的鏈隊(duì)列中，隊(duì)列頭和隊(duì)列尾指針?lè)謩e為front和rear，則判斷隊(duì)列空的條件為

　　A.front==rear B.front!=NULL

　　C.rear!==NULL D.front==NULL

　　7.深度為5的二叉樹(shù)，結(jié)點(diǎn)個(gè)數(shù)最多為

　　A.31個(gè) B.32個(gè)

　　C.63個(gè) D.64個(gè)

　　8.如果結(jié)點(diǎn)A有2個(gè)兄弟結(jié)點(diǎn)，結(jié)點(diǎn)B為A的雙親，則B的度為

　　A.1 B.3

　　C.4 D.5

　　9.將題9圖所示的一棵樹(shù)轉(zhuǎn)換為二叉樹(shù)，結(jié)點(diǎn)C是

　　A.A的左孩子

　　B.A的右孩子

　　C.B的右孩子

　　D.E的右孩子

　　10.n為圖的頂點(diǎn)個(gè)數(shù)，e為圖中弧的數(shù)目，則圖的拓?fù)渑判蛩惴ǖ臅r(shí)間復(fù)雜度為

　　A.O(n) B.O(e)

　　C.O(n-e) D.O(n+e)

　　11.無(wú)向圖的鄰接矩陣是

　　A.對(duì)角矩陣 B.稀疏矩陣

　　C.上三角矩陣 D.對(duì)稱(chēng)矩陣

　　12.在具有101個(gè)元素的順序表中查找值為x的元素結(jié)點(diǎn)時(shí)，平均比較元素的次數(shù)為

　　A.50 B.51

　　C.100 D.101

　　13.構(gòu)造散列函數(shù)的方法很多，常用的構(gòu)造方法有

　　A.數(shù)字分析法、除留余數(shù)法、平方取中法

　　B.線(xiàn)性探測(cè)法、二次探測(cè)法、除留余數(shù)法

　　C.線(xiàn)性探測(cè)法、除留余數(shù)法、鏈地址法

　　D.線(xiàn)性探測(cè)法、二次探測(cè)法、鏈地址法

　　14.就平均時(shí)間性能而言，快速排序方法最佳，其時(shí)間復(fù)雜度為

　　A.O(n) B.O(nlog2n)

　　C.O(n2) D.O(1og2n)

　　15.下述算法中，不穩(wěn)定的排序算法是

　　A.直接插入排序 B.冒泡排序

　　C.堆排序 D.歸并排序

　　非選擇題部分

　　注意事項(xiàng)：

　　用黑色字跡的簽字筆或鋼筆將答案寫(xiě)在答題紙上，不能答在試題卷上。

　　二、填空題(本大題共13小題，每小題2分，共26分)

　　16.數(shù)據(jù)的基本單位是_________。

　　17.雙向循環(huán)鏈表中，在p所指結(jié)點(diǎn)的后面插入一個(gè)新結(jié)點(diǎn)*t，需要修改四個(gè)指針，分別為

　　t->prior=P;t->next=p->next;_________;p->next=t;。

　　18.在帶有頭結(jié)點(diǎn)的循環(huán)鏈表中，尾指針為rear，判斷指針P所指結(jié)點(diǎn)為首結(jié)點(diǎn)的條件是_________。

　　19.若線(xiàn)性表中最常用的操作是求表長(zhǎng)和讀表元素，則順序表和鏈表這兩種存儲(chǔ)方式中，較節(jié)省時(shí)間的是_________。

　　20.不含任何數(shù)據(jù)元素的棧稱(chēng)為_(kāi)________。

　　21.稀疏矩陣一般采用的壓縮存儲(chǔ)方法是_________。

　　22.100個(gè)結(jié)點(diǎn)的二叉樹(shù)采用二叉鏈表存儲(chǔ)時(shí)，用來(lái)指向左、右孩子結(jié)點(diǎn)的指針域有_________個(gè)。

　　23.已知完全二叉樹(shù)的第5層有5個(gè)結(jié)點(diǎn)，則整個(gè)完全二叉樹(shù)有_________個(gè)結(jié)點(diǎn)。

　　24.n個(gè)頂點(diǎn)的有向圖G用鄰接矩陣A[1..n，1..n]存儲(chǔ)，其第i列的所有元素之和等于頂點(diǎn)

　　Vi的_________。

　　25.具有10個(gè)頂點(diǎn)的有向完全圖的弧數(shù)為_(kāi)________。

　　26.要完全避免散列所產(chǎn)生的“堆積’’現(xiàn)象，通常采用_________解決沖突。

　　27.在長(zhǎng)度為n的帶有崗哨的順序表中進(jìn)行順序查找，查找不成功時(shí)，與關(guān)鍵字的比較次數(shù)為_(kāi)________。

　　28.歸并排序算法的時(shí)間復(fù)雜度是_________。

　　三、應(yīng)用題(本大題共5小題，每小題6分，共30分)

　　29.稀疏矩陣A如題29圖所示，寫(xiě)出該稀疏矩陣A的三元組表示法。

　　30.設(shè)二叉樹(shù)的中序遍歷序列為BDCEAFHG，后序遍歷序列為DECBHGFA，試畫(huà)出該二叉樹(shù)。

　　31.寫(xiě)出題31圖所示無(wú)向圖的鄰接矩陣，并寫(xiě)出每個(gè)頂點(diǎn)的度。

　　題31圖

　　32.已知散列表的地址空間為0至13，散列函數(shù)H(k)=kmod11，(mod為求余運(yùn)算)，待散列序列為(26，61，38，84，49)，用二次探測(cè)法解決沖突，構(gòu)造該序列的散列表，要求寫(xiě)出處理沖突的過(guò)程。

　　33.將一組鍵值(80，50，65，13，86，35，96，57，39，79，59，15)應(yīng)用二路歸并排序算法從小到大排序，試寫(xiě)出各趟的結(jié)果。