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

谋学网

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

一、单选题（共 25 道试题，共 100 分。）V 1.  一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是（）。
A. edcba
B. decba
C. abcde
D. dceab
      满分：4  分
2.  对某二叉树进行前序遍历的结果为ABDEFC，中序遍历的结果为DBFEAC，则后序遍历的结果为（ ）。
A. DBFEAC
B. DFEBCA
C. BDFECA
D. BDEFAC
      满分：4  分
3.  对顺序表上的插入、删除算法的时间复杂性分析来说，通常以（ ）为标准操作
A. 条件判断
B. 结点移动
C. 算术表达式
D. 赋值语句
      满分：4  分
4.  快速排序方法在情况下最不利于发挥其长处。
A. 要排序的数据量太大
B. 要排序的数据中含有多个相同值
C. 要排序的数据已基本有序
D. 要排序的数据个数为奇数
      满分：4  分
5.  某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（ ）的二叉树。
A. 空或只有一个结点
B. 高度等于其结点数
C. 任一结点无左孩子
D. 任一结点无右孩子
      满分：4  分
6.  顺序查找法适合于存储结构为（）的线性表。
A. 散列表
B. 顺序存储或连接存储
C. 压缩存储
D. 索引存储
      满分：4  分
7.  设有向图有n个顶点和e条边，采用领接表作为其存储表示，在进行拓扑排序时，总的计算时间为（）。
A. O（nloge）
B. O（n+e）
C. O(n*e)
D. O(n的平方)
      满分：4  分
8.  在索引顺序表中查找一个元素，可用的且最快的方法是（　 ）
A. 用顺序查找法确定元素所在块，再用顺序查找法在相应块中查找
B. 用顺序查找法确定元素所在块，再用二分查找法在相应块中查找
C. 用二分查找法确定元素所在块，再用顺序查找法在相应块中查找
D. 用二分查找法确定元素所在块，再用二分查找法在相应块中查找
      满分：4  分
9.  在一棵二叉树中，第4层上的结点数最多为（ ）。
A. 8
B. 15
C. 16
D. 31
      满分：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.  二叉树上叶结点数等于（）。
A. 分支结点数加1
B. 单分支结点数加1
C. 双分支结点数加1
D. 双分支结点数减1
      满分：4  分
15.  若用冒泡排序法对序列（18，14，6，27，8，12，16，52，10，26，47，29，41，24）从小到大进行排序，共要进行（ ）次比较。
A. 33
B. 45
C. 70
D. 91
      满分：4  分
16.  二分查找要求被查找的表是（ ）
A. 键值有序的链接表
B. 链接表但键值不一定有序
C. 键值有序的顺序表
D. 顺序表但键值不一定有序
      满分：4  分
17.  有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100},当二分查找值为82的结点时,（ ）次比较后查找成功。
A. 1
B. 2
C. 4
D. 8
      满分：4  分
18.  设循环队列Q[1..N-1]的头尾指针为F，R，当插入元素时尾指针R加1，头指针F总是指在队列中第一个元素的前一个位置，则队列中元素计数为（）。
A. R-F
B. N-（R-F）
C. （R-F+N）%N
D. （F-R+N）%N
      满分：4  分
19.  如果从无向的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是（ ）。
A. 完全图
B. 连通图
C. 有回路
D. 一棵树
      满分：4  分
20.  设有两个串（S1和S2），求S1在S2中首次出现的位置的运算称为（）。
A. 连接
B. 模式匹配
C. 求子串
D. 求串长
      满分：4  分
21.  有一个长度为12的有序表,按二分查找法对该表进行查找,在表内各元素等概率情况下查找成功所需的平均比较次数为（）
A. 35/12
B. 37/12
C. 39/12
D. 43/12
      满分：4  分
22.  二叉树上叶结点数等于（ ）。
A. 分支结点数加1
B. 单分支结点数加1
C. 双分支结点数加1
D. 双分支结点数减1
      满分：4  分
23.  下列数据结构中，能用折半查找的是( )。
A. 顺序存储的有序线性表
B. 线性链表
C. 二叉链表
D. 有序线性链表
      满分：4  分
24.  以下四种排序方法中，要求附加的内存容量最大的是（ ）
A. 插入排序
B. 选择排序
C. 快速排序
D. 归并排序
      满分：4  分
25.  对于数据结构课程的主要内容，以下解释正确的是
A. 数据结构的定义，包括逻辑结构、存储结构和基本运算集
B. 数据结构的实现，包括存储实现、运算实现和基本运算集
C. 数据结构的评价和选择，包括逻辑结构的选择、基本运算集的选择和存储选择
D. 以上说法均不正确
      满分：4  分

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