南开22秋学期（高起本1709-1803、全层次1809-2103）《数据结构》在线作业【标准答案】

22秋学期（高起本1709-1803、全层次1809-2103）《数据结构》在线作业-00002

试卷总分:100 得分:98

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

1.链表适用于()查找

A.次序

B.二分法

C.次序，也能二分法

D.随机



2.引进二叉头绪树的意图是（ ）

A.加速查找结点的前驱或后继的速度

B.为了能在二叉树中便利的进行刺进与删去

C.为了能便利的找到双亲

D.使二叉树的遍历成果仅有



3.栈中元素的进出准则是（）

A.领先先出

B.后进先出

C.栈空则进

D.栈满则出



4.堆是一种()排序。

A.刺进

B.挑选

C.交流

D.归并



5.断定一个行列QU（最多元素为m0）为满行列的条件是（）

A.QU->rear － QU->front = = m0

B.QU->rear － QU->front －1= = m0

C.QU->front = = QU->rear

D.QU->front = = QU->rear+1



6.有8个结点的有向彻底图有（）条边

A.14

B.28

C.56

D.112



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

A.1/2

B.1

C.2

D.4



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

A.从小到大摆放好的

B.从大到小摆放好的

C.元素无序

D.元素根本有序



9.下述几种排序方法中，要求内存最大的是()

A.刺进排序

B.疾速排序

C.归并排序

D.挑选排序



10.堆的形状是一棵()

A.二叉排序树

B.满二叉树

C.彻底二叉树

D.平衡二叉树



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

A.希尔排序

B.冒泡排序

C.刺进排序

D.挑选排序



12.有8个结点的无向连通图起码有（）条边

A.5

B.6

C.7

D.8



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

A.有必要是接连的

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

C.必定是不接连的

D.接连或不接连都能够



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



{图}

A.0 3 2 1

B.0 1 2 3

C.0 1 3 2

D.0 3 1 2



15.减半查找有序表（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



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

A.8

B.9

C.10

D.25



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

A.能够次序存储

B.数据元素是一个字符

C.能够链式存储

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



18.断定一个栈ST（最多元素为m0）为空的条件是（）

A.ST->top<>0

B.ST->top=0

C.ST->top<>m0

D.ST->top=m0



19.不含任何结点的空树（）

A.是一棵树

B.是一棵二叉树

C.是一棵树也是一棵二叉树

D.既不是树也不是二叉树



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



{图}

A.0 2 4 3 1 6 5

B.0 1 3 5 6 4 2

C.0 1 2 3 4 6 5

D.0 1 2 3 4 5 6



21.减半查找与二叉查找树的时刻功能()

A.一样

B.彻底不一样

C.有时不一样

D.数量级都是O（log2n）



22.数据在计算机存储器内表明时，物理地址与逻辑地址一样而且是接连的，称之为()

A.存储结构

B.逻辑结构

C.次序存储结构

D.链式存储结构



23.设串s1=’ABCDEFG’，s2=’PQRST’，函数con(x,y)回来x和y串的衔接串，subs(s, i, j)回来串s的从序号i开端的j个字符构成的子串，len(s)回来串s的长度，则con(subs(s1, 2, len(s2)), subs(s1, len(s2), 2))的成果串是（）

A.BCDEF

B.BCDEFG

C.BCPQRST

D.BCDEFEF



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

A.CBEFDA

B.FEDCBA

C.CBEDFA

D.不定



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

A.n-1

B.n

C.n+1

D.n+2



26.在表长为ｎ的链表中进行线性查找，它的均匀查找长度为（ ）

A.ＡＳＬ＝ｎ

B.ＡＳＬ＝（ｎ＋１）／２

C.{图}

D.{图}



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

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



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



{图}

A.0 1 3 2

B.0 2 3 1

C.0 3 2 1

D.0 1 2 3



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

A.先序遍历

B.中序遍历

C.后序遍历

D.层次遍历



30.在一个图中，一切极点的度数之和等于图的边数的（）倍

A.1/2

B.1

C.2

D.4



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

31.链表的删去算法很简略，由于当删去链中某个结点后，计算时机自动地将后续的各个单元向前移动。



32.栈和链表是两种不一样的数据结构。



33.一个栈的输入序列是12345，则栈的输出序列不可以能是12345。



34.二叉树中每个结点的两棵子树的高度差等于1。



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



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



37.在表结构中最常用的是线性表，栈和行列不太常用。



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



39.线性表的每个结点只能是一个简略类型，而链表的每个结点能够是一个杂乱类型。



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



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



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



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



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



45.用二叉链表法（link-rlink）存储包括n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。



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



47.二叉树中每个结点有两棵非空子树或有两棵空子树。



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



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



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