西工大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.快速排序
35.一组记录的排序码为（25，48，16，35，79，82，23，40，36，72），其中含有5个长度为2的有序表，按归并排序的方法对该序列进行一趟归归并后的结构为（ ）。
A.16 25 35 48 23 40 79 82 36 72
B.16 25 35 48 79 82 23 36 40 72
C.16 25 48 35 79 82 23 36 40 72
D.16 25 35 48 79 23 36 40 72 82
36.一个n*n的对称矩阵，如果以行或列为主序存入内存，则其容量为（ ）。
A.n*n
B.n*(n+1)/2
C.(n+1)*(n+1)/2
D.(n-1)*n/2
37.在数据结构中，数据的逻辑结构可以分为（ ）。
A.内部结构和外部结构
B.线性结构和非线性结构
C.紧凑结构和非紧凑结构
D.动态结构和静态结构
38.计算机识别、存储和加工处理的对象被统称为（ ）。
A.数据
B.数据元素
C.数据结构
D.数据类型
39.若串S=’syntax’，其字串的数目是（ ）。
A.6
B.21
C.22
D.7
40.设有5000个元素，希望用最快速度挑选出其中前10个最大的元素，在以下的排序方法中，采用那一种最好（ ）。
A.快速排序
B.堆排序
C.归并排序
D.基数排序和shell排序
二、判断题 (共 10 道试题,共 20 分)
41.若一个栈的输出序列是1,2,3，…，n，输出序列的第一个元素是n，则第i个输出元素是n-i+1。（ ）
42.空格串是指由空格字符所组成的字符串，其长度等于空格个数。（ ）
43.模式串P=’abaabcac’的next函数值序列为01122313。（ ）
44.含零个字符的串称为空串。任何串中所含字符的个数为该串的长度。
45.线性表中元素数量基本稳定，且很少进行插入和删除，要求以最快的速度存取线性表中的元素，此线性表宜采用链式存储结构。（ ）
46.被计算机加工的数据元素不是孤立无关的，它们彼此之间一般存在着某种联系通常将数据元素间的这种联系关系称为结构。（ ）
47.队列中还有空余的空间，但元素不能进入队列的现象称为假溢出现象。（ ）
48.线性表采用顺序存储表示时，必须占用一片连续的存储单元。（ ）
49.数据结构是指定义了一组按某些关系结合在一起的数组元素。（ ）
50.POP（PUSH（S，A））的运算步骤是首先将元素A压入栈中，若栈S满，出现上溢现象，否则将元素A压入栈顶，且元素个数加1，然后做POP（S）运算，将栈顶元素弹出，且元素个数减一。（ ）
转载请注明：奥鹏作业之家 » 西工大20春《数据结构》在线作业【标准答案】