数据机构 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程序，但。。。！建议大家安个红帽子）
kaoyan.com网友chenxiong0115 回忆整理 |
收藏
点赞!
反对!