搜索
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。A．p－＞next＝＝NULLB．p＝＝NULLC．p－＞next＝＝headD．p＝＝head13．在循环双链表的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．edcbaB．decbaC．dceabD．abcde16．一个队列的入队序列是1，2，3，4，则队列的输出序列是B。A．4，3，2，1B．1，2，3，4C．1，4，3，2D．3，2，4，117．在循环队列中，若front与rear分别表示对头元素和队尾元素的位置，则判断循环队列空的条件是C。A．front＝＝rear＋1B．rear＝＝front＋1C．front＝＝rearD．front＝＝018．若串S＝‘software’，其子串的数目是B。A．8B．37C．36D．919．串的长度是指B。A．串中所含不同字母的个数B．串中所含字符的个数C．串中所含不同字符的个数D．串中所含非空格字符的个数20．串是一种特殊的线性表，其特殊性体现在B。A．可以顺序存储B．数据元素是一个字符C．可以链式存储D．数据元素可以是多个字符21．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点的个数是B。A．9B．11C．15D．不能确定22．具有10个叶子结点的二叉树中有B个度为2的结点。A．8B．9C．10D．1123．某二叉树结点的中序序列为ABCDEFG，后序序列为BDCAFGE，则其左子树中结点数目为：CA．3B．2C．4D．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．在一棵m阶B树中，除根结点外，每个结点最多有m棵子树，最少有m/2棵子树。三、判断题（共10分，共10题，每题一分）。1．在决定选取何种存储结构时，一般不考虑各结点的值如何。（√）2．抽象数据类型（ADT）包括定义和实现两方面，其中定义是独立于实现的，定义仅给出一个ADT的逻辑特性，不必考虑如何在计算机中实现。（√）3．抽象数据类型与计算机内部表示和实现无关。（√）4．顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。（×）5．线性表采用链式存储结构时，结点和结点内部的存储空间可以是不连续的。（×）6．双向链表可随机访问任一结点。（×）7．在单链表中，给定任一结点的地址p，则可用下述语句将新结点s插入结点p的后面：p－＞next；（×）8．队列是一种插入和删除操作分别在表的两端进行的线性表，是一种先进后出的结构。（×）9．长度为1的串等价于一个字符型常量。（×）10．空串和空白串是相同的。（×）四、编程题（共20分，共2题，每题10分）。1.请用C语言定义一个链表的数据结构存储方式。（10分）2.请有C语言简单描述冒泡排序算法。（10分）