数据结构基础教程习题及解答

精品文档---下载后可任意编辑 第1章习题解答 一、填空 1．数据是指所有能够输入到计算机中被计算机加工、处理的 符号 的集合。 2．可以把计算机处理的数据，笼统地分成 数值 型和 非数值 型两大类。 3．数据的逻辑结构就是指数据间的 邻接关系 。 4．数据是由一个个 数据元素 集合而成的。 5．数据项是数据元素中 不可再分割 的最小标识单位，通常不具备完整、确定的实际意义，只是反映数据元素某一方面的属性。 6．数据是以 数据元素 为单位存放在内存的，分配给它的内存区域称为 存储结点 。 7．每个数据元素都具有 完整 、 确定 的实际意义，是数据加工处理的对象。 8．假如两个数据结点之间有着逻辑上的某种关系，那么就称这两个结点是 邻接 的。 9．在一个存储结点里，除了要有数据本身的内容外，还要有体现 数据间邻接关系 的内容。 10．从整体上看，数据在存储器内有两种存放的方式一是集中存放 在一个连续的 内存存储区中；一是利用存储器中的零星区域， 分散地存放在 内存的各个地方。 11．在有些书里，数据的“存储结构”也称为数据的“ 物理结构 ”。 12．“基本操作”是指算法中那种所需时间与操作数的具体取值 无关 的操作。 二、选择 1．在常见的数据处理中， B 是最基本的处理。 A．删除B．查找C．读取D．插入 2．下面给出的名称中， A 不是数据元素的同义词。 A．字段B．结点C．顶点D．记录 3． D 是图状关系的特例。 A．只有线性关系B．只有树型关系 C．线性关系和树型关系都不D．线性关系和树型关系都 4．链式存储结构中，每个数据的存储结点里 D指向邻接存储结点的指针，用以反映数据间的逻辑关系。 A．只能有1个B．只能有2个C．只能有3个D．可以有多个 5．本书将采纳 C 来描述算法。 A．自然语言B．流程图（即框图）C．类C语言D．C语言 6．有下面的算法段 for i0; in; i k; 其时间复杂度为 B 。 A．O1B．OnC．Olog2nD．On2 三、问答 1．中国百家姓中的赵、钱、孙、李、周、吴、郑、王等姓氏数据之间，是一种什么样的邻接关系，为什么 答是一种线性关系，因为这些姓氏之间符合关系的“有头有尾，顺序排列”的特点。 2．什么是数据结点什么是存储结点它们间有什么关系 答数据结点即是数据集合中的一个数据元素，存储结点是存放数据结点的内存单位。在存储结点里，不仅要存放数据结点的内容，还要（显式或隐式地）存放数据结点间的逻辑关系。 3．为什么说链式存储既提高了存储的利用率，又降低了存储的利用率 答由于链式存储是通过指针来体现数据元素之间的逻辑关系的，因此，存储结点可以不占用存储器的连续存储区。从这个意义上说，链式存储能够充分利用存储器中小的存储区，因此提高了存储器的利用率。另一方面，链式存储中的存储结点不仅要存放数据元素，还要占用适当的存储区来存放指针，这是一种额外的存储开销。从这个意义上说，链式存储降低了存储器的利用率。 4．列举几个数据之间具有树型结构的实际例子。 答学校各级管理之间，是一种分支层次结构；一本书的书目，是一种分支层次结构。 5．推断如下除法过程是否是一个算法，为什么 （1）开始； （2）给变量m赋初值5，给变量n赋初值0； （3）mm/n； （4）输出m； （5）结束。 答因为0不能为除数，本题第（3）步不具有有效性，所以它不是一个算法。但假如n的初值不为0，则是一个正确的算法。 四、应用 1．用类C语言中的do-while语句，描述输出整数1、2、3、、9、10的过程。 答算法编写如下。 void num { i1; do { printf “i d\n”, i ; i i 1; } while i 10; } 2．用类C语言中的if-else语句，编写算法，描述当输入的数据大于等于0时，输出信息“输入的是正数”；当输入的数据小于0时，输出信息“输入的是负数”。 答算法编写如下。 void judge { scanf “d\n”, x; if x0 printf “输入的是正数”; else printf “输入的是负数”; } 3．分析算法段中标有记号“1”和“2”的基本操作的执行次数 for i0; in; i for j0; jn; j { 1 y1; for k0; kn; k 2 yy1; } 答标有记号“1”的基本操作的执行次数是n2；标有记号“2”的基本操作的执行次数是n3。 4．给出下面3个算法段的时间复杂度 （1）x； （2）for j1; jn; j x; （3）for j1; jn; j { printf “j”, j; for kj; kn; k x; } 答（1）的时间复杂度为O1； （2）的时间复杂度On； （3）中“printf “j”, j;”执行次数的数量级为On，“x;”执行次数是 nn-1n-221 nn1/2 其数量级为On2，因此整个算法段的时间复杂度应该是On2。 第2章习题解答 一、填空 1．当一组数据的逻辑结构呈线性关系时，在数据结构里就称其为 线性表 。 2．线性表中数据元素的个数n称为线性表的 长度 。 3．以顺序存储结构实现的线性表，被称为 顺序表 。 4．以链式存储结构实现的线性表，被称为 链表 。 5．不带表头结点的链表，是指该链表的表头指针直接指向该链表的 起始结点 。 6．在一个双链表中，已经由指针ptr指向需要删除的存储结点，则删除该结点所要执行的两条操作是①ptr-Prior-Next ptr-Next; ②ptr-Next-Prior ptr-Prior; 。 7．设tail是指向非空、带表头结点的循环单链表的表尾指针。那么，该链表起始结点的存储位置应该表示成 tail-Next-Next 。 8．在一个不带表头结点的非空单链表中，若要在指针qtr所指结点的后面插入一个值为x的结点，则需要执行下列操作 ptr malloc size; ptr-Data x ; ptr-Next qtr-Next ; qtr-Next ptr ; 9．顺序表Sq a1，a2，a3，，an（n≥1）中，每个数据元素需要占用w个存储单元。若m为元素a1的起始地址，那么元素an的存储地址是mn-1*w。 10．当线性表的数据元素个数基本稳定、很少进行插入和删除