1数据：数据是人们利用文字符号、数字符号以及其他规定的符号对现实世界的事物及其活动所做的抽象描述。
2线性表：线性表是具有相同属性的数据元素的一个有限序列。
3稀疏矩阵：稀疏矩阵是矩阵中的一种特殊情况，其非零元素的个数远远小于零元素的个数。
4栈：栈又称堆栈，它是一种运算受限的线性表，其限制是仅允许在表的一端进行插入和删除运算。
5数据类型：数据类型是对数据的取值范围、数据元素之间的结构以及允许施加操作的一种综合描述。
6数据结构：数据结构是指数据以及相互之间的联系。
7链接存储：在链接存储中，每个存储结点不仅含有所存元素本身的信息，而且含有元素之间逻辑关系的信息，其存储结点的结构为：
data P1 p2 ... pm 其中data表示值域，用来存储一个元素，p1,p2,...,pm(m≥1)均为指针域， 8队列：队列简称队，它也是一种运算受限的线性表，其限制是仅允许在表的一端进行插入，而在表的另一端进行删除。
9堆：堆分为小根堆和大根堆两种。对于一个小根堆，它是具有以下特性的一棵完全二叉树：（1）若树根结点存在左孩子，则根结点的值（或某个域的值）小于等于左孩子结点的值（或某个域的值）；（2）若树根结点存在右孩子，则根结点的值（或某个域的值）小于等于右孩子结点的值（或某个域的值）。（3）以左右孩子为根的子树又各是一个堆。（4）大根堆的定义与上述类似，只要把小于等于改为大于等于就可以了。 简答题
一、中缀表达式如何转换为后缀表达式课本89页几道例题 二、算法的定义及具有哪些特性
算法定义就是解决特定问题的方法。五个特性：1、有穷性：一个算法必须在执行有穷步之后结束。2、确定性：算法中每一步都必须有确切的含义。3、可行性：算法中每一步都必须是可行的，即算法中每一步都能够通过手工或机器可以接受的有限次操作在有限时间内实现。4、输入：一个算法可以有0个1个或多个输入量，在算法被执行前提供给算法。5、输出：一个算法执行结束后至少有一个输出量，它是利用算法对输入量进行运算和处理的结果。
三、树的性质1树中的结点数等于所有的结点的度数加1；2度为k的数中第i层上至多有ki-1个结点（i>>1）；3深度为h的k叉树至多有（kh-1）/(k-1)个结点；4具有n个结点的k叉树的最小深度为[logk(n(k-1)+1)]（k为底数） 四、什么是二叉搜索数：二叉搜索数又称二叉排序树，它或者是一棵空树，或者是一棵具有如下特性的非空二叉树：（1）若它左子树非空，则左子树上所有结点的关键字均小于根结点的关键字；（2）若它的右子树非空，则右子树上所有节点的关键字均大于（若允许具有相同的关键字的结点存在，则大于等于）根结点的关键字；（3）左、右子树本身又各是一棵二叉搜索树 五、什么是图、子图、完全图、路径、回路、连通、网
1图是一种复杂的非线性数据结构。2设有两个图G=(V,E)和G’(V’,E’)，若V’是V的子集，即V’?V，且E’是E的子集，即E’?E，则称G’是G的子图。3若无向图中的每两个顶点之间都存在着一条边，有向图中的每两个顶点之间都存在着方向相反的两条边，则称此图为完全图。4在一个图G中，从顶点v
到顶点v’的一条路径是一个顶点序列vi1，vi2，?，vim，其中v=vi1，v’=vim，若此图是无向图，则（vij-1，vij）∈E(G)，（2≤j≤m）；若此图是有向图，则
正确性，健壮性，可读性，简单性，时间复杂度，空间复杂度。
七、给出广义表，画出树：课本118页最上面的广义表，对应的树为图5-1 八、二叉树的性质：1二叉树上终端结点数等于双分支结点数加1；2二叉树上第i层上至多有2i-1个结点（i>>1）；3深度为h的二叉树至多有2h-1（2的h次方减1）个结点；4对完全二叉树中编号为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，它是双亲结点的右孩子。此点也适合于一般二叉树。5具有n个(n>0)结点的完全二叉树的深度为log2(n+1)或log2n+1。 九、二叉树有几种遍历递归算法？并写出算法。 前序遍历算法
void Preorder(struct BTreeNode* BT) { if(BT!=NULL) {
printf(\Preorder(BT->left); Preorder(BT->right); }
}
中序遍历算法
void Inorder (struct BTreeNode* BT) { if (BT!=NULL) { Inorder(BT->left);
printf(\Inorder(BT->right);} }
后序遍历递归算法
void Postorder(struct BTreeNode* BT) { if(BT!=NULL) {
Postorder(BT->left); Postorder(BT->right); printf(\ }
十、什么是哈夫曼树？写出它的具体算法
哈夫曼(Huffman)树又称作最优二叉树。它是n个带权叶子结点构成的所有二叉树中，带权路径长度WPL最小的二叉树。算法如下：(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中只含有一棵树为止，此树便是哈夫曼树。 十一、什么是栈，栈顶，栈顶元素，栈底，进栈，出栈
1栈（stack）又称堆栈，它是一种运算受限的线性表，其限制是仅允许在表的一端进行插入和删除运算。2人们把对栈进行运算的一端称为栈顶。3栈顶的第一个元素被称为栈顶元素。4相对地，把另一端称为栈底。5向一个栈插入新元素又称为进栈或入栈，它是把该元素放到栈顶元素的上面，使之成为新的栈顶元素。6从一个栈删除元素又称为出栈或退栈，它是把栈顶元素删除掉，使其下面的相邻元素成为新的栈顶元素。 普里姆算法
void Prim(adjmatrix GA,edgeset CT,int a,int n) { int i,j,k,min,t,m,w; struct edgeElem x; for(i=0;i if(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,k for(j=k-1;j if(CT[j].weight CT[k-1]=CT[m]; CT[m=x]; j=CT[k-1].endvex; for(i=k;i if(w CT[i].fromvex=j; } } } } P163向堆中插入一个元素的算法描述为： void InsertHeap(struct HeapSq* HBT, ElemType x) { int i; if(HBT->len==HBT->MaxSize) { ElemType *p; p=realloc(HBT->heap, 2*HBT->MaxSize*sizeof(ElemType)); if(!p) { printf(\存储空间用完!\\n\ exit(1);} HBT->heap=p; HBT->MaxSize=2*HBT->MaxSize; } HBT->heap[HBT->len]=x; HBT->len++; i=HBT->len-1; while(i!=0) { int j=(i-1)/2; if(x>=HBT->heap[j]) break; HBT->heap[i]=HBT->heap[j]; i=j; } HBT->heap[i]=x; } 克鲁斯卡尔算法 void Kruskal(edgeset GE,edgeset C,int n) { int i,j,k,d; int m1,m2; adjmatrix s; for(i=1;i { for(j=0;j while(k { for(i=0;i if(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;j s[m1][j]=s[m1][j] || s[m2][j]; s[m2][j]=0; }} d++ } } P187图的遍历深度优先搜索遍历 void dfs1(adjmatrix GA, int i, int n)/*从初始点vi出发深度优先搜索由邻接矩阵GA表示图*/ { int j; printf(\ visited[i]=1; for(j=0; j dfs1(GA,j,n); } (以邻接矩阵)广度优先搜索遍历的过程p189 void bfs1(adjmatrix GA, int i, int n) { struct QueueSq Q; InitQueue1(&Q); printf(\ EnQueue(&Q,i); while(!EmptyQueue(&Q)) { int j;int k=OutQueue(&Q); for(j=0; j if(GA[k][j]!=0 && GA[k][j]!=MaxValue && !visited[j]) { printf(\ visited[j]=1; EnQueue(&Q,j); } } } } (以邻接表)广度优先搜索遍历的过程p189 void bfs2 (adjlist GL, int i, int n) { struct QueueSq Q; InitQueue1(&Q); printf(\ EnQueue(&Q,i); while(!EmptyQueue(&Q)) { int k=OutQueue(&Q); struct edgenode* p=GL[k]; while（p！=NULL）｛ int j=p->adjvex; if (!visted[j]) { printf(\ visited[j]=1; EnQueue(&Q,j); }