数据结构习题集附答案Word文件下载.docx
《数据结构习题集附答案Word文件下载.docx》由会员分享，可在线阅读，更多相关《数据结构习题集附答案Word文件下载.docx（60页珍藏版）》请在冰点文库上搜索。
5.线性结构中元素之间存在________关系,树形结构中元素之间存在________关系,图形结构中元素之间存在________关系。
6.算法的五个重要特性是________、________、________、________、________。
7.数据结构的三要素是指________、________和________。
8.链式存储结构与顺序存储结构相比较,主要优点是________________________________。
9.设有一批数据元素,为了最快的存储某元素,数据结构宜用
________结构,为了方便插入一个元素,数据结构宜用________结构。
四、算法分析题
1.求下列算法段的语句频度及时间复杂度
forforx=x+1;
分析：
该算法为一个二重循环，执行次数为内、外循环次数相乘，但内循环次数不固定，与外循环有关，因些，时间频度T=1+2+3+…+n=n*/2有1/4≤T/n2≤1，故它的时间复杂度为Ｏ,即Ｔ与n2数量级相同。
2.分析下列算法段的时间频度及时间复杂度forforforx=i+j-k;
分析算法规律可知时间频度T=1+++...+由于有1/6≤T/n3≤1，故时间复杂度为Ｏ第二章线性表
1.一个线性表第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的地址是。
A．110B．108C．100D．120
2.向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动个元素。
A．64B．63C．
63.5D．7
3.线性表采用链式存储结构时，其地址。
A．必须是连续的B．部分地址必须是连续的C．一定是不连续的D．连续与否均可以
4.在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行。
A．s-next=p;
p-next=s;
B．s-next=p-next;
C．s-next=p-next;
p=s;
D．p-next=s;
s-next=p;
5.在一个单链表中，若删除p所指结点的后续结点，则执行。
A．p-next=p-next-next;
B．p=p-next;
p-next=p-next-next;
C．p-next=p-next;
D．p=p-next-next;
6.下列有关线性表的叙述中，正确的是。
A．线性表中的元素之间隔是线性关系B．线性表中至少有一个元素C．线性表中任何一个元素有且仅有一个直接前趋D．线性表中任何一个元素有且仅有一个直接后继
7.线性表是具有n个的有限序列
2.如果没有提供指针类型的语言，就无法构造链式结构。
3.线性结构的特点是只有一个结点没有前驱，只有一个结点没有后继，其余的结点只有一个前驱和后继。
4.语句p=p-next完成了指针负值并使p指针得到了p指针所指后继结点的数据域值。
5.要想删除p指针的后继结点，我们应该执行q=p-next；
p-next=q-next；
free。
1.已知P为单链表中的非首尾结点，在P结点后插入S结点的语句为：
________。
2.顺序表中逻辑上相邻的元素物理位置相邻，单链表中逻辑上相邻的元素物理位置________相邻。
3.线性表L＝采用顺序存储，假定在不同的n＋1个位置上插入的概率相同，则插入一个新元素平均需要移动的元素个数是________。
4.在非空双向循环链表中，在结点q的前面插入结点p的过程如下：
p-prior=q-prior;
q-prior-next=p;
p-next=q;
________;
5.
已知L是无表头结点的单链表，是从下列提供的答案中选择合适的语句序列，实现：
表尾插入s结点的语句序列是________。
A．p-next=s;
B．p=L;
C．L=s;
D．p-next=s-next;
E．s-next=p-next;
F．s-next=L;
G．s-next=null;
H．whilep=p-next;
I．whilep=p-next;
四、算法设计题
1.试编写一个求已知单链表的数据域的平均值的函数。
2.已知带有头结点的循环链表中头指针为head,试写出删除并释放数据域值为x的所有结点的c函数。
3.某百货公司仓库中有一批电视机，按其价格从低到高的次序构成一个循环链表，每个结点有价格、数量和链指针三个域。
现出库m台价格为h的电视机，试编写算法修改原链表。
4.某百货公司仓库中有一批电视机，按其价格从低到高的次序构成一个循环链表，每个结点有价格、数量和链指针三个域。
现新到m台价格为h的电视机，试编写算法修改原链表。
5.线性表中的元素值按递增有序排列，针对顺序表和循环链表两种不同的存储方式，分别编写C函数删除线性表中值介于a与b之间的元素。
6.设A=,B=是两个给定的线性表,它们的结点个数分别是n和m,且结点值均是整数。
若n=m，且ai=bi，则A=B；
若nm，且ai=bi，则AB；
若存在一个j，jm，jn，且ai=bi，若ajbj，则AB，否则AB。
试编写一个比较A和B的C函数，该函数返回-1或0或1，分别表示AB或A=B或AB。
7.试编写算法,删除双向循环链表中第k个结点。
8.线性表由前后两部分性质不同的元素组成,m和n为两部分元素的个数,若线性表分别采用数组和链表两种方式存储,编写算法将两部分元素换位成,分析两种存储方式下算法的时间和空间复杂度。
9.用循环链表作线性表和的存储结构,头指针分别为ah和bh，设计C函数，把两个线性表合并成形如的线性表，要求不开辟新的动态空间,利用原来循环链表的结点完成合并操作,结构仍为循环链表,头指针为head,并分析算法的时间复杂度。
10.试写出将一个线性表分解为两个带有头结点的循环链表，并将两个循环链表的长度放在各自的头结点的数据域中的C函数。
其中,线性表中序号为偶数的元素分解到第一个循环链表中,序号为奇数的元素分解到第二个循环链表中。
11.试写出把线性链表改为循环链表的C函数。
12.己知非空线性链表中x结点的直接前驱结点为y,试写出删除x结点的C函数。
第三章栈和队列
1.一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是。
A．edcbaB．decbaC．dceabD．abcde
2.栈结构通常采用的两种存储结构是。
A．线性存储结构和链表存储结构B．散列方式和索引方式C．链表存储结构和数组D．线性存储结构和非线性存储结构
3.判定一个栈ST为空的条件是。
A．ST-〉top。
=0B．ST-〉top==0C．ST-〉top。
=m0D．ST-〉top=m0
4.判定一个栈ST为栈满的条件是。
A．ST-top。
=0B．ST-top==0C．ST-top。
=m0-1D．ST-top==m0-1
5.一个队列的入列序列是1,2,3,4,则队列的输出序列是。
A．4,3,2,1B．1,2,3,4C．1,4,3,2D．3,2,4,1
6.循环队列用数组A存放其元素值，已知其头尾指针分别是front和rear则当前队列中的元素个数是。
A．%mB．rear-front+1C．rear-front-1D．rear-front
7.栈和队列的共同点是A．都是先进后出B．都是先进先出C．只允许在端点处插入和删除元素D．没有共同点
8.表达式a*-d的后缀表达式是。
A．abcd*+-B．abc+*d-C．abc*+d-D．-+*abcd
9.4个元素a1，a2，a3和a4依次通过一个栈，在a4进栈前，栈的状态，则不可能的出栈序是。
A．a4，a3，a2，a1B．a3，a2，a4，a1C．a3，a1，a4，a2D．a3，a4，a2，a1
10.以数组Q存放循环队列中的元素，变量rear和qulen分别指示循环队列中队尾元素的实际位置和当前队列中元素的个数，队列第一个元素的实际位置是。
A．rear－qulenB．rear－qulen＋mC．m－qulenD．1＋%m
二、填空题
1.栈的特点是________，队列的特点是________。
2.线性表、栈和队列都是________结构,可以在线性表的________位置插入和删除元素，对于栈只能在________插入和删除元素，对于队列只能在________插入元素和________删除元素。
3.一个栈的输入序列是12345,则栈有输出序列12345是________。
4.设栈S和队列Q的初始状态皆为空，元素a1，a2，a3，a4，a5和a6依次通过一个栈，一个元素出栈后即进入队列Q，若6个元素出队列的顺序是a3，a5，a4，a6，a2，a1则栈S至少应该容纳________个元素。
三、算法设计题
1.假设有两个栈s1和s2共享一个数组stack,其中一个栈底设在stack处，另一个栈底设在stack处。
试编写对任一栈作进栈和出栈运算的C函数pushA．一个串的字符个数即该串的长度B．一个串的长度至少是1C．空串是由一个空格字符组成的串D．两个串S1和S2若长度相同，则这两个串相等
2.字符串“abaaabab“的nextval值为A．B．C．D．
3.字符串满足下式,其中head和tail的定义同广义表类似,如head=‘x’,tail=‘yz’,则s=。
concat）,head）））=‘dc’。
A．abcdB．acbdC．acdbD．adcb
4.串是一种特殊的线性表,其特殊性表现在A．可以顺序存储B．数据元素是一个字符C．可以链式存储D．数据元素可以是多个字符5．设串S1=‘ABCDEFG’,s2=‘PQRST’,函数CONCAT返回X和Y串的连接串，SUBSTR返回串S从序号I开始的J个字符组成的字串，LENGTH返回串S的长度，则CONCAT），SUBSTR，2））的结果串是。
A．BCDEFB．BCDEFGC．BCPQRSTD．BCDEFEF
二、算法设计
1.分别在顺序存储和一般链接存储两种方式下,用C语言写出实现把串s1复制到串s2的串复制函数strcpy。
2.在一般链接存储方式下,写出采用简单算法实现串的模式匹配的C语言函数intL_index。
第五章数组与广义表
一、选择题1．常对数组进行的两种基本操作是A．建立与删除B．索引和修改C．查找和修改D．查找与索引
2.二维数组M的元素是4个字符组成的串,行下标i的范围从0到4,列下标j的范围从0到5,M按行存储时元素M的起始地址与M按列存储时元素的起始地址相同。
A．MB．MC．MD．M
3.数组A中,每个元素A的长度为3个字节,从首地址SA开始连续存放在存储器内,存放该数组至少需要的单元数是。
A．80B．100C．240D．270
4.数组A中,每个元素A的长度为3个字节,从首地址SA开始连续存放在存储器内,该数组按行存放时,元素A的起始地址为。
A．SA+141B．SA+144C．SA+222D．SA+225
5.数组A中,每个元素A的长度为3个字节,从首地址SA开始连续存放在存储器内,该数组按列存放时,元素A的起始地址为。
A．SA+141B．SA+180C．SA+222D．SA+225
6.稀疏矩阵一般的压缩存储方法有两种,即。
A．二维数组和三维数组B．三元组和散列C．三元组和十字链表D．散列和十字链表
7.若采用三元组压缩技术存储稀疏矩阵,只要把每个元素的行下标和列下标互换,就完成了对该矩阵的转置运算,这种观点。
A．正确B．错误
8.设矩阵A是一个对称矩阵,为了节省存储,将其下三角部分按行序存放在一维数组B中,对下三角部分中任一元素ai,j,在一组数组B的下标位置k的值是。
A．i/2+j-1B．i/2+jC．i/2+j-1D．i/2+j
1.己知二维数组A采用行序为主方式存储,每个元素占k个存储单元,并且第一个元素的存储地址是LOC,则A的地址是________。
2.二维数组A采用列序为主方式存储,每个元素占一个存储单元,并且A的存储地址是200,则A的地址是________。
3.有一个10阶对称矩阵A,采用压缩存储方式=1）,则A的地址是________。
4.设n行n列的下三角矩阵A已压缩到一维数组S中,若按行序为主存储,则A对应的S中的存储位置是________。
5.若A是按列序为主序进行存储的4×
6的二维数组,其每个元素占用3个存储单元,并且A的存储地址为1000,元素A的存储地址为________，该数组共占用________个存储单元。
三、算法设计
1.如果矩阵A中存在这样的一个元素A满足条
件:
A是第i行中值最小的元素,且又是第j列中值最大的元素,则称之为该矩阵的一个马鞍点。
编写一个函数计算出1×
n的矩阵A的所有马鞍点。
算法思想：
依题意,先求出每行的最小值元素,放入min之中,再求出每列的最大值元素,放入max之中,若某元素既在min中,又在max中,则该元素A便是马鞍点,找出所有这样的元素,即找到了所有马鞍点。
2.n只猴子要选大王,选举办法如下:
所有猴子按1,2,...,n编号围坐一圈,从1号开始按
1、2、...、m报数,凡报m号的退出到圈外,如此循环报数,直到圈内剩下只猴子时,这只猴子就是大王。
n和m由键盘输入,打印出最后剩下的猴子号。
编写一程序实现上述函数。
算法思想:
本题用一个含有n个元素的数组a,初始时a中存放猴子的编号i,计数器似的值为0。
从a开始循环报数,每报一次,计数器的值加1,凡报到m时便打印出a值,同时将a的值改为O,计数器值重新置为0。
该函数一直进行到n只猴子全部退出圈外为止,最后退出的猴子就是大王。
因此,现本题功能的程序如下:
3.数组和广义表的算法验证程序编写下列程序:
求广义表表头和表尾的函数head和tail。
计算广义表原子结点个数的函数count_GL。
计算广义表所有原子结点数据域。
include“
malloc.h“typedefstructnode{inttag;
union{structnode*sublist;
chardata;
}dd;
struct
node*link;
}NODE;
NODE*creat_GL{NODE*h;
charch;
ch=*;
++;
if{h=malloc）;
if{h-tag=1;
h-
dd.sublist=creat_GL;
}Else
{h-tag=0;
dd.data=ch;
}}else
h=NULL;
ifif
h-link=creat_GL;
else
h-link=NULL;
return;
}void
prn_GL{if{if
{printf;
if
printf;
prn_GL;
}else
printf“）;
if{printf;
}}}
NODE*copy_GL{NODE*q;
ifreturn;
q=malloc）;
q-tag=p-tag;
q-
dd.sublist=copy_GL;
dd.data=p-
dd.data;
q-link=copy_GL;
}
NODE*head/*求表头函数*/{return;
}NODE*tail/*求表
尾函数*/{return;
}intsum/*求原子结点的数据域之和
函数*/{intm,n;
else{ifn=p-
n=sum;
m=sum;
elsem=0;
}}intdepth/*求表的深度函数*/{inth,maxdh;
NODE*q;
elseifreturn1;
else{maxdh=0;
while{ifh=0;
else{q=p-
dd.sublist;
h=depth;
}ifmaxdh=h;
p=p-link;
}return;
}}main{NODE*hd,*hc;
chars,*p;
p=gets;
hd=creat_GL;
prn_GL）;
hc=copy_GL;
printf）;
}第六章树
1.在线索化二叉树中,t所指结点没有左子树的充要条件是。
A．t-〉left==NULLB．t-〉ltag==1C．t-〉ltag=1且t-〉left=NULLD．以上都不对
2.二叉树按某种顺序线索化后,任一结点均有指向其前趋和后继的线索,这种说法。
A．正确B．错误C．不同情况下答案不确定
3.二叉树的前序遍历序列中,任意一个结点均处在其子女结点的前面,这种说法。
4.由于二叉树中每个结点的度最大为2,所以二叉树是一种特殊的树,这种说法。
5.设高度为h的二叉树上只有度为0和度为2的结点,则此类二叉树中所包含的结点数至少为。
A．2hB．2h-1C．2h+1D．h+1
6.已知某二叉树的后序遍历序列是dabec。
中序遍历序列是debac,它的前序遍历序列是。
A．acbedB．decabC．deabcD．cedba
7.如果T2是由有序树T转换而来的二叉树,那么T中结点的前序就是T2中结点的A．前序B．中序C．后序D．层次序
8.某二叉树的前序遍历结点访问顺序是abdgcefh,中序遍历的结点访问顺序是dgbaechf,则其后序遍历的结点访问顺序是。
A．bdgcefhaB．gdbecfhaC．bdgaechfD．gdbehfca
9.二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。
这种说法。
10.按照二叉树的
定义,具有3个结点的二叉树有种。
A．3B．4C．5D．6
11.在一非空二叉树的中序遍历序列中,根结点的右边。
A．只有右子树上的所有结点B．只有右子树上的部分结点C．只
有左子树上的部分结点D．只有左子树上的所有结点
12.树最适合用来表示。
A．有序数据元素B．无序数据元素C．元素之间具有分支层次关系的数据D．元素之间无联系的数据
13.任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序。
A．不发生改变B．发生改变C．不能确定D．以上都不对
14.实现任意二叉树的后序遍历的非递归算法而不使用栈结构,最佳方案是二叉树采用存储结构。
A．二叉链表B．广义表存储结构C．三叉链表D．顺序存储结构
15.对一个满二叉树,m个树叶,n个结点,深度为h,则。
A．n=h+mB．h+m=2nC．m=h-1D．n=2h-1
16.如果某二叉树的前序为stuwv,中序为uwtvs,那么该二叉树的后序为。
A．uwvtsB．vwutsC．wuvtsD．wutsv
17.具有五层结点的二叉平衡树至少有个结点。
A．10B．12C．15D．17
1.二叉树中任何一个结点的度都是2。
2.由二叉树结点的先根
升级会员 