数据结构本科教学资料-数据结构习题答案

《数据结构本科教学资料-数据结构习题答案》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、参考答案第一章绪论1.什么是信息？广义地讲，信息就是消息。宇宙三要素（物质、能量、信息）Z-O它是现实世界各种事物在人们头脑中的反映。此外，人们通过科学仪器能够认识到的也是信息。信息的特征为：可识别、可存储、可变换、可处理、可传递、可再生、可压缩、可利用、可共享。什么是数据？因为信息的表现形式十分广泛，许多信息在计算机中不方便存储和处理,例如，一个大楼屮4部电梯在软件控制下调度和运行的状态、一个商店屮商品的在库明细表等，必须将它们转换成数据才能很方便地在计算机中存储、处理、变换。因此，数据（data）是信息的载体，是描述客观事物的数、字符、以及所有能输入到

2、计算机中并被计算机程序识别和处理的符号的集合。在计算机中，信息必须以数据的形式出现。2.数据结构是指数据以及相互之间的关系。记为：数据结构二｛D,R｝。其中，D是某一数据对象，R是该对象中所有数据成员之间的关系的有限集合。有关数据结构的讨论一般涉及以下三方面的内容：①数据成员以及它们相互之间的逻辑关系，也称为数据的逻辑结构，简称为数据结构;②数据成员极其关系在计算机存储器内的存储表示，也称为数据的物理结构，简称为存储结构；③施加于该数据结构上的操作。数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储不是一码事，是与计算机存储无关的。因此，数据的逻辑结构可

3、以看作是从具体问题屮抽象出来的数据模型，是数据的应用视图。数据的存储结构是逻辑数据结构在计算机存储器中的实现（亦称为映像），它是依赖于计算机的，是数据的物理视图。数据的操作是泄义于数据逻辑结构上的一组运算，每种数据结构都有一个运算的集合。例如搜索、插入、删除、更新、排序等。3.线性结构的特点是：在结构中所有数据成员都处于一个序列中，有且仅有一个开始成员和一个终端成员，并且所有数据成员都最多有一个直接前驱和一个直接后继。例如，一维数组、线性表等就是典型的线性结构非线性结构的特点是：一个数据成员可能有零个、一个或多个直接前驱和直接后继。例如，树、图或网络等都是

4、典型的非线性结构。4.通常，定义算法为“为解决某一特定任务而规定的一个指令序列。”一个算法应当具有以下特性：①有输入。一个算法必须有0个或多个输入。它们是算法开始运算前给予算法的量。这些输入取自于特定的对象的集合。它们可以使用输入语句由外部提供，也可以使用赋值语句在算法内给定。②有输出。一个算法应有一个或多个输出，输出的量是算法计算的结果。③确定性。算法的每一步都应确切地、无歧义地定义。对于每一种情况，需要执行的动作都应严格地、清晰地规定。④有穷性。一个算法无论在什么情况下都应在执行有穷步后结束。⑤有效性。算法屮每一条运算都必须是足够基本的。就是说，它们原

5、则上都能精确地执行，甚至人们仅用笔和纸做有限次运算就能完成。算法和程序不同，程序可以不满足上述的特性(4)。例如，一个操作系统在用户未使用前一直处于“等待”的循环中，直到出现新的用户事件为止。这样的系统可以无休止地运行,直到系统停工。此外，算法是面向功能的，通常用面向过程的方式描述；程序可以用面向对象方式搭建它的框架。1.(1)判断n是否是一个素数，若是则返回数值1,否则返冋0。该算法的时间复杂性为0(石)°(2)计算£i!的值。时间复杂性为0(n)。i=l(3)计算£i!的值。时间复杂性为0(同。i=l(4)求出满足不等式1+2+3+…+i鼻n的最小i值

6、。时间复杂性为0(百)。(5)利用数组c[10]中的每个元素c[i]对应统计出inp所联系的整数文件中个位值同为i的整数个数。时间复杂性为0(n)o(6)打印出一个具有n行的乘法表，第i行(lWiWn)中有n-i+l个乘法项，每个乘法项为i与j(iWjWn)的乘积。时间复杂性为0(n2)o(7)使数组a[M][N]中的每一个元素均乘以d的值。时间复杂性为0(MXN)o第二章线性表l.B2.B3.①sym==1②p二p->rLink③q=q->ILink4.(1)顺序存储表示是将数据元素存放于一个连续的存储空间中，实现顺序存取或(按下标)直接存収。它的存储效

7、率高，存取速度快。但它的空间大小一经定义，在程序整个运行期间不会发生改变，因此，不易扩充。同时，由于在插入或删除时，为保持原有次序，平均需要移动一半(或近一半)元素，修改效率不高。链接存储表示的存储空间一般在程序的运行过程屮动态分配和释放，且只要存储器中还有空间，就不会产生存储溢出的问题。同时在插入和删除时不需要保持数据元素原来的物理顺序，只需要保持原来的逻辑顺序，因此不必移动数据，只需修改它们的链接指针，修改效率较高。但存取表中的数据元素时，只能循链顺序访问，因此存取效率不高。(2)如果有n个表同时并存，并且在处理过程屮各表的长度会动态发生变化，表的总数

8、也可能白动改变、在此情况下，应选用链接存储表示。如果采用顺序存储表