廈門理工學(xué)院-c語言數(shù)據(jù)結(jié)構(gòu)-級數(shù)據(jù)結(jié)構(gòu)期末試卷-A

第 1 頁 共 8 頁 廈門理工學(xué)院期末考試卷廈門理工學(xué)院期末考試卷 2011 2012 學(xué)年 第一學(xué)期 課程名稱數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法 試卷 卷別 A B 專業(yè)專業(yè) 10 級級 班級班級 考試 方式 閉卷 開卷 本試卷共本試卷共 四四 大題大題 4 頁頁 滿分 滿分 100 分 考試時間分 考試時間 120 分鐘 分鐘 請在答題紙上作答 在試卷上作答無效 請在答題紙上作答 在試卷上作答無效 考考 生生 信信 息息 欄欄 系 專業(yè) 10 級 班級 姓名 學(xué)號 裝 訂 線 一 選擇題 本題共一 選擇題 本題共 20 小題 每題小題 每題 2 分 共分 共 40 分 分 1 對數(shù)據(jù)結(jié)構(gòu) 下列結(jié)論中不正確的是 對數(shù)據(jù)結(jié)構(gòu) 下列結(jié)論中不正確的是 A 相同的邏輯結(jié)構(gòu) 對應(yīng)的存儲結(jié)構(gòu)也必相同 相同的邏輯結(jié)構(gòu) 對應(yīng)的存儲結(jié)構(gòu)也必相同 B 數(shù)據(jù)結(jié)構(gòu)由邏輯結(jié)構(gòu) 存儲結(jié)構(gòu)和基本操作數(shù)據(jù)結(jié)構(gòu)由邏輯結(jié)構(gòu) 存儲結(jié)構(gòu)和基本操作 3 個方面組成個方面組成 C 數(shù)據(jù)存儲結(jié)構(gòu)就是數(shù)據(jù)邏輯結(jié)構(gòu)的機(jī)內(nèi)的實現(xiàn)數(shù)據(jù)存儲結(jié)構(gòu)就是數(shù)據(jù)邏輯結(jié)構(gòu)的機(jī)內(nèi)的實現(xiàn) D 對數(shù)據(jù)基本操作的實現(xiàn)與存儲結(jié)構(gòu)有關(guān)對數(shù)據(jù)基本操作的實現(xiàn)與存儲結(jié)構(gòu)有關(guān) 2 下面程序的時間復(fù)雜度為 下面程序的時間復(fù)雜度為 for int i 0 i m i for int j 0 jnext NULL B p next next H C p data 0 D p next H 5 若要在若要在 O 1 的時間復(fù)雜度上實現(xiàn)兩個循環(huán)鏈表表頭尾相接 則對應(yīng)兩個循的時間復(fù)雜度上實現(xiàn)兩個循環(huán)鏈表表頭尾相接 則對應(yīng)兩個循 環(huán)鏈表各設(shè)置一個指針 分別指向 環(huán)鏈表各設(shè)置一個指針 分別指向 A 各自的頭節(jié)點各自的頭節(jié)點 B 各自的尾節(jié)點各自的尾節(jié)點 C 各自的第一個元素節(jié)點各自的第一個元素節(jié)點 D 一個表的頭節(jié)點 另一個表的尾節(jié)點一個表的頭節(jié)點 另一個表的尾節(jié)點 6 一個鏈隊列中 假設(shè)一個鏈隊列中 假設(shè) f 和分別為隊首和隊尾指針 則插入和分別為隊首和隊尾指針 則插入 s 所指節(jié)點的運(yùn)所指節(jié)點的運(yùn) 算是 算是 A f next s f s B r next s r s C s next r r s D s next f f s 第 2 頁 共 8 頁 7 在雙向鏈表中刪除指針在雙向鏈表中刪除指針 p 所指的節(jié)點時需要修改指針 所指的節(jié)點時需要修改指針 A p llink rlink p rlink p rlink llink p llink B p llink p llink llink p llink rlink p C p rlink llink p p rlink p rlink rlink D p rlink p llink llink p llink p rlink rlink 8 設(shè)棧設(shè)棧 s 和隊列和隊列 q 的初始狀態(tài)為空 的初始狀態(tài)為空 6 個元素入棧的順序為 個元素入棧的順序為 a1 a2 a3 a4 a5 a6 一個元素出棧之 一個元素出棧之 后立即入隊列后立即入隊列 q 若 若 6 個元素出對的順序是 個元素出對的順序是 a2 a4 a3 a6 a5 a1 則棧 則棧 s 的容量至少應(yīng)該是 的容量至少應(yīng)該是 A 2 B 3 C 4 D 6 9 向一個棧頂指針為向一個棧頂指針為 top 的鏈棧中插入一個的鏈棧中插入一個 s 節(jié)點 則執(zhí)行 節(jié)點 則執(zhí)行 A top next s B s next top next top next s C s next top top s D s next top top top next 10 循環(huán)隊列用數(shù)組循環(huán)隊列用數(shù)組 V 0 m 1 存放其元素值 已知其頭 尾指針分別是存放其元素值 已知其頭 尾指針分別是 f 和和 r 則當(dāng)前隊列中的元 則當(dāng)前隊列中的元 素個數(shù)是 素個數(shù)是 A A r f m m B r f 1 C r f m 1 m D r f m 1 m 11 單循環(huán)鏈表表示的隊列長度為單循環(huán)鏈表表示的隊列長度為 n 若只設(shè)頭指針 則進(jìn)隊的時間復(fù)雜度為 若只設(shè)頭指針 則進(jìn)隊的時間復(fù)雜度為 A O n B O 1 C O n2 D O nlogn 12 已知循環(huán)隊列的存儲空間為數(shù)組已知循環(huán)隊列的存儲空間為數(shù)組 a 21 且當(dāng)前隊列的頭指針和尾指針的值分別是 且當(dāng)前隊列的頭指針和尾指針的值分別是 8 和和 3 則該 則該 隊列的當(dāng)前長度為 隊列的當(dāng)前長度為 A 5 B 6 C 16 D 17 13 一棵樹共有一棵樹共有 n 個節(jié)點的數(shù) 其中所有分支節(jié)點的度均為個節(jié)點的數(shù) 其中所有分支節(jié)點的度均為 k 則該數(shù)中葉子節(jié)點的個數(shù)為 則該數(shù)中葉子節(jié)點的個數(shù)為 A n k 1 k B n k C n 1 k D nk n 1 k 14 若一棵二叉樹有若一棵二叉樹有 1001 個節(jié)點 且無度為個節(jié)點 且無度為 1 的節(jié)點 則葉子節(jié)點的個數(shù)為 的節(jié)點 則葉子節(jié)點的個數(shù)為 A 498 B 499 C 500 D 501 15 樹中所有節(jié)點的度等于所有節(jié)點數(shù)加 樹中所有節(jié)點的度等于所有節(jié)點數(shù)加 A 0 B 1 C 1 D 2 16 設(shè)高度為設(shè)高度為 h 的二叉樹只有度為的二叉樹只有度為 0 和度為和度為 2 的節(jié)點 則此類二叉樹中所包含的節(jié)點數(shù)至少為的節(jié)點 則此類二叉樹中所包含的節(jié)點數(shù)至少為 A 2h B 2h 1 C 2h 1 D h 1 17 設(shè)某二叉樹的前序序列為設(shè)某二叉樹的前序序列為 abdcef 中序為 中序為 dbaecf 則此二叉樹的后序為 則此二叉樹的后序為 A dbefca B debfca C dfebca D dbfeca 18 線索二叉樹中的線索是指 線索二叉樹中的線索是指 A 左孩子左孩子 B 右孩子右孩子 C 遍歷遍歷 D 指針指針 19 具有具有 10 個頂點的無向圖最多有 個頂點的無向圖最多有 條邊 條邊 A 0 B 9 C 10 D 45 20 對對 AOE 網(wǎng)的關(guān)鍵路徑 下面的說法 網(wǎng)的關(guān)鍵路徑 下面的說法 是正確的 是正確的 A 提高關(guān)鍵路徑上的一個關(guān)鍵活動的速度 必然使得整個工期縮短 提高關(guān)鍵路徑上的一個關(guān)鍵活動的速度 必然使得整個工期縮短 B 完成工程的最短時間是從始點到終點的最短路徑的長度 完成工程的最短時間是從始點到終點的最短路徑的長度 C 一個 一個 AOE 網(wǎng)的關(guān)鍵路徑只有一條 但關(guān)鍵路徑活動可有多個網(wǎng)的關(guān)鍵路徑只有一條 但關(guān)鍵路徑活動可有多個 第 3 頁 共 8 頁 D 任何一項活動持續(xù)時間的改變都可能會影響關(guān)鍵路徑的改變 任何一項活動持續(xù)時間的改變都可能會影響關(guān)鍵路徑的改變 第 4 頁 共 8 頁 考考 生生 信信 息息 欄欄 系系 專業(yè)專業(yè) 10 級級 班級班級 姓名姓名 學(xué)號學(xué)號 裝裝 訂訂 線線 二 分析運(yùn)算題 本題共二 分析運(yùn)算題 本題共 6 小題 每題小題 每題 6 分 共分 共 36 分 分 1 如果輸入序列為如果輸入序列為 6 5 4 3 2 1 試問能否通過棧結(jié)構(gòu)得到以下兩個序列試問能否通過棧結(jié)構(gòu)得到以下兩個序列 3 4 6 5 2 1 和和 2 3 4 1 5 6 請說明為什么不能或如何才能得到請說明為什么不能或如何才能得到 2 請寫出圖請寫出圖 1 中二叉樹的前序中二叉樹的前序 先序先序 和中序遍歷序列 和中序遍歷序列 圖圖 1 圖圖 2 3 算術(shù)表達(dá)式如下 算術(shù)表達(dá)式如下 a b c d 用二叉樹表示算術(shù)表達(dá)式用二叉樹表示算術(shù)表達(dá)式 寫出后序 后綴 表達(dá)式寫出后序 后綴 表達(dá)式 4 請寫出無向圖圖請寫出無向圖圖 2 中頂點中頂點 a f 的度 的度 5 給定元素序列 給定元素序列 50 25 80 20 76 93 畫出按照該序列構(gòu)造的二 畫出按照該序列構(gòu)造的二 叉排序樹叉排序樹 必須畫出二叉排序樹的建樹過程必須畫出二叉排序樹的建樹過程 6 下面的鄰接表表示一個給定的無向圖下面的鄰接表表示一個給定的無向圖 請根據(jù)鄰接表畫出無向圖請根據(jù)鄰接表畫出無向圖 給出從頂點給出從頂點 v1 開始開始 根據(jù)鄰接表對圖用深度優(yōu)先搜索法進(jìn)行遍歷時的根據(jù)鄰接表對圖用深度優(yōu)先搜索法進(jìn)行遍歷時的 頂點序列 頂點序列 給出從頂點給出從頂點 v1 開始開始 根據(jù)鄰接表對圖用廣度優(yōu)先搜索法進(jìn)行遍歷時的根據(jù)鄰接表對圖用廣度優(yōu)先搜索法進(jìn)行遍歷時的 頂點序列 頂點序列 第 5 頁 共 8 頁 三 程序填空題 本題共三 程序填空題 本題共 5 空 每空空 每空 2 分 分 共共 10 分 分 鏈?zhǔn)奖肀硎竞蛯崿F(xiàn)線性表的部分程序如下 請在鏈?zhǔn)奖肀硎竞蛯崿F(xiàn)線性表的部分程序如下 請在 程序空白處填上適當(dāng)?shù)恼Z句 程序空白處填上適當(dāng)?shù)恼Z句 線性表的單鏈表存儲結(jié)構(gòu)線性表的單鏈表存儲結(jié)構(gòu) typedef struct LNode ElemType data struct LNode next LNode LinkList 帶頭結(jié)點的單鏈表帶頭結(jié)點的單鏈表 L 中第中第 i 個位置之前插入元個位置之前插入元 素素 e int ListInsert L LinkList int j j 為計數(shù)器為計數(shù)器 p L p 指向指向 L 的頭節(jié)點的頭節(jié)點 j 0 while p s LinkList sizeof LNode 生成新結(jié)點生成新結(jié)點 s e 使新結(jié)點數(shù)據(jù)域的使新結(jié)點數(shù)據(jù)域的 值為值為 e 將新結(jié)點插入到單鏈表將新結(jié)點插入到單鏈表 L 中中 修改第修改第 i 1 個結(jié)點指針個結(jié)點指針 return OK 四 算法設(shè)計題 本題共四 算法設(shè)計題 本題共 1 小題 每題小題 每題 14 分 共分 共 14 分 分 1 如果通訊字符如果通訊字符 a b c d 出現(xiàn)頻度分別為出現(xiàn)頻度分別為 7 5 2 4 某同學(xué)設(shè)計了如下程序 請根據(jù)程序畫出對應(yīng)某同學(xué)設(shè)計了如下程序 請根據(jù)程序畫出對應(yīng) 的二叉樹 計算所畫出的二叉樹的帶權(quán)路徑長度的二叉樹 計算所畫出的二叉樹的帶權(quán)路徑長度 必須寫出計算過程 否則不給分 必須寫出計算過程 否則不給分 if input c printf c c else if input d printf c d else if input a printf c a else printf c b 請畫出赫夫曼 哈弗曼 樹請畫出赫夫曼 哈弗曼 樹 必須畫出赫夫曼必須畫出赫夫曼 樹的建樹過程樹的建樹過程 計算赫夫曼樹的帶權(quán)路徑長度 必須寫出計算計算赫夫曼樹的帶權(quán)路徑長度 必須寫出計算 過程 否則不給分 過程 否則不給分 根據(jù)赫夫曼樹 用根據(jù)赫夫曼樹 用 if else 語句修改語句修改 中的程序 中的程序 寫出最佳判定算法 寫出最佳判定算法 第 6 頁 共 8 頁 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法 A 卷答案卷答案 一 選擇題選擇題 本題共 本題共 2020 小題 每題小題 每題 2 2 分 分 共共 4040 分 分 1 A2 B3 D4 D5 B6 B7 A8 B9 C10 A 11 A12 C13 D14 D15 C16 C17 A18 D19 D20 D 二 分析運(yùn)算題 本題共二 分析運(yùn)算題 本題共 6 小題 每題小題 每題 6 分 共分 共 36 分 分 1 如果輸入序列為如果輸入序列為 6 5 4 3 2 1 試問能否通過棧試問能否通過棧 結(jié)構(gòu)得到以下兩個序列結(jié)構(gòu)得到以下兩個序列 3 4 6 5 2 1 和和 2 3 4 1 5 6 請說明為什么不能或如何才能得到請說明為什么不能或如何才能得到 輸出序列 2 3 4 1 5 6 可以得到 2 分 輸出序列 3 4 6 5 2 1 不能得到 2 分 其理由是 輸出序列中間兩元素是 6 5 前面 2 個元素 3 4 得到后 棧中元素剩 6 5 且 5 在棧頂 不可能棧底元素 6 在棧頂元素 5 之前出 棧 2 分 2 請寫出圖中二叉樹的前序請寫出圖中二叉樹的前序 先序先序 和中序遍歷和中序遍歷 序列 序列 前序 先序 ABDCEF 3 分 中序 DBAECF 3 分 3 算術(shù)表達(dá)式如下 算術(shù)表達(dá)式如下 a b c d 用二叉樹表示算術(shù)表達(dá)式用二叉樹表示算術(shù)表達(dá)式 寫出后序 后綴 表達(dá)式寫出后序 后綴 表達(dá)式 d a bc 3 分 后序 后綴 表達(dá)式 abc d 3 分 4 請寫出無向圖中頂點請寫出無向圖中頂點 a f 的度的度 a 3 1 分 b 2 1 分 c 1 1 分 d 2 1 分 e 4 1 分 f 2 1 分 5 給定元素序列 給定元素序列 50 25 80 20 76 93 畫出按照該序列 畫出按照該序列 構(gòu)造的二叉排序樹構(gòu)造的二叉排序樹 必須畫出二叉排序樹的建樹必須畫出二叉排序樹的建樹 過程過程 每個結(jié)點 1 分 6 下面的鄰接表表示一個給定的無向圖下面的鄰接表表示一個給定的無向圖 請根據(jù)鄰接表畫出無向圖請根據(jù)鄰接表畫出無向圖 給出從頂點給出從頂點 v1 開始開始 根據(jù)鄰接表對圖根據(jù)鄰接表對圖 用深度優(yōu)先搜索法進(jìn)行遍歷時的頂點序列 用深度優(yōu)先搜索法進(jìn)行遍歷時的頂點序列 50 2580 76 93 20 第 7 頁 共 8 頁 給出從頂點給出從頂點 v1 開始開始 根據(jù)鄰接表對圖用廣根據(jù)鄰接表對圖用廣 度優(yōu)先搜索法進(jìn)行遍歷時的頂點序列 度優(yōu)先搜索法進(jìn)行遍歷時的頂點序列 V5 V3 V1 V4 V6 V2 2 分 深度序列 V1 V2 V5 V3 V4 V6 2 分 廣度序列 V1 V2 V3 V4 V5 V6 2 分 三 程序填空題 本題共三 程序填空題 本題共 5 空 每空空 每空 2 分 分 共共 10 分 分 p next 2 分 malloc 2 分 data 2 分 s next p ne