item是什么意思m的用法读音典

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

案

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

选择题：ccbdca

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的数据元素位置。

voiddelete（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）回文是指正读反读均相同的

字符序列，如“abba”和“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:

queue(int=10);~queue(){delete[]q;}voidenqueue(type

item);typedequeue();typegetfront();

voidmakeempty(){front=rear=tag=0;}

//置空队列

//判队列空否

intisempty()const{returnfront==reartag==0;}private:

intrear,front,tag;type*q;

//队尾指针、队头指针和队满标志

//存放队列元素的数组

//循环队列的类定义

intisfull()const{returnfront==reartag==1;}//判队列满否

intm;}

//队列最大可容纳元素个数

构造函数

templateclasstype

queuetype::queue(intsz):rear(0),front(0),tag(0),m(sz){//

建立一个最大具有m个元素的空队列。q=newtype[m];assert

(q!=0);}

//创建队列空间

//断言:动态存储分配成功与否

插入函数

templateclasstype

voidqueuetype::enqueue(typeitem){}

assert(!isfull());rear=(rear+1)%m;q[rear]=item;tag

=1;

//判队列是否不满，满则出错处理

//队尾位置进1,队尾指针指示实际队尾位置//进队列

//标志改1，表示队列不空

删除函数

templateclasstype

typequeuetype::dequeue(){

assert(!isempty());front=(front+1)%m;tag=0;

returnq[front];

//判断队列是否不空，空则出错处理

//标志改0,表示栈不满//返回原队头元素的值

//队头位置进1,队头指针指示实际队头的前一位置

}

读取队头元素函数

templateclasstype春游湖阅读答案

typequeuetype::getfront(){}

assert(!isempty());

//判断队列是否不空，空则出错处理

//返回队头元素的值

returnq[(front+1)%m];

第4章串、数组和广义表

1．选择题

bbcabbbcbbabdcbc2.综合应用题

（1）已知模式串t=‘abcaabbabcab’写出用kmp法求得的每个字

符对应的next和nextval函数值。

模式串t的next和nextval值如下：

（3）数组a中，每个元素a[i,j]的长度均为32个二进位,行下标从-1

到9，列下标从1到11，从首地址s开始连续存放主存储器中，主

存储器字长为16位。求：

①存放该数组所需多少单元？

②存放数组第4列所有元素至少需多少单元？

③数组按行存放时，元素a[7,4]的起始地址是多少？④数组按列存

放时，元素a[4,7]的起始地址是多少？

每个元素32个二进制位，主存字长16位，故每个元素占2个字长，

行下标可平移至1到11。

（1）242（2）22（3）s+182（4）s+142

(4)请将香诗经采薇原文注音版 蕉banana用工具h()—head()，t()—tail()从l中取出。

l=(apple,(orange,(strawberry,(banana)),peach),pear)h（h（t

（h（t（h（t（l）））））））

（5）写一个算法统计在输入字符串中各个不同字符出现的频度并将

结果存入文件（字符串中的合法字符为a-z这26个字母和0-9这10

个数字）。

voidcount（）

//统计输入字符串中数字字符和字母字符的个数。｛inti，num[36]；

charch；

for（i＝0；i36；i++）num[i]＝０；//初始化while（（ch＝

getchar（））!=‘#’）//‘#’表示输入字符串结束。if（‘0’=ch=‘9’）

｛i=ch－48;num[i]++；｝//数字字符elseif（‘a’=ch=‘z’）

｛i=ch-65+10;num[i]++；｝//字母字符

for（i=0；i10；i++）//输出数字字符的个数printf（“数字％d的

个数＝％dn”，i，num[i]）；for（i＝10；i36；i++）//求出字母

字符的个数printf（“字母字符％c的个数＝％dn”，i＋55，

num[i]）；｝//算法结束。

第5章树和二叉树

1．选择题

addcaccbdcccacc

【篇二：数据结构习题集答案(c语言严版)】

所有能输入到计算机中并被计算机程序处理的符号的总称。

数据元素是数据的基本单位，在计算机程序中通常作为一个整体进

行考虑和处理。

数据对象是性质相同的数据元素的集合，是数据的一个子集。

数据结构是相互之间存在一种或多种特定关系的数据元素的集合。

存储结构是数据结构在计算机中的表示。

数据类型是一个值的集合和定义在这个值集上的一组操作的总称。

抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。

是对一般数据类型的扩展。

1.2解：抽象数据类型包含一般数据类型的概念，但含义比一般数据

类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接

提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象

数据类型通常由编程者定义，包括定义它所使用的数据和在这些数

据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分

时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储

结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供

良好的使用接口。

1.3解：

1.4解：adtcomplex{

数据对象：d={r,i|r,i为实数}数据关系：r={r,i}基本操作：

initcomplex(c,re,im)操作结果：构造一个复数c，其实部和虚部分

别为re和imdestroycmoplex(c)操作结果：销毁复数cget(c,k,e)

操作结果：用e返回复数c的第k元的值操作结果：改变复数c的

第k元的值为e操作结果：如果复数c的两个元素按升序排列，则

返回1，否则返回0操作结果：如果复数c的两个元素按降序排列，

则返回1，否则返回0操作结果：用e返回复数c的两个元素中值

较大的一个操作结果：用e返回复数c的两个元素中值较小的一个

put(c,k,e)isascending(c)isdescending(c)max(c,e)

min(c,e)}adtcomplex

数据对象：d={s,m|s,m为自然数，且m不为0}数据关系：

r={s,m}基本操作：

initrationalnumber(r,s,m)操作结果：构造一个有理数r，其分子

和分母分别为s和mdestroyrationalnumber(r)操作结果：销毁有

理数rget(r,k,e)操作结果：用e返回有理数r的第k元的值adt

rationalnumber{

put(r,k,e)操作结果：改变有理数r的第k元的值为e操作结果：若

有理数r的两个元素按升序排列，则返回1，否则返回0操作结果：

若有理数r的两个元素按降序排列，则返回1，否则返回0操作结果：

用e返回有理数r的两个元素中值较大的一个操作结果：用e返回

有理数r的两个元素中值较小的一个isascending(r)

isdescending(r)max(r,e)min(r,e)

}adtrationalnumber

1.6解：(1)exit常用于异常错误处理，它可以强行中断程序的执行，

返回操作系统。

(2)以函数的返回值判断正确与否常用于子程序的测试，便于实现程

序的局部控制。

(3)用整型函数进行错误处理的优点是可以给出错误类型，便于迅速

确定错误。

1.7解：(1)用scanf和printf直接进行输入输出的好处是形象、直

观，但缺点是需要对其进行格式控制，较为烦琐，如果出现错误，

则会引起整个系统的崩溃。

(2)通过函数的参数传递进行输入输出，便于实现信息的隐蔽，减少

出错的可能。

(3)通过全局变量的隐式传递进行输入输出最为方便，只需修改变量

的值即可，但过多的全局变量使程序的维护较为困难。

1.8解：(1)n-1

(2)n-1

(3)n-1(4)n+(n-1)+(n-2)+...+1=n(n?1)2

(5)1+(1+2)+(1+2+3)+...+(1+2+3+...+n)=

=1n?i?1ni(i?1)21n1n21n2(i?i)??i??i?i(i?1)?2?2i?12i?12i?1i?1

=111n(n?1)(2n?1)?n(n?1)?n(n?1)(2n?3)12412

(6)n(7)n?向下取整

n)count=log2n?2

n=40n=16(8)11001.9解：o(log21.11解：2nn?10式的部首 12?101210

则对于同样的循环次数n，在这个规模下，第二种算法所花费的代

价要大得多。故在这个规模下，第一种算法更适宜。

1.12解：(1)对(2)错(3)错(4)对(5)错

1.13解：n的增长趋势快。但在n较小的时候，50nlog22n的值较

大。

当n438时，n2?50nlog2n

1.14解：(1)g(n)快(2)g(n)快(3)f(n)快(4)f(n)快

1.16试写一算法，自大至小依次输出顺序读入的三个整数x，y和z

的值

解：

intmax3(intx,inty,intz)

{

}

1.17解：k0为阶数，n为数列的第n项

intfibonacci(intk,intn)

{

}

1.18解：

typedefenum{a,b,c,d,e}schoolname;

typedefenum{female,male}sextype;

typedefstruct{

charevent[3];//项目sextypesex;schoolnameschool;int

score;if(k1)exit(overflow);int*p,x;p=newint[k+1];if(!p)

exit(overflow);inti,j;for(i=0;ik+1;i++){}for(i=k+1;in+1;i++){}

returnp[k];x=p[0];for(j=0;jk;j++)p[j]=p[j+1];p[k]=2*p[k-1]-x;

if(ik-1)p[i]=0;elsep[i]=1;if(xy)if(xz)returnx;elsereturnz;

if(yz)returny;elsereturnz;else

}component;

typedefstruct{

intmalesum;//男团总分intfemalesum;//女团总分inttotalsum;

//团体总分

}sum;

sumsumscore(schoolnamesn,componenta[],intn)

{

}

1.19解：

#includeiostream.h

#includestdlib.h

#definemaxint65535

#definearrsize100

intfun(inti);

intmain()

{

}

1.20解：

#includeiostream.h

#,k;inta[arrsize];coutenterk:;cink;

if(karrsize-1)exit(0);for(i=0;i=k;i++){}for(i=0;i=k;i++){}return0;

if(a[i]maxint)exit(0);elsecouta[i];if(i==0)a[i]=1;else{}

if(2*i*a[i-1]maxint)exit(0);elsea[i]=2*i*a[i-1];sumtemp;

m=0;sum=0;um=0;inti;

for(i=0;in;i++){}

um=m+sum;returntemp;

if(a[i].school==sn){}if(a[i].sex==male)

m+=a[i].score;if(a[i].sex==female)

sum+=a[i].score;

#definen10

doublepolynomail(inta[],inti,doublex,intn);

intmain()

{

doublex;

}

doublepolynomail(inta[],inti,doublex,intn)

{

}

本算法的时间复杂度为o(n)。

第2章线性表

2.1描述以下三个概念的区别：头指针，头结点，首元结点（第一个

元素结点）。

解：头指针是指向链表中第一个结点的指针。首元结点是指链表中

存储第一个数据元素的结点。头结点是在首元结点之前附设的一个

结点，该结点不存储数据元素，其指针域指向首元结点，其作用主

要是为了方便对链表的操作。它可以对空表、非空表以及首元结点

的操作进行统一处理。

2.2填空题。

解：(1)在顺序表中插入或删除一个元素，需要平均移动表中一半元

素，具体移动的元素个数与元素在表中的位if(i0)returna[n-

i]+polynomail(a,i-1,x,n)*x;elsereturna[n];intn,i;inta[n];cout

输入变量的值x:;cinx;cout输入多项式的阶次n:;cinn;if(nn-1)

exit(0);cout输入多项式的系数a[0]--a[n]:;for(i=0;i=n;i++)cina[i];

coutthepolynomailvalueispolynomail(a,n,x,n)endl;return0;

置有关。

(2)顺序表中逻辑上相邻的元素的物理位置必定紧邻。单链表中逻辑

上相邻的元素的物理位置不一定紧邻。

(3)在单链表中，除了首元结点外，任一结点的存储位置由其前驱结

点的链域的值指示。

(4)在单链表中设置头结点的作用是插入和删除首元结点时不用进行

特殊处理。

2.3在什么情况下用顺序表比链表好？

解：当线性表的数据元素在物理位置上是连续存储的时候，用顺序

表比用链表好，其特点是可以进行随机存取。

2.4解：

【篇三：数据结构c++版课后习题解析】

.........................................................................................................1

1.1本章导

学.......................................................................................................

................1

1.2习题解

析.......................................................................................................

................2

第2章线性

表.......................................................................................................

....................8

2.2习题解

析.......................................................................................................

................9

第3章栈和队

列.......................................................................................................

............17

3.1本章导

学.......................................................................................................

..............17

3.2习题解

析.......................................................................................................

..............18

第4章字符串和多维数

组...................................................................................................

24

4.1本章导

学.......................................................................................................

..............24

4.2习题解

析.......................................................................................................

..............25

第5章树和二叉

树.......................................................................................................

..........30

5.1本章导

学.......................................................................................................

..............30

5.2习题解

析.......................................................................................................

..............31

第6章

图.......................................................................................................

..........................40

6.1本章导

学.............................覆巢之下安有完卵的下一句 ..........................................................................

...............40

6.2习题解

析.......................................................................................................

...............41

第7章查找技

术.......................................................................................................

..............53

7.1本章导

学.......................................................................................................

...............53

7.2习题解

析.......................................................................................................

...............54

第8章排序技

术.......................................................................................................

..............63

8.1本章导

学.......................................................................................................

...............63

8.2习题解

析.......................................................................................................

...............64

第9章索引技

术.......................................................................................................

..............74

9.1本章导

学...........................................................................................描写秋天的诗句 ............

...............74

9.2习题解

析.......................................................................................................

...............74

第1章绪论

1.1本章导学

1.知识结构图

本章的知识结构如图1-1所示，其中第二层的椭圆代表本章的学习

主线。

图1-1知识结构图

2.学习要点

对本章的学习要从两条主线出发，一条主线是数据结构，包括数据

结构的相关概念及含义，另一条主线是算法，包括算法的相关概念、

描述方法以及时间复杂度的分析方法。

在学习数据结构时要抓住两个方面：逻辑结构和存储结构，并注意

把握二者之间的关系。在学习算法时，要以算法的概念和特性为基

本点，并在以后的学习中注意提高算法设计的能力。对于算法时间

性能的分析，要将注意力集中在增长率上，即基本语句执行次数的

数量级，在设计算法时，养成分析算法时间性能的习惯，进而有效

地改进算法的效率。

1.2习题解析

1.填空

（1）（）是数据的基本单位，在计算机程序中通常作为一个整体进

行考虑和处理。

【解答】数据元素

（2）（）是数据的最小单位，（）是讨论数据结构时涉及的最小数

据单位。

【解答】数据项，数据元素

【分析】数据结构指的是数据元素以及数据元素之间的关系。

（3）从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。

【解答】集合，线性结构，树结构、图结构

（4）数据的存储结构主要有（）和（）两种基本方法，不论哪种

存储结构，都要存储两方面的内容：（）和（）。

【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间

的关系

（5）算法具有五个特性，分别是（）、（）、（）、（）、

（）。

【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，

可行性

（6）算法的描述方法通常有（）、（）、（）和（）四种，其中，

（）被称为算法语言。

【解答】自然语言，程序设计语言，流程图，伪代码，伪代码

（7）在一般情况下，一个算法的时间复杂度是（）的函数。

【解答】问题规模

（8）设待处理问题的规模为n，若一个算法的时间复杂度为一个常

数，则表示成数量级的形式为（），若为2n*log25n+8n，则表示

成数量级的形式为（）。

【分析】用大o记号表示算法的时间复杂度，需要将低次幂去掉，

将最高次幂的系数去掉。

2.选择题

（1）顺序存储结构中数据元素之间的逻辑关系是由（）表示的，

链接存储结构中的数据元素之间的逻辑关系是由（）表示的。

a线性结构b非线性结构c存储位置d指针

【解答】c，d

【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，

其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储

结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系

由结点中的指针表示。

（2）假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子

女可以继承父亲或母亲的遗产；子女间不能相互继承遗产。则表示

该遗产继承关系的最合适的数据结构应该是（）。

a树b图c线性表d集合

【解答】b

【分析】将丈夫、妻子和子女分别作为数据元素，根据继承关系画

出逻辑结构图如图1-2

所示。

图1-2遗产继承逻辑结构图

（3）计算机所处理的数据一般具有某种内在联系，这是指（）。

a数据和数据之间存在某种关系b元素和元素之间存在某种关系

c元素内部具有某种结构d数据项和数据项之间存在某种关系

【解答】b

【分析】数据结构是指相互之间存在一定关系的数据元素的集合，

数据元素是讨论数据结构时涉及的最小数据单位，元素内部各数据

项一般不予考虑。

（4）对于数据结构的描述，下列说法中不正确的是（）。

a相同的逻辑结构对应的存储结构也必相同

b数据结构由逻辑结构、存储结构和基本操作三方面组成

c对数据结构基本操作的实现与存储结构有关

d数据的存储结构是数据的逻辑结构的机内实现

【解答】a

【分析】相同的逻辑结构可以用不同的存储结构实现，一般来说，

在不同的存储结构下基本操作的实现是不同的，例如线性表可以顺

序存储也可以链接存储，在顺序存储和链接存储结构下插入操作的

实现截然不同。

（5）可以用（）定义一个完整的数据结构。

a数据元素b数据对象c数据关系d抽象数据类型

【解答】d

【分析】抽象数据类型是一个数据结构以及定义在该结构上的一组

操作的总称。

（6）算法指的是（）。

a对特定问题求解步骤的一种描述，是指令的有限序列。

b计算机程序c解决问题的计算方法d数据处理

【解答】a

【分析】计算机程序是对算法的具体实现；简单地说，算法是解决

问题的方法；数据处理是通过算法完成的。所以，只有a是算法的

准确定义。

（7）下面（）不是算法所必须具备的特性。

a有穷性b确切性c高效性d可行性

【解答】c

【分析】高效性是好算法应具备的特性。

（8）算法分析的目的是（），算法分析的两个主要方面是（）。

a找出数据结构的合理性b研究算法中输入和输出的关系

c分析算法的效率以求改进d分析算法的易读性和文档性