第二阶段测试卷
考试科目:《数据结构》第五章至第七章（总分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　Ｄ、n2
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、设有向图二叉树的深度为kG中有五个顶点，各顶点的度分别为3、2、2、1、2，则G中弧数为（B）。
Ａ、4条　Ｂ、5条　Ｃ、6条　Ｄ、无法确定
二、（10分）
设有上三角矩阵(aij)n×n，将其上三角元素逐行存于数组B[m]中（m充分大），使得B[k]=aij，求用i和j表示k的下标变换公式。
三、（10分）
设二叉树如下，试对其进行先序线索化，画出相应的先序线索二叉树存储结构示意图。
四、（15分）
设用于通信的电文由8个字母组成，字母在电文中出现的频率分别为0.12、0.31、0.22、0.02、0.03、0.08、0.17、0.05。试为这8个字母设计哈夫曼编码，要求画出设计过程中所构造的哈夫曼二叉树。
五、（15分）
设有AOE网如下，要求：
⑴求图中各顶点代表的事件的最早发生时间和最晚发生时间；
⑵求图中各弧代表的活动的最早开始时间和最晚开始时间；
⑶列出各条关键路径。
六、（20分）
设二叉树以二叉链表存储，试设计算法，实现二叉树的层序遍历。
答案：
一、选择题
C、B、D、D、C、B、D、B、D、B
二、设有上三角矩阵(aij)n×n，将其上三角元素逐行存于数组B[m]中（m充分大），使得B[k]=aij，求用i和j表示k的下标变换公式。
答：
三、设二叉树如下，试对其进行先序线索化，画出相应的先序线索二叉树存储结构示意图。
答：
四、设用于通信的电文由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
五、设有AOE网如下，要求：
⑴求图中各顶点代表的事件的最早发生时间和最晚发生时间；
⑵求图中各弧代表的活动的最早开始时间和最晚开始时间；
⑶列出各条关键路径。
答：
关键路径１：v1→v2→v5→v7
关键路径２：v1→v3→v6→v7
六、设二叉树以二叉链表存储，试设计算法，实现二叉树的层序遍历。
答：
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;
      EnQueue(Q,p->lchild);
    }//if
    if (p->rchild){
      if (!visit(p->rchild->data)) return ERROR;
      EnQueue(Q,p->rchild);

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。