【数据结构与算法】第1章绪论（头歌习题）【合集】

第1关：求和

任务描述

本关任务：给定整数n，计算sum(n)=1+2+3+…+n。

编程要求

根据提示，在右侧编辑器补充完成函数add的代码，计算并输出1+2+3+…+n的值。

测试说明
平台会对你编写的代码进行测试：

测试输入：
1
100
预期输出：
1
5050

代码

#include<stdio.h>

/**
 * 计算1+2+3+...+n的和并返回
 */
int add(int n) {
    /*****请在下面编写您的代码*****/
    int sum = 0;
    for(int i=1; i<=n; i++) {
        sum += i;
    }
    return sum;
    /*********代码编写结束*********/
}

int main()
{
    int n;
    while (scanf("%d", &n) != EOF)
    {
        int sum = add(n);
        printf("%d\n", sum);
    }
    return 0;
}

第2关：求倒数和的倒数

任务描述

本关任务：一个正整数的倒数是用阿拉伯数字写的整数，但数字的顺序是倒序的，第一位数字变为最后一位，反之亦然。例如，1245的倒数是5421，注意所有前导零均被省略，这意味着如果整数以零结尾，则零会通过反转而丢失（例如1200等于21）。另外还要注意倒数不会有任何尾随零。这里的任务是将两个倒数相加并输出其和的倒数。

编程要求

根据提示，在右侧编辑器补充代码，设计求正整数a倒数的算法reverse(a)，用函数返回值直接返回a的倒数。

输入格式
输入包含n个测试用例。第一行仅包含正整数n，每个测试用例仅由一行组成，其中有两个用空格隔开的正整数。

输出格式
对于每个测试用例，输出一行表示两个输入的正整数的倒数和的倒数，忽略任何前导零。

测试说明
平台会对你编写的代码进行测试：

输入样例
3
24 1
4358 754
305 794

输出样例
34
1998
1

样例解释
24的倒数为42， 1的倒数为1， 42+1=43，43的倒数为34。
4358的倒数为8534，754的倒数为457，8534+457=8991，8991的倒数为1998。
305的倒数为503，794的倒数为497，503+497=1000， 1000的倒数为0001。忽略前导0之后为1。

开始你的任务吧，祝你成功！

完整代码

#include<iostream>
using namespace std;

//产生正整数a的倒数并返回
int reverse(int a)
{
	//请在下面编写代码
	/*****************Begin********************/
    // 1. 以零结尾的整数 直接取非零部分，再反转
    // 2. 不以零结尾的整数 直接反转
    int b = a;
    int sum=0;
    int i=0;
    int arr[10];
    
    if(b%10==0) {  // 处理末尾第一个零
        b /= 10;
        
        if(b==0) {
            return b;
        }
          
        while(b%10==0) { // 处理末尾连续的零
            b /=10;
        }
        while(b>0) {  //倒序存入数组
            arr[i] = b%10;
            b /=10;
            i++;
        }
        arr[i] = b;
    }else{     // 处理末尾第一个不是零
        while(b>0) {  //倒序存入数组
            arr[i] = b%10;
            b /=10;
            i++;
        }
        arr[i] = b;
    }

    // 取出数组中的数
    for(int j=0; j<i; j++) {
        sum = sum*10 + arr[j];         
    }
    return sum;  
    
    /******************End********************/
}

int main()
{
    int n, a, b;
    scanf("%d", &n);
    while (n--)
    {
        scanf("%d%d", &a, &b);
        printf("%d\n", reverse(reverse(a) + reverse(b)));
    }
    return 0;
}

第3关：回文数

任务描述

本关任务：给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。
回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。例如，121 是回文，而 123 不是，-121也不是回文数。

编程要求

根据提示，在右侧编辑器补充代码，在函数bool isPalindrome(int x)中判断x是否为回文数，如果x是回文数，返回true， 否则返回false。

测试说明
平台会对你编写的代码进行测试：

测试用例1
输入：x = 121
输出：true

测试样例2
输入：x = -121
输出：false
解释：从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。

测试样例3
输入：x = 10
输出：false
解释：从右向左读, 为 01 。因此它不是一个回文数。

提示：
?2^31 <= x < 2 ^31 ?1

开始你的任务吧，祝你成功！

完整代码

#include <iostream>
using namespace std;

/**
 * 如果x为回文数，返回true，否则返回false。
 */
bool isPalindrome(int x)
{
	//请在下面编写代码
	/********************Begin********************/
    int b = x;
    int i=0;
    int j=0;
    int flag=0;
	if(x>=0) {
        int a[12];
        for(i=0; b>0; i++) {    // 先将各个位数存入数组中
            a[i] = b%10;
            b /= 10;
        }
        i = i-1;
        for(j=0; j<i; j++,i--){  // 比较相同否
            flag = 0;
            if(a[j]==a[i]) {
                flag = 1;
                continue;
            }
        }
        if(flag==1||x==0) {        // 进入if语句之后结束for退出   
            return true;
        }else if(flag==0) {  // 未进入if之后退出for
            return false;
        }
    }
    return false;
    /********************End**********************/
}


int main(int argc, char* argv[])
{
	int x;
	scanf("%d", &x);
	if (isPalindrome(x))
		printf("true\n");
	else printf("false\n");
	return 0;
}
 

第4关：求素数个数

任务描述

本关任务：编写一个程序，求[1,n]之间的素数个数。
实验目的：通过对比同一问题不同解法的绝对执行时间，体会如何设计“好”的算法。
实验内容：编写一个程序,求[1,n]的素数个数。要求采用两种解法实现函数is_prime(int n)。

编程要求

根据提示，在右侧编辑器补充代码，要求分别用两种方法实现函数is_prime(int n)。

测试说明
平台会对你编写的代码进行测试：

测试输入：10000
预期输出：
Time elapsed is: 0.001000 seconds
The number of prime is: 1229

测试输入：20001
预期输出：
Time elapsed is: 0.002000 seconds
The number of prime is: 2262

测试输入：100010
预期输出：
Time elapsed is: 0.014000 seconds
The number of prime is: 9593

开始你的任务吧，祝你成功！

完整代码

#include <stdio.h>
#include <time.h>	//clock_t, clock, CLOCKS_PER_SEC
#include <math.h>   //sqrt(n)

//如果正整数n是素数, 返回true；否则返回false
bool is_prime(int n)
{
	//请在下面编写代码
	/***************Begin**************/
    int i;
    if(n<=1) {
        return false;
    }
	if(n>=2) {
        for(i=2; i<=int(sqrt(n)); i++) {
            if(n%i==0) {
                break;
            }
        }
        if(i>int(sqrt(n))) {
            return true;        
        }else{
            return false;
        }
    }

	/****************End***************/
}
void CountPrime(int n)		//耗时统计
{
	clock_t t;
	int sum = 0, i;
	t = clock();			//算法起始时间
	for (i = 2; i <= n; i++)
		if (is_prime(i))
			sum++;
	t = clock() - t;		//算法结束时间
	//printf("Time elapsed is: %lf seconds\n" , ((double)t) / CLOCKS_PER_SEC); //换算为秒
	printf("The number of prime is: %d\n", sum);	//打印素数个数
}
//测试程序
int main()
{
	int n;
	scanf("%d", &n);
	if (n < 10000) return 0;
	CountPrime(n);
	return 0;
}
 

第5关：最大因子

任务描述

本关任务：给定一组整数，共n（1≤n≤5000）个整数，整数的取值范围为1~20000，请确定具有最大素数因子的整数（记住：素数只有因子1和它自身，例如整数7是素数，而整数6可以被2和3整除，6不是素数）。

编程要求

根据提示，在右侧编辑器补充代码，输出具有最大因子的整数。

测试说明
输入格式：
第一行为单个整数n，接下来共n个整数，每一行包含一个整数。

输出格式：
在一行中输出具有最大素数因子的那个整数，如果有多个，则输出最早出现在输入文件中的一个。

输入样例：
4
36
38
40
42

输出样例：
38

样例解释：
36的素数因子为2、3。
38的素数因子为2、19。
40的素数因子为2、5。
42的素数因子为2、3、7。
最大的素数因子为19，所以输出38。

开始你的任务吧，祝你成功！

完整代码

#include<iostream>
using namespace std;

const int N =20001;
int a[N];
int p[N];
int cnt = 0;

void init()
{
    for(int i = 0; i <= N - 1; i++)
        a[i] = 1;
        a[0] =a[1] = 0;
        for(int i=2; i <= N - 1; i++){
            if(a[i]==1){
                p[cnt++] = i;
                for(int j = i + i; j <= N - 1; j += i)
                    a[j]=0;
            }
        }
    }

int main()
{
    init();
    int n;
    cin >> n;
    int ansp=2;
    int ansn=1;
    while(n--)
    {
        int val;
        cin >> val;
        for(int j=cnt-1; j>=0; j--)
        {
            if(val%p[j]==0)
            {
                if(p[j]>ansp)
                {
                    ansp=p[j];
                    ansn=val;
                }
            }
        }
    }
    cout << ansn << endl;
    return 0;
}

第6关：数据结构基础知识

任务描述

本关任务：完成数据结构基础知识题。

1. 知识结构图
   第1章知识结构图
   

2. 基本知识点
   (1)数据的逻辑结构、存储结构和数据运算三方面的概念及相互关系。
   (2)采用抽象数据类型描述求解问题。
   (3)算法描述中的输出型参数描述方法。
   (4)算法的时间和空间复杂度分析，特别是递归算法的时间和空间复杂度分析。
   (5)如何设计“好”的算法。

3. 要点归纳
   (1)数据结构是相互之间存在一种或多种特定关系的数据元素的集合。数据是由数据元素组成的，数据元素可以由若干个数据项组成，数据元素是数据的基本单位，数据项是数据的最小单位。
   (2)数据结构一般包括数据逻辑结构、数据存储结构和数据运算3个方面。数据运算分为抽象运算(运算功能描述)和运算实现两个层次。
   (3)数据的逻辑结构分为集合、线性结构、树形结构和图形结构，树形结构和图形结构统称为非线性结构。
   (4)数据的存储结构分为顺序存储结构、链式存储结构、索引存储结构和哈希(散列)存储结构。
   (5)在设计数据的存储结构时既要存储逻辑结构的每个元素值，又要存储元素之间的逻辑关系。同一逻辑结构可以设计相对应的多个存储结构。
   (6)描述一个求解问题的抽象数据类型由数据逻辑结构和抽象运算两部分组成。
   (7)算法是对特定问题求解步骤的一种描述，它是指令的有限序列。运算实现通过算法来表示。
   (8)算法具有有穷性、确定性、可行性、输入和输出5个重要特征。
   (9)算法满足有穷性，程序不一定满足有穷性。算法可以用计算机程序来描述，但并不是说任何算法必须用程序来描述。
   (10)在用C/C++语言描述算法时，通常算法采用C/C++函数的形式来描述，复杂算法可能需要多个函数来表示。
   (11)在设计一个算法时先要弄清哪些是输入(已知条件)、哪些是输出(求解结果)，通常将输入参数设计成非引用型形参，将输出参数设计成引用型形参。在有些情况下，算法求解结果可以用函数返回值表示。
   (12)对于算法的输入通常需要判断其有效性，当输入有效并正确执行时返回true(真)，否则返回false(假)。
   (13)算法分析包括时间复杂度和空间复杂度分析，其目的是分析算法的效率以求改进，所以通常采用事前估算法，而不是进行算法绝对执行时间的比较。
   (14)在分析算法的时间复杂度时通常选取算法中的基本运算，求出其频度，取最高阶并置序数为1作为该算法的时间复杂度。
   (15)递归算法的时间复杂度分析方法是先由递归算法推导出执行时间的递推式，然后计算T(n)，再用O表示。
   (16)递归算法的空间复杂度分析方法是先由递归算法推导出占用空间的递推式，然后计算S(n)，再用O表示。
   (17)通常算法是建立在数据存储结构之上的，设计好的存储结构可以提高算法的效率。
   (18)求解问题的一般步骤是建立其抽象数据类型，针对运算的实现设计出合理的存储结构，在此基础上设计出尽可能高效的算法。

开始你的任务吧，祝你成功！

题目及答案

1、计算机所处理的数据一般具备某种内在联系，这是指 ( ) 。正确选项：B

A、
数据和数据之间存在某种关系

B、
元素和元素之间存在某种关系

C、
元素内部具有某种结构

D、
数据项和数据项之间存在某种关系

2、数据结构是具有( )的数据元素的集合。正确选项：C

A、
性质相同

B、
相同物理结构

C、
相互关系

D、
数据项

3、在数据结构中，数据的逻辑结构是指( )。正确选项：C

A、
数据类型

B、
指针类型

C、
数据元素之间的逻辑关系

D、
数据元素之间的物理关系

4、在数据结构中，以下说法中不正确的是（ ）。正确选项：D

A、
数据元素是数据的基本单位

B、
数据项是不可分割的最小可标识单位

C、
数据可由若干个数据元素构成

D、
数据项可由若干个数据元素构成

5、正确选项：C

在数据结构中从逻辑上可以把数据结构分为（ ）两类。

A、
动态结构和静态结构

B、
紧凑结构和非紧凑结构

C、
线性结构和非线性结构

D、
内部结构和外部结构

6、正确选项：C

数据结构通常采用二元组表示：B=(D,R)，其中R表示（ ）的集合。

A、
数据项

B、
数据元素

C、
数据元素关系

D、
数据类型

7、正确选项：B

数据结构通常采用二元组表示：B=(D,R)，其中D表示（ ）的集合。

A、
数据项

B、
数据元素

C、
数据元素关系

D、
数据类型

8、正确选项：A

在数据结构中，与所使用的计算机无关的是数据的 （ ）结构。

A、
逻辑

B、
存储

C、
逻辑和存储

D、
物理

9、正确选项：D

数据结构的研究内容不涉及（ ）。

A、
数据如何组织

B、
数据如何存储

C、
数据运算如何实现

D、
算法用什么语言来描述

10、数据的逻辑结构分为集合、线性结构、▁▁▁和图形结构4种基本类型。

正确答案：
填空1：树形结构

11、一个数据结构在计算机中的▁▁▁称为存储结构。

正确答案：
填空1：存储形式、映像、表示

12、数据的存储构分为顺序、▁▁▁、索引和哈希表4种基本类型。

正确答案：
填空1：链式

13、所有存储结点存放在一个连续的存储区里，利用结点在存储器中的相对位置来表示数据元素之间的逻辑关系。这种存储方式是▁▁▁存储结构。

填空1答案：
顺序

14、数据结构是带有结构的数据元素的集合。正确选项：正确

正确

错误
15、正确选项：正确

数据的逻辑结构是指数据元素之间的逻辑关系。

正确

错误
16、正确选项：正确

数据的物理结构是指数据在计算机内的实际存储形式。

正确

错误
17、正确选项：错误

数据对象就是一组任意数据元素的集合。

正确

错误
18、正确选项：正确

数据的运算描述是定义在数据的逻辑结构上的。

正确

错误
19、正确选项：错误

任何数据结构都具备3个基本运算：插入、删除和查找。

正确

错误
20、正确选项：错误

一种逻辑结构的数据只有一种对应的存储结构。

正确

错误
21. 正确选项：A

设n是描述问题规模的非负整数，下面程序片段的时间复杂度是（）。
时间复杂度

A、
O(n)

B、
O(log
2
?
n)

C、
O(n
2
)

D、
O(nlog
2
n)

22、正确选项：A

在数据结构中，与所使用的计算机无关的是数据的（ ）结构。

A、
逻辑

B、
逻辑和存储

C、
物理

D、
存储

23、正确选项：C

在计算机中存储数据时，通常不仅要存储各数据元素的值，而且还要存储（ ）。

A、
数据的处理方法

B、
数据元素的类型

C、
数据元素之间的关系

D、
数据的存储方法

24、正确选项：B

在算法设计时，若实参和形参同步发生改变，则应把形参变量说明为（ ）型参数。

A、
指针

B、
引用

C、
传值

D、
常值

25、正确选项：C

某算法的时间复杂度为O(n^2)，表明该算法的（ ）。

A、
问题规模是n
2

B、
执行时间等于n
2

C、
执行时间与n
2
成正比

D、
问题规模与n
2
成正比

26、正确选项：A

算法的时间复杂度与（ ）有关。

A、
问题规模

B、
计算机硬件性能

C、
编译程序质量

D、
程序设计语言

27、正确选项：C

算法分析的目的是（ ）。

A、
找出数据结构的合理性

B、
研究算法中的输入和输出关系

C、
分析算法的效率以求改进

D、
分析算法的易读性和文档性

28、正确选项：B

某算法的时间复杂度为O(n)，表示该算法的（ ）。

A、
执行时间是n

B、
执行时间与n呈现线性增长关系

C、
执行时间不受n的影响

D、
以上都不对

29、正确选项：D

算法的空间复杂度是指（ ）。

A、
算法中输入数据所占用的存储空间的大小

B、
算法本身所占用的存储空间的大小

C、
算法中占用的所有存储空间的大小

D、
算法中需要的临时变量所占用存储空间的大小

30、正确答案：
填空1：问题规模、问题规模n、n

在分析算法的时间复杂度时，通常认为算法的执行时间是▁▁▁的函数。

填空1答案：
问题规模

31、正确选项：正确

数据结构概念包括数据之间的逻辑结构、数据在计算机中的存储方式和数据的运算三个方面。

正确

错误

32、正确选项：正确

抽象数据类型与计算机内部表示和实现无关。

正确

错误

33、正确选项：B

被计算机加工的数据元素不是孤立的，它们彼此之间一般存在某种关系，通常把数据元素之间的这种关系称为（）。

A、
规则

B、
结构

C、
集合

D、
运算