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

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