罗文劼《数据结构与算法》第4版-第1章课后习题参考答案.pdf

第1章绪论

1.选择题

（1）C（2）B（3）C（4）D（5）B

2.判断题

（1）√（2）Ⅹ（3）Ⅹ（4）Ⅹ（5）√

3.简答题

（1）根据数据元素之间的不同逻辑关系，通常将其划分为哪几类结构？

【解答】常见的四种逻辑结构有：

①集合结构：数据元素间的关系是“属于同一个集合”。

②线性结构：数据元素之间存在着一对一的关系。

③树型结构：数据元素之间存在着一对多的关系。

④图型结构：数据元素之间存在着多对多的关系。

（2）请描述线性结构中数据元素与数据元素之间的关系特点？

【解答】线性结构的特点是数据元素之间是一种线性关系，数据元素“一个接一个的排列”。在线性

结构中，有且仅有一个元素被称为“第一个”，除第一个元素之外其他元素均有唯一一个“前驱”；有且

仅有一个元素被称为“最后一个”，除最后一个元素之外其他元素均有唯一一个“后继”。

（3）请描述树形结构中数据元素与数据元素之间的关系特点？

【解答】树形存储结构，就是数据元素与元素之间存在着一对多关系的数据结构。在树形存储结构中，

树的根节点没有前驱结点，其余的每个节点有且只有一个前驱结点，除叶子结点没有后续节点外，其他节

点的后续节点可以有一个或者多个。

（4）常用的存储结构有哪几种，各自的特点是什么？

【解答】常见的四种存储结构有：

①顺序存储：把逻辑上相邻的元素存储在物理位置相邻的存储单元中。顺序存储结构是一种最基本

的存储表示方法，通常借助于程序设计语言中的数组来实现。

②链接存储：对逻辑上相邻的元素不要求不要求物理位置相邻的存储单元，元素间的逻辑关系通过

附设的指针域来表示。

③索引存储：通过建立索引表存储结点信息的方法，其中索引表一般存储结点关键字和一个地点信

息，可通过该地址找到结点其它信息。

④散列存储：根据结点的关键字直接计算出该结点的存储地址的方法。

（5）简述算法和程序的区别。

【解答】一个算法若用程序设计语言来描述，则它就是一个程序。算法的含义与程序十分相似，但又

有区别。一个程序不一定满足有穷性。例如，操作系统，只要整个系统不遭破坏，它将永远不会停止，即

使没有作业需要处理，它仍处于动态等待中。因此，操作系统不是一个算法。另一方面，程序中的指令必

须是机器可执行的，而算法中的指令则无此限制。算法代表了对问题的解，而程序则是算法在计算机上的

特定的实现。

（6）试举一个数据结构的例子，叙述其逻辑结构、存储结构、运算这三方面的内容。

【解答】略。

（7）运算是数据结构的一个重要方面。试举例说明两个数据结构的逻辑结构和存储方式完全相同，只是

对于运算的定义不同，使得两个结构具有显著不同的特性。

【解答】比如顺序栈和循环队列，二者的逻辑结构都是线性结构，都采用顺序存储方式存储，但它们

运算不同，栈限定元素的插入和删除在栈顶进行，队列限定元素在队尾插入、在队首删除，从而它们是截

然不同的数据结构。

（8）分析下列程序段中带标号“#”语句的执行频度（n为正整数）。

1）j=1;k=0;

while(j=n-1)

{j++;

k+=j;//#1

}

【解答】n-1

2）i=0;s=0;n=100;

do{i++;

s+=10*i;//#2

}while(!(insn));

【解答】1

3）k=0;

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

for(j=i;jn;j++)

k++;//#3

【解答】n(n+1)/2

4）a=1;b=0;

while(a+b=n)

{if(ab)a++;//#4

elseb++;

}

【解答】n

5）x=91;y=100;

while(y0)

{if(x100){x-=10;y--;}//#5