数据结构原理与应用答案清华大学版

数据结构与算法

一 选择题

1．算法的计算量的大小称为计算的（ B ）。

A．效率 B. 复杂性 C. 现实性 D. 难度

2．下面说法正确的是（ C ）

(1）算法原地工作的含义是指不需要任何额外的辅助空间

（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2)的算法 （3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 （4）同一个算法，实现语言的级别越高，执行效率就越低

A．(1) B.(1),(2) C.(1),(4) D.(3)

3. 连续存储设计时，存储单元的地址（ A ）。

A．一定连续 B．一定不连续 C．不一定连续 D．部分连续，部分不连续

4. 下述哪一条是顺序存储结构的优点？（A ）

A．存储密度大 B．插入运算方便 C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示

5．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ A ）存储方式最节省时间。

A．顺序表 B．双链表 C．带头结点的双循环链表

第三章 栈和队列

栈和队列是在软件设计中常用的两种数据结构，它们的逻辑结构和线性表相同。其特点在于运算受到了限制：栈按“后进先出”的规则进行操作，队按“先进先出”的规则进行操作，故称运算受限制的线性表。

3．1 栈

３.１.１ 栈的定义及基本运算

栈是限制在表的一端进行插入和删除的线性表。允许插入、删除的这一端称为栈顶，另一个固定端称为栈底。当表中没有元素时称为空栈。如图3.1.1所示栈中有三个元素，进栈的顺序是a1、a2、a3，当需要出栈时其顺序为a3、a2、a1，所以栈又称为后进先出的线性表（Last In First Out），简称 LIFO表。

入栈 top

a3 a2 a1 出栈

图3.1 栈示意图

在日常生活中，有很多后进先出的例子，读者可以列举。在程序设计中，常常需要栈这样的数据结构，使得与保存数据时相反顺序来使用这些数据，这时就需要用一个栈来实现。对于栈，常做的基本运算有： ⑴ 栈初始化：Init_Stack(s)

初始条件：栈s不存在 操作结果：构造了一个空栈。 ⑵ 判栈空：Empty_Stack(s)

初始条件：栈s已存在

操作结果：若s为空栈返回为1，否则返回为0。 ⑶ 入栈： Push_Stac

习题1

一、单项选择题

A1.数据结构是指（）。

A.数据元素的组织形式

B.数据类型

C.数据存储结构

D.数据定义

C2.数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（）。

A.存储结构

B.逻辑结构

C.链式存储结构

D.顺序存储结构

D3.树形结构是数据元素之间存在一种（）。

A.一对一关系

B.多对多关系

C.多对一关系

D.一对多关系

B4.设语句x++的时间是单位时间，则以下语句的时间复杂度为（）。

for(i=1; i<=n; i++)

for(j=i; j<=n; j++)

x++;

A.O(1)

B.O(2n)

C.O(n)

D.O(3n)

CA5.算法分析的目的是（1），算法分析的两个主要方面是（2）。

（1） A.找出数据结构的合理性 B.研究算法中的输入和输出关系

C.分析算法的效率以求改进

D.分析算法的易懂性和文档性

（2） A.空间复杂度和时间复杂度 B.正确性和简明性

C.可读性和文档性

D.数据复杂性和程序复杂性

6.计算机算法指的是（1），它具备输入，输出和（2）等五个特性。

（1） A.计算方法 B.排序方法

C.解决问题的有限运算序列

D.调度方法

（2） A.可行性，可移植性和可扩充性 B.可行性，确

.

1-1什么是数据? 它与信息是什么关系?

【解答】

什么是信息？广义地讲，信息就是消息。宇宙三要素（物质、能量、信息）之一。它是现实世界各种事物在人们头脑中的反映。此外，人们通过科学仪器能够认识到的也是信息。信息的特征为：可识别、可存储、可变换、可处理、可传递、可再生、可压缩、可利用、可共享。

什么是数据？因为信息的表现形式十分广泛，许多信息在计算机中不方便存储和处理，例如，一个大楼中4部电梯在软件控制下调度和运行的状态、一个商店中商品的在库明细表等，必须将它们转换成数据才能很方便地在计算机中存储、处理、变换。因此，数据(data)是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。在计算机中，信息必须以数据的形式出现。

1-2什么是数据结构? 有关数据结构的讨论涉及哪三个方面?

【解答】

数据结构是指数据以及相互之间的关系。记为：数据结构= { D, R }。其中，D是某一数据对象，R是该对象中所有数据成员之间的关系的有限集合。

有关数据结构的讨论一般涉及以下三方面的内容：

①数据成员以及它们相互之间的逻辑关系，也称为数据的逻辑结构，简称为数据结构；

②数据成员极其关系在计算机存储器内的存储表示，也称为数据

第三章

N=>D=> {0,1,2,3,4,5,6,7,8,9} N=>ND=>NDD

L={a |a(0|1|3..|9)n

且 n>=1}

(0|1|3..|9)n

且 n>=1

{ab,}

anbn

n>=1

第6题.

(1) <表达式> => <项> => <因子> => i

(2) <表达式> => <项> => <因子> => (<表达式>) => (<项>)

=> (<因子>)=>(i)

(3) <表达式> => <项> => <项>*<因子> => <因子>*<因子> =i*i

(4) <表达式> => <表达式> + <项> => <项>+<项> => <项>*<因子>+<项>

=> <因子>*<因子>+<项> => <因子>*<因子>+<因子> = i*i+i

(5) <表达式> => <表达式>+<项>=><项>+<项> => <因子>+<项>=i+<项> => i+<因子> => i+(<表达式>) => i+(<表达式>+<项>)

=> i+(<因子>+<因子>)

=> i+(i+i)

(6) <表达式> => <表达式>+<项>

6.3 典型例题

一、单项选择题

[例6-1] 数据结构用集合的观点可以表示为一个二元组DS＝(D，R)。其中，D是 ( ① )的有穷集合，R是D上( ② )的有限集合。

①A. 算法 B. 数据元素 C. 数据操作 D. 逻辑结构 ②A. 操作 B. 映像 C. 存储 D．关系

解析：由数据结构的集合形式化定义可知，本题答案为：①B； ②D。 [例6-2] 数据的常用存储结构中不包括( )。

A．顺序存储结构 B．线性结构 C．索引存储结构 D．散列存储结构 解析：数据通常有四种基本的存储方法，即顺序存储方法、链式存储方法、索引存储 方法和散列存储方法。由此可知，本题答案为：B。

[例6-3] 算法指的是( ① )，它必须具备( ② )这三个特性。

①A．计算方法 B．排序方法 C．解决问题的步骤序列 D．调度方法 ②A．可执行性、可移植性、可扩充性 B．可执行性、确定性、有穷性 C．确定性、有穷性、稳定性

6.3 典型例题

一、单项选择题

[例6-1] 数据结构用集合的观点可以表示为一个二元组DS＝(D，R)。其中，D是 ( ① )的有穷集合，R是D上( ② )的有限集合。

①A. 算法 B. 数据元素 C. 数据操作 D. 逻辑结构 ②A. 操作 B. 映像 C. 存储 D．关系

解析：由数据结构的集合形式化定义可知，本题答案为：①B； ②D。 [例6-2] 数据的常用存储结构中不包括( )。

A．顺序存储结构 B．线性结构 C．索引存储结构 D．散列存储结构 解析：数据通常有四种基本的存储方法，即顺序存储方法、链式存储方法、索引存储 方法和散列存储方法。由此可知，本题答案为：B。

[例6-3] 算法指的是( ① )，它必须具备( ② )这三个特性。

①A．计算方法 B．排序方法 C．解决问题的步骤序列 D．调度方法 ②A．可执行性、可移植性、可扩充性 B．可执行性、确定性、有穷性 C．确定性、有穷性、稳定性

清华大学第二版编译原理答案

《编译原理》课后习题答案第一章 第 4 题

对下列错误信息，请指出可能是编译的哪个阶段（词法分析、语法分析、语义分析、 代码生成）报告的。 （1） else 没有匹配的if （2） 数组下标越界

（3） 使用的函数没有定义 （4） 在数中出现非数字字符 答案：

（1） 语法分析 （2） 语义分析 （3） 语法分析 （4） 词法分析

《编译原理》课后习题答案第三章 第1 题

文法G＝({A,B,S},{a,b,c},P,S)其中P 为： S→Ac|aB A→ab B→bc

写出L(G[S])的全部元素。 答案：

L(G[S])={abc}

第2 题

文法G[N]为： N→D|ND

D→0|1|2|3|4|5|6|7|8|9 G[N]的语言是什么？ 答案:

G[N]的语言是V+。V={0,1,2,3,4,5,6,7,8,9} N=>ND=>NDD.... =>NDDDD...D=>D......D

或者：允许0 开头的非负整数？ 第３题

为只包含数字、加号和减号的表达式，例如9-2＋5，3-1，７等构造一个文法。答案： G[S]:

S->S+D|S-D

高电压工程课后答案 1.1空气作为绝缘的优缺点如何？

答：优点：空气从大气中取得，制取方便，廉价，简易，具有较强的自恢复能力。缺点：空气比重较大，摩擦损失大，导热散热能力差。空气污染大，易使绝缘物脏污，且空气是助燃物当仿生电流时，易烧毁绝缘，电晕放电时有臭氧生成，对绝缘有破坏作用。 1.2为什么碰撞电离主要是由电子而不是离子引起？

答：由于电子质量极小，在和气体分子发生弹性碰撞时，几乎不损失动能，从而在电场中继续积累动能，此外，一旦和分子碰撞，无论电离与否均将损失动能，和电子相比，离子积累足够造成碰撞电离能量的可能性很小。 1.5负离子怎样形成，对气体放电有何作用？

答：在气体放电过程中，有时电子和气体分子碰撞，非但没有电离出新电子，碰撞电子反而别分子吸附形成了负离子，离子的电离能力不如电子，电子为分子俘获而形成负离子后电离能力大减，因此在气体放电过程中，负离子的形成起着阻碍放电的作用。

1.7非自持放电和自持放电主要差别是什么？

答：非自持放电必须要有光照，且外施电压要小于击穿电压，自持放电是一种不依赖外界电离条件，仅由外施电压作用即可维持的一种气体放电。 1.13电晕会产生哪些效应，工程上常用哪些防晕措施？

答：电晕

《编译原理》课后习题

第 1 章引论

第 1 题解释下列术语：

（1） 编译程序：如果源语言为高级语言，目标语言为某台计算机上的汇编语言或机器语 言，则此翻译程序称为编译程序。

（2） 源程序：源语言编写的程序称为源程序。

（3） 目标程序：目标语言书写的程序称为目标程序。

（4） 编译程序的前端：它由这样一些阶段组成：这些阶段的工作主要依赖于源语言而与 目标机无关。通常前端包括词法分析、语法分析、语义分析和中间代码生成这些阶 段，某些优化工作也可在前端做，也包括与前端每个阶段相关的出错处理工作和符 号表管理等工作。

（5） 后端：指那些依赖于目标机而一般不依赖源语言，只与中间代码有关的那些阶段， 即目标代码生成，以及相关出错处理和符号表操作。

（6） 遍：是对源程序或其等价的中间语言程序从头到尾扫视并完成规定任务的过程。 第 2 题

一个典型的编译程序通常由哪些部分组成？各部分的主要功能是什么？并画出编译程 序的总体结构图。

答案：一个典型的编译程序通常包含 8 个组成部分，它们是词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、中间代码优化程序、目标代码生成程序、表格管理程序和错误处理程序。其各部分的主要功能简述如下。

词法分析