824數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)A

本文格式為Word版，下載可任意編輯——824數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)A

XX科技大學(xué)

2023年碩士研究生入學(xué)考試試題A

─────────────────────────────────

科目編號(hào)：824科目名稱：數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)

考生須知：

1、答案必需寫(xiě)在答題紙上，寫(xiě)在試題或草稿紙上不給分。

2、答題須用藍(lán)、黑色鋼筆或圓珠筆，用鉛筆、紅色筆者不給分。3、答題必需寫(xiě)清題號(hào)，字跡要明白，卷面要保持整齊。4、試題要隨答題紙一起交回。

一、單項(xiàng)選擇題（每題2分，共30分）

（1）并歸排序的時(shí)間繁雜度是（）。

A．O(n2)B．O(nlog2n)C．O(n)D．O(log2n)

（2）設(shè)一個(gè)鏈表最常用的操作是在末尾插入結(jié)點(diǎn)和刪除尾結(jié)點(diǎn)，選用（）存儲(chǔ)結(jié)構(gòu)最節(jié)省時(shí)間。

A．單鏈表B．單循環(huán)鏈表C．帶尾指針的單循環(huán)鏈表D．帶頭結(jié)點(diǎn)的雙循環(huán)鏈表（3）散列文件是一種（）。

A．順序文件B．索引文件C．鏈接文件D．計(jì)算機(jī)尋址文件（4）常用于函數(shù)調(diào)用的數(shù)據(jù)結(jié)構(gòu)是（）。

A．棧B．隊(duì)列C．?dāng)?shù)組D．鏈表（5）兩個(gè)矩陣Ams,Bsn相乘的時(shí)間繁雜度是（）。

A．O(n2)B．O(s2)C．O(msn)D．O(mn)（6）圖的廣度優(yōu)先探尋遍歷使用的數(shù)據(jù)結(jié)構(gòu)是（）。

A．棧B．隊(duì)列C．集合D．樹(shù)

（7）在單鏈表中，每個(gè)存貯結(jié)點(diǎn)有兩個(gè)域，即數(shù)據(jù)域和指針域，指針域指向該結(jié)點(diǎn)的（）。A．直接前驅(qū)B．直接后繼C．開(kāi)始結(jié)點(diǎn)D．終端結(jié)點(diǎn)（8）在已知頭指針的單鏈表中，要在其尾部插入一個(gè)新結(jié)點(diǎn)，其時(shí)間繁雜度是（）。A．O(n2)B．O(1)C．O(n)D．O(log2n)（9）在鏈隊(duì)列中執(zhí)行入隊(duì)操作，（）。

A．需判斷隊(duì)是否為空B．限定在鏈表頭p進(jìn)行

C．需判斷隊(duì)是否為滿D．限定在鏈表尾p進(jìn)行

（10）對(duì)序列（95，83，62，70）進(jìn)行冒泡排序（由小到大），第2趟排序后的結(jié)果為（）。A．（70，83，62，95）B．（70，62，83，95）

共5頁(yè)第1頁(yè)

C．（62，70，83，95）D．（83，62，70，95）（11）以下選項(xiàng)中與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無(wú)關(guān)的術(shù)語(yǔ)是（）。

A．棧B．鏈隊(duì)列C．順序表D．鏈表

（12）已知循環(huán)隊(duì)列的存貯空間大小為m，對(duì)頭指針front指向?qū)︻^元素，對(duì)尾指針rear

指向?qū)ξ苍氐南乱粋€(gè)位置，則向?qū)α兄胁迦胄略貢r(shí)，修改指針的操作是（）。A．rear=（rear-1）％mB．rear=（rear+1）％m

C．front=（front-1）％mD．front=（front+1）％m（13）對(duì)于廣義表A，若head(A)=tail(A)，則A為（）。

A．(())B．()C．((),())D．((),(),())（14）若一棵具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)的先序遍歷和后序遍歷的次序正好相反，則該二叉樹(shù)應(yīng)是（）。

A．結(jié)點(diǎn)均無(wú)左孩子的二叉樹(shù)B．高度為n的二叉樹(shù)

C．結(jié)點(diǎn)均無(wú)右孩子的二叉樹(shù)D．存在度為2的結(jié)點(diǎn)的二叉樹(shù)（15）平均時(shí)間繁雜度為O(nlog2n)的穩(wěn)定排序算法是（）。

A．快速排序B．堆排序C．歸并排序D．冒泡排序

二、填空題（每題2分，共20分）

（1）數(shù)據(jù)結(jié)構(gòu)由數(shù)據(jù)的規(guī)律結(jié)構(gòu)、存貯結(jié)構(gòu)和數(shù)據(jù)的三部分組成。（2）廣義表A=(a,b,(c,d,(e,f)),G)的長(zhǎng)度為。

（3）以數(shù)據(jù)集{25,4,15,5,1}為權(quán)值構(gòu)造一棵哈夫曼樹(shù)，其帶權(quán)路徑長(zhǎng)度為。（4）在高度為h的具有n個(gè)結(jié)點(diǎn)的二叉排序樹(shù)中，查找任一結(jié)點(diǎn)的最多比較次數(shù)是。

（5）若某哈夫曼樹(shù)有m個(gè)葉子結(jié)點(diǎn)，則該哈夫曼樹(shù)共有個(gè)結(jié)點(diǎn)。

（6）向一個(gè)棧頂指針為top的鏈棧中插入一個(gè)新結(jié)點(diǎn)*p時(shí)，應(yīng)執(zhí)行p->next=top和操作。

（7）在隊(duì)列中，允許插入的一端稱為。

（8）在一棵二叉樹(shù)中，度為1的結(jié)點(diǎn)數(shù)是3，度為2的結(jié)點(diǎn)數(shù)是4，則該二叉樹(shù)有個(gè)葉子結(jié)點(diǎn)。

（9）具有n個(gè)頂點(diǎn)的連通無(wú)向圖，其生成樹(shù)有條邊。

（10）當(dāng)關(guān)鍵字序列基本有序時(shí)，快速排序、簡(jiǎn)單項(xiàng)選擇擇排序和直接插入排序三種排序算法

中，運(yùn)行效率最高的是。

共5頁(yè)第2頁(yè)

三、簡(jiǎn)答題（任選5道題，每題8分，共40分）

（1）什么是線性表？尋常有哪些存貯方式？其各自的優(yōu)缺點(diǎn)是什么？

（2）什么是順序隊(duì)列的“假溢出〞現(xiàn)象？有哪些處理方式？如何判斷隊(duì)滿和隊(duì)空？（3）什么是二叉樹(shù)的順序存儲(chǔ)方式？其優(yōu)缺點(diǎn)有哪些？（4）圖的存儲(chǔ)結(jié)構(gòu)有哪些？其各自的優(yōu)缺點(diǎn)是什么？（5）靜態(tài)查找有哪三種方法？各自的查找效率如何？

（6）什么樣的圖其最小生成樹(shù)是唯一的？用Prim和Kruskal算法求最小生成樹(shù)的時(shí)間繁雜度各為多少？他們分別適合于哪種類型的圖？

四、應(yīng)用題（每題10分，共40分）

（1）已知待排序記錄的關(guān)鍵字序列為{25,96,11,63,57,78,44}，請(qǐng)回復(fù)以下問(wèn)題：

（a）畫(huà)出堆排序的初始堆（大根堆）；（b）畫(huà)出第2次重建堆之后的堆。

（2）已知關(guān)鍵字序列為{56,23,41,79,38,62,18}，用散列函數(shù)H(key)=key％11將其散列到

散列表HT[0…10]中，采用線性探測(cè)法處理沖突，請(qǐng)回復(fù)以下問(wèn)題：（a）畫(huà)出散列存儲(chǔ)后的散列表；

（b）求在等概率下查找成功的平均查找長(zhǎng)度。

（3）已知某二叉排序樹(shù)（結(jié)點(diǎn)值大小按字母順序）的前序遍歷序列為EBACDFHG，請(qǐng)回復(fù)以下問(wèn)題：

（a）畫(huà)出此二叉排序樹(shù)；

（b）若將此二叉排序樹(shù)看作森林的二叉鏈表存儲(chǔ)，畫(huà)出對(duì)應(yīng)的森林。

（4）下圖所示是一帶權(quán)有向圖的鄰接表法存儲(chǔ)表示。其中出邊表中的每個(gè)結(jié)點(diǎn)均含有三個(gè)字段，依次為邊的另一個(gè)頂點(diǎn)在頂點(diǎn)表中的序號(hào)、邊上的權(quán)值和指向下一個(gè)邊結(jié)點(diǎn)的指針。請(qǐng)回復(fù)以下問(wèn)題：

（a）畫(huà)出該帶權(quán)有向圖的圖形；

（b）從頂點(diǎn)V1為起點(diǎn)的廣度優(yōu)先遍歷的頂點(diǎn)序列及對(duì)應(yīng)的生成樹(shù)；（c）以頂點(diǎn)V1為起點(diǎn)的深度優(yōu)先遍歷的頂點(diǎn)序列及對(duì)應(yīng)的生成樹(shù)；（d）由頂點(diǎn)V1到頂點(diǎn)V3的最短路徑。

(頂點(diǎn)邊)1V12V23V3?4V45V56V6?230110338618?542?233336?（出邊表）429625?共5頁(yè)第3頁(yè)

五、算法設(shè)計(jì)題（任選2題，每題10分，共20分）

（1）假定二叉樹(shù)結(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu)定義如下：typedefstructnode

{chardata；

structnode*lchild；structnode*rchild；}NODE；

試編寫(xiě)C（或Java）語(yǔ)言函數(shù)voidexchange(NODE*t)，其功能是交換二叉樹(shù)的各

結(jié)點(diǎn)的左右子樹(shù)（根結(jié)點(diǎn)指針為t）。

（2）以二叉鏈表為存儲(chǔ)結(jié)構(gòu)，編寫(xiě)按層次順序（同一層自左至右）遍歷二叉樹(shù)的算法。（3）給定頭指針為ha的單鏈表A，和頭指針為hb的遞增有序單鏈表B。試?yán)帽鞟和

表B的結(jié)點(diǎn)，將表A和表B歸并為遞增有序單鏈表C，其頭指針為hc（允許有一致的data值，表A、B、C均帶有頭結(jié)點(diǎn)）。

閱讀下面的函數(shù)merge（），請(qǐng)給有下劃線的位置填空，使之成為完整的算法（程序）。表結(jié)點(diǎn)的類型定義如下：

structnode{intdata;

structnode*next;};C語(yǔ)言算法如下：

voidmerge(structnode*ha,structnode*hb,structnode*hc){

structnode*pc,*qc,*pa,*fa;intsearch;hc=hb;hb=NULL;pa=ha->next;free(ha);while(pa){pc=hc;qc=hc->next;

search=1;//設(shè)置查找標(biāo)志while(