2018秋北理工《数据结构与算法》在线作业（100分）

hezuo001

(单选题) 1: 下面四种内排序方法中，要求容量最大的是()。
A: 插入排序
B: 选择排序
C: 快速排序
D: 归并排序




(单选题) 2: 下列说法正确的是()
A: 堆栈是在两端操作、先进后出的线性表
B: 堆栈是在一端操作、先进后出的线性表
C: 队列是在一端操作、先进先出的线性表
D: 队列是在两端操作、后进先出的线性表




(单选题) 3: 以下关于线性表的说法不正确的是()。
A: 线性表中的数据元素可以是数字、字符、记录等不同类型
B: 线性表中包含的数据元素个数不是任意的
C: 线性表中的每个结点都有且只有一个直接前趋和直接后继
D: 存在这样的线性表：表中各结点都没有直接前趋和直接后继




(单选题) 4: 下列排序中，某一趟结束后未必能选出一个元素放在其最终位置上的是()。
A: 直接插入排序
B: 冒泡排序
C: 快速排序
D: 堆排序




(单选题) 5: 判定一个队列Q(最多元素为m0)为满队列的条件是()
A: rear-front= = m0
B: rear-front-1= =m0
C: front= =rear
D: front= =rear+1




(单选题) 6: 设有一个长度为80的已排好序的表，用二分查找法进行查找，若查找不成功，至少比较()次。
A: 9
B: 8
C: 7
D: 6




(单选题) 7: 数据结构主要研究()。
A: 数据的逻辑结构
B: 数据的存储结构
C: 数据的逻辑结构和存储结构
D: 数据的逻辑结构、存储结构以及数据在操作上的实现




(单选题) 8: 设连通图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




(单选题) 9: 设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数数为()
A: 3
B: 4
C: 5
D: 1




(单选题) 10: 下列存储表示中,哪一个不是树的存储形式()。
A: 双亲表示法
B: 孩子链表表示法
C: 顺序存储表示法
D: 孩子兄弟表示法




(单选题) 11: 对哈希(HASH)函数H(k)= k MOD m, 一般来说，m应取()。
A: 素数
B: 很大的数
C: 偶数
D: 奇数




(单选题) 12: 在以下栈的基本运算中，不是加工型运算的是()
A: lnitStack(S)
B: Push(S,X)
C: Pop(S)
D: empty(S)




(单选题) 13: 数组的数据元素类型DataType可根据实际需要而定义。以下说法完全正确的是()
A: 数组的读运算可以读取一个数据元素整体,写运算只能修改一个数据元素的一部分
B: 数组的读、写运算可以读取或修改一个数据元素的一部分或一个整体
C: 数组的读、写运算只能读取或修改一个数据元素的一部分
D: 数组的读、写运算只能读取或修改一个数据元素整体




(单选题) 14: 用链接方式存储的队列，在进行插入运算时()。
A: 仅修改头指针
B: 头、尾指针都要修改
C: 仅修改尾指针
D: 头、尾指针可能都要修改




(单选题) 15: 下列说法哪个是不正确的()。
A: 快速排序属于不稳定排序。
B: 希尔排序属于不稳定排序。
C: 直接插入排序属于不稳定排序。
D: 堆排序属于不稳定排序。




(单选题) 16: 设有一个二维数A[m][n]，以行序为主序存储。假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，则A[4][5]在()位置，(10)表明用10进数表示。
A: 692(10)
B: 626(10)
C: 709(10)
D: 724(10)




(单选题) 17: 具有线性结构的数据结构是()
A: 赫夫曼树
B: 栈
C: 图
D: 树




(单选题) 18: 具有2000个结点的二叉树，其高度至少为()。
A: 9
B: 10
C: 11
D: 12




(单选题) 19: 长度为256的表,采用分块查找,每块最佳长度为()。
A: 14
B: 16
C: 18
D: 26




(单选题) 20: n 个顶点的连通图至少有()条边。
A: n-1
B: n
C: n+1
D: 0




(单选题) 21: 在数据结构中，与所使用的计算机无关的是数据的()结构
A: 逻辑
B: 存储
C: 逻辑和存储
D: 物理




(单选题) 22: 线性表的顺序存储结构是一种()的存储结构。
A: 随机存取
B: 顺序存取
C: 索引存取
D: 散列存取




(单选题) 23: 顺序表是线性表的()
A: 链式存储结构
B: 顺序存储结构
C: 索引存储结构
D: 散列存储结构




(单选题) 24: 我们在讨论某种数据结构时，主要讨论四个方面的问题，①数据的逻辑结构②数据的存储结构③在数据的逻辑结构上定义的数据的基本操作；④基本操作算法的具体实现；这四个问题的讨论的先后顺序应该是怎样的？()
A: ①②③④
B: ①③②④
C: ②①③④
D: ②①④③




(单选题) 25: 若某线性表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用哪一种存储结构算法的时间效率最高?()
A: 单链表
B: 给出表头指针的单循环链表
C: 双向链表
D: 给出表尾指针的双向循环链表




(单选题) 26: 一个具有767个结点的完全二叉树，其叶子结点个数为()。
A: 383
B: 384
C: 385
D: 386




(单选题) 27: 一个栈的入栈序列是abcde，则栈的不可能的输出序列是()。
A: edcba
B: decba
C: dceab
D: abcde




(单选题) 28: 从1000个元素中选出其中五个最大值元素()排序最适合。
A: 冒泡
B: 快速排序
C: 堆排序
D: 选择排序




(单选题) 29: 当待排序列基本有序时，下列排序方法中()最好。
A: 直接插入排序
B: 快速排序
C: 堆排序
D: 归并排序




(单选题) 30: 开放定址法中，增量序列的取法不包括()
A: 线性探测再散列
B: 委随机探测再散列
C: 二次探测再散列
D: 随机探测再散列




(单选题) 31: 栈的插入和删除操作在()进行。
A: 栈顶
B: 栈底
C: 任意位置
D: 指定位置




(单选题) 32: 下列排序方法中，排序趟数与序列的原始状态有关的方法是()。
A: 选择排序
B: 希尔排序
C: 堆排序
D: 冒泡排序




(单选题) 33: 从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为()排序法。
A: 插入
B: 选择
C: 交换
D: 二路归并




(单选题) 34: 稀疏矩阵一般的压缩存储方法有两种，即()。
A: 二维数组和三维数组
B: 三元组表和散列表
C: 三元组表和十字链表
D: 散列表和十字链表




(单选题) 35: 以二叉链表作为二叉树的存贮结构时，在具有n个结点的二叉链表中(n>0)，空指针域的个数为()。
A: 2n-1
B: n+1
C: n-1
D: 2n+1




(单选题) 36: 在一个长度为n的顺序线性表中顺序查找值为x的元素时，查找成功时的平均查找长度（即x与元素的平均比较次数，假定查找每个元素的概率都相等）为().
A: n
B: n/2
C: (n+1)/2
D: (n-1)/2




(单选题) 37: 在表达式求值算法中，需要用()个栈？
A: 0
B: 1
C: 2
D: 3




(单选题) 38: A算法的时间复杂度为O（n^3），B算法的时间复杂度为O（2n），则说明()。
A: 对于任何的数据量，A算法的时间开销都比B算法小
B: 随着问题规模n的增大，A算法比B算法有效
C: 随着问题规模n的增大，B算法比A算法有效
D: 对于任何数据量，B算法的时间开销都比A算法小




(单选题) 39: 某二叉树的前序和后序序列正好相同，则该二叉树一定是()的二叉树。
A: 空或只有一个结点
B: 高度等于其结点数
C: 任一结点无左孩子
D: 任一结点无右孩子




(单选题) 40: 若一个具有n个结点、k条边的非连通无向图是一个森林(n>k)，则该森林中必有()棵树。
A: k
B: n
C: n-k
D: n+k