文档库

最新最全的文档下载
当前位置:文档库 > 对外经济贸易大学数据结构期末考试试卷(B卷)

对外经济贸易大学数据结构期末考试试卷(B卷)

对外经济贸易大学

数据结构期末考试试卷(B卷)

本试卷适用于:信息管理与信息系统专业

学号___________姓名___________

班级___________成绩___________

一、填空题(每小题1分,共20分)

1.线性结构中元素之间存在关系,树形结构中元素之间存在关系,图形结构中元素之间存在关系。

2.在线性结构中,第一个结点前驱结点,其余每个结点有且只有个前驱结点;最后一个结点后续结点,其余每个结点有且只有个后续结点。

3.在具有n个单元的循环队列中,队满时共有个元素

4.带有一个头结点的单链表head为空的条件是

5.在hq的链队列中,判定只有一个结点的条件是

6.对于一个具有n个结点的单链表,在已知p所指向结点后插入一个新结点的时间复杂度是在给定值为x的结点后插入一个新结点的时间复杂度是

7. 两个串相等的充分必要条件是且

8. 设s='I_AM_A_TEACHER', 其长度是

9.一棵二叉树的第I(I>=1)层最多有个结点;一棵有n(n>0)个结点的满二叉树共有个叶子和非终端结点

10.在无向图G的邻接矩阵A中,若A[i][j]等于1,则A[j][i]等于

11.已知一个图的邻接矩阵表示,删除所有从第I个结点出发的边方法是

二、选择题(每小题2分,共40分)

1.在数据结构中,从逻辑上可以把数据结构分成①。

A.动态结构和静态结构B.紧凑结构和非紧凑结构

C.线性结构和非线性结构D.内部结构和外部结构

2.线性表的顺序存储结构是一种①的存储结构,线性表的链式存储结构是一种②的存储结构。

A.随机存取B.顺序存取C.索引存取D.散列存取

3. 设有两个串p和q,求q在p中首次出现的位置的运算称作

A.连接 B 模式匹配 C 求子串 D 求串长

4.算法分析的两个主要方面是。

A.空间复杂性和时间复杂性

B.正确性和简明性

C.可读性和文档性

D.数据复杂性和程序复杂性

5.每种结构都具备三个基本运算:插入、删除和查找,这种说法①A.正确B.不正确

6.栈的特点是,队列的特点是。

A.先进先出B.先进后出

7.判定一个循环队列QU(最多元素为m0)为满队列的条件是。

A.QU.front== (QU.rear+1)%m0

B.QU.front!= (QU.rear+1)%m0

C.QU.front== QU.rear

D.QU.front!= QU.rear+1

8.不带头结点的单链表head为空的判定条件是

A.head=NULL

B.head - >next=NULL

C.head- >next=head

D.head!=NULL

9.在循环单链表p所指结点之后插入s所指结点的操作是

A.p →right=s; s→left=p;p→right→left=s;s→right=p→right;

B.p →right=s;p→right→left=s; s→left=p; s→right=p→right;

C.s→left=p; s→right=p→right; p →right=s; p→right→left=s;

D.s→left=p; s→right=p→right; p→right→left=s; p →right=s;

10.从一个具有n个结点的单链表中查找其值等于x结点时,在查找成功的情况下,需平均比较______个结点。

A.n B.n/2 C.(n—1)/2 D.(n+1)/2

11.二叉树的前序遍历序列中,任意一个结点均处在其子女结点的前面,这种说法

A 正确

B 错误

12.设高度为h的二叉树上只有度为0和度为2的结点,则此类二叉树中所包含的结点数至少为

A 2h

B 2h-1

C 2h+1

D h+1

13. 某二叉树的前序遍历结点访问顺序是abdgcefh,中序遍历的结点访问顺序是dgbaechf, 则其后序遍历的结点访问顺序是

A bdgcefha

B gdbecfha Cbdgaechf Dgdbehfca

14. 树最适合用来表示

A有序数据元素 B 无序数据元素 C 元素之间具有分支层次关系的数据

D 元素之间无联系的数据

15. 线索二叉树是一种_ 结构

A 逻辑

B 逻辑和存储

C 物理

D 线性

16.具有6个顶点的无向图至少应有条边才能确保是一个连通图

A.5 B.6 C.7 D.8

17.采用邻接表存储的图的广度优先遍历算法类似于二叉树的:

A.先序遍历B.中序遍历C.后序遍历D.按层遍历

18.判断一个有向图是否存在回路除了可以利用拓扑排序方法外,还可以利用:A.求关键路径的方法B.求最短路径的方法

C.广度优先遍历算法D.深度优先遍历算法

三、每小题5分,20分

1.

2.

3.

4.

四、写算法(20分):

1.删除顺序表中第i个元素的算法