东北大学14春学期《数据结构Ⅱ》在线作业2

14春学期《数据结构Ⅱ》在线作业2
试卷总分：100 奥鹏学习网（aopeng123.cn) 发布
单选题
一、单选题（共 20 道试题，共 100 分。）
V
1.
在具有 n 个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是
A. O(1)
B. O(n)
C.
O(nlogn)
D.
O(n 2 )
需要购买答案的联系QQ:79691519满分：5 分
2.
若数组 s[0..n-1] 为两个栈 s1 和 s2 的共用存储空间，且仅当 s[0..n-1] 全满时，各栈才不能进行进栈操作， 则为这两个栈分配空间的最佳方案是： s1 和 s2 的栈顶指针的初值分别为
A. 1 和 n+1
B. 1 和 n/2
C.
－ 1 和 n
D. － 1 和 n+1
需要购买答案的联系QQ:79691519满分：5 分
3.
将两个各有 n 个元素的有序表归并成一个有序表，其最少的比较次数是
A.
n
B.
2n-1
C.
2n
D.
n-1
需要购买答案的联系QQ:79691519满分：5 分
4.
链栈与顺序栈相比，比较明显的优点是
A.
插入操作更加方便
B.
删除操作更加方便
C.
不会出现下溢的情况
D.
不会出现上溢的情况
此题选: D 满分：5 分
5.
如果某图的邻接矩阵是对角线元素均为零的上三角矩阵，则此图是
A. 有向完全图
B. 连通图
C.
强连通图
D.
有向无环图
此题选: D 满分：5 分
6.
下列序列中，不构成堆的是
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 ）
此题选: D 满分：5 分
7.
稠密索引是在索引表中
A. 为每个记录建立一个索引项
B. 为每个页块建立一个索引项
C. 为每组记录建立一个索引项
D.
为每个字段建立一个索引项
需要购买答案的联系QQ:79691519满分：5 分
8.
下面哪一方法可以判断出一个有向图是否有回路
A.
深度优先遍历
B.
求关键路径
C.
求最短路径
D.
A 和 C
需要购买答案的联系QQ:79691519满分：5 分
9.
数据的四种基本存储结构是指
A. 顺序存储结构、索引存储结构、直接存储结构、倒排存储结构
B. 顺序存储结构、索引存储结构、链式存储结构、散列存储结构
C. 顺序存储结构、非顺序存储结构、指针存储结构、树型存储结构
D. 顺序存储结构、链式存储结构、树型存储结构、图型存储结构
需要购买答案的联系QQ:79691519满分：5 分
10.
深度为 h 的满 m 叉树的第 k 层的结点 (1= k= h) 数有
A. m k-1
B. m k -1
C.
m h-1
D. m h -1
需要购买答案的联系QQ:79691519满分：5 分
11.
在一个单链表中，已知 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;
需要购买答案的联系QQ:79691519满分：5 分
12.
对二叉树从 1 开始进行连续编号，要求每个结点的编号大于其左右孩子的编号，同一个结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用遍历方式是
A. 先序
B. 中序
C. 后序
D. 从根开始的层次遍历
需要购买答案的联系QQ:79691519满分：5 分
13.
已知函数 Sub(s,i,j) 的功能是返回串 s 中从第 i 个字符起长度为 j 的子串，函数 Scopy(s,t) 的功能为复制串 t 到 s 。若字符串 S= ″ SCIENCESTUDY ″，则调用函数 Scopy(P,Sub(S,1,7)) 后得到
A. P= ″ SCIENCE ″
B. P= ″ STUDY ″
C.
S= ″ SCIENCE ″
D.
S= ″ STUDY ″
需要购买答案的联系QQ:79691519满分：5 分
14.
对长度为 n 的关键字序列进行堆排序的空间复杂度为
A.
O （ log 2 n ）
B.
O （ 1 ）
C.
O （ n ）
D.
O （ n*log 2 n ）
需要购买答案的联系QQ:79691519满分：5 分
15.
假设以数组 A[n] 存放循环队列的元素，其头、尾指针分别为 front 和 rear 。若设定尾指针指向队列中的队尾 元素，头指针指向队列中队头元素的前一个位置，则当前存于队列中的元素个数为
A. (rear-front-1) ％ n
B. (rear-front) ％ n
C. (front-rear+1) ％ n
D. (rear-front+n) ％ n
此题选: D 满分：5 分
16.
若以 1234 作为双端队列的输入序列，则既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得 到的输出序列是
A. 1234
B. 4132
C. 4231
D. 4213
需要购买答案的联系QQ:79691519满分：5 分
17.
在按层次遍历二叉树的算法中，需要借助的辅助数据结构是
A. 队列
B. 栈
C. 线性表
D.
有序表
需要购买答案的联系QQ:79691519满分：5 分
18.
当在二叉排序树中插入一个新结点时，若树中不存在与待插入结点的关键字相同的结点，且新结点的关键字小于根结点的关键字，则新结点将成为
A. 左子树的叶子结点
B. 左子树的分支结点
C.
右子树的叶子结点
D.
右子树的分支结点
需要购买答案的联系QQ:79691519满分：5 分
19.
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 ）
需要购买答案的联系QQ:79691519满分：5 分
20.
若一棵二叉树有 11 个叶子结点，则该二叉树中度为 2 的结点个数是
A. 10
B. 11
C. 12
D. 15
需要购买答案的联系QQ:79691519满分：5 分