奥鹏作业网北交《数据结构（专）》在线作业一-0002
试卷总分:100 得分:100
一、单选题 (共 38 道试题,共 95 分)
1.若让元素1，2，3依次进栈，则出栈次序不可能出现（）种情况。
A.3，2，1
B.3，1，2
C.2，1，3
D.1，3，2
2.数组A中，每个元素A的长度为3个字节，行下标I 从1到8,列下标j从1到10，从首地址SA开始连续存放在存储器内，存放该数组至少需要的单元数为（ ）。
A.80
B.270
C.240
D.100
3.某二叉树结点的前序序列为E、A、C、B、D、G、F，中序遍历为A、B、C、D、E、F、G。 该二叉树结点的后序序列为 ( )。
A.E,G,F,A,C,D,B
B.E,G,A,C,D,F,B
C.B,D,C,F,A,G,E
D.B,D,C,A,F,G,E
4.对于含有n个顶点e条边的无向连通图，利用Prim算法生成最小代价生成树其时间复杂度为( )。
A.O(n*n)
B.O(ne)
C.O(log2n)
D.O(elog2e)
5.顺序查找法适合于存储结构为（）的线性表。
A.顺序存储或链接存储
B.索引存储
C.散列表
D.压缩存储
6.若从二叉树的任一节点出发到根的路径上所经过的节点序列按其关键字有序，则该二叉树是（ ）。
A.堆
B.哈夫曼树
C.二叉排序树
D.AVL树
7.具有2000个节点的二叉树，其高度至少为（）。
A.9
B.12
C.11
D.10
8.对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是（ ）。
A.n*n
B.(n-1)(n-1)
C.n-1
D.n
9.向二叉排序树中插入一个元素时，其时间复杂度大致为( )。
A.O(n*log2n)
B.O(n)
C.O(log以2为底的n)
D.O(1)
10.线索化二叉树中某结点D，没有左孩子的主要条件是（）。
A.D->ltag=1
B.D->ltag=0
C.D->Rchild=Null
D.D->Lchild=Null
11.设无向图的顶点个数为n，则该图最多有（）条边。
A.n-1
B.n(n-1)/2
C.n(n+1)/2
D.0
12.一个有顺序表有255个对象，采用顺序搜索法查表，平均搜索长度为（ ）。
A.255
B.128
C.127
D.126
13.判定一个顺序栈（最多元素为m个）为空的条件是（ ）。
A.top＝＝m
B.top＝＝0
C.top!＝m
D.top!＝0
14.在一个长度为n的顺序存储的线性表中，向第i个元素（1≤i≤n+1）之前插入一个新元素时，需要从前向后依次后移（ ）个元素。
A.n-i-1
B.n-i+1
C.n-i
D.i
15.如果一个树中，结点A有3个兄弟，而且B为A的双亲，则B的度为（ ）。
A.5
B.4
C.3
D.1
16.在线性表的散列存储中，若用m表示散列表的长度，n表示待散列存储的元素的个数，则装填因子a等于（）。
A.n/(n+m)
B.n/m
C.m/(n+m)
D.m/n
17.非空的循环单链表head的尾节点（由p所指向）满足（ ）。
A.p->next=head
B.p->next=NULL
C.p=head
D.p=NULL
18.对某二叉树进行前序遍历的结果为ABDEFC，中序遍历的结果为DBFEAC，则后序遍历的结果为（ ）。
A.DFEBCA
B.DBFEAC
C.BDFECA
D.BDEFAC
19.已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是（ ）。
A.decab
B.deabc
C.cedba
D.acbed
20.设单链表中指针p指着结点A，若要删除A之后的结点（若存在），则需要修改指针操作为（）。
A.p＝p->next->next
B.p＝p->next
C.p->next＝p->next->next
D.p->next＝p
21.在稀疏矩阵的带行指针向量的链接存储中，每个行单链表中的结点都具有相同的（）。
A.行号
B.地址
C.列号
D.元素值
22.计算机的算法是（ ）。
A.调度算法
B.计算方法
C.排序方法
D.对特定问题求解步骤的一种描述
23.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主的存储，a11为第一个元素，其存储地址为1，每个元素占1个地址空间，则a85的地址为（）。
A.40
B.33
C.18
D.13
24.队列操作的原则是（ ）。
A.后进先出
B.只能进行插入
C.只能进行删除
D.先进先出
25.某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（ ）的二叉树。
A.空或只有一个结点高度等于其结点数
B.任一结点无左孩子
C.任一结点无右孩子
26.如下叙述中正确的是（ ）。
A.空串就是空白串
B.串的长度必须大于零
C.串是一种特殊的线性表
D.串中元素只能是字母
27.n个顶点的连通图至少有（ ）条边。
A.n-1
B.n+1
C.n
D.0
28.下列关于栈的叙述正确的是（ ）。
A.栈是非线性结构
B.栈是一种树状结构
C.栈具有后进先出的特征
D.栈具有先进先出的特征
29.无向图的邻接矩阵是一个 ( )。
A.零矩阵
B.对角矩阵
C.对称矩阵
D.上三角矩阵
30.线性表的链接实现有利于（）运算。
A.读表元
B.查找
C.插入
D.定位
31.设有两个串（S1和S2），求S1在S2中首次出现的位置的运算称为（）。
A.连接
B.求子串
C.求串长
D.模式匹配
32.两个串相等的充分必要条件是（ ）。
A.以上条件都不正确
B.两个串的长度相等且对应位置的字符相同
C.两个串的长度相等
D.两个串对应位置的字符相等
33.设有向图有n个顶点和e条边，采用领接表作为其存储表示，在进行拓扑排序时，总的计算时间为（）。
A.O（nlog2e）
B.O（n+e）
C.O(n*n)
D.O(n*e)
34.设循环队列Q[1..N-1]的头尾指针为F，R，当插入元素时尾指针R加1，头指针F总是指在队列中第一个元素的前一个位置，则队列中元素计数为（）。
A.（R-F+N）%N
B.R-F
C.N-（R-F）
D.（F-R+N）%N
35.完成堆排序的全过程需要 ( )个纪录大小的辅助空间。
A.|nlog2n|
B.nlog2n
C.n
D.1
36.邻接表是图的一种（ ）。
A.顺序存储结构
B.链式存储结构
C.索引存储结构
D.列存储结构
37.假设一个有n个顶点和e条弧的有向图用邻接表表示,则删除与某个顶点vi相关的所有弧的时间复杂度是()。
A.O(n+e)
B.O(n*e)
C.O(n)
D.O(e)
38.图的深度优先遍历类似于二叉树的（ ）。
A.层次遍历
B.后序遍历
C.先序遍历
D.中序遍历
二、判断题 (共 2 道试题,共 5 分)
39.二维数组是其数组元素为线性表的线性表?
40.线性表的顺序存储表示优于链式存储表示?
