1、排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为 （）。 希尔排序   冒泡排序 
插入排序  选择排序 
[A]   教师批改：C 
2、对线性表进行折半查找时，要求线性表必须（）。 以顺序方式存储  以链接方式存储 
以顺序方式存储，且结点按关键字有序排列  以链接方式存储，且结点按关键字有序排列 
[B]   教师批改：C 
3、设关键码序列为（16，9，4，25，15，2，13，18，17，5，8，24），要按关键码值递增的次序排列，采用直接选择排序法，一趟排序后的结果是（）。 （15，2，4，18，16，5，8，24，17，9，13，25）  （2，9，4，25，15，16，13，18，17，5，8，24） 
（9，4，16，15，2，13，18，17，5，8，24，25）  （9，16，4，25，21，5，13，18，5，17，8，24） 
[C]   教师批改：B 
4、在顺序表（3，6，8，10，12，15，16，18，21，25，30）中，用二分法查找关键码值11，所需的关键码比较次数为（）。 2  3 
4  5 
[A]   教师批改：C 
5、以下各组序列不属于堆的是（）。 （100，85，98，77，80，60，82，40，20，10，66）  （100，98，85，82，80，77，66，60，40，20，10） 
（10，20，40，60，66，77，80，82，85，98，100）  （100，85，40，77，80，60，66，98，82，10，20） 
[A]   教师批改：D 
6、顺序查找适合于存储结构为（）的线性表。 散列存储  顺序存储或链式存储 
压缩存储  索引存储 
[A]   教师批改：B 
7、设有1000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好选用（）排序法。 冒泡排序  快速排序 
堆排序  选择排序 
[B]   教师批改：C 
8、采用顺序查找法查找长度为N的线性表时，每个元素的平均查找长度为（）。 N  N/2 
（N+1）/2  （N-1）/2 
[C]   教师批改：C 
9、用直接插入排序方法对序列（15，11，9，10，13）进行排序，关键码比较次数为（）。 10  8 
4  9 
[D]   教师批改：A 
10、下列排序方法中，哪一个是稳定的排序方法（）。 归并排序  稀尔排序 
堆排序      快速排序 
[A]   教师批改：A 
11、下列排序方法中，属于稳定排序方法的有（）。
直接插入排序  冒泡排序 
快速排序  直接选择排序 
[AB]    教师批改：A，B 
12、下列查找方法中，可以将待查找序列按顺序存储方式进行存储的是（）
顺序查找  对分（或二分）查找 
分块查找  哈希（散列）查找 
[ACD]    教师批改：A，B，C，D 
13、下列各项中，属于完全二叉树特性的有（）。
叶子结点数比双分支结点数多一个，即n0=n2+1  在第K层，最多有2 K-1  （K>=1)个结点 
叶子结点都分布在最底的一层  叶子结点都分布在底部的两层 
[AB]    教师批改：A，B，D 
14、通过被查元素与表中的元素进行直接比较而达到查找目的的查找方法有（）。
顺序查找  对分查找（或称二分查找） 
分块查找  哈希查找 
[ABC]    教师批改：A，B，C 
15、有序线性表，若采用链式存储结构，则只能用顺序查找。 正确 错误
[错误]    教师批改：正确 
16、二分（或称对分）查找，也适用于链式存储的有序线性表。 正确 错误
[错误]    教师批改：错误 
17、分块查找比二分查找的查找速度要快。 正确 错误
[错误]    教师批改：错误 
18、比较理想的哈希函数须满足2个要求：散列地址的均匀性要好；散列地址的计算要尽量简单。 正确 错误
[正确]    教师批改：正确 
19、哈希表技术的一个特点是，怎么样存，也就怎么样查。 正确 错误
[]    教师批改：正确 
20、简单（或直接）选择法，是稳定的排序方法。 正确 错误
[正确]    教师批改：错误 
21、对于一棵二叉树，若其每个结点满足如下条件：其结点值大于其左孩子的结点值，而小于其右孩子的结点值，则该二叉树即是一棵二叉排序树。 正确 错误
[错误]    教师批改：错误 
22、拓扑排序（或称拓扑分类），也是将待排序序列按元素关键码值升序或降序进行排列的排序方法。 正确 错误
[正确]    教师批改：错误
23、顺序输入的数列（25，30，8，1，27，24，26，10，21，9，28，7，13，15），假定每个结点的查找概率相同，若用顺序存储方式组织该数列，则查找一个数成功的平均比较次数为（）。若按二叉排序树结构组织该数列，则查找一个数成功的平均比较次数为（）。
 教师批改：8、57/15 
24、二分法查找的存储结构仅限于（），且是有序的。
 教师批改：顺序存储结构 
25、（）排序方法采用的是二分法的思想，（）排序方法其数据的组织采用完全二叉树结构。
 教师批改：快速
堆 
26、在插入和选择排序中，若初始数据基本正序，则选用（）；若初始数据基本反序，则选用（）。
 教师批改：插入排序、选择排序 
27、对N个元素的序列进行冒泡排序时，最少的比较次数是（）。
 教师批改：N-1（当初始数据正序时，即已有序时，第一趟比较N-1次，交换数为0，完成排序） 
28、假定一组记录为（46，79，56，38，40，80），对其进行快速排序的第一次划分后的结果为（）。
 教师批改：[40，38]，46，[56，79，80] 
29、假定一组记录为（46，79，56，38，40，84），在冒泡排序的过程中进行第一趟排序后的结果是（）。
 教师批改：（46，56，38，40，79，84）
30、依次输入以下元素序列：
           56，78，34，45，85，45，36，91，84，78
试构造一棵二叉排序树。要在这棵二叉排序树中查找55，需要比较多少次？
教师批改：
构造的二叉排序树如下：

要在这棵二叉排序树中查找55，需要比较4次，以失败告终。
31、试编写在二叉排序树中插入一个元素的算法。 
教师批改：
输入：二叉排序树头指针BT，插入的元素b。
输出：插入元素b后的二叉排序树。
用C语言描述的算法如下（其中ET为数据元素类型）：
  #include  “stdlib.h”           
  struct  btnode          
  {  ET  d ;                    
    struct btnode  lchild ;   
    struct btnode  rchild ;    
  } ;
struct  btnode  *insort ( struct  btnode  * bt , ET  b )
{
  struct  btnode  * p , * q ;
  p = ( struct  btnode  * ) malloc ( sizeof ( struct btnode ) ) ;  
  p->d = b ;   p->lchild = NULL ;
  p->rchild =NULL ;
  q = bt ;
  if ( q = = NULL  )
     bt = p ;          
   else              
 {  while  ( ( q->lchild != p )  &&
     ( q->rchild != p ) )   
      { if  ( b < q-> d )  
             { if ( q->lchild != NULL )
                   q = q->lchild ;
                else  q->lchind = p ;
               }
         else        
               { if ( q->rchild != NULL )
                     q = q->rchild ;
                 else  q->rchind = p ;
               }
          }
     }
  return  ( bt ) ;          
     

2007-6-22