《计算机科学导论》有哪些章节是关于计算机硬件基础、计算机软件基础、数据结构基础、操作系统基础的？

数据结构学科的章节基本分为:绪论、线性表、堆栈和队列、字符串、多维数组和广义表、树和二叉树、图、搜索、内行、外行、文件和动态存储分配。

对于绝大多数学校来说，“流出、档案、动态存储分配”三章基本不考，在大多数高校的计算机本科教学过程中基本不教。所以这三章不用花太多精力，只要知道基本概念就行。但是对于申请名校，尤其是学校，并且在试卷上有考核这三章的历史的人来说，那么这些朋友就要注意这三章了。

根据上面给出的章节和后三章的介绍，章节在数据结构中所占的比例大致如下:

简介:内容很少，概念简单，大部分分数只有几分，有的学校甚至不考。

线性表:基础章节，必修内容之一。考题多为基本概念题，名校大规模算法设计题很少。如果有，也是结合其他章节。

堆栈与队列:基础章节，易给基本概念题，必考内容之一。栈经常和其他章节一起被检查，也经常和递归这样的概念联系在一起。

弦乐:基础章节，概念比较简单。很少有专门针对这一章的大规模算法设计问题，更常见的是按照KMP来分析算法。

多维数组和广义表:基础章节中，基于数组的算法题也比较常见，分值比例波动较大，所以是题的“可选单元”或“等待单元”。一般要出题的话，大多不会作为大题出题。数组经常和“搜索、排序”等章节结合在一起作为一个大题。

树和二叉树:重点和难点章节，所有学校都要求。这一章学校的区别在于，这一章给出的是一个还是两个大的算法设计问题。通过对多所学校的试卷分析，大部分学校都有过本章大规模算法设计题的历史。

图:重点难点章节，特别是名校。如果以考试为重点，多出现在分析设计题中，可以和树章一起形成算法设计题的题型设计。

搜索:重点难点章节，概念多，联系紧密，容易混淆。问题可以作为分析性问题给出，在基本概念题中也很常见。算法设计题可以通过数组组合来考查，也可以结合树章来考查。

排序:类似于找一章，这一章既属于重点章节，也属于难点章节，概念更多，联系更紧密，也更容易混淆。在基本概念的考查中，我特别喜欢比较各种排序算法的优劣。在算法设计这个大问题中，如果作为一个问题，往往会结合数组来考察。

其次，概述了数据结构每一章的要点:

第0章概述

这一章主要起一个引导作用，为读者学习数据结构打下一些基础。我们主要关注以下几点:数据结构的基本概念，时间和空间复杂度的概念和度量方法，算法设计的注意事项。本章考点不多，注意理解即可。

第一章线性表

线性表章节作为线性结构的开篇章节，在线性结构乃至整个数据结构学科的学习中起着重要的作用。本章首次系统地介绍了链式存储的概念，无论哪一章涉及到这个概念，链式存储都将是整个数据结构学科中最重要的部分。

一般来说，线性表这一章的重要考点可以从以下几个方面来考察:

1.与线性表相关的基本概念，如前任、继任、表长、空表、头节点、头节点、头指针等等。

2.线性表的结构特点主要是指每个节点除首末元素外，只有一个前任和一个继任者。

3.线性表的顺序存储方式及其在特定语言环境下的两种不同实现:表空间的静态分配和动态分配。静态链表和顺序链表的异同。

4.线性表的链式存储方式以及以下几种常用链表的特点和操作:单链表、循环链表、双向链表、双向循环链表。其中，单链表的归并算法、循环链表的归并算法、双向链表和双向循环链表的插入和删除算法都是常见的检查方法。另外，最近几年，很多学校出现了需要递归算法实现单链表输出(或者按顺序，或者按逆序)的问题。

在链表的小题中，我们经常会得到一些问题比如:判断空表。在不同的链表中，判断空表的方式是不同的。请注意。

5.在线性表顺序存储和链式存储的情况下，比较了它们不同的优缺点，即各自的适用场合。在单链表中设置头指针，在循环链表中设置尾指针而不设置头指针和索引存储结构的优点。

第二章堆栈和队列

堆栈和队列是很多学习DS的学生遇到的第一个障碍。很多人从这一章开始晕车，一直晕到现在。所以理解栈和队列是掌握DS的必经之路。

在学习本章之前，你可以问问自己是否已经知道以下几点:

1.栈和队列的定义以及数据结构的相关概念，包括:顺序栈、链栈、* * * *共享栈、循环队列、链队列等。堆栈和队列访问数据的特点(请注意包括存储和检索两部分)。

2.递归算法。堆栈和递归的关系，借助堆栈把递归变成非递归的经典算法:n！阶乘问题、fib序列问题、hanoi问题、背包问题、二叉树的递归与非递归遍历问题、图深度遍历与栈的关系等。其中与树和图相关的问题多在树和图的相关章节中考查。

3.堆栈的应用:数值表达式的求解原理和圆括号的匹配只是原理上的理解，没有太多具体的要求去考察本题的算法设计。

4.循环队列中判断队列是空还是满的条件，循环队列中排队和出队的算法。

如果你熟悉以上几点，你可以跳过栈和队列这一章。注意，我说的是可以不看了，不是可以不写题了。

第三章弦

在经历了栈章的痛苦煎熬后，终于迎来了连载章。

字符串，概念上是比较少的章节，也是最容易自学的章节之一，但是经历过的人都知道，KMP算法是这一章的重要关口。过了这个关口，就是马平川的又一条大DS山河了，呵呵。

需要攻破主要堡垒的一串章节是:

1.字符串的基本概念，字符串和线性表的关系(字符串是一种特殊的线性表，其元素都是字符数据)，空字符串和空白字符串的区别，字符串相等的条件。

2.字符串的基本操作以及这些基本函数的使用，包括子串、字符串串联、字符串替换、字符串长度计算等等。利用字符串的基本运算来完成一个特定的算法是很多学校在基本运算中的重点。

3.数列串与链式串、区块链串的区别与联系，以及实现方法。

4.KMP算法的想法。KMP next阵列和nextval阵列的求解。明确传统模式匹配算法的不足和下一步需要改进的地方。其中理解算法是核心，数组是得分点。不用说，这一节是本章最重要的部分。可能的检查方式是找到next和nextval的数组值，根据得到的next或nextval的数组值给出使用KMP算法的匹配过程。

第四章数组和广义表

学过编程语言的朋友，已经不是第一次看到数组的概念了，应该是“一次生，两次熟”，所以概念上不会有太大的障碍。不过作为研究生课程，这一章的重点可能和大学的编程语言有所不同，下面会介绍。

数据结构中首次出现了广义表的概念。它是线性表或表元素的有限序列，构成结构的每个子表或元素也是线性的，所以本章也归为线性结构。

本章的重点是:

1.多维数组中数组元素的位置求解。一般给定一个数组元素的第一个元素的地址和每个元素占用的地址空间，给定一个多维数组的维数，然后要求你找出一个元素在数组中的位置。

2.明确行存储和列存储的区别和联系，能够根据这两种不同的存储方式解决1中的问题。

3.根据相应的转换方法将特殊矩阵中的元素存储到数组中。这些矩阵包括:对称矩阵、三角矩阵、具有一定特征的稀疏矩阵等等。熟悉稀疏矩阵的三种不同存储方式:三重、带辅助行向量的二进制和交叉链表存储。掌握将稀疏矩阵的三元或二元组转化为交叉链表的算法。

4.广义表的概念，尤其是表头和表尾的定义。这是理解广义表全节算法的基础。最近在一些学校出现了这样一种题型:对某个广义表L进行几次取头取尾的操作后给出字符串值，并求原广义表L，大家要注意了。

5.与广义表相关的递归算法。因为广义表的定义是递归的，所以与广义表相关的算法往往也是递归的。比如:求表的深度，复制广义表等。这个问题可以根据广义表的表现形式从不同的角度用两种不同的方式来解决:一种是把广义表当作表头和表尾，分别操作表头和表尾；第二种是把一个一般化的表看成几个子表，分别对每个子表进行操作。

第五章树和二叉树

从对线性结构的过度学习到对树型结构的学习，是数据结构课程学习的一次飞跃。这个飞跃的完成将直接影响到你在实际考试中能否取得高分，而这一切最终都会影响到你的专业课总分。因此，这一章对于树木的重要性不言而喻。

一般来说，树章节的知识点包括:

二叉树的概念、性质和存储结构，二叉树遍历的三种算法(递归和非递归)，基于三种基本遍历算法的其他算法，线索二叉树的概念、线索算法和线索后搜索算法，最优二叉树的概念、组成和应用，树的概念和存储形式，树和森林的遍历算法及其与二叉树遍历算法的关系，树和森林与二叉树的转换。