第六套 模拟题
（1）下列叙述中正确的是
　A）线性表是线性结构
　B）栈与队列是非线性结构
　C）线性链表是非线性结构
　D）二叉树是线性结构
（2）非空的循环单链表head的尾结点（由p所指向），满足
　A）p->next==NULL
　B）p==NULL
　C）p->next=head
　D）p=head
（3）已知数据表A中每个元素距其最终位置不远，为节省时间，应采用的算法是
　A）堆排序
　B）直接插入排序
　C）快速排序
　D）直接选择排序
（4）对建立良好的程序设计风格，下面描述正确的是
　A）程序应简单、清晰、可读性好
　B）符号名的命名只要符合语法
　C）充分考虑程序的执行效率
　D）程序的注释可有可无
（5）下列不属于结构化分析的常用工具的是
　A）数据流图
　B）数据字典
　C）判定树
　D）PAD图
（6）在软件生产过程中，需求信息的给出是
　A）程序员
　B）项目管理者
　C）软件分析设计人员
　D）软件用户
（7）下列工具中为需求分析常用工具的是
　A）PAD
　B）PFD
　C）N-S
　D）DFD
（8）NULL是指
　A）0
　B）空格
　C）未知的值或无任何值
　D）空字符串
（9）数据库的故障恢复一般是由
　A）数据流图完成的
　B）数据字典完成的
　C）DBA完成的
　D）PAD图完成的
（10）下列说法中，不属于数据模型所描述的内容的是
　A）数据结构
　B）数据操作
　C）数据查询
　D）数据约束
（11）冒泡排序算法在最好的情况下的元素交换次数为 【1】 。

（12）在最坏情况下，堆排序需要比较的次数为 【2】 。

（13）若串s="MathTypes"，则其子串的数目是 【3】 。

（14）软件开发环境是全面支持软件开发全过程的 【4】 集合。

（15）关系数据库的关系演算语言是以 【5】 为基础的DML语言。
试题解析
　　1．解析： 线性表是一种线性结构，数据元素在线性表中的位置只取决于它们自己的序号，即数据元素之间的相对位置是线性的；栈、队列、线性链表实际上也是线性表，故也是线性结构；树是一种简单的非线性结构。

　　2．解析： 循环链表就是将链表的最后一个结点指向链表头结点（或第一个结点），即p->next=head。
　　3．解析： 当数据表A中每个元素距其最终位置不远，说明数据表A按关键字值基本有序，在待排序序列基本有序的情况下，采用插入排序所用时间最少，故答案为选项B）。

　　4．解析： 程序设计应该简单易懂，语句构造应该简单直接，不应该为提高效率而把语句复杂化。
　　5．解析： 结构化分析的常用工具有数据流图、数据字典、判定树和判定表。而PAD图是常见的过程设计工具中的图形设计。

　　6．解析： 软件需求是指用户对目标软件系统在功能、行为、性能、设计约束等方面的期望。
　　7解析： 需求分析中的常用工具有PAD、PFD及N-S等，而DFD（数据流图）为结构化分析工具。

　　8解析： 此题属于记忆性的题目，NULL是指未知的值或无任何值。

　　9．解析： 一旦数据库中的数据遭受破坏，需要及时进行恢复，RDBMS一般都提供此种功能，并由DBA负责执行故障恢复功能。

　　10．解析： 数据模型所描述的内容有3个部分，它们是数据结构、数据操作和数据约束。其中，数据模型中的数据结构主要描述数据的类型、内容、性质，以及数据库的联系等；数据操作主要是描述在相应数据结构上的操作类型与操作方式。

　　11．解析： 根据冒泡排序算法思想可知，若待排序的初始序列为“正序”序列，则只需进行一趟排序，在排序过程中进行n-1次关键字间的比较，且不移动和交换记录，这种情况是冒泡排序的最好情况，故冒泡排序算法在最好的情况下的元素交换次数为0。

　　12 ．O（nlog2n）

　　13．解析： 串s中共有9个字符，由于串中字符各不相同，则其子串中有0个字符的1个（空串），1个字符的9个，2个字符的8个，3个字符的7个，4个字符的6个，5个字符的5个，6个字符的4个，7个字符的3个，8个字符的2个，9个字符的1个，共有1+2+3+4+5+6+7+8+9+1=46。

　　14．软件工具

　　15．解析： 关系数据库中的关系演算包括元组关系演算和域关系演算。二者都是由原子公式组成的公式。而这些关系演算都是以数理逻辑中的谓词演算为基础的。