数据结构c语言版期末考试 - 图文

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。 （2）给出按后序遍历得到的数列R2。

25

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}，请给出采用直接插入排

26

序法对该序列作升序排序时每一趟的结果。

38．设散列表的长度m＝13（0，1，2，?，12），散列函数为H（k）＝k mod m，给定的关键字序列为{19，14，23，10，68，20，84，27，55，11}。试画出用线性探测法解决冲突时所构造的散列表。

27

28