1、数据结构习题集与参考答案重要第一章 绪论一、填空题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 一个算法的时间复杂度通常用问题规模大小的函数来
2、表示，当一个算法的时间复杂度与问题规模n大小无关时，则表示为_；成正比关系时，则表示为_；成对数关系时，则表示为_；成平方关系时，则表示为_。5 数据结构的逻辑结构包括_、树型结构和图型结构三种类型，其中树型结构和图型结构合称为_；数据结构的存储结构主要包括_和_两种类型。6 线性结构的特点是：第一个结点_前驱结点，其余结点有且仅有_个前驱结点；最后一个结点_后继结点，其余每个结点有且仅有_个后继结点。7 树型结构的特点是：根结点没有_结点，其余每个结点有且仅有_个前驱结点；叶子结点_后继结点，其余结点可以有_个后继结点。8 图型结构的特点是：每个结点可以有_个前驱结点和后继结点。9 程序段f
3、or（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），其中：
4、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
5、) 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;第一章参考答案一、填空题1 数据元素，数据项，结构2 数据，关系3 树型4 O(1)，O(n)，O(log2n)，O(n2)5 线性结构，非线性结构，顺序结构，链式结构6 无，一，无，一7 前驱，一，无，任意8 任意9 O(n1/2)分析：设程序段中的循环体执行k次，则有不等式
6、成立，解此不等式得到不等式，因此。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结点之间两
7、条相反的弧用一条无向边来代替。三、指出下列各函数的功能并求出其时间复杂度。1 函数的功能是判断n是否是一个素数，其时间复杂度为O(n1/2)。分析：函数prime中出现的库函数sqrt为平方根函数，因此。2 函数的计算的值，其时间复杂度为O(n2)。3 函数的计算的值，其时间复杂度为O(n)。4 函数的功能是对数组r中的n个元素进行冒泡排序，其时间复杂度为O(n2)。分析：。第二章 线性表一、填空题1 设长度为n的顺序线性表在任何位置上插入或删除操作都是等概率的，则插入一个元素时平均需要移动_个元素，删除一个元素时平均需要移动_个元素。2 在顺序线性表中插入一个元素时，插入位置开始后的所有元素
8、均需要_移动一个位置。3 在顺序线性表中删除一个元素时，被删除元素后的所有元素均需要_移动一个位置。4 线性表的链式存储结构中，元素之间的线性关系是通过结点中的_来实现的。5 线性表的顺序存储结构中逻辑上相邻的元素，物理位置_相邻；线性表的链式存储结构中逻辑上相邻的元素，物理位置_相邻。6 已知单链表的长度为n，则在给定值为x的结点后插入一个新结点的时间复杂度为_。7 已知单链表的长度为n，则删除给定值为x的结点的时间复杂度为_。8 在单链表中设置头结点的作用是_。9 双向链表中每个结点含有两个指针域，其中一个指针域指向_结点，另一个指针域指向_结点。10 在长度为n的线性表中顺序查找某个结点
9、值为X的时间复杂度为_。二、选择题1在长度为n的顺序线性表中删除第i个元素(1=inext=p p=p-next p=p-next-next p-next=p-next-next4设指针p指向单链表中结点A，指针q指向单链表中结点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
10、-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-llin
11、k-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为单链表的头指针，则带头结点的单链表为空的判定条件是（ ）。 hea
12、d=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个结点的单链表，要求从尾部进行插入
13、。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分析：当在顺序线性
14、表中的第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始终指向当前链表中的最后一个结点，
15、新生成的结点直接在尾部进行插入。这种设置指针变量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及其以后版本中可以使用，它的作用是使得对形式
16、参数的修改可以影响到对应的实在参数。以后算法设计题中经常用到。2. 建立一个有n个结点的单链表，要求从头部进行插入。void createlklistfromhead (lklist *&head ) int i; lklist *p,*q; for (i=1,q=head=0;idata); p-next=head; head=p;提示：不断从头部插入新结点的方法来构造单向链表比不断从尾部插入新结点的方法来构造单向链表稍微操作简单一些。但顺序打印从尾部插入建立的单向链表所得到的序列与建立单向链表输入的序列一样，而顺序打印从头部插入建立的单向链表所得到的序列与建立单向链表输入的序列正好相反。3
17、. 用顺序存储结构实现线性表就地逆置算法，即在原表的存储空间内将线性表（a1，a2，an）逆置为(an，an-1，a1)。void invertsqlist(sqlist &list)int i,temp,n=list.n;for(i=1;inext; q-next=head; head=q;5. 已知集合A、B，求集合C=AB算法，要求集合A、B和C均用采用顺序存储结构表示。分析：本题的算法思想是顺序取出集合A中的元素Ai，然后再在集合B中从前向后进行顺序查找，如果找到等于该元素的结点则将其放入集合C中，否则什么也不做。本题算法思想同样适用于其后的第6题。void intersections
18、qlist(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. 设计在带有头结点的单向链
19、表中删除值为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; i
20、f (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;。第三章 栈和队列一、填空题
21、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. 设有一个顺序循环队列如上题中的约定，则该队列满的条件是_
