一．选择题
1．设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1 到8 ，j的值为1 到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为( ) A. BA+141 B. BA+180 C. BA+222 D. BA+225
2．假设以行序为主序存储二维数组A=array[1..100，1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5，5]=（）
A. 808 B. 818 C. 1010 D. 1020 3．对稀疏矩阵进行压缩存储目的是（）
A．便于进行矩阵运算 B．便于输入和输出 C．节省存储空间 D．降低运算的时间复杂度
4．假设以三元组表表示稀疏矩阵，则与如图所示三元组表对应的4×5的稀疏矩阵是（注：矩阵的行列下标均从1开始）（ ） ?0?8?0?7?00???50A.??0?8?0?0?70???50C.?00040004600060000??0?0??0??0??3?0??0???0?8?0?7??50??00 B.??0?8?0?7??50??00 D.?00400040600060000??3?0??0??0??0?3??0??
二．解答题
已知一个6行5列的稀疏矩阵中非零元的值分别为：-90，41，-76，28，-54，65，-8，它们
在矩阵中的列号依次为：1，4，5，1，2，4，5。当以带行表的三元组表作存储结构时，其行表中的值依次为0，0，2，2，3，5（行列下标均从1开始），写出该稀疏矩阵。
第六章树和二叉树
一．选择题
1．如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是（）
A. 栈 B. 队列 C. 树 D. 图
2．设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为（）
A．5 B．6 C．7 D．8
3．已知一棵含50个结点的二叉树中只有一个叶子结点，则该树中度为1的结点个数为（） A. 0 B. 1 C. 48 D. 49 4．树的先根序列等同于与该树对应的二叉树的（）
A．先序序列 B．中序序列 C．后序序列 D．层序序列
5. 用二叉链表表示具有n个结点的二叉树时，值为空的指针域的个数为（） A．n-1 B．n C．n+l D．2n
11
6. 设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（）
A．m-n B．m-n-1 C．n+1 D．条件不足，无法确定
7. 设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1，则T中的叶子数为（）
A．5 B．6 C．7 D．8
8．设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（）
A．M1 B．M1+M2 C．M3 D．M2+M3 9．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）
A． 250 B． 500 C．254 D．505 E．以上答案都不对 10．有n个叶子的哈夫曼树的结点总数为（）
A．不确定 B．2n C．2n+1 D．2n-1
11．一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有( )结点 A．2h B．2h-1 C．2h+1 D．h+1
12．将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度（） A．4 B．5 C．6 D．7
13．若度为m的哈夫曼树中，其叶结点个数为n，则非叶结点的个数为（）
A．n-1 B．?n/m?-1 C．?(n-1)/(m-1)? D．?n/(m-1)?-1 E．?(n+1)/(m+1)?-1 14．若下面几个符号串编码集合中，不是前缀编码的是（）。 A．{0,10,110,1111} B．{11,10,001,101,0001} C．{00,010,0110,1000} D．{b,c,aa,ac,aba,abb,abc}
15．一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（） A．CABDEFG B．ABCDEFG C．DACEFBG D．ADCFEG 16．线索二叉树是一种（）结构。
A．逻辑 B．逻辑和存储 C．物理 D．线性 17．引入二叉线索树的目的是（）
A．加快查找结点的前驱或后继的速度 B．为了能在二叉树中方便的进行插入与删除 C．为了能方便的找到双亲 D．使二叉树的遍历结果唯一 18．n个结点的线索二叉树上含有的线索数为（） A．2n B．n－l C．n＋l D．n
19．若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则x的前驱为( ) A.X的双亲 B.X的右子树中最左的结点 C.X的左子树中最右结点 D.X的左子树中最右叶结点
20．某二叉树的前序序列和后序序列正好相反，则该二叉树一定是（）的二叉树 A．空或只有一个结点 B．任一结点无左子树 C．高度等于其结点数 D．任一结点无右子树
二．填空题
1．假定一棵树的嵌套括号表示法为 A （ B （ E ）， C （ F （ H ， I ， J ）， G ）， D ），则该树的度为______，树的深度为_____，终端点的个数为____，但分支结点的个数为_____，双分支结点为_____，三分支结点的个数为______， C 结点的双亲结点为_________，其孩子结点为__________和为_________结点。 2．一棵深度为 K 的满二叉树结点总数为___________ ，一棵深度为 K 的完全二叉树的结
12
点总数的最小值为________，最大值为____________。
3．由三个结点构成的二叉树，共有_____________种不同的形态。 4．具有100个叶子结点的完全二叉树的深度为
5．高为h（h>0）的满二叉树对应森林的由棵树构成。
三．已知一个二叉树的中序序列为CBEDAHGIJF,后序序列为CEDBHJIGFA。 1．画出该二叉树。
2．画出该二叉树的先序线索二叉树。 四．试找出分别满足下列条件的所有二叉树： 1．先序序列和中序序列相同。 2．中序序列和后序序列相同。 3．先序序列和后序序列相同。
五．设二叉树用二叉链表表示，设计算法求二叉树的高度。
六．设用于通信的电文由字符集｛a,b,c,d,e,f,g｝中的字母构成，它们在电文中出现的频率分别为｛0.31,0.16,0.10,0.08,0.11,0.20,0.04｝，回答下列问题： ⑴为这7个字母设计哈夫曼编码
⑵若对这7个字母进行等长编码，至少需要几位二进制数？ 七．设计算法以输出二叉树中先序序列的前k（k>0）个结点的值。 八．编写算法，对一棵二叉树统计叶子的个数 九．假设以二叉链表表示二叉树，其类型定义如下：
typedef struct node { DataType data;
struct node * lchild, * rchild; //左右孩子指针 }* BinTree ;
阅读下列算法，并回答问题：
③ 已知以T为根指针的二叉树如图所示，写出执行Demo2(T)之后的返回值； ④ 简述算法Demo2的功能。 int Demo2( BinTree T) { int d; if ( ! T) return 0;
d = Demo2 ( T - > lchild) +Demo2 ( T - > rchild) ;
13
if (T - > lchild && T - > rchild) return d + 1 ; else return d; }
③ 返回值： ④ 功能：
第七章图
一．选择题
1．n个顶点，e条边的有向图的邻接矩阵中非零元素有个。 A.n B.2e C.e D.n+e 2．用邻接表存储图所用的空间大小（） A．与图的顶点数和边数都有关 B．只与图的边数有关 C．只与图的顶点数有关 D．与边数的平方有关
3．有 n 条边的无向图的邻接表存储法中，链边中结点的个数是（）个。 A．n B．2n C．n/2 D．n*n 4．一个带权无向连通图的最小生成树（）。
A．有一棵或多棵 . B．只有一棵 C．一定有多棵 D．可能不存在
5．若一个图中包含有k个连通分量，若要按照深度优先搜索的方法访问所有顶点，则必须调用( )次深度优先搜索遍历的算法。 A．k B．1 C．k-1 D．k+1
二．如下所示有向图：
1．请给出每个顶点的度，入度和出度。
2．请画出其邻接矩阵、邻接表、逆邻接表、十字链表。
BADC 三．试对下图所示的AOE网络，解答下列问题。
1．求每个事件的最早发生时间ve [i]和最迟发生时间vl[i]。
14
2．求每个活动的最早开始时间ee(s)和最迟开始时间el(s)。 3．指出哪些活动加速可使整个工程提前完成。
=3Ba3a4=3a1=2Ea7=2a8=1ACa5=4=2a2DFa6=3 四．写出下图所示的AOV网的所有拓扑有序序列。
ABCDEF
第八章查找
一．填空题
1．采用二分法进行查找的查找表，应选择____________________方式的存储结构
2．设在有序表A[0??9]中进行二分查找，比较一次查找成功的结点数为_____，比较二次查找成功的结点数为______，比较三次查找成功的结点数为_____，比较四次查找成功的结点数为_____，比较五次查找成功的结点数为_____，平均查找长度为______。
二．选择题
1．对线性表进行二分查找时，要求线性表必须（ ） A．键值有序的链接表 B．键值有序的顺序表 C．链接表但键值不一定有序 D．顺序但键值不一定有序
2．有一个有序表{1，4，6，10，18，35，42，53，67，71，78，84，92，99},当用二分查找法查找键值为84的结点时，经（ ）比较后查找成功。 A．2 B． 3 C．4 D．12
3．顺序检索一个具有n个数据元素的线性表，其时间复杂度为（ ），二分检索一个具有n个数据元素的线性表，其时间复杂度为（ ）
A． O(n) B．O(log2n) C．O(n2) D．O(nlog2n) 4．在一棵平衡二叉排序树中，每个结点的平衡因子的取值范围是( )。
A. -1?1 B. -2?2 C. 1?2 D. 0?1
5．设散列表长度为m，散列函数为H（key）=key%p，为了减少发生冲突的可能性，p应取（ ）
A．小于m的最大奇数 B．小于m的最大素数 C．小于m的最大偶数 D．小于m的最大合数
6．若根据查找表(23,44,36,48,52,73,64,58)建立哈希表，采用h(K)=K计算哈希地址，则元素64的哈希地址为( )。
15