2243计算机软件基础(一)复习资料11

50. 深度为6的二叉树最多有 （63 ） 结点 2^k-1

52 树是适合用来表示元素之间具有分支层次关系的数据，

53 试编写算法交换二叉树中所有结点上的左、右子树，

     void  exch_tree ( hitreptr ,BT )

   { ( if (BT ! = NULL ))

     { exch_tree ( BT -> lchild )

       exch_tree ( BT -> rchild )

       P= BT ->lchild ;

       BT -> lchild =BT ->rchild ;

       BT -> rchild =p ; } }

54 以二叉链表作为存储结构，试编写求二叉树中叶子树的算法

   int  leaf_count ( bitreptr T)

   { if (T = = NULL ) leaf =0 ;

     else if ( ( T -> lchild = = NULL )&& ( T -> rchild == NULL) )

           leaf = 1;

         else { L= leaf_count ( T-> lchild );

              R = leafcount ( T-> rchild; );

              leaf = L+ R ; }

     return (leaf );  }

55. 以下程序是实现图的深度优先搜索算法

   Dfs (GraphTP g , int v)

    { ArcNodeTP  * p ;

     printf ( "% d" ,v );

     visited [ v ] =1

     p = g.adjlist[ v ].firstarc ;

     while ( p ! =NULL )

      { if ( !visited [ p -> adjvex ] )

        Dfs(g, p->adjvex );

        p= p ->nextarc ;

       } }

56. 二分查找法适用于存储结构为顺序存储的且按关键字排好序的线性表

57. 用顺序查找法对具有 n个结点的线性表，查找的时间复杂量级为 O (n)

58. 用二分查找法对具有 n个结点的线性表，查找的时间复杂量级为 O (log₂ⁿ)

59.以下程序是在有序表中用二分查找法，查找关键值等于 K 的元素 

   int  binsearch ( sqtable r, kegtype k)

  { low =1, hig = r.n ;

    while ( low <= hig )

    { mid = (low +hig ) / 2 ;

      if (k= = r.wtem [mid] key)  return (mid );

      else if (k< r.wtem [mid] key) hig = mid-1;

     　　 else low =mid+1 ;

     } }

60. 以下运算法是指针 T 所指的二叉排序树上查找键值等于K的结点

   bireptr *search_bst(bitreptr T, keytype k)

   { if ( T = = NULL ) return ( NULL);

     else if (T -> key = = k)  ruturn ( T);

         else if (T -> key > k) return (search_bst(T -> lchild ; k) ) ;

             else return (search-bst(T -> rchild ; k) ) ;

    }