数据结构(第2版)-在线作业-1

数据结构(第2版)_在线作业_1一、单选题1.(5分)采用分块查找时，若线性表内共有625个数据元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的数据块，每块设定的数据元素总数为（

）最佳。

A.

625

B.

6

C.

25

D.

10纠错得分：

5知识点：

6.2查找算法展开解析2.(5分)堆栈通常采用的两种存储结构是（

）。

A.

线性与非线性结构

B.

链表与集合方式

C.

散列与索引方式

D.

顺序与连接方式纠错得分：

5知识点：

3.2堆栈展开解析3.(5分)对一个满二叉树，m个树叶，n个结点，深度为h，则他们之间的关系是（

）。

A.

n=2h-1

B.

n=h+m

C.

h+m=2n

D.

m=h-1纠错得分：

5知识点：

4.2二叉树展开解析4.(5分)一个栈的入栈序列是

a,b,c,d,e,

则不可能的出栈序列是（

）。

A.

dceab

B.

decba

C.

abcde

D.

edcba纠错得分：

5知识点：

3.2堆栈展开解析5.(5分)如果要求线性表既能支持较快地查找，又能适应数据动态变化的要求，你认为可以采用（

）查找方法。

A.

折半

B.

散列

C.

顺序

D.

分块纠错得分：

5知识点：

6.2查找算法展开解析6.(5分)在一个长度为n的顺序存储线性表中，删除值为x的元素，问进行比较和数据移动的总操作次数为（

）。

A.

n+1

B.

n

C.

n/2

D.

(n+1)/2纠错得分：

5知识点：

2.2顺序存储结构线性表展开解析7.(5分)给定三个算法频度函数：f(n)=100n3+n2+1000g(n)=25n3+4000n2h(n)=n1.01+1000nlg(n)指出算法时间复杂度数量级描述中错误的是（

）。

A.

h(n)=O(nlg(n))

B.

g(n)=O(n3)

C.

h(n)=O(n1.01)

D.

f(n)=O(n3)纠错得分：

5知识点：

1.3C程序与例题展开解析8.(5分)在一棵二叉树上第5层的结点数最多为（

）。

A.

16

B.

8

C.

32

D.

15纠错得分：

5知识点：

4.2二叉树展开解析9.(5分)假定一个链式的栈顶指针用top表示，每个结点的结构为

structNODE{intdata;structNODE*np;};

出栈时所进行的指针操作为（

）。

A.

top=top->np

B.

top->np=top

C.

top->np=top->np->np

D.

top=top->data纠错得分：

5知识点：

3.2堆栈展开解析10.(5分)已知有向图的邻接表如下：

根据有向图深度优先遍历原则，从定点V1出发，所得到的定点序列是（

）。

A.

1-4-3-5-2

B.

1-2-3-5-4

C.

1-2-3-4-5

D.

1-3-4-5-2纠错得分：

5知识点：

数据结构(第2版),5.2图的存储展开解析11.(5分)最小生成树指的是连通图中（

）。

A.

定点相对较少的生成树

B.

连通子图

C.

边数最少的生成树

D.

所有生成树中权值之和最低的生成树纠错得分：

5知识点：

5.1图的基本术语与定义展开解析12.(5分)一组记录关键字为{46,79,56,38,40,84}，应用快速排序法，以第一个关键字作为排序对象（枢轴），得到结果为（

）。

A.

40,38,46,79,56,84

B.

38,40,46,56,79,84

C.

40,38,46,56,79,84

D.

40,38,46,84,56,79纠错得分：

5知识点：

7.4快速排序展开解析13.(5分)如果待排序序列中两个数据元素具有相同的值在排序前后他们的相互位置发生颠倒，则称该排序算法是不稳定的。（

）和（

）就是不稳定的排序算法。

A.

shell排序，直接插入排序

B.

冒泡排序，归并排序

C.

直接插入排序，简单选择排序

D.

shell排序，简单选择排序纠错得分：

5知识点：

7排序展开解析14.(5分)消除递归不一定需要使用栈的说法是（

）的。

A.

正确

B.

错误纠错得分：

5知识点：

3.2堆栈展开解析15.(5分)Huffman树是带权路径长度最小的数，树中权重（

）的结点，距离根结点（

）。

A.

较高，较近

B.

较高，较远

C.

较低，较近纠错得分：

5知识点：

4.4Huffman树及应用展开解析16.(5分)在一个长度为n的顺序存储线性表中，向第i个元素（1<=i<=n+1）位置插入一个新元素时，需要从后向前依次后移（

）个元素。

A.

n-i-1

B.

i

C.

n-i+1

D.

n-i纠错得分：

5知识点：

2.2顺序存储结构线性表展开解析17.(5分)一个队列的入队序列为

1,2,3,4，则队列的输出序列是（

）。

A.

1234

B.

1432

C.

3241

D.

4321纠错得分：

5知识点：

3.1顺序存储结构队列展开解析18.(5分)采用邻接表存储的图的深度优先遍历算法，类似与二叉树的（

）。

A.

先序遍历

B.

后续遍历

C.

按层遍历

D.

中序遍历纠错得分：

5知识点：

数据结构(第2版),5.2图的存储展开解析19.(5分)在一个具有n个顶点的有向图中，若所有顶点的出度之和为S，则所有顶点的入度之和为（

）。

A.

S-1

B.

n

C.

S

D