数据结构专科作业1Word文档下载推荐.docx
《数据结构专科作业1Word文档下载推荐.docx》由会员分享，可在线阅读，更多相关《数据结构专科作业1Word文档下载推荐.docx（55页珍藏版）》请在冰点文库上搜索。
6.当需要用一个形参访问对应的实参时，则该形参应说明为引用。
7.在函数中对引用形参的修改就是对相应实参的修改，对值（或赋值）形参的修改只局限在该
函数的内部，不会反映到对应的实参上。
8.当需要进行标准I/O操作时，则应在程序文件中包含iostream.h头文件，当需要进行文件I/O操作时，
则应在程序文件中包含fstream.h头文件。
9.在包含有stdlib.h头文件的程序文件中，使用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）。
inti=0,s=0;
while（++i<
=n）{
intp=1;
j++）P*=j;
s=s+p;
}
17.一个算法的时间复杂度为（3n2+2nlog2n+4n-7）/（5n）,其数量级表示为O（n）。
18.从一个数组a[7]中顺序查找元素时，假定查找第一个元素a[0]的概率为1/3，查找第二
个元素a[1]的概率为1/4，查找其余元素的概率均相同，则在查找成功时同元素的平均比
较次数为35/12。
三、应用题
}1.设计二次多项式ax2+bx+c的一种抽象数据类型，假定起名为QIAdratic,
该类型的数据部分分为三个系数项a、b和c，操作部分为：
（请写出下面每一个
操作的具体实现）。
⑴初始化数据成员ab和c（假定用记录类型Quadratie定义成员），每个数据成
员的默认值为0。
QuadraticInitQuadratic（floataa=0,floatbb=0,floatcc=0）;
解：
QuadraticInitQuadratic（floataa,floatbb,floatcc）
{
Quadraticq;
q.a=aa;
q.b=bb;
q.c=cc;
returnq;
⑵做两个多项式加法,即使对应的系数相加,并返回相加的结果。
QuadraticAdd（Quadraticq1,Quadraticq2）;
解：
q.a=q1.a+q2.a;
q.b=q1.b+q2.b;
q.c=q1.c+q2.c;
⑶根据给定x的值计算多项式的值。
floatEval（Quadraticq,floatx）;
floatEval（Quadraticq,floatx）
return（q.a*x*x+q.b*x+q.c）;
⑷计算方程ax2+bx+c=0的两个实数根，对于有实根、无实根和不是实根方程
（即a==0）这三种情况要返回不同的整数值，以便于工作调用函数做不同的处理。
intRoot（Quadraticq,float&
r1,float&
r2）;
intRoot（Quadraticq,float&
r2）
if（q.a==0）return-1;
floatx=q.b*q.b-4*q.a*q.c;
if（x>
=0）{
r1=（float）（-q.b+sqrt（x））/（2*q.a）;
r2=（float）（-q.b-sqrt（x））/（2*q.a）;
return1;
else
return0;
⑸按照ax**2+bx+c的格式（x2用x**2表示）输出二次多项式，在输出时要注意
去掉系数为0的项，并且当b和c的值为负时，其前不能出现加号。
voidPrint（Quadraticq）
voidPrint（Quadraticq）
if（q.a）cout<
<
q.a<
"
x**2"
;
if（q.b）
if（q.b>
0）
cout<
+"
q.b<
x"
if（q.c）
if（q.c>
q.c;
end1;
2.指出下列各算法的功能并求出其时间复杂度。
⑴intprime（intn）
inti=1;
intx=（int）sqrt（n）;
while（++i<
=x）
if（n%i==0）break;
if（i>
x）return1;
elsereturn0;
判断n是否是一个素数，若是则返回数值1，否则返回0。
该算法的时间复杂度为O（n1/2）。
⑵intsum1（intn）
intp=1,s=0;
i++）{
p*=i;
s+=p;
returns;
计算∑i!
（上标为n，下标为i=1）的值，其时间的复杂度为O（n）。
⑶intsum2（intn）
ints=0;
p*=j;
的值，时间复杂度为O（n2）
⑷intfun（intn）
inti=1,s=1;
while（s<
n）
s+=++i;
returni;
求出满足不等式1+2+3...+i≥n的最小i值，其时间复杂度为O（n1/2）。
⑸voidUseFile（ifstream&
inp,intc[10]）
//假定inp所对应的文件中保存有n个整数
10;
c[i]=0;
intx;
while（inp>
>
x）{
i=x%10;
c[i]++;
利用数组c[10]中的每个元素c[i]对应统计出inp所联系的整数文件中个位值同为i的整数个
数，时间复杂度为O（n）
⑹voidmtable（intn）
for（intj=i;
*"
="
<
setw
（2）<
i*j<
打印出一个具有n行的乘法表，第i行（1≤i≤n）中有n-i+1个乘法项，每个乘法项为i与j（i≤j≤n）的乘积，时间复杂度为O（n2）。
⑺voidcmatrix（inta[M][N],intd）
//M和N为全局整型常量
M;
N;
a[i][j]*=d;
使数组a[M][N]中的每一个元素均详细以d的值，时间复杂度为O（M*N）
⑻voidmatrimult（inta[M][N],intb[N][L],intc[M][L]）
inti,j,k;
for（i=0;
for（j=0;
L;
c[i][j]=0;
for（k=0;
k<
k++）
c[i][j]+=a[i][k]*b[k][j];
矩阵相乘，即a[M][N]×
b[N][L]→c[M][L]，时间复杂度为O（M×
N×
L）。
第二章线性表
一、（答案）
⑴解：
（79,62,34,57,26,48）
⑵解：
（26,34,48,57,62,79）
⑶解：
（48,56,57,62,79,34）
⑷解：
（56,57,79,34）
⑸解：
（26,34,39,48,57,62）
二、对于List类型的线性表,编写出下列每个算法。
⑴从线性表中删除具有最小值的元素并由函数返回，空出的位置由最后一个元素填补，若
线性表为空则显示出错信息并退出运行。
ElemTypeDMValue（List&
L）
//从线性表中删除具有最小值的元素并由函数返回,空出的位置
//由最后一个元素填补,若线性表为空则显示出错信息并退出运行
if（ListEmpty（L））{
cerr<
ListisEmpty!
exit
（1）;
ElemTypex;
x=L.list[0];
intk=0;
L.size;
ElemTypey=L.list[i];
if（y<
x）{x=y;
k=i;
}
L.list[k]=L.list[L.size-1];
L.size--;
returnx;
⑵从线性表中删除第i个元素并由函数返回。
intDeletel（List&
L,inti）
//从线性表中删除第i个元素并由函数返回
if（i<
1||i>
L.size）{
Indexisoutrange!
x=L.list[i-1];
for（intj=i-1;
L.size-1;
L.list[j]=L.list[j+1];
⑶向线性表中第i个元素位置插入一个元素。
voidInser1（List&
L,inti,ElemTypex）
//向线性表中第i个元素位置插入一个元素
L.size+1）{
if（L.size==MaxSize）
Listoverflow!
for（intj=L.size-1;
j>
i-1;
j--）
L.list[j+1]=L.list[j];
L.list[i-1]=x;
L.size++;
⑷从线性表中删除具有给定值x的所有元素。
voidDelete2（List&
L,ElemTypex）
//从线性表中删除具有给定值x的所有元素
inti=0;
while（i<
L.size）
if（L.list[i]==x）{
for（intj=i+1;
L.sizr;
L.list[j-1]=L.list[j];
i++;
4.对于结点类型为LNode的单链接表,编写出下列每个算法。
⑴将一个单链接表按逆序链接,即若原单链表中存储元素的次序为a1,a2,...,an,则
逆序链接后变为an,an-1,...a1。
voidContrary（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个结点。
voidDelete1（LNode*&
HL,inti）
//删除单链表中的第i个结点
1||HL==NULL）{
LNode*ap,*cp;
ap=NULL;
cp=HL;
//cp指向当前结点，ap指向其前驱结点
intj=1;
while（cp!
if（j==i）
break;
//cp结点即为第i个结点
else{//继续向后寻找
ap=cp;
cp=cp->
j++;
if（cp==NULL）{
if（ap==NULL）
HL=HL->
ap->
next=cp->
deletecp;
⑶从单链表中查找出所有元素的最大值，该值由函数返回，若单链表为空，则显示出错信息
并停止运行。
ElemTypeMaxValue（LNode*HL）
//从单链表中查找出所有元素的最大值，该值由函数返回
if（HL==NULL）{
Linkedlistisempty!
ElemTypemax=HL->
data;
LNode*p=HL->
=NULL）{
if（max<
p->
data）max=p->
returnmax;
⑷统计出单链表中结点的值等于给定值x的结点数。
intCount（LNode*HL,ElemTypex）
//统计出单链表中结点的值等于给定值x的结点数
intn=0;
while（HL!
if（HL->
data==x）n++;
returnn;
数据结构（专科）作业2
第三章稀疏距阵和广义表
1.在稀疏矩阵的带行指针指向量的链接存储中，每个行单链表中的结点都具有相同的
A。
A行号B列号C元素值D地址
2.设一个具有t个非零元素的m*n大小的稀疏矩阵采用顺序存储，求其转置矩阵的普通
转置算法的时间复杂度为D。
AO（m）BO（n）CO（n+t）DO（n*t）
3.设一个广义表中结点的个数为n，则求广义表深度算法的时间复杂度为B。
AO
（1）BO（n）CO（n2）DO（log2n）
1.在一个稀疏矩阵中，每个非零元素所对应的三元组包括该元素的行号、列号、和
元素值。
2.在稀疏矩阵所对应的三元组线性表中，每个三元组元素按行号为主序、列号为辅
助的次序排列。
3.在初始化一个稀疏矩阵的函数定义中，矩阵形参应说明为引用参数。
4.在稀疏矩阵的顺序存储中，利用一个数组来存储非零元素，该数组的长度应大于
等于对应的三元线性表的长度。
5.在稀疏矩阵的带行指针向量的链接存储中，每个结点包含有4个域，在相应的
十字链接存储中，每个结点包含有5个域。
6.在稀疏矩阵的十字链接存储中，每个结点的down指针域指向行号相同的下一个结点，
right指针指向列号相同的下一个结点。
7.一个广义表中的元素为单元素和表元素两类。
8.一个广义表的深度等于括号嵌套的最大层数。
9.在广义表的存储结构中，每个结点均包含有3个域。
10.在广义表的存储结构中，单元素结点与表元素结点有一个域对应不同，各自分别为
值域和子表指针域。
11.若把整个广义表也看为一个表结点，则该结点的tag域的值为true或1、next域的值
为NULL或0。
1.已知一个稀疏矩阵如图3-11所示:
0400000
000-3001
8000000
0005000
0-700020
0006000
图3-11具有6行×
7列的一个稀疏矩阵
⑴写出它的三元组线性表；
（（1,2,4）,（2,4,-3）,（2,7,1）,（3,1,8）,（4,4,5）,（5,,2,-7）,（5,6,2）,（6,4,6））
⑵给出它的顺序存储表示；
下标
1
2
3
4
5
6
7
8
...
MaxTerms
row（行号）
col（列号）
val（元素值）
-3
-7
6
⑶给出它的转置矩阵的三元组线性表和顺序存储表示；
（（1,3,8）,（2,1,4）,（2,5,-7）,（4,2,-3）,（4,4,5）,（4,6,6）,（6,5,2）,（7,2,1））
3.画出下列每个广义表的带表头附加结点的链接存储结构图并分别计算出它们的长度和深度。
⑴A=（（））
⑵B=（a,b,c）
⑶C=（a,（b,（c）））
⑷D=（（a,b）,（c,d））
⑸E=（a,（b,（c,d））,（e））
⑹F=（（a,（b,（）,c）,（（d））,e）））
每小题的长度和深度如下表示。
题号
长度
深度
第四章栈和队列
一、应用题
1.设用第二章定义的类型为AlinkList的一维数组MS[MaxSize]建立三个链接堆栈，其中前三个元
素的next域用来存储三个栈顶指针，从下标为3的元素起作为空闲元素提供给三个栈共同使用，
试编写一个算法把从键盘上输入的n个整数按照下列条件分别进入不同的栈：
⑴若输入的整数x小于60，则进第一个栈；
⑵若输入的整数x大于等于60同时小于100，则进第二个栈；
⑶若输入的整数大于100，则进第三个栈。
voidMoreStack（ALinkListMS,intn）
//把从键盘上输入的n个整数按不同条件分别进入到三个不同的链接栈中
if（n>
MaxSize-3）{
存储空间不足!
inti,x,av;
3;
MS[i].next=0//置空栈，即给三个栈顶指针赋0
av=3;
//av指向可利用元素的下标，赋初值为3
输入"
n<
个整数：
//从键盘读入一个整数并把它赋给av元素的值域
cin>
x;
MS[av].data=x;
//按条件把av元素压入不同的栈，即链接到相应栈的栈顶
if（x<
60）{
Ms[av].next=MS[0].next;
MS[0].next=av;
elseif（x>
=60&
&
x<
=100）{
MS[av].next=MS[1]
升级会员 