数据结构试卷二_数据结构期末考试卷

《数据结构》第02章

《数据结构》第02章在线测试

数据结构试卷二_数据结构期末考试卷

数据结构试卷二_数据结构期末考试卷

数据结构试卷二_数据结构期末考试卷

剩余时间：

55:29

答题须知：1、本卷满分20分。

2、答完题后，请一定要单击下面的“交卷”按钮交卷，否则无法记录本试卷的成绩。

3、在交卷之前，不要刷新本网页，否则你的答题结果将会被清空。

题、单项选择题（每题1分，5道题共5分）

1、线性表的顺序存储结构是一种＿＿＿＿B＿＿＿＿的存储结构。

A、顺序存取

B、随机存取

C、索引存取

D、散列存取

2、单链表是一种＿＿＿＿＿A＿＿＿的存储结构。

A、顺序存取

B、随机存取

C、索引存取

D、散列存取

3、有头结点的单链表（head为头指针）是空表的条件是＿＿＿＿A＿＿＿

A、head-＞next＝＝NULL;

B、head＝＝NULL;

C、head-＞next＝＝head;

D、head-＞next-＞next＝＝ NULL;

4、非空的循环单链表(head为头指针)的尾结点（由指针p所指示）应满足＿＿＿＿＿＿C＿＿。

A、p-＞next＝＝NULL;

B、p＝＝NULL;

C、p-＞next＝＝head;

D、v

5、若在线性表的任何位置上删除元素的概率是相等的，那么在长度为n的顺序表中删除一个元素时需平均移动＿＿＿＿B＿＿＿＿个元素。

A、n

B、(n-1)/2

C、n/2

D、(n+1)/2

第二题、多项选择题（每题2分，5道题共10分）

1、在线性表的下列存储结构中，读取元素花费时间相同的是＿＿＿BCD＿＿＿＿＿。

A、顺序结构

B、单链表

C、双向链表

D、循环链表

2、顺序表的特点是＿＿＿＿ADFG＿＿＿＿。

A、随机存取

B、顺序存取

C、元素间的逻辑关系由指针指示

D、插入删除元素时需要移动表中元素

E、插入删除元素时不必移动元素，只须修改指针

F、数据元素在存储器内的物理位置顺序与它们的逻辑顺序一定相同

G、元素间的逻辑关系隐含在存储位置中

3、下列链表中，能从当前结点出发访问到表中其余各结点的有＿＿CDE＿＿＿＿＿＿。

A、带头结点的单链表

B、不带头结点的单链表

C、带头结点的循环链表

D、不带头结点的循环链表

E、双向链表

4、在双向循环链表中，若s是指向表中某结点的指针，则＿＿＿BC＿＿＿＿＿。

A、s-＞next＝＝s

B、s-＞next-＞prior＝＝s

C、s-＞prior-＞next ＝＝s

D、s-＞ prior＝＝s

5、在双向链表中，每个结点有两个指针域，分别指向＿＿＿BC＿＿＿＿＿。

A、其自身

B、其直接前驱结点

C、其直接后继结点

D、头结点

第三题、判断题（每题1分，5道题共5分）

1、在单链表中插入或删除元素时是以结点的指针变化来反映逻辑关系的变化，因此不需要移动元素。T

正确

错误

2、顺序表能够以元素在计算机内的物理位置的相邻性来表示线性表中元素之间的逻辑关系。T

正确

错误

3、在循环链表中设尾指针比设头指针方便。 （ T）

正确

错误

4、单链表的头结点表示的是线性表中的个元素。F

正确

错误

5、顺序表中插入或删除元素时是以元素的移动来反映逻辑关系的变化的。T

正确

错误

数据结构试题求解

大略看了下，错了请见谅。

-------------

一.判断题

1.（ ）带表头结点的双向循环链表判空的条件是：first->next==first(first为表头指针)。

错。给的条件能确定链表含1个单元，而非空。

2.（ ）一个有向图的邻接表和逆邻接表中的结点个数一定相等。

错。但是有向图的弧(指相邻点vi到vj的有向边)数等于邻接表(逆邻接表)个出边表结点(入边表结点)的数目。

3.（ ）一棵3阶B树是平衡的3路搜索树，反之，一棵平衡的3路搜索树是3阶B树。

错。

二.填空题

1. 下面程序段时间复杂度为________

for (int i=0;i

for (int j=0;j

S+=i;

O(nk)

2.数据结构的存储结构包括顺序，________，索引和散列四种。

链接

3.设森林T中有三棵树，，二，三棵树的结点个数分别为n1,n2,n3,将森林转换成二叉树后，其根结点的左子树上有________个结点。

n1-1。

森林转为二叉树之后，原棵树T1的根将成为二叉树Tn的根，其右子树的根为原来T2的根，左子树的数显然为原来T1的总结点数减去成为Tn根的原T1的根，即n1-1。

4.对二叉搜索树进行________遍历，可以得到按关键字从小到大排列的结点序列。

中序

三.选择题

1.已知单链表A长度为m，单链表B长度为n，若将B联接在A的末尾，其时间复杂度应为________。

A. O(1) B. O(m) C. O(n) D.O(m+n)

B。之前答错了……

已知单链表A，我们需要步进m次（即O(m)）以达到其尾，然后将该的next指向B，即可完成拼接。因此选B。

2.设有一个递归算法如下：

int fact(int n) { //n大于等于0

if(n<=0) return 1;

else return nfact(n-1);

}则计算fact(n)需要调用该函数的次数为________次。

A. n B. n+1 C. n+2 D.n-1

选B（取n=0，特殊情况）。

求解数据结构试题！！！

1，C

2，A 一退化的二叉树就是链表

3，B选项不全

4，插入排序

5，nn

6，n 第二个表的最小比个表的来的大

7，B 出队，front（4）=(front（3）+1)%6

入队rear(2)=(rear(0)+2)%6

8，2的H-1次方 BC中的一个 H-1层是满的 H层至少一个

9，A 图中任意一个顶点都是连通的，就是连通的，非连通图的极大连通子图叫连通分量

10，D

11，结构

12, 0 无向连通矩阵是对称的

13，O(elog2e)

14, n-1

15，C

希望可以提供参考

数据结构试题 求

1： 线性结构

树结构

图结构

2 ：顺序存储结构：把逻辑上相邻的存储在物理位置上相邻的存储单元中，结点之间的逻辑关系由存储单元的邻接关系来体现。

链式存储结构：在计算机中用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的).每个结点是由数据域和指针域组成。

3：栈是一种特殊的线性表。其特殊性在于限定仅在表尾进行插入或删除作。队列，其特殊性在于限定插入在线性表的一端进行，删除在线性表的另外一端进行。

以下是栈和队列的几个经典应用：

栈：“括号匹配”，“迷宫求解”，“进制转换”。

队列：“回文判断”，“排队取号”。

4：

5：先序：12，8，6，2，10，20，16，15

中序：2，6，8，10，12，15，16，20

后序：2，6，10，8，15，16，20，12

注：一题一步E的右子树是F

数据结构试题

本文出自

一、选择题

1、栈和队列的共同特点是( )。

参是：A

2、用链接方式存储的队列，在进行插入运算时( ).

参是：D

3、以下数据结构中哪一个是非线性结构？( )

参是：D

4、设有一个二维数组A[m][n]，设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？

A．688

参是：C

5、树最适合用来表示( )。

参是：C

6、二叉树的第k层的结点数最多为( ).

A. 2k-1

参是：D

7、若有18个元素的有序表存放在一维数组A[19]中，个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( )

参是：D

8、对n个记录的文件进行快速排序，所需要的辅助存储空间大致为（ ）

A. O（1）

参是：C

9、对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）= K %9作为散列函数，则散列地址为1的元素有（ ）个。

参是：D

10、设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。

参是：A

二、填空题

1、通常从四个方面评价算法的质量：_________、_________、_________和_________。

参是：

正确性 易读性 强壮性 高效率

2、一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为________。

参是：

O(n)

3、定一棵树的广义表表示为A（C，D（E，F，G），H（I，J）），则树中所含的结点数为_______个，树的深度为_______，树的度为_________。

参是：

9 3 3

4、后缀算式9 2 3 + - 10 2 / -的值为__________。中缀算式（3+4X）-2Y/3对应的后缀算式为_________________。

参是：

-1 3 4 X + 2 Y 3 / -

5、若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指针。在这种存储结构中，n个结点的二叉树共

参是：

2n n-1 n+1

6、对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点分别有_______个和________个。

参是：

e 2e

7、AOV网是一种_____________的图。

参是：

有向无回路

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

参是：

n(n-1)/2 n(n-1)

9、定一个线性表为(12,23,74,55,63,40)，若按Key % 4条件进行划分，使得同一余数的元素成为一个子表，则得到的四个子表分别为

参是：

（12，40） （ ） （74） （23,55，63）

10、向一棵B_树插入元素的过程中，若最终引起树根结点的分裂，则新树比原树的高度___________。

参是：

增加1

11、在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为________，整个堆排序过程的时间复杂度为________。

参是：

O(log2n) O(nlog2n)

12、在快速排序、堆排序、归并排序中，_________排序是稳定的。

参是：

归并