实用数据结构基础参考答案

单元练习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〕数据在计算机存储器内表示时，物理地址和逻辑地址相同并且是连续的，称之为〔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<n;i++)for(j=0;i<n;j++)c[i][j]=i+j;A.O〔1〕B.O〔n〕C.O〔log2n〕D.O〔n2〕〔19〕算法分析的两个主要方面是〔A〕。A.空间复杂性和时间复杂性 B.正确性和简明性C.可读性和文档性 D.数据复杂性和程序复杂性〔20〕计算机算法必须具备输入、输出和〔C〕。A.计算方法B.排序方法C.解决问题的有限运算步骤D.程序设计方法四．分析下面各程序段的时间复杂度for(i=0;i<n;i++)for(j=0;j<m;j++)A[i][j]解：O(n*m)〔2〕s=0;for(i=0;i<n;i++)for(j=0;j<n;j++)s+=B[i][j];sum=s;解：O(n2)〔3〕T=A；A=B；B=T；解：O(1)〔4〕s1(intn){intp=1,s=0;for(i=1;i<=n;i++){p*=i;s+=p;}return(s);}O(n)〔5〕s2(intn)x=0;y=0;for(k=1;k<=n;k++)x++;for(i=1;i<=n;i++)for(j=1;j<=n;j++)y++;解：O(n2)五．根据二元组关系，画出对应逻辑图形的草图，指出它们属于何种数据结构。〔1〕A=〔D，R〕，其中：D={a，b，c，d，e}，R={}解：abcde属于集合〔2〕B=〔D,R〕，其中：D={a,b,c,d,e,f}，R={r}R={<a,b>,<b,c>,<c,d>,<d,e>,<e,f>}〔尖括号表示结点之间关系是有向的〕解：bbaedfc属于线性结构。〔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>}25502550755736826455属于树结构〔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)}〔园括号表示结点之间关系是有向的〕解：1126345属于图结构〔5〕E=〔D,R〕，其中：D={a,b,c,d,e,f,g,h}，R={r}R={<d,b>,<d,g>,<d,a>,<b,c>,<g,e>,<g,h>,<e,f>}解：bbdfeahgcc属于树结构。单元练习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;来实现该操作。PPΛabSS三．选择题〔1〕在具有n个结点的单链表中，实现〔A〕的操作，其算法的时间复杂度都是O〔n〕。A．遍历链表或求链表的第i个结点 B．在地址为P的结点之后插入一个结点C．删除开始结点 D．删除地址为P的结点的后继结点〔2〕设a、b、c为三个结点，p、10、20分别代表它们的地址，那么如下的存储结构称为〔B〕。aa10c^b20P循环链表 B．单链表 C．双向循环链表 D．双向链表〔3〕单链表的存储密度〔C〕。 A．大于1 B．等于1 C．小于1 D．不能确定〔4〕一个顺序存储的线性表，设每个结点占m个存储单元，假设第一个结点的地址为B，那么第i个结点的地址为〔A〕。A．B+(i-1)*m B．B+i*m C．B-i*m D．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==L B．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．2 B．3 C．4D．5 〔12〕单链表的示意图如下：LABCDΛQRQRP指向链表Q结点的前趋的指针是〔B〕。A．L B．P C．Q D．R〔13〕设p为指向单循环链表上某结点的指针，那么*p的直接前驱〔C〕。A．找不到 B．查找时间复杂度为O〔1〕C．查找时间复杂度为O〔n〕 D．查找结点的次数约为n〔14〕等概率情况下，在有n个结点的顺序表上做插入结点运算，需平均移动结点的数目为〔C〕。A．n B．(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*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)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．0 B．-1C．不再改变D．动态变化〔19〕一个栈的入栈次序ABCDE，那么栈的不可能的输出序列是(C)。A．EDCBAB．DECBA C．DCEAB D．ABCDE〔20〕设有一个顺序栈S，元素A,B,C,D,E,F,依次进栈，如果六个元素出栈的顺序是B，D，C，F，E，A，那么栈的容量至少应是(A)。A．3B．4 C．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<strlen(a);i++)if(a[i]==’(’)Push(s,’(’);elseif(a[i]==’)’){ifStackEmpty(s) //调用判栈空函数return0; //假设栈为空返回0；否那么出栈elsePop(s);}if(StackEmpty(s)) //调用判栈空函数printf(“配对正确！〞); //假设栈空，说明配对正确，并返回1elseprintf(“配对错误！〞); //配对错误返回0}设计一个将十进正整数转换为十进制数的算法，并要求上机调试通过。解：#include<stdio.h>#include<stdlib.h>typedefstructstacknode //定义栈的存储结构{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〕判断顺序队列为空的标准是头指针和尾指针都指向同一个结点。〔×〕〔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-2 B．n-1 C．nD．n+1〔6〕一个循环队列一旦说明，其占用空间的大小〔A〕。A．已固定B．可以变动 C．不能固定D．动态变化〔7〕循环队列占用的空间(A)。A．必须连续 B．不必连续 C．不能连续D．可以不连续〔8〕存放循环队列元素的数组data有10个元素，那么data数组的下标范围是(B)。A．0..10B．0..9 C．1..9 D．1..10〔9〕假设进队的序列为：A，B，C，D，那么出队的序列是〔C〕。A．B，C，D，A B．A，C，B，DC．A，B，C，D D．C，B，D，A〔10〕四个元素按：A，B，C，D顺序连续进队Q，那么队尾元素是〔D〕。A．A B．BC．C D．D〔11〕四个元素按：A，B，C，D顺序连续进队Q，执行一次OutQueue(Q)操作后，队头元素是〔B〕。A．A B．BC．C D．D〔12〕四个元素按：A，B，C，D顺序连续进队Q，执行四次OutQueue(Q)操作后，再执行QEmpty(Q);后的值是〔B〕。A．0 B．1C．2 D．3〔13〕队列Q，经过以下运算后，x的值是〔B〕。InitQueue(Q)(初始化队列);InQueue(Q,a);InQueue(Q,b);OutQueue(Q,x);ReadFront(Q,x);A．a B．bC．0D．1〔14〕循环队列SQ队满的条件是(B)。A．SQ->rear==SQ->front B．(SQ->rear+1)%MAXLEN==SQ->frontC．SQ->rear==0 D．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．A B．BC．CD．D〔17〕带头结点的链队列LQ示意图如下，指向链队列的队头指针是〔C〕LQ->frontHABCDΛLQ->rearA．LQ->frontB．LQ->rearC．LQ->front->next D．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．a B．bC．0 D．1〔20〕假设用一个大小为6的数组来实现循环队列，且当前front和rear的值分别为3和0，当从队列中删除一个元素，再参加两个元素后，front和rear的值分别为(B)。A．5和1 B．4和2 C．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．3 C．4 D．5〔10〕设串S1="IAM"，S2="ASDUDENT",那么ConcatStr(S1,S2)=(B)。A．"IAM" B．"IAMASDUDENT"C．"IAMASDUDENT" D."ASDUDENT"〔11〕设S=""，那么LenStr〔S〕=〔A〕。A．0 B．1 C．2D．3〔12〕设目标串T="AABBCCDDE"，模式P="ABCDE"，那么该模式匹配的有效位移为(A)。A．0 B．1 C．2D．3〔13〕设目标串T="AABBCCDDEEFF"，模式P="CCD"，那么该模式匹配的有效位移为(D)。A．2 B．3C．4D.5〔14〕设目标串T="aabaababaabaa"，模式P="abab",朴素匹配算法的外层循环进行了(D)次。A．1B．9 C．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<<r1->vec<<r2->vec; if(r1->len+r2->len>MAXLEN) cout<<"两个串太长，溢出！"; else{ for(i=0;i<r2->len;i++)//把r2连接到r1 r1->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(i<x->len&&tag){if(x->vec[i]!=y->vec[i])tag=0;i++;〔或i=i+1〕}return(tag);}}下面算法是判断字符串是否为回文〔即正读和倒读相同〕，试完成程序填空。#include"stdio.h"typedefstruct{charvec[MAXLEN];intlen;}str;voidPalindrome(strs){inti=0;ingj=s.len-1;while(j-i>=1){if(s.vec[i]==s.vec[j]){i++;j--;continue}//(或j=j+1)elsebreak;}if(j-i>=1)cout<<"Itisnotapalindrome\n";elsecout<<"Itisapalindrome\n";}编程题〔1〕设下面所用的串均采用顺序存储方式，其存储结构定义如下，请编写以下算法：#defineMAXLEN100typedefstruct{charvec[MAXLEN];intlen;}str;将串中r中所有其值为ch1的字符换成ch2的字符。将串中r中所有字符按照相反的次序仍存放在r中。从串r中删除其值等于ch的所有字符。从串r1中第index个字符起求出首次与字符r2相同的子串的起始位置。从串r中删除所有与串r3相同的子串〔允许调用第〔4〕小题的函数〕。编写一个比拟x和y两个串是否相等的函数。解：①//算法思想：从头至尾扫描r串，对于值为ch1的元素直接替换成ch2即可。str*trans(r,ch1,ch2)str*r;charch1,ch2;{inti;for(i=0;i<r->len;i++)if(r->vec[i]==ch1)r-vec[i]=ch2;return(r);}②//算法思想是：将第一个元素与最后一个元素交换，第二个元素与倒数第二个元素交换，依次类推，便将该串的所有字符反序了。str*invert(r)str*r;{inti;charx;for(i=0;i<(r->len%2);i++){x=r->vec[i];r->vec[i]=