吉林大学21秋学期《数据结构》在线作业二

试卷总分:100  得分:42

一、单选题 (共 10 道试题,共 40 分)

1.链栈与顺序栈相比，有一个比较明显得优点是( )

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

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

C.插入操作更加方便

D.删除操作更加方便

 泽学网（www.zexuewang.net）更多答案请添加：zexue66

2.带头结点的单链表head为空的判断条件是()。

A.head=NULL

B.head->next=NULL

C.head->next=head

D.head!=NULL

3.PUSH和POP命令常用于（ ）操作

A.队列

B.数组

C.栈

D.记录

4.深度为6的二叉树最多有( )个结点。

A.64

B.63

C.32

D.31

5.在无向图中，所有顶点的度数之和是所有边数的( )倍。

A.0.5

B.1

C.2

D.4

6.线性表是具有n个（ ）的有限序列

A.表元素

B.字符

C.数据元素

D.数据项

7.含n个顶点的连通图中的任意一条简单路径，其长度不可能超过( )。

A.1

B.n/2

C.n-1

D.n

8.在单链表中，删除p所指结点的直接后继的操作是( )

A.p->next=p->next->next;

B.p=p->next;p->next=p->next->next;

C.p->next=p->next;

D.p=p->next->next;

9.设深度为k的二叉树上只有度为0和度为2的结点，则这类二叉树上所含结点总数最少( )个。

A.k+1

B.2k

C.2k-1

D.2k+1

10.通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（ ）

A.数据元素具有同一特点

B.不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致

C.每个数据元素都一样

D.数据元素所包含的数据项的个数要相等

二、多选题 (共 5 道试题,共 20 分)

11.图的存储结构有（）

A.邻接矩阵

B.邻接表

C.数组表示法

D.十字链表

12.属于插入排序的排序方法有（）

A.直接插入排序

B.对半插入排序

C.渐减增量排序

D.冒泡排序

13.类string中包含的串运算有（ ）

A.Find()

B.Substr()

C.Insert()

D.Length()

14.以下属于操作受限的顺序表是（ ）

A.栈

B.队列

C.单链表

D.树

15.二叉树的遍历方式有（）

A.先根遍历

B.中根遍历

C.后根遍历

D.深度遍历

三、判断题 (共 10 道试题,共 40 分)

16.对于前序遍历和中序遍历结果相同的二叉树为所有结点只有右孩子的二叉树

17.具有n（n>0）个顶点的无向图最多含有n(n-1)/2条边

18.字符串是一种线性表，其特殊性表现在它的数据元素是一个字符

19.从未排序的序列中依次取出一个元素与已排序序列中的元素进行比较，然后将其放在已排序序列的合适位置上，该排序方法称为插入排序

20.在一颗非空二叉树中，叶子节点的总数比度为2的节点总数多1个

21.设栈的输入序列是1,2,3,4，则1,4,3,2不可能是其出栈序列

22.任何一棵二叉树中至少有一个结点的度为2。( )

23.由权值为9,2,5,7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度44

24.在第一趟排序之后，一定能把数据表中最大或最小元素放在其最终的排序算法是冒泡排序

25.在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法是归并排序