1、数据结构习题集附答案数据结构习题集附答案第一章绪论一、选择题1.组成数据的基本单位是A数据项B数据类型C数据元素D数据变量2.数据结构是研究数据的以及它们之间的相互关系。A理想结构，物理结构B理想结构，抽象结构C物理结构，逻辑结构D抽象结构，逻辑结构3.在数据结构中，从逻辑上可以把数据结构分成。A动态结构和静态结构B紧凑结构和非紧凑结构C线性结构和非线性结构D内部结构和外部结构4.数据结构是一门研究非数值计算的程序设计问题中计算机的以及它们之间的和运算等的学科。A数据元素B计算方法C逻辑存储D数据映像A结构B关系C运算D算法5.算法分析的两个主要方面是。A数据复杂性和程序复杂性B正确性和简明性
2、C可读性和简明性D空间复杂性和时间复杂性6.算法分析的目的是。A找出数据结构的合理性B研究算法中的输入和输出的关系C分析算法的效率以求改进D分析算法的易懂性和文档性7.计算机算法指的是,它必须具备输入、输出和等5个特性。A计算方法B排序方法C解决问题的有限运算序列D调度方法A可执行性，可移植性和可扩充性B可行性，确定性和有穷性C确定性、有穷性和稳定性D易读性、稳定性和安全性二、判断题1.数据的机内表示称为数据的存储结构。2.算法就是程序。3.数据元素是数据的最小单位。4.算法的五个特性为：有穷性、输入、输出、完成性和确定性。5.算法的时间复杂度取决于问题的规模和待处理数据的初态。三、填空题1.
3、数据逻辑结构包括_、_、_和_四种类型,其中树形结构和图形结构合称为_。2.在线性结构中,第一个结点_前驱结点,其余每个结点有且只有_个前驱结点；最后一个结点 _ 后续结点 , 其余每个结点有且只有 _个后续结点。3.在树形结构中,树根结点没有_结点,其余每个结点有且只有_个前驱结点；叶子结点没有_结点 ,其余每个结点的后续结点可以 _。4. 在图形结构中 , 每个结点的前驱结点数和后续结点数可以 _。5.线性结构中元素之间存在_关系,树形结构中元素之间存在_关系,图形结构中元素之间存在_关系。6.算法的五个重要特性是 _、_、_、_、_。7.数据结构的三要素是指_、_和_。8. 链式存储结构
4、与顺序存储结构相比较 , 主要优点是_。9. 设有一批数据元素 , 为了最快的存储某元素 , 数据结构宜用_结构,为了方便插入一个元素,数据结构宜用_结构。四、算法分析题1.求下列算法段的语句频度及时间复杂度for for x=x+1;分析：该算法为一个二重循环，执行次数为内、外循环次数相乘，但内循环次数不固定，与外循环有关，因些，时间频度T=1+2+3+n=n*/2有1/4T/n21，故它的时间复杂度为, 即与n2数量级相同。2.分析下列算法段的时间频度及时间复杂度for for for x=i+j-k;分析算法规律可知时间频度T=1+.+ 由于有1/6 T/ n3 1，故时间复杂度为第二章
5、线性表一、选择题1.一个线性表第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的地址是。A110 B108 C100 D1202.向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动个元素。A64 B63 C63.5 D73.线性表采用链式存储结构时，其地址。A必须是连续的B部分地址必须是连续的C一定是不连续的D连续与否均可以4.在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行。A s-next=p;p-next=s;B s-next=p-next;p-next=s;Cs-next=p-next;p=s;Dp-next=s;s-nex
6、t=p;5.在一个单链表中，若删除p所指结点的后续结点，则执行。Ap-next=p-next-next;Bp=p-next;p-next=p-next-next;Cp-next=p-next;Dp=p-next-next;6.下列有关线性表的叙述中，正确的是。A线性表中的元素之间隔是线性关系B线性表中至少有一个元素C线性表中任何一个元素有且仅有一个直接前趋D线性表中任何一个元素有且仅有一个直接后继7.线性表是具有n个的有限序列2.如果没有提供指针类型的语言，就无法构造链式结构。3.线性结构的特点是只有一个结点没有前驱，只有一个结点没有后继，其余的结点只有一个前驱和后继。4.语句p=p-next
7、完成了指针负值并使p指针得到了p指针所指后继结点的数据域值。5.要想删除p指针的后继结点，我们应该执行q=p-next ；p-next=q-next；free。三、填空题1.已知P为单链表中的非首尾结点，在P结点后插入S结点的语句为：_。2.顺序表中逻辑上相邻的元素物理位置相邻，单链表中逻辑上相邻的元素物理位置_相邻。3.线性表L采用顺序存储，假定在不同的n1个位置上插入的概率相同，则插入一个新元素平均需要移动的元素个数是_。4.在非空双向循环链表中，在结点q的前面插入结点p的过程如下：p-prior=q-prior;q-prior-next=p;p-next=q;_;5.已知L是无表头结点的
8、单链表，是从下列提供的答案中选择合适的语句序列，实现：表尾插入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 while p=p-next;Iwhile p=p-next;四、算法设计题1.试编写一个求已知单链表的数据域的平均值的函数。2.已知带有头结点的循环链表中头指针为head,试写出删除并释放数据域值为x的所有结点的c函数。3.某百货公司仓库中有一批电视机，按其价格从低到高的次序构成一个循环链表，每个结点有价格、数量和链指针三个域。现出库m台价格为h的
9、电视机，试编写算法修改原链表。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，分别表示
10、AB或A=B或AB。7.试编写算法,删除双向循环链表中第k个结点。8.线性表由前后两部分性质不同的元素组成,m和n为两部分元素的个数,若线性表分别采用数组和链表两种方式存储,编写算法将两部分元素换位成,分析两种存储方式下算法的时间和空间复杂度。9.用循环链表作线性表和的存储结构,头指针分别为ah和bh，设计C函数，把两个线性表合并成形如的线性表，要求不开辟新的动态空间,利用原来循环链表的结点完成合并操作,结构仍为循环链表, 头指针为head,并分析算法的时间复杂度。10.试写出将一个线性表分解为两个带有头结点的循环链表，并将两个循环链表的长度放在各自的头结点的数据域中的C函数。其中, 线性表中
11、序号为偶数的元素分解到第一个循环链表中,序号为奇数的元素分解到第二个循环链表中。11.试写出把线性链表改为循环链表的C函数。12.己知非空线性链表中x结点的直接前驱结点为y,试写出删除x结点的C函数。第三章栈和队列一、选择题1. 一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是。Aedcba Bdecba Cdceab Dabcde2.栈结构通常采用的两种存储结构是。A线性存储结构和链表存储结构B散列方式和索引方式C链表存储结构和数组D线性存储结构和非线性存储结构3.判定一个栈ST为空的条件是。AST-top。=0 BST-top=0 CST-top。=m0 DST- top=m
12、04.判定一个栈ST为栈满的条件是。AST-top。=0 BST-top=0 CST-top。=m0-1 DST-top=m0-15.一个队列的入列序列是1,2,3,4,则队列的输出序列是。A4,3,2,1 B1,2,3,4 C1,4,3,2 D3,2,4,16.循环队列用数组A存放其元素值，已知其头尾指针分别是front和rear则当前队列中的元素个数是。A%m Brear-front+1 Crear-front-1 Drear-front7. 栈和队列的共同点是A都是先进后出B都是先进先出C只允许在端点处插入和删除元素D没有共同点8.表达式a*-d的后缀表达式是。Aabcd*+- Babc
13、+*d- Cabc*+d- D-+*abcd 9.4个元素a1，a2，a3和a4依次通过一个栈，在a4进栈前，栈的状态，则不可能的出栈序是。Aa4，a3，a2，a1 Ba3，a2，a4，a1 Ca3，a1，a4，a2 Da3，a4，a2，a110.以数组Q存放循环队列中的元素，变量rear和qulen分别指示循环队列中队尾元素的实际位置和当前队列中元素的个数，队列第一个元素的实际位置是。Arearqulen Brearqulenm Cmqulen D1%m二、填空题1.栈的特点是_，队列的特点是_。2. 线性表、栈和队列都是 _ 结构 , 可以在线性表的 _位置插入和删除元素，对于栈只能在_插
14、入和删除元素，对于队列只能在_插入元素和_删除元素。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函数push A一个串的字符个数即该串的长度B一个串的长度至少是1 C空串是由一个空格字符组成的串D两个串S1和S2
15、若长度相同，则这两个串相等2.字符串“abaaabab“的nextval值为A B C D3.字符串满足下式, 其中head和tail的定义同广义表类似,如head=x,tail= yz, 则s=。concat）,head）= dc。Aabcd Bacbd Cacdb Dadcb4.串是一种特殊的线性表,其特殊性表现在A可以顺序存储B数据元素是一个字符C可以链式存储D数据元素可以是多个字符5设串S1=ABCDEFG,s2=PQRST,函数CONCAT返回X和Y串的连接串，SUBSTR返回串S从序号I开始的J个字符组成的字串，LENGTH返回串S的长度，则CONCAT），SUBSTR，2）的结果
16、串是。ABCDEF BBCDEFG CBCPQRST DBCDEFEF二、算法设计1. 分别在顺序存储和一般链接存储两种方式下,用C语言写出实现把串s1复制到串s2的串复制函数strcpy。2.在一般链接存储方式下,写出采用简单算法实现串的模式匹配的C语言函数int L_index。第五章数组与广义表一、选择题1常对数组进行的两种基本操作是A建立与删除B索引和修改C查找和修改D查找与索引2.二维数组M的元素是4个字符组成的串,行下标i的范围从0到4,列下标j的范围从0到5,M按行存储时元素M的起始地址与M按列存储时元素的起始地址相同。AM BM CM DM3.数组A中,每个元素A的长度为3个字
17、节,从首地址SA开始连续存放在存储器内,存放该数组至少需要的单元数是。A80 B100 C240 D2704.数组A中,每个元素A的长度为3个字节,从首地址SA开始连续存放在存储器内,该数组按行存放时, 元素A的起始地址为。ASA+141 BSA+144 CSA+222 DSA+2255.数组A中,每个元素A的长度为3个字节,从首地址SA开始连续存放在存储器内,该数组按列存放时,元素A的起始地址为。ASA+141 BSA+180 CSA+222 DSA+2256.稀疏矩阵一般的压缩存储方法有两种,即。A二维数组和三维数组B三元组和散列C三元组和十字链表D散列和十字链表7.若采用三元组压缩技术存
18、储稀疏矩阵,只要把每个元素的行下标和列下标互换,就完成了对该矩阵的转置运算, 这种观点。A正确B错误8.设矩阵A是一个对称矩阵,为了节省存储, 将其下三角部分按行序存放在一维数组B中,对下三角部分中任一元素ai,j,在一组数组B的下标位置k的值是。Ai/2+j-1 Bi/2+j Ci/2+j-1 Di/2+j二、填空题1.己知二维数组A采用行序为主方式存储,每个元素占k个存储单元,并且第一个元素的存储地址是LOC,则A的地址是_。2.二维数组A采用列序为主方式存储,每个元素占一个存储单元, 并且A的存储地址是200,则A的地址是_。3.有一个10阶对称矩阵A,采用压缩存储方式=1）,则A的地址
19、是 _。4.设n行n列的下三角矩阵A已压缩到一维数组S中,若按行序为主存储,则A对应的S中的存储位置是_。5.若A是按列序为主序进行存储的46的二维数组,其每个元素占用3个存储单元,并且A的存储地址为1000,元素A的存储地址为_，该数组共占用_个存储单元。三、算法设计1.如果矩阵A中存在这样的一个元素A满足条件:A是第i行中值最小的元素,且又是第j列中值最大的元素,则称之为该矩阵的一个马鞍点。编写一个函数计算出1n的矩阵A的所有马鞍点。算法思想：依题意,先求出每行的最小值元素,放入min之中,再求出每列的最大值元素,放入max之中,若某元素既在min中,又在max中,则该元素A便是马鞍点,找
20、出所有这样的元素,即找到了所有马鞍点。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.数组和广义表的算法
21、验证程序编写下列程序: 求广义表表头和表尾的函数head和tail。计算广义表原子结点个数的函数count_GL。计算广义表所有原子结点数据域。include “malloc.h“ typedef struct node int tag;union struct node *sublist;char data;dd;structnode *link;NODE;NODE *creat_GL NODE *h;char ch;ch=*;+;if h=malloc）;if h-tag=1;h-dd.sublist=creat_GL; Elseh-tag=0;h-dd.data=ch; elseh=NU
22、LL;ch=*;+;if ifh-link =creat_GL;elseh-link=NULL;return; voidprn_GL if ifprintf;ifprintf;elseprn_GL; elseprintf;ifprintf“）;if printf;prn_GL; NODE *copy_GL NODE *q;if return;q=malloc）;q-tag=p-tag;ifq-dd.sublist =copy_GL;elseq-dd.data =p-dd.data;q-link=copy_GL;return;NODE *head /*求表头函数 */ return; NODE
23、*tail /*求表尾函数 */ return; int sum /*求原子结点的数据域之和函数 */ int m,n;if return;else if n=p-dd.data;elsen=sum;ifm=sum;else m=0;return; int depth /*求表的深度函数 */ int h,maxdh;NODE *q;if return;else if return 1;else maxdh=0;while if h=0;else q=p-dd.sublist;h=depth; ifmaxdh=h;p=p-link; return; main NODE *hd,*hc;char
24、 s,*p;p=gets;hd=creat_GL;prn_GL）;prn_GL）;hc=copy_GL;printf;prn_GL;printf）;printf）; 第六章树一、选择题1.在线索化二叉树中,t所指结点没有左子树的充要条件是。At-left=NULL Bt-ltag=1 Ct-ltag=1且t-left=NULL D以上都不对2.二叉树按某种顺序线索化后,任一结点均有指向其前趋和后继的线索,这种说法。A正确B错误C不同情况下答案不确定3.二叉树的前序遍历序列中,任意一个结点均处在其子女结点的前面,这种说法。A正确B错误C不同情况下答案不确定4.由于二叉树中每个结点的度最大为2,所
25、以二叉树是一种特殊的树,这种说法。A正确B错误C不同情况下答案不确定5.设高度为h的二叉树上只有度为0和度为2的结点,则此类二叉树中所包含的结点数至少为。A2h B2h-1 C2h+1 Dh+16.已知某二叉树的后序遍历序列是dabec。中序遍历序列是debac,它的前序遍历序列是。Aacbed Bdecab Cdeabc Dcedba7.如果T2是由有序树T转换而来的二叉树,那么T中结点的前序就是T2中结点的A前序B中序C后序D层次序8.某二叉树的前序遍历结点访问顺序是abdgcefh,中序遍历的结点访问顺序是dgbaechf,则其后序遍历的结点访问顺序是。Abdgcefha Bgdbecf
26、ha Cbdgaechf Dgdbehfca9.二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。这种说法。A正确B错误C不同情况下答案不确定10.按照二叉树的定义,具有3个结点的二叉树有种。A3 B4 C5 D611.在一非空二叉树的中序遍历序列中,根结点的右边。A只有右子树上的所有结点B只有右子树上的部分结点C只有左子树上的部分结点D只有左子树上的所有结点12.树最适合用来表示。A有序数据元素B无序数据元素C元素之间具有分支层次关系的数据D元素之间无联系的数据13.任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序。A不发生改变B发生改变C不能确定D以上都不对14. 实现任意二叉树的后序遍历的非递归算法而不使用栈结构,最佳方案是二叉树采用存储结构。A二叉链表B广义表存储结构C三叉链表D顺序存储结构15.对一个满二叉树,m个树叶,n个结点,深度为h,则。An=h+m Bh+m=2n Cm=h-1 Dn=2h-116.如果某二叉树的前序为stuwv,中序为uwtvs,那么该二叉树的后序为。Auwvts Bvwuts Cwuvts Dwutsv17.具有五层结点的二叉平衡树至少有个结点。A10 B12 C15 D17二、判断题1.二叉树中任何一个结点的度都是2。2.由二叉树结点的先根
