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

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

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

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

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

第99卜4頁(yè)值元素放在A[n]中：第2趟排序?qū)⒋涡≈翟胤旁贏[2J中，次大值元素放在A[n-1]中；……，依此下去，直至排序結(jié)束。五、填空題(本題共20分，每小題各2分).已知某等比數(shù)列的第一項(xiàng)即為I,公比為3,F列程序的功能是諭出該數(shù)列中小于1000的最大項(xiàng)an及其對(duì)應(yīng)的n.請(qǐng)?jiā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ù)組的元素是否按值從小到大排列.若是一個(gè)遞增數(shù)組，則函數(shù)返回true,否則，函數(shù)返回false.請(qǐng)?jiān)诤瘮?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中兩條對(duì)角線(xiàn)上元素之和.請(qǐng)?jiān)诔绦虻目瞻滋?方框內(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中分別存放主對(duì)角線(xiàn)與副對(duì)角線(xiàn)上的元素之和?/printfT*%d,%d\n'\x,y);}4.下列程序的功能是先通過(guò)鍵盤(pán)輸入一正整數(shù),然后調(diào)用一遞歸函數(shù)FUNC4.該函數(shù)將正整數(shù)轉(zhuǎn)換為對(duì)應(yīng)的數(shù)字字符組成的字符串顯示在屏幕上.例如：若輸入的正整數(shù)為583,則屏幕上顯示的是字符串583?請(qǐng)?jiān)诔绦虻目瞻滋?方框內(nèi))填入合適內(nèi)容，使程序完整。#include<std沁.h>voidFUNC4(intn){inti;i=n/10;-bFUNC4(i);putchardb；)main(){intn;printR”請(qǐng)輸入一正整數(shù)n：”)；scanff%1”,&n);prinlR”轉(zhuǎn)換后的字符串是：'*)；FUNC4(n);)5.下列程序的功能是將小寫(xiě)字母轉(zhuǎn)換成對(duì)應(yīng)的大寫(xiě)字母后的第2個(gè)字母，例如：將a轉(zhuǎn)換成C,將b轉(zhuǎn)換成D.其中,y轉(zhuǎn)換成A,z轉(zhuǎn)換成B?請(qǐng)?jiān)诔绦虻目瞻滋?方框內(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字符、回車(chē)符以及換行符.請(qǐng)?jiān)诤瘮?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);.下列程序的功能是判斷輸入的字符串是否是“回文二(注：按順序讀與按逆序讀都一樣的字符串被稱(chēng)為“回文'例如：abcdcba).請(qǐng)?jiān)诔绦虻目瞻滋?方框內(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);).下列程序的功能是：對(duì)于字符類(lèi)型變量ch=108,保留中間兩位，而將高、低3位清零.請(qǐng)?jiān)诔绦虻目瞻滋?方框內(nèi))填入合適內(nèi)容，使程序完整.main(){charch;ch=108;chdkprintfl[1*%d,\ch);}.設(shè)file為存放了整型數(shù)據(jù)的二進(jìn)制文件.下列程序的功能是從該文件中讀入第3個(gè)數(shù)據(jù)輸出到屏幕上.請(qǐng)?jiān)诔绦虻目瞻滋?方框內(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.下列程序的功能是將一個(gè)磁盤(pán)中的二進(jìn)制文件復(fù)制到另一個(gè)磁盤(pán)中.兩個(gè)文件的文件名隨命令行一起輸入，輸入時(shí)原有文件的文件名在前，新復(fù)制文件的文件名在后.請(qǐng)?jiān)诔绦虻目瞻滋?方框內(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);)六、簡(jiǎn)答題(本題共20分，每小題各5分).在C語(yǔ)言中，函數(shù)調(diào)用時(shí)數(shù)據(jù)的傳遞通常有哪幾種方式？.在C語(yǔ)言中，指針可以做哪些運(yùn)算？.共用體(union)具有哪些基本特征？.使用文件的基本操作步驟是怎樣的？七、程序設(shè)計(jì)題(本題15分)請(qǐng)編寫(xiě)一程序，該程序的功能是找出并且刪除一維整型數(shù)組a[lOOJ中的最小值兀素.要求：①數(shù)組各元素通過(guò)鍵盤(pán)輸入獲得初值；②所有對(duì)數(shù)組元素的引用必須通過(guò)指針完成.八、程序設(shè)計(jì)題(本題20分)請(qǐng)僅編寫(xiě)出一C語(yǔ)言函數(shù)char*maxword(char*s,char*t).該函數(shù)的功能是求出字符串s與字符串t的最長(zhǎng)公共單詞(這里，假設(shè)兩個(gè)字符串均由英文字母和空格字符組成):若找到這樣的公共單詞，函數(shù)返回該單詞，否則，函數(shù)返回NULL.例如：若s="ThisisCprogrammingtext",X'ThisisatextforCprogramming”.則函數(shù)返回“programming".要求：①函數(shù)中不得設(shè)胃保存單詞的存儲(chǔ)空間：②給出函數(shù)之前請(qǐng)用文字簡(jiǎn)要敘述函數(shù)的基本思想.2012年北京慶大學(xué)W12012年北京北京航空航天大學(xué)2012年

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

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

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

題:2圖.請(qǐng)將由題三2圖給定的樹(shù)轉(zhuǎn)換為一棵二叉樹(shù).(只須畫(huà)出轉(zhuǎn)換題:2圖.已知某3階B樹(shù)如題三3圖所示，請(qǐng)畫(huà)出在該B樹(shù)中插入關(guān)健字20以后得到的B樹(shù)。.請(qǐng)分別寫(xiě)出對(duì)數(shù)據(jù)元素序列(49.38,65,97.76,13,27.49，)按從小到大進(jìn)行謝爾(Shell)排序時(shí)每一趟的結(jié)果。設(shè)排序的間隔數(shù)(也稱(chēng)為增量)依次為4,21.四、算法設(shè)計(jì)題(本題15分)已知某哈夫曼樹(shù)采用二叉鏈表存儲(chǔ)，結(jié)點(diǎn)構(gòu)造為［Ichild|data|rchild|.其中，葉結(jié)點(diǎn)的data域中已經(jīng)存放了該葉結(jié)點(diǎn)對(duì)應(yīng)的權(quán)值.請(qǐng)寫(xiě)一非遞而京該算法的功能是計(jì)算根結(jié)點(diǎn)指針為T(mén)的哈夫曼樹(shù)的帶權(quán)路徑長(zhǎng)度(WPL)。要求：.用文字簡(jiǎn)要給出匏法的基本思想；.根據(jù)算法的基本思想寫(xiě)出相應(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分).對(duì)于下列程序，為了使輸出結(jié)果為t=4,輸入量x和y應(yīng)該滿(mǎn)足的條件是-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);}.若已有下列定義，則友達(dá)式p>b/n.a的值是色，表達(dá)式p->b/n.a*++p->b的伯是②,表達(dá)式(*p).a+p，c的值是3_,structnum{inta;intb;floatc;}n={135.0};structnum*p-&n;.下列程序段的功能是計(jì)算1000!的末尾含有多少個(gè)零.請(qǐng)?jiān)诔绦蚨蔚目瞻滋幪钌媳匾膬?nèi)容，使程序段完整。(提示：只要計(jì)算出1000!中含有因數(shù)5的個(gè)數(shù)即可)fbr(k=0,i=5;i<=1000;i+=5){m=i;whiledb(k++;mam/5;}}.下列程序的功能是通過(guò)指針操作，找出并輸出三個(gè)整數(shù)中的量小工，請(qǐng)存程序的空白處境上必要的內(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.下列程序的功能是先由用戶(hù)通過(guò)鍵盤(pán)輸入一個(gè)文件名，然后向此文件箱入一串字符(假設(shè)輸入以字符結(jié)束)，最后再將當(dāng)前日期寫(xiě)到文件的尾部.請(qǐng)?jiān)诔绦虻目瞻滋幘成媳匾膬?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è)計(jì)題（本題15分）請(qǐng)^寫(xiě)一C語(yǔ)言程序，該程序的功能是先通過(guò)鍵盤(pán)輸入個(gè)整數(shù)n.然后調(diào)用一個(gè)遞歸函數(shù)Nn（intn）計(jì)算1+2+3+…+n,最后輸出計(jì)算結(jié)果。八、程序設(shè)計(jì)題（本題20分）請(qǐng)?jiān)O(shè)計(jì)一C語(yǔ)言函數(shù)C主：只須寫(xiě)出函數(shù).不必寫(xiě)出完整程序）.該函數(shù)的功能是用盡可能高的時(shí)間效率與空間效率將一個(gè)int類(lèi)型的數(shù)組A[0..n7）的所有元素依次循環(huán)右移k個(gè)位置。例如，對(duì)于某數(shù)組，當(dāng)k=3時(shí)（即把數(shù)組所有元素循環(huán)右移3個(gè)位置）.是將10|20j30I40]50 |701轉(zhuǎn)換為|50|60|70|10|20|30|402.中國(guó)傳媒大學(xué)數(shù)據(jù)結(jié)構(gòu)與計(jì)算機(jī)網(wǎng)絡(luò)歷年考研真題

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

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

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

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

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

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