杭电数据结构期末复习卷答案

（正确的打“√”，错误的打“×”。）

1.  数据结构可用三元式表示（D，S，P）。其中：D是数据对象，S是D上的关系集，

P是对D的基本操作集。×

2.  线性表的链式存储结构具有可直接存取表中任一元素的优点。 ×

3.  队列是数据对象特定的线性表。×

4.  二叉树是一棵结点的度最大为二的树。 ×

5． 邻接表可以用以表示无向图，也可用以表示有向图。√

6． 可从任意有向图中得到关于所有顶点的拓扑次序。×

7． 一棵无向连通图的生成树是其极大的连通子图。×

8． 二叉排序树的查找长度至多为log2ｎ。×

9． 对于一棵m阶的B-树，树中每个结点至多有m-1个关键字。除根之外的所有非终端结点至少有m/2 -1个关键字。√

10．对于目前所知的排序方法，快速排序具有最好的平均性能。√

11. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。×

12. 二维数组是其数据元素为线性表的线性表。√

13. 连通图G的生成树是一个包含G的所有n个顶点和n-1条边的子图。×

14. 折半查找不适用于有序链表的查找。√

15. 完全二叉树必定是平衡二叉树。√

16. 中序线索二叉树的优点是便于在中序下查找直接前驱结点和直接后继结点。√

17. 队列是与线性表完全不同的一种数据结构。×

18. 平均查找长度与记录的查找概率有关。√

19. 广义表的表头和表尾都有可能是原子或广义表。×

20. 算法的时间复杂性越好，可读性就越差；反之，算法的可读性越好，则时间复杂性就越差。×

二．选择题

1.  若广义表LS满足GetHead(LS)==GetTail(LS)，则LS为( b )。

  A. ( )          B. (( ))       C. (( ),( ))     D. (( ),( ),( ))

2.  递归程序可借助于(  b  )转化为非递归程序。

    a:线性表      b: 栈        c:队列      d:数组    

3.  在下列数据结构中(  c  )具有先进先出（FIFO）特性，(  b  )具有先进后出(FILO）特性。

a:线性表        b:栈       c:队列       d:广义表

4.  假设用于通讯的电文仅由6个字符组成，字母在电文中出现的频率分别为7, 19, 22, 6, 32, 14。 若为这6个字母设计哈夫曼编码（设生成新的二叉树的规则是按给出的次序从左至右的结合，新生成的二叉树总是插入在最右），则频率为7的字符编码是（ g  ），频率为32的字符编码是（ c ）。

a: 00       b: 01      c: 10      d: 11  

e: 011      f: 110     g: 1110    h:1111

5. 对二叉排序树按（ c ）可得到有序序列。

  a:层次遍历       b:前序遍历      c:中序遍历      d:后序遍历

6．已知某树的先根遍历次序为abcdefg，后根遍历次序为cdebgfa。若将该树转换为二叉树，其后序遍历次序为（ d ）。

 a:  abcdefg    b: cdebgfa     c:  cdegbfa      d: edcgfba

7．对一棵完全二叉树进行层序编号。则编号为n的结点若存在右孩子，其编号是( d )。

编号为n的结点若存在双亲，其编号是( a )。

a: n/2        b: 2n        c: 2n-1       d: 2n+1     e: n      f: 2(n+1)

8．关键路径是指在只有一个源点和一个汇点的有向无环网中源点至汇点（ c ）的路径。

a:弧的数目最多   b:弧的数目最少   c:权值之和最大    d:权值之和最小

9. 哈希表的查找效率取决于（ d ）。

a: 哈希函数   b:处理冲突的方法。  c:哈希表的装填因子。  d:以上都是

10．从逻辑上可以把数据结构分成( c )。

    a: 动态结构和静态结构              b: 顺序组织和链接组织

c: 线性结构和非线性结构            d: 基本类型和组合类型

11．在计算递归函数时，如不用递归过程，应借助于( b )这种数据结构。

a: 线性表         b: 栈            c: 队列          d: 双向队列

12．若已知某二叉树的中序和后序遍历序列分别BCAEFD和CBFEDA，则该二叉树的先序序列为( a )。

a: ABCDEF        b: ABDCEF        c: ABDCFE        d: ACBDFE

13．当待排序序列的关键字次序为倒序时，若需为之进行正序排序，下列方案中( d )为佳。

    a: 起泡排序                    b: 快速排序

c: 直接插入排序                d: 简单选择排序

14．若从二叉树的根结点到其它任一结点的路径上所经过的结点序列按其关键字递增有序，则该二叉树是( c )。

a: 二叉排序树         b: 赫夫曼树         c: 堆         d: 平衡二叉树

15．下图所有可能的拓扑序列有( b )种。

a: 2               b: 3              c: 4               d: 5

16．下列排序算法中，( d )算法可能会出现：初始数据为正序时，花费的时间反而最多。

a: 堆排序          b: 起泡排序       c: 归并排序        d: 快速排序

17．右图为一棵3阶B-树。                    20 ，25

在该树上插入元素15        

后的B-树是( c )。                10 , 14        21        35

 a:           15 , 25                    b:           20 , 25

   10 , 14       20 , 21     35             10 , 14      15 , 21      35

 c:          20                         d:          14 , 25

      14            25                   10 , 15       20 , 21     35

10     15     21     35

18．设森林F中有三棵树，第一、第二和第三棵树的结点个数分别为m1、m2和m3，则与森林F对应的二叉树根结点的右子树上的结点个数是( d )。

a: m1             b: m1+m2           c: m3            d: m2+m3

19. 根据插入次序（80，90，100，110，85，70，75，60，72）建立二叉排序树。图（ a ）是最终变化的结果。若仍以该插入次序建立平衡二叉树。图（ c ）是最终变化的结果。

      a:                              b:

         80                             80         

 70         90                 75           90   

 60    75   85    100          60    70     85      100 

    72               110    72                         110 

      c:                               d:

    90                                  90      

 75         100                    80            100 

 70    80         110             75       70   85       110 

60     72       85                         60    72  

20.设输入序列为20,45,30,,70,38,62，19，依次插入到一棵2-3树中(初始状态为空)，该B-树为（ b ）。再删除38，该B-树为（ f ）。

 a:                                         b:

          （  30  62 ）                                 （  45  ）                 

（19，20）（ 38 45 ） （ 70， ）              （  30  ）        （ 70 ）

（19 20）     （38 ）（ 62 ） （  ）

c:                                         d:

        （  45   70  ）                                （   45  ）                 

（20）   （ 62 ）  （  ）                  （ 20 ）         （ 70 ）

（19）（ 30 ）                           （ 19 ）   ( 30,38 ）（ 62 ） （  ）

e:                                           f:

         （  30    70  ）                               （  45  ）                 

（19，20） （ 45 62）  （  ）               （ 20 ）          （ 70 ）

（19 ）     （30 ）（ 62 ）  （  ）

21．已知一组待排序的记录关键字初始排列如下：45,34,87,25,67,43,11,66,27,78 。

( g )是快速排序法一趟排序的结果；

( a )是希尔排序法（初始步长为4）一趟排序的结果；

( b )是初始堆（大堆顶）；

( d )是基数排序法一趟排序的结果。

a：27,34,11,25,45,43,87,66,67,78        b: 87,78,45,66,67,43,11,25,27,34

c: 11,43,34,25,45,66,27,67,87,78        d:11,43,34,45,25,66,87,67,27,78

e: 34,45,25,67,43,11,66,27,78,87        f: 87,45,11,25,34,78,27,66,67,43

g: 27,34,11,25,43,45,67,66,87,78        h: 34,11,27,25,43,78,45,67,66,87

22．若有序表中关键字序列为：14，20，25，32，34，45，57，69，77，83，92。对其进行折半查找，则在等概率情况下，查找成功时的平均查找长度是( c )。查找32时需进行( c )次比较。

a: 1               b: 2              c: 3              d: 4         

23. 设一棵二叉树BT的存储结构如下:

              1    2    3    4    5    6    7    8

    lchild    2    3    0    0    6    0    0    0

      data    A    B    C    D    E    F    G    H

    rchild    0    5    4    0    8    7    0    0

    其中lchild，rchild分别为结点的左、右孩子指针域，data为结点的数据域。则

该二叉树的高度为( d )；

第3层有( a )个结点（根结点为第1层）。

   a: 2              b: 3              c: 4               d: 5

24. 一个连通图的最小生成树( b )。

   a: 只有一棵       b: 有一棵或多棵     c: 一定有多棵      d: 可能不存在

25．若某二叉树有20个叶子结点，有20个结点仅有一个孩子，则该二叉树的总结点数是( c )。

   a: 40             b: 55             c: 59              d: 61

26．已知哈希表地址空间为A[0..8]，哈希函数为H(k)=k mod 7，采用线性探测再散列处理冲突。若依次将数据序列：76,45,88,21,94,77,17存入该散列表中，则元素17存储的下标为( f )；在等概率情况下查找成功的平均查找长度为( c )。

    a: 0               b: 1               c: 2               d: 3

e: 4               f: 5               g: 6               h: 7

27．已知某有向图的邻接表存储结构如图所示。

   0  E           2             1   ∧

1  D           0            3             4   ∧

2  C      4   ∧

3  B           1            2             0   ∧

4  A           2   ∧



根据存储结构，依教材中的算法其深度优先遍历次序为（ d ）。

广度优先遍历次序为（ c ）。各强连通分量的顶点集为（ f ）。

a:  abcde.       b:  edcba.     c:  ecdab.       d:  ecadb.   

  e:  abc及ed     f:  ac及bed   g:  ab及ced     h:  bc及aed

28. 已知某无向图的邻接表如下所示；            

( e )是其原图。                         

( c )是按该邻接表遍历所得深度优先生成树。

( d )是按该邻接表遍历所得广度优先生成树。

  0  a         3        2        1    

  1  b         3        0   

  2  c         4        3       0

  3  d         5        2       1        0

  4  e         5        2

  5  f         4        3

a: a      b                b: a    b                 c:  a    b     

c     d                    c     d                    c    d     

e     f                    e     f                    e    f      

d: a     b                 e: a     b                f: a     b

   d     c                    c     d                   c     d

   f     e                    e     f                   e     f

29．设有二维数组A 5 x 7 ,每一元素用相邻的4个字节存储，存储器按字节编址。

已知A的起始地址为100。则按行存储时，元素A06的存储地址是（ d ）；

按列存储时，元素A06的存储地址是（ a ）。

a. 220        b. 200         c. 140        d. 124

30.若顺序表中各结点的查找概率不等，则可用如下策略提高顺序查找的效率：若找到指定

的结点，将该结点与其后继（若存在）结点交换位置，使得经常被查找的结点逐渐移至

表尾。以下为据此策略编写的算法，请选择适当的内容，完成此功能。

顺序表的存储结构为：

typedef struct{

               ElemType *elem; //数据元素存储空间，0号单元作监视哨

               int     length; //表长度

              }SSTable;

int search_seq(SSTable ST, KeyType key)

{ //在顺序表ST中顺序查找关键字等于key的数据元素。

//若找到，则将该元素与其后继交换位置，并返回其在表中的位置，否则为0。

ST.elem[0].key=key;

i=ST.length;

while(ST.elem[i].key!=key)    f    ;

if(     g     )

  { ST.elem[i]←→ST.elem[i+1]；

        e    ；

  }    

return i;

}

a: i>0 b: i>=0        c: ie: i++        f: i--         g: A和C同时满足      h: B和D同时满足

三．算法设计题

1. 单链表结点的类型定义如下：

typedef struct LNode {

        int data;

        struct LNode *next;

} LNode, *Linklist;

写一算法，Contrary(linklist &L) ,对一带头结点且仅设尾指针L的循环单链表就地逆置。（即首元变尾元，尾元变首元。）

void Contrary(linklist &L)

{ p=L->next; q=L;

 while(p!=L)

{ r=p->next; p->next=q; q=p; p=r; }

p->next=q;

}

2．二叉树用二叉链表存储表示。

typedef struct BiTNode {

      TelemType  data;

      Struct BiTNode *lchild, *rchild;

} BiTNode, *BiTree;

试编写销毁二叉树T的算法DestroyBiTree ( BiTree  &T)。

void DestroyBiTree ( BiTree  &T)

{ if(!T) return;

if(T-lchild) DestroyBiTree(T->lchild);

if(T-rchild) DestroyBiTree(T->rchild);

 free(T); T=NULL;

}

3．设带头结点的单链表中的元素以值非递减有序排列，试编写算法，删除表中所有值相同的多余元素。

单链表结点的类型定义如下：

  typedef struct LNode{

        int data;

        Struct LNode  *next;

     }LNode, *LinkList;

void Delete_same(LinkList L)

{ if(!L->next) return;

p=L->next; q=p->next;

 while(q)

if(p->data==q->data)

{ p->next=q->next; free(q); q=p->next;}

  else

{ p=q; q=q->next;}

}