北航《算法与数据结构》在线作业三
一、单选题：
1.在一棵二叉树中，第4层上的结点数最多为(    )。          (满分:4)
    A. 8
    B. 15
    C. 16
    D. 31
    正确答案:A
2.非空的循环单链表head的尾节点（由p所指向）满足(    )。          (满分:4)
    A. p->next=NULL
    B. p=NULL
    C. p->next=head
    D. p=head
    正确答案:C
3.堆排序在最坏情况下，其时间复杂性为（    　）          (满分:4)
    A. O(nlog2n)
    B. O(n2)
    C. O(log2n2)
    D. O(log2n)
    正确答案:A
4.采用分块查时,若线性表中共有625个元素,查每个元素的概率相同,假设采用顺序查来确定结点所在的块时,每块应分(    )个结点最佳          (满分:4)
    A. 10
    B. 25
    C. 6
    D. 625
    正确答案:B
5.队列操作的原则是(    )。          (满分:4)
    A. 先进先出
    B. 后进先出
    C. 只能进行插入
    D. 只能进行删除
    正确答案:A
6.设字符串S1='ABCDEFG'，S2='PQRST'，则运算S=CONCAT（SUB（S1，2，LENGTH（S2）），SUB（S1，LENGTH（S2），2））后结果为(    )。          (满分:4)
    A. BCQR'
    B. 'BCDEF'
    C. 'BCDEFG'
    D. 'BCDEFEF'
    正确答案:D
7.算法的时间复杂度，都要以通过算法中执行频度最高的语句的执行次数来确定这种观点          (满分:4)
    A. 完全正确
    B. 完全错误
    C. 视情况而定
    D. 以上说法均不正确
    正确答案:B
8.在索引顺序表中查一个元素，可用的且最快的方法是（    ）          (满分:4)
    A. 用顺序查法确定元素所在块，再用顺序查法在相应块中查
    B. 用顺序查法确定元素所在块，再用二分查法在相应块中查
    C. 用二分查法确定元素所在块，再用顺序查法在相应块中查
    D. 用二分查法确定元素所在块，再用二分查法在相应块中查
    正确答案:C
9.对有n个记录的有序表采用二分查，其平均查长度的量级为（　）          (满分:4)
    A. O(log2n)
    B. O(nlog2n)
    C. O(n)
    D. O(n2)
    正确答案:A
10.以下说法正确的是 (    )          (满分:4)
    A. 因链栈本身没有容量限制
    故在用户内存空间的范围内不会出现栈满情况
    B. 因顺序栈本身没有容量限制
    故在用户内存空间的范围内不会出现栈满情况
    C. 对于链栈而言
    在栈满状态下
字符串长度排序
    如果此时再作进栈运算，则会发生“上溢”
    D. 对于顺序栈而言在栈满状态下如果此时再作迸栈运算，则会发生“下溢”。
    正确答案:A
11.设有两个串（S1和S2），求S1在S2中首次出现的位置的运算称为(    )。          (满分:4)
    A. 连接
    B. 模式匹配
    C. 求子串
    D. 求串长
    正确答案:B
12.设有向图有n个顶点和e条边，采用领接表作为其存储表示，在进行拓扑排序时，总的计算时间为(    )。          (满分:4)
    A. O（nloge）
    B. O（n+e）
    C. O(n*e)
    D. O(n的平方)
    正确答案:B
13.下列图的说法中正确的是(    ) 。          (满分:4)
    A. 一个具有 n 个顶点的无向完全图的边数为 n(n-1)
    B. 连通图的生成树是该图的一个极大连通子图
    C. 图的广度优先搜索是一个递归过程
    D. 在非连通图的遍历过程中，每调用一次深度优先搜索算法都得到该图的一个连通分量
    正确答案:C
14.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主的存储，a11为第一个元素，其存储地址为1，每个元素占1个地址空间，则a85的地址为(    )。          (满分:4)
    A. 13
    B. 18
    C. 33
    D. 40
    正确答案:C
15.下述几种排序方法中,平均查长度最小的是(    )          (满分:4)
    A. 插入排序
    B. 选择排序
    C. 快速排序
    D. 归并排序
    正确答案:C
16.以下说法错误的是(    )          (满分:4)
    A. 用数字式计算机解决问题的实质是对数据的加工处理
    B. 程序设计的实质是数据处理；数据的逻辑结构是数据的组织形式，基本运算规定了数据的基本操作方式
    C. 运算实现是完成运算功能的算法，或这些算法的设计
    D. 数据处理方式总是与数据某种相应的表示形式相联系，反之亦然
    正确答案:B
17.二叉树上叶结点数等于(    )。          (满分:4)
    A. 分支结点数加1
    B. 单分支结点数加1
    C. 双分支结点数加1
    D. 双分支结点数减1
    正确答案:C
18.顺序存储结构(    )          (满分:4)
    A. 仅适合于静态查表的存储
    B. 仅适合于动态查表的存储
    C. 既适合静态又适合动态查表的存储
    D. 既不适合静态又不适合动态查表的存储
    正确答案:C
19.邻接表是图的一种(    )。          (满分:4)
    A. 顺序存储结构
    B. 链式存储结构
    C. 索引存储结构
    D. 列存储结构
    正确答案:B
20.设无向图的顶点个数为n，则该图最多有(    )条边。          (满分:4)
    A. n-1
    B. n(n-1)/2
    C. n(n+1)/2
    D. 0
    正确答案:B
21.设有一个无向图G=（V，E）和G'=（V'，E'）如果G'为G的生成树，则下面不正确的说法是(    )          (满分:4)
    A. G'为G 的子图
    B. G'为G 的边通分量
    C. G'为G的极小连通子图且V'=V
    D. G'为G的一个无环子图
    正确答案:B
22.通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着          (满分:4)
    A. 数据元素具有同一特点
    B. 不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致
    C. 每个数据元素都一样
    D. 数据元素所包含的数据项的个数要相等
    正确答案:B
23.对于含有n个顶点e条边的无向连通图，利用Prim算法生成最小代价生成树其时间复杂度为(    )。          (满分:4)
    A. O(log2n)
    B. O(n2)
    C. O(ne)
    D. O(elog2e)
    正确答案:B
24.向顺序栈中压入新元素时，应当(    )。          (满分:4)
    A. 先移动栈顶指针，再存入元素
    B. 先存入元素，再移动栈顶指针
    C. 先后次序无关紧要
    D. 同时进行
    正确答案:A
25.设二叉树有n个结点，则其深度为          (满分:4)
    A. n-1
    B. n
    C. 5floor(log2n)
    D. 无法确定
    正确答案:D

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。