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

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

一、單項選擇題（本大題共15小題，每小題2分，共30分）
在每小題列出的四個備選項中只有一個是符合題目要求的，請將其代碼填寫在題后的括號內(nèi)。錯選、多選或未選均無分。
1.數(shù)據(jù)的不可分割的最小標(biāo)識單位是（       ）
A.數(shù)據(jù)項  B.數(shù)據(jù)記錄 
C.數(shù)據(jù)元素 D.數(shù)據(jù)變量
2.        for（i=0；i<m；i++）
for（j=0；j<t；j++）
c［i］［j］=0；
for（i=0；i<m；i++）
for（j=0；j<t；j++）
for（k=0；k<n；k++）
c［i］［j］=c［i］［j］+a［i］［k］*b［k］［j］；
上列程序的時間復(fù)雜度為（       ）
A.O（m+n×t） B.O（m+n+t）
C.O（m×n×t） D.O（m×t+n）
3.若線性表最常用的操作是存取第i個元素及其前趨的值，那么最節(jié)省操作時間的存儲方式是（       ）
A.單鏈表 B.雙鏈表
C.單循環(huán)鏈表 D.順序表
4.設(shè)單鏈表中指針p指向結(jié)點A，要刪除A之后的結(jié)點（若存在），則修改指針的操作為（       ）
A.p—>next=p—>next—>next B.p=p—>next
C.p=p—>next—>next D.p—>next=p
5.向一個棧頂指針為hs的鏈棧中插入一個*s結(jié)點時，應(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)隊列的元素存放在一維數(shù)組Q［0‥30］中，隊列非空時，front指示隊頭元素的前一個位置，rear指示隊尾元素。如果隊列中元素的個數(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］，起始地址為LOC，每個元素占2L個存儲單元，在以行序為主序的存儲方式下，某數(shù)據(jù)元素的地址為LOC+50L，則在以列序為主序的存儲方式下，該元素的存儲地址為（       ）
A.LOC+28L B.LOC+36L 
C.LOC+50L D.LOC+52L 8.具有n個結(jié)點的二叉樹，擁有指向孩子結(jié)點的分支數(shù)目是（       ）
A.n-1 B.n 
C.n+1 D.2n
9.對一棵有100個結(jié)點的完全二叉樹按層序編號，則編號為49的結(jié)點，它的左孩子的編號為（       ）
A.99 B.98 
C.97 D.50
10.有m個葉子結(jié)點的哈夫曼樹，其結(jié)點總數(shù)是（       ）
A.2m-1 B.2m 
C.2m+1 D.2（m+1）
11.有n個結(jié)點的無向圖的邊數(shù)最多為（       ）
A.n+1 B.
C.n（n+1） D.2n（n+1）
12.設(shè)圖的鄰接矩陣為 ，則該圖為（       ）
A.有向圖 B.無向圖 
C.強連通圖 D.完全圖
13.二分查找算法的時間復(fù)雜度是（       ）
A.O（n2）  B.O（nlog2n） 
C.O（n） D.O（log2n）
14.已知8個元素（34，76，45，18，26，54，92，65），按照依次插入結(jié)點的方法生成一棵二叉排序樹，則該樹的深度為（       ）
A.4 B.5 
C.6 D.7
15.采用排序算法對n個元素進行排序，其排序趟數(shù)肯定為n-1趟的排序方法是（       ）
A.插入和快速 B.冒泡和快速 
C.選擇和插入 D.選擇和冒泡

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

三、應(yīng)用題（本大題共5小題，每小題6分，共30分）
29.已知一棵二叉樹的前序序列是ABCDEFG，中序序列是CBDAEGF。請構(gòu)造出該二叉樹，并給出該二叉樹的后序序列。
30.將題30圖所示的由三棵樹組成的森林轉(zhuǎn)化為一棵二叉樹。
 
題30圖
31.已知某圖的鄰接表存儲結(jié)構(gòu)如題31圖所示：
 
題31圖
（1）畫出該圖。
（2）根據(jù)該鄰接表從頂點A出發(fā)，分別寫出按深度優(yōu)先搜索法和廣度優(yōu)先搜索法進行遍歷的結(jié)點序列。
32.假定采用H（k）=k mod 7計算散列地址，引用線性探測的開放定址法解決沖突，試在0~6的散列地址空間中，對關(guān)鍵字序列（38，25，74，63，52，48）構(gòu)造散列表，并求出等概率情況下查找成功的平均查找長度。
33.用快速排序法對數(shù)據(jù)序列（49，38，65，97，16，53，134，27，39）進行排序，寫出其第一趟排序的全過程。

四、算法設(shè)計題（本大題共2小題，每小題7分，共14分）
34.完善下列折半插入排序算法。
Void binasort（struct node r［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<r［mid］.key）
high=（2）_________；
else low=（3）_________；
}
for（j=i-1；j>=low；j- -）
（4）_________；
r［low］=r［0］ ；
}
}
35.下列算法的功能是求出指定結(jié)點在給定的二叉排序樹中所在的層次。請完善該算法。
Void level（BSTree root，p）
{ int level=0；
if（！root）
（1）_________；
else{
level++；
while（root—>key!=p—>key）{
if（root—>key<p—>key）
（2）_________ ；
else
（3）_________ ；
level++；
}
（4）_________；
}
}