2017年浙江海洋学院数据结构复试实战预测五套卷
● 摘要
一、应用题
1. 线性表有两种存储结构:一是顺序表,二是链表。试问:
(1)如果有,2个线性表同时并存,并且在处理过程中各表的长度会动态变化,线性表的总数也会自动地改变。在此情况下,应选用哪种存储结构? 为什么?
(2)若线性表的总数基本稳定,且很少进行插入和删除,但要求以最快的速度存取线性表中的元素,那么应采用哪种存储结构? 为什么?
【答案】(1)应选择链式存储结构。因为它可动态申请内存空间,不受表长度(即表中元素个数)的影响,插入、删除时间复杂度为O (1)。
(2)应选择顺序存储结构。因为顺序表可以随机存取,时间复杂度为O (1)。
2. KMP 算法(字符串匹配算法)较Brute (朴素的字符串匹配)算法有哪些改进?
【答案】朴素的模式匹配度达到
时间复杂度是
KMP 算法有一定改进,时间复杂
主要优点是主串指针不回溯。当主串很大不能一次读入内存且经常发生部分匹配
时,KMP 算法的优点更为突出。
3. 证明:置换选择排序法产生的初始归并段的长度至少为m (m 是所用缓冲区的长度)。
【答案】证明:由置换选择排序思想,第一个归并段中第一个元素是缓冲区中最小的元素,,缓以后每选一个元素都不应小于前一个选出的元素,故当产生第一个归并段时(即初始归并段)冲区中m 个元素中除最小元素之外,其他m-1个元素均大于第一个选出的元素,即当以后读入元素均小于输出元素时,初始归并段中也至少能有原有的m 个元素。证毕。
4.
某局域网采用协议实现介质访问控制,
数据传输率为程。
(1)若主机甲和主机乙发送数据时发生冲突,则从开始发送数据时刻起,到两台主机均检测到冲突时刻止,最短需经过多长时间? 最长需经过多长时间?(假设主机甲和主机乙发送数据过程中,其他主机不发送数据)
(2)若网络不存在任何冲突与差错,主机甲总是以标准的最长以太网数据帧(1518字节)向主机乙发送数据,主机乙每成功收到一个数据帧后立即向主机甲发送一个64字节的确认帧,主机甲收到确认帧后方可发送下一个数据帧,此时主机甲的有效数据传输速率是多少?(不考虑以太网帧的前导码)
【答案】(1)当甲乙两台主机同时向对方发送数据时,两台主机均检测到冲突的时间最短
:
=
第 2 页,共 37 页
主机甲和主机乙之
间的距离为2km ,信号传播速度是200000km/S。请回答下列问题,要求说明理由或写出计算过
(lkm/200000km/s)×2=10j×s ; 当一台主机发送的数据就要到达另一台主机时,另一台主机才发送数据,两台主机均检测到冲突的时间最长:
=1500B=1500×8bit=12000bit; 发送1518B 的发送时间=1518×8/10Mbps=间=2km/200000km/s
=
确认帧的发送时间=64×
8/10Mbps=
; 确认帧的传播时间
=2km/200000km/s=
;
发送1518B
所用的总时间为
主机甲的有效数据传输率为12000bit /
1285.6μs=9.33Mbps。
5. 设阶稀疏矩阵A 有t 个非零元素,其三元组表示为素的个数t 达到什么程度时用,共占用三元组表
元组)
时,用
的
表示A 才有意义?
个存储单元,用二维数组存储时占用
个单元,
只有当
数据帧的传播时
(2)有效数据传输速率=发送的有效数据/发送有效数据所用的总时间。发送的有效数据
试问:非零元
【答案】稀疏矩阵A 有t 个非零元素,加上行数mu 、列数皿和非零元素个数tu (也算一个三
表示A 才有意义。解不等式得
6. 若森林共有n 个结点和b 条边(b 【答案】森林的n 个结点开始可看做是n 个连通分量,加入一条边将减少一个连通分量。因为树可以定义为无环的图,故加入b 条边将减少b 个连通分量,因而n 个结点b 条边的森林有n-b 棵树。 7. 在某程序中,有两个栈共享一个一维数组空间的栈底。 (1)对栈1、栈2, 试分别写出(元素x )入栈的主要语句和出栈的主要语句。 (2)对栈1、栈2, 试分别写出栈满、栈空的条件。 【答案】(1)入栈主要语句 出栈主要语句 分别是两个栈 (2) 8. 请写出应填入下列叙述中( )内的正确答案。 某一工程作业的网络图如图1所示,其中箭头表示作业,箭头边的数字表示完成作业所需的天 第 3 页,共 37 页 数。箭头前后的圆圈表示事件,圆圈中的数字表示事件的编号。用事件编号的序列(例如0-2-7-9-11)表示进行作业的路径。 完成此工程的关键路径是(A )完成此工程所需的最少天数为(B )天,此工程中具有最大充,充裕天数是(D )裕天数的事件是(C )。关键路径上的事件的充裕天数是(E )。 图1 【答案】A. 0-2-6-9-11; B. 20; C.事件顶点1、5和7各充裕两天;D. 4天;E. 0 二、算法设计题 9. 辅助地址表的排序是不改变结点物理位置的排序。辅助地址表实际上是一组指针,用它来指出结点排序后的逻辑顺序地址。设 用 表示辅助地址表。初始时 非递减序)算法的语句序列。 【答案】算法如下: 10.设A 和B 均为下三角矩阵,每一个都有n 行n 列。因此在下三角区域中各有无素。另设有一个二维数组C ,它有n 行 个 表示n 个结点的值, 用 在排序中,凡需对结点交换就用它的地址来 进行。例如当n=3时,对K (31,11,19)则有T (2,3,1)。试编写实现辅助地址表排序(按 列。试设计一个方案,将两个矩阵A 和B 中的下三 和B 的矩 角区域元素存放于同一个C 中。要求将A 的下三角区域中的元素存放于C 的下三角区域中,B 的下三角区域中的元素转置后存放于C 的上三角区域中。并给出计算A 的矩阵元素阵元素在C 中的存放位置下标的公式。 【答案】算法如下: 第 4 页,共 37 页