南開20秋《數(shù)據(jù)結(jié)構(gòu)》（1709、1803、1809、1903、1909、2003、2009）在線作業(yè)

1、南開20秋數(shù)據(jù)結(jié)構(gòu)（1709、1803、1809、1903、1909、2003、2009）在線作業(yè)對有n個記錄的表作快速排序，在最壞情況下，算法的時間復(fù)雜度是()A.O(n)B.O(n2)C.O(nlog2n)D.O(n3)引入二叉線索樹的目的是()A.加快查找結(jié)點的前驅(qū)或后繼的速度B.為了能在二叉樹中方便的進行插入與刪除C.為了能方便的找到雙親D.使二叉樹的遍歷結(jié)果唯一在一個圖中，所有頂點的度數(shù)之和等于圖的邊數(shù)的()倍A.1/2B.1C.2D.4已知圖的鄰接矩陣，根據(jù)算法，則從頂點0出發(fā)，按廣度優(yōu)先遍歷的結(jié)點序列是()A.0 2 4 3 1 6 5B.0 1 3 5 6 4 2C.0 1 2

2、 3 4 6 5D.0 1 2 3 4 5 6在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的()倍。A.1/2B.1C.2D.4判定一個棧ST(最多元素為m0)為空的條件是()A.ST->top0B.ST->top=0C.ST->topm0D.ST->top=m0若已知一個棧的入棧序列是1，2，3，n，其輸出序列為p1，p2，p3，pn，若p1=n，則pi為()A.iB.n=iC.n-i+1D.不確定在表長為n的鏈表中進行線性查找，它的平均查找長度為()A.ASL=nB.ASL=(n+1)/2C.ASL=n+1D.ASLlog2（n+1）-1已知圖的鄰接矩陣

3、，根據(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一個向量第一個元素的存儲地址是100，每個元素的長度為2，則第5個元素的地址是()A.110B.108C.100D.120數(shù)組Qn用來表示一個循環(huán)隊列，f為當前隊列頭元素的前一位置，r為隊尾元素的位置，假定隊列中元素的個數(shù)小于n，計算隊列中元素的公式為()A.r-fB.(n+f-r)% nC.n+r-fD.(n+r-f)% n已知圖的鄰接矩陣，根據(jù)算法思想，則從頂點0出發(fā)按深度優(yōu)先遍歷的結(jié)點序列是()A.0 2 4 3

4、 1 5 6B.0 1 3 6 5 4 2C.0 4 2 3 1 6 5D.0 3 6 1 5 4 2設(shè)有兩個串p和q，求q在p中首次出現(xiàn)的位置的運算稱作()A.連接B.模式匹配C.求子串D.求串長已知圖的鄰接表如下所示，根據(jù)算法，則從頂點0出發(fā)按深度優(yōu)先遍歷的結(jié)點序列是()A.0 1 3 2B.0 2 3 1C.0 3 2 1D.0 1 2 3鏈表是一種采用()存儲結(jié)構(gòu)存儲的線性表A.順序B.鏈式C.星式D.網(wǎng)狀判定一個隊列QU(最多元素為m0)為滿隊列的條件是()A.QU->rear-QU->front=m0B.QU->rear-QU->front-1=m0C.QU

5、->front=QU->rearD.QU->front=QU->rear+1不含任何結(jié)點的空樹()A.是一棵樹B.是一棵二叉樹C.是一棵樹也是一棵二叉樹D.既不是樹也不是二叉樹快速排序在下列哪種情況下最易發(fā)揮其長處()A.被排序的數(shù)據(jù)中含有多個相同排序碼B.被排序的數(shù)據(jù)已基本有序C.被排序的數(shù)據(jù)完全無序D.被排序的數(shù)據(jù)中的最大值和最小值相差懸殊在n個結(jié)點的順序表中，算法的時間復(fù)雜度是O(1)的操作是()A.訪問第i個結(jié)點(1in)和求第i個結(jié)點的直接前驅(qū)(2in)B.在第i個結(jié)點后插入一個新結(jié)點(1in)C.刪除第i個結(jié)點(1in)D.將n個結(jié)點從小到大排序設(shè)串s1=A

6、BCDEFG，s2=PQRST，函數(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已知圖的鄰接表如下所示，根據(jù)算法，則從頂點0出發(fā)按廣度優(yōu)先遍歷的結(jié)點序列是()A.0 3 2 1B.0 1 2 3C.0 1 3 2D.0 3 1 2用鄰接表表示圖進行深度優(yōu)先遍歷時，通常是采用()來實現(xiàn)算法的A.棧B.隊列C.樹D.圖向一個有127個元素

7、的順序表中插入一個新元素并保持原來順序不變，平均要移動()個元素A.8B.63.5C.63D.7數(shù)據(jù)在計算機存儲器內(nèi)表示時，物理地址與邏輯地址相同并且是連續(xù)的，稱之為()A.存儲結(jié)構(gòu)B.邏輯結(jié)構(gòu)C.順序存儲結(jié)構(gòu)D.鏈式存儲結(jié)構(gòu)深度優(yōu)先遍歷類似于二叉樹的()A.先序遍歷B.中序遍歷C.后序遍歷D.層次遍歷下列關(guān)鍵字序列中，()是堆A.16，72，31，23，94，53B.94，23，31，72，16，53C.16，53，23，94，31，72D.16，23，53，31，94，72已知圖的鄰接矩陣，根據(jù)算法，則從頂點0出發(fā)，按廣度優(yōu)先遍歷的結(jié)點序列是()A.0 2 4 3 6 5 1B.0 1 3

8、 6 4 2 5C.0 4 2 3 1 5 6D.0 1 3 4 2 5 6一棵具有n個結(jié)點的完全二叉樹的樹高度(深度)是()A.logn+1B.logn+1C.lognD.logn-1二叉樹是非線性數(shù)據(jù)結(jié)構(gòu)，所以()A.它不能用順序存儲結(jié)構(gòu)存儲B.它不能用鏈式存儲結(jié)構(gòu)存儲C.順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)都能存儲D.順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)都不能使用具有n(n>0)個結(jié)點的完全二叉樹的深度為()A.log2(n)B.log2(n)C.log2(n)+1D.log2(n)+1二叉樹中每個結(jié)點的關(guān)鍵字值大于其左非空子樹(若存在的話)所有結(jié)點的關(guān)鍵字值，且小于其右非空子樹(若存在的話)所有結(jié)點

9、的關(guān)鍵字值。()A.正確B.錯誤線性表的每個結(jié)點只能是一個簡單類型，而鏈表的每個結(jié)點可以是一個復(fù)雜類型。()A.正確B.錯誤順序表結(jié)構(gòu)適宜于進行順序存取，而鏈表適宜于進行隨機存取。()A.正確B.錯誤隊是一種插入與刪除操作分別在表的兩端進行的線性表，是一種先進后出型結(jié)構(gòu)。()A.正確B.錯誤兩個棧共享一片連續(xù)內(nèi)存空間時，為提高內(nèi)存利用率，減少溢出機會，應(yīng)把兩個棧的棧底分別設(shè)在這片內(nèi)存空間的兩端。()A.正確B.錯誤順序存儲方式只能用于存儲線性結(jié)構(gòu)。()A.正確B.錯誤鏈表的刪除算法很簡單，因為當刪除鏈中某個結(jié)點后，計算機會自動地將后續(xù)的各個單元向前移動。()A.正確B.錯誤線性表的邏輯順序與存

10、儲順序總是一致的。()A.正確B.錯誤線性表在物理存儲空間中也一定是連續(xù)的。()A.正確B.錯誤對于一棵非空二叉樹，它的根結(jié)點作為第一層，則它的第i層上最多能有2i1個結(jié)點。()A.正確B.錯誤棧和隊列的存儲方式既可是順序方式，也可是鏈接方式。()A.正確B.錯誤對于不同的使用者，一個表結(jié)構(gòu)既可以是棧，也可以是隊列，也可以是線性表。()A.正確B.錯誤棧是一種對所有插入、刪除操作限于在表的一端進行的線性表，是一種后進先出型結(jié)構(gòu)。()A.正確B.錯誤二叉樹中每個結(jié)點有兩棵非空子樹或有兩棵空子樹。()A.正確B.錯誤二叉樹中每個結(jié)點的兩棵子樹是有序的。()A.正確B.錯誤鏈表的每個結(jié)點中都恰好包含一個指針。()A.正確B.錯誤二叉樹中每個結(jié)點的兩棵子樹的高度差等于1。()A.正確B.錯誤棧和鏈表是兩種不同的數(shù)據(jù)結(jié)構(gòu)。()A.正確B.錯誤二叉樹中所有結(jié)點，如果不存在非空左子樹，則不存在非空右子樹。()A.正確B.錯誤二叉樹中所有結(jié)點個數(shù)是2k-1-1，其中k是樹的深度。()A.正確B.錯誤 參考答案：B參考答案：A參考答案：C參考答案：C參考答案：B參考答案：B參考答案：C參考答案：B參考答案：D參考答案：B參考答案：D參考答案：C參考答案：B參考答案：D參考答案：B參考答案：A參考答案：C參考答案：C參考答案：A參考答案：D參考答案：A參考