2016年宁波大学信息科学与工程学院C程序设计之数据结构复试笔试仿真模拟题
● 摘要
一、选择题
1． 引入二叉线索树的目的是（ ）。
A. 加快查找结点的前驱或后继的速度 B. 为了能在二叉树中方便地进行插入与删除 C. 为了能方便地找到双亲 D. 使二叉树的遍历结果唯一 【答案】A
【解析】二叉线索树有指向前驱和后继的指针，因此加快了查找前驱和后继结点的速度。
2． 有两个并发执行的进程P1和P2, 共享初值为1的变量x 。P1对x 加1, P2对x 减1。加1和减1操作的指令序列分别如下所示。
//取x 到寄存器R1中
两个操作完成后，2的值（ ）。 A. 可能为-1或3 B. 只能为1 C. 可能为0、1或2 D. 可能为-1、0、1或2 【答案】C
【解析】这是在数据库中常有的操作。为保证数据的正确，避免产生错误，系统必须保证数据的同步。而保证数据的同步一般采取加锁的方法，让进程P1和P2互斥访问共享变量X 。当然用信号量和P 、V 操作也是可以 保证互斥操作，达到数据同步的。本例中，由于没有采取保证数据同步的相应措施，则最后结果就会出现差错。 例如，当正常情况下，进程P1和P2先后对x 操作，可以看到x 值的变化为初始1→2→1的过程，若P2, P1先后操作，则x 值的变化为初始1→0→1，这是正确的。若考虑一种并发的情况，进程P1和P2先后执行了取数load 的操作，它们得到的x 值均为1，运算后，P1和P2的x 值分别为2和0, 此时要看哪个进程后执行存数store 的 操作了，哪个进程后操作，结果就是那个进程的x 值，所以可能的结果为0或2, 加上前面正确的x 值1, 则可能的结果就有3种了。
3． 某同步总线的时钟频率为所需要的时间至少是（ ）。
A.20ns B.40ns C.50ns D.80ns
【答案】C 。
宽度为32位，地址/数据线复用，每传输一个地址或数据占用
一个时钟周期。若该总线支持突发（猝发）传输方式，则一次“主存写”总线事务传输128位数据
【解析】总线的时钟频率为100MHz ，贝时钟周期为10ns 。数据是128位，总线宽度是32位，所以需要4个时钟周期，而传输地址还需要一个周期，所以传输一个128位的数据至少需要5个时钟周期，所以至少需要10ns*5=50ns。 4． 若串其子串的数目是（ ）。
A.8 B.37 C.36 D.9
【答案】B
【解析】子串的定义是：串中任意个连续的字符组成的子序列，并规定空串是任意串的子串，任意串是其自身的子串。若字符串长度为长为
长为n 的子串有1个，长为
的子串有2个，
的子串有3个，……，长为1的子串有n 个。由于空串是任何串的子串，所以本题的答案
为：故选B 。
5． 用希尔排序方法对一个数据序列进行排序时，若第1趟排序结果为趟排序采用的增量（间隔）可能是（ ）
A.2 B.3 C.4 D.5
【答案】B
【解析】对于A , 增量为2, 那么9, 4, 7, 20, 15是一组，而它们是无序的，所以A 错误 对于C , 增量为4, 那么9, 7，15是一组，而它们是无序的，所以C 错误
则该
对于D , 增量为5, 那么9, 8是一组，降序，1，20是一组，而它们是升序，所以D 也错误。对于B ，分为3组：都是升序有序，所以B 正确
6． 下列关于RISC 的叙述中，错误的是（ ）。
A.RISC 普遍采用微程序控制器
B.RISC 大多数指令在一个时钟周期内完成 C.RISC 的内部通用寄存器数量相对CISC 多
D.RISC 的指令数、寻址方式和指令格式种类相对CISC 少
【答案】A
【解析】B 项、C 项、D 项都是RISC 的特点之一，所以它们都是正确的，只有A 项是CISC 的特点，因为RISC 的速度快，所以普遍采用硬布线控制器，而非微程序控制器。
7． 处理外部中断时，应该由操作系统保存的是（ ）。
A. 程序计数器（PC ）的内容 B. 通用寄存器的内容 C. 快表（TLB ）的内容 D.Cache 中的内容 【答案】B
【解析】外部中断处理过程首先要保护现场，使得中断处理完后能够恢复程序的状态继续执；②由中断服务程序保行。保护现场有两个含义：①由中断隐指令保存程序的断点（程序计数器）存通用寄存器和状态寄存器的内容。中断服务程序是操作系统的一部分。
8． 设n 是描述问题规模的非负整数，下面程序片段的时间复杂度是（ ）。
【答案】A
【解析】其中，以基本的原操作重复执行的次数作为算法的时间度量。题目中的基本运算是语句
9． 为支持
，则有设其执行时间为T （n ）
中视频文件的快速随机播放，播放性能最好的文件数据块组织方式是（ ）
A. 连续结构 B. 链式结构 C. 直接索引结构 D. 多级索引结钩 【答案】A
【解析】为了实现快速随机播放，要保证最短的查询时间，即不能选取链表和索引结构，因此连续结构最优。
10．就平均性能而言，目前最好的内排序方法是（ ）排序法。
A. 起泡 B. 希尔插入 C. 交换
相关内容
相关标签