2014(1)数据结构-A-试题.pdf

南阳理工学院 2013 2014学年第 2 学期试卷 A 卷 课程 数据结构 课程 数据结构 课程号 课程号 1504108130 考核方式 闭卷 课程性质 专业必修课 适用对象 12 级软件工程专业 题号 一 二 三 四 五 总分 复核人 满分 20 20 10 30 20 100 得分 一 选择题 每题 2 分 共 20 分 1 设某数据结构的二元组形式表示为 A D R D 01 02 03 04 05 06 07 08 09 R 则数据结构 A 是 A 线性结构 B 树型结构 C 物理结构 D 图型结构 2 栈和队列的共同特点是 A 只允许在端点处插入和删除元素 B 都是先进后出 C 都是先进先出 D 没有共同点 3 在头指针为 head 的循环链表中 判断指针变量 P 指向尾结点的条件是 A p next next head B p next head C p next next NULL D p next NULL 4 在单链表中 要将 s 所指结点插入到 p 所指结点之后 其语句应为 A s next p 1 p next s B p next s s next p next C s next p next p next s next D s next p next p next s 5 数组 Q n 用来表示一个循环队列 f 为当前队列头元素的前一位置 r 为队尾 元素的位置 假定队列中元素的个数小于 n 计算队列中元素个数的公式为 A r f B n f r n C n r f D n r f n 6 设有数组 A 0 7 0 9 数组的每个元素长度为 2 字节 数组从内存首地址 1000 开始顺序存放 当用以行为主存放时 元素 A 5 8 的存储首地址为 A 1116 B 1094 C 1138 D 1120 7 若对 n 阶对称矩阵 A 以行序为主序方式将其下三角形的元素 包括主对角线上 所有元素 依次存放于一维数组 B 1 n n 1 2 中 则在 B 中确定 aij i j 且 i j 1 2 n 的位置 k 的关系为 A i i 1 2 j B j j 1 2 i C i i 1 2 j D j j 1 2 i 8 串是一种特殊的线性表 其特殊性体现在 A 可以顺序存储 B 数据元素是一个字符 C 可以链式存储 D 数据元素可以是多个字符若 评卷人 得分 第 1 页 共 4 页 9 用带有头结点的链式方式存储的队列 在进行插入运算时 A 仅修改头指针 B 头 尾指针都要修改 C 仅修改尾指针 D 头 尾指针可能都要修改 10 无向图中所有顶点的度数之和与所有边数之比是 A 1 2 B 1 C 2 D 4 二 填空题 每空 2 分 共 20 分 1 若在长度为 n 的顺序表第 i 个元素之前插入一个元素 则需 要向后移动的元素个数是 2 队列只能在队尾进行插入操作 在队首进行 操作 3 广义表 A x y z a b 则函数 head head tail A 的值是 4 以权值分别为 8 6 3 4 5 的五个叶子结点构成的哈夫曼树 其带权路径长 度 WPL 是 5 己知散列表表长 m 11 散列函数 h key key 11 表中存有三个关键字 15 27 39 其余地址为空 若采用线性探查法处理冲突 则关键字为 60 的结点 保存的下标位置是 6 一棵 4 阶的 B 树中结点的关键字个数最多 个 7 头指针为 L 的带头结点的双循环链表 结点的前趋指针域为 prior 后继指针 域为 next 判断该链表为空的条件是 8 在一个具有 n 个结点的线索二叉树中有 个指针是用来作为线索处 理的 9 若无向图中任意两个不同的顶点间都有路径 则称该图为 10 在计算机中通常作为一个整体进行考虑和处理的数据的基本单位是 三 判断题 每题 2 分 共 10 分 1 线性表 L a1 a2 an 中诸元素的排列必须是由小到大或由大到小 2 在静态查找中 顺序查找的平均查找长度为 n 1 2 元素可以采用顺序存 储或者链式存储 3 在一个具有 n 个单元的顺序栈中 假设以地址低端作为栈底 以 top 作为栈顶 指针 则当作进栈处理时 top 的变化为 top 4 已知一棵完全二叉树的第 7 层有 10 个叶子结点 则整个二叉树的结点个数最 多是 73 5 一棵二叉树的先序遍历序列为 ABDGCEHF 中序遍历序列为 DGBAEHCF 其后序遍历序列为 GDBHEFCA 评卷人 得分 评卷人 得分 第 2 页 共 4 页 四 应用题 每题 6 分 共 30 分 1 用 X 代表进栈操作 S 代表出栈操作 给出利用栈将字符串 a b c 改变为 ab c 的操作步骤 例如 将 ABC 改变为 BCA 则其操作步骤为 XXSXSS 2 设图以邻接表存储 如右图所示 1 写出从顶点 v1 出发图的深度优先搜索遍历序列 2 写出从顶点 v1 出发图的广度优先搜索遍历序列 3 己知无向网 G V E 其中 V A B C D E 该网的邻接矩阵如下图所 示 要求 1 画出对应的无向网 G 2 画出无向网 G 的最小生成树 4 在一棵空的二叉排序树中依次插入关键字序列为 100 60 80 90 120 110 130 请画出所得到的二叉排序树 并求其在等概率的情况下查找成功的平均 查找长度 ASL 5 给出对序列 12 2 16 30 28 10 16 20 6 18 进行二路归并排序时每一趟的 结果 并判断其稳定性如何 评卷人 得分 第 3 页 共 4 页 五 算法设计题 每题 10 分 共 20 分 1 Please write S