《数据结构》作业和检测网络课程原题及答案

作业1

一、单选题
1.一个具有1025个结点的二叉树的高h为______.
A.11
B.10
C.11至1025之间
D.10至1024之间
答案：C

2.有关二叉树下列说法正确的是______.
A.二叉树的度为2
B.一棵二叉树的度可以小于2
C.二叉树中至少有一个结点的度为2
D.二叉树中任何一个结点的度都为2
答案：B

3.下述几种排序方法中，要求内存最大的是（ ）。
A.希尔排序
B.快速排序
C.归并排序
D.堆排序
答案：C

4.下述几种排序方法中，（ ）是稳定的排序方法。
A.希尔排序
B.快速排序
C.归并排序
D.堆排序
答案：C

5.数据表中有10000个元素，如果仅要求求出其中最大的10个元素，则采用( )算法最节省时间。
A.冒泡排序
B.快速排序
C.简单选择排序
D.堆排序
答案：D

6.下列排序算法中，（ ）不能保证每趟排序至少能将一个元素放到其最终的位置上。
A.希尔排序
B.快速排序
C.冒泡排序
D.堆排序
答案：A

7.堆的形状是一棵( )。
A.二叉排序树
B.满二叉树
C.完全二叉树
D.平衡二叉树
答案：C

8.树最适合用来表示______.
A.有序数据元素
B.无序数据元素
C.元素之间无联系的数据
D.元素之间有分支的层次关系
答案：D

9.前序遍历序列为A,B,C的二叉树共有_____种。
A.2
B.3
C.4
D.5
答案：D

10.根据二叉树的定义，具有3个结点的二叉树有___种树型。
A.3
B.4
C.5
D.6
答案：C

11.引入二叉线索树的目的是______。
A.加快查找结点的前驱或后继的速度
B.为了能在二叉树中方便的进行插入与
C.为了能方便的找到双亲
D.使二叉树的遍历结果唯一
答案：A

12.在一棵具有五层的满二叉树中，结点的总数为____。
A.16
B.31
C.32
D.33
答案：B

13.具有64个结点的完全二叉树的深度为_____。
A.5
B.6
C.7
D.8
答案：C

14.从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为（ ）。
A.归并排序
B.冒泡排序
C.插入排序
D.选择排序
答案：D

15.对n个不同的关键字由小到大进行冒泡排序，在下列（ ）情况下比较的次数最多。
A.从小到大排列好的
B.从大到小排列好的
C.元素无序
D.元素基本有序
答案：B

16.对n个不同的排序码进行冒泡排序，在元素无序的情况下比较的次数最多为（ ）。
A.n+1
B.O(n2)
C.O(nlog2n)
D.O(n3)
答案：B

17.若一组记录的排序码为（46, 79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（ ）。
A.38，40，46，56，79，84
B.40，38，46，79，56，84
C.40，38，46，56，79，84
D.40，38，46，84，56，79
答案：C

18.若一组记录的排序码为（46，79，56，38，40，84），则利用堆排序的方法建立的初始堆为（ ）。
A.79，46，56，38，40，84
B.84，79，56，38，40，46
C.84，79，56，46，40，38
D.84，56，79，40，46，38
答案：B

19.在下列存储形式中，_____不是树的存储形式？
A.双亲表示法
B.孩子链表表示法
C.孩子兄弟表示法
D.顺序存储表示法
答案：D

20.线索二叉树是一种（ ）结构。
A.逻辑
B.逻辑和存储
C.物理
D.线性
答案：C

21.一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足___.
A.所有的结点均无左孩子
B.所有的结点均无右孩子
C.所有的结点均无右孩子
D.是任意一棵二叉树
答案：C

22.利用二叉链表存储树，则根结点的右指针是（ ）。
A.指向最左孩子
B.指向最右孩子
C.空
D.非空
答案：C

23.一个具有1025个结点的二叉树的高h为______。
A.11
B.10
C.11至1025之间
D.10至1024之间
答案：C

24.由3个结点可以构造出多少种不同的二叉树？_____
A.2
B.3
C.4
D.5
答案：D

25.一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有_____结点.
A.2h
B.2h-1
C.2h+1
D.h+1
答案：B

26.从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置上的方法，这种排序方法称为（ ）。
A.归并排序
B.冒泡排序
C.插入排序
D.选择排序
答案：CD

27.平衡二叉树的左右子树的高度之差不可能是( )。
A.1
B.0
C.-1
D.2
答案：D

28.有n个叶子结点的哈夫曼树的结点总数为____。
A.不确定
B.2n
C.2n+1
D.2n-1
答案：D

29.将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点编号，根结点的编号为1，则编号为45的结点的右孩子编号为_____.
A.46
B.47
C.90
D.91
答案：CD

30.某二叉树的后序遍历序列为：DABEC,中序遍历序列为：DEBAC,则前序遍历序列为_____.
A.ACBED
B.DECAB
C.DEABC
D.CEDBA
答案：D

作业2

一、单选题
1.G是一个非连通无向图，共有28条边，则该图至少有_____个顶点。
A.7
B.8
C.9
D.10
答案：C

2.用邻接表表示图进行广度优先遍历时，通常借助（ ）来实现算法。
A.栈
B.队列
C.树
D.图
答案：B

3.对矩阵压缩存储是为了_____.
A.方便压缩
B.节省空间
C.方便存储
D.提高运算速度
答案：B

4.设二维数组A[1..m，1..n]（即m行n列）按行存储在数组B[1..m*n]中，则二维数组元素A[i,j]在一维数组B中的下标为____.
A.(i-1)*n+j
B.(i-1)*n+j-1
C.i*(j-1)
D.j*m+i-1
答案：A

5.串是种特殊的线性表,其特殊性体现在___。
A.可以顺序存储
B.数据元素是一个字符
C.可以链式存储
D.数据元素可以是多个字符
答案：B

6.循环队列存储在数组A[0..m]中，则入队时的操作为（　）。
A.rear=rear+1
B.rear=(rear+1)%(m-1)
C.rear=(rear+1)%m
D.rear=(rear+1)%(m+1)
答案：D

7.设计一个判别表达式中左，右括号是否配对出现的算法，采用（　）数据结构最佳。
A.线性表的顺序存储结构
B.队列
C.线性表的链式存储结构
D.栈
答案：D

8.栈在 （ ）中有所应用。
A.递归调用
B.函数调用
C.表达式求值
D.前三个选项都有
答案：D

9.链式栈结点为：(data,link)，top指向栈顶.若想摘除栈顶结点，并将删除结点的值保存到x中,则应执行操作（ ）。
A.x=top->data;top=top->link
B.top=top->link;x=top->link
C.x=top;top=top->link
D.x=top->link
答案：A

10.用链接方式存储的队列，在进行删除运算时_______。
A.仅修改头指针
B.仅修改尾指针
C.头、尾指针都要修改
D.头、尾指针可能都要修改
答案：D

11.下面的________方法可以判断出一个有向图是否有环。
A.求最小生成树
B.拓扑排序
C.求最短路径
D.求关键路径
答案：B

12.数组Q[n]用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素个数的公式为_______。
A.r-f
B.(n+f-r)%n
C.n+r-f
D.（n+r-f)%n
答案：D

13.若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为（ ）。
A.i
B.n-i
C.n-i+1
D.不确定
答案：C

14.同一队列的各元素的类型____.
A.必须一致
B.不能一致
C.可以不一致
D.不限制
答案：A

15.在循环队列中，设尾指针指向队尾元素的后一个位置，头指针指向队头元素，队列容量为M，则若尾指针rear小于头指针front,其元素个数为_______。
A.rear-front
B.front-rear
C.M-front+rear
D.M-rear+front
答案：C

16.若用一个大小为6的数组来实现循环队列,且当前Head和Tail的值分别为0和3,当从队列中删除一个元素,再加入两个元素后,Head和Tail的值分别为_____.
A.1和5
B.2和4
C.4和2
D.5和1
答案：A

17.循环队列在进行删除运算时,_____.
A.仅修改头指针
B.仅修改尾指针
C.头尾指针都要修改
D.头尾指针可能都要修改
答案：A

18.一个栈的输入序列为1,2,3,…,n,若输出序列的第一个元素是n,输出序列的第i(1≤i≤n)个元素是______.
A.不确定
B.n-i+1
C.i
D.n-i
答案：B

19.有向网G1=(V1,{A1}),其中V1={a,b,c,d,e,f}，A1={＜a,b,5＞,＜a,f,3＞,＜b,c,5＞,＜c,e,1＞,＜d,c,2＞,＜d,e,6＞,＜f,b,1＞＜f,d,3＞,＜f,e,4＞},其中数值表示边的权值。对G1采用迪杰斯特拉(Dijkstra)算法求从顶点a到其余各顶点的最短路径,顶点最短路径求出的次序是_______.
A.b,c,d,e,f
B.f,b,c,e,d
C.f,b,d,c,e
D.b,f,c,e,d
答案：C

20.已知某连通网G=(V1，{A1})，其中
V1={a,b,c,d,e,f,g},A1={(a,b,9),(a,g,4),(a,f,5),(b,c,3),(b,g,7),(c,d,2),(c,g,6),(d,e,4),(d,g,6),(e,g,6),(e,f,5)},其中数值表示边的权值。对G采用克鲁斯卡尔算法求最小生成树,选择边的顺序是_______.
A.c,d),(b,c),(d,e),(e,f),(a,f),(a,g)
B.(c,d),(b,c),(a,g),(d,e),(a,f),(e,f)
C.(c,d),(b,c),(d,e),(e,f),(a,g),(a,f)
D.(b,g),(g,c),(g,e),(d,g),(a,b),(e,f)
答案：B

21.已知某连通网G=(V1，{A1})，其中V1={a,b,c,d,e,f,g},A1={(a,b,9),(a,g,4),(a,f,5),(b,c,3),(b,g,7),(c,d,2),(c,g,6),(d,e,4),(d,g,6),(e,g,6),(e,f,5)},其中数值表示边的权值。对G采用普里姆算法生成最小生成树,从顶点g出发,选择顶点的次序是_______.
A.a,b,c,d,e,f
B.a,f,e,d,c,b
C.c,d,b,e,f,a
D.b,c,d,e,f,a
答案：B

22.已知某无向图G=（V1，{A1}），其中V1={a,b,c,d},A1={(a,b),(a,d),(b,c),(b,d),(c,d)},则下列____不可能是它的广度优先遍历序列。
A.a,b,c,d
B..a,b,d,c
C.a,d,b,c
D.b,c,d,a
答案：A

23.已知某无向图G=（V1，{A1}），其中V1={a,b,c,d},A1={(a,b),(a,d),(b,c),(b,d),(c,d)},则下列____不可能是它的深度优先遍历序列。
A.a,b,c,d
B.a,b,d,c
C.a,d,b,c
D.a,c,b,d
答案：D

24.用邻接表表示图进行深度优先遍历时，通常借助______来实现算法。
A.栈
B.队列
C.树
D.图
答案：A

25.下面______算法适合构造一个稠密图G的最小生成树。
A.Prim算法
B.Kruskal算法
C.Floyd算法
D.Dijkstra算法
答案：A

作业3

一、单选题
1.关于数据对象,下列描述正确的是_____.
A.是数据的一个子集,其中的数据元素包含的数据项可各不相同
B.是数据的一个子集,其中包含多个数据项
C.是数据的一个子集,其中的数据元素性质应相同
D.数据对象是数据元素的一个子集
答案：C

2.数据在计算机存储内表示时，物理地址和逻辑地址相同并且是连续的，称之为______.
A.存储结构
B.逻辑结构
C.顺序存储结构
D.链式存储结构
答案：C

3._____是顺序表的特点.
A.容量不易扩充和访问速度慢
B.容量易扩充和访问速度快
C.容量不易扩充和访问速度快
D.容量易扩充和访问速度慢
答案：C

4.等概率情况下,在有n个结点的顺序表上做插入结点运算,需平均移动结点的数目为____.
A.n
B.(n-1)/2
C.n/2
D.(n+1)/2
答案：C

5.链表不具备的特点是____.
A.随机访问
B.不必事先估计存储空间
C.插入删除时不需移动元素
D.所需空间与线性表成正比
答案：A

6.两个指针P和Q，分别指向单向链表的两个元素，P所指元素是Q所指元素的前驱的条件是___.
A.P.next==Q.next
B.P.next==Q
C.Q.next==P
D.P==Q
答案：B

7.设p为指向单循环链表上某结点的指针,则p的直接前驱___.
A.找不到
B.查找时间复杂度为O(1)
C.查找时间复杂度为O(n)
D.查找结点的次数约为n
答案：C

8.下列有关线性表的叙述中,正确的是____.
A.线性表中的元素之间是线性关系
B.线性表中至少有一个元素
C.线性表中任何一个元素有且仅有一个直接前驱
D.线性表中任何一个元素有且仅有一个直接后继
答案：A

9.线性表若采用链式存储结构,要求内存中可用存储单元的地址_____.
A.必须是连续的
B.部分地址必须是连续的
C.一定不是连续的
D.连续或不连续都可以
答案：D

10.循环链表的主要优点是______.
A.不再需要头指针了
B.已知某个结点的位置后,容易找到它的直接前驱
C.在进入插入、删除运算时，能更好地保证链表不断开
D.从表中的任意结点出发都能扫描到整个链表
答案：D

11.设有一个10阶的对称矩阵，采用压缩存储方式，以行序为主序，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（ ）。
A.13
B.33
C.18
D.40
答案：B

12.已知一个顺序存储的线性表,设每个结点占m个存储单元,若第一个结点的地址为B,则第i个结点的地址为___.
A.B+(i-1)*m
B.B+i*m
C.B-i*m
D.B+(i+1)*m
答案：A

13.以下关于线性表的论述,不正确的为____.
A.线性表中的元素可以是数字、字符、记录等不同类型
B.线性顺序表中包含的元素个数不是任意的
C.线性表中的每个结点都有且仅有一个直接前驱和一个直接后继
D.存在这样的线性表，表中没有任何结点
答案：C

14.用链表表示线性表的优点是_____
A.便于随机存取
B..花费的存储空间较顺序存储少
C.便于插入和删除
D.数据元素的物理顺序和逻辑顺序相同
答案：C

15.在____的运算中，使用顺序表比链表好。
A.插入
B.根据序号查找
C.删除
D.根据元素查找
答案：B

16.在单链表中,增加头结点的目的是___.
A.使单链表至少有一个结点
B.标志表中首结点的位置
C.便于运算的实现
D.说明该单链表是线性表的链式存储结构
答案：C

17.在具有n个结点的单向链表中，实现_____的操作，其算法的时间复杂度都是O(n).
A.遍历链表或求链表的第i个结点
B.在地址为P的结点之后插入一个结点
C.删除开始结点
D.删除地址为P的结点的后继结点
答案：A

18.在有n个结点的顺序表上做插入、删除结点运算的时间复杂度为___.
A..O(1)
B.O(n)
C.O(n2)
D.O(log2n)
答案：B

19.在数据结构的图结构中，数据元素之间存在___的关系。
A.零对零
B.一对一
C.一对多
D.多对多
答案：D

20.计算机算法是指_____.
A.计算方法
B.排序方法
C.解决问题的有限运算序列
D.调度方法
答案：C

21.算法具备输入、输出、_____五个特性。
A.可行性、可移植性和可扩充性
B.可行性、确定性和有穷性
C.确定性、有穷性和稳定性
D.穷性、确定性和连续性
答案：B

22.下列四种算法的时间复杂度中,_____执行时间最短。
A.O(n)
B.O(log2n)
C.O(2n)
D..O(n2)
答案：B

23.数据结构通常是研究数据的______及它们之间的相互关系。
A.存储结构和逻辑结构
B.存储和抽象
C.联系和抽象
D.联系与逻辑
答案：A

24.下列关于算法的描述,正确的是_____.
A.算法的设计取决于数据的逻辑结构,实现取决于存储结构
B.算法的设计取决于数据的存储结构,实现取决于数据的逻辑结构
C.算法的设计和实现都取决于逻辑结构
D.算法的设计和实现都取决于存储结构
答案：A

25.下列算法的时间复杂度是______.for(i=0;i<n;i++)
for(j=0;j<n;j++)
c[i,j]=i+j;
A.O(1)
B.O(n)
C.O(log2n)
D.O(n2)
答案：D

26.具有10个叶结点的二叉树中有____个度为2的结点.
A.8
B.9
C.10
D.11
答案：B

27.m阶B-树是一棵( )。
A.m叉排序树
B.m叉平衡排序树
C.m-1叉平衡排序树
D.m+1叉平衡排序树
答案：B

28.一棵完全二叉树上有1001个结点，其中叶子结点的个数是______.
A.255
B.480
C.490
D.501
答案：D

29.采用线性探测法处理冲突，可能要探测多个位置，在查找成功的情况下，所探测的这些位置上的关键字 ( )。
A.不一定都是同义词
B.一定都是同义词
C.一定都不是同义词
D.都相同
答案：A

30.二叉树的叶结点个数比度为2的结点的个数_______.
A.无关
B.相等
C.多一个
D.少一个
答案：C

31.二叉树按某种顺序线索化后，任一结点均有指向其前驱和后继的线索,这种说法_______.
A.正确
B.错误
C.不确定
D.都有可能
答案：B

32.把一棵树转换为二叉数后，这棵二叉树的形态是_____.
A.唯一的
B.有多种
C.有多种.但根结点都没有左孩子
D.有多种，但根结点都没有右孩子
答案：D

更多内容关注：河南招生考试网

高起专、专升本：郑大、河大、河南财经、河师大、河南科技大学等.河南众多知名高校..（行政管理、汉语言文学、会计、法律、金融、工商企业管理、市场营销等多个专业）…

【报名方式】

（1）加张老师微信13140109176 -发电子版报名资料-报名费学费转账-书快递发给学员

（2）现场报名→身份证原件→刷卡现金→现场领书（需提前一天预约）

（3）联系电话：13140109176 （张老师） 微信：13140109176