|
软件基础试题 共3页，第1页
2004 工程硕士学位研究生入学试题
科目名称：软件基础
第一部分 数据结构
一、 单项选择题：（每题 2 分，共 12 分）
1． 入桟序列是 a,b,c,d,e,则不可能的出桟序列是（ ）
① edcba ② decba ③ dceab ④ abcde
2．在一个单链表中，已知 q↑结点是 p↑结点的前驱结点，若在 q↑和 p↑之间插入 s↑结点，
则需执行以下哪组操作？ （ ）
① s↑.next:=p↑.next； p↑.next:=s；
② p↑.next:=s↑.next； s↑.next:=p；
③ q↑.next:=s； s↑.next:=p；
④ p↑.next:=s； s↑.next＝q；
3．广义表(()，())的表头和表尾分别为（ ）。
① ()，() ② ()，(()) ③ NIL, () ④ (), NIL
4．在线索化二叉树中，结点 p↑没有左子树的充要条件是：( )
① p↑.lchild=NIL ② p↑.ltag=1
③ p↑.ltag=1 AND p↑.lchild=NIL ④ 以上都不对
5．已知某二叉树的后序遍历序列是 dfgebca，中序遍历序列是 dbfegac，它的前序遍历序列是
（ ）
① abdefgc ② dabecgf ③ abcdefg ④ dbegacf
6. 设有 10000 个无序的元素，若希望最快的迭出前 10 个最大的元素，则（ ）算法最好
① 快速排序 ② 归并排序 ③ 希尔排序 ④ 堆排序
二、填空题：（每空 2 分，共 10 分）
1．数据结构是研究数据的 和物理结构以及它们之间的相互关系，并对这种结构
定义相适应的 ，设计出相应的算法。
供选择的答案：
（1）理想结构 （2）抽象结构 （3）物理结构 （4）逻辑结构
（5）结构 （6）运算 （7）算法 （8）规则
2．已知广义表 A=（a，b,c），B=（A，A），C=（a，（b，A），d, B），求下列各运算的结果。
head（head（tail（B）））= 。
tail（head（tail（C）））= 。
3．设哈希表长 m=13，哈希函数 H（k）=k MOD 11。表中已有四个记录，如果用二次探测再散
列处理冲突，关键字为 50 的记录的存储地址是 。
0 1 2 3 4 5 6 7 8 9 10 11 12
15 38 61 84
三、简答题：（每题 6 分，共 18 分）
1． 试述顺序查找法、折半查找法和分块查找法对查找表的要求。
2． 试提出二种判定一个图是否有回路的方法。
，更多更新年份持续更新，请在本站的考博信息网|www.kaoboinfo.com中的“考研试卷库”学校栏目中查询下载。
|
您现在的位置： 
