西工大17春《数据结构》在线作业（资料）

奥鹏在线作业

西工大17春《数据结构》在线作业




一、单选题（共 40 道试题，共 80 分。）

1.  设无向图G中顶点数为n，图G最多（ ）有条边。
A. n
B. n-1
C. n*(n-1)/2
D. n*(n-1)

2.  如果某图的邻接矩阵时对角线元素均为零的上三角矩阵，则此图是（ ）。
A. 有向完全图
B. 连通图
C. 强连通图
D. 有向无环图

3.  常采用下面几种方式解决散列法中出现的冲突问题（ ）。
A. 数字分析法、除余法、平均取中法
B. 数字分析法、除余法、线性探测法
C. 数字分析法、线性探测法、散列多重法
D. 线性探测法、散列多重法、链地址法

4.  在n个顶点的有向完全图中，边的总数为（ ）条。
A. n(n-1)/2
B. n(n-1)
C. n(n-2)
D. 2n

5.  有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主序，A11为第一个元素，其存储地址为1，每个元素占1个地址空间，则A85的地址为（ ）。
A. 13
B. 33
C. 18
D. 40

6.  在有n个结点的二叉链表中，值为空的链域个数为（ ）。
A. n-1
B. 2n-1
C. n+1
D. 2n+1

7.  串是一种特殊的线性表，其特殊性体现在（ ）。
A. 串中所含不同字母的个数
B. 串中所含字符的个数
C. 串中所含不同字符的个数
D. 串中所含非空格字符的个数

8.  已知广义表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))

9.  下面关于串的叙述中，哪一个是不正确的（ ）。
A. 串是字符的有限序列
B. 空串是由空格构成的串
C. 模式匹配是串的一种重要运算
D. 串既可以采用顺序存储，也可以采用链式存储

10.  在含n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为（ ）。
A. e
B. 2e

11.  希尔排序的增量序列必须是（ ）。
A. 递增的
B. 随机的
C. 递减的
D. 非递减的

12.  为了方便的在线性结构的数据中插入一个数据元素，则其数据结构宜采用（ ）。
A. 顺序存储
B. 链式存储
C. 索引存储
D. 散列存储

13.  折半查找法的时间复杂度是（ ）。
A. O(n*n)
B. O(n)
C. O(nlogn)
D. O(logn)

14.  对于哈希函数H（key）=key%13，被称为同义词的关键字是（ ）。
A. 35和41
B. 23和39
C. 15和44
D. 25和51

15.  设有两个串p和q，其中q是p的字串，求q在p中首次出现的位置的算法称为（ ）。
A. 求子串
B. 联接
C. 匹配
D. 求串长

16.  计算机识别、存储和加工处理的对象被统称为（ ）。
A. 数据
B. 数据元素
C. 数据结构
D. 数据类型

17.  散列表的平均查找长度（ ）。
A. 与处理冲突方法有关而与表的长度无关
B. 与处理冲突方法无关而与表的长度有关
C. 与处理冲突方法有关且与表的长度有关
D. 与处理冲突方法无关且与表的长度无关

18.  已知广义表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)))

19.  若串S=’syntax’，其字串的数目是（ ）。
A. 6
B. 21
C. 22
D. 7

20.  线索二叉树是一种（ ）结构。
A. 逻辑
B. 逻辑和存储
C. 物理
D. 线性

21.  设有5000个元素，希望用最快速度挑选出其中前10个最大的元素，在以下的排序方法中，采用那一种最好（ ）。
A. 快速排序
B. 堆排序
C. 归并排序
D. 基数排序和shell排序

22.  n个顶点的强连通图至少有（ ）条边。
A. n-1
B. n
C. 2n
D. n(n-1)

23.  对于单链表形式的队列，队空的条件是（ ）。
A. F=R=null
B. F=R
C. F≠null且R=null
D. R-F=1

24.  对表长为n的顺序表进行顺序查找，在查找概率相等的情况下，查找成功的平均查找长度为（ ）。
A. （n-1）/2
B. n/2
C. (n+1)/2
D. n

25.  算法指的是（ ）。
A. 计算机程序
B. 解决问题的计算方法
C. 排序算法
D. 解决问题的有限运算序列

26.  一个n*n的对称矩阵，如果以行或列为主序存入内存，则其容量为（ ）。
A. n*n
B. n*(n+1)/2
C. (n+1)*(n+1)/2
D. (n-1)*n/2

27.  二维数组a的每个元素是由6个字符组成的串，行下标i的范围从0～8，列下标j的范围从1～10。若a按行存放，元素a[8,5]的起始地址与当a按列存放时的元素（ ）的起始地址一致（每个字符占一个字节）。
A. a[8,5]
B. a[3,10]
C. a[5,8]
D. a[0,9]

28.  广义表运算式tail[((a,b),(c,d))]的结果为（ ）。
A. c,d
B. (c,d)
C. ((c,d))
D. d,c

29.  下列程序段的时间复杂度是（ ）。 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)

30.  深度为5的二叉树至多有结点数为（ ）。
A. 16
B. 30
C. 31
D. 32

31.  适于对动态查找表进行高效率查找的组织结构是（ ）。
A. 有序表
B. 分块有序表
C. 三叉排序树
D. 线性链表

32.  下列排序方法中，平均时间性能为O(nlogn)且空间性能最好的是（ ）。
A. 快速排序
B. 堆排序
C. 归并排序
D. 基数排序

33.  若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为（ ）。
A. 顺序存储结构
B. 链式存储结构
C. 索引存储结构
D. 散列存储结构

34.  在数据结构中，数据的逻辑结构可以分为（ ）。
A. 内部结构和外部结构
B. 线性结构和非线性结构
C. 紧凑结构和非紧凑结构
D. 动态结构和静态结构

35.  在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A的左孩子的平衡因子为-1，右孩子的平衡因子为0，则应作（ ）型调整以使其平衡。
A. LL
B. LR
C. RL
D. RR

36.  数组b[1..10，-2..6，2..8]以行优先的顺序存储，设第一个元素的首址是100，每个元素的长度为3。元素b[5,0,7]的存储首址为（ ）。
A. 900
B. 912
C. 910
D. 913

37.  向顺序栈中压入新元素时，习惯上应当（ ）。
A. 先移动栈顶指针，再存入元素
B. 先存入元素，再移动栈顶指针
C. 先后次序无关紧要
D. 同时进行

38.  对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则所有顶点邻接表中的结点总数为（ ）。
A. 2*n
B. 2*e
C. n
D. e

39.  如果T2是由有序树T转换而来的二叉树，那么T中结点的后序就是T2结点的（ ）。
A. 先序
B. 中序
C. 后序
D. 层序

40.  若待排序列已基本有序，要使它们完全有序，从关键码比较次数和移动次数考虑，应当使用的排序方法是（ ）。
A. 归并排序
B. 直接插入排序
C. 直接选择排序
D. 快速排序




西工大17春《数据结构》在线作业




二、判断题（共 10 道试题，共 20 分。）

1.  数据结构是指定义了一组按某些关系结合在一起的数组元素。（ ）
A. 错误
B. 正确

2.  队列中还有空余的空间，但元素不能进入队列的现象称为假溢出现象。（ ）
A. 错误
B. 正确

3.  线性表采用顺序存储表示时，必须占用一片连续的存储单元。（ ）
A. 错误
B. 正确

4.  设一数列的顺序为1,2,3,4,5,6，通过栈操作，可以得到顺序为3,2,5,6,4,1的输出序列。（ ）
A. 错误
B. 正确

5.  线性表中元素数量基本稳定，且很少进行插入和删除，要求以最快的速度存取线性表中的元素，此线性表宜采用链式存储结构。（ ）
A. 错误
B. 正确

6.  在单链表中只能由当前结点访问其后的任一结点，而在双向链表中，可以由当前结点出发访问链表中的任一结点。（ ）
A. 错误
B. 正确

7.  图的生成树是不唯一的，一个连通图的生成树是一个最小连通子图，n个顶点的生成树有n-1条边，最小代价生成树是唯一的。（ ）
A. 错误
B. 正确

8.  含零个字符的串称为空串。任何串中所含字符的个数为该串的长度。
A. 错误
B. 正确

9.  被计算机加工的数据元素不是孤立无关的，它们彼此之间一般存在着某种联系通常将数据元素间的这种联系关系称为结构。（ ）
A. 错误
B. 正确

10.  模式串P=’abaabcac’的next函数值序列为01122313。（ ）
A. 错误
B. 正确