计算机软件资格考试—第四章数据结构与算法和第八章标准化和知识产权基础知识-Seo优化-合肥市网站建设公司

第四章数据结构与算法

递归函数执行时，需要栈来提供支持。
递归函数执行时，其调用和返回控制是利用栈来进行的。
数据结构中的栈常用来对函数调用和返回处理的控制进行支持。
为支持函数调用及返回，常采用称为栈的数据结构。
递归过程或函数调用时，处理参数及返回地址要用一种称为栈的数据结构。
设 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_{i=1}^{n} q_i×(n-i)=\frac{1}{n}\sum_{i=1}^{n} (n-i)=\frac{n-1}{2}Edelete=∑i=1nqi×(n−i)=n1∑i=1n(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_1，a_2，….，a_na1，a2，….，an，递增序列B为b 1 ， b 2 ， … ， b m b_1，b_2，…，b_mb1，b2，…，bm，且m>n，则将这两个序列合并为一个长度为m+n的递增序列时，当a n < b 1 a_n<b_1an<b1时，归并过程中元素的比较次数最少。
若查找每个关键字的概率均等，则在具有n个关键字的顺序表中采用顺序查找法查找一个记录，若查找成功的平均查找长度ASL是n + 1 2 \frac{n+1}22n+1。
若线性表采用链式存储结构，则适用的查找方法为顺序查找。
线性表采用单链表存储结构时，访问表中元素的方式为顺序查找。
用伪代码来描述算法时，可以采用类似于程序设计语言的语法结构，也易于转换为程序。
稠密图适合采用邻接矩阵存储，稀疏图适合采用邻接表存储。
在哈希表中，要按照确定的计算关系来找到给定关键码的存储位置。
数据结构中，()不是表示存储结构的术语。
A.单向链表
B.循环队列
C.稀疏矩阵
D.邻接矩阵

在数据结构中，存储结构（物理结构）是指数据在计算机内存中的具体存放方式，常见的有顺序存储、链式存储、索引存储和散列存储等。
常见的存储结构术语
顺序存储结构：数组（一维、多维）、顺序表、顺序栈、顺序队列（包括循环队列）、邻接矩阵（图的顺序存储）、双端队列的顺序实现等
链式存储结构：单向链表、双向链表、循环链表、静态链表、链栈、链队列、邻接表（图的链式存储）、十字链表（用于稀疏矩阵或图）、邻接多重表、二叉链表（树的链式存储）、三叉链表等
索引存储结构：稠密索引、稀疏索引、分块索引、B树、B+树（常用于文件索引）
散列存储结构：哈希表（散列表）、哈希桶等
其他特殊存储结构：三元组表（稀疏矩阵的顺序存储）、广义表的存储（如头尾链表）、并查集的树形存储等

常见干扰项：
线性结构：线性表、栈、队列、串、广义表
非线性结构：树、二叉树、森林、图、集合
特殊矩阵：稀疏矩阵、对称矩阵、三角矩阵、对角矩阵

设A是n*n常数矩阵(n>1)，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组成的列向量，线性方程组AX=B有唯一解的充分必要条件不是A的秩不等于0。
下表列出了数字0~9的某种二进制编码值及其在某类应用中出现的概率，这种编码的平均位数大约为3。

数字	0	1	2	3	4	5	6	7	8	9
编码	0	10	1100	11010	11011	11100	11101	11110	111110	111111
概率	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%*1+15%*2+10%*4+25%*5+10%*6=2.95.

某市有N个考生参加了程序员上午和下午两科考试两科成绩都及格才能合格。设上午和下午考试科目的及格率分别为A和B，合格率为C，则C≤min(A,B)。

N个考生参加了程序员上午和下午两科考试，设上午考试有a人及格，下午考试有b人及格，两科都及格(合格)有c人。显然cSa，csb，因此c≤min(a,b)。min(a,b)是a和b中的最小值。因为A=a/N，B=b/N，C=c/N，所以c/N≤a/N，c/N≤b/N，C≤min(A,B)

从任意初始值X开始，通过迭代关系式X n = X n − 1 / 2 + 1 ( n = 1 ， 2 ， . . ) X_n=X_{n-1}/2+1(n=1，2，..)Xn=Xn−1/2+1(n=1，2，..)可形成序列X 1 ， X 2 X_1，X_2X1，X2，该序列将收敛于2。

从任意初始值X 0 X_0X0开始，通过迭代关系式X n = X n − 1 / 2 + 1 ( n = 1 ， 2 ， . . ) X_n=X_{n-1}/2+1(n=1，2，..)Xn=Xn−1/2+1(n=1，2，..)，可形成序列：X 1 = X 0 / 2 + 1 X_1=X_0/2+1X1=X0/2+1
X 2 = X 0 / 2 2 + 1 / 2 + 1 X_2=X_0/2^2+1/2+1X2=X0/22+1/2+1
X 3 = X 0 / 2 3 + 1 / 2 2 + 1 / 2 + 1 X_3=X_0/2^3+1/2^2+1/2+1X3=X0/23+1/22+1/2+1
X n = X 0 / 2 n − 1 + 1 / 2 n − 2 + . . . + 1 / 2 + 1 X_n=X_0/2^{n-1}+1/2^{n-2}+...+1/2+1Xn=X0/2n−1+1/2n−2+...+1/2+1
其中首项的极限为0，后面等比数列的和极限为2，因此序列Xn的极限为2。
(由于序列Xn的极限存在，设其极限为X，则对等式X n = X n − 1 / 2 + 1 X_n=X_{n-1}/2+1Xn=Xn−1/2+1两边取极限得到X=X/2+1，因此X=2。)

某地区有1000人参加了程序员考试(包括上午科目和下午科目)，其中上午科目45以上有700人，下午科目45以上有600人，据此可以推断，至少有300人这两个科目的成绩同时在45分以上。

某地区有1000人参加了程序员考试(包括上午科目和下午科目)，其中上午科目45以上有700人，下午科目45以上有600人，那么至少有700+600-1000=300人这两个科的成绩同时在45分以上。

已知cos 0.70=a，cos 0.71=b，则用线性插值方法可求出cos 0.702的近似值为(4a+b)/5。

0.702位于0.70与0.71之间。如果将区间[0.70,0.71]分成5等分，则分点依次为0.702，0.704，0.706，0.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=(4a+b) /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的解)，首先需要确定初始区间[x1，x2]，使f(x1)fx2)≤0。其原理是：只要连续函数f(x)在某区间的两端点上符号相反，则在该区间内必存在一个根。也就是说，从负值连续变到正值必然会经过零值；从正值连续变到负值也必然要经过0值。f(-2)=-8-8-0.1<0；f(-1)=-1-2-0.1<0；f(1)=1-2-0.1<0；f(2)=8-8-0.1<0；f(3)=27-18-0.1>0
所以，在区间[2，3]中必然存在f(x)的一个根，[2，3]可以作为二分法求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日。