连续字符组成的序列称为该串的( 子串 )串。
21、VSAM文件结构由三部分组成：索引集、(顺序集)和数据集。
22、串的顺序存储有两种方法：一种是每个单元只存一个字符，称为(非紧缩格式)格式，另一种是每个单元存放多个字符，称为(紧缩格式)格式。
23、线性表的常见链式存储结构有单链表、(双向链表)和(循环链表)。
24、线性表典型的基本运算包括初始化、(插入)、(删除)、查找定位、求长度、存取等六种。 25、已知：s1=〃I’m a teacher〃，s2=〃teacher〃，s3=〃student〃，则SUBSTR(s1,7,7)等于(student)。 26、已知：s1=〃I’m a teacher〃，s2=〃teacher〃，s3=〃student〃，则DELETE(s1,4,10) 等于( I’m )。
27、已知：s1=〃I’m a teacher〃，s2=〃teacher〃，s3=〃student〃，则EQUAL(s1,s2)等于(0 ) 。 28、顺序表中逻辑上相邻的元素的物理位置(必须)紧邻。单链表中逻辑上相邻的元素的物理位置(不需要)紧邻。
29、四维数组是一种非线性结构，其中的每一个数组元素最多有(4)个直 接前驱（或直接后继）
30、一般地，栈和线性表类似有两种实现方法，即( 顺序 )实现和( 链接 )实现。 31、含零个字符的串称为( 空串)串，用(Ф)表示。
32、栈是一种限定在表的一端进行插入和删除的线性表，又被称为(后进先出)线性表。 33、在栈的顺序实现中，设栈顶指针为top，栈空的条件为(top=0)。
34、若已知一个栈的入栈序列是1，2，3，4，?，n ，其输出序列是P1，P2，P3，?，Pn，若P1=n，则Pi为(n-i+1 )。
35、对于顺序存储的栈，因为栈的空间是有限的，在进行(后进)运算时，可能发生栈的上溢，在进行(先出)运算时，可能发生栈的下溢。
36、(栈)可以作为实现递归函数调用的一种数据结构。
37、对任何二叉树，若度为2的节点数为n2，则叶子数n0=( n2+1 )。 38、队列中允许进行删除的一端称为(对头)。
39、一般地，一个n维数组可视为其数据元素为( n )维数组的线性表。数组通常只有(删除)和(插入)两种基本运算。
40、二叉树有不同的链式存储结构，其中最常用的是(二叉链表 )与(三叉链表 )。 41、以下运算实现在顺序栈上的进栈，请在( )处用适当的语句予以填充。
Int Push(SqStackTp *sq,DataType x)
{ if(sp->top==sqstack_maxsize-1}{error(“栈满”);return(0);} else{( sq->top++):
(sq->data[sq->top])=x;
return(1);}
}
42、深度为90的满二叉树上，第11层有(210)个结点。
43、已知一棵度为3的树有2个度为1的结点，3个度过为2的结点，1个度为3 的结点，则该树中有(6)个叶子结点。
44、深度优先搜索遍历类似于树的(先根)遍历，它所用到的数据结构是(栈)。 45、具有n个结点的完全二叉树的深度为([log2n]＋1 )。
46、(树 )中结点的最大度数允许大于2，而( 二叉树 )中结点的最大度数不允许大于2
47、一棵树按照左子女-右兄弟表示法转换成对应的二叉树，则该二叉树中树根结点肯定没有(右)子女。
k48、深度为k(k>=1)的二叉树至多有(2-1 )个结点。
49、有m个叶子结点的哈夫曼树，其结点总数为( 2m-1 )。
50、在一棵树中，( 根)结点没有前驱结点。
51、对无向图，其邻接矩阵是一个关于(对角线)对称的矩阵。
52、n (n﹥0) 个顶点的有向连通图最多有(n(n-1) )条边，最少有(n-1)条边 53、设无向连通图G的顶点数为n，则G最少有(n-1 )条边。
54、遍历图的基本方法有(深度)优先搜索和( 广度 )优先搜索两种。
55、在集合这种逻辑结构中，任何结点之间都不存在( 逻辑 )关系，这是集合这种逻辑结构的基本特点。 56、一个有向图G中若有弧,
57、广度优先搜索遍历类似于树的(层次)遍历，它所用到的数据结构是(队列)。 58、由( 树)转换成二叉树时，其根结点的右子树总是空的。 59、设图G=(V,E)，V={1,2,3,4}, E={<1,2>,<1,3>,<2,4>,<3,4>}，从顶点1出发，对图G进行广度优先搜索的序列有种( 2 )。
60、任何连通图的连通分量只有一个，即(本身)。 61、向一棵二叉搜索树中插入一个元素时，若元素的值小于根结点的值，则应把它插入到根结点的(左子树)上。
62、对有序表(25，30，32，38，47，54，62，68，90，95)用二分查找法查找32，则所需的比较次数为( 3 )。 63、静态查找表包括(建表)、(查找)、(读元素)三种基本运算。
64、动态查找表包括建表、查找、读元素、( 插入)、( 删除 )五种基本运算。
65、根据一组记录（56，42，50，64，48）依次插入结点生成一棵AVL树（高度平衡的二叉搜索树）时，当插入到值为(50)的结点时需要进行旋转调整。
66、平衡二叉排序树上任一结点的平衡因子只可能是(0)、(1)或(-1)。
67、在二叉排序树上插入新结点时，不必移动其它结点，仅需使某结点的指针域由(空)变为(指向该结点)即可。
68、在一棵AVL树（高度平衡的二叉搜索树）中，每个结点的左子树高度与右子 树高度之差的绝对值不超过( 1 )。
69、在具有24个元素的有序表上进行二分查找，则比较一次查找成功的结点数为( 1 )。 70、快速排序是不稳定的，其时间复杂性为( O（nlog2n） ) 71、直接选择排序是不稳定的，其时间复杂性为(O（n2) )。 72、按排序过程中依据的不同原则对内部排序方法进行分类，主要有：插入排序、(选择排序)、(交换排序)、归并排序等四类
73、归并排序的空间复杂度为(O(1))。
74、二叉排序树是一种特殊的、增加了限制条件的二叉树，其限制条件是任一结点的键值(大 )于其左孩子（及其子孙）的键值且(小)于其右孩子（及其子孙）的键值。 75、归并排序的时间复杂度是(O（nlog2n）)。
2
76、简单排序的时间复杂性为( O（n) )，空间复杂度为( O(1) )。
i-1
77、二叉树第i（i>=1）层至多有(2 )个节点。
2
78、直接插入排序是稳定的，它的时间复杂性为(O（n))，空间复杂度为(O（1))。 79、归并排序要求待排序列由若干个(有序)的子序列组成。
80、按照排序过程涉及的存储设备的不同，排序可分为(内)排序和（外)排序。
四、计算题
1、设二维数组A8*9的每个元素占4个字节，已知Loc（a00）=1000，A共占多少个字节？A的终端结点a78的起始地址为多少？按行和按列优先存储时，a45的起始地址分别为多少？ 答案： （(1）288；（2）1284；（3）行：1164 列：1176)
2、设二维数组A8*9的每个元素占4个字节，行下标i的范围从1到8， 列下标j的范围从0到8已知Loc（a10）=1000，A共占多少个字节？ A的终端结点a78的起始地址为多少？按行和按列优先存储时，a65的起 始地址分别为多少？
答案：（1）288；（2）1284；（3）行：1200 列：1180
3、设二维数组A8*9的每个元素占5个字节，行下标i的范围从0到7，列下标j的范围从1到9已知Loc（a01）=2000，A共占多少个字节？A的终端结点a78的起始地址为多少？按行和按列优先存储时，a45的起始地址分别为多少？
答案：（1）360；（2）2355；（3）行：2200 列：2185
4、设二维数组A11*9的每个元素占7个字节，行下标i的范围从0到10，
列下标j的范围从1到9已知Loc（a01）=2500，A共占多少个字节？A的终端结点a109的起始地址为多少？按行和按列优先存储时，a75的起始地址分别为多少？ 答案：（1）693；（2）3186；（3）行：2969 列：2857
5、设二维数组A7*9的每个元素占4个字节，已知Loc（a11）=2000，A共占多少个字节？A的终端结点a68的起始地址为多少？按行和按列优先存储时，a55的起始地址分别为多少？
答案：（1）252；（2）2208；（3）行：2160 列：2128
6、设二维数组A8*9的每个元素占8个字节，已知Loc（a00）=2000，A 共占多少个字节？A的终端结点a78的起始地址为多少？ 答案：（1）576；（2）2568
7、设有一个10阶的对称矩阵A[10][10]，采用压缩存储方式按行将矩阵
中下三角部分的元素存入一维数组B[ ]中，A[0][0]存入B[0]中，则A[7][5]在B[ ]中位置为多少？
答案：33
8、设二维数组A10*9的每个元素占4个字节，已知Loc（a00）=2000，按行和按列优先存储时，a56的起始地址分别为多少？ 答案；（1）2024；（2）2260
9、设有一个10阶的对称矩阵A[10][10]，采用压缩存储方式按行将矩阵中下三角部分的元素
存入一维数组B[ ]中，A[0][0]存入B[0]中，则A[8][5]在B[ ]中位置为多少？
答案：41
10、设二维数组A10*9的每个元素占7个字节，已知Loc（a00）=1500，A 共占多少个字节？A的终端结点a98的起始地址为多少？ 答案：（1）630；（2）2123
11、设有一个10阶的对称矩阵A[20][20]，采用压缩存储方式按行将矩阵
中下三角部分的元素存入一维数组B[ ]中，A[0][0]存入B[0]中，则A[14][12]在B[ ]中位置为多少？
答案：117
12、设二维数组A6*7的每个元素占5个字节，已知Loc（a00）=1000，A共占多少个字节？A的终端结点a56的起始地址为多少？按行和按列优先存储时，a46的起始地址分别为多少？
答案：（1）210；（2）1205；（3）行：1170 列：1200
13、设二维数组A12*9的每个元素占4个字节，已知Loc（a11）=2000，A共占多少个字节？A的终端结点a118的起始地址为多少？按行和按列优先存储时，a85的起始地址分别为多少？
答案:（1）432；（2）2428；（3）行：2268 列：2220
五、综合题
1、给出下列二叉树的前序序列、中序序列、后序序列。
答案：前序：CABEFDHG
中序：BAFECHDG 后序：BFEAHGDC
2、假定用于通信的电文仅由4个字母a，b，c，d, e组成，各个字母在电文中出现的频率分别为7，6, 5，2，4。试为这5个字母设计Huffman树且写出对应的Huffman编码。 答案:
a :10 b: 00 c: 01 d:110 e :111
b c a d e
3、把下面的森林转换为对应的二叉树。
A E H D G I K
C J B