​全国自考（数据结构）模拟试卷3

一、1.单项选择题

0. 设有两个串p和q，求q在p中首次出现的位置的运算称为(  )

A．连接
B．模式匹配
C．求子串
D．求串长

1. 对于shell排序来说，给定的一组排序数值为  49,38,65,97,13,27,49,55,04  则第二趟排序后的结果为(  )

A．04,13,27,49,49,38,55,65,76,97
B．04,13,27,38,49,49,55,65,76,97
C．13,04,49,38,27,49,55,65,97,76
D．13,27,49,55,04,49,38,65,97,76

2. 将上万个一组无序并且互不相等的正整数序列，存放于顺序存储结构中，采用(  )方法能够最快地找出其中最大的正整数。

A．快速排序
B．插入排序
C．选择排序
D．归并排序

3. 长度为12的按关键字有序的查找表采用顺序组织方式。若采用二分查找方法，则在等概率情况下，查找失败时的ASL值是(  )

A．13850
B．62/13
C．14580
D．49/13

4. 一个具有N个顶点的有向图最多有(  )条边。

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

5. Aarr和Barr两个数组的说明如下：  VAR Aarr:Array[O··7]of char;     Barr:Array[-5··2,3,··8]of char; 这两个数组分别能存放的字符的最大个数是(  )

A．7和35
B．1和5
C．8和48
D．1和6

6. 对于一棵具有三个结点的二叉树，共有(  )种不同的树的形态。

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

7. 设一个数组中，行下标i的范围是从1到8，列下标的范围是从1到10，假设此数组的初始存储地址是A，则如果将此数组按照列优先的顺序连续存放，则元素Q[5][8]的起始地址是(  )

A．1
B．23
C．24
D．529

8. 具有24个记录的序列，采用冒泡排序最少的比较次数是(  )

A．1
B．23
C．24
D．529

9. 下列说法中正确的是(  )

A．任何一棵二叉树中至少有一个结点的度为2
B．任何一棵二叉树中的每个结点的度为2
C．任何一棵二叉树中的度肯定等于2
D．任何一棵二叉树中的度可以小于2

10. 二分查找算法要求被查找的表是(  )

A．键值有序的链表
B．键值不一定有序的链表
C．键值有序的顺序表
D．键值不一定有序的顺序表

11. 下面的程序在执行时，S语句共被执行了(  )次。
  i=1;
  while(i＜=n)
   {for(j=i;j＜n;j++)
    {  S ;
      }
    i=i+1;
    }

12. 堆(Heap)是(  )

A．完全二叉树
B．线性表
C．二叉排序树
D．平衡二叉树

13. 下面程序的时间复杂性是(  )  for (i=1;i＜=n;i++)    for(j=1;j＜=m;j++)     {A[i][j]=i*j;     }

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

14. 与数据元素本身的形式、内容、相对位置、个数无关的是数据的(  )

A．存储结构
B．存储实现
C．逻辑结构
D．运算实现

二、2.填空题

0. 对无向图，其邻接矩阵是一个关于______对称的矩阵。

1. 多维数组和广义表是一种非常复杂的非线性结构，它们的逻辑特点是______。

2. 18.已知L是无表头结点的单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。
(1)在P结点之前插入S结点的语句序列是______；
(2)在表首插入S结点的语句序列是______。
  a P—＞nex=S      b P—＞next=P—＞next—＞next
  c P—＞next=S—＞next  d S—＞next=P—＞next
  e S—＞next=L      f Q=P
  g while(P—＞next!=Q＞P=P—＞next
  h while(P—＞next!=NULL)P=P—＞next
  i P=L  j L=S

3. 在散列技术中，处理冲突的方法有：______和______。

4. 如果我们定义一个长度为N的串空间，则它最多能放______个字符。

5. 假设在图G中任意的顶点设为v_i，此顶点对应的度为D(v_i)，此图的顶点数为n。则边数e和度数之间的关系为______。

6. ______的邻接矩阵不一定是不对称的。

7. 在串的匹配运算中，一般我们将主串称为______，而将子串称为______。

8. 当所有结点的权值都相等时，用这些结点构造的二叉排序树上只有______。

9. N个顶点的连通图，至少有______条边。

三、3.解答题

0. 已知有一个关键字序列为(99,38,309,08,27,145,67,96,186,122,71,63,59)，假设用散列函数为h(key)=key%13，现在如果采用拉链法解决冲突问题，请画出这组关键字的散列表。

1. 已知有一关键字序列为{486,79,596,34,900,120,789,179,703,307)，如果我们采用基数排序方法对此序列进行排序(按照升序排列)，请给出每一趟的排序结果。

2. 写出二分查找的递归算法。

3. 已知连通图如下：
  
  分别以邻接矩阵的邻接表实现存储，试给出该图的邻接矩阵和邻接表，若从顶点B出发对该图进行遍历，分别给出一个按深度优先搜索和广度优先搜索的顶点序列。

四、4.算法阅读题

0. 以下运算实现在链队上的入队列，请在______处用适当的语句予以填充。
  void EnQueue(QueptrTp*lq,DataType x)
  { LqueueTp*P;
    p=(LqueueTp*)malloc(sizeof(LqueueTp));
    ______=x;
    p—＞next=NULL;
    (1q—＞rear)—＞next=______;
    ______;
  }

1. 以下运算实现在链栈上的初始化，请在______处用适当的语句予以填充。
  void InitStack(LStackTp*ls){______;)

2. 以下算法在指针T所指的二叉排序树上的查找键值等于K的结点。成功时回送指向该结点的指针；否则回送空指针。请分析程序，并在______上填充合适的语句。
  bitreptr search_bst(bitreptr T,keytype K)
  { if(T==NULL)return(NULL);
   else switch
    { case T—＞key==K:______;
     case______: return(search_bst(T—＞lchild,K));
     case______: return(search_bst(T—＞rchild,K));
    }
  }

3. 以下为顺序表的插入运算，分析算法，请在______处填上正确的语句。
  void insert_sqlist(sqlist L,datatype x,int i)／*将X插人到顺序表L的第i-1个位置*／
  { if(L.1ast==maxsize)error("表满");
  if((i＜1)||(i＞L.last+1))error("非法位置");
  for(j=L.last;j≥i;j--)
  L.data[i-]=X;
  L.last=L.last+1;
  }

五、5.算法设计题

0. 写出向某个有序文件中插入一个记录的程序。