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

一、1.单项选择题

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

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

1. 已知指针p和q分别指向某单链表中第一个结点和最后一个结点。假设指针s指向另一个单链表中某个结点，则在s所指结点之后插入上述链表应执行的语句为  (  )

A．q—＞next=s—＞next;s—＞next=p;
B．s—＞next=P;q—＞next=s—＞next;
C．p—＞next=s—＞next;s—＞next=q;
D．s—＞next=q;p—＞next=s—＞next;

2. 在计算机内实现递归算法时所需的辅助数据结构是  (  )

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

3. 假设以数组A[m]存放循环队列的元素。已知队列的长度为length，指针rear指向队尾元素的下一个存储位置，则队头元素所在的存储位置为  (  )

A．(rear-length+m+1)%m
B．(rear-length+m)%m
C．(rear-length+m-1)%m
D．(rear-length)%m

4. 通常将链串的结点大小设置为大于1是为了  (  )

A．提高串匹配效率
B．提高存储密度
C．便于插入操作
D．便于删除操作

5. 带行表的三元组表是稀疏矩阵的一种  (  )

A．顺序存储结构
B．链式存储结构
C．索引存储结构
D．散列存储结构

6. 表头和表尾均为空表的广义表是  (  )

A．()
B．(())
C．((()))
D．(()，())

7. 用二叉链表表示具有n个结点的二叉树时，值为空的指针域的个数为  (  )

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

8. 为便于判别有向图中是否存在回路，可借助于  (  )

A．广度优先搜索算
B．最小生成树算法
C．最短路径算
D．拓扑排序算法

9. 连通网的最小生成树是其所有生成树中  (  )

A．顶点集最小的生成树
B．边集最小的生成树
C．顶点权值之和最小的生成树
D．边的权值之和最小的生成树

10. 按排序过程中依据的原则分类，快速排序属于  (  )

A．插入类的排序方法
B．选择类的排序方法
C．交换类的排序方法
D．归并类的排序方法

11. 下列关键字序列中，构成小根堆的是  (  )

A．{84,46,62,41,28,58,15,37}
B．{84,62,58,46,41,37,28,15}
C．{15,28,46,37,84,41,58,62}
D．{15,28,46,37,84,58,62,41}

12. 在长度为32的有序表中进行二分查找时，所需进行的关键字比较次数最多为(  )

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

13. 假设在构建散列表时，采用线性探测解决冲突。若连续插入的n个关键字都是同义词，则查找其中最后插入的关键字时，所需进行的比较次数为  (  )

A．n-1
B．n
C．n+i
D．n+2

14. 散列文件也称为  (  )

A．顺序文件
B．索引文件
C．直接存取文件
D．间接存取文件

二、2.填空题

0. 数据的逻辑结构描述数据元素之间的______，与存储方式无关。

1. 在一个长度为100的顺序表中删除第10个元素时，需移动______个元素。

2. 队列的队尾位置通常是随着______操作而变化的。

3. 两个空串联接得到的串的长度为______。

4. 设对称矩阵A压缩存储在一维数组B中，其中矩阵的第一个元素a11存储在B[0]，元素a52存储在B[11]，则矩阵元素a36存储在[B______]中。

5. 已知一棵哈夫曼树含有60个叶子结点，则该树中共有______个非叶子结点。

6. 如图所示的有向图中含有______个强连通分量。

7. 已知一组关键字为{15,36,28,97,24,78,47,52,13,86}，其中每相邻两个关键字构成一个有序子序列。对这些子序列进行一趟两两归并的结果是______。

8. 从空树起，依次插入关键字11,27,35,48,52,66和73构造所得的二叉排序树，在等概率查找的假设下，查找成功时的平均查找长度为______。

9. 控制区间和控制区域是______文件的逻辑存储单位。

三、3.解答题

0. 利用广义表的head和tail操作，可从广义表
  L=((a,b)，(c,d))
  中分解得到原子c，其操作表达式为
  head(head(tail(L)));
  分别写出从下列广义表中分解得到b的操作表达式。
  (1)L1=(a,b,c,d);
  (2)L2=(((a),(b),(c),(d)))。

1. 画出与如图所示森林对应的二叉树。

2. 已知有向图G的定义如下：
  G=(V,E)
  V={a,b,c,d,e}
  E={＜a,b＞，＜a,c＞，＜b,c＞，＜b,d＞，＜c,d＞，＜e,c＞，＜e,d＞)
  (1)画出G的图形；
  (2)写出G的全部拓扑序列。

3. 已知3阶B-树如图所示。
  (1)画出将关键字88插入之后的B-树；
  (2)画出将关键字47和66依次插入之后的B一树。
 

四、4.算法阅读题

0. 假设某个不设头指针的无头结点单向循环链表的长度大于1，S为指向链表中某个结点的指针。算法f30的功能是，删除并返回链表中指针S所指结点的前驱。请在空缺处填入合适的内容，使其成为完整的算法。
  typedef struct node{
   DataType data;
   struct node *next;
  }*LinkList;
  DataType f 30(LinkList s){
   LinkList pre,p;
   DataType e;
   pre=s;
   p=s—＞next;
   while(  (1)  ){
   pre=p;
    (2)  ；
   }
   pre—＞next=  (3)  ;
   e=p—＞data;
   free(p);
   return e;
  }

1. 算法f31的功能是清空带头结点的链队列Q。请在空缺处填入合适的内容，使其成为一个完整的算法。
  typedef struct node{
   DataType data;
   struct node *next;
  }QueueNode;
  typedef struet{
   QueueNode*front; //队头指针
   QueueNode*rear; //队尾指针
  }LinkQueue;
  void f31(LinkQueue*Q){
   QueueNode*p,*s;
   p=  (1)  ;
   while(P!=NULL){
    s=p;
    p=p—＞next;
    free(s);
   }
     (2)  =NULL;
    Q—＞rear=  (3)  ;
  }

2. 假设采用动态存储分配的顺序串HString作为串的存储结构。该类型实现的串操作函数原型说明如下：
  void strinit(HString s); //置s为空串
  int strlen(HString s); //求串s的长度
  void strcpy(HString to,HString from); //将串from复制到串to
  void streat(HString to,HString from); //将串from联接到串to的末尾
  int strcmp(HString s1,HString s2);
   //比较串s1和s2的大小，当s1＜s2，s1=s2或s1＞s2时，
   //返回值小于0，等于0或大于0
  HString substr(HString s,int i,int m);
   //返回串S中从第i(0≤i≤strlen(s)-m)个字符起长度为m的子串阅读下列算法f32，并回答问题：
  (1)设串S="abcdabcd"，T="bcd"，V="bcda"，写出执行f32(S,T,V)之后的S；
  (2)简述算法f32的功能。
  void f 32(HString S,HString T,HString V){
   int m,n,pos,i;
   HString news;
   strinit(news);
   n=strlen(S);
   m=strlen(T);
   pos=i=0;
   while(i＜=n-m){
   if(strcmp(substr(S,i,m)，T)!=0)i++;
   else{
    strcat(news,substr(S,pos,i-pos));
    strcat(news,V);
    pos=i=i+m;
   }
   }
   strcat(news,substr(S,pos,n—pos));
   strcpy(S,news);
  }

3. 假设以二叉链表作为二叉树的存储结构，其类型定义如下：
  typedef struct node{
   char data;
   struct node*lchild,*rchild; //左右孩子指针
  }BinTNode,*BinTree;
  阅读下列算法f33，并回答问题：
  (1)已知如图所示的二叉树以T为指向根结点的指针，画出执行f33(T)后的二叉树；
  (2)简述算法f 33的功能。
  void f 33(BinTtee T){
   if(T){
    f 33(T—＞lchild);
    f 33(T—＞rchild);
    if((!T—＞lchild)&&L T—＞rchild){
     T—＞lchild=T—＞rchild;
     T—＞rchild=NULL;
    }
   }
  }

五、5.算法设计题

0. 假设以带头结点的单链表表示有序表，单链表的类型定义如下：
  typedef struct node{
   int data;
   struct node*next;
  }LinkNode,*LinkList;
  编写算法，输入n个整数构造一个元素值互不相同的递增有序链表(即相同的整数只取一
个)。算法的函数原型给定为
  LinkList f 34(int n);