给定线性序集中n个元素和一个整数k，1≤k≤n，要求找出这n个元素中第k小的元素，请设计一个最坏时间复杂度为O（n）的算法，并对其时间复杂度进行分析说明。
给定线性序集中n个元素和一个整数k，1≤k≤n，要求找出这n个元素中第k小的元素，请设计一个最坏时间复杂度为O（n）的算法，并对其时间复杂度进行分析说明。
相关考题：
若一个栈初始为空,其输入序列是1,2,3,…,n－1,n,其输出序列的第一个元素为k(1≤k≤「n／2」),则输出序列的最后一个元素是()。 A.值为n的元素B.值为1的元素C.值为n-k的元素D.不确定的
假设把整数关键码K散列到有N个槽的散列表，以下哪些散列函数是好的散列函数()A.h(K)=KmodNB.h(K)=1C.h(K)=K/ND.h(K)=(K+rand(N))modN,rand(N)返回一个0到N-1的整数
下列给定程序中，函数fun()的功能是：找出一个大于给定整数m且紧随m的素数，并作为函数值返回。请改正程序中的错误，使它能得出正确的结果。注意：不要改动main函数，不得增行或删行，也不得更改程序的结构．试题程序：include ＜conio.h＞include ＜stdio.h＞int fun( int m){ int i,k;for (i=m+1; ;i++){ for (k=2;k＜i;k++)/*************found**************/if (i%k!=0)break;/*************found**************/if (k＜i)return(i);}}main(){ int n;clrscr ();printf("\nPlease enter n: ");scanf ("%d", n);printf ("%d\n",fun(n));}
阅读下列说明和流程图，将应填入(n)处的语句写在对应栏内。【说明】下列流程图用于从数组K中找出一切满足：K(I)+K(J)=M的元素对(K(I)，K(J))(1≤I≤J≤N)。假定数组K中的N个不同的整数已按从小到大的顺序排列，M是给定的常数。【流程图】此流程图1中，比较“K(I)+K(J):M”最少执行次数约为(5)。
假设有一维数组T[O...m*n-1]，其中m＞n。从数组T的第一个元素(T[0])开始，每隔n个元素取出一个元素依次存入数组B[1...m)中，即B[1]=T[0]，B[2]=T[n]，依此类推，那么放入B[k](1≤k≤n)的元素是(120)。A．T[(K-1)*m]B．T[K*n)C．T[(K-1)*n]D．T[K*m]
已知数组a中有n个元素，下列语句将数组a中从下标x1开始的k个元素移动到从下标x2开始的k个元素中，其中O＜=xl＜x2＜n，x2+k＜n，请将下列语句补充完整。For(int i=x1+k-1；i＞=x1；i--)a[______]=a[i]；
阅读以下函数说明和C语言函数，将应填入(n)处的字句写在对应栏内。[说明]这是一个求解Josephus问题的函数。用整数序列1，2，3…，n表示顺序围坐在圆桌周围的人，并采用数组表示作为求解过程中使用的数据结构。Josephus问题描述，设n个人围坐在一个圆桌周围，现在从第s个人开始报数，数到第m个人，让他出局；然后从出局的下一个人重新开始报数，数到第m个人，再让他出局，…如此反复直到所有的人全部出局为止。[C函数]void Josephus(int A[],int n,s,m)(int i,j,k,temp;if(m==O){printf("m=0是无效的参数!\n");return;}for(i=0;i＜n;i++) A[i]=i+1; /*初始化，执行n次*/i= (1) /*报名起始位置*/for(k=n;k＞1;k-){if((2)) i=0;i=(3) /*寻找出局位置*/if(i!=k-1){tmp=A[i];for(j=i;J＜k-1;j++) (4);(5);}}for(k=0;k＜n/2;k++){tmp=A[k];A[k]=A[n-k+1];A[n-k+1]=tmp;}}
设线性表中有2n个元素，算法( )，在单链表上实现要比在顺序表上实现效率更高。A．删除所有值为x的元素B．在最后一个匀速的后面插入一个新元素C．顺序输出前k个元素D．交换第i个元素和第2n-i-1个元素的值(i=0，1，…，n-1)
●设有二维数组a[1..m,1..n](2mn），其第一个元素为a[1,1]，最后一个元素为a[m,n]，若数组元素以行为主序存放，每个元素占用k个存储单元(k1)，则元素a[2,2]的存储位置相对于数组空间首地址的偏移量为(35)。A.(n+1)*kB.n*k+lC.(m+1)*kD.m*k+l
已知有一维数组T[0...m*n-1]，其中m＞n。从数组T的第一个元素(T[0])开始，每隔n个元素取出一个元素依次存入数组B[1...m]中，即B[1]＝T[0]，B[2)= T[n]，依次类推，那么放入B[k](1≤k≤m)的元素是______。A．T[(k-1)*n]B．T[k*n]C．T[(k-1)*m]D．T[k*m]
若一个栈初始为空，其输入序列是1，2，3…，n-l，n．其输出序列的第一个元素为 k (l≤k≤[n/2])，则输出序列的最后一个元素是(58) 。A.值为n的元素B.值为1的元素C.值为n-k的元素D.不确定的
●试题一阅读下列说明和流程图，将应填入(n)处的语句写在答题纸的对应栏内。【说明】下列流程图用于从数组K中找出一切满足：K(I)+K(J)=M的元素对(K(I)，K(J))(1≤I≤J≤N)。假定数组K中的N个不同的整数已按从小到大的顺序排列，M是给定的常数。【流程图】此流程图1中，比较"K(I)+K(J)∶M"最少执行次数约为 (5) 。图1
阅读以下函数说明和C语言函数，将应填入(n)处的字句写在对应栏内。[说明]函数int psort(int a[],int n)实现将含n个整数的数组a[]的不同元素按从小到大顺序存于数组a[]中。实现方法是从未确定的元素列中找到最小元素并将a[]的第i最小元素交换至a[i]位置。如该最小元素比已确定的最后一个最小元素大，则将它接在已确定的元素序列的后面；否则，忽视该元素。[C函数]int psort(int a[],int n){int i,J,k,P;for(i=0,k=0;i＜(1);i++){for(j=i+1, (2) ;j＜n; j++)if(a[p]＞a[j])p=j;if(p!=i){t=a[p];a[p]=a[i];a[i]=t;}if( (3) ) k++;else if( (4) ＜a[i])(5)=a[i];}return k;}int a[]={5,7,5,6,4,3,4,6,7};main(){int k,n;for(k=0;k＜(Sizeof a)/Sizeof(int);k++)printf("%5d",a[k]);printf ("\n\n");n=psort(a,(sizeof(a))/sizeof(int));for(k=0;k＜n;k++)printf("%5d",a[k]);printf("\n\n");}
阅读以下说明和C语言函数，将解答填入对应栏内。【说明】下面待修改的C程序完成的功能是：对于给定的一个长正整数，从其个位数开始，每隔一位取一个数字(即取其个位、百位、万位等数字)，形成一个新的整数并输出。例如，将该程序修改正确后，运行时若输入“14251382”，则输出的整数为“4532”。下面给出的C程序代码中有五个错误，请指出所有的错误。【C程序代码】01 include ＜stdio.h＞0203 int main()04 {05 long n, num;06 int i;0708 do {09 printf("请输入一个正整数：");10 scanf("%ld", n);11 }while(n ＜= 0);12 k = 1;13 for (i = 1; n ＞= 0; i++) {14 if (i % 2 = 1) {15 num= num+ (n % 10) * k;16 k = k * 10;17 }18 n = n / 10;19 }20 printf("新数据为: %d \n",num);21 return 0;22 }
下面是一个对整数数组A中的前n个元素求最小值的C程序，函数返回最小元素的位置。 Int minValue(int A[]，int n){ int k=0： for(int j=1；j＜=n-1；j++) if(A[j]＜a[k])k=j； return k： 当n=4时，程序中可能的执行路径数为______。A．2B．4C．8D．16
以下子例行程序用于实现向一维数组下标为P的数组元素处插入一个整数X SUBROUTINE INSERT(B,N,P,X) INTEGER B(N),X,P DO 20 K=N-1,P,-1 B(K+1)=______ 20 CONTINUE B(P)=X END 为使程序完整，应在______处放入( )。A.XB.KC.B.(P)D.B.(K)
若一个栈初始为空，其输入序列是1，2，3，…，n-1，n，其输出序列的第一个元素为k（1≤k≤「n/2」），则输出序列的最后一个元素是（）。A、值为n的元素B、值为1的元素C、值为n-k的元素D、不确定的
在搜索解图的过程中，若解图的耗散值记为k（n，N），则若n是一个外向连接符指向后继节点{n1，…，ni}，并设该连接符的耗散值为Cn，则k（n，N）＝（）A、CnB、k（n1，N）+…+k（ni，N）C、0D、Cn+k（n1，N）+…+k（ni，N）
单选题将一个正整数n表示成一系列正整数之和，n=n1+n2+…+nk（其中，n1≥n2≥…≥nk≥1，k≥1）正整数n的一个这种表示称为正整数n的一个划分。正整数n的不同的划分个数总和称为正整数n的划分数，记作p（n）；另外，在正整数n的所有不同划分中，将最大加数n1不大于m的划分个数记作q（n，m）。则当n=10时，p（n）=（）。Aq（8，8）B1+q（9，9）C2+q（10，8）DABC都正确
单选题下列说法不正确的是（ ）。As个n维向量α(→)1，α(→)2，…，α(→)s线性无关，则加入k个n维向量β(→)1，β(→)2，…，β(→)k后的向量组仍然线性无关Bs个n维向量α(→)1，α(→)2，…，α(→)s线性无关，则每个向量增加k维分量后得到的向量组仍然线性无关Cs个n维向量α(→)1，α(→)2，…，α(→)s线性相关，则加入k个n维向量β(→)1，β(→)2，…，β(→)k后得到的向量组仍然线性相关Ds个n维向量α(→)1，α(→)2，…，α(→)s线性无关，则减少一个向量后得到的向量组仍然线性无关
单选题在搜索解图的过程中，若解图的耗散值记为k（n，N），则若n是N的一个元素，则k（n，N）＝（）AnBNCN-nD0