一、    选择题
1.    用二分法对一个长度为12的有序表进行二分查找，若各元素被等概率查找，则查找成功下所需的平均关键字比较次数是（  ）。
A）    35/12  B）37/12  C）39/12  D）43/12
2.    若一个序列的进栈顺序为1，2，3，4，则 ¬¬（）不是一个对应的出栈序列。
A）    3，2，1，4    B）4，2，3，1   C）4，3，2，1   D）1，2，3，4
3.    具有65个结点的完全二叉树，其深度为（）。（根在第一层）
A）8  B）7    C）6     D）5
4.    若表r在排序前已按元素键值递增顺序排列，采用（）方法比较次次数最少。
   A）直接插入排序   B）快速排序  C）归并排序    D）选择排序
5.    如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可采用（）查找方法。
       A）顺序  B）二分    C）分块  D）随机
6.    下列（）排序方法在每趟结束后不一定能选出一个元素放在其排好序的位置上。
   A）选择 B）昌泡  C）归并  D）随机
7.    对照个不同的数据进行排序，最多需要比较（）次。
   A）8   B）10    C）15  D）25
8.    下列排序算法中，稳定的是（）排序。
   A）直接选择 B）直接插入  C）快速  D）堆
9.    在线性表的存储结构中，能实现随机存取的是（）
   A）单链表 B） 双链表 C）循环链表  D）顺序表
10.    采用分块查找时，若线性表中共有225个元素，查找每个元素的概率相同，假充采用顺序查找来确定结点所在的块时，每块应分为（）个结点最佳。
   A）12   B）10  C） 15   D）25
11.    设顺序表中有10个元素。删除第4个元素需移动（）元素。
   A）5    B）6     C）7      D）8
12.    由n个结点所构成的二叉树其最小可能的高度是（）。
   A）log2(n+1)     B）  log2n+1   C）    log2n  D）[log2n]+1
13.    在一棵度为4的树中，度为4的结点有1个，度为3的结点有2个，度为0的结点有1个，则度为2的结点有（）个。
   A）5    B）4     C）3     D）2     
14.    将n个权值作为叶结点上的权值开始构成的哈夫曼树上有（）个非叶结点。
   A）n    B）2n-1     C）n-1     D）n+1
15.    二叉排序树上最小的结点在（）。
      A）最左下    B）最右下     C）叶中     D）内结点 
16.    设长度为100的分块索引表均匀分成10块，确定块号和在块内查找均采用线性查找，则查找的平均查找长度为（）。
  A）11    B）10     C）5.5     D）log2101-1
17.    由6棵结点数均为5的树所组成的森林转化的二叉树中，根结点的右子树上一定有结点。
   A）30    B）6     C）5     D）25
18.    带头结点的循环单链表H为空的判定条件是（）。
   A）H->next==NULL    B）H==NULL     C）H->next==N    D）H!=H->next
19.    （）排序法是不稳定的排序法。
    A）昌泡    B）直接插入  C）直接选择  D）归并
20.    （）排序法在记录按关键字有序的情况下，效率反而退化到最差。
A）    希尔 B）堆  C）快速  D）归并 

二、    简答题
1、在单链表中，为什么要增设一个虚的头结点？
2、平衡二叉树的作用是什么？
3、在平衡二叉树中，LR表示在何种情况下的一种旋转操作？
4、在顺序查找时为何要设置“哨岗”？
5、线索二叉链表中使用使用线索的目的是什么？

三、    判断题
1、    完全二叉树中，若一个结点无左孩子，则它必是叶子。
2、    循环队列中无溢出现象。
3、    同一棵二叉树先序序列和后序列可以唯一确定该二叉树。
4、    当所有结点权值相等时，用这些结点构造二叉排序权树的特点是只有右子树。
5、    二叉树是树的特殊情形。
6、    栈和队列都是特殊的线性表。
7、    深度为k(k≥1)的二叉树至多有2K-1个结点.
8、    散列表的平均查找长度不与表中元素个数n有关,而是与装填因子有关.
9、    平衡二叉树的查找与有序表的折半查找的时间性能相同。
10、哈夫曼树逻辑上是不唯一的，但一般算法只能求出唯一的一棵。

四、    填空题
1、    带头结点的单链表中，除头结点外，任一结点的存储位置保存在(   )。
2、    若含n个结点的无向图构成一个环，则它有(   )棵生成树。
3、    3个结点可构成(   )棵不同形态的树。
4、    算法的主要特性有：有穷性、确定性、(   )、输入和输出。
5、    ¬¬¬¬散列法存储的基本思想是根据(   )来决定储地址。
6、    可以仅由一个尾指针来唯一确定的链表有单笔直循环链表和(   )。
7、    一棵二叉树的先序序列为ABDCEFG，中序序列为DBCAFEG，则其后序序列为(   )。
8、    具有9个叶结点的二叉树，一定有(   )个度为2的结点。
9、    快速排序在n个数据呈现为(   )。算法效率反而降为O（n2）.
10、若由数据元素:34,76,45,18,26,54,92,65,依次插入结点的方法生成一棵二叉排序树,则其叶结点是(   ).
11、一棵含n个结点的k叉树，可能达到的最大高度为（   ），最小高度为（   ）。
12、    算具有输入、输出、可行性、（   ）和有穷性五大特性。
13、    一个高度为k的堆中，最多有（   ）个结点，最少有（   ）个结点。

五、算法阅读题。
试阅读下列各小题中的相应算法，并加以填充。
1.    双向冒泡排序是指从右往左从倒数的第1个位置进行两两比较，发现逆序就进行交换，将最小关键字的元素排至排序范围中的第一个位置。再从左往右从第2个位置开始两两相邻的数据元素按关键字进行比较，发现逆序的元素就进行交换，将最大的交换到扫描范围内的最后位置上。如此继续，下一趟比上一趟排序范围至少减少前后两个元素。直到最后排好序为止。
Struct   ElemTyps  {
      KeyType  key;
      DataType others;
};
typeder ElemType SQLIST[M];//M为一个较大的常数
void dbbubble(SQLIST r, n){//n为待排数据元素实际人数
int  I=1 ,j,  flag=1;
ElemType  temp;
While  (flag){
_______________;
for(__________;j>I+1;j___)
if ( f [j] .key<r [j-1].key){
   flag=1;
   temp=r[1];
__________
r[j-1]=temp;
}
for  (j=I+1;___;j++)
if(r[j].key>r[j+1].key){
flag=1;
temp=r[j];
___________;
r[j+1]=temp;
}
___________;
}
}
2、    二叉排序树上的插入.在以root为根的二叉排序树上插入关键字X。要求插入后仍保持为二叉排序树。
Struct BITNODE {
   KeyType  key;
    BITNODE  *LCHILD, *rchild;};
BITNODE  *insertbirtee(BITNODE  root , KeyType  x){
{BITNODE *P;
If  (root==NULL)
{__________;
 p->key=x;
 p-.lchild=NULL;
_____________;
}
else if (x<root->key)root->lchild=__________;
   else  root->rchild=____________;//分别递归插入左或右子树__________;//返回该二叉排序树
}
3．完成二叉树中任意结点的左、右孩子交换的操作。用非递归方法实现。设立一个堆栈stack用于存放还没有交换过的结点。设top为栈顶指针。交换算法如下：
a)    反根结点放入栈；
b)    当堆栈不空时，取出栈顶元素，交换它的左、右子树，并把它的左、右孩子入栈。
c)    重复（2）直到堆栈为空为止。
Const int  M=50;
Typedef struct node *tree;
Struct node {int data;
           Tree lchild, rchild;
           };
Exchange (terr t)
{tree p,temp;
tree stack[M];
int top=0;
&not;&not;&not;&not;&not;&not;&not;&not;&not;&not;&not;&not;&not;___________//根入栈  
while  (top>=0)
{___________//栈顶元素出栈
If (___________)
{ temp=p->rchild;
p->child=p->rchild;
p->child=temp;
stack[__________]=p->lchild; 
stack[__________]=p->lchild;
}
}
}
4、下列函数reverse不清的作用是完成单链表逆转的操作。
LINKNODE *reverse(LINKNODE *P){
LINKNODE *ptr,*p1,*p2;
Ptr=p;
___________
While(___________){
P2=ptr；
Ptr=ptr->next；
___________
p1=p2;
}
___________
}
六、计算题
1.    对数据：2，9，3，6，7，10，5，按此进入的次序，建立一棵平衡二叉树。
2.    对权值：10，7，3，8，9，2，5，分别所对应的符号设计哈夫曼编码。要求按算法路线先建立唯一的一棵哈夫曼树（而不是从逻辑上求出满足条件的任意一个），然后求出哈夫曼编码。
3.    已知一组关键字为：26，36，41，38，44，15，68，12，6，51，25，22用线性探查法解决冲突，构造散列表。要求：装填因子为0。8，选用除留余法H（Key）=Key%p作散列函数，p=13.并分别计算查找成功和不成功下的查找平均长度。

七、算法编写题
1.    编写在二叉排序树上查找关键字为X的结点算法。若找到，则返回其所在结点的指针，若没到，则将其插入该二叉排序树中。




2.    设A和B分别为两个集合，且均由链表顺序表示（设其中元素仅为整数，按值从小到大排列），求A与B 的交集。试写出相应的算法。





3.    假设以二叉链表为二叉树的存储结构，且每个结点中增加一个存入其作为根的子树中结点个数的域num，试编写一个算法求每个结点为根的子树上的结点数并存入其num域。




4.    编写将两个递增有序表合并为一个递减有序表的算法。要求用循环单链表加以实现。（数据结点类型自己加以定义说明）




5.    试编写算法，在二叉排序树中查找值为X的结点。若找不到，则返回空指针。若找到，则返回该 结点的指针，并将其为根的子树中的所有结点中的值按由小到大的次序加以输出（设结点中只含一个整数）



6.    以邻接表为存储结构，编写求图中各个顶点的入度的算法。




7.    计算下列模式串的每一位字符的失效函数值。（注：失效函数初值设为1）
1）a  b  a  a  b  c  a  c 

2)1001001100011001