数据结构第一章习题参考解析.docxVIP

1.6 习题1.6.1知识点：数据结构的定义一、选择题1① 数据结构通常是研究数据的（A）及它们之间的相互联系。A．存储和逻辑结构 B．存储结构 C．顺序结构 D．链式存储结构2① 数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为（C）A．存储结构 B．逻辑结构 C．顺序存储结构 D．链式存储结构3① 线性结构是数据元素之间存在一种（D）。A．一对多关系 B. 多对多关系 C 多对一关系 D 一对一关系4① 计算机内部数据处理的基本单位是（B）。A. 数据 B．数据元素 C.数据项 D．数据库5② 从逻辑上可以把数据结构分为（C）两大类。【武汉交通科技大学 1996】A．动态结构、静态结构 B．顺序结构、链式结构C．线性结构、非线性结构 D．初等结构、构造型结构二、填空题1① 数据结构按逻辑结构可分为四大类，它们分别是集合、线性、树、图。2① 数据的存储结构可用四种基本的存储方法表示，它们分别是顺序、链式、散列、索引。三、判断题（F）1① 数据元素是数据的最小单位。（T）2① 记录是数据处理的最小单位。（F）3① 数据的逻辑结构是指数据的各数据项之间的逻辑关系。（T）4① 数据的物理结构是指数据在计算机内的实际存储形式。四、简答题1① 简述什么是数据结构?2② 数据结构与数据类型有什么区别? 【哈尔滨工业大学 2001】1.6.2知识点：算法的概念一、选择题1① 计算机算法指的是（C）A．计算方法 B．排序方法C．解决问题的有限运算序列 D．调度方法2① 算法分析的目的是（（1）C），算法分析的两个主要方面（（2）A）．（1） A．找出数据结构的合理性 B．研究算法中的输入与输出的关系 C．分析算法的效率以求改进 D．分析算法的易查性和文档性（2） A．空间复杂度和时间复杂度 B．正确性和简明性C．可读性和文档性 D．数据复杂性和程序复杂性3② 设语句X++的时间是单位时间，则语句： for（i=1;i=n;i++） x++;时间复杂度为（C）。A．O（1） B．O（n） C．O（） D．O（）4② 算法的计算量的大小称为计算的（B）。【北京邮电大学2000】A．效率 B．复杂性 C．现实性 D．难度5② 算法的时间复杂度取决于（C）【中科院计算所 1998】A．问题的规模 B．待处理数据的初态 C．A 和B6② 下面关于算法说法错误的是（A）【南京理工大学 2000】A．算法最终必须由计算机程序实现B．为解决某问题的算法同为该问题编写的程序含义是相同的C．算法的可行性是指指令不能有二义性D．以上几个都是错误的7② 下面说法错误的是（D）【南京理工大学 2000】（1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模n 下，复杂度O（n）的算法在时间上总是优于复杂度O（2n）的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（4）同一个算法，实现语言的级别越高，执行效率就越低A．（1） B．（1）,（2） C．（1）,（4） D．（3）8② 程序段for（i=n-1;i=1;i++）for（ j=1;j=i;j++）if（ A[j]A[j+1]）A[j]与A[j+1]对换；其中 n 为正整数，则最后一行的语句频度在最坏情况下是（D）【南京理工大学1998】A．O（n） B．O（） C． O（） D． O（）二、填空题1① 以夹杂自然语言和程序语句的形式来描述解决问题的方法称为____伪码________。2① 一个算法的效率可分为___时间______效率和__空间_______效率．3② 有一个程序片断如下：for（i=0;in;i++）x=x+1;则其时间复杂度为：_O（n）________4② 有一个程序片断如下：for（i=0;in;i++） for（j=i;jn;j++）for（k=j;kn;k++）m=1;则其时间复杂度为：O（n3）5② 有一个程序片断如下：for（i=0;in;i++）{j=i;while（j=2）j=j/2; }则其时间复杂度为：O（n）三、判断题（T）1① 算法的优劣与算法描述语言无关，但与所用计算机有关。（T）2① 健壮的算法不会因非法的输入数据而出现莫名其妙的状态。（F）3① 程序一定是算法。四、简答题1① 如何判断一个算法的好坏?2③ 调用下列C 函数f（n）回答下列问题：（1）试指出f（n）值的大小，并写出f（n）值的推导过程；（2）假定n= 5，试指出f（5）值的大小和执行f（5）时的输出结果。C 函数：int f（int n）{ int i,j，k,sum= 0;for（