北理工《数据结构与算法》在线作业 -0002 试卷总分:100 得分:0 一、 单选题 (共 40 道试题,共 100 分) 1.设连通图G中的边集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点
北理工《数据结构与算法》在线作业 -0002
试卷总分:100 得分:0
一、 单选题 (共 40 道试题,共 100 分)
1.设连通图G中的边集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发可以得到一种深度优先遍历的顶点序列为()
A.abedfc
B.acfebd
C.aebdfc
D.aedfcb
2.栈的插入和删除操作在()进行。
A.栈顶
B.栈底
C.任意位置
D.指定位置
3.某二叉树的前序和后序序列正好相同，则该二叉树一定是()的二叉树。
A.空或只有一个结点
B.高度等于其结点数
C.任一结点无左孩子
D.任一结点无右孩子
4.下列排序算法中，其中()是稳定的。
A.堆排序，冒泡排序
B.快速排序，堆排序
C.直接选择排序，希尔排序
D.归并排序，冒泡排序
5.对于经常要存取线性表任意指定位置元素的应用，线性表应采用()存储结构。
A.顺序存储结构
B.链式存储结构
C.线性链表
D.栈
6.快速排序属于那种排序类型()。
A.选择排序
B.插入排序
C.交换排序
D.基数排序
7.线性链表是通过()方式表示元素之间的关系
A.后继元素地址
B.元素的存储顺序
C.左、右孩子地址
D.元素的相对存储位置
8.关键路径是指AOE(Activity On Edge)网中()。
A.最长的回路
B.最短的回路
C.从源点到汇点(结束顶点)的最长路径
D.从源点到汇点(结束顶点)的最短路径
9.在有序表（3,8,13,15,16,17,21,24,45）中，用二分查找法查找关键字21，所需进行关键字比较的次数为()。
A.2
B.3
C.4
D.5
10.下列排序方法中效率最高的排序方法是()。
A.起泡排序
B.堆排序
C.快速排序
D.直接插入排序
11.已知A=(a,b), B=(A,A),那么GetHead(GetHead(GetTail(B)))=()。
A.(a)
B.A
C.a
D.(A)
12.图的存储结构不包括()
A.数组表示
B.邻接表
C.邻接多重表
D.孩子兄弟表示
13.()是HASH查找的冲突处理方法。
A.求余法
B.平方取中法
C.二分法
D.开放定址法
14.以下不稳定的排序方法是()
A.直接插入排序
B.冒泡排序
C.直接选择排序
D.二路归并排序
15.一棵高度（假定树根结点为第0层）为4的完全二叉树中的结点数最少为()。
A.15
B.16
C.17
D.31
16.用线性链表存储线性表时，要求存储空间()
A.必须是连续的
B.连续不连续都可以
C.部分元素的存储空间必须是连续的
D.必须是不连续的
17.评价排序算法好坏的标准主要是()。
A.执行时间
B.辅助空间
C.算法本身的复杂度
D.执行时间和所需的辅助空间
18.由于数据的逻辑结构通过不同的存储映像方法可得到不同的存储结构，常见的数据存储结构没有()。
A.邻接存储结构
B.顺序存储结构
C.索引存储结构
D.散列存储结构
19.具有 n 个顶点的有向完全图有()条弧。
A.n
B.n*(n-1)
C.n*(n+1)
D.n*n
20.根据二叉树的定义可知二叉树共有()种不同的形态。
A.4
B.5
C.6
D.7
21.在一棵具有5层的满二叉树中结点总数为()。
A.31
B.32
C.33
D.16
22.若一个具有n个结点、k条边的非连通无向图是一个森林(n>k)，则该森林中必有()棵树。
A.k
B.n
C.n-k
D.n+k
23.线性表的顺序存储结构是一种()的存储结构。
A.随机存取
B.顺序存取
C.索引存取
D.散列存取
24.中序遍历一棵二叉排序树所得到的结点序列是键值的()序列。
A.递增或递减
B.递减
C.递增
D.无序
25.在以下栈的基本运算中，不是加工型运算的是()
A.lnitStack(S)
B.Push(S,X)
C.Pop(S)
D.empty(S)
26.二分查找（又称折半查找）要求查找表中的记录按关键字()。
A.有序
B.无序
C.既可有序也可无序
27.若构造一棵具有n个结点的二叉排序树，最坏情况下，其深度不会超过()。
A.n/2
B.n
C.(n+1)/2
D.n+1
28.下列排序方法中，排序趟数与序列的原始状态有关的方法是()。
A.选择排序
B.希尔排序
C.堆排序
D.冒泡排序
29.我们在讨论某种数据结构时，主要讨论四个方面的问题，①数据的逻辑结构②数据的存储结构③在数据的逻辑结构上定义的数据的基本操作；④基本操作算法的具体实现；这四个问题的讨论的先后顺序应该是怎样的？()
A.①②③④
B.①③②④
C.②①③④
D.②①④③
30.线性表采用链式存储时，结点的存储地址()
A.必须是不连续的
B.连续与否均可
C.必须是连续的
D.和头结点的存储地址相连续
31.采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为()。
A.n
B.n/2
C.（n-1）/2
D.（n+1）/2
32.已知一栈的进栈序列为：1234，则下列序列中不可能的出栈序列是()。
A.1234
B.4321
C.2143
D.4123
33.学习数据结构主要目的是()。
A.处理数值计算问题
B.研究程序设计技巧
C.选取合适数据结构，写出更有效的算法
D.是计算机硬件课程的基础
34.若已知一棵二叉树先序序列为ABCDEFG，中序序列为CBDAEGF，则其后序序列为()。
A.CDBGFEA
B.CDBFGEA
C.CDBAGFE
D.BCDAGFE
35.栈与一般的线性表的区别在于()。
A.数据元素的类型不同
B.运算是否受限制
C.数据元素的个数不同
D.逻辑结构不同
36.下列不属于栈基本运算的是()。
A.入栈
B.删除栈底元素
C.判断栈是否为空
D.建立一个空栈
37.以下说法错误的是()
A.每个存储结点只能存放一个数据元素
B.数据元素之间的关联方式可由存储结点之间的关联方式直接表达
C.一种存储结构可以在两个级别上讨论。其一是机器级，其二是语言级
D.语言级描述可经编译自动转换成机器级 因此也可以看成是一种机内表示
38.在一个具有n个顶点的无向图中,要连通全部顶点至少需要()边。
A.n
B.n+1
C.n-1
D.n/2
39.队列的操作特点是()。
A.先进先出
B.后进先出
C.先进后出
D.只能从队尾出队
40.具有线性结构的数据结构是()
A.赫夫曼树
B.栈
C.图
D.树
