北京交通大学《数据结构（专）》在线作业一答卷

北交《数据结构（专）》在线作业一-0005

试卷总分：100得分：100

一、单选题（共38道试题，共95分）

1.向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要

移动（）个元素。

A.8

B.63.5

C.64

D.7

答案:B

2.设有1000个元素，用折半查找时，最大比较次数是（）。

A.1

B.7

C.10

D.25

答案:C

3.对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是（）。

A.n

B.（n-1）（n-1）

C.n-l

D.n*n

答案:D

4.链表不具有的特点是（）。

A.不必事先估计存储空间

B.可随机访问任一元素

C.插入删除不需要移动元素

D.所需空间与线性表长度成正比

答案:B

5.具有2000个节点的二叉树，其高度至少为（）。

A.9

B.10

C.11

D.12

答案:C

6.具有65个结点的完全二叉树其深度为（）。

A.8

B.7

C.6

D.5

答案:B

7.设在栈中，由顶向下已存放元素c、b、a,在第4个元素d入栈之前，栈中元素

可以出栈，试问d入栈前后，不可能的出栈序列是（）。

A.dcba

B.cbda

C.cadb

D.cdba

答案:c

8.广义表（（a）,a）的表头是（）。

A.a

B.b

C.（a）

D.（（a））

答案:C

9.若待排序对象序列在排序前已按其排序码递增顺序排序，则采用（）方法比较

次数最少。

A.直接插入排序

B.快速排序

C.归并排序

D.直接选择排序

答案:A

10.队列操作的原则是（

A.先进先出

B.后进先出

C.只能进行插入

D.只能进行删除

答案:A

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

A.e

B.2e

C.n*n—e

D.n*n—2e

答案:D

12.队列的删除操作是在（）进行。

A.队首

B.队尾

C.队前

D.队后

答案:A

13.在有n个叶子结点的哈夫曼树中，其结点总数为（）。

A.不确定

B.2n

C.2n+l

D.2n-l

答案：D

14.设一数列的顺序为1,2,3,4,5,6,通过栈结构不可能排成的顺序数列为（）。

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

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

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

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

答案:B

15.n个顶点的连通图至少有（）条边。

A.n-l

B.n

C.n+1

D.0

答案:A

16.采用顺序查找方法查找长度为n的线性表时，每个元素的平均长度为（）。

A.n

B.n/2

C.（n+l）/2

D.（n-l）/2

答案:C

17.在一个长度为n的顺序存储的线性表中，向第i个元素（lWiWn+1）之前插

入一个新元素时，需要从前向后依次后移（）个元素。

A.n-i

B.n-i+1

C.n-i-1

D.i

答案:B

18.设有50行60列的二维数组A[50][60],其元素长度为4字节,按行优先顺序

存储，基地址为200,则元素A[18][25]的存储地址为（）。

A.3700

B.4376

C.3900

D.4620

答案:D

19.若从二叉树的任一节点出发到根的路径上所经过的节点序列按其关键字有序,

则该二叉树是（

A.二叉排序树

B.哈夫曼树

C.堆

D.AVL树

答案:C

20.算法分析的目的是（）。

A.找出数据结构的合理性

B.研究算法中的输入和输出的关系

C.分析算法的效率以求改进

D.分析算法的易读性和文档性

答案:C

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

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

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

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

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

答案:B

22.带头节点的单链表head为空的判定条件（）。

A.head=NULL

B.head->next=NULL

C.head->next=head

D.head!=head

答案:B

23.深度为5的二叉树至多有（）个节点。

A.16

B.32

C.31

D.10

答案:C

24.串的长度是（）o

A.串中不同字符的个数

B.串中不同字母的个数

C.串中所含字符的个数且字符个数大于0

D.串中所含字符的个数

答案:D

25.向二叉排序树中插入一个元素时，其时间复杂度大致为()。

A.O(log以2为底的n)

B.O(n)

C.O(l)

D.0(n*log2n)

答案:A

26.算法的时间复杂度是指()。

A.执行算法程序所需要的时间

B.算法程序的长度

C.算法执行过程中所需要的基本运算次数

D.算法程序中的指令条数

答案:C

27.由权值分别为3,6,7,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为

()。

A.23

B.51

C.53

D.74

答案:B

28.每次从无序表中取出一个元素，把它插入到有序表中的适当位置，此种排序方

法叫做()排序.

A.插入

B.交换

C.选择

D.归并

答案:A

29.顺序查找法适合于存储结构为()的线性表。

A.散列表

B.顺序存储或链接存储

C.压缩存储

D.索引存储

答案:B

30.如果待排序序列中两个数据元素具有相同的值，在排序后它们的位置发生颠倒,

则称该排序是不稳定的。下列选项中，()就是不稳定的排序方法。

A.起泡排序

B.归并排序

C.直接插入法排序

D.简单选择排序

答案:D

31.若某线性表中最常用的操作是取第I个元素和找第I个元素的前趋元素，则采

用（）存储方式最节省时间。

A.顺序表

B.单链表

C.双链表

D.单循环链表

答案:A

32.若由森林转化得到的二叉树是非空的二叉树，则二叉树形状是（）。

A.根结点无右子树的二叉树

B.根结点无左子树的二叉树

C.根结点可能有左二叉树和右二叉树

D.各结点只有一个儿子的二叉树

答案:C

33.非空的循环单链表head的尾节点（由p所指向）满足（）。

A.p->next=NULL

B.p=NULL

C.p->next=head

D.p=head

答案:C

34.如果一个树中，结点A有3个兄弟，而且B为A的双亲，则B的度为（）。

A.1

B.3

C.4

D.5

答案:C

35.设单链表中指针p指着结点A,若要删除A之后的结点（若存在），则需要修改

指针操作为（）。

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

B.p=p->next

C.p=p->next->next

D.p->next=p

答案:A

36.在稀疏矩阵的带行指针向量的链接存储中，每个行单链表中的结点都具有相同

的（）。

A.行号

B.列号

C.元素值

D.地址

答案:A

37.以下数据结构中不属于线性数据结构的是()。

A.线性表

B.队列

C.二叉树

D.栈

答案:C

38.设有向图有n个顶点和e条边，采用领接表作为其存储表示，在进行拓扑排序

时，