数据结构习题集

目录

第一章 绪论

一 选择题。 

二 填空题。

第二章．线性表

一 选择题。

二 填空题。

第三章．栈、队列

一 选择题。

二 填空题。

第六章．树与二叉树

一 选择题。

二 填空题。

三 简答题。

第七章．图

一 选择题。

二 填空题。

三 简答题。

第九章．查找

一 选择题。

二 填空题。

三 应用题。

第十章．排序

一 选择题。

---

第一章 绪论

一 选择题。 

1.下列说法中不正确的是（D）

A. 数据元素是数据的基本单位

B. 数据项是数据中不可分割的最小可标识单位

C. 数据可由若干个数据元素构成

D. 数据项可由若干个数据元素构成

2.在链式存储结构中，一个存储结点通常用于存储一个（B）

A. 数据项         B. 数据元素

C. 数据结构     D. 数据类型

3.数据运算（A）

A. 其执行效率与采用何种存储结构有关

B. 是根据存储结构来定义的

C. 有算术运算和关系运算两大类

D. 必须用程序设计语言来描述

4.数据结构在计算机内存中的表示是指（A）

A. 数据的存储结构

B. 数据结构

C. 数据的逻辑结构

D. 数据元素之间的关系

5.在数据结构中，与所使用的计算机无关的是（A）

A. 逻辑结构                   B. 存储结构

C. 逻辑结构和存储结构 D. 物理结构

6.数据采用链式存储结构时要求（D）

A. 每个结点占用一片连续的存储区域

B. 所有结点占用一片连续的存储区域

C. 结点的最后一个字段是指针类型

D. 每个结点有多少个后继就设多少个指针域

7.以下（B）不是算法的基本特性。

A. 可行性

B. 长度有限

C. 在确定的时间内完成

D. 确定性

8.在计算机中算法指的是解决某一问题的有限运算序列，它必须具备输人、输出、（B）

A. 可行性、可移植性和可扩充性

B. 可行性、有穷性和确定性

C. 确定性、有穷性和稳定性

D. 易读性、稳定性和确定性

9.下面关于算法的说法正确的是（B）

A. 算法最终必须由计算机程序实现

B. 一个算法所花的时间等于该算法中每条语句的执行时间之和

C. 算法的可行性是指指令不能有二义性

D. 以上几个都是错误的

10.算法的时间复杂度与（A）有关。

A. 问题规模 B. 计算机硬件性能

C. 编译程序质量 D. 程序设计语言

11.算法分析的主要任务之一是分析（D）

A. 算法是否具有较好的可读性

B. 算法中是否存在语法错误

C. 算法的功能是否符合设计要求

D. 算法的执行时间和问题规模之间的关系

12.算法分析的目的是（C）

A. 找出数据结构的合理性

B. 研究算法中的输人和输出关系

C. 分析算法的效率以求改进

D. 分析算法的易读性和文档性

13.某算法的时间复杂度为O()，表明该算法的（C）

A. 问题规模是 

B. 执行时间等于 

C. 执行时间与  成正比

D. 问题规模与  成正比

14.某算法的时间复杂度为O(n)，表示该算法的（B）

A. 执行时间是n

B. 执行时间与n呈现线性增长关系

C. 执行时间不受n的影响

D. 以上都不对

15.算法的空间复杂度是指（C）

A. 算法中输入数据所占用的存储空间的大小

B. 算法本身所占用的存储空间的大小

C. 算法中占用的所有存储空间的大小

D. 算法中需要的临时变量所占用存储空间的大小

16. 数据结构通常是研究数据的（A）及它们之间的相互联系。

       A.  存储和逻辑结构   B.  存储和抽象

       C.  顺序存储结构      D.  理想与逻辑

17．数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为（C）。

       A.  存储结构            B.  逻辑结构

       C.  顺序存储结构     D.  链式存储结构

18．线性结构是数据元素之间存在一种（D）。

  A.  一对多关系　　　 B.  多对多关系

  C.  多对一关系　　　 D.  一对一关系

19．图型结构中，每个结点（D）。

       A.  无直接前驱 

       B.  只有一个直接前驱和后继

       C.  只有一个直接前驱和个数不受限制的直接后继

       D.  有个数不受限制的直接前驱和后继 

20．除了考虑存储数据结构本身所占用的空间外，实现算法所用辅助空间的多少称为算法的（B）。

       A.  时间效率         B.  空间效率

       C.  硬件效率         D.  软件效率

21．设语句x++的时间是单位时间，则语句：

        for（i=1；i<=n；i++）

            x++；

   时间复杂程度为（B）。

        A.  O（1）      B.  O（n）       C.  O（  ）       D.  O（）

22．数据结构被形式的定义为（K，R），其中K是（B）的有限集合，R是K上的（D）有限集合。

     （1）  A.  算法    B.  数据元素    C.  数据操作    D.  逻辑结构

     （2)   A.  操作    B.  映象        C.  存储        D.  关系

23．在数据结构中,从逻辑上可以把数据结构分成(C)

        A.  动态结构和静态结构      B.  紧凑结构和非紧凑结构

        C.  线性结构和非线性结构    D.  内部结构和外部结构  

24．算法分析的目的是 （C）, 算法分析的两个主要方面 （A）。  

      (1) A.  找出数据结构的合理性           B.  研究算法中的输入与输出的关系

          C.  分析算法的效率以求改进         D.  分析算法的易懂性和文档性

      (2) A.  空间复杂性和时间复杂性         B.  正确性和简明性

          C.  可读性和文档性                 D.  数据复杂性和程序复杂性

25．线性表若采用链式存储结构时,要求内存中可用存储单元的地址(D)。

    A.  必须是连续的     B.  部分的地址必须是连续的

    C.  一定是不连续的   D.  连续或不连续都可以

二 填空题。

1.数据结构包括数据逻辑结构，数据的存储结构和数据的运算这三方面的内容。

2.数据结构按逻辑结构可分为两大类，它们分别是线性结构和非线性结构。

3.数据的存储结构可用四种基本的存储方法表示，它们分别是顺序，链式，索引和散列。

4.数据的运算最常用的有五种，它们分别是插入，删除，修改，查找和排序。

5.线性结构反映结点间的逻辑关系是一对一的，非线形结构反映结点间的逻辑关系是一对多或多对多的。

6. 一个算法的效率可分为时间效率和空间效率。

7. 在树型结构中，树根结点没有前驱结点，其余每个结点有且只有一个前驱结点；叶子结点没有后续结点,其余每个结点的后续结点可以任意多个。

8.在图形结构中, 每个结点的前驱结点数和后继结点数可以任意多个

9.线性结构中元素之间存在一对一关系,树形结构中元素之间存在一对多关系,图形结构中元素之间存在多对多关系。

10．算法的五个特性是有穷性，确定性，可行性，输入，输出。    

11．下面程序段的时间复杂度是O(${\color{Red} n^{2}}$)。

        for (i=0;  i<n;  i++)

          for(j=0; j<n; j++)

           A[i][j] =0;

12．下面程序段的时间复杂度是O(${\color{Red} n^{2}}$)。 

     s=0；

     for (i=0；i<n；i++)

          for (j=0；j<n；j++)

            s+=b[i][j]；

          sum=s；

13．下面程序段的时间复杂度是O(log3n)。

       i=1；

       while （i<=n）

         i=i*3；

第二章．线性表

一 选择题。

1. 线性表是(A)

A. 一个有限序列，可以为空

B. 一个有限序列，不可以为空

C. 一个无限序列，可以为空

D. 一个无限序列,不可以为空

2. 在一个长度为n的顺序表中向第i个元素(1≤i≤n+1)之前插入一个新元素时需要向后移动(B)个元素。

A.  n-i     B.  n-i+1

C.  n-i- 1 D.  i

3. 一个顺序表所占用存储空间的大小与(D)无关。

A. 顺序表的长度

B. 顺序表中元素的数据类型

C. 顺序表中元素各数据项的数据类型

D. 顺序表中各元素的存放次序

4. 顺序表具有随机存取特性指的是(C)

A. 查找值为x的元素与顺序表中元素的个数n无关

B. 查找值为x的元素与顺序表中元素的个数n有关

C. 查找序号为i的元素与顺序表中元素的个数n无关

D. 查找序号为i的元素与顺序表中元素的个数n有关

5. 顺序表和链表相比存储密度较大，这是因为(B)

A. 顺序表的存储空间是预先分配的

B. 顺序表不需要增加指针来表示元素之间的逻辑关系

C. 链表的所有结点是连续的

D. 顺序表的存储空间是不连续的

6. 链表不具有的特点是(A)

A. 可随机访问任一元素

B. 插入、删除不需要移动元素

C. 不必事先估计存储空间

D. 所需空间与线性表长度成正比

7.当线性表采用链式存储结构时，各结点之间的地址(D)

A. 必须是连续的

B. 一定是不连续的

C. 部分地址必须是连续的

D. 连续与否均可以

8.在线性表的下列存储结构中，读取指定序号的元素所花费时间最少的是(D)

A. 单链表 B. 双链表

C. 循环链表     D. 顺序表

9.若线性表最常用的运算是存取第i个元素及其前驱元素值，则采用(D)存储方式节省时间。

A. 单链表 B. 双链表

C. 循环单链表 D. 顺序表

10.设某个线性表有n个元素，在以下运算中，(A)在顺序表上实现比在链表上实现效率更高。

A. 输出第i(1≤i≤n)个元素值

B. 交换第1个元素与第2个元素的值

C. 顺序输出所有n个元素的值

D. 求第1个值为x的元素的逻辑序号

11.不带头结点的单链表head为空的判断条件是(A)。

       A.   head = NULL          B.   headànext =NULL

       C.   headànext = head    D.   head ! =  head

12.带头结点的单链表head为空的判断条件是(B)。

       A.   head = NULL           B.   headànext =NULL

       C.   headànext = head     D.   head ! =  NULL

13. 为保证带头结点的循环单链表head不空，其尾结点（由p所指向）应满足（C）。

       A.   pànext =NULL         B.   p = NULL

       C.   pànext = head        D.   p = head

14. 在循环双链表的p所指结点之后插入s所指结点的操作是(D)。

       A.   pàright =s；                 B.  pàright =s；

           sàleft = p；                     pàrightàleft = s；

           pàrightàleft = s；              sàleft = p；

           sàright = pàright；             sàright = pàright；

       C． sàleft = p；              D.  sàleft = p；

           sàright = pàright；             sàright = pàright；

       pàright = s；                    pàrightàleft = s；

       pàrightàleft = s；              pàright = s；

15.在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点则执行(C)。 

   A． sà next = pà next；pà next = s；

   B． pà next = sà next；  sà next = p；

   C． qà next = s；  sànext =p；

   D． pànext =s； sànext=q；

16.在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行(B)。

   A． sànext =p；  pànext=s；        B． sànext =pànext；  pànext =s；

   C． sànext =pànext；  p=s；        D.   pànext =s；   sànext =p；

17.在一个单链表中,若删除p所指结点的后续结点,则执行(A)。

   A.  pànext=pànextànext；          B.  p=pànext； pànext=pànextànext；

   C.  pànext=pànext；                D.  p=pànextànext；

18.下面给出的算法段是要把一个q所指新结点作为非空双向链表中的p所指结点的前驱结点插入到该双链表中,能正确完成要求的算法段是(C)。

   A.  qàrlink=p；                       B.   pàllink=q；

      qàllink=pàllink；                    qàrlink=p；

      pàllink=q；                           pàllinkàrlink=q；

      pàllinkàrlink=q；                    qàllink=pàllink；

       C.  qàllink=pàllink ；               D.   以上都不对

      qàrlink=p；

      pàllinkàrlink=q；

      pàllink=q；

 19. 从一个具有n各结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较(D) 个结点。    

   A.  n      B.  n/2       C. （n-1）/2      D. （n+1）/2

 20．在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（B）。

   A.  O（1）     B.   O（n）     C.   O（）     D.  O（）

 21．给定有n个元素向量，建立一个有序单链表的时间复杂度（C）。

   A.  O（1）     B.  O（n）      C.   O（）     D.  O（）

22. 用单链表方式存储的线性表，存储每个结点需要两个域，一个是数据域，另一个是(B)。

    A.  当前结点所在地址域　          B.  指针域

       C.  空指针域　                    D.  空闲域

 23．在具有n个结点的单链表中，实现（D）的操作，其算法的时间复杂度都是O（n）。  

       A.  遍历链表和求链表的第 I 个结点     B.  在地址为p 的结点之后插入一个结点

       C.  删除开始结点                      D.  删除地址为p的结点的后继结点

 24. 单链表的存储密度（C）。

       A.  大于１　      B.  等于１　   C.  小于１    D.  不能确定

 25.已知一个顺序存储的线性表，设每个结点需占m 个存储单元，若第一个结点的地址为d1，则第i个结点的地址为（A）。　

•     A.  d1+(i-1)*m    B.  d1+i*m    C.  d1-i*m     D.  d1+(i+1)*m

 26. 在n 个结点的顺序表中，算法的时间复杂度是 O(1)的操作是（A）。

    A.  访问第i个结点（1<=i<=n）和求第i个结点的直接前趋（2<=i<=n）

•     B.  在第i 个结点后插入一个新结点(1<=i<=n)
•     C.  删除第i 个结点(1<=i<=n)
•     D.  将n 个结点从小到大排序

27.在单链表中删除p所指结点的后继结点，该算法的时间复杂度是(A)

A. O(1) B.  O() C.  O() D.  O(n)

28.与单链表相比，双链表的优点是(D)

A. 插入、删除操作更简单

B. 可以进行随机访问

C. 可以省略表头指针或表尾指针

D. 访问前后相邻结点更方便

29.在长度为n(n≥1)的双链表L中,在p所指结点之前插人一个新结点的时间复杂度为(A)

A.O(1) B.  O(n) C.  O() D.  O() 

30.在长度为n(n≥1)的双链表L中，删除尾结点的时间复杂度为(B)

A. O(1) B.  O(n) C.  O() D.  O() 

31.在长度为n(n≥1)的双链表L中，删除p所指结点的时间复杂度为(A)

A. O(1) B.  O(n) C.  O() D.  O() 

32．链式存储的存储结构所占存储空间（A）。

  A.  分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针

  B.  只有一部分，存放结点值

  C.  只有一部分，存储表示结点间关系的指针

  D.  分两部分，一部分存放结点值，另一部分存放结点所占单元数

33.某个向量第一个元素的存储地址是100，每个元素的长度是2，则第5个元素的地址是(B)。

•       A．110     B．108    C．100    D．120

二 填空题。

1. 单链表是线性表的链接存储表示。

2. 可以使用双链表表示树形结构。

3. 在双链表中，每个结点有两个指针域，一个指向后续结点，另一个指向前驱结点。

4. 在一个单链表中的p所指结点之前插入一个s 所指结点时，可执行如下操作：

      （1）sànext =p->next；

      （2）pànext =s；

      （3）t=pàdata；

      （4）pàdata=s->data；

      （5）sàdata=t；

5. 在一个单链表中删除p所指结点时，应执行以下操作：

       q=pànext；

       pàdata=qàdata；

       pànext=q->next；

       free (q)；

6. 在一个单链表中p所指结点之后插入一个s 所指结点时，应执行sànext =p->next和pànext =s操作。

1. 对于一个具有n个结点的单链表，在已知p所指结点后插入一个新结点的时间复杂度是O(1)；在给定值为x的结点后插入一个新结点的时间复杂度是O(N)。
2. 按顺序存储方法存储的线性表称为顺序表，按链式存储的线性表称为链表。
3. 顺序表相对于链表的优点有节省存储和随机存取。

10. 链表相对于顺序表的优点有插入和删除操作方便。

11. n个结点的顺序表中插入一个结点需平均移动n/2个结点，具体的移动次数取决于位置与表长。

12. 在n个结点的顺序表中删除一个结点需平均移动(n-1)/2，具体的移动次数取决于各待删除元素的位置及其被删除概率。

13. 在顺序表中访问任意一个结点的时间复杂度均为O(1)，因此，顺序表也称为随机存取的数据结构。   

14. 在n个结点的单链表中要删除已知结点*p，需找到它的直接前驱结点的地址，其时间复杂度为O(n)。

15. 在双链表中要删除已知结点*p, 其时间复杂度为O(1)。

16.在单链表中要在已知结点*p之前插入一新结点，仍需找到*p的直接前驱结点的地址,其时间复杂度为O(n)；而在双链表中，完成同样操作其时间复杂度为O(1)。

17.在循环链表中，可根据任意结点的地址遍历整个链表，而单链表中需知道头指针才能遍历整个链表。

第三章．栈、队列

一 选择题。

1．向一个栈顶指针为HS的带头结点链栈中插入一个s 所指结点时，则执行（C）。

   A.  HSànext =s；              B.  sànext=HSànext； HSànext=s；

       C.  sànext=HS； HS=s；        D.  sànext=HS； HS=HSànext；

 2．从一个栈顶指针为HS的不带头结点的链栈中删除一个结点时，用x保存被删除结点的值，则执行（D）。

   A.  x=HS；HS=HSànext；           B.  x=HSàdata；

       C.  HS=HSànext；  x=HSàdata；   D.  x=HSàdata； HS=HSànext；

 3．在一个链队中，假设f和r 分别为队首和队尾指针，则插入s所指结点的运算是（B）。

   A.  fànext=s；f=s；              B.  rànext=s；r=s；

   C.  sànext=r；r=s；              D.  sànext=f；f=s；

 4．在一个链队中，假设f和r分别为队首和队尾指针，则删除一个结点的运算时（C）。

   A.  r= fànext；                  B.  r= rànext；

   C.  f= fànext；                  D.  f= rànext；

5．在栈中存取数据的原则是（）。//先进后出

       A．先进先出         B．后进先出      

       C．后进后出         D．随意进出

6．在队列中存取数据的原则是（A）。

       A．先进先出         B．后进先出

       C．先进后出         D．随意进出

7．在栈中，出栈操作的时间复杂度为（A）。

       A．O（1）    B．O（log2n）   C． O（n）   D．O（n２） 

8．一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是(C)。

•     A．edcba   B．decba   C．dceab    D．abcde

9. 若已知一个栈的入栈序列是1,2,3,……， n，其输出序列是p1,p2,p3……,pn,若p1=n，  

•    则pi为 (C)。
•     A．i       B．n-i     C．n-i+1    D．不确定

10．栈结构通常采用的两种存储结构是（A）。

1.  ．顺序存储结构和链式存储结构       B．散列方式和索引方式

•     C．链表存储结构和数组               D．线性存储结构和非线性存储结构

11. 判断一个栈ST（最多元素m0）为空的条件是（B）。

•     A．STàtop <>0           B．STàtop=0
•     C．STàtop<>m0           D．STàtop=m0

12.一个栈ST（最多元素m0）为满的条件是（D）。

•     A．STàtop !=0           B.  STàtop= =0
•     C．STàtop!=m0           D.  STàtop = =m0

13. 一个队列的入列序列是1,2,3,4,则队列的输出序列是(B)。

•     A．4,3,2,1       B．1,2,3,4       C．1,4,3,2       D．3,2,4,1

14. 判断一个队列QU（最多元素为m0)为空的条件(D)。

•     A．QUàrear-QUàfront = =m0    B．QUàrear-QUàfront-1 = =m0
•     C．QUàfront = =Quàrear         D．QUàfront = =QUàrear+1

15. 判断一个队列QU（最多元素为m0）为满的条件(A)。

•     A．QUàrear-QUàfront = =m0    B．QUàrear-QUàfront-1 = =m0
•     C．QUàfront = =QUàrear       D．QUàfront = =QUàrear+1

16．循环队列用数组存放其元素值A[0，m-1]已知其头尾指针分别是front和rear，则当

    前队列中的元素个数是(A)。

•     A．(rear-front+m)%m              B．rear-front+1
•     C．rear-front­1                  D．rear-front

17. 栈和队列的共同特点是(D)。

•     A．都是先进后出                  B．都是先进先出
•     C．只允许在端点处插入和删除      D．没有共同点

18．在以下的叙述中,正确的是(B)。

1.  线性表的顺序存储结构优于链表存储结构  
2. 二维数组是其数据元素为线性表的线性表      

C.  栈的操作方式是先进先出

1.  队列的操作方式是先进后出

二 填空题。

1．在栈结构中，允许插入、删除的一端称为栈顶，另一端称为栈底。

2. 在有n个元素的栈中，进栈和退栈操作的时间复杂度为O(1)和O(1)。

3．在队列结构中，允许插入的一端称为队尾；允许删除的一端称为队头。

4．设长度为n的链队列用单循环链表表示，若只设头指针，则入队和出队操作的时间复杂度分别为O(n)和O(1)；若只设尾指针，则入队和出队操作的时间复杂度分别为O(1)和O(1)。

5．设循环向量有m个元素，循环向量中有一个循环队列。在循环队列中，设队头指针front 指向队头元素，队尾指针rear指向队尾元素后的一个空闲元素。

（1）在循环队列中，队空标志为front==rear；队满标志为front==(rear+1)%MAXQSIZE。

（2）当rear>=front时，队列长度为rear-front；当rear<front时，队列长度为rear+MAXQSIZE-front。      

6．向量，栈和队列都是线性结构，可以在向量的任何位置插入和删除元素；对于栈只能在栈顶插入和删除元素；对于队列只能在队尾插入元素和队头删除元素。

7.一个栈的输入序列是12345，则栈的输出序列是43521是不可能的。

8.在栈顶指针为HS的链栈中，判定栈空的条件是HS==NULL。

9.在HQ的链队中，判定只有一个结点的条件是HQ->front==HQ->rear。

第六章．树与二叉树

一 选择题。

1．结点前序为xyz的不同二叉树，那么它有（C）不同状态。

       A．3          B．4          C．5          D．6

2．某二叉树的后序遍历序列为dabec，中序遍历序列为debac，则前序序列遍历为（D）。

       A．acbed      B．decab      C．deabc      D．cedba

3．具有35 个结点的完全二叉树的深度为（B）。

       A．5          B．6          C．7          D．8

4．将一棵有100 个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为（A）。

       A．98         B．99         C．50         D．48

5．某二叉树的前序和后序序列正好相反，则该二叉树一定是（B）的二叉树。

       A．空或只有一个结点         B．高度等于其结点数

       C．任一结点无左孩子         D．任一结点无右孩子

6．二叉树在线索化后，仍不能有效求解的问题是（D）。

       A．前序线索二叉树中求前序后继        B．中序线索二叉树中求前中序后继

       C．中序线索二叉树中求中序前趋        D．后序线索二叉树中求后序后继 

7．判断线索二叉树中某结点p有左孩子的条件是（C）。

       A．p!=null   B．pàlchild!=null   C．pàltag=0    D．pàltag=1

8．一棵左右子树均不空的二叉树在后序线索化后，其中空指针域的个数为（B）。

       A．0         B．1          C．2          D．不确定

9．一棵左子树为空的二叉树在前序线索化后，其中空指针域的个数为（C）。

       A．0         B．1          C．2          D．不确定

10．如图所示的4棵二叉树中，（C）不是完全二叉树。

                      A                                   B                                 C                                       D

11．在线索化二叉树中，t所指结点没有左子树的充要条件是（B）。

        A.  tàleft=NULL                      B.  tàltag=1

        C.  tàltag=1且t->left=NULL          D.  以上都不对

12．二叉树按某种顺序线索化后，任一结点均有指向其前驱和后继的线索，这种说法（B）。

        A．正确                 B．错误

13．二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法（A）。

        A．正确                 B．错误

14．由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，这种说法（B）。

        A．正确                 B．错误

15．设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（B）。

        A．2h          B．2h-1         C．2h+1          D．h+1

16．某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是（D）。

        A．bdgcefha    B．gdbecfha     C．bdgaechf      D．gdbehfca

17．按照二叉树的定义，具有3个结点的二叉树有（C）种。

         A．3          B．4             C．5            D．6

18．树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把由树转化得到的二叉树叫做这棵树对应的二叉树。结论（A）是正确的。

         A．树的先根遍历序列与其对应的二叉树的先序遍历序列相同

         B．树的后根遍历序列与其对应的二叉树的后序遍历序列相同

         C．树的先根遍历序列与其对应的二叉树的中序遍历序列相同

         D．以上都不对

19．深度为5的二叉树至多有（C）个结点。

         A．16          B．32            C．31            D．10

20．在一非空二叉树的中序遍历序列中，根结点的右边（A）。

         A．只有右子树上的所有结点            B．只有右子树上的部分结点

         C．只有左子树上的部分结点            D．只有左子树上的所有结点

21．树最适合用来表示（C）。

         A．有序数据元素                      B．无序数据元素

         C．元素之间具有分支层次关系的数据    D．元素之间无联系的数据

22．任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（A）。

         A．不发生改变                        B．发生改变

         C．不能确定                          D．以上都不对

23．实现任意二叉树的后序遍历的非递归算法而不使用栈结构，最佳方案是二叉树采用（C）存储结构。

         A．二叉链表                          B．广义表存储结构

         C．三叉链表                          D．顺序存储结构

24．设n，m为一棵二叉树上的两个结点，在中序遍历时，n在m 前的条件是（C）。

        A．n 在m右方                  B．n是m祖先

        C．n在m左方                   D．n是m子孙

25．线索二叉树是一种（C）结构。

        A．逻辑           B．逻辑和存储      C．物理         D．线性

26．对于一棵满二叉树，m个树叶，n个结点，深度为h则（A）。

        A．n=h+m           B．2n=h+m      C．m=h-1         D．n=2h-1

二 填空题。

1．对于二叉树来说，第i层上最多有${\color{Red} 2^{i-1}}$个结点。

2．树中结点的最大层次称为树的深度。

3．由一棵二叉树的前序序列和中序遍历可唯一确定这棵二叉树。

4．高度为5的完全二叉树至少有16个结点。

5．一棵树转化成一棵二叉树至少有一种。

6．将一棵树转换成二叉树，二叉树根结点没有右子树。

7．一棵含有n个结点完全二叉树，它的高度 |${\color{Red} log_{2}n}$|+1  (|*|向下取整)。 

8．森林后根遍历序列正是相应二叉树的后序遍历序列，森林先根遍历正是相应二叉树的前序遍历序列。

9．含有n个结点二叉树用二叉链表示时，有n+1个空链域。

10．哈夫曼树是带权路径长度最短的二叉树。

11．有m个叶结点的哈夫曼树共有2m-1个结点。

12．前序为a，b，c且后序c，b，a的二叉树共有4棵。

13．已知完全二叉树的第8层有8个结点，则其叶子结点数是68。

14．已知完全二叉树的第7层有10个叶子结点，则整个二叉树的结点数最多是73个。        

15．已知二叉树有50个叶子结点，则二叉树的总结点数至少是99个。

16．深度为k的完全二叉树至少有${\color{Red} 2^{k-1}}$个结点。至多有${\color{Red} 2^{k}-1}$个结点，若按自上而下从左到右次序给结点编号（从1开始），则编号最小的叶子结点的编号是${\color{Red} 2^{k-2}+1}$。

17．在一棵二叉树中，度为零的结点的个数为n0，度为2的结点的个数为n2，则有n0=n2+1。        

18．一棵二叉树的第i(i≥1)层最多有${\color{Red} 2^{i-1}}$个结点；一棵有n(n>0)个结点的满二叉树共${\color{Red} 2^{log_{2}(n+1)-1}}$有个叶子和${\color{Red} 2^{log_{2}(n+1)-1}}$-1个非终端结点。

三 简答题。

1.已知权值：4，2，5，7，5。请画出相应的哈夫曼树并计算其带权路径长度WPL。

 

 WPL=(5+5)*2+(2+4)*3+7*2=52

2．分别画出满足下列条件的所有二叉树：

  （1）前序序列和中序序列均为ABCDE；

（2）前序序列为ABCDE，并且与其对应的二叉树高度为5。

 一共有十六种

3.假设一段正文由字符集{a,b,c,d,e,f}中的字母构成，这6个字母在这段正文中出现的次数分别是{12,18,26,6,4,34}。回答以下问题:

（1）试画出对应的Huffman树并为这6个字母设计哈夫曼编码。

 

 

a:011 b:00 c:10 d:0101 e:0100 f:11

（2）求带权路径长度WPL。

WPL=18*2+(4+6)*4+12*3+(26+34)*2=232

4.有一份电文中共使用5个字符：a、b、c、d、e，它们的出现频率依次为4、7、5、2、9，试画出对应的Huffman树（请按左子树根结点的权小于等于右子树根结点的权的次序构造），并求出每个字符的Huffman编码。

a:011 b:10 c:00 d:010 e:11

5．将下图图1的树转换成二叉树，并将图2的二叉树转换成森林。

 

                           图1                                                         图2 

 

第七章．图

一 选择题。

1．有8个结点的有向完全图有（C）条边。

       A．14        B．28        C．56         D．112

2．用邻接表表示图进行广度优先遍历时，通常采用（B）来实现算法的。

       A．栈        B．队列      C．树         D．图

3．用邻接表表示图进行深度优先遍历时，通常采用（A）来实现算法的。

A．栈        B．队列      C．树         D．图

4．已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是（B）。

A．0 2 4 3 1 5 6     B．0 1 3 4 5 6 2

C．0 4 2 3 1 6 5     D．0 3 6 1 5 4 2

//建议答案：0 1 3 4 2 5 6

5．已知图的邻接矩阵同上题，根据算法，则从顶点0出发按广度优先遍历的结点序列是（D）。

       A．0 2 4 3 1 5 6                B．0 1 3 5 6 4 2

       C．0 4 2 3 1 6 5                D．0 1 2 3 4 5 6

//建议答案：0 1 2 3 4 6 5

6．任何一个无向连通图的最小生成树（B）。

       A．只有一棵                     B．一棵或多棵 

       C．一定有多棵                   D．可能不存在

7．在一个图中，所有顶点的度数之和等于所有边数的（C）倍。

       A．1/2         B．1         C．2           D．4

8．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（B）倍。

       A．1/2         B．1         C．2           D．4

9．一个有n个顶点的无向图最多有（C）条边。

       A．n           B．n（n-1）   C．n（n-1）/2   D．2n

10．具有4个顶点的无向完全图有（A）条边。

       A．6           B．12        C．16          D．20

11．具有6个顶点的无向图至少应有（A）条边才能确保是一个连通图。

       A．5           B．6         C．7           D．8

12．在一个具有n个顶点的无向图中，要连通全部顶点至少需要（C）条边。

       A．n           B．n+1       C．n-1         D．n/2

13．对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是（D）。

       A．n           B．（n-1）*（n-1）        C．n-1     D．n*n

14．对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为

      （A）所有邻接表中的结点总数是（C）。

      （1）A．n        B．n+1     C．n-1    D．n+e

      （2）A．e/2      B．e       C．2e     D．n+e

15．已知一个图如图所示，若从顶点a出发按深度搜索法进行遍历，则可能得到的一种顶点序列为（D）；按宽度搜索法进行遍历，则可能得到的一种顶点序列为（B）。

      （1）A．a，b，e，c，d，f       B．a，c，f，e，b，d

           C．a，e，b，c，f，d       D．a，e，d，f，c，b

      （2）A．a，b，e，c，d，f       B．a，b，c，e，d，f

           C．a，e，b，c，f，d       D．a，c，f，d，e，b

//建议答案：A B E D F C

//建议答案：A B C E F D

16．采用邻接表存储的图的深度优先遍历算法类似于二叉树的（B）。   

       A．先序遍历              B．中序遍历

       C．后序遍历              D．按层遍历

17．判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以利用（D）。

       A．求关键路径的方法         B．求最短路径的Dijkstra方法

       C．宽度优先遍历算法         D．深度优先遍历算法

18.对含有n个顶点、e条边的带权图求最短路径的Dijkstra算法的时间复杂度为（C）

A.  O(n) B.  O(n+e) C.  O() D.  O(ne)

19.若一个有向图中的顶点不能排成一个拓扑序列，则可断定该有向图（D）

A. 是个有根有向图 B. 是个强连通图

C. 含有多个入度为0的项点 D. 含有顶点数目大于1的强连通分量

20.关键路径是AOE网中（A）

A. 从源点到汇点的最长路径

B. 从源点到汇点的最短路径

C. 最长的回路

D. 最短的回路

21.对于AOE网的关键路径，以下叙述中正确的是（D）

A. 任何一个关键活动提前完成,则整个工程也会提前完成

B. 完成工程的最短时间是从源点到汇点的最短路径长度

C. 一个AOE网的关键路径是唯一的

D. 任何一个活动持续时间的改变可能会影响关键路径的改变

二 填空题。

1．图有邻接矩阵，邻接表等存储结构，遍历图有深度优先搜索、广度优先搜索等方法。

2．有向图G 用邻接表存储，其第i行的所有元素之和等于顶点i的_______________。

题目中的邻接表应该改为邻接矩阵，不然不存在行的元素之和

2．有向图G 用邻接矩阵存储，其第i行的所有元素之和等于顶点i的出度。

3．n个顶点e条边的图若用邻接矩阵存储，则空间复杂度为O(${\color{Red} n^{2}}$)。

4．n个顶点e条边的图若用邻接表存储，则空间复杂度为O(n+e)。

5．设有一稀疏图G，则G采用邻接表存储较省空间。

6．设有一稠密图G，则G采用邻接矩阵存储较省空间。

三 简答题。

1.写出图1无向图的邻接矩阵和邻接表存储形式，并按照邻接表写出其相应的深度优先遍历和广度优先遍历结果。

                图1的邻接矩阵存储形式

                         图1的邻接表存储形式

深度优先遍历：0 1 2 5 4 3 6 7

广度优先遍历：0 1 3 2 4 6 7 5

2.写出图2有向图的至少两种拓扑排序结果。

第一种：0 2 1 5 3 4

第二种：5 0 3 2 1 4

3.对于图所示的AOE网，求：

（1）每项活动ai的最早开始时间e(ai)和最迟开始时间l(ai)。

（2）完成此工程最少需要多少天（设边上的权值为天数）？

完成此工程最少需要55天。

（3）哪些是关键活动?

从以上计算中得出，关键活动为a1，a6，a8。

3.写出图4利用prim算法构造最小生成树的过程。

 

4.对于图5所示的有向网，利用Dijkstra算法求出从源点1出发到其余各顶点的最短路经，并写出执行过程。

E:5

B:25

C:40

F:100

6.给定如图6所示的带权无向图G。

（1）画出该图的邻接表存储结构。

 

（2）根据该图的邻接表存储结构,从顶点0出发,调用 DFS和算法遍历该图,给出相应的遍历序列。

DFS即为深度优先搜索：0 1 2 4 3 5

BFS即为广度优先搜索：0 1 2 3 4 5

（3）给出采用Kruskal 算法构造最小生成成树的过程。

 

第九章．查找

一 选择题。

1．顺序查找法适合于存储结构为（B）的线性表。

       A．散列存储              B．顺序存储或链接存储

       C．压缩存储              D．索引存储

2．对线性表进行二分查找时，要求线性表必须（C）。

       A.  以顺序方式存储        B.  以链接方式存储

       C．以顺序方式存储，且结点按关键字有序排序

       D．以链接方式存储, 且结点按关键字有序排序

3．采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为（C）。

       A．n        B．n/2        C．(n+1)/2          D．(n-1)/2

4．采用二分查找方法查找长度为n的线性表时，每个元素的平均查找长度为（D）。

 A．O（）     B．O（）     C．O（n）      D．O（）

5．二分查找和二叉排序树的时间性能（B）。

       A．相同           B．不相同

6．有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当二分查找值82的结点时，（C）次比较后查找成功。

       A．1         B．2               C．4            D．8

7．设哈系表长m=14，哈系表函数H（key）=key%11。表中已有4个结点：addr（15）=4；addr（38）=5；addr（61）=6；addr（84）=7；其余地址为空如果用二次探测再散列处理冲突，关键字为49的结点的地址是（D）。

       A．8         B．3               C．5            D．9

8．有一个长度为12的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况

   下查找成功所需的平均比较次数（B）。

A．35/12     B．37/12           C．39/12        D．43/12

9．分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分（B）个结点最佳。

        A．10       B．25              C．6            D．625

10．如果要求一个线性表既能较快的查找，又能适应动态变化的要求，可以采用（A）查找方法。

        A．分块     B．顺序            C．二分         D．散列

11．设有100个元素，用折半查找法进行查找时，最大比较次数是（D）。

        Ａ．25       B．50              C．10           D．7

12．设有100个元素，用折半查找法进行查找时，最小比较次数是（D）。

     A．7        B．4               C．2            D．1

13．哈希函数有一个共同性质，即函数值应当以（A）取其值域的每个值。

     A．同等概率     B．最大概率        C．最小概率     D．平均概率

14．设散列地址空间为0到m-1，k为关键字，用p去除k，将所得的余数作为k的散列地址，即H（k）=k%p。为了减少发生冲突的频率，一般取p为（C）。

 A．小于m的最大奇数    B．小于m的最大偶数        

 C．小于m的最大素数    D．小于m的最大合数

15．某顺序存储的表格中有90000个元素，以按关键字值额定升序排列，假定对每个元素进行查找的概率是相同的，且每个元素的关键字的值皆不相同，用顺序查找法查找时，平均比较次数约为（C）；最大比较次数约为（D）。

      A．25000        B．30000           C．45000        D．90000

16．二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值，小于其右孩子的值。这种说法（B）。

         A．正确           B．错误

17．如图所示的4棵二叉树，（B）是平衡二叉树。

          A                          B                                C                                 D 

18.在二叉排序树中，凡是新插入的结点都是没有（A）的。

A. 孩子 B. 关键字 C. 平衡因子 D. 赋值

19.以下关于二叉排序树的叙述中正确的是（D）

A. 二叉排序树是动态树表，在插人新结点时会引起树的重新分裂和合并

B. 对二叉排序树进行层次遍历可以得到一个有序序列

C. 在构造二叉排序树时，若关键字序列有序,则二叉排序树的高度最大

D. 在二叉排序树中进行查找，关键字的比较次数不超过结点数的一半

20.关于二叉排序树的描述不正确的是（C）

A. 二叉排序树的查找效率取决于树的形态

B. 从二叉排序树中删去一个结点后再重新插入，一定是作为叶子结点插人的

C. 在最坏情况下，利用插入操作构造一棵二叉排序树花费的代价为O()

D. 在含有n个结点的平衡二叉排序树中，查找失败时最多花费代价为O()

21.在含有27个结点的二叉排序树上查找关键字为35的结点，则依次比较的关键字序列有可能是（D）

A. 28,36,18,46,35

B. 18,36,28,46.35

C. 46,28,18,36,35

D. 46,36,18,28,35

22.对于下列关键字序列，不可能构成某二叉排序树中一条查找路径的序列是（A）

A. 95,22,91,24,94,71

B. 92,20,91,34,88,35

C. 21,89,77,29,36,38

D. 12,25,71,68,33,34

23.哈希表中出现哈希冲突是指（D）

A. 两个元素具有相同的序号

B. 两个元素的关键字不同，而其他属性相同

C. 数据元素过多

D. 两个元素的关键字不同，而对应的哈希函数值相同

24.下面有关哈希表的叙述中正确的是（B）

A. 哈希查找的时间与规模n成正比

B. 不管是开放地址法还是拉链法，查找时间都与装填因子α有关

C. 开放地址法存在堆积现象，而拉链法不存在堆积现象

D. 拉链法中装填因子α必须小于1

25.为提高哈希表的查找效率，可以采取的正确措施是（D）

Ⅰ增大装填因子

Ⅱ设计冲突少的哈希函数

Ⅲ处理冲突时避免产生堆积现象

A. 仅Ⅰ

B. 仅Ⅱ

C. 仅Ⅰ、Ⅱ

D. 仅Ⅱ、Ⅲ

26.从100个元素中查找其中某个元素，如果最多进行5次元素之间的比较，则采用的查找方法只可能是（A）

A. 折半查找

B. 分块查找

C. 哈希查找

D. 二叉排序树查找

二 填空题。

1．含n个元素的顺序表，若采用顺序查找法的平均查找长度为${\color{Red} (n+1)/2}$；二分查找法的平均查找长度为${\color{Red} [(n+1)*log_{2}(n+1)]/n-1}$；分块查找法（以顺序查找确定块）的平均查找长度为${\color{Red} (s^{2}+2s+n)/2s}$；分块查找法（以二分查找确定块）的平均查找长度为${\color{Red} log_{2}(n/s+1)+s/2}$；哈希表查找法采用链接法处理冲突时平均查找长度为1+a(a为装填因子)。

2．在各种查找方法中，平均查找长度与结点个数n无关的查找方法是哈希查找。

3．二分查找的存储结构仅限于顺序存储，且是有序。

三 应用题。

1.设有一组关键字{19，01，23，14，55，20，84，27，68，11，10，77}，采用哈希函数：H（key）=key%13，采用开放地址法的线性探测再散列方法解决冲突，试在0到18的散列地址空间中对该关键字序列构造哈希表，并计算查找成功的情况下平均查找长度ASL。

ASL成功=(1+2+1+4+3+1+1+3+1+1+3+2)/12=1.92 

2.设有一组关键字{19，01，23，14，55，20，84，27，68，11，10，77}，采用哈希函数：H（key）=key%13，采用开放地址法的二次探测再散列方法解决冲突，试在0到18的散列地址空间中对该关键字序列构造哈希表，并计算平均查找长度。

ASL=(3+1+2+1+2+3+1+1+3+1+1+1)/12=1.67

3.线性表的关键字集合{87，25，310，08，27，132，68，95，187，123，70，63，47}，共有13个元素，已知散列函数为H（k）=k%13，采用拉链法处理冲突，设计出这种链表结构，并计算该表的成功查找的平均查找长度。

ASL=(18+2*3)/13=1.84

4.对于关键字序列{30，15，21，40，25，26，36，37}，若查找表的装填因子为0.8，采用线性探测法解决冲突，完成下列各题： 

（1）设计哈希函数。

 由于装填因子为0.8，关键字有8个，所以表长为8/0.8=10

用除留余数法，哈希函数为H(key)=key%7

（2）画出哈希表。

（3）计算在等概率条件下查找成功的平均查找长度。

 ASL=(1+1+1+3+1+1+2+6)/8=2

第十章．排序

一 选择题。

1．在所有排序方法中，关键字比较的次数与记录的初始排序次序无关的是（D）。

  A．希尔排序    B．起泡排序     C．插入排序     D．选择排序

2．设有1000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好选用（C）。

    A．起泡排序    B．快速排序     C．堆排序       D．基数排序

3．在待排序的元素序列基本有序的前提下，效率最高的排序方法是（A）。

        A．插入排序    B．选择排序    C．快速排序     D．归并排序

4．一组记录的排序码为（46，79，56，38，40，84），则利用堆排序的方法建立的初始堆为（B）。

        A．79，46，56，38，40，84    B．84，79，56，38，40，46

        C．84，79，56，46，40，38    D．84，56，79，40，46，38

5．一组记录的排序码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（C）。

        A．38，40，46，56，79，84    B．40，38，46，79，56，84

        C．40，38，46，56，79，84    D．40，38，46，84，56，79

6．一组记录的排序码为（25，48，16，35，79，82，23，40，36，72），其中含有5个长度为2的有序表，按归并排序的方法对该序列进行一趟归并后的结果为（A）。

        A．16 25 35 48 23 40 79 82 36 72     B．16 25 35 48 79 82 23 36 40 72

        C．16 25 48 35 79 82 23 36 40 72     D．16 25 35 48 79 23 36 40 72 82

7．排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为（C）。

     A．希尔排序    B．起泡排序     C．插入排序     D．选择排序

8．用某种排序方法对线性表（25，84，21，47，15，27，68，35，20）进行排序时，元素序列的变化情况如下：

 （1）25，84，21，47，15，27，68，35，20

 （2）20，15，21，25，47，27，68，35，84

 （3）15，20，21，25，35，27，47，68，84

 （4）15，20，21，25，27，35，47，68，84

 则采用的排序方法是（D）。

       A．选择排序    B．希尔排序     C．归并排序     D．快速排序

9．下述几种排序方法中，平均比较次数最少的是（C）。

        A．插入排序     B．选择排序    C．快速排序    D．归并排序

10．下述几种排序方法中，要求内存量最大的是（D）。

      A．插入排序     B．选择排序    C．快速排序    D．归并排序

11．快速排序方法在（C）情况下，最不利于发挥其长处。

      A．要排序的数据量太大      B．要排序的数据中含有多个相同值

      C．要排序的数据已基本有序  D．要排序的数据个数为奇数

12．对n个不同的排序码进行冒泡排序，在（B）情况下比较的次数最多。

      A．从小到大排序好的        B．从大到小排列好的

      C．元素无序                D．元素基本有序

13．对n个不同的排序码进行冒泡排序，在元素无序的情况下比较的次数为（D）。

      A．n+1        B．n        C．n-1       D．n（n-1）/2

14．快速排序在（C）情况下最易发挥其长处。

       A．被排序的数据中含有多个相同的排序码   B．被排序的数据已基本有序

 C．被排序的数据完全无序      D．被排序的数据中的最大值和最小值相差悬殊

15．将5个不同的数据进行排序，至少需要比较（A）。

 A．4             B．5          C．6          D．7

16．将5个不同的数据进行排序，至多需要比较（C）。

•      A．8             B．9          C．10         D．25

17．下列关键字序列中（C）是堆。

        A．16，72，31，23，94，53     B．94，23，31，72，16，53

        C．16，53，23，94，31，72     D．16，23，53，31，94，72

18．堆是一种（B）排序。

        A．插入          B．选择       C．交换        D．归并

19．堆的形状是一棵（C）。

        A．二叉排序树    B．满二叉树   C．完全二叉树   D．平衡二叉树

二 简答题。

1.已知序列{48，36，68，99，75，24，28，52}，请给出采用快速排序法对该序列作升序排列时的每一趟的结果。

28 36 24 48 75 99 68 52

24 28 36 48 52 68 75 99

24 28 36 48 52 68 75 99

2.已知序列{53，17，78，32，45，65，87，9}，请给出采用堆排序法构建初始大根堆的过程。

构建初始大根堆的过程分为4步

1.87与78进行交换

2.45与17进行交换

3.87与53进行交换

4.78与53进行交换

之后得到如下图像

3.已知序列{10，18，4，3，6，12，1，9，18，8}，请给出采用归并排序法对该序列作升序排序时的每一趟的结果。 

1.【10，18】【3，4】【6，12】【1，9】【8，18】

2.【3，4，10，18】【1，6，9，12】【8，18】

3.【3，4，10，18】【1，6，8，9，12，18】

4.【1，3，4，6，8，9，10，12，18，18】