全國(guó)2009年10月高等教育自學(xué)考試
數(shù)據(jù)結(jié)構(gòu)試題
課程代碼：02331

一、單項(xiàng)選擇題（本大題共15小題，每小題2分，共30分）
在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其代碼填寫在題后的括號(hào)內(nèi)。錯(cuò)選、多選或未選均無(wú)分。
1．按值可否分解，數(shù)據(jù)類型通常可分為兩類，它們是（　　　）
A．靜態(tài)類型和動(dòng)態(tài)類型
B．原子類型和表類型
C．原子類型和結(jié)構(gòu)類型
D．?dāng)?shù)組類型和指針類型

2．對(duì)于三個(gè)函數(shù)f(n)=2008n³+8n²+96000，g(n)=8n³+8n+2008和h(n)=8888nlogn+3n²，下列陳述中不成立的是（　　�。�
A．f(n)是0(g(n))
B．g(n)是0(f(n))
C．h(n)是0(nlogn)
D．h(n)是0(n²)

3．指針p、q和r依次指向某循環(huán)鏈表中三個(gè)相鄰的結(jié)點(diǎn)，交換結(jié)點(diǎn)*q和結(jié)點(diǎn)*r在表中次序的程序段是（　　　）
A．p->next=r； q->next=r->next； r->next=q；
B．p->next=r； r->next=q； q->next=r->next；
C．r->next=q； q->next=r->next； p->next=r；
D．r->next=q； p->next=r； q->next=r->next；

4．若進(jìn)棧次序?yàn)閍，b，c，且進(jìn)棧和出棧可以穿插進(jìn)行，則可能出現(xiàn)的含3個(gè)元素的出棧序列個(gè)數(shù)是（　　　）
A．3
B．5
C．6
D．7

5．假設(shè)以數(shù)組A［n］存放循環(huán)隊(duì)列的元素，其頭指針front指向隊(duì)頭元素的前一個(gè)位置、尾指針rear指向隊(duì)尾元素所在的存儲(chǔ)位置，則在少用一個(gè)元素空間的前提下，隊(duì)列滿的判定條件為（　　�。�
A．rear= =front
B．(front+1)％n= =rear
C．rear+1= =front
D．(rear+1)％n= =front
6．串的操作函數(shù)str定義為：
int str(char*s) {
char *p=s；
while (*p！=′\0′)p++；
return p-s；
}
則str(″abcde″)的返回值是（　　�。�
A．3
B．4
C．5
D．6

7．二維數(shù)組A［10］［6］采用行優(yōu)先的存儲(chǔ)方法，若每個(gè)元素占4個(gè)存儲(chǔ)單元，已知元素A［3］［4］的存儲(chǔ)地址為1000，則元素A［4］［3］的存儲(chǔ)地址為（　　　）
A．1020
B．1024
C．1036
D．1240

8．對(duì)廣義表L= (a，())執(zhí)行操作tail(L)的結(jié)果是（　　　）
A．()
B．(())
C．a(chǎn)
D．(a)

9．已知二叉樹的中序序列和后序序列均為ABCDEF，則該二叉樹的先序序列為（　　�。�
A．FEDCBA
B．ABCDEF
C．FDECBA
D．FBDCEA

10．已知森林F={T₁，T₂，T₃，T₄，T₅}，各棵樹Ti(i=1，2，3，4，5)中所含結(jié)點(diǎn)的個(gè)數(shù)分別為7，3，5，l，2，則與F對(duì)應(yīng)的二叉樹的右子樹中的結(jié)點(diǎn)個(gè)數(shù)為（　　�。�
A．2
B．3
C．8
D．11

11．若非連通無(wú)向圖G含有21條邊，則G的頂點(diǎn)個(gè)數(shù)至少為（　　　）

A．7
B．8
C．21
D．22

12．如圖所示的有向圖的拓?fù)湫蛄惺牵ā　　。?
A．c，d，b，a，e
B．c，a，d，b，e
C．c，d，e，a，b
D．c，a，b，d，e

13．對(duì)關(guān)鍵字序列(6，1，4，3，7，2，8，5)進(jìn)行快速排序時(shí)，以第1個(gè)元素為基準(zhǔn)的一次劃分的結(jié)果為（　　　）
A．(5，1，4，3，6，2，8，7)
B．(5，1，4，3，2，6，7，8)
C．(5，1，4，3，2，6，8，7)
D．(8，7，6，5，4，3，2，1)

14．分塊查找方法將表分為多塊，并要求（　　　）
A．塊內(nèi)有序
B．塊間有序
C．各塊等長(zhǎng)
D．鏈?zhǔn)酱鎯?chǔ)

15．便于進(jìn)行布爾查詢的文件組織方式是（　　�。�
A．順序文件
B．索引文件
C．散列文件
D．多關(guān)鍵字文件