西工大20春《数据结构》在线作业[答案]满分答案
西工大20春《数据结构》在线作业题目
试卷总分: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
2.折半查找法的时间复杂度是（ ）。
A.O(n*n)
B.O(n)
C.O(nlogn)
D.O(logn)
3.在n个顶点的有向完全图中，边的总数为（ ）条。
A.n(n-1)/2
B.n(n-1)
C.n(n-2)
D.2n
4.若二叉树中度为2的结点有15个，度为1的结点有10个，该树有（ ）个结点。
A.25
B.30
C.31
D.41
5.对有18个元素的有序表作二分查找，则查找A[3]的比较序列的下标依次为（ ）。
A.1,2,3
B.9,5,2,3
C.9,5,3
D.9,4,2,3
6.对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则所有顶点邻接表中的结点总数为（ ）。
A.2*n
B.2*e
C.n
D.e
7.在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A的左孩子的平衡因子为-1，右孩子的平衡因子为0，则应作（ ）型调整以使其平衡。
A.LL
B.LR
C.RL
D.RR
8.表达式INDEX(‘DATASTRUCTURE’,’STR’)的运算结果是（ ）。
A.5
B.4
C.6
D.3
9.对表长为n的顺序表进行顺序查找，在查找概率相等的情况下，查找成功的平均查找长度为（ ）。
A.（n-1）/2
B.n/2
C.(n+1)/2
D.n
10.树形结构最适合用来描述（ ）。
A.有序的数据元素
B.无序的数据元素
C.数据元素之间的具有层次关系的数据
D.数据元素之间没有关系的数据
11.下列排序方法中，平均时间性能为O(nlogn)且空间性能最好的是（ ）。
A.快速排序
B.堆排序
C.归并排序
D.基数排序
12.具有65个结点的完全二叉树的高度为（ ）。（根的层次号为0）
A.8
B.7
C.6
D.5
13.对于哈希函数H（key）=key%13，被称为同义词的关键字是（ ）。
A.35和41
B.23和39
C.15和44
D.25和51
14.在双向循环链表中，在p指针所指向的结点前插入一个指针q所指向的新结点其修改指针的操作是（ ）。（双向链表的结点结构是llink，data，rlink）
A.p->llink=q;q->rlink=p;p->llink->rlink=q;q->llink=q;
B.p->llink=q; p->llink->rlink=q; q ->rlink=p;q->llink= p->llink;
C.p->llink=q; q->llink= p->llink; p->llink->rlink=q;p->llink=q;
D.q->llink= p->llink;q->rlink=p; p->llink =q;p->llink=q;
15.一个无向连通图的生成树是含有该连通图的全部顶点的（ ）。
A.极小连通子图
B.极小子图
C.极大连通子图
D.极大子图
16.常采用下面几种方式解决散列法中出现的冲突问题（ ）。
A.数字分析法、除余法、平均取中法
B.数字分析法、除余法、线性探测法
C.数字分析法、线性探测法、散列多重法
D.线性探测法、散列多重法、链地址法
17.数组b[1..10，-2..6，2..8]以行优先的顺序存储，设第一个元素的首址是100，每个元素的长度为3。元素b[5,0,7]的存储首址为（ ）。
A.900
B.912
C.910
D.913
18.向顺序栈中压入新元素时，习惯上应当（ ）。
A.先移动栈顶指针，再存入元素
B.先存入元素，再移动栈顶指针
C.先后次序无关紧要
D.同时进行
19.有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主序，A11为第一个元素，其存储地址为1，每个元素占1个地址空间，则A85的地址为（ ）。
A.13
B.33
C.18
D.40
20.n个顶点的强连通图至少有（ ）条边。
A.n-1
B.n
C.2n
D.n(n-1)
21.深度为5的二叉树至多有结点数为（ ）。
A.16
B.30
C.31
D.32
22.算法指的是（ ）。
A.计算机程序
B.解决问题的计算方法
C.排序算法
D.解决问题的有限运算序列
23.下述排序算法中，稳定的是（ ）。
A.直接选择排序
B.表插入排序
C.快速排序
D.堆排序
24.下列程序段的时间复杂度是（ ）。 for(i=0;i<="" a[i][j]="0;" for(j="1;j<m;j++)">
A.O(n)
B.O(m+n+1)
C.O(m+n)
D.O(m*n)
25.如果T2是由有序树T转换而来的二叉树，那么T中结点的后序就是T2结点的（ ）。
A.先序
B.中序
C.后序
D.层序
26.一个广义表为(a,(a,b),d,e,((i,j),k))，则该广义表的长度和深度分别为（ ）。
A.5和3
B.5和4
C.4和3
D.4和4
27.已知广义表ls=(a,(b,c,d),e)，运用head和tail函数取出ls中原子b的运算是（ ）。
A.head(head(ls))
B.tail(head(ls))
C.head(head(tail(ls)))
D.head(tail(ls))
28.设无向图G中顶点数为n，图G最多（ ）有条边。
A.n
B.n-1
C.n*(n-1)/2
D.n*(n-1)
29.下面关于串的叙述中，哪一个是不正确的（ ）。
A.串是字符的有限序列
B.空串是由空格构成的串
C.模式匹配是串的一种重要运算
D.串既可以采用顺序存储，也可以采用链式存储
30.在有n个结点的二叉链表中，值为空的链域个数为（ ）。
A.n-1
B.2n-1
C.n+1
D.2n+1
31.希尔排序的增量序列必须是（ ）。
A.递增的
B.随机的
C.递减的
D.非递减的
32.若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为（ ）。
A.顺序存储结构
B.链式存储结构
C.索引存储结构
D.散列存储结构
33.已知广义表a=((a,b,c)，(d,e,f))，从a中取出原子e的运算是（ ）。
A.tail(head(a))
B.head(tail(a))
C.head(tail(tail(head(a))))
D.head(tail(tail(a)))
34.若待排序列已基本有序，要使它们完全有序，从关键码比较次数和移动次数考虑，应当使用的排序方法是（ ）。
A.归并排序
B.直接插入排序
C.直接选择排序
D.快速排序
