数据结构考点仅供参考

《数据结构考点仅供参考》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数据结构填空与选择参考资料（此中题目由根据老师上课所提考点写成，仅供参考）（以下提到的log2n,均为以2底数，n为对数的指数）1.集合中的每一个数据元素均只有一个前驱；（4）除最后一个之外，集合中每个数据元素均只有一个后继2.带头节点空表的表示:在书上P28图2.7（b)所示3.书上P29页算法2.8中单链表的插入、删除算法语句4.书上P36页双向链表的算法语句5.栈是限定仅在表尾进行插入和删除操作的线性表。因此，对栈来说，表尾端有其特殊含义，称为栈顶，相应的，表头称为栈底，不含元素的空表称为空栈6.栈的特点：先进后出(FI

2、LO）（或者被称为后进先出（LIFO)）7.队列的特点：先进先出8.循环队列如何判断队列是空是满：当(Q.real+1)%MAXQSIZE==Q.front，队列满；当Q.front==Q.rear，队列为空（书P63至P65有详解）9.循环队列：根据头指针、尾指针求队列长度,队长为(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE(MAXQSIZE为队列设定的能允许的最大队列的长度）10.串：串中任意个连续的字符组成的子序列称为该串的子串，通常称字符在序列中的序号为该字符在串中的位置11.由一个或多个空格组

3、成的串称为空格串，零个字符的串称为空串，空格串不等于空串1.Concat(&T,S1,S2)操作结果：用T返回S1和S2联接而成的新串（看书P71页各个串的基本操作）2.了解串中转义字符的使用3.串中字符的数目称为串的长度，StrLength(S)操作结果为返回元素的个数（串的长度），注意：串的长度与存储空间大小不一样，串的结尾有标志‘’，串的长度不包括，空间大小包括4.求子串在主串中的位置：看书P79算法4.5所示，求子位置的定位函数Index(S,T,pos)5.看书P80模式匹配6.假若相同的元素或者零元素在

4、矩阵中的分布有一定的规律，则我们称此类矩阵为特殊矩阵，反之，称为稀疏矩阵7.了解数组（书P90）、矩阵的压缩存储（书P95）、稀疏矩阵（P96)、三元组（书P98）8.广义表一般记作：LS=（α1，,α2，...，αn）；当广义表非空时，称第一个元素α1为LS的表头，称其余元素组成的表（α2，α3，...，αn）是LS的表尾9.任何一个非空列表其表头可能是原子，也可能是列表，而其表尾必定为列表。（书P108）10.二叉树是另一种树型结构，它的特点是每个节点至多只有两颗子树，二叉树的子树有左右之分，其次序不能任意颠倒。（书P12

5、1）11.看书P120树的相关名称概念树的度是树内各结点的度的最大值，树中结点最大的层次称为树的深度k1.二叉树的性质：性质1：在二叉树的第i层上至多有个结点（i≥1)。性质2：深度为k的二叉树至多有个结点（k≥1）性质3：对任何一颗二叉树T，如果其终端结点数为n0，度为2的结点数为n2,则n0=n2+1n性质4：具有n个结点的完全二叉树的深度为n[log2n]+1n性质5：如果对一棵有n个结点的完全二叉树（其深度为[log2n]+1)的结点按序编号（从第1层到第[log2n]+1层，每层从左到右），则对任一结点i（1≤i≤n

6、),有：（1）如果i=1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲PARENT(i)是结点[i/2]（2）如果2i>n,则结点i无左孩子（结点i为叶子结点）；否则其左孩子LCHILD(i)是结点2ik（3）如果2i+1>n,则结点i无右孩子；否则其右孩子RCHILD(i)是结点2i+130.一棵深度为k且有个结点的二叉树为满二叉树31.深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称之为完全二叉树30.遍历二叉树：按某条搜索路径巡防树中每个结点，使得每个结点

7、均被访问一次，而且仅被访问一次。访问顺序：先序遍历二叉树：根结点→左子树→右子树中序遍历二叉树：左子树→根结点→右子树后序遍历二叉树：左子树→右子树→中子树31.加上线索的二叉树称之为线索二叉树（书P132）32.森林是m（m≥0)棵互不相交的树的集合森林与树的相互转换：树→森林：在兄弟之间连线去除左孩子以外的线横线全部顺时针旋转45度（书P137图6.16）森林→树：将各棵树转换为二叉树连接各个根结点以第一个二叉树的根结点为二叉树的根，其它横线以根结点为轴，顺时针旋转45度（书P138图6.17）33.用n表示图中顶点数目，

8、e表示边或弧的数目，对于无向图，e的取值范围是0到n(n-1)。有n(n-1)条边的无向图称为完全图。对于有向图，e的取值范围是0到n(n-1)，具有n(n-1)条弧的有向图称为有向完全图。有很少边或弧（如e