22春季東北大學(xué)《數(shù)據(jù)結(jié)構(gòu)Ⅱ》在線平時(shí)作業(yè)3

【奧鵬】數(shù)據(jù)結(jié)構(gòu)11-[東北大學(xué)]《數(shù)據(jù)結(jié)構(gòu)II》在線平時(shí)作業(yè)3

試卷總分：100得分：100

第1題,一個(gè)含n個(gè)頂點(diǎn)和e條弧的有向圖以鄰接矩陣表示法為存儲結(jié)構(gòu)，則計(jì)算該有向圖中

某個(gè)頂點(diǎn)出度的時(shí)間復(fù)雜度為

A、0(D)

B、0(e)

C、0(n+e)

D、0(n2)

正確答案:A

第2題,索引非順序文件的特點(diǎn)是

A、主文件無序,索引表有序

B、主文件有序,索引表無序

C、主文件有序,索引表有序

D、主文件無序,索引表無序

正確答案:A

第3題，二維數(shù)組A按行優(yōu)先順序存儲，其中每個(gè)元素占1個(gè)存儲單元。若A[1][1]的存

儲地址為420,A[3][3]的存儲地址為446,則A[5][5]的存儲地址為

A、470

B、471

C、472

D、473

正確答案:C

第4題,在單鏈表中，指針-p指向元素為x的結(jié)點(diǎn)，實(shí)現(xiàn)“刪除x的后繼”的語句是

A、p=p-next;

B、p-next=p-next-next;

C、p-next=p;

D、p=p-next-next;

正確答案:B

第5題，引入二叉線索樹的目的是

A、加快查找結(jié)點(diǎn)的前驅(qū)或后繼的速度

B、為了能在二叉樹中方便的進(jìn)行插入與刪除

C、為了能方便的找到雙親

D、使二叉樹的遍歷結(jié)果唯一

正確答案:A

第6題,一棵樹高為K的完全二叉樹至少的結(jié)點(diǎn)是

A、2k-1

B、2k-l-1

C、2k-l

D、2k

正確答案:C

第7題,下列查找算法中，平均查找長度與元素個(gè)數(shù)n不直接相關(guān)的查找方法是

A、分塊查找

B、順序查找

C、二分查找

D、散列查找

正確答案:D

第8題,某二叉樹中序序列為A,B,C,D,E,F,G,后序序列為B,D,C,A,F,G,E則該二叉樹對應(yīng)的

森林包括的樹的棵樹是

A、1

B、2

C、3

D、4

正確答案:B

第9題，已知循環(huán)隊(duì)列的存儲空間為數(shù)組data[21],且當(dāng)前隊(duì)列的頭指針和尾指針的值分別

為8和3,則該隊(duì)列的當(dāng)前長度為

A、5

B、6

C、16

D、17

正確答案:C

第10題，在長度為n的順序表中刪除第i個(gè)元素（lWiWn）時(shí)，元素移動的次數(shù)為

A、n-i+1

B、i

C、i+1

D、n-i

正確答案:D

第11題,從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為兩大類，即

A、動態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu)

B、順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu)

C、線性結(jié)構(gòu)、非線性結(jié)構(gòu)

D、初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu)

正確答案:C

第12題,如果求一個(gè)連通圖中以某個(gè)頂點(diǎn)為根的高度最小的生成樹，應(yīng)采用

A、深度優(yōu)先搜索算法

B、廣度優(yōu)先搜索算法

C、求最小生成樹的prim算法

D、拓?fù)渑判蛩惴?/p>

正確答案:B

第13題,為便于判別有向圖中是否存在回路，可借助于

A、廣度優(yōu)先搜索算法

B、最小生成樹算法

C、最短路徑算法

D、拓?fù)渑判蛩惴?/p>

正確答案:D

第14題，隊(duì)列和棧的主要區(qū)別是

A、邏輯結(jié)構(gòu)不同

B、存儲結(jié)構(gòu)不同

C、所包含的運(yùn)算個(gè)數(shù)不同

D、限定插入和刪除的位置不同

正確答案：D

第15題，在頭指針為head且表長大于1的單循環(huán)鏈表中，指針p指向表中某個(gè)結(jié)點(diǎn)，若

p-next-next=head,貝ij

A、p指向頭結(jié)點(diǎn)

B、p指向尾結(jié)點(diǎn)

C、p的直接后繼是頭結(jié)點(diǎn)

D、P的直接后繼是尾結(jié)點(diǎn)

正確答案:D

第16題，若將數(shù)據(jù)結(jié)構(gòu)形式定義為二元組(K,R),其中K是數(shù)據(jù)元素的有限集合，則R是K

上

A、操作的有限集合

B、映象的有限集合

C、類型的有限集合

D、關(guān)系的有限集合

正確答案:D

第17題,通常將鏈串的結(jié)點(diǎn)大小設(shè)置為大于1是為了

A、提高串匹配效率

B、提高存儲密度

C、便于插入操作

D、便于刪除操作

正確答案:B

第18題,對長度為n的關(guān)鍵字序列進(jìn)行堆排序的空間復(fù)雜度為

A、0(log2n)

B、0(1)

C、0(n)

D、0(n*log2n)

正確答案:B

第19題，在一個(gè)帶權(quán)連通圖G中，權(quán)值最小的邊一定包含在G的

A、最小生成樹中

B、深度優(yōu)先生成樹中

C、廣度優(yōu)先生成樹中

D、深度優(yōu)先生成森林中

正確答案:A

第20題，假設(shè)以數(shù)組A[m]存放循環(huán)隊(duì)列的元素。已知隊(duì)列的長度為length,指針rear指向