《数据结构》19秋期末考

1、【奥鹏】 - 南开大学 数据结构 19 秋期末考核试卷总分 :100 得分 :100第 1 题 , 有 8 个结点的无向连通图最少有（）条边A 、 5B、 6C、 7D 、 8 正确答案 :C 第 2 题 , 链表是一种采用存储结构存储的线性表A 、 顺序B 、 链式C 、 星式D 、 网状正确答案 :B第 3 题 , 栈中元素的进出原则是（）A 、 先进先出B 、 后进先出C 、 栈空则进D 、 栈满则出正确答案 :B第 4 题 , 用邻接表表示图进行深度优先遍历时，通常是采用 （） 来实现算法的B、A、栈队列C、 树D、 图正确答案 :A第 5 题 ,链表适用于（） 查找A 、顺序B 、二

2、分法C 、顺序，也能二分法D 、随机正确答案 :A第 6 题 ,把一棵树转换为二叉树后，这棵二叉树的形态是（）A 、唯一的B 、有多种C 、有多种，但根结点都没有左孩子D 、有多种，但根结点都没有右孩子正确答案 :A第 7 题,向一个有127 个元素的顺序表中插入一个新元素并保持原来顺序不 变，平均要移动（）个元素A 、8B、 63.5C、 63D 、 7 正确答案 :B 第 8 题 ,引入二叉线索树的目的是（）A 、加快查找结点的前驱或后继的速度B 、为了能在二叉树中方便的进行插入与删除C 、为了能方便的找到双亲D 、使二叉树的遍历结果唯一正确答案 :A第 9 题 , 已知图的邻接矩阵，根据

3、算法，则从顶点 0 出发，按深度优先遍历 的结点序列是（）A 、 0 2 4 3 1 5 6B、 0 1 3 5 6 4 2C、 0 4 2 3 1 6 5D、 0 1 3 4 2 5 6 正确答案 :D第 10 题 ， 判定一个栈ST （最多元素为 mO ）为空的条件是（）A、 ST-top0B、 ST-top=0C、 ST-topm0D、 ST-top=m0正确答案 :B第 11 题 ,一个向量第一个元素的存储地址是100 ，每个元素的长度为2 ，则第5 个元素的地址是（）A 、 110B、 108C、 100D、 120正确答案 :B第 12 题 ,广度优先遍历类似于二叉树的 ()A 、

4、先序遍历B 、中序遍历C 、后序遍历D 、层次遍历正确答案 :D第 13 题,已知图的邻接矩阵，根据算法，则从顶点0 出发，按广度优先遍历 的结点序列是() A 、 0 2 4 3 6 5 1E、 0 1 3 6 4 2 5F、 0 4 2 3 1 5 6G、 0 1 3 4 2 5 6正确答案 :B第 14 题， 设 al、 a2、 a3 为 3个结点，整数P0, 3, 4 代表地址，则如下的链式存储结构称为 ()A、循环链表B、单链表C 、双向循环链表D 、双向链表正确答案 :B第 15 题 , 链接存储的存储结构所占存储空间 ()A 、 分 两部分，一部分存放结点值，另一部分存放表示结点

5、间关系的指针B 、 只 有一部分，存放结点值C 、只有一部分，存储表示结点间关系的指针D 、分两部分，一部分存放结点值，另一部分存放结点所占单元数正确答案 :A第16题，设串s仁ABCDEFGs2= ' PQRST 函数con(x,y)返回x和y串的连 接串，subs(s,i,j返回串s的从序号i开始的j个字符组成的子串，len(s)返回串s的长 度，则 con(subs(s1,2, len(s2), subs(s1, len(s2), 2 的)结果串是()H、 BCDEFI、 BCDEFGJ、 BCPQRSTK、 BCDEFEF正确答案:D第 17 题 , 任何一个无向连通图的最小生

6、成树()A 、只有一棵B 、一棵或多棵c、一定有多棵D 、可能不存在正确答案 :A第 18 题 , 串是一种特殊的线性表，其特殊性体现在()A 、 可 以顺序存储B 、 数据元素是一个字符C 、可以链式存储D 、数据元素可以是多个字符正确答案 :B第 19 题,判定一个队列QU （最多元素为mO ）为满队列的条件是（）L、 Q U-rear Q U-front = = m0B 、 Q U -rear Q U -front 1 = = mOC 、 QU-front = = QU-rearD 、QU-front = = QU-rear+1正确答案 :A第20题已知图的邻接表如下所示，根据算法，贝

7、S从顶点 0出发按深度优先 遍历的结点序列是（）A 、 0 1 3 2M、 0 2 3 1N、 0 3 2 1O、 0 1 2 3正确答案 :D第 21 题 ,下列关键字序列中， （）是堆A、 16,72,31,23,94,53B、 94,23,31,72,16,53C、 16,53,23,94 ， 31,72D、 16,23,53,31,94,72正确答案 :D第 22 题,折半查找有序表（ 4 ， 6， 10 ， 12 ， 20 ， 30 ， 50 ， 70 ， 88 ， 100） 若查找表中元素58 ，则它将依次与表中（） 比较大小，查找结果是失败。A、20,30, 5B0、，30 ,5

8、88,70, 0C、 20, 50D、 30 ,50正确答案：A第23题，深度优先遍历类似于二叉树的（）A、 先序遍历B、 中序遍历C、 后序遍历D、 层次遍历 正确答案:A第24题,已知图的邻接矩阵，根据算法，则从顶点0出发，按广度优先遍历 的结点序列是（）A、0 2 4 3 1 6 5B、 0 1 3 5 6 4 2C、 0 1 2 3 4 6 5D、0 1 2 3 4 5 6正确答案：C第25题，下述几种排序方法中，要求内存最大的是 （）A、 插入排序B、 快速排序C、 归并排序D、 选择排序正确答案 :C第 26 题 ,线性表在物理存储空间中也一定是连续的。A 、错误B 、正确正确答案

9、 :A第 27 题 ,队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。A 、错误B 、 正确 正确答案 :A第 28 题 ,线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。A 、错误B 、正确正确答案 :A第 29 题 ,栈和队列的存储方式既可是顺序方式，也可是链接方式。A 、错误B 、正确正确答案 :B第 30 题 ,二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字值，且小于其右非空子树（若存在的话）所有结点的关键字 值。错误A、正确B、正确答案:Ai 层上最第 31 题 ,对于一棵非空二叉树，它的根结点作为第一层，则它的第

10、多能有 2i 1 个结点。A 、 错误B 、 正确正确答案:A第 32 题 ,栈和链表是两种不同的数据结构。A、错误B、正确正确答案 :A第 33 题 ,顺序存储方式的优点是存储密度大，且插入、删除运算效率高。A 、错误B 、正确正确答案 :A第 34 题,具有 12 个结点的完全二叉树有 5 个度为 2 的结点。A 、错误B 、正确正确答案 :B第 35 题 ,线性表的逻辑顺序与存储顺序总是一致的。A 、 错误正确B、正确答案 :A第 36 题 ,链表的物理存储结构具有同链表一样的顺序。A 、错误B 、正确正确答案 :A第 37 题 ,二叉树中所有结点，如果不存在非空左子树，则不存在非空右子

11、 树。A、错误B、正确正确答案 :A第 38 题 ,二叉树中每个结点的两棵子树是有序的。A 、错误B 、正确正确答案 :B第 39 题 ,一个栈的输入序列是12345 ，则栈的输出序列不可能是12345 。A 、错误B 、正确正确答案 :A第 40 题 ,顺序存储方式只能用于存储线性结构。A 、错误B 、正确正确答案 :A第 41 题 ， 二叉树中所有结点个数是 2k-1-1 , 其中 k 是树的深度。错误A、B 、 正确正确答案 :A第 42 题,线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。A、错误B、正确正确答案 :A第 43 题 ,对于不同的使用者，一个表结构

12、既可以是栈，也可以是队列，也可以是线性表A 、错误B、正确正确答案 :B第 44 题 ,栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。A 、错误B 、正确正确答案 :B第 45 题 ,两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。A 、错误B 、正确正确答案 :B第 46 题,设一组初始记录关键字序列为 （ 45 ， 80 ， 48 ， 40 ， 22 ， 78 ） ，则分别 给出第 4 趟简单选择排序和第 4 趟直接插入排序后的结果。正确答案 （22 ， 40 ， 45 ， 48 ， 80 ， 78） ， （40 ， 45 ， 48 ， 80 ， 22 ， 78）第 47 题,设一组初始记录关键字集合为 （25， 10 ， 8， 27 ， 32 ， 68） ，散列表 的长度为 8，散列函数H （k） =k mod 7 ，要求分别用线性探测和链地址法作为解决