15年研究生昆明理工計(jì)算機(jī)818考試題目和答案

/XX理工大學(xué)2015年碩士研究生招生入學(xué)考試試題<A卷>考試科目代碼：818考試科目名稱：計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合考生答題須知所有題目〔包括填空、選擇、圖表等類型題目答題答案必須做在考點(diǎn)發(fā)給的答題紙上,做在本試題冊上無效。請考生務(wù)必在答題紙上寫清題號。評卷時不評閱本試題冊,答題如有做在本試題冊上而影響成績的,后果由考生自己負(fù)責(zé)。答題時一律使用藍(lán)、黑色墨水筆或圓珠筆作答〔畫圖可用鉛筆,用其它筆答題不給分。答題時不準(zhǔn)使用涂改液等具有明顯標(biāo)記的涂改用品。數(shù)據(jù)結(jié)構(gòu)部分單項(xiàng)選擇題〔共15題,每題2分,共30分1、下面語句段執(zhí)行的時間復(fù)雜度是〔for<i=1;i<=n;i++>for<j=i;j<=n;j++>s++;A>T<n>=n2B>T<n>=n3C>T<n>=O<n2>D>T<n>=O<n3>不可分割的、含有獨(dú)立意義的最小數(shù)據(jù)單位稱為〔 A>數(shù)據(jù)B>數(shù)據(jù)元素C>數(shù)據(jù)項(xiàng)D>記錄3、單鏈表中指針p指向結(jié)點(diǎn)A,若刪除A之后的結(jié)點(diǎn)〔結(jié)點(diǎn)若存在,則需修改指針的操作是〔。Ap->next=p->next->nextBp=p->nextCp=p->next->nextDnext=p4、線性表是〔。A一個有限序列,可以為空B一個有限序列,不能為空C一個無限序列,可以為空D一個無限序列,不能為空5、在數(shù)組A[8][10]中,每一個數(shù)組元素占用4個字節(jié),所有數(shù)組元素相繼存放于一個連續(xù)的存儲空間中,則存放該數(shù)組至少需要的空間是<字節(jié)。10*8*4A>80 B>100C>280 D>3206、假定一個順序循環(huán)隊(duì)列中空一個存儲單元不用,其隊(duì)首和隊(duì)尾指針分別用front和rear表示,則判斷隊(duì)滿的條件為〔

A>front+1==rearB>rear+1==frontC>front==0 D>front==rear7、一個棧的入棧序列是1,2,3,4,5,則該棧不可能的輸出序列是〔A>54321B>43512C>45321 D8、棧操作的特點(diǎn)是<>。A>先進(jìn)后出B>先進(jìn)先出C>

隨機(jī)存取D>順序存取XX理工大學(xué)2015年碩士研究生招生入學(xué)考試試題9、線性表若是采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時,要求內(nèi)存中可用存儲單元的地址<>。A>必須是連續(xù)的B>部分地址必須是連續(xù)的C>一定是不連續(xù)的D>連續(xù)或不連續(xù)都可以10、樹最適合用來表示〔。A有序數(shù)據(jù)元素B元素之間具有分支層次關(guān)系的數(shù)據(jù)C無序數(shù)據(jù)元素D元素間無聯(lián)系的數(shù)據(jù)11、深度為5的二叉樹最多有〔個結(jié)點(diǎn)。A10B16C32D31:2^n-112、在以下所示的有向圖中,頂點(diǎn)D的入度和出度分別是〔A12B21C31D1313、一個AOV網(wǎng)的拓?fù)湫蛄小睞一定是唯一的B不一定是唯一的C一定不是唯一的D以上說法都不正確14、對長度為18的順序存儲的有序表,采用二分查找,則查找第15個元素的比較次數(shù)為<>。A3B4C15、在下面的排序方法中,關(guān)鍵字比較的次數(shù)與記錄的初始排序次序無關(guān)的是〔。A選擇排序B冒泡排序C快速排序D插入排序N<n-1>/2次二、判斷題〔共10題,每題1分,共10分1、時間復(fù)雜度用來描述算法占用存儲空間的多少[W]2、空串就是由空格組成的字符串。[W]3、在順序表中進(jìn)行插入和刪除操作需要移動大量元素,時間效率較低。[R]4、二叉樹中結(jié)點(diǎn)最大的度為2。[R]5、樹中所有結(jié)點(diǎn)都有雙親結(jié)點(diǎn)。[W]6、一個有n個頂點(diǎn)連通圖,其生成樹有n-1條邊。[R]7、有向圖跟無向圖的領(lǐng)接矩陣都是對稱距陣。[W]無向圖的鄰接矩陣是對稱的有向圖是非對稱矩陣XX理工大學(xué)2015年碩士研究生招生入學(xué)考試試題8、二叉排序樹的中序編歷序列是按結(jié)點(diǎn)關(guān)鍵字遞增排序的有序序列。[R]9、若待排序的記錄數(shù)目較小,可采用直接插入排序或直接選擇排序。[R]10、直接插入排序是不穩(wěn)定的。[W]快速排序不穩(wěn)定三、完成如下問題:〔共3題,每題6分,共18分已知一組權(quán)值W={6,8,2,4,9,15,19},請〔按左小右大方式構(gòu)造一棵哈夫曼樹,并計(jì)算出其WPL值?！?分161一棵二叉樹的后序序列和中序序列分別如下,試畫出該二叉樹?！?分中序序列：a+b*c–d/e；后序序列:abc*+de/-后序放中間,中序分兩邊,依次找出跟V1V2V3V4V5V6V7∞18∞∞V1V2V3V4V5V6V7∞18∞∞234618∞5812∞∞∞5∞10∞∞∞∞810∞1520∞2312∞15∞25∞4∞∞2025∞76∞∞∞∞7∞V1V2V3V4V5V6V7四、算法設(shè)計(jì)：〔17分已知DBF<intj>是連通圖的遍歷算法。非連通圖的遍歷算法如下,請?jiān)诖嘶A(chǔ)上修改算法,使該算法具有求出非連通圖中有多少連通分量的功能：TRAVER<>{intj;for<j=0;j<n;j++>visited[j]=FALSE;for<j=0;j<n;j++>{if<!visited[j]>DBF<j>;printf<"compend\n">;}}XX理工大學(xué)2015年碩士研究生招生入學(xué)考試試題網(wǎng)路部分一、單項(xiàng)選擇題〔每小題1分,總分22分1、按照網(wǎng)絡(luò)覆蓋范圍可把計(jì)算機(jī)網(wǎng)絡(luò)分類為〔

。A.廣播式網(wǎng)絡(luò)、點(diǎn)對點(diǎn)式網(wǎng)絡(luò)B.存儲轉(zhuǎn)發(fā)網(wǎng)絡(luò)、電路交換網(wǎng)絡(luò)C.公眾網(wǎng)、專用網(wǎng)D.局域網(wǎng)、城域網(wǎng)和廣域網(wǎng)2、在OSI參考模型中,數(shù)據(jù)鏈路層的協(xié)議數(shù)據(jù)單元是〔

。A.DataB.SegmentC.packetD.frame在傳輸層的數(shù)據(jù)叫段,

網(wǎng)絡(luò)層叫包,

數(shù)據(jù)鏈路層叫幀,

物理層叫比特流,這樣的叫法叫PDU〔協(xié)議數(shù)據(jù)單元3、將物理信道的總頻帶寬分割成若干個子信道,每個子信道傳輸一路信號,這就是〔

。A.同步時分多路復(fù)用

B.空分多路復(fù)用

C.異步時分多路復(fù)用

D.頻分多路復(fù)用

4、在TCP/IP協(xié)議棧中,〔

用來完成域名和IP地址之間的映射。A．DNS B.ARP C.RARP D.ICMP5、網(wǎng)絡(luò)中管理計(jì)算機(jī)通信的規(guī)則稱為〔

。A.協(xié)議

B.介質(zhì)

C.服務(wù)

D.網(wǎng)絡(luò)操作系統(tǒng)

6、〔

這種數(shù)字?jǐn)?shù)據(jù)編碼方式屬于自含時鐘編碼。A.非歸零制 B.脈沖編碼 C.曼徹斯特編碼 D.二進(jìn)制編碼7、計(jì)算機(jī)自動撥號建立線路連接的過程屬于OSI/RM的〔

功能。A.物理層

B.數(shù)據(jù)鏈路層

C.網(wǎng)絡(luò)層

D.傳輸層

自動撥號使用的是slip協(xié)議或PPP協(xié)議8.雙絞線由兩個具有絕緣保護(hù)層的銅導(dǎo)線按一定密度互相絞在一起組成,這樣可以〔

。A.降低成本

B.降低信號干擾的程度C.提高傳輸速度

D.無任何作用

9、在OSI參考模型中,第N層和其上的第N+1層的關(guān)系是〔

。A.

第N+1層將為從第N層接收的信息增加一個信頭B.

第N層利用第N+1層的服務(wù)C.

第N層對第N+1層沒有任何作用D.

第N層為第N+1層提供服務(wù)

10、UDP是TCP/IP協(xié)議簇的〔

協(xié)議。A.應(yīng)用層

B.傳輸層

C.網(wǎng)絡(luò)層

D.網(wǎng)絡(luò)接口層

11、一座大樓內(nèi)的一個計(jì)算機(jī)網(wǎng)絡(luò)系統(tǒng),屬于〔

。A.PAN

B.LAN

C.MAN

D.WAN

12、制定FDDI標(biāo)準(zhǔn)的機(jī)構(gòu)是〔

。A.

ISO

B.IEEE802委員會

C.ANSI

美國國家標(biāo)準(zhǔn)局

D.IT13、通信系統(tǒng)必須具備的三個基本要素是〔

.。A.

終端、電纜、計(jì)算機(jī)

B.信號發(fā)生器、通信線路、信號接收設(shè)備C.信源、信道、信宿

D.終端、通信設(shè)施、接收設(shè)備

XX理工大學(xué)2015年碩士研究生招生入學(xué)考試試題14、Internet上的3個傳統(tǒng)的基本應(yīng)用是〔

。A.Telnet、FTP、Email

B.Telnet、FTP、WWW

C.FTP、WWW、Email

D.WWW、BBS、SNMP

15、OSI的網(wǎng)絡(luò)管理標(biāo)準(zhǔn)框架的基本網(wǎng)絡(luò)管理功能不包括〔

A.計(jì)費(fèi)管理

B.應(yīng)用程序管理

C.性能管理

D.安全管理

配置管理、性能管理、故障管理、安全管理和計(jì)費(fèi)管理16、IP地址190是〔

地址。A.A類

B.B類

C.C類

D.D類

A類網(wǎng)絡(luò)的IP地址范圍為－54；

B類網(wǎng)絡(luò)的IP地址范圍為：－54；

C類網(wǎng)絡(luò)的IP地址范圍為：－54。17、以下哪種總線不是網(wǎng)卡的總線類型〔

。A.AGP

B.ISA

C.PCI

D.EISA

ISA、PCI、PCI-X、PCMCIA和USB18、IEEE802.5與以下哪個網(wǎng)絡(luò)相關(guān)〔

。A.TokenRingB.Ethernet

C.Internet

D.ATM

EEE802.1

—局域網(wǎng)概述、體系結(jié)構(gòu)、網(wǎng)絡(luò)管理和網(wǎng)絡(luò)互聯(lián)

IEEE802.2

—邏輯鏈路控制

LLC

IEEE802.3—CSMA/CD訪問方法和物理層規(guī)范,主要包括如下幾個標(biāo)準(zhǔn)：

IEEE802.3

—

CSMA/CD介質(zhì)訪問控制標(biāo)準(zhǔn)和物理層規(guī)范：定義了四種不同介質(zhì)10Mbps以太網(wǎng)

規(guī)范

：10BASE2、10BASE5、10BASET、10BASEF

IEEE802.5—Token

Ring〔令牌環(huán)訪問方法和物理層規(guī)范

IEEE802.6—城域網(wǎng)訪問方法和物理層規(guī)范

IEEE802.11

—無線局域網(wǎng)訪問方法和物理層規(guī)范,包括：

19、當(dāng)電子郵件程序向郵件服務(wù)器發(fā)送郵件時,使用的是〔

協(xié)議。A.PPP B.POP3 C.SMTP D.UDP20、不同自治系統(tǒng)的路由器之間所使用的動態(tài)路由協(xié)議歸類為〔

。A.OSPF B.EGP C.IGP D.RIP21、以下軟件中〔

不是瀏覽器。A.OutlookExpress

B.Netscape

C.Firefox

D.InternetExplorer

22、Intranet指〔

。A.萬維網(wǎng)

B.企業(yè)內(nèi)部網(wǎng)

C.環(huán)球互連網(wǎng)

D.交換網(wǎng)二、綜合應(yīng)用題〔總分53分1、簡述調(diào)制解調(diào)器的主要功能?！?0分〔1信號轉(zhuǎn)換

〔2確保信源和信宿兩端同步

〔3提高數(shù)據(jù)在傳輸過程中的抗干擾能力

〔4實(shí)現(xiàn)信道的多路復(fù)用2、網(wǎng)絡(luò)互連的含義是什么？〔10分所謂網(wǎng)絡(luò)的互聯(lián)是指將兩個以上的計(jì)算機(jī)網(wǎng)絡(luò),通過一定的方法,用一種或多種通信處理設(shè)備相互連接起來,以構(gòu)成更大的網(wǎng)絡(luò)系統(tǒng).網(wǎng)絡(luò)互聯(lián)的形式有局域網(wǎng)與局域網(wǎng),局域網(wǎng)與廣域網(wǎng),廣域網(wǎng)與廣域網(wǎng)的互聯(lián)三種。設(shè)某數(shù)據(jù)通信系統(tǒng)采用CRC校驗(yàn),生成多項(xiàng)式G〔X=X4+X3+1。若目的節(jié)點(diǎn)接收到的二進(jìn)制比特串是110111001,試問傳輸過程中是否出現(xiàn)了差錯？為什么？〔10分G<X>=11001110111001/11001余數(shù)不為0,所以出現(xiàn)了差錯4、電子郵件地址的格式是怎么樣的？各部分的含義是什么？〔10分一個電子郵件地址的一般格式是由USER@組成的

USER表示用戶

MAILSERVER表示提供郵件服務(wù)的服務(wù)器地址

@是AT的意思,連起來就是某用戶在某郵件服務(wù)器十進(jìn)制IP地址為請轉(zhuǎn)換成二進(jìn)制形式,并說明是哪一類IP地址,該類地址最大網(wǎng)絡(luò)數(shù)和每個網(wǎng)絡(luò)中最大主機(jī)數(shù)?！?3分A類網(wǎng)段計(jì)算：

根據(jù)規(guī)定,A類地址的網(wǎng)絡(luò)標(biāo)識必須以"0"開頭。那么其網(wǎng)段數(shù)應(yīng)該為0XXXXXXX．YYYYYYYY．YYYYYYYY．YYYYYYYY即后面有七位數(shù)字,因?yàn)槭嵌M(jìn)制數(shù),所以網(wǎng)段數(shù)應(yīng)該為：

27,即2的7次冪個網(wǎng)段,等于128,即網(wǎng)段應(yīng)該是0—127之間。而網(wǎng)絡(luò)空間計(jì)算都必須"減2",這是因?yàn)橐鄢齼蓚€保留地址：二進(jìn)制數(shù)里全是"0"和全是"1"的要保留。"0"做為網(wǎng)絡(luò)號,"1"做為廣播號。所以A類地址的網(wǎng)段為1—126.

A類主機(jī)數(shù)計(jì)算：

因?yàn)楹竺?4位是主機(jī)標(biāo)識,所以主機(jī)數(shù)應(yīng)該是224,即2的24次冪

224=412=166=2563=16777216,扣除兩個保留地址后,主機(jī)最大數(shù)應(yīng)該是16777214個。

綜上所述,A類IP地址范圍應(yīng)該是：~54

其中紅色的為網(wǎng)絡(luò)標(biāo)識,綠色為主機(jī)標(biāo)識

B類網(wǎng)段計(jì)算：

根據(jù)規(guī)定,A類地址的網(wǎng)絡(luò)標(biāo)識必須以"10"開頭。那么其網(wǎng)段數(shù)應(yīng)該為10XXXXXX．XXXXXXXX．YYYYYYYY．YYYYYYYY