第1章 概 论 习题参考解答
一、填空题
1、数据的逻辑结构是数据元素之间的逻辑关系，通常有下列4类：（ ）、（ ）、（ ）、（ ）。
【答】 集合、线性结构、树型结构和图状结构。
2、数据的存储结构是数据在计算机存储器里的表示，主要有4种基本存储方法：（ ）、（ ）、（ ）、（ ）。
【答】 顺序存储方法、链接存储方法、索引存储方法和散列存储方法。
二、选择题
1、一个算法必须在执行有穷步之后结束，这是算法的（ ）。
（A）正确性 （B）有穷性
（C）确定性 （D）可行性
【答】 B。
2、算法的每一步，必须有确切的定义。也就是说，对于每步需要执行的动作必须严格、清楚地给出规定。这是算法的（ ）。
（A）正确性 （B）有穷性
（C）确定性 （D）可行性
【答】 C。
3、算法原则上都是能够由机器或人完成的。整个算法好像是一个解决问题的“工作序列”，其中的每一步都是我们力所能及的一个动作。这是算法的（ ）。
（A）正确性 （B）有穷性
（C）确定性 （D）可行性
【答】 D。
三、简答题
1、 算法与程序有何异同？
【答】 尽管算法的含义与程序非常相似，但两者还是有区别的。首先，一个程序不一定满足有穷性，因此它不一定是算法。例如，系统程序中的操作系统，只要整个系统不遭受破坏，它就永远不会停止，即使没有作业要处理，它仍处于等待循环中，以待一个新作业的进入。因此操作系统就不是一个算法。其次，程序中的指令必须是计算机可以执行的，而算法中的指令却无此限止。如果一个算法采用机器可执行的语言来书写，那么它就是一个程序。
数据结构（本）课程导学
一、课程的性质、内容与任务
“数据结构（本）”是中央广播电视大学计算机科学与技术本科专业（专科起点）的统设必修、学位课程。本课程4学分，72学时，其中实验24学时，开设一学期。
“数据结构（本）”是计算机科学与技术专业的一门重要专业基础课。主要介绍如何合理地组织数据、有效地存储和处理数据，正确地设计算法以及对算法进行分析和评价。课程的主要内容包括：数据结构和算法的基本概念、线性表、栈和队列、串、数组和广义表、树和二叉树、图、查找和排序。
通过本课程的学习，使学生较深入地理解数据的逻辑结构和物理结构，掌握有关算法和基本的程序设计技能，能编制高效且有一定难度的程序，为学习后续课程奠定基础。
课程以C语言作为数据结构和算法的描述工具。教学环节包括理论教学和实验，教学中注重基础，突出应用，强化数据结构基本知识和程序设计基本能力的双基训练。
二、为什么要学习数据结构
在计算机发展的初期，人们使用计算机的目的主要是处理数值计算问题。当我们使用计算机来解决一个具体问题时，一般需要经过下列几个步骤：首先要从该具体问题抽象出一个适当的数学模型，然后设计或选择一个解此数学模型的算法，最后编出程序进行调试、测试，直至得到最终的解答。例如，预报人口增长情况的数学模型为微分方程。然而，更多的非数值计算问题无法用数学方程加以描述。
由于当时所涉及的运算对象是简单的整型、实型或布尔类型数据，所以程序设计者的主要精力是集中于程序设计的技巧上，而无须重视数据结构。随着计算机应用领域的扩大和软、硬件的发展，非数值计算问题越来越显得重要。据统计，当今处理非数值计算性问题占用了90%以上的机器时间。这类问题涉及到的数据结构更为复杂，数据元素之间的相互关系一般无法用数学方程式加以描述。因此，解决这类问题的关键不再是数学分析和计算方法，而是要设计出合适的数据结构，才能有效地解决问题。例如 学生信息检索系统。当我们需要查找某个学生的有关情况的时候；或者想查询某个专业或年级的学生的有关情况的时候，只要我们建立了相关的数据结构，按照某种算法编写了相关程序，就可以实现计算机自动检索。由此，可以在学生信息检索系统中建立一张按学号顺序排列的学生信息表和分别按姓名、专业、年级顺序排列的索引表，这四张表构成的文件便是学生信息检索的数学模型，计算机的主要操作便是按照某个特定要求（如给定姓名）对学生信息文件进行查询。诸如此类的还有电话自动查号系统、考试查分系统、仓库库存管理系统等。
第 4 章 广义线性表——多维数组和广义表
2005-07-14
第 4 章 广义线性表——多维数组和广义表
课后习题讲解
1. 填空
⑴ 数组通常只有两种运算：（ ）和（ ），这决定了数组通常采用（ ）结构来实现存储。
【解答】存取，修改，顺序存储
【分析】数组是一个具有固定格式和数量的数据集合，在数组上一般不能做插入、删除元素的操作。除了初始化和销毁之外，在数组中通常只有存取和修改两种操作。
⑵ 二维数组A中行下标从10到20，列下标从5到10，按行优先存储，每个元素占4个存储单元，A[10][5]的存储地址是1000，则元素A[15][10]的存储地址是（ ）。
【解答】1140
【分析】数组A中每行共有6个元素，元素A[15][10]的前面共存储了(15-10)×6+5个元素，每个元素占4个存储单元，所以，其存储地址是1000+140=1140。
⑶ 设有一个10阶的对称矩阵A采用压缩存储，A[0][0]为第一个元素，其存储地址为d，每个元素占1个存储单元，则元素A[8][5]的存储地址为（ ）。
【解答】d+41
【分析】元素A[8][5]的前面共存储了(1+2+…+8)+5=41个元素。
⑷ 稀疏矩阵一般压缩存储方法有两种，分别是（ ）和（ ）。
【解答】三元组顺序表，十字链表
⑸ 广义表((a), (((b),c)),(d))的长度是（ ），深度是（ ），表头是（ ），表尾是（ ）。
【解答】3，4，(a)，((((b),c)),(d))
⑹ 已知广义表LS=(a，(b，c，d)，e)，用Head和Tail函数取出LS中原子b的运算是（ ）。
【解答】Head(Head(Tail(LS)))
2. 选择题
⑴ 二维数组A的每个元素是由6个字符组成的串，行下标的范围从0~8，列下标的范围是从0~9，则存放A至少需要（ ）个字节，A的第8列和第5行共占（ ）个字节，若A按行优先方式存储，元素A[8][5]的起始地址与当A按列优先方式存储时的（ ）元素的起始地址一致。
一、选择
1、 设输入序列为1，2，3，4。借助一个栈可以得到的输出序列是（ ）。
A. 1，3，4，2 B. 3，1，4，2 C. 4，3，1，2 D. 4，1，2，3
2、 一个队列的入队序列是1，2，3，4，则队列的出队序列是（ ）。
A. 1，3，4，2 B. 3，1，4，2 C. 4，3，1，2 D. 1，2，3，4
3、 栈和队列都是（ ）。
A. 顺序存储的线性表 B. 链式存储的线性表
C. 限制存储点的线性表 D. 限制存储点的非线性结构
4、 队列通常采用两种存储结构是( )
A.顺序存储结构和链表存储结构 B.和索引方式
C.链表存储结构和散列方式 D.线性存储结构和非线性存储结构
5、 设循环队列用数组A[n]存储，头尾指针分别为front和rear。求解当前队列中元素个数的公式是 ( )
A .rear-front B. front-rear
C.n-(front-rear) D. (n+rear-front)%n
二、填空
1、 设有一个链栈，其中各结点中有data和next两字段 ，栈顶指针为Ls（≠NULL）， 则执行退栈的基本操作是____________________。则S指针所指向的结点入栈操作的语句为：S->next=Ｌs；Ｌs=______________。
2、 设数组Ｂ[5][6]的元素占４个单元。从首地址1000开始将其按行优先方式存储，则元素Ｂ[3][2]的地址为______________。
3、 在具有n个单元的循环队列中，队满时共有______________个元素。
4、 循环队列判满的条件是______________________。
