数据结构习题.doc

第1章 概论一、选择题1. 要求同一逻辑结构的所有数据元素具有相同的特性，这意味着（ B ）A、数据元素具有同一的特点。B、不仅数据元素包含的数据项的个数要相同，而且对应数据项的类型要一致。C、每个数据元素都一样。D、数据元素所包含的数据项的个数要相等。2. 数据结构是一门研究非数值计算的程序设计问题中计算机的（ （c） ）以及它们之间的（ B ）和运算的学科。（1）A、操作对象 B、计算方法 C、逻辑存储 D、数据映象（2）A、结构 B、关系 C、运算 D、算法3. 数据结构被形式的定义为（D，R），其中D是（ （B） ）的有限集合，R是D上（ （D） ）的有限集合。（1）A、算法 B、数据元素 C、数据操作 D、逻辑结构（2）A、操作 B、映象 C、存储 D、关系4. 在数据结构中，从逻辑上可以把数据结构分为（ C ）A、动态结构和静态结构 B、紧凑结构和非紧凑结构C、线性结构和非线性结构 D、内部结构和外部结构5. 线性-表的顺序存储结构是一种（ A ）的存储结构。A、随机存取 B、顺序存取 C、索引存取 D、Hash存取6. 算法分析的目的是（ C ）A、找出数据结构的合理性 B、研究算法中的输入和输出的关系C、分析算法的效率以求改进 D、分析算法的易懂性和文档性7. 计算机算法指的是（ （C） ）。它必需具备输入、输出和（ （B） ）等五个特征。（1） A、计算方法 B、排序方法 C、解决某一问题的有限运算序列 D、调度方法（2） A、可行性、可移植性和可扩充性B、可行性、确定性和有穷性C、确定性、有穷性和稳定性D、易读性、稳定性和安全性8. 线性表若采用链表存储结构时，要求内存中可用存储单元的地址（ D）A、必须是连续的 B、部分地址必须是连续的C、一定是不连续的 D、连续不连续都可以9. 在以下的叙述中，正确的是（B ）A、线性表的线性存储结构优于链式存储结构B、二维数组是它的每个数据元素为一个线性表的线性表C、栈的操作方式是先进先出D、队列的操作方式是先进后出10. 根据数据元素之间关系的不同特性，以下四类基本的逻辑结构反映了四类基本的数据组织形式。以下解释错误的是 ( A )A、集合中任何两个结点之间都有逻辑关系但组织形式松散B、线性结构中结点按逻辑关系依次排列形成一条锁链C、树形结构具有分支、层次特性，其形态有点像自然界中的树D、图状结构中的各个结点按逻辑关系互相缠绕，任何两个结点都可以邻接11. 以下说法正确的是( D )A、数据元素是数据的最小单位B、数据项是数据的基本单位C、数据结构是带有结构的各数据项的集合D、数据结构是带有结构的数据元素的集合二、判断题1. 数据元素是数据的最小单位。02. 数据结构是带有结构的数据元素的集合。13. 数据结构，数据元素，数据项在计算机中的映象分别称为存储结构，结点，数据域。14. 数据项是数据的基本单位。05. 数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用需要建立的。16. 数据的物理结构是数据在计算机中实际的存储形式。17. 算法和程序没有区别，所以在数据结构中二者是通用的。08. 顺序存储结构属于静态结构，链式存储结构属于动态结构。0三、填空题1. 所谓数据的逻辑结构指的是数据元素之间的 _逻辑关系_。2. 数据结构是相互之间存在一种或多种特定关系的数据元素的集合，它包括三方面的内容数据的逻辑结构、数据的存储结构、对数据施加的操作。3. 数据的逻辑结构包括 集合 、 线性结构 、 树形结构 和图状构图 四种类型。4. 在线性结构中，开始结点_没有_前驱结点，其余每个结点有且只有_1_个结点。5. 在树形结构中，树根结点只有_1_，其余每个结点有且只有_1_前驱结点；叶子结点没有_后继_结点，其余每个结点的后继结点可以_任意个_。6. 在图形结构中，每个结点的前驱结点和后继结点可以有_任意个_。7. 算法的五个重要特性是_有穷性_、_确定性_、_可行性_、_输入_、_输出_。8. 下列程序段的时间复杂度是_。for (i=1;i=n;i+) Aij=0;9. 下列程序段的时间复杂度是_。s=0;for(i=1;i=n;i+) for(j=1;j=n;j+) s=s+Bij;sum=s;10. 存储结构是逻辑结构的_物理_实现。11. 从数据结构的观点看，通常所说的数据应分成三个不同的层次，即_数据_、_数据元素_和_数据项_。12. 根据需要，数据元素又被称为_结点_、_记录_、_元素_或_顶点_。13. 通常，存储结点之间可以有_顺序存储、链式存储、索引存储、散列存储_、_、_、_四种关联方式，称为四种基本存储方式。14. 通常从_正确性、可读性、健壮性、高效性_、_、_、_等几方面评价算法的(包括程序)的质量。15. 一个算法的时空性能是指该算法的_时间复杂度_和_空间复杂度_，前者是算法包含的_计算量_，后者是算法需要的_存储量_。16. 在一般情况下，一个算法的时间复杂性是_问题规模_的函数。17. 常见时间复杂性的量级有：常数阶O(_1_)、对数阶O(_)、线性阶O ( _n_)、平方阶O(_)、和指数阶O(_)。通常认为，具有指数阶量级的算法是_不可行_的。18. 数据结构的基本任务是数据结构的_设计_和_实现_。19. 数据对象是性质相同的 数据元素 的集合。20. 抽象数据类型是指一个 数学模型 以及定义在该模型上的一组操作。四、应用题1. 分析下列程序段的时间复杂度。i=1；WHILE（i=n）i=i*2；2. 叙述算法定义及其重要特性。3. 简述下列术语：数据，数据元素，数据结构，数据对象。4. 逻辑结构与存储结构是什么关系?5. 将数量级，n，n2，n3，nlog2n，log2n，2n，n!，按增长率进行排列。6. 设有数据逻辑结构为：D=k1,k2,k3,k9R=,画出这个逻辑结构的图示，并确定相对于关系R，哪些结点是开始结点，哪些结点是终端结点？7. 设有如图1.1所示的逻辑结构图，给出它的逻辑结构，并说出它是什么类型的逻辑结构。k1k5k8k2k3k6k4k7图1.18. 分析下列程序的时间复杂度（设n为正整数） (1) int rec(int n) if(n=1) return(1); else return(n*rec(n-1); (2) x=91;y=100;while(y0) if(x10) y-;(3) i=1;j=0; while(i+jj) j+; else i+;(4) x=n;y=0; while(x=(y+1)*(y+1) y+;9. 设n为正数。试确定下列各程序段中前置以记号的语句的频度：（1）i=1;k=0;while(i=n-1)k+=10*i; i+;(2) k=0; for(i=1;i=n;i+) for(j=i;jnext=NULL C、head-next=head D、head!=NULL10. 非空循环单链表head的尾结点*p满足（ C ）A、p-next=NULL B、p=NULL C、p-next=head D、p=head 11. 在循环双链表的*p结点之后插入*s结点的操作是（ D ）A、p-next=s; s-prior=p; p-next-prior=s; s-next=p-next;B、p-next=s; p-next-prior=s; s-prior=p; s-next=p-next;C、s-prior=p; s-next=p-next;p-next:=s; p-next-prior=s; D、s-prior =p; snext=pnext; pnext-prior =s;p-next=s; 12. 在一个单链表中，已知*q结点是*p结点的前驱结点，若在*q和*p之间插入结点*s，则执行（ C ）A、s-next=p-next; p-next=s;B、p-next=s-next; s-next=p;C、q-next=s; s-next=p;D、p-next=s; s-next=q;13. 在一个单链表中，若*p结点不是最后结点，在*p之后插入结点*s，则执行（ B ）A、s-next=p; p-next=s;B、s-next=p-next; p-next=s;C、s-next= p-next; p=s;D、p-next=s; s-next=p;14. 若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（ A ）存储方式最节省时间。A、顺序表 B、单链表 C、双链表 D、单循环链表15. 设rear是指向非空带头结点的循环单链表的尾指针，则删除表中第一元素的操作可表示为（D ）A、p=rear; rear=rear-next; free(p)B、rear=rear-next; free(rear);C、rear=rear-next-next; free(rear); D、p=rear-next-next; rear-next-next=p-next; free(p);16. 在一个单链表中，若删除*p结点的后继结点，则执行（ A ）A、q=pnext; pnext=qnext; free(q);B、p=p-next; p-next= p-next-next;free(p);C、p-next= p-next;free(p-next);D、p= p-next-next;free(p-next);17. 设指针P指向双链表的某一结点，则双链表结构的对称性可用（ C ）式来刻画A、p-prior-next=p-next-nextB、p-prior-prior=p-next-priorC、p-prior-next=p-next-priorD、p-next-next=p-prior-prior18. 在循环链表中，将头指针改设为尾指针rear后，其头结点和尾结点的存储位置分别是 （ B ）A、rear和rear-next-nextB、rear-next 和rearC、rear-next-next和rearD、rear和rear-next19. 循环链表主要优点是（ D ）A、不再需要头指针了B、已知某个结点的位置后，能够容易找到它的直接前趋C、在进行插入、删除运算时，能更好地保证链表不断开D、从表中任一结点出发都能扫描到整个链表20. 在线性表的下列存储结构中，读取元素花费时间最少的是（ D ）A、单链表 B、双链表 C、循环链表 D、顺序表二、判断题1. 顺序存储的线性表可以随机存取。A2. 顺序存储的线性表的插入和删除操作不需要付出很大的代价，因为平均每次操作只有近一半的元素需要移动。B3. 线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。A4. 在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上不一定相邻。B5. 在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。A6. 在单链表中，可以从头结点进行查找任何一个元素。A7. 线性表的链式存储结构优于顺序存储结构。B8. 在线性表的顺序存储结构中，插入和删除元素时，移动元素的个数与该元素的位置有关。A9. 在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。B10. 顺序存储方式只能用于存储线性结构。B三、填空题1. 为了便于讨论，有时将含n(n0)个结点的线性结构表示成(a1，a2,an)，其中每个ai代表一个_结点_。a1称为_第一个_结点，an称为_最后一个_结点，i称为ai在线性表中的_位置_。对任意一对相邻结点ai、ai1(1inext=head后，该单链表构成 单循环链表 。16. 在单链表中，若p和s是两个指针，且满足p-next与s相同，则语句p-next=s-next作用是 删除 s指向的结点。17. 设r指向单循环链表的最后一个结点，要在最后一个结点之后插入s所指的结点，需执行的三条语句是_ snext=r-next_；r-next=s; r=s;。18. 在单链表中，指针p所指结点为最后一个结点的条件是_ pnext=NULL _。19. 在双循环链表中，若要在指针p所指节点前插入s所指的节点，则需执行下列语句：s-next=p；s-prior=p-prior；1. _ ppriornext_=s；p-prior=s；20. 在单链表中的p所指结点之前插入一个s所指结点时，可进行下列操作： s-next=_； p-next=s; temp=p-data； p-data=_； s-data=_；四、应用题1. 描述以下三个概念的区别：头指针，头结点，首元结点（第一个元素结点）。2. 何时选用顺序表、何时选用链表作为线性表的存储结构为宜？3. 在顺序表中插入和删除一个结点需平均移动多少个结点？具体的移动次数取决于哪两个因素？4. 为什么在单循环链表中设置尾指针比设置头指针更好？5. 双链表和单循环链表中，若仅知道指针p指向某个结点，不知道头指针，能否将结点*p从相应的链表中删除？若可以，其时间复杂度各为多少？6. 下列算法的功能是什么？LinkedList test1(LinkedList L)/L是无头结点的单链表 ListNode *q,*p;if(L&L-next)q=L ; L=L-next; p=L;while(p-next) p=p-next;p-next=q; q-next=NULL;return L;7. 如果有n个线性表同时共存，并且在处理过程中各表的长度会发生动态变化，线性表的总长度也会自动地改变。在此情况下，应选择哪一种存储结构。为什么？8. 若线性表的总数基本稳定，且很少进行插入删除操作，但要求以最快的方式存取线性表的元素，应该用哪种存储结构。为什么？9. 设有多项式a(x)=9+8x+9x4+5x10b(x)=-2x+22x7-5x10（1） 用单链表给出a(x)、b(x)的存储表示；（2） 设c (x)=a(x)+b(x)，求得c(x)并用单链表给出其存储表示。第3章 栈和队列一、选择题1. 设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出栈的顺序是s2,s3,s4,s6,s5,s1，则栈的容量至少应该是（ b ）A、2 B、 3 C、 5 D、 6 2. 若一个栈的输入序列是a,b,c，则通过入、出栈操作可能得到a,b,c的不同排列个数为（ b ）A、 4 B、 5 C、 6 D、 7 3. 设有一顺序栈已经含有3个元素，如图3.1所示元素a4正等待进栈。下列不可能出现的出栈序列是（ a ）0 maxsize-1A、a3,a1,a4,a2 B、 a3,a2,a4,a1 C、 a3,a4,a2,a1 D、 a4,a3,a2,a1 a1a2Topa3 图3.14. 链栈和顺序栈相比，有一个比较明显的优势是（ a ）A、通常不会出现栈满的情况 B、 通常不会出现栈空的情况 C、 插入操作更容易实现 D、 删除操作更加容易实现5. 若一个栈的输入序列是1,2,3,4,n，输出序列的第一个元素是n，则第i个输出元素是（ c ）A、不确定 B、 n-i C、 n-i+1 D、n-i-16. 以下说法正确的是( a )A、因链栈本身没有容量限制,故在用户内存空间的范围内不会出现栈满情况B、因顺序栈本身没有容量限制,故在用户内存空间的范围内不会出现栈满情况C、对于链栈而言,在栈满状态下,如果此时再作进栈运算，则会发生“上溢”D、对于顺序栈而言在栈满状态下如果此时再作进栈运算，则会发生“下溢”。7. 顺序队列的入队操作应为（ a ）A、 sq.rear=sq.rear+1; sq.datasq.rear=x;B 、sq.datasq.rear=x; sq.rear=sq.rear+1;C 、sq.rear=(sq.rear+1)% maxsize; sq.datasq.rear=x;D 、sq.datasqrear=x; sq.rear=(sq.rear+1)% maxsize;8. 循环队列的入队操作应为（ c ）A 、sq.rear=sq.rear+1; sq.datasq.rear=xB 、sq.datasq.rear=x;sq.rear=sq.rear+1;C 、sq.rear=(sq.rear+1)% maxsiae; sq.datasq.rear=x;D 、sq.datasq.rear=x; sq.rear=(sq.rear+1)% maxsize;9. 顺序队列的出队操作为（ b ）A 、sq.front=(sq.front+1)% maxsize； B 、sq.front=sq.front+1；C 、sq.rear=(sq.rear+1)% maxsize；D 、sq.rear=sq.rear+1；10. 循环队列的出队操作为( a )A 、sq.front=(sq.front+1)% maxsize；B 、sq.front=sq.front+1；C 、sq.rear=(sq.rear+1)% maxsize；D 、sq.rear=sq.rear+1；11. 循环队列的队满条件为（ c ）A、 (sq.rear+1) % maxsize = =(sq.front+1) % maxsize;B 、(sq.rear+1) % maxsize = =sq.front+1C 、(sq.rear+1) % maxsize = =sq.frontD 、sq.rear = =sq.front12. 循环队列的队空条件为（ d ）A 、(sq.rear+1) % maxsize = =(sq.front+1) % maxsize；B 、(sq.rear+1) % maxsize = =sq.front+1；C 、(sq.rear+1) % maxsize = =sq.front；D 、sq.rear = = sq.front；13. 如果以链表作为栈的存储结构,则退栈操作时（ c ）A、必须判别栈是否满 B、判别栈元素的类型C、必须判别栈是否空 D、 对栈不做任何判别14. 向一个栈顶指针为Top的链栈中插入一个s所指结点时，其操作步骤为（ c ）A、Top-next=s; B、 s-next=Top-next;Top-next=s;C、s-next=Top;Top=s; D、 s-next=Top;Top=Top-next;15. 从栈顶指针为Top的链栈中删除一个结点，并将被删节点的值保存到x中，其操作步骤为（ a ）A、x=Top-data;Top=Top-next; B、Top=Top-next;x=Top-data;C、x=Top;Top=Top-next; D、x=Top-data;16. 在一个链队中，若f,r分别为队首、队尾指针，则插入s所指结点的操作为（ b ）A、f-next=s;f=s; B、r-next=s;r=s;C、s-next=r;r=s; D 、s-next=f;f=s;17. 一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是（ c ） A 、e d c b a B、d e c b a C、d c e a b D、a b c d e18. 一个队列的入队序列是1，2，3，4，则队列的可能的输出系列是（ b ） A、 4，3，2，1 B、 1，2，3，4 C、1，4，3，2 D、 3，2，4，119. 设计一个判别表达式中左、右括号是否配对出现的算法，采用（ b ）数据结构最佳。 A、线性表的顺序存储结构 B、栈C 、队列 D、 线性表的链式存储结构 20. 若以1234作为双端队列的输入序列，则既不能由输入受限双端队列得到，也不能由输出受限双端队列得到的输出序列是（ c ）A、1234 B、4132 C、4231 D、4213二、 判断题1. 在顺序栈栈满情况下，不能做进栈运算，否则会产生“上溢”。a2. 链栈与顺序栈相比的一个优点是链栈插入和删除操作更加方便。b3. 若一个栈的输入序列为1，2，3，n，其输出序列的第一个元素为n，则其输出序列的每个元素ai一定满足ai=i+1(i=1,2, ,n)。b4. 在链队列中，即使不设置尾指针也能进行入队操作。a5. 在对链队列（带头指针）做出队操作时，不会改变front指针的值。a6. 循环队列中元素个数为rear-front。b7. 一个栈的输入序列是1,2,3,4，则在栈的输出序列中可以得到4,3,1,2。b8. 一个栈的输入序列是1,2,3,4，则在栈的输出序列中可以得到1,2,3,4。a9. 若以链表作为栈的存储结构，则进栈需要判断栈是否满。b10. 若以链表作为栈的存储结构，则出栈需要判断栈是否空。a三、 填空题1. 向一个栈顶指针为Top的链栈中插入一个s所指的结点时，其进行的操作是_ s-next=Top; Top=s _。2. 从栈顶指针为Top的链栈中删除一个结点，并将结点保存在x中，进行的操作是_ x=Top-data; _。在具有n个单元的循环队列中，队满时共有_ n-1_个元素。3. 假设以S和X分别表示进栈和退栈操作，则对输入序列a,b,c,d,e进行一系列栈操作SSXSXSSXXX之后，得到的输出序列为 b c e d a 。4. 设有数组A0.m作为循环队列的存储空间，front为队头指针，rear为队尾指针，则元素x执行入队操作的语句是 if(rear+1)%(m+1)!=front) rear=(rear+1) % (m+1); Arear=x; 。5. 在一个链队列中，如f,r分别为队首，队尾指针，则插入s所指结点的操作是_ r-next=s; r=s;_。6. 栈的逻辑特点是 后进先出 ，队列的逻辑特点是_先进先出_，二者共同特点是_操作受限_。a) _栈_可以作为实现递归函数调用的一种数据结构。b) 在队列中，新插入的结点只能添加到 队尾 。datanext7. 链队在一定范围内不会出现 队满 的情况。当lq.front= =lq.rear时，队中无元素，此时 队空 。8. 设一个链栈的栈顶指针为ls，栈中结点的格式为 ，栈空的条件是_；如果栈不为空，则退栈操作为p=ls; ;free(p)。9. 对带有头结点的链队列lq,判定队列中只有一个数据元素的条件是_。10. 设有一个空栈，现在输入序列为1，2，3，4，5，经过push，push，pop，push，pop，push，后栈顶指针所指元素是_4_。11. 设用一维数组A1.n来表示一个栈，令An为栈底。用整型变量t来指示当前栈顶的位置，At为栈顶元素。往栈中压入一个新元素时，变量t的值_减1_，从栈中弹出一个元素时，变量t的值_加1_。设空栈时，有输入序列a,b,c经过push，pop，push，push，pop操作后，从栈中弹出的元素是_c_。四、应用题1. 试证明：若借助栈由输入序列1，2，3， ，n得到输出序列p1，p2， ，pn(它是输入序列的一个排列)，则在输出序列中不可能出现这样的情形：存在着ijk, 使pipj1