2017年江苏科技大学计算机科学与工程学院845计算机综合之数据结构考研仿真模拟题
● 摘要
一、选择题
1． 图中有关路径的定义正确的是（ ）。
A. 由顶点和相邻顶点构成的边所形成的序列 B. 由不同顶点所形成的序列 C. 由不同边所形成的序列 D. 上述定义都不是 【答案】A
【解析】顶点Vp 到顶点Vq 之间的一条路径是指顶点序列
，路径上边
的数目称为路径的长度。
2． 若元素a ，b , c, d, e，f 依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈操作，则不可能得到的出栈序列是（ ）。
A.d ，c ，e ，b ，f ，a B.c ，b ，d ，a ，e ，f C.b ，c ，a ，e ，f ，d D.a ，f ，e ，d ，c ，b
【答案】D
【解析】4个选项所给序列的进、出栈操作序列分别为：
选项A.Push , Push , Push ，Push , Pop, Pop, Push，Pop , Pop, Push , Pop ，Pop 选项B.Push , Push , Push , Pop , Pop , Push, Pop, Pop, Push, Pop , Push, Pop 选项C.Push , Push , Pop , Push , Pop , Pop, Push, Push, Pop, Push , Pop , Pop 选项D.Push , Pop , Push, Push , Push , Push, Push, Pop, Pop，Pop , Pop , Pop
按照题目要求，不允许连续三次进行退栈操作，所以选项D 所给序列为不可能得到的出栈顺序。
3． 设n 是描述问题规模的非负整数，下面程序片段的时间复杂度是（ ）。
【答案】A
【解析】其中，以基本的原操作重复执行的次数作为算法的时间度量。题目中的基本运算是 ，则有语句设其执行时间为T （n ）
4． 系统为某进程分配了4个页框，该进程已访问的页号序列为2, 0, 2, 9, 3, 4, 2, 8, 2, 3, 8, 4, 5, 若进程要访问的下一页的页号为7，依据LRU 算法，应淘汰页的页号是（ ）。
A.2 B.3 C.4 D.8
【答案】B
【解析】LRU 置换算法是选择最近最久未使用的页面予以淘汰。进程有4个页框，题中访问过程中页框的变化如下：
序列：页框：
淘汰：3。
5． 就平均性能而言，目前最好的内排序方法是（ ）排序法。
A. 起泡 B. 希尔插入 C. 交换 D. 快速 【答案】D
【解析】快速排序的平均时间复杂度是复杂度也是
所需要的辅助存储为
仅仅表示的是一个量级，
比如
所需要的辅助存储为和
的量级都为
虽然堆排序的时间
之所以说快排
看似堆排序比快速排序的性能好，
但是需要注意
访问页号为7的页时，内存中存在的页的页号是：3、8、4和5，根据LRU 定义应淘汰的是
最好，是在综合考虑的情况下。
6． 下列选项中，不能构成折半查找中关键字比较序列的是（ ）。
A.500，200，450，180 B.500，450，200，180 C.180，500，200，450 D.180，200，500，450
【答案】A
【解析】折半查找的过程是：先确定待查找记录所在的范围，然后逐步缩小范围直到找到或找不到该记录为止。折半查找的关键字序列满足：对每一个关键字，其后面的所有关键字序列或
者都小于等于该关键字或者都大于等于该关键字。A 项错误，第三次比较的关键字为450，说明待查关键字位于200〜450间，所以第四次比较时不会遇到关键字180。
7． 线性表是具有n 个（ ）的有限序列（n ＞0）。
A. 表元素 B. 字符 C. 数据元素 D. 数据项E. 信息项 【答案】C
【解析】一个线性表是n 个数据元素的有限序列。至于每个数据元素的具体含义，在不同的情况下各不相同。
8． 对于100Mbps 的以太网交换机，当输出端口无排队直通（cut-throughswitching ）方式转发一个以太网帧（不包括前导码）时，引入的转发延迟至少是（ ）
A. B. C. D. 【答案】B
【解析】直通交换方式是指以太网交换机可以在各端口间交换数据。它在输入端口检测到一个数据包时，检查该包的包头，获取包的目的地址，启动内部的动态查找表转换成相应的输出端口，在输入与输出交叉处接通，把数据包直通到相应的端口，实现交换功能。通常情况下，直通交换方式只检查数据包的包头即前14个字节，由于不需要考虑前导码，只需要检测目的地址的6B ，
所以最短的传输延迟是
9． 算法的计算量的大小称为计算的（ ）。
A. 效率 B. 复杂性 C. 现实性 D. 难度 【答案】B
【解析】算法复杂度通常分为时间复杂度和空间复杂度，算法的计算量的大小可以用时间复杂度衡量，即可以称为计算的复杂度。
10．单链表中，增加一个头结点的目的是为了（ ）。
A. 使单链表至少有一个结点 B. 标识表结点中首结点的位置 C. 方便运算的实现