杭 州 师 范 大 学
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.确定性
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. a<=b C. a || b+c && b D. !a && b
5、为避免嵌套if-else语句的二义性，C语言规定：else总是与（ ）组成配对关系。
A. 在其之前未配对的最近的if B. 缩进位置相同的if
C. 在其之前未配对的if D. 同一行上的if
6、在while(x)语句中的x与下面条件表达式等价的是（ ）。
A. x == 0 B. x == 1 C. x != 1 D. x != 0
7、设有以下程序段：
int k=10;
while(k=0) k=k-1;
则下面描述中正确的是（ ）。
A. 循环执行10次 B. 循环是无限循环
C. 循环体语句一次也不执行 D. 循环体语句执行一次
8、以下说法正确的是（ ）。
A. 可以在一个函数中定义另一个函数
B. 构成C程序的基本单位是函数
C. main函数必须放在其他函数之前
D. C程序可以从任何非main函数开始执行
9、在C语言中，以下说法正确的是（ ）。
A. 函数的定义不可以嵌套，但函数的调用可以嵌套
B. 函数的定义和函数的调用均不可以嵌套
C. 函数的定义可以嵌套，但函数的调用不可以嵌套
D. 函数的定义和函数的调用均可以嵌套
10、下面属于正确的宏定义的是（ ）。
A. #define S 24 B. #define S 24;
C. #define S=24 D. #define S=24;
11、若在一个函数中的复合语句中定义了一个变量，则该变量的有效范围是（ ）。
A. 在该函数中有效 B. 在本程序范围内有效
C. 非法变量 D. 在该复合语句中有效
12、若变量已正确定义并且指针p已经指向某个变量x，则(*p)++相当于（ ）。
A. p++ B. &x++ C. *(p++) D. x++
13、设p1和p2是指向同一个int型一维数组的指针变量，k为int型变量，则不能正确执行的语句是（ ）。
A. k=*p1+*p2; B. p2=k; C. p1=p2; D. k=*p1*(*p2);
14、语句：int (*p)(); 的含义是（ ）。
A. p是一个指向一维数组的指针变量
B. p是指针变量，指向一个int类型数据
C. p是一个指向函数的指针，该函数返回一个int类型数据
D. 以上都不对
15、数组定义为 int a[3][2]={1, 2, 3, 4, 5, 6}，数组元素（ ）的值为6。
A. a[3][2] B. a[2][1] C. a[1][2] D. a[2][3]
16、如果定义int a[10], *p=a; 则不与a[5]等价的是（ ）。
A.p + 5 B.p[5] C.*(p + 5) D.*(a + 5)
17、若用数组名作为函数调用的实参，传递给形参的是（ ）。
A. 数组的首地址 B. 数组第一个元素的值
C. 数组中全部元素的值 D. 数组元素的个数
18、若有：char x[] = "China"; 则x所占据的空间为（ ）。
A. 7个字节 B. sizeof(x) C. 4个字节 D. 8个字节
19、已知
struct {
int x; int y;
} s[2] = {{1, 2}, {3, 4}}, *p = s;
则++p->x的值为（ ）。
A. 1 B. 3 C. 2 D. 4
20、以下叙述中，错误的是（ ）。
A. 不可以用FILE类型定义指向二进制文件的文件指针
B. 在程序结束时，应用fclose函数关闭已打开的文件
C. 顺序文件某一时刻，只能处于读或写模式中的一种
D. 利用fread函数从二进制文件中读数据时，可用数组名给数组中所有元素读入数据
三、综合应用题（每小题5分，共15分）
1、以下程序的输出结果是________。
#include <stdio.h>
#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 <stdio.h>
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) {
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 <stdio.h>
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;
}
第二部分：数据结构
一、单项选择题（每小题2分，共20分）
1.下列程序段的时间复杂度是( )。
for (i = 0;i<n; i++)
for (j = n - i; j >0; j - -)
printf("%d\n", j);
A. O(n) B. (n2) C. O(nlogn) D. O(n3)
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(n2)
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。
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分）
