- —四川最大高校综合门户网
（共3页） 说明： 1、本试卷分为数据结构和操作系统两部分。数据结构部分共六题，满分100分；操作系统部分共三题满分50分。全试卷全九题，满分150分。 2、答案一律写在答题纸上。 3、答卷应字迹清楚，语义确切。 数据结构部分 注意事项： 1、算法应说明基本思路，应对
（共3页）
说明：
1、本试卷分为数据结构和操作系统两部分。数据结构部分共六题，满分100分；操作系统部分共三题满分50分。全试卷全九题，满分150分。
2、答案一律写在答题纸上。
3、答卷应字迹清楚，语义确切。
数据结构部分
注意事项：
1、算法应说明基本思路，应对主要数据类型、变量给出说明，所写算法应结构清晰、简明易懂，应加上必要的注释；
2、算法可用（类）PASCAL语言、C语言等你所熟悉的高级语言编写，但要注明语种。
一、解答下列问题（共30分）：
1、[5分]线性表可用顺序表或链表存储，试问这两种存储表示各有哪些主要优缺点？
2、[5分]利用广义表的head和tail操作写出函数表达式，把单元素banana从广义表L3：
（（（apple）,(pear),(banana),(orange)））
中分离出来。
3、[5分]如果一棵度为m的树有n1个度为1的结点，有n2个度2的结点，…，nm个度为m的结点，试问有多少个度为0的结点？
4、[5分]已知一棵树的先根次序遍历的结果与其对应二叉树表示（长子-兄弟表示）的前序遍历结果相同，树的后根次序遍历结果与其对应二叉树表示的中序遍结果相同。试问利用树的先树次序遍历结果和后根次序遍历结果能否唯一确定一棵树？（如能请说明原因，如不能请举例说明。）
5、[5分]有n个顶点的有向连通图最多有多少条边？最少有多少条边？
6、[5分]分析表1，回答问题：为什么要用二叉排序树表示动态查找表？
查找 插入 删除
无序顺序表 O(n) O(l) O(n)
无序线性链表 O(n) O(l) O(l)
有序顺序表 O(logn) O(n) O(n)
有序线性链表 O(n) O(l) O(l)
第1页
二、[10分]一棵二叉树的中序遍历序列为BCDAFEHJIG，后序遍历序列为ECBFJIHGEA，要求：
1、画出此二叉权
2、将此二叉树转换为树或森林
三、[15分]设有一有向图G如图1所示：
1
6
2
3
4
5
1、画出图G的邻接表存储表示（邻接顶点要请以顶点序号递增序排列，以使答案唯一）。
2、写出从顶点1开始按深度优先遍历G得到的顶点序列。
四、[15分]如果一个字符串从前往后扫描与从后往前扫描得到的结果完全一样，则称该字符串为回文（如ababa和abba是回文，abb不是回文）。请写一个判定任意输入的字符串是否回文的算法，并分析算法的时间复杂度和空间复杂度。（注意：由于输入的字符串是任意的，所以字符串的长度是可变化的，未知的。可在输入的字符串前后加上起始符$的结束符#，但它们不属于字符串中的符号。）
五、[15分]试设计一个算法，使得在O(n)的时间内重排数组，将所有取负值的排序碱排在所有取正值（非负值）的排序码之前。
第2页
六、[15分]假定用一个循环链表示来实现一个序表，并让指针head指向具有最小关键码的结点。指针current初始时等于head，每次搜索后指向当前检索的结点，但如果搜索不成功则current重置为head。试编写一个函数search(head,current,key)实现这种搜索。当搜索成功时函数返回被检索的结点地址，若搜索不成功则函数返回空指针。请说明如何保持指针currnet以减少搜索时的平均搜索长度。
操作系统部分
一、简答题（每小题5分，共30分）
1、什么是操作系统？列举4种操作系统的名称。
2、进程的5种基本状态分别是什么？画出状态转换的进程状态图。
3、如何理解产生死锁的4个必要条件？
4、Spooling系统由几部分组成？Spooling系统有哪些好处？
5、什么叫文件？试说明文件目录的作用，它一般应包括哪些信息。
6、有哪些途径可以提高磁盘I/O的速度？
二、（10分）在视频通信系统中，由进程pa采集一帧图像信息并存入环形缓冲区Buffer中，进程Pb从Buffer中陂一帧数据进行处理。假设Buffer的大小为N，试用P，V操作实现进程Pa和Pb。
三、（10分）考虑下面的页访问串：
1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6，假定分别有1个，3个，5个，7个物理块。试问：若应用下面的页面替换算法，在上述四种情况下分别会出现多少次缺页中断？注意，所给定的物理块初始都为空，因此，首次访问一页时就会发生缺页中断。
（1）RU替换法算法。 （2）FIFO替换算法。 （3）Optimal替换算法。