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

hezuo001

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




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




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




(单选题) 4: 设有7000个无序的元素,希望用最快的速度挑选出其中前5个最大的元素,最好选用()法。
A: 冒泡排序
B: 快速排序
C: 堆排序
D: 基数排序




(单选题) 5: 根据二叉树的定义可知二叉树共有()种不同的形态。
A: 4
B: 5
C: 6
D: 7




(单选题) 6: 下述几种排序方法中，平均查找长度最小的是()。
A: 插入排序
B: 选择排序
C: 快速排序
D: 归并排序




(单选题) 7: 设数组Data[0..m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作的语句为()
A: front=front+1
B: front=(front+1)% m
C: rear=(rear+1)%m
D: front=(front+1)%(m+1)




(单选题) 8: 在一个具有n个顶点的无向图中,要连通全部顶点至少需要()边。
A: n
B: n+1
C: n-1
D: n/2




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




(单选题) 10: 由于数据的逻辑结构通过不同的存储映像方法可得到不同的存储结构，常见的数据存储结构没有()。
A: 邻接存储结构
B: 顺序存储结构
C: 索引存储结构
D: 散列存储结构




(单选题) 11: 有一个有序表为｛1，3，9，12，32，41，45，62，75，77，82，95，100｝，当采用折半查找值为82的节点时，()次比较后查找成功。
A: 1
B: 2
C: 4
D: 8




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




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




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




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




(单选题) 16: 线性表采用链式存储时，结点的存储地址()
A: 必须是不连续的
B: 连续与否均可
C: 必须是连续的
D: 和头结点的存储地址相连续




(单选题) 17: 3个结点的无向完全连通图至少有()条边。
A: 3
B: 4
C: 5
D: 6




(单选题) 18: 用线性链表存储线性表时，要求存储空间()
A: 必须是连续的
B: 连续不连续都可以
C: 部分元素的存储空间必须是连续的
D: 必须是不连续的




(单选题) 19: 设有50行60列的二维数组A[50][60]，其元素长度为4字节，按行优先顺序存储，基地址为200，则元素A[18][25]的存储地址为()。
A: 3700
B: 4376
C: 3900
D: 4620




(单选题) 20: 学习数据结构主要目的是()。
A: 处理数值计算问题
B: 研究程序设计技巧
C: 选取合适数据结构，写出更有效的算法
D: 是计算机硬件课程的基础




(多选题) 1: 下面关于哈希(Hash)查找的说法不正确的是（）
A: 哈希函数构造的越复杂越好，因为这样随机性好，冲突小
B: 除留余数法是所有哈希函数中最好的
C: 不存在特别好与坏的哈希函数，要视情况而定
D: 若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单的将该元素删去即可

,B,D


(多选题) 2: 下面几个符号串编码集合中，是前缀编码的是（）
A: {0,10,110,1111}
B: {11,10,001,101,0001}
C: {00,010,0110,1000}
D: {b,c,aa,ac,aba,abb,abc}

,C,D


(多选题) 3: 对于单链表表示法，以下说法正确的是（）
A: 指向链表的第一个结点的指针，称为头指针
B: 单链表的每一个结点都被一个指针所指
C: 任何结点只能通过指向它的指针才能引用
D: 尾指针变量具标识单链表的作用，故常用尾指针变量来命名单链表

,B,C


(多选题) 4: 下面关于串的的叙述中，正确的是（）
A: 串是字符的有限序列
B: 空串是由空格构成的串
C: 模式匹配是串的一种重要运算
D: 串既可以采用顺序存储，也可以采用链式存储

,C,D


(多选题) 5: 图的存储结构有（）
A: 邻接矩阵
B: 邻接表
C: 数组表示法
D: 十字链表

,B,C,D


(多选题) 6: 单链表表示法的基本思想是指针P表示结点间的逻辑关系，则以下说法正确的是（）
A: 任何指针都不能用打印语句输出一个指针型变量的值
B: 如果要引用(如访问)p所指结点，只需写出p(以后跟域名)即可
C: 若想修改变量p的值(比如让P指向另一个结点)，则应直接对p赋值
D: 对于一个指针型变量P的值。只需知道它指的是哪个结点

,C,D


(多选题) 7: 对于顺序表的优缺点，以下说法正确的是（）
A: 无需为表示结点间的逻辑关系而增加额外的存储空间
B: 可以方便地随机存取表中的任一结点
C: 插入和删除运算较方便
D: 由于顺序表要求占用连续的空间，存储分配只能预先进行(静态分配)

,B,D


(多选题) 8: 以下不稳定的排序方法是（）
A: 快速排序
B: 冒泡排序
C: 希尔排序
D: 堆排序

,C,D


(多选题) 9: 以下说法正确的是（）
A: 直接插入排序的空间复杂度为O(1)
B: 快速排序附加存储开销为O(log2n)
C: 堆排序的空间复杂度为O(n)
D: 二路归并排序的空间复杂度为O(n)

,B,D


(多选题) 10: 某堆栈的输入序列为a, b，c，d,下面的四个序列中，可能是它的输出序列的是（）
A: a，c，b，d
B: b, c，d，a
C: c, d，b, a
D: d, c，a，b

,B,C


(判断题) 1: 设一棵二叉树的先序序列和后序序列，则能够唯一确定出该二叉树的形状。
A: 错误
B: 正确




(判断题) 2: 线性表的逻辑顺序与物理顺序总是一致的。
A: 错误
B: 正确




(判断题) 3: 广义表中原子个数即为广义表的长度。
A: 错误
B: 正确




(判断题) 4: 做进栈运算时应先判别,栈是否为空。
A: 错误
B: 正确




(判断题) 5: 顺序存储方式只能用于存储线性结构。
A: 错误
B: 正确




(判断题) 6: 深度为6的二叉树最多有64个结点。
A: 错误
B: 正确




(判断题) 7: 二叉树是二叉排序树的充要条件是其任意非叶结点的值均大于其左孩子的值、小于其右孩子的值。
A: 错误
B: 正确




(判断题) 8: 空格也是合法字符，它可以出现在较长的字符串中，也可以单独出现 。
A: 错误
B: 正确




(判断题) 9: 在单链表中，要访问某个结点，只要知道该结点的指针即可；因此，单链表是一种随机存取结构。
A: 错误
B: 正确




(判断题) 10: 完全二叉树的某结点若没有左孩子，则它必是叶子结点。
A: 错误
B: 正确




(判断题) 11: 哈夫曼树又称为最优二叉树。
A: 错误
B: 正确




(判断题) 12: 一个循环链表可以由所给定的头指针或者尾指针惟一地确定。
A: 错误
B: 正确




(判断题) 13: 哈夫曼树是带权路径最短的树,路径上权值较大的结点离根较近。
A: 错误
B: 正确




(判断题) 14: 中序遍历二叉排序树可以得到一个有序的序列。
A: 错误
B: 正确




(判断题) 15: 算法必须具备的5个特征是：有穷性、确定性、可行性、有0或多个输入量，至少有1个输出量。
A: 错误
B: 正确




(判断题) 16: 快速排序是排序算法中平均性能最好的一种排序。
A: 错误
B: 正确




(判断题) 17: 用带表头结点的单链表表示队列，则判断队列为空的标准是头指针和尾指针均指向同一个结点。
A: 错误
B: 正确




(判断题) 18: 快速排序的速度在所有排序方法中为最快，而且所需附加空间也最少。
A: 错误
B: 正确




(判断题) 19: 任何一棵二叉树中至少有一个结点的度为2。
A: 错误
B: 正确




(判断题) 20: 队列和栈都是运算受限的线性表。
A: 错误
B: 正确