才径谷 >电大网教 >南开大学 >南开大学计算机科学与技术专业《数据结构》作业及答案6

南开大学计算机科学与技术专业《数据结构》作业及答案6试卷及答案大全

永久免费查看

更新时间：2026-04-10

南开大学计算机科学与技术专业《数据结构》作业及答案6提供该考试科目的试卷全部试题及答案大全，科目内容齐全，答案供学员学习免费使用，助力考试通关！

第1题、 [单选题] 对有n个记录的表作快速排序，在最坏情况下，算法的时间复杂度是()

A.O(n)

B.O(n2)

C.O(nlog2n)

D.O(n3)

答案如下：

第2题、 [单选题] 引入二叉线索树的目的是()

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

B.为了能在二叉树中方便的进行插入与删除

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

D.使二叉树的遍历结果唯一

答案如下：

第3题、 [单选题] 在一个图中，所有顶点的度数之和等于图的边数的()倍

A.1/2

B.1

C.2

D.4

答案如下：

第4题、 [单选题] 已知图的邻接矩阵，根据算法，则从顶点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

答案如下：

第5题、 [单选题] 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的()倍。

A.1/2

B.1

C.2

D.4

答案如下：

第6题、 [单选题] 判定一个栈ST(最多元素为m0)为空的条件是()

A.ST->top<>0

B.ST->top=0

C.ST->top<>m0

D.ST->top=m0

答案如下：

第7题、 [单选题] 若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为()

A.i

B.n=i

C.n-i+1

D.不确定

答案如下：

第8题、 [单选题] 在表长为n的链表中进行线性查找，它的平均查找长度为()

A.ASL=n

B.ASL=(n+1)/2

C.ASL=√n+1

D.ASL≈log₂（n+1）-1

答案如下：

第9题、 [单选题] 已知图的邻接矩阵，根据算法，则从顶点0出发，按深度优先遍历的结点序列是()

A.0 2 4 3 1 5 6

B.0 1 3 5 6 4 2

C.0 4 2 3 1 6 5

D.0 1 3 4 2 5 6

答案如下：

第10题、 [单选题] 一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是()

A.110

B.108

C.100

D.120

答案如下：

第11题、 [单选题] 数组Q[n]用来表示一个循环队列，f为当前队列头元素的前一位置，r为队尾元素的位置，假定队列中元素的个数小于n，计算队列中元素的公式为()

A.r-f

B.(n+f-r)% n

C.n+r-f

D.(n+r-f)% n

答案如下：

第12题、 [单选题] 已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是()

A.0 2 4 3 1 5 6

B.0 1 3 6 5 4 2

C.0 4 2 3 1 6 5

D.0 3 6 1 5 4 2

答案如下：

第13题、 [单选题] 设有两个串p和q，求q在p中首次出现的位置的运算称作()

A.连接

B.模式匹配

C.求子串

D.求串长

答案如下：

第14题、 [单选题] 已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是()

A.0 1 3 2

B.0 2 3 1

C.0 3 2 1

D.0 1 2 3

答案如下：

第15题、 [单选题] 链表是一种采用()存储结构存储的线性表

A.顺序

B.链式

C.星式

D.网状

答案如下：

第16题、 [单选题] 判定一个队列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

答案如下：

第17题、 [单选题] 不含任何结点的空树()

A.是一棵树

B.是一棵二叉树

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

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

答案如下：

第18题、 [单选题] 快速排序在下列哪种情况下最易发挥其长处()

A.被排序的数据中含有多个相同排序码

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

C.被排序的数据完全无序

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

答案如下：

第19题、 [单选题] 在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是()

A.访问第i个结点(1≤i≤n)和求第i个结点的直接前驱(2≤i≤n)

B.在第i个结点后插入一个新结点(1≤i≤n)

C.删除第i个结点(1≤i≤n)

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

答案如下：

第20题、 [单选题] 设串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

答案如下：

第21题、 [单选题] 已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是()

A.0 3 2 1

B.0 1 2 3

C.0 1 3 2

D.0 3 1 2

答案如下：

第22题、 [单选题] 用邻接表表示图进行深度优先遍历时，通常是采用()来实现算法的

A.栈

B.队列

C.树

D.图

答案如下：

第23题、 [单选题] 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动()个元素

A.8

B.63.5

C.63

D.7

答案如下：

第24题、 [单选题] 数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为()

A.存储结构

B.逻辑结构

C.顺序存储结构

D.链式存储结构

答案如下：

第25题、 [单选题] 深度优先遍历类似于二叉树的()

A.先序遍历

B.中序遍历

C.后序遍历

D.层次遍历

答案如下：

第26题、 [单选题] 下列关键字序列中，()是堆

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

答案如下：

第27题、 [单选题] 已知图的邻接矩阵，根据算法，则从顶点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

答案如下：

第28题、 [单选题] 一棵具有n个结点的完全二叉树的树高度(深度)是()

A.[logn]+1

B.logn+1

C.[logn]

D.logn-1

答案如下：

第29题、 [单选题] 二叉树是非线性数据结构，所以()

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

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

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

D.顺序存储结构和链式存储结构都不能使用

答案如下：

第30题、 [单选题] 具有n(n>0)个结点的完全二叉树的深度为()

A.log2(n)

B.log2(n)

C.log2(n)+1

D.log2(n)+1

答案如下：

第31题、 [判断题] 二叉树中每个结点的关键字值大于其左非空子树(若存在的话)所有结点的关键字值，且小于其右非空子树(若存在的话)所有结点的关键字值。()

A.正确

B.错误

答案如下：

第32题、 [判断题] 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。()

A.正确

B.错误

答案如下：

第33题、 [判断题] 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。()

A.正确

B.错误

答案如下：

第34题、 [判断题] 队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。()

A.正确

B.错误

答案如下：

第35题、 [判断题] 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。()

A.正确

B.错误

答案如下：

第36题、 [判断题] 顺序存储方式只能用于存储线性结构。()

A.正确

B.错误

答案如下：

第37题、 [判断题] 链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。()

A.正确

B.错误

答案如下：

第38题、 [判断题] 线性表的逻辑顺序与存储顺序总是一致的。()

A.正确

B.错误

答案如下：

第39题、 [判断题] 线性表在物理存储空间中也一定是连续的。()

A.正确

B.错误

答案如下：

第40题、 [判断题] 对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i—1个结点。()

A.正确

B.错误

答案如下：

第41题、 [判断题] 栈和队列的存储方式既可是顺序方式，也可是链接方式。()

A.正确

B.错误

答案如下：

第42题、 [判断题] 对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。()

A.正确

B.错误

答案如下：

第43题、 [判断题] 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。()

A.正确

B.错误

答案如下：

第44题、 [判断题] 二叉树中每个结点有两棵非空子树或有两棵空子树。()

A.正确

B.错误

答案如下：

第45题、 [判断题] 二叉树中每个结点的两棵子树是有序的。()

A.正确

B.错误

答案如下：

第46题、 [判断题] 链表的每个结点中都恰好包含一个指针。()

A.正确

B.错误

答案如下：

第47题、 [判断题] 二叉树中每个结点的两棵子树的高度差等于1。()

A.正确

B.错误

答案如下：

第48题、 [判断题] 栈和链表是两种不同的数据结构。()

A.正确

B.错误

答案如下：

第49题、 [判断题] 二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。()

A.正确

B.错误

答案如下：

第50题、 [判断题] 二叉树中所有结点个数是2k-1-1，其中k是树的深度。()

A.正确

B.错误

答案如下：