《软件设计师考试考点分析与真题详解(版)》由会员分享，可在线阅读，更多相关《软件设计师考试考点分析与真题详解(版)（75页珍藏版）》请在金锄头文库上搜索。
1、 软件设计师 http:/ 4 版）第 1 章 数据结构基础数据结构是指数据对象及其相互关系和构造方法，一个数据结构 S 可以用一个二元组表示为：S=（D,R）。其中，D 是数据结构中的数据的非空有限集合，R 是定义在 D 上的关系的非空有限集合。在数据结构中，结点及结点间的相互关系称为数据的逻辑结构，数据在计算机中的存储形式称为数据的存储结构。数据结构按逻辑结构的不同分为线性结构和非线性结构两大类，其中非线性结构又可分为树形结构和图结构，而树形结构又可分为树结构和二叉树结构。按照考试大纲的要求，在数据结构与算法方面，要求考生掌握以下知识点。1.常用数据结构数组（静态数组、动态数组）、线性表、
2、链表（单向链表、双向链表、循环链表）、队列、栈、树（二叉树、查找树、平衡树、线索树、堆）、图等的定义、存储和操作。Hash（存储地址计算，冲突处理）。2.常用算法排序算法、查找算法、数值计算方法、字符串处理方法、数据压缩算法、递归算法、图的相关算法。软件设计师 http:/ 线性表线性表是最简单、最常用的一种数据结构，它是由相同类型的结点组成的有限序列。一个由 n 个结点 a0,a1,，an1 组成的线性表可记为（a0,a1,，an1）。线性表的结点个数为线性表的长度，长度为 0 的线性表称为空表。对于非空线性表，a0 是线性表的第一个结点，an1 是线性表的最后一个结点。线性表的结点构成一个
3、序列，对序列中两相邻结点 ai 和 ai+1,称 ai 是 ai+1 的前驱结点，ai+1 是 ai 的后继结点。其中 a0 没有前驱结点，an1 没有后继结点。线性表中结点之间的关系可由结点在线性表中的位置确定，通常用（ai,ai+1）（0in2）表示两个结点之间的先后关系。例如，如果两个线性表有相同的数据结点，但它们的结点在线性表中出现的顺序不同，则它们是两个不同的线性表。线性表的结点可由若干成分组成，其中能唯一标识该结点的成分称为关键字，或简称键。为了讨论方便，往往只考虑结点的关键字，而忽略其他成分。1.线性表的基本运算软件设计师 http:/ i（0in1）个结点的前面或后面插入一个新
4、结点。3）删除运算删除线性表的第 i（0in 1）个结点。4）其他运算统计线性表中结点的个数；输出线性表各结点的值；复制线性表；线性表分拆；线性表合并；线性表排序；软件设计师 http:/ i 个结点存储在数组的第 i（0in1）个元素中，用数组元素的顺序存储来体现线性表中结点的先后次序关系。顺序存储线性表的最大优点就是能随机存取线性表中的任何一个结点，缺点主要有两个，一是数组的大小通常是固定的，不利于任意增加或减少线性表的结点个数；二是插入和删除线性表的结点时，要移动数组中的其他元素，操作复杂。2）链接存储链接存储是用链表存储线性表（链表），最简单的是用单向链表，即从链表的第一个结点开始，将
5、线性表的结点依次存储在链表的各结点中。链表的每个结点不但要存储线性表结点的信息，还要用一个域存储其后继结点的指针。单向链表通过链接指针来体现线性表中结点的先后次序关系。链表存储线性表的优点是线性表中每个结点的实际存储位置是任意的，这给线性表的插入和删除操作带来了方便，只要改变链表有关结点的后继指针就能完成插入或删除的操软件设计师 http:/ n 个结点，把值为 x 的新结点插在线性表的第 i（0in）个位置上。完成插入主要有以下步骤：检查插入要求的有关参数的合理性；把原来的第 n1 个结点至第 i 个结点依次往后移一个数组元素位置；把新结点放在第 i 个位置上；修正线性表的结点个数。在具有
6、n 个结点的线性表上插入新结点，其时间主要花费在移动结点的循环上。若插入任一位置的概率相等，则在顺序存储线性表中插入一个新结点，平均移动次数为 n/2.软件设计师 http:/ x 的新结点，分为以下 4 种情况：在某指针 p 所指结点之后插入；插在首结点之前，使待插入结点成为新的首结点；接在线性表的末尾；在有序链表中插入，使新的线性表仍然有序。5.删除线性表的结点1）顺序存储在有 n 个结点的线性表中，删除第 i（0in1）个结点。删除时应将第 i+1 个结点至第 n1 个结点依次向前移一个数组元素位置，共移动 ni1 个结点。完成删除主要有以下几个步骤：检查删除要求的有关参数的合理性；把原
7、来第 i+1 个表元至第 n1 个结点依次向前移一个数组元素位置；修正线性表表元个数。在具有 n 个结点的线性表上删除结点，其时间主要花费在移动表元的循环上。若删除任一表元的概率相等，则在顺序存储线性表中删除一个结点，平均移动次数为（n-1）/2.软件设计师 http:/ 栈栈是一种特殊的线性表，栈只允许在同一端进行插入和删除运算。允许插入和删除的一端称为栈顶，另一端为栈底。称栈的结点插入为进栈，结点删除为出栈。因为最后进栈的结点必定最先出栈，所以栈具有后进先出的特征。1.顺序存储可以用顺序存储线性表来表示栈，为了指明当前执行插入和删除运算的栈顶位置，需要一个地址变量 top 指出栈顶结点在数
8、组中的下标。软件设计师 http:/ top,top 为 NULL 的链表是空栈。1.1.2 队列队列也是一种特殊的线性表，只允许在一端进行插入，另一端进行删除运算。允许删除运算的那一端称为队首，允许插入运算的一端称为队尾。称队列的结点插入为进队，结点删除为出队。因最先进入队列的结点将最先出队，所以队列具有先进先出的特征。1.顺序存储可以用顺序存储线性表来表示队列，为了指明当前执行出队运算的队首位置，需要一个指针变量 head（称为头指针），为了指明当前执行进队运算的队尾位置，也需要一个指针变量 tail（称为尾指针）。若用有 N 个元素的数组表示队列，随着一系列进队和出队运算，队列的结点移向
9、存放队列的数组的尾端，会出现数组的前端空着，而队列空间已用完的情况。一种可行的解决办法是当发生这样的情况时，把队列中的结点移到数组的前端，修改头指针和尾指针。另一种更好的解决办法是采用循环队列。循环队列就是将实现队列的数组 aN的第一个元素 a0与最后一个元素 aN1连接起来。队空的初态为 head=tail=0.在循环队列中，当 tail 赶上 head 时，队列满。反之，当 head 赶上 tail 时，队列变为空。这样队空和队满的条件都同为 head=tail,这会给程序软件设计师 http:/ head=tail,队满的判别条件是 head=tail+1。2.链接存储队列也可以用链接存
10、储线性表实现，用链表实现的队列称为链接队列。链表的第一个结点是队列首结点，链表的末尾结点是队列的队尾结点，队尾结点的链接指针值为 NULL.队列的头指针 head 指向链表的首结点，队列的尾指针 tail 指向链表的尾结点。当队列的头指针 head 值为 NULL 时，队列为空。1.1.3 稀疏矩阵在计算机中存储一个矩阵时，可使用二维数组。例如，MN 阶矩阵可用一个数组aMN来存储（可按照行优先或列优先的顺序）。如果一个矩阵的元素绝大部分为零，则称为稀疏矩阵。若直接用一个二维数组表示稀疏矩阵，则会因存储太多的零元素而浪费大量的内存空间。因此，通常采用三元组数组或十字链表两种方法来存储稀疏矩阵。
11、1.三元组数组稀疏矩阵的每个非零元素用一个三元组来表示，即非零元素的行号、列号和它的值。然后按某种顺序将全部非零元素的三元组存于一个数组中。如果只对稀疏矩阵的某些单个元素进行处理，则宜用三元组表示。软件设计师 http:/ 5 个域，分别为结点对应的矩阵元素的行号、列号、值，以及该结点所在行链表后继结点指针、所在列链表后继结点指针。为了处理方便，通常对每个行链表和列链表分别设置一个表头结点，并使它们构成带表头结点的循环链表。为了引用某行某列的方便，全部行链表的表头结点和全部列链表的表头结点分别组成数组，这两个数组的首结点指针存于一个十字链表的头结点中，最后由一个指针指向该头结点。例如有矩阵 A 如图 1-1 所示。则其十字链表如图 1-2 所示。图 1-1 矩阵 A 示意图图 1-2软件设计师 http:/ A 十字链表存储示意图如果对稀疏矩阵某行或某列整体做某种处理，可能会使原来为零的元素变为非零，而原来非零的元素变成零。对于这种场合，稀疏矩阵宜用十字链表来表示。1.1.4 字符串字符串是由某字符集上的字符所组成的任何有限字符序列。当一个字符串不包含任何字符时，称它为空字符串。一个字符串所包含的有效字符个数称为这个字符串的长度。一个字符串中任一连续的子序列称为该字符串的子串。字符串通常存于足够大的字符
