《数据结构 第2版 习题答案 作者 宗大华 陈吉人 数据结构习题解答》由会员分享，可在线阅读，更多相关《数据结构 第2版 习题答案 作者 宗大华 陈吉人 数据结构习题解答（42页珍藏版）》请在金锄头文库上搜索。
1、习题解答数据结构习题解答第1章习题解答一、填空1数据是指所有能够输入到计算机中被计算机加工、处理的 符号 的集合。2可以把计算机处理的数据，笼统地分成 数值 型和 非数值 型两大类。3数据的逻辑结构就是指数据间的 邻接关系 。4数据是由一个个 数据元素 集合而成的。5数据项是数据元素中 不可再分割 的最小标识单位，通常不具备完整、确定的实际意义，只是反映数据元素某一方面的属性。6数据是以 数据元素 为单位存放在内存的，分配给它的内存区域称为 存储结点 。7每个数据元素都具有 完整 、 确定 的实际意义，是数据加工处理的对象。8如果两个数据结点之间有着逻辑上的某种关系，那么就称这两个结点是 邻接
2、 的。9在一个存储结点里，除了要有数据本身的内容外，还要有体现 数据间邻接关系 的内容。10从整体上看，数据在存储器内有两种存放的方式：一是集中存放 在一个连续的 内存存储区中；一是利用存储器中的零星区域， 分散地存放在 内存的各个地方。11在有些书里，数据的“存储结构”也称为数据的“ 物理结构 ”。12“基本操作”是指算法中那种所需时间与操作数的具体取值 无关 的操作。二、选择1在常见的数据处理中， B 是最基本的处理。A删除B查找C读取D插入2下面给出的名称中， A 不是数据元素的同义词。A字段B结点C顶点D记录3 D 是图状关系的特例。A只有线性关系B只有树型关系C线性关系和树型关系都不
3、D线性关系和树型关系都4链式存储结构中，每个数据的存储结点里 D指向邻接存储结点的指针，用以反映数据间的逻辑关系。A只能有1个 B只能有2个 C只能有3个 D可以有多个5本书将采用 C 来描述算法。A自然语言 B流程图（即框图） C类C语言 DC语言6有下面的算法段：for (i=0; in; i+) k+;其时间复杂度为 B 。AO(1) BO(n) CO(log2n) DO(n2)三、问答1中国百家姓中的赵、钱、孙、李、周、吴、郑、王等姓氏数据之间，是一种什么样的邻接关系，为什么？答：是一种线性关系，因为这些姓氏之间符合关系的“有头有尾，顺序排列”的特点。2什么是数据结点？什么是存储结点？
4、它们间有什么关系？答：数据结点即是数据集合中的一个数据元素，存储结点是存放数据结点的内存单位。在存储结点里，不仅要存放数据结点的内容，还要（显式或隐式地）存放数据结点间的逻辑关系。3为什么说链式存储既提高了存储的利用率，又降低了存储的利用率？答：由于链式存储是通过指针来体现数据元素之间的逻辑关系的，因此，存储结点可以不占用存储器的连续存储区。从这个意义上说，链式存储能够充分利用存储器中小的存储区，因此提高了存储器的利用率。另一方面，链式存储中的存储结点不仅要存放数据元素，还要占用适当的存储区来存放指针，这是一种额外的存储开销。从这个意义上说，链式存储降低了存储器的利用率。4列举几个数据之间具有
5、树型结构的实际例子。答：学校各级管理之间，是一种分支层次结构；一本书的书目，是一种分支层次结构。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 = %dn”, i ); i = i +1; while (i=0) printf (
6、“输入的是正数”); else printf (“输入的是负数”);3分析算法段中标有记号“#1”和“#2”的基本操作的执行次数：for ( i=0; in; i+) for (j=0; jn; j+) #1 y=1; for (k=0; kn; k+) #2 y=y+1;答：标有记号“#1”的基本操作的执行次数是：n2；标有记号“#2”的基本操作的执行次数是：n3。4给出下面3个算法段的时间复杂度：（1）x+；（2）for (j=1; jn; j+) x+;（3）for (j=1; j=n; j+) printf (“j=%”, j); for (k=j; kPrior-Next = ptr
7、-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)（n1）中，每个数据元素需要占用w个存储单元。若m为元素a1的起始地址，那么元素an的存储地址是 m+
8、(n-1)*w 。10当线性表的数据元素个数基本稳定、很少进行插入和删除操作，但却要求以最快的速度存取表中的元素时，我们应该对该表采用 顺序 存储结构。二、选择1下面，对非空线性表特点的论述， C 是正确的。A所有结点有且只有一个直接前驱B所有结点有且只有一个直接后继C每个结点至多只有一个直接前驱，至多只有一个直接后继D结点间是按照1对多的邻接关系来维系其逻辑关系的2一般单链表Lk_h为空的判定条件是 A 。ALk_h = NULLBLk_h-Next = NULLCLk_h-Next = Lk_hDLk_h != NULL3带表头结点的单链表Lk_h为空的判定条件是 B 。ALk_h = N
9、ULLBLk_h-Next = NULLCLk_h-Next = Lk_hDLk_h != NULL4往一个顺序表的任一结点前插入一个新数据结点时，平均而言，需要移动 B个结点。AnBn/2Cn+1D(n+1)/25在一个单链表中，已知qtr所指结点是ptr所指结点的直接前驱。现要在qtr所指结点和ptr所指结点之间插入一个rtr所指的结点，要执行的操作应该是 C 。Artr-Next = ptr-Next;ptr-Next = rtr;Bptr-Next = rtr-Next;Cqtr-Next = rtr;rtr-Next = ptr;Dptr-Next = rtr;rtr-Next =
10、qtr-Next;6在一个单链表中，若现在要删除ptr指针所指结点的直接后继结点，则需要执行的操作是 A 。Aptr-Next = ptr-Next-Next ;Bptr = ptr-Next; ptr-Next = ptr-Next-Next ;Cptr = ptr-Next-Next ;Dptr-Next ptr ; 7在长度为n的顺序表中，往其第i个元素（1in）之前插入一个新的元素时，需要往后移动 B 个元素。An-iBn-i+1Cn-i-1Di8在长度为n的顺序表中，删除第i个元素（1in）时，需要往前移动 A 个元素。An-iBn-i+1Cn-i-1Di9设tail是指向一个非空带
11、表头结点的循环单链表的尾指针。那么，删除链表起始结点的操作应该是 D 。Aptr = tail ;Btail = tail-Next ; tail = tail-Next ; free (tail) ; free (ptr);Ctail = tail-Next-Next ;Dptr = tail-Next-Next ; Free (tail); tail-Next-Next = ptr-Next ; Free (ptr); free (ptr);10在单链表中，如果指针ptr所指结点不是链表的尾结点，那么在ptr之后插入由指针qtr所指结点的操作应该是 B 。Aqtr-Next = ptr ;
12、Bqtr-Next = ptr-Next ; ptr-Next = qtr ; ptr-Next = qtr ;Cqtr-Next = ptr-Next ;Dptr-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的起
