PAGEPAGE19单元
练习
飞向蓝天的恐龙练习非连续性文本练习把字句和被字句的转换练习呼风唤雨的世纪练习呼风唤雨的世纪课后练习
1一．判断
题
快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题
（下列各题，正确的请在前面的括号内打√；错误的打╳）（√）（1）数据的逻辑结构与数据元素本身的内容和形式无关。（√）（2）一个数据结构是由一个逻辑结构和这个逻辑结构上的一个基本运算集构成的整体。（ㄨ）（3）数据元素是数据的最小单位。（ㄨ）（4）数据的逻辑结构和数据的存储结构是相同的。（ㄨ）（5）程序和算法原则上没有区别，所以在讨论数据结构时可以通用。（√）（6）从逻辑关系上讲，数据结构主要分为线性结构和非线性结构两类。（√）（7）数据的存储结构是数据的逻辑结构的存储映像。（√）（8）数据的物理结构是指数据在计算机内实际的存储形式。（ㄨ）（9）数据的逻辑结构是依赖于计算机的。（√）（10）算法是对解题方法和步骤的描述。二．填空题数据有逻辑结构和存储结构两种结构。数据逻辑结构除了集合以外，还包括：线性结构、树形结构和图形结构。数据结构按逻辑结构可分为两大类，它们是线性结构和非线性结构。树形结构和图形结构合称为非线性结构。在树形结构中，除了树根结点以外，其余每个结点只有1个前趋结点。在图形结构中，每个结点的前趋结点数和后续结点数可以任意多个。数据的存储结构又叫物理结构。数据的存储结构形式包括：顺序存储、链式存储、索引存储和散列存储。线性结构中的元素之间存在一对一的关系。树形结构结构中的元素之间存在一对多的关系，图形结构的元素之间存在多对多的关系。数据结构主要研究数据的逻辑结构、存储结构和算法（或运算）三个方面的内容。数据结构被定义为(D，R)，其中D是数据的有限集合，R是D上的关系的有限集合。算法是一个有穷指令的集合。算法效率的度量可以分为事先估算法和事后统计法。一个算法的时间复杂性是算法输入规模的函数。算法的空间复杂度是指该算法所耗费的存储空间，它是该算法求解问题规模n的函数。若一个算法中的语句频度之和为T（n）=6n+3nlog2n，则算法的时间复杂度为O（nlog2n）。若一个算法中的语句频度之和为T（n）=3n+nlog2n+n2，则算法的时间复杂度为O（n2）。（20）数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象，以及它们之间的关系和运算的学科。三．选择题（1）数据结构通常是研究数据的（A）及它们之间的相互联系。A.存储结构和逻辑结构B.存储和抽象C.联系和抽象D.联系与逻辑（2）在逻辑上可以把数据结构分成：（C）。A.动态结构和静态结构B.紧凑结构和非紧凑结构C.线性结构和非线性结构D.内部结构和外部结构（3）数据在计算机存储器内
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
示时，物理地址和逻辑地址相同并且是连续的，称之为（C）。A.存储结构B.逻辑结构C.顺序存储结构D.链式存储结构（4）非线性结构中的每个结点（D）。无直接前趋结点无直接后继结点只有一个直接前趋结点和一个直接后继结点可能有多个直接前趋结点和多个直接后继结点（5）链式存储的存储结构所占存储空间（A）。A．分两部分，一部分存放结点的值，另一部分存放表示结点间关系的指针B．只有一部分，存放结点的值C．只有一部分，存储表示结点间关系的指针D．分两部分，一部分存放结点的值，另一部分存放结点所占单元素（6）算法的计算量大小称为算法的（C）。A.现实性B.难度C.时间复杂性D.效率（7）数据的基本单位是（B）。A.数据结构B.数据元素C.数据项D.文件（8）每个结点只含有一个数据元素，所有存储结点相继存放在一个连续的存储区里，这种存储结构称为（A）结构。A.顺序存储B.链式存储C.索引存储D.散列存储（9）每一个存储结点不仅含有一个数据元素，还包含一组指针，该存储方式是（B）存储方式。A.顺序B.链式C.索引D.散列（10）以下任何两个结点之间都没有逻辑关系的是（D）。A.图形结构B.线性结构C.树形结构D.集合（11）在数据结构中，与所使用的计算机无关的是（C）。A.物理结构B.存储结构C.逻辑结构D.逻辑和存储结构（12）下列四种基本逻辑结构中，数据元素之间关系最弱的是（A）。A.集合B.线性结构C.树形结构D.图形结构（13）与数据元素本身的形式、内容、相对位置、个数无关的是数据的（A）。A.逻辑结构B.存储结构C.逻辑实现D.存储实现（14）每一个存储结点只含有一个数据元素，存储结点存放在连续的存储空间，另外有一组指明结点存储位置的表，该存储方式是（C）存储方式。A.顺序B.链式C.索引D.散列（15）算法能正确的实现预定功能的特性称为算法的（A）。A.正确性B.易读性C.健壮性D.高效性（16）算法在发生非法操作时可以作出处理的特性称为算法的（C）。A.正确性B.易读性C.健壮性D.高效性（17）下列时间复杂度中最坏的是（D）。A.O（1）B.O（n）C.O（log2n）D.O（n2）（18）下列算法的时间复杂度是（D）。for(i=0;i
,,,,}（尖括号表示结点之间关系是有向的）解：baedfc属于线性结构。（3）F=（D,R），其中：D={50,25,64,57,82,36,75,55}，R={r}R={<50,25>,<50,64>,<25,36>,<64,57>,<64,82>,<57,55>,<57,75>}2550755736826455解：属于树结构（4）C=（D,R），其中：D={1,2,3,4,5,6}，R={r}R={(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)}（园括号表示结点之间关系是有向的）解：126345属于图结构（5）E=（D,R），其中：D={a,b,c,d,e,f,g,h}，R={r}R={,,,,,,}解：bdfeahgc属于树结构。单元练习2一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳）（×）（1）线性表的链式存储结构优于顺序存储。（×）（2）链表的每个结点都恰好包含一个指针域。（√）（3）在线性表的链式存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。（×）（4）顺序存储方式的优点是存储密度大，插入、删除效率高。（×）（5）线性链表的删除算法简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。（×）（6）顺序表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。（√）（7）线性表链式存储的特点是可以用一组任意的存储单元存储表中的数据元素。（√）（8）线性表采用顺序存储，必须占用一片连续的存储单元。（×）（9）顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。（ㄨ）（10）插入和删除操作是数据结构中最基本的两种操作，所以这两种操作在数组中也经常使用。二．填空题顺序表中逻辑上相邻的元素在物理位置上必须相连。线性表中结点的集合是有限的，结点间的关系是一对一关系。顺序表相对于链表的优点是：节省存储和随机存取。链表相对于顺序表的优点是：插入、删除方便。（5）采用顺序存储结构的线性表叫顺序表。（6）顺序表中访问任意一个结点的时间复杂度均为O(1)。（7）链表相对于顺序表的优点是插入、删除方便；缺点是存储密度小。（8）在双链表中要删除已知结点*P，其时间复杂度为O(1)。（9）在单链表中要在已知结点*P之前插入一个新结点，需找到*P的直接前趋结点的地址，其查找的时间复杂度为O(n)。单链表中需知道头指针才能遍历整个链表。性表中第一个结点没有直接前趋，称为开始结点。在一个长度为n的顺序表中删除第i个元素，要移动n-i个元素。在一个长度为n的顺序表中，如果要在第i个元素前插入一个元素，要后移n-i+1个元素。在无头结点的单链表中，第一个结点的地址存放在头指针中，而其它结点的存储地址存放在前趋结点的指针域中。当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快速度存取线性表中的元素时，应采用顺序存储结构。在线性表的链式存储中，元素之间的逻辑关系是通过指针决定的。在双向链表中，每个结点都有两个指针域，它们一个指向其前趋结点，另一个指向其后继结点。对一个需要经常进行插入和删除操作的线性表，采用链式存储结构为宜。双链表中，设p是指向其中待删除的结点，则需要执行的操作为：p->prior->next=p->next。在如图所示的链表中，若在指针P所在的结点之后插入数据域值为a和b的两个结点，则可用下列两个语句：S->next->next=P->next;和P->next=S;来实现该操作。PΛabS三．选择题（1）在具有n个结点的单链表中，实现（A）的操作，其算法的时间复杂度都是O（n）。A．遍历链表或求链表的第i个结点B．在地址为P的结点之后插入一个结点C．删除开始结点D．删除地址为P的结点的后继结点（2）设a、b、c为三个结点，p、10、20分别代表它们的地址，则如下的存储结构称为（B）。a10c^b20P循环链表B．单链表C．双向循环链表D．双向链表（3）单链表的存储密度（C）。A．大于1B．等于1C．小于1D．不能确定（4）已知一个顺序存储的线性表，设每个结点占m个存储单元，若第一个结点的地址为B，则第i个结点的地址为（A）。A．B+(i-1)*mB．B+i*mC．B-i*mD．B+(i+1)*m（5）在有n个结点的顺序表上做插入、删除结点运算的时间复杂度为（B）。A．O（1）B．O（n）C．O（n2）D．O（log2n）（6）设Llink、Rlink分别为循环双链表结点的左指针和右指针，则指针P所指的元素是双循环链表L的尾元素的条件是（D）。A．P==LB．P->Llink==LC．P==NULLD．P->Rlink==L（7）两个指针P和Q，分别指向单链表的两个元素，P所指元素是Q所指元素前驱的条件是（B）。A．P->next==Q->nextB．P->next==QC．Q->next==PD．P==Q（8）用链表存储的线性表，其优点是（C）。A．便于随机存取B．花费的存储空间比顺序表少C．便于插入和删除D．数据元素的物理顺序与逻辑顺序相同（9）在单链表中，增加头结点的目的是（C）。A．使单链表至少有一个结点B．标志表中首结点的位置C．方便运算的实现D．说明该单链表是线性表的链式存储结构（10）下面关于线性表的叙述中，错误的是（D）关系。A．顺序表必须占一片地址连续的存储单元B．顺序表可以随机存取任一元素C．链表不必占用一片地址连续的存储单元D．链表可以随机存取任一元素（11）L是线性表，已知LengthList（L）的值是5，经DelList（L，2）运算后，LengthList（L）的值是（C）。A．2B．3C．4D．5（12）单链表的示意图如下：LABCDΛQRP指向链表Q结点的前趋的指针是（B）。A．LB．PC．QD．R（13）设p为指向单循环链表上某结点的指针，则*p的直接前驱（C）。A．找不到B．查找时间复杂度为O（1）C．查找时间复杂度为O（n）D．查找结点的次数约为n（14）等概率情况下，在有n个结点的顺序表上做插入结点运算，需平均移动结点的数目为（C）。A．nB．(n-1)/2C．n/2D．(n+1)/2（15）在下列链表中不能从当前结点出发访问到其余各结点的是（C）。A．双向链表B．单循环链表C．单链表D．双向循环链表（16）在顺序表中，只要知道（D），就可以求出任一结点的存储地址。A．基地址B．结点大小C．向量大小D．基地址和结点大小（17）在双链表中做插入运算的时间复杂度为（A）。A．O（1）B．O（n）C．O（n2）D．O（log2n）（18）链表不具备的特点是（A）。A．随机访问B．不必事先估计存储空间C．插入删除时不需移动元素D．所需空间与线性表成正比（19）以下关于线性表的论述，不正确的为（C）。A．线性表中的元素可以是数字、字符、记录等不同类型B．线性顺序表中包含的元素个数不是任意的C．线性表中的每个结点都有且仅有一个直接前趋和一个直接后继D．存在这样的线性表，即表中没有任何结点（20）在（B）的运算中，使用顺序表比链表好。A．插入B．根据序号查找C．删除D．根据元素查找ListNode*Demo1(LinkListL,ListNode*p){//L是有头结点的单链表ListNode*q=L->next;While(q&&q->next!=p)q=q->next;if(q)returnq;elseError(“*pnotinL”);}四．分析下述算法的功能（1）voidDemo2(ListNode*p,ListNode*q){//p,*q是链表中的两个结点DataTypetemp;temp=p->data;p->data=q->data;q->data=temp;}（2）解：（1）返回结点*p的直接前趋结点地址。（2）交换结点*p和结点*q（p和q的值不变）。五．程序填空（1）已知线性表中的元素是无序的，并以带表头结点的单链表作存储。试写一算法，删除表中所有大于min，小于max的元素，试完成下列程序填空。Voiddelete(lklisthead;datatypemin,max){q=head->next;while(p!=NULL){if((p->data<=min)||(p->data>=max){q=p;p=p->next;}else{q->next=p->next;delete(p);p=q->next;}}}（2）在带头结点head的单链表的结点a之后插入新元素x，试完成下列程序填空。structnode{elemtypedata;node*next;};voidlkinsert(node*head,elemtypex){node*s,*p;s=newnode;s->data=x;p=head->next;while(p!=NULL)&&(p->data!=a)____p=p->next;if(p==NULL)cout<<"不存在结点a!";else{_____s->next=p->next______;___p->next=s__________;}}六．算法设计题（1）写一个对单循环链表进行遍历（打印每个结点的值）的算法，已知链表中任意结点的地址为P。解：voidShow(ListNode*P){ListNode*t=P;do{printf("%c",t->data);t=t->rear;}while(t!=P);}对给定的带头结点的单链表L，编写一个删除L中值为x的结点的直接前趋结点的算法。解：voiddelete(ListNode*L){ListNode*p=L,*q;if(L->next->data==X){printf(“值为x的结点是第一个结点，没有直接前趋结点可以删除”);return;}For(p->next->data!=X;q=p;p=p->next);//删除指针p所指向的结点q->next=p->next;deletep;}已知一个单向链表，编写一个函数从单链表中删除自第i个结点起的k个结点。解：voidDel(node*head,inti,intk){node*p,*q;intj;if(i==1)for(j=1;j<=k;j++)//删除前k个元素{p=head;//p指向要删除的结点head=head->next;deletep;}else{p=head;for(j=1;j<=i-2;j++)p=p->next;//p指向要删除的结点的前一个结点for(j=1;j<=k;j++){q=p->next;//q指向要删除的结点p->next=q->next;deleteq;}}}有一个单向链表（不同结点的数据域值可能相同），其头指针为head，编写一个函数计算值域为x的结点个数。解：//本题是遍历单链表的每个结点，每遇到一个结点，结点个数加1，结点个数存储在变量n中。实现本题功能的函数如下：intcounter(head)node*head；{node*p;intn=0;p=head；while(p!=NULL){if(p->data==x)n++；p=p->next;}return(n);}（5）有两个循环单向链表，链头指针分别为head1和head2，编写一个函数将链表head1链接到链表head2，链接后的链表仍是循环链表。解：//本题的算法思想是：先找到两链表的尾指针，将第一个链表的尾指针与第二个链表的头结点链接起来，使之成为循环的。函数如下：node*link(node*head1,*head2){node*p,*q;p=head1;while(p->next!=head1)p=p->next;q=head2;while(q->next!=head2)q=q->next;p->next=head2;q->next=head1;return(head1);}单元练习3一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳）（√）（1）栈是运算受限制的线性表。（√）（2）在栈空的情况下，不能作出栈操作，否则产生下溢出。（ㄨ）（3）栈一定是顺序存储的线性结构。（√）（4）栈的特点是“后进先出”。（ㄨ）（5）空栈就是所有元素都为0的栈。（ㄨ）（6）在C或C++语言中设顺序栈的长度为MAXLEN，则top=MAXLEN时表示队满。（√）（7）链栈与顺序栈相比，其特点之一是通常不会出现栈满的情况。（ㄨ）（8）一个栈的输入序列为：A，B，C，D，可以得到输出序列：C，A，B，D。（ㄨ）（9）递归定义就是循环定义。（√）（10）将十进制数转换为二进制数是栈的典型应用之一。二．填空题（1）在栈结构中，允许插入、删除的一端称为栈顶。（2）在顺序栈中，当栈顶指针top=-1时，表示栈空。（3）在有n个元素的栈中，进栈操作的时间复杂度为O（1）。（4）在栈中，出栈操作的时间复杂度为：O(1)。（5）已知表达式，求它的后缀表达式是栈的典型应用。（6）在一个链栈中，若栈顶指针等于NULL，则表示栈空。（7）向一个栈顶指针为top的链栈插入一个新结点*p时，应执行p->next=top；和top=p；操作。（8）顺序栈S存储在数组S->data[0..MAXLEN-1]中，进栈操作时要执行的语句有：S->top++。（或=S->top+1）（9）链栈LS，指向栈顶元素的指针是LS->next。（10）从一个栈删除元素时，首先取出栈顶元素，然后再移动栈顶指针。（11）由于链栈的操作只在链表的头部进行，所以没有必要设置头结点。（12）已知顺序栈S，在对S进行进栈操作之前首先要判断栈是否满。（13）已知顺序栈S，在对S进行出栈操作之前首先要判断栈是否空。（14）若内存空间充足，链栈可以不定义栈满运算。（15）链栈LS是空的条件是LS->next=NULL。（16）链栈LS的栈顶元素是链表的首元素。（17）同一栈的各元素的类型相同。（18）若进栈的次序是A、B、C、D、E，执行三次出栈操作以后，栈顶元素为B。（19）A+B/C-D*E的后缀表达式是：ABC/+DE*-。（20）四个元素按A、B、C、D顺序进S栈，执行两次Pop（S，x）运算后，x的值是C。三．选择题（1）插入和删除只能在一端进行的线性表，称为(C)。A．队列B．循环队列C．栈D．循环栈（2）设有编号为1，2，3，4的四辆列车，顺序进入一个栈结构的站台，下列不可能的出站顺序为(D)A．1234B．1243C．1324D．1423（3）如果以链表作为栈的存储结构，则出栈操作时（B）A．必须判别栈是否满B．必须判别栈是否空C．必须判别栈元素类型D．队栈可不做任何判别（4）元素A,B,C,D依次进栈以后，栈顶元素是（D）A．AB．BC．CD．D（5）顺序栈存储空间的实现使用（B）存储栈元素。A．链表B．数组C．循环链表D．变量（6）在C或C++语言中，一个顺序栈一旦被声明，其占用空间的大小（A）。A．已固定B．不固定C．可以改变D．动态变化（7）带头结点的链栈LS的示意图如下，栈顶元素是（A）LSHABCDΛA．AB．BC．CD．D（8）链栈与顺序栈相比，有一个比较明显的优点是（B）。A．插入操作更加方便B．通常不会出现栈满的情况。C．不会出现栈空的情况D．删除操作根加方便（9）从一个栈顶指针为top的链栈中删除一个结点时，用x保存被删除的结点，应执行下列(D)命令。A．x=top;top=top->next;B．top=top->next;x=top->data;C．x=top->data;D．x=top->data;top=top->next;（10）在一个栈顶指针为HS的链栈中，将一个S指针所指的结点入栈，应执行下列(B)命令。A．HS->next=S;B．S->next=HS->next;HS->next=S;C．S->next=HS->next;HS=S;D．S->next=HS;HS=HS->next;（11）四个元素按A、B、C、D顺序进S栈，执行两次Pop（S，x）运算后，栈顶元素的值是（B）。A．AB．BC．CD．D（12）元素A,B,C,D依次进栈以后，栈底元素是（A）。A．AB．BC．CD．D（13）经过下列栈的运算后，再执行ReadTop(s)的值是（A）。InitStack(s)（初始化栈）;Push(s,a);Push(s,b);Pop(s)A．aB．bC．1D．0（14）经过下列栈的运算后，x的值是（B）。InitStack(s)（初始化栈）;Push(s,a);Push(s,b);ReadTop(s);Pop(s,x);A．aB．bC．1D．0（15）经过下列栈的运算后，x的值是（B）。InitStack(s)（初始化栈）;Push(s,a);Pop(s,x);Push(s,b);Pop(s,x);A．aB．bC．1D．0（16）经过下列栈的运算后，SEmpty(s)的值是（C）。InitStack(s)（初始化栈）;Push(s,a);Push(s,b);Pop(s,x);Pop(s,x);A．aB．bC．1D．0（17）向顺序栈中压入元素时，（B）。先存入元素，后移动栈顶指针B．先移动栈顶指针，后存入元素C．谁先谁后无关紧要D．同时进行（18）初始化一个空间大小为5的顺序栈S后，S->top的值是（B）。A．0B．-1C．不再改变D．动态变化（19）一个栈的入栈次序ABCDE，则栈的不可能的输出序列是(C)。A．EDCBAB．DECBAC．DCEABD．ABCDE（20）设有一个顺序栈S，元素A,B,C,D,E,F,依次进栈，如果六个元素出栈的顺序是B，D，C，F，E，A，则栈的容量至少应是(A)。A．3B．4C．5D．6四．应用题（1）设有一个栈，元素进栈的次序为：A，B，C，D，E，用I表示进栈操作，O表示出栈操作，写出下列出栈的操作序列。①C，B，A，D，E②A，C，B，E，D解：①IIIOOOIOIO②IOIIOOIIOO求后缀表达式A^B^C/D解：AB^C^D/-A+B*C+D/E解：0A–BC*+DE/+A*(B+C)*D-E解：ABC+*D*E-(A+B)*C-E/(F+G/H)-D解：AB+C*EFGH/+/-D-8/(5+2)-6解：852+/6-六．算法设计题（1）设用一维数组stack[n]表示一个堆栈，若堆栈中每个元素需占用M个数组单元（M>1）。①试写出其入栈操作的算法。②试写出其出栈操作的算法。解：//用一整型变量top表示栈顶指针，top为0时表示栈为空。栈中元素从S[1]开始存放元素。//①入栈算法：voidpush(charx){if((top+M)>MAXLEN-1)printf(“堆栈溢出！”);else{if(top==0){top++;S[top]=x;}else{top=top+M;S[top]=x;}}}//②出栈算法：voidpop(charx){if(top==0)printf(“堆栈为空栈！”);else{if(top==1){x=S[top];top––;}else{x=S[top];top=top–M;}}}（2）设计一个算法，要求判别一个算术表达式中的圆括号配对是否正确。解：//设表达式在字符数组a[]中，使用一堆栈S来帮助判断。intcorrect(chara[]){stacks;InitStack(s);//调用初始化栈函数for(i=0;i#includetypedefstructstacknode//定义栈的存储结构{intdata;structstacknode*next;}stacknode;typedefstruct{stacknode*top;//定义栈顶的指针}linkstack;voidConversion(intn)//栈的应用：十——十六进制转换{linkstacks;intx;s.top=NULL;//置栈空do{x=n%16;//取余数n=n/16;//取新的商stacknode*p=newstacknode;//申请新结点p->next=s.top;//修改栈顶指针s.top=p;s.top->data=x;//余数入栈}while(n);printf("\n\t\t转换后的十六进制数值为：";while(s.top)//出栈处理{if(s.top->data<10);printf("%d",s.top->data);elseswitch(s.top->data){case10:printf("%c",'A');break;case11:printf("%c",'B');break;case12:printf("%c",'C');break;case13:printf("%c",'D');break;case14:printf("%c",'E');break;case15:printf("%c",'F');break;}stacknode*p=s.top;s.top=s.top->next;free(p);//出栈一个余数，收回一个结}printf("\n\n");}voidmain(){intn;printf("\n\t\t请输入一个十进制正整数：");scanf("%d",&n);Conversion(n);}单元练习4一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳）（√）（1）队列是限制在两端进行操作的线性表。（√）（2）判断顺序队列为空的
标准
excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载
是头指针和尾指针都指向同一个结点。（×）（3）在链队列上做出队操作时，会改变front指针的值。（√）（4）在循环队列中，若尾指针rear大于头指针front，其元素个数为rear-front。（×）（5）在单向循环链表中，若头指针为h，那么p所指结点为尾结点的条件是p=h。（√）（6）链队列在一定范围内不会出现队满的情况。（×）（7）在循环链队列中无溢出现象。（×）（8）栈和队列都是顺序存储的线性结构。（×）（9）在队列中允许删除的一端称为队尾。（×）（10）顺序队和循环队关于队满和队空的判断条件是一样的。二．填空题在队列中存取数据应遵循的原则是先进先出。队列是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。在队列中，允许插入的一端称为队尾。在队列中，允许删除的一端称为队首（或队头）。队列在进行出队操作时，首先要判断队列是否为空。顺序队列在进行入队操作时，首先要判断队列是否为满。顺序队列初始化后，front=rear=-1。解决顺序队列“假溢出”的方法是采用循环队列。循环队列的队首指针为front，队尾指针为rear，则队空的条件为front==rear。链队列LQ为空时，LQ->front->next=NULL。设长度为n的链队列用单循环链表表示，若只设头指针，则入队操作的时间复杂度为O（n）。设长度为n的链队列用单循环链表表示，若只设尾指针，则出队操作的时间复杂度为0（1）。在一个链队列中，若队首指针与队尾指针的值相同，则表示该队列为空。设循环队列的头指针front指向队首元素，尾指针rear指向队尾元素后的一个空闲元素，队列的最大空间为MAXLEN，则队满标志为：front==(rear+1)%MAXLEN。在一个链队列中，若队首指针为front，队尾指针为rear，则判断该队列只有一个结点的条件为：front==rear&&front!NULL。(或front==rear&&front<>NULL)向一个循环队列中插入元素时，首先要判断队尾指针，然后再向指针所指的位置写入新的数据。读队首元素的操作不改变（或不影响）队列元素的个数。（18）设循环队列的容量为40（序号从0到39），现经过一系列的入队和出队运算后，有front=11，rear=19，则循环队列中还有8个元素。（L=(N＋rear－front)%N=（40＋19－11）%40=8）（19）队列Q，经过下列运算：InitQueue(Q)(初始化队列);InQueue(Q,a);InQueue(Q,b);OutQueue(Q,x);ReadFront(Q,x);QEmpty(Q);后的值是0。（20）队列Q经过InitQueue(Q)(初始化队列);InQueue(Q,a);InQueue(Q,b);ReadFront(Q,x)后，x的值是a。三．选择题（1）队列是限定在（D）进行操作的线性表。A．中间B．队首C．队尾D．端点（2）队列中的元素个数是(B)。A．不变的B．可变的C．任意的D．0（3）同一队列内各元素的类型(A)。A．必须一致B．不能一致C．可以不一致D．不限制（4）队列是一个(C)线性表结构。A．不加限制的B．推广了的C．加了限制的D．非（5）当利用大小为n的数组顺序存储一个队列时，该队列的最后一个元素的下标为（B）。A．n-2B．n-1C．nD．n+1（6）一个循环队列一旦说明，其占用空间的大小（A）。A．已固定B．可以变动C．不能固定D．动态变化（7）循环队列占用的空间(A)。A．必须连续B．不必连续C．不能连续D．可以不连续（8）存放循环队列元素的数组data有10个元素，则data数组的下标范围是(B)。A．0..10B．0..9C．1..9D．1..10（9）若进队的序列为：A，B，C，D，则出队的序列是（C）。A．B，C，D，AB．A，C，B，DC．A，B，C，DD．C，B，D，A（10）四个元素按：A，B，C，D顺序连续进队Q，则队尾元素是（D）。A．AB．BC．CD．D（11）四个元素按：A，B，C，D顺序连续进队Q，执行一次OutQueue(Q)操作后，队头元素是（B）。A．AB．BC．CD．D（12）四个元素按：A，B，C，D顺序连续进队Q，执行四次OutQueue(Q)操作后，再执行QEmpty(Q);后的值是（B）。A．0B．1C．2D．3（13）队列Q，经过下列运算后，x的值是（B）。InitQueue(Q)(初始化队列);InQueue(Q,a);InQueue(Q,b);OutQueue(Q,x);ReadFront(Q,x);A．aB．bC．0D．1（14）循环队列SQ队满的条件是(B)。A．SQ->rear==SQ->frontB．(SQ->rear+1)%MAXLEN==SQ->frontC．SQ->rear==0D．SQ->front==0（15）设链栈中结点的结构：data为数据域，next为指针域，且top是栈顶指针。若想在链栈的栈顶插入一个由指针s所指的结点，则应执行下列（A）操作。A．s->next=top->next；top->next=s；B．top->next=s；C．s->next=top；top=top->next；D．s->next=top；top=s；（16）带头结点的链队列LQ示意图如下，链队列的队头元素是（A）LQ->frontHABCDΛLQ->rearA．AB．BC．CD．D（17）带头结点的链队列LQ示意图如下，指向链队列的队头指针是（C）LQ->frontHABCDΛLQ->rearA．LQ->frontB．LQ->rearC．LQ->front->nextD．LQ->rear->next（18）带头结点的链队列LQ示意图如下，在进行进队运算时指针LQ->front（A）LQ->frontHABCDΛLQ->rearA．始终不改变B．有时改变C．进队时改变D．出队时改变（19）队列Q，经过下列运算后，再执行QEmpty(Q)的值是（C）。InitQueue(Q)(初始化队列);InQueue(Q,a);InQueue(Q,b);OutQueue(Q,x);ReadQueue(Q,x);A．aB．bC．0D．1（20）若用一个大小为6的数组来实现循环队列，且当前front和rear的值分别为3和0，当从队列中删除一个元素，再加入两个元素后，front和rear的值分别为(B)。A．5和1B．4和2C．2和4D．1和5四．写出程序运行的结果写出下列程序段的输出结果（队列中的元素类型为char）。voidmain(){QueueQ;InitQueue(Q);//初始化队列charx="E";y="C";InQueue(Q,"H");InQueue(Q,"R");InQueue(Q,y);OutQueue(Q,x);InQueue(Q,x);OutQueue(Q,x);InQueue(Q,"A");while(!QEmpty(Q)){OutQueue(Q,y);printf(y);};printf(x);}答：输出为“CHAR”。五．程序填空假定用一个循环单链表表示一个循环队列，该队列只设一个队尾指针rear，试填空完成向循环队列中插入一个元素为x的结点的函数。typedefstructqueuenode//定义队列的存储结构{intdata;structqueuenode*next;}QueueNode;InQueue(QueueNode*rear,intx)//向队列插入元素为x的函数{QueueNode*rear;QueueNode*head,*s;s=newQueueNode;s->data=x;if(rear==NULL)//循环队列为空，则建立一个结点的循环队列{rear=s;rear->next;}else{head=rear->next;//循环队列非空，则将s插到后面rear->next=s;rear=s;rear->next=head;}}六.算法设计题（1）设一个循环队列Queue，只有头指针front，不设尾指针，另设一个含有元素个数的记数器cont，试写出相应的入队算法和出队算法。解：//入队算法：voidinqueqe(intx){inttemp;if(count==n)printf("队列上溢出\n");else{count++temp=(front+count)%n;Queue[temp]=x}}//出队算法：intoutqueue(){inttemp;if(count==0)printf("队列下溢出\n");else{temp=Queue[front];front=(front+1)%n;count--;returntemp;}}（2）用一个循环数组Q[0..MAXLEN-1]表示队列时，该队列只有一个头指针front，不设尾指针，而改置一个记数器count用以记录队列中结点的个数。试编写一个能实现：初始化队列、判队空、读队头元素、入队操作和出队操作的算法。解：//用一个循环数组Queue[0，n-1]表示该循环队列，头指针为front，计数器count用来记录队列中结点的个数。//队列为空：count==0//队列为满：count=MAXLEN//队尾第一个元素位置==(front+count)%MAXLEN//队首第一个元素位置==(front+1)%MAXLENconstMAXLEN=100;intqueue[MAXLEN];intfront,count;//定义队头和计数器count①初始化队列voidinit(){front=1;count=0;}②判定队空intQEmpty(){if(count==0)return(1);elsereturn(0);}③读队头元素voidReadFront(intqueue[],x){if(count==0)printf("下溢出\n");else{front=(front+1)%MAXLEN;x=queue[front];}}④入队操作voidInQueue(intqueue[],intx){intplace;if(count==MAXLEN)printf("上溢出\n");else{count++;place=(front+count)%MAXLEN;queue[MAXLEN]=x;}}⑤出队操作voidOutQueue(intqueue[])//删除队列头元素{if(count==0)printf("队列下溢出\n");else{front=(front+1)%MAXLEN;count--;}}（3）一个用单链表组成的循环队列，只设一个尾指针rear，不设头指针，请编写他如下算法：①向循环队列中插入一个元素为x的结点；②从循环队列中删除一个结点。①解：//定义本题队列的结点类型如下：typedefstructlinknode{intdata;structlinknode*next;}QueueNode;QueueNode*rear;Inqueue(intx)//向队列插入结点x{QueueNode*head,*s;s=(qu*)newqu;//创建一个新结点s->data=x;if(rear==NUlL)//若队空,则建立一个循环队列{rear=s;rear->next=s;}else//若不为空，则将s插到后面{head=rear->next；rear->next=s;rear=s;//rear始终指向最后一个结点rear->next=head;}}②解：voiddelqueue(rear){if(rear==NULL)printf("下溢出!\n");else{head=rear->next;//head指向队首结点if(head==rear)rear=NULL//只有—个结点则直接删除该结点elserear->next=head->next//否则删除第一个结点deletehead；//释放队首结点}}单元练习5一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳）（ㄨ）（1）串是n个字母的有限序列。（√）（2）串的数据元素是一个字符。（ㄨ）（3）串的长度是指串中不同字符的个数。（ㄨ）（4）如果两个串含有相同的字符，则说明它们相等。（ㄨ）（5）如果一个串中所有的字母均在另一个串中出现，则说明前者是后者的子串。（√）（6）串的堆分配存储是一种动态存储结构。（ㄨ）（7）“DT”是“DATA”的子串。（ㄨ）（8）串中任意个字符组成的子序列称为该串的子串。（√）（9）子串的定位运算称为模式匹配。（√）（10）在链串中为了提高存储密度，应该增大结点的大小。二．填空题由零个或多个字符组成的有限序列称为字符串（或串）。字符串按存储方式可以分为：顺序存储、链接存储和堆分配存储。串的顺序存储结构简称为顺序串。串顺序存储非紧凑格式的缺点是：空间利用率低。串顺序存储紧凑格式的缺点是对串的字符处理效率低。串链接存储的优点是插入、删除方便，缺点的空间利用率低。在C或C++语言中，以字符\0表示串值的终结。空格串的长度等于空格的个数。在空串和空格串中，长度不为0的是空格串。两个串相等是指两个串相长度等，且对应位置的字符都相同。设S="MyMusic"，则LenStr(s)=_8。两个字符串分别为：S1="Todayis"，S2="30July,2005",ConcatStr(S1,S2)的结果是：Todayis30July,2005。求子串函数SubStr("Todayis30July,2005",13,4)的结果是：July。在串的运算中，EqualStr(aaa,aab)的返回值为<0。在串的运算中，EqualStr(aaa,aaa)的返回值为0。在子串的定位运算中，被匹配的主串称为目标串，子串称为模式。模式匹配成功的起始位置称为：有效位移。设S="abccdcdccbaa"，T="cdcc"，则第6次匹配成功。设S="c:/mydocument/text1.doc"，T="mydont"，则字符定位的位置为0。若n为主串长度，m为子串长度，且n>>m，则模式匹配算法最坏情况下的时间复杂度为：(n-m+1)*m。三．选择题（1）串是一种特殊的线性表，其特殊性体现在（B）。A.可以顺序存储B．数据元素是一个字符C.可以链接存储D．数据元素可以是多个字符（2）某串的长度小于一个常数，则采用（B）存储方式最节省空间。A．链式B．顺序C．堆结构D．无法确定（3）以下论述正确的是（C）。A．空串与空格串是相同的B．"tel"是"Teleptone"的子串C．空串是零个字符的串D.空串的长度等于1（4）以下论述正确的是（B）。A．空串与空格串是相同的B．"ton"是"Teleptone"的子串C．空格串是有空格的串D.空串的长度等于1（5）以下论断正确的是(A)。A．""是空串，""空格串B．"BEIJING"是"BEIJING"的子串C．"something"<"Somethig"D．"BIT"="BITE"（6）设有两个串S1和S2，则EqualStr(S1,S2)运算称作(D)。A.串连接B．模式匹配C.求子串D．串比较（7）串的模式匹配是指（D）。A．判断两个串是否相等C．找某字符在主串中第一次出现的位置B．对两个串比较大小D．找某子串在主串中第一次出现的第一个字符位置（8）若字符串"ABCDEFG"采用链式存储，假设每个字符占用1个字节，每个指针占用2个字节。则该字符串的存储密度为(D)。A．20％B．40％C．50％D．33．3％（9）若字符串"ABCDEFG"采用链式存储，假设每个指针占用2个字节，若希望存储密度50％，则每个结点应存储(A)个字符。A．2B．3C．4D．5（10）设串S1="IAM"，S2="ASDUDENT",则ConcatStr(S1,S2)=(B)。A．"IAM"B．"IAMASDUDENT"C．"IAMASDUDENT"D."ASDUDENT"（11）设S=""，则LenStr（S）=（A）。A．0B．1C．2D．3（12）设目标串T="AABBCCDDE"，模式P="ABCDE"，则该模式匹配的有效位移为(A)。A．0B．1C．2D．3（13）设目标串T="AABBCCDDEEFF"，模式P="CCD"，则该模式匹配的有效位移为(D)。A．2B．3C．4D.5（14）设目标串T="aabaababaabaa"，模式P="abab",朴素匹配算法的外层循环进行了(D)次。A．1B．9C．4D．5（15）朴素模式匹配算法在最坏情况下的时间复杂度是(D)。A．O（m）B．O（n）C．0（m+n）D．0（m*n）（16）S="morning"，执行求子串函数SubStr(S,2,2)后的结果为(B)。A．"mo"B．"or"C．"in"D．"ng"（17）S1="good"，S2="morning"，执行串连接函数ConcatStr(S1,S2)后的结果为(A)。A．"goodmorning"B．"goodmorning"C．"GOODMORNING"D．"GOODMORNING"（18）S1="good"，S2="morning"，执行函数SubStr(S2,4,LenStr(S1))后的结果为(B)。A．"good"B．"ning"C．"go"D．"morn"（19）设串S1="ABCDEFG"，S2="PQRST",则ConcatStr(SubStr(S1,2,LenStr(S2)),SubStr(S1,LenStr(S2),2))的结果串为(D)。A．BCDEFB．BCDEFGC．BCPQRSTD.BCDEFEF（20）若串S="SOFTWARE"，其子串的数目最多是：（C）。A．35B．36C．37D．38（8+7+6+5+4+3+2+1+1=37）四．程序题填空（1）下面程序是把两个串r1和r2首尾相连的程序，即：r1=r1+r2，试完成程序填空。typedefStruct{charvec[MAXLEN];//定义合并后串的最大长度intlen;//len为串的长度}St;voidConcatStr(Str*r1,Str*r2)//字符串连接函数{inti;cout<vec<vec;if(r1->len+r2->len>MAXLEN)cout<<"两个串太长，溢出！";else{for(i=0;ilen;i++)//把r2连接到r1r1->vec[r1->len+i]=r2->vec[i];r1->vec[r1->len+i]='\0';//添上字符串结束标记r1->len=r1->len+r2->len;//修改新串长度}}（2）设x和y两个串均采用顺序存储方式，下面的程序是比较x和y两个串是否相等的函数，试完成程序填空。#defineMAXLEN100typedefstruct{charvec[MAXLEN];len;}str;intsame(x,y)str*x,*y;{inti=0,tag=1;if(x->len!=y->len)return(0);//(或<>)else{while(ilen&&tag){if(x->vec[i]!=y->vec[i])tag=0;i++;（或i=i+1）}return(tag);}}下面算法是判断字符串是否为回文（即正读和倒读相同），试完成程序填空。#include"stdio.h"typedefstruct{c
浙公网安备 33021202002483