搜索
第2章线性表一选择题1．下述哪一条是顺序存储结构的优点？（A）A．存储密度大B．插入运算方便C．删除运算方便D．可方便地用于各种逻辑结构的存储表示2．下面关于线性表的叙述中，错误的是哪一个？（B）A．线性表采用顺序存储，必须占用一片连续的存储单元。B．线性表采用顺序存储，便于进行插入和删除操作。C．线性表采用链接存储，不必占用一片连续的存储单元。D．线性表采用链接存储，便于插入和删除操作。3．线性表是具有n个（C）的有限序列（n0）。A．表元素B．字符C．数据元素D．数据项E．信息项4．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（A）存储方式最节省时间。A．顺序表B．双链表C．带头结点的双循环链表D．单循环链表5．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（D）存储方式最节省运算时间。A．单链表B．仅有头指针的单循环链表C．双链表D．仅有尾指针的单循环链表6．设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用(D)最节省时间。A.单链表B.单循环链表C.带尾指针的单循环链表D.带头结点的双循环链表7．若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用（D）存储方式最节省运算时间。A．单链表B．双链表C．单循环链表D．带头结点的双循环链表23．在双向链表指针p的结点前插入一个指针q的结点操作是（C）。A.p-Llink=q;q-Rlink=p;p-Llink-Rlink=q;q-Llink=q；B.p-Llink=q;p-Llink-Rlink=q;q-Rlink=p;q-Llink=p-Llink;C.q-Rlink=p;q-Llink=p-Llink;p-Llink-Rlink=q;p-Llink=q;D.q-Llink=p-Llink;q-Rlink=q;p-Llink=q;p-Llink=q;24．在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（B）。A．p-next=s;s-next=p-next;B．s-next=p-next;p-next=s;C．p-next=s;p-next=s-next;D．p-next=s-next;p-next=s;25．对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（B）A．head==NULLB．head→next==NULLC．head→next==headD．head!=NULL26.在双向链表存储结构中，删除p所指的结点时须修改指针（A）。A．(p^.llink)^.rlink:=p^.rlink(p^.rlink)^.llink:=p^.llink;B．p^.llink:=(p^.llink)^.llink(p^.llink)^.rlink:=p;C．(p^.rlink)^.llink:=pp^.rlink:=(p^.rlink)^.rlinkD．p^.rlink:=(p^.llink)^.llinkp^.llink:=(p^.rlink)^.rlink;二、判断1.链表中的头结点仅起到标识的作用。(F)2.顺序存储结构的主要缺点是不利于插入或删除操作。(T)3．线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。(T)4．顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。(F)5.对任何数据结构链式存储结构一定优于顺序存储结构。(F)6．顺序存储方式只能用于存储线性结构。(F)三、填空1．当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用__顺序_____存储结构。2．线性表L=（a1,a2,…,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是_(n-1)/2_______。3．设单链表的结点结构为(data,next)，next为指针域，已知指针px指向单链表中data为x的结点，指针py指向data为y的新结点,若将结点y插入结点x之后，则需要执行以下语句:_py-next=px-next______；_px-next=py_____;4．在一个长度为n的顺序表中第i个元素（1=i=n）之前插入一个元素时，需向后移动__n-i+1______个元素。11.顺序存储结构是通过_物理上相邻_______表示元素之间的关系的;链式存储结构是通过___指针_____表示元素之间的关系的。第3章栈和队列一选择题1.对于栈操作数据的原则是（B）。A.先进先出B.后进先出C.后进后出D.不分顺序2.在作进栈运算时,应先判别栈是否(B①),在作退栈运算时应先判别栈是否(A②)。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为(B③)。为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的内存空间时,应将两栈的(④D)分别设在这片内存空间的两端,这样,当(C⑤)时，才产生上溢。①,②:A.空B.满C.上溢D.下溢③:A.n-1B.nC.n+1D.n/2④:A.长度B.深度C.栈顶D.栈底⑤:A.两个栈的栈顶同时到达栈空间的中心点.B.其中一个栈的栈顶到达栈空间的中心点.C.两个栈的栈顶在栈空间的某一位置相遇.D.两个栈均不空,且一个栈的栈顶到达另一个栈的栈底.3.一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1=i=n）个元素是（B）。A.不确定B.n-i+1C.iD.n-i4.若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j个输出元素是（D）。A.i-j-1B.i-jC.j-i+1D.不确定的5.若已知一个栈的入栈序列是1,2,3,…,n，其输出序列为p1,p2,p3，…，pN,若pN是n，则pi是(D)。A.iB.n-iC.n-i+1D.不确定6.有六个元素6，5，4，3，2，1的顺序进栈，问下列哪一个不是合法的出栈序列？（C）A.543612B.453126C.346521D.2341567.设栈的输入序列是1，2，3，4,则（D）不可能是其出栈序列。A.1，2，4，3，B.2，1，3，4，C.1，4，3，2，D.4，3，1，2，E.3，2，1，4，8.一个栈的输入序列为12345，则下列序列中不可能是栈的输出序列的是（B）。A.23415B.54132C.23145D.1543222.用链接方式存储的队列，在进行删除运算时（D）。A.仅修改头指针B.仅修改尾指针C.头、尾指针都要修改D.头、尾指针可能都要修改23.用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点，则在进行删除操作时(D)。A．仅修改队头指针B.仅修改队尾指针C.队头、队尾指针都要修改D.队头,队尾指针都可能要修改24.递归过程或函数调用时，处理参数及返回地址，要用一种称为（C）的数据结构。A．队列B．多维数组C．栈D.线性表25.假设以数组A[m]存放循环队列的元素,其头尾指针分别为front和rear，则当前队列中的元素个数为（A）。A．(rear-front+m)%mB．rear-front+1C．(front-rear+m)%mD．(rear-front)%m26.循环队列A[0..m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是(A)。A.(rear-front+m)%mB.rear-front+1C.rear-front-1D.rear-front27.循环队列存储在数组A[0..m]中，则入队时的操作为（D）。A.rear=rear+1B.rear=(rear+1)mod(m-1)C.rear=(rear+1)modmD.rear=(rear+1)mod(m+1)28.若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？(B)A.1和5B.2和4C.4和2D.5和129.已知输入序列为abcd经过输出受限的双向队列后能得到的输出序列有（BD）。A.dacbB.cadbC.dbcaD.bdacE.以上答案都不对30.若以1234作为双端队列的输入序列，则既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列是(C)。A.1234B.4132C.4231D.421332.栈和队列的共同点是（C）。A.都是先进先出B.都是先进后出C.只允许在端点处插入和删除元素D.没有共同点33.栈的特点是（①B）,队列的特点是（A②）,栈和队列都是（C③）。若进栈序列为1,2,3,4则（C④）不可能是一个出栈序列（不一定全部进栈后再出栈）；若进队列的序列为1,2,3,4则（F⑤）是一个出队列序列。①,②:A.先进先出B.后进先出C.进优于出D.出优于进③:A.顺序存储的线性结构B.链式存储的线性结构C.限制存取点的线性结构D.限制存取点的非线性结构④,⑤:A.3,2,1,4B.3,2,4,1C.4,2,3,1D.4,3,2,1F.1,2,3,4G.1,3,2,4三填空题1．栈是_操作受限______的线性表，其运算遵循_后进先出______的原则。2．__栈_____是限定仅在表尾进行插入或删除操作的线性表。3．一个栈的输入序列是：1，2，3则不可能的栈输出序列是__312_____。4.设有一个空栈，栈顶指针为1000H(十六进制)，现有输入序列为1，2，3，4，5，经过PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后，输出序列是___23____，而栈顶指针值是_100C______H。设栈为顺序栈，每个元素占4个字节。15.队列的特点是_先进先出______。16．队列是限制插入只能在表的一端，而删除在表的另一端进行的线性表，其特点是先进先出。第四章串一、选择题1．下面关于串的的叙述中，哪一个是不正确的？（B）A．串是字符的有限序列B．空串是由空格构成的串C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储2若串S1=‘ABCDEFG’,S2=‘9898’,S3=‘###’,S4=‘012345’,执行concat(replace(S1,substr(S1,length(S2),length(S3)),S3),substr(S4,index(S2,‘8’),length(S2)))其结果为（E）A．ABC###G0123B．ABCD###2345C．ABC###G2345D．ABC###2345E．ABC###G1234F．ABCD###1234G．ABC###012343．设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（C）A．求子串B．联接C．匹配D．求串长4．已知串S=‘aaab’,其Next数组值为（A）。A．0123B．1123C．1231D．12115．串‘ababaaababaa’的next数组为（C）。A．012345678999B．012121111212C．011234223456D．012301232234510．串的长度是指（B）A．串中所含不同字母的个数B．串中所含字符的个数C．串中所含不同字符的个数D．串中所含非空格字符的个数二、填空题1．空格串是指__有空格字符所组成的字符串__，其长度等于_空格个数_。2．组成串的数据元素只能是__字符______。3．一个字符串中__任意个连续的字符组成的子序列______称为该串的子串。6．模式串P=‘abaabcac’的next函数值序列为_01122312_______。9．串是一种特殊的线性表，其特殊性表现在__其数据元素都是字符__；串的两种最基本的存储方式是__顺序存储__、__链式存储__；两个串相等的充分必要条件是_串的长度相等且两串中对应位置的字符也相等_。1