奥鹏13春北航《算法与数据结构》在线作业一资料

谋学网

一、单选题（共 25 道试题，共 100 分。）V 1.  采用顺序查找方法查找长度为n的线性表时，每个元素的平均长度为( ）。
A. n
B. n/2
C. (n+1)/2
D. (n-1)/2
      满分：4  分
2.  关于逻辑结构，以下说法错误的是
A. 逻辑结构与数据元素本身的形成、内容无关
B. 逻辑结构与数据元素的相对位置有关
C. 逻辑结构与所含结点个数无关
D. 一些表面上很不相同的数据可以有相同的逻辑结构
      满分：4  分
3.  以下四种排序方法中，要求附加的内存容量最大的是（ ）
A. 插入排序
B. 选择排序
C. 快速排序
D. 归并排序
      满分：4  分
4.  在所有排序方法中，关键字比较的次数与记录得初始排列次序无关的是（）
A. 希尔排序
B. 起泡排序
C. 插入排序
D. 选择排序
      满分：4  分
5.  设有两个串（S1和S2），求S1在S2中首次出现的位置的运算称为（）。
A. 连接
B. 模式匹配
C. 求子串
D. 求串长
      满分：4  分
6.  顺序查找法适合于存储结构为（）的线性表。
A. 散列表
B. 顺序存储或连接存储
C. 压缩存储
D. 索引存储
      满分：4  分
7.  具有24个记录的序列，采用冒泡排序至少的比较次数是（ ）
A. 1
B. 23
C. 24
D. 529
      满分：4  分
8.  判定一个顺序栈（最多元素为m个）为空的条件是（ ）。
A. top＝＝0
B. top＝＝m
C. top!＝0
D. top!＝m
      满分：4  分
9.  在一棵二叉树中，第4层上的结点数最多为（ ）。
A. 8
B. 15
C. 16
D. 31
      满分：4  分
10.  下述几种排序方法中,要求内存量最大的是（）。
A. 插入排序
B. 选择排序
C. 快速排序
D. 归并排序
      满分：4  分
11.  深度为5的二叉树至多有（ ）个节点。
A. 16
B. 32
C. 31
D. 10
      满分：4  分
12.  顺序存储结构（ ）
A. 仅适合于静态查找表的存储
B. 仅适合于动态查找表的存储
C. 既适合静态又适合动态查找表的存储
D. 既不适合静态又不适合动态查找表的存储
      满分：4  分
13.  队列操作的原则是（ ）。
A. 先进先出
B. 后进先出
C. 只能进行插入
D. 只能进行删除
      满分：4  分
14.  一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是（）。
A. edcba
B. decba
C. abcde
D. dceab
      满分：4  分
15.  若待排序对象序列在排序前已按其排序码递增顺序排序，则采用（ ）方法比较次数最少。
A. 直接插入排序
B. 快速排序
C. 归并排序
D. 直接选择排序
      满分：4  分
16.  若某线性表中最常用的操作是取第I个元素和找第I个元素的前趋元素，则采用( )存储方式最节省时间。
A. 顺序表
B. 单链表
C. 双链表
D. 单循环链表
      满分：4  分
17.  算法分析的目的是（)。
A. 找出数据结构的合理性
B. 研究算法中的输入和输出的关系
C. 分析算法的效率以求改进
D. 分析算法的易读性和文档性
      满分：4  分
18.  任何一棵二叉树的叶结点在其先根、中根、后跟遍历序列中的相对位置
A. 肯定发生变化
B. 有时发生变化
C. 肯定不发生变化
D. 无法确定
      满分：4  分
19.  设矩阵A（aij ，l≤i,j≤ 10）的元素满足： aij≠0(i≥j, l≤i, j≤ 10) aij=0 (i<j, l≤i, j≤ 10) 现将A的所有非0元素以行序为主序存放在首地址为2000的存储区域中，每个元素占有4个单元，则元素A[9][5]的首址为
A. 2340
B. 2336
C. 2164
D. 2160
      满分：4  分
20.  计算机的算法必须具备输入，输出和（ ）五个特性。
A. 可行性，可移植性和可扩充性
B. 可行性，确定性和有穷性
C. 确定性，有穷性和稳定性
D. 易读性，稳定性和安全性
      满分：4  分
21.  由两个栈共享一个向量空间的好处是（ ）。
A. 减少存取时间，降低下溢发生的机率
B. 节省存储空间，降低上溢发生的机率
C. 减少存取时间，降低上溢发生的机率
D. 节省存储空间，降低下溢发生的机率
      满分：4  分
22.  树最适合用来表示（ ）。
A. 有序数据元素
B. 无序数据元素
C. 元素之间具有分支层次关系的数据
D. 元素之间无联系的数据
      满分：4  分
23.  具有65个结点的完全二叉树的高度为（ ）。（根的层次号为0）
A. 8
B. 7
C. 6
D. 5
      满分：4  分
24.  设哈希表长m=14,哈希函数H(key)=key%11。表中已有4个结点: addr(15)=4 addr(38)=5 addr(61)=6 addr(84)=7其余地址为空，如用二次探测再散列处理冲突,关键字为49的结点的地址是（）。
A. 8
B. 3
C. 5
D. 9
      满分：4  分
25.  对顺序表上的插入、删除算法的时间复杂性分析来说，通常以（ ）为标准操作
A. 条件判断
B. 结点移动
C. 算术表达式
D. 赋值语句
      满分：4  分