东大08计算机应用技术回忆_跨考网

　　我想对后来�h说的是，看书�Q�看书。。�?span lang="EN-US">

　　勤思考，记笔记。注意细节�?span lang="EN-US">

　　数据机构 75�?span lang="EN-US">

　　一。下列算法时间复杂�?span lang="EN-US">?

　　void fun(int m,int n)

　　{

　　int i=0,j=0;

　　while(i<M)< p>

　　if(j<>

　　else

　　{

　　j=0;

　　i++;

　　}

　　} (送分�?span lang="EN-US">)

　　二�?span lang="EN-US">(此题����?span lang="EN-US">)

　　1 void String::fail ( ) { // 计算模式p ( *this)的失败函�?span lang="EN-US">

　　2 int LengthP= Length( ); f[0]= -1;

　　3 for (int j = 1; j < LengthP; j++) { // 计算f[j]

　　4 int i = f[j-1];

　　5 while ((*(str+j)!=*(str+i+1)) && (i>=0)) i = f [ i ] ;

　　6 if ( *(str+j) == *(str+i+1)) f[j] = i+1;

　　7 else f[j] = -1;

　　8 }

　　9 }

　　问：(x��)�W?span lang="EN-US">5句的作用�?span lang="EN-US">?执行�W?span lang="EN-US">6句时i可以���于0�?span lang="EN-US">?执行�W?span lang="EN-US">7句时i一定小�?span lang="EN-US">0�?span lang="EN-US">?

　　三�?span lang="EN-US"> R0�Q?span lang="EN-US">R1�Q?span lang="EN-US">R2�Q?span lang="EN-US">R3�Q?span lang="EN-US">R4�Q?span lang="EN-US">R5�Q?span lang="EN-US">R6����|着�?span lang="EN-US">(数据两两不相�{�，自己�~�哈) (考过)

　　四。论�q�在克鲁斯卡��?d��ng)算法中�Q�如何利用�ƈ查集判断所选边是否�?x��)成环�?span lang="EN-US">(书上有，仔细看书)

　　五�?span lang="EN-US">(书上有，不错�q�每一�l�节)

　　�?w��i)的定义�Q�一���|��(w��i)是由一个或多个�l�点�l�成的有限集合，且其�?span lang="EN-US">

　　(1) 存在一个称为根的特定结�?span lang="EN-US">;

　　(2) 剩余�l�点被划分�ؓ(f��)n�?个不�怺�集合T1, �? Tn�Q�且Ti(1≤i≤n)也是一���|��(w��i)�?span lang="EN-US">T1, �? Tn �U�Cؓ(f��)根结点的子树(w��i)�?span lang="EN-US">

　　问：(x��)��Z��么树(w��i)不能为空�?span lang="EN-US">?��Z��么二叉树(w��i)可以�?span lang="EN-US">?

　　六。快排序和堆排序都不�E�_���Q��D例说明�?span lang="EN-US">(书上�?f��n)�?span lang="EN-US">)

　　(我选的�?span lang="EN-US">(a0,a1,a2),其中a0=a1=a2,�q�个好记哈。。�?span lang="EN-US">)

　　七。给�?ji��n)一��?span lang="EN-US">3�?span lang="EN-US">B�?w��i)，��d��描述�q�箋删除两个敎ͼ�再在原图上连�l�插入两个数�q�程�?span lang="EN-US">

　　(说白�?ji��n)，往�q�很多这�U�题)

　　八�?span lang="EN-US">

　　struct Element{int key;};

　　struct TreeNode

　　{

　　TreeNode *LeftChild,*RightChild;

　　Element data;

　　}

　　利用上面两个�l�构�l�出判断一���|���?span lang="EN-US">t的二叉树(w��i)是否�?span lang="EN-US">AVL�?w��i)的递归���法�?span lang="EN-US">(此题我用�?span lang="EN-US">2分钟)

　　bool Tree::IsAVL()

　　{

　　return IsAVL(t);

　　}

　　bool Tree::IsAVL(TreeNode * cur)

　　{

　　if(!cur) return true;

　　//...下面自己写哈

　　}

　　int Tree::Height(TreeNode * cur)

　　{

　　//...

　　}

 (t��ng)