1 第1章 绪论 .................................................................................................................................................. 2
1、填空题 ................................................................................................................................................................ 2
2、应用题 ................................................................................................................................................................ 2
第2章 线性表 .............................................................................................................................................. 3
1、填空题 ................................................................................................................................................................ 3
第1章 绪论
1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。
解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。
数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。
数据对象是性质相同的数据元素的集合，是数据的一个子集。
数据结构是相互之间存在一种或多种特定关系的数据元素的集合。
存储结构是数据结构在计算机中的表示。
数据类型是一个值的集合和定义在这个值集上的一组操作的总称。
抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。
1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。
解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。
1.3 设有数据结构(D,R)，其中
4,3,2,1ddddD，rR，4,3,3,2,2,1ddddddr
试按图论中图的画法惯例画出其逻辑结构图。
解：
1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。
解：
ADT Complex{
数据对象：D={r,i|r,i为实数}
数据关系：R={}
基本操作：
InitComplex(&C,re,im)
清华大学模拟试题二
一． 单项选择题（2分/题）
1．一棵左右子树均不空的二叉树在先序前驱和后序后继线索化后，其空链域数为（）。
A.0 B.1 C.2 D.不确定
2．设图G采用邻接表存储，则拓扑排序算法的时间复杂度是（）。
A.O(n) B.O(n+e) C.O(n2) D.O(n*e)
3．下列排序算法中，时间复杂度为O(nlog2n)且占用额外空间最少的是（）。
A.堆排序 B.冒泡排序 C.快速排序 D.SHELL排序
4．已知数据表A中每个元素距其最终位置不远，则采用（）排序算法最节省时间。
A.堆排序 B.插入排序 C.快速排序 D.直接选择排序
5．串是（）。
A.不少于一个字母的序列 B. 任意个字母的序列
C.不少于一个字符的序列 D.有限个字符的序列
二． 判断题（1分/题）
1.（ ）若一个栈的输入序列为123…n，其输出序列的第一个元素为n，则其输出序列的每个元素ai一定满足ai =n-i+1。(i=1,2,...,n)
2.（ ）二叉树中的叶子结点就是二叉树中没有左右子树的结点。
3.（ ）一棵树中的叶子结点数一定等于与其对应的二叉树中的叶子结点数。
4.（ ）删除二叉排序树中的一个结点，再重新插入上去，一定能得到原来的二叉排序树。
5.（ ）线性表就是顺序表。
6.（ ）若一棵树中某结点的度为1，则该结点仅有一棵子树。
7.（ ）所谓平衡二叉树是指左右子树的高度差的绝对值不大于1的二叉树。
8.（ ）AOE网所表示的工程至少所需的时间等于从源点到汇点的最短路径的长度。
9.（ ）若某二叉树的叶子结点数为1，则其先序序列和后序序列一定相反。 10.（ ）在采用线性探测法处理冲突的散列表中，所有的同义词在表中相邻。
第1章 绪论
1.1
简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。
解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。
数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。
数据对象是性质相同的数据元素的集合，是数据的一个子集。
数据结构是相互之间存在一种或多种特定关系的数据元素的集合。
存储结构是数据结构在计算机中的表示。
数据类型是一个值的集合和定义在这个值集上的一组操作的总称。
抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。
1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。
解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。
1.3 设有数据结构(D,R)，其中
4,3,2,1ddddD，rR，4,3,3,2,2,1ddddddr
试按图论中图的画法惯例画出其逻辑结构图。
解：
1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。
解：
ADT Complex{
数据对象：D={r,i|r,i为实数}
数据关系：R={}
基本操作：
InitComplex(&C,re,im)
