《数据结构》东师17秋在线作业12
数据结构17秋在线作业1
一、单选题:【20道,总分:60分】
1.堆的形状是一棵( )。 (满分:3)
A. 二叉排序树
B. 满二叉树
C. 完全二叉树
D. AVL树
2.数组A 的每个元素占5个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A 的地址是( )。 (满分:3)
A. 1165
B. 1170
C. 1175
D. 1180
3.设有n个结点的二叉排序树，对于成功的查找，最少的比较次数为( )。 (满分:3)
A. Ο( 1 )
B. Ο(log2n)
C. Ο(n)
D. Ο(nlog2n)
4.已知一个顺序存储的线性表，设每个结点占c个单元，若第一个结点的地址为LOC(a0)，则第i个结点的地址为( )。 (满分:3)
A. LOC(a0)+(i-1)*c
B. LOC(a0)+i*c
C. LOC(a0)-i*c
D. LOC(a0)+(i+1)*c
5.一个算法应该是( )。 (满分:3)
A. 程序
B. 问题求解步骤的描述
C. 要满足五个基本特性
D. A和C
6.对下列四种排序方法，在排序中关键字比较次数同记录初始排列无关的是( )。 (满分:3)
A. 直接插入排序
B. 冒泡排序
C. 快速排序
D. 归并排序
7.设有100个关键字，用折半查找法进行查找时，最小比较次数为( )。 (满分:3)
A. 7
B. 4
C. 2
D. 1
8.完全二叉树是下列情况的哪一种( )。 (满分:3)
A. 一定是满二叉树
B. 可能是满二叉树
C. 一定不是满二叉树
D. 不是二叉树
9.在下列排序算法中，哪一个算法的时间复杂度与记录初始排列无关( )。 (满分:3)
A. 直接插入排序
B. 冒泡排序
C. 快速排序
D. 直接选择排序
10.判断线索二叉树中某结点p有右子女的条件是( )。 (满分:3)
A. p->rtag = = 0
B. p->rtag = = 1
C. p ! = NULL
D. p->lchild ! = NULL
11.若X是中序线索二叉树中一个有右子女的结点，且X不为根，则X的中序后继为( )。 (满分:3)
A. X的双亲
B. X的右子树中最左下的结点
C. X的左子树中最右下的结点
D. X的右子树中最左下的叶结点
12.一棵左子树为空的二叉树在前序线索化后，其中空的链域的个数是：( )。 (满分:3)
A. 不确定
B. 0
C. 1
D. 2
13.若一组记录的排序码为 { 46,79,56,38,40,84 }，则利用堆排序的方法建立的初始堆为( )。 (满分:3)
A. 79,46,56,38,40,84
B. 84,79,56,38,40,46
C. 84,79,56,46,40,38
D. 84,56,79,40,46,38
14.下面说法不正确的是( )。 (满分:3)
A. 广义表的表头总是一个广义表
B. 广义表的表尾总是一个广义表
C. 广义表常采用链接存储结构
D. 广义表可以是一个多层次的结构
15.采用邻接表存储的图的广度优先遍历类似于二叉树的( )。 (满分:3)
A. 前序遍历
B. 中序遍历
C. 后序遍历
D. 层次遍历
16.下面关于串的叙述中，哪一个是不正确的?( ) (满分:3)
A. 串是字符的有限序列
B. 空串是由空格构成的串
C. 模式匹配是串的一种重要运算
D. 串既可以采用顺序存储，也可以采用链式存储
17.插入、删除只能在同一端进行的线性表，称为( )。 (满分:3)
A. 队列
B. 循环队列
C. 栈
D. 循环栈
18.在数据结构中，从逻辑上可以把数据结构分成( )。 (满分:3)
A. 动态结构和静态结构
B. 紧凑结构和非紧凑结构
C. 线性结构和非线性结构
D. 内部结构和外部结构
19.对于3个结点a、b、c，可构成二叉树的不同形态数为( )。 (满分:3)
A. 3
B. 4
C. 5
D. 6
20.求顶点间的最短路径问题，考虑的是下面的哪一种图( )。 (满分:3)
A. 无向图
B. 有向图
C. 带权的无向图
D. 带权的有向图
二、判断题:【20道,总分:40分】
1.哈希法(散列法)的平均查找长度不随表中结点数目的增加而增加，而是随负载因子的增大而增大。 (满分:2)
A. 错误
B. 正确
2.一个有向图的邻接表和逆邻接表中结点的个数可能不等。 (满分:2)
A. 错误
B. 正确
3.数据的存储(物理)结构是指数据在计算机内的实际存储形式。 (满分:2)
A. 错误
B. 正确
4.连通图的各边权值均不相同，则该图的最小生成树是唯一的。 (满分:2)
A. 错误
B. 正确
5.顺序查找法适用于存储结构为顺序或链接存储的线性表。 (满分:2)
A. 错误
B. 正确
6.倒排文件是对次关键字建立索引。 (满分:2)
A. 错误
B. 正确
7.广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表。 (满分:2)
A. 错误
B. 正确
8.二叉树结点的中序遍历序列与后序遍历序列可以唯一地确定该棵二叉树。 (满分:2)
A. 错误
B. 正确
9.内部排序要求数据一定要以顺序方式进行存储。 (满分:2)
A. 错误
B. 正确
10.对一棵二叉排序树按中序方法遍历得到的结点序列是从小到大的序列。 (满分:2)
A. 错误
B. 正确
11.哈希表与哈希文件的唯一区别是哈希文件引入了“桶”的概念。 (满分:2)
A. 错误
B. 正确
12.将森树转成二叉树，根结点没有左子树。 (满分:2)
A. 错误
B. 正确
13.消除递归不一定需要使用栈。 (满分:2)
A. 错误
B. 正确
14.树与二叉树是两种不同的树形结构。 (满分:2)
A. 错误
B. 正确
15.任何二叉树的后序线索树进行后序遍历时都必须用栈。 (满分:2)
A. 错误
B. 正确
16.归并排序的辅助存储空间代价为O(1 )。 (满分:2)
A. 错误
B. 正确
17.在图G的最小生成树T中，可能会有某条边的权值超过未选边的权值。 (满分:2)
A. 错误
B. 正确
18.程序一定是算法。 (满分:2)
A. 错误
B. 正确
19.若一个有向图的邻接矩阵对角线以下的元素均为零，则该图的拓扑有序序列必定存在。 (满分:2)
A. 错误
B. 正确
20.链接存储结构属静态存储方式。 (满分:2)
A. 错误
B. 正确
数据结构17秋在线作业2
一、单选题:【20道,总分:60分】
1.顺序表中逻辑上相邻的结点其物理位置也( )。 (满分:3)
A. 一定相邻
B. 不必相邻
C. 按某种规律排列
D. 无要求
2.B+ 树应用在( ) 文件系统中。 (满分:3)
A. ISAM
B. VSAM
C. 顺序
D. 散列
3.采用邻接表存储的图的广度优先遍历类似于二叉树的( )。 (满分:3)
A. 前序遍历
B. 中序遍历
C. 后序遍历
D. 层次遍历
4.非线性结构的逻辑特征是一个结构可能有( )。 (满分:3)
A. 一个前驱和一个后继
B. 多个前驱和一个后继
C. 一个前驱和多个后继
D. 多个前驱和多个后继
5.一个顺序栈一旦被说明，其占用空间的大小( )。 (满分:3)
A. 可以改变
B. 不能固定
C. 已固定
D. 动态变化
6.在排序方法中，从未排序序列中挑选记录，并将其依次放入已排序序列(初始时为空)的一端的方法，称为( )。 (满分:3)
A. 希尔排序
B. 插入排序
C. 归并排序
D. 选择排序
7.如果BT是由有序树T转换而来的二叉树，那么T中结点的后根序列就是BT中结点的( ) 序列。 (满分:3)
A. 前序
B. 中序
C. 后序
D. 层次次序
8.由3个结点可以构造出多少种不同形态的有向树？( ) (满分:3)
A. 2
B. 3
C. 4
D. 5
9.有n个顶点的无向图的边数最多为( )。 (满分:3)
A. n
B. n(n-1)
C. n(n-1)/2
D. 2n
10.折半查找要求结点( )。 (满分:3)
A. 无序、顺序存储
B. 无序、链接存储
C. 有序、顺序存储
D. 有序、链接存储
11.广义表A=(a, b,( c, d ) ,(e，( f , g ) ) )，则式子head( tail( head( tail( tail( A ) ) ) ) )的值为( )。 (满分:3)
A.( g )
B.( d )
C. c
D. d
12.顺序存储结构的优点是( )。 (满分:3)
A. 存储密度大
B. 插入运算方便
C. 删除运算方便
D. 结构可动态变化
13.设有n个结点的AVL树，其平均查找长度为( )。 (满分:3)
A. Ο( 1 )
B. Ο(log2n)
C. Ο(n)
D. Ο(nlog2n)
14.若设根结点的层数为0，则高(或深)度为4的二叉树至多含有的结点数为( )。 (满分:3)
A. 10
B. 16
C. 31
D. 32
15.head指向的不带表头结点的单链表为空的判定条件是( )。 (满分:3)
A. head = = NULL
B. head->next = = head
C. head ! = NULL
D. head->next = = NULL
16.设根结点层次为1，某二叉树的结点前序序列和后序序列正好相反，则该二叉树一定是( )。 (满分:3)
A. 空或只有一个结点
B. 高度等于其结点数
C. 任一结点无左子女
D. 任一结点无右子女
17.若有向图的邻接矩阵中，主对角线以下元素均为零，则该图的拓扑有序序列( )。 (满分:3)
A. 存在
B. 不存在
C. 不一定存在
D. 可能不存在
18.在链队列中，假设f和r分别为队首和队尾指针，则删除一个结点的操作是( )。 (满分:3)
A. r = f->next;
B. r = r->next;
C. f = f->next;
D. f = r->next;
19.下列说法不正确的是( )。 (满分:3)
A. 图的遍历是从给定的源点出发每个顶点仅被访问一次
B. 遍历的基本方法有两种：深度优先遍历和广度优先遍历
C. 图的深度优先遍历不适用于有向图
D. 图的深度优先遍历是一个递归过程
20.有n个顶点的无向连通图的边数最少为( )。 (满分:3)
A. n/2
B. n-1
C. n
D. n+1
二、判断题:【20道,总分:40分】
1.后序线索二叉树是不完善的，要对它进行遍历，还需要使用栈。 (满分:2)
A. 错误
B. 正确
2.在对n个元素的序列进行排序时，堆排序所需要的附加存储空间是O(n)。 (满分:2)
A. 错误
B. 正确
3.带权的连通无向图的最小(代价)生成树必是唯一的。 (满分:2)
A. 错误
B. 正确
4.任何二叉树的后序线索树进行后序遍历时都必须用栈。 (满分:2)
A. 错误
B. 正确
5.二叉树只能用二叉链表表示。 (满分:2)
A. 错误
B. 正确
6.两个栈共用静态存储空间，对接使用方式减少了空间溢出的可能性。 (满分:2)
A. 错误
B. 正确
7.顺序查找法适用于存储结构为顺序或链接存储的线性表。 (满分:2)
A. 错误
B. 正确
8.在待排数据基本有序的情况下，快速排序效果最好。 (满分:2)
A. 错误
B. 正确
9.串只能按顺序存储方式进行存储。 (满分:2)
A. 错误
B. 正确
10.完全二叉树一定存在度为1的结点。 (满分:2)
A. 错误
B. 正确
11.空串是由空格构成的串。 (满分:2)
A. 错误
B. 正确
12.结点(数据元素)是数据的最小单位。 (满分:2)
A. 错误
B. 正确
13.归并排序在任何情况下都比所有简单的排序方法速度快。 (满分:2)
A. 错误
B. 正确
14.链表中的表头指针与表头结点起到不同的作用。 (满分:2)
A. 错误
B. 正确
15.循环队列也存在空间溢出问题。 (满分:2)
A. 错误
B. 正确
16.数据的逻辑结构说明数据元素之间的顺序关系，它依赖于计算机的存储结构。 (满分:2)
A. 错误
B. 正确
17.有向图的邻接矩阵是对称的。 (满分:2)
A. 错误
B. 正确
18.两个栈共用静态存储空间，对接使用方式也存在空间溢出问题。 (满分:2)
A. 错误
B. 正确
19.数据的逻辑结构是指数据的各数据项之间的逻辑关系。 (满分:2)
A. 错误
B. 正确
20.无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵。 (满分:2)
A. 错误
B. 正确
页:
[1]