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

35． 设计一个用链表表示的直接选择排序算法。

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

int Pop(LStackTp*is,DataType*x)

    { LStackTp*P;

      if(1s!=NULL)

           { p=ls;

              *x=______;

              ls=ls—＞next;

              ______;

              return(1);

            } else return(0);

  }

34． 分析下面程序段的时间复杂度______。

j=1; 

while(j＜=n)  

{j=j*2; 

}

30． 假设有一个容量为5的队列，假设其初始状态为front=rear=0，则对此队列进行下列操作之后，请画出此时的头、尾指针的变化情况和相应的队列内元素的存储情况。 (1)队列为空(即没有任何元素进入)； (2)A，B，C入队； (3)A出队； (4)B，C出队，此时队列为空。

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

int EmptyCycQueue(CycqcleueTp sq)

       { if(______)retum(1);

         else return(0);

       }

32． 以下算法在有序表R中用二分查找法查找键值等于K的元素，请分析程序，并在______上填充合适的语句。

int binsearch(sqtable R,keytype K)

  {low=l;hig=R.n;/*置查找区间初值。low，hig分别标记查找区间的下、上界*/

      while(low＜=hig)

       { mid=(low+hig)/2;

         switch

           { case K==R.item[i].key:return(mid);   /*找到，返回位置mid*/

             case K＜R.item[i].key:______;break;/*缩小区间*/

             case K＞R.item[i].key:______;break;/*缩小区间*/

           }

       }

     return(0); /*若区间长度已为0但仍不成功，则返回0，表示查找不成功*/

  }

29． 进行多项式相加，采用哪一种表示方法处理较为简单?

多项式A(x)=a_nXⁿ+a_n-1X^n-1+…+a₁X+a₀的线性表表示法有下列两种可能的形式：

A=(n,a_n,a_n-1，…，a₁，a₀) 

A=(m，1_m-1，b_m-1，1_m-2，b_m-2，…，1₀，b₀)

其中：m为非零项的个数，1_i，b_i分别为非零项的指数和系数。试分析：

两种表示方法对存储空间的需要情况；

27． 已知串S=‘(xyz)*’，t=‘(x+z)*y’，试利用串的基本运算将s串转化为t串，t串转化为s串。

26． 试分别画出具有3个结点的树和具有3个结点的二叉树的所有不同的形态。