wangdapeng

清华大学1996年数据结构程序设计与编译原理考研试题

wangdapeng

wangdapeng

wangdapeng

wangdapeng

wangdapeng

清华大学2000年数据结构与程序设计考研试题

1、(12分)
请回答下列关于图(Graph)的一些问题:
1（4分）有n个顶点的有向连通图最多有多少条边?最少有多少条边？
2（4分）表示一个有1000个顶点、1000条边的有向图的邻接矩阵有多少个矩阵元素?是否稀疏矩阵？
3（4分）对于一个有向图，不用拓扑排序，如何判断图中是否存在环？
2、(12分)
斐波那契数列Fn定义如下:
F0=0,  F1=1,  Fn=  Fn-1  +  Fn-2,  n=2,3,…
请就此斐波那契数列，回答下列问题:
1.（7分）在递归计算Fn的时候，需要对较小的Fn－1，Fn－2，…，F1，F0精确计算多少次？
2.（5分）若干有关大O表示法，试给出递归计算Fn时递归函数的时间复杂度是多少？

3、（17分）
有一种简单的排序算法，叫做计数排序(count  sorting)。这种排存算法对一个待排序的表(用数组表示)进行排序，并将排序结果存放到另一个新的表中。必须注意的是，表中所有待排序的关键码互不相同。计数排序算法针对表中的每个记录，扫描待排序的表一趟，统计表中有多少个记录的关键码比该记录的关键码小。假设针对某一个记录，统计出的计数值为c,那么，这个记录在新的有序表中的合适的存放位置即为c。

1.（3分）给出适用于计数排序的数据表定义；

2.（7分）使用Pascal或C语言编写实现计数排序的算法；  

3.（4分）对于有n个记录的表，关键码比较次数是多少？

④.（3分）与简单选择排序相比较，这种方法是否更好？为什么？

4、（10分）
  在一棵表示有序集S的二叉搜索树（binary  search  tree）中，任意一条从根到叶节点的路径将S分为3部分:在该路径左边节点中的元素组成的集合S1；在该路径上的节点中的元素组成的集合S2；在该路径右边节点中的元素组成的集合S3。S＝S1∪S2∪S3。若对于任意的a∈S1,  b∈S2,  c∈S3,是否总有a<=b<=c?为什么？

5、（12分）请回答下列关于堆（Heap）的一些问题:

1.（4分）堆的存储表示是顺序的，还是链接的？  

2.（4分）设有一个最小堆，即堆中任意节点的关键码均大于它的左子女和右子女的关键码。其具有最大值的元素可能在什么地方？

3.（4分）对n个元素进行初始建堆的过程中，最多做多少次数据比较（不用大O表示法）？

6、（12分）
  已知Q是一个非空队列，S是一个空栈。仅用队列和栈的ADT函数和少量工作变量，使用Pascal或C语言编写一个算法，将队列Q中的所有元素逆置。
栈的ADT函数有:
makeEmpty(s:stack);  置空栈
push(s:stack;  value:datatype);  新元素value进栈
pop(s:stack):datatype;  出栈，返回栈顶值
isEmpty(s:stack):boolean;  判栈空否
队列的ADT函数有
enqueue(q:queue;value:datatype);  元素value进队
deQueue(q:queue):datatype;  出队列，返回队头值
isEmpty(q:queue):boolean;  判队列空否

7、（13分）
设散列表为HT[0..12],即表的大小为m=13。现采用双散列法解决冲突。散列函数和在散列函数分别为:
H0(key)=key%13;  注:％是求余数运算（＝mod）
Hi=(Hi-1+REV(key+1)%11+1)%13;  i=1,2,3,…，m-1
其中，函数REV（x）表示颠倒10进制数x的各位，如REV(37)=73,REV(7)=7等。若插入的关键码序列为{2,8,31,20,19,18,53,27}。

1.（8分）试画出插入这8个关键码后的散列表。
2.（5分）计算搜索成功的平均搜索长度ASL。

8、（12分）
  从左到右及从右到左遍历一个单链表是可能的，其方法是在从左向右遍历的过程中将连接方向逆转，如图1所示。在图中的指针p指向当前正在访问的节点，指针pr指向指针p所指节点的左侧的节点。此时，指针p所指节点左侧的所有节点的连接方向都已逆转。

图1  题8图

1.（6分）使用Pascal或C语言编写一个算法，从任一给定位置（pr,p）开始，将指针p右移1个节点。如果p移出链表，则将p置为NULL，并让pr留在链表最右边的节点上。

2.（6分）使用Pascal或C语言编写一个算法，从任一给定位置（pr,p）开始，将指针p左移一个节点。如果p移出链表，则将p置为NULL,并让pr停留在链表最左边的节点上。

wangdapeng

清华大学2001年数据结构与程序设计考研试题

2001年数据结构与程序设计
试题内容:
一、试给出下列有关并查集(mfsets)的操作序列的运算结果:
union(1,2) , union(3,4) , union(3,5) , union(1,7) , union(3,6) , union(8,9) , union(1,8) , union(3,10) , union(3,11) , union(3,12) , union(3,13) , union(14,15) , union(16,0) , union(14,16) , union(1,3) , union(1,14)。（union是合并运算，在以前的书中命名为merge）
要求
(1) 对于union(i,j)，以i作为j的双亲； （5分）
(2) 按i和j为根的树的高度实现union(i,j)，高度大者为高度小者的双亲；  （5分）
(3) 按i和j为根的树的结点个数实现union(i,j)，结点个数大者为结点个数小者的双亲；  （5分）
二、设在4地（A,B,C,D）之间架设有6座桥,如图所示:

要求从某一地出发,经过每座桥恰巧一次,最后仍回到原地
(1) 试就以上图形说明:此问题有解的条件是什么?  (5分)
(2) 设图中的顶点数为n,试用C或Pascal描述与求解此问题有关的数据结构并编写一个算法,找出满足要求的一条回路.  (10分)
三、针对以下情况确定非递归的归并排序的运行时间(数据比较次数与移动次数):
(1) 输入的n个数据全部有序;  (5分)
(2) 输入的n个数据全部逆向有序;  (5分)
(3) 随机地输入n个数据.  (5分)
四、简单回答有关AVL树的问题.
(1) 在有N个结点的AVL树中,为结点增加一个存放结点高度的数据成员,那么每一个结点需要增加多少个字位(bit)?  (5分)
(2) 若每一个结点中的高度计数器有8bit,那么这样的AVL树可以有多少层?最少有多少个关键码?  (5分)
五、设一个散列表包含hashSize=13个表项,.其下标从0到12,采用线性探查法解决冲突. 请按以下要求,将下列关键码散列到表中.
10 100 32 45 58 126 3 29 200 400 0
(1) 散列函数采用除留余数法,用%hashSize(取余运算)将各关键码映像到表中. 请指出每一个产生冲突的关键码可能产生多少次冲突.   (7分)
(2) 散列函数采用先将关键码各位数字折叠相加, 再用%hashSize将相加的结果映像到表中的办法. 请指出每一个产生冲突的关键码可能产生多少次冲突.   (8分)
六、设一棵二叉树的结点定义为
struct BinTreeNode{
ElemType data;
BinTreeNode *leftChild, *rightChild;
}
现采用输入广义表表示建立二叉树. 具体规定如下:
(1) 树的根结点作为由子树构成的表的表名放在表的最前面;
(2) 每个结点的左子树和右子树用逗号隔开. 若仅有右子树没有左子树, 逗号不能省略.
(3) 在整个广义表表示输入的结尾加上一个特殊的符号(例如”#”)表示输入结果.
例如,对于如右图所示的二叉树, 其广义表表示为A(B(D,E(G,)),C(,F))
   A
   /  \
B   C
/  \   \
D  E   F
   /
  G
此算法的基本思路是:依次从保存广义表的字符串ls中输入每个字符. 若遇到的是字母(假定以字母作为结点的值), 则表示是结点的值, 应为它建立一个新的结点, 并把该结点作为左子女(当k=1)或有子女(当k=2)链接到其双亲结点上. 若遇到的是左括号”(“, 则表明子表的开始,将k置为1;若遇到的是右括号”)”, 则表明子表结果. 若遇到的是逗号”,”, 则表示以左子女为根的子树处理完毕,应接着处理以右子女为根的子树, 将k置为2.
在算法中使用了一个栈s, 在进入子表之前,将根结点指针进栈, 以便括号内的子女链接之用. 在子表处理结束时退栈. 相关的栈操作如下:
MakeEmpty(s) 置空栈
Push(s,p) 元素p进栈
Pop(s) 进栈
Top(s) 存取栈顶元素的函数
下面给出了建立二叉树的算法, 其中有5个语句缺失. 请阅读此算法并把缺失的语句补上.  (每空3分)
Void CreateBinTree(BinTreeNode *&BT, char ls){
Stacks; MakeEmpty(s);
BT=NULL;          //置二叉树
BinTreeNode *p;
int k;
istream ins(ls);        //把串ls定义为输入字符串流对象ins
Char ch;
ins>>ch;            //从ins顺序读入一个字符
While(ch!=”#”){        //逐个字符处理,直到遇到'#'为止
Switch(ch){
case’(‘: _______(1)_______
k=1;
break;
case’)’: pop(s);
break;
case’,‘: _______(2)_______
break;
default: p=new BinTreeNode;
_______(3)_______
p->leftChild=NULL;
p->rightChild=NULL;
if(BT==NULL)
_______(4)_______
else if (k==1) top(s)->leftChild=p;
else top(s)->rightChild=p;
}
_______(5)_______
}
}
七、下面是一个用C编写的快速排序算法. 为了避免最坏情况,取基准记录pivot采用从left,right和mid=[(left+right)/2]中取中间值, 并交换到right位置的办法. 数组a存放待排序的一组记录, 数据类型为Type, left和right是呆排序子区间的最左端点和最右端点.
Void quicksort(Type a&#;,int left,int right){
Type temp;
If(leftType pivot=median3(a,left,right);
Int I=left, j=right-1;
For( ; ; ){
While(iWhile(iif(itemp=a; a[j]=a; a=temp;
I++; j--;
}
else break;
}
if(a>pivot)
{temp=a: a=a[right]; a[right]=temp;}
quicksort(a,left,i-1);         //递归排序左子区间
quicksort(a,i+1,right);        //递归排序右子区间
}
}
(1) 用C或Pascal实现三者取中子程序 median3(a,left,right); (5分)
(2) 改写 quicksort 算法, 不用栈消去第二个递归调用 quicksort(a,i+1,right); (5分)
(3) 继续改写 quicksort 算法, 用栈消去剩下的递归调用. (5分)

编译原理及操作系统

试题内容:

编译原理部分
1.(5%) 给出下述NFA  M的五元组表示, 并将其确定化



2 (5%) 构造一个不具有ε-转移的NFA  M’ , 使得L(M’)=L(M)



3 (10%) 证明文法G[A]是LR(1)文法.
G[A]:A->BA|ε
B->aB|b
4 (5%) 证明合并不存在冲突(移进/归约、归约/归约)的LR(1)项目集的同心集不会产生新的移进/归约冲突.


5.(5%) 对目标代码运行时的存储空间采用基于过程活动记录的栈式分配方案, 举例说明象PASCAL这样的语言如何实现对非局部变量的访问.


6(15%) 文法G[R]: R->R+R | R·R | R*| (R) | a | b | ε
(1)证明文法 G[R] 生成字母表 Σ={a, b} 上的所有正规表达式(用+代替”|”, 连接符·没有省略)
(2)证明此文法是二义的
(3)根据正规式的三个运算符(+,·, *) (或, 连接, 闭包) 的优先性和结合性约定重新构造一个等价的LL(1) 文法


7(5%) 找出下列流图中的回边和回边组成的循环.编译中利用流图完成什么工作?



操作系统部分

一、名次解释（10分）
多道程序、多重处理、进程、线程、虚存
二、画出NT操作系统的线程状态转移图（10分）
三、UNIX系统与Linux系统等中都提供pipe文件功能，简述pipe() 的工作原理。（10分）
四、设周期性任务P1，P2，P3的周期T1，T2，T3分别为100，150，350；执行时间分别为20，40，100。试计算后回答是否可以用频率单调调度算法进行调度？（10分）
五、I/O控制可用那几种方式实现？各有何优缺点？（10分）

wangdapeng

清华大学2001年计算机组成原理考研试题


一、（10分）某RISC处理机各类指令使用频率和理想CPI（指令和数据访问Cache命中率为100％时的CPI）如下表所示。而实际测得的指令访问Cache缺失率（miss rate）为5％，数据访问的Cache缺失率为10％，Cache的缺失损失（miss penalty）为40个时钟周期。
（1） 该机器在无Cache缺失（理想情况）时的CPI是多少？（3分）
（2） 该机器在无Cache缺失（理想情况）时的速度比有Cache缺失时快多少倍？（7分）
指令类型 使用频率 CPI ideal
ALU操作 43% 1
Loads    21% 2
Stores    12% 2
Branches  24% 2


二、（13分）一台模型机共有7条指令，主频25MHz，各指令的使用频率与CPI如下表所示。该模型机有8位和16位两种指令字长，采用2-4扩展操作码。8位字长指令为寄存器（R－R）二地址类型，16位字长指令为寄存器－存储器（R－M）二地址变址寻址类型（-128<=变址范围<=127）。

指令（字长） 使用频度f CPI
I1（8位） 35% 1
I2（8位） 25% 2
I3（8位） 20% 2
I4（16位） 10% 2
I5（16位） 5% 1
I6（16位） 3% 2
I7（16位） 2% 2
（1） 计算该机的MIPS速率。（4分）
（2） 计算操作码的平均码长。（3分）
（3） 该机允许使用多少个可编址的通用寄存器，多少变址寄存器？（3分）
（4） 设计该机的两种指令格式，标出各字段位数并给出操作编码。（3分）
三、（12分）假设在一个采用组织相联映像方式的Cache中，主存有B0～B7共8块组成，Cache有C0～C3共4块，组内块数为2块。每块的大小为32个字节，采用FIFO块替换算法。在一个程序执行过程中依次访问块地址流如下:
B1，B4，B6，B3，B0，B4，B6，B2，B4，B5
（1） 写出主存地址的格式，并标出各字段的长度（3分）
（2） 写出Cache地址的格式，并标出各字段的长度（3分）
（3） 画出主存与Cache之间各个块的映像对应关系（3分）
（4） 列出程序执行过程中Cache的块地址流分布情况。并计算Cache的块命中率。（3分）
四、（15分）有4个中断源D1、D2、D3、D4，它们的中断优先级和中断屏蔽码见下表，表中，"1"表示该中断源被屏蔽，"0"表示该中断源开放。假设从处理机响应中断源的中断服务请求到运行中断服务程序中第一次开中断所用的时间为1微秒，其它中断服务时间为10微秒。
（1） 处理机在0时刻开始响应中断请求，这时4个中断源都已经申请中断服务，写出处理机开始响应各中断源的中断请求和处理机为各中断源完成中断服务的时刻。（7分）
（2） 处理机在0时刻开始响应中断请求，这时中断源D3和D4已经申请中断服务，在6微秒时中断源D1和D2同时申请中断服务，写出处理机开始响应各中断源的中断请求和处理机为各中断源完成中断服务的时刻。（8分）
中断源 中断优先级 中断屏蔽码D1 D2 D3 D4
D1 1（最高） 1 1 0 0
D2 2（第二） 0 1 0 1
D3  3（第三） 1 0 1 0
D4 4（最低）  1 0 1 1


五、（10分）假定我们将某一执行部件性能改进后速度提高10倍。改进后被改进部件执行时间占系统总运行时间的50％。则改进后获得的加速比Sp是多少？
六、（10分）在下列单级互连网络中，将信息从一个PE播送给所有其它PE要用多少步（N＝2n个PE）？
（1） 混洗交换网络，每步只能做一次混洗或一次交换。（5分）
（2） 超立方体网络，每步i（0≤i≤n－1）可实现寻径函数Ci。（5分）
七、（15分）在一台单流水线处理机上执行下面的程序。每条指令都要经过"取指令"、"译码"、"执行"和"写结果"4个流水段，每个流水段的延迟时间都是5ns。在"执行"流水段，LS部件完成LOAD和STORE操作，其他操作都在ALU部件中完成，两个操作部件的输出端有直接数据通路与任意一个操作部件的输入端相连接，ALU部件产生的条件码也能够直接送入控制器。
1: SUB R0, R0 :R0←0
2: LOAD R1, #8 :R1←向量长度8
3:LOOP: LOAD R2, A(R1) :R2←A向量的一个元素
4: MUL R2, R1 :R2←（R2）×（R1）
5: ADD R0, R2 :R0←（R0）＋（R2）
6: DNE R1, LOOP :R1←（R1）－1，若（R1）≠0 转向LOOP
7: STORE R0, S :保存结果
（1） 采用静态分支预测技术，每次都预测转移不成功。画出指令流水线的时空图（中间部分可以省略，图中可用指令序号表示），计算流水线的吞吐率和加速比，并分别计算译码部件和ALU部件的使用效率。（8分）
（2） 采用静态分支预测技术，每次都预测转移成功。计算指令流水线的吞吐率和加速比，并分别计算译码部件和ALU部件的使用效率。（7分）
八、（15分）分别在下面三种计算机系统上用最短的时间来计算表达式 。假设加法和乘法分别需要2个和4个单位时间，从存储器取指令、取数据、译码的时间忽略不计，所有的指令和数据已装入有关的PE或处理机中。PE或处理机中有一个加法器和一个乘法器，同一时刻只有其中一个可以使用。试确定下列每种情况的最小计算时间。
（1） 一台串行计算机，这种单处理机系统不需要数据寻径操作。（3分）
（2） 一台有8个PE（PE0，PE1，···，PE7）的SIMD计算机，8个PE连成单向环结构。每个PE用一个单位时间可以把数据直接送给它的相邻PE。操作数Ai和Bi最初存放在PEi mod 8 中，其中i＝0，2，···，35。（6分）
（3） 分布存储器的MIMD多处理机，8个CPU用立方体网连接。在相邻CPU之间传送一个数据需要一个单位时间。操作数Ai和Bi最初存放在CPU i mod 8中，其中i＝0，1，···，35。最终结果s可以放在任意CPU的寄存器中。（6分）
总共用时＝35+1次乘法＝39单位时间。

wangdapeng

清华大学2005年计算机专业考研试题

  DS(50分）
一。（15分）
回答下列各题，并简要说明理由，每题3分
1。 什么是线形表？线形表的各元素类型是否必须是同一类型？为什么？
2。线形表有两种不同的继承形式，顺序的和链接的存储结构，
  在使用时，如何确定使用哪种存储结构？
3。给出一个二叉树的前序和中序遍历序列，要求写出后序遍历序列。
4。（记不清楚具体数字了，大概的数字把）
  一个文件用B+树做索引，给定文件大小2000000 B，每个页块大小为4000 B,
  每个指针大小为5 B。每个记录是200 B,其中关键码为5 B.
  问:
   1）应采用多少阶B+树?
   2)该文件索引块数目。
5。下列哪些可以做Hash函数？哪些效果不好？哪些效果好？
  其中，n为Hash表的表长；Random(n)可以产生一个0---n=1 的随机数；
  p(n)为小于n的最大素数。
   1）Hash(key) = key/n;
   2) Hash(key) = 1;
   3) Hash(key) = (key + Random(n)) % n;
   4) Hash(key) = key % p(n);
二。（5分）
  证明:一棵二叉树的前序，中序，后序遍历序列中，叶结点的相对位置是不变的
三。（15分）
  1） 给定一组关键码，要求依次插入建立一棵AVL树，大约12个关键码左右，
   （和03年那个真题只是关键码的不同）
    需要旋转的时候，要求标出旋转的类型:左单旋，右单旋，先左后右双旋，先右后
左双旋。
  2）在建成的这棵AVL树上，依次删除关键码****（四个），要求:
     如果需要旋转，那要标出旋转类型；用中序的直接前驱代替关键码
四。（15分）
  1）将书上284页的Dijkstra算法挖去5个空，让添。（5分）
   具体字母有差别，但是确实就是那个算法，我按照书上的来了。
   void ShortestPath(Graph<T> G, int v, int n)
   {
      for (int i = 0; i < n; i++){  //n为图的顶点数目
       dist = Edge[v];
       s = 0;
       if (i != v && dist < MaxNum)
        1空;
       else
        path = -1;
      }
      s[v] = 1;
      dist[v] = 0;
      for (int i = 0; i < n - 1; i++){
       float min = MaxNum;
       int u = v;
       for (int j = 0; j < n; j++){
        if( 2空 && dist[j] < min){
          u = j;
          min = dist[j];
        }
        }
        }
     3空；
     for (int w = 0; w < n; w++){
       if( 4空 && Edge[w] < MaxNum && dist + Edge[w] < dist
[w]){
        dist[w] = dist + Edge[w];
        5空；
       }
     }
     }
   2）（10分）
   定义了一个Max{***********}，即顶点i到其余各顶点的最短路径的最大值，
   让写一个算法求 这个Max{***********}的最小值。


操作系统
1.反置页表原理,同样的逻辑地址空间,主存空间,用一般的页表和反置页表各需要多少项.
(反置的表项是以主存空间来分的;比一般页表项少得多.)
2.UNIX的文件组织方式,磁块地址4BYTE,索引结点前10个直接,一个一级,二个二级的最大文               
件长度.
3.快表的作用和原理.
4.学生选课最多可以选3们，但是如果王同学选了3门C1C2C3后，想把C3换成C4，王同
学就得先退选C3再申请选修C4.但是这个时候可能C4已经选满了,而王同学想再选回
C3的时候可能已经被人选满,不能再选了.为了解决这个问题,使用一个函数
TradeCourse(user,course1,course2)将课程course1换成course2.下面给出一种实
现.如果有不正确,给出所有错误的执行情况,并给出你认为正确的实现.要有适当注
释.15分.
TradeCourse（user，course1，course2）{
course1->p();    //申请课程course1数据结构的互斥信号量
course1->drop(user); //退选课程course1
course2->p();    //申请课程course2数据结构的互斥信号量
if(course2->isFull()==false){//课程course2没有选满
   course2->add(user);//申请选修课程course2
   course2->v();  //释放课程course2数据结构的互斥信号量
   course1->v();  //释放课程course1数据结构的互斥信号量
}
}

(答案是错误.若课程2选满,即c2-full==1,会死锁)
  


组成原理:
第一题:填空，每空1.5分，共18分
1、多处理机存储的两种组织类型是_____和_____
2、写出3种多处理机高性能通信网络________________________
3。硬盘的接口的两种类型____________________
4。举例应用局部性原理的两种系统_________________和________________
5。显卡的两种总线接口___________和_________
6。IA32机的最大主存空间是__________

第二题:20分
1。什么叫disk array,它的作用。3分
2。什么叫cache，它的原理和作用。6分
3。什么叫SMP,它个cluster（集群系统）比较有什么区别和联系。3分
4。写出RISC、CISC、VLIW的基本思想。5分
5。嵌入式cpu和普通 cpu比较有哪些特点？3分

第三题:选择，每个3分，共12分。选择题基本上都是历年出过的真题，去核对一
下就知道了。
1。浮点数的尾数3位，符号为1位，用补码表示；阶数2位，符号1位。x的尾数是
-0.875，阶数为1。y的尾数是0.625，阶数是2。则z=x-y规格化后的结果是:
A、1011011  B、*******  C、*******  D以上均不对

2。cache用组相联映射，一块大小为128字节，cache共64块，4块分一组。主存有
4096块。地址共需多少位:
A、19 B、18 C、17 D、****

3。指令的执行分为取指令用时△t，译址用时2△t，执行用时3△t。当流水执行的
时，时间接近:
A 1n△t  B、2n△t   C、3n△t    D、6n△t

4。总线分同步总线和异步总线，其中同步总线具备的性质是:
1成本高、2成本低、3逻辑复杂、④逻辑简单、⑤⑥后两个想不起来了。
A、2、3、6  B、1、3、5  C、1、4、5  D、2、4、6

wangdapeng

清华大学2006年CS专业考研试题

计组部分

一、填空题
1. a,b为两个1位2进制数，Carryin为低位进位，Carryout为高位进位，用and,or写出带进
位的1位加法器的Carryout并化简，Carryout=____
2. 5段流水线分别为IF,__,EX,__,WB.
3. 一个串行程序可并行部分占%90，规模不变的情况下，串行程序并行化后加速比不超过
_______
4. 二进制补码1111 1111 1111 1111 1111 1111 1111 1011化为十进制后为_______

二、判断题
1.CISC计算机比RISC计算机指令多。
2.速度为10MIPS的计算机一定比速度为5MIPS的计算机快。
3.SRAM比DRAM的速度快，成本高。
4.SCSI硬盘与SATA硬盘的速度，价格比较.
5.PCI-Express与AGP都可用于显卡接口
6.SPECCPU 2000基准测试程序可用于测I/O性能。
7.IEEE 754是计算机中的二进制整数算术标准。
8.全相联与直接映象Cache的比较
9.INTEL P4功率小于10w
10.64位CPU一般比32位CPU快一倍
11.增加流水线段数可提高CPU频率
12.VHDL是硬件描述语言。
13.EPIC是VLIW的发展

三、简答题
1.试说明为何编译程序要进行如下优化
for(j=0;j<200;j++)
  {for(i=0;i<20;i++)
{
A[j]=A[j]+1;
}
}
编译优化后
for(i=0;i<20;i++)
  {for(j=0;j<200;j++)
{
A[j]=A[j]+1;
}
}
2.硬盘平均寻道时间为12ms，传输速率为10MB/s，磁盘控制器延时为2ms,则一个转速为72
00r/min的硬盘写1KB数据时间为多少?
3.为什么要设置二叉分支预测指令？画出2bit转移预测的状态图

数据结构

证明题:
1 证明在一棵满二叉树中分支B与叶子节点n0满足关系 B=2(n0-1)
2.证明，完全无向图中,两个顶点之间简单路径书目为:
  1 + A(n-2,1) + A(n-2,2) + ... + A(n-2,n-2)
其中A(m,n)是m取n的排列数。

作图题:
给了一个Dijkstra无向连通图的最小生成树算法描述，要你根据该描述作出最小生成树及
并查集的变化。

程序填空
给了一段排序算法，用静态链表描述的
1 问你这是什么排序算法（里面写着selectsort）
2 把挖去的5个空填上 （发现只有4个）

程序设计题
用链表表示的多项式
1 写类的描述
2 insert算法，如果相同指数合并，没有就插入
3 利用insert,给出多项式乘法的算法


操作系统

1 给出一个并发程序的描述:
semaphore X1=X2=Y=1;
int c1=c2=0;

procedure f1:
  p(X1)
  if (++c1 = 1) p(Y)
  v(X1)
  compute A
  p(X1)
  if (--c1 = 0) v(Y)
  v(X1)

procedure f2:
  p(X2)
  if (++c2 = 1) p(Y)
  v(X2)
  compute B
  p(X2)
  if (--c2 = 0) v(Y)
  v(X2)
问computeA和computeB各自能有多少并发执行，会不会出现饿死？

2 给出一个cpu的频率，使用基于时间片的轮转队列调度，并给出了参数。求调度的效率和
响应时间。

3 使用多级页表，给出一些参数，如虚实地址空间大小、页大小、页表项大小等，问:
a) 多级页表的优点
b) 如果页表限制在一个页面里，问有多少页表项？
c) 进程页表占用多少内存？

4 把一个UNIX文件卷复制到另一个磁盘上，问:
a) UNIX文件卷由哪几部分组成？
b) 只复制文件数据，包括目录之后，不能访问，为什么？
c) 终于搞好了之后，发现有重复的硬链接，为什么？

5 给出了一个使用pthread的程序代码，里面系统调用包括fork()，thread()，join()等等
，中间穿插print HELLO。问最后一共打印了多少个HELLO