數(shù)據(jù)結(jié)構(gòu)清華大學(xué)模擬試題一答案數(shù)據(jù)結(jié)構(gòu)清華大學(xué)模擬試題一答案數(shù)據(jù)結(jié)構(gòu)清華大學(xué)模擬試題一答案清華大學(xué)模擬試題一一．單項選擇題（2分/題）1．一個棧的輸入序列為12345，則以下序列中是棧的輸出序列的是（）。知道這題的解題思路嗎？A.23415B.54132C.31245D.142532．設(shè)循環(huán)行列中數(shù)組的下標(biāo)范圍是1~n，其頭尾指針分別為f和r，則其元素個數(shù)為（）。A.r-fB.r-f+1C.(r-f)modn+1D.(r-f+n)modn3．二叉樹在線索化后，仍不可以有效求解的問題是（）。這題是線索化問題，可能你沒看過?？梢缘任胰ソo你講。A.先序線索二叉樹中求先序后繼B.中序線索二叉樹中求中序后繼C.中序線索二叉樹中求中序前驅(qū)D.后序線索二叉樹中求后序后繼4．求最短路徑的FLOYD算法的時間復(fù)雜度為（）。（那Djstla的時間復(fù)雜度呢？）A.O(n)B.O(n+e)C.O(n2)D.O(n3)5．一棵左右子樹不空的二叉樹在先序線索化后，其空指針域數(shù)為（）。（知道是哪個指針域嗎？就是最后一個接見的節(jié)點的右指針，由于它沒有后繼節(jié)點。）A.0B.1C.2D.不確立6．?dāng)?shù)組A[1..5,1..6]的每個元素占5個單元，將其按行優(yōu)先次序儲蓄在初步地點為1000的連續(xù)的內(nèi)存單元中，則元素A[5,5]的地點為（）。這題可要會喲@A.1140B.1145C.1120D.11257．在以下排序算法中，在待排序的數(shù)據(jù)表已經(jīng)為有序時，開支時間反而最多的是（）。(要知道為何，這個我跟你講過)A.迅速排序B.希爾排序C.冒泡排序

D.堆排序8．對有18個元素的有序表做折半查找，則查找A[3]標(biāo)挨次為（）。（這題的數(shù)組下標(biāo)應(yīng)當(dāng)說明一下是

的比較序列的下A[1..18]）A.1-2-3

B.9-5-2-3

C.9-5-3

D.9-4-2-39．以下排序算法中，某一趟結(jié)束后未必能選出一個元素放在其最后地點上的是（）。這些題出的都不錯！A.堆排序B.冒泡排序C.迅速排序D.直接插入排序10．在均衡二叉樹中插入一個結(jié)點后造成了不均衡，設(shè)最低的不均衡點為A，并已知A的左孩子的均衡因子為-1，右孩子的均衡因子為0，則做（）型調(diào)整以使其均衡。A.LLB.LRC.RLD.RR二．判斷題（1分/題）1.（）線性表的長度是線性表所占用的儲蓄空間的大小。2.（）雙循環(huán)鏈表中，隨意一結(jié)點的后繼指針均指向其邏輯后繼。3.（）在對鏈行列做出隊操作時，不會改變front指針的值。4.（）假如兩個串含有同樣的字符，則說它們相等。5.（）假如二叉樹中某結(jié)點的度為1，則說該結(jié)點只有一棵子樹。6.（）已知一棵樹的先序序列和后序序列，必定能結(jié)構(gòu)出該樹。7.（）圖G的一棵最小代價生成樹的代價未必小于G的其余任何一棵生成樹的代價。8.（）圖G的拓?fù)湫蛄歇氁?，則其弧數(shù)必為n-1（此中n為極點數(shù)）。9.（）對一個堆按層次遍歷，不用然能獲得一個有序序列。10.（）直接選擇排序算法知足：其時間復(fù)雜度不受數(shù)據(jù)的初始特色影響，為O(n2)。三．填空題（2分/空）1．已知完滿二叉樹的第8層有8個結(jié)點，則其葉子結(jié)點數(shù)是（68）。2．將下三角矩陣A[1..8,1..8]的下三角部分逐行地儲蓄到初步地點為1000的內(nèi)存單元中，已知每個元素占4個單元，則A[7,5]的地點是1100）。3．有n個極點的強連通有向圖G最罕有（n）條弧。4．有n個結(jié)點而且其高度為n的二叉樹的數(shù)量是（2n-1）。5．高度為8的均衡二叉樹的結(jié)點數(shù)最少是（54）。6．3個結(jié)點可組成（3）棵不同樣形態(tài)的樹。7．對以以下圖所示的網(wǎng)，履行prim算法可獲得最小生成樹，試在下表的空白處填上適合的內(nèi)容，以說明該算法的履行過程。極點134UV(U,V)(2,1)(2,3)(2,4){2}{1,3,4}1代價4215(U,V)(4,1)(2,3){2,4}{1,3}5代價5434(U,V)(3,1){2,4,3}{1}代價142(U,V){2,4,3,1}{}2代價8．設(shè)散列表函數(shù)為H(key)，用拉鏈法解決矛盾，H的值域為0,...,n-1，結(jié)構(gòu)的散列表種類以下：TYPElink=^node;node=RECORDkey:keytype;next:link;...END;openhash=array[0..n-1]oflink;K的結(jié)請在以下算法劃線處填上適合內(nèi)容，以達(dá)成查找鍵值等于點，若查找成功，返回該結(jié)點的指針，不然返回空指針。FUNCresearch(K:keytype;HP:openhash):link;i:=H(K);SUC:=false;p:=HP[i];while(p<>nil)andnot(SUC)doifp^.key<>Kthenp:=p^.nextelseSUC:=true;return(p)ENDC;{researsh}四．應(yīng)用題（5分/題）1．對下邊兩棵二叉樹，分別畫出它們的次序儲蓄結(jié)構(gòu)。AABCBCDEFGDEFIJKIJ123456789101234567891011ABCDEFGIJKABCDEFIJ2．設(shè)圖G=(V,E),V={1,2,3,4,5,6},E={<1,2>,<1,3>,<2,5>,<3,6>,<6,5>,<5,4>,<6,4>}。請寫出圖G中頂點的全部拓?fù)湫蛄小?---2---3---6---5---41253---2---6---5---43646---2---5---43．對下邊3階B-樹挨次履行以下操作，畫出每步的操作結(jié)果。插入300100（1）插入7050200（2）插入303）刪除15010406080150260（1）1005020010406080150260300（2）1005070200104060801502603003）501003070200104060801502603004）501003070260104060802003004．求出下邊AOE網(wǎng)中的重點路徑，要求注明每個極點的最早和最遲發(fā)生時間，并畫出重點路徑。267627453344533545451382105422310618466622542547947912345678910e0454101113141318五．算法設(shè)計題（10分/題）1．設(shè)計算法將一個帶頭結(jié)點的單循環(huán)鏈表A分解為兩個擁有同樣結(jié)構(gòu)的鏈表B和C，此中B表中結(jié)點為A表中值為奇數(shù)的結(jié)點，而C表中結(jié)點為A表中值為偶數(shù)的結(jié)點（要求利用原表結(jié)點）。算法思想：B表頭結(jié)點利用A表頭結(jié)點；為C表產(chǎn)生一個頭結(jié)點。從A的首元結(jié)點檢查每個結(jié)點應(yīng)插入B表仍是C表，進(jìn)而從A表取下，做響應(yīng)的插入操作。設(shè)節(jié)點定義以下：structnode{intkey;structnode*next;}則算法以下：voidgive_b_c( ){structnode*B,*C;B=A;//此刻B和A是一回事，馬上奇數(shù)留下，偶數(shù)取出來放到C中C=(structnode*)malloc(sizeof(structnode));p1=B;p2=p1->next;q=C;//p1p2是B上的工作指針q是

C上的工作指針while(p2!=B){if(p2->keymod2==0)

//偶數(shù)則放入

C中{p1->next=p2->next;q->next=p2;q=p2;p2=p1->next}else{p1=p2;p2=p1->next;}

奇//數(shù)則不變}q->next=C;}2．設(shè)計算法判斷無向圖G是不是連通的，若連公則返回true，不然返回false?？梢允褂靡韵聨讉€函數(shù)調(diào)用：firstadj(G,v)—返回圖G中極點v的第一個毗鄰點，若不存在返回0nextadj(G,v,w)—返回圖G中極點v的毗鄰點中處于w今后的毗鄰點，若不存在返回0nodes(G)—返回圖G中的極點數(shù)算法思想：從某個極點出發(fā)深度/廣度遍歷。設(shè)協(xié)助數(shù)組visited[max]則算法以下：booltotal_search_dfs(GraphG)//這里bool的定義缺省了，這是算法與程序的差異{for(i=0;i<node(G);i++)visited[i]=false;son_search_dfs(G,0);從//第一個元素開始深度遍歷，自然，從任何一個都行for(i=0;i<node(G);i++)if(visited[i]==false)returnfalse;returnture;}voidson_search_dfs(GraphG,inti){visited[i]=true;p=firstadj(G,i);while(p){ifvisited[p->adjvex]==falseson_search_dfs(G,p->adjvex);p=nextadj(G,i,p)}}3．已知數(shù)組A[1..n]的元素遞加有序，試設(shè)計算法以數(shù)組造一棵二叉排序樹，并使其知足均衡二叉樹的條件。算法思想：遞歸算法，以居中的元素作為根結(jié)點。設(shè)二叉樹節(jié)點結(jié)構(gòu)定義以下：

A中的元素構(gòu)structnode{structnode*lchild,*rchild;intkey;}則算法以下：voidget_sort(structnode*root;intlow,high){root=null;while(low<=high){mid=(low+high)/2;root=(structnode*)malloc(sizeof(structnode));root->key=A[mid];get_sort(root->lchild,low,mid-1)