第四章 数据结构与算法递归函数执行时需要栈来提供支持。递归函数执行时其调用和返回控制是利用栈来进行的。数据结构中的栈常用来对函数调用和返回处理的控制进行支持。为支持函数调用及返回常采用称为栈的数据结构。递归过程或函数调用时处理参数及返回地址要用一种称为栈的数据结构。设 S是一个长度为n的非空字符串其中的字符各不相同则其互异的非平凡子串(非空且不同于S本身)的个数( n − 2 ) ( n − 1 ) 2 \frac{(n-2)(n-1)}22(n−2)(n−1)​。在C程序中有些变量随着其所在函数被执行而为其分配存储空间当函数执行结束后由系统回收。这些变量的存储空间应在栈区分配。含有n个元素的线性表采用顺序存储等概率删除其中任一个元素平均需要移动E d e l e t e ∑ i 1 n q i × ( n − i ) 1 n ∑ i 1 n ( n − i ) n − 1 2 E_{delete}\sum_{i1}^{n} q_i×(n-i)\frac{1}{n}\sum_{i1}^{n} (n-i)\frac{n-1}{2}Edelete​∑i1n​qi​×(n−i)n1​∑i1n​(n−i)2n−1​个元素。判定表和判定树常用于描述数据流图的加工逻辑。一个计算机算法是对特定问题求解步骤的一种描述。算法的效率是指算法能指执行算法时计算机资源的消耗包括计算机内存的消耗和计算机运行时间的消耗。按照逻辑关系的不同可将数据结构分为线性结构和非线性结构。常见的特殊矩阵有对称矩阵、三角矩阵和对角矩阵等。图的深度优先遍历算法类似与二叉树的先序遍历算法图的广度优先遍历算法类似与二叉树的层次遍历算法栈和队列的主要区别是插入运算和删除运算的要求不同。有n个结点的有序单链表中插入一个新结点并保持有序的运算的时间复杂度为O(n)。关系模型的基本数据结构是二维表。折半(二分)查找法适用的线性表应该满足顺序方式存储、元素有序的要求。根据枢轴元素(或基准元素)划分序列而进行排序的是快速排序。通过设置基准(枢轴)元素将待排序的序列划分为两个子序列使得其一个子序列的元素均不大于基准元素另一个子序列的元素均不小于基准元素然后再分别对两个子序列继续递归地进行相同思路的排序处理这种排序方法称为快速排序。进行快速排序时要求待排序的关键字序列采用顺序存储方式。为实现快速排序算法待排序列适合采用顺序存储。快速排序算法、归并排序算法采用了分治算法设计策略。若待排序记录按关键字基本有序则宜采用的排序方法是直接插入排序。堆排序是一种基于选择的排序方法。在最好和最坏情况下的时间复杂度均为O(nlog₂n)且稳定的排序方法是归并排序。对关键字序列k 1 , k 2 , . . . , k n {k_1,k_2,...,k_n}k1​,k2​,...,kn​进行排序时采用二路归并排序算法所需的辅助存储空间最多。设递增序列A为a 1 a 2 … . a n a_1a_2….a_na1​a2​….an​递增序列B为b 1 b 2 … b m b_1b_2…b_mb1​b2​…bm​且mn则将这两个序列合并为一个长度为mn的递增序列时当a n b 1 a_nb_1an​b1​时归并过程中元素的比较次数最少。若查找每个关键字的概率均等则在具有n个关键字的顺序表中采用顺序查找法查找一个记录若查找成功的平均查找长度ASL是n 1 2 \frac{n1}22n1​。若线性表采用链式存储结构则适用的查找方法为顺序查找。线性表采用单链表存储结构时访问表中元素的方式为顺序查找。用伪代码来描述算法时可以采用类似于程序设计语言的语法结构也易于转换为程序。稠密图适合采用邻接矩阵存储稀疏图适合采用邻接表存储。在哈希表中要按照确定的计算关系来找到给定关键码的存储位置。数据结构中()不是表示存储结构的术语。A.单向链表B.循环队列C.稀疏矩阵D.邻接矩阵在数据结构中存储结构物理结构是指数据在计算机内存中的具体存放方式常见的有顺序存储、链式存储、索引存储和散列存储等。常见的存储结构术语顺序存储结构数组一维、多维、顺序表、顺序栈、顺序队列包括循环队列、邻接矩阵图的顺序存储、双端队列的顺序实现等链式存储结构单向链表、双向链表、循环链表、静态链表、链栈、链队列、邻接表图的链式存储、十字链表用于稀疏矩阵或图、邻接多重表、二叉链表树的链式存储、三叉链表等索引存储结构稠密索引、稀疏索引、分块索引、B树、B树常用于文件索引散列存储结构哈希表散列表、哈希桶等其他特殊存储结构三元组表稀疏矩阵的顺序存储、广义表的存储如头尾链表、并查集的树形存储等常见干扰项线性结构线性表、栈、队列、串、广义表非线性结构树、二叉树、森林、图、集合特殊矩阵稀疏矩阵、对称矩阵、三角矩阵、对角矩阵设A是n*n常数矩阵(n1)X是由未知数X 1 、 X 2 、 . . . 、 X n X_1、X_2、...、X_nX1​、X2​、...、Xn​组成的列向量B是由常数b 1 、 b 2 、 . . . 、 b n b_1、b_2、...、b_nb1​、b2​、...、bn​组成的列向量线性方程组AXB有唯一解的充分必要条件不是A的秩不等于0。下表列出了数字0~9的某种二进制编码值及其在某类应用中出现的概率这种编码的平均位数大约为3。数字0123456789编码01011001101011011111001110111110111110111111概率40%15%10%5%5%5%5%5%5%5%这种编码是不定长的其长度从1位到6位不等。长度为1位的编码只有1种(数字0)出现的概率为40%;长度为2位的编码只有1种(数字1)出现的概率为15%;长度为4位的编码只有1种(数字2)出现的概率为10%;长度为5位的编码有5种(数字3~7)出现的概率共55%;长度为6位的编码有2种(数字8~9)出现的概率为25%。因此这种编码的平均位数(长度)等于40%*115%*210%*425%*510%*62.95.某市有N个考生参加了程序员上午和下午两科考试两科成绩都及格才能合格。设上午和下午考试科目的及格率分别为A和B合格率为C则C≤min(A,B)。N个考生参加了程序员上午和下午两科考试设上午考试有a人及格下午考试有b人及格两科都及格(合格)有c人。显然cSacsb因此c≤min(a,b)。min(a,b)是a和b中的最小值。因为Aa/NBb/NCc/N所以c/N≤a/Nc/N≤b/NC≤min(A,B)从任意初始值X开始通过迭代关系式X n X n − 1 / 2 1 ( n 1 2 . . ) X_nX_{n-1}/21(n12..)Xn​Xn−1​/21(n12..)可形成序列X 1 X 2 X_1X_2X1​X2​该序列将收敛于2。从任意初始值X 0 X_0X0​开始通过迭代关系式X n X n − 1 / 2 1 ( n 1 2 . . ) X_nX_{n-1}/21(n12..)Xn​Xn−1​/21(n12..)可形成序列X 1 X 0 / 2 1 X_1X_0/21X1​X0​/21X 2 X 0 / 2 2 1 / 2 1 X_2X_0/2^21/21X2​X0​/221/21X 3 X 0 / 2 3 1 / 2 2 1 / 2 1 X_3X_0/2^31/2^21/21X3​X0​/231/221/21X n X 0 / 2 n − 1 1 / 2 n − 2 . . . 1 / 2 1 X_nX_0/2^{n-1}1/2^{n-2}...1/21Xn​X0​/2n−11/2n−2...1/21其中首项的极限为0后面等比数列的和极限为2因此序列Xn的极限为2。(由于序列Xn的极限存在设其极限为X则对等式X n X n − 1 / 2 1 X_nX_{n-1}/21Xn​Xn−1​/21两边取极限得到XX/21因此X2。)某地区有1000人参加了程序员考试(包括上午科目和下午科目)其中上午科目45以上有700人下午科目45以上有600人据此可以推断至少有300人这两个科目的成绩同时在45分以上。某地区有1000人参加了程序员考试(包括上午科目和下午科目)其中上午科目45以上有700人下午科目45以上有600人那么至少有700600-1000300人这两个科的成绩同时在45分以上。已知cos 0.70acos 0.71b则用线性插值方法可求出cos 0.702的近似值为(4ab)/5。0.702位于0.70与0.71之间。如果将区间[0.70,0.71]分成5等分则分点依次为0.7020.7040.7060.708。其中0.702位于最靠近0.70处即与0.70的距离是区间长度的1/5。具体的表示式为0.702(4/5)×0.70(1/5)×0.71。按照线性插值方法它们的函数值也应有这样的比例:cos 0.702(4/5)×cos 0.70(1/5)×cos 0.71(4ab) /5.为了用二分法求函数f x ) x 3 − 2 x 2 − 0.1 fx)x^3-2x^2-0.1fx)x3−2x2−0.1的根(方程f(x)0的解)可以选择初始区间[2,3]。也就是说通过对该区间逐次分半可以逐步求出该函数的一个根的近似值。为了用二分法求函数f(x)的根(方程f()0的解)首先需要确定初始区间[x1x2]使f(x1)fx2)≤0。其原理是只要连续函数f(x)在某区间的两端点上符号相反则在该区间内必存在一个根。也就是说从负值连续变到正值必然会经过零值从正值连续变到负值也必然要经过0值。f(-2)-8-8-0.10f(-1)-1-2-0.10f(1)1-2-0.10f(2)8-8-0.10f(3)27-18-0.10所以在区间[23]中必然存在f(x)的一个根[23]可以作为二分法求f(x)之根的初始区间。第八章 标准化和知识产权基础知识新质生产力利用商业秘密权可以对软件的技术信息、经营信息提供保护。软件著作权的客体不包括软件开发思想。计算机软件著作权的客体1计算机程序包括源程序和目标程序2计算机软件的文档《中华人民共和国著作权法》和《计算机软件保护条例》是构成我国保护计算机软件著作权的两个基本法律文件。根据《计算机软件保护条例》的规定对软件著作权的保护不包括软件中采用的算法。行业标准代号我国行业标准代号由汉字拼音大写字母再加上斜杠和大写字母T组成推荐性行业标准(如QX表示气象行业标准)。地方标准代号由大写汉字拼音DB加上省、自治区、直辖市行政区划代码的前两位数字如北京市11、天津市12、上海市31等再加上斜线T组成推荐性地方标准不加斜线T为强制性地方标准。例如DBIl表示北京市标准DB31/T表示上海市堆荐性标准。企业标准的代号由汉字大写拼音字母Q加斜杠再加企业代号组成(Q/xxx)企业代号可由大写拼音字母或阿拉数字组成或者两者兼用。标准代号行业/领域说明QB轻工历史“轻标”的拼音而非“轻工”全拼QJ航天第七机械工业部“七机”DB地震因DZ被【地质】占用另选的“地标”变体SB商业因SY被【石油】占用采用“商标”YD通信历史“邮电”的拼音标准代号GB表示我国国家标准的代号标准代号GJB表示由我国国防科学技术工业委员会批准适合于国防部门和军队使用的标准(行业标准)标准代号IEEE表示美国电气和电子工程师学会标准(行业标准)如果IEEE冠有ANSI字头便具有国家标准的性质标准代号ISO表示国际标准化组织(ISO)制定或批准的国际标准。发表权和著作财产权的保护期限为50年。单个自然人的软件著作权保护期为自然人终生及其死亡后50年。根据著作权法规定当著作权属于公民时著作权人署名权的保护期为永久。(1)公民的作品其发表权和著作财产权的保护期限为作者的终生及其死亡后50年截止于作者死亡后第50年的12月31日。例如甲在1980年3月4日创作了一作品但没有发表甲在2000年的10月1日死亡那么其发表权和著作财产权的保护期限将从1980年3月4日开始计算并截止于2050年的12月31日。(2)法人或者其他组织的作品以及著作权(署名权除外)由法人或其他组织享有的职务作品其发表权和著作财产权的保护期限为50年一般从作品首次发表时开始计算截止于作品首次发表后第50年的12月31日。但如果作品自创作完成后50年内没有发表的著作权法不再给予保护。(3)电影作品和以类似摄制电影的方法创作的作品、摄影作品其发表权和著作财产权的保护期限为50年截止于作品首次发表后第50年的12月31日但作品自创作完成后50年内没有发表的其著作权不再受保护。(4)合作作品的发表权、著作财产权的保护期限为作者终生加死亡后50年截止于最后死亡的作者死亡后第50年的12月31日。例如甲与乙于1980年3月4日创作了一作品如果甲在1990年的8月1日死亡乙在2000年的10月1日死亡那么该作品的发表权和著作财产权的保护期限将从1980年3月4日开始计算并截止于2050年的12月31日。(5)作者身份不明的作品著作财产权的保护期限为50年截止于作品首次发表后第50年的12月31日。发明专利权的保护期限为20年。外观设计专利权的保护期限为10年。实用新型专利权的保护周期为10年。公民的作品其发表权权利的保护期为作者终生及其死亡后五十年截止于作者死亡后第五十年的12月31日如果是合作作品截止于最后死亡的作者死亡后第五十年的12月31日。著作人身权 著作财产权著作人身权①发表权 ②开发者身份权也称为署名权③修改权 ④保护作品完整权著作财产权①复制权 ②发行权 ③出租权 ④展览权 ⑤表演权 ⑥放映权 ⑦广播权 ⑧信息网络传播权 ⑨摄制权 ⑩改编权 ⑪翻译权【一种自然语言文字转换成另一种自然语言文字】 ⑫汇编权 ⑬应当由著作权人享有的其他权利计算机软件著作权权利中发表权和署名权是不可以转让的。在下列情况下使用作品可以不经著作权人许可不向其支付报酬但应当指明作者姓名、作品名称并且不得侵犯著作权人依照本法享有的其他权利(一)为个人学习、研究或者欣赏使用他人已经发表的作品(二)为介绍、评论某一作品或者说明某一问题在作品中适当引用他人已经发表的作品(三)为报道时事新闻在报纸、期刊、广播电台电视台等媒体中不可避免地再现或者引用已经发表的作品(四)报纸、期刊、广播电台、电视台等媒体刊登或者播放其他报纸、期刊、广播电台、电视台等媒体已经发表的关于政治、经济、宗教问题的时事性文章但作者声明不许刊登、播放的除外(五)报纸、期刊、广播电台、电视台等媒体刊登或者播放在公众集会上发表的讲话但作者声明不许刊登、播放的除外(六)为学校课堂教学或者科学研究翻译或者少量复制已经发表的作品供教学或者科研人员使用但不得出版发行(七)国家机关为执行公务在合理范围内使用已经发表的作品(八)图书馆、档案馆、纪念馆、博物馆、美术馆等为陈列或者保存版本的需要复制本馆收藏的作品(九)免费表演已经发表的作品该表演未向公众收取费用也未向表演者支付报酬(十)对设置或者陈列在室外公共场所的艺术作品进行临摹、绘画、摄影、录像(十一)将中国公民、法人或者其他组织已经发表的以汉语言文字创作的作品翻译成少数民族语言文字作品在国内出版发行(十二)将已经发表的作品改成盲本馆收藏的作前款规定适用于对出版者、表演者、录音录像制作者、广播电台、电视台的权利的限制。《著作权法》第5条规定本法不适用于(1)法律、法规国家机关的决议、决定、命令和其他具有立法、行政、司法性质的文件及其官方正式译文:(2)时事新闻(3)历法、通用数表、通用表格和公式。两名以上的申请人分别就同样的软件发明创造申请专利时最先申请的人可取得专利权。商标权保护的对象是注册商标。知识产权权利人Owner of Intellectual Property指合法占有某项知识产权的自然人或法人即知识产权权利人包括专利权人、商标注册人、版权所有人等。对计算机软件的法律保护不涉及知识产权法。根据《计算机软件保护条例》的规定当软件作品创作完成并固定在某种有形物体上后其软件著作权才能得到保护。将他人的软件光盘占为己有的行为是侵犯有形财产所有权行为。李某购买了一张有注册商标的正版软件光盘擅自将其复制出售则该行为侵犯了开发商的知识产权。张某购买了一张有注册商标的应用软件光盘并擅自复制出售则其行为是侵犯软件著作权行为。将他人的软件光盘占为已有涉及的是物体本身即软件的物化载体该行为是侵犯财产所有权的行为。如果行为人虽未占有这一软件光盘(如借或租他人一张软件光盘使用后返还)但擅自将该软件光盘复制出售则该行为涉及的是无形财产即软件开发商的思想表现形式(知识产品)属于侵犯知识产权行为。