唐·王勃年全国硕士研究生招生考试2025计算机科学与技术学科联考计算机学科专业基础综合试题一、单项选择题：1~40小题，每小题2分，共80分。下列每题给出的四个选项中，只有一个选项符合试题要求。 1.设n是描述问题规模的非负整数，下列程序段的时间复杂度是x=0； A.O(log n)B.O(n1/2)C.O(n)D.O(n2)2.若将一棵树T转化为对应的二又树BT，则下列对BT的遍历中，其遍历序列与T的后根遍历序列相同的是A.先序遍历B.中序遍历C.后序遍历D.按层遍历3.对n个互不相同的符号进行哈夫曼编码。若生成的哈夫曼树共有115个结点，则n的值是A.56 B.57 C.58 D.60 4.在任意一棵非空平衡二又树(AVL树)T1中，删除某结点v之后形成平衡二又树T2，再将w插入T2形成平衡二又树T3。下列关于T1与T3的叙述中，正确的是I.若v是T1的叶结点，则T1与T3可能不相同.若v不是T1的叶结点，则T1与T3一定不相同.若v不是T1的叶结点，则T1与T3一定相同A.仅I B.仅II C.仅I、D.仅I、5.下图所示的AOE网表示一项包含8个活动的工程。活动d的最早开始时间和最迟开始时间分别

单项选择题（本大题有40小题，每小题2分，共80分）1、下列关于操作系统的描述，错误的是：A.操作系统是计算机系统的核心系统软件B.操作系统是用户和计算机之间的接口C.操作系统的主要目标是管理计算机系统的资源D.操作系统具有编译程序的功能答案：D解析：操作系统（Operating System，简称OS）是管理计算机硬件与软件资源的计算机程序，同时也是计算机系统的内核与基石。它负责为用户和其他软件提供一个运行环境，管理计算机的硬件资源，如CPU、内存、磁盘等，并提供用户与计算机硬件之间的接口。编译程序则是将源代码（如C、C++等语言编写的程序）转换成目标代码（如机器语言）的程序，这是编译器的功能，而非操作系统的功能。 解答题（本大题有7小题，每小题10分，共70分）第一题题目：设有一个非空二叉树T，其所有非叶结点的值均为其左、右孩子结点值的平均值。给定T的根结点root的值为x，请设计一个算法计算并返回树T中所有叶结点的值的和。答案：class TreeNode:def _init_(self, val=0, left=None, right=None):self.val = val self.left = left self.right = right def sumOfLeaves(root):if not root:return 0 如果是叶结点，则直接返回该结点的值if not root.left and not root.

全国硕士硕士招生考试计算机科学与技术学科联考计算机学科专业基础综合试题一、单项选择题：1~40小题，每题2分，共80分。下列每题给出四个选项中，只有一种选项符合试题规定。1.设n是描述问题规模非负整数，下列程序段时间复杂度是x=0； A.O(log n)B.O(n1/2)C.O(n)D.O(n2)2.若将一棵树T转化为对应二又树BT，则下列对BT遍历中，其遍历序列与T后根遍历序列相似是A.先序遍历B.中序遍历C.后序遍历D.按层遍历3.对n个互不相似符号进行哈夫曼编码。若生成哈夫曼树共有115个结点，则n值是A.56 B.57 C.58 D.604.在任意一棵非空平衡二又树(AVL树)T1中，删除某结点v之后形成平衡二又树T2，再将w插入T2形成平衡二又树T3。下列有关T1与T3论述中，对是I.若v是T1叶结点，则T1与T3也许不相似.若v不是T1叶结点，则T1与T3一定不相似.若v不是T1叶结点，则T1与T3一定相似A.仅I B.仅II C.仅I、D.仅I、5.下图所示AOE网表达一项包含8个活动工程。活动d最早开始时间和最迟开始时间分别是A.3和7 B.12和12 C.12和14 D.15和156.用有向无环图描述体现式(x+y)*

1.为处理计算机与打印机之间速度不匹配的问题,一般设置一种打印数据缓冲区,主机将要输出的数据依次写入该缓冲区,而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑构造应该是A.栈B.队列C.树D.图2.设栈S和队列Q的初始状态均为空,元素abcdefg依次进入栈S。若每个元素出栈后立即进入队列Q,且7个元素出队的顺序是bdcfeag,则栈S的容量至少是A.1B.2C.3D.43.给定二叉树图所示。设N代表二叉树的根,L代表根结点的左子树,R代表根结点的右子树。若遍历后的结点序列为3,1,7,5,6,2,4,则其遍历方式是1234567A.LRNB.NRLC.RLND.RNL4.下列二叉排序树中,满足平衡二叉树定义的是A.B.C.D.5.已知一棵完全二叉树的第6层(设根为第1层)有8个叶结点,则完全二叉树的结点个数最多是A.39B.52C.111D.1196.将森林转换为相应的二叉树,若在二叉树中,结点u是结点v的父结点的父结点,则在原来的森林中,u和v可能具有的关系是I.父子关系II.弟兄关系III.u的父结点与v的父结点是弟兄关系A.只有IIB.I和IIC.I和IIID.I、II和III7.下列有关无向连通图特征的论述中,正确的