第一章
1.1 什么是信息？信息与数据的区别和联系在何处？
信息定义之一：信息是现实世界中存在的客观实体、现象、关系进行描述的数据。
信息定义之二：信息是经过加工后并对实体的行为产生影响的数据。 与数据的区别和联系： 数据定义：数据是现实世界客观存在的实体或事物的属性值，即指人们听到的事实和看到的景象。
我们把这些数据收集起来，经过处理后，即得到人们需要的信息。 信息和数据的关系可以归结为： 1. 信息是有一定含义的数据。
2. 信息是经过加工（处理）后的数据。 3. 信息是对决策有价值的数据。 1.2 信息有哪些基本属性？
信息的基本属性有： 1. 事实性。 2. 等级性。 3. 可压缩性。 4. 可扩散性。 5. 可传输性。 6. 共享性。
7. 增值性和再生性。 8. 转换性。
1.3 计算机的主要特点是什么？
计算机最主要的特点是： 1. 高速自动的操作功能。 2. 具有记忆的能力。
3. 可以进行各种逻辑判断。 4. 精确高速的计算能力。
1.5 完整的计算机系统应该包括哪几部分？
目前最完整的计算机系统学说认为由五部分组成： 1. 人员 2. 数据 3. 设备 4. 程序 5. 规程
1.6 什么是计算机硬件？什么是计算机软件？
硬件：泛指实际存在的物理设备，包括计算机本身及其外围设备。
微型计算机的硬件系统：主机、外存储器、输入设备、输出设备、微机的系统总线。
软件：是指计算机程序、方法、规则的文档以及在计算机上运行它时所必须的数据。
计算机软件一般分为系统软件和应用软件。
1.8 软件技术发展的几个阶段各有什么特点？它与硬件的关系如何？
1
第一阶段：高级语言阶段
特点：这一时期，编译技术代表了整个软件技术，软件工作者追求的主要
目的是设计和实现在控制结构和数据结构方面表现能力强的高级语言。但在这一时期内，编译系统主要是靠手工编制，自动化程度很低。 硬件关系：此时期计算机的硬件要求仅能用机器指令来编制可运行的程序。 第二阶段：结构程序设计阶段
特点：在程序的正确性方面，提出了结构化程序设计思想使程序的可靠性
提高了。
程序设计方法论方面，提出由顶向下法和自底向上法。使程序模块
化，使问题的复杂性和人的思维统一起来了。
出现了软件生产管理。
硬件关系：磁盘问世，操作系统发展，非数值计算应用发展，通信设备完
善，网络发展，集成电路发展等使软件复杂性增加产生软件危机，在此背景下发展了软件技术。
第三阶段：自动程序设计阶段
特点：向集成化、一体化发展。出现了软件开发环境。程序设计基本方法
进一步改进。
硬件关系：集成电路迅速发展以及高分辨率终端的出现，为个人计算机发
展提供了条件，再加上人工智能、专家系统研究的发展，使程序设计进入成熟期。
第二章
2.1 什么是数据结构？它对算法有什么影响？
数据结构是指同一数据对象中各数据元素间存在的关系。
对算法是影响：算法的实现必须借助程序设计语言中提供的数据类型及其
运算。一个算法的效率往往与数据的表达形式有关，因此数据结构的选择对数据处理的效率起着至关重要的作用。它是算法和程序设计的基本部分，它对程序的质量影响很大。 2.2 何谓算法？它与程序有何区别？
广义地说，为解决一个问题而采取的方法和步骤，就称为“算法”。计算机算法是通过计算机能执行的算法语言来表达的。 和程序的区别：一个程序包括两个方面的内容：
（1）、对数据的描述，即数据结构。 （2）、对操作的描述，即算法。 所以算法是程序的一个要素。
2.3 何谓频度，时间复杂度，空间复杂度？说明其含义。
频度：在某个算法中某个语句被重复执行的次数就是此语句的频度。 时间复杂度：是用来估算一个算法的执行时间的量，以算法中频度最大的语句来度量。 空间复杂度：指在算法中所需的辅助空间的单元，而不包括问题的原始数据占用的空间。
2.6 数据的存储结构主要有哪两种?它们之间的本质区别是什么？
数据的存储结构：向量和链表。 本质区别：
2
向量是连续存放的，其存储空间是静态分配的，以存放顺序来表
达元素的前后件的关系。
链式存储结果不需要一组连续的存储单元，其数据元素可以分散存放在存储空间中，其元素关系由指针来指向。 2.16 试比较顺序表和链表的优缺点。
1. 线性表的长度是否固定方面：由于向量的存储空间是静态分配的，链表的存储空间是动态分配的，因此若表长不固定时采用线性链表较好。
2. 线性表的主要操作是什么：由于向量是连续存放的，所以适用于查找操作，不适用插入、删除操作。由于线性链表只能顺序存取，所以适用于插入、删除操作，不适用于查找操作。
3. 采用的算法语言：线性链表要求所使用的语言工具提供指针类型变量。 2.17 试比较单向链表与双向链表的优缺点。
1. 单向链表只能单方向地寻找表中的结点，双向链表具有对称性，从表中某一给定的结点可随意向前或向后查找。
2. 在作插入、删除运算时，双向链表需同时修改两个方向上的指针，单向链表则简便些。
2.23 试画出表达式A*(B-D)/D+C**(E*F)执行过程中NS,OS栈的变化情况。
B-D=T1 D/T1=T2 T2*A=T3 E*F=T4 T4**C=T5 T5+T3=T6 D ) D / B - T1 * C + ) ; ; ( A ; T2 * F * T4 ** T5 + * A ; E ( C + T3 ; A ; ** T3 ;
C +
T3 ; 2.26 用三元组和带行辅助向量形式表示下列稀疏矩阵：
800?1300026?1500220?15?0????0113000??1500600050?? （1）：???0?30403000???000?600??
（2）：200040??000000??000? ???000000??9100000??00?12?020000000????0028000?????000400000??700000000????12002060030?? （1）：三元组
3
; T6 ;
带行辅助向量 行 列 1 1 1 4 1 6 2 2 2 3 3 4 5 1 值 15 22 -15 11 3 -6 91 i 1 2 3 4 5 6 POS 1 4 6 7 7 8 NUM 3 2 1 0 1 1 6 3 28 (2): 三元组 带行辅助向量
行 列 值 i 1 2 3 4 5 6 7 8 9 1 1 8 POS 1 4 7 10 12 13 14 15 16 1 5 -13 NUM 3 3 3 2 1 1 1 1 4 1 9 26 2 1 15 2 4 6 2 8 5 3 2 -3 3 4 4 3 6 3 4 4 2 4 8 4 5 3 -12 6 2 2 7 4 4 8 1 7 9 1 12 9 4 2 9 6 6 9 9 30
2.27 试说明树与二叉树有何不同？为何要将一般树转换为二叉树？
树与二叉树区别：树是由n个（n>=0）结点组成的有限集合T，其中有且仅有一个结点称为根结点，在此类元素结点之间存在明显的分支和层次关系。
二叉树是一种特殊的树结构，每一个结点最多只有两个孩子，即最多只有两个分支。
为何要转换：一般树，树中结点次序没有要求，分支庞杂。而二叉树，元素之间存在严谨的前后代关系，在对数据元素进行删除、查找、插入等运算时更加有效率。
2.28 将下列（题图2.3）的一般树化为二叉树。
4
A B C D E F G I J K L 题图2.3
转换后：
A B D C E G I F K J L 2.30 设一棵二叉树其中序和后序遍历为
中序：BDCEAFHG 后序：DECBHGFA
画出这棵二叉树的逻辑结构，并写出先序遍历结果。 先序遍历：ABCDEFGH 其逻辑结构如下：
5