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

1、共 5共 5頁第5頁西安科技大學(xué)2013 年碩士研究生入學(xué)考試試題 A科目編號：824科目名稱： 數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)考生須知：1、 答案必須寫在答題紙上，寫在試題或草稿紙上不給分。2、 答題須用藍(lán)、黑色鋼筆或圓珠筆，用鉛筆、紅色筆者不給分。3、 答題必須寫清題號，字跡要清楚，卷面要保持整潔。4、 試題要隨答題紙一起交回。一、單項(xiàng)選擇題（每小題 2 分，共 30 分）并歸排序的時(shí)間復(fù)雜度是（。AO(n2)BO(nlog2n)CO(n)DO(log2n)設(shè)一個(gè)鏈表最常用的操作是在末尾插入結(jié)點(diǎn)和刪除尾結(jié)點(diǎn)，選用（）省時(shí)間。A單鏈表B單循環(huán)鏈表C帶尾指針的單循環(huán)鏈表D帶頭結(jié)點(diǎn)的雙循環(huán)鏈表散列文件是一種

2、（。A順序文件B索引文件C鏈接文件D計(jì)算機(jī)尋址文件常用于函數(shù)調(diào)用的數(shù)據(jù)結(jié)構(gòu)是（。A棧B隊(duì)列C數(shù)組D鏈表兩個(gè)矩陣A,Bmssn相乘的時(shí)間復(fù)雜度是（ 。AO(n2)BO(s2)CO(msn)DO(mn)圖的廣度優(yōu)先搜索遍歷使用的數(shù)據(jù)結(jié)構(gòu)是（。A棧B隊(duì)列C集合D樹（ 。A直接前驅(qū)B直接后繼C開始結(jié)點(diǎn)D終端結(jié)點(diǎn)在已知頭指針的單鏈表中，要在其尾部插入一個(gè)新結(jié)點(diǎn)，其時(shí)間復(fù)雜度是（。AO(n2)BO(1)CO(n)DO(log2n)在鏈隊(duì)列中執(zhí)行入隊(duì)操作（ 。A需判斷隊(duì)是否為空B限定在鏈表頭p進(jìn)行C需判斷隊(duì)是否為滿D限定在鏈表尾p進(jìn)行對序進(jìn)行冒泡排（由小到大第2趟排序后的結(jié)果（ A（7，8，6，9）B768

3、，9）C6270839）D8367095）下列選項(xiàng)中與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)的術(shù)語是（。A棧B鏈隊(duì)列C順序表D鏈表已知循環(huán)隊(duì)列的存貯空間大小為對頭指針front指向?qū)︻^元素，對尾指針rear 指向?qū)ξ苍氐南乱粋€(gè)位置，則向?qū)α兄胁迦胄略貢r(shí)，修改指針的操作是（ 。Arear=（rear-1）mBrear=（rear+1）mCfront=（front-1）mDfront=（front+1）mAhead(A)=tail(A)A為（。A()B()C(),()D( ),( ),()n 應(yīng)是（。A結(jié)點(diǎn)均無左孩子的二叉樹B高度為 n 的二叉樹 C結(jié)點(diǎn)均無右孩子的二叉樹D存在度為2的結(jié)點(diǎn)的二叉的穩(wěn)定排序算法是（

4、。A快速排序B堆排序C歸并排序D冒泡排序二、填空題（每小題 2 分，共 20 分）數(shù)據(jù)結(jié)構(gòu)由數(shù)據(jù)的邏輯結(jié)構(gòu)、存貯結(jié)構(gòu)和數(shù)據(jù)的三部分組成。廣義表A=(a,b,(c,d,(e,f),的長度為。以數(shù)據(jù)25,4,15,5,1為權(quán)值構(gòu)造一棵哈夫曼樹，其帶權(quán)路徑長度為。在高度為h 的具有 n 個(gè)結(jié)點(diǎn)的二叉排序樹中，查找任一結(jié)點(diǎn)的最多比較次是。若某哈夫曼樹有m 個(gè)葉子結(jié)點(diǎn)，則該哈夫曼樹共有個(gè)結(jié)點(diǎn)。向一個(gè)棧頂指針為top的鏈棧中插入一個(gè)新結(jié)*p時(shí)應(yīng)執(zhí)行p-next=top和作。在隊(duì)列中，允許插入的一端稱為。在一棵二叉樹中度為1的結(jié)點(diǎn)數(shù)是3度為2的結(jié)點(diǎn)數(shù)是則該二叉樹有葉子結(jié)點(diǎn)。具有n 個(gè)頂點(diǎn)的連通無向圖，其生成

5、樹有條邊。當(dāng)關(guān)鍵字序列基本有序時(shí)快速排序簡單選擇排序和直接插入排序三種排序算 中，運(yùn)行效率最高的是。三、簡答題（任選 5 道題，每小題 8 分，共 40 分）什么是線性表？通常有哪些存貯方式？其各自的優(yōu)缺點(diǎn)是什么？什么是順序隊(duì)列的“假溢出”現(xiàn)象？有哪些處理方式？如何判斷隊(duì)滿和隊(duì)空？什么是二叉樹的順序存儲方式？其優(yōu)缺點(diǎn)有哪些？圖的存儲結(jié)構(gòu)有哪些？其各自的優(yōu)缺點(diǎn)是什么？靜態(tài)查找有哪三種方法？各自的查找效率如何？什么樣的圖其最小生成樹是唯一的？用PrimKruskal雜度各為多少？他們分別適合于哪種類型的圖？四、應(yīng)用題（每小題 10 分，共 40 分）（1）25,96,11,63,57,78,44，

6、請回答下列問題：畫出堆排序的初始堆（大根堆；2次重建堆之后的堆。（2）56,23,41,79,38,62,18H(key)=key11 HT010中，采用線性探測法處理沖突，請回答下列問題：畫出散列存儲后的散列表；求在等概率下查找成功的平均查找長度。已知某二叉排序樹（結(jié)點(diǎn)值大小按字母順序）的前序遍歷序列為 EBACDFHG回答下列問題：畫出此二叉排序樹；若將此二叉排序樹看作森林的二叉鏈表存儲，畫出對應(yīng)的森林。針。請回答下列問題：畫出該帶權(quán)有向圖的圖形；V1 為起點(diǎn)的廣度優(yōu)先遍歷的頂點(diǎn)序列及對應(yīng)的生成樹；V1 為起點(diǎn)的深度優(yōu)先遍歷的頂點(diǎn)序列及對應(yīng)的生成樹；V1V3的最短路徑。V1V2233V1V

7、2233429625336V612（出邊表）3V34 V42303385425 V51106186五、算法設(shè)計(jì)題（任選 2 題，每小題 10 分，共 20 分）假定二叉樹結(jié)點(diǎn)的存儲結(jié)構(gòu)定義如下：typedefstructnodechardata；structnode*lchild； structnodeNODE；試編寫或Java）語言函數(shù)voidexchange(NODE *t 其功能是交換二叉樹的結(jié)點(diǎn)的左右子樹（根結(jié)點(diǎn)指針為。以二叉鏈表為存儲結(jié)構(gòu)，編寫按層次順序（同一層自左至右）遍歷二叉樹的算法。haAhbA和B的結(jié)點(diǎn)，將表A B C，其頭指針為dataABC均帶有頭結(jié)點(diǎn)。閱讀下面的函數(shù)merg（程序表結(jié)點(diǎn)的類型定義如下：struct node int data;struct node *next; ;C 語言算法如下：void merge(struct node *ha, struct node *hb, struct node *hc)structnode*pc,*qc,*pa,intsearch;hc=hb; hb=NULL;pa=ha-nex