2018杭州师范大学计算机825计算机基础真题.doc
杭 州 师 范 大 学 硕 士 研 究 生 入 学 考 试 命 题 纸2018 年 考试科目代码 825 考试科目名称 计算机基础 (本考试科目共 8 页,第 1 页)杭 州 师 范 大 学2018 年招收攻读硕士研究生入学考试题考试科目代码: 825 考试科目名称: 计算机基础 说明:考生答题时一律写在答题纸上,否则漏批责任自负。第一部分:程序设计基础(C 语言)一、判断题(每小题 2 分,共 20 分)1、可执行的 C 程序一般应该含有 main 函数,它是 C 程序执行的入口。( )2、在 C 语言中,标识符是不区分大小写的。( )3、C 语言的 int 类型数据可以表示任何整数。( )4、在编译 C 源程序时,计算机根本不会去识别各个变量名的具体含义。但命名规范对编写 C 程序而言是必要的,可以提高程序可读性和可维护性。( )5、在 C 语言中,可以给指针变量赋一个整数作为地址值。( )6、假设有 int a10,*p;则 p= 则标识符 p 是一个指向有 4 个整型元素的一维数组的指针变量。( )8、若有定义:int *p; 使 p 指向类型相同的 3 个连续存储单元的语句是:p=malloc(3*sizeof(int); ( )9、用 malloc 函数动态分配的内存是在栈中分配的,而不是在堆中分配的。( )10、对二维数组 a34,a+1 与 a1都是数组第二行的首地址。( )二、单项选择题(每小题 2 分,共 40 分)1、算法是一个计算过程,是程序设计的基础和精髓。一个有效的算法应该具有如下特点,其中错误的是( ) 。A.零个或多个输入及一个或多个输出 B.无穷性杭 州 师 范 大 学 硕 士 研 究 生 入 学 考 试 命 题 纸2018 年 考试科目代码 825 考试科目名称 计算机基础 (本考试科目共 8 页,第 2 页)C.可行性 D.确定性2、若有以下语句:int b; char c10;则正确的输入语句是( ) 。A. scanf(“%d%s“, B. scanf(“%d%s“, C. scanf(“%s%s“, b, c); D. scanf(“%d%s“, b, 3、设 a 为 5,执行下列语句后,b 的值不为 2 的是( ) 。A. b = a / 2; B. b = 6 - (-a); C. b = a % 2; D. b = a 3 ? 2 : 2;4、若有定义:int a=3, b=4, c=5; 则以下表达式中值为 0 的是( ) 。A. a int main(void) f();#ifdef N#undef N#endifreturn 0;void f(void) #if defined(N)printf(“N is %dn“, N);#elseprintf(“N is undefinedn“);#endif2、以下程序的输出结果是_。#include void swap1(int c) int t;t = c0;c0 = c1;c1 = t; void swap2(int c0,int c1) int t;杭 州 师 范 大 学 硕 士 研 究 生 入 学 考 试 命 题 纸2018 年 考试科目代码 825 考试科目名称 计算机基础 (本考试科目共 8 页,第 5 页)t = c0;c0 = c1;c1 = t;int main(void) int a2 = 3, 5, b2 = 3, 5;swap1(a); swap2(b0, b1);printf(“%d#%d#%d#%dn“, a0, a1, b0, b1);return 0;3、以下程序的输出结果是_。#include struct node int k; struct node *link; ; int main(void) struct node m5, *p = m, *q = m + 4; int i = 0; while(p != q) p-k = +i; p+; q-k = i+; q-; q-k = i; for(i = 0; i 0; j - -)printf(“%dn“, j);A. O(n) B. (n2) C. O(nlogn) D. O(n3)2.假设一个循环队列 QmaxSize的队头指针为 front,队尾指针为 rear,队列的最大容量为 maxSize,除此之外,该队列再没有其他数据成员,则该队列的队满条件是( )。A. front = rear B. front + rear = maxSizeC. rear = (front + 1) % maxSize D. front = (rear + 1)%maxSize3. 若元素 1、2、3 依次进栈,允许进栈和出栈操作交替进行,则下列序列中不可能得到的出栈序列是( )。A. 1 2 3 B. 3 1 2 C. 1 3 2 D. 3 2 14.若用邻接矩阵表示有向图,则其中每一列包含的1的个数代表为( )。A图中每个顶点的出度 B图中每个顶点的入度C图中弧的条数 D图中连通分量的数目5.如果所有关键字都相等,那么插入排序算法的时间复杂度为( )。A. O(1) B.O(n) C. O(nlogn) D.O(n2)6.下列排序算法中,平均时间复杂度为 O(nlogn)且占用额外空间最多的是( )。A. 堆排序 B. 插入排序 C. 归并排序 D. 快速排序7.若有向图 G=(V, E)含有 7 个顶点,要保证图 G 都是强连通的,则需要的边数最少是( )。A. 6 B. 7 C. 12 D. 148.若用数组 SN(S0N-1)作为两个栈 S1 和 S2 的共用存储结构,对任何一个栈,只有当 S 数组全满时才不能入栈操作。为这两个栈分配空间的最佳初始方案杭 州 师 范 大 学 硕 士 研 究 生 入 学 考 试 命 题 纸2018 年 考试科目代码 825 考试科目名称 计算机基础 (本考试科目共 8 页,第 7 页)是( )。A. S1 的栈底位置为-1,S2 的栈底位置为 N; B. S1 的栈底位置为-1,S2 的栈底位置为 N / 2;C. S1 的栈底位置为 0,S2 的栈底位置为 N-1; D. S1 的栈底位置为 N/2 -1,S2 的栈底位置为 N/2。9. 以下排序方法中,当输入为已排好序的序列时,( )算法时间复杂度最高。A.选择排序 B.插入排序 C.冒泡排序 D.快速排序10.下列序列中,( )不是堆(heap).A. 100, 98, 85, 82, 80, 77, 66, 60, 40, 20, 10B. 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二、填空题 (每空 2 分,共 20 分)1. 若一棵二叉树的中序序遍历序列和后序遍历序列分别为 ABCDEFG 和 BDCAFGE 则该二叉树的前序遍历序列为(1) ,层序遍历结果为(2) 。2. 给定序列 25, 40, 11, 97, 59, 30, 87, 73, 21 将其进行升序排列,如使用快速排序(quick sort) ,第一轮排序完成后序列为(3) ;如使用堆排序(heap sort) ,第一轮完成后(建堆完成后) ,序列为 (4) ;如使用归并排序(merge sort) ,第一轮完成后序列为(5) 。3. 用顺序查找法对具有 n 个结点的线性表查找一个结点的时间复杂度为(6) 。4. 实现折半查找的存储结构仅限于(7)存储结构,且其中元素排列必须是 (8) 的。5. 图的 DFS 遍历类似于树的 (9) 遍历,图的 BFS 遍历类似于树的 (10) 遍历。三、请写出用数组实现的循环队列的入队列和出队列的算法。 (20 分)四、请写出快速排序的递归算法。 (15 分)杭 州 师 范 大 学 硕 士 研 究 生 入 学 考 试 命 题 纸2018 年 考试科目代码 825 考试科目名称 计算机基础 (本考试科目共 8 页,第 8 页)