山东科技大学数据结构与操作系统2004-2008、2010-2015历年考研真题汇编
● 摘要
科目代码：416 请在答题纸（本）上做题，在此试卷及草稿纸上做题无效！ 山东科技大学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页