浙02142#數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題第5頁（共5頁）全國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.becabC.deabc D.cedba3.含有n個(gè)結(jié)點(diǎn)的二叉樹用二叉鏈表表示時(shí)，空指針域個(gè)數(shù)為()A.n-1 B.nC.n+1 D.n+24.在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和與圖的邊數(shù)的比是()A.1∶2 B.1∶1C.2∶1 D.4∶15.長度為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.nC.n+1 D.n(n-1)／28.對(duì)線性表進(jìn)行二分查找時(shí)，要求線性表必須()A.以順序方式存儲(chǔ)B.以鏈?zhǔn)椒绞酱鎯?chǔ)C.以順序方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排列D.以鏈接方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排列9.在表長為n的順序表上做刪除運(yùn)算，其平均時(shí)間復(fù)雜度為()A.O(1) B.O(n)C.O(nlog2n) D.O(n2)10.當(dāng)利用大小為n的數(shù)組順序存儲(chǔ)一個(gè)隊(duì)列時(shí)，該隊(duì)列的最大容量為()A.n-2 B.n-1C.n D.n+111.有關(guān)插入排序的敘述，錯(cuò)誤的是()A.插入排序在最壞情況下需要O(n2)時(shí)間B.插入排序在最佳情況可在O(n)時(shí)間內(nèi)完成C.插入排序平均需要O(nlog2n)時(shí)間D.插入排序的空間復(fù)雜度為O(1)12.有關(guān)樹的敘述正確的是()A.每一個(gè)內(nèi)部結(jié)點(diǎn)至少有一個(gè)兄弟B.每一個(gè)葉結(jié)點(diǎn)均有父結(jié)點(diǎn)C.有的樹沒有子樹D.每個(gè)樹至少有一個(gè)根結(jié)點(diǎn)與一個(gè)葉結(jié)點(diǎn)。13.循環(huán)隊(duì)列存儲(chǔ)在數(shù)組元素A[0]至A[m]中，則入隊(duì)時(shí)的操作為()A.rear=rear+1 B.rear=(rear+1)％(m-1)C.rear=(rear+1)％m D.rear=(rear+1)％(m+1)14.關(guān)于串的的敘述，不正確的是()A.串是字符的有限序列B.空串是由空格構(gòu)成的串C.替換是串的一種重要運(yùn)算D.串既可以采用順序存儲(chǔ)，也可以采用鏈?zhǔn)酱鎯?chǔ)15.對(duì)稱矩陣A[N][N]，A[1][1]為首元素，將下三角(包括對(duì)角線)元素以行優(yōu)先順序存儲(chǔ)到一維數(shù)組元素T[1]至T[N(N+1)／2]中，則任一上三角元素A[i][j]存于T[k]中，下標(biāo)k為()A.i(i-1)／2+j B.j(j-1)／2+iC.i(j-i)／2+1 D.j(i-1)／2+l二、填空題(本大題共13小題，每小題2分，共26分)請(qǐng)?jiān)诿啃☆}的空格中填上正確答案。錯(cuò)填、不填均無分。16.下列程序段的時(shí)間復(fù)雜度為____________。for(i=1；i<=n；i++)for(j=1；j<=n；j++)for(k=1；k<=n；k++)s=i+j+k；17.在數(shù)據(jù)結(jié)構(gòu)中，各個(gè)結(jié)點(diǎn)按邏輯關(guān)系互相纏繞，任意兩個(gè)結(jié)點(diǎn)可以鄰接的結(jié)構(gòu)稱為____________。18.在單鏈表中，存儲(chǔ)每個(gè)結(jié)點(diǎn)有兩個(gè)域，一個(gè)是數(shù)據(jù)域，另一個(gè)是指針域，指針域指向該結(jié)點(diǎn)____________的。19.在棧結(jié)構(gòu)中，允許插入的一端稱為____________。20.從一個(gè)長度為n的順序表中刪除第i個(gè)元素(1≤i≤n)時(shí)，需向前移動(dòng)____________個(gè)元素。21.一個(gè)棧的輸入序列是1，2，3，…，n，輸出序列的第一個(gè)元素是n，則第i個(gè)輸出元素為____________。22.循環(huán)隊(duì)列被定義為結(jié)構(gòu)類型，含有三個(gè)域：data、front和rear，則循環(huán)隊(duì)列sq為空的條件是____________。23.一個(gè)10階對(duì)稱矩陣A，采用行優(yōu)先順序壓縮存儲(chǔ)上三角元素，a00為第一個(gè)元素，其存儲(chǔ)地址為0，每個(gè)元素占有1個(gè)存儲(chǔ)地址空間，則a45的地址為____________。24.對(duì)于一棵滿二叉樹，若有m個(gè)葉子，則樹中結(jié)點(diǎn)數(shù)為____________。25.含有n個(gè)頂點(diǎn)和n-1條邊的連通圖G采用____________存儲(chǔ)結(jié)構(gòu)較省空間。26.在圖中，第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑稱為____________。27.動(dòng)態(tài)查找中兩個(gè)元素X，Y存入同一個(gè)散列表時(shí)，X、Y鍵值相同，則這種情況稱為____________。28.堆排序需____________個(gè)記錄大小的輔助存儲(chǔ)空間。三、應(yīng)用題(本大題共5小題，每小題6分，共30分)29.有一字符串的次序?yàn)?3*y+a／y！2，試?yán)脳⑤敵龃涡蚋淖優(yōu)?y*-ay！2／+，試寫出進(jìn)棧和退棧的操作步驟。(用push(x)表示x進(jìn)棧，pop(x)表示x退棧)30.已知一棵二叉樹的先根遍歷序列為ABCDEGHF，中根遍歷序列為CBEDAGFH，畫出該二叉樹。31.題31圖中二叉排序樹的各結(jié)點(diǎn)的值為32～40，標(biāo)出各結(jié)點(diǎn)的值。題31圖32.下述矩陣表示一個(gè)無向網(wǎng)，畫出該無向網(wǎng)，并構(gòu)造出其最小生成樹。33.什么是堆?寫出對(duì)應(yīng)于序列(10