东南大学08计算�����研试题_跨考网

复习(f��n)紧张�Q�焦头烂额？逆风轻袭�Q�来跨考秋季集训营�Q�帮你寻�Ҏ(gu��)���Q�定�Ҏ(gu��)���Q?/span> 了解一�?>

　　数据�l�构 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">

　　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;

　　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">)

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

　　八�?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">

　　bool Tree::IsAVL()

　　{

　　return IsAVL(t);

　　}

　　bool Tree::IsAVL(TreeNode * cur)

　　{

　　if(!cur) return true;

　　//...下面自己写哈

　　}

　　int Tree::Height(TreeNode * cur)

　　{

　　//...

　　}

　　操作�pȝ�� 75�?span lang="EN-US">

　　一�?span lang="EN-US">OS的基本内容和基本特征?

　　二、引入虚存�ؓ(f��)啥就那么重要�?span lang="EN-US">?虚存定w��与主存与外存有关�?span lang="EN-US">?

　　三�?span lang="EN-US">PCB的作�?span lang="EN-US">?包括哪些��?span lang="EN-US">?(�?span lang="EN-US">5-6��?span lang="EN-US">)

　　四、啥叫原�?span lang="EN-US">?用高�U�语�a�实现�l�典原语P操作�?span lang="EN-US">

　　五、某作业�q�程�?span lang="EN-US">10��，��大��?span lang="EN-US">32。其中已�?span lang="EN-US">8��在��d���Q�块地址�?span lang="EN-US">b1,b2,b3,b4,b5,b6,b7,b8

　　其中前四��在快表中。给定虚址101 183 299 321(十进�?span lang="EN-US">)

　　(不好意思，数据是我�~�的�Q�已���_��)

　　问：(x��)

　　1.哪个(�?span lang="EN-US">)地址�q�法? (2�?span lang="EN-US">)

　　2.哪个(�?span lang="EN-US">)地址映射发生在快表中�Q�他(他们)��d��地址�?span lang="EN-US">? 2�?span lang="EN-US">

　　3.哪个(�?span lang="EN-US">)地址映射发生在主存中�Q�他(他们)��d��地址�?span lang="EN-US">? 2�?span lang="EN-US">

　　4.哪个(�?span lang="EN-US">)地址�?x��)发生缺�?span lang="EN-US">? 2�?span lang="EN-US">

　　六、进�E?span lang="EN-US">A B C D�q�入���q�A队列旉��� �?span lang="EN-US"> 0 1 2 3�?span lang="EN-US">

　　�?span lang="EN-US">CPU周期分别�?span lang="EN-US"> 8 4 9 5�?span lang="EN-US">

　　���法是可抢夺最短周期优先。按教材的图�C�法��d���q�程推进�q�程。�ƈ�?span lang="EN-US">ATT�?span lang="EN-US">

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

　　main()

　　{

　　int pid;

　　pid=fork();

　　if(pid==0)

　　printf("���强��q���?span lang="EN-US">!\n");

　　else

　　{

　　if(pid>0)

　　printf("���强爱妈�?span lang="EN-US">!\n");

　　else

　　printf("���强��p��婆!\n");

　　}

　　printf("他们我都�?span lang="EN-US">!\n");

　　}

　　问：(x��)

　　1、上�q�程序中�pȝ��调用名是?2�?span lang="EN-US">

　　上述�E�序中库函数名是? 2�?span lang="EN-US">

　　2、结果可能�ؓ(f��)? 8�?span lang="EN-US">