福建师范大学《数据结构概论》在线作业二答卷

1、福师数据结构概论在线作业二-0005试卷总分:100 得分:100一、单选题 (共 25 道试题,共 50 分)下列排序算法中，在待排序数据已有序时，花费时间反而最多的是( )排序冒泡希尔快速堆答案:C2.表达式a*(b+c)-d的后缀表达式是( )abcd*+-abc+*d-abc*+d-+*abcd答案:B3.已知串S=aaab,其Next数组值为（ ）0123112312311211答案:A4.一个算法应该是（ ）。程序问题求解步骤的描述要满足五个基本特性A和C.答案:B5.下面给出的四种排序法中（ ）排序法是不稳定性排序法。插入冒泡二路归并堆答案:D6.下列排序算法中，（ ）算法可能会

2、出现下面情况：在最后一趟开始之前，所有元素都不在其最终的位置上。堆排序冒泡排序快速排序插入排序答案:D7.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ）91115不确定答案:B8.算法的时间复杂度取决于（ ）问题的规模待处理数据的初态A和B变量个数答案:C9.线索二叉树是一种（ ）构。逻辑逻辑和存储物理线性答案:C10.CLEAR MEMORY命令的功能是清除整个屏幕清除内存中的所有信息清除所有内存变量清除所有变量答案:C11.在数据库设计中用关系模型来表示实体和实体之间的联系。关系模型的结构是？层次结构二维表结构网状结构封装结构答案:B12.SELECT-S

3、QL语句是选择工作区语句数据查询语句选择标准语句数据修改语句答案:B13.线性表（ a1,a2,an）以链接方式存储时，访问第i位置元素的时间复杂性为（ ）O（i）O（1）O（n）O（i-1）答案:C14.对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为（ ）（N+1）/2N/2N（1+N）*N /2答案:A15.若串S=software,其子串的数目是（ ）837369答案:B16.如果要创建一个数据组分组报表，第一个分组表达式是部门，第二个分组表达式是性别，第三个分组表达式是基本工资，当前索引的索引表达式应当是?部门+性别+基本工资部门+性别+STR(基本工资)STR

4、(基本工资)+性别+部门性别+部门+STR(基本工资)答案:B17.在选项对话框的文件位置选项卡中可以设置下面哪一项?表单的默认大小默认目录日期和时间的显示格式程序代码的颜色答案:B18.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（ ）(1=i=n+1)。O(0)O(1)O(n)O(n2)答案:C19.具有12个关键字的有序表，折半查找的平均查找长度（ ）3.142.55答案:A20.在完全二叉树中，若一个结点是叶结点，则它没（ ）左子结点右子结点左子结点和右子结点左子结点，右子结点和兄弟结点答案:C21.动态存储管理系统中，通常可有（ ）种不同的分配

5、策略。1234答案:C22.栈在（ ）中应用。递归调用子程序调用表达式求值A，答案:D23.关键路径是事件结点网络中（ ）。从源点到汇点的最长路径从源点到汇点的最短路径最长回路最短回路答案:A24.数组A0.4,-1.-3,5.7中含有元素的个数（ ）55453616答案:B25.对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（ ）。O(n) O(n)O(n) O(1)O(1) O(n)O(1) O(1)答案:C二、判断题 (共 20 道试题,共 40 分)26.循环队列也存在空间溢出问题。答案:正确27.二叉树是度为2的有序树答案:错误28.SQL语言的事务管理主要通过事务提交

6、COMMIT和事务撤消ROLLBACK（回滚）两个命令来实现的。答案:正确29.在待排数据基本有序的情况下，快速排序效果最好（ ）答案:错误30.当待排序的元素很多时，为了交换元素的位置，移动元素要占用较多的时间，这是影响时间复杂度的主要因素（ ）答案:正确31.在伙伴系统中的伙伴是指任意两块大小相同、位置相邻的内存块。答案:错误32.主键约束（primary key constraints）的含义是，要求表中在指定的列上没有两行具有相同的值,且不允许为空值。答案:正确33.当待排序的元素很大时，为了交换元素的位置，移动元素要占用较多的时间，这是影响时间复杂度的主要因素答案:正确34.链表中的

7、头结点仅起到标识的作用（ ）答案:错误35.广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表（ ）答案:错误36.对一棵二叉树进行层次遍历时，应借助于一个栈答案:错误37.排序算法中的比较次数与初始元素序列的排列无关（ ）答案:错误38.如果一个工人可管理多个设施，而一个设施只被一个工人管理，则实体工人与实体设备之间存在一对多的联系。答案:正确39.数据管理技术经历了 人工管理 文件系统 数据库系统 三个阶段。答案:正确40.栈和队列都是限制存取点的线性结构（ ）答案:正确41.二叉树的遍历结果不是唯一的（ ）答案:正确42.缺省约束（default constraints）指的

8、是：当向数据库中的表中插入数据时，如果用户没有明确给出某列的值，则系统自动为该字段输入指定的值。答案:正确43.用树的前序遍历和中序遍历可以导出树的后序遍历。答案:错误44.健壮的算法不会因非法的输入数据而出现莫名其妙的状态。答案:正确45.线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的（ ）答案:正确三、多选题 (共 5 道试题,共 10 分)46.数据库文件有哪几种组织方式？顺序文件式链表文件式随机存取文件式索引组织文件式答案:ABCD47.以下数据结构中属于线性数据结构的有哪些（ ）队列线性表二叉树栈答案:ABD48.下列四项关于数据库的说法，哪些项是正确的?数据库具有较高的数据独立性数据库减少了数据冗余数据库中的数据可以共享数据库避免了一切数据的重复答案:ABC49.下面关于线性表的叙述中，正确的是（ ）线性表采用顺序存储，必须占用一片连续的存储单元。线性表采用顺序存储，便于进行插入和