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)?]。

?