2020年全国硕士研究生入学统一考试计算机科学与技术学科联考(408).docxVIP

2020年全国硕士研究生招生考试

计算机科学与技术学科联考

计算机学科专业基础综合试题

一、单项选择题：1~40小题，每小题2分，共80分。下列每题给出的四个选项中，只有一个选项符合题意要求。

1.将一个10*10对称矩阵M的上三角部分的元素素mij(1≤i≤j≤10)按列优先存入C语言的一维数组N中，元素m7,2在N中的下标是：

A、15B、16C、22D、23

2.对空栈S进行Push与Pop操作，入栈序列a,b,c,d,e经过Push，Push，Pop，Push，Pop，Push，Push，Pop操作后得到的出栈序列是

A、b,a,cB、b,a,eC、b,c,aD、b,c,e

3.对于任意一棵高度为5且有10个节点的二叉树，若采用顺序存储结构保存，每个结点占1个存储单元(仅存放结点的数据信息)，则存放该二叉树需要的存储单元数量至少是：

A、31B、16C、15D、10

4.已知森林F及与之对应的二叉树T，若F的先根遍历序列是a,b,c,d,e,f，中根遍历序列是b,a,d,f,e,c则T的后根遍历序列是：

A、b,a,d,f,e,cB、b,d,f,e,c,aC、b,f,e,d,c,aD、f,e,d,c,b,a

5.下列给定的关键字输入序列中，不能生成如下二叉排序树的是：

A、4，5，2，1，3

B、4，5，1，2，3

C、4，2，5，3，1

D、4，2，1，3，5

6.修改递归方式实现的图的深度优先有哪些信誉好的足球投注网站(DFS)算法，将输出(访问)定点信息的语句移到退出递归前(即执行输出语句后立刻退出递归)。采用修改后的算法遍历有向无环图G，若输出结果中包含G中的全部顶点，则输出的顶点序列是G的：

A、拓扑有序序列

C、广度优先有哪些信誉好的足球投注网站序列

B、逆拓扑有序序列

D、深度优先有哪些信誉好的足球投注网站序列

7.已知无向图G如下所示，使用克鲁斯卡尔(K『uskal)算法求图G的最小生成树，加入到最小生成树中的边依次是：

A、(b,f)(b,d)(a,e)(c,e)(b,e)B、(b刀(b,d)(b,e)(a,e)(e,c)

(不确定最后一个括号的内容)C、(a,e)(b,e)(c,e)(b,d)(b乃

D、(a,e)(c,e)(b,e)(b,f)(b,d)

8.若使用AOE网估算工程进度，则下列叙述中正确的是：

A、关键路径是从原点到汇点边数最多的一条路径

B、关键路径是从原点到汇点路径长度最长的路径

C、增加任一关键活动的时间不会延长工程的工期

D、缩短任一关键活动的时间将会缩短工程的工期

9.下列关于大根堆(至少含2个元素)的叙述中正确的是：

I．可以将堆看成一棵完全二叉树

II．可采用顺序存储方式保存堆；

III．可以将堆看成一棵二叉排序树；

IV．堆中的次大值一定在根的下一层。

A、I,IIB、I,II,IVC、II,IIID、II,III,IV

10.依次将关键字5，6，9，13，8，2，12，15插入初始为空的4阶B树后，根节点中包含的关键字是：

A、8B、6,9C、8,13D、9,12

11.对大部分元素已有序的数组进行排序时，直接插入排序比简单选择排序效率更高，其原因是：

I、直接插入排序过程中元素之间的比较次数更少

II、直接插入排序过程中所需要的辅助空间更少

III、直接插入排序过程中元素的移动次数更少

A、IB、IIIC、I,IID、I,II,III

12.下列给出的部件中其位数(宽度)一定与机器字长相同的是：

I、ALU；