计算机软件技术基础所有题目答案-自学.doc

数据结构习题答案 第一节 概 论 一、选择题 1．要求同一逻辑结构的所有数据元素具有相同的特性，这意味着( )。 A．数据元素具有同一的特点 *B．不仅数据元素包含的数据项的个数要相同，而且对应数据项的类型要一致 C．每个数据元素都一样 D．数据元素所包含的数据项的个数要相等 2．数据结构是一门研究非数值计算的程序设计问题中计算机的( (1) )以及它们之间的( (2) )和运算的学科。 (1) *A．操作对象 B．计算方法 C．逻辑存储 D．数据映像 (2) A．结构 *B．关系 C．运算 D．算法 3．数据结构被形式地定义为(D，R)，其中D是( (1) )的有限集合，R是D上( (2) )的有限集合。 (1) A．算法 *B．数据元素 C．数据操作 D．逻辑结构 (2)A．操作 B．映像 C．存储 *D．关系 4．在数据结构中，从逻辑上可以把数据结构分为( )。 A．动态结构和静态结构 B．紧凑结构和非紧凑结构 *C．线性结构和非线性结构 D．内部结构和外部结构 5．线性表的顺序存储结构是一种( )的存储结构。 *A．随机存取 B．顺序存取 C．索引存取 D．Hash存取 6．算法分析的目的是( )。 A．找出数据结构的合理性 B．研究算法中的输入和输出的关系 *C．分析算法的效率以求改进 D．分析算法的易懂性和文档性 7．计算机算法指的是( (1) )，它必须具备输入、输出和( (2) )等五个特征。 (1) A．计算方法 B．排序方法 *C．解决某一问题的有限运算序列 D．调度方法 (2) A．可行性、可移植性和可扩充性 *B．可行性、确定性和有穷性 C．确定性，有穷性和稳定性 D．易读性、稳定性和安全性 8．线性表若采用链表存储结构，要求内存中可用存储单元的地址( )。 A．必须是连续的 B．部分必须是连续的 C．一定是不连续的 *D．连续不连续都可以 9．在以下的叙述中，正确的是( )。 A．线性表的线性存储结构优于链式存储结构 *B．二维数组是它的每个数据元素为一个线性表的线性表 C．栈的操作方式是先进先出 D．队列的操作方式是先进后出 10．根据数据元素之间关系的不同特性，以下四类基本的逻辑结构反映了四类基本的数据组织形式，其中解释错误的是( )。 *A．集合中任何两个结点之间都有逻辑关系但组织形式松散 B．线性结构中结点按逻辑关系依次排列形成一条“锁链” C．树形结构具有分支、层次特性，其形态有点像自然界中的树 D．图状结构中的各个结点按逻辑关系互相缠绕，任何两个结点都可以邻接 11．以下说法正确的是( )。 A．数据元素是数据的最小单位 B．数据项是数据的基本单位 C．数据结构是带有结构的各数据项的集合 *D．数据结构是带有结构的数据元素的集合 二、判断题 ╳1．数据元素是数据的最小单位。 √2．数据结构是带有结构的数据元素的集合。 √3．数据结构、数据元素、数据项在计算机中的映像分别称为存储结构、结点、数据域。 ╳4．数据项是数据的基本单位。 √5．数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用需要建立的。 √6．数据的物理结构是数据在计算机中实际的存储形式。 ╳7．算法和程序没有区别，所以在数据结构中二者是通用的。 ╳8．顺序存储结构属于静态结构，链式存储结构属于动态结构。 三、填空题 1．所谓数据的逻辑结构指的是数据元素之间的____逻辑关系_____。 2，数据结构是相互之间存在一种或多种特定关系的数据元素的集合，它包括三方面的内容___数据的逻辑结构、数据的存储结构、对数据施加的操作___。 3．数据的逻辑结构包括_____集合结构___、_____线性结构___、____树型结构_____和__图状结构_____四种类型。 4．在线性结构中，开始结点__没有_前驱结点，其余每个结点有且只有__一个_个前驱结点。 5．在树形结构中，根结点只有___一个___，其余每个结点有且只有___一个___前驱结点；叶结点没有___后继__结点，其余每个结点的后继结点可以有__任意个__· 6．在图形结构中，每个结点的前驱结点和后继结点可以有___任意个___。 7．算法的五个重要特性是__可行性___、___确定性___、___有穷性___、___输入__、___输出__。 8．下列程序段的时间复杂度是__O（n）___。 for (i=1；i=n；i++) A[i，i]=0； 9．下列程序段的时间复杂度是__ O（n2）___。 S=0； f