數(shù)據(jù)結(jié)構(gòu)考試題9

1、要求：所有的題目的解答均寫在答題紙上，需寫清楚題目的序號。每張答題紙都要寫上姓名和學(xué)號。一、單項(xiàng)選擇題（每小題2分，共20小題，共計(jì)40分）1、設(shè)n是描述問題規(guī)模的非負(fù)整數(shù)，下面程序片段的時(shí)間復(fù)雜度為（ ）。x=1;while (x<=n)x=5*x;A. O(log5n)B.O(n)C.O(nlog5n)D.O(n5)2、順序表和鏈表相比存儲密度較大，這是因?yàn)椋?）。A.順序表的存儲空間是預(yù)先分配的B.順序表不需要增加指針來表示元素之間的邏輯關(guān)系C.鏈表中所有節(jié)點(diǎn)的地址是連續(xù)的D.順序表中所有元素的存儲地址是不連續(xù)的3、在長度為n（n1）的循環(huán)雙鏈表L中，在尾節(jié)點(diǎn)之后插入一個(gè)新節(jié)點(diǎn)的時(shí)

2、間復(fù)雜度為（ ）。A. O(n2)B.O(n)C. O(1)D.O(nlog2n)4、設(shè)棧的輸入序列是1、2、3、4，則（ ）不可能是其出棧序列。A.1，2，4，3B.2，1，3，4C.1，4，3，2D.4，3，1，25、當(dāng)用一個(gè)數(shù)組data0.n-1存放棧中元素時(shí)，棧底最好（ ）。A. 設(shè)置在data0或datan-1處B.設(shè)置在datan-1處C. 設(shè)置在data0處D.設(shè)置在data數(shù)組的任何位置6、在數(shù)據(jù)處理過程中常需要保存一些中間數(shù)據(jù)，如果先保存的數(shù)據(jù)先處理，則使用（ ）來保存這些數(shù)據(jù)。A.線性表B. 隊(duì)列C. 棧D.單鏈表7、在環(huán)形隊(duì)列中，元素的排列順序（ ）。A.與隊(duì)頭和隊(duì)尾指針

3、的取值有關(guān)B.與元素值的大小有關(guān)C.由元素進(jìn)隊(duì)的先后順序確定D.與存放隊(duì)中元素的數(shù)組大小有關(guān)8、將10階對稱矩陣壓縮存儲到一維數(shù)組A中，則數(shù)組A的長度最少為（ ）。A.100B.40C.80D.559、設(shè)目標(biāo)串為s，模式串為是t，在KMP模式匹配中，next4=2的含義是（ ）。A.表示t4字符前面最多有2個(gè)字符和開頭的2個(gè)字符相同B.表示s4字符前面最多有2個(gè)字符和開頭的2個(gè)字符相同C.表示目標(biāo)串匹配失敗的位置是i=4D.表示模式串匹配失敗的位置是j=210、由權(quán)值分別為9、2、7、5的四個(gè)葉子節(jié)點(diǎn)構(gòu)造一棵哈夫曼樹，該樹的帶權(quán)路徑長度為（ ）。A.23B.44C.37D.2711、對于無向圖

4、的鄰接矩陣來說，（ ）。A.第i行上、第i列上非零元素總數(shù)等于頂點(diǎn)i的度數(shù)B.矩陣中的非零元素個(gè)數(shù)等于圖中的邊數(shù)C.第i行上的非零元素個(gè)數(shù)和第i列的非零元素個(gè)數(shù)一定相等D.鄰接矩陣中非全零行的行數(shù)等于圖中的頂點(diǎn)數(shù)12、有一個(gè)頂點(diǎn)編號為04的帶權(quán)有向圖G，現(xiàn)用Floyd算法求任意兩個(gè)頂點(diǎn)之間的最短路徑，在算法執(zhí)行的某時(shí)刻，已考慮了02的頂點(diǎn)，現(xiàn)考慮頂點(diǎn)3，則以下敘述中正確的是（ ）。A.只可能修改從頂點(diǎn)02到頂點(diǎn)3的最短路徑B.只可能修改從頂點(diǎn)3到頂點(diǎn)02的最短路徑C.只可能修改從頂點(diǎn)02到頂點(diǎn)4的最短路徑D.所有兩個(gè)頂點(diǎn)之間的路徑都可能被修改13、適合于折半查找的數(shù)據(jù)組織方式是（ ）。A.以順

5、序表存儲的有序線性表B.以順序表存儲的線性表C.以鏈表存儲的有序線性表D. 以鏈表存儲的線性表14、對含有n個(gè)元素的順序表采用順序查找方法，不成功時(shí)的比較次數(shù)是（ ）。A. 1B. nC. n-1D. n+115、在一棵平衡二叉樹中，每個(gè)節(jié)點(diǎn)的平衡因子的取值范圍是（ ）。A. 12B. -22C. -11D. 0116、在一棵m階B-樹中刪除一個(gè)關(guān)鍵字會引起合并，則該節(jié)點(diǎn)原有（ ）個(gè)關(guān)鍵字。A. 1B. ém/2ùC. ém/2ù+1D. ém/2ù-117、以下關(guān)于哈希查找的敘述中正確的是（ ）。A.哈希查找中不需要任何關(guān)鍵字的比較

6、B.采用拉鏈法解決沖突時(shí)，查找每個(gè)元素的時(shí)間是相同的C.哈希表在查找成功時(shí)的平均查找長度僅僅與表長有關(guān)D.哈希表的裝填因子等于表中填入的記錄數(shù)除以哈希表的長度18、以下排序方法中，（ ）在初始序列已基本有序的情況下，排序效率最高。A.二路歸并排序B. 快速排序C. 直接插入排序D.堆排序19、如要在1000個(gè)整數(shù)中找出前10個(gè)最小的整數(shù)，在以下排序方法中最好采用（ ）。A.直接插入排序B. 冒泡排序C.二路歸并排序D. 希爾排序20、有n個(gè)十進(jìn)制整數(shù)進(jìn)行基數(shù)排序，其中最大的整數(shù)為5位，則基數(shù)排序過程中臨時(shí)建立的隊(duì)數(shù)個(gè)數(shù)是（ ）。A.10B.nC.5D.2二、問答題（共4小題，共計(jì)35分）1、（

7、8分）已知一棵二叉樹的先序遍歷序列為ABDGHCEIF，它的中序遍歷序列是BGDHAEICF，請構(gòu)造出這棵二叉樹，并給出其層次遍歷序列。2、（8分）一棵二叉排序樹的結(jié)構(gòu)如圖1所示，其中各結(jié)點(diǎn)的關(guān)鍵字依次為3240，請標(biāo)出各結(jié)點(diǎn)的關(guān)鍵字。 圖1 一棵二叉排序樹的結(jié)構(gòu)3、（8分）一組記錄關(guān)鍵字為（5，11，7，2，3，17），利用堆排序方法建立初始大根堆，給出你建立的初始大根堆對應(yīng)的關(guān)鍵字序列。4、（11分）對于一個(gè)帶權(quán)連通無向圖G，可以采用Prim算法構(gòu)造出從某個(gè)頂點(diǎn)v出發(fā)的最小生成樹，問該最小生成樹一定包含從頂點(diǎn)v到其他所有頂點(diǎn)的最短路徑嗎？如果回答是，請予以證明；如果回答不是，請給出反例。三

8、、算法設(shè)計(jì)題（共2小題，共計(jì)25分）1. （15分）有兩個(gè)遞增有序表，所有元素為整數(shù)，均采用帶頭結(jié)點(diǎn)的單鏈表存儲，結(jié)點(diǎn)類型定義如下：typedef struct nodeint data;struct node *next; LinkNode;設(shè)計(jì)一個(gè)盡可能高效的算法，將兩個(gè)遞增有序單鏈表ha、hb合并為一個(gè)遞減有序單鏈表hc，要求算法空間復(fù)雜度為O(1)。2、（10分）設(shè)二叉樹中每個(gè)結(jié)點(diǎn)存放單個(gè)字符，其結(jié)點(diǎn)類型如下：typedef struct node char data; struct node *lchild，*rchild; BTNode;設(shè)計(jì)一個(gè)算法求其中單分支的結(jié)點(diǎn)個(gè)數(shù)。“數(shù)據(jù)結(jié)

9、構(gòu)”考試試題（A）參考答案一、單項(xiàng)選擇題（每小題2分，共20小題，共計(jì)40分）1、A2、B3、C4、D5、A6、B7、C8、D9、A10、B11、C12、D13、A14、B15、C16、D17、D18、C19、B20、A二、問答題（共4小題，共計(jì)35分）1、（8分）最后構(gòu)造的二叉樹如圖1所示（4分），其層次遍歷序列為ABCDEFGHI（4分）。ABCDGHFIE圖1 一棵二叉樹2、（8分）得到如圖2所示的二叉排序樹（中序序列是遞增的）。 363240353733383439 圖2 一棵二叉排序樹3、（8分）初始大根堆對應(yīng)的關(guān)鍵字序列為（17，11，7，2，3，5），如果畫出樹正確但沒有給出序列

10、扣2分。4、（11分）不是。反例：如圖3所示的圖G從頂點(diǎn)0出發(fā)的最小生成樹如圖4所示，而從頂點(diǎn)0到頂點(diǎn)的2的最短路徑為0®2，而不是最小生成樹中的0®1®2。 圖3 一個(gè)帶權(quán)連通無向圖G圖4 圖G的一棵最小生成樹評分說明：回答“不是”或者“不一定”給5分，反例部分為6分?；卮稹笆恰北绢}為0分。三、算法設(shè)計(jì)題（共2小題，共計(jì)25分）1. （15分）參考算法如下：void merge(LinkNode *ha， LinkNode *hb， LinkNode *&hc)LinkNode *pa=ha->next，*pb=hb->next，*q;fre

11、e(hb);hc=ha; hc->next=NULL;/hc利用ha的頭結(jié)點(diǎn)，并設(shè)置為空while (pa!=NULL && pb!=NULL)/掃描ha、hb的數(shù)據(jù)結(jié)點(diǎn)if (pa->data<pb->data)/將較小結(jié)點(diǎn)采用頭插法插入到hc中q=pa->next;pa->next=hc->next;hc->next=pa;pa=q;elseq=pb->next;pb->next=hc->next;hc->next=pb;pb=q;if (pb!=NULL) pa=pb;while (pa!=NULL)/將沒有掃描完的結(jié)點(diǎn)采用頭插法插入到hc中q=pa->next;pa->next=hc->next;hc->next=pa;pa=q;評分說明：上述算法的時(shí)間復(fù)雜度為O(m+n)。若設(shè)計(jì)的算法時(shí)間復(fù)雜度為O(m*n)，至少扣3分，若設(shè)計(jì)的算法空間復(fù)雜度不為O(1)，扣2分。2、（10分）參考算法如下：int singleodes(BTNode *b)if (b=NULL) return 0; if (b->lchild=NULL && b->rchild!=NULL) |/單分支的結(jié)點(diǎn)(b->lchild!