數(shù)據(jù)結(jié)構(gòu)模擬試題答案

1、?數(shù)據(jù)結(jié)構(gòu)?模擬試題、單項(xiàng)選擇題(30分)1在數(shù)據(jù)結(jié)構(gòu)的討論中把數(shù)據(jù)結(jié)構(gòu)從邏輯上分為CA. 內(nèi)部結(jié)構(gòu)與外部結(jié)構(gòu)B. 靜態(tài)結(jié)構(gòu)與動(dòng)態(tài)結(jié)構(gòu)C. 線性結(jié)構(gòu)與非線性結(jié)構(gòu)D. 緊湊結(jié)構(gòu)與非緊湊結(jié)構(gòu)?？勺x性和文檔性空間復(fù)雜性和時(shí)間復(fù)雜性2 算法分析的兩個(gè)主要方面是_ D_ 。A. 正確性和簡(jiǎn)明性B.C.數(shù)據(jù)復(fù)雜性和程序復(fù)雜性D.3 在存儲(chǔ)數(shù)據(jù)時(shí)，通常不僅要存儲(chǔ)各數(shù)據(jù)元素的值，而且還要存儲(chǔ)A.數(shù)據(jù)的處理方法B. 數(shù)據(jù)元素的類型C. 數(shù)據(jù)元素之間的關(guān)系D. 數(shù)據(jù)的存儲(chǔ)方法4. 設(shè)順序表有9個(gè)元素，那么在第3個(gè)元素前插入一個(gè)元素所需移動(dòng)元素的個(gè)數(shù)為cA.5B.6C.7D.95. 線性表采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要求內(nèi)

2、存中可用存儲(chǔ)單元的地址d_。A.必須是連續(xù)的B.必須是局部連續(xù)的C. 一定是不連續(xù)的D.連續(xù)和不連續(xù)都可以6. 對(duì)具有n個(gè)結(jié)點(diǎn)的線性表進(jìn)行插入和刪除操作，所需的算法時(shí)間復(fù)雜度為 d2A. O(1)B. 0(n) C. 0( nlog2n)D. O(n )7. 在單鏈表中指針p所指結(jié)點(diǎn)之后插入指針為s的結(jié)點(diǎn)，正確的操作是 _b。A. p->n ext=s;s->n ext= p->n ext;B. s->n ext= p->n ext; p->n ext=s;C. p->n ext=s; p->next=s->nextD. p->n e

3、xt=s->n ext; p->n ext=s;8.棧中兀素的進(jìn)出原那么是b。A.先進(jìn)先出B .先進(jìn)后出C.?？漳敲催M(jìn)D .棧滿那么出9 .長(zhǎng)度是n的順序循環(huán)隊(duì)列，front和 rear分別指示隊(duì)首和隊(duì)尾，判斷隊(duì)列為滿隊(duì)列的條件是dA . rear=0B.front=0C. rear=frontD.(rear+1 ) %n=front10.下面說法不正確的選項(xiàng)是c。A.廣義表的表頭總是個(gè)廣義表B .廣義表的表尾總是一個(gè)廣義表C .廣義表難以用順序存儲(chǔ)結(jié)構(gòu)D 廣義表可以是一個(gè)多層次的結(jié)構(gòu)11二叉樹的先序遍歷序列為ABCD中序遍歷序列為 BCDA那么后序遍歷序列為A. ABCD B .

4、 BCDAC. CDBAD. DCBA12 .一棵含50個(gè)結(jié)點(diǎn)的二叉樹中只有一個(gè)葉子結(jié)點(diǎn)，該二叉樹中度為1的結(jié)點(diǎn)個(gè)數(shù)為d。A. 0 B. 1C. 48D. 4913折半查找有序表2,5,20, 25,36, 40, 60),假設(shè)查找元素 60,需依次與表中元素進(jìn)行比擬。A. 20, 36, 40,60.25, 40C. 25, 40, 60.20, 36, 4014.在有向圖的鄰接表存儲(chǔ)表示中,頂點(diǎn)V在鏈表結(jié)點(diǎn)中出現(xiàn)的次數(shù)是A.頂點(diǎn)V的入度B.頂點(diǎn)V的出度C.頂點(diǎn)V的度D.依附于頂點(diǎn) V的邊的數(shù)目15.對(duì)關(guān)鍵字序列5,8, 6進(jìn)行快速排序時(shí),以第一個(gè)元素5為基準(zhǔn)的一次劃分的結(jié)果為A. (1,

5、2, 3, 4,5,8)B. (1, 4, 3,2,5, 7, 8, 6)C. (2, 1, 4, 3, 5, 7, 8, 6)D . (8, 7, 6,5,4, 3, 2, 1)二、填空題20分1.數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的物理結(jié)構(gòu)、數(shù)據(jù)的邏輯結(jié)構(gòu)和數(shù)據(jù)的運(yùn)算這三個(gè)方面的內(nèi)容。2. 一個(gè)算法的時(shí)間復(fù)雜度為3n3+2n 7，其數(shù)量級(jí)表示為 0 n? 。3. 線性結(jié)構(gòu)中元素之間存在一對(duì)一關(guān)系，樹形結(jié)構(gòu)中元素之間存在一對(duì)多關(guān)系，圖形結(jié)構(gòu)中元素之間存在 多對(duì)多關(guān)系。4. 順序表中邏輯上相鄰的元素的物理位置 也相鄰或一定相鄰。單鏈表中邏輯上相鄰的元素的物理位置不一定相鄰。5. 棧中允許刪除元素的一端稱為棧頂；

6、隊(duì)列中，允許刪除元素的一端稱為隊(duì)頭6. 廣義表a,b,c,d的表頭是a 表尾是b,c,d 。7. 深度為5的滿二叉樹共有31個(gè)結(jié)點(diǎn)，其中有16個(gè)葉子節(jié)點(diǎn)。36&用4個(gè)權(quán)值9, 2, 3, 6構(gòu)造的哈夫曼樹的帶權(quán)路徑長(zhǎng)度是9在有向圖的鄰接矩陣中，第i行中非零元素的個(gè)數(shù)正好是第i個(gè)頂點(diǎn)的 _出度;第i列中非零元素的個(gè)數(shù)正好是第i個(gè)頂點(diǎn)的 入度。10 折半查找法中要求線性表必須采用 順序存儲(chǔ)結(jié)構(gòu)，且表中元素必須 有序。11 快速排序在平均情況下的時(shí)間復(fù)雜度為_O (nlog 2n),在最環(huán)情況下的時(shí)間復(fù)雜度為_o(n2) _。三、判斷題(對(duì)的打，錯(cuò)的打 )(10分)()1.數(shù)據(jù)元素是數(shù)據(jù)處理

7、的最小單位。()2.線性表的順序存儲(chǔ)結(jié)構(gòu)優(yōu)于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。()3.棧的特點(diǎn)是先進(jìn)后出，隊(duì)列的特點(diǎn)是先進(jìn)先出。()4.串中任意個(gè)字符組成的子序列稱為該串的子串。()5.樹型結(jié)構(gòu)中每個(gè)結(jié)點(diǎn)都有一個(gè)直接前趨。()6.滿二叉樹中存在度為 1的結(jié)點(diǎn)。()7. 一棵哈夫曼樹有m個(gè)葉子結(jié)點(diǎn)，那么其結(jié)點(diǎn)總數(shù)為 2m-1。()8.在有向圖中每個(gè)頂點(diǎn)的度等于該頂點(diǎn)的入度與出度之和。()9.有向圖是一種非線性結(jié)構(gòu)。()10.折半查找方法適用于按值有序的線性鏈表的查找。四、簡(jiǎn)答題(30分)1 對(duì)于一個(gè)棧，如果輸入項(xiàng)序列由A、B、C組成，試給出全部可能的輸出序列。5分答：根據(jù)棧的操作特點(diǎn)是后進(jìn)先出,因此輸出序列有：1

8、A入，A入，B出，C出,輸出序列為ABC;入，A入，C入，C出,輸出序列為ACB;出，C輸出序列為BAC;輸出序列為BCA;輸出序列為出，B出，A出,入, B入, C入，CCBA;A5分先序：RADEBCFGHI 中序：DEABGHIFCR 后序：EDIHGFCBAR3對(duì)如下有向圖，要求：(7分)(1) 寫出該圖中每個(gè)頂點(diǎn)的度、出度、入度頂點(diǎn)1:度為3，出度為1,入度為2頂點(diǎn)2：度為4,出度1，入度3頂點(diǎn)3：度為3,出度為2,入度為1頂點(diǎn)4：度為4,出度為2,入度為2頂點(diǎn)5:度為3,出度為2,入度為1頂點(diǎn)6：度為5,出度為3,入度為2(2) 畫出該圖的鄰接表；該圖的鄰接表如下列圖所示：11十3

9、4560(3) 根據(jù)鄰接表，分別寫出從頂點(diǎn)1出發(fā)進(jìn)行深度優(yōu)先和廣度優(yōu)先搜索得到的頂點(diǎn)序列。深度優(yōu)先序列：1-2-4-3-6-5廣度優(yōu)先序列：1-2-4-3-6-54. 5分從空樹起，依次插入關(guān)鍵字8, 12, 5, 7, 9, 1, 13 ,10,構(gòu)造一棵二叉排序樹。1畫出該二叉排序樹;(2)畫出從1所得樹中插入關(guān)鍵字為6的結(jié)點(diǎn)之后的二叉排序樹。插入后6應(yīng)該是7的左子樹(3)畫出從首先中序遍歷二叉排序樹得到一個(gè)線性有序序列:(1 , 5, 6, 7, 8, 9, 10, 12, 13),在這個(gè)序列中，10就是12的直接前趨，然后用 12的直接前趨10代替12 ,再把12的直接前趨10刪除即可8

10、576139105. ( 8分)一組數(shù)值序列為(50, 47, 65, 33, 41, 26, 71, 56)，請(qǐng)完成下面的各項(xiàng)操作：(1) 采用直接插入排序法對(duì)該組序列作升序排序，并給出每一趟的排序結(jié)果。(2) 采用冒泡排序法對(duì)該組序列作升序排序，并給出每一趟的排序結(jié)果。(3) 采用快速排序法對(duì)該組序列作升序排序，并給出每一趟的排序結(jié)果。直接插入排序：47,50,65,33,41,26,71,56這是第一趟的排序結(jié)果。要求給出每一趟的排序結(jié)果？正確的方法如下：(1)直接插入排序：50 , 47, 65, 33, 41, 26, 71, 56初始序列：50, 47, 65, 33, 41 ,

11、26, 71, 56第一趟：47, 50,65,33,41,26,71,56第二趟：47,50,65 ,33,41,26,71,56第三趟：33,47,50,65 ,41,26,71,56第四趟：33,41,47,50,65,26,71,56第五趟：26,33,41,47,50,65,71,56第六趟：26,33,41,47,50,65,71,56第七趟：26,33,41,47,50,56,65,71下面兩種排序按上面的方法完成冒泡排序：50, 47, 65, 33, 41 , 26, 71, 56第趟：47,50,33,41,26,65,56,71第二趟：47,33,41,26,50,56,

12、65,71第三趟：33,41,26,47,50,56,65,71第四趟：33,26,41,47,50,56,65,71第五趟：26,33,41,47,50,56,65,71第八趟：26,33,41,47,50,56,65,71第七趟：26,33,41,47,50,56,65,71快速排序：50, 47, 65, 33, 41 , 26, 71, 56第一趟：26, 47, 41, 33,型,65, 71, 56第二趟：26, 47, 41, 33第三趟：33, 41, 47第四趟：33 ，41第五趟：56, 65 71第六趟：26 , 33, 41, 47, 50, 56, 65, 71x的新

13、元素。五、算法填空題(10分)1 以下算法的功能是在順序表中第i個(gè)位置上插入一個(gè)值為順序表的類型描述：#define MAXSIZE 20typedef struct int dataMAXSIZE;int len gth ;SeqList;算法：int Insert_Seqlist(SeqList *L,int i,int x)int j;if (_L->length>=MAXSIZE-1 ) printf("表滿！ ); return (-1); if ( i<1|i>L-> length +1) printf("插入位置錯(cuò)！ )； return (0); for (j= L->length ； j>=i-1； j-) L_>dataj+1=L_>datajl;L->datai-1=x;_L->Le ngth+ ;return (1);2 以下是先序遍歷二叉樹的遞歸算法。二叉樹的二叉鏈表