这个是我费了好大劲才弄到的，希望大家不要用它来挣钱。
2007年复旦大学 数据结构与计算机系统基础(804) 专业课试题
数据结构部分：
1. 二叉数的层次序遍历（可以用C++或Java 语言实现）
2. 输出下面每一步操作的结果
ArrayQueue Q = new ArrayQueue();
Q.enqueue('F');
Q.enqueue('U');
Q.enqueue('D');
Q.enqueue('A');
Q.enqueue('N');
Q.dequeue();
Q.dequeue();
Q.dequeue();
Q.enqueue('B');
Q.empty();
3. 快速排序，归并排序，堆排序的时间复杂度均为O(nlogn)，请问那种排序算法的速度最快。
4. 在什么样的应用场景下需要稳定的（stable）排序算法？
5. 写一个程序,将一个普通的数组转变成一个三叉排序堆(三叉排序堆是一个符合最小树原则的完全三叉树)。
计算机系统部分：
1. 一共三个小题
typedef point{
int x;
int y;
int z;
}
typedef {
int i;
int j;
union{
struct point p;
int c;
double d;
}u;
double e;
}m;
int main()
{
struct *m=calloc(sizeof(m));
m.u.p.x = 10;
m.u.p.y = 7;
m.u.p.z = 11;
printf("x=%d, y=%d, z=%d",m.u.p.x, m.u.p.y, m.u.p.z);
}
请问程序的输出结果是什么?
后面的两个小题与这个小题相似;
2. 跟样题中的第一题有些相似。
typedef struct{
char name[5];
double height;
double *components;
short type;
char id;
}Exam_Structure1;
typedef struct{
char *class;
unsigned short color;
short m;
unsigned n;
int price;
}Exam_Structure2;
(1) 请使用下面的模板表示出Exam_Structure1和Exam_Structure2的结构（最大24字节）；
Exam_Structure1
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
+--+--+--+--+--+--+--+--+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| |
+--+--+--+--+--+--+--+--+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
Exam_Structure2
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
+--+--+--+--+--+--+--+--+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| |
+--+--+--+--+--+--+--+--+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
(2) 定义一个结构体叫Exam_Modified，它是由Exam_Structure1修改而来。问应该如何修改Exam_Structure1，才能使Exam_Modified的实例占用最少的存储空间，Exam_Modified的一个实例的大小为多少？
typedef struct{
}Exam_Modified;
3. 下面一段程序
int foo(int *a, int n)
{
int i, x, y;
for(i=0; i<n; i++)
{
x = a;
y *= x;
}
return y;
}
设x为寄存器变量，L1 cache的访问时间为3个时钟周期，L2 cache的访问时间为7个周期，主存的访问时间为30个周期，请问：
(1) 如果每一次循环均是L1 cache miss和L2 cache miss，请问每次循环所需要的时间是多少？
(2) 现在设有一个8字节大小的L2 cache，那么现在循环操作所需要的平均时间是多少？
3. 考得是跟虚拟内存有关的内容，在CSAPP那本书的第十章均有相关的练习。这次的考题考得有端到端的之转换（虚拟地址转换成物理地址），变量的cache命中率等问题，不是很难的。
下面一段程序
typedef int array[4][4]
array dst,src;
void bar(int dst, int src)
{
int i,j;
for(i=0;i<4;i++)
for(j=3;j>=0;j--)
dst[j] = src[j]
}
void main()
{
L0:
array dst, src;
if(fork())
{ L1:
/* run in child process */
bar(dst, src);
}
L2:
bar(dst, src);
}
程序大概就是这个样子，然后给出了一些数据，虚存大小是256MB，物理内存是64MB，TLB是2 way set associative，八行，共十六个条目。cache是直接映射（direct-mapped）的，写穿（write-through），两个数据块，每个数据块4个字节，共八个字节。
第一个小题问得是子进程创建完成，还未运行的时候，其是否会影响父进程的TLB和cache内容，要详答。
第二个小题给出变量dst和src的虚拟地址，还有TLB等寄存器的一些内容，让你进行地址翻译。
第三个小题让你填写变量dst在L1和L2处时，各元素被cache命中的情况（填表），以及计算dst的cache未命中率
就这些了，希望能给后来人一些帮助。 |
收藏
点赞!
反对!