2008年华南理工大学831计算机专业综合(数据结构、操作系统)考研试题

831华南理工大学2008年攻读硕士学位研究生入学考试试卷（请在答题纸上做答，试卷上做答无效，试后本卷必须与答题纸一同交回）科目名称：计算机专业综合(数据结构、操作系统)适用专业：系统分析与集成，计算机系统结构，计算机软件与理论，计算机应用技术，生物医学工程共5页第1页数据结构部分一．选择题（每题只有一个答案正确，每题2分，共24分）1．带头结点的单链表head为空的判断条件是()A．head==NULLB．head—＞next==NULLC．head—＞next==headD．head!=NULL2．若进栈序列为a，b，c，则通过入、出栈操作可能得到的a，b，c的不同排列数是()。A．4B．5C．6D．73．下列说法正确的是()。A．二叉树中任何一个结点的度都为2B．二叉树的度为2C．一棵二叉树的度可小于2D．任何一棵二叉树中至少有一个结点的度为24．一棵有124个叶子结点的完全二叉树，最多有()个结点。A．247B．124C．248D．1255．以下说法错误的是()。A．存在这样的二叉树，对其采用任何次序的遍历其结点访问序列均相同。B．二叉树是树的特殊情形。C．由树转换成二叉树，其根结点的右子树总是空的。D在二又树只有一棵子树的情况下，也要指出是左子树还是右子树6．有拓扑排序的图—定是()。A有环图B．无向图C．强连通图D．有向无环图第2页7．在待排序的元素序列基本有序的前提下，效率最高的排序方法是()。A．插入排序B．选择排序C．快速排序D．归并排序8．从逻缉上可以把数据结构分为（）。A．动态结构和静态结构B．紧凑结构和非紧凑结构C．线性结构和非线性结构D．内部结构和外部结构9．下面程序的时间复杂度为()．for〔i=0；i＜m；i++)for(j=0：j＜n；j++)A[i][j]＝i*j；A．O(m)B．O(n)C．O(m×n)D．O(m+n)2210.三维数组A[4][5][6]按行优先存储方法存储在内存中，若每个元素占2个存储单元，且数组中第一个元素A[0][0][0]的存储地址为120，则元素A[3][4][5]存储地址为()。A.356B.358C.360D.36211.用DFS遍历一个有向无环图，并在DFS算法退栈返回时打印出相应顶点，则输出的顶点序列是()。A．逆拓扑有序的B．拓扑有序的C．无序的D．DFS遍历序列12．与其他查找方法相比，散列查找法的特点是()。A．通过关键字的比较进行查找B．通过关键字计算元素的存储地址进打查找C．通过关键字计算元素的存储地址并进行一定的比较进行查找D．以上都不是二．解答题（每题5分，共40分）1．已知查找表为{19，01．23，14，55，20，84，27，68，11，10，77}设定哈希函数为：H(key)=key％13，采用开放地址法的二次探测法解决冲突，试在0~18的散列第3页地址空间中对该关键字构造哈希表，并求出查找成功时的平均查找长度。(5分)2、如图所示的双向链表中，欲在*p前插入一个结点*s，请写出关键代码完成有关操作。(5分)3、用于通信的电文由字符集[a，b，c，d，e，f，g,h]中的字母构成，这8个字母在电文中出现的概率分别为(0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10)。请为这8个字母设计哈夫曼编码。(5分)4、由如图所示的二叉树，回答以下问题：(5分)（1）其中序遍历序列是什么？（2）其前序遍历序列是什么？（3）其后序遍历序列是什么？5、己知顺序栈S，根据各步运算在括号内及问号处填写相应的内容。(5分)序号运算运算后S栈中的内容栈顶元素1）InitStack()S=()?2）Push(S,a)S=()?3）Push(S,b)S=()?4）Push(S,c)S=()?5）Pop(S,x)S=()?6）StackEmpty(S)S=()?7）StackTop(S)S=()?8）Pop(S,x)S=()?9）Pop(S,x)S=()?第4页6、画出以顶点V1为初始源点遍历图如下所示的有向图所得到的DFS和BFS生成森林。(5分)7、如下所示的连通图，请用Prim算法构造其最小生成树。(5分)8、将下列按关键字的值从大到小的直接选择排序算法补充完整。(5分)Select(listr,intn){for(i=1；；i++){k=i;for(j=i+1;;j++)if(r[k].keyr[j].key);if()swap(r[k],r[i]);//r[k]与r[i]交换}}三．算法设计。做出简要分析并写函数。（共11分）1.在链串上实现串的判等运算Equal(S，T)(5分)2.试写—个算法，基于图的深度优先搜索策略判别以邻接表方式存储的有向图中是否存在由顶点Vi到顶点Vj的路径(i≠j)。(6分)V1V3V4V2V5V8V7V6第5页操作系统部分一、名词解释（15分）临界区，时钟页面置换算法，请求调页二、简答题1、什么是核心态和用户态？为什么要设置这两个状态？（7分）2、使用一个文件之前为什么需要打开操作？打开文件实际上主要做了哪些事情？（7分）3、什么是中断？中断处理的过程是怎样的？（8分）4、某磁盘有10601个柱面，寻道时移过每个柱面花费时间0.8ms(毫秒)。若不采取措施尽量使得文件的块在磁盘上紧密存放，则逻辑上相邻的两个块平均间隔13个柱面。但是，如果操作系统尽量把相关的块放在一起，此时块间的平均距离为2个柱面。设旋转延迟时间为8.33ms(毫秒)，传输速率为17µs(微秒)/块，则在这两种情况下传输一个100块的文件需要多长时间？你对这个结果有什么看法？能否举出一个在现实操作系统中利用这一现象提高性能的例子？（8分）三、在一页式系统中，页面的大小为1KB，地址寄存器的字长为20位。现有一长度为4KB的用户程序，其4个页面分别被分配在内存的10，14，15和18块中。当程序中的访问地址为2058时，试说明地址变换的过程。（10分）四、设下列算式中的每一步计算均用一个进程来完成。画出进程流程图（尽可能实现并发），并写出程序描述，用信号量的up、down操作实现各进程之间的同步。（10分）A*B―(C＋D)*(E―F)五、什么是死锁？死锁发生的必要条件是什么？（10分）