南京林業(yè)大學(xué)考研真題-數(shù)據(jù)結(jié)構(gòu)2004

朽木易折，金石可鏤。千里之行，始于足下。第頁(yè)/共頁(yè)南京林業(yè)大學(xué)2004年攻讀碩士學(xué)位研究生入學(xué)考試數(shù)據(jù)結(jié)構(gòu)試題注重事項(xiàng)：1.答案一律寫(xiě)在答題紙上；2.答案卷應(yīng)字跡清晰、語(yǔ)義確切；3.算法應(yīng)對(duì)主要數(shù)據(jù)類(lèi)型、變量給出說(shuō)明，所寫(xiě)算法應(yīng)結(jié)構(gòu)清晰、簡(jiǎn)明易懂，可加上須要的注釋?zhuān)?.算法可用（類(lèi)）PASCAL語(yǔ)言、C語(yǔ)言等你所認(rèn)識(shí)的高級(jí)語(yǔ)言編寫(xiě)，但要注明語(yǔ)種。單項(xiàng)挑選題（本大題共15小題，每小題2分，共30分）算法指的是（）。A．計(jì)算機(jī)程序B．解決問(wèn)題的計(jì)算主意C．排序算法D．解決問(wèn)題的有限運(yùn)算序列線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，結(jié)點(diǎn)的存儲(chǔ)地址（）。A．必須是不延續(xù)的B．部分地址必須是延續(xù)的C．延續(xù)與否均可D．和頭結(jié)點(diǎn)的存儲(chǔ)地址相延續(xù)若已知一個(gè)棧的入棧序列是1,2,3,…,n,其輸出序列為s1,s2,s3,…sn,若s1=n,則si為（）。A．iB．n=iC．n-i+1D．以上都不對(duì)算法的時(shí)光復(fù)雜度取決于（）。A．問(wèn)題的規(guī)模B．待處理數(shù)據(jù)的初態(tài)C．A與B都對(duì)D．算法的易讀性將兩個(gè)各有n1和n2個(gè)元素的有序表(遞增)歸并成一個(gè)有序表，仍保持其遞增順序，則最少的比較次數(shù)是（）。A．n1B．n2C．n1+n2-1D．min(n1,n2)一個(gè)非空廣義表的表頭（）。A．不可能是子表B．只能是子表C．只能是原子D．可以是子表或原子深度為6的二叉樹(shù)至多有（）個(gè)結(jié)點(diǎn)。A．32B．40C．63D．64下面哪一個(gè)主意可以判斷出一個(gè)有向圖中是否有環(huán)（回路）（）。A．廣度優(yōu)先遍歷B．拓樸排序

C．求最短路徑D．求關(guān)鍵路徑按照二叉樹(shù)的定義，具有3個(gè)結(jié)點(diǎn)的二叉樹(shù)有()種。A．3B．4C．5D．6在含n個(gè)頂點(diǎn)和e條邊的無(wú)向圖的鄰接矩陣中,零元素的個(gè)數(shù)為()。A．eB．2eC．n2－eD．n2－2e某二叉樹(shù)的先序序列和后序序列正巧相反，則該二叉樹(shù)一定是()的二叉樹(shù)。A．空或惟獨(dú)一個(gè)結(jié)點(diǎn)B．任一結(jié)點(diǎn)惟獨(dú)左孩子

C．高度等于其結(jié)點(diǎn)數(shù)D．任一結(jié)點(diǎn)惟獨(dú)右孩子一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖最多有()條邊。A．nB．n(n-1)C．n(n-1)/2D．2n用某種排序主意對(duì)關(guān)鍵字序列（25，84，21，47，15，27，68，35，20）舉行排序時(shí)，序列的變化情況如下：20，15，21，25，47，27，68，35，8415，20，21，25，35，27，47，68，8415，20，21，25，27，35，47，68，84則所采用的排序主意是（）。A．挑選排序B．希爾排序C．歸并排序D．迅速排序假設(shè)一個(gè)有n個(gè)頂點(diǎn)和e條弧的有向圖用鄰接表表示,則刪除與某個(gè)頂點(diǎn)vi相關(guān)的所有弧的時(shí)光復(fù)雜度是()。A．O(n)B．O(e)C．O(n+e)D．O(n*e)下述二叉樹(shù)中,哪一種滿(mǎn)意性質(zhì)：從隨意結(jié)點(diǎn)出發(fā)到根的路徑上所經(jīng)過(guò)的結(jié)點(diǎn)序列按其關(guān)鍵字有序：（）。A．哈夫曼樹(shù)B．AVL樹(shù)C．堆D．二叉排序樹(shù)填空題：（本大題共15小題，每小題2分，若有兩個(gè)空格，每個(gè)空格1分，共30分）1．評(píng)價(jià)算法的效率性能從利用計(jì)算機(jī)資源角度看主要從和兩個(gè)方面舉行分析。2．有一個(gè)含頭結(jié)點(diǎn)的單重循環(huán)鏈表，頭指針為head,則判斷其是否為空的條件為：。3．用數(shù)組Queue（其下標(biāo)在0～n-1中，共有n個(gè)元素）表示一個(gè)循環(huán)隊(duì)列，front為當(dāng)前隊(duì)頭元素的前一位置，rear為隊(duì)尾元素的位置。假定隊(duì)列中元素個(gè)數(shù)總小于n，則隊(duì)列中元素個(gè)數(shù)為：。4．設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素a,b,c,d,e,f依次通過(guò)棧S，一個(gè)元素出棧后即進(jìn)入隊(duì)列Q。若這6個(gè)元素出隊(duì)列的順序是b,d,c,f,e,a,則棧S的容量至少應(yīng)該是。5．設(shè)n行n列的上三角矩陣A已壓縮存儲(chǔ)到一維數(shù)組B[1..n*(n+1)/2]中，且按行為主序存儲(chǔ)，則aij對(duì)應(yīng)的B中的存儲(chǔ)位置為。6．從任何一個(gè)結(jié)點(diǎn)開(kāi)始都能勝利尋找其他結(jié)點(diǎn)的單鏈表是表。7．設(shè)SS[1..maxsize]為一個(gè)順序存儲(chǔ)的棧，變量top指示棧頂元素的位置，當(dāng)棧未滿(mǎn)時(shí)，將元素e壓入棧需執(zhí)行下列語(yǔ)句：和。8．所有結(jié)點(diǎn)的前驅(qū)和后繼的個(gè)數(shù)都沒(méi)有限制的數(shù)據(jù)結(jié)構(gòu)是結(jié)構(gòu)。9．若一個(gè)二叉樹(shù)的葉子結(jié)點(diǎn)，是某子樹(shù)的中序遍歷序列中的最后一個(gè)結(jié)點(diǎn)，則它必是該子樹(shù)的序列中的最后一個(gè)結(jié)點(diǎn)。10．用二分法尋找一個(gè)線性表時(shí)，要求線性表必須以方式存儲(chǔ)，且

。11．采用散列法實(shí)現(xiàn)尋找時(shí)，需要解決的主要問(wèn)題有：和。12．設(shè)廣義表L=（（（a））），則該廣義表的長(zhǎng)度是，深度是。13．有向圖G有n個(gè)頂點(diǎn){v1,v2,…,vn}，它的鄰接矩陣為A，A[i,j]=1表示vi到vj存在鄰接關(guān)系，而A[i,j]=0表示不存在鄰接關(guān)系。則G中頂點(diǎn)vi的度為。14．n個(gè)頂點(diǎn)的有向強(qiáng)連通圖用鄰接矩陣表示時(shí)，該矩陣至少有個(gè)非零元素。15．若一個(gè)二叉樹(shù)含有n個(gè)結(jié)點(diǎn)，則它的二叉鏈表中必有個(gè)空的鏈域。是非題：（判斷下列各題是否準(zhǔn)確，準(zhǔn)確的在括號(hào)內(nèi)打

“√”，錯(cuò)的打“×”。每小題2分，共20分）1．線性表的邏輯順序與存儲(chǔ)順序總是一致的。（）2．消除遞歸不一定需要使用棧。（）3．隊(duì)列是后進(jìn)先出的線性表。（）4．任何一個(gè)數(shù)據(jù)結(jié)構(gòu)至少有一個(gè)結(jié)點(diǎn)沒(méi)有前驅(qū)。（）5．將一棵樹(shù)轉(zhuǎn)換成二叉樹(shù)后，根結(jié)點(diǎn)沒(méi)有左子樹(shù)。（）6．若采用以行序?yàn)橹餍蛉M表示法存儲(chǔ)稀疏矩陣，只要把每個(gè)元素的行下標(biāo)和列下標(biāo)互換，就完成了對(duì)該矩陣的轉(zhuǎn)置運(yùn)算。（）7．對(duì)于不同的存儲(chǔ)結(jié)構(gòu)，應(yīng)采用不同的檢索主意。（）8．倘若一個(gè)二叉樹(shù)中沒(méi)有度為1的結(jié)點(diǎn)，則必為滿(mǎn)二叉樹(shù)。（）9．樹(shù)和二叉樹(shù)的邏輯結(jié)構(gòu)是一致的。（）10．不僅需要使用內(nèi)存，而且還要使用外存的排序稱(chēng)為外排序。（）解答題：（本大題共5小題，每小題4分，共20分）1．將算術(shù)表達(dá)式((a+b)+c*(d+e)+f)*(g+h)轉(zhuǎn)化為二叉樹(shù)。(注：括號(hào)無(wú)需在樹(shù)中浮上)2．子串的定位運(yùn)算通常稱(chēng)為串的模式匹配，是各種串處理系統(tǒng)中最重要的運(yùn)算之一，其中KMP匹配算法是效率較高的主意。請(qǐng)問(wèn)KMP匹配算法的基本思想是什么？求字符串’ababaababcabb’的NEXT數(shù)組。3．假設(shè)用下述兩種結(jié)點(diǎn)的鏈表作廣義表的存儲(chǔ)結(jié)構(gòu)：tag=1hp(表頭指針)tp(表尾指針)表結(jié)點(diǎn)tag=0data(值域)原子結(jié)點(diǎn)試畫(huà)出廣義表LA=((((a),b)),(((),(d)),(e,f)))的存儲(chǔ)結(jié)構(gòu)。4．（1）若一棵二叉樹(shù)先序遍歷與中序遍歷的次序分離為:先序序列:ABDEHCFGI；中序序列：DBEHAFCIG。試畫(huà)出這棵二叉樹(shù)。（2）給出二叉樹(shù)的先序和中序序列、中序和后序序列、先序和后序序列。試問(wèn)是否在任何情況下都可決定唯一的一棵二叉樹(shù)；若有不能者，請(qǐng)舉出一個(gè)反例說(shuō)明之。5．設(shè)有向圖G為：VV1V3V4V2寫(xiě)出所有的拓樸序列；在圖中添加一條弧，使得僅可能有唯一的拓樸序列。算法閱讀題：（本大題共2小題，每小題5分，共10分）1．設(shè)有算法如下:typedefintKeyType;typedefstruct{KeyTypekey;OtherTypeother_data;}ListType;voidfunction(ListTypeR[],intlength){inti,j;for(i=2;i<length;i++){R[0]=R[i];j=i-1;while(R[0].key<R[j].key){R[j+1]=R[j];j=j-1;}R[j+1]=R[0];}}請(qǐng)回答下面兩個(gè)問(wèn)題：（1）該算法的功能是什么？（2）這個(gè)算法是否穩(wěn)定？并請(qǐng)說(shuō)明你的理由。2．設(shè)有算法如下：#defineNULL0typedefstructnode{KeyTypekey;structnode*lchild,*rchild;}BSN,*BST;voidunknown(BST*bs,KeyTypekey){BSTs;

if(*bs==NULL){s=(BST)malloc(sizeof(BSN));s->key=key;s->lchild=NULL;s->rchild=NULL;*bs=s;}elseif(key==(*bs)->key)printf(“Thenodeexistsinthebinarytree!”);

elseif(key<(*bs)->key)

unknown(&((*bs)->lchild),key);

else

unknown(&((*bs)->rchild),key);}函數(shù)unknown實(shí)現(xiàn)了對(duì)二叉排序樹(shù)的一種運(yùn)算；（1）試說(shuō)明unknown的功能。（2）若root是BST型變量，且root指向如下二叉樹(shù)的根結(jié)點(diǎn)，試畫(huà)出執(zhí)行完unknown(root,‘X’)后，root指向的二叉樹(shù)。WWRYAZroot六、算法設(shè)計(jì)題：（本大題共3小題，共４0分）１．已知Q是一個(gè)非空隊(duì)列，S是一個(gè)空棧。僅用隊(duì)列和棧的ADT(抽象數(shù)據(jù)類(lèi)型)函數(shù)和少量工作變量，編寫(xiě)一個(gè)算法，將隊(duì)列Q中的所有元素逆置。（本題15分）其中：棧的ADT函數(shù)有：InitStack(S);將棧S初始化為空棧Push(S,x);新元素x進(jìn)棧Pop(S,&x);出棧，返回棧頂值給xintIsEmpty(