重慶理工大學(xué)2019年攻讀碩士學(xué)位研究生入學(xué)考試試題學(xué)院名稱：計(jì)算機(jī)科學(xué)與工程學(xué)院 學(xué)科、專業(yè)名稱： 計(jì)算機(jī)技術(shù)考試科目（代碼）：計(jì)算機(jī)基礎(chǔ)綜合(817)A （試題共4頁(yè)）注意：1.所有試題的答案均寫(xiě)在專用的答題紙上，寫(xiě)在試題紙上一律無(wú)效。2.試題附在考卷內(nèi)交回。一、 單選題（每題3分，60分）1、“千兆以太網(wǎng)”通常是一種高速局域網(wǎng)，其網(wǎng)絡(luò)數(shù)據(jù)傳輸速率大約為： 。 A.1Mbit/s B.10Mbit/s C.1000Mbit/s D.1000Mbyte/s2、下列軟件中，屬于應(yīng)用軟件的是： 。 AExcel2010 B.Win7 C.Linux D.UNIX3、IPv4地址用4組十進(jìn)制數(shù)表示，每組數(shù)字的最大值： 。 A128 B.256 C.255 D.1274、為了提高軟件開(kāi)發(fā)效率，軟件開(kāi)發(fā)時(shí)盡量采用： 。A匯編語(yǔ)言 B.指令系統(tǒng) C.高級(jí)語(yǔ)言 D.OFFICE20105、在ASCII碼表中，根據(jù)碼值由小到大的排列順序是: 。A空格字符、數(shù)字符、小寫(xiě)英文字母、大寫(xiě)英文字母B數(shù)字符、空格字符、小寫(xiě)英文字母、大寫(xiě)英文字母C空格字符、小寫(xiě)英文字母、數(shù)字符、大寫(xiě)英文字母D.數(shù)字符、小寫(xiě)英文字母、空格字符、大寫(xiě)英文字母6、十進(jìn)制數(shù)126轉(zhuǎn)換成無(wú)符號(hào)二進(jìn)制整數(shù)是： 。A10001111 B.1111 1111 C.1111 1110 D.0111 11117.下列不是度量存儲(chǔ)器容量的單元是： 。A.GB B.TB C.GHz D.MB8.以gif為擴(kuò)展名的文件通常是: 。A圖像文件 B.視頻文件 C.音頻文件 D.文本文件9.假設(shè)郵件服務(wù)器的地址是,則用戶正確的電子郵箱地址的格式是: 。A用戶名 B. 用戶名$C用戶名 D. 用戶名at 10.英文縮寫(xiě)CAI的中文意思是: 。A計(jì)算機(jī)輔助管理 B.計(jì)算機(jī)輔助設(shè)計(jì)C計(jì)算機(jī)輔助制造 D.計(jì)算機(jī)輔助教學(xué)11.世界上公認(rèn)的第一臺(tái)電子計(jì)算機(jī)誕生的年代是: 。A20世紀(jì)30年代 B.20世紀(jì)40年代C20世紀(jì)50年代 D.20世紀(jì)60年代12.在計(jì)算機(jī)內(nèi)部用來(lái)傳送、存儲(chǔ)、加工處理的數(shù)據(jù)或指令所采用的形式是： 。A.八進(jìn)制 B.十進(jìn)制 C.二進(jìn)制 D.十六進(jìn)制13.用位圖格式文件存儲(chǔ)與用矢量格式文件存儲(chǔ)所占用的空間比較: 。A.相同 B.無(wú)法確定 C.更大 D.更小14.在ASCII碼表中，英文字母b和A的碼值之差的十進(jìn)制值是: 。A32 B.31 C20 D.6115.影響計(jì)算機(jī)性能的關(guān)鍵部件是： 。A硬盤 B.顯示器 C.內(nèi)存 D.CPU16.在數(shù)據(jù)結(jié)構(gòu)中，與所使用計(jì)算機(jī)無(wú)關(guān)的是數(shù)據(jù)的_。 A. 存儲(chǔ)結(jié)構(gòu) B. 邏輯和物理結(jié)構(gòu) C. 邏輯結(jié)構(gòu) D. 物理結(jié)構(gòu) 17.棧和隊(duì)列的共同點(diǎn)是_。A. 都是先進(jìn)后出 B. 都是先進(jìn)先出 C. 允許在端點(diǎn)處插入和刪除元素 D. 沒(méi)有共同點(diǎn)18線性鏈表（動(dòng)態(tài)）是通過(guò)_方式表示元素之間的關(guān)系的。A. 保存后繼元素地址 B. 元素的存儲(chǔ)順序 C. 保存左、右孩子地址 D. 保存后繼元素的數(shù)組下標(biāo)19在解決計(jì)算機(jī)主機(jī)與打印機(jī)之間速度不匹配的問(wèn)題時(shí)，通常設(shè)置一個(gè)打印緩沖區(qū)，該緩沖區(qū)應(yīng)該是一個(gè)_結(jié)構(gòu)。A棧 B隊(duì)列 C數(shù)組 D線性表20數(shù)組通常具有的兩種基本操作是_。A查找和修改 B查找和索引 C索引和修改 D建立和刪除二、 簡(jiǎn)答題（每小題10分，共60分）1、有一份電文中，共使用 5 個(gè)字符：a、b、c、d、e，其出現(xiàn)頻率如表1所示：表1 字符及其出現(xiàn)頻率字符abcde出現(xiàn)頻率47529試畫(huà)出對(duì)應(yīng)的哈夫曼樹(shù)（請(qǐng)按左子樹(shù)根結(jié)點(diǎn)的權(quán)小于等于右子樹(shù)根結(jié)點(diǎn)的權(quán)的次序構(gòu)造）(5分)，并求出每個(gè)字符的哈夫曼編碼(5分)。2、對(duì)給定的數(shù)列 R=2,12,5,8,3,10,7,20,9，構(gòu)造一棵二叉排序樹(shù)(5分)，并且： 給出按中序遍歷得到的數(shù)列R1；(3分) 給出按后序遍歷得到的數(shù)列R2。(2分)3、對(duì)下圖畫(huà)出其鄰接表存儲(chǔ)結(jié)構(gòu)圖（按節(jié)點(diǎn)號(hào)遞增順序存放）(5分)并用廣度優(yōu)先搜索(3分)和深度優(yōu)先搜索對(duì)其進(jìn)行遍歷（從頂點(diǎn)1出發(fā)）(2分)，給出遍歷序列。4、對(duì)下圖使用克魯斯卡爾算法構(gòu)造出一棵最小生成樹(shù)，要求寫(xiě)出每一個(gè)步驟。 5、設(shè)散列表為 T0.12，散列函數(shù)為 H（key）= key%13。給定鍵值序列是39，36，28，38，44，15，42，12，06，25，要求如下： 分別畫(huà)出用拉鏈法和線性探測(cè)法處理沖突時(shí)所構(gòu)造的散列表(6分) 求出在等概率情況下，這兩種方法查找成功時(shí)的平均查找長(zhǎng)度(4分)。6、已知序列11，18，4，3，6，15，1，9，18，8，請(qǐng)給出采用歸并排序法對(duì)該序列作升序排序時(shí)每一趟的結(jié)果。三、 編程題（每小題10分，共30分）1、現(xiàn)有一個(gè)成績(jī)登記表L用帶頭結(jié)點(diǎn)的單鏈表表示，linklist類型定義如下，現(xiàn)要求完成函數(shù)int fun1(linklist *L)的定義，實(shí)現(xiàn)統(tǒng)計(jì)成績(jī)登記表L中成績(jī)優(yōu)秀（成績(jī)大于等于90分）的人數(shù)功能。typedef struct studentchar *number;/表示學(xué)號(hào)char *name;/表示姓名int score;/表示成績(jī)struct student *next;linklist;2、現(xiàn)有一個(gè)成績(jī)登記表S用順序表表示，sqlist類型定義如下，現(xiàn)要求完成函數(shù)void fun2(sqlist *S)的定義，實(shí)現(xiàn)根據(jù)成績(jī)非遞減對(duì)順序表S排序的功能，要求說(shuō)明算法類別或算法思想。#define Nmax maxlen /maxlen表示成績(jī)最大個(gè)數(shù)typedef struct studentint score;/表示成績(jī)NODEtypedef struct NODE studentNmax;/表示成績(jī)int length;/表示長(zhǎng)度sqlist;3、現(xiàn)有一個(gè)哈夫曼樹(shù)TREE用二叉鏈表表示，Bitree類型定義如下，現(xiàn)要求完成函數(shù)void fun3(Bitree *TREE)的定義，實(shí)現(xiàn)打印哈夫曼樹(shù)TREE所有節(jié)點(diǎn)編碼的功能，要求說(shuō)明算法類別或算法思想。typedef struct nodechar *code;/表示編碼struct node *lch,*rch;Bitree;第5頁(yè)第1頁(yè)