38．散列法存储的思想是由关键字值决定数据的存储地址。（√）
39．二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。（×） 40．具有n个结点的二叉排序树有多种，其中树高最小的二叉排序树是最佳的。（√） 41．直接选择排序算法在最好情况下的时间复杂度为O(n)。（×） 四、应用简答题。
1．有下列几种用二元组表示的数据结构，画出它们分别对应的逻辑图形表示，并指出它们分别属于何种结构。 （1）A ＝｛D，R｝，其中：D＝｛a，b，c，d，e，f，g，h｝，R ＝｛r｝，
r ＝｛
r ＝｛
r ＝｛（1，2），（2，3），（2，4），（3，4），（3，5），（3，6），（4，5），（4，6）｝ 2．简述顺序表和链表存储方式的特点。
答：顺序表的优点是可以随机访问数据元素，缺点是大小固定，不利于增减结点（增减结点操作需要移动元素）。链表的优点是采用指针方式增减结点，非常方便（只需改变指针指向，不移动结点）。其缺点是不能进行随机访问，只能顺序访问。另外，每个结点上增加指针域，造出额外存储空间增大。 3．对链表设置头结点的作用是什么？（至少说出两条好处）
答：其好处有：
（1）对带头结点的链表，在表的任何结点之前插入结点或删除表中任何结点，所要做的都是修改前一个结点的指针域，因为任何元素结点都有前驱结点（若链表没有头结点，则首元素结点没有前驱结点，在其前插入结点和删除该结点时操作复杂些）。 （2）对带头结点的链表，表头指针是指向头结点的非空指针，因此空表与非空表的处理是一样的。
4．对于一个栈，给出输入项A，B，C。如果输入项序列由A，B，C组成，试给出全部可能的输出序列。
5．设有4个元素1、2、3、4依次进栈，而栈的操作可随时进行（进出栈可任意交错进行，但要保证进栈次序不破坏1、2、3、4的相对次序），请写出所有不可能的出栈次序和所有可能的出栈次序。
6．现有稀疏矩阵A如图所示，要求画出三元组表示法和十字链表表示法：
17
?15?0??0??0?91???0220?15?133000??00?600??
00000?00000??028000??007．设4维数组的4个下标的范围分别为
[-1，0]，[1，2]，[1，3]，[-2，-1]，请分别按行序和列序列出各元素。
8．有一份电文中共使用5个字符：a，b，c，d，e，它们出现的频率依次为4，7，5，2，9，试画出对应的哈夫曼树（请按左子树根结点的权小于等于右子树根结点的权的次序构造），并求出每个字符的哈夫曼编码。 9．有如图所示的二叉树，回答如下问题。 a（1） 写出该树的中序遍历序列; （2） 写出该树的先序遍历序列; bc（3） 写出该树的后序遍历序列；
（4） 画出该二叉树的中序线索二叉树； def（5） 画出该二叉树的后序线索二叉树； （6） 画出该二叉树对应的森林； gh10已知一棵树边的集合为
i{
（2） 写出先序遍历、中序遍历和后序遍历的结果； （3） 写出结点值c的双亲结点，其左、右孩子；
18
（4） 画出把此二叉树还原成森林的图。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 e a f d g c j h i b 12．已知一棵二叉树的中序序列为cbedahgijf，后序序列为cedbhjigfa，画出该二叉树的先序线索二叉树。 13．某二叉树的先序遍历序列是abdgcefh，中序遍历序列是dgbaechf，给出其后序遍历序列。
LGA CBMNHO
PDEFJIK
RQ
13．已知非空线性链表的第一个结点的指针为head，请写一个算法，将该链表中数据域值最小的结点移动到链表的最前端。编写的函数具有如下原型：void func(TLinkNode *head),其中链结点的结构如下： struct TLinkNode {
int data;
TLinkNode *next; }
请完成该算法。
14．在数组a[0?n-1]中存放有n个不同的整数，请编写一个函数，将a中的n个数按从小到大的顺序排列，要求使用改进的插入排序算法，元素a[i]要插入的位置由折半（二分）查找算法找到。
19
14．将下图所示森林转换成为二叉树，并写出转化后二叉树中序遍历结果。
15．有一份电文中共使用8个字符：a、b、c、d、e、f、o、i，它们的出现频率依次为10，20，15，32，40，60，26，18。试画出对应的哈夫曼树（请按左子树根结点的权小于等于右子树根结点的权的次序构造），并求出每个字符的哈夫曼编码。
16．已知某系统在通信联络中只可能出现A,B,C,D,E,F,G,H八种字符，其频率为0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11试设计哈夫曼编码。 17．对有五个顶点{v1,v2,v3,v4,v5}的图的邻接矩阵如图所示，解答下列问题： （1）画出逻辑图。
（2）画出该逻辑结构的邻接表。
（3）基于邻接矩阵写出图的深度、广度优先遍历序列。
? ?010030?10???0????
??60020??? ??10? ??0???????500?18．如图所示，解答如下问题：
?（1）写出从定点A出发，深度和广度优先遍历方法遍历该图的顶点序列。
（2）根据普里姆算法和克鲁斯卡尔算法，分别求它的最小生成树，要求给出构造过程。
20
相关推荐：
loading