824數(shù)據(jù)結(jié)構與算法設計A

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

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

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

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

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

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

7、2233429625336V612（出邊表）3V34 V42303385425 V51106186五、算法設計題（任選 2 題，每小題 10 分，共 20 分）假定二叉樹結(jié)點的存儲結(jié)構定義如下：typedefstructnodechardata；structnode*lchild； structnodeNODE；試編寫或Java）語言函數(shù)voidexchange(NODE *t 其功能是交換二叉樹的結(jié)點的左右子樹（根結(jié)點指針為。以二叉鏈表為存儲結(jié)構，編寫按層次順序（同一層自左至右）遍歷二叉樹的算法。haAhbA和B的結(jié)點，將表A B C，其頭指針為dataABC均帶有頭結(jié)點。閱讀下面的函數(shù)merg（程序表結(jié)點的類型定義如下：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