平均查找长度。查找失败时需对键值的最多比较次数。
2．将整数序列{8，6，3，1，2，5，9，7，4}中的数依次插入到一棵空的二叉排序树中，求在等概率情况下，查找成功的平均查找长度，查找失败时对键值的最多比较次数。再画出从二叉排序树中删除结点6和8的结果。
3．将整数序列{8，6，3，1，2，5，9，7，41中的数依次插入到一棵空的平衡二叉排序树中，求在等概率情况下，查找成功的平均检索长度，查找失败时对键值的最多比较次数o
4．按不同的输入顺序输入4，5，6，建立相应的不同形态的二叉排序树。
5．设有键值序列{25，40，33，47，12，66，72，87，94，22，5，58}散列表长为12，散列函数为H(key)=key％11，用拉链法处理冲突，请画出散列表，在等概率情况下，求查找成功的平均查找长度和查找失败的平均查找长度。
6．已知一个散列函数为H(key)=key％13，采用双散列法处理冲突，H1(key)=key％11+1，探查序列为di=(H(key)+i* H1(key))％m，i=1，2，?m-1，散列表见表1，要求回答下列问题：
(1)对表中键值21，57，45和50进行查找时，所需进行的比较次数各为多少? (2)在等概率情况下查找时，查找成功的平均查找长度是多少? 0 1 2 3 4 5 6 7 8 9 10 11 12
表1 散列表
四、算法设计题
1．设二叉树用二叉链表表示，且每个结点的键值互不相同，请编写判别该二叉树是否为二叉排序树的非递归算法。
50 21 5 7 45 37 第八章 排序
一、单项选择题
1．对n个不同的记录按排序码值从小到大次序重新排列，用冒泡(起泡)排序方法，初始序列在 （1） 情况下，与排序码值总比较次数最少，在 （2） 情况下，与排序码值总比较次数最多；用直接插入排序方法，初始序列在 （3） 情况下，与排序码值总比较次数最少，在 （4） 情况下，与排序码值总比较次数最多；用快速排序方法在 （5） 情况下，与排序码值总比较次数最少，在 （5） 情况下与排序码值总比较次数最多。
(1)-(6)：
A．按排序码值从小到大排列 B．按排序码值从大到小排列 C．随机排列(完全无序) D．基本按排序码值升序排列
2．用冒泡排序方法对n个记录按排序码值从小到大排序时，当初始序列是按排序码值从大到小排列时，与码值总比较次数是 （7） 。 (7)：A．n-1 B．n C．n+1 D．n(n-1)／2
3．下列排序方法中，与排序码值总比较次数与待排序记录的初始序列排列状态无关的是 (8) 。
16
(8)：A．直接插入排序 B．冒泡排序 C．快速排序 D．直接选择排序 4．将6个不同的整数进行排序，至少需要比较 (9) 次，至多需要比较 (10) 次。 (9)-(10)：A．5 B．6 C．15 D．21
5．若需要时间复杂度在O(nlog2n)内，对整数数组进行排序，且要求排序方法是稳定的，则可选择的排序方法是 (11) 。
(11)：A．快速排序 B．归并排序 C．堆排序 D．直接插入排序
6．当待排序的整数是有序序列时，采用 (12) 方法比较好，其时间复杂度为O(n)，而采用 （13）方法却正好相反，达到最坏情况下时间复杂度为O(n)；无论待排序序列排列是否有序，采用 （14）方法的时间复杂度都是O(n)。
(12)-(14)：A．快速排序 B．冒泡排序 C．归并排序 D．直接选择排序 7．堆是一种 (15) 排序。
(15)：A．插入 B．选择 C．交换 D．归并
8．若一组记录的排序码值序列为{40，80，50，30，60，70}，利用堆排序方法进行排序，初建的大顶堆是 (16) 。
(16)：A．80，40，50，30，60，70 B．80，70，60，50，40，30 C．80，70，50，40，30，60 D．80，60，70，30，40，50
9．若一组记录的排序码值序列为{50，80，30，40，70，60}利用快速排序方法，以第一个记录为基准，得到一趟快速排序的结果为 （17） 。
(17)：A．30，40，50，60，70，80 B．40，30，50，80，70，60 C．50，30，40，70，60，80 D．40，50，30，70，60，80 10．下列几种排序方法中要求辅助空间最大的是 （18） 。
(18)：A．堆排序 B．直接选择排序 C．归并排序 D．快速排序
11．已知A[m]中每个数组元素距其最终位置不远，采用下列 (19) 排序方法最节省时间。
(19)：A．直接插入 B．堆 C．快速 D．直接选择
12．设有10000个互不相等的无序整数，若仅要求找出其中前10个最大整数，最好采用 （20） 排序方法。
(20)：A．归并 B．堆 C．快速 D．直接选择
13．在下列排序方法中不需要对排序码值进行比较就能进行排序的是 （21） 。 (21)：A：基数排序 B．快速排序 C．直接插入排序 D．堆排序
14．给定排序码值序列为{F，B，J，C，E，A，I，D，C，H}，对其按字母的字典序列的次序进行排列，希尔(Shell)排序的第一趟(d1=5)结果应为 （22） ，冒泡排序(大数下沉)的第一趟排序结果应为 （23） ，快速排序的第一趟排序结果为 （24） ，二路归并排序的第一趟排序结果是 （25） 。
(22)-(25)：A．{B，F，C，J，A，E，D，I，C，H} B．{C，B，D，A，E，F，I，C，J，H} C．{B，F，C，E，A，I，D，C，H，J}
17
2
2
D．{A，B，D，C，E，F，I，J，C，H}
二、填空题
1．内部排序方法按排序采用的策略可划分为五类： （1）、 （2）、 （3）、 （4）、 （5）。 2．快速排序平均情况下的时间复杂度为 （6） ，其最坏情况下的时间复杂度为 （7）。 3．当待排序的记录个数n很大时，应采用平均时间复杂度为 （8）即 （9）、 （10）、 （11），在这些方法中当排序码值是随机分布时，采用 （12） 排序方法的平均时间复杂度最小。当希望排序方法是稳定时，应采用 (13) 排序方法，若只从节省空间考虑，最节省空间的是 （14） 方法。
4．对一组整数{60，40，90，20，10，70，50，80}进行直接插入排序时，当把第7个整数50插入到有序表中时，为寻找插人位置需比较 （15）次。
5．从未排序序列中挑选最小(最大)元素，并将其依次放到已排序序列的一端，称为 （16）排序。
6．对n个记录进行归并排序，所需要的辅助存储空间是 （17） ，其平均时间复杂度是 （18） ，最坏情况下的时间复杂度是 （19） 。
7．对n个记录进行冒泡排序，最坏情况下的时间复杂度是 （20） 。
8．对20个记录进行归并排序时，共需进行 （21） 趟归并，在第三趟归并时是把最大长度为 （22） 的有序表两两归并为长度为 （23） 的有序表。 三、应用题
1．举例说明本章介绍的排序方法中哪些是不稳定的?
2．已知排序码值序列{17，18，60，40，7，32，73，65，85}，请写出冒泡排序每一趟的排序结果。
3．对于排序码值序列{10，18，14，13，16，12，11，9，15，8}，给出希尔排序(dl=5，d2=2，d3=1)的每一趟排序结果。
4．判断下列序列是否为大顶堆?若不是，则把它们调整为大顶堆。 (1){90，86，48，73，35，40，42，58，66，20} (2){12，70，34，66，24，56，50，90，86，36} 四、算法设计题
1．在带表头结点的单链表上，编写一个实现直接选择排序的算法。 2．请编写一个快速排序的非递归算法。
18
附录：
大连理工大学2002年硕士入学试题
数据结构部分(共50分)
一、算法填空题(20分)
1．对以下函数填空，实现将头指针为h的单链表逆置，即原链表的第一个结点变成逆置后新链表的最后一个结点，原链表的第二个结点变成新链表的倒数第二个结点，如此等等，直到最后一个结点作为新链表的第一个结点，并返回指向该结点的指针。设单链表结点类型的定义为
typedef struct node {int data；
strcut node *next； }NODE；
NODE *dlbnz(NODE*h) { NODE *p，*q； q=NULL； while(h) p=h； h=h->next； ； ； } return q； }
2．假设算术表达式由字符串b表示，其中可以包含三种括号：圆括号和方括号及花括号，其嵌套的顺序随意，如{[]([])}。请对以下函数填空，实现判别给定表达式中所含括号是否正确配对出现的算法。 #define M 10 int khjc(char *b) { char sM}； int i，j=0，f=1；
j=0；
for(i=0；f&&b[i]!=?\\0?；i++) { switch(b[i])
{ case ?(?： ；break； case ?[?： ；break； case ?{?： ；break；
19
case ?)?： case ?]?：
case ?[?：if(j==0;||b[I]!= ) f=0； } }
return f&& ； }
3．对以下函数填空，实现以带头结点的单链表h为存储结构的直接选择排序。设单链表结点类型的定义为
typedef struct node { int key；
struct node *next；
}NODE； void pxx(NODE *h) { NODE *p，*q，*m； int z； p=h->next； while(p!=NULL) { q=p->next； m=p；
while(q!=NULL)
{ if(m->key>q->key) ； ； } if(p!=m) { x=p->key； p->key=m->key； m->key=x； } ；} }
二、算法设计题(30分)
请用类C或类PASCAL语言设计实现下列功能的算法。
1．设二叉排序树以二叉链表为存储结构，请编写一个非递归算法，从大到小输出二叉排序树中所有其值不小于X的键值。(10分)
2．设由n个整数组成一个大根堆(即第一个数是堆中的最大值)，请编写一个时间复杂度为O(log2n)的算法，实现将整数X插入到堆中，并保证插入后仍是大根堆。(10分)
20