数据结构单元练习10.docx

数据结构单元练习10.docx

《数据结构单元练习10.docx》由会员分享，可在线阅读，更多相关《数据结构单元练习10.docx（20页珍藏版）》请在冰点文库上搜索。

数据结构单元练习10

单元测验10

一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳）

（ㄨ）

（1）如果某种排序算法不稳定，则该排序方法就没有实用价值。

（√）

（2）希尔排序是不稳定的排序。

（ㄨ）（3）冒泡排序是不稳定的排序。

（√）（4）对n个记录的进行快速排序，所需要的平均时间是O（nlog2n）。

（ㄨ）（5）堆排序所需的时间与待排序的记录个数无关。

（√）（6）当待排序的元素个数很多时，为了交换元素的位置要占用较多的时间，这是影响时间复杂度的主要因素。

（ㄨ）（7）快速排序在任何情况下都比其它排序方法速度快。

（√）（8）对快速排序来说，初始序列为正序或反序都是最坏情况。

（√）（9）采用归并排序可以实现外排序。

（√）（10）采用希尔方法排序时，若关键字的排列杂乱无序，则效率最高。

二．填空题

（1）大多数排序算法都有两个基本的操作：

比较和移动。

（2）评价排序算法优劣的主要标准是时间复杂度和算法所需的附加空间。

（3）根据被处理的数据在计算机中使用不同的存储设备，排序可分为：

内排序和外排序。

（4）外排序是指在排序过程中，数据的主要部分存放在计算机的外存中。

（5）对n个关键字进行冒泡排序，其可能的最小比较次数为：

n-1次。

（6）在最坏情况下，在第i趟直接插入排序中，要进行i-1次关键字的比较。

（7）对n个关键字进行冒泡排序，时间复杂度为O（n2）。

（8）快速排序在最坏情况下的时间复杂度是O（n2）。

（9）对于n个记录的集合进行归并排序，所需要的平均时间为：

O（log2n）。

（10）对于n个记录的集合进行归并排序，所需要的附加空间是O（n）。

（11）若原始数据接近无序，则选用快速排序最好。

（12）在排序前，关键字值相等的不同记录，排序后相对位置保持不变的排序方法，称为稳定排序方法。

（13）在插入排序和选择排序中，若初始数据基本正序，则选用插入排序较好。

（14）当增量为1时，该趟希尔排序与直接插入排序基本一致。

（15）第一趟排序后，序列中键值最大的记录交换到最后的排序算法是冒泡排序。

（16）依次将每个记录插入到一个有序的子文件中的排序方法称为直接插入排序。

（17）在插入排序、选择排序和归并排序中，排序是不稳定的为：

选择排序。

（18）在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需比较3次。

（19）两个序列分别为：

L1={25，57，48，37，92，86，12，33}

L2={25，37，33，12，48，57，86，92}。

用冒泡排序法对L1和L2进行排序，交换次数较少的是序列：

L2。

（20）对一组记录（54，35，96，21，12，72，60，44，80）进行直接选择排序时，第四次选择和交换后，未排序记录是54，72，60，96，80。

三．选择题

（1）排序是根据（A）的大小重新安排各元素的顺序。

A．关键字B．数组C．元素件D．结点

（2）评价排序算法好坏的标准主要是（D）。

A．执行时间B．辅助空间

C．算法本身的复杂度D．执行时间和所需的辅助空间

（3）直接插入排序的方法是（B）的排序方法。

A．不稳定B．稳定C．外部D．选择

（4）直接插入排序的方法要求被排序的数据（B）存储。

A．必须链表B．必须顺序C．顺序或链表D．可以任意

（5）排序方法中，从无序序列中选择关键字最小的记录，将其与无序区（初始为空）的第一个记录交换的排序方法，称为（D）。

A．希尔排序B．归并排序C．插入排序D.选择排序

（6）每次把待排序方的区间划分为左、右两个区间，其中左区间中元素的值不大于基准元素的值，右区间中元素的值不小于基准元素的值，此种排序方法叫做（C）。

A．冒泡排序B．堆排序C．快速排序D.归并排序

（7）快速排序在（C）情况下最易发挥其长处。

A．待排序的数据中含有多个相同的关键字B．待排序的数据已基本有序

C．待排序的数据完全无序D．待排序的数据中最大值与最小值相差悬殊

（8）下述几种排序方法中，要求内存量最大的是：

（D）。

A．插入排序B．选择排序C．快速排序D.归并排序

（9）直接插入排序的方法是从第（B）个元素开始，插入到前边适当位置的排序方法。

A．1B．2C．3D．n

（10）堆的形状是一棵（C）。

A．二叉排序树B．满二叉树C．完全二叉树D．平衡二叉树

（11）内排序是指在排序的整个过程中，全部数据都在计算机的（A）中完成的排序。

A．内存B．外存C．内存和外存D．寄存器

（12）快速排序的方法是（A）的排序方法。

A．不稳定B．稳定C．外部D．选择

（13）下列排序方法中，关键字比较次数与记录的初始排列次序无关的是（A）。

A．选择排序B．希尔排序C．插入排序D．冒泡排序

（14）下述几种排序方法中，平均时间复杂度最小的是（A）。

A．希尔排序B．插入排序C．冒泡排序D．选择排序

（15）对有n个记录的表作快速排序，在最坏情况下，算法的时间复杂度是（B）。

A．O（n）B．O（n2）C．O（nlog2n）D．O（n3）

（16）冒泡排序的方法对n个数据进行排序，第一趟排序共需要比较（C）次。

A．1B．2C．n-1D．n

（17）对ｎ个不同的排序码进行冒泡（递增）排序，在下列（B）情况比较的次数最多。

A．从小到大排列好的B．从大到小排列好的C．元素无序D．元素基本有序

（18）用直接插入排序法对下面的四个序列进行由小到大的排序，元素比较次数最少的是（B）。

A，94，32，40，90，80，46，21，69B．21，32，46，40，80，69，90，94

C．32，40，21，46，69，94，90，80D．90，69，80，46，21，32，94，40

（19）一组记录的排序码为（25，48，16，35，79，82，23，40），其中含有4个长度为2的有序表，按归并排序的方法对该序列进行一趟归并后的结果为：

（A）。

A，16253548234079823672B．16253548798223364072

C．16254835798223364072D．16253548792336407282

（20）一个数据序列的关键字为：

（46，79，56，38，40，84），采用快速排序，并以第一个数为基准得到第一次划分的结果为：

（C）

A．（38，40，46，56，79，84）B．（40，38，46，79，56，84）

C．（40，38，46，56，79，84）D．（40，38，46，79，56，84）

四．排序过程分析

1．已知数据序列{10，8，18，15，7，16}，写出采用直接插入算法排序时，每一趟排序的结果。

解：

1081815716

第一趟结束时结果：

[810]1815716

第二趟结束时结果：

[81018]15716

第三趟结束时结果：

[8101518]716

第四趟结束时结果：

[78101518]16

第五趟结束时结果：

[7810151618]

2．已知数据序列{18，17，60，40，07，32，73，65}，写出采用直接插入算法排序时，每一趟排序的结果。

解：

1817604007327365

第一趟结束时结果：

[1718]604007327365

第二趟结束时结果：

[171860]4007327365

第三趟结束时结果：

[17184060]07327365

第四趟结束时结果：

[0717184060]327365

第五趟结束时结果：

[071718324060]7365

第六趟结束时结果：

[07171832406073]65

第七趟结束时结果：

[0717183240606573]

3.已知数据序列{17，18，60，40，7，32，73，65，85}

请写出采用冒泡排序法对该序列作升序排序时每一趟的结果。

解：

17186040732736585

第一趟排序结果：

17184073260657385

第二趟排序结果：

171873240606573

第三趟排序结果：

1771832406065

第四趟排序结果：

71718324060

第五趟排序结果：

717183240

第五趟排序过程中已无记录交换，排序结束。

4．已知数据序列{80，18，9，90，27，75，42，69，34}

请写出采用冒泡排序法对该序列作升序排序时每一趟的结果。

解：

801809902775426934

第一趟排序结果：

180980277542693490

第二趟排序结果：

0918277542693480

第三趟排序结果：

09182742693475

第四趟排序结果：

091827423469

第五趟排序结果：

0918273440

第六趟排序结果：

09182734

第六趟排序过程中已无记录交换，排序结束。

5．已知数据序列{10，18，4，3，6，12，9，15，8}，写出希尔排序每一趟（设d=4、2、1）排序的结果。

解：

1018436129158

d=46124381891510

d=24361281591810

d=13468910121518

6．已知数据序列{12，02，16，30，28，10，17，20，06，18}，写出希尔排序每一趟排序的结果。

（设d=5、2、1）

解：

12021630281017200618

d=5

10021606181217203028

d=2

12021606171218203028

d=102061012161718202830

7．已知数据序列{10，18，4，3，6，12，9，15}，写出二路归并排序的每一趟排序结果。

[10][18][4][3][6][12][9][15]

[1018][34][612][915]第一趟排序结果

[341018][691215]第二趟排序结果

[346910121518]第三趟排序结果

8．已知数据序列{53，36，48，36，60，7，18，41}，写出采用简单选择排序的每一趟排序结果。

解：

[533648366071841]

（7）[36483660531841]

（718）[483660533641]

（71836）[4860533641]

（7183636）[60534841]

（718363641）[534860]

（71836364148）[5360]

（7183636414853）[60]

（718363641485360）

9．已知数据序列{10，1，15，18，7，15}，试画出采用快速排序法，第一趟排序的结果。

解

1011518715

lowhigh

交换

711518[10]15

lowhigh

交换

第一趟排序结果：

71[10]181515

lowhigh

10．已知数据序列{10，1，15，18，7，15}，试写出采用快速排序法，第一趟排序的结果。

解：

7110181515

五．二分插入排序程序填空

voidBInsSort（）//按递增序对R[1]~R[n]进行二分插入排序

{inti,j,low,high,m;

for（i=2;i<=n;i++）

{R[0]=R[i];//设定R[0]为监视哨

low=1;

high=n；

while（low<=high）

{m=（low+high）/2;

if（R[0]

high=m-1;

else

low=m+1;

}

for（j=i-1;j>=high+1;j--）

R[j+1]=R[j];//元素后移

R[high]=R[0];//插入

}

}

六．算法题

1．以单链表为存储结构，写一个直接选择排序算法。

解：

voidselectsort（pointerh）

{pointerp,q,r,s,t;

t=NULL;

while（h）

{p=h;q=NULL;

s=h;r=NULL;

while（p）

{if（p->keykey）

{s=p;p=q;}

if（s==h）

h=h->link;

else

h=s;

s->link=t;

t=s;

}

h=t;

}

}

2．以单链表作为存储结构实现直接插入排序算法。

解：

voidInsertList（Listhead）

{Lnode*p,*pprev,q,*qprev,*current;

if（!

head）

return;

pprev=head;

p=head->next;

while（p）

{q=head;

qprev=NULL;

while（q->keykey）//查找插入位置

{qprev=q;q=q->next;}

if（q==p）//p最大，无须插入

{pprev=p;p=p->next;}

else

{current=p;p=p->next;

pprev->next=p;

current->next=q;

if（q==head）//插在表头

head=current;

else//插在中间某个位置上

qprev->next=current;

}

}

}

3．设计一个算法，使得在尽可能少的时间内重排数组，将所有取负值的关键字放在所有取非负值的关键字之前。

解：

voidpart（inta[]）

{i=1;j=n;//初、终下标

while（i

{while（i=0）//自右向左找非负数

j--;

while（i

i++;

if（i

{t=a[i];

a[i]=a[j];

a[j]=t;

i++;

j--;

}

}

}

4．

设已排序的文件用单链表表示，再插入一个新记录，仍然按关键字从小到大的次序排序，试写出该算法。

voidinsert（lklisthead;datatypex）

{

s=new（node）;

s->key=x;

s->next=NULL;

if（head==NULL）

head=s;

else

{p=head;

q=NULL;

while（（p!

=NULL）&&（s->key>p->key））

{q=p;p=p->next;}

if（q==NULL）

{s->next=head;head=s;}

else

{if（p==NULL）

q->next=s;

else

{s->next=q->next;q->next=s;}

}

}

}

排序过程分析

1．已知数据序列{50，60，40，20，80，15，10，45}，试画出采用快速排序法，第一趟排序的结果。

解：

[45，10，40，20，15]50[80，60]

2．已知数据序列{82，40，66，13，84，36，96，57，39，80，61，14}，写出二路归并排序的每一趟排序结果。

解：

[82][40][66][13][84][36][96][57][39][80][61][14]

[4082][1366][3684][5796][3980][1461]第一趟排序结果

[13406682][36578496][14396180]第二趟排序结果

[1336405766828496][14396180]第三趟排序结果

[131436394057616680828496]第四趟排序结果

3．已知数据序列{40，63，11，84，35，93，58，39，15}，写出采用简单选择排序的每一趟排序结果。

解：

[406311843593583915]

（11）[6340843593583915]

（1115）[40843593583963]

（111535）[844093583963]

（11153539）[4093588463]

（1115353940）[93588463]

（111535394058）[938463]

（11153539405863）[8493]

（1115353940586384）[93]

（111535394058638493）

4．已知数据序列{18，17，60，40，07，32，73，65}，写出采用冒泡排序法每一趟排序的结果。

解：

1817604007327365

第一趟结束时结果：

1718400732606573

第二趟结束时结果：

17180732406065

第三趟结束时结果：

170718324060

第四趟结束时结果：

0717183240

第五趟结束时结果：

07171832

已无交换，结束。

5．已知数据序列{10，18，14，13，16，12，11，9，15，08}，写出希尔排序每一趟排序的结果（设d=5、2、1）。

解：

10181413161211091508

d=5

10110913081218141516

d=2

08110912101315141816

d=108091011121314151618

6．已知数据序列{39，28，55，80，75，06，17，45}，写出采用直接插入算法排序时，每一趟排序的结果。

解：

3928558075061745

第一趟结束时结果：

[2839]558075061745

第二趟结束时结果：

[283955]8075061745

第三趟结束时结果：

[28395580]07327365

第四趟结束时结果：

[0728395580]327365

第五趟结束时结果：

[072832395580]7365

第六趟结束时结果：

[07283239557380]65

第七趟结束时结果：

[0728323955657380]

程序填空

1．设表的长度为L，试填空完成直接插入排序程序。

voidinsertsort（intR[]）//按递增序对R[1]~R[n]进行直接插入排序

{inti,j;

for（i=2;i<=L;i++）

{R[0]=R[i];//设定R[0]为监视哨

j=i-1；

while（R[0]

{R[j+1]=R[j];

j--;

}

R[j+1]=R[0];//插入第i个记录

}

}

2．直接选择排序

voidselectsort（）//按递增序对R[1]~R[n]进行直接选择排序

{inti,j,k;

for（i=1;i<=n;i++）

{k=i;

for（j=i+1;j<=n;j++）//选择选择关键字最小的记录

if（R[j]

k=j;

if（!

k=j）

{R[0]=R[i];//交换关键字

R[i]=R[k];

R[k]=R[0];

}

}

}

3．二分插入排序

voidBInsSort（）//按递增序对R[1]~R[n]进行二分插入排序

{inti,j,low,high,m;

for（i=2;i<=n;i++）

{R[0]=R[i];//设定R[0]为监视哨

low=1;

high=n；

while（low<=high）

{m=（low+high）/2;

if（R[0]

high=m-1;

else

low=m+1;

}

for（j=i-1;j>=high+1;j--）

R[j+1]=R[j];//元素后移

R[high]=R[0];//插入

}

}

算法设计题

1．设计一个函数修改冒泡排序过程以实现双向冒泡排序（每一趟排序，通过相邻的关键字比较，产生最小和最大的两个元素）。

解：

voiddbubble（SeqListr）

{inti,j,t,b;

while（b）

{b=0;

for（j=n-i+1;j>=i+1;j--）//由底向上

if（r[j].key

{b=1;

t=r[j];

r[j]=r[j-1];

r[j-1]=t;

}

for（j=i+1;j

if（r[j].key>r[j+1].key）

{b=1;

t=r[j];

r[j]=r[j+1];

r[j+1]=t;

}

i++;

}

}

2．以单链表为存储结构，写一个直接选择排序算法。

解：

voidselectsort（pointerh）

{pointerp,q,r,s,t;

t=NULL;

w