2018年算法笔试题（持续更新）

1、假设有10个关键字互为同义词，若用线性探测再散列探查法把这10个关键字存入哈希表中，至少需要探测的次数
A、55      B、11      C、10      D、100
2、设某循环队列的容量为50，如果头指针Front=40(指向队头元素)，尾指针rear=10（指向队尾元素下一个位置），则该循环队列中共有（ ）个元素
A、10      B、40      C、20      D、30
3、在含有10个结点的二叉排序树上，查找关键字为20的结点，则依次比较的关键字有可能是（ ）
A、25,10,15,20      B、25,10,15,18,20      C、10,30,25,20      D、10,30,20
4、计算式6/3(4+5)-7/(9+8)的前序表达式和后续表达式分别为（    ）
A、-/63+457/+98 63/4+5798+/-
B、-/63+45/7+98 63/45+798+/-
C、-/63+45/79+8 63/45+79+8/-
D、-6/3+45/7+98 6/345+798+/-
5、已知字符串S=“121121121345623”，模式串P=“12112134”。采用KMP算法进行匹配时，首次匹配失败时候，i=j=6，接下来继续匹配，匹配开始时i和j分别是：
A、i=2,j=1      B、i=6,j=3      C、i=6,j=2      D、i=1,j=0
6、二叉树的谦虚遍历为ABCDEFGH,中序遍历为CDBAFEHG,则次树的后续遍历为（    ）
A、ABECFGDH
B、DCBFHGEA
C、HGFEABCD
D、CDBAEFGH
7、对信号量S执行V操作后，当S小于0时表示（    ）
A、s.count的绝对值为可以资源个数
B、唤醒一个阻塞进程
C、s.count的绝对值为阻塞进程个数
D、唤醒一个就绪进程
8、一个理想的调度算法应当考虑（    ）
A、确保每个进程获得合理的CPU份额
B、使CPU百分百地忙碌
C、使批处理用户等待输出的时间尽可能短
D、系统并发进程的数量
9、在mysql中执行命令drop database;会（    ）
A、删除数据库和表文件
B、仅删除表的记录，不删除表的结构
C、返回被删除表的名称列表
D、返回被删除表的数量
10、TCP的关闭过程，说法正确的是（    ）
A、处于TIME_WAIT状态的连接等待2MSL后真正关闭连接
B、主动发送FIN消息的连接端，收到对方回应ack之前不能发只能收，在收到对方回复ack之后不能发也不能收，进入CLOSING状态
C、在已经成功建立连接的TCP连接上，任何情况下都不允许丢失数据
D、对一个established状态的TCP连接，在调用shutdown函数之前调用close接口，可以让主动调用的一方进入半关闭状态
11、现有三张表student(sid,aname,sex,age),course(cid,cname),schedule(sid,cid,grade),请检索选课表schedule中选修课程号（cid）为c3的学生中成绩最高的学号sid。（    ）
A、select sid from schedule where cid ='c3' and grade not in (select grade from schedule where cid='c3')
B、select sid,sum(grade) from schedule where grade>=60 group by sid order by 2 desc having count()>=4 where cid='c3' and grade>=(select grade from schedule where cid='c3')
C、select sid from schedule where cid = 'c3' and grade in (select grade from schedule where cid = 'c3')
D、select sid from schedule where cid = 'c3' and grade>=all(select grade from schedule where cid = 'c3')
12、以下（    ）算法是分类算法？
A、K-Means      B、Birch      C、DBSCAN      D、CART
13、下面程序段的所需要的计算时间为（    ）
int MaxSum(int n,int * a,int &besti,int &bestj)

14、以下哪个描述不属于关系数据模型的优点？
A、概念单一，无论实体还是实体之间的联系都是用关系表示
B、关系型数据库可以存储非结构化数据
C、存取路径对用户透明，有更高的数据独立性、更好的安全保密性
D、关系模型中的数据操作是集合操作，及操作的对象和操作的结果都是用关系表示
15、public class Test{
                    Person person = null;
                    Public person createPerson(String type){
                                if("1".equals(type)){
                                            person = new BlabkPerson();
                                }else if("2".equals(type)){
                                            person=new YellowPerson();
                                }else{
                                            person = new SupperPerson();
                                }
                    }
}
上面的代码使用了下面那红设计模式？（    ）
A、简单工厂（Simple Factory）        B、工厂方法（Factory Method）
C、抽象工厂（Abstract Factory）      D、建造者模式（Builder）
16、图G=（V，E）采用邻接链表表示时，其深度优先搜索（DFS）算法的时间复杂度是：
A、O(V)      B、O(V2)      C、O(E2)      D、O(V+E)