國(guó)家工信部網(wǎng)站備案實(shí)名:湖北自考網(wǎng) 為考生提供湖北自考信息服務(wù),僅供學(xué)習(xí)交流使用,官方信息以湖北教育考試院為準(zhǔn)。
湖北自考在線 湖北學(xué)位英語(yǔ)培訓(xùn)班 湖北成人高考報(bào)名 湖北自考視頻免費(fèi)領(lǐng)取

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

湖北自考網(wǎng) 來(lái)源: 時(shí)間:2009-07-04 00:00:00

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

一、單項(xiàng)選擇題(本大題共15小題,每小題2分,共30分)
在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的,請(qǐng)將其代碼填寫在題后的括號(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;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];
上列程序的時(shí)間復(fù)雜度為(       )
A.O(m+n×t) B.O(m+n+t)
C.O(m×n×t) D.O(m×t+n)
3.若線性表最常用的操作是存取第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.
C.n(n+1) D.2n(n+1)
12.設(shè)圖的鄰接矩陣為 ,則該圖為(       )
A.有向圖 B.無(wú)向圖 
C.強(qiáng)連通圖 D.完全圖
13.二分查找算法的時(shí)間復(fù)雜度是(       )
A.O(n2)  B.O(nlog2n) 
C.O(n) D.O(log2n)
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ù),稱為_(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)中,允許插入的一端稱為 _________;在隊(duì)列結(jié)構(gòu)中,允許插入的一端稱為 _________。
21.在循環(huán)隊(duì)列中,存儲(chǔ)空間為0~n-1。設(shè)隊(duì)頭指針front指向隊(duì)頭元素前一個(gè)空閑元素,隊(duì)尾指針指向隊(duì)尾元素,那么其隊(duì)空標(biāo)志為rear=front,隊(duì)滿標(biāo)志為 _________。
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ì)線性表R[0…59]進(jìn)行分塊檢索,共分為10塊,每塊長(zhǎng)度等于6。若檢索索引表和塊均用順序檢索的方法,則檢索每一個(gè)元素的平均檢索長(zhǎng)度為_(kāi)________。
26.文件在外存儲(chǔ)器上的組織結(jié)構(gòu)主要有三種:順序文件、散列文件和索引文件,其中 _________特別適應(yīng)磁帶存儲(chǔ)器,也適應(yīng)磁盤存儲(chǔ)器。
27.在插入排序、冒泡排序、快速排序、歸并排序等排序算法中,占用輔助空間最多的是 _________。
28.冒泡排序最好的時(shí)間復(fù)雜度為 _________,平均時(shí)間復(fù)雜度為 _________,是一種穩(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)畫出該圖。
(2)根據(jù)該鄰接表從頂點(diǎn)A出發(fā),分別寫出按深度優(yōu)先搜索法和廣度優(yōu)先搜索法進(jìn)行遍歷的結(jié)點(diǎn)序列。
32.假定采用H(k)=k mod 7計(jì)算散列地址,引用線性探測(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)行排序,寫出其第一趟排序的全過(guò)程。

四、算法設(shè)計(jì)題(本大題共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é)點(diǎn)在給定的二叉排序樹(shù)中所在的層次。請(qǐng)完善該算法。
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)_________;
}
}

結(jié)束
本文標(biāo)簽
特別聲明:1.凡本網(wǎng)注明稿件來(lái)源為“湖北自考網(wǎng)”的,轉(zhuǎn)載必須注明“稿件來(lái)源:湖北自考網(wǎng)(trillionsbussines.com)”,違者將依法追究責(zé)任;
2.部分稿件來(lái)源于網(wǎng)絡(luò),如有不實(shí)或侵權(quán),請(qǐng)聯(lián)系我們溝通解決。最新官方信息請(qǐng)以湖北省教育考試院及各教育官網(wǎng)為準(zhǔn)!
限時(shí),免費(fèi)獲取學(xué)歷提升方案

已幫助10w萬(wàn)+意向?qū)W歷提升用戶成功上岸

  • 毛澤東思想概論

    毛澤東思想概論

    培訓(xùn)優(yōu)勢(shì):課時(shí)考點(diǎn)精講+刷題+沖刺,熟練應(yīng)對(duì)考試題型。全程督促學(xué)習(xí),安排好學(xué)習(xí)計(jì)劃。 毛澤東思想概論...自考培訓(xùn)
  • 英語(yǔ)二

    英語(yǔ)二

    本課程既是一門語(yǔ)言實(shí)踐課程,也是拓寬知識(shí)、了解世界文化的重要素質(zhì)課程,它以培養(yǎng)學(xué)習(xí)者的綜合語(yǔ)言應(yīng)用能力為目標(biāo),使他們?cè)趯W(xué)習(xí)、工作和社會(huì)交往中能夠使用英語(yǔ)進(jìn)行有效的交流。 英語(yǔ)二...自考培訓(xùn)
  • 馬克思主義基本原理概論

    馬克思主義基本原理概論

    本書包括兩個(gè)部分:自學(xué)考試大綱和基本原理。主要內(nèi)容有,馬克思主義是關(guān)于工人階級(jí)和人類解放的科學(xué),物質(zhì)世界及其發(fā)展規(guī)律,認(rèn)識(shí)的本質(zhì)及其規(guī)律,人類社會(huì)及其發(fā)展規(guī)律,資本主義的形成及其發(fā)展,資本主義發(fā)展的歷史進(jìn)程,社會(huì)主義社會(huì)及其進(jìn)程,共產(chǎn)主義社會(huì)及其進(jìn)程等。 馬克思主義基本原理概論...自考培訓(xùn)
  • 思想道德修養(yǎng)與法律基礎(chǔ)

    思想道德修養(yǎng)與法律基礎(chǔ)

    《思想道德修養(yǎng)與法律基礎(chǔ)》課具有鮮明的政治性、思想性、理論性、針對(duì)性、科學(xué)性、知識(shí)性以及實(shí)踐性和修養(yǎng)性。它包羅政治、思想、道德、心理本質(zhì)、學(xué)習(xí)成才和法律本質(zhì)等內(nèi)容,指導(dǎo)和回答大學(xué)生在人生、抱負(fù)、信念等方面遍及關(guān)心和迫切需要解決的問(wèn)題。 思想道德修養(yǎng)與法律基礎(chǔ)...自考培訓(xùn)
  • 中國(guó)近代史綱要

    中國(guó)近代史綱要

    “中國(guó)近現(xiàn)代史綱要”全國(guó)高等教育自學(xué)考試指定教材,依據(jù)中央審定的普通高等學(xué)?!爸袊?guó)近現(xiàn)代史綱要”編寫大綱以及馬克思主義理論研究和建設(shè)工程重點(diǎn)教材《中國(guó)近現(xiàn)代史綱要》,結(jié)合自學(xué)考試的特點(diǎn)設(shè)計(jì)了十章,集中講述1840年鴉片戰(zhàn)爭(zhēng)爆發(fā)一直到2007年中國(guó)共產(chǎn)黨第十七次全國(guó)代表大會(huì)召開(kāi)的160多年的中國(guó)近現(xiàn)代歷史。 中國(guó)近代史綱要...自考培訓(xùn)
微信公眾號(hào) 考試交流群
湖北自考網(wǎng)微信公眾號(hào)

掃一掃關(guān)注微信公眾號(hào)

隨時(shí)獲取湖北省自考政策、通知、公告以及各類學(xué)習(xí)資料、學(xué)習(xí)方法、課程。