数据机构 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树的递归算法。（此题我用了2分钟）
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分
（这题没有把握，考试前还在红帽子上弄过几个fork程序，但。。。！建议大家安个红帽子