1、试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。

【解答】数据结构是指相互之间存在一定关系的数据元素的集合。 而

抽象数据类型是指一个数据结构以及定义在该结构上的一组操作。 程序设计语言中的数据类型是一个值的集合和定义在这个值集上一组操作的总称。抽象数据类型可以看成是对数据类型的一种抽象。

串:是零个或多个字符组成的有限序列。

串是一种特殊的线性表，它的每个结点仅由一个字符组成。

空串 :长度为零的串，它不包含任何字符。

空白串 :仅由一个或多个空格组成的串

子串 :串中任意个连续字符组成的子序列称为该串的子串。

串变量和串常量

通常在程序中使用的串可分为：串变量和串常量。

（1）串变量 ：串变量和其它类型的变量一样，其取值是可以改变的。

（2）串常量 ：串常量和整常数、实常数一样，在程序中只能被引用但不能改变其值。即只能读不能写。

（1）树形图表示： 树形图表示是树结构的主要表示方法。

（2）树的其他表示法

① 嵌套集合表示法：是用集合的包含关系来描述树结构。

② 凹入表表示法：类似于书的目录

③ 广义表表示法：用广义表的形式表示的。上图 (a)树的广义表表示法如下：

（A（B（E，F（I，J））， C，D（G，H）））

1．中序遍历的递归算法定义：

若二叉树非空，则依次执行如下操作：

(1)遍历左子树； (2)访问根结点； (3)遍历右子树。

2．先序遍历的递归算法定义：

若二叉树非空，则依次执行如下操作：

(1) 访问根结点； (2) 遍历左子树； (3) 遍历右子树。

3．后序遍历得递归算法定义：

若二叉树非空，则依次执行如下操作：

(1)遍历左子树； (2)遍历右子树； (3)访问根结点。

2、链表具有的特点是

B 插入、删除不需要移动元素

C 不必事先估计存储空间

D 所需空间与线性表长度成正比

顺序队列

（1）队列的顺序存储结构称为顺序队列，顺序队列实际上是运算受限的顺序表。

（2） 顺序队列的表示

①和顺序表一样顺序队列用一个向量空间存放当前队列中的元素。

②由于队列的队头和队尾的位置是变化的，设置两个指针 front 和 rear 分别指示队头元素和队尾元素在向量空间中的位置，它们的初值在队

列初始化时均应置为 0。

顺序队列的基本操作

①入队时：将新元素插入 rear 所指的位置，然后将 rear 加 1。

②出队时：删去 front 所指的元素然后将 front 加 1 并返回被删元素。

注意 ：①当头尾指针相等时，队列为空。

②在非空队列里，队头指针始终指向队头元素，尾指针始终指向队尾元素的下一位置。

顺序队列中的溢出现象

① "下溢 "现象 ：当队列为空时，做出队运算产生的溢出现象。 “下溢 ”是正常现象，常用作程序控制转移的条件。

② "真上溢 "现象 ：当队列满时，做进栈运算产生空间溢出的现象。 “真上溢 ”是一种出错状态，应设法避免。

③ "假上溢 "现象 ：由于入队和出队操作中，头尾指针只增加不减小，致使被删元素的空间永远无法重新利用。

3、请说明顺序表和单链表各有何优缺点，并分析下列情况下，采用何种存储结构更好些。

⑴ 若线性表的总长度基本稳定，且很少进行插入和删除操作，但要

求以最快的速度存取线性表中的元素。

⑵ 如果 n 个线性表同时并存，并且在处理过程中各表的长度会动态

发生变化。

⑶ 描述一个城市的设计和规划。

顺序表的优点：

① 无需为表示表中元素之间的逻辑关系而增加额外的存储空间；

② 可以快速地存取表中任一位置的元素（即随机存取） 。

顺序表的缺点：

① 插入和删除操作需移动大量元素；

② 表的容量难以确定；③ 造成存储空间的“碎片” 。

单链表的优点：

① 不必事先知道线性表的长度；

② 插入和删除元素时只需修改指针，不用移动元素。单

链表的缺点：

① 指针的结构性开销；

② 存取表中任意元素不方便，只能进行顺序存取。

4、设单链表以非递减有序排列，设计算法实现在单链表中删去值相同的多余结点。

【解答】从头到尾扫描单链表， 若当前结点的元素值与后继结点的元素值不相等，则指针后移；否则删除该后继结点。具体算法如下：

5、在单链表中， 除了头结点以外， 任一结点的存储位置由 （ 其前趋结点的指针域）指示。

6、当线性表采用顺序存储结构时，其主要特点是（ 逻辑结构中相邻的结点在存储结构中仍相邻）。

7、在双链表中，每个结点设置了两个指针域，其中一个指向（ 前驱）结点，另一个指向（ 后继）结点。

8、设有一个空栈，栈顶指针为 1000H，现有输入序列为 1、2、3、4、5， 经过 push，push，pop，push，pop，push，push 后，输出序列是（ 23），栈顶指针为（1003H ）。

9、 栈通常采用的两种存储结构是 （顺序存储结构和链接存储结构（或顺序栈和链栈） ）；

其判定栈空的条件分别是 （栈顶指针 top= -1 和 top=NULL，栈顶指针 ），

判定栈满的条件分别是（ top 等于数组的长度和内存无可用空间）。

10、（ 栈）可作为实现递归函数调用的一种数据结构。

【分析】递归函数的调用和返回正好符合后进先出性。

11、表达式 a*(b+c)-d 的后缀表达式是（ abc+*d-）。

【分析】将中缀表达式变为后缀表达式有一个技巧： 将操作数依次写下来，再将算符插在它的两个操作数的后面。

12、和队列是两种特殊的线性表，栈的操作特性是（ 后进先出，先进先出），队列的操作特性是（对插入和删除操作限定的位置不同 ），栈和队列的主要区别

13、循环队列的引入是为了克服（假溢出 ）。

14、数组 Q[n] 用来表示一个循环队列， front 为队头元素的前一个位置，rear 为队尾元素的位置，计算队列中元素个数的公式为（（rear-front+n ）% n）。

【分析】也可以是（ rear-front ）% n，但 rear-front 的结果可能是

负整数，而对一个负整数求模，其结果在不同的编译器环境下可能会有所不同。

15、用循环链表表示的队列长度为 n，若只设头指针，则出队和入队的时间复杂度分别是（Ｏ (1)）和（Ｏ(n)）。

【分析】在带头指针的循环链表中，出队即是删除开始结点，这只需修改相应指针；入队即是在终端结点的后面插入一个结点，这需要从头指针开始查找终端结点的地址。

16、 串是一种特殊的线性表，其特殊性体现在（数据元素的类型是一个字符 ）。

17、 两个串相等的充分必要条件是（ 长度相同且对应位置的字符相等）。

【分析】例如 “abc” ≠"abc " ，“abc” ≠"bca" 。

18、 若一个栈的输入序列是 1，2，3，, ， n，输出序列的第一个元素是 n，则第 i 个输出元素是（n-i+1 ）。

19、一个栈的入栈序列是 1，2，3，4，5，则栈的不可能的输出序列是（ 43512）。

【分析】此题有一个技巧： 在输出序列中任意元素后面不能出现比该元素小并且是升序（指的是元素的序号）的两个元素。

20、设计一个判别表达式中左右括号是否配对的算法，采用（栈 ）数据结构最佳

【分析】每个右括号与它前面的最后一个没有匹配的左括号配对， 因此具有后进先出性。

21、在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印缓冲区，该缓冲区应该是一个（队列）

22、举例说明顺序队列的“假溢出”现象。

【解答】假设有一个顺序队列，如图 3-6 所示，队尾指针 rear=4 ，队头指针 front=1 ，如果再有元素入队，就会产生“上溢”，此时的“上溢”又称为“假溢出” ，因为队列并不是真的溢出了，存储队列的数组中还有 2 个存储单元空闲，其下标分别为 0 和 1。

23、空串和空格串有何区别？串中的空格符有何意义？空串在串处理

中有何作用？

【解答】不含任何字符的串称为空串，其长度为零。仅含空格的串称为空格串，它的长度为串中空格符的个数。串中的空格符可用来分隔一般的字符，便于人们识别和阅读，但计算串长时应包括这些空格符。空串在串处理中可作为任意串的子串。

24、如果进栈序列为 A、B、C、D，则可能的出栈序列是什么？

答：共 14 种，分别是：ABCD ，ABDC ，ACBD ，ACDB ，ADCB ，BACD，BADC ，BCAD ，BCDA ，BDCA ，CBAD ，CBDA ，CDBA ，DCBA

25、简述队列和栈这两种数据结构的相同点和不同点。

【解答】相同点：它们都是插入和删除操作的位置受限制的线性表。不同点：栈是限定仅在表尾进行插入和删除的线性表， 是后进先出的线性表，而队列是限定在表的一端进行插入，在另一端进行删除的线性表，是先进先出的线性表。

26、利用两个栈 S1和 S2 模拟一个队列，如何利用栈的运算实现队列的插入和删除操作，请简述算法思想。

【解答】利用两个栈 S1和 S2模拟一个队列， 当需要向队列中插入一个元素时，用 S1来存放已输入的元素，即通过向栈 S1 执行入栈操作来实现；当需要从队列中删除元素时，则将 S1中元素全部送入到 S2中，再从 S2中删除栈顶元素，最后再将 S2中元素全部送入到 S1中；判断队空的条件是：栈 S1和 S2同时为空。

27、设计算法把一个十进制整数转换为二至九进制之间的任一进制

数输出。

【解答】算法基于原理： N=(N div d) ×d + N mod d （div 为整除

运算， mod为求余运算）。

28、 一棵具有 n 个结点的二叉树采用顺序存储结构，编写算法对该二

叉树进行前序遍历。

【解答】按照题目要求，设置一个工作栈以完成对该树的非递归算法，

思路如下：

① 每访问一个结点，将此结点压栈，查看此结点是否有左子树，若

有，访问左子树，重复执行该过程直到

左子树为空。

② 从栈弹出一个结点，如果此结点有右子树，访问右子树执行步骤

①，否则重复执行步骤②。

具体算法如下：

29、 以孩子兄弟表示法做存储结构，求树中结点 x 的第 i 个孩子。

【解答】先在链表中进行遍历，在遍历过程中查找值等于 x 的结点，

然后由此结点的最左孩子域 firstchild

找到值为 x 结点的第一个孩子，再沿右兄弟域 rightsib 找到值为 x

结点的第 i 个孩子并返回指向这个孩子的

指针。

树的孩子兄弟表示法中的结点结构定义如下：

template

struct TNode

{

T data;

TNode *firstchild, *rightsib;

};

具体算法如下：

30、试找出分别满足下列条件的所有二叉树：

⑴ 前序序列和中序序列相同。

⑵ 中序序列和后序序列相同。

⑶ 前序序列和后序序列相同。

【解答】 ⑴ 空二叉树、只有一个根结点的二叉树和右斜树。

⑵ 空二叉树、只有一个根结点的二叉树和左斜树。

⑶ 空二叉树、只有一个根结点的二叉树

31、以孩子兄弟表示法作为存储结构，编写算法求树的深度。

【解答】采用递归算法实现。若树为空树，则其深度为 0，否则其深

度等于第一棵子树的深度 +1和兄弟子

树的深度中的较大者。具体算法如下：

32、设计算法，判断一棵二叉树是否为完全二叉树。

【解答】根据完全二叉树的定义可知，对完全二叉树按照从上到下、

从左到右的次序（即层序）遍历应该

满足：

⑴ 若某结点没有左孩子，则其一定没有右孩子；

⑵ 若某结点无右孩子，则其所有后继结点一定无孩子。

若有一结点不满足其中任意一条，则该二叉树就一定不是完全二叉

树。因此可采用按层次遍历二叉树的方

法依次对每个结点进行判断是否满足上述两个条件。 为此，需设两个

标志变量 BJ和 CM，其中 BJ表示已扫

描过的结点是否均有左右孩子， CM存放局部判断结果及最后的结果。

具体算法如下：

33、n 个顶点的无向图，采用邻接表存储，回答下列问题 ?

⑴ 图中有多少条边？

⑵ 任意两个顶点 i 和 j 是否有边相连？

⑶ 任意一个顶点的度是多少 ?

【解答】

⑴ 边表中的结点个数之和除以 2。

⑵ 第 i 个边表中是否含有结点 j 。

⑶ 该顶点所对应的边表中所含结点个数。

34、n 个顶点的无向图，采用邻接矩阵存储，回答下列问题：

⑴ 图中有多少条边？

⑵ 任意两个顶点 i 和 j 是否有边相连？

⑶ 任意一个顶点的度是多少？

【解答】

⑴ 邻接矩阵中非零元素个数的总和除以 2。

⑵ 当邻接矩阵 A中 A[i][j]=1 （或 A[j][i]=1 ）时，表示两顶点之间

有边相连。

⑶ 计算邻接矩阵上该顶点对应的行上非零元素的个数。

35、证明：生成树中最长路径的起点和终点的度均为１。

【解答】用反证法证明。

设 v1, v2, , , vk 是生成树的一条最长路径，其中， v1 为起点， vk

为终点。若 vk 的度为 2，取 vk 的另一个

邻接点 v，由于生成树中无回路，所以， v 在最长路径上，显然 v1,

v2, , , vk , v 的路径最长，与假设矛盾。

所以生成树中最长路径的终点的度为 1。

同理可证起点 v1 的度不能大于 1，只能为 1。

36、已知一个连通图如图 6-6 所示，试给出图的邻接矩阵和邻接表存

储示意图，若从顶点 v1 出发对该图进

行遍历，分别给出一个按深度优先遍历和广度优先遍历的顶点序列。

【解答】邻接矩阵表示如下：

深度优先遍历序列为： v1 v2 v3 v5 v4 v6

广度优先遍历序列为： v1 v2 v4 v6 v3 v5

邻接表表示如下：

37、已知无向图 G的邻接表如图 6-10 所示，分别写出从顶点 1 出发

的深度遍历和广度遍历序列，并画出相

应的生成树。

【解答】深度优先遍历序列为： 1，2，3，4，5，6

对应的生成树为：

广度优先遍历序列为： 1，2，4，3，5，6

对应的生成树为：

38、试述顺序存储和链式存储的区别及各自的优缺点。

答：数组占用连续的内存空间，链表不要求结点的空间连续。

1）插入与删除操作： 由于数组在插入与删除数据时需移动大量的数据元素，而链表只需要改变一些指针的链接，因此，链表比数组易于实现数据的插入和删除操作。

2）内存空间的占用情况：因链表多了一个指针域，故较浪费空间，因此，在空间占用方面，数组优于链表。

3）数据的存取操作：访问链表中的结点必须从表头开始，是顺序的存取方式，而数组元素的访问是通过数组下标来实现的，是随机存取方式，因此，在数据存取方面，数组优于链表。数据的合并与分离：链表优于数组，因为只需要改变指针的指向

39、java堆和栈的区别：

①数据结构：堆：堆可以被看成是一棵完全二叉树树（最小堆和最大堆）。栈：一种先进后出的数据结构。

②栈的优势是，存取速度比堆要快，仅次于直接位于CPU中的寄存器。但缺点是，存在栈中的数据大小与生存期必须是确定的，缺乏灵活性。另外，栈数据在多个线程或者多个栈之间是不可以共享的，但是在栈内部多个值相等的变量是可以指向一个地址的。

堆的优势是可以动态地分配内存大小，生存期也不必事先告诉编译器，Java的垃圾收集器会自动收走这些不再使用的数据。但缺点是，由于要在运行时动态分配内存，存取速度较慢。

③ 栈(stack)与堆(heap)都是Java用来在Ram中存放数据的地方。与C++不同，Java自动管理栈和堆，程序员不能直接地设置栈或堆。

④Java中的数据类型有两种。

一种是基本类型(primitivetypes), 共有8种，即int,short, long, byte, float, double, boolean, char(注意，并没有string的基本类型)。这些字面值的数据，由于大小可知，生存期可知(这些字面值固定定义在某个程序块里面，程序块退出后，字段值就消失了)，出于追求速度的原因，就存在于栈中。

40、知一棵二叉排序树（结点值大小按字母顺序）的前序遍历序列为 EBACDFHG ，

请回答下列问题：

41、已知有向图的邻接表如图所示，请回答下面问题：

(1)给出该图的邻接矩阵；

(2)从结点 A 出发，写出该图的深度优先遍历序列

42、已知待排记录的关键字序列为 {25， 96，11，63，57，78，44} ，请回答下列问题：

(1)画出堆排序的初始堆（大根堆） ；

(2)画出第二次重建堆之后的堆。

43、已知关键字序列为 (56，23，41，79， 38，62，18)，用散列函数 H(key)=key%11 将其散列到散列表 HT[0…10] 中，

采用线性探测法处理冲突。请回答下列问题：

(1)画出散列存储后的散列表：

(2)求在等概率情况下查找成功的平均查找长度

44、

45、

46、

47、

48、

49、

50、

51、

52、

53、

54、

55、

56、

57、

58、

59、

60、

61、

62、

63、

64、

65、

66、

67、

68、

69、

70、

71、

72、

73、

74、

75、

76、

77、

78、

79、

80、

81、

82、

83、

84、

85、

86、

87、

88、

89、

90、

91、

92、

93、

94、

95、

96、

97、

98、

99、

100、

101、

102、

103、

104、

105、

106、

107、

108、

109、

110、

111、

112、

113、

114、

115、

116、

117、

118、

119、

120、

121、

122、

123、

124、

125、