《计算机科学基础实验》课件

计算机科学基础实验欢迎参加计算机科学基础实验课程本课程旨在通过实践操作，帮助学生掌握计算机科学的核心概念和技能我们将从基础知识开始，逐步深入到高级主题，涵盖硬件、软件、数据结构、算法、数据库、网络以及人工智能等领域通过亲手实践，你将获得真实世界中解决问题的能力，并为未来的专业发展奠定坚实基础让我们一起踏上这段充满挑战与收获的学习之旅！课程目标和学习成果掌握计算机基础知识培养实践编程能力12通过本课程，学生将能够理解计算机系统的基本工作原理，掌握学生将通过大量编程实验，熟练掌握至少一门编程语言的使用，硬件组成部分以及操作系统的核心概念，为后续学习打下坚实基能够独立设计、编写和调试简单程序，解决实际问题础构建系统思维方式增强团队协作能力34培养学生分析问题、设计解决方案的系统思维能力，建立算法思通过小组实验项目，学生将学习团队协作的方法，提高沟通表达想和数据结构概念，提高逻辑推理能力和创新思维能力，为将来进入职场做好准备实验环境介绍硬件设备软件环境网络设施我们的实验室配备了最新的计算机设备实验室电脑预装了多种操作系统，包括实验室内有高速Wi-Fi和有线网络连接，每台机器都有足够的处理能力来支持Windows、Linux和macOS，方便学生，支持学生进行网络实验和资源下载本课程的所有实验硬件配置包括高性体验不同平台此外，我们还安装了各我们还设置了专用服务器，供数据库和能处理器、充足的内存和大容量存储设种编程工具、IDE、编译器和数据库系网络编程实验使用，确保稳定的实验环备，确保实验过程流畅统，为各类实验提供支持境实验安全须知电气安全网络安全数据安全使用实验设备时请确保双手干严禁在实验室内进行任何非法妥善保管个人账户和密码，实燥，禁止带饮料靠近电脑设备网络活动，包括攻击、扫描或验结束后务必退出所有账号发现设备冒烟、异响或异味下载盗版软件网络安全实验重要实验数据请及时备份，避时，请立即切断电源并报告实必须在指定的隔离环境中进行免因系统故障导致数据丢失验室管理员切勿擅自拆卸电，不得影响校园网络的正常运不要在公共电脑上存储个人敏脑硬件或更换电源线路行感信息应急措施熟悉实验室内灭火器和应急出口的位置发生火灾等紧急情况时，请保持冷静，按照指定路线有序撤离实验过程中如遇任何安全问题，立即通知实验指导教师实验报告撰写指南实验目的清晰简洁地陈述本次实验要达成的目标，表明你对实验意义的理解这部分应当与实验指导书中的目标相呼应，但可以用自己的话重新表述实验原理概述实验的理论基础，包括相关的概念、公式或算法这部分应当展示你对实验背后的科学原理的掌握程度，必要时可以引用课本或其他权威资料实验步骤详细记录实验的操作过程，包括环境配置、代码实现、参数设置等关键步骤这部分应当足够详细，使他人能够按照你的记录重复实验过程实验结果客观呈现实验数据和观察结果，可使用表格、图表等方式组织数据对于程序输出，应当截图或复制完整的运行结果，并标注关键输出分析讨论这是实验报告的核心部分，应当对实验结果进行深入分析，解释现象背后的原因，讨论与理论预期的异同，以及可能的改进方向这部分体现了你的思考能力和对知识的融会贯通第一部分计算机基础知识计算机发展历史1从机械计算机到电子计算机的演变计算机系统组成2硬件、软件和数据的关系计算思维导论3问题分解与算法思想信息表示基础4二进制与数据编码计算机基础知识是我们学习旅程的起点在这一部分中，我们将探索计算机的核心概念和基本工作原理，理解数字世界的基础构建块通过掌握这些基础知识，你将能够更深入地理解后续章节中的高级概念我们将从计算机的历史演变开始，了解计算机系统的组成部分，培养计算思维方式，并学习计算机如何表示和处理信息这些知识将为你未来的计算机科学学习之旅打下坚实基础计算机硬件组成中央处理器内存主板存储设备CPU RAMCPU是计算机的大脑，负责内存是临时存储数据和程序主板是连接计算机各个部件硬盘驱动器HDD和固态驱动执行指令和处理数据它包的地方，特点是访问速度快的核心电路板，它提供了各器SSD是常见的长期存储设含控制单元、算术逻辑单元但断电后数据会丢失它与种接口和总线，使CPU、内备，用于保存操作系统、应和寄存器等组件当代CPU CPU直接交互，存储当前正存、存储设备和其他外设能用程序和用户数据与内存通常采用多核设计，能够并在执行的程序和处理中的数够相互通信主板上的芯片不同，这些设备在断电后仍行处理多个任务，大幅提高据，是影响系统性能的关键组控制着数据的流动和系统能保留数据，但访问速度相系统性能组件之一资源的分配对较慢操作系统基础应用程序1用户直接交互的软件系统调用接口2连接应用与内核的桥梁操作系统内核3管理硬件资源和提供基础服务硬件抽象层4屏蔽硬件差异的接口层计算机硬件5提供基础计算和存储能力操作系统是计算机中最基础的系统软件，它管理计算机硬件和软件资源，为用户程序提供通用服务常见的操作系统包括Windows、macOS、Linux和Android等每个操作系统都有其独特的特点和适用场景操作系统的主要功能包括进程管理、内存管理、文件系统管理、设备驱动管理和用户接口提供通过这些功能，操作系统实现了资源的高效分配和管理，使用户能够方便地使用计算机系统在接下来的实验中，我们将逐步探索操作系统的核心概念和工作原理文件系统操作实验文件创建与编辑学习使用文本编辑器创建和修改文件，掌握基本文件操作实验中将使用多种编辑工具，包括记事本、vim和nano等，体验不同平台下的编辑方式文件权限管理了解Linux系统中的文件权限概念，学习使用chmod和chown命令修改文件的访问权限和所有者通过实例理解读、写、执行权限的含义及其对系统安全的重要性文件搜索与过滤掌握使用find、grep等命令在文件系统中搜索特定文件或内容的方法学习正则表达式的基本语法，提高文本处理和信息检索的效率文件压缩与归档学习常见的文件压缩工具如zip、tar等的使用方法，理解不同压缩算法的特点通过实践掌握大文件的备份、传输和存储技巧命令行界面使用基本命令掌握1学习常用命令如cd（切换目录）、ls/dir（列出文件）、mkdir（创建目录）、rm/del（删除文件）等这些命令是命令行操作的基础，掌握它们将使你能够高效地在文件系统中导航和执行基本操作管道与重定向2了解输入输出重定向（、、）和管道（|）的概念和使用方法这些技术允许你将一个命令的输出作为另一个命令的输入，或将结果保存到文件中，大大提高工作效率环境变量配置3学习查看和设置环境变量的方法，理解环境变量对程序运行的影响通过修改PATH等环境变量，可以自定义命令行环境，使其更适合个人工作习惯脚本编写基础4掌握简单shell脚本或批处理文件的编写方法，实现命令自动化脚本可以将一系列命令组合成一个可执行文件，大大简化重复性工作，提高操作效率第二部分程序设计基础算法设计问题分析2设计解决问题的步骤和方法1理解问题需求和约束条件代码实现3将算法转化为具体的程序代码5优化改进测试调试提高程序性能和代码质量4检查程序正确性并修复错误程序设计是计算机科学的核心内容，通过学习编程语言和设计方法，我们能够将抽象问题转化为计算机可执行的指令序列在这一部分中，我们将系统学习程序设计的基本概念、思想方法和实践技巧我们将从编程语言的基础语法开始，逐步学习变量、数据类型、控制结构、函数、数组、指针等概念，并通过大量的实验练习培养编程能力和解决问题的思维方式这些知识和技能是后续学习高级编程概念和专业课程的基础编程语言概述编程语言是人与计算机交流的媒介，它允许我们用结构化的方式描述计算机应该执行的操作不同的编程语言设计用于不同的应用场景，各有其特点和优势例如，C语言以其高效和对硬件的控制而著名；Python以简洁易读的语法和丰富的库受到欢迎；Java以其跨平台性和面向对象特性广泛应用编程语言通常分为编译型语言（如C、C++）和解释型语言（如Python、JavaScript）编译型语言需要先将源代码转换为机器码，然后执行；解释型语言则是边解释边执行在本课程中，我们将主要使用C语言作为学习的工具，因为它能够帮助我们更好地理解计算机的工作原理语言基础语法C数据类型示例声明占用内存值范围int inta=10;通常4字节-2147483648~2147483647float floatb=

3.14f;4字节

1.2E-38~

3.4E+38char charc=A;1字节-128~127double doubled=

3.14159;8字节

2.3E-308~

1.7E+308C语言是一种广泛使用的编程语言，以其高效性和对硬件的控制能力而著名C语言的程序结构包括头文件引入、全局变量声明、函数定义等部分一个标准的C程序必须包含main函数，它是程序的入口点C语言的基本语法元素包括标识符、关键字、数据类型、运算符和表达式标识符用于命名变量、函数和数组等；关键字如if、else、while是语言预定义的词汇；数据类型决定变量可以存储的数据种类；运算符用于执行特定操作；表达式则是由变量、常量和运算符组合而成变量和数据类型实验变量声明与初始化学习如何声明不同类型的变量并为其赋初值理解变量命名规则和最佳实践，掌握全局变量与局部变量的区别及其作用域数据类型转换探索隐式和显式类型转换，了解不同数据类型之间转换的规则和可能出现的精度损失学习如何安全地进行类型转换，避免常见错误运算符和表达式实践各种算术、关系、逻辑和位运算符的使用，学习表达式求值的优先级规则通过编写表达式计算程序，巩固对运算符的理解常量定义与使用掌握使用#define和const定义常量的方法，理解两种方式的区别及适用场景通过实例学习如何合理使用常量提高程序的可读性和可维护性控制结构实验条件语句循环语句学习if-else和switch-case语句的使用，通过实例理解条件判断和多分掌握for、while和do-while循环的语法和使用场景，了解循环控制关键支选择的实现方法实验中将编写程序解决实际问题，如成绩分级、简字break和continue的作用通过编写求和、查找、排序等算法，深入单菜单系统等，锻炼逻辑思维能力理解循环结构的工作原理嵌套控制结构控制流优化学习如何在一个控制结构内部使用另一个控制结构，如嵌套循环、循环探索优化控制流程的技巧，如减少嵌套层数、合并条件表达式、简化循中的条件判断等通过解决复杂问题（如打印图案、多层菜单）理解嵌环结构等学习如何提高程序的可读性和效率，避免常见的控制结构设套结构的设计方法计错误函数和模块化编程参数传递机制函数调用与递归理解值传递和引用传递（通过指探索函数调用的过程和堆栈的使针）的区别，掌握如何选择合适用，了解递归函数的工作原理模块化程序设计的参数传递方式实验不同传递通过经典问题（如阶乘计算、斐函数定义与声明方式对原始数据的影响，加深对波那契数列）实践递归设计，分学习如何将程序划分为多个功能内存模型的理解析其优缺点学习C语言中函数的定义语法和模块，使用多文件编程和头文件函数原型声明的重要性掌握返组织代码掌握使用静态函数限回类型、参数列表和函数体的编制访问范围，提高代码的安全性写规则，理解函数签名的概念和可维护性2314数组和字符串操作一维数组基础多维数组应用字符串处理函数学习一维数组的声明、初始化掌握二维及多维数组的定义和学习C语言中字符串的表示方和访问方法，理解数组索引和使用技巧，了解多维数组在内式和常用处理函数，如strlen内存分配模型通过实验掌握存中的存储布局通过矩阵运、strcpy、strcat、strcmp等常见数组操作，如遍历、搜索算、图像处理等实例，理解多实践字符串的输入输出、拼、排序等，培养使用数组解决维数组在科学计算中的重要作接、比较、查找和替换等操作问题的能力用，提高文本处理能力字符串算法实现尝试自行实现一些字符串处理算法，如单词统计、回文检测、模式匹配等通过编码过程理解字符串算法的设计思想和实现技巧，培养算法思维指针概念及应用指针基础概念指针与数组指针与函数指针是一种存储内存地址的变量，它允数组名本质上是指向数组第一个元素的指针作为函数参数可以实现参数的引用许程序间接访问和操作数据在C语言指针，这一特性使得指针算术运算可以传递，允许函数修改调用者的变量函中，指针是一个强大而灵活的特性，但用于数组遍历通过实验对比基于索引数指针则允许将函数作为参数传递或返也是初学者常感困惑的概念理解指针和基于指针的数组访问方式，理解两者回，实现回调机制和动态行为通过设需要先掌握变量在内存中的存储模型，的等价性和性能差异学习指针数组和计使用函数指针的排序算法，体验函数以及地址操作符和解引用操作符*的使数组指针的区别，掌握二维数组的指针式编程的思想用表示结构体和联合体结构体定义与声明结构体是C语言中用户自定义的复合数据类型，可以将不同类型的数据组合在一起本实验将学习结构体的定义语法、变量声明方式，以及如何使用点运算符访问结构体成员结构体数组与指针掌握结构体数组的创建和操作方法，学习结构体指针的声明和使用技巧理解结构体指针如何使用箭头运算符（-）访问成员，以及结构体在函数间传递的最佳实践嵌套结构体设计学习在一个结构体内部包含另一个结构体的方法，理解嵌套结构体的内存布局和访问规则通过实现简单的数据结构（如链表节点）来掌握嵌套结构的设计思想联合体应用场景了解联合体的概念和与结构体的区别，学习如何利用联合体在相同内存位置存储不同类型的数据通过实例探索联合体在内存优化、数据转换等场景中的应用文件操作实验文件打开与关闭文件读取技术文件写入操作文件定位与随机访问学习使用fopen和fclose函数打掌握字符级（fgetc）、行级（学习使用fprintf、fputs、fwrite等理解文件指针位置的概念，学习使开和关闭文件，掌握不同文件模式fgets）和块级（fread）文件读取函数向文件写入数据，理解格式化用fseek、ftell和rewind函数控制（读、写、追加等）的含义和应用函数的使用方法，了解它们的效率输出和二进制写入的区别通过实文件读写位置通过实现简单的数场景理解文件指针的概念和重要差异和适用情况实践文件内容的例掌握文件内容的生成、更新和备据库操作，体验随机访问文件的优性，学会处理文件操作可能出现的解析和处理，如统计字符频率、提份技术，培养数据持久化能力势和应用方法错误取特定信息等第三部分数据结构实验复杂数据结构1树、图、哈希表基本数据结构2栈、队列、字典线性数据结构3数组、链表数据组织方式4数据的存储和检索基本概念5抽象数据类型数据结构是计算机科学中研究数据组织方式的学科，它关注如何高效地存储、访问和处理数据良好的数据结构设计对于算法效率至关重要，直接影响程序的性能和资源利用率在本部分实验中，我们将从线性表开始，逐步学习栈、队列、树和图等数据结构的概念和实现方法通过亲手构建这些数据结构并解决实际问题，你将深入理解它们的工作原理、优缺点和适用场景，为后续的算法设计和软件开发打下坚实基础线性表概述线性表的定义与特性1线性表是具有相同数据类型的n个数据元素的有限序列它的特点是除了第一个和最后一个元素外，每个元素都有且仅有一个前驱和一个后继线性表是最基本也是最常用的数据结构之一，是许多复杂数据结构的基础线性表的基本操作2线性表支持多种基本操作，包括初始化、插入、删除、查找、更新等这些操作的实现方式取决于线性表的具体存储结构，但操作的逻辑语义保持一致，体现了数据结构的抽象性线性表的存储结构3线性表有两种基本的存储结构顺序存储结构（顺序表）和链式存储结构（链表）顺序表使用连续的内存空间存储元素，适合随机访问；链表使用指针连接分散的节点，适合动态操作线性表的应用场景4线性表在计算机科学和软件开发中有广泛应用，如编译器的符号表、操作系统的进程管理、数据库的记录组织等理解线性表的实现和操作，是掌握更复杂数据结构的基础顺序表实现与操作顺序表是线性表的一种实现方式，它使用连续的内存空间存储元素顺序表的优点是支持高效的随机访问（时间复杂度为O1），缺点是插入和删除操作需要移动大量元素在本实验中，我们将使用数组实现顺序表，并实现其基本操作实验内容包括顺序表的初始化、销毁、长度计算、元素获取、元素查找、元素插入和元素删除等操作通过实现这些操作，学生将理解顺序表的工作原理和性能特点，掌握使用数组模拟动态结构的技术，为理解更复杂的数据结构奠定基础链表实现与操作单向链表双向链表循环链表单向链表中的每个节点包含数据域和指双向链表的节点除了有指向下一个节点循环链表是首尾相连的链表，最后一个向下一个节点的指针它只能从头到尾的指针外，还有指向前一个节点的指针节点的指针指向第一个节点这种结构遍历，不支持反向查找单向链表实现这使得双向链表可以向前或向后遍历使得从任何节点出发都能遍历整个链表简单，内存消耗较少，适用于只需要单，便于实现某些特定操作，但代价是增，适用于需要循环处理数据的场景，如向遍历的场景加了内存消耗和结构复杂性操作系统的资源分配栈的概念及实现栈的基本概念栈是一种遵循后进先出LIFO原则的线性数据结构它只允许在一端（栈顶）进行插入和删除操作，这一特性使得栈适用于需要记住最近信息的场景，如函数调用、表达式求值和语法分析等栈的顺序存储实现使用数组实现栈是最简单的方法，我们需要一个数组存储栈元素，以及一个变量记录栈顶位置栈的基本操作包括初始化、判断栈空/栈满、入栈、出栈和获取栈顶元素等，这些操作的实现都非常高效（时间复杂度为O1）栈的链式存储实现使用链表实现栈可以避免顺序栈的容量限制，链栈通常以单链表形式实现，将链表的头部作为栈顶，这样入栈和出栈操作都可以在链表头部高效完成链栈的优点是空间动态分配，不存在栈满的情况栈的应用实例通过实现表达式求值、括号匹配检查、迷宫求解等经典问题，体验栈在解决实际问题中的应用这些实例将帮助学生理解栈的工作原理和思维方式，培养使用数据结构解决问题的能力队列的概念及实现顺序队列实现队列的基本概念2基于数组的队列存储方式1先进先出的线性数据结构循环队列优化3解决假溢出问题的技术5队列应用实例链式队列实现解决实际问题的队列应用4基于链表的队列存储结构队列是一种遵循先进先出FIFO原则的线性数据结构，它只允许在一端（队尾）插入元素，在另一端（队头）删除元素队列广泛应用于操作系统的进程调度、网络数据包处理、广度优先搜索等场景在本实验中，我们将实现顺序队列、循环队列和链式队列，理解它们的工作原理和性能特点循环队列通过将队列视为首尾相连的环形结构，有效解决了顺序队列的假溢出问题；链式队列则通过链表实现，具有更灵活的内存利用方式学生将通过编程实践，掌握队列的各种操作和应用技巧递归算法实验递归的基本概念1函数直接或间接调用自身递归与迭代对比2两种解决问题方式的异同递归终止条件3防止无限递归的边界情况递归的内存模型4栈帧的创建和销毁过程递归是一种重要的算法设计方法，通过函数调用自身来解决问题，通常可以使复杂问题的解决方案变得简洁优雅递归算法通常由两部分组成基本情况（终止条件）和递归情况良好的递归设计需要确保每次递归都能向基本情况靠近，避免无限递归导致栈溢出在本实验中，我们将实现经典的递归算法，如阶乘计算、斐波那契数列、汉诺塔问题和二分查找等通过这些实例，学生将理解递归的工作原理、递归与栈的关系、以及递归优化技术（如尾递归和记忆化搜索）这些知识对于后续学习高级算法和数据结构至关重要树结构概述二叉树二叉搜索树平衡树堆多叉树其他树是一种非线性数据结构，由节点和连接节点的边组成，具有层次关系与线性结构不同，树结构可以表示一对多的关系，因此在表示具有层次特性的数据时非常有用树结构的基本术语包括根节点、父节点、子节点、叶节点、节点的度、树的高度等不同类型的树结构有不同的特点和应用场景二叉树每个节点最多有两个子节点，是最常用的树结构；二叉搜索树具有良好的查找性能；平衡树（如AVL树、红黑树）通过保持平衡提高操作效率；堆是一种特殊的完全二叉树，常用于优先队列实现了解这些树结构的特性和实现方法，对于解决实际问题至关重要二叉树的实现与遍历二叉树的基本实现前序遍历中序遍历后序遍历二叉树通常使用链式结构实前序遍历的访问顺序是根中序遍历的访问顺序是左后序遍历的访问顺序是左现，每个节点包含数据域、节点-左子树-右子树子树-根节点-右子树子树-右子树-根节点左子节点指针和右子节点指这种遍历方式先访问当前节对于二叉搜索树，中序遍历这种方式适合需要先处理子针在本实验中，我们将实点，然后递归遍历左右子树可以得到有序的节点序列，节点再处理父节点的场景，现二叉树的基本操作，包括，适用于需要优先处理父节这一特性在很多应用中非常如释放树的内存或计算目录创建二叉树、插入节点、删点的场景，如复制树结构或有用我们将实现递归和非大小后序遍历的非递归实除节点和查找节点等，这些输出目录结构实验中将同递归的中序遍历算法，并讨现较为复杂，是理解树操作操作是理解树结构的基础时实现递归和非递归（使用论其适用场景的好练习栈）两种方式图的表示与遍历邻接矩阵表示邻接表表示广度优先搜索深度优先搜索邻接矩阵使用二维数组表示邻接表为每个顶点维护一个BFS从指定起点开始，先访问DFS尽可能深地搜索图的分支图中顶点之间的连接关系，链表，存储与该顶点相连的所有距离为1的顶点，再访问，直到无法继续前进时回溯适合表示稠密图它的优点所有顶点，适合表示稀疏图距离为2的顶点，依此类推它可以使用递归或栈实现是实现简单，可以快速判断它的优点是空间效率高，它使用队列存储待访问的顶，适合探索迷宫、拓扑排序两个顶点是否相连；缺点是便于遍历顶点的所有邻居；点，适合寻找最短路径或在等场景在实验中，我们将空间复杂度高（On²），不缺点是判断两点是否相连较层次性搜索中使用我们将比较DFS和BFS的特点，并讨适合表示大规模稀疏图慢，需要遍历链表实现BFS并应用于解决实际问论它们的应用场景题第四部分算法设计与分析算法概念基础理解算法的定义、特性和表示方法，掌握算法分析的基本方法和度量标准学习如何从时间和空间两个维度评估算法的效率，为设计高效算法打下基础常见算法设计策略学习分治、贪心、动态规划等经典算法设计思想，了解它们的适用场景和局限性通过解决典型问题，培养算法设计的思维方式和解决复杂问题的能力排序与查找算法深入了解常见的排序算法（如冒泡排序、快速排序、归并排序等）和查找算法（如顺序查找、二分查找、哈希查找等），分析它们的时间复杂度和空间复杂度，学习如何根据实际需求选择合适的算法高级算法专题探索图算法、字符串算法、数值计算算法等专业领域的算法，拓展算法知识面通过实现这些算法解决实际问题，提高编程能力和算法应用能力算法复杂度分析输入规模n O1Olog nOn On log nOn²算法复杂度分析是评估算法效率的重要方法，它关注算法执行时间和内存消耗随输入规模增长的变化趋势时间复杂度通常用大O符号表示，如O1表示常数时间、On表示线性时间、On²表示平方时间等空间复杂度则描述算法所需额外空间的增长率在本实验中，我们将学习如何分析算法的时间复杂度和空间复杂度，理解不同复杂度级别的实际意义通过比较不同算法解决同一问题的效率，体验算法设计的重要性我们还将探讨最佳情况、平均情况和最坏情况分析，以及渐近分析的局限性，培养全面评估算法性能的能力排序算法实验（上）冒泡排序选择排序1Bubble Sort2Selection Sort冒泡排序是一种简单的比较排序算法，它重复地遍历要排序的数列，一选择排序也是一种简单直观的排序算法，它的工作原理是每次从未排序次比较两个元素，如果顺序错误就交换它们其时间复杂度为On²，部分找出最小（或最大）元素，放到已排序部分的末尾选择排序的时虽然效率不高，但实现简单，适合小规模数据排序和教学使用间复杂度同样是On²，但交换操作的次数少于冒泡排序插入排序希尔排序3Insertion Sort4Shell Sort插入排序通过构建有序序列，对于未排序数据，在已排序序列中从后向希尔排序是插入排序的一种改进版本，它通过比较相距一定间隔的元素前扫描，找到相应位置并插入它的时间复杂度是On²，但对于接近来工作，随着算法的进行，间隔会逐渐减小，直到最后比较相邻元素有序的数据，其效率接近On，在实际应用中比冒泡和选择排序更有价希尔排序的时间复杂度取决于间隔序列的选择，通常在Onlogn到值On²之间。