---

数据结构 75分

一、下列算法时间复杂性?
void fun(int m,int n)
{
        int i=0,j=0;
        while(i<m)
                if(j<n) j++;
                else
                {
                        j=0;
                        i++;
                }
} 
二、
1 void String::fail ( ) {                // 计算模式p ( *this)的失败函数
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 }
   问：第5句的作用是？执行第6句时i可以小于0吗？执行第7句时i一定小于0吗？
三、 R0，R1，R2，R3，R4，R5，R6建败着树（数据两两不相等，自己编哈） （考过）
四、论述在克鲁斯卡尔算法中，如何利用并查集判断所选边<u,v>是否会成环。（书上有，仔细看书）
五、（书上有，不错过每一细节）
树的定义：一棵树是由一个或多个结点组成的有限集合，且其中
（1） 存在一个称为根的特定结点；
（2） 剩余结点被划分为n≥0个不相交集合T1, …, Tn，且Ti（1≤i≤n）也是一棵树。T1, …, Tn 称为根结点的子树。
   问：为什么树不能为空啊？为什么二叉树可以啊？
六、快排序和堆排序都不稳定，举例说明。（书上习题）
    (我选的是(a0,a1,a2),其中a0=a1=a2,这个好记哈。。。)
七、给了一棵3阶B树，画图描述连续删除两个数，再在原图上连续插入两个数过程。
八、
struct Element{int key;}
struct TreeNode
{
        TreeNode *LeftChild,*RightChild;
        Element data;
}
利用上面两个结构给出判断一棵根为t的二叉树是否为AVL树的递归算法。
bool Tree::IsAVL()
{
        return  IsAVL(t);
}
bool Tree::IsAVL(TreeNode * cur)
{
        if(!cur) return true;
        //...下面自己写哈
}
int Tree::Height(TreeNode * cur)
{
        //...
}

操作系统 75分

一、OS的基本内容和基本特征？
二、引入虚存为啥就那么重要呢？虚存容量与主存与外存有关吗？
三、PCB的作用？包括哪些项？（写5-6项）
四、啥叫原语？用高级语言实现经典原语P操作。
五、某作业进程共10页，页大小32。其中已有8页在主存，块地址为b1,b2,b3,b4,b5,b6,b7,b8
    其中前四页在快表中。给定虚址101    183    299    321（十进制）
        （不好意思，数据是我编的，已足够）
        问：
        1.哪个（些）地址违法？    （2分）
        2.哪个（些）地址映射发生在快表中，他（他们）主存地址为？  2分
        3.哪个（些）地址映射发生在主存中，他（他们）主存地址为？  2分
        4.哪个（些）地址会发生缺页？  2分
六、进程A   B   C   D进入就绪队列时间 为 0   1   2   3。
    下CPU周期分别为 8   4   9   5。 
        算法是可抢夺最短周期优先。按教材的图示法画出进程推进过程。并求ATT。
七、
main()
{
        int pid;
        pid=fork();
        if(pid==0)
                printf("陈雄爱爸爸!\n");
        else
        {
                if(pid>0)
                        printf("陈雄爱妈妈!\n");
                else
                        printf("陈雄爱老婆!\n");
        }
        printf("他们我都爱!\n");
}
问：
1、上述程序中系统调用名是？2分
   上述程序中库函数名是？  2分
2、结果可能为？ 8分