全國2009年1月自學(xué)考試數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題
數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題
課程代碼:02142
一、單項選擇題(本大題共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;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];
上列程序的時間復(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.n(n-1)/2
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)=kmod7計算散列地址,引用線性探測的開放定址法解決沖突,試在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.完善下列折半插入排序算法。
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é)點在給定的二叉排序樹中所在的層次。請完善該算法。
Voidlevel(BSTreeroot,p)
{intlevel=0;
if(!root)
(1)_________;
else{
level++;
while(root—>key!=p—>key){
if(root—>keykey)
(2)_________;
else
(3)_________;
level++;
}
(4)_________;
}
}
·09年1月全國各省市自學(xué)考試成績查詢時間匯總
·2009年自學(xué)考試報名時間匯總
·全國各地2008年10月自考網(wǎng)上成績查詢匯總
·環(huán)球網(wǎng)校2009年自考課程查看
更多信息請訪問:自學(xué)考試頻道 自學(xué)考試論壇 自學(xué)考試博客圈
最新資訊
- 真題練習(xí):自學(xué)考試《中國近現(xiàn)代史綱要》真題及答案(12.21)2024-12-21
- 真題訓(xùn)練!自學(xué)考試《外國文學(xué)史》真題及答案解析(11.9)2024-11-09
- 備考2025年自學(xué)考試:《外國文學(xué)史》真題訓(xùn)練(11.7)2024-11-07
- 論述題和簡答題!2024年10月自考《中國近代史綱要》真題及答案2024-10-31
- 考后對答案!24年10月自考《習(xí)概》真題及答案解析2024-10-30
- 真題速遞:24年10月自考《馬克思主義基本原理概論》真題及答案匯總2024-10-30
- 24年10月自考《馬克思主義基本原理概論》簡答題和論述題答案匯總2024-10-29
- 簡答題匯總!24年10月自考《美學(xué)》真題及答案解析2024-10-29
- 論述和簡答題匯總!24年10月自考《習(xí)概》真題及答案2024-10-29
- 論述題!2024年10月自考《習(xí)概》真題及答案解析2024-10-29