数据结构习题集-南京廖华答案网

数据结构习题集下载本文

内容发布更新时间 : 2024/5/3 23:10:19星期一下面是文章的全部内容请认真阅读。

平均查找长度。查找失败时需对键值的最多比较次数。

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) 。

(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}

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．请编写一个快速排序的非递归算法。

附录：

大连理工大学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；

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分)

Word文档下载：数据结构习题集.doc

搜索更多:数据结构习题集