给定线性序集中n个元素和一个整数k,1≤k≤n,要求找出这n个元素中第k小的元素,请设计一个最坏时间复杂度为O(n)的算法,并对其时间复杂度进行分析说明。
第1题:
假设有一维数组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]
第2题:
阅读以下函数说明和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;
}
}
第3题:
设线性表中有2n个元素,算法( ),在单链表上实现要比在顺序表上实现效率更高。
A.删除所有值为x的元素
B.在最后一个匀速的后面插入一个新元素
C.顺序输出前k个元素
D.交换第i个元素和第2n-i-1个元素的值(i=0,1,…,n-1)
第4题:
已知有一维数组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]
第5题:
●试题一
阅读下列说明和流程图,将应填入(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
第6题:
阅读以下说明和C语言函数,将解答填入对应栏内。
【说明】
下面待修改的C程序完成的功能是:对于给定的一个长正整数,从其个位数开始,每隔一位取一个数字(即取其个位、百位、万位等数字),形成一个新的整数并输出。例如,将该程序修改正确后,运行时若输入“14251382”,则输出的整数为“4532”。
下面给出的C程序代码中有五个错误,请指出所有的错误。
【C程序代码】
01 include <stdio.h>
02
03 int main()
04 {
05 long n, num;
06 int i;
07
08 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 }
第7题:
第8题:
第9题:
元素周期表中各种元素的谱线是有规律排列的,并以K,L,M,N…表示若干谱系,对于一个给定的元素,各谱系的能量是:K<L<M<N…
第10题:
在搜索解图的过程中,若解图的耗散值记为k(n,N),则若n是N的一个元素,则k(n,N)=()
第11题:
s个n维向量α1,α2,…,αs线性无关,则加入k个n维向量β1,β2,…,βk后的向量组仍然线性无关
s个n维向量α1,α2,…,αs线性无关,则每个向量增加k维分量后得到的向量组仍然线性无关
s个n维向量α1,α2,…,αs线性相关,则加入k个n维向量β1,β2,…,βk后得到的向量组仍然线性相关
s个n维向量α1,α2,…,αs线性无关,则减少一个向量后得到的向量组仍然线性无关
第12题:
n
N
N-n
0
第13题:
已知数组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];
第14题:
给定一个有n个元素的线性表。若采用顺序存储结构,则在等概率前提下,向其插入一个元素需要移动的元素个数平均为(43)。
A.n+1
B.n/2
C.
D.
第15题:
●设有二维数组a[1..m,1..n](2<m<n),其第一个元素为a[1,1],最后一个元素为a[m,n],若数组元素以行为主序存放,每个元素占用k个存储单元(k>1),则元素a[2,2]的存储位置相对于数组空间首地址的偏移量为(35)。
A.(n+1)*k
B.n*k+l
C.(m+1)*k
D.m*k+l
第16题:
若一个栈初始为空,其输入序列是1,2,3…,n-l,n.其输出序列的第一个元素为 k (l≤k≤[n/2]),则输出序列的最后一个元素是(58) 。
A.值为n的元素
B.值为1的元素
C.值为n-k的元素
D.不确定的
第17题:
阅读以下函数说明和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");
}
第18题:
下面是一个对整数数组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.2
B.4
C.8
D.16
第19题:
第20题:
若一个栈初始为空,其输入序列是1,2,3,…,n-1,n,其输出序列的第一个元素为k(1≤k≤「n/2」),则输出序列的最后一个元素是()。
第21题:
在搜索解图的过程中,若解图的耗散值记为k(n,N),则若n是一个外向连接符指向后继节点{n1,…,ni},并设该连接符的耗散值为Cn,则k(n,N)=()
第22题:
q(8,8)
1+q(9,9)
2+q(10,8)
ABC都正确
第23题: