计算复杂性-第一次作业

数据结构第一次作业数据结构第一次作业一．单项选择题(20分)( )1.已知一算术表达式的后缀形式为ABC *+DE-/，则其中缀形式为 _________。

a、(A＋B *C)/(D-E)b、A+B*C /D-Ec、(A+B*C)/D-Ed、A+B*C/(D-E)( )2.若某链表中最常用的操作是在最后一个结点之后插入一个结点和删除第一个结点，则采用________存储方式最节省运算时间（假设链表仅设有一个first指针）。

a. 单链表b. 带头结点的双循环链表c. 单循环链表d. 双链表( )3.设一个栈的输入序列为A，B，C，D，则所得到的输出序列不可能是_______。

a. A，B，C，Db. D，C，B，Ac. A，C，D，Bd. D，A，B，C( )4.若线性表最常用的操作是存取第i个元素及其直接前驱的值，则采用_____存储方式节省时间。

a．顺序表 b．双链表 c．单循环链表 d．单链表( )5.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为_______。

(1≤i≤n+1)a、O(0)b、O(1)c、O(n)d、O(n2)( )6.若指针L指向一带头结点的循环单链表的头结点，该表为空表的条件是_______为真值；a. !( L -> link );b. L == (L -> link) -> link;c. L -> link;d. L == L -> link;( )7.用数组A[0..N-1]存放一个循环队列，一元素出队时，其队头指针front的修改方法是________：a. front = (front + 1) mod N;b. front = (front - 2)mod N;c. front = front + 1;d. front = front – 2;( )8.若用Head()和Tail()分别表示取广义表的表头和表尾，广义表A=（1,2,(3,4),(5,(6,7))），则Head(Tail(Head(Tail(Tail(A))))) 。

一．“七段数码管字形发生器”真值表（支持共阴极，1亮0灭）二．卡诺图化简：三．在Quartus 中，建工程，采用原理图设计方法，画整体电路图，设定I/O ，编译纠错第一次编译出错，Input与Output中部分名称重复，改Input中“A”为“In-A”，B、C、D同理。

第二次编译通过。

四．在Quartus中，对所设计的电路进行整体功能仿真：五．仅采用与非门实现的解决方案：根据摩根代换定律，将a~f的表达式改为与非式，在Quartus中重新用原理图的方法画出整体电路图，设定I/O，根据新表达式在电路中适当添加非门，编译纠错。

并对电路功能进行整体仿真。

六．支持共阳极数码管的解决方案：将a~f的输出信号按位取反。

即在各信号输出之前添加非门。

七．填写真值表：八．自定义三个4变量功能函数（不能重复前面的三变量函数功能），填写真值表：九．小结：首先明白了数码管工作原理后，通过写出a~f输出变量的表达式熟练了将真值表在卡诺图上表示的方法。

（由于BD字样不易显示，选用小写b和d）之后在摸索中掌握了Quartus中原理图的使用方法。

第一次编译得知在定义名称时字母不区分大写小写，A与a 将被视为重复命名。

第二次只是有几个warnings，给忽略了。

进行仿真时，由于和原理图设计是分两次进行的，在选择“Node Finder...”插入节点时系统没有自动选中我之前保存的bdf文件，显示“No node available”。

重新打开之前的工程文件重试后成功。

在仿真时不知道是否应该将ABCD连续设置16次分别观察是否显示0~F，还是将输入信号设为随即信号，整体观察。

后来一想没啥区别，后者逐个信号竖向观察就能知道显示的数字对不对，还更方便。

观察仿真波形发现，在固定输入信号时，确实输出的信号符合要求。

选做题没想出好方法，觉得只有同时连两条线路才可实现。

其实已开始对这个软件真是无从下手。

多亏几个朋友对我的帮助，我才掌握了基本使用方法。

现代密码学总结现代密码学总结第⼀讲绪论1、密码学是保障信息安全的核⼼2、安全服务包括：机密性、完整性、认证性、不可否认性、可⽤性3、⼀个密码体制或密码系统是指由明⽂（m或p）、密⽂（c）、密钥（k）、加密算法（E）和解密算法（D）组成的五元组。

4、现代密码学分类：（1）对称密码体制：（⼜称为秘密密钥密码体制，单钥密码体制或传统密码体制）密钥完全保密；加解密密钥相同；典型算法：DES、3DES、AES、IDEA、RC4、A5 （2）⾮对称密码体制：（⼜称为双钥密码体制或公开密钥密码体制）典型算法：RSA、ECC第⼆讲古典密码学1、代换密码：古典密码中⽤到的最基本的处理技巧。

将明⽂中的⼀个字母由其它字母、数字或符号替代的⼀种⽅法。

（1）凯撒密码：c = E(p) = (p + k) mod (26)p = D(c) = (c –k) mod (26)（2）仿射密码：明⽂p ∈Z26，密⽂c ∈Z26 ，密钥k=(a,b)ap+b = c mod (26)（3）单表代换、多表代换Hill密码：（多表代换的⼀种）——明⽂p ∈(Z26)m，密⽂c ∈(Z26)m，密钥K ∈{定义在Z26上m*m的可逆矩阵}——加密 c = p * K mod 26解密p = c * K-1 mod 26Vigenere密码：查表解答（4）转轮密码机：2、置换密码：将明⽂字符按照某种规律重新排列⽽形成密⽂的过程列置换，周期置换3、密码分析：（1）统计分析法：移位密码、仿射密码和单表代换密码都没有破坏明⽂的频率统计规律，可以直接⽤统计分析法（2）重合指数法完全随机的⽂本CI=0.0385，⼀个有意义的英⽂⽂本CI=0.065实际使⽤CI 的估计值CI ’：L ：密⽂长。

fi ：密⽂符号i 发⽣的数⽬。

第三讲密码学基础第⼀部分密码学的信息论基础1、 Shannon 的保密通信系统模型（1）对称密码体制（2）（3）⼀个密码体制是⼀个六元组：（P , C, K 1, K 2, E, D )P--明⽂空间C--密⽂空间K 1 --加密密钥空间 K 2--解密密钥空间E --加密变换D --解密变换对任⼀k ∈K 1,都能找到k’∈K 2，使得D k’ (E k (m ))=m ，?m ∈M.2、熵和⽆条件保密（1）设随机变量X={xi | i=1,2,…,n}, xi 出现的概率为Pr(xi) ≧0, 且, 则X 的不确定性或熵定义为熵H(X)表⽰集X 中出现⼀个事件平均所需的信息量(观察前)；或集X 中每出现⼀个事件平均所给出的信息量(观测后).（2）设X={x i |i=1,2,…,n}, x i 出现的概率为p (x i ) ≥0，且∑i=1,…,n p (x i )=1;0 )(1log )()(≥=∑ii ai x p x p X HY={y i |i=1,2,…,m}, y i 出现的概率为p (y i ) ≥0，且∑i=1,…,m p (y i )=1; 则集X 相对于集Y 的条件熵定义为（3） X 视为⼀个系统的输⼊空间，Y 视为系统的输出空间，通常将条件熵H (X|Y)称作含糊度，X 和Y 之间的平均互信息定义为：I (X,Y)=H (X)-H (X|Y) 表⽰X 熵减少量。

练习——简答题1.什么是算法？算法有哪些特征？答：算法是求解问题的⼀系列计算步骤。

算法具有有限性、确定性、可⾏性、输⼊性和输出性5个重要特征。

2.算法设计应满⾜的⼏个⽬标答：算法设计应满⾜正确性、可使⽤性、可读性、健壮性和⾼效率与低存储量需求。

3.算法设计的基本步骤答：算法设计的基本步骤是:(1)分析求解问题(2)选择数据结构和算法设计策略(3)描述算法(4)证明算法正确性(5)算法分析各步骤之间存在循环和反复过程。

4.什么是算法复杂性？它主要有哪两个⽅⾯构成？答：算法复杂性是算法运⾏时所需要的计算机资源的量，它包括两个⽅⾯：时间复杂性（需要时间资源的量）和空间复杂性（需要空间资源的量）。

5.分析算法复杂性的意义是什么？算法的复杂性是算法效率的度量，是评价算法优劣的重要依据。

⼀个算法的复杂性的⾼低体现在运⾏该算法所需要的计算机资源的多少上⾯，所需的资源越多，我们就说该算法的复杂性越⾼；反之，所需的资源越低，则该算法的复杂性越低。

6.f(n)=O(g(n))答：f(n)=O(g(n))当且仅当存在正常量c和n0，使当n≥n0时，f(n)≤cg(n)，即g(n)为f(n)的上界。

7.f(n)=W(g(n))答：f(n)=W(g(n))当且仅当存在正常量c和n0，使当n≥n0时，f(n)≥cg(n)，即g(n)为f(n)的下界。

8.f(n)=Q(g(n))答：f(n)=Q(g(n))当且仅当存在正常量c1、c2和n0，使当n≥n0时，有c1g(n)≤f(n)≤c2g(n)，即g(n)与f(n)的同阶。

9.算法的平均情况、最好情况、最坏情况，哪种情况的可操作性最好，最具有实际价值？答：设⼀个算法的输⼊规模为n，Dn是所有输⼊的集合，任⼀输⼊I∈Dn，P(I)是I出现的概率，有 =1，T(I)是算法在输⼊I下所执⾏的基本语句次数，则该算法的平均执⾏时间为：A(n)=算法的最好情况为：G(n)= ，是指算法在所有输⼊I下所执⾏基本语句的最少次数。

人生有几件绝对不能失去的东西:自制的力量，冷静的头脑，希望和信心 1计算复杂性理论总结报告一、 图灵机(1) 图灵机基本模型图灵机是山图灵(Alan Mathisom Turing)在1936年提出的，它是一个通用的计算 模型。

通过图灵机，来研究递归可枚举集和部分递归函数，对算法和可计算性进行研究 提供了形式化描述工具。

图灵机的基本模型包括一个有穷控制器，一条含有无数个带方格的输入带和一个读 写头。

其直观物理模型如下图1所示。

基本图灵动作有以下三种：(1) 改写被扫描带方格内容，控制器转化为下一状态。

(2) 读写头向左移一个带方格，控制器转化为下一状态。

(3) 读写头向左移一个带方格，控制器转化为下一状态。

图1图灵机(2) 图灵机形式化定义，图灵机演算过程及语言描述定义：一个基本图灵机定义为一个七元组TM={Q,C,6,A.B,ql,F)o 其中Q 是状态集合，(图灵机所有的状态)非空有限集；C 是带符号表，(放在带方格中的符号集合)非空集；6是控制函数或过程转换函数(定义控制器)6： QxCTQxCU (R.L)； A 是输入字母表，ACC ；B 是空白符，BGC ：ql 是初始状态，qlSQ ；F 是终态集，F £ Q.TM 的扫描符号串主要山6来确定：(1)5 (q, s)二(q‘，s'); (2)8 (q, s) =(q* , R); (3)8 (q, s) =(q* , L); (4) 6 (q, s)无效，对应无定义时图灵机终止。

TM 的工作用“格局”的转换来描述。

格局：6 ala2a3...aj-lqajaj+l...其中 qWQ, aiGC ；帯(1)若8 (q, ai)无定义，称o为停机格局；(2)若qEF,称o为接受格局；人生有几件绝对不能失去的东西:自制的力量，冷静的头脑，希望和信心__(3) 若q为初始状态，称o为初始格局;格局O到格局T的转换a 卜mt 若成立go 1 |~mlo2 卜m2。

算法的计算复杂性概念
计算复杂性是一个相当普遍的概念，用来衡量算法的复杂程度及其所需要的计算和存储资源。

它指出了通过解决一个特定问题所需要的资源数量和时间，是计算机科学领域中应用非常广泛的计算时间和空间复杂度理论。

计算复杂性的基本思想是：给定的算法的运行时间，由其所执行的基本步骤的重复次数决定。

这些步骤机会包括读写输出、内存操作、比较和逻辑判断等。

每一次的重复，都会消耗算法所需的资源。

算法的运行时间，在某程度上可以用消耗的资源数量来衡量。

计算复杂性概念被用来衡量算法空间和时间复杂度，以及评价算法效率，它是一种定量量度。

运行时间和空间复杂度由大O表示法来表示，Big O表示法在数学里描述函数增加量的时候，使用主要步骤多少来表示算法的复杂程度。

算法中最耗时的基本步骤是核心步，而计算复杂性可以衡量算法的效率，并评估算法的运行性能。

计算复杂性的概念历经多年，今天已经成为计算机科学领域的核心技术，深受计算性能分析专家、软件开发者和算法设计者的重视。

它不仅能够帮助识别算法效率的关键瓶颈，而且能够用精准的度量标准来比较两个算法的性能，帮助推进算法的改进，提高计算性能。

因此计算复杂性是一个极为重要的计算机科学概念，它能够用精确的方式衡量算法的复杂程度，用于评估算法的性能，以及帮助算法设计者和开发者识别算法缺陷并进行改进。

c语⾔第⼀次作业⼀、PTA实验作业题⽬1.温度转换本题要求编写程序，计算华⽒温度150°F对应的摄⽒温度。

计算公式：C=5×(F−32)/9，式中：C表⽰摄⽒温度，F表⽰华⽒温度，输出数据要求为整型。

1.实验代码int fahr,celsius;fahr = 150;celsius = 5*(fahr-32)/9;printf("fahr = 150, celsius = %d\n",celsius);2 设计思路主要描述题⽬算法。

第⼀步：定义华⽒温度fahr和摄⽒温度celsius第⼆步：输⼊题⽬中给定的华⽒温度150第三步：写出计算公式celsius = 5*(fahr-32)/9第四步：输出fahr和celsius的值3.本题调试过程碰到问题及解决办法错误：单词stdio拼写错误，写成studio。

解决⽅法：从头看了⼀下程序，发现错误之后改掉，继续看⼀下有没有其他错误，提交后答案正确。

4.本题PTA实验结果题⽬2.将x的平⽅赋值给y假设x的值为3，计算x的平⽅并赋值给y，分别以“y = x ∗ x”和“x ∗ x = y”的形式输出x和y的值。

1.实验代码int x,y;x=3;y=x*x;printf("%d = %d * %d\n",y,x,x);printf("%d * %d = %d",x,x,y);2. 设计思路主要描述题⽬算法。

第⼀步：定义整数x，y第⼆步：给出x的值x=3第三步：给出公式y=x*x第四步：输出9=3*3和3*3=93.本题调试过程碰到问题及解决办法（1）误解题⽬，认为是输出y=3*3和3*3=y解决⽅法：重新阅读了⼏遍题⽬，改了多次并与同学交流讨论理解题⽬意思（2）错误：没有⽤公式y=x*x，直接在输出语句中计算y解决⽅法：多次修改，试了⼏遍，根据提交后给出的错误的提⽰⼀直调试，最后终于答案正确。