上海交通大学 python程序设计课程 Ch8-1

专业课复习资料（最新版）封面数据结构与C语言程序设计一. 是非题（2’⨯10）（ ）1、 队列逻辑上是一个表头和表尾既能插入又能删除的线性表。

（ ）2、 任何一个递归过程都可以转换成非递归过程。

（ ）3、 与n个键值的集合{k1,k2,…,kn}相对应的堆是唯一的。

（ ）4、 在索引顺序表上实现分块查找，在等概率查找情况下，其查找长度只与表中元素个数有关，而与每块中元素个数无关。

（ ）5、 所谓加权无向图G的最小生成树T就是将G中各结点间的最短路径作为边所构造出来的G的子图。

（ ）6、 在10万个随机排列的数据中，要选出5个最小的数，采用快速排序比采用Shell排序、堆排序及各种直接排序法都快。

（ ）7、 B树查找算法的时间复杂性为O（n）。

（ ）8、 哈希表查找无需进行关键字的比较。

（ ）9、 在执行某个排序过程中，出现排序码朝着最终位置相反方向移动，则该算法是不稳定的。

（ ）10、任何有向图的顶点都可以按拓扑序排序。

二.填空题（2’⨯6）1．假设用于通信的电文由8个字母组成，其频率分别为0.07，0.19,0.02,0.06,0.32,0.03,0.21,0.10, 为这8个字母设计哈夫曼编码，其中编码长度最大的字母的编码是 位。

2．已知二叉树按中序遍历所得到的结点序列为DCBGEAHFIJK， 按后序遍历所得到的结点序列为DCEGBFHKJIA， 按先序遍历所得到的结点序列为 。

3. 设哈希表长度为11，散列函数H(k)=k MOD 11, 若输入顺序为（18,10,21,9,6,3,16,25,7）,处理冲突方法为线性探测再散列，请构造哈希表 。

果 。

5．已知模式匹配的KMP算法中模式串t=’adabbadada’，其next函数的值为 。

6．在置换-选择排序中，假设工作区的容量为w，若不计输入、输出的时间，则对n个记录的文件而言，生成所有初始归并段所需时间为 。

三.简答题（6’⨯5）1．有n个不同的英文单词，它们的长度相等，均为m，若n>>50，m<5，试问采用什么排序方法时间复杂度最佳？为什么？2．对于一个栈，给出输入序列A，B，C，试给出全部可能的输出序列。

一、选择题: 将唯一正确的选项写在题前括号中.每题2分.【】(1) 本课程的目标定位是什么?[A] 学习Python语言[B] 学习计算机的工作原理[C] 学习各种算法[D] 学习用计算机解决问题【】(2) 下列哪个标识符是合法的?[A] var-name [B] !@#$% [C] _100 [D] elif 【】(3) 执行下列语句后的显示结果是什么?>>> s = ”hi”>>> print “hi”, 2*s[A] hihihi [B] ”hi”hihi[C] hi hihi [D] hi hi hi 【】(4) 如何解释下面的执行结果?>>> print 1.2 - 1.0 == 0.2False[A] Python的实现有错误[B] 浮点数无法精确表示[C] 布尔运算不能用于浮点数比较[D] Python将非0数视为False【】(5) 想用一个变量来表示出生年份,下列命名中哪个最可取?[A] b_y [B] birth_year [C] __birthYear__ [D] birthyear【】(6) 执行下列语句后的显示结果是什么?>>> a = 1>>> b = 2 * a / 4>>> a = “one”>>> print a,b[A] one 0 [B] 1 0 [C] one 0.5 [D] one,0.5【】(7) 执行下列语句后的显示结果是什么?>>> s = ”GOOD MORNING”>>> print s[3:-4][A] D MOR [B] D MORN [C] OD MOR [D] OD MORN【】(8) 表达式1+2L*3.14>0的结果类型是:[A] int [B] long [C] float [D] bool【】(9) 程序设计的原型(Prototyping)方法是指:[A] 先设计程序框架结构,再逐步精化细节[B] 先设计类,再实例化为对象[C] 先设计简单版本,再逐步增加功能[D] 以上都不是【】(10) 对n个数做归并排序(merge sort),这个算法是:[A] log n时间的[B] 线性时间的[C] n log n时间的[D] n2时间的二、判断题:在题目前面的括号中打勾或叉.每题2分.【】(1) 高级语言程序要被机器执行,只有用解释器来解释执行.【】(2) 不同类型的数据不能相互运算.【】(3) 由于引号表示字符串的开始和结束,所以字符串本身不能包含引号. 【】(4) 计算机科学并非研究计算机的科学,正如天文学并非研究望远镜. 【】(5) 算法和程序是不同的概念.【】(6) 下面的程序段是错的:temp = 42print "The temperature is" + temp【】(7) 同一Python变量可以先后赋予不同类型的值.【】(8) 计算机的计算是确定的,因此并不能真正产生随机数.【】(9) 对象就是类的实例.【】(10) Hanoi塔问题属于不可解问题.三、填空题:每题2分.A 卷总 5 页第 2 页(1) 表达式2**3*4%5的值为: .(2) 函数range(1,1,1)的值是: .(3) 格式化输出浮点数: 宽度10,2位小数,左对齐,则格式串为: .(4) 表达式chr(ord(‘a’))的值为: .(5) 表达式((2>=2) or (2<2)) and 2的值为: .(6) 无穷循环while True:的循环体中可用语句退出循环.(7) 不用math模块中的sqrt(), 如何计算4的平方根: .(8) 给出一个计算机本质上不可解问题的例子: .(9) 表达式‘%d%%%d’%(1%2,3%4)的值为: .(10) Python的标准随机数生成器模块是: .四、读程序并回答问题:每题5分.(1) 下面的程序根据用户输入的三个边长a,b,c来计算三角形面积.请找出程序中的错误并改正之.(设用户输入合法,面积公式无误)import matha, b, c = raw_input(“Enter a,b,c: ”)s = a + b + cs = s / 2.0area = sqrt(s*(s-a)*(s-b)*(s-c))print “The area is:”, area将raw_input 改成input将sqrt改成math.sqrt(2) 下面的程序要求用户输入二进制数字0/1并显示之.找出程序中的错误并改正之. bit = input(“Enter a binary digit: “)if bit = 0 or 1:print “Your input is:”, bitelseprint “Your input is invalid.”将bit = 0 or 1 改成bit == 0 or bit== 1将else改成else:(3) 下面程序的输出是什么?A 卷总 5 页第 3 页def f(a, b, c):x = y = 0for i in range(c):x = x + a + yy = y + breturn xprint f(-5, 2, 10)注意return x 在for 的缩进里面，所以最后只有一个数据输出range(10)其实是从0开始计数到9再不断迭代即可40(4) 下面程序的输出是什么？def f(a,b):a = 4print a, bdef main():a = 5b = 6print a, bf(a,b)print a, bmain()564656(5) 下面程序的功能是什么?def f(a, b):if b == 0:print aelse:f(b, a%b)a, b = input(“Enter two natural numbers: ”)print f(a, b)求最大公因式A 卷总 5 页第 4 页五、程序设计:15分.(1) 用分而治之(divide and conquer)和递归方法设计程序:产生并打印一个序列的全排列.例如,序列[1,2,3]的全排列123,132,213,231,312,321可以这样获得:1为前缀, 后接[2,3]的全排列2为前缀, 后接[1,3]的全排列3为前缀, 后接[1,2]的全排列而[2,3]等序列的全排列依此类推.下面给出了这个程序的部分代码,在理解上述算法的基础上补足所缺的代码.# 函数perm(list,k,m):产生前缀为list[0:k]后接list[k:m+1]的全排列def perm(list,k,m):if k == m:print list[i],printelse:list[k],list[i] = list[i],list[k]list[k],list[i] = list[i],list[k]myList = input(“Input a list([1,2,3,...]): “)(2) 编写程序: 输入一个文件A, A中每行包含若干数值.生成文件B, B中每行是A中对应行的数值的平均值.Import stringfileA = raw_input(“Enter a data file: ”)infile = open(fileA,’r’)outfile = open (‘B.dat’,’w’)line = infile.readline()while line != “”：sum = 0.0count = 0for xStr in string.split(line):sum = sum + eval(xStr)count = count + 1.avg = sum/countoutfile.write(str(avg)+’n’)line = infile.readline()infile.close()outfile.close()。