📄 第1章 绪论.htm
字号:
<P class=MsoNormal><SPAN lang=EN-US
style="mso-bidi-font-size: 10.5pt; mso-fareast-font-family: 黑体"><o:p> </o:p></SPAN></P></TD></TR></TBODY></TABLE>
<P class=MsoNormal
style="MARGIN-LEFT: 11.4pt; TEXT-INDENT: -11.4pt; mso-char-indent-count: -1.0"><SPAN
lang=EN-US
style="FONT-FAMILY: 黑体; mso-hansi-font-family: 宋体; mso-bidi-font-size: 10.5pt"><o:p> </o:p></SPAN></P>
<P class=MsoNormal
style="MARGIN-LEFT: 11.4pt; TEXT-INDENT: -11.4pt; mso-char-indent-count: -1.0"><SPAN
style="FONT-FAMILY: 黑体; mso-hansi-font-family: 宋体; mso-bidi-font-size: 10.5pt">三．填空题<SPAN
lang=EN-US><o:p></o:p></SPAN></SPAN></P>
<P class=MsoNormal style="TEXT-INDENT: 22.8pt; mso-char-indent-count: 2.0"><SPAN
lang=EN-US style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt">1</SPAN><SPAN
style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt">．数据元素<SPAN lang=EN-US><SPAN
style="mso-spacerun: yes"> </SPAN></SPAN>数据元素间关系 <SPAN
lang=EN-US><SPAN
style="mso-spacerun: yes"> </SPAN>2</SPAN>．集合<SPAN
lang=EN-US><SPAN style="mso-spacerun: yes"> </SPAN></SPAN>线性结构<SPAN
lang=EN-US><SPAN style="mso-spacerun: yes"> </SPAN></SPAN>树形结构<SPAN
lang=EN-US><SPAN style="mso-spacerun: yes">
</SPAN></SPAN>图状结构或网状结构。<SPAN lang=EN-US><o:p></o:p></SPAN></SPAN></P>
<P class=MsoNormal style="TEXT-INDENT: 22.8pt; mso-char-indent-count: 2.0"><SPAN
lang=EN-US style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt">3</SPAN><SPAN
style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt">．数据的组织形式，即数据元素之间逻辑关系的总体。而逻辑关系是指数据元素之间的关联方式或称“邻接关系”。<SPAN
lang=EN-US><o:p></o:p></SPAN></SPAN></P>
<P class=MsoNormal style="TEXT-INDENT: 22.8pt; mso-char-indent-count: 2.0"><SPAN
lang=EN-US style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt">4</SPAN><SPAN
style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt">．表示（又称映像）。<SPAN
lang=EN-US><SPAN style="mso-spacerun: yes">
</SPAN>5</SPAN>．（<SPAN lang=EN-US>1</SPAN>）逻辑特性<SPAN lang=EN-US><SPAN
style="mso-spacerun: yes"> </SPAN></SPAN>（<SPAN
lang=EN-US>2</SPAN>）在计算机内部如何表示和实现<SPAN lang=EN-US><SPAN
style="mso-spacerun: yes"> </SPAN></SPAN>（<SPAN
lang=EN-US>3</SPAN>）数学特性。<SPAN lang=EN-US><o:p></o:p></SPAN></SPAN></P>
<P class=MsoNormal style="TEXT-INDENT: 22.8pt; mso-char-indent-count: 2.0"><SPAN
lang=EN-US style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt">6</SPAN><SPAN
style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt">．算法的时间复杂度和空间复杂度。<SPAN
lang=EN-US>7</SPAN>．（<SPAN lang=EN-US>1</SPAN>）逻辑结构（<SPAN
lang=EN-US>2</SPAN>）物理结构（<SPAN lang=EN-US>3</SPAN>）操作（运算）（<SPAN
lang=EN-US>4</SPAN>）算法。<SPAN lang=EN-US><o:p></o:p></SPAN></SPAN></P>
<P class=MsoNormal style="TEXT-INDENT: 22.8pt; mso-char-indent-count: 2.0"><SPAN
lang=EN-US style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt">8</SPAN><SPAN
style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt">．（<SPAN
lang=EN-US>1</SPAN>）有穷性<SPAN lang=EN-US><SPAN style="mso-spacerun: yes">
</SPAN></SPAN>（<SPAN lang=EN-US>2</SPAN>）确定性 （<SPAN
lang=EN-US>3</SPAN>）可行性。<SPAN lang=EN-US><o:p></o:p></SPAN></SPAN></P>
<P class=MsoNormal style="TEXT-INDENT: 22.8pt; mso-char-indent-count: 2.0"><SPAN
lang=EN-US style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt">9</SPAN><SPAN
style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt">．（<SPAN
lang=EN-US>1</SPAN>）<SPAN lang=EN-US>n+1<SPAN style="mso-spacerun: yes">
</SPAN></SPAN>（<SPAN lang=EN-US>2</SPAN>）<SPAN lang=EN-US>n<SPAN
style="mso-spacerun: yes"> </SPAN></SPAN>（<SPAN lang=EN-US>3</SPAN>）<SPAN
lang=EN-US>n(n+3)/2<SPAN style="mso-spacerun: yes"> </SPAN><SPAN
style="mso-spacerun: yes"> </SPAN></SPAN>（<SPAN lang=EN-US>4</SPAN>）<SPAN
lang=EN-US>n(n+1)/2</SPAN>。<SPAN lang=EN-US><o:p></o:p></SPAN></SPAN></P>
<P class=MsoNormal style="TEXT-INDENT: 22.8pt; mso-char-indent-count: 2.0"><SPAN
lang=EN-US style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt">10</SPAN><SPAN
style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt">．<SPAN
lang=EN-US>1+</SPAN>（<SPAN lang=EN-US>1+2++</SPAN>（<SPAN
lang=EN-US>1+2+3</SPAN>）<SPAN lang=EN-US>+</SPAN>…<SPAN
lang=EN-US>+</SPAN>（<SPAN lang=EN-US>1+2+…+n</SPAN>）<SPAN
lang=EN-US>=n(n+1)(n+2)/6<SPAN style="mso-spacerun: yes">
</SPAN>O(n<SUP>3</SUP>)<SUB><o:p></o:p></SUB></SPAN></SPAN></P>
<P class=MsoNormal style="TEXT-INDENT: 22.8pt; mso-char-indent-count: 2.0"><SPAN
lang=EN-US style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt">11.
log<SUB>2</SUB>n<SPAN style="mso-spacerun: yes">
</SPAN>12. nlog<SUB>2</SUB>n<SPAN
style="mso-spacerun: yes"> </SPAN>13.
log<SUB>2</SUB>n<SUP>2<SPAN
style="mso-spacerun: yes">
</SPAN></SUP>14. (n+3)(n-2)/2<SPAN
style="mso-spacerun: yes"> </SPAN>15.
O(n)<o:p></o:p></SPAN></P>
<P class=MsoNormal
style="MARGIN-LEFT: 40.8pt; TEXT-INDENT: -18pt; mso-list: l1 level1 lfo10; tab-stops: list 40.8pt"><![if !supportLists]><SPAN
lang=EN-US
style="FONT-FAMILY: 宋体; mso-bidi-font-family: 宋体; mso-bidi-font-size: 10.5pt"><SPAN
style="mso-list: Ignore">16.<SPAN style="FONT: 7pt 'Times New Roman'">
</SPAN></SPAN></SPAN><![endif]><SPAN lang=EN-US
style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt"><SPAN
style="mso-spacerun: yes"> </SPAN></SPAN><SPAN
style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt">①<SPAN lang=EN-US> (1)1<SPAN
style="mso-spacerun: yes"> </SPAN>(2)1<SPAN
style="mso-spacerun: yes"> </SPAN>(3)f(m,n-1)<SPAN
style="mso-spacerun: yes"> </SPAN>(4)n<SPAN
style="mso-spacerun: yes"> </SPAN></SPAN>②<SPAN lang=EN-US>
9<SPAN style="mso-spacerun: yes"> </SPAN><SPAN
style="mso-spacerun: yes"> </SPAN><SPAN
style="mso-spacerun: yes"> </SPAN>17.
n(n-1)/2</SPAN></SPAN><SPAN lang=EN-US
style="mso-bidi-font-size: 10.5pt"><o:p></o:p></SPAN></P>
<P class=MsoNormal><SPAN lang=EN-US
style="mso-bidi-font-size: 10.5pt"><o:p> </o:p></SPAN></P>
<P class=MsoNormal><SPAN
style="FONT-FAMILY: 黑体; mso-hansi-font-family: 宋体; mso-bidi-font-size: 10.5pt">四．应用题<SPAN
lang=EN-US><o:p></o:p></SPAN></SPAN></P>
<P class=MsoNormal
style="MARGIN-LEFT: 22.8pt; mso-para-margin-left: 2.0gd"><SPAN lang=EN-US
style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt">1</SPAN><SPAN
style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt">．数据结构是一门研究在非数值计算的程序设计问题中，计算机的操作对象及对象间的关系和施加于对象的操作等的学科。<SPAN
lang=EN-US><o:p></o:p></SPAN></SPAN></P>
<P class=MsoNormal style="TEXT-INDENT: 22.8pt; mso-char-indent-count: 2.0"><SPAN
lang=EN-US style="mso-bidi-font-size: 10.5pt">2</SPAN><SPAN
style="FONT-FAMILY: 宋体; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-size: 10.5pt; mso-ascii-font-family: 'Times New Roman'">．四种表示方法</SPAN><SPAN
lang=EN-US style="mso-bidi-font-size: 10.5pt"><o:p></o:p></SPAN></P>
<P class=MsoNormal
style="TEXT-INDENT: 11.15pt; mso-char-indent-count: .98"><SPAN
style="FONT-FAMILY: 宋体; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-size: 10.5pt; mso-ascii-font-family: 'Times New Roman'">（</SPAN><SPAN
lang=EN-US style="mso-bidi-font-size: 10.5pt">1</SPAN><SPAN
style="FONT-FAMILY: 宋体; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-size: 10.5pt; mso-ascii-font-family: 'Times New Roman'">）顺序存储方式。数据元素顺序存放，每个存储结点只含一个元素。存储位置反映数据元素间的逻辑关系。存储密度大，但有些操作（如插入、删除）效率较差。</SPAN><SPAN
lang=EN-US style="mso-bidi-font-size: 10.5pt"><o:p></o:p></SPAN></P>
<P class=MsoNormal
style="TEXT-INDENT: 11.15pt; mso-char-indent-count: .98"><SPAN
style="FONT-FAMILY: 宋体; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-size: 10.5pt; mso-ascii-font-family: 'Times New Roman'">（</SPAN><SPAN
lang=EN-US style="mso-bidi-font-size: 10.5pt">2</SPAN><SPAN
style="FONT-FAMILY: 宋体; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-size: 10.5pt; mso-ascii-font-family: 'Times New Roman'">）链式存储方式。每个存储结点除包含数据元素信息外还包含一组（至少一个）指针。指针反映数据元素间的逻辑关系。这种方式不要求存储空间连续，便于动态操作（如插入、删除等），但存储空间开销大（用于指针），另外不能折半查找等。</SPAN><SPAN
lang=EN-US style="mso-bidi-font-size: 10.5pt"><o:p></o:p></SPAN></P>
<P class=MsoNormal
style="TEXT-INDENT: 11.15pt; mso-char-indent-count: .98"><SPAN
style="FONT-FAMILY: 宋体; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-size: 10.5pt; mso-ascii-font-family: 'Times New Roman'">（</SPAN><SPAN
lang=EN-US style="mso-bidi-font-size: 10.5pt">3</SPAN><SPAN
style="FONT-FAMILY: 宋体; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-size: 10.5pt; mso-ascii-font-family: 'Times New Roman'">）索引存储方式。除数据元素存储在一地址连续的内存空间外，尚需建立一个索引表，索引表中索引指示存储结点的存储位置（下标）或存储区间端点（下标），兼有静态和动态特性。</SPAN><SPAN
lang=EN-US style="mso-bidi-font-size: 10.5pt"><o:p></o:p></SPAN></P>
<P class=MsoNormal
style="TEXT-INDENT: 11.15pt; mso-char-indent-count: .98"><SPAN
style="FONT-FAMILY: 宋体; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-size: 10.5pt; mso-ascii-font-family: 'Times New Roman'">（</SPAN><SPAN
lang=EN-US style="mso-bidi-font-size: 10.5pt">4</SPAN><SPAN
style="FONT-FAMILY: 宋体; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-size: 10.5pt; mso-ascii-font-family: 'Times New Roman'">）散列存储方式。通过散列函数和解决冲突的方法，将关键字散列在连续的有限的地址空间内，并将散列函数的值解释成关键字所在元素的存储地址，这种存储方式称为散列存储。其特点是存取速度快，只能按关键字随机存取，不能顺序存取，也不能折半存取。</SPAN><SPAN
lang=EN-US style="mso-bidi-font-size: 10.5pt"><o:p></o:p></SPAN></P>
<P class=MsoNormal style="TEXT-INDENT: 22.8pt; mso-char-indent-count: 2.0"><SPAN
lang=EN-US style="mso-bidi-font-size: 10.5pt">3</SPAN><SPAN
style="FONT-FAMILY: 宋体; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-size: 10.5pt; mso-ascii-font-family: 'Times New Roman'">．数据类型是程序设计语言中的一个概念，它是一个值的集合和操作的集合。如</SPAN><SPAN
lang=EN-US style="mso-bidi-font-size: 10.5pt">C</SPAN><SPAN
style="FONT-FAMILY: 宋体; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-size: 10.5pt; mso-ascii-font-family: 'Times New Roman'">语言中的整型、实型、字符型等。整型值的范围（对具体机器都应有整数范围），其操作有加、减、乘、除、求余等。实际上数据类型是厂家提供给用户的已实现了的数据结构。“抽象数据类型（</SPAN><SPAN
lang=EN-US style="mso-bidi-font-size: 10.5pt">ADT</SPAN><SPAN
style="FONT-FAMILY: 宋体; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-size: 10.5pt; mso-ascii-font-family: 'Times New Roman'">）”指一个数学模型及定义在该模型上的一组操作。“抽象”的意义在于数据类型的数学抽象特性。抽象数据类型的定义仅取决于它的逻辑特性，而与其在计算机内部如何表示和实现无关。无论其内部结构如何变化，只要它的数学特性不变就不影响它的外部使用。抽象数据类型和数据类型实质上是一个概念。此外，抽象数据类型的范围更广，它已不再局限于机器已定义和实现的数据类型，还包括用户在设计软件系统时自行定义的数据类型。使用抽象数据类型定义的软件模块含定义、表示和实现三部分，封装在一起，对用户透明（提供接口），而不必了解实现细节。抽象数据类型的出现使程序设计不再是“艺术”，而是向“科学”迈进了一步。</SPAN><SPAN
lang=EN-US style="mso-bidi-font-size: 10.5pt"><o:p></o:p></SPAN></P>
<P class=MsoNormal
style="TEXT-INDENT: 22.8pt; tab-stops: 45.0pt; mso-char-indent-count: 2.0"><SPAN
lang=EN-US style="mso-bidi-font-size: 10.5pt">4</SPAN><SPAN
style="FONT-FAMILY: 宋体; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-size: 10.5pt; mso-ascii-font-family: 'Times New Roman'">．（</SPAN><SPAN
lang=EN-US style="mso-bidi-font-size: 10.5pt">1</SPAN><SPAN
style="FONT-FAMILY: 宋体; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-size: 10.5pt; mso-ascii-font-family: 'Times New Roman'">）数据的逻辑结构反映数据元素之间的逻辑关系（即数据元素之间的关联方式或“邻接关系”），数据的存储结构是数据结构在计算机中的表示，包括数据元素的表示及其关系的表示。数据的运算是对数据定义的一组操作，运算是定义在逻辑结构上的，和存储结构无关，而运算的实现则是依赖于存储结构。</SPAN><SPAN
lang=EN-US style="mso-bidi-font-size: 10.5pt"><o:p></o:p></SPAN></P>
<P class=MsoNormal
style="MARGIN-LEFT: 0.05pt; TEXT-INDENT: -0.05pt; tab-stops: 45.0pt"><SPAN
lang=EN-US style="mso-bidi-font-size: 10.5pt"><SPAN
style="mso-spacerun: yes"> </SPAN></SPAN><SPAN
style="FONT-FAMILY: 宋体; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-size: 10.5pt; mso-ascii-font-family: 'Times New Roman'">（</SPAN><SPAN
lang=EN-US style="mso-bidi-font-size: 10.5pt">2</SPAN><SPAN
style="FONT-FAMILY: 宋体; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-size: 10.5pt; mso-ascii-font-family: 'Times New Roman'">）逻辑结构相同但存储不同，可以是不同的数据结构。例如，线性表的逻辑结构属于线性结构，采用顺序存储结构为顺序表，而采用链式存储结构称为线性链表。</SPAN><SPAN
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -