11．取线性表的第i个元素的时间同i的大小有关。（×） 12．循环链表不是线性表。（×）
13．链表是采用链式存储结构的线性表，进行插入、删除操作时，在链表中比在顺序表中效率高。（√）
14．双向链表可随机访问任一结点。（×）
15．在单链表中，给定任一结点的地址p，则可用下述语句将新结点s插入结点p的后面：p->next = s; s->next = p->next; (× ) 16．队列是一种插入和删除操作分别在表的两端进行的线性表，是一种先进后出的结构。（×） 17.串是一种特殊的线性表，其特殊性体现在可以顺序存储。（×） 18．长度为1的串等价于一个字符型常量。(× ) 19．空串和空白串是相同的。（×）
20．数组元素的下标值越大，存取时间越长。(× )
21．用邻接矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关。(√ ) 22．一个广义表的表头总是一个广义表。（×） 23．一个广义表的表尾总是一个广义表。（√）
24．广义表((( a ), b), c ) 的表头是(( a ), b)，表尾是( c )。（√）
25．二叉树的后序遍历序列中，任意一个结点均处在其孩子结点的后面。（√） 26．度为2的有序树是二叉树。（×）
27．二叉树的前序遍历序列中，任意一个结点均处在其孩子结点的前面。（√） 28．用一维数组存储二叉树时，总是以前序遍历顺序存储结点。（×）
29．若已知一棵二叉树的前序遍历序列和后序遍历序列，则可以恢复该二叉树。（×） 30．在哈夫曼树中，权值最小的结点离根结点最近。(× ) 31．强连通图的各顶点间均可达。（√）
32．对于任意一个图，从它的某个结点进行一次深度或广度优先遍历可以访问到该图的每个顶点。（×）
33．在待排序的记录集中，存在多个具有相同键值的记录，若经过排序，这些记录的相对次序仍然保持不变，称这种排序为稳定排序。(√34．在平衡二叉树中，任意结点左右子树的高度差（绝对值）不超过1。(√ ) 35．拓扑排序是按AOE网中每个结点事件的最早发生时间对结点进行排序。(× ) 36．冒泡排序算法关键字比较的次数与记录的初始排列次序无关。（×）
37．对线性表进行折半查找时，要求线性表必须以链式方式存储，且结点按关键字有序排列。（×）
16
) 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