2016年大连海事大学航海学院Z01数据结构复试笔试最后押题五套卷
● 摘要
一、选择题
1． 为实现快速排序算法，待排序序列宜采用的存储方式是（ ）。
A. 顺序存储 B. 散列存储 C. 链式存储 D. 索引存储 答:A
【解析】对绝大部分内部排序而言，只适用于顺序存储结构，快速排序在排序过程中，既要从后向前查找，也要从前向后查找，因此宜采用顺序存储。
2． 循环队列存放其元素值，用front 和rear 分别表示队头和队尾，则当前队列中的元素数是（ ）。
答:A
【解析】对于循环队列，需要深刻理解队头在队尾进行进队操作。
素的个数=所以统一的公式就是
3． 设栈S 和队列Q 的初始状态为空，元素后即进队列Q ，若6个元素出队的序列是
A.6 B.4 C.3 D.2 答:C
4． 数组通常具有的两种基本操作是（ ）。
A. 查找和修改 B. 查找和索引 C. 索引和修改 D. 建立和删除 答:A
【解析】数组中的元素是顺序存放的，通过下标可以很好地查找数组元素，同时通过对应的指针可以修改数组元素的值，因此数组通常具有的两种基本操作是查找和修改。根据数组的性质，
和队尾
的概念，在队头进行出队操作，
如果为负则元
可能为正也可能为负，为正时元素个数=
依次通过栈S ，一个元素出栈 则栈S 的容量至少应该是（ ）。
数组通常具有的两种基本运算是排序和查找。
5． 在下面的排序方法中，辅助空间为的是（ ）。
A. 希尔排序 B. 堆排序 C. 选择排序 D. 归并排序 答:D
6． 假定编译器规定int 和short 类型长度分别为32位和16位，执行下列C
语言语句
得到y 的机器数为（ ）。
答:B 。
【解析】X 和y 均为无符号数，其中X 为16位，y 为32位，将16位无符号数转化成32位无符号数，前面要补零。因为所以
7． 先序序列为a , b，c , d的不同二叉树的个数是（ ）。
A.13 B.14 C.15 D.16 答:B
【解析】二叉树的先序遍历定义为：若二叉树为空，则空操作；否则，访问根节点，然后先序遍历左子树，最后先序遍历右子树。本题中，结点a 为二叉树的根节点，左右子树的先序遍历可能存在下面四种情况：①左子树为空，bed 为右子树；②b 为左子树，cd 为右子树；③be 为左子树，d 为右子树；④bed 为左子树，右子树为空。然后将左右子树继续分解，如第①种情况的右子树先序遍历（bed ）可能有：a. 左子树为空，右子树为cd ；b. 左子树为c ，右子树为d ；c. 左子树为cd ，右子树为空。按照这种方法继续分解左右子树，直到不能再分解为止，可得第①和④种情况各包含5种不同情况，第②和③种情况各包含2种情况，因此总共有14种不同的二 叉树。
8． 下列排序算法中，其中（ ）是稳定的。
A. 堆排序，起泡排序 B. 快速排序，堆排序 C. 直接选择排序，归并排序 D. 归并排序，起泡排序 答:D
9． 下列命中组合情况中，一次访存过程中不可能发生的是（ ）。
A.TLB 未命中，Cache 未命中，Page 未命中 B.TLB 未命中，Cache 命中，Page 命中 C.TLB 命中，Cache 未命中，Page 命中 D.TLB 命中，Cache 命中，Page 未命中 答:D
【解析】TLB （快表）和慢表（页表，Page ）构成二级存储系统，若TLB 命中，则Page 必命中。因此不可能发生的是D 选项。
10．假定编译器将赋值语句“x=x+3; ”转换为指令” add xaddt, 3”，其中xaddt 是x 对应的存储单元地址，若执行该指令的计算机采用页式虚拟存储管理方式，并配有相应的TLB ，且Cache 使用直写（Write Through）方式，则完成该指令功能需要访问主存的次数至少是（ ）。
A.0 B.1 C.2 D.3 答:C
【解析】采用页式虚拟存储管理方式时，若页表全部放在内存中，则存取一个数据最少要访问两次内存：第一次是访问页表，得到所存取的数据或指令的物理地址；第二次根据该地址存取数据或指令。在配有TLB 的页式虚拟管理方式中，如果给出的地址在TLB 中，则直接根据该地址取数据或指令，仅需要一次访问内存。Cache 使用直写方式时，计算完需要将数据写回到内存中，因此完成整个指令功能至少需要访问主存2次。
二、填空题
11．高度为4的3阶B-树中，最多有_____个关键字。
答:26
【解析】第4层是叶结点，1层至3层每个结点两个关键字，每个节点的关键字达到最大时，关键字最多。
12．一个算法具有5个特性：_____、_____、_____、有零个或多个输入、有一个或多个输出。
答:有穷性；确定性；可行性
13．对n 个记录的表r[l..n]进行简单选择排序，所需进行的关键字间的比较次数为_____。
答:n （n-1）/2
【解析】第一次需要n-1次比较，第i 此需要n-i 此比较，所以共需要、n-l+n-2+...+l=n（n-l ）/2。
相关内容
相关标签