内容发布更新时间 : 2024/11/15 7:19:51星期一 下面是文章的全部内容请认真阅读。

( √ )10. 线性表可以看成是广义表的特例，如果广义表中的每个元素都是原子，则广义表便成为线性表。

( √ )11. 由树转换成二叉树，其根结点的右子树总是空的。 ( × )12. 后序遍历树和中序遍历与该树对应的二叉树，其结果不同。

( × )13. 若有一个结点是某二叉树子树的中序遍历序列中的最后一个结点，则它必是该子 树的前序遍历序列中的最后一个结点。

( √ )14.若一个树叶是某子树的中序遍历序列中的最后一个结点，则它必是该子树的前序 遍历序列中的最后一个结点。

( × )15. 已知二叉树的前序遍历和后序遍历序列并不能唯一地确定这棵树，因为不知道树 的根结点是哪一个。

( × )16. 在哈夫曼编码中，当两个字符出现的频率相同时，其编码也相同，对于这种情况应作特殊处理。 ( √ )17. 有回路的图不能进行拓扑排序。

( × )18. 连通分量是无向图中的极小连通子图。 ( √ )19. 散列法存储的基本思想是由关键码的值决定数据的存储地址。

( √ )20. 散列表的查找效率取决于散列表造表时选取的散列函数和处理冲突的方法。 ( √ )21. m阶B-树每一个结点的子树个数都小于或等于m。 ( √ )22. 中序遍历二叉排序树的结点就可以得到排好序的结点序列。

( √ )23. 在二叉排序树上插入新的结点时，不必移动其它结点，仅需改动某个结点的指针， 由空变为非空即可。 ( √ )24. 当待排序的元素很多时，为了交换元素的位置，移动元素要占用较多的时间，这是影响时间复杂性的主要因素。

( √ )25. 对于n个记录的集合进行快速排序，所需要的平均时间是O(nlog2 n)。

( √ )26. 对于n个记录的集合进行归并排序，所需要的平均时间是O(nlog2 n)。

( √ )27. 堆中所有非终端结点的值均小于或等于（大于或等于）左右子树的值。

( × )28. 磁盘上的顺序文件中插入新的记录时，必须复制整个文件。

( × )29. 在索引顺序文件中插入新的记录时，必须复制整个文件。

( × )30. 索引顺序文件是一种特殊的顺序文件，因此通常存放在磁带上。

四、简答题。(共6小题，每小题约5分，共32分) 1. 简述下列术语：数据、数据项、数据元素、数据逻辑结构、数据存储结构、数据类型和算法。

数据：数据是信息的载体，是计算机程序加工和处理的对象，包括数值数据和非数值数据。

数据项：数据项指不可分割的、具有独立意义的最小数据单位，数据项有时也称为字段或域。

数据元素：数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理，一个数据元素可由若干个数据项组成。

数据逻辑结构：数据的逻辑结构就是指数据元素间的关系。 数据存储结构：数据的物理结构表示数据元素的存储方式或者数据元素的物理关系。

数据类型：是指变量的取值范围和所能够进行的操作的总和。 算法：是对特定问题求解步骤的一种描述，是指令的有限序列。

2. 简述栈和线性表的区别。

答：一般线性表使用数组来表示的。线性表一般有插入、删除、读取等对于任意元素的操作。

而栈只是一种特殊的线性表。栈只能在线性表的一端插入（称

为入栈,push）或者读取栈顶元素或者称为“弹出、出栈”(pop)。

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

答：相同点：栈和队列都是特殊的线性表，只在端点处进行插入，删除操作。

不同点：栈只在一端（栈顶）进行插入，删除操作；队列在一端（top）删除，一端(rear)插入。

4. 如果进栈的元素序列为A，B，C，D，则可能得到的出栈序列有多少种? 写出全部的可能序列。 答：可能序列有14种：ABCD; ACBD; ACDB; ABDC; ADCB; BACD; BADC; BCAD; BCDA; BDCA; CBAD; CBDA; CDBA; DCBA。

5. 如果进栈的元素序列为1，2，3，4，5，6，能否得到4，3，5，6，1，2和1，3，5，4，2，6的出栈序列?并说明为什么不能得到或如何得到。

答：不能得到4，3，5，6，1，2，最先出栈的是4,则按321的方式出，不可能得到1在2前的序列，可以得到1，3，5，4，2，6，按如下方式进行push(1), pop(), push(2), push(3), pop(), push(4), push(5), pop(), pop(), pop(), push(6), pop()。

6. 设s=“I AM A STUDENT”,t=“GOOD”，q=“WORKER”。 求：StrLength (s)， StrLength (t)，SubStr( s，8，7)，SubStr(t，2，1)，StrIndex(s,“A”)，StrIndex (s，t)，StrRep(s，

“STUDENT”，q)，SubStr (SubStr (s，6，2)，StrConcat (t，SubStr(s，7，8)))。

答：StrLength (s)=14, StrLength (t)=4, SubStr( s，

8，7)=” STUDENT”, SubStr(t，2，1)=”O”,

StrIndex(s,“A”)=3, StrIndex (s，t)=0, StrRep(s，“STUDENT”，q)=” I AM A WORKER”,

7. 简述下列每对术语的区别：空串和空格串；串变量和串常量；主串和子串；串变量的名字和串变量的值。

答：空串：不含任何字符；空格串：所含字符都是空格。 串变量和串常量:串常量在程序的执行过程中只能引用不能改变；串变量的值在程序执行过程中是可以改变和重新赋值的。

主串与子串：子串是主串的一个子集。

串变量的名字与串变量的值:串变量的名字表示串值的标识符。

8. 设有二维数组A(6×8)，每个元素占6个字节存储，顺序存放，A的起地址为1000，计算： (1)数组A的体积(即存储量)；

(2)数组的最后一个元素A的起地址；

(3)按行优先存放时，元素A1,4的起地址； (4)按列优先存放时，元素A4,7的起地址。 (1)6*8*6=288 (2)1000+47*6=1282 (3)1000+(8+4)*8=1096 (4)1000+(6*7+4)*8=1368

9. 分别画出含三个结点的无序树与二叉树的所有不同形态。 答：无序树形态如下：

二叉树形态如下：

10. 分别写出图1中所示二叉树的先序遍历、中序遍历、后序遍历的结点访问序列。

答：先序遍历序列:ABDEHICFJG 中序遍历序列:DBHEIAFJCG 后序遍历序列:DHIEBJFGCA

11. 试找出分别满足下列条件的所有二叉树。 (1) 先序序列与中序序列相同。 (2) 后序序列与中序序列相同。 (3) 先序序列与后序序列相同。

答：(1) 先序序列和中序序列相同：空树或缺左子树的单支树；