牛客网选择题100题

1 最坏情况下,合并两个大小为n的已排序数组所需要的比较次数为2n-1。

2 声明一个指向含有10个元素的数组的指针,其中每个元素是一个函数指针,该函数的返回值是int,参数是int*,正确的是() int ((int *)[10])*p

3 任何一个非空广义表其表头可能是原子,也可能是列表,而其表尾必定是列表。

4 若广义表LS(n>=1)非空,则a1是LS的表头,其余元素组成的表(a2,…an)称为LS的表尾。

5 从两个方向搜索双链表,比从一个方向搜索双链表的方差要小

6 STL容器是线程不安全的。当容量不够时,vector内部内存扩展方式是翻倍。std::stack默认是用deque实现的

7 一台刚刚接入互联网的WEB服务器第一次被访问到时,不同协议的发生顺序是ARP -> DNS -> HTTP。

8 输出结果

int main(void)
{
    const int a = 10;
    int * p = (int *)(&a);
    *p = 20;
    cout<<"a = "<<a<<", *p = "<<*p<<endl;
    return 0;
}

答案:a = 10, *p = 20

9 用十进制计算30!(30的阶乘),将结果转换成3进制进行表示的话,该进制下的结果末尾会有__个0。
答案:N/3+N/9+N/27=14

10 二查搜索树中序遍历一定是有序的

11 作为特使,你需要组织A/B两国元首相约在杭州萧山机场交换一份重要文件(假设交换文件不需要时间)。约定两国飞机在晚上的20点至24点这4个小时会面,A国的飞机如果到了,会等待1个小时,B国的飞机如果到了,会等待2个小时,如果假设两架飞机在这段时间内降落机场的概率是均匀分布的,那么能顺利完成交换的概率是__
解析:
设x为a到达的时间 y为b到达的时间

20<x<24
20<y<24
0<x-y<1
0<y-x<2

ok花图像求出面积比

12 小赵和小钱二人分别从寝室和图书馆同时出发,相向而行。过了一段时间后二人在中途相遇,小赵继续向图书馆前进,此时:若小钱继续向寝室前进,则当小赵到达图书馆时,小钱离寝室还有600米;若小钱立即折返向图书馆前进,则当小赵到达图书馆是,小钱离图书馆还有150米。那么图书馆与寝室间的距离是__
解析:

设小赵,小钱速度分别位v1,v2,相遇前后时间为t1,t2。则可以得到:
( v1-v2 )(t 1+ t 2) = 600
( v 1 -v 2 )t2 = 150
v 2 t 1 = v 1 t 2
解得v 1: v 2 = 3:1,t 1: t 2 = 3:1, 则总距离s = v 1( t 1+ t 2 ) = 900

13 一张1024×640分辨率的图片,假定每个像素用16位色彩表示,用位图文件(bitmap)格式存储,则这张图片文件需要占用多大的存储空间__
答案:
1024*640*16 bit = 1024*640*16/8 B = 1024*640*16/8/1024 KB = 1280KB

14 char *p[10] 是指针数组,数组里存放了10个指针,在64位系统下指针占8个字节,所以sizeof(p) = 10 * 8 = 80.
char (*p1)[10]是数组指针,p1是一个指向存放10个char类型的数组的指针,所以sizeof(p1) = 8.

15 求最小生成树的Prim和Kruskal都是漂亮的贪心算法。

16 设有一个n行n列的对称矩阵A,将其下三角部分按行存放在一个一维数组B中,A[0][0]存放于B[0]中,那么第i行的对角元素A[i][i]存放于B中()处
答案:A[i][i]是第i+1行第i+1列元素,是第1+2+...+(i+1)=[(i+1)*(i+2)/2]个元素,又因为起始坐标是0。所以存放在[(i+1)*(i+2)/2]-1=[ (i+3)*i/2 ]

17 int A[2][3]={1,2,3,4,5,6};,则A[1][0]*(*(A+1)+1)的值分别是()
答案:4 5

18 一个有序数列,序列中的每一个值都能够被2或者3或者5所整除,这个序列的初始值从1开始,但是1并不在这个数列中。求第1500个值是多少?
解析:
2、3、5的最小公倍数是30。[ 1, 30]内符合条件的数有22个。如果能看出[ 31, 60]内也有22个符合条件的数,那问题就容易解决了。也就是说,这些数具有周期性,且周期为30.
第1500个数是:1500/22=68 1500%68=4。也就是说:第1500个数相当于经过了68个周期,然后再取下一个周期内的第4个数。一个周期内的前4个数:2,3,4,5。
故,结果为68*30=2040+5=2045

19 一个5*4的矩阵,有多少个长方形?
解析:5的排列 乘以 4的排列 (5+4+3+2+1)×(4+3+2+1)=15×10=150个矩形

21 Which statement is true for the class java.util.ArrayList?
The elements in the collection are ordered.

22 并不是所有的操作符都能被重载。除了 . , .* , :: , ? : , sizeof , typeid 这几个运算符不能被重载,其他运算符都能被重载。

23 下列的模板说明中,正确的有( )

template <typename T1, typename T2>
template <class T1, class T2>

24 In C++, which of the following keyword(s) can be used on both a variable and a function?
答案:static, extern, const

25 Which of the following statement(s) equal(s) value 1 in C programming language?
答案:

return (7&1)
char *str="microsoft"; return str=="microsoft"
return "microsoft"=="microsoft"

26 IPv4
在IP地址3种主要类型里,各保留了3个区域作为私有地址,其地址范围如下:

A类地址:10.0.0.0~10.255.255.255
B类地址:172.16.0.0~172.31.255.255
C类地址:192.168.0.0~192.168.255.255

27 二分查找算法
只能用于数组;只能在已经排序的数组上进行查找;最坏情况下时间复杂度是 O(logN).

28 命令

ping命令通过发送ICMP数据包检测网络层是否连通
tracert是用来跟踪路由的命令
telnet命令式通过telnet协议和另一主机相联。
ipconfig是查看ip地址信息

29 路由器转发数据包到非直接网段的过程中,依靠下列哪一个选项来寻找下一跳地址( )
答案:IP报文头部
路由器工作在OSI的网络层,转发的数据包是IP报文。
IP报文的头部有源IP和目的IP
路由器根据目的ip计算出iP所在的网段,根据网段转发到不同的端口。
如果在路由表中没有该网段的转发端口,则转发至默认路由端口

30 调用动态连接库的函数有哪几种方法?
调用一个DLL中的函数有两种方法:

  1. 载入时动态链接(load-time dynamic linking),模块非常明确调用某个导出函数,使得他们就像本地函数一样。这需要链接时链接那些函数所在DLL的导入库,导入库向系统提供了载入DLL时所需的信息及DLL函数定位。
  2. 运行时动态链接(run-time dynamic linking),运行时可以通过LoadLibrary或LoadLibraryEx函数载入DLL。DLL载入后,模块可以通过调用GetProcAddress获取DLL函数的出口地址,然后就可以通过返回的函数指针调用DLL函数了。如此即可避免导入库文件了。

一般有两种调用方式:
1、静态调用。将编译之后的dll和所对应的lib文件放到要调用它们的工程所在路径,然后添加如下代码:
#pragma comment(lib,"dege.lib")
extern "C" __declspec(dllimport) FuncA(//参数);
然后可以直接使用FuncA函数了,跟普通函数一样。这个其实是一个静态库,因为你很可能没有lib文件,所以建议使用第二种方式:
2、动态调用。

typedef int(*lpFunA)(int, int); //宏定义函数指针类型,这里假设你的FuncA是一个int型的函数,且带两个int型的参数,你可以假设为是一个求和的Add函数。
在要使用FunA的地方添加如下代码
HINSTANCE hDll;//定义个DLL句柄
lpFunA addFun;//自定义函数的指针
hDll=LoadLibrary("..\\Debug\\dege.dll");//动态加载dll,这里假设你的dll放在你要调用它的工程的debug下
if(hDll!=NULL)
{
    addFun=(lpFunA)GetProAddress(hDll,"FunA");//获得FunA的地址
if(FunA!=NULL)
{
    //这里正常使用addFun,跟普通函数一样
}
FreeLibrary(hDll);//用完之后要释放句柄
}

31 WM_QUIT消息的用途是什么?一个普通的Windows窗口能收到的最后一条消息是什么?
WM_QUIT通知程序退出,一般情况下在主线程中会有一个循环如下:

while(GetMessage(......))
{
    TranslateMessage(&msg);
    DispatchMessage(&msg);
}

如果GetMessage获得的是WM_QUIT消息,GetMessage便会返回FALSE,导致while循环退出,一般情况下,程序也会退出。windows窗口不会受到WM_QUIT消息。

普通Windows窗口能收到的最后一条消息时WM_DESTROY。

32 ArrayLists和LinkedList的区别

ArrayList是实现了基于动态数组的数据结构,LinkedList基于链表的数据结构。
对于随机访问get和set,ArrayList觉得优于LinkedList,因为LinkedList要移动指针。
对于新增和删除操作add和remove,LinedList比较占优势,因为ArrayList要移动数据。
ArrayList的空间浪费主要体现在在list列表的结尾预留一定的容量空间,而LinkedList的空间花费则体现在它的每一个元素都需要消耗相当的空间。

32 若串S=’software’,其子串数目为(包括空串):
长度为1的,8个;长度为2的,7个;长度为3的,6个;长度为4的,5个;…
…于是 总共是1+2+..+8=36,再加上空字符串,37。

33 串是一种特殊的线性表,其特殊性体现在()
数据元素是一个字符

34 若初始序列为gbfcdae,那么只会少需要[5]次两两交换,才能使该序列变为abcdefg。任给一个*a–g这7个字母组成的排列,最坏的情况下需要至少[6]次两两交换,才能使序列变为abcdefg。

35 下列哪两个数据结构,同时具有较高的查找和删除性能?()
AVL树、Hash表

36 下述哪一条是顺序存储结构的优点?()
存储密度大

37 广义表()和(())不同。前者是长度为0的空表,对其不能做求表头和表尾的运算;而后者是长度为l的非空表(只不过该表中惟一的一个元素是空表),对其可进行分解,得到的表头和表尾均是空表()

38 集合与线性表的区别是是否允许元素重复

39 下列哪个算法是对一个list排序的最快方法()
二分插入排序

40 基于比较的排序的时间复杂度下限是多少?
O(nlogn)

41 假设网络带宽是128MB/s,网络单向延时为100ms, 1000个客户端(单线程)同时向服务器传输64KB大小的文件,每个请求大小为64KB,服务器磁盘并发写入速度30MB/s,在传输过程中,服务器吞吐量为30MB/S ,单个请求响应时间为 700 ms

42 如果信号量的当前值为-4,则表示系统中在该信号量上有(4)个进程等待。

43 早期的OS主要追求的是(系统的效率)

44 存储管理方法中,(段页式存储管理)用户可采用覆盖技术。

45 下列的进程状态变化中,哪些是不可能发生的?
等待→运行

46 在存储管理中,采用覆盖与交换技术的目的是(减少程序占用的主存空间)。

47 如何减少换页错误?
访问局部性(locality of reference)满足进程要求

48 ()就是能从这许多查询策略中找出最有效的查询执行计划的一种处理过程。
查询优化

49 应尽量避免在 where 子句中使用 or 来连接条件,否则将导致引擎放弃使用索引而进行全表扫描

50 Linux 有三个查看文件的命令,若希望在查看文件内容过程中可以用光标上下移动来查看文件内容,应使用命令。
less

51 下列文件中,包含了主机名到IP地址的映射关系的文件是: /etc/hosts。

52 下述是Linux下多线程编程常用的pthread库提供的函数名和意义,说法正确的有?

pthread_create 创建一个线程
pthread_join用来等待一个线程的结束
pthread_mutex_init 初始化一个线程互斥锁
pthread_exit结束一个线程

53 下列关于makefile描述正确的有?

makefile文件保存了编译器和连接器的参数选项
主要包含了五个东西:显式规则、隐晦规则、变量定义、文件指示和注释
默认的情况下,make命令会在当前目录下按顺序找寻文件名为“GNUmakefile”、“makefile”、“Makefile”的文件, 找到了解释这个文件

54 从n个数里面找最大的两个数理论最少需要比较()
n+ logn -2

55 对n个记录的线性表进行快速排序为减少算法的递归深度,以下叙述正确的是()
每次分区后,先处理较短的部分

56 堆排序的时间复杂度是(),堆排序中建堆过程的时间复杂度是()。
O(n log n),(n)

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

58 既希望较快的查找又便于线性表动态变化的查找方法是()
索引顺序查找

59 Which statement declares a variable a which is suitable for referring to an array of 50 string objects?

String a[];
String[]a;
Object a[];

在java 中,声明一个数组时,不能直接限定数组长度,只有在创建实例化对象时,才能对给定数组长度.。

60 在一个容量为25的循环队列中,若头指针front=18,尾指针rear=9,则该循环队列*有 16 个元素。

61 现有一完全的P2P共享协议,每次两个节点通讯后都能获取对方已经获取的全部信息,现在使得系统中每个节点都知道所有节点的文件信息,共17个节点,假设只能通过多次两个对等节点之间通讯的方式,则最少需要(30)次通讯
2n - 4

62 线程安全的map在JDK 1.5及其更高版本环境 有哪几种方法可以实现?

Map map = new ConcurrentHashMap();
Map map = Collections.synchronizedMap(new HashMap());

63 基于哈希的索引和基于树的索引有什么区别?

hash索引仅满足“=”、“IN”和“<=>”查询,不能使用范围查询
hash索引无法被用来进行数据的排序操作
对于组合索引,Hash 索引在计算 Hash 值的时候是组合索引键合并后再一起计算 Hash 值,而不是单独计算 Hash 值,所以通过组合索引的前面一个或几个索引键进行查询的时候,Hash 索引也无法被利用
Hash 索引遇到大量Hash值相等的情况后性能并不一定就会比B-Tree索引高

64 有一个数组(53,83,18,59,38,35),依次将其存储在hash表中,其中哈希函数为h(k)=k%7,如采用线性探测(每次向后查找1位)的方式解决冲突,则该hash表上查找38,35,53访问hash表的表项次数分别为5 , 2 , 1 。

65 散列函数有一个共同性质,即函数值应按()取其值域的每一个值。
同等概率

66 设有n个关键字具有相同的Hash函数值,则用线性探测法把这n个关键字映射到Hash表中需要做几次线性探测?
n*(n-1)/2

67 假设把整数关键字K Hash到有N个槽的散列表,以下哪些散列函数比较合适()
H(k)=(k+Random(N))mod N,其中Random(N)返回0到N-1的整数

68 拉链法处理冲突简单,且无堆积现象,即非同义词决不会发生冲突,因此平均查找长度较短

69 下列哪两个数据结构,同时具有较高的查找和删除性能?()
AVL树
Hash表

70 采用开址定址法解决冲突的哈希查找中,发生集聚的原因主要是()
解决冲突的算法选择不好

71 任何二叉树中度为0的结点比度为2的结点多一个

72 求解最短路径的Floyd算法的时间复杂度为()
O(n*n*n)

73 所有的AOV网都有一个拓扑序列

74 设T是由n个结点构成的二叉树,其中,叶子结点个数为n0,次数为2的结点个数为n2,则有:
n0=n2+1

75 下面哪个是无线网络协议(C)
A、ADSL B、100BaseT C、WiMax D、1000BaseT

76 Android的IPC(进程通讯)主要采用以下哪个?(C)
A、Socket B、Pipe C、Binder D、Signal

77 在函数F中,本地变量a和b的构造函数(constructor)和析构函数(destructor)的调用顺序是:

Class A;
Class B;
voidF() {
        A a;
        B b;
}

答案:a构造 b构造 b析构 a析构

78 在C++, 下列哪一个可以做为对象继承之间的转换
dynamic_cast

79 是用辗转相除法来计算两个非负数之间的最大公约数:

long long gcd(long long x, long long y) {
    if (y == 0)
        return x;
    else
        return gcd(y, x % y);
}

我们假设x,y中最大的那个数的长度为n,x>y,基本运算时间复杂度为O(1),那么该程序的时间复杂度为( )
O(logy)

80 一棵有124个叶节点的完全二叉树,最多有( 248)个节点。
n0 = n2 + 1,于是度为2的结点个数123个
完全二叉树中度为1结点个数最多1个
因此该完全二叉树中结点最多有123 + 1 + 124 = 248个

81 在CPU和内存之间增加cache的作用是( )
解决内存速度低于CPU的性能问题

82 假设整数0x12345678 存放在内存地址0x0开始的连续四个字节中 (即地址0x0到 0x3). 那么在以Little Endian字节序存储的memory中,地址0x3的地方存放的字节是:
0x12

83 代码生成阶段的主要任务是( )
把中间代码变换成依赖具体机器的目标代码

84 词法分析器用于识别( )
单词

85 操作系统采用分页式存储管理(PAGING)方法,要求( )
每个进程拥有一张页表,但只要执行进程的页表驻留在内存中,其他进程的页表不必驻留在内存中

86 linux中调用write发送网络数据返回n(n>0)表示( )
本地已发送n个字节

87 HTTP 应答中的 500 错误是:

403:禁止访问;
404:找不到该页面;
503:服务器繁忙;
500:内部服务器访问出错。

88 RED HAT LINUX 9.0的安装方式有哪些?
从软件安装来源可以分为:光盘、硬盘、nfs服务器、ftp服务器、http服务器

89 下列哪个算法是对一个list排序的最快方法()
快速排序——不需要随机访问

90 应用程序PING发出的是什么报文()
ICMP请求报文

91 语法分析器可以用于()
识别语法错误

92 如果在一个建立了TCP连接的socket上调用recv函数,返回值为0,则表示()
对端关闭了连接

93 下述哪种情况会提出中断请求()
在键盘输入过程中,每按一次键

94 X86体系结构在保护模式下中有三种地址,请问一下那种说法是正确的?
虚拟地址先经过分段机制映射到线性地址,然后线性地址通过分页机制映射到物理地址

95 将一颗有100个结点的完全二叉树从根这一层开始,进行广度遍历编号,那么编号最小的叶节点的编号是(51)
解析:100/2+1=51

96 快排在完全无序的情况下效果最好,时间复杂度为O(nlogn),在有序情况下效果最差,时间复杂度为O(n^2)

97 假设把整数关键码K散列到有N个槽的散列表,以下那些散列函数是好的散列函数?
h(k)=k mod N

98 采用开址定址法解决冲突的哈希查找中,发生集聚的原因主要是()
解决冲突的算法选择不好

99 栈是从高地址向低地址增长的。

100 进程阻塞的原因不包括__时间片切换__。
包括的有等待I/O,进程sleep,等待解锁

上一篇:互联网、电商及游戏行业实时BI分析


下一篇:PLSQL_案例优化系列_体会函数及位图索引与SQL优化(案例7)