违法和不良信息举报 联系客服
免费注册 登录

若对n个元素进行直接插入排序，在进行第i趟排序时，假定元素r[i

题目

若对n个元素进行直接插入排序，在进行第i趟排序时，假定元素r[i+1]的插入位置为r[j]，则需要移动的元素的次数为（）

  • A、 j-i
  • B、 i-1
  • C、 i-j-1
  • D、 i-j+1
如果没有搜索结果或未解决您的问题，请直接 联系老师 获取答案。
相似问题和答案

第1题：

设有一个长度为n的顺序表,要在第i个元素之前(也就是插入元素作为新表的第i个元素),插入一个元素,则移动元素个数为()。

A.n-i+1

B.n-i-1

C.n-i

D.i


参考答案：A

第2题：

若长度为n的线性表采用顺序存储结构，那么在第i个位置插入一个元素，需要依次向后移动 ______个元素。

A．n-i

B． n-i+1

C． n-i-1

D． i


正确答案：B
解析： 在采用顺序结构存储的线性表的第i个位置插入新元素，则要将第i个元素以后的元素向后移动(包括第i个元素) ，所以共有n-i+1个元素后移。

第3题：

● 对具有n个元素的顺序表（采用顺序存储的线性表）进行 （40） 操作，其耗时与n的大小无关。

（40）A．在第i（1≤i≤n）个元素之后插入一个新元素

B．删除第i（1≤i≤n）个元素

C．对顺序表中的元素进行排序

D．访问第i（1≤i≤n）个元素的前驱和后继


试题（40）分析

本题考查数据结构基础知识。
线性表的逻辑关系特点是元素依序排列。当采用顺序存储方式时（一维数组存储），可以随机访问其中的任何一个元素。在表中插入元素和删除元素都要移动其他元素，所需移动的元素个数大约为n/2，而排序所需时间更是与表中元素个数n相关。

参考答案（40）D

第4题：

在对n个关键字进行直接选择排序的过程中，每一趟都要从无序区选出最小关键字元素，则在进行第i趟排序之前，无序区中关键字元素的个数为 ( )

A．i

B．i+1

C．n-i

D．n-i+1


正确答案：D

第5题：

若对n个元素进行直接插入排序，则进行第i趟排序过程前，有序表中的元素个数为______。

A．1

B．11

C．i

D．i+l


正确答案：C

第6题：

若对n个元素进行直接插入排序，则进行第i趟排序过程前，有序表中的元素个数为 ______。

A．1

B．i-1

C．i

D．i+1


正确答案：C

第7题：

对具有n个元素的顺序表(采用顺序存储的线性表)进行( ) 操作，其耗时与n的大小无关。

A．在第i(1≤i≤n)个元素之后插入一个新元素

B．删除第i(1≤i≤n)个元素

C．对顺序表中的元素进行排序

D．访问第i(1≤i≤n)个元素的前驱和后继


正确答案：D
解析：线性表是随机读取的，所以参看某个元素与n无关。【总结与扩展】顺序表是在计算机内存中以数组的形式保存的线性表，是指用一组地址连续的存储单元依次存储数据元素的线性结构。线性表采用顺序存储的方式存储就称之为顺序表。顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。将表中元素一个接一个地存入一组连续的存储单元中，这种存储结构是顺序结构。采用顺序存储结构的线性表简称为“顺序表”。顺序表的存储特点是：只要确定了起始位置，表中任一元素的地址都通过下列公式得到：L0c(ai)=LOC(ai)+(i-1)*L(1≤i≤n)，其中，L是元素占用存储单元的长度。

第8题：

在下列对单链表进行的操作中,算法时间复杂度为O(n)的是()。

A、访问第i个元素的前驱(1

B、在第i个元素之后插入一个新元素(1≤i≤n)

C、删除第i个元素(1≤i≤n)

D、对表中元素进行排序


参考答案：A

第9题：

含有n个元素的线性表采用顺序存储方式时，对其运算速度最快的操作是(36)。

A.访问第i个元素(l＜i≤n)

B.删除第i个元素(1≤j≤n)

C.在第i个元素(1≤i≤n)之后插入一个新元素

D.查找与特定值相匹配的元素


正确答案：A
本题考查数据结构基础知识。线性表(a1,a2,a3.......an)采用顺序存储方式如下图所示，其逻辑上相邻的元素物理位置也是相邻的，因此，按照序号访问元素的速度是很快的。访问第i个元素(1≤i≤n)的元素，仅需计算出a1的存储位置再进行内存的随机访问操作即可，以LOC(a1)表示线性表中第一个元素的存储位置，L表示每个元素所占存储单元的个数，则计算LOC(a1)的方式如下：LOC(a1)=LOC(a1)+(i-I)×L再分析其他运算，不在表尾插入或删除时就需要移动其他元素，这是比较耗时的。查找与特定值相匹配的元素时，需要经过一个与表中多个元素进行比较的过程，相对于随机访问第i个元素，消耗更多时间。

第10题：

第二题 阅读以下说明和代码，填补代码中的空缺，将解答填入答题纸的对应栏内。
【说明】
对n个元素进行简单选择排序的基本方法是：第一趟从第1个元素开始，在n个元素中选出最小者，将其交换至第一个位置，第二趟从第2个元素开始，在剩下的n-1个元素中选出最小者，将其交换至第二个位置，依此类推，第i趟从n-i+1个元素中选出最小元素，将其交换至第i个位置，通过n-1趟选择最终得到非递减排序的有序序列。 问题：2.1 【代码】
#include
void selectSort(int data[ ],int n)
//对 data[0]~data[n-1]中的n个整数按非递减有序的方式进行排列
{
int i,j,k;
int temp;
for(i=0;i for(k=i,j=i+1;（1）;（2）) //k表示data[i]~data[n-1]中最小元素的下标
if(data[j] if(k!=i) {
//将本趟找出的最小元素与data[i]交换
temp=data[i]; （4） ;data[k]=temp;
}
}
}

int main()
{
int arr[ ]={79,85,93,65,44,70,100,57};
int i,m;
m=sizeof(arr)/sizeof(int); //计算数组元素的个数，用m表示
（5）; //调用selectSort对数组arr进行非递减排序
for(（6）;i printf(“%d\t”,arr[i]);
printf(“\n”);
return 0;
}


答案：
解析：
j（2）j++
（3）k=j
（4）data[i]=data[k]
（5）selectSort(arr,m)此处m也可以填8或者sizeof(arr)/sizeof(int), arr可以改成&arr[0]
（6）i=0

【解析】

本题考查 C 程序设计基本技能及应用。简单选择排序方法是设所排序序列的记录个数为n。i取1,2,…,n-1,从所有n-i+1个记录（Ri,Ri+1,…,Rn）中找出排序码最小的记录，与第i个记录交换。执行n-1趟后就完成了记录序列的排序。
第1空应填j循环结束条件，j应该运行至序列末尾。填j第2空填j循环控制语句，j每次递增1，往后移动一个元素与a[i]进行比较。
第3空为自动保存最大元素的下标，k=j。
第4空为交换两个元素，temp为临时变量，保存data[i]的值，使用data[i]=data[k]使data[i]为后面n-i+1个记录（Ri,Ri+1,…,Rn）中找出排序码最小的记录，再将temp赋给data[k]。
第5空为调用selectSort对数组arr进行非递减排序，selectSort有两个参数，数组和排序元素个数，为selectSort(arr,m)。
第6空进行元素遍历输出所有的数组元素，从下标为0开始，所以填i=0。

更多相关问题
相关内容