专升本《数据结构》_试卷_答案

第1页共5页 1

专升本《数据结构》

一、 （共７5题，共１５０分）

１。 数据的基本单位是(）。 （2分)

A。数据元素 Ｂ。记录 C。数据对象 D。数据项

.标准答案：Ａ

2． ()是数据的不可分割的最小单位。 （2分）

A。数据对象 Ｂ。数据元素 C.数据类型 D。数据项

。标准答案:D

3． 算法的空间复杂度是对算法()的度量． (2分)

Ａ.时间效率 B。空间效率 C。可读性 Ｄ。健壮性

。标准答案:B

4. （)是限制了数据元素的内部结构仅为一个字符的线性表． （2分）

A.栈 B。队列 Ｃ．串 Ｄ。数组

。标准答案：B

５。 串的长度是指串中所含（)的个数. （２分)

A．不同字符 B。不同字母 Ｃ。相同字符 D.所有字符

。标准答案:D

6。 采用带头结点双向链表存储的线性表,在删除一个元素时，需要修改指针(）次.

(２分)

Ａ。1 B.2 C。3 D。4

.标准答案:B

7。 线性表的顺序存储结构是一种（)的存储结构。 (2分)

Ａ。顺序存取 B。随机存取 C.索引存取 Ｄ。Hａsｈ存取

。标准答案:B

８。 数组ａ[1。.m]采用顺序存储，ａ［１]和ａ［m］地址分别为102４和1150，每个元素占2字节，则ｍ是()。 (2分）

A.64 Ｂ。３２ C。１６ D。８

。标准答案：A

9。 深度为ｈ的二叉树，第h层最多有（)个结点。 （2分)

Ａ。h B。2ｈ—１

Ｃ。2ｈ—1 D。２h 。标准答案：C

10。 m个结点的二叉树，其对应的二叉链表共有（）个非空链域. （2分)

A．m B。m+1 C.2m Ｄ．ｍ—1

。标准答案:B

11. 下面叙述错误的是(）。 (２分）

A．顺序表是借助物理单元相邻表示数据元素之间的逻辑关系

B。对于空队列进行出队操作过程中发生下溢现象

Ｃ。有向图的邻接矩阵一定是对称的

D.具有相同的叶子个数和具有相同的叶子权值的赫夫曼树不是唯一的

。标准答案：C

12。 以下与数据的存储结构无关的术语是(). （2分)

A。循环队列 Ｂ。双向链表 Ｃ。哈希表 Ｄ。数组

.标准答案：D

13。 在一个长度为n的链式栈中出栈实现算法的时间复杂度为(). （2分）

A.O（1） B.O(log n）

Ｃ.O(ｎ） D。Ｏ(ｎ2)

．标准答案：A

1４. 在具有k个度数为2的二叉树中，必有(）个叶子结点。 （2分)

Ａ。k B。ｋ—1 C。2k D.k+1

。标准答案:Ｄ

１5. 在关键字序列（10,20,30,４0，50)中,采用折半法查找20,关键字之间比较需要(）次。 （2分）

A.１ Ｂ。2 C.3 D.4

。标准答案：C

16。 16某二叉树的后序遍历序列和和中序遍历序列均为abcd,该二叉树的前序遍历序列是（)。 (２分)

Ａ。abcd B。dcｂa C．acbd Ｄ.dｂcａ

。标准答案:Ｂ

17。 n个顶点的无向连通图的生成树,至少有()个边。 (２分）

Ａ。n（n-1） B。n(ｎ—１)/２ C。2ｎ D.ｎ-1

。标准答案:Ｄ

１8。 可以采用()这种数据结构，实现二叉树的层次遍历运算。 （2分)

Ａ。队列 B．树 C。栈 D.集合

。标准答案：Ａ 第2页共5页 2

19． 假设以数组Ａ［０.。n-１]存放循环队列的元素，其头指针fｒont指向队头元素、尾指针rear指向队尾元素一个，则在少用一个元素空间的前提下,队列空的判定条件为（)． （2分）

A。ｒear＝ =front Ｂ。(frｏnt+1)％n= ＝rｅaｒ

C。rear+1＝ ＝frｏnt D.（rear+1)％n= ＝ｆront

。标准答案：Ａ

20。 序列(21，19，3７，5,2）经冒泡排序法由小到大排序,第一趟后所得结果为()。 (2分）

A.（19,21，３7,5,2) B.(1９,21，5,2，37）

C.(19，2１,5，37，2） D。(１9,21,2,5,37）

。标准答案:B

2１。 二叉链表适合作为(）的存储结构。 (2分）

A。队列 B。二叉树 C。树 Ｄ。森林

．标准答案:B，Ｃ,Ｄ

22。 设哈希（Ｈaｓh)函数为H（k)= k % 17，其中k为关键字，关键字()是同义词。 （2分)

A.44，5,１５ B．2８,４5，6２ C.６，57,125 D．20１,３1，48

。标准答案：B，Ｃ,D

２3． 下列各项键值（)序列不是堆的。 (２分）

A.｛94,68，23,16,5 B.{9４,23,６8，5,16

C。{94,23,16,6８，5 D。{９4,１6,68，23，５

。标准答案:C,Ｄ

24。 在下列排序方法中，()的空间复杂度为O（n).其中，ｎ为参加排序的元素个数. (2分)

A。选择排序 Ｂ.快速排序 C。归并排序 D。冒泡排序

。标准答案:Ｂ,C

25。 十字链表适合于（）选作存储结构。 (２分)

A。队列 Ｂ.稀疏矩阵

C。边或弧数较少的图 D．二叉树

。标准答案:Ｂ,C

26。 基于数据的逻辑关系，数据的逻辑结构划分为（）基本结构. （2分)

A.６类 B。5类 C。4类 D。3类

。标准答案:Ｃ

2７。 (）不是算法具有的5个特性之一。 (2分) A。有穷性 B。确定性 C。可行性 Ｄ。正确性

。标准答案：D

28。 算法的时间复杂度是对算法(）的度量. (2分)

A。时间效率 B。空间效率 Ｃ。可读性 D.健壮性

．标准答案:A

２９。 线性表若采用链式存储结构时,要求结点的存储单元地址(）． (2分)

A.必须是连续的 B.部分地址必须是连续的

Ｃ。必须是不连续的 D。连续或不连续都可以

.标准答案:D

30。 二维数组通常采用顺序存储，其优点是()。 （2分)

A。便于增加存储空间 B。防止下标溢出

C.避免数据元素的移动 D。便于依据下标进行随机存取

。标准答案:D

３1。 采用顺序存储的线性表，若表长为n，在第i号元素之后插入一个元素时，需要移动()个元素. （2分)

Ａ.ｉ+1 B。ｉ C。n—ｉ Ｄ．n—i＋1

。标准答案:C

32． 若已知一个栈的入栈序列是1、2、3、４,其出栈序列不可能为__＿______.

（２分)

A。１、４、3、2 B.3、4、１、2 C。4、3、２、1 D。２、3、4、1

。标准答案：B

33. 数组a[１。.256]采用顺序存储,a的首地址为１0,每个元素占２字节,则a[21]的地址是()。 （2分）

Ａ.10 Ｂ。30 Ｃ。50 D。70

。标准答案：Ｃ

３4。 深度为h的完全二叉树至少有（)个叶子结点． （2分)

A。2（h—１）+1 B。2(h-2）+1

C。2h-1 D。2h—２

。标准答案:Ｄ

35. 若二叉树对应的二叉链表共有m个非空链域,则该二叉树有（）个结点的二叉树． (2分)

Ａ。m B。m-1 Ｃ。m＋1 D。2ｍ

。标准答案:B

３6. 下面叙述错误的是()。 （2分) 第3页共5页 3 Ａ。单链表是借助指针表示数据元素之间的逻辑关系

B。在顺序栈的入栈操作过程中可能发生上溢现象

Ｃ。具有相同的叶子个数和具有相同的叶子权值的赫夫曼树是唯一的

D。无向图的邻接矩阵一定是对称的

。标准答案:C

3７. 以下()术语与数据的存储结构无关 (2分)

A.栈 B。哈希表 C。线索树 D。双向链表

。标准答案：A

3８。 在一个长度为n的链式队列中入队实现算法的时间复杂度为(). （2分)

A。Ｏ（１) B。O（loｇ n）

C.O（n) D。O(n2）

.标准答案：A

39. 队列的出队操作是指()操作。 （2分)

A．队尾删除 B.队头删除 C。队尾插入 Ｄ。队头插入

。标准答案:B

40。 在关键字序列(１０，15，20,25，3０)中采用折半法查找25,依次与(）关键字进行了比较。 （2分）