南開大學(xué)22年春學(xué)期《數(shù)據(jù)結(jié)構(gòu)》在線作業(yè)-00003

1、-本頁為預(yù)覽頁P(yáng)AGE14-本頁為預(yù)覽頁-本頁為預(yù)覽頁22春學(xué)期（高起本1709-1803、全層次1809-2103）數(shù)據(jù)結(jié)構(gòu)在線作業(yè)-00003第1題. 有8個結(jié)點(diǎn)的有向完全圖有（）條邊選項(xiàng)A：14選項(xiàng)B：28選項(xiàng)C：56選項(xiàng)D：112參考答案：C第2題. 有8個結(jié)點(diǎn)的無向圖最多有（）條邊選項(xiàng)A：14選項(xiàng)B：28選項(xiàng)C：56選項(xiàng)D：112參考答案：B第3題. 一個向量第一個元素的存儲地址是100，每個元素的長度為2，則第5個元素的地址是()選項(xiàng)A：110選項(xiàng)B：108選項(xiàng)C：100選項(xiàng)D：120參考答案：B第4題. 已知圖的鄰接矩陣，根據(jù)算法，則從頂點(diǎn)0出發(fā)，按廣度優(yōu)先遍歷的結(jié)點(diǎn)序列是（）選

2、項(xiàng)A：0 2 4 3 6 5 1選項(xiàng)B：0 1 3 6 4 2 5選項(xiàng)C：0 4 2 3 1 5 6選項(xiàng)D：0 1 3 4 2 5 6參考答案：B第5題. 折半搜索與二叉搜索樹的時間性能()選項(xiàng)A：相同選項(xiàng)B：完全不同選項(xiàng)C：有時不相同選項(xiàng)D：數(shù)量級都是O（log2n）參考答案：C第6題. 堆的形狀是一棵()選項(xiàng)A：二叉排序樹選項(xiàng)B：滿二叉樹選項(xiàng)C：完全二叉樹選項(xiàng)D：平衡二叉樹參考答案：C第7題. 線性表在（）情況下適用于使用鏈?zhǔn)浇Y(jié)構(gòu)實(shí)現(xiàn)。選項(xiàng)A：需經(jīng)常修改中的結(jié)點(diǎn)值選項(xiàng)B：需不斷對進(jìn)行刪除插入選項(xiàng)C：中含有大量的結(jié)點(diǎn)選項(xiàng)D：中結(jié)點(diǎn)結(jié)構(gòu)復(fù)雜參考答案：B第8題. 從未排序序列中挑選元素，并將其依

3、次插入已排序序列（初始時為空）的一端的方法，稱為()選項(xiàng)A：希爾排序選項(xiàng)B：歸并排序選項(xiàng)C：插入排序選項(xiàng)D：選擇排序參考答案：D第9題. 引入二叉線索樹的目的是（ ）選項(xiàng)A：加快查找結(jié)點(diǎn)的前驅(qū)或后繼的速度選項(xiàng)B：為了能在二叉樹中方便的進(jìn)行插入與刪除選項(xiàng)C：為了能方便的找到雙親選項(xiàng)D：使二叉樹的遍歷結(jié)果唯一參考答案：A第10題. 鏈表是一種采用 存儲結(jié)構(gòu)存儲的線性表選項(xiàng)A：順序選項(xiàng)B：鏈?zhǔn)竭x項(xiàng)C：星式選項(xiàng)D：網(wǎng)狀參考答案：B第11題. 一棵具有 n個結(jié)點(diǎn)的完全二叉樹的樹高度（深度）是（）選項(xiàng)A：選項(xiàng)B：選項(xiàng)C：選項(xiàng)D：參考答案：A第12題. 用鄰接表表示圖進(jìn)行深度優(yōu)先遍歷時，通常是采用()來實(shí)現(xiàn)

4、算法的選項(xiàng)A：棧選項(xiàng)B：隊(duì)列選項(xiàng)C：樹選項(xiàng)D：圖參考答案：A第13題. 設(shè)有兩個串p和q，求q在p中首次出現(xiàn)的位置的運(yùn)算稱作（）選項(xiàng)A：連接選項(xiàng)B：模式匹配選項(xiàng)C：求子串選項(xiàng)D：求串長參考答案：B第14題. 已知一棵二叉樹的前序遍歷結(jié)果為ABCDEF,中序遍歷結(jié)果為CBAEDF,則后序遍歷的結(jié)果為()選項(xiàng)A：CBEFDA選項(xiàng)B：FEDCBA選項(xiàng)C：CBEDFA選項(xiàng)D：不定參考答案：A第15題. 在n個結(jié)點(diǎn)的順序表中，算法的時間復(fù)雜度是O（1）的操作是（）選項(xiàng)A：訪問第i個結(jié)點(diǎn)（1in）和求第i個結(jié)點(diǎn)的直接前驅(qū)（2in）選項(xiàng)B：在第i個結(jié)點(diǎn)后插入一個新結(jié)點(diǎn)（1in）選項(xiàng)C：刪除第i個結(jié)點(diǎn)（1in

5、）選項(xiàng)D：將n個結(jié)點(diǎn)從小到大排序參考答案：A第16題. 快速排序在下列哪種情況下最易發(fā)揮其長處()選項(xiàng)A：被排序的數(shù)據(jù)中含有多個相同排序碼選項(xiàng)B：被排序的數(shù)據(jù)已基本有序選項(xiàng)C：被排序的數(shù)據(jù)完全無序選項(xiàng)D：被排序的數(shù)據(jù)中的最大值和最小值相差懸殊參考答案：C第17題. 判定一個隊(duì)列QU（最多元素為m0）為滿隊(duì)列的條件是（）選項(xiàng)A：QU-rear QU-front = = m0選項(xiàng)B：QU-rear QU-front 1= = m0選項(xiàng)C：QU-front = = QU-rear選項(xiàng)D：QU-front = = QU-rear+1參考答案：A第18題. 具有n(n0)個結(jié)點(diǎn)的完全二叉樹的深度為（ ）

6、選項(xiàng)A：選項(xiàng)B：選項(xiàng)C：選項(xiàng)D：參考答案：C第19題. 已知圖的鄰接矩陣，根據(jù)算法思想，則從頂點(diǎn)0出發(fā)按深度優(yōu)先遍歷的結(jié)點(diǎn)序列是（ ）選項(xiàng)A：0 2 4 3 1 5 6選項(xiàng)B：0 1 3 6 5 4 2選項(xiàng)C：0 4 2 3 1 6 5選項(xiàng)D：0 3 6 1 5 4 2參考答案：C第20題. 向一個有127個元素的順序表中插入一個新元素并保持原來順序不變，平均要移動（）個元素選項(xiàng)A：8選項(xiàng)B：63.5選項(xiàng)C：63選項(xiàng)D：7參考答案：B第21題. 若已知一個棧的入棧序列是1，2，3，n，其輸出序列為p1，p2，p3，pn，若p1=n，則pi為（）選項(xiàng)A：i選項(xiàng)B：n=i選項(xiàng)C：n-i+1選項(xiàng)D：

7、不確定參考答案：C第22題. 鏈接存儲的存儲結(jié)構(gòu)所占存儲空間（）選項(xiàng)A：分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放表示結(jié)點(diǎn)間關(guān)系的指針選項(xiàng)B：只有一部分，存放結(jié)點(diǎn)值選項(xiàng)C：只有一部分，存儲表示結(jié)點(diǎn)間關(guān)系的指針選項(xiàng)D：分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放結(jié)點(diǎn)所占單元數(shù)參考答案：A第23題. 對有n個記錄的表作快速排序，在最壞情況下，算法的時間復(fù)雜度是()選項(xiàng)A：O(n)選項(xiàng)B：O(n2)選項(xiàng)C：O(nlog2n)選項(xiàng)D：O(n3)參考答案：B第24題. 數(shù)據(jù)在計算機(jī)存儲器內(nèi)表示時，物理地址與邏輯地址相同并且是連續(xù)的，稱之為()選項(xiàng)A：存儲結(jié)構(gòu)選項(xiàng)B：邏輯結(jié)構(gòu)選項(xiàng)C：順序存儲結(jié)構(gòu)選項(xiàng)D：鏈?zhǔn)酱鎯?/p>

8、結(jié)構(gòu)參考答案：C第25題. 任何一個無向連通圖的最小生成樹()選項(xiàng)A：只有一棵選項(xiàng)B：一棵或多棵選項(xiàng)C：一定有多棵選項(xiàng)D：可能不存在參考答案：A第26題. 將5個不同的數(shù)據(jù)進(jìn)行排序，至多需要比較()次選項(xiàng)A：8選項(xiàng)B：9選項(xiàng)C：10選項(xiàng)D：25參考答案：C第27題. 廣度優(yōu)先遍歷類似于二叉樹的()選項(xiàng)A：先序遍歷選項(xiàng)B：中序遍歷選項(xiàng)C：后序遍歷選項(xiàng)D：層次遍歷參考答案：D第28題. 用鄰接表表示圖進(jìn)行廣度優(yōu)先遍歷時，通常是采用（）來實(shí)現(xiàn)算法的選項(xiàng)A：棧選項(xiàng)B：隊(duì)列選項(xiàng)C：樹選項(xiàng)D：圖參考答案：B第29題. 設(shè)串s1=ABCDEFG，s2=PQRST，函數(shù)con(x,y)返回x和y串的連接串，s

9、ubs(s, i, j)返回串s的從序號i開始的j個字符組成的子串，len(s)返回串s的長度，則con(subs(s1, 2, len(s2), subs(s1, len(s2), 2)的結(jié)果串是（）選項(xiàng)A：BCDEF選項(xiàng)B：BCDEFG選項(xiàng)C：BCPQRST選項(xiàng)D：BCDEFEF參考答案：D第30題. 設(shè)a1、a2、a3為3個結(jié)點(diǎn)，整數(shù)P0，3，4代表地址，則如下的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為（）選項(xiàng)A：循環(huán)鏈表選項(xiàng)B：單鏈表選項(xiàng)C：雙向循環(huán)鏈表選項(xiàng)D：雙向鏈表參考答案：B第31題. 具有12個結(jié)點(diǎn)的完全二叉樹有5個度為2的結(jié)點(diǎn)。選項(xiàng)A：錯誤選項(xiàng)B：正確參考答案：B第32題. 鏈表的刪除算法很簡單，因

10、為當(dāng)刪除鏈中某個結(jié)點(diǎn)后，計算機(jī)會自動地將后續(xù)的各個單元向前移動。選項(xiàng)A：錯誤選項(xiàng)B：正確參考答案：A第33題. 線性表的每個結(jié)點(diǎn)只能是一個簡單類型，而鏈表的每個結(jié)點(diǎn)可以是一個復(fù)雜類型。選項(xiàng)A：錯誤選項(xiàng)B：正確參考答案：A第34題. 棧和鏈表是兩種不同的數(shù)據(jù)結(jié)構(gòu)。選項(xiàng)A：錯誤選項(xiàng)B：正確參考答案：A第35題. 線性表的邏輯順序與存儲順序總是一致的。選項(xiàng)A：錯誤選項(xiàng)B：正確參考答案：A第36題. 二叉樹中所有結(jié)點(diǎn)，如果不存在非空左子樹，則不存在非空右子樹。選項(xiàng)A：錯誤選項(xiàng)B：正確參考答案：A第37題. 一個棧的輸入序列是12345，則棧的輸出序列不可能是12345。選項(xiàng)A：錯誤選項(xiàng)B：正確參考答案

11、：A第38題. 線性表在順序存儲時，邏輯上相鄰的元素未必在存儲的物理位置次序上相鄰。選項(xiàng)A：錯誤選項(xiàng)B：正確參考答案：A第39題. 兩個棧共享一片連續(xù)內(nèi)存空間時，為提高內(nèi)存利用率，減少溢出機(jī)會，應(yīng)把兩個棧的棧底分別設(shè)在這片內(nèi)存空間的兩端。選項(xiàng)A：錯誤選項(xiàng)B：正確參考答案：B第40題. 若二叉樹用二叉鏈表作存貯結(jié)構(gòu)，則在n個結(jié)點(diǎn)的二叉樹鏈表中只有n1個非空指針域。選項(xiàng)A：錯誤選項(xiàng)B：正確參考答案：B第41題. 線性表在物理存儲空間中也一定是連續(xù)的。選項(xiàng)A：錯誤選項(xiàng)B：正確參考答案：A第42題. 隊(duì)是一種插入與刪除操作分別在表的兩端進(jìn)行的線性表，是一種先進(jìn)后出型結(jié)構(gòu)。選項(xiàng)A：錯誤選項(xiàng)B：正確參考答案：A第43題. 二叉樹中每個結(jié)點(diǎn)的兩棵子樹的高度差等于1。選項(xiàng)A：錯誤選項(xiàng)B：正確參考答案：A第44題. 棧是一種對所有插入、刪除操作限于在表的一端進(jìn)行的線性表，是一種后進(jìn)先出型結(jié)構(gòu)。選項(xiàng)A：錯誤選項(xiàng)B：正確參考答案：B第45題. 順序存儲方式只能用于存儲線性結(jié)構(gòu)。選項(xiàng)A：錯誤選項(xiàng)B：正確參考答案：A第46題. 對于一棵非空二叉樹，它的根結(jié)點(diǎn)作為第一層，則它的第i層上最多能有2i1個結(jié)點(diǎn)。選項(xiàng)A：錯誤選項(xiàng)B：正確參考答案：A第47題. 用二叉鏈表法（link-rlin