2019考研计算机真题详解：算法与数据结构、网络应用模型

"2019年全国硕士研究生入学统一考试计算机学科专业基础综合真题" 这篇文档是2019年全国硕士研究生入学统一考试的计算机学科专业基础综合真题，涵盖了多项选择题和综合应用题。考试的总分为150分，考生有180分钟的时间答题。下面是对部分试题及其相关知识点的详细说明： 1. 时间复杂度分析题：题目考察的是算法的时间复杂度。给定的程序段是一个循环结构，x的初始值为0，循环条件是n >= (x+1)*(x+1)，每次循环x递增1。显然，当x为√n时，循环停止，因此该程序段的时间复杂度为O(√n)。正确答案是B. O(n^0.5)。 2. 树的遍历：题目涉及到二叉树和树的遍历方法。后根遍历是指先遍历子树，最后访问根节点，而在二叉树中，后序遍历的顺序与原树的后根遍历相同。所以，正确答案是C. 后序遍历。 3. 哈夫曼编码与哈夫曼树：题目提到哈夫曼树有115个节点，而生成哈夫曼树的n个互不相同的符号表示的叶子节点数为n，其余115-n个节点是内部节点。根据哈夫曼树的特性，内部节点数等于叶子节点数减1，即115-n = n - 1，解得n = 58。所以，正确答案是C. 58。 4. TCP三次握手：TCP连接的建立需要三次握手，第三次握手时，主机乙会发送一个确认序列号，这个确认序列号是前一次接收到的序列号加1，即甲的初始序列号2018加1，因此答案是D. 2047。 5. 网络应用模型：题目讨论了P2P（对等网络）和C/S（客户/服务器）模型。在C/S模型中，客户机主动发起请求，服务器被动响应；P2P中所有节点对等，没有固定的角色划分。错误的选项是B，因为C/S模型中，客户与客户之间通常不能直接通信。正确答案是B. 6. 综合应用题：题目要求对线性表L进行重新排列，得到一个新的链表，新链表的元素顺序是原链表的元素交错排列。为达到O(1)的空间复杂度，不能使用额外的数据结构。解决此问题的基本设计思想是首先找到链表的中点，然后逆置后半部分链表，最后通过两个指针从头和尾开始交错合并链表。这样可以保证在不使用额外空间的情况下，仅遍历链表一次完成任务。 以上就是从提供的文件信息中提炼出的计算机科学相关知识点，包括算法复杂度、数据结构（树和链表）、网络协议（TCP连接）以及数据压缩（哈夫曼编码）。这些知识点是计算机科学基础的重要组成部分，对于备考研究生入学考试的考生来说，理解和掌握这些概念至关重要。