一、算法设计题
1。 设二叉树bt采用二叉链表结构存储。试设计一个算法输出二叉树中所有非叶子结点,并求出非叶子结点的个数。
【答案】
int count=0；
void algo2(BTNode *bt)｛
      if (bt)｛
        if（bt->lchild  || bt—〉rchild)｛
          printf（bt—>data);
    count++；
}
      algo2（bt->lchild）；
      algo2（bt—〉rchild）;
    ｝
  }
2。 阅读下列函数arrange(）
    int arrange（int a［],int 1，int h,int x）
｛//1和h分别为数据区的下界和上界
    int i，j，t；
    i=1；j=h；
      while(i〈j){
        while（i<j ＆＆ a［j］>=x）j—-;
        while(i〈j && a[j]>=x）i++;
        if(i〈j)
          {  t=a［j］；a［j]=a[i]；a［i]=t；}
      }
        if(a［i]<x)  return i;
        else  return i－1;
      }
（1）写出该函数的功能；
（2）写一个调用上述函数实现下列功能的算法:对一整型数组b［n］中的元素进行重新排列，将所有负数均调整到数组的低下标端，将所有正数均调整到数组的高下标端，若有零值，则置于两者之间,并返回数组中零元素的个
数。
【答案】
(1）该函数的功能是：调整整数数组a[］中的元素并返回分界值i，使所有＜x的元素均落在a[1。.i］上，使所有≥x的元素均落在a［i＋1.。h］上。
      (2）int f(int b［］，int n)                      或  int f（int b［]，int n）
              ｛                                                    ｛
  int p,q；                                        int p，q；
  p=arrange（b，0，n－1,0）；                  p=arrange(b,0,n－1，1）；
  q= arrange（b,p+1，n－1，1）；        q= arrange（b，0,p,0)；
  return q－p;                                  return p－q;
  ｝                                              ｝
3。 假设线性表以带表头结点的循环单链表表示。试设计一个算法，在线性表的第k个元素前插入新元素y。假如表长小于k,则插在表尾。
【答案】
void algo1(LNode ＊h，int k，ElemType y）{
q=h; P=h—〉next; j=1;
while（ p！=h ＆& j<k）{
  q=p； p=p—〉next; j++;
｝
s=(LNode ＊）malloc(sizeof（Lnode));
s-〉data=y;
q-〉next=s；
s—〉next=q；
｝     
4. 二叉排序树的类型定义如下：
typedef struct BSTNode {∥ 完全二叉树算法二叉排序树的结点结构
int    data；    ∥数据域
struct  BSTNode  ＊lchild， ＊rchild； ∥左、右孩子指针
｝BSTNode,＊BSTree;
设计递归算法，统计一棵二叉排序树T中值小于a的结点个数。
【答案】
int  f34（BSTree  root)
{
  int count;
  BSTNode *p；
  p=root;
  if （ p ＆&  p->data〈a）  count++；
  f34（p—>lchild);
  return count;
}
5。 设二叉树T采用二叉链表结构存储，试设计算法求出二叉树中离根最近的第一个叶子结点。（注：结点按从上往下，自左
至右次序编号）
【答案】
BTNode * Firstleaf（BTNode *bt)
    ｛ InitQueue(Q）; //初始化队列Q
      if(bt){
      EnQueue（Q，bt);;
      while(！EmptyQueue(Q))｛
        DeQueue（Q,p);
        if(！p—>lchild  ＆&  !p->rchild） return p;
        if(p-〉lchild）  EnQueue(Q，p->lchild）;
        if（p->rchild）  EnQueue(Q，p—〉rchild）;
      ｝
      }
    ｝
6。 已知一棵具有n个结点的完全二叉树被顺序存储在一维数组中，结点为字符类型，编写算法打印出编号为k的结点的双亲和
孩子结点。
【答案】
    int algo2（char  bt[]，int n，int k）｛
      if (k〈1||k〉n) return 0；
if( k==1）  printf(“ %c is  a  root\n”, bt［1])；
else  printf(“ %c’s parent  is ％c\n”， bt[k］， bt［k/2]）；
      if(2＊k<=n）  printf（“ %c's lchild  is ％c\n”， bt[k], bt[2*k］）；
      else printf（“ ％c is  not  lchild\n", bt［k］)）；
      if（2*k+1〈=n）  printf（“ ％c's rchild  is %c\n”， bt［k]， bt[2＊k+1］）；
else printf(“ %c is  not  rchild\n"， bt[k])）;
return 1;
  }
7. 编写算法,将非空单链表hb插入到单链表ha的第i(0〈i≤表长)个结点前。
【答案】
int  algo1(LNode *ha, LNode *hb，int i)｛ 
    for（p=hb;p->next; p=p-〉next)；
    for（j=1，q=ha；j〈i; j++)  q=q—>next；
    p-〉next=q—〉next;
    q—〉next=hb—〉next  ；
    free（hb）；
  ｝
8。 设二叉树T已按完全二叉树的形式存储在顺序表T中，试设计算法根据顺序表T建立该二叉树的二叉链表结构.顺序表T定义如下:
struct tree｛
  int no；          /* 结点按完全二叉树的编号＊/
  ElEMTP  data;    /＊ 数据域 */
  }T[N］；            /＊ N为二叉树T的结点数*/
【答案】
BTNode ＊creat_tree（struct tree T［N]）
    ｛ BTNode ＊p[MAX]；
      t=NULL；
      for(i=0;i〈N；i++){
        s=（BTNode *)malloc（sizeof（BTNode)）；
        s->data=T[i］.data； 
        s—>lchild=s-〉rchild=NULL；
        m=T［i］.no；  p［m］=s;
        if（m==1) t=s;
        else ｛ j=m/2；
                if（m%2==0） p［j]—>lchild=s;
                else p[j]—>rchild=s;

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。