南京經(jīng)濟(jì)學(xué)院

1、PAGE PAGE 11 第 頁 共8頁南 京 財 經(jīng)經(jīng) 大 學(xué)2008年攻讀讀碩士學(xué)位研究生入入學(xué)考試（初初試）試卷考試科目： 819數(shù)據(jù)結(jié)結(jié)構(gòu)與單片機(jī)機(jī) 適用專業(yè)： 計算機(jī)應(yīng)用用技術(shù) 考試時間： 2008年年1月20日下午2:005:00 注意事項： 所有答案必必須寫在答題題紙上，做在在試卷或草稿稿紙上無效。第一部分：數(shù)據(jù)據(jù)結(jié)構(gòu)部分試試題（本部分共三大大題，共計775分）一、簡答題（共共15題，每每題1分，共共計15分）1已知一有向向圖的鄰接表表存儲結(jié)構(gòu)如如下圖所示。根根據(jù)有向圖的的深度優(yōu)先遍遍歷算法，從從頂點v1出發(fā)，所所得到的頂點點序列為何？根據(jù)有向圖圖的廣度優(yōu)先先遍歷算法，從從頂點v

2、1出發(fā)，所所得到的頂點點序列又為何何？2. 如果最常常用的操作是是取第i個結(jié)結(jié)點及其前驅(qū)驅(qū)，則采用單單鏈表、雙鏈表、順序表還是單循環(huán)鏈鏈表這四種存儲方方式中的哪一一種最節(jié)省時時間？3. 已知一個個圖如下圖所所示，若從頂頂點a出發(fā)，則在在以下四種頂頂點序列中，哪哪一種是按照照深度優(yōu)先搜搜索法進(jìn)行遍遍歷時可能得得到的序列？為什么？ A. a, b, e, dd, c, f B. a, bb, c, e, f, dC. a, e, dd, f, c, b D. a, e, bb, d, c, f4. 向一個棧棧頂指針為HH的鏈棧中插插入一個s所指的結(jié)點時，應(yīng)該該執(zhí)行什么樣的的運(yùn)算？5試圖在一個個循環(huán)

3、順序隊隊列中插入一一個元素，需需要判斷該隊列是否已滿。問這與隊頭頭指針的值還還是與隊尾指指針的值有關(guān)關(guān)？6數(shù)組元素之之間的關(guān)系是是線性的嗎？是樹形的嗎嗎？7若一個有向向圖的鄰接距距陣中對角線線以下的元素素均為零，則則該圖是否存在拓?fù)鋼溆行蛐蛄校?采用鄰接表表存儲的圖的的深度優(yōu)先遍遍歷算法類似似于二叉樹的的哪種遍歷？9. 廣義表 (a,b,(c,d) 的表頭、表尾尾是什么？10. 樹最適適合用來表示示何種數(shù)據(jù)？11若廣義表表A=(a,b,(c,d),(ee,(f,gg)，則則 headd( taiil( heead( ttail( tail( A) ) ) ) ) = ?12. 樹的基基本遍歷策

4、略略可分為先根根遍歷和后根根遍歷；二叉叉樹的基本遍遍歷策略可分分為先序遍歷歷、中序遍歷歷和后序遍歷歷。這里，我我們把由樹轉(zhuǎn)轉(zhuǎn)化得到的二二叉樹叫做這這棵樹對應(yīng)的的二叉樹。問問樹的先根遍遍歷序列與其其對應(yīng)的二叉叉樹的何種遍遍歷序列相同同？13. 在一非非空二叉樹的的中序遍歷序序列中，根結(jié)結(jié)點的左、右右邊各有哪些些結(jié)點？14在對線性性表進(jìn)行折半半查找時，對對線性表本身身有何要求？15. 一棵二二叉樹如圖所所示，其中序序遍歷的序列列為何？二、解析題（共共題，每題題6分，共計計36分）1請對下面的的無向帶權(quán)圖圖，寫出它的的鄰接表，并并按克魯斯卡卡爾算法求其其最小生成樹樹。2分別畫出和和下列樹對應(yīng)應(yīng)的各個

5、二叉叉樹：3簡述以下算算法的功能（棧棧的元素類型型SElemmType為為int）。Status algo11(Stacck S) int ii, n, A2555; n=0; whilee(!StaackEmppty(S) n+; Pop(S, An ) ; for(ii=1; ii=n; i+) Push(S, Ai ) ;4令u = abcaaabbabbcabaaacbacbba 試分別求求出它們的nnext函數(shù)數(shù)值和nexxtval函函數(shù)值。5已知下面的的有向圖，請請給出該圖的的（1）逆鄰接表表；（2）強(qiáng)連通分分量。6已知下圖為為廣義表存儲儲結(jié)構(gòu)圖，其其中表結(jié)點為為 tag=1 |

6、hhp | ttp ，原子結(jié)點點結(jié)構(gòu)為 ttag=0 | atoom 。寫出出如圖表示的的廣義表。三、算法題（共共3題，每題題8分，共計計24分）1假設(shè)以兩個個元素依值遞遞增有序排列列的線性表AA和B分別表示兩兩個集合（即即同一表中的的元素值各不不相同），現(xiàn)現(xiàn)要求另辟空空間構(gòu)成一個個線性表C，其元素為為A和B中元素的交交集，且表CC中的元素也也依值遞增有有序排列。試試對順序表編編寫求C的算法。2 編寫遞歸歸算法，從大大到小輸出給給定二叉樹中中所有關(guān)鍵字字不小于x的的數(shù)據(jù)元素。要要求算法的時時間復(fù)雜度為為O(logg2n+m)，其其中n為排序序樹中所含結(jié)結(jié)點數(shù)，m為為輸出的關(guān)鍵鍵字個數(shù)。3試寫出

7、一趟趟快速排序（一一次劃分）的的算法。即交交換順序表的的子表Rllow.highh中的記錄錄，使樞軸記記錄到位，并并返回其所在在位置，此時時在它前面的的記錄均不大大于它，在它它后面的記錄錄均不小于它它。第二部分：單片片機(jī)部分試題題（本部分共五大大題，共計775分）四、簡答題（共共6小題，每每小題5分，共共30分） 1、80CC51系列單單片機(jī)在片內(nèi)內(nèi)集成了哪些些主要邏輯功功能部件?簡簡述各個部件件的主要功能能?2、80C511單片機(jī)RAAM和ROMM的地址空間間分別是多少少？訪問RAAM和ROMM的指令有何何區(qū)別？請舉舉例加以說明明。 3、80CC51單片機(jī)機(jī)的指令周期期、機(jī)器周期期、時鐘 (

8、晶體振蕩器器) 周期的關(guān)系系如何?當(dāng)主主頻為12 MHz時，11個機(jī)器周期期等于多少s？執(zhí)行一一條最長的指指令需多少s？4、80C551單片機(jī)內(nèi)內(nèi)部有幾個定定時器計數(shù)數(shù)器? 有幾幾種工作方式式? 作定時時用時，定時時間與與哪些因素有有關(guān)? 舉例例說明。5、什么是中中斷？80C51有有幾個中斷源源？其中斷入入口地址各是是多少？ 6、某800C51串行接口口，采用幀格式為：一一個起始位,八個數(shù)據(jù)位、一個個停止位，其工作方方式為哪種？已知每秒鐘傳送96000個字符，傳送送波特率是多多少。五、閱讀下列程程序段，寫出出整個程序段段的功能（119分） MOV A,#555H MOV R00，#20H MOV R1，#4LOOP：MOOV R0，A INC R0 CPL A DJNZZ R1，LOOPP RET六 、編程（1112分）已知80C511單片機(jī)時鐘鐘(晶體振蕩器器)頻率為66 MHz，編程使P1.0輸出周期為1 ms的方波。要求用定時器T1、工作方式2定時、中斷方式工作，說明其控制字；定時常數(shù)。七、電路分析（1112分） 下圖為為某80C51單單片機(jī)片外擴(kuò)擴(kuò)展存儲器的的電路，分析析回答：圖中芯片A、芯芯片B分別是是程序存儲器器還是數(shù)據(jù)存存儲器。芯片A、B的地地址范圍分別別是多少？芯