《數據結構》期末模擬試題一.docx

《數據結構》期末模擬試題一 《數據結構》期末模擬試題一 一、單選題(每小題 2 分，共 8 分) 結點。 結點。 在一個單鏈表HL中，若要向表頭插入一個由指針 p指向的結點，則執行 。 A HL=p; p->next=HL; B p->next=HL; HL=p; C p->next=HL; p=HL; D p->next=HL->next; HL->next=p; 在一個順序隊列中，隊首指針指向隊首元素的 位置。 A 前一個 B 后一個 C 當前 從二叉搜索樹中查找一個元素時，其時間復雜度大致為 。 2 A O(n) B O(1) C O(log 2n) D O(n 2) 由權值分別為 3,8,6,2,5 的葉子結點生成一棵哈夫曼樹，它的帶權路徑長度為 。 A 24 B 48 C 72 D 53 二、填空題(每空 1 分，共 32 分) TOC \o "1-5" \h \z 一個算法的時間復雜度為 (3 n2+2nlog 2n+4n-7)/(5 n) ，其數量級表示為 。 在以HL為表頭指針的帶表頭附加結點的單鏈表和循環單鏈表中， 鏈表為空的條件分 別為 和 。 3．一個廣義表中的元素分為 元素和 元素兩類。 4．從一個鏈棧中刪除一個結點時，需要把棧頂結點的 域的值賦給 。 5．在進行函數調用時，需要把每個實參的值和調用后的 傳送給被調用的函數 中。 對于一棵具有n個結點的二叉樹，若一個結點的編號為 i(1 < i w n)，則它的左孩子 結點的編號為 ，右孩子結點的編號為 ，雙親結點的編號為 。 在一棵高度為 5 的理想平衡樹中，最少含有 個結點，最多含有 個 在一個單鏈表HL中，若要向表頭插入一個由指針 p指向的結點，則執行 。 A HL=p; p->next=HL; B p->next=HL; HL=p; C p->next=HL; p=HL; D p->next=HL->next; HL->next=p; 在一個順序隊列中，隊首指針指向隊首元素的 位置。 A 前一個 B 后一個 C 當前 從二叉搜索樹中查找一個元素時，其時間復雜度大致為 。 2 A O(n) B O(1) C O(log 2n) D O(n 2) 由權值分別為 3,8,6,2,5 的葉子結點生成一棵哈夫曼樹，它的帶權路徑長度為 。 A 24 B 48 C 72 D 53 二、填空題(每空 1 分，共 32 分) TOC \o "1-5" \h \z 一個算法的時間復雜度為 (3 n2+2nlog 2n+4n-7)/(5 n) ，其數量級表示為 。 在以HL為表頭指針的帶表頭附加結點的單鏈表和循環單鏈表中， 鏈表為空的條件分 別為 和 。 3．一個廣義表中的元素分為 元素和 元素兩類。 4．從一個鏈棧中刪除一個結點時，需要把棧頂結點的 域的值賦給 。 5．在進行函數調用時，需要把每個實參的值和調用后的 傳送給被調用的函數 中。 對于一棵具有n個結點的二叉樹，若一個結點的編號為 i(1 < i w n)，則它的左孩子 結點的編號為 ，右孩子結點的編號為 ，雙親結點的編號為 。 在一棵高度為 5 的理想平衡樹中，最少含有 個結點，最多含有 個 在一個單鏈表HL中，若要向表頭插入一個由指針 p指向的結點，則執行 。 A HL=p; p->next=HL; B p->next=HL; HL=p; C p->next=HL; p=HL; D p->next=HL->next; HL->next=p; 在一個順序隊列中，隊首指針指向隊首元素的 位置。 A 前一個 B 后一個 C 當前 從二叉搜索樹中查找一個元素時，其時間復雜度大致為 。 2 A O(n) B O(1) C O(log 2n) D O(n 2) 由權值分別為 3,8,6,2,5 的葉子結點生成一棵哈夫曼樹，它的帶權路徑長度為 。 A 24 B 48 C 72 D 53 二、填空題(每空 1 分，共 32 分) TOC \o "1-5" \h \z 一個算法的時間復雜度為 (3 n2+2nlog 2n+4n-7)/(5 n) ，其數量級表示為 。 在以HL為表頭指針的帶表頭附加結點的單鏈表和循環單鏈表中， 鏈表為空的條件分 別為 和 。 3．一個廣義表中的元素分為 元素和 元素兩類。 4．從一個鏈棧中刪除一個結點時，需要把棧頂結點的 域的值賦給 。 5．在進行函數調用時，需要把每個實參的值和調用后的 傳送給被調用的函數 中。 對于一棵具有n個結點的二叉樹，若一個結點的編號為 i(1 < i w n)，則它的左孩子 結點的編號為 ，右孩子結點的編號為 ，雙親結點的編號