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

、单选题（共 25 道试题，共 100 分。）
1. Substring('DATA STRUCTURE'，5，9)=（ ）。
A. 'STRUCTURE'
B. 'ASTUCTUR'
C. 'DATA STRUCTRUE'
D. 'DATA'
   满分：4 分
2. 某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（ ）的二叉树。
A. 空或只有一个结点高度等于其结点数
B. 任一结点无左孩子
C. 任一结点无右孩子
   满分：4 分
3. 设有50行60列的二维数组A[50][60]，其元素长度为4字节，按行优先顺序存储，基地址为200，则元素A[18][25]的存储地址为（）。
A. 3700
B. 4376
C. 3900
D. 4620
   满分：4 分
4. 在一个顺序队列中，队首指针指向队首元素的（　　）位置。
A. 后一个
B. 前一个
C. 当前
D. 不确定
   满分：4 分
5. 在线性表的散列存储中，若用m表示散列表的长度，n表示待散列存储的元素的个数，则装填因子a等于（）。
A. n/m
B. m/n
C. n/(n+m)
D. m/(n+m)
   满分：4 分
6. 算法分析的目的是（)。
A. 找出数据结构的合理性
B. 研究算法中的输入和输出的关系
C. 分析算法的效率以求改进
D. 分析算法的易读性和文档性
   满分：4 分
7. 向顺序栈中压入新元素时，应当（ ）。
A. 先移动栈顶指针，再存入元素
B. 先存入元素，再移动栈顶指针
C. 先后次序无关紧要
D. 同时进行
   满分：4 分
8. 一般地，一个存储结构包括以下三个主要部分。以下说法错误的是
A. 存储结点每个存储结点可以存放一个或一个以上的数据元素
B. 数据元素之间关联方式的表示 也就是逻辑结构的机内表示
C. 附加设施，如为便于运算实现而设置的“哑结点”等等
D. 一种存储结构可以在两个级别上讨论。其一是机器级，其二是语言级
   满分：4 分
9. n个顶点的连通图至少有（ ）条边。
A. n-1
B. n
C. n+1
D. 0
   满分：4 分
10. 排序方法中,从未排序序列中依次取出元素与己排序序列(初始时为空)中的元素进行比较,将其放入己排序序列的正确位置上的方法,称为（）
A. 希尔排序
B. 起泡排序
C. 插入排序
D. 选择排序
   满分：4 分
11. 3个结点可构成（ 　）个不同形态的二叉树。
A. 2
B. 3
C. 4
D. 5
   满分：4 分
12. 在一个具有n个顶点的无向图中，要连通所有顶点则至少需要（ ）条边。
A. n
B. 2n
C. n-1
D. n+1
   满分：4 分
13. 当初始序列已经按键值有序，用直接插入算法对其进行排序，需要循环的次数为（ ）
A. n2
B. nlog2n
C. log2n
D. n-1
   满分：4 分
14. 深度为6的二叉树最多有( )个结点
A. 64
B. 63
C. 32
D. 31
   满分：4 分
15. 如果待排序序列中两个数据元素具有相同的值，在排序后它们的位置发生颠倒，则称该排序是不稳定的。下列选项中，（）就是不稳定的排序方法。
A. 起泡排序
B. 归并排序
C. 直接插入法排序
D. 简单选择排序
   满分：4 分
16. 对有n个记录的表按记录键值有序的顺序建立二叉树，在这种情况下，其平均查找长度的量级为（　）
A. O(n)
B. O(nlog2n)
C. O(1)
D. (log2n)
   满分：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. 有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100},当二分查找值为82的结点时,（ ）次比较后查找成功。
A. 1
B. 2
C. 4
D. 8
   满分：4 分
21. 以下说法错误的是
A. 用数字式计算机解决问题的实质是对数据的加工处理
B. 程序设计的实质是数据处理
C. 数据的逻辑结构是数据的组织形式，基本运算规定了数据的基本操作方式
D. 运算实现是完成运算功能的算法，或这些算法的设计
   满分：4 分
22. 串的逻辑结构与（ ）的逻辑结构不同。
A. 线性表
B. 栈
C. 队列
D. 树
   满分：4 分
23. 以下四种排序方法中，要求附加的内存容量最大的是（ ）
A. 插入排序
B. 选择排序
C. 快速排序
D. 归并排序
   满分：4 分
24. 二叉树上叶结点数等于（）。
A. 分支结点数加1
B. 单分支结点数加1
C. 双分支结点数加1
D. 双分支结点数减1
   满分：4 分
25. 某二叉树结点的前序序列为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 分