数据结构期末习题答案1

第一章绪论一，选择题1 .组成数据的根本单位是()A.数据项 B.数据类型 C.数据元素 D.数据变量2 .数据结构是研究数据的()以及它们之间的相互关系。A.理想结构，物理结构 B.理想结构，抽象结构C.物理结构，逻辑结构 D.抽象结构，逻辑结构3 .算法分析的两个主要方面是1 )A.正确性和简单性 B.可读性和文档性C.数据复杂性和程序复杂性 D.时间复杂度和空间复杂度4 .算法分析的目的是()。A.找出数据结构的合理性 B.研究算法中的输入和输出的关系C.分析算法的效率以求改良D.分析算法的易懂性和文档性5 .算法的时间复杂度取决于()A.问题的规模 B.待处理数据的初态 C.A和 B D.以上都不是6.一个算法应该是()oA.程序 B.问题求解步骤的描述 C.要满足五个根本特性 D.A和 C.7 .下面关于算法说法错误的选项是()A.算法最终必须由计算机程序实现C.算法的可行性是指指令不能有二义性 D.以上几个都是错误的8 .从逻辑上可以把数据结构分为()两大类。A.动态结构、静态结构 B.顺序结构、链式结构C.线性结构、非线性结构 D.初等结构、构造型结构9 .程序段 f o r(i=nT;i =l;i)f o r(j=l j A j+l )A j 与 A j+1 对换；其 中 n 为正整数，那么最后一行的语句频度在最坏情况下是()A.0(n)B.O(nlogn)C.0(n3)D.0(n2)1 0 .连续存储设计时，存储单元的地址()。A.一定 连 续 B.一 定 不 连 续 C.不 一 定 连 续 D.局部连续，局部不连续二，判断题1 .数据结构的抽象操作的定义与具体实现有关。()2 .数据结构是数据对象与对象中数据元素之间关系的集合。3 .在顺序存储结构中，有时也存储数据结构中元素之间的关系。()4 .数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用的需要建立的。5 .算法和程序原那么上没有区别，在讨论数据结构是两者是通用的。6.同一数据逻辑结构中的所有数据元素都具有相同的特性是指数据元素所包含的数据项的个数都相等。7 .数据的逻辑结构与数据元素本身的内容和形式无关。8 .算法的优劣与算法描述语言无关，但与所用计算机有关。()9.健壮的算法不会因非法的输入数据而出现莫名其妙的状态。()10.算法可以用不同的语言描述，如果用C 语言或PASCAL语言等高级语言来描述，那么算法实际上就是程序了。()一，选择题1.C2.C3.D4.C5.C6.B7.D8.C9.D10.A二，判断题1.X2.V3.X4.J5.X6.X7.J8.X9.10.X三，填空1.数据的物理结构包括 的表示和 的表示。2.对于给定的n 个元素，可 以 构 造 出 的 逻 辑 结 构 有,四种。3.一个数据结构在计算机中 称为存储结构。4.抽 象 数 据 类 型 的 定 义 仅 取 决 于 它 的 一 组,而与 无关，即不管其内部结构如何变化，只要它的 不变，都不影响其外部使用。5.线性结构中元素之间存在 关系，树形结构中元素之间存在 关系，图形结构中元素之间存在 关系。6.一个算法有5 个特性:、,有零个或多个输入、有一个或多个输出。7.如下程序段for(i=n；i=l;i+)语句 1(x:=x+l；语句2 for(j=n;j=i;j+)语句 3y:=y+l;语句 4)语 句 1 执 行 的 频 度 为；语句2 执 行 的 频 度 为；语 句 3 执行的频度为；语句4 执 行 的 频 度 为。8.在下面的程序段中，对 x 的 赋 值 语 句 的 频 度 为 (表示为n 的函数)for(i=l;i=n;i+)fo r(j=1;j=i;j+)for(k=l;k=j;j+)x x+d e lta；9.计算机执行下面的语句时，语句s 的执行次数为。fo r(i=l；i=i;j)s;10.下面程序段的时间复杂度为 _o(nl)sum=l；for(i=0;sumn;i+)sum+=l;三，填空题1.数据元素数据元素间关系2.集 合 线 性 结 构 树 形 结 构 图 状 结 构 或 网 状 结 构3.表示(又称映像).4.逻辑特性在计算机内部如何表示和实现数学特性5.一对一6.有穷性7.n+1 n一对多 多对多确定性 可行性n(n+3)/2 n(n+l)/28.1+(1+2+(1+2+3)+(l+2+-+n)=n(n+l)(n+2)/6 0(n3)9.(n+3)(n-2)/21 0.0(n)四，应用题1 .什么是数据？它与信息是什么关系？2 .什么是数据结构？数据结构是研究什么内容的学科？有关数据结构的讨论涉及哪三方面?3 .评价一个好的算法，从哪几方面考虑？4 .假设将数据结构定义为一个二元组(D,R)，说明符号D,R应分别表示什么？5 .解释算法与程序的区别？6 .有以下几种用二元组表示的数据结构，画出它们分别对应的逻辑图形表示，并指出它们分别属于何种结构。(1)A=(K,R),其中：K=a,b,c,d,e,f,g R=r r=,b,c ,c,d),(d,e),e,f),f,g)(2)B=(K,R),其中：K=a,b,c,d,e,f,g,h R=r r=d,b)，d,g，d,a),(b,c),g,e),g,h),a,f)(3)C=(K,R),其中：K=1,2,3,4,5,6)R=r r=(l,2),(2,3),(2,4),(3,4),3,5),3,6),(4,5),(4,6)这里的圆括号对表示两结点是双向的。7.分析以下程序段的时间复杂度。(1)a=0；b=l；f o r (i=2；i =n；i+)(s=a+b：b-a；a=S：(2)in t i,j,k；f o r (i=0；i n；i+)f o r (j=0；j n；j+c i皿=0;f o r (k=0；k (n；k+c i r j =c i|j +a i k +b k j;I8.求以下算法段的语句频度及时间复杂度(1)f b r(i=l;i=n;i+)f o r(j =l；j =i；j+)x=x+l;(2)f o r (i=l;i =n;i+)f o r (j=l;j =i;j+)f o r (k=l;k =j;k+)x=i+j-k;四，应用题1 .什么是信息？广义地讲，信息就是消息。宇宙三要素(物质、能量、信息)之一。它是现实世界各种事物在人们头脑中的反映。此外，人们通过科学仪器能够认识到的也是信息。信息的特征为：可识别、可存储、可变换、可处理、可传递、可再生、可压缩、可利用、可共享。什么是数据？因为信息的表现形式十分广泛，许多信息在计算机中不方便存储和处理，例如，一个大楼中4部电梯在软件控制下调度和运行的状态、一个商店中商品的在库明细表等，必须将它们转换成数据才能很方便地在计算机中存储、处理、变换。因此，数据(d a t a)是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。在计算机中，信息必须以数据的形式出现。2 .数据结构是指数据以及相互之间的关系。记为：数据结构=D,R。其中，D是某一数据对象，R是该对象中所有数据成员之间的关系的有限集合。数据结构是一门研究在非数值计算的程序设计问题中，计算机的操作对象及对象间的关系和施加于对象的操作等的学科。有关数据结构的讨论一般涉及以下三方面的内容：(1)数据成员以及它们相互之间的逻辑关系，也称为数据的逻辑结构，简称为数据结构；(2)数据成员及其关系在计算机存储器内的存储表示，也称为数据的物理结构，简称为存储结构；(3)施加于该数据结构上的操作。数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储不是一码事，是与计算机存储无关的。因此，数据的逻辑结构可以看作是从具体问题中抽象出来的数据模型，是数据的应用视图。数据的存储结构是逻辑数据结构在计算机存储器中的实现(亦称为映像)，它是依赖于计算机的，是数据的物理视图。数据的操作是定义于数据逻辑结构上的一组运算，每种数据结构都有一个运算的集合。例如搜索、插入、删除、更新、排序等。3 .评价好的算法有四个方面。一是算法的正确性；二是算法的易读性；三是算法的健壮性;四是算法的时空效率(运行)。4 .D是数据元素的有限集合，S是D上数据元素之间关系的有限集合。5 .算法是为了解决某类问题而规定的一个有限长的操作序列。一个算法必须满足以下五个重要特性：有 穷 性 确 定 性 可 行 性 有输入 有输出算法与程序的联系和区别：(1)算法代表了对问题的解，而程序那么是算法在计算机上的特定的实现。一个程序不一定满足有穷性。例如，操作系统，只要整个系统不遭破坏，它将永远不会停止。因此，操作系统不是一个算法。(2)程序中的指令必须是机器可执行的，而算法中的指令那么无此限制。(3)算法是面向功能的，通常用面向过程的方式描述；程序可以用面向对象方式搭建它的框架。(4)算法与数据结构是相辅相承的：解决某一特定类型问题的算法可以选定不同的数据结构，而且选择恰当与否直接影响算法的效率。反之，一种数据结构的优劣由各种算法的执行来表达。6.(1)A对应逻辑图形如下，它是一种线性结构。(1)解：语句的频度是2；语句的频度是n；语句的频度是n-1；语句的频度是n-1；语句的频度是n-1；故，该程序段的时间复杂度T I n)=2+n+3*(n-1)=4 n-l=0 (n J (2)解:语句的循环控制变量i 要增加到n,测试到i=n 成立才会终止，故它的频度为n+1；语句作为语句循环体内的语句应该执行n次，但语句本身要执行n+1次，故语句的频度是n (n+1)；同理可得语句、和的频度分别是n 2,n 2 (n+1)和 n 3。该程序段所有语句的频度之和为：T (n)=2 n 3+3 n 2+2 n+l其复杂度为0 (n 3)8.(1)分析：该算法为一个二重循环，执行次数为内、外循环次数相乘，但内循环次数不固定，与外循环有关,因此，时间频度T(n)=l+2+3+n=n*(n+l)/2。有 l/4 W T(n)/n W l,故它的时间复杂度为0 (n)即 T(n)与 r?数量级相同。(2)分析算法规律可知时间频度T(n)=l+(l+2)+(l+2+3)+.+(1+2+3+n)。由于有1/6 n e x t=h B.p-n e x t=N I L C.p-n e x t-n e x t=h D.p-d a t a=-l2 .下面关于线性表的表达中，A.线性表采用顺序存储,B.线性表采用顺序存储,C.线性表采用链接存储,D.线性表采用链接存储,3 .线性表是具有n个()A.表元素 B.字符错误的选项是哪一个？(必须占用一片连续的存储单元。便于进行插入和删除操作。不必占用一片连续的存储单元。便于插入和删除操作。的有限序列(n 0)oC.数据元素 D.数据项4.假设某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算,那 么 利 用()存储方式最节省时间。A.顺序表 B.双链表 C.带头结点的双循环链表 D.单循环链表5 .某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，那么采 用()存储方式最节省运算时间。A.单链表 B.仅有头指针的单循环链表C.双链表 D.仅有尾指针的单循环链表6 .设一个链表最常用的操作是在末尾插入结点和删除尾结点，那 么 选 用()最节省时间。7 .在带有头结点的单链中插入一个新结点时不可能修改()。A.头指针 B.头 结 点 指 针 域 C.开 始 结 点 指 针 域 D.其它结点指针域8 .双向链表中有两个指针域，l l i n k 和 r l i n k,分别指向前驱及后继，设 p指向链表中的一个结点，q指向一待插入结点，现要求在P前插入q,那么正确的插入为(A.p-l l i n k=q;q-r l i n k=p;p-l l i n k-r l i n k=q;q-l l i n k=p-l 1 i n k;B.q-l l i n k=p-l l i n k;p-l l i n k-r l i n k=q;q