2015春北京航空航天大学《算法与数据结构》在线作业三

北航《算法与数据结构》在线作业三单选题
一、单选题（共25道试题，共100分。）1.在一棵二叉树中，第4层上的结点数最多为（）。
A.8
B.15
C.16
D.31
-----选择：A
2.非空的循环单链表head的尾节点（由p所指向）满足（）。
A.p-next=NULL
B.p=NULL
C.p-next=head
D.p=head
-----选择：C
3.堆排序在最坏情况下，其时间复杂性为（）
A.O(nlog2n)
B.O(n2)
C.O(log2n2)
D.O(log2n)
-----选择：A
4.采用分块查找时,若线性表中共有625个元素,查找每个元素的概率相同,假设采用顺序查找来确定结点所在的块时,每块应分（）个结点最佳
A.10
B.25
C.6
D.625
-----选择：B
5.队列操作的原则是（）。
A.先进先出
B.后进先出
C.只能进行插入
D.只能进行删除
-----选择：A
6.设字符串S1='ABCDEFG'，S2='PQRST'，则运算S=CONCAT（SUB（S1，2，LENGTH（S2）），SUB（S1，LENGTH（S2），2））后结果为（）。
A.BCQR'
B.'BCDEF'
C.'BCDEFG'
D.'BCDEFEF'
-----选择：D
7.算法的时间复杂度，都要以通过算法中执行频度最高的语句的执行次数来确定这种观点
A.完全正确
B.完全错误
C.视情况而定
D.以上说法均不正确
-----选择：B
8.在索引顺序表中查找一个元素，可用的且最快的方法是（）
A.用顺序查找法确定元素所在块，再用顺序查找法在相应块中查找
B.用顺序查找法确定元素所在块，再用二分查找法在相应块中查找
C.用二分查找法确定元素所在块，再用顺序查找法在相应块中查找
D.用二分查找法确定元素所在块，再用二分查找法在相应块中查找
-----选择：C
9.对有n个记录的有序表采用二分查找，其平均查找长度的量级为（）
A.O(log2n)
B.O(nlog2n)
C.O(n)
D.O(n2)
-----选择：A
10.以下说法正确的是()
A.因链栈本身没有容量限制,故在用户内存空间的范围内不会出现栈满情况
B.因顺序栈本身没有容量限制,故在用户内存空间的范围内不会出现栈满情况
C.对于链栈而言,在栈满状态下,如果此时再作进栈运算，则会发生“上溢”
D.对于顺序栈而言在栈满状态下如果此时再作迸栈运算，则会发生“下溢”。
-----选择：A
11.设有两个串（S1和S2），求S1在S2中首次出现的位置的运算称为（）。
A.连接
B.模式匹配
C.求子串
D.求串长
-----选择：B
12.设有向图有n个顶点和e条边，采用领接表作为其存储表示，在进行拓扑排序时，总的计算时间为（）。
A.O（nloge）
B.O（n+e）
C.O(n*e)
D.O(n的平方)
-----选择：B
13.下列图的说法中正确的是（）。
A.一个具有n个顶点的无向完全图的边数为n(n-1)
B.连通图的生成树是该图的一个极大连通子图
C.图的广度优先搜索是一个递归过程
D.在非连通图的遍历过程中，每调用一次深度优先搜索算法都得到该图的一个连通分量
-----选择：C
14.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主的存储，a11为第一个元素，其存储地址为1，每个元素占1个地址空间，则a85的地址为（）。
A.13
B.18
C.33
D.40
-----选择：C