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

1 第一章概論 自測題答案 一 填空題 1 數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機的 操作對象 以及它們之間的 關(guā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ù)的 運算 這三個方面的內(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é)點 沒有 前驅(qū)結(jié)點 其余每個結(jié)點有且只有 1 個前驅(qū)結(jié)點 最后一個結(jié)點 沒有 后續(xù)結(jié) 點 其余每個結(jié)點有且只有 1 個后續(xù)結(jié)點 7 在樹形結(jié)構(gòu)中 樹根結(jié)點沒有 前驅(qū) 結(jié)點 其余每個結(jié)點有且只有 1 個前驅(qū)結(jié)點 葉子結(jié)點沒有 后續(xù) 結(jié)點 其余每個結(jié)點的后續(xù)結(jié)點數(shù)可以任意多個 8 在圖形結(jié)構(gòu)中 每個結(jié)點的前驅(qū)結(jié)點數(shù)和后續(xù)結(jié)點數(shù)可以 任意多個 9 數(shù)據(jù)的存儲結(jié)構(gòu)可用四種基本的存儲方法表示 它們分別是順序 鏈?zhǔn)?索引 和 散列 10 數(shù)據(jù)的運算最常用的有 5 種 它們分別是插入 刪除 修改 查找 排序 11 一個算法的效率可分為 時間 效率和 空間 效率 二 單項選擇題 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)中 與所使用的計算機無關(guān)的是數(shù)據(jù)的 結(jié)構(gòu) A 存儲 B 物理 C 邏輯 D 物理和存儲 C 3 算法分析的目的是 A 找出數(shù)據(jù)結(jié)構(gòu)的合理性 B 研究算法中的輸入和輸出的關(guān)系 C 分析算法的效率以求改進 D 分析算法的易懂性和文檔性 A 4 算法分析的兩個主要方面是 A 空間復(fù)雜性和時間復(fù)雜性 B 正確性和簡明性 C 可讀性和文檔性 D 數(shù)據(jù)復(fù)雜性和程序復(fù)雜性 C 5 計算機算法指的是 A 計算方法 B 排序方法 C 解決問題的有限運算序列 D 調(diào)度方法 B 6 計算機算法必須具備輸入 輸出和 等 5 個特性 A 可行性 可移植性和可擴充性 B 可行性 確定性和有窮性 C 確定性 有窮性和穩(wěn)定性 D 易讀性 穩(wěn)定性和安全性 三 簡答題 2 嚴題集 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)的不同點 答 線性結(jié)構(gòu)反映結(jié)點間的邏輯關(guān)系是答 線性結(jié)構(gòu)反映結(jié)點間的邏輯關(guān)系是 一對一的 非線性結(jié)構(gòu)反映結(jié)點間的邏輯關(guān)系是多對多的 一對一的 非線性結(jié)構(gòu)反映結(jié)點間的邏輯關(guā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 解 因為 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é)點是開始 結(jié)點 哪些結(jié)點是終端結(jié)點 1 嚴蔚敏習(xí)題集 P7 1 3 D d1 d2 d3 d4 R d1 d2 d2 d3 d3 d4 答 d1 d2 d3 d4 d1 無直接前驅(qū) 是首結(jié)點 d4 無直接后繼是尾結(jié)點 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é)點 d2 d5 d7 d9 無直接后繼是葉子結(jié)點 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é)點 d6 d7 無直接后繼是終端結(jié)點 2 3 第 2 章 自測卷答案 一 填空 1 嚴題集 2 2 在順序表中插入或刪除一個元素 需要平均移動 表中一半元素 具體移動的元素個數(shù)與 表長和該元素 在表中的位置 有關(guān) 2 線性表中結(jié)點的集合是 有限 的 結(jié)點間的關(guān)系是 一對一 的 3 向一個長度為 n 的向量的第 i 個元素 1 i n 1 之前插入一個元素時 需向后移動 n i 1 個元素 4 向一個長度為 n 的向量中刪除第 i 個元素 1 i n 時 需向前移動 n i 個元素 5 在順序表中訪問任意一結(jié)點的時間復(fù)雜度均為 O 1 因此 順序表也稱為 隨機存取 的數(shù)據(jù)結(jié)構(gòu) 6 嚴題集 2 2 順序表中邏輯上相鄰的元素的物理位置 必定相鄰 單鏈表中邏輯上相鄰的元素的物理位置 不一定 相 鄰 7 嚴題集 2 2 在單鏈表中 除了首元結(jié)點外 任一結(jié)點的存儲位置由 其直接前驅(qū)結(jié)點的鏈域的值 指示 8 在 n 個結(jié)點的單鏈表中要刪除已知結(jié)點 p 需找到它的前驅(qū)結(jié)點的地址 其時間復(fù)雜度為 O n 二 判斷正誤 在正確的說法后面打勾 反之打叉 1 鏈表的每個結(jié)點中都恰好包含一個指針 答 錯誤 鏈表中的結(jié)點可含多個指針域 分別存放多個指針 例如 雙向鏈表中的結(jié)點可以含有兩個指針 域 分別存放指向其直接前趨和直接后繼結(jié)點的指針 2 鏈表的物理存儲結(jié)構(gòu)具有同鏈表一樣的順序 錯 鏈表的存儲結(jié)構(gòu)特點是無序 而鏈表的示意圖有序 3 鏈表的刪除算法很簡單 因為當(dāng)刪除鏈中某個結(jié)點后 計算機會自動地將后續(xù)的各個單元向前移動 錯 鏈表 的結(jié)點不會移動 只是指針內(nèi)容改變 4 線性表的每個結(jié)點只能是一個簡單類型 而鏈表的每個結(jié)點可以是一個復(fù)雜類型 錯 混淆了邏輯結(jié)構(gòu)與物理結(jié)構(gòu) 鏈表也是線性表 且即使是順序表 也能存放記錄型數(shù)據(jù) 5 順序表結(jié)構(gòu)適宜于進行順序存取 而鏈表適宜于進行隨機存取 錯 正好說反了 順序表才適合隨機存取 鏈表恰恰適于 順藤摸瓜 6 順序存儲方式的優(yōu)點是存儲密度大 且插入 刪除運算效率高 錯 前一半正確 但后一半說法錯誤 那是鏈?zhǔn)酱鎯Φ膬?yōu)點 順序存儲方式插入 刪除運算效率較低 在表長為 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需一致 三 單項選擇題 C 1 數(shù)據(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é)點的順序表中 算法的時間復(fù)雜度是 O 1 的操作是 A 訪問第 i 個結(jié)點 1 i n 和求第 i 個結(jié)點的直接前驅(qū) 2 i n B 在第 i 個結(jié)點后插入一個新結(jié)點 1 i n C 刪除第 i 個結(jié)點 1 i n D 將 n 個結(jié)點從小到大排序 B 4 向一個有 127 個元素的順序表中插入一個新元素并保持原來順序不變 平均要移動 個元素 A 8 B 63 5 C 63 D 7 A 5 鏈接存儲的存儲結(jié)構(gòu)所占存儲空間 A 分兩部分 一部分存放結(jié)點值 另一部分存放表示結(jié)點間關(guān)系的指針 B 只有一部分 存放結(jié)點值 C 只有一部分 存儲表示結(jié)點間關(guān)系的指針 D 分兩部分 一部分存放結(jié)點值 另一部分存放結(jié)點所占單元數(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)實現(xiàn) 需經(jīng)常修改 中的結(jié)點值 需不斷對 進行刪除插入 中含有大量的結(jié)點 中結(jié)點結(jié)構(gòu)復(fù)雜 C 9 單鏈表的存儲密度 大于 1 等于 1 小于 1 不能確定 B 10 設(shè) a1 a2 a3 為 3 個結(jié)點 整數(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 嚴題集 2 3 試比較順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)的優(yōu)缺點 在什么情況下用順序表比鏈表好 答 順序存儲時 相鄰數(shù)據(jù)元素的存放地址也相鄰 邏輯與物理統(tǒng)一 要求內(nèi)存中可用存儲單元的地址必須是連續(xù)的 優(yōu)點 存儲密度大 1 存儲空間利用率高 缺點 插入或刪除元素時不方便 鏈?zhǔn)酱鎯r 相鄰數(shù)據(jù)元素可隨意存放 但所占存儲空間分兩部分 一部分存放結(jié)點值 另一部分存放表示結(jié)點間 關(guān)系的指針 優(yōu)點 插入或刪除元素時很方便 使用靈活 缺點 存儲密度小 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 對他們分別進行棧操作或隊操作 在進?；蜻M隊操作時 按 a1 a2 a3 a4 次 序每次進入一個元素 假設(shè)?；蜿牭某跏紶顟B(tài)都是空 現(xiàn)要進行的棧操作是進棧兩次 出棧一次 再進棧兩次 出棧一次 這時 第一次出棧得到的元素是 A 第二次 出棧得到的元素是 B 是 類似地 考慮對這四個數(shù)據(jù)元素進行的隊操作是進隊兩次 出隊一次 再進隊兩次 出隊 一次 這時 第一次出隊得到的元素是 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) 棧是一種線性表 它的特點是 A 設(shè)用一維數(shù)組 A 1 n 來表示一個棧 A n 為棧底 用整型變量 T 指示當(dāng)前棧 頂位置 A T 為棧頂元素 往棧中推入 PUSH 一個新元素時 變量 T 的值 B 從棧中彈出 POP 一個元素時 變 量 T 的值 C 設(shè)?？諘r 有輸入序列 a b c 經(jīng)過 PUSH POP PUSH PUSH POP 操作后 從棧中彈出的元素的 序列是 D 變量 T 的值是 E 供選擇的答案 A 先進先出 后進先出 進優(yōu)于出 出優(yōu)于進 隨機進出 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) 在做進棧運算時 應(yīng)先判別棧是否 A 在做退棧運算時 應(yīng)先判別棧是否 B 當(dāng)棧中元素為 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 兩個棧的棧頂同時到達?？臻g的中心點 其中一個棧的棧頂?shù)竭_?？臻g的中心點 兩個棧的棧頂在達?？臻g的某一位置相遇 兩個棧均不空 且一個棧的棧頂?shù)竭_另一個棧的棧底 答案 ABCDE 2 1 2 4 3 四 簡答題 每小題 4 分 共 20 分 1 嚴題集 3 2 和 3 11 說明線性表 棧與隊的異同點 劉答 相同點 都是線性結(jié)構(gòu) 都是邏輯結(jié)構(gòu)的概念 都可以用順序存儲或鏈表存儲 棧和隊列是兩種特殊的線性表 即受 限的線性表 只是對插入 刪除運算加以限制 不同點 運算規(guī)則不同 線性表為隨機存取 而棧是只允許在一端進行插入 刪除運算 因而是后進先出表 LIFO 隊列 是只允許在一端進行插入 另一端進行刪除運算 因而是先進先出表 FIFO 用途不同 堆棧用于子程調(diào)用和保護現(xiàn)場 隊列用于多道作業(yè)處理 指令寄存及其他運算等等 2 統(tǒng)考書 P60 4 11 難于嚴題集 3 1 設(shè)有編號為 1 2 3 4 的四輛列車 順序進入一個棧式結(jié)構(gòu)的車站 具體寫出 這四輛列車開出車站的所有可能的順序 劉答 至少有 14 種 全進之后再出情況 只有 1 種 4 3 2 1 進 3 個之后再出的情況 有 3 種 3 4 2 1 3 2 4 1 3 2 1 4 進 2 個之后再出的情況 有 5 種 2 4 3 1 2 3 4 1 2 1 3 4 2 1 4 3 2 3 1 4 進 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è)一字符序列已存入計算機 請分析用線性表 堆棧和隊列等方式正確輸出其回文的可能性 答 線性表是隨機存儲 可以實現(xiàn) 靠循環(huán)變量 j 從表尾開始打印輸出 堆棧是后進先出 也可以實現(xiàn) 靠正序入棧 逆序出棧即可 隊列是先進先出 不易實現(xiàn) 6 哪種方式最好 要具體情況具體分析 若正文在機內(nèi)已是順序存儲 則直接用線性表從后往前讀取即可 或?qū)⒍褩ｍ?開到數(shù)組末尾 然后直接用 POP 動作實現(xiàn) 但堆棧是先減后壓還是 若正文是單鏈表形式存儲 則等同于隊列 需開輔助空間 可以從鏈?zhǔn)组_始入棧 全部壓入后再依次輸出 4 統(tǒng)考書 P60 4 13 順序隊的 假溢出 是怎樣產(chǎn)生的 如何知道循環(huán)隊列是空還是滿 答 一般的一維數(shù)組隊列的尾指針已經(jīng)到了數(shù)組的上界 不能再有入隊操作 但其實數(shù)組中還有空位置 這就叫 假溢出 采用循環(huán)隊列是解決假溢出的途徑 另外 解決隊滿隊空的辦法有三 設(shè)置一個布爾變量以區(qū)別隊滿還是隊空 浪費一個元素的空間 用于區(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)過一系列的入隊和出隊運算后 有 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 嚴題集 3 7 按照四則運算加 減 乘 除和冪運算 優(yōu)先關(guān)系的慣例 并仿照教材例 3 2 的格式 畫出對下 列算術(shù)表達式求值時操作數(shù)棧和運算符棧的變化過程 A B C D E F 答 2 嚴題集 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 嚴題集 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 嚴題集 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ù)元素進行逆置 六 算法設(shè)計 每小題 5 分 共 15 分 至少要寫出思路 1 李春葆及嚴題集 3 19 假設(shè)一個算術(shù)表達式中包含圓括弧 方括弧和花括弧三種類型的括弧 編寫一個判別表達式 中括弧是否正確配對的函數(shù) correct exp tag 其中 exp 為字符串類型的變量 可理解為每個字符占用一個數(shù)組元素 表示被判別的表達式 tag 為布爾型變量 答 用堆棧 st 進行判定 將 或 入棧 當(dāng)遇到 或 時 檢查當(dāng)前棧頂元素是否是對應(yīng)的 或 若是則退棧 否則返回表示不配對 當(dāng)整個算術(shù)表達式檢查完畢時 若棧為空表示括號正確配對 否則不配對 編程后的整個函數(shù)如下 李書 P31 32 define m0 100 m0 為算術(shù)表達式中最多字符個數(shù) correct exp tag char exp m0 int tag char st m0 int top 0 i 1 tag 1 while i0 tag 0 若棧不空 則不配對 嚴題集對應(yīng)答案 8 3 19 Status AllBrackets Test char str 判別表達式中三種括號是否匹配 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é)答案 已上機通過 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ù)的變量 因為 C 語言的函數(shù)變量是傳值機制 所以在函數(shù)中 對參數(shù)進行了拷貝復(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 嚴題集 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)嚴題集 4 1 簡答題 簡述空串和空格串的區(qū)別 2 設(shè) S A document Mary doc 則 strlen s 20 的字符定位的位置為 3 4 子串的定位運算稱為串的模式匹配 被匹配的主串 稱為目標(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 年計算機系考研題 設(shè)數(shù)組 a 1 60 1 70 的基地址為 2048 每個元素占 2 個存儲單元 若以列序為主序順序存儲 則元素 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é)點對應(yīng)于稀疏矩陣的一個非零元素 它包含有三個數(shù)據(jù)項 分別表示該元素 的 行下標(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)的位置的運算稱作 連接 模式匹配 求子串 求串長 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 年計算機系考研題 假設(shè)有 60 行 70 列的二維數(shù)組 a 1 60 1 70 以列序為主序順序存儲 其基地址為 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ù)雜度與樣本個數(shù) n 有關(guān) 是指最深層的執(zhí)行語句耗費時間 而遞歸算法與非遞歸算法在最深層的語句執(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 因為 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é)點對應(yīng)于稀疏矩陣的一個非零元素 它包含有三個數(shù)據(jù)項 分別表示該元素的 行 下標(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 嚴題集 4 12 編寫一個實現(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é)點的完全二叉樹的深度為 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é)點都沒有左孩子 有多種 但根結(jié)點都沒有右孩子 5 94 程 P11 從供選擇的答案中 選出應(yīng)填入下面敘述 內(nèi)的最確切的解答 把相應(yīng)編號寫在答卷的對應(yīng)欄內(nèi) 樹是結(jié)點的有限集合 它 A 根結(jié)點 記為 T 其余的結(jié)點分成為 m m 0 個 B 的集合 T1 T2 Tm 每個集合又都是樹 此時結(jié)點 T 稱為 Ti的父結(jié)點 Ti稱為 T 的子結(jié)點 1 i m 一個結(jié)點的 子結(jié)點個數(shù)為該結(jié)點的 C 供選擇的答案 A 有 0 個或 1 個 有 0 個或多個 有且只有 1 個 有 1 個或 1 個以上 B 互不相交 允許相交 允許葉結(jié)點相交 允許樹枝結(jié)點相交 C 權(quán) 維數(shù) 次數(shù) 或度 序 答案 ABC 1 1 3 6 95 程 P13 從供選擇的答案中 選出應(yīng)填入下面敘述 內(nèi)的最確切的解答 把相應(yīng)編號寫在答卷的對應(yīng)欄內(nèi) 二叉樹 A 在完全的二叉樹中 若一個結(jié)點沒有 B 則它必定是葉結(jié)點 每棵樹都能惟一地轉(zhuǎn)換成與它對應(yīng)的 二叉樹 由樹轉(zhuǎn)換成的二叉樹里 一個結(jié)點 N 的左子女是 N 在原樹里對應(yīng)結(jié)點的 C 而 N 的右子女是它在原樹里對應(yīng) 結(jié)點的 D 供選擇的答案 A 是特殊的樹 不是樹的特殊形式 是兩棵樹的總稱 有是只有二個根結(jié)點的樹形結(jié)構(gòu) B 左子結(jié)點 右子結(jié)點 左子結(jié)點或者沒有右子結(jié)點 兄弟 C D 最左子結(jié)點 最右子結(jié)點 最鄰近的右兄弟 最鄰近的左兄弟 最左的兄弟 最右的兄弟 答案 A B C D 答案 ABCDE 2 1 1 3 四 簡答題 每小題 4 分 共 20 分 1 嚴題集 6 2 一棵度為 2 的樹與一棵二叉樹有何區(qū)別 答 度為 2 的樹從形式上看與二叉樹很相似 但它的子樹是無序的 而二叉樹 是有序的 即 在一般樹中若某結(jié)點只有一個孩子 就無需區(qū)分其左右次序 而在二叉樹中即使是一個孩子也有左右之分 2 01 年計算機研題 設(shè)如下圖所示的二叉樹 B 的存儲結(jié)構(gòu)為二叉鏈表 root 為根指針 結(jié)點結(jié)構(gòu)為 lchild data rchild 其中 lchild rchild 分別為指向左 右孩子的指針 data 為字符型 root 為根指針 試回答下列問題 1 對下列二叉樹 B 執(zhí)行下列算法 traversal root 試指出其輸出結(jié)果 2 假定二叉樹 B 共有 n 個結(jié)點 試分析算法 traversal root 的時間復(fù)雜度 共 8 分 二叉樹 B A B D C F G E C 的結(jié)點類型定義如下 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é)點一次 輸出結(jié)果為 A B C C E E B A D F F D G G 特點 每個結(jié)點肯定都會被打印兩次 但出現(xiàn)的順序不同 其規(guī)律是 凡是有左子樹的結(jié)點 必間隔左子樹的全部結(jié)點 后再重復(fù)出現(xiàn) 如 A B D 等結(jié)點 反之馬上就會重復(fù)出現(xiàn) 如 C E F G 等結(jié)點 時間復(fù)雜度以訪問結(jié)點的次數(shù)為主 精確值為 2 n 時間漸近度為 O n 3 01 年計算機研題 嚴題集 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 計算機研 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é)點序列 答 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é)點一律歸入左子樹 新添連線結(jié)點一律歸入右子 樹 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 嚴題集 6 17 閱讀下列算法 若有錯 改正之 4 嚴題集 6 21 畫出和下列二叉樹相應(yīng)的森林 答 注意根右邊的子樹肯定是森林 而孩子結(jié)點的右子樹均為兄弟 六 算法設(shè)計題 前 5 題中任選 2 題 第 6 題必做 每題 8 分 共 24 分 1 嚴題集 6 42 編寫遞歸算法 計算二叉樹中葉子結(jié)點的數(shù)目 解 思路 輸出葉子結(jié)點比較簡單 用任何一種遍歷遞歸算法 凡是左右指針均空者 則為葉子 將其打印出來 法一 核心部分為 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é)點的數(shù)目 if T return 0 空樹沒有葉子 else if T lchild 葉子結(jié)點 else return Leaf Count T lchild Leaf Count T rchild 左子樹的葉子數(shù)加 上右子樹的葉子數(shù) LeafCount BiTree 注 上機時要先建樹 例如實驗二的方案一 打印葉子結(jié)點值 并求總數(shù) 思路 先建樹 再從遍歷過程中打印結(jié)點值并統(tǒng)計 步驟 1 鍵盤輸入序列 12 8 17 11 16 2 13 9 21 4 構(gòu)成一棵二叉排序樹 葉子結(jié)點值應(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é)點的指針 本函數(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é)點后繼的程序 共有 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é)點的完整程序如下 說明部分為 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ù)進行排序輸出 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