數(shù)據(jù)結(jié)構(gòu)導(dǎo)論2009年1月真題及答案解析（02142）

數(shù)據(jù)結(jié)構(gòu)導(dǎo)論2009年1月真題及答案（02142），該試卷為數(shù)據(jù)結(jié)構(gòu)導(dǎo)論自考?xì)v年真題試卷，包含答案及詳細(xì)解析。

一、單項選擇題(本大題共15小題，每小題2分，共30分)在每小題列出的四個備選項中只有一個是符合題目要求的，請將其代碼填寫在題后的括號內(nèi)。錯選、多選或未選均無分。

1.數(shù)據(jù)的不可分割的最小標(biāo)識單位是(　　)

A.數(shù)據(jù)項
B.數(shù)據(jù)記錄
C.數(shù)據(jù)元素
D.數(shù)據(jù)變量

2.上列程序的時間復(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é)點(diǎn)A，要刪除A之后的結(jié)點(diǎn)(若存在)，則修改指針的操作為(　　)

A.p->next=p->next->next
B.p=p->next
C.p=p->next->next
D.p->next=p

5.向一個棧頂指針為hs的鏈棧中插入一個*s結(jié)點(diǎn)時，應(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個存儲單元，在以行序?yàn)橹餍虻拇鎯Ψ绞较?，某?shù)據(jù)元素的地址為LOC+50L，則在以列序?yàn)橹餍虻拇鎯Ψ绞较?，該元素的存儲地址?　　)

A.LOC+28L
B.LOC+36L
C.LOC+50L
D.LOC+52L

8.具有n個結(jié)點(diǎn)的二叉樹，擁有指向孩子結(jié)點(diǎn)的分支數(shù)目是(　　)

A.n-1
B.n
C.n+1
D.2n

9.對一棵有100個結(jié)點(diǎn)的完全二叉樹按層序編號，則編號為49的結(jié)點(diǎn)，它的左孩子的編號為(　　)

A.99
B.98
C.97
D.50

10.有m個葉子結(jié)點(diǎn)的哈夫曼樹，其結(jié)點(diǎn)總數(shù)是(　　)

A.2m-1
B.2m
C.2m+1
D.2(m+1)

11.有n個結(jié)點(diǎn)的無向圖的邊數(shù)最多為(　　)

A.n+1

B.

12.設(shè)圖的鄰接矩陣為，則該圖為(　　)

A.有向圖
B.無向圖
C.強(qiáng)連通圖
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é)點(diǎn)的方法生成一棵二叉排序樹，則該樹的深度為(　　)

A.4
B.5
C.6
D.7

15.采用排序算法對n個元素進(jìn)行排序，其排序趟數(shù)肯定為n-1趟的排序方法是(　　)

A.插入和快速
B.冒泡和快速
C.選擇和插入
D.選擇和冒泡

二、填空題(本大題共13小題，每小題2分，共26分)請在每小題的空格中填上正確答案。錯填、不填均無分。

11.在數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)的存儲結(jié)構(gòu)有順序存儲方式、鏈?zhǔn)酱鎯Ψ绞?、_________和散列存儲方式等四種。

12. 作為一個算法輸入的數(shù)據(jù)所含數(shù)據(jù)元素的數(shù)目，或與此數(shù)目有關(guān)的其他參數(shù)，稱為_________。

13.在雙鏈表中，存儲一個結(jié)點(diǎn)有三個域，一個是數(shù)據(jù)域，另兩個是指針域，分別指向 _________和 _________。

14.在有n個元素的鏈隊列中，入隊和出隊操作的時間復(fù)雜度分別為_________和_________。

15.在棧結(jié)構(gòu)中，允許插入的一端稱為 _________;在隊列結(jié)構(gòu)中，允許插入的一端稱為 _________。

16.在循環(huán)隊列中，存儲空間為0~n-1。設(shè)隊頭指針front指向隊頭元素前一個空閑元素，隊尾指針指向隊尾元素，那么其隊空標(biāo)志為rear=front，隊滿標(biāo)志為 _________。

17.深度為k的二叉樹至多有 _________個結(jié)點(diǎn)，最少有 _________個結(jié)點(diǎn)。

18.設(shè)有一稠密圖G，則G采用 _________存儲結(jié)構(gòu)較省空間。設(shè)有一稀疏圖G，則G采用 _________存儲結(jié)構(gòu)較省空間。

19.在一個具有n個結(jié)點(diǎn)的單鏈表中查找其值等于x的結(jié)點(diǎn)時，在查找成功的情況下，需平均比較_________個元素結(jié)點(diǎn)。

110.假定對線性表R[0…59]進(jìn)行分塊檢索，共分為10塊，每塊長度等于6。若檢索索引表和塊均用順序檢索的方法，則檢索每一個元素的平均檢索長度為_________。

111.文件在外存儲器上的組織結(jié)構(gòu)主要有三種：順序文件、散列文件和索引文件，其中 _________特別適應(yīng)磁帶存儲器，也適應(yīng)磁盤存儲器。

112.在插入排序、冒泡排序、快速排序、歸并排序等排序算法中，占用輔助空間最多的是 _________。

113.冒泡排序最好的時間復(fù)雜度為_________，平均時間復(fù)雜度為_________，是一種穩(wěn)定的排序算法。

三、應(yīng)用題(本大題共5小題，每小題6分，共30分)

21.已知一棵二叉樹的前序序列是ABCDEFG，中序序列是CBDAEGF。請構(gòu)造出該二叉樹，并給出該二叉樹的后序序列。

22.將題30圖所示的由三棵樹組成的森林轉(zhuǎn)化為一棵二叉樹。                                                    題30圖

23.已知某圖的鄰接表存儲結(jié)構(gòu)如題31圖所示：                                                 題31圖(1)畫出該圖。(2)根據(jù)該鄰接表從頂點(diǎn)A出發(fā)，分別寫出按深度優(yōu)先搜索法和廣度優(yōu)先搜索法進(jìn)行遍歷的結(jié)點(diǎn)序列。

24.假定采用H(k)=k mod 7計算散列地址，引用線性探測的開放定址法解決沖突，試在0~6的散列地址空間中，對關(guān)鍵字序列(38，25，74，63，52，48)構(gòu)造散列表，并求出等概率情況下查找成功的平均查找長度。

25.用快速排序法對數(shù)據(jù)序列(49，38，65，97，16，53，134，27，39)進(jìn)行排序，寫出其第一趟排序的全過程。

四、算法設(shè)計題(本大題共2小題，每小題7分，共14分)

31.完善下列折半插入排序算法。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];    }}

32.下列算法的功能是求出指定結(jié)點(diǎn)在給定的二叉排序樹中所在的層次。請完善該算法。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)_________;           }}