2017年暨南大学信息科学技术学院830数据结构考研冲刺密押题
● 摘要
一、填空题
1． 设有一个空找，栈顶指针为1000H （十六进制），现有输入序列为1，2，3, 4, 5，经过PUSH ，PUSH , POP , PUSH , POP ，PUSH ，PUSH 之后，输出序列是_____，而栈顶指针值是_____。设栈为顺序栈，每个元素占4个字节。
【答案】23; 100CH
2． —个字符串中_____称为该串的子串。
【答案】任意个连续的字符组成的子序列
3． 栈是_____的线性表，其运算遵循_____的原则。
；后进先出 【答案】操作受限（或限定仅在表尾进行插入和删除操作）
4． 当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_____存储结构。
【答案】顺序
【解析】顺序存储结构的存取操作比较方便，但插入和删除操作不如链式存储结构方便，而且需要连续的存储空间，由于该线性表的元素总数基本稳定，而且很少进行插入删除操作，为了更快的存取元素，顺序表更合适。
5． 对于一个具有n 个结点的单链表，在已知的结点半p 后插入一个新结点的时间. 复杂度为_____，在给定值为x 的结点后插入一个新结点的时间复杂度为_____。
【答案】
【解析】第一种情况只需直接修改指针的指向。第二种情况必须从头结点遍历找到x 的结点。
6． 阅读下列程序，指出其功能，并写出空格处应填上的语句。
【答案】
【解析】本题是在哈希表ht[]中插入值为的元素，如该元素已在哈希表中，报告出错。
7． 克鲁斯卡尔算法的时间复杂度为_____，它对_____图较为适合。
【答案】O （eloge ）; 边稀疏
8． 文件可按其记录的类型不同而分成两类，即_____和_____文件。
【答案】操作系统文件；数据库
9． 二叉树的前序序列和中序序列相同的条件是_____。
【答案】空树或任何结点至多只有右子树的二叉树
【解析】前序遍历的顺序为根左右，中序遍历的顺序为左根右，因此若中序遍历和前序遍历序列相同，则任何结点都没有左子树。
10．在哈希函数中，P 值最好取_____。
【答案】小于等于表长的最大素数或不包含小于20的质因子的合数
【解析】在使用除留余数法时，对除数P 的选择很重要。若P 选的不好，容易产生同义词。一般情况下，可以选P 为质数或不包含小于20的质因素的合数。
二、选择题
11．下列关于无向连通图特性的叙述中，正确的是（ ）。
I. 所有的顶点的度之和为偶数 II. 边数大于顶点个数减1 III. 至少有一个顶点的度为1 A. 只有I B. 只有II C.I 和II D.I 和III 【答案】A
【解析】在图中，顶点的度TD 点数，
e 为总边数），因此，I 项正确。对于II 、III 项中的特性不是一般无向连通图的特性，可以轻松地举出反例。“至少有一个顶点的度为1”的反例如下图（1）所示，“边数大于顶点个数减1”
之和与边的数目满足关系式：（n 为图的总结
的反例如下图（2）所示。
图
12．处理外部中断时，应该由操作系统保存的是（ ）。
A. 程序计数器（PC ）的内容 B. 通用寄存器的内容 C. 快表（TLB ）的内容 D.Cache 中的内容 【答案】B
【解析】外部中断处理过程首先要保护现场，使得中断处理完后能够恢复程序的状态继续执；②由中断服务程序保行。保护现场有两个含义：①由中断隐指令保存程序的断点（程序计数器）存通用寄存器和状态寄存器的内容。中断服务程序是操作系统的一部分。
13．下列进程调度算法中，综合考虑进程等待时间和执行时间的是（ ）。
A. 时间片轮转调度算法 B. 短进程优先调度算法 C. 先来先服务调度算法 D. 尚响应比优先调度算法 【答案】D
【解析】时间片轮转法和先来先服务算法都是公平的方法，并未考虑进程等待时间和执行时间，而短进程优先考虑的是进程执行时间。最高响应比优先调度算法是最先执行响应比最尚的进程（响应比=1＋等待时间/估计运行时间）。该算法综合了先来先服务（FCFS ）和短作业优先（SJF ）算法，FCFS 只考虑每个作业的等待时间，而未考虑执行时间的长短。SJF 只考虑执行时间的长短，而未考虑等待时间的长短，HRRN 算法则同时考虑执行时间和等待时间。
14．对矩阵压缩存储是为了（ ）。
A. 方便运算 B. 方便存储 C. 提高运算速度 D. 减少存储空间 【答案】D
相关内容
相关标签