2017年青岛大学数据结构与算法基础考研真题921.pdf0页

2017年青岛大学数据结构与算法基础考研真题921.pdf1 青 岛大 学 2017 年 硕士 研究 生 入学 考试 试题 科 目 代 码 ： 9 2 1 科 目 名 称 ： 数 据 结 构 与 算 法 基 础 （ 共 5 页 ） 请 考 生 写 明 题 号 ， 将 答 案 全 部 答 在 答 题 纸 上 ， 答 在 试 卷 上 无 效 一、 单项 选择题 （共 15 小题 ，每 小题 2 分， 共 30 分） 1. 以下时间复杂度 T ( n) 最高的是： A . T ( n) = 666n + 999 B . T ( n) = 100n 2 C . T ( n) = 2 n D . T ( n) = 22223nlog 2 n 2. 二叉树 T 中度为 2 的结点有 2016 个，则 T 中叶子结点有： A . 2015 个 B . 2016 个 C . 2017 个 D . 以上都不对 3. 逆波兰式 ( 后缀式 ) 10 25 5 / - 2 * 8 3 - / 的值是： A . 2 B . 0 C . 1 D . 6 4. 元素 A B C D E 依次入栈，则以下( ) 是不可能的出栈次序。 A . A B C D E B . E D C B A C . A C B D E D . D A B C E 5. 对于有 N 个结点的二叉搜索树( B i na r y S e a r c h T r e e ) ， 以下说法正确的是： A . 在此树中查找值为 x 的结点的时间复杂度是 O (log N ) 。 B . 将此树的每个结点的左右儿子结点互换， 产生的新树依然是一棵二 叉搜索树。 C . 此树中值最大的结点一定在右子树。 D . 此树中值最小的结点一定不在右子树。 6. 一 个 具 有 N 个 顶 点 的 无 向 连 通 图 G ， 其 生 成 树 为 T ， 以 下 说 法 正 确 的 是： A . 该生成树一定是唯一的。 B . 该生成树可能不唯一，但不同生成树各边的权值之和是相等的。 C . 生成树 T 一定具有 N - 1 条边。 D . 生成树 T 是图 G 的极大连通子图。 7. 二叉树的第 k( k> = 1) 层的结点数最多为： A ． 2 k - 1 B .2k+ 1 C .2k- 1 D . 2 k - 1 8. 下列排序算法中，其中（ ）是稳定的