数据结构期末试卷(A)2012

姓名       

《数据结构》期末考试题A卷

一、选择题（2*20=40分）

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

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

2、以下与数据的存储结构无关的术语是（   ）。

A．顺序队列       B. 链表        C. 有序表          D.  链栈

3、一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（   ）。

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

4、链接存储的存储结构所占存储空间（   ）。

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

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

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

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

5、设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次进入栈S，一个元素出栈后即进入Q，若6个元素出队的序列是e2、e4、e3、e6、e5和e1，则栈S的容量至少应该是（　）。

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

6、数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素个数的公式为（  ）。

A．r-f             B．(n+f-r)%n       C．n+r-f           D．（n+r-f)%n

7、串是一种特殊的线性表，其特殊性体现在（  ）。

  A．可以顺序存储               B．数据元素是一个字符      

C．可以链式存储               D．数据元素可以是多个字符若

8、串的长度是指（  ）。

A．串中所含不同字母的个数       B．串中所含字符的个数

C．串中所含不同字符的个数       D．串中所含非空格字符的个数

9、把一棵树转换为二叉树后，这棵二叉树的形态是（   ）。              

A．唯一的                          Ｂ．有多种

C．有多种，但根结点都没有左孩子    Ｄ．有多种，但根结点都没有右孩子

10、一棵完全二叉树上有1001个结点，其中叶子结点的个数是（  ）。

A．250         B． 500          C．254        D．501

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

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

12、具有n个顶点的有向图最多有（   ）条边。  

A．n              B．n(n-1)         C．n(n+1)        D．n2

13、深度优先遍历类似于二叉树的（   ）。

A．先序遍历      B．中序遍历        C．后序遍历      D．层次遍历

14、对n个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为（   ）。

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

15、当在一个有序的顺序表上查找一个数据时，既可用折半查找，也可用顺序查找，但前者比后者的查找速度（   ）。                      

A．必定快                            B．不一定    

C．在大部分情况下要快                D．取决于表递增还是递减

16、对22个记录的有序表作折半查找，当查找失败时，至少需要比较（   ）次关键字。

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

17、从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置上的方法，这种排序方法称为（   ）。

A．归并排序       B．冒泡排序        C．插入排序        D．选择排序

18、对n个不同的关键字由小到大进行冒泡排序，在下列（   ）情况下比较的次数最多。

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

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

19、快速排序在下列（   ）情况下最易发挥其长处。

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

B．被排序的数据已基本有序   

C．被排序的数据完全无序         

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

20、下述几种排序方法中，（   ）是稳定的排序方法。

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

二、填空题（2*10=20分）

2、数据结构包含三个方面的内容，即数据的（     ）、（     ）和对数据进行的运算或操作。（逻辑结构，物理结构）

3、数据结构中有四种基本结构，它们是集合、（       ）、（       ）、和图形结构。（线性结构，树形结构）

4、数据在计算机内的表示称为数据的（      ）。 （物理结构）

5、在数据的物理结构中，结点可以有四种存储方式，分别是（       ）、（       ）、索引存储方式和散列存储方式。     （顺序存储方式，链式存储方式）

6、在线性结构中，第一个结点没有（     ），最后一个结点没有（        ）。 （前驱结点，后继结点）

7、线性结构中元素之间存在（        ）关系，树形结构中存在（      ）关系，图形结构中存在多对多关系。   （一对一，一对多）

8、算法是描述计算机求解问题的操作过程，必须满足五个性质，即（      ）、（      ）、可行性、输入性和输出性。    （有穷性，确定性）

9、算法分析的目的是分析算法的效率以求改进。算法分析的两个主要方面是（       ）和（       ）。    （时间复杂度，空间复杂度）

10、在正确性、有穷性、可行性、确定性中，（ 正确性      ）不是算法的基本特征。

三、应用题（共40分）

1、设双向循环链表中结点的数据域、前驱和后继指针域分别为data,pre和next,试写出在指针p 所指结点之前插入一s结点的C语言描述语句。（10分）

{p=A；                   ∥p为A链表的工作指针，本题假定A和B均无头结点。

 pre=p；                 ∥pre记住每趟比较中A链表的开始结点。

 q=B；                  ∥q是B链表的工作指针。

 while（p && q）

   if（p->data==q->data） {p=p->next；q=q->next；}

   else{pre=pre->next；p=pre；                    ∥A链表新的开始比较结点。

        q=B；}                                    ∥q从B链表第一结点开始。

if（q==null）return（1）；                       ∥B是A的子序列。

else   return（0）；                            ∥B不是A的子序列。

}                                               ∥算法结束。

2、设一棵二叉树的先序序列： A B D F C E G H ，中序序列： B F D A G E H C，画出这棵二叉树。（10分）

3、已知图的邻接矩阵如图所示。试分别画出自顶点1出发进行遍历所得的深度优先生成树和广度优先生成树。（20分）