杭 州 师 范 大 学 硕 士 研 究 生 入 学 考 试 命 题 纸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（n>0）阶乘的算法如下，其时间复杂度是( ) 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 分）