Question

求解数据结构试题！！！

1.元素大小为1个单元，容量为n个单元的非空顺序栈中，以地址高端为栈底，以top作为栈顶指针，则出栈处理后，top的值应修改为( )
A. top=top B. top=n-1
C. top=top-1 D. top=top+1
2.某二叉树的先根遍历序列和后根遍历序列正好相反，则该二叉树具有的特征是( )
A.高度等于其结点数 B.任一结点无左孩子
C.任一结点无右孩子 D.空或只有一个结点

3.若构造一棵具有n个结点的二叉排序树，最坏的情况下其深度不超过( )
A. B. n
C. D. n+1

4.在插入排序和选择排序中，若原始记录已基本有序，则较适合选用____________。
5.对n个元素的序列进行冒泡排序时，最多需进行____________趟。

6.将两个各有n个元素的有序表合并成一个有序表，其最少的比较次数为(　　　)
A.n B.2n-1
C.2n D.n2

7.若用一个有6个单元的数组来实现循环队列，rear和front的初值分别为0和3。则从队列中删除一个元素，再添加两个元素后，rear和front的值分别为(　　　)
A.1和5 B.2和4
C.4和2 D.5和1

8.在一棵深度为H的完全二叉树中，所含结点的个数不少于(　　　)
A.2H-1-1 B.2H-1
C.2H-1 D.2H
9.一个具有n个顶点的无向连通图，它所包含的连通分量数为(　　　)
A.0 B.1
C.n D.不确定

10.关于VSAM文件存取操作的说法，正确的是(　　　)
A.不能顺序存取，只能按关键字随机存取 B.不能顺序存取，不能按关键字随机存取
C.只能顺序存取，不能按关键字随机存取 D.既能顺序存取，也能按关键字随机存取
11.在任何问题中，数据元素都不是孤立的，它们之间总存在某种关系，通常称这种关系为
________。
12.在无向图G的邻接矩阵A中，若A［i］［j］等于0，则A［j］［i］等于________

13.对含有n个结点e条边的无向连通图，利用prim算法生成最小生成树的时间复杂度为________。
14.对n个元素进行冒泡排序时，最少的比较次数为________。

15. for（i=0；i<m；i++）
for（j=0；j<t；j++）
c［i］［j］=0；
for（i=0；i<m；i++）
for（j=0；j<t；j++）
for（k=0；k<n；k++）
c［i］［j］=c［i］［j］+a［i］［k］*b［k］［j］；
上列程序的时间复杂度为( )
A.O(m+n×t) B.O(m+n+t)
C.O(m×n×t) D.O(m×t+n）

Answer 1

1，C
2，A 一退化的二叉树就是链表
3，B选项不全
4，插入排序
5，n*n
6，n 第二个表的最小比第一个表的最大来的大
7，B 出队，front（4）=(front（3）+1)%6
入队rear(2)=(rear(0)+2)%6
8，2的H-1次方 BC中的一个 H-1层是满的 H层至少一个
9，A 图中任意一个顶点都是连通的，就是连通的，非连通图的极大连通子图叫连通分量
10，D
11，结构
12, 0 无向连通矩阵是对称的
13，O(elog2e)
14, n-1
15，C
希望可以提供参考