数据结构辅导习题.doc

第一章 绪论1数据结构是按照某种逻辑关系组织起来的一批数据，按一定的存储表示方式把它们存储在计算机的存储器中，并在这些数据上定义了一个_D_的集合。 A逻辑结构 B物理结构 C算法 * D运算2数据结构在形式上可定义为一个二元组：D=（K，R），其中K是_D_的有限集合，R是K上关系的有限集合。 A数据操作 B逻辑结构 C算法 * D数据元素3在数据结构中，从逻辑上可以把数据结构分为_A_。 * A线性结构和非线性结构 B内部结构和外部结构 C动态结构和静态结构 D紧凑结构和非紧凑结构4算法的时间复杂度与_A_有关。 *求解问题的规模和所处理数据集的初始状态 B算法本身的难度和执行算法所耗费的存储空间C求解问题的规模和执行算法所耗费的存储空间D算法本身的难度和所处理数据集的初始状态5分析下面程序段的时间复杂度。 for (i=1; i=n; i+) for (j=1; j=i; j+) x+;解答：第一个语句执行n+1次，第二个语句执行n(n+3)/2次，第三个语句执行n(n+1)/2次，总共执行次数为n+3n+1，其时间复杂度为O（n）。6分析下面程序段的时间复杂度。 for (i=1; i=n; i+) for (j=1; j=i; j+) for (k=1; k=j; k+) x+;解答：第一个语句执行n+1次，第二个语句执行n(n+3)/2次，第三个语句执行 次，第四个语句执行次，共执行次数为这四个语句执行次数之和，其时间复杂度为O（n3）。该程序段中执行频度最大的语句是x+。为了简单起见，只考虑第四个语句执行次数，因此可以从内层循环向外层循环分析语句x+的执行次数，也可以用下式表示： 7分析下面程序段的时间复杂度。 for (i=1; i=2) j=j/2; 解答：对于for循环而言，循环次数为n次，while循环的执行次数与i有关，对于每个i，while循环执行log2i次，因此，算法的时间复杂度为 O(nlog2n)8 有如下递归函数fact(n)，分析其时间复杂度。void fact(int n) if (nllink-rlink=p-rlink; p-rlink-llink=p-llink; B. p-rlink-llink=p-llink; p-llink-rlink=p-rlink; C. p-llink-rlink=p; p-llink-rlink-llink=p-rlink; * D. p-llink-rlink=p-rlink; 7. 设一元多项式A和B的项数分别为m和n，均采用单链表表示，进行A加B运算的时间复杂度为_C_。 A. O(m) (当mn) B. O(n) (当mn) * C. O(m+n) D. O(m*n)8说明以下三个概念的区别：头指针，头结点，首元素结点（第一个元素结点）。解答：头指针是指向链表中第一个结点（首元素结点）的指针，在首元素结点之前附设的一个结点称为头结点；首元素结点为链表中存储线性表中第一个数据元素的结点。若链表中附设头结点，则不管线性表是否为空表，头指针均不为空，否则表示空表的链表的头指针为空。9线性表有两种存储结构：一是顺序存储结构，二是链式存储结构。试问：（1） 两种存储表示各有哪些主要优缺点？（2） 如果有n个线性表同时并存，并且在处理过程中各表的长度会动态发生变化，线性表的总长度也会自动地改变。在此情况下，应选用哪种存储结构？为什么？（3）若线性表的总长度基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素，那么，应采用哪种存储结构？为什么？解答：（1）顺序存储是按索引（隐含的）直接存取数据元素，方便灵活，效率高，但插入和删除操作时将引起元素移动，因而效率低；链接存储采用动态分配存储空间，存储空间利用率高，但需增设指示结点之间关系的指针域，存取数据元素不如顺序存储方便，但结点的插入、删除操作十分简单。（2）应选用链接表存储结构。其理由是，链式存储结构用一组任意的存诸单元依次存储线性表中各元素，其存储单元可以是连续的，也可以是不连续的。这种存储结构，在对元素作插入或删除运算时，不需要移动元素，仅修改指针即可。所以很容易实现表的容量的扩充。（3）应选用顺序存储结构。其理由是，每个数据元素的存储位置和线性表的起始位置相差一个和数据元素在线性表中的序号成正比的常数。由此，只要确定了起始位置，线性表中任意一个数据元素都可随机存取，所以线性表的顺序存储结构是一种可以进行随机存取的存储结构。而链表则是一种顺序存取的存储结构。 10. 现有一个具有五个元素的线性表L=a,b,c,d,e，若它以链接方式存储，每个结点由数据(占2个字节)和指针(占2个字节)组成，其存储空间为100-119，如下所示：dP1bP2aP3eP4cP5 100 120试问：（1）指针、的值分别为多少？（2）该线性表的首结点的起始地址为多少？（3）该线性表的末结点的起始地址为多少？ 解答：解答此题时首先应明确用链接方式存储线性表中相邻的两个元素，其存储地址不一定相邻。依题意，计算出每个元素的首地址，即，d的首地址为100，b的首地址为104，a的首地址为108，e的首地址为112，c的首地址为116。元素b的指针为p2，b的后继为c，所以p2的值应为c的首地址116。即（1）指针、的值分别为:116、NIL（或为0）、100。（2）线性表的首结点的数据元素为a，起始地址应为108。（3）末结点的数据元素为e，其起始地址应为112。 11 线性表的存储方式有顺序和链接两种。试指出下面各表中使用的是哪种存储方式。各表中左边的S指向起始表元。 表21表元编号 货号 数量 12345661820510350178191040215201724 S 表 22表元编号 货号 数量 表元间联系12345661820510350178191040215201724 5 1 4 0 6 3 S 表 23表元编号 货号 数量 表元间联系12345661820510350178191040215201724 5 1 4 2 6 3 S 表 24 表元编号 货号 数量表元间联系1表元间联系212345661820510350178191040215201724 5 1 4 0 6 3 2 0 6 3 1 5S 解答：表21是顺序存储方式；表22是单向链接存储方式；表23是循环链接存储方式；表24是双向链接存储方式。12多项式A（x）=anxn+an-1xn-1+a1x+a0的线性表表示法有下列两种可能的形式：A1=（n，an，an-1，a1，a0） A2=（m，em-1，bm-1，em-2，bm-2， e0，b0）A1中的n表示指数，ai表示系数（非零项或零项）；A2中的 m为非零项的个数，ei，bi分别为非零项的指数和系数。试分析：（1）两种表示法对存储空间的需求情况；（2）若进行多项式相加，采用哪一种表示法处理较为简单？解答：（1）第一种表示法需要n+2个存储单元，其中n为多项式的最高幂数；第二种表示法需要2m+1个存储单元，其中m为非零项的个数。显然，当非零项的个数较少时（即m ） ，第二种表示法需要较少的存储空间。(2) 采用第一种表示法处理多项式相加较为简单，只需将次数较低的多项式的各项系数加到次数较高多项式的相应的系数上去即可。而第二种表示法要查找到相同的指数才能将系数进行相加，相加之和可能为0，为0时需要作删除操作；另外当某个多项式中有的项而在另一个多项式中没有，显然应作插入操作；当项数发生变化时，还要修改项数m的值。13设有多项式 A（x）=7+3x+9x8+5x17 B（x）=8x+22x7-9x8（1） 用单链表给出A（X）存储表示；（2） 用单链表给出B（X）存储表示；（3） 以上述两个单链表为基础，通过插入和删除等运算得出A（x）+B（x）的存储表示，使其存储空间覆盖A（x）和B（x）的存储空间。解答：（1） 每个结点由三个域组成 系数值指数值指向下一个结点的指针 单链表按x的升幂链接，并且不记录系数为0的项，于是A（x）可表示为 （2） 类似地，B(x)可表示为 （3）在实现A（x）+ B（x）时，可以A（x）的单链表为基础，逐项考虑B（x）。若B（x）中的指数与A（x）某项的指数相同，则将两个相应的系数相加，若结果为0，则从A（x）的单链表中删去此项的结点；若结果不为0，则修改A（x）单链表中该项的系数域，使之表示同类项合并的结果。若B（x）中某项的系数在A（x）单链表中未出现，则将该项结点插入A（x）单链表中。这样就得到下列重复使用A（x）和B（x）存储空间的A（x）+ B（x）的存储表示。 二算法设计1. 试编写一个高效的算法,删除线性表中所有值大于min,且小于max的元素(线性表中的元素均为整数，且存在这样的元素，min小于max)，并将剩下的元素集中存放在线性表的前面。要求采用顺序存储结构，时间复杂度为O（n），空间复杂度为O（0）（即不需要辅助存储空间）。解答: 算法一：void ds0203a(sqlist a,int min,int max) int i,j,len; i=1;j=2; while (j=n) if (ai=max) i+; j+; else if (aj=max)ai=aj; aj=（min+max）/2; i+; j+; else j+; len=i-1;return (len); 算法二：利用快速排序的思想（见数据结构教材中排序的内容）实现：void ds0203b(sqlist a,int min,int max) int i,j; i=1;j=n; while (ij) while (ai=max) i+; while (ajmin & ajmax) j-; ai=aj; i+; j-; len=i-1;return (len); 2. 设一维数组a中的元素依次为( a1，a2，.，an-1，an，b1，b2，.，bm)，试设计一个算法,将数组逆置,即使元素排列次序颠倒成为（b1，b2，.，bm，a1，a2，.， an-1，an ）。要求算法的空间复杂度为O（1）。解答:算法设计思想：（1）先将a逆置为： （bm，bm-1，.，b2，b1，an，an-1，.，a2，a1） （2）然后将（bm，bm-1，.，b2，b1）逆置为（b1，b2，.，bm）（3）将（an，an-1，.，a2，a1）逆置为（a1，a2，.， an-1，an ）经过上述处理之后便得到：（b1，b2，.，bm，a1，a2，.， an-1，an ）（1）实现逆置的递归算法如下：为了实现上述功能，先编写一个逆置函数，对a中从alow到ahig的部分进行逆置。void ds0204a(sqlist a,int low,int hig) int i,x; for (i=low;i=(low+hig)/2;i+) x=ai;ai=alow+hig-i;alow+hig-i=x; void ds0204b(sqlist a,int m,int n) ds0204a(a,1,m+n); ds0204a(a,1,m); ds0204a(a,m+1,m+n); （2）实现逆置的非递归算法如下：void invert(sqlist a, int m,int n) int i,x; for (i=1; i=(m+n)/2; i+) x=ai; ai=am+n+1-i; am+n+1-i=x； /*将ai和am+n+1-i互换*/ for (i=1; i=m/2; i+) x=ai; ai=am+1-i; am+1-i=x； /*将ai和am+1-i互换*/for (i=1; i=n/2; i+) x=am+i; ai=am+n+1-i; am+n+1-i=x； /*将am+i和am+n+1-i互换*/3. 用一维数组A和B分别表示两个线性表,元素的个数分别为m和n,若表中数据都是由小到大顺序排列的,且这(m+n)个元素中没有相重的。（1）设计一个算法将这两个线性表合并成一个,且元素仍是由小到大排列的线性表,并存储到另一个数组C中。下面是A和B的两个线性表合并结果的示例。 1 2 3 4 5 61 5691318 (a) A: 1 2 3 4 5 6 723714162134 B: 1 2 3 4 5 6 7 8 9 10 11 12 131235679131416182134 (b) C: （2）如果数组B的大小为(m+n)个单元,是否可不利用数组C而将合并成的线性表存放于数组B中,试设计此算法。（3）设数组A1.m+n中前m个有序，后n个有序，试设计一个算法，使得整个数组有序。解答: (1) 算法描述如下:void ds0206a(int am,int bn,int cm+n, int m,int n) int i=j=k=1; while(i=m & j=n) if(aibj) ck+=ai+; else ck+=bj+; while(i=m) ck+=ai+; while(j=n ) ck+=bj+;(2)方法一:从a和b的第一个元素开始,依次进行比较,当aibj时,应将ai插入b中,b表的长度加1.插入之前应将bj及其之后的元素相应后移。void ds0206b(int am,int bn, int m,int n) int i=j=1,k; while(i=m) if(ai=j;k-) bk+1=bk; bj=ai; i+; n+; j+; else j+; 方法二:首先确定合并之后的表的长度为(m+n),然后从a和b的最后一个元素开始,依 次向较小元素的方向进行比较,将该插入的元素依次从表的最后向前插入。void ds0206c(int am,int bn,int m,int n) int i=m,j=n,t=m+n; while(i0 & j0) if(aibj) bt-=bj-; else bt-=ai-; if(j=0) for(k=1;k=i;k+) bk=ak; （3）算法描述如下:void ds0206d(int am+n,int m,int n) int i=1,j=m+1,k; int x;dowhile(aiaj & ij) i+;if(i=i;k-) ak+1=ak; ai=x; j+; i+;while(i!=j);4. 已知线性表中的元素是无序的,并以带头结点的单链表作存储结构。试编写一个算法,删除表中所有值大于min且小于max的元素。解答: 算法描述如下:void ds0220a(pointer *head,int min,int max) pointer *p, *q; q=head; p=head-link; while(p!=NULL) if( p-datadata=max ) q=p; p=p-link; else q-link=p-link; free(p); p=q-link; 另外,若链表中的元素是有序的,则可采用如下算法:void ds0220b(pointer *head,int min,int max) /* 删除带表头结点的单链表中大于min且小于max的所有元素 */ pointer *p, *q; if(head!=NULL) q=head; p=head-link; while ( p!=NULL & p-datalink; while( p!=NULL & p-datalink; q-link=p; 5试设计一个算法，将一个带头结点的单向循环链表表示的多项式分解成两个多项式，其中一个仅含有奇次项指数，另一个仅含有偶次项指数，并要求利用原来链表中的结点空间来构成这两个链表。解答：（1）算法思想 建立奇数项循环链表的头结点，偶数项的头结点仍用原多项式循环链表的头结点； 当搜索的结点指数为偶数时，则只修改搜索指针及其前驱结点的指针； 当搜索的结点指数为奇数时，则将该结点链接到奇数项循环链表中。修改奇数循环链表指针和搜索指针。注意：要将该结点与原链表分离开来，且原链表仍保持循环链表。 分解结束的标志为：搜索指针等于原链表的头结点的指针。（2）算法描述typedef struct node int coef; /多项式的系数域int exp; /多项式的指数域 struct node *link; pointer; typedef struct node *pointer;void ds0221(pointer *plyn)pointer *p, *q, *s, *odd; odd= (node*) malloc (sizeof (node);odd-link=odd;q=plyn; p=plyn-link; s=odd; while (p!=plyn) if (p-exp%2=0) /指数为偶数在原链表中 q=p; p=p-link; else /指数为奇数在新链表中 q-link=p-link; p-link=s-link; s-link=p; p=q-link; s=s-link; 6已知由单链表表示的线性表中仅含有三类字符(字母字符，数字字符和其它字符)。试设计一个构造三个循环链表表示的线性表的算法，并使每个表中只含有同一类的字符，且利用原来链表中的结点空间来构成这三个链表，头结点可另开辟空间。解答：算法描述void ds0223(pointer *head) pointer *p, *q, *d, *b; d= (node*) malloc (sizeof (node); /生成数字字符链表的头结点 b= (node*) malloc (sizeof (node); /生成字母字符链表的头结点 p=head; q=p-link; while (q!=NULL) if (q-datadata=0) p-link=q-link; q-link=d-link; /构成循环 d-link=q; q=p-link; else if (q-datadata=A) | (q-datadata=a) p-link=q-link; q-link=b-link; /构成循环 b-link=q; q=p-link; else p=q; q=p-link; p-link=head; /构成循环 第三章 栈和队列一基本知识1栈和队列都是_。 A. 顺序存储的线性结构 B. 链式存储的线性结构 * C. 限制存取点的线性结构 D. 限制存取点的非线性结构 2设栈S最多能容纳4个元素，现有6个元素按a、b、c、d、e、f的顺序进栈，下列的_序列可能是出栈的序列。 Ae、b、c、d、a、f Bb、c、e、f、a、d*Cc、b、e、d、a、f Da、d、f、e、b、c3. 若一个栈的输入序列是1，2，3，n，输出序列的第一个元素是n，则第i个输出的元素是_。 A. n-i * B. n-i+1 C. i D. n-i-14若一个栈的输入序列依次是1，2，3，n，输出序列的第一个元素是i，则第j个输出的元素是_。 A i-j-1 B i-j C i-j +1 * D 不确定的5设栈S的初始状态为空，6个元素入栈的顺序为a,a,a,a,a,a。若出栈的顺序是a,a,a,a,a,a,则栈S的容量至少应该是_。 A2 *B3 C4 D6 6. 队列结构可用于_。A. 表达式求值和操作系统的作业调度 B.表达式求值和排队过程的模拟 * C. 排队过程的模拟和操作系统的作业调度 D.按逆序打印表和排队过程的模拟 7. 设头指针front指向队首元素的前一个位置，队尾指针rear指向队尾的元素。用循环队列解决队列的假溢出现象，其队列满的条件是_。 A.rearfront B.rearfront+1 C.frontrear+1 *D.front(rear+1) % n 8. 设头指针front指向队首元素的前一个位置，队尾指针rear指向队尾的元素。用循环队列解决队列的假溢出，队列空的条件是_。 * A.rearfront B.rearfront+1 C.frontrear+1 D.front(rear+1) % n9有如下递归函数：int dunno（int m） int value； if （m=0） value=3； else value=dunno（m-1）+5； return（value）；求执行语句printf（”%dn”,dunno(3)）;的结果。答案：1810阅读下列程序，选择正确答案。 #include try() char c; if (c=getchar()!=#) try(); putchar(c); main() try(); 若键盘键入1 2 3 4 5 6#时，则输出的结果是：答案：6 5 4 3 2 1二算法设计1假设以I和O分别表示入栈和出栈的操作，则初态和终态均为空的入栈和出栈的操作序列可以表示为仅由I和O组成的序列，称可以操作的序列为合法序列，否则称为非法序列。(1)下面所示的序列哪些是合法的？A. IOIIOIOO B. IOOIOIIOC. IIIOIOIO D. IIIOOIOO(2)通过对(1)的分析，写一个算法判定给定的操作序列是否是合法的。合法返回真，否则返回假。（假定被判定的操作序列已存入数组中，且仅含I和O两种字符）。解答：（1）根据栈的入栈和出栈操作原理，以及题目要求初始和终止时栈均为空的条件，判断操作序列的合法性可归结为以下几条准则： 序列中的第一个操作应为I操作，第n个操作应为o操作； 序列中前j个（包含第j个）操作中，I操作的个数应大于等于O操作的个数； 终止时I操作和O操作的个数应相等。根据以上分析，正确的操作序列应为：A和D。（2）判断操作序列合法性的算法。 方法一：void ds0301a(char an,int n) int j;int x=0,y=0;if (a1=O | an=I) return (0);for (j=1; j=n; j+) if (aj=I) x+;else y+;if(xy) return (0); if (x=y) return (1); else return (0);方法二：void ds0301b(char an,int n) int j;int top=0;char s;if (a1=O | an=I) return (0);for (j=1; j=0)=); scanf (%u,&n); /* 输入非负十进制整数n */ while (n!=0) s+top= n %16; /* 入栈n除以16的余数(16进制的低位) */ n=n/16; while (top!=0) /* 当栈不空 */ e=stop- /* 弹出栈顶元素且赋值给e */ if (edata; p=p-link; p=h; while (p!=NULL) if (p-data=stop) p=p-link; top-; else j=false; p=NULL; return j;5假设一个算术表达式中包含三种括号：圆括号“（”和“）”，方括号“”和“”,花括号“”和“”，且这三种括号可任意次序嵌套使用。试编写算法，判断给定表达式中所含括号是否配对出现的算法。解答：首先扫描表达式，将扫描到的“（”，或 “”，或 “”括号存入栈s中；若是“)”，或 “”，或 “”括号则与栈顶元素进行比较，配对则继续比较，不配对则退出；若是其他字符，则继续扫描。void ds0305 (exp,tag) char s;int top =0; int i=1, n;int tag=1;while (i=1) printf(“队列上溢出！n”); else if (top1=n)& (top2=0) for(i=1; i=n; i+) s2+top2=s1top1-; s1+top1=x; else s1+top1=x; （2）出队算法void ds03(s1,s2，n)ST s1,s2;int n; int y,i; if (top1=0)& (top2=0) printf(“队列下溢出