发布时间 : 星期二 文章数据结构复习题090612更新完毕开始阅读5f34c8fa04a1b0717fd5ddd8
26．下表给出了某工程各工序之间的优先关系和各工序所需时间。解答下列问题： （1）画出相应的AOE图；
（2）给出各事件的最早发生时间和最晚发生时间； （3）找出关键路径，并指明完成该工程所需最短时间；
（4）若把AOE网视为AOV网，给出其一个拓扑序列的例子。 工序A 代号 时间 15 先驱－ 工作 B C D E F G H I J K L M M 10 50 8 15 40 90 15 80 60 15 30 20 40 － A,B B C,D B E G,I E I F,I H,J,K L G
27．某不带权有向图如下所示。给出其邻接矩阵和邻接表表示。
AFBGEDC
28．求如下AOE图的关键路径，要求给出求解过程。
29．有一组数据，内容如下：8，15，38，57，68，88，98，108，129，234，256 试用二分查找法查找68和222，要求先画出二叉折半检索树，然后写出查找过程。
30．已知有序表为｛12，18，24，35，47，50，62，83，90，115，134｝，请画出采用折半查找法对应的判断树。
31．设数据集合d＝｛1，12，5，8，3，10，7，13，9｝，试完成下列各题： （1）依次取d中各数据，构造一棵二叉排序树bt。 （2）如何依据此二叉树bt得到d的一个有序序列。 （3）画出在二叉树bt中删除“12”后的树结构。
32．对给定的数列R＝{7，16，4，8，20，9，6，18，5}，构造一棵二叉排序树，并且 （1）给出按中序遍历得到的数列R1。 （1）给出按后序遍历得到的数列R2。
33．已知序列{17，18，60，40，7，32，73，65，85}，请给出采用冒泡排序法对该序列作升序排序时每一趟的结果。
34．已知序列{503，87，512，61，908，170，897，275，653，462}，请给出采用快速排序法对该序列作升序排序时每一趟的结果。
35．已知序列{503，87，512，61，908，170，897，275，653，462}，请给出采用堆排序法对该序列作升序排序时每一趟的结果。
36．已知序列{503，87，512，61，908，170，897，275，653，462}，请给出采用希尔排序法对该序列作升序排序时每一趟的结果。
37．已知序列{17，18，60，40，7，32，73，65，85}，请给出采用直接插入排序法对该序列作升序排序时每一趟的结果。
38．设散列表的长度m＝13（0，1，2，?，12），散列函数为H（k）＝k mod m，给定的关键字序列为{19，14，23，10，68，20，84，27，55，11}。试画出用线性探测法解决冲突时所构造的散列表。
五、算法设计题。
1．已知一个顺序表L，其中的元素按值非递减有序排列，设计一个算法插入一个元素x后保持该顺序表仍按非递减有序排列。
2．设计一个算法从顺序表L中删除所有值为x的元素。
3．已知线性表元素递增有序，并以带头结点的单链表作存储结构，设计一个高效算法，删除表中所有值大于mink且小于maxk的元素（若表中存在这样的元素）。并分析所写算法的时间复杂度。
4．设计一个在带头结点的单链表中删除一个最小值结点的高效算法。 5．有一个不带头结点的单链表L（至少有一个结点），其头指针为head。设计一个算法将L逆置，即最后一个结点变成第一个结点，原来倒数第二个结点变成第二个结点，如此等等。 6．假设二叉树采用链式存储方式存储，编写一个二叉树前序遍历的非递归算法。 7．假设二叉树采用链式存储方式存储，编写一个二叉树后序遍历的非递归算法。 8．假设二叉树采用链式存储方式存储，编写一个二叉树中序遍历的非递归算法。
9．编写一个c函数。实现线性表就地逆置。即在原表的存储空间内将线性表（a1,a2,…,an）逆置为（an,…,a2,a1）。
10．编写一个单链表倒链程序，即将单链表中每个结点的前驱与后继关系颠倒。
11．在数组a[0?n-1]中存放有n个不同的整数，请编写一个函数，将a中的n个数按从小到大的顺序排列。
12．有一个不带头结点的单链表L（至少有一个结点），其头指针为head。设计一个算法将L逆置，即最后一个结点变成第一个结点，原来倒数第二个结点变成第二个结点，如此等等。
13．已知非空线性链表的第一个结点的指针为head，请写一个算法，将该链表中数据域值最小的结点移动到链表的最前端。编写的函数具有如下原型：void func(TLinkNode *head),其中链结点的结构如下：
struct TLinkNode {
int data;
TLinkNode *next; }
请完成该算法。
14．在数组a[0?n-1]中存放有n个不同的整数，请编写一个函数，将a中的n个数按从小到大的顺序排列，要求使用改进的插入排序算法，元素a[i]要插入的位置由折半（二分）查找算法找到。