北航12春《算法与数据结构》在线作业二

谋学网

谋学网: www.mouxue.com 主要提供奥鹏作业资料，奥鹏在线作业资料，奥鹏离线作业资料以及奥鹏毕业论文，致力打造中国最专业远程教育辅导社区。

一、单选题（共 25 道试题，共 100 分。）V 1.  Substr('DATA STRUCTURE'，5，9)=（ ）。
A. STRUCTURE'
B. 'ASTUCTUR'
C. 'DATA STRUCTRUE'
      满分：4  分
2.  将含有83个结点的完全二叉树从根结点开始编号，根为1号，后面按从上到下、从左到右的顺序对结点编号，那么编号为41的双结点编号为
A. 42
B. 40
C. 21
D. 20
      满分：4  分
3.  假设一个有n个顶点和e条弧的有向图用邻接表表示,则删除与某个顶点vi相关的所有弧的时间复杂度是()。
A. O(n)
B. O(e)
C. O(n+e)
D. O(n*e)
      满分：4  分
4.  下列关于栈的叙述正确的是（ ）。
A. 栈是非线性结构
B. 栈是一种树状结构
C. 栈具有先进先出的特征
D. 栈具有后进先出的特征
      满分：4  分
5.  按照二叉树的定义，具有3个结点的二叉树有（ ）种。
A. 3
B. 4
C. 5
D. 6
      满分：4  分
6.  在一个图中，所有顶点的度数之和等于所有边数的（ ）倍。
A. 1
B. 2
C. 3
D. 4
      满分：4  分
7.  具有65个结点的完全二叉树其深度为（）。
A. 8
B. 7
C. 6
D. 5
      满分：4  分
8.  对于单链表表示法，以下说法错误的是（ ）
A. 数据域用于存储线性表的一个数据元素
B. 指针域或链域用于存放一个指向本结点所含数据元素的直接后继所在结点的指针
C. 所有数据通过指针的链接而组织成单链表
D. NULL称为空指针，它不指向任何结点，只起标志作用
      满分：4  分
9.  队列的删除操作是在（ ）进行。
A. 队首
B. 队尾
C. 队前
D. 队后
      满分：4  分
10.  以下关于树的说法错误的是
A. 树形结构的特点是一个结点可以有多个直接前趋
B. 线性结构中的一个结点至多只有一个直接后继
C. 树形结构可以表达(组织)更复杂的数据
D. 树(及一切树形结构)是一种"分支层次"结构
      满分：4  分
11.  对于顺序表，以下说法错误的是（ ）
A. 顺序表是用一维数组实现的线性表，数组的下标可以看成是元素的绝对地址
B. 顺序表的所有存储结点按相应数据元素间的逻辑关系决定的次序依次排列
C. 顺序表的特点是:逻辑结构中相邻的结点在存储结构中仍相邻
D. 顺序表的特点是:逻辑上相邻的元素，存储在物理位置也相邻的单元中
      满分：4  分
12.  以下关于二叉树说法错误的是
A. 二叉树可以是空集
B. 二叉树的任一结点都有两棵子树
C. 二叉树与树具有相同的树形结构
D. 二叉树中任一结点的两棵子树有次序之分
      满分：4  分
13.  设有一个二元数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676 (10)，每个元素占一个空间，则A[4][5]在（ ）位置，(10)表明用10进数表示。
A. 692(10)
B. 626(10)
C. 709(10)
D. 724(10)
      满分：4  分
14.  在一个无向图中，所有顶点的度数之和等于所有边数的（ ）倍。
A. 3
B. 2
C. 1
D. 1/2
      满分：4  分
15.  若由森林转化得到的二叉树是非空的二叉树，则二叉树形状是 （）。
A. 根结点无右子树的二叉树
B. 根结点无左子树的二叉树
C. 根结点可能有左二叉树和右二叉树
D. 各结点只有一个儿子的二叉树
      满分：4  分
16.  在一个长度为n的顺序存储的线性表中，向第i个元素（1≤i≤n+1）之前插入一个新元素时，需要从前向后依次后移（ ）个元素。
A. n-i
B. n-i+1
C. n-i-1
D. i
      满分：4  分
17.  若用冒泡排序法对序列（18，14，6，27，8，12，16，52，10，26，47，29，41，24）从小到大进行排序，共要进行（ ）次比较。
A. 33
B. 45
C. 70
D. 91
      满分：4  分
18.  在稀疏矩阵的带行指针向量的链接存储中，每个行单链表中的结点都具有相同的（）。
A. 行号
B. 列号
C. 元素值
D. 地址
      满分：4  分
19.  设有1000个元素，用二分法查找时，最大比较次数是（ ）。
A. 1
B. 7
C. 10
D. 25
      满分：4  分
20.  在一个具有n个顶点的无向图中，要连通所有顶点则至少需要（ ）条边。
A. n
B. 2n
C. n-1
D. n+1
      满分：4  分
21.  在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为()。
A. e
B. 2e
C. n的平方－e
D. n的平方－2e
      满分：4  分
22.  以下数据结构中不属于线性数据结构的是（ ）。
A. 线性表
B. 队列
C. 二叉树
D. 栈
      满分：4  分
23.  对某二叉树进行前序遍历的结果为ABDEFC，中序遍历的结果为DBFEAC，则后序遍历的结果为（ ）。
A. DBFEAC
B. DFEBCA
C. BDFECA
D. BDEFAC
      满分：4  分
24.  以下说法错误的是（ ）
A. 用数字式计算机解决问题的实质是对数据的加工处理
B. 程序设计的实质是数据处理；数据的逻辑结构是数据的组织形式，基本运算规定了数据的基本操作方式
C. 运算实现是完成运算功能的算法，或这些算法的设计
D. 数据处理方式总是与数据某种相应的表示形式相联系，反之亦然
      满分：4  分
25.  在所有排序方法中，关键字比较的次数与记录得初始排列次序无关的是（）
A. 希尔排序
B. 起泡排序
C. 插入排序
D. 选择排序
      满分：4  分

谋学网: www.mouxue.com 主要提供奥鹏作业资料，奥鹏在线作业资料，奥鹏离线作业资料以及奥鹏毕业论文，致力打造中国最专业远程教育辅导社区。