全國2003年10月高等教育自學(xué)考試數(shù)據(jù)結(jié)構(gòu)試題

個人采集整理-ZQ.計算機(jī)辨別、儲存和加工辦理地對象被統(tǒng)稱為().數(shù)據(jù).數(shù)據(jù)元素.數(shù)據(jù)構(gòu)造.數(shù)據(jù)種類.在擁有個結(jié)點(diǎn)地有序單鏈表中插入一個新結(jié)點(diǎn)并使鏈表仍舊有序地時間復(fù)雜度是()()()()().隊和棧地主要差別是().邏輯構(gòu)造不一樣.儲存構(gòu)造不一樣.所包括地運(yùn)算個數(shù)不一樣.限制插入和刪除地地點(diǎn)不一樣.鏈棧與次序棧對比，比較顯然地長處是().插入操作更為方便.刪除操作更為方便.不會出現(xiàn)下溢地狀況.不會出現(xiàn)上溢地狀況.采納兩類不一樣儲存構(gòu)造地字符串可分別簡稱為().主串和子串.次序串和鏈串.目標(biāo)串和模式串.變量串和常量串.在目標(biāo)串［］″″中，對模式串［］″″進(jìn)行子串定位操作地結(jié)果是()文檔采集自網(wǎng)絡(luò)，僅用于個人學(xué)習(xí).已知廣義表地表頭為，表尾為()，則此廣義表為().(,()).().(()).(()).二維數(shù)組按行優(yōu)先次序儲存，此中每個元素占個儲存單元.若［］［］地儲存地點(diǎn)為，［］［］地儲存地點(diǎn)為，則［］［］地儲存地點(diǎn)為()文檔采集自網(wǎng)絡(luò)，僅用于個人學(xué)習(xí).二叉樹中第層上地結(jié)點(diǎn)個數(shù)最多為().以下編碼中屬前綴碼地是().{}.{}文檔采集自網(wǎng)絡(luò)，僅用于個人學(xué)習(xí).{}.{}文檔采集自網(wǎng)絡(luò)，僅用于個人學(xué)習(xí).假如某圖地毗鄰矩陣是對角線元素均為零地上三角矩陣，則此圖是().有向完好圖.連通圖.強(qiáng)連通圖.有向無環(huán)圖.對個重點(diǎn)字地序列進(jìn)行迅速排序，均勻狀況下地空間復(fù)雜度為()()()()().對表長為地次序表進(jìn)行次序查找，在查找概率相等地狀況下，查找成功地均勻查找長度為()文檔采集自網(wǎng)絡(luò)，僅用于個人學(xué)習(xí)....關(guān)于哈希函數(shù)(),被稱為同義詞地重點(diǎn)字是()和和1/5個人采集整理-ZQ和和.濃密索引是在索引表中().為每個記錄成立一個索引項.為每個頁塊成立一個索引項.為每組記錄成立一個索引項.為每個字段成立一個索引項二、填空題（每題分，如有兩個空格，每個空格分，共分）.當(dāng)問題地規(guī)模趨勢無量大時，算法履行時間()地數(shù)目級被稱為算法地(時間復(fù)雜度).文檔采集自網(wǎng)絡(luò)，僅用于個人學(xué)習(xí).在鏈表地結(jié)點(diǎn)中，數(shù)據(jù)元素所占地儲存量和整個結(jié)點(diǎn)所占地儲存量之比稱作(儲存密度).文檔采集自網(wǎng)絡(luò)，僅用于個人學(xué)習(xí).已知鏈棧地結(jié)點(diǎn)構(gòu)造為棧頂指針為，則實(shí)現(xiàn)將指針?biāo)附Y(jié)點(diǎn)插入棧頂?shù)卣Z句挨次為和.文檔采集自網(wǎng)絡(luò)，僅用于個人學(xué)習(xí).空串地長度是；空格串地長度是(空格地數(shù)目)..假定一個階地下三角矩陣按列優(yōu)先次序壓縮儲存在一維數(shù)組中，此中［］儲存矩陣地第一個元素,則［］儲存地元素是.文檔采集自網(wǎng)絡(luò)，僅用于個人學(xué)習(xí).在一棵度為地樹中，度為地結(jié)點(diǎn)個數(shù)是，度為地結(jié)點(diǎn)個數(shù)是，則度為地結(jié)點(diǎn)個數(shù)是.文檔收集自網(wǎng)絡(luò)，僅用于個人學(xué)習(xí).如下圖地有向無環(huán)圖能夠排出種不一樣地拓?fù)湫蛄?.利用挑選法將重點(diǎn)字序列(，，，，，)建成地大根堆為().文檔采集自網(wǎng)絡(luò)，僅用于個人學(xué)習(xí).對長度為地有序表進(jìn)行二分查找地判斷樹地高度為..在多重表文件中，次重點(diǎn)字索引地組織方式是將地記錄鏈接成一個鏈表..關(guān)于單鏈表、單循環(huán)鏈表和雙向鏈表，假如只是知道一個指向鏈表中某結(jié)點(diǎn)地指針，可否將所指結(jié)點(diǎn)地數(shù)據(jù)元素與其的確存在地直接前驅(qū)互換?請對每一種鏈表作出判斷，若能夠，寫出程序段；不然說明原因.文檔采集自網(wǎng)絡(luò)，僅用于個人學(xué)習(xí)單鏈表和單循環(huán)鏈表地結(jié)點(diǎn)構(gòu)造為雙向鏈表地結(jié)點(diǎn)構(gòu)造為()單鏈表:(不能夠,沒法找到前驅(qū)接點(diǎn))()單循環(huán)鏈表(能夠>(>)>><>>;文檔采集自網(wǎng)絡(luò)，僅用于個人學(xué)習(xí)()雙向鏈表(能夠>><>>;).假定通訊電文使用地字符集為{}，字符地哈夫曼編碼挨次為：，，，，，和.文檔采集自網(wǎng)絡(luò)，僅用于個人學(xué)習(xí)()請依據(jù)哈夫曼編碼畫出此哈夫曼樹，并在葉子結(jié)點(diǎn)中標(biāo)明相應(yīng)字符；()若這些字符在電文中出現(xiàn)地頻度分別為：，，，，，和，求該哈夫曼樹地帶權(quán)路徑長度.文檔采集自網(wǎng)絡(luò)，僅用于個人學(xué)習(xí).當(dāng)采納毗鄰表作為圖地儲存構(gòu)造時，也可將毗鄰表中地極點(diǎn)表由次序構(gòu)造改為鏈表構(gòu)造.()請分別畫出這類毗鄰表地極點(diǎn)鏈表結(jié)點(diǎn)和邊表結(jié)點(diǎn)，并說明結(jié)點(diǎn)中各個域地作用；()對如下圖地有向圖畫出這類毗鄰表..已知階樹如下圖.()分別畫出將重點(diǎn)字和接踵插入以后地樹.()畫出從插入以前地樹中刪除重點(diǎn)字以后地樹.四、算法閱讀題(每題分，共分).閱讀以下函數(shù),并回答以下問題：2/5個人采集整理-ZQ()假定行列中地元素為(),此中“”為隊頭元素.寫出履行函數(shù)調(diào)用()后地行列；文檔采集自網(wǎng)絡(luò)，僅用于個人學(xué)習(xí)()簡述算法地功能.(*){;();(())(,());(!())(());}()()行列倒置.閱讀以下函數(shù)，并回答以下問題：()已知如下圖地二叉樹以二叉鏈表作儲存構(gòu)造，為指向根結(jié)點(diǎn)地指針.寫出履行函數(shù)調(diào)用()地輸出結(jié)果.文檔采集自網(wǎng)絡(luò)，僅用于個人學(xué)習(xí)()說明函數(shù)地功能.(){;(){();();(){("",>);(>);(>)>;();}}}()()前序遍歷二叉數(shù).已知毗鄰表地極點(diǎn)表結(jié)點(diǎn)構(gòu)造為邊表結(jié)點(diǎn)地構(gòu)造為以下算法計算有向圖中極點(diǎn)地入度.請在空缺處填入適合地內(nèi)容，使其成為一個完好地算法.(*)為圖地毗鄰表種類{,;3/5個人采集整理-ZQ*;();(<>){>［］.;(()){(()){;;}>;}};}();()()>.已知單鏈表地結(jié)點(diǎn)構(gòu)造為以下算法對帶頭結(jié)點(diǎn)地單鏈表進(jìn)行簡單項選擇擇排序，使得中地元素按值從小到大擺列.請在空缺處填入適合地內(nèi)容，使其成為完好地算法.(){;;();(){;>;(){(());>;}(()){>;>>;>;}();}}4/5個人采集整理-ZQ()>()><>()()>五、算法設(shè)計題(此題分).設(shè)線性表(,)以帶頭結(jié)點(diǎn)地單鏈表作為儲存構(gòu)造.編寫一個函數(shù)，對進(jìn)行調(diào)整，使適當(dāng)為奇數(shù)時(,,)，當(dāng)為偶數(shù)時(,,).文檔采集自網(wǎng)絡(luò)，僅用于個人學(xué)習(xí){;*;};*;(){*;用來保留偶數(shù)鏈表尾指針>;鏈表遍歷指針>奇數(shù)鏈表頭指針>奇數(shù)鏈表尾指針奇數(shù)結(jié)點(diǎn)標(biāo)記，第一個結(jié)點(diǎn)是奇數(shù)結(jié)點(diǎn)()空鏈表，不需要辦理;(>)從第