【数据结构】【绪论】【基本概念】

【数据结构】【绪论】【基本概念】

• • • • • 一、数据结构的基本概念
        • 二、算法的基本概念
        • 三、习题
        • 四、答案

一、数据结构的基本概念

1.数据：客观事物的符号表示
2.数据元素：数据的基本单位
3.数据项：数据结构中讨论的最小单元
4.数据对象：性质相同的数据元素的集合
5.数据的逻辑结构：
（1）线性结构
（2）非线性结构：树 图
6.数据的物理结构：
（1）顺序存储
（2）链式存储
（3）索引存储
（4）散列存储

二、算法的基本概念

1.算法：由基本运算及规定的运算顺序所构成的完整的解题步骤
2.算法的特性：
（1）有穷性
（2）确定性
（3）输入
（4）输出
（5）可行性
3.算法的设计目标
（1）正确性
（2）可读性
（3）健壮性
（4）高效率与低存储量需求

三、习题

1.下面说法错误的是（）
（1）算法原地工作的含义是指不需要任何额外的辅助空间
（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O( 2 n 2^n 2n)
（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上届
（4）同一个算法，实现语言的级别越高，执行效率就越低
A.(1） B.(1),(2） C.(1),(4) D.(3)

2.下述（）与数据的存储结构无关
A.栈 B.双向链表 C.散列表 D.线索树 E.循环队列

3.连续存储设计时，存储单元的地址（）
A.一定连续 B.一定不连续 C.不一定连续 D.部分连续，部分不连续

4.以下属于逻辑结构的是（）
A.顺序表 B.散列表 C.有序表 D.单链表

5.下面函数mergesort()执行的时间复杂度为多少？假设函数调用被写为mergesort（1，n），merge()函数时间复杂度为O(n)

void mergegsort(int i, int j)
{int m;if(i != j){m=(i+j)/2mergegsort( i,m );mergegsort( m+1,j );mergeg( i,j,m );//本函数时间复杂度为O(n)}
}

四、答案

1. C
   （1）一个可执行程序除了需要内存空间来寄存本身的指令、常数、变量和输入数据外，还需要额外空间，如果这个额外空间相当于问题的规模（输入数据）来说是个常数，我们就称之为原地工作。因此(1)不对。
   （2）时间复杂度的大小，常用的比较关系：
   O(1) $\le$ O( l o g 2 n log_2^n log2n​) $\le$ O(n) $\le$ O(n* log ⁡ 2 n \log_2^n log2n​) $\le$ O( n 2 n^2 n2) $\le$ O( n 3 n^3 n3) $\le$… $\le$ O( n k n^k nk) $\le$ O( 2 n 2^n 2n)
   （3）对于O(1) 、 O( l o g 2 n log_2^n log2n​) 、 O(n)等，O的形式定义为：若f(n)是正数n的一个函数，，则O(f(n))表示存在一个正常数M，使得当n$\ge$ n 0 n_0 n0​时|O(f(n))|$\le$M*|f(n)|，也就是O(f(n))给出了函数f(n)的一个上界
   （4）这句话是严版数据结构上的原句，大多数情况下应该是这样，但是不能说的这么绝对，需要看编译连接后最终的机器指令，这些指令操作的次数越少，说明该语言在某种编译链接环境下效率越高。实际上即使同一种语言在不同的编译环境下，也有可能不同

2. A
   A项 栈是逻辑结构
   B项 双向链表是说明线性表是以链式结构存储的
   C项 散列是算法，散列存储方法本质上是顺序存储方法的扩展。散列表本质上是顺序表的扩展
   D项 线索树是在链式存储结构的基础上对树进行线索，与链式存储结构有关
   E项 循环队列是建立在顺序存储结构上的

3. A
   顺序存储结构要开辟一片连续的存储空间

4. C
   有序表指出了表中数据是根据一定逻辑顺序排序的，是一种逻辑结构

5. 显然规模为n，基本操作在merge()函数中，merge()时间复杂度为O(n),因此merge()内基本操作次数可设为cn，mergesort()函数基本操作次数设为f(n)，则有
   f(n)=2f(n/2)+cn
   = 2 2 2^2 22f(n/4)+2cn
   = 2 3 2^3 23f(n/8)+3cn
   …
   = 2 k 2^k 2kf(n/( 2 k 2^k 2k))+kcn
   由mergesort()函数可知，f(1)=O(1)
   当n= 2 k 2^k 2k (k= l o g 2 n log_2^n log2n​)时 f(n)=O(1)n+cn l o g 2 n log_2^n log2n​
   因此时间复杂度T(n)=O(n l o g 2 n log_2^n log2n​)

2 2 2^2 22f(n/4)+2cn 到 2 3 2^3 23f(n/8)+3cn，完整的步骤应该是
2* 2* f(n/4)+cn*(1/2)+cn= 2 2 2^2 22f(n/4)+2cn
因为进入mergesort(i,m)或者mergesort(m+1,j)函数后，merge()函数处理的序列变为原来的一半，因此基本操作次数变为原来的一半。对于本步，基本操作次数为cn*（1/2），以此类推，每次内层函数的基本操作次数是外层函数的一半。因此由本步推出下一步就应该是
( 2 2 2^2 22) * (2*f(n/8) + cn * (1/4))+2cn=( 2 3 2^3 23)f(n/8)+3cn

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！