数据结构考试试卷(C语言版).docxVIP

********学院

学期期末试题一据结构（C语言）

一.选择题（10X2分）：共10小题，请将答案壊入题中的括号中，毎小题惟独一个正确答案，错选或者不逸均不给分?

1.

2.

组成数据的基本单位是（）

A.数据项

C.数据元素下面程序段的时间复杂度为（fbr（i=l;i=n;i++）

for（J=ij=n;j++）

s++,

A.0（1）

B.数据类型数据变量

D.

B.

0(n)

C?O(nlog/))

D.

O(n2)

在一个长度为n的顺序存储线性表中，向第1个兀素（1WiWn+1）之前插入一个新兀素时,需向后挪移（）个元素。

A.U-1

C.n-1-l

4.设单链表中指针p指向结点A,操作为（）?

A.p-next=p-next-next

C.p=p-next-next

若让元素1,2,3挨次进栈，

A、3,2,1

C,3,1,2

3.

5.

6.

7.

8.

9.

B.n-1+l

D.1

若要删除A后的结点且该结点存在，则需要修改指针的

B■p=p-next

D.p-next=p

则出栈次序不可,能浮现()种情况。

B,2,1,3

D.1,3.2

在一个循环顺序队列中，队首指针指向队首元素的（）位置。

A、当前 B、后面

C、前一个 D、后一个

假定一个链队的队首和队尾指针分别为front和

A、front=NULL

C、rear!=NULL

二叉树第证二1）层最多有（

A.21

C.21

rear.则判断队空的条件是（）。

B、front!=NULL

D.front二二rear

）个结点。

B.2时

D?2l-l

如果结点A有3个兄弟，而且B为A的双亲，则B是度为（）

A.4 B.3

C.5 D.1

下列哪种排序算法的平均时间复杂度最优（）o直接选择排序

冒泡排序

10.当待排序序列的关键码是随机分布时,A.直接插入排序

C.快速排序

B.

D.

二.填空题（30分）：每空2分

PAGE

PAGE#

PAGE

PAGE#

数据的逻辑结构被分为 、 和 四种。

在一个长度为n的顺序表中插入一个元素，至少需挪移 个元素,最多需挪移 个元素。

双向循环链表的优点是

队列的原则是 。

顺序存储的队列如果不采用循环方式，则会浮现 问题。

具有64个结点的彻底二叉树的深度为 。

设一颗彻底二叉树共有50个叶子结点，则它共有 个度为2的结点。

二叉树釆用 遍历可以得到结点的有序序列。

在一个具有n个顶点的无向彻底图中，包含有 条边，在一个具有n个顶点的有向彻底图中，包含有 条边。

快速排序算法在最差的情况卜其时间复杂度是 。

=.判断题（5X2分）

任意—?棵满二叉树一定也是彻底二叉树°（）

进栈操作时，必须判断栈是否己满。（）

—个程序的时间岌杂度是指该程序运行时间与问题规模的对应关系。（）

采用链式结构存储线性表时，其地址可以是不连续的。（）

折半查找法的前提之一是线性表有序。（）

四.应用题（4X5分）

试比较顺序存储和链式存储的优缺点。（5分）

筒述栈和队列这两种数据结构的相同点和不同点0（5分）

己知一棵二叉树的中序序列和后序序列分别是BDCEAFHG和DECBHGFA,试画出这棵二叉树o（5分）

对于给定的一组关键码：83.40,63,13,84,35,画岀用冒泡排序对上述序列进行操作的各趟结果。（5分）

五.算法设计题（20分）

编写算法，将任意十进制数转换成其他进制.要求写出完整代码，可采用顺序栈或者链栈实现o（12分）

编写一算法完成瑟夫生死者游戏o（8分）

瑟夫生死者游戏的描述：N个旅客同乘-条船，因为严重超我，加之风浪大，危（wei）险万分；因此船长告诉乘客，惟独将全船一半的旅客投入海中，其余人材干避免遇难。无奈，大家只得允许这种办法，并拟定个人围成-?圈，由第一个人数起，挨次报数，数到第r人，便把他投入海中，然后再从他的下一个人数起，数到第r人，再将他仍进海里，如此循环的进行,直到剩卜N/2个乘客为止。问哪些位置是将被扔卜大海的位置口

答案及评分标准:

数据结构（C语言）答案及评分标准

选择题（10X2分）：每小题惟独一个正确答案，错选或者不选均不给分。

1

2

3

-

6

/

8

7

K

C

D

B

A

C

C

D

B

A

C

填空题（30分）：每空2分。

集合线性结构树型结构图型结构

TOC\o1-5\h\z0n

既可以方便的找到后继结点又可以方便的找到前驱结点。

先进先出

假溢岀

7

49

中

n（nT）/2n（nT）

0（n2）o

=.判断题（5X2分）

V；2.X；3.V；