江南大学现代远程教育 2015数据结构第2阶段测试题2a

考试科目:《数据结构》第五章至第七章（总分100分） 时间：90分钟 ______________学习中心（教学点） 批次： 层次：

专业： 学号： 身份证号： 姓名： 得分：

一、选择题（每题3分，共30分）

1、对稀疏矩阵进行压缩存储的目的是（ C ）。 Ａ、便于进行矩阵运算 Ｂ、便于输入和输出 Ｃ、节省存储空间 Ｄ、降低运算的时间复杂度

2、设二维数组A5×8按行优先顺序存储，每个数据元素占2个字节，首地址即元素A[0][0]的起始地址为S，则元素A[3][6]的起始地址为（ B ）。 Ａ、S+66 Ｂ、S+60 Ｃ、S+33 Ｄ、S+30

3、设广义表L=((a,()),b,(c,d,e))，则Head(Tail(Tail(L)))的值为（ D ）。 Ａ、b Ｂ、c Ｃ、(c) Ｄ、(c,d,e) 4、下列叙述中错误的是（ D ）。 Ａ、对数组一般不做插入和删除操作 Ｂ、顺序存储的数组是一个随机存取结构 Ｃ、空的广义表没有表头和表尾

Ｄ、广义表的表尾可能是原子也可能是子表

5、一棵度为3的树中，度为3的结点有2个，度为2的结点有2个，度为1的结点有2个，则度为0的结点有（ C ）。

Ａ、5个 Ｂ、6个 Ｃ、7个 Ｄ、8个

6、已知二叉树T的先序序列为abdegcfh，中序序列为dbgeachf，则T的后序序列为（B ）。 Ａ、gedhfbca Ｂ、dgebhfca Ｃ、abcdefgh Ｄ、acbfedhg 7、下列叙述中错误的是（D ）。

Ａ、由树的先序遍历序列和后序遍历序列可以惟一确定一棵树 Ｂ、二叉树不同于度为2的有序树 Ｃ、深度为k的二叉树上最少有k个结点

Ｄ、在结点数目相同的二叉树中，最优二叉树的路径长度最短 8、设无向图的顶点个数为n，则该图最多有（ B）条边。 Ａ、n-1 Ｂ、n(n-1)/2 Ｃ、n(n+1)/2 Ｄ、n

1

2

9、设有无向图G=(V,E)，其中顶点集合V={a,b,c,d,e,f}，边集合E={(a,b), (a,e), (a,c), (b,e), (c,f), (f,d), (e,d)}。对G进行深度优先遍历，正确的遍历序列是（D ）。 Ａ、a,b,e,c,d,f Ｂ、a,c,f,e,b,d Ｃ、a,e,b,c,f,d Ｄ、a,e,d,f,c,b 10、设有向图G中有五个顶点，各顶点的度分别为3、2、2、1、2，则G中弧数为（ B ）。 Ａ、4条 Ｂ、5条 Ｃ、6条 Ｄ、无法确定

二、（10分）

设有上三角矩阵(aij)n×n，将其上三角元素逐行存于数组B[m]中（m充分大），使得B[k]=aij，求用i和j表示k的下标变换公式。 答：k

i(2ni1)j

2三、（10分）

设二叉树如下，试对其进行先序线索化，画出相应的先序线索二叉树存储结构示意图。

答

2

四、（15分）

设用于通信的电文由8个字母组成，字母在电文中出现的频率分别为0.12、0.31、0.22、0.02、0.03、0.08、0.17、0.05。试为这8个字母设计哈夫曼编码，要求画出设计过程中所构造的哈夫曼二叉树。 答

编码：

0.02: 00100 0.03: 00101 0.05: 0011 0.08: 000 0.12: 100 0.17: 101 0.22: 01 0.31: 11

3

五、（15分）

设有AOE网如下，要求：

⑴求图中各顶点代表的事件的最早发生时间和最晚发生时间； ⑵求图中各弧代表的活动的最早开始时间和最晚开始时间； ⑶列出各条关键路径。

答

关键路径１：v1→v2→v5→v7 关键路径２：v1→v3→v6→v7

六、（20分）

设二叉树以二叉链表存储，试设计算法，实现二叉树的层序遍历。 答：

Status LevelOrderTraverse(Bitree T,Status (*visit)(TElemType e)){ if (!T) return OK; //空二叉树 InitQueue(Q); //初始化辅助队列

if (!visit(T->data)) return ERROR; //访问根结点 EnQueue(Q,T); //指向结点的指针入队 while (!QueueEmpty(Q)){ //若队列非空 DeQueue(Q,p); //队头指针出队

if (p->lchild){//先访问p所指结点的左孩子，再访问其右孩子 if (!visit(p->lchild->data)) return ERROR;

4

EnQueue(Q,p->lchild); }//if

if (p->rchild){

if (!visit(p->rchild->data)) return ERROR; EnQueue(Q,p->rchild); }//if }//while return OK;

}//LevelOrderTraverse

5