第1章 时间复杂度 练习题

算法与数据结构试题第⼀章算法分析基础1、下列时间复杂度最好的是( )A 、O )(log 2nB 、O )(2n C 、O )(n D 、O )log (2n n2、从逻辑上可以把数据结构分为哪两⼤类？（）A 、动态结构、静态结构B 、顺序结构、链式结构C 、线性结构、⾮线性结构D 、初等结构、构造型结构3、算法分析的主要任务是分析（）A ．算法是否具有较好的可读性B ．算法中是否存在语法错误C ．算法的功能是否符合设计要求D ．算法的执⾏时间和问题规模之间的关系4、下⾯程序段中带下划线的语句的执⾏次数是。

for(i=0;i<=n;i++)for(j=0;j<=i;j++) x=x+1;5、下列程序的时间复杂度为（）s=0;for(i=0;i<10;i++)for(j=0;j<10;j++)s=s+1;A ． O （10）B ． O （20）C． O （1） D．O（102）6、数据的最⼩单位是（）A.数据项B.数据类型C.数据元素D.数据变量7、下列程序的时间复杂度为（）i=1；k=100；{k=k+1；i=i+2；}A.O（1）B. O（n）C. O（n3）D.O（n2）8、称算法的时间复杂度为O(logn)，其含义是指算法的执⾏时间和_______的数量级相同。

第⼆章线性表1、⾮空的循环单链表L的尾结点（由p所指）满⾜（）A.p->next=NULLB. p=NULLC. p->next= LD. p= L2、从⼀个长度为n的顺序表中删除第i个元素（1≤i≤n）时，需向前移动的元素的个数是（）A.n-iB.n-i+1C.n-i-1D.i3、链表不具备的特点是（）A．可随机访问任⼀结点 B．插⼊删除不需要移动元素C．不必事先估计存储空间 D．所需空间与其长度成正⽐4、顺序表的存储密度为1，⽽链表的存储密度 _。

5、写算法，顺序查找⼀个元素值等于e的元素的逻辑序号。

第一章测试试题参考答案一、单选题1.一个数组元素a[i]与____A____的表示等价。

A、*(a+i)B、a+iC、*a+iD、&a+i2.下面程序段的时间复杂度为____C________。

for(int i=0; i<m; i++)for(int j=0; j<n; j++) a[i][j]=i*j;A、O(m2)B、O(n2)C、O(m*n)D、O(m+n)3.执行下面程序段时，执行S语句的次数为_____D_____。

for(int i=1; i<=n; i++)for(int j=1; j<=i; j++) S;A、n2B、n2/2C、n(n+1)D、n(n+1)/24.下面算法的时间复杂度为______B______。

int f( unsigned int n ){ if ( n==0 || n==1 ) return 1; else return n*f(n-1); }A、O(1)B、O(n)C、O(n2)D、O(n!)二、填空题1.数据的逻辑结构被分为__集合__、___线性结构__、_树形结构_和____图状结构_四种。

2.数据的存储结构被分为_顺序存储结构___和_____链式存储结构_____两种。

3.在线性结构、树形结构和图形结构中，前驱和后继结点之间分别存在着__一对一___、___一对多_____和__多对多__的联系。

4.一种抽象数据类型包括__数据模型（数据对象及数据关系）_和_该模型上的操作两个部分。

5.当一个形参类型的长度较大时，应最好说明为_指针或引用型____，以节省参数值的传输时间和存储参数的空间。

6.当需要用一个形参访问对应的实参时，则该形参应说明为__指针或引用型___。

7.在函数中对引用形参的修改就是对相应__实参___的修改，对__值型__形参的修改只局限在该函数的内部，不会反映到对应的实参上。

8.一个数组a所占有的存储空间的大小即数组长度为___sizeof(a)____，下标为i的元素a[i]的存储地址为__a+i______，或者为____a+i*sizeof(a[0])___。

时间复杂度练习题一、基础知识题1. 请简述时间复杂度的定义及其在算法分析中的重要性。

2. 常见的时间复杂度有哪些？请按从低到高的顺序排列。

4. 请举例说明一个O(n)时间复杂度的算法。

5. 如何计算一个循环语句的时间复杂度？二、选择题A. O(n^3)B. O(2^n)C. O(1)D. O(n!)2. 一个算法的时间复杂度为O(n)，如果输入规模n增加10倍，其运行时间将如何变化？A. 减少到原来的1/10B. 增加到原来的10倍C. 增加到原来的100倍D. 不确定A. 二分查找B. 冒泡排序C. 快速排序D. 选择排序A. 遍历一个长度为n的数组B. 遍历一个长度为n的链表C. 遍历一个长度为n的数组，并对每个元素进行一次操作D. 遍历一个长度为n的数组，并对每对元素进行一次操作三、计算题for i in range(n):for j in range(n):print(i, j)for i in range(n):print(i)while head:print(head.val)head = head.next四、分析题def bubble_sort(arr):n = len(arr)for i in range(n):for j in range(0, ni1):if arr[j] > arr[j+1]:arr[j], arr[j+1] = arr[j+1], arr[j] def binary_search(arr, target):left, right = 0, len(arr) 1while left <= right:mid = (left + right) // 2if arr[mid] == target:return midelif arr[mid] < target:left = mid + 1else:right = mid 1def factorial(n):if n == 0:return 1else:return n factorial(n1)五、判断题1. 一个算法的时间复杂度与输入数据的顺序无关。

数据结构习题及答案第1章算法一、选择题1.算法的时间复杂度是指（）。

A）执行算法程序所需要的时间B）算法程序中的指令条数C）算法执行过程中所需要的基本运算次数D）算法程序的长度2.算法的空间复杂度是指（）。

A）算法程序的长度B）算法程序所占的存储空间C）算法执行过程中所需要的存储空间D）算法程序中的指令条数3.下面（）的时间复杂度最好（即执行时间最短）。

logn)O(）O(n ) B）A2logn2 ) D）O(n)C）O(n24.下面累加求和程序段的时间复杂度为（）。

int sum(int a[],int n){int i, s=0;for (i=0;i<n;i++)< p="">s+=a[i];return s;}logn ) ）O(A）O(1 ) B22)）O(nC）O(n ) D中的算法，c[][]相加的结果存放到b[][]n阶矩阵5.下面是将两个n阶矩阵a[][]与。

该算法的时间复杂度为（）void matrixadd(int a[][],intb[][],c[][],int n){int i,j;for (i=0;i<n;i++)< p="">for(j=0;j<n;j++)< p="">c[i][j]=a[i][j]+b[i][j];}nlog) ）O(1 ) B）O(A22) ）O(nO( n ) DC）。

6.下面程序段的时间复杂度为（） 1int i=0,s1=0,s2=0;while(i<n)< p="">{if(i%2)s1+=i;elses2+=i;i++;}nlog) O(A）O(1 ) B）22) ）O(nC）O(n ) D ）。

7.下面程序段的时间复杂度为（int prime(int n){int i=1;int x=(int)sqrt(n);while(i<=x){i++;if(n%i==0)break;}if(i>x)return 1;elsereturn 0;}nlog) O(O(1 ) BA））2n) O(）CO(n ) D））下面程序段的时间复杂度为（8.int fun(int n){int i=1,s=1;while(s<n)< p="">{i++;s+=i;}return i;}nlog)O(n/2) BA））O(2 2n) ）O(C）O(n ) D9.下面程序段的时间复杂度为（）int i,j,m,n,a[][];for(i=0;i<m;i++)< p="">for(j=0;j<n;j++)< p="">a[i][j]=i*j;22) ）O(nA）O(m) BO(m+n) ）C）O(m*n ) D ）10. 下面程序段的时间复杂度为（int sum1(int n){int i,p=1,s=0;for(i=1;i<=n;i++){p*=i;s=s+p;}return s;}nlog) ）O(A）O(1 ) B22)O(n ) D）O(nC）二、填空题复杂度。

一、填空题01、数据结构是一门研究非数值计算的程序设计问题中计算机的(操作对象)以及它们之间的(关系和运算)等的学科。

02、数据结构被形式地定义为(D,R)，其中D是(数据元素)的有限集合，R是D上的(关系)有限集合。

03、数据结构包括数据的(逻辑结构)、数据的(存储结构)和数据的(运算)这三个方面的内容。

04、数据结构按逻辑结构可分为两大类，它们分别是(线性结构)和(非线性结构)。

05、线性结构中元素之间存在(一对一)关系，树形结构中元素之间存在(一对多)关系，图形结构中元素之间存在(多对多)关系。

06、在线性结构中，第一个结点(没有)前驱结点，其余每个结点有且只有1个前驱结点；最后一个结点(没有)后续结点，其余每个结点有且只有1个后续结点。

07、在树形结构中，树根结点没有(前驱)结点，其余每个结点有且只有(1)个前驱结点；叶子结点没有(后续)结点，其余每个结点的后续结点数可以(任意多个)。

08、在图形结构中，每个结点的前驱结点数和后续结点数可以(任意多个)。

09、数据的存储结构可用四种基本的存储方法表示，它们分别是(顺序)、(链式)、(索引)、(散列)。

10、对于给定的n个元素，可以构造出的逻辑结构有(集合)、(线性结构)、(树形结构)、(图状结构)四种。

11、数据的运算最常用的有5种，它们分别是(插入)、(删除)、(修改)、(查找)、(排序)。

12、一个算法的效率可分为(时间)效率和(空间)效率。

13、数据结构中评价算法的两个重要指标是算法的(时间复杂度)和(空间复杂度)。

14、一个数据结构在计算机中的(映射)称为存储结构。

15、算法的五个重要特性是(有穷性)、(确定性)、(可行性)、输入、输出。

16、已知如下程序段for (i=n; i>=1; i--) //语句1{ x++; //语句2for (j=n; j>=i; j--) //语句3y++; //语句4}语句 1 执行的频度为(n+1)；语句2执行的频度为(n)；语句3执行的频度为(n(n+3)/2)；语句4执行的频度为(n(n+1)/2)。

数据结构章节练习题第一章绪论一、单选题1.一个数组元素a[i]与________的表示等价。

A、 *(a+i)B、 a+iC、 *a+iD、 &a+i2.下面程序段的时间复杂度为____________。

for(int i=0; i<m; i++)for(int j=0; j<n; j++)a[i][j]=i*j;A、 O(m2)B、 O(n2)C、 O(m*n)D、 O(m+n)3.执行下面程序段时，执行S语句的次数为____________。

for(int i=1; i<=n; i++)for(int j=1; j<=i; j++)S;A、 n2B、 n2/2C、 n(n+1)D、 n(n+1)/24.下面算法的时间复杂度为____________。

int f( unsigned int n ){ if ( n==0 || n==1 ) return 1; else return n*f(n-1); }A、 O(1)B、 O(n)C、 O(n2)D、 O(n!)二、填空题1.数据的逻辑结构被分为__________、_________、__________和__________四种。

2.数据的存储结构被分为__________、和__________两种。

3.在线性结构、树形结构和图形结构中，前驱和后继结点之间分别存在着________、________和________的联系。

4.一种抽象数据类型包括__________和__________两个部分。

5.在下面程序段中，s=s+p语句的执行次数为________，p*=j语句的执行次数为________，该程序段的时间复杂度为________。

int i=0,s=0;while(++i<=n) {int p=1;for(int j=1;j<=i;j++) p*=j;s=s+p;}6.一个算法的时间复杂度为(3n2+2nlog2n+4n-7)/(5n)，其数量级表示为________。

第1章绪论1.1选择题1. 算法的时间复杂度取决于（）A）问题的规模B）待处理数据的初态C）A和B2.计算机算法指的是解决问题的步骤序列，它必须具备（）这三个特性。

A）可执行性可移植性可扩充性B）可执行性、确定性、有穷性C）确定性、有穷性、稳定性D）易读性、稳定性、安全性5．从逻辑上可以把数据结构分为（）两大类。

A）动态结构、静态结构B）顺序结构、链式结构C）线性结构、非线性结构D）初等结构、构造型结构6．在下面的程序段中，对x的赋值的语句频度为（）for(i=0;i<n;i++)for(j=0;j<n;j++) x=x+1;A）O(2n) B）O(n) C．O(n2) D．O(log2n)7．下面的程序段中，n为正整数，则最后一行的语句频度在最坏情况下是（）for(i=n-1;i>=1;i--)for(j=1;j<=i;j++)if (A[j]>A[j+1])A[j]与A[j+1]对换；A. O（n）B）O(nlog2n) C）O(n3) D）O(n2)1.2填空题2. 对于给定的n个元素,可以构造出的逻辑结构有_____________，_____________，_____________，_____________四种。

4．数据结构中评价算法的两个重要指标是_____________。

5. 数据结构是研讨数据的_____________和_____________，以及它们之间的相互关系，并对与这种结构定义相应的_____________，设计出相应的_____________。

6．一个算法具有5个特性：_____________、_____________、_____________，有零个或多个输入、有一个或多个输出。

9．已知如下程序段for(i=n;i>0;i--) {语句1}{ x=x+1; {语句2}for(j=n;j>=i;j--) {语句3}y=y+1; {语句4}}语句1执行的频度为_____________；语句2执行的频度为_____________；语句3执行的频度为_____________；语句4执行的频度为_____________。

数据结构习题第⼀章知识点：1.基本概念：数据结构分类、特点等：如线性结构，是数据元素之间存在⼀种（⼀对⼀关系）数据元素的概念（数据项）2.时空复杂度1、设有数据结构（D ，R ），其中D={d1,d2,d3,d4,d5,d6},R=r ,r={(d1,d2),(d2,d3),(d3,d4),(d2,d5),(d3,d5)}试按照图论中的画法画出其逻辑结构图。

2、称算法的时间复杂度为O(f(n))，其含义是指算法的执⾏时间和_【1】_的数量级相同。

3. 计算下⾯程序段的时间复杂度。

x=0;for(i=1; ifor (j=1; j<=n-i; j++)x++;解：因为x++共执⾏了n-1+n-2+……＋1= n(n-1)/2，所以执⾏时间为O （n 2）. 4. 计算下⾯程序段的时间复杂度。

x=n;y=0; 解：设@执⾏了t(n)次，则(t(n)+1)2<=n ，推出t(n)<=n 1/2-1。

所以时间复杂度为O （n 1/2）.5. 分析下⾯各程序段的时间复杂度（1） O(n*m) (2) O(log 3n) 1）for (i=0; ifor (j=0; jA[i][j]=0; 2） i=1;while(i<=n) i=i*3;6. 在n 个结点的顺序表中，算法的时间复杂度是O （1）的操作是：A（A ）访问第i 个结点（1≤i ≤n ）和求第i 个结点的直接前驱（2≤i ≤n ）（B ）在第i 个结点后插⼊⼀个新结点（1≤i ≤n ）（C ）删除第i 个结点（1≤i ≤n ）（D ）将n 个结点从⼩到⼤排序第⼆章线性表知识点：顺序表、单链表、双向链表（插⼊、查找、删除运算）循环链表(单双向)特点，考点：基本操作、复杂度、特点、算法应⽤1.在⼀个单链表中，若p所指结点是q所指结点的前驱结点，则删除结点q的正确操作是（ B ）A. p->next=qB. p->next=q->nextC. p=q->nextD. p->next=q->next->next2、在⼀个头指针为head的带头结点单链表中，要向表头插⼊⼀个由指针p指向的结点,则应执⾏【4】p->next=head->next;、【5】head->next=p。

时间复杂度⼗道练习题⽬1、分析以下时间复杂度void fun(int n){int i=0,s=0;while(s<n){++i;s=s+i;}}分析：n为规模，基本操作语句是++i和s=s+i，while循环处当s>=n不符合条件停⽌，假设执⾏m次结束，i=1,2,3..依次渐加，i只影响s值，主要看s， s1=1, s2 =1+2=3, s3 =1+2+3=6，... s m =1+2+3+...+m=m(m+1)/2 ,正解答案中给出，m(m+1)/2+k=n (k起修正作⽤的常数)，也可⼤致⼝算m≈ √n ,则时间复杂度为O( √n )2、设n为如下程序段处理的数据个数，求时间复杂度for(i=1;i<n;i=2*i)std::cout<<"i="<<i<<std::endl;分析：主看for循环，当i>=n时结束，假设执⾏m次结束, i1 =2= 21 , i2 =2*2 = 22 , ..., i m = 2m ,则有 2m =n ,⼤致⼝算m= log2n ，则时间复杂度为O( log2n )3、计算n！的递归函数如下，分析时间复杂度int func(int n){if(n<=1)return 1; //①elsereturn n*func(n-1); //②}分析：n！递归函数中，①的时间复杂度显然O(1)，应主要分析else后的语句②，递归调⽤func(n-1)的时间开销为T(n-1)，则②时间开销就是O(1)+T(n-1)。

假设求1!就是O(1)+T(n-1)=1×O(1)+T(n-1)【n=1】 ,2!就是O(1)+O(1)+T(n-2)=2×O(1)+T(n-2)【n=2】... ，n！=(n-1)×O(1)+T(n-(n-1)) =(n-1)×O(1)+T(1) = n×O(1)=O(n) ，所以时间复杂度为O(n)4、设A是⼀个线性表（a_1 ....a_n）采⽤顺序存储结构，则在等概率的前提下，平均插⼊⼀个元素需要移动的元素个数是多少？若元素插⼊在a_i(1≤i≤n)所在位置处的概率为 n-i/n(n-1)/2 ,则平均插⼊⼀个元素要移动的元素个数是多少？分析：（1）：在a_1插⼊则要移动n次，a_2插⼊移动n-1次，...，a_n插⼊移动0次，总次数为0+1+2+...+n=n(n+1)/2 ,总共是0到n共1+n个 。