2019年北京建筑大学专升本数据结构考试真题

    诚为径教育网给同学们整理的2019年北京建筑大学专升本数据结构考试真题， 考生可先详细看一下，诚为径教育网在此预祝考生能取得优异成绩。

2019年北京建筑大学专升本数据结构考试真题

一、单项选择题，请选择最佳答案(每题2分，共40分)。

1、【 】是数据的最小单位。

A. 数据项 B.数据元素 C.结构 D.算法

2、数据结构是指数据以及它们之间的【 】。

A. 运算 B.关系 C.计算方法 D.存储

3、数据结构在计算机中的表示可以分为【 】。

A.动态结构和静态结构 B.顺序结构和链式结构

C.紧凑结构和非紧凑结构 D.内部结构和外部结构

4、算法分析的目的【 】。

A.找出数据结构的合理性 B.研究算法的输入输出关系

C.分析算法的效率以求改进 D.算法是否具有较好的可读性

5、线性表是具有n个【 】的有限序列

A.数据元素 B.字符 C.逻辑关系 D.数据项

6、在具有n个元素的顺序表中查找一个元素的时间复杂度是【 】。

A. O(1) B. O(n) C. O(n2) D. O(nlog2n)

7、带头结点的单链表L为空的判定条件是【 】。

A.L= =NULL B.L->next= =NULL

C.L->next=L D.L!=NULL

8、如果最常用的操作是取线性表中第i个元素及其前驱，则采用【 】存储方式最节省时间。

A.单链表 B.双向链表 C.循环链表 D.顺序表

9、递归程序执行时，要用到的数据结构是【 】。

A. 栈 B. 队列 C. 线性表 D. 数组

10、一个栈的入栈序列是1,2,3，下列不可能的出栈序列是【 】。

A.123 B.132 C.312 D.213

11、串的长度是指【 】。

A.串中所含非空格字符的个数 B.串中所含字符的个数

C.串中所含不同字符的个数 D. 串中所含不同字母的个数

12、稀疏矩阵用三元组表示的目的是【 】。

A. 便于进行矩阵运算 B. 便于输入和输出

C. 节省存储空间 D.降低运算的时间复杂度

13、图最合适用来表示【 】。

A.元素之间具有线性关系的数据 B.元素之间具有分支层次关系的数据

C.元素之间具有网状关系的数据 D.元素之间无联系的数据

14、二叉树第4层上至多有【 】结点。

A. 4 B.8 C.16 D.7

15、若有向图中的顶点能排成拓扑序列,则该有向图【 】。

A.是有向无环图 B.不存在回路

C.含有多个入度为0的顶点 D.是强连通图

16、如果从无向图中任一顶点出发进行一次深度优先搜索即可访问图中所有顶点,则该图一定是【 】。

A.完全图 B.连通图 C.有回路 D.一棵树

17、具有20个叶结点的二叉树中有【 】个度为2的结点，

A. 8 B. 19 C. 20 D. 2l

18、在一个无向图中，所有顶点的度数之和等于所有边数【 】倍。

A.1/2 B.2 C.1 D.4

19、具有6个顶点的无向图至少应有几条边才能确保是一个连通图【 】。

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

20、从有序表(14，20，34，58，69，72，87，96)中用二分查找法查找34时，其查找长度为【 】。

A. 2 B. 1 C. 3 D. 4

二、简答与运算题(44分)

1、设有下列用二元组表示的数据结构，画出它们的逻辑图形表示，并指出它属于哪种结构。(5分)

DS= (D，S)，其中：

D = { a,b,c,d,e,f,g}

S = { , ,,,,,}

2、学生成绩表中有100个学生信息，每个学生信息有学号、姓名、成绩，现在需要对学生成绩进行管理，分析这个问题中的数据、数据元素、数据项、数据结构及可能涉及的基本操作(答出三个即可)。(8分)

3、在下列单链表中，写出删除元素b的语句系列，设结点类型为Node，它含两个域：数据域data和指针域next。(5 分)

4、对下列二叉树，回答问题。(5分)

(1)该二叉树的深度为 ;

(2)该二叉树的度为 ;

(3)该二叉树的叶子节点个数为 ;

(4)该二叉树的中序遍历序列为 。

5、请根据给出的无向图，回答下列问题：(9分)

(1)该图的邻接矩阵表示：

(2)该图从节点1 出发的深度优先搜索序列;

(3)该图从节点1出发的广度优先搜索序列。

6、设有关键字{ 8, 15, 19, 10，27, 16, 11, 23 }，采用哈希法将它们填入到表长p=13的表中。要求：使用哈希函数H(key)=key % p ，解决冲突的方法采用线性探测再散列。(8分)

7、输入数据(28,15, 39, 10，27, 16, 11, 43, 12)，写出每一趟快速排序后的结果。(4分)

三、算法设计(16分)

假设用顺序表存储线性表中元素，顺序表定义如下：

typedef int ElemType;

typedef struct{

ElemType *elem; //数组指针表示存储空间基址

int length; //当前长度

int listsize; //当前分配的存储容量

}Sqlist;

在以上存储结构上设计算法：

(1)编写求顺序表L中最大值元素所在位置并用e返回其值的算法。

(2)假设顺序表L有序，编写算法，实现用折半查找法查找一个给定的元素key，找到则返回其在表中的下标，没有则返回-1。

以上就是2019年北京建筑大学专升本数据结构考试真题，同学们如果想要获得答案和进行测试评分的可在前往诚为径教育网专升本题库了解。

　　感谢您阅读2019年北京建筑大学专升本数据结构考试真题，本文出自：诚为径统招专升本网，转载需带上本文链接地址：https://tzzsb.cwjedu.com/lnzt/27655