第第 2 部分部分 習題解析習題解析 第 1 章 緒論 1 1 選擇題 1 算法的時間復雜度取決于 C A 問題的規模 B 待處理數據的初態 C A 和 B 答案 C 2 計算機算法指的是解決問題的步驟序列 它必須具備 B 這三個特性 A 可執行性 可移植性 可擴充性B 可執行性 確定性 有窮性 C 確定性 有窮性 穩定性D 易讀性 穩定性 安全性 答案 B 5 從邏輯上可以把數據結構分為 C 兩大類 A 動態結構 靜態結構B 順序結構 鏈式結構 C 線性結構 非線性結構D 初等結構 構造型結構 答案 C 6 在下面的程序段中 對 x 的賦值的語句頻度為 C for i 0 i n i for j 0 j 1 i for j 1 jA j 1 A j 與 A j 1 對換 A O n B O nlog2n C O n3 D O n2 答案 D 1 2 填空題 2 對于給定的 n 個元素 可以構造出的邏輯結構有 四種 答案 1 集合 2 線性結構 3 樹形結構 4 圖狀結構或網狀結構 4 數據結構中評價算法的兩個重要指標是 答案 算法的時間復雜度和空間復雜度 5 數據結構是研討數據的 和 以及它們之間的相互關系 并對與這種結 構定義相應的 設計出相應的 答案 1 邏輯結構 2 物理結構 3 操作 運算 4 算法 6 一個算法具有 5 個特性 有零個或多個輸入 有一個或多個輸出 答案 1 有窮性 2 確定性 3 可行性 9 已知如下程序段 for i n i 0 i 語句 1 x x 1 語句 2 for j n j i j 語句 3 y y 1 語句 4 語句 1 執行的頻度為 語句 2 執行的頻度為 語句 3 執行的頻度為 語句 4 執行的頻度為 答案 1 n 1 2 n 3 n n 3 2 4 n n 1 2 10 在下面的程序段中 對 的賦值語句的頻度為 表示為 n 的函數 for i 0 i n i for j 0 j i j for k 0 k j k delta 數據結構上機實驗與習題解析 亱店 打烊 oO 2 答案 1 1 2 1 2 3 1 2 n n n 1 n 2 6 O n3 11 下面程序段中帶下劃線的語句的執行次數的數量級是 i 1 while i n i i 2 答案 log2n 12 計算機執行下面的語句時 語句 s 的執行次數為 for i l i i j s 答案 n 3 n 2 2 13 下面程序段的時間復雜度為 n 1 sum 1 for i 0 sumprior q q next p p prior next q q prior p prior B q prior p prior p prior next q q next p p prior q next C q next p p next q p prior next q q next p D p prior next q q next p q prior p prior p prior q 答案 D 4 在一個具有 n 個結點的有序單鏈表中插入一個新結點并仍然保持有序的時間復雜度是 A O nlog2n B O 1 C O n D O n2 答案 C 5 在一個以 h 為頭指針的單循環鏈中 p 指針指向鏈尾結點的條件是 A p next NULLB p next h C p next next hD p data 1 答案 B 6 對于一個具有 n 個結點的線性表 建立其單鏈表的時間復雜度是 A O n B O 1 C O nlog2n D O n2 答案 A 8 在雙向鏈表存儲結構中 刪除 p 所指的結點時須修改指針 A p prior next p nextp next prior p prior B p prior p prior priorp prior next p C p next prior pp next p next next D p next p prior priorp prior p next next 答案 A 9 線性表采用鏈式存儲時 其元素地址 A 必須是連續的B 一定是不連續的 C 部分地址是連續的D 連續與否均可 答案 D 2 2 填空題 1 線性表 L a1 a2 an 用數組表示 假定刪除表中任一元素的概率相同 則刪除一個元素 第 2 部分 習題解析 亱店 打烊 oO 3 平均需要移動元素的個數是 答案 n 1 2 2 在單鏈表中設置頭結點的作用是 答案 主要是使插入和刪除等操作統一 在第一個元素之前插入元素和刪除第一個結點不必另作判 斷 另外 不論鏈表是否為空 鏈表頭指針不變 3 線性表的順序存儲是通過 來反應元素之間的邏輯關系 而鏈式存儲結構是通過 來反應元素之間的邏輯關系 答案 1 數據元素的前后順序 2 元素中的指針 4 當對一個線性表經常進行的是存取操作 而很少進行插入和刪除操作時 則采用 存 儲結構最節省時間 相反當經常進行插入和刪除操作時 則采用 存儲結構最節省時間 答案 1 順序 2 鏈式 5 對于一個具有 n 個結點的單鏈表 在已知的結點 p 后插入一個新結點的時間復雜度為 在給定值為 x 的結點后插入一個新結點的時間復雜度為 答案 1 O 1 2 O n 7 對于雙向鏈表 在兩個結點之間插入一個新結點需修改的指針共 個 單鏈表為 個 答案 1 4 2 2 8 循環單鏈表的最大優點是 答案 從任一結點出發都可訪問到鏈表中每一個元素 9 若要在一個不帶頭結點的單鏈表的首結點 p 結點之前插入一個 s 結點時 可執行下列操作 s next p next s t p data p data s data 答案 1 p next 2 s data 3 t 10 某線性表采用順序存儲結構 每個元素占據 4 個存儲單元 首地址為 100 則下標為 11 的 第 12 個 元素的存儲地址為 答案 144 11 帶頭結點的雙循環鏈表 L 中只有一個元素結點的條件是 答案 L next next L 2 3 判斷題 1 取線性表的第 i 個元素的時間同 i 的大小有關 答案 2 線性表的特點是每個元素都有一個前驅和一個后繼 答案 3 順序存儲方式的優點是存儲密度大 且插入 刪除運算效率高 答案 4 線性表采用鏈表存儲時 結點的存儲空間可以是不連續的 答案 5 鏈表是采用鏈式存儲結構的線性表 進行插入 刪除操作時 在鏈表中比在順序存儲結構中效率 高 答案 6 順序存儲方式只能用于存儲線性結構 答案 解析 線性結構 樹型結構和圖狀結構均可用順序存儲表示 9 順序存儲結構的主要缺點是不利于插入或刪除操作 答案 10 順序存儲方式插入和刪除時效率太低 因此它不如鏈式存儲方式好 答案 2 4 程序設計題 1 設順序表 va 中的數據元素遞增有序 試設計一個算法 將 x 插入到順序表的適當位置上 以保持 數據結構上機實驗與習題解析 亱店 打烊 oO 4 該表的有序性 算法源代碼 void Insert SqList SqList va int x 把 x 插入遞增有序表 va 中 int i if va length MAXSIZE return for i va length 1 va elem i xi va elem i 1 va elem i va elem i 1 x va length Insert SqList 2 設 A a1 a2 am 和 B b1 b2 bn 均為順序表 試設計一個比較 A B 大小的算 法 請注意 在算法中 不要破壞原表 A 和 B 算法分析 比較順序表 A 和 B 并用返回值表示結果 值為 1 表示 A B 值為 1 表示 A B 值為 0 表示 A B 1 當兩個順序表可以互相比較時 若對應元素不等 則返回值為 1 或 1 2 當兩個順序表可以互相比較的部分完全相同時 若表長也相同 則返回值為 0 否則 哪個較長 哪個就較大 算法源代碼 int ListComp SqList A SqList B for i 1 i A length if A length B length return 0 return A length B length 1 1 當兩個順序表可以互相比較的部分完全相同時 哪個較長 哪個就較大 ListComp 3 已知指針 ha 和 hb 分別指向兩個單鏈表的頭結點 并且已知兩個鏈表的長度分別為 m 和 n 試設 計一個算法將這兩個鏈表連接在一起 即令其中一個表的首元結點連在另一個表的最后一個結點之后 假設指針 hc 指向連接后的鏈表的頭結點 并要求算法以盡可能短的時間完成連接運算 算法分析 1 單鏈表 ha 的頭結點作為連接后的鏈表的頭結點 即 hc ha 2 查找單鏈表 ha 的最后一個結點 由指針 p 指向 即 p next NULL 3 將單鏈表 hb 的首元結點 非頭結點 連接在 p 之后 即 p next hb next 4 回收單鏈表 hb 的頭結點空間 算法源代碼 void ListConcat LinkList ha LinkList hb LinkList hc 把鏈表 hb 接在 ha 后面形成鏈表 hc hc ha p ha 由指針 p 指向 ha 的尾元結點 p p next p next hb next free hb ListConcat 4 試設計一個算法 在無頭結點的動態單鏈表上實現線性表操作 INSERT L i b 并和在帶頭 結點的動態單鏈表上實現相同操作的算法進行比較 算法分析 1 生成新結點存放元素 b 由指針 new 指向 2 將 new 插入在單鏈表的第 i 個元素的位置上 若 i 1 new 插在鏈表首部 否則查找第 i 1 個結 點 由指針 p 指向 然后將 new 插在 p 之后 算法源代碼 void Insert LinkList L int i int b LinkList new 第 2 部分 習題解析 亱店 打烊 oO 5 new LinkList malloc sizeof LNode new data b if i 1 插入在鏈表頭部 New next L L new else 插入在第 i 個元素的位置 p L while i 1 p p next new next p next p next new Insert 5 已知線性表中的元素以值遞增有序排列 并以單鏈表作存儲結構 試設計一個高效的算法 刪除 表中所有值大于 mink 且小于 maxk 的元素 若表中存在這樣的元素 同時釋放被刪結點空間 注意 mink 和 maxk 是給定的兩個參變量 它們的值可以和表中的元素相同 也可以不同 算法分析 1 查找最后一個不大于 mink 的元素結點 由指針 p 指向 2 如果還有比 mink 更大的元素 查找第一個不小于 maxk 的元素 由指針 q 指向 3 p next q 即刪除表中所有值大于 mink 且小于 maxk 的元素 算法源代碼 void Delete Between LinkList L int mink int maxk p L while p next datanext p 是最后一個不大于 mink 的元素 if p next 如果還有比 mink 更大的元素 q p next while q datanext q 是第一個不小于 maxk 的元素 p next q Delete Between 6 已知線性表中的元素以值遞增有序排列 并以單鏈表作存儲結構 試設計一個高效的算法 刪除 表中所有值相同的多余元素 使得操作后的線性表中所有元素的值均不相同 同時釋放被刪結點空間 算法分析 1 初始化指針 p 和 q 分別指向鏈表中相鄰的兩個元素 2 當 p next 不為空時 做如下處理 若相鄰兩元素不相等時 p 和 q 都向后推一步 否則 當相鄰元素相等時 刪除多余元素 算法源代碼 void Delete Equal LinkList L p L next q p next p 和 q 指向相鄰的兩個元素 while p next if p data q data 若相鄰兩元素不相等時 p 和 q 都向后推一步 p p next q p next else while q data p data 當相鄰元素相等時刪除多余元素 數據結構上機實驗與習題解析 亱店 打烊 oO 6 r q q q next free r p next q p q q p next else while Delete Equal 7 試設計一個算法 對帶頭結點的單鏈表實現就地逆置 算法分析 1 空表或長度為 1 的表 不做任何處理 2 表長大于 2 時 做如下處理 首先將整個鏈表一分為二 即從鏈表的第一元素結點處斷開 逐個地把剩余鏈表的當前元素 q 插入到鏈表的頭部 算法源代碼 void LinkList reverse LinkList L if L next L next next return p L next q p next s q next p next NULL 從鏈表的第一元素結點處斷開 while s next q next p p q q s s s next 把 L 的元素逐個插入新表表頭 q next p s next q L next s LinkList reverse 8 設線性表 A a1 a2 am 和 B b1 b2 bn 試設計一個按下列規則合并 A B 為 線性表 C 的算法 即使得 C a1 b1 am bm bm 1 bn 當 m n 時 或者 C a1 b1 an bn an 1 am 當 m n 時 線性表 A B 和 C 均以單鏈表作存儲結構 且 C 表利用 A 表和 B 表中的結點空間構成 注意 單鏈 表的長度值 m 和 n 均未顯式存儲 算法分析 1 初始化指針 p 指向鏈表 A 的當前元素 指針 q 指向鏈表 B 的當前元素 2 當鏈表 A 和 B 均為結束時 做如下處理 將 B 的元素插入 若 A 非空 將 A 的元素插入 指針 p 和 q 同時后移 算法源代碼 void merge1 LinkList A LinkList B LinkList C p A next q B next C A while pp next q 將 B 的元素插入 if s t q next q next s 若 A 非空 將 A 的元素插入 p s q t 指針 p 和 q 同時后移 while merge1 9 假設有兩個按元素值遞增有序排列的線性表 A 和 B 均以單鏈表作存儲結構 請設計一個算法將 A 表和 B 表歸并成一個按元素值遞減有序 即非遞增有序 允許表中含有值相同的元素 排列的線性表 C 并要求利用原表 即 A 表和 B 表 的結點空間構造 C 表 算法分析 按從小到大的順序依次把 A 和 B 的元素插入新表的頭部 pc 處 最后處理 A 或 B 的剩 第 2 部分 習題解析 亱店 打烊 oO 7 余元素 算法源代碼 void reverse merge LinkList A LinkList B LinkList C LinkList pa pb pre pa A next pb B next pa 和 pb 分別指向 A 和 B 的當前元素 pre NULL while pa pb if pa datadata pb 將 A 的元素插入新表 pc pa q pa next pa next pre pa q else 將 B 的元素插入新表 pc pb q pb next pb next pre pb q pre pc C A A next pc 構造新表頭 reverse merge 10 已知 A B 和 C 為三個遞增有序的線性表 現要求對 A 表作如下操作 刪去那些既在 B 表中出 現又在 C 表中出現的元素 試對順序表編寫實現上述操作的算法 并分析你的算法的時間復雜度 注意 題中沒有特別指明同一表中的元素值各不相同 算法分析 先從 B 和 C 中找出共有元素 記為 same 再在 A 中從當前位置開始 凡小于 same 的 元素均保留 存到新的位置 等于 same 的就跳過 到大于 same 時就再找下一個 same 算法源代碼 void SqList Intersect Delete SqList A SqList B SqList C i 0 j 0 k 0 m 0 i 指示 A 中元素原來的位置 m 為移動后的位置 while i A length else same B elem j 找到了相同元素 same while B elem j same j while C elem k same k j 和 k 后移到新的元素 while i A length 需保留的元素移動到新位置 while i A length 跳過相同的元素 while while inext NULL 鏈表不為空表 p la next next p 指向第一結點的后繼 la next next NULL 直接插入原則認為第一元素有序 然后從第二元素起依次插入 while p NULL r p next 暫存 p 的后繼 q la while q next NULL 查找插入位置 數據結構上機實驗與習題解析 亱店 打烊 oO 8 p next q next 將 p 結點鏈入鏈表 q next p p r 12 設有一個雙向循環鏈表 每個結點中除有 prior data 和 next 三個域外 還增設了一個訪問頻度 域 freq 在鏈表被起用之前 頻度域 freq 的值均初始化為零 而每當對鏈表進行一次 LOCATE L X 的操作后 被訪問的結點 元素值等于 X 的結點 中的頻度域 freq 的值便增 1 同時調整鏈表中結點之間 的次序 使其按訪問頻度非遞增的次序順序排列 以便始終保持被頻繁訪問的結點總是靠近表頭結點 試 編寫符合上述要求的 LOCATE 操作的算法 算法分析 1 在雙向鏈表中查找數據值為 x 的結點 由指針 p 指向 若找不到 直接返回 否則執行第 2 步 2 修改 x 結點的訪問頻度 freq 并將結點從鏈表上摘下 3 順結點的前驅鏈查找該結點的位置 即找到一個結點的訪問頻度大于 x 結點的訪問頻度 由指針 q 指向 若 q 和 p 不是相鄰結點 調整位置 把 p 插在 q 之后 算法源代碼 DuLNode Locate DuList DuLinkList L int x p L next while p data x if p L return NULL 沒找到 x 結點 p freq p pre next p next p next pre p pre 將 x 結點從鏈表上摘下 q p pre while q freqfreq 查找插入位置 if q p pre 將 x 結點插入 q next pre p p next q next q next p p pre q 調整位置 return p Locate DuList 13 已知三個帶頭結點的線性鏈表 A B 和 C 中的結點均依元素值自小至大非遞減排列 可能存在兩 個以上值相同的結點 編寫算法對 A 表進行如下操作 使操作后的鏈表 A 中僅留下三個表中均包含的數 據元素的結點 且沒有值相同的結點 并釋放所有無用結點 限定算法的時間復雜度為 O m n p 其 中 m n 和 p 分別為三個表的長度 算法分析 留下三個鏈表中公共數據 首先查找兩表 A 和 B 中公共數據 再去 C 中找有無該數據 要消除重復元素 應記住前驅 要求時間復雜度 O m n p 在查找每個鏈表時 指針不能回溯 算法源代碼 LinkList Common LinkList A LinkList B LinkList C pa A next pb B next pc C next pa pb 和 pc 是工作指針 pre A while pa pa pa next free u else if pa data pb data pb pb next else if pa if pc if pc data pa data 處理 pa 結點 后移指針 u pa pa pa next free u else if pre A 結果表中第一個結點 pre next pa pre pa pa pa next else if pre data pa data 重復結點不鏈入 A 表 u pa pa pa next free u 第 2 部分 習題解析 亱店 打烊 oO 9 else pre next pa pre pa pa pa next 將新結點鏈入 A 表 pb pb next pc pc next 鏈表的工作指針后移 else if pa NULL pre next NULL 若 A 表已結束 置 A 表表尾 else 處理原 A 表未到尾而 B 或 C 到尾的情況 pre next NULL 置 A 表表尾標記 while pa NULL 刪除原 A 表剩余元素 u pa pa pa next free u 14 設 head 為一單鏈表的頭指針 單鏈表的每個結點由一個整數域 data 和指針域 next 組成 整數在 單鏈表中是無序的 編一函數 將 head 鏈中結點分成一個奇數鏈和一個偶數鏈 分別由 p q 指向 每個 鏈中的數據按由小到大排列 程序中不得使用 malloc 申請空間 算法分析 本題要求將一個鏈表分解成兩個鏈表 兩個鏈表都要有序 兩鏈表建立過程中不得使用 malloc 申請空間 這就是要利用原鏈表空間 隨著原鏈表的分解 新建鏈表隨之排序 算法源代碼 discreat LinkList p LinkList q LinkList head p NULL q NULL p 和 q 鏈表初始化為空表 s head while s NULL r s next 暫存 s 的后繼 if s data 2 0 處理偶數 if p NULL p s p next NULL 第一個偶數結點 else pre p if pre data s data s next pre p s 插入當前最小值結點 else while pre next NULL if pre next datadata pre pre next 查找插入位置 s next pre next 鏈入結點 pre next s else 處理奇數鏈 if q NULL q s q next NULL 第一奇數結點 else pre q if pre data s data s next pre q s 修改頭指針 else while pre next NULL 查找插入位置 if pre next datadata pre pre next s next pre next 鏈入結點 pre next s 結束奇數鏈結點 s r s 指向新的待排序結點 第 3 章 桟和隊列 3 1 選擇題 1 一個棧的輸入序列為 123 n 若輸出序列的第一個元素是 n 輸出第 i 1 i n 個元素是 A 不確定 B n i 1 C i D n i 答案 B 解析 根據棧的性質 LIFO 若輸出的第一個元素是 n 則表明所有的元素已經入棧 則出棧順 序為 n n 1 3 2 1 2 設棧 S 和隊列 Q 的初始狀態為空 元素 e1 e2 e3 e4 e5 和 e6 依次通過棧 S 一個元素出棧 后即進隊列 Q 若 6 個元素出隊的序列是 e2 e4 e3 e6 e5 e1 則棧 S 的容量至少應該是 A 6 B 4 C 3 D 2 答案 C 解析 根據棧的性質 LIFO 得 e2 出棧前 棧中存有 e1 和 e2 兩個元素 e4 出棧前 棧中存有 e1 e3 和 e4 三個元素 e4 和 e3 出棧以后 e5 和 e6 入棧 棧中同樣存在 e1 e5 和 e6 三個元素 然后三 個元素依次出棧 所以棧的容量至少應該為 3 3 若一個棧以向量 V 1 n 存儲 初始棧頂指針 top 為 n 1 則下面 x 進棧的正確操作是 A top top 1 V top x B V top x top top 1 C top top 1 V top x D V top x top top 1 答案 C 解析 棧式運算受限的線性表 只允許在棧頂進行插入和刪除操作 本題中棧頂指針為 n 1 該數 組將棧頂放在了下標大的一端 所以在進行入棧操作時 top 指針應該進行減一操作 通常元素進棧的操作 為 先移動棧頂指針后存入元素 4 如果我們用數組 A 1 100 來實現一個大小為 100 的棧 并且用變量 top 來指示棧頂 top 的初值為 0 表示棧空 請問在 top 為 100 時 再進行入棧操作 會產生 A 正常動作 B 溢出 C 下溢 D 同步 答案 B 解析 當 top 為 100 時 表示棧已經滿了 此時再進行入棧操作 則會造成溢出 5 棧在 中應用 A 遞歸調用 B 子程序調用 C 表達式求值 D A 答案 D 6 表達式 3 2 4 2 2 6 3 5 求值過程中當掃描到 6 時 對象棧和算符棧為 其中 為乘冪 A 3 2 4 1 1 B 3 2 8 C 3 2 4 2 2 D 3 2 8 答案 D 解析 根據表達式求值的基本思想 在掃描表達式時 依次讀入表達式的每個字符 若是操作數則 進對象棧 若為運算符則和運算符棧的棧頂運算符比較優先級后做相應的操作 7 用鏈接方式存儲的隊列 在進行刪除運算時 A 僅修改頭指針 B 僅修改尾指針 C 頭 尾指針都要修改 D 頭 尾指針可能都要修改 答案 D 解析 若隊列中的元素多于一個 刪除隊列中的隊尾元素 只需修改隊尾指針 若隊列中只有一個 元素 刪除該元素后 隊頭隊尾指針都需要修改 8 循環隊列 A 0 m 1 存放其元素值 用 front 和 rear 分別表示隊頭和隊尾 則當前隊列中的元素 數是 A rear front m m B rear front 1 C rear front 1 D rear front 答案 A 解析 循環隊列是解決假溢出的問題 通常把一維數組看成首尾相接 在循環意義下的求元素個數 的運算可以利用求模運算 9 若用一個大小為 6 的數組來實現循環隊列 且當前 rear 和 front 的值分別為 0 和 3 當從隊列中 刪除一個元素 再加入兩個元素后 rear 和 front 的值分別為多少 數據結構上機實驗與習題解析 亱店 打烊 oO 2 A 1 和 5 B 2 和 4 C 4 和 2 D 5 和 1 答案 B 解析 循環隊列是解決假溢出的問題 通常把一維數組看成首尾相接 在循環意義下的加 1 運算通 常用求模運算來實現 所以入隊和出隊時的操作分別為 rear rear 1 m front front 1 m 10 棧和隊列的共同點是 A 都是先進先出 B 都是先進后出 C 只允許在端點處插入和刪除元素 D 沒有共同點 答案 C 解析 棧和隊列都是運算受限的線性表 只允許在表端點處進行操作 11 在一個鏈隊列中 假定 front 和 rear 分別為隊頭和隊尾指針 則插入 s 結點的操作為 A front next s front s B s next rear rear s C rear next s rear s D s next front front s 答案 C 解析 隊列是運算受限的線性表 FIFO 插入元素只能插在隊尾 所以需修改隊尾指針 12 判定一個棧 S 元素個數最多為 MAXSIZE 為空和滿的條件分別為 A S top 1 S top MAXSIZE 1 B S top 1 S top MAXSIZE 1 C S top 1 S top MAXSIZE 1 D S top 1 S top MAXSIZE 1 答案 B 13 循環順序隊列中是否可以插入下一個元素 A 與隊頭指針和隊尾指針的值有關 B 只與隊尾指針的值有關 與隊頭指針的值無關 C 只與數組大小有關 而與隊頭指針和隊尾指針的值無關 D 與曾經進行過多少次插入操作有關 答案 A 解析 在循環隊列中判斷隊滿的條件為 q rear 1 m q front 是否為真 從中可以看出 與隊頭 指針和隊尾指針的值有關 14 最不適合用作鏈隊的鏈表是 A 只帶隊頭指針的非循環雙鏈表 B 只帶隊頭指針的循環雙鏈表 C 只帶隊尾指針的非循環雙鏈表 D 只帶隊尾指針的循環單鏈表 答案 A 解析 鏈隊是在鏈表的兩端進行操作 而在 A 中查找鏈表最后一個結點的時間復雜度為 O n 15 下列哪中數據結構常用于系統程序的作業調度 A 棧 B 隊列 C 鏈表 D 數組 答案 B 解析 作業調度采用先到先服務的方式 因此最適合的數據結構為隊列 3 2 填空題 1 棧是 的線性表 其運算遵循 的原則 答案 1 操作受限 或限定僅在表尾進行插入和刪除操作 2 后進先出 2 設有一個空棧 棧頂指針為 1000H 十六進制 現有輸入序列為 1 2 3 4 5 經過 PUSH PUSH POP PUSH POP PUSH PUSH 之后 輸出序列是 而棧頂指針值是 H 設棧為順序棧 每個元素占 4 個字節 答案 1 23 2 100CH 解析 PUSH 為入棧操作 POP 為出棧操作 根據棧的性質 經過 PUSH PUSH POP 運算之后 棧 中存在元素 1 輸出數據為 2 然后經過 PUSH POP 3 入棧 3 出棧 然后經過 PUSH PUSH 之后 4 5 入 棧 此時出棧序列為 2 3 棧中元素為 1 4 5 每個元素占 4 個字節 所以棧頂指針的值為 1000H 3 4 100CH 十六進制數 3 循環隊列的引入 目的是為了克服 答案 假溢出時大量移動數據元素 4 隊列是限制插入只能在表的一端 而刪除在表的另一端進行的線性表 其特點是 答案 先進先出 第 2 部分 習題解析 亱店 打烊 oO 3 5 已知鏈隊列的頭尾指針分別是 f 和 r 則將值 x 入隊的操作序列是 答案 s LinkList malloc sizeof LNode s data x s next r next r next s r s 解析 根據隊列的性質 新插入的元素永遠插在隊尾 6 區分循環隊列的滿與空 只有兩種方法 它們是 和 答案 1 犧牲一個存儲單元 2 設標記 7 表達式 23 12 3 2 4 34 5 7 108 9 的后綴表達式是 答案 23 12 3 2 4 34 5 7 108 9 注 表達式中的點 表示將數隔開 如 23 12 3 是三個數 解析 表達式的后綴表達式是將表達式中的運算符寫在兩個操作數之后 轉換原則如下 1 從左到右掃描表達式 若讀到的是操作數 則直接把它輸出 2 若讀到的是運算符 該運算符為左括號 則直接入棧 該運算符為右括號 則輸出棧中運算符 直到遇到左括號為止 該運算符為非括號運算符 則與棧頂元素做優先級比較 若比棧頂元素的優先級高或相等 則直接入棧 若比棧頂元素的優先級低 則輸出棧頂元素 3 當表達式掃描完后棧中還有運算符 則依次輸出運算符 直到棧空 8 用下標 0 開始的 N 元數組實現循環隊列時 為實現下標變量 M 加 1 后在數組有效下標范圍內循 環 可采用的表達式是 M 答案 M 1 N 解析 循環隊列是解決假溢出的問題 通常把一維數組看成首尾相接 在循環意義下的加 1 運算通 常用求模運算來實現 9 當兩個棧共享一存儲區時 棧利用一維數組 stack 1 n 表示 兩棧頂指針為 top 1 與 top 2 則當 棧 1 空時 top 1 為 棧 2 空時 top 2 為 棧滿時為 答案 1 0 2 n 1 3 top 1 1 top 2 解析 為了增加內存空間的利用率和減少溢出的可能性 由兩個棧共享一片連續的內存空間時 應將 兩棧的棧頂分別設在這片內存空間的兩端 這樣 當兩個棧的棧頂在棧空間的某一位置相遇時 才產生上溢 即 top 1 1 top 2 10 在作進棧運算時應先判別棧是否 在作退棧運算時應先判別棧是否 當棧中元素為 n 個 作進棧運算時發生上溢 則說明該棧的最大容量為 為了增加內存空間的利用率和減少溢出的可能性 由兩個棧共享一片連續的空間時 應將兩棧的 分別設在內存空間的兩端 這樣只有當 時才產生溢出 答案 1 滿 2 空 3 n 4 棧底 5 兩棧頂指針相鄰 11 在 Q 的鏈隊列中 判斷只有一個結點的條件是 答案 Q front NULL 注 算法中可調用棧操作的基本算法 算法分析 判斷表達式中括號是否匹配 可通過棧 簡單說是左括號時進棧 右括號時退棧 退棧 時 若棧頂元素是左括號 則新讀入的右括號與棧頂左括號就可消去 如此下去 輸入表達式結束時 棧 為空則正確 否則括號不匹配 算法源代碼 int EXYX char E E 存放字符串表達式 以 結束 char s 30 s 是一維數組 容量足夠大 用作存放括號的棧 int top 0 i top 用作棧頂指針 s top 先入棧 用于和表達式結束符號 匹配 i 0 字符數組 E 的工作指針 while E i 逐字符處理字符表達式的數組 switch E i case s top i break case if s top top i break else printf 括號不配對 exit 0 case if s top printf 括號配對 n return 1 else printf 括號不配對 n return 0 括號不配對 default i 讀入其它字符 不作處理 算法結束 2 假設以帶頭結點的循環鏈表表示隊列 并且只設一個指針指向隊尾結點 但不設頭指針 請寫出 相應的入隊列和出隊列算法 算法分析 根據隊列的先進先出的性質 隊列的入隊操作在隊尾進行 出隊操作在隊頭進行 而題目所采用的數 據結構是只設一個尾指針的循環鏈表 我們可以根據循環鏈表的特點找到頭指針 算法源代碼 1 void EnQueue LinkList rear ElemType x rear 是帶頭結點的循環鏈隊列的尾指針 本算法將元素 x 插入到隊尾 s LinkList malloc sizeof LNode 申請結點空間 s data x s next rear next 將 s 結點鏈入隊尾 rear next s rear s rear 指向新隊尾 算法源代碼 2 void DeQueue LinkList rear rear 是帶頭結點的循環鏈隊列的尾指針 本算法執行出隊操作 操作成功輸出隊頭元素 否則給出出錯信息 if rear next rear printf 隊空 n exit 0 s rear next next s 指向隊頭元素 rear next next s next 隊頭元素出隊 printf 出隊元素是 d s data if s rear rear rear next 空隊列 free s 3 設整數序列 a1 a2 an 給出求解最大值的遞歸程序 數據結構上機實驗與習題解析 亱店 打烊 oO 6 算法分析 根據題意 本題的函數定義為 a 1 n 1 maxvalue a n a n a n maxvalue a n 1 maxvalue a n 1 a n MaxValue a n 1 max a n else max MaxValue a n 1 return max 4 試將下列遞歸函數改寫為非遞歸函數 void test int sum int x scanf d if x 0 sum 0 else test sum x printf 5d sum 算法分析 該函數是以讀入數據的順序為相反順序進行累加問題 可將讀入數據放入棧中 等輸入結束時 將棧 中數據退出進行累加 累加的初值為 0 算法源代碼 int test int x sum 0 top 0 s 30 scanf d while x 0 s top a scanf d printf 5d sum while top sum s top printf 5d sum 5 編寫一個算法 利用棧的基本運算將指定棧中的內容進行逆轉 算法分析 利用兩個臨時棧 s1 和 s2 先將 s 棧中的內容移到 s1 棧中 再將 s1 棧中的內容移到 s2 棧中 最后將 s2 棧中的內容移到 s 棧中 即可實現 算法源代碼 reverse SqStack s SqStack s1 s2 s s1 s2 均為棧類型 ElemType x 棧中元素的類型 用于存儲從棧中取出元素的臨時變量 initstack s1 棧的初始化 initstack s2 while stackempty s 如果棧不空 將 s 棧中的內容移到 s1 棧中 pop s x 取棧頂元素放入變量 x 中 push s1 x 將變量 x 入棧 while stackempty s1 如果棧不空 將 s1 棧中的內容移到 s2 棧中 pop s1 x push s2 x while stackempty s2 如果棧不空 將 s2 棧中的內容移到 s 棧中 第 2 部分 習題解析 亱店 打烊 oO 7 pop s2 x push s x 6 假設循環隊列中只設 rear 和 length 來分別指示隊尾元素的位置和隊中元素的個數 試給出判別此 循環隊列的隊滿條件 并寫出相應的入隊和出隊算法 要求出隊時需返回隊頭元素 算法分析 該題的關鍵問題是如何確定頭指針 根據為指針 rear 和元素個數 length 很容易確定頭指針 front rear length MAXSIZE MAXSIZE 算法源代碼 define MAXQSIZE 100 最大隊列長度 typedef int ElemType typedef struct ElemType data MAXSIZE 隊列存儲空間 int rear 尾指針 若隊列不空 指向隊列尾元素 int length 隊列內含元素的個數 CyQueue int FullQueue CyQueue Q 判隊滿 隊中元素個數等于空間大小 return Q length Maxsize void EnQueue CyQueue Q ElemType x 入隊 if FullQueue Q printf 隊已滿 無法入隊 return Q Data Q rear x Q rear Q rear 1 MAXSIZE 在循環意義上的加 1 Q length ElemType DeQueue CyQueue Q 出隊 int front 設一個臨時隊頭指針 if Q length 0 Error 隊已空 無元素可出隊 front Q rear MAXSIZE Q length MAXSIZE Q length return Q Data front 7 一個雙向棧 S 是在同一向量空間內實現的兩個棧 它們的棧底分別設在向量空間的兩端 試為此 雙向棧設計初始化 InitStack S 入棧 Push S i x 和出棧 Pop S i 等算法 其中 i 為 0 或 1 用以表 示棧號 算法分析 雙向棧其實和單向棧原理相同 只是在一個向量空間內 好比是兩個頭對頭的棧放在一起 中間的空 間可以充分利用 算法源代碼 void InitStack DuStack S 初始化雙向棧 S top 0 1 S top 1 STACKSIZE int EmptyStack DuStack S int i 判棧空 棧號 i return i 0 int FullStack DuStack S 判棧滿 滿時肯定兩頭相遇 return S top 0 S top1 1 數據結構上機實驗與習題解析 亱店 打烊 oO 8 void Push DuStack S int i ElemType x 進棧 棧號 i if FullStack S Error Stack overflow 上溢 退出運行 if i 0 S Data S top0 x 棧 0 入棧 if i 1 S Data S top 1 x 棧 1 入棧 ElemType Pop DuStack S int i 出棧 棧號 i if EmptyStack S i Error Stack underflow 下溢退出 if i 0 return S Data S top0 返回棧頂元素 指針值減 1 if i 1 return S Data S top 1 該棧是以另一端為底的 所以指針加 1 8 回文是指正讀反讀均相同的字符序列 如 abba 和 abdba 均是回文 但 good 不是回文 設計一 個算法判定給定的字符向量是否為回文 提示 將一半字符入棧 算法源代碼 void sympthy LinkList head stack s 判斷長為 n 的字符串是否中心對稱 int i 1 LinkList p head next while idata p p next if n 2 0 p p next 奇數個結點時跳過中心結點 while p if p NULL printf 鏈表中心對稱 else printf 鏈表不是中心對稱 算法結束 9 用標志位方式設計出在循環隊列中進行插入和刪除運算的算法 算法分析 可引入標志位 flag 且規定當 flag 0 時表示隊列空 當 flag 1 時表示隊列非空 同時設 front rear 和 MAXSIZE 分別為隊頭指針 隊尾指針和隊列的長度 其中 隊頭指針指向隊頭元素所在的實際存儲單元 的前一個位置 隊尾指針指向隊尾元素所在的位置 從而可得隊滿的條件是 rear front 設置全局變量 flag 作為標志位 enqueue SqQueue sq ElemType x 將 x 插入循環隊列 sq 中 sq 具有隊頭和隊尾指針 if flag 1 else sq rear sq rear 1 MAXSIZE sq data sq rear x if flag 0 flag 1 ElemType dequeue SqQueue sq 刪除隊列 sq 的隊頭元素 并返回該元素 ElemType x if flag 0 printf queue is empty n 判斷隊空 else sq front sq front 1 MAXSIZE x sq data sq front 第 2 部分 習題解析 亱店 打烊 oO 9 if sq front sq rear flag 0 return x 第 4 章 串 4 1 選擇題 1 下面關于串的的敘述中 哪一個是不正確的 A 串是字符的有限序列 B 空串是由空格構成的串 C 模式匹配是串的一種重要運算 D 串既可以采用順序存儲 也可以采用鏈式存儲 答案 B 解析 空串是不含任何字符的串 即空串的長度是零 空格串是由空格組成的串 其長度等于空格 的個數 2 設有兩個串 p 和 q 其中 q 是 p 的子串 求 q 在 p 中首