《數(shù)據(jù)結(jié)構(gòu)》2020年春季學(xué)期在線作業(yè)（二）
試卷總分:100 得分:100
第1題,在線性表的順序存儲(chǔ)結(jié)構(gòu)中，邏輯上相鄰的數(shù)據(jù)元素的物理位置（ ），在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，邏輯上相鄰的數(shù)據(jù)元素的物理位置（ ）。
A、必相鄰 必相鄰
B、必相鄰 不一定相鄰
C、不一定相鄰 必相鄰
D、不一定相鄰 不一定相鄰
正確答案:
第2題,若線性表最常用的操作是存取第i個(gè)元素及其前驅(qū)的值，則采用（ ）存儲(chǔ)方式節(jié)省時(shí)間。
A、單鏈表
B、雙鏈表
C、單循環(huán)鏈表
D、順序表
正確答案:
第3題,已知廣義表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))))
正確答案:
第4題,設(shè)有兩個(gè)串T和P，求P在T中首次出現(xiàn)的位置的串運(yùn)算稱作（ ）。
A、聯(lián)接
B、求子串
C、字符定位
D、子串定位
正確答案:
第5題,下列說(shuō)法正確的是 （ ）。
A、樹的先根遍歷序列與其對(duì)應(yīng)的二叉樹的先根遍歷序列相同
B、樹的先根遍歷序列與其對(duì)應(yīng)的二叉樹的后根遍歷序列相同
C、樹的后根遍歷序列與其對(duì)應(yīng)的二叉樹的先根遍歷序列相同
D、樹的后根遍歷序列與其對(duì)應(yīng)的二叉樹的后根遍歷序列相同
正確答案:
第6題,在二叉樹的先序遍歷，中序遍歷和后序遍歷算法中，所有葉子結(jié)點(diǎn)的先后順序（ ）。
A、都不相同
B、完全相同
C、前序遍歷和中序遍歷相同，而與后序遍歷不同
D、前序遍歷和后序遍歷相同，而與中序遍歷不同
正確答案:
第7題,若串S=“software”,其子串?dāng)?shù)目是（ ）。
A、8
B、37
C、36
D、9
正確答案:
第8題,以下判斷不正確的是（ ）。
A、順序存儲(chǔ)的線性表可隨機(jī)存取。
B、同一線性表中的數(shù)據(jù)元素應(yīng)具有相同的特性。
C、順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大，插入、刪除操效率高。
D、在線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，邏輯上相鄰的數(shù)據(jù)元素在物理位置上不一定相鄰。
正確答案:
第9題,假設(shè)主串的長(zhǎng)度為m，模式串的長(zhǎng)度為n，KMP算法的時(shí)間復(fù)雜度為（ ）。
A、n+m
B、n*m
C、n
D、m
正確答案:
第10題,在順序存儲(chǔ)（空間大小為m）的循環(huán)隊(duì)列q中，下列判滿正確的是（ ）。
A、q.front % m = 0 ;
B、q.rear % m = 0 ;
C、q.front = q.rear ;
D、(q.front+1) % m = q.rear;
正確答案:
第11題,線性結(jié)構(gòu)中的一個(gè)結(jié)點(diǎn)代表一個(gè)（ ）。
A、數(shù)據(jù)元素
B、數(shù)據(jù)項(xiàng)
C、數(shù)據(jù)
D、數(shù)據(jù)結(jié)構(gòu)
正確答案:
第12題,設(shè)深度為K的二叉樹上只有度為0和度為2的結(jié)點(diǎn)，則這類二叉樹上所含的結(jié)點(diǎn)總數(shù)為（ ）。
A、K+1
B、2K
C、2K-1
D、2K+1
正確答案:
第13題,題目和答案如下圖所示：
A、A
B、B
C、C
D、D
正確答案:
第14題,下列說(shuō)法不正確的是（ ）。
A、圖的遍歷是從給定的源點(diǎn)出發(fā)每一個(gè)頂點(diǎn)僅被訪問(wèn)一次
B、圖的深度遍歷不適用于有向圖
C、遍歷的基本算法有兩種：深度遍歷和廣度遍歷
D、圖的深度遍歷是一個(gè)遞歸過(guò)程
正確答案:
第15題,進(jìn)行二分查找要求查找表必須（ ）。
A、以順序方式存儲(chǔ)。
B、以鏈?zhǔn)椒绞酱鎯?chǔ)。
C、以順序方式存儲(chǔ)且數(shù)據(jù)元素按關(guān)鍵字有序排列。
D、以鏈?zhǔn)椒绞酱鎯?chǔ)且數(shù)據(jù)元素按關(guān)鍵字有序排列。
正確答案:
第16題,哈希查找中k個(gè)關(guān)鍵字具有同一哈希值，若用線性探測(cè)法將這k個(gè)關(guān)鍵字對(duì)應(yīng)的記錄存入哈希表中，至少要進(jìn)行（ ）次探測(cè)。
A、k
B、k-1
C、k(k-1)/2
D、1+k(k-1)/2
正確答案:
第17題,下面關(guān)于完全二叉樹的特點(diǎn)敘述不正確的是（ ）。
A、只有最后一層是不滿的，不滿層的結(jié)點(diǎn)首先出現(xiàn)在左邊
B、至多只有最下面的兩層結(jié)點(diǎn)的度小于2
C、左子樹的高度不會(huì)小于右子樹的高度，且左、右子樹高度最大相差±1
D、葉子只能出現(xiàn)在最后兩層上；
正確答案:
第18題,若在線性表中采用折半查找法查找元素，該線性表應(yīng)該（ ）。
A、元素按值有序
B、采用順序存儲(chǔ)結(jié)構(gòu)
C、元素按值有序，且采用順序存儲(chǔ)結(jié)構(gòu)
D、元素按值有序，且采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
正確答案:
第19題,采用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
正確答案:
第20題,對(duì)廣義表L=((a,b),c,d)進(jìn)行操作tail(head(L))的結(jié)果是（ ）。
A、(c,d )
B、(d )
C、b
D、(b)
正確答案:
