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

1、-本頁(yè)為預(yù)覽頁(yè)P(yáng)AGE13-本頁(yè)為預(yù)覽頁(yè)-本頁(yè)為預(yù)覽頁(yè)22春學(xué)期（高起本1709-1803、全層次1809-2103）數(shù)據(jù)結(jié)構(gòu)在線作業(yè)-00001第1題. 一個(gè)向量第一個(gè)元素的存儲(chǔ)地址是100，每個(gè)元素的長(zhǎng)度為2，則第5個(gè)元素的地址是()選項(xiàng)A：110選項(xiàng)B：108選項(xiàng)C：100選項(xiàng)D：120參考答案：B第2題. 下列關(guān)鍵字序列中，()是堆選項(xiàng)A：16,72,31,23,94,53選項(xiàng)B：94,23,31,72,16,53選項(xiàng)C：16,53,23,94，31,72選項(xiàng)D：16,23,53,31,94,72參考答案：D第3題. 不含任何結(jié)點(diǎn)的空樹（）選項(xiàng)A：是一棵樹選項(xiàng)B：是一棵二叉樹選項(xiàng)C：是

2、一棵樹也是一棵二叉樹選項(xiàng)D：既不是樹也不是二叉樹參考答案：C第4題. 對(duì)有n個(gè)記錄的表作快速排序，在最壞情況下，算法的時(shí)間復(fù)雜度是()選項(xiàng)A：O(n)選項(xiàng)B：O(n2)選項(xiàng)C：O(nlog2n)選項(xiàng)D：O(n3)參考答案：B第5題. 已知圖的鄰接矩陣，根據(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第6題. 設(shè)a1、a2、a3為3個(gè)結(jié)點(diǎn)，整數(shù)P0，3，4代表地址，則如下的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為（）選項(xiàng)A：循環(huán)鏈表選項(xiàng)B：?jiǎn)捂湵磉x項(xiàng)C：雙向循環(huán)

3、鏈表選項(xiàng)D：雙向鏈表參考答案：B第7題. 用鄰接表表示圖進(jìn)行廣度優(yōu)先遍歷時(shí)，通常是采用（）來(lái)實(shí)現(xiàn)算法的選項(xiàng)A：棧選項(xiàng)B：隊(duì)列選項(xiàng)C：樹選項(xiàng)D：圖參考答案：B第8題. 把一棵樹轉(zhuǎn)換為二叉樹后，這棵二叉樹的形態(tài)是（）選項(xiàng)A：唯一的選項(xiàng)B：有多種選項(xiàng)C：有多種，但根結(jié)點(diǎn)都沒(méi)有左孩子選項(xiàng)D：有多種，但根結(jié)點(diǎn)都沒(méi)有右孩子參考答案：A第9題. 有8個(gè)結(jié)點(diǎn)的有向完全圖有（）條邊選項(xiàng)A：14選項(xiàng)B：28選項(xiàng)C：56選項(xiàng)D：112參考答案：C第10題. 折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，則它將依次與表中()比較大小，查找結(jié)果是失敗。選項(xiàng)A：20，70

4、，30，50選項(xiàng)B：30，88，70，50選項(xiàng)C：20，50選項(xiàng)D：30，88，50參考答案：A第11題. 鏈表適用于()查找選項(xiàng)A：順序選項(xiàng)B：二分法選項(xiàng)C：順序，也能二分法選項(xiàng)D：隨機(jī)參考答案：A第12題. 用鄰接表表示圖進(jìn)行深度優(yōu)先遍歷時(shí)，通常是采用()來(lái)實(shí)現(xiàn)算法的選項(xiàng)A：棧選項(xiàng)B：隊(duì)列選項(xiàng)C：樹選項(xiàng)D：圖參考答案：A第13題. 若一組記錄的排序碼為（46, 79, 56, 38, 40, 84），則利用堆排序的方法建立的初始堆為()選項(xiàng)A：79,46,56,38,40,84選項(xiàng)B：84,79,56,38,40,46選項(xiàng)C：84,79,56,46,40,38選項(xiàng)D：84,56,79,40

5、,46,38參考答案：B第14題. 設(shè)有兩個(gè)串p和q，求q在p中首次出現(xiàn)的位置的運(yùn)算稱作（）選項(xiàng)A：連接選項(xiàng)B：模式匹配選項(xiàng)C：求子串選項(xiàng)D：求串長(zhǎng)參考答案：B第15題. 數(shù)組用來(lái)表示一個(gè)循環(huán)隊(duì)列，為當(dāng)前隊(duì)列頭元素的前一位置，為隊(duì)尾元素的位置，假定隊(duì)列中元素的個(gè)數(shù)小于，計(jì)算隊(duì)列中元素的公式為選項(xiàng)A：rf選項(xiàng)B：（nfr）% n選項(xiàng)C：nrf選項(xiàng)D：（nrf）% n參考答案：D第16題. 折半搜索與二叉搜索樹的時(shí)間性能()選項(xiàng)A：相同選項(xiàng)B：完全不同選項(xiàng)C：有時(shí)不相同選項(xiàng)D：數(shù)量級(jí)都是O（log2n）參考答案：C第17題. 下述幾種排序方法中，要求內(nèi)存最大的是()選項(xiàng)A：插入排序選項(xiàng)B：快速排序

6、選項(xiàng)C：歸并排序選項(xiàng)D：選擇排序參考答案：C第18題. 已知圖的鄰接矩陣，根據(jù)算法，則從頂點(diǎn)0出發(fā)，按廣度優(yōu)先遍歷的結(jié)點(diǎn)序列是（）選項(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第19題. 在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的（）倍。選項(xiàng)A：1/2選項(xiàng)B：1選項(xiàng)C：2選項(xiàng)D：4參考答案：B第20題. 二叉樹是非線性數(shù)據(jù)結(jié)構(gòu)，所以（）選項(xiàng)A：它不能用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)選項(xiàng)B：它不能用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ)選項(xiàng)C：順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)都能存儲(chǔ)選項(xiàng)D：順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)都不

7、能使用參考答案：C第21題. 堆的形狀是一棵()選項(xiàng)A：二叉排序樹選項(xiàng)B：滿二叉樹選項(xiàng)C：完全二叉樹選項(xiàng)D：平衡二叉樹參考答案：C第22題. 若已知一個(gè)棧的入棧序列是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：不確定參考答案：C第23題. 在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于圖的邊數(shù)的（）倍選項(xiàng)A：1/2選項(xiàng)B：1選項(xiàng)C：2選項(xiàng)D：4參考答案：C第24題. 已知圖的鄰接矩陣，根據(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 5 6 4 2選項(xiàng)C：0 4 2

8、 3 1 6 5選項(xiàng)D：0 1 3 4 2 5 6參考答案：D第25題. 鏈接存儲(chǔ)的存儲(chǔ)結(jié)構(gòu)所占存儲(chǔ)空間（）選項(xiàng)A：分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放表示結(jié)點(diǎn)間關(guān)系的指針選項(xiàng)B：只有一部分，存放結(jié)點(diǎn)值選項(xiàng)C：只有一部分，存儲(chǔ)表示結(jié)點(diǎn)間關(guān)系的指針選項(xiàng)D：分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放結(jié)點(diǎn)所占單元數(shù)參考答案：A第26題. 鏈表是一種采用 存儲(chǔ)結(jié)構(gòu)存儲(chǔ)的線性表選項(xiàng)A：順序選項(xiàng)B：鏈?zhǔn)竭x項(xiàng)C：星式選項(xiàng)D：網(wǎng)狀參考答案：B第27題. 串是一種特殊的線性表，其特殊性體現(xiàn)在（）選項(xiàng)A：可以順序存儲(chǔ)選項(xiàng)B：數(shù)據(jù)元素是一個(gè)字符選項(xiàng)C：可以鏈?zhǔn)酱鎯?chǔ)選項(xiàng)D：數(shù)據(jù)元素可以是多個(gè)字符參考答案：B第28題

9、. 單鏈表的存儲(chǔ)密度（）選項(xiàng)A：大于1選項(xiàng)B：等于1選項(xiàng)C：小于1選項(xiàng)D：不能確定參考答案：C第29題. 判定一個(gè)棧ST（最多元素為m0）為空的條件是（）選項(xiàng)A：ST-top0選項(xiàng)B：ST-top=0選項(xiàng)C：ST-topm0選項(xiàng)D：ST-top=m0參考答案：B第30題. 對(duì)22個(gè)記錄的有序表作折半查找，當(dāng)查找失敗時(shí)，至少需要比較()次關(guān)鍵字。選項(xiàng)A：3選項(xiàng)B：4選項(xiàng)C：5選項(xiàng)D：6參考答案：C第31題. 順序表結(jié)構(gòu)適宜于進(jìn)行順序存取，而鏈表適宜于進(jìn)行隨機(jī)存取。選項(xiàng)A：錯(cuò)誤選項(xiàng)B：正確參考答案：A第32題. 隊(duì)是一種插入與刪除操作分別在表的兩端進(jìn)行的線性表，是一種先進(jìn)后出型結(jié)構(gòu)。選項(xiàng)A：錯(cuò)誤選

10、項(xiàng)B：正確參考答案：A第33題. 二叉樹中每個(gè)結(jié)點(diǎn)有兩棵非空子樹或有兩棵空子樹。選項(xiàng)A：錯(cuò)誤選項(xiàng)B：正確參考答案：A第34題. 二叉樹中所有結(jié)點(diǎn)個(gè)數(shù)是2k-1-1，其中k是樹的深度。選項(xiàng)A：錯(cuò)誤選項(xiàng)B：正確參考答案：A第35題. 順序存儲(chǔ)方式只能用于存儲(chǔ)線性結(jié)構(gòu)。選項(xiàng)A：錯(cuò)誤選項(xiàng)B：正確參考答案：A第36題. 二叉樹中每個(gè)結(jié)點(diǎn)的兩棵子樹是有序的。選項(xiàng)A：錯(cuò)誤選項(xiàng)B：正確參考答案：B第37題. 兩個(gè)棧共享一片連續(xù)內(nèi)存空間時(shí)，為提高內(nèi)存利用率，減少溢出機(jī)會(huì)，應(yīng)把兩個(gè)棧的棧底分別設(shè)在這片內(nèi)存空間的兩端。選項(xiàng)A：錯(cuò)誤選項(xiàng)B：正確參考答案：B第38題. 若二叉樹用二叉鏈表作存貯結(jié)構(gòu)，則在n個(gè)結(jié)點(diǎn)的二叉樹

11、鏈表中只有n1個(gè)非空指針域。選項(xiàng)A：錯(cuò)誤選項(xiàng)B：正確參考答案：B第39題. 鏈表的刪除算法很簡(jiǎn)單，因?yàn)楫?dāng)刪除鏈中某個(gè)結(jié)點(diǎn)后，計(jì)算機(jī)會(huì)自動(dòng)地將后續(xù)的各個(gè)單元向前移動(dòng)。選項(xiàng)A：錯(cuò)誤選項(xiàng)B：正確參考答案：A第40題. 順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大，且插入、刪除運(yùn)算效率高。選項(xiàng)A：錯(cuò)誤選項(xiàng)B：正確參考答案：A第41題. 在表結(jié)構(gòu)中最常用的是線性表，棧和隊(duì)列不太常用。選項(xiàng)A：錯(cuò)誤選項(xiàng)B：正確參考答案：A第42題. 鏈表的物理存儲(chǔ)結(jié)構(gòu)具有同鏈表一樣的順序。選項(xiàng)A：錯(cuò)誤選項(xiàng)B：正確參考答案：A第43題. 一個(gè)棧的輸入序列是12345，則棧的輸出序列不可能是12345。選項(xiàng)A：錯(cuò)誤選項(xiàng)B：正確參考答案：A第44題. 線性表的邏輯順序與存儲(chǔ)順序總是一致的。選項(xiàng)A：錯(cuò)誤選項(xiàng)B：正確參考答案：A第45題. 對(duì)于不同的使用者，一個(gè)表結(jié)構(gòu)既可以是棧，也可以是隊(duì)列，也可以是線性表選項(xiàng)A：錯(cuò)誤選項(xiàng)B：正確參考答案：B第46題. 線性表的每個(gè)結(jié)點(diǎn)只能是一個(gè)簡(jiǎn)單類型，而鏈表的每個(gè)結(jié)點(diǎn)可以是一個(gè)復(fù)雜類型。選項(xiàng)A：錯(cuò)誤選項(xiàng)B：正確參考答案：A第47題. 棧和隊(duì)列是一種非線性數(shù)據(jù)結(jié)構(gòu)。選