1、-本頁為預覽頁PAGE13-本頁為預覽頁-本頁為預覽頁22春學期（高起本1709-1803、全層次1809-2103）數據結構在線作業-00002第1題. 設有兩個串p和q，求q在p中首次出現的位置的運算稱作（）選項A：連接選項B：模式匹配選項C：求子串選項D：求串長參考答案：B第2題. 設F是一個森林，B是由F變換得的二叉樹。若F中有n個非終端結點，則B中右指針域為空的結點有()個選項A：n-1選項B：n選項C：n+1選項D：n+2參考答案：C第3題. 若一組記錄的排序碼為（46, 79, 56, 38, 40, 84），則利用堆排序的方法建立的初始堆為()選項A：79,46,56,38,4

2、0,84選項B：84,79,56,38,40,46選項C：84,79,56,46,40,38選項D：84,56,79,40,46,38參考答案：B第4題. 排序方法中，從未排序序列中依次取出元素與已排序序列（初始時為空）中的元素進行比較，將其放入已排序序列的正確位置上的方法，稱為()選項A：希爾排序選項B：冒泡排序選項C：插入排序選項D：選擇排序參考答案：C第5題. 快速排序在下列哪種情況下最易發揮其長處()選項A：被排序的數據中含有多個相同排序碼選項B：被排序的數據已基本有序選項C：被排序的數據完全無序選項D：被排序的數據中的最大值和最小值相差懸殊參考答案：C第6題. 折半搜索與二叉搜索樹的

3、時間性能()選項A：相同選項B：完全不同選項C：有時不相同選項D：數量級都是O（log2n）參考答案：C第7題. 把一棵樹轉換為二叉樹后，這棵二叉樹的形態是（）選項A：唯一的選項B：有多種選項C：有多種，但根結點都沒有左孩子選項D：有多種，但根結點都沒有右孩子參考答案：A第8題. 設a1、a2、a3為3個結點，整數P0，3，4代表地址，則如下的鏈式存儲結構稱為（）選項A：循環鏈表選項B：單鏈表選項C：雙向循環鏈表選項D：雙向鏈表參考答案：B第9題. 有8個結點的有向完全圖有（）條邊選項A：14選項B：28選項C：56選項D：112參考答案：C第10題. 堆的形狀是一棵()選項A：二叉排序樹選項

4、B：滿二叉樹選項C：完全二叉樹選項D：平衡二叉樹參考答案：C第11題. 已知圖的鄰接表如下所示，根據算法，則從頂點0出發按深度優先遍歷的結點序列是（）選項A：0 1 3 2選項B：0 2 3 1選項C：0 3 2 1選項D：0 1 2 3參考答案：D第12題. 下述幾種排序方法中，要求內存最大的是()選項A：插入排序選項B：快速排序選項C：歸并排序選項D：選擇排序參考答案：C第13題. 單鏈表的存儲密度（）選項A：大于1選項B：等于1選項C：小于1選項D：不能確定參考答案：C第14題. 廣度優先遍歷類似于二叉樹的()選項A：先序遍歷選項B：中序遍歷選項C：后序遍歷選項D：層次遍歷參考答案：D第

5、15題. 深度優先遍歷類似于二叉樹的()選項A：先序遍歷選項B：中序遍歷選項C：后序遍歷選項D：層次遍歷參考答案：A第16題. 不含任何結點的空樹（）選項A：是一棵樹選項B：是一棵二叉樹選項C：是一棵樹也是一棵二叉樹選項D：既不是樹也不是二叉樹參考答案：C第17題. 線性表若采用鏈式存儲結構時，要求內存中可用存儲單元的地址（）選項A：必須是連續的選項B：部分地址必須是連續的選項C：一定是不連續的選項D：連續或不連續都可以參考答案：D第18題. 下列關鍵字序列中，()是堆選項A：16,72,31,23,94,53選項B：94,23,31,72,16,53選項C：16,53,23,94，31,72

6、選項D：16,23,53,31,94,72參考答案：D第19題. 對有n個記錄的表作快速排序，在最壞情況下，算法的時間復雜度是()選項A：O(n)選項B：O(n2)選項C：O(nlog2n)選項D：O(n3)參考答案：B第20題. 對22個記錄的有序表作折半查找，當查找失敗時，至少需要比較()次關鍵字。選項A：3選項B：4選項C：5選項D：6參考答案：C第21題. 已知圖的鄰接矩陣，根據算法，則從頂點0出發，按廣度優先遍歷的結點序列是（）選項A：0 2 4 3 1 6 5選項B：0 1 3 5 6 4 2選項C：0 1 2 3 4 6 5選項D：0 1 2 3 4 5 6參考答案：C第22題.

7、 在一個圖中，所有頂點的度數之和等于圖的邊數的（）倍選項A：1/2選項B：1選項C：2選項D：4參考答案：C第23題. 設串s1=ABCDEFG，s2=PQRST，函數con(x,y)返回x和y串的連接串，subs(s, i, j)返回串s的從序號i開始的j個字符組成的子串，len(s)返回串s的長度，則con(subs(s1, 2, len(s2), subs(s1, len(s2), 2)的結果串是（）選項A：BCDEF選項B：BCDEFG選項C：BCPQRST選項D：BCDEFEF參考答案：D第24題. 判定一個隊列QU（最多元素為m0）為滿隊列的條件是（）選項A：QU-rear QU-

8、front = = m0選項B：QU-rear QU-front 1= = m0選項C：QU-front = = QU-rear選項D：QU-front = = QU-rear+1參考答案：A第25題. 鏈表是一種采用 存儲結構存儲的線性表選項A：順序選項B：鏈式選項C：星式選項D：網狀參考答案：B第26題. 一個向量第一個元素的存儲地址是100，每個元素的長度為2，則第5個元素的地址是()選項A：110選項B：108選項C：100選項D：120參考答案：B第27題. 將5個不同的數據進行排序，至多需要比較()次選項A：8選項B：9選項C：10選項D：25參考答案：C第28題. 從未排序序列中

9、挑選元素，并將其依次插入已排序序列（初始時為空）的一端的方法，稱為()選項A：希爾排序選項B：歸并排序選項C：插入排序選項D：選擇排序參考答案：D第29題. 二叉樹是非線性數據結構，所以（）選項A：它不能用順序存儲結構存儲選項B：它不能用鏈式存儲結構存儲選項C：順序存儲結構和鏈式存儲結構都能存儲選項D：順序存儲結構和鏈式存儲結構都不能使用參考答案：C第30題. 鏈表適用于()查找選項A：順序選項B：二分法選項C：順序，也能二分法選項D：隨機參考答案：A第31題. 棧和隊列的存儲方式既可是順序方式，也可是鏈接方式。選項A：錯誤選項B：正確參考答案：B第32題. 鏈表的物理存儲結構具有同鏈表一樣的

10、順序。選項A：錯誤選項B：正確參考答案：A第33題. 順序存儲方式的優點是存儲密度大，且插入、刪除運算效率高。選項A：錯誤選項B：正確參考答案：A第34題. 線性表的每個結點只能是一個簡單類型，而鏈表的每個結點可以是一個復雜類型。選項A：錯誤選項B：正確參考答案：A第35題. 兩個棧共享一片連續內存空間時，為提高內存利用率，減少溢出機會，應把兩個棧的棧底分別設在這片內存空間的兩端。選項A：錯誤選項B：正確參考答案：B第36題. 一個棧的輸入序列是12345，則棧的輸出序列不可能是12345。選項A：錯誤選項B：正確參考答案：A第37題. 二叉樹中每個結點的兩棵子樹是有序的。選項A：錯誤選項B：

11、正確參考答案：B第38題. 二叉樹中所有結點個數是2k-1-1，其中k是樹的深度。選項A：錯誤選項B：正確參考答案：A第39題. 順序表結構適宜于進行順序存取，而鏈表適宜于進行隨機存取。選項A：錯誤選項B：正確參考答案：A第40題. 棧和隊列是一種非線性數據結構。選項A：錯誤選項B：正確參考答案：A第41題. 棧是一種對所有插入、刪除操作限于在表的一端進行的線性表，是一種后進先出型結構。選項A：錯誤選項B：正確參考答案：B第42題. 線性表在順序存儲時，邏輯上相鄰的元素未必在存儲的物理位置次序上相鄰。選項A：錯誤選項B：正確參考答案：A第43題. 二叉樹中每個結點有兩棵非空子樹或有兩棵空子樹。選項A：錯誤選項B：正確參考答案：A第44題. 順序存儲方式只能用于存儲線性結構。選項A：錯誤選項B：正確參考答案：A第45題. 二叉樹中每個結點的關鍵字值大于其左非空子樹（若存在的話）所有結點的關鍵字值，且小于其右非空子樹（若存在的話）所有結點的關鍵字值。選項A：錯誤選項B：正確參考答案：A第46題. 線性表的邏輯順序與存儲順序總是一致的。選項A：錯誤選項B：正確參考答案：A第47題. 具有12個結點的完全二叉樹有5個度為2的結點。選項A：