【精品】數(shù)據(jù)結(jié)構(gòu)答疑材料

精品精品 數(shù)據(jù)結(jié)構(gòu)答疑材料數(shù)據(jù)結(jié)構(gòu)答疑材料 數(shù)據(jù)結(jié)構(gòu)答疑材料 1 數(shù)據(jù)結(jié)構(gòu)是一門(mén)研究 的程序設(shè)計(jì)問(wèn)題中計(jì)算機(jī)的操作對(duì)象 以及它們之間的關(guān)系和運(yùn)算等的學(xué)科 A 數(shù)值B 非數(shù)值C 字符D 數(shù)字答案B 2 快速排序的分區(qū)結(jié)果唯一嗎 答案不唯一 取決于樞軸元素的選 取 3 小頂堆的堆頂元素是序列中 A 最大的元素B 次大的元素C 最小的元素D 次小的元素答案C 4 設(shè)s1 GOOD s2 BYE 則字符串s1和s2連接后的結(jié)果是 a BYE GOODb GOOD BYEc BYEDGOOD d GOODBYE答案d 5 在一個(gè)單鏈表中 已知p所指結(jié)點(diǎn) 若在p之后插入s結(jié)點(diǎn) 則執(zhí) 行 答案s next p next p next s6 數(shù)據(jù)的邏輯結(jié)構(gòu)中非線(xiàn)性結(jié)構(gòu)有A 集合B 線(xiàn)形結(jié)構(gòu)C 樹(shù)形結(jié)構(gòu)D 網(wǎng)狀結(jié)構(gòu)E 鏈?zhǔn)浇Y(jié)構(gòu)答案C樹(shù)形結(jié)構(gòu) D網(wǎng)狀結(jié)構(gòu)7 線(xiàn) 性結(jié)構(gòu)中元素之間存在 關(guān)系 樹(shù)形結(jié)構(gòu)中元素之間存在 關(guān) 系 圖形結(jié)構(gòu)中元素之間存在 關(guān)系A(chǔ) 一對(duì)一 多對(duì)多 一 對(duì)多B 一對(duì)多 一對(duì)一 多對(duì)多C 一對(duì)一 一對(duì)多 多對(duì)多D 多 對(duì)多 一對(duì)多 一對(duì)一E 以上都不正確答案C 一對(duì)一 一對(duì)多 多對(duì)多8 廣義表 a a 的表尾是 A a B b C a D a 答案C9 算法有哪些重要特性 答案1 有窮性2 確定性3 可行性4 有輸入5 有輸出10 數(shù)據(jù)結(jié)構(gòu)是一門(mén)研究什么 內(nèi)容的學(xué)科 答案數(shù)據(jù)結(jié)構(gòu)是一門(mén)研究在非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn) 題中 計(jì)算機(jī)的操作對(duì)象及對(duì)象間的關(guān)系和施加于對(duì)象的操作等的 學(xué)科 11 設(shè)有一個(gè)空棧 現(xiàn)在有輸入序列 1 2 3 4 5 經(jīng)過(guò)push push pop push pop push push pop pop pop后 輸出序列是 a 1 2 3 4 5b 2 3 5 4 1c 5 4 3 2 1d 1 3 4 2 5答案b 2 3 5 4 1解析1 2進(jìn)棧 最先出棧的肯定是2 12 兩個(gè)串相等的條件是A 長(zhǎng)度相等B 對(duì)應(yīng)位置的字符相等C 存 儲(chǔ)位置相同D 存儲(chǔ)結(jié)構(gòu)相同E 以上都是答案AB13 順序查找適用 于存儲(chǔ)結(jié)構(gòu)為 的線(xiàn)性表A 散列B 順序或者鏈?zhǔn)紺 壓縮D 索引答案B14 設(shè)哈希表長(zhǎng)m 16 哈希函數(shù)H key key 13 表中 已有3個(gè)結(jié)點(diǎn)H 19 6H 27 1H 23 10其余地址為空 如用線(xiàn)性探測(cè)再散列處理沖突 關(guān)鍵字14的 地址是選項(xiàng) a 1b 2c 3d 0e 以上都不正確答案b解析14 13 1 因?yàn)?地址中已經(jīng)有元素 所以需要再哈希求地址 14 1 13 21 5 最常用的哈希函數(shù)構(gòu)造方法為A 除留余數(shù)法B 直接定址法C 折疊法D 數(shù)字分析法答案A16 一個(gè)鏈?zhǔn)疥?duì)列中 假設(shè)f和r分別為 隊(duì)首和隊(duì)尾指針 則插入s所指結(jié)點(diǎn)的運(yùn)算是 A r next s B r s C s r D s r next E s next r答案AB17 廣義表L a x y x 的長(zhǎng)度是 深 度是 A 33B C D E 答案A 33解析 廣義表LS中的直接元素的個(gè)數(shù)稱(chēng)為L(zhǎng)S的長(zhǎng)度 廣義表LS中括號(hào)的最大 嵌套層數(shù)稱(chēng)為L(zhǎng)S的深度 18 在一個(gè)單鏈表中 已知p所指結(jié)點(diǎn) 若在p之后插入s結(jié)點(diǎn) 則執(zhí) 行 A s next p next B p next s C p next s next D p next s E p next p next next答案AB19 順序棧S為空的判定條件a S top S base b S S base c S top S d 沒(méi)有正確答案答案a 20 什么叫循環(huán)隊(duì)列如何區(qū)分空滿(mǎn)循環(huán)隊(duì)列 當(dāng)隊(duì)列采用順序存儲(chǔ)結(jié) 構(gòu)表示時(shí) 為避免空間浪費(fèi)問(wèn)題發(fā)生 便提出了循環(huán)隊(duì)列 相當(dāng)于 把順序隊(duì)列頭尾相接形成一個(gè)環(huán)狀空間 判斷循環(huán)隊(duì)列是空還是滿(mǎn) 通常有兩種處理方法其一是在存儲(chǔ)區(qū)域 中占用一個(gè)元素空間設(shè)一個(gè)標(biāo)志位以區(qū)別隊(duì)列是空還是滿(mǎn) 其二是 少用一個(gè)元素空間 約定以 隊(duì)列頭指針在隊(duì)列尾指針的下一位置 指環(huán)狀的下一位置 上 作為隊(duì)列呈滿(mǎn)狀態(tài)的標(biāo)志 通常采用第二種方法 21 一個(gè)隊(duì)列的入隊(duì)序列是 1 3 4 2 則隊(duì)列的首次輸出元素是 A 3B 2C 1D 4答案C22 計(jì)算機(jī)算法指的是 1 它必須具備 2 這三個(gè)特性 1 A 計(jì)算方法B 排序方法C 解決問(wèn)題的步驟序列D 調(diào)度方法 2 A 可執(zhí)行性 可移植性 可擴(kuò)充性B 可執(zhí)行性 確定性 有窮 性C 確定性 有窮性 穩(wěn)定性D 易讀性 穩(wěn)定性 安全性答案C B 2 3 從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為 兩大類(lèi) A 動(dòng)態(tài)結(jié)構(gòu) 靜態(tài)結(jié)構(gòu)B 順序結(jié)構(gòu) 鏈?zhǔn)浇Y(jié)構(gòu)C 線(xiàn)性結(jié)構(gòu) 非線(xiàn) 性結(jié)構(gòu)D 初等結(jié)構(gòu) 構(gòu)造型結(jié)構(gòu)答案C 24 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)由哪 四種基本的存儲(chǔ)方法實(shí)現(xiàn) 答案四種表示方法 1 順序存儲(chǔ)方式 數(shù)據(jù)元素順序存放 每個(gè)存儲(chǔ)結(jié)點(diǎn)只含一個(gè)元素 存儲(chǔ)位置反映數(shù)據(jù)元素間的邏輯關(guān)系 存儲(chǔ)密度大 但有些操作 如插入 刪除 效率較差 2 鏈?zhǔn)酱鎯?chǔ)方式 每個(gè)存儲(chǔ)結(jié)點(diǎn)除包含數(shù)據(jù)元素信息外還包含一組 至少一個(gè) 指針 指針?lè)从硵?shù)據(jù)元素間的邏輯關(guān)系 這種方式不要求存儲(chǔ)空間連續(xù) 便于動(dòng)態(tài)操作 如插入 刪除等 但存儲(chǔ)空間開(kāi)銷(xiāo)大 用于指針 另外不能折半查找等 3 索引存儲(chǔ)方式 除數(shù)據(jù)元素存儲(chǔ)在一地址連續(xù)的內(nèi)存空間外 尚需建立一個(gè)索引表 索引表中索引指示存儲(chǔ)結(jié)點(diǎn)的存儲(chǔ)位置 下標(biāo) 或存儲(chǔ)區(qū)間端點(diǎn) 下標(biāo) 兼有靜態(tài)和動(dòng)態(tài)特性 4 散列存儲(chǔ)方式 通過(guò)散列函數(shù)和解決沖突的方法 將關(guān)鍵字散列在連續(xù)的有限的地 址空間內(nèi) 并將散列函數(shù)的值解釋成關(guān)鍵字所在元素的存儲(chǔ)地址 這種存儲(chǔ)方式稱(chēng)為散列存儲(chǔ) 其特點(diǎn)是存取速度快 只能按關(guān)鍵字隨機(jī)存取 不能順序存取 也 不能折半存取 25 線(xiàn)性表是具有n個(gè) 的有限序列 n 0 A 表元素B 字符C 數(shù)據(jù)元素D 數(shù)據(jù)項(xiàng)E 信息項(xiàng)答案C26 若長(zhǎng) 度為n的線(xiàn)性表采用順序存儲(chǔ)結(jié)構(gòu) 在其第i個(gè)位置插入一個(gè)新元素 的算法的時(shí)間復(fù)雜度為 1 i n 1 A O 0 B O 1 C O n D O n2 答案C27 線(xiàn)性表有兩種存儲(chǔ)結(jié)構(gòu)一是順序表 二 是鏈表 試問(wèn) 1 如果有n個(gè)線(xiàn)性表同時(shí)并存 并且在處理過(guò)程中各表的長(zhǎng)度會(huì) 動(dòng)態(tài)變化 線(xiàn)性表的總數(shù)也會(huì)自動(dòng)地改變 在此情況下 應(yīng)選用哪種存儲(chǔ)結(jié)構(gòu) 為什么 2 若線(xiàn)性表的總數(shù)基本穩(wěn)定 且很少進(jìn)行插入和刪除 但要求以 最快的速度存取線(xiàn)性表中的元素 那么應(yīng)采用哪種存儲(chǔ)結(jié)構(gòu) 為什 么 答案 1 選鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 它可動(dòng)態(tài)申請(qǐng)內(nèi)存空間 不受表長(zhǎng)度 即表中元素個(gè)數(shù) 的影響 插入 刪除時(shí)間復(fù)雜度為O 1 2 選順序存儲(chǔ)結(jié)構(gòu) 順序表可以隨機(jī)存取 時(shí)間復(fù)雜度為O 1 28 若較頻繁地對(duì)一個(gè)線(xiàn)性表進(jìn)行插入和刪除操作 該線(xiàn)性表宜采 用何種存儲(chǔ)結(jié)構(gòu) 為什么 答案采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 它根據(jù)實(shí)際需 要申請(qǐng)內(nèi)存空間 而當(dāng)不需要時(shí)又可將不用結(jié)點(diǎn)空間返還給系統(tǒng) 在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中插入和刪除操作不需要移動(dòng)元素 29 線(xiàn)性結(jié)構(gòu)包括 和 線(xiàn)性表的存儲(chǔ)結(jié)構(gòu)分成 和 答案線(xiàn)性表?xiàng)ｊ?duì)列串順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)30 對(duì)于棧操作 數(shù)據(jù)的原則是 A 先進(jìn)先出B 后進(jìn)先出C 后進(jìn)后出D 不分順序答案B 31 一個(gè)棧的 輸入序列為123 n 若輸出序列的第一個(gè)元素是n 輸出第i 1 i n 個(gè)元素是 A 不確定B n i 1C i D n i答案B32 有六個(gè)元素6 5 4 3 2 1的順序進(jìn)棧 問(wèn)下列哪一 個(gè)不是合法的出棧序列 A 543612B 453126C 346521D 234156 答案C 33 棧和隊(duì)列的共同點(diǎn)是 A 都是先進(jìn)先出B 都是先進(jìn)后出C 只允許在端點(diǎn)處插入和刪除元素D 沒(méi)有共同點(diǎn)答案C34 判斷棧與隊(duì)列是一種特殊操作的線(xiàn)性表 答案 35 判斷棧和隊(duì)列都是線(xiàn)性表 只是在插入和刪除時(shí)受 到了一些限制 答案 36 名詞解釋棧 答案棧是只準(zhǔn)在一端進(jìn)行插入和刪除操作的線(xiàn)性表 允許插入和刪 除的一端叫棧頂 另一端叫棧底 最后插入的元素最先刪除 故棧也稱(chēng)后進(jìn)先出 LIFO 表 37 名詞解釋隊(duì)列答案隊(duì)列是允許在一端插入而在另一端刪除的線(xiàn) 性表 允許插入的一端叫隊(duì)尾 允許刪除的一端叫隊(duì)頭 最先插入隊(duì)的元素最先離開(kāi) 刪除 故隊(duì)列也常稱(chēng)先進(jìn)先出 FIF O 表 38 若元素的進(jìn)棧序列為A B C D E 運(yùn)用棧操作 能否得到出 棧序列B C A E D和D B A C E 為什么 答案能得到出棧 序列B C A E D 不能得到出棧序列D B A C E 其理由為若出棧序列以D開(kāi)頭 說(shuō)明在D之前的入棧元素是A B和C 三個(gè)元素中C是棧頂元素 B和A不可能早于C出棧 故不可能得到D B A C E出棧序列 39 什么叫串的模式匹配算法答案就是給定一個(gè)串和子串 定位字 串在串中位置的算法 40 下面關(guān)于串的的敘述中 哪一個(gè)是不正確的 A 串是字符 的有限序列B 空串是由空格構(gòu)成的串C 模式匹配是串的一種重要 運(yùn)算D 串既可以采用順序存儲(chǔ) 也可以采用鏈?zhǔn)酱鎯?chǔ)答案B41 串 的長(zhǎng)度是指 A 串中所含不同字母的個(gè)數(shù)B 串中所含字符的個(gè) 數(shù)C 串中所含不同字符的個(gè)數(shù)D 串中所含非空格字符的個(gè)數(shù)答案B 42 設(shè)s I AMA STUDENT 則字符串的長(zhǎng)度Length s A 11B 12C 14D 1543 空格串是指 1 其長(zhǎng)度等于 2 答案 1 由空格字符 ASCII值32 所組成的字符串 2 空格個(gè)數(shù)44 串是一種特殊的線(xiàn)性表 其特殊性表現(xiàn)在 1 串的兩種最基本的存儲(chǔ)方式是 2 3 兩個(gè)串相等的充分必要條件是 4 答案 1 其數(shù)據(jù)元素都是字符 2 順序存儲(chǔ) 3 和鏈?zhǔn)酱鎯?chǔ) 4 串的長(zhǎng)度相等且兩串中對(duì)應(yīng)位置的字符也相等45 描述以下概念 的區(qū)別空格串與空串答案空格是一個(gè)字符 其ASCII碼值是32 空格串是由空格組成的串 其長(zhǎng)度等于空格的個(gè)數(shù) 空串是不含任何字符的串 即空串的長(zhǎng)度是零 46 廣義表有兩個(gè)特殊的基本運(yùn)算答案取表頭head LS 取表中的第 一個(gè)數(shù)據(jù)元素 不能對(duì)空表操作 取表尾tail LS 取除表頭外 其余數(shù)據(jù)元素構(gòu)成的子表 不能對(duì)空 表操作 47 廣義表 a b c d 的表頭是 表尾是 A a B C a b c d D b c d 答案C48 廣義表 a b c d e 的表頭為 A a B a b c C a b c D a 答案A 49 廣義表 a b c d 的表頭是 表尾是 A b B a C a D b c d E b c d答案B a D b c d 50 已知一算術(shù) 表達(dá)式的中綴形式為A B C D E 后綴形式為ABC DE 其前綴形式為 A A B C DE B A B CD E C ABC DE D A BC DE答案D 51 若采用孩子兄弟鏈表作為樹(shù)的存儲(chǔ)結(jié)構(gòu) 則樹(shù)的先根遍歷應(yīng)采 用二叉樹(shù)的 A 層次遍歷B 先序遍歷C 中序遍歷D 后序遍歷答案B 52 二叉樹(shù)的5個(gè)性質(zhì)53 有關(guān)二叉樹(shù)下列說(shuō)法正確的是 A 二 叉樹(shù)的度為2B 一棵二叉樹(shù)的度可以小于2C 二叉樹(shù)中至少有一個(gè) 結(jié)點(diǎn)的度為2D 二叉樹(shù)中任何一個(gè)結(jié)點(diǎn)的度都為2答案B55 一棵樹(shù) 高為K的完全二叉樹(shù)至少有 個(gè)結(jié)點(diǎn)A 2k 1B 2k 1 1C 2k 1D 2k答案C56 已知一棵二叉樹(shù)的前序遍歷結(jié)果為ABCDEF 中序遍歷 結(jié)果為CBAEDF 則后序遍歷的結(jié)果為 A CBEFDA B FEDCBA C CBEDFA D 不定答案A57 線(xiàn)索二叉樹(shù)是一種 結(jié)構(gòu) A 邏輯B 邏輯和存儲(chǔ)C 物理D 線(xiàn)性答案C58 由3個(gè)結(jié)點(diǎn)可以構(gòu) 造出多少種不同的二叉樹(shù) A 2B 3C 4D 5答案D59 從概念 上講 樹(shù) 森林和二叉樹(shù)是三種不同的數(shù)據(jù)結(jié)構(gòu) 將樹(shù) 森林轉(zhuǎn)化 為二叉樹(shù)的基本目的是什么 并指出樹(shù)和二叉樹(shù)的主要區(qū)別 答案樹(shù)的孩子兄弟鏈表表示法和二叉樹(shù)二叉鏈表表示法 本質(zhì)是一 樣的 只是解釋不同 也就是說(shuō)樹(shù) 樹(shù)是森林的特例 即森林中只 有一棵樹(shù)的特殊情況 可用二叉樹(shù)唯一表示 并可使用二叉樹(shù)的一 些算法去解決樹(shù)和森林中的問(wèn)題 樹(shù)和二叉樹(shù)的區(qū)別有三一是二叉樹(shù)的度至多為2 樹(shù)無(wú)此限制 二是 二叉樹(shù)有左右子樹(shù)之分 即使在只有一個(gè)分枝的情況下 也必須指 出是左子樹(shù)還是右子樹(shù) 樹(shù)無(wú)此限制 三是二叉樹(shù)允許為空 樹(shù)一 般不允許為空 個(gè)別書(shū)上允許為空 60 樹(shù)和二叉樹(shù)之間有什么樣的區(qū)別與聯(lián)系 答案樹(shù)和二叉樹(shù)邏輯 上都是樹(shù)形結(jié)構(gòu) 區(qū)別有以上題1所述三點(diǎn) 二叉樹(shù)不是樹(shù)的特例 61 請(qǐng)分析線(xiàn)性表 樹(shù) 廣義表的主要結(jié)構(gòu)特點(diǎn) 以及相互的差異 與關(guān)聯(lián) 答案線(xiàn)性表屬于約束最強(qiáng)的線(xiàn)性結(jié)構(gòu) 在非空線(xiàn)性表中 只有一個(gè) 第一個(gè) 元素 也只有一個(gè) 最后一個(gè) 元素 除第一個(gè)元素外 每個(gè)元素有唯一前驅(qū) 除最后一個(gè)元素外 每個(gè)元素有唯一后繼 樹(shù)是一種層次結(jié)構(gòu) 有且只有一個(gè)根結(jié)點(diǎn) 每個(gè)結(jié)點(diǎn)可以有多個(gè)子 女 但只有一個(gè)雙親 根無(wú)雙親 從這個(gè)意義上說(shuō)存在一 雙親 對(duì)多 子女 的關(guān)系 廣義表中的元素既可以是原子 也可以是子表 子表可以為它表共 享 從表中套表意義上說(shuō) 廣義表也是層次結(jié)構(gòu) 從邏輯上講 樹(shù)和廣義表均屬非線(xiàn)性結(jié)構(gòu) 但在以下意義上 又蛻變?yōu)榫€(xiàn)性結(jié)構(gòu) 如度為1的樹(shù) 以及廣義表中的元素都是原子時(shí) 另外 廣義表從元素之間的關(guān)系可看成前驅(qū)和后繼 也符合線(xiàn)性表 但這時(shí)元素有原子 也有子表 即元素并不屬于同一數(shù)據(jù)對(duì)象 62 已知完全二叉樹(shù)有30個(gè)結(jié)點(diǎn) 則整個(gè)二叉樹(shù)有多少個(gè)度為0的結(jié) 點(diǎn) 答案 1563 假設(shè)有向圖含n個(gè)頂點(diǎn)及e條弧 則表示該圖的鄰接表中包含 的弧結(jié)點(diǎn)個(gè)數(shù)為 A n B e C 2e D n e答案B64 一個(gè)n個(gè)頂點(diǎn)的連通無(wú)向圖 其邊的個(gè)數(shù)至少為 A n 1B n C n 1D nlogn 答案A65 n個(gè)結(jié)點(diǎn)的完全有向圖含有邊的數(shù)目 A n n n n C n 2D n n l 答案D66 判斷一個(gè)無(wú) 向圖是一棵樹(shù)的條件是 答案有n個(gè)頂點(diǎn) n 1條邊的無(wú)向連通圖67 具有10個(gè)頂點(diǎn)的無(wú)向圖 邊的總數(shù)最多為 答案4568 求圖的最小生成樹(shù)有兩種算法 算法適合于求稀 疏圖的最小生成樹(shù) 答案克魯斯卡爾69 下面描述的是一種構(gòu)造最小生成樹(shù)算法的基本 思想 設(shè)要處理的無(wú)向圖包括n個(gè)節(jié)點(diǎn)V1 V2 Vn 用相鄰矩陣A 表示 邊的權(quán)全是正數(shù) 請(qǐng)?jiān)谙铝袆澗€(xiàn)處填上正確敘述 1 若 Vi Vj 是邊 則A i j 的值等于 若 Vi Vj 不是邊 則A i j 的值是一個(gè)比任何邊的權(quán) 矩陣 的對(duì)角線(xiàn)元素全為0 2 構(gòu)造最小生成樹(shù)過(guò)程中 若節(jié)點(diǎn)Vi已包括進(jìn)生成樹(shù) 就把相 鄰矩陣的對(duì)角線(xiàn)元素A i i 置成 若 Vi Vj 已包括進(jìn) 生成樹(shù) 就把矩陣元素A i j 置成 3 算法結(jié)束時(shí) 相鄰矩陣中 的元素指出最小生成樹(shù)的 答案 1 Vi Vj 邊上