2012.1数据结构试卷(A)

1、以下数据结构中，哪一个是线性结构？（    ）

A．广义表        B．二叉树     C．稀疏矩阵        D．串

2、若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（    ）(1<=i<=n+1)。

A．O(0)          B．O(1)        C．O(n)            D．O(n2) 

3、输入序列为ABC，输出序列为BCA时，经过的栈操作为（    ）。

A．push, pop, push, pop, push, pop        B．push, push, pop, push, pop, pop

    C．push, push, pop, pop, push, pop        D．push, pop, push, push, pop, pop

4、模式串t=‘abcaabbcabcaabdab’，该模式串的next数组的值为（    ）。

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

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

5、设S为一个长度为n的字符串，其中的字符各不相同，则S中的互异的非平凡子串（非空且不同于S本身的串）的个数为（    ）。

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

6、假设以行序为主序存储二维数组A=array[0..99，0..99]，设每个数据元素占2个存储单元，基地址为10，则A[5，5]=（    ）。

   A．808        B．818       C．1010       D．1020

7、某二叉树中序序列为A,B,C,D,E,F,G，后序序列为B,D,C,A,F,G,E，则前序序列是：（    ）。

A．E,G,F,A,C,D,B   B．E,A,C,B,D,G,F   C．E,A,G,C,F,B,D   D．上面的都不对

8、根据使用频率为5个字符设计的哈夫曼编码不可能是（    ）。

A．0，100，101，110，111     B．0000，0001，001，01，1

C．000，001，010，011，11     D．00，01，10，110，111

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

A．15            B．25            C．35            D．313

10、以下序列不是堆的是（    ）。

A．(100,85,98,77,80,60,82,40,20,10,66)      B．(100,98,85,82,80,77,66,60,40,20,10)

C．(10,20,40,60,66,77,80,82,85,98,100)      D．(100,85,40,77,80,60,66,98,82,10,20)

二、应用题（本大题共 5 小题，每小题6分，共30分）

1、假设一棵二叉树的层次次序（按层次递增顺序排列，同一层次自左向右）为ABECFGDHI，中序序列为BCDAFEHIG。请画出该二叉树。

2、举例说明顺序队的“假溢出”现象，简要叙述循环队列的数据结构，并说明判定循环队列的队空条件和队满条件。

3、已知下列字符A、B、C、D、E、F、G的权值分别为3、12、7、4、2、8，11，试填写出其对应哈夫曼树HT的存储结构的初态（见下表左半部分）和终态（见下表右半部分）。（注意：生成的哈夫曼树权值左孩子小右孩子大，权值相等时编号小的先取）

5、给出一组关键字T=(12,2,16,30,8,28,4,10,20,6,18)，写出用下列算法从小到大排序时第一趟结束时的序列。

(1)希尔排序（第一趟排序的增量为5）；

(2)快速排序（选第一个记录为枢轴（分隔））。

三、程序填空题（本大题共 5 小题，共15个空白处，每空2分，共30分，注意：每空只填一个语句）

1、对不带头结点的单链表进行就地逆置。该算法用L返回逆置后的链表的头指针。

void  reverse(linklist &L)

{

p=null；q=L；

while(q！=null)

{

   (1)      ; ∥暂存后继

q->next=p；

p=q；

    (2)      ; ∥待逆置结点

              }

              (3)      ; ∥头指针仍为L

         }

2、Search_Bin函数，实现在一个递增有序数组ST中采用折半查找法确定元素位置的算法。

int Search_Bin(int *ST,int n,int key)

{//在有序表ST中折半查找其关键字等于key的数据元素。若找到，则函数值为该元

//素在表中的位置，否则为-1。n为有序表的长度。

           int low,high,mid;

           low = 1;    ∥置区间初值

           high = n;

           while(    (4)    )

           {

             mid = (low + high)/2 ;

             if (    (5)    )  

                   return mid;

             else if (key < ST[mid] ) 

                         (6)      ; 

             else

                  low = mid + 1;   

           }

           return -1;  ∥顺序表中不存在待查元素

     }

3、下列算法为奇偶交换排序，思路如下：第一趟对所有奇数的i，将a[i]和a[i+1]进行比较，第二趟对所有偶数的i，将a[i]和a[i+1]进行比较，每次比较时若a[i]>a[i+1]，将二者交换；以后重复上述二趟过程，直至整个数组有序（从小到大）。注意：待排序的元素存储在数组下标1…n的位置。

void oesort (int a[n])

{

int flag,i,t;

 do 

  {

flag=0;

for(i=1; i if(a[i]>a[i+1])

      {

flag=1;

t=a[i+1]; 

a[i+1]=a[i]; 

      (7)     ;

}

for      (8)     

if (a[i]>a[i+1])

      {

flag=1

t=a[i+1]; 

a[i+1]=a[i]; 

a[i]=t;

}

  }while       (9)     ;

}  

4、图的广度优先遍历

    void BFSTraverse(Graph G, Status (*Visit)(int v )) {

  // 按广度优先非递归遍历图G。使用辅助队列Q和访问标志数组visited，数组元素的

//值设为FALSE表示对应该结点未访问，设为TRUE则为已经访问。

  QElemType v,w;

  Queue Q;

  QElemType u;

for (v=0; v  InitQueue(Q);                     // 置空的辅助队列Q

for (v=0; v    if (!visited[v]) {              

      visited[v] = TRUE;  Visit(v); 

            (11)      ;                

      while (!QueueEmpty(Q)) {

             (12)      ;                   

        for (w=FirstAdjVex(G, u);  w>=0;  w=NextAdjVex(G, u, w))

// FirstAdjVex(G, u)取结点u的第一个相邻结点，NextAdjVex(G, u, w)取u的下一个//相邻结点

          if (      (13)      ) {        

            visited[w] = TRUE;  Visit(w);

            EnQueue(Q, w);        

          }//if   

      }//while                       

    }//if

} // BFSTraverse

其中队列Queue数据结构的基本操作如下：

InitQueue(Queue &Q);   //构造一个空队列Q

QueueEmpty(Queue Q);  //若Q为空队列返回TRUE，否则返回FALSE

QueueLength(Queue Q);  //返回队列Q的元素个数

EnQueue(Queue &Q, QElemType e);    //插入元素e作为队列Q的队尾元素

DeQueue(Queue &Q, QElemType &e);  //删除队列Q的队头元素，并用e返回其值

假定上述操作已经实现，直接调用即可。

5、以下程序是二叉链表树中序遍历的非递归算法，请填空使之完善。二叉树链表的结点类型的定义如下：

 typedef struct node   //C语言描述

    {char data; struct  node *lchild,*rchild;}*bitree;

void vst(bitree bt)                     //bt为根结点的指针

    { bitree  p; p=bt;  initstack(s);         //初始化栈s为空栈  

while(p || !empty(s))                 //栈s不为空

 if(p) { 

push (s,p);                  //p入栈

      (14)      ;          //沿左子树向下

} 

else { 

p=pop(s);                   //栈顶元素出栈

printf(“%c”,p->data);

      (15)      ; 

} 

} 

四、算法设计题（本大题共 2小题，每小题10分，共20分。请先简要说明算法思想，然后写出算法的源代码实现）

1、给定（已生成）一个带表头结点的单链表，设head为头指针，结点的结构为(data,next)，试写出算法：按递增次序输出单链表中各结点的数据元素，并释放结点所占的存储空间。(要求：不允许使用数组作辅助空间)

单链表定义如下：

typedef struct LNode{

int           data;

struct LNode  * next;

}LNode, * LinkList;

统一使用如下函数名：void  MiniDelete(LinkedList  head)

2、已知一二叉树中结点的左右孩子为lchild和rchild，p指向二叉树的某一结点。请用C语言编一个非递归函数PostFirst (p)，求p所对应子树（即以p为根的子树）的第一个后序遍历结点。

二叉树采用二叉链表表示，定义如下：

typedef struct BiTNode{

TElemType      data;

struct BiTNode  * lchild, * rchild;

} BiTNode, * BiTree;

统一使用如下函数名：BiTree PostFirst(p)