数据结构第2阶段练习题20年江大考试题库及答案一科共有三个阶段,这是其中一个阶段答案在最后

1、江南大学网络教育第二阶段练习题考试科目：数据结构第章至第章（总分100分）学习中心（教学点）批次：层次:专业：学号：身份证号：姓名：得分:一单选题（共10题，总分值20分，下列选项中有且仅有一个选项符合题目要求，请在答题卡上正确填涂。）1 .设有无向图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进行深度优先遍历，正确的遍历序列是（）。（2分）A.a,b,e,c,d,fB.a,c,f,e,b,dC.a,e,b,c,f,dD.a,e,d,f,c,b2 .设二维数组A5x8按行优先顺序存储，

2、每个数据元素占2个字节，首地址即元素A00的起始地址为S,则元素A36的起始地址为（）。（2分）A.S+66B.S+60C.S+33D.S+303 .下列叙述中错误的是（）。（2分）A.由树的先序遍历序列和后序遍历序列可以惟一确定一棵树B.二叉树不同于度为2的有序树C.深度为k的二叉树上最少有k个结点D.在结点数目相同的二叉树中，最优二叉树的路径长度最短4 .一棵度为3的树中，度为3的结点有2个，度为2的结点有2个，度为1的结点有2个，则度为0的结点有（）。（2分）A.5个B.6个C.7个D.8个5 .下列叙述中错误的是（）。（2分）A.对数组一般不做插入和删除操作B.顺序存储的数组是一个随机

3、存取结构第1页/共8页C.空的广义表没有表头和表尾D,广义表的表尾可能是原子也可能是子表6 .对稀疏矩阵进行压缩存储的目的是（）。（2分）A.便于进行矩阵运算B.便于输入和输出C.节省存储空间D.降低运算的时间复杂度7 .设广义表L=（a,（）,b,（c,d,e）,贝UHead（Tail（Tail（L）的值为（）。（2分）A.bB.cC.（c）D.（c,d,e）8 .已知二叉树T的先序序列为abdegcfh,中序序列为dbgeachf,则T的后序序列为（）。（2分）A.gedhfbcaB.dgebhfca9 .设有向图G中有五个顶点，各顶点的度分别为分）A.4条B.5条10 .设无向图的顶点个

4、数为n,则该图最多有（C.abcdefghD.acbfedhg3、2、2、1、2,则G中弧数为（）。（2C.6条D.无法确定）条边。（2分）A.n-1B.n(n-1)/2C.n(n+1)/2D.n2二简答题（共2题，总分值20分）11.设二叉树如下，试对其进行先序线索化，画出相应的先序线索二叉树存储结构示意图。12.(10分)设有上三角矩阵伟/.，i=0,1,n-1;j=0,1,n-1,将其上三角元素逐行存于数组Bm中（m充分大），使得Bk=aj,k呈0,求用i和j表示k的下标变换公式。第2页/共8页（10分）三综合题(共3题，总分值60分)（20分）13 .设二叉树以二叉链表存储，试设计算法

5、，实现二叉树的层序遍历。14 .设有AO刖如下，要求：(1)求图中各顶点代表的事件的最早发生时间和最晚发生时间;(2)求图中各弧代表的活动的最早开始时间和最晚开始时间；列出各条关键路径。（20分）15 .设用于通信的电文由8个字母组成，字母在电文中出现的频率分别为0.12、0.31、0.22、0.02、0.03、0.08、0.17、0.05。试为这8个字母设计哈夫曼编码，要求画出设计过程中所构造的哈夫曼二叉树。(20分)第3页/共8页一单选题（共10题，总分值20分，下列选项中有且仅有一个选项符合题目要求，请在答题卡上正确填涂。）1 .答案：D解析过程：2 .答案：B解析过程：3 .答案：D解析过程：4 .答案：C第4页/共8页解析过程：5 .答案：D解析过程：6 .答案：C解析过程：