19春北理工《实用数据结构与算法》在线作业答案

www.vu8o.com

??------------------------------------------------------------------------------------------------------------------------------

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

(单选题)2: 中序遍历一棵二叉排序树所得到的结点序列是键值的()序列。 A: 递增或递减 B: 递减 C: 递增 D: 无序 正确答案:

(单选题)3: 在一棵具有5层的满二叉树中结点总数为()。 A: 31 B: 32 C: 33 D: 16

正确答案:

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

(单选题)5: 设数组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) 正确答案:

(单选题)6: 线性链表是通过()方式表示元素之间的关系 A: 后继元素地址 B: 元素的存储顺序 C: 左、右孩子地址 D: 元素的相对存储位置 正确答案:

(单选题)7: 对于经常要存取线性表任意指定位置元素的应用，线性表应采用()存储结构。 A: 顺序存储结构 B: 链式存储结构 C: 线性链表 D: 栈

正确答案:

(单选题)8: 如果结点a有三个兄弟，而且b为a的双亲，则b的度为()。 A: 3 B: 4 C: 5 D: 2

正确答案:

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

www.vu8o.com

??------------------------------------------------------------------------------------------------------------------------------

C: 3900 D: 4620 正确答案:

(单选题)10: 栈是一种()的数据结构。 A: 存取受限的线性结构 B: 存取不受限的线性结构 C: 存取受限的非线性结构 D: 存取不受限的非线性结构 正确答案:

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

(单选题)12: ()是HASH查找的冲突处理方法。 A: 求余法 B: 平方取中法 C: 二分法 D: 开放定址法 正确答案:

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

(单选题)14: 用链接方式存储的队列，在进行插入运算时()。 A: 仅修改头指针

B: 头、尾指针都要修改 C: 仅修改尾指针

D: 头、尾指针可能都要修改 正确答案:

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

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

正确答案:

(单选题)17: 具有65个结点的完全二叉树其深度为（根的层次号为1）()。 A: 8 B: 7 C: 6 D: 5

正确答案:

(单选题)18: 线性表若采用链表存储结构时，要求内存中可用存储单元的地址()。 A: 必须是连续的

www.vu8o.com

??------------------------------------------------------------------------------------------------------------------------------

B: 部分地址必须是连续的 C: 一定是不边疆的 D: 连续不连续都可以 正确答案:

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

(单选题)20: 顺序查找适合于存储结构为()的查找表。 A: 压缩存储 B: 散列存储 C: 索引存储

D: 顺序存储或链式存储 正确答案:

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

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

(多选题)23: 下面几个符号串编码集合中，是前缀编码的是（） A: {0,10,110,1111}

B: {11,10,001,101,0001} C: {00,010,0110,1000}

D: {b,c,aa,ac,aba,abb,abc} 正确答案:

(多选题)24: 下面关于串的的叙述中，正确的是（） A: 串是字符的有限序列 B: 空串是由空格构成的串

C: 模式匹配是串的一种重要运算

D: 串既可以采用顺序存储，也可以采用链式存储 正确答案:

(多选题)25: 下面关于线性表的叙述中，正确的是（） A: 线性表采用顺序存储，必须占用一片连续的存储单元 B: 线性表采用顺序存储，便于进行插入和删除操作 C: 线性表采用链接存储，不必占用一片连续的存储单元 D: 线性表采用链接存储，便于插入和删除操作。 正确答案:

(多选题)26: 在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形可能出现的是（） A: G中有弧<Vi，Vj> B: G中有一条从Vi到Vj的路径 C: G中没有<Vi,Vj>

D: G中有一条从Vj到Vi的路径 正确答案:

(多选题)27: 下面关于求关键路径的说法正确的是（）

www.vu8o.com

??------------------------------------------------------------------------------------------------------------------------------

A: 求关键路径是以拓扑排序为基础的

B: 一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同

C: 一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差 D: 关键活动一定位于关键路径上 正确答案:

(多选题)28: 对于顺序表的优缺点，以下说法正确的是（） A: 无需为表示结点间的逻辑关系而增加额外的存储空间 B: 可以方便地随机存取表中的任一结点 C: 插入和删除运算较方便

D: 由于顺序表要求占用连续的空间，存储分配只能预先进行(静态分配) 正确答案:

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

(多选题)30: 下列说法正确的是（）

A: 栈是限定在表尾进行插入或删除操作的线性表 B: 栈是限定在表头进行插入或删除操作的线性表 C: 对列是先进先出的线性表 D: 栈是后进先出的线性表 正确答案:

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

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

(判断题)33: 层次遍历初始堆可以得到一个有序的序列。 A: 错误 B: 正确 正确答案:

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

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

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

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

www.vu8o.com

??------------------------------------------------------------------------------------------------------------------------------

(判断题)38: 完全二叉树中，若一个结点没有左孩子，则它必是树叶。 A: 错误 B: 正确 正确答案:

(判断题)39: 空栈就是所有元素都为0的栈。 A: 错误 B: 正确 正确答案:

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

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

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

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

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

(判断题)45: 散列法存储的基本思想是由关键码的值决定数据的存储地址。 A: 错误 B: 正确 正确答案:

(判断题)46: 若有向图有n个顶点，则其强连通分量最多有n个。 A: 错误 B: 正确 正确答案:

(判断题)47: 顺序查找法适用于存储结构为顺序或链接存储的线性表。 A: 错误 B: 正确 正确答案:

(判断题)48: 若采用三元组存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算。 A: 错误 B: 正确 正确答案:

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

(判断题)50: 一个栈的输入序列是12345，则栈的输出序列可以是54312。 A: 错误 B: 正确 正确答案:

www.vu8o.com

??------------------------------------------------------------------------------------------------------------------------------

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

(单选题)2: 中序遍历一棵二叉排序树所得到的结点序列是键值的()序列。 A: 递增或递减 B: 递减 C: 递增 D: 无序 正确答案:

(单选题)3: 在一棵具有5层的满二叉树中结点总数为()。 A: 31 B: 32 C: 33 D: 16

正确答案:

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

(单选题)5: 设数组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) 正确答案:

(单选题)6: 线性链表是通过()方式表示元素之间的关系 A: 后继元素地址 B: 元素的存储顺序 C: 左、右孩子地址 D: 元素的相对存储位置 正确答案:

(单选题)7: 对于经常要存取线性表任意指定位置元素的应用，线性表应采用()存储结构。 A: 顺序存储结构 B: 链式存储结构 C: 线性链表 D: 栈

正确答案:

(单选题)8: 如果结点a有三个兄弟，而且b为a的双亲，则b的度为()。 A: 3 B: 4 C: 5 D: 2

正确答案:

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

www.vu8o.com

??------------------------------------------------------------------------------------------------------------------------------

C: 3900 D: 4620 正确答案:

(单选题)10: 栈是一种()的数据结构。 A: 存取受限的线性结构 B: 存取不受限的线性结构 C: 存取受限的非线性结构 D: 存取不受限的非线性结构 正确答案:

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

(单选题)12: ()是HASH查找的冲突处理方法。 A: 求余法 B: 平方取中法 C: 二分法 D: 开放定址法 正确答案:

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

(单选题)14: 用链接方式存储的队列，在进行插入运算时()。 A: 仅修改头指针

B: 头、尾指针都要修改 C: 仅修改尾指针

D: 头、尾指针可能都要修改 正确答案:

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

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

正确答案:

(单选题)17: 具有65个结点的完全二叉树其深度为（根的层次号为1）()。 A: 8 B: 7 C: 6 D: 5

正确答案:

(单选题)18: 线性表若采用链表存储结构时，要求内存中可用存储单元的地址()。 A: 必须是连续的

www.vu8o.com

??------------------------------------------------------------------------------------------------------------------------------

B: 部分地址必须是连续的 C: 一定是不边疆的 D: 连续不连续都可以 正确答案:

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

(单选题)20: 顺序查找适合于存储结构为()的查找表。 A: 压缩存储 B: 散列存储 C: 索引存储

D: 顺序存储或链式存储 正确答案:

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

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

(多选题)23: 下面几个符号串编码集合中，是前缀编码的是（） A: {0,10,110,1111}

B: {11,10,001,101,0001} C: {00,010,0110,1000}

D: {b,c,aa,ac,aba,abb,abc} 正确答案:

(多选题)24: 下面关于串的的叙述中，正确的是（） A: 串是字符的有限序列 B: 空串是由空格构成的串

C: 模式匹配是串的一种重要运算

D: 串既可以采用顺序存储，也可以采用链式存储 正确答案:

(多选题)25: 下面关于线性表的叙述中，正确的是（） A: 线性表采用顺序存储，必须占用一片连续的存储单元 B: 线性表采用顺序存储，便于进行插入和删除操作 C: 线性表采用链接存储，不必占用一片连续的存储单元 D: 线性表采用链接存储，便于插入和删除操作。 正确答案:

(多选题)26: 在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形可能出现的是（） A: G中有弧<Vi，Vj> B: G中有一条从Vi到Vj的路径 C: G中没有<Vi,Vj>

D: G中有一条从Vj到Vi的路径 正确答案:

(多选题)27: 下面关于求关键路径的说法正确的是（）

www.vu8o.com

??------------------------------------------------------------------------------------------------------------------------------

A: 求关键路径是以拓扑排序为基础的

B: 一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同

C: 一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差 D: 关键活动一定位于关键路径上 正确答案:

(多选题)28: 对于顺序表的优缺点，以下说法正确的是（） A: 无需为表示结点间的逻辑关系而增加额外的存储空间