3.8 真题

3.8 真题

1、对于二维数组a[1…N，1…N] 中的一个元素a[i，j]（1≤i、j≤N），存储在a[i，j]之前的元素个数（ ）。

A.与按行存储或按列存储方式无关

B.在i=j时与按行存储或按列存储方式无关

C.在按行存储方式下比按列存储方式下要多

D.在按行存储方式下比按列存储方式下要少

2、设有 n阶三对角矩阵 A，即非零元素都位于主对角线以及与主对角线平行且紧邻的两条对角线上，现对该矩阵进行按行压缩存储，若其存储空间用数组 B表示，A的元素下标从 0开始，B的元素下标从 1开始。已知A［0,0］存储在 B［1］，A［n－1，n－1］存储在 B［3n-2］，那么非零元素 A［i,j］（0≤ i＜n，0≤ j＜n，│ij│≤1）存储在 B［（ ）］。

A.2i+j-1

B.2i+j

C.2i+j+1

D.3i-j+1

3、用哈希表存储元素时，需要进行冲突（碰撞）处理，冲突是指（ ）。

A.关键字被依次映射到地址编号连续的存储位置

B.关键字不同的元素被映射到相同的存储位置

C.关键字相同的元素被映射到不同的存储位置

D.关键字被映射到哈希表之外的位置

4、令序列 X、Y、Z的每个元素都按顺序进栈，且每个元素进栈和出栈仅一次。则不可能得到的出栈序列是( )。

A.X Y Z

B.X Z Y

C.Z X Y

D.Y Z X

5、以下关于单链表存储结构特征的叙述中，不正确的是（ ）。

A.表中结点所占用存储空间的地址不必是连续的

B.在表中任意位置进行插入和删除操作都不用移动元素

C.所需空间与结点个数成正比

D.可随机访问表中的任一结点

6、B-树是一种平衡的多路查找树。以下关于 B-树的叙述中，正确的是（ ）。

A.根结点保存树中所有关键字且有序排列

B.从根结点到每个叶结点的路径长度相同

C.所有结点中的子树指针个数都相同

D.所有结点中的关键字个数都相同

7、对于给定的关键字序列｛47, 34, 13, 12, 52, 38, 33, 27, 5｝，若用链地址法（拉链法）解决冲突来构造哈希表，且哈希函数为H（key）=key%11，则（ ）。

A.哈希地址为1的链表最长

B.哈希地址为6的链表最长

C. 34和12在同一个链表中

D. 13和33在同一个链表中

8、某有向图 G的邻接表如下图所示，可看出该图中存在弧<v2, v3>，而不存在从顶点 V1出 发的弧。以下关于图G的叙述中，错误的是（ ）。

A. G中存在回路

B. G中每个顶点的入度都为1

C. G的邻接矩阵是对称的

D.不存在弧<v3,v1>

9、已知有序数组a的前10000个元素是随机整数，现需查找某个整数是否在该数组中。以下方法中，（ ）的查找效率最高。

A.二分查找法

B.顺序查找法

C.逆序查找法

D.哈希查找法

10、在常见的数据结构中，（ ）是只能通过访问它的一端来实现数据存储和检索的一种线性数据结构，它的修改遵循先进后出的原则；（ ）是一种先进先出的线性表。

（5）A.链表 B.队列 C.栈 D.串

（6）A.链表 B.队列 C.栈 D.串

（7）A.链表 B.队列 C.栈 D.串

11、二叉树遍历是按照某种策略访问树中的每个节点，且仅访问一次。按照遍历左子树要在遍历右子树之前进行的原则，根据访问（ ）位置的不同，可得到二叉树的前序、中序和后序三种遍历方法。

A.根节点

B.导航节点

C.叶子结点

D.兄弟节点

12、以下有关霍夫曼树的说法中，错误的是（ ）。

A.霍夫曼树又被称为最优二叉树

B.霍夫曼树是一种带权路径长度最短的树

D.霍夫曼树可以用来进行通信电文的编码和解码

13、查找算法中，（ ）要求查找表进行顺序存储并且按照关键字有序排列，一般不进行表的插入和删除操作。

A.顺序查找

B.折半查找

C.分块查找

D.动态查找

14、一个栈的输入序列为1，2，3，4，5，不可能得到的输出序列是（ ）。

A. 2,3,4,1,5

B. 5,4,1,3,2

C. 2,3,1,4,5

D. 1,5,4,3,2

15、（ ） 算法是不稳定的排序算法。

A.简单选择

B.冒泡

C.直接插入

D.归并排序

16、（ ） 是一种先进先出的线性表，只允许在表的一端插入元素，而在表的另一端删除元素。

A.栈

B.队列

C.串

D.树

17、一颗5层的二叉树，其最多有（ ）个结点，第5层最多有（ ）个结点。

（8）A.15 B.16 C.31 D.32

（9）A.15 B.16 C.31 D.32

18、（ ）排序又被称为缩小增量排序，是对直接插入排序方法的改进。

A.简单选择

B.冒泡

C.快速

D.希尔

19、计算机在处理算术表达式78+21*（36-34）时，先将其转换成“（ ） ”的后缀形式表示，然后利用（ ）进行计算。

20、依次在初始为空的队列中插入元素5、6、7、8以后，紧接着做了两次删除操作，此时的队头元素是（ ）。

A.5

B. 6

C.7

D.8

21、以下关于串的叙述中，错误的是（ ） 。

A.串是仅由字符构成的有限序列

B.串是取值范围受限的线性表

C.空串不包含任何字符

D.串只可以采用顺序存储方式

22、折半查找要求查找表中的数据为（ ）。

A.顺序存储、有序排列

B.散列存储、有序排列

C.顺序存储、无序排列

D.散列存储、无序排列

23、（ ）的基本思想是先将待排的记录划分为独立的两个部分，然后分别对这两部分记录再执行该排序算法，最终使整个序列有序。

A.快速排序

B.冒泡排序

C.堆排序

D.希尔排序

24、如果一个线性表最常用的操作是存取第i个元素及其后继（若存在）的值，那么使该操作最快的存储方式是（ ）。

A.单链表

B.单循环链表

C.双链表

D.数组

25、设有一个具有头结点的单链表，指针h指向其头结点，则当（ ）时该单链表为空；如果该单链表非空，且指针p指向链尾，那么（ ）。

26、如果一棵二叉树有10个度为2的结点，5个度为1的结点，那么度为0的结点个数为（ ）。

A.15

B. 11

C.9

D.0

27、若一棵二叉树的先序遍历序列为EFHIGJK，中序遍历序列为HFIEJKG,则该二叉树根结点的右孩子为（ ）。

A.E

B. F

C.G

D.H

28、已知一个有序表为（12，18，24，35，47，50，62，83，90，115，134），当折半查找值为90的元素时，经过（ ）次比较后查找成功。

A.2

B.3

C.4

D.5