电大《数据结构（本）》复习题及答案(3)

_________________、_________________。

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第 14 页 共 30 页

四、程序填空题（每空2分，共16分）

第 15 页 共 30 页

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库电大《数据结构（本）》复习题及答案(3)在线全文阅读。