22, 2022年硕士学位研究生入学考试试题回忆版

数据结构

1．一个时间复杂度为n2

的算法运行，m1算n个问题用时1秒，m2处理器是m1效率的64倍，则m2每秒能计算（）个问题。

A. 64n              B. 8n           C. n+64             D. n+32

2.下列说法正确的是?()

A,单链表的表头和表尾都可以做队头，且进出队效率相同

B,将单链表表头作为队头，可以在O(1)的时间复杂度下完成出队入队操作

C,循环双链表比单链表入队出队效率更高

D,单链表比循环双链表入队出队效率更高

3，二叉树结点1000个，最小高度为？

A,1000               B，9            C,10                 D,11.

4, 设二叉排序树上有n个结点,则在二叉排序树上查找结点的平均时间复杂度为( )。

A.O(log2n )           B.O(n)          C.O(nlog2n )          D.O(n2 )

5，邻接矩阵如下，迪杰斯特拉算法找1号出发的最短路径(下标从1开始，1是第一步)，第四步是哪个点（）。

A.1               B.2         

C.3               D.4