数据结构1-4章习题答案

《数据结构1-4章习题答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第1章概论习题参考解答一、填空题1、数据的逻辑结构是数据元素之间的逻辑关系，通常有下列4类：（）、（）、（）、（）。【答】集合、线性结构、树型结构和图状结构。2、数据的存储结构是数据在计算机存储器里的表示，主要有4种基本存储方法：（）、（）、（）、（）。【答】顺序存储方法、链接存储方法、索引存储方法和散列存储方法。二、选择题1、一个算法必须在执行有穷步之后结束，这是算法的（）。（A）正确性（B）有穷性（C）确定性（D）可行性【答】B。2、算法的每一步，必须有确切的定义。也就是说，对于每步需要执行的动作必须严格、清楚地给出规定

2、。这是算法的（）。（A）正确性（B）有穷性（C）确定性（D）可行性【答】C。3、算法原则上都是能够由机器或人完成的。整个算法好像是一个解决问题的“工作序列”，其中的每一步都是我们力所能及的一个动作。这是算法的（）。（A）正确性（B）有穷性（C）确定性（D）可行性【答】D。三、简答题1、算法与程序有何异同？【答】尽管算法的含义与程序非常相似，但两者还是有区别的。首先，一个程序不一定满足有穷性，因此它不一定是算法。例如，系统程序中的操作系统，只要整个系统不遭受破坏，它就永远不会停止，即使没有作业要处理，它仍处于等待循环中，以待一

3、个新作业的进入。因此操作系统就不是一个算法。其次，程序中的指令必须是计算机可以执行的，而算法中的指令却无此限止。如果一个算法采用机器可执行的语言来书写，那么它就是一个程序。2、什么是数据结构？试举一个简单的例子说明。【答】数据结构是指数据对象以及该数据对象集合中的数据元素之间的相互关系（即数据元素的组织形式）。例如，队列的逻辑结构是线性表（先进先出）；队列在计算机中既可以采用顺序存储也可以采用链式存储；对队列可进行删除、插入数据元素以及判断是否为空队列、将队列置空等操作。3、什么是数据的逻辑结构？什么是数据的存储结构？【答】

4、数据元素之间的逻辑关系，也称为数据的逻辑结构。数据元素以及它们之间的相互关系在计算机存储器内的表示（又称映象），称为数据的存储结构，也称数据的物理结构。1、什么是算法？算法有哪些特性？【答】算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作；此外，一个算法还具有下列5个特性：①有穷性：一个算法必须在执行有穷步之后结束，即算法必须在有限时间内完成。②确定性：算法中每一步必须有确切的含义，不会产生二义性。并且，在任何条件下，算法只有唯一的一条执行路径，即对于相同的输入只能得出相同的输出。③可

5、行性：一个算法是能行的，即算法中的每一步都可以通过已经实现的基本运算执行有限次得以实现。④输入：一个算法有零个或多个输入，它们是算法开始时对算法给出的初始量。⑤输出：一个算法有一个或多个输出，它们是与输入有特定关系的量。四、算法分析题1、将下列复杂度由小到大重新排序：2n、n!、n2、10000、log2n、n×log2n。【答】10000

6、n【答】O(n4)。⑷n×log2n+n×log3n【答】O(n×log2n)。3、设n为正整数，请用大“O”表示法描述下列程序段的时间复杂度。⑴i=1;k=0;⑵i=0;k=0;while(i1*/while(i+j<=n)while(x>=(y+1)*(y+1)){if(i>j)j++;y++;elsei++}【答】O(n)。【答】O()。⑸for((i

7、=1;i<=n;i++)⑹x=91;y=100;for(j=1;j<=i;j++)while(y>0)for(k=1;k<=j;k++){if(x>100){x-=10;y--;}x+=c;(c为常数)elsex++;}【答】O(n3)。【答】O(n)。第2章线性表习题参考解答一、简答题1．试描述头指针、头结点、开始结点的区别、并说明头指针和头结点的作用。【答】头指针：是指向链表中的第一个结点的指针。头结点：在开始结点之前附加上的一个结点。开始结点：链表的第一个结点。头指针是一个指向地址的变量，用于表示一个链表的开始。引入头

8、结点可以更加方便的进行链表是否为空的判断，同时方便了插入和删除结点。开始结点用于存储链表的第一个数据元素。2．何时选用顺序表、何时选用链表作为线性表的存储结构为宜?【答】顺序表中查找元素、获取表长非常容易，但是，要插入或者删除一个元素却需要移动大量的元素；相反，链表中却是方便插入或者删除元