数据结构期末考试题及答案AWord格式文档下载.doc

数据结构期末考试题及答案AWord格式文档下载.doc

《数据结构期末考试题及答案AWord格式文档下载.doc》由会员分享，可在线阅读，更多相关《数据结构期末考试题及答案AWord格式文档下载.doc（5页珍藏版）》请在冰点文库上搜索。

　　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＝＝NULL　　　　B．p＝＝NULL

　　C．p－＞next＝＝head　　　D．p＝＝head

　　13．在循环双链表的p所指的结点之前插入s所指结点的操作是　D　。

　　A．p－＞prior－＞prior=s

　　B．p－＞prior－＞next=s

　　C．s－＞prior－＞next＝s

　　D．s－＞prior－＞prior＝s

　　14．栈和队列的共同点是　C　。

　　A．都是先进后出　　　　　　　　　　　B．都是先进先出

　　C．只允许在端点处插入和删除元素　　　D．没有共同点

　　15．一个栈的进栈序列是a，b，c，d，e，则栈的不可能的输出序列是　C　。

　　A．edcba　　　B．decba　　C．dceab　　　D．abcde

　　16．一个队列的入队序列是1，2，3，4，则队列的输出序列是　B　。

　　A．4，3，2，1　　　B．1，2，3，4

　　C．1，4，3，2　　　D．3，2，4，1

　　17．在循环队列中，若front与rear分别表示对头元素和队尾元素的位置，则判断循环队列空的条件是　C　　。

A．front＝＝rear＋1　　B．rear＝＝front＋1　　C．front＝＝rear　　　D．front＝＝0

18．若串S＝‘software’，其子串的数目是　B　。

　　A．8　　B．37　　C．36　　　　D．9

　　19．串的长度是指　B　。

　　A．串中所含不同字母的个数　　　B．串中所含字符的个数

　　C．串中所含不同字符的个数　　　D．串中所含非空格字符的个数

　　20．串是一种特殊的线性表，其特殊性体现在　B　。

　　A．可以顺序存储　　　B．数据元素是一个字符

　　C．可以链式存储　　　D．数据元素可以是多个字符

　　21．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点的个数是　B。

　　A．9　　B．11　　C．15　　D．不能确定

　　22．具有10个叶子结点的二叉树中有　B　个度为2的结点。

　　A．8　　B．9　　C．10　D．11

　　23．某二叉树结点的中序序列为ABCDEFG，后序序列为BDCAFGE，则其左子树中结点数目为：

　　C

　　A．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．在一棵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语言简单描述冒泡排序算法。