d0c194b8a60baae657c6cc1308ead715_在线真题试卷与模拟练习_d0c194b8a60baae657c6cc1308ead715_考试宝

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

有效期：个月

章节介绍：共有个章节

收藏

我的练习

我的错题
(0道)

我的收藏
(0道)

我的斩题
(0道)

我的笔记
(0道)

专项练习

顺序练习 0 / 0

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

题型乱序 按导入顺序练习

模拟考试 仿真模拟

题型练习 按题型分类练习

易错题 精选高频易错题

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

搜索

题库预览

堆的形状是一棵（）。

若一组记录的排序码为（46,79,56,38,40,84），则利用堆排序的方法建立的初始堆为（）。

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

下述几种排序方法中，（）是稳定的排序方法。

数据表中有10000个元素，如果仅要求求出其中最大的10个元素，则采用( )算法最节省时间。

下列排序算法中，（）不能保证每趟排序至少能将一个元素放到其最终的位置上。

设待排序的关键字序列为[12，2，16，30，28，10，16*，20，6，18]，试分别写出使用以下排序方法，每趟排序结束后关键字序列的状态。① 直接插入排序② 折半插入排序③ 希尔排序（增量选取5，3，1）④ 冒泡排序⑤ 快速排序⑥ 简单选择排序⑦ 堆排序⑧ 二路归并排序

给出如下关键字序列〔321，156，57，46，28，7，331，33，34，63〕，试按链式基数排序方法，列出每一趟分配和收集的过程。

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

试以单链表为存储结构，实现简单选择排序算法。 [算法描述:] void LinkedListSelectSort(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 { ElementType 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<j两种情况。前一情况执行第1个元素和第k个元素交换，之后i++；后一情况，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>=j){ while (k>=j && 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++; //再交换r[k]和r[i]，使红色砾石入位。 } if (r[k].key==2) if (i<=j) { temp=r[k];r[k]=r[j];r[j]=temp; j++;} else { temp=r[k];r[k]=r[j];r[j]=temp; j++;} //i、j分别指向红、白色砾石的后一位置 }//while if (r[k].key==2) j++; //*处理最后一粒砾石 else if (r[k].key==1) { temp=r[i];r[i]=r[k];r[k]=temp; i++; j++;} //最后红、白、兰色砾石的个数分别为: i-1;j-i;n-j+1 }//结束QkSort算法 [算法讨论]若将j（上面指向白色）看作工作指针，将r[1..j-1]作为红色，r[j..k-1]为白色，r[k..n]为兰色。从j=1开始查看，若r[j]为白色，则j++; 若r[j]为红色，则交换r[j]与r[i]，且j=j+1，i=i+1; 若r[j]为兰色，则交换r[j]与r[k];k=k-1。算法进行到j<=k为止。算法片段如下： int i=1,j=1,k=n; while(j<=k) if (r[j].key==1) //当前元素是红色 {temp=r[i]; r[i]=r[j]; r[j]=temp; i++;j++;} else if (r[j].key==2) j++; //当前元素是白色 else //r[j].key==3 当前元素是兰色 {temp=r[j]; r[j]=r[k]; r[k]=temp; k--;} 对比两种算法，可以看出，正确选择变量（指针）的重要性。

编写算法，对n个关键字选择变量（指针）的重要性。以使所有关键字为负值的记录排在关键字为非负值的记录之前，要求：① 采用顺序存储结构，至多使用一个记录的辅助存储空间；② 算法的时间复杂度为O(n)。 [算法描述:] void process(int A[n]){ low = 0; high = n-1; while (low<high) while (low<high && A[low]<0) low++; while (low<high && A[high]>0) high++; if (low<high){ x=A[low]; A[low]=A[high]; A[high]=x; low++; high--; } return; }【缺少答案，请补充】

借助于快速排序的算法思想，在一组无序的记录中查找给定关键字值等于key的记录。设此组记录存放于数组r[1..n]中。若查找成功，则输出该记录在r数组中的位置及其值，否则显示“not find”信息。请简要说明算法思想并编写算法。 [算法描述:] int index (RecType R[], int l, h, datatype key) {int i=l,j=h; while (i<=j) {while (i<=j && R[j].key>key) j--; if (R[j].key==key) return j; while (i<=j && R[i].key<key) i++; if (R[i].key==key) return i; } cout<<"Not find"; return 0; }//index

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

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

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