2013杭州师范大学计算机826计算机基础真题.doc

杭 州 师 范 大 学 硕 士 研 究 生 入 学 考 试 命题 纸2013 年 考试科目代码 826 考试科目名称 计算机基础 （本考试科目共 13 页，第 1 页）杭 州 师 范 大 学2013 年招收攻读硕士研究生入学考试题考试科目代码： 826 考试科目名称： 计算机基础 说明：1、考生答题时一律写在答题纸上，否则漏批责任自负；第一部分 程序设计基础一、选择题（每小题 2 分，共 30 分）1完成 C 语言源程序文件编辑后，到生成执行文件，C 语言处理系统必须执行的步骤依次为（ ） 。A链接、编译 B编译、链接C链接、运行 D运行2设有：double x; 通过 scanf 语句正确地输入 x 值的语句是（ ） 。Ascanf(“%f“, x); Bscanf(“%f“, Cscanf(“%lf“, x); Dscanf(“%lf“, 3设有：int x = 10, y = 4, f; double m; 执行语句： f = m = x / y; 后，f、m 的值分别是（ ） 。A2 和 2.5 B3 和 2.5 C2.5 和 2.5 D2 和 2.04设有：int x = 5, y = 7, z = 8; 执行语句：z += x+ | y+ | +z; 后，x、y、z的值分别是（ ） 。A6、7、9 B6、8、10 C6、8、8 D6、8、1杭 州 师 范 大 学 硕 士 研 究 生 入 学 考 试 命题 纸2013 年 考试科目代码 826 考试科目名称 计算机基础 （本考试科目共 13 页，第 2 页）5以下一维数组的定义中，正确的是（ ） 。A#define MAX 5; Bint MAX = 5;int aMAX; int aMAX;Cconst int MAX = 5; Dint MAX;int aMAX; scanf(“%d“, 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+j B*(*(num+j)+i)C*(num+i)+j D*(numi+j)9已知学生结构描述为：struct student int no;char name20;char sex;struct 杭 州 师 范 大 学 硕 士 研 究 生 入 学 考 试 命题 纸2013 年 考试科目代码 826 考试科目名称 计算机基础 （本考试科目共 13 页，第 3 页）int year;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.birth.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在函数外部定义的变量是全局变量杭 州 师 范 大 学 硕 士 研 究 生 入 学 考 试 命题 纸2013 年 考试科目代码 826 考试科目名称 计算机基础 （本考试科目共 13 页，第 4 页）B在函数内部定义的变量是局部变量C函数的形参是局部变量D局部变量不能与全局变量同名12下列程序的输出结果是（ ） 。#include 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(c杭 州 师 范 大 学 硕 士 研 究 生 入 学 考 试 命题 纸2013 年 考试科目代码 826 考试科目名称 计算机基础 （本考试科目共 13 页，第 5 页）int f(int n) if(n = 1)return 1;elsereturn n + f(n - 1);int main(void) printf(“%dn“, f(5);return 0;A21 B10 C16 D1514下列程序的输出结果是（ ） 。#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;杭 州 师 范 大 学 硕 士 研 究 生 入 学 考 试 命题 纸2013 年 考试科目代码 826 考试科目名称 计算机基础 （本考试科目共 13 页，第 6 页）A3 B0 C1 D215若文本文件 example.txt 中原有内容为：good，则运行下面程序后文件 example.txt 中的内容为（ ） 。#include int main(void) FILE *fp;fp = fopen(“example.txt“, “w“);fprintf(fp, “abc“);fclose(fp);return 0;Agoodabc Babcd Cabc Dabcgood二、综合题（每小题 10 分，共 20 分）1查找是计算机程序中常见的操作。所谓查找，就是在数组中寻找一个指定元素的过程。常用的查找算法有：顺序查找和二分（折半）查找。编写一个二分（折半）查找函数：int binarySearch(int key, int list, int arraySize)，第 1 个参数 key 是需要查找的关键字；第 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；在 main 函数中，通过调用 isPrime 和 reverse 函数输出前 100 个杭 州 师 范 大 学 硕 士 研 究 生 入 学 考 试 命题 纸2013 年 考试科目代码 826 考试科目名称 计算机基础 （本考试科目共 13 页，第 7 页）emirp，每行显示 10 个，并适当对齐。第二部分 数据结构一 选择题（每小题 2 分，共 30 分）1. 设 n 是描述问题规模的非负整数，下列程序段的时间复杂度是( )。for (i = 1; i = maxSizeC. rear = (front + 1) % maxSize D. front = (rear + 1)% maxSize5. 对一棵完全二叉树进行层序 (从上到上，从左到右)从 1 开始编号。则编号为 n 的结点若存在双亲，其位置是( )。A. B. 2n C. 2n-1 D.2n+1 E. F.2n 2n2n6. 在下图所示的 4 棵二叉树中，( )不是完全二叉树(Complete Binary Tree)。A. B. C. D. 杭 州 师 范 大 学 硕 士 研 究 生 入 学 考 试 命题 纸2013 年 考试科目代码 826 考试科目名称 计算机基础 （本考试科目共 13 页，第 8 页）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. 快速排序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. 100, 98, 85, 82, 80, 77, 66, 60, 40, 20, 10 B. 100, 85, 98, 77, 80, 60, 82, 40, 20, 10, 66C. 10, 20, 40, 60, 66, 77, 80, 82, 85, 98, 100 D. 100, 85, 40, 77, 80, 60, 66, 98, 82, 10, 20杭 州 师 范 大 学 硕 士 研 究 生 入 学 考 试 命题 纸2013 年 考试科目代码 826 考试科目名称 计算机基础 （本考试科目共 13 页，第 9 页）14. 若用数组 memoryn（memory0 n-1）作为两个栈 S1 和 S2 的共用存储结构，对任何一个栈，只有当 memory 数组全满时才不能入栈操作。为这两个栈分配空间的最佳初始方案是( )。A. S1 的栈底位置为 0，S2 的栈底位置为 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 所在结点的左右子结点中保存的关键字分别是( )。2 41 3 3 03 7A. NULL 48 B.48 30 C. 30 48 D. 30 NULL二、综合题（每小题 10 分，共 20 分）1. 用循环链表表示的整数队列长度为 n，若只设头指针（指向第一个结点的指针） ，则出队和入队的时间复杂度分别是多少，并给出该链表结点结构的 C 语言定义？若要求出队和入队的时间复杂度都为常数时间，则应该如何设计该循环链表，且使得使用空间最少？2. 给定如下有向图 G，请依次回答以下问题: 012534杭 州 师 范 大 学 硕 士 研 究 生 入 学 考 试 命题 纸2013 年 考试科目代码 826 考试科目名称 计算机基础 （本考试科目共 13 页，第 10 页）(1)给出每个结点的入度(in-degree)和出度(out-degree)(2)画出该有向图的邻接矩阵表示(adjacency matrix)(3)画出该有向图的邻接表表示(adjacency list)(4)给出从结点 2 出发的深度优先遍历结果(5)给出从结点 2 出发的广度优先遍历结果第三部分 计算机网络一、选择题（每小题 2 分，共 30 分）1 当 PCM 用于数字化语音系统时，如果将声音分为 128 个量化级，由于系统的采样速率为 8000 样本/秒，那么数据传输速率应该达到（ ） 。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 典型的局域网交换机允许 10Mbps 与 100Mbps 两种网卡共存，它采用的技术是10/100Mbps 的（ ） 。A. 线路交换 B. 令牌控制 C. 自动侦测 D.速率变换7 FDDI 的高可靠性主要取决于它的（ ）和自愈机制。