下载文档原格式
1.对顺序存储结构的线性表,设表长为La;插入一个数据元素需平均]
移动表中元素n/2 个;在最坏情况下需移动表中元素_n_个。
2.从逻辑角度看，四种基本的数据结构可分为集合、线性结构、
树形结构和图状结构；两种存储结构为顺序和链式。
5.堆栈被称为一个后进先出的线性表;队列被称为一个先进先出的线性表
6.静态查找表的查找方法主要有：有序表查找及有序表、静态树表、索引顺序表等查找方法；
8.内部排序方法大致可分为插入、交换、选择、归并和计数等五类；
简单排序方法的时间复杂度为O(n2)。
9．前序序列和中序序列相同的二叉树为单右支二叉树或孤立结点
10.文件的组织方式有顺序、随机和链等三种；顺序文件又可分为
连续文件和串联文件两大类。
11. 在内部排序中，平均比较次数最少的是快速排序，要求附加
的内存容量最大的是归并排序。
12.由n个权值构成的哈夫曼树共有2n-1个结点。
13.在单链表中，除首元结点外，任一结点的存储位置由其直接前趋
结点的链域指示。
14.栈结构允许进行删除操作的一端称为栈的栈顶。
15. GetTail(p)为求广义表p的表尾函数。其中( )是函数符号，运算
GetTail(GetHead((a,b),(c,d)))的结果是(b)。
16．循环链表的主要优点是从任一结点出发可以遍历链表中的所有结点17．在左右子树均不空的先序线索二叉树（有n个结点）中，空链
域的数目是1。
18.如果含n个顶点的图是一个环，则它有n棵生成树。
在有序表ST中折半查找其关键字等于key的数据元素。若找到，
则函数值为该元素在表中的位置，否则为0。
Low =1; high=ST.length;
While (low<=high){
mid= (low+high)/2;
if EQ(key, ST.elem[mid].key) return mid;
else if LT( key, ST.elem[mid].key) high=mid-1;
else low= mid+1;
2. 中序遍历二叉树T的递归算法，对数据元素操作调用函数printf()。InOrderTraverse(struct TNode *T){
if (T){
InOrderTraverse(___T->lchild___);
printf("%c",___ T->data _____);
InOrderTraverse(___T->rchild_____);
3. void Pop(SqStack *S0, char *e){
//若栈不空，则删除栈顶元素，用e返回其值。
if(S0->top= =__S0->base _____) return;
____(S0->top)_____;
*e=*(____(S0->top)_____);
4. 给出一整数序列(4,2,5,6,3),从小到大排序选用直接插入排序、2—路
归并排序及快速排序:(2,4,5,6,3), (2,4,5,6,3), (3,2,4,6,5)
5. 已知一颗3阶的B-树（见下图），依次插入关键字3及90，分别写出
每插入一个关键字后所生成的B-树? （10分）。
1.对关键字序列{72，73,71,23,94,16,05,68},按照堆排序（直接插入排序）的方法进行排序。（8分）
6. 已知一无向带权图（见下图），写出其最小生成树（10分）。
7. 已知4个结点的权值为｛20，30，32，40，78｝，构造一颗
赫夫曼树，并写出其赫夫曼编码（10分）。
四、简答题（每小题7分，共42分）
3. 已知一棵二叉树的中序遍历序列为CDBAEGF, 先序遍历序列为ABCDEFG，试问能不能唯一确定一棵二叉树，若能，请画出该二叉树。
答：（1）由中序遍历序列和先序遍历或中序遍历和后序遍历序列可以唯一确定一棵二叉树。基本思想是前序（后序）定根，中序分左右。
对于给定的先序和中序序列，可确定根结点为A,以A为根的左子树结点为B,C,D,右子树结
点为E,F,G。进一步确定所有子树的根结点，因而也就确定了整个二叉树。对应的二叉树如附图2 所示。
4. 已知一个有向图和该图的邻接表如图1所示，并依此邻接表进行从顶点a开始出发的深度优先遍历，画出由此得到的深度优先生成树。
答：DFS生成树如附图下图所示。
6. 已知序列(12,18,4,3,6,13,2,9,19,8)。请给出采用希尔排序对该序列作升序排序的第一趟结果（初始步长为5）。
答：(12,2,4,3,6,13,18,9,19,8)
