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

久爱奥鹏晓林

一、单选题（共 25 道试题，共 100 分。）V 1.  若某线性表中最常用的操作是取第I个元素和找第I个元素的前趋元素，则采用( )存储方式最节省时间。
A. 顺序表
B. 单链表
C. 双链表
D. 单循环链表
      满分：4  分
2.  有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100},当二分查找值为82的结点时,（ ）次比较后查找成功。
A. 1
B. 2
C. 4
D. 8
      满分：4  分
3.  某二叉树结点的前序序列为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  分
4.  在一个顺序队列中，队首指针指向队首元素的（　　）位置。
A. 后一个
B. 前一个
C. 当前
D. 不确定
      满分：4  分
5.  线性链表不具有的特点是（）。
A. 随机访问
B. 不必事先估计所需存储空间大小
C. 插入与删除时不必移动元素
D. 所需空间与线性表长度成正比
      满分：4  分
6.  当初始序列已经按键值有序，用直接插入算法对其进行排序，需要循环的次数为（ ）
A. n2
B. nlog2n
C. log2n
D. n-1
      满分：4  分
7.  具有24个记录的序列，采用冒泡排序至少的比较次数是（ ）
A. 1
B. 23
C. 24
D. 529
      满分：4  分
8.  向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（ ）个元素。
A. 8
B. 63.5
C. 64
D. 7
      满分：4  分
9.  设有1000个元素，用折半查找时，最大比较次数是（）。
A. 1
B. 7
C. 10
D. 25
      满分：4  分
10.  队列的插入操作是在（ ）进行。
A. 队首
B. 队尾
C. 队前
D. 队后
      满分：4  分
11.  算法的时间复杂度是指（ ）。
A. 执行算法程序所需要的时间
B. 算法程序的长度
C. 算法执行过程中所需要的基本运算次数
D. 算法程序中的指令条数
      满分：4  分
12.  Substr('DATA STRUCTURE'，5，9)=（ ）。
A. STRUCTURE'
B. 'ASTUCTUR'
C. 'DATA STRUCTRUE'
      满分：4  分
13.  关于有向图的邻接表和逆邻接表表示法，下列结论正确的是 （）。
A. 用邻接表表示法计算入度比较方便
B. 用邻接表表示法计算入度和出度都方便
C. 用逆邻接表表示法计算入度和出度都不方便
D. 用逆邻接表表示法计算入度比计算出度方便
      满分：4  分
14.  当利用大小为N 的数组顺序存储一个栈时，假定用top = = N表示栈空，则退栈时，用（ ）语句000top指针。
A. top++
B. top=0
C. top--
D. top=N
      满分：4  分
15.  对某二叉树进行前序遍历的结果为ABDEFC，中序遍历的结果为DBFEAC，则后序遍历的结果为（ ）。
A. DBFEAC
B. DFEBCA
C. BDFECA
D. BDEFAC
      满分：4  分
16.  两个串相等的充分必要条件是（ ）。
A. 两个串的长度相等
B. 两个串对应位置的字符相等
C. 两个串的长度相等且对应位置的字符相同
D. 以上条件都不正确
      满分：4  分
17.  下述几种排序方法中,平均查找长度最小的是（）
A. 插入排序
B. 选择排序
C. 快速排序
D. 归并排序
      满分：4  分
18.  单链表表示法的基本思想是指针P表示结点间的逻辑关系，则以下说法错误的是
A. 任何指针都不能用打印语句输出一个指针型变量的值
B. 如果要引用(如访问)p所指结点，只需写出p(以后跟域名)即可
C. 若想000变量p的值(比如让P指向另一个结点)，则应直接对p赋值
D. 对于一个指针型变量P的值。只需知道它指的是哪个结点
      满分：4  分
19.  如果结点A有3个兄弟，而且B为A的双亲，则B的度为（ ）。
A. 1
B. 3
C. 4
D. 5
      满分：4  分
20.  在一个长度为n的顺序存储的线性表中，向第i个元素（1≤i≤n+1）之前插入一个新元素时，需要从后向前依次后移（ ）个元素。
A. n-i
B. n-i+1
C. n-i-1
D. i
      满分：4  分
21.  由两个栈共享一个向量空间的好处是（ ）。
A. 减少存取时间，降低下溢发生的机率
B. 节省存储空间，降低上溢发生的机率
C. 减少存取时间，降低上溢发生的机率
D. 节省存储空间，降低下溢发生的机率
      满分：4  分
22.  一般地，一个存储结构包括以下三个主要部分。以下说法错误的是
A. 存储结点每个存储结点可以存放一个或一个以上的数据元素
B. 数据元素之间关联方式的表示 也就是逻辑结构的机内表示
C. 附加设施，如为便于运算实现而设置的“哑结点”等等
D. 一种存储结构可以在两个级别上讨论。其一是机器级，其二是语言级
      满分：4  分
23.  设在栈中，由顶向下已存放元素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  分
24.  某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（ ）的二叉树。
A. 空或只有一个结点
B. 高度等于其结点数
C. 任一结点无左孩子
D. 任一结点无右孩子
      满分：4  分
25.  完成堆排序的全过程需要 ( )个纪录大小的辅助空间。
A. 1
B. n
C. nlog2n
D. |nlog2n|
      满分：4  分