数据结构试卷2006~2007B.doc

2005—2006学年第一学期考试卷 　　　　　　　　　　　　　　　　　　　　试卷编号：　　　　（B）卷 数据结构 课程 课程类别：必 开卷(范围)（教材）：　　　　　考试日期：　　　　 题号 一 二 三 四 五 六 七 八 九 十 总分 累分人签名 题分 10 30 15 30 15 100 得分 考生注意事项：1、本试卷共 页，总分　　分，考试时间　　　分钟。 2、考试结束后，考生不得将试卷、答题纸和草稿纸带出考场。 判断题：正确在（）内打√，否则打×(每题1分，共10分) 数据的逻辑结构与数据元素本身的内容和形式无关。( ) 在单链表中，头结点是必不可少的。( ) 顺序存储结构只能存线性结构。链式存储结构只能存非线性结构。( ) 如果两个串含有相同的字符，则这两个串相等。( ) 二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字值，且小于其右非空子树（若存在的话）所有结点的关键字值。( ) 一个图的邻接矩阵表示法是唯一的，而邻接表表示法是不唯一的。( ) 拓扑排序是指结点的值是有序排列。( ) 线性结构只能用顺序结构存放，非线性结构只能用链表存放。( ) 哈夫曼树中没有度为1的结点，所以必为满二叉树。( ) 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。( ) 选择题(每题 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 深度为K的二叉树最多有( )个结点。 A)2K B) 2K–1 C) 2K –1 D) 2K +1 带头结点的单循环链表为空的条件是( )。 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 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，则编号为49的结点的左孩子的编号为( ) A) 98 B) 99 C) 50 D) 48 利用逐点插入法建立序列(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) 顺序，也能