專升本數(shù)據(jù)結(jié)構(gòu)試題解析

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