[数据结构与算法]数据结构第二次上机题

1.逻辑结构与时间复杂度基础知识

2-1 关于逻辑结构
数据结构可以从逻辑上分成 ▁▁C▁▁▁ 两大类。
(5分)
A.动态结构和静态结构
B.紧凑结构和非紧凑结构
C.线性结构和非线性结构
D.内部结构和外部结构
2-2 数据逻辑结构可以分为（B ）。
A.线性结构和图结构
B.集合结构、线性结构、树结构和图结构
C.顺序结构和链式结构
D.集合结构和非线性结构
2-3 算法分析的两个主要方面是（　A　）。
(5分)
A.空间复杂度和时间复杂度
B.正确性和简明性
C.可读性和文档性
D.数据复杂性和程序复杂性
2-4 算法设计的要求设计一个好的算法应该满足正确性、▁▁▁B▁▁、健壮性和高效性等要求。
A.稳定性
B.可读性
C.可靠性
D.可行性
2-5 算法的特性一个算法必须满足有限性、确定性、▁▁▁C▁▁、输入和输出等五个重要特性。
A.高效性
B.稳定性
C.可行性
D.可读性
2-6 执行下面程序段时，执行S语句的频度为（D）。

for(int i=0;i<n;i++)
for(int j=1;j<=i;j++)
     S;

A.n2
B.n2/2
C.n(n+1)
D.n(n+1)/2
2-7 下列程序段的时间复杂度为（B）。

x = n;     /*n > 1*/
y = 0;
while(x >= (y + 1) * (y + 1))
     y = y + 1;

A.Θ(n)
B.Θ(n?)
C.Θ(1)
D.Θ(n2)
2-8 时间复杂度分析
下面算法的时间复杂度为 ▁▁▁▁▁。

int foo(int n)
{
    int i, s = 0;
    for (i = 1; i * i <= n; ++i)
    {
        s += i;
    }
    return s;
}

A.O(n2)
B.O(n)
C.O(n?)
D.O(log2?n)
2-9 时间复杂度分析
下面算法的时间复杂度为 ▁▁D▁▁▁。

int foo(int n)
{
    int i, j, s = 0;
    for (i = 1; i <= n; ++i)
    {
        for (j = 1; j <= i; ++j)
        {
            s += i * j;
        }
    }
    return s;
}

A.O(n⁽ⁿ(1/2))?)
B.O(n)
C.O(nlog2?n)
D.O(n2)
2-10
时间复杂度分析
下面算法的时间复杂度为 ▁▁O(n)▁▁▁。

int foo(int n)
{
    int i, m = n / 2, s = 0;
    for (i = 1; i <= m; ++i)
    {
        s += i;
    }
    return s;
}

2-11

时间复杂度分析

下面算法的时间复杂度为 ▁▁O(n)▁▁▁。

int foo(int n)
{
    int i, s = 0;
    for (i = 1; i <= n; ++i)
    {
        s += i;
    }
    return s;
}

2-12

时间复杂度分析

下面算法的时间复杂度为 ▁▁▁▁▁。

int foo(int n)
{
    return n * (n + 1) / 2;
}

2.数组中按值找元素 (20 分)

在数组A[1…N]中查找值为k的元素，若找到输出其位置i(1<=i<=n)，否则输出0作为标志。
函数接口定义：

Search(int a[],int n,int k);

其中 a 、 n、k 都是用户传入的参数。a 为数组名，期中存了n个整数，下标为1到n；k 为待查数据元素；若找到了，返回其下标；否则，返回0。
裁判测试程序样例：

#include <stdio.h>
Search(int a[],int n,int k);
main()
{
    int a[50],n,i,k;
    scanf("%d",&n);  //接收数组元素个数
    for(i=1;i<=n;i++)   //依次接收各个元素的值
        scanf("%d",&a[i]);
    scanf("%d",&k);      // 接收待查元素值k
    int x=Search(a,n,k);  
    if(x==0)
        printf("NONE\n");
    else
        printf("%d\n",x);

}

/* 请在这里填写答案 */

输入样例1：

5
67 48 90 34 25
34
结尾无空行

输出样例1：

4
结尾无空行

输入样例2：

6
45 67 89 9 7 5 56
34
结尾无空行

输出样例2：

NONE
结尾无空行

int Search(int a[],int n,int k)
{
	int i;
	int t=0;
	if(n==0)            //数组不存在时
	return 0;
	else
	{
		for(i=1;i<=n;i++)
		{
			if(a[i]==k)
			{
				return i;
			
			}
			else if(i==n)       //数字不在数组中
				return 0;
		}
	}
}

3. 找最大值和次大值 (20 分)

找出数组A[1…N]中最大值和次大值。（数组中元素个数大于两个且值各不相同）
函数接口定义：

void FindMax(int a[],int n,int *pmax1,int *pmax2);

其中 a 和 n 是用户传入的参数。 a为数组名， n为数组中元素的个数，在下标从1到n处存放。利用指针变量 pmax1和pmax2带出运算结果。 pmax1为指向最大值的指针；pmax2为指向次大值的指针。
裁判测试程序样例：

#include <stdio.h>
void FindMax(int a[],int n,int *pmax1,int *pmax2);
main()
{
    int a[50],n,i;
    int max1,max2;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%d",&a[i]);
    FindMax(a,n,&max1,&max2);
    printf("%d %d\n",max1,max2);
}
/* 请在这里填写答案 */

输入样例：

5
32 45 57 8754 33
结尾无空行

输出样例：

8754 57
结尾无空行

void FindMax(int a[],int n,int *pmax1,int *pmax2){
 int i,j=1,k,t;
 for(i=1;i<=n;i++){
  for(j=i+1;j<=n;j++){
   if(a[i]<a[j]){
    t=a[i];a[i]=a[j];a[j]=t;//冒泡排序，取前两位
   }
  }
 }
 *pmax1=a[1];
 *pmax2=a[2];
 return 0;
}