第1章习题答案

1 简述下列概念：数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、线性结构、非线性结构。

● 数据：是对信息的一种符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。

● 数据元素：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

● 数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。通常数据类型可以看作是程序设计语言中已实现的数据结构。

● 数据结构：是相互之间存在一种或多种特定关系的数据元素的集合，一般包括三个方面的内容:数据的逻辑结构、存储结构和数据的运算。

● 逻辑结构：只抽象反映数据元素的逻辑关系。

● 存储结构：数据的逻辑结构在计算机存储器中的实现。

● 线性结构：数据逻辑结构中的一类。它的特征是若结构为非空集，则该结构有且只有一个开始结点和一个终端结点，并且所有结点都有且只有一个直接前趋和一个直接后继。线性表就是一个典型的线性结构。栈、队列、串等都是线性结构。

● 非线性结构：数据逻辑结构中的另一大类，它的逻辑特征是一个结点可能有多个直接前趋和直接后继。数组、广义表、树和图等数据结构都是非线性结构。

2．设n为正整数，利用大\记号，将下列程序段的执行时间表示为n的函数。 (1) i=1; k=0; while(i

{ k=k+10*i;i++; } 解析：

i=1; //1 k=0; //1

while(i

由以上列出的各语句的频度，可得该程序段的时间消耗： T(n)=1+1+n+(n-1)+(n-1)=3n 可表示为T(n)=O(n)

(2) i=0; k=0; do{

k=k+10*i; i++; }

while(i

k=k+10*i; //n i++; //n }

while(i

由以上列出的各语句的频度，可得该程序段的时间消耗： T(n)=1+1+n+n+n+n=4n+2 可表示为T(n)=O(n)

(3) i=1; j=0;

while(i+j<=n) {

if (i>j) j++; else i++; } 解析：

通过分析以上程序段，可将i+j看成一个控制循环次数的变量，且每执行一次循环，i+j的值加1。该程序段的主要时间消耗是while循环，而while循环共做了n次，所以该程序段的执行时间为： T(n)=O(n)

补充：

在下面的程序段中，对ｘ的赋值语句的频度为______（表示为n的函数） FOR i：＝１ TO n DO FOR j：＝１ TO i DO

FOR k：＝1 TO j DO

ｘ：＝ｘ＋1；

3

1+（1+2）+（1+2+3）+…+（1+2+…+n）=n(n+1)(n+2)/6 O(n)

3．按增长率由小至大的顺序排列下列各函数：

2100, (3/2)n，(2/3)n， nn ,n0.5 , n! ，2n ，lgn , nlgn, n(3/2) 解答：

常见的时间复杂度按数量级递增排列,依次为:常数阶0(1)、对数阶0(log2n)、线性阶0(n)、线性对数阶0(nlog2n)、平方阶0(n2)、立方阶0(n3)、k次方阶0(nk)、指数阶0(2n)。 先将题中的函数分成如下几类： 常数阶：2100 对数阶：lgn

K次方阶：n0.5、n(3/2)

指数阶 (按指数由小到大排)：nlgn、(3/2)n、2n、 n!、 nn

注意：(2/3)^n由于底数小于1，所以是一个递减函数，其数量级应小于常数阶。 根据以上分析按增长率由小至大的顺序可排列如下：

(2/3)n < 2100 < lgn < n0.5 < n(3/2) < nlgn < (3/2)n < 2n < n! < nn .

第2章习题答案

1. 试比较顺序存储结构和链式存储结构的优缺点. 顺序存储结构优点：

（1）无须为表示结点间的逻辑关系而增加额外的存储空间。 （2）可以方便地随机存储表中的任一结点。 顺序存储结构缺点：

（1）插入和删除平均须移动一半结点。 （2）存储分配只能预先进行（静态） 过大 浪费 过小 溢出

链式存储结构的优缺点与上述恰好相反（学生自己补充）

2. 填空题

(1)在顺序表中插入或删除一个元素，需要平均移动________元素，具体移动的元素个数与______有关。

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

(3)在单链表中，除了首元结点外，任一结点的存储位置由________指示。 (4)在单链表设置头结点的作用是________________。

(1)约表长的一半，该元素在线性表中的位置； (2)必须，不必；

(3)其直接前驱结点的链域的值；

(4)插入和删除首元素时不必对头指针进行特殊处理。

3.顺序表类型定义如下： typedef struct {

ElemType *elem; //存储空间基址 int length; //当前长度

int listsize; //当前分配的存储容量（以sizeof(ElemType)为单位 }SqList ;

试写一算法, 实现顺序表的就地逆置, 即利用原表的存储空间将线性表( a1 , a2?, an ) 逆置为( an , an - 1 , ?, a1 ) 。

void reverse(SqList &A)//顺序表的就地逆置 {

for(i=1,j=A.length;i