大學(xué)計(jì)算機(jī)基礎(chǔ)-07數(shù)據(jù)結(jié)構(gòu)與算法課件

1、第7章數(shù)據(jù)結(jié)構(gòu)與算法7.1 算 法7.2 數(shù)據(jù)結(jié)構(gòu)的基本概念7.3 線性表及其順序存儲(chǔ)結(jié)構(gòu)7.4 棧和隊(duì)列7.5 線性鏈表7.6 樹(shù)與二叉樹(shù)7.7 查找與排序技術(shù)習(xí)題8/20/202217.1 算 法7.1.1 算法的基本概念1算法的基本特征 （1）可行性 （2）確定性 （3）有窮性 （4）有零個(gè)或多個(gè)輸入 （5）有一個(gè)或多個(gè)輸出一個(gè)算法，就是一組定義了運(yùn)算順序的規(guī)則，并且每個(gè)規(guī)則都是有效的、明確的，此運(yùn)算順序?qū)⒃谟邢薜牟襟E后終止。8/20/20222對(duì)數(shù)據(jù)對(duì)象的運(yùn)算和操作，算法的控制結(jié)構(gòu)。2算法的基本要素8/20/20223（1）算法中對(duì)數(shù)據(jù)的運(yùn)算和操作 算術(shù)運(yùn)算：主要包括加、減、乘、除等運(yùn)

2、算。 邏輯運(yùn)算：主要包括“邏輯與”、“邏輯或”、“邏輯非”等運(yùn)算。 關(guān)系運(yùn)算：主要包括“大于”、“大于或等于”、“小于”、“小于或等于”、“等于”、“不等于”等運(yùn)算。 數(shù)據(jù)傳輸：主要包括賦值、輸入、輸出等操作。8/20/20224（2）算法的控制結(jié)構(gòu)算法中各種操作之間的執(zhí)行順序稱(chēng)為算法的控制結(jié)構(gòu)。一個(gè)算法一般都可以用順序結(jié)構(gòu)、選擇結(jié)構(gòu)、和循環(huán)結(jié)構(gòu)這三種基本控制結(jié)構(gòu)組合而成。8/20/202253算法設(shè)計(jì)基本方法 （1） 列舉法 列舉法就是根據(jù)所要解決的問(wèn)題，把所有可能的情況都一一列舉出來(lái)，并用問(wèn)題中給定的條件來(lái)檢驗(yàn)?zāi)男┦切枰?，哪些是不需要的。例如：設(shè)x,y為非負(fù)整數(shù)，求滿(mǎn)足方程 2x+3y=

3、10的x,y。8/20/20226（2）歸納法 歸納法的基本思想是通過(guò)列舉少量的特殊情況，經(jīng)過(guò)分析，最后找出一般的關(guān)系。 可以看出，歸納法可以解決列舉量為無(wú)限的問(wèn)題。 8/20/20227（3）遞推 遞推是指從已知的初始條件出發(fā)，逐步推出所要求的結(jié)果。例如：求 x2=a 的遞推公式：8/20/20228（4）遞歸 在解決某些復(fù)雜問(wèn)題時(shí)，為了降低問(wèn)題的復(fù)雜程度（如問(wèn)題的規(guī)模等），可以將問(wèn)題逐層分解，最后歸結(jié)為一些最簡(jiǎn)單的問(wèn)題。8/20/20229例7.2 有5個(gè)人坐在一起，問(wèn)第5個(gè)人的歲數(shù)，他說(shuō)比第4個(gè)人大2歲。問(wèn)第4個(gè)人的歲數(shù)，他說(shuō)比第3個(gè)人大2歲。問(wèn)第3個(gè)人的歲數(shù)，他說(shuō)比第2個(gè)人大2歲。問(wèn)第

4、2個(gè)人的歲數(shù)，他說(shuō)比第1個(gè)人大2歲。問(wèn)第1個(gè)人的歲數(shù)，他說(shuō)是10歲。請(qǐng)問(wèn)第5個(gè)人多大。 8/20/202210這個(gè)問(wèn)題可以用遞歸方法解決。遞歸過(guò)程如下： age（5）age（4）十2 age（4）age（3）十2 age（3）age（2）十2 age（2）age（1）十2 age（ l）108/20/202211（5）減半遞推技術(shù) “減半”是指將問(wèn)題的規(guī)模減半，而問(wèn)題的性質(zhì)不變；“遞推”是指重復(fù)“減半”的過(guò)程。8/20/202212 7.1.2 算法的復(fù)雜度 可分為時(shí)間復(fù)雜度和空間復(fù)雜度。 1算法的時(shí)間復(fù)雜度 算法的時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量。 例如：兩個(gè)n階方陣的乘積的乘法次數(shù)

5、為n3。 兩種常用方法：（1） 平均性態(tài)（2）最壞情況復(fù)雜性8/20/2022132算法的空間復(fù)雜度算法的空間復(fù)雜度是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間。類(lèi)似算法的時(shí)間復(fù)雜度，空間復(fù)雜度作為算法所需存儲(chǔ)空間的度量。 8/20/2022147.2 數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)主要研究三個(gè)問(wèn)題： （1）數(shù)據(jù)集合中各數(shù)據(jù)元素之間所固有的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)； （2）在對(duì)數(shù)據(jù)進(jìn)行處理時(shí)，各數(shù)據(jù)元素在計(jì)算機(jī)中的存儲(chǔ)關(guān)系，即數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)； （3）對(duì)各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算。8/20/202215例7.5 無(wú)序表的順序查找與有序表的對(duì)分查找。7.2 數(shù)據(jù)結(jié)構(gòu)的基本概念7.2.1 什么是數(shù)據(jù)結(jié)構(gòu)8/20/20

6、2216現(xiàn)實(shí)世界中存在的一切個(gè)體都可以是數(shù)據(jù)元素（簡(jiǎn)稱(chēng)元素）。例如： 春、夏、秋、冬； 26、56、65、 73、26、； 父親、兒子、女兒。數(shù)據(jù)元素之間的關(guān)系可用前后件關(guān)系例如， “春”是“夏”前件，“夏”是“春”的后件。8/20/2022171數(shù)據(jù)的邏輯結(jié)構(gòu)指數(shù)據(jù)之間的邏輯關(guān)系，與它們?cè)谟?jì)算機(jī)中的存儲(chǔ)位置無(wú)關(guān)。有兩個(gè)基本要素： 表示數(shù)據(jù)元素的信息，通常記為D； 表示各數(shù)據(jù)元素之間的前后件關(guān)系，通常記為R。例7.2 一年四季的數(shù)據(jù)結(jié)構(gòu)可以表示成 B=（D，R） D=春，夏，秋，冬 R=（春，夏），（夏，秋），（秋，冬）8/20/202218例7.3 家庭成員數(shù)據(jù)結(jié)構(gòu)可以表示成 B=（D， R

7、） D=父親，兒子，女兒 R=（父親，兒子），（父親，女兒）8/20/2022192數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) 數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放形式稱(chēng)為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)（也稱(chēng)數(shù)據(jù)的物理結(jié)構(gòu)）。 一種數(shù)據(jù)的邏輯結(jié)構(gòu)可以表示成多種存儲(chǔ)結(jié)構(gòu)。 常用的存儲(chǔ)結(jié)構(gòu)有順序、鏈接、索引等存儲(chǔ)結(jié)構(gòu)。8/20/2022207.2.2 數(shù)據(jù)結(jié)構(gòu)的圖形表示8/20/2022217.2.3 線性結(jié)構(gòu)與非線性結(jié)構(gòu)如果一個(gè)數(shù)據(jù)結(jié)構(gòu)滿(mǎn)足：（1）有且只有一個(gè)根結(jié)點(diǎn)；（2）每個(gè)結(jié)點(diǎn)最多有一個(gè)前件，也最多有一個(gè)后件。則稱(chēng)該數(shù)據(jù)結(jié)構(gòu)為線性結(jié)構(gòu)。線性結(jié)構(gòu)又稱(chēng)線性表。8/20/2022227.3 線性表及其順序存儲(chǔ)結(jié)構(gòu)7.3.1 線性表的基本概

8、念線性表是指n個(gè)數(shù)據(jù)元素的有限序列。線性表可以表示為 （a1，a2，ai，an），當(dāng)n=0時(shí)，稱(chēng)為空表。 8/20/2022237.3.2 線性表的順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)的特點(diǎn)如下：（1）線性表中所有元素所占的存儲(chǔ)空間是連續(xù)的；（2）線性表中各數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存放的。8/20/2022247.3.3 順序表的插入運(yùn)算8/20/2022257.3.4 線性表的刪除運(yùn)算8/20/2022267.4 棧和隊(duì)列7.4.1 棧及其基本運(yùn)算 1棧的基本概念棧（stack）是限定僅在一端進(jìn)行插入和刪除運(yùn)算的線性表。在棧中，允許插入與刪除的一端稱(chēng)為棧頂，而不允許插入與刪除的另一端稱(chēng)為棧底。8

9、/20/202227棧的順序存儲(chǔ)結(jié)構(gòu)如圖所示。8/20/2022282棧的基本運(yùn)算 有三種：入棧、退棧與讀棧頂元素。（1） 入棧運(yùn)算首先將棧頂指針進(jìn)一，然后將新元素插入到棧頂指針指向的位置；8/20/202229（2） 退棧運(yùn)算首先將棧頂元素賦給一個(gè)指定的變量，然后將棧頂指針退一。（3） 讀棧頂元素是指將棧頂元素賦給一個(gè)指定的變量。棧頂指針不會(huì)改變。8/20/2022307.4.2 隊(duì)列及其基本運(yùn)算1隊(duì)列的基本概念隊(duì)列（queue）是在表的一端進(jìn)行插入，在表的另一端進(jìn)行刪除的線性表。在隊(duì)列中，允許插入的一端稱(chēng)為隊(duì)尾， 允許刪除的一端稱(chēng)為隊(duì)頭。隊(duì)列又稱(chēng)為“先進(jìn)先出”或“后進(jìn)后出”的線性表。在隊(duì)列

10、中，常用指針front 指向隊(duì)頭，用rear指向隊(duì)尾，如圖所示。8/20/202231圖7.11是在隊(duì)列中進(jìn)行插入與刪除的示意圖。 8/20/2022327.5 線性鏈表7.5.1 線性鏈表的基本概念1線性鏈表其鏈表結(jié)構(gòu)如圖（a）所示。實(shí)際上，常用圖（b）來(lái)表示它們的邏輯關(guān)系。8/20/202233雙向鏈表：一個(gè)指向其前件結(jié)點(diǎn)，稱(chēng)為前件指針或左指針；另一指向其后件結(jié)點(diǎn)，稱(chēng)為后件指針或右指針。8/20/2022347.6 樹(shù)與二叉樹(shù)7.6.1 樹(shù)的基本概念樹(shù)（tree）是一種非線性結(jié)構(gòu)，其所有數(shù)據(jù)元素之間的關(guān)系具有明顯的層次特點(diǎn)。8/20/202235實(shí)際上，能用樹(shù)結(jié)構(gòu)表示的例子有許多。8/20

11、/202236樹(shù)的基本特征和基本術(shù)語(yǔ)：每一個(gè)結(jié)點(diǎn)只有一個(gè)前件，稱(chēng)為父結(jié)點(diǎn)。沒(méi)有前件的結(jié)點(diǎn)只有一個(gè)，稱(chēng)為根結(jié)點(diǎn)（簡(jiǎn)稱(chēng)根）。每一個(gè)結(jié)點(diǎn)可以有多個(gè)后件，稱(chēng)為該結(jié)點(diǎn)的子結(jié)點(diǎn)。沒(méi)有后件的結(jié)點(diǎn)稱(chēng)為葉子結(jié)點(diǎn)。個(gè)結(jié)點(diǎn)所擁有的后件的個(gè)數(shù)稱(chēng)為該結(jié)點(diǎn)的度。所有結(jié)點(diǎn)中的最大的度稱(chēng)為樹(shù)的度。樹(shù)的最大層數(shù)稱(chēng)為樹(shù)的深度。以某結(jié)點(diǎn)的一個(gè)子結(jié)點(diǎn)為根構(gòu)成的樹(shù)稱(chēng)為該結(jié)點(diǎn)的一棵 子樹(shù)。8/20/2022377.6.2 二叉樹(shù)及其基本運(yùn)算1二叉樹(shù)的基本概念兩個(gè)特點(diǎn)： 非空二叉樹(shù)只有一個(gè)根結(jié)點(diǎn)； 每個(gè)結(jié)點(diǎn)最多有兩棵子樹(shù)，且分別稱(chēng)為該結(jié)點(diǎn)的左子樹(shù)與右子樹(shù)。8/20/202238圖中所示的是4顆不同的二叉樹(shù)，但如果作為樹(shù)，它們就相同了。8/

12、20/2022392滿(mǎn)二叉樹(shù)與完全二叉樹(shù)（1） 滿(mǎn)二叉樹(shù)在一顆二叉樹(shù)中，如果所有分支結(jié)點(diǎn)都存在左子樹(shù)和右子樹(shù)，并且所有葉子結(jié)點(diǎn)都在同一層上，這樣的二叉樹(shù)稱(chēng)為滿(mǎn)二叉樹(shù)。8/20/202240（2） 完全二叉樹(shù)完全二叉樹(shù)是指除最后一層外，每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值，而在最后一層上只缺少右邊的若干結(jié)點(diǎn)。8/20/2022413二叉樹(shù)的基本性質(zhì)二叉樹(shù)具有下列重要性質(zhì)：性質(zhì)1 在二叉樹(shù)中，第i層的結(jié)點(diǎn)數(shù)最多為2i-1個(gè)（i1）。性質(zhì)2 在深度為k的二叉樹(shù)中，結(jié)點(diǎn)總數(shù)最多為2k-1個(gè)（k1）。8/20/202242例如，在圖7.25所示的二叉樹(shù)中，有5個(gè)葉子結(jié)點(diǎn)，有4個(gè)度為2的結(jié)點(diǎn)，度為0的結(jié)點(diǎn)比度為2

13、的結(jié)點(diǎn)多一個(gè)。性質(zhì)3 對(duì)任意一棵二叉樹(shù)，度為0的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）總是比度為2的結(jié)點(diǎn)多一個(gè)。8/20/202243性質(zhì)4 （1）具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，其深度至少為log2n+1，其中l(wèi)og2n表示取log2n的整數(shù)部分。（2）具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為log2n+1。8/20/202244性質(zhì)5 如果對(duì)一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的結(jié)點(diǎn)從1到n按層序編號(hào)，則對(duì)任一結(jié)點(diǎn)i（1in），有（1）如果i=1，則結(jié)點(diǎn)i是二叉樹(shù)的根，它沒(méi)有父結(jié)點(diǎn)；如果i1，則其父結(jié)點(diǎn)編號(hào)為i/2。（2）如果2in，則結(jié)點(diǎn)i無(wú)左子結(jié)點(diǎn)（結(jié)點(diǎn)i為葉子結(jié)點(diǎn)）；否則，其左子結(jié)點(diǎn)是結(jié)點(diǎn)2i。（3）如果2i+1n，則結(jié)點(diǎn)i無(wú)右子

14、結(jié)點(diǎn)；否則，其右子結(jié)點(diǎn)是結(jié)點(diǎn)2i+1。根據(jù)完全二叉樹(shù)的這個(gè)性質(zhì)，如果按從上到下、從左到右順序存儲(chǔ)完全二叉樹(shù)的各結(jié)點(diǎn)，則很容易確定每一個(gè)結(jié)點(diǎn)的父結(jié)點(diǎn)、左子結(jié)點(diǎn)和右子結(jié)點(diǎn)的位置。 8/20/2022457.6.3 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)二叉樹(shù)通常采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。用于存儲(chǔ)二叉樹(shù)中各元素的存儲(chǔ)結(jié)點(diǎn)由兩部分組成：數(shù)據(jù)域與指針域。8/20/2022467.6.4 二叉樹(shù)的遍歷分為三種：前序遍歷、中序遍歷、后序遍歷。下面分別介紹這三種遍歷的方法，并用 D 表示“訪問(wèn)根結(jié)點(diǎn)” L 表示“遍歷根結(jié)點(diǎn)的左子樹(shù) R 表示“遍歷根結(jié)點(diǎn)的右子樹(shù)”。8/20/2022471前序遍歷（DLR）是指首先訪問(wèn)根結(jié)點(diǎn)，然后遍歷左子樹(shù)

15、，最后遍歷右子樹(shù)例如，對(duì)圖7.31中的二叉樹(shù)進(jìn)行前序遍歷，則為ABDGCEHIF。8/20/2022482中序遍歷（LDR）是指首先遍歷左子樹(shù)，然后訪問(wèn)根結(jié)點(diǎn)，最后遍歷右子樹(shù)。例如，對(duì)圖7.31中的二叉樹(shù)進(jìn)行中序遍歷，則為DGBAHEICF。8/20/2022493后序遍歷（LRD）是指首先遍歷左子樹(shù)，然后遍歷右子樹(shù)，最后訪問(wèn)根結(jié)點(diǎn)。例如，對(duì)圖7.31中的二叉樹(shù)進(jìn)行后序遍歷，則為GDBHIEFCA。8/20/2022507.7 查找與排序技術(shù)7.7.1 順序查找順序查找又稱(chēng)為順序搜索。順序查找是指在線性表中查找指定的元素，例如在線性表（a1，a2，ai，an）中查找 x。8/20/202251

16、7.7.2 二分法查找二分法查找只適用于順序存儲(chǔ)的有序表，即要求線性表中的元素按元素值的大小排列（遞減排列或遞增排列）。8/20/2022527.7.3 交換類(lèi)排序法1冒泡排序法原序列628131957第1遍（從前往后）261318579（從后往前）126135879第2遍（從前往后）121356789（從后往前）112356789第3遍（從前往后）112356789最后結(jié)果1123567898/20/2022537.7.3 插入類(lèi)排序法1簡(jiǎn)單插入排序法8/20/2022547.7.4 選擇類(lèi)排序法1簡(jiǎn)單選擇排序法 8/20/202255選擇題 1算法具有五個(gè)特性，以下選項(xiàng)中不屬于算法特性的是

17、（ ）。 A) 有窮性 B) 簡(jiǎn)潔性 C) 可行性 D)確定性 答案：B 8/20/202256選擇題 2算法的時(shí)間復(fù)雜度是指（ ）。A） 執(zhí)行算法程序所需要的時(shí)間B） 算法程序的長(zhǎng)度C） 算法執(zhí)行過(guò)程中所需要的基本運(yùn)算次數(shù)D） 算法程序中的指令條數(shù)答案：C 8/20/202257選擇題 3算法的空間復(fù)雜度是指（ ）。A） 算法程序的長(zhǎng)度B） 算法程序中的指令條數(shù)C） 算法程序所占的存儲(chǔ)空間D） 算法執(zhí)行過(guò)程中所需要的存儲(chǔ)空間答案：D8/20/202258選擇題 4數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是指（ ）。A） 數(shù)據(jù)所占的存儲(chǔ)空間量 B） 數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示C） 數(shù)據(jù)在計(jì)算機(jī)中的順序存儲(chǔ)方式 D）

18、 存儲(chǔ)在外存中的數(shù)據(jù)答案：B 8/20/202259選擇題 5下列對(duì)于線性表的描述中正確的是（ ）。 A) 存儲(chǔ)空間不一定是連續(xù)，且各元素的存儲(chǔ)順序是任意的 B) 存儲(chǔ)空間不一定是連續(xù)，且前件元素一定存儲(chǔ)在后件元素的前面 C) 存儲(chǔ)空間必須連續(xù)，且各前件元素一定存儲(chǔ)在后件元素的前面 D) 存儲(chǔ)空間必須連續(xù)，且各元素的存儲(chǔ)順序是任意的答案：A 8/20/202260選擇題 6下列關(guān)于棧的敘述中正確的是（ ）。A） 在棧中只能插入數(shù)據(jù) B）在棧中只能刪除數(shù)據(jù)C） 棧是先進(jìn)先出的線性表 D）棧是先進(jìn)后出的線性表答案：D 8/20/202261選擇題 7下列關(guān)于棧的描述中錯(cuò)誤的是（ ）。A) 棧是先進(jìn)

19、后出的先性表 B) 棧只能順序存儲(chǔ) C) 棧具有記憶作用 D) 對(duì)棧的插入和刪除操作中，不需要改變棧底指針答案：B 8/20/202262選擇題 8下列關(guān)于隊(duì)列的敘述中正確的是（ ）。A） 在隊(duì)列中只能插入數(shù)據(jù) B） 在隊(duì)列中只能刪除數(shù)據(jù)C） 隊(duì)列是先進(jìn)先出的線性表 D） 隊(duì)列是先進(jìn)后出的線性表答案：C 8/20/202263選擇題 9下列敘述中正確的是（ ）。A） 線性表是線性結(jié)構(gòu) B） 棧與隊(duì)列是非線性結(jié)構(gòu)C） 線性鏈表是非線性結(jié)構(gòu) D） 二叉樹(shù)是線性結(jié)構(gòu)答案：A8/20/202264選擇題 10下列數(shù)據(jù)結(jié)構(gòu)具有記憶功能的是（ ）。 A）隊(duì)列 B）循環(huán)隊(duì)列 C）棧 D）順序表答案：C8/2

20、0/202265選擇題 11遞歸算法一般需要利用（ ）實(shí)現(xiàn)。 A）棧 B）隊(duì)列 C）循環(huán)鏈表 D）雙向鏈表答案：A 8/20/202266選擇題 12下列敘述中正確的是（ ）。 A）線性鏈表中的各元素在存儲(chǔ)空間中的位置必須是連續(xù)的 B）線性鏈表中的表頭元素一定存儲(chǔ)在其他算數(shù)的前面 C）線性鏈表中的各元素在存儲(chǔ)空間中的位置不一定是連續(xù)的，但表頭元素一定存儲(chǔ)在其他算數(shù)的前面 D）線性鏈表中的各元素在存儲(chǔ)空間中的位置不一定是連續(xù)的，且各元素的存儲(chǔ)順序也是任意的。答案：D 8/20/202267選擇題 13設(shè)有下列二叉樹(shù)： 二叉樹(shù)中序遍歷的結(jié)果為（ ）。A） ABCDEF B） DBEAFC C） A

21、BDECF D） DEBFCA答案：B 8/20/202268選擇題 14在深度為5的滿(mǎn)二叉樹(shù)中，葉子結(jié)點(diǎn)的個(gè)數(shù)為（ ）。A） 32 B） 31 C） 16 D） 15答案：C 8/20/202269選擇題 15設(shè)樹(shù)T的度為4，其中度為1，2，3，4的結(jié)點(diǎn)個(gè)數(shù)分別為4，2，1，1。則T中的葉子結(jié)點(diǎn)數(shù)為（ ）。A） 8 B） 7 C） 6 D） 5答案：A8/20/202270選擇題 16設(shè)一棵二叉樹(shù)中有3個(gè)葉子結(jié)點(diǎn)，有8個(gè)度為1的結(jié)點(diǎn)，則該二叉樹(shù)中總的結(jié)點(diǎn)數(shù)為（ ）。A） 12 B） 13 C） 14 D）15答案：B 8/20/202271選擇題 17對(duì)長(zhǎng)度為n的線性表進(jìn)行順序查找，在最壞情

22、況下所需要的比較次數(shù)為（ ）。A） n+l B） n C） （n+1）/2 D） n/2答案：B 8/20/202272選擇題 18在長(zhǎng)度為n的有序線性表中進(jìn)行二分法查找，需要的比較次數(shù)為（ ）。A）log2n B） nlog2n C） n/2 D） (n+1)/2答案：A8/20/202273選擇題 19對(duì)于長(zhǎng)度為N的線性表，在最壞的情況下，下列各排序法所對(duì)應(yīng)的比較次數(shù)中正確的是（ ）。 A) 冒泡排序?yàn)镹/2 B) 冒泡排序?yàn)镹 C) 快速排序?yàn)镹 D) 快速排序?yàn)镹(N-1)/2答案：D 8/20/202274選擇題 20在最壞的情況下，下列排序方法中時(shí)間復(fù)雜度最小的是（ ）。A）冒泡排序 B） 快速排序 C） 插入排序 D）堆排序答案：D 8/20/202275選擇題 21希爾排序法屬于（ ）。A）選擇類(lèi)排序 B）交換類(lèi)排序 C）插入類(lèi)排序 D）以上都不對(duì)答案：C8/20/202276填空題 1問(wèn)題處理方案的正確而完整的描述稱(chēng)為_(kāi)。答案：算法 8/2