数据结构19春在线作业2-0005

adminhan

下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响的是 ()。
A:直接插入排序
B:快速排序
C:直接选择排序
D:堆排序

设有100个关键字，用折半查找法进行查找时，最大比较次数为 ()。
A:6
B:7
C:25
D:50

堆的形状是一棵 ( )。
A:二叉排序树
B:满二叉树
C:完全二叉树
D:AVL树

在查找过程中，若同时还要做增、删工作，这种查找则称为 ()。
A:静态查找
B:动态查找
C:内查找
D:外查找

内排序方法的稳定性是指 ()。
A:该排序算法不允许有相同的关键字记录
B:该排序算法允许有相同的关键字记录
C:平均时间为O(nlog2n ) 的排序方法
D:以上都不对

有n个顶点的无向图的边数最多为 ()。
A:n
B:n(n-1)
C:n(n-1)/2
D:2n

在数据结构中，从逻辑上可以把数据结构分成 ( )。
A:动态结构和静态结构
B:紧凑结构和非紧凑结构
C:线性结构和非线性结构
D:内部结构和外部结构

下面关于算法说法错误的是（）。
A:算法最终必须由计算机程序实现
B:为解决某问题的算法同为该问题编写的程序含义是相同的
C:算法的可行性是指指令不能有二义性
D:以上几个都是错误的

一个有向无环图的拓扑排序序列 () 是唯一的。
A:一定
B:不一定
C:可能
D:三者均不对

设根结点层次为1，某二叉树的结点前序序列和后序序列正好相反，则该二叉树一定是 ( )。
A:空或只有一个结点
B:高度等于其结点数
C:任一结点无左子女
D:任一结点无右子女

就排序算法所用的辅助空间而言，堆排序、快速排序、归并排序的关系是 () 。
A:堆排序＜快速排序＜归并排序
B:堆排序＜归并排序＜快速排序
C:堆排序＞归并排序＞快速排序
D:堆排序＞快速排序＞归并排序

下述文件中适合于磁带存储的是 ()。
A:顺序文件
B:索引文件
C:散列文件
D:多关键字文件

排序趟数与序列的原始状态有关的排序方法是 () 排序法。
A:直接插入
B:直接选择
C:冒泡
D:归并

在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在p之前插入s所指结点，则执行 ( )。
A:p->next = s; s->next = q;
B:s->next = p->next; p->next = s;
C:p->next = s->next; s->next = p;
D:q->next = s; s->next = p;

在查找过程中，仅进行查找操作，没有引起表本身的改动，这种查找则称为 ()。
A:静态查找
B:动态查找
C:内查找
D:外查找

下面说法不正确的是 ()。
A:广义表的表头总是一个广义表
B:广义表的表尾总是一个广义表
C:广义表常采用链接存储结构
D:广义表可以是一个多层次的结构

一棵左子树为空的二叉树在前序线索化后，其中空的链域的个数是：( )。
A:不确定
B:0
C:1
D:2

下列序列中，() 是执行第一趟按递减序快速排序后所得的序列。
A:[ 68, 11 , 18 , 69 ] 70 [ 23 , 93 , 73]
B:[ 68 , 11 , 69 , 23 ] 70 [18, 93, 73 ]
C:[ 93, 73 ]  70  [ 68, 11, 69, 23, 18 ]
D:[ 68 , 11 , 69, 23, 18 ] 70 [ 93, 73 ]

下列排序算法中，其中 () 是稳定的。
A:堆排序，起泡排序
B:快速排序，堆排序
C:归并排序，起泡排序
D:直接选择排序，归并排序

由3个结点可以构造出多少种不同形态的有向树？( )
A:2
B:3
C:4
D:5

对n个记录的文件进行堆排序，最坏情况下的执行时间是O(nlog2n )。
A:错误
B:正确

在平衡的二叉排序树中，向某个平衡因子不为零的结点的树中插入一新结点，必引起平衡旋转。
A:错误
B:正确

排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。
A:错误
B:正确

有向图的邻接矩阵是对称的。
A:错误
B:正确

串是一种数据对象和操作都特殊的线性表。
A:错误
B:正确

两个栈共用静态存储空间，对接使用方式也存在空间溢出问题。
A:错误
B:正确

堆是完全二叉树。
A:错误
B:正确

完全二叉树肯定是平衡二叉排序树。
A:错误
B:正确

一个有向图的邻接表和逆邻接表中结点的个数可能不等。
A:错误
B:正确

二叉树是度为2的有序树。
A:错误
B:正确

一个广义表可以为其他广义表所共享。
A:错误
B:正确

任何一个递归过程都可以转换成非递归过程。
A:错误
B:正确

快速排序总比简单的排序方法快。
A:错误
B:正确

若一个广义表的表头为空表，则此广义表亦为空表。
A:错误
B:正确

归并排序的辅助存储空间代价为O(1 )。
A:错误
B:正确

顺序存储结构的主要缺点是不利于插入、删除操作。
A:错误
B:正确

完全二叉树的存储结构通常采用顺序存储结构。
A:错误
B:正确

就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大
A:错误
B:正确

链表中的表头结点使得插入、删除操作简单。
A:错误
B:正确

虽然关键字序列的顺序不一样，但依此生成的二叉排序树却是一样的。
A:错误
B:正确