数据结构与算法分析c语言描述中文答案.pdf

语言描述中文答
案

【篇一：数据结构语言版)课后习题答案完整版】
(c

选择题：
6．试分析下面各程序段的时间复杂度。（1）o（1）（2）o

（m*n）（3）o（n2）（4）o（log3n）
（5）因为x++共执行了n-1+n-2+??＋1=n(n-1)/2，所以执行时间

为o（n2）（6）o(n)
第2章线性表
1．选择题
babadbcabdcddac2．算法设计题
（6）设计一个算法，通过一趟遍历在单链表中确定值最大的结点。

elemtypemax(linklistl){
if(l-next==null)returnnull;
pmax=l-next;//假定第一个结点中数据具有最大值p=l-next-next;
while(p!=null){//如果下一个结点存在if(p-datapmax-data)

pmax=p;p=p-next;}
returnpmax-data;
（7）设计一个算法，通过遍历一趟，将链表中所有结点的链接方向

逆转，仍利用原表的存储空间。
voidinverse(linklistl){//逆置带头结点的单链表lp=l-next;l-

next=null;while(p){
q=p-next;//q指向*p的后继p-next=l-next;
l-next=p;//*p插入在头结点之后p=q;}
}
（10）已知长度为n的线性表a采用顺序存储结构，请写一时间复
杂度为o(n)、空间复杂度为o(1)的算法，该算法删除线性表中所有

值为item的数据元素。
[题目分析]在顺序存储的线性表上删除元素，通常要涉及到一系列
元素的移动（删第i个元素，第i+1至第n个元素要依次前移）。本
题要求删除线性表中所有值为item的数据元素，并未要求元素间的
相对位置不变。因此可以考虑设头尾两个指针（i=1，j=n），从两端
向中间移动，凡遇到值item的数据元素时，直接将右端元素左移至

值为item的数据元素位置。
elemtypea[]，intn）
∥a是有n个元素的一维数组，本算法删除a中所有值为item的元

素。{i=1；j=n；∥设置数组低、高端指针（下标）。while（ij）
{while（ija[i]!=item）i++；∥若值不为item，左移指针。
if（ij）while（ija[j]==item）j--；∥若右端元素值为item，指针

左移if（ij）a[i++]=a[j--]；}
[算法讨论]因元素只扫描一趟，算法时间复杂度为o（n）。删除元

素未使用其它辅助空间，最后线性表中的元素个数是j。
第3章栈和队列
1．选择题
ccdaadabcdddbcb2.算法设计题（2）回文是指正读反读均相同的
字符序列，如和“abdba”均是回文，但“good”不是回文。试
写一个算法判定给定的字符向量是否为回文。(提示：将一半字符入

栈)
根据提示，算法可设计为：//以下为顺序栈的存储结构定义
#definestacksize100//假定预分配的栈空间最多为100个元素
typedefchardatatype;//假定栈元素的数据类型为字符typedef

struct{
datatypedata[stacksize];inttop;}seqstack;
intishuiwen(char*t)
{//判断t字符向量是否为回文，若是，返回1，否则返回0seqstack

s;inti,len;chartemp;initstack(s);
len=strlen(t);//求向量长度
for(i=0;ilen/2;i++)//将一半字符入栈push(s,t[i]);

while(!emptystack(s))
{//每弹出一个字符与相应字符比较temp=pop(s);
if(temp!=s[i])return0;//不等则返回0elsei++;}
return1;//比较完毕均相等则返回1}
（7）假设以数组q[m]存放循环队列中的元素,同时设置一个标志
tag，以tag==0和tag==1来区别在队头指针(front)和队尾指针
(rear)相等时，队列状态为“空”还是“满”。试编写与此结构相应的插

入(enqueue)和删除(dlqueue)算法。
【解答】
循环队列类定义
#includeassert.h
templateclasstypeclassqueue{public:
item);typedequeue();typegetfront();
voidmakeempty(){front=rear=tag=0;}
//
//判队列空否
intisempty()const{returnfront==reartag==0;}private:
intrear,front,tag