全國名校數(shù)據(jù)結(jié)構(gòu)考研真題匯編

55563383372588-1^333444555555563383372588-1^333444555536O44837718518S-58O446&777788899OII22233422f229p??29>?n^1nnaaA1nn目錄1,北京航空航天大學(xué)數(shù)據(jù)結(jié)構(gòu)。C語言程序設(shè)計歷年考研真題 2013年北京航空航天大學(xué)991數(shù)據(jù)結(jié)構(gòu)與C語J程序設(shè)計考研真題2012年北京航空航天大學(xué)991數(shù)據(jù)結(jié)構(gòu)與C語才程序設(shè)計考研出題2011年北京航空航天大學(xué)991數(shù)據(jù)結(jié)構(gòu)。C語言程序設(shè)計考研真題.中國傳媒大學(xué)數(shù)據(jù)結(jié)構(gòu)。計眸機M絡(luò)歷年考研真題 2014年中國傳媒大學(xué)821數(shù)據(jù)結(jié)構(gòu)與計算機網(wǎng)絡(luò)考研真題 2013年中國傳媒大學(xué)821數(shù)據(jù)結(jié)構(gòu)與計算機網(wǎng)絡(luò)考研真題 .上海海事大學(xué)數(shù)據(jù)結(jié)構(gòu)歷年考研真題 2014年上海海事大學(xué)821數(shù)據(jù)結(jié)構(gòu)考研出題 2013年上海海事大學(xué)821數(shù)據(jù)結(jié)構(gòu)考研其題 2012年上海海事大學(xué)821數(shù)據(jù)結(jié)構(gòu)考研真題 2011年上海海事大學(xué)821數(shù)據(jù)結(jié)構(gòu)考研真題 .浙江理匚大學(xué)數(shù)據(jù)結(jié)構(gòu)歷年考研我題 2014年浙江理工大學(xué)991數(shù)據(jù)結(jié)構(gòu)號研真題 2013年浙江理工大學(xué)991數(shù)據(jù)結(jié)構(gòu)考研支牌 2012年浙江理工大學(xué)991數(shù)據(jù)結(jié)構(gòu)考研真腮 2011年浙江理1：大學(xué)991數(shù)據(jù)結(jié)構(gòu)考研真題 .武漢科技大學(xué)數(shù)據(jù)結(jié)構(gòu)（C語言版）歷年號研真題 2014年武漢科技大學(xué)856數(shù)據(jù)結(jié)構(gòu)（C語汴版》A誅考研也題2013年武漢科技大學(xué)856數(shù)據(jù)結(jié)構(gòu)（C語言版）A卷考研我題........2013年武漢科技大學(xué)856數(shù)據(jù)數(shù)構(gòu)（C語言版）B卷考研真劇 .中山大學(xué)專業(yè)基礎(chǔ)（數(shù)據(jù)結(jié)構(gòu)）歷年考研真題 2015年中山大學(xué)9185業(yè)送礎(chǔ)（數(shù)據(jù)結(jié)構(gòu)）考研真題 2014年中山大學(xué)912?業(yè)基礎(chǔ)（數(shù)據(jù)結(jié)構(gòu)）考研我題 2013年中山大學(xué)867專業(yè)威礎(chǔ)（數(shù)據(jù)結(jié)構(gòu)）考研出題 2012年中山大學(xué)909專業(yè)甚礎(chǔ)（數(shù)據(jù)結(jié)構(gòu)）苕研收題 2012年中山大學(xué)913專業(yè)版礎(chǔ)（數(shù)據(jù)結(jié)構(gòu)）考研真題 2011年中山大學(xué)9”專業(yè)星礎(chǔ)（數(shù)據(jù)結(jié)構(gòu)）考研真題 .沈陽航空航天大學(xué)數(shù)據(jù)結(jié)構(gòu)專業(yè)綜合歷年考研我題 2014年沈陽航空航天大學(xué)805數(shù)據(jù)結(jié)構(gòu)C業(yè)綜合專研真題 2013年沈陽航空航天大學(xué)80S數(shù)據(jù)結(jié)構(gòu)專業(yè)綜合考研出題 2012年沈陽航空航天大學(xué)818/數(shù)據(jù)結(jié)構(gòu)專業(yè)探合考研出題 .其他名校數(shù)據(jù)結(jié)構(gòu)歷年考研真題 2011年暨南大學(xué)信息科學(xué)技術(shù)學(xué)院83（）數(shù)據(jù)結(jié)構(gòu)考研瓦通 說明：精選了26套名校數(shù)據(jù)結(jié)構(gòu)歷年考研直題.次大學(xué)數(shù)據(jù)結(jié)構(gòu)與(語言程序設(shè)計歷年考研真愿2013年北京航空航天大學(xué)991數(shù)據(jù)結(jié)構(gòu)與<"語言程序設(shè)計考研UHI北京航空航天大學(xué)2013年

碩士研究生入學(xué)考試試題科目代碼：991數(shù)據(jù)結(jié)構(gòu)與C語言程序設(shè)計(共1。貯考生注意：所有答題務(wù)必書寫在考場提供的答題紙上，寫在本試題單上的答題一律無效(本題單不參與閱卷，一、第項選擇題(本題共20分，每小題各2分)I.對于長度為n的線性表，建立其對應(yīng)的單鏈表的時間復(fù)雜度為.A.0(1)： B.O(log2n)：C.O(n)； D.O(n2)..一般情況下，在一個雙向鏈表中插入一個新的鏈結(jié)點，,A.需要修改4個指針域內(nèi)的指針；B.需要修改3個指針域內(nèi)的指針；C.需要像改2個指針域內(nèi)的指針： D.只需要修改1個指針域內(nèi)的指針..假設(shè)用單個字母表示中級表達式中的一個運算數(shù)(或稱運算對象)，并利用堆棧產(chǎn)生中綴表達式對應(yīng)的后綴表達式.對于中級表達式A+BnC/D-E),當(dāng)從左至右掃描到運算數(shù)E時，堆棧中的運算符依次是?(注：不包含表達式的分界符)A.+*/-{ B.+?(/-: C.+*-t D.+?(-4.若某二叉排序樹的前序遍歷序列為50,20,40,30,80,60,70,則后序遍歷序列為.A.30,40,20.50,70,60,80： B.30,40,20,70,60,80,50：C.70,60.80,50,30.4020； D.70,60,80.30.40,20,50.5.分別以6,3,8,12,5,7對應(yīng)葉結(jié)點的權(quán)值構(gòu)造的哈夫曼(Huffman)樹的深度為.A.6； B.5； C.4； D.3.6.下列關(guān)于圖的敘述中，錯誤的是,A.根據(jù)圖的定義.圖中至少有一個頂點；

B.根據(jù)圖的定義，圖中至少有一個頂點和一條邊(弧)；C.具有n個頂點的無向圖最多有nx(n-l)/2條邊：D.具有n個頂點的有向圖最多有nx(n-l)條邊(弧)?.若在有向圖G的拓撲序列中，頂點v,在頂點”之前，則下列4種情形中不可能出現(xiàn)的是。G中有?。紇“vj＞：G中沒有?。紇“Vj＞：G中有一條從頂點v,到頂點”的路徑：G中有一條從頂點,到頂點%的路徑..下列關(guān)于查找操作的敘述中，錯誤的是.A.在麻序表中查找元素可以采用順序查找法，也可以采用折半查找法；B.在鏈表中查找結(jié)點只能采用順序杳找法,不能采用折半杳找法：C.一般情況下,順序查找法不如折半查找法的時間效率高；D.折半查找的過程可以用一棵稱之為“判定樹”的二叉樹來描述.9.在一啾m階B-樹中，除根結(jié)點之外的任何分支結(jié)點包含關(guān)鍵字的個數(shù)至少是.A.m/2-l；B.m/2j C.Fm/2\~1； D.「m/21.10.若對序列(49,38,65,97,76,13,27.49)進行快速排序，則第一趟排序結(jié)束(即確定了第I個分界元素的最終位置)時，序列的狀態(tài)是,A.(13,27,49\38,49,76,97,65)； B.(13,38.27.49\49,76.97.65)；C.(13,38,49,,27,49,97,76,65)： D.(13,38,49\27.49,76,97,65).二、境空題(本題共20分，每小題各2分).非空線性表在采用存儲結(jié)構(gòu)的情況下，刪除表的一個數(shù)據(jù)元素平均需要移動表中近一半元素的位置..將一個長度為n的單鞋表鏈接到一個長度為m的單鏈表后面，該算法的時間復(fù)雜度用大O符號表示為,.若完全二叉樹的葉結(jié)點的數(shù)目為k,且最下面一層的結(jié)點數(shù)大于1.則該完全二叉樹的深度為?.若深度為8的完全二叉樹的第7層有10個葉結(jié)點，則該二叉樹的結(jié)點總數(shù)為..在具有n個頂點的有向圖中,每個頂點的度最大可以達到?.若對有向圖進行拓撲持序，則能夠得到拓撲序列的條件是..已知長度為10的順序表中數(shù)據(jù)元素按值從小到大排列.若在該表中進行折半查找.則平均查找長度（ASL）是..若在一棵m階B-樹的某個結(jié)點中插入一個新的關(guān)凝字值而引起結(jié)點產(chǎn)生分戮.則該結(jié)點中原有的關(guān)鍵字值的數(shù)目是..有一種排序方法可能會出現(xiàn)這種情況：最后一趟排序開始之前,序列中所有的元素都不在其最終應(yīng)該在的位置匕這種摔序方法是..若按照泡持序法的思想將序列（2,12,16.5,10）中元素按值從小到大進行排序，整個排序過程中所進行的元素之間的比較次數(shù)為?三、綜合題（本題共20分，每小題各S分）.般情況下，當(dāng)一個算法中需要建立多個堆棧時可以選用下列三種處理方案之一.問：這三種方案之間相比較各有什么優(yōu)點和缺點？（1）多個堆棧共享一個連續(xù)的存儲空間；（2）分別建立多個采用順序存儲結(jié)構(gòu)的堆棧：（3）分別建立多個采用鏈式存儲結(jié)構(gòu)的堆棧..已知二叉樹采用二叉鏈表存端結(jié)構(gòu)，根結(jié)點指針為T,鏈結(jié)點類型定義為：typedefstructnode{chardata; /?數(shù)據(jù)域?/structnode?Ichild.?rchild; Ze指向左、右子樹的指針域?/）?BTREE；第9913頁下面的算法的功能是輸出二叉樹中所有葉結(jié)點的數(shù)據(jù)信息.請在算法的空白處（方框內(nèi)）填入合適內(nèi)容,使算法完整.voidFUNCfBTREET）（ifTT!=NULL）{ifiCZZJprintfC*%c”,T->data）;FUNCdFUNCdb；|}.對給定AOE網(wǎng)（如題三3圖所示），請完成（1）分別求出各活動困6=1.2,…，［4）的最早開始時間與最晚開始時間：（請以表格形式給出結(jié)果）（2）求出所有關(guān)罅路徑.（請以圖形方式畫出各關(guān)鍵路徑）題二3圖.已知要將給定的關(guān)鍵字值序列（42,51,16.26,50,25,37,68,64,33,18）進行散列存儲，并且要求裝填因子（也稱負我因子）030.61,（1）請利用除留余數(shù)法構(gòu)造出合適的散列函數(shù)；（2）請畫出利用該散列函數(shù)依次將序列中各關(guān)鍵字值插入到散列表以后表的狀態(tài).設(shè)散列表初始為空，并且采用線性探測再散列法處理散列沖突.四、算法設(shè)計題（本題15分）假設(shè)長度為n的順序表A［L.n］中每個數(shù)據(jù)元素為一整數(shù)，請寫出按照下列思想將表

中數(shù)據(jù)元素按值從小到大進行排序的算法：第I趟排序?qū)⒆钚≈翟胤旁贏（l］中，城大

第99卜4頁值元素放在A[n]中：第2趟排序?qū)⒋涡≈翟胤旁贏[2J中，次大值元素放在A[n-1]中；……，依此下去，直至排序結(jié)束。五、填空題(本題共20分，每小題各2分).已知某等比數(shù)列的第一項即為I,公比為3,F列程序的功能是諭出該數(shù)列中小于1000的最大項an及其對應(yīng)的n.請在程序的空白處(方框內(nèi))填入合適內(nèi)容，使程序完整。main(){intn=l,a=l,q=3;whiie(i){a=a*q;n-H-;if(a>=1000)} printf(“n=%d,a=%d\n”,nT,|b;}.下列遞歸函數(shù)FUNC2的功能是判斷整型數(shù)組a[n]是否為遞增數(shù)組，即判斷數(shù)組的元素是否按值從小到大排列.若是一個遞增數(shù)組，則函數(shù)返回true,否則，函數(shù)返回false.請在函數(shù)的空白處(方框內(nèi))填入合適內(nèi)容，使函數(shù)完整。boolFUNC2(inta[].intn){if(n—1)returntrue;ifi[n=2)return|'匕return ]&&(a[nl)>=a[n-2]);).下列程序的功能是主函數(shù)調(diào)用FUNC3函數(shù)求方陣a中兩條對角線上元素之和.請在程序的空白處(方框內(nèi))填入合適內(nèi)容，使程序完整."defineN10voidFUNC3(inta[N][N],ini*p,int*q){inti;*P=0;*q=O；fbr(i=O;i<N;i++){*p=*p+C匚二□)；*q=*qM*【D;})main(){inta(N](N],i,j,x,y;for(i=0;i<N;i++)fortjaO;j<N;j++)scanf("％d”，YaT+j);FUNC3(a,&x,&y); /*x,y中分別存放主對角線與副對角線上的元素之和?/printfT*%d,%d\n'\x,y);}4.下列程序的功能是先通過鍵盤輸入一正整數(shù),然后調(diào)用一遞歸函數(shù)FUNC4.該函數(shù)將正整數(shù)轉(zhuǎn)換為對應(yīng)的數(shù)字字符組成的字符串顯示在屏幕上.例如：若輸入的正整數(shù)為583,則屏幕上顯示的是字符串583?請在程序的空白處(方框內(nèi))填入合適內(nèi)容，使程序完整。#include<std沁.h>voidFUNC4(intn){inti;i=n/10;-bFUNC4(i);putchardb；)main(){intn;printR”請輸入一正整數(shù)n：”)；scanff%1”,&n);prinlR”轉(zhuǎn)換后的字符串是：'*)；FUNC4(n);)5.下列程序的功能是將小寫字母轉(zhuǎn)換成對應(yīng)的大寫字母后的第2個字母，例如：將a轉(zhuǎn)換成C,將b轉(zhuǎn)換成D.其中,y轉(zhuǎn)換成A,z轉(zhuǎn)換成B?請在程序的空白處(方框內(nèi))填入合適內(nèi)容,使程序完整.#include<stdio.h>main(){charch;while((ch=getchar())!="')if(ch>=ta,&&ch<?*z*)(-&&ch<=Z+2)rzzzt}}.下列函數(shù)FUNC6的功能是刪除字符串s中的所有空白字符，包括Tab字符、回車符以及換行符.請在函數(shù)的空白處(方框內(nèi))填入合適內(nèi)容，使函數(shù)完整.#include<stdio.h>/include<string.h>/include<ctype.h>FUNC6(char*s){inti,t;charc(80];fbr(i=O,t^O;s[i];i++)>f(!isspace(jb)c[| [Wil；c[t]=,\O,;strcpy(s,c);.下列程序的功能是判斷輸入的字符串是否是“回文二(注：按順序讀與按逆序讀都一樣的字符串被稱為“回文'例如：abcdcba).請在程序的空白處(方框內(nèi))填入合適內(nèi)容，使程序完整，#include<stdio.h>#include<string.h>main(){charch[81].*p=ch.eq;gcts(p);qw{4whiledi**ps?q){p++；q-；}elsebreak;)iRp<q)prinifC該字符串不是回文！\ntt);elseprintR”該字符串是回文！VT);).下列程序的功能是：對于字符類型變量ch=108,保留中間兩位，而將高、低3位清零.請在程序的空白處(方框內(nèi))填入合適內(nèi)容，使程序完整.main(){charch;ch=108;chdkprintfl[1*%d,\ch);}.設(shè)file為存放了整型數(shù)據(jù)的二進制文件.下列程序的功能是從該文件中讀入第3個數(shù)據(jù)輸出到屏幕上.請在程序的空白處(方框內(nèi))填入合適內(nèi)容，使程序完整./include<stdio.h>main(){FILE*fp;ininumber;fphfbpen(“file”,"rb")：fscek(fp.|—ISEEK_SET);freaddL2,1,fp);printfC*%d”.number);fclose(fp);)10.下列程序的功能是將一個磁盤中的二進制文件復(fù)制到另一個磁盤中.兩個文件的文件名隨命令行一起輸入，輸入時原有文件的文件名在前，新復(fù)制文件的文件名在后.請在程序的空白處(方框內(nèi))填入合適內(nèi)容，使程序完整./include<stdio.h>main(intargc,char*argv[]){FILE*old,*new,if(argc!=3)(printff'Youforgottoenterafilename!\nM);exit(0);} if((old=fopen(||)=NULL){printffCannotopeninfile!\n*');exit(0);)if((new=fopen(| b==NULL){printf(4*Cannotopenoutfl】e!\n");exit(0);)while(!feof(old))iputc(fgetc(old).new);fciosefold);fclose(new);)六、簡答題(本題共20分，每小題各5分).在C語言中，函數(shù)調(diào)用時數(shù)據(jù)的傳遞通常有哪幾種方式？.在C語言中，指針可以做哪些運算？.共用體(union)具有哪些基本特征？.使用文件的基本操作步驟是怎樣的？七、程序設(shè)計題(本題15分)請編寫一程序，該程序的功能是找出并且刪除一維整型數(shù)組a[lOOJ中的最小值兀素.要求：①數(shù)組各元素通過鍵盤輸入獲得初值；②所有對數(shù)組元素的引用必須通過指針完成.八、程序設(shè)計題(本題20分)請僅編寫出一C語言函數(shù)char*maxword(char*s,char*t).該函數(shù)的功能是求出字符串s與字符串t的最長公共單詞(這里，假設(shè)兩個字符串均由英文字母和空格字符組成):若找到這樣的公共單詞，函數(shù)返回該單詞，否則，函數(shù)返回NULL.例如：若s="ThisisCprogrammingtext",X'ThisisatextforCprogramming”.則函數(shù)返回“programming".要求：①函數(shù)中不得設(shè)胃保存單詞的存儲空間：②給出函數(shù)之前請用文字簡要敘述函數(shù)的基本思想.2012年北京慶大學(xué)W12012年北京北京航空航天大學(xué)2012年

碩士研究生入學(xué)考試試題科目代碼，991數(shù)據(jù)結(jié)構(gòu)與C語言程序設(shè)計(共■頁)考生注意：所有答題務(wù)必書寫在考場提供的答題紙上，寫在本試題單上的答題i律無效(本題單不參與閱卷)。一、填空題(本題共20分，每小題各2分)I.從總體上說,“數(shù)據(jù)結(jié)構(gòu)”課程上要研究二個方面的內(nèi)容..若對某線性表最常用的操作是在友中插入元素或行刪除表中元素,則對丁西序在儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)這兩種存儲結(jié)構(gòu)血言,線性表應(yīng)該采用..在長度為n的II?空隊列中進行插入或為刪除操作的時間復(fù)雜度用KO符號表示為..若一棵度為4的樹中度為I、2,3和4的結(jié)點個數(shù)分別為4、2、1和1,則該樹中葉結(jié)點的個數(shù)為?.若某二叉樹的中序遍歷序列為B,A,F,D,(iC,E,按2次遍歷序列為A.B,C,D,E￡G.則該二叉樹的后序遍歷序列為..將一株結(jié)點總數(shù)為n、且具有m個葉結(jié)點的樹轉(zhuǎn)換為一株二義樹以后，儂二叉樹中右干樹為空的結(jié)點有個..對于圖G=(V.E)與G-(V,E),若有VVV,EeE,則稱G.是G的?.在順序表(6.15,30,37.65,68.70,72,89,99)中采用折半查找法查找元素37.與表中進行過比較的元素依次是..若已知n個關(guān)鍵字值具有相同的散列函數(shù)值，并且采用線性探測再做列法處理沖突，那么，將這n個關(guān)穰字值全部散列到初始為空的地址空間中.發(fā)生散列沖突的次數(shù)是..若長度為n的序列Krk1,k?,…人）當(dāng)且僅當(dāng)滿足kWk%并fl.kWk2+（lWiWln/2b時,則稱該序列為個小頂堆枳（Heap）.根據(jù)該定義，序列（26577161」5,⑼對應(yīng)的小預(yù)堆枳是?二、簡答題（本題共20分，每小題各5分）.如果?個具有100個頂點、200條邊的令向圖采用鄰接知陸存儲,該鄰接他陣是否是稀班矩陣？為什么？（這中我們假設(shè)：當(dāng)矩陣中非零元素的數(shù)目小r整個能防總元素的數(shù)口的5%時認為該矩陣為稀疏矩陣）. 般情況卜,建立散列表時難以避免出現(xiàn)散列沖突，常用處理收列沖突的方法之一是開放定址法，以力法的基木思想是什么？.若對序列（2.12,16,88510）按值從小到大進行排序，前二趟排序的結(jié)果分別為：第道排序的結(jié)果：（2,12.16510、88）笫一趟排序的結(jié)果：（2J2510.I6,88）第二趟排序的結(jié)果：（2510.12,16,88）請問：該結(jié)果是采用了選擇排序法還是采用廣（起）泡撐序法得到的？為仰么？.快速排序法的排序過程是遞歸的,若待排序序列的長度為n,則快速描序的戢小遞歸深度。最大遞6深度分別是多少？三、綜合題（本題共20分，每小題各5分）.若非空雙向循環(huán)錐表中鏈結(jié)點結(jié)構(gòu)為llinkdaia|rlink,則依次執(zhí)行下刖4條語句的H的是在該鏈表中由q指的結(jié)點后面插入一個由p指的結(jié)點，其中1條語句有錯誤，請找出該語句，并寫出正確的語句.p->llink=q; /*第1 條語句?/p->rlink=q->rlink; /*第2 條語句?/q->rlink可； /?第3條語句?/q->r!ink->llink=p; "第4 條語句?/.已知某完全二叉樹的第7層有10個葉結(jié)點，請求出該完全一叉網(wǎng)的結(jié)點總數(shù)的最大值.（要求寫出結(jié)論的求解過科）.證明:具有n個頂點的無向圖最驛有nx(n-lX2條邊..請分別寫出對數(shù)據(jù)元素序列(8U.3O.5O.1O.9O.2O)按位從人到小進行選掙排序時每一超的排序結(jié)果。四、算法設(shè)計題(本題15分)已知某具有n個頂點的有向圖采用鄰接表方法存儲，其中,用以存儲有向邊信息的邊結(jié)點類型為typedefstructedge(intadjvex; /?某有向邊的終止頂點在頂點結(jié)點中的位置?/structedge*next; /?指向下?個邊結(jié)點?/}ELink;用以存儲頂點信息的頂點結(jié)點類型為typedefstructver{intindegree; /*某頂點的入度*/vertypevertex; /*某頂點的數(shù)據(jù)信息*/ELink*!ink; /*指向以該頂點為出發(fā)點的第一個邊結(jié)點*/}VLink:井fin個頂點結(jié)點構(gòu)成個數(shù)組結(jié)構(gòu)G[0..n-l],清寫一個算.法，該算法判斷給定的頂點序列V[0..nIMvi^vj..…,V。}是否是該有向陰的一個拓撲序列,若是沒有向圖的一個拓撲序列，算法返PH，否則，算法返F10.五、單項選擇題(本題共2Q分，每小蛙各2分).在C語旨中，標識符只能由字母、數(shù)字和卜劃線三種字符組成，并FL第個字符?A.必須是字母 B,必須是下劃線C.必須是字母或者下劃線 D.可以是字母、數(shù)字和卜劃線之.若整型變量x的初值為6,則計算表達式“x+=x-r*x”之后，x的值是.A.50 B.60 C.-50 D.-60.卜.列4個程序段中，不是無限循環(huán)的是?A.fbr(b=O.a=l;a>++b;a=kH)k=a: B.fbr(;;a++=k);C.while(l){a+>;} D.fbrfk^lO;.k-)total+=k;4.說明“double(*pir)(N];”中的標識符ph?是.A.N個指向double類型變鬣的指針B.指向N個double類型變后的函數(shù)指針C.一個指向由N個double類型元素組成的維數(shù)組的指針D.具有N個指針元素的維指針數(shù)組，其每一個元素都只能指向double類型變量5.5列4個敘述中，正確的是.char*r="china”;等價于char*r;*尸“china”；char*ptr="china”;等價Tchar*ptr;ptr,china''：charstring[10]={"china"};等價于charstring。。];string[產(chǎn){“china"):charslr[4]="abc”.temp(4]="abc";等價Jcharstr[4|=temp(4]=Mabc,';.在C程序中，語句"char*fiinc(intx,inty);"表示?A.對函數(shù)func的定義 B.對函數(shù)func的調(diào)用C.對函數(shù)func返回值類型的說明D.對函數(shù)func的原型說明.對于下列程序，若從健盤上輸入：abcdef<|可車>，則輸出結(jié)果是./include<stdio.h>/include<malloc.h>main(){char*p,*q;p=(char?)malloc(sizeofl(char)*20);q=p;scanf(tl%s%s,,,p,q);printR"%s%s\n”,p,q);}A.demef B.abedefC.abcd D.dd8.當(dāng)說明一個結(jié)構(gòu)體變量時系統(tǒng)分配給它的內(nèi)存是.A.結(jié)構(gòu)中最后一個成員所需的內(nèi)存基.結(jié)構(gòu)中第一個成員所需的內(nèi)存量C.成員中占內(nèi)存量最大者所需的容量D.各成員所需內(nèi)存量的總和.下列程序的輸出結(jié)果為/defineABC(x)x*xmain()inta,k=3;a=++ABC(k+i);printf(y,a);)A.8 B.9 C.14 D.1710.若要以a+方式打開一個已經(jīng)存在的文件，則下列敘述中,正確的是 -A.文件被打開時，原有的文件內(nèi)容不破刪除，位置指針移動到文件的末尾,可進行添加和讀操作B.文件被打開時,原有的文件內(nèi)容不被刪除,位置指針移動到文件的開頭，可進行重寫和讀操作C.文件被打開時，原有的文件內(nèi)容被刪除，只能進行寫操作D.以上三種說法都不正確六、簡答題(本題共20分，每小題各5分).在C語言中，頭文件的作用是什么？.在C語占中，^include"Rlenamc.h”和#include〈filename.h＞的區(qū)別是什么？.在C語言中，全局變量和局部變量的主要區(qū)別是什么？.字符指針,浮點數(shù)指旬,以及函數(shù)指針這三種類型的變做哪個占用的內(nèi)存最大？為什么？七、填空題（本題共20分，每小題各2分）.下列代碼的功能包括：定義一個x數(shù)組,說明一個結(jié)構(gòu)體，同時對變出t進行初始化,使得[的a成員的值為50.b成員的值為x數(shù)組的首地址?請在空臼處（方框內(nèi)）填入合適的內(nèi)容，以完成上述功能?intx[5]={l,2,3,4,5）；struct{*b*.下列函數(shù)的功能是根據(jù)公式I1I I產(chǎn)1-丁?了-7+….計算s的值，其中.n通過形參傳人（nM）,計算結(jié)果通過形參指針傳回.請在函數(shù)的空白處（方框內(nèi)）填入合適的內(nèi)容，使函數(shù)完整，voidfun（float*snjntn）{floatsWkwQl;inti：for（i=0;i<=n;H^）{■①kW=一②]；s+=w;}*sn=s;）.卜列程序?qū)崿F(xiàn)將輸入的一個小寫字母循環(huán)后移5個位If后輸出?例如，若輸入字則輸出字母若輸入字母則輸出字母I、請在程序的空白處（方框內(nèi)）填入合適的內(nèi)容，使桿印完整，tfinclude<stdio.h>main(){charc;c-getchar():&&r?3elsei^c>?*vw&&c<=*z')~￥~lputcharfc);).下列自定義函數(shù)的功能是實現(xiàn)兩個字符小的比較.請在函數(shù)的空白處(方機內(nèi))填入合適的內(nèi)容,使函數(shù)完整intsstrempfehar*s,char*t){while(*s&&*t&&*s=={①t){s++;t+*；)relum②卜I.下列程序的功能是將已先按升序排好序的兩個字符串sir!和slr2中的字行再拉升序歸并到字符串str3中.請住程序的空白處(方框內(nèi))填入合適的內(nèi)容，使程序完整，/include<stdio.h>main(){charstrl[]=*'acegikin";charstr2("bdihjlnpq";charstr3(],*p；inti=Oj=O,k=O;whil?strlli]!=W&&str2[j]!-,\0'){insirl[i]<str2D])str3|k]=strHi++|;elsek++;)str3[k產(chǎn)'\0'；ifj@~bp=str2+j;elsep=stri+i;strcat(str3,p);puts(str3);).對于卜列main函數(shù)，經(jīng)過編譯、連接后得到的可執(zhí)行文件名為file.exe,并且已知在系統(tǒng)的命令狀態(tài)下輸入命令行“用cBeijingShanghai<[^車>”后得到的飾出結(jié)果是BeijingShanghai請在函數(shù)的空白處(方程內(nèi))填入合適的內(nèi)容，使函數(shù)完整.main(intargc.char*argv[J)(while(j①b{++argv；pnnt.%^”]②卜-argc;}}7.下列程序的功能是打開兩個已存在的文件filel和file2,并將file2拼接到filel的后面.請在程序的空門處(方椎內(nèi))填入合適的內(nèi)容，使程序完整.#include<sidio.h>inimain(){FILE*fpl/fp2:ifl(fpl=fbpcnC*fiIe1f①UIL){printfC'Cannotopenfilelreturn0;)if([(fp2=fbpen(llfi 匚豆]“==NULL){primff'CannolopenfHe2!\n");return0;}while(!ieo③|))fputc(|?1fpl)；tclose(fpl);fclose(fp2);}?.設(shè)n>0.卜列函數(shù)的功能是。intfun(intn)<intcount=0;while(n){count++;n=n/IO;returncount;9,下列程序的功能是."include<stdio.h>//include<string.h>main(){charstr[81].*ptrl,*ptr2;intn;gcts(str);n=strlen(str);ptrl=str;plr2~slr+n-l:while(ptrl<ptr2){if(*ptrl!=*p(r2)break;else{ptrl++;ptr2一;}}if(ptrl<ptr2)printf("No!\n'');elseprimR"Yes!\rr);}10.5列程序的功能是。(注：他11(*F1LE)返回long類型的文件指針位音)#include<stdio.h>voidmain(){FILE*fp;longposition;ic-Jr：fprintRfp/,data*');position^ftell(fp);printf(,lposition=%ld',n",position);fclosc(fjp);}八、程序設(shè)計題（本題15分）請編寫C語占程序,該程序的功能是確定字符串中首次出現(xiàn)的某字符在符中的位者（即該字符是字符串中的第幾個字符），然后從字符串中刪除該字符.要求：①如果未找到該字符,程序給出相應(yīng)信息，杳則,徜出該字符在字符串中苜次出現(xiàn)的位置，刪除該字符（濘：不考慮非苜次出現(xiàn)的該字符的刪除），并且顯示刪除前后的字符串.②通過鍵盤輸入字符串以及被確定的字符.2011年北京航空航天大學(xué)991數(shù)據(jù)結(jié)構(gòu)與C語言程序設(shè)計考研真題北京航空航天大學(xué)2011年碩士研究生入學(xué)考試試題科目代期991

數(shù)據(jù)結(jié)構(gòu)與C語言程序設(shè)計（共7頁）考生注意：所有答題務(wù)必書寫在考場提供的答題紙上，寫在本試題單上的答題一律無效（本題單不參與閱卷）。一、單項選擇題（本題共20分,每小題各2分）.卜列關(guān)于線性表的存儲結(jié)構(gòu)的敘述中，錯誤的是,A.線性表的順序存儲結(jié)構(gòu)中除式地存儲了數(shù)據(jù)元素之何的邏輯關(guān)系B.線性表的順序存儲結(jié)構(gòu)一定需要占用一片地址連續(xù)的存儲空間C.線性表的鏈式存儲結(jié)構(gòu)通過指針來反映數(shù)據(jù)元素之間的邏輯關(guān)系D.線性表的鏈式存儲結(jié)構(gòu)占用的存儲空間一定不連續(xù) ?.若from和rear分別表示鏈接隊列的隊頭指針與隊尾指針，則向隊列中插入一個由p指的新元素的過程是依次執(zhí)行.A.rear=p;front-p; B.front=p;rear=p;C.rear->link=p;rear-p; D.front->iink=p;rear=p;.F列關(guān)于二叉樹的敘述中，正確的是,A,二叉樹的度可以小于2 B.二叉樹的度等于2C.二叉樹中至少有一個結(jié)點的度為2D.二叉樹中每一個結(jié)點的度都為2.若某二義樹有40個葉結(jié)點,則該二叉樹的結(jié)點總數(shù)最少是?A.78 B.79 C.80 D.81.若采用鄰接矩陣存儲個有向圖，且鄰接矩陣主對角線以下元素均為0,則設(shè)有向圖的拓撲序列.A.存在旦惟一 B.存在但可能不惟一C.不存在 D.無法確定.下而關(guān)于AOE網(wǎng)的敘述中，正確的是AOE網(wǎng)是一個帶權(quán)的連通投AOE網(wǎng)是一個帶權(quán)的強連通圖AOE網(wǎng)是一個帶權(quán)的無回路的連通圖AOE網(wǎng)是個帶權(quán)且無回路的有向圖.下列關(guān)于線性表查找方法的敘述中,錯誤的是.A.順序杳找法適合于采用順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)的線性表的杳找.對于相同元素，順序杳找法定能夠杳找到表中首次出現(xiàn)的元素C.對于相同元素，折半杳找法定能夠杏找到裹中首次出現(xiàn)的元素D.對于相同元素，折半杳找法不一定能夠會找到表中首次出現(xiàn)的兀素

.在二叉擇序樹中進行查找的平均時間效率主要與下列因素之一有關(guān)，該因素是.A.二叉撲序樹的深度 B.二叉排序樹中結(jié)點的個數(shù)的多少C.被杳找結(jié)點的度 D,二叉排序樹的存儲結(jié)構(gòu).下列4種排序方法中，每一趟排序結(jié)束時不一定能鑼確定一個元素排序的最終位置的是.A.插入排序 B.快速排序C.堆積(Heap)排序 D.二路歸并排序.下列4種排序方法中，當(dāng)待排序的序列中元素初始時已經(jīng)按值有序，If序所花費的時間反而有可能最多的是?A.泡推序 B.謝爾(Shell)排序C.快速排序 D.堆積(Heap)排序二、簡答跟(本題共20分，每小題各S分)I.等概率情況下，在長度為n的順序表中插入和刪除一個數(shù)據(jù)幾素分別需要平均移動多少個元素？移動的元素個數(shù)主要取決于哪幾個因素?在采用循環(huán)單鏈表作為某隊列的存儲結(jié)構(gòu)時，可以只設(shè)置一個隊頭指針，也可以只設(shè)置一個隊尾指針.請問：從操作的時間效率考慮，采用哪種方案更合適？為什么？對于具有n個頂點、e條邊的稀疏圖和稠密圖，就空間性能而言，采用鄰接矩陣存儲方法和鄰接表存儲方法哪一種更合適？為什么？4,什么是小頂堆枳(Heap)?在小頂堆積中，值最大的元素可能處在什么位置？(可以借助一株二叉樹描述)三、綜合題(本題共20分，每小題各5分).下列算法的功能是刪除長度為n的順序表A中更發(fā)出現(xiàn)的多余元素.即對于重復(fù)出現(xiàn)的元素，表中只保的個.請在算法的空白處填上必要的內(nèi)容，使算法完整。voidPURGE(ElemTypeA(j,int&n){inti=0ji;whilc(i<n)(j=i+1； /?從第i+l個元素開始逐個與第i個元素比較*/while(j<n)ifiAU]—A[i]){ /?若A[j]與A[i]相同，刪除AUJ*/ford5bA[kl]=A[k];n-; /?修改表的長度?/}else)

題:2圖.請將由題三2圖給定的樹轉(zhuǎn)換為一棵二叉樹.(只須畫出轉(zhuǎn)換題:2圖.已知某3階B樹如題三3圖所示，請畫出在該B樹中插入關(guān)健字20以后得到的B樹。.請分別寫出對數(shù)據(jù)元素序列(49.38,65,97.76,13,27.49，)按從小到大進行謝爾(Shell)排序時每一趟的結(jié)果。設(shè)排序的間隔數(shù)(也稱為增量)依次為4,21.四、算法設(shè)計題(本題15分)已知某哈夫曼樹采用二叉鏈表存儲，結(jié)點構(gòu)造為［Ichild|data|rchild|.其中，葉結(jié)點的data域中已經(jīng)存放了該葉結(jié)點對應(yīng)的權(quán)值.請寫一非遞而京該算法的功能是計算根結(jié)點指針為T的哈夫曼樹的帶權(quán)路徑長度(WPL)。要求：.用文字簡要給出匏法的基本思想；.根據(jù)算法的基本思想寫出相應(yīng)算法。五、程序閱讀題(本題共20分，每小題各2分).下列程序的輸出結(jié)果是.main(){charch-4A';printR“ch(I)=%d,ch(2)=%c\n”,ch,ch,I);).下列程序段的輸出結(jié)果是■k=l;t=3;do{t+=k++;ifO%7g0)continue;else++k;}while(t<15);printfC*%d",k);.下列程序的輸出結(jié)果是.#include<stdio.h>main()( ints[12]={l,2,3,4,4.321,1,123}』葉{0}j；fbr(i=0;i<12;i-H-)a回用h；fbr(i=1;i<5;i++)printfC%T,a[iD；printR"\n");}.下列程序的輸出結(jié)果是?#includc<string.h>main(){charstrlfl5]=ugoodM,str2(10]="morning”；printf(**%d\n*,,strlen(strcat(str1,str2)));}.下列程序的輸出結(jié)果是?main(){inia(5]={l,2,3A5).*p;L；printfC'%d\n,>,*(++p));).下列程序的輸出結(jié)果是.main(){char*s=“】3579”；s++;printfT'%c%c%c'',*s,*(s+1),*s+1);}.下列程序的輸出結(jié)果是.defineMAX(A,B)(A)>(B)?(A):(B)“definePRINT(Y)printf(uY=%d\tM,Y)main(){inta=),b=2,c=3,d=4,temp;temp=MAX(a+b,c+d);PRJNT(temp);}.下列程序的輸出結(jié)果是?intfun(intx,inty){retum(x+y);}main()(inia=2,b=5.c=8;printR'^MjdW'.funCfunCa+c.bJ.ac));.下列程序的輸出結(jié)果是,/include<stdio.h>main()(structdate(intyear.month,day;}today;printff1*%d\n''tsizeofi(structdate));).執(zhí)行下列程序后，文件fik2.txt中的內(nèi)容是.“include<stdio.h>main()(FILE?in,*out;char?strl-uYOUPLANTOFAIL.”；char"str2H“IFYOUFAILTOPLAN”；i?(in-fbpcnC-file1.txtVw,,))!=NULL)whi砥*sirl!='.')fputc(*strl-*-+,in);fclose(in);if(((in=fopen(**fileLtx「,"r"))!=NULL)&&((out=fbpen(,'file2.txt',,ww,,)!=NULL)){while(!eof(in)){^getc(in);tputc(*str2++.out);))fch)se(in);fclose(oul);)六、填空題(本題共20分，每小題各4分).對于下列程序，為了使輸出結(jié)果為t=4,輸入量x和y應(yīng)該滿足的條件是-main(){intx,y,s=l,t=l;scanfi4l%d,%d,,.&x,&y);ifi(x>0)s=s+l;iRx>y)t=s+t;elseiflfx—y)t=5;elsel=2*s;printf(**t=%d,',t);}.若已有下列定義，則友達式p>b/n.a的值是色，表達式p->b/n.a*++p->b的伯是②,表達式(*p).a+p，c的值是3_,structnum{inta;intb;floatc;}n={135.0};structnum*p-&n;.下列程序段的功能是計算1000!的末尾含有多少個零.請在程序段的空白處填上必要的內(nèi)容，使程序段完整。(提示：只要計算出1000!中含有因數(shù)5的個數(shù)即可)fbr(k=0,i=5;i<=1000;i+=5){m=i;whiledb(k++;mam/5;}}.下列程序的功能是通過指針操作，找出并輸出三個整數(shù)中的量小工，請存程序的空白處境上必要的內(nèi)容，使程序完整。#include<stdlib.h>main(){int*a,*b.*c,num,x,y,z;a=&x;b=&y;c=&z;printf(wlnput“b.c:");scanf(4*%d%d%d,\a,b,c);prinlfir%d,%d,%d\n”jajb,*c);num=*a;】R*a>*b)□S3if(num>*c)printR“Theminimun=%d\n".num);}5.下列程序的功能是先由用戶通過鍵盤輸入一個文件名，然后向此文件箱入一串字符(假設(shè)輸入以字符結(jié)束)，最后再將當(dāng)前日期寫到文件的尾部.請在程序的空白處境上必要的內(nèi)容，使程序完整。/include<stdio.h>main()(charch,date[2O],fname[3O];FILE*lp；printff'Inputthefilename:");scanfl(,t%s,,,fharne^iR(fp=fbpen(l—U)]))==NULL)(prinlR"Cannotopenfile%s!\n",fname);exit(O);}printfC'Inputastring:\nM);while((ch=getchar())!=*#")fputc廣②一b；print鏟Enterdate:\nM);scanf(學(xué)s,dale),fprintfd遨b；fcloseffp);七、程序設(shè)計題（本題15分）請^寫一C語言程序，該程序的功能是先通過鍵盤輸入個整數(shù)n.然后調(diào)用一個遞歸函數(shù)Nn（intn）計算1+2+3+…+n,最后輸出計算結(jié)果。八、程序設(shè)計題（本題20分）請設(shè)計一C語言函數(shù)C主：只須寫出函數(shù).不必寫出完整程序）.該函數(shù)的功能是用盡可能高的時間效率與空間效率將一個int類型的數(shù)組A[0..n7）的所有元素依次循環(huán)右移k個位置。例如，對于某數(shù)組，當(dāng)k=3時（即把數(shù)組所有元素循環(huán)右移3個位置）.是將10|20j30I40]50 |701轉(zhuǎn)換為|50|60|70|10|20|30|402.中國傳媒大學(xué)數(shù)據(jù)結(jié)構(gòu)與計算機網(wǎng)絡(luò)歷年考研真題

2014年中國傳媒大學(xué)?21數(shù)據(jù)結(jié)構(gòu)與計算機網(wǎng)絡(luò)考研?題中國傳媒大學(xué)2014年全國碩士研究生入學(xué)統(tǒng)一考試

數(shù)據(jù)結(jié)構(gòu)與計算機網(wǎng)絡(luò)試題答題說明：答案--律寫在答題紙上,不需抄題,標明題號即可，答在試題上無效.一、觸項選擇題：(每小題2分，共50分).下列關(guān)于棧和隊列說法中.正確的是().A.消除遞歸不一定需要使用棧B.對同一輸入序列進行兩組不同的合法入棧和出棧組合操作，所得的輸出序列也一定相同C.通常使用隊列來處理函數(shù)或過程處理D.隊列和棧是運尊受限的線性表，只允許在表的兩端進行運算.一個棧的入棧序列是1,23,4,5,則棧的不可能的輸出序列是().A.5,4,3,2,1.B.4,532,1C.43,5,1,2,D.123,4,5.己知棧的輸入序列為1,2.3,…，n,輸出序列為pi，pj.pj.p?.若出=3.則6的值為().A.一定是2B.一定是1 C.可能是1D.可能是2.循環(huán)隊列用數(shù)組存放其元素值，已知其頭尾指針分別為fiont和rear,則當(dāng)前元素個數(shù)為().A.(rear-front*m)MODm B.rear-front+1C.rear-front-1 D.rear-front5.已知有一維數(shù)組若要對應(yīng)為m行、n列的矩陣，將元素A[k](此kVm?n)我示成矩陣的第i行、第j列的元素(OSiVm,與Vn),則下面的對應(yīng)關(guān)系是().A.i=k/n,j=k%m B.i~k/m,j-k%mC.i=k/n,j=k%n D.i=k/m,j=k%n.設(shè)有一個10階的對稱矩陣A,采用壓縮存儲方式，以行序為主存儲，air為第-元素，其存儲地址為1,每個元素占一個地址空間，則ag.s的地址是().A.13 B.33C.18 D.40.含有n個結(jié)點的三叉樹的最小高度是().A.nB.|_〃/3」C.[log3nj+lD.「Iogj(2〃+1)]

.在棵具有n個結(jié)點的二丈樹中,所有站點的空/樹個數(shù)等J().A.n B.n-l C.n+l D.2*n.在常用的描述二叉排序樹的存儲結(jié)構(gòu)中，關(guān)犍字值最大的結(jié)點是().A.左指針一定為空 B.右指針一定為空C.左右指針均為空 D.左右指針均不為空.由權(quán)值為9、2.5、7的四個葉子構(gòu)造一棵哈夫亞樹，該樹的帶權(quán)路徑長度為().A.23 B.37 C44 D.46.若一個具有n個結(jié)點、k條邊的非連通無向圖是一個森林(n>k).則該森林中必有樹的數(shù)目是().A.k B.n C.n-k D.n+k.采用鄰接表存儲的圖的廣度優(yōu)先遍歷眸法類似「樹的()?A.中根遍歷B.先根遍歷 C.后根遍歷D.按層次遍歷.住有向圖G的拓撲序列中,若頂點V,在頂點V,之前,則下列情形不可能出現(xiàn)的是().A.G中有弧<V,,Vj> B.G中有一條從V1到』的路在C.G中沒有瓠〈MN戶 D.G中有一條從V,到V,的路徑.有一個長度為12的有序表，按折華杏找法對該次進行杳找，在表內(nèi)各元素等慨率情況下,許找成功所需的平均比較次數(shù)是().A.37/12B.35/12C.39/12 D.43/12.假設(shè)有k個關(guān)鍵字互為同義詞,若用線性探唐法把這k個關(guān)鍵字存入，至少要進行的探告次數(shù)是().A.k-1 B.k C.k+1 D.k(k+iy2.下列序列中,滿足堆定義的是().(100.86,9,1)(5,24,6.33)(103,97,56,2,.26)(3,1.36,76,28.100).對于一個長度為n的任意表進行排序，至少需要進行的比較次數(shù)是().A.O(n) B.O(n2) C.O(logn)D.Ofnlogn)!8.關(guān)于網(wǎng)絡(luò)分層結(jié)構(gòu),下列說法正確的是().A.某一層可以使用其上一層提供的服務(wù)而不需知道服務(wù)是如何實現(xiàn)的B.層次劃分越多,靈活性越好，協(xié)議效率也越高C.由于結(jié)構(gòu)彼此分寓，實現(xiàn)和維護更加困難D.當(dāng)某?層發(fā)生變化時，只要接口關(guān)系不變，以上或以下的各層均不受影響.不受電磁干擾或噪聲影響的介質(zhì)是().A.雙線線 B.光纖 C.同軸電纜 D.微波.要在帶寬為4kHz的信道上用2秒鐘發(fā)送80kb的數(shù)據(jù)塊,按照杏農(nóng)定理，信道的信噪比最小應(yīng)為多少？（）A.1023 B.200 C.1005 D.600.若數(shù)據(jù)鏈路層采用選擇電傳協(xié)議，發(fā)送方已經(jīng)發(fā)送「編號為。?6的幀.當(dāng)計時器超時時，只有5號幀的確認還沒有返回，則發(fā)送方需要重發(fā)的幀數(shù)為（）.A.I B.2 C.3 D.7.卜面技術(shù)無法使10Mbps以太網(wǎng)升級到100Mbps和IGbps的是（）.A.采用幀擴展和幀突發(fā)技術(shù)B.傳輸介質(zhì)使用高速光纖C.幀長保持不變，網(wǎng)絡(luò)跨距增加D.使用以太網(wǎng)交換機，引入全雙工流量控制協(xié)議.位于不同于?網(wǎng)中的主機之間進行相互通信,下面說法中正確的是（）.A.源站點可以直接進行ARP廣播得到目的站的硬件地址B.路由器在轉(zhuǎn)發(fā)1P數(shù)據(jù)報時，重新封裝源硬件地址和目的硬件地址C.路由器在轉(zhuǎn)發(fā)IP數(shù)據(jù)報時，重新封裝H的IP地址和目的IP硬件地址D.路由器在轉(zhuǎn)發(fā)IP數(shù)據(jù)報時，加新封裝源IP地址和目的IP地址24.在TCP/IP網(wǎng)絡(luò)上，主機及主機上運行的程序可以用（）來標識.A. IP地址，MAC地址 B.端口號，IP地址C. 1P地址，主機地址 D. IP地址，端口號標準的URL組成：服務(wù)器類型、主機名和路徑及（）.A.文件名 B.瀏覽器C.客戶名 D.進程名二、綜合應(yīng)用題：26?34小題,共100分。（10分）現(xiàn)有一個解決無向連通圖的最小生成樹的一種方法如下：將圖中所有邊按權(quán)用從大到小排序為（el,e2，…,em）;i=I；while（所剩邊數(shù)>=頂點數(shù)）（從圖中刪去ci;若圖不再連通，則恢復(fù)ei;i=i+l;}請問上述方法能否求得原圖的最小生成樹?若該方法可行，請證明之：否則請舉例說明.（10分）采用散列函數(shù)H（k）=3xkMOD13并用線性探泅開放地址法處理沖突，在散列地址空間［0..12］中對關(guān)健字序列22,41,53,46,30.13.1,67,51：（1）構(gòu)造散列表（畫示意圖）：（2）裝填因子：（3）等概率情況下杳找成功的平均查找長度：（4）等概率情況卜盒找失敗的平均直找長度.（12分）己知數(shù)組的元素類型為整型int,設(shè)計一個時間和空間上盡可能高效的算法，將其調(diào)整為左右兩部分，左邊所有元素為負整數(shù)，右邊所有元素為正整數(shù)。不要求對這些元素排序.（!）給出算法的基本設(shè)計思想：（2）根據(jù)設(shè)計思想，采用C或C++語言表述算法，關(guān)鍵之處給出注和：（3）說明你所設(shè)計算法的時間復(fù)雜度和空間復(fù)雜度。（12分）己知帶頭結(jié)點的單鏈表H,寫?算法將其數(shù)據(jù)結(jié)點逆序鏈接.即線性表＜a|...an）逆置為（4..向）?（I）給出算法的其本設(shè)計思想。（2）根據(jù)設(shè)計思想，采用C或C++語言描述史.法，關(guān)鍵之處給出注擇。（12分）假設(shè)：叉樹采用二叉鏈表存儲結(jié)構(gòu)存儲.設(shè)計個尊法，利用緒點的右孩子指針rchild將一棵二叉樹的葉子結(jié)點按從左往右的順序串成一個單鏈表。（1）給出算法的基本設(shè)計思想.（2）根據(jù)設(shè)計思想，采用C或C++語自描述算法，關(guān)鍵之處給出注料.（8分）若構(gòu)造■?個CSMA/CD總線網(wǎng).速率為100Mbps,電纜總長度1km,中間用一個中繼器連接，電纜中的信號傳播速度是200000km/s.信號經(jīng)過中繼器產(chǎn)生2Ms時延。試求出數(shù)據(jù)幀的最小長度。（14分）?個公司有兩個部門，銷14部和財務(wù)部，銷傳部有28臺PC.財務(wù)部有15臺PC。現(xiàn)在，公司申請了一個C類地址,規(guī)劃的網(wǎng)絡(luò)拓撲如下圖所示，試解答如下問題。（I）給出合理的子網(wǎng)規(guī)劃,并說明理由.（2）為兩個部門各分配一個f網(wǎng)地址，并為兩個路由器的接口和各臺PC分配IP地址.（3）如果路由器RI和R2都采用了R1P作為路由選擇協(xié)議，請給出當(dāng)穩(wěn)定運行之后，RI和R2的路由表。（12分）假設(shè)主機A己向七機B發(fā)送了個序號為70的報文段,并已在超時計數(shù)器超時之前收到「主機B的確認.現(xiàn)主機A向主機B乂連續(xù)發(fā)送了兩個TCP報文段p、q,其序號分別為90、130.請回答以下問題，并寫出解答過程.（I）p報文段攜帶/多少字節(jié)的數(shù)據(jù)？（2）主機B收到p報文段后發(fā)回的確認中的確認號應(yīng)當(dāng)是多少？（3）如果主機B收到q報文段后發(fā)回的確認中的確認號是180,試問A發(fā)送的q報文段中的數(shù)據(jù)有多少字節(jié)？（4）如果A發(fā)送的p報文段丟失但q報文段到達B在q報文段到達后向A發(fā)送確認.試問這個確認號應(yīng)為多少？34.（10分）基千萬維網(wǎng)的電f郵件系統(tǒng)有什么特點？在傳送郵件時使用什么協(xié)議？2013年中國傳媒大學(xué)821數(shù)據(jù)結(jié)構(gòu)與計舞機網(wǎng)絡(luò)考研直跑中國傳媒大學(xué)2013年全國碩士研究生入學(xué)統(tǒng)一考試數(shù)據(jù)結(jié)構(gòu)與計算機網(wǎng)絡(luò)試題答題說明：答案律寫在答題紙上，不需抄題，標明題號即可,答在試題上無效.一、單項選擇題：1?25小題，每小題2分，共50分..一長為n的順序療的的線性衣,當(dāng)在任何位置上刷除?個元素的概率相券時，刪除個無索所需移動無索的平均個數(shù)為( ).A.n B.n!2 C.(n-l)/2 D.(n+l)/2.設(shè)n是描述時理現(xiàn)模的II負整數(shù).卜面程序片段的時間乂雜度足( ).inii=1;while(i<n)i=i,2:A.Oflog:nlB.O(n) C.O(nlog;n)D.O(n?)TOC\o"1-5"\h\z解決計切機L機。打印機之間速度不幾和何也時通常設(shè)置個打卬數(shù)據(jù)緩沖M.1：機將要輸出的數(shù)據(jù)依次。入該緩沖區(qū),而打印機則從該線沖區(qū)中收出數(shù)據(jù)打印.該級沖區(qū)的結(jié)構(gòu)是( ).A.楨 B.隊列 C.數(shù)組 D.線性&.在卜.面的應(yīng)用中，通常使用權(quán)的足( ).I遞打調(diào)用II括凡配III友達式求侑A.I.II B.II.IllC.L111D.1.ILIII.用燧接力式存儲的隊列.在進行刪除運燈時.F面正確的是( ).A.儀修改頭指針 B.僅修改尾指針C.頭.他指針都要修改 D.頭、尾指針燈能都要修改.設(shè)樹T的度為4.其中度為I.2.3和4的結(jié)點個數(shù)分別為4.2.I.I則T中的葉廣數(shù)是《 ).A.B.6C.7A.B.6C.7D.8.卜列夫「?二義樹的說法中,正峋的是( ).A.度為2的有序樹就是二叉樹.含仃n個結(jié)點的.義樹，其高度為[log?“+1C.完全.叉樹中.一?個結(jié)點沒行左孩f，則它必是葉f結(jié)點D.在任意棵II空.義指序樹中,刪除某結(jié)點后乂將其插入,則所行的義揖序樹與扁除前原?義排摩樹相同TOC\o"1-5"\h\z.某：義樹的先序遍方序列為IJKLMNO,中序遍歷存列為JLKINMO,則下序遍歷序列是( ).A.JLKMNOIB.LKNJOMIC.LKJNOMID.LKNOJM1.設(shè)森林卜中仃三棵樹.第?.第：,第棵樹的結(jié)業(yè)個數(shù)分別為N1,N2和N3.9公林F對應(yīng)的.義樹根結(jié)點的。廣樹上的結(jié)點：個數(shù)是( ).A.Nl B.NI+N2C.N3 D.N2+N3.筒單元向圖的鄰接也陣是對稱的,可以對其進行拒縮療儲.若無向圖Gtn個結(jié)點,其鄰接卻附為八、]〃儲在BUHn-iyZ].外拉行壓縮4儲對稱如用的I：:?加幾索.則巧n等J10時，邊(v6,v3)的信息存儲〃( )?A.B[I8] B.B(I9] C.B|20] D.B|2l]IL以卜次「圖的說法正確的是( ).I/I個仃向圖的柘撲序列中,若頂點a在頂點b之前,則圖中必仃條弧＜a.b＞11r.個仃向圖的鄰接沿陣中對角線卜兀索均為o,則該圖的拓撲環(huán)列必定〃aHI/1AOE網(wǎng)中定只r條關(guān)鍵路憐A.LII B.II.Ill C.kIII D.僅有1112.設(shè)無向圖G=(V.E)和G'=(V'E').如果G'是G的牛.成樹.則卜血說法中慘誤的是( ).A.G，足G的/圖 B.G?足G的連通分研C.G，是G的極小連通f圖11V=V' D.G'是G的個無環(huán)f?圖.以卜夫卜圖的說法正確的是＜ ).I圖G的生成樹是該圖的?個極小11通/圖II'上成樹中業(yè)K路役的起立和終點的位均為Iinxj(r.s個圖,從我個頂點出發(fā)進行一次深度優(yōu)先或廣度優(yōu)先遍歷,可訪同圖的所仃頂點B.II.IllC.I,IIID.B.II.IllC.I,IIID.僅仃II.|2-仃向圖G=(V,A)?K'I'V-；a.bx.d.c|.A|<a,b>.<a.c>.<d.c>.<d.e>.對4圖進行拓撲打，?卜面序列中不是拓撲國序的是( ).A.a.d.c.b.cB.d.a.b,c,c C.a.b.d.c.eD.a,b.c.d.c.，列(8.9.10,4.5.620.1,2).只能是以卜哪種掃序方法兩趟排序后的結(jié)果().A.選抨找序B.”泡作序 C.插入排序 D.堆指序.卜列揖序律法中，時間攵雜度為O(nlogn)ll.占川額外空間加少的足( ).A.WHI序B.起泡指序C.快速排序 D.布爾“序.財大鍵時序列(23,17,72.60.25,8,68,71,52)進行堆排序,輸出兩個小小關(guān)ft!碼不的軻氽用足().A.(23.72.602) B,(23.25.52,60,71,72.68)C(2.60,72.68) D.(2.6O,72.7I)TOC\o"1-5"\h\zIX.與數(shù)據(jù)由源網(wǎng)A怯送個II的端B時,不參1j數(shù)據(jù)封裝I：件的止( )A.傳輸江B.網(wǎng)路公C.數(shù)據(jù)鏈路房D.物理以.莊常用的傳輸介質(zhì)中,希寬最寬,此號內(nèi)輸或減最小，抗卜擾能力最強的是( ).A.雙紋紋 B.同軸電纜C.光纖 D.俄波.作無啜小情況卜.井某通俗鏈路的帶寬為3kHz.栗川16種不同的物理狀態(tài)來點示數(shù)據(jù).則該通信璉路的公人數(shù)據(jù)化輸速率是多少？( )A.24 B.18 C.12 D.3.?；數(shù)據(jù)埴路工采用斤退N幀協(xié)議.發(fā)送方L1經(jīng)發(fā)送廣編號0■心的幀.當(dāng)計時器的時時，乂收到r13和51；幀的確認,發(fā)送方需鬟很傳的幀的數(shù)二是( ).A.I B.2 C.5 D.6.在RO2.3MAC觸中.H的地地DA字段個為“I”,則女東( ).A.無效地用 B.廣播地址C.組地址 D.木服務(wù)器地址.某路由器收到r個ip分組,在對其頭部進行檢驗和后發(fā)現(xiàn)仃差鉗,該路由器采取的動作是< ).A.把該IP分組返網(wǎng)給源計〃機B.史新il。分組頭冷依和歸維續(xù)轉(zhuǎn)發(fā)該IP分組C.丟棄該IP分組D.給目的地計算機發(fā)送一個ICMP報文TOC\o"1-5"\h\z.設(shè)TCP的擁塞窗口的慢開始門限值為16（單位為報文段），與擁寒窗I」I-升到20時,網(wǎng)絡(luò)發(fā)生超時，TCP開始慢啟動和擁塞髭免,那么第13次傳輸時擁超窗口大小為（ ）.A.I B.17 C.8 D.1625.如果本地域名服務(wù)無名存,當(dāng)采用速與方法解析另個網(wǎng)絡(luò)的如上機域名時,用戶主機，本地域名服務(wù)器發(fā)送的域名請求條數(shù)分別為（ ）.A.I條，多條 B.I條,I條C.多條.I條 D.多條，多條二、綜合應(yīng)用題：26?34小題,共100分.（10分）已知加權(quán)行向圖G如F,網(wǎng)答系列問題：（I）制出該仃向圖G的鄰接矩陽：（2）試利用Dijkstra算法求G中從頂點a到其他各頂點間的最短路徑.并給出求解過程.（10分）對卜面的關(guān)鍵字集｛30.15,21.40,25,26,3637｝心作找表的裝填因廣為0.8,栗川線件探測杵散列方法解決沖突：（I）設(shè)計散列函數(shù)：（2）腳出散列入：<3>計算作找成功和查找失敗的平均能找長度.（12分）請，一個立法將順序存儲結(jié)構(gòu)的線性衣（御..2）逆置為g".向）.（12分）分行個帶頭結(jié)點的箭環(huán)單鏈我.其結(jié)點值均為正整數(shù).試設(shè)計個。法,反女找出單域&中結(jié)點值去小的點點,Ji輸出之,然不將該結(jié)業(yè)從中刪除,H到單鏈&空為止.最后在刪除衣頭結(jié)點.（12分）假設(shè)『空.義樹bt采川義鏈衣”儲.K中所仃結(jié)點數(shù)據(jù)域為lE械數(shù),他計個3⑶法求其中的被大ff!（X分）A、B兩站相距l(xiāng)km,使用CSMA/CD協(xié)議,信號在網(wǎng)絡(luò)上的W播速收為200OOOkms.兩站的發(fā)送速中為10Mbps,A光發(fā)送數(shù)據(jù)，如果發(fā)送用抻.求：（I）最先發(fā)送數(shù)據(jù)的A站一晚經(jīng)過Z氏時間d能檢測到發(fā)上門而撞（2）自測到碎押Ki,A己外發(fā)送r.少位？（假設(shè)A要發(fā)送的頓足夠K）（II分）設(shè)仃A、B,C.DJH14公】機都處〃同?個物理網(wǎng)絡(luò)中,AI機的IP地址為192,175.12.112.BI；機的IP地址是192,175.12.120,C1.機的IP地hl是76,DI機的1P地址是22.其同的門編掩碼是24謫問答以卜問邀.并日出解梓過程.⑴A、B、C、D-4介I：機之間哪些可以I'［接通信?哪叫需嚶通過設(shè)置網(wǎng)大（或路由器）才能通優(yōu)?詁倆出網(wǎng)絡(luò)連接術(shù)意圖.并標注各個r網(wǎng)地址利l機地址.（2）試描述I機A發(fā)送個IP數(shù)據(jù)報到上機D的過程（包括物珅地川帆析過程）.（3）:加入第5臺七機E.使它能9CL機H接通億JUP地址的設(shè)定的用應(yīng)是多少？（12分）川TCP傳送5124W的數(shù)據(jù).設(shè)窗II為100字忙向TCP報文段每次也足W送100字行的數(shù)據(jù)出設(shè)發(fā)送力和接收力的起始序”分別為100和200?妣出發(fā)送方和接收方建立連接、傳輸數(shù)據(jù)、大⑷連接的示意圖。（10分）假設(shè)4Internet上臺FTP服務(wù)器.支名稱為.IP地址為5.FTP服務(wù)器進拜住默認端”守候并史持匿名訪問（用戶名:anonymous.II令：guest）.如果用戶AH接川服務(wù)器名稱訪問該FTP服務(wù)器.JI從該服務(wù)器卜伐四個文件p和q.試敘述FTP客戶進程。FTP服務(wù)器邊程之間的交換過程（汴：文f'lp和q允許WZ賬戶訪問）.

3.上海海事大學(xué)數(shù)據(jù)結(jié)構(gòu)歷年考研直題2014年上海海事大學(xué)K21數(shù)據(jù)結(jié)構(gòu)考研真期2014年上海海事大學(xué)攻讀碩士學(xué)位研究生入學(xué)考試試題重要提示：杵案必須做在答題紙匕做花試8S上不給分）考試科目代碼821 考試科目名稱數(shù)據(jù)結(jié)構(gòu)一.判斷題（本題io分.每小題I分）.若某峨序表采用順序存儲結(jié)構(gòu).每個元素占10個存籍單元.1T地址為200.則下標為“（第12的元素的存儲起始地址為320..若對線性表進行的主要操作不是插入和副除，則該線性表宜采用順序存?zhèn)鹘Y(jié)構(gòu)..對一個空桎按a.b.c,d,e,f.g?序依次讀入.經(jīng)過多次入校和出校的操作后.能再到按￡e.g.d,a,c.b畸序的出棱序列.4,假定在行序表中每個位置插入的口率相同.向一個有644元素的順序表中插入一個新元索并?？嬖珥樞虿蛔?平均要棒動33個元素.5,含有3個結(jié)點（元素值均不相同）的二乂推序樹共有30種..n個頂點的連通圖至少有n-1條邊..在無向圖G的瓠接矩陣A中.若等于1,則A（jKi]等于0?8,未用*序檢索法在一個有123個元素的有序■序表中查找.若務(wù)個元素的杳擾就卑相等.則成功除案的平均查找長度ASL為61..在散列存儲中.裝我因子a的值植大.發(fā)生沖突的可能性就越大..快速抨序是一種檢定的撐序方法.二.填空唐（本題30分，每空2分）.分析下列程序段.其時間復(fù)雜電分別為：(1) . (2).i=b=0; a-0;whileGt<n){ for(i=l;i<=n;i*+)for(j=2*i;j<=n;j++)0++；.廣義表A=（a.（a.b）J（i.j）.k）.（lc）的長度是二深度是（。.取表頭和表電函數(shù)分■別為head()和tail().i!lhead(tail(head(tail(A)))))~ (5),而從表中取出原子項i的運算為⑹ ?.有一個二維數(shù)組A[0..6][2..9],每個數(shù)組元素占用8個存儲單元.并且A[2][5]的存儲地址為2080,若枝行序為主序方式存儲,敷煙元崇Al41r61的存伸地址是 ⑺ .

TOC\o"1-5"\h\z.一裸企全二叉樹育600個結(jié)點.則它的，?是 （8）?.巳如一個圖采用鄰接矩陣/示.計*第i個結(jié)點的人質(zhì)的方法是⑼ ?.一個圖的邊諼為｛<A,B>.<A.C>.<A.E>,<B.C>.<B.D>.<C,I）>,<E.B>.<E.D>）.從頂點A出發(fā)進行深度優(yōu)先搜索弟歷訪問了點職序為⑩.從頂點A出3進行廣度優(yōu)先搜索遢歷訪問頂點順序為（1D .對該國進行拓撲彈序博到的頂點序列為。2> ..對12個元京的序列進行直接插入排序時,一少的比較次敝為? .. 0。排序方法采用的是二分法思想.在?情況下最不利于發(fā)揮其長處.=.選擇題（本屆20分，誨空2分）.在敷據(jù)結(jié)構(gòu)中.從巫輯上可以把數(shù)據(jù)結(jié)構(gòu)分成（ ）.A.動態(tài)結(jié)構(gòu)和舲杰結(jié)構(gòu) B.緊湊結(jié)構(gòu)和非緊展結(jié)構(gòu)C.找性結(jié)構(gòu)和#線性結(jié)構(gòu) D.內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu).線性表若采用值式存儲結(jié)構(gòu)時.內(nèi)存中可用存儲單元的地址（ ）.A.必秉是連續(xù)的 B.部分地址必疑是建債的C. 一定是不連犢的 D.連堆不連篌都可以.線性表的順序存儲結(jié)構(gòu)是一種（ ）的存儲結(jié)構(gòu).而線性表的鏈式存儲結(jié)構(gòu)是一種隨機存取的存儲結(jié)構(gòu).A.候機存取B.順序存取C.索引存取D,做列存取.在一個單自表中,已知q所指結(jié)點是p所指結(jié)點的前驅(qū)結(jié)點.若在q和p之間插入s結(jié)點，則執(zhí)行（）.A.s->ncxt=p->ncxt;p->ncxt=s;B.p->ncxt=s->ncx?;s->ncxt=p;C.q->ncxt=s;s->ncxt=p; D.p->ncxt=s;s->ncxt=q;.在雙旗表中的p所指結(jié)點之后插入§所指結(jié)點的操作是（ ）.p->nexi-s;aprior二p:p->ncxt->prioris;§?>ncx〔二jv'ncxt：p->ncxt=s;p->ncxt->prior=s;s->prior=p;s->ncxt=p->ncxl;s->prior=p;s->ncxt=p->ncxt;p->ncxt=s;p->ncxt->priorrs;s->prior-p;s->ncxt^p->next;p->ncxt->prior^s;p->nexr=s;.串是一種轉(zhuǎn)咻的線性表.其轉(zhuǎn)殊性體現(xiàn)在（ ）.A.可以順序存?zhèn)?B.數(shù)據(jù)元索是一個字符C.可以61接存儲 D.數(shù)據(jù)元素可以是多個字符.以下（ ）是稀疏矩陣一般的壓縮存儲方法.A.二維數(shù)組和三維數(shù)組 B.三元招和做列C.三元組和十字銃表 D.散列和十字修表?20M試

TOC\o"1-5"\h\z.采用鄰接表存儲的圖的深度優(yōu)先遍歷第法類似于二叉樹的（ ）.A.先序遍歷 B.中序遍歷C.后序遺房D.按層遍歷.以下不需進行關(guān)鍵字的比較的排序方法是（ ）.A.快速排序 B.歸并排序C.冬數(shù)排庫D.起泡排序.有一個長度為12的有序表.按二分查找法對該表迸行查找.在表內(nèi)各元素等假率情況下查找成功所需的平均比較次數(shù)為（ ）.A.35/12 B.37/12C.39/12D.43/12.應(yīng)用題（本題60分，每小題10分）.已知一愣二叉樹的先序序列和中序序列分別為.先序序列：ABDEGHCFK中序序列：DBGEHAFKC請畫出該樹的結(jié)構(gòu)并寫出其后序序列.TOC\o"1-5"\h\z.右圖是一個無向圖.試分別用下列兩種方法求它的最小 一?生成樹,并給出依次產(chǎn)生的邊.連接頂點i和j邊用vi.9的形 6/\式表示.口用普里姆算法從頂點a開始； X%XX2）用克魯斯卡爾算法. ?-5 ?.某通