人武学院《数据结构》试卷

一、选择题（10道题，每题3分共30分）

1、下面算法的时间复杂度为（      ）

While(i   n=n*10;

A    O(1)       B    O(n)          C  O(n2)         D  O(logN)

2.不带头结点的单链表first为空的判定条件是（   B    ）

A first= =NULL B first->link = =NULL

C first->link= =first D first!= NULL

3. 设有一个广义表A( ( x, (a, b ) ), ( x, (a ,b ) , y ) ),运算Head( Head(Head(A ) ) )的执行结果为（  A  ）

A   x                              B    (a,b) 

C  (x, ( a , b ))                  D     y

4. 在一棵完全二叉书中，若编号为i的结点存在左子树，则右子树结点编号为（    ）。假定树根结点的编号为0.

   A.  2i           B 2i-1         C   2i+1          D 2i+2

5.设有一个n*n的对称矩阵A，将其上三角部分按行存放在一个一维数组B中，A[0][0]存放于B[0]中，那么第i行的对角元素 A[i][i]存放与B中（　　　）

处。

A  (i+3)*i/2                         B (i+1)*i/2

C  (2n-i+1)*i/2                      D  (2n-i-1)*i/2

6 .图的广度优先算法类借助的数据结构为（   B ）

  A  栈              B  队列           C  二叉树           D  树

7. 如果从中国人找出100个年龄最大的，那么使用下列排序算法中（   D  ）算法最快

  A  归并排序      B 希尔排序          C  堆排序        D   基数排序

8.散列函数应该有这样的性质，即函数值应当以 （      ）概率取其值域范围内的每一个值。

 A   最大            B  最小            C    平均       D  同等   

9．若待排序序列在排序前已基本递减有序，则采用（  A    ）个方法比较次数比较少。

A    直接插入排序                       B  快速排序

C    归并排序                           D直接选择排序

10．10阶B树中，每个结点最多允许有（      ）个关键字。

  A   8              B    9              C   10           D  1 1

二、填空题（8道题，每空1分共10分）

1、在顺序表中逻辑上相邻的结点而在物理位置上_______一定__相邻。

2、在一棵高度为3的二叉书中，最多含有_____85____个结点，假设根结点的高度为0.

3.在链表中进行插入和_______操作的效率比在顺序存储结构中进行相同的操作

效率搞。

4.在一棵二叉排序树中插入一个元素时，若元素的值大于根结点的值，则应把它插入到根结点的____右子树________上。

5.一棵树按照左子树-右兄弟表示法转换成对应的二叉树，则该二叉树根结点肯定没有______右____子树。

6.设双向循环链表中每个结点的结构为（data，llink，rlink），则结点*p的前驱结点的值为____p->llink__________.

7．在一棵高度为3的理想的平衡二叉树，最少还有___8____（_ 2h ）_____个结点，最多还有_____15（_2h+1-1_）_____个结点。假定树根结点为高度为1。

8.快速排序最坏情况和平均情况时间复杂度为___________和_____________.

三、判断题（10道题，每题1分共10分）（判断下列各个叙述的正误。对，在括号里面写T，错误，在括号里面写F）

1.数据项是数据的最小单位。                                     (     )

2. 顺序栈与链式栈相比，一个明显的优点是通常不会出现栈满的情况。(     )

3.一棵二叉树中，假定每个结点只有左子树，没有右子树，若对他分别进行中序遍历和后序遍历，则具有相同的结果。                             (     )

4.一个广义表尾是一个广义表。                                    (     )

5.邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都使用。

                                                               (     )

6.对于AOE网络，任一关键活动延迟将导致整个工程延迟完成。       (     )

7.数据的逻辑结构与数组元素本身的内容与形式无关。                (     )

8.当输入序列已经基本有序时，冒泡排序需要比较关键值的次数，比快速排序少。

9.若将一批杂乱无章的数据按堆结构组织起来，则堆中数据必然是按从大到小的顺序排列的。                                                   (     )

10.能够在链接存储的有序表进行折半查找，时间复杂度与顺序存储的时间复杂度小。                                                         (     ) 

四、运算题（5道题 每题8分共40分）              

1、假定一棵二叉树的广义表表示为 A(B(  ,D(G)),C(E,F))分别写出对它先序，中序，后序序列。

2、已知一个数据表为{47,25,76,32,40}，请写出在进行快速排序的过程每次划分后数据表的变化。

3、线性表的关键字集合为{113,12,180,138,92,67,94,134,252,6,70,323,60}，共有13个元素，已知散列函数为：H（k）=k mod 13，采用链接表处理冲突，试设计这种链表结构

4. 有一份电文使用5个字符：a、b、c、d、e，它们的出现频率依次为10、4、2、12、8。试画出对应的哈夫曼树，并求出每个字符的哈夫曼编码。

5. 已知一个带权图的顶点集V和边集V为

V={0，1，2，3，4，5，6}；

E={（0，1）19，(0，2)10，（0，3）14，（1，2）6，（1，5）5，（2，3）26，（2，4）15，（3，4）18，（4，5）6，（4，6）6，（5，6）12}   

根据Dijkstra算法求顶点0到其它顶点的最短距离，并写出各路径。    

五、程序设计题（1道题共10分）   

设计一个用单链表作存储结构的直接插入排序算法。

数据结构  A

三、判断题（10道题，每题1分共10分）（判断下列各个叙述的正误。对，在括号里面写T，错误，在括号里面写F）

1.数据元素是数据的最小单位。                                  (      )

2.链式栈与顺序栈相比，一个明显的优点是通常不会出现栈满的情况。 （     ）

3.一棵二叉树中，假定每个结点只有左子树，没有右子树，若对他分别进行中序遍历和后序遍历，则具有相同的结果。                             （     ）

4.一个广义表头总是一个广义表。                                （     ）

5.邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都使用。                                                               （    ）

6.对于AOE网络，任一关键 活动延迟将导致整个工程延迟完成。       （    ）

7.数据的逻辑结构与数组元素本身的内容与形式无关。                （    ）

8.当输入序列已经基本有序时，冒泡排序需要比较关键值的次数，比快速排序少。                                                            （     ）

9.若将一批杂乱无章的数据按堆结构组织起来，则堆中数据必然是按从小到大的顺序排列的。                                                  （     ）

10.能够在链接存储的有序表进行折半查找，时间复杂度与顺序存储的时间复杂度相同。                                                        （     ）

四、运算题（5道题 每题8分共40分）            

1、已知一棵二叉树的中序和后序如下，求改二叉树的前序序列和原图。

中序序列：c,  b,  d,  e,  a,  g,  i,  h,  j,  f

后序序列：c,  e,  d,  b,  i,  j,   h,  g,  f,  a

原图结构：

前序序列为：

2、已知一个数据表为{48,25,56,32,40}，请写出在进行快速排序的过程每次划分后数据表的变化。

3、设散列表长m=14，哈希函数为H(k)=k mod 11，表中一共有8个元素{15,27,50,73,49,61,37,60} ，试画出采用二次探测法处理冲突的散列表。

&&4. 有一份电文使用5个字符：a、b、c、d、e，它们的出现频率依次为5、 2、1、6、4。试画出对应的哈夫曼树，并求出每个字符的哈夫曼编码。

5. 求出下图各结点最早，最晚开始时间，并求出关键活动。                  

1、假定一棵二叉树的广义表表示为 A(B(  ,D(G)),C(E,F))分别写出对它先序，中序，后序序列。

2、知一个数据表为{47,25,76,32,4‰}，请熙出在进行快速排序的꿇程䯏次划分琎数䍮表的变化。

3、 线性表的关键字集合为{113,12,180,138,92,67,94,134,252,6,70,323,60}，共有13个元素，已知散列函数为：H（k）=k mod 13，采用链接表处理冲突，试设计这种链表结构

5.已知一个带权图的顶点集⁖和꾹集V为

V={0，1，2，3，4，5，6}；

E={（0，1）19，(0，2)10，（0，3）14，（1，2）6，（1，5）5，（2，3）26，（2，4）15，（3，4）18，（4，5）6，（4，6）6，（5，6）12}   

根据Dijkstra算法求顶点0到其它顶点的最短距离，并写出各路径。     

五、程序设计题（1道题共10分）  

 试设计一个算法实现双向冒泡排序。（双向冒泡排序就是在排序的过程中交替改变扫描方向。）