[经济学]数据结构习题正文.doc

《[经济学]数据结构习题正文.doc》由会员分享，可在线阅读，更多相关《[经济学]数据结构习题正文.doc（41页珍藏版）》请在三一办公上搜索。

1、数据结构习题集-淮阴工学院计算机工程学院第一章 数据结构概论1-1 什么是数据? 它与信息是什么关系?1-2 什么是数据、数据对象、数据元素、数据结构、存储结构和算法? 有关数据结构的讨论涉及哪三个方面? 1-3 数据的逻辑结构分为线性结构和非线性结构两大类。线性结构包括数组、链表、 栈、队列、优先级队列等; 非线性结构包括树、图等、这两类结构各自的特点是什么？1-4 什么是算法? 算法的5个特性是什么? 试根据这些特性解释算法与程序的区别。1-5 (1) 在下面所给函数的适当地方插入计算count的语句：void d (ArrayElement x , int n ) int i = 1;

2、do xi += 2; i += 2; while (i = n ); i = 1; while ( i = (n / 2) ) xi += xi+1; i+; (2) 将由(1)所得到的程序化简。使得化简后的程序与化简前的程序具有相同的count值。(3) 程序执行结束时的count值是多少？(4) 使用执行次数的方法计算这个程序的程序步数，画出程序步数统计表。 1-6 判断下列叙述的对错。如果正确，在题前打“”，否则打“”。 (1) 数据元素是数据的最小单位。(2) 数据结构是数据对象与对象中数据元素之间关系的集合。(3) 数据结构是具有结构的数据对象。(4) 数据的逻辑结构是指各数据元素

3、之间的逻辑关系，是用户按使用需要建立的。(5) 算法和程序原则上没有区别，在讨论数据结构时二者是通用的。1-7 判断下列叙述的对错。如果正确，在题前打“”，否则打“”。 (1) 所谓数据的逻辑结构是指数据元素之间的逻辑关系。(2) 同一数据逻辑结构中的所有数据元素都具有相同的特性是指数据元素所包含的数据项的个数都相等。(3) 数据的逻辑结构与数据元素本身的内容和形式无关。(4) 数据结构是指相互之间存在一种或多种关系的数据元素的全体。(5) 从逻辑关系上讲，数据结构主要分为两大类：线性结构和非线性结构。1-8 设n为正整数, 分析下列各程序段中加下划线的语句的程序步数。 (1)for (int

4、 i = 1; i = n; i+) (2) x = 0; y = 0; for (int j = 1; j = n; j+) for (int i = 1; i = n; i+) cij = 0.0; for (int j = 1; j = i; j+) for (int k = 1; k = n; k+)for (int k = 1; k = j; k+) cij = cij + aik * bkj; x = x + y; (3) int i = 1, j = 1; (4) int i =1;while (i=n & j=n) do i = i + 1; j = j + i; for (i

5、nt j = 1; j = n; j+) i = i + j; while ( i 100 + n );1-9 填空题 算法是一个有穷的指令集，它为解决某一特定任务规定了一个运算序列。它应当具有输入、输出、( )、有穷性和可执行性等特性。 算法效率的度量分为( )和( )。( )主要通过在算法的某些部位插装时间函数来测定算法完成某一规定功能所需的时间。而( )不实际运行算法，它是分析算法中语句的执行次数来度量算法的时间复杂性。 程序所需的存储空间包含两个部分( )和( )。( )空间的大小与输入输出数据的个数多少，数值大小无关；( )空间主要包括其大小与问题规模有关的成分变量所占空间，引用变量

6、所占空间，以及递归栈所用的空间，还有在算法运行过程中动态分配和回收的空间。1-10. 试用大O表示法给出下面程序的时间复杂性。void out ( float x , int m, int n ) float sum ; for ( int i = 0; i m; i+ ) sumi = 0.0; for ( int j = 0; j n; j+ ) sumi = xij; for ( int i = 0; i m; i+ ) printf( Line: %f :, sumi); 1-11 分析以下程序段的时间复杂度 (1). for (i=1;in;i+) y=y+1; for(j=0;j=

7、(2*n);j+) x+; (2).i=1;while(i=n)i=i*2;(3).a=0;b=1;for(i=2;i=n;i+)s=a+b;b=a;a=s;(4).Int a=2,5,1,7,9,3,6,8;order(int j,int m)int itemp;if(jm)for(i=j;j=m;i+)if(aiaj)temp=ai;ai=aj;aj=temp;j+;order(j,m);main()int j;order(0,7);for(i=0;i=7;i+)printf(“%d”,aI);(5).i=1;while(i=n)i=i*3;1-12 试举例说明数据结构与算法的关系。1-1

8、3 试编写一算法，自大到小依次输出顺序输入的三个数x,y,z,的值。1-14 已知有实现同一功能的两种算法，其时间复杂度分别为O(2n)和O(n10), 假设现实计算机可连续运算的时间为107秒，又每秒可执行基本操作105 次。试问在此条件，这两种算法可解决问题的规模各为多少？哪个算 法更适宜？请说明理由。1-15 求两个n阶矩阵的乘法C=AXB，其算法如下：# define MAX 100void maxtrixmult(int n,float aMAXMAX,bMAXMAX,float cMAXMAX)int I,j,k;float x;for(I=1;I=n;I+)for(j=1;j=n

9、;j+)x=0;for(k=1;k=n;k+)x+=aIk*bkj;cIj=x;分析该算法的时间复杂度。1-16 数据结构在计算机中的表示称作数据的 。 A 逻辑结构 B 存储结构 C 线性结构 D 顺序存储结构1-17 算法是求解问题的一个运算序列.下列表述的各项中,_不属于一各算法应有的特性.A.有穷性 B.确定性 C.可行性 D.复杂性1-18. 算法的主运算如下，其中i的初值为1，s的初值为0，“”为赋值号。 while in do for j 1 to n do s s+ai,j; i i*2; 则该算法的时间复杂度为。A. O（2n） B.O（n+log2n ） 1-19 设三个函

10、数f,g,h分别为 f(n)=100n3+n2+1000 , g(n)=25n3+5000n2 , h(n)=n1.5+5000nlgn 请判断下列关系是否成立：(1) f(n)=O(g(n) (2) g(n)=O(f(n) (3) h(n)=O(n1.5)(4) h(n)=O(nlgn)1-20 设有两个算法在同一机器上运行，其执行时间分别为100n2和2n,要使前者快于后者，n至少要多大?1-21 设n为正整数，利用大O记号，将下列程序段的执行时间表示为n的函数。(1) i=1; k=0 while(in) k=k+10*i;i+; T(n)=n-1 T(n)=O(n) 这个函数是按线性阶

11、递增的(2) i=0; k=0;dok=k+10*i; i+; while(in); T(n)=n T(n)=O(n) 这也是线性阶递增的(3) i=1; j=0; while(i+j=n) if (i1 while (x=(y+1)*(y+1)y+; T(n)=n1/2 T(n)=O(n1/2) 最坏的情况是y=0，那么循环的次数是n1/2次，这是一个按平方根阶递增的函数。(5) x=91; y=100; while(y0)if(x100)x=x-10;y-;else x+; T(n)=O(1) 这个程序看起来有点吓人，总共循环运行了1000次，但是我们看到n没有? 没。这段程序的运行是和n

12、无关的，就算它再循环一万年，我们也不管他，只是一个常数阶的函数。1-22 算法的时间复杂度仅与问题的规模相关吗?1-23 按增长率由小至大的顺序排列下列各函数：2100, (2/3)n，(3/2)n， nn , , n! ，2n ，lgn ,nlgn, n(3/2) 分析如下：2100 是常数阶； (2/3)n和 (3/2)n是指数阶,其中前者是随n的增大而减小的； nn是指数方阶； n 是方根阶, n! 就是n(n-1)(n-2). 就相当于n次方阶；2n 是指数阶，lgn是对数阶 ,nlgn是对数方阶, n(3/2)是3/2次方阶。根据以上分析按增长率由小至大的顺序可排列如下： (2/3)

13、n 2100 lgn n n(3/2) nlgn (3/2)n 2n n! nn 1-24 有时为了比较两个同数量级算法的优劣，须突出主项的常数因子，而将低次项用大O记号表示。例如，设T1(n)=1.39nlgn+100n+256=1.39nlgn+O(n), T2(n)=2.0nlgn-2n=2.0lgn+O(n), 这两个式子表示，当n足够大时T1(n)优于T2(n)，因为前者的常数因子小于后者。请用此方法表示下列函数，并指出当n足够大时，哪一个较优，哪一个较劣?函 数 大O表示 优劣 (1) T1(n)=5n2-3n+60lgn 5n2+O(n) 较差(2) T2(n)=3n2+1000

14、n+3lgn 3n2+O(n) 其次 (3) T3(n)=8n2+3lgn 8n2+O(lgn) 最差(4) T4(n)=1.5n2+6000nlgn 1.5n2+O(nlgn) 最优 第二章 线性表2-1 设有一个线性表（e0, e1, , en-2, en-1）存放在一个一维数组AarraySize中的前n个数组元素位置。请编写一个函数将这个线性表原地逆置，即将数组的前n个原址内容置换为（en-1, en-2, , e1, e0）。2-2 设有一个二维数组Amn，假设A00存放位置在644（10），A22存放位置在676（10），每个元素占一个空间，问A33（10）存放在什么位置？脚注（1

15、0）表示用10进制表示。2-3 设有一个nn的对称矩阵A，如图（a）所示。为了节约存储，可以只存对角线及对角线以上的元素，或者只存对角线或对角线以下的元素。前者称为上三角矩阵，后者称为下三角矩阵。我们把它们按行存放于一个一维数组B中，如图（b）和图（c）所示。并称之为对称矩阵A的压缩存储方式。试问：(1) 存放对称矩阵A上三角部分或下三角部分的一维数组B有多少元素？(2) 若在一维数组B中从0号位置开始存放，则如图(a)所示的对称矩阵中的任一元素aij在只存上三角部分的情形下（图(b)）应存于一维数组的什么下标位置？给出计算公式。(3) 若在一维数组B中从0号位置开始存放，则如图(a)所示的对

16、称矩阵中的任一元素aij在只存下三角部分的情形下（图(c)）应存于一维数组的什么下标位置？给出计算公式。2-4 编写一个算法frequency，统计在一个输入字符串中各个不同字符出现的频度。用适当的测试数据来验证这个算法。2-5 利用顺序表的操作，实现以下的函数。(1) 从顺序表中删除具有最小值的元素并由函数返回被删元素的值。空出的位置由最后一个元素填补，若顺序表为空则显示出错信息并退出运行。 (3) 向顺序表中第i个位置插入一个新的元素x。如果i不合理则显示出错信息并退出运行。(8) 从顺序表中删除所有其值重复的元素，使表中所有元素的值均不相同。2-6 字符串的替换操作replace ( S

17、tring& s, String& t, String& v) 是指：若t是s的子串，则用串v替换串t在串s中的所有出现；若t不是s的子串，则串s不变。例如，若串s为“aabbabcbaabaaacbab”，串t为“bab”，串v为“abdc”，则执行replace操作后，串s中的结果为“aababdccbaabaaacabdc”。试利用字符串的基本运算实现这个替换操作。2-7 顺序表的插入和删除要求仍然保持各个元素原来的次序。设在等概率情形下, 对有127个元素的顺序表进行插入, 平均需要移动多少个元素? 删除一个元素, 又平均需要移动多少个元素?2-8 设A和B均为下三角矩阵，每一个都有n

18、行。因此在下三角区域中各有n（n+1）/2个元素。另设有一个二维数组C，它有n行n+1列。试设计一个方案，将两个矩阵A和B中的下三角区域元素存放于同一个C中。要求将A的下三角区域中的元素存放于C的下三角区域中，B的下三角区域中的元素转置后存放于C的上三角区域中。并给出计算A的矩阵元素aij和B的矩阵元素bij在C中的存放位置下标的公式。2-9 稀疏矩阵的三元组表可以用带行指针数组的二元组表代替。稀疏矩阵有多少行，在行指针数组中就有多少个元素：第i个元素的数组下标i代表矩阵的第i行，元素的内容即为稀疏矩阵第i行的第一个非零元素在二元组表中的存放位置。二元组表中每个二元组只记录非零元素的列号和元素

19、值，且各二元组按行号递增的顺序排列。试对右图所示的稀疏矩阵，分别建立它的三元组表和带行指针数组的二元组表。2-10. 判断下列叙述的对错。如果正确，在题前打“”，否则打“”。 (1) 线性表的逻辑顺序与物理顺序总是一致的。(2) 线性表的顺序存储表示优于链式存储表示。(3) 线性表若采用链式存储表示时所有存储单元的地址可连续可不连续。(4) 二维数组是其数组元素为线性表的线性表。(5) 每种数据结构都应具备三种基本运算：插入、删除和搜索。2-11. 线性结构可用顺序表或链表存储。试问：(1) 如果有n个表同时并存，并且在处理过程中各表的长度会动态发生变化，表的总数也可能自动改变、在此情况下，应

20、选用哪种存储表示？为什么？(2) 若表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，这时，应采用哪种存储表示？为什么？2-12. 已知整数数组A 中有n个元素，试设计一个算法，求数组中所有元素值的和。2-13. 已知整数数组A 中有n个元素，试设计一个算法，求数组中所有元素值的平均值。2-14. 假定数组AarraySize中有多个零元素, 试写出一个函数, 将A 中所有的非零元素依次移到数组A的前端Ai (0 i link = p-link; p-link = s;(2) q-link = s; s-link = p;(3) p-link = s-link; s-l

21、ink = p;(4) p-link = s; s-link = q;2-42. 设单链表中结点的结构为（data, link）。已知指针p所指结点不是尾结点，若在*p之后插入结点*s，则应执行下列哪一个操作？(1) s-link = p; p-link = s;(2) s-link = p-link; p-link = s;(3) s-link = p-link; p = s;(4) p-link = s; s-link = p; 2-43. 设单链表中结点的结构为（data, link）。若想摘除结点*p的直接后继，则应执行下列哪一个操作？(1) p-link = p-link-link;

22、 (2) p = p-link; p-link = p-link-link;(3) p-link = p-link; (4) p = p-link-link;2-44. 已知head为单链表的表头指针, 链表中存储的都是整型数据，试写出实现下列运算的递归算法：(1) 求链表中的最大整数。(2) 求链表的结点个数。2-45. 定位函数Locate：在单链表中寻找第i个结点。若找到，则函数返回第i个结点的地址；若找不到，则函数返回NULL。2-46. 统计函数number：统计单链表中具有给定值x的所有元素。2-47. 整理函数cleardupnode：在非递减有序的单链表中删除值相同的多余结点。

23、2-48. 设单循环链表中结点的结构为（data, link），且rear是指向非空的带表头结点的单循环链表的尾结点的指针。若想删除链表第一个结点，则应执行下列哪一个操作？(1) s = rear; rear = rear-link; free(s);(2) rear = rear-link; free(rear);(3) rear = rear-link-link; free(rear); (4) s = rear-link-link; rear-link-link = s-link; free(s);2-49. 有一个循环链表，它既没有头指针又没有头结点。只有一个指针p指向表中的某一结点。

24、试编写一个函数，删除指针p所指结点的直接前驱结点。2-50. 判断一个带表头结点的双向循环链表L是否对称相等的算法如下所示，请在算法中的 处填入正确的语句。int symmetry ( DlinkList L ) int sym = 1; DlistNode * p = L-next, q = L-prior; while ( ( p != q | p-prior = q ) & ) if ( p-data = q-data ) ; ; else sym = 0; return sym; 2-51. 设双向循环链表中结点的结构为（data, prior, next），且不带表头结点。若想在指针

25、p所指结点之后插入指针s所指结点，则应执行下列哪一个操作？(1) p-next = s; s-prior = p; p-next-prior = s; s-next = p-next;(2) p-next = s; p-next-prior = s; s-prior = p; s-next = p-next;(3) s-prior = p; s-next = p-next; p-next = s; p-next-prior = s; (4) s-prior = p; s-next = p-next; p-next-prior = s; p-next = s;2-52. 设有一个栈，元素进栈的次

26、序为：A，B，C，D，E。试问能否得到出栈序列： (1) C,E,A,B,D (2) C,B,A,D,E (3) D,C,A,B,E (4) A,C,B,E,D (5) A,B,C,D,E (6) E,A,B,C,D 若能，请写出操作序列。2-53* 假设在算法描述语言中引入指针的二元运算“异或”（用“”表示），若a和b为指针，则ab的运算结果仍为原指针类型，且：a(ab)=(aa) b, (ab) b=a(bb),则可利用一个指针来实现双向链表。每个结点有两个域：data和link 域，link域存放该结点前驱与后续结点指针（不存在时为NULL）的异货。若设指针h 指向链表中第一个结点，e指

27、向链表中最后一个结点，则可实现从前向后或从后向前遍历次双向链表（这种链表称为对称表）。（1）编写一个函数从前向后输出该链表中个元素的值。 （2）编写一个函数在第I个结点之前插入一个其data域为 x 的结点的函数。（3）编写一个函数删除第I个结点的函数。2-54 线性表可用顺序表或链表存储。试问：(1) 两种存储表示各有哪些主要优缺点?(2) 如果有n个表同时并存，并且在处理过程中各表的长度会动态发生变化，表的总数也可能自动改变、在此情况下，应选用哪种存储表示？为什么？(3) 若表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，这时，应采用哪种存储表示？为什么？第三章

28、栈和队列3-1 试写一个判别表达式中开，闭括号是否配对出现的算法。3-2 按照四则运算加，减，乘，除和幂运算优先关系，仿照教科书，画出对下列算术表达式求值时操作数栈和运算符栈的变化过程：A+B C*E-D/F*G3-3 假设有2个栈共享向量空间v（1：m)，它们的栈底分别设在向量的两端，且进栈的每个元素只占一个分量。试写出这两个栈共用的栈操作方法pushi（I,X)，popi(I)和topi(I)， 其中I为1或0，用以指示出栈号。并讨论过程或函数设计这些操作算法各有什么优缺点。3-4 假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾结点（注意不设头指针），试编写相应的置空队列，如队

29、列和出队列的算法。3-5 假设以数组sequ(0:m-1)存放循环队列的元素，同时设变量rear和quelen分别指示循环队列中队尾元素的位置和内含元素的个数。试给出循环队列的队满条件，并写出相应的入队列和出队列的算法（在出队列的算法中要返回队头元素）。3-6 给定元素的向量，建立一个有序单链表表示的链栈的时间复杂度是多少？3-7 有一个单链表表示的链式队列（不同结点的数据域值可能相同），其队首指针为head，编写一个函数计算数据域为x 的结点个数。3-8 已知有两个栈A和B，其栈顶指针分别为topa和topb，编写一个函数从栈A中删除自I个元素起的共 len个元素，然后将它们插入到栈B的第j

30、个元素之前。3-9 输入一个名单，有n个名字，每个名字不超过10个字符，按字典顺序将名单的序列号排出单链表表示的队列序列（即每个名字对应的链表值是其后继名字的序号，最后一个链表值为0）。3-10 铁路进行列车调度时, 常把站台设计成栈式结构的站台，如右图所示。试问：(1) 设有编号为1, 2, 3, 4, 5, 6的六辆列车, 顺序开入栈式结构的站台, 则可能的出栈序列有多少种?(2) 若进站的六辆列车顺序如上所述, 那么是否能够得到435612, 325641, 154623和135426的出站序列, 如果不能, 说明为什么不能; 如果能, 说明如何得到(即写出进栈或出栈的序列)。3-11 假设以数组Qm存放循环队列中的元素, 同时设置一个标志tag，以tag = 0和tag = 1来区别在队头指针(front)和队尾指针(rear)相等时，队列状态为“空”还是“满”。试编写