数据结构第2阶段练习题答案 2022秋下半年江南大学限时机考考前复习资料

第11页/共NUMPAGES\*ARABIC11页江南大学网络教育第二阶段练习题的参考答案选择为，在文档最后考试科目:《数据结构》第章至第章（总分100分）__________学习中心（教学点）批次：层次：专业：学号：身份证号：姓名：得分：一单选题(共10题，总分值20分，下列选项中有且仅有一个选项符合题目要求，请在答题卡上正确填涂。)1.设有向图G中有五个顶点，各顶点的度分别为3、2、2、1、2，则G中弧数为（）。（2分）A.4条B.5条C.6条D.无法确定2.下列叙述中错误的是（）。（2分）A.对数组一般不做插入和删除操作B.顺序存储的数组是一个随机存取结构C.空的广义表没有表头和表尾D.广义表的表尾可能是原子也可能是子表3.下列叙述中错误的是（）。（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.设有无向图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,b6.设无向图的顶点个数为n，则该图最多有（）条边。（2分）A.n-1B.n(n-1)/2C.n(n+1)/2D.n27.设二维数组A5×8按行优先顺序存储，每个数据元素占2个字节，首地址即元素A[0][0]的起始地址为S，则元素A[3][6]的起始地址为（）。（2分）A.S+66B.S+60C.S+33D.S+308.已知二叉树T的先序序列为abdegcfh，中序序列为dbgeachf，则T的后序序列为（）。（2分）A.gedhfbcaB.dgebhfcaC.abcdefghD.acbfedhg9.对稀疏矩阵进行压缩存储的目的是（）。（2分）A.便于进行矩阵运算B.便于输入和输出C.节省存储空间D.降低运算的时间复杂度10.设广义表L=((a,()),b,(c,d,e))，则Head(Tail(Tail(L)))的值为（）。（2分）A.bB.cC.(c)D.(c,d,e)二多选题(共5题，总分值10分，下列选项中至少有2个或2个以上选项符合题目要求，请在答题卡上正确填涂。)11.下列不属于数组的主要操作的是（）。（2分）A.存取;B.修改;C.插入;D.删除;E.查找12.下列说法正确的是（）。（2分）A.线性表中数据元素之间仅有线性关系;B.在图形结构中节点间的关系可以是任意的;C.简单路径中序列中顶点可以重复出现;D.邻接表是图的一种链式存储结构13.以下说法正确的是（）（2分）A.二叉树的特点是每个结点至多只有两棵子树;B.二叉树的子树无左右之分;C.二叉树只能进行链式存储;D.树的结点包含一个数据元素及若干指向其子树的分支14.图的应用算法有（）。（2分）A.克鲁斯卡尔算法;B.哈弗曼算法;C.迪杰斯特拉算法;D.拓扑排序算法15.完全二叉树（）。（2分）A.适合于顺序结构存储;B.不一定适合顺序结构存储;C.叶子结点可在任一层出现;D.某些结点有右子树则必有左子树三判断题(共10题，总分值10分正确的填涂“A”，错误的填涂“B”。)16.连通图的生成树包含了图中的所有顶点。（1分）（

）17.用邻接表法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关。（1分）（

）18.在含有n个结点的树中，边数只能是n-1条。（1分）（

）19.设深度为d（只有一个根结点时，d为1）的二叉树只有度为0和2的结点，则此类二叉树的结点数至少为2d-1。（1分）（

）20.有向图的邻接矩阵一定是不对称的。（1分）（

）21.二叉树通常有顺序存储结构和链式存储结构。（1分）（

）22.图的深度优先遍历非递归算法通常采用队列实现，广度优先遍历非递归算法通常采用堆栈实现。（1分）（

）23.对N（≥2）个权值均不相同的字符构造哈夫曼树，则树中任一非叶结点的权值一定不小于下一层任一结点的权值。（1分）（

）24.某二叉树的后序和中序遍历序列正好一样，则该二叉树中的任何结点一定都无右孩子。（（1分）（

）25.AOE图的关键路径就是最长的路径。（1分）（

）四简答题(共2题，总分值20分)26.设二叉树如下，试对其进行先序线索化，画出相应的先序线索二叉树存储结构示意图。（10分）27.设有上三角矩阵(aij)n×n，i=0,1,…,n-1;j==0,1,…,n-1,将其上三角元素逐行存于数组B[m]中（m充分大），使得B[k]=aij，k≧0,求用i和j表示k的下标变换公式。（10分）五综合题(共3题，总分值40分)28.设有AOE网如下，要求：(1)求图中各顶点代表的事件的最早发生时间和最晚发生时间；(2)求图中各弧代表的活动的最早开始时间和最晚开始时间；(3)列出各条关键路径。（14分）29.设用于通信的电文由8个字母组成，字母在电文中出现的频率分别为0.12、0.31、0.22、0.02、0.03、0.08、0.17、0.05。试为这8个字母设计哈夫曼编码，要求画出设计过程中所构造的哈夫曼二叉树。（13分）30.设二叉树以二叉链表存储，试设计算法，实现二叉树的层序遍历。（13分）

一单选题(共10题，总分值20分，下列选项中有且仅有一个选项符合题目要求，请在答题卡上正确填涂。)1.参考答案选择为：B解析过程：2.参考答案选择为：D解析过程：3.参考答案选择为：D解析过程：4.参考答案选择为：C解析过程：5.参考答案选择为：D解析过程：6.参考答案选择为：B解析过程：7.参考答案选择为：B解析过程：8.参考答案选择为：B解析过程：9.参考答案选择为：C解析过程：10.参考答案选择为：D解析过程：二多选题(共5题，总分值10分，下列选项中至少有2个或2个以上选项符合题目要求，请在答题卡上正确填涂。)11.参考答案选择为：C,D解析过程：12.参考答案选择为：A,B,D解析过程：13.参考答案选择为：A,D解析过程：14.参考答案选择为：A,C,D解析过程：15.参考答案选择为：A,D解析过程：三判断题(共10题，总分值10分正确的填涂“A”，错误的填涂“B”。)16.参考答案选择为：T解析过程：17.参考答案选择为：F解析过程：18.参考答案选择为：T解析过程：19.参考答案选择为：T解析过程：20.参考答案选择为：F解析过程：21.参考答案选择为：T解析过程：22.参考答案选择为：F解析过程：23.参考答案选择为：T解析过程：24.参考答案选择为：T解析过程：25.参考答案选择为：T解析过程：四简答题(共2题，总分值20分)26.参考答案选择为：答：解析过程：27.参考答案选择为：答：解析过程：五综合题(共3题，总分值40分)28.参考答案选择为：关键路径１：v1→v2→v5→v7关键路径２：v1→v3→v6→v7解析过程：29.参考答案选择为：编码：0.02:001000.03:001010.05:00110.08:0000.12:1000.17:1010.22:010.31:11解析过程：30.参考答案选择为：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所指结点的