数据结构(本)期末综合练习(2015年11月)

2015年11月

综合练习一

一、单项选择题

  1.对稀疏矩阵进行压缩存储,可采用三元组表，一个10 行8列的稀疏矩阵A共有73

    个零元素，其相应的三元组表共有(   C   )个元素。

    A．8                  B．80     C．7                  D．10             

2. 对稀疏矩阵进行压缩存储,可采用三元组表，一个10 行8列的稀疏矩阵A，其相应的

     三元组表共有6个元素，矩阵A共有(    C   )个零元素。

     A．8                B．72      C．74            D．10  

3.字符串(   A  )是“abcd321ABCD”的子串。

A. “21AB”     B. “abcD”       C. “aBCD”        D. “321a”

   4. 程序段

     char a[  ]=“abdcacdef”; 

     char *p=a;  int n=0; 

     while( *p!=‘\0’){ n++; p++;} 结果中,n的值是（    D   ）。

       A. 6           B.8          C.      7        D.9        

5.栈和队列的共同特点是（  A ）。

     A．都是操作受限的线性结构       B．元素都可以随机进出

     C．都是先进后出               D．都是先进先出                                          

   6. 10,6,2,1按顺序依次进栈，该队列的可能输出序列是（  A  ）。

 (进栈出栈可以交替进行）。

     A．6,10,1,2    B．2,10,6,1         C．6,1,10,1            D．1,6,10,2

7. 在一个链队中，假设f和r分别为队头和队尾指针，p指向一个新结点,要为结点p

      所指结点赋值x,并入队的运算为p->data=x; p->next=NULL;（ B  ）。

     A. f->next=p; f=p;     B． r->next=p;r=p;

     C． r=p; p->next=r;     D． p->next=f;f=p;                                               

8. 对一个栈顶指针为top的链栈进行出栈操作，用变量e保存栈顶元素的值 ，则执行

    (  B ）。

     A．e= top->next; top->data=e;

     B．e=top->data; top=top->next;

     C．top=top->next; e=top->data;

     D．top=top->next; e=data;   

 9. 数据结构中，与所使用的计算机无关的是数据的(    A     ) 结构。

A.逻辑      B.存储      C.逻辑与存储      D.物理                

 10. 算法的时间复杂度与(   A )有关。

     A.  算法本身                B.  所使用的计算机

    C.  算法的程序设计          D.  数据结构

11．顺序表所具备的特点之一是（ A  ）。

  A．可以随机访问任一结点            B．不需要占用连续的存储空间     

  C．插入元素的操作不需要移动元素    D．删除元素的操作不需要移动元素

12．在一个单向链表中,在p所指结点之后插入一个s所指的结点时，可执行

s->next=p->next; 和（   D ）。 

   A．p= s;                  B． p->next=s->next;

C．p=s->next D． p->next=s;

13. 数据元素是数据的基本单位，它（   C   ）。

     A．只能有一个数据项组成      

     B．至少有二个数据项组成

     C．可以是一个数据项也可以由若干个数据项组成

     D．至少有一个数据项为指针类型                       

14. 一种逻辑结构在存储时  （      C）。

     A．只要存储数据元素间的关系     B．只能采用一种存储结构  

C．可采用不同的存储结构         D．只要存储数据元素的值   

15．设有头指针为head的非空的单向链表, 指针p指向其尾结点, 要使该单向链表成为单向循环链表,则可利用下述语句（C  ）。

       A．p =head;    B．p=NULL;   C．p->next =head; D．head=p;     

16.单向链表所具备的特点是(  C )。

A.可以随机访问任一结点         B.占用连续的存储空间

  C.插入删除不需要移动元素       D.可以通过某结点的指针域访问其前驱结点 

17. 在线性表的顺序结构中，以下说法正确的是（C  ）。

     A．逻辑上相邻的元素在物理位置上不一定相邻

     B．数据元素是不能随机访问的

     C．逻辑上相邻的元素在物理位置上也相邻

     D．进行数据元素的插入、删除效率较高                       

18.数据结构在计算机内存中的表示是指 ( B  ) 。 

     A．数据元素之间的关系        B．数据的存储结构  

     C．数据元素的类型            D．数据的逻辑结构

19.对链表, 以下叙述中正确的是（ A   ）。

   A．不能随机访问任一结点                 B．结点占用的存储空间是连续的 

   C．插入删除元素的操作一定要要移动结点   D．可以通过下标对链表进行直接访问 

   20.下面关于线性表的叙述中,错误的是( B   )。

     A . 线性表采用顺序存储,必须占用一片连续的存储空间。

     B.  线性表采用顺序存储,进行插入和删除操作,不需要进行数据元素间的移动。

     C.  线性表采用链式存储，不必占用连续的存储空间。

     D.  线性表采用链式存储，进行插入删除操作，不需要移动元素

21 .设有一个长度为35的顺序表，要在第5个元素之前插入1个元素（也就是插入元素

      作为新表的第5个元素），则移动元素个数为（B    ）。

      A．30        B．31        C. 5      D．6    

  22 .设有一个长度为18的顺序表，要在第5个元素之前插入1个元素（也就是插入元素作为新表的第5个元素），则移动元素个数为（B    ）。

      A．15        B．14       C. 5     D．6     

23．设有一个长度为40的顺序表，要删除第10个元素(下标从1开始)需移动元素的个数为（  C  ）。

      A．11      B．10       C．30      D．31       

 24．设有一个长度为25的顺序表，要删除第10个元素(下标从1开始)需移动元素的个数为（  C  ）。

     A．10       B．17       C．15      D．16  

25．设有一个25阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素a7,5在一维数组B中的下标是（ C  ）。

A．25            B．24            C．26            D．27      

  26．设有一个18阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素a10,8在一维数组B中的下标是（ D   ）。

A．62,             B．63           C．51            D．53     

27．线性表在存储后,如果相关操作中有要求:利用已知的指向某结点的指针或序号,访问

该结点的前驱结点，则采用（A   ）的存储方式是不可行的。

  A．单向链表    B．双向链表   C．单向循环链表  D．顺序表  

28．在一个尾指针为rear的不带头结点的单循环链表中,插入一个s所指的结点,并作为第一个结点，可执行snext=rearnext ;和（  D  ）。

      A． rearnext= snext;           B． rear =snext; 

  C． rear=s;                         D． rearnext=s;    

29．在一棵二叉树中，若编号为i的结点存在左孩子,i结点的左孩子的顺序编号为（ B  ）。

       A．i/2.0                B．2*i        C．2*i+1           D．i+2   

30．在一棵二叉树中，若编号为15的结点是其双亲结点的右孩子，则双亲结点的顺序编号为（D  ）。

       A．30      B．8        C．31           D．7             

二、填空题

1. 广义表( ( b,a,c) ,c ,d , f , e , ( (i , j ) , k ) ) 的长度是___ 6_____。   

2. 结构中的元素之间存在一对多的关系是___树形_____结构。

3. 数据结构中，数据元素之间的抽象关系称为____逻辑____结构。               

4. 结构中的元素之间存在多对多的关系是 ___图状_____结构 。

5. 栈的操作特点是后进___先出_____ 。                            

6. 循环队列的最大存储空间为MaxSize ,若队头指针front，队尾指针rear，采用少用一个

  存储空间以有效地判断栈空或栈满，队空的判定条件为___ rear==front为真_____ 。

7. 广义表(( b,a,c) ,c ,d , f , e ,( (i , j ) , k ) ) 的表头是____（b,a,c）____。 

8. 广义表( ( b,a,c) ,c ,d , f , e , ( (i , j ) , k ) ) 的长度是____ 6____。 

9. 设有一个长度为18的顺序表 ,  第8号元素到第18号元素依次存放的值为8,9,…,18.

   某人想要删除第8号元素，程序中他的做法是用语句for(i=18;i<=9;i--)a[i-1]=a[i];

   即从第18号元素开始, 直到第9号元素,每个元素依次向前(左)移动1个位置.事实上这

   样做是错误的.其结果新表中第9号元素的值为___ 18 _____。                                                                            

10．要求在n个数据元素中找值最大的元素，其基本操作为元素间的比较。算法的时间复杂

  度为____ O(n)___  。

11. 一棵二叉树,有1个2度结点,，2个1度结点，则该树共有 _ 5______个结点。

12．一棵有8个叶结点的二叉树，其1度结点的个数为3，则该树共有 ___ 18____个结点。

13．设有一棵深度为5的完全二叉树，该树共有21个结点,第5层上有   6    个结点。

 （根所在结点为第1层）                                                 

14.对于一棵具有n个结点的二叉树，其相应的链式存储结构有__ n+1______个指针域为空。 

 15．中序遍历____二叉排序树 ____树可得到一个有序序列。        

16. 对一组记录（5，8，9，2，12，7，56，44，39）进行直接插入排序(由小到大排序) ，当把第6个记录7插入有序表，为寻找插入位置需比较__ 4______次。  

17. 序列12,10,13,11,16,14,采用冒泡排序算法,经一趟冒泡后,序列的结果是____ 10，12，11，13，14，16____。

 （按升序排序）                            

18．设有一棵深度为6的完全二叉树，第6层上有3个结点，该树共有__ 34_____个结点。（根所在结点为第1层） 

19. 对16个元素的序列用冒泡排序法进行排序，共需要进行___ 15_____趟冒泡。  

20．一棵有16个叶结点的哈夫曼树，则该树共有___ 31____个结点。 

21. 一棵有16个叶结点的哈夫曼树，则该树共有__ 15_____个非叶结点。   

22.  20个元素进行冒泡法排序，通常第6趟冒泡要进行__ _ 14___次元素间的比较。 

23. 在对一组记录（40，24，82，9，1，78，46，31，69）进行直接插入排序(由小到大排

   序) ，当把第7个记录46插入到有序表时，为寻找插入位置需比较____3____次。

24．对稀疏矩阵进行压缩存储,可采用三元组表，一个6行7列的稀疏矩阵A共有38个零

    元素，其相应的三元组表共有____4___个元素。                                        

三、综合题

1．

设有序表为(5, 8, 14, 15, 33, 51, 61, 73, 81, 82, 93) ,元素的序号依次为

 1,2,3,……，11.

  （1）画出对上述查找表进行折半查找所对应的判定树（树中结点可用序号表示）

  （2）说明成功查找到元素33需要经过多少次比较？

   (3) 在等概率条件下, 给出成功查找的平均查找长度

（1）图4

                    51

             14            81

        5        15      61       82

           8        33       73          93

      (2)  4次 

       (3)  ( 1+2*2+3*4+4*4)/11=33/11=3

2.

设数据集合a={1,5,8,3,10,7,13,9}

（1）依次取a中各数据，构造一棵二叉排序树。

（2）对该二叉树进行查找，成功查找到7要进行多少次元素间的比较？

（3）给出对该二叉树中序遍历的序列。

 (1) 图5

 (2)  4次    

 (3) 中序遍历 1, 3 , 5 ,7 , 8 , 9 , 10 , 13

3．

(1)如图1所示,若从顶点a出发，首先经过c按图的深度优先搜索法进行遍历，给出可能得到的一种顶点序列。  

(1) acdbfeh

  (2) 1523 或   152634 或  156234

  (2)设有向图如图2所示下，写出首先删除顶点1的1种拓扑序列

4．

设有序表为(30, 48, 58, 70, 78, 79, 90) ,元素的序号依次为 1,2,3,……，7.

（1） 画出对上述查找表进行折半查找所对应的判定树（树中结点用序号表示）

（2） 给出有序表中经3次比较成功查找到的所有元素

(3)  说明不成功查找元素59需要经过多少次比较？

（1）图6

                               70

                      48            79

                30         58      78      90

(2)  30  58  78  90 

  (3)  3次

5.

(1) 设数据集合a={7,4,9,8,6,5,3},依次取a中各数据，构造一棵二叉排序树。

    (2)对该二叉树进行查找，成功查找到5要进行多少次元素间的比较？

(3) 给出对上述二叉排序树进行中序遍历的序列

   (1) 图7

(2)  4

(3)  3,4,,5,6,7,8,9  

6．

(1)  如图3所示，若从顶点a出发，首先经过c按广度优先搜索法进行遍历，给出可能得

     到的一种顶点序列。

（2）同图3所示, 若从顶点h出发，按深度优先搜索法进行遍历，给出可能得到的2种顶点

 序列。

   (3) 

  一组记录的关键字序列为（75，63，95，80，53，45，38，20），利用堆排序的方法建立小根堆(堆顶元素是最小元素）,给出按筛选法建立的的初始堆。

         (1)  acefdh

      (2)  hdeacf   hdfcae

     （3）

   20, 53，38，63，75，45，95，80

四、程序填空题

1．以下函数在a[0]到a[n-1]中，用折半查找算法查找关键字等于k的记录，查找成功返回该记录的下标，失败时返回-1，完成程序中的空格

typedef   struct

{   int  key;

……

}NODE;

int Binary_Search(NODE a[],int n, int k)

     {

         int low,mid,high;

         low=0;

         high=n-1;

         while(___(1)_____)                

         {

              mid=(low+high)/2;

              if(a[mid].key==k)

                  return __(2)______;                 

              else if(___(3)_____)         

                   low=mid+1;             

              else __(4)______;               

           }

           ___(5)_____;                         

        }

(1) low<=high

 (2) mid 

(3) a[mid].key < k

 (4) high=mid -1  

(5) return  -1

2．以下函数为直接选择排序算法，对a[1],a[2],…a[n]中的记录进行直接选择排序

  ，完成程序中的空格

typedef   struct

{   int  key;

……

    }NODE;

  void selsort(NODE a[ ],int n)

  {

     int i,j,k;

     NODE temp;

  for(i=1;i<= ___(1)___;i++)                 

     {    k=i;    

        for(j=i+1; ___(2)__; j++)            

         if(a[j].key           if(i!=k)                    

           {    temp=a[i];

            ___(4)____;                       

            ___(5)____;   

           }

      }

  }

(1) n-1

(2) j<=n

 (3) k=j

     (4) a[i]=a[k]

     (5) a[k]=temp

3.以下函数为链栈的进栈操作，x是要进栈的结点的数据域，top为栈顶指针

struct  node

{   ElemType  data;

    struct  node  *next;

     };

   struct node *top ;

    void Push(ElemType x)    

        {  struct node *p;

         p=(struct node*)malloc(___(1)___);   

p->data=x;

         __ (2)____;                                                          

         ___(3)___;                                  

       }

(1) sizeof(struct node)

(2) p next=top 

(3) top=p

4.以下函数为链队列的入队操作，x为要入队的结点的数据域的值，front、 

   rear分别是链队列的队头、队尾指针

struct  node

{   ElemType  data;

struct  node  *next;

};

struct  node  *front，*rear;

          void InQueue(ElemType x)

            { 

              struct node *p;

              p= (struct node*) ___(1)_____;        

p->data=x;

p->next=NULL;

              ___(2)_____;                   ;                      

              rear= ___(3)_____;                              

            }

(1) malloc(sizeof(struct node)) 

(2) rear->next=p;

 (3) rear=p;

综合练习二

一、单项选择题

  1. 对稀疏矩阵进行压缩存储,可采用三元组表，一个有10 行的稀疏矩阵A共有97个零元素，其相应的三元组表共有3个元素。该矩阵A有(   D    )列。

     A．8                         B．9 

     C．7                         D．10   

2 .单向链表所具备的特点是(  C   )。

A.可以随机访问任一结点         B.占用连续的存储空间

  C.插入删除不需要移动元素       D.可以通过某结点的指针域访问其前驱结点  

 3. 子串“acd”在主串 “abdcacdefac”中的位置是(    B  ) 。           

     A．3                         B．5 

     C．7                         D．1                           

4 .设有一个长度为18的顺序表，要在第6个元素之前插入一个元素（也就是插入元素作为新表的第6个元素），则移动元素个数为（  C  ）。

    A．12          B．5          C. 13          D．6        

5. 序列12,16,8,4按顺序依次进栈，按该栈的可能输出序列依次入队列，该队列的不可能输出序列是（ B   ）。 (进栈、出栈可以交替进行）。

    A．16,12,8,4          B．4,8,12,16 

   C．8,4,16,12          D．16,12,4,8                            

6．栈和队列的共同特点是（ A    ）。

    A．都是线性结构                      B．元素都可以随机进出

C．都是先进后出                      D．都是先进先出      

7. 在一个不带头结点的链队中，假设f和r分别为队头和队尾指针，对该队列进行出队

     操作,并把结点的值保存在变量e中,其运算为（  C  ）。

     A．e=f->data；r=r->next; B．e=f->data；r->next=r;

     C．e=f->data；f=f->next; D．e=f->data；f->next=f;

  8．元素1，3，5，7按顺序依次入队列，按该队列的出队序列进栈，该栈的可能输出序列是（  D  ）（进栈出栈可以交替进行）。

     A．7，5，1，3                B．7，3，1，5  

C．5，1，3，7                D．7，5，3，1 

9. 数据的逻辑结构在计算机内存中的表示是(  B   )。

     A.给相关变量分配存储单元

     B.数据的存储结构

     C.数据的逻辑结构

     D.算法的具体体现                             

 10．在一个不带头结点的链队中，假设f和r分别为队头和队尾指针，则对该队列进行出队操作中并把结点的值保存在变量e中,其运算为e=fdata；和（  C  ）。

    A．r=rnext;             B．rnext=r;

C．f=fnext;             D．fnext=f

 11. 以下说法正确的是(   B    )。

   A. 线性表的链式存储结构必须占用连续的存储空间                 

   B. 一种逻辑结构可以有不同的存储结构

  C．一种逻辑结构只能有唯一的存储结构       

D．线性表的顺序存储结构不必占用连续的存储空间                 

12．设有一个对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），B数组共有45个元素,则该矩阵是（ D   ）阶的对称矩阵。

A．15             B．11            C．10           D．9     

13．在一个单链表中要删除p所指结点的后继结点，可执行q=p->next; 和（  A ）。 

  A．p->next=q->next ; B．p=q->next;

C．p->next=q; D．p->next=q;

14. 下列是C语言中〝abcd321ABCD〞的子串的选项是（ A   ）。

   A. 〝21ABC〞                    B.〝abcABCD〞 

   C.  abcD                        D. 〝321a〞  

15. 在数据结构和算法中，与所使用的计算机有关的是 （  B    ）。

     A．数据元数间的抽象关系      B．数据的存储结构  

     C．算法的时间复杂度          D．数据的逻辑结构   

16. 字符串a1=〝BEIJING〞, a2 =〝BEF〞 , a3= 〝BEFANG〞,  a4=“BEFI〞最小的是（  B  ）.

A.  a1                          B.  a2

     C. a3                           D. a4     

17. 以下表中可以随机访问的是（ D ）。

     A．单向链表               B．双向链表     

     C．单向循环链表           D．顺序表                

18．一棵有20个结点采用链式存储的二叉树中，共有（   A ）个指针域为空。

     A．21              B．20            C．19           D．18  

19.头指针为head的不带头结点的单向链表为空的判定条件是逻辑表达式(    A )为真。

A. head= =NULL B. head->next= =NULL

C. head->next=NULL      D. head->next!= NULL

20．设一棵哈夫曼树共有18个叶结点，则该树有（  C  ）个非叶结点。

     A．18               B．19            C．17           D．16    

21 .设有一个长度为32的顺序表，要在第5个元素之前插入1个元素（也就是插入元素

     作为新表的第5个元素），需移动元素个数为（ B  ）。

     A．25        B．28       C. 5     D．6     

22．如图1所示的一个图，若从顶点g出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为（D   ）。

    A．gabecdf            B．gacfebd         C．gaebcfd       D．gaedfcb     

 图1

 23．设有一个长度为33的顺序表，要删除第10个元素(下标从1开始)需移动元素的个数

     为（ C   ）。

     A．11       B．10       C．23      D．14      

 24．线性表以（ B  ）方式存储，能进行折半查找。

     A．关键字有序的       B．关键字有序的顺序      C．链接      D．顺序

 25．设有一个28阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序 

     存储到一维数组B中（数组下标从1开始），则数组中第26号元素对应于矩阵中的元素是（   A ）。 

A．a7,5  ,             B．a7,6           C．a6,5            D．a7,4    

26．有一个长度为8的有序表，按折半查找对该表进行查找，在等概率情况下查找成功的平均比较次数为（ D  ）。

A．22/8              B．20/8             C．23/8         D．21/8   

27. 在一个不带头结点的单循环链表中，p、q分别指向表中第一个结点和尾结点，现要

    删除第一个结点，且p、q仍然分别指向新表中第一个结点和尾结点。可用的语句是

p=p->next;和（  D  ）。

    A．p=q->next; B．p->next=q ; C． q=p; D． q->next=p;

28. 排序算法中，从尚未排序序列中依次取出元素与已排序序列（初始为空）中的元素进行比较（要求比较次数尽量少），然后将其放入已排序序列的正确位置的方法是（A   ）。

    A．折半插入排序     B．直接插入排序    C．归并排序   D．选择排序   

29．在一棵二叉树中，若编号为16的结点是其双亲结点的左孩子，则他的双亲结点的顺序编号 为（ B  ）。

    A．7           B．8        C．32           D．33    

30．排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始为空）的一端的方法，称为（  C  ）排序。

    A．堆        B．冒泡       C．选择       D．快速          

二、填空题

1.数据的逻辑结构在计算机中的表示称为__物理 (存储)______结构。     

2.结构中的数据元素存在一对多的关系称为__树形______结构。

3.四类基本结构分别为____    集合 线性 树形 图状                         ___结构。        

4.栈的操作特点是____先进后出__________。

5.队列的操作特点是先进____先出____。                       

6.广义表的( a , (a ,b) , d , e ,( (i ,j ) ,k ) )深度是____ 3 ____。

7.广义表( (b,a,c) , c,d ,( e ,i ,j ,k ) )的表尾是___ (c,d,(e,i,j,k))_____。       

8.广义表( (a ,b) , d , e ,( (i ,j ) ,k ) )的长度是______ 4 __。 

9.设有一个长度为20的顺序表 , 第8号元素到第20号元素依次存放的值为8,9,…,20。

   某人想要在第8号元素前插入1个元素7（也就是插入元素作为新表的第8个元素），程

   序中他的做法是用语句for(i=8;i<=20;i++)a[i+1]=a[i];a[8]=7;即从第8号元素开始,

   直到第20号元素,每个元素依次向后(右）移动1个位置,然后把7存放在第8号位置。

   事实上这样做是错误的.其结果是新表中第20号元素的值为___ 8_____。         

10. 设顺序队列的类型为typedef struct

                       { ElemType  data[MaxSise];

                        int  front,rear;

}Squeue;

Squeue  *sq; 

 sq为指向顺序队列的指针变量，要进行元素的出队操作，并把元素赋给边量x, 按教科书约定,可用语句x=sq->data[sq->front];和__ sq->fronf++;______ 。  

11．设有一棵有38个结点的完全二叉树，该树共有_____ 6 ____层。（根所在结点为第1层）

12. 设顺序队列的类型为typedef struct

                    { ElemType  data[MaxSise];

                      int  front,rear;

}Squeue;

Squeue  *sq; 

 sq为指向顺序队列的指针变量，要进行新元素x的入队操作，按教课书约定,可用语句

sq->data[sq->rear]=x;和___ sq->rear++;_____。 

13． 一棵有18个结点的二叉树，其2度结点数的个数为8，则该树共有  ___ 1____个1度结点。                                                                                                              

14. 序列14,12,15,13,18,16,采用冒泡排序算法,经一趟冒泡后,序列的结果是___ 12,14,13,15,16,18_____。（由小到大排序）

15. 对一组记录（1，3，9，2，12，7，5，4，6）进行直接插入排序(由小到大排序) ，当把第6个记录7插入有序表，为寻找插入位置需比较_____ 3___次。     

16. 数据结构中, _____数据元素___ 之间的抽象关系称为逻辑结构。 

17. 序列5,3,8,4,7,6,采用冒泡排序算法,经一趟冒泡后,序列的结果是___ 3,5,4,7,6,8_____。

(按升序排序)                                       

18. 循环队列中，设front和rear分别为队头和队尾指针，(最多元素为MaxSize,),判断循环队列为空的条件为____ front= =rear____为真。

19. 广义表(b,a , (c ,b) , f , e ,( (i ,j ) ,k ) )的长度是____ 6____ 。            

20. 排序算法中，从尚未排序序列中依次取出元素与已排序序列（初始为空）中的元素进行比较（要求比较次数尽量少），然后将其放入已排序序列的正确位置的方法是  折半插入排序       。

21． 一棵有18个叶结点的哈夫曼树，则该树共有____ 17___个非叶结点。 

22. 对稀疏矩阵进行压缩存储,可采用三元组表,矩阵元素a3,4 对应的三元组为__ (3,4, a3,4)_____ 。

23．对稀疏矩阵进行压缩存储,可采用三元组表，一个8行7列的稀疏矩阵A共有51个零元 

    素，其相应的三元组表共有____ 5___个元素                        

24．在双向链表中，要删除p所指的结点，其中所用的一条语句（p->next）->prior=p->prior; 

    的功能是：使P所指结点的直接后继的左指针指向___ P所指结点的直接前驱_____。

三、综合题

1.

设数据集合a={6,17,10,13,8,15,12,18,14}

 （1）依次取a中各数据，构造一棵二叉排序树。

 （2）给出对该二叉树中序遍历的序列

 （3）对该二叉树进行查找，成功查找到14要进行多少次元素间的比较？

图2

(2)中序遍历 6 , 8 ,10,12 , 13 , 14 , 15 , 17 , 18

 (3) 6次

2.设数据集合a={62,74,30,15,56,48}

（1）依次取a中各数据，构造一棵二叉排序树。

（2）对该二叉树进行查找，不成功查找有多少种可能？画出不成功查找树的示意图。

（3）不成功查找的平均查找长度是多少?

（4）为了成功查找到48需要进行多少次元素间的比较?

（5）给出对该二叉树后序遍历的序列。

(1)图3                        

  (2)图4  7种可能               

(3)(2*2+3*3+4*2)/7=21/7          

(4)4次                          

(5)15,48,56,30,74,62  

3．

设有序表为(2, 5, 11, 12, 30, 48, 58) ,元素的序号依次为 1,2,3,……，7.

  （1）画出对上述查找表进行折半查找所对应的判定树（树中结点用序号表示）

 （2）说明成功查找到元素11需要经过多少次比较？

  (3) 在等概率条件下, 给出成功查找的平均查找长度 

（1）图5

 (2)  3次 

 (3)  ( 1+2*2+3*4)/7=17/7

4．设有序表为（3，9，15，26，38，41，53，74，81，96，97，99），元素的  

   序号依 次为1,2,……,12。

  （1）说出有哪几个元素需要经过3次元素间的比较才能成功查到。

 （2）画出对上述有序表进行折半查找所对应的判定树（树结点用序号表示）。

 （3）设查找5号元素(38)，需要进行多少次元素间的比较才能确定不能查到, 依次和

      哪些元素进行了比较？（要求写出具体元素）。

 （4）给出后序遍历该二叉树的序列。

  (5)  给出中序遍历该二叉树的序列。    

(1) 3, 26, 53, 97

 (2)图7

 (3)4次41,15,26,38

 (4) 2(9),1(3),5(38),4(26),3(15),8(74),7(53),10(96),12(99),11(97),9(81),6(41)    

（5）1( 3）,2(9), 3(15),4(26),5(38),6(41),7(53),8(74),9(81),10(96),11(97),12(99)

5 .

(1)如图1所示，若从顶点a出发，首先经过顶点c按广度优先搜索法进行遍历，给出可能得到的一种顶点序列。

 (2) 如图1所示，给出从顶点h出发，首先经过顶点d和e按深度优先搜索法进行遍历，给出可能得到的一种顶点序列。

（3）一组记录的关键字序列为（80,57,41,39,46,47），利用堆排序的方法的方法建立小根堆(堆顶元素是最小元素）,给出按筛选法建立的的初始堆。

(1)  acefdbh

(2)  hdeacfb

（3）39 46 41 57 80 47

四、程序填空题

1．以下冒泡法程序对存放在a[1]，a[2]，……，a[n]中的序列进行冒泡排序完成程序中的

   空格部分，其中n是元素个数，程序按升序排列。

  void bsort (NODE  a[ ], int)

  {  NODE temp;

     int i,j,flag;

for( j=1; j<=n -1 ;    (1)      )      

     {    flag=0;

          for(i=1;  (2)       ;i++)    

if ( a[i].key>a[i+1].key)

  {  flag=1;

       (3)                 

    a[ i]=a[i+1];

       (4)        ;        

  }

      if(flag= =0)break;

  }

 } 

程序中flag的功能是  (5)         

      1.

   (1) j++

(2) i<=n-j

 (3) temp=a[i];

     (4) a[i+1]=temp;

 (5) 判断某一趟排序中是否有元素交换             

2.学生信息存放在结构数组中，每个数组元素存放一个学生的信息，下标从0到n-1。数组元素按学号num由小到大有序排列，以下函数在a[0]到a[n-1]中，用折半查找算法查找关键字num等于k的记录，查找成功返回该记录的下标(数组元素的下标)。失败时返回-1，完成程序中的空格。

     typedef   struct

{  

    char sex;

    int  num;

……

    }NODE;

int Binary_Search(NODE a[],int n, int k)

     {

         int low,mid,high;

         low=0;

         high=n-1;

         while(___(1)_____)

         {

              mid=(low+high)/2;

              if(a[mid].num = =k)

                  return __(2)______;              

              else if(___(3)_____)

                   low=mid+1;             

              else __(4)______;             

           }

              return  -1 ;                       

        }

(1)low<=high

(2)mid       

(3)a[mid].num(4) high=mid-1;

3．以下函数为链栈的出栈操作，出栈结点的数据由x返回

struct  node

{   ElemType  data;

struct  node  *next;

};

ElemType Pop( )

        {  int x;                          

           if(top==___(1)_____)                

{                 

             printf("栈下溢错误！\n");

             exit(1);                       

           }                         

           x=___(2)_____;                                             

           top=___(3)_____;                   

           return x;                      

        }           

(1) NULL

(2) top->data

(3) top->next

4．以下函数是二叉排序树的查找算法，若二叉树为空，则返回根结点的指针，否则，返回值是指向树结点的结构指针p（查找成功p指向查找到的树结点，不成功，则p指向为NULL），完成程序中的空格。

struct  bnode 

{   int  key;

    struct   bnode *left;

struct   bnode *right;

} ;

    typedef struct bnode Bnode

       Bnode *BSearch(Bnode  *bt, int k) /* bt用于接收二叉排序树

                                            的根结点的指针，k用以

                                            接收要查找的关键字*/                                                                               

         {   Bnode *p;

             if(bt = = NULL)

              return (bt);

              ___(1)_____

while(p->key  !=    __(2)___)          

{ if(kkey)              

                  ___(3)_____;

                 else ___(4)_____;          

                 if(p==NULL) break;        

              }

             return p ;

         }

 (1) p=bt;       

(2)  k 

(3)p=p->left

(4)p=p->right

综合练习一答案

一、单项选择题

1．C  2．C  3．A   4．D  5．A   6．A  7．B   8．B   9．A   10．A   11．A  12．D   13．C   14．C    15．C  16．C   17．C   18．B   19．A   20．B  21．B   22．B    23．C   24．C   25．C    26．D  27．A   28．D  29．B   30．D

二、填空题

1. 6

2. 树形

3. 逻辑

4. 图状

5. 先出

6. rear==front为真

7.（b,a,c）

8. 6

9. 18 

10.O(n)

11. 5

12.18

13. 6 

14. n+1

15. 二叉排序树 

16., 4

17. 10，12，11，13，14，16

18.34

19. 15

20.31

21. 15

22. 14

23. 3 

24. 4

三、综合应用题

1．

（1）图4

                    51

             14            81

        5        15      61       82

           8        33       73          93

      (2)  4次 

       (3)  ( 1+2*2+3*4+4*4)/11=33/11=3

  2. 

 (1) 图5

 (2)  4次    

 (3) 中序遍历 1, 3 , 5 ,7 , 8 , 9 , 10 , 13

3  

 (1) acdbfeh

  (2) 1523 或   152634 或  156234

4．

（1）图6

                               70

                      48            79

                30         58      78      90

(2)  30  58  78  90 

  (3)  3次

5  

(1) 图7

(2)  4

(3)  3,4,,5,6,7,8,9  

6．  

(1)  acefdh

      (2)  hdeacf   hdfcae

     （3）

   20, 53，38，63，75，45，95，80

四、程序填空题

1.

(1) low<=high

 (2) mid 

(3) a[mid].key < k

 (4) high=mid -1  

(5) return  -1 

2.

 (1) n-1

 (2) j<=n

 (3) k=j

     (4) a[i]=a[k]

     (5) a[k]=temp

3.            

(1) sizeof(struct node)

(2) pnext=top 

(3) top=p

4.            

(1) malloc(sizeof(struct node)) 

 (2) rear->next=p;

 (3) rear=p;

综合练习二答案

 一、单项选择题

1．D  2．C  3．B   4．C  5．B   6．A  7．C  8．D  9．B   10．C  11．B   12．D 13．A   14．A  15．B  16．B  17．D   18．A    19.A   20．C  21．B  22．D  23．C 24．B   25．A  26．D  27．D   28．A 29．B   30．C

二、填空题

1. 物理 (存储)

2．树形

3. 集合 线性 树形 图状

4．先进后出

5. 先出

6．3 

7. (c,d,(e,i,j,k))

8．4

9. 8

10．sq->fronf++;

11. 6 

12．sq->rear++;

13. 1

14．12,14,13,15,16,18

15. 3

16．数据元素

17. 3,5,4,7,6,8

18．front= =rear

19. 6

20．折半插入排序

21. 17

22．(3,4, a3,4)

23. 5

24．P所指结点的直接前驱

三、综合应用题

1. 

(1)图2

(2)中序遍历 6 , 8 ,10,12 , 13 , 14 , 15 , 17 , 18

 (3) 6次

2 

  (1)图3                        

  (2)图4  7种可能               

(3)(2*2+3*3+4*2)/7=21/7          

(4)4次                          

(5)15,48,56,30,74,62               

3 .

（1）图5

 (2)  3次 

 (3)  ( 1+2*2+3*4)/7=17/7

4.

(1) 3, 26, 53, 97

 (2)图7

 (3)4次41,15,26,38

 (4) 2(9),1(3),5(38),4(26),3(15),8(74),7(53),10(96),12(99),11(97),9(81),6(41)    

（5）1( 3）,2(9), 3(15),4(26),5(38),6(41),7(53),8(74),9(81),10(96),11(97),12(99)

图7

5. 

(1)  acefdbh

(2)  hdeacfb

（3）39 46 41 57 80 47

四、程序填空题

1.

   (1) j++

   (2) i<=n-j

 (3) temp=a[i];

     (4) a[i+1]=temp;

 (5) 判断某一趟排序中是否有元素交换 

2. 

(1)low<=high

(2)mid       

(3)a[mid].num(4) high=mid-1;

3.           

 (1) NULL

 (2) top->data 

    (3) top->next

4． 

(1) p=bt;       

(2)  k 

(3)p=p->left

(4)p=p->right