东北大学15秋《数据结构Ⅰ》在线作业答案
东北大学15秋《数据结构Ⅰ》在线作业1试卷总分：100 测试时间：--
一、单选题（共20道试题，共100分。）
1.上溢现象通常出现在
A. 顺序栈的入栈操作过程中
B.顺序栈的出栈操作过程中
C. 链栈的入栈操作过程中
D.链栈的出栈操作过程中
满分：5分
2.
在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系
A.不一定相同
B.都相同
C. 都不相同
D. 互为逆序
满分：5分
3.
带行表的三元组表是稀疏矩阵的一种
A.顺序存储结构
B. 链式存储结构
C.索引存储结构
D.散列存储结构
满分：5分
4.
在平衡二叉树中插入一个结点后引起了不平衡，设最低(最接近于叶子)的不平衡点是A，并已知A的左、右孩子的平衡因子分别为-1和0，则应进行的平衡旋转是
A.LL型
B. LR型
C. RL型
D.RR型
满分：5分
5.
抽象数据类型的三个组成部分分别为
A.数据对象、数据关系和基本操作
B. 数据元素、逻辑结构和存储结构
C. 数据项、数据元素和数据类型
D. 数据元素、数据结构和数据类型
满分：5分
6.
计算机识别、存储和加工处理的对象被统称为
A.数据
B.数据元素
C. 数据结构
D.数据类型
满分：5分
7.
若采用孩子兄弟链表作为树的存储结构，则树的后序遍历应采用二叉树的
A. 层次遍历算法
B.前序遍历算法
C. 中序遍历算法
D.后序遍历算法
满分：5分
8.
导致栈上溢的操作是
A.
栈满时执行的出栈
B. 栈满时执行的入栈
C.
栈空时执行的出栈
D. 栈空时执行的入栈
满分：5分
9.
若允许表达式内多种括号混合嵌套，则为检查表达式中括号是否正确配对的算法，通常选用的辅助结构是
A.
栈
B.线性表
C.
队列
D.二叉排序树
满分：5分
10.
对长度为n的关键字序列进行堆排序的空间复杂度为
A.
O（log2n）
B. O（1）
C.
O（n）
D.O（n*log2n）
满分：5分
11.
链栈与顺序栈相比，比较明显的优点是
A.
插入操作更加方便
B. 删除操作更加方便
C.
不会出现下溢的情况
D. 不会出现上溢的情况
满分：5分
12.
连通图是指图中任意两个顶点之间
A. 都连通的无向图
B. 都不连通的无向图
C.都连通的有向图
D.都不连通的有向图
满分：5分
13.
一棵具有 n个结点的完全二叉树的树高度（深度）是
A. logn+1
B. logn+1
C.logn
D.logn-1
满分：5分
14.
连通网的最小生成树是其所有生成树中
A.顶点集最小的生成树
B. 边集最小的生成树
C. 顶点权值之和最小的生成树
D.边的权值之和最小的生成树
满分：5分
15.
以下属于逻辑结构的是
A.
顺序表
B.哈希表
C.有序表
D. 单链表
满分：5分
16.
设有一个顺序栈，6个元素1、2 、3、4、5、6依次入栈，如果6个元素出栈的顺序是2、3、4、6、5、1，则栈的容量至少应该是
A. 2
B. 3
C. 5
D. 6
满分：5分
17.
无向图中一个顶点的度是指图中
A.通过该顶点的简单路径数
B. 与该顶点相邻接的顶点数
C. 通过该顶点的回路数
D. 与该顶点连通的顶点数
满分：5分
18.
以下与数据的存储结构无关的术语是
A.
循环队列
B.链表
C. 哈希表
D. 栈
满分：5分
19.
若要在单链表中的结点p之后插入一个结点s，则应执行的语句是
A.s->next=p->next; p->next=s;
B. p->next=s; s->next=p->next;
C.p->next=s->next; s->next=p;
D. s->next=p; p->next=s->next;
满分：5分
20.
为便于判别有向图中是否存在回路，可借助于
A. 广度优先搜索算法
B. 最小生成树算法
C.最短路径算法
D.拓扑排序算法
满分：5分15秋学期《数据结构Ⅰ》在线作业2
试卷总分：100 测试时间：--
一、单选题（共20道试题，共100分。）
1.
将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是
A. n
B. 2n-1
C. 2n
D. n-1
满分：5分
2.
以下属于逻辑结构的是
A.
顺序表
B.哈希表
C.有序表
D. 单链表
满分：5分
3.
通常将链串的结点大小设置为大于1是为了
A.
提高串匹配效率
B. 提高存储密度
C.
便于插入操作
D. 便于删除操作
满分：5分
4.
带行表的三元组表是稀疏矩阵的一种
A.顺序存储结构
B. 链式存储结构
C.索引存储结构
D.散列存储结构
满分：5分
5.
如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是
A. 栈
B.队列
C. 树
D.图
满分：5分
6.
在关键字序列(12，23，34，45，56，67，78，89，91)中二分查找关键字为45、89和12的结点时，所需进行的比较次数分别为
A. 4，4，3
B.4，3，3
C.3，4，4
D. 3，3，4
满分：5分
7.
以下说法不正确的是
A.无向图中的极大连通子图称为连通分量
B.连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点
C. 图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点
D. 有向图的遍历不可采用广度优先搜索
满分：5分
8.
有关二叉树下列说法正确的是
A. 二叉树的度为2
B. 一棵二叉树的度可以小于2
C. 二叉树中至少有一个结点的度为2
D. 二叉树中任何一个结点的度都为2
满分：5分
9.
能进行二分查找的线性表,必须以
A.顺序方式存储,且元素按关键字有序
B. 链式方式存储,且元素按关键字有序
C.顺序方式存储,且元素按关键字分块有序
D.链式方式存储,且元素按关键字分块有序
满分：5分
10.
下列数据结构中，属于非线性数据结构的是
A.
栈
B. 队列
C. 完全二叉树
D.堆
满分：5分
11.
用有向无环图描述表达式(A+B)*((A+B)/A)，至少需要顶点的数目为
A. 5
B. 6
C. 8
D. 9
满分：5分
12.
若度为m的哈夫曼树中，其叶结点个数为n，则非叶结点的个数为
A. n-1
B.n/m-1
C.
é(n-1)/(m-1)ù
D. én/(m-1)ù-1
满分：5分
13.
下面哪一方法可以判断出一个有向图是否有回路
A.
深度优先遍历
B. 求关键路径
C.
求最短路径
D. A和C
满分：5分
14.
执行下列程序段后，串X的值为
S=〞abcdefgh〞; T=〞xyzw〞;
substr (X,S,2,strlen(T));
substr (Y,S, stelen(T),2);
strcat (X,Y);
A.
〞cdefgh〞
B.〞cdxyzw〞
C.
〞cdefxy〞
D. 〞cdefef〞
满分：5分
15.
对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为
A. O(n)O(n)
B. O(n)O(1)
C.
O(1)O(n)
D. O(1) O(1)
满分：5分
16.
栈是一种操作受限的线性结构，其操作的主要特征是
A.
先进先出
B. 后进先出
C.
进优于出
D. 出优于进
满分：5分
17.
适宜进行批量处理的文件类型是
A. 顺序文件
B. 索引顺序文件
C. 散列文件
D. 多关键字文件
满分：5分
18.
在一个带权连通图G中，权值最小的边一定包含在G的
A. 最小生成树中
B.深度优先生成树中
C. 广度优先生成树中
D. 深度优先生成森林中
满分：5分
19.
在目标串T［0..n-1］=″xwxxyxy″中，对模式串P［0..m-1］=″xy″进行子串定位操作的结果是
A. 0
B. 2
C. 3
D. 5
满分：5分
20.
二维数组A的每个元素是由6个字符组成的串，其行下标i=0，l，…，8，列下标为j=1，2．…．10。设每个字符占一个字节,若按行先存储，元素A的起始地址与A按列存储时起始地址相同的元素是
A. A
B. A
C.
A
D.A
满分：5分15秋学期《数据结构Ⅰ》在线作业3
试卷总分：100 测试时间：--
一、单选题（共20道试题，共100分。）
1.
采用ISAM或VSAM组织的文件是
A. 索引非顺序文件
B. 顺序文件
C.索引顺序文件
D.散列文件
满分：5分
2.
. 对长度为15的有序顺序表进行二分查找，在各记录的查找概率均相等的情况下，查找成功时所需进行的关键字比较次数的平均值为
A.39/15
B. 49/15.
C. 51/15
D.55/15
满分：5分
3.
假设一棵完全二叉树按层次遍历的顺序依次存放在数组BT中，其中根结点存放在BT，若BT中的结点有左孩子，则左孩子存放在
A.BT
B. BT
C. BT
D. BT
满分：5分
4.
for（i=0；i<m；i++）
for（j=0；j<t；j++）
c［i］［j］=0；
for（i=0；i<m；i++）
for（j=0；j<t；j++）
for（k=0；k<n；k++）
c［i］［j］=c［i］［j］+a［i］［k］*b［k］［j］；
上列程序的时间复杂度为
A. O（m+n×t）
B. O（m+n+t）
C. O（m×n×t）
D. O（m×t+n）
满分：5分
5.
BFS算法可用来解决单源最短路径问题的条件是当各边上的权值
A.
均相等
B.均互不相等
C.
不一定相等
D. 任意值
满分：5分
6.
高度为5的完全二叉树中含有的结点数至少为
A. 16
B. 17
C. 31
D. 32
满分：5分
7.
下列序列中，不构成堆的是
A.
（1，2，5，3，4，6，7，8，9，10）
B.
（10，5，8，4，2，6，7，1，3）
C.
（10，9，8，7，3，5，4，6，2）
D.
（1，2，3，4，10，9，8，7，6，5）
满分：5分
8.
多维数组之所以有行优先顺序和列优先顺序两种存储方式是因为
A.
数组的元素处在行和列两个关系中
B. 数组的元素必须从左到右顺序排列
C.
数组的元素之间存在次序关系
D.数组是多维结构，内存是一维结构
满分：5分
9.
用二叉链表表示具有n个结点的二叉树时，值为空的指针域的个数为
A. n-1
B. n
C. n+1
D. 2n
满分：5分
10.
在线性表的下列运算中，不改变数据元素之间结构关系的运算是
A. 插入
B. 删除
C. 排序
D.查找
满分：5分
11.
导致栈上溢的操作是
A.
栈满时执行的出栈
B. 栈满时执行的入栈
C.
栈空时执行的出栈
D. 栈空时执行的入栈
满分：5分
12.
判断两个串大小的基本准则是
A.
两个串长度的大小
B. 两个串中首字符的大小
C.
两个串中大写字母的多少
D. 对应的第一个不等字符的大小
满分：5分
13.
可有效提高次关键字查找效率的文件是
A.顺序文件
B. 倒排文件
C.散列文件
D.VSAM文件
满分：5分
14.
若<vi, vj>是有向图的一条边，则称
A.vi邻接于vj
B.vj邻接于vi
C.vi和vj相互邻接
D. vi与vj-不相邻接
满分：5分
15.
某二叉树中序序列为A,B,C,D,E,F,G，后序序列为B,D,C,A,F,G,E 则该二叉树对应的森林包括的树的棵树是
A. 1
B. 2
C. 3
D. 概念上是错误的
满分：5分
16.
在一个单链表中，已知q结点是p结点的前驱结点，若在q 和p之间插入结点s，则执行操作
A. s->next=p->next;p->next=s;
B. s->next=p; q->next=s
C. q->next=s;s->next=p; D. p->next=s;s->next=q;
D. q->next=s;s->next=p; D. p->next=s;s->next=q;
满分：5分
17.
下面说法错误的是
(1）算法原地工作的含义是指不需要任何额外的辅助空间
（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法
（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界
（4）同一个算法，实现语言的级别越高，执行效率就越低
A.
(1)
B. (1),(2)
C.
(1),(4)
D.(3)
满分：5分
18.
n个顶点的有向完全图中含有向边的数目最多为
A.
n-1
B. n
C.
n(n-1)/2
D.n(n-1)
满分：5分
19.
对有18个元素的有序表作二分查找，则查找A的比较序列的下标为
A.1，2，3
B. 9，5，2，3
C. 9，5，3
D. 9，4，2，3
满分：5分
20.
若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，
再加入两个元素后，rear和front的值分别为
A.1和 5
B.2和4
C.
4和2
D. 5和1
满分：5分
页:
[1]