MOOC 数据结构与算法Python版-北京大学 中国大学慕课答案.docx
《MOOC 数据结构与算法Python版-北京大学 中国大学慕课答案.docx》由会员分享,可在线阅读,更多相关《MOOC 数据结构与算法Python版-北京大学 中国大学慕课答案.docx(35页珍藏版)》请在文库网上搜索。
1、 MOOC 数据结构与算法 Python 版-北京大学 中国大学慕课答案第一周测验1、问题:以下关于基于有穷观点的能行方法说法错误的是:选项:A、由有限数量的任意指令构成B、指令执行在有限步骤后终止C、指令每次执行都得到唯一的结果D、原则上可以由人单独采用纸笔完成正确答案:【由有限数量的任意指令构成】2、问题:以下关于 ADT 抽象数据类型说法错误的是:选项:A、ADT 是对数据进行处理的一种逻辑描述。B、ADT 建立的封装技术将可能的处理实现细节隐蔽起来。C、同一 ADT 只有唯一的数据结构可以实现。D、采用程序设计语言的控制结构和基本数据类型来实现 ADT 的所提供的逻辑接口。正确答案:【
2、同一 ADT 只有唯一的数据结构可以实现。】3、问题:关于“图灵机”,下列说法不正确的个数为:1)图灵机给出的是计算机的理论模型;2)图灵机的状态转移函数 q, X, Y, R(或 L 或 N), p,其实就是一条指令,即在 q 状态下,当输入为 X 时,输出为 Y,读写头向右(R)、向左(L)移动一格或不动(N),状态变为 p;3)图灵机是一种离散的、有穷的、构造性的问题求解思路;4)凡是能用算法方法解决的问题也一定能用图灵机解决,凡是图灵机解决不了的问题算法也解决不了。选项:A、0B、1C、2D、3正确答案:【0】4、问题:下列哪个项目是抽象的逻辑功能?选项:A、电视机使用手册;B、电视机
3、的电路图;C、汽车维修手册; D、宫保鸡丁菜谱;正确答案:【电视机使用手册;】5、问题:逻辑功能接口和实现方法的关系?选项:A、逻辑功能接口是稳定的,可以用不同方法来实现;B、逻辑功能接口的实现方法只有一种;C、实现方法改变了,逻辑功能也一定会改变;D、逻辑功能改变的话,实现方法可以保持不变。正确答案:【逻辑功能接口是稳定的,可以用不同方法来实现;】6、问题:一个图灵机应该由以下哪些部分组成?选项:A、无限长的分格纸带B、读写头C、状态寄存器D、有限的控制规则E、字符正确答案:【无限长的分格纸带#读写头#状态寄存器#有限的控制规则】7、问题:一般来说我们可以把生活中常见的问题分为哪几类?选项:
4、A、分类问题B、证明问题C、过程问题D、计算问题正确答案:【分类问题#证明问题#过程问题】8、问题:以下哪些方法不是以算法的概念来解决问题?选项:A、超大规模分布式计算B、光子计算C、DNA 计算D、量子计算E、智慧众包F、星象占卜正确答案:【智慧众包#星象占卜】OJ 的适应性测试第二周测验 1、问题:判断下列代码段,关于的大 O 级别:test=0 foriinrange(n): forjinrange(n):forkinrange(i): test=test+i*j选项:A、O(n)B、O(n2)C、O(n3)D、O(n*log(n)正确答案:【O(n3)】2、问题:判断下列代码段的大 O
5、 级别:test=0 foriinrange(n): test=test+1forjinrange(n): test=test-1 forkinrange(n): test=test*1选项:A、O(n)B、O(n2)C、O(n3)D、O(n*log(n)正确答案:【O(n)】3、问题:判断下列代码段的大 O 级别:foriinrange(n): forjinrange(i): k=2+2选项:A、O(n)B、O(n2)C、O(n3)D、O(1)正确答案:【O(n2)】4、问题:判断下列代码段的大 O 级别:deffunction(n): return2选项:A、O(n)B、O(n2)C、O(
6、n3)D、O(1)正确答案:【O(1)】5、问题:以下是一个快速幂算法:defpow(x,n): ifn=0: return1 elifn=1: returnxelifn%2=0: returnpow(x*x,n/2) else: returnpow(x*x,n/2)*x 问它对于 n 的大 O 级别。选项:A、O(n)B、O(log n)C、O(nlog n) D、O(1)正确答案:【O(log n)】6、问题:下面的列表操作中哪些是 O(1)的?(假设列表 alist 足够长,不导致任何报错)选项:A、alist.pop(0)B、alist.pop()C、alist.append(10)D
7、、alist10:16E、alist.sort()正确答案:【alist.pop()#alist.append(10)#alist10:16】7、问题:下面的字典操作中哪些是 O(1)的?选项:A、inmy_dictB、delmy_dictC、my_dict=10D、my_dict+=1正确答案:【inmy_dict#delmy_dict#my_dict=10#my_dict+=1】8、问题:令 n 为问题规模,其中解决本问题的三个算法称为 A,B,C,他们需要的总运算次数分别是:A: 96+108n+24n2+12n3B: 16+3n48C:10080+168n+7n2*log(n)三个算法
8、的时间复杂度的大 O 级别中,以下表述正确的有:选项:A、A 算法和 B 算法的时间复杂度相同B、B 算法比 A 算法的时间复杂度更大C、C 算法的时间复杂度最大D、C 算法的时间复杂度最小E、A 算法比 B 算法的时间复杂度更大正确答案:【B 算法比 A 算法的时间复杂度更大#C 算法的时间复杂度最小】第三周作业第三周测验1、问题:假设你执行了下列的栈操作:s=Stack() s.push(1) s.push(3) s.push(5)s.pop() s.push(7)现在栈内还有哪些元素?选项:A、1, 5, 7B、3, 5, 7 C、1, 3, 7D、1, 3, 5正确答案:【1, 3,
9、7】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 + -正确答案:【5 3 - 2 4 + *】3、问题:给定后缀表达式 3 6 + 5 2 - /求值结果为?选项:A、3B、4C、6D、10正确答案:【3】4、问题:使用括号匹配算法判断以下表达式:()结果是否匹配?匹配过程中栈内元素最多有多少个?选项:A、否,3B、是,3C、是,4D、否,4正确答案:【否,3】5、问题:判断以下函数的功能 deffunc(str1): s=
10、Stack() forcharinstr1: s.push(char)str2= whilenots.isEmpty(): str2+=s.pop() returnstr2选项:A、将给定的字符串反转输出B、判断给定字符串长度C、将给定字符串复制并输出D、包含错误,无法运行正确答案:【将给定的字符串反转输出】6、问题:以下哪些关于栈的说法是正确的?选项:A、栈的 pop 操作时间复杂度是 O(n)B、栈的 pop 操作时间复杂度是 O(1) C、栈的特性是先进先出(FIFO)D、栈的特性是后进先出(LIFO)E、括号匹配算法需要栈结构的参与F、在 Python 中栈结构可以由 list 来实现
11、正确答案:【栈的特性是后进先出(LIFO)#括号匹配算法需要栈结构的参与#在Python 中栈结构可以由 list 来实现】7、问题:以下未完成的函数可实现不同的功能 deffunc(lst1): s1,s2=Stack(),Stack()foriteminlst1: s1.push(item) lst2= whilenots1.isEmpty(): #在此进行代码填空#returnlst2 #测试 print(func(1,3,5,7,9)在下列选项中,填空内容与分别对列表1, 3,5, 7, 9调用结果相对应的选项有?选项:A、lst2.append(s1.pop()9, 7, 5, 3,
12、 1B、lst2.append(s1.pop() 1, 3, 5, 7, 9C、whilenots1.isEmpty(): s2.push(s1.pop() lst2.append(s2.pop() whilenots2.isEmpty():s1.push(s2.pop()1, 3, 5, 7, 9D、whilenots1.isEmpty(): s2.push(s1.pop() lst2.append(s2.pop() whilenots2.isEmpty():s1.push(s2.pop()9, 7, 5, 3, 1E、lst2.append(s1.peek()死循环,无法运行F、lst2.
13、append(s1.peek()9, 9, 9, 9, 9G、foriinrange(s1.pop(): s2.push(i) lst2.append(s2.size()9, 16, 21, 24, 25H、foriinrange(s1.pop(): s2.push(i) lst2.append(s2.size()1, 4, 9, 16, 25正确答案:【lst2.append(s1.pop()9, 7, 5, 3, 1#whilenots1.isEmpty(): s2.push(s1.pop()lst2.append(s2.pop() whilenots2.isEmpty(): s1.pus
14、h(s2.pop()1, 3, 5, 7,9#lst2.append(s1.peek()死循环,无法运行#foriinrange(s1.pop(): s2.push(i)lst2.append(s2.size()9, 16, 21, 24, 25】8、问题:以下哪些算法适合用栈来实现?选项:A、实现 UNDO 和 REDO 功能的算法B、HTML 标签匹配算法C、求列表平均数的算法D、1 到 N 的累计求和算法正确答案:【实现 UNDO 和 REDO 功能的算法#HTML 标签匹配算法】第四周作业第四周测验1、问题:下列叙述正确的是?选项: A、有两个指针域的链表称为二叉链表B、队列可以用链式
15、存储结构的双向链表实现C、带链的栈有栈顶指针和栈底指针,因此又称为双重链表D、节点中具有多个指针域的链表称为多重链表E、栈可以用链式存储结构的单链表实现正确答案:【队列可以用链式存储结构的双向链表实现#栈可以用链式存储结构的单链表实现】2、问题:用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点,则在进行删除操作时选项:A、仅修改队头指针B、仅修改队尾指针C、队头、队尾指针都必须要修改D、队头、队尾指针都可能要修改,但不必然都修改正确答案:【队头、队尾指针都可能要修改,但不必然都修改】3、问题:递归过程或函数调用时,处理参数或返回地址,用以下哪种数据结构最合适?选项
16、:A、栈B、队列C、线性表D、多维数组正确答案:【栈】4、问题:设有序单链表的关键字序列为1,4,6,11,19,35,52,54,57,71,78,86,92,96,当查找关键字为 21 的结点时,经( )次比较后查找失败?选项:A、14B、6C、7D、3正确答案:【6】5、问题:设某顺序表中第一个元素的起始存储地址为 a,每个元素的长度为 b,则第c 个元素的起始地址是?(a,b,c 均为非负整数)选项:A、a+b*cB、a+b+cC、a+b*(c-1) D、a+(b-1)*c正确答案:【a+b*(c-1)】6、问题:以下哪些不是单链表的特点?选项:A、随机存取B、顺序存取C、插入删除元素
17、时需要移动表中元素D、插入删除元素时不必移动表中元素E、插入删除元素时需要修改指针正确答案:【随机存取#插入删除元素时需要移动表中元素】7、问题:以下哪些是顺序表的特点?选项:A、随机存取B、顺序存取C、插入删除元素时需要移动表中元素D、插入删除元素时不需要移动表中元素正确答案:【随机存取#插入删除元素时需要移动表中元素】8、问题:设一个队列的入队顺序是 1,2,3,4,5,那下列哪些是不能存在的出队顺序?选项:A、1,2,3,5,4B、3,4,5,1,2C、1,2,3,4,5D、5,4,3,2,1E、1,2,5,4,3F、2,3,4,5,1正确答案:【1,2,3,5,4#3,4,5,1,2#
18、5,4,3,2,1#1,2,5,4,3#2,3,4,5,1】第五周作业第五周测验1、问题:以下哪项不是递归的三定律之一?选项:A、有一个基本结束条件B、算法调用自身C、能够不断减小问题规模 D、对函数运行结果进行缓存正确答案:【对函数运行结果进行缓存】2、问题:递归函数的实现与哪种数据结构直接相关?选项:A、栈B、队列C、堆D、无序表正确答案:【栈】3、问题:使用进制转换函数:deftoStr2(n,base):convertString=0123456789ABCDEF ifn=0: returnreturntoStr2(n/base,base)+convertStringn%base将数字
19、 135 转换为三进制“12000”的过程中,函数共被调用了多少次(包含初始调用)?选项:A、3B、4C、5D、6正确答案:【6】4、问题:若定义实心等边三角形为 0 阶谢尔宾斯基三角,现给定一个边长为 1 的4 阶谢尔宾斯基三角,请问它的面积更接近以下哪个数字?选项:A、0.316B、0.244C、0.183D、0.137E、0.237正确答案:【0.137】5、问题:以下是使用递归方式实现的圆括号匹配函数:defmatch(s,n=0): ifs:ifs0=(: n+=1 else: n-=1 ifn0: returnFalse returnmatch(s1:,n) else: retur
20、nn=0 请问以下哪个输入中可能出现参数为 match(), 3)的函数调用?选项:A、()()B、()()C、()(D、()正确答案:【()()】 6、问题:给定绘制分形树函数:deftree(branch_len): t.pendown()t.forward(branch_len) t.penup() ifbranch_len5: t.left(20) tree(branch_len-5) t.right(40)tree(branch_len-5) t.left(20) t.backward(branch_len)其中 t 为海龟画笔对象。在调用函数 tree(50)时,下列哪些说法是正确
21、的?选项:A、画线的长度总和为 10180B、画线的长度总和为 9150C、组成树的线段共 1023 条D、组成树的线段共 511 条E、树梢与树根的路径距离为 275F、树梢与树根的路径距离为 270G、树梢共 512 个H、树梢共 256 个正确答案:【画线的长度总和为 10180#组成树的线段共 1023 条#树梢与树根的路径距离为 275#树梢共 512 个】7、问题:以下函数用于可用于求方程的近似解,其中参数 f 为一个输入、输出均为数字的函数 defsolve(f,x1,x2): mid=(x1+x2)/2 iff(mid)=0orabs(x1-x2)1e-8: return#Ae
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- MOOC 中国大学慕课答案