牛客错题解析

本文参考自牛客错题解析

查看原文: 原文地址

1.如果I/O设备与存储设备间的数据交换不经过CPU来完成，则这种数据交换方式是
A：程序查询方式：检查条件及处理需要占用CPU时间；
B：中断模式：检查条件不占用CPU时间，满足条件进入中断处理子程序，此时需占用CPU；
C：DMA方式：由DMA控制器完成I/O与内存之间的请求，CPU占用仅发生在DMA请求阶段和结束阶段；
D：无条件存取方式：在处理过程中仍然需要占用CPU。


2.设计多道批处理系统时，首先要考虑的是（ ） _系统效率和吞吐量____
单道批处理注重顺序性
多到批处理方式为了提高资源利用率和吞吐量，周转时间长，无交互能力
分时系统为了实现人机交互，特点是多路性独立性及时性和交互性
实时系统最明显的特征是实时性和可靠性


3.一个西瓜切三次，最多可被分成多少块?
一）讨论直线分割平面
直线要想最多分割平面的前提：任意两条直线都要相交，任意三条直线不能交于同一点。
设n条直线最多分割平面为f(n)部分，一条直线分平面为两部分，f(1)=2;f(2)=4;f(3)=7;......，首先要弄明白的就是f(n)与f(n+1)的关系。
看新增加的第n+1条直线，由前提条件可知，增加的第n+1条直线，与前n条有 n个交点，而这n条直线又把第n+1条直线分成n+1段，而这n+1段又把它所在的平面一分为二，所以由n条直线增加到n+1条直线增加了n+1个区域。
二）讨论平面最大分割空间
满足条件的前提：所有平面都相交，任意三个平面不相交于同一直线。
设n个平面最多分割空间为F(n)个区域，一条直线分平面为两部分，即F(1)=2;F(2)=4;F(3)=8;......,接下来要弄清楚F(n)与F(n+1)的关系。
考察n+1个平面，前面的n个平面与这个平面相交得n条交线，已知这n条直线两两相交且没有任意三条直线相交于同一点，由前面讨论的结果知：n条直线最多分割平面为f(n)部分，而f(n)部分把他们所在的空间一分为二，这样有：F(n+1)=F(n)+f(n);


4.下面有关vector和list的区别，描述错误的是？  
**list不支持随机存取，不支持[]操作
vector和built-in数组类似，它拥有一段连续的内存空间，并且起始地址不变，因此它能非常好的支持随即存取，即[]操作符，但由于它的内存空间是连续的，所以在中间进行插入和删除会造成内存块的拷贝，另外，当该数组后的内存空间不够时，需要重新申请一块足够大的内存并进行内存的拷贝。这些都大大影响了vector的效率。 
list就是数据结构 中的双向链表(根据sgi stl源代码)，因此它的内存空间可以是不连续的，通过指针来进行数据的访问，这个特点使得它的随即存取变的非常没有效率，因此它没有提供[]操作符的重载。但由于链表的特点，它可以以很好的效率支持任意地方的删除和插入。 


5.首先栈和队列都是线性结构。栈只能在栈顶存取点，队列只能在头部取点，在队尾存点，因此都是限制存取点的线性结构


6.在C++中使用流进行输入输出，其中用于屏幕输出的对象是（ cout ）
cin，C++编程语言互换流中的标准输入流。
cout，C++编程语言互换流中的标准输出流。
cerr是C++预定义的标准错误输出函数，作用就是直接将参数（错误消息）打印到屏幕上。
CFile是MFC文件类的基类，它直接提供非缓冲的二进制磁盘输入/输出设备，并直接地通过派生类支持文本文件和内存文件。


7.下列哪些不是线性表？    关联数组
线性表具有如下的结构特点：
1).均匀性：虽然不同数据表的数据元素可以是各种各样的，
但对于同一线性表的各数据元素必定具有相同的数据类型和长度。
2).有序性：各数据元素在线性表中的位置只取决于它们的序号，
数据元素之前的相对位置是线性的，即存在唯一的“第一个“和
“最后一个”的数据元素，除了第一个和最后一个外，
其它元素前面均只有一个数据元素(直接前驱)和后面均只有一个数据元素
（直接后继）。
关联数组：关联数组和数组类似，它包含着类似于（键，值）的有序对，
是一种具有特殊索引方式的数组，关联数组的元素没有
特定的顺序。


8.同一进程下的线程可以共享（ data section ） 
线程共享的内容包括：
1).代码段（code segment）
2).数据段（data section）
3).进程打开的文件描述符、
4).信号的处理器、
5).进程的当前目录和
6).进程用户ID与进程组ID
一个进程可以包含多个线程，这些线程执行同一程序中的相同代码段或不同代码段，共享数据区和堆。一般认为，进程是资源分配的单位，线程是cpu的调度单位


9.常见文件系统 系统函数
fcntl  文件控制  
open  打开文件   
creat  创建新文件  
close  关闭文件描述字  
read  读文件  
write  写文件  
readv  从文件读入数据到缓冲数组中  
writev  将缓冲数组里的数据写入文件  
pread 对文件随机读  
pwrite  对文件随机写 


10.
分页：
分页存储管理器把进程的逻辑地址分成若干页，并为各页加上编号。相应的，内存也会被分成若干个物理块。为了正确的找到页对应的物理块，系统为每个进程添加了一份页表，页表需要的内存空间是连续的（使用多级页表可以缓解这个问题）。页表中存放了对应的物理块号，因此页表是一维的。
分段：
为了方便用户编程，作业的空间可以被分成若干个段，每个段的起始地址都是从0开始的，也就是说，每一段的地址是不连续的。但是段内的地址是连续的。在分段系统中，每个进程也会拥有一个段表，系统为每个段分配连续的内存空间。段表中存放着段长度和段的起始地址。因此，段表是二维的。
页式的逻辑地址是连续的，操作系统会自己去把虚拟地址划分成虚页号和页内偏移，它允许物理地址是空间是非连续的。段式的逻辑地址由段号和段内偏移组成，段号只是段的名称表示，当然可以不连续，A正确。在编程的时候，如果是分页存储，你只需要给定一个虚拟地址，然后操作系统会自己去把虚拟地址划分成虚页号和页内偏移，所以是一维的。如果是段式存储的话，你需要给定的虚拟地址必须包括虚段号和段内偏移量，因为分段式从程序员的角度来分的，操作系统并不知道，所以段式存储是二维的，B,C正确。D明显正确。页式采用动态重定位方式，动态重定位是指在进程运行时，每次读取指令的时候进行动态地址转换，需要硬件的支持，称为地址转换器在cpu中。该过程实在执行期间完成的。


11.
前序遍历：根结点 -> 左子树 -> 右子树
中序遍历：左子树 -> 根结点 -> 右子树
后序遍历：左子树 -> 右子树 -> 根结点


12.对二叉树的结点从1开始进行连续编号,要求每个结点的编号大于其左、右孩子的编号,在同一结点的左、右孩子中,其左孩子的编号小于其右孩子的编号,可采用()次序的遍历实现编号    后序
编号越迟，号值越大，题目要求：左子节点<右子节点<节点。明显是先遍历左子节点，然后右子节点，最后是节点本身


13.
1).平衡二叉树：它是一棵空树或者它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
2).二叉查找树：二叉排序树，又称二叉查找树，或者称为二叉搜索树。
二叉查找树或者是一棵空树，或者是具有下列性质的二叉树：
（1）若左子树不空，则左子树所有的结点的值均小于或者等于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于或者等于它的根结点的值；
（3）左、右子树也分别为二叉排序树


    我们知道，对于一般的二叉搜索树（Binary Search Tree），其期望高度（即为一棵平衡树时）为log2n，其各操作的时间复杂度（O(log2n)）同时也由此而决定。但是，在某些极端的情况下（如在插入的序列是有序的时），二叉搜索树将退化成近似链或链，此时，其操作的时间复杂度将退化成线性的，即O(n)。我们可以通过随机化建立二叉搜索树来尽量的避免这种情况，但是在进行了多次的操作之后，由于在删除时，我们总是选择将待删除节点的后继代替它本身，这样就会造成总是右边的节点数目减少，以至于树向左偏沉。这同时也会造成树的平衡性受到破坏，提高它的操作的时间复杂度。
    平衡二叉搜索树（Balanced Binary Tree）具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。常用算法有红黑树、AVL、Treap、伸展树等。在平衡二叉搜索树中，我们可以看到，其高度一般都良好地维持在O（log2n），大大降低了操作的时间复杂度。

最后

以上就是失眠月饼为你收集整理的牛客错题解析的全部内容，希望文章能够帮你解决牛客错题解析所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。