西交《数据结构》在线作业-00001

试卷总分:100  得分:100

一、单选题 (共 30 道试题,共 60 分)

1.由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）

A.24

B.71

C.48

D.53

答案:

2.由两个栈共享一个向量空间的好处是：（）

A.减少存取时间，降低下溢发生的机率

B.节省存储空间，降低上溢发生的机率

C.减少存取时间，降低上溢发生的机率

D.节省存储空间，降低下溢发生的机率

答案:

3.数据的基本单位（ ）。

A.数据结构

B.数据元素

C.数据项

D.文件

答案:

4.设一组初始记录关键字序列为(60，80，55，40，42，85)，则以第一个关键字45为基准而得到的一趟快速排序结果是（ ）。

A.40，42，60，55，80，85

B.42，45，55，60，85，80

C.42，40，55，60，80，85

D.42，40，60，85，55，80

答案:

5.下列各种排序算法中平均时间复杂度为O（n）是（）。

A.快速排序

B.堆排序

C.归并排序

D.冒泡排序

答案:

6.对于一些特殊矩阵，采用压缩存储的目的是（ ）。

A.使表达变得更简单

B.对矩阵元素的存取变得简单

C.去掉矩阵中的多于元素

D.减少不必要的存储空间

答案:

7.循环队列占用的空间（ ）。

A.必须连续

B.不必连续

C.不能连续

D.可以不连续

答案:

8.链式栈与顺序栈相比，一个比较明显的优点是（）

A.插入操作更加方便

B.通常不会出现栈满的情况

C.不会出现栈空的情况

D.删除操作更加方便

答案:

9.在二叉排序树中插入一个结点的时间复杂度为（）。

A.O(1)

B.O(n)

C.O(log2n)

D.O(n)

答案:

10.设某哈夫曼树中有199个结点，则该哈夫曼树中有（）个叶子结点。

A.99

B.100

C.101

D.102

答案:

11.设给定权值总数有n 个，其哈夫曼树的结点总数为( )

A.不确定

B.2n

C.2n+1

D.2n-1

答案:

12.设输入序列1、2、3、?、n经过栈作用后，输出序列中的第一个元素是n，则输出序列中的第i个输出元素是（）。

A.n-i

B.n-1-i

C.n+l-i

D.不能确定

答案:

13.设二叉排序树上有n个结点，则在二叉排序树上查找结点的平均时间复杂度为（）。

A.O(n)

B.O(n^2)

C.O(nlog2n)

D.O(log2n)

答案:

14.如果要求频繁的对线性表进行插入和删除操作,则线性表应该采用( )存储结构。

A.散列

B.顺序

C.链式

D.任意

答案:

15.下列说法中，正确的是（ ）。

A.度为2的树是二叉树

B.度为2的有序树是二叉树

C.子树有严格的左、右之分的树是二叉树

D.子树有严格的左、右之分，且度不超过2的树是二叉树

答案:

16.两个字符串相等的条件是( )。

A.两串的长度相等；

B.两串包含的字符相同；

C.两串的长度相等，并且两串包含的字符相同；

D.两串的长度相等，并且对应位置上的字符相同。

答案:

17.设有100个数据元素，采用折半搜索时，最大比较次数为（）

A.6

B.7

C.8

D.10

答案:

18.设有5000个待排序的记录关键字，如果需要用最快的方法选出其中最小的10个记录关键字，则用下列（）方法可以达到此目的。

A.快速排序

B.堆排序

C.归并排序

D.插入排序

答案:

19.建立一个长度为n的有序单链表的时间复杂度为（）

A.O(n)

B.O(1)

C.O(n)

D.O(log2n)

答案:

20.下面关于线性表的叙述错误的是（）。

A.线性表采用顺序存储必须占用一片连续的存储空间

B.线性表采用链式存储不必占用一片连续的存储空间

C.线性表采用链式存储便于插入和删除操作的实现

D.线性表采用顺序存储便于插入和删除操作的实现

答案:

21.线性表采用链式存储时，结点的存储地址（）

A.必须是不连续的

B.连续与否均可

C.必须是连续的

D.和头结点的存储地址相连续

答案:

22.下列存储形式中，（）不是树的存储形式

A.双亲表示法

B.左子女右兄弟表示法

C.广义表表示法

D.顺序表示法

答案:

23.有n个顶点的无向图的邻接矩阵是用（ ）数组存储。

A.一维

B.n行n列

C.任意行n列

D.n行任意列

答案:

24.若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用( )遍历方法最合适。

A.前序

B.中序

C.后序

D.按层次

答案:

25.设输入序列为1、2、3、4、5、6，则通过栈的作用后可以得到的输出序列为（）。

A.5，3，4，6，1，2

B.3，2，5，6，4，1

C.3，1，2，5，4，6

D.1，5，4，6，2，3

答案:

26.在一棵具有5层的满二叉树中结点数为（）

A.31

B.32

C.33

D.16

答案:

27.若进队的序列为A、B、C、D，则出队的序列是（ ）。

A.C、D、A

B.C、B、D

C.B、C、D

D.B、D、A

答案:

28.线性链表各结点之间的地址( )

A.必须连续

B.一定不连续

C.部分地址必须连续

D.连续与否无所谓

答案:

29.设某棵二叉树中只有度数为0和度数为2的结点且度数为0的结点数为n，则这棵二叉中共有（）个结点。

A.2n

B.n+l

C.2n-1

D.2n+l

答案:

30.设一组初始记录关键字序列为(13，18，24，35，47，50，62，83，90，115，134),则利用二分法查找关键字90需要比较的关键字个数为（）。

A.1

B.2

C.3

D.4

答案:

二、判断题 (共 20 道试题,共 40 分)

31.满二叉树一定是完全二叉树,完全二叉树不一定是满二叉树。

答案: 

32.一般树和二叉树的结点数目都可以为0。 ( )

答案: 

33.在使用后缀表表示实现计算器时用到一个栈的实例，其作用是暂存运算对象。

答案: 

34.堆是完全二叉树，完全二叉树不一定是堆。

答案: 

35.线性表中的所有元素都有一个前驱元素和后继元素。（ ）

答案: 

36.算法与程序没有区别。 ( )

答案: 

37.在B+树中查找和在B-树中查找的过程完全相同。 ( )

答案: 

38.从本质上看,文件是一种非线性结构。

答案: 

39.在线性表的链式存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。（ ）

答案: 

40.如果某种排序算法不稳定，则该排序方法就没有实用价值。（ ）

答案: 

41.栈和队列都是限制存取点的线性结构。

答案: 

42.设某堆中有n个结点，则在该堆中插入一个新结点的时间复杂度为O(log2n)。（ ）

答案: 

43.有向图的邻接表和逆邻接表中表结点的个数不一定相等。

答案: 

44.先序遍历一棵二叉排序树得到的结点序列不一定是有序的序列。

答案: 

45.如果两个关键字的值不等但哈希函数值相等，则称这两个关键字为同义词。

答案: 

46.数据元素是数据的最小单位。（ ）

答案: 

47.除了插入和删除操作之外，数组的操作还包括存取、修改、检索和排序。( )

答案: 

48.当向二叉排序树中插入一个结点，则该结点一定成为叶子结点。（ ）

答案: 

49.在循环队列中，若尾指针rear大于头指针front，其元素个数为rear-front。（ ）

答案: 

50.线性表的顺序存储结构比链式存储结构更好。

答案:

奥鹏，国开，广开，电大在线，各省平台，新疆一体化等平台学习
详情请咨询QQ：3494317897  微信：aopy98