2022年全國(guó)計(jì)算機(jī)等級(jí)考試二級(jí)公共基礎(chǔ)知識(shí)考題庫(kù)及答案超強(qiáng)

1、2022 年全國(guó)運(yùn)算機(jī)等級(jí)考試二級(jí)公共基礎(chǔ)學(xué)問(wèn)考題庫(kù) 及答案（超強(qiáng)） 第一章 數(shù)據(jù)結(jié)構(gòu) 一,選擇題 （ 1）以下數(shù)據(jù)結(jié)構(gòu)中,能用二分法進(jìn)行查找的是 A）次序儲(chǔ)備的有序線(xiàn)性表 B ）線(xiàn)性鏈表 C）二叉鏈表 D）有序線(xiàn)性鏈表 【答案】 A 【解析】二分查找只適用于次序儲(chǔ)備的有序表；在此所說(shuō)的有序表是指線(xiàn)性表 中的元素按值非遞減排列 即從小到大 但答應(yīng)相鄰元素值相等 的；選項(xiàng) A 正確； （ 2）以下關(guān)于棧的描述正確選項(xiàng) A）在棧中只能插入元素而不能刪除元素 B）在棧中只能刪除元素而不能插入元素 C）棧是特別的線(xiàn)性表,只能在一端插入或刪除元素 D）棧是特別的線(xiàn)性表,只能在一端插入元素,而在另一端刪除

2、元素 【答案】 C 【解析】棧是一種特別的線(xiàn)性表,其插入與刪除運(yùn)算都只在線(xiàn)性表的一端進(jìn)行； 由此可見(jiàn),選項(xiàng) A,選項(xiàng) B 和選項(xiàng) D 錯(cuò)誤,正確答案是選 項(xiàng) C； （ 3）以下表達(dá)中正確選項(xiàng) A ）一個(gè)規(guī)律數(shù)據(jù)結(jié)構(gòu)只能有一種儲(chǔ)備結(jié)構(gòu) B ）數(shù)據(jù)的規(guī)律結(jié)構(gòu)屬于線(xiàn)性結(jié)構(gòu),儲(chǔ)備結(jié)構(gòu)屬于非線(xiàn)性結(jié)構(gòu) 第 1 頁(yè),共 151 頁(yè)C）一個(gè)規(guī)律數(shù)據(jù)結(jié)構(gòu)可以有多種儲(chǔ)備結(jié)構(gòu),且各種儲(chǔ)備結(jié)構(gòu)不影響數(shù)據(jù)處理 的效率 D）一個(gè)規(guī)律數(shù)據(jù)結(jié)構(gòu)可以有多種儲(chǔ)備結(jié)構(gòu),且各種儲(chǔ)備結(jié)構(gòu)影響數(shù)據(jù)處理的 效率 【答案】 D 【解析】一般來(lái)說(shuō),一種數(shù)據(jù)的規(guī)律結(jié)構(gòu)依據(jù)需要可以表示成多種儲(chǔ)備結(jié)構(gòu), 常用的儲(chǔ)備結(jié)構(gòu)有次序,鏈接,索引等儲(chǔ)備結(jié)構(gòu)；

3、而接受不同的儲(chǔ)備結(jié)構(gòu),其 數(shù)據(jù)處理的效率是不同的；由此可見(jiàn),選項(xiàng) D 的說(shuō)法正 確； 4 算法執(zhí)行過(guò)程中所需要的儲(chǔ)備空間稱(chēng)為算法的 A）時(shí)間復(fù)雜度 B）運(yùn)算工作量 C）空間復(fù)雜度 D）工作空間 【答案】 c 【解析】算法執(zhí)行時(shí)所需要的儲(chǔ)備空間,包括算法程序所占的空間,輸入的初 始數(shù)據(jù) 所占的儲(chǔ)備空間以及算法執(zhí)行過(guò)程中所需要的額外空間,其中額外 空間仍包括算法程序執(zhí)行過(guò)程的工作單元以及某種數(shù)據(jù)結(jié)構(gòu)所需要的附加儲(chǔ)備 空間；這些儲(chǔ)備空間共稱(chēng)為算法的空間復(fù)雜度； 5 以下關(guān)于隊(duì)列的表達(dá)中正確選項(xiàng) A）在隊(duì)列中只能插入數(shù)據(jù) B）在隊(duì)列中只能刪除數(shù)據(jù) C）隊(duì)列是先進(jìn)先出的線(xiàn)性表 D）隊(duì)列是先進(jìn)后出的線(xiàn)性表

4、 【答案】 c 【解析】對(duì)隊(duì)列可以進(jìn)行插入和刪除數(shù)據(jù)的操作,只是插入數(shù)據(jù)只能在隊(duì)尾, 刪除數(shù)據(jù)只能在隊(duì)頭；所以隊(duì)列是先進(jìn)先出的線(xiàn)性表； 6 設(shè)有以下二叉樹(shù)： A 第 2 頁(yè),共 151 頁(yè)B DE CF 對(duì)此二叉樹(shù)后序遍歷的結(jié)果為 A） ABCDEF B）BDAECF C） ABDCEF D） DBEFCA 【答案】 D 【解析】二叉樹(shù)的遍歷分為先序,中序,后序三種不同方式；此題要求后序遍 歷；其遍歷次序應(yīng)當(dāng)為：后序遍歷左子樹(shù)一 后序遍歷右子樹(shù)一 拜望根結(jié)點(diǎn)； 依據(jù)定義,后序遍歷序列是 DBEFC,A 故答案為 D； 7 以下表達(dá)中正確選項(xiàng) A 程序執(zhí)行的效率與數(shù)據(jù)的儲(chǔ)備結(jié)構(gòu)親熱相關(guān) B 程序

5、執(zhí)行的效率只取決于程序的把握結(jié)構(gòu) C程序執(zhí)行的效率只取決于所處理的數(shù)據(jù)量 D以上三種說(shuō)法都不對(duì) 【答案】 A 【解析】此題考查程序效率；程序效率是指程序運(yùn)行速度和程序占用的儲(chǔ)備空 間；影響程序效率的因素是多方面的,包括程序的設(shè)計(jì),使用的算法,數(shù)據(jù)的 儲(chǔ)備結(jié)構(gòu)等；在確定數(shù)據(jù)規(guī)律結(jié)構(gòu)的基礎(chǔ)上,選擇一種合適的儲(chǔ)備結(jié)構(gòu),可以 使得數(shù)據(jù)操作所花費(fèi)的時(shí)間少,占用的儲(chǔ)備空間少,即提高程序的效率；因此, 此題選項(xiàng) A 的說(shuō)法是正確的； 第 3 頁(yè),共 151 頁(yè)8 以下表達(dá)中正確選項(xiàng) A 數(shù)據(jù)的規(guī)律結(jié)構(gòu)與儲(chǔ)備結(jié)構(gòu)必定是一一對(duì)應(yīng)的 B 由于運(yùn)算機(jī)儲(chǔ)備空間是向量式的儲(chǔ)備結(jié)構(gòu),因此,數(shù)據(jù)的儲(chǔ)備結(jié)構(gòu)確定是線(xiàn) 性結(jié)構(gòu)

6、C程序設(shè)計(jì)語(yǔ)言中的數(shù)組一般是次序儲(chǔ)備結(jié)構(gòu),因此,利用數(shù)組只能處理線(xiàn)線(xiàn) 結(jié)構(gòu) D以上三種說(shuō)法都不對(duì) 【答案】 D 【解析】此題考查數(shù)據(jù)結(jié)構(gòu)的基本學(xué)問(wèn)； 數(shù)據(jù)之間的相互關(guān)系稱(chēng)為規(guī)律結(jié)構(gòu)；通常分為四類(lèi)基本規(guī)律結(jié)構(gòu),即集合,線(xiàn) 性結(jié)構(gòu),樹(shù)型結(jié)構(gòu),圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)；儲(chǔ)備結(jié)構(gòu)是規(guī)律結(jié)構(gòu)在儲(chǔ)備器中的 映象,它包含數(shù)據(jù)元素的映象和關(guān)系的映象；儲(chǔ)備結(jié)構(gòu)在運(yùn)算機(jī)中有兩種,即 次序儲(chǔ)備結(jié)構(gòu)和鏈?zhǔn)絻?chǔ)備結(jié)構(gòu)；次序儲(chǔ)備結(jié)構(gòu)是把數(shù)據(jù)元素儲(chǔ)備在一塊連續(xù)地 址空間的內(nèi)存中；鏈?zhǔn)絻?chǔ)備結(jié)構(gòu)是使用指針把相互直接關(guān)聯(lián)的節(jié)點(diǎn)鏈接起來(lái)； 因此,這兩種儲(chǔ)備結(jié)構(gòu)都是線(xiàn)性的；可見(jiàn),規(guī)律結(jié)構(gòu)和儲(chǔ)備結(jié)構(gòu)不是一一對(duì)應(yīng) 的；因此,選項(xiàng) A 和選項(xiàng) B

7、 的說(shuō)法都是錯(cuò)誤的； 無(wú)論數(shù)據(jù)的規(guī)律結(jié)構(gòu)是線(xiàn)性的仍是非線(xiàn)性的,只能選擇次序儲(chǔ)備結(jié)構(gòu)或鏈?zhǔn)酱?儲(chǔ)結(jié)構(gòu)來(lái)實(shí)現(xiàn)儲(chǔ)備；程序設(shè)計(jì)語(yǔ)言中,數(shù)組是內(nèi)存中一段連續(xù)的地址空間,可 看作是次序儲(chǔ)備結(jié)構(gòu)；可以用數(shù)組來(lái)實(shí)現(xiàn)樹(shù)型規(guī)律結(jié)構(gòu)的儲(chǔ)備,比如二叉樹(shù)； 因此,選項(xiàng) c 的說(shuō)法是錯(cuò)誤的 9 冒泡排序在最壞情形下的比較次數(shù)是 Ann+1/2 Bnlog 2nCnn-1/2 Dn/2 【答案】 C 第 4 頁(yè),共 151 頁(yè)【解析】冒泡排序的基本思想是：將相鄰的兩個(gè)元素進(jìn)行比較,假如反序,就 交換；對(duì)于一個(gè)待排序的序列,經(jīng)一趟排序后,最大值的元素移動(dòng)到最終的位 置,其他值較大的元素也向最終位置移動(dòng),此過(guò)程稱(chēng)為一趟冒泡；對(duì)

8、于有 n 個(gè) 數(shù)據(jù)的序列,共需 n-1 趟排序,第 i 趟對(duì)從 l 到 n-i 個(gè)數(shù)據(jù)進(jìn)行比較,交換； 冒泡排序的最壞情形是待排序序列逆序,第 l趟比較 n-1 次,第 2 趟比較 n-2 次；依此類(lèi)推,最終趟比較 1 次,一共進(jìn)行 n-l 趟排序；因此,冒泡排序在最 壞情形下的比較次數(shù)是 n-1+n-2+ +l ,結(jié)果為 nn-1/2 ；此題的正確答案 是選項(xiàng) c； 10 一棵二叉樹(shù)中共有 70 個(gè)葉子結(jié)點(diǎn)與 80 個(gè)度為 1 的結(jié)點(diǎn),就該二叉樹(shù)中的 總結(jié)點(diǎn)數(shù)為 A219 B221 C229 D231 【答案】 A 【解析】此題考查數(shù)據(jù)結(jié)構(gòu)中二叉樹(shù)的性質(zhì)；二叉樹(shù)中意如下一條性質(zhì),即： 對(duì)任意

9、一棵二叉樹(shù),如終端結(jié)點(diǎn) 即葉子結(jié)點(diǎn) 數(shù)為 n0,而其度數(shù)為 2 的結(jié)點(diǎn)數(shù) 為 n2,就 n0= n2+l； 依據(jù)這條性質(zhì)可知, 如二叉樹(shù)中有 70 個(gè)葉子結(jié)點(diǎn),就其度為 2 的結(jié)點(diǎn)數(shù)為 70-1 , 即 69 個(gè)；二叉樹(shù)的總結(jié)點(diǎn)數(shù)是度為 2,度為 1 和葉子結(jié)點(diǎn)的總和,因此,題目 中的二叉樹(shù)總結(jié)點(diǎn)數(shù)為 69+80+70,即 219；因此,此題的正確答案是選項(xiàng) A； 11 以下表達(dá)中正確選項(xiàng) A算法的效率只與問(wèn)題的規(guī)模有關(guān),而與數(shù)據(jù)的儲(chǔ)備結(jié)構(gòu)無(wú)關(guān) B算法的時(shí)間復(fù)雜度是指執(zhí)行算法所需要的運(yùn)算工作量 C數(shù)據(jù)的規(guī)律結(jié)構(gòu)與儲(chǔ)備結(jié)構(gòu)是一一對(duì)應(yīng)的 D算法的時(shí)間復(fù)雜度與空間復(fù)雜度確定相關(guān) 第 5 頁(yè),共 15

10、1 頁(yè)【答案】 B 【解析】此題考查數(shù)據(jù)結(jié)構(gòu)中有關(guān)算法的基本學(xué)問(wèn)和概念；數(shù)據(jù)的結(jié)構(gòu),直接 影響算法的選擇和效率；而數(shù)據(jù)結(jié)構(gòu)包括兩方面,即數(shù)據(jù)的規(guī)律結(jié)構(gòu)和數(shù)據(jù)的 儲(chǔ)備結(jié)構(gòu)；因此,數(shù)據(jù)的規(guī)律結(jié)構(gòu)和儲(chǔ)備結(jié)構(gòu)都影響算法的效率；選項(xiàng) A 的說(shuō) 法是錯(cuò)誤的；算法的時(shí)間復(fù)雜度是指算法在運(yùn)算機(jī)內(nèi)執(zhí)行時(shí)所需時(shí)間的度量； 與時(shí)間復(fù)雜度類(lèi)似,空間復(fù)雜度是指算法在運(yùn)算機(jī)內(nèi)執(zhí)行時(shí)所需儲(chǔ)備空間的度 量；因此,選項(xiàng) B 的說(shuō)法是正確 的； 數(shù)據(jù)之間的相互關(guān)系稱(chēng)為規(guī)律結(jié)構(gòu)；通常分為四類(lèi)基本規(guī)律結(jié)構(gòu),即集合,線(xiàn) 性結(jié)構(gòu),樹(shù)型結(jié)構(gòu),圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)；儲(chǔ)備結(jié)構(gòu)是規(guī)律結(jié)構(gòu)在儲(chǔ)備器中的 映象,它包含數(shù)據(jù)元素的映象和關(guān)系的映象；儲(chǔ)備結(jié)

11、構(gòu)在運(yùn)算機(jī)中有兩種,即 次序儲(chǔ)備結(jié)構(gòu)和鏈?zhǔn)絻?chǔ)備結(jié)構(gòu)；可見(jiàn),規(guī)律結(jié)構(gòu)和儲(chǔ)備結(jié)構(gòu)不是一一對(duì)應(yīng)的； 因此,選項(xiàng) c 的說(shuō)法是錯(cuò)誤的；有時(shí)人們?yōu)榱颂岣咚惴ǖ臅r(shí)間復(fù)雜度,而以犧 牲空間復(fù)雜度為代價(jià)；但是,這兩者之間沒(méi)有必定的聯(lián)系；因此,選項(xiàng) D 的 說(shuō) 法是錯(cuò)誤的； 12 以下關(guān)于算法的時(shí)間復(fù)雜度陳述正確選項(xiàng) A） 算法的時(shí)間復(fù)雜度是指執(zhí)行算法程序所需要的時(shí)間 B） 算法的時(shí)間復(fù)雜度是指算法程序的長(zhǎng)度 C） 算法的時(shí)間復(fù)雜度是指算法執(zhí)行過(guò)程中所需要的基本運(yùn)算次數(shù) D） 算法的時(shí)間復(fù)雜度是指算法程序中的指令條數(shù) 【答案】 C 【解析】算法的時(shí)間復(fù)雜度是指執(zhí)行算法所需要的運(yùn)算工作量,也就是算法在 執(zhí)行過(guò)程中

12、所執(zhí)行的基本運(yùn)算的次數(shù),而不是指程序運(yùn)行需要的時(shí)間或是程序 的長(zhǎng)度； 第 6 頁(yè),共 151 頁(yè)13 以下關(guān)于棧的表達(dá)中正確選項(xiàng) A）在棧中只能插入數(shù)據(jù) B ）在棧中只能刪除數(shù)據(jù) C）棧是先進(jìn)先出的線(xiàn)性表 D）棧是先進(jìn)后出的線(xiàn)性表 【答案】 D 【解析】對(duì)?？蛇M(jìn)行插入和刪除數(shù)據(jù)的操作,但必需牢記插入和刪除數(shù)據(jù)都只 能是在棧頂,是一種特別的線(xiàn)性表；所以棧是先進(jìn)后出的線(xiàn)性表； 14 設(shè)有以下二叉樹(shù)： A B CDE FF F 對(duì)此二叉樹(shù)中序遍歷的結(jié)果為 A） ABCDEF B ） DAECF C ） BDAECF D ）DBEFCA 【答案】 C 【解析】二叉樹(shù)的遍歷分為先序,中序,后序三種不同方

13、式；此題要求中序遍 歷,其遍歷次序應(yīng)當(dāng)為：中序遍歷左子樹(shù) - 拜望根結(jié)點(diǎn) - 中序遍歷右子樹(shù)；按 照定義,中序遍歷序列是 BDAEC,F 故答案為 B； 15 依據(jù)“后進(jìn)先出”原就組織數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)是 A）隊(duì)列 D）二叉樹(shù) B ）棧 C）雙向鏈表 【答案】 B 第 7 頁(yè),共 151 頁(yè)【解析】“后進(jìn)先出”表示最終被插入的元素最先能被刪除；選項(xiàng) A 中,隊(duì)列是 指答應(yīng)在一端進(jìn)行插入,而在另一端進(jìn)行刪除的線(xiàn)性表,在隊(duì)列這種數(shù)據(jù)結(jié)構(gòu) 中,最先插入的元素將最先能夠被刪除,反之,最終插入的元素將最終才能被 刪除,隊(duì)列又稱(chēng)為“先進(jìn)先出”的線(xiàn)性表,它表達(dá)了“先來(lái)先服務(wù)”的原就： 選項(xiàng) B 中,棧頂元素總是

14、最終被插入的元素,從而也是最先能被刪除的元素, 棧底元素總是最先被插入的元素,從而也是最終才能被刪除的元素；隊(duì)列和棧 都屬于線(xiàn)性表,它們具有次序儲(chǔ)備的特點(diǎn),所以才有“先進(jìn)先出”和“后進(jìn)先 出”的數(shù)據(jù)組織方式；雙向鏈表使用鏈?zhǔn)絻?chǔ)備方式二叉樹(shù)也通常接受鏈?zhǔn)酱?儲(chǔ)方式,它們的儲(chǔ)備數(shù)據(jù)的空間可以是不連續(xù)的,各個(gè)數(shù)據(jù)結(jié)點(diǎn)的儲(chǔ)備次序與 數(shù)據(jù)元素之間的規(guī)律關(guān)系可以不一樣；所以選項(xiàng) c 和選項(xiàng) D 錯(cuò)； 16 以下表達(dá)中正確選項(xiàng) A）線(xiàn)性鏈表是線(xiàn)性表的鏈?zhǔn)絻?chǔ)備結(jié)構(gòu) B）棧與隊(duì)列是非線(xiàn)性結(jié)構(gòu) C）雙向鏈表是非線(xiàn)性結(jié)構(gòu) D）只有根結(jié)點(diǎn)的二叉樹(shù)是線(xiàn)性結(jié)構(gòu) 【答案】 A 【解析】一個(gè)非空的數(shù)據(jù)結(jié)構(gòu)假如中意以下兩個(gè)條件

15、： 1 有且只有一個(gè)根結(jié) 點(diǎn);2 每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件,也最多有一個(gè)后件；就稱(chēng)為線(xiàn)性結(jié)構(gòu)；線(xiàn) 性鏈表是線(xiàn)性表的鏈?zhǔn)絻?chǔ)備結(jié)構(gòu),選項(xiàng) A 的說(shuō)法是正確的；棧與隊(duì)列是特別的 線(xiàn)性表,它們也是線(xiàn)性結(jié)構(gòu),選項(xiàng) B 的說(shuō)法是錯(cuò)誤的；雙向鏈表是線(xiàn)性表的鏈 式儲(chǔ)備結(jié)構(gòu),其對(duì)應(yīng)的規(guī)律結(jié)構(gòu)也是線(xiàn)性結(jié)構(gòu),而不是非線(xiàn)性結(jié)構(gòu),選項(xiàng) c 的 說(shuō)法是錯(cuò)誤的；二叉樹(shù)是非線(xiàn)性結(jié)構(gòu),而不是線(xiàn)性結(jié)構(gòu),選項(xiàng) D 的說(shuō)法是錯(cuò)誤 的；因此,此題的正確答案為 A 第 8 頁(yè),共 151 頁(yè)17 對(duì)如下二叉樹(shù) A DB E F C進(jìn)行后序遍歷的結(jié)果為 A） ABCDEF B） DBEAFC C） ABDECF D） DEBFCA 【答案

16、】 D 【解析】二叉樹(shù)后序遍歷的簡(jiǎn)潔描述如下：如二叉樹(shù)為空,就終止返回；否就 （ 1 后序遍歷左子樹(shù)； 2 后序遍歷右子樹(shù)； 3 拜望根結(jié)點(diǎn)；也就是說(shuō),后序 遍歷是指在拜望根結(jié)點(diǎn),遍歷左子樹(shù)與遍歷右子樹(shù)這三者中,第一遍歷左子樹(shù), 然后遍歷右子樹(shù),最終拜望根結(jié)點(diǎn),并且,在遍歷左,右子樹(shù)時(shí),仍然先遍歷 左子樹(shù),然后遍歷右子樹(shù),最終拜望根結(jié)點(diǎn)；依據(jù)后序遍歷的算法,后序遍歷 的結(jié)果為 DEBFC；A 18 以下對(duì)隊(duì)列的表達(dá)正確選項(xiàng) A隊(duì)列屬于非線(xiàn)性表 B隊(duì)列按“先進(jìn)后出”原就組織數(shù)據(jù) C隊(duì)列在隊(duì)尾刪除數(shù)據(jù) 第 9 頁(yè),共 151 頁(yè)D隊(duì)列按“先進(jìn)先出”原就組織數(shù)據(jù) 【答案】 D 【解析】此題考查數(shù)據(jù)結(jié)

17、構(gòu)中隊(duì)列的基本學(xué)問(wèn)；隊(duì)列是一種限定性的線(xiàn)性表, 它只答應(yīng)在表的一端插入元素,而在另一端刪除元素,所以隊(duì)列具有先進(jìn)先出 的特性；在隊(duì)列中,答應(yīng)插入元素的一端叫做隊(duì)尾,答應(yīng)刪除的一端就稱(chēng)為隊(duì) 頭；這與日常生活中的排隊(duì)是一樣的,最早進(jìn)入隊(duì)列的人最早離開(kāi),新來(lái)的人 總是加入到隊(duì)尾；因此,此題中只有選項(xiàng) D 的說(shuō)法是正確 的； 19 對(duì)以下二叉樹(shù)進(jìn)行前序遍歷的結(jié)果為 A DYBEAFCZX B YDEBFZXCA C ABDYECFXZ D ABCDEFXYZ 【答案】 C 【解析】此題考查數(shù)據(jù)結(jié)構(gòu)中二叉樹(shù)的遍歷；依據(jù)對(duì)二叉樹(shù)根的拜望先后次序 不同,分別稱(chēng)為前序遍歷,中序遍歷和后序遍歷；這三種遍歷都是遞

18、歸定義的, 即在其子樹(shù)中也依據(jù)同樣的規(guī)律進(jìn)行遍歷；下面就是前序遍歷方法的遞歸定義； 當(dāng)二叉樹(shù)的根不為空時(shí),依次執(zhí)行如下 3 個(gè)操作： 1 拜望根結(jié)點(diǎn) 2 按先序遍歷左子樹(shù) 3 按先序遍歷右子樹(shù) 依據(jù)如上前序遍歷規(guī)章,來(lái)遍歷此題中的二叉樹(shù)；第一拜望根結(jié)點(diǎn),即 A,然 后遍歷 A 的左子樹(shù)；遍歷左子樹(shù)同樣依據(jù)相同的規(guī)章第一拜望根結(jié)點(diǎn) B,然后 遍歷 B 的左子樹(shù)； 遍歷 B 的左子樹(shù), 第一拜望 D,然后拜望 D 的左子樹(shù), D 的 左 第 10 頁(yè),共 151 頁(yè)子樹(shù)為空 , 接下來(lái)拜望 D 的右子樹(shù),即 Y；遍歷完 B 的左子樹(shù)后,再遍歷 B 的右 子樹(shù),即 E；到此遍歷完 A 的左子樹(shù),接下

19、來(lái)遍歷 A 的右子樹(shù)；依據(jù)同樣的規(guī) 就,第一拜望 C,然后遍歷 c 的左子樹(shù)；即 F； c 的左子樹(shù)遍歷完,接著遍歷 c 的右子樹(shù)；第一拜望右子樹(shù)的根結(jié)點(diǎn) X,然后拜望 X 的左子樹(shù), X 的左子樹(shù), 即 Z,接下來(lái)拜望 X 的右子樹(shù), 右子樹(shù)為空；到此,把題目的二叉樹(shù)進(jìn)行了一次前 序遍歷；遍歷的結(jié)果為 ABDYECFX,Z故此題的正確答案為選 項(xiàng) C； 20 某二叉樹(shù)中有 n 個(gè)度為 2 的結(jié)點(diǎn),就該二叉樹(shù)中的葉子結(jié)點(diǎn)數(shù)為 A n+1 B n-1 C 2n D n/2 【答案】 A 【解析】此題考查數(shù)據(jù)結(jié)構(gòu)中二叉樹(shù)的性質(zhì)； 二叉樹(shù)中意如下一條性質(zhì),即： 對(duì)任意一棵二叉樹(shù),如終端結(jié)點(diǎn) 即葉子結(jié)

20、點(diǎn) 數(shù)為 no,而其度數(shù)為 2 的結(jié)點(diǎn)數(shù) 為 n2,就 n0=n2+l； 依據(jù)這條性質(zhì)可知,如二叉樹(shù)中有 n 個(gè)度為 2 的結(jié)點(diǎn),就該二叉樹(shù)中的葉子結(jié) 點(diǎn)數(shù)為 n+l ；因此,此題的正確答案是選項(xiàng) A； 21 在深度為 7 的滿(mǎn)二叉樹(shù)中,葉子結(jié)點(diǎn)的個(gè)數(shù)為 A） 32 B）31 C）64 D） 63 【答案】 C k-1 【解析】在二叉樹(shù)的第 k 層上,最多有 2 k 1 個(gè)結(jié)點(diǎn)；對(duì)于滿(mǎn)二叉樹(shù)來(lái)說(shuō), 每一層上的結(jié)點(diǎn)數(shù)都達(dá)到最大值, 即在滿(mǎn)二叉樹(shù)的第 k 層上有 2 個(gè)結(jié)點(diǎn)；因此, k-1 7-1 在深度為 7 的滿(mǎn)二叉樹(shù)中, 全部葉子結(jié)點(diǎn)在第 7 層上即其結(jié)點(diǎn)數(shù)為 2 =2 =64 因此此題的正

21、確答案為 c； 22 以下表達(dá)中正確選項(xiàng) A）一個(gè)算法的空間復(fù)雜度大,就其時(shí)間復(fù)雜度也必定大 第 11 頁(yè),共 151 頁(yè)B）一個(gè)算法的空間復(fù)雜度大,就期時(shí)間復(fù)雜度必定小 C）一個(gè)算法的時(shí)間復(fù)雜度大,就其空間復(fù)雜度必定小 D）上述三種說(shuō)法都不對(duì) 【答案】 D 【解析】時(shí)間復(fù)雜度是指一個(gè)算法執(zhí)行時(shí)間的相對(duì)度量；空間復(fù)雜度是指算法 在運(yùn)行過(guò)程中臨時(shí)占用所需儲(chǔ)備空間大小的度量；人們都期望選擇一個(gè)既省存 儲(chǔ)空間,又省執(zhí)行時(shí)間的算法；然而,有時(shí)為了加快算法的運(yùn)行速度,不得不 增加空間開(kāi)銷(xiāo)；有時(shí)為了能有效地儲(chǔ)備算法和數(shù)據(jù),又不得不犧牲運(yùn)行時(shí)間； 時(shí)間和空間的效率往往是一對(duì)沖突,很難做到兩全；但是,這不適用

22、于全部的 情形,也就是說(shuō)時(shí)間復(fù)雜度和空間復(fù)雜度之間雖然經(jīng)常沖突；但是二者不存在 必定的聯(lián)系；因此,選項(xiàng) A,B,c 的說(shuō)法都是錯(cuò)誤的；故此題的正確答案是 D； 23 在長(zhǎng)度為 64 的有序線(xiàn)性表中進(jìn)行次序查找,最壞情形下需要比較的次數(shù)為 A） 63 B ）64 C）6 D）7 【答案】 B 【解析】在長(zhǎng)度為 64 的有序線(xiàn)性表中,其中的 64 個(gè)數(shù)據(jù)元素是依據(jù)從大到小 或從小到大的次序排列有序的；在這樣的線(xiàn)性表中進(jìn)行次序查找,最壞的情形 就是查找的數(shù)據(jù)元素不在線(xiàn)性表中或位于線(xiàn)性表的最終；依據(jù)線(xiàn)性表的次序查 找算法,第一用被查找的數(shù)據(jù)和線(xiàn)性表的第一個(gè)數(shù)據(jù)元素進(jìn)行比較；如相等, 就查找勝利,否就,

23、連續(xù)進(jìn)行比較,即和線(xiàn)性表的其次個(gè)數(shù)據(jù)元素進(jìn)行比較； 同樣,如相等,就查找勝利,否就,連續(xù)進(jìn)行比較；依次類(lèi)推,直到在線(xiàn)性表 中查找到該數(shù)據(jù)或查找到線(xiàn)性表的最終一個(gè)元素,算法才終止；因此,在長(zhǎng)度 為 64 的有序線(xiàn)性表中進(jìn)行次序查找,最壞的情形下需要比較 64 次；因此,本 題的正確答案為 B； 第 12 頁(yè),共 151 頁(yè)24 對(duì)以下二叉樹(shù) 進(jìn)行中序遍歷的結(jié)果是 A） ACBDFEG B）ACBDFGE C） ABDCGEF D）FCADBEG F A CDE G B 【答案】 A 【解析】二叉樹(shù)的中序遍歷遞歸算法為：假如根不空,就 1 按中序次序拜望左 子樹(shù)； 2 拜望根結(jié)點(diǎn)： 3 按中序次序

24、拜望右子樹(shù)；否就返回；此題中,依據(jù) 中序遍歷算法應(yīng)第一依據(jù)中序次序拜望以 c 為根結(jié)點(diǎn)的左子樹(shù),然后再拜望 根結(jié)點(diǎn) F,最終才拜望以 E 為根結(jié)點(diǎn)的右子樹(shù)； 遍歷以 c 為根結(jié)點(diǎn)的左子樹(shù)同樣 要遵循中序遍歷算法,因此中序遍歷結(jié)果為 ACBD；然后遍歷根結(jié)點(diǎn) F；遍歷以 E 為根結(jié)點(diǎn)的右子樹(shù),同樣要遵循中序遍歷算法,因此中序遍歷結(jié)果為 EG；最終 把這三部分的遍歷結(jié)果按次序連接起來(lái),中序遍歷結(jié)果為 ACBDFE；G因此,此題 的正確答案是 A； （ 25）數(shù)據(jù)的儲(chǔ)備結(jié)構(gòu)是指； A）儲(chǔ)備在外存中的數(shù)據(jù) B）數(shù)據(jù)所占的儲(chǔ)備空間量 C）數(shù)據(jù)在運(yùn)算機(jī)中的次序儲(chǔ)備方式 D）數(shù)據(jù)的規(guī)律結(jié)構(gòu)在運(yùn)算機(jī)中的表示

25、【答案】 D 【解析】數(shù)據(jù)的規(guī)律結(jié)構(gòu)在運(yùn)算機(jī)儲(chǔ)備空間中的存放形式稱(chēng)為數(shù)據(jù)的儲(chǔ)備結(jié)構(gòu), 第 13 頁(yè),共 151 頁(yè)也稱(chēng)數(shù)據(jù)的物理結(jié)構(gòu)；所以選項(xiàng) D 正 確； （ 26）以下關(guān)于棧的描述中錯(cuò)誤選項(xiàng) ； A） 棧是先進(jìn)后出的線(xiàn)性表 B） 棧只能次序儲(chǔ)備 C） 棧具有記憶作用 D） 對(duì)棧的插入與刪除操作中,不需要轉(zhuǎn)變棧底指針 【答案】 B 【解析】此題考核棧的基本概念,我們可以通過(guò)排除法來(lái)確定此題的答案；棧 是限定在一端進(jìn)行插入與刪除的線(xiàn)性表,棧頂元素總是最終被插入的元素,從 而也是最先能被刪除的元素；棧底元素總是最先被插入的元素,從而也是最終 才能被刪除的元素,即棧是依據(jù)“先進(jìn)后出”或“后進(jìn)先出”

26、的原就組織數(shù)據(jù) 的,這便是棧的記憶作用,所以選項(xiàng) A 和選項(xiàng) C 正確；對(duì)棧進(jìn)行插入和刪除操 作時(shí),棧頂位置是動(dòng)態(tài)變化的,棧底指針不變,選項(xiàng) D 正確；由此可見(jiàn),選B 項(xiàng) 的描述錯(cuò)誤； （ 27）對(duì)于長(zhǎng)度為 n 的線(xiàn)性表,在最壞情形下,以下各排序法所對(duì)應(yīng)的比較次 數(shù) 中正確選項(xiàng)； B）冒泡排序?yàn)?n A）冒泡排序?yàn)?n/2 C）快速排序?yàn)?n【答案】 D D）快速排序?yàn)?nn-1/2 【解析】假設(shè)線(xiàn)性表的長(zhǎng)度為 n,在最壞情形下,冒泡排序和快速排序需要的比 較次數(shù)為 nn 1 2；由此可見(jiàn),選項(xiàng) D正 確； （ 28）對(duì)長(zhǎng)度為 n 的線(xiàn)性表進(jìn)行次序查找,在最壞情形下所需要的比較次數(shù) 為 ； 第

27、 14 頁(yè),共 151 頁(yè)n A） log2 B）n/2 C） n D）n+1 【答案】 C 【解析】在長(zhǎng)度為 n 的線(xiàn)性表中進(jìn)行次序查找,最壞情形下需要比較 n 次；選 項(xiàng) C 正 確； （ 29）以下對(duì)于線(xiàn)性鏈表的描述中正確選項(xiàng) ； A） 儲(chǔ)備空間不愿定是連續(xù),且各元素的儲(chǔ)備次序是任意的 B） 儲(chǔ)備空間不愿定是連續(xù),且前件元素確定儲(chǔ)備在后件元素的前面 C） 儲(chǔ)備空間必需連續(xù),且前件元素確定儲(chǔ)備在后件元素的前面 D） 儲(chǔ)備空間必需連續(xù),且各元素的儲(chǔ)備次序是任意的 【答案】 A 【解析】在鏈?zhǔn)絻?chǔ)備結(jié)構(gòu)中,儲(chǔ)備數(shù)據(jù)的儲(chǔ)備空間可以不連續(xù),各數(shù)據(jù)結(jié)點(diǎn)的 儲(chǔ)備次序與數(shù)據(jù)元素之間的規(guī)律關(guān)系可以不一樣,數(shù)

28、據(jù)元素之間的規(guī)律關(guān)系, 是由指針域來(lái)確定的；由此可見(jiàn),選項(xiàng) A 的描述正確； （ 30）某二叉樹(shù)中度為 2 的結(jié)點(diǎn)有 18 個(gè),就該二叉樹(shù)中有 個(gè)葉子結(jié)點(diǎn)； 【答案】 19 【解析】二叉樹(shù)具有如下性質(zhì)：在任意一棵二叉樹(shù)中,度為 O 的結(jié)點(diǎn) 即葉子 結(jié) 點(diǎn) 總是比度為 2 的結(jié)點(diǎn)多一個(gè)；依據(jù)題意,度為 2 的節(jié)點(diǎn)為 18 個(gè),那么, 葉子結(jié)點(diǎn)就應(yīng)當(dāng)是 19 個(gè)； （ 1）線(xiàn)性表如接受鏈?zhǔn)絻?chǔ)備結(jié)構(gòu)時(shí),要求內(nèi)存中可用儲(chǔ)備單元的地址 A）必需是連續(xù)的 B）部分地址必需是連續(xù)的 C）確定是不連續(xù)的 第 15 頁(yè),共 151 頁(yè)D）連續(xù)不連續(xù)都可以 解析： 在鏈?zhǔn)絻?chǔ)備結(jié)構(gòu)中,儲(chǔ)備數(shù)據(jù)結(jié)構(gòu)的儲(chǔ)備空間可以是連

29、續(xù)的,也可以是 不連續(xù)的,各數(shù)據(jù)結(jié)點(diǎn)的儲(chǔ)備次序與數(shù)據(jù)元素之間的規(guī)律關(guān)系可以不一樣；故 此題答案應(yīng)當(dāng)為選項(xiàng) D） （ 2）在待排序的元素序列基本有序的前提下,效率最高的排序方法是 A）冒泡排序 B）選擇排序 C）快速排序 D）歸并排序 解析： 從平均時(shí)間性能而言,快速排序正確,其所需時(shí)間最少,但快速排序在 最壞情形下的時(shí)間性能不如堆排序和歸并排序；當(dāng)序列中的記錄基本有序或元 素個(gè)數(shù)較少時(shí),冒泡排序和簡(jiǎn)潔選擇排序?yàn)檎_排序方法,故此題答案應(yīng)當(dāng)為 選項(xiàng) A）； （ 3）以下表達(dá)中,錯(cuò)誤選項(xiàng) A）數(shù)據(jù)的儲(chǔ)備結(jié)構(gòu)與數(shù)據(jù)處理的效率親熱相關(guān) B）數(shù)據(jù)的儲(chǔ)備結(jié)構(gòu)與數(shù)據(jù)處理的效率無(wú)關(guān) C）數(shù)據(jù)的儲(chǔ)備結(jié)構(gòu)在運(yùn)算機(jī)

30、中所占的空間不愿定是連續(xù)的 D）一種數(shù)據(jù)的規(guī)律結(jié)構(gòu)可以有多種儲(chǔ)備結(jié)構(gòu) 解析： 一般來(lái)說(shuō),一種數(shù)據(jù)結(jié)構(gòu)依據(jù)需要可以表示成多種儲(chǔ)備結(jié)構(gòu)；常用的存 儲(chǔ)結(jié)構(gòu)有次序,鏈接,索引等,而接受不同的儲(chǔ)備結(jié)構(gòu),其數(shù)據(jù)處理的效率是 不同的；一個(gè)數(shù)據(jù)結(jié)構(gòu)中的各數(shù)據(jù)元素在運(yùn)算機(jī)儲(chǔ)備空間中的位置關(guān)系與規(guī)律 關(guān)系是有可能不同的；故此題答案應(yīng)當(dāng)為選項(xiàng) B）； （ 4）希爾排序?qū)儆?第 16 頁(yè),共 151 頁(yè)A）交換排序 B）歸并排序 C）選擇排序 D）插入排序 解析： 希爾排序的基本思想是把記錄按下標(biāo)的確定增量分組,對(duì)每組記錄使用 插入排序,隨增量的逐步減小,所分成的組包含的記錄越來(lái)越多,到增量 的值減小到 1 時(shí),整個(gè)

31、數(shù)據(jù)合成一組,構(gòu)成一組有序記錄,故其屬于插入 排序方法；故此題答案應(yīng)當(dāng)為選項(xiàng) D）； （ 1）棧和隊(duì)列的共同特點(diǎn)是 A）都是先進(jìn)先出 B）都是先進(jìn)后出 C）只答應(yīng)在端點(diǎn)處插入和刪除元素 D）沒(méi)有共同點(diǎn) 解析：棧和隊(duì)列都是一種特別的操作受限的線(xiàn)性表,只答應(yīng)在端點(diǎn)處進(jìn)行插入 和刪除； 二者的區(qū)分是： 棧只答應(yīng)在表的一端進(jìn)行插入或刪除操作, 是一種“后 進(jìn)先出”的線(xiàn)性表；而隊(duì)列只答應(yīng)在表的一端進(jìn)行插入操作,在另一端進(jìn)行刪 除操作,是一種“先進(jìn)先出”的線(xiàn)性表；故此題答案應(yīng)當(dāng)為選項(xiàng) C）； （ 2）已知二叉樹(shù)后序遍歷序列是 歷序列是 A） acbed B） decab C） deabc D） cedba

32、 dabec,中序遍歷序列是 debac,它的前序遍 第 17 頁(yè),共 151 頁(yè)解析： 依據(jù)后序遍歷序列可確定根結(jié)點(diǎn)為 c；再依據(jù)中序遍歷序列可知其左子 樹(shù)由 deba 構(gòu)成,右子樹(shù)為空；又由左子樹(shù)的后序遍歷序列可知其根結(jié)點(diǎn)為 e, 由中序遍歷序列可知其左子樹(shù)為 d,右子樹(shù)由 ba 構(gòu)成,如下圖所示；求得該二 叉樹(shù)的前序遍歷序列為選項(xiàng) D）； （ 3）鏈表不具有的特點(diǎn)是 A）不必事先估量?jī)?chǔ)備空間 B）可隨機(jī)拜望任一元素 C）插入刪除不需要移動(dòng)元素 D）所需空間與線(xiàn)性表長(zhǎng)度成正比 解析： 鏈表接受的是鏈?zhǔn)絻?chǔ)備結(jié)構(gòu),它克服了次序儲(chǔ)備結(jié)構(gòu)的缺點(diǎn)：它的結(jié)點(diǎn) 空間可以動(dòng)態(tài)申請(qǐng)和釋放；它的數(shù)據(jù)元素的規(guī)律

33、次序靠結(jié)點(diǎn)的指針來(lái)指示, 不需要移動(dòng)數(shù)據(jù)元素；但是鏈?zhǔn)絻?chǔ)備結(jié)構(gòu)也有不足之處： 每個(gè)結(jié)點(diǎn)中的 指針域需額外占用儲(chǔ)備空間； 此題答案應(yīng)當(dāng)為選項(xiàng) D）； （ 6）算法的時(shí)間復(fù)雜度是指 A）執(zhí)行算法程序所需要的時(shí)間 B）算法程序的長(zhǎng)度 鏈?zhǔn)絻?chǔ)備結(jié)構(gòu)是一種非隨機(jī)儲(chǔ)備結(jié)構(gòu)；故 C）算法執(zhí)行過(guò)程中所需要的基本運(yùn)算次數(shù) D）算法程序中的指令條數(shù) 第 18 頁(yè),共 151 頁(yè)解析： 算法的復(fù)雜度主要包括算法的時(shí)間復(fù)雜度和算法的空間復(fù)雜度；所謂算 法的時(shí)間復(fù)雜度是指執(zhí)行算法所需要的運(yùn)算工作量；算法的空間復(fù)雜度一 般是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間；故此題答案應(yīng)當(dāng)為選項(xiàng) A）； （ 1）已知一棵二叉樹(shù)前序遍歷和中序

34、遍歷分別為 二叉樹(shù)的后序遍歷為 A） GEDHFBCA B） DGEBHFCA C） ABCDEFGH D） ACBFEDHG ABDEGCF和H DBGEACH,F就 該 解析： 利用前序和中序遍歷的方法可以確定二叉樹(shù)的結(jié)構(gòu),詳細(xì)步驟如下： 前序遍歷的第一個(gè)結(jié)點(diǎn) A 為樹(shù)的根結(jié)點(diǎn)； 中序遍歷中 A 的左邊的結(jié)點(diǎn) 為 A 的 左子樹(shù), A 右邊的結(jié)點(diǎn)為 A 的右子樹(shù)； 再分別對(duì) A 的左右子樹(shù)進(jìn)行上述兩步 處理,直到每個(gè)結(jié)點(diǎn)都找到正確的位置；故此題答案應(yīng)當(dāng)為選項(xiàng) B）； （ 2）樹(shù)是結(jié)點(diǎn)的集合,它的根結(jié)點(diǎn)數(shù)目是 A）有且只有 1 B） 1 或多于 1 C） 0 或 1 D）至少 2 解析： 樹(shù)

35、是一個(gè)或多個(gè)結(jié)點(diǎn)組成的有限集合,其中一個(gè)特定的結(jié)點(diǎn)稱(chēng)為根,其 余結(jié)點(diǎn)分為如干個(gè)不相交的集合；每個(gè)集合同時(shí)又是一棵樹(shù)；樹(shù)有且只有 1 個(gè) 根結(jié)點(diǎn)；故此題答案應(yīng)當(dāng)為選項(xiàng) A）； （ 3）假如進(jìn)棧序列為 e1,e2,e3,e4 ,就可能的出棧序列是 A） e3,e1,e4,e2 第 19 頁(yè),共 151 頁(yè)B） e2,e4,e3,e1 C） e3,e4,e1,e2 D）任意次序 解析： 由棧 后進(jìn)先出 的特點(diǎn)可知： A）中 e1 不行能比 e2 先出, C）中 e3 不 可能比 e4 先出,且 e1 不行能比 e2 先出, D）中棧是先進(jìn)后出的,所以不行能 是任意次序； B）中出棧過(guò)程如以下圖： 故

36、此題答案應(yīng)當(dāng)為選項(xiàng) B）； （ 4）在設(shè)計(jì)程序時(shí),應(yīng)接受的原就之一是 A）不限制 goto 語(yǔ)句的使用 B）削減或取消注解行 C）程序越短越好 D）程序結(jié)構(gòu)應(yīng)有助于讀者懂得 解析：濫用 goto 語(yǔ)句將使程序流程無(wú)規(guī)律,可讀性差,因此 A）不選；注解行 有利于對(duì)程序的懂得,不應(yīng)削減或取消, B）也不選；程序的長(zhǎng)短要依照實(shí)際情 況而論,而不是越短越好, C）也不選；故此題答案應(yīng)當(dāng)為選項(xiàng) D）； （ 5）程序設(shè)計(jì)語(yǔ)言的基本成分是數(shù)據(jù)成分,運(yùn)算成分,把握成分和 A）對(duì)象成分 B）變量成分 C）語(yǔ)句成分 第 20 頁(yè),共 151 頁(yè)D）傳輸成分 解析： 程序設(shè)計(jì)語(yǔ)言是用于書(shū)寫(xiě)運(yùn)算機(jī)程序的語(yǔ)言,其基本成

37、分有以下 4 種, 數(shù)據(jù)成分：用來(lái)描述程序中的數(shù)據(jù)；運(yùn)算成分：描述程序中所需的運(yùn)算； 把握成分：用來(lái)構(gòu)造程序的規(guī)律把握結(jié)構(gòu)；傳輸成分：定義數(shù)據(jù)傳輸成分, 如輸入輸出語(yǔ)言；故此題答案應(yīng)當(dāng)為選項(xiàng) D）； （ 1）循環(huán)鏈表的主要優(yōu)點(diǎn)是 A）不再需要頭指針了 B）從表中任一結(jié)點(diǎn)動(dòng)身都能拜望到整個(gè)鏈表 C）在進(jìn)行插入,刪除運(yùn)算時(shí),能更好的保證鏈表不斷開(kāi) D）已知某個(gè)結(jié)點(diǎn)的位置后,能夠簡(jiǎn)潔的找到它的直接前件 解析： 循環(huán)鏈表就是將單向鏈表中最終一個(gè)結(jié)點(diǎn)的指針指向頭結(jié)點(diǎn),使整個(gè)鏈 表構(gòu)成一個(gè)環(huán)形,這樣的結(jié)構(gòu)使得從表中的任一結(jié)點(diǎn)動(dòng)身都能拜望到整個(gè)鏈表； 故此題答案應(yīng)當(dāng)為選項(xiàng) B）； （ 2）棧底至棧頂依次存放

38、元素 A,B,C,D,在第五個(gè)元素 E 入棧前,棧中元素 可以出棧,就出棧序列可能是 A） ABCED B） DCBEA C） DBCEA D） CDABE 解析： 棧操作原就上“后進(jìn)先出” ,棧底至棧頂依次存放元素 A, B,C,D,就 說(shuō)明這 4 個(gè)元素中 D 是最終進(jìn)棧, B,C 處于中間, A 最早進(jìn)棧；所以出棧時(shí)一 定是先出 D,再出 C,最終出 A；故此題答案應(yīng)當(dāng)為選項(xiàng) B）； （ 3）對(duì)長(zhǎng)度為 N 的線(xiàn)性表進(jìn)行次序查找,在最壞情形下所需要的比較次數(shù)為 第 21 頁(yè),共 151 頁(yè)； A N+1 B N C N+1/2 D N/2 解析： 答案 B ,很簡(jiǎn)潔,我們的二級(jí)程序設(shè)計(jì)語(yǔ)言

39、書(shū)中都有此算法,另外仍要 把握二分法查找,這也是我們二級(jí)中?？嫉模荒敲炊址ㄗ顗牡那樾螢槎?少次呢？ log2 n的最小整數(shù)值；比如 n 為 4,最壞的情形要比較 3 次； n 為 18,最壞的情形要比較 5 次； （ 1）以下表達(dá)中正確選項(xiàng) A）線(xiàn)性表是線(xiàn)性結(jié)構(gòu) B）棧與隊(duì)列是非線(xiàn)性結(jié)構(gòu) C）線(xiàn)性鏈表是非線(xiàn)性結(jié)構(gòu) D）二叉樹(shù)是線(xiàn)性結(jié)構(gòu) 解析： 線(xiàn)性表是一種線(xiàn)性結(jié)構(gòu),數(shù)據(jù)元素在線(xiàn)性表中的位置只取決于它們自己 的序號(hào),即數(shù)據(jù)元素之間的相對(duì)位置是線(xiàn)性的；棧,隊(duì)列,線(xiàn)性鏈表實(shí)際上也 是線(xiàn)性表,故也是線(xiàn)性結(jié)構(gòu)；樹(shù)是一種簡(jiǎn)潔的非線(xiàn)性結(jié)構(gòu)；故此題答案應(yīng)當(dāng)為 選項(xiàng) A）； （ 2）非空的循環(huán)單鏈表 head

40、 的尾結(jié)點(diǎn)（由 p 所指向）,中意 A） p-next=NULL B） p=NULL C） p-next=head D） p=head 第 22 頁(yè),共 151 頁(yè)解析： 循環(huán)鏈表就是將鏈表的最終一個(gè)結(jié)點(diǎn)指向鏈表頭結(jié)點(diǎn)（或第一個(gè)結(jié)點(diǎn)） , 即 p-next=head ；故此題答案應(yīng)當(dāng)為選項(xiàng) C）； （ 3）已知數(shù)據(jù)表 A 中每個(gè)元素距其最終位置不遠(yuǎn),為節(jié)省時(shí)間,應(yīng)接受的算法 是 A）堆排序 B）直接插入排序 C）快速排序 D）直接選擇排序 解析： 當(dāng)數(shù)據(jù)表 A 中每個(gè)元素距其最終位置不遠(yuǎn),說(shuō)明數(shù)據(jù)表 A 按關(guān)鍵字值 基 本有序,在待排序序列基本有序的情形下,接受插入排序所用時(shí)間最少,故答 案為

41、選項(xiàng) B）； （ 1）假設(shè)線(xiàn)性表的長(zhǎng)度為 n,就在最壞情形下,冒泡排序需要的比較次數(shù)為 nA） log2 B） n C） O（） D） n（n-1 ）/2 解析： 假設(shè)線(xiàn)性表的長(zhǎng)度為 n,就在最壞情形下,冒泡排序要經(jīng)過(guò) n/2 遍的從 前往后的掃描和 n/2 遍的從后往前的掃描,需要的比較次數(shù)為 n（ n-1 ）/2 ；故 此題答案應(yīng)當(dāng)為選項(xiàng) D）； （ 2）算法分析的目的是 A）找出數(shù)據(jù)結(jié)構(gòu)的合理性 B）找出算法中輸入和輸出之間的關(guān)系 C）分析算法的易懂性和牢靠性 第 23 頁(yè),共 151 頁(yè)D）分析算法的效率以求改進(jìn) 解析： 算法分析是指對(duì)一個(gè)算法的運(yùn)行時(shí)間和占用空間做定量的分析,一般計(jì)

42、算出相應(yīng)的數(shù)量級(jí),常用時(shí)間復(fù)雜度和空間復(fù)雜度表示；分析算法的目的就是 要降低算法的時(shí)間復(fù)雜度和空間復(fù)雜度,提高算法的執(zhí)行效率；故此題答案應(yīng) 該為選項(xiàng) D）； （ 3）線(xiàn)性表 L=（a1,a2,a3, ai , an）,以下說(shuō)法正確選項(xiàng) A）每個(gè)元素都有一個(gè)直接前件和直接后件 B）線(xiàn)性表中至少要有一個(gè)元素 C）表中諸元素的排列次序必需是由小到大或由大到小 D）除第一個(gè)元素和最終一個(gè)元素外,其余每個(gè)元素都有一個(gè)且只有一個(gè)直接前 件和直接后件 解析： 線(xiàn)性表可以為空表；第一個(gè)元素沒(méi)有直接前件,最終一個(gè)元素沒(méi)有直接 后件；線(xiàn)性表的定義中,元素的排列并沒(méi)有規(guī)定大小次序；故此題答案應(yīng)當(dāng)為 選項(xiàng) D）； （

43、 4）在單鏈表中,增加頭結(jié)點(diǎn)的目的是 A）便利運(yùn)算的實(shí)現(xiàn) B）使單鏈表至少有一個(gè)結(jié)點(diǎn) C）標(biāo)識(shí)表結(jié)點(diǎn)中首結(jié)點(diǎn)的位置 D）說(shuō)明單鏈表是線(xiàn)性表的鏈?zhǔn)絻?chǔ)備實(shí)現(xiàn) 解析： 頭結(jié)點(diǎn)不僅標(biāo)識(shí)了表中首結(jié)點(diǎn)的位置,而且依據(jù)單鏈表（包含頭結(jié)點(diǎn)） 的結(jié)構(gòu),只要把握了表頭,就能夠拜望整個(gè)鏈表,因此增加頭結(jié)點(diǎn)目的是為了 便于運(yùn)算的實(shí)現(xiàn)；故此題答案應(yīng)當(dāng)為選項(xiàng) A）； （ 1）算法的空間復(fù)雜度是指 第 24 頁(yè),共 151 頁(yè)A）算法程序的長(zhǎng)度 B）算法程序中的指令條數(shù) C）算法程序所占的儲(chǔ)備空間 D）執(zhí)行過(guò)程中所需要的儲(chǔ)備空間 解析： 算法的復(fù)雜度主要包括算法的時(shí)間復(fù)雜度和算法的空間復(fù)雜度；所謂算 法的時(shí)間復(fù)雜度是指執(zhí)行

44、算法所需要的運(yùn)算工作量；算法的空間復(fù)雜度一般是 指執(zhí)行這個(gè)算法所需要的內(nèi)存空間；故此題答案應(yīng)當(dāng)為選項(xiàng) D）； （ 2）用鏈表表示線(xiàn)性表的優(yōu)點(diǎn)是 A）便于隨機(jī)存取 B）花費(fèi)的儲(chǔ)備空間較次序儲(chǔ)備少 C）便于插入和刪除操作 D）數(shù)據(jù)元素的物理次序與規(guī)律次序相同 解析： 鏈?zhǔn)絻?chǔ)備結(jié)構(gòu)克服了次序儲(chǔ)備結(jié)構(gòu)的缺點(diǎn)：它的結(jié)點(diǎn)空間可以動(dòng)態(tài)申請(qǐng) 和釋放；它的數(shù)據(jù)元素的規(guī)律次序靠結(jié)點(diǎn)的指針來(lái)指示,不需要移動(dòng)數(shù)據(jù)元素； 故鏈?zhǔn)絻?chǔ)備結(jié)構(gòu)下的線(xiàn)性表便于插入和刪除操作；故此題答案應(yīng)當(dāng)為選項(xiàng) C）； （ 3）數(shù)據(jù)結(jié)構(gòu)中,與所使用的運(yùn)算機(jī)無(wú)關(guān)的是數(shù)據(jù)的 A）儲(chǔ)備結(jié)構(gòu) B）物理結(jié)構(gòu) C）規(guī)律結(jié)構(gòu) D）物理和儲(chǔ)備結(jié)構(gòu) 解析： 數(shù)據(jù)

45、結(jié)構(gòu)概念一般包括 3 個(gè)方面的內(nèi)容,數(shù)據(jù)的規(guī)律結(jié)構(gòu),儲(chǔ)備結(jié)構(gòu)及 數(shù)據(jù)上的運(yùn)算集合；數(shù)據(jù)的規(guī)律結(jié)構(gòu)只抽象的反映數(shù)據(jù)元素之間的規(guī)律關(guān) 系,而不管它在運(yùn)算機(jī)中的儲(chǔ)備表示形式；故此題答案應(yīng)當(dāng)為選項(xiàng) C）； 第 25 頁(yè),共 151 頁(yè)（ 1）由兩個(gè)棧共享一個(gè)儲(chǔ)備空間的好處是 A）削減存取時(shí)間,降低下溢發(fā)生的機(jī)率 B）節(jié)省儲(chǔ)備空間,降低上溢發(fā)生的機(jī)率 C）削減存取時(shí)間,降低上溢發(fā)生的機(jī)率 D）節(jié)省儲(chǔ)備空間,降低下溢發(fā)生的機(jī)率 解析： 經(jīng)常一個(gè)程序中要用到多個(gè)棧,為了不發(fā)生上溢錯(cuò)誤,就必需給每個(gè)棧 支配一個(gè)足夠大的儲(chǔ)備空間；但實(shí)際中,很難精確地估量,如每個(gè)棧都支配過(guò) 大的儲(chǔ)備空間,勢(shì)必造成系統(tǒng)空間緊急；如

46、讓多個(gè)棧共用一個(gè)足夠大的連續(xù)存 儲(chǔ)空間,就可利用棧的動(dòng)態(tài)特性使他們的儲(chǔ)備空間互補(bǔ)；故此題答案應(yīng)當(dāng)為選 項(xiàng) B）； （ 2）設(shè)有兩個(gè)串 p 和 q,求 q 在 p 中首次顯現(xiàn)位置的運(yùn)算稱(chēng)作 A）連接 B）模式匹配 C）求子串 D）求串長(zhǎng) 解析： 子串的定位操作通常稱(chēng)作串的模式匹配,是各種串處理系統(tǒng)中最重要的 操作之一,算法的基本思想是：從主串的開(kāi)頭字符起和模式的第一個(gè)字符比較, 如相等就連續(xù)比較后續(xù)字符,否就從主串的下一個(gè)字符起再重新和模式的字符 比較,依次類(lèi)推,直至模式中的每一個(gè)字符依次和主串中的一個(gè)連續(xù)的字符序 列相等,稱(chēng)匹配勝利,否就稱(chēng)匹配不勝利； （ 3）以下關(guān)于隊(duì)列的表達(dá)中正確選項(xiàng) ；

47、 A. 在隊(duì)列中只能插入數(shù)據(jù) B. 在隊(duì)列中只能刪除數(shù)據(jù) 第 26 頁(yè),共 151 頁(yè)C. 隊(duì)列是先進(jìn)先出的線(xiàn)性表 D. 隊(duì)列是先進(jìn)后出的線(xiàn)性表 解析： C 隊(duì)列是先進(jìn)先出的,棧是先進(jìn)后出的, 2 者的區(qū)分確定要搞清楚； 1 算法的空間復(fù)雜度是指 A 算法程序的長(zhǎng)度 B 算法程序中的指令條數(shù) C執(zhí)行算法程序所占的儲(chǔ)備空間 D算法執(zhí)行過(guò)程中所需要的儲(chǔ)備空間 【答案】 D 【解析】算法的空間復(fù)雜度一般是指這個(gè)算法執(zhí)行時(shí)所需要的內(nèi)存空間,其中 包括算法程序所占的空間,輸入的初始數(shù)據(jù)所占的儲(chǔ)備空間以及算法執(zhí)行過(guò)程 中所需要的額外空間,其中額外空間仍包括算法程序執(zhí)行過(guò)程的工作單元以及 某種數(shù)據(jù)結(jié)構(gòu)所需要

48、的附加儲(chǔ)備空間； （ 2）線(xiàn)性表的鏈?zhǔn)絻?chǔ)備結(jié)構(gòu)是一種 A 隨機(jī)結(jié)構(gòu) B 次序結(jié)構(gòu) C索引結(jié)構(gòu) D散列結(jié)構(gòu) 【答案】 B 【解析】線(xiàn)性表的鏈?zhǔn)絻?chǔ)備結(jié)構(gòu)中的每一個(gè)儲(chǔ)備結(jié)點(diǎn)不僅含有一個(gè)數(shù)據(jù)元素, 仍包括指針,每一個(gè)指針指向一個(gè)與本結(jié)點(diǎn)有規(guī)律關(guān)系的結(jié)點(diǎn)；此類(lèi)儲(chǔ)備方式 屬于次序儲(chǔ)備； 第 27 頁(yè),共 151 頁(yè)（ 3）設(shè)有以下二叉樹(shù)：對(duì)此二叉樹(shù)先序遍歷的結(jié)果是 AABCDEF BDBEAFC CABDECF DDEBFCA 【答案】 C 【解析】二叉樹(shù)的遍歷分為先序,中序,后序三種不同方式；此題要求先序遍 歷；遍歷次序應(yīng)當(dāng)為：拜望根結(jié)點(diǎn) - 先序遍歷左子樹(shù) - 先序遍歷右子樹(shù)；按 照定義,先序遍歷序列

49、是 ABDEC；F （ 1）算法分析的目的是 ； A）找出數(shù)據(jù)結(jié)構(gòu)的合理性 B ）找出算法中輸入和輸出之間的關(guān)系 C）分析算法的易懂性和牢靠性 答案： D D）分析算法的效率以求改進(jìn) 評(píng)析：算法分析是指對(duì)一個(gè)算法的運(yùn)行時(shí)間和占用空間做定量的分析,一般計(jì) 算出相應(yīng)的數(shù)量級(jí),常用時(shí)間復(fù)雜度和空間復(fù)雜度表示；分析算法的目的就是 要降低算法的時(shí)間復(fù)雜度和空間復(fù)雜度,提高算法的執(zhí)行效率； （ 3）已知數(shù)據(jù)表 A 中每個(gè)元素距其最終位置不遠(yuǎn),為節(jié)省時(shí)間,應(yīng)接受的算法 是； B）直接插入排序 D）直接選擇排序 A）堆排序 C）快速排序 答案： B 評(píng)析：當(dāng)數(shù)據(jù)表 A 中每個(gè)元素距其最終位置不遠(yuǎn),說(shuō)明數(shù)據(jù)表

50、A 按關(guān)鍵字值基 本有序,在待排序序列基本有序的情形下,接受插入排序所用時(shí)間最少,故答 第 28 頁(yè),共 151 頁(yè)案為選項(xiàng) B； （ 4）用鏈表表示線(xiàn)性表的優(yōu)點(diǎn)是 ； A）便于插入和刪除操作 B）數(shù)據(jù)元素的物理次序與規(guī)律次序相同 C）花費(fèi)的儲(chǔ)備空間較次序儲(chǔ)備少 答案： A D）便于隨機(jī)存取 評(píng)析：鏈?zhǔn)絻?chǔ)備結(jié)構(gòu)克服了次序儲(chǔ)備結(jié)構(gòu)的缺點(diǎn)：它的結(jié)點(diǎn)空間可以動(dòng)態(tài)申請(qǐng) 和釋放；它的數(shù)據(jù)元素的規(guī)律次序靠結(jié)點(diǎn)的指針來(lái)指示,不需要移動(dòng)數(shù)據(jù)元素； 故鏈?zhǔn)絻?chǔ)備結(jié)構(gòu)下的線(xiàn)性表便于插入和刪除操作； 1. 以下數(shù)據(jù)結(jié)構(gòu)中不屬于線(xiàn)性數(shù)據(jù)結(jié)構(gòu)的是 ； A ,隊(duì)列 B ,線(xiàn)性表 C ,二叉樹(shù) D ,棧 解析 : 線(xiàn)性表,棧

51、和隊(duì)列等數(shù)據(jù)結(jié)構(gòu)所表達(dá)和處理的數(shù)據(jù)以線(xiàn)性結(jié)構(gòu)為組織形 式；棧是一種特別的線(xiàn)性表,這種線(xiàn)性表只能在固定的一端進(jìn)行插入和刪除操 作,答應(yīng)插入和刪除的一端稱(chēng)為棧頂,另一端稱(chēng)為棧底；一個(gè)新元素只能從棧 頂一端進(jìn)入,刪除時(shí),只能刪除棧頂?shù)脑?即剛剛被插入的元素；所以棧又 稱(chēng)后進(jìn)先出表（ Last In First Out ）；隊(duì)列可看作是插入在一端進(jìn)行,刪除在 另一端進(jìn)行的線(xiàn)性表,答應(yīng)插入的一端稱(chēng)為隊(duì)尾,答應(yīng)刪除的一端稱(chēng)為隊(duì)頭； 在隊(duì)列中,只能刪除隊(duì)頭元素,隊(duì)列的最終一個(gè)元素確定是最新入隊(duì)的元素； 因此隊(duì)列又稱(chēng)先進(jìn)先出表（ First In First Out ）； 此題答案為 C； 5. 以下關(guān)于棧

52、的表達(dá)中正確選項(xiàng) ； A,在棧中只能插入數(shù)據(jù) B,在棧中只能刪除數(shù)據(jù) C,棧是先進(jìn)先出的線(xiàn)性表 D,棧是先進(jìn)后出的線(xiàn)性表 解析 : 棧是限定在一端進(jìn)行插入與刪除的線(xiàn)性表； 棧是依據(jù) 先進(jìn)后出 的或后進(jìn)先出的原就組織數(shù)據(jù)的,因此,棧也被稱(chēng)為 先進(jìn)后出 表或 后進(jìn)先出 表； 此題答案是 D； 7. 對(duì)長(zhǎng)度為 N 的線(xiàn)性表進(jìn)行次序查找,在最壞情形下所需要的比較次數(shù)為 第 29 頁(yè),共 151 頁(yè)； A,N+1 B,NC,N+1/2 D,N/2 解析 : 在進(jìn)行次序查找過(guò)程中,假如線(xiàn)性表中被查的元素是線(xiàn)性表中的最終一 個(gè),或者被查元素根本不在線(xiàn)性表中,就為了查找這個(gè)元素需要與線(xiàn)性表中所 有元素進(jìn)行比較

53、,這是次序查找最壞的情形； 此題答案為 B； 1. 在一棵二叉樹(shù)上第 5 層的結(jié)點(diǎn)數(shù)最多是； A, 8 B, 16 C, 32 D, 15 解析 : 依據(jù)二叉樹(shù)的性質(zhì)：二叉樹(shù)第 i （ i 1）層上至多有 2 個(gè)結(jié)點(diǎn)；得到第 5層的結(jié)點(diǎn)數(shù)最多是 16； 此題答案為 B； 3. 以下表達(dá)中正確選項(xiàng) ； A,線(xiàn)性表是線(xiàn)性結(jié)構(gòu) B,棧與隊(duì)列是非線(xiàn)性結(jié)構(gòu) C,線(xiàn)性鏈表是非線(xiàn)性結(jié)構(gòu) D,二叉樹(shù)是線(xiàn)性結(jié)構(gòu) 解析 : 依據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后間關(guān)系的復(fù)雜程度,一般將數(shù)據(jù)結(jié)構(gòu) 分為兩大類(lèi)型：線(xiàn)性結(jié)構(gòu)與非線(xiàn)性結(jié)構(gòu)； 假如一個(gè)非空的數(shù)據(jù)結(jié)構(gòu)中意以下兩個(gè)條件：（ 1）有且只有一個(gè)根結(jié)點(diǎn)； （ 2）每一個(gè)結(jié)點(diǎn)

54、最多有一個(gè)前件,也最多有一個(gè)后件；就稱(chēng)該數(shù)據(jù)結(jié)構(gòu)為線(xiàn)性 結(jié)構(gòu),又稱(chēng)線(xiàn)性表； 所以線(xiàn)性表,棧與隊(duì)列,線(xiàn)性鏈表都是線(xiàn)性結(jié)構(gòu),而二叉樹(shù)是非線(xiàn)性結(jié)構(gòu)； 此題答案是 A； 7. 在以下選項(xiàng)中,哪個(gè)不是一個(gè)算法一般應(yīng)當(dāng)具有的基本特點(diǎn) ； A,確定性 B,可行性 第 30 頁(yè),共 151 頁(yè)C,無(wú)窮性 D,擁有足夠的情報(bào) 解析 : 作為一個(gè)算法,一般應(yīng)具有以下幾個(gè)基本特點(diǎn)； 1 可行性 2 確定性 3 有窮性 4 擁有足夠的情報(bào) 此題答案為 C； 5. 在運(yùn)算機(jī)中,算法是指 ； A,查詢(xún)方法 B,加工方法 C,解題方案的精確而完整的描述 D,排序方法 解析 : 運(yùn)算機(jī)算法是指解題方案的精確而完整的描述,它有

55、以下幾個(gè)基本特點(diǎn)： 可行性,確定性,有窮性和擁有足夠的情報(bào)； 此題答案為 C； 7. 在單鏈表中,增加頭結(jié)點(diǎn)的目的是 ； A,便利運(yùn)算的實(shí)現(xiàn) B,使單鏈表至少有一個(gè)結(jié)點(diǎn) C,標(biāo)識(shí)表結(jié)點(diǎn)中首結(jié)點(diǎn)的位置 D,說(shuō)明單鏈表是線(xiàn)性表的鏈?zhǔn)絻?chǔ)備實(shí)現(xiàn) 解析 : 頭結(jié)點(diǎn)不僅標(biāo)識(shí)了表中首結(jié)點(diǎn)的位置,而且依據(jù)單鏈表（包含頭結(jié)點(diǎn)）的 結(jié)構(gòu),只要把握了表頭,就能夠拜望整個(gè)鏈表,因此增加頭結(jié)點(diǎn)目的是為了便 于運(yùn)算的實(shí)現(xiàn)； 此題答案為 A； 1. 數(shù)據(jù)的儲(chǔ)備結(jié)構(gòu)是指 ； A,儲(chǔ)備在外存中的數(shù)據(jù) B,數(shù)據(jù)所占的儲(chǔ)備空間量 C,數(shù)據(jù)在運(yùn)算機(jī)中的次序儲(chǔ)備方式 D,數(shù) 據(jù)的規(guī)律結(jié)構(gòu)在運(yùn)算機(jī)中的表示 解析 : 此題考查的是數(shù)據(jù)結(jié)構(gòu)

56、的基本概念； 數(shù)據(jù)的規(guī)律結(jié)構(gòu)在運(yùn)算機(jī)儲(chǔ)備空間中的存放形式形式稱(chēng)為數(shù)據(jù)的儲(chǔ)備結(jié)構(gòu) 第 31 頁(yè),共 151 頁(yè)（也稱(chēng)數(shù)據(jù)的物理結(jié)構(gòu)）； 故此題答案為 D； 2. 以下關(guān)于棧的描述中錯(cuò)誤選項(xiàng) ； A,棧是先進(jìn)后出的線(xiàn)性表 B,棧只能次序儲(chǔ)備 C,棧具有記憶作用 D,對(duì)棧的插入與刪除操作中,不需要轉(zhuǎn)變棧底指針 解析 : 此題考查的是棧和隊(duì)列； 棧是一種特別的線(xiàn)性表,這種線(xiàn)性表只能在固 定的一端進(jìn)行插入和刪除操 作,答應(yīng)插入和刪除的一端稱(chēng)為棧頂,另一端稱(chēng)為棧底；一個(gè)新元素只能從棧 頂一端進(jìn)入,刪除時(shí),只能刪除棧頂?shù)脑?即剛剛被插入的元素；所以棧又 稱(chēng)先進(jìn)后出表（ FILO-First In Last

57、 Out ）；線(xiàn)性表可以次序儲(chǔ)備,也可以鏈 式儲(chǔ)備,而棧是一種線(xiàn)性表,也可以接受鏈?zhǔn)絻?chǔ)備結(jié)構(gòu)； 故此題答案為 B； 3. 對(duì)于長(zhǎng)度為 n 的線(xiàn)性表,在最壞情形下,以下各排序法所對(duì)應(yīng)的比較次數(shù)中 正確選項(xiàng)； A,冒泡排序?yàn)?n/2 B,冒泡排序?yàn)?nC,快速排序?yàn)?n D,快速排序?yàn)?nn-1/2 解析 : 此題考查的是基本排序算法； 假設(shè)線(xiàn)性表的長(zhǎng)度為 n,就在最壞情形下, 冒泡排序需要經(jīng)過(guò) n/2 遍的從前 往后掃描和 n/2 遍的從后往前掃描,需要比較次數(shù)為 最壞情形比較次數(shù)也是 nn-1/2 ； 故此題答案為 D； nn-1/2 ；快速排序法的 4. 對(duì)長(zhǎng)度為 n 的線(xiàn)性表進(jìn)行次序查找,

58、在最壞情形下所需要的比較次數(shù)為 ； A, log2n B, n/2 C, n D, n+1 第 32 頁(yè),共 151 頁(yè)解析 : 此題考查的是次序查找； 在進(jìn)行次序查找過(guò)程中,假如線(xiàn)性表中的第一個(gè)元素就是被查找元素,就 只需做一次比較就查找勝利,查找效率最高；但假如被查找的元素是線(xiàn)性表中 的最終一個(gè)元素,或者被查找的元素根本就不在線(xiàn)性表中,就為了查找這個(gè)元 素需要與線(xiàn)性表中全部的元素進(jìn)行比較,這是次序查找的最壞情形；所以對(duì)長(zhǎng) 度為 n 的線(xiàn)性表進(jìn)行次序查找,在最壞情形下需要比較 n 次； 故此題答案為 C； 5. 以下對(duì)于線(xiàn)性鏈表的描述中正確選項(xiàng) ； A,儲(chǔ)備空間不愿定是連續(xù),且各元素的儲(chǔ)備次

59、序是任意的 B,儲(chǔ)備空間不愿定是連續(xù),且前件元素確定儲(chǔ)備在后件元素的前面 C,儲(chǔ)備空間必需連續(xù),且前件元素確定儲(chǔ)備在后件元素的前面 D,儲(chǔ)備空間必需連續(xù),且各元素的儲(chǔ)備次序是任意的 解析 : 此題考查的是線(xiàn)性單鏈表,雙向鏈表與循環(huán)鏈表的結(jié)構(gòu)及其基本運(yùn)算； 在鏈?zhǔn)絻?chǔ)備結(jié)構(gòu)中,儲(chǔ)備數(shù)據(jù)結(jié)構(gòu)的儲(chǔ)備空間可以不連續(xù),各數(shù)據(jù)結(jié)點(diǎn)的 儲(chǔ)備次序與數(shù)據(jù)元素之間的規(guī)律關(guān)系可以不一樣,而數(shù)據(jù)元素之間的規(guī)律關(guān)系 是由指針域來(lái)確定的； 故此題答案為 A； 1. 算法的時(shí)間復(fù)雜度是指 ； A,執(zhí)行算法程序所需要的時(shí)間 B,算法程序的長(zhǎng)度 C,算法執(zhí)行過(guò)程中所 需要的基本運(yùn)算次數(shù) D,算法程序中的指令條數(shù) 解析 : 所謂算

60、法的時(shí)間復(fù)雜度,是指執(zhí)行算法所需要的運(yùn)算工作量； 為了能夠比較客觀地反映出一個(gè)算法的效率,在度量一個(gè)算法的工作量時(shí), 不僅應(yīng)當(dāng)與所使用的運(yùn)算機(jī),程序設(shè)計(jì)語(yǔ)言以及程序編制者無(wú)關(guān),而且仍應(yīng)當(dāng) 與算法實(shí)現(xiàn)過(guò)程中的許多細(xì)節(jié)無(wú)關(guān)；為此,可以用算法在執(zhí)行過(guò)程中所需基本 運(yùn)算的執(zhí)行次數(shù)來(lái)度量算法的工作量； 此題答案是 C； 2. 以下表達(dá)中正確選項(xiàng) ； A,線(xiàn)性表是線(xiàn)性結(jié)構(gòu) B,棧與隊(duì)列是非線(xiàn)性結(jié)構(gòu) C,線(xiàn)性鏈表是非線(xiàn)性結(jié)構(gòu) 第 33 頁(yè),共 151 頁(yè)D,二叉樹(shù)是線(xiàn)性結(jié)構(gòu) 解析 : 依據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后間關(guān)系的復(fù)雜程度,一般將數(shù)據(jù)結(jié)構(gòu) 分為兩大類(lèi)型：線(xiàn)性結(jié)構(gòu)與非線(xiàn)性結(jié)構(gòu)； 假如一個(gè)非空的數(shù)據(jù)結(jié)