数据结构复习题（考试用的），求高手解答，有点急（第二部分）

数据结构复习题（考试用的），求高手解答，有点急（第二部分）
二、选择题：
1、在具有n个结点的二叉排序树上插入一个新结点时，其时间复杂度大致为（　）。
A、O（n2） B、O(n) C、O(log2n) D、O(nlog2n)
2、下面程序段的时间复杂度为（　）。
　　 for (i=1;i<=m;++i)
for (j=1;j<=n;++j)
A[i,j]=i*j;
A、O（m2） B、O（n2） C、O（m*n） D、O（m+n）
3、带头结点的单链表h为空的判断条件是（ ）。
A、h==NULL B、h->next==NULL C、h->next==h D、h!=NULL
4、单链表中，增加头结点的目的是为了（ ）。
A、方便运算的实现 B、标识单链表
C、使单链表中至少有一个结点 D、用于标识起始结点的位置
5、一棵非空的二叉树的前序遍历与后序遍历序列正好相反，则该二叉树一定满足（）
A: 所有的节点均无左孩子； B: 所有的节点均无右孩子；
C: 只有一个叶子节点； D: 是任意一棵二叉树
6、在一个具有n个单元的顺序栈中，假定以地址低端（即下标为0的单元）作为栈底，以top作为栈顶指针，则当作退栈处理时，top的变化为（　）。
A、top不变　B、top=0　C、top＝top+1　D、top=top-1
7、链栈与顺序栈相比，有一个较明显的优点是（ ）。
A、通常不会出现栈满的情况 B、通常不会出现栈空的情况
C、插入操作更加方便 D、删除操作更加方便
8、设有一个无向图G＝（V，E）和G｀＝（V｀，E｀），如果G｀为G的生成树，则下面不正确的说法是（　）。
A、G｀为G的子图　 B、G｀为G的连通分量
C、G｀为G的极小连通子图且V｀＝V 　
D、G｀是G的一个无环子图
9、设计一个判别表达式中左右括号是否配对出现的算法，采用（　）数据结构最佳。
A、线性表的顺序存储结构　 B、栈　
C、队列　 D、线性表的链式存储结构
10、在具有n个叶子的哈夫曼树中，其结点总数为（　）。
A、不确定　B、2n　C、2n+1　D、2n-1
11、任何一个无向连通图的最小生成树（　）。
A、只有一棵　B、有一棵或多棵　C、一定有多棵　D、可能不存在
12、带权有向图G用邻接矩阵A存储，则顶点i的入度等于A中（ ）。
A、第i行非∞元素之和 B、第i列非∞元素之和
C、第i行非零且非∞元素的个数 D、第i列非零且非∞元素的个数
13、若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（　）存储方式最节省时间。
A、单链表　B、双链表　C、单向循环链表　D、顺序表
14、 若用一个大小为6 的数组来实现循环队列，且当前rear 和front 的值分别为0 和3，当从队列中删除一个元素，再加入两个元素后，rear 和front 的值分别为（　）。
A. 1 和 5 B. 2 和4
C. 4 和2 D. 5 和1
15、已知10个数据元素为（54，28，16，34，73，62，95，60，26，43），按依次插入结点的方法生成一棵二叉排序树后，查找值为62的结点所需用比较的次数为（　），查找61的比较次数为（　）。
A、2　B、3 　C、4　D、5
16、在一个具有n个单元的顺序栈中，假定以地址高端（即下标为n-1的单元）作为栈底，以top作为栈顶指针，则当向栈中压入一个元素时，top的变化为（　）。
A、top不变　B、top=n-1　C、top=top+1　D、top=top-1
17、设森林T中有三棵树，第一、二、三棵树的结点个数分别是n1，n2，n3，那么当把森林转换成二叉树后，其根结点的左子树上有（　）个结点，右子树上有（　）个结点。
A、n1-1　B、n1　C、n1+n2　D、n2+n3

1.c 2.c 3. b 4.a(使得一些算法统一) 5.a,b都对（左右单直都满足前序与后序相反）6.c 7.a 8.b 9.b
10. d 11.a 12. d 13. d 14.b 15.b,c 16.d 17. a,d
纯自己做的记得给分哦
如果有类似的问题尽管在问我