数据结构练习题1：基本概念

约定不等于承诺〃 2024-03-16 21:18 35阅读 0赞

#### 练习题1：基本概念 ####

*   *  1 抽象数据类型概念分析
     *  2. 逻辑结构与存储结构概念分析
     *  3.综合选择题
     *  4.综合判断题
     *  5.时间复杂度相关习题
     *  6 时间复杂度计算方法（一、二、三层循环）

### 1 抽象数据类型概念分析 ###

1.可以用（抽象数据类型）定义一个完整的数据结构。

分析：  
1）抽象数据类型（ADT）描述了数据的逻辑结构和抽象运算，通常用数据对象、数据关系和基本操作集这样的三元组来表示，从而构成一个完整的数据结构定义。

2）抽象数据类型的两个重要特征：数据抽象和数据封装。  
①数据抽象：用ADT描述程序处理的实体时，强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口。（即外界使用它的方法）  
②数据封装：将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节。

[抽象数据类型的理解][Link 1]

### 2. 逻辑结构与存储结构概念分析 ###

1.数据的逻辑结构独立于其存储结构。  
分析：数据的逻辑结构从实际问题出发，只采用抽象表达方式，独立于存储结构，数据的存储方式有多种选择。而数据的存储结构是逻辑结构在计算机上的映射，它不能独立于逻辑结构而存在。

2.数据结构的三要素：逻辑结构、存储结构和运算。  
  
**问题：逻辑结构的存储方式有多种选择什么意思？**  
是指既能顺序存储又能链式存储。

3.下面属于逻辑结构的是  
A 顺序表 B 哈希表 C 有序表 D 单链表

4.以下与数据的存储结构有关的术语是  
A.有序表 B.线性表 C.有向图 D.顺序表

5.以下与数据的存储结构无关的术语是  
A 循环队列 B 链表 C 哈希表 D 栈

**逻辑结构与存储结构： 3-5 CDD**

有序表、线性表、有向图既能顺序存储，又能链式存储，是逻辑结构。  
顺序表、循环队列、顺序栈为顺序存储。  
  
**属于逻辑结构 = 与存储结构无关 = 既能顺序存储又能链式存储  
与存储结构有关 = 只能顺序存储或只能链式存储**  
  
**栈逻辑结构对应的顺序存储结构为顺序栈，对应的链式存储结构为链栈。**  
  
**队列的顺序存储结构是循环队列，链式存储结构是链队列，又叫做单链表。**  
  
**线性表逻辑结构对应的顺序存储结构为顺序表，对应的链式存储结构为链表。**

特殊案例：  
有序表是指关键字有序的线性表，仅描述元素之间的逻辑关系，既可以顺序存储（使用数组）也可以链式存储（使用指针），不受存储结构制约，由于有序受到逻辑制约，属于逻辑结构。  
哈希表，是个大数组，顺序存储。

问题1：如何区分数据结构和数据类型？

数据类型的运算主要是算数运算、逻辑运算等。  
而数据结构运算主要是对数据的增删改查等。  
[数据类型和数据结构的区别][Link 2]

问题2：抽象数据类型有哪些？  
栈、队列、树、图、集合、映射。  
  
**问题3：哈希表是散列存储，为什么做题时不考虑这种存储方式？**

6.存储数据时存储的是数据元素的值和数据元素之间的关系。

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

结点内什么意思？ 是value值域与next域结合，称这个结点为内部。

typedef struct LNode \{

int value; // value中存放结点值域，默认是int型

struct Lnode \*next;//指向后继结点的指针

\}LNode; // 定义单链表结点类型

上述定义了一个结构体，包括两部分，一是值域，二是指针域；每当定义一个结点都会产生这两个区域。如下图：

<table> 
 <thead> 
  <tr> 
   <th>value</th> 
   <th>next</th> 
  </tr> 
 </thead> 
</table>

这个value与next域必须是挨着的，称这个结点为内部。  
结点内部一定是连续的。若第一个结点占用两个地址，那么value域的起始地址是1，则指针域的地址就是2。同理若第二个结点的value地址是10，则next域就是11。

参考：[链式存储设计时，链表结点内的存储单元地址是如何分布的][Link 3]

### 3.综合选择题 ###

1.下列叙述中正确的是  
A)算法的效率只与问题的规模有关，而与数据的存储结构无关  
B)算法的时间复杂度是指执行算法所需要的计算工作量  
C)数据的逻辑结构与存储结构是一一对应的  
D)算法的时间复杂度与空间复杂度一定相关

2.算法的有穷性是指  
A）算法程序的运行时间是有限的 B）算法程序所处理的数据量是有限的  
C）算法程序的长度是有限的 D）算法只能被有限的用户使用

3.下列叙述中正确的是  
A）一个逻辑数据结构只能有一种存储结构  
B）数据的逻辑结构属于线性结构，存储结构属于非线性结构  
C）一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率  
D）一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率

4.算法的空间复杂度是指  
A)算法程序的长度 B)算法程序中的指令条数  
C)执行算法程序所占的存储空间 D)算法执行过程中所需要的存储空间

5.在下列选项中，哪个不是一个算法一般应该具有的基本特征  
A、确定性 B、可行性 C、无穷性 D、拥有足够的情报

6.被计算机加工的数据元素不是孤立的，它们彼此之间一般存在某种关系，通常把数i元素之间的这种关系称为  
A 规则 B 结构 C 集合 D 运算

7.设有如下遗产继承规则:丈夫和妻子可以互相继承遗产，子女可以继承父亲和母亲的遗产，子女间不能相互继承，则表示该遗产继承关系最合适的数据结构应该是  
A 树 B 图 C 线性表 D 集合

8.下面关于抽象数据类型的描述错误的是  
A.数据封装 B.用例驱动  
C.信息隐藏 D.使用与实现分离

9.数据结构中，与所使用的计算机无关的是数据的  
A 存储结构 B 物理结构 C 逻辑结构 D 物理和存储结构

10.下列关于算法的时间复杂度陈述正确的是  
A 算法的时间复杂度是指执行算法程序所需要的时间  
B 算法的时间复杂度是指算法程序的长度  
C 算法的时间复杂度是指算法执行过程中所需要的基本运算次数  
D 算法的时间复杂度是指算法程序中的指令条数

**综合选择题：1-5 BADCC 6-10 BBBCC**

### 4.综合判断题 ###

1…在数据元素内数据项之间也有关系，在讨论数据的逻辑结构时应考虑。 × 逻辑结构看的是数据元素之间的关系

2.同一个算法，实现语言级别越高，算法执行的效率越低。√ 级别越高，需要额外执行的条件就越多，效率也就越低。

3.集合中任何两个数据元素之间都没有逻辑关系，而且组织形式松散。√ 除同属于一个集合外，没有其他任何关系。

### 5.时间复杂度相关习题 ###

O(1)<O(log2n)<O(n)<O(nlog2n)<O( n 2 n^2 n2)<O( n 3 n^3 n3)<O( 2 n 2^n 2n)<O(n!)<O( n n n^n nn)

1.下面时间复杂度较小的是 A  
![在这里插入图片描述][5db872b5b6784715a09353c1bdb948ed.png]  
2.以下程序段中语句"m++;"的语句频度为 C

int m=0,i,j;
    for(i=1;i<=n;i++)
    for(j=1;j<=2*ij++)
      m++;

A n B n+1 C n(n+1) D  n 2 n^2 n2  
2+4+6+…+2n = n(n+1)

3.下列函数的时间复杂度是() 。

int func(int n){
        
    int i=0,sum=O;
    while(sum<n)  sum+=++i;
    return i;
    }

设语句频度为f(n)

1+2+3+…+f(n)<n

(1+f(n))f(n)/2<n

解得时间复杂度为O(n^(1/2) )

a=i++，这个运算的意思是先把i的值赋予a，然后在执行i=i+1；  
a=++i，这个的意思是先执行i=i+1，然后在把i的值赋予a；  
  
4.下面说法错误的是 D  
A 某算法的时间复杂度为O( n 2 n^2 n2)，表明该算法的执行时间与 n 2 n^2 n2成正比  
B 在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O( n 2 n^2 n2)算法  
C 所谓时间复杂度是指**最坏情况下，估算算法执行时间的一个上界**  
D **算法原地工作的含义是指不需要任何额外的辅助空间**

时间复杂度：一般总是考虑在最坏情况下的时间复杂度，以保证算法的运行时间不会比它更长，即它是最坏情况下估算算法执行时间的一个上界。  
  
算法的时间复杂度只与规模相关吗？

算法的时间复杂度不仅与问题的规模相关，还与输入实例中的初始状态有关。但在最坏的情况下，其时间复杂度就是只与求解问题的规模相关的。我们在讨论时间复杂度时，一般就是以最坏情况下的时间复  
杂度为准的。

算法原地工作是指算法所需的辅助空间是常量。  
5.下面算法将一维数组a中的n个数逆序存放到原数组中，空间复杂度为()。

for(i=0;i<n/2;i++){
        
    t=a[i];
    a[i]=a[n-i-1];
    a[n-i-1]=t}

该算法仅需要借助一个变量t，与问题规模n的大小无关，所以其空间复杂度为O(1)

很值得看的理解：  
[时间复杂度和空间复杂度计算][Link 4]  
[时间复杂度分析（含王道绪论习题）][Link 5]

6.以下关系式中，错误的是 D![在这里插入图片描述][84b01b8fbbd94a2a80f23636c08a0d06.png]  
A f(n) =O(g(n))  
B g(n) = O(f(n))  
C h(n) = O( n 2 n^2 n2)  
D h(n) = O(nlog2n)

已知f(n)=O(g(n)),则必能推出g(n)=O(f(n))

7.![在这里插入图片描述][637cacc713b546bea03bf4dd6af84484.png]  
A.O(1) B.O(n) C.O( n − 1 n^\{-1\} n−1) D.O( n 2 n^2 n2)  
答案选B n趋与无穷，f(n)/n为常数

8.设n是描述问题规模的非负整数，下列程序段的时间复杂度是 B

x=0;
    while(n>=(x+1)*(x+1))
    x=x+1;

A.O(logn) B.O( n 1 / 2 n^1/2 n1/2) C.O(n) D.O( n 2 n^2 n2)

9.下列程序段的时间复杂度是

int sum = 0;
    for(int i=1;i<n;i*=2)
       for (int j=0;j<i;j++)
       sum++;

A.O(logn) B.O(n) C.O(nlogn) D.O( n 2 n^2 n2)  
i = 1,2,4,8,…, 2 k − 1 2^\{k-1\} 2k−1（ 2 k − 1 2^\{k-1\} 2k−1<n)  
T = 1+2+4+8+…+ 2 k − 1 2^\{k-1\} 2k−1= 2 k 2^k 2k\-1  
n<T<2n，时间复杂度为O(n)

### 6 时间复杂度计算方法（一、二、三层循环） ###

![在这里插入图片描述][fef93d4f3b2d4db59ef6f8eca6807279.png]  
![在这里插入图片描述][5142dc1637b1447fb4d1bf7b45f5fb24.png]  
![在这里插入图片描述][a59309aa7eed4e5ea9a5e8682537da42.png]

[Link 1]: https://blog.csdn.net/CltCj/article/details/121365905
[Link 2]: https://blog.csdn.net/gao_zhennan/article/details/107616650
[Link 3]: https://baijiahao.baidu.com/s?id=1637101416424485356
[5db872b5b6784715a09353c1bdb948ed.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/3a554960df2543159ecbfeb47c427a9a.png
[Link 4]: https://blog.csdn.net/m0_58761900/article/details/124250221
[Link 5]: https://blog.csdn.net/qq_43606914/article/details/107633537
[84b01b8fbbd94a2a80f23636c08a0d06.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/0da119483d014f16a9632a0d02802ef8.png
[637cacc713b546bea03bf4dd6af84484.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/0484d1dd97a2416a901b3303a9dcc0ec.png
[fef93d4f3b2d4db59ef6f8eca6807279.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/46ea8d1df57c4607ba6c62439ee78501.png
[5142dc1637b1447fb4d1bf7b45f5fb24.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/d7e8b2edecfa461fb46271ad25c26b32.png
[a59309aa7eed4e5ea9a5e8682537da42.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/e2355d23c65443b1a019f52876c728d2.png