​2008年下半年全国自考（数据结构）真题试卷

一、1.单项选择题

0. 如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是  (  )

A．栈
B．队列
C．树
D．图

1. 下面程序段的时间复杂度为  (  )  for(i=0;i＜m;i++)  for(j=0;j＜n;j++)  A[i][j]=i*j;

A．O(m²)
B．O(n²)
C．O(m*n)
D．O(m+n)

2. 在头指针为head的非空单循环链表中，指针p指向尾结点，下列关系成立的是  (  )

A．p—＞next==head
B．p—＞next—＞Next==head
C．p—＞next==NULL
D．p==head

3. 若以S和X分别表示进栈和退栈操作，则对初始状态为空的栈可以进行的栈操作序列是(  )

A．SXSSXXXX
B．SXXSXSSX
C．SXSXXSSX
D．SSSXXSXX

4. 两个字符串相等的条件是  (  )

A．串的长度相等
B．含有相同的字符集
C．都是非空串
D．串的长度相等且对应的字符相同

5. 如果将矩阵A_n×n的每一列看成一个子表，整个矩阵看成是一个广义表L，即L=((a₁₁，a₂₁，…，a_n1)，(a₁₂，a₂₂，…，a_n2)，…，(a_1n，a_2n，…，a_nn))，并且可以通过求表头head和求表尾tail的运算求取矩阵中的每一个元素，则求得a₂₁的运算是  (  )

A．head(tail(head(L)))
B．head(head(head(L)))
C．tail(head(tail(L)))
D．head(head(tail(L)))

6. 已知一棵含50个结点的二叉树中只有一个叶子结点，则该树中度为1的结点个数为(  )

A．O
B．1
C．48
D．49

7. 在一个具有n个顶点的有向图中，所有顶点的出度之和为D_out，则所有顶点的入度之和为(  )

A．D_out
B．D_out-1
C．D_out+1
D．n

8. 如图所示的有向无环图可以得到的拓扑序列的个数是  (  )

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

9. 如图所示的带权无向图的最小生成树的权为  (  )

A．51
B．52
C．54
D．56

10. 对长度为n的关键字序列进行堆排序的空间复杂度为  (  )

A．O(log₂n)
B．O(1)
C．O(n)
D．O(n*log₂n)

11. 已知用某种排序方法对关键字序列(51,35,93,24,13,68,56,42,77)进行排序时，前两趟排序的结果为  (35,51,24,13,68,56,42,77,93)  (35,24,13,51,56,42,68,77,93)  所采用的排序方法是  (  )

A．插入排序
B．冒泡排序
C．快速排序
D．归并排序

12. 已知散列表的存储空间为T[0…18]，散列函数H(key)=key%17，并用二次探测法处理冲突。散列表中已插入下列关键字：T[5]=39，T[6]=57和T[7]=7，则下一个关键字23插入的位置是 (  )

A．T[2]
B．T[4]
C．T[8]
D．T[10]

13. 适宜进行批量处理的文件类型是  (  )

A．顺序文件
B．索引顺序文件
C．散列文件
D．多关键字文件

14. VSAM文件的索引结构为  (  )

A．B+树
B．二叉排序树
C．B-树
D．最优二叉树

二、2.填空题

0. 如果某算法对于规模为n的问题的时间耗费为T(n)=3n³，在一台计算机上运行时间为t秒，则在另一台运行速度是其64倍的机器上，用同样的时间能解决的问题规模是原问题规模的______倍。

1. 将两个长度分别为m和n的递增有序单链表，归并成一个按元素递减有序的单链表，可能达到的最好的时问复杂度是______。

2. 已知循环队列的存储空间大小为m，队头指针front指向队头元素，队尾指针rear指向队尾元素的下一个位置，则在队列不满的情况下，队列的长度是______。

3. 字符串"sgabacbadfgbacst"中存在有______个与字符串"ba"相同的子串。

4. 假设以列优先顺序存储二维数组A[5][8]，其中元素A[0][0]的存储地址为LOC(a₀₀)，且每个元素占4个存储单元，则数组元素A[i][j]的存储地址为______ 。

5. 假设用＜x,y＞表示树的边(其中s是y的双亲)，已知一棵树的边集为{＜b,d＞，＜a,b＞，＜c,g＞，＜c,f＞，＜c,h＞，＜a,c＞)，该树的度是______。

6. n个顶点且含有环路的无向连通图中，至少含有______条边。

7. 在一般情况下用直接插入排序、选择排序和冒泡排序的过程中，所需记录交换次数最少的是______。

8. 和二分查找相比，顺序查找的优点是除了不要求表中数据元素有序之外，对______结构也无特殊要求。

9. 顺序文件中记录存放的物理顺序和______顺序一致。

三、3.解答题

0. 由森林转换得到的对应二叉树如图所示，写出原森林中第三棵树的前序序列和后序序列。
  
  前序序列：
  后序序列：

1. 图的邻接表的类型定义如下所示：
  #define MaxVertexNum 50
  typedef struct node{
   int adjvex;
   struct node*next;
  }EdgeNode;
  typedef struct{
   VertexType vertex;
   EdgeNode*firstedge;
  }VertexNode;
  typedef VertexNode A djList[MaxVertexNum];
  typedef struct{
   AdjList adjiist;
   int n,e;
  }ALGraph;
  为便于删除和插入图的顶点的操作，可将邻接表的表头向量定义为链式结构，两种定义的存储表示实例如下图所示，请写出重新定义的类型说明。
 

2. 某类物品的编号由一个大写英文字母及2位数字(0…9)组成，形如E32。运用基数排序对下列物品编号序列进行按字典序的排序，写出每一趟(分配和收集)后的结果。
  E13,A37,F43,B32,B47,E12,F37,B12
  第一趟：
  第二趟：
  第三耥：

3. (1)画出对表长为13的有序顺序表进行二分查找的判定树；
  (2)已知关键字序列为(12,14,16,21,24,28,35,43,52,67,71,84,99)，写出在该序列中二分查找37时所需进行的比较次数。

四、4.算法阅读题

0. 已知线性表的存储结构为顺序表，阅读下列算法，并回答问题：
  (1)设线性表L=(21,-7,-8,19,0，-11,34,30，-10)，写出执行f30(&L)后的L状态；
  (2)简述算法f30的功能。
  void f30(SeqList*L){
   int i,j;
   for(i=j=0;i＜L—＞length;i++)
    if(L—＞data[i]＞=0){
      if(i!=j)L—＞data[j]=L—＞data[i];
      j++;
     }
    L—＞length=j;
  }

1. 阅读下列算法，并回答问题：
  (1)Q、Q1和Q2都是队列结构，设队列Q=(1,0,-5,2,-4,-6,9)，其中1为队头元素，写出执行f31(&Q，&Q₁，&Q₂)之后队列Q、Q₁和Q₂的状态；
  (2)简述算法f31的功能。
  (注：InitQueue、EnQueue、DeQueue和QueueEmpty分别是队列初始化、入队、出队和判队空的操作)
  void f31(Queue*Q,Queue*Q₁,Queue*Q₂){
    int e;
    InitQueue(Q₁);
    InitQueue(Q₂);
    while(!QueueEmpty(Q)){
     e=DeQueue(Q);
     if(e＞=0)EnQueue(Q₁,e);
     else EnQueue(Q₂,e);
    }
  }

2. 阅读下列算法，并回答问题：
  (1)假设串由合法的英文字母和空格组成，并以""作结束符。设串，写出f32(s)的返回值；
  (2)简述算法f32的功能。
  int f32(char*s){
   int i,n,inword;
   n=inword=0;
   for(i=0;s[i]!="";i++)
   
       inword=0;
    return n;
  }

3. 阅读下列对正整数关键字序列L操作的算法，并回答问题：
  (1)设L=(28,19,27,49,56,12,10,25,20,50)，写出f33(L,4)的返回值；
  (2)简述函数f33的功能。
  int Partition(SeqList*L,int low,int high);
  //对L[low…high]做划分，返回基准记录的位置，并使左部的关键字
  //都小于或等于基准记录的关键字，右部的关键字都大于基准记录的关键字
  int f33(SeqList L,int k){
   int low,high,pivotpos;
   low=1;
   high=L.length;
   if(k＜low||k＞high)
    return-1;
   do {
    pivotpos=Partition(&L,low,high)；//调用快速排序的划分算法
    if(pivotpos＜k)
      low=pivotpos+1;
    else if(pivotpos＞k)
       high=pivotpos-1;
   }while(pivotpos!=k);
   return L.data[pivotpos];
  }

五、5.算法设计题

0. 二叉排序树的类型定义如下：
  typedef struet BSTNode{//二叉排序树的结点结构
    int data; //数据域
    struct BSTNode*lchild,*rchild;//左、右孩子指针
  }BSTNode,*BSTree;
  设计递归算法，统计一棵二叉排序树T中值小于a的结点个数。