算法與數(shù)據(jù)結(jié)構(gòu).ppt

計(jì)算機(jī)二級(jí)C語(yǔ)言 上機(jī)時(shí)間90分鐘 筆試時(shí)間90分鐘 考核方式 筆試 公共基礎(chǔ) 30 C語(yǔ)言程序設(shè)計(jì) 70 選擇題20分 填空題10分 選擇題50分 填空題20分 機(jī)試 C語(yǔ)言程序設(shè)計(jì) 基本操作題 填空題 簡(jiǎn)單應(yīng)用題 改錯(cuò)題 綜合應(yīng)用題 編程題 算法與數(shù)據(jù)結(jié)構(gòu) 公共基礎(chǔ)第一部分 本章考核內(nèi)容約占13 主要包括一下幾個(gè)方面 算法復(fù)雜度棧 隊(duì)列 線性鏈表的基本概念樹(shù)的結(jié)點(diǎn)計(jì)算和遍歷排序的最壞次數(shù)計(jì)算 考點(diǎn)1算法的基本概念1 算法是指解題方案的準(zhǔn)確而完整的描述 換句話說(shuō) 算法是對(duì)某一特定問(wèn)題而采取的方法和步驟 對(duì)于一個(gè)問(wèn)題 如果可以通過(guò)一個(gè)計(jì)算機(jī)程序 在有限的存儲(chǔ)空間內(nèi)運(yùn)行有限的時(shí)間而得到正確的結(jié)果 則稱這個(gè)問(wèn)題是可解的 算法不等于程序 也不等于計(jì)算方法 程序的編制不可能優(yōu)于算法的設(shè)計(jì) 考點(diǎn)1算法的基本概念2 算法特征 1 可行性2 確定性3 有窮性 即算法必須能在執(zhí)行有限個(gè)步驟之后終止 在有限的時(shí)間內(nèi)完成4 擁有足夠的情報(bào) 針對(duì)實(shí)際問(wèn)題而設(shè)計(jì)的算法 執(zhí)行后能夠得到滿意的結(jié)果 每一條指令的含義明確 無(wú)二義性 并且在任何條件下 算法只有唯一的一條執(zhí)行路徑 即相同的輸入只能得出相同的輸出 算法必須在有限的時(shí)間內(nèi)完成 有兩重含義 一是算法中的操作步驟為有限個(gè) 二是每個(gè)步驟都能在有限時(shí)間內(nèi)完成 算法中各種運(yùn)算總是要施加到各個(gè)運(yùn)算對(duì)象上 而這些運(yùn)算對(duì)象又可能具有某種初始狀態(tài) 這就是算法執(zhí)行的起點(diǎn)或依據(jù) 考點(diǎn)1算法的基本概念 2008年4月 算法的有窮性是指 A 算法程序的運(yùn)行時(shí)間是有限的B 算法程序所處理的數(shù)據(jù)量是有限的C 算法程序的長(zhǎng)度是有限的D 算法只能被有限的用戶使用 答案 A 算法必須在有限的時(shí)間內(nèi)完成 有兩重含義 一是算法中的操作步驟為有限個(gè) 二是每個(gè)步驟都能在有限時(shí)間內(nèi)完成 考點(diǎn)1算法的基本概念3 算法的基本元素一個(gè)算法通常由兩種基本要素組成 一是對(duì)數(shù)據(jù)對(duì)象的運(yùn)算和操作 二是算法的控制結(jié)構(gòu) 一般的計(jì)算機(jī)系統(tǒng)中 基本運(yùn)算和操作包括以下4類 算術(shù)運(yùn)算 加 減 乘 除等運(yùn)算 邏輯運(yùn)算 與 或 非等運(yùn)算 關(guān)系運(yùn)算 等于 不等于 大于 小于等運(yùn)算 數(shù)據(jù)傳輸 賦值 輸入 輸出等操作 考點(diǎn)1算法的基本概念3 算法的基本元素算法的控制結(jié)構(gòu)算法各操作之間的執(zhí)行順序稱為算法的控制結(jié)構(gòu) 算法的控制結(jié)構(gòu)包括 順序 選擇 分支 和循環(huán) 考點(diǎn)1算法的基本概念4 算法設(shè)計(jì)的基本方法計(jì)算機(jī)解題的過(guò)程實(shí)際上是在實(shí)施某種算法 這種算法稱為計(jì)算機(jī)算法 列舉法 例如 百錢買百雞 歸納法 遞推 遞歸 例如 漢諾塔 減半遞推技術(shù) 回溯法 例如 求解皇后問(wèn)題 考點(diǎn)2算法的復(fù)雜度 算法的復(fù)雜度包括算法時(shí)間復(fù)雜度和算法空間復(fù)雜度 1 算法時(shí)間復(fù)雜度算法時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量 在度量一個(gè)算法的工作量時(shí) 用算法在執(zhí)行過(guò)程中所需基本運(yùn)算的執(zhí)行次數(shù)來(lái)度量算法的工作量 分析算法工作量的方法 平均性和最壞情況復(fù)雜性 考點(diǎn)2算法的復(fù)雜度 2 算法空間復(fù)雜度一個(gè)算法的空間復(fù)雜度 一般是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間大小 一個(gè)算法所占用的存儲(chǔ)空間包括算法程序所占的空間 輸入的初始數(shù)據(jù)所占的空間以及算法執(zhí)行過(guò)程中所需要的額外空間 考點(diǎn)2算法的復(fù)雜度 2005年9月 算法復(fù)雜度主要包括時(shí)間復(fù)雜度和 復(fù)雜度 2006年9月 下列敘述中正確的是 A 一個(gè)算法的空間復(fù)雜度大 則其時(shí)間復(fù)雜度也必定大B 一個(gè)算法的空間復(fù)雜度大 則其時(shí)間復(fù)雜度必定小C 一個(gè)算法的時(shí)間復(fù)雜度大 則其空間復(fù)雜度必定小D 上述三種說(shuō)法都不對(duì) 答案 D 空間 考點(diǎn)2算法的復(fù)雜度 2007年4月 下列敘述中正確的是 A 算法的效率只與問(wèn)題的規(guī)模有關(guān) 而與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無(wú)關(guān)B 算法的時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量C 數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)是一一對(duì)應(yīng)的D 算法的時(shí)間復(fù)雜度與空間復(fù)雜度一定相關(guān) 答案 B 考點(diǎn)3數(shù)據(jù)結(jié)構(gòu)1 基本概念1 數(shù)據(jù) 描述客觀事物的數(shù) 字符以及所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序加工處理的符號(hào)的集合 2 數(shù)據(jù)元素 數(shù)據(jù)的基本單位 即數(shù)據(jù)集合中的個(gè)體 有時(shí)一個(gè)數(shù)據(jù)元素由若干個(gè)數(shù)據(jù)項(xiàng)組成 在這種情況下 將數(shù)據(jù)元素稱為記錄 由記錄所組成的線性表為文件 考點(diǎn)3數(shù)據(jù)結(jié)構(gòu)1 基本概念3 數(shù)據(jù)項(xiàng) 具有獨(dú)立意義的最小數(shù)據(jù)單位 4 數(shù)據(jù)對(duì)象 具有相同特性的數(shù)據(jù)元素的集合 是數(shù)據(jù)的子集 5 結(jié)構(gòu) 指數(shù)據(jù)元素之間的前后件關(guān)系 考點(diǎn)3數(shù)據(jù)結(jié)構(gòu)1 基本概念6 數(shù)據(jù)結(jié)構(gòu) 指相互關(guān)聯(lián)的數(shù)據(jù)元素的集合 數(shù)據(jù)結(jié)構(gòu)包含兩方面信息 一是表示數(shù)據(jù)元素的信息 二是表示各數(shù)據(jù)元素之間的前后件關(guān)系 例如 描述一年四季的季節(jié)名春 夏 秋 冬 可以作為季節(jié)的數(shù)據(jù)元素 在考慮一年4個(gè)季節(jié)的順序關(guān)系時(shí) 則 春 是 夏 的前件 而 夏 是 春 的后件等 考點(diǎn)3數(shù)據(jù)結(jié)構(gòu)2 數(shù)據(jù)的邏輯結(jié)構(gòu)在以上所述的數(shù)據(jù)結(jié)構(gòu)中 數(shù)據(jù)元素之間的前后件關(guān)系是指它們的邏輯關(guān)系 而與它們?cè)谟?jì)算機(jī)中的存儲(chǔ)位置無(wú)關(guān) 因此 上面所述的數(shù)據(jù)結(jié)構(gòu)實(shí)際上是數(shù)據(jù)的邏輯結(jié)構(gòu) 1 概念 所謂數(shù)據(jù)的邏輯結(jié)構(gòu) 是指反映數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu) 考點(diǎn)3數(shù)據(jù)結(jié)構(gòu)2 數(shù)據(jù)的邏輯結(jié)構(gòu)2 表示 圖形表示 集合 線性 樹(shù) 圖 考點(diǎn)3數(shù)據(jù)結(jié)構(gòu)2 數(shù)據(jù)的邏輯結(jié)構(gòu)2 表示 二元關(guān)系表示數(shù)據(jù)的邏輯結(jié)構(gòu)有兩個(gè)要素 一是數(shù)據(jù)元素的集合 通常記為D 二是D上的關(guān)系 它反映了D中各數(shù)據(jù)元素之間的前后件關(guān)系 通常記為R 即一個(gè)數(shù)據(jù)結(jié)構(gòu)可以表示成 B D R 其中B表示數(shù)據(jù)結(jié)構(gòu) 為了反映D中各數(shù)據(jù)元素之間的前后件關(guān)系 一般用二元組來(lái)表示 考點(diǎn)3數(shù)據(jù)結(jié)構(gòu)2 數(shù)據(jù)的邏輯結(jié)構(gòu)2 表示 二元關(guān)系表示例如 一年四季的數(shù)據(jù)結(jié)構(gòu)可以表示成 B D R D 春 夏 秋 冬 R 春 夏 夏 秋 秋 冬 考點(diǎn)4數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)1 概念 數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間的存放形式稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) 考點(diǎn)4數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)2 存儲(chǔ)形式 數(shù)據(jù)元素之間的關(guān)系在計(jì)算機(jī)中有兩種不同的表示方法 順序映像和非順序映像 并由此得到兩種不同的存儲(chǔ)結(jié)構(gòu) 順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 順序映像的特點(diǎn)是借助元素在存儲(chǔ)器中的相對(duì)位置來(lái)表示數(shù)據(jù)元素之間的邏輯關(guān)系 非順序映像的特點(diǎn)是借助指示元素存儲(chǔ)地址的指針 Pointer 表示數(shù)據(jù)元素之間的邏輯關(guān)系 數(shù)據(jù)元素之間具有的邏輯關(guān)系 結(jié)構(gòu) 線性關(guān)系 線性結(jié)構(gòu) 如線性表 線性鏈表 堆棧 隊(duì)列等 具有某種邏輯結(jié)構(gòu)的數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)器中的存儲(chǔ)方式 存儲(chǔ)映象 順序存儲(chǔ)結(jié)構(gòu) 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 用一組地址連續(xù)的存儲(chǔ)單元依次存放數(shù)據(jù)元素 數(shù)據(jù)元素之間的邏輯關(guān)系通過(guò)元素的地址直接反映 用一組地址任意的存儲(chǔ)單元依次存放數(shù)據(jù)元素 數(shù)據(jù)元素之間的邏輯關(guān)系通過(guò)指針間接地反映 非線性關(guān)系 非線性結(jié)構(gòu) 如樹(shù) 二叉樹(shù) 圖等 考點(diǎn)4數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)注意 數(shù)據(jù)元素在計(jì)算機(jī)存儲(chǔ)空間中的位置關(guān)系可能與邏輯關(guān)系不同 數(shù)據(jù)的邏輯結(jié)構(gòu)可以表示成多種存儲(chǔ)結(jié)構(gòu) 采用不同的存儲(chǔ)結(jié)構(gòu) 其數(shù)據(jù)處理的效率是不同的 1 研究數(shù)據(jù)元素之間的客觀聯(lián)系 2 研究具有某種邏輯關(guān)系的數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)器內(nèi)的存儲(chǔ)方式 3 研究如何在數(shù)據(jù)的各種結(jié)構(gòu) 邏輯的和物理的 的基礎(chǔ)上對(duì)數(shù)據(jù)實(shí)施一系列有效的基本操作 考點(diǎn)4數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) 2005年4月 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是指 A 存儲(chǔ)在外存中的數(shù)據(jù)B 數(shù)據(jù)所占的存儲(chǔ)空間量C 數(shù)據(jù)在計(jì)算機(jī)中的順序存儲(chǔ)方式D 數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示 答案 D 考點(diǎn)4數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) 2005年9月 下列敘述中正確的是 A 一個(gè)邏輯數(shù)據(jù)結(jié)構(gòu)只能有一種存儲(chǔ)結(jié)構(gòu)B 數(shù)據(jù)的邏輯結(jié)構(gòu)屬于線性結(jié)構(gòu) 存儲(chǔ)結(jié)構(gòu)屬于非線性結(jié)構(gòu)C 一個(gè)邏輯數(shù)據(jù)結(jié)構(gòu)可以有多種存儲(chǔ)結(jié)構(gòu) 且各種存儲(chǔ)結(jié)構(gòu)不影響數(shù)據(jù)處理的效率D 一個(gè)邏輯數(shù)據(jù)結(jié)構(gòu)可以有多種存儲(chǔ)結(jié)構(gòu) 且各種存儲(chǔ)結(jié)構(gòu)影響數(shù)據(jù)處理的效率 答案 D 考點(diǎn)4數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) 2007年9月 下列敘述中正確的是 A 數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)必定是一一對(duì)應(yīng)的B 由于計(jì)算機(jī)存儲(chǔ)空間是向量式的存儲(chǔ)結(jié)構(gòu) 因此 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)一定是線性結(jié)構(gòu)C 程序設(shè)計(jì)語(yǔ)言中的數(shù)組一般是順序存儲(chǔ)結(jié)構(gòu) 因此 利用數(shù)組只能處理線性結(jié)構(gòu)D 以上三種說(shuō)法都不對(duì) 答案 D 考點(diǎn)4數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) 2008年9月 下列敘述中正確的是 A 順序存儲(chǔ)結(jié)構(gòu)的存儲(chǔ)一定是連續(xù)的 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的存儲(chǔ)空間不一定是連續(xù)的B 順序存儲(chǔ)結(jié)構(gòu)只針對(duì)線性結(jié)構(gòu) 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)只針對(duì)非線性結(jié)構(gòu)C 順序存儲(chǔ)結(jié)構(gòu)能存儲(chǔ)有序表 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)不能存儲(chǔ)有序表D 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)比順序存儲(chǔ)結(jié)構(gòu)節(jié)省存儲(chǔ)空間 答案 A 考點(diǎn)5線性結(jié)構(gòu)與非線性結(jié)構(gòu) 根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后件關(guān)系的復(fù)雜程度 將數(shù)據(jù)結(jié)構(gòu)分為兩大類型 線性結(jié)構(gòu)非線性結(jié)構(gòu) 邏輯結(jié)構(gòu) a1a2a3 a30 存儲(chǔ)結(jié)構(gòu) 1 順序存儲(chǔ)結(jié)構(gòu) 線性結(jié)構(gòu) 線性表 2 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 考點(diǎn)5線性結(jié)構(gòu)與非線性結(jié)構(gòu) 如果一個(gè)非空的數(shù)據(jù)結(jié)構(gòu)滿足兩個(gè)條件 一是有且只有一個(gè)根結(jié)點(diǎn) 二是每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件 也最多有一個(gè)后件 則稱該數(shù)據(jù)結(jié)構(gòu)為線性結(jié)構(gòu) 線性結(jié)構(gòu)又稱線性表 注意 在一個(gè)線性結(jié)構(gòu)中插入或刪除任何一個(gè)結(jié)點(diǎn)后還應(yīng)是線性結(jié)構(gòu) 如果一個(gè)數(shù)據(jù)結(jié)構(gòu)不是線性結(jié)構(gòu) 則稱為非線性結(jié)構(gòu) 考點(diǎn)6線性表的基本概念線性表是最簡(jiǎn)單 最常用的一種數(shù)據(jù)結(jié)構(gòu) 線性表由一組數(shù)據(jù)元素構(gòu)成的有限序列 如一年的四個(gè)季節(jié) 線性表中結(jié)點(diǎn)的個(gè)數(shù)n稱為線性表的長(zhǎng)度 n 0時(shí) 稱為空表 考點(diǎn)6線性表的基本概念非空線性表有如下一些結(jié)構(gòu)特征 有且只有一個(gè)根結(jié)點(diǎn) 它無(wú)前件 有且只有一個(gè)終端結(jié)點(diǎn) 它無(wú)后件 除根結(jié)點(diǎn)與終端結(jié)點(diǎn)外 其他所有結(jié)點(diǎn)有且只有一個(gè)前件 也有且只有一個(gè)后件 考點(diǎn)7線性表的順序存儲(chǔ)在計(jì)算機(jī)中存放線性表的一種最簡(jiǎn)單的方法是順序存儲(chǔ) 也稱為順序分配 用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)的線性表稱作順序表 考點(diǎn)7線性表的順序存儲(chǔ)線性表的順序存儲(chǔ)結(jié)構(gòu)具有以下兩個(gè)基本特點(diǎn) 1 線性表中所有元素所占的存儲(chǔ)空間是連續(xù)的 2 線性表中各數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存放的 由此可以看出 在線性表的順序存儲(chǔ)結(jié)構(gòu)中 其前后件兩個(gè)元素在存儲(chǔ)空間中是緊鄰的 且前件元素一定存儲(chǔ)在后件元素的前面 可以通過(guò)計(jì)算機(jī)直接確定第i個(gè)結(jié)點(diǎn)的存儲(chǔ)地址 例 一維數(shù)組的存儲(chǔ)結(jié)構(gòu)inta 5 a 0 a 1 a 2 a 3 a 4 1000 1006 數(shù)組元素地址 數(shù)組起始地址 元素下標(biāo) sizeof 數(shù)組類型 a 3 的地址為 1000 3 2 1006 考點(diǎn)7線性表的順序存儲(chǔ)注意 在線性表的順序存儲(chǔ)結(jié)構(gòu)中 其前后件兩個(gè)元素在存儲(chǔ)空間中是緊鄰的 且前件元素一定存儲(chǔ)在后件元素的前面 考點(diǎn)8順序表的操作1 插入順序表的插入運(yùn)算 在一般情況下 要在第i 1 i n 個(gè)元素之前插入一個(gè)新元素時(shí) 首先要從最后一個(gè) 即第n個(gè) 元素開(kāi)始 直到第i個(gè)元素之間共n i 1個(gè)元素依次向后移動(dòng)一個(gè)位置 移動(dòng)結(jié)束后 第i個(gè)位置就被空出 然后將新元素插入到第i項(xiàng) 插入結(jié)束后 線性表的長(zhǎng)度就增加了1 該運(yùn)算是在線性表的第i 1個(gè)數(shù)據(jù)元素與第i個(gè)數(shù)據(jù)元素之間插入一個(gè)由符號(hào)item表示的數(shù)據(jù)元素 使長(zhǎng)度為n的線性表 a1 a2 ai 1 ai ai 1 an 1 an 轉(zhuǎn)換成長(zhǎng)度為n 1的線性表 a1 a2 ai 1 item ai an 1 an 考點(diǎn)8順序表的操作1 插入向順序表中插入一個(gè)新結(jié)點(diǎn)時(shí) 由于需要保持運(yùn)算的結(jié)果仍然是順序存儲(chǔ) 所以可能要移動(dòng)一系列結(jié)點(diǎn) 若順序表中結(jié)點(diǎn)個(gè)數(shù)為n 在向每個(gè)位置插入的概率相等的情況下 插入一個(gè)結(jié)點(diǎn)平均需要移動(dòng)之結(jié)點(diǎn)個(gè)數(shù)為n 2 算法的時(shí)間復(fù)雜度是O n 順性表的插入運(yùn)算時(shí)需要移動(dòng)元素 在等概率情況下 平均需要移動(dòng)n 2個(gè)元素 考點(diǎn)8順序表的操作2 刪除順序表的刪除運(yùn)算 在一般情況下 要?jiǎng)h除第i 1 i n 個(gè)元素時(shí) 則要從第i 1個(gè)元素開(kāi)始 直到第n個(gè)元素之間共n i個(gè)元素依次向前移動(dòng)一個(gè)位置 刪除結(jié)束后 線性表的長(zhǎng)度就減小了1 該運(yùn)算是把線性表的第i個(gè)數(shù)據(jù)元素從線性表中去掉 使得長(zhǎng)度為n的線性表 a1 a2 ai 1 ai ai 1 an 1 an 轉(zhuǎn)換成長(zhǎng)度為n 1的線性表 a1 a2 ai 1 ai 1 an 1 an 考點(diǎn)8順序表的操作2 刪除從順序表中刪除一個(gè)結(jié)點(diǎn)可能需要移動(dòng)一系列結(jié)點(diǎn) 在等概率的情況下 刪除一個(gè)結(jié)點(diǎn)平均需移動(dòng)結(jié)點(diǎn)個(gè)數(shù)為 n 1 2 算法的時(shí)間復(fù)雜度也是O n 考點(diǎn)9線性表的鏈?zhǔn)酱鎯?chǔ) 為了適應(yīng)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 計(jì)算機(jī)的內(nèi)存空間被劃分為多個(gè)小塊 每個(gè)小塊占若干個(gè)字節(jié) 通常稱這些小塊為存儲(chǔ)結(jié)點(diǎn) 每個(gè)存儲(chǔ)結(jié)點(diǎn)分為兩部分 一部分用于存儲(chǔ)數(shù)據(jù)元素的值 稱為數(shù)據(jù)域 一部分用于存儲(chǔ)下一個(gè)數(shù)據(jù)元素的存儲(chǔ)序號(hào) 即存儲(chǔ)結(jié)點(diǎn)的地址 稱為指針域 考點(diǎn)9線性表的鏈?zhǔn)酱鎯?chǔ) 1 線性鏈表 單鏈表 所謂線性鏈表就是鏈?zhǔn)酱鎯?chǔ)的線性表 其結(jié)點(diǎn)中只含有一個(gè)指針域 用來(lái)指出其后繼結(jié)點(diǎn)的存儲(chǔ)位置 線性鏈表的最后一個(gè)結(jié)點(diǎn)無(wú)后繼結(jié)點(diǎn) 它的指針域?yàn)榭?記為NULL或 另外還要設(shè)置表頭指針head 指向線性鏈表的第一個(gè)結(jié)點(diǎn) 考點(diǎn)9線性表的鏈?zhǔn)酱鎯?chǔ) 1 線性鏈表 單鏈表 對(duì)線性鏈表可以進(jìn)行插入 刪除等運(yùn)算 注意 做刪除運(yùn)算時(shí)改變的是被刪結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)中指針域的值 因此 若要查找且刪除某一結(jié)點(diǎn) 則應(yīng)在查找被刪結(jié)點(diǎn)的同時(shí)記下它前一個(gè)結(jié)點(diǎn)的位置 考點(diǎn)9線性表的鏈?zhǔn)酱鎯?chǔ) 2 雙向鏈表線性單鏈表中 每個(gè)結(jié)點(diǎn)只有一個(gè)指針域 由此指針只能找到后件節(jié)點(diǎn) 為了彌補(bǔ)線性單鏈表的這個(gè)缺點(diǎn) 在某些應(yīng)用中 對(duì)線性單鏈表的每個(gè)結(jié)點(diǎn)設(shè)置兩個(gè)指針 一個(gè)稱為左指針 Llink 用以指向其前件結(jié)點(diǎn) 另一個(gè)稱為右指針 Rlink 用以指向其后件結(jié)點(diǎn) 這樣的線性鏈表稱為雙向鏈表 考點(diǎn)9線性表的鏈?zhǔn)酱鎯?chǔ) 3 循環(huán)鏈表所謂循環(huán)鏈表是指鏈表的最后一個(gè)結(jié)點(diǎn)的指針值指向第一個(gè)結(jié)點(diǎn) 整個(gè)鏈表形成一個(gè)環(huán) 線性鏈表 考點(diǎn)9線性表的鏈?zhǔn)酱鎯?chǔ) 注意 在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中 存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)空間可以不連續(xù) 各數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)順序與數(shù)據(jù)元素之間的邏輯關(guān)系可以不一致 而數(shù)據(jù)元素之間的邏輯關(guān)系是由指針域來(lái)確定的 考點(diǎn)9線性表的鏈?zhǔn)酱鎯?chǔ) 2005年4月 對(duì)于線性鏈表的描述中正確的是 A 存儲(chǔ)空間不一定是連續(xù) 且各元素的存儲(chǔ)順序是任意的B 存儲(chǔ)空間不一定是連續(xù) 且前件元素一定存儲(chǔ)在后件元素的前面C 存儲(chǔ)空間必須連續(xù) 且前件元素一定存儲(chǔ)在后件元素的前面D 存儲(chǔ)空間必須連續(xù) 且各元素的存儲(chǔ)順序是任意的 答案 A 考點(diǎn)10棧及其基本運(yùn)算 1 棧的定義棧是一種特殊的線性表 棧是限定僅在表尾 表的一端 進(jìn)行插入和刪除運(yùn)算的線性表 表尾稱為棧頂 top 表頭叫做棧底 bottom 棧中無(wú)元素時(shí)稱為空棧 棧遵守 后進(jìn)先出 LIFO 的操作原則 具有記憶功能 考點(diǎn)10棧及其基本運(yùn)算 2 棧的存儲(chǔ)棧的既可以用順序存儲(chǔ)結(jié)構(gòu) 也可用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 在程序設(shè)計(jì)語(yǔ)言中 用一維數(shù)組S 1 m 作為棧的順序存儲(chǔ)空間 其中m為棧的最大容量 通常 棧底指針指向?？臻g的低地址一端 即數(shù)組的起始地址這一端 棧用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 帶鏈的棧稱為可利用棧 考點(diǎn)10棧及其基本運(yùn)算 3 棧的運(yùn)算1 入棧運(yùn)算 指在棧頂位置插入一個(gè)新元素 其方法是先將棧頂指針top進(jìn)一 即top加1 然后將新元素插入到棧頂指針指向的位置 注意 棧 上溢 錯(cuò)誤 棧頂指針為m 2 退棧運(yùn)算 指取出棧頂元素并賦給一個(gè)指定的變量 其方法是先將棧頂元素賦給一個(gè)指定的變量 然后將棧頂指針top退一 即top減1 注意 棧 下溢 錯(cuò)誤 棧頂指針為0 考點(diǎn)10棧及其基本運(yùn)算 3 棧的運(yùn)算3 讀棧頂元素 指將棧頂元素賦給一個(gè)指定的變量 注意 此元素不刪除棧頂元素 只是將其賦給一個(gè)變量 因此在這個(gè)運(yùn)算中 棧頂指針不會(huì)改變 考點(diǎn)10棧及其基本運(yùn)算 2005年4月 下列關(guān)于棧的描述中錯(cuò)誤的是 A 棧是先進(jìn)后出的線性表B 棧只能順序存儲(chǔ)C 棧具有記憶作用D 對(duì)棧的插入與刪除操作中 不需要改變棧底指針 答案 B 考點(diǎn)10棧及其基本運(yùn)算 2005年9月 下列關(guān)于棧的描述正確的是 A 在棧中只能插入元素而不能刪除元素B 在棧中只能刪除元素而不能插入元素C 棧是特殊的線性表 只能在一端插入或刪除元素D 棧是特殊的線性表 只能在一端插入元素 而在另一端刪除元素 答案 C 考點(diǎn)10棧及其基本運(yùn)算 2006年4月 按照 后進(jìn)先出 原則組織數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)是 A 隊(duì)列B 棧C 雙向鏈表D 二叉樹(shù) 2006年9月 按 先進(jìn)后出 原則組織數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)是 答案 棧 B 考點(diǎn)10棧及其基本運(yùn)算 2008年4月 下列關(guān)于棧的敘述正確的是 A 棧按 先進(jìn)先出 組織數(shù)據(jù)B 棧按 先進(jìn)后出 組織數(shù)據(jù)C 只能在棧底插入數(shù)據(jù)D 不能刪除數(shù)據(jù) 答案 B 考點(diǎn)10棧及其基本運(yùn)算 2008年9月 一個(gè)棧的初始狀態(tài)為空 現(xiàn)將元素1 2 3 4 5 A B C D E依次入棧 然后再依次出棧 則元素出棧的順序是 A 12345ABCDEB EDCBA54321C ABCDE12345D 54321EDCBA 答案 B 考點(diǎn)11隊(duì)列及其基本運(yùn)算 1 隊(duì)列的定義隊(duì)列是一種特殊的線性表 隊(duì)列是限定所有的插入都在表的一端進(jìn)行 所有的刪除都在表的另一端進(jìn)行的線性表 允許插入的一端稱為隊(duì)尾 通常用一個(gè)稱為尾指針 rear 的指針指向隊(duì)尾元素 允許刪除的一端稱為隊(duì)頭 通常用一個(gè)稱為頭指針 front 的指針指向排頭元素的前一個(gè)位置 考點(diǎn)11隊(duì)列及其基本運(yùn)算 1 隊(duì)列的定義隊(duì)列遵守 先進(jìn)先出 FIFO 的操作原則 隊(duì)尾指針和隊(duì)頭指針共同反映了隊(duì)列中元素的動(dòng)態(tài)變化情況 2 隊(duì)列的存儲(chǔ)隊(duì)列既可以用順序存儲(chǔ)結(jié)構(gòu) 一般采用循環(huán)隊(duì)列 也可用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 3 隊(duì)列的運(yùn)算入隊(duì)運(yùn)算 退隊(duì)運(yùn)算 取隊(duì)頭元素 檢查隊(duì)列是否為空 清除等 考點(diǎn)11隊(duì)列及其基本運(yùn)算 4 循環(huán)隊(duì)列 順序存儲(chǔ)結(jié)構(gòu) 循環(huán)隊(duì)列就是將隊(duì)列存儲(chǔ)空間的最后一個(gè)位置繞到第1個(gè)位置 形成邏輯上的環(huán)狀空間 供隊(duì)列循環(huán)使用 考點(diǎn)11隊(duì)列及其基本運(yùn)算 4 循環(huán)隊(duì)列入隊(duì)運(yùn)算 入隊(duì)運(yùn)算是指在循環(huán)隊(duì)列的隊(duì)尾加入一個(gè)新元素 rear加1 當(dāng)rear m 1時(shí) 則置rear 1 退隊(duì)運(yùn)算 退隊(duì)運(yùn)算是指在循環(huán)隊(duì)列的排頭位置退出一個(gè)元素 front加1 當(dāng)front m 1時(shí) 則置front 1 考點(diǎn)11隊(duì)列及其基本運(yùn)算 4 循環(huán)隊(duì)列當(dāng)循環(huán)隊(duì)列滿時(shí)有front rear 而當(dāng)循環(huán)隊(duì)列為空時(shí)也有front rear 為了那個(gè)區(qū)分隊(duì)列是滿還是隊(duì)列空 通常需要增加一個(gè)標(biāo)示s s 0表示隊(duì)列空 s 1表示隊(duì)列非空 由此可得隊(duì)列滿與空的條件 隊(duì)列空的條件為s 0 隊(duì)列滿的條件為s 1且front rear 考點(diǎn)11隊(duì)列及其基本運(yùn)算 2008年4月 設(shè)某循環(huán)隊(duì)列的容量為50 頭指針Front 5 指向隊(duì)頭元素的前一位置 尾指針rear 29 指向隊(duì)尾元素 則該循環(huán)隊(duì)列中共有個(gè)元素 答案 24 考點(diǎn)11隊(duì)列及其基本運(yùn)算 2008年9月 下列敘述中正確的是 A 循環(huán)隊(duì)列中有隊(duì)頭和隊(duì)尾兩個(gè)指針 因此 循環(huán)隊(duì)列是非線性結(jié)構(gòu)B 在循環(huán)隊(duì)列中 只需要隊(duì)頭指針就能反映隊(duì)列中元素的動(dòng)態(tài)變化情況C 在循環(huán)隊(duì)列中 只需要隊(duì)尾指針就能反映隊(duì)列中元素的動(dòng)態(tài)變化情況D 循環(huán)隊(duì)列中元素的個(gè)數(shù)是由隊(duì)頭指針和隊(duì)尾指針共同決定 答案 D 考點(diǎn)11隊(duì)列及其基本運(yùn)算 2005年9月 數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu) 循環(huán)隊(duì)列屬于結(jié)構(gòu) 2006年9月 數(shù)據(jù)結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu) 帶鏈的隊(duì)列屬于 答案 存儲(chǔ) 線性 考點(diǎn)11隊(duì)列及其基本運(yùn)算 2007年4月 下列對(duì)隊(duì)列的敘述正確的是 A 隊(duì)列屬于非線性表B 隊(duì)列按 先進(jìn)后出 原則組織數(shù)據(jù)C 隊(duì)列在隊(duì)尾刪除數(shù)據(jù)D 隊(duì)列按 先進(jìn)先出 原則組織數(shù)據(jù) 2007年9月 線性表的存儲(chǔ)結(jié)構(gòu)主要分為順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 隊(duì)列是一種特殊的線性表 循環(huán)隊(duì)列是隊(duì)列的存儲(chǔ)結(jié)構(gòu) 答案 D 順序 考點(diǎn)12樹(shù)的基本概念1 樹(shù)樹(shù)是一種簡(jiǎn)單的非線性結(jié)構(gòu) 在樹(shù)這種結(jié)構(gòu)中 所有數(shù)據(jù)元素之間的關(guān)系具有明顯的層次特性 一般認(rèn)為 直線連接起來(lái)的兩端結(jié)點(diǎn)中 上端結(jié)點(diǎn)是前件 下端結(jié)點(diǎn)是后件 具有層次關(guān)系的數(shù)據(jù)都可以用樹(shù)來(lái)表示 考點(diǎn)12樹(shù)的基本概念2 常用術(shù)語(yǔ)根結(jié)點(diǎn) 沒(méi)有前件的結(jié)點(diǎn) 只有一個(gè) 葉子結(jié)點(diǎn) 沒(méi)有后件的結(jié)點(diǎn) 父結(jié)點(diǎn) 每一個(gè)結(jié)點(diǎn)只有一個(gè)前件 該前件結(jié)點(diǎn)稱為父結(jié)點(diǎn) 考點(diǎn)12樹(shù)的基本概念2 常用術(shù)語(yǔ)子結(jié)點(diǎn) 每一個(gè)結(jié)點(diǎn)可以有多個(gè)后件 它們都稱為該結(jié)點(diǎn)的子結(jié)點(diǎn) 兄弟 Sibling 具有相同親結(jié)點(diǎn)的結(jié)點(diǎn)互為兄弟 結(jié)點(diǎn)的度 Degree 一個(gè)結(jié)點(diǎn)所擁有的后件的個(gè)數(shù) 樹(shù)的度 樹(shù)中各結(jié)點(diǎn)的度的最大值 考點(diǎn)12樹(shù)的基本概念2 常用術(shù)語(yǔ)結(jié)點(diǎn)的層數(shù) 根結(jié)點(diǎn)的層數(shù)為1 同一層上所有結(jié)點(diǎn)的所有子結(jié)點(diǎn)都在下一層 樹(shù)的深度 樹(shù)的最大層次 子樹(shù) 以某結(jié)點(diǎn)的一個(gè)子結(jié)點(diǎn)為根構(gòu)成的樹(shù)稱為該結(jié)點(diǎn)的一棵子樹(shù) 葉子結(jié)點(diǎn)沒(méi)有子樹(shù) 考點(diǎn)13二叉樹(shù)及其基本性質(zhì) 1 二叉樹(shù)定義二叉樹(shù)是一種很有用的非線性結(jié)構(gòu) 二叉樹(shù)具有以下兩個(gè)特點(diǎn) 1 非空二叉樹(shù)只有一個(gè)根結(jié)點(diǎn) 2 每一個(gè)結(jié)點(diǎn)最多有兩棵子樹(shù) 且分別稱為該結(jié)點(diǎn)的左子樹(shù)與右子樹(shù) 二叉樹(shù)的5種基本形態(tài) 考點(diǎn)13二叉樹(shù)及其基本性質(zhì) 2 二叉樹(shù)的性質(zhì) 在二叉樹(shù)的i層上 最多有2i 1個(gè)結(jié)點(diǎn) i 1 深度為k的二叉樹(shù)最多有2k 1個(gè)結(jié)點(diǎn) k 1 對(duì)任何一棵二叉樹(shù)T 如果葉子結(jié)點(diǎn) 度為0 的數(shù)為n0 度為2的結(jié)點(diǎn)數(shù)為n2 則n0 n2 1 具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)的深度至少為 log2n 1 1 一棵非空二叉樹(shù)的第i層最多有2i 1個(gè)結(jié)點(diǎn) i 1 證明 采用歸納法 1 當(dāng)i 1時(shí) 結(jié)論顯然正確 非空二叉樹(shù)的第1層有且僅有一個(gè)結(jié)點(diǎn) 即樹(shù)的根結(jié)點(diǎn) 2 假設(shè)對(duì)于第j層 1 j i 1 結(jié)論也正確 即第j層最多有2j 1個(gè)結(jié)點(diǎn) 3 有定義可知 二叉樹(shù)中每個(gè)結(jié)點(diǎn)最多只能有兩個(gè)孩子結(jié)點(diǎn) 若第i 1層的每個(gè)結(jié)點(diǎn)都有兩棵非空子樹(shù) 則第i層的結(jié)點(diǎn)數(shù)目達(dá)到最大 而第i 1層最多有2i 2個(gè)結(jié)點(diǎn)已由假設(shè)證明 于是 應(yīng)有2 2i 2 2i 1 證畢 2 深度為h的非空二叉樹(shù)最多有2h 1個(gè)結(jié)點(diǎn) 證明 由性質(zhì)1可知 若深度為h的二叉樹(shù)的每一層的結(jié)點(diǎn)數(shù)目都達(dá)到各自所在層的最大值 則二叉樹(shù)的結(jié)點(diǎn)總數(shù)一定達(dá)到最大 即有20 21 22 2i 1 2h 1 2h 1 證畢 3 若非空二叉樹(shù)有n0個(gè)葉結(jié)點(diǎn) 有n2個(gè)度為2的結(jié)點(diǎn) 則n0 n2 1 證明 設(shè)該二叉樹(shù)有n1個(gè)度為1的結(jié)點(diǎn) 結(jié)點(diǎn)總數(shù)為n 有n n0 n1 n2 1 設(shè)二叉樹(shù)的分支數(shù)目為B 有B n 1 2 這些分支來(lái)自度于為1的結(jié)點(diǎn)與度度為2結(jié)點(diǎn) 即B n1 2n2 3 聯(lián)列關(guān)系 1 2 與 3 可得到n0 n2 1 證畢 4 具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度h log2n 1 證明 略 考點(diǎn)13二叉樹(shù)及其基本性質(zhì) 2 二叉樹(shù)的性質(zhì) 2005年4月 某二叉樹(shù)中度為2的結(jié)點(diǎn)有18個(gè) 則該二叉樹(shù)中有 個(gè)葉子結(jié)點(diǎn) 2005年9月 一棵二叉樹(shù)第六層 根結(jié)點(diǎn)為第一層 的結(jié)點(diǎn)數(shù)最多為結(jié)構(gòu) 2007年4月 某二叉樹(shù)中有n個(gè)度為2的結(jié)點(diǎn) 則該二叉樹(shù)中的葉子結(jié)點(diǎn)數(shù)為 A n 1B n 1C 2nD n 2 答案 19 A 32 考點(diǎn)13二叉樹(shù)及其基本性質(zhì) 2 二叉樹(shù)的性質(zhì) 2007年9月 一棵二叉樹(shù)共有70個(gè)葉子結(jié)點(diǎn)與80個(gè)度為1的結(jié)點(diǎn) 則該二叉樹(shù)中的總結(jié)點(diǎn)數(shù)為 A 219B 221C 229D 231 答案 A 考點(diǎn)13二叉樹(shù)及其基本性質(zhì) 3 滿二叉樹(shù)滿二叉樹(shù)與完全二叉樹(shù)是兩種特殊形態(tài)的二叉樹(shù) 所謂滿二叉樹(shù)是指除最后一層外 每一層上的所有結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn) 在滿二叉樹(shù)中 每一層上的結(jié)點(diǎn)數(shù)都達(dá)到最大值 考點(diǎn)13二叉樹(shù)及其基本性質(zhì) 3 滿二叉樹(shù) 2006年4月 在深度為7的滿二叉樹(shù)中 葉子結(jié)點(diǎn)的個(gè)數(shù)為 A 32B 31C 64D 63 2007年4月 在深度為7的滿二叉樹(shù)中 度為2的結(jié)點(diǎn)個(gè)數(shù)為 2008年4月 深度為5的滿二叉樹(shù)有個(gè)葉子結(jié)點(diǎn) 答案 16 C 63 考點(diǎn)13二叉樹(shù)及其基本性質(zhì) 4 完全二叉樹(shù)1 定義 所謂完全二叉樹(shù)是指除最后一層外 每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值 在最后一層上只缺少右邊的若干結(jié)點(diǎn) 考點(diǎn)13二叉樹(shù)及其基本性質(zhì) 4 完全二叉樹(shù)2 性質(zhì) 具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為 設(shè)完全二叉樹(shù)共有n個(gè)結(jié)點(diǎn) 如果從根結(jié)點(diǎn)開(kāi)始 按層序 每一層從左到右 用自然1 2 n給結(jié)點(diǎn)進(jìn)行編號(hào) 則對(duì)于編號(hào)為k k 1 2 n 的結(jié)點(diǎn)有以下結(jié)論 考點(diǎn)13二叉樹(shù)及其基本性質(zhì) 4 完全二叉樹(shù)若是k 1 則該結(jié)點(diǎn)為根結(jié)點(diǎn) 它沒(méi)有父結(jié)點(diǎn) 若k 1 則該結(jié)點(diǎn)的父結(jié)點(diǎn)編號(hào)為INT k 2 若2k n 則編號(hào)為k的結(jié)點(diǎn)的左子結(jié)點(diǎn)編號(hào)為2k 否則該結(jié)點(diǎn)無(wú)左子結(jié)點(diǎn) 若2k 1 n 則編號(hào)為k的結(jié)點(diǎn)的右子結(jié)點(diǎn)編號(hào)為2k 1 否則該結(jié)點(diǎn)無(wú)右子結(jié)點(diǎn) 考點(diǎn)14二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)二叉樹(shù)的存儲(chǔ)通常采用鏈接方式 每個(gè)結(jié)點(diǎn)除存儲(chǔ)結(jié)點(diǎn)自身的信息外再設(shè)置兩個(gè)指針域llink和rlink 分別指向結(jié)點(diǎn)的左子女和右子女 當(dāng)結(jié)點(diǎn)的某個(gè)指針為空時(shí) 則相應(yīng)的指針值為空 NULL 考點(diǎn)15二叉樹(shù)的遍歷 遍歷 或稱周游 是樹(shù)形結(jié)構(gòu)的一種重要運(yùn)算 不重復(fù)訪問(wèn)二叉樹(shù)中的所有結(jié)點(diǎn) 可以按多種不同的次序遍歷樹(shù)形結(jié)構(gòu) 二叉樹(shù)的基本組成部分是 根 N 左子樹(shù) L 右子樹(shù) R 因此可有NLR LNR LRN NRL RNL RLN六種遍歷次序 以下著重介紹前序遍歷 中序遍歷 后序遍歷 考點(diǎn)15二叉樹(shù)的遍歷 遍歷規(guī)則 前序遍歷 先訪問(wèn)根結(jié)點(diǎn) 然后遍歷左子樹(shù) 最后遍歷右子樹(shù) 中序遍歷 先訪問(wèn)左子樹(shù) 然后遍歷根結(jié)點(diǎn) 最后遍歷右子樹(shù) 后序遍歷 先訪問(wèn)左子樹(shù) 然后遍右子樹(shù) 最后遍歷根結(jié)點(diǎn) 考點(diǎn)15二叉樹(shù)的遍歷 2007年4月 對(duì)下列二叉樹(shù)進(jìn)行前序遍歷的結(jié)果為 A DYBEAFCZXB YDEBFZXCAC ABDYECFXZD ABCDEFXYZ 答案 C 考點(diǎn)15二叉樹(shù)的遍歷 2006年9月 對(duì)下列二叉樹(shù)進(jìn)行中序遍歷的結(jié)果是 A ACBDFEGB ACBDFGEC ABDCGEFD FCADBEG 答案 A 考點(diǎn)15二叉樹(shù)的遍歷 2008年9月 對(duì)下列二叉樹(shù)進(jìn)行中序遍歷的結(jié)果是 答案 DBXEAYFZC 考點(diǎn)15二叉樹(shù)的遍歷 2006年4月 對(duì)如下二叉樹(shù)進(jìn)行后序遍歷的結(jié)果為 A ABCDEFB DBEAFCC ABDECFD DEBFCA 答案 D 考點(diǎn)16順序查找 順序查找 順序搜索 是指在線性表中查找指定的元素 查找方法 從第一個(gè)元素開(kāi)始 逐個(gè)比較 若相等則查找成功 若找遍所有結(jié)點(diǎn)都不相等 則查找失敗 優(yōu)點(diǎn) 對(duì)線性表的結(jié)點(diǎn)邏輯次序沒(méi)有要求 不必排序 對(duì)線性表的存儲(chǔ)結(jié)構(gòu)也沒(méi)有要求 順序存儲(chǔ) 鏈?zhǔn)酱鎯?chǔ)皆可 缺點(diǎn) 平均檢索長(zhǎng)度大 對(duì)于長(zhǎng)度為n的有序線性表 在最壞的情況下 順序查找需要比較n次 平均查找次數(shù)為n 2 考點(diǎn)16順序查找 2005年4月 對(duì)長(zhǎng)度為n的線性表進(jìn)行順序查找 在最壞情況下所需要的比較次數(shù)為 A log2nB n 2C nD n 1 2006年9月 在長(zhǎng)度為64的有序線性表中進(jìn)行順序查找 最壞情況下需要比較的次數(shù)為 A 63B 64C 6D 7