优酷【算法类】：笔试题目6终（最全）

已知一棵完全二叉树中共有626个结点,叶结点的个数应为()
A. 311
B. 312
C. 313
D. 314
E. 其他

单选
一棵具有n个结点的完全二叉树的树高(深度)是()
A. [logn]+1
B. logn+1
C. [logn]
D. logn-1

单选
深度为h的满m叉树的第k层有()个结点(1<=k<=h)
A. mk-1
B. mk-1
C. mh-1
D. mh-1

单选
设树T的度为4,其中度为1,2,3和4的结点个数分别为4,2,1,1,则T中的叶子数为()
A. 5
B. 6
C. 7
D. 8

单选
一个有7个顶点的完全三部图，至少有存在几条边？
A. 10
B. 11
C. 15
D. 16

单选
邻接矩阵为对称矩阵的图是？
A. 有向图
B. 带权有向图
C. 有向图或无向图
D. 无向图

单选
对于以下说法，错误的是________。
A. Dijkstra算法用于求解图中两点间最短路径，其时间复杂度O(n^2)
B. Floyd-Warshall算法用于求解图中所有点对之间最短路径，其时间复杂度为O(n^3)
C. 找出n个数字的中位数至少需要O(n*logn)的时间
D. 基于比较的排序问题的时间复杂度下界是O(n*logn)

单选
任何无向图都存在生成树()
A. 对
B. 错

单选
在表示某工程的AOE网中,加速其关键路径上的任意关键活动均可缩短整个工程的完成时间()
A. 对
B. 错

单选
在AOE图中,关键路径上活动的时间延长多少,整个工程的时间也就随之延长多少()
A. 对
B. 错

有向图中顶点V的度等于其邻接矩阵中第V行中的1的个数()
A. 对
B. 错

单选
有向图的邻接矩阵是对称的()
A. 对
B. 错

单选
邻接矩阵适用于有向图和无向图的存储,但不能存储带权的有向图和无向图,而只能使用邻接表存储形式来存储它()
A. 对
B. 错

单选
要连通具有n个顶点的有向图,至少需要()条边
A. n-1
B. n
C. n+1
D. 2n

单选
用邻接表存储图所用的空间大小()
A. 与图的顶点数和边数都有关
B. 只与图的边数有关
C. 只与图的顶点数有关
D. 与边数的平方有关

单选
当各边上的权值()时,BFS算法可用来解决单源最短路径问题
A. 均相等
B. 均互不相等
C. 不一定相等

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

单选
10个数放入模10hash链表，最大长度是多少？
A. 1
B. 10
C. 9
D. 以上答案都不正确

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

单选
采用线性探测法处理散列时的冲突,当从哈希表删除一个记录时,不应将这个记录的所在位置置空,因为这会影响以后的查找()
A. 对
B. 错