******** 学院
学期期末试题一据结构（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个兀素（1 WiWn+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分

1.数据的逻辑结构被分为    '    、    和    四种。
2.在一个长度为n的顺序表中插入一个元素，至少需挪移    个元素,最多需挪移     个元素。
3.双向循环链表的优点是   
4.队列的原则是    。
5.顺序存储的队列如果不采用循环方式，则会浮现    问题。
6.具有64个结点的彻底二叉树的深度为    。
7.设一颗彻底二叉树共有50个叶子结点，则它共有    个度为2的结点。
8.二叉树釆用    遍历可以得到结点的有序序列。
9.在一个具有n个顶点的无向彻底图中，包含有    条边，在一个具有n个顶点的 有向彻底图中，包含有    条边。
10.快速排序算法在最差的情况卜其时间复杂度是    。
=.判断题（5X2分）
1.任意—•棵满二叉树一定也是彻底二叉树° （）
2.进栈操作时，必须判断栈是否己满。（）
3.—个程序的时间岌杂度是指该程序运行时间与问题规模的对应关系。（）
4.采用链式结构存储线性表时，其地址可以是不连续的。（）
5.折半查法的前提之一是线性表有序。（）
四.应用题（4X5分）
1.试比较顺序存储和链式存储的优缺点。（5分）
2.筒述栈和队列这两种数据结构的相同点和不同点0 （5分）
3,己知一棵二叉树的中序序列和后序序列分别是BDCEAFHG和DECBHGFA,试画出这 棵二叉树o （5分）
4.对于给定的一组关键码：83. 40, 63, 13, 84, 35,画岀用冒泡排序对上述序列进行操 作的各趟结果。（5分）
五.算法设计题（20分）
1.编写算法，将任意十进制数转换成其他进制.要求写出完整代码，可采用顺序栈或者链栈 实现o （12分）
2.编写一算法完成瑟夫生死者游戏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分。
1.集合线性结构 树型结构 图型结构
2.0 n
3.既可以方便的到后继结点又可以方便的到前驱结点。
4.先进先出
5.假溢岀
6.7
7.49
8.中
9.n（nT）/2 n（nT）
10.0 （n2） o
=.判断题（5X2分）
1.V； 2. X； 3. V； 4. V； 5. V
四.应用题（4X5分）
1.顺序存储查效率高，插入和删除效率低：链式存储插入和删除效率高，査效率低。
2.栈和队列都是操作受限的线性表。栈是先进后出，操作在一端进行；队列是先进先出, 插入在一端，删除在另一端进行。
3.
4.    83 40 63 13 84 35
13 83 40 63 35 84

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。