数据结构重难题答案解析 .pdfVIP

第一章绪论

23+…an

1试编写算法，求一元多项式P(x)=a+ax+ax+axx的值P(x)，并确定算法中的每

n0123nn0

一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能小，规定算法中不能使

用求幂函数。注意：本题中的输入a(i=0,1,…,n),x和n，输出为P(x)。通常算法的输入和输

in0

出可采用下列两种方式之一：

（1）通过参数表中的参数显式传递。

（2）通过全局变量隐式传递。

试讨论这两种方法的优缺点，并在本题算法中以你认为较好的一种方式实现输入和输出。

voidpolyvalue()

{

floatad;

float*p=a;

printf(Inputnumberofterms:);

scanf(%d,n);

printf(Inputthe%dcoefficientsfroma0toa%d:\n,n,n);

for(i=0;i=n;i++)scanf(%f,p++);

printf(Inputvalueofx:);

scanf(%f,x);

p=a;xp=1;sum=0;//xp用于存放x的i次方

for(i=0;i=n;i++)

{

sum+=xp*(*p++);

xp*=x;

}

printf(Valueis:%f,sum);

}//polyvalue

第二、三章线性顺序及链表

1设线性表存于va(1:arrsize)的前elenum个分量中且递增有序。试写一算法，将X插入

到线性表的适当位置上，以保持线性表的有序性。

StatusInsert_SqList(SqList*va,intx)//把x插入递增有序表va中

{

if(va.length+1va.listsize)returnERROR;

va.length++;

for(i=va.length-1;va.elem[i]xi=0;i--)

va.elem[i+1]=va.elem[i];

va.elem[i+1]=x;

returnOK;

}//Insert_SqList

2已知线性表中的元素（整数）以值递增有序排列，并以单链表作存储结构。试

写一高效算法，删除表中所有大于mink且小于maxk的元素（若表中存在这样的

元素），分析你的算法的时间复杂度（注意：mink和maxk是给定的两个参变量，

它们的值为任意的整数）。

StatusDelete_Between(Linklist*L,intmink,intmaxk)//删除元素递增排列的链表L

中值大于mink且小于maxk的所有元素

{

p=L-head;

while(p-next-data=mink)p=p-next;//p是最后一个不大于mink的元素

if(p-next)//如果还有比mink更大的元素

{

q=p-next;

while(q-datamaxk)q=q-next;//q是第一个不小于maxk的元素

p-next=q;

}

}//Delete_Between

3试分别以不同的存储结构实现线性表的就地逆置算法，即在原表的存储空间将

线性表（a,a...,a）逆置为（a,a,...,a）。

12nnn-11

（1）以一维数组作存储结构，设线性表存于a(1:arrsize)的前elenum个分量中。

（2）以单链表作存储结构。

voidreverse(SqList*A)//顺序表的就地逆置

{

for(