1、重庆理工大学2019年攻读硕士学位研究生入学考试试题学院名称：计算机科学与工程学院 学科、专业名称： 计算机技术考试科目（代码）：计算机基础综合(817)A （试题共4页）注意：1.所有试题的答案均写在专用的答题纸上，写在试题纸上一律无效。2.试题附在考卷内交回。一、 单选题（每题3分，60分）1、“千兆以太网”通常是一种高速局域网，其网络数据传输速率大约为： 。 A.1Mbit/s B.10Mbit/s C.1000Mbit/s D.1000Mbyte/s2、下列软件中，属于应用软件的是： 。 AExcel2010 B.Win7 C.Linux D.UNIX3、IPv4地址用4组十进制数表示
2、，每组数字的最大值： 。 A128 B.256 C.255 D.1274、为了提高软件开发效率，软件开发时尽量采用： 。A汇编语言 B.指令系统 C.高级语言 D.OFFICE20105、在ASCII码表中，根据码值由小到大的排列顺序是: 。A空格字符、数字符、小写英文字母、大写英文字母B数字符、空格字符、小写英文字母、大写英文字母C空格字符、小写英文字母、数字符、大写英文字母D.数字符、小写英文字母、空格字符、大写英文字母6、十进制数126转换成无符号二进制整数是： 。A10001111 B.1111 1111 C.1111 1110 D.0111 11117.下列不是度量存储器容量的单元是
3、： 。A.GB B.TB C.GHz D.MB8.以gif为扩展名的文件通常是: 。A图像文件 B.视频文件 C.音频文件 D.文本文件9.假设邮件服务器的地址是,则用户正确的电子邮箱地址的格式是: 。A用户名 B. 用户名$C用户名 D. 用户名at 10.英文缩写CAI的中文意思是: 。A计算机辅助管理 B.计算机辅助设计C计算机辅助制造 D.计算机辅助教学11.世界上公认的第一台电子计算机诞生的年代是: 。A20世纪30年代 B.20世纪40年代C20世纪50年代 D.20世纪60年代12.在计算机内部用来传送、存储、加工处理的数据或指令所采用的形式是： 。A.八进制 B.十进制 C.二
4、进制 D.十六进制13.用位图格式文件存储与用矢量格式文件存储所占用的空间比较: 。A.相同 B.无法确定 C.更大 D.更小14.在ASCII码表中，英文字母b和A的码值之差的十进制值是: 。A32 B.31 C20 D.6115.影响计算机性能的关键部件是： 。A硬盘 B.显示器 C.内存 D.CPU16.在数据结构中，与所使用计算机无关的是数据的_。 A. 存储结构 B. 逻辑和物理结构 C. 逻辑结构 D. 物理结构 17.栈和队列的共同点是_。A. 都是先进后出 B. 都是先进先出 C. 允许在端点处插入和删除元素 D. 没有共同点18线性链表（动态）是通过_方式表示元素之间的关系的
5、。A. 保存后继元素地址 B. 元素的存储顺序 C. 保存左、右孩子地址 D. 保存后继元素的数组下标19在解决计算机主机与打印机之间速度不匹配的问题时，通常设置一个打印缓冲区，该缓冲区应该是一个_结构。A栈 B队列 C数组 D线性表20数组通常具有的两种基本操作是_。A查找和修改 B查找和索引 C索引和修改 D建立和删除二、 简答题（每小题10分，共60分）1、有一份电文中，共使用 5 个字符：a、b、c、d、e，其出现频率如表1所示：表1 字符及其出现频率字符abcde出现频率47529试画出对应的哈夫曼树（请按左子树根结点的权小于等于右子树根结点的权的次序构造）(5分)，并求出每个字符的
6、哈夫曼编码(5分)。2、对给定的数列 R=2,12,5,8,3,10,7,20,9，构造一棵二叉排序树(5分)，并且： 给出按中序遍历得到的数列R1；(3分) 给出按后序遍历得到的数列R2。(2分)3、对下图画出其邻接表存储结构图（按节点号递增顺序存放）(5分)并用广度优先搜索(3分)和深度优先搜索对其进行遍历（从顶点1出发）(2分)，给出遍历序列。4、对下图使用克鲁斯卡尔算法构造出一棵最小生成树，要求写出每一个步骤。 5、设散列表为 T0.12，散列函数为 H（key）= key%13。给定键值序列是39，36，28，38，44，15，42，12，06，25，要求如下： 分别画出用拉链法和线
7、性探测法处理冲突时所构造的散列表(6分) 求出在等概率情况下，这两种方法查找成功时的平均查找长度(4分)。6、已知序列11，18，4，3，6，15，1，9，18，8，请给出采用归并排序法对该序列作升序排序时每一趟的结果。三、 编程题（每小题10分，共30分）1、现有一个成绩登记表L用带头结点的单链表表示，linklist类型定义如下，现要求完成函数int fun1(linklist *L)的定义，实现统计成绩登记表L中成绩优秀（成绩大于等于90分）的人数功能。typedef struct studentchar *number;/表示学号char *name;/表示姓名int score;/表
8、示成绩struct student *next;linklist;2、现有一个成绩登记表S用顺序表表示，sqlist类型定义如下，现要求完成函数void fun2(sqlist *S)的定义，实现根据成绩非递减对顺序表S排序的功能，要求说明算法类别或算法思想。#define Nmax maxlen /maxlen表示成绩最大个数typedef struct studentint score;/表示成绩NODEtypedef struct NODE studentNmax;/表示成绩int length;/表示长度sqlist;3、现有一个哈夫曼树TREE用二叉链表表示，Bitree类型定义如下，现要求完成函数void fun3(Bitree *TREE)的定义，实现打印哈夫曼树TREE所有节点编码的功能，要求说明算法类别或算法思想。typedef struct nodechar *code;/表示编码struct node *lch,*rch;Bitree;第4页第1页