_________________、_________________。
24．两个串相等的充分必要条件是___________________________________________________。 25．一棵二叉树叶结点〈终端结点〉数为5，单分支结点数为2，该树共有____________个结点。 26．根据搜索方法的不同，图的遍历有__________________________________、__________________________________两种方法。
27．一个有序表{3，4，10，14，34，43，46，64，75，78，90，96，130}用折半查找法查找值为90的结点，经_________________次比较后查找成功。
三、综合题（每小题10分，共30分）
28．(1)已知某二叉树的后序遍历序列是debca，中序遍历序列是dbeac，试画出该二叉树。 (2)若上述二叉树的各个结点的字符分别代表不同的整数(其中没有相等的)，并恰好使该树成为一棵二叉排序树，试给出a、b、c、d、e的大小关系。
(3)给出该树的前序遍历序列。
29．(1)一组记录的关键字序列为{45，40，65，43，35，95}，写出利用快速排序的方法，以第一个记录为基准得到的一趟划分的结果(要求给出一趟划分中每次扫描和交换的结果〉。
(2)对序列{45，40，65，43，35，95}利用直接插入排序，写出逐次插入过程(从第一个元素一直到第六个元素〉。
30．(1)设有查找表{5，14，2，6，18，7，4，16，3}，依次取表中数据，构造一棵二叉排序树。 (2)说明如何通过序列的二叉排序树得到相应序列的排序结果。
四、程序填空题（每空2分，共16分）
31．以下函数在a[O]到a[n-1]中，用折半查找算法查找关键字等于k的记录，查找成功返回该记录的下标，失败时返回-1，完成程序中的空格。
第 11 页 共 30 页
32．以下函数为链栈的进栈操作，x是要进栈的结点的数据域，top为钱顶指针
第 12 页 共 30 页
第 13 页 共 30 页
参考答案
一、单项选择题（每小题2芳，共30分） DCCBA CCAAB CCDCD
二、填空题（每题2分，共24分} 16．树形、图状 17．图状
18．p->next=head; 19．r=f 20．在>next=hs; 21．r->next=的 22．顺序存储、链式存储 23．2i、2i+1
24．串长度相等且对应位置的字符相等 26．深度优先搜索遍历、广度优先搜索遍历 27．4
三、结合应用题（每小题10分，共30分） 28．(1)
(2)d
四、程序填空题（每空2分，共16分）
第 15 页 共 30 页