1、 4/42021年西安電子科技大學(xué)數(shù)據(jù)結(jié)構(gòu)考研復(fù)試核心題庫(kù)之算法設(shè)計(jì)題精編 特別說明 本書根據(jù)最新復(fù)試要求并結(jié)合歷年復(fù)試經(jīng)驗(yàn)對(duì)該題型進(jìn)行了整理編寫，涵蓋了這一復(fù)試科目該題型?？技爸攸c(diǎn)復(fù)試試題并給出了參考答案，針對(duì)性強(qiáng)，由于復(fù)試復(fù)習(xí)時(shí)間短，時(shí)間緊張建議直接背誦記憶，考研復(fù)試首選資料。 版權(quán)聲明 青島掌心博閱電子書依法對(duì)本書享有專有著作權(quán)，同時(shí)我們尊重知識(shí)產(chǎn)權(quán)，對(duì)本電子書部分內(nèi)容參考和引用的市面上已出版或發(fā)行圖書及來自互聯(lián)網(wǎng)等資料的文字、圖片、表格數(shù)據(jù)等資料，均要求注明和來源。但由于各種原因，如資料引用時(shí)未能聯(lián)系上或者無法確認(rèn)內(nèi)容來源等，因而有部分未注明或來源，在此對(duì)原或權(quán)利人表示感謝。若使用過程

2、中對(duì)本書有任何異議請(qǐng)直接聯(lián)系我們，我們會(huì)在第一時(shí)間與您溝通處理。 因編撰此電子書屬于首次，加之水平和時(shí)間所限，書中錯(cuò)漏之處在所難免，懇切希望廣大考生讀者批評(píng)指正。 重要提示 本書由本機(jī)構(gòu)編寫組多位高分在讀研究生按照考試大綱、真題、指定參考書等公開信息潛心整理編寫，僅供考研復(fù)試復(fù)習(xí)參考，與目標(biāo)學(xué)校及研究生院官方無關(guān)，如有侵權(quán)請(qǐng)聯(lián)系我們立即處理。 一、2020年西安電子科技大學(xué)數(shù)據(jù)結(jié)構(gòu)考研復(fù)試核心題庫(kù)之算法設(shè)計(jì)題精編 1已知二叉樹用LeftChild-RightChild表示，頭文件BinaiyTreeNode.h中定義了BinaryTreeNode 類，類中定義了公有數(shù)據(jù)LeftChild，Ri

3、ghtChad，它們分別是指向本結(jié)點(diǎn)左子樹和右子樹根結(jié)點(diǎn)的指針，設(shè)計(jì)并完成下述使用找的非遞歸前序遍歷算法。 【答案】算法如下： 2n個(gè)不同的整數(shù)按遞增序存儲(chǔ)在中，若存在一個(gè)下標(biāo)i,使得，寫一算法找到該下標(biāo)，要求算法的最壞時(shí)間復(fù)雜度為。 【答案】算法如下： 3某有向圖如圖所示，要求: (1)給出拓?fù)渑判蛩惴ùa描述； (2)給出圖的算法執(zhí)行結(jié)果。 圖【答案】(1)拓?fù)渑判虻乃惴枋鋈缦隆?(2)拓?fù)渑判蚪Y(jié)果為 (答案不唯一)。 4已知二叉排序樹采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，根結(jié)點(diǎn)的指針為T，結(jié)點(diǎn)的構(gòu)造為： 其中l(wèi)child、rchild分別指向該結(jié)點(diǎn)左、右孩子的指針(當(dāng)孩子結(jié)點(diǎn)不存在時(shí)，相應(yīng)指針域?yàn)閚il)，data域存放結(jié)點(diǎn)的數(shù)據(jù)信息。請(qǐng)寫出遞歸算法,從小到大輸出該二叉排序樹中所有數(shù)據(jù)值的結(jié)點(diǎn)的數(shù)據(jù)。要求先找到第一個(gè)滿足條件的結(jié)點(diǎn)后再依次輸出其它滿足條件的結(jié)點(diǎn)。 【答案】對(duì)二叉排序樹中序遍歷依次輸出符合條件的結(jié)點(diǎn)數(shù)據(jù)。 5已知一棵二叉樹，該二叉樹中結(jié)點(diǎn)的形式為。其中data域?yàn)榻Y(jié)點(diǎn)的數(shù)據(jù)域，且它的數(shù)據(jù)類型為int；left域和right域分別給出本結(jié)點(diǎn)的左孩子和右孩子的地址，又已知該排序二叉樹的根結(jié)點(diǎn)地址為root。請(qǐng)?jiān)O(shè)計(jì)一個(gè)非遞歸的函數(shù)，給出該二叉樹的前序遍歷序列的