《2017年上海海洋大学中国水产科学研究院(联合培养)919计算机基础综合之数据结构考研导师圈点必考题汇编.doc》由会员分享，可在线阅读，更多相关《2017年上海海洋大学中国水产科学研究院(联合培养)919计算机基础综合之数据结构考研导师圈点必考题汇编.doc（4页珍藏版）》请在金锄头文库上搜索。
1、2017年上海海洋大学中国水产科学研究院(联合培养)919计算机基础综合之数据结构考研导师圈点必考题汇编一、填空题1 设有一个10阶对称矩阵A 采用压缩存储方式（以行为主序存储：【答案】33【解析】设存储的元素的行标为i ，列标为j 。若则则的地址为若的地址为将代入得33。 2 设T 和P 是两个给定的串，在T 中寻找等于P 的子串的过程称为_，又称P 为_。【答案】模式匹配；模式串 3 外排序的基本操作过程是_和_。；归并 【答案】生成有序归并段（顺串） 4 一个有2001个结点的完全二叉树的高度是_。【答案】11【解析】完全二叉树的高度5 无用单元是指_，例_ ，）则的地址为_。【答案】用
2、户不再使用而系统没有回收的结构和变量； 6 VSAM （虚拟存储存取方法）文件的优点是：动态地_，不需要文件进行_，并能较快地_进行查找。【答案】分配和释放存储空间；重组；对插入的记录7 当广义表中的每个元素都是原子时，广义表便成了_。【答案】线性表【解析】如果每个元素都是原子，则元素不可分。此时的元素是只有一对一的关系，所以广义表变成了线性表。 8 以下程序的功能是实现带附加头结点的单链表数据结点逆序连接，请填空完善之。 【答案】（1）（2）链表未到尾就一直进行将当前结点作为头结点后的第一元素结点插入二、选择题9 ARP 协议的功能是（ ）。A. 根据IP 地址查询MAC 地址 B. 根据M
3、AC 地址查询IP 地址 C. 根据域名查询IP 也址 D. 根据IP 地址查询域名 【答案】A 。【解析】ARP 协议是网络层协议，因此只能和传输层和数据链路层有关系，从这一点出发，域名是应用层的范畴，选项C 和D 是不正确的，根据MAC 地址查询IP 地址是RARP 协议的功能，因此进而得出正确答案是A 。10采用递归方式对顺序表进行快速排序。下列关于递归次数的叙述中，正确的是（ ）。A. 递归次数与初始数据的排列次序无关B. 每次划分后，先处理较长的分区可以减少递归次数 C. 每次划分后，先处理较短的分区可以减少递归次数 D. 递归次数与每次划分后得到的分区的处理顺序无关 【答案】D【解
4、析】快速排序是递归的，递归过程可用一棵二叉树给出，递归调用层次数与二叉树的深，采用快速排序方法，其对应递归调用度一致。例如：待排序列48, 62，35, 77, 55, 14, 35, 98）过程的二叉树如下图所示。 在最坏情况下，若初始序列按关键码有序或基本有序时，快速排序反而蜕化为冒泡排序。即其对应递归调用过程的二叉树是一棵单支树。因此快速排序的递归次数与初始数据的排列次序有关。但快速排序的递归次数与每次划分后得到的分区处理顺序无关，即先处理较长的分区或先处理较短的分区都不影响递归次数。 11下列选项中，在用户态执行的是（ ）。A. 命令解释程序 B. 缺页处理程序C. 进程调度程序 D.
5、 时钟中断处理程序 【答案】A【解析】题目是问用户态执行，可见是有关操作系统基本概念的问题。四个选项中，用户唯一能面对的是命令解释程序，缺页处理程序和时钟中断都属于中断，在核心态执行，而进城调度属于系统调用在核心态执行。只有命令解释程序属于命令接口，可以运行在用户态，接受用户的命令操作控制。 12对于一个线性表既要求能够进行较快速地的插入和删除，又要求存储结构能反映数据之间的逻辑关系，则应该用（ ）。A. 顺序存储方式 B. 链式存储方式 C. 散列存储方式 D. 以上均可以 【答案】B 13归并排序中，归并的趟数是（ ）。 【答案】B【解析】不妨设归并的趟数为m ，第一次归并每组有两个元素，最后一次归并只剩下一组，这组的元素个数为n。因此每次归并元素的个数增加一倍。所以 14下列不是设计一个“好”的算法应考虑达到的目标是（ ）。A. 可行的 B. 健壮的 C. 无二义性的 D. 可读性好的 【答案】A【解析】设计一个“好”的算法应考虑以下目标：正确性；可读性；健壮性；效率和低存储量需求。可行性是算法的五个基本特征之一，不是一个好的算法该达到的目标。 15中断处理和子程序调用都需要压栈以保护现场，中断处理一定会保存而子程序调用不需要保存其内容的是（ ）。A. 程序计数器 B. 程序状态字寄存器 C. 通用数据寄存器所以归并的趟数为一、填空题考研试题
