2018年杭州师范大学825计算机基础硕士研究生入学考试试题

杭州师范大学硕士研究生入学考试命题纸
2018 年考试科目代码 825 考试科目名称计算机基础（本考试科目共 7 页，第 1 页）
杭州师范大学
2018 年招收攻读硕士研究生入学考试题
考试科目代码： 825
考试科目名称：计算机基础
说明：考生答题时一律写在答题纸上，否则漏批责任自负。
第一部分：程序设计基础（C 语言）
一、判断题（每小题 2 分，共 20 分）
1、可执行的 C 程序一般应该含有 main 函数，它是 C 程序执行的入口。（）
2、在 C 语言中，标识符是不区分大小写的。（）
3、C 语言的 int 类型数据可以表示任何整数。（）
4、在编译 C 源程序时，计算机根本不会去识别各个变量名的具体含义。但命名规
范对编写 C 程序而言是必要的，可以提高程序可读性和可维护性。（）
5、在 C 语言中，可以给指针变量赋一个整数作为地址值。（）
6、假设有 int a[10]，*p；则 p=&a[0]与 p=a 等价。（）
7、若有：int *p[4]; 则标识符 p 是一个指向有 4 个整型元素的一维数组的指针变
量。（）
8、若有定义：int *p; 使 p 指向类型相同的 3 个连续存储单元的语句是：
p=malloc(3*sizeof(int)); （）
9、用 malloc 函数动态分配的内存是在栈中分配的，而不是在堆中分配的。（）
10、对二维数组 a[3][4]，a+1 与 a[1]都是数组第二行的首地址。（）
二、单项选择题（每小题 2 分，共 40 分）
1、算法是一个计算过程，是程序设计的基础和精髓。一个有效的算法应该具有如
下特点，其中错误的是（）。
A.零个或多个输入及一个或多个输出 B.无穷性
C.可行性 D.确定性
杭州师范大学硕士研究生入学考试命题纸
2018 年考试科目代码 825 考试科目名称计算机基础（本考试科目共 7 页，第 2 页）
2、若有以下语句：
int b; char c[10];
则正确的输入语句是（）。
A. scanf("%d%s", &b, &c); B. scanf("%d%s", &b, c);
C. scanf("%s%s", b, c); D. scanf("%d%s", b, &c);
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' && 'b' B. ax 的值为（）。
A. 1 B. 3 C. 2 D. 4
20、以下叙述中，错误的是（）。
A. 不可以用 FILE 类型定义指向二进制文件的文件指针
B. 在程序结束时，应用 fclose 函数关闭已打开的文件
C. 顺序文件某一时刻，只能处于读或写模式中的一种
D. 利用 fread 函数从二进制文件中读数据时，可用数组名给数组中所有元素读入
数据
杭州师范大学硕士研究生入学考试命题纸
2018 年考试科目代码 825 考试科目名称计算机基础（本考试科目共 7 页，第 4 页）
三、综合应用题（每小题 5 分，共 15 分）
1、以下程序的输出结果是________。
#include
#define N 10
void f(void);
int main(void) {
f();
#ifdef N
#undef N
#endif
return 0;
}
void f(void) {
#if defined(N)
printf("N is %d\n", N);
#else
printf("N is undefined\n");
#endif
}
2、以下程序的输出结果是________。
#include
void swap1(int c[]) {
int t;
t = c[0];
c[0] = c[1];
c[1] = t;
}
void swap2(int c0,int c1) {
int t;
t = c0;
c0 = c1;
c1 = t;
}
int main(void) {
杭州师范大学硕士研究生入学考试命题纸
2018 年考试科目代码 825 考试科目名称计算机基础（本考试科目共 7 页，第 5 页）
int a[2] = {3, 5}, b[2] = {3, 5};
swap1(a);
swap2(b[0], b[1]);
printf("%d#%d#%d#%d\n", a[0], a[1], b[0], b[1]);
return 0;
}
3、以下程序的输出结果是________。
#include
struct node {
int k;
struct node *link;
};
int main(void) {
struct node m[5], *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 < 5; ++i)
printf("%d", m[i].k);
printf("\n");
return 0;
}
杭州师范大学硕士研究生入学考试命题纸
2018 年考试科目代码 825 考试科目名称计算机基础（本考试科目共 7 页，第 6 页）
第二部分：数据结构
一、单项选择题（每小题 2 分，共 20 分）
1.下列程序段的时间复杂度是( )。
for (i = 0;i0; j - -)
printf("%d\n", j);
A. O(n) B. (n
2
) C. O(nlogn) D. O(n
3
)
2.假设一个循环队列 Q[maxSize]的队头指针为 front，队尾指针为 rear，队列的
最大容量为 maxSize，除此之外，该队列再没有其他数据成员，则该队列的队满条
件是( )。
A. front == rear B. front + rear >= maxSize
C. rear == (front + 1) % maxSize D. front == (rear + 1)%maxSize
3. 若元素 1、2、3 依次进栈，允许进栈和出栈操作交替进行，则下列序列中不可
能得到的出栈序列是( )。
A. 1 2 3 B. 3 1 2 C. 1 3 2 D. 3 2 1
4.若用邻接矩阵表示有向图，则其中每一列包含的″1″的个数代表为( )。
A．图中每个顶点的出度 B．图中每个顶点的入度
C．图中弧的条数 D．图中连通分量的数目
5.如果所有关键字都相等，那么插入排序算法的时间复杂度为( )。
A. O(1) B.O(n) C. O(nlogn) D.O(n
2
)
6.下列排序算法中，平均时间复杂度为 O(nlogn)且占用额外空间最多的是
( )。
A. 堆排序 B. 插入排序 C. 归并排序 D. 快速排序
7.若有向图 G=（V, E）含有 7 个顶点，要保证图 G 都是强连通的，则需要的边数
最少是( )。
A. 6 B. 7 C. 12 D. 14
8.若用数组 S[N](S[0…N-1])作为两个栈 S1 和 S2 的共用存储结构，对任何一个栈，
只有当 S 数组全满时才不能入栈操作。为这两个栈分配空间的最佳初始方案是
( )。
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。
杭州师范大学硕士研究生入学考试命题纸
2018 年考试科目代码 825 考试科目名称计算机基础（本考试科目共 7 页，第 7 页）
9. 以下排序方法中，当输入为已排好序的序列时，( )算法时间复杂度最高。
A.选择排序 B.插入排序 C.冒泡排序 D.快速排序
10.下列序列中，( )不是堆(heap).
A. {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, 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 分）