数据结构习题(含答案).doc

第一章 绪论一、填空题1 数据是描述客观事物的数、字符以及所有能输入到计算机且能够被计算机程序加工处理的符号集合。_是数据的基本单位；_是数据的最小单位。通常被计算机加工处理的数据不是孤立无关的，而是彼此之间存在着某种联系，将这种数据间的联系称为_。2 数据结构进行形式化定义时，可以从逻辑上认为数据结构DS是_的集合D和D上_的集合R所构成的二元组：DS=（D，R）。3 已知某数据结构的二元组形式表示为：A=(D，R)，D=01，02，03，04，05，06，07，08，09，R=r，r=，。则此数据结构属于_结构。4 一个算法的时间复杂度通常用问题规模大小的函数来表示，当一个算法的时间复杂度与问题规模n大小无关时，则表示为_；成正比关系时，则表示为_；成对数关系时，则表示为_；成平方关系时，则表示为_。5 数据结构的逻辑结构包括_、树型结构和图型结构三种类型，其中树型结构和图型结构合称为_；数据结构的存储结构主要包括_和_两种类型。6 线性结构的特点是：第一个结点_前驱结点，其余结点有且仅有_个前驱结点；最后一个结点_后继结点，其余每个结点有且仅有_个后继结点。7 树型结构的特点是：根结点没有_结点，其余每个结点有且仅有_个前驱结点；叶子结点_后继结点，其余结点可以有_个后继结点。8 图型结构的特点是：每个结点可以有_个前驱结点和后继结点。9 程序段for（i=1，s=0；sn；i+） s=s+i；的时间复杂度为_。10 常见的时间复杂度有常数阶O(1)、对数阶O(log2n)、线性阶O(n)、平方阶O(n2)、线性对数阶O(nlog2n)、立方阶O(n3)、指数阶O(2n)等等，这些数量阶之间的大小关系为_。二、分析下列用二元组形式表示的数据结构，指出他们分别属于何种类型的数据结构。1. A=（K，R），其中：K=a，b，c，d，e，f，g，h，R=r，r=，。2. B=（K，R），其中：K=a，b，c，d，e，f，g，h，R=r，r=，。3. C=（K，R），其中：K= a，b，c，d，e ，R=r，r=，。4. D=（K，R），其中：K=48，25，64，57，82，36，75，R=r1，r2，r1=，；r2=，。5. E=（K，R），其中：K=1，2，3，4，5，6，7，R=r，r=，。三、指出下列各函数的功能并求出其时间复杂度。1. void prime(int n)int i;for(i=2;isqrt(n) printf(“yes”); else printf(“no”);2. long sum1(int n)long sum,w,i;for(sum=0,i=1;i=n;i+) w=1; for(j=1;j=i;j+) w=wi; sum=sum+w; return(sum);3. long sum2(int n)long sum,w,i;for(sum=0, w=1,i=1;i=n;i+) w=wi; sum=sum+w;return(sum);4. void sort(int r ,int n)int i,j;for(i=1; in;i+) for(j=0;jrj+1) temp=rj;rj=rj+1;rj+1=temp;补充：0.分析下面算法（程序段），给出最大语句频度 ，该算法的时间复杂度是 _ 0. N2 _。 for (i=0;in;i+) for (j=0;jn; j+) Aij=0; 1 分析下面算法（程序段），给出最大语句频度 ，该算法的时间复杂度是_ N3 _。 s=0; for (i=0;in;i+) for (j=0;jn;j+) for (k=0;kn;k+) s=s+Bijk; sum=s; 2 分析下面算法（程序段）给出最大语句频度 ，该算法的时间复杂度是_根号N _。 i=s=0; while (sn) i+; s+=i; /s=s+i 3。 分析下面算法（程序段）给出最大语句频度 ，该算法的时间复杂度是_ log(N)_。 i=1; while (i=n) i=i*2;第一章参考答案一、填空题1 数据元素，数据项，结构2 数据，关系3 树型4 O(1)，O(n)，O(log2n)，O(n2)5 线性结构，非线性结构，顺序结构，链式结构6 无，一，无，一7 前驱，一，无，任意8 任意9 O(n1/2)分析：设程序段中的循环体执行k次，则有不等式成立，解此不等式得到不等式，因此。10 O(1)O(log2n)O(n)O(nlog2n)O(n2)O(n3)O(2n)二、分析下列用二元组形式表示的数据结构，指出他们分别属于何种类型的数据结构。1 线性结构2 树型结构3 图型结构4 图型结构分析：数据结构D中的关系集合R有两个关系r1和r2。如果只考虑关系r1，则为线性结构；如果只考虑关系r2，则为树型结构；如果把关系r1和r2联合起来考虑，则为图型结构。5 图型结构分析：若用图形来表示则可以看出r是E上的对称关系，为了简化起见，我们通常把和这两个有序偶对用一个无序偶对(x，y)或(y，x)来代替。在用图形表示时，我们把x结点和y结点之间两条相反的弧用一条无向边来代替。三、指出下列各函数的功能并求出其时间复杂度。1 函数的功能是判断n是否是一个素数，其时间复杂度为O(n1/2)。分析：函数prime中出现的库函数sqrt为平方根函数，因此。2 函数的计算的值，其时间复杂度为O(n2)。3 函数的计算的值，其时间复杂度为O(n)。4 函数的功能是对数组r中的n个元素进行冒泡排序，其时间复杂度为O(n2)。分析：。第二章 线性表一、填空题1 设长度为n的顺序线性表在任何位置上插入或删除操作都是等概率的，则插入一个元素时平均需要移动_个元素，删除一个元素时平均需要移动_个元素。2 在顺序线性表中插入一个元素时，插入位置开始后的所有元素均需要_移动一个位置。3 在顺序线性表中删除一个元素时，被删除元素后的所有元素均需要_移动一个位置。4 线性表的链式存储结构中，元素之间的线性关系是通过结点中的_来实现的。5 线性表的顺序存储结构中逻辑上相邻的元素，物理位置_相邻；线性表的链式存储结构中逻辑上相邻的元素，物理位置_相邻。6 已知单链表的长度为n，则在给定值为x的结点后插入一个新结点的时间复杂度为_。7 已知单链表的长度为n，则删除给定值为x的结点的时间复杂度为_。8 在单链表中设置头结点的作用是_。9 双向链表中每个结点含有两个指针域，其中一个指针域指向_结点，另一个指针域指向_结点。10 在长度为n的线性表中顺序查找某个结点值为X的时间复杂度为_。二、选择题1在长度为n的顺序线性表中删除第i个元素(1=inext=p p=p-next p=p-next-next p-next=p-next-next4设指针q指向单链表中结点A，指针p指向单链表中结点A的后继结点B，指针s指向被插入的结点X，则在结点A和结点B之间插入结点X的操作为（ ）。 s-next=p-next； p-next=s； q-next=s； s-next=p； p-next=s-next； s-next=p； p-next=s； s-next=q；5在长度为n的顺序线性表中的第i个元素(1=irlink=s； s-llink=p； p-rlink-llink=s； s-rlink=p-rlink； s-llink=p； s-rlink=p-rlink； p-rlink=s； p-rlink-llink=s； p-rlink=s； p-rlink-llink=s； s-llink=p； s-rlink-p-rlink； s-llink=p； s-rlink=p-rlink； p-rlink-llink=s； p-rlink=s；8指针p指向双向链表中的结点A，则删除结点A的操作是（ ）。 p-llink-rlink=p-rlink； p-rlink-llink=p-llink； p-rlink-llink=p-rlink； p-llink-llink=p-llink； p-llink-rlink=p-llink； p-rlink-llink=p-rlink； p-rlink-rlink=p-rlink； p-rlink-rlink=p-rlink；9线性表采用链式存储结构时，要求存储单元的地址（ ）。 必须是连续的 部分地址必须是连续的 一定是不连续的 连续不连续都可以10设head为单链表的头指针，则不带头结点的单链表为空的判定条件是（ ）。 head=NULL head-next=NULL head-next=head head!=NULL11设head为单链表的头指针，则带头结点的单链表为空的判定条件是（ ）。 head=NULL head-next=NULL head-next=head head!=NULL12设head和tail分别为单向循环链表的头指针和尾指针，则下列等式成立的是（ ）。 head=tail head-next=tail tail-next=head head-next=tail-next三、算法设计题顺序存储结构的类型定义：typedef struct int am; int n; sqlist;链式存储结构的类型定义：typedef struct node int data; struct node *next; lklist;1. 建立一个有n个结点的单链表，要求从尾部进行插入。2. 建立一个有n个结点的单链表，要求从头部进行插入。3. 用顺序存储结构实现线性表就地逆置算法，即在原表的存储空间内将线性表（a1，a2，an）逆置为(an，an-1，a1)。4. 用链式存储结构实现线性表就地逆置算法，即在原表的存储空间内将线性表（a1，a2，an）逆置为(an，an-1，a1)。5. 已知集合A、B，求集合C=AB算法，要求集合A、B和C均用采用顺序存储结构表示。6. 已知集合A、B，求集合C=AB算法，要求集合A、B和C均用采用链式存储结构表示。7. 设计在带有头结点的单向链表中删除值为X的结点算法。第二章参考答案一、填空题1 n/2，(n-1)/2分析：当在顺序线性表中的第i（1=i=n+1）个位置之前插入一个新元素时，从第i个元素起向后的n+1-i个元素均要向后移动一个位置。因此在等概率情况下，插入操作中元素的平均移动次数为；当在顺序线性表中删除第i（1=ileft）和指向后继结点的指针（p-right），然后再分别表示出前驱结点中的右指针域（p-left-right）和后继结点的左指针域（p-right-left），最后分别修改前驱结点中的右指针域和后继结点的左指针域。9 (4)10 (1)11 (2)12 (3)三、算法设计题1. 建立一个有n个结点的单链表，要求从尾部进行插入。分析：本题的算法思想是设置指针变量q始终指向当前链表中的最后一个结点，新生成的结点直接在尾部进行插入。这种设置指针变量q的方法使得操作比较简单，否则每次在尾部插入新结点时需要用一个临时指针变量从链表头部移到链表尾部。void createlklistfromtail (lklist *&head ) int i; lklist *p,*q; for (i=1,head=0;idata);p-next=0; if(i=1)head=q=p;else q-next=p;q=p;提示：以下形式参数表中出现在形式参数名前加符号“&”的现象，这种现象在我们常见的Turbo C 2.0版本中不能使用，但在Borland C 3.1及其以后版本中可以使用，它的作用是使得对形式参数的修改可以影响到对应的实在参数。以后算法设计题中经常用到。2. 建立一个有n个结点的单链表，要求从头部进行插入。void createlklistfromhead (lklist *&head ) int i; lklist *p,*q; for (i=1,q=head=0;idata); p-next=head; head=p;提示：不断从头部插入新结点的方法来构造单向链表比不断从尾部插入新结点的方法来构造单向链表稍微操作简单一些。但顺序打印从尾部插入建立的单向链表所得到的序列与建立单向链表输入的序列一样，而顺序打印从头部插入建立的单向链表所得到的序列与建立单向链表输入的序列正好相反。3. 用顺序存储结构实现线性表就地逆置算法，即在原表的存储空间内将线性表（a1，a2，an）逆置为(an，an-1，a1)。void invertsqlist(sqlist &list)int i,temp,n=list.n;for(i=1;inext; q-next=0; while(p!=0)q=p; p=p-next; q-next=head; head=q;5. 已知集合A、B，求集合C=AB算法，要求集合A、B和C均用采用顺序存储结构表示。分析：本题的算法思想是顺序取出集合A中的元素Ai，然后再在集合B中从前向后进行顺序查找，如果找到等于该元素的结点则将其放入集合C中，否则什么也不做。本题算法思想同样适用于其后的第6题。void intersectionsqlist(sqlist lista, sqlist listb,sqlist &listc)int i,j;for(listc.n=0,i=0;i=lista.n-1; i+)for(j=0;j=listb.n-1; j+) if (listb.aj=lista.ai) break;if(jnext)for(q=listb;q!=0;q=q-next) if (p-data=q-data) break;if(q!=0) s=(lklist *)malloc(sizeof(lklist); s-data=p-data; s-next=listc; listc=s;7. 设计在带有头结点的单向链表中删除值为X的结点算法。分析：本题的算法思想是首先在单链表中查找值为x的结点，如果单链表为空或在单链表中找不到值为x的结点则给出相应的提示信息，否则进行删除操作。为了便于删除操作的实现而设置指针变量p指向被删除的结点，指针变量q始终指向其前驱结点。void deletelklist(lklist *&head, int x)lklist *q,*p;if (head-next=0) printf(“This linklist is emptyn”);else for(q=head,p=head-next; p!=0; q=p, p=p-next) if (p-data=x) break; if (p=0) printf(“Not found %d in this linklistn”,x); else q-next=p-next; free(p);提示：在链表中引入头结点后可以消除空表的特殊性，统一表示和处理空表和非空表的情形，从而简化插入和删除等操作的某些细节。具体涉及到本题中，如果没有引入头结点，则在找到值为x的结点后要区分该结点是第一个结点还是其它结点，而引入头结点后，则这两种情况就可以统一处理。如果本题中的单链表没有带头结点，则需要将上述黑体中的代码改为代码if (p=head) head=p-next; else q-next=p-next;。第三章 栈和队列一、填空题1. 线性表、栈和队列从逻辑上来说都是_结构。可以在线性表的_位置插入和删除元素；对于栈只能在_插入和删除元素；对于队列只能在_插入元素和在_删除元素。2. 栈的插入和删除只能在栈的栈顶进行，后进栈的元素必定先出栈，所以又把栈称为_表；队列的插入和删除运算分别在队列的两端进行，进行插入的一端叫做_，进行删除的一端叫做_，先进队的元素必定先出队，所以又把队列称为_表。3. 假设用向量S1：m来存储顺序栈，指针top指向当前栈顶的位置。则当栈为空时满足的条件是_；当栈为满时满足的条件是_。4. 设有一个空栈，现有输入序列1、2、3、4、5，经过push、push、pop、push、pop、push、push、pop、pop、 pop后，输出序列为_。5. 在一个顺序循环队列中为了方便入队列和出队列的操作通常约定头指针front指向实际队头元素的_前一个位置_，尾指针rear指向当前实际队尾元素的_所在位置_。若该顺序循环队列有m个存储单元，则队列满时共有_个元素。6. 设有一个顺序循环队列如上题中的约定，则该队列满的条件是_，队列空的条件是_。7. 不论是顺序栈（队列）还是链式栈（队列），插入（删除）运算的时间复杂度均为_。8. 系统在函数调用前自动把调用后的_压入堆栈；当函数调用结束后，系统又自动作退栈处理，并将程序执行流程无条件转移到所保存的_处继续执行。二、选择题1设栈的输入序列是1、2、3、n，输出序列的第一个元素是n，则第i个输出元素是（ ）。 n-i n-i-1 n-i+1不确定2设元素进栈次序为A、B、C、D、E，则下列不可能的出栈序列是（ ）。 ABCDE BCDEA EABCD EDCBA3设用一维数组sm表示栈的存储空间，用top指向当前栈顶元素（其初始值为-1），则进行出栈时的操作序列是（ ）。 x=sop； x=stop；top=0； x=stop；top=top-1； x=stop；top=top+1；4设指针hs指向栈顶，指针s指向插入的结点A，则插入结点A时的操作为（ ）。 hs-next=s； s-next=hs； hs=s； s-next=hs-next； hs-next=s； s-next=hs； hs=hs-next；5设用一维数组sm表示栈的存储空间，用top指向当前栈顶元素（其初始值为-1），则进行入栈时的操作序列是（ ）。 stop =x； top=top+1；stop=x； top=top-1；stop=x； stop=x；top=top+1；6设front是链式队列的头指针，rear是链式队列的尾指针，s指向插入的结点A，则插入结点A的操作为（ ）。 front-next=s； front=s； s-next=rear； rear=s； rear-next=s； rear=s； s-next=front； front=s；7设front是链式队列的头指针，rear是链式队列的尾指针，则删除队头元素的操作为（ ）。 front=front-next； rear=rear-next； rear=front-next； front=rear-next；8对于一个具有m个存储单元的顺序循环队列，设front为队头指针，rear为队尾指针，则该队列中队列元素的个数计算公式为（ ）。 rear-front front-rear (rear-front)%m (rear-front+m)%m9 设用一维数组qm作为顺序循环队列的存储空间，front指向队头元素的前一个位置，rear指向队尾元素的当前位置，则入队列的操作序列为（ ）。 qrear =x；rear=rear+1； qrear=x；rear=rear-1； rear=(rear+1)%m；qrear =x； rear=(rear-1)%m；qrear=x；10 设用一维数组qm作为顺序循环队列的存储空间，front指向队头元素的前一个位置，rear指向队尾元素的当前位置，则出队列的操作序列为（ ）。 x=qfront；front=front+1；front=(front+1)%m；x=qfront； x=qfront；front=front-1；front=(front-1)%m；x=qfront；三、算法设计题1 设有两个顺序栈S1和S2共享一个存储区S0：m-1，为了尽量利用存储空间减少溢出的可能性，采用栈顶相向、迎面增长的存储方式，要求分别设计两个栈的入栈和出栈操作。2 设计算法判断表达式中的圆括号是否配对出现。3 设用一个单向循环链表来表示队列（也称循环队列），该队列只设一个队尾指针rear，不设队头指针front，要求设计出该队列的入队列和出队列操作。4 假设以一个一维向量q0：m-1作为顺序循环队列的存储空间，同时设变量rear和len分别指示顺序循环队列中的队尾元素的位置和实际队列中的元素个数，要求设计出该队列的入队列和出队列操作。5 将数字1、2、n按顺时针方向排列成环形，按顺时针方向从1开始计数，计满时则输出该位置上的数字并从环中删除该数字，然后从下一个数字开始继续计数，直到环中所有数字均被输出为止，要求设计一个算法完成此功能。第三章参考答案一、填空题1 线性，任何，栈顶，队尾，队头2 先进后出（FILO），队尾，队头，先进先出（FIFO）3 top=0，top=m 4 235415 前一个位置，所在位置， m-1分析：在顺序循环队列中约定头指针front和尾指针rear所指向的位置，是牺牲掉一个存储单元而方便表示队列空和队列满的条件，因此顺序循环队列中实际可用的存储单元只有m-1个。6 (rear+1)%m=front，rear=front7 O(1)8 返回地址，返回地址二、选择题1. (3)分析：设栈的输入序列是1、2、3、n，输出序列的第一个元素是n，则输出序列必定是n、n-1、n-2、1，因此第i个输出元素是n+1-i。2. (3)3. (3)4. (2)5. (2)6. (3)7. (1)8. (4)分析：顺序循环队列中的元素个数=，整理合并可写成(rear-front+m)%m。9. (3)10. (2)三、算法设计题1. 设有两个顺序栈S1和S2共享一个存储区S0：m-1，为了尽量利用存储空间减少溢出的可能性，采用栈顶相向、迎面增长的存储方式，要求分别设计两个栈的入栈和出栈操作。分析：本题算法思想是引入形式参数flag，当形式参数flag的值为1时表示对栈1进行操作，flag的值为2时表示对栈2进行操作。typedef struct int sm; int top1; int top2; sqstack;void push(sqstack &stack , int x,int flag)if (stack.top1+1=stack.top2) printf(“stack is fulln”);else if (flag=1) stack.top1+; stack.sstack.top1=x;else if(flag=2)stack.top2-; stack.sstack.top2=x;else printf(“input errorn”);void pop(sqstack &stack , int &y, int flag)if (flag=1) if(stack.top1=m) printf(“emptyn”); else y=stack.sstack.top2;stack.top2+; else printf(“input errorn”);2. 设计算法判断表达式中的圆括号是否配对出现。分析：本题的算法思想是顺序扫描表达式，当扫描到左圆括号时进栈而扫描到右圆括号时出栈，如果扫描到右圆括号时不能出栈或扫描表达式结束时栈中仍有左圆括号则意味表达式中圆括号不匹配，否则表达式中圆括号匹配。typedef struct int sm; int top; sqstack;int matchbracket()char ch; sqstack stack; stack.top= -1;do ch=getchar();if (ch=() stack.top=stack.top+1; stack.sstack.top=ch; else if (ch=) if (stack.top0) return(0); else stack.top=stack.top-1;while(ch!= #);if (stack.topdata=x;if (rear=0) rear=p; rear-next=rear;else p-next=rear-next; rear-next=p; rear=p;void outlkqueue(lklist *rear, int *y)lklist *p;if (rear=0) printf(“queue is emptyn”);else if rear-next=rear y=rear-data; rear=0; else p=rear-next; y=p-data; rear-next=p-next; free(p);4. 假设以一个一维向量q0：m-1作为顺序循环队列的存储空间，同时设变量rear和len分别指示顺序循环队列中的队尾元素的位置和实际队列中的元素个数，要求设计出该队列的入队列和出队列操作。分析：本题中出队列的算法思路是设置一个临时变量front指向当前队列中队头元素的实际位置，考虑到表达式queue.rear+1-queue.len的值可能为负，因此设置front的值为(queue.rear+1-queue.len+m)%m。typedef struct int qm; int rear; int len; sqqueue;void insqqueue(sqqueue &queue, int x)if (queue.len=m) printf(“queue is fulln”);else queue.rear=(queue.rear+1)%m; queue.qqueue.rear=x;queue.len+;void outsqqueue(sqqueue &queue, int *y)int front;if (queue.len=0) printf(“queue is emptyln”);else front=queue.rear+1-queue.len+m%m; y=queue.qqueue.front;queue.len-;5. 编写一个算法解决约瑟夫（Josephus）环问题。其问题是：设有n个人围坐在一张圆桌周围，现从第一个人开始从1报数，报到k的人出离开圆桌，接着从下一个人从1开始重新报数，以此类推，直到他们都离开圆桌，求出他们离开圆桌的先后顺序。分析：本题的算法思路是设置变量sum和num，其中变量 sum表示当前已经离开圆桌的人数个数，变量num表示当前的报数。void Josephus( int n, int k) int i,num,sum,r100; for(i=0;in; i+) ri=i; for(sum=num=i=0; sumn; i=(i+1)%n) if (ri!=-1) num+; if (num % k=0) printf(%dt,i); num=0;sum+; ri= -1;第四章 字符串和数组一、填空题1. 设字符串S1=“ABCDEF”，S2=“PQRS”，则运算S=CONCAT(SUB(S1，2，LEN(S2)，SUB(S1，LEN(S2)，2)的结果为S=_。2. 判断两个字符串相等的充要条件是_。3. 下列程序段实现子串t在主串s中位置的算法，要求在下划线处填上正确语句。int index(char s , char t )i=j=0;while(istrlen(s) & j=j）的地址为_。7. 设有n行n列的三对角矩阵A，每个数组元素占L个字节的存储单元，按照从上到下从左到右的顺序将三条对角线上的元素存放在3n-2个连续的存储单元中，已知A00的地址为1000，则三对角线上元素Aij的地址为_。8. 已知稀疏矩阵A=，则A的三元组表为_。二、算法设计题1. 设用顺序存储结构存储字符串S1和S2，要求设计一个函数完成对两个字符串的比较。若S1S2时则返回正数；若S1=S2时则返回0；若S1S2时则返回正数；若S1=S2时则返回0；若S1S2时则返回负数。int comparestring(char s1 , char s2 )int i;for(i=0;s1i!=0;i+) if (s1i!=s2i) break; return(s1i-s2i);2. 用顺序存储结构实现在字符串S中删除所有其值等于ch（假设ch=A）的字符的算法。void deletestring(char s ,char ch)int i=0,j;while(si!=0) if (si=ch) for(j=i+1; sj!=0; j+) sj-1=sj; sj-1=0;else i+;3. 设计一个算法判断字符串S中的字符是否关于中心对称。typedef struct char sm; int top; sqstack;int stringsymmetry(char s )int i; sqstack stack; stack.top= -1;for(i=0;si!=0;i+) stack.top+; stack.sstack.top=si;for(i=0;si!=0;i+) if (si=stack.sstack.top) stack.top=stack.top-1; else return(0);return(1);第五章 树一、填空题1. 设一棵树的二元组形式表示为T=（D，R），其中D=A，B，C，D，E，F，G，R=(A，B)，(A，C)，(A，D)，(B，E)，(C，F)，(C，G)，则该树的度数为_，树的深度为_，叶子结点的个数为_，分支结点的个数