數據結構 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分 |
