75 题以后

题目 76

下面有关Cookie的说法，错误的是

  • Cookie不是只有一个，而是一个网站一个

  • Cookie总是保存在客户端中，按在客户端中的存储位置，可分为内存Cookie和硬盘Cookie

  • 在HTTP请求中的Cookie是密文传递的

  • 有一些Cookie在用户退出会话的时候就被删除了，这样可以有效保护个人隐私

正确答案及解析

答案：C

HTTP的cookie是明文传送的，HTTPS的cooike是密文传送的。

题目 77

关于 linux 的进程，下面说法不正确的是：

  • 僵尸进程会被 init 进程接管，不会造成资源浪费；

  • 孤儿进程的父进程在它之前退出，会被 init 进程接管，不会造成资源浪费；

  • 进程是资源管理的最小单位，而线程是程序执行的最小单位。Linux 下的线程本质上用进程实现；

  • 子进程如果对资源只是进行读操作，那么完全和父进程共享物理地址空间。

正确答案及解析

答案：A

孤儿进程：一个父进程退出，而它的一个或多个子进程还在运行，那么那些子进程将成为孤儿进程。孤儿进程将被init进程(进程号为1)所收养，并由init进程对它们完成状态收集工作。

僵尸进程：一个进程使用fork创建子进程，如果子进程退出，而父进程并没有调用wait或waitpid获取子进程的状态信息，那么子进程的进程描述符仍然保存在系统中。这种进程称之为僵死进程。

题目 78

拓扑结构指的是（）的拓扑结构。

  • 资源网络

  • 通信网络

  • 线路网络

  • 链路

正确答案及解析

答案：A

计算机网络拓扑结构是指网络中各个站点相互连接的形式，各个站点抽象来说都是网络资源。

计算机网络的最主要的拓扑结构有总线型拓扑、环型拓扑、树型拓扑、星型拓扑、混合型拓扑以及网状拓扑。其中环形拓扑、星形拓扑、总线拓扑是三个最基本的拓扑结构。在局域网中，使用最多的是星型结构。

题目 79

在下面的叙述中正确的是()。

  • 线程是比进程更小的能独立运行的基本单位

  • 引入线程可提高程序并发执行的程度，可进一步提高系统效率

  • 线程的引入增加了程序执行时时空开销

  • 一个进程一定包含多个线程

正确答案及解析

答案：B

选B，A线程不能独立运行，线程需要进程所获得的资源。

C引入线程机制降低了时空的开销。

D一个进程至少包含一个主线程（线程数量大于等于1）。

题目 80

已知有一个关键字序列：（19，14,23,1,68,20,84,27,55,11,10,79）散列存储在一个哈希表中，若散列函数为H（key）=key%7，并采用链地址法来解决冲突，则在等概率情况下查找成功的平均查找长度为（）。

正确答案及解析

答案：1.5

这些关键字除以7取余后分别得到5,0,2,1,5,6,0,6，6，4,3,2存储结构如下
位置--存储
0-----14-84 //14查找1次，84需要查找2次，以下类似
1-----1
2-----23-79
3-----10
4-----11
5-----19-68
6-----20-27-55
总查找次数为1+2+1+1+2+1+1+1+2+1+2+3=18
总共有12的关键字
平均查找次数为18/12=1.5

题目 81

Longest Increasing Subsequence (LIS) means a sequence containing some elements in another sequence by the same order, and the values of elements keeps increasing.For example, LIS of {2, 1, 4, 2, 3, 7, 4, 6} is {1, 2, 3, 4, 6}, and its LIS length is 5. Considering an array with N elements, what is the average time and space complexity to get the length of LIS?

  • Time: N^2, Space: N^2

  • Time: N^2, Space: N

  • Time: NlogN, Space: N

  • Time: N, Space: N

  • Time: N, Space: C

正确答案及解析

答案：C

  • 最长递增子序列，可以用动态规划（DP）算法来求解。

  • 动态规划相当于递归的改进版，就是用辅助数组记录求解的中间过程来减少计算量。

  • 需要一个长度为N的辅助数组记录当前子串的最长递增子序列的长度。

  • 平均时间复杂度为NlogN，空间复杂度为N

最长递增子序列详解（longest increasing subsequence）

题目 82

某二叉树T有n个结点,设按某种顺序对T中的每个结点进行编号,编号为1,2,…,n,且有如下性质:T中任一结点V,其编号等于左子树上的最小编号减1,而V的右子树的结点中,其最小编号等于V左子树上结点的最大编号加1。这时是按()编号的

  • 中序遍历序列

  • 前序遍历序列

  • 后序遍历序列

  • 层次顺序

正确答案及解析

答案：B

题目 83

下面有关共享内存，说法不正确的是？

  • 共享内存和使用信号量一样，属于进程间通信的一种方式。

  • 使用shmget函数来创建共享内存

  • 尽管每个进程都有自己的内存地址，不同的进程可以同时将同一个内存页面映射到自己的地址空间中，从而达到共享内存的目的

  • 共享内存提供了同步机制，在第一个进程结束对共享内存的写操作之前，会有自动机制可以阻止第二个进程开始对它进行读取

正确答案及解析

答案：D

共享内存并没有提供同步机制。为了防止冲突，用信号量的方式来控制访问临界区的资源！

题目 84

有作业控制块JCB连成一串而形成的排队队列称为（）。

  • 挂起队列

  • 阻塞队列

  • 就绪队列

  • 后备队列

正确答案及解析

答案：D

三种调度模式：

  • 高级调度 （作业调度或长程调度JCB ）:后备队列

  • 中级调度 （中程调度 pcb）：就绪队列，阻塞队列，

  • 低级调度 （进程调度或短程调度 pcb）：挂起队列 or 就绪队列 or 阻塞队列

题目 85

  • tan(x)

  • sec^2(x)

  • -tan(x)

  • -sec^2(x)

正确答案及解析

答案：C

题目 86

如下代码输出结果是什么？

#include<stdio.h>
char *myString()
{
    char buffer[6] = {0};
    char *s = "Hello World!";
    for (int i = 0; i < sizeof(buffer) - 1; i++)
    {
        buffer[i] = *(s + i);
    }
    return buffer;
}
int main(int argc, char **argv)
{
    printf("%s\n", myString());
    return 0;
}

  • Hello

  • Hello World!

  • Well

  • 以上全部不正确

正确答案及解析

答案：D

函数 char *myString() 中没有使用new或者malloc分配内存，所有buffer数组的内存区域在栈区

随着 char *myString() 的结束，栈区内存释放，字符数组也就不存在了，所以会产生野指针，输出结果未知

题目 87

以下GPU缓冲区中哪个是深度缓冲区:()

  • frame buffer

  • z buffer

  • color buffer

  • stencil buffer

正确答案及解析

答案：B

题目 88

下列关于集中式总线解决方式的叙述中正确的是()

  • 集中式串行链接,查询所有部件都用一条"总线请求"线

  • 集中式定时查询,所有部件共用一条"总线忙"线

  • 集中式独立请求,查询所有部件都用一条"总线请求"线

  • 集中式定时查询,所有部件都用一条"总线请求"线

正确答案及解析

答案：ABD

集中式总线请求方案有三种，定时查询、串行连接和独立请求，定时查询和串行连接所有部件都用一条"总线请求"线，但是定时查询是由CPU去定时查询总线上的部件，而串行连接是部件去请求CPU。独立请求每个部件均有一条 "总线请求"线。

题目 89

二进制地址为011011110000，大小为（4）10和（16）10块的伙伴地址分别为： ? ， ? 。

正确答案及解析

答案：011011110100, 011011100000

均为十进制，大小分别为 4 和 16

题目 90

写出表达式 ((A+B)*C-(D-E)*(F+G)) 的前缀表达式 ? 。

正确答案及解析

答案：-*+ABC*-DE+FG

题目 91

任一查找树(二叉分类树)的平均查找时间都小于用顺序查找法查找同样结点的线性表的平均查找时间()

正确答案及解析

答案：错的

只有左子树或者右子树的BST就是一样的了

题目 92

在重载运算符函数时，下面（）运算符必须重载为类成员函数形式（）

  • +

  • -

  • ++

  • ->

正确答案及解析

答案：D

只能使用成员函数重载的运算符有：=、()、[]、->、new、delete。

题目 93

面向对象程序设计思想的主要特征不包括（）

  • 封装性

  • 多态性

  • 继承性

  • 模板

正确答案及解析

答案：D

面向对象程序语言的三大特征分别是：1.封装，2.继承，3.多态

题目 94

对任何数据结构链式存储结构一定优于顺序存储结构()

正确答案及解析

答案：错的

查找则用数组好，添加和删除则用链表。

题目 95

下列关于树的深度优先搜索算法描述错误的是？

  • 按照某种条件往前试探搜索，如果前进中遭到失败，则退回头另选通路继续搜索，直到找到条件的目标为止。

  • 先访问该节点所有的子节点，遍历完毕后选取它未访问过的子节点重复上述过程，直到找到条件的目标为止。

  • 假设数的顶点数为V，则算法的复杂度为O(V)

  • 深度优先算法非常适合使用递归来实现

正确答案及解析

答案：B

A选项讲的是深搜，B选项讲的是广搜啊

题目 96

下列各种操作的时间中，哪一个不属于活动头硬盘的存取访问时间？

  • 寻道时间

  • 旋转延迟时间

  • 定位时间

  • 传送时间

正确答案及解析

答案：C

硬盘的存取访问时间分为三个部分：

寻道时间Ts，旋转延迟时间Tr和传送时间Tt

题目 97

设有一个10阶的对称矩阵A,采用压缩存储方式,以行序为主存储,a11为第一元素,其存储地址为1,每个元素占一个地址空间,则a85的地址为()

  • 13

  • 33

  • 18

  • 40

正确答案及解析

答案：B

数组下标从1开始，只存储其下三角形元素，在a8,5的前面有7行，第1行有1个元素，第2行有2个元素，…，第7行有7个元素，这7行共有(1+7)×7／2=2 8个元素，在第8行中，a8,5的前面有4个元素，所以，a8，5前有28+4=32个元素，其地址为33。

题目 98

假设二叉排序树的定义是：1、若它的左子树不为空，则左子树所有节点均小于它的根节点的值；2、若右子树不为空，则右子树所有节点的值均大于根节点的值；3、它的左右子树也分别为二叉排序树。下列哪种遍历之后得到一个递增有序数列 （）

  • 前序遍历

  • 中序遍历

  • 后序遍历

  • 广度遍历

正确答案及解析

答案：B

题目 99

某指令流水线由 5 段组成，各段所需要的时间分别是：t、3t、t、2t 和 t 。问如果连续执行 10 条指令，则吞吐率是多少 ?

正确答案及解析

答案：0.2857/t

参考博客

自己画出指令执行的时空图，可以看出执行第n条指令的时间是：8t+(n-1)*3t

而吞吐率＝指令/时间＝10/(8t+9*3t)=10/35*t=0.2857t

题目 100

通过文件名存取文件时，文件系统内部的操作过程是通过？

  • 文件在目录中查找文件数据存取位置。

  • 文件名直接找到文件的数据，进行存取操作。

  • 文件名在目录中查找对应的i节点，通过i节点存取文件数据。

  • 文件名在目录中查找对应的超级块，在超级块查找对应i节点，通过i节点存取文件数据

正确答案及解析

答案：C

如果一个文件有多个数据块，这些数据块很可能不是连续存放的，应该如何寻址到每个块呢？实际上，根目录的数据块是通过其inode中的索引项Blocks[0]找到的，事实上，这样的索引项一共有15个，从Blocks[0]到Blocks[14]，每个索引项占4字节。前12个索引项都表示块编号，例如上面的例子中Blocks[0]字段保存着24，就表示第24个块是该文件的数据块，如果块大小是1KB，这样可以表示从0字节到12KB的文件。如果剩下的三个索引项Blocks[12]到Blocks[14]也是这么用的，就只能表示最大15KB的文件了，这是远远不够的，事实上，剩下的三个索引项都是间接索引。

题目 101

图中每个圆圈是一个补给站，存储着一定数量的汽油（在圈中标识），每个圈之间的路上标识了这段路需要消耗的汽油量，一辆小车从A点出发，在图上随意行走，到达某个补给站后，可以获得这个补给站的所有汽油，则其到B点后最多剩余的汽油量是____。

正确答案及解析

答案：10

总共是 7+1+3+1+0+5-7=10

可以使用A*算法获得

题目 102

给定如下C程序：

typedef struct node_s{
    int item;
    struct node_s* next;
}node_t;
node_t* reverse_list(node_t* head)
{
    node_t* n=head;
    head=NULL;
    while(n){
    _________               
    }
    return head;
 }

正确答案及解析

答案：node_t* m=n; n=n->next; m->next=head; head=m;

题目 103

若有定义int（*pt）[3]；则下列说法正确的是：

  • 定义了基类型为int的三个指针变量

  • 定义了基类型为int的具有三个元素的指针数组pt

  • 定义了一个名为*pt、具有三个元素的整型数组

  • 定义了一个名为pt的指针变量，它可以指向每行有三个整数元素的二维数组

正确答案及解析

答案：D

int (*pt)[3]，首先看括号内，*pt说明pt是一个指针，其指向的内容是int[3]，具有3个int元素的数组。

D选项说，可以指向每行有三个整数元素的二维数组，即int[][3]
int(*pt)[3] = NULL;
int arr[2][3] = {0};
pt = arr;

题目 104

实现虚拟存储的目的是（）。

  • 实现存储保护

  • 事项程序浮动

  • 扩充辅存容量

  • 扩充主存容量

正确答案及解析

答案：D

题目 105

下面程序应该输出多少？

char *c[] = { "ENTER", "NEW", "POINT", "FIRST" }; 
char **cp[] = { c+3, c+2, c+1, c }; 
char ***cpp = cp; 

int main(void)
{ 
    printf("%s", **++cpp); 
    printf("%s", *--*++cpp+3); 
    printf("%s", *cpp[-2]+3); 
    printf("%s\n", cpp[-1][-1]+1); 
    return 0;
}

正确答案及解析

答案：POINTERSTEW

**++cpp ：首先cpp 移动到cp+1的地方 然后取 两次* 相当于 **(cp+1) 结果就是POINT 移动cpp到cp+1的位置

*--*++cpp+3 ：首先cpp移动到cp+2的地方 然后取* 相当于 *--cp[2]+3 然后 --cp[2]的话相当于 --(c+1) 就等于c  就变成了 *c+3  输出ER    移动cpp到cp+2   cp[2]变成c

*cpp[-2]+3： 首先 cpp[-2] = *(cpp-2) [cpp=cp+2]   =  **cp+3 结果 ST 没有移动

cpp[-1][-1]+1： 首先cpp[-1]   -> *(cp+1) -> c+2  然后 (c+2)[-1] -> (c+2)[-1] -> *(c+2-1) -> c[1]      然后 c[1]+1    就变成了 EW

结果就是A

这个题目中 中间 cpp 变动两次，cp[2] 变动一次 特别注意  cp[2] 是数组 里面内容可以变动

题目 106

虚拟存储的容量受到下列哪一个因素的限制影响最大?

  • 磁盘空间大小

  • 物理内存大小

  • 数据存放的实际地址

  • 计算机地址位数

正确答案及解析

答案：B

本题问的是影响最大的因素，所以选内存大小。如果是有影响的因素，则有内存大小，外存大小，计算机寻址位数。

题目 107

Which of the following is(are) true about providing security to database servers ? Select all that apply

  • Do not host a database server on the same server as your web server

  • Do not host a database server on a server based system

  • Do not use blank password for SA account

  • Employ a centralized administration model

正确答案及解析

答案：ABCD

题目 108

Unix系统中，下列哪些可以用于进程间的通讯：（ ）

  • socket

  • 共享内存

  • 消息队列

  • 信号量

正确答案及解析

答案：ABCD

题目 109

以下数字在表示为double（8字节的双精度浮点数）时存在舍入误差的有（）。

  • 2的平方根

  • 10的30次方

  • 0.1

  • 0.5

  • 100

正确答案及解析

答案：ABC

A毫无疑问不用说

8字节的共64位，按照标准的浮点数表示方法，应该是1位符号位，11位指数位，52位尾数位
对于 B（2^90 < B < 2^100)来说，指数位是够了，但是尾数位会不会够呢？  B = 2^30*5^30 也就是说将B表示成二进制后，其后30位全为0，从其第一个不为0到最后一个不为0的二进制表示位中，至少需要90-30 = 60位来存储，而其尾数位只有52位，必然会产生舍入误差，所以B是的

对于C来说，将C表示成二进制便知 10[0.1] = 2[0.00011001100110011.......]，亦为无限循环小数，所以将0.1表示成二进制的double型必然也会产生舍入误差

题目 110

在mysql中，与语句SELECT * FROM book b WHERE b.book_num NOT BETWEEN 200 AND 300;等价的有

正确答案及解析

答案：SELECT * FROM book b WHERE b.book_num < 200 OR b.book_num > 300

注意BETWEEN AND的范围，上下都取等于。

题目 111

随着装填因子a的增大,用闭哈希法解决冲突,其平均搜索长度比用开哈希法解决冲突时的平均搜索长度增长得慢()

正确答案及解析

答案：错的

开哈希表-------链式地址法

闭哈希表-------开放地址法

装填因子增大，意味着哈希表的空间利用率在增大。

开哈希和闭哈希主要的区别在于，随着哈希表的密集度提高，使用闭哈希时，不仅会与相同哈希值的元素发生冲突，还容易与不同哈希值的元素发生冲突；而开哈希则不受哈希表疏密与否的影响，始终只会与相同哈希值的元素冲突而已。所以在密集度变大的哈希表中查找时，显然开哈希的平均搜索长度不会增长。

题目 112

进程从CPU退下时，将"现场"保存在系统栈内。

正确答案及解析

答案：错的

错，保存在任务栈中，系统栈要给下一个要运行的进程用

题目 113

采用深度优先搜索或拓扑排序算法可以判断出一个有向图中是否有环(回路)()

正确答案及解析

答案：对的

深度优先搜索只要在其中记录下搜索的节点数n，当n大于图中节点数时退出，并可以得出有回路

若有回路，则拓扑排序访问不到图中所有的节点，所以也可以得出回路

题目 114

对下列常见的各种网络术语，描述错误的是？

  • DNS（域名系统）是一种用于TCP/IP应用程序的分布式数据库，因此它在TCP/IP体系结构中处于应用层。

  • TFTP是一种文件传递应用程序，它使用的传输层协议是TCP

  • Telnet是标准的提供远程登录功能的应用，可以在不同OS系统的主机之间运行

  • Ping是对两个TCP/IP系统连通性进行测试的基本工具，它利用ICMP进行基本的请求和应答

正确答案及解析

答案：B

TFTP为简单文件传输协议，是基于UDP实现的，故传输层协议为UDP

题目 115

代码生成阶段的主要任务是（ ）

  • 把高级语言翻译成汇编语言

  • 把高级语言翻译成机器语言

  • 把中间代码变换成依赖具体机器的目标代码

  • 把汇编语言翻译成机器语言

正确答案及解析

答案：C

编译程序的工作过程一般划分为五个阶段：词法分析、语法分析、语义分析与中间代码产生、优化、目标代码生成。所以选C 。

题目 116

求下面函数的返回值。

int func(x)
 {
    int countx = 0;    
     while (x)
     {
      countx ++;
      x = x & (x - 1);
     }
     return countx;
 }

假定x = 9999。

正确答案及解析

答案：8

x=x&(x-1); & 是位运算符，需要将x转化成二进制计算，当&两边都为1时,为1，否则为0， 该题相当于求x的二进制式中含有1的个数，

x&(x-1) 求的是二进制中1的个数

x|(x+1) 求的是二进制中0的个数

题目 117

把校园中同一区域的两张不同比例尺的地图叠放在一起，并且使 其中较小尺寸的地图完全在较大尺寸的地图的覆盖之下。 每张地图上 都有经纬度坐标，显然，这两个坐标系并不相同。我们把恰好重叠在 一起的两个相同的坐标称之为重合点。 下面关于重合点的说法中正确 的是？

正确答案及解析

答案：必然有且只有一个重合点

假设地图有不止一个重合点，把任意两个重合点连成一条直线，则在大地图和小地图上的直线也是重合的，且长度相同。这导致两个地图的比例相等，与题设相矛盾。所以两个地图至多有一个重合点。

题目 118

通用多态是指

  • 强制多态和包含多态

  • 重载多态和强制多态

  • 参数多态和重载多态

  • 包含多态和参数多态

正确答案及解析

答案：D

//1.参数多态

//包括函数模板和类模板

//2.包含多态  virtual

class A{

    virtual void foo() {        printf("A virtual void foo()");        }

};

class B : public A {

    void foo() {        printf("B void foo()");        }

};

void test() {

    A *a = new B();

    a->foo(); // B void foo()

}

//3.重载多态

//重载多态是指函数名相同，但函数的参数个数或者类型不同的函数构成多态

void foo(int);

void foo(int, int);

//4.强制多态

//强制类型转换

题目 119

下面程序的输出结果是__________。

#include < iostream.h> 
#define SQR(A) A*A
void main() { 
    int x=6,y=3,z=2; 
    x/=SQR(y+z)/SQR(y+z); 
    cout< < x< < endl; 
}

正确答案及解析

答案：0

宏定义是一个很看重括号的东西
1.#define f(x) x*x   这里f(x+y) 就会被翻译成x+y*x+y 为什么，因为你没有添加括号啊宏定义只是简单的替换不会替你加括号
2.#define f(x) (x)*(x) 这里f(x+y) 就会翻译成（x+y）*（x+y） 就是这么回事
回到题上
上述式子等价为 x/=y+z*y+z/y+z*y+z，再加上/=优先级最低，所以x/=3+6+2/3+6+2 所以x=0

题目 120

程序动态链接的时刻是（）。

  • 编译时

  • 装入时

  • 调用时

  • 紧凑时

正确答案及解析

答案：B

B C都可以的 有装载时动态链接 也有运行时动态链接。。。

题目 121

一个具有8个顶点的连通无向图，最多有（）条边

正确答案及解析

答案：28

8个点中任选择两个， 都可以有一条边， 最多 8 * 7 / 2 = 28

题目 122

在分时操作系统中,进程调度经常采用( )算法

  • 先来先服务

  • 最高优先权

  • 时间片轮转

  • 随机

正确答案及解析

答案：C

时间片轮转。前提是进程资源是可抢占的。可是广泛采用的一种方式

其他选项说明：
先来先服务是最简单的进程调用方式，只需要维护一个队列即可。也可以说是最公平的调用方式。但是容易引起一个问题就是前面来的进程耗费较多的时间导致后面来的需要时间少的进程长时间得不到响应，会引起用户的不满

最高优先权。这个也容易引起低优先权的用户长时间得不到响应。想想军队里，战争的时候，越高级的长官越有必要占用较多的通信或者计算资源，也是合理的。

随机就不做评价了吧，跟抛硬币似的

题目 123

关于函数的描述正确的是___。

  • 虚函数是一个static型的函数

  • 派生类的虚函数与基类的虚函数具有不同的参数个数和类型

  • 虚函数是一个非成员函数

  • 基类中说明了虚函数后，派生类中起对应的函数可以不必说明为虚函数

正确答案及解析

答案：D

  • 在派生类中重新定义该虚函数时，关键字virtual可以写也可以不写。

  • 一个虚函数无论被公有继承多少次，它仍然保持其虚函数的特性。

  • 虚函数必须是其所在类的成员函数，而不能是友元函数，也不能是静态成员函数（static）

题目 124

以下代码输出什么?

int a =1,b =32 ;
printf("%d,%d",a<<b,1<<32);

正确答案及解析

答案：1,1

执行a<<b时，编译器会先将b与31进行and操作，以限制左移的次数小于等于31。b&31=0，则a<<b=1

执行1<<32时，编译器直接执行算术左移的操作。
 来自 http://blog.csdn.net/hgl868/article/details/7058909

题目 125

下面数据结构能够支持随机的插入和删除操作、并具有较好的性能的是____。

  • 数组和链表

  • 链表和哈希表

  • 哈希表和队列

  • 队列和堆栈

  • 堆栈和双向队列

  • 双向队列和数组

正确答案及解析

答案：B

数组和队列不方便插入和删除，因为队列在中间不好插入和删除，队列只在端点插入和删除，所以队列要插入和删除要移位许多

题目 126

设一个系统中有5个进程，它们的到达时间和服务时间如下，A的到达时间为0，服务时间为3；B的到达时间为2，服务时间为6；C的到达时间为4，服务时间为4；D的到达时间为6，服务时间为5；E的 到达时间为8，服务时间为2，忽略1/0以及其他开销时间，若分别按先来先服务（fFCFS）进行CPU调度，其平均周转时间为？

正确答案及解析

答案：8.6

先来先服务调度算法
进程名  到达时间    服务时间    开始执行时间    完成时间    周转时间
 A  0   3   0   3   3
 B  2   6   3   9   7
 C  4   4   9   13  9
 D  6   5   13  18  12
 E  8   2   18  20  12
周转时间 = 完成时间 - 到达时间
平均周转时间 = 所有进程周转时间 / 进程数 = （3+7+9+12+12）/ 5 = 8.6

题目 127

10.1.0.1/17的广播地址是（ ）

正确答案及解析

答案：10.1.127.255

题目 128

以下有关Http协议的描述中，正确的有？

  • post请求一般用于修改服务器上的资源，对发送的消息数据量没有限制，通过表单方式提交

  • HTTP返回码302表示永久重定向，需要重新URI

  • 可以通过206返回码实现断点续传

  • HTTP1.1实现了持久连接和管线化操作以及主动通知功能，相比http1.0有大福性能提升

正确答案及解析

答案：ACD

  • HTTP /302 redirect: 302 代表暂时性转移(Temporarily Moved )。

  • HTTP/206 “Partial Content”响应是在客户端表明自己只需要目标URL上的部分资源的时候返回的.这种情况经常发生在客户端继续请求一个未完成的下载的时候(通常是当客户端加载一个体积较大的嵌入文件,比如视屏或PDF文件 ),或者是客户端尝试实现带宽遏流的时候.

题目 129

如果系统现在需要在一个很大的表上创建一个索引，你会考虑那些因素，如何做以尽量减小对应用的影响?

  • 增大sort_area_size（8i）/pga_aggregate_target（Arrayi）值

  • 如果表有分区（一般大表都要用到分区的），按分区逐个建索引，如果是本地索引的话

  • 系统空闲的时候建。

  • 把日志文件放到另一个地方

正确答案及解析

答案：ABC

不选D，改日志位置需要down机，应用在这个时间用不了

题目 130

堆肯定是一棵平衡二叉树()

正确答案及解析

答案：错的

堆是二叉树，但不保证是平衡二叉树，因为堆中左右子树的高度差并不保证小于等于1。

题目 131

堆是满二叉树()

正确答案及解析

答案：错的

堆是完全二叉树，但不是满二叉树。

题目 132

在用堆排序算法排序时,如果要进行增序排序,则需要采用"大根堆"()

正确答案及解析

答案：对的

因为大根堆每次生成的根都会跟最右侧没有排序的叶子节点进行交换，从而使得越大的元素越放在后面。这个特性使用数组的结构能够很清晰的表现出来。最终得到了升序排列。

如果是小根堆，则每次拿到最小的跟最右侧未排过序的叶子节点进行交换，最终得到的序列是递减的。

题目 133

(101,88,46,70,34,39,45,58,66,10)是堆()

正确答案及解析

答案：对的

最小堆：直接父节点比两个子节点都小。

最大堆：直接父节点比两个子节点都大。

解析得到这是大堆，故是对的

题目 134

有 1000 个无序的整数，希望使用最快的方式找出前 50 个最大的，最佳的选择是（ ）

  • 冒泡排序

  • 基数排序

  • 堆排序

  • 快速排序

正确答案及解析

答案：C

1、快速排序：在最理想的情况下，即划分可以使得每次分到n/2 的两个序列，复杂度为o（nlogn）。
2、堆排序：无论什么情况都是o（nlogn），当然还有建堆的时间o（n），所以为n+nlogn，但是，本题只是要前五十个，所以堆排序只需要执行50次就够了：n+50logn。
3、本题的条件是1000个无序整数，1000+50log1000<1000log1000，所以自然是堆排序最好。
p.s.：堆排序只需要一个n大小的二叉树就行了，快速排序除了n大小的数组，每次递归最少还得有logn的栈，所以堆排序的空间复杂度也优于快速排序。

题目 135

在堆排序算法中我们用一个数组A来模拟二叉树T，如果该A[0]存放的是T的根节点，那么A[K](K>0)的父亲节点是

  • (K-1)/2

  • K/2

  • (K+1)/2

  • 都不对

正确答案及解析

答案：A

当数组从0开始时，下标为k的结点的父结点下标为(k-1)/2；

当数组从1开始时，下标为k的结点的父结点下标为k/2；

题目 136

以下序列不是堆的是()

  • (100,85,98,77,80,60,82,40,20,10,66)

  • (100,98,85,82,80,77,66,60,40,20,10)

  • (10,20,40,60,66,77,80,82,85,98,100)

  • (100,85,40,77,80,60,66,98,82,10,20)

正确答案及解析

答案：D

最大（小）堆，所有节点都大（小）于其孩子节点，i 位置节点的孩子节点为 2i 和 2i+1 ，i 节点的父节点为 i/2 注意 i 是从1开始的。

题目 137

【0、2、1、4、3、9、5、8、6、7】是以数组形式存储的最小堆，删除堆顶元素0后的结果是（）

  • 【2、1、4、3、9、5、8、6、7】

  • 【1、2、5、4、3、9、8、6、7】

  • 【2、3、1、4、7、9、5、8、6】

  • 【1、2、5、4、3、9、7、8、6】

正确答案及解析

答案：D

题目 138

就分类算法所用的辅助空间而言,堆分类、快速分类和归并分类的关系是()

正确答案及解析

答案：堆分类<快速分类<归并分类

堆分类 O(1) 用于交换的时候临时变量

快速分类 O(logn) 递归保存现场

归并分类 O(n) 用元素个数同长度空间保存归并结果

题目 139

下述二叉树中,哪一种满足性质:从任一结点出发到根的路径上所经过的结点序列按其关键字有序()

  • 二叉排序树

  • 哈夫曼树

  • AVL树

  • 堆

正确答案及解析

答案：D

一：二叉排序树的左子树节点值都小于根节点值，右子树节点值都大于根节点，因此假如根节点值为10，其左节点值为5，其左节点的右节点值为8，那么从右节点到跟节点的值依次为8  5  10，显然不是有序的
二：哈夫曼树是带权路径最小的二叉树，也不是
三：AVL树是二叉平衡树，只不过其左右子树的高度差有限制，在1之内，由一只非有序
四：堆是一种完全二叉树，其有大顶堆和小顶堆的分别，大顶堆是指其每个节点的值都大于其左右孩子的值（小顶堆反之），因此从任一节点到根节点是升序排列的（小顶堆反之）

题目 140

最坏情况下 insert sort, quick sort ,merge sort 的复杂度分别是多少？

  • O(n*n),O(nlogn),O(n*n)

  • O(n*n),O(n*n),O(nlogn)

  • O(n*n),O(nlogn),O(nlogn)

  • O(nlogn),O(nlogn),O(nlogn)

正确答案及解析

答案：B

1：简单选择  最好时间 O(n^2)      平均时间O(n^2)      最坏时间 O(n^2)
2：直接插入  最好时间 O(n)         平均时间O(n^2)      最坏时间 O(n^2)
3：冒泡排序  最好时间 O(n)         平均时间O(n^2)      最坏时间 O(n^2)
4：希尔排序  最好时间 O(n)         平均时间O(logn)     最坏时间 O(n^s) 1<s<2
5：快速排序  最好时间 O(nlogn)  平均时间O(nlogn)   最坏时间O(n^2) 
6：堆排序      最好时间 O(nlogn)  平均时间O(nlogn)   最坏时间O(nlogn) 
7：归并排序  最好时间 O(nlogn)  平均时间O(nlogn)   最坏时间O(nlogn)

题目 141

有一组数据(15,9,7,8,20,-1,7,4),用堆排序的筛选方法建立的初始堆为()

  • -1,4,8,9,20,7,15,7

  • -1,7,15,7,4,8,20,9

  • -1,4,7,8,20,15,7,9

  • ABC均不对

正确答案及解析

答案：C

题目 142

关于序列16 14 10 8 7 9 3 2 4 1的说法下面哪一个正确（）

  • 大顶堆

  • 小顶堆

  • 不是堆

  • 二叉排序树

正确答案及解析

答案：A

大顶堆，在n位置上的数要比在2n+1和2n+2位置上的数大(n 从 0 开始)

题目 143

下面有关c++静态数据成员，说法正确的是？

  • 不能在类内初始化

  • 不能被类的对象调用

  • 不能受private修饰符的作用

  • 可以直接用类名调用

正确答案及解析

答案：D

通常静态数据成员在类声明中声明,在包含类方法的文件中初始化.

初始化时使用作用域操作符来指出静态成员所属的类.

但如果静态成员是整型或是枚举型const,则可以在类声明中初始化!!

如果改成有的静态数据成员是可以直接在类中初始化就对了

题目 144

对n个记录的文件进行堆排序,最坏情况下的执行时间是多少?()

  • O(log2n)

  • O(n)

  • O(nlog2n)

  • O(n*n)

正确答案及解析

答案：C

时间复杂度分析，第一步首先建堆需要用时o(n)，第二步对大小为n的堆，取出元素放入数组尾部用时o(1)，重新进行保持堆特性为o(lgn)，因此o(n)+o(nlgn)，总体时间时间复杂度为o(nlgn)

题目 145

下标从1开始,在含有n个关键字的小根堆(堆顶元素最小)中,关键字最大的记录有可能存储在()位置上

  • [n/2]

  • [n/2]-1

  • 1

  • [n/2]+2

正确答案及解析

答案：D

小根堆中最大的数一定是放在叶子节点上，堆本身是个完全二叉树，完全二叉树的叶子节点的位置大于[n/2]

题目 146

下列哪一个关键码序列不符合堆的定义？

  • A、C、D、G、H、M、P、Q、R、X

  • A、C、M、D、H、P、X 、G、0、R

  • A、D、P、R、C、Q、X 、M、H、G

  • A、D、C、M、P、G、H、X 、R、Q

正确答案及解析

答案：C

C选项中关键码序列用完全二叉树表示后很容易看出，结点值d大于了左子结点值c

题目 147

下列关于堆和栈的区别描述错误的有？

  • 申请方式的不同，堆是系统自动分配，栈是自己申请

  • 栈的大小是固定的，堆的大小受限于系统中有效的虚拟内存

  • 栈的空间由系统决定何时释放，堆需要自己决定何时去释放

  • 堆的使用容易产生碎片，但是用起来最方便

正确答案及解析

答案：A

  1. 栈内存操作系统来分配，堆内存由程序员自己来分配。

  2. 栈有系统自动分配，只要栈 剩余空间大于所申请空间，系统将为程序提供内存，否则将报异常提示栈溢出。

题目 148

已知关键字序列5,8,12,19,28,20,15,22是最小堆，插入关键字3，调整后得到的最小堆是()

  • 3,8,12,5,20,15,22,28,19

  • 3,5,12,19,20,15,22,8,28

  • 3,12,5,8,28,20,15,22,19

  • 3,5,12,8,28,20,15,22,19

正确答案及解析

答案：D

题目 149

初始序列为1 8 6 2 5 4 7 3一组数采用堆排序，当建堆（小根堆）完毕时，堆所对应的二叉树中序遍历序列为：（）

  • 8 3 2 5 1 6 4 7

  • 3 2 8 5 1 4 6 7

  • 3 8 2 5 1 6 7 4

  • 8 2 3 5 1 4 7 6

正确答案及解析

答案：A

最小堆：先以数组顺序构建一棵完全二叉树，再从第n/2 +1个元素开始构建最小堆，再进行中序遍历。

首先从最后一个非端子结点开始(即2) 因为是建小根堆

所以交换子节点中小于自己的最小那个 3比2大——不换 看6 与4换

接着8与2换且与3换 最后1不换 就形成了最终结果 然后再中序遍历之

Previous前 75 题NextPython 语言特性

Last updated