《数据结构习题及答案》由会员分享，可在线阅读，更多相关《数据结构习题及答案（18页珍藏版）》请在金锄头文库上搜索。
1、习题 一1 填空题（1） 数据的逻辑结构可形式地用一个二元组B(K，R)来表示，其中K是_，R是_。（2） 存储结构可根据数据元素在机器中的位置是否连续分为，。（3） 算法的基本要求有，。 （4） 度量算法效率可通过，两方面进行。 2 简述下列术语： 数据 数据元素 数据对象 数据结构 存储结构 数据类型。3. 常用的存储表示方法有哪几种?4.举例说明一下数据结构和算法的关系。5.设有数据逻辑结构为B=（K，R），K=k1，k2，k9r=, ,画出这个逻辑结构的图示，并确定相对于r哪些结点是开始结点，哪些结点是终端结点？6.试举一个数据结构的例子，并叙述其逻辑结构、存储结构、运算三方面的内容。
2、7.何谓算法？试详述算法设计的目的和算法必须满足的条件。8.编写一个算法，对三个两位数按由大到小的顺序进行排序。描述构造该算法的思维过程。习题二1.如定理2.1所描述的，从盒子中往外取球，在1-4所给的答案中，哪一个是i，j，k对应的值。Red，5，6Blue，5，6Blue，3，Red6，5，Red2如定理2.1所描述的，从盒子往外取球，在1-4所给的答案中，哪一个是i,j,k对应的值。6，7，RedBlue,7,38,2,Red9,Red,13.假设T1（N）= O（F（N），T2（N）= O（F（N），说明下列哪一个正确？T1 (N)+ T2 (N) = O(F(N)T1 (N)- T2
3、 (N) = O(F(N)T1 (N)/ T2 (N) = O(1)T1 (N) = O(T2 (N)4.假设两个算法的时间复杂度分别为T1（N）=O（N）和T2（N）=O（N2），说明下列哪一个正确（估算）？T1（N）* T2（N）= O（N3）T1（N）+ T2（N）= O（N2）T2（N）/ T1（N）= O（N）T2（N）- T1（N）= O（N）5.基于定理2.2的描述，为什么不能充分获得一个最大连续子序列之和的次平方运行时间？6.读者思考：由算法2.1到算法2.2的改进过程中，时间复杂度由三次降到二次，那么算法的空间复杂度有没有变化？这种改进是不是无条件的？7.将下列各式组合成与B
4、ig-Oh相等的函数。x2，x2 + x，x2 - x，x3/( x 1 )8确定以下各式的等价Big-Oh函数(估算)。x4/(x+1),x3-x2，x2+x39.程序A和程序B经分析，有不超过150NlogN和N2的最坏情况下的运行时间，如可能，分别回答下列各问题：当N值很大时（N 10,000）,哪个程序对运行时间有保证？N值较小（N 1000）时，哪一个程序对运行时间有更好的保证？在N = 1，000的平均情况下，哪个程序运行更好？在所有可能的输入中，程序B总比程序A运行的快吗？10程序A和程序B经分析，有不超过150NlogN和N2的最坏情况下的运行时间，读者计算一下输入的值N在哪个
5、范围里程序A的运行效率高于程序B，在哪个范围里程序B的运行效率高于程序A？（提示：可以通过建立方程式求解）11.对于这些你用手工来计算的典型算法，确定其运行时间。两个N位整数相加两个N位整数相乘两个N位整数相除12设一个N位整数x，对于表达式x2 + x-x3/( x 1 )，试确定其运行的时间复杂度（考虑“最坏情况分析法”）。13.对于N个项来说，以下计算XN的算法运行时间是多少？double power（double x，int n） double result = 1.0; for（int i = 0; i n; i+） result *= x; return result;14试确定下
6、面递归算法的时间复杂度：Int func（int n）if（n= =0）return（0）；return（n+func（n-1）；15.对于求最大子序列之和问题的平方算法而言，精确的确定语句最内部循环被执行多少次？16试计算在算法2.1中，精确的确定语句最内部循环被执行多少次？17.一个算法在输入规模为100时，花费0.5ms的时间，在下列情况下，输入规模为500时，它将花费多少时间（低次项不考虑）？线性算法O(NlogN)平方算法立方算法18一个算法在输入规模为10时，花费0.05ms的时间，在下列情况下，输入规模为1000时，它将花费多少时间（低次项不考虑）？线性算法O(NlogN)平方算
7、法立方算法19.一个算法在输入规模为100时，花费0.5ms的时间，在下列情况下，一分钟可以解决一个多大的问题（低次项不考虑）？线性算法平方算法立方算法20一个算法在输入规模为10时，花费0.05ms的时间，在下列情况下，0.5分钟可以解决一个多大的问题（低次项不考虑）？线性算法平方算法立方算法习题三1填空题(1) 线性表(a1,a2,an)有两种存贮结构：顺序存贮结构和链接存贮结构，请就这两种存贮结构完成下列填充： _存贮密度较大；_存贮利用率较高； _可以随机存取；_不可以随机存取；_插入和删除操作比较方便。 (2) 在单链表中，删除指针P所指结点的后继结点的语句是_。（1） 带头结点的单
8、循环链表Head的判空条件是_；不带头结点的单循环链表的判空条件是_。（2） 删除带头结点的单循环链表Head的第一个结点的操作是_；删除不带头结点的单循环链表的第一个结点的操作是_。（3） 如果线性表中最常用的操作是存取第I个元素及其前驱的值，则采用_存储方式节省时间。 A单链表 B双链表 C单循环链表 D顺序表2 动态与静态数据结构在计算机内存中的存储方式有何不同？各有何优缺点？3 描述以下三个概念的区别：头指针、头结点、第一个结点。4 试写出一个计算线性链表P中结点个数的算法，其中指针P指向该表中第一个结点，尾结点的指针域为空。5 何时选用顺序表、何时选用链表作为线性表的存储结构为宜?6
9、 在顺序表中插入和删除一个结点需平均移动多少个结点?具体的移动次数取决于哪两个因素?7 在单链表、双链表和单循环链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点*p从相应的链表中删去?若可以，其时间复杂度各为多少?8 假设LA、LB为两个递增有序的线性链表，试写出将这两个线性链表归并成一个线性链表LC的操作算法。9 将学生成绩按成绩高低排列建立了一个有序单链表，每个结点包括：学号、姓名和课程成绩。（1） 输入一个学号，如果与链表中的结点的学号相同，则将此结点删除；（2） 在链表中插入一个学生的记录，使得插入后链表仍然按成绩有序排列。10 某仓库中有一批零件，按其价格从低到高的顺序构成
10、一个单链表存于计算机内，链表的每一个结点说明同样价格的若干个零件。现在又新有m个价格为s的零件需要进入仓库，试写出仓库零件链表增加零件的算法。链表结点结构如下：11 设指针P指向单链表的首结点，指针X指向单链表中的任意一个结点，写出在X前插入一个结点i的算法。12 设多项式A和B采用线性链表的存储方式存放，试写出两个多项式相加的算法，要求把相加结果存放在A中。13 设指针a和b分别为两个带头结点的单链表的头指针，编写实现从单连表La中删除自第i个数据元素起，共length个数据元素、并把它们插入到单链表Lb中第j个元素之前的算法。14 设La和Lb是两个有序的循环链表，Pa和Pb分别指向两个表
11、的表头结点，是写一个算法将这两个表归并为一个有序的循环链表。15 已知有一个单向循环链表，其每个结点中含三个域：pre、data和next，其中data为数据域，next为指向后继结点的指针域，pre也为一个指针域，但是他的值为空（null），试编写一个算法将此单链表改为双向循环链表，即使pre成为指向前驱结点的指针域。16 画出执行下列各行语句后各指针及链表的示意图。L=（linklist）malloc （size of（lnode）；P=l；for（i=1；inext=(linklist)malloc(size of (lnode);p=p-next;p-data=i*2-1;p-next
12、=null;for (i=4;i=1;i- -；) insert_linklist（l;i+1;i*2）;for(i=1;i3;i+) del_linklist(l,i);17. 设顺序表L是一个递增有序表，试写一算法，将x插入L中，并使L仍是一个有序表。习题四1 填空题（1） 设栈S和队列Q的初始状态皆为空，元素a1，a2，a3，a4，a5和a6依次通过一个栈，一个元素出栈后即进入队列Q，若6个元素出队列的顺序是a3，a5，a4，a6，a2，a1则栈S至少应该容纳_个元素。（2） 一个栈的输入序列为1，2，3，4，5则下列序列中不可能是栈的输出序列的是_。A 2，3，4，1，5 B. 5，4
13、，1，3，2 C. 2，3，1，4，5 D. 1，5，4，3，22 对于下面的每一步画出栈中元素及栈顶指针的示意图：（1） 空栈；（2） 元素A入栈；（3） 元素B入栈；（4） 删除栈顶元素；（5） 元素C入栈；（6） 元素D入栈；3 比较栈和队列的相同点和不同点，举例说明。4 对于算术表达式3*（5-2）+7，用栈存储式子中的运算对象和运算符，试说明该算术表达式的运算过程。5 若依次输入数据元素序列a，b，c，d，e，f，g进栈，出栈操作可以和入栈操作间隔进行，则下列那些元素序列可以由出栈序列得到？ d，e，c，f，b，g，a； f，e，g，d，a，c，b； e，f，d，g，b，c，a； c
14、，d，b，e，f，a，g6 编写一个算法，用来判别表达式中开、闭括号是否配对出现。7 设将整数以万计1、2、3、4依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下有问题：（1） 若入栈次序为push(1)，pop()，push(2)，push(3)，pop()，pop()，push(4)，pop( )，则出栈的数字序列为什么？（2） 请分析1、2、3、4的24种排列中，哪些序列可以通过相应的入出栈得到。8 链栈中为何不设头指针？10. 循环队列的优点是什么？如何判断它的空和满？11. 试述队列的链式存储结构和顺序存储结构的优缺点。12. 假设以一维数组sn存储循环队列的元素，
