吉大21秋学期《数据结构》在线作业二[答案]

吉大21秋学期《数据结构》在线作业二[答案]答案

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

试卷总分:100  得分:42

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

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

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

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

C.插入操作更加方便

D.删除操作更加方便

正确答案:-----

 

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.数据元素所包含的数据项的个数要相等

正确答案:-----

 

吉大21秋学期《数据结构》在线作业二[答案]多选题答案

二、多选题 (共 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条边

 

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

 

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

 

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

 

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

 

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

 

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

 

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

吉大21秋学期《数据结构》在线作业二[答案]历年参考题目如下：

《数据结构（本科）》21年6月作业考核

试卷总分:100  得分:100

一、单选题 (共 25 道试题,共 100 分)

1.设有一个10阶的对称矩阵A[10][10]，采用压缩存储方式按行将矩阵中下三角部分的元素存入一维数组B[ ]A[0][0]存入B[0]中，则A[8][5]在B[ ]中（ )

A.32

B.33

C.41

D.65

 

2.下列存储形式中不是树的存储形式( )

A.双亲表示法

B.孩子兄弟表示法

C.顺序表示法

D.广义表表示法

 

3.设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front值为（ ）

A.front=front+1

B.front=(front+1)%(m-1)

C.front=(front-1)%m

D.front=(front+1)%m

 

4.对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。这样的排序方法是( )

A.直接选择排序

B.直接插入排序

C.快速排序

D.起泡排序

 

5.一个二叉树按顺序方式存储在如下的一个维数组中,0 1 2 3 4 5 6 7 8 9 10 11 12 13 14A B C D E F G H I J则结点E在二叉树的第（ ）层。

A.1

B.2

C.3

D.4

 

6.对有14个数据元素的有序表R[14]进行折半搜索，搜索到R[3]的关键码等于给定值，此时元素比较顺序依次为( )

A.R[0]，R[1]，R[2]，R[3]

B.R[0]，R[13]，R[2]，R[3]

C.R[6]，R[2]，R[4]，R[3]

D.R[6]，R[4]，R[2]，R[3]

 

7.若让元素1，2，3依次进栈，则出栈次序不可能出现种情况( )

A.3，2，1

B.2，1，3

C.3，1，2

D.1，3，2

 

8.一个关键字序列为{46，79，56，38，40，84}，采用快速排序以位于最左位置的元素为基准而得到的第一次划分结果为（ )

A.{38，46，79，56，40，84}

B.{38，79，56，46，40，84}

C.{40，38，46，56，79，84}

D.{38，46，56，79，40，84}

 

9.线性表是一个具有n个（ ）的有限序列。

A.表元素

B.字符

C.数据元素

D.数据项

 

10.设某算法的问题规模函数f(n)=300n2+8000n+900，则它的渐进时间复杂度为（ )

A.O(n3)

B.O(n2)

C.O(n)

D.O(1)

 

11.线性链表不具有的特点是( )

A.随机访问

B.不必事先估计所需存储空间大小

C.插入与删除时不必移动元素

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

 

12.对5个不同的数据元素进行直接插入排序，最多需要进行（ ）次比较

A.8

B.10

C.15

D.25

 

13.依次在初始为空的队列中插入元素X，Y，Z，W以后，紧接着作了两次删除操作，此时的队头元素是（ )

A.X

B.Y

C.Z

D.W

 

14.设有向图有n个顶点和e条边，采用领接表作为其存储表示，在进行拓扑排序时，总的计算时间为( )

A.O（nlog2e）

B.O（n+e）

C.O(ne)

D.O(n2)

 

15.在一个单链表HL中，若要在指针q所指结点的后面插入一个由指针P所指向的结点，则执行( )

A.q—＞next＝p—＞next；p—＞next＝q

B.p—＞next＝q—＞next；q＝p

C.q—＞next＝p—＞next；p—＞next＝q

D.p—＞next＝q—＞next；q—＞next＝p

 

16.若采用邻接矩阵法存储一个N个顶点的无向图，则该邻接矩阵是一个( )

A.队头元素的前一个位置

B.队头元素的后一个位置

C.队头元素位置

D.队尾元素的前一位置

 

17.n个顶点的有向完全图中含有向边的数目最多为（ )

A.n-1

B.n

C.n(n-1)/2

D.n(n-1)

 

18.深度为8的二叉树至多有（ ）个结点

A.7

B.15

C.127

D.255

 

19.用链表表示线性表的优点是( )

A.便于随机存取

B.花费的存储空间比顺序表少

C.便于插入与删除

D.数据元素的物理顺序与逻辑顺序相同

 

20.设F是一个森林，B是由F转换得到的二叉树，F中有n个非叶结点，则B中右指针域为空的结点有（ )

A.n-1

B.n

C.n+1

D.n+2

 

21.设串sl=″Data Structures with Java″,s2=″it″，则子串定位函数index(s1,s2)的值为( )

A.15

B.16

C.17

D.18

 

22.对某二叉树进行前序遍历的结果为ABDEFC，中序遍历的结果为DBFEAC，则后序遍历的结果为（ ）

A.DBFEAC

B.DFEBCA

C.BDFECA

D.BDEFAC

 

23.假设一个有n个顶点和e条弧的有向图用邻接表表示,则删除与某个顶点vi相关的所有弧的时间复杂度是（ )

A.O(n)

B.O(e)

C.O(n+e)

D.O(n×e)

 

24.AVL树是一种平衡的二叉排序树，树中任一结点的( )

A.左、右子树的高度均相同

B.左、右子树高度差的绝对值不超过1

C.左子树的高度均大于右子树的高度

D.左子树的高度均小于右子树的高度

 

25.右图中的拓扑序列为（ )

A.C1，C2，C6，C7，C5，C4，C3

B.C1，C2，C6，C3，C4，C5，C7

C.C1，C4，C2，C3，C5，C6，C7

D.C5，C7，C4，C1，C2，C6，C3