2017年西安交通大学机械工程学院814计算机基础综合之数据结构考研题库
● 摘要
一、选择题
1． 已知广义表
用
【答案】C 【解析】
操作就是得到广义表中第一个的原子。
得
到得到e 。
2． 设二维数组
（即m 行n 列）按行存储在数组
【答案】A 【解析】
前
的元素个数为
所以二维数组元素
在一维数组B
中的下标为
需要注意数组B 的下标是从0开始，还是从1开始。
3． 从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（ ）排序法。
A. 插入 B. 选择 C. 希尔 D. 二路归并 【答案】A
【解析】解此题需要熟知各种排序方法的基本思想。插入排序的基本思想是：假设待排序的
记录存放在数组
中，排序过程的某一中间时刻，R
被划分成两个子区间
插入到有序区
和
其中：前一个子区间是已排好序的有序区，后一个子区间则是当前未排序的部分，不妨
称其为无序区。将当前无序区的第1
个记录
4． 下列排序算法中，其中（ ）是稳定的。
A. 堆排序，起泡排序 B. 快速排序，堆排序
和数取出LS 中原子e 的运算是（ ）。
操作就是得到除第一个原子外剩下元得
到
得
到
素构成的表
。
中，
则二维数组元素
在一维数组B 中的下标为（ ）。
中适当的位置上。使
变为新的有序区。这种方法通常称为增量法，因为它每次使有序区增加1个记录。
C. 直接选择排序，归并排序 D. 归并排序，起泡排序 【答案】D
5． 处理外部中断时，应该由操作系统保存的是（ ）。
A. 程序计数器（PC ）的内容 B. 通用寄存器的内容 C. 快表（TLB ）的内容 D.Cache 中的内容 【答案】B
【解析】外部中断处理过程首先要保护现场，使得中断处理完后能够恢复程序的状态继续执；②由中断服务程序保行。保护现场有两个含义：①由中断隐指令保存程序的断点（程序计数器）存通用寄存器和状态寄存器的内容。中断服务程序是操作系统的一部分。
6． 下列关于闪存（FlashMemory ）的叙述中，错误的是（ ）。
A. 信息可读可写，并且读、写速度一样快 B. 存储元由MOS 管组成，是一种半导体存储器 C. 掉电后信息不丢失，是一种非易失性存储器 D. 采用随机访问方式，可替代计算机外部存储器 【答案】A 。
【解析】考查闪存的特性，闪存是EEPROM 的进一步发展，可读可写，用MOS 管的浮栅上有无电荷来存储信息，它依然是ROM 的一种，故写速度比读速度要慢不少。闪存是一种非易失性存储器，它采用随机访问方式，现在常见的SSD 固态硬盘就是由flash 芯片组成的，故答案为A 。
7． 数据链路层采用选择重传协议（SR ）传输数据，发送方已发送了0H3号数据倾，现已收到1号帧的确认，而0、2号帧依次超时，则此时需要重传的帧数是（ ）。
A.1 B.2 C.3 D.4
【答案】B
【解析】在选择重传协议中，接收方逐个地确认正确接收的分组，不管接收到的分组是否有序，只要正确接 收就发送选择ACK 分组进行确认。因此选择重传不支持累积确认，要特别注意其与GBN 协议的区别。本题收到1号帧的确认，说明1号帧正确接收，0和2号帧依次超时，因此必须重传，然而3号帧尚未超时，是否正确接收未知，故不用重传，因此必须重传0和2号帧，答案是B 。
8． 基于比较方法的n 个数据的内部排序。 最坏情况下的时间复杂度能达到的最好下界是（ ）。
A.0（nlogn ） B.O （logn ） C.O （n ） D.
【答案】A
【解析】在内部排序中，最坏情况下的时间复杂度为0（nlogn ）。 已知待排序的n 个元素可分为
个组，每个组包含k 个元素，且任一组内的各元素均分别
大干前一
9． 有关二叉树下列说法正确的是（ ）。
A_二叉树的度为2
B. —棵二叉树的度可以小于2 C. 二叉树中至少有一个结点的度为2 D. 二叉树中任何一个结点的度都为2 【答案】B
【解析】树的度=MAX（结点1的度，结点2的度，结点3的度，... ，结点n 的度）。二叉树之所以称为二叉树，是因为二叉树中节点的度最大是2，也可以小于2。
10．为解决计算机主机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（ ）。
A. 栈 B. 队列 C. 树 D. 图 【答案】B
【解析】这类问题一般都先分析题目中的数据具有什么操作特性或是结构特性比如“先进后出”、“先进先出”等再判断其逻辑结构。栈和队列是操作受限的线性表，栈具有先进后出的特性而队列具有先进先出的特性。由于本题中先进入打印数据缓冲区的文件先被打印，因此打印数据缓冲区具有先进先出性，则它的逻辑结构应该是队列。
二、填空题
11．对于一个具有n 个结点的二叉树，当它为一棵_____二叉树时具有最小高度，当它为一棵_____ 时. 具有最大高度
【答案】完全；只有一个叶结点的二叉树
相关内容
相关标签