【解答】 (4) 1-15单选题 (1)一个数组元素a[」与 的表示等价。 B D.8.a÷ (2)对于两个函数,若函数名相同,但只是不同则不是重载函数 A.参数类型 B.参数个数C.函数类型 (3)若需要利用形参直接访问实参,则应把形参变量说明为参数 A.指针 B.引用 (4)下面程序段的时间复杂度为 for(int i=0;i< for( int j=0;j<n;1-+4) a1i*i A.0(m2) C OCm x n 1. ((m+n (5)执行下面程序段时,执行S语句的次数为 for( int ja];j<=1:j++) A. n B.n2/2 C.n(n+1) D.2(n-1)/2 (6)下面算法的时间复杂度为 int I( unsigned int n) t if (n==o n=l) return 1 else return n* i(n-1);
A.O(1) B.()(n) C. O(n' 【解答】 (3)B(4)C(5)D )B 1-16填空题 )数据的逻辑结构被分为 4种。 (2)数据的有储结构被分为 和 4种 (3)在线性结构、树形结构和图形结构中,直接前驱和直接后继结点之间分别存在 着 和 的联系 ()…种抽象数据类型包括 两个部分。 (5)当一个传值型形式参数所占的体积较大时,应最好说明为 以节省参数值的 传输时间和存情参数的空间。 ()当霱要用一个形式参数自接改变对应实际参数的侑时,则该形式参数应说明 为 (7)在函数中对引用型形式参数的修改就是对相应 的修改,而对 形式参 数的修改只局限在该函数的内部,不会及映到对应的实际参数 (8)当需要进行标准IO操作时,则应在程序文件中包含头文件,当需要进行文 件/(操作时,则成在程序文件中包含头文件。 (9)一个记录r理论上占有的存储空间的大小等于所有域 ,实际上占有的存储 空间的大小即记承长度为 (10)·个数组a所占有的存储空间的大小即数组长度为 下标为i的元素a门 的存储地址为 ,或者为 (11)函数重载要求 或 有所不同 (12)对于双目操作符,其重载函数(非成员函数)带有 个参数,其中至少们一个 为的类型 (13)若对象ra和rb中至少有一个是属于用户定义的关,则执行ra-=rb时,需要 调用 重载函数,该函数的第一个参数应与 的类型相同,第二个参数应与 的类型相 (14)从一维数组an」中顺序查找出一个最大值元素的时间复杂度为 输出一 个二维数组bm]5n]中所有元素值的时间复杂度为 (15)在下面程序段中,$=p请句的执行次数为 ,b*一j语句的执行次数 该程序段的时间复杂度为 for(intj=1;j<-i:j|一)p*-」 (16)一个算法的时间复杂度为(3n2+2 logan+4n-7)/(5n),其数量级表示为
【解答】 (1)集合结构、线性结构、树形结构、图形结构(次序无先后) 2)顺序结构、链接结构、索引结构、散列结构(次序无先后) 3)1:1、1:N、M:N(或者1对1,1对N,M对N) (4)数据、操作(次序无先后) (5)引用型 (6)引用型 (7)实际参数的值、传值型 (8)iostream. h, fst (9)长度之和, sizeof(r) (10) sizeof(a)、a+、(char关 sizeof(aLt]) (11)参数类型、参数个数、排列次序(次序无先后 (12)二、用户定义 (13) int operator==、ra、rb 〔14)O(n)、O(mn) (15)n、n(n+1)/2、O(n2) (16)O(n) 1-17试计算以下程序所有语句的总执行次数。 (1)非递归的求和程序 float sum( float a[ 1, int n)4 float s=0. o for( int i=0;i< n; i++ retum s: 归的求和程序 float rsum( float a[ ], int n f(n<=0)return a[o]: else return rsum(a, n-1)+a[n-l 【解答】 (1)2n+3(2)2n+ 1-18设有3个值大小不同的整数a、b和c,试编写一个C-一函数,求 (1)其中值最大的整数; (2)其中值最小的整数; (3)其中位于中间值的整数。 【解答】 (1)求3个整数中的最大整数的函数
【方案1】 int max(int a, int b, int c)( if( c>> retnrn 【方案2】(此程序可修改循环终止变量扩大到n个整数) int max(int a, int b, int c)t int data[3]= a,b,c 开始时假定data「0最大 for(int-1;i<3;1++) 与其他整数逐个比较 if(data[l,>> data[m])m=i; //m记录新的最大者 return data 1 (2)求3个整数中的最小整数的函数 可将上面求最大整数的函数稍做修改,“>”改为“<”,可得求最小整数函数。 【方案1】 if (h s m)m=b: 【方案2】(此程序可修改循环终止变量扩大到n个整数) int max(int a, int b, int c) [={a,b int m=0; /开始时假定data[o最小 for (int 1=1;1<3:i++) /与具他整数逐个比较 if (data[i data[m])m=i m记录新的最小者 (3)求3个整数中具有中间值的整数 【方案1】 int mid( int a, int b, int c)( if(b< ml)( m2= ml; ml=b: J else m2=b; if (e ml)i m2=ml: ml=c: j else if (c m2)( m2-c:
retur 【方案2】(此程序可修改循环终止变量扩大到n个整数寻求次小元素) int rmid int a, int b. int c)( 指小最小幣数,m2指小次小整数 for (int i=1 与其他整数逐个比较 ir(data[ d s datam1)(m2-ml;ml=i;}:原米最小变为次小,m1指尔新的最小 else if(m2==-1||data[i< data[m2])m2-1:/m2记录新的次小者 return data m2 1-19用C-+函数编写一个算法,比较两个整数a和b的大小,对于a>b,a--b,a<b这 三种不同情况应分别返回“>”,“一”和“<”字符。并求其时间复杂度 【解答】 har Compare( int a, int b)I f (a> b)return>: else if t a- b) return 时间复杂度为O)(1) 1-20假定一维整型数组a[n中的每个元素值均在L0,200区间内,用(++函数编写一 个算法,分别统计出落在[0,20),[20,50),[50.80),L80,130),L130、200)等各区间内的 元素个数。 【解答】 int Count(int a_-] 用数组c「5保存统计结果 130,201}; 用来保存各统计区间的上限 int i, j: 5;i--)c[u·0 给数组c5中的每个元素赋初值0 for(i=O:i<n;i.I)( ir(a<0||an>200 return 0; 返回数值0表示数组屮数据有错统计失坡 for(j-0;j<5;j|亠) /查找所在的区间 if(a i<du])break 使统计相应区间的兀素增1 ret eturn 返回数值1表示统计成功 1-21指出下列各算法的功能并求出其时间复杂度