2017年数据结构期末考试题及答案A

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非空的循环单链表head的尾结点（由p所指向）满足C 。Apnext NULLBp NULLCpnext head Dp head13在循环双链表的p所指的结点之前插入s所指结点的操作是 D 。Appriorprior=sBppriornext=sCspriornext sDspriorprior s14栈和队列的共同点是C 。A都是先进后出 B都是先进先出C只允许在端点处插入和删除元素 D没有共同点15一个栈的进栈序列是a，b，c，d，e，则栈的不可能的输出序列是 C 。AedcbaBdecbaCdceabDabcde16一个队列的入队序列是1，2，3，4，则队列的输出序列是B 。A4，3，2，1 B1，2，3，4C1，4，3，2 D3，2，4，117在循环队列中，若front与rear 分别表示对头元素和队尾元素的位置，则判断循环队列空的条件是 C。Afrontrear1 Brearfront1 Cfrontrear Dfront018若串Ssoftware，其子串的数目是 B 。A8 B37 C36D919串的长度是指B 。A串中所含不同字母的个数 B串中所含字符的个数C串中所含不同字符的个数 D串中所含非空格字符的个数20串是一种特殊的线性表，其特殊性体现在B 。A可以顺序存储B数据元素是一个字符C可以链式存储D数据元素可以是多个字符21若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点的个数是B 。A9 B11 C15D不能确定22具有10个叶子结点的二叉树中有 B 个度为2的结点。A8 B9 C10 D1123某二叉树结点的中序序列为ABCDEFG，后序序列为BDCAFGE，则其左子树中结点数目为：CA3B2 C4D5二、填空题。（共计20分，共10题，每空1分）1数据逻辑结构包括线性结构 、树形结构和图状结构三种类型，树形结构和图状结构合称 非线性结构 。2数据的逻辑结构分为集合 、线性结构 、树形结构和图状结构4种。3线性结构中元素之间存在 一对一 关系，树形结构中元素之间存在 一对多 关系，图形结构中元素之间存在多对多关系。4数据结构的基本存储方法是 顺序、链式、 索引和 散列存储 。5子串 ”str” 在主串 ”datastructure” 中的位置是 5。6深度为5的二叉树至多有31 个结点。7若某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点个数为 69 。8具有10个顶点的无向图，边的总数最多为_45_。 9索引是为了加快检索速度而引进的一种数据结构。一个索引隶属于某个数据记录集，它由若干索引项组成，索引项的结构为关键字 和 关键字对应记录的地址 。10在一棵m阶B树中，除根结点外，每个结点最多有 m棵子树，最少有 m/2 棵子树。三、判断题（共10分，共10题，每题一分）。1在决定选取何种存储结构时，一般不考虑各结点的值如何。（）2抽象数据类型（ADT）包括定义和实现两方面，其中定义是独立于实现的，定义仅给出一个ADT的逻辑特性，不必考虑如何在计算机中实现。（ ）3抽象数据类型与计算机内部表示和实现无关。（ ）4顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。（ ）5线性表采用链式存储结构时，结点和结点内部的存储空间可以是不连续的。（ ）6双向链表可随机访问任一结点。（）7在单链表中，给定任一结点的地址p，则可用下述语句将新结点s插入结点p的后面 ：pnext； （ ）8队列是一种插入和删除操作分别在表的两端进行的线性表，是一种先进后出的结构。（ ）9长度为1的串等价于一个字符型常量。（）10空串和空白串是相同的。（）四、编程题（共20分，共2题，每题10分）。1. 请用C语言定义一个链表的数据结构存储方式。（10分） 2.请有C语言简单描述冒泡排序算法。（10分）