最新消息:可做奥鹏等各院校作业论文,答案请联系QQ/微信:18866732

东师数据结构20春在线作业2【标准答案】

数据结构20春在线作业2题目

试卷总分:100  得分:100

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

1.递归过程的实现需用到 ( )。

A.线性表

B.链表

C.栈

D.队列

 

2.在下列情况中,可称为二叉树的是 ( )。

A.每个结点至多有两棵子树的树

B.哈夫曼树

C.每个结点至多有两棵子树的有序树

D.每个结点只有一棵右子树

 

3.经过下列栈的操作后,GetTop(ST)的值是 ( )。InitStack(ST); push(ST,’a’); push(ST,’b’); pop(ST,x);

A.a

B.b

C.1

D.2

 

4.若要求尽可能快地对序列进行稳定的排序,则应选 () 。

A.快速排序

B.归并排序

C.起泡排序

D.希尔排序

 

5.一个算法应该是()。

A.程序

B.问题求解步骤的描述

C.要满足五个基本特性

D.A和C

 

6.判断线索二叉树中某结点p有左子女的条件是 ( )。

A.p ! = NULL

B.p->lchild ! = NULL

C.p->ltag = = 0

D.p->ltag = = 1

 

7.二叉树在中序线索化后,仍不能有效求解的问题是 ( )。

A.求指定结点的前序后继

B.求指定结点的中序前驱

C.求指定结点的中序后继

D.求指定结点的后序后继

 

8.顺序文件采用顺序结构实现文件的存储,对大型的顺序文件的少量修改,要求重新复制整个文件,代价很高,采用 () 的方法可降低所需的代价。

A.附加文件

B.按关键字大小排序

C.按记录输入先后排序

D.连续排序

 

9.广义表A=(a, b, ( c, d ) , (e,( f , g ) ) ),则式子head ( tail ( head ( tail ( tail ( A ) ) ) ) )的值为 ()。

A.( g )

B.( d )

C.c

D.d

 

10.( ) 的遍历仍需要栈的支持。

A.前序线索二叉树

B.中序线索二叉树

C.后序线索二叉树

D.前三种均需要

 

11.线索二叉树是一种 ( ) 结构。

A.逻辑

B.物理

C.逻辑和存储

D.线性

 

12.有一个100*90的稀疏矩阵,非零元素有10个,设每个整型数占2字节,则用三元组表示该矩阵时,所需的字节数是 () 。

A.60

B.66

C.18000

D.33

 

13.就排序算法所用的辅助空间而言,堆排序、快速排序、归并排序的关系是 () 。

A.堆排序<快速排序<归并排序

B.堆排序<归并排序<快速排序

C.堆排序>归并排序>快速排序

D.堆排序>快速排序>归并排序

 

14.下列说法不正确的是 ()。

A.图的遍历是从给定的源点出发每个顶点仅被访问一次

B.遍历的基本方法有两种:深度优先遍历和广度优先遍历

C.图的深度优先遍历不适用于有向图

D.图的深度优先遍历是一个递归过程

 

15.在一个图中,所有顶点的度数之和等于图的边数的几倍 ()。

A.1/2

B.1

C.2

D.4

 

16.在一个单链表中,已知q所指结点是p所指结点的前驱结点,若在p之前插入s所指结点,则执行 ( )。

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

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

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

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

 

17.在对n个元素的序列进行排序时,堆排序所需要的附加存储空间是 ()。

A.O(log2n )

B.O( 1 )

C.O(n )

D.O(nlog2n )

 

18.已知一个顺序存储的线性表,设每个结点占c个单元,若第一个结点的地址为LOC(a0),则第i个结点的地址为 ( )。

A.LOC(a0)+(i-1)*c

B.LOC(a0)+i*c

C.LOC(a0)-i*c

D.LOC(a0)+(i+1)*c

 

19.分块查找要求表中的结点 ()。

A.全部无序

B.块之间无序

C.全部有序

D.块之间有序

 

20.下面关于串的叙述中,哪一个是不正确的? ( )

A.串是字符的有限序列

B.空串是由空格构成的串

C.模式匹配是串的一种重要运算

D.串既可以采用顺序存储,也可以采用链式存储

 

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

21.二叉树按某种次序线索化后,任一结点均有指向其前序结点和后继结点的线索。

 

22.在执行某个排序算法过程中,出现了排序码朝着它最终排序位置相反的方向移动,则该算法是不稳定的。

 

23.非空的二叉树一定满足:某结点若有左子女,则其中序前驱一定没有右子女。

 

24.数组是同类型值的集合。

 

25.用链表 ( lchild-rchild表示法 ) 存储的包含n个结点的二叉树,结点的2n个指针域中有n + l 个空指针。

 

26.链表中的表头指针与表头结点起到相同的作用。

 

27.栈和队列的存储方式,既可以是顺序方式,又可以是链式方式。

 

28.一个有向图的邻接表和逆邻接表中结点的个数可能不等。

 

29.对大小均为n的有序表和无序表分别进行顺序查找,在等概率查找的情况下,对于查找成功,它们的平均查找长度是相同的,而对于查找失败,它们的平均查找长度是不同的。

 

30.任何无向图都存在生成树。

 

31.在完全二叉树中,若一个结点没有左子女,则它必是树叶。

 

32.链表中的表头结点仅起到标识的作用。

 

33.将一棵树转成二叉树,根结点没有右子树。

 

34.连通分量是无向图中的极大连通子图。

 

35.所谓取广义表的表尾就是返回广义表中最后一个元素。

 

36.需要借助于一个栈来实现DFS算法。

 

37.必须把一般的树转换成二叉树后才能进行存储。

 

38.对于插入、删除运算来说,链接存储结构一定优于顺序存储结构。

 

39.后序线索二叉树是不完善的,要对它进行遍历,还需要使用栈。

 

40.二维以上的数组其实是一种特殊的广义表。

转载请注明:奥鹏作业之家 » 东师数据结构20春在线作业2【标准答案】

发表我的评论
取消评论
表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址