(13电子本)数据结构-选择填空

第一章概论一、填空题计算机专业人员必须完成的两项基本任务是：数据表示和数据处理。数据在计算机存储器中的存在形式称为机内表示。3•概括地说，数据结构课程的主要内容包括：数据的逻辑结构、定义在逻辑结构上的基本运算、数据的存储结构和运算的实现。此外，该课程还要考虑各种结构和实现方法的评价和选择。由一种逻辑性_结构和一组—基本运算构成的整体是实际问题的一种数学模型，这种数学模型的建立、选择和实现是数据结构的核心问题。存储结构是逻辑结构的存储实现。数据表示任务是逐步完成的，即数据表示形式的变化过程是机外表示-〉逻辑结构->存储结构。数据处理任务也是逐步完成的，即转化过程是处理要求->基本运算和运算->算法。&从数据结构的观点看，通常所说的〃数据〃应分成三个不同的层次，即—数据、数据元素和数据项。9•根据需要，数据元素又被称为元素、结点、顶点或记录。在有些场合下，数据项又称为字段或域，它是数据的不可分割的最小标识单位。从某种意义上说，数据、数据元素和数据项实际反映了数据组织的三个层次，数据可由若干个数据元素构成，数据元素可由若干个数据项构成。根据数据元素之间关系的不同特性，通常有集合、线性结构、树形结构、图状结构四类基本逻辑结构，它们反映了四类基本的数据组织形式。根据操作的效果，可将运算分成以下两种基本类型：加工型运算，其操作改变了原逻辑结构的“值”,如结点个数、某些结点的内容等；引用型运算，其操作不改变原逻辑结构，只从中提取某些信息作为运算的结果。将以某种逻辑结构S为操作对象的运算称为“定义在S上的运算”,简称“_S上运算”。一般地，可能存在同一逻辑结构S上的两个运算A和B，A的实现需要或可以利用B，而B的实现不需要利用A。在这种情况下，称A可以“归纳”为B。存储实现的基本目标是建立数据的机内表示。—般地，一个存储结构包括存储结点、数据兀素之间关联方式的表示7.附加设施三个主要部分。通常，存储结点之间可以有顺序存储方式、链式存储方式、索引存储方式、散列存储方式四种关联方式，称为四种基本存储方式。可用任何一种存储方式所规定的存储结点之间的关联方式来间接表达给定逻辑结构S中数据元素之间的逻辑关系。由此得到的存储结构，称为给定逻辑结构S的存储实现—或—存储映象。—个运算的实现是指一个完成该运算功能的墮序。运算实现的核心是处理步骤的规定，即算法设计。21•任何算法都必须用某种语言加以描述。根据描述算法的语言的不同，可将算法分为：运行终止的程序可执行部分、伪语言算法、非形式算法三类。数据结构课程着重评论算法的时空性能，又称为“算法分析”。通常从正确性能、易读性、健壮性、高效性等几方面评价算法的（包括程序）的质量。一个算法的时空性能是指该算法的时间性能和空间性能，前者是算法包含的计算量后者是算法需要的存储量。通常采用下述办法来估算求解某类问题的各个算法在给定输入下的计算量：根据该类问题的特点合理地选择一种或几种操作作为“标准操作”;确定每个算法在给定输入下共执行了多少次—标准操作，并将此次数规定为该算法在给定输入下的计算量。通常，一个算法在不同输入下的计算量是不同的。则可用以下两种方式来确定一个算法的计算量：以算法在所有输入下的计算量的最大值作为算法的计算量，这种计算量称为算法的最坏情况时间复杂性或—最坏情况时间复杂度。以算法在所有输入下的计算量的加权平均值作为算法的计算量，这种计算量称为算法的—平均时间复杂性或平均时间复杂度。最坏情况时间复杂性和平均时间复杂性统称为时间复杂性或时间复杂度。在一般情况下，一个算法的时间复杂性是算法输入规模的函数。一个算法的输入规模或问题的规模是指—作为该算法输入的数据所含数据元素的数目，或与此数目有关的其他参数。常见时间复杂性的量级有：常数阶0(1)、对数阶0(log2n)、线性阶0(_n_)、平方阶o(_n_)、和指数阶0(2n)o通常认为，具有指数阶量级的算法是实际不可计算,而量级低于平方阶的算法是高效的。数据结构的基本任务是数据结构的—设计_和_实现_。数据结构的课程的主要内容可以概括为：数据结构的定义、数据结构的实现数据结构的评价和选择-。数据的逻辑结构与数据元素本身的内容和形式无关。从逻辑关系上讲，数据结构主要分为两大类，它们是线性结构和非线性结构。程序段“for(i=l;i〈二n;i++){k++;for(j=1;j〈二n;j++)l+=k;}”的时间复杂度T(n)=0(n2)。程序段“i=1;while(i〈二n)i=i*2;”的时间复杂度T(n)=o(lo%n)。二、单项选择题以下说法错误的是2_用数字式计算机解决问题的实质是对数据的加工处理程序设计的实质是数据处理数据的逻辑结构是数据的组织形式，基本运算规定了数据的基本操作方式运算实现是完成运算功能的算法，或这些算法的设计数据处理方式总是与数据某种相应的表示形式相联系，反之亦然根据数据元素之间关系的不同特性，以下四类基本的逻辑结构反映了四类基本的数据组织形式。以下解释错误的是(1)集合中任何两个结点之间都有逻辑关系但组织形式松散线性结构中结点按逻辑关系依次排列形成一条〃锁链〃树形结构具有分支、层次特性，其形态有点像自然界中的树图状结构中的各个结点按逻辑关系互相缠绕，任何两个结点都可以邻接3•关于逻辑结构，以下说法错误的是(2)逻辑结构与数据元素本身的形成、内容无关逻辑结构与数据元素的相对位置有关逻辑结构与所含结点个数无关一些表面上很不相同的数据可以有相同的逻辑结构逻辑结构是数据组织的某种〃本质性〃的东西根据操作的效果，可将运算分成加工型运算、引用型运算两种基本类型。对于表格处理中的五种功能以下解释错误的是(3)查找引用型运算，功能是找出满足某种条件的结点在S(线形结构)中的位置读取引用型运算功能是读出S(线形结构)中某指定位置结点的内容插入引用型运算，功能是在S(线形结构)的某指定位置上增加一个新结点删除加工型运算，功能是撤消S(线形结构)某指定位置上的结点更新加工型运算，功能是修改S(线形结构)中某指定结点的内容一般地，一个存储结构包括以下三个主要部分。以下说法错误的是(1)存储结点每个存储结点可以存放一个或一个以上的数据元素数据元素之间关联方式的表示也就是逻辑结构的机内表示附加设施，如为便于运算实现而设置的“哑结点”等等一般地，一个存储结构包括以下三个主要部分。以下说法错误的是每个存储结点只能存放一个数据元素(2)数据元素之间的关联方式可由存储结点之间的关联方式直接表达一种存储结构可以在两个级别上讨论。其一是机器级，其二是语言级语言级描述可经编译自动转换成机器级因此也可以看成是一种机内表示通常从正确性、易读性、健壮性、高效性等四个方面评价算法(包括程序)的质量。以下解释错误的是(4)正确性算法应能正确地实现预定的功能(即处理要求)易读性算法应易于阅读和理解以便于调试修改和扩充健壮性当环境发生变化时，算法能适当地做出反应或进行处理，不会产生不需要的运行结果高效性即达到所需要的时间性能对于数据结构课程的主要内容，以下解释正确的是(3)数据结构的定义，包括逻辑结构、存储结构和基本运算集数据结构的实现，包括存储实现、运算实现和基本运算集数据结构的评价和选择，包括逻辑结构的选择、基本运算集的选择和存储选择9，与数据元素本身的形式、内容、相对位置、个数无关的是数据的(3)存储结构②存储实现③逻辑结构④运算实现10顺序存储结构(3)仅适合于静态查找表的存储仅适合于动态查找表的存储既适合静态又适合动态查找表的存储既不适合静态又不适合动态查找表的存储算法的时间复杂度，都要以通过算法中执行频度最高的语句的执行次数来确定这种观点(2)正确②错误以下说法正确的是(2)所谓数据的逻辑结构指的是数据元素之间的逻辑关系。逻辑结构与数据元素本身的内容和形式无关顺序文件只适合于存放在磁带上，索引文件只能存放在磁盘上基于某种逻辑结构之上的运算，其实现是惟一的以下说法正确的是(4)①数据元素是数据的最小单位数据项是数据的基本单位数据结构是带有结构的各数据项的集合数据结构是带有结构的数据元素的集合以下说法错误的是（4）①所谓数据的逻辑结构指的是数据元素之间的逻辑关系的整体数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用需要而建立的数据结构、数据元素、数据项在计算机中的映象分别称为存储结构、结点、数据域数据项是数据的基本单位通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（2）数据元素具有同一特点不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致每个数据元素都一样数据元素所包含的数据项的个数要相等第二章线性表习题一、单项选择题TOC\o"1-5"\h\z线性表是__A。—个有限序列，可以为空B.—个有限序列，不可以为空C.一个无限序列，可以为空D.—个无限序列，不可以为空在一个长度为n的顺序表中删除第i个元素（O〈=i〈=n）时，需向前移动A个元素。n-iB.n-i+lC.n-i-1D.i线性表采用链式存储时，其地址___D。A.必须是连续的B.一定是不连续的C.部分地址必须是连续的D.连续与否均可以从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较___C个元素结点。A.n/2B.nC.（n+1）/2D.（n-1）/2在双向循环链表中，在p所指的结点之后插入s指针所指的结点，其操作是_D—。p->next=s;s->prior=p;p->next->prior=s;s->next=p->next;s->prior=p;s->next=p->next;p->next=s;p->next->prior=s;p->next=s;p->next->prior=s;s->prior=p;s->next=p->next;s->prior=p;s->next=p->next;p->next->prior=s;p->next=s;设单链表中指针p指向结点m,若要删除m之后的结点（若存在），则需修改指针的操作为___A。A.p->next=p->next->next;B.p=p->next;C.p=p->next->next;D.p->next=p;在一个长度为n的顺序表中向第i个元素（0〈i〈n+l）之前插入一个新元素时，需向后移动__B个元素。A．n-iB．n-i+lC．n-i-1D．i在一个单链表中，已知q结点是p结点的前趋结点，若在q和p之间插入s结点，则须执行BA．s->next=p->next;p->next=sB．q->next=s;s->next=pC．p->next=s->next;s->next=pD．p->next=s;s->next=q以下关于线性表的说法不正确的是__C。A.线性表中的数据元素可以是数字、字符、记录等不同类型。B线性表中包含的数据元素个数不是任意的。线性表中的每个结点都有且只有一个直接前趋和直接后继。存在这样的线性表：表中各结点都没有直接前趋和直接后继。线性表的顺序存储结构是一种__A的存储结构。A.随机存取B顺序存取C.索引存取D.散列存取在顺序表中，只要知道___D，就可在相同时间内求出任一结点的存储地址。A.基地址B结点大小C.向量大小D.基地址和结点大小在等概率情况下，顺序表的插入操作要移动__B结点。A.全部B一半C.三分之一D.四分之一在___C___运算中，使用顺序表比链表好。A.插入B删除C.根据序号查找D.根据元素值查找在一个具有n个结点的有序单链表中插入一个新结点并保持该表有序的时间复杂度是TOC\o"1-5"\h\z__B。A．O(1)B．O(n)C．O(n2)D．O(logn)设有一个栈，元素的进栈次序为A,B,C,D,E,下列是不可能的出栈序列C。A．A,B,C,D,EB．B,C,D,E,AC．E,A,B,C,DD．E,D,C,B,A在一个具有n个单元的顺序栈中，假定以地址低端(即0单元)作为栈底，以top作为栈顶指针，当做出栈处理时，top变化为__C。A．top不变B．top=0C．top--D．top++向一个栈顶指针为hs的链栈中插入一个s结点时，应执行__B。A．hs->next=s;B．s->next=hs;hs=s;C．s->next=hs->next;hs->next=s;D．s->next=hs;hs=hs->next;在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队满的条件为___D。A．rear％n==frontB．(front+l)％n==rearC．rear％n-1==frontD．(rear+l)％n==front在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队空的条件为___C。A．rear％n==frontB．front+l=rearC．rear==frontD．(rear+l)％n=front在一个链队列中，假定front和rear分别为队首和队尾指针，则删除一个结点的操作为___A。A．front=front->nextB．rear=rear->nextC．rear=front->nextD．front=rear->next二、填空题线性表是一种典型的线性结构。在一个长度为n的顺序表的第i个元素之前插入一个元素，需要后移n-i+1个元素。顺序表中逻辑上相邻的元素的物理位置相邻。要从一个顺序表删除一个元素时，被删除元素之后的所有元素均需一前移-一个位置,移动过程是从一前-向一后-依次移动每一个元素。在线性表的顺序存储中，元素之间的逻辑关系是通过物理存储位置决定的：在线性表的链接存储中，元素之间的逻辑关系是通过链域的指针值决定的。在双向链表中，每个结点含有两个指针域，一个指向一前趋-结点，另一个指向后继结点。当对一个线性表经常进行存取操作，而很少进行插入和删除操作时，则采用一顺序-存储结构为宜。相反，当经常进行的是插入和删除操作时,则采用链接一存储结构为宜。&顺序表中逻辑上相邻的元素，物理位置-一定相邻,单链表中逻辑上相邻的元素，物理位置一不一定相邻。线性表、栈和队列都是线性结构，可以在线性表的任何位置插入和删除元素；对于栈只能在栈顶一位置插入和删除元素：对于队列只能在队尾位置插入元素和在一队头-位置删除元素。根据线性表的链式存储结构中每个结点所含指针的个数，链表可分为单链表和双链表：而根据指针的联接方式，链表又可分为非循环链表和循环链表。在单链表中设置头结点的作用是。对于一个具有n个结点的单链表，在已知的结点p后插入一个新结点的时间复杂度为一0(1)一，在给定值为x的结点后插入一个新结点的时间复杂度为O(n)__。对于一个栈作进栈运算时，应先判别栈是否为栈满，作退栈运算时，应先判别栈是否为栈空，当栈中元素为m时，作进栈运算时发生上溢，则说明栈的可用最大容量为m。为了增加内存空间的利用率和减少发生上溢的可能性，由两个栈共享一片连续的内存空间时，应将两栈的栈底分别设在这片内存空间的两端,这样只有当两个栈的栈顶在栈空间的某一位置相遇时才产牛上溢。设有一空栈，现有输入序列1,2，3，4，5,经过push,push,pop,push,pop,push,push后，输出序列是2、3。无论对于顺序存储还是链式存储的栈和队列来说，进行插入或删除运算的时间复杂度均相同为。习题三栈和队列一单项选择题在作进栈运算时，应先判别栈是否(①)，在作退栈运算时应先判别栈是否(②)。当栈中元素为n个，作进栈运算时发生上溢，则说明该栈的最大容量为(③)。(BAB)①,②:A.空B.满C.上溢D.下溢:A.n-1B.nC.n+1D.n/2若已知一个栈的进栈序列是1,2,3,…，n，其输出序列为pl,p2,p3,...,pn,若pl=3,则p2为(A)。A可能是2B一定是2C可能是1D一定是1有六个元素6,5,4,3,2,1的顺序进栈，问下列哪一个不是合法的出栈序列？(C)543612B.453126C.346521D.234156设有一顺序栈S,元素s,s,s,s,s,s依次进栈，如果6个元素出栈的顺序是s,s,s,s,1234562346s,s,则栈的容量至少应该是(B)51A.2B.3C.5D.6若栈采用顺序存储方式存储，现两栈共享空间V[1..m],top[i]代表第i个栈(i=1,2)栈顶，栈1的底在v[1],栈2的底在V[m],则栈满的条件是(B)。A.|top[2]-top[1]|=0B.top[1]+1=top[2]C.top[1]+top[2]=mD.top[1]=top[2]执行完下列语句段后，i值为：(B)intf(intx){return((x>0)?x*f(x-1):2);}inti;i=f(f(1));A．2B.4C.8D.无限递归表达式3*2'(4+2*2-6*3)-5求值过程中当扫描到6时，对象栈和算符栈为(D),其中’为乘幂。A.3,2,4,1,1；(*(+*-B.3,2,8；(*—C.3,2,4,2,2；(*"(-D.3,2,8；(*"(-&用链接方式存储的队列，在进行删除运算时(D)。A.仅修改头指针B.仅修改尾指针C.头、尾指针都要修改D.头、尾指针可能都要修改递归过程或函数调用时，处理参数及返回地址，要用一种称为(C)的数据结构。A.队列B.多维数组C.栈D.线性表设C语言数组Data[m+1]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针,则执行出队操作的语句为(D)A.front=front+1B.front=(front+1)%mC.rear=(rear+1)%(m+1)D.front=(front+1)%(m+1)循环队列的队满条件为(C)(sq.rear+1)%maxsize==(sq.front+1)%maxsize;(sq.front+1)%maxsize==sq.rear(sq.rear+1)%maxsize==sq.frontsq.rear==sq.front栈和队列的共同点是(C)。A.都是先进先出B.都是先进后出C.只允许在端点处插入和删除元素D.没有共同点二、填空题栈是_操作受限(或限定仅在表尾进行插入和删除操作)的线性表，其运算遵循—后进先出的原则。一个栈的输入序列是：1,2,3则不可能的栈输出序列是312。用S表示入栈操作，X表示出栈操作，若元素入栈的顺序为1234，为了得到1342出栈顺序，相应的S和X的操作串为SXSSXSXX_。循环队列的引入，目的是为了克服假溢出时大量移动数据元素。队列是限制插入只能在表的一端，而删除在表的另一端进行的线性表，其特点是先进先出。已知链队列的头尾指针分别是f和r，则将值x入队的操作序列是s=(LinkedList)malloc(sizeof(LNode))；s—〉data二x;s—〉next=r—〉next；r—〉next=s；r=s；7.表达式求值是应用的一个典型例子。循环队列用数组A[0..m-1]存放其元素值，已知其头尾指针分别是front和rear，贝V当前队列的元素个数是__(rear-front+m)%m_。以下运算实现在链栈上的初始化，请在处用请适当句子予以填充。VoidInitStacl(LstackTp*ls){一ls二NULL;}'以下运算实现在链栈上的进栈，请在处用请适当句子予以填充。VoidPush(LStackTp*ls,DataTypex){LstackTp*p;p=malloc(sizeof(LstackTp));p—〉data=x;p—〉next=ls;ls=p;}以下运算实现在链栈上的退栈，请在处用请适当句子予以填充。IntPop(LstackTp*ls,DataType*x){LstackTp*p;if(ls!=NULL){p=ls;*x=;ls=ls—〉next;一free(p);return(1)；}elsereturn(0);}以下运算实现在链队上的入队列，请在处用适当句子予以填充。VoidEnQueue(QueptrTp*lq,DataTypex){LqueueTp*p;p=(LqueueTp*)malloc(sizeof(LqueueTp));p—〉data=x;p—〉next=NULL;(lq-〉rear)-〉next二_p_;.lq—〉rear二p;习题四串一、单项选择题1．下面关于串的的叙述中，哪一个是不正确的？（B）A.串是字符的有限序列B.空串是由空格构成的串C.模式匹配是串的一种重要运算D.串既可以采用顺序存储，也可以采用链式存储2．串是一种特殊的线性表，其特殊性体现在（B）。A.可以顺序存储B.数据元素是一个字符C.可以链接存储D.数据元素可以是多个字符3．串的长度是指（B）A.串中所含不同字母的个数B.串中所含字符的个数C.串中所含不同字符的个数D.串中所含非空格字符的个数设有两个串p和q,其中q是p的子串，求q在p中首次出现的位置的算法称为（C）A.求子串B.联接C.匹配D.求串长若串S=“software”，其子串的个数是（C）。A.8B.37C.36D.9二、填空题1•含零个字符的串称为空-串。任何串中所含字符-的个数称为该串的长度。空格串是指_由空格字符（ASCII值32）所组成的字符串,其长度等干空格个数。当且仅当两个串的长度____相等并且各个对应位置上的字符都相等时,这两个串相等。一个串中任意个连续字符组成的序列称为该串的一子____串，该串称为它所有子串的一主一串。TOC\o"1-5"\h\zINDEX（'DATASTRUCTURE','STR'）=_5。模式串P='abaabcac'的next函数值序列为_01122312,。下列程序判断字符串s是否对称，对称则返回1,否则返回0；如f（〃abba〃）返回1,f（〃abab〃）返回0；intf（）{inti=0,j=0；while（s[j]）（2）j++;for（j—;i<j&&s[i]==s[j];i++,j—）;return（（3）i〉=j）}下列算法实现求采用顺序结构存储的串s和串t的一个最长公共子串。voidmaxcomstr(orderstring*s,*t;intindex,length){inti,j,k,length1,con;index=0;length=0;i=1;while(i<=s.len){j=1;while(j<=t.len){if(s[i]==t[j]){k=1;length1=1;con=1;while(con)if(l)i+k〈二s.len&&j+k〈二t.len&&s「i+k]二=t[j+k]{length1=length1+1;k=k+1;}else(2)con=0:if(length1>length){index=i;length=length1;}(3)i+=k:}else(4)i++:}(5)i++}}习题五数组和广义表一、单项选择题1．常对数组进行的两种基本操作是(C)A.建立与删除B.索引与修改C.查找与修改D.查找与索引对于C语言的二维数组DataTypeA[m][n],每个数据元素占K个存储单元，二维数组中任意元素a[i,j]的存储位置可由(C)式确定.Loc[i,j]=A[m,n]+[(n+1)*i+j]*kLoc[i,j]=loc[0,0]+[(m+n)*i+j]*kLoc[i,j]=loc[0,0]+[(n+1)*i+j]*kLoc[i,j]=[(n+1)*i+j]*k稀疏矩阵的压缩存储方法是只存储(A)A.非零元素B.三元祖(i,j,aij)C.aijD.i,j数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址是(A)。A.1175B.1180C.1205D.1210A[N，N]是对称矩阵，将下面三角(包括对角线)以行序存储到一维数组T[N(N+1)/2]中，则对任一上三角元素a[i][j]对应T[k]的下标k是(B)。A.i(i-1)/2+jB.j(j-1)/2+iC.i(j-i)/2+1D.j(i-1)/2+1用数组r存储静态链表，结点的next域指向后继，工作指针j指向链中结点，使j沿链移动的操作为(A)。A.j=r[j].nextB.j=j+1C.j=j->nextD.j=r[j]->next对稀疏矩阵进行压缩存储目的是(C)。A.便于进行矩阵运算B.便于输入和输出C.节省存储空间D.降低运算的时间复杂度&已知广义表LS=((a,b,c),(d,e,f)),运用head和tail函数取出LS中原子e的运算是(C)。A.head(tail(LS))B.tail(head(LS))C.head(tail(head(tail(LS)))D.head(tail(tail(head(LS))))广义表((a,b,c,d))的表头是()，表尾是(C)。A.aB.()C.(a,b,c,d)D.(b,c,d)设广义表L=((a,b,c)),则L的长度和深度分别为(C)。

A.1A.1和1B.1和3下面说法不正确的是(A)。A.广义表的表头总是一个广义表C.广义表难以用顺序存储结构二、填空题C.1和2D.2和3B.广义表的表尾总是一个广义表D.广义表可以是一个多层次的结构通常采用_顺序-存储结构来存放数组。对二维数组可有两种存储方法：一种是以列序为主序的存储方式，另一种是以为主序的存储方式。用一维数组B与列优先存放带状矩阵A中的非零元素A[i,j](1WiWn,i-2WjWi+2),B中的第8个元素是A中的第第1行，第第3列的元素。设n行n列的下三角矩阵A已压缩到一维数组B[1..n*(n+1)/2]中，若按行为主序存储，则A[i,j]对应的B中存储位置为i(i-1)/2+j(1〈=i,j〈=n)。所谓稀疏矩阵指的是非零元很少(t〈〈m*n)且分布没有规律。广义表简称表，是由零个或多个原子或子表组成的