20秋学期《数据结构Ⅰ》在线平时作业3

adminhan

下列排序算法中，时间复杂度不受数据初始状态影响，恒为0(nlog2n)的是
A:堆排序
B:冒泡排序
C:直接选择排序
D:快速排序

引起循环队列队头位置发生变化的操作是lang=EN-US
A:出队
B:入队
C:取队头元素
D:取队尾元素

下列查找算法中，平均查找长度与元素个数n不直接相关的查找方法是
A:分块查找
B:顺序查找
C:二分查找
D:散列查找

一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少的结点数有lang=EN-US
A:2h
B:2h-1
C:2h 1
D:h 1

数据的四种基本存储结构是指lang=EN-USlang=EN-USlang=EN-USlang=EN-US
A:顺序存储结构、索引存储结构、直接存储结构、倒排存储结构
B:顺序存储结构、索引存储结构、链式存储结构、散列存储结构
C:顺序存储结构、非顺序存储结构、指针存储结构、树型存储结构
D:顺序存储结构、链式存储结构、树型存储结构、图型存储结构

在以单链表为存储结构的线性表中，数据元素之间的逻辑关系用lang=EN-US
A:数据元素的相邻地址表示
B:数据元素在表中的序号表示
C:指向后继元素的指针表示
D:数据元素的值表示

某二叉树的先序序列和后序序列正好相反，则该二叉树的特点一定是lang=EN-US
A:空或只有一个结点
B:高度等于其结点数
C:任一结点无左孩子
D:任一结点无右孩子

由同一关键字集合构造的各棵二叉排序树
A:其形态不一定相同，但平均查找长度相同lang=EN-US
B:其形态不一定相同，平均查找长度也不一定相同lang=EN-US
C:其形态均相同，但平均查找长度不一定相同lang=EN-US
D:其形态均相同，平均查找长度也都相同

若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上lang=EN-US
A:操作的有限集合
B:映象的有限集合
C:类型的有限集合
D:关系的有限集合

设一个栈的输入序列为12345，则借助一个栈所得到的输出序列不可能是lang=EN-US
A:23415
B:54132
C:23145
D:15432

假设一棵完全二叉树按层次遍历的顺序依次存放在数组BT[m]中，其中根结点存放在BT[0]，若BT[i]中的结点有左孩子，则左孩子存放在lang=EN-US
A:BT[i/2]
B:BT[2*i-1]
C:BT[2*i]
D:BT[2*i 1]

已知一棵树的前序序列为ABCDEF，后序序列为CEDFBA，则对该树进行层次遍历得到的序列为lang=EN-US
A:ABCDEF
B:ABCEFD
C:ABFCDE
D:ABCDFE

对长度为n的关键字序列进行堆排序的空间复杂度为
A:O（log2n）
B:O（1）
C:O（n）
D:O（n*log2n）

若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不可能出现的出栈序列是
A:2，4，3，1，5，6
B:3，2，4，1，6，5
C:4，3，2，1，5，6
D:2，3，5，1，6，4

用有向无环图描述表达式(A B)*((A B)/A)，至少需要顶点的数目为
A:5
B:6
C:8
D:9

for（i=0；ilt;m；i  ）for（j=0；jlt;t；j  ）c［i］［j］=0；for（i=0；ilt;m；i  ）for（j=0；jlt;t；j  ）for（k=0；klt;n；k  ）c［i］［j］=c［i］［j］ a［i］［k］*b［k］［j］；上列程序的时间复杂度为
A:O（m ntimes;t）
B:O（m n t）
C:O（mtimes;ntimes;t）
D:O（mtimes;t n）

引入二叉线索树的目的是lang=EN-US
A:加快查找结点的前驱或后继的速度lang=EN-US
B:为了能在二叉树中方便的进行插入与删除
C:为了能方便的找到双亲lang=EN-US
D:使二叉树的遍历结果唯一

采用ISAM或VSAM组织的文件是lang=EN-US
A:索引非顺序文件
B:顺序文件
C:索引顺序文件
D:散列文件

下面哪一方法可以判断出一个有向图是否有回路
A:深度优先遍历
B:求关键路径
C:求最短路径
D:A和C

在计算机内实现递归算法时所需的辅助数据结构是
A:栈
B:队列
C:树
D:图