科目代码：416 请在答题纸（本）上做题，在此试卷及草稿纸上做题无效！ 二、[10分]一棵二叉树的中序遍历序列为BCDAFEHJIG，后序遍历序列为ECBFJIHGEA，要求： 1、画出此二叉权 2、将此二叉树转换为树或森林 三、[15分]设有一有向图G如图1所示： 1 6 2 5 3 4 1、画出图G的邻接表存储表示（邻接顶点要请以顶点序号递增序排列，以使答案唯一）。 2、写出从顶点1开始按深度优先遍历G得到的顶点序列。 四、[15分]如果一个字符串从前往后扫描与从后往前扫描得到的结果完全一样，则称该字符串为回文（如ababa和abba是回文，abb不是回文）。请写一个判定任意输入的字符串是否回文的算法，并分析算法的时间复杂度和空间复杂度。（注意：由于输入的字符串是任意的，所以字符串的长度是可变化的，未知的。可在输入的字符串前后加上起始符$的结束符#，但它们不属于字符串中的符号。） 五、[15分]试设计一个算法，使得在O(n)的时间内重排数组，将所有取负值的排序碱排在所有取正值（非负值）的排序码之前。 山东科技大学2004年招收硕士学位研究生入学考试
数据结构与操作系统试卷
（共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(n) O(logn) O(n)
插入 O(l) O(l) O(n) O(l) 第1页
删除 O(n) O(l) O(n) O(l)
第2页
山东科技大学823数据结构与操作系统2004-2008、2010-2011、2013-2017年考研真题,暂无答案。
