计算机二级考试选泽题必备知识点（第二部分）
创作者俱乐部成员
计算机二级考试选泽题必备知识点（第二部分）
采用静态地址重定位的是固定分区存储管理。
如果作业的逻辑地址空间大于计算机实际的物理内存空间，则应采取的存储管理技术是请求分页式管理。
连续存储管理的是分区式存储管理。
地址重定位方式包括静态地址重定位和动态地址重定位。
静态地址重定位要求程序必须占用连续固定的内存空间。
动态地址重定位不要求程序装入固定的内存空间，且允许冲虚在内存中再次移动位置。
文件属性包括：文件名称、文件长度、文件类型。
在操作系统中，将文件名称转换为文件存储地址的结构是文件目录。
在操作系统中，文件系统是指负责存取和管理文件信息的软件机构。
I/O方式中使计算机系统并行工作程度最高的是通道。
当CPU需要执行I/O操作时，程序将主动查询I/O设备是否准备好。
I/O方式中的程序中断方式是指当出现异常情况时，CPU暂时停止当前程序的运行，转向执行相应的服务程序。
I/O方式中的通道是指I/O设备与主存之间由硬件组成富饶直接数据通路，用于成组数据传送。
计算机I/O接口的功能包括实现电平转换、实现数据缓存以达到速度匹配、实现设备的选泽。
计算机系统的I/O方式包括程序查询、程序中断、通道。
计算机中运算器的基本功能是进行算术和逻辑运算。
理论上计算机虚拟内存最大容量取决于计算机地址位数。
计算机中的缓冲技术用于提高主机和设备交换信息的速度。
程序的局部性包括时间局部性和空间局部性两个方面。时间局部性是指如果一个存储项被访问，则该项在近期可能很快被再次访问。
空间局部性是指如果一个存储项被访问，则该项及其邻近的项也可能很快被访问。
并发程序具有共享性。
数据的存储结构会影响算法的效率。
算法设计必须考虑算法的复杂度，算法强调动态的执行过程，不同于静态的计算公式，算法必须能在有限个步骤之后终止。
对数据的压缩存储会降低算法的空间复杂度。
为了降低算法的空间复杂度，要求算法尽量采用原地工作。所谓的原地工作是指执行算法是所使用的额外空间固定，即不随算法所处理的数据空间大小的变化而变化。
非线性结构：具有两个根结点的数据结构、具有两个以上叶子结点的数据结构、具有一个根结点且只有一个叶子结点的数据结构都属于非线性结构。
线性结构一定能采用顺序存储结构，也能采用链式存储结构，有的非线性结构也能采用书序存储结构。
具有多个指针城的链表也可能是线性结构，循环队列属于线性结构，具有两个以上根结点的数据结构一定是非线性结构。
采用顺序存储的完全二叉树属于非线性结构。
在线性表的链式存储结构中，其存储空间一般是不连续的，并且前件结点的存储序号可以小于也可以大于后件结点的存储序号。
在线性表的顺序存储结构中，其存储空间连续，各个元素所占的字节数相同，元素的存储顺序与逻辑顺序一致。
在长度为n的顺序表中查找一个元素，假设需要查找的元素一定在表中，并且元素出现在表中每个位置上的可能性是相同的，则在平均情况下需要比较的次数为(n+1)/2.
设顺序表的长度为n，堆排序的比较次数小于n(n-1)/2。快速排序比较次数等于n(n-1)/2。
设栈的存储空间为S(1:50)，初始状态为top=51。现经过一系列正常的入栈与退栈操作后，top=50,则栈中的元素个数为1.
设栈的存储空间为S(1:60)，初始状态为top=60.现经过一系列正常的入栈与退栈操作后，top=1，则 栈中的元素个数为60。
设栈的存储空间为S(1:50)，初始状态为top=0.现经过一系列正常的入栈与退栈操作后，top=51，则 栈中的元素个数为不可能。
设栈的存储空间为S(1:m)，初始状态为top=m+1.现经过一系列正常的入栈与退栈操作后，top=0，则 栈中的元素个数为不可能。
设栈的存储空间为S(1:60)，初始状态为top=61.现经过一系列正常的入栈与退栈操作后，top=25，则 栈中的元素个数为36。
设栈的存储空间为S(1:50)，初始状态为top=-1.现经过一系列正常的入栈与退栈操作后，top=30，则 栈中的元素个数为30。
设栈的存储空间为S(1:m)，初始状态为top=m+1.则 栈中的数据元素个数为m-top+1.
设栈的存储空间为S(1:m)，初始状态为top=m+1.经过一系列入栈与退栈操作后，top=1.现又要讲一个元素进栈，栈顶指针top值变为发生栈满的错误。
某带链栈的初始状态为top=bottom=NULL,经过一系列正常的入栈与退栈操作后，top=bottom=20.该栈中的元素个数为1.
在带链栈中，经过一系列正常的操作后，如果top=bottom，则栈中的元素个数为0或1.
带链栈空的条件是top=bottom=NULL.
循环队列的存储空间为Q(1:50)，初始状态为front=rear=50.经过一系列的正常入队与退队操作后，front=rear=25，此后又插入一个元素，则循环队列中的元素个数为1或50且产生上溢错误。
循环队列的存储空间为Q(1:40)，初始状态为front=rear=40.经过一系列的正常入队与退队操作后，front=rear=15，此后又退出一个元素，则循环队列中的元素个数为39或0且产生下溢错误。
循环队列的存储空间为Q(1:100)，初始状态为front=rear=100.经过一系列的正常入队与退队操作后，front=rear=99，则循环队列中的元素个数为0或100.
循环队列的存储空间为Q(1:200)，初始状态为front=rear=200.经过一系列的正常入队与退队操作后，front=rear=1，则循环队列中的元素个数为0或200。
循环队列的存储空间为Q(1:100)，初始状态为空。现经过一系列的正常入队与退队操作后，front=49，则循环队列中的元素个数为不确定。
循环队列的存储空间为Q(1:50)，初始状态为front=rear=50，经过一系列的正常入队与退队操作后，front-1=rear。为了在该对列中寻找值最大的元素，在最坏情况下需要的比较次数为48。
