资源描述
- 2018 试 题 1/6 -2018 年 上 海 海 事 大 学 攻 读 硕 士 学 位 研 究 生 入 学 考 试试题（重要提示：答案必须做在答题纸上，做在试题上不给分）考试科目代码 828 考试科目名称 数据结构及程序设计 一判断题（本题 10 分，每小题 1 分）1. 线 性 的 数 据 结 构 可 以 顺 序 存 储 ， 也 可 以 链 接 存 储 。 非 线 性 的 数 据 结 构 只能链接存储。2. 单链表从任何一个结点出发，都能访问到所有结点。3. 单 链 表 形 式 的 队 列 ， 头 指 针 F 指 向 队 列 的 第 一 个 结 点 ， 尾 指 针 R 指 向 队列的最后一个结点。4. 若 在 采 用 链 式 存 储 结 构 线 性 表 中 ， 元 素 按 值 有 序 ， 则 该 线 性 表 可 以 采 用折半查找法查找元素。5. 一 个 栈 的 输 入 序 列 为 1, 2, 3, , n， 其 输 出 序 列 的 第 二 个 元 素 为 n 的 输 出序 列 的 个 数 有 n-1 种。6. 设 串 S 的 长 度 为 n， 则 S 的 子 串 个 数 为 n(n+1)/2。7. 若一个广义表的表头为空表，则此广义表亦为空表。8. 二 叉 树 中 除 叶 节 点 外 ， 任 一 节 点 x， 其 左 子 树 根 节 点 的 值 小 于 该 节 点 (x)的 值 ， 其 右 子 树 根 节 点 的 值 大 于 该 节 点 (x)的 值 ， 则 此 二 叉 树 一 定 是 二 叉 排 序 树 。9. 网络的最小代价生成树是唯一的。10 （ 99, 86, 46, 70, 34, 39, 45, 58, 66, 10 ）是堆。二填空题（本题 20 分，每空 2 分）1. 一个栈的输入序列是：1、2、3，则不可能的栈输出序列是 。- 2018 试 题 2/6 -2. 将整型数组 A1.8, 1.8按行优先次序存储在 起始地址为 1000 的连 续内存单元中，则元素 A7, 3的地址是： 。3 已知广义表 A=( 9, 7, ( 8, 10, ( 99 ) ), 12 )，取表头和表尾的操作为 head( )和 tail( )，则将原子元素 99 从 A 中取出来的操作为 。4. 已 知 一 棵 度 为 3 的 树 有 2 个 度 为 1 的 结 点 ， 3 个 度 为 2 的 结 点 ， 4 个度为3 的结点，则该树有 个叶子结点。5. 已知二叉树先根序序列为 ABDEGCF，中根序序列为 DBGEACF，则后根序序列为 。6. 已知一无向图 G=（ V， E） ， 其中 V= a, b, c, d, e E= (a, b), (a, d), (a, c), (d, c), (b, e) ， 现用某一 种图遍历方法从顶点 a 开始遍历图， 得到的序列为 abecd，则采用的是 遍历方法。7. 己知有序表为( 11, 18, 25, 32, 46, 50, 62, 85, 90, 115, 134 )，用二分法查找46 时，需 次查找成功，查 100 时，需 次才能确定不成功。8 分别采用堆排序， 快速排序， 冒泡排序和归并排序， 对初态为有序的表， 则最省时间的是 算法，最费时间的是 算法。三选择题（本题 30 分，每空 2 分）1 用二进制文件和文本文件存储整型数-8765 时， 各占用 （ ） 个字节。A2 和 2 B2 和 5 C5 和 5 D5 和 2 2设有定义语句 char s=“123“; 则表达式 s3的值是（ ） 。A1 B3 C0 D语法出错3执行下列程序段后的输出结果是（ ） 。x = 9；while ( x 7 ) printf(“*“); x-; - 2018 试 题 3/6 -A* B* C* D * 4设 int m=1, n=2; 则 m+ = = n 的结果是（ ） 。A0 B1 C2 D35以下程序段（ ） 。x = -1;dox = x * x; while ( ! x );A.是死循环 B.循环执行二次 C.循环执行一次 D.有语法错误6已知一算术表达式的中缀形式为 A+B*C-D/E，后缀形式为 ABC*+DE/-，其前缀形式为（ ） 。A-A+B*C/DE B-A+B*CD/E C-+*ABC/DE D -+A*BC/DE7 线性表采用链式存储时，结点的存储地址（ ） 。A必须是不连续的 B连续与否均可C必须是连续的 D和头结点的存储地址相连续 8 判定一个循环队列 QU（ 最多元素为 m0）为满队列的条件 是 （ ） 。AQU.front = = (QU.rear+1)%m0 BQU.front != (QU.rear+1)%m0 CQU.front = = QU.rear DQU.front != QU.rear+1 9设广义表 L= ( ( a, b, c ) )，则 L 的长度和深度分别为（ ） 。A1 和 1 B1 和 3 C1 和 2 D2 和 310一棵二叉树度为 2 的结点有 10 个，则度为 0 的结点有（ ）个。A9 B 11 C12 D不确定11 具有 n ( n 1 ) 个顶点的强连通图至少有（ ）条弧。A B3 49 7C 7 D5 812E 6 F11 - 2018 试 题 104/6 -GAn+1 Bn Cn-1 D2(n-1)12具有 n 个顶点和 e 条边的无向图的邻接矩阵中有（ ）个零元素。Ae B2e Cn 2-e Dn 2-2e13 无 向 图 G=(V, E)中 V=a, b, c, d, e, f， E=(a, b), (a, c), (a, d), (b, e), (c, f) , (d, e), (d, f) ，对该图进行广度优先遍历得到的顶点序列正确的是（ ） 。Aa,e,d,f,c,b Ba,c,f,e,b,d Ca,e,b,c,f,d Da,b,d,c,e,f 14直接插入排序在最好情况下的时间复杂度为（ ） 。AO(logN) BO(N) CO(N*logN) DO(N*N) 15 若 查 找 每 个 记 录 的 概 率 均 等 ， 则 在 具 有 n 个 记 录 的 连 续 顺 序 文 件 中 采 用顺序查找法查找一个记录，其平均查找长度 ASL 为（ ） 。A(n-1)/2 Bn/2 C(n+1)/2 Dn四应用题（本题 60 分，每小题 10 分）1. 右图是一个有向图，试回答下列问题：1） 给出它的邻接表存储表示；2） 写出其所有可能的拓扑序列。2. 某通信系统中共包含八个字母：G 、 U、 Z、O 、N 、G 、R 、 D，各个字符出现频率分别为：21%、 8%、 15%、 9%、 18%、 10%、 6%、 13%，试为它们构 造 一 棵 Huffman 树（ 哈夫曼树） ，并求出这些字符的哈夫曼编码。3. 试分别用普里姆算法和克鲁斯卡尔算法求 右 图 的 最 小 生 成 树 （给 出 最 小 生 成 树 中 各 条 边加 入 的 先 后 顺 序 ， 连 接 顶 点 x 和 y 的边用A BC DE F- 2018 试 题 5/6 -形式表示） ，并求出最小生成树的代价（即各条边权值之和） 。1） 普 里 姆 算 法 从 顶 点 D 出发；2） 克鲁斯卡尔算法；3） 最小生成树的代价。4 有 关 键 码 序 列 38、 53、 14、 33、 76、 47、 65、 42、 25、 54、 82 ， 采 用散 列 函 数 H(key) = key % 11 存 储 在 散 列 表 HT0.12中 ， 并 用 线 性 探 测 再 散 列 法解 决 冲 突 ， 试 解 下 列 问 题 ：1） 画 出 依 次 插 入 以 上 11 个关键码后的散列表。2） 计算在等概率情况下查找成功时的平均查找长度。5. 右图为一棵二叉树，试回答下列问题：1） 写出该二叉树的中根序序列；2） 画出该二叉树的顺序存储表示；3） 画 出 该 二 叉 树 的 中 根 序 线 索 二 叉 链 表 存 储 表示。6. 有一组待排序记录的关键字分别为 495、725、321、682、586、216、412、278、365、532、438、192、627 ，试采用下列方法按关键字值递增的次序进行排序：1） 步 长 为 5、3、1 的 Shell 排序；2） 归并排序。五编程题（本题 30 分，每小题 10 分）1 试 编 写 一 个 函 数 sum( n ) 计 算 满 足 下 式 的 最 大 m：AB CD E FG H K- 2018 试 题 6/6 -1*2 + 2*3 + 3*4 + . + (m-1)*m = n2 有 一 个 带 头 结 点 的 链 表 存 储 学 生 成 绩 score， 试 编 写 函 数 计 算 链 表 所 有 记录 中 的 最 高 成 绩 max、 最 低 成 绩 min 和 平 均 成 绩 aver， 链 表 的 存 储 结 构 为 ： typedef struct Node char name;float score;struct Node *next; Node, *List;3 编 写 函 数 exchange( ) 计算二叉树的高度并将其每一个结点的左孩子与右孩子对调，设二叉树采用二叉链表存储：typedef struct BTNode ElemType data;struct BTNode *lchild, *rchild;BTNode,*BTree;
展开阅读全文