数据结构各章作业题目.docx
《数据结构各章作业题目.docx》由会员分享，可在线阅读，更多相关《数据结构各章作业题目.docx（20页珍藏版）》请在冰点文库上搜索。
数据结构各章作业题目
第一章作业
一、选择题
1.被计算机加工的数据元素不是孤立的，它们彼此之间一般存在某种关系，通常把数据元素之间的这种关系称为（）。
A.规则B.结构C.集合D.运算
2.在Data_Structure=（D,S）中，D是（）的有限集合。
A.数据元素B.算法C.数据操作D.数据对象
3.计算机所处理的数据一般具有某种关系，这是指（）之间存在的某种关系。
A.数据与数据B.数据元素与数据元素
D.数据文件内记录与记录C.元素内数据项与数据项
4.顺序存储表示中数据元素之间的逻辑关系是由（）表示的。
A.指针B.逻辑顺序C.存储位置D.问题上下文
5.链接存储表示中数据元素之间的逻辑关系是由（）表示的。
A.指针B.逻辑顺序C.存储位置D.问题上下文
6.从逻辑上可将数据结构分为（）。
A.动态结构和静态结构B.紧凑结构和非紧凑结构
D.线性结构和非线性结构C.内部结构和外部结构
（）。
7.以下选项属于线性结构的是稀疏数组B.广义表二叉树C.串D.A.
8.以下选项属于非线性结构的是（）。
A.广义表B.队列C.优先队列D.栈
9.以下属于逻辑结构的是（）
A.顺序表B.散列表C.有序表D.单链表
10.一个完整的算法应该具有（）等特性。
A.可执行性、可修改性和可维护性B.可行性、确定性和有穷性
1
C.确定性、有穷性和可靠性D.正确性、可读性和有效性
11.若一个问题既可以用迭代方法也可以用递归方法求解，则（）的方法具有更高的时空效率。
A.迭代B.递归C.先递归后迭代D.先迭代后递归
12.一个递归算法必须包括（）
A.递归部分B.终止条件和递归部分C.迭代部分D.终止条件和迭代部分有关。
算法的时间复杂度与（）13.编译后执行程序的D.B.源程序长度A.问题规模C.计算机硬件运行速度质量二、指出下列各算法的功能并求出其时间复杂度。
（1）n）{intPrime（int据C.数B.数据记录inti=2,x=（int）sqrt（n）;数据项数据字段D.元素
1.顺序表是线性表的（）存储表示。
A.有序B.连续C.数组D.顺序存取
nii的合法的非空线性表采用顺序存储结构，在表中的第2.若长度为个位置插入一个数据元素，值应该是（）
A.B.C.D.n?
0?
i?
n?
?
i?
n1?
1i?
n?
1i0?
1n，那么，在表中顺序查找一个值为x若设一个顺序表的长度为的元素时，在等概率的情况下，3.查找成功的数据平均比较次数为（）
A.B.C.D.2）/（n2（n?
1）/?
12/nnn的顺序表的表尾插入一个新的元素的时间复杂度为（）4.在长度为2O（logn））（On）O（On）（1B.C.D.A.25.数据结构反映了数据元素之间的结构关系。
单链表是一种（）。
A.顺序存储线性表B.非顺序存储非线性表C.顺序存储非线性表D.非顺序存储线性表
2
6.单链表又称为线性链表，在单链表上实施插入和删除操作（）
A.不需移动结点，不需改变结点指针B.不需移动结点，只需改变结点指针
D.只需移动结点，不需改变结点指针既需移动结点，又需改变结点指针C.
7.已知L是带头结点的单链表，则删除首元素结点的语句是（）
A.L=L->next;B.L->next=L->next->next;C.L=L->next->next;D.L->next=L;AmBnBA的末尾，在没有链尾指针的情况下，已知单链表长度为，若将，单链表链接在长度为8.
算法的时间复杂度应为（）。
O（n）O（m?
n））m）O（O（1D.A.C.B.
n个元素的一维数组，建立一个有序单链表的时间复杂度是（）9.给定有2）（OnO（nlogn））O（1O）n（C.B.A.D.2二、算法设计中x（ElemTypex）（SqListL）删除具有给定值的所有元素。
L设计一个算法，从顺序表1.
2.设计一个算法，从有序顺序表中删除所有其值重复的元素，使表中所有元素的值均不相同。
设计一个算法，在非递减有序的带头结点的单链表中删除值相同的多余结点。
3.
3
第三章作业
一、选择题
1.用S表示进栈操作，用X表示出栈操作，若元素的进栈顺序是1234，为了得到1342的出栈顺序，相应的S和X的操作序列为（）
A.SXSXSSXX
B.SSSXXSXX
C.SXSSXXSX
D.SXSSXSXX
2.假设一个栈的输入序列是1，2，3，4，则不可能得到的输出序列是（）
A.1,2,3,4
B.4,1,2,3
C.4,3,2,1
D.1,3,4,2
nij个出栈元素是（）。
其输出序列的第一个元素是，3.已知一个栈的进栈序列为1,2,3,…,则第，n?
ii?
jj?
i?
1B.D.不确定A.C.
p,p,p,?
ppnp?
n,,12,3,?
的值是4.已知一个栈的进栈序列为。
若，其输出序列是，则i321n1（）
in?
in?
i?
1D.C.A.不确定B.
p,p,p,?
pp?
3pn,?
21,,3的值是，其输出序列是5.已知一个栈的进栈序列为，则。
若n12321（）
A.一定是2
B.一定是1
C.可能是1
D.可能是2
p,p,p,?
pp?
1pn,,?
1,2,3的值是，则。
若，其输出序列是6.已知一个栈的进栈序列为3n2311（）
A.一定是2
B.可能是2
C.不可能是2
D.一定是3
p,p,p,?
pp?
3pn3,?
1,2,的值是7.，其输出序列是已知一个栈的进栈序列为，则。
若331n21（）
A.一定是2
B.可能是2
C.不可能是1
D.一定是1
p,p,p,?
pp?
1pn,3,,?
21,的值是8.已知一个栈的进栈序列为，其输出序列是。
若，则n123n1（）
4
n?
ii1i?
n?
D.不确定B.A.C.
9.设栈S和队列Q的初始状态均为空，元素1,2,3,4,5,6,7，依次进入S。
如果每个元素出栈后立即进入队列Q，且7个元素的出队顺序为2,4,3,6,5,1,7，则栈S的容量至少是（）
A.1
B.2
C.3
D.4
10.对中缀表达式求值，在求值过程中扫描到6时，操作数栈和操作符栈的内5）*2?
6*3?
?
23?
*（42容分别是（）
A.3,2,4,2,2和+,*,（,+,*B.3,2,4,4和+,*,（,+
C.3,2,8和+,*,（D.
3,2,8,6和+,*,（,-二、算法设计题》第25页。
）（C1.详见《数据结构题集语言版2.详见《数据结构题集25》第）（C语言版页。
5
第四章作业
11.串是一种特殊的线性表，其特殊性体现在（）
A.可以顺序存储B.数据元素是一个字符C.可以链式存储D.数据元素可以是多个字符（）。
和12.设有两个串TP，求P在T中首次出现的位置的运算叫做C.A.求子串B.模式匹配串替换D.串连接13.下面关于串的叙述中，哪一个是不正确的（）
A．串是字符的有限序列B．空串是由空格构成的串
C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储
14.串的长度是指（）
A．串中所含不同字母的个数B．串中所含字符的个数
C．串中所含不同字符的个数D．串中所含非空格字符的个数
15.两个串相等的充分必要条件是（）
A．串中所含的字符相同B．串中所含字符的个数相同，且对应位置上的字符也相同
C．串中所含的字符个数相同D．串中对应位置上的字符相同
6.已知p=”abcaabbabcabaacbacb”，求出next函数值。
6
第五章作业
一、选择题
16.数组通常具有的操作是（）
A.顺序存取B.直接存取C.散列存取D.索引存取
17.多维数组实际上是由（）实现的。
A.一维数组B.多项式C.三元组表D.简单变量
18.在二维数组A[8][10]中，每一个数组元素A[i][j]占用3个存储空间，所有数组元素相继存放于一个连续的存储空间中，则存放该数组至少需要的存储空间是（）。
A.80
B.100
C.240
D.270
19.一个二维数组A[10][20]按行存放于一个连续的存储空间中，A[0][0]的存储地址是200，每个数组元素占1个存储字，则A[6][2]的地址为（）
A.226
B.322
C.341
D.342
20.一个二维数组A[10][20]按列存放于一个连续的存储空间中，A[0][0]的存储地址是200，每个数组元素占1个存储字，则A[6][2]的地址为（）
A.226
B.322
C.341
D.342
21.在二维数组A[9][10]中，每个数组元素占用3个存储单元，从首地址SA开始按行连续存放，在这种情况下，元素A[8][5]的起始地址为（）
A.SA+141
B.SA+144
C.SA+222
D.SA+255
22.将一个的对称矩阵A的下三角部分按存放在一个一维数组B中，A[0][0]存放在B[0]中，那nn?
iii]在B中的存放位置是行的对角元素A[（）][么第A.B.C.D.2/）i?
i）i/2?
1（23）i/2n（i?
1）i/21（2n?
i?
?
（i23.将一个的对称矩阵A的上三角部分按存放在一个一维数组B中，A[0][0]存放在B[0]中，那nn?
iii]在B中的存放位置是么第（）行的对角元素A[][A.B.C.D.2i/i?
1）i/2）（2n?
/）（i?
3i/2?
（i1）i2i（2n?
?
1AA的对角线及对角线上方的元素以列优先（以列为主序）的方式存24.设是一个的对称矩阵，将n?
na（0?
i,j?
n,i?
j）B中的存放位置是（）则矩阵中任一元素放在一维数组中，在]?
n（[Bn12/）ij7
A.B.C.D.1?
2?
ji?
1?
1）/2?
j）/1）/2?
iij（j?
1）/2?
i?
1（i（ijj（?
25.设n阶三对角矩阵A的三条对角线上的元素被按行压缩存储到一维数组B中，A[0][0]存放于B[0]。
i是（），那么该元素在原始矩阵中的行号若某矩阵元素在B中存放的位置在kA.B.C.D.?
?
?
?
?
?
?
?
3/）?
1（k?
1）/3）/3（k/3k?
1（k二、简答题]15[10][20][A个，按行优先存放于一个连续的存储空间中，维数组设有一个3每个数组元素占426.]98][A[A0][0][0][7][的存储地址是存储字，首元素存放于什么地方。
1000，则676644]A2A[2][0][n]A[][0][m，每个元，设有一个二维数组存放在，假设存放位置在27.）10（）10（]3][3A[个存储单元，问素占1存放在什么位置脚注表示用十进制表示。
（10））（10A假设两种存储对于一个矩阵按行存储和按列存储时的地址之差是多少的任一元素（，28.nn?
]][j[ai）0（0,LOCd相同）以及元素所占存储单元数的开始存储地址]0B[:
3n3?
An中，使得，将其329.设有阶三对角矩阵条对角线上的元素逐行存储到数组B[k]?
A[i][j]B[0]?
A[0][0]，求，且
ijk的下标变换公式。
，表示
（1）用kij的下表变换公式。
表示
（2）用，A[0][0]nn?
BA存放中，的对称矩阵，将其下三角部分按行压缩存放于一个一维数组30.设有一个A[i][j]BBBA应存于一维数组中的任意一个元素
（1）一维数组有多少个元素
（2）于[0]，试问：
的什么下标位置
A[0][0]nn?
BA存放的对称矩阵中，，将其上三角部分按列压缩存放于一个一维数组31.设有一个A[i][j]BBBA应存于一维数组，试问：
于[0]
（1）
（2）有多少个元素中的任意一个元素一维数组的什么下标位置
8
第六章作业
一、选择题
n个结点的树的所有结点的度数之和为（）。
32.一颗有2n1n?
n-1nA.C.B.D.
hnm个叶结点，则（）设一颗高度为个结点，其中有的满二叉树有33.
hC.D.A.B.1?
n?
21hn?
?
nh?
m?
mh?
m?
234.一颗有124个叶结点的完全二叉树最多有（）个结点。
A.247
B.248
C.249
D.250
35.一颗有129个叶结点的完全二叉树最少有（）个结点。
A.254
B.255
C.257
D.258
36.设完全二叉树的第6层有24个叶结点，则此树最多有（）个结点。
A.55
B.79
C.81
D.127
37.具有1000个结点的完全二叉树的次底层的叶结点个数为（）。
A.11
B.12
C.24
D.36
R[n]n中，38.用顺序存储的方法将当个结点的完全二叉树中所有结点按层逐个顺序存放在一维数组R[0]R[i]有左孩子，则左孩子是（）时，若结点。
编号为0的根结点存放于
R[2i?
2]]12]R[2i]R[i?
2R[i?
1B.D.A.C.
R[n]n中，当个结点的完全二叉树中所有结点按层逐个顺序存放在一维数组39.用顺序存储的方法将R[0]R[i]有右孩子，则右孩子是（）。
0的根结点存放于时，若结点编号为R[2i?
2]]i?
1]1R[2i?
]R[2iR[2C.D.A.B.
40.二叉树的叶结点在前序、中序和后序遍历过程中的相对顺序（）。
A.发生改变B.不发生变化C.无法确定D.以上均不对
nmnm前的条件是（）设在，。
为一颗二叉树上的两个结点，在该二叉树的中序遍历序列中41.nmnmnmnm的子孙是C.在左方D.B.A.在右方是的祖先abdecdbeac，则该二叉树的后序遍历顺序是（）。
设一颗二叉树的前序序列为42.，中序序列为
9
abdecdebacdebcaabedcC.A.D.B.
badcebdeca，则该二叉树的前序遍历顺序是（）设一颗二叉树的中序序列为。
，后序序列为43.
adbecdecabdebacabcdeA.C.B.D.
44.对二叉树的结点从1开始连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左、右孩子中，其左孩子编号小于其右孩子编号，则可采用（）遍历实现二叉树的结点编号。
A.先序B.中序C.后序D.层次序
TTTT中结点的（）如果中结点的先根遍历顺序对应是由有序树遍历转换成的二叉树，那么45.22顺序。
A.前序B.中序C.后序D.层次序
TTTT中结点的（）是由有序树中结点的后根遍历顺序对应转换成的二叉树，那么遍历46.如果22顺序。
A.前序B.中序C.后序D.层次序
n个权值构造出来的Huffman树共有用（）个结点。
47.
A.B.C.D.112nn?
2n2n?
1?
48.由权值为8,4,5,7的4个叶结点构造一颗Huffman树，该树的带权路径长度为（）。
A.24B.36C.48D.72
二、简答题为距离根最远的叶结点所在的层次，试回答以下问题：
49.设二叉树根结点所在层次为1，树的深度d的满二叉的完全二叉树的不同二叉树的棵数；
（2）试精确给出深度为dd
（1）试精确给出深度为树的不同二叉树棵数。
nnnm的结点，试问有个度为1的结点，有个度为2的结点，……，有个度为50.如果一棵树有m21的结点多少个度为0EBCDAFHIGJABECDFGHIJ画出这棵二叉。
，中序遍历序列为
（1）已知一棵二叉树的前序遍历序列为51.
）。
（
（2）树；给出这棵二叉树后序遍历序列；（3）画出这棵二叉树转换成对应的树或森林组成，各字母在电文中出现的频率分别为852.假定用于通信的电文仅有个字母A,B,C,D,E,F,G,H编码，并给出该电文的总码数。
Huffman85,25,3,6,10,11,36,4。
试为这个字母设计不等长三、算法设计10
53.设二叉树的存储结构为二叉链表，编写一个递归算法，统计二叉树中度为1的结点个数。
54.设二叉树的存储结构为二叉链表，编写一个递归算法，统计二叉树中度为2的结点个数。
TT的叶结点个数。
-兄弟链表作为其存储表示，编写一个算法统计树55.设树以孩子TT的高度。
兄弟链表作为其存储表示，编写一个算法计算树-设树56.以孩子
11
第七章作业
一、选择题
n个顶点且每一对不同顶点间都有一条边的无向图被称为（）。
1.具有A.完全无向图B.无向连通图C.无向强连通图D.无向树图
2.一个有n个顶点的无向图中边数最多有（）条。
A.B.C.D.n2?
11））/n（n?
n（nn23.对于具有个顶点的强连通图，其有向边条数至少是（））n?
1n（A.B.C.D.n21n?
n?
n1?
G是一个非连通无向图，有15条边，则该图的顶点数至少有（）个。
4.设
A.5
B.6
C.7
D.8
ns，则所有顶点的入度之和为（）个顶点的有向图中，若所有顶点的岀度之和为5.在一个具有。
nss+1
C.D.A.
nn一个有（）个顶点和。
条边的无向图一定是6.
D.有环的不连通图C.无环的A.重连通图B.
（）。
7.无向图的邻接矩阵是一个对角矩阵C.上三角矩阵D.B.A.对称矩阵零矩阵
。
个顶点和e条边的无向图采用邻接矩阵存储，零元素的个数为（）8.有n22e?
2nn?
ee2eB.C.D.A.
AGi（）A存储，则顶点。
的入度等于9.带权有向图中用邻接矩阵ii列非∞的元素之和B.第A.第行非∞的元素之和ii的元素个数列非∞且非0C.第第行非∞且非0的元素个数D.
en条边，采用邻接矩阵时，遍历图的顶点所需时间为设图有10.（）个顶点和。
2）（On）（）O（nneOeO（）A.D.B.C.
。
（）en11.设图有个顶点和条边，采用邻接表时，遍历图的顶点所需时间为21
2）（nO）neOn?
e）（O（e）O（D.C.B.A.
（）次序遍历。
图的深度优先搜索类似于树的12.
D.层C.后根A.先根B.中根（）次序遍历。
13.图的广度优先搜索类似于树的D.层C.后根A.先根B.中根（）。
14.采用邻接表存储的图的深度优先搜索算法类似于二叉树的D.层次遍历C.后序遍历A.中序遍历B.前序遍历
（）。
15.采用邻接表存储的图的广度优先搜索算法类似于二叉树的层次遍历后序遍历D.C.A.中序遍历B.前序遍历
。
如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是（）16.一棵树有回路D.强连通图B.连通图C.A.
GG生成树中。
的17.如果一个连通网络（）中各边权值互不相同，权重最小的边一定包含在深度优先D.B.任何C.广度优先A.最小
。
任何一个连通图的最小生成树（）18.
可能不存在D.有一棵或多棵C.一定有多棵A.只有一棵B.
en（）个顶点和条边。
条边的连通图的生成树有19.一个有D.B.C.A.en1?
nn?
1nlogn条边，则应该选通个顶点的带权连通图有（）20.设一个n算法来求这个图的最小生成树，2从而使计算时间较少。
A.Prim
B.Kruskal
C.DFS
D.BFS
21.求最短路径的Dijkstra算法的时间复杂度为（）。
2D.A.B.C.）nO（）（e）neO（On）?
O（n22.求最短路径的Floyd算法的时间复杂度为（）。
23D.A.B.C.）nO（（）nO）nO（）O（nene条边，如果用邻接表作为它的存储结构，则拓扑排序的时间复杂度为23.设有向图具有个顶点和（）。
13
2D.B.C.A.）（nO）（O（n）ne）O（n?
eO24.设有向图具有n个顶点和e条边，如果用邻接矩阵作为它的存储结构，则拓扑排序的时间复杂度为（）。
2D.C.A.B.）O（n）O（ne）O（n?
eeO（nlog）2二、应用题25.针对图所示的有向图，画出该图的邻接矩阵、邻接表和逆邻接表。
1
DAebEBgadFCfc
图1图2
a开始进行深度优先遍历，给出2个可得到的顶点访问序列；从顶对图2所示的无向图，从顶点26.a开始进行广度优先遍历，给出2个可得到的顶点访问序列。
点
27.已知一个带权连通图如图3所示，分别使用Prim算法和Kruskal算法求其最小生成树。
B
c3b12a201215AC510E165151098864DFd8e9f
图3图4
a到其余各顶点的最短路径及路径长算法求从顶点所示，4用Dijkstra28.已知一个带权有向图如图度。
29.如图所示的AOE网，求
（1）完成此工程最少要多少天（设弧上的权值为天数）；
ae（a）l（a）；和最迟开始时间每项活动
（2）的最早开始时间iii（3）哪些是关键活动；
14
（4）是否存在某些活动，当其提高速度后能使整个工程缩短工期
6I432HC
5图51
第九章作业
一、选择题
30.顺序查找算法适用于（）。
A.线性表B.查找树C.查找网D.连通图
31.顺序查找法适用于线性表的（）。
A.散列存储B.压缩存储C.索引存储D.顺序或链接存储
n的顺序表时，平均查找长度为（）32.采用顺序查找方式查找长度为（n?
1）/2（n?
1）/22n/nB.D.A.C.
a,b,c,d,e}放在顺序表中，他们的查找概率分别为{,,,.015,}个关键吗如果有5{，可使平均查找33.
长度达到最小的存放方式是（）。
d,a,b,c,ee,d,c,b,aa,b,c,d,ea,c,e,d,bD.B.A.C.
n的有序单链表，若查找每个元素的概率相等，则顺序查找表中任一元素的查找成功对于长度为34.
的平均查找长度为（）
（n?
1）/2（n?
1）/22/n/4nB.
升级会员 