南开18春《数据结构》在线作业参考
18春学期《数据结构》在线作业一、单选题：
1.（单选题）堆的形状是一棵() (满分:)
A二叉排序树
B满二叉树
C完全二叉树
D平衡二叉树
正确答案:——C——
2.（单选题）有8个结点的有向完全图有（）条边 (满分:)
A14
B28
C56
D112
正确答案:——C——
3.（单选题）数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素的公式为 (满分:)
Ar－f
B（n＋f－r）%n
Cn＋r－f
D（n＋r－f）%n
正确答案:——D——
4.（单选题）有8个结点的无向连通图最少有（）条边 (满分:)
A5
B6
C7
D8
正确答案:————
5.（单选题）折半搜索与二叉搜索树的时间性能() (满分:)
A相同
B完全不同
C有时不相同
D数量级都是O（log2n）
正确答案:————
6.（单选题）折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它将依次与表中()比较大小，查找结果是失败。 (满分:)
A20，70，30，50
B30，88，70，50
C20，50
D30，88，50
正确答案:————
7.（单选题）已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是（） (满分:)
A0243156
B0136542
C0423165
D0361542
正确答案:————
8.（单选题）排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为() (满分:)
A希尔排序
B冒泡排序
C插入排序
D选择排序
正确答案:————
9.（单选题）设有两个串p和q，求q在p中首次出现的位置的运算称作（） (满分:)
A连接
B模式匹配
C求子串
D求串长
正确答案:————
10.（单选题）下列关键字序列中，()是堆 (满分:)
A16,72,31,23,94,53
B94,23,31,72,16,53
C16,53,23,94，31,72
D16,23,53,31,94,72
正确答案:————
11.（单选题）对有n个记录的表作快速排序，在最坏情况下，算法的时间复杂度是() (满分:)
AO(n)
BO(n2)
CO(nlog2n)
DO(n3)
正确答案:————
12.（单选题）在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。 (满分:)
A1/2
B1
C2
D4
正确答案:————
13.（单选题）二叉树是非线性数据结构，所以（） (满分:)
A它不能用顺序存储结构存储
B它不能用链式存储结构存储
C顺序存储结构和链式存储结构都能存储
D顺序存储结构和链式存储结构都不能使用
正确答案:————
14.（单选题）栈中元素的进出原则是（） (满分:)
A先进先出
B后进先出
C栈空则进
D栈满则出
正确答案:————
15.（单选题）若一组记录的排序码为（46,79,56,38,40,84），则利用堆排序的方法建立的初始堆为() (满分:)
A79,46,56,38,40,84
B84,79,56,38,40,46
C84,79,56,46,40,38
D84,56,79,40,46,38
正确答案:————
16.（单选题）具有n(n>0)个结点的完全二叉树的深度为（） (满分:)
A
B
C
D
正确答案:————
17.（单选题）把一棵树转换为二叉树后，这棵二叉树的形态是（） (满分:)
A唯一的
B有多种
C有多种，但根结点都没有左孩子
D有多种，但根结点都没有右孩子
正确答案:————
18.（单选题）向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（）个元素 (满分:)
A8
B63.5
C63
D7
正确答案:————
19.（单选题）深度优先遍历类似于二叉树的() (满分:)
A先序遍历
B中序遍历
C后序遍历
D层次遍历
正确答案:————
20.（单选题）对ｎ个不同的排序码进行冒泡排序，在下列哪种情况下比较的次数最多。() (满分:)
A从小到大排列好的
B从大到小排列好的
C元素无序
D元素基本有序
正确答案:————
21.（单选题）将5个不同的数据进行排序，至多需要比较()次 (满分:)
A8
B9
C10
D25
正确答案:————
22.（单选题）设F是一个森林，B是由F变换得的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有()个 (满分:)
An-1
Bn
Cn+1
Dn+2
正确答案:————
23.（单选题）在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是（） (满分:)
A访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）
B在第i个结点后插入一个新结点（1≤i≤n）
C删除第i个结点（1≤i≤n）
D将n个结点从小到大排序
正确答案:————
24.（单选题）串是一种特殊的线性表，其特殊性体现在（） (满分:)
A可以顺序存储
B数据元素是一个字符
C可以链式存储
D数据元素可以是多个字符
正确答案:————
25.（单选题）一棵具有n个结点的完全二叉树的树高度（深度）是（） (满分:)
A
B
C
D
正确答案:————
26.（单选题）对22个记录的有序表作折半查找，当查找失败时，至少需要比较()次关键字。 (满分:)
A3
B4
C5
D6
正确答案:————
27.（单选题）设串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))的结果串是（） (满分:)
ABCDEF
BBCDEFG
CBCPQRST
DBCDEFEF
正确答案:————
28.（单选题）线性表Ｌ在（）情况下适用于使用链式结构实现。 (满分:)
A需经常修改Ｌ中的结点值
B需不断对Ｌ进行删除插入
CＬ中含有大量的结点
DＬ中结点结构复杂
正确答案:————
29.（单选题）设a1、a2、a3为3个结点，整数P0，3，4代表地址，则如下的链式存储结构称为（） (满分:)
A循环链表
B单链表
C双向循环链表
D双向链表
正确答案:————
30.（单选题）不含任何结点的空树（） (满分:)
A是一棵树
B是一棵二叉树
C是一棵树也是一棵二叉树
D既不是树也不是二叉树
正确答案:————
三、判断题：
31.（判断题）用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。 (满分:)
A错误
B正确
正确答案:————
32.（判断题）栈和链表是两种不同的数据结构。 (满分:)
A错误
B正确
正确答案:————
33.（判断题）具有12个结点的完全二叉树有5个度为2的结点。 (满分:)
A错误
B正确
正确答案:————
34.（判断题）对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表 (满分:)
A错误
B正确
正确答案:————
35.（判断题）一个栈的输入序列是12345，则栈的输出序列不可能是12345。 (满分:)
A错误
B正确
正确答案:————
36.（判断题）栈和队列是一种非线性数据结构。 (满分:)
A错误
B正确
正确答案:————
37.（判断题）线性表在物理存储空间中也一定是连续的。 (满分:)
A错误
B正确
正确答案:————
38.（判断题）链表的每个结点中都恰好包含一个指针。 (满分:)
A错误
B正确
正确答案:————
39.（判断题）线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。 (满分:)
A错误
B正确
正确答案:————
40.（判断题）二叉树中每个结点的两棵子树的高度差等于1。 (满分:)
A错误
B正确
正确答案:————
41.（判断题）对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i—1个结点。 (满分:)
A错误
B正确
正确答案:————
42.（判断题）顺序存储方式的优点是存储密度大，且插入、删除运算效率高。 (满分:)
A错误
B正确
正确答案:————
43.（判断题）二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字值，且小于其右非空子树（若存在的话）所有结点的关键字值。 (满分:)
A错误
B正确
正确答案:————
44.（判断题）链表的物理存储结构具有同链表一样的顺序。 (满分:)
A错误
B正确
正确答案:————
45.（判断题）线性表的逻辑顺序与存储顺序总是一致的。 (满分:)
A错误
B正确
正确答案:————
46.（判断题）顺序存储方式只能用于存储线性结构。 (满分:)
A错误
B正确
正确答案:————
47.（判断题）栈和队列的存储方式既可是顺序方式，也可是链接方式。 (满分:)
A错误
B正确
正确答案:————
48.（判断题）二叉树中每个结点有两棵非空子树或有两棵空子树。 (满分:)
A错误
B正确
正确答案:————
49.（判断题）顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。 (满分:)
A错误
B正确
正确答案:————
50.（判断题）栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。 (满分:)
A错误
B正确
正确答案:————
转载请注明www.ap5u.com
页:
[1]