东北大学13秋《数据结构Ⅱ》在线作业答案
东北大学13秋学期《数据结构Ⅱ》在线作业1试卷总分：100 测试时间：--
一、单选题（共20道试题，共100分。）
1.
下面说法错误的是
(1）算法原地工作的含义是指不需要任何额外的辅助空间
（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法
（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界
（4）同一个算法，实现语言的级别越高，执行效率就越低
A.
(1)
B.
(1),(2)
C.
(1),(4)
D.
(3)
满分：5分
2.
ISAM文件的周期性整理是为了空出
A. 磁道索引
B. 柱面索引
C.
柱面基本区
D.
柱面溢出区
满分：5分
3.
由同一关键字集合构造的各棵二叉排序树
A.其形态不一定相同，但平均查找长度相同
B.
其形态不一定相同，平均查找长度也不一定相同
C.
其形态均相同，但平均查找长度不一定相同
D.
其形态均相同，平均查找长度也都相同
满分：5分
4.
下面的说法中正确的是
(1)任何一棵二叉树的叶子节点在三种遍历中的相对次序不变。
(2)按二叉树定义，具有三个节点的二叉树共有6种。
A.
(1)，(2)
B.
(1)
C.
(2)
D.
(1)，(2)都错
满分：5分
5.
除第一层外，满二叉树中每一层结点个数是上一层结点个数的
A. 1/2倍
B. 1倍
C.
2倍
D.
3倍
满分：5分
6.
算法的时间复杂度主要取决于
A.
问题的规模
B.
待处理数据的初态
C.
难度
D.
A和B
满分：5分
7.
有关二叉树下列说法正确的是
A. 二叉树的度为2
B. 一棵二叉树的度可以小于2
C.
二叉树中至少有一个结点的度为2
D.
二叉树中任何一个结点的度都为2
满分：5分
8.
若在9阶B-树中插入关键字引起结点分裂，则该结点在插入前含有的关键字个数为
A. 4
B. 5
C. 8
D. 9
满分：5分
9.
若一个有向图的邻接距阵中,主对角线以下的元素均为零,则该图的拓扑有序序列
A.
一定存在
B.
一定不存在
C.
不一定存在
D.
不确定
满分：5分
10.
一个具有1025个结点的二叉树的高h为
A. 11
B. 10
C.
11至1025之间
D.10至1024之间
满分：5分
11.
在具有n个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是
A. O(1)
B. O(n)
C.
O(nlogn)
D.
O(n2)
满分：5分
12.
如果求一个连通图中以某个顶点为根的高度最小的生成树，应采用
A.深度优先搜索算法
B.广度优先搜索算法
C.
求最小生成树的prim算法
D.拓扑排序算法
满分：5分
13.
一棵具有 n个结点的完全二叉树的树高度（深度）是
A. logn+1
B.logn+1
C.logn
D.logn-1
满分：5分
14.
将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是
A.
n
B.
2n-1
C.
2n
D.
n-1
满分：5分
15.
若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则节省时间的存储方式是
A.
顺序表
B.
双链表
C.
带头结点的双循环链表
D.
单循环链表
满分：5分
16.
在长度为n的顺序表的第i(1≤i≤n+1)个位置上插入一个元素，元素的移动次数为
A.n-i+1
B.n-i
C.i
D.i-1
满分：5分
17.
在计算机内实现递归算法时所需的辅助数据结构是
A.
栈
B.
队列
C.
树
D.
图
满分：5分
18.
下述哪一条是顺序存储结构的优点
A.
存储密度大
B.
插入运算方便
C.
删除运算方便
D.
可方便地用于各种逻辑结构的存储表示
满分：5分
19.
在用邻接表表示图时，拓扑排序算法时间复杂度为
A.
O(n)
B.
O(n＋e)
C.
O(n*n)
D.
O(n*n*n)
满分：5分
20.
在分块索引的在顺序表中查找，算法中采用的最佳技术是
A.
穷举法
B.
贪心法
C.
分治法
东北大学13秋学期《数据结构Ⅱ》在线作业3
试卷总分：100 测试时间：--
一、单选题（共20道试题，共100分。）
1.
下列编码中属于前缀编码的是
A.{1,01,000,001}
B. {1,01,011,010}
C.
{0,10,110,11}
D. {0,1,00,11}
满分：5分
2.
以下数据结构中，属于线性结构的是
A.
广义表
B.
二叉树
C.
稀疏矩阵
D.
串
满分：5分
3.
数据结构中所定义的数据元素，是用于表示数据的
A.最小单位
B. 最大单位
C.
基本单位
D.
不可分割的单位
满分：5分
4.
有关二叉树下列说法正确的是
A. 二叉树的度为2
B. 一棵二叉树的度可以小于2
C.
二叉树中至少有一个结点的度为2
D.
二叉树中任何一个结点的度都为2
满分：5分
5.
多维数组之所以有行优先顺序和列优先顺序两种存储方式是因为
A.
数组的元素处在行和列两个关系中
B.
数组的元素必须从左到右顺序排列
C.
数组的元素之间存在次序关系
D.
数组是多维结构，内存是一维结构
满分：5分
6.
若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则x的前驱为
A.X的双亲
B.X的右子树中最左的结点
C.
X的左子树中最右结点
D.
X的左子树中最右叶结点
满分：5分
7.
在一个带权连通图G中，权值最小的边一定包含在G的
A. 最小生成树中
B. 深度优先生成树中
C.
广度优先生成树中
D.
深度优先生成森林中
满分：5分
8.
无向图中一个顶点的度是指图中
A. 通过该顶点的简单路径数
B. 与该顶点相邻接的顶点数
C. 通过该顶点的回路数
D. 与该顶点连通的顶点数
满分：5分
9.
倒排文件的主要优点是
A. 便于进行插入和删除运算
B. 便于进行文件的恢复
C. 便于进行多关键字查询
D.
节省存储空间
满分：5分
10.
一棵具有 n个结点的完全二叉树的树高度（深度）是
A. logn+1
B.logn+1
C.logn
D.logn-1
满分：5分
11.
抽象数据类型的三个组成部分分别为
A. 数据对象、数据关系和基本操作
B. 数据元素、逻辑结构和存储结构
C. 数据项、数据元素和数据类型
D. 数据元素、数据结构和数据类型
满分：5分
12.
在一个单链表中，若删除*p结点的后继结点，则执行操作
A. q=p->next;p->next=q->next;free(q);
B. p=p->next;p->next=p->next->next;free(p);
C.
p->next=q->next;free(p->next);
D. p=p->next->next;free(p->next);
满分：5分
13.
当在二叉排序树中插入一个新结点时，若树中不存在与待插入结点的关键字相同的结点，且新结点的关键字小于根结点的关键字，则新结点将成为
A.左子树的叶子结点
B.左子树的分支结点
C.
右子树的叶子结点
D.
右子树的分支结点
满分：5分
14.
下面关于线性表的叙述中，错误的是
A.
线性表采用顺序存储，必须占用一片连续的存储单元。
B.
线性表采用顺序存储，便于进行插入和删除操作。
C.
线性表采用链接存储，不必占用一片连续的存储单元。
D.
线性表采用链接存储，便于插入和删除操作。
满分：5分
15.
对长度为15的有序顺序表进行二分查找，在各记录的查找概率均相等的情况下，查找成功时所需进行的关键字比较次数的平均值为
A. 39/15
B. 49/15
C. 51/15
D. 55/15
满分：5分
16.
若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则节省时间的存储方式是
A.
顺序表
B.
双链表
C.
带头结点的双循环链表
D.
单循环链表
满分：5分
17.
在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若p->next->next=
head,则
A. p指向头结点
B. p指向尾结点
C. p的直接后继是头结点
D.P的直接后继是尾结点
满分：5分
18.
如果某图的邻接矩阵是对角线元素均为零的上三角矩阵，则此图是
A.有向完全图
B.连通图
C.
强连通图
D.
有向无环图
满分：5分
19.
上溢现象通常出现在
A.
顺序栈的入栈操作过程中
B.
顺序栈的出栈操作过程中
C.
链栈的入栈操作过程中
D.
链栈的出栈操作过程中
满分：5分
20.
在一棵高度为k的满二叉树中，结点总数为
A. 2k-1
B. 2k
C.
2k-1
D.
东北大学13秋学期《数据结构Ⅱ》在线作业2
试卷总分：100 测试时间：--
一、单选题（共20道试题，共100分。）
1.
如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是
A.栈
B.队列
C.
树
D.
图
满分：5分
2.
若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则节省时间的存储方式是
A.
顺序表
B.
双链表
C.
带头结点的双循环链表
D.
单循环链表
满分：5分
3.
下面说法错误的是
(1）算法原地工作的含义是指不需要任何额外的辅助空间
（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法
（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界
（4）同一个算法，实现语言的级别越高，执行效率就越低
A.
(1)
B.
(1),(2)
C.
(1),(4)
D.
(3)
满分：5分
4.
下面的说法中正确的是
(1)任何一棵二叉树的叶子节点在三种遍历中的相对次序不变。
(2)按二叉树定义，具有三个节点的二叉树共有6种。
A.
(1)，(2)
B.
(1)
C.
(2)
D.
(1)，(2)都错
满分：5分
5.
已知一组关键字为{25,48,36,72,79,82,23,40,16,35}，其中每相邻两个为有序子序列。对这些子序列进行一趟两两归并的结果是
A.
.{25,36,48,72,23,40,79,82,16,35}
B.
.{25,36,48,72,16,23,40,79,82,35}
C.
.{25,36,48,72,16,23,35,40,79,82}
D.
.{16,23,25,35,36,40,48,72,79,82}
满分：5分
6.
一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂度为
A.O(n)
B.O(e)
C.
O(n+e)
D.
O(n2)
满分：5分
7.
含n个关键字的二叉排序树的平均查找长度主要取决于
A.关键字的个数
B.树的形态
C.
关键字的取值范围
D.
关键字的数据类型
满分：5分
8.
算法的时间复杂度主要取决于
A.
问题的规模
B.
待处理数据的初态
C.
难度
D.
A和B
满分：5分
9.
快速排序在最坏情况下的时间复杂度是
A.
O(n2log2n)
B.
O(n2)
C.
O(nlog2n)
D.
O(log2n)
满分：5分
10.
引入二叉线索树的目的是
A. 加快查找结点的前驱或后继的速度
B.
为了能在二叉树中方便的进行插入与删除
C.
为了能方便的找到双亲
D.
使二叉树的遍历结果唯一
满分：5分
11.
一个具有1025个结点的二叉树的高h为
A. 11
B. 10
C.
11至1025之间
D.10至1024之间
满分：5分
12.
设有一个顺序栈，6个元素1、2 、3、4、5、6依次入栈，如果6个元素出栈的顺序是2、3、4、6、5、1，则栈的容量至少应该是
A. 2
B. 3
C. 5
D. 6
满分：5分
13.
已知二叉树的先序序列为ABDECF，中序序列为DBEAFC，则后序序列为
A. DEBAFC
B.DEFBCA
C. DEBCFA
D. DEBFCA
满分：5分
14.
若在9阶B-树中插入关键字引起结点分裂，则该结点在插入前含有的关键字个数为
A. 4
B. 5
C. 8
D. 9
满分：5分
15.
若要在O(1)的时间复杂度上实现两个循环链表头尾相接，则应对两个循环链表各设置一个指针，分别指向
A. 各自的头结点
B.各自的尾结点
C. 各自的第一个元素结点
D. 一个表的头结点，另一个表的尾结点
满分：5分
16.
对长度为n的关键字序列进行堆排序的空间复杂度为
A.
O（log2n）
B.
O（1）
C.
O（n）
D.
O（n*log2n）
满分：5分
17.
按排序过程中依据的原则分类，快速排序属于
A.
插入类的排序方法
B.
选择类的排序方法
C.
交换类的排序方法
D.
归并类的排序方法
满分：5分
18.
已知含10个结点的二叉排序树是一棵完全二叉树，则该二叉排序树在等概率情况下查找成功的平均查找长度等于
A. 1.0
B. 2.9
C.
3.4
D.
5.5
满分：5分
19.
若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为
A.O(0)
B. O(1)
C.
O(n)
D. O(n2)
满分：5分
20.
当在二叉排序树中插入一个新结点时，若树中不存在与待插入结点的关键字相同的结点，且新结点的关键字小于根结点的关键字，则新结点将成为
A. 左子树的叶子结点
B. 左子树的分支结点
C.
右子树的叶子结点
D.
右子树的分支结点
满分：5分
页:
[1]