、基本數(shù)據(jù)結構與算法(參考版)
2025-08-04 17:22本頁面
【正文】 A. 交換類排序法 B. 插入類排序法 C. 選擇類排序法 D. 建堆排序法 ?已知數(shù)據(jù)表 A中每個元素距其最終位置不遠，為節(jié)省時間，應采用的算法是 ______。 希爾排序：最壞 O() 選擇排序 簡單選擇排序：最壞 n(n1)/2 堆排序：最壞 O(nlog2n) ，適用于較大規(guī)模的線性表。在待排序的元素序列基本有序的前提下，效率最高。 答： n(n1)/2或 n*(n1)/2或 O(n(n1)/2)或 O(n*(n1)/2) ? （ 2）快速排序 ：通過一趟排序將待排記錄分割成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分記錄的關鍵字小，則可分別對這兩部分記錄繼續(xù)進行排序，以達到整個序列有序。 ...直到在某趟排序過程中沒有進行過交換記錄的操作為止。直至第 n1個記錄和第 n個記錄的關鍵字進行過比較為止。 ?直接插入排序 :是將一個記錄插入到已排好序的有序表中，從而得到一個新的、記錄數(shù)增 1的有序表。 ?對長度為 N的線性表進行順序查找，在最壞情況下所需要的比較次數(shù)為 ______。 對于長度為 N的有序線性表，在最壞情況下，二分查找只需要比較 log2N次，而順序查找要比較 N次。 A. 隊列 B. 線性表 C. 二叉樹 D. 棧 樹是結點的集合，它的根結點數(shù)目是（ ） 具有 3個結點的二叉樹有（ ）種形態(tài) (B) (B) (16) （ C） 有且只有 1 （ 5） ?二叉樹的存儲結構 二叉樹通常采用鏈式存儲結構 ? 十八 .遍歷二叉樹 的三種方法： ? 先序 ： 訪問根結點 先序訪問左子樹 先序訪問右子樹 中序 中序訪問左子樹 中序訪問根結點 中序訪問右子樹 后序 后序訪問左子樹 后序訪問右子樹 訪問根結點 ?先序遍歷結果： 1,2,4,5,6,7,3 ?中序遍歷結果： 4,2,6,5,7,1,3 ?后序遍歷結果： 4,6,7,5,2,3,1 ?設一棵二叉樹中有 3個葉子結點，有 8個度為 1的結點，則該二叉樹中總的結點數(shù)為（ 13） 分析 已知二叉樹后序遍歷序列是 dabec，中序遍歷序列是 debac，它的前序遍歷序列是（ cedba） 分析 已知一棵二叉樹前序遍歷和中序遍歷分別為ABDGCFK和 DGBAFCK，則該二叉樹的后序遍歷為（ B） 分析 A、 ACFKBDG B、 GDBFKCA C、 KCFAGDB D、 ABCDFKG 若某二叉樹的前序遍歷訪問順序是 abdgcefh，中序遍歷訪問順序是 dgbaechf，則其后序遍歷的結點訪問順序是（ gdbehfca） ? 十九 .順序查找與二分查找 ? 順序查找 ：從表中最后一個記錄開始，逐個進行記錄的關鍵字和給定值的比較，若某個記錄的關鍵字和給定值比較相等，則查找成功，找到所查記錄；反之，查找不成功。 B. 350 C. 255 D. 351 在一棵二叉樹上第 5層的結點數(shù)最多是 _。否則其左孩子 LCHILD(i)是結點 2i (3)如果 2i+1n,則結點 i無右孩子 。 ? 性質４：具有 n個結點的完全二叉樹的深度為 |log2n|+1 ? 性質５：如果對一棵有 n個結點的完全二叉樹的結點按層序編號，則對任一結點 i(1=i=n)有： (1)如果 i=1,則結點 i是二叉樹的根 ,無雙親 。 ? 性質２：深度為 k的二叉樹至多有 2k1個結點 (k=1)。具有 N個結點的完全二叉樹的深度為 [log2n]+1 完全二叉樹總結點數(shù)為 N， N為奇數(shù)，則葉子結點數(shù)為 （ N+1） /2 若 N為偶數(shù)，則葉子結點數(shù)為 N/2。 ? 注意： 滿二叉樹：除最后一層以外，每一層上的所有結點都有兩個子結點。 ? 十七 .二叉樹的定義 ? 二叉樹是另一種樹型結構，它的特點是每個結點至多只有二棵子樹（即二叉樹中不存在度大于 2的結點 ),并且 ,二叉樹的子樹有左右之分 ,其次序不能任意顛倒。 ?如果將樹中結點的各子樹看成從左至右是有次序的，則稱該樹為有序樹，否則稱為無序樹。其雙親在同一層的結點互為堂兄弟。 ?以某結點為根的子樹中的任一結點都稱為該結點的子孫 。 ?同一個雙親的孩子之間互稱 兄弟 。 ?樹的度是樹內各結點的度的最大值。 ?度為 0的結點稱為 葉子 或 終端結點 。在任意一棵非空樹中： (1)有且僅有一個特定的稱為根的結點； (2)當 n1時 ,其余結點可分為 m(m0)個互不相交的有限集 T1,T2,...Tm,其中每一個集合本身又是一棵樹 ,并且稱為根的子樹 . ?二、樹的基本概念： ?樹的 結點 包含一個數(shù)據(jù)元素及若干指向其子樹的分支。這題有 2個答案。 ?在 中，只要指出表中任何一個結點的位置，就可以從它出發(fā) 依次 訪問到表中其他所有結點。 ?十五 .循環(huán)鏈表的存儲結構及其基本運算 是另一種形式的鏈式存儲結構，它的特點是表中最后一個結點的指針域指向頭結點，整個鏈表形成一個環(huán)。 十三 .線性鏈表的基本運算 ?用鏈表表示線性表的優(yōu)點是 ______。缺點是不容易找到直接前趨。當循環(huán)隊列為空 S=0，不能進行退隊運算，
環(huán)評公示相關推薦
鄂ICP備17016276號-1