數(shù)據(jù)結(jié)構(gòu)各章自測題答案.pdf

1 第一章概論 自測題答案 一 填空題 1 數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機(jī)的 操作對象 以及它們之間的 關(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ù)的 存儲結(jié)構(gòu) 和數(shù)據(jù)的 運(yùn)算 這三個方面的內(nèi)容 4 數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類 它們分別是 線性結(jié)構(gòu) 和 非線性結(jié)構(gòu) 5 線性結(jié)構(gòu)中元素之間存在一對一關(guān)系 樹形結(jié)構(gòu)中元素之間存在一對多關(guān)系 圖形結(jié)構(gòu)中元素之間存在多對多關(guān)系 6 在線性結(jié)構(gòu)中 第一個結(jié)點(diǎn) 沒有 前驅(qū)結(jié)點(diǎn) 其余每個結(jié)點(diǎn)有且只有 1 個前驅(qū)結(jié)點(diǎn) 最后一個結(jié)點(diǎn) 沒有 后續(xù)結(jié) 點(diǎn) 其余每個結(jié)點(diǎn)有且只有 1 個后續(xù)結(jié)點(diǎn) 7 在樹形結(jié)構(gòu)中 樹根結(jié)點(diǎn)沒有 前驅(qū) 結(jié)點(diǎn) 其余每個結(jié)點(diǎn)有且只有 1 個前驅(qū)結(jié)點(diǎn) 葉子結(jié)點(diǎn)沒有 后續(xù) 結(jié)點(diǎn) 其余每個結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)數(shù)可以任意多個 8 在圖形結(jié)構(gòu)中 每個結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)數(shù)和后續(xù)結(jié)點(diǎn)數(shù)可以 任意多個 9 數(shù)據(jù)的存儲結(jié)構(gòu)可用四種基本的存儲方法表示 它們分別是順序 鏈?zhǔn)?索引 和 散列 10 數(shù)據(jù)的運(yùn)算最常用的有 5 種 它們分別是插入 刪除 修改 查找 排序 11 一個算法的效率可分為 時間 效率和 空間 效率 二 單項(xiàng)選擇題 B 1 非線性結(jié)構(gòu)是數(shù)據(jù)元素之間存在一種 A 一對多關(guān)系 B 多對多關(guān)系 C 多對一關(guān)系 D 一對一關(guān)系 C 2 數(shù)據(jù)結(jié)構(gòu)中 與所使用的計算機(jī)無關(guān)的是數(shù)據(jù)的 結(jié)構(gòu) A 存儲 B 物理 C 邏輯 D 物理和存儲 C 3 算法分析的目的是 A 找出數(shù)據(jù)結(jié)構(gòu)的合理性 B 研究算法中的輸入和輸出的關(guān)系 C 分析算法的效率以求改進(jìn) D 分析算法的易懂性和文檔性 A 4 算法分析的兩個主要方面是 A 空間復(fù)雜性和時間復(fù)雜性 B 正確性和簡明性 C 可讀性和文檔性 D 數(shù)據(jù)復(fù)雜性和程序復(fù)雜性 C 5 計算機(jī)算法指的是 A 計算方法 B 排序方法 C 解決問題的有限運(yùn)算序列 D 調(diào)度方法 B 6 計算機(jī)算法必須具備輸入 輸出和 等 5 個特性 A 可行性 可移植性和可擴(kuò)充性 B 可行性 確定性和有窮性 C 確定性 有窮性和穩(wěn)定性 D 易讀性 穩(wěn)定性和安全性 三 簡答題 2 嚴(yán)題集 1 2 數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類型兩個概念之間有區(qū)別嗎 答 簡單地說 數(shù)據(jù)結(jié)構(gòu)定義了一組按某些關(guān)系結(jié)合在一起的數(shù)組元素 數(shù)據(jù)類型不僅定義了一組帶結(jié)構(gòu)的數(shù)據(jù)元素 而且 還在其上定義了一組操作 3 簡述線性結(jié)構(gòu)與非線性結(jié)構(gòu)的不同點(diǎn) 答 線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是答 線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是 一對一的 非線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是多對多的 一對一的 非線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是多對多的 四 嚴(yán)題集 1 8 分析下面各程序段的時間復(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í)行時間為 O n2 4 i 1 while i n i i 3 答 O log3n 2 五 設(shè)有數(shù)據(jù)邏輯結(jié)構(gòu) S D R 試按各小題所給條件畫出這些邏輯結(jié)構(gòu)的圖示 并確定相對于關(guān)系 R 哪些結(jié)點(diǎn)是開始 結(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 無直接前驅(qū) 是首結(jié)點(diǎn) d4 無直接后繼是尾結(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 答 此圖為樹形結(jié)構(gòu) d1 無直接前驅(qū) 是根結(jié)點(diǎn) d2 d5 d7 d9 無直接后繼是葉子結(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 無直接前驅(qū) 是開始結(jié)點(diǎn) d6 d7 無直接后繼是終端結(jié)點(diǎn) 2 3 第 2 章 自測卷答案 一 填空 1 嚴(yán)題集 2 2 在順序表中插入或刪除一個元素 需要平均移動 表中一半元素 具體移動的元素個數(shù)與 表長和該元素 在表中的位置 有關(guān) 2 線性表中結(jié)點(diǎn)的集合是 有限 的 結(jié)點(diǎn)間的關(guān)系是 一對一 的 3 向一個長度為 n 的向量的第 i 個元素 1 i n 1 之前插入一個元素時 需向后移動 n i 1 個元素 4 向一個長度為 n 的向量中刪除第 i 個元素 1 i n 時 需向前移動 n i 個元素 5 在順序表中訪問任意一結(jié)點(diǎn)的時間復(fù)雜度均為 O 1 因此 順序表也稱為 隨機(jī)存取 的數(shù)據(jù)結(jié)構(gòu) 6 嚴(yán)題集 2 2 順序表中邏輯上相鄰的元素的物理位置 必定相鄰 單鏈表中邏輯上相鄰的元素的物理位置 不一定 相 鄰 7 嚴(yán)題集 2 2 在單鏈表中 除了首元結(jié)點(diǎn)外 任一結(jié)點(diǎn)的存儲位置由 其直接前驅(qū)結(jié)點(diǎn)的鏈域的值 指示 8 在 n 個結(jié)點(diǎn)的單鏈表中要刪除已知結(jié)點(diǎn) p 需找到它的前驅(qū)結(jié)點(diǎn)的地址 其時間復(fù)雜度為 O n 二 判斷正誤 在正確的說法后面打勾 反之打叉 1 鏈表的每個結(jié)點(diǎn)中都恰好包含一個指針 答 錯誤 鏈表中的結(jié)點(diǎn)可含多個指針域 分別存放多個指針 例如 雙向鏈表中的結(jié)點(diǎn)可以含有兩個指針 域 分別存放指向其直接前趨和直接后繼結(jié)點(diǎn)的指針 2 鏈表的物理存儲結(jié)構(gòu)具有同鏈表一樣的順序 錯 鏈表的存儲結(jié)構(gòu)特點(diǎn)是無序 而鏈表的示意圖有序 3 鏈表的刪除算法很簡單 因?yàn)楫?dāng)刪除鏈中某個結(jié)點(diǎn)后 計算機(jī)會自動地將后續(xù)的各個單元向前移動 錯 鏈表 的結(jié)點(diǎn)不會移動 只是指針內(nèi)容改變 4 線性表的每個結(jié)點(diǎn)只能是一個簡單類型 而鏈表的每個結(jié)點(diǎn)可以是一個復(fù)雜類型 錯 混淆了邏輯結(jié)構(gòu)與物理結(jié)構(gòu) 鏈表也是線性表 且即使是順序表 也能存放記錄型數(shù)據(jù) 5 順序表結(jié)構(gòu)適宜于進(jìn)行順序存取 而鏈表適宜于進(jìn)行隨機(jī)存取 錯 正好說反了 順序表才適合隨機(jī)存取 鏈表恰恰適于 順藤摸瓜 6 順序存儲方式的優(yōu)點(diǎn)是存儲密度大 且插入 刪除運(yùn)算效率高 錯 前一半正確 但后一半說法錯誤 那是鏈?zhǔn)酱鎯Φ膬?yōu)點(diǎn) 順序存儲方式插入 刪除運(yùn)算效率較低 在表長為 n 的順序表中 插入和刪除一個數(shù)據(jù)元素 平均需移動表長一半個數(shù)的數(shù)據(jù)元素 7 線性表在物理存儲空間中也一定是連續(xù)的 錯 線性表有兩種存儲方式 順序存儲和鏈?zhǔn)酱鎯?后者不要求連續(xù)存放 8 線性表在順序存儲時 邏輯上相鄰的元素未必在存儲的物理位置次序上相鄰 錯誤 線性表有兩種存儲方式 在順序存儲時 邏輯上相鄰的元素在存儲的物理位置次序上也相鄰 9 順序存儲方式只能用于存儲線性結(jié)構(gòu) 錯誤 順序存儲方式不僅能用于存儲線性結(jié)構(gòu) 還可以用來存放非線性結(jié)構(gòu) 例如完全二叉樹是屬于非線性結(jié)構(gòu) 但 其最佳存儲方式是順序存儲方式 后一節(jié)介紹 3 10 線性表的邏輯順序與存儲順序總是一致的 錯 理由同 7 鏈?zhǔn)酱鎯蜔o需一致 三 單項(xiàng)選擇題 C 1 數(shù)據(jù)在計算機(jī)存儲器內(nèi)表示時 物理地址與邏輯地址相同并且是連續(xù)的 稱之為 A 存儲結(jié)構(gòu) B 邏輯結(jié)構(gòu) C 順序存儲結(jié)構(gòu) D 鏈?zhǔn)酱鎯Y(jié)構(gòu) B 2 一個向量第一個元素的存儲地址是 100 每個元素的長度為 2 則第 5 個元素的地址是 A 110 B 108 C 100 D 120 A 3 在 n 個結(jié)點(diǎn)的順序表中 算法的時間復(fù)雜度是 O 1 的操作是 A 訪問第 i 個結(jié)點(diǎn) 1 i n 和求第 i 個結(jié)點(diǎn)的直接前驅(qū) 2 i n B 在第 i 個結(jié)點(diǎn)后插入一個新結(jié)點(diǎn) 1 i n C 刪除第 i 個結(jié)點(diǎn) 1 i n D 將 n 個結(jié)點(diǎn)從小到大排序 B 4 向一個有 127 個元素的順序表中插入一個新元素并保持原來順序不變 平均要移動 個元素 A 8 B 63 5 C 63 D 7 A 5 鏈接存儲的存儲結(jié)構(gòu)所占存儲空間 A 分兩部分 一部分存放結(jié)點(diǎn)值 另一部分存放表示結(jié)點(diǎn)間關(guān)系的指針 B 只有一部分 存放結(jié)點(diǎn)值 C 只有一部分 存儲表示結(jié)點(diǎn)間關(guān)系的指針 D 分兩部分 一部分存放結(jié)點(diǎn)值 另一部分存放結(jié)點(diǎn)所占單元數(shù) B 6 鏈表是一種采用 存儲結(jié)構(gòu)存儲的線性表 A 順序 B 鏈?zhǔn)?C 星式 D 網(wǎng)狀 D 7 線性表若采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時 要求內(nèi)存中可用存儲單元的地址 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)值 需不斷對 進(jìn)行刪除插入 中含有大量的結(jié)點(diǎn) 中結(jié)點(diǎn)結(jié)構(gòu)復(fù)雜 C 9 單鏈表的存儲密度 大于 1 等于 1 小于 1 不能確定 B 10 設(shè) a1 a2 a3 為 3 個結(jié)點(diǎn) 整數(shù) P0 3 4 代表地址 則如下的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為 P0 3 4 P0 a1 3 a2 4 A3 0 循環(huán)鏈表 單鏈表 雙向循環(huán)鏈表 雙向鏈表 四 簡答題 1 嚴(yán)題集 2 3 試比較順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)的優(yōu)缺點(diǎn) 在什么情況下用順序表比鏈表好 答 順序存儲時 相鄰數(shù)據(jù)元素的存放地址也相鄰 邏輯與物理統(tǒng)一 要求內(nèi)存中可用存儲單元的地址必須是連續(xù)的 優(yōu)點(diǎn) 存儲密度大 1 存儲空間利用率高 缺點(diǎn) 插入或刪除元素時不方便 鏈?zhǔn)酱鎯r 相鄰數(shù)據(jù)元素可隨意存放 但所占存儲空間分兩部分 一部分存放結(jié)點(diǎn)值 另一部分存放表示結(jié)點(diǎn)間 關(guān)系的指針 優(yōu)點(diǎn) 插入或刪除元素時很方便 使用靈活 缺點(diǎn) 存儲密度小 top0 ST top 0 ST topm0 ST top m0 A 4 李春葆 判定一個隊列 QU 最多元素為 m0 為滿隊列的條件是 QU rear QU front m0 QU rear QU front 1 m0 QU front QU rear QU front QU rear 1 解 隊滿條件是元素個數(shù)為 m0 由于約定滿隊時隊首指針與隊尾指針相差 1 所以不必再減 1 了 應(yīng)當(dāng)選 A 當(dāng)然 更正 確的答案應(yīng)該取模 即 QU front QU rear 1 m0 D 5 數(shù)組 用來表示一個循環(huán)隊列 為當(dāng)前隊列頭元素的前一位置 為隊尾元素的位置 假定隊列 中元素的個數(shù)小于 計算隊列中元素的公式為 r f n f r n n r f n r f n 6 98 初程 P71 從供選擇的答案中 選出應(yīng)填入下面敘述 內(nèi)的最確切的解答 把相應(yīng)編號寫在答卷的對應(yīng)欄 5 內(nèi) 設(shè)有 4 個數(shù)據(jù)元素 a1 a2 a3 和 a4 對他們分別進(jìn)行棧操作或隊操作 在進(jìn)?；蜻M(jìn)隊操作時 按 a1 a2 a3 a4 次 序每次進(jìn)入一個元素 假設(shè)?；蜿牭某跏紶顟B(tài)都是空 現(xiàn)要進(jìn)行的棧操作是進(jìn)棧兩次 出棧一次 再進(jìn)棧兩次 出棧一次 這時 第一次出棧得到的元素是 A 第二次 出棧得到的元素是 B 是 類似地 考慮對這四個數(shù)據(jù)元素進(jìn)行的隊操作是進(jìn)隊兩次 出隊一次 再進(jìn)隊兩次 出隊 一次 這時 第一次出隊得到的元素是 C 第二次出隊得到的元素是 D 經(jīng)操作后 最后在棧中或隊中的元 素還有 E 個 供選擇的答案 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)編號寫在答卷的對應(yīng)欄 內(nèi) 棧是一種線性表 它的特點(diǎn)是 A 設(shè)用一維數(shù)組 A 1 n 來表示一個棧 A n 為棧底 用整型變量 T 指示當(dāng)前棧 頂位置 A T 為棧頂元素 往棧中推入 PUSH 一個新元素時 變量 T 的值 B 從棧中彈出 POP 一個元素時 變 量 T 的值 C 設(shè)棧空時 有輸入序列 a b c 經(jīng)過 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 注意 向地址的高端生長 稱為向上生成堆棧 向地址低端生長叫向下生成堆棧 本題中底部為 n 向地址的低端遞減生成 稱為向下生成堆棧 8 91 初程 P77 從供選擇的答案中 選出應(yīng)填入下面敘述 內(nèi)的最確切的解答 把相應(yīng)編號寫在答卷的對應(yīng)欄 內(nèi) 在做進(jìn)棧運(yùn)算時 應(yīng)先判別棧是否 A 在做退棧運(yùn)算時 應(yīng)先判別棧是否 B 當(dāng)棧中元素為 n 個 做進(jìn)棧運(yùn) 算時發(fā)生上溢 則說明該棧的最大容量為 C 為了增加內(nèi)存空間的利用率和減少溢出的可能性 由兩個棧共享一片連續(xù)的內(nèi)存空間時 應(yīng)將兩棧的 D 分別設(shè)在這片 內(nèi)存空間的兩端 這樣 只有當(dāng) E 時 才產(chǎn)生上溢 供選擇的答案 A B 空 滿 上溢 下溢 C n 1 n n 1 n 2 D 長度 深度 棧頂 棧底 E 兩個棧的棧頂同時到達(dá)?？臻g的中心點(diǎn) 其中一個棧的棧頂?shù)竭_(dá)?？臻g的中心點(diǎn) 兩個棧的棧頂在達(dá)棧空間的某一位置相遇 兩個棧均不空 且一個棧的棧頂?shù)竭_(dá)另一個棧的棧底 答案 ABCDE 2 1 2 4 3 四 簡答題 每小題 4 分 共 20 分 1 嚴(yán)題集 3 2 和 3 11 說明線性表 棧與隊的異同點(diǎn) 劉答 相同點(diǎn) 都是線性結(jié)構(gòu) 都是邏輯結(jié)構(gòu)的概念 都可以用順序存儲或鏈表存儲 棧和隊列是兩種特殊的線性表 即受 限的線性表 只是對插入 刪除運(yùn)算加以限制 不同點(diǎn) 運(yùn)算規(guī)則不同 線性表為隨機(jī)存取 而棧是只允許在一端進(jìn)行插入 刪除運(yùn)算 因而是后進(jìn)先出表 LIFO 隊列 是只允許在一端進(jìn)行插入 另一端進(jìn)行刪除運(yùn)算 因而是先進(jìn)先出表 FIFO 用途不同 堆棧用于子程調(diào)用和保護(hù)現(xiàn)場 隊列用于多道作業(yè)處理 指令寄存及其他運(yùn)算等等 2 統(tǒng)考書 P60 4 11 難于嚴(yán)題集 3 1 設(shè)有編號為 1 2 3 4 的四輛列車 順序進(jìn)入一個棧式結(jié)構(gòu)的車站 具體寫出 這四輛列車開出車站的所有可能的順序 劉答 至少有 14 種 全進(jìn)之后再出情況 只有 1 種 4 3 2 1 進(jìn) 3 個之后再出的情況 有 3 種 3 4 2 1 3 2 4 1 3 2 1 4 進(jìn) 2 個之后再出的情況 有 5 種 2 4 3 1 2 3 4 1 2 1 3 4 2 1 4 3 2 3 1 4 進(jìn) 1 個之后再出的情況 有 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ī)存儲 可以實(shí)現(xiàn) 靠循環(huán)變量 j 從表尾開始打印輸出 堆棧是后進(jìn)先出 也可以實(shí)現(xiàn) 靠正序入棧 逆序出棧即可 隊列是先進(jìn)先出 不易實(shí)現(xiàn) 6 哪種方式最好 要具體情況具體分析 若正文在機(jī)內(nèi)已是順序存儲 則直接用線性表從后往前讀取即可 或?qū)⒍褩ｍ?開到數(shù)組末尾 然后直接用 POP 動作實(shí)現(xiàn) 但堆棧是先減后壓還是 若正文是單鏈表形式存儲 則等同于隊列 需開輔助空間 可以從鏈?zhǔn)组_始入棧 全部壓入后再依次輸出 4 統(tǒng)考書 P60 4 13 順序隊的 假溢出 是怎樣產(chǎn)生的 如何知道循環(huán)隊列是空還是滿 答 一般的一維數(shù)組隊列的尾指針已經(jīng)到了數(shù)組的上界 不能再有入隊操作 但其實(shí)數(shù)組中還有空位置 這就叫 假溢出 采用循環(huán)隊列是解決假溢出的途徑 另外 解決隊滿隊空的辦法有三 設(shè)置一個布爾變量以區(qū)別隊滿還是隊空 浪費(fèi)一個元素的空間 用于區(qū)別隊滿還是隊空 使用一個計數(shù)器記錄隊列中元素個數(shù) 即隊列長度 我們常采用法 即隊頭指針 隊尾指針中有一個指向?qū)嵲?而另一個指向空閑元素 判斷循環(huán)隊列隊空標(biāo)志是 f rear 隊滿標(biāo)志是 f r 1 N 5 統(tǒng)考書 P60 4 14 設(shè)循環(huán)隊列的容量為 40 序號從 0 到 39 現(xiàn)經(jīng)過一系列的入隊和出隊運(yùn)算后 有 front 11 rear 19 front 19 rear 11 問在這兩種情況下 循環(huán)隊列中各有元素多少個 答 用隊列長度計算公式 N r f N L 40 19 11 40 8 L 40 11 19 40 32 五 閱讀理解 每小題 5 分 共 20 分 至少要寫出思路 1 嚴(yán)題集 3 7 按照四則運(yùn)算加 減 乘 除和冪運(yùn)算 優(yōu)先關(guān)系的慣例 并仿照教材例 3 2 的格式 畫出對下 列算術(shù)表達(dá)式求值時操作數(shù)棧和運(yùn)算符棧的變化過程 A B C D E F 答 2 嚴(yán)題集 3 3 寫出下列程序段的輸出結(jié)果 棧的元素類型 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 寫出下列程序段的輸出結(jié)果 隊列中的元素類型 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 簡述以下算法的功能 棧和隊列的元素類型均為 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 答 該算法的功能是 利用堆棧做輔助 將隊列中的數(shù)據(jù)元素進(jìn)行逆置 六 算法設(shè)計 每小題 5 分 共 15 分 至少要寫出思路 1 李春葆及嚴(yán)題集 3 19 假設(shè)一個算術(shù)表達(dá)式中包含圓括弧 方括弧和花括弧三種類型的括弧 編寫一個判別表達(dá)式 中括弧是否正確配對的函數(shù) correct exp tag 其中 exp 為字符串類型的變量 可理解為每個字符占用一個數(shù)組元素 表示被判別的表達(dá)式 tag 為布爾型變量 答 用堆棧 st 進(jìn)行判定 將 或 入棧 當(dāng)遇到 或 時 檢查當(dāng)前棧頂元素是否是對應(yīng)的 或 若是則退棧 否則返回表示不配對 當(dāng)整個算術(shù)表達(dá)式檢查完畢時 若棧為空表示括號正確配對 否則不配對 編程后的整個函數(shù)如下 李書 P31 32 define m0 100 m0 為算術(shù)表達(dá)式中最多字符個數(shù) correct exp tag char exp m0 int tag char st m0 int top 0 i 1 tag 1 while i0 tag 0 若棧不空 則不配對 嚴(yán)題集對應(yīng)答案 8 3 19 Status AllBrackets Test char str 判別表達(dá)式中三種括號是否匹配 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)前棧頂括號匹配 for if StackEmpty s return ERROR return OK AllBrackets Test 2001 級通信 6 班張沐同學(xué)答案 已上機(jī)通過 include include void push char x void pop void correct enum Boolean 原來的定義是 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 并沒有被推入堆棧中 即 head data 的值在 Push 中顯示為 y 的值 但是出 Push 函數(shù) 馬上變成 Null else continue if head next NULL 原來的程序是 if head NULL tag TRUE tag TRUE else tag FALSE 總結(jié) 由于 head 為全局變量 所以不應(yīng)該將其再次作為函數(shù)的變量 因?yàn)?C 語言的函數(shù)變量是傳值機(jī)制 所以在函數(shù)中 對參數(shù)進(jìn)行了拷貝復(fù)本 所以不能改變 head 的數(shù)值 2 統(tǒng)考書 P60 4 15 假設(shè)一個數(shù)組 squ m 存放循環(huán)隊列的元素 若要使這 m 個分量都得到利用 則需另一個標(biāo)志 tag 以 tag 為 0 或 1 來區(qū)分尾指針和頭指針值相同時隊列的狀態(tài)是 空 還是 滿 試編寫相應(yīng)的入隊和出隊的算法 解 這就是解決隊滿隊空的三種辦法之 設(shè)置一個布爾變量以區(qū)別隊滿還是隊空 其他兩種見簡答題 思路 一開始隊空 設(shè) tag 0 若從 rear 一端加到與 front 指針相同時 表示入隊已滿 則令 tag 1 若從 front 一端加到與 rear 指針相同時 則令 tag 0 表示出隊已空 3 嚴(yán)題集 3 31 試寫一個算法判別讀入的一個以 為結(jié)束符的字符序列是否是 回文 答 編程如下 int Palindrome Test 判別輸入的字符串是否回文序列 是則返回 1 否則返回 0 InitStack S InitQueue Q while c getchar Push S c EnQueue Q c 同時使用棧和隊列兩種結(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 不包含任何字符 長度為 0 的串 稱為空串 由一個或多個空格 僅由空格符 組成的串 稱為空白串 對應(yīng)嚴(yán)題集 4 1 簡答題 簡述空串和空格串的區(qū)別 2 設(shè) S A document Mary doc 則 strlen s 20 的字符定位的位置為 3 4 子串的定位運(yùn)算稱為串的模式匹配 被匹配的主串 稱為目標(biāo)串 子串 稱為模式 5 設(shè)目標(biāo) T abccdcdccbaa 模式 P cdcc 則第 6 次匹配成功 10 6 若 n 為主串長 m 為子串長 則串的古典 樸素 匹配算法最壞的情況下需要比較字符的總次數(shù)為 n m 1 m 7 假設(shè)有二維數(shù)組 A6 8 每個元素用相鄰的 6 個字節(jié)存儲 存儲器按字節(jié)編址 已知 A 的起始存儲位置 基地址 為 1000 則數(shù)組 A 的體積 存儲量 為 288 B 末尾元素 A57的第一個字節(jié)地址為 1282 若按行存儲時 元素 A14的 第一個字節(jié)地址為 8 4 6 1000 1072 若按列存儲時 元素 A47的第一個字節(jié)地址為 6 7 4 6 1000 1276 注 數(shù)組是從 0 行 0 列還是從 1 行 1 列計算起呢 由末單元為 A57可知 是從 0 行 0 列開始 8 00 年計算機(jī)系考研題 設(shè)數(shù)組 a 1 60 1 70 的基地址為 2048 每個元素占 2 個存儲單元 若以列序?yàn)橹餍蝽樞虼鎯?則元素 a 32 58 的存儲地址為 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 三元素組表中的每個結(jié)點(diǎn)對應(yīng)于稀疏矩陣的一個非零元素 它包含有三個數(shù)據(jù)項(xiàng) 分別表示該元素 的 行下標(biāo) 列下標(biāo) 和 元素值 10 求下列廣義表操作的結(jié)果 1 GetHead a b c d a b 頭元素不必加括號 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)在 可以順序存儲 數(shù)據(jù)元素是一個字符 可以鏈?zhǔn)酱鎯?數(shù)據(jù)元素可以是多個字符 B 2 李 設(shè)有兩個串 p 和 q 求 q 在 p 中首次出現(xiàn)的位置的運(yùn)算稱作 連接 模式匹配 求子串 求串長 D 3 李 設(shè)串 s1 ABCDEFG s2 PQRST 函數(shù) con x y 返回 x 和 y 串的連接串 subs s i j 返回串 s 的從序號 i 開始的 j 個字符組成的子串 len s 返回串 s 的長度 則 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 的從序號 i 開始的 j 個字符組成的子串 則 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ī)系考研題 假設(shè)有 60 行 70 列的二維數(shù)組 a 1 60 1 70 以列序?yàn)橹餍蝽樞虼鎯?其基地址為 10000 每個元素占 2 個存儲單元 那么第 32 行第 58 列的元素 a 32 58 的存儲地址為 無第 0 行第 0 列元素 16902 16904 14454 答案 A B C 均不對 答 此題與填空題第 8 小題相似 57 列 60 行 31 行 2 字節(jié) 10000 16902 B 5 設(shè)矩陣 A 是一個對稱矩陣 為了節(jié)省存儲 將其下三角部分 如下圖所示 按行序存放在一維數(shù)組 B 1 n n 1 2 中 對下三角部分中任一元素 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)編號寫在答卷的對應(yīng)欄內(nèi) 有一個二維數(shù)組 A 行下標(biāo)的范圍是 0 到 8 列下標(biāo)的范圍是 1 到 5 每個數(shù)組元素用相鄰的 4 個字節(jié)存儲 存儲器按 字節(jié)編址 假設(shè)存儲數(shù)組元素 A 0 1 的第一個字節(jié)的地址是 0 存儲數(shù)組 A 的最后一個元素的第一個字節(jié)的地址是 A 若按行存儲 則 A 3 5 和 A 5 3 的第一個字節(jié)的地址分別是 B 和 C 若按列存儲 則 A 7 1 和 A 2 4 的第一個字節(jié)的地址分別是 D 和 E 供選擇的答案 A E 28 44 76 92 108 116 132 176 184 188 答案 ABCDE 8 3 5 1 6 7 94 程 P12 有一個二維數(shù)組 A 行下標(biāo)的范圍是 1 到 6 列下標(biāo)的范圍是 0 到 7 每個數(shù)組元素用相鄰的 6 個字節(jié)存儲 存儲器按字節(jié)編址 那么 這個數(shù)組的體積是 A 個字節(jié) 假設(shè)存儲數(shù)組元素 A 1 0 的第一個字節(jié)的地址是 0 則存儲 數(shù)組 A 的最后一個元素的第一個字節(jié)的地址是 B 若按行存儲 則 A 2 4 的第一個字節(jié)的地址是 C 若按列存儲 解 注意 B 的下標(biāo)要求從 1 開始 先用第一個元素去套用 可能有 B 和 C 再用第二個元素去套用 B 和 C B 2 而 C 3 不符 所以選 B nnnn aaa aa a A 2 1 2 21 2 1 1 11 則 A 5 7 的第一個字節(jié)的地址是 D 供選擇的答案 A D 12 66 72 96 114 120 156 234 276 282 11 283 12 288 答案 ABCD 12 10 3 9 三 簡答題 每小題 5 分 共 15 分 1 其他教材 已知二維數(shù)組 Am m 采用按行優(yōu)先順序存放 每個元素占 K 個存儲單元 并且第一個元素的存儲地址為 Loc a11 請寫出求 Loc aij 的計算公式 如果采用列優(yōu)先順序存放呢 解 公式教材已給出 此處雖是方陣 但行列公式仍不相同 按行存儲的元素地址公式是 Loc aij Loc a11 i 1 m j 1 K 按列存儲的元素地址公式是 Loc aij Loc a11 j 1 m i 1 K 2 全國專升本資格考試 遞歸算法比非遞歸算法花費(fèi)更多的時間 對嗎 為什么 答 不一定 時間復(fù)雜度與樣本個數(shù) n 有關(guān) 是指最深層的執(zhí)行語句耗費(fèi)時間 而遞歸算法與非遞歸算法在最深層的語句執(zhí) 行上是沒有區(qū)別的 循環(huán)的次數(shù)也沒有太大差異 僅僅是確定循環(huán)是否繼續(xù)的方式不同 遞歸用棧隱含循環(huán)次數(shù) 非遞歸用 循環(huán)變量來顯示循環(huán)次數(shù)而已 四 計算題 每題 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 解 參見填空題 4 三元素組表中的每個結(jié)點(diǎn)對應(yīng)于稀疏矩陣的一個非零元素 它包含有三個數(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 下列各三元組表分別表示一個稀疏矩陣 試寫出它們的稀疏矩陣 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 個 2 為 4 5 矩陣 非零元素有 5 個 五 算法設(shè)計題 每題 10 分 共 30 分 1 嚴(yán)題集 4 12 編寫一個實(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 已 順便 移動了 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 位 只用一個輔助存儲空間 for i 1 i k i if n i 0 求 n 和 k 的最大公約數(shù) p for i 0 i0 個結(jié)點(diǎn)的完全二叉樹的深度為 log2 n log2 n log2 n 1 log2 n 1 注 1 x 表示不小于 x 的最小整數(shù) x 表示不大于 x 的最大整數(shù) 它們與 含義不同 注 2 選 A 是錯誤的 例如當(dāng) n 為 2 的整數(shù)冪時就會少算一層 似乎 log2 n 1 是對的 A 4 把一棵樹轉(zhuǎn)換為二叉樹后 這棵二叉樹的形態(tài)是 唯一的 有多種 有多種 但根結(jié)點(diǎn)都沒有左孩子 有多種 但根結(jié)點(diǎn)都沒有右孩子 5 94 程 P11 從供選擇的答案中 選出應(yīng)填入下面敘述 內(nèi)的最確切的解答 把相應(yīng)編號寫在答卷的對應(yīng)欄內(nèi) 樹是結(jié)點(diǎn)的有限集合 它 A 根結(jié)點(diǎn) 記為 T 其余的結(jié)點(diǎn)分成為 m m 0 個 B 的集合 T1 T2 Tm 每個集合又都是樹 此時結(jié)點(diǎn) T 稱為 Ti的父結(jié)點(diǎn) Ti稱為 T 的子結(jié)點(diǎn) 1 i m 一個結(jié)點(diǎn)的 子結(jié)點(diǎn)個數(shù)為該結(jié)點(diǎn)的 C 供選擇的答案 A 有 0 個或 1 個 有 0 個或多個 有且只有 1 個 有 1 個或 1 個以上 B 互不相交 允許相交 允許葉結(jié)點(diǎn)相交 允許樹枝結(jié)點(diǎn)相交 C 權(quán) 維數(shù) 次數(shù) 或度 序 答案 ABC 1 1 3 6 95 程 P13 從供選擇的答案中 選出應(yīng)填入下面敘述 內(nèi)的最確切的解答 把相應(yīng)編號寫在答卷的對應(yīng)欄內(nèi) 二叉樹 A 在完全的二叉樹中 若一個結(jié)點(diǎn)沒有 B 則它必定是葉結(jié)點(diǎn) 每棵樹都能惟一地轉(zhuǎn)換成與它對應(yīng)的 二叉樹 由樹轉(zhuǎn)換成的二叉樹里 一個結(jié)點(diǎn) N 的左子女是 N 在原樹里對應(yīng)結(jié)點(diǎn)的 C 而 N 的右子女是它在原樹里對應(yīng) 結(jié)點(diǎn)的 D 供選擇的答案 A 是特殊的樹 不是樹的特殊形式 是兩棵樹的總稱 有是只有二個根結(jié)點(diǎn)的樹形結(jié)構(gòu) B 左子結(jié)點(diǎn) 右子結(jié)點(diǎn) 左子結(jié)點(diǎn)或者沒有右子結(jié)點(diǎn) 兄弟 C D 最左子結(jié)點(diǎn) 最右子結(jié)點(diǎn) 最鄰近的右兄弟 最鄰近的左兄弟 最左的兄弟 最右的兄弟 答案 A B C D 答案 ABCDE 2 1 1 3 四 簡答題 每小題 4 分 共 20 分 1 嚴(yán)題集 6 2 一棵度為 2 的樹與一棵二叉樹有何區(qū)別 答 度為 2 的樹從形式上看與二叉樹很相似 但它的子樹是無序的 而二叉樹 是有序的 即 在一般樹中若某結(jié)點(diǎn)只有一個孩子 就無需區(qū)分其左右次序 而在二叉樹中即使是一個孩子也有左右之分 2 01 年計算機(jī)研題 設(shè)如下圖所示的二叉樹 B 的存儲結(jié)構(gòu)為二叉鏈表 root 為根指針 結(jié)點(diǎn)結(jié)構(gòu)為 lchild data rchild 其中 lchild rchild 分別為指向左 右孩子的指針 data 為字符型 root 為根指針 試回答下列問題 1 對下列二叉樹 B 執(zhí)行下列算法 traversal root 試指出其輸出結(jié)果 2 假定二叉樹 B 共有 n 個結(jié)點(diǎn) 試分析算法 traversal root 的時間復(fù)雜度 共 8 分 二叉樹 B A B D C F G E C 的結(jié)點(diǎn)類型定義如下 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) 每個結(jié)點(diǎn)肯定都會被打印兩次 但出現(xiàn)的順序不同 其規(guī)律是 凡是有左子樹的結(jié)點(diǎn) 必間隔左子樹的全部結(jié)點(diǎn) 后再重復(fù)出現(xiàn) 如 A B D 等結(jié)點(diǎn) 反之馬上就會重復(fù)出現(xiàn) 如 C E F G 等結(jié)點(diǎn) 時間復(fù)雜度以訪問結(jié)點(diǎn)的次數(shù)為主 精確值為 2 n 時間漸近度為 O n 3 01 年計算機(jī)研題 嚴(yán)題集 6 27 給定二叉樹的兩種遍歷序列 分別是 前序遍歷序列 D A C E B H F G I 中序遍歷序列 D C B E H A G I F 試畫出二叉樹 B 并簡述由任意二叉樹 B 的前序遍歷序列和中序遍歷序列求二叉樹 B 的思想方法 解 方法是 由前序先確定 root 由中序可確定 root 的左 右子樹 然后由其左子樹的元素集合和右子樹的集合對應(yīng)前序遍 歷序列中的元素集合 可繼續(xù)確定 root 的左右孩子 將他們分別作為新的 root 不斷遞歸 則所有元素都將被唯一確定 問 題得解 D A C F E G B H I 4 計算機(jī)研 2000 給定如圖所示二叉樹 T 請畫出與其對應(yīng)的中序線索二叉樹 解 要遵循中序遍歷的軌跡來畫出每個前驅(qū)和后繼 中序遍歷序列 55 40 25 60 28 08 33 54 28 25 33 40 60 08 54 55 五 閱讀分析題 每題 5 分 共 20 分 1 P60 4 26 試寫出如圖所示的二叉樹分別按先序 中序 后序遍歷時得到的結(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 把如圖所示的樹轉(zhuǎn)化成二叉樹 答 注意全部兄弟之間都要連線 包括度為 2 的兄弟 并注意原有連線結(jié)點(diǎn)一律歸入左子樹 新添連線結(jié)點(diǎn)一律歸入右子 樹 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 閱讀下列算法 若有錯 改正之 4 嚴(yán)題集 6 21 畫出和下列二叉樹相應(yīng)的森林 答 注意根右邊的子樹肯定是森林 而孩子結(jié)點(diǎn)的右子樹均為兄弟 六 算法設(shè)計題 前 5 題中任選 2 題 第 6 題必做 每題 8 分 共 24 分 1 嚴(yán)題集 6 42 編寫遞歸算法 計算二叉樹中葉子結(jié)點(diǎn)的數(shù)目 解 思路 輸出葉子結(jié)點(diǎn)比較簡單 用任何一種遍歷遞歸算法 凡是左右指針均空者 則為葉子 將其打印出來 法一 核心部分為 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 求二叉樹中葉子結(jié)點(diǎn)的數(shù)目 if T return 0 空樹沒有葉子 else if T lchild 葉子結(jié)點(diǎn) else return Leaf Count T lchild Leaf Count T rchild 左子樹的葉子數(shù)加 上右子樹的葉子數(shù) LeafCount BiTree 注 上機(jī)時要先建樹 例如實(shí)驗(yàn)二的方案一 打印葉子結(jié)點(diǎn)值 并求總數(shù) 思路 先建樹 再從遍歷過程中打印結(jié)點(diǎn)值并統(tǒng)計 步驟 1 鍵盤輸入序列 12 8 17 11 16 2 13 9 21 4 構(gòu)成一棵二叉排序樹 葉子結(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 是指向中序線索二叉樹上某個結(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 處錯誤 注 當(dāng) rtag 1 時說明內(nèi)裝后繼指針 可 直接返回 第一句無錯 當(dāng) rtag 0 時說明內(nèi)裝右孩子指針 但孩 子未必是后繼 需要計算 中序遍歷應(yīng)當(dāng) 先左再根再右 所以應(yīng)當(dāng)找左子樹直到葉 子處 r rr r lchild lchild 直到直到 LTag 1LTag 1 應(yīng)改為 while r Ltag r r Lchild 17 編程 生成二叉樹排序樹之后 再中序遍歷排序查找結(jié)點(diǎn)的完整程序如下 說明部分為 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 如何生成二叉排序樹 參見教材 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 如何接入二叉排序樹的適當(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 先生成二叉排序樹 再調(diào)用中序遍歷遞歸函數(shù)進(jìn)行排序輸出 int i x i 1 root NULL 千萬別忘了賦初值給 root do printf please input data d i i scanf d 從鍵盤采集數(shù)據(jù) 以 9999 表示輸入結(jié)束 if x 9999 DLR root printf nNo