




已閱讀5頁(yè),還剩37頁(yè)未讀, 繼續(xù)免費(fèi)閱讀
版權(quán)說(shuō)明:本文檔由用戶(hù)提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1 第一章概論 自測(cè)題答案 一 填空題 1 數(shù)據(jù)結(jié)構(gòu)是一門(mén)研究非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題中計(jì)算機(jī)的 操作對(duì)象 以及它們之間的 關(guān)系 和運(yùn)算等的學(xué) 科 2 數(shù)據(jù)結(jié)構(gòu)被形式地定義為 D R 其中 D 是 數(shù)據(jù)元素 的有限集合 R 是 D 上的 關(guān)系 有限集合 3 數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的 邏輯結(jié)構(gòu) 數(shù)據(jù)的 存儲(chǔ)結(jié)構(gòu) 和數(shù)據(jù)的 運(yùn)算 這三個(gè)方面的內(nèi)容 4 數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類(lèi) 它們分別是 線性結(jié)構(gòu) 和 非線性結(jié)構(gòu) 5 線性結(jié)構(gòu)中元素之間存在一對(duì)一關(guān)系 樹(shù)形結(jié)構(gòu)中元素之間存在一對(duì)多關(guān)系 圖形結(jié)構(gòu)中元素之間存在多對(duì)多關(guān)系 6 在線性結(jié)構(gòu)中 第一個(gè)結(jié)點(diǎn) 沒(méi)有 前驅(qū)結(jié)點(diǎn) 其余每個(gè)結(jié)點(diǎn)有且只有 1 個(gè)前驅(qū)結(jié)點(diǎn) 最后一個(gè)結(jié)點(diǎn) 沒(méi)有 后續(xù)結(jié) 點(diǎn) 其余每個(gè)結(jié)點(diǎn)有且只有 1 個(gè)后續(xù)結(jié)點(diǎn) 7 在樹(shù)形結(jié)構(gòu)中 樹(shù)根結(jié)點(diǎn)沒(méi)有 前驅(qū) 結(jié)點(diǎn) 其余每個(gè)結(jié)點(diǎn)有且只有 1 個(gè)前驅(qū)結(jié)點(diǎn) 葉子結(jié)點(diǎn)沒(méi)有 后續(xù) 結(jié)點(diǎn) 其余每個(gè)結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)數(shù)可以任意多個(gè) 8 在圖形結(jié)構(gòu)中 每個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)數(shù)和后續(xù)結(jié)點(diǎn)數(shù)可以 任意多個(gè) 9 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)可用四種基本的存儲(chǔ)方法表示 它們分別是順序 鏈?zhǔn)?索引 和 散列 10 數(shù)據(jù)的運(yùn)算最常用的有 5 種 它們分別是插入 刪除 修改 查找 排序 11 一個(gè)算法的效率可分為 時(shí)間 效率和 空間 效率 二 單項(xiàng)選擇題 B 1 非線性結(jié)構(gòu)是數(shù)據(jù)元素之間存在一種 A 一對(duì)多關(guān)系 B 多對(duì)多關(guān)系 C 多對(duì)一關(guān)系 D 一對(duì)一關(guān)系 C 2 數(shù)據(jù)結(jié)構(gòu)中 與所使用的計(jì)算機(jī)無(wú)關(guān)的是數(shù)據(jù)的 結(jié)構(gòu) A 存儲(chǔ) B 物理 C 邏輯 D 物理和存儲(chǔ) C 3 算法分析的目的是 A 找出數(shù)據(jù)結(jié)構(gòu)的合理性 B 研究算法中的輸入和輸出的關(guān)系 C 分析算法的效率以求改進(jìn) D 分析算法的易懂性和文檔性 A 4 算法分析的兩個(gè)主要方面是 A 空間復(fù)雜性和時(shí)間復(fù)雜性 B 正確性和簡(jiǎn)明性 C 可讀性和文檔性 D 數(shù)據(jù)復(fù)雜性和程序復(fù)雜性 C 5 計(jì)算機(jī)算法指的是 A 計(jì)算方法 B 排序方法 C 解決問(wèn)題的有限運(yùn)算序列 D 調(diào)度方法 B 6 計(jì)算機(jī)算法必須具備輸入 輸出和 等 5 個(gè)特性 A 可行性 可移植性和可擴(kuò)充性 B 可行性 確定性和有窮性 C 確定性 有窮性和穩(wěn)定性 D 易讀性 穩(wěn)定性和安全性 三 簡(jiǎn)答題 2 嚴(yán)題集 1 2 數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類(lèi)型兩個(gè)概念之間有區(qū)別嗎 答 簡(jiǎn)單地說(shuō) 數(shù)據(jù)結(jié)構(gòu)定義了一組按某些關(guān)系結(jié)合在一起的數(shù)組元素 數(shù)據(jù)類(lèi)型不僅定義了一組帶結(jié)構(gòu)的數(shù)據(jù)元素 而且 還在其上定義了一組操作 3 簡(jiǎn)述線性結(jié)構(gòu)與非線性結(jié)構(gòu)的不同點(diǎn) 答 線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是答 線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是 一對(duì)一的 非線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是多對(duì)多的 一對(duì)一的 非線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是多對(duì)多的 四 嚴(yán)題集 1 8 分析下面各程序段的時(shí)間復(fù)雜度 2 s 0 for i 0 i n i for j 0 j n j s B i j sum s 答 O n2 1 for i 0 i n i for j 0 j m j A i j 0 答 O m n 3 x 0 for i 1 i n i for j 1 j n i j x 解 因?yàn)?x 共執(zhí)行了 n 1 n 2 1 n n 1 2 所以執(zhí)行時(shí)間為 O n2 4 i 1 while i n i i 3 答 O log3n 2 五 設(shè)有數(shù)據(jù)邏輯結(jié)構(gòu) S D R 試按各小題所給條件畫(huà)出這些邏輯結(jié)構(gòu)的圖示 并確定相對(duì)于關(guān)系 R 哪些結(jié)點(diǎn)是開(kāi)始 結(jié)點(diǎn) 哪些結(jié)點(diǎn)是終端結(jié)點(diǎn) 1 嚴(yán)蔚敏習(xí)題集 P7 1 3 D d1 d2 d3 d4 R d1 d2 d2 d3 d3 d4 答 d1 d2 d3 d4 d1 無(wú)直接前驅(qū) 是首結(jié)點(diǎn) d4 無(wú)直接后繼是尾結(jié)點(diǎn) 2 D d1 d2 d9 R d1 d2 d1 d3 d3 d4 d3 d6 d6 d8 d4 d5 d6 d7 d8 d9 答 此圖為樹(shù)形結(jié)構(gòu) d1 無(wú)直接前驅(qū) 是根結(jié)點(diǎn) d2 d5 d7 d9 無(wú)直接后繼是葉子結(jié)點(diǎn) 3 D d1 d2 d9 R d1 d3 d1 d8 d2 d3 d2 d4 d2 d5 d3 d9 d5 d6 d8 d9 d9 d7 d4 d7 d4 d6 答 此圖為圖形結(jié)構(gòu) d1 d2 無(wú)直接前驅(qū) 是開(kāi)始結(jié)點(diǎn) d6 d7 無(wú)直接后繼是終端結(jié)點(diǎn) 2 3 第 2 章 自測(cè)卷答案 一 填空 1 嚴(yán)題集 2 2 在順序表中插入或刪除一個(gè)元素 需要平均移動(dòng) 表中一半元素 具體移動(dòng)的元素個(gè)數(shù)與 表長(zhǎng)和該元素 在表中的位置 有關(guān) 2 線性表中結(jié)點(diǎn)的集合是 有限 的 結(jié)點(diǎn)間的關(guān)系是 一對(duì)一 的 3 向一個(gè)長(zhǎng)度為 n 的向量的第 i 個(gè)元素 1 i n 1 之前插入一個(gè)元素時(shí) 需向后移動(dòng) n i 1 個(gè)元素 4 向一個(gè)長(zhǎng)度為 n 的向量中刪除第 i 個(gè)元素 1 i n 時(shí) 需向前移動(dòng) n i 個(gè)元素 5 在順序表中訪問(wèn)任意一結(jié)點(diǎn)的時(shí)間復(fù)雜度均為 O 1 因此 順序表也稱(chēng)為 隨機(jī)存取 的數(shù)據(jù)結(jié)構(gòu) 6 嚴(yán)題集 2 2 順序表中邏輯上相鄰的元素的物理位置 必定相鄰 單鏈表中邏輯上相鄰的元素的物理位置 不一定 相 鄰 7 嚴(yán)題集 2 2 在單鏈表中 除了首元結(jié)點(diǎn)外 任一結(jié)點(diǎn)的存儲(chǔ)位置由 其直接前驅(qū)結(jié)點(diǎn)的鏈域的值 指示 8 在 n 個(gè)結(jié)點(diǎn)的單鏈表中要?jiǎng)h除已知結(jié)點(diǎn) p 需找到它的前驅(qū)結(jié)點(diǎn)的地址 其時(shí)間復(fù)雜度為 O n 二 判斷正誤 在正確的說(shuō)法后面打勾 反之打叉 1 鏈表的每個(gè)結(jié)點(diǎn)中都恰好包含一個(gè)指針 答 錯(cuò)誤 鏈表中的結(jié)點(diǎn)可含多個(gè)指針域 分別存放多個(gè)指針 例如 雙向鏈表中的結(jié)點(diǎn)可以含有兩個(gè)指針 域 分別存放指向其直接前趨和直接后繼結(jié)點(diǎn)的指針 2 鏈表的物理存儲(chǔ)結(jié)構(gòu)具有同鏈表一樣的順序 錯(cuò) 鏈表的存儲(chǔ)結(jié)構(gòu)特點(diǎn)是無(wú)序 而鏈表的示意圖有序 3 鏈表的刪除算法很簡(jiǎn)單 因?yàn)楫?dāng)刪除鏈中某個(gè)結(jié)點(diǎn)后 計(jì)算機(jī)會(huì)自動(dòng)地將后續(xù)的各個(gè)單元向前移動(dòng) 錯(cuò) 鏈表 的結(jié)點(diǎn)不會(huì)移動(dòng) 只是指針內(nèi)容改變 4 線性表的每個(gè)結(jié)點(diǎn)只能是一個(gè)簡(jiǎn)單類(lèi)型 而鏈表的每個(gè)結(jié)點(diǎn)可以是一個(gè)復(fù)雜類(lèi)型 錯(cuò) 混淆了邏輯結(jié)構(gòu)與物理結(jié)構(gòu) 鏈表也是線性表 且即使是順序表 也能存放記錄型數(shù)據(jù) 5 順序表結(jié)構(gòu)適宜于進(jìn)行順序存取 而鏈表適宜于進(jìn)行隨機(jī)存取 錯(cuò) 正好說(shuō)反了 順序表才適合隨機(jī)存取 鏈表恰恰適于 順藤摸瓜 6 順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大 且插入 刪除運(yùn)算效率高 錯(cuò) 前一半正確 但后一半說(shuō)法錯(cuò)誤 那是鏈?zhǔn)酱鎯?chǔ)的優(yōu)點(diǎn) 順序存儲(chǔ)方式插入 刪除運(yùn)算效率較低 在表長(zhǎng)為 n 的順序表中 插入和刪除一個(gè)數(shù)據(jù)元素 平均需移動(dòng)表長(zhǎng)一半個(gè)數(shù)的數(shù)據(jù)元素 7 線性表在物理存儲(chǔ)空間中也一定是連續(xù)的 錯(cuò) 線性表有兩種存儲(chǔ)方式 順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ) 后者不要求連續(xù)存放 8 線性表在順序存儲(chǔ)時(shí) 邏輯上相鄰的元素未必在存儲(chǔ)的物理位置次序上相鄰 錯(cuò)誤 線性表有兩種存儲(chǔ)方式 在順序存儲(chǔ)時(shí) 邏輯上相鄰的元素在存儲(chǔ)的物理位置次序上也相鄰 9 順序存儲(chǔ)方式只能用于存儲(chǔ)線性結(jié)構(gòu) 錯(cuò)誤 順序存儲(chǔ)方式不僅能用于存儲(chǔ)線性結(jié)構(gòu) 還可以用來(lái)存放非線性結(jié)構(gòu) 例如完全二叉樹(shù)是屬于非線性結(jié)構(gòu) 但 其最佳存儲(chǔ)方式是順序存儲(chǔ)方式 后一節(jié)介紹 3 10 線性表的邏輯順序與存儲(chǔ)順序總是一致的 錯(cuò) 理由同 7 鏈?zhǔn)酱鎯?chǔ)就無(wú)需一致 三 單項(xiàng)選擇題 C 1 數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)器內(nèi)表示時(shí) 物理地址與邏輯地址相同并且是連續(xù)的 稱(chēng)之為 A 存儲(chǔ)結(jié)構(gòu) B 邏輯結(jié)構(gòu) C 順序存儲(chǔ)結(jié)構(gòu) D 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) B 2 一個(gè)向量第一個(gè)元素的存儲(chǔ)地址是 100 每個(gè)元素的長(zhǎng)度為 2 則第 5 個(gè)元素的地址是 A 110 B 108 C 100 D 120 A 3 在 n 個(gè)結(jié)點(diǎn)的順序表中 算法的時(shí)間復(fù)雜度是 O 1 的操作是 A 訪問(wèn)第 i 個(gè)結(jié)點(diǎn) 1 i n 和求第 i 個(gè)結(jié)點(diǎn)的直接前驅(qū) 2 i n B 在第 i 個(gè)結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn) 1 i n C 刪除第 i 個(gè)結(jié)點(diǎn) 1 i n D 將 n 個(gè)結(jié)點(diǎn)從小到大排序 B 4 向一個(gè)有 127 個(gè)元素的順序表中插入一個(gè)新元素并保持原來(lái)順序不變 平均要移動(dòng) 個(gè)元素 A 8 B 63 5 C 63 D 7 A 5 鏈接存儲(chǔ)的存儲(chǔ)結(jié)構(gòu)所占存儲(chǔ)空間 A 分兩部分 一部分存放結(jié)點(diǎn)值 另一部分存放表示結(jié)點(diǎn)間關(guān)系的指針 B 只有一部分 存放結(jié)點(diǎn)值 C 只有一部分 存儲(chǔ)表示結(jié)點(diǎn)間關(guān)系的指針 D 分兩部分 一部分存放結(jié)點(diǎn)值 另一部分存放結(jié)點(diǎn)所占單元數(shù) B 6 鏈表是一種采用 存儲(chǔ)結(jié)構(gòu)存儲(chǔ)的線性表 A 順序 B 鏈?zhǔn)?C 星式 D 網(wǎng)狀 D 7 線性表若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí) 要求內(nèi)存中可用存儲(chǔ)單元的地址 A 必須是連續(xù)的 B 部分地址必須是連續(xù)的 C 一定是不連續(xù)的 D 連續(xù)或不連續(xù)都可以 B 8 線性表 在 情況下適用于使用鏈?zhǔn)浇Y(jié)構(gòu)實(shí)現(xiàn) 需經(jīng)常修改 中的結(jié)點(diǎn)值 需不斷對(duì) 進(jìn)行刪除插入 中含有大量的結(jié)點(diǎn) 中結(jié)點(diǎn)結(jié)構(gòu)復(fù)雜 C 9 單鏈表的存儲(chǔ)密度 大于 1 等于 1 小于 1 不能確定 B 10 設(shè) a1 a2 a3 為 3 個(gè)結(jié)點(diǎn) 整數(shù) P0 3 4 代表地址 則如下的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱(chēng)為 P0 3 4 P0 a1 3 a2 4 A3 0 循環(huán)鏈表 單鏈表 雙向循環(huán)鏈表 雙向鏈表 四 簡(jiǎn)答題 1 嚴(yán)題集 2 3 試比較順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn) 在什么情況下用順序表比鏈表好 答 順序存儲(chǔ)時(shí) 相鄰數(shù)據(jù)元素的存放地址也相鄰 邏輯與物理統(tǒng)一 要求內(nèi)存中可用存儲(chǔ)單元的地址必須是連續(xù)的 優(yōu)點(diǎn) 存儲(chǔ)密度大 1 存儲(chǔ)空間利用率高 缺點(diǎn) 插入或刪除元素時(shí)不方便 鏈?zhǔn)酱鎯?chǔ)時(shí) 相鄰數(shù)據(jù)元素可隨意存放 但所占存儲(chǔ)空間分兩部分 一部分存放結(jié)點(diǎn)值 另一部分存放表示結(jié)點(diǎn)間 關(guān)系的指針 優(yōu)點(diǎn) 插入或刪除元素時(shí)很方便 使用靈活 缺點(diǎn) 存儲(chǔ)密度小 top0 ST top 0 ST topm0 ST top m0 A 4 李春葆 判定一個(gè)隊(duì)列 QU 最多元素為 m0 為滿(mǎn)隊(duì)列的條件是 QU rear QU front m0 QU rear QU front 1 m0 QU front QU rear QU front QU rear 1 解 隊(duì)滿(mǎn)條件是元素個(gè)數(shù)為 m0 由于約定滿(mǎn)隊(duì)時(shí)隊(duì)首指針與隊(duì)尾指針相差 1 所以不必再減 1 了 應(yīng)當(dāng)選 A 當(dāng)然 更正 確的答案應(yīng)該取模 即 QU front QU rear 1 m0 D 5 數(shù)組 用來(lái)表示一個(gè)循環(huán)隊(duì)列 為當(dāng)前隊(duì)列頭元素的前一位置 為隊(duì)尾元素的位置 假定隊(duì)列 中元素的個(gè)數(shù)小于 計(jì)算隊(duì)列中元素的公式為 r f n f r n n r f n r f n 6 98 初程 P71 從供選擇的答案中 選出應(yīng)填入下面敘述 內(nèi)的最確切的解答 把相應(yīng)編號(hào)寫(xiě)在答卷的對(duì)應(yīng)欄 5 內(nèi) 設(shè)有 4 個(gè)數(shù)據(jù)元素 a1 a2 a3 和 a4 對(duì)他們分別進(jìn)行棧操作或隊(duì)操作 在進(jìn)?;蜻M(jìn)隊(duì)操作時(shí) 按 a1 a2 a3 a4 次 序每次進(jìn)入一個(gè)元素 假設(shè)?;蜿?duì)的初始狀態(tài)都是空 現(xiàn)要進(jìn)行的棧操作是進(jìn)棧兩次 出棧一次 再進(jìn)棧兩次 出棧一次 這時(shí) 第一次出棧得到的元素是 A 第二次 出棧得到的元素是 B 是 類(lèi)似地 考慮對(duì)這四個(gè)數(shù)據(jù)元素進(jìn)行的隊(duì)操作是進(jìn)隊(duì)兩次 出隊(duì)一次 再進(jìn)隊(duì)兩次 出隊(duì) 一次 這時(shí) 第一次出隊(duì)得到的元素是 C 第二次出隊(duì)得到的元素是 D 經(jīng)操作后 最后在棧中或隊(duì)中的元 素還有 E 個(gè) 供選擇的答案 A D a1 a2 a3 a4 E 1 2 3 0 答 ABCDE 2 4 1 2 2 7 94 初程 P75 從供選擇的答案中 選出應(yīng)填入下面敘述 內(nèi)的最確切的解答 把相應(yīng)編號(hào)寫(xiě)在答卷的對(duì)應(yīng)欄 內(nèi) 棧是一種線性表 它的特點(diǎn)是 A 設(shè)用一維數(shù)組 A 1 n 來(lái)表示一個(gè)棧 A n 為棧底 用整型變量 T 指示當(dāng)前棧 頂位置 A T 為棧頂元素 往棧中推入 PUSH 一個(gè)新元素時(shí) 變量 T 的值 B 從棧中彈出 POP 一個(gè)元素時(shí) 變 量 T 的值 C 設(shè)??諘r(shí) 有輸入序列 a b c 經(jīng)過(guò) PUSH POP PUSH PUSH POP 操作后 從棧中彈出的元素的 序列是 D 變量 T 的值是 E 供選擇的答案 A 先進(jìn)先出 后進(jìn)先出 進(jìn)優(yōu)于出 出優(yōu)于進(jìn) 隨機(jī)進(jìn)出 B C 加 1 減 1 不變 清 0 加 2 減 2 D a b b c c a b a c b a c E n 1 n 2 n n 1 n 2 答案 ABCDE 2 2 1 6 4 注意 向地址的高端生長(zhǎng) 稱(chēng)為向上生成堆棧 向地址低端生長(zhǎng)叫向下生成堆棧 本題中底部為 n 向地址的低端遞減生成 稱(chēng)為向下生成堆棧 8 91 初程 P77 從供選擇的答案中 選出應(yīng)填入下面敘述 內(nèi)的最確切的解答 把相應(yīng)編號(hào)寫(xiě)在答卷的對(duì)應(yīng)欄 內(nèi) 在做進(jìn)棧運(yùn)算時(shí) 應(yīng)先判別棧是否 A 在做退棧運(yùn)算時(shí) 應(yīng)先判別棧是否 B 當(dāng)棧中元素為 n 個(gè) 做進(jìn)棧運(yùn) 算時(shí)發(fā)生上溢 則說(shuō)明該棧的最大容量為 C 為了增加內(nèi)存空間的利用率和減少溢出的可能性 由兩個(gè)棧共享一片連續(xù)的內(nèi)存空間時(shí) 應(yīng)將兩棧的 D 分別設(shè)在這片 內(nèi)存空間的兩端 這樣 只有當(dāng) E 時(shí) 才產(chǎn)生上溢 供選擇的答案 A B 空 滿(mǎn) 上溢 下溢 C n 1 n n 1 n 2 D 長(zhǎng)度 深度 棧頂 棧底 E 兩個(gè)棧的棧頂同時(shí)到達(dá)棧空間的中心點(diǎn) 其中一個(gè)棧的棧頂?shù)竭_(dá)??臻g的中心點(diǎn) 兩個(gè)棧的棧頂在達(dá)棧空間的某一位置相遇 兩個(gè)棧均不空 且一個(gè)棧的棧頂?shù)竭_(dá)另一個(gè)棧的棧底 答案 ABCDE 2 1 2 4 3 四 簡(jiǎn)答題 每小題 4 分 共 20 分 1 嚴(yán)題集 3 2 和 3 11 說(shuō)明線性表 棧與隊(duì)的異同點(diǎn) 劉答 相同點(diǎn) 都是線性結(jié)構(gòu) 都是邏輯結(jié)構(gòu)的概念 都可以用順序存儲(chǔ)或鏈表存儲(chǔ) 棧和隊(duì)列是兩種特殊的線性表 即受 限的線性表 只是對(duì)插入 刪除運(yùn)算加以限制 不同點(diǎn) 運(yùn)算規(guī)則不同 線性表為隨機(jī)存取 而棧是只允許在一端進(jìn)行插入 刪除運(yùn)算 因而是后進(jìn)先出表 LIFO 隊(duì)列 是只允許在一端進(jìn)行插入 另一端進(jìn)行刪除運(yùn)算 因而是先進(jìn)先出表 FIFO 用途不同 堆棧用于子程調(diào)用和保護(hù)現(xiàn)場(chǎng) 隊(duì)列用于多道作業(yè)處理 指令寄存及其他運(yùn)算等等 2 統(tǒng)考書(shū) P60 4 11 難于嚴(yán)題集 3 1 設(shè)有編號(hào)為 1 2 3 4 的四輛列車(chē) 順序進(jìn)入一個(gè)棧式結(jié)構(gòu)的車(chē)站 具體寫(xiě)出 這四輛列車(chē)開(kāi)出車(chē)站的所有可能的順序 劉答 至少有 14 種 全進(jìn)之后再出情況 只有 1 種 4 3 2 1 進(jìn) 3 個(gè)之后再出的情況 有 3 種 3 4 2 1 3 2 4 1 3 2 1 4 進(jìn) 2 個(gè)之后再出的情況 有 5 種 2 4 3 1 2 3 4 1 2 1 3 4 2 1 4 3 2 3 1 4 進(jìn) 1 個(gè)之后再出的情況 有 5 種 1 4 3 2 1 3 2 4 1 3 4 2 1 2 3 4 1 2 4 3 3 劉自編 假設(shè)正讀和反讀都相同的字符序列為 回文 例如 abba 和 abcba 是回文 abcde 和 ababab 則 不是回文 假設(shè)一字符序列已存入計(jì)算機(jī) 請(qǐng)分析用線性表 堆棧和隊(duì)列等方式正確輸出其回文的可能性 答 線性表是隨機(jī)存儲(chǔ) 可以實(shí)現(xiàn) 靠循環(huán)變量 j 從表尾開(kāi)始打印輸出 堆棧是后進(jìn)先出 也可以實(shí)現(xiàn) 靠正序入棧 逆序出棧即可 隊(duì)列是先進(jìn)先出 不易實(shí)現(xiàn) 6 哪種方式最好 要具體情況具體分析 若正文在機(jī)內(nèi)已是順序存儲(chǔ) 則直接用線性表從后往前讀取即可 或?qū)⒍褩m?開(kāi)到數(shù)組末尾 然后直接用 POP 動(dòng)作實(shí)現(xiàn) 但堆棧是先減后壓還是 若正文是單鏈表形式存儲(chǔ) 則等同于隊(duì)列 需開(kāi)輔助空間 可以從鏈?zhǔn)组_(kāi)始入棧 全部壓入后再依次輸出 4 統(tǒng)考書(shū) P60 4 13 順序隊(duì)的 假溢出 是怎樣產(chǎn)生的 如何知道循環(huán)隊(duì)列是空還是滿(mǎn) 答 一般的一維數(shù)組隊(duì)列的尾指針已經(jīng)到了數(shù)組的上界 不能再有入隊(duì)操作 但其實(shí)數(shù)組中還有空位置 這就叫 假溢出 采用循環(huán)隊(duì)列是解決假溢出的途徑 另外 解決隊(duì)滿(mǎn)隊(duì)空的辦法有三 設(shè)置一個(gè)布爾變量以區(qū)別隊(duì)滿(mǎn)還是隊(duì)空 浪費(fèi)一個(gè)元素的空間 用于區(qū)別隊(duì)滿(mǎn)還是隊(duì)空 使用一個(gè)計(jì)數(shù)器記錄隊(duì)列中元素個(gè)數(shù) 即隊(duì)列長(zhǎng)度 我們常采用法 即隊(duì)頭指針 隊(duì)尾指針中有一個(gè)指向?qū)嵲?而另一個(gè)指向空閑元素 判斷循環(huán)隊(duì)列隊(duì)空標(biāo)志是 f rear 隊(duì)滿(mǎn)標(biāo)志是 f r 1 N 5 統(tǒng)考書(shū) P60 4 14 設(shè)循環(huán)隊(duì)列的容量為 40 序號(hào)從 0 到 39 現(xiàn)經(jīng)過(guò)一系列的入隊(duì)和出隊(duì)運(yùn)算后 有 front 11 rear 19 front 19 rear 11 問(wèn)在這兩種情況下 循環(huán)隊(duì)列中各有元素多少個(gè) 答 用隊(duì)列長(zhǎng)度計(jì)算公式 N r f N L 40 19 11 40 8 L 40 11 19 40 32 五 閱讀理解 每小題 5 分 共 20 分 至少要寫(xiě)出思路 1 嚴(yán)題集 3 7 按照四則運(yùn)算加 減 乘 除和冪運(yùn)算 優(yōu)先關(guān)系的慣例 并仿照教材例 3 2 的格式 畫(huà)出對(duì)下 列算術(shù)表達(dá)式求值時(shí)操作數(shù)棧和運(yùn)算符棧的變化過(guò)程 A B C D E F 答 2 嚴(yán)題集 3 3 寫(xiě)出下列程序段的輸出結(jié)果 棧的元素類(lèi)型 SElem Type 為 char void main Stack S Char x y InitStack S X c y k 7 Push S x Push S a Push S y Pop S x Push S t Push S x Pop S x Push S s while StackEmpty S Pop S y printf y Printf x 答 輸出為 stack 3 嚴(yán)題集 3 12 寫(xiě)出下列程序段的輸出結(jié)果 隊(duì)列中的元素類(lèi)型 QElem Type 為 char void main Queue Q Init Queue Q Char x e y c EnQueue Q h EnQueue Q r EnQueue Q y DeQueue Q x EnQueue Q x DeQueue Q x EnQueue Q a while QueueEmpty Q DeQueue Q y printf y Printf x 答 輸出為 char 4 嚴(yán)題集 3 13 簡(jiǎn)述以下算法的功能 棧和隊(duì)列的元素類(lèi)型均為 int void algo3 Queue int d InitStack S while QueueEmpty Q DeQueue Q d Push S d while StackEmpty S Pop S d EnQueue Q d 答 該算法的功能是 利用堆棧做輔助 將隊(duì)列中的數(shù)據(jù)元素進(jìn)行逆置 六 算法設(shè)計(jì) 每小題 5 分 共 15 分 至少要寫(xiě)出思路 1 李春葆及嚴(yán)題集 3 19 假設(shè)一個(gè)算術(shù)表達(dá)式中包含圓括弧 方括弧和花括弧三種類(lèi)型的括弧 編寫(xiě)一個(gè)判別表達(dá)式 中括弧是否正確配對(duì)的函數(shù) correct exp tag 其中 exp 為字符串類(lèi)型的變量 可理解為每個(gè)字符占用一個(gè)數(shù)組元素 表示被判別的表達(dá)式 tag 為布爾型變量 答 用堆棧 st 進(jìn)行判定 將 或 入棧 當(dāng)遇到 或 時(shí) 檢查當(dāng)前棧頂元素是否是對(duì)應(yīng)的 或 若是則退棧 否則返回表示不配對(duì) 當(dāng)整個(gè)算術(shù)表達(dá)式檢查完畢時(shí) 若棧為空表示括號(hào)正確配對(duì) 否則不配對(duì) 編程后的整個(gè)函數(shù)如下 李書(shū) P31 32 define m0 100 m0 為算術(shù)表達(dá)式中最多字符個(gè)數(shù) correct exp tag char exp m0 int tag char st m0 int top 0 i 1 tag 1 while i0 tag 0 若棧不空 則不配對(duì) 嚴(yán)題集對(duì)應(yīng)答案 8 3 19 Status AllBrackets Test char str 判別表達(dá)式中三種括號(hào)是否匹配 InitStack s for p str p p if p p p push s p else if p p p if StackEmpty s return ERROR pop s c if p if p if p 必須與當(dāng)前棧頂括號(hào)匹配 for if StackEmpty s return ERROR return OK AllBrackets Test 2001 級(jí)通信 6 班張沐同學(xué)答案 已上機(jī)通過(guò) include include void push char x void pop void correct enum Boolean 原來(lái)的定義是 void correct struct Stack head enum Boolean typedef struct Stack char data struct Stack next struct Stack head p enum Boolean FALSE TRUE tag void main head struct Stack malloc sizeof struct Stack head data S head next NULL head s data has not been initialized correct tag if tag printf Right else printf Wrong void push char x p struct Stack malloc sizeof struct Stack if p printf There s no space n else p data x p next head head p if you define the Correct function like that Debug will show that the Push action doesn t take effection void pop if head next NULL printf The stack is empty n 9 else p head head head next free p void correct struct Stack head enum Boolean char y printf Please enter a bds for i 0 y n i scanf c if y else if y y y push y 調(diào)試程序顯示 y 并沒(méi)有被推入堆棧中 即 head data 的值在 Push 中顯示為 y 的值 但是出 Push 函數(shù) 馬上變成 Null else continue if head next NULL 原來(lái)的程序是 if head NULL tag TRUE tag TRUE else tag FALSE 總結(jié) 由于 head 為全局變量 所以不應(yīng)該將其再次作為函數(shù)的變量 因?yàn)?C 語(yǔ)言的函數(shù)變量是傳值機(jī)制 所以在函數(shù)中 對(duì)參數(shù)進(jìn)行了拷貝復(fù)本 所以不能改變 head 的數(shù)值 2 統(tǒng)考書(shū) P60 4 15 假設(shè)一個(gè)數(shù)組 squ m 存放循環(huán)隊(duì)列的元素 若要使這 m 個(gè)分量都得到利用 則需另一個(gè)標(biāo)志 tag 以 tag 為 0 或 1 來(lái)區(qū)分尾指針和頭指針值相同時(shí)隊(duì)列的狀態(tài)是 空 還是 滿(mǎn) 試編寫(xiě)相應(yīng)的入隊(duì)和出隊(duì)的算法 解 這就是解決隊(duì)滿(mǎn)隊(duì)空的三種辦法之 設(shè)置一個(gè)布爾變量以區(qū)別隊(duì)滿(mǎn)還是隊(duì)空 其他兩種見(jiàn)簡(jiǎn)答題 思路 一開(kāi)始隊(duì)空 設(shè) tag 0 若從 rear 一端加到與 front 指針相同時(shí) 表示入隊(duì)已滿(mǎn) 則令 tag 1 若從 front 一端加到與 rear 指針相同時(shí) 則令 tag 0 表示出隊(duì)已空 3 嚴(yán)題集 3 31 試寫(xiě)一個(gè)算法判別讀入的一個(gè)以 為結(jié)束符的字符序列是否是 回文 答 編程如下 int Palindrome Test 判別輸入的字符串是否回文序列 是則返回 1 否則返回 0 InitStack S InitQueue Q while c getchar Push S c EnQueue Q c 同時(shí)使用棧和隊(duì)列兩種結(jié)構(gòu) while StackEmpty S Pop S a DeQueue Q b if a b return ERROR return OK Palindrome Test 第 4 5 章 串和數(shù)組 一 填空題 每空 1 分 共 20 分 1 不包含任何字符 長(zhǎng)度為 0 的串 稱(chēng)為空串 由一個(gè)或多個(gè)空格 僅由空格符 組成的串 稱(chēng)為空白串 對(duì)應(yīng)嚴(yán)題集 4 1 簡(jiǎn)答題 簡(jiǎn)述空串和空格串的區(qū)別 2 設(shè) S A document Mary doc 則 strlen s 20 的字符定位的位置為 3 4 子串的定位運(yùn)算稱(chēng)為串的模式匹配 被匹配的主串 稱(chēng)為目標(biāo)串 子串 稱(chēng)為模式 5 設(shè)目標(biāo) T abccdcdccbaa 模式 P cdcc 則第 6 次匹配成功 10 6 若 n 為主串長(zhǎng) m 為子串長(zhǎng) 則串的古典 樸素 匹配算法最壞的情況下需要比較字符的總次數(shù)為 n m 1 m 7 假設(shè)有二維數(shù)組 A6 8 每個(gè)元素用相鄰的 6 個(gè)字節(jié)存儲(chǔ) 存儲(chǔ)器按字節(jié)編址 已知 A 的起始存儲(chǔ)位置 基地址 為 1000 則數(shù)組 A 的體積 存儲(chǔ)量 為 288 B 末尾元素 A57的第一個(gè)字節(jié)地址為 1282 若按行存儲(chǔ)時(shí) 元素 A14的 第一個(gè)字節(jié)地址為 8 4 6 1000 1072 若按列存儲(chǔ)時(shí) 元素 A47的第一個(gè)字節(jié)地址為 6 7 4 6 1000 1276 注 數(shù)組是從 0 行 0 列還是從 1 行 1 列計(jì)算起呢 由末單元為 A57可知 是從 0 行 0 列開(kāi)始 8 00 年計(jì)算機(jī)系考研題 設(shè)數(shù)組 a 1 60 1 70 的基地址為 2048 每個(gè)元素占 2 個(gè)存儲(chǔ)單元 若以列序?yàn)橹餍蝽樞虼鎯?chǔ) 則元素 a 32 58 的存儲(chǔ)地址為 8950 答 不考慮 0 行 0 列 利用列優(yōu)先公式 LOC aij LOC ac1 c2 j c2 d1 c1 1 i c1 L 得 LOC a32 58 2048 58 1 60 1 1 32 1 2 8950 9 三元素組表中的每個(gè)結(jié)點(diǎn)對(duì)應(yīng)于稀疏矩陣的一個(gè)非零元素 它包含有三個(gè)數(shù)據(jù)項(xiàng) 分別表示該元素 的 行下標(biāo) 列下標(biāo) 和 元素值 10 求下列廣義表操作的結(jié)果 1 GetHead a b c d a b 頭元素不必加括號(hào) 2 GetHead GetTail a b c d c d 3 GetHead GetTail GetHead a b c d b 4 GetTail GetHead GetTail a b c d d 二 單選題 每小題 1 分 共 15 分 B 1 李 串是一種特殊的線性表 其特殊性體現(xiàn)在 可以順序存儲(chǔ) 數(shù)據(jù)元素是一個(gè)字符 可以鏈?zhǔn)酱鎯?chǔ) 數(shù)據(jù)元素可以是多個(gè)字符 B 2 李 設(shè)有兩個(gè)串 p 和 q 求 q 在 p 中首次出現(xiàn)的位置的運(yùn)算稱(chēng)作 連接 模式匹配 求子串 求串長(zhǎng) D 3 李 設(shè)串 s1 ABCDEFG s2 PQRST 函數(shù) con x y 返回 x 和 y 串的連接串 subs s i j 返回串 s 的從序號(hào) i 開(kāi)始的 j 個(gè)字符組成的子串 len s 返回串 s 的長(zhǎng)度 則 con subs s1 2 len s2 subs s1 len s2 2 的結(jié)果串是 BCDEF BCDEFG BCPQRST BCDEFEF 解 con x y 返回 x 和 y 串的連接串 即 con x y ABCDEFGPQRST subs s i j 返回串 s 的從序號(hào) i 開(kāi)始的 j 個(gè)字符組成的子串 則 subs s1 2 len s2 subs s1 2 5 BCDEF subs s1 len s2 2 subs s1 5 2 EF 所以 con subs s1 2 len s2 subs s1 len s2 2 con BCDEF EF 之連接 即 BCDEFEF A 4 01 年計(jì)算機(jī)系考研題 假設(shè)有 60 行 70 列的二維數(shù)組 a 1 60 1 70 以列序?yàn)橹餍蝽樞虼鎯?chǔ) 其基地址為 10000 每個(gè)元素占 2 個(gè)存儲(chǔ)單元 那么第 32 行第 58 列的元素 a 32 58 的存儲(chǔ)地址為 無(wú)第 0 行第 0 列元素 16902 16904 14454 答案 A B C 均不對(duì) 答 此題與填空題第 8 小題相似 57 列 60 行 31 行 2 字節(jié) 10000 16902 B 5 設(shè)矩陣 A 是一個(gè)對(duì)稱(chēng)矩陣 為了節(jié)省存儲(chǔ) 將其下三角部分 如下圖所示 按行序存放在一維數(shù)組 B 1 n n 1 2 中 對(duì)下三角部分中任一元素 ai j i j 在一維數(shù)組 B 中下標(biāo) k 的值是 i i 1 2 j 1 i i 1 2 j i i 1 2 j 1 i i 1 2 j 6 91 初程 P78 從供選擇的答案中 選出應(yīng)填入下面敘述 內(nèi)的最確切的解答 把相應(yīng)編號(hào)寫(xiě)在答卷的對(duì)應(yīng)欄內(nèi) 有一個(gè)二維數(shù)組 A 行下標(biāo)的范圍是 0 到 8 列下標(biāo)的范圍是 1 到 5 每個(gè)數(shù)組元素用相鄰的 4 個(gè)字節(jié)存儲(chǔ) 存儲(chǔ)器按 字節(jié)編址 假設(shè)存儲(chǔ)數(shù)組元素 A 0 1 的第一個(gè)字節(jié)的地址是 0 存儲(chǔ)數(shù)組 A 的最后一個(gè)元素的第一個(gè)字節(jié)的地址是 A 若按行存儲(chǔ) 則 A 3 5 和 A 5 3 的第一個(gè)字節(jié)的地址分別是 B 和 C 若按列存儲(chǔ) 則 A 7 1 和 A 2 4 的第一個(gè)字節(jié)的地址分別是 D 和 E 供選擇的答案 A E 28 44 76 92 108 116 132 176 184 188 答案 ABCDE 8 3 5 1 6 7 94 程 P12 有一個(gè)二維數(shù)組 A 行下標(biāo)的范圍是 1 到 6 列下標(biāo)的范圍是 0 到 7 每個(gè)數(shù)組元素用相鄰的 6 個(gè)字節(jié)存儲(chǔ) 存儲(chǔ)器按字節(jié)編址 那么 這個(gè)數(shù)組的體積是 A 個(gè)字節(jié) 假設(shè)存儲(chǔ)數(shù)組元素 A 1 0 的第一個(gè)字節(jié)的地址是 0 則存儲(chǔ) 數(shù)組 A 的最后一個(gè)元素的第一個(gè)字節(jié)的地址是 B 若按行存儲(chǔ) 則 A 2 4 的第一個(gè)字節(jié)的地址是 C 若按列存儲(chǔ) 解 注意 B 的下標(biāo)要求從 1 開(kāi)始 先用第一個(gè)元素去套用 可能有 B 和 C 再用第二個(gè)元素去套用 B 和 C B 2 而 C 3 不符 所以選 B nnnn aaa aa a A 2 1 2 21 2 1 1 11 則 A 5 7 的第一個(gè)字節(jié)的地址是 D 供選擇的答案 A D 12 66 72 96 114 120 156 234 276 282 11 283 12 288 答案 ABCD 12 10 3 9 三 簡(jiǎn)答題 每小題 5 分 共 15 分 1 其他教材 已知二維數(shù)組 Am m 采用按行優(yōu)先順序存放 每個(gè)元素占 K 個(gè)存儲(chǔ)單元 并且第一個(gè)元素的存儲(chǔ)地址為 Loc a11 請(qǐng)寫(xiě)出求 Loc aij 的計(jì)算公式 如果采用列優(yōu)先順序存放呢 解 公式教材已給出 此處雖是方陣 但行列公式仍不相同 按行存儲(chǔ)的元素地址公式是 Loc aij Loc a11 i 1 m j 1 K 按列存儲(chǔ)的元素地址公式是 Loc aij Loc a11 j 1 m i 1 K 2 全國(guó)專(zhuān)升本資格考試 遞歸算法比非遞歸算法花費(fèi)更多的時(shí)間 對(duì)嗎 為什么 答 不一定 時(shí)間復(fù)雜度與樣本個(gè)數(shù) n 有關(guān) 是指最深層的執(zhí)行語(yǔ)句耗費(fèi)時(shí)間 而遞歸算法與非遞歸算法在最深層的語(yǔ)句執(zhí) 行上是沒(méi)有區(qū)別的 循環(huán)的次數(shù)也沒(méi)有太大差異 僅僅是確定循環(huán)是否繼續(xù)的方式不同 遞歸用棧隱含循環(huán)次數(shù) 非遞歸用 循環(huán)變量來(lái)顯示循環(huán)次數(shù)而已 四 計(jì)算題 每題 5 分 共 20 分 1 設(shè) s I AM A STUDENT t GOOD q WORKER 求 Replace s STUDENT q 和 Concat SubString s 6 2 Concat t SubString s 7 8 解 Replace s STUDENT q I AM A WORKER 因?yàn)?SubString s 6 2 A SubString s 7 8 STUDENT Concat t SubString s 7 8 GOOD STUDENT 所以 Concat SubString s 6 2 Concat t SubString s 7 8 A GOOD STUDENT 2 P60 4 18 用三元組表表示下列稀疏矩陣 20000000 00000005 00000000 00060000 00000000 03000800 00000000 00000000 1 000003 000000 000500 000000 000009 200000 2 解 參見(jiàn)填空題 4 三元素組表中的每個(gè)結(jié)點(diǎn)對(duì)應(yīng)于稀疏矩陣的一個(gè)非零元素 它包含有三個(gè)數(shù)據(jù)項(xiàng) 分別表示該元素的 行 下標(biāo) 列下標(biāo) 和 元素值 所以 1 可列表為 2 可列表為 8 8 5 3 2 3 3 6 8 5 4 6 7 8 5 8 1 2 3 P60 4 19 下列各三元組表分別表示一個(gè)稀疏矩陣 試寫(xiě)出它們的稀疏矩陣 1616 635 444 313 1212 221 646 1 734 653 823 942 111 554 2 6 6 4 1 6 2 2 5 9 4 3 5 6 5 3 12 解 1 為 6 4 矩陣 非零元素有 6 個(gè) 2 為 4 5 矩陣 非零元素有 5 個(gè) 五 算法設(shè)計(jì)題 每題 10 分 共 30 分 1 嚴(yán)題集 4 12 編寫(xiě)一個(gè)實(shí)現(xiàn)串的置換操作 Replace 將串 S 中所有子串 T 替換為 V 并返回置換次數(shù) for n 0 i 1 iA 6 A 6 A 12 A 12 A 3 A 3 A 9 A 9 A 0 已 順便 移動(dòng)了 A 6 A 12 第二條鏈 A 1 A 7 A 7 A 13 A 13 A 4 A 4 A 10 A 10 A 1 第三條鏈 A 2 A 8 A 8 A 14 A 14 A 5 A 5 A 11 A 11 A 2 恰好使所有元素都右移一次 雖然未經(jīng)數(shù)學(xué)證明 但作者相信上述規(guī)律應(yīng)該是正確的 程序如下 void RSh int A n int k 把數(shù)組 A 的元素循環(huán)右移 k 位 只用一個(gè)輔助存儲(chǔ)空間 for i 1 i k i if n i 0 求 n 和 k 的最大公約數(shù) p for i 0 i0 個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為 log2 n log2 n log2 n 1 log2 n 1 注 1 x 表示不小于 x 的最小整數(shù) x 表示不大于 x 的最大整數(shù) 它們與 含義不同 注 2 選 A 是錯(cuò)誤的 例如當(dāng) n 為 2 的整數(shù)冪時(shí)就會(huì)少算一層 似乎 log2 n 1 是對(duì)的 A 4 把一棵樹(shù)轉(zhuǎn)換為二叉樹(shù)后 這棵二叉樹(shù)的形態(tài)是 唯一的 有多種 有多種 但根結(jié)點(diǎn)都沒(méi)有左孩子 有多種 但根結(jié)點(diǎn)都沒(méi)有右孩子 5 94 程 P11 從供選擇的答案中 選出應(yīng)填入下面敘述 內(nèi)的最確切的解答 把相應(yīng)編號(hào)寫(xiě)在答卷的對(duì)應(yīng)欄內(nèi) 樹(shù)是結(jié)點(diǎn)的有限集合 它 A 根結(jié)點(diǎn) 記為 T 其余的結(jié)點(diǎn)分成為 m m 0 個(gè) B 的集合 T1 T2 Tm 每個(gè)集合又都是樹(shù) 此時(shí)結(jié)點(diǎn) T 稱(chēng)為 Ti的父結(jié)點(diǎn) Ti稱(chēng)為 T 的子結(jié)點(diǎn) 1 i m 一個(gè)結(jié)點(diǎn)的 子結(jié)點(diǎn)個(gè)數(shù)為該結(jié)點(diǎn)的 C 供選擇的答案 A 有 0 個(gè)或 1 個(gè) 有 0 個(gè)或多個(gè) 有且只有 1 個(gè) 有 1 個(gè)或 1 個(gè)以上 B 互不相交 允許相交 允許葉結(jié)點(diǎn)相交 允許樹(shù)枝結(jié)點(diǎn)相交 C 權(quán) 維數(shù) 次數(shù) 或度 序 答案 ABC 1 1 3 6 95 程 P13 從供選擇的答案中 選出應(yīng)填入下面敘述 內(nèi)的最確切的解答 把相應(yīng)編號(hào)寫(xiě)在答卷的對(duì)應(yīng)欄內(nèi) 二叉樹(shù) A 在完全的二叉樹(shù)中 若一個(gè)結(jié)點(diǎn)沒(méi)有 B 則它必定是葉結(jié)點(diǎn) 每棵樹(shù)都能惟一地轉(zhuǎn)換成與它對(duì)應(yīng)的 二叉樹(shù) 由樹(shù)轉(zhuǎn)換成的二叉樹(shù)里 一個(gè)結(jié)點(diǎn) N 的左子女是 N 在原樹(shù)里對(duì)應(yīng)結(jié)點(diǎn)的 C 而 N 的右子女是它在原樹(shù)里對(duì)應(yīng) 結(jié)點(diǎn)的 D 供選擇的答案 A 是特殊的樹(shù) 不是樹(shù)的特殊形式 是兩棵樹(shù)的總稱(chēng) 有是只有二個(gè)根結(jié)點(diǎn)的樹(shù)形結(jié)構(gòu) B 左子結(jié)點(diǎn) 右子結(jié)點(diǎn) 左子結(jié)點(diǎn)或者沒(méi)有右子結(jié)點(diǎn) 兄弟 C D 最左子結(jié)點(diǎn) 最右子結(jié)點(diǎn) 最鄰近的右兄弟 最鄰近的左兄弟 最左的兄弟 最右的兄弟 答案 A B C D 答案 ABCDE 2 1 1 3 四 簡(jiǎn)答題 每小題 4 分 共 20 分 1 嚴(yán)題集 6 2 一棵度為 2 的樹(shù)與一棵二叉樹(shù)有何區(qū)別 答 度為 2 的樹(shù)從形式上看與二叉樹(shù)很相似 但它的子樹(shù)是無(wú)序的 而二叉樹(shù) 是有序的 即 在一般樹(shù)中若某結(jié)點(diǎn)只有一個(gè)孩子 就無(wú)需區(qū)分其左右次序 而在二叉樹(shù)中即使是一個(gè)孩子也有左右之分 2 01 年計(jì)算機(jī)研題 設(shè)如下圖所示的二叉樹(shù) B 的存儲(chǔ)結(jié)構(gòu)為二叉鏈表 root 為根指針 結(jié)點(diǎn)結(jié)構(gòu)為 lchild data rchild 其中 lchild rchild 分別為指向左 右孩子的指針 data 為字符型 root 為根指針 試回答下列問(wèn)題 1 對(duì)下列二叉樹(shù) B 執(zhí)行下列算法 traversal root 試指出其輸出結(jié)果 2 假定二叉樹(shù) B 共有 n 個(gè)結(jié)點(diǎn) 試分析算法 traversal root 的時(shí)間復(fù)雜度 共 8 分 二叉樹(shù) B A B D C F G E C 的結(jié)點(diǎn)類(lèi)型定義如下 struct node char data struct node lchild rchild C 算法如下 void traversal struct node root if root printf c root data traversal root lchild printf c root data traversal root rchild 15 解 這是 先根再左再根再右 比前序遍歷多打印各結(jié)點(diǎn)一次 輸出結(jié)果為 A B C C E E B A D F F D G G 特點(diǎn) 每個(gè)結(jié)點(diǎn)肯定都會(huì)被打印兩次 但出現(xiàn)的順序不同 其規(guī)律是 凡是有左子樹(shù)的結(jié)點(diǎn) 必間隔左子樹(shù)的全部結(jié)點(diǎn) 后再重復(fù)出現(xiàn) 如 A B D 等結(jié)點(diǎn) 反之馬上就會(huì)重復(fù)出現(xiàn) 如 C E F G 等結(jié)點(diǎn) 時(shí)間復(fù)雜度以訪問(wèn)結(jié)點(diǎn)的次數(shù)為主 精確值為 2 n 時(shí)間漸近度為 O n 3 01 年計(jì)算機(jī)研題 嚴(yán)題集 6 27 給定二叉樹(shù)的兩種遍歷序列 分別是 前序遍歷序列 D A C E B H F G I 中序遍歷序列 D C B E H A G I F 試畫(huà)出二叉樹(shù) B 并簡(jiǎn)述由任意二叉樹(shù) B 的前序遍歷序列和中序遍歷序列求二叉樹(shù) B 的思想方法 解 方法是 由前序先確定 root 由中序可確定 root 的左 右子樹(shù) 然后由其左子樹(shù)的元素集合和右子樹(shù)的集合對(duì)應(yīng)前序遍 歷序列中的元素集合 可繼續(xù)確定 root 的左右孩子 將他們分別作為新的 root 不斷遞歸 則所有元素都將被唯一確定 問(wèn) 題得解 D A C F E G B H I 4 計(jì)算機(jī)研 2000 給定如圖所示二叉樹(shù) T 請(qǐng)畫(huà)出與其對(duì)應(yīng)的中序線索二叉樹(shù) 解 要遵循中序遍歷的軌跡來(lái)畫(huà)出每個(gè)前驅(qū)和后繼 中序遍歷序列 55 40 25 60 28 08 33 54 28 25 33 40 60 08 54 55 五 閱讀分析題 每題 5 分 共 20 分 1 P60 4 26 試寫(xiě)出如圖所示的二叉樹(shù)分別按先序 中序 后序遍歷時(shí)得到的結(jié)點(diǎn)序列 答 DLR A B D F J G K C E H I L M LDR B F J D G K A C H E L I M LRD J F K G D B H L M I E C A 2 P60 4 27 把如圖所示的樹(shù)轉(zhuǎn)化成二叉樹(shù) 答 注意全部兄弟之間都要連線 包括度為 2 的兄弟 并注意原有連線結(jié)點(diǎn)一律歸入左子樹(shù) 新添連線結(jié)點(diǎn)一律歸入右子 樹(shù) A B E C K F H D L G I M J 28 25 33 40 60 08 54 55 2 2 4 5 6 3 054 N N N N 16 3 嚴(yán)題集 6 17 閱讀下列算法 若有錯(cuò) 改正之 4 嚴(yán)題集 6 21 畫(huà)出和下列二叉樹(shù)相應(yīng)的森林 答 注意根右邊的子樹(shù)肯定是森林 而孩子結(jié)點(diǎn)的右子樹(shù)均為兄弟 六 算法設(shè)計(jì)題 前 5 題中任選 2 題 第 6 題必做 每題 8 分 共 24 分 1 嚴(yán)題集 6 42 編寫(xiě)遞歸算法 計(jì)算二叉樹(shù)中葉子結(jié)點(diǎn)的數(shù)目 解 思路 輸出葉子結(jié)點(diǎn)比較簡(jiǎn)單 用任何一種遍歷遞歸算法 凡是左右指針均空者 則為葉子 將其打印出來(lái) 法一 核心部分為 DLR liuyu root 中序遍歷 遞歸函數(shù) if root NULL if root lchild NULL printf d n root data DLR root lchild DLR root rchild return 0 法二 int LeafCount BiTree Bitree T 求二叉樹(shù)中葉子結(jié)點(diǎn)的數(shù)目 if T return 0 空樹(shù)沒(méi)有葉子 else if T lchild 葉子結(jié)點(diǎn) else return Leaf Count T lchild Leaf Count T rchild 左子樹(shù)的葉子數(shù)加 上右子樹(shù)的葉子數(shù) LeafCount BiTree 注 上機(jī)時(shí)要先建樹(shù) 例如實(shí)驗(yàn)二的方案一 打印葉子結(jié)點(diǎn)值 并求總數(shù) 思路 先建樹(shù) 再?gòu)谋闅v過(guò)程中打印結(jié)點(diǎn)值并統(tǒng)計(jì) 步驟 1 鍵盤(pán)輸入序列 12 8 17 11 16 2 13 9 21 4 構(gòu)成一棵二叉排序樹(shù) 葉子結(jié)點(diǎn)值應(yīng)該是 4 9 13 21 總數(shù) 應(yīng)該是 4 12 7 17 2 11 16 21 4 9 13 BiTree InSucc BiTree q 已知 q 是指向中序線索二叉樹(shù)上某個(gè)結(jié)點(diǎn)的指針 本函數(shù)返回指向 q 的后繼的指針 r q rchild 應(yīng)改為 r q if r rtag while r rtag r r rchild 應(yīng)改為 while r Ltag r r Lchild return r 應(yīng)改為 return r rchild ISucc 答 這是找結(jié)點(diǎn)后繼的程序 共有 3 處錯(cuò)誤 注 當(dāng) rtag 1 時(shí)說(shuō)明內(nèi)裝后繼指針 可 直接返回 第一句無(wú)錯(cuò) 當(dāng) rtag 0 時(shí)說(shuō)明內(nèi)裝右孩子指針 但孩 子未必是后繼 需要計(jì)算 中序遍歷應(yīng)當(dāng) 先左再根再右 所以應(yīng)當(dāng)找左子樹(shù)直到葉 子處 r rr r lchild lchild 直到直到 LTag 1LTag 1 應(yīng)改為 while r Ltag r r Lchild 17 編程 生成二叉樹(shù)排序樹(shù)之后 再中序遍歷排序查找結(jié)點(diǎn)的完整程序如下 說(shuō)明部分為 include include typedef struct liuyu int data struct liuyu lchild rchild test liuyu root int sum 0 int m sizeof test void insert data int x 如何生成二叉排序樹(shù) 參見(jiàn)教材 P43C 程序 liuyu p q s s test malloc m s data x s lchild NULL s rchild NULL if root root s return p root while p 如何接入二叉排序樹(shù)的適當(dāng)位置 q p if p data x printf data already exist n return else if xdata p p lchild else p p rchild if xdata q lchild s else q rchild s DLR liuyu root 中序遍歷 遞歸函數(shù) if root NULL if root lchild NULL printf d n root data DLR root lchild DLR root rchild return 0 main 先生成二叉排序樹(shù) 再調(diào)用中序遍歷遞歸函數(shù)進(jìn)行排序輸出 int i x i 1 root NULL 千萬(wàn)別忘了賦初值給 root do printf please input data d i i scanf d 從鍵盤(pán)采集數(shù)據(jù) 以 9999 表示輸入結(jié)束 if x 9999 DLR root printf nNo
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶(hù)所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶(hù)上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶(hù)上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶(hù)因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 山里踏雪活動(dòng)方案
- 展廳寵物活動(dòng)方案
- 小紅帽公司活動(dòng)策劃方案
- 山西省基礎(chǔ)教育活動(dòng)方案
- 布丁酒店活動(dòng)方案
- 工作迎新活動(dòng)方案
- 小學(xué)生居家游戲活動(dòng)方案
- 小柴米充值活動(dòng)方案
- 盡快落實(shí)活動(dòng)方案
- 師生環(huán)保進(jìn)社區(qū)活動(dòng)方案
- 天臺(tái)保安考試題及答案
- 招聘渠道ROI評(píng)估模型-洞察及研究
- 2025春季學(xué)期國(guó)開(kāi)電大本科《人文英語(yǔ)4》一平臺(tái)機(jī)考真題及答案(第六套)
- 第七單元1認(rèn)識(shí)小數(shù)(課件)-三年級(jí)數(shù)學(xué)下冊(cè)(人教版)
- 2025年河北省中考麒麟卷生物(二)及答案
- 2024年民族出版社招聘事業(yè)編制專(zhuān)業(yè)技術(shù)人員真題
- 2025年食品安全管理員考試試題及答案
- 2025-2030骨科植入器材產(chǎn)業(yè)市場(chǎng)深度分析及發(fā)展趨勢(shì)與投資戰(zhàn)略研究報(bào)告
- T/SHPTA 071.1-2023高壓電纜附件用橡膠材料第1部分:絕緣橡膠材料
- 湖北省浠水縣聯(lián)考2025年七下數(shù)學(xué)期末質(zhì)量檢測(cè)試題含解析
- 生產(chǎn)基層管理培訓(xùn)課程
評(píng)論
0/150
提交評(píng)論