《数据结构》试题及答案（A卷）.docx

《《数据结构》试题及答案（A卷）.docx》由会员分享，可在线阅读，更多相关《《数据结构》试题及答案（A卷）.docx（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构考试试卷（A卷）班级：姓名:学号:分数:题号*四五六七八九十总分得分评卷 人一.单项选择题（每题2分，共30分）（1） 一个栈的入栈序列为1 2 3 4,以下出栈序列不可能得到的是（）1 3 2 4B. 2 3 4 1C. 4 3 12D. 3 4 2 1（2）假设一个二叉树具有10个度为2的结点，那么度为0的结点的个数为（）9 B. 10 C. 11 D.不确定（3）链式结构线性表的特点是：（）A.便于随机存取B.花费的存储空间比顺序结构少C.便于插入和删除D.元素的物理顺序与逻辑顺序一致（4） 一个二叉树的前序遍历序为ABCDEFG,那么中序遍历序可能是：（）CABDEFG B.

2、ABCDEFG C. DACEFBG D. EABCDFG（5）树最适合用来表示（）oA.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据（6）以下有关图遍历的说法中不正确的选项是：（）A.连通图的深度优先搜索是一个递归过程。B.图的广度优先搜索中邻接点的寻找具有“先进先出”的特征。C.非连通图不能用深度优先搜索法。D.图的遍历要求每一顶点仅被访问一次。（7）假设待排序序列基本有序，那么效率最高的排序方法是：（A.直接插入排序B.直接选择排序C.快速排序 D.归并排序（8）对一棵完全二叉树按层次遍历序进行递增编号，根结点编号为1,那么编号为49的结点的 左

3、子的编号是：（）A. 98 B. 99 C. 50 D. 48 （9）以下序列中不符合堆的定义的是：（）A. acdghmpqrxA. acmdhpxgorB. adprcqxmhgC. adcmpghxrq（10）以下排序方法中，相同关键字元素的顺序不会被改变的排序方法是：（） A.希尔排序法B.堆排序法C.快速排序 D.归并排序法（11）在有n个叶结点的哈夫曼树上，结点总数为：（）2n B. 2n+l C. 2nT D.不确定（12）对于关键字值序列（12、13、11、18、60、15、7、18、25、100）建堆，调整的起点是：（）A. 100 B. 12 C. 60 D. 15 (13

4、)以下关键字序列中，是执行完一趟快速排序后得到的序列的是：()A. da, ax, eb, de, bbff ha, gcB. cd, eb, ax, da ff ha, gc, bbC. gc, ax, eb, cd, bbff da, haD. ax, bb, cd, da ff eb, gc, ha_（14）假设从二叉树的任一结点出发到根的路径上所经过的结点序列按其关键字有序，那么该二叉树 是：（）A.二叉排序树B.平衡二叉树 C.堆 D.哈夫曼树（15）在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并A的左 孩子的平衡因子为0右孩子的平衡因子为1,那么应采取的调整型

5、是：（）A. LL B. LR C. RL D. RR二.填空题（每题2分，共20分）（1）通常从四个方面评价算法的质量：、和 o（2）假设用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指 针。在这种存储结构中，n个结点的二叉树共有 个指针域，其中有 个指针域是存放了地址，有 个指针是空指针。（3）A0V网是一种的图。（4）在一个具有n个顶点的无向完全图中，包含有 条边，在一个具有n个顶点的有向完全图中，包含有 条边。三.判断题（每题2分，共30分）（1）由二叉树的前序和后序遍历序可以推导出其中序遍历序。（）（2）线性表的逻辑顺序和物理顺序总是一致的。（）（3）有向图

6、的邻接表结构比邻接矩阵结构要节省空间。（）（4）栈和队列都是限制了读写操作的线性表，只是所施加的限制不同。（）（5）大顶堆（降序堆）是根结点大于其他所有结点的完全二叉树。（）（6）连通图从任意顶点出发进行一趟深度优先遍历，可以访问到图中的所有顶点。（）（7）用二叉链结构存储的一棵n个结点的二叉树上，有n+1个空链。（）（8）二路归并排序的核心操作是将两个有序序列归并为一个有序序列。（）（9）设只有根结点的二叉树高度为1,那么高度为h的二叉树，至多有个结点。（）（10）递归形式的代码一定可以用非递归的形式来实现。（）（11）稳定排序法可以保证排序的效率，不稳定排序法不能保证排序的效率。（）（12

7、）邻接矩阵所需存储空间大小只与结点数有关，与弧的个数无关。（）（13）二叉树中，具有两个子结点的中序后继结点最多只可能有一个子结点。（）（14）假设一棵二叉树的左右子树都是平衡二叉树，那么该二叉树亦为平衡二叉树。（）（15）折半查找法只适用于顺序结构的线性表。（）四.（共10分）请画出以下图的邻接矩阵（5分）和邻接表（5分）。五.某工程包括多个子工程，某些子工程可能存在前期子工程，也就是说，只有当前期子工程都完成后，该子工程才能开始。下面给出各子工程的工期，以及各子工程的前期子工程。请计算总工期的下限，以及哪些子工程是影响总工期的关键子工程，写出计算过程，并简要说 明计算过程。（共10分）子工

8、程名称子工程工期前期子工程A55B90C16BD61A、CE11BF80BG76FH2D、E数据结构考试参考答案(A卷)题号五六七八九总分得分3020301010100一.单项选择题(每题2分，共30分)(4) B(5) C(9) C(10) D(14) C (15) C(I) C(2) C(3) CC(7) A(8) A(II) C (12) C (13) A.填空题(每空2分，共20分)(1)正确性易读性强壮性高效率2n n-ln+1(3)有向无回路n(n-l)/2n(n-l)二 .判断题(每题2分，共30分)(1) N(2) N (3) N (4) Y(5) N(6) Y(7) Y(8)

9、 Y (9) N(10) Y(11) N (12) Y(13) Y (14) N (15) Y01110四.请画出以下图的邻接矩阵和邻接表(共10分)。(1) (5分)邻接矩阵如下所示：-0 11110 10110 110 100 111（2） （5分）邻接表如下所示:2345五、（共10分）由表可知A0E网如下:144计算拓扑序、ve vl如下:拓扑序021345ve090106167170246vl090183244170246计算e、1如下:子工程名称子工程工期e1A550128B9000C1690167D61106183E1190233F809090G76170170H2167244因此，总工期下限为246 关键子工程为：B、F、G