全國2010年1月高等教育自學(xué)考試

　　數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題

　　課程代碼：02142

　　一、單項(xiàng)選擇題(本大題共15小題，每小題2分，共30分)

　　在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其代碼填寫在題后的括號(hào)內(nèi)。錯(cuò)選、多選或未選均無分。

　　1.下述文件中適合于磁帶存儲(chǔ)的是( )

　　A.順序文件 B.索引文件

　　C.散列文件 D.多關(guān)鍵字文件

　　2.某二叉樹的后根遍歷序列為dabec，中根遍歷序列為debac，則先根遍歷序列為( )

　　A.acbed B.becab

　　C.deabc D.cedba

　　3.含有n個(gè)結(jié)點(diǎn)的二叉樹用二叉鏈表表示時(shí)，空指針域個(gè)數(shù)為( )

　　A.n-1 B.n

　　C.n+1 D.n+2

　　4.在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和與圖的邊數(shù)的比是( )

　　A.1∶2 B.1∶1

　　C.2∶1 D.4∶1

　　5.長度為n的鏈隊(duì)列用單循環(huán)鏈表表示，若只設(shè)頭指針，則出隊(duì)操作的時(shí)間復(fù)雜度為( )

　　A.O(1) B.O(1og2n)

　　C.O(n) D.O(n2)

　　6.下述幾種排序方法中，要求內(nèi)存量最大的是( )

　　A.插入排序 B.快速排序

　　C.歸并排序 D.選擇排序

　　7.對(duì)n個(gè)不同值進(jìn)行冒泡排序，在元素?zé)o序的情況下比較的次數(shù)為( )

　　A.n-1 B.n

　　C.n+1 D.n(n-1)/2

　　8.對(duì)線性表進(jìn)行二分查找時(shí)，要求線性表必須( )

　　A.以順序方式存儲(chǔ)

　　B.以鏈?zhǔn)椒绞酱鎯?chǔ)

　　C.以順序方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排列

　　D.以鏈接方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排列