数据结构--第一章

川长思鸟来 2022-12-30 10:35 138阅读 0赞

1. 简述逻辑结构与存储结构的关系。

就我个人理解而言，逻辑结构，软件层面上看的话，用特殊的容器将数据按序保存起来的一种结构，如链表、数组、队列等。存储结构，即真实的物理存储结构，指硬件上。

网上摘抄的回答：

> 存储结构是逻辑结构的存储映像，逻辑结构指的是数据间的关系，它又分为线性结构和非线性结构,这两者并不冲突。一个指的是数据之间的关系，而另一个指这种关系在计算机中的表现形式。
> 
> 两者的区别就在于给他们定义的特殊操作，它们都有”出“和”入“两种操作，一个是“先进先出”，而一个是“后进先出”。一种逻辑结构在计算机里可以用不同的存储结构实现。比如逻辑结构中简单的线性结构，可以用数组（顺序存储）或单向链表（链接存储）来实现。
> 
> 逻辑结构：指各数据元素之间的逻辑关系。
> 
> 存储结构：就是数据的逻辑结构用计算机语言的实现。
> 
> 扩展资料：
> 
> 1、逻辑结构是指数据之间的相互关系。通常分为四类结构：集合：结构中的数据元素除了同属于一种类型外，别无其它关系。线性结构：结构中的数据元素之间存在一对一的关系。树型结构：结构中的数据元素之间存在一对多的关系。图状结构：结构中的数据元素之间存在多对多的关系。
> 
> 2、存储结构是指数据结构在计算机中的表示，又称为数据的物理结构。通常由四种基本的存储方法实现：顺序存储方式。数据元素顺序存放，每个存储结点只含一个元素。存储位置反映数据元素间的逻辑关系。存储密度大。但有些操作（如插入、删除）效率较差。数据元素间的逻辑关系。这种方式不要求存储空间连续，便于动态操作（如插入、删除等），但存储空间开销大（用于指针），另外不能折半查找等。索引存储方式。除数据元素存储在一组地址连续的内存空间外，还需建立一个索引表，索引表中索引指示存储结点的存储位置（下标）或存储区间端点（下标）。散列存储方式。通过散列函数和解决冲突的方法，将关键字散列在连续的有限的地址空间内，并将散列函数的值解释成关键字所在元素的存储地址。其特点是存取速度快，只能按关键字随机存取，不能顺序存取，也不能折半存取。

2. 度量一个算法的执行时间通常有几种方法？各有何优缺点？

<table style="width:500px;"> 
 <tbody> 
 <tr> 
 <td>&nbsp;</td> 
 <td>大O表示法</td> 
 <td>Ω表示法</td> 
 <td>θ表示法</td> 
 </tr> 
 <tr> 
 <td>定义</td> 
 <td>如果存在证书 c 和 N，使得对任意的 n ≥ N，都有 f(n) ≤ cg(n)，则称 f(n) 在集合 O(g(n)) 中，或简称 f(n) 是 O(g(n)) 的。</td> 
 <td>如果存在整数 c 和 N，使得对所以的 n ≥ N，都有 f(n) ≥ cg(n)，则称函数 f(n) 在集合 Ω(g(n)) 中，或简称 f(n) 是 Ω(g(n)) 的。</td> 
 <td> 存在正常数<img alt="\small c_{1}" src="https://private.codecogs.com/gif.latex?%5Csmall%20c_%7B1%7D">&nbsp; 和&nbsp;<img alt="\small c_{2}" src="https://private.codecogs.com/gif.latex?%5Csmall%20c_%7B2%7D">&nbsp;以及正整数 N，使得对于任意的正整数 n &gt; N 有下列两不等式同时成立：<img alt="\small c_{1}g(n)" src="https://private.codecogs.com/gif.latex?%5Csmall%20c_%7B1%7Dg%28n%29">&nbsp;≤ f(n) ≤&nbsp;<img alt="\small c_{2}g(n)" src="https://private.codecogs.com/gif.latex?%5Csmall%20c_%7B2%7Dg%28n%29"> &nbsp; </td> 
 </tr> 
 <tr> 
 <td>优点</td> 
 <td>提供了一种表达函数增长率上限的方法。表达了一种算法最多会差到何种程度。</td> 
 <td>提供了一种表达函数增长率下限的方法。表达了一种算法最多会好到何种程度。</td> 
 <td>即给出了函数增长率的上限，也给出了函数增长率的下限。</td> 
 </tr> 
 <tr> 
 <td>缺点</td> 
 <td>不能给出函数增长率的下限。</td> 
 <td>不能给出函数增长率的上限。</td> 
 <td>&nbsp;</td> 
 </tr> 
 <tr> 
 <td>特性</td> 
 <td> * 如果函数 f(n) 是 O(g(n)) 的，g(n) 是 O(h(n)) 的，则 f(n) 是 O(h(n)) 的。 * 如果函数 f(n) 是 O(h(n)) 的， g(n) 是 O(h(n)) 的，则 f(n) + g(n) 是 O(h(n)) 的。 * 函数 a<img alt="n^{k}" src="https://private.codecogs.com/gif.latex?n%5E%7Bk%7D">&nbsp;是 O(<img alt="n^{k}" src="https://private.codecogs.com/gif.latex?n%5E%7Bk%7D">) 的，符号 a 表示不依赖于 n 的任意常数。 * 若 f(n)=cg(n)，则 f(n) 是 O(g(n)) 的。 * 对任何正数 a 和 b，且 b ≠ 1，函数&nbsp;<img alt="\small log_{a}n" src="https://private.codecogs.com/gif.latex?%5Csmall%20log_%7Ba%7Dn">&nbsp;是 O(<img alt="\small log_{b}n" src="https://private.codecogs.com/gif.latex?%5Csmall%20log_%7Bb%7Dn">)的。即任何对数函数无论底数为何值，都具有相同的增长率。 * 对任何正数 a ≠ 1，都有&nbsp;<img alt="\small log_{a}n" src="https://private.codecogs.com/gif.latex?%5Csmall%20log_%7Ba%7Dn">&nbsp;是&nbsp;<img alt="\small log_{2}n" src="https://private.codecogs.com/gif.latex?%5Csmall%20log_%7B2%7Dn">的。&nbsp;<img alt="\small log_{2}n" src="https://private.codecogs.com/gif.latex?%5Csmall%20log_%7B2%7Dn">&nbsp;简写为&nbsp;<img alt="\small logn" src="https://private.codecogs.com/gif.latex?%5Csmall%20logn">。 g(n) = 1，常数函数，不依赖于数据规模 n。 g(n) =&nbsp;<img alt="\small logn" src="https://private.codecogs.com/gif.latex?%5Csmall%20logn">，对数函数，比线性函数 n 长得慢。 g(n) = n，线性增长，随时间规模 n 而增长。 g(n) =&nbsp;<img alt="\small n^{2}" src="https://private.codecogs.com/gif.latex?%5Csmall%20n%5E%7B2%7D">，二阶增长，例如：1 + 2 + 3 + ··· + n = n x (n + 1) / 2 g(n) = <img alt="\small nlog(n)" src="https://private.codecogs.com/gif.latex?%5Csmall%20nlog%28n%29">，其增长率的阶数低于二阶，但高于一阶线性。 g(n) =&nbsp;<img alt="\small a^{n}" src="https://private.codecogs.com/gif.latex?%5Csmall%20a%5E%7Bn%7D">，指数增长，随问题规模 n 快速增长。 &nbsp; </td> 
 <td>&nbsp;</td> 
 <td> 例如： f(n) = 100 x&nbsp;<img alt="\small n^{2}" src="https://private.codecogs.com/gif.latex?%5Csmall%20n%5E%7B2%7D">&nbsp;+ 5 x n + 500 &nbsp; 令 g(n) =&nbsp;<img alt="\small n^{2}" src="https://private.codecogs.com/gif.latex?%5Csmall%20n%5E%7B2%7D">，存在常数&nbsp;<img alt="\small c_{1}" src="https://private.codecogs.com/gif.latex?%5Csmall%20c_%7B1%7D">&nbsp;= 100，<img alt="\small c_{2}" src="https://private.codecogs.com/gif.latex?%5Csmall%20c_%7B2%7D">&nbsp;= 105，N =10，当 n &gt; N 时，&nbsp;<img alt="\small c_{1}" src="https://private.codecogs.com/gif.latex?%5Csmall%20c_%7B1%7D">g(n) ≤ f(n) ≤&nbsp;<img alt="\small c_{2}" src="https://private.codecogs.com/gif.latex?%5Csmall%20c_%7B2%7D">g(n)。则 f(n) 为 θ(<img alt="\small n^{2}" src="https://private.codecogs.com/gif.latex?%5Csmall%20n%5E%7B2%7D">) </td> 
 </tr> 
 </tbody> 
</table>

3. 分析下面函数的时间复杂度。

void func(int n)
 {
 int i = 1, k = 100;
 while(i < n)
 {
 k++; i += 2;
 }
 }

单论赋值的话，k++ 等价于 k = k + 1。i += 2 等价于 i = i + 2。 i 和 k 进行初始化，算 2 次。即 while 循环每次有2次赋值操作 。那么算下来就是 2 + 2x(n - 1) 即为 2n，用 大O表示法即为 O(n)。

4. 设 n 是 偶数且有程序段：

for (int i = 1; i <= n; i++)
 {
 if(2 * i <= n)
 {
 for (int j = 2*i; j <= n ; j++)
 {
 y = y + i * j;
 }
 }
 }

则 y=y+i\*j 的执行次数是多少？

分析：

外层循环 for 的执行次数是 n。内层循环中的 for 循环 i值最大是 n/2，即有 n/2 项：

当 i = 1 时，内部 for 循环执行 y=y+i\*j 表达式的次数为 n-1 次。

当 i = 2 时，内部 for 循环执行 y=y+i\*j 表达式的次数为 n-3 次。

当 i = 3 时，内部 for 循环执行 y=y+i\*j 表达式的次数为 n-5 次。

...

当 i = n/2 - 1 时，内部 for 循环执行 y=y+i\*j 表达式的次数为 3 次。

当 i = n/2 时，内部 for 循环执行 y=y+i\*j 表达式的次数为 1 次。

所以当 总共执行的次数是 n-1 + n- 3 + n - 5 + ··· + 3 + 1 = ![\\small \\frac\{n^\{2\}\}\{2\}][small _frac_n_2_2]

5. 将下列函数按它们在![\\small n \\to \\infty][small n _to _infty]时的无穷大阶数，从小到大排列。

![\\small n][small n]，![\\small n-n^\{3\}+7n^\{5\}][small n-n_3_7n_5]，![\\small nlogn][small nlogn]，![\\small 2^\{n/2\}][small 2_n_2]，![\\small n^\{3\}][small n_3]，![\\small logn][small logn]，![\\small n^\{1/2\}+logn][small n_1_2_logn]，![\\small \\left ( 3/2 \\right )^\{n\}][small _left _ 3_2 _right _n]，![\\small n!][small n 1]，![\\small n^\{2\}+logn][small n_2_logn]

这个好办，这些表达式，都是随着n的增长而增长，直接取大数带入算出各个表达式的大小即可。

答案是：![\\small logn][small logn] < ![\\small n^\{1/2\}+logn][small n_1_2_logn] < ![\\small n][small n] < ![\\small nlogn][small nlogn] < ![\\small n^\{2\}+logn][small n_2_logn] < ![\\small n^\{3\}][small n_3] < ![\\small n-n^\{3\}+7n^\{5\}][small n-n_3_7n_5] < ![\\small 2^\{n/2\}][small 2_n_2] < ![\\small \\left ( 3/2 \\right )^\{n\}][small _left _ 3_2 _right _n] < ![\\small n!][small n 1]。

[small _frac_n_2_2]: https://private.codecogs.com/gif.latex?%5Csmall%20%5Cfrac%7Bn%5E%7B2%7D%7D%7B2%7D
[small n _to _infty]: https://private.codecogs.com/gif.latex?%5Csmall%20n%20%5Cto%20%5Cinfty
[small n]: https://private.codecogs.com/gif.latex?%5Csmall%20n
[small n-n_3_7n_5]: https://private.codecogs.com/gif.latex?%5Csmall%20n-n%5E%7B3%7D&plus;7n%5E%7B5%7D
[small nlogn]: https://private.codecogs.com/gif.latex?%5Csmall%20nlogn
[small 2_n_2]: https://private.codecogs.com/gif.latex?%5Csmall%202%5E%7Bn/2%7D
[small n_3]: https://private.codecogs.com/gif.latex?%5Csmall%20n%5E%7B3%7D
[small logn]: https://private.codecogs.com/gif.latex?%5Csmall%20logn
[small n_1_2_logn]: https://private.codecogs.com/gif.latex?%5Csmall%20n%5E%7B1/2%7D&plus;logn
[small _left _ 3_2 _right _n]: https://private.codecogs.com/gif.latex?%5Csmall%20%5Cleft%20%28%203/2%20%5Cright%20%29%5E%7Bn%7D
[small n 1]: https://private.codecogs.com/gif.latex?%5Csmall%20n%21
[small n_2_logn]: https://private.codecogs.com/gif.latex?%5Csmall%20n%5E%7B2%7D&plus;logn