杭 州 师 范 大 学 硕 士 研 究 生 入 学 考 试 命 题 纸2016 年 考试科目代码 826 考试科目名称计算机基础（本考试科目共 5 页，第 1 页）杭 州 师 范 大 学2016 年招收攻读硕士研究生入学考试题考试科目代码： 826 考试科目名称： 计算机基础 说明：考生答题时一律写在答题纸上，否则漏批责任自负。第一部分：程序设计基础（C 语言）一、单项选择题（每小题 2 分，共 20 分）1、如果 a 的类型为 int 且值为 12，b 的类型为 int 且值为 5，d 的类型为 double 且值为24.0，则 d / (a / b) 的类型及值为（ ）。A. int, 10 B. double, 12.0000 C. int, 12 D. double, 10.00002、“变量 a 的值为 5 或是 6” 应表示为（ ）。A. a = 5 | a = 6 B. a = 5 | a = 6 C. a = 5 for(i = 0; i 2 double factorial(int number);3 int main(void) 4 int n, k;5 double c;6 do 7 printf(“Please input n, k:“);8 scanf(“%d%d“, 9 while(n = maxSizeC. rear = (front + 1) % maxSizeD. front = (rear + 1)%maxSize4. 已知单链表 A 长度为 m，单链表 B 长度为 n，若将 B 连接到 A 的末尾，在没有链尾指针的情况下，算法的时间复杂度为( )。A. O(1) B. O(n) C. O(m) D. O(m + n)5. 对一棵完全二叉树进行层序(从上到上，从左到右)从 1 开始编号。则编号为 n 的结点若杭 州 师 范 大 学 硕 士 研 究 生 入 学 考 试 命 题 纸2016 年 考试科目代码 826 考试科目名称计算机基础（本考试科目共 5 页，第 4 页）存在右孩子，其位置是( )；若存在双亲，其位置是( )。A. B. 2n C. 2n-1 D.2n+1 E. 2nF. 2nn2二、问答题（每小题 10 分，共 40 分）1. 简述堆栈和队列的异同点。2. 简述二叉搜索树中的插入结点算法。3. 简述有向图和无向图的区别，并给出有向图的单源全目标最短路径算法（即，从某一个顶点出发到其余所有顶点的最短路径） 。4. 简述任意 1 种利用二叉树进行排序的算法，并分析其复杂性。第三部分:计算机网络一、单项选择题（共 15 分，每小题 1 分。把最恰当的一个答案填入括号内。 ）1. 以下关于 OSI 参考模型的基本概念的描述中错误的是（ ）A. 术语“OSI 参考模型”中的“开放”是指可以用于任何一种计算机的操作系统BOSI 参考模型定义了开放系统的层次结构、层次之间的相互关系COSI 的服务定义详细地说明了各层所提供的服务，不涉及接口的具体实现方法DOSI 参考模型不是一个标准，而是一种在制定标准时所使用的概念性的框架2. 设立数据链路层的主要目的是将有差错的物理线路变为对网络层无差错（ ） 。A物理链路 B.数据链路 C点一点链路 D端一端链路3. 以下选项中不属于自含时钟编码的是（ ）A. 差分曼彻斯特编码 B曼彻斯特编码 C非归零码 D都不是4. 一台交换机具有 24 个 10/100Mbps 端口和两个 1Gbps 端口，如果所有端口都工作在全双工状态，那么交换机的总带宽最大是（ ） 。A.4.4Gbps B.6.4Gbps C.6.8Gbps D.8.8Gbps5. 以下关于统计时分多路复用技术特征的描述中，错误的是（ ） 。 A. 统计时分多路复用发出的数据不需要带有收发双方的地址B统计时分多路复用允许动态地分配时间片C统计时分多路复用的英文缩写是“ATDM”D多路复用设备也可以采用存储转发方式来调节通信线路的传输速率6. HDLC 帧传输中采取增加转义字符或 0 比特插入的目的是保证数据传输的（ ） 。A透明性 B安全性 C正确性 D可靠性7. 以下关于熟知端口号中错误的是（ ） 。A. DNS: 53 B. FTP:11 C.TFTP: 69 D.NTP: 123.8. 网络层中传输的数据单位是（ ） 。A. 帧 B. 比特流 C IP 数据报 D. 比特流和帧杭 州 师 范 大 学 硕 士 研 究 生 入 学 考 试 命 题 纸2016 年 考试科目代码 826 考试科目名称计算机基础（本考试科目共 5 页，第 5 页）9. 标准的 URL 由 3 部分组成：服务器类型、主机名和路径及（ ） 。A. 进程名 B. 客户名 C. 浏览器名 D.文件名10. 以下关于网络体系结构的研究方法优点的描述中错误的是（ ） 。A允许隔层通信是 OSI 参考模型灵活性的标志 B各层之间相互独立C易于实现和标准化 D实现技术的变化都不会对整个系统工作产生影响11. 在传送 TCP 报文段时，若确认号为 20，表明到序号（ ）为止的数据均正确接收。A18 B19 C20 D2112. 在路由表中，对每一条路由最主要的信息是目的网络地址和（ ） 。A网络地址 B下一跳地址 C接口 D物理地址 13. 某个网络的 IP 地址空间为 201.1.5.0/24，采用子网划分，地址掩码为 255.255.255. 248，那么该网络的最大子网数与每个子网最多可以分配的地址数为（ ） 。A. 32,6 B.32,8 C.8,32 D.8,3014. 将双绞线制作成交叉线（一端按 EIA/TIA 568A 线序，另一端按 EIA/TLA 568B 线序） ，该双绞线连接的两个设备可为（ ） 。A网卡与网卡 B网卡与交换机 C网卡与集线器 D交换机的以太口与下一级交换机的 UPLINK 口。15. 两台计算机利用电话线路传输数据信号时必备的设备是（ ） 。A. 中继器 B.网卡 C. HUB D. MODEM二、简答题（共 35 分）1 OSI/RM 将整个通信功能划分为 7 个层次，简述其层次划分的主要原则。 （5 分）2 请简述单帧停等协议完整的工作过程以及它的特点。 （8 分）3 简述无线局域网的 CSMA/CA 协议与以太网的 CSMA/CD 协议主要区别在哪里？为什么在无线局域网中不能使用 CSMA/CD 协议。 （10 分）4 计算并填写下列表中的内容（12 分）IP 地址 189.77.129.80 主机号子网掩码 255.255.240.0 直接广播地址网络前缀 子 网 内 第 一 个 可 用 IP地 址网络地址 子 网 内 最 后 一 个 可 用 IP地 址