《數(shù)據(jù)結(jié)構(gòu)》2020年春季學(xué)期在線作業(yè)（一）
試卷總分:100 得分:100
第1題,設(shè)A是n*n的對稱矩陣，將A的對角線及對角線上方的元素以列為主的次序存放在一維數(shù)組B[1..n(n+1)/2]中，對上述任一元素aij(1≤i，j≤n，且i≤j)在B中的位置為（ ）。
A、i(i-l)/2+j
B、j(j-l)/2+i
C、j(j-l)/2+i-1
D、i(i-l)/2+j-1
正確答案:
第2題,有六個(gè)元素6，5，4，3，2，1 的順序進(jìn)棧，問下列哪一個(gè)不是合法的出棧序列？（ ）。
A、5 4 3 6 1 2
B、4 5 3 1 2 6
C、3 4 6 5 2 1
D、2 3 4 1 5 6
正確答案:
第3題,關(guān)鍵路徑是事件結(jié)點(diǎn)網(wǎng)絡(luò)中（ ）。
A、從源點(diǎn)到匯點(diǎn)的最長路徑
B、從源點(diǎn)到匯點(diǎn)的最短路徑
C、最長回路
D、最短回路
正確答案:
第4題,在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成（ ）。
A、動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)
B、緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)
C、線性結(jié)構(gòu)和非線性結(jié)構(gòu)
D、內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)
正確答案:
第5題,樹最適合用來表示（ ）。
A、有序數(shù)據(jù)元素
B、無序數(shù)據(jù)元素
C、元素之間具有分支層次關(guān)系的數(shù)據(jù)
D、元素之間無聯(lián)系的數(shù)據(jù)
正確答案:
第6題,已知廣義表: A=(a,b), B=(A,A), C=(a,(b,A),B), 求下列運(yùn)算的結(jié)果:tail(head(tail(C))) = （ ）。
A、（a）
B、A
C、(b)
D、(A)
正確答案:
第7題,下面關(guān)于線性表的敘述中，錯(cuò)誤的是哪一個(gè)？（ ）。
A、線性表采用順序存儲，必須占用一片連續(xù)的存儲單元。
B、線性表采用順序存儲，便于進(jìn)行插入和刪除操作。
C、線性表采用鏈接存儲，不必占用一片連續(xù)的存儲單元。
D、線性表采用鏈接存儲，便于插入和刪除操作。
正確答案:
第8題,題目和答案如下圖所示：
A、A
B、B
C、C
D、D
正確答案:
第9題,采用BF算法在主串a(chǎn) a b a a a c a a c b b b中查找子串a(chǎn) a a c a a c b的查找次數(shù)為（ ）。
A、13
B、14
C、15
D、16
正確答案:
第10題,n個(gè)頂點(diǎn)的有向完全圖中含有有向邊的數(shù)目最多為（ ）。
A、n-1
B、n
C、n(n-1)/2
D、n(n-1)
正確答案:
第11題,在有序表中使用折半查找法的平均時(shí)間是（ ）。
A、O(1)
B、O(n)
C、O(log2n)
D、O(n2)
正確答案:
第12題,下列判斷正確的是（ ）。
A、二叉樹是樹的特例。
B、具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為n/2。
C、Huffman樹是帶權(quán)路徑長度最小的二叉樹，樹中權(quán)值越大的葉子結(jié)點(diǎn)距離根結(jié)點(diǎn)越遠(yuǎn)。
D、棧和隊(duì)列都是限制存取點(diǎn)的線性結(jié)構(gòu)。
正確答案:
第13題,若某線性表中最常用的操作是取第i個(gè)元素和找第i個(gè)元素的前趨元素，則采用（ ）存儲方式最節(jié)省時(shí)間。
A、順序表
B、單鏈表
C、雙鏈表
D、單循環(huán)鏈表
正確答案:
第14題,一個(gè)含n個(gè)頂點(diǎn)和e條弧的有向圖以鄰接矩陣表示法為存儲結(jié)構(gòu)，則計(jì)算該有向圖中某個(gè)頂點(diǎn)出度的時(shí)間復(fù)雜度為（ ）。
A、O(n)
B、O(e)
C、O(n+e)
D、O(n2)
正確答案:
第15題,已知廣義表LS=((a,b,c),(d,e,f)),運(yùn)用head和tail函數(shù)取出LS中元素e的運(yùn)算是（ ）。
A、head(tail(LS))
B、tail(head(LS))
C、head(tail(head(tail(LS))))
D、head(tail(tail(head(LS))))
正確答案:
第16題,設(shè)有一個(gè)無向圖G=（V，E）和G’=（V’，E’）如果G’為G的生成樹，則下面不正確的說法是（ ）。
A、G’為G 的子圖
B、G’為G 的連通分量
C、G’為G的極小連通子圖且V’=V
D、G’為G的一個(gè)無環(huán)子圖
正確答案:
第17題,最大容量為n的循環(huán)隊(duì)列，隊(duì)尾指針是rear，隊(duì)頭是front，則隊(duì)空的條件是（ ）。
A、(rear+1) % n = front
B、rear = front
C、rear+1 = front
D、(rear-l) % n = front
正確答案:
第18題,下面關(guān)于圖的存儲的敘述中正確的是（ ）。
A、用相鄰矩陣法存儲圖，占用的存儲空間大小只與圖中結(jié)點(diǎn)個(gè)數(shù)有關(guān)，而與邊數(shù)無關(guān)
B、用相鄰矩陣法存儲圖，占用的存儲空間大小只與圖中邊數(shù)有關(guān)，而與結(jié)點(diǎn)個(gè)數(shù)無關(guān)
C、用鄰接表法存儲圖，占用的存儲空間大小只與圖中結(jié)點(diǎn)個(gè)數(shù)有關(guān)，而與邊數(shù)無關(guān)
D、用鄰接表法存儲圖，占用的存儲空間大小只與圖中邊數(shù)有關(guān)，而與結(jié)點(diǎn)個(gè)數(shù)無關(guān)
正確答案:
第19題,若串S=“software”,其子串?dāng)?shù)目是（ ）。
A、8
B、37
C、36
D、9
正確答案:
第20題,假設(shè)主串的長度為m，模式串的長度為n，BF算法在一般和最壞情況下的時(shí)間復(fù)雜性分別為 （ ），所以還是一個(gè)常用算法。由于有回溯，所以主串輸入后必須保存。
A、n+m n*m
B、n m
C、n*m n+m
D、m n
正確答案:
