华中科技大学834计算机专业基础综合复习试题：排序、数据结构与网络知识

"2018年华中科技大学834计算机专业基础综合复习八套卷一（版）" 在计算机科学中，起泡排序是一种简单的排序算法，它的主要思想是通过重复遍历待排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。起泡排序的结束条件是当一轮遍历下来没有发生任何交换，这表明数列已经排序完成。在描述中的问题（1）中，考生需要理解这个关键点来确定排序是否结束。 希尔排序，由Donald Shell于1959年提出，是插入排序的一种更高效的改进版本。它通过将待排序的序列分割成若干个子序列，然后对子序列进行插入排序，逐步减少子序列的间隔，直到间隔为1，整个序列就是一个有序序列。问题（2）要求考生概述希尔排序的基本思想，即通过增量序列缩小序列的间隔，使得元素能在更大的范围内进行有效的排序。 在问题（3）中，考生需要将给定的序列调整为一个最小堆，最小堆是一种特殊的树形数据结构，每个父节点的值都小于或等于其子节点的值。对于给出的序列112 70 33 65 24 56 48 92 80 13，调整为最小堆的过程涉及反复比较并交换元素以满足堆性质，最终形成的堆顶元素将是序列中的最小值。 问题（4）涉及到选择排序算法，找到最小关键字需要遍历整个序列一次，所以至少需要比较15次。而找出次小的关键字，可以在找到最小值后，仅需要比较剩下的15个元素，因此至少需要比较14次。选择方法是每次比较当前元素与已知最小值，若更小则更新最小值。 4. OSI（开放系统互连）参考模型和TCP/IP参考模型都是用于描述网络通信的层次结构。OSI模型有七层，自下而上分别是物理层、数据链路层、网络层、传输层、会话层、表示层和应用层。TCP/IP模型则简化为四层，包括网络接口层、网际层、传输层和应用层。两者的主要相同点是都有类似的分层结构，负责处理不同层面的通信问题；不同点在于OSI模型更为详尽，而TCP/IP模型更注重实用性，较少的层次使其更适合互联网的实际应用。 在试卷的填空题部分，涉及了计算机科学的基础概念，如顺序表的插入操作、栈的定义及其操作特性、后缀表达式、矩阵存储优化、哈希函数的设计、IP地址分类、网络速率单位以及TCP/IP协议的分层等。 判断题部分则检验了考生对数据结构、算法效率、网络协议、操作系统以及信息传输等多个方面的理解，如顺序存储的优缺点、数据的物理结构、栈和队列的实现方式、数组与二叉树的关系、B-树的平衡因子、有序表与无序表的查找效率、OSI模型的层次、TCP段头的窗口大小、带宽与吞吐量的单位以及IPv4地址的子网掩码含义。 选择题中包含的算法复杂度分析、存储结构设计以及程序执行效率等题目，旨在测试考生对基础算法和数据结构的掌握程度，以及对计算机系统运行原理的理解。 这些题目覆盖了计算机科学多个核心领域，对于准备计算机考研的学生来说，是全面检验和提升知识水平的重要练习。