24年春江苏开放大学算法设计与分析060730形考作业1最新答案

试题列表
单选题
题型：单选题客观题分值2分难度：一般得分：2
1
若已知一个栈的入栈序列是1,2,3，…，n，其输出序列为p1，p2，p3，…，pN，若pN是n，则pi是（ ）。
A
n-i+1
B
i
C
不确定
D
n-i
学生答案：C
老师点评：
题型：单选题客观题分值2分难度：一般得分：2
2
记号O的定义正确的是（ ）
A
O(g(n))={f(n)|存在正常数c＞0，存在正数和n0＞0使得对所有n≥n0有：0≤cg(n)≤f(n)}
B
O(g(n))={f(n)|存在正常数c和n0使得对所有n≥n0有：0≤cg(n)≤f(n) }
C
O(g(n))={f(n)|存在正常数c和n0使得对所有n≥n0有：0≤f(n)≤cg(n)}
D
O(g(n))={f(n)|存在正常数c＞0，存在正数和n0＞0使得对所有n≥n0有：0≤f(n)≤cg(n)}
学生答案：C
老师点评：
题型：单选题客观题分值2分难度：一般得分：2
3
设a，b为一棵二叉树上的两个结点，在中序遍历时，a在b前面的条件是（ ）
A
a在b的左方
B
a是b的祖先
C
a是b的子孙
D
a在b的右方
学生答案：A
老师点评：
题型：单选题客观题分值2分难度：中等得分：2
4
某二叉树的中序序列ABCDEFG，后序序列为BDCAFGE，则其左子树中结点数目为（ ）。
A
2
B
3
C
5
D
4
学生答案：D
老师点评：
题型：单选题客观题分值2分难度：简单得分：2
5
顺序查找法适合于存储结构为（ ）的线性表。
A
散列存储
B
压缩存储
C
顺序存储或链接存储
D
索引存储
学生答案：C
老师点评：
题型：单选题客观题分值2分难度：一般得分：2
6
在一棵具有5层的满二叉树中结点总数为（ ）
A
31
B
33
C
16
D
32
题型：单选题客观题分值2分难度：简单得分：2
7
数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为：（ ）
A
存储结构
B
逻辑结构
C
顺序存储结构
D
链式存储结构
题型：单选题客观题分值2分难度：简单得分：2
8
如下程序段，其时间复杂度为（）
for (i=1; i<=n; i++){
for(j=1; j<=n; j++){
c[i][j]=a[i][j]+b[i][j]; //矩阵a和b相加得到矩阵c。
}
}
A
O(n3)
B
log(n)
C
O(n2)
D
O(n)
题型：单选题客观题分值2分难度：一般得分：2
9
二叉树的深度为k，则二叉树最多有（ ）个结点。
A
2k-1
B
2k-1
C
2k
D
2k-1
题型：单选题客观题分值2分难度：一般得分：2
10
用链接方式存储的队列，在进行删除运算时（ ）。
A
头、尾指针都要修改
B
仅修改头指针
C
头、尾指针可能都要修改
D
仅修改尾指针
题型：单选题客观题分值2分难度：一般得分：2
11
设abcdef以所给的次序进栈，若在进栈操作时，允许退栈操作，则下面得不到的序列为（ ）。
A
fedcba
B
bcafed
C
dcefba
D
cabdef
题型：单选题客观题分值2分难度：简单得分：2
12
链表是一种采用（ ）存储结构存储的线性表。
A
链式
B
顺序
C
网状
D
星式
题型：单选题客观题分值2分难度：简单得分：2
13
树最适合用来表示（ ）。
A
元素之间具有分支层次关系的数据
B
元素之间无联系的数据
C
有序数据元素
D
无序数据元素
题型：单选题客观题分值2分难度：一般得分：2
14
设计一个判别表达式中左，右括号是否配对出现的算法，采用（ ）数据结构最佳。
A. 线性表的顺序存储结构
A
队列
B
栈
C
线性表的顺序存储结构
D
线性表的链式存储结构
题型：单选题客观题分值2分难度：简单得分：2
15
当代计算机的最主要的体系结构称为是（ ）
A
图灵机
B
PASCAL机
C
冯·诺依曼机
D
非冯·诺依曼机
题型：单选题客观题分值2分难度：简单得分：2
16
算法空间复杂度最主要强调下列哪一个空间占用（ ）
A
算法在运行过程中临时占用的存储空间
B
算法在运行结束占用的存储空间
C
算法的输入输出所占用的空间
D
算法本身的占用空间
题型：单选题客观题分值2分难度：简单得分：2
17
汇编程序的任务是（ ）
A
将高级语言编写的程序转换为可执行程序
B
将汇编语言编写的程序转换为目标程序
C
将高级语言编写的程序转换为汇编语言程序
D
将汇编语言编写的程序转换为可执行程序
题型：单选题客观题分值2分难度：简单得分：2
18
C语言是（ ）
A
目标语言
B
汇编语言
C
高级语言
D
机器语言
题型：单选题客观题分值2分难度：简单得分：2
19
一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（ ）
A
108
B
100
C
110
D
120
题型：单选题客观题分值2分难度：简单得分：2
20
栈和队列的共同点是（）
A
都是先进先出
B
都是先进后出
C
没有共同点
D
只允许在端点处插入和删除元素
填空题
题型：填空题客观题答案不允许乱序分值2分难度：中等得分：2
1
一个栈的输入序列是：1，2,3则不可能的栈输出序列是 。
第1空分值：2分
题型：填空题客观题答案不允许乱序分值2分难度：简单得分：2
2
算法的时间复杂性指算法中 的执行次数。
第1空分值：2分
题型：填空题客观题答案不允许乱序分值2分难度：一般得分：2
3
哈夫曼树是其树的带权路径长度 的二叉树。
第1空分值：2分
题型：填空题客观题答案不允许乱序分值2分难度：简单得分：2
4
在单链表中，要删除某一个指定的结点，必须找到该结点的 结点。
第1空分值：2分
题型：填空题客观题答案不允许乱序分值2分难度：一般得分：2
5
在一个长度为n的顺序表中删除第i （0=<i<=n-1）个元素，需向前移动 个元素。
第1空分值：2分
题型：填空题客观题答案不允许乱序分值2分难度：简单得分：2
6
队列是限制插入只能在表的一端，而删除在表的另一端进行的线性表，其特点是 。
第1空分值：2分
题型：填空题客观题答案允许乱序分值6分难度：简单得分：6
7
结构化程序的编写有 、 、 三种程序结构。
第1空分值：2分
第2空分值：2分
第3空分值：2分
题型：填空题客观题答案不允许乱序分值2分难度：简单得分：2
8
树内各结点度的 称为树的度。
第1空分值：2分
题型：填空题客观题答案不允许乱序分值2分难度：简单得分：2
9
计算机能直接识别和执行的语言是 。
第1空分值：2分
题型：填空题客观题答案不允许乱序分值2分难度：一般得分：2
10
在一棵二叉树中，度为0的结点的个数是n0,度为2的结点的个数为n2，则有n0= 。
第1空分值：2分
简答题
题型：简答题主观题分值10分难度：一般得分：10
1
名词解释：栈，队列，循环队列。
题型：简答题主观题分值10分难度：一般得分：10
2
程序设计语言经过了哪些阶段。
题型：简答题主观题分值16分难度：简单得分：15
3
求m和n的最大公约数，写出他的伪代码。