2022年春北航《算法与数据结构》在线作业试卷二 .pdf

15 春北航算法与数据结构在线作业试卷二一、单选题（共25 道试题，共100 分。 ）1. 若线性表最常用的操作是存取第i 个元素及其前趋的值，则采用（ ）存储方式节省时间。A. 单链表B. 双链表C. 单循环链表D. 顺序表正确答案： D 2. 除了( ) ，其它任何指针都不能在算法中作为常量出现，也无法显示。A. 头指针B. 尾指针C. 指针型变量D. 空指针正确答案： D 3. 栈的插入和删除操作在（）进行。A. 栈顶B. 栈底C. 任意位置D. 指定位置名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 8 页 - - - - - - - - - 正确答案： A 4. 采用分块查找时 ,若线性表中共有625 个元素 ,查找每个元素的概率相同 ,假设采用顺序查找来确定结点所在的块时,每块应分（）个结点最佳A. 10 B. 25 C. 6 D. 625 正确答案：5. 图的深度优先遍历类似于二叉树的（） 。A. 先序遍历B. 中序遍历C. 后序遍历D. 层次遍历正确答案：6. 计算机的算法是（） 。A. 计算方法B. 排序方法C. 对特定问题求解步骤的一种描述D. 调度算法正确答案：7. 以下四种排序方法中，要求附加的内存容量最大的是（）名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 8 页 - - - - - - - - - A. 插入排序B. 选择排序C. 快速排序D. 归并排序正确答案：8. 对于顺序表，以下说法错误的是（）A. 顺序表是用一维数组实现的线性表，数组的下标可以看成是元素的绝对地址B. 顺序表的所有存储结点按相应数据元素间的逻辑关系决定的次序依次排列C. 顺序表的特点是 :逻辑结构中相邻的结点在存储结构中仍相邻D. 顺序表的特点是 :逻辑上相邻的元素，存储在物理位置也相邻的单元中正确答案：9. 二叉树第 i 层上至多有（）结点。A. 2i B. 2 的 i 次方C. 2i-1 D. 2 的（i-1）次方正确答案：10. 深度为 6（根的层次为 1）的二叉树至多有（）结点。A. 64 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 8 页 - - - - - - - - - B. 32 C. 31 D. 63 正确答案：11. 假设一个有 n 个顶点和 e 条弧的有向图用邻接表表示,则删除与某个顶点 vi 相关的所有弧的时间复杂度是()。A. O(n) B. O(e) C. O(n+e) D. O(n*e) 正确答案：12. 从一棵 B_树删除元素的过程中，若最终引起树根结点的合并，则新树高度是（） 。A. 原树高度加 1 B. 原树高度减 1 C. 原树高度D. 不确定正确答案：13. 设数组 Data0.m作为循环队列 SQ的存储空间， front 为队头指针，rear为队尾指针，则执行出队操作的语句为（）A. front=front+1 B. front=(front+1)% m 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 8 页 - - - - - - - - - C. rear=(rear+1)%m D. front=(front+1)%(m+1) 正确答案：14. 数组 A 中，每个元素 A 的长度为 3 个字节，行下标 I 从 1 到 8,列下标 j 从 1 到 10，从首地址 SA 开始连续存放在存储器内，存放该数组至少需要的单元数为（） 。A. 80 B. 100 C. 240 D. 270 正确答案：15. 向堆中插入一个元素的时间复杂度为（） 。A. O(log2n) B. O(n) C. O(1) D. O(nlog2n) 正确答案：16. 设深度为 k 的二叉树上只有度为0 和度为 2 的节点，则这类二叉树上所含结点总数最少（）个A. k+1 B. 2k C. 2k-1 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 8 页 - - - - - - - - - D. 2k+1 正确答案：17. 下列数据组织形式中，（ ）的各个结点可以任意邻接。A. 集合B. 树形结构C. 线性结构D. 图状结构正确答案：18. 向一个有 127 个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（）个元素。A. 8 B. 63.5 C. 64 D. 7 正确答案：19. 以下说法正确的是( ) A. 因链栈本身没有容量限制,故在用户内存空间的范围内不会出现栈满情况B. 因顺序栈本身没有容量限制,故在用户内存空间的范围内不会出现栈满情况C. 对于链栈而言 ,在栈满状态下 ,如果此时再作进栈运算，则会发生“上溢”名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 8 页 - - - - - - - - - D. 对于顺序栈而言在栈满状态下如果此时再作迸栈运算，则会发生“下溢” 。正确答案：20. 在有 n 个叶子结点的哈夫曼树中，其结点总数为（） 。A. 不确定B. 2n C. 2n+1 D. 2n-1 正确答案：21. 若某线性表中最常用的操作是取第i 个元素和找第i 个元素的前趋元素，则采用（）存储方式最节省时间。A. 单链表B. 双链表C. 单向循环D. 顺序表正确答案：22. 一个队的入队序列是1，2，3，4 ，则队列的输出序列是（） 。A. 4，3，2，1 B. 1，2，3，4 C. 1，4，3，2 D. 3，2，1，4 正确答案：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 8 页 - - - - - - - - - 23. 有一个长度为12 的有序表 ,按二分查找法对该表进行查找,在表内各元素等概率情况下查找成功所需的平均比较次数为（）A. 35/12 B. 37/12 C. 39/12 D. 43/12 正确答案：24. 当初始序列已经按键值有序，用直接插入算法对其进行排序，需要循环的次数为（）A. n2 B. nlog2n C. log2n D. n-1 正确答案：25. 邻接表是图的一种（） 。A. 顺序存储结构B. 链式存储结构C. 索引存储结构D. 列存储结构正确答案：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 8 页 - - - - - - - - -