北航《算法与数据结构》在线作业一二三答案-15春

奥鹏作业答案

北航《算法与数据结构》在线作业一
试卷总分：100       测试时间：--
单选题  


一、单选题（共 25 道试题，共 100 分。）V 1.  排序方法中,从未排序序列中依次取出元素与己排序序列(初始时为空)中的元素进行比较,将其放入己排序序列的正确位置上的方法,称为（）
A. 希尔排序
B. 起泡排序
C. 插入排序
D. 选择排序
      满分：4  分
2.  设有1000个无序的元素,希望用最快的速度挑选出其中前10个最大的元素,最好（）排序法。
A. 起泡排序
B. 快速排序
C. 堆排序
D. 基数排序
      满分：4  分
3.  以下说法正确的是 ( )
A. 因链栈本身没有容量限制,故在用户内存空间的范围内不会出现栈满情况
B. 因顺序栈本身没有容量限制,故在用户内存空间的范围内不会出现栈满情况
C. 对于链栈而言,在栈满状态下,如果此时再作进栈运算，则会发生“上溢”
D. 对于顺序栈而言在栈满状态下如果此时再作迸栈运算，则会发生“下溢”。
      满分：4  分
4.  对于数据结构课程的主要内容，以下解释正确的是
A. 数据结构的定义，包括逻辑结构、存储结构和基本运算集
B. 数据结构的实现，包括存储实现、运算实现和基本运算集
C. 数据结构的评价和选择，包括逻辑结构的选择、基本运算集的选择和存储选择
D. 以上说法均不正确
      满分：4  分
5.  堆是一个键值序列{k1,k2,…, kn},对i=1,2,…,|_n/2_|,满足( )
A. ki≤k2i≤k2i+1
B. ki<k2i+1<k2i
C. ki≤k2i且ki≤k2i+1(2i+1≤n)
D. ki≤k2i 或ki≤k2i+1(2i+1≤n)
      满分：4  分
6.  某二叉树结点的前序序列为E、A、C、B、D、G、F，中序遍历为A、B、C、D、E、F、G。 该二叉树结点的后序序列为 ( )。
A. B,D,C,A,F,G,E
B. B,D,C,F,A,G,E
C. E,G,F,A,C,D,B
D. E,G,A,C,D,F,B
      满分：4  分
7.  向堆中插入一个元素的时间复杂度为（ ）。
A. O(log2n)
B. O(n)
C. O(1)
D. O(nlog2n)
      满分：4  分
8.  将含有83个结点的完全二叉树从根结点开始编号，根为1号，后面按从上到下、从左到右的顺序对结点编号，那么编号为41的双结点编号为
A. 42
B. 40
C. 21
D. 20
      满分：4  分
9.  n个顶点的连通图至少有（ ）条边。
A. n-1
B. n
C. n+1
D. 0
      满分：4  分
10.  顺序表中逻辑上相邻的节点其物理位置也（ ）。
A. 一定相邻
B. 不必相邻
C. 按某种规律排列
D. 无要求
      满分：4  分
11.  在一个具有n个顶点的无向图中，要连通所有顶点则至少需要（ ）条边。
A. n
B. 2n
C. n-1
D. n+1
      满分：4  分
12.  根据操作的效果，可将运算分成加工型运算、引用型运算两种基本类型。对于表格处理中的五种功能以下解释错误的是
A. 查找引用型运算，功能是找出满足某种条件的结点在s(线形结构)中的位置
B. 读取引用型运算 功能是读出s(线形结构)中某指定位置结点的内容
C. 插入引用型运算，功能是在s(线形结构)的某指定位置上增加一个新结点
D. 删除加工型运算，功能是撤消s(线形结构)某指定位置上的结点
      满分：4  分
13.  具有65个结点的完全二叉树的高度为（ ）。（根的层次号为0）
A. 8
B. 7
C. 6
D. 5
      满分：4  分
14.  如果一个树中，结点A有3个兄弟，而且B为A的双亲，则B的度为（ ）。
A. 1
B. 3
C. 4
D. 5
      满分：4  分
15.  堆排序在最坏情况下，其时间复杂性为（ 　）
A. O(nlog2n)
B. O(n2)
C. O(log2n2)
D. O(log2n)
      满分：4  分
16.  采用分块查找时,若线性表中共有625个元素,查找每个元素的概率相同,假设采用顺序查找来确定结点所在的块时,每块应分（）个结点最佳
A. 10
B. 25
C. 6
D. 625
      满分：4  分
17.  一组记录的排序码为(46,79,56,38,40,84),则利用堆排序的方法建立的初始堆为（ ）。
A. 79,46,56,38,40,80
B. 84,79,46,38,40,56
C. 84,79,56,46,40,38
D. 84,56,79,40,46,38
      满分：4  分
18.  一个具有n个顶点的无向完全图的边数为（　 ）
A. n(n+1)/2
B. n(n-1)/2
C. n(n-1)
D. n(n+1)
      满分：4  分
19.  以下时间复杂性不是O(n2)的排序方法是
A. 直接插入排序
B. 二路归并排序
C. 冒泡排序
D. 直接选择排序
      满分：4  分
20.  单链表表示法的基本思想是指针P表示结点间的逻辑关系，则以下说法错误的是
A. 任何指针都不能用打印语句输出一个指针型变量的值
B. 如果要引用(如访问)p所指结点，只需写出p(以后跟域名)即可
C. 若想修改变量p的值(比如让P指向另一个结点)，则应直接对p赋值
D. 对于一个指针型变量P的值。只需知道它指的是哪个结点
      满分：4  分
21.  设二叉树有n个结点，则其深度为
A. n-1
B. n
C. 5floor(log2n)
D. 无法确定
      满分：4  分
22.  判定一个顺序栈（最多元素为m个）为空的条件是（ ）。
A. top＝＝0
B. top＝＝m
C. top!＝0
D. top!＝m
      满分：4  分
23.  以下说法错误的是
A. 用数字式计算机解决问题的实质是对数据的加工处理
B. 程序设计的实质是数据处理
C. 数据的逻辑结构是数据的组织形式，基本运算规定了数据的基本操作方式
D. 运算实现是完成运算功能的算法，或这些算法的设计
      满分：4  分
24.  设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主的存储，a11为第一个元素，其存储地址为1，每个元素占1个地址空间，则a85的地址为（）。
A. 13
B. 18
C. 33
D. 40
      满分：4  分
25.  顺序队列的人队操作应为 ( )
A. sq.rear=sq.rear+1 sq.data[sq.rear]=x
B. sq.data[sq.rear]=x sq.rear=sq.rear+1
C. sq.rear=(sq.rear+1)% maxsize; sq.data[sq.rear]=x
D. sq.data[sqrear]=x sq.rear=(sq.rear+1)% maxsize
      满分：4  分

北航《算法与数据结构》在线作业二
试卷总分：100       测试时间：--
单选题  


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

北航《算法与数据结构》在线作业三
试卷总分：100       测试时间：--
单选题  


一、单选题（共 25 道试题，共 100 分。）V 1.  在一棵二叉树中，第4层上的结点数最多为（ ）。
A. 8
B. 15
C. 16
D. 31
      满分：4  分
2.  非空的循环单链表head的尾节点（由p所指向）满足（ ）。
A. p->next=NULL
B. p=NULL
C. p->next=head
D. p=head
      满分：4  分
3.  堆排序在最坏情况下，其时间复杂性为（ 　）
A. O(nlog2n)
B. O(n2)
C. O(log2n2)
D. O(log2n)
      满分：4  分
4.  采用分块查找时,若线性表中共有625个元素,查找每个元素的概率相同,假设采用顺序查找来确定结点所在的块时,每块应分（）个结点最佳
A. 10
B. 25
C. 6
D. 625
      满分：4  分
5.  队列操作的原则是（ ）。
A. 先进先出
B. 后进先出
C. 只能进行插入
D. 只能进行删除
      满分：4  分
6.  设字符串S1='ABCDEFG'，S2='PQRST'，则运算S=CONCAT（SUB（S1，2，LENGTH（S2）），SUB（S1，LENGTH（S2），2））后结果为（ ）。
A. BCQR'
B. 'BCDEF'
C. 'BCDEFG'
D. 'BCDEFEF'
      满分：4  分
7.  算法的时间复杂度，都要以通过算法中执行频度最高的语句的执行次数来确定这种观点
A. 完全正确
B. 完全错误
C. 视情况而定
D.
以上说法均不正确

      满分：4  分
8.  在索引顺序表中查找一个元素，可用的且最快的方法是（　 ）
A. 用顺序查找法确定元素所在块，再用顺序查找法在相应块中查找
B. 用顺序查找法确定元素所在块，再用二分查找法在相应块中查找
C. 用二分查找法确定元素所在块，再用顺序查找法在相应块中查找
D. 用二分查找法确定元素所在块，再用二分查找法在相应块中查找
      满分：4  分
9.  对有n个记录的有序表采用二分查找，其平均查找长度的量级为（　）
A. O(log2n)
B. O(nlog2n)
C. O(n)
D. O(n2)
      满分：4  分
10.  以下说法正确的是 ( )
A. 因链栈本身没有容量限制,故在用户内存空间的范围内不会出现栈满情况
B. 因顺序栈本身没有容量限制,故在用户内存空间的范围内不会出现栈满情况
C. 对于链栈而言,在栈满状态下,如果此时再作进栈运算，则会发生“上溢”
D. 对于顺序栈而言在栈满状态下如果此时再作迸栈运算，则会发生“下溢”。
      满分：4  分
11.  设有两个串（S1和S2），求S1在S2中首次出现的位置的运算称为（）。
A. 连接
B. 模式匹配
C. 求子串
D. 求串长
      满分：4  分
12.  设有向图有n个顶点和e条边，采用领接表作为其存储表示，在进行拓扑排序时，总的计算时间为（）。
A. O（nloge）
B. O（n+e）
C. O(n*e)
D. O(n的平方)
      满分：4  分
13.  下列图的说法中正确的是（ ） 。
A. 一个具有 n 个顶点的无向完全图的边数为 n(n-1)
B. 连通图的生成树是该图的一个极大连通子图
C. 图的广度优先搜索是一个递归过程
D. 在非连通图的遍历过程中，每调用一次深度优先搜索算法都得到该图的一个连通分量
      满分：4  分
14.  设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主的存储，a11为第一个元素，其存储地址为1，每个元素占1个地址空间，则a85的地址为（）。
A. 13
B. 18
C. 33
D. 40
      满分：4  分
15.  下述几种排序方法中,平均查找长度最小的是（）
A. 插入排序
B. 选择排序
C. 快速排序
D. 归并排序
      满分：4  分
16.  以下说法错误的是（ ）
A. 用数字式计算机解决问题的实质是对数据的加工处理
B. 程序设计的实质是数据处理；数据的逻辑结构是数据的组织形式，基本运算规定了数据的基本操作方式
C. 运算实现是完成运算功能的算法，或这些算法的设计
D. 数据处理方式总是与数据某种相应的表示形式相联系，反之亦然
      满分：4  分
17.  二叉树上叶结点数等于（ ）。
A. 分支结点数加1
B. 单分支结点数加1
C. 双分支结点数加1
D. 双分支结点数减1
      满分：4  分
18.  顺序存储结构（ ）
A. 仅适合于静态查找表的存储
B. 仅适合于动态查找表的存储
C. 既适合静态又适合动态查找表的存储
D. 既不适合静态又不适合动态查找表的存储
      满分：4  分
19.  邻接表是图的一种（ ）。
A. 顺序存储结构
B. 链式存储结构
C. 索引存储结构
D. 列存储结构
      满分：4  分
20.  设无向图的顶点个数为n，则该图最多有（）条边。
A. n-1
B. n(n-1)/2
C. n(n+1)/2
D. 0
      满分：4  分
21.  设有一个无向图G=（V，E）和G’=（V’，E’）如果G’为G的生成树，则下面不正确的说法是（ ）
A. G’为G 的子图
B. G’为G 的边通分量
C. G’为G的极小连通子图且V’=V
D. G’为G的一个无环子图
      满分：4  分
22.  通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着
A. 数据元素具有同一特点
B. 不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致
C. 每个数据元素都一样
D. 数据元素所包含的数据项的个数要相等
      满分：4  分
23.  
对于含有n个顶点e条边的无向连通图，利用Prim算法生成最小代价生成树其时间复杂度为( )。

A. O(log2n)
B. O(n2)
C. O(ne)
D. O(elog2e)
      满分：4  分
24.  向顺序栈中压入新元素时，应当（ ）。
A. 先移动栈顶指针，再存入元素
B. 先存入元素，再移动栈顶指针
C. 先后次序无关紧要
D. 同时进行
      满分：4  分
25.  设二叉树有n个结点，则其深度为
A. n-1
B. n
C. 5floor(log2n)
D. 无法确定
      满分：4  分