完美WORD格式.整理
（30）设一棵二叉树结点的先序遍历序历为：ABDECFGH，中序遍历序历为：DEBAFCHG，则二叉树中叶结点是： E、F、H 。
（31）对于二叉树来说，第i层上至多有 2 个结点。 （32）深度为h的二叉树至多有 2-1 个结点。
（33）采用二叉链表存储的n个结点的二叉树，一共有 2n 个指针域。 （34）采用二叉链表存储的n个结点的二叉树，共有空指针 n+1 个。
（35）将一棵完全二叉树按层次编号，对于任意一个编号为i的结点，其左孩子结点的编号为： 2*i 。
（36）图常用的存储方式有邻接矩阵和 邻接表 等。 （37）图的遍历有： 深度优先搜 和广度优先搜等方法。 （38）设有一稀疏图G，则G采用 _邻接表____存储比较节省空间。 (39)设有一稠密图G，则G采用 _邻接矩阵____存储比较节省空间。
(40)在关键字序列（7，10，12，18，28，36，45，92）中，用二分查找法查找关键字92，要比较 4 次才找到。
(41)二叉排序树是一种 动态 查找表。
(42)哈希表是按 散 列 存储方式构造的存储结构 (43)哈希法既是一种存储方法，又是一种 查找 方法。
(44)散列表的查找效率主要取决于散列表造表时选取的散列函数和处理 冲突 的方法。
三、程序填空
（1）在带头结点head的单链表的结点a之后插入新元素x，试完成下列程序填空。
struct node { elemtype data; node *next; };
void lkinsert (node *head, elemtype x) { node *s, *p;
s= new node ; s->data= x ; p=head->next;
while (p!=NULL) && ( p->data!=a )
____p=p->next ; if (p==NULL)
cout<< \不存在结点a! \else {_____s->next=p->next______;
___ p->next=s __________; }
}
h
i-1
. 专业资料分享 .
完美WORD格式.整理
(2)假定用一个循环单链表表示一个循环队列，该队列只设一个队尾指针rear，试填空完成向循环队列中插入一个元素为x的结点的函数。
typedef struct queuenode // 定义队列的存储结构 { int data;
struct queuenode *next; }QueueNode;
InQueue(QueueNode *rear,int x) // 向队列插入元素为x的函数 { QueueNode *rear; QueueNode *head,*s;
s= new QueueNode ; s->data= x ;
if(rear==NULL) // 循环队列为空，则建立一个结点的循环队列 { rear=s; rear->next;} else
{ head= rear->next ; // 循环队列非空，则将s插到后面
rear->next= s ; rear=s;
rear->next =head; } } （3）下面程序是把两个串r1和r2首尾相连的程序，即：r1=r1+r2，试完成程序填空。
typedef Struct
{ char vec[MAXLEN]; // 定义合并后串的最大长度 int len; // len为串的长度 }St ;
void ConcatStr(Str *r1,Str *r2) // 字符串连接函数 { int i; cout<
{ for(i=0;i< r2->len ;i++) // 把r2连接到r1 r1->vec[ r1->len+i ]=r2->vec[i]; r1->vec[r1->len+i]= '\\0' ; // 添上字符串结束标记 r1->len= r1->len+r2->len ; // 修改新串长度 } } (4)下面算法是判断字符串是否为回文（即正读和倒读相同），试完成程序填空。
#include \typedef struct { char vec[MAXLEN]; int len; }str;
. 专业资料分享 .
完美WORD格式.整理
void Palindrome (str s) { int i=0;
ing j= s.len-1 ; while ( j-i>=1 )
{ if ( s.vec[i]== s.vec[j] )
{i++; j-- ;continue} // (或 j=j+1 ) else break; }
if ( j-i>=1 )
cout<<\ else
cout<<\}
(5)void BInsSort( ) //按递增序对R[1]~R[ n ]进行二分插入排序
{ int i, j, low, high, m; for( i=2;i<= n ; i++) { R[0]=R[i];
low=1; high= n ； while(low <= high) { m=(low+high)/2 ;
if(R[0] low=m+1; } for(j=i-1;j>=high+1;j--) R[j+1]= R[ j ] ; } } 四、应用题 （1）已知一棵二叉树的后序遍历和中序遍历的序列分别为：ACDBGIHFE和ABCDEFGHI。 请画出该二叉树，并写出它的前序遍历的序列。 解：恢复的二叉树为： E B A C DG F H I // 元素后移 R[high]=R[0]; // 插入 // 设定R[0]为监视哨 . 专业资料分享 . 完美WORD格式.整理 其前序遍历的序列为：E B A D C F H G I （2） 把下列一般树转换为二叉树 ① ② 1 A 2 B C 4 3 5 F E G H I 6 7 J 8 解： ① ② 1 A 2 B 3 C E 4 F H D 5 J G I 6 8 7 （3）把下列森林转换为二叉树 ① ② ③ A F H C B D G I J E K . 专业资料分享 . D