数据结构
相似问题和答案
第1题：
A、O(n2)
B、O(nlog2n)
C、O(n)
D、O(log2n)
第2题：
设平衡二叉排序树(AVL树)的节点个数为n，则其平均检索长度为
A．O(1)
B．O(log2n)
C．O(n)
D．O(n log2n)
解析：平衡二叉树又称AVL树，它或者是一棵空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1，若将二叉树上节点的平衡因子BF定义为该节点的左子树的深度减去它的右子树的深度，则平衡二叉树上所有节点的平衡因子只可能是-1、0和1。只要二叉树上有一个节点的平衡因子的绝对值大于1，则该二叉树就是不平衡的。因为AVL树上任何节点的左右子树的深度之差都不超过1，则可以证明它的深度和log2n是同数量级的(n为节点个数)。因此，它的平均查找长度也和log2n同数量级。
第3题：
●在平衡二叉排序树上进行查找时，其时间复杂度为 (52) 。
(52) A．O(log2n+1)
B．O(log2n)
C．O(log2n-1)
D．log22n
【解析】此题是考查二叉树的查找效率问题。这是二叉树的基本查找问题，因为是平衡二叉树，其时间复杂度即为树的高，所以为log2n。
第4题：
以下程序的输出结果是【 】。
main()
{ int x=0；
sub(&x，8，1)；
printf(“%d\n”，x)；
}
sub(int *a，int n，int k)
{ if(k＜＝n)sub(a，n/2，2*k)；
*a+=k；
}
7 解析：在主函数中定义了一个变量x并赋初值0，然后执行函数调用语句，该语句的执行过程为sub(&x,8,1)调用sub(&a,4,2)，sub(&a,4,2)调用sub(&a,2,4)，sub(&a,2, 4)中由于24，所以if后面括号里的判断为假，递归结束，执行其后的*a+=k;语句此时 x=x+k=0+4=4，回退到上一层调用函数sub(&x,4,2)中，执行后面的语句，x=x+k= 4+2=6，再回推到最上一层调用函数sub(&x,8,1)执行后面的语句，x=x+k=6+1=7，所以最后输出7。
第5题：
运行以下程序后，输出结果为_____________。 Private Sub Command1_Click() a=1:b=2:c=3 Call test(a,b+3,(c)) Print "main:";a;b;c End Sub Private Function test(p,m,n) p=p+1:m=m+1:n=n+1 Print "sub:";p;m;n End Function
：A. sub:2 6 4 main:1 2 3
B. sub:2 6 4 main:2 2 3
C. sub:2 6 4 main:2 6 4
D. sub:2 6 4 main:1 6 4
第6题：
采用折半查找法查找长度为n的线性表时，每个元素的平均查找长度为()。
A.O（n2）
B.O（nlog2n）
C.O（n）
D.O（log2n）
第7题：
结点数目为n的二叉查找树(二叉排序树)的最小高度为(52)、最大高度为(53)。
A．n
B．
C．[log2n]
D．[log2(n+1)]
解析：本题考查二叉排序树的基本构造特点。若二叉树中有n个结点，则结点分布均匀、且高度最小的树的特点是除了最后一层，其余各层的结点数目都达到最大值(第i层上有2t-1个结点)，此时树的高度为 [log2(n+1))。若每层只有一个结点，则树的高度为n。具有三个结点的二叉树的所有形态如下所示，每层只有一个结点时称为单枝树。
二叉排序树是根据输入序列构造的，当序列呈现有序的特点时，就构造出一棵单枝树。
第8题：
（ 1 ）下列叙述中，正确的是
A ）对长度为 n 的有序链表进行查找，最坏情况下需要的比较次数为 n
B ）对长度为 n 的有序链表进行对分查找，最坏情况下需要的比较次数为（ n/2 ）
C ）对长度为 n 的有序链表进行对分查找，最坏情况下需要的比较次数为（ log 2 n ）
D ）对长度为 n 的有序链表进行对分查找，最坏情况下需要的比较次数为（ n log 2 n ）
第9题：
有如下事件过程： Private Sub Command1_Click( ) Dim m AS Integer，n AS Integer m=2：n=1 Print "m="；m；"n="；n Call TOD(m，n) Print "m="；m；"n="；n End Sub Sub TOD(x，y) x=x^2 y=y^3 End Sub 程序运行后，输出的结果为
A．m=2，n=1 m=1，n=2
B．m=2，n=1 m=4，n=1
C．m=1，n=2 m=1，n=4
D．m=1，n=2 m=2，n=4
解析：本题考查的是函数调用和输出语句。定义了一个函数，函数的功能是：将实参传给形参，按址传送，将改变实参的数值，语句x=x^2的作用是将x的平方值赋给x，为4；语句y=y^3的作用是将y的三次方值传给y，为1；然后返回主调过程，输出变化前后的值。
第10题：
若有如下程序： int sub(int m) { if(m==1||m==0) return 2; else return(sub(m-1)*sub(m-2));} main() { int n; scanf("%d",&n); printf("%d",sub(n)); } 如果从键盘输入4＜回车＞，则程序运行后的输出结果是( )。
A．8
B．16
C．24
D．32
解析：本题的sub()函数是一个递归函数，当参数m为1或0时返回2，否则返回sub(m-1)*sub(m-2)。所以sub(4)递推下来就是sub(4)=sub(3)*sub(2)=sub(2)*sub(1)*sub(1)*sub(0)=sub(1)*sub(0)*2*2*2=25(上标)=32。所以正确答案是D。