《数据结构基础教程》习题解答（新）
第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 (i=0; i - 1 - 习题解答 三、问答 1．中国百家姓中的赵、钱、孙、李、周、吴、郑、王……等姓氏数据之间，是一种什么样的邻接关系，为什么？ 答：是一种线性关系，因为这些姓氏之间符合关系的“有头有尾，顺序排列”的特点。 2．什么是数据结点？什么是存储结点？它们间有什么关系？ 答：数据结点即是数据集合中的一个数据元素，存储结点是存放数据结点的内存单位。在存储结点里，不仅要存放数据结点的内容，还要（显式或隐式地）存放数据结点间的逻辑关系。 3．为什么说链式存储既提高了存储的利用率，又降低了存储的利用率？ 答：由于链式存储是通过指针来体现数据元素之间的逻辑关系的，因此，存储结点可以不占用存储器的连续存储区。从这个意义上说，链式存储能够充分利用存储器中小的存储区，因此提高了存储器的利用率。另一方面，链式存储中的存储结点不仅要存放数据元素，还要占用适当的存储区来存放指针，这是一种额外的存储开销。从这个意义上说，链式存储降低了存储器的利用率。 4．列举几个数据之间具有树型结构的实际例子。 答：学校各级管理之间，是一种分支层次结构；一本书的书目，是一种分支层次结构。 5．判断如下除法过程是否是一个算法，为什么： （1）开始； （2）给变量m赋初值5，给变量n赋初值0； （3）m=m/n； （4）输出m； （5）结束。 答：因为0不能为除数，本题第（3）步不具有有效性，所以它不是一个算法。但如果n的初值不为0，则是一个正确的算法。 四、应用 1．用类C语言中的do-while语句，描述输出整数1、2、3、……、9、10的过程。 答：算法编写如下。 void num () { i=1; 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 (x>=0) - 2 - 习题解答 printf (“输入的是正数”); else printf (“输入的是负数”); } 3．分析算法段中标有记号“#1”和“#2”的基本操作的执行次数： for ( i=0; i #1 y=1; for (k=0; k 答：标有记号“#1”的基本操作的执行次数是：n2；标有记号“#2”的基本操作的执行次数是：n3。 4．给出下面3个算法段的时间复杂度： （1）x++； （2）for (j=1; j printf (“j=%”, j); for (k=j; k<=n; k++) x++; } 答：（1）的时间复杂度为O(1)； （2）的时间复杂度O(n)； （3）中“printf (“j=%”, j);”执行次数的数量级为O(n)，“x++;”执行次数是： n+(n-1)+(n-2)+……+2+1 = n(n+1)/2 其数量级为O(n2)，因此整个算法段的时间复杂度应该是O(n2)。 第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所指结点的后面插入一个值 - 3 - 习题解答 为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的存储地址是 m+(n-1)*w 。 10．当线性表的数据元素个数基本稳定、很少进行插入和删除操作，但却要求以最快的速度存取表中的元素时，我们应该对该表采用 顺序 存储结构。 二、选择 1．下面，对非空线性表特点的论述， C 是正确的。 A．所有结点有且只有一个直接前驱 B．所有结点有且只有一个直接后继 C．每个结点至多只有一个直接前驱，至多只有一个直接后继 D．结点间是按照1对多的邻接关系来维系其逻辑关系的 2．一般单链表Lk_h为空的判定条件是 A 。 A．Lk_h == NULL B．Lk_h->Next == NULL C．Lk_h->Next == Lk_h D．Lk_h != NULL 3．带表头结点的单链表Lk_h为空的判定条件是 B 。 A．Lk_h == NULL B．Lk_h->Next == NULL C．Lk_h->Next == Lk_h D．Lk_h != NULL 4．往一个顺序表的任一结点前插入一个新数据结点时，平均而言，需要移动 B个结点。 A．n B．n/2 C．n+1 D．(n+1)/2 5．在一个单链表中，已知qtr所指结点是ptr所指结点的直接前驱。现要在qtr所指结点和ptr所指结点之间插入一个rtr所指的结点，要执行的操作应该是 C 。 A．rtr->Next = ptr->Next; ptr->Next = rtr; B．ptr->Next = rtr->Next; C．qtr->Next = rtr; rtr->Next = ptr; D．ptr->Next = rtr; rtr->Next = qtr->Next; 6．在一个单链表中，若现在要删除ptr指针所指结点的直接后继结点，则需要执行的操作是 A 。 A．ptr->Next = ptr->Next->Next ; B．ptr = ptr->Next; ptr->Next = ptr->Next->Next ; C．ptr = ptr->Next->Next ; D．ptr->Next ptr ; 7．在长度为n的顺序表中，往其第i个元素（1≤i≤n）之前插入一个新的元素时，需要往后移动 B 个元素。 A．n-i B．n-i+1 C．n-i-1 D．i 8．在长度为n的顺序表中，删除第i个元素（1≤i≤n）时，需要往前移动 A 个元素。 A．n-i B．n-i+1 C．n-i-1 D．i 9．设tail是指向一个非空带表头结点的循环单链表的尾指针。那么，删除链表起始结点的操作应该是 D 。 A．ptr = tail ; B．tail = tail->Next ; - 4 - 习题解答 tail = tail->Next ; free (tail) ; free (ptr); C．tail = tail->Next->Next ; D．ptr = tail->Next->Next ; Free (tail); tail->Next->Next = ptr->Next ; Free (ptr); free (ptr); 10．在单链表中，如果指针ptr所指结点不是链表的尾结点，那么在ptr之后插入由指针qtr所指结点的操作应该是 B 。 A．qtr->Next = ptr ; B．qtr->Next = ptr->Next ; ptr->Next = qtr ; ptr->Next = qtr ; C．qtr->Next = ptr->Next ; D．ptr->Next = qtr ; ptr = qtr ; qtr->Next = ptr ; 三、问答 1．试问，如下的线性表： L = (29，25，21，17，13，11，7，5，3，1) 是有序线性表还是无序线性表？ 答：L是一个有序线性表。 2．线性表L第i个存储结点ai的起始地址LOC（ai）可以通过下面的公式计算得到： LOC（ai）= LOC（ai-1）+k 其中k表示存储结点的长度。这个公式对吗？为什么？ 答：这个公式是对的，因为第i个存储结点ai的起始地址LOC（ai），实际上就是等于第i-1个存储结点ai-1的起始地址LOC（ai-1）加上一个存储结点的长度k得到。 3．试说明创建顺序表算法Create_Sq ()中，Sq_max和Sq_num的不同之处。 答：Sq_max代表的是顺序表的最大长度，也就是它最多可以容纳下多少个数据元素，顺序表创建后，Sq_max是一个保持不变的常量；Sq_num代表的是顺序表内当前拥有的数据元素个数，在顺序表创建后，随着对数据元素进行的插入、删除操作，Sq_num将会不断地发生变化。 4．如何判断一个顺序表是否为空？ 答：只需判定Sq_num的当前值是多少，如果Sq_num为0，则表示顺序表Sq为空，否则表示该顺序表里有数据元素存在。 5．在算法2-3里，操作“Sq_num=Sq_num -1”的作用是什么？没有它行吗？ 答：该操作是非常重要的，因为顺序表里当前拥有的元素个数是通过Sq_num来记录的，删除了一个元素，Sq_num必须减1，这样才能正确反映出删除后表中元素的个数。所以，没有这个操作是不行的。 6．在算法2-9里，如果现在是把一个结点插入到单链表尾结点的后面。按照算法的描述，能够保证插入后最后一个结点的Next域为“Λ”吗？ 答：能够。因为原来ptr->Next里是“Λ”，做了第1步操作： qtr->Next = ptr->Next ; 后，就是把插入结点的Next域置为“Λ”。 7．在一个单链表中，为了删除指针ptr所指的结点，有人编写了下面的操作序列。读懂并加以理解。试问，编写者能够达到目的吗？其思想是什么？ x = ptr->Data ; qtr = ptr->Next ; ptr->Data = ptr->Next->Data ; - 5 -