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

33． 以下为求单链表表长的运算，分析算法，请在______处填上正确的语句。

int length_lklist(lklist head)   /*求表的长度。 */

  {______;

    j=0;

   while(p—＞next!=NULL)

  {______;

    j++;}

   return(j);

  }   /*回传表长*/

34． 从键盘上输入若干字符(每行长度不等)，输入后把它们存储到一磁盘文件中，再从该文件中读出这些数据，将其中小写字母转换成大写字母再进行屏幕输出。

31． 以下算法实现若开散列表HP中存在键值为K的结点，则将其删除。请分析程序，并在______上填充合适的语句。

void delete_openhash(keytype K,openhash HP)

  {i=H(K);

    if(HP[i]==NULL)return;   /*空表则退出*/

     p=HV[i];

     if(p—＞key==K){______=p—＞next;free(p);return;)

                              /*表首结点为待删除结点时的删除*/

  while(p—＞next!=NULL)     /*其他情况下的删除*/

    { q=p;p=p—＞next;

       if(p—＞key==K){______=p—＞next;delete(p);return;)

    }

  }

32． 以下运算实现在循环队上的出队列，请在______处用适当的语句予以填充。

int OutCycQueue(CycqueueTp*sq,DataType*x)

      { if(sq—＞front==______){error("队空");return(0);)

        else{______;

             ______;

             return(1);

            }

      }

30． 以下为单链表按序号查找的运算，分析算法，请在______处填上正确的语句。

pointer find_lklist(1klist head,int i)

  { p=head;j=0;

     while(______)

      { p=p—＞next;j++;}

        if(i==j)return(p);

        else return(NULL);

  }

29． 已知一棵二叉树按照顺序结构存储，其存储结构如下：

则请回答如下问题：

(1)请画出此二叉树的树形结构。

(2)请写出此二叉树的前序遍历、中序遍历和后序遍历序列。

(3)此二叉树的高度是多少? 

(4)结点F的双亲、孩子，以及祖先分别是什么?

(5)此树中，度数为1的结点共有几个?分别是哪几个?

(6)结点C有左孩子吗?如果有左孩子，则C的左孩子的编号应该是什么?

26． 对于下面用三元组表示的稀疏矩阵，请分别写出它们所对应的稀疏矩阵。

28． 假设有一个长度为n的有序序列，在进行查找时，可以借助二叉树来进行，请结合二叉树的性质来分析二分查找的最坏性能和平均性能。

27． 假设有下面所示的稀疏矩阵，请写出其三元组表(按行优先的顺序)。

24． 在单链表中，除了首元结点外，任一结点的存储位置是由______指示。

25． 大多数排序算法都有两个基本操作，它们是______和______。

23． 计算机软件系统中，有两种处理字符串长度的方法：一种是采用______，第二种是______。

22． ______中结点的最大度数允许大于2，而______中结点的最大度数不允许大于2。

21． 对角矩阵中，除了______的元素之外，其余的元素都是零。则对于一个k对角线矩阵(k为奇数)A是满足下面的条件的矩阵；如果______，则元素a[_ij=0。

19． 对于一个二维数组A[m][n]，若按行序为主序存储，则任一元素A[i][j]相对于A[0][0]的地址为______。

20． 在一个按行优先顺序存储的二维数组(M×N)中，假设数组的基地址是P，并且数组的每一个元素所占的存储空间为d个字节，则a[_ij的地址计算公式为______。

18． 在分块查找法中，首先查找______，然后再查找相应的______。

17． 设一个链栈的栈顶指针为ls，栈中结点两个字段分别为info和next，其中next是指示后继结点的指针，栈空的条件是______。如果栈不空，则退栈操作为p：=ls；______；dispose(p)。

16． 在直接插入和直接选择排序中，如果初始数据基本正序，则选用______，若初始数据基本反序，则选用______。

15． 设有一顺序栈S，元素s₁，s₂，s₃，s₄，s₅，s₆依次进栈，如果6个元素出栈的顺序是s₂，s₃，s₄，s₅，s₆，s₁，则栈的容量至少应该是 ( )

14． 设计一个判别表达式中左、右括号是否配对出现的算法，采用( )数据结构最佳。

12． 在一棵二叉树中，第k层上最多有( )个结点。

13． 一棵二叉树如图所示，其中序遍历的序列为  (  )

10． 已知一个单链表中有3000个结点，每个结点存放一个整数，( )可用于解决这3000个整数的排序问题且不需要对算法作大的变动。

11． 二维数组M[i,j]的元素是4个字符(每个字符占一个存储单元)组成的串，行下标i的范围从0到4，列下标j的范围从0到5。M按行存储时元素M[3,5]的起始地址与M按列存储时元素( )的起始地址相同。

9． 以下有关数据结构的叙述，正确的是 ( )

8． 设rear是指向非空带头结点的循环单链表的尾指针，则删除起始结点的操作可表示为( )

6． 在图的邻接表存储结构上执行广度优先搜索遍历类似于二叉树上的 ( )

7． 一个栈的入栈序列为a1,a2,a3,a4,a5，则此栈不可能的输出序列是 ( )

5． 设二叉树有n个结点，则其深度为 ( )

4． 深度为6(根的层次为1)的二叉树至多有( )个结点。

3． 在单链表中，删除p所指结点的直接后继的操作是 ( )

2． 已知一个向量的第一个元素的存储地址是loO，每个元素的长度为2，则第6个元素的地址是 ( )

1． 在图的邻接表存储结构上执行深度优先搜索遍历类似于二叉树上的 ( )