西昌学院数据结构导论期末考试复习题及参考答案

西昌学院成人在线学习平台

数据结构导论在线考试

课程名称：数据结构导论（专升本）

1.（单选题）2线性表是具有n个（）的有限序列。（本题2.0分）

A.表元素

B.字符

C.数据元素

D.信息项

答案：C.

解析：无.

2.（单选题）算法指的是（）。（本题2.0分）

A.计算机程序

B.解决问题的计算方法

C.排序算法

D.解决问题的有限运算序列

答案:D.

解析：无.

3.（单选题）在数据结构中，从逻辑上可以把数据结构分成【】。（本题

2.0分）

A.动态结构和静态结构

B.紧凑结构和非紧凑结构

C.线性结构和非线性结构

D.内部结构和外部结构

答案：C.

解析：无.

4.（单选题）数据结构在计算机内存中的表示是指【】。（本题2.0分）

A.数据的存储结构

B.数据结构

C.数据结构的逻辑结构

D.数据元素之间的关系

答案:A.

解析：无.

5.（单选题）在存储数据时，不仅要考虑存储各数据元素的值，而且还要存储

【]o（本题2.0分）

A.数据处理的方法

B.数据元素的类型

C.数据元素之间的关系

D.数据的存储方法

答案：C.

解析：无.

6.（单选题）栈和队列的共同点是【】。（本题2.0分）

A.都是先进先出

B.都是后进后出

C.只允许在端点处进行插入和删除

D.无共同点

答案：C.

解析：无.

9.（单选题）采用顺序查找法查找长度为n的查找表时，每个元素查找的平均查

找长度为【】。（本题2.0分）

A.n

B.n/

C.n+1/2

D.n-1/2

答案：c.

解析：无.

10.（单选题）一个有N个顶点的有向图最多有（）条边。（本题2.0分）

A.N

B.N（N-l）

C.N（n-l）/2

D.2N

答案:B.

解析：无.

11.（单选题）若串S="software",其子串的数目是（）。（本题2.0分）

A.8

B.37

C.36

D.9

答案：B.

解析：无.

12.（单选题）在数据结构中，与所使用的计算机无关的是数据的结构。（本题

2.0分）

A.逻辑

B.存储

C.逻辑和存储

D.物理

答案：A.

解析：无.

13.（单选题）一个具有N个结点的有序单链表中插入一个新结点使得数据仍然有

序,其算法时间复杂度为（）。（本题2.0分）

A.0（logn）

B,0（1）

C.0（n2）

D.0（n）

答案：D.

解析：无.

14.（单选题）线性表是（）。（本题2.0分）

A.一个有限序列，可以为空

B.一个有限序列，不能为空

C.一个无限序列，可以为空

D.一个无序序列，不能为空

答案:A.

解析：无.

15.（单选题）线性表采用链式存储时,其地址（）。（本题2.0分）

A.必须是连续的

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

C.一定是不连续的

D.连续与否均可以

答案：D.

解析：无.

16.（单选题）设单链表中指针p指着结点A,要删除A之后的结点（若存在），则需

修改指针的操作为（）。（本题2.0分）

A.p->next=p->next->next

B.p=p->next

C.p=p->next->next

D.next=p

答案：A.

解析：无.

17.（单选题）在双向链表存储结构中，删除p所指的结点时需修改指针（）。（本

题2.0分）

A.p->prior->next=p->nextp->next->prior=p->prior

B.p->prior=p->prior->nextp->prior->prior->next=p

C.p->prior->prior->next=pp->prior=p->prior->prior

D.p->next->next->prior=pp->next=p->next->next

答案:A.

解析：无.

18.（单选题）若元素a、b、c、d、e、f依次进栈，允许进栈、退栈的操作交替进

行,但不允许连续3次退栈工作,则不可能得到的出栈序列是（）。（本题2.0分）

A.dcebfa

B.cbdaef

C.bcaefd

D.afedcb

答案：D.

解析：无.

21.（单选题）栈和队列具有相同的（）。（本题2.0分）

A.抽象数据类型

B.逻辑结构

C.存:储结构

D.运算

答案：B.

解析：无.

22.（单选题）一个队列的入队序列为1234,则出队序列是（）。（本题2.0分）

A.4321

B.1234

C.1432

D.3241

答案：B.

解析：无.

23.（单选题）以下关于二叉树的说法正确的是（）。（本题2.0分）

A.二叉树中每个结点的度均为2

B.二叉树中至少有一个结点的度为2

C.二叉树中每个结点的度可以小于2

D.二叉树中至少有一个结点

答案：C.

解析：无.

24.（单选题）一棵满二叉树共有64个叶子结点，则其结点个数为（）。（本题2.0

分）

A.64

B.65

C.127

D.128

答案：C.

解析：无.

25.（单选题）有n个元素的数组，查找其中最大值的元素，一般需要（）次元素的

比较。（本题2.0分）

A.1

B.n

C.n+1

D.n-1

答案：C.

解析：无.

26.（单选题）以下排序中，关键字比较的次数与元素的初始排列的次序无关的是

（）。（本题2.0分）

A.希尔排序

B.冒泡排序

C.插入排序

D.简单选择排序

答案：D.

解析：无.

27.（单选题）（）不是算法的基本特性。（本题2.0分）

A.可行性

B.长度有限

C.在规定的时间内完成

D.确定性

答案：B.

解析：无.

28.（单选题）某算法的时间复杂度为0（n2）,表明该算法的（）。（本题2.0分）

A.问题规模是n2

B.执行时间等于n2

C.执行时间与n2成正比

D.问题规模与n2成正比

答案：C.

解析：无.

29.（单选题）线性表的静态链表存储结构与顺序存储结构相比，优点是（）。（本

题2.0分）

A.所有的操作算法实现简单

B.便于随机存取

C.便于插入和删除

D.便于利用零散的存储器空间

答案：C.

解析：无.

30.（单选题）带头结点的单链表L为空的判定条件时（）。（本题2.0分）

A.L==NULL

B.L->next==NULL

C.L->next==L

D.L!=NULL

答案：B.

解析：无.

31.（单选题）在双向链表存储结构中,删除p所指的结点的前驱结点（若存在）时

需修改指针（）。（本题2.0分）

A.p->prior->next=p->nextp->next->prior=p->prior

B.p->prior=p->prior->nextp->prior->prior->next=p

C.p->prior->prior->next=pp->prior=p->prior->prior

D.p->next->next->prior=pp->next=p->next->next

答案：c.

解析：无.

32.（单选题）一个栈的进栈序列是a、b、c、d、e,则栈的不可能输出序列是（）。

（本题2.0分）

A.edcba

B.decba

C.dceab

D.abcde

答案：c.

解析：无.

33.（单选题）递归模型为f（l）=l,f（n）=f（n-l）+n（n〉l）,其中递归体是（）。（本

题2.0分）

A.f（n）=f（n-l）+n

B.f（0）=l

C.f（l）=0

D.f（n）=n

答案：A.

解析：无.

34.（单选题）已知输入序列是abed,经过输出受限的双端队列后能得到的输出序

列是（）。（本题2.0分）

A.dacb

B.cadb

C.dbea

D.以上序列都不能得到

答案：B.

解析：无.

35.（单选题）以下（）是“abcd321ABCD”串的子串。（本题2.0分）

A.abed

B.321AB

C.“abcABC”

D.“21AB”

答案:D.

解析：无.

36.（判断题）顺序队列中的元素个数，可以根据队首指针和队尾指针的值计算出

来。（）（本题2.0分）

A.true

B.false

答案：A.

解析：无.

37.（判断题）二分查找可以在有序的双向链表上进行。（）（本题2.0分）

A.true

B.false

答案：B.

解析：无.

38.（判断题）逻辑结构不相同的数据，必须采用不同类型的存储方法（）。（本题

2.0分）

A.正确

B.错误

答案：B.

解析：无.

39.（判断题）在单链表中，可以从头结点开始查找任何一个结点。（）（本题2.0

分）

A.正确

B.错误

答案：A.

解析：无.

40.（判断题）栈底元素是不能删除的元素。（）（本题2.0分）

A.正确

B.错误

答案：B.

解析：无.

41.（判断题）用一维数组存储特殊矩阵，可以简化对矩阵的存取操作。（）（本题

2.0分）

A.正确

B.错误

答案：B.

解析：无.

42.（判断题）树适合表示层次关系。（）（本题2.0分）

A.正确

B.错误

答案：A.

解析：无.

43.（判断题）在先序、中序和后序序列中，叶子结点出现的相对次序是相同的。

（）（本题2.0分）

A.正确

B.错误

答案：A.

解析：无.

44.（判断题）对一个图进行广度优先遍历时,每个顶点恰好进队和出队各一次。

（）（本题2.0分）

A.正确

B.错误

答案:A.

解析：无.

45.（判断题）基数排序是一种稳定