南開大學(xué)20秋《數(shù)據(jù)結(jié)構(gòu)》在線作業(yè)-2（參考答案）

1、南開大學(xué)20秋數(shù)據(jù)結(jié)構(gòu)在線作業(yè)-2（參考答案）已知圖的鄰接矩陣，根據(jù)算法，則從頂點0出發(fā)，按深度優(yōu)先遍歷的結(jié)點序列是()。A.0 2 4 3 1 5 6B.0 1 3 5 6 4 2C.0 4 2 3 1 6 5D.0 1 3 4 2 5 6設(shè)有兩個串p和q，求q在p中首次出現(xiàn)的位置的運算稱作()。A.連接B.模式匹配C.求子串D.求串長一個向量第一個元素的存儲地址是100，每個元素的長度為2，則第5個元素的地址是()。A.110B.108C.100D.120已知圖的鄰接矩陣，根據(jù)算法，則從頂點0出發(fā)，按廣度優(yōu)先遍歷的結(jié)點序列是()。A.0 2 4 3 1 6 5B.0 1 3 5 6 4 2

2、C.0 1 2 3 4 6 5D.0 1 2 3 4 5 6對n個不同的排序碼進(jìn)行冒泡排序，在下列哪種情況下比較的次數(shù)最多?()A.從小到大排列好的B.從大到小排列好的C.元素?zé)o序D.元素基本有序線性表L在()情況下適用于使用鏈?zhǔn)浇Y(jié)構(gòu)實現(xiàn)。A.需經(jīng)常修改L中的結(jié)點值B.需不斷對L進(jìn)行刪除插入C.L中含有大量的結(jié)點D.L中結(jié)點結(jié)構(gòu)復(fù)雜具有n(n>0)個結(jié)點的完全二叉樹的深度為()。A.log2(n)B.log2(n)C.log2(n)+1D.log2(n)+1一棵具有n個結(jié)點的完全二叉樹的樹高度(深度)是()。A.logn+1B.logn+1C.lognD.logn-1鏈表適用于()查找。

3、A.順序B.二分法C.順序，也能二分法D.隨機線性表若采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時，要求內(nèi)存中可用存儲單元的地址()。A.必須是連續(xù)的B.部分地址必須是連續(xù)的C.一定是不連續(xù)的D.連續(xù)或不連續(xù)都可以在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的()倍。A.1/2B.1C.2D.4數(shù)據(jù)在計算機存儲器內(nèi)表示時，物理地址與邏輯地址相同并且是連續(xù)的，稱之為()。A.存儲結(jié)構(gòu)B.邏輯結(jié)構(gòu)C.順序存儲結(jié)構(gòu)D.鏈?zhǔn)酱鎯Y(jié)構(gòu)對有n個記錄的表作快速排序，在最壞情況下，算法的時間復(fù)雜度是()。A.O(n)B.O(n2)C.O(nlog2n)D.O(n3)任何一個無向連通圖的最小生成樹()。A.只有一棵B.一棵或

4、多棵C.一定有多棵D.可能不存在已知圖的鄰接矩陣，根據(jù)算法思想，則從頂點0出發(fā)按深度優(yōu)先遍歷的結(jié)點序列是()。A.0 2 4 3 1 5 6B.0 1 3 6 5 4 2C.0 4 2 3 1 6 5D.0 3 6 1 5 4 2鏈表是一種采用()存儲結(jié)構(gòu)存儲的線性表。A.順序B.鏈?zhǔn)紺.星式D.網(wǎng)狀折半搜索與二叉搜索樹的時間性能()。A.相同B.完全不同C.有時不相同D.數(shù)量級都是O(log2n)在表長為n的鏈表中進(jìn)行線性查找，它的平均查找長度為()。A.ASL=nB.ASL=(n+1)/2C.ASL=+1D.ASLlog(n+1)-1廣度優(yōu)先遍歷類似于二叉樹的()。A.先序遍歷B.中序遍歷

5、C.后序遍歷D.層次遍歷排序方法中，從未排序序列中依次取出元素與已排序序列(初始時為空)中的元素進(jìn)行比較，將其放入已排序序列的正確位置上的方法，稱為()。A.希爾排序B.冒泡排序C.插入排序D.選擇排序數(shù)組Qn用來表示一個循環(huán)隊列，f為當(dāng)前隊列頭元素的前一位置，r為隊尾元素的位置，假定隊列中元素的個數(shù)小于n，計算隊列中元素的公式為()。A.r-fB.(n+f-r)%nC.n+r-fD.(n+r-f)%n已知一棵二叉樹的前序遍歷結(jié)果為ABCDEF，中序遍歷結(jié)果為CBAEDF，則后序遍歷的結(jié)果為()。A.CBEFDAB.FEDCBAC.CBEDFAD.不定設(shè)串s1=ABCDEFG，s2=PQRST

6、，函數(shù)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)的結(jié)果串是()。A.BCDEFB.BCDEFGC.BCPQRSTD.BCDEFEF設(shè)a1、a2、a3為3個結(jié)點，整數(shù)P0，3，4代表地址，則如下的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為()。A.循環(huán)鏈表B.單鏈表C.雙向循環(huán)鏈表D.雙向鏈表有8個結(jié)點的有向完全圖有()條邊。A.14B.28C.56D.112用鄰接表表示圖進(jìn)行深度優(yōu)先遍歷時，通常是采用()來實現(xiàn)算法的。A.棧B.隊列C.樹D.圖已知圖

7、的鄰接矩陣，根據(jù)算法，則從頂點0出發(fā)，按廣度優(yōu)先遍歷的結(jié)點序列是()。A.0 2 4 3 6 5 1B.0 1 3 6 4 2 5C.0 4 2 3 1 5 6D.0 1 3 4 2 5 6已知圖的鄰接表如下所示，根據(jù)算法，則從頂點0出發(fā)按深度優(yōu)先遍歷的結(jié)點序列是()。A.0 1 3 2B.0 2 3 1C.0 3 2 1D.0 1 2 3棧中元素的進(jìn)出原則是()。A.先進(jìn)先出B.后進(jìn)先出C.棧空則進(jìn)D.棧滿則出判定一個棧ST(最多元素為m0)為空的條件是()。A.ST-top0B.ST-top=0C.ST-topm0D.ST-top=m0一個棧的輸入序列是12345，則棧的輸出序列不可能是1

8、2345。()A.錯誤B.正確具有12個結(jié)點的完全二叉樹有5個度為2的結(jié)點。()A.錯誤B.正確二叉樹中所有結(jié)點，如果不存在非空左子樹，則不存在非空右子樹。()A.錯誤B.正確二叉樹中每個結(jié)點的兩棵子樹是有序的。()A.錯誤B.正確順序表結(jié)構(gòu)適宜于進(jìn)行順序存取，而鏈表適宜于進(jìn)行隨機存取。()A.錯誤B.正確棧和隊列是一種非線性數(shù)據(jù)結(jié)構(gòu)。()A.錯誤B.正確棧是一種對所有插入、刪除操作限于在表的一端進(jìn)行的線性表，是一種后進(jìn)先出型結(jié)構(gòu)。()A.錯誤B.正確用二叉鏈表法(link-rlink)存儲包含n個結(jié)點的二叉樹，結(jié)點的2n個指針區(qū)域中有n+1個為空指針。()A.錯誤B.正確順序存儲方式只能用于

9、存儲線性結(jié)構(gòu)。()A.錯誤B.正確鏈表的物理存儲結(jié)構(gòu)具有同鏈表一樣的順序。()A.錯誤B.正確線性表的邏輯順序與存儲順序總是一致的。()A.錯誤B.正確順序存儲方式的優(yōu)點是存儲密度大，且插入、刪除運算效率高。()A.錯誤B.正確線性表的每個結(jié)點只能是一個簡單類型，而鏈表的每個結(jié)點可以是一個復(fù)雜類型。()A.錯誤B.正確棧和隊列的存儲方式既可是順序方式，也可是鏈接方式。()A.錯誤B.正確鏈表的每個結(jié)點中都恰好包含一個指針。()A.錯誤B.正確隊是一種插入與刪除操作分別在表的兩端進(jìn)行的線性表，是一種先進(jìn)后出型結(jié)構(gòu)。()A.錯誤B.正確棧和鏈表是兩種不同的數(shù)據(jù)結(jié)構(gòu)。()A.錯誤B.正確二叉樹中每個

10、結(jié)點的關(guān)鍵字值大于其左非空子樹(若存在的話)所有結(jié)點的關(guān)鍵字值，且小于其右非空子樹(若存在的話)所有結(jié)點的關(guān)鍵字值。()A.錯誤B.正確若二叉樹用二叉鏈表作存貯結(jié)構(gòu)，則在n個結(jié)點的二叉樹鏈表中只有n-1個非空指針域。()A.錯誤B.正確鏈表的刪除算法很簡單，因為當(dāng)刪除鏈中某個結(jié)點后，計算機會自動地將后續(xù)的各個單元向前移動。()A.錯誤B.正確 參考答案：D參考答案：B參考答案：B參考答案：C參考答案：B參考答案：B參考答案：C參考答案：A參考答案：A參考答案：D參考答案：B參考答案：C參考答案：B參考答案：A參考答案：C參考答案：B參考答案：C參考答案：B參考答案：D參考答案：C參考答案：D參考答案：A參考答案：D參考答案