联大学堂《数据结构（河南农业大学）》题库及答案

联大学堂《数据结构（河南农业大学）》题库及答案
1、下列算法的时间复杂度是（）.for（i=0；ifor（j=0；jc[i，j=i+j；
A.O（1）
B.O（n）
C.O（log2n）
D.O（n2）
正确答案：D
2、下列关于算法的描述，正确的是（）。
A.算法的设计取决于数据的逻辑结构，实现取决于存储结构
B.算法的设计取决于数据的存储结构，实现取决于数据的逻辑结构
C.算法的设计和实现都取决于逻辑结构
D.算法的设计和实现都取决于存储结构
正确答案：A
3、数据结构通常是研究数据的（）及它们之间的相互关系。
A.存储结构和逻辑结构
B.存储和抽象
C.联系和抽象
D.联系与逻辑
正确答案：A
4、算法具备输入、输出、（）五个特性。
A.可行性、可移植性和可扩充性
B.可行性、确定性和有穷性
C.确定性、有穷性和稳定性
D.穷性、确定性和连续性
正确答案：B
5、在单链表中，增加头结点的目的是（）。
A.使单链表至少有一个结点
B.标志表中首结点的位置
C.便于运算的实现
D.说明该单链表是线性表的链式存储结构
正确答案：C
6、在具有n个结点的单向链表中，实现（）的操作，其算法的时间复杂度都是O（n）。
A.遍历链表或求链表的第i个结点
B.在地址为P的结点之后插入一个结点
C.删除开始结点
D.删除地址为P的结点的后继结点
正确答案：A
7、在（）的运算中，使用顺序表比链表好。
A.插入
B.根据序号查找
C.删除
D.根据元素查找
正确答案：B
8、在数据结构的图结构中，数据元素之间存在（）的关系。
A.零对零
B.一对一
C.一对多
D.多对多
正确答案：D
9、用链表表示线性表的优点是（）
A.便于随机存取
B..花费的存储空间较顺序存储少
C.便于插入和删除
D.数据元素的物理顺序和逻辑顺序相同
正确答案：C
10、线性表若采用链式存储结构，要求内存中可用存储单元的地址（）。
A.必须是连续的
B.部分地址必须是连续的
C.一定不是连续的
D.连续或不连续都可以
正确答案：D
11、下列有关线性表的叙述中，正确的是（）。
A.线性表中的元素之间是线性关系
B.线性表中至少有一个元素
C.线性表中任何一个元素有且仅有一个直接前驱
D.线性表中任何一个元素有且仅有一个直接后继
正确答案：A
12、在有n个结点的顺序表上做插入、删除结点运算的时间复杂度为（）。
A..O（1）
B.O（n）
C.O（n2）
D.O（log2n）
正确答案：B
13、以下关于线性表的论述，不正确的为（）。
A.线性表中的元素可以是数字、字符、记录等不同类型
B.线性顺序表中包含的元素个数不是任意的
C.线性表中的每个结点都有且仅有一个直接前驱和一个直接后继
D.存在这样的线性表，表中没有任何结点
正确答案：C
14、设有一个10阶的对称矩阵，采用压缩存储方式，以行序为主序，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（）。
A.13
B.33
C.18
D.40
正确答案：B
15、循环链表的主要优点是（）。
A.不再需要头指针了
B.已知某个结点的位置后，容易找到它的直接前驱
C.在进入插入、删除运算时，能更好地保证链表不断开
D.从表中的任意结点出发都能扫描到整个链表
正确答案：D
16、等概率情况下，在有n个结点的顺序表上做插入结点运算，需平均移动结点的数目为（）。
A.n
B.（n-1）/2
C.n/2
D.（n+1）/2
正确答案：C
17、已知一个顺序存储的线性表，设每个结点占m个存储单元，若第一个结点的地址为B，则第i个结点的地址为（）。
A.B+（i-1）*m
B.B+i*m
C.B-i*m
D.B+（i+1）*m
正确答案：A
18、设p为指向单循环链表上某结点的指针，则p的直接前驱（）。
A.找不到
B.查找时间复杂度为O（1）
C.查找时间复杂度为O（n）
D.查找结点的次数约为n
正确答案：C
19、链表不具备的特点是（）。
A.随机访问
B.不必事先估计存储空间
C.插入删除时不需移动元素
D.所需空间与线性表成正比
正确答案：A
20、计算机算法是指（）。
A.计算方法
B.排序方法
C.解决问题的有限运算序列
D.调度方法
正确答案：C
21、数据在计算机存储内表示时，物理地址和逻辑地址相同并且是连续的，称之为（）。
A.存储结构
B.逻辑结构
C.顺序存储结构
D.链式存储结构
正确答案：C
22、两个指针P和Q，分别指向单向链表的两个元素，P所指元素是Q所指元素的前驱的条件是（）。
A.P.next==Q.next
B.P.next==Q
C.Q.next==P
D.P==Q
正确答案：B
23、下列四种算法的时间复杂度中，（）执行时间最短。
A.O（n）
B.O（log2n）
C.O（2n）
D..O（n2）
正确答案：B
24、（）是顺序表的特点。
A.容量不易扩充和访问速度慢
B.容量易扩充和访问速度快
C.容量不易扩充和访问速度快
D.容量易扩充和访问速度慢
正确答案：C
25、关于数据对象，下列描述正确的是（）。
A.是数据的一个子集，其中的数据元素包含的数据项可各不相同
B.是数据的一个子集，其中包含多个数据项
C.是数据的一个子集，其中的数据元素性质应相同
D.数据对象是数据元素的一个子集
正确答案：C
26、用邻接表表示图进行深度优先遍历时，通常借助（）来实现算法。
A.栈
B.队列
C.树
D.图
正确答案：A
27、下面（）算法适合构造一个稠密图G的最小生成树。
A.Prim算法
B.Kruskal算法
C.Floyd算法
D.Dijkstra算法
正确答案：A
28、已知某无向图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
29、已知某无向图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
30、已知某连通网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
31、已知某连通网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
32、有向网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
33、若用一个大小为6的数组来实现循环队列，且当前Head和Tail的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，Head和Tail的值分别为（）。
A.1和5
B.2和4
C.4和2
D.5和1
正确答案：A
34、一个栈的输入序列为1，2，3，.，n，若输出序列的第一个元素是n，输出序列的第i（1≤i≤n）个元素是（）。
A.不确定
B.n-i+1
C.i
D.n-i
正确答案：B
35、同一队列的各元素的类型（）。
A.必须一致
B.不能一致
C.可以不一致
D.不限制
正确答案：A
36、循环队列在进行删除运算时，（）。
A.仅修改头指针
B.仅修改尾指针
C.头尾指针都要修改
D.头尾指针可能都要修改
正确答案：A
37、在循环队列中，设尾指针指向队尾元素的后一个位置，头指针指向队头元素，队列容量为M，则若尾指针rear小于头指针front，其元素个数为（）。
A.rear-front
B.front-rear
C.M-front+rear
D.M-rear+front
正确答案：C
38、数组Q[n用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素个数的公式为（）。
A.r-f
B.（n+f-r）%n
C.n+r-f
D.（n+r-f）%n
正确答案：D
39、若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为（）。
A.i
B.n-i
C.n-i+1
D.不确定
正确答案：C
40、下面的（）方法可以判断出一个有向图是否有环。
A.求最小生成树
B.拓扑排序
C.求最短路径
D.求关键路径
正确答案：B
41、用链接方式存储的队列，在进行删除运算时（）。
A.仅修改头指针
B.仅修改尾指针
C.头、尾指针都要修改
D.头、尾指针可能都要修改
正确答案：D
42、链式栈结点为：（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
43、栈在（）中有所应用。
A.递归调用
B.函数调用
C.表达式求值
D.前三个选项都有
正确答案：D
44、循环队列存储在数组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
45、串是种特殊的线性表，其特殊性体现在（）。
A.可以顺序存储
B.数据元素是一个字符
C.可以链式存储
D.数据元素可以是多个字符
正确答案：B
46、设计一个判别表达式中左，右括号是否配对出现的算法，采用（）数据结构最佳。
A.线性表的顺序存储结构
B.队列
C.线性表的链式存储结构
D.栈
正确答案：D
47、设二维数组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
48、G是一个非连通无向图，共有28条边，则该图至少有（）个顶点。
A.7
B.8
C.9
D.10
正确答案：C
49、对矩阵压缩存储是为了（）。
A.方便压缩
B.节省空间
C.方便存储
D.提高运算速度
正确答案：B
50、一棵二叉树高度为h，所有结点的度或为0，或为2，则这棵二叉树最少有（）结点。
A.2h
B.2h-1
C.2h+1
D.h+1
正确答案：B
51、用邻接表表示图进行广度优先遍历时，通常借助（）来实现算法。
A.栈
B.队列
C.树
D.图
正确答案：B
52、由3个结点可以构造出多少种不同的二叉树？（）
A.2
B.3
C.4
D.5
正确答案：D
53、利用二叉链表存储树，则根结点的右指针是（）。
A.指向最左孩子
B.指向最右孩子
C.空
D.非空
正确答案：C
54、一个具有1025个结点的二叉树的高h为（）。
A.11
B.10
C.11至1025之间
D.10至1024之间
正确答案：C
55、一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（）。
A.所有的结点均无左孩子
B.所有的结点均无右孩子
C.所有的结点均无右孩子
D.是任意一棵二叉树
正确答案：C
56、在下列存储形式中，（）不是树的存储形式？
A.双亲表示法
B.孩子链表表示法
C.孩子兄弟表示法
D.顺序存储表示法
正确答案：D
57、若一组记录的排序码为（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
58、对n个不同的排序码进行冒泡排序，在元素无序的情况下比较的次数最多为（）。
A.n+1
B.O（n2）
C.O（nlog2n）
D.O（n3）
正确答案：B
59、若一组记录的排序码为（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
60、线索二叉树是一种（）结构。
A.逻辑
B.逻辑和存储
C.物理
D.线性
正确答案：C
61、对n个不同的关键字由小到大进行冒泡排序，在下列（）情况下比较的次数最多。
A.从小到大排列好的
B.从大到小排列好的
C.元素无序
D.元素基本有序
正确答案：B
62、从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为（）。
A.归并排序
B.冒泡排序
C.插入排序
D.选择排序
正确答案：D
63、具有64个结点的完全二叉树的深度为（）。
A.5
B.6
C.7
D.8
正确答案：C
64、在一棵具有五层的满二叉树中，结点的总数为（）。
A.16
B.31
C.32
D.33
正确答案：B
65、前序遍历序列为A，B，C的二叉树共有（）种。
A.2
B.3
C.4
D.5
正确答案：D
66、根据二叉树的定义，具有3个结点的二叉树有（）种树型。
A.3
B.4
C.5
D.6
正确答案：C
67、引入二叉线索树的目的是（）。
A.加快查找结点的前驱或后继的速度
B.为了能在二叉树中方便的进行插入与
C.为了能方便的找到双亲
D.使二叉树的遍历结果唯
正确答案：A
68、树最适合用来表示（）。
A.有序数据元素
B.无序数据元素
C.元素之间无联系的数据
D.元素之间有分支的层次关
正确答案：D
69、堆的形状是一棵（）。
A.二叉排序树
B.满二叉树
C.完全二叉树
D.平衡二叉树
正确答案：C
70、下述几种排序方法中，（）是稳定的排序方法。
A.希尔排序
B.快速排序
C.归并排序
D.堆排序
正确答案：C
71、数据表中有10000个元素，如果仅要求求出其中最大的10个元素，则采用（）算法最节省时间。
A.冒泡排序
B.快速排序
C.简单选择排序
D.堆排序
正确答案：D
72、下列排序算法中，（）不能保证每趟排序至少能将一个元素放到其最终的位置上。
A.希尔排序
B.快速排序
C.冒泡排序
D.堆排序
正确答案：A
73、下述几种排序方法中，要求内存最大的是（）。
A.希尔排序
B.快速排序
C.归并排序
D.堆排序
正确答案：C
74、一个具有1025个结点的二叉树的高h为（）。
A.11
B.10
C.11至1025之间
D.10至1024之间
正确答案：B
75、有关二叉树下列说法正确的是（）。
A.二叉树的度为2
B.一棵二叉树的度可以小于2
C.二叉树中至少有一个结点的度为2
D.二叉树中任何一个结点的度都
正确答案：B