北航14春《算法与数据结构》在线作业答案
北航14春《算法与数据结构》在线作业一试卷总分：100 测试时间：--
一、单选题（共25道试题，共100分。）
1.除了( ) ，其它任何指针都不能在算法中作为常量出现，也无法显示。
A. 头指针
B. 尾指针
C. 指针型变量
D. 空指针
满分：4分
2.有 n 条边的无向图的邻接表存储法中，链边中结点的个数是（ ）个。
A. n
B. 2n
C. n/2
D. n*n
满分：4分
3.判定一个顺序栈（最多元素为m个）为空的条件是（ ）。
A. top＝＝0
B. top＝＝m
C. top!＝0
D. top!＝m
满分：4分
4.快速排序的记录移动次数（ ）比较次数，其总执行时间为O(nlog2n)。
A. 大于
B. 大于等于
C. 小于等于
D. 小于
满分：4分
5.对某二叉树进行前序遍历的结果为ABDEFC，中序遍历的结果为DBFEAC，则后序遍历的结果为（ ）。
A. DBFEAC
B. DFEBCA
C. BDFECA
D. BDEFAC
满分：4分
6.若线性表最常用的操作是存取第i个元素及其前趋的值，则采用（ ）存储方式节省时间。
A. 单链表
B. 双链表
C. 单循环链表
D. 顺序表
满分：4分
7.图的深度优先遍历类似于二叉树的（ ）。
A. 先序遍历
B. 中序遍历
C. 后序遍历
D. 层次遍历
满分：4分
8.假设一个有n个顶点和e条弧的有向图用邻接表表示,则删除与某个顶点vi相关的所有弧的时间复杂度是()。
A. O(n)
B. O(e)
C. O(n+e)
D. O(n*e)
满分：4分
9.串的逻辑结构与（ ）的逻辑结构不同。
A. 线性表
B. 栈
C. 队列
D. 树
满分：4分
10.对线性表进行二分查找时,要求线性表必须（ ）。
A. 以顺序方式存储
B. 以链接方式存储
C. 以顺序方式存储,且结点按关键字有序排序
D. 以链接方式存储,且结点按关键字有序排序
满分：4分
11.栈操作的原则是（ ）
A. 栈顶删除
B. 先进先出
C. 后进先出
D. 栈顶插入
满分：4分
12.某程序的时间复杂度为（3n+nlog2n+n 2+8）, 其数量级表示为（ ）。
A. O（n）
B. O（nlog2n）
C. O（n 2）
D. O（log2n）
满分：4分
13.堆排序在最坏情况下，其时间复杂性为（ ）
A. O(nlog2n)
B. O(n2)
C. O(log2n2)
D. O(log2n)
满分：4分
14.串是任意有限个（ ）
A. 符号构成的序列
B. 符号构成的集合
C. 字符构成的序列
D. 字符构成的集合
满分：4分
15.下列有关图遍历的说法中不正确的是（ ）。
A. 连通图的深度优先搜索是个递增过程
B. 图的广度优先搜索中邻接点的寻找具有“先进先出”的特征
C. 非连通图不能用深度优先搜索法
D. 图的遍历要求每个顶点仅被访问一次
满分：4分
16.以下关于数据的存储结构的叙述哪一条是正确的（ ）。
A. 数据的存储结构是数据间关系的抽象描述
B. 数据的存储结构是逻辑结构在计算机存储器中的实现
C. 数据的存储结构分为线性结构和非线性结构
D. 数据的存储结构对数据运算的具体实现没有影响
满分：4分
17.设有向图有n个顶点和e条边，采用领接表作为其存储表示，在进行拓扑排序时，总的计算时间为（）。
A. O（nloge）
B. O（n+e）
C. O(n*e)
D. O(n的平方)
满分：4分
18.具有24个记录的序列，采用冒泡排序至少的比较次数是（ ）
A. 1
B. 23
C. 24
D. 529
满分：4分
19.一般地，一个存储结构包括以下三个主要部分。以下说法错误的是
A. 存储结点每个存储结点可以存放一个或一个以上的数据元素
B. 数据元素之间关联方式的表示 也就是逻辑结构的机内表示
C. 附加设施，如为便于运算实现而设置的“哑结点”等等
D. 一种存储结构可以在两个级别上讨论。其一是机器级，其二是语言级
满分：4分
20.3个结点可构成（ ）个不同形态的二叉树。
A. 2
B. 3
C. 4
D. 5
满分：4分
21.顺序队列的人队操作应为 ( )
A. sq.rear=sq.rear+1 sq.data=x
B. sq.data=x sq.rear=sq.rear+1
C. sq.rear=(sq.rear+1)% maxsize; sq.data=x
D. sq.data=x sq.rear=(sq.rear+1)% maxsize
满分：4分
22.二叉树第i层上至多有（）结点。
A. 2i
B. 2的i次方
C. 2i-1
D. 2 的（i-1）次方
满分：4分
23.用某种排序方法队线性表（25，84，21，47，15，27，68，35，20）进行排序，元素序列变化如下：（1）25，84，21，47，15，27，68，35，20 （2）20，15，21，25，47，27，68，35，84 （3）15，20，21，25，35，27，47，68，84 （4）15，20，21，25，27，35，47，68，84 所采用的排序方法是（ ）。
A. 选择排序
B. Shell排序
C. 归并排序
D. 快速排序
满分：4分
24.组成数据结构的基本单位是（ ）。
A. 数据项
B. 数据类型
C. 数据元素
D. 数据变量
满分：4分
25.循环队列的人队操作应为 ( )
A. sq.rear=sq.rear+1 sq.data=x
B. sq.data=x sq.rear=sq.rear+1
C. sq.rear=(sq.rear+1)% maxsize sq.data=x
D. sq.data=x sq.rear=(sq.rear+1)% maxsize
北航《算法与数据结构》在线作业二
试卷总分：100 测试时间：--
一、单选题（共25道试题，共100分。）
1.以下说法正确的是（ ）
A. 所谓数据的逻辑结构指的是数据元素之间的逻辑关系
B. 逻辑结构与数据元素本身的内容和形式无关
C. 顺序文件只适合于存放在磁带上，索引文件只能存放在磁盘上
D. 基于某种逻辑结构之上的运算，其实现是惟一的
满分：4分
2.循环队列的人队操作应为 ( )
A. sq.rear=sq.rear+1 sq.data=x
B. sq.data=x sq.rear=sq.rear+1
C. sq.rear=(sq.rear+1)% maxsize sq.data=x
D. sq.data=x sq.rear=(sq.rear+1)% maxsize
满分：4分
3.有 n 条边的无向图的邻接表存储法中，链边中结点的个数是（ ）个。
A. n
B. 2n
C. n/2
D. n*n
满分：4分
4.按照二叉树的定义，具有3个结点的二叉树有（ ）种。
A. 3
B. 4
C. 5
D. 6
满分：4分
5.除了( ) ，其它任何指针都不能在算法中作为常量出现，也无法显示。
A. 头指针
B. 尾指针
C. 指针型变量
D. 空指针
满分：4分
6.设有1000个无序的元素,希望用最快的速度挑选出其中前10个最大的元素,最好（）排序法。
A. 起泡排序
B. 快速排序
C. 堆排序
D. 基数排序
满分：4分
7.下述几种排序方法中,要求内存量最大的是（）。
A. 插入排序
B. 选择排序
C. 快速排序
D. 归并排序
满分：4分
8.在一个顺序队列中，队首指针指向队首元素的（ ）位置。
A. 后一个
B. 前一个
C. 当前
D. 不确定
满分：4分
9.二分查找和二叉排序树的时间性能（ ）。
A. 始终相同
B. 始终不相同
C. 根据情况确定
D. 以上说法均不正确
满分：4分
10.设有一个10阶的对称矩阵A，采用压缩存储方式按行将矩阵中下三角部分的元素存入一维数组B[ ]中，A存入B中，则A在B[ ]中（ ）位置。
A. 32
B. 33
C. 41
D. 65
满分：4分
11.为了最快地对线性结构的数据进行某数据元素的读取操作，则其数据存储结构宜采用( )方式。
A. 顺序存储
B. 链式存储
C. 索引存储
D. 散列存储
满分：4分
12.顺序查找法适合于存储结构为（）的线性表。
A. 散列表
B. 顺序存储或连接存储
C. 压缩存储
D. 索引存储
满分：4分
13.设在栈中，由顶向下已存放元素c、b、a，在第4个元素d入栈之前，栈中元素可以出栈， 试问d入栈前后，不可能的出栈序列是( )。
A. d c b a
B. c b d a
C. c a d b
D. c d b a
满分：4分
14.对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是（ ）。
A. n
B. (n-1)(n-1)
C. n-1
D. n*n
满分：4分
15.下列关于树说法正确的是
A. 树的先根遍历序列与其对应的二叉树的先根遍历序列相同
B. 树的先根遍历序列与其对应的二叉树的后根遍历序列相同
C. 树的后根遍历序列与其对应的二叉树的先根遍历序列相同
D. 树的后根遍历序列与其对应的二叉树的后根遍历序列相同
满分：4分
16.每次从无序表中取出一个元素，把它插入到有序表中的适当位置，此种排序方法叫做（）排序.
A. 插入
B. 交换
C. 选择
D. 归并
满分：4分
17.强连通分量是（ ）极大连通子图。
A. 有向图
B. 无向图
C. 树
D. 图
满分：4分
18.任何一棵二叉树的叶结点在其先根、中根、后跟遍历序列中的相对位置
A. 肯定发生变化
B. 有时发生变化
C. 肯定不发生变化
D. 无法确定
满分：4分
19.一个有顺序表有255个对象，采用顺序搜索法查表，平均搜索长度为（ ）。
A. 128
B. 127
C. 126
D. 255
满分：4分
20.对n个记录的文件进行堆排序，最坏情况下的执行时间为 ( )。
A. O(log2n)
B. O(nlogn)
C. O(n)
D. O(n的平方)
满分：4分
21.有 n 个顶点的无向图的邻接矩阵是用（ ）组存储。
A. n 行 n 列
B. 一维
C. 任意行 n 列
D. n 行任意列
满分：4分
22.一个具有n个顶点的无向完全图的边数为（ ）
A. n(n+1)/2
B. n(n-1)/2
C. n(n-1)
D. n(n+1)
满分：4分
23.图的深度优先遍历类似于二叉树的（ ）。
A. 先序遍历
B. 中序遍历
C. 后序遍历
D. 层次遍历
满分：4分
24.一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是（）。
A. edcba
B. decba
C. abcde
D. dceab
满分：4分
25.一个加权的无向连通图的最小生成树（ ）。
A. 有一棵或多棵
B. 只有一棵
C. 一定有多棵
D. 可能不存在
北航《算法与数据结构》在线作业三
试卷总分：100 测试时间：--
一、单选题（共25道试题，共100分。）
1.栈操作的原则是（ ）
A. 栈顶删除
B. 先进先出
C. 后进先出
D. 栈顶插入
满分：4分
2.二分查找和二叉排序树的时间性能（ ）。
A. 始终相同
B. 始终不相同
C. 根据情况确定
D. 以上说法均不正确
满分：4分
3.下列有关图遍历的说法中不正确的是（ ）。
A. 连通图的深度优先搜索是个递增过程
B. 图的广度优先搜索中邻接点的寻找具有“先进先出”的特征
C. 非连通图不能用深度优先搜索法
D. 图的遍历要求每个顶点仅被访问一次
满分：4分
4.若某线性表中最常用的操作是取第i 个元素和找第i个元素的前趋元素，则采用（ ）存储方式最节省时间。
A. 单链表
B. 双链表
C. 单向循环
D. 顺序表
满分：4分
5.除了( ) ，其它任何指针都不能在算法中作为常量出现，也无法显示。
A. 头指针
B. 尾指针
C. 指针型变量
D. 空指针
满分：4分
6.对线性表进行二分查找时,要求线性表必须（ ）。
A. 以顺序方式存储
B. 以链接方式存储
C. 以顺序方式存储,且结点按关键字有序排序
D. 以链接方式存储,且结点按关键字有序排序
满分：4分
7.设字符串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分
8.设有10000个元素组成的无序序列,希望尽快挑选出其中前10个最大值元素,在不改变已有算法结构的前提下,以下几种内排序算法中( )最合适。
A. 选择排序法
B. 快速排序法
C. 堆排序法
D. 冒泡排序法。
满分：4分
9.某程序的时间复杂度为（3n+nlog2n+n 2+8）, 其数量级表示为（ ）。
A. O（n）
B. O（nlog2n）
C. O（n 2）
D. O（log2n）
满分：4分
10.顺序表中逻辑上相邻的节点其物理位置也（ ）。
A. 一定相邻
B. 不必相邻
C. 按某种规律排列
D. 无要求
满分：4分
11.在稀疏矩阵的带行指针向量的链接存储中，每个行单链表中的结点都具有相同的（）。
A. 行号
B. 列号
C. 元素值
D. 地址
满分：4分
12.通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着
A. 数据元素具有同一特点
B. 不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致
C. 每个数据元素都一样
D. 数据元素所包含的数据项的个数要相等
满分：4分
13.以下四种排序方法中，要求附加的内存容量最大的是（ ）
A. 插入排序
B. 选择排序
C. 快速排序
D. 归并排序
满分：4分
14.一组记录的关键码为(46,79,56,38,40,84),则利用快速排序的方法,以第一个记录为基准得到的一次划分结果为（）。
A. 38,40,46,56,79,84
B. 40,38,46,79,56,84
C. 40,38,46,56,79,84
D. 40,38,46,84,56,79
满分：4分
15.具有65个结点的完全二叉树的高度为（ ）。（根的层次号为0）
A. 8
B. 7
C. 6
D. 5
满分：4分
16.单链表表示法的基本思想是指针P表示结点间的逻辑关系，则以下说法错误的是
A. 任何指针都不能用打印语句输出一个指针型变量的值
B. 如果要引用(如访问)p所指结点，只需写出p(以后跟域名)即可
C. 若想修改变量p的值(比如让P指向另一个结点)，则应直接对p赋值
D. 对于一个指针型变量P的值。只需知道它指的是哪个结点
满分：4分
17.在一个长度为n的顺序存储的线性表中，向第i个元素（1≤i≤n+1）之前插入一个新元素时，需要从前向后依次后移（ ）个元素。
A. n-i
B. n-i+1
C. n-i-1
D. i
满分：4分
18.顺序表是线性表的
A. 链式存储结构
B. 顺序存储结构
C. 索引存储结构
D. 散列存储结构
满分：4分
19.顺序查找法适合于存储结构为（）的线性表。
A. 散列表
B. 顺序存储或连接存储
C. 压缩存储
D. 索引存储
满分：4分
20.顺序队列的人队操作应为 ( )
A. sq.rear=sq.rear+1 sq.data=x
B. sq.data=x sq.rear=sq.rear+1
C. sq.rear=(sq.rear+1)% maxsize; sq.data=x
D. sq.data=x sq.rear=(sq.rear+1)% maxsize
满分：4分
21.线性表的链接实现有利于（）运算。
A. 插入
B. 读表元
C. 查找
D. 定位
满分：4分
22.一般地，一个存储结构包括以下三个主要部分。以下说法错误的是
A. 存储结点每个存储结点可以存放一个或一个以上的数据元素
B. 数据元素之间关联方式的表示 也就是逻辑结构的机内表示
C. 附加设施，如为便于运算实现而设置的“哑结点”等等
D. 一种存储结构可以在两个级别上讨论。其一是机器级，其二是语言级
满分：4分
23.下列数据组织形式中，（ ）的各个结点可以任意邻接。
A. 集合
B. 树形结构
C. 线性结构
D. 图状结构
满分：4分
24.在一个图中，所有顶点的度数之和等于所有边数的（ ）倍。
A. 1
B. 2
C. 3
D. 4
满分：4分
25.采用二分查找方法查找长度为n的线性表时,每个元素的平均查找长度为（）
A. O(n2)
B. O(log2n)
C. O(n)
D. O(log2n)
满分：4分
页:
[1]