全國(guó)2009年1月自學(xué)考試數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題

更新時(shí)間：2009-10-19 15:27:29 來(lái)源：|0

瀏覽

自學(xué)考試報(bào)名、考試、查分時(shí)間免費(fèi)短信提醒

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

一、單項(xiàng)選擇題(本大題共15小題，每小題2分，共30分)
在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其代碼填寫(xiě)在題后的括號(hào)內(nèi)。錯(cuò)選、多選或未選均無(wú)分。
1.數(shù)據(jù)的不可分割的最小標(biāo)識(shí)單位是（　?。?
A.數(shù)據(jù)項(xiàng)
B.數(shù)據(jù)記錄
C.數(shù)據(jù)元素
D.數(shù)據(jù)變量

2.for(i=0;ifor(j=0;jc[i][j]=0;
for(i=0;ifor(j=0;jfor(k=0;kc[i][j]=c[i][j]+a[i][k]*b[k][j];
上列程序的時(shí)間復(fù)雜度為（　　）
A.O(m+n×t)
B.O(m+n+t)
C.O(m×n×t)
D.O(m×t+n)

3.若線(xiàn)性表最常用的操作是存取第i個(gè)元素及其前趨的值，那么最節(jié)省操作時(shí)間的存儲(chǔ)方式是（　　）
A.單鏈表
B.雙鏈表
C.單循環(huán)鏈表
D.順序表

4.設(shè)單鏈表中指針p指向結(jié)點(diǎn)A，要?jiǎng)h除A之后的結(jié)點(diǎn)(若存在)，則修改指針的操作為（　?。?
A.p—>next=p—>next—>next
B.p=p—>next
C.p=p—>next—>next
D.p—>next=p

5.向一個(gè)棧頂指針為hs的鏈棧中插入一個(gè)*s結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行的操作為（　?。?
A.hs—>next=s;
B.s—>next=hs;hs=s;
C.s—>next=hs—>next;hs—>next=s;
D.s—>next=hs;hs=hs—>next;

6.設(shè)循環(huán)隊(duì)列的元素存放在一維數(shù)組Q[0ㄅ30]中，隊(duì)列非空時(shí)，front指示隊(duì)頭元素的前一個(gè)位置，rear指示隊(duì)尾元素。如果隊(duì)列中元素的個(gè)數(shù)為11，front的值為25，則rear應(yīng)指向的元素是（　　）
A.Q[4]
B.Q[5]
C.Q[14]
D.Q[15]

7.定義二維數(shù)組A[1ㄅ8，0ㄅ10]，起始地址為L(zhǎng)OC，每個(gè)元素占2L個(gè)存儲(chǔ)單元，在以行序?yàn)橹餍虻拇鎯?chǔ)方式下，某數(shù)據(jù)元素的地址為L(zhǎng)OC+50L，則在以列序?yàn)橹餍虻拇鎯?chǔ)方式下，該元素的存儲(chǔ)地址為（　?。?
A.LOC+28L
B.LOC+36L
C.LOC+50L
D.LOC+52L

8.具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，擁有指向孩子結(jié)點(diǎn)的分支數(shù)目是（　?。?
A.n-1
B.n
C.n+1
D.2n

9.對(duì)一棵有100個(gè)結(jié)點(diǎn)的完全二叉樹(shù)按層序編號(hào)，則編號(hào)為49的結(jié)點(diǎn)，它的左孩子的編號(hào)為（　?。?
A.99
B.98
C.97
D.50

10.有m個(gè)葉子結(jié)點(diǎn)的哈夫曼樹(shù)，其結(jié)點(diǎn)總數(shù)是（　?。?
A.2m-1
B.2m
C.2m+1
D.2(m+1)

11.有n個(gè)結(jié)點(diǎn)的無(wú)向圖的邊數(shù)最多為（　?。?
A.n+1
B.n(n-1)/2
C.n(n+1)
D.2n(n+1)

12.設(shè)圖的鄰接矩陣為，則該圖為（　?。?
A.有向圖
B.無(wú)向圖
C.強(qiáng)連通圖
D.完全圖

13.二分查找算法的時(shí)間復(fù)雜度是（　?。?
A.O(n²)
B.O(nlog₂n)
C.O(n)
D.O(log₂n)

14.已知8個(gè)元素(34，76，45，18，26，54，92，65)，按照依次插入結(jié)點(diǎn)的方法生成一棵二叉排序樹(shù)，則該樹(shù)的深度為（　?。?
A.4
B.5
C.6
D.7

15.采用排序算法對(duì)n個(gè)元素進(jìn)行排序，其排序趟數(shù)肯定為n-1趟的排序方法是（　　）
A.插入和快速
B.冒泡和快速
C.選擇和插入
D.選擇和冒泡

二、填空題(本大題共13小題，每小題2分，共26分)
請(qǐng)?jiān)诿啃☆}的空格中填上正確答案。錯(cuò)填、不填均無(wú)分。
16.在數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)有順序存儲(chǔ)方式、鏈?zhǔn)酱鎯?chǔ)方式、_________和散列存儲(chǔ)方式等四種。
17.作為一個(gè)算法輸入的數(shù)據(jù)所含數(shù)據(jù)元素的數(shù)目，或與此數(shù)目有關(guān)的其他參數(shù)，稱(chēng)為_(kāi)________。
18.在雙鏈表中，存儲(chǔ)一個(gè)結(jié)點(diǎn)有三個(gè)域，一個(gè)是數(shù)據(jù)域，另兩個(gè)是指針域，分別指向_________和_________。
19.在有n個(gè)元素的鏈隊(duì)列中，入隊(duì)和出隊(duì)操作的時(shí)間復(fù)雜度分別為_(kāi)________和_________。
20.在棧結(jié)構(gòu)中，允許插入的一端稱(chēng)為_(kāi)________;在隊(duì)列結(jié)構(gòu)中，允許插入的一端稱(chēng)為_(kāi)________。
21.在循環(huán)隊(duì)列中，存儲(chǔ)空間為0~n-1。設(shè)隊(duì)頭指針front指向隊(duì)頭元素前一個(gè)空閑元素，隊(duì)尾指針指向隊(duì)尾元素，那么其隊(duì)空標(biāo)志為rear=front，隊(duì)滿(mǎn)標(biāo)志為_(kāi)________。
22.深度為k的二叉樹(shù)至多有_________個(gè)結(jié)點(diǎn)，最少有_________個(gè)結(jié)點(diǎn)。
23.設(shè)有一稠密圖G，則G采用_________存儲(chǔ)結(jié)構(gòu)較省空間。設(shè)有一稀疏圖G，則G采用_________存儲(chǔ)結(jié)構(gòu)較省空間。
24.在一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表中查找其值等于x的結(jié)點(diǎn)時(shí)，在查找成功的情況下，需平均比較_________個(gè)元素結(jié)點(diǎn)。
25.假定對(duì)線(xiàn)性表R[0…59]進(jìn)行分塊檢索，共分為10塊，每塊長(zhǎng)度等于6。若檢索索引表和塊均用順序檢索的方法，則檢索每一個(gè)元素的平均檢索長(zhǎng)度為_(kāi)________。
26.文件在外存儲(chǔ)器上的組織結(jié)構(gòu)主要有三種：順序文件、散列文件和索引文件，其中_________特別適應(yīng)磁帶存儲(chǔ)器，也適應(yīng)磁盤(pán)存儲(chǔ)器。
27.在插入排序、冒泡排序、快速排序、歸并排序等排序算法中，占用輔助空間最多的是_________。
28.冒泡排序最好的時(shí)間復(fù)雜度為_(kāi)________，平均時(shí)間復(fù)雜度為_(kāi)________，是一種穩(wěn)定的排序算法。

三、應(yīng)用題(本大題共5小題，每小題6分，共30分)
29.已知一棵二叉樹(shù)的前序序列是ABCDEFG，中序序列是CBDAEGF。請(qǐng)構(gòu)造出該二叉樹(shù)，并給出該二叉樹(shù)的后序序列。
30.將題30圖所示的由三棵樹(shù)組成的森林轉(zhuǎn)化為一棵二叉樹(shù)。

題30圖
31.已知某圖的鄰接表存儲(chǔ)結(jié)構(gòu)如題31圖所示：

題31圖
(1)畫(huà)出該圖。
(2)根據(jù)該鄰接表從頂點(diǎn)A出發(fā)，分別寫(xiě)出按深度優(yōu)先搜索法和廣度優(yōu)先搜索法進(jìn)行遍歷的結(jié)點(diǎn)序列。
32.假定采用H(k)=kmod7計(jì)算散列地址，引用線(xiàn)性探測(cè)的開(kāi)放定址法解決沖突，試在0~6的散列地址空間中，對(duì)關(guān)鍵字序列(38，25，74，63，52，48)構(gòu)造散列表，并求出等概率情況下查找成功的平均查找長(zhǎng)度。
33.用快速排序法對(duì)數(shù)據(jù)序列(49，38，65，97，16，53，134，27，39)進(jìn)行排序，寫(xiě)出其第一趟排序的全過(guò)程。

四、算法設(shè)計(jì)題(本大題共2小題，每小題7分，共14分)
34.完善下列折半插入排序算法。
Voidbinasort(structnoder[MAXSIZE]，int n)
　　{for(i=2;i<=n;i++){
　　　　r[0]=r[i];low=1;high=i-1;
　　　　while(low<=high){
　　　　　　mid=(1)_________;
　　　　　　if(r[0].key　　　　　　　　high=(2)_________;
　　　　　　elselow=(3)_________;
　　　　}
　　　　for(j=i-1;j>=low;j--)
　　　　(4)_________;
　　　　r[low]=r[0];
　　}
}
35.下列算法的功能是求出指定結(jié)點(diǎn)在給定的二叉排序樹(shù)中所在的層次。請(qǐng)完善該算法。
Voidlevel(BSTreeroot，p)
　　{intlevel=0;
　　　　if(!root)
　　　　　　(1)_________;
　　　　else{
　　　　　　level++;
　　　　　　while(root—>key!=p—>key){
　　　　　　　　if(root—>keykey)
　　　　　　　　　　(2)_________;
　　　　　　　　else
　　　　　　　　　　(3)_________;
　　　　　　　　level++;
　　　　　　}
　　　　　　(4)_________;
　　　　}
　　}