【渝粤教育】国家开放大学2018年春季 0025-22T数据结构 参考试题

编号：0025 座位号：
17-18学年第1学期期末考试
数据结构 试题

一、选择题：（每题2分，共20分）

在一个单链表中，在p所指结点的后继位置插入一个由q指向的新结点，则需实现以下步骤：首先将新结点连接到当前列表中。具体而言：A选项表示将新结点作为当前列表中的后续元素；B选项则表明先调整新结点与原后续元素的关系；C选项则是重新设置相关指针以完成插入操作；D选项描述了一种重新配置现有指针的方式以实现目标。

在稀疏矩阵的交叉链式存储中，每个行单链表中的节点都具有相同的关键属性。具体来说：
A项为元素值，
B项为行列索引之一，
C项为对应的列索引，
D项为存储位置标识。

3．栈的插入和删除操作在＿＿＿进行．
Ａ．栈顶 Ｂ．栈底
Ｃ．任意位置 Ｄ．指定位置

4．在一棵高度为４的二叉树，最多含有＿＿个结点。
A．8 B．12
C．16 D．15

5．根据下列二叉树遍历的结果为C,D,B,G,F,E,A，则此遍历为＿＿。

A A．前序
B E B．中序
C D F C．后序
G D．层次

二、填空题：（每空2分，共20分）

1．在线性结构，树结构和图结构中，前驱和后继结点分别存在着________、 ________和________的联系。

在一棵二叉排序树中，在每个分支结点处的所有左子树上的节点数值必须不大于该分支结点数值，在其所有右子树上的节点数值必须不小于该分支结点数值

3．由4个顶点构成的无向完全图中共有6条边，在一个由n个顶点构成的有向完全图中共有n(n-1)条边。

对于包含n个顶点与e条边的有向图与无向图，在采用边集数组表示时，则存储在数组中的边数分别为O(n^2)和O(e)。

5．假定一组记录的排序码为（４６,７９,５６,３８,４０,８４），则利用堆排序方法建立的初始堆为___________________________________。

三、问答题：（共40分）

已知一个后缀算术表达式如下：
6\ 3\ 20\ 5／＊8－6＊＋＠ （共20分）
（1）请将相应的中缀算术表达式转换出来；
（2）请描述在对上述后缀表达式进行求值过程中数值栈的变化过程。

给定一组数据序列(36,\ 25,\ 48,\ 12,\ 65,\ 20)
，
采用直接插入排序法将每个数据项依次插入到其前有序序列中的适当位置后得到的最终排列结果是什么？
（共20分）

四、阅读算法，写出执行后的结果（20分）

队列Q初始化为空；
初始化队列Q；
创建整型数组a，并初始化为{5,8,12,15}；
对数组a中的每个元素依次执行入队操作；
将队列删除后的结果再次入队；
将数值30加入队列中；
将队列删除后的结果加10后再入队；
当队列不为空时，持续输出队列头元素并移除该元素；

结果为：_________________________________。