北航17秋《算法与数据结构》在线作业123
北航《算法与数据结构》在线作业一一、单选题:【25道,总分:100分】
1.顺序存储结构( ) (满分:4)
A. 仅适合于静态查找表的存储
B. 仅适合于动态查找表的存储
C. 既适合静态又适合动态查找表的存储
D. 既不适合静态又不适合动态查找表的存储
2.若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用（ ）存储方式最节省运算时间。 (满分:4)
A. 单链表
B. 双链表
C. 带头结点的双循环链表
D. 容量足够大的顺序表
3.从一棵B树删除元素的过程中，若最终引起树根结点的合并，则新树高度是( )。 (满分:4)
A. 原树高度加1
B. 原树高度减1
C. 原树高度
D. 不确定
4.任何一棵二叉树的叶结点在其先根、中根、后跟遍历序列中的相对位置 (满分:4)
A. 肯定发生变化
B. 有时发生变化
C. 肯定不发生变化
D. 无法确定
5.带头节点的单链表head 为空的判定条件( )。 (满分:4)
A. head=NULL
B. head->next=NULL
C. head->next=head
D. head!=head
6.采用二分查找方法查找长度为n的线性表时,每个元素的平均查找长度为( ) (满分:4)
A. O(n2)
B. O(log2n)
C. O(n)
D. O(log2n)
7.有 n 个顶点的无向图的邻接矩阵是用( )组存储。 (满分:4)
A. n 行 n 列
B. 一维
C. 任意行 n 列
D. n 行任意列
8.顺序表中逻辑上相邻的节点其物理位置也( )。 (满分:4)
A. 一定相邻
B. 不必相邻
C. 按某种规律排列
D. 无要求
9.设无向图的顶点个数为n，则该图最多有( )条边。 (满分:4)
A. n-1
B. n(n-1)/2
C. n(n+1)/2
D. 0
10.根据数据元素之间关系的不同特性，以下四类基本的逻辑结构反映了四类基本的数据组织形式。以下解释错误的是 数据组织形式。以下解释错误的是 (满分:4)
A. 集合中任何两个结点之间都有逻辑关系但组织形式松散
B. 线性结构中结点按逻辑关系依次排列形成一条"锁链"
C. 树形结构具有分支、层次特性，其形态有点像自然界中的树
D. 图状结构中的各个结点按逻辑关系互相缠绕，任何两个结点都可以邻接
11.对于顺序表的优缺点，以下说法错误的是 (满分:4)
A. 无需为表示结点间的逻辑关系而增加额外的存储空间
B. 可以方便地随机存取表中的任一结点
C. 插入和删除运算较方便
D. 由于顺序表要求占用连续的空间，存储分配只能预先进行(静态分配)
12.在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为( )。 (满分:4)
A. e
B. 2e
C. n的平方－e
D. n的平方－2e
13.某二叉树的先序序列和后序序列正好相反，则该二叉树一定是( )的二叉树。 (满分:4)
A. 空或只有一个结点高度等于其结点数
B. 任一结点无左孩子
C. 任一结点无右孩子
14.对顺序表上的插入、删除算法的时间复杂性分析来说，通常以( )为标准操作 (满分:4)
A. 条件判断
B. 结点移动
C. 算术表达式
D. 赋值语句
15.在以下栈的基本运算中，不是加工型运算的是( ). (满分:4)
A. lnitStack(S)
B. Push(S,X)
C. Pop(S)
D. empty(S)
16.3个结点可构成（ ）个不同形态的二叉树。 (满分:4)
A. 2
B. 3
C. 4
D. 5
17.设二叉树有n个结点，则其深度为 (满分:4)
A. n-1
B. n
C. 5floor(log2n)
D. 无法确定
18.串是任意有限个( ) (满分:4)
A. 符号构成的序列
B. 符号构成的集合
C. 字符构成的序列
D. 字符构成的集合
19.顺序表是线性表的 (满分:4)
A. 链式存储结构
B. 顺序存储结构
C. 索引存储结构
D. 散列存储结构
20.以下二叉树说法错误的是 (满分:4)
A. 完全二叉树上结点之间的父子关系可由它们编号之间的关系来表达
B. 在三叉链表上，二叉树的求双亲运算很容易实现
C. 在二叉链表上，求根，求左、右孩子等很容易实现
D. 在二叉链表上，求双亲运算的时间性能很好
21.向堆中插入一个元素的时间复杂度为( )。 (满分:4)
A. O(log2n)
B. O(n)
C. O(1)
D. O(nlog2n)
22.若从二叉树的任一节点出发到根的路径上所经过的节点序列按其关键字有序，则该二叉树是( )。 (满分:4)
A. 二叉排序树
B. 哈夫曼树
C. 堆
D. AVL树
23.如下叙述中正确的是( )。 (满分:4)
A. 串是一种特殊的线性表
B. 串的长度必须大于零
C. 串中元素只能是字母
D. 空串就是空白串
24.关于逻辑结构，以下说法错误的是 (满分:4)
A. 逻辑结构与数据元素本身的形成、内容无关
B. 逻辑结构与数据元素的相对位置有关
C. 逻辑结构与所含结点个数无关
D. 一些表面上很不相同的数据可以有相同的逻辑结构
25.下列图的说法中正确的是( ) 。 (满分:4)
A. 一个具有 n 个顶点的无向完全图的边数为 n(n-1)
B. 连通图的生成树是该图的一个极大连通子图
C. 图的广度优先搜索是一个递归过程
D. 在非连通图的遍历过程中，每调用一次深度优先搜索算法都得到该图的一个连通分量
北航《算法与数据结构》在线作业三
一、单选题:【25道,总分:100分】
1.指针的全部作用就是 (满分:4)
A. 指向某常量
B. 指向某变量
C. 指向某结点
D. 存储某数据
2.下列关于树说法正确的是 (满分:4)
A. 树的先根遍历序列与其对应的二叉树的先根遍历序列相同
B. 树的先根遍历序列与其对应的二叉树的后根遍历序列相同
C. 树的后根遍历序列与其对应的二叉树的先根遍历序列相同
D. 树的后根遍历序列与其对应的二叉树的后根遍历序列相同
3.以下关于树的说法错误的是 (满分:4)
A. 树形结构的特点是一个结点可以有多个直接前趋
B. 线性结构中的一个结点至多只有一个直接后继
C. 树形结构可以表达(组织)更复杂的数据
D. 树(及一切树形结构)是一种"分支层次"结构
4.以下说法错误的是( ) (满分:4)
A. 线性表的元素可以是各种各样的，逻辑上相邻的元素在物理位置上不一定相邻
B. 在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上不一定相邻
C. 在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻
D. 线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素
5.Substr('DATA STRUCTURE'，5，9)=( )。 (满分:4)
A. STRUCTURE'
B. 'ASTUCTUR'
C. 'DATA STRUCTRUE'
6.如果结点A有3个兄弟，而且B为A的双亲，则B的度为( )。 (满分:4)
A. 1
B. 3
C. 4
D. 5
7.一个加权的无向连通图的最小生成树( )。 (满分:4)
A. 有一棵或多棵
B. 只有一棵
C. 一定有多棵
D. 可能不存在
8.设无向图的顶点个数为n，则该图最多有( )条边。 (满分:4)
A. n-1
B. n(n-1)/2
C. n(n+1)/2
D. 0
9.数组A中，每个元素A的长度为3个字节，行下标I 从1到8,列下标j从1到10，从首地址SA开始连续存放在存储器内，存放该数组至少需要的单元数为( )。 (满分:4)
A. 80
B. 100
C. 240
D. 270
10.通常从正确性、易读性、健壮性、高效性等四个方面评价算法(包括程序)的质量。以下解释错误的是 (满分:4)
A. 正确性 算法应能正确地实现预定的功能(即处理要求)
B. 易读性 算法应易于阅读和理解 以便于调试 修改和扩充
C. 健壮性 当环境发生变化时，算法能适当地做出反应或进行处理，不会产生不需要的运行结果
D. 高效性 即达到所需要的时间性能
11.对于顺序表的优缺点，以下说法错误的是 (满分:4)
A. 无需为表示结点间的逻辑关系而增加额外的存储空间
B. 可以方便地随机存取表中的任一结点
C. 插入和删除运算较方便
D. 由于顺序表要求占用连续的空间，存储分配只能预先进行(静态分配)
12.从一棵B树删除元素的过程中，若最终引起树根结点的合并，则新树高度是( )。 (满分:4)
A. 原树高度加1
B. 原树高度减1
C. 原树高度
D. 不确定
13.设有50行60列的二维数组A，其元素长度为4字节，按行优先顺序存储，基地址为200，则元素A的存储地址为( )。 (满分:4)
A. 3700
B. 4376
C. 3900
D. 4620
14.以下二叉树说法错误的是 (满分:4)
A. 完全二叉树上结点之间的父子关系可由它们编号之间的关系来表达
B. 在三叉链表上，二叉树的求双亲运算很容易实现
C. 在二叉链表上，求根，求左、右孩子等很容易实现
D. 在二叉链表上，求双亲运算的时间性能很好
15.线性表是一个具有n个( )的有限序列。 (满分:4)
A. 表元素
B. 字符
C. 数据元素
D. 数据项
16.下列数据结构中，能用折半查找的是( )。 (满分:4)
A. 顺序存储的有序线性表
B. 线性链表
C. 二叉链表
D. 有序线性链表
17.深度为6（根的层次为1）的二叉树至多有( )结点。 (满分:4)
A. 64
B. 32
C. 31
D. 63
18.以下说法正确的是( ) (满分:4)
A. 顺序存储方式的优点是存储密度大、且插入、删除运算效率高
B. 链表的每个结点中都恰好包含一个指针
C. 线性表的顺序存储结构优于链式存储结构
D. 顺序存储结构属于静态结构，链式结构属于动态结构
19.若某线性表中最常用的操作是取第I个元素和找第I个元素的前趋元素，则采用( )存储方式最节省时间。 (满分:4)
A. 顺序表
B. 单链表
C. 双链表
D. 单循环链表
20.向堆中插入一个元素的时间复杂度为( )。 (满分:4)
A. O(log2n)
B. O(n)
C. O(1)
D. O(nlog2n)
21.快速排序的记录移动次数（ ）比较次数，其总执行时间为O(nlog2n)。 (满分:4)
A. 大于
B. 大于等于
C. 小于等于
D. 小于
22.线性链表不具有的特点是( )。 (满分:4)
A. 随机访问
B. 不必事先估计所需存储空间大小
C. 插入与删除时不必移动元素
D. 所需空间与线性表长度成正比
23.二叉树第i层上至多有( )结点。 (满分:4)
A. 2i
B. 2的i次方
C. 2i-1
D. 2 的（i-1）次方
24.向二叉排序树中插入一个元素时，其时间复杂度大致为( )。 (满分:4)
A. O(log2n(其中2是底数))
B. O(n)
C. O(1)
D. O(n*log2n(其中2是底数))
25.判定一个顺序栈（最多元素为m个）为空的条件是( )。 (满分:4)
A. top＝＝0
B. top＝＝m
C. top!＝0
D. top!＝m
北航《算法与数据结构》在线作业二
一、单选题:【25道,总分:100分】
1.带头节点的单链表head 为空的判定条件( )。 (满分:4)
A. head=NULL
B. head->next=NULL
C. head->next=head
D. head!=head
2.深度为6（根的层次为1）的二叉树至多有( )结点。 (满分:4)
A. 64
B. 32
C. 31
D. 63
3.非空的循环单链表head的尾节点（由p所指向）满足( )。 (满分:4)
A. p->next=NULL
B. p=NULL
C. p->next=head
D. p=head
4.在一个具有n个顶点的无向图中，要连通所有顶点则至少需要( )条边。 (满分:4)
A. n
B. 2n
C. n-1
D. n+1
5.在索引顺序表中查找一个元素，可用的且最快的方法是（ ） (满分:4)
A. 用顺序查找法确定元素所在块，再用顺序查找法在相应块中查找
B. 用顺序查找法确定元素所在块，再用二分查找法在相应块中查找
C. 用二分查找法确定元素所在块，再用顺序查找法在相应块中查找
D. 用二分查找法确定元素所在块，再用二分查找法在相应块中查找
6.以下说法错误的是( ) (满分:4)
A. 线性表的元素可以是各种各样的，逻辑上相邻的元素在物理位置上不一定相邻
B. 在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上不一定相邻
C. 在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻
D. 线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素
7.关于有向图的邻接表和逆邻接表表示法，下列结论正确的是 ( )。 (满分:4)
A. 用邻接表表示法计算入度比较方便
B. 用邻接表表示法计算入度和出度都方便
C. 用逆邻接表表示法计算入度和出度都不方便
D. 用逆邻接表表示法计算入度比计算出度方便
8.单链表表示法的基本思想是指针P表示结点间的逻辑关系，则以下说法错误的是 (满分:4)
A. 任何指针都不能用打印语句输出一个指针型变量的值
B. 如果要引用(如访问)p所指结点，只需写出p(以后跟域名)即可
C. 若想修改变量p的值(比如让P指向另一个结点)，则应直接对p赋值
D. 对于一个指针型变量P的值。只需知道它指的是哪个结点
9.栈的插入和删除操作在( )进行。 (满分:4)
A. 栈顶
B. 栈底
C. 任意位置
D. 指定位置
10.假设一个有n个顶点和e条弧的有向图用邻接表表示,则删除与某个顶点vi相关的所有弧的时间复杂度是( )。 (满分:4)
A. O(n)
B. O(e)
C. O(n+e)
D. O(n*e)
11.如果以链表作为栈的存储结构，则退栈操作时( ) (满分:4)
A. 必须判别栈是否满
B. 对栈不作任何判别
C. 必须判别栈是否空
D. 判别栈元素的类型
12.以下关于数据的存储结构的叙述哪一条是正确的( )。 (满分:4)
A. 数据的存储结构是数据间关系的抽象描述
B. 数据的存储结构是逻辑结构在计算机存储器中的实现
C. 数据的存储结构分为线性结构和非线性结构
D. 数据的存储结构对数据运算的具体实现没有影响
13.线索化二叉树中某结点D，没有左孩子的主要条件是( )。 (满分:4)
A. D->Lchild=Null
B. D->ltag=1
C. D->Rchild=Null
D. D->ltag=0
14.设有一个无向图G=（V，E）和G'=（V'，E'）如果G'为G的生成树，则下面不正确的说法是( ) (满分:4)
A. G'为G 的子图
B. G'为G 的边通分量
C. G'为G的极小连通子图且V'=V
D. G'为G的一个无环子图
15.若某线性表中最常用的操作是取第I个元素和找第I个元素的前趋元素，则采用( )存储方式最节省时间。 (满分:4)
A. 顺序表
B. 单链表
C. 双链表
D. 单循环链表
16.一个加权的无向连通图的最小生成树( )。 (满分:4)
A. 有一棵或多棵
B. 只有一棵
C. 一定有多棵
D. 可能不存在
17.在一个图中，所有顶点的度数之和等于所有边数的( )倍。 (满分:4)
A. 1
B. 2
C. 3
D. 4
18.二叉树上叶结点数等于( )。 (满分:4)
A. 分支结点数加1
B. 单分支结点数加1
C. 双分支结点数加1
D. 双分支结点数减1
19.设有1000个无序的元素,希望用最快的速度挑选出其中前10个最大的元素,最好( )排序法。 (满分:4)
A. 起泡排序
B. 快速排序
C. 堆排序
D. 基数排序
20.顺序查找法适合于存储结构为( )的线性表。 (满分:4)
A. 散列表
B. 顺序存储或链接存储
C. 压缩存储
D. 索引存储
21.下列那种排序需要的附加存储开销最大( )。 (满分:4)
A. 快速排序
B. 堆排序
C. 归并排序
D. 插入排序
22.对n个记录的文件进行堆排序，最坏情况下的执行时间为( )。 (满分:4)
A. O(log2n)
B. O(nlogn)
C. O(n)
D. O(n的平方)
23.Substring('DATA STRUCTURE'，5，9)=( )。 (满分:4)
A. 'STRUCTURE'
B. 'ASTUCTUR'
C. 'DATA STRUCTRUE'
D. 'DATA'
24.n个顶点的连通图至少有( )条边。 (满分:4)
A. n-1
B. n
C. n+1
D. 0
25.Substr('DATA STRUCTURE'，5，9)=( )。 (满分:4)
A. STRUCTURE'
B. 'ASTUCTUR'
C. 'DATA STRUCTRUE'
页:
[1]