西工大19春《数据结构》在线作业
试卷总分:100 得分:100
一、单选题(共40 道试题,共80 分)
1.设有一个空栈，栈顶指针为1000H（十六进制），现有一输入序列为1,2,3,4,5，经过PUSH，PUSH，POP，PUSH，POP，PUSH，PUSH后，输出序列是2,3，栈顶指针是（）。
A.1001H
B.1003H
C.1002H
D.1000H
答案:B
2.折半查找法的时间复杂度是（）。
A.O(n*n)
B.O(n)
C.O(nlogn)
D.O(logn)
答案:D
3.在n个顶点的有向完全图中，边的总数为（）条。
A.n(n-1)/2
B.n(n-1)
C.n(n-2)
D.2n
答案:B
4.若二叉树中度为2的结点有15个，度为1的结点有10个，该树有（）个结点。
A.25
B.30
C.31
D.41
答案:D
5.对有18个元素的有序表作二分查找，则查找A[3]的比较序列的下标依次为（）。
A.1,2,3
B.9,5,2,3
C.9,5,3
D.9,4,2,3
答案:D
6.对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则所有顶点邻接表中的结点总数为（）。
A.2*n
B.2*e
C.n
D.e
答案:B
7.在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A的左孩子的平衡因子为-1，右孩子的平衡因子为0，则应作（）型调整以使其平衡。
A.LL
B.LR
C.RL
D.RR
答案:B
8.表达式INDEX(‘DATASTRUCTURE’,’STR’)的运算结果是（）。
A.5
B.4
C.6
D.3
答案:A
9.对表长为n的顺序表进行顺序查找，在查找概率相等的情况下，查找成功的平均查找长度为（）。
A.（n-1）/2
B.n/2
C.(n+1)/2
D.n
答案:C
10.树形结构最适合用来描述（）。
A.有序的数据元素
B.无序的数据元素
C.数据元素之间的具有层次关系的数据
D.数据元素之间没有关系的数据
答案:C
11.下列排序方法中，平均时间性能为O(nlogn)且空间性能最好的是（）。
A.快速排序
B.堆排序
C.归并排序
D.基数排序
答案:B
12.具有65个结点的完全二叉树的高度为（）。（根的层次号为0）
A.8
B.7
C.6