、基本數(shù)據(jù)結(jié)構(gòu)與算法-資料下載頁(yè)
2025-08-01 17:22本頁(yè)面
【正文】 線性表 （順序或鏈?zhǔn)剑?為無(wú)序表 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的有序表 ? 二分查找 （折半查找） 只適用于順序存儲(chǔ)的有序表（從小到大）。 對(duì)于長(zhǎng)度為 N的有序線性表，在最壞情況下，二分查找只需要比較 log2N次，而順序查找要比較 N次。 ? 先確定待查記錄所在的范圍（區(qū)間），然后逐步縮小范圍直到找到或找不到該記錄為止。 ?對(duì)長(zhǎng)度為 N的線性表進(jìn)行順序查找，在最壞情況下所需要的比較次數(shù)為 ______。 A. N+1 B. N C. (N+1)/2 D. N/2 (B) 二分查找 查找過(guò)程 ?二十 .排序 ?排序 ：將一個(gè)數(shù)據(jù)元素的無(wú)序序列重新排列成一個(gè)按關(guān)鍵字有序的序列。 ?直接插入排序 :是將一個(gè)記錄插入到已排好序的有序表中，從而得到一個(gè)新的、記錄數(shù)增 1的有序表。排序過(guò)程： 38,49,65,97,76,13,27,49,... ?二十 .交換類排序法 冒泡排序與快速排序法屬于交換類的排序方法 冒泡排序法 假設(shè)線性表的長(zhǎng)度為 N，則在最壞的情況下，冒跑排序需要經(jīng)過(guò) N/2遍的從前往后的掃描和 N/2遍的從后往前的掃描，需要的比較次數(shù)為 N（ N1） /2 ? （ 1）起泡排序： 首先將第一個(gè)記錄的關(guān)鍵字和第二個(gè)記錄的關(guān)鍵字進(jìn)行比較，若為逆序，則將兩個(gè)記錄交換之，然后比較第二個(gè)記錄和第三個(gè)記錄的關(guān)鍵字。直至第 n1個(gè)記錄和第 n個(gè)記錄的關(guān)鍵字進(jìn)行過(guò)比較為止。 ? 然后進(jìn)行第二趟起泡排序，對(duì)前 n1個(gè)記錄進(jìn)行同樣操作。 ...直到在某趟排序過(guò)程中沒(méi)有進(jìn)行過(guò)交換記錄的操作為止。 ?在最壞情況下，冒泡排序的時(shí)間復(fù)雜度為 ___。 答： n(n1)/2或 n*(n1)/2或 O(n(n1)/2)或 O(n*(n1)/2) ? （ 2）快速排序 ：通過(guò)一趟排序?qū)⒋庞涗浄指畛瑟?dú)立的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小，則可分別對(duì)這兩部分記錄繼續(xù)進(jìn)行排序，以達(dá)到整個(gè)序列有序。 ? 二十一 .選擇類排序法 ? 二十 二 .插入類排序法 交換類排序 冒泡排序：最壞 n(n1)/2 ；最簡(jiǎn)單的交換排序。在待排序的元素序列基本有序的前提下，效率最高。 快速排序：最壞 n(n1)/2； 最好 O(Nlog2 N) 插入排序 簡(jiǎn)單插入排序：最壞 n(n1)/2 ； 每個(gè)元素距其最終位置不遠(yuǎn)時(shí)適用 。 希爾排序：最壞 O() 選擇排序 簡(jiǎn)單選擇排序：最壞 n(n1)/2 堆排序：最壞 O(nlog2n) ，適用于較大規(guī)模的線性表。 ?希爾排序法屬于哪一種類型的排序法 ___。 A. 交換類排序法 B. 插入類排序法 C. 選擇類排序法 D. 建堆排序法 ?已知數(shù)據(jù)表 A中每個(gè)元素距其最終位置不遠(yuǎn)，為節(jié)省時(shí)間，應(yīng)采用的算法是 ______。 A. 堆排序 B. 直接插入排序 C. 快速排序 D. 直接選擇排序 (B) (B) （ ） e1,e2,e3,e4，則可能的出棧序列是（ e2,e4,e3,e1 ，這只是其中一種，請(qǐng)大家分別列出剩下的幾種出棧序列）選擇題選擇答案為 A. e3,e1,e2,e4 ,e2,e3,e1 C. e4,e1,e3,e2 ,e4,e2,e1 A、 B、 C、 D，在第五個(gè)元素E入棧前，棧中元素可以出棧，則出棧序列可能是（ DCBEA，這只是其中一種，請(qǐng)大家分別列出剩下的幾種出棧序列） （線性存儲(chǔ)結(jié)構(gòu)和鏈表存儲(chǔ)結(jié)構(gòu)） 只允許在端點(diǎn)處插入和刪除元素 （ D） （ D） 度成正比 （便于插入和刪除操作） ，增加頭結(jié)點(diǎn)的目的是（方便運(yùn)算的實(shí)現(xiàn)） （從表中任一結(jié)點(diǎn)出發(fā)都能訪問(wèn)到整個(gè)鏈表） L＝（ a1,a2,a3,…… ai,…… an），下列說(shuō)法正確的是 ，其余每個(gè)元素都有一個(gè)且只有一個(gè)直接前件和直接后件 （ B） （ D） ?，要求內(nèi)存中可用存儲(chǔ)單元的地址 結(jié)構(gòu)分別是（ ） ，它的根結(jié)點(diǎn)數(shù)目是（ ） 5的滿二叉樹(shù)中，葉子結(jié)點(diǎn)的個(gè)數(shù)為 3個(gè)結(jié)點(diǎn)的二叉樹(shù)有（ ）種形態(tài) （ D） 答： 隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)、順序存取的存儲(chǔ)結(jié)構(gòu) 答： 有且只有 1 （ 16） （ 5） ? 3個(gè)葉子結(jié)點(diǎn)，有 8個(gè)度為 1的結(jié)點(diǎn)，則該二叉樹(shù)中總的結(jié)點(diǎn)數(shù)為 dabec，中序遍歷序列是 debac，它的前序遍歷序列是 ABDGCFK和 DGBAFCK，則該二叉樹(shù)的后序遍歷為 A、 ACFKBDG B、 GDBFKCA C、 KCFAGDB D、 ABCDFKG abdgcefh，中序遍歷訪問(wèn)順序是 dgbaechf，則其后序遍歷的結(jié)點(diǎn)訪問(wèn)順序是 （ 13） 分析 （ cedba） 分析 （ B） 分析 （ gdbehfca） 返回 16題分析 17題分析 c e d b a 18題分析 A B D C K G
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1