计算机软件技术基础 习题一解答Word文档格式.docx
《计算机软件技术基础 习题一解答Word文档格式.docx》由会员分享，可在线阅读，更多相关《计算机软件技术基础 习题一解答Word文档格式.docx（28页珍藏版）》请在冰点文库上搜索。
（3）i=1时，i=2，j=j+i=1+2=2+1，
i=2时，i=3，j=j+i=（2+1）+3=3+1+2，
i=3时，i=4，j=j+i=（3+1+2）+4=4+1+2+3，
i=4时，i=5，j=j+i=（4+1+2+3）+5=5+1+2+3+4，
……
i=k时，i=k+1，j=j+i=（k+1）+（1+2+3+4+…+k），
解出满足上述不等式的k值，即为语句i=i+1的程序步数。
（4）for语句每执行一次，语句i=i+j将执行n次，而i的值会增加
因此，当for语句执行k次后，i的值将变为
故最终for语句的执行次数k为满足
的最小整数k，语句i=i+j的程序步数为n*k。
4.试编写一个函数计算n!
*2n的值，结果存放于数组A[arraySize]的第n个数组元素中，0narraySize。
若设计算机中允许的整数的最大值为maxInt，则当n>
arraySize或者对于某一个k（0kn），使得k!
*2k>
maxInt时，应按出错处理。
可有如下三种不同的出错处理方式：
（1）用printf显示错误信息及exit
（1）语句来终止执行并报告错误；
（2）用返回整数函数值0,1来实现算法，以区别是正常返回还是错误返回；
（3）在函数的参数表设置一个引用型的整型变量来区别是正常返回还是某种错误返回。
试讨论这三种方法各自的优缺点，并以你认为是最好的方式实现它。
#include<
stdio.h>
constintarraySize=100;
constintMaxInt=0x7fffffff;
intcalc（intT[],intn）{
inti,value=1;
T[0]=1;
if（n!
=0）{
intedge=MaxInt/n/2;
for（i=1;
n;
i++）{
value*=i*2;
T[i]=value;
if（value>
edge）return0;
}
value*=n*2;
}
T[n]=value;
printf（"
A[%d]=%d\n”,n,T[n]）;
return1;
}
voidmain（）{
intA[arraySize];
inti;
for（i=0;
arraySize;
i++）
if（!
calc（A,i））{
printf（"
failedat%d.\n"
i）;
break;
/*---------顺序表结构的定义.为简化起见，表元素我们使用整型数据-----------
-----------数据元素从data[0]处开始存储---------------------------------*/
typedefstruct/*注意typedef的使用*/
{
intdata[MAXSIZE];
/*数据域*/
intlength;
/*表长*/
}listtype;
5.设有一个线性表（a0,a1,…,an-2,an-1）存放在一个一维数组A[arraySize]中的前n个数组元素位置。
请编写一个函数将这个线性表原地逆置，即将数组的前n个原址内容置换为（an-1,an-2,…,a1,a0）。
最后分析此算法的时间复杂度及空间复杂度。
voidinverse（listtype*A）{
inttmp;
intn=A->
length;
for（inti=0;
=（n-1）/2;
i++）{
tmp=A->
data[i];
A->
data[i]=A->
data[n-i-1];
data[n-i-1]=tmp;
}
时间复杂度：
需进行n/2次循环，因此时间复杂度为O（n）；
空间复杂度：
使用一个整形辅助存储单元tmp，因此空间复杂度为O
（1）。
6.顺序表的插入和删除要求仍然保持各个元素原来的次序。
设在等概率情形下,对有127个元素的顺序表进行插入,平均需要移动多少个元素?
删除一个元素,又平均需要移动多少个元素?
若设顺序表中已有n个元素。
又设插入或删除表中各个元素的概率相等，则在插入时因有n+1个插入位置（可以在表中最后一个表项后面追加），每个元素位置插入的概率为1/（n+1），但在删除时只能在已有n个表项范围内删除，所以每个元素位置删除的概率为1/n。
插入时平均移动元素个数AMN（AveragyMovingNumber）为
删除时平均移动元素个数AMN为
7.利用顺序表的操作，实现以下的函数。
并分析你所编制的函数的时间复杂度，并分析
（2）与（3）的时间复杂度出现差异的原因。
（1）从顺序表中删除具有给定值x的所有元素。
（2）从顺序表中删除其值在给定值s与t之间（要求s小于t）的所有元素。
（3）从有序顺序表中删除其值在给定值s与t之间（要求s小于t）的所有元素。
（4）将两个有序顺序表la,lb合并成一个新的有序顺序表lc。
（5）从顺序表中删除所有其值重复的元素，使表中所有元素的值均不相同。
voidDelValue（listtype*L,intx）{
inti=0,j;
while（i<
L->
length）/*循环,寻找具有值x的元素并删除它*/
if（L->
data[i]==x）{/*删除具有值x的元素,后续元素前移*/
for（j=i;
j<
length-1;
j++）L->
data[j]=L->
data[j+1];
L-length--;
/*表长减1*/
elsei++;
（2）实现删除其值在给定值s与t之间（要求s小于t）的所有元素的函数如下：
voidDelValue_s_to_t（listtype*L,ints,intt）{
inti,j;
if（L->
length==0||s>
=t）{
printf（“Listisemptyorparametersareillegal!
\n”）;
exit
（1）;
i=0;
length）/*循环,寻找具有值x的元素并删除它*/
data[i]>
=s&
L->
data[i]<
=t）{
/*删除满足条件的元素,后续元素前移*/
for（j=i;
length--;
elsei++;
（3）实现从有序顺序表中删除其值在给定值s与t之间的所有元素的函数如下：
voidDelValue_s_to_t_1（listtype*L,intsintt）{
inti,j,k;
=t）{
for（i=0;
i++）/*循环,寻找值≥s的第一个元素*/
data[i]>
=s）break;
/*退出循环时,i指向该元素*/
if（i<
length）{
for（j=1;
i+j<
j++）/*循环,寻找值>
t的第一个元素*/
data[i+j]>
t）break;
/*退出循环时,i+j指向该元素*/
for（k=i+j;
k++）/*删除满足条件的元素,后续元素前移*/
data[k-j]=L->
data[k];
L->
length-=j;
/*表长减j*/
（4）实现将两个有序顺序表合并成一个新的有序顺序表的函数如下：
listtype*Merge（listtype*LA,listtype*LB）{
/*合并有序顺序表LA与LB成为一个新的有序顺序表并由函数返回
listtype*LC;
intvalue1,value2;
initiatelist（LC）;
if（LA->
length+LB->
length>
MAXSIZE）{
printf（“表上溢/n”;
i=0,j=0,k=0;
value1=LA->
value2=LB->
data[j];
while（i<
LA->
length&
LB->
/*循环,两两比较,小者存入结果表*/
if（value1<
=value2）{
LC->
data[k]=value1;
i++;
value1=LA->
else{
LC->
data[k]=value2;
j++;
value2=LB->
k++;
while（i<
length）{/*当LA表未检测完,继续向结果表传送*/
k++;
}
while（j<
length）{/*当LB表未检测完,继续向结果表传送*/
LC->
length=k;
returnLC;
（5）实现从表中删除所有其值重复的元素的函数如下：
voidDelDouble（listtype*L）{
inti,j,k;
inttmp;
if（L->
length==0）{
printf（“表空\n”;
i=0;
length）{/*循环检测*/
j=i+1;
tmp=L->
while（j<
length）{/*对于每一个i,重复检测一遍后续元素*/
if（tmp==L->
data[j]）{/*如果相等,删除此结点，后续元素前移*/
for（k=j+1;
k++）L->
data[k-1]=L->
/*表最后元素位置减1*/
elsej++;
i++;
/*检测完L->
data[i],检测下一个*/
8.线性表可用顺序表或链表存储。
试问：
（1）两种存储表示各有哪些主要优缺点?
（2）如果有n个表同时并存，并且在处理过程中各表的长度会动态发生变化，表的总数也可能自动改变、在此情况下，应选用哪种存储表示？
为什么？
（3）若表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，这时，应采用哪种存储表示？
（1）顺序存储表示是将数据元素存放于一个连续的存储空间中，实现顺序存取或（按下标）直接存取。
它的存储效率高，存取速度快。
但它的空间大小一经定义，在程序整个运行期间不会发生改变，因此，不易扩充。
同时，由于在插入或删除时，为保持原有次序，平均需要移动一半（或近一半）元素，修改效率不高。
链接存储表示的存储空间一般在程序的运行过程中动态分配和释放，且只要存储器中还有空间，就不会产生存储溢出的问题。
同时在插入和删除时不需要保持数据元素原来的物理顺序，只需要保持原来的逻辑顺序，因此不必移动数据，只需修改它们的链接指针，修改效率较高。
但存取表中的数据元素时，只能循链顺序访问，因此存取效率不高。
（2）如果有n个表同时并存，并且在处理过程中各表的长度会动态发生变化，表的总数也可能自动改变、在此情况下，应选用链接存储表示。
如果采用顺序存储表示，必须在一个连续的可用空间中为这n个表分配空间。
初始时因不知道哪个表增长得快，必须平均分配空间。
在程序运行过程中，有的表占用的空间增长得快，有的表占用的空间增长得慢；
有的表很快就用完了分配给它的空间，有的表才用了少量的空间，在进行元素的插入时就必须成片地移动其他的表的空间，以空出位置进行插入；
在元素删除时，为填补空白，也可能移动许多元素。
这个处理过程极其繁琐和低效。
如果采用链接存储表示，一个表的存储空间可以连续，可以不连续。
表的增长通过动态存储分配解决，只要存储器未满，就不会有表溢出的问题；
表的收缩可以通过动态存储释放实现，释放的空间还可以在以后动态分配给其他的存储申请要求，非常灵活方便。
对于n个表（包括表的总数可能变化）共存的情形，处理十分简便和快捷。
所以选用链接存储表示较好。
（3）应采用顺序存储表示。
因为顺序存储表示的存取速度快，但修改效率低。
若表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，这时采用顺序存储表示较好。
/*---------链表结构的定义.为简化起见，表元素我们使用整型数据-----------
-----------此链表带头结点--------------------------------------------*/
typedefstructmynode{
intdata;
/*数据域：
整型*/
structmynode*next;
/*指针域*/
}node,linklisttype;
9.试写出计算线性链表长度的算法。
intlengthsl（linklisttype*L）{
linklisttype*p;
intlen;
if（L==NULL）{return–1;
p=L->
next;
/*p指向链表L的头结点*/
len=0;
while（p!
=NULL）{
len++;
p=p->
returnlen;
10.设有一个表头指针为h的单链表。
试设计一个算法，通过遍历一趟链表，将链表中所有结点的链接方向逆转，如下图所示。
要求逆转结果链表的表头指针h指向原链表的最后一个结点。
voidLinkListInverse（linklisttype*L）{
linklisttype*p,*pre,*next;
if（L==NULL||L->
next==NULL）return;
/*表未初始化，或为空表*/
p=L->
pre=L;
while（p!
=NULL）{/*循环修改链表中所有结点的后继指针的指向*/
next=p->
/*取当前结点的后继指针*/
p->
next=pre;
/*当前结点的后继改为指向其原来的前驱*/
pre=p,p=next;
/*指针后移*/
next->
next=NULL;
/*原第一个结点改为最后一个结点*/
/*链表的头结点指向原最后一个结点*/
11.设有一线性链表，其结点值均为整数。
试将该线性链表分解为两个线性链表，其中一链表中的结点值均为负整数，而另一链表中结点的值均为正整数，并删除结点值为零的结点。
voidLinkListDispose（linklisttype*L,linklisttype*LA,linklisttype*LB）{
/*
将链表L分解为LA、LB两个链表，其中LA中结点值均为正，LB中结点值均为负，
并删除结点值为零的结点,最后释放L的头结点。
*/
linklisttype*p,*pt,*pa,*pb;
LA=initiatesl（）;
pa=LA;
/*指向LA中的最后一个结点*/
LB=initiatesl（）;
pb=LB;
/*指向LB中的最后一个结点*/
If（L==NULL||L->
next==NUUL）return;
/*L为空指针或L为空表*/
p=L->
/*p指向链表L的第一个结点*/
while（p!
=NULL）/*遍历链表L*/
if（p->
data>
0）{/*将p链入链表LA的pa后*/
pa->
next=p;
pa=p;
p=p->
elseif（p->
data<
0）{/*将p链入链表LB的pb后*/
pb->
pb=p;
else{/*删除值为0的结点*/
pt=p->
/*记录当前结点的后继，以便删除当前结点*/
free（p）;
p=pt;
pa->
pb->
free（L）;
12．设ha和hb分别是两个带表头结点的非递减有序单链表的表头指针,试设计一个算法,将这两个有序链表合并成一个非递减有序的单链表。
要求结果链表仍使用原来两个链表的存储空间,不另外占用其它的存储空间。
表中允许有重复的数据。
voidlinklistMerge（linklisttype*LA,linklisttype*LB）{
/*合并有序链表LA与LB,结果存入LA中，并释放LB的头结点*/
linklisttype*pa,*pb,*pre,*pn;
if（LA==NULL||LB==NULL||）return;
if（LA->
next==NULL）{/*LA为空表，则直接将LB链入LA即可*/
LA->
next=LB->
free（LB）;
retrun;
if（LB->
next==NULL）return;
/*LB为空表，则直接返回即可*/
pa=LA->
next,pb=LB->
next,pre=LA;
while（pa!
=NULL&
pb!
=NULL）/*循环,两两比较,小者存入结果表*/
if（pa->
next）{/*将pb链入LA，然后pb指针后移*/
pre->
next=pb;
pn=pb->
pb->
next=pa;
pb=pn;
pre=pre->
next
else{/*pa指针后移*/
pa=pa->
pre=pre->
if（pb!
=NULL）/*将pb剩余结点链入LA*/
pre->
free（LB）;
13．设ha和hb分别是两个带表头结点的非递减有序单链表的表头指针,试设计一个算法,将这两个有序链表合并成一个非递增有序的单链表。
Linklisttype*linklistMerge_inverse（linklisttype*LA,linklisttype*LB）{
/*合并有序链表LA与LB,结果存入LC中，并释放LA、LB的头结点,函数返回LC*/
linklisttype*pa,*pb,*p;
LC=initiatesl（）;
=NULL）/*循环,两两比较,大者存入LC*/
next）{/*将pa链为LC的第一个结点*/
p=pa->
pa->
next=LC->
pa=p;
else{/*将pa链为LC的第一个结点*/
p=pb->
pb=p;
while（pa!
=NULL）{/*将pa剩余结点链入LC*/
while（pb!
=N
升级会员 