江大数据结构第2阶段测试题

1江南大学现代远程教育2012年上半年第二阶段测试卷考试科目:《数据结构》第五章至第七章（总分100分）时间：90分钟______________学习中心（教学点）批次：层次：专业：学号：身份证号：姓名：得分：一、选择题（每题3分，共30分）1、对稀疏矩阵进行压缩存储的目的是（C）。Ａ、便于进行矩阵运算Ｂ、便于输入和输出Ｃ、节省存储空间Ｄ、降低运算的时间复杂度2、设二维数组A5×8按行优先顺序存储，每个数据元素占2个字节，首地址即元素A[0][0]的起始地址为S，则元素A[3][6]的起始地址为（Ｂ）。Ａ、S+66Ｂ、S+60Ｃ、S+33Ｄ、S+303、设广义表L=((a,()),b,(c,d,e))，则Head(Tail(Tail(L)))的值为（Ｄ）。Ａ、bＢ、cＣ、(c)Ｄ、(c,d,e)4、下列叙述中错误的是（Ｄ）。Ａ、对数组一般不做插入和删除操作Ｂ、顺序存储的数组是一个随机存取结构Ｃ、空的广义表没有表头和表尾Ｄ、广义表的表尾可能是原子也可能是子表5、一棵度为3的树中，度为3的结点有2个，度为2的结点有2个，度为1的结点有2个，则度为0的结点有（Ｃ）。Ａ、5个Ｂ、6个Ｃ、7个Ｄ、8个6、已知二叉树T的先序序列为abdegcfh，中序序列为dbgeachf，则T的后序序列为（Ｂ）。Ａ、gedhfbcaＢ、dgebhfcaＣ、abcdefghＤ、acbfedhg7、下列叙述中错误的是（Ｄ）。Ａ、由树的先序遍历序列和后序遍历序列可以惟一确定一棵树Ｂ、二叉树不同于度为2的有序树Ｃ、深度为k的二叉树上最少有k个结点Ｄ、在结点数目相同的二叉树中，最优二叉树的路径长度最短8、设无向图的顶点个数为n，则该图最多有（Ｂ）条边。Ａ、n-1Ｂ、n(n-1)/2Ｃ、n(n+1)/2Ｄ、n29、设有无向图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进行深度优先遍历，正确的遍历序列是（Ｄ）。Ａ、a,b,e,c,d,fＢ、a,c,f,e,b,dＣ、a,e,b,c,f,dＤ、a,e,d,f,c,b210、设有向图G中有五个顶点，各顶点的度分别为3、2、2、1、2，则G中弧数为（Ｂ）。Ａ、4条Ｂ、5条Ｃ、6条Ｄ、无法确定二、（10分）设有上三角矩阵(aij)n×n，将其上三角元素逐行存于数组B[m]中（m充分大），使得B[k]=aij，求用i和j表示k的下标变换公式。答：jinik2)12(三、（10分）设二叉树如下，试对其进行先序线索化，画出相应的先序线索二叉树存储结构示意图。答：四、（10分）设有向网如下，试写出其邻接矩阵。答：6253324173五、（10分）设用于通信的电文由8个字母组成，字母在电文中出现的频率分别为0.12、0.31、0.22、0.02、0.03、0.08、0.17、0.05。试为这8个字母设计哈夫曼编码，要求画出设计过程中所构造的哈夫曼二叉树。答：编码：0.02:001000.03:001010.05:00110.08:0000.12:1000.17:1010.22:010.31:11六、（10分）设有AOE网如下，要求：⑴求图中各顶点代表的事件的最早发生时间和最晚发生时间；⑵求图中各弧代表的活动的最早开始时间和最晚开始时间；⑶列出各条关键路径。答：4关键路径１：v1→v2→v5→v7关键路径２：v1→v3→v6→v7七、（20分）设二叉树以二叉链表存储，试设计算法，实现二叉树的层序遍历。答：StatusLevelOrderTraverse(BitreeT,Status(*visit)(TElemTypee)){if(!T)returnOK;//空二叉树InitQueue(Q);//初始化辅助队列if(!visit(T-data))returnERROR;//访问根结点EnQueue(Q,T);//指向结点的指针入队while(!QueueEmpty(Q)){//若队列非空DeQueue(Q,p);//队头指针出队if(p-lchild){//先访问p所指结点的左孩子，再访问其右孩子if(!visit(p-lchild-data))returnERROR;EnQueue(Q,p-lchild);}//ifif(p-rchild){if(!visit(p-rchild-data))returnERROR;EnQueue(Q,p-rchild);}//if}//whilereturnOK;}//LevelOrderTraverse