一:简要回答下列问题(共40分)
1.假设一棵二叉树的层序序列是ABCDEFGHIJ和中序序列是DBGEHJACIF,请画出该树
.(6分)
2.简单比较文件的多重表和倒排表组织方式各自的特点.(6分)
3.画出对算术表达式A-B*C/D+E^F求值时操作数栈和运算符栈的变化过程.(6分)
4.找出所有满足下列条件的二叉树6分)
a)它们在先序遍历和中序遍历时,得到的结点访问序列相同;
b)它们在后序遍历和中序遍历时,得到的结点访问序列相同;
c)它们在先序遍历和后序遍历时,得到的结点访问序列相同.
5.对一个由n个关键字不同的记录构成的序列,能否用比2n-3少的次数选出该序列中
关键字取最大值和关键字取最小值的记录?请说明如何实现?在最坏情况下至少进行
多少次比较?(8分)
6.已知某文件经过置换选择排序后,得到长度分别为47,9,31,18,4,12,23,7的8个初
始归并段.试为3路平衡归并设计读写外存次数最少的归并方案,并求出读写外存的
次数.(8分)
二:
已知L是无表头结点的单链表,其中P结点既不是首元结点,也不是尾元结点,(10分
)
a)在P结点后插入S结点的语句序列是______
b)在P结点前插入S结点的语句序列是______
c)在表首插入S结点的语句序列是______
d)在表尾插入S结点的语句序列是______
(1) P^.next:=S;
(2) P^.next:=P^.next^.next;
(3) P^.next:=S^.next;
(4) S^.next:=P^.next;
(5) S^.next:=L;
(6) S^.next:=NIL;
(7) Q:=P;
(8) WHILE P^.next<>Q DO P:=P^.next;
(9) WHILE P^.next<>NIL DO P:=P^.next;
(10) P:=Q;
(11) P:=L;
(12) L:=S;
(13) L:=P;
三:
设计一个符号表的表示方法,编写算法使得在该表中进行查询,插入和删除任何一个
标识符X的操作在O(1)的时间内.假设1<=x<=m,n为要插入的个数,所需空间为m+n.
(10分)
四:
试利用Dijkstra算法求下图中从顶点a到其它各顶点的最短路径,写出执行算法过程
中各步的状态.(10分)
____________
/ 4 \
↓ 6 \
b------→e___9 \
15↑ ↑ \ /
/ 2 /8 ↓/
a------→c g (和严蔚敏习题集上题目相同)
\ \4 ↑↑
12↓ 5 ↓ 10/ /
d←------f__/ /
\___________/
3
五:
以顺序存储结构表示串,设计算法,求串S中出现的第一个最长重复子串及其位置并
分析算法的时间复杂度.(15分)
六:
写出按后序序列遍历中序线索树的算法.(15分)
1.假设一棵二叉树的层序序列是ABCDEFGHIJ和中序序列是DBGEHJACIF,请画出该树
.(6分)
2.简单比较文件的多重表和倒排表组织方式各自的特点.(6分)
3.画出对算术表达式A-B*C/D+E^F求值时操作数栈和运算符栈的变化过程.(6分)
4.找出所有满足下列条件的二叉树6分)
a)它们在先序遍历和中序遍历时,得到的结点访问序列相同;
b)它们在后序遍历和中序遍历时,得到的结点访问序列相同;
c)它们在先序遍历和后序遍历时,得到的结点访问序列相同.
5.对一个由n个关键字不同的记录构成的序列,能否用比2n-3少的次数选出该序列中
关键字取最大值和关键字取最小值的记录?请说明如何实现?在最坏情况下至少进行
多少次比较?(8分)
6.已知某文件经过置换选择排序后,得到长度分别为47,9,31,18,4,12,23,7的8个初
始归并段.试为3路平衡归并设计读写外存次数最少的归并方案,并求出读写外存的
次数.(8分)
二:
已知L是无表头结点的单链表,其中P结点既不是首元结点,也不是尾元结点,(10分
)
a)在P结点后插入S结点的语句序列是______
b)在P结点前插入S结点的语句序列是______
c)在表首插入S结点的语句序列是______
d)在表尾插入S结点的语句序列是______
(1) P^.next:=S;
(2) P^.next:=P^.next^.next;
(3) P^.next:=S^.next;
(4) S^.next:=P^.next;
(5) S^.next:=L;
(6) S^.next:=NIL;
(7) Q:=P;
(8) WHILE P^.next<>Q DO P:=P^.next;
(9) WHILE P^.next<>NIL DO P:=P^.next;
(10) P:=Q;
(11) P:=L;
(12) L:=S;
(13) L:=P;
三:
设计一个符号表的表示方法,编写算法使得在该表中进行查询,插入和删除任何一个
标识符X的操作在O(1)的时间内.假设1<=x<=m,n为要插入的个数,所需空间为m+n.
(10分)
四:
试利用Dijkstra算法求下图中从顶点a到其它各顶点的最短路径,写出执行算法过程
中各步的状态.(10分)
____________
/ 4 \
↓ 6 \
b------→e___9 \
15↑ ↑ \ /
/ 2 /8 ↓/
a------→c g (和严蔚敏习题集上题目相同)
\ \4 ↑↑
12↓ 5 ↓ 10/ /
d←------f__/ /
\___________/
3
五:
以顺序存储结构表示串,设计算法,求串S中出现的第一个最长重复子串及其位置并
分析算法的时间复杂度.(15分)
六:
写出按后序序列遍历中序线索树的算法.(15分)