【牛客】错题集
牛客错题集
1. 执行"int x=1;int y=~x;"语句后,y的值为？
运算对象为数字的补码，而不是二进制码。当补码的符号位为1时，说明该补码对应的是负数，所以根据补码求原码的时候遵循负数的原则，补码取反加一。如果符号位为0时，则该补码对应的原码与其相同。
-3：
10000011（原码）
11111100（反码）
11111101（补码）（这是-3在计算机中的表示形式）
~（-3）：
00000010（补码）（~（-3）在计算机中的表示形式）
所以~（-3）=4
1：
00000001（原码，反码，补码）
~1：
11111110（补码）（~1在计算机中的表示形式）
10000010（原码）
~1=-2
2.#include命令的功能是 （在命令处插入一个文本文件）。
预处理器发现#include后，就会寻找指令后面<>中的文件名，并把这个文件的内容包含到当前的文件中，
被包含的文件中的文本将替换源代码文件中的#include指令。
3.
在官方文档里，对于 fseek 的描述是
Move to specified position in file，移到文件的某一个特殊位置
status = fseek
(fileID, offset, origin)
fileID的意思是fopen打开时产生的整数标识，代表文件指针，大于0时，表示文件成功打开。
在文件中，offset是，相对于起始origin的位置开始移动的整数
origin有三种状态，bof，cof，eof，其分别表示文件的开始位置，当前位置，和末尾位置。
如果操作成功，则状态返回0，否则返回为-1.
4.
5.
C的运算符有以下几类：
1.算术运算符：* - + /
2.关系运算符： > < == != >= <=
3.逻辑运算符：! && ||
4.位运算符：<< >> ~ | ^ &
5.赋值运算符：=及扩展赋值运算符
6.条件运算符：?:
7.逗号运算符：,
8.指针运算符：*和&
9.求字节数运算符：sizeof
10.强制类型转换运算符：(类型)
11.分量运算符：. ->
12.下标运算符：[ ]
13.其他：如函数调用运算符:()
注意：条件运算符是C语言中惟一一个三目(三元)运算符
6.在下列排序算法中，哪几个算法的时间复杂度与初始排序无关()
直接插入排序：
算法思想：将第i个记录插入到前面已经排好序的i - 1个记录中去。
算法要点：使用监视哨r[0]临时保存带插入记录
从后往前查找应插入的位置
查找与移动用同一循环完成
算法时间复杂度：o(n^2)折半插入排序：
算法思想：利用折半查找的思想找到需要插入的位置
算法时间复杂度：o(n^2)，虽然减少了查找插入位置的次数，但是移动元素的时间仍未改变希尔排序：
算法思想：将待排序的关键字序列分成若干个较小的子序列，对子序列进行直接插入排序，使整个待排序序列排好序。
算法时间复杂度：o(n^1.5)快速排序：
算法思想：从待排序记录中选择一个记录为枢纽，设为K，将其余大于K的记录移动至K的后面，小于K的移动至前面，此过程称为一趟快速排序。当然就是对接下来的两个字表进行相同的操作，直到子表的长度不超过1
算法时间复杂度：o(Knlog2n),K为常数因子，且在所有O(nlogn)复杂度中,快排的K值最小简单选择排序：
算法思想：
第一趟：从第一个记录开始，通过n-1次关键字比较，从n个记录中选出最小的并和第一个记录交换；
第二趟：从第二个记录开始，通过n-2次关键字比较，从n -1个记录中选出最小的并和第二个记录交换；
...
算法时间复杂度：o(n^2)堆排序：
算法思想：将向量中存储的数据看成一棵完全二叉树，利用完全二叉树中双亲节点和孩子节点之间的内在关系选择关键字最小的记录。
大根堆：各节点关键字满足：a[i] >= a[2i]并且a[i] >= a[2i + 1]
小根堆：各节点关键字满足：a[i] <= a[2i]并且a[i] <= a[2i+1]
算法时间复杂度：o(nlogn)归并排序：
算法思想：设初始序列长度为n,将这n个序列看成n个有序的子序列，然后辆辆合并，得到一个ceil(n/2)长度为2的有序子序列。
在此基础上再对长度为2 的有序子序列进行归并排序，得到若干长度为4的子序列，如此重复直到得到一个长度为n的有序子序列为止时间复杂度：o(nlogn)
选堆快希不稳（稳定性） 选堆归基不变（时间复杂度的变化特性）
直接插入排序：
算法思想：将第i个记录插入到前面已经排好序的i - 1个记录中去。
算法要点：使用监视哨r[0]临时保存带插入记录
从后往前查找应插入的位置
查找与移动用同一循环完成
算法时间复杂度：o(n^2)折半插入排序：
算法思想：利用折半查找的思想找到需要插入的位置
算法时间复杂度：o(n^2)，虽然减少了查找插入位置的次数，但是移动元素的时间仍未改变希尔排序：
算法思想：将待排序的关键字序列分成若干个较小的子序列，对子序列进行直接插入排序，使整个待排序序列排好序。
算法时间复杂度：o(n^1.5)快速排序：
算法思想：从待排序记录中选择一个记录为枢纽，设为K，将其余大于K的记录移动至K的后面，小于K的移动至前面，此过程称为一趟快速排序。当然就是对接下来的两个字表进行相同的操作，直到子表的长度不超过1
算法时间复杂度：o(Knlog2n),K为常数因子，且在所有O(nlogn)复杂度中,快排的K值最小简单选择排序：
算法思想：
第一趟：从第一个记录开始，通过n-1次关键字比较，从n个记录中选出最小的并和第一个记录交换；
第二趟：从第二个记录开始，通过n-2次关键字比较，从n -1个记录中选出最小的并和第二个记录交换；
...
算法时间复杂度：o(n^2)堆排序：
算法思想：将向量中存储的数据看成一棵完全二叉树，利用完全二叉树中双亲节点和孩子节点之间的内在关系选择关键字最小的记录。
大根堆：各节点关键字满足：a[i] >= a[2i]并且a[i] >= a[2i + 1]
小根堆：各节点关键字满足：a[i] <= a[2i]并且a[i] <= a[2i+1]
算法时间复杂度：o(nlogn)归并排序：
算法思想：设初始序列长度为n,将这n个序列看成n个有序的子序列，然后辆辆合并，得到一个ceil(n/2)长度为2的有序子序列。
在此基础上再对长度为2 的有序子序列进行归并排序，得到若干长度为4的子序列，如此重复直到得到一个长度为n的有序子序列为止时间复杂度：o(nlogn)
选堆快希不稳（稳定性） 选堆归基不变（时间复杂度的变化特性）
7.在以下协议中，那个协议与其他协议是不属于同一类的()
网络层：IP协议、ICMP协议、ARP协议、RARP协议。
传输层：UDP协议、TCP协议。
应用层：FTP（文件传送协议）、Telenet（远程登录协议）、DNS（域名解析协议）、SMTP（邮件传送协议），POP3协议（邮局协议），HTTP协议， SNMP协议， TFTP。
查看12道真题和解析