搜索
计算机等级二级公共基础知识部分(1)在下列选项中，哪个不是一个算法一般应该具有的基本特征______。(C)A.确定性B.可行性C.无穷性D.有穷性有穷性：一个算法应包含有限的操作步骤而不能是无限的。或是有限时间内停止。确定性：算法中每一个步骤应当是确定的，而不能应当是含糊的、模棱两可的。有零个或多个输入。有一个或多个输出。有效性：算法中每一个步骤应当能有效地执行，并得到确定的结果。对于程序设计人员，必须会设计算法，并根据算法写出程序(2)希尔排序法属于哪一种类型算法的排序法______。(B)A.交换类排序法B.插入类排序法C.选择类排序法D.建堆排序法属于插入类排序,是将整个无序列分割成若干小的子序列分别进行插入排序排序过程：先取一个正整数d1n，把所有序号相隔d1的数组元素放一组，组内进行直接插入排序；然后取d2d1，重复上述分组和排序操作；直至di=1，即所有记录放进一个组中排序为止(3)下列关于队列的叙述中正确的是______。(C)A.在队列中只能插入数据B.在队列中只能删除数据C.队列是先进先出的线性表D.队列是先进后出的线性表队列是一种特殊的线性表，它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。队列具有先进先出（FIFO）的特点。队列空的条件：front=rear队列满的条件：rear=MAXSIZE队列可以用数组Q[1…ｍ]来存储，数组的上界ｍ即是队列所容许的最大容量。在队列的运算中需设两个指针：head：队头指针，指向实际队头元素的前一个位置tall：队尾指针，指向实际队尾元素所在的位置一般情况下，两个指针的初值设为０，这时队列为空，没有元素。图1(a)画出了一个由６个元素构成的队列，数组定义Q[1…10]。Q(i)i=3,4,5,6,7,8头指针head＝2，尾指针tail＝8。队列中拥有的元素个数为:L=tail-head现要让排头的元素出队，则需将头指针加１。即head=head+1这时头指针向上移动一个位置，指向Q(3)，表示Q(3)已出队。见图1(b)。如果想让一个新元素入队，则需尾指针向上移动一个位置。即tail=tail+1这时Q(9)入队，见图1(c)。当队尾已经处理在最上面时，即tail=10，如果还要执行入队操作，则要发生上溢，但实际上队列中还有三个空位置，所以这种溢出称为假溢出。克服假溢出的方法有两种。一种是将队列中的所有元素均向低地址区移动，显然这种方法是很浪费时间的；另一种方法是将数组存储区看成是一个首尾相接的环形区域。当存放到n地址后，下一个地址就翻转为１。在结构上采用这种技巧来存储的队列称为循环队列循环队的入队算法如下：1、tail=tail+1；2、若tail=n+1，则tail=1；3、若head=tail尾指针与头指针重合了，表示元素已装满队列，则作上溢出错处理；4、否则，Q(tail)=X，结束（X为新入出元素）。队列和栈一样，有着非常广泛的应用。操作类型作用返回值例子length(s)函数求字符串s的长度整型s:='123456789';l:=length(s);{l的值为9}copy（s,w,k)函数复制s中从w开始的k位字符串s:='123456789';s1:=copy(s,3,5);{s1的值是'34567'}val(s,k,code)过程将字符串s转为数值，存在k中；code是错误代码vars:string;k,code:integer;begins:='1234';val(s,k,code);write(k);{k=1234}str(i,s)过程将数值i转为字符串si:=1234;str(i,s);write(s);{s='1234'}Delete(s,w,k)过程在s中删除从第w位开始的k个字符s:='HonestAbeLincoln';Delete(s,8,4);Writeln(s);{'HonestLincoln'}Insert(s1,S,w)过程将s1插到s中第w位S:='HonestLincoln';Insert('Abe',S,8);{'HonestAbeLincoln'}Pos(c,S)函数求字符c在s中的位置整型S:='123.5';i:=Pos('',S);{i的值为1}+运算符将两个字符串连接起来s1:='1234';s2:='5678';s:=s1+s2;{'12345678'}在STL中，对队列的使用很是完美(4)对长度为N的线性表进行顺序查找，在最坏情况下所需要的比较次数为______。(B)A.N+1B.NC.(N+1)/2D.N/2线性表是最基本、最简单、也是最常用的一种数据结构。线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的。线性表的逻辑结构简单，便于实现和操作。因此，线性表这种数据结构在实际应用中是广泛采用的一种数据结构。线性表是一种常用的数据结构，本章介绍线性表及其顺序存储，并对栈和队列及它们的顺序实现给出了详细的设计描述。在实际应用中，线性表都是以栈、队列、字符串、数组等特殊线性表的形式来使用的。由于这些特殊线性表都具有各自的特性，因此，掌握这些特殊线性表的特性，对于数据运算的可靠性和提高操作效率都是至关重要的。(5)信息隐蔽的概念与下述哪一种概念直接相关______。(B)A.软件结构定义B.模块独立性C.模块类型划分D.模拟耦合度(6)面向对象的设计方法与传统的的面向过程的方法有本质不同，它的基本原理是______。(C)A.模拟现实世界中不同事物之间的联系B.强调模拟现实世界中的算法而不强调概念C.使用现实世界的概念抽象地思考问题从而自然地解决问题D.鼓励开发者在软件开发的绝大部分中都用实际领域的概念去思考(7)在结构化方法中，软件功能分解属于下列软件开发中的阶段是______。(C)A.详细设计B.需求分析C.总体设计D.编程调试(8)软件调试的目的是______。(B)A.发现错误B.改正错误C.改善软件的性能D.挖掘软件的潜能(9)按条件f对关系R进行选择，其关系代数表达式为______。(C)A.R|X|RB.R|X|RC.бf(R)D.∏f(R)(10)数据库概念设计的过程中，视图设计一般有三种设计次序，以下各项中不对的是______。(D)A.自顶向下B.由底向上C.由内向外D.由整体到局部(1)数据结构中，与所使用的计算机无关的是数据的______。(C)A.存储结构B.物理结构C.逻辑结构D.物理和存储结构(2)栈底至栈顶依次存放元素A、B、C、D，在第五个元素E入栈前，栈中元素可以出栈，则出栈序列可能是______。(D)A.ABCEDB.DBCEAC.CDABED.DCBEA栈是一种数据结构，它按照后进先出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。栈是只能在某一端插入和删除的特殊线性表。用桶堆积物品，先堆进来的压在底下，随后一件一件往堆。取走时，只能从上面一件一件取。堆和取都在顶部进行，底部一般是不动的。栈就是一种类似桶堆积物品的数据结构，进行删除和插入的一端称栈顶，另一堆称栈底。插入一般称为进栈（PUSH），删除则称为退栈（POP）。栈也称为后进先出表（LIFO表）。(3)线性表的顺序存储结构和线性表的链式存储结构分别是______。(B)A.顺序存取的存储结构、顺序存取的存储结构B.随机存取的存储结构、顺序存取的存储结构C.随机存取的存储结构、随机存取的存储结构D.任意存取的存储结构、任意存取的存储结构(4)在单链表中，增加头结点的目的是______。(A)A.方便运算的实现B.使单链表至少有一个结点C.标识表结点中首结点的位置D.说明单链表是线性表的链式存储实现(5)软件设计包括软件的结构、数据接口和过程设计，其中软件的过程设计是指______。(B)A.模块间的关系B.系统结构部件转换成软件的过程描述C.软件层次结构D.软件开发过程软件设计包括软件的结构设计，数据设计，接口设计和过程设计．结构设计是指：定义软件系统各主要部件之间的关系数据设计是指：将模型转换成数据结构的定义接口设计是指：软件内部，软件和操作系统间以及软件和人之间如何通信过程设计是指：系统结构部件转换成软件的过程描述(6)为了避免流程图在描述程序逻辑时的灵活性，提出了用方框图来代替传统的程序流程图，通常也把这种图称为______。(B)A.PAD图B.N-S图C.结构图D.数据流图(7)数据处理的最小单位是______。(C)A.数据B.数据元素C.数据项D.数据结构(8)下列有关数据库的描述，正确的是______。(C)A.数据库是一个DBF文件B.数据库是一个关系C.数据库是一个结构化的数据集合D.数据库是一组文件(9)单个用户使用的数据视图的描述称为______。(A)A.外模式B.概念模式C.内模式D.存储模式(10)需求分析阶段的任务是确定______。(D)A.软件开发方法B.软件开发工具C.软件开发费用D.软件系统功能(1)在计算机中，算法是指______。(C)A.查询方法B.加工方法C.解题方案的准确而完整的描述D.排序方法(2)栈和队列的共同点是______。(C)A.都是先进后出B.都是先进先出C.只允许在端点处插入和删除元素D.没有共同点(3)已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是______。(A)A.cedbaB.acbedC.decabD.deabc从二叉树的递归定义可知，一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此，在任一给定结点上，可以按某种次序执行三个操作：（1）访问结点本身(N)，（2）遍历该结点的左子树(L)，（3）遍历该结点的右子树(R)。以上三种操作有六种执行次序：NLR、LNR、LRN、NRL、RNL、RLN。注意：前三种次序与后三种次序对称，故只讨论先左后右的前三种次序。2．三种遍历的命名根据访问结点操作发生位置命名：①NLR：前序遍历(PreorderTraversal亦称(先序遍历))——访问结点的操作发生在遍历其左右子树之前。②LNR：中序遍历(InorderTraversal)——访问结点的操作发生在遍历其左右子树之中(间)。③LRN：后序遍历(PostorderTraversal)——访问结点的操作发生在遍历其左右子树之后。注意：由于被访问的结点必是某子树的根，所以N(Node)、L(Leftsubtree)和R(Rightsubtree)又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。(4)在下列几种排序方法中，要求内存量最大的是______。(D)A.插入排序B.选择排序C.快速排序D.归并排序一、冒泡排序已知一组无序数据a[1]、a[2]、……a[n]，需将其按升序排列。首先比较a[1]与a[2]的值，若a[1]大于a[2]则交换两者的值，否则不变。再比较a[2]与a[3]的值，若a[2]大于a[3]则交换两者的值，否则不变。再比较a[3]与a[4]，以此类推，最后比较a[n-1]与a[n]的值。这样处理一轮后，a[n]的值一定是这组数据中最大的。再对a[1]~a[n-1]以相同方法处理一轮，则a[n-1]的值一定是a[1]~a[n-1]中最大的。再对a[1]~a[n-2]以相同方法处理一轮，以此类推。共处理n-1轮后a[1]、a[2]、……a[n]就以升序排列了。优点：稳定，比较次数已知；缺点：慢，每次只能移动相邻两个数据，移动数据的次数多。二、选择排序已知一组无序数据a[1]、a[2]、……a[n]，需将其按升序排列。首先比较a[1]与a[2]的值，若a[1]大于a[2]则交换两者的值，否则不变。再比较a[1]与a[3]的值，若a[1]大于a[3]则交换两者的值，否则不