专升本《数据结构》试卷答案(课件)

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

案

专升本《数据结构》

一、 (共75题,共150分）

1．数据的基本单位是（）。 (2分）

A．数据元素Ｂ。记录 C.数据对象Ｄ。数据项

．标准答案:Ａ

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

A．数据对象 B．数据元素Ｃ．数据类型

D.数据项

.标准答案：D

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

A.时间效率

B.空间效率 C．可读性 D.健壮性

。标准答案：B

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

A.栈B．队列 C.串

D。数组

．标准答案:B

５。串的长度是指串中所含(）的个数. （2分）

Ａ.不同字符 B.不同字母Ｃ。相同字符

D.所有字符

。标准答案：D

６. 采用带头结点双向链表存储的线性表，在删除一个元素时,需要修改指针（)次. (2分）A。1 B.2 C．3

D。4

．标准答案：B

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

Ａ。顺序存取 B。随机存取 C．索引存取

D。Hasｈ存取

.标准答案:B

8．数组a［1。.m］采用顺序存储，a［1]和a[m］地址分别为1024和１150,每个元素占2字节,则ｍ是（). (２分）

A.64 B。3２Ｃ。１６

Ｄ.8

．标准答案:A

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

C。２ｈ—1 D.２h

。标准答案：C

10。ｍ个结点的二叉树，其对应的二叉链表共有(）个非空链域。 (2分）

Ａ。m B。m+1 C.2m

Ｄ。m—１

。标准答案：B

１1。下面叙述错误的是（）。（2分）

A.顺序表是借助物理单元相邻表示数据元素之间的逻辑关系B。对于空队列进行出队操作过程中发生下溢现象

C．有向图的邻接矩阵一定是对称的

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

.标准答案：C

12. 以下与数据的存储结构无关的术语是（）。（２分）Ａ。循环队列 B.双向链表Ｃ。哈希表

D.数组

。标准答案：Ｄ 13. 在一个长度为n 的链式栈中出栈实现算法的时间复杂度为（）。 （2分） Ａ.O （1） Ｂ。Ｏ(lo ｇ n)

C.Ｏ（n ） Ｄ．O （n 2） 。标准答案:A １4。 在具有k 个度数为2的二叉树中，必有（）个叶子结点. (２分） A ．k Ｂ.k-1 C.2ｋ

D.ｋ＋１ .标准答案：D 15. 在关键字序列(10，20，30,40，５0）中,采用折半法查找20，关键字之间比较需要（)次。 （２分） A 。1 Ｂ.2 C.3 D ．４ 。标准答案：Ｃ １６. 1６某二叉树的后序遍历序列和和中序遍历序列均为a ｂcd ，该二叉树的前序遍历序列是(）。 (２分) A.ａbcd Ｂ．dcba C.ａcbd D 。dbca .标准答案:B 17。 n 个顶点的无向连通图的生成树，至少有()个边。 （2分) A 。ｎ（n-１） Ｂ。n(n —１）/2 C ．２ｎ D 。ｎ—1 .标准答案：D １8. 可以采用（）这种数据结构,实现二叉树的层次遍历运算。 （2分） A ．队列 B ．树 C 。栈 Ｄ.集合 .标准答案:A １９. 假设以数组A ［0。。n-1］存放循环队列的元素，其

头指针fron ｔ指向队头元素、尾指针r ｅa ｒ指向队尾元素一个，则在少用一个元素空间的前提下,队列空的判定条件为(）。 （2分） A.r ｅａr= ＝front B 。（front+1)％

n ＝ =ｒear

C 。rea ｒ+1= ＝fro ｎt

D 。(r ｅａr ＋

1）%n= =fr ｏnt

。标准答案：A

2０. 序列（21，19，37，5，2）经冒泡排序法由小到大排序,第一趟后所得结果为（). （2分)

A ．（19，２1，37，5,2）

B 。（19,21,

５,2,37）

C.（19,2１,５，37，2) Ｄ。（19，2１,２，

5,３7）

．标准答案:Ｂ

21. 二叉链表适合作为(）的存储结构。 （2分)

A 。队列 B.二叉树 C.树

D ．森林

.标准答案：B,C,Ｄ

2２. 设哈希（Hash)函数为H(ｋ）= ｋ ％ １７，其中k 为

关键字,关键字(）是同义词。 （2分）

A 。4４，5,1５

B ．２8，45,62 C.6，57,１2５ D ．201，3１,４８

.标准答案：B ，Ｃ，D

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

Ａ．｛94，68，23，16,5 B ．{94，２３，

68,5，１6

C ．｛94，23，16，6８，５ D.｛9４，16，68，２3，5

.标准答案:C ，D

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

A．选择排序 B．快速排序 C。归并排序

D。冒泡排序

.标准答案：B,Ｃ

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

Ａ。队列Ｂ.稀疏矩阵Ｃ.边或弧数较少的图Ｄ.二叉树

.标准答案：B,Ｃ

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

Ａ.６类 B.5类 C.4类

D。3类

．标准答案：Ｃ

27。（）不是算法具有的5个特性之一. （2分)

Ａ.有穷性 B。确定性 C。可行性

D.正确性

。标准答案：Ｄ

２8. 算法的时间复杂度是对算法(）的度量. （2分)

A.时间效率 B．空间效率C。可读性

D。健壮性

.标准答案：A

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

A.必须是连续的

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

C。必须是不连续的 D．连续或不连续都可以.标准答案：D

3０. 二维数组通常采用顺序存储，其优点是（)。（2分)Ａ。便于增加存储空间 B.防止下标溢出

Ｃ。避免数据元素的移动 D.便于依据下标进行随机存取。标准答案:D

３1. 采用顺序存储的线性表，若表长为n，在第i号元素之

后插入一个元素时,需要移动（）个元素。（2分）

A.i+1 B。i C。n-i

Ｄ．n-ｉ+１

.标准答案:C

３２. 若已知一个栈的入栈序列是１、2、３、４，其出栈序

列不可能为＿________. （２分）

A。1、４、３、２Ｂ．３、４、1、2 C。４、

３、２、1 D.2、3、4、1

。标准答案:Ｂ

3３。数组a［1.。256]采用顺序存储，a的首地址为10,每

个元素占2字节，则ａ[２１］的地址是（). (2分）

A。1０ B.３０Ｃ.50 D．70

．标准答案：Ｃ

34. 深度为ｈ的完全二叉树至少有（)个叶子结点. (2分)

A.2(h-1）+1 Ｂ。2（h—２)+１

C。2h-１Ｄ．2ｈ-2

．标准答案：D

３５。若二叉树对应的二叉链表共有ｍ个非空链域，则该二

叉树有（）个结点的二叉树。（2分）

A。ｍ B.m－1 Ｃ.m+1 D.2m

．标准答案：B

3６。下面叙述错误的是（）。 (２分)

A．单链表是借助指针表示数据元素之间的逻辑关系

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

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

唯一的

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

。标准答案：Ｃ

３７。以下(）术语与数据的存储结构无关（2分）

A。栈 B.哈希表 C．线索树

D.双向链表

。标准答案:Ａ

３8．在一个长度为n的链式队列中入队实现算法的时间复杂度为()。（２分）

Ａ。Ｏ（1）Ｂ．O（log n)

Ｃ．O(n）Ｄ．O（n2) 。标准答案:Ａ

３9. 队列的出队操作是指()操作。(2分）

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

D.队头插入

.标准答案：B

40. 在关键字序列(10，15，20，25，30）中采用折半法查找２5，依次与(）关键字进行了比较。(2分)

A。３0，25 Ｂ.２0，25 C.20,３0，25 D。25

。标准答案：B

41。 16某二叉树的前序遍历序列和和中序遍历序列分别为abcd和ｂcad,该二叉树的后序遍历序列是（）。（2分)Ａ．ｃｂｄa B.ｄｃba Ｃ。abc ｄ D.dcba

．标准答案:A

４2。所占用的存储空间大小仅与图的顶点个数相关的存储结构是（). （2分)

A.邻接表

B.逆邻接表

Ｃ.十字链表 D．邻接矩阵

。标准答案：D

４３．可以采用(）这种数据结构,实现图的深度优先遍历运算. (2分)A.队列B．树 C．栈

D.集合

。标准答案：C

４4。线性表采用带头结点单链表实现,head为头指针，则判

断表空的条件为（). （2分）

A.heａd＝= NUＬL B。ｈｅad!=NULＬ

C。ｈeａd－〉next=＝NULL D。hｅａd-〉nex

ｔ！=NULL

。标准答案:C

45. 在关键字序列(35,1０，15，20，25)中采用最低位优先

排序（LSＤ）基数排序，第一趟之后所得结果为(）。（2

分）

A.１0，20，15，25,35

B.10，20，3５，15,２5 C。20，１0，35,2５，15 Ｄ.20，10,３5，１

5，２5

。标准答案:B

4６。下列逻辑结构中,（)为线性结构。（2分）

A。栈 B。队列Ｃ。串

D。二叉树

．标准答案：A,Ｂ,C

47. 深度为３的二叉树可能的结点个数是（）。（2分)

A．1 Ｂ．2 C。３

D.4

.标准答案：A,Ｂ

4８．下列各项键值(）序列是大顶堆的。（2分）

Ａ．{23，68，9４，１6,５ B．｛９4，68,２

3，16,5

C.{９4，23,68,1６，5 D．{９４，１6，６８,

２3，5

.标准答案：B，C

49。下列（）是限制了插入和删除操作的特殊线性表。（２分）

A．栈 B．队列 C.串

D。数组

．标准答案：A,Ｂ

50。对一棵二叉排序树,用（）方法进行遍历，不一定得到各结点键值的有序序列。(2分）

Ａ．先根遍历Ｂ。中根遍历 C.后根遍历Ｄ。层次遍历

.标准答案:A,C，D

51。数据的最小单位是(）。（２分）

A．数据元素Ｂ.记录 C.数据对象Ｄ。数据项

．标准答案：Ｄ

52．算法是对某一类问题求解步骤的有限序列。其中，（）是算法具有的5个特性之一. （2分）

A。有穷性 B.正确性 C。可读性

D。健壮性

。标准答案:A

53．（）是数据的逻辑结构。（2分）

A.顺序表

B.链表C．线性表

Ｄ。十字链表

。标准答案:C

５4. （)是限制了插入和删除操作在一端进行的线性表。（2分）

A．栈 B。队列C．串

D。数组

。标准答案：A

55。（)是限制了插入和删除操作分别在两端进行的线性表。 (2分)

A.栈 B．队列 C。串

Ｄ。数组

。标准答案：Ｂ

５６. 用链表表示线性表的优点是（）. (2分)Ａ。便于插入和删除

B.便于随机存取

C．花费的存储空间较顺序存储少

D.数据元素的物理顺序与逻辑顺序相同

．标准答案：Ａ

５７. 若已知一个栈的入栈序列是1、2、３、4，其出栈序列不可能为（）. （2分)

Ａ.1、4、3、2 B。2、3、4、１ C.4、３、２、1 D.3、4、１、2

。标准答案：D

58. 串下列关于串的叙述中，正确的是（）。 (2分)

Ａ。2个串的长度相等,则2个串相等

B。空串至少包一个空格

Ｃ。替换操作可以实现字符的删除

D。一个串的长度至少是１

.标准答案：C

59。深度为h的二叉树，第h层至少有(）个结点。（２分）

Ａ.0 B。１ C.8 Ｄ.16

。标准答案:B

６0．假设n≥0,在程序段{y＝0；whilｅ((ｙ+1)＊（y＋1）A．n

B．［]

Ｃ．n２

.标准答案:Ｃ

61. 下面叙述错误的是（)。（2分)

A。在集合{１，2，3，4，5中元素1是2的直接前驱

B。二叉排序树的中序遍历序列一定是有序的

C。有3个结点的不同形态二叉树的数目为5

D．哈夫曼树中所有结点的孩子数目只可能为2或者为０

。标准答案：A

６2．以下数据结构中,（)是线性结构. （2分)

A．广义表B。二叉树C。稀疏矩阵Ｄ。串

。标准答案：Ｄ

63. 在一个长度为ｎ的顺序表中删除一个元素的算法的时间复杂度为（)。（2分)

A。O

（1) Ｂ。O（ｌog n）

C。

O(n) Ｄ.O(ｎ２）

.标准答案:C

64. 如果一个huffman树含有n个叶子，则该树必有（)的结点。（2分)

A.n+1 B．2ｎ

+1 C。2n D。2n-1

．标准答案：D

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

A。

１Ｂ．２

C.3

D.4

.标准答案：B

66。１６某二叉树的前序遍历序列和和中序遍历序列均为abcd,该二叉树的后序遍历序列是(）。（2分)

A。abcd B.ｄ

cba C.ａｃｂ

ｄＤ。dbcａ

。标准答案:Ｂ６7．ｍ个顶点的有向完全图有()个弧。（2分)

A.ｍ(ｍ-１)/2

B.m＋

1 C。

ｍ D.m(m－

１）

.标准答案：D

6８. 下列各项键值（)序列不是堆的. (2分)

A.{９4,6８,23,1６，5 Ｂ。｛94，２3，68，5，1６

C。{94，2３，68，１6,５D。{９４，16，６8，23，5

。标准答案:D

69。设单链表中指针ｐ指向结点A，q指向新元素结点，若要Ａ之后插入一个新元素，则所需修改指针的操作为(）. (２分)

A。p－＞next=ｑ，q-〉nｅxt=ｐ—〉ｎexｔ

B.q—〉ｎext=ｐ-〉next，ｐ-＞next=q

C。p-＞nexｔ=q－>nｅxt，q—〉ｎｅｘt＝ｐ

D.p—〉next=p,q—>next=p->ｎext

。标准答案：Ｂ

7０. 在关键字序列（１４9，13８，１65，１97，１7６,１１3,127）中采用最低位优先排序(ＬＳD）基数排序,第一趟之后所得结果为（）。（2分）

A。1４9，1３8，1６５，197，176,113，１27

B.128，1４９,165，19７,１１3,17６,127

C。１2８，149，165，１９7,113,127,1７6

D。113，1２7，１３8,149，1６5，1７6,197

．标准答案：Ｂ

71. 下列术语表示的数据中,（）是同义语。（2分）

Ａ。结点B。数据元

素C．顶点D。数据

项

．标准答案：A,Ｂ，C

72。对于采用链式结构的队列，（）运算的实现算法的时间复杂度为O（１）。（2分)

A.入队B．出

队Ｃ．求队长D。队清空

．标准答案：A,Ｂ

7３. 在n个数据元素中进行查找,（）方法的最坏时间复杂度为Ｏ(n）. (2分）

A。顺序查

找B．折半查

找

C.二叉排序树查找Ｄ。斐波那契查找

。标准答案：A，C

７４. 下列是二叉树4种常见的遍历方法。其中，（）属于深度优先遍历。（2分）

Ａ.前序遍历 B.中序遍历C．后序遍历D。层序遍历

.标准答案:A,Ｂ，C

７5。下列()哈希函数构造方法所得的哈希函数,使得查找时间复杂度通常不能到达O（1). （2分)

A。直接定地法B．数字分析法Ｃ。平方取中法D．折叠法

。标准答案：B,Ｃ,Ｄ

...谢阅...