2018年山東工商學(xué)院算法與數(shù)據(jù)結(jié)構(gòu)考研真題B卷

2018年山東工商學(xué)院算法與數(shù)據(jù)結(jié)構(gòu)考研真題B卷一、簡答題（共6題，每題10分）1.基本的數(shù)據(jù)結(jié)構(gòu)有哪幾類?簡述其邏輯特點(diǎn)。對于社交網(wǎng)站中處理的數(shù)據(jù)應(yīng)該選擇什么數(shù)據(jù)結(jié)構(gòu)?給出你的理由。2.比較棧和隊(duì)列兩種數(shù)據(jù)結(jié)構(gòu)的異同，舉例說明哪些算法中會用到?；蛘哧?duì)列。3.若線性表中元素總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除，但要求以最快的速度存取線性表中的元素，那么應(yīng)采用哪種存儲結(jié)構(gòu)?為什么?4.具有1000個結(jié)點(diǎn)的完全二叉樹有多少個葉子結(jié)點(diǎn)?寫出推導(dǎo)過程。5.設(shè)A[0.，9，0..9]是10階對稱矩陣，若采用壓縮存儲的方式存儲其下三角矩陣，以行序?yàn)橹餍颍總€元素占2個單元，矩陣第一個元素A[0，0]的地址是1000，A[4，5]的地址是多少?寫出計(jì)算過程。6.什么是A0V網(wǎng)?什么是AOE網(wǎng)?分析二者的異同點(diǎn)，分別有什么應(yīng)用?二、綜合應(yīng)用題（共7題，每題10分）1.請寫出如圖1所示的二叉樹的先序遍歷和中序遍歷序列，并將其轉(zhuǎn)換成樹或者森林。2.設(shè)有無向圖G如下圖所示∶（1）請畫出圖G的鄰接矩陣和鄰接表。（2）并在（1）所畫的鄰接表的基礎(chǔ)上，寫出從頂點(diǎn)1出發(fā)的深度優(yōu)先遍歷和廣度優(yōu)先遍歷序列。（3）簡述深度優(yōu)先算法和廣度優(yōu)先算法的不同點(diǎn)。3.設(shè)有無向圖G（如圖3），（1）簡述普里姆（prim）算法的基本思想。（2）請按普里姆算法從頂點(diǎn)v1開始構(gòu)造最小生成樹。請寫出并入邊的次序。4.已知某系統(tǒng)在通信聯(lián)絡(luò)中出現(xiàn)的字符為{a，b，c，d，e，f，g，h}，其概率分別為{0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10}。要求∶（1）簡述構(gòu)造Huffman樹的算法思想。（2）樹畫出對應(yīng)的Huffman樹，計(jì)算加權(quán)路徑長度WPL。（3）寫出每個字符的哈夫曼編碼。5.已知一組關(guān)鍵字序列{38，23，7，79，9，45，3，19，30，62，23*，47}，要實(shí)現(xiàn)非遞減有序排列，請完成如下操作∶（1）冒泡排序，寫出第1、2趟排序結(jié)果。（2）快速排序（選第一個記錄為樞軸），寫出第1趟快速排序的結(jié)果。（3）分析冒泡排序和快速排序算法的異同。6.如圖4所示的是一個具有11個活動（al，…，al1）的某個工程的AOE網(wǎng)，頂點(diǎn)V1表示工程開始，頂點(diǎn)V9表示工程結(jié)束，邊上的權(quán)值表示活動所需的時間。（1）計(jì)算各頂點(diǎn)事件的最早和最遲發(fā)生時間。（2）計(jì)算各活動的最早和最遲開始時間。（3）求關(guān)鍵活動和關(guān)鍵路徑。7.設(shè)數(shù)據(jù)集合D=2，28，15.18，10，20，17，35，19}試完成下列各題∶（1）什么是二叉排序?依次取D中各數(shù)據(jù)，構(gòu)造一棵二叉排序樹T。（2）如何依據(jù)此二叉樹T得到D的一個有序序列。（3）畫出在二叉樹T中刪除"28"后的樹結(jié)構(gòu)。三、算法題（共2題，每題10分）1.設(shè)有兩個棧sl，s2都采用順序棧方式，并且共享一個存儲區(qū)data[0..MAXSIZE-1]，為了盡量利用空間，減少溢出的可能，可采用棧頂相向，迎面增長的存儲方式。請編寫s1，s2的入棧、出棧的操作算法。（1）采用C或C++，寫出該棧的數(shù)據(jù)類型定義;（2）采用C或C++描述算法，關(guān)鍵之處做出注釋。2.二叉排序樹采用二叉鏈表存儲，結(jié)點(diǎn)結(jié)構(gòu)為[Lchild|key|factor|Rchild]，其中key為char類型關(guān)鍵字，factor為結(jié)點(diǎn)的平衡因子，Lchild和Rchild分別是左、右孩子指針。編寫算法計(jì)算并輸出每個結(jié)點(diǎn)的平衡