数据结构08-09期末试题B

一、填空（共20分，每空1分）

1. 计算机程序设计的两个核心目标：            、            。

2．对下面一段程序代码表示的算法：

      Sum = 0

For (j=1; j<=n; j++)

For (i = 1; i<=j; i++)

             Sum ++;

其基本运算应为            , 时间复杂度应为            。

3. 设单链表用两个同样大小的一维数组V(1:n)和Next(1:n)分别保存该链表各结点的数据域值和指针域值。链表中指针p指向结点A，若要删除结点A的后继结点(假设A存在后继结点)，该操作的程序代码为             。

4. 普通树的结构太复杂,难以计算机实现。因此应用中常树的每个结点只能有最多_________个子结点，称为二叉树。

5. 如果一种内部排序方法只比较和交换相邻记录，它的平均时间代价应是________。

6. 若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构_______。

7. 磁盘中数据访问过程中，读取的数据量对读取时间影响不大。因此可以磁盘驱动器从磁盘中取出多余数据，以满足将来的请求，这称为_________技术。

8. _________是堆排序算法的一个微小变体，常用于外部排序。

9. 在散列技术中，处理冲突的两种主要方法是开散列方法和_________。

10. 二叉查找树做删除操作时，若被删除的结点是一个叶子结点，则直接删除；若有一个子结点，则_________；若有两个子结点，则_________。

11.  对于一个队列，允许执行插入操作的一端是_____，允许执行删除操作的一端是______。

12. 哈夫曼编码的前缀特性是指_________。

13. 冒泡排序的平均时间代价是_________、堆排序的平均时间代价是_________、而_________排序的平均时间代价是O(n1+￡)，0<￡<1。

14. ________排序的基本思想是指将两个或两个以上的有序表合并成一个新的有序表。

二、单项选择（共20分，每小题1分）

1.堆从结构上属于（     ）

A. 线性表       B.完全二叉树       C. 满二叉树       D.树

2.对一个单链表，完成在某结点后插入一个新结点的时间代价为（    ）

A. Θ（1）     B.Θ（n）      C. Θ（n2）      D. Θ（nlogn）    

3.一个栈的入栈序列是1,2,3,4,5，则栈的不可能的输出序列是（   ）。

A. 5,4,3,2,1      B. 4,5,3,2,1     C. 4,3,5,1,2      D. 1,2,3,4,5

4.作为一般规律，当线性表的元素数目（    ），最好使用链表实现。

A. 变化较大     B. 较大       C. 已知       D. 变化较小

5.栈是限定仅仅在一端进行插入和删除操作的线性表，其数据输入和输出顺序的特点是(     )  

A. 先进后出     B. 先进先出   C. 无规律     D.可人为控制

6.从栈顶指针为top的链栈中删除一个结点，用x保存被删除结点的值，则执行（     ）。

A. x = top; top = top->next; B. x = top->value;

C. top = top->next; x = top->value; D. x = top->value; top = top->next;

7.对任何一棵二叉树T，如果其叶结点的个数为n0，度为2的结点个数为n2，则（    ）

A. n0 = n2-1      B. n0 = n2      C. n0 = n2+1    D. 没有规律

8.散列技术中的冲突指的是（     ）。

A. 两个元素即有相同的序号    B. 两个元素的值不同，而其他属性相同  

C. 数据元素过多              D. 不同值的元素对应相同的存储地址

9. 在对算法时间代价进行渐近分析时，我们通常分析一种算法运行时间增长率，忽略算法运行时间函数的系数和（     ）。

A. 低次项       B. 问题规模      C. 计算机硬件配置     D. 不同的输入数据

10. 前序周游是指在周游二叉树时要首先访问（     ）

A. 左子树       B. 右子树        C. 根结点       D. 值最小的结点

11. 如右图所示，要删除单链表中的结点(即元素12所在的结点)，应采用下述语句(      )。

A. fence->next=fence->next->next

B. fence =fence->next

C. fence->next=fence D. fence =fence->next->next

12. 外部排序算法的主要目标应为（    ）

  A. 减少比较次数                 B.减少数据移动次数    

C. 减少存储空间占用             D.减少磁盘访问次数 

13. 散列表发生冲突的概率主要由（    ）决定

  A. 记录数量     B.槽的数量     C. 关键码的类型      D. 填充因子

14. 一个算法的最佳情况是指(   )。

A. 输入规模达到了可能的最小值

B. 规模大小给定的一个特定的输入实例，算法在此种输入情况下代价最小

C. 输入规模达到了可能的最大值

D. 规模大小给定的一个特定的输入实例，算法在此种输入情况下代价最大

15. 集合具有如下(     )的性质。

A. 可以有重复的元素，每个元素有一个位置

  B. 可以有重复的元素，但元素没有位置

C. 没有重复的元素，每个元素有一个位置

D. 没有重复的元素，且元素没有位置

16. 对结点数量一定的二叉树，高度最小的应为（     ）

A. 满二叉树     B. 完全二叉树      C. 二叉查找树     D. 哈夫曼树

17. 顺序表中所有元素所占的存储空间是（     ）

  A. 连续                  B. 不连续    

C. 可连续，亦可不连续    D. 根据顺序表类型而确定是否连续

18. 一个单链表中存储的数据序列是（a, b, c, d, e），如果从b出发，能够访问（     ）

  A. 所有结点      B. 结点a     C. 结点c, d, e       D. 都不能访问

19. 二叉查找树的查找、插入、删除的时间代价都取决于树的（     ）

  A. 高度         B. 结点数量    C. 分支结点数量    D. 形状

20. 在堆中执行一次插入操作，其最差情况下的时间代价是（      ）

A. Θ（n）      B. Θ（n2）      C. Θ（logn）       D. Θ（nlogn）

三、多项选择（共10分，每小题2分）

1. 链表具有的特点包括（           ）

  A. 物理上无序                               B. 逻辑上有序     

C. 通过指针域反映数据结点之间的逻辑联系     D. 存储空间利用效率高

E. 结点包含数据域和指针域两部分

2. 算法效率分析时，基本运算的选择原则包括（    ）

A. 基本运算的次数与算法执行的运算总次数大体上成比例。 

B. 基本运算应是算法执行中难度最大的运算。

     C．基本运算以外的其它运算的运算量可以忽略。

D. 基本运算应体现该算法区别于其它算法的特征。

E. 基本运算应是所有运算中单次执行耗时最长的运算。

3. 下列说法正确的有（      ）

   A. 快速排序是目前为止平均速度最快的一种排序方法，对一个相同序列，快速排序一定会比希尔排序花更少的时间。

  B. 如果一个线性表中元素数量多，并且存在元素频繁地插入或删除操作，那么更适宜采用线性链表而不是顺序表。

  C. 算法分析时，最佳情况下的时间代价是指输入规模小条件，因为输入规模小时算法花费的时间少。

D. 学习数据结构知识可以帮助我们更有效地组织、管理和使用数据。

E. 算法的时间代价分析时，最客观和准确的方法是直接测量算法对问题求解的时间。

4. 属于线性表的数据结构包括（        ）

A. 栈      B. 队列       C. 二叉树        D. 堆        E. 顺序表

5. 平均时间代价为Θ（n2）的排序算法有（      ）

    A. 冒泡排序    B. 选择排序    C. 希尔排序    D. 归并排序   E. 基数排序

四、判断题（共8分，每小题1分，正确打√，错误打×）

1. 一个大线性表，其插入和删除操作频繁，该线性表最好采用顺序存储结构。（    ）

2. 后序周游一棵二叉查找树能够得到一个有序序列。（     ）

3. 栈与队列都属于线性表，但它们区别的除了插入和删除操作位置不同外，还在于栈采用顺序存储结构而队列采用链式存储结构。（     ）

4. 算法效率分析时，基本运算是指算法中最关键和必不可少的运算。（     ）

5. 采用二叉链表存储一棵二叉树时，空闲指针域总是比使用了的指针域多。（     ）

6. 线性表中数据的逻辑顺序和存储顺序中是一致的。（      ）

7. 二叉树中的结点有两个子结点。（      ）

8. 快速排序是目前为止平均速度是快的内部排序算法，因此它是所有内部排序算法中最好的算法。（    ）

五、综合分析（共35分）

1. 已知二叉树的中序和后序周游序列分别是CBEDAFIGH和CEDBIFHGA，试构造该二叉树，并给出前序周游序列。（5分）

2．将序列(22, 25, 18, 7, 61, 19, 76, 30)的各元素依次插入一棵初始为空的二叉查找树中，请画出最后得到二叉查找树（5分）。

3. 将右图所示的完全二叉树调整为最大值堆。（5分）

4. 对某编码字符集｛a,b,c,d,e,f,g}，这些字符出现的频度分别为：20,14,7,13,20,13, 8。通过构建哈夫曼编码树，给出该字符集的哈夫曼编码。（5分）

5.对于初始状态为72，6，57，88，85，42，83，73，48，60的序列，请给出其前三次执行选择排序每一次的详细序列。

6. 对于初始状态为72，6，57，88，85，42，83，73，48，60的序列，给出Shell排序的详细操作步骤。

7. 设散列表容量为6（散列地址空间为0至5），给定表（15，27，18，55，24, 29），散列函数H（k）=k mod 5，采用线性探测法解决冲突，要求：（5分）

       （1）构造散列表；

（2）给出构造散列表过程中发生冲突的总次数。

六、算法编程（共7分）   

一个链表长度为n，头指针为head，用两个同样大小的一维数组V(1:m)和Next(1:m)分别保存该链表各结点的数据域值和指针域值。

  请编程实现: 将链表中的数据倒置。例如链表中原数据序列为（a, b, c, d,e），倒置后则为（e, d, c, b, a）。