数据结构期末试卷2.docVIP

　　　　　　　　　　　　　　　　　　　　试卷编号：　　　　（A）卷 数据结构 课程 课程类别：必 开卷(范围)（ A4纸一张 ）：　　　　考试日期：　 题号 一 二 三 四 五 六 七 八 九 十 总分 累分人签名 题分 30 20 38 12 100 得分 考生注意事项：1、本试卷共 7 页，总分　100　分，考试时间　120 分钟。 2、考试结束后，考生不得将试卷、答题纸和草稿纸带出考场。 得分 评阅人 选择题(每题 2 分，共30分) 假设某算法语句总的执行次数为T(n)=6n4+n3,那么该算法的时间复杂性量级为( )。 A) O(2) B) O(n5) C) O(n4) D) O(1) 线性表采用存储结构时，其地址( )。 A) 必须是连续的 B) 部分地址必须是连续的C) 一定是不连续的 D) 连续与否均可以 在顺序线性表（a1,a2,···,a29,a30）中，在a20之前插入一个新的结点，需要将( )个结点后移。 A) 11 B) 20 C) 19 D) 10 带头结点的单循环链表为空的条件是( )。 A)head-next==NULL B) head==NULL C) head-next==head D) head!=NULL 栈S最多能容纳4个元素。现在6个元素按A、B、C、D、E、F的顺序进栈，下列哪一个序列是不可能的出栈序列？( ) A) A、B、C、D、E、F B) A、F、E、D 、C、B C) C、B、E、D、A、F D) C、D、B、F、 E、 A 深度为K的二叉树最多有( )个结点。 A)2K B) 2K–1 C) 2K –1 D) 2K +1 n个顶点的向完全图的弧数为( )。 A) n (n-1) B) n×n C) 2n D) n (n-1) /2 在一个图中，图的边数等于所有顶点的度数之和的( )倍。 A)1/2 B) 1 C) 2 D) 4 图的广度优先遍历类似于二叉树的 A) 先序遍历 B) 中序遍历 C) 层次遍历 D) 后序遍历 在有n个叶子结点的哈夫曼树中，其结点总数为 ( ) 。 A) 不确定 B) 2n C) 2n+1 D) 2n-1 将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号为的结点的左孩子的编号为( ) A) 71 B) 72 C) 73 D) 37 利用逐点插入法建立序列(50，72，43，85，75，20，35，45，65，30)对应的二叉排序树以后，查找元素35要进行（ ）元素间的比较。 A) 4次 B) 5次 C) 7次 D) 10次 在顺序表 ( 3, 6, 8, 10, 12, 15, 16, 18, 21, 25, 30 ) 中，用折半法查找关键码值11，所需的关键码比较次数为： A) 2 B) 3 C) 4 D) 5 链表适用于（ ）查找 A) 顺序 B) 二分法 C) 顺序，也能二分法 D) 随机 和所占用的空间来判断一个算法的优劣。 队列中允许进行删除的一端为 队头 。 在顺序队列中，虽然仍有空闲，但不能进行入队操作，这被称为是 假溢出 。 n个顶点的连通图的生成树有 n-1 条边。 后缀算式79 2 20 + - 6 2 / *的值为_ 171 _。中缀算式（8-X*Y）-4*Y/7对应的后缀算式为__8 X Y* - 4 Y*7/- 。 若要求一个稀疏图G的最小生成树，最好用 克鲁斯卡尔 算法来求解。 若进栈序列为a, b, c，则通过入出栈操作可能得到的a, b, c的不同排列个数为: 5 （备注：abc acb cba bac bca）DS的定义如下，请给出其逻辑结构图示。（5分） DS = (D, R) D = { a