杭 州 师 范 大 学 硕 士 研 究 生 入 学 考 试 命 题 纸2017 年 考试科目代码 825 考试科目名称 计算机基础 （本考试科目共 9 页，第 1 页）杭 州 师 范 大 学2017 年招收攻读硕士研究生入学考试题考试科目代码： 825 考试科目名称： 计算机基础 说明：考生答题时一律写在答题纸上，否则漏批责任自负。第一部分：程序设计基础（C 语言）一、判断题（每小题 2 分，共 20 分）1、C 语言的标识符是区分大小写的。（ ）2、在编译 C 源程序时，计算机根本不会去识别各个变量名的具体含义，因此命名规范对编写 C 程序而言不是必要的，而且有可能会降低编写 C 源程序的效率。（ ）3、C 语言中，注释不可以出现在程序中任意的地方。（ ）4、C 语言程序中的变量必须先声明后使用。（ ）5、在 C 语言中，'B'和“B“在内存中的表示没有区别。（ ）6、一个复合语句是作为一个语句处理的且在逻辑上相互关联的一组语句。（ ）7、C 语言程序的三种基本结构是顺序结构、分支（选择）结构和循环结构。（ ）8、C 语言的 double 类型数据可以精确表示任何实数。（ ）9、在 C 语言中，将语句“if(x=5) y+;”误写作“if(x=5) y+;”，将导致编译错误。（ ）10、在 switch 语句中，表达式和常量表达式的值只能是整型、字符型或枚举型。（ ）二、单项选择题（每小题 2 分，共 40 分）杭 州 师 范 大 学 硕 士 研 究 生 入 学 考 试 命 题 纸2017 年 考试科目代码 825 考试科目名称 计算机基础 （本考试科目共 9 页，第 2 页）1、程序的开发步骤中不包括（ ） 。A. 撰写文档 B. 程序测试 C. 编译链接 D. 运行程序2、以下（ ）为有效变量名。A. 234 B. 1926sum C. a double z; 则以下语句中错误的是（ ） 。A. scanf(“%2d*%d%lf“, B. scanf(“%x%*d%o“, C. scanf(“%d,%lx,%le“, D. scanf(“%x%o%6.2f“, 7、以下程序的输出结果是（ ） 。#include int main(void) int a = 1234;printf(“%2dn“, a);return 0;A. 1234 B. 提示出错、无结果 C. 12 D. 348、以下非法的赋值语句是（ ） 。A. n=+i; B. x=(j-); C. +(i+1); D. j+;9、已知：int x=5,y=5,z=5; 执行语句：x%=y+z; 后，x 的值是（ ） 。A. 0 B. 5 C. 6 D. 110、 “变量 a 的值为 5 或是 6” 应表示为（ ） 。A. a = 5|a = 6 B. a = 5|a = 6C. a = 5while(k=1)k+;while 循环执行的次数是（ ） 。A. 无限次 B. 有语法错，不能执行C. 一次也不执行 D. 执行一次13、语句 for(i = 1; i void m(int x, int y) x = 3;y0 = 3;int main(void) int x = 0;int y1;m(x, y);printf(“%d#%dn“, x, y0);return 0;2、以下程序的输出结果是_。#include #include struct NODE int num;struct NODE *next;int main(void) struct NODE *p, *q, *r;int sum = 0;p = (struct NODE *)malloc(sizeof(struct NODE);q = (struct NODE *)malloc(sizeof(struct NODE);r = (struct NODE *)malloc(sizeof(struct NODE);p->num = 1;q->num = 2;r->num = 3;杭 州 师 范 大 学 硕 士 研 究 生 入 学 考 试 命 题 纸2017 年 考试科目代码 825 考试科目名称 计算机基础 （本考试科目共 9 页，第 5 页）p->next = q;q->next = r;r->next = NULL;sum += q->next->num;sum += p->num;printf(“%dn“, sum);return 0;3、下列程序执行后，文件 example.txt 中内容是_。#include #include void fun(char *filename, char *str) FILE *fp;int i;fp = fopen(filename, “w“);for(i = 0; i < strlen(str); +i)fputc(stri, fp);fclose(fp);int main(void) fun(“example.txt“, “gelivable“);fun(“example.txt“, “awesome“);return 0;第二部分：数据结构一、单选题（每小题 2 分，共 40 分）1、下列程序段的时间复杂度为( )。count = 0;for (k = 1; k <= n; k *= 2)for (j = 1; j <= n; j+)杭 州 师 范 大 学 硕 士 研 究 生 入 学 考 试 命 题 纸2017 年 考试科目代码 825 考试科目名称 计算机基础 （本考试科目共 9 页，第 6 页）count+;A、O(log 2n) B、O( n) C、O( nlog2n) D、O( n2)2、设顺序线性表中有 n 个数据元素，则删除表中第 i 个元素需要移动( )个元素。A、n-i B、n+l -i C、n-1-i D、i3、一个栈的入栈序列是 a,b,c,d,e,则栈的不可能的输出序列是( )。A、edcba B、decba C、dceab D、abcde4、下列选项中，可以使用二分法查找（binary search）的关键字序列是( )，假设所有数据均保存的数组中。A、500, 200, 450, 180 B、500, 450, 200, 180 C、180，500，200，450 D、180, 200, 500,450 5、循环队列 SQ 的存储空间是数组 dm，队头、队尾指针分别是 front 和rear，则执行出队列操作后其头指针 front 值是( )。Afront=front+1 B. front=(front+1)%(m-1)C. front=(front-1)%m D. front=(front+1)%m6、设二维数组 Amn按行优先顺序存储，如果 A00的地址是 LA，每个元素占 1 个字节，则元素 Aij的地址为( )。A、LA+(i*m+j) B、LA+(i*n+j) C、LA+(i-1)*n+j-1 D、LA+(i-1)*m+j-1 7、用“左孩子-兄弟” （left child right sibling）表示法作为树的存储结构，一棵结点个数大于 2 的树转化为二叉树后( )。A、二叉树的根仅含左子树 B、二叉树的根仅含右子树C、二叉树的根既含左子树又含右子树 D、以上三种情况均可能8、对右边的二叉树做中序遍历（inorder traversal）的结果是( )。A、debxac B、abdexc C、edxbca D、abcdxe9、设线性表的长度为 n，则顺序查找成功的平均比较次数为( )。A、n B、n/2 C、(n+1)/2 D、(n-1)/210、在下列排序算法中，平均时间复杂度为 O（ nlog2n）的是( )。A、直接插入排序（Insertion sort） B、快速排序（Quick sort）C、起泡排序（Bubble sort） D、基数排序（radix sort）acbxde杭 州 师 范 大 学 硕 士 研 究 生 入 学 考 试 命 题 纸2017 年 考试科目代码 825 考试科目名称 计算机基础 （本考试科目共 9 页，第 7 页）11、在下列排序算法中，需要线性附助空间 O(n)的算法是( )。A、堆排序（Heap sort） B、归并排序（Merge sort） C、快速排序（Quick sort） D、希尔排序（Shell sort）12、如果 G 是一个共有 n 个顶点的有向完全图，则该图中共有( )条弧。A、 （ n2-1）/2 B、 n(n-1) / 2 C、 n(n-1) D、 n2-113、用 Dijkstra 算法求无向网的单源点最短路径，假设用邻接矩阵作为图的存储结构，则算法的时间复杂度为( )。A、O( n + e) B、O( n) C、O( n2) D、O( n*e)其中：n 为图中的顶点数，e 为图中边的个数。14、对下图的有向图进行拓扑排序，得到的拓扑序列可能是( )。A、 3,1,2,6,4,5 B、3,1,2,4,6,5 C、3,1,4,2,5,6 D、3,1,4,2,6,515、二叉树的第 k 层的结点数最多为( )。A、2 k-1 B、2K+1 C、2K-1 D、 2 k-116、设有 6 个顶点的有向图，该图至少应有( )条边才能确保是一个连通图。A、6 B、5 C、7 D、817、已知单链表 A 长度为 m，单链表 B 长度为 n，若将 B 连接到 A 的末尾，在没有链尾指针的情况下，算法的时间复杂度为( )。A、O(1) B、O(n) C、O(m) D、O(m + n)18、对一棵完全二叉树进行层序(从上到上，从左到右)从 1 开始编号。则编号为n 的结点若存在右孩子，其位置是( )。A、2 n B、 2 n-1 C、2 n+1 D、 2n3 41625杭 州 师 范 大 学 硕 士 研 究 生 入 学 考 试 命 题 纸2017 年 考试科目代码 825 考试科目名称 计算机基础 （本考试科目共 9 页，第 8 页）19、单链表和双向循环链表表示 List 时常常增加一个头结点，其目的是( )。A.为了简化查找算法 B.为了简化归并算法C.为插入删除操作时不需要做特殊的处理 D.以上说法都不对。20、在下图所示的 4 棵二叉树中，( )不是完全二叉树(Complete Binary Tree)。A、 B、 C、 D、 二、综合应用题（共 35 分） 1、简述堆栈和队列的特点，并分别给出应用实例。(10 分)2、已知一棵二叉树的中序序列和后序序列分别如下，请画出该二叉树。(10 分)中序序列：D I G J L K B A E C H F后序序列：I L K J G D B E H F C A3、请写出在二叉查找树（Binary Search Tree）中查找某个值的算法。 （15 分）杭 州 师 范 大 学 硕 士 研 究 生 入 学 考 试 命 题 纸2017 年 考试科目代码 825 考试科目名称 计算机基础 （本考试科目共 9 页，第 9 页）