全国自考（数据结构）模拟试卷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． 在单链表中，除了首元结点外，任一结点的存储位置是由______指示。