数据结构习题

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=, , , , , 。则此数据结构属于树型结构。1 .一个算法的时间复杂度通常用问题规模大小的函数来表示，当一个算法的时间复杂度与问题规模n大小无关时，则表示为0(1);成正比关系时，则表示为O(n);成对数关系时，则表示为O(log2n)；成平方关系时，则表示为O(n2)。4. 数据结构的逻辑结构包括线性结构、树型结构和图型结构三种类型，其中树型结构和图型结构合称为非线性结构；数据结构的存储结构主要包括顺序结构和链式结构两种类型。5. 线性结构的特点是：第一个结点无前

2、驱结点，其余结点有且仅有一个前驱结点；最后一个结点无后继结点，其余每个结点有且仅有一个后继结点。6. 树型结构的特点是：根结点没有前马蹒点，其余每个结点有且仅仁个前驱结点；叶子结点无后继结点，其余结点可以有任意 个后继结点。7. 图型结构的特点是：每个结点可以有任意一个前驱结点和后继结点。8. 程序段for (i=1, s=0； sn； i+) s=s+i；的时间复杂度为 O(n1/2)9. 常见的时间复杂度有常数阶O(1卜对数阶O(loqn)、线性阶O(n卜平方阶O(n线性又t数阶O(nlog2n)、立方阶。济、指数阶O(2n)等等，这些数量阶之间的大小关系为 O(1)O(log2n)O(n)O(nlog2n)O(n2)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=,

3、,。图型结构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= , , , , , , o图型结构三、指出下列各函数的功能并求出其时间复杂度。1. void prime(int n)inti;for(i=2;isqrt(n)printf(“yes ); else printf( no” );函数的功能是判断n是否是一个素数，其时间复杂度为O(n1/2)2. long sum1(int n)long sum,Wfor(sum=0,i=1;i=n;i+)w=1; for(j=1;j=i;j+)w=W; sum=sum+w; x return(sum);函数的计算 的值，其时间复杂度为0(n2)3. long sum2(int n)long sum,Wfor(sum=0, w=1,i=1;i=n;i+) w=wi; sum=sum+w;return(sum);函数的计算的值，其时间复杂度为0

4、(n)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;函数的功能是对数组r中的n个元素进行冒泡排序,其时间复杂度为O(n2)o 第二章 线性表一、填空题1 设长度为 n 的顺序线性表在任何位置上插入或删除操作都是等概率的，则插入一个元素时平均需要移动_ n/2个元素，删除一个元素时平均需要移动_ (n-1)/2_个元素。_2 在顺序线性表中插入一个元素时，插入位置开始后的所有元素均需要_向后 移动一个位置。3 在顺序线性表中删除一个元素时，被删除元素后的所有元素均需要向前 移动一个位置。4 线性表的链式存储结构中，元素之间的线性关系是通过结点中的_指针域 来实现的。5 线性表的顺序存储结构中逻辑上相邻的元素， 物理位置 一定 相邻； 线性表的链式存储结构中逻辑上相邻的元素， 物理位置 不一定 相邻。6 已知单链表的长度为n,则在给定值为x的结点后插入一个新结点的时间复杂度为_O(n)-7 已知单链表的长度为n,则删除给定值为x的结点的时间复杂度为_O(n

5、)8 在单链表中设置头的点的作用是_消除空表的特殊性，统一表示和处理空表和非空表的情形，从而简化插入和删除等操作的某些细节。9 双向链表中每个的点含有两个指针域，其中一个指针域指向_前驱 的点，另一个指针域指向_后继 的点。10 在长度为 n 的线性表中顺序查找某个的点值为 X 的时间复杂度为O(n)。 _、选择题1.在长度为n的顺序线性表中删除第i个元素(1=inext=p p=p-nextp=p-next-next p-next=p-next-next4 . 设指针q指向单链表中结点A,指针p指向单链表中结点A的后继结点B,指针s指向被插入的结点X,则在结点A和结点B之间插入结点X的操 作为( 2 ) 。s-next=p-nex；t p-next=s； q-next=s； s-next=p；p-next=s-nex；t 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

6、-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 的操作是( 1 ) 。 p-llink-rlink=p-rlink； p-rlink-llink=p-rlink； p-llink-rlink=p-llink； p-rlink-rlink=p-rlink；p-rlink-llink=p-llink； p-llink-llink=p-llink； p-rlink-llink=p-rlink； p-rlink-rlink=p-rlink；#9线性表采用链式存储的构时，要求存储单元的地址(4 ) 部分地址必须是连续的 必须是连续的一定是不连续的连续不连续都可以10 .设hea昉单链表的头指针，则不带头结点的单链表为空的判定条件是（1 head=NULL head-next=NULL head-next=head head!

7、=NULL11 .设hea昉单链表的头指针，则带头结点的单链表为空的判定条件是（2 head=NULL head-next=NULL head-next=head head!=NULL12 .设hea用口 tail分别为单向循环链表的头指针和尾指针，则下列等式成立的是（3 head=tail head-next=tail tail-next=head head-next=tail-next第三章栈和队列一、填空题1. 线性表、栈和队列从逻辑上来说都是线性结构。可以在线性表的任何位置插入和删除元素；对于栈只能在_栈顶插入和删除元素；对于队列只能在队尾插入元素和在队头删除元素。2. 栈的插入和删除只能在栈的栈顶进行，后进栈的元素必定先出栈，所以又把栈称为先进后出（FILO）表；队列的插入和删除运算分别在队列的两端进行，进行插入的一端叫做队尾，进行删除的一端叫做队头,先进队的元素必定先出队，所以又把队列称为先进先出（FIFO） 表。3. 1（设用向量S1： m来存储顺序栈，指针top指向当前栈顶的位置。则当栈为空时满足的条件是top=Q当栈为满时满足的条件是 top=m4. 设有一个空栈，现有输入序列 1、2、3、4、5,经过push push pop push pop、push push pop pop、pop后，输出序列为 235415. 在一个顺序循环队列中为了方便入队列和出队列的操作通常约定头指针front指向实际队头元素的期一个位置尾指针rear指向当前实际队尾元素的所在位置,若该顺序循环队

《数据结构习题》由会员夏**分享，可在线阅读，更多相关《数据结构习题》请在金锄头文库上搜索。