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

李老师

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


一、单选题（共 25 道试题，共 100 分。）V 1.  设字符串S1='ABCDEFG'，S2='PQRST'，则运算S=CONCAT（SUB（S1，2，LENGTH（S2）），SUB（S1，LENGTH（S2），2））后结果为（ ）。
A. BCQR'
B. 'BCDEF'
C. 'BCDEFG'
D. 'BCDEFEF'
      满分：4  分
2.  在一个长度为n的顺序存储的线性表中，向第i个元素（1≤i≤n+1）之前插入一个新元素时，需要从后向前依次后移（ ）个元素。
A. n-i
B. n-i+1
C. n-i-1
D. i
      满分：4  分
3.  以下说法正确的是 ( )
A. 因链栈本身没有容量限制,故在用户内存空间的范围内不会出现栈满情况
B. 因顺序栈本身没有容量限制,故在用户内存空间的范围内不会出现栈满情况
C. 对于链栈而言,在栈满状态下,如果此时再作进栈运算，则会发生“上溢”
D. 对于顺序栈而言在栈满状态下如果此时再作迸栈运算，则会发生“下溢”。
      满分：4  分
4.  在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行（ ）。
A. HL=p;p->next=HL;
B. p->next=HL;HL=p;
C. p->next=HL;p=HL;
D. p->next=HL->next;HL->next=p;
      满分：4  分
5.  顺序队列的人队操作应为 ( )
A. sq.rear=sq.rear+1 sq.data[sq.rear]=x
B. sq.data[sq.rear]=x sq.rear=sq.rear+1
C. sq.rear=(sq.rear+1)% maxsize; sq.data[sq.rear]=x
D. sq.data[sqrear]=x sq.rear=(sq.rear+1)% maxsize
      满分：4  分
6.  设F是一个森林，B是由F转换得到的二叉树，F中有n个非叶结点，则B中右指针域为空的结点有（）个。
A. n-1
B. n
C. n+1
D. n+2
      满分：4  分
7.  以下时间复杂性不是O(n^2)的排序方法是
A. 直接插入排序
B. 二路归并排序
C. 冒泡排序
D. 直接选择排序
      满分：4  分
8.  以下说法正确的是（ ）
A. 顺序存储方式的优点是存储密度大、且插入、删除运算效率高
B. 链表的每个结点中都恰好包含一个指针
C. 线性表的顺序存储结构优于链式存储结构
D. 顺序存储结构属于静态结构，链式结构属于动态结构
      满分：4  分
9.  二分查找和二叉排序树的时间性能（ ）。
A. 始终相同
B. 始终不相同
C. 根据情况确定
D. 以上说法均不正确
      满分：4  分
10.  某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（ ）的二叉树。
A. 空或只有一个结点
B. 高度等于其结点数
C. 任一结点无左孩子
D. 任一结点无右孩子
      满分：4  分
11.  一个有顺序表有255个对象，采用顺序搜索法查表，平均搜索长度为（ ）。
A. 128
B. 127
C. 126
D. 255
      满分：4  分
12.  在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为()。
A. e
B. 2e
C. n的平方－e
D. n的平方－2e
      满分：4  分
13.  堆排序在最坏情况下，其时间复杂性为（ 　）
A. O(nlog2n)
B. O(n^2)
C. O(log2n^2)
D. O(log2n)
      满分：4  分
14.  如果要求一个线性表既能较快地查找,又能适应动态变化的要求,可以采用（）查找方法。
A. 分块
B. 顺序
C. 二分
D. 散列
      满分：4  分
15.  
对于含有n个顶点e条边的无向连通图，利用Prim算法生成最小代价生成树其时间复杂度为( )。

A. O(log2n)
B. O(n2)
C. O(ne)
D. O(elog2e)
      满分：4  分
16.  如果从无向的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是（ ）。
A. 完全图
B. 连通图
C. 有回路
D. 一棵树
      满分：4  分
17.  设有一个10阶的对称矩阵A[10][10]，采用压缩存储方式按行将矩阵中下三角部分的元素存入一维数组B[ ]中，A[0][0]存入B[0]中，则A[8][5]在B[ ]中（ ）位置。
A. 32
B. 33
C. 41
D. 65
      满分：4  分
18.  顺序表是线性表的
A. 链式存储结构
B. 顺序存储结构
C. 索引存储结构
D. 散列存储结构
      满分：4  分
19.  二叉树上叶结点数等于（）。
A. 分支结点数加1
B. 单分支结点数加1
C. 双分支结点数加1
D. 双分支结点数减1
      满分：4  分
20.  在稀疏矩阵的带行指针向量的链接存储中，每个行单链表中的结点都具有相同的（）。
A. 行号
B. 列号
C. 元素值
D. 地址
      满分：4  分
21.  下列有关图遍历的说法中不正确的是（ ）。
A. 连通图的深度优先搜索是个递增过程
B. 图的广度优先搜索中邻接点的寻找具有“先进先出”的特征
C. 非连通图不能用深度优先搜索法
D. 图的遍历要求每个顶点仅被访问一次
      满分：4  分
22.  关于逻辑结构，以下说法错误的是
A. 逻辑结构与数据元素本身的形成、内容无关
B. 逻辑结构与数据元素的相对位置有关
C. 逻辑结构与所含结点个数无关
D. 一些表面上很不相同的数据可以有相同的逻辑结构
      满分：4  分
23.  采用二分查找方法查找长度为n的线性表时,每个元素的平均查找长度为（）
A. O(n2)
B. O(log2n)
C. O(n)
D. O(log2n)
      满分：4  分
24.  邻接表是图的一种（ ）。
A. 顺序存储结构
B. 链式存储结构
C. 索引存储结构
D. 列存储结构
      满分：4  分
25.  深度为5的二叉树至多有（ ）个节点。
A. 16
B. 32
C. 31
D. 10
      满分：4  分