2017年东北理工大学数据结构(同等学力加试)复试实战预测五套卷
● 摘要
一、应用题
1． 我们知道，对于n 个元素组成的线性表进行快速排序时，所需进行的比较次数与这n 个元素的初始排序有关。问：
（1）当n=7时，在最好情况下需进行多少次比较? 请说明理由。
（2）当n=7时，给出一个最好情况的初始排序的实例。
（3）当n=7时，在最坏情况下需进行多少次比较? 请说明理由。
（4）当n=7时，给出一个最坏情况的初始排序的实例。
【答案】（1）在最好情况下，每次划分能得到两个长度相等的子文件。假设文件的长度那么第一趟划分得到两个长度均为
以此类推，
总共进行
需2次，共10次即可。
（2）在最好情况下快速排序的原始序列实例：4，1，3，2，6，5，7。
（3）在最坏情况下，若每次用来划分的记录的关键字具有最大（或最小）值，那么只能得到左（或右）子文件，其长度比原长度少1。因此，若原文件中的记录按关键字递减次序排列，而要求排序后按递増次序排列时，快速排序的效率与起泡排序相同，其时间复杂度为
n=7时，最坏情况下的比较次数为21次。
（4）在最坏情况下快速排序的初始序列实例：7，6，5，4，3，2，1，要求按递増排序。
2． 分析ISAM 文件（IndeXed Sequential Access Methord）和VSAM 文件（Virtual storage Access Methord ）的应用场合、优缺点等。
【答案】ISAM 是一种专为磁盘存取设计的文件组织形式，采用静态索引结构，对磁盘上的数据文件建立盘组、柱面、磁道三级索引。ISAM 文件中记录按关键字顺序存放，插入记录时需移动记录并将同一磁道上最后的一个记录移至溢出区，同时修改磁道索引项，删除记录只需在存储位置作标记，不需移动记录和修改指针。经过多次插入和删除记录后，文件结构变得不合理，需周期整理ISAM 文件。
VSAM 文件采用动态索引结构，文件只有控制区间和控制区域等逻辑存储单位，与外存储
树，作为文件的索引部分可实现顺链查找和从器中柱面、磁道等具体存储单位没有必然联系。VSAM 文件结构包括索引集、顺序集和数据集三部分，记录存于数据集中，顺序集和索引集构成
根结点开始的随机查找。
优缺点：与ISAM 文件相比，VSAM 文件有如下优点：动态分配和释放存储空间，不需对文件进行重组；能保持较高的查找效率，且查找先后插入记录所需时间相同。因此，基于
的子文件，第二趟划分得到4个长度均为的子文件，趟划分，各子文件的长度均为1，排序完毕。当n=7时，k=3，在最好情况下，第一趟需比较6次，第二趟分别对两个子文件（长度均为3，k=2）进行排序，各所以当的VSAM
文件通常作为大型索引顺序文件的标准组织。
3． （1）如果G1是一个具有n 个顶点的连通无向图，那么G1最多有多少条边?G1最少有多少条边？
（2）如果G2是一个具有n 个顶点的强连通有向图，那么G2最多有多少条边?G2最少有多少条边？
（3）如果G3是一个具有n 个顶点的弱连通有向图，那么G3最多有多少条边?G3最少有多少条边？
1）G1最多n （n-l ）/2条边，最少n-1条边。 【答案】（
（2）G2最多n （n-l ）条边，最少n 条边。
（3）G3最多n （n-l ）条边，最少n-1条边。
4． 下面程序段的时间复杂度是什么？
【答案】赋值语句一共被执行了m*n次，所以该程序段的时间复杂度是O （m*n）。
5． 试举一例，说明对相同的逻辑结构，同一种运算在不同的存储方式下实现，其运算效率不同。
【答案】线性表中的插入、删除操作，在顺序存储方式下平均移动近一半的元素，时间复杂度为O （n ）; 而在链式存储方式下，插入和删除时间复杂度都是0（1）。
6． 某计算机字长16位，主存地址空间大小为128KB , 按字编址，采用单字长指令格式，指令各字段定义如下：
源操作数目的操作数
转移指令采用相对寻址方式，相对偏移量用补码表示，寻址方式定义如下：
注：（X ）表示存储器地址X 或寄存器X 的内容。请回答下列问题：
（1）该指令系统最多可有多少条指令? 该计算机最多有多少个通用寄存器? 存储器地址寄存器（MAR ）和存储器数据寄存器（MDR ）至少各需要多少位？
（2）转移指令的目标地址范围是多少？
（3）若操作码0010B 表示加法操作（助记符为add ）, 寄存器R4和R5的编号分别为100B 和101B ，R4的内容为1234H ，R5的内容为5678H , 地址1234H 的内容为5678H ，地址5678H 中的内容为1234H ，则汇编语句
改变后的内容是什么？
【答案】（1）指令操作码占4位，则指令系统最多可有
量为128KB ，计算机字长为16位，故主存有
需16位。
（2）由于寄存器字长为16位，所以转移指令的目标地址范围为0000H 〜FFFFH 。。
（3）汇编语句
寄存器
R5和地址为5678H 的存储单元的内容会改变，改变后的内容分别为
：
7． 队列可以用循环单链表来实现，故可以只设置一个头指针或者只设置一个尾指针。请你分析对于循环单链表实现的队列，用哪种方案更合适。
【答案】循环单链表若只设头指针，则出队操作时间复杂度是
是若只设尾指针，则出队和入队操作时间复杂度都是而如对操作时间复杂度
因此，用循环单链表来实现队 +对应的机器码为该指令执行后，条不同的指令；指令操作上占6个通用寄存器；主存容个存储单元，故MDR 和MAR 至少各位，寻址方式占3位，于是寄存器编号占3位，该计算机最多可以有（逗号前为源操作数，逗号后为目的操作数）对应的机器码是什么（十六进制表示）？该指令执行后，哪些寄存器和存储单元的内容会改变? 列，设置一个尾指针更合适。
8． 对给定文件（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