2017年北京交通大学02201数据库原理(同等学力加试)复试仿真模拟三套题
● 摘要
一、应用题
1． 试证明：同一棵二叉树的所有叶结点，在前序序列、对称序序列以及后序序列中都按相同的
，例如前序后序运对称序。 相对位置出现（即先后顺序相同）
，中序遍历是“左根右”，后序遍历是“左右根”【答案】前序遍历是“根左右”。三种遍历中
只是访问 " 根”结点的时机不同，对左右子树均是按左右顺序来遍历的，因此所有叶子都按相同的相对位罝出现。
2． 将下列出三棵树组成的森林转换为二叉树（只要求给出转换结果）。
图1
【答案】森林转换为二叉树分以下三步：
（1）连线（将兄弟结点相连，各树的根看作兄弟）。
（2）切线（保留最左边子女为独生子女，将其他子女分支切掉）。
（3）旋转（以最左边树的根为轴. 顺时针向下旋转45度）。
所以由上面三棵树转换得到的二叉树如图2所示：
图2
3． 对给定文件（28，07，39，10，65，14，61，17，50，21）选择第一个元素28进行划分，写出其快速排序第一遍的排序过程。
【答案】快速排序的思想如下：首先将待排序记录序列中的所有记录作为当前待排序区域，
，凡其关键字不大干枢轴的记录均移动至该记录之前，以第一个记录的关键字作为枢轴（或支点）
凡关键字不小于枢轴的记录均移动至该记录之后。致使一趟排序之后，记录的无序序
割成两部分：和和
且
将分然后再递归地将进行快速排序。快速排序在记录有序时蜕变为起泡排序，可用“三者取中”法改善其性能，避免最坏情况的出现。本题解答如下：
初始序列：[28]，07，39，10，65，14，61，17，50，21
21移动：21，07，39，10，65，14，61，17，50，[]
39移动：21，07，[]，10，65，14，61，17，50，39
17移动：21，07，17，10，65，14，61，[]，50，39
65移动：21，07，17，10，[]，14，61，65，50，39
14移动：21，07，17，10，14，[28]，61，65，50，39
4． 假设Internet 的两个自治系统构成网络如题图所示，自治系统ASI 由路由器R1连接两个子网构成；自治系统AS2由路由器R2、R3互联并连接3个子网构成。各子网地址、R2的接口名、R1与R3的部分接口 IP 地址如题图所示。请回答下列问题。
题图网络拓扑结构
（1）假设路由表结构如下所示。请利用路由聚合技术，给出R2的路由表，要求包括到达题图中所有子网的路由，且路由表中的路由项尽可能少。
（2）若R2收到一个目的IP 地址为194.17.20.200的IP 分组，R2会通过哪个接口转发该IP 分组？
R1与R2之间利用哪个路由协议交换信息？该路由协议的报文被封装到哪个议的分组中（3）
进行传输？
【答案】
（1）在AS1中，子网和子网可以聚合为子网在AS2
中，子
网和子网单独连接到的接口可以聚合为子网但缺少子网
于是可以得到R2的路由表如下：
（2）该IP 分组的目的IP 地址194.17.20.200与路由表中194.17.20.0/23和194.17.20.128/25两个路由表项均匹配，根据最长匹配原则，R2将通过E0接口转发该1P 分组。
（3）R1与R2之间利用BGP4 （或BGP ）交换路由信息；BGP4的报文被封装到TCP 协议段中进行传输。2012年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专此基础综合真题及详解
5． 请写出应填入下列叙述中（ ）内的正确答案。
排序有各种方法，如插入排序、快速排序、堆排序等。
设一数组中原有数据如下：15，13，20，18，12，60。下面是一组用不同排序方法进行一遍排序后的结果。
（ ）排序的结果为：12，13，15，18，20，60
（ ）排序的结果为：13，15，18，12，20，60
（ ）排序的结果为：13，15，20，18，12，60
（ ）排序的结果为：12，13，20，18，15，60
【答案】①快速排序②起泡排序③直接插入排序④堆排序
相关内容
相关标签