龙空技术网

数据结构错题收录(一)

Coding日记 69

前言:

今天姐妹们对“二叉搜索树的时间复杂度”可能比较关心,姐妹们都需要分析一些“二叉搜索树的时间复杂度”的相关文章。那么小编在网上搜集了一些关于“二叉搜索树的时间复杂度””的相关内容,希望我们能喜欢,姐妹们一起来学习一下吧!

1、以下属于逻辑结构的是()• A:顺序表• B:哈希表• C:有序表• D:单链表解析

顺序表、哈希表和单链表是三种不同的数据结构,既描述逻辑结构,又描述存储结构和数据运算。而有序表是指关键字有序的线性表,仅描述元素之间的逻辑关系,它既可以链式存储,又可以顺序存储,故属于逻辑结构。

答案:C2、链式存储设计时,结点内的存储单元地址()。• A:一定连续• B:一定不连续• C:不一定连续• D:部分连续,部分不连续解析

链式存储设计时,各个不同结点的存储空间可以不连续,但结点内的存储单元地址必须连续

答案:A3、对于两种不同的数据结构,逻辑结构或物理结构一定不相同吗?

数据的运算也是数据结构的一个重要方面。 对于两种不同的数据结构,它们的逻辑结构和物理结构完全有可能相同。比如二叉树和二叉排序树,二叉排序树可以采用二叉树的逻辑表示和存储方式,前者通常用于表示层次关系,而后者通常用于排序和查找。虽然它们的运算都有建立树、插入结点、删除结点和查找结点等功能,但对于二叉树和二叉排序树,这些运算的定义是不同的,以查找结点为例,二叉树的时间复杂度为O(n),而二叉排序树的时间复杂度为O(log)。

4、试举一例,说明对相同的逻辑结构,同一种运算在不同的存储方式下实现时,其运算效率不同。

线性表既可以用顺序存储方式实现,又可以用链式存储方式实现。在顺序存储方式下,在线性表中插入和删除元素,平均要移动近一半的元素,时间复杂度为O(n);而在链式存储方式下,插入和删除的时间复杂度都是O(1)。

5、下面关于倒排文件的说法中正确的是____。• A:倒排文件是对主关键字建立索引• B:倒排文件是对次关键字建立索引• C:倒排文件的优点是维护简单• D:采用倒排文件是为了节省存储空间解析

倒排文件:用记录的非主属性(也叫副键)来查找记录而组织的文件叫倒排文件,即次索引。倒排文件中包括了所有副键值,并列出了与之有关的所有记录主键值,主要用于复杂查询。倒排文件的优点是检索记录较快。特别是对某些询问,不用读取记录,就可得到解答。

答案:B6、下列术语中,____与数据的存储结构无关。• A:循环队列• B:堆栈• C:散列表• D:单链表解析

数据的存储结构有顺序存储、链式存储、索引存储和散列存储。栈是一种抽象数据类型,可采用顺序存储或链式存储,是一种逻辑结构。散列表和单链表表示几种数据结构,既描述逻辑结构,又描述存储结构。

答案:B7、下面程序的时间复杂度为____。

for (i = 1, s= 0 ; i < n ; i++){    t = 1 ;    for(j =1 ; j<=i;j++)    {        t=t*j;    }    s=s+t;}
• A:O(n)• B:O()• C:O()• D:O()解析

分析代码:内层循环执行i次,外层循环执行n次,i从1取到n。 得知执行最内层循环语句总次数为,即O()。

答案:B8、下面算法的时间复杂度是____。

Void fun(int n){    int i = 0,s = 0;    while(s<n)    {        ++i;        s=s+i;    }}
• A:O(n)• B:O()• C:O()• D:O(nlog(n))解析

最底层的代码为s=s+i,s到达n的过程刚好是1+2+3+4....+m这样累加起来的,根据等差队列之和的公式,(1+m)*m=2n,故m约等于根号n,所以此题选C。

答案:C9、下面算法的空间复杂度为_____。

float aver(float a[n]){    int j;    for(j=n;j>0;j--)        printf("%8.2f",a[j]);}
• A:O(1)• B:O(log)• C:O(n)• D:O()解析

函数体定义中出现数组,数组在初始化时需要分配空间,此时空间复杂度为O(n),所以选C。

答案:C10、已知程序如下所示,程序运行时使用栈来保存调用过程的信息,自栈底到栈顶保存的信息依次对应的是____。

int S(int n){    return (n<=0)?0:S(n-1)+n;}void main(){    cout<<S(1);}
• A :main()->S(1)->S(0)• B:S(0)->S(1)->main()• C:main()->S(0)->S(1)• D:S(1)->S(0)->main()解析

程序都是从main函数开始的,进入main函数后执行S(1),之后递归执行S(0)。

答案:A学海无涯苦作舟

标签: #二叉搜索树的时间复杂度