- —四川最大高校综合门户网
1、本试卷分为数据结构和操作系统两部分。数据结构部分共六题，满分100分；操作系统部分共三题满分50分。全试卷全九题，满分150分。 2、答案一律写在答题纸上。 3、答卷应字迹清楚，语义确切。 数据结构部分 注意事项： 1、算法应说明基本思路，应对主要数据类型、变量
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以减少搜索时的平均搜索长度。
离散数学部分
一、（10分）证明：
。
二、（10分）设集合 ， 上的二元关系：
R={<a,b>,<b,c>,<c,b>},
求R的自反闭包r(R)，对称闭包s（R）和传递闭包t(R.)。
三、（15分）设<G,*>为一个群，B是G的有限非空子集，证明：若运算*在B上封闭，则<B,*>是<G,*>的子群。
四、（15分）若在一个n个人（n 3）的联会上，任意两个人合起来认识其余的n－2个人，证明这n个人可以排成一排，使得每个人都认识他的排中的左、右邻。
（说明：①题中的“认识”是指相互的，即若A认识B，那么B也认识A；
②排头和排尾的“左、右邻”只有一个：左邻或者右邻。）