智慧树数据结构答案.docx
《智慧树数据结构答案.docx》由会员分享，可在线阅读，更多相关《智慧树数据结构答案.docx（27页珍藏版）》请在冰点文库上搜索。
智慧树数据结构答案
绪论
1
【单选题】（2分）
（C）在貝著作《讣算机程序设计艺术》中，开创了数据结构的最初体系。
（）
A.理查徳•卡普
B.史蒂芬・古克
C.腐纳徳•克努特
D.尼古拉斯・沃斯
2
【单选题】（2分）
（A）提出了著名的公式程序=算法+数据结构。
（）
A.尼古拉斯・沃斯
B.史蒂芬•古克
C.唐纳徳•克努特
D.理查徳•卡普
3
【单选题】（2分）
数据结构课程不是（A）课程的先修课程。
A.高级语言程序设计
B.操作系统
C.数据库原理
D.计算机组成原理
4
【单选题】（2分）
下面哪个不是常见的数据结构。
（B）
A.线性表
B.线性方程组
C.树
D.栈
5
【单选题】（2分）
下面说法错误的是（A）。
A.我国高校从20世纪50年代就开设了数据结构这一课程
B.通过数据结构课程，能够掌握数据结构的逻辑结构、存储结构及实现算法
C.精心选择的数据结构能够带来更高的计算速度和存储效率
D.程序是为处理计算机问题编制的一组指令集
第一章
1
【单选题】（2分）
（A）是组成数据具有独立含义不可分割的最小单位。
（）
A.数据项
B.数据元素
C.数据对象
D.数据变量
2
【单选题】（2分）
数据逻辑结构中非线性结构包括（B
A.顺序结构和链式结构
B.树形结构和图形结构
C.树形结构和队列结构
D.图形结构和堆栈结构
3
【单选题】（2分）
设某数据结构的二元组形式表示为A=（D,R）,D={01,02,03,04,05,06.07,0&09},R={r},r={<01,02>,<01,03>,<01,04>,<02,05>,<02,06>,<03,07>,<03,08>,<03,09>}.则数据结构A是（B）。
A.线性结构
B.树形结构
C.图形结构
D.物理结构
4
【单选题】（2分）
数据结构的主要研究内容包括数据的（A）以及数据的运算和操作。
A.逻辑结构、物理结构
B.抽象结构、物理结构
C.离散结构、抽象结构
D.逻借结构、抽象结构
5
【单选题】（2分）
数据结构被形象化的泄义为一个二元组Group=（D,S）,其中D为数据元素的有限集，S为（B）的有限集。
A操作
B.关系
C.结构
D.运算
6
【单选题】（2分）
线性结构中的数据元素具有（D）关系。
A.—对多关系
B.多对多关系
C.多对一关系
D.—对一关系
7
【单选题】（2分）
对一个算法的评价，不包括如下（C）方而的内容。
A.时空复杂度
B.健壮性和可读性
c・并行性
D・正确性8
【单选题】（2分）
下列时间复杂度中最好的是（B）。
A.O（n2）
B.0（Iog2n）
C.O（n）
D.O（2n）
9
【单选题】（2分）
以下算法的时间复杂度是（B）oi=l;while（i<=n）i=i*3;
A.O（Iog2n）
B.0（Iog3n）
C.O（n）
D.O（nA3）
10
【单选题】（2分）
以下算法:
s=0;for（i=0;ifor（j=0;jA.O（Iog2n）
B.0（n）
C.O（nA2）
D.O（nA3）
第二章
【单选题】（2分）
下面关于线性表的叙述中，错误的是哪一个？
（A）
A•线性表釆用顺序存储，便于插入和删除操作
B•线性表采用顺序存储，必须占用一片连续的存储单元
C•线性表釆用链接存储，便于插入和删除操作2
【单选题】（2分）
如果最常用的操作是取第i个结点及其前驱，则采用（C）存储方式最节省时间。
A.单链表
B.双链表
C.顺序表
D.单循环链表
3
【单选题】（2分）
线性表采用顺序存储时，存储地址（C）oA•可以与逻辑顺序不一致
B-zk是不连续的
C.必须是连续的
D.连续与否均可
4
【单选题】（2分）
线性表采用链式存储时，结点的存储地址（C）o
A.和头结点的存储地址相连续
B.必须是连续的
C.连续与否均可
D.必须是不连续的
5
【单选题】（2分）
带头结点的单链表head为空的判定条件是（A）
A.head->next==NULL
B.head==NULL
C.head!
=NULL
D.head->next==head
6
【单选题】（2分）
设指针变量p指向单链表结点A,则删除结点A的后继结点B需要的操作为（C）。
A.p=p・>nextnext
B.p=p・>next
C.p->next=p・>next->next
D.p->next=p
7
【单选题】（2分）
在一个长度为n（n>l）的单链表上，设有头指针和尾指针，执行（B）操作与链表的长度有关。
A.删除单链表中的第一个元素
B.删除单链表中的最后一个元素
C.在单链表的最后一个元素后插入一个新元素
D.在单链表的第一个元素前插入一个新元素
8
【单选题】（2分）
若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用（C）存储方式最节省运算时间。
A.双链表
B.给出表头指针的单循环链表
C.带头结点的双循环链表
D.单链表
9
【单选题】（2分）
在双向链表存储结构中，删除p所指的结点时须修改指针（A）o
A.p->prior->next=p->next;p->next->prior=p->prior;
B.p->prior=p->prior->prior;p->prior->next=p;
C.p->next=p->prior->prior;p->prior=p->next->next;
D.p->next->prior=p;p・>next=p->next->next;
10
【单选题】（2分）
建立一个长度为n的有序单链表的时间复杂度为（A）
A.0（n2）
B.O（l）
C.O（n）
D.O（log2n）
第三章
1
【单选题】（2分）
若让元素C,h,i,n,a依次进栈，则出栈次序不可能出现在（B）种情况。
A.h,i,a,n,C
B.n9i,C,h9a
C.a,n,ith,C
D.h,C,a,n,i
2
【单选题】（2分）
若已知一个栈的入栈序列是1,2,3,…，n,英输岀序列为pl,p2,p3,…，pn,若pl=n,则pi为（D）o
A.n-i
B.不确泄
C.i
D.n-i+1
3
【单选题】（2分）
设计一个判别表达式中左，右括号是否配对出现的算法，采用（C）数据结构最佳。
A.线性表的顺序存储结构
B.线性表的链式存储结构
C.栈
D.队列
4
【单选题】（2分）
若栈采用顺序存储方式存储，现两栈共享空间top[i]代表第i个栈（i=l,2）栈顶,栈1的底在V⑴，栈2的底在V[m],则栈满的条件是（C）
A.|top[2]-top[l]|=0
B.top[l]=top[2]
C.top[l]+1=top[2]
D.top[l]+top[2]=m
5
【单选题】（2分）
为解决计算机主机与打印机间速度不匹配问题，通常设一个打印数据缓冲区。
主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。
该缓冲区的逻辑结构应
该是（B）o
A.栈
B.队列
C.有序表
D.线性表
6
【单选题】（2分）
用链接方式存储的队列，在进行删除运算时（B）。
A.仅修改头指针
B.头、尾指针可能都要修改
C.头、尾指针都要修改
D.仅修改尾指针
7
【单选题】（2分）
栈和队列的共同点是（B）。
A.都是先进先出
B.只允许在端点处插入和删除元素
C.都是先进后出
D.没有共同点
8
【单选题】（2分）
设栈S和队列Q的初始状态为空，元素el、e2、e3、e4、e5和e6依次进入栈S,—个元素出栈后即进入Q,若6个元素出队的序列是e2、e4、e3、e6、e5和el,则栈S的容量至少应该是（D）»
A.6
B.4
C.2
D.3
9
【单选题】（2分）
循环队列存储在数组A[O..m]中，则入队时的操作为（C）o
A.rear=rear+1
B.rear=（rear+l）%（m-l）
C.rear=（rear+l）%（m+l）
D.rear=（rear+l）%m
10
【单选题】（2分）
递归过程或者函数调用时处理参数和返回地址需要用到（D）数据结构。
A.队列
B.线性表
C.二叉树
D.栈
第四章
1
【单选题】（2分）
串是一种特殊的线性表，其特殊性体现在（A）。
A.数据元素是一个字符
B.数据元素可以是多个字符若
C.可以顺序存储
D.可以链式存储
2
【单选题】（2分）
若串S=“master”其子串的个数是（B）。
A.21
B.22
C.23
D.20
3
【单选题】（2分）
串的长度是指（A）。
A.串中所含字符的个数
B.串中所含不同字母的个数
C.串中所含非空格字符的个数
■
D.串中所含不同字符的个数
4
【单选题】（2分）
设有两个串P和q・其中q是P的子串，求q在p中首次出现的位豊的算法称为（C）。
A.求子串
B.求串长
C.匹配
D.联接
5
【单选题】（2分）
数组A[0..4,-l,3,5..7]中含有元素的个数（B）o
A.55
B.45
C.36
D.16
6
【单选题】（2分）
假设以行序为主序存储二维数组A=array[1..100,1..100],设每个数据元素占2个存储单元,基地址为10,则LOC[5,5]=（D）o
A.808
B.1020
C.1010
D.818
7
【单选题】（2分）
设有数组A[i,j],数组的每个元素长度为3字节，i的值为1到&j的值为1到10,数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5,8]的存储首地址为（B）。
A.BA+225
B.BA+180
C.BA+141
D.BA+222
8
【单选题】（2分）
设有一个10阶的对称矩阵A,采用压缩存储方式，以行序为主存储，all为第一元素，苴存储地址为每个元素占一个地址空间，则a85的地址为（C）o
A.40
B.32
C.33
D.13
9
【单选题】（2分）
广义表（（a,b,c,d））的表头是（C）。
A.（b,c,d）
B.（b,c）
C・（abc,d）
D.a
10
【单选题】（2分）
广义表A=（ab（c，d）,©（f,g）））,则Head（Tail（Head（Tail（Tail（A）））））的值为（A）。
A.d
B.（d）
C.c
D・（g）
第五章
1
【单选题】（2分）
由3个结点可以构造岀多少种不同的二叉树？
（D）
A.2
B.3
C.4
D.5
2
【单选题】（2分）
一棵完全二叉树上有1001个结点，其中叶子结点的个数是（C）。
A.254
B.500
C.501
D.250
3
【单选题】（2分）
一个具有1025个结点的二叉树的高h为（C）<>
A.10
B.10至1024之间
C.11至1025之间
D.11
4
【单选题】（2分）
对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于英左、右孩子的编号，同一结点的左右孩子中，英左孩子的编号小于其右孩子的编号，可采用（A）遍历实现编号。
A.后序
B.先序
C.从根开始按层次遍历
D冲序
5
【单选题】（2分）
已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历结果为（C）。
A.CBEDFA
B.不确泄
C.CBEFDA
D.FEDCBA
6
【单选题】（2分）
引入二叉线索树的目的是（C）o
A.为了能在二叉树中方便的进行插入与删除
B.为了能方便的找到双亲
D使二叉树的遍历结果唯一
C.加快查找结点的前驱或后继的速度
7
【单选题】（2分）
在下列存储形式中，（A）不是树的存储形式？
A.顺序存储表示法
B.孩子兄弟表示法
C.孩子链表表示法
D.双亲表示法
8
【单选题】（2分）
利用二叉链表存储树，则根结点的右指针是（D）。
A.指向最左孩子
B.指向最右孩子
C.非空
D.空
【单选题】（2分）
设F是一个森林，B是由F变换得的二叉树。
若F空的结点有（B）个。
A.nT
B.n+1
C.n+2
D.n
10
A.100
B.101
C.102
D.99
第六章
1
【单选题】（2分）
具有4个顶点的无向完全图有（C）条边。
B.20
C.6
D.16
2
駕*議向图至少应有（D）条边才能确保是-个连通图。
A.6
B.8
D.5
3
【单选题】（2分）宀
在_个无向图中，所有顶点的度数之和等于所有边数的（C）倍
A.1/2
B.1
C.2
4
【单选题】（2分）
任何一个无向连通图的最小生成树（C）°
A.只有一棵
B・可能不存在
C・有一棵或多棵
D•—泄有多棵
5
【单选题】（2分）
设无向图6=（V,E）,G'=（V1,E'>,如果G是G的生成树，则下而说法错误的是（D）。
AG为G的极小连通子图，且V'=V
B.G*为G的子图
C.G，为G的无环子图
DG为G的连通分量
6
【判断题】（2分）
无向图的邻接矩阵一泄是对称矩阵，有向图的邻接矩阵一泄不是对称矩阵。
（B）
A.对
B.错
7
【单选题】（2分）
某无向^G=（V,E）,其中:
V=（a,b,c,d,e,f）,E=（（a,b）,（a,e）,（a,c）,（b,e）,（c,f）,（f,d）,（e,d））,对该图进行深度优先遍历，则顶点序列正确的是（B）o
A.a’c尢e»b”d
B・a,e,d,tc,b
C・a,e,b,c‘td
D.a,b,e,c,ctf
8
【单选题】（2分）
已知有向图G=（V,E）,其中V={vl/v2/v3/v4/v5/v6},E={///////}/G的拓扑序列是（B）。
A.vl,v4/v3/v5/v2/v6
B.v3/vl/v4/v5/v2/v6
C・v3N4，vbv5，v2,\/6
9
【单选题】（2分）
关键路径是事件结点网络中（A）。
A.从源点到汇点的最长路径
B.最短的回路
C.从源点到汇点的最短路径
D.最长的回路
10
【单选题】（2分）
普里姆算法是一种通过选点法构造最小生成树的算法。
时间复杂度为（D）。
A.O（eloge）
B.0（n+e）
C.O（e2）
D.O（n2）
第七章
1
【单选题】（2分）
有一个长度为12的有序表，按折半査找法对该表进行查找，在表内各元素等概率的情况下査找成功所需的平均比较次数为（D）。
A.35/12
B.39/12
C.43/12
D.37/12
2
【单选题】（2分）
对于线性表（7,34,55,25,64,46,20,10）进行散列存储时，若选用H（K）二K%9作为散列函数，则散列地址为1的元素有（C）个，
A.3
B.1
C.4
D.2
3
【单选题】（2分）
顺序查找不论在顺序线性表中还是在链式线性表中的时间复杂度为（B）。
A.O（nl/2）
B.O（n）
C.O（log2n）
D.O（n2）
4
【单选题】（2分）
设一组初始记录关键字序列为（13,1&24,35,47,50,62,83,90,115,134）,则利用二分法查找关键字90需要比较的关键字个数为（C）。
A.3
B.1
C.2
D.4
5
【单选题】（2分）
设某散列表的长度为100,散列函数H（k）=k%P,则P通常情况下最好选择（D
A.99
B.93
C.91
D.97
6
【单选题】（2分）
设有一组初始记录关键字序列为（34,76,45,1&26,54,92）,则由这组记录关键字生成的二叉排序树的深度为（C）o
A.7
B.6
C.4
D.5
7
【单选题】（2分）
二叉排序树中左子树上所有结点的值均（C）根结点的值。
A.!
=
B.>
C.<
D=
8
【单选题】（2分）
从n个结点的二叉排序树中查找一个元素时，最坏情况下时间复杂度为（D）o
A.0（n2）
B.O（log2n）
C.0（nl/2）
D.O（n）
9
【单选题】（2分）
在平衡二叉树中，每个结点平衡因子的绝对值必须（C）o
A・小于1
B.等于0
C.小于等于1
D.大于1
10
【单选题】（2分）
深度为4的平衡二叉树中至少有（D）个结点。
A.10
B.8
C.6
D.7
第八章
1
【单选题】（2分）
用某种排序方法对线性表｛25,84,2匕47」5,27,68,35,20｝进行排序时,元素序列的变化情况如下:
（1）
25,
84,
21,47,
15,
27,6&
35,
20
（2）
20,
15>
21,25,
47,
27,6&
35,
84
（3）
15,
20.
21,25,
35,
27,47,
68,
84
（4）
15,
20.
21,25,
27,
35t47,
68,
84
则采用的排序方法是（
C）o
A.直接选择排序
B.希尔排序
C.快速排序
D.归并排序
【单选题】（2分）
对记录的关键字为｛52,26,38,80,70,90,8,30,40,20｝进行排序，各趟排序结束时的结果为:
（1）
51,
26,
>38
80,
70,
90,
，&30,
40.20
（2）
51,
&
30,
40,
20,
90,
26,38,
80,70
（3）
26,
&
30,
40,
20,
80,
51,38,
90,70
（4）
8,
20,
26,
30,
38,
40,
51,70,
80.90
则采用的排序方法是（A）。
A.希尔排序
B.直接选择排序
C.快速排序
D.归并排序
3
【单选题】（2分）
设一组初始记录关键字序列（5,2,6,3,8）,以第一个记录关键字5为基准进行一趟快速
排序的结果为（B）0
A.293,6,5,8
B.3,
2,5,
6,
8
C.3,
2,5,
8,
6
D.2,
3,5,
8,
6
4
【单选题】
（2分）
下列四种排序中（D）的空间复杂度最大。
A.冒泡排序
B.堆排序
C.插入排序
D.归并排序
5
【单选题】（2分）
快速排序的空间复杂度为（A）。
A.O（log2n）
B.O（n3）
C.O（n）
D.O（n2）
6
【单选题】（2分）
下面哪种排序算法是稳左的排序算法（B）。
A.希尔排序
B.归并排序
C.快速排序
D.宜接选择排序
7
【单选题】（2分）
下面哪种排序算法的时间复杂度为0（nlog2n）。
（D）
A.冒泡排序
B.直接插入排序
c・直接选择排序
D.快速排序
8
【单选题】（2分）
设一组初始记录关键字序列为（25,50,15,35,80,85,20,40,36,70）,英中含有5个长度为2的有序子表，则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为（C）。
A.15,
25,35,
50,
80,
20,
85,
40.
70,36
B.15,
25,35,
50,
80,
85,
20,
36,
40,70
C.15»
25,35,
50,
20,
40,
80,
85,
36,70
D.15,
25,35,
50,
80,
20,
36,
40,
70,85
9
【单选题】（2分）
利用直接插入排序法的思想建立一个有序线性表的时间复杂度为（B）。
A.O（log2n）
B.O（n2）
C.O（n）
D.O（nlog2n）
10
【单选题】（2分）
设一组初始记录关键字序列为（CbH,C,Y,P,A,M,S,R,D,F,X）,则按字母升序的第一趟冒泡排序结朿后的结果是（B）。
A.F,
H,
C,
D,
P,
A.
M,
Q，
R,St
Y,
X
B.H,
C,
Cb
P,
A,
M,
S,
R,
D,F,
X,
Y
C.A,
D,
C,
R,
F,
Q,
M,
S,
Y,P,
H,
X
D.P,
A,
C,
S,
Q,
D,
F,
X,
R,H,
M,
Y
升级会员 