第1章 绪 论
2、（1）×(２)×(3)√
3、（１）A(2）C（3)C
５、计算下列程序中x=x+1得语句频度
fｏr(i=1;i＜=n；ｉ＋+）
for（j=1;ｊ〈=i；ｊ++）
ｆoｒ（k＝1；k〈=j;ｋ＋+)
x=x＋1;
【解答】x=ｘ+1得语句频度为：
T（n）=1+（1＋2）+(1+2+3）＋……+(1+2＋……+n）=n（n+1）(n＋2)/6
6、编写算法，求 一元多项式pn（x)=ａ０+a1x+a2x2+……、+anxn得值pn(x0),并确定算法中每一语句得执行次数与整个算法得时间复杂度,要求时间复杂度尽可能小，规定算法中不能使用求幂函数.注意:本题中得输入为ai(i=0，１,…n)、x与n,输出为Ｐn（x0）。 算法得输入与输出采用下列方法
（1）通过参数表中得参数显式传递
（2）通过全局变量隐式传递。讨论两种方法得优缺点,并在算法中以您认为较好得一种实现输入输出.
【解答】
（1）通过参数表中得参数显式传递
优点：当没有调用函数时，不占用内存，调用结束后形参被释放,实参维持，函数通用性强,移置性强。
缺点：形参须与实参对应，且返回值数量有限。
(２）通过全局变量隐式传递
优点:减少实参与形参得个数，从而减少内存空间以及传递数据时得时间消耗
缺点:函数通用性降低,移植性差
算法如下:通过全局变量隐式传递参数
ＰolyValue(）
{ int i，ｎ；
float ｘ,a[],ｐ;
prｉｎtf(“＼nn=”);
ｓｃanf（“%f”，&n）;
prｉntf（“\nx＝”)；
scaｎf(“%f”,＆x）；
ｆor（i＝0;i<ｎ；i++)
ｓｃａnf（“％ｆ "，＆a［i]）; /＊执行次数：n次 */
p=a[0］;
foｒ（ｉ=1；i<=n;ｉ++）
{ ｐ=p+a［i]*x; ／＊执行次数:n次*/
x=ｘ*x；｝
ｐriｎｔｆ(“％f”，p）;
｝
算法得时间复杂度：Ｔ（n)=O（ｎ）
通过参数表中得参数显式传递
ｆｌoａt PolyVａｌuｅ（float a[ ]， fｌoat x, ｉｎt n）
{
ｆｌｏaｔ p，s;
int i；
p=x；
s=a[0]；
fｏr(i＝1;ｉ<＝ｎ;i＋＋)
｛s=ｓ+a［i]＊p； /*执行次数：n次*/
p=p*x;｝
rｅturn（p）；
}
算法得时间复杂度：T(n）=Ｏ（n）
第2章 线性表
习 题
１、填空：
(1）在顺序表中插入或删除一个元素,需要平均移动一半元素，具体移动得元素个数与插入或删除得位置有关。
(2）线性表有顺序与链式两种存储结构.在顺序表中，线性表得长度在数组定义时就已经确定，就是静态保存，在链式表中,整个链表由“头指针”来表示,单链表得长度就是动态保存。
(３）在顺序表中，逻辑上相邻得元素，其物理位置_一定＿＿＿__相邻.在单链表中,逻辑上相邻得元素,其物理位置不一定相邻。
（4）在带头结点得非空单链表中，头结点得存储位置由头指针指示，首元素结点得存储位置由头结点指示，除首元素结点外，其它任一元素结点得存储位置由其直接前趋得neｘt域指示.
2、选择题
(1) A
（2） 已知L就是无表头结点得单链表,且P结点既不就是首元素结点,也不就是尾元素结点。按要求从下列语句中选择合适得语句序列.
a、 在P结点后插入S结点得语句序列就是:E、Ａ。
b、 在Ｐ结点前插入S结点得语句序列就是：H、Ｌ、Ｉ、Ｅ、A。
c、 在表首插入S结点得语句序列就是：F、M。
d、 在表尾插入S结点得语句序列就是：L、J、A、G。
供选择得语句有:
A P—>ｎext=S;
B P-＞nexｔ= P—〉nexｔ－>nexｔ;
Ｃ P-＞next= S—〉next；
D S—〉neｘt= P－>next;
Ｅ S－>ｎｅxt= L;
F S->nｅxｔ＝ NULＬ；
G Q= Ｐ；
H ｗhilｅ （P-〉nexｔ!=Q） P＝P－>ｎｅxt;
I ｗhile (P－>nｅxt!=NUＬL） P=Ｐ—〉nexｔ;
Ｊ P= Ｑ;
K P＝ L；
Ｌ Ｌ= Ｓ；
M L= P;
(3) D
(4) D
(5) Ｄ
（6） A
7试分别以不同得存储结构实现单线表得就地逆置算法，即在原表得存储空间将线性表(a1，ａ2,…，an)逆置为(an，aｎ—1，…，ａ1）。
【解答】（1)用一维数组作为存储结构
voiｄ inｖert(SeqLｉst ＊L， iｎt ＊num)
{
ｉnt j;
ＥｌemTｙｐe tｍp；
ｆor（j=0；j＜＝(*ｎｕm-１）/２;j＋＋）
{ tmp=L[j]；
Ｌ[j]=Ｌ［＊nｕm－j-1]；
L[＊num—ｊ—1]=tmp;}
｝
(２）用单链表作为存储结构
vｏid ｉnｖert（ＬｉｎｋＬiｓt L)
｛
Nodｅ ＊p， ＊q， ＊r；
if(L-〉nｅxt ==NULL) return; /＊链表为空*/
p＝L->next；
q=p—>next；
ｐ—>next=NULL; /＊ 摘下第一个结点，生成初始逆置表 *／
wｈilｅ(ｑ！＝NＵLL) /* 从第二个结点起依次头插入当前逆置表 ＊／
｛
r=q－〉nｅxt；
ｑ->ｎeｘt=L－〉next;
L－〉next=q;
q=r;
}
｝
11将线性表A=(ａ１,a2，……am）, Ｂ＝（ｂ1,b２，……bn）合并成线性表C， C＝(a1,b1，……ａm,bm,bm+1，……、bn） 当m〈＝n时，或数据结构与算法第二版课后题答案 Ｃ=(a1，ｂ1， ……an，bｎ,an＋１，……am）当m＞ｎ时,线性表A、B、C以单链表作为存储结构，且C表利用A表与Ｂ表中得结点空间构成.注意:单链表得长度值m与n均未显式存储.
【解答】算法如下：
LinkＬist mergｅ(LinkLｉst A, LｉnkList B， LｉnkList C）
｛ Ｎｏde *pa， *ｑa， *pb， ＊qb， ＊p；
pa＝Ａ—〉nexｔ； /*pa表示A得当前结点＊/
ｐb=B－>next；
ｐ＝A; / *利用p来指向新连接得表得表尾，初始值指向表A得头结点＊/
whilｅ(pa!=NULL ＆＆ ｐｂ!=NULL） /*利用尾插法建立连接之后得链表*／
{ qa=pa->nexｔ；
qb=qb—>next；
p－>ｎext＝pa; /*交替选择表Ａ与表Ｂ中得结点连接到新链表中;*／
p=pａ；
p—＞nexｔ＝pb;
p=pb;
pa=qa;
pb=qb;
｝
if（pａ!＝NＵＬL） p—>next=pａ； /*A得长度大于B得长度＊/
if（ｐｂ!＝NULL) p－〉ｎeｘt=ｐb； /＊Ｂ得长度大于Ａ得长度＊/
C=A;
Rｅturｎ（C)；
｝
实习题
约瑟夫环问题
约瑟夫问题得一种描述为:编号1，2,…,n得n个人按顺时针方向围坐一圈,每个人持有一个密码（正整数）。一开始任选一个报数上限值m，从第一个人开始顺时针自1开始顺序报数，报到ｍ时停止报数.报m得人出列，将她得密码作为新得m值，从她在顺时针方向上得下一个人开始重新从1报数，如此下去，直至所有得人全部出列为止。试设计一个程序,求出出列顺序。利用单向循环链表作为存储结构模拟此过程，按照出列顺序打印出各人得编号。
例如m得初值为20；n＝7，7个人得密码依次就是：３,１，７,2，4，8,4,出列顺序为6,1，4,７，2,３,5.
【解答】算法如下:
ｔypedef stｒuct Nodｅ
｛
ｉｎt pasｓwｏrd；
ｉｎt num；
struｃt Node ＊nｅxｔ；
｝ Nｏde,＊Lｉnklist；
ｖoid Ｊosｅphuｓ（）
{
Ｌｉｎklisｔ L；
Noｄe *p，*r,＊q;
ｉｎｔ m,n，C，j；
L＝(Ｎoｄe*)ｍaｌｌｏc（siｚｅof(Nｏｄe））; ／＊初始化单向循环链表＊/
if（L＝＝NULＬ) { printf(”\n链表申请不到空间！”）；return;}
L－〉nｅxt＝ＮＵLＬ;
ｒ=L；
prinｔf("请输入数据n得值(ｎ〉0）:”);
sｃanｆ(”％ｄ＂，&n);
foｒ(j=１；j〈=n；j＋+) /＊建立链表*／
｛
p＝（Ｎodｅ*)malloc（ｓｉzeｏｆ(Node)）；
if(ｐ!=NULL）
{
priｎtf（＂请输入第%ｄ个人得密码：",j);
scaｎf（"％d"，＆C）；
p—>pasｓworｄ=C;
p->nｕm=ｊ；
r—>ｎeｘt＝p;
r＝ｐ；
}
}
r-〉next=Ｌ-〉nｅxｔ；
printｆ("请输入第一个报数上限值ｍ（m〉0）：”)；
ｓcａｎｆ(”％d”,&m）；
printf（＂＊*＊＊*＊**＊＊＊****＊*＊＊＊**＊***＊＊**＊＊**＊*＊**＊*\ｎ"）;
ｐrintf（”出列得顺序为：\ｎ");
q=Ｌ；
p=Ｌ—>next；
ｗhiｌe(n!=1） /*计算出列得顺序＊/
{
ｊ=1;
wｈｉle（j〈ｍ） /＊计算当前出列得人选ｐ＊/
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论