1、杭 州 师 范 大 学 硕 士 研 究 生 入 学 考 试 命题 纸杭 州 师 范 大 学 2013 年招收攻读硕士研究生入学考试题 考试科目代码： 826 考试科目名称： 计算机基础 说明：1、考生答题时一律写在答题纸上，否则漏批责任自负；第一部分 程序设计基础一、选择题（每小题2分，共30分）1完成C语言源程序文件编辑后，到生成执行文件，C语言处理系统必须执行的步骤依次为（ ）。A链接、编译B编译、链接C链接、运行D运行2设有：double x; 通过scanf语句正确地输入x值的语句是（ ）。Ascanf(%f, x);Bscanf(%f, &x);Cscanf(%lf, x);Dsca
2、nf(%lf, &x);3设有：int x = 10, y = 4, f; double m; 执行语句：f = m = x / y; 后，f、m的值分别是（ ）。A2和2.5B3和2.5C2.5和2.5D2和2.04设有：int x = 5, y = 7, z = 8; 执行语句：z += x+ | y+ | +z; 后，x、y、z的值分别是（ ）。A6、7、9B6、8、10C6、8、8D6、8、15以下一维数组的定义中，正确的是（ ）。A#define MAX 5;Bint MAX = 5; int aMAX; int aMAX;Cconst int MAX = 5; Dint MAX;
3、int aMAX; scanf(%d, &MAX); int aMAX;6以下对二维数组a进行正确初始化的是（ ）。 Aint a23 = 1,2, 3,4, 5,6 ; Bint a3 = 1,2,3,4,5,6 ; Cint a2 = 1,2,3,4,5,6 ;Dint a2 = 1,2, 3,4 ;7设有：char (*p)10; 该语句声明了一个（ ）。A指向含有10个元素的一维字符型数组的指针变量pB指向长度为10的字符串的指针变量pC有10个元素的指针数组p，每个元素可以指向一个字符串D有10个元素的指针数组p，每个元素存放一个字符串8以下（ ）表示与numij是等价的。Anumi
4、+jB*(*(num+j)+i) C*(num+i)+jD*(numi+j)9已知学生结构描述为：struct student int no;char name20;char sex;struct intyear;char month20;int day; birth;struct student s;设变量s中的“生日”应是“1994年7月10日”，下列对“生日”的正确赋值方式是（ ）。As.birth.year = 1994; s.birth.month = 7; s.birth.day = 10;Bs.birth.year = 1994; s.birth.month = 7; s.bir
5、th.day = 10;Cs.birth.year = 1994; strcpy(s.birth.month, 7); s.birth.day = 10;Ds.birth.year = 1994; s.birth.month = 7; s.birth.day = 10;10若用数组名作为函数调用时的实参，则实际上传递给形参的是（ ）。 A数组首地址B数组的第一个元素值C数组中全部元素的植 D数组元素的个数11下列错误的描述是（ ）。 A在函数外部定义的变量是全局变量 B在函数内部定义的变量是局部变量 C函数的形参是局部变量D局部变量不能与全局变量同名12下列程序的输出结果是（ ）。#inclu
6、de int main(void) int k = 0;char c = A; do switch (c+) case A: +k; break; case B: -k; case C: k += 2; break; case D: k = k % 2; break; case E: k = k * 10; break; default: k = k / 3; +k; while(cG);printf(k=%dn, k);return 0;Ak=6Bk=8Ck=7Dk=913下列程序的输出结果是（ ）。#include int f(int n) if(n = 1) return 1; else
7、 return n + f(n - 1);int main(void) printf(%dn, f(5); return 0;A21B10C16D1514下列程序的输出结果是（ ）。#include int f(int x) return x * x + x - 12;int any_function(int (*pf)(int) int n = 0; while(pf(n) +n; return n;int main(void) printf(%dn, any_function(f); return 0;A3B0C1D215若文本文件example.txt中原有内容为：good，则运行下面程
8、序后文件example.txt中的内容为（ ）。#include int main(void) FILE *fp;fp = fopen(example.txt, w);fprintf(fp, abc);fclose(fp);return 0;AgoodabcBabcdCabcDabcgood二、综合题（每小题10分，共20分）1查找是计算机程序中常见的操作。所谓查找，就是在数组中寻找一个指定元素的过程。常用的查找算法有：顺序查找和二分（折半）查找。编写一个二分（折半）查找函数：int binarySearch(int key, int list, int arraySize)，第1个参数key
9、是需要查找的关键字；第2个参数list是需要查找的有序数组；第3个参数arraySize是数组大小。如果在数组list中找到与关键字key匹配的数组元素，则返回该数组元素的下标，否则返回-1。2无暇素数emirp（英文素数prime的逆序）是这样一种素数：一个数本身为素数，且其逆序数也是素数。例如，17是素数，其逆序数71也是，因此17和71是emirp。编写程序，定义函数：int isPrime(int n)，判断n是否是素数，如果是素数，函数返回1，否则返回0；定义函数：int reverse(int n)，求n的逆序数，函数返回n的逆序数，如n为17，函数reverse(n)返回71；在
10、main函数中，通过调用isPrime和reverse函数输出前100个emirp，每行显示10个，并适当对齐。第二部分 数据结构一 选择题（每小题2分，共30分）1. 设n是描述问题规模的非负整数，下列程序段的时间复杂度是( )。for (i = 1; i n - 1;i+) for(j = 1; j = n; j+) for(k = 1; k = maxSizeC. rear = (front + 1) % maxSize D. front = (rear + 1)% maxSize5. 对一棵完全二叉树进行层序(从上到上，从左到右)从1开始编号。则编号为n的结点若存在双亲，其位置是( )
11、。 A. B. 2n C. 2n-1 D.2n+1 E. F.6. 在下图所示的4棵二叉树中，( )不是完全二叉树(Complete Binary Tree)。A. B. C. D. 7.若用邻接矩阵表示有向图，则其中每一行包含的1的个数为( )。 A图中每个顶点的出度 B图中每个顶点的入度 C图中弧的条数 D图中连通分量的数目 8.若无向图G=（V, E）含有7个顶点，要保证图G都是连通的，则需要的边数最少是( )。 A. 16 B. 15 C. 6 D. 219.下列排序算法中，平均时间复杂度为O(nlogn)且占用额外空间最多的是( )。A. 堆排序 B. 插入排序 C. 归并排序 D.
12、 快速排序10.对下图进行拓扑排序，可以得到不同的拓扑序列的个数是( )。 A. 5 B.4 C. 3 D. 211. 若一棵二叉树的前序遍历序列和中序遍历序列分别为abecdf和beadcf，则该二叉树的后序遍历序列为( )。A. ebadfc B. ebdfca C. dfceba D. fdecba12. 为提高散列（hash）表的查找效率，可以采取的正确措施是( ) I. 增大装填因子 II. 设计冲突（碰撞）少的散列函数 III. 处理冲突（碰撞）时避免产生聚集现象 A. 仅I B. 仅I、 II C. 仅III D. 仅II、III13.下列序列中，( )不是堆(heap).A.
13、100, 98, 85, 82, 80, 77, 66, 60, 40, 20, 10 B. 100, 85, 98, 77, 80, 60, 82, 40, 20, 10, 66 C. 10, 20, 40, 60, 66, 77, 80, 82, 85, 98, 100 D. 100, 85, 40, 77, 80, 60, 66, 98, 82, 10, 2014. 若用数组memoryn（memory0n-1）作为两个栈S1和S2的共用存储结构，对任何一个栈，只有当memory数组全满时才不能入栈操作。为这两个栈分配空间的最佳初始方案是( )。A. S1的栈底位置为0，S2的栈底位置为
14、n-1; B. S1的栈底位置为0，S2的栈底位置为n / 2;C. S1的栈底位置为n / 2，S2的栈底位置为0; D. S1的栈底位置为n/2-1, S2的栈底位置为n/2;15.在下图所示的AVL树（平衡二叉树）中，插入关键字48后得到一棵新平衡二叉树。在新平衡二叉树中，关键字37所在结点的左右子结点中保存的关键字分别是( )。 A. NULL 48 B.48 30 C. 30 48 D. 30 NULL二、综合题（每小题10分，共20分）1. 用循环链表表示的整数队列长度为n，若只设头指针（指向第一个结点的指针），则出队和入队的时间复杂度分别是多少，并给出该链表结点结构的C语言定义？
15、若要求出队和入队的时间复杂度都为常数时间，则应该如何设计该循环链表，且使得使用空间最少？2. 给定如下有向图G，请依次回答以下问题:(1) 给出每个结点的入度(in-degree)和出度(out-degree)(2) 画出该有向图的邻接矩阵表示(adjacency matrix)(3) 画出该有向图的邻接表表示(adjacency list)(4) 给出从结点2出发的深度优先遍历结果(5) 给出从结点2出发的广度优先遍历结果第三部分 计算机网络一、选择题（每小题2分，共30分）1 当PCM用于数字化语音系统时，如果将声音分为128个量化级，由于系统的采样速率为8000样本/秒，那么数据传输速率
16、应该达到（ ）。A14.4bps B56Kbps C32Kbps D64Kpbs2 在ATM技术中，信元作为数据传输的基本单位，它的长度是（ ）。A. 43B B.5B C. 53B D. 48B3 在（ ）差错控制方式中，只会重新传输出错的数据帧。A. 连续工作 B. 停止等待 C. 拉回 D. 选择重发4 下列哪个不是决定LAN和MAN特性的要素（ ）。A. 网络拓扑 B. 传输速率 C. 传输介质 D.介质访问控制方法5 数据链路层服务功能主要分为一下3类，面向连接确认服务、无连接确认服务和（ ）。A. 差错控制服务 B. 认证服务 C. 面向连接不确认服务 D. 无连接不确认服务6 典
17、型的局域网交换机允许10Mbps与100Mbps两种网卡共存，它采用的技术是10/100Mbps的（ ）。A. 线路交换 B. 令牌控制 C. 自动侦测 D.速率变换7 FDDI的高可靠性主要取决于它的（ ）和自愈机制。A. 令牌控制 B. 分组交换 C. 线路交换 D.双环结构 8 网络156.26.0.0/27的广播地址是（ ）。A. 156.26.0.255 B.156.26.255.255 C.156.26.0.31 D. 156.26.0.159 ICMP差错报告报文共有5种，目的站不可达到、源站抑制、改变路由、超时和（ ）。A参数问题 B网络不可达C目的主机不存在 D.路由寻址出错
18、10 TCP使用了4种计时器，其中为了控制丢失的或丢弃的报文段，TCP采用了（ ）。A. 坚持计时器 B. 时间等待计时器 C. 重传计时器 D. 保持计时器11 下述（ ）选择正确地描述了OSI/RM的分层次序。A. PH、DL、N、T、P、S、A B. PH、DL、T、N、P、S、AC. PH、DL、N、T、S、P、A D. DL、PH、T、N、P、S、A12 标准的URL由3部分组成：服务器类型、主机名和路径及（ ）。A.文件名 B. 客户名 C. 浏览器名 D. 进程名13 远程登录协议Telnet、电子邮件协议SMTP、文件传输协议FTP依赖于（ ）协议。A. UDP B. TCP
19、C. ICMP D. IGMP14 从协议分析的角度，WWW服务的第一步操作是WWW浏览器对WWW服务器的（ ）。A. 传输连接建立 B. 地址解析 C.域名解析 D.会话连接建立15 在Cisco路由器配置中，在“Router#”模式下输入“?”表示的意思是（ ）。A. 查看用户执行模式下的所有命令B. 查看特权执行模式下的所有命令C. 查看全局配置模式下的所有命令D. 查看接口配置模式下的所有命令二、综合题（每小题10分，共20分）1.请叙述采用CSMA/CD协议的Ethernet网的某结点数据发送流程。2按要求回答以下问题（1）求以下网络地址与子网地址144.12.25.1/16144.12.25.1/24（2）找出以下IP地址的网络号和主机号122.56.2.2 129.15.1.36 202.22.122.111 （3）根据以下数据找出NetId,SubnetId与HostIdIP地址：120.14.22.16子网掩码：255.255.128.0 2013 年 考试科目代码 826 考试科目名称 计算机基础 （本考试科目共 13页，第13 页）
