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

.

********学院

学期期末试题——数据结构(C语言)

一．选择题（10×2分）：共10小题，请将答案填入题中的括号中，每小题只有一个正确答案，错选或不选均不给分。

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

Ａ．数据项 Ｂ．数据类型 C．数据元素 D．数据变量 2．下面程序段的时间复杂度为（ ）。 for(i=1;i<=n;i++) for(j=i;j<=n;j++) s++;

A．O(1) B．O(n) C．O(nlog2))

n

D．O(n2)

3．在一个长度为n的顺序存储线性表中，向第i个元素(1≤i≤n+1)之前插入一个新元素时，需向后移动（ ）个元素。

A．n-i B．n-i+1 C．n-i-1 D．i

4．设单链表中指针p指向结点A，若要删除A后的结点且该结点存在，则需要修改指针的操作为（ ）。

A．p->next=p->next->next B．p=p->next C．p=p->next->next D．p->next=p 5．若让元素1，2，3依次进栈，则出栈次序不可能出现（ ）种情况。

A、3，2，1 B、2，1，3 C、3，1，2 D、1，3，2

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

A、当前 B、后面 C、前一个 D、后一个

7．假定一个链队的队首和队尾指针分别为front和rear，则判断队空的条件是（ ）。

A、front==NULL B、front!=NULL C、rear!=NULL D、front==rear 8．二叉树第i(i≥1)层最多有（ ）个结点。

ii-1

A．2 B． 2

i

C．2i D．2 -1

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

Ａ．4 Ｂ．3 C．5 D．1

10．当待排序序列的关键码是随机分布时，下列哪种排序算法的平均时间复杂度最优（ ）。

A．直接插入排序 B．直接选择排序 C．快速排序 D．冒泡排序

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

.

.

1. 数据的逻辑结构被分为 、 、 和 四种。 2．在一个长度为n的顺序表中插入一个元素，最少需移动 个元素，最多需移动________个元素。

3．双向循环链表的优点是 4．队列的原则是 。

5．顺序存储的队列如果不采用循环方式，则会出现 问题。 6．具有64个结点的完全二叉树的深度为 。

7．设一颗完全二叉树共有50个叶子结点，则它共有________个度为2的结点。 8．二叉树采用_____序遍历可以得到结点的有序序列。

9．在一个具有n个顶点的无向完全图中，包含有 条边，在一个具有n个顶点的有向完全图中，包含有 条边。

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

三．判断题（5×2分）

1．任意一棵满二叉树一定也是完全二叉树。( ) 2．进栈操作时，必须判断栈是否已满。( )

3．一个程序的时间复杂度是指该程序运行时间与问题规模的对应关系。( ) 4．采用链式结构存储线性表时，其地址可以是不连续的。( ) 5．折半查找法的前提之一是线性表有序。( )

四．应用题（4×5分）

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

2． 简述栈和队列这两种数据结构的相同点和不同点。（5分）

3． 已知一棵二叉树的中序序列和后序序列分别是BDCEAFHG和DECBHGFA，试画出这棵二叉

树。（5分）

4． 对于给定的一组关键码：83，40，63，13，84，35，画出用冒泡排序对上述序列进行操

作的各趟结果。（5分）

.

.

五．算法设计题（20分）

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

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

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

.

.

答案及评分标准：

数据结构(C语言)答案及评分标准

一．选择题（10×2分）：每小题只有一个正确答案，错选或不选均不给分。 1 C

二．填空题（30分）：每空2分。 1．集合 线性结构 树型结构 图型结构 2．0 n

3．既可以方便的找到后继结点又可以方便的找到前驱结点。 4．先进先出 5．假溢出 6．7 7．49 8．中

9．n(n-1)/2 n(n-1) 10．O(n)。

三．判断题（5×2分）

1．√；2．×；3．√；4．√；5．√

四．应用题（4×5分）

1．顺序存储查找效率高，插入和删除效率低；链式存储插入和删除效率高，查找效率低。 2．栈和队列都是操作受限的线性表。栈是先进后出，操作在一端进行；队列是先进先出，插入在一端，删除在另一端进行。 3．

A B F 2

2 D 3 B 4 A 5 C 6 C 7 D 8 B 9 A 10 C C A D 4． 83 40 63 13 84 35

.

E H