数据结构与算法试题

一、单选题

1.下面给出的四种排序法中（　）排序法是不稳定的排序法。

A. 插入

B. 冒泡

C. 二路归并

D. 堆

知识点： 数据结构与算法

答案 D

2.串是一种特殊的线性表，其特殊性体现在（　　）。

A. 可以顺序存储

B. 数据元素是一个字符

C. 可以链接存储

D. 数据元素可以是多个字符

知识点： 数据结构与算法

答案 B

3.设表中含100个数据元素，用折半查找法进行查找，则所需最大比较次数为（ ）。

A. 50

B. 25

C. 10

D. 7

知识点： 数据结构与算法

答案 A

4.m阶Ｂ树中的一个分支结点最多含（）个关键字。（ ）

A. m-1

B. m

C. [m/2]

D. [m/2]+1

知识点： 数据结构与算法

答案 A

5.设串 s ='abcdefgh'，则其子串数为（　　）。

A. 8

B. 37

C. 36

D. 9

知识点： 数据结构与算法

答案 B

6.将两个各有n个元素的有序表归并成一个有序表，最少进行（ ）次比较。

A. n

B. 2n-1

C. 2n

D. n-1

知识点： 数据结构与算法

答案 A

7.在树形结构中，数据元素间存在（ ）的关系。

A. 一对一

B. 一对多

C. 多对多

D. 除同属一个集合外别无关系

知识点： 数据结构与算法

答案 B

8.ISAM文件和VSAM文件属于（ ）。

A. 索引非顺序文件

B. 索引顺序文件

C. 顺序文件

D. 散列文件

知识点： 数据结构与算法

答案 A

9.适用于折半查找的表的存储方式及元素排列要求为（　）。

A. 链接方式存储，元素无序

B. 链接方式存储，元素有序

C. 顺序方式存储，元素无序

D. 顺序方式存储，元素有序

知识点： 数据结构与算法

答案 D

10.串的长度是指（ ）。

A. 串中所含不同字母的个数

B. 串中所含字符的个数

C. 串中所含不同字符的个数

D. 串中所含非空格字符的个数

知识点： 数据结构与算法

答案 B

11.下列说法中错误的是（ ）。

A. 数据对象是数据的子集

B. 数据元素间关系在计算机中的映象即为数据的存储结构

C. 非顺序映象的特点是借助指示元素存储地址的指针来表示数据元素间逻辑关系

D. 抽象数据类型指一个数学模型及定义在该模型上的一组操作

知识点： 数据结构与算法

答案 B

12.下述文件中适合于磁带存储的是（ ）。

A. 顺序文件

B. 索引文件

C. 散列文件

D. 多关键字文件

知识点： 数据结构与算法

答案 C

13.设有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表，至少要进行（ ）次探测。

A. k-1

B. k

C. k+1

D. k(k-1)/2

知识点： 数据结构与算法

答案 B

14.设有一组关键字值（46,79,56,38,40,84），则用堆排序的方法建立的初始堆为（　）。

A. 79,46,56,38,40,84

B. 84,79,56,38,40,46

C. 84,79,56,46,40,38

D. 84,56,79,40,46,38

知识点： 数据结构与算法

答案 B

15.一棵度为3的树中，度为3的结点有2个，度为2的结点有2个，度为1的结点有2个，则度为0的结点有（　）。

A. 5个

B. 6个

C. 7个

D. 8个

知识点： 数据结构与算法

答案 C

16.具有n个顶点的有向强连通图最少有（ ）条弧。

A. n-1

B. n

C. n(n-1)

D. n(n-1)/2

知识点： 数据结构与算法

答案 B

17.设有无向图 G =(V,E)，其中顶点集合 V ={a,b,c,d,e,f}，边集合 E ={(a,b), (a,e), (a,c), (b,e), (c,f), (f,d), (e,d)}。对G进行深度优先遍历，正确的遍历序列是（　）。

A. a,b,e,c,d,f

B. a,c,f,e,b,d

C. a,e,b,c,f,d

D. a,e,d,f,c,b

知识点： 数据结构与算法

答案 D

18.广义表 (a,(b,(),c)) 的深度为（ ）。

A. 1

B. 2

C. 3

D. 4

知识点： 数据结构与算法

答案 C

19.设输入序列为ABC，输出序列为CBA，则经过的栈操作为（　　）。

A. push,pop,push,pop,push,pop

B. push,push,push,pop,pop,pop

C. push,push,pop,pop,push,pop

D. push,pop,push,push,pop,pop

知识点： 数据结构与算法

答案 B

20.外部排序是指（ ）。

A. 在外存上进行的排序方法

B. 不需要使用内存的排序方法

C. 数据量很大，需要人工干预的排序方法

D. 排序前后数据在外存，排序时数据调入内存的排序方法

知识点： 数据结构与算法

答案 B

21.一棵二叉树中第６层上最多有（ ）个结点。

A. ２

B. 31

C. 32

D. 64

知识点： 数据结构与算法

答案 C

22.若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（　）。

A. 快速排序

B. 堆排序

C. 归并排序

D. 直接插入排序

知识点： 数据结构与算法

答案 C

23.已知二叉树T的先序序列为abdegcfh，中序序列为dbgeachf，则T的后序序列为（　）。

A. gedhfbca

B. dgebhfca

C. abcdefgh

D. acbfedhg

知识点： 数据结构与算法

答案 B

24.含n个顶点的有向图最多有（ ）条弧。

A. n

B. n(n-1)

C. n(n+1)

D. n2

知识点： 数据结构与算法

答案 B

25.下列排序算法中（　）不能保证每趟排序至少能将一个元素放到其最终的位置上。

A. 快速排序

B. shell排序

C. 堆排序

D. 冒泡排序

知识点： 数据结构与算法

答案 B

26.设二维数组A5×8按行优先顺序存储，每个数据元素占2个字节，首地址即元素A[0][0]的起始地址为S，则元素A[3][6]的起始地址为（　）。

A. S+66

B. S+60

C. S+33

D. S+30

知识点： 数据结构与算法

答案 B

27.设无向图的顶点个数为n，则该图最多有（　）条边。

A. n-1

B. n(n-1)/2

C. n(n+1)/2

D. n2

知识点： 数据结构与算法

答案 B

28.对稀疏矩阵进行压缩存储的目的是（　）。

A. 便于进行矩阵运算

B. 便于输入和输出

C. 节省存储空间

D. 降低运算的时间复杂度

知识点： 数据结构与算法

答案 C

29.若查找每个元素的概率均相等，则在具有n个元素的静态查找表中采用顺序查找法查找一个记录，其平均查找长度ASL为（　）。

A. (n-1)/2

B. n/2

C. (n+1)/2

D. n

知识点： 数据结构与算法

答案 C

30.直接插入排序在最好情况下的时间复杂度为（ ）。

A. O(logn)

B. O(n)

C. O(n*logn)

D. O(n2)

知识点： 数据结构与算法

答案 D

31.一棵高为k的二叉树最少有（ ）个结点。

A. k-1

B. k

C. k+1

D. 2k-1

E. 2k-1

知识点： 数据结构与算法

答案 B

32.设串s1='abcdefg'，s2='ab'，则Concat(s1,s2)的返回值（　　）。

A. ab

B. cdefg

C. abcdefg

D. abcdefgab

知识点： 数据结构与算法

答案 D

33.顺序表中数据元素的存取方式为（　　）。

A. 随机存取

B. 顺序存取

C. 索引存取

D. 连续存取

知识点： 数据结构与算法

答案 A

34.设在一不带头结点的链队列中，front和rear分别为其队头和队尾指针，则判定该队中只有一个结点的条件是（ ）。

A. front->next

B. rear->next

C. front==rear

D. front!=rear

知识点： 数据结构与算法

答案 C

35.下面关于m阶B树说法正确的是（　）。

①每个结点至少有两棵非空子树；　　②树中每个结点至多有 m - 1 个关键字；

③所有叶子在同一层上；　　　　　　④当插入一个数据项引起B树结点分裂后，树长高一层。

A. ①②③

B. ②③

C. ②③④

D. ③

知识点： 数据结构与算法

答案 B

36.对二叉排序树进行（　）遍历所得的遍历序列中，关键字值是按升序排列的。

A. 前序

B. 中序

C. 后序

D. 层序

知识点： 数据结构与算法

答案 B

37.下列叙述中错误的是（ ）。

A. 树的度与该树中结点的度的最大值相等

B. 二叉树就是度为2的有序树

C. 有5个叶子结点的二叉树中必有4个度为2的结点

D. 满二叉树一定是完全二叉树

知识点： 数据结构与算法

答案 B

38.在待排元素序列基本有序的前提下，效率最高的排序方法是（　）。

A. 插入

B. 选择

C. 快速

D. 归并

知识点： 数据结构与算法

答案 A

39.下列叙述中错误的是（　）。

A. 对数组一般不做插入和删除操作

B. 顺序存储的数组是一个随机存取结构

C. 空的广义表没有表头和表尾

D. 广义表的表尾可能是原子也可能是子表

知识点： 数据结构与算法

答案 D

40.下列不属算法特性的是（ ）。

A. 有穷性

B. 确定性

C. 零或多个输入

D. 健壮性

知识点： 数据结构与算法

答案 D

41.由树转换而得的二叉树，根结点（ ）。

A. 没有左子树

B. 没有右子树

C. 左右子树都有

D. 视树的形态而定

知识点： 数据结构与算法

答案 B

42.（　　）是数据的不可分割的最小单位。

A. 数据元素

B. 数据对象

C. 数据项

D. 数据结构

知识点： 数据结构与算法

答案 C

43.以下属单链表优点的是（　　）。

A. 顺序存取

B. 插入操作能在O(1)的时间复杂度上完成

C. 插入时不需移动数据元素

D. 节省存储空间

知识点： 数据结构与算法

答案 C

44.在长为n的顺序表中删除一个数据元素，平均需移动（ ）个数据元素。

A. n

B. n-1

C. n/2

D. (n-1)/2

知识点： 数据结构与算法

答案 D

45.若采用顺序映象，则数据元素在内存中占用的存储空间（　　）。

A. 一定连续

B. 一定不连续

C. 可连续可不连续

知识点： 数据结构与算法

答案 A

46.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。

A. 顺序表

B. 双链表

C. 带头结点的双向循环链表

D. 单循环链表

知识点： 数据结构与算法

答案 A

47.判定一个栈顶指针为S且不带头结点的链栈为空栈的条件是（ ）。

A. S

B. S->next

C. S->next==NULL

D. !S

知识点： 数据结构与算法

答案 D

48.下列叙述中错误的是（　）。

A. 由树的先序遍历序列和后序遍历序列可以惟一确定一棵树

B. 二叉树不同于度为2的有序树

C. 深度为k的二叉树上最少有k个结点

D. 在结点数目相同的二叉树中，最优二叉树的路径长度最短

知识点： 数据结构与算法

答案 D

49.在一个可存放n个数据元素的顺序栈中，假设以高地址端为栈底，以top为栈顶指针，当向栈中压入一个数据元素时，top的变化是（ ）。

A. 不变

B. top=n

C. top++

D. top--

知识点： 数据结构与算法

答案 D

50.设在一不带头结点的链队列中，front和rear分别为其队头和队尾指针，则删除一个结点的操作是（ ）。

A. rear=front->next

B. rear=rear->next

C. front=front->next

D. front=rear->next

知识点： 数据结构与算法

答案 C