愚昧从来没有给人带来幸福；幸福的根源在于知识。——左拉。
第一章绪论。
一、单选题。
1.一个数组元素a[i]与 a 的表示等价。
a *(a+i) b a+i c *a+i d &a+i
2.对于两个函数，若函数名相同，但只是 c 不同则不是重载函数。
a 参数类型 b 参数个数 c 函数类型
3.若需要利用形参直接访问实参，则应把形参变量说明为 b 参数。
a 指针 b 引用 c 值。
4.下面程序段的复杂度为 c 。
for(int i=0;ifor(int j=0;ja[i][j]=i*j;
a o(m2) b o(n2) c o(m*n) d o(m+n)
5.执行下面程序段时，执行s语句的次数为 d 。
for(int i=1;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
6.下面算法的时间复杂度为 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.**性结构、树型结构和图形结构中，前驱和后继结点之间分别存在着 1对1 、 1对n 和 m对n 的关系。
4.一种抽象数据类型包括数据和操作两个部分。
5.当一个形参类型的长度较大时，应最好说明为引用 ，以节省参数值的传输时间和存储参数的空间。
6.当需要用一个形参访问对应的实参时，则该形参应说明为引用 。
7.在函数中对引用形参的修改就是对相应实参的修改，对值(或赋值)形参的修改只局限在该函数的内部，不会反映到对应的实参上。
8.当需要进行标准i/o操作时，则应在程序文件中包含 头文件，当需要进行文件i/o操作时，则应在程序文件中包含 头文件。
9.在包含有 头文件的程序文件中，使用 rand()%21 能够产生0-20之间的一个随机数。
10.一个记录r理论上占有的存储空间的大小等于所有域的长度之和 ，实际上占有的存储空间的大小即记录长度为 sizeof(r) 。
11.一个数组a所占有的存储空间的大小即数组长度为 sizeof(a) ，下标为i的元数a[i]的存储地址为 a+i ，或者为 (char*)a+i*sizeof(a[i])
12.函数重载要求参数类型 、 参数个数或排列顺序有所不同。
13.对于双目操作符，其重载函数带有 2 个参数，其中至少有一个为用户自定义
的类型。14.若对象ra和rb中至少有一个属于用户定义的类型，则执行ra==rb时，需要调用等于号(==重载函数，该函数第一个参数应与 ra ，的类型相同，第二个参数应与。
rb 的类型。
相同。15.从一维数组a[n]中顺序查找出一个最大值元素的时间复杂度为 o(n) ，输出一个二维数组b[m][n]中所有元素值的时间复杂度为 o(m*n) 。
16.在下面程序段中，s=s+p语句的执行次数为 n ，p*=j语句的执行次数为n(n+1)/2，该程序段的时间复杂度为 o(n2) 。
int i=0,s=0;
while(++i<=n){
int p=1;
for(int j=1;j<=i;j++)p*=j;
s=s+p17.一个算法的时间复杂度为(3n2+2nlog2n+4n-7)/(5n),其数量级表示为 o(n) 。
18.从一个数组a[7]中顺序查找元素时，假定查找第一个元素a[0]的概率为1/3，查找第二个元素a[1]的概率为1/4，查找其余元素的概率均相同，则在查找成功时同元素的平均比较次数为 35/12 。
三、应用题。
1.设计二次多项式ax2+bx+c的一种抽象数据类型，假定起名为quadratic,该类型的数据部分分为三个系数项a、b和c，操作部分为：(请写出下面每一个操作的具体实现)。
初始化数据成员a,b和c(假定用记录类型quadratie定义成员)，每个数据成员的缺省值为0。
quadratic initquadratic(float aa=0,float bb=0,float cc=0);
解：quadratic initquadratic(float aa,float bb,float cc)
quadratic q;
return q做两个多项式加法，即使对应的系数相加，并返回相加的结果。
quadratic add(quadratic& q1,quadratic& q2);
解：quadratic add(quadratic& q1,quadratic& q2)
愚昧从来没有给人带来幸福；幸福的根源在于知识。——左拉。
quadratic q;
return q根据给定x的值计算多项式的值。
float eval(quadratic& q,float x);
解：float eval(quadratic& q,float x)
float value;
value=
return value计算方程ax2+bx+c=0的两个实数根，对于有实根、无实根和不是实根方程。
即a==0)这三种情况要返回不同的整数值，以便于工作调用函数做不同的处理。
int root(quadratic& q,float& r1,float& r2);
解：int root(quadratic& q,float& r1,float& r2)
if( return -1;
float x=
if(x>=0){
r1=(float)(
r2=(float)(
return 1;
elsereturn 0按照ax**2+bx+c的格式(x2用x**2表示)输出二次多项式，在输出时要注意去掉系数为0的项，并且当b和c的值为负时，其前不能出现加号。
void print(quadratic& q)
解：void print(quadratic& q)
if( cout<< if(if(>0) cout<<"x"; elsecout<< if(if(>0) cout<<" elsecout<< cout else return 0; 解： 判断n是否是一个素数，若是则返回数值1，否则返回0。该算法的时间复杂度为 o(n1/2)。 int sum1(int n) int p=1,s=0; for(int i=1;i<=n;i++) p*=i;s+=p; return s; 解： 计算∑i!(上标为n，下标为i=1)的值，其时间的复杂度为o(n)。 int sum2(int n) int s=0; for(int i=1;i<=n;i++) int p=1; for(int j=1;j<=i;j++) p*=j;s+=p; return s; 解： 计算∑i!的值，时间复杂度为o(n2) int fun(int n) int i=1,s=1; while(s>x){ i=x%10; c[i解： 利用数组c[10]中的每个元素c[i]对应统计出inp所联系的整数文件中个位值同为i的整数个数，时间复杂度为o(n) void mtable(int n) for(int i=1;i<=n;i++) for(int j=i;j<=n;j++) cout<。 从线性表中删除具有最小值的元素并由函数返回，空出的位置由最后一个元素填补，若线性表为空则显示出错信息并退出运行。 解： elemtype dmvalue(list& l) /从线性表中删除具有最小值的元素并由函数返回，空出的位置。 /由最后一个元素填补，若线性表为空则显示出错信息并退出运行。 if(listempty(l)){ cerr<<"list is empty!"< cerr<<"index is out range!"< cerr<<"index is out range!" 从线性表中删除具有给定值x的所有元素。 解：void delete2(list& l,elemtype x) /从线性表中删除具有给定值x的所有元素。 int i=0; while(i< j=i+1;j< elsei4.对于结点类型为lnode的单链接表，编写出下列每个算法。 将一个单链接表按逆序链接，即若原单链表中存储元素的次序为a1,a2,..an,则逆序链接后变为an,an-1,..a1。 解：void contrary(lnode*&hl) /将一个单多办实事有按逆序链接。 lnode* p=hl;//p指向待逆序的第一个结点，初始指向原表头结点。 hl=null;//hl仍为逆序后的表头指针，初始值为空。 while(p!=null) //把原单链表中的结点依次进。 行逆序链接。 lnode* q=p; /q指向待处理的结点。 p=p->next; /p指向下一个待逆序的结点。 /将q结点插入到已陈序单链表的表头。 q->next=hl; hl=q删除单链表中的第i个结点。 解：void delete1(lnode*&hl,int i) /删除单链表中的第i个结点。 if(i<1||hl==null){ cerr<<"index is out range!" j++;if(cp==null){ cerr<<"index is out range!" elseap->next=cp->next; /删除的不是第一个结点。 delete cp从单链表中查找出所有元素的最大值，该值由函数返回，若单链表为空，则显示出错信息并停止运行。 解：elemtype maxvalue(lnode*hl) /从单链表中查找出所有元素的最大值，该值由函数返回。 if(hl==null){ cerr<<"linked list is empty!" lnode*p=hl->next; while(p!=null){ if(maxdata) max=p->data; p=p->next; return max统计出单链表中结点的值等于给定值x的结点数。 解：int count(lnode*hl,elemtype x) /统计出单链表中结点的值等于给定值x的结点数。 int n=0; while(hl!=null){ 愚昧从来没有给人带来幸福；幸福的根源在于知识。——左拉。 if(hl->data==x) n++; hl=hl->next; return n愚昧从来没有给人带来幸福；幸福的根源在于知识。——左拉。 读书有三到，谓心到，眼到，口到 朱熹 第一章绪论。一 单选题。1.一个数组元素a i 与 a 的表示等价。a a i b a i c a i d a i 2.对于两个函数，若函数名相同，但只是 c 不同则不是重载函数。a 参数类型 b 参数个数 c 函数类型 3.若需要利用形参直接访问实参，则应把形... 第一章绪论。一 单选题。1.一个数组元素a i 与 a 的表示等价。a a i b a i c a i d a i 2.对于两个函数，若函数名相同，但只是 c 不同则不是重载函数。a 参数类型 b 参数个数 c 函数类型 3.若需要利用形参直接访问实参，则应把形参变量说明为 b 参数。a 指针 b ... 第一章绪论。1 数据结构研究的内容 数据的逻辑结构 数据的物理结构 数据运算。2 数据的逻辑结构 集合 线性结构 树形结构 图形结构。1 各种逻辑结构的特点 线性结构 一对一 树形结构 一对多 图形结构 多对多 2 逻辑结构的二元组描述 见下例 例 数据的逻辑结构如下，试画出对应的逻辑结构图。fam...数据结构 专科 作业
数据结构 专科 作业
数据结构》复习提纲 专科