南开23秋学期（仅限-高起专1909、专升本1909）《数据结构》在线作业【标准答案】

23秋学期（仅限-高起专1909、专升本1909）《数据结构》在线作业-00001

试卷总分:100 得分:100

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

1.设F是一个森林，B是由F变换得的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有()个

A.n-1

B.n

C.n+1

D.n+2



2.排序方法中，从未排序序列中顺次取出元素与已排序序列（初始时为空）中的元素进行对比，将其放入已排序序列的正确方位上的方法，称为()

A.希尔排序

B.冒泡排序

C.刺进排序

D.挑选排序



3.连接存储的存储结构所占存储空间（）

A.分两有些，一有些寄存结点值，另一有些寄存表明结点间关系的指针

B.只要一有些，寄存结点值

C.只要一有些，存储表明结点间关系的指针

D.分两有些，一有些寄存结点值，另一有些寄存结点所占单元数



4.一棵具有 n个结点的彻底二叉树的树高度（深度）是（ ）

A.{图}

B.{图}

C.{图}

D.{图}



5.用邻接表表明图进行广度优先遍历时，一般是选用（）来完成算法的

A.栈

B.行列

C.树

D.图



6.减半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它将顺次与表中()对比巨细，查找成果是失利。

A.20，70，30，50

B.30，88，70，50

C.20，50

D.30，88，50



7.已知图的邻接矩阵，依据算法，则从极点0动身，按广度优先遍历的结点序列是（）



{图}

A.0 2 4 3 6 5 1

B.0 1 3 6 4 2 5

C.0 4 2 3 1 5 6

D.0 1 3 4 2 5 6



8.已知图的邻接表如下所示，依据算法，则从极点0动身按深度优先遍历的结点序列是（）



{图}

A.0 1 3 2

B.0 2 3 1

C.0 3 2 1

D.0 1 2 3



9.在n个结点的次序表中，算法的时刻杂乱度是O（1）的操作是（）

A.拜访第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）

B.在第i个结点后刺进一个新结点（1≤i≤n）

C.删去第i个结点（1≤i≤n）

D.将n个结点从小到大排序



10.二叉树对错线性数据结构，所以（）

A.它不能用次序存储结构存储

B.它不能用链式存储结构存储

C.次序存储结构和链式存储结构都能存储

D.次序存储结构和链式存储结构都不能运用



11.疾速排序鄙人列哪种状况下最易发扬其利益()

A.被排序的数据中富含多个一样排序码

B.被排序的数据已根本有序

C.被排序的数据彻底无序

D.被排序的数据中的最大值和最小值相差悬殊



12.深度优先遍历相似于二叉树的()

A.先序遍历

B.中序遍历

C.后序遍历

D.层次遍历



13.链表是一种选用 存储结构存储的线性表

A.次序

B.链式

C.星式

D.网状



14.对有n个记载的表作疾速排序，在最坏状况下，算法的时刻杂乱度是()

A.O(n)

B.O(n2)

C.O(nlog2n)

D.O(n3)



15.线性表Ｌ在（）状况下适用于运用链式结构完成。

A.需常常修正Ｌ中的结点值

B.需不断对Ｌ进行删去刺进

C.Ｌ中富含很多的结点

D.Ｌ中结点结构杂乱



16.用邻接表表明图进行深度优先遍历时，一般是选用()来完成算法的

A.栈

B.行列

C.树

D.图



17.下列关键词序列中，()是堆

A.16,72,31,23,94,53

B.94,23,31,72,16,53

C.16,53,23,94，31,72

D.16,23,53,31,94,72



18.将5个不一样的数据进行排序，至多需求对比()次

A.8

B.9

C.10

D.25



19.在一个有向图中，一切极点的入度之和等于一切极点的出度之和的（）倍。

A.1/2

B.1

C.2

D.4



20.线性表若选用链式存储结构时，要求内存中可用存储单元的地址（）

A.有必要是接连的

B.有些地址有必要是接连的

C.必定是不接连的

D.接连或不接连都能够



21.广度优先遍历相似于二叉树的()

A.先序遍历

B.中序遍历

C.后序遍历

D.层次遍历



22.串是一种特别的线性表，其特别性表现在（）

A.能够次序存储

B.数据元素是一个字符

C.能够链式存储

D.数据元素能够是多个字符



23.数组Ｑ［ｎ］用来表明一个循环行列，ｆ为当时行列头元素的前一方位，ｒ为队尾元素的方位，假定行列中元素的个数小于ｎ，计算行列中元素的公式为

A.r－f

B.（n＋f－r）% n

C.n＋r－f

D.（n＋r－f）% n



24.任何一个无向连通图的最小生成树()

A.只要一棵

B.一棵或多棵

C.必定有多棵

D.能够不存在



25.堆的形状是一棵()

A.二叉排序树

B.满二叉树

C.彻底二叉树

D.平衡二叉树



26.对ｎ个不一样的排序码进行冒泡排序，鄙人列哪种状况下对比的次数最多。()

A.从小到大摆放好的

B.从大到小摆放好的

C.元素无序

D.元素根本有序



27.单链表的存储密度（）

A.大于1

B.等于1

C.小于1

D.不能断定



28.向一个有127个元素的次序表中刺进一个新元素并坚持本来次序不变，均匀要移动（）个元素

A.8

B.63.5

C.63

D.7



29.已知一棵二叉树的前序遍历成果为ABCDEF,中序遍历成果为CBAEDF,则后序遍历的成果为()

A.CBEFDA

B.FEDCBA

C.CBEDFA

D.不定



30.有8个结点的无向图最多有（）条边

A.14

B.28

C.56

D.112



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

31.二叉树中每个结点的关键词值大于其左非空子树（若存在的话）一切结点的关键词值，且小于其右非空子树（若存在的话）一切结点的关键词值。



32.链表的每个结点中都刚好包括一个指针。



33.关于不一样的运用者，一个表结构既能够是栈，也能够是行列，也能够是线性表



34.若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只要n—1个非空指针域。



35.具有12个结点的彻底二叉树有5个度为2的结点。



36.二叉树中一切结点个数是2k-1-1，其间k是树的深度。



37.二叉树中一切结点，假如不存在非空左子树，则不存在非空右子树。



38.两个栈同享一片接连内存空间时，为进步内存使用率，削减溢出时机，应把两个栈的栈底别离设在这片内存空间的两头。



39.次序存储方法的长处是存储密度大，且刺进、删去运算功率高。



40.次序存储方法只能用于存储线性结构。



41.栈和行列的存储方法既但是次序方法，也但是连接方法。



42.队是一种刺进与删去操作别离在表的两头进行的线性表，是一种领先后出型结构。



43.次序表结构适合于进行次序存取，而链表适合于进行随机存取。



44.栈和行列是一种非线性数据结构。



45.线性表在次序存储时，逻辑上相邻的元素未必在存储的物理方位次第上相邻。



46.二叉树中每个结点的两棵子树是有序的。



47.栈是一种对一切刺进、删去操作限于在表的一端进行的线性表，是一种后进先出型结构。



48.线性表的逻辑次序与存储次序老是共同的。



49.链表的物理存储结构具有同链表相同的次序。



50.关于一棵非空二叉树，它的根结点作为榜首层，则它的第i层上最多能有2i—1个结点。