2018年杭州师范大学考研专业课试题825计算机基础.doc

1、杭 州 师 范 大 学 硕 士 研 究 生 入 学 考 试 命 题 纸杭 州 师 范 大 学 2018 年招收攻读硕士研究生入学考试题 考试科目代码： 825 考试科目名称： 计算机基础 说明：考生答题时一律写在答题纸上，否则漏批责任自负。第一部分：程序设计基础（C语言）一、判断题（每小题2分，共20分）1、可执行的C程序一般应该含有main函数，它是C程序执行的入口。（ ）2、在C语言中，标识符是不区分大小写的。（ ）3、C语言的int类型数据可以表示任何整数。（ ）4、在编译C源程序时，计算机根本不会去识别各个变量名的具体含义。但命名规范对编写C程序而言是必要的，可以提高程序可读性和可维护

2、性。（ ）5、在C语言中，可以给指针变量赋一个整数作为地址值。（ ）6、假设有int a10，*p；则p=&a0与p=a等价。（ ）7、若有：int *p4; 则标识符p是一个指向有4个整型元素的一维数组的指针变量。（ ）8、若有定义：int *p; 使p指向类型相同的3个连续存储单元的语句是：p=malloc(3*sizeof(int); （ ）9、用malloc函数动态分配的内存是在栈中分配的，而不是在堆中分配的。（ ）10、对二维数组a34，a+1与a1都是数组第二行的首地址。（ ）二、单项选择题（每小题2分，共40分）1、算法是一个计算过程，是程序设计的基础和精髓。一个有效的算法应该具

3、有如下特点，其中错误的是（ ）。A.零个或多个输入及一个或多个输出 B.无穷性C.可行性 D.确定性2、若有以下语句：int b; char c10;则正确的输入语句是（ ）。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; 则以下表达

4、式中值为0的是（ ）。A. a & b B. ax的值为（ ）。A. 1 B. 3 C. 2 D. 420、以下叙述中，错误的是（ ）。A. 不可以用FILE类型定义指向二进制文件的文件指针B. 在程序结束时，应用fclose函数关闭已打开的文件C. 顺序文件某一时刻，只能处于读或写模式中的一种D. 利用fread函数从二进制文件中读数据时，可用数组名给数组中所有元素读入数据三、综合应用题（每小题5分，共15分）1、以下程序的输出结果是_。#include #define N 10void f(void);int main(void) f();#ifdef N#undef N#endifret

5、urn 0;void f(void) #if defined(N)printf(N is %dn, N);#elseprintf(N is undefinedn);#endif2、以下程序的输出结果是_。#include voidswap1(intc) intt;t = c0;c0 = c1;c1 = t;voidswap2(intc0,intc1) intt;t = c0;c0 = c1;c1 = t;intmain(void) inta2 = 3, 5, b2 = 3, 5;swap1(a);swap2(b0, b1);printf(%d#%d#%d#%dn, a0, a1, b0, b1

6、);return0;3、以下程序的输出结果是_。#include struct node int k; structnode *link;int main(void) structnodem5, *p = m, *q = m + 4; inti = 0;while(p != q)p-k = +i;p+;q-k = i+;q-; q-k = i; for(i = 0; i 5; +i) printf(%d, mi.k); printf(n);return 0;第二部分：数据结构一、单项选择题（每小题2分，共20分）1.下列程序段的时间复杂度是( )。for (i = 0;i0; j - -)pr

7、intf(%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

8、. 3 1 2 C. 1 3 2D. 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. 1

9、48.若用数组SN(S0N-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,

10、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将其进行升序排列,如使用快速

11、排序（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 页）