Date:2019-07-19
1. 两个指针 P 和 Q ，分别指向单链表的两个元素， P 所指元素是 Q 所指元素前驱的条件是（ P->next== Q）
2. 串是一种特殊的线性表，其特殊性体现在（数组元素是一个字符）
3. 下列文件中属于逻辑结构文件的是 （C）
A.连续文件
B.系统文件 （计算机文件系统目录可用树实现，树的先序遍历）
C.顺序文件 (逻辑结构文件)
D.散列文件
4. 在长度为 n 的顺序表的第 i 个位置上插入一个元素（ 1≤ i ≤n+1 ），元素的移动次数为： （n-i+1）
5. 线性表的逻辑顺序与存储顺序总是一致的。 False。
线性表（linear list）是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列。数据元素是一个抽象的符号，其具体含义在不同的情况下一般不同。
在稍复杂的线性表中，一个数据元素可由多个数据项（item）组成，此种情况下常把数据元素称为记录（record），含有大量记录的线性表又称文件（file）。
线性表中的个数n定义为线性表的长度，n=0时称为空表。在非空表中每个数据元素都有一个确定的位置，如用ai表示数据元素，则i称为数据元素ai在线性表中的位序。
线性表的相邻元素之间存在着序偶关系。如用（a1，…，ai-1，ai，ai+1，…，an）表示一个顺序表，则表中ai-1领先于ai，ai领先于ai+1，称ai-1是ai的直接前驱元素，ai+1是ai的直接后继元素。当i=1,2，…，n-1时，ai有且仅有一个直接后继，当i=2，3，…，n时，ai有且仅有一个直接前驱 。
我们说“线性”和“非线性”，只在逻辑层次上讨论，而不考虑存储层次，所以双向链表和循环链表依旧是线性表。
在数据结构逻辑层次上细分，线性表可分为一般线性表和受限线性表。一般线性表也就是我们通常所说的“线性表”，可以自由的删除或添加结点。受限线性表主要包括栈和队列，受限表示对结点的操作受限制。
1．集合中必存在唯一的一个“第一元素”。
2．集合中必存在唯一的一个 “最后元素” 。
3．除最后一个元素之外，均有唯一的后继(后件)。
4．除第一个元素之外，均有唯一的前驱(前件)。
线性表主要由顺序表示或链式表示。在实际应用中，常以栈、队列、字符串等特殊形式使用。
顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素，称为线性表的顺序存储结构或顺序映像（sequential mapping）。它以“物理位置相邻”来表示线性表中数据元素间的逻辑关系，可随机存取表中任一元素。
链式表示指的是用一组任意的存储单元存储线性表中的数据元素，称为线性表的链式存储结构。它的存储单元可以是连续的，也可以是不连续的。在表示数据元素之间的逻辑关系时，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置），这两部分信息组成数据元素的存储映像，称为结点（node）。它包括两个域；存储数据元素信息的域称为数据域；存储直接后继存储位置的域称为指针域。指针域中存储的信息称为指针或链 。
6. 散列函数有一个共同的性质，即函数值应当以( 同等概率 )取其值域的每个值。 (散列函数即是hash函数)
7. 用ISAM组织文件适合于（磁盘）
8. 大量在外部排序中使用的数据结构是(B+Tree)
9. 一些表面上很不相同的数据可以有相同的逻辑结构 True
10. STL中的unordered_map和priority_queue使用的底层数据结构分别是什么?(hashtable,heap)
优先队列是由堆(heap)实现的，堆是一个完全二叉树；无序映射是由哈希表实现的。
11. 数据元素是数据的最小单位。 False
注意区分“基本单位”和“最小单位”。
数据元素(Data Element)：是数据的基本单位，数据元素用于完整的描述一个对象。
数据项是不可分割的最小单位，数据项是构成数据元素的最小单位。
12. 设T为一棵平衡树，在其中插入一个结点n，然后立即删除该结点后得到T1 ，则T与T1 必定相同。 False
13.在数据结构中，从逻辑上可以把数据结构分为（线性结构和非线性结构）
14. 一个向量第一个元素的存储地址是 100,每个元素的长度为 2,则第 5 个元素的地址 108
15. 对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K %9作为散列函数，则散列地址为1的元素有（4）个 分别是：55，64，46，10
16. 广义表的元素可以是子表，也可以是单元素，这样的说法正确吗？ True
17. 数据结构是研究数据的（物理结构和逻辑结构）以及它们之间的相互关系
18. 下述哪一条是顺序存储结构的优点？存储密度大，但是插入和删除不方便，时间复杂度高。
19. 以下四类基本的逻辑结构反映了四类基本的数据组织形式，解释错误的是 ( A）
A. 集合中任何两个结点之间都有逻辑关系但组织形式松散
B. 线性结构中结点按逻辑关系依次排列形成一条"锁链"
C. 树形结构具有分支、层次特性，其形态有点像自然界中的树
D.图状结构中的各个结点按逻辑关系互相缠绕，任何两个结点都可以邻接
20. 对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为 用尾指针表示的循环单链表
21. 查找相同结点的效率折半查找总比顺序查找高。 False,不一定。
22. 广义表的表尾一定是一个广义表，这样的说法正确吗？ True
23. 线性表中每个元素都有一个直接前驱和一个直接后继，这样的说法正确吗？ False，表头没有前驱，表尾没有后继。
24. 数据的存储结构通常可以有以下四种：
四种，它们分别是:顺序存储结构、链式存储结构、索引结构与散列结构
25. 邻接表是图的一种顺序存储结构，这种说法（） False
26. 在KMP算法中，已知模式串为ADABCADADA,请写出模式串的next数组值？A
KMP算法：分为模式串和主串，在主串中匹配模式串，next数组中每个值如举例 下标为 j 的值 k，表示模式串第 j 个字符和主串的某个字符没有匹配成功，此时主串这个字符应该和模式串中第 k 个字符进行匹配。
原理其实就是在第 j 个字符匹配不成功的时候，查找前面会不会出现在第一个字符开始的连续的 k-1个字符和以第 j-1 个字符结束的连续 k-1个字符是相同的情况，如果有的话，我们就可以让模式串从第 k 个字符开始和那个主串中没有匹配成功的字符进行匹配，节省了时间。原因在于在第 j 个字符前面，主串和模式串是匹配成功的，证明在主串中 第一个字符开始的连续的 k-1个字符和第j-1字符结束的连续的k-1个字符是相同的。因此我们是可以看到模式串中第j-1个字符结束的连续k-1个字符和主串中第一个字符开始的k-1个字符是一定相同的，就无需匹配了，我们就只需要从模式串中的第k个字符开始和主串中前面没有匹配成功的该字符进行匹配。
从图上看应该是这样的：
在没有上述情况发生的时候，证明只能从模式串的第一个开始和主串的这个没有匹配成功的字符进行匹配了；还有一种情况就是当k等于1的时候，即之前和这个主串没有匹配成功的字符匹配的模式串字符刚好是从头开始的。那么我们就不能移动字符串只能移动主串了，让主串的下一个字符和模式串的第一个字符开始匹配。
以上的分析转换成模式串的next函数的定义就是：
next[j] = 0， 当 j = 1 的时候， 理解 ：0的含义就是让主串的这个字符和模式串的首字符前面那个不存在的字符进行比较，换种说法就是前面所讲的让主串移动，让主串的下一个字符和模式串的第一个字符进行匹配。
next[j] = Max { k | 1< k < j 且 P 1到 P k-1 == P j-k+1 到 P j-1 | } 出现上图所示情况
next[j] = 1 没有上图所示情况，且匹配不成功的模式串字符不是第一个此时需要让主串没有匹配成功的字符和模式串的首字符进行匹配
按上述分析解答：
A： 首字符 0
D：前面 A 1
A ：前面 AD 1
B ：前面 ADA 第一个A和第三个A相同，k-1 = 1 ，答案 k = 2
C ：前面 ADAB 1
A ：前面 ADABC 1
D ：前面 ADABCA 第一个A和第三个A相同，k-1 = 1 ，答案 k = 2
A ：前面 ADABCAD 前面两个AD和最后两个AD相同， k - 1= 2 ，答案 k = 3
D ：前面ADABCADA 前面三个ADA和最后三个ADA相同， k - 1 = 3 ，答案 k = 4
A ：前面ADABCADAD 前面 两个AD和最后两个AD相同， k - 1 = 2，答案 k = 3
27. 有如下一个类似跳表的数据结构：每层都是已经排好序的链表，level1层的链表有所有元素，levelN层的链表只有levelN-1的1半的元素，levelN层的结点指向levelN-1层中相同的结点。请问查找一个元素的时间复杂度是：
跳跃表的查找时间复杂度是O(logn).
28. 假设物理块大小为4KB，每个指针占4B，采用一级间接索引，则允许的文件的最大长度是（4096KB）。
29. 两台计算机利用电话线路传输数据信号时，必备的设备是 调制解调器
30. STL中的unordered_map和priority_queue使用的底层数据结构分别是什么?( hashtable,heap(堆))
Part two：python- 机器学习练习
31. What gets printed?()
names1 = ['Amir', 'Barry', 'Chales', 'Dao']
if 'amir' in names1:
print 1
else:
print 2return ：2
32. 下面哪个是Python中的不变的数据结构？tuple; 但set、list、dict都是可变的数据结构。
33. 下列代码的运行结果是？
return：True
print 'a' < 'b' < 'c'34. What gets printed?（）
nums = set([1,1,2,3,3,3,4])
print(len(nums))
# return :435. 深度学习是当前很热门的机器学习算法，在深度学习中，涉及到大量的矩阵相乘，现在需要计算三个稠密矩阵A,B,C的乘积ABC,假设三个矩阵的尺寸分别为m*n，n*p，p*q，且m<n<p<q，以下计算顺序效率最高的是（A）
A.(AB)C
B.AC(B)
C.A(BC)
D.所以效率都相同
解释：
a*b,b*c两矩阵相乘效率为a*c*b
ABC=(AB)C=A(BC).
(AB)C = m*n*p + m*p*q,
A(BC)=n*p*q + m*n*q.
m*n*p<m*n*q,m*p*q< n*p*q, 所以 (AB)C 最小
36. 
结果是学历。
37. 以下不能创建一个字典的语句是（C）
A. dict ={}
B. dict2 = { 3 : 5 }
C. dict3 = {[1,2,3]: “uestc”}(字典的key不能为列表数据)
D.dict4 = {(1,2,3): “uestc”}
38.
如何解释下面的执行结果?
print 1.2 - 1.0 == 0.2
False
解释：浮点数无法精确表示。
39. SPSS的界面中，以下是主窗口是（数据编辑窗口 ）
补充：SPSS共有五个操作界面，分别为：主窗口(数据编辑窗口)、结果输出窗口、对象编辑窗口、语法编辑器窗口和脚本编写窗口
40.有如下函数定义，执行结果正确的是？
def dec(f):
n = 3
def wrapper(*args,**kw):
return f(*args,**kw) * n
return wrapper
@dec
def foo(n):
return n * 2
结果：foo(2) == 12。
41. ARMA是常见的时间序列模型。
42. A* Dijkstra 动态规划 这三个算法可用于路径规划，但K-means算法不能用于路径规划中。
43. x = (y = z + 1) 在python语句中是非法的。
44. while True : pass 是正确的python语句。
45. 下列哪种说法是错误的（A）
A. 除字典类型外，所有标准对象均可以用于布尔测试(错误)
B. 空字符串的布尔值是False (print(bool('')))
C. 空列表对象的布尔值是False print(bool([]))
D.值为0的任何数字对象的布尔值是False print(bool(0))
46. 有两个样本点，第一个点为负样本,它的特征向量是(0,-1);第二个点为正样本,它的特征向量是(2,3),从这两个样本点组成的训练集构建一个线性SVM分类器的分类面方程是(x+2y=3）
必须满足：
min 1/2(w12+w22)
s.t. -1*(0*w1-1*w2+b)>=1
1*(2*w1+3*w2+b)>=1
这样联立方程组可以解出w1=1/5，w2=2/5，b= -3/5，所以就是答案三：(x+2y=3)
47. 解决隐马模型中预测问题的算法是? （维特比算法）
48.
(python2) What gets printed by the code snippet below?()
import mathprint math.floor(5.5)return ：5.0 (python3中是5)
49. 关于支持向量机SVM,下列说法错误的是（C）
A.L2正则项，作用是最大化分类间隔，使得分类器拥有更强的泛化能力
B.Hinge 损失函数，作用是最小化经验分类错误
V.分类间隔为1/||w||，||w||代表向量的模（错误）
D.当参数C越小时，分类间隔越大，分类错误越多，趋于欠学习
A正确。考虑加入正则化项的原因：想象一个完美的数据集，y>1是正类，y<-1是负类，决策面y=0，加入一个y=-30的正类噪声样本，那么决策面将会变“歪”很多，分类间隔变小，泛化能力减小。加入正则项之后，对噪声样本的容错能力增强，前面提到的例子里面，决策面就会没那么“歪”了，使得分类间隔变大，提高了泛化能力。 B正确。 C错误。间隔应该是2/||w||才对，后半句应该没错，向量的模通常指的就是其二范数。 D正确。考虑软间隔的时候，C对优化问题的影响就在于把a的范围从[0，+inf]限制到了[0,C]。C越小，那么a就会越小，目标函数拉格朗日函数导数为0可以求出w=求和a_i*y_i*x_i，a变小使得w变小，因此间隔2/||w||变大
50. 已知print_func.py的代码如下：
print('Hello
World!')
print('__name__
value: ', __name__)
def main():
print('This message is from main function')
if __name__ ==
'__main__':
main()print_module.py的代码如下：
import print_func
print("Done!")运行print_module.py程序，结果是：
Hello World! __name__ value: print_func Done!
运行print_module.py后的结果如下:
自己运行自己的程序，__name__ 即为__main__
当程序当做脚本被别人调用运行时，其__name__ 为自己的模块名称，这里的print_func即被导入到print_module中当做脚本被运行时，则print_func的__name__即变为其自身的模块名。
详情见：https://blog.csdn.net/HEERY551/article/details/94736960
51. 对以下代码解释正确的是：
foo = [1,2]
foo1 = foo
foo.append(3)结果：
foo 值为[1,2,3]
foo1 值为[1,2,3]
52. 在统计模式识分类问题中，当先验概率未知时，可以使用(B C)?
B. N-P判决
C,最小最大损失准则
解释：
在贝叶斯决策中，对于先验概率p(y)，分为已知和未知两种情况。
1. p(y)已知，直接使用贝叶斯公式求后验概率即可；
2. p(y)未知，可以使用聂曼-皮尔逊决策(N-P决策)来计算决策面。
而最大最小损失规则主要就是使用解决最小损失规则时先验概率未知或难以计算的问题的。
53. 若 a = (1, 2, 3)，下列哪些操作是合法的? 对于元组tuple，改变元组的元素值是不合法的，索引、a*3、list(a)是合法的。
54. Python中单下划线_foo与双下划线__foo与__foo__的成员，下列说法正确的是？ABC
A._foo 不能直接用于’from module import *’
B.__foo解析器用_classname__foo来代替这个名字，以区别和其他类相同的命名
C. __foo__代表python里特殊方法专用的标识
D.__foo 可以直接用于’from module import *’
python中主要存在四种命名方式：
1、object #公用方法
2、_object #半保护
#被看作是“protect”，意思是只有类对象和子类对象自己能访问到这些变量，
在模块或类外不可以使用，不能用’from module import *’导入。
#__object 是为了避免与子类的方法名称冲突， 对于该标识符描述的方法，父
类的方法不能轻易地被子类的方法覆盖，他们的名字实际上是
_classname__methodname。
3、_ _ object #全私有，全保护
#私有成员“private”，意思是只有类对象自己能访问，连子类对象也不能访
问到这个数据，不能用’from module import *’导入。
4、_ _ object_ _ #内建方法，用户不要这样定义
54. __new__和__init__的区别，说法正确的是？ ABCD
A.__new__是一个静态方法，而__init__是一个实例方法
B.__new__方法会返回一个创建的实例，而__init__什么都不返回
C.只有在__new__返回一个cls的实例时，后面的__init__才能被调用
D.当创建一个新实例时调用__new__，初始化一个实例时用__init__
解释：
根据官方文档：
即，__new__在__init__之前被调用，__new__的返回值（实例）将传递给__init__方法的第一个参数，然后__init__给这个实例设置一些参数。
* __init__ 方法为初始化方法, __new__方法才是真正的构造函数。
* __new__方法默认返回实例对象供__init__方法、实例方法使用。
* __init__ 方法为初始化方法，为类的实例提供一些属性或完成一些动作。
* __new__ 方法创建实例对象供__init__ 方法使用，__init__方法定制实例对象。
* __new__是一个静态方法，而__init__是一个实例方法。
55. 下面哪些是基于核的机器学习算法?() Radial Basis Function + Linear Discrimimate Analysis + Support Vector Machine
56. 关于K-means聚类算法说法正确的是（ABC）
A.对大数据集有较高的效率并且具有可伸缩性。
B.是一种无监督学习方法。
C.k值无法自动获取，初始聚类中心随机选择。
D.初始聚类中心的选择对聚类结果影响不大。(影响较大)