《資料結構與演算法》2015-2016學年第1學期考試複習題
該版糾錯題有:7,16,22
一、 選擇題(下面各小題有乙個正確答案,請將正確答案的編號填寫在各小題的括號內)。
1、在一棵具有5層的滿二叉樹中結點總數為( a )。
a) 31b)32
c)33d)16
2、串的邏輯結構與( d )的邏輯結構不相同。
a)線性表b)棧
c)佇列d)集合
3、下列序列中,執行第一趟快速排序後得到的序列是( a )。
a)[d,a,e,d,b]f[h,g] b) [c,e,a,d]f[h,g,b]
c) [g,a,e,c,b]f[d,h] d) [a,b,c,d,]f[e,g,h]
4、n個頂點的強連通圖至少有( a )條邊。
a)n b)n+1 c)n-1 d)n(n-1)
5、資料結構中,在邏輯上可以把資料結構分成( b )。
a)動態結構和靜態結構
b)線性結構和非線性結構
c)緊湊結構和非緊湊結構
d)內部結構和外部結構
6、鏈式儲存的儲存結構所佔儲存空間( a )。
a)分兩部分,一部分存放結點值,另一部分存放表示結點間關係的指標
b)只有一部分,存放結點值
c)只有一部分,儲存表示結點間關係的指標
d)分兩部分,一部分存放結點值,另一部分存放結點所佔單元數
7、有乙個有序表。當用二分查詢法查詢鍵值為84的結點時,經( a )比較後查詢成功。
a) 4b)3c)2d)12
8、設單鏈表中指標p指向結點m,若要刪除m之後的結點(若存在),則需修改指標的操作為( a )。
a)p->next=p->next->nextb) p=p->next;
c)p=p->next->next; d) p->next=p;
9、n個頂點,e條邊的有向圖的鄰接矩陣中非零元素有( c )個。
a)nb)2ec)e d) n+e
10、對下圖v4的度為( c )。
a)1 b)2 c)3 d)4
v1 v2v3
v411、在一棵度為3的樹中,度為3的結點個數為2,度為2的結點個數為1,則度為0的結點個數為( c )。
a)4b)5
c)6d)7
12、在資料結構中,從邏輯上可以把資料結構分為( c )。
a)動態結構和靜態結構 b)緊湊結構和非緊湊結構
c)線性結構和非線性結構 d)內部結構和外部結構
13、用一維陣列a進行順序儲存時,若起始位址為loc(a1),元素長度為c,則a的第i個陣列單元在存放位址loc(ai),等於( b )。
a)loc(a1)+i*c b)loc(a1)+(i-1)*c
c)loc(a1)+i*c+1 d)loc(a1)+(i+1)*c
14、( c )在進行插入操作時,常產生假溢位現象。
a)順序棧b)迴圈佇列
c)順序佇列d)鏈佇列
15、某線性表中最常用的操作是在最後乙個元素之後插入乙個元素和刪除第乙個元素,則採用( d )儲存方式最節省運算時間。
a) 單鏈表b) 僅有頭指標的單迴圈鍊錶
c) 雙鏈表d) 僅有尾指標的單迴圈鍊錶
16、向乙個棧頂指標為hs的鏈棧中插入乙個s結點時,應執行( c )。
a) hs->next=sb) s->next=hs->next; hs->next=s;
c) s->next=hs; hs=sd) s->next=hs;hs=hs->next;
17、在乙個鏈佇列中,假定front和rear分別為隊首和隊尾指標,則刪除乙個結點的操作為( b )。
a) rear=rear->nextb) front=front->next;
c) rear=front->nextd) front=rear->next;
18、已知棧的最大容量為4。若進棧序列為1,2,3,4,5,6,且進棧和出棧可以穿插進行,則可能出現的出棧序列為( c )。
a) 5,4,3,2,1,6b) 2,3,5,6,1,4
c) 3,2,5,4,1,6d) 1,4,6,5,2,3
19、已知廣義表l=((x,y,z),a,(u,t,w)),從l 表中取出原子項t 的操作是( d )。
a) head(head(tail(tail(l
b) tail(head(head(tail(l))))
c) head(tail(head(tail(l
d)head(tail(head(tail(tail(l)))))
20、下列各種資料結構中屬於線性結構的有( a )。
a)棧b) 二叉樹
c) 廣義表d) 圖
21、倘若在對串的插入、刪除運算中,期望運算速度最快,則應採用( c )。
a)順序表示法b)單字元為結點的單鏈表表示法
c)等量分塊表示法 d)不等量分塊表示法
22、廣義表head(((a,b),(c,d)))的運算結果為( d )。
a)(a,bb)(c,d)
c)空表d)((a,b),(c,d))
23、 n個頂點的圖的最小生成樹必定( d ),是不正確的描述。
a)不唯一b)權的總和唯一
c)不含迴路d)有n條邊
24、採用鏈結構儲存線性表時,其位址( b )。
a)必須是連續的b)連續不連續都可以
c)部分位址必須是連續 d)必須是不連續的
25、佇列的操作的原則是( a )。
a)先進先出b) 後進先出
c) 只能進行插入d) 只能進行刪除
26、以下屬於順序儲存結構優點的是( a )。
a) 儲存密度大 b) 插入運算方便
c)刪除運算方便 d)可方便地用於各種邏輯結構的儲存表示
27、資料結構研究的內容是( d )。
a)資料的邏輯結構b)資料的儲存結構
c)建立在相應邏輯結構和儲存結構上的演算法 d)包括以上三個方面
28、在乙個單鏈表中,已知q結點是p結點的前趨結點,若在q和p之間插入s結點,則須執行( a )。
a)q->next=s;s->next=p;b)s->next=p->next;p->next=s;
c)p->next=s->next;s->next=p d)p->next=s;s->next=q;
29、若某線性表最常用的操作是訪問任一指定序號的元素和在最後進行插入和刪除運算,則利用( d )儲存方式最節省時間。
a)順序表 b)雙鏈表 c)帶頭結點的雙迴圈鍊錶 d)單迴圈鍊錶
30、下面關於線性表的敘述中,錯誤的是哪乙個?( d )
a)線性表採用順序儲存,必須占用一片連續的儲存單元。
b)線性表採用鏈結儲存,便於插入和刪除操作。
c)線性表採用鏈結儲存,不必占用一片連續的儲存單元。
d)線性表採用順序儲存,便於進行插入和刪除操作。
31、在乙個具有n個單元的順序棧中,假定以位址低端(即0單元)作為棧底,以top作為棧頂指標,當做出棧處理時,top變化為( c )。
a)top不變 b)top=0 c)top-- d)top++
32、在乙個鏈佇列中,假定front和rear分別為隊首和隊尾指標,則插入乙個結點的操作為( b )。
a)front=front->nextb) rear=rear->next;
c) rear=front->next; d) front=rear->next;
33、設有乙個棧,元素的進棧次序為a,b,c,d,e,下列是不可能的出棧序列是( c )。
a) a,b,c,d,e
b) b,c,d,e,a
c) e,a,b,c,d
d) e,d,c,b,a
34、廣義表a=(a,b,(c,d),(e,(f,g))),則head(tail(head(tail(tail(a)))))=( d )。
a) (gb) (dc) c d) d
35、設給定問題的規模為變數n,解決該問題的演算法所需時間為tn=o(f(n)),tn表示式中記號o表示( a )。
a)乙個數量級別 b)乙個平均值
c)乙個最大值d)乙個均方值
36、線性表的鏈結實現有利於( a )運算。
資料結構試題及答案
資料結構試卷 一 一 單選題 每題 2 分,共20分 1.棧和佇列的共同特點是 a a.只允許在端點處插入和刪除元素 b.都是先進後出 c.都是先進先出 d.沒有共同點 2.用鏈結方式儲存的佇列,在進行插入運算時 d a.僅修改頭指標b.頭 尾指標都要修改 c.僅修改尾指標d.頭 尾指標可能都要修改...
資料結構試題及答案
2 二維陣列是陣列元素為一維陣列的線性表,因此它是線性結構。3 順序錶用一維陣列作為儲存結構,因此順序表是一維陣列。4 通常使用兩個類來協同表示單鏈表,即鍊錶的結點類和鍊錶類。5 棧和佇列都是順序訪問的的線性表,但它們對訪問位置的限制不同。6 在使用字尾表表示實現計算器時用到乙個棧的例項,其作用是暫...
資料結構試題及答案
資料結構 自考複習思考試題 一 單選題 從選擇的答案中選出正確的答案,將其字母編號填入下列敘述中的括號內。每小題 3分,共24分 1 向乙個有127個元素原順序表中插入乙個新元素並儲存原來順序不變,平均要移動 個元素。a 8 b 63.5 c 63 d 7 2 設有乙個二維數a m n 假設a 0 ...