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

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

32． 以下算法在指针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));

       }

  }

33． 以下为顺序表的插入运算，分析算法，请在______处填上正确的语句。

void insert_sqlist(sqlist L,datatype x,inti)／*将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;

  }

31． 以下运算实现在链栈上的初始化，请在______处用适当的语句予以填充。

void InitStack(LStackTp*ls){______;)

29． 已知连通图如下：

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

30． 以下运算实现在链队上的入队列，请在______处用适当的语句予以填充。

void EnQueue(QueptrTp*lq,DataType x)

  {LqueueTp*P;

      p=(LqueueTp*)malloc(sizeof(LqueueTp));

      ______=x;

      p—＞next=NULL;

      (1q—＞rear)—＞next=______;

      ______;

  }

28． 写出二分查找的递归算法。

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

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

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

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

22． ______的邻接矩阵不一定是不对称的。

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

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

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

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

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

18． 已知L是无表头结点的单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。

不是尾元结点，试从下列提供的答案中选择合适的语句序列。

(1)在P结点之前插入S结点的语句序列是______；

(2)在表首插入S结点的语句序列是______。

  a P—＞nex=S           b P—＞next=P—＞next—＞next

  cP—＞next=S—＞next   d S—＞next=P—＞next

  e S—＞next=L          f Q=P

  gwhile(P—＞next!=Q＞P=P—＞next

  hwhile(P—＞next!=NULL)P=P—＞next

  i P=L   j L=S

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

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

13． 堆(Heap)是( )

14． 下面程序的时间复杂性是(  )

for (i=1;i＜=n;i++)

for(j=1;j＜=m;j++)

{A[i][j]=i*j;

}

12． 下面的程序在执行时，S语句共被执行了(  )次。

i=1;

while(i＜=n)

{for(j=i;j＜n;j++)

{ S; 

} 

i=i+1; 

}

10． 下列说法中正确的是( )

11． 二分查找算法要求被查找的表是( )

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

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

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

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

6． Aarr和Barr两个数组的说明如下：

VAR Aarr:Array[O··7]of char; 

Barr:Array[-5··2,3,··8]of char; 

这两个数组分别能存放的字符的最大个数是(  )

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

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

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

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