数据结构（c语言版）（第2版双色版）-习题答案

更新时间：试题数量：购买人数：提供作者：

有效期：个月

章节介绍：共有个章节

收藏

我的练习

我的错题
(0道)

我的收藏
(0道)

我的斩题
(0道)

我的笔记
(0道)

专项练习

顺序练习 练习进度 0 / 0

随机练习 自定义设置练习量

模拟考试 仿真模拟

题型练习 按题型分类练习

易错题 精选高频易错题

学习资料 考试学习相关信息

搜索

题库预览

对输入文件（101，51，19，61，3，71，31，17，19，100，55，20，9，30，50，6，90）：当k=6时，使用置换-选择算法，写出建立的初始败者树及生成的初始归并段。（含图）

试以单链表为存储结构，实现简单选择排序算法。 [算法描述]： void LinkeedListSelectSort(LinkedList head) //本算法一趟找出一个关键字最小的结点，其数据和当前结点进行交换;若要交换指针，则须记下 //当前结点和最小结点的前驱指针 p=head->next; while(p!=null) {q=p->next; r=p; //设r是指向关键字最小的结点的指针 while (q!=null) {if(q->data<r->data) r=q; q:=q->next; } if(r!=p) r->data<->p->data; p=p->next; }

有n个记录存储在带头结点的双向链表中，现用双向冒泡排序法对其按上升序进行排序，请写出这种排序的算法。（注：双向冒泡排序即相邻两趟排序向相反方向冒泡）。 [算法描述]： typedef struct node { ElemType data; struct node *prior,*next; }node, *DLinkedList; void TwoWayBubbleSort(DLinkedList la) //对存储在带头结点的双向链表la中的元素进行双向起泡排序。 {int exchange=1; //设标记 DLinkedList p,temp,tail; head=la //双向链表头，算法过程中是向下起泡的开始结点 tail=null; //双向链表尾，算法过程中是向上起泡的开始结点 while (exchange) {p=head->next; //p是工作指针，指向当前结点 exchange=0; //假定本趟无交换 while (p->next!=tail) // 向下（右）起泡，一趟有一最大元素沉底 if (p->data>p->next->data) //交换两结点指针，涉及6条链 {temp=p->next; exchange=1;//有交换 p->next=temp->next;temp->next->prior=p //先将结点从链表上摘下 temp->next=p; p->prior->next=temp; //将temp插到p结点前 temp->prior=p->prior; p->prior=temp; } else p=p->next; //无交换，指针后移 tail=p; //准备向上起泡 p=tail->prior; while (exchange && p->prior!=head) //向上（左）起泡，一趟有一最小元素冒出 if (p->data<p->prior->data) //交换两结点指针，涉及6条链 {temp=p->prior; exchange=1; //有交换 p->prior=temp->prior;temp->prior->next=p; //先将temp结点从链表上摘下 temp->prior=p; p->next->prior=temp; //将temp插到p结点后（右） temp->next=p->next; p->next=temp; } else p=p->prior; //无交换，指针前移 head=p; //准备向下起泡 }// while (exchange) }//算法结束

设有顺序放置的n个桶，每个桶中装有一粒砾石，每粒砾石的颜色是红，白，蓝之一。要求重新安排这些砾石，使得所有红色砾石在前，所有白色砾石居中，所有蓝色砾石居后，重新安排时对每粒砾石的颜色只能看一次，并且只允许交换操作来调整砾石的位置。 [题目分析]利用快速排序思想解决。由于要求“对每粒砾石的颜色只能看一次”，设3个指针i，j和k，分别指向红色、白色砾石的后一位置和待处理的当前元素。从k=n开始，从右向左搜索，若该元素是兰色，则元素不动，指针左移（即k-1）；若当前元素是红色砾石，分i>j（这时尚没有白色砾石）和i<k两种情况。前一情况执行第i个元素和第k个元素交换，之后i+1；后一情况，i所指的元素已处理过（白色），j所指的元素尚未处理，应先将i和j所指元素交换，再将i和k所指元素交换。对当前元素是白色砾石的情况，也可类似处理。为方便处理，将三种砾石的颜色用整数1、2和3表示。 [算法描述]： void QkSort(rectype r[],int n) { // r为含有n个元素的线性表，元素是具有红、白和兰色的砾石，用顺序存储结构存储， //本算法对其排序，使所有红色砾石在前，白色居中，兰色在最后。 int i=1,j=1,k=n,temp; while (k!=1){ while (r[k].key==3) k--; // 当前元素是兰色砾石，指针左移 if (r[k].key==1) // 当前元素是红色砾石 if (i>j) {temp=r[k];r[k]=r[i];r[i]=temp; i++;} //左侧只有红色砾石，交换r[k]和r[i] else {temp=r[j];r[j]=r[i];r[i]=temp; j++;} //左侧已有红色和白色砾石，先交换白色砾石到位 temp=r[k];r[k]=r[i];r[i]=temp; i++; //白色砾石（i所指）和待定砾石（j所指） } //再交换r[k]和r[i]，使红色砾石入位。 if (r[k].key==2) if (i<=j) { temp=r[k];r[k]=r[j];r[j]=temp; j++;} // 左侧已有白色砾石，交换r[k]和r[j] else { temp=r[k];r[k]=r[i];r[i]=temp; j=i+1;} //i、j分别指向红、白色砾石的后一位置 }//while if (r[k]==2) j++; // 处理最后一粒砾石 else if (r[k]==1) { temp=r[j];r[j]=r[i];r[i]=temp; i++; j++; }

设有顺序放置的n个桶，每个桶中装有一粒砾石，每粒砾石的颜色是红，白，蓝之一。要求重新安排这些砾石，使得所有红色砾石在前，所有白色砾石居中，所有蓝色砾石居后，重新安排时对每粒砾石的颜色只能看一次，并且只允许交换操作来调整砾石的位置。

编写算法，对n个关键字取整数值的记录序列进行整理，以使所有关键字为负值的记录排在关键字为非负值的记录之前，要求： ① 采用顺序存储结构，至多使用一个记录的辅助存储空间； ② 算法的时间复杂度为O(n)。

借助于快速排序的算法思想，在一组无序的记录中查找给定关键字值等于key的记录。设此组记录存放于数组r[1..n]中。若查找成功，则输出该记录在r数组中的位置及其值，否则显示“not find”信息。请简要说明算法思想并编写算法。

有一种简单的排序算法，叫做计数排序。这种排序算法对一个待排序的表进行排序，并将排序结果存放到另一个新的表中。必须注意的是，表中所有待排序的关键字互不相同，计数排序算法针对表中的每个记录，扫描待排序的表一趟，统计表中有多少个记录的关键字比该记录的关键字小。假设针对某一个记录，统计出的计数值为c，那么，这个记录在新的有序表中的合适的存放位置即为c。 ① 给出适用于计数排序的顺序表定义； ② 编写实现计数排序的算法； ③ 对于有n个记录的表，关键字比较次数是多少？ ④ 与简单选择排序相比较，这种方法是否更好？为什么？