数据结构期末考试题及答案.doc

精品文件2017年数据结构期末考试问题及答复一、选题(共计50分，每题2分，共计25题)1 .在数据结构中，逻辑上数据结构可分为c。a .动态结构和静态结构b .紧凑结构和非紧凑结构c .线性结构和非线性结构d .内部结构和外部结构2 .数据结构在计算机存储器中的显示是指a。a .数据的存储结构b .数据结构c .数据的逻辑结构d .数据要素之间的关系3 .在数据结构中，与使用的计算机无关，是数据的a结构。a .逻辑b .存储c .逻辑和存储d .物理4 .在存储数据的情况下，通常不仅存储各个数据要素的值，还存储c。a .处理数据的方法b .数据要素的类型c .数据元素之间的关系d .数据的存储方法5 .决定选择哪个存储结构通常不考虑a。a .各节点的值如何b .节点数的多少c .对于数据使用哪个运算d .的编程语言实现这个结构比较方便？6 .以下说法正确的是d。a .数据项是数据的基本单位b .数据元素是数据的最小单位c .数据结构是一组带结构的数据项d .一些表面上非常不同的数据可以具有相同的逻辑结构7 .在以下陈述中，正确的是b。a .线性表的顺序存储结构优于链接表存储结构b .二维阵列是线性表，其中数据元素是线性表c .栈的操作方式是先进的d .队列的操作方式是先进的8 .同一逻辑结构中的所有数据元素通常必须具有相同的特性。 这意味着b。a .数据元素具有相同的特点b .不仅数据元素中包含的数据项的数目必须相同，相应数据项的类型也必须匹配c .每个数据元素相同d .数据元素所含数据项的数目应相等9 .链表中没有的特征是a。a .可以随机访问任意节点b .插入删除不需要的移动要素c .存储空间d .必要的空间不需要预先估计为与其长度成比例10 .如果一个表中最常用的操作是在最后一个节点之后插入节点或删除最后一个节点，则d存储方案将节省最多的计算时间。a .单链表b .给予标题指针的单链表c .双链表d .开头节点的双链表11 .需要分配很大的空间，需要插入和删除不需要移动元素的线性表，其存储结构为b。a .单链表b .静态链表c .线性链表d .顺序存储结构12 .非空循环链路表头的尾部节点(用p指示)满足c。A.p-next=NULLB.p=NULLc.p-下一步=头部d.p=头部13 .在循环双链接表的p所指的节点之前插入s所指的节点的操作是d。A.p-prior-prior=sB.p-prior-next=sC.s-prior-next=sD.s-prior-prior=s14 .堆栈和队列的共同点是c。a .一切先进出口b .都是先进出口c .只允许在端点处插入和删除元素d。 没有共同点15 .如果一个堆栈的堆栈序列是a、b、c、d和e，那么堆栈的不可能输出序列是c。A.edcba B.decbaC.dceab D.abcde16 .如果一个队列的入队序列是1、2、3、4，则该队列的输出序列是b。a.4，3，2，1 b.1，2，3，4c.1，4，3，2 d.3，2，4，117 .在循环队列中，如果front和rear分别表示头要素和尾要素的位置，则判断为循环队列为空闲的条件为c。a.front=rear 1b.rear=front 1c.front=reard.front=018 .如果串s=软件，则该子串的数目是b。A.8 B.37 C.36D.919 .字符串的长度指b。a .字符串中包含的不同字符的个数b .字符串中包含的字符的个数c .字符串中包含的不同字符数d .字符串中包含的空格以外的字符数20 .字符串是特殊的线性表，其特殊性出现在b。a.b .数据元素是字母c.d .数据元素可以是多个字符21 .如果一个二叉树具有10个度为2的节点和5个度为1的节点，则度为0的节点的数目为b。A.9 B.11 C.15D .不能确定22 .具有10个叶节点的二叉树有b个度为2的节点。A.8 B.9 C.10 D.1123 .某二叉树节点的中序序列为ABCDEFG，后序序列为BDCAFGE，其左子树的节点数为： cA.3 B.2 C.4 D.5二、填空问题。 (共计20分，共计10题，每天1分)1 .数据逻辑结构包括线性结构、树结构和图结构三种类型，树结构和图结构统称为非线性结构。2 .数据的逻辑结构分为集合、线性结构、树结构和图结构4种。3 .线性构造中要素间存在一对一的关系，树形构造中要素间存在一对多的关系，图形构造中要素间存在多对多的关系。4 .数据结构的基本存储方法是顺序、链、索引和散列存储。5 .子字符串“str”在主字符串“datastructure”中的位置为5。6 .深度为5的二叉树最多有31个节点。7 .如果某个二叉树有20个叶节点，30个节点只有一个孩子，那么该二叉树的总结点数为69。具有8.10个顶点的无向图表，边的总数最大为_45_。9 .索引是为了加快检索速度而引入的数据结构。 索引属于数据记录集，由多个索引项构成，索引项的结构是与关键字和关键字对应的记录的地址。10.1棵m次b树中，除了根节点以外，每个节点最大有m棵子树，m/2棵子树很少。三、判断问题(共10分，共10分，每题1分)。1 .在确定选择哪个存储结构时，不一般考虑每个节点的值。 ()2 .抽象数据类型(ADT )包括定义和实现，定义独立于实现，定义只提供一个ADT逻辑特性，无需考虑如何在计算机上实现。 ()3 .抽象数据类型与计算机内部的表现和实现无关。 ()4 .顺序存储方式的插入和删除效率低下，因此优于链式存储方式。 （）5 .在线性表采用连锁存储结构的情况下，节点与节点内部的存储空间可能是不连续的。 （）6 .双向链路表可以随机访问任何节点。 （）7 .在链接列表中，如果指定任意节点的地址p，则使用以下语句将新节点s插入节点p之后： p-next； （）8 .矩阵是插入和删除操作分别在表的两端进行的线形