河南科技大学计软12级数据结构考试重点_管理学_高等教育_教育专区

《河南科技大学计软12级数据结构考试重点_管理学_高等教育_教育专区》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数据结构（C语言描述）复习要点数据：数据是人们利用文字符号、数字符号以及其他规定的符号对现实世界的事物及其活动所做的抽象描述。线性表：线性表是具有相同属性的数据元素的一个有限序列。稀疏矩阵：稀疏矩阵是矩阵中的一种特殊情况，其非零元素的个数远远小于零元素的个数。队列：简称队，它是一种运算受限的线性表，其限制是仅允许在表的一端进行插入，而在表的另一端进行删除。栈：栈又称堆栈，它是一种运算受限的线性表，其限制是仅允许在表的一端进行插入和删除运算。数据类型：数据类型是对数据的取值范围、数据元素之间的结构以及允

2、许施加操作的一种综合描述。数据结构：数据结构是指数据以及相互之间的联系。链接存储：链接存储的概念在链接存储中，每个存储结点不仅含有所存元素本身的信息，而且含有元素之间逻辑关系的信息，其存储结点（简称结点）的结构为：dataP1p2...pm其中data表示值域，用来存储一个元素，p1,p2,...,pm(m≥1)均为指针域，每个指针域的值为其对应的后继元素或前驱元素所在结点（以后简称为后继结点或前驱结点）的存储位置。通过结点的指针域（又称为链域）可以访问到对应的后继结点或前驱结点，该后继结点或前驱结点

3、称为指针域（链域）所指向（链接）的结点。若一个结点中的某个指针域不需要指向任何结点，则令它的值为空，用常量NULL表示，NULL在stdio.h中被定义为具有void*类型的整数0。队列：队列简称队，它也是一种运算受限的线性表，其限制是仅允许在表的一端进行插入，而在表的另一端进行删除。堆：堆是具有以下特性的一棵完全二叉树：（1）若树根结点存在左孩子，则根结点的值（或某个域的值）小于（大于）等于左孩子结点的值（或某个域的值）；（2）若树根结点存在右孩子，则根结点的值（或某个域的值）小于（大于）等于右孩子

4、结点的值（或某个域的值）。(3)以左右孩子为根的子树又各是一个堆。中缀表达式如何转换为后缀表达式略算法的定义及具有哪些特性算法就是解决特定问题的方法。作为一个算法应该具备以下五个特性：有穷性；确定性；可行性；输入；输出树的性质树的结点数等于所有的结点数的度数加1；度为k的数第i层上至多有ki-1个结点；深度为h的k叉树至多有（kh-1）/(k-1)个结点；具有n个结点的k叉树的最小深度为[log(n(k-1)+1)]什么是二叉搜索数二叉搜索数又称二叉排序树，它或者是一棵空树，或者是一棵具有如下特性的非

5、空二叉树：（1）若它左子树非空，则左子树上所有结点的关键字均小于根结点的关键字；（2）若它的右子树非空，则右子树上所有节点的关键字均大于（若允许具有相同的关键字的结点存在，则大于等于）根结点的关键字；（3）左、右子树本身又是一棵二叉搜索树什么是图、子图、完全图、路径、回路、连通、网图是一种复杂的非线性数据结构。设有两个图G=(V,E)和G’(V’,E’)，若V’是V的子集，即V’⊆V，且E’是E的子集，即E’⊆E，则称G’是G的子图。若无向图的每两个顶点之间都存在着一条边，有向图中的每两个顶点之间都存

6、在着方向相反的两条边，则称此图为完全图。在一个图G中，从顶点v到顶点v’的一条路径是一个顶点序列vi1，vi2，…，vim，其中v=vi1，v’=vim，若此图是有向图，则（vij-1，vij）∈E(G)，（2≤j≤m）；若此图是无向图，则∈E(G)，（2≤j≤m）。若一条路径上的前后两端点相同，则被称为回路。在有向图G中，若从顶点vi到vj有路径，则称从vi到vj是连通的。边上带有权的图称作带权图，也常称作网。一般从哪几个方面对算法进行评价？一般从以下六个方面对算法进行评价：正

7、确性，健壮性，可读性，简单性，时间复杂度，空间复杂度。给出广义表，画出树略二叉树的性质二叉树上终端结点数等于双分支结点数加1；二叉树上第i层上至多有2i-1个结点；深度为h的二叉树上至多有2h-1个结点；对完全二叉树中编号为i的结点（1≤i≤n，n>1，n为结点数）有(1)若i≤n/2，即2i≤n，则编号为i的结点为分支结点，否则为叶子结点。表达式x表示对x进行向下取整。(2)若n为奇数，则树中每个分支结点都既有左孩子，又有右孩子；若n为偶数，则编号最大的分支结点（编号为n/2）只有左孩子，没有右孩子

8、，其余分支结点左、右孩子都有。(3)若编号为i的结点有左孩子，则左孩子结点的编号为2i；若编号为i的结点有右孩子，则右孩子结点的编号为2i+1，即遵循对一般二叉树的编号规则。(4)除树根结点外，若一个结点的编号为i，则它的双亲结点的编号为n/2,也就是说，当i为偶数时，其双亲结点的编号为i/2，它是双亲结点的左孩子，当i为奇数时，其双亲结点的编号为(i-1)/2，它是双亲结点的右孩子。此点也适合于一般二叉树。具有n个(n>0)结点的完全二叉树的深度为lo