模拟试题6
一、选择题（每小题1分，共10分）
1、如某数据结构的数据元素的集合为S={A,B,C,D,E,F,G},数据元素之间的关系为R={<A,D>,<A,G>,<D,B>,< D, C >,< G, E>,< G, F >},则该数据结构是一种__________ 。
(A)线性结构_____________ (B)树结构_____________ (C)图结构_____________ (D)链表结构
2、设有二维数组A[50][60]，其元素长度为1个字节，按列优先顺序存储，首元素A[0][0]的地址为200，则元素A[10][20]的存储地址为__________ 。
(A)820_____________ _____________ (B)720_____________ _____________ (C)1210_____________ _____________ (D)1410
3、一组记录（50，40，95，20，15，70，60，45，80）进行冒泡排序时，第一趟需进行相邻记录的交换的次数为_________ 。
(A)5_____________ _____________ _____________ (B)6_____________ _____________ _____________ (C)7_____________ _____________ _____________ (D)8
4、具有20个结点的二叉树，其深度最多为_________ 。
(A)4_____________ _____________ _____________ (B)5_____________ _____________ _____________ (C)6_____________ _____________ _____________ (D)20
5、在具有N个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队空的条件为_________ 。
(A)front==rear_____________ _____________ _____________ (B)（rear+1）%MAXSIZE==front_____________ _____________ _____________
(C)front-rear==1_____________ _____________ _____________ (D)rear%MAXSIZE==front
6、一个5×5的对称矩阵采用压缩存储，需要存储_________ 个元素。
(A)5_____________ _____________ _____________ (B)10_____________ _____________ _____________ (C)15_____________ _____________ _____________ (D)20
7、一个无向连通图有5个顶点、8条边，则其生成树将要去掉_________ 条边。
(A)3_____________ _____________ _____________ (B)4_____________ _____________ _____________ (C)5_____________ _____________ _____________ (D)6
8、设一颗二叉树共有50个叶子结点（终端结点），则共有____ ____ 个度为2的结点。
(A)25_____________ _____________ _____________ (B)49_____________ _____________ (C)50_____________ _____________ (D)51
二、填空题（每题2分，共16分）
1、一个算法，如果不管问题规模大小，运行所需时间都是一样，则该算法的时间复杂度是
______________ 。
2、已知某算法的执行时间为（n+n2）/2+log2(2n+1)，n代表问题规模，则该算法的时间复杂度是______________ 。
3、在求最小生成树的两种算法中，______________ 算法适合稀疏图。
4、一棵哈夫曼树是由5个叶子结点形成的，该哈夫曼树总共有_ ____________ 个结点。
5、设循环队列Q[1….N]的头尾指针分别为F，R，当插入元素时尾指针R加1，头指针F总是指在队列中第一个元素的前一个位置，则队列中元素个数为______________ 。