廣州自考2009年10月考試模擬試題_數(shù)據(jù)結(jié)構(gòu)試題.doc

廣州自考2009年10月考試模擬試題_數(shù)據(jù)結(jié)構(gòu)試題,廣州自考2009年10月考試模擬試題，只供復(fù)習(xí)參考！
廣東自學(xué)考試簡(jiǎn)介廣東自考表格
廣州自考年月考試模擬試題數(shù)據(jù)結(jié)構(gòu)試題
課程代碼：
一、單項(xiàng)選擇題本大題共小題，每小題分，共分
在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是最符合題目要求的，請(qǐng)將其代碼填寫(xiě)在題后的括號(hào)內(nèi)。錯(cuò)選、多選或未選均無(wú)分。
如果在數(shù)據(jù)結(jié)構(gòu)中每個(gè)數(shù)據(jù)元素只可能有一個(gè)直接前驅(qū)，但可以有多個(gè)直接后繼，則該結(jié)構(gòu)是
棧隊(duì)列
樹(shù)圖
下面程序段的時(shí)間復(fù)雜度為






++在頭指針為的非空單循環(huán)鏈表中，指針指向尾結(jié)點(diǎn)，下列關(guān)系成立的是


若以和分別表示進(jìn)棧和退棧操作，則對(duì)初始狀態(tài)為空的�？梢赃M(jìn)行的棧操作系列是


兩個(gè)字符串相等的條件是
串的長(zhǎng)度相等含有相同的字符集
都是非空串串的長(zhǎng)度相等且對(duì)應(yīng)的字符相同
如果將矩陣×的每一列看成一個(gè)子表，整個(gè)矩陣看成是一個(gè)廣義表，即………，…并且可以通過(guò)求表頭和求表尾的運(yùn)算求取矩陣中的每一個(gè)元素，則求得的運(yùn)算是


已知一棵含個(gè)結(jié)點(diǎn)的二叉樹(shù)中只有一個(gè)葉子結(jié)點(diǎn)，則該樹(shù)中度為的結(jié)點(diǎn)個(gè)數(shù)為


在一個(gè)具有個(gè)頂點(diǎn)的有向圖中，所有頂點(diǎn)的出度之和為，則所有頂點(diǎn)的入度之和為


+如圖所示的有向無(wú)環(huán)圖可以得到的拓?fù)湫蛄械膫�(gè)數(shù)是


如圖所示的帶權(quán)無(wú)向圖的最小生成樹(shù)的權(quán)為


對(duì)長(zhǎng)度為的關(guān)鍵字序列進(jìn)行堆排序的空間復(fù)雜度為


已知用某種排序方法對(duì)關(guān)鍵字序列，，，，，，，，進(jìn)行排序時(shí)，前兩趟排序的結(jié)果為
，，，，，，，，
，，，，，，，，
所采用的排序方法是
插入排序冒泡排序
快速排序歸并排序
已知散列表的存儲(chǔ)空間為，散列函數(shù)并用二次探測(cè)法處理沖突。散列表中已插入下列關(guān)鍵字：，和，則下一個(gè)關(guān)鍵字插入的位置是


適宜進(jìn)行批量處理的文件類(lèi)型是
順序文件索引順序文件
散列文件多關(guān)鍵字文件
文件的索引結(jié)構(gòu)為
+樹(shù)二叉排序樹(shù)
樹(shù)最優(yōu)二叉樹(shù)
二、填空題本大題共小題，每小題分，共分
請(qǐng)?jiān)诿啃☆}的空格中填上正確答案。錯(cuò)填、不填均無(wú)分。
如果某算法對(duì)于規(guī)模為的問(wèn)題的時(shí)間耗費(fèi)為，在一臺(tái)計(jì)算機(jī)上運(yùn)行時(shí)間為秒，則在另一臺(tái)運(yùn)行速度是其倍的機(jī)器上，用同樣的時(shí)間能解決的問(wèn)題規(guī)模是原問(wèn)題規(guī)模的倍。
將兩個(gè)長(zhǎng)度分別為和的遞增有序單鏈表，歸并成一個(gè)按元素遞減有序的單鏈表，可能達(dá)到的最好的時(shí)間復(fù)雜度是。
已知循環(huán)隊(duì)列的存儲(chǔ)空間大小為，隊(duì)頭指針指向隊(duì)頭元素，隊(duì)尾指針指向隊(duì)尾元素的下一個(gè)位置，則在隊(duì)列不滿(mǎn)的情況下，隊(duì)列的長(zhǎng)度是。
字符串“”中存在有個(gè)與字符串“”相同的子串。
假設(shè)以列優(yōu)先順序存儲(chǔ)二維數(shù)組，其中元素的存儲(chǔ)地址為