17春北航《算法与数据结构》在线作业三标准答案

在线作业答案

北航《算法与数据结构》在线作业三
答案

一、单选题：
1.快速排序的记录移动次数（　   ）比较次数，其总执行时间为O(nlog2n)。          (满分:4)
    A. 大于
    B. 大于等于
    C. 小于等于
    D. 小于
2.对于顺序表的优缺点，以下说法错误的是          (满分:4)
    A. 无需为表示结点间的逻辑关系而增加额外的存储空间
    B. 可以方便地随机存取表中的任一结点
    C. 插入和删除运算较方便
    D. 由于顺序表要求占用连续的空间，存储分配只能预先进行(静态分配)
3.对一个由n个整数组成的序列，借助排序过程找出其中的最大值，希望比较次数和移动次数最少，应选用(    )方法。          (满分:4)
    A. 归并排序
    B. 直接插入排序
    C. 直接选择排序
    D. 快速排序。
4.一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是(    )。          (满分:4)
    A. edcba
    B. decba
    C. abcde
    D. dceab
5.一般地，一个存储结构包括以下三个主要部分。以下说法错误的是          (满分:4)
    A. 存储结点每个存储结点可以存放一个或一个以上的数据元素
    B. 数据元素之间关联方式的表示 也就是逻辑结构的机内表示
    C. 附加设施，如为便于运算实现而设置的“哑结点”等等
    D. 一种存储结构可以在两个级别上讨论。其一是机器级，其二是语言级
6.下列数据结构中，能用折半查找的是(    )。          (满分:4)
    A. 顺序存储的有序线性表
    B. 线性链表
    C. 二叉链表
    D. 有序线性链表
7.若从二叉树的任一节点出发到根的路径上所经过的节点序列按其关键字有序，则该二叉树是(    )。          (满分:4)
    A. 二叉排序树
    B. 哈夫曼树
    C. 堆
    D. AVL树
8.下列关于树说法正确的是          (满分:4)
    A. 树的先根遍历序列与其对应的二叉树的先根遍历序列相同
    B. 树的先根遍历序列与其对应的二叉树的后根遍历序列相同
    C. 树的后根遍历序列与其对应的二叉树的先根遍历序列相同
    D. 树的后根遍历序列与其对应的二叉树的后根遍历序列相同
9.深度为6的二叉树最多有(    )个结点          (满分:4)
    A. 64
    B. 63
    C. 32
    D. 31
10.判定一个顺序栈（最多元素为m个）为空的条件是(    )。          (满分:4)
    A. top＝＝0
    B. top＝＝m
    C. top!＝0
    D. top!＝m
11.如果从无向的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是(    )。          (满分:4)
    A. 完全图
    B. 连通图
    C. 有回路
    D. 一棵树
12.以下数据结构中不属于线性数据结构的是(    )。          (满分:4)
    A. 线性表
    B. 队列
    C. 二叉树
    D. 栈
13.具有2000个节点的二叉树，其高度至少为(    )。          (满分:4)
    A. 9
    B. 10
    C. 11
    D. 12
14.在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行(    )。          (满分:4)
    A. HL=p;p->next=HL;
    B. p->next=HL;HL=p;
    C. p->next=HL;p=HL;
    D. p->next=HL->next;HL->next=p;
15.设有50行60列的二维数组A[50][60]，其元素长度为4字节，按行优先顺序存储，基地址为200，则元素A[18][25]的存储地址为(    )。          (满分:4)
    A. 3700
    B. 4376
    C. 3900
    D. 4620
16.组成数据结构的基本单位是(    )。          (满分:4)
    A. 数据项
    B. 数据类型
    C. 数据元素
    D. 数据变量
17.采用分块查找时,若线性表中共有625个元素,查找每个元素的概率相同,假设采用顺序查找来确定结点所在的块时,每块应分(    )个结点最佳          (满分:4)
    A. 10
    B. 25
    C. 6
    D. 625
18.线性结构中的一个结点代表一个          (满分:4)
    A. 数据元素
    B. 数据项
    C. 数据
    D. 数据结构
19.如果以链表作为栈的存储结构，则退栈操作时(    )          (满分:4)
    A. 必须判别栈是否满
    B. 对栈不作任何判别
    C. 必须判别栈是否空
    D. 判别栈元素的类型
20.队列操作的原则是(    )。          (满分:4)
    A. 先进先出
    B. 后进先出
    C. 只能进行插入
    D. 只能进行删除
21.顺序表中逻辑上相邻的节点其物理位置也(    )。          (满分:4)
    A. 一定相邻
    B. 不必相邻
    C. 按某种规律排列
    D. 无要求
22.具有65个结点的完全二叉树其深度为(    )。          (满分:4)
    A. 8
    B. 7
    C. 6
    D. 5
23.有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100},当二分查找值为82的结点时,(    )次比较后查找成功。          (满分:4)
    A. 1
    B. 2
    C. 4
    D. 8
24.设有1000个元素，用二分法查找时，最大比较次数是(    )。          (满分:4)
    A. 1
    B. 7
    C. 10
    D. 25
25.排序方法中,从未排序序列中挑选元素并将其依次放入己排序序列(初始为空)的一端的方法,称为(    )          (满分:4)
    A. 希尔排序
    B. 归并排序
    C. 插入排序
    D. 选择排序
转载请注明易百网