985院校數(shù)據(jù)結(jié)構(gòu)試卷

1、； break； break ； break；大連理工大學(xué)2002 年碩士入學(xué)試題數(shù)據(jù)結(jié)構(gòu)部分(共 50分 )一、算法填空題(20 分 )1對以下函數(shù)填空，實(shí)現(xiàn)將頭指針為h 的單鏈表逆置，即原鏈表的第一個(gè)結(jié)點(diǎn)變成逆置后新鏈表的最后一個(gè)結(jié)點(diǎn)， 原鏈表的第二個(gè)結(jié)點(diǎn)變成新鏈表的倒數(shù)第二個(gè)結(jié)點(diǎn)， 如此等等， 直到最后一個(gè)結(jié)點(diǎn)作為新鏈表的第一個(gè)結(jié)點(diǎn)，并返回指向該結(jié)點(diǎn)的指針。設(shè)單鏈表結(jié)點(diǎn)類型 的定義為typedef struct nodeint data ；strcut node *next ；NODE ；NODE *dlbnz(NODE*h) NODE *p ， *q ； q=NULL ；while(h

2、)p=h；h=h->next ；return q；2假設(shè)算術(shù)表達(dá)式由字符串 b 表示，其中可以包含三種括號：圓括號和方括號及花括號，其嵌套的順序隨意，如 () 。請對以下函數(shù)填空，實(shí)現(xiàn)判別給定表達(dá)式中所含括號是否正確配對出現(xiàn)的算法。#define M 10int khjc(char *b) char sM ；int i ，j=0 ， f=1 ；j=0 ；for(i=0 ；f&&bi!=0； i+) switch(bi) case：( case ： case ： case ：)case： case ：if(j=0;|bI!=)f=0 ；return f&&；

3、3對以下函數(shù)填空，實(shí)現(xiàn)以帶頭結(jié)點(diǎn)的單鏈表h 為存儲結(jié)構(gòu)的直接選擇排序。設(shè)單鏈表結(jié)點(diǎn)類型的定義為typedef struct node int key ；struct node *next ；NODE ；void pxx(NODE *h) NODE *p ， *q ， *m ； int z；p=h->next ； while(p!=NULL) q=p->next ；m=p； while(q!=NULL) if(m->key>q->key)；if(p!=m) x=p->key ；p->key=m->key ；m->key=x ； 二、算法設(shè)計(jì)題

4、(30 分 )請用類 C 或類 PASCAL 語言設(shè)計(jì)實(shí)現(xiàn)下列功能的算法。1設(shè)二叉排序樹以二叉鏈表為存儲結(jié)構(gòu)，請編寫一個(gè)非遞歸算法，從大到小輸出二叉排序樹中所有其值不小于X 的鍵值。 (10 分 )2設(shè)由 n 個(gè)整數(shù)組成一個(gè)大根堆(即第一個(gè)數(shù)是堆中的最大值)，請編寫一個(gè)時(shí)間復(fù)雜度為 O(log 2n)的算法，實(shí)現(xiàn)將整數(shù)X 插入到堆中，并保證插入后仍是大根堆。(10 分 )3請編寫一個(gè)算法，判斷含n 個(gè)頂點(diǎn)和e 條邊的有向圖中是否存在環(huán)。并分析算法的時(shí)間復(fù)雜度。 (10 分 )大連理工大學(xué)2003 年碩士入學(xué)試題數(shù)據(jù)結(jié)構(gòu)部分(共 75分 )一、回答下列問題(20 分 )1循環(huán)隊(duì)列用數(shù)組A0 m1

5、) 存放其數(shù)據(jù)元素。設(shè)向其實(shí)際隊(duì)首的前一個(gè)位置，則當(dāng)前隊(duì)列中的數(shù)據(jù)元素有多少個(gè)斷?tail指向其實(shí)際的隊(duì)尾，front?如何進(jìn)行隊(duì)空和隊(duì)滿的判指2設(shè)散列表的地址空間為010，散列函數(shù)為H(key)=key 11(為求余函數(shù) )，采用線性探查法解決沖突，并將鍵值序列15 ， 36， 50， 27，19，48 依次存儲到散列表中，請畫出相應(yīng)的散列表；當(dāng)查找鍵值48 時(shí)需要比較多少次?3什么是 m 階 B -樹?在什么情況下向一棵m 階 B-樹中插入一個(gè)關(guān)鍵字會產(chǎn)生結(jié)點(diǎn)分裂?在什么情況下從一棵m 階 B -樹中刪除一個(gè)關(guān)鍵字會產(chǎn)生結(jié)點(diǎn)合并?4什么是線索二叉樹?一棵二叉樹的中序遍歷序列為由djbaec

6、hif ，前序遍歷序列為abdjcefhi ，請畫出該二叉樹的后序線索二叉樹。二、請用類 C 或類 PASCAL 語言進(jìn)行算法設(shè)計(jì)，并回答相應(yīng)問題。(45分)1設(shè)計(jì)一非遞歸算法采用深度優(yōu)先搜索對無向圖進(jìn)行遍歷，并對算法中的無向圖的存儲結(jié)構(gòu)予以簡單說明。2用鏈?zhǔn)酱鎯Y(jié)構(gòu)存放一元多項(xiàng)式Pn(x)=P 1xel+P2xe2+ +Pnxen，其中 Pi 是指數(shù)為 ei 的項(xiàng)的非零系數(shù)，且滿足0e1e2<en=n。請?jiān)O(shè)計(jì)算法將多項(xiàng)式PB=P n2(x) 加到多項(xiàng)式A=P (x)，同時(shí)對算法及鏈表的結(jié)點(diǎn)結(jié)構(gòu)給出簡單注釋。要求利用(x) 和 P (x) 的結(jié)點(diǎn)產(chǎn)生n1nln2最后求得的和多項(xiàng)式，不允許

7、另建和多項(xiàng)式的結(jié)點(diǎn)空間。3 (1)Rl ， R2， ， Rn 為待排序的記錄序列，請?jiān)O(shè)計(jì)算法對R1 ， R2， ， Rn 按關(guān)鍵字的非遞減次序進(jìn)行快速排序。(2) 若待排序的記錄的關(guān)鍵字集合是 30 ， 4， 48， 25， 95， 13，90， 27， 18)，請給出采用快速排序的第一趟、第二趟排序結(jié)果。(3) 若對 (2) 中給出的關(guān)鍵字集合采用堆排序，請問初建的小根堆是什么待排序的記錄的關(guān)鍵字基本有序時(shí)，應(yīng)采用堆排序還是快速排序? (4) 當(dāng)給定的?為什么 ? 三、算法填空(10 分)1一棵樹以孩子兄弟表示法存儲，遞歸算法numberofleaf 計(jì)算并返回根為子結(jié)點(diǎn)的個(gè)數(shù) (NULL代

8、表空指針 )。typedef struct nodestruct node *firstchild， *nextbrother ； TFNNode ；int numberofleaf(TFNNode *r) int num ；if(r=NULL)num=0；elseif(r->firstchild=NULL)num=+numberofleaf ；(r->nextbrother) ；else；return(num) ；r 的樹中葉2在根結(jié)點(diǎn)為仍是一棵二叉排序樹r 的二叉排序樹中，插人數(shù)據(jù)域值為(NULL 代表空指針 )。x 的結(jié)點(diǎn)，要求插入新結(jié)點(diǎn)后的樹二叉排序樹的結(jié)點(diǎn)結(jié)構(gòu)為typed

9、ef struct node int key ；struct node *lc,*rc ； BiNode ；BiNode *insert(BiNode *r,int x) BiNode *p,*q,*s;s=(BiNode*)malloc(sizeof(BiNode); s->key=x;s->lc=NULL;s->rc=NULL;q=NULL;if(r=NULL)r=s;return(r);p=r;while() q=p;if()p=p->lc;else p=p->rcif(x<q->key);else;return;清華大學(xué) 2001 年數(shù)據(jù)結(jié)構(gòu)與

10、程序設(shè)計(jì)試題試題內(nèi)容：一、試給出下列有關(guān)并查集(mfsets) 的操作序列的運(yùn)算結(jié)果：union(1 ， 2)， union(3 ， 4)， union(3 ，5) ，union(1 ， 7)， union(3 ， 6)， union(8 ， 9)， union(1 ，8)， union(3 ， 10)， union(3 ， 11)，union(3 ， 12)， union(3 ， 13)，union(14 ，15)， union(16 ， 0)， union(14 ，16)， union(1， 3)， union(1 ， 14)。 (union 是合并運(yùn)算，在以前的書中命名為 merge)要

11、求：(1)對于 union(i ，j) ，以 i 作為 j 的雙親； (5 分 )(2)按i 和j 為根的樹的高度實(shí)現(xiàn)union(i ， j) ，高度大者為高度小者的雙親；(5 分)(3) 按 i 和 j 為根的樹的結(jié)點(diǎn)個(gè)數(shù)實(shí)現(xiàn) union(i， j) ，結(jié)點(diǎn)個(gè)數(shù)大者為結(jié)點(diǎn)個(gè)數(shù)小者的雙親。(5 分)二、設(shè)在 4 地 (A ， B， C， D) 之間架設(shè)有 6 座橋，如下圖所示：要求從某一地出發(fā)，經(jīng)過每座橋恰巧一次，最后仍回到原地。(1) 試就以上圖形說明：此問題有解的條件是什么?(5 分 )(2) 設(shè)圖中的頂點(diǎn)數(shù)為 n，試用 C 或 Pascal 描述與求解此問題有關(guān)的數(shù)據(jù)結(jié)構(gòu)并編寫一個(gè)算法，

12、找出滿足要求的一條回路。(10 分)三、針對以下情況確定非遞歸的歸并排序的運(yùn)行時(shí)間(數(shù)據(jù)比較次數(shù)與移動(dòng)次數(shù))：(1) 輸人的 n 個(gè)數(shù)據(jù)全部有序；(5 分) (2)輸入的 n 個(gè)數(shù)據(jù)全部逆向有序；(5 分) (3)隨機(jī)地輸入幾個(gè)數(shù)據(jù)。(5 分 ) 四、簡單回答有關(guān) AVL 樹的問題。(1) 在有 N 個(gè)結(jié)點(diǎn)的 A VL 樹中，為結(jié)點(diǎn)增加一個(gè)存放結(jié)點(diǎn)高度的數(shù)據(jù)成員，那么每一個(gè)結(jié)點(diǎn)需要增加多少個(gè)字位 (bit)?(5 分 )(2) 若每一個(gè)結(jié)點(diǎn)中的高度計(jì)數(shù)器有 8bit，那么這樣的 AVL 樹可以有多少層 ?最少有多少個(gè)關(guān)鍵碼 ?(5 分)五、一個(gè)散列表包含hashSize=13 個(gè)表項(xiàng)，其下標(biāo)從

13、 0 到 12，采用線性探查法解決沖突。請按以下要求，將下列關(guān)鍵碼散列到表中。101003245581263292004000(1) 散列函數(shù)采用除留余數(shù)法，用hashSize(取余運(yùn)算 )將各關(guān)鍵碼映像到表中。請指出每一個(gè)產(chǎn)生沖突的關(guān)鍵碼可能產(chǎn)生多少次沖突。(7 分) (2) 散列函數(shù)采用先將關(guān)鍵碼各位數(shù)字折疊相加，再用 hashSize 將相加的結(jié)果映像到表中的辦法。請指出每一個(gè)產(chǎn)生沖突的關(guān)鍵碼可能產(chǎn)生多少次沖突。(8 分)六、設(shè)一棵二叉樹的結(jié)點(diǎn)定義為structBinTreeNode ElemType data；BinTreeNode*leftChild,*rightChild；現(xiàn)采用輸

14、入廣義表表示建立二叉樹。具體規(guī)定如下：(1)樹的根結(jié)點(diǎn)作為由子樹構(gòu)成的表的表名放在表的最前面；(2) 每個(gè)結(jié)點(diǎn)的左子樹和右子樹用逗號隔開。若僅有右子樹，沒有左子樹，逗號不能省略。(3)在整個(gè)廣義表表示輸入的結(jié)尾加上一個(gè)特殊的符號(例如 “#”)表示輸入結(jié)果。 ； 例如，對于如右圖所示的二叉樹，其廣義表表示為A(B(D ，E(G，)，C(， F)此算法的基本思路是：依次從保存廣義表的字符串ls 中輸入每個(gè)字符。若遇到的是字母(假定以字母作為結(jié)點(diǎn)的值)，則表示是結(jié)點(diǎn)的值，應(yīng)為它建立一個(gè)新的結(jié)點(diǎn)，并把該結(jié)點(diǎn)作為左子女當(dāng)(k=1) 或右子女 (當(dāng)k=2)鏈接到其雙親結(jié)點(diǎn)上。若遇到的是左括號” (，”則

15、表明子表的開始，將 A 置為 1；若遇到的是右括號”)”，則表明子表結(jié)束。若遇到的是逗號”， ”，則表示以左子女為根的子樹處理完畢，應(yīng)接著處理以右子女為根的子樹，將A 置為 2。在算法中使用了一個(gè)棧 s，在進(jìn)入子表之前，將根結(jié)點(diǎn)指針進(jìn)棧，以便括號內(nèi)的子女鏈接之用。在子表處理結(jié)束時(shí)退棧。相關(guān)的棧操作如下：MakeEmpty(s) 置空棧 Push(s，p)元素 p 進(jìn)棧 Pop(s)退棧Top(s) 存取棧頂元素的函數(shù)下面給出了建立二叉樹的算法，其中有 5 個(gè)語句缺失。請閱讀此算法并把缺失的語句補(bǔ)上。 (每空 3 分)Void CreateBinTree(BinTreeNode*&BT,

16、char ls) Stack<BinTreeNode*>s ； MakeEmpty(s) ；BT=NULL ；/置二叉樹BinTreeNode *p；int k ；istream ins(ls) ；/ 把串l s 定義為輸入字符串流對象inschar ch；ins>>ch ；/ 從 ins 順序讀入一個(gè)字符while(ch!=” #”)/ 逐個(gè)字符處理，直到遇到 #為止switch(ch) case ：( (1) k=1；break；case：)pop(s)；break；case , (2)break；default： p=new BinTreeNode ；(3)p-&

17、gt;leftChild=NULL；p->rightChfild=NULL；if(BT=NULL)(4)else if(k=1)top(s)->leftChild=p；else top(8)->rightChild=p；(5)|七、下面是一個(gè)用C 編寫的快速排序算法。為了避免最壞情況，取基準(zhǔn)記錄pivot 采用從 left ，right 和 mid=(1eft+right)/2 中取中間值，并交換到right 位置的辦法。數(shù)組a 存放待排序的一組記錄，數(shù)據(jù)類型為Type， left 和 right 是待排序子區(qū)間的最左端點(diǎn)和最右端點(diǎn)。Void quicksort(Type a

18、&#, intlefl ，int right) Type temp ；if(left<right) Type pivot=medlian3(a,left，right) ；int i=left ， j=right-1;for(； ； ) while(i<j&&sI<pivot) i+；while(i<j&&pivot<ajj- ；if(i<j) temp=ai ； aj=ai ； ai=temp ；i+ ； j- ；else break；if(si>pivot) temp=ai ； ai=aright ； arig

19、ht=temp ；quicksort(a,left ， i-1) ；/遞歸排序左子區(qū)間quicksort(a ， i+1 ， right) ； /遞歸排序右子區(qū)間(1) 用C 或Pascal 實(shí)現(xiàn)三者取中子程序median3(a,left,right) ； (5 分 )(2) 改寫 quicksoft 算法，不用棧消去第二個(gè)遞歸調(diào)用quicksort(a ， j+1 ， right) ；(5 分 ) (3) 繼續(xù)改寫 quicksort 算法，用棧消去剩下的遞歸調(diào)用。(5 分)上海交通大學(xué)2001年數(shù)據(jù)結(jié)構(gòu)及程序設(shè)計(jì)試題注意：程序設(shè)計(jì)請采用 C 語言，程序應(yīng)有注解及說明?；卮饐栴}簡潔、清晰全面

20、。不得采用類 C 之類的語言寫程序。一、參見下圖，該有向圖是AOE網(wǎng)絡(luò)。該圖上已標(biāo)出了源點(diǎn)及匯點(diǎn)，并給出了活動(dòng)(邊)的權(quán)值。請求出該 A OE 網(wǎng)絡(luò)的關(guān)鍵路徑，以及事件(結(jié)點(diǎn) )的最早發(fā)生時(shí)間及最遲發(fā)生時(shí)間。(本題8 分)二、已知某二叉樹的每個(gè)結(jié)點(diǎn)，要么其左、右子樹皆為空，要么其左、右子樹皆不空。又知該二叉樹的前序序列為(即先根次序 )：J、F、D、B、A、C、E、H、X、I、K；后序序列為 (即后根次序 )： A 、C、B 、 E、 D、 X 、 I、H 、 F、 K 、 Jo 請給出該二叉樹的中序序列(即中根次序 )，并畫出相應(yīng)的二叉樹樹形。(本題 8分 )三、回答下列問題：(本題 10分

21、)1)具有 N 個(gè)結(jié)點(diǎn)且互不相似的二叉樹的總數(shù)是多少?2)具有 N 個(gè)結(jié)點(diǎn)且不同形態(tài)的樹的總數(shù)是多少?3)對二叉樹而言，如果它的葉子結(jié)點(diǎn)總數(shù)為N0 ，度為 2 的結(jié)點(diǎn)的總為 N2 ，則 N0 和 N 2之間的關(guān)系如何 ?4)二叉樹是否是結(jié)點(diǎn)的度最多為2 的樹 ?請說明理由。5)具有 n 片葉子的哈夫曼樹 (即赫夫曼樹 )中，結(jié)點(diǎn)總數(shù)為多少？四、在外部分類時(shí)，為了減少讀、寫的次數(shù)，可以采用k 路平衡歸并的最佳歸并樹模式。當(dāng)初始?xì)w并段的總數(shù)不足時(shí)，可以增加長度為零的“虛段 ?！闭垎栐黾拥?“虛段 ”的數(shù)目為 多少 ?請推導(dǎo)之。設(shè)初始?xì)w并段的總數(shù)為m。 (本題 8 分)五、對平衡的排序二叉樹進(jìn)行刪除

22、結(jié)點(diǎn)的操作，必須保證刪除之后平衡樹中的每個(gè)結(jié)點(diǎn)的平衡因子是 +1， -1， 0三種情況之一，且該樹仍然是排序二叉樹。現(xiàn)假定刪除操作是在p結(jié)點(diǎn)的左子樹上進(jìn)行的，且該左子樹原高為h-l，現(xiàn)變?yōu)?h-2。因此，必須從 p 的左子樹沿著到根的方向回溯調(diào)整結(jié)點(diǎn)的平衡因子，并進(jìn)行樹形的調(diào)整。設(shè)p 是調(diào)整時(shí)遇到的第一個(gè)平衡因子力圖由 -1 變成 -2 的最年輕的 “前輩 ”結(jié)點(diǎn)。我們知道，以p 為根的子樹經(jīng)調(diào)整后，高度有可能減少 1。試用圖形把調(diào)整前及調(diào)整后的相關(guān)結(jié)點(diǎn)的平衡因子、樹形表示出來；僅僅針對調(diào)整后子樹的高度減少1 的情況即可。注意，羅列出所有可能的情況。上圖可供參考。(本題10分)六、某算法由下述

23、方程表示。請求出該算法的時(shí)間復(fù)雜性的級別(以大 O 形式表示 )。注意 n>7 求解問題的規(guī)模，設(shè) n 是 3 的正整數(shù)冪。 (本題8 分 )1如果 n=1Tn=5T(n/3)+n如果 n>1七、如右圖所示，該二叉樹是某棵有序樹變換成 的相對應(yīng)的二叉樹。試給出原來的有序樹的形狀。并回答以下問題：1)原有序樹是度為多少的樹?2)原有序樹的葉子結(jié)點(diǎn)有哪幾個(gè)?3)是否所有的二叉樹都可以找到相對應(yīng)的有序樹?必須滿足什么條件?(本題5 分) 八、在排序二叉樹上進(jìn)行查找操作時(shí)，設(shè)對樹中的每個(gè)結(jié)點(diǎn)查找概率相同。設(shè)由n 個(gè)結(jié)點(diǎn)構(gòu)成的序列生成的排序二叉樹是“隨機(jī) ”的。試求出在成功查找的情況下，平均

24、查找長度是多少 ?為了簡單起見，最后得到的遞推式可不予求解。(本題 8 分)九、設(shè)從鍵盤每次輸入兩個(gè)字符。如A 、 B，則表示存在著一條由數(shù)據(jù)場之值為字符A的結(jié)點(diǎn)到數(shù)據(jù)場之值為字符B 的結(jié)點(diǎn)的有向邊。依此輸入這些有向邊，直至出現(xiàn)字符! 為止。試設(shè)計(jì)一個(gè)程序，生成該有向圖的鄰接表及逆鄰接表。必須交待所用的結(jié)構(gòu)、變量、加以適當(dāng)注解。(本題 20 分 )·十、設(shè)二叉樹中結(jié)點(diǎn)的數(shù)據(jù)場之值為一字符。采用二叉鏈表的方式存儲該二叉樹中的所有結(jié)點(diǎn)，設(shè) p 為指向樹根結(jié)點(diǎn)的指針。設(shè)計(jì)一個(gè)程序在該二叉樹中尋找數(shù)據(jù)場之值為key(key為一變量，變量內(nèi)容為一字符)的那個(gè)結(jié)點(diǎn)的所有祖先。設(shè)二叉樹中結(jié)點(diǎn)數(shù)據(jù)場

25、之值互不重復(fù)。 (本題 15 分)注意：有些書上將二叉樹的二叉鏈表存儲形式稱之為標(biāo)準(zhǔn)存儲形式。南開大學(xué) 2001年數(shù)據(jù)結(jié)構(gòu)試題一、選擇題 (每小題 3 分，共 21 分 ) 在下列各題中，每題之后均有若干個(gè)備選答案，請選出所有正確的答案，填人“處。答案請寫在答題紙上。1任何一個(gè)無向連通圖的最小生成樹。只有一棵有一棵或多棵一定有多棵可能不存在2已知一棵非空二叉樹的，則能夠惟一確定這棵二叉樹?！毕刃虮闅v序列和后序遍歷序列先序遍歷序列和中序遍歷序列先序遍歷序列中序遍歷序列，3使用指針實(shí)現(xiàn)二叉樹時(shí)，如果結(jié)點(diǎn)的個(gè)數(shù)為n，則非空的指針域個(gè)數(shù)為。 n-1 2n-1 n+1 2n+1 4 設(shè)隊(duì)列存儲于一個(gè)一維

26、數(shù)組中，數(shù)組下標(biāo)范圍是 1-n，頭尾指針分別為f 和 r， f 指向第一個(gè)元素的前一個(gè)位置，r 指向隊(duì)列中的最后一個(gè)元素，則隊(duì)列中元素個(gè)數(shù)為。 r-f r-f+1 (r-f+1)mod n (r-f+n)mod n5任意一個(gè) A OE 網(wǎng)絡(luò)的關(guān)鍵路徑。一定有多條只有一條可能不只一條可能不存在6下列排序算法中，在每一趟都能選出一個(gè)元素放到其最終位置上的是。插入排序希爾排序快速排序堆排序7任意一個(gè)有向圖的拓?fù)渑判蛐蛄?。一定有多種只有一種可能不存在以上都不對二、 (7 分 )已知散列表地址空間為0-8，哈希函數(shù)為H(k)=kmod7 ，采用線性探測再散列法解決沖突。將下面關(guān)鍵字?jǐn)?shù)據(jù)依次填入該散列表中

27、，同時(shí)將查找每個(gè)關(guān)鍵字所需的比較次數(shù)m 填入下表中，并求等概率下的平均查找長度。關(guān)鍵字值： 100， 20， 21， 35， 3，78， 99，45012345678A1002021353789945m三、 (12分 )回答下列問題：(1)(3 分 )什么叫基數(shù)排序 ?(2)(3 分 )什么是 A VL 樹中的平衡因子，它有什么特點(diǎn)?(3)(6 分 )n 個(gè)元素的序列 k1,k2, kn 滿足什么條件才能稱之為堆?簡述對它進(jìn)行堆排序的過程。四、 (10 分 )順序給出以下關(guān)鍵字：63、 23、 31、 26、 7、 91、 53、 15、72、52、 49、 68，構(gòu)造 3 階 B-樹。要求從

28、空樹開始，每插入一個(gè)關(guān)鍵字，畫出一個(gè)樹形。五、 (6 分 )設(shè)有向無環(huán)圖G 如下圖所示：試寫出圖 G 的六種不同的拓?fù)渑判蛐蛄?。六?(10分 )設(shè)二叉樹以二叉鏈表表示，各結(jié)點(diǎn)的結(jié)構(gòu)如下所示：leftdatasubsumright其中 left、 right 分別為指向該結(jié)點(diǎn)左、右孩子的指針，data 為存儲關(guān)鍵字值的整數(shù)域，subsum 中存儲以該結(jié)點(diǎn)為根的子樹中所有關(guān)鍵字值之和。試使用C 或 C+ 語言設(shè)計(jì)算法，計(jì)算所給樹 T 中所有結(jié)點(diǎn)的 subsum 值。七、 (12 分 )給出一個(gè)帶表頭的單鏈表L ， L 的每個(gè)結(jié)點(diǎn)中存放一個(gè)整數(shù)?，F(xiàn)給定一個(gè)閾值 K，將 L 分成兩個(gè)子表L1 和 L

29、2 ，其中 L 1 中存放 L 中所有關(guān)鍵字值大于等于是的結(jié)點(diǎn)，L2中存放 L 中所有關(guān)鍵字值小于K 的結(jié)點(diǎn)。試編程實(shí)現(xiàn)這個(gè)過程。要求，使用C 或 C+ 語言實(shí)現(xiàn)算法， L1 和 L2 仍占用 L 的存儲空間。八、 (10 分)設(shè)有一維整數(shù)數(shù)組A ，試使用 C 或 C+語言設(shè)計(jì)算法，將A 中所有的奇數(shù)排在所有偶數(shù)之前。要求，時(shí)間復(fù)雜度盡可能地少，結(jié)果仍放在A 原來的存儲空間。九、 (12 分 )簡述哈夫曼編碼的構(gòu)造過程。華東理工大學(xué) 2001年數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì)試題一、單選題 (10 分 ) 1若某線性表中最常用的操作是在最后一個(gè)元素之后插入一個(gè)元素和刪除第一個(gè)元素，則采用 存儲方式最節(jié)省運(yùn)算

30、時(shí)間。A 單鏈表B 僅有頭指針的單循環(huán)鏈表C雙鏈表D 僅有尾指針的單循環(huán)鏈表2若在線性表中采用折半查找法查找元素，該線性表應(yīng)該。A 元素按值有序B 采用順序存儲結(jié)構(gòu)C元素按值有序，且采用順序存儲結(jié)構(gòu)D元素按值有序，且采用鏈?zhǔn)酱鎯Y(jié)構(gòu)3對于給定的結(jié)點(diǎn)序列abcdef，規(guī)定進(jìn)棧只能從序列的左端開始。通過棧的操作，能得到的序列為。A abcfedB cabfedC abcfdeD cbafde 4已知一算術(shù)表達(dá)式的中綴形式為 A+B*C-D/E，后綴形式為 ABC*+DE/- ，其前綴形式為。A -A+B*C/DEB -A+B*CD/EC -+*ABC/DED -+A*BC/DE5如果 n1 和 n

31、2 是二叉樹 T 中兩個(gè)不同結(jié)點(diǎn)，n2 為 n1 的后代，那么按遍歷二叉樹 T時(shí)，結(jié)點(diǎn) n2 一定比結(jié)點(diǎn) n1 先被訪問。A 前序B 中序C后序D 層次序 6具有65 個(gè)結(jié)點(diǎn)的完全二叉樹其深度為。 (根的層次號為 1)A 8B 7C6D 57已知二叉樹的前序遍歷序列是abdgcefh，中序遍歷序列是 dgbaechf，它的后序遍歷序列是。A bdgcefha B. gdbecfhaC bdgechfa D gdbehfca8對于前序遍歷和后序遍歷結(jié)果相同的二叉樹為。A 一般二叉樹B只有根結(jié)點(diǎn)的二叉樹C根結(jié)點(diǎn)無左孩子的二叉樹D根結(jié)點(diǎn)無右孩子的二叉樹9對于前序遍歷與中序遍歷結(jié)果相同的二叉樹為。A

32、根結(jié)點(diǎn)無左孩子的二叉樹B根結(jié)點(diǎn)無右孩子的二叉樹 C所有結(jié)點(diǎn)只有左子樹的二叉樹D所有結(jié)點(diǎn)只有右子樹的二叉樹10在有 n 個(gè)葉子的哈夫曼樹中，其結(jié)點(diǎn)總數(shù)為。A 不確定B 2nC 2n+1D 2n-1 二、是非題 (10 分) 1順序存儲方式只能用于存儲線性結(jié)構(gòu)。2消除遞歸不一定需要使用棧。3將一棵樹轉(zhuǎn)換成相應(yīng)的二叉樹后，根結(jié)點(diǎn)沒有右子樹。4完全二叉樹可以采用順序存儲結(jié)構(gòu)實(shí)現(xiàn)，存儲非完全二叉樹則不能。5在前序遍歷二叉樹的序列中，任何結(jié)點(diǎn)的子樹的所有結(jié)點(diǎn)都是直接跟在該結(jié)點(diǎn)之后。6鄰接表法只能用于有向圖的存儲，而鄰接矩陣法對于有向圖和無向圖的存儲都適用。7在一個(gè)有向圖的鄰接表中，如果某個(gè)頂點(diǎn)的鏈表為空，

33、則該頂點(diǎn)的度一定為零。8二叉樹為二叉排序樹的充分必要條件是其任一結(jié)點(diǎn)的值均大于其左孩子的值，小于其右孩子的值。9最佳二叉排序樹的任何子樹都是最佳二叉排序樹。10對兩棵具有相同關(guān)鍵字集合的而形狀不同的二叉排序樹，按中序遍歷它們得到的序列的順序是一樣的。三、問答題(應(yīng)屆生限做2， 3， 4， 5 題；在職生任選做四題；共40 分 )1 (10 分 )什么是廣義表 ?請簡述廣義表與線性表的主要區(qū)別。2 (10 分 )下圖表示一個(gè)地區(qū)的通訊網(wǎng)，邊表示城市間的通訊線路，邊上的權(quán)表示架設(shè)線路花費(fèi)的代價(jià)。請分別給出該圖的鄰接表和鄰接矩陣，要求每種存儲結(jié)構(gòu)能夠表達(dá)出該圖的全部信息，并分別對這二種形式中每個(gè)部分

34、的含義(物理意義 )予以簡要說明。若假設(shè)每個(gè)域 (包括指針域 )的長度為一個(gè)字節(jié)，請分別計(jì)算出這二種結(jié)構(gòu)所占用的空間大小。3 (10 分 )已知如下所示長度為12 的表：(Jan， Feb， Mar， Apr ， May ， June， July， Aug ， Sep， Oct， Nov ， Dec)試按表中元素的順序依次插入一棵初始為空的二叉排序樹， 請畫出插入完成之后的二叉排序樹，并求其在等概率的情況下查找成功的平均查找長度。若對表中元素先進(jìn)行排序構(gòu)成有序表， 求在等概率的情況下對此有序表進(jìn)行折半查找時(shí)查找成功的平均查找長度。按表中元素順序構(gòu)造一棵平衡二叉排序樹， 并求其在等概率的情況下查

35、找成功的平均查找長度。4 (10 分 )在起泡排序過程中，有的關(guān)鍵字在某趟排序中可能朝著與最終排序相反的方向移動(dòng)，試舉例說明之?？焖倥判蜻^程中有沒有這種現(xiàn)象?5 (10 分 )調(diào)用下列函數(shù) f(n) ，回答下列問題：試指出 f(n) 值的大小，并寫出 f(n) 值的推導(dǎo)過程；假定 n=5，試指出 f(5)值的大小和執(zhí)行 f (5)的輸出結(jié)果。C 函數(shù)int f(int n) int i ，j ， k， sum=0； for(j=1 ； i<n+1 i+) for(j=n ； j>i-1 ； j-) for(k=1 ； k<j+1 ； k+) suni+ ； prinft( ”

36、 sum=%dn”， sum)；return(sum) ；Pascal 函數(shù)FUNCTION f(n： integer) ： integer；VAR i ， j， k， sum， integer；BEGINsum： =0；FOR i ： =1 TO n DOBEGINFOR j ：=n DOWN i DOFOR k ： =1 TO j DOsum： =sum+1 writeln( sum=，sum)END ；f： =sumEND ；四、編寫算法(應(yīng)屆生限做 1、 2、 3、 4 題，在職生任選四題，每題10 分，共 40 分 )1(10 分 )利用兩個(gè)棧S1 和 S2 模擬一個(gè)隊(duì)列，寫出入隊(duì)和

37、出隊(duì)的算法(可用棧的基本操作) 。棧的操作有：makeEmpty(s ：stack)；stack；value： datatype)；pop(s： stack)：datatype；isEmpty(s ： stack)： boolean；置空棧 push(s：新元素 value 進(jìn)棧出棧，返回棧頂值判?？辗耜?duì)列的操作有enQtleue(s1： stack； s2：stack； value：datatype)；元素 value 進(jìn)隊(duì)deQueue(s1： stack； s2： stack)： datatype；出隊(duì)列，返回隊(duì)頭值2 (10 分 )試寫出給定的二叉樹進(jìn)行層次遍歷的算法，在遍歷時(shí)使用一個(gè)

38、鏈接隊(duì)列。3 (10 分 )試寫一個(gè)算法，判別以鄰接表方式存儲的有向圖中是否存在由頂點(diǎn)vj 的路徑 (i<>j) 。假設(shè)分別基于下述策略：1)圖的深度優(yōu)先搜索；2)圖的廣度優(yōu)先搜索；4 (10 分) 設(shè)二叉排序樹中關(guān)鍵字由1 至 1000 的整數(shù)構(gòu)成，現(xiàn)要檢索關(guān)鍵字為vi 到頂點(diǎn)531 的結(jié)點(diǎn)，下述關(guān)鍵字序列中哪些可能是二叉排序樹上搜索到的序列，哪些不可能是二叉排序樹上搜索到的序列，哪些不可能是二叉排序樹上搜索到的序列？a)800， 399，588， 570， 500， 520， 566，531b)730 ， 355， 780， 390， 701，401， 530，531c)732

39、， 321，712， 385， 713， 392， 531 d)8 ，578，555， 340， 433， 551， 550， 450， 531通過對上述序列的分析，試寫一個(gè)算法判定給定的關(guān)鍵字序列 (假定關(guān)鍵字互不相同否可能是二叉排序樹的搜索序列。若可能則返回真，否則返回假。可假定被判定的序列已存入數(shù)組中。)是5 (10分 )編寫一個(gè)在非空的帶表頭結(jié)點(diǎn)的單鏈表上實(shí)現(xiàn)就地排序的程序。(不額外申請新的鏈表空間)華中理工大學(xué)2001年數(shù)據(jù)結(jié)構(gòu)試題說明：在有數(shù)據(jù)類型定義和算法設(shè)計(jì)的各題中，任取C 語言、 PASCAL 語言之一作答，但不許使用所謂“類 C”或 “類 PASCAL ”。一、選擇題 (從

40、下列各題四個(gè)備選答案中選出一至四個(gè)正確答案，將其代號(A ， B ，C，D)寫在題干前面的括號內(nèi)。答案選錯(cuò)或未選全者，該題不得分。每小題1 分，共計(jì) 20 分 ) ()1一個(gè)算法具有等特點(diǎn)。A 可行性B至少有一個(gè)輸入量C確定性D健壯性()2.是一個(gè)線性表。A (A ， B， C， D)B A， B， C， DC(1， 2， 3，)D (40， -22， 88)()3可使用作壓縮稀疏矩陣的存儲結(jié)構(gòu)。A 鄰接矩陣C鄰接表B三元組表D 十字鏈表()4采用一維數(shù)組表示順序存儲結(jié)構(gòu)時(shí)，可用它來表示。A 字符串B 2 度樹C二叉樹D無向圖)5假設(shè)進(jìn)入棧的元素序列為d， c， a，b， e，那么可得到出棧的

41、元素序列A a， b， c，d， eB a，b， e， d，cCd， b， a， e， cD d， b，a， c， e。()6對隊(duì)列的操作有。A 在隊(duì)首插入元素B刪除值最小的元素C按元素的大小排序D判斷是否還有元素()7假設(shè)有 60 行 70 列的二維數(shù)組 a1 60， 1 70，以列序?yàn)橹餍蝽樞虼鎯?，其基地址?10000，每個(gè)元素占2 個(gè)存儲單元，那么第32 行第 58 列的元素 a32， 58 的存儲地址為。(無第 0 行第 0 列元素 )A 16902B 16904C14454D答案 A ， B， C 均不對()8.是 C 語言中 "abcd321ABCD" 的子串

42、。A abedB 32lABC ” abeABC”D ” 2lAB ”()9 在下列各廣義表中，長度為3 的廣義表有。A (a， b， c， ()B (g) ， (a， b， c， d， f) ， ()C(a，(b ，(c)D ()()10一個(gè)堆 (heap)又是一棵。 A 二叉排序樹B完全二叉樹C平衡二叉樹D哈夫曼 (Huffman) 樹()11折半查找有序表(4， 6， 10，20， 30， 50，70， 88，100)，若查找元素它將依次與表中元素比較大小，查找結(jié)果是失敗。A 20， 70，30， 50B 30， 88， 70C20， 50D 30， 88，50， 70()12對 27

43、個(gè)記錄的有序表作折半查找，當(dāng)查找失敗時(shí)，至少需要比較58，則次關(guān)鍵字。(A 3B4C5D6)13具有 12 個(gè)結(jié)點(diǎn)的完全二叉樹有。A 5 個(gè)葉子B 5 個(gè)度為 2 的結(jié)點(diǎn)C7 個(gè)分支結(jié)點(diǎn)D 2 個(gè)度為 1 的結(jié)點(diǎn))14具有 n(n>0) 個(gè)結(jié)點(diǎn)的完全二叉樹的深度為。A log 2(n)B log 2(n+1)C log 2(n) +1D loge(n) +1)15用 5 個(gè)權(quán)值 3 ， 2，4，5，1 構(gòu)造的哈夫曼 (Huffman)樹的帶權(quán)路徑長度是A 32B 33C 34D 15)16對 14 個(gè)記錄的表進(jìn)行2 路歸并排序，共需移動(dòng)次記錄。A 42B 56C 91D 84)17對有

44、n 個(gè)記錄的表作快速排序，在最壞情況下，算法的時(shí)間復(fù)雜度是2n)18在最好情況下，下列算法中排序算法所需比較關(guān)鍵字次數(shù)最少。A 冒泡B 歸并C快速D 直接插入。()19置換選擇排序的功能是。 A 選出最大的元素B產(chǎn)生初始?xì)w并段C產(chǎn)生有序文件D 置換某個(gè)記錄()20可在構(gòu)造一個(gè)散列文件。A 內(nèi)存B軟盤C磁帶D硬盤二、試用 2 種不同表示法畫出下列二叉樹B 1 的存儲結(jié)構(gòu)，并評述這2 種表示法的優(yōu)、缺點(diǎn)。 (共 10 分)二題圖 B1三題圖 G三、對圖 G：1 從頂點(diǎn) A 出發(fā)，求圖 G 的一棵深度優(yōu)先生成樹；2 從頂點(diǎn) B 出發(fā)，求圖 G 的一棵廣度優(yōu)先生成樹；3求圖 G 的一棵最小生成樹。(共

45、 12 分 ) 四、設(shè)哈希 (Hash)函數(shù)為： H(k)=kMODl4 ，其中 k 為關(guān)鍵字 (整數(shù) )， MOD 為取模運(yùn)算，用線性探測再散列法處理沖突，在地址范圍為014 散列區(qū)中，試用關(guān)鍵字序列(19， 27，26，28， 29， 40， 64， 21， 15， 12)造一個(gè)哈希表，回答下列問題：1畫出該哈希表的存儲結(jié)構(gòu)圖；2若查找關(guān)鍵字40，必須依次與表中哪些關(guān)鍵字比較大小？3假定每個(gè)關(guān)鍵字的查找概率相同，試求查找成功時(shí)的平均查找長度。(共13 分) 五、給定頭指針為ha 的單鏈表 A ，和頭指針為hb 的遞增有序單鏈表B 。試?yán)帽?A和表 B 的結(jié)點(diǎn)，將表 A 和表 B 歸并為遞增有序表 C，其頭指針為 hc，允許有相同 data 值 (數(shù) 據(jù)元素 )的結(jié)點(diǎn)存在，表 A ， B， C 均帶表頭結(jié)點(diǎn)。例如，給定：將它們歸并為：1在下列C 算法 merge 中有下劃線的位置填空，使之成為完整的算法，要求在填空后加注釋，以提高算法的可讀性。2假定單鏈表 A 和 B 的長度分別為