江苏省白蒲高级中学2020—2021学年信息技术竞赛数据结构与算法全套练习（含答案）

　　 　　　　　　　　　　　　　 　　　　　　　　　5 绪论 作业1 一、单项选择题 1．数据结构在计算机中的表示称为数据的（　A　）。 A）存储结构 B）抽象结构 C）顺序结构 D）逻辑结构 2．对于下面程序段的时间复杂度为（　B　）。 for(i=1;i<=n;i++) for(j=1;j<=i;j++) x=x+1; A）O(n) B）O(n2) C）O(n*i) D）O(n+i) 3．数据结构是（　A　）。 A）相互之间存在一种或多种特定关系的数据元素的集合 B）相互之间存在一种特定关系的数据元素的集合 C）数据元素的集合 D）前面都不正确 4．数据结构可形式地定义为(D,S)，其中S是D上（　C　）的有限集。 A）操作 B）存储映象 C）关系 D）数据元素 5．数据结构在计算机中存储器内表示时，物理地址和逻辑地址相同并且是连续的，称之为（　B　）。 A）逻辑结构 B）顺序存储结构 C）链式存储结构 D）以上都对 二、综合题 1．下面程序段用于求两个n*n矩阵相乘的算法，试求其时间复杂度。 for(i=0;i<n;i++) for(j=0;j<n;j++){ c[i][j]=0; for(k=0;k<n;k++) c[i][j]=c[i][j]+a[i][k]*b[k][j]; } 【解答】 问题规模n，基本操作为乘法“*”， 三层for循环，每层循环n次，基本操作的执行次数为f(n)= ，则时间复杂度T(n)=O(f(n))=O( ). 2．试编写一算法，实现将输入的三个整数x，y，z按从小到大的顺序排列起来。 【解答】： #include <iostream> using namespace std; int main(int argc, char** argv) { int x,y,z,mid; cout<<"请输入三个整数："<<endl; cin>>x>>y>>z; if(x>=y) { mid=x; x=y; y=mid; } if(x>=z) { mid=x; x=z; z=mid; } if(y>=z) { mid=y; y=z; z=mid; } cout<<"输入的三个整数按从小到大的顺序排列起来为："<<x<<" "<<y<<" "<<z<<endl; retur