河南科技大学计软12级数据结构考试重点

数据：数据是人们利用文字符号、数字符号以及其他规定的符号对现实世界的事物及其活动所做的抽象描述。

线性表：线性表是具有相同属性的数据元素的一个有限序列。

稀疏矩阵：稀疏矩阵是矩阵中的一种特殊情况，其非零元素的个数远远小于零元素的个数。 队列：简称队，它是一种运算受限的线性表，其限制是仅允许在表的一端进行插入，而在表的另一端进行删除。

栈：栈又称堆栈，它是一种运算受限的线性表，其限制是仅允许在表的一端进行插入和删除运算。 数据类型：数据类型是对数据的取值范围、数据元素之间的结构以及允许施加操作的一种综合描述。

数据结构：数据结构是指数据以及相互之间的联系。 链接存储：链接存储的概念 在链接存储中，每个存储结点不仅含有所存元素本身的信息，而且含有元素之间逻辑关系的信息，其存储结点（简称结点）的结构为：

data P1 p2 ... pm

其中data表示值域，用来存储一个元素，p1,p2,...,pm(m≥1)均为指针域，每个指针域的值为其对应的后继元素或前驱元素所在结点（以后简称为后继结点或前驱结点）的存储位置。通过结点的指针域（又称为链域）可以访问到对应的后继结点或前驱结点，该后继结点或前驱结点称为指针域（链域）所指向（链接）的结点。若一个结点中的某个指针域不需要指向任何结点，则令它的值为空，用常量NULL表示，NULL在stdio.h中被定义为具有void*类型的整数0。

队列：队列简称队，它也是一种运算受限的线性表，其限制是仅允许在表的一端进行插入，而在表的另一端进行删除。

堆：堆是具有以下特性的一棵完全二叉树：（1）若树根结点存在左孩子，则根结点的值（或某个域的值）小于（大于）等于左孩子结点的值（或某个域的值）；

（2）若树根结点存在右孩子，则根结点的值（或某个域的值）小于（大于）等于右孩子结点的值（或某个域的值）。

(3)以左右孩子为根的子树又各是一个堆。 中缀表达式如何转换为后缀表达式 略

算法的定义及具有哪些特性

算法就是解决特定问题的方法。作为一个算法应该具备以下五个特性：有穷性；确定性；可行性；输入；输出 树的性质

树的结点数等于所有的结点数的度数加1； 度为k的数第i层上至多有ki-1个结点；

深度为h的k叉树至多有（kh-1）/(k-1)个结点； 具有n个结点的k叉树的最小深度为[log(n(k-1)+1)] 什么是二叉搜索数

二叉搜索数又称二叉排序树，它或者是一棵空树，或者是一棵具有如下特性的非空二叉树：（1）若它左子树非空，则左子树上所有结点的关键字均小于根结点的关键字；

（2）若它的右子树非空，则右子树上所有节点的关键字均大于（若允许具有相同的关键字的结点存在，则大于等于）根结点的关键字； （3）左、右子树本身又是一棵二叉搜索树

什么是图、子图、完全图、路径、回路、连通、网 图是一种复杂的非线性数据结构。

设有两个图G=(V,E)和G’(V’,E’)，若V’是V的子集，即V’⊆V，且E’是E的子集，即E’⊆E，则称G’是G的子图。

若无向图的每两个顶点之间都存在着一条边，有向图中的每两个顶点之间都存在着方向相反的两条边，则称此图为完全图。

在一个图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是连通的。 边上带有权的图称作带权图，也常称作网。 一般从哪几个方面对算法进行评价？

一般从以下六个方面对算法进行评价：正确性，健壮性，可读性，简单性，时间复杂度，空间复杂度。

给出广义表，画出树 略

二叉树的性质

二叉树上终端结点数等于双分支结点数加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）只有左孩子，没有右孩子，其余分支结点左、右孩子都有。 (3) 若编号为i的结点有左孩子，则左孩子结点的编号为2i；若编号为i的结点有右孩子，则右孩子结点的编号为2i+1，即遵循对一般二叉树的编号规则。

(4) 除树根结点外，若一个结点的编号为i，则它的双亲结点的编号为n/2,也就是说，当i为偶数时，其双亲结点的编号为i/2，它是双亲结点的左孩子，当i为奇数时，其双亲结点的编号为(i-1)/2，它是双亲结点的右孩子。此点也适合于一般二叉树。 具有n个(n>0)结点的完全二叉树的深度为log2(n+1)或log2n+1。 二叉树有几种遍历递归算法？并写出算法。 前序遍历算法

void Preorder(struct BTreeNode* BT) {

if(BT!=NULL) {

printf(\"%c \Preorder(BT->left);

Preorder(BT->right);

} }

中序遍历算法

void Inorder (struct BTreeNode* BT) {

If (BT!=NULL) { Inorder(BT->left);

printf(\"%c \ Inorder(BT->right); } }

后序遍历递归算法

void Postorder(struct BTreeNode* BT) {

if(BT!=NULL) {

Postorder(BT->left); /*后序遍历左子树*/ Postorder(BT->right); /*后序遍历右子树*/ printf(\"%c \访问根结点*/ } }

什么是哈夫曼树？写出它的具体算法

哈夫曼(Huffman)树又称作最优二叉树。它是n个带权叶子结点构成的所有二叉树中，带权路径长度WPL最小的二叉树。因为构造这种树的算法是最早由哈夫曼于1952年提出的，所以被称之为哈夫曼树。 算法如下：

(1) 根据与n个权值{w1,w2,…,wn}对应的n个结点构成具有n棵二叉树的森林F={T1,T2,…,Tn}，其中每棵二叉树Ti(1≤i≤n)都只有一个权值为wi的根结点，其左、右子树均为空；

(2) 在森林F中选出两棵根结点的权值最小的树作为一棵新树的左、右子树，且置新树的根结点的权值为其左、右子树上根结点的权值之和；

(3) 从F中删除构成新树的那两棵树，同时把新树加入F中；

(4) 重复(2)和(3)步，直到F中只含有一棵树为止，此树便是哈夫曼树。 什么是栈，栈顶，栈顶元素，栈底，进栈，出栈

栈（stack）又称堆栈，它是一种运算受限的线性表，其限制是仅允许在表的一端进行插入和删除运算。

人们把对栈进行运算的一端称为栈顶。 栈顶的第一个元素被称为栈顶元素。 相对地，把另一端称为栈底。

向一个栈插入新元素又称为进栈或入栈，它是把该元素放到栈顶元素的上面，使之成为新的栈顶元素。

从一个栈删除元素又称为出栈或退栈，它是把栈顶元素删除掉，使其下面的相邻元素成为新的栈顶元素。 普里姆算法

void Prim(adjmatrix GA,edgeset CT,int a,int n) {

int i,j,k,min,t,m,w; struct edgeElem x; for(i=0;iCT[i].fromvex=a; CT[i].endvex=i;

CT[i].weight=GA[a][i]; }

else if(i>a) {

CT[i-1].fromvex=a; CT[i-1].endvex=i;

CT[i-1].weight=GA[a][i]; } }

for(k=1,kmin=MaxValue; m=k-1;

for(j=k-1;jif(CT[j].weightx=CT[k-1]; CT[k-1]=CT[m]; CT[m=x];

j=CT[k-1].endvex; for(i=k;iif(w克鲁斯卡尔算法

void Kruskal(edgeset GE,edgeset C,int n) {

int i,j,k,d; int m1,m2;

}

adjmatrix s; for(i=1;ifor(j=0;jif(i==j) s[i][j]=1; else s[i][j]=0; } k=1; d=0;

while(kfor(i=0;iif(s[i][GE[d].fromvex]==1) m1=i; if(s[i][GE[d].endvex]==1) m2=i); }

if(m1!=m2) {

C[k-1]=GE[d]; k++;

for(j=0;js[m1][j]=s[m1][j] || s[m2][j]; s[m2][j]=0; } } d++ }