2004年上海交通大學(xué)研究生數(shù)據(jù)結(jié)構(gòu)試題_跨考網(wǎng)
一、?已知一棵中序線索二叉樹的結(jié)點(diǎn)結(jié)構(gòu)為:
???????????????????????????????left????????????? ?ltag?????????? ???? ? data??????????????? rtag????????????????right
? |
? |
? |
? |
? |
其中:data 域的類型為int。
ltag=0,那么left域中存放的是該結(jié)點(diǎn)的左兒子結(jié)點(diǎn)的地址。
ltag=1,那么left域中存放的是該結(jié)點(diǎn)的按中序周游次序的前驅(qū)結(jié)點(diǎn)的地址。
rtag=0,那么right域中存放的是該結(jié)點(diǎn)的右兒子結(jié)點(diǎn)的地址。
rtag=1,那么right域中存放的是該結(jié)點(diǎn)的按中序周游次序的后繼結(jié)點(diǎn)地址。
現(xiàn)已知該中序線索樹中,按照中序遍歷次序的第一個(gè)結(jié)點(diǎn)的地址為first,以及某一整數(shù)值為key。請寫一個(gè)函數(shù),輸出結(jié)點(diǎn)的data之值為key 的結(jié)點(diǎn),并仍保持中序線索樹的性質(zhì)不變。注意:不準(zhǔn)使用遞歸,額外空間不得大于O(1)。(本題 25 分)
要點(diǎn):
1、注意,題目給出的是按照中序遍歷次序的第一個(gè)結(jié)點(diǎn)的地址first,因此必須從first開始查找data之值為key 的結(jié)點(diǎn)p及其父結(jié)點(diǎn)q,而不能從根結(jié)點(diǎn)開始進(jìn)行尋找。
2、若結(jié)點(diǎn)p是q的右兒子,可分四種情況進(jìn)行討論:
A、?結(jié)點(diǎn)p是葉子。
B、?結(jié)點(diǎn)p無左兒子,但有右兒子。
C、?結(jié)點(diǎn)p有左兒子,但無右兒子。
D、?結(jié)點(diǎn)p既有左兒子,同樣也有右兒子。
在進(jìn)行調(diào)整后,注意保持調(diào)整后的中序穿線樹的結(jié)點(diǎn)的中序遍歷次序不變。
3、若結(jié)點(diǎn)p是q的左兒子,同樣有四種情況必須討論,同2。
二、已知一棵二叉樹是以二叉鏈表的形式存儲的,且結(jié)點(diǎn)的數(shù)據(jù)場的類型為int?,F(xiàn)已知該二叉樹的根結(jié)點(diǎn)的地址為root。請寫一個(gè)非遞歸的函數(shù)(使用的額外空間不得大于O(1)),給出按后序遍歷次序的第一個(gè)結(jié)點(diǎn)的數(shù)據(jù)場之值。(本題10分)
要點(diǎn):根據(jù)后序周游的定義:LRN 可知第一個(gè)被訪問的結(jié)點(diǎn)將是二叉樹中的最左方的葉子,設(shè)p=root,若p 為空,則無解返回,否則有三種情況。
1。若有左兒子,則p=p->left;
2。若無左兒子,但有右兒子,則p=p->right;
3。若既沒有左兒子,也沒有右兒子,則p即為所求。
三、已知一棵二叉樹是以二叉鏈表的形式存儲的,其結(jié)點(diǎn)結(jié)構(gòu)說明如下:(本題10 分。)
struct node { ?int data;?? // 結(jié)點(diǎn)的數(shù)據(jù)場。
struct node *left;??? // 給出結(jié)點(diǎn)的左兒子的地址。
?struct node * right;?? // 給出結(jié)點(diǎn)的右兒子的地址。
? };
請?jiān)?、2二題的 [????? ]? 處進(jìn)行填空,完成題目要求的功能。注意,每空只能填一個(gè)語句,多填為 0 分。
1、?求出以T 為根的二叉樹或子樹的結(jié)點(diǎn)個(gè)數(shù)。
int size (struct node * T ) {
???if (? [? T == NULL? ]? ) return 0;
???else [ return 1 +size(T->left) + size(T->right) ];
?}
?2、 求出以T為根的二叉樹或子樹的高度。注:高度定義為樹的總的層次數(shù)。
int height(struct node * T ) {
???if ( T == NULL ) [? return 0? ];
???else [ return 1 +( ( height(T->left) > height(T->right))? height(T->left): height(T->right) ) ];
?}
四、設(shè)結(jié)點(diǎn)個(gè)數(shù)為n,請問采用堆排序法進(jìn)行排序,其時(shí)間復(fù)雜性是多少?請以大O形式給出,并給出證明。(本題10分)
要點(diǎn):?
1、建堆的時(shí)間代價(jià):O(n)
2、?排序且進(jìn)行調(diào)整的時(shí)間代價(jià):log(n-1)+ log(n-2)+……+ log3+ log2 = O(nlogn)
證明的詳細(xì)過程略。
五、填空:(本題15分)
1、在二叉排序樹上成功地找到一個(gè)結(jié)點(diǎn),在平均情況下的時(shí)間復(fù)雜性是 [ O(logn)? ], 在最壞情況下的時(shí)間復(fù)雜性是 [ O(n)???? ]。設(shè)結(jié)點(diǎn)個(gè)數(shù)為 n,以大O形式給出時(shí)間復(fù)雜性。
2、在二叉平衡排序樹上成功地找到一個(gè)結(jié)點(diǎn),在平均情況下的時(shí)間復(fù)雜性是 [ O(logn)???? ], 在最壞情況下的時(shí)間復(fù)雜性是 [O(logn)???? ]。設(shè)結(jié)點(diǎn)個(gè)數(shù)為 n,以大O形式給出時(shí)間復(fù)雜性。
3、設(shè)工作區(qū)的容量為W,則置換選擇排序法所得到的初始?xì)w并段長度的期望值為[ 2w ]。
4、設(shè)主串和模式的字符個(gè)數(shù)分別為m和 n,則在最壞情況下,KMP 算法的時(shí)間復(fù)雜性為 [ O( m+n)?]。
?
2022考研初復(fù)試已經(jīng)接近尾聲,考研學(xué)子全面進(jìn)入2023屆備考,跨考為23考研的考生準(zhǔn)備了10大課包全程準(zhǔn)備、全年復(fù)習(xí)備考計(jì)劃、目標(biāo)院校專業(yè)輔導(dǎo)、全真復(fù)試模擬練習(xí)和全程針對性指導(dǎo);2023考研的小伙伴針也已經(jīng)開始擇校和復(fù)習(xí)了,跨考考研暢學(xué)5.0版本全新升級,無論你在校在家都可以更自如的完成你的考研復(fù)習(xí),暑假集訓(xùn)營帶來了院校專業(yè)初步選擇,明確方向;考研備考全年規(guī)劃,核心知識點(diǎn)入門;個(gè)性化制定備考方案,助你贏在起跑線,早出發(fā)一點(diǎn)離成功就更近一點(diǎn)!
考研院校專業(yè)選擇和考研復(fù)習(xí)計(jì)劃 | |||
2023備考學(xué)習(xí) | 2023線上線下隨時(shí)學(xué)習(xí) | 34所自劃線院??佳袕?fù)試分?jǐn)?shù)線匯總 | |
2022考研復(fù)試最全信息整理 | 全國各招生院??佳袕?fù)試分?jǐn)?shù)線匯總 | ||
2023全日制封閉訓(xùn)練 | 全國各招生院校考研調(diào)劑信息匯總 | ||
2023考研先知 | 考研考試科目有哪些? | 如何正確看待考研分?jǐn)?shù)線? | |
不同院校相同專業(yè)如何選擇更適合自己的 | 從就業(yè)說考研如何擇專業(yè)? | ||
手把手教你如何選專業(yè)? | 高校研究生教育各學(xué)科門類排行榜 |
相關(guān)推薦
跨考考研課程
班型 | 定向班型 | 開班時(shí)間 | 高定班 | 標(biāo)準(zhǔn)班 | 課程介紹 | 咨詢 |
秋季集訓(xùn) | 沖刺班 | 9.10-12.20 | 168000 | 24800起 | 小班面授+專業(yè)課1對1+專業(yè)課定向輔導(dǎo)+協(xié)議加強(qiáng)課程(高定班)+專屬規(guī)劃答疑(高定班)+精細(xì)化答疑+復(fù)試資源(高定班)+復(fù)試課包(高定班)+復(fù)試指導(dǎo)(高定班)+復(fù)試班主任1v1服務(wù)(高定班)+復(fù)試面授密訓(xùn)(高定班)+復(fù)試1v1(高定班) | |
2023集訓(xùn)暢學(xué) | 非定向(政英班/數(shù)政英班) | 每月20日 | 22800起(協(xié)議班) | 13800起 | 先行階在線課程+基礎(chǔ)階在線課程+強(qiáng)化階在線課程+真題階在線課程+沖刺階在線課程+專業(yè)課針對性一對一課程+班主任全程督學(xué)服務(wù)+全程規(guī)劃體系+全程測試體系+全程精細(xì)化答疑+擇校擇專業(yè)能力定位體系+全年關(guān)鍵環(huán)節(jié)指導(dǎo)體系+初試加強(qiáng)課+初試專屬服務(wù)+復(fù)試全科標(biāo)準(zhǔn)班服務(wù) |