一、概述第一周测验1、以下关于基于有穷观点的能行方法说法错误的是：
a、由有限数量的任意指令构成
b、指令执行在有限步骤后终止
c、指令每次执行都得到唯一的结果
d、原则上可以由人单独采用纸笔完成
2、以下关于adt抽象数据类型说法错误的是：
a、adt是对数据进行处理的一种逻辑描述。
b、adt建立的封装技术将可能的处理实现细节隐蔽起来。
c、同一adt只有唯一的数据结构可以实现。
d、采用程序设计语言的控制结构和基本数据类型来实现adt的所提供的逻辑接口。
3、关于“图灵机”，下列说法不正确的个数为： 1）图灵机给出的是计算机的理论模型； 2）图灵机的状态转移函数q, x, y, r(或l或n), p，其实就是一条指令，即在q状态下，当输入为x时，输出为y，读写头向右(r)、向左(l)移动一格或不动(n)，状态变为p； 3）图灵机是一种离散的、有穷的、构造性的问题求解思路； 4）凡是能用算法方法解决的问题也一定能用图灵机解决，凡是图灵机解决不了的问题算法也解决不了。
a、0
b、1
c、2
d、3
4、下列哪个项目是抽象的逻辑功能？
a、电视机使用手册；
b、电视机的电路图；
c、汽车维修手册；
d、宫保鸡丁菜谱；
5、逻辑功能接口和实现方法的关系？
a、逻辑功能接口是稳定的，可以用不同方法来实现；
b、逻辑功能接口的实现方法只有一种；
c、实现方法改变了，逻辑功能也一定会改变；
d、逻辑功能改变的话，实现方法可以保持不变。
6、一个图灵机应该由以下哪些部分组成？
a、无限长的分格纸带
b、读写头
c、状态寄存器
d、有限的控制规则
e、字符
7、一般来说我们可以把生活中常见的问题分为哪几类？
a、分类问题
b、证明问题
c、过程问题
d、计算问题
8、以下哪些方法不是以算法的概念来解决问题？
a、超大规模分布式计算
b、光子计算
c、dna计算
d、量子计算
e、智慧众包
f、星象占卜
二、算法分析第二周测验1、判断下列代码段的大o级别： test = 0 for i in range(n): for j in range(n): test = test i * j
a、o(n)
b、o(n^2)
c、o(n^3)
d、o(n*log(n))
2、判断下列代码段的大o级别： test = 0 for i in range(n): test = test 1 for j in range(n): test = test - 1
a、o(n)
b、o(n^2)
c、o(n^3)
d、o(n*log(n))
3、判断下列代码段的大o级别： for i in range(n): k = 2 2
a、o(n)
b、o(n^2)
c、o(n^3)
d、o(1)
4、判断下列代码段的大o级别： def function(n): return n 2
a、o(n)
b、o(n^2)
c、o(n^3)
d、o(1)
5、以下是一个快速幂算法： def pow(x, n): if n==0: return 1 elif n==1: return x elif n%2==0: return pow(x*x, n//2) else: return pow(x*x, n//2)*x问它对于n的大o级别。
a、o(n)
b、o(log n)
c、o(nlog n)
d、o(1)
6、下面的列表操作中哪些是o(1)的？
a、list.pop(0)
b、list.pop()
c、list.append(10)
d、list[10]
7、下面的字典操作中哪些是o(1)的？
a、'' in my_dict
b、del my_dict['']
c、my_dict[''] == 10
d、my_dict[''] = 1
8、令n为问题规模，其中解决本问题的三个算法称为a,b,c，他们需要的总运算次数分别是： a: 96 108n 24n^2 12n^3 b: 16n 48n^3 c: 10080 168n 7n^2*log(n) 三个算法的时间复杂度的大o级别中，以下表述正确的有：
a、a算法和b算法的时间复杂度相同
b、b算法比a算法的时间复杂度更大
c、c算法的时间复杂度最大
d、c算法的时间复杂度最小
e、a算法比b算法的时间复杂度更大
oj的适应性测试1、a/b问题
2、打印实心矩形
3、找到最小的数
三、基本结构（上）第三周测验1、假设你执行了下列的栈操作： s = stack() s.push(1) s.push(3) s.pop() s.push(5) s.push(7)现在栈内还有哪些元素？
a、1, 5, 7
b、3, 5, 7
c、1, 3, 7
d、1, 3, 5
2、将以下中缀表达式： ( 5 - 3 ) * ( 2 4 ) 转换为后缀表达式，结果为？
a、5 3 - 2 4 *
b、5 3 2 4 * -
c、5 3 2 * - 4
d、5 3 2 * 4 -
3、给定后缀表达式 3 6 5 2 - / 求值结果为？
a、3
b、4
c、6
d、10
4、使用括号匹配算法判断以下表达式： ([()[]{]}<>)结果是否匹配？匹配过程中栈内元素最多有多少个？
a、否，3
b、是，3
c、是，4
d、否，4
5、判断以下函数的功能 def func(str1): s = stack() for char in str1: s.push(char) str2 = '' while not s.isempty(): str2 = s.pop() return str2
a、将给定的字符串反转输出
b、判断给定字符串长度
c、将给定字符串复制并输出
d、包含错误，无法运行
6、以下哪些关于栈的说法是正确的？
a、栈的pop操作时间复杂度是o(n)
b、栈的pop操作时间复杂度是o(1)
c、栈的特性是先进先出(fifo)
d、栈的特性是后进先出(lifo)
e、括号匹配算法需要栈结构的参与
f、在python中栈结构可以由list来实现
7、以下未完成的函数可实现不同的功能 def func(lst1): s1, s2 = stack(), stack() for item in lst1: s1.push(item) lst2 = [] while not s1.isempty(): ### 在此进行代码填空 ### return lst2 # 测试 print(func([1, 3, 5, 7, 9]))在下列选项中，填空内容与分别对列表[1, 3, 5, 7, 9]调用结果相对应的选项有？
a、lst2.append(s1.pop()) [9, 7, 5, 3, 1]
b、lst2.append(s1.pop()) [1, 3, 5, 7, 9]
c、while not s1.isempty(): s2.push(s1.pop()) lst2.append(s2.pop()) while not s2.isempty(): s1.push(s2.pop())[1, 3, 5, 7, 9]
d、while not s1.isempty(): s2.push(s1.pop()) lst2.append(s2.pop()) while not s2.isempty(): s1.push(s2.pop()) [9, 7, 5, 3, 1]
e、lst2.append(s1.peek())死循环，无法运行
f、lst2.append(s1.peek())[9, 9, 9, 9, 9]
g、for i in range(s1.pop()): s2.push(i) lst2.append(s2.size()) [9, 16, 21, 24, 25]
h、for i in range(s1.pop()): s2.push(i) lst2.append(s2.size())[1, 4, 9, 16, 25]
8、以下哪些算法适合用栈来实现？
a、实现undo和redo功能的算法
b、html标签匹配算法
c、求列表平均数的算法
d、1到n的累计求和算法
第三周作业1、有效的括号
2、一维开心消消乐
3、强迫症老板和他的洗碗工
四、基本结构（下）第四周测验1、下列叙述正确的是？
a、有两个指针域的链表称为二叉链表
b、队列可以用链式存储结构的单链表实现
c、带链的栈有栈顶指针和栈底指针，因此又称为双重链表
d、节点中具有多个指针域的链表称为多重链表
2、用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点，则在进行删除操作时
a、仅修改队头指针
b、仅修改队尾指针
c、队头、队尾指针都必须要修改
d、队头、队尾指针都可能要修改，但不必然都修改
3、递归过程或函数调用时，处理参数或返回地址，用以下哪种数据结构最合适？
a、栈
b、队列
c、线性表
d、多维数组
4、设有序表的关键字序列为{1,4,6,11,19,35,52,54,57,71,78,86,92,96}，当查找关键字为34的结点时，经( )次比较后查找失败？
a、14
b、6
c、7
d、3
5、设某顺序表中第一个元素的起始存储地址为a,每个元素的长度为b,则第c个元素的起始地址是？（a,b,c均为非负整数）
a、a b*c
b、a b c
c、a b*c-b
d、a b*c-c
6、以下哪些是单链表的特点？
a、随机存取
b、顺序存取
c、插入删除元素时需要移动表中元素
d、插入删除元素时不必移动表中元素
e、插入删除元素时需要修改指针
7、以下哪些是顺序表的特点？
a、随机存取
b、顺序存取
c、插入删除元素时需要移动表中元素
d、插入删除元素时不需要移动表中元素
8、设一个队列的入队顺序是1，2，3，4，5，那下列哪些是不能存在的出队顺序？
a、1，2，3，5，4
b、3，4，5，1，2
c、1，2，3，4，5
d、5，4，3，2，1
第四周作业（北大选课同学选做）1、有序队列
2、最近的请求次数
3、基数排序
五、递归（上）第五周测验1、以下哪项不是递归的三定律之一？
a、有一个基本结束条件
b、算法调用自身
c、能够不断减小问题规模
d、对函数运行结果进行缓存
2、递归函数的实现与哪种数据结构直接相关？
a、栈
b、队列
c、堆
d、无序表
3、使用进制转换函数： def tostr2(n,base): convertstring='0123456789abcdef' if n == 0: return '' return tostr2(n // base, base) convertstring[n % base] 将数字135转换为三进制“12000”的过程中，函数共被调用了多少次（包含初始调用）？
a、3
b、4
c、5
d、6
4、若定义实心等边三角形为0阶谢尔宾斯基三角，现给定一个边长为1的3阶谢尔宾斯基三角，请问它的面积更接近以下哪个数字？
a、0.4330127
b、0.2435696
c、0.1826772
d、0.1370079
5、以下是使用递归方式实现的圆括号匹配函数： def match(s, n=0): if s: if s[0] == '(': n = 1 else: n -= 1 if n < 0: return false return match(s[1:], n) else: return n == 0 请问以下哪个输入中可能出现参数为match("((()))", 3)的函数调用？
a、"(((()((()))"
b、"()((()))"
c、"((()))((("
d、"((()))"
6、给定绘制分形树函数： def tree(branch_len): t.pendown() t.forward(branch_len) t.penup() if branch_len > 5: t.left(20) tree(branch_len - 5) t.right(40) tree(branch_len - 5) t.left(20) t.backward(branch_len) 其中t为海龟画笔对象。 在调用函数tree(50)时，下列哪些说法是正确的？
a、画线的长度总和为10180
b、画线的长度总和为9150
c、组成树的线段共1023条
d、组成树的线段共511条
e、树梢距树根距离为275
f、树梢距树根距离为270
g、树梢共512个
h、树梢共256个
7、以下函数用于可用于求方程的近似解，其中参数f为一个输入、输出均为数字的函数 def solve(f, x1, x2): mid = (x1 x2) / 2 if f(mid) == 0 or abs(x1 - x2) < 1e-8: return #
猜你喜欢
- 2022-12-05 21:43
- 2022-12-05 21:37学习通《论语》中的人生智慧与自我管理-超星尔雅-学习通-题库零氪最新考试答案
- 2022-12-05 21:11
- 2022-12-05 20:50
- 2022-12-05 20:36
- 2022-12-05 20:14
- 2022-12-05 20:10
- 2022-12-05 20:10
- 2022-12-05 19:55
- 2022-12-05 19:22