2017年南京大学1507计算机软件基础之数据结构(C语言版)复试仿真模拟三套题
● 摘要
一、应用题
1． 某计算机的CPU 主频为500MHz ，CPI 为5（即执行每条指令平均需要5个时钟周期）。假定某外设的数据传输率为0.5MB/S，采用中断方式与主机进行数据传送，以32位为传输单位，对应的中断服务程序包含18条指令，中断服务的其他开销相当于2条指令的执行时间。请回答下列问题，要求给出计算过程。
（1）在中断方式下，CPU 用于该外设I/O的时间占整个CPU 时间的百分比是多少？
（2）当该外设的数据传输率达到5MB/s时，改用DMA 方式传送数据。假定每次DMA 传送块大小为5000B , 且DMA 预处理和后处理的总开销为500个时钟周期，则CPU 用于该外设I/0时间占整个CTU 时间的百分比是多少？（假设DMA 与CPU 之间没有访存冲突）
【答案】（1）已知主频为500MHz ，则时钟周期=l÷500MHz=2ns，因为CPI=5, 所以每条指令
，数据传输率为0.5MB/S, 所以传送时间平均5×2=10ns。又已知每中断一次传送32位（4个字节）
=4÷0.5MB/s=CPU 用于该外设I/0共需20条指令（中断服务程序包括18条指令+其他开销折
，花费时间=20×l0=200ns。CPU 用于该外设I/0的时间占整个CPU 时间的百分比合2条指令）
=200/8000×100%=0.025×100%=2.5%。
（2）改用DMA 方式传送数据，数据传输率为5MB/S，传送5000B 的时间=5000B÷5MB/s=lms。预处理和后处理的总开销时间=500×2ns=CPU 用于该外设I/0时间占整个CPU 时间的百分比=预处理和后处理的总开销时间÷传送数据的时间=l/1000×l00%=0.001×100%=0.1%。
2． 设LS 是一个线性表，若采用顺序存储结构，则在等概率的前提下，插入一个元素需要平均移动的元素个数是多少? 若元素插
在
【答案】需要分两种情况讨论：
，插入位置0..n ，则平均移动个数为（1）等概率（后插）
（2）若不等概率，则平均移动的元素个数为
3． 快速排序的最大递归深度是多少? 最小递归深度是多少？
【答案】设待排序记录的个数为n ，则快速排序的最小递归深度为
4． 请写出应填入下列叙述中（ ）内的正确答案。
排序有各种方法，如插入排序、快速排序、堆排序等。
与
之间的概率
为则插入一个元素需要平均移动的元素个数又是多少？ 最大递归深度n 。
设一数组中原有数据如下：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
【答案】①快速排序②起泡排序③直接插入排序④堆排序
5． 请写出应填入下列叙述中（ ）内的正确答案。
某一工程作业的网络图如图1所示，其中箭头表示作业，箭头边的数字表示完成作业所需的天
数。箭头前后的圆圈表示事件，圆圈中的数字表示事件的编号。用事件编号的序列（例如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
6． 阅读下面的算法，说明算法实现的功能。
【答案】本算法功能是将两个无头结点的循环链表合并为一个循环链表。Head1最后一个结点的链域指向head2, head2最后一个结点的链域指向headl ，headl 为结果循环链表的指针。
7． 画出同时满足下列两个条件的两棵不同的二叉树。
（1）按前序遍历二叉树的顺序为ABCDE 。
（2）高度为5其对应的树（森林）的高度最大为4。
【答案】（1）满足条件的二叉树如图1所示：
图1
（2）满足条件的二叉树如图2所示：
图2
8． 三维数组
的存储首地址。
【答案】数组占的存储字节
数
的存储地
址的每个元素的长度为4个字节，试问该数组要占多少个字节的存储空间? 如果数组元素以行优先的顺序存储，设第一个元素的首地址是100，试求元素
二、算法设计题
9． 设有一头指针为L 的带有表头结点的非循环双向链表，其每个结点中除有pred （前驱指针），data （数据）和next （后继指针）域外，还有一个访问频度域freq 。在链表被启用前，其值均初始化为零。每当在链表中进行一次Locate （L ，x ）运算时，令元素值为x 的结点中freq 域的值増1, 并使此链表中结点保持按访问频度非增（递减）的顺序排列，同时最近访问的结点排在频度相同的结点的最后，以便使频繁访问的结点总是靠近表头。试编写符合上述要求的Locate （L , x ）运算的算法，该运算为函数过程，返回找到结点的地址，类型为指针型。
【答案】算法如下：
相关内容
相关标签