大连理工大学数据结构 课后题答案(1-3章).pdfVIP

以家为家，以乡为乡，以国为国，以天下为天下。——《管子》

数据结构部分课后习题答案(1-3)

第一章

1.1

数据的逻辑结构是从具体问题中抽象出来的数学模型，体现了事物的组成和

事物之间的逻辑关系。

数据的存储结构主要用来解决各种逻辑结构在计算机中物理存储表示的问

题。

1.2

事前分析和事后统计

事前分析：

优点，程序不必运行，所得结果只依赖于算法本身

缺点，不够精确

事后统计：

优点，精确

缺点，必须运行程序，所得结果依赖于硬件、环境等因素

1.3

voidfunc(intn)

{

inti=1,k=100;

while(in)

{

k++;i+=2;

}

}

考虑赋值、运算操作执行的次数

第3行赋值2次

第6行赋值执行n次，加法执行n次

所以，总共2n+2次操作，算法复杂度为O(n)

1.4

y=y+i*j执行次数：

1.5

以家为家，以乡为乡，以国为国，以天下为天下。——《管子》

第二章

2.9

内存中一片连续空间（不妨假设地址从1到m）提供给两个栈S1和S2使用，怎

样分配这部分存储空间，使得对任一个栈，仅当这部分空间全满时才发生上溢。

答：S1和S2共享内存中一片连续空间（地址1到m），可以将S1和S2的栈

底设在两端，两栈顶向共享空间的中心延伸，仅当两栈顶指针相邻（两栈顶指针

值之差的绝对值等于1）时，判断为栈满，当一个栈顶指针为0，另一个栈顶指

针m+1时为两栈均空。

2.10

线性表是数据项组成的一种有限且有序的序列，各元素之间呈线性关系。从

逻辑结构来说，栈和队列与线性表相同，都是典型的线性结构。与线性表不同的

是，栈和队列的操作特殊，受到一定的限制，仅允许在线性表的一端或两端进行。

栈是限定仅在一端进行插入删除的线性表，无论插入、删除还是读取都在一端进

行，按后进先出的原则。队列的元素只能从一端插入，从另一端删除，按先进先

出的原则进行数据的存取。

2.11

共有132种合法序列。

235641序列可以。

154623序列不可以。

1

对于每一个数来说，必须进栈一次、出栈一次。我们把进栈设为状态‘’，

出栈设为状态‘0’。n个数的所有状态对应n个1和n个0组成的2n位二进制

1nb

数。由于等待入栈的操作数按照‥的顺序排列、入栈的操作数大于等于出

栈的操作数a(a≤b)，因此输出序列的总数目=由左而右扫描由n个1和n个0组

2n10

成的位二进制数，的累计数不小于的累计数的方案种数。

在2n位二进制数中填入n个1的方案数为c(2n,n),不填1的其余n位自动填0。