2015杭州师范大学计算机826计算机基础真题.doc
杭 州 师 范 大 学 硕 士 研 究 生 入 学 考 试 命 题 纸2015 年 考试科目代码 826 考试科目名称 计算机基础 (本考试科目共 6 页,第 1 页)杭 州 师 范 大 学2015 年招收攻读硕士研究生入学考试题考试科目代码: 826 考试科目名称: 计算机基础 说明:考生答题时一律写在答题纸上,否则漏批责任自负。第一部分:程序设计基础(C 语言) (50 分)一、单项选择题(每小题 2 分,共 20 分)1. 以下( )为有效变量名。A. 234 B. 1926sum C. afor(i = 0; i 2 int maxCommonFactor(int a, int b);3 int main(void) 4 int a, b, x;5 printf(“Input a, b:“);6 scanf(“%d%d“, a, b);7 x = maxCommonFactor(a,b);8 printf(“MaxCommonFactor=%dn“, x);9 10 int maxCommonFactor(int a, int b) 11 int r;12 do 13 r = a % b;14 a = b;15 b = r;16 while(r != 0);17 return a;18 程序中存在的错误在第_行。(5 分)杭 州 师 范 大 学 硕 士 研 究 生 入 学 考 试 命 题 纸2015 年 考试科目代码 826 考试科目名称 计算机基础 (本考试科目共 6 页,第 3 页)3. 编写一个二分(折半)查找函数:int binarySearch(int key, int list, int arraySize)第 1 个参数 key 是需要查找的关键字;第 2 个参数 list 是需要查找的有序数组;第 3 个参数 arraySize 是数组大小。如果在数组 list 中找到与关键字 key 匹配的数组元素,则返回该数组元素的下标,否则返回-1。 (10 分)4. 编写程序。猴子第 1 天摘下若干个桃子,当即吃了一半,还不过瘾,又多吃了一个。第2 天早上又将剩下的桃子吃掉一半,又多吃了一个。以后每天早上都吃了前一天剩下的一半另加一个。到第 10 天早上想再吃时,就只剩下一个桃子了。问第 1 天共摘了多少个桃子。(10 分)第二部分:数据结构(50 分)一、单项选择题(每小题 1 分,共 5 分)1. 求整数 n(n0)阶乘的算法如下,其时间复杂度是( ) int fact(int n)if (n = 1) return 1;else n * fact(n - 1);A. O(log2n) B. O(n) C. O(n log2n) D. O(n2)2. 已知两个长度分别为 m 和 n 的有序表,若将它们合并成一个长度为 m+n 的有序表,则最坏情况下的时间复杂度为( )。A. O(n) B. O(m * n) C. O(min(m,n) D. O(m + n)3. 栈的特点是( )A. 先进先出 B. 后进先出 C. 没有特点 D. 后进后出4.假设一个循环队列 queuemaxSize的队头指针为 front,队尾指针为 rear,初始时置front = rear = 0,则循环队列的判空条件为( )。A. rear = front B. rear = maxSizeC. rear +1 =front D. front = (rear + 1) % maxSize5. 若一棵二叉树的先序遍历序列为 a, e, b, d, c,中序遍历序列分别为 e, b, a, d, c,则该二叉树的后序遍历序列为( )。A. beadc B. becda C. dceba D. eacdb 杭 州 师 范 大 学 硕 士 研 究 生 入 学 考 试 命 题 纸2015 年 考试科目代码 826 考试科目名称 计算机基础 (本考试科目共 6 页,第 4 页)二、填空题(每空格 1 分,共 5 分)1. 给定一无序整数序列 56, 70, 33, 65, 12, 24, 48, 92, 35, 86,若用堆排序算法进行排序,则初始建堆(建大顶堆)的结果为 (1) ;若用归并排序,则第一趟排序结果为 (2) ;若用第一个数为轴心元素(pivot)的快速排序,则第一趟排序结果为 (3) 。2. 设一棵完全二叉树(Complete binary tree)中有 21 个结点,如果按照从上到下、从左到右的顺序从 1 开始顺序编号,则编号为 8 的父结点(parent node)的编号是 (4) ,编号为 8 的左孩子结点的编号是 (5) 。三、简答题(共 40 分) 1. 给定某有向图的邻接矩阵如下:(a) 画出该图(b) 给出该图从 V1 出发的深度优先搜索和宽度优先搜索序列(c) 该有向图是否可以有拓扑排序序列?如果有,请给出一个拓扑排序的序列。(10 分)2. 给定一个二叉树的数组存储方式如下图:1 2 3 4 5 6 7 8 9 10 11a b c d g e f(a) 画出该二叉树(b) 写出该二叉树的前序遍历(preorder order)结果(c) 写出该二叉树的中序遍历(inorder order)结果(d) 写出该二叉树的后序遍历(postorder order)结果(e) 写出该二叉树的层序遍历(level order)结果(20 分)杭 州 师 范 大 学 硕 士 研 究 生 入 学 考 试 命 题 纸2015 年 考试科目代码 826 考试科目名称 计算机基础 (本考试科目共 6 页,第 5 页)3. 依次将 60, 30, 20, 50, 78, 85 插入一棵二叉搜索树(Binary search tree),请 (a)给出二叉搜索树定义。 (b)画出每插入一个数后得到的所有二叉搜索树 (c)画出将 30 删除后的二查搜索树(10 分)第三部分:计算机网络(50 分)一、单项选择题(每小题 2 分,共 20 分)1. 以下关于网络分类的描述中错误的是( ) 。A连接用户计算机身边 10m 之内计算机等数字终端设备的网络称为 WSNB覆盖 l0m-l0km 的网络称为 LANC覆盖 l0-l00km 的网络称为 MAND覆盖 l00-l000km 的网络称为 WAN2. 网络层中传输的数据单位是( ) 。A. 帧 B. IP 数据报 C比特流 D. 比特流和帧3. 域名 WWW.SOHU.COM 中属顶级域名的是( ) 。A WWW BSOHU CCOM DWWW.SOHU4. 标准的 URL 由 3 部分组成:服务器类型、主机名和路径及( ) 。A. 进程名 B. 客户名 C. 浏览器名 D.文件名5. 远程登录协议 Telnet、电子邮件协议 SMTP、文件传输协议 FTP 依赖于( )协议。A. TCP B. UDP C. ICMP D. IGMP6. 以下关于网络体系结构的研究方法优点的描述中错误的是( ) 。A允许隔层通信是 OSI 参考模型灵活性的标志 B各层之间相互独立C易于实现和标准化 D 实现技术的变化都不会对整个系统工作产生影响7. 在传送 TCP 报文段时,若确认号为 20,表明到序号( )为止的数据均正确接收。A 18 B19 C20 D21杭 州 师 范 大 学 硕 士 研 究 生 入 学 考 试 命 题 纸2015 年 考试科目代码 826 考试科目名称 计算机基础 (本考试科目共 6 页,第 6 页)8. 以下选项中不属于自含时钟编码的是( ) 。A. 差分曼彻斯特编码 B曼彻斯特编码 B非归零码 D都不是9. 一台交换机具有 24 个 10/100Mbps 端口和两个 1Gbps 端口,如果所有端口都工作在全双工状态,那么交换机的总带宽最大是( ) 。A. 4.4Gbps B. 6.4Gbps C. 6.8Gbps D. 8.8Gbps10. 在路由表中,对每一条路由最主要的信息是目的网络地址和( ) 。A下一跳地址 B网络地址 C接口 D物理地址 二、综合应用题(共 30 分)1. 简述虚拟局域网相对于传统局域网的优点,并举出它三种划分方法。 (10 分)2. 假设有一个 CSMA/CD 网络,其发送速率为 100Mbps,网络电缆长度为 1Km,区间无中断器,主机 A 位于网络电缆的一端,信号在电缆中的速度为 200000km/s。如果主机 A 最先发送帧,并且主机 A 在检测出冲突发生的时候还有数据要发送。请回答:(1)主机 A 检测出冲突最长需要多少时间?(5 分)(2)该网络的帧最小长度是多少?(5 分)3. 假设某主机的 IP 地址为 210.114.105.164,子网掩码分别为(1)255.255.255.240 和(2)255.255.255.224 时,请问该主机所在网络的广播地址和网络地址分别是什么?它们可用的 IP 地址范围分别又是什么?(10 分)