《大大数据结构》课后参考问题详解

《《大大数据结构》课后参考问题详解》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

实用标准文档单元练习1一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳）（√）（1）数据的逻辑结构与数据元素本身的内容和形式无关。（√）（2）一个数据结构是由一个逻辑结构和这个逻辑结构上的一个基本运算集构成的整体。（ㄨ）（3）数据元素是数据的最小单位。（ㄨ）（4）数据的逻辑结构和数据的存储结构是相同的。（ㄨ）（5）程序和算法原则上没有区别，所以在讨论数据结构时可以通用。（√）（6）从逻辑关系上讲，数据结构主要分为线性结构和非线性结构两类。（√）（7）数据的存储结构是数据的逻辑结构的存储映像。（√）（8）数据的物理结构是指数据在计算机内实际的存储形式。（ㄨ）（9）数据的逻辑结构是依赖于计算机的。（√）（10）算法是对解题方法和步骤的描述。二．填空题（1）数据有逻辑结构和存储结构两种结构。（2）数据逻辑结构除了集合以外，还包括：线性结构、树形结构和图形结构。（3）数据结构按逻辑结构可分为两大类，它们是线性结构和非线性结构。（4）树形结构和图形结构合称为非线性结构。（5）在树形结构中，除了树根结点以外，其余每个结点只有1个前趋结点。（6）在图形结构中，每个结点的前趋结点数和后续结点数可以任意多个。（7）数据的存储结构又叫物理结构。（8）数据的存储结构形式包括：顺序存储、链式存储、索引存储和散列存储。（9）线性结构中的元素之间存在一对一的关系。（10）树形结构结构中的元素之间存在一对多的关系，（11）图形结构的元素之间存在多对多的关系。文案大全 实用标准文档（1）数据结构主要研究数据的逻辑结构、存储结构和算法（或运算）三个方面的内容。（2）数据结构被定义为(D，R)，其中D是数据的有限集合，R是D上的关系的有限集合。（3）算法是一个有穷指令的集合。（4）算法效率的度量可以分为事先估算法和事后统计法。（5）一个算法的时间复杂性是算法输入规模的函数。（6）算法的空间复杂度是指该算法所耗费的存储空间，它是该算法求解问题规模n的函数。（7）若一个算法中的语句频度之和为T（n）=6n+3nlog2n，则算法的时间复杂度为O（nlog2n）。（8）若一个算法中的语句频度之和为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）。A.无直接前趋结点B.无直接后继结点C.只有一个直接前趋结点和一个直接后继结点文案大全 实用标准文档A.可能有多个直接前趋结点和多个直接后继结点（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）插入和删除操作是数据结构中最基本的两种操作，所以这两种操作在数组中也经常使用。二．填空题（1）顺序表中逻辑上相邻的元素在物理位置上必须相连。（2）线性表中结点的集合是有限的，结点间的关系是一对一关系。（3）顺序表相对于链表的优点是：节省存储和随机存取。（4）链表相对于顺序表的优点是：插入、删除方便。（5）采用顺序存储结构的线性表叫顺序表。（6）顺序表中访问任意一个结点的时间复杂度均为O(1)。（7）链表相对于顺序表的优点是插入、删除方便；缺点是存储密度小。（8）在双链表中要删除已知结点*P，其时间复杂度为O(1)。（9）在单链表中要在已知结点*P之前插入一个新结点，需找到*P的直接前趋结点的地址，其查找的时间复杂度为O(n)。（10）单链表中需知道头指针才能遍历整个链表。文案大全 实用标准文档（10）性表中第一个结点没有直接前趋，称为开始结点。（11）在一个长度为n的顺序表中删除第i个元素，要移动n-i个元素。（12）在一个长度为n的顺序表中，如果要在第i个元素前插入一个元素，要后移n-i+1个元素。（13）在无头结点的单链表中，第一个结点的地址存放在头指针中，而其它结点的存储地址存放在前趋结点的指针域中。（14）当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快速度存取线性表中的元素时，应采用顺序存储结构。（15）在线性表的链式存储中，元素之间的逻辑关系是通过指针决定的。（16）在双向链表中，每个结点都有两个指针域，它们一个指向其前趋结点，另一个指向其后继结点。（17）对一个需要经常进行插入和删除操作的线性表，采用链式存储结构为宜。（18）双链表中，设p是指向其中待删除的结点，则需要执行的操作为：p->prior->next=p->next。（19）在如图所示的链表中，若在指针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^b20PA．循环链表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);}（1）对给定的带头结点的单链表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;}（1）已知一个单向链表，编写一个函数从单链表中删除自第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;}}}（1）有一个单向链表（不同结点的数据域值可能相同），其头指针为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）。A．先存入元素，后移动栈顶指针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（2）求后缀表达式①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(" tt转换后的十六进制数值为：";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(" ");}voidmain(){intn;printf(" tt请输入一个十进制正整数：");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）顺序队和循环队关于队满和队空的判断条件是一样的。二．填空题（1）在队列中存取数据应遵循的原则是先进先出。（2）队列是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。（3）在队列中，允许插入的一端称为队尾。（4）在队列中，允许删除的一端称为队首（或队头）。（5）队列在进行出队操作时，首先要判断队列是否为空。（6）顺序队列在进行入队操作时，首先要判断队列是否为满。（7）顺序队列初始化后，front=rear=-1。（8）解决顺序队列“假溢出”的方法是采用循环队列。（9）循环队列的队首指针为front，队尾指针为rear，则队空的条件为front==rear。（10）链队列LQ为空时，LQ->front->next=NULL。（11）设长度为n文案大全 实用标准文档的链队列用单循环链表表示，若只设头指针，则入队操作的时间复杂度为O（n）。（1）设长度为n的链队列用单循环链表表示，若只设尾指针，则出队操作的时间复杂度为0（1）。（2）在一个链队列中，若队首指针与队尾指针的值相同，则表示该队列为空。（3）设循环队列的头指针front指向队首元素，尾指针rear指向队尾元素后的一个空闲元素，队列的最大空间为MAXLEN，则队满标志为：front==(rear+1)%MAXLEN。（4）在一个链队列中，若队首指针为front，队尾指针为rear，则判断该队列只有一个结点的条件为：front==rear&&front!NULL。(或front==rear&&front<>NULL)（5）向一个循环队列中插入元素时，首先要判断队尾指针，然后再向指针所指的位置写入新的数据。（6）读队首元素的操作不改变（或不影响）队列元素的个数。（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("队列上溢出 ");else{count++temp=(front+count)%n;Queue[temp]=x}}//出队算法：intoutqueue(){inttemp;if(count==0)printf("队列下溢出 ");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("下溢出 ");else{front=(front+1)%MAXLEN;x=queue[front];}}④入队操作voidInQueue(intqueue[],intx){intplace;if(count==MAXLEN)printf("上溢出 ");else{count++;place=(front+count)%MAXLEN;文案大全 实用标准文档queue[MAXLEN]=x;}}⑤出队操作voidOutQueue(intqueue[])//删除队列头元素{if(count==0)printf("队列下溢出 ");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("下溢出! ");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）在链串中为了提高存储密度，应该增大结点的大小。二．填空题（1）由零个或多个字符组成的有限序列称为字符串（或串）。（2）字符串按存储方式可以分为：顺序存储、链接存储和堆分配存储。（3）串的顺序存储结构简称为顺序串。（4）串顺序存储非紧凑格式的缺点是：空间利用率低。（5）串顺序存储紧凑格式的缺点是对串的字符处理效率低。（6）串链接存储的优点是插入、删除方便，缺点的空间利用率低。（7）在C或C++语言中，以字符表示串值的终结。（8）空格串的长度等于空格的个数。（9）在空串和空格串中，长度不为0的是空格串。（10）两个串相等是指两个串相长度等，且对应位置的字符都相同。（11）设S="MyMusic"，则LenStr(s)=_8。（12）两个字符串分别为：S1="Todayis"，S2="30文案大全 实用标准文档July,2005",ConcatStr(S1,S2)的结果是：Todayis30July,2005。（1）求子串函数SubStr("Todayis30July,2005",13,4)的结果是：July。（2）在串的运算中，EqualStr(aaa,aab)的返回值为<0。（3）在串的运算中，EqualStr(aaa,aaa)的返回值为0。（4）在子串的定位运算中，被匹配的主串称为目标串，子串称为模式。（5）模式匹配成功的起始位置称为：有效位移。（6）设S="abccdcdccbaa"，T="cdcc"，则第6次匹配成功。（7）设S="c:/mydocument/text1.doc"，T="mydont"，则字符定位的位置为0。（8）若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]='';//添上字符串结束标记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);}}（2）下面算法是判断字符串是否为回文（即正读和倒读相同），试完成程序填空。#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 ";elsecout<<"Itisapalindrome ";}五．编程题（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;ilen;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]=r->[r->len-i+1];r->vec[r->len-i+1]=x;}return(r);}文案大全 实用标准文档③//算法思想：从头到尾扫描r串，对于值为ch的元素用移动的方式进行删除。str*delall(r,ch)str*r;charch;{inti,j;for(i=0;ilen;i++)if(r->vec[i]==ch){for(j=i;jlen;j++)r->vec[i]=r->vec[i+1];r->len=r->len-1;}return(r);}④//算法思想：从第index个元素开始扫描r1，当其元素值与r2的第一个元素的值相同时，判定它们之后的元素值是否依次相同，直到r2结束为止，若都相同则返回，否则继续上述过程直到r1扫描完为止。intpartposition(r2,r1,index)str*r2,*r1;intindex;{inti,j,k;for(i=index;r1->vec[i];i++)for(j=i,k=0;r1->vec[j]==r2->vec[k];j++,k++)if(!r2->vec[k+1])return(i);return(-1);}⑤算法思想：从位置1开始调用第（4）小题的函数partposition（），若找到了一个相同子串，则调用delsubstring（），再相同的方法查找后面位置的相同子串。文案大全 实用标准文档str*delstringall(r,r3)str*r,*r3;{inti=0;while(ilen){if(partposition(r,r3,i)!=-1)delsubstring(r,i,r3->len)i++;}}⑥两个串相等的条件是两个串的长度相等，且两个串的对应的字符必须都相同。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++;}return(tag);}}（2）设计一算法判断字符串是否为回文（即正读和倒读相同）解：#include"stdio.h"typedefstruct{char*head;文案大全 实用标准文档intlength;}Hstring;voidisPalindrome(Hstrings){inti=0;intj=s.length-1;while(j-i>=1){if(s.head[i]==s.head[j]){i++;j--;continue;}elsebreak;}if(j-i>=1)printf("Ttisnotapalindrome ");elseprintf("itisapalindrome ");}（2）设计一算法从字符串中删除所有与字串"del"相同的子串解：#include"stdio.h"#include"string.h"typedefstruct{char*head;intlength;}Hstring;char*DeleteSubString(HstringS,HstringT){inti=0;文案大全 实用标准文档intj,k;intSlength=S.length;intTlength=T.length;char*tail;while(i<=Slenght-Tlength){j=0;k=i;while(jt<=0)printf(“a<=0”);if(②col<0||col>=a->n)printf(“列错！”);for(③k=0;kt;④k++)if(a->tada[k].j==n)sum=⑤sum+a->data[k].v;returnsum;}五．编程题（1）试编写求一个三元组表的稀疏矩阵对角线元素之和的算法。#include"stdio.h"#defineERROR-99999typedefstruct{introw;intcol;intdata;}Triple;intMDSum(Triple*a){inti;intsum=0;if(a[0].row!=a[0].col)returnERROR;for(i=1;i<=a[0].data;i++)文案大全 实用标准文档{if(a[i].row==a[i].col)sum+=a[i].data;}returnsum;}（2）试编写求广义表中原子元素个数的算法。解：设j为原子个数，则求广义表中原子元素个数的算法可递归定义如下：j=0LS为空表尾原子元素个数+1LS非空且表头为原子元素表头子表原子元素个数+表尾原子元素个数+1LS非空且表头子表intatomnum(Gnode*head){if(head==NULL)return0;if(head->tag==0)return(atomnum(head->next)+1);elsereturn(atomnum(head->next)+atomnum(head->val.sublist));}（3）试编写求广义表最大中原子元素个数的算法。intmaxele(Gnode*head){intm=0,a;while(head){if(head->tag==1){a=maxele(head->val.sublist);文案大全 实用标准文档if(a>m)m=a;}elseif(head->val.data>m)m=head->val.data;head=head->next;}returnm;}文案大全 实用标准文档单元练习7一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳）（√）（1）树结构中每个结点最多只有一个直接前驱。（ㄨ）（2）完全二叉树一定是满二查树。（ㄨ）（3）在中序线索二叉树中，右线索若不为空，则一定指向其双亲。（√）（4）一棵二叉树中序遍历序列的最后一个结点，必定是该二叉树前序遍历的最后一个结点。（√）（5）二叉树的前序遍历中，任意一个结点均处于其子女结点的前面。（√）（6）由二叉树的前序遍历序列和中序遍历序列，可以推导出后序遍历的序列。（√）（7）在完全二叉树中，若一个结点没有左孩子，则它必然是叶子结点。（ㄨ）（8）在哈夫曼编码中，当两个字符出现的频率相同，其编码也相同，对于这种情况应该做特殊处理。（ㄨ）（9）含多于两棵树的森林转换的二叉树，其根结点一定无右孩子。（√）（10）具有n个叶子结点的哈夫曼树共有2n-1个结点。二．填空题（1）在树中，一个结点所拥有的子树数称为该结点的度。（2）度为零的结点称为叶（或叶子，或终端）结点。（3）树中结点的最大层次称为树的深度（或高度）。（4）对于二叉树来说，第i层上至多有2i-1个结点。（5）深度为h的二叉树至多有2h-1个结点。（6）由一棵二叉树的前序序列和中序序列可唯一确定这棵二叉树。（7）有20个结点的完全二叉树，编号为10的结点的父结点的编号是5。（8）哈夫曼树是带权路径长度最小的二叉树。（9）由二叉树的后序和中序遍历序列，可以唯一确定一棵二叉树。（10）某二叉树的中序遍历序列为:DEBAC，后序遍历序列为：EBCAD。则前序遍历序列为：DABEC。文案大全 实用标准文档（1）设一棵二叉树结点的先序遍历序历为：ABDECFGH，中序遍历序历为：DEBAFCHG，则二叉树中叶结点是：E、F、H。（2）已知完全二叉树的第8层有8个结点，则其叶结点数是68。（3）由树转换成二叉树时，其根结点无右子树。（4）采用二叉链表存储的n个结点的二叉树，一共有2n个指针域。（5）采用二叉链表存储的n个结点的二叉树，共有空指针n+1个。（6）前序为A，B，C且后序为C，B，A的二叉树共有4种。ACBABCABCACB（17）三个结点可以组成2种不同形态的树。（18）将一棵完全二叉树按层次编号，对于任意一个编号为i的结点，其左孩子结点的编号为：2*i。（19）给定如下图所示的二叉树，其前序遍历序列为：ABEFHCG。ABFGHDCE文案大全 实用标准文档（20）给定如下图所示的二叉树，其层次遍历序列为：ABCEFGH。ABFGHDCE三．选择题（1）树最适合用来表示（D）。A．有序数据元素B．无序数据元素C．元素之间无联系的数据D．元素之间有分支的层次关系（2）前序为A，B，C的二叉树共有（D）种。A．2B．3C．4D．5（3）根据二叉树的定义，具有3个结点的二叉树有（C）种树型。A．3B．4C．5D．6（4）在一棵具有五层的满二叉树中，结点的总数为（B）A．16B．31C．32D．33（5）具有64个结点的完全二叉树的深度为（C）A．5B．6C．7D．8（6）任何一棵二叉树的叶结点在前序、中序、后序遍历序列中的相对次序（A）。文案大全 实用标准文档A．不发生改变B．发生改变C．不能确定D．以上都不对（7）A，B为一棵二叉树上的两个结点，在中序遍历时，A在B前的条件是（C）。A．A在B右方B．A是B祖先C．A在B左方D．A是B子孙（8）下列4棵树中，（B）不是完全二叉树。A．B．C．D．ABEGFDCDABECDABCDABEFCDABADECFGHI（9）如右图所示的二叉树，后序遍历的序列是（D）A．ABCDEFGHIB．ABDHIECFGC．HDIBEAFCGD．HIDEBFGCA（10）对于下边的二叉树，其中序序列为（A）A．DBEHAFCGB．DBHEAFCGC．ABDEHCFGD．ABCDEFGH（11）某二叉树的后序遍历序列为：DABEC，中序遍历序列为:DEBAC文案大全 实用标准文档，则前序遍历序列为（D）。A．ACBEDB．DECABC．DEABCD．CEDBA（12）具有n（n>1）个结点的完全二叉树中，结点i（2i>n）的左孩子结点是（D）。A．2iB．2i+1C．2i-1D．不存在（若2i<=n，则答案为A）（13）把一棵树转换为二叉树后，这棵二叉树的形态是（A）。A．唯一的B．有多种C．有多种，但根结点都没有左孩子D．有多种，但根结点都没有右孩子（14）将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点编号，根结点的编号为1，则编号为45的结点的左孩子编号为（B）。A．46B．47C．90D．91（15）将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点编号，根结点的编号为1，则编号为49的结点的右孩子编号为（B）。A．98B．99C．50D．100（16）二叉树按某种顺序线索化后，任一结点均有指向其前驱和后继的线索，这种说法（B）。A．正确B．错误C．不确定D．都有可能（17）下列陈述正确的是（D）。A．二叉树是度为2的有序树B．二叉树中结点只有一个孩子时无左右之分C．二叉树中必有度为2的结点D．二叉树中最多只有两棵子树，且有左右子树之分（18）用5个权值{3,2,4,5,1}构造的哈夫曼树的带权路径长度是（B）。Ａ．32Ｂ．33Ｃ．34Ｄ．15（先构造哈夫曼树，WPL=（1+2）*3+（3+4+5）*2=33）（19）在树结构中，若结点B有4个兄弟，A是B的父亲结点，则A的度为为（C）。A．3B．4C．5D．6（20）二叉树的叶结点个数比度为2的结点的个数（C）。A．无关B．相等C．多一个D．少一个文案大全 实用标准文档四.简答题（1）已知一棵树边的集合如下，请画出此树，并回答问题。{(L,M),(L,N),(E,L),(B,E),(B,D),(A,B),(G,J),(G,K),(C,G),(C,F),(H,I),(C,H),(A,C)}①哪个是根结点？②哪些是叶结点？③哪个是G的双亲？④哪些是G的祖先？⑤哪些是G的孩子？⑥哪些是E的子孙？⑦哪些是E的兄弟？哪些是F的兄弟？⑧结点B和N的层次各是多少？⑨树的深度是多少？⑩以结点C为根的子树的深度是多少？⑪树的度数是多少？答：①A是根结点。②叶结点：M，N，D，J，K，F，I。③G的双亲：C。④G的祖先：A，C。⑤G的孩子：J，K。⑥E的子孙：L，M，N。⑦E的兄弟：D；F的兄弟：G，H。⑧结点B的层次为2；结点N的层次是5。⑨树的深度是5。⑩以结点C为根的子树的深度是3。⑪树的度数是3。（2）设下列二叉树是与某森林对应的二叉树，试回答下列问题。DABEGICFHJLK①森林中有几棵树？②每一棵树的根结点分别是什么？③第一棵树有几个结点？④第二棵树有几个结点？⑤森林中有几个叶结点？文案大全 实用标准文档解：①4②A,C,G,K③6④2⑤7（3）二叉树按中序遍历的结果为：ABC，试问有几种不同形态的二叉树可以得到这一遍历结果？并画出这些二叉树。答：有5种不同形态的二叉树可以得到这一遍历结果，如下图所示。ABCAADCBBABCACCB（4）分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。答：3个结点的树：3个结点的二叉树树：五.应用题文案大全 实用标准文档（1）已知一棵二叉树的后序遍历和中序遍历的序列分别为：ACDBGIHFE和ABCDEFGHI。请画出该二叉树，并写出它的前序遍历的序列。BCHDDFGEIA解：恢复的二叉树为：其前序遍历的序列为：EBADCFHGI（2）已知一棵二叉树的前序遍历和中序遍历的序列分别为：ABDGHCEFI和GDHBAECIF。请画出此二叉树，并写出它的后序遍历的序列。GHABDCEFI解：恢复的二叉树为：其后序遍历的序列为：GHDBEIFCA（3）已知一棵树的层次遍历的序列为：ABCDEFGHIJ，中序遍历的序列为：DBGEHJACIF，请画出该二叉树，并写出它的后序遍历的序列。ABCHDDFGEIJ解：文案大全 实用标准文档后序遍历的序列：DGJHEBIFCA（2）把下列一般树转换为二叉树12435678①②ABFEGHIJCD124688D537ABCHDDFGEIJ解：①②文案大全 实用标准文档（5）把下列森林转换为二叉树ACBDEFGKIJH①②③KABCHDDFGEIJ解：文案大全 实用标准文档（6）把下列二叉树还原为森林ADBICHFGE解：还原后的二叉树为：ABCHDDFGEI①②③（7）某二叉树的结点数据采用顺序存储，其结构如下：1234567891011121314151617181920EAFDHCGIB①画出该二叉树（3分）②写出按层次遍历的结点序列（2分）解：ADHFGECBI文案大全 实用标准文档层次遍历的结点序列：EAFDHCGIB（8）某二叉树的存储如下：12345678910lchild00237580101dataJHFDBACEGIrchild0009400000其中根结点的指针为6，lchild、rchild分别为结点的左、右孩子的指针域，data为数据域。①画出该二叉树（3分）②写出该树的前序遍历的结点序列（2分）解：BDJHGACFEI文案大全 实用标准文档前序遍历的结点序列：ABCEDFHGIJ（9）给定如图所示二叉树T，请画出与其对应的中序线索二叉树。330828D25D33D40D60D08D54D55D解：中序遍历序列：5540256028083354中序线索二叉树：NULLNULL0828D25D33D40D60D08D54D55D（10）画出表达式：-A+B-C+D的标识符树，并求它们的后缀表达式。解：文案大全 实用标准文档+¯+¯BDCAD0后缀表达式：0A–B+C–D+（11）画出表达式：（A+B/C-D）*（E*（F+G））的标识符树，并求它们的后缀表达式。ABC+DDFGE/+*¯*解：后缀表达式：ABC/+D–EFG+**文案大全 实用标准文档（12）对于算术表达式（A+B*C/D）*E+F*G，画出标识符树，并求它们的后缀表达式。解：*EGFD*B++*AD/C后缀表达式：ABCD/*+E*FG*+（13）给定一个权集W={4,5,7,8,6,12,18}，试画出相应的哈夫曼树，并计算其带权路径长度WPL。351325D12660181798D457解：456781218913172535文案大全 实用标准文档60WPL=(12+18)*2+(6+7+8)*3+(4+5)*4=159（14）给定一个权集W={3,15,17,14,6,16,9,2}，试画出相应的哈夫曼树，并计算其带权路径长度WPL。491733D1698229201514D56113D2解：2369141516175293311204982WPL=(16+17)*2+(9+14+15)*3+6*4+(2+3)*5=229（15）假设用于通信的电文仅由A、B、C、D、E、F、G8个字母组成，字母在电文中出现的频率分别为7，19，2，6，32，3，21，10。试为这8个字母设计哈夫曼编码。解：以权值：2、3、6、7、10、19、21、32构造哈夫曼树：（左子为0，右子为1。）651911281740D213260D10000D023D710D0000011111101字母编号对应编码出现频率A10107B0019C100002D10016E1132D100013E0121F101110文案大全 实用标准文档六．算法设计题以二叉链表为存储结构，设二叉树BT结构为：typedefstructBT{chardata;BT*lchild;BT*rchild;}BT;（1）求二叉树中的度数为2的结点。解：voidcount(BTt){if(t){if(t->lchild&&t->rchild)k++;count(t->lchild);count(t->rchild);}}（2）求二叉树中值为最大的元素。解：intmaxnode(BTt,intmax){if(t){if(t->data>max)max=t->data;max=maxnode(t->lchild,max);文案大全 实用标准文档max=maxnode(t->rchild,max);}}（1）将二叉树各结点存储到一维数组中。解：voidcreate(BTt,inta[],inti){if(t){a[i]=t->data;create(t->lchild,a,2*i);create(t->rchild,a,2*i+1);}}（2）前序输出二叉树中各结点及其结点所在的层号。解：voidpreorderlevel(BTt,inth)//t的层数为h{if(t!=NULL){printf(“%d,%d”,t->data,h);preorderlevel(t->lchild,h+1);preorderlevel(t->rchild,h+1);}}（3）求二叉树的宽度解：//思想：按层遍历二叉树，采用一个队列q，让根结点入队列，最后出队列，若有左右子树，则左右子树根结点入队列，如此反复，直到队列为空。intWidth(BT*T){intfront=-1,rear=-1;//队列初始化intflag=0,count=0,p;文案大全 实用标准文档//p用于指向树中层的最右边的结点，标志flag记录层中结点数的最大值if(T!=NULL){rear++;q[rear]=T;flag=1;p=rear;}while(frontlchild!=NULL){rear++;q[rear]=T->lchild;count++;}if(T->rchild!=NULL){rear++;q[rear]=T->rchild;count++;}if(front==p)//当前层已遍历完毕{if(flag-1){T=stack[top];top--;if(T->child!=NULL||T->rchild!=NULL){//交换结点的左右指针temp=T->lchild;T->lchild=T->rchild;T->rchild=temp;}if(T->lchild!=NULL){top++;stack[top]=T->lchild;}if(T->rchild!=NULL){top++;stack[top]=T->rchild;文案大全 实用标准文档}}}}voidmain(){intI,j,k,l;printf(“ ”);root=CreateBinTree();Inorder(root);i=CountNode(root);j=CountLeafs(root);k=Depth(root);l=Width(root);printf(“ TheNode’sNumber:%d”,i);printf(“ TheLeafs’sNumber:%d”,j);printf(“ TheDepthis:%d”,k);printf(“ Thewidthis:%d”,l);Swap(root);Printf(“ TheswapTreeis:”);Inorder(root);}（7）写出在二叉树中查找值为x的结点在树中层数的算法。解：inth=-1,lh=1,count=0;charx=’c’;//赋初值Level(BinTreeT,inth,intlh)//求X结点在树只的层树{if(T==Null)h=0;else文案大全 实用标准文档if(T->data==x){h=lh;count=h;}else{h++;Level(T->lchild,h,lh);if(h==-1)Level(T->rchild,h,lh);}}voidmain(){BinTree*(*newroot);Printf(“ ”);Root=CreateBinTree();Inorder(root);Printf(“ ”);Level(root,h,lh);Printf(“%d”,count);}文案大全 实用标准文档单元练习8一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳）（√）（1）图可以没有边，但不能没有顶点。（ㄨ）（2）在无向图中，（V1，V2）与（V2，V1）是两条不同的边。（ㄨ）（3）邻接表只能用于有向图的存储。（√）（4）一个图的邻接矩阵表示是唯一的。（ㄨ）（5）用邻接矩阵法存储一个图时，所占用的存储空间大小与图中顶点个数无关，而只与图的边数有关。（ㄨ）（6）有向图不能进行广度优先遍历。（√）（7）若一个无向图的以顶点V1为起点进行深度优先遍历，所得的遍历序列唯一，则可以唯一确定该图。（√）（8）存储无向图的邻接矩阵是对称的，因此只要存储邻接矩阵的上三角（或下三角）部分就可以了。（ㄨ）（9）用邻接表法存储图时，占用的存储空间大小只与图中的边数有关，而与结点的个数无关。（√）（10）若一个无向图中任一顶点出发，进行一次深度优先遍历，就可以访问图中所有的顶点，则该图一定是连通的。二．填空题（1）图常用的存储方式有邻接矩阵和邻接表等。（2）图的遍历有：深度优先搜和广度优先搜等方法。（3）有n条边的无向图邻接矩阵中，1的个数是_2n____。（4）有向图的边也称为_弧___。（5）图的邻接矩阵表示法是表示__顶点____之间相邻关系的矩阵。（6）有向图G用邻接矩阵存储，其第i行的所有元素之和等于顶点i的__出度____。（7）n个顶点e条边的图若采用邻接矩阵存储，则空间复杂度为：O（n2）。文案大全 实用标准文档（1）n个顶点e条边的图若采用邻接表存储，则空间复杂度为：O（n+e）。（2）设有一稀疏图G，则G采用_邻接表____存储比较节省空间。（3）设有一稠密图G，则G采用_邻接矩阵____存储比较节省空间。（4）图的逆邻接表存储结构只适用于__有向____图。（5）n个顶点的完全无向图有n(n-1)/2_条边。（6）有向图的邻接表表示适于求顶点的出度。（7）有向图的邻接矩阵表示中，第i列上非0元素的个数为顶点Vi的入度。（8）对于具有n个顶点的图，其生成树有且仅有n-1条边。（9）对n个顶点，e条弧的有向图，其邻接表表示中，需要n+e个结点。（10）从图中某一顶点出发，访遍图中其余顶点，且使每一顶点仅被访问一次，称这一过程为图的遍历。（11）无向图的邻接矩阵一定是对称矩阵。（12）一个连通网的最小生成树是该图所有生成树中权最小的生成树。（13）若要求一个稠密图G的最小生成树，最好用Prim算法来求解。三．选择题（1）在一个图中，所有顶点的度数之和等于图的边数的(C)倍。A．1/2B.1C.2D.4（2）在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的(B)倍。A．1/2B.1C.2D.4（3）对于一个具有n个顶点的有向图的边数最多有（B）。A．nB．n(n-1)C．n(n-1)/2D．2n（4）在一个具有n个顶点的无向图中，要连通全部顶点至少需要（C）条边。A．nB．n+1C．n-1D．n/2（5）有8个结点的有向完全图有(C)条边。A．14B.28C.56D.112文案大全 实用标准文档（6）深度优先遍历类似于二叉树的(A)。A．先序遍历B．中序遍历C．后序遍历D．层次遍历（7）广度优先遍历类似于二叉树的(D)。A．先序遍历B．中序遍历C．后序遍历D．层次遍历（8）任何一个无向连通图的最小生成树(A)。A．只有一棵B．一棵或多棵C．一定有多棵D．可能不存在（9）无向图顶点v的度是关联于该顶点（B）的数目。A．顶点B．边C．序号D．下标（10）有n个顶点的无向图的邻接矩阵是用（B）数组存储。A．一维B．n行n列C．任意行n列D．n行任意列（11）对于一个具有n个顶点和e条边的无向图，采用邻接表表示，则表头向量大小为（C）。A．n-1B．n+1C．nD．n+e（12）在图的表示法中，表示形式唯一的是（A）。A．邻接矩阵表示法B．邻接表表示法C．逆邻接表表示法D．邻接表和逆邻接表表示法（13）在一个具有n个顶点e条边的图中，所有顶点的度数之和等于（C）。A．nB．eC．2nD．2e（14）下图中，度为3的结点是（B）。12354文案大全 实用标准文档A．V1B.V2C.V3D.V412354（15）下图是（A）。A．连通图B.强连通图C.生成树D.无环图（16）如下图所示，从顶点a出发，按深度优先进行遍历，则可能得到的一种顶点序列为（D）。abcfdeA．a，b，e，c，d，fB．a，c，f，e，b，dC.a，e，b，c，f，dD.a，e，d，f，c，b（17）如下图所示，从顶点a出发，按广度优先进行遍历，则可能得到的一种顶点序列为（A）。abcfdeA.a，b，e，c，d，fB.a，b，e，c，f，dC.a，e，b，c，f，dD.a，e，d，f，c，b文案大全 实用标准文档（18）最小生成树的构造可使用（A）算法。A．prim算法B．卡尔算法C．哈夫曼算法D．迪杰斯特拉算法（19）下面关于图的存储结构的叙述中正确的是（A）。A．用邻接矩阵存储图，占用空间大小只与图中顶点数有关，而与边数无关B．用邻接矩阵存储图，占用空间大小只与图中边数有关，而与顶点数无关C．用邻接表存储图，占用空间大小只与图中顶点数有关，而与边数无关D．用邻接表存储图，占用空间大小只与图中边数有关，而与顶点数无关（20）连通分量是（C）的极大连通子图。A．树B．图C．无向图D．有向图四．应用题（1）有向图如下图所示，画出邻接矩阵和邻接表①②②②②③②②②④②②②⑤②②②解：邻接矩阵12345文案大全 实用标准文档邻接表1235∧24∧35∧41∧54∧（2）已知一个无向图有6个结点，9条边，这9条边依次为(0,1)，(0,2)，(0,4)，(0,5)，(1,2)，(2,3)，(2,4)，(3,4)，(4,5)。试画出该无向图，并从顶点0出发，分别写出按深度优先搜索和按广度优先搜索进行遍历的结点序列。解：231D045从顶点0出发的深度优先搜索遍历的结点序列：012345（答案不唯一）从顶点0出发的广度优先搜索遍历的结点序列：012453（答案不唯一）文案大全 实用标准文档（3）已知一个无向图的顶点集为：{a，b，c，d，e}，其邻接矩阵如下，画出草图，写出顶点a出发按深度优先搜索进行遍历的结点序列。解：acbed①②深度优先搜索：abdce（答案不唯一）广度优先搜索：abedc（答案不唯一）（4）网G的邻接矩阵如下，试画出该图，并画出它的一棵最小生成树。2543125431解：最小生成树：81110834137347文案大全 实用标准文档（5）已知某图G的邻接矩阵如图，①画出相应的图；②要使此图为完全图需要增加几条边。解：①134242D31②完全无向图应具有的边数为：n*(n-1)1/2=4*(4-1)/2=6，所以还要增加2条边（如右图）。（6）已知如图所示的有向图，请给出该图的:①每个顶点的入/出度；②邻接表；③邻接矩阵。文案大全 实用标准文档解：①②顶点123456入度321122出度022313③（7）如图，请完成以下操作：①写出无向带权图的邻接矩阵；②设起点为a，求其最小生成树。解：①邻接矩阵为：②起点为a，可以直接由原始图画出最小生成树文案大全 实用标准文档（8）给定下列网G:①画出网G的邻接矩阵；②画出网G的最小生成树。解：①邻接矩阵②最小生成树FBEDACGD五．程序题填空题图G为有向无权图，试在邻接矩阵存储结构上实现删除一条边(v,w)的操作：DeleteArc(G,v,w)。若无顶点v或w，返回“ERROR”；若成功删除，则边数减1，并文案大全 实用标准文档返回“OK”。（提示：删除一条边的操作，可以将邻接矩阵的第i行全部置0）StatusDeleteArc(MGraph&G,charv,charw)//在邻接矩阵表示的图G上删除边(v,w){if((i=LocateVex(G,v))<0)returnERROR;if((j=LocateVex(G,w))<0)returnERROR;if(G.arcs[i][j].adj){G.arcs[i][j].adj=0;G.arcnum--;（或G.arcnum=G.arcnum-1）}returnOK;}五．算法题（1）编写一个无向图的邻接矩阵转换成邻接表的算法。解：//本题思想是逐个扫描邻接矩阵的各个元素，若第i行第j列的元素为1，则相应的邻接表的第i个单链表上增加一个j结点。voidtrans(intedges[n][n],Adjlistadj){inti,j;edgenode*p;for(i=0;iadjvex=j;p->next=adj[i].link;adj[i].link=p;}}}（2）以知有n个顶点的有向图邻接表，设计算法分别实现以下功能：①求出图G中每个顶点的出度、入度。②求出G中出度最大的一个顶点，输出其顶点序号。③计算图中度为0的顶点数。解：①//求出度的思想：计算出邻接表中第i个单链表的结点数即可。intoutdegree(adjlistadj,intv){intdegree=0;edgenode*p;p=adj[v].link;while(p!=NULL){degree++;p=p->next;}returndegree;}voidprintout(adjlistadj,intn){inti,degree;printf("TheOutdegreeare: ");for(i=0;iadjvex==v)degree++;p=p->next;}}returndegree;}voidprintin(adjlistadj,intn){inti,degree;printf("TheIndegreeare: ");for(i=0;imaxdegree){maxdegree=degree;maxv=i;}}printf("maxoutdegree%d,maxvertex=%d",maxdegree,maxv);}①求度为0的顶点数的算法intoutzero(adjlistadj,intn){intnum=0,i;for(i=0;ip->key)p=p->link;elseif(x==p->key)returnp;else{p=NULL;returnp;}}}2．试设计一个在用开放地址法解决从突的散列表上删除一个指定结点的算法。解：//算法思想是：首先计算要删除的关键字为k的记录所在的位置，将其置为空(即删除)，然后利用线性探测法查找是否有与k发生冲突而存储到下一地址的记录，如果有则将记录移到原来k所在的位置，直至表中没有与k冲突的记录为止。实现本题功能的算法如下：voiddelete(sqlistr，intn，intk)文案大全 实用标准文档{inth,h0,h1;h=k%n;while(r[h].key!=k)h=(h+1)％n;r[h]=NULL;h0=h;hl=(h+1)％n;while(hl!=h){while(r[h1].key％n!=h)hl=(hl+1)％n;r[h0]=r[h1];r[h1]=NULL;h0=h1;h1=(hl+1)％n;}}3．设给定的散列表存储空间为H[1-m]，每个单元可存放一个记录，H[i]的初始值为零，选取散列函数为H(R.key)，其中key为记录R的关键字，解决冲突的方法为线性控测法，编写一个函数将某记录R填入到散列表H中。解：//本题的算法思想：先计算地址H(R.key)，如果没有冲突，则直接填入;否则利用线性探测法求出下一地址，直到找到一个为零的地址，然后填入。实现本题功能的函数如下：voidinsert(recordH,intm,recordR){inti;i=H(R.key);if(H[i]==NULL)H[i]=R;else{文案大全 实用标准文档while(H[i]!=NULL)i=(i+1)%(m+1);H[i]=R;}}文案大全 实用标准文档单元练习10一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳）（ㄨ）（1）如果某种排序算法不稳定，则该排序方法就没有实用价值。（√）（2）希尔排序是不稳定的排序。（ㄨ）（3）冒泡排序是不稳定的排序。（√）（4）对n个记录的进行快速排序，所需要的平均时间是O(nlog2n)。（ㄨ）（5）堆排序所需的时间与待排序的记录个数无关。（√）（6）当待排序的元素个数很多时，为了交换元素的位置要占用较多的时间，这是影响时间复杂度的主要因素。（ㄨ）（7）快速排序在任何情况下都比其它排序方法速度快。（√）（8）对快速排序来说，初始序列为正序或反序都是最坏情况。（√）（9）采用归并排序可以实现外排序。（√）（10）采用希尔方法排序时，若关键字的排列杂乱无序，则效率最高。（√）（11）快速排序算法在每一趟排序中都能找到一个元素放在其最终位置上。（√）（12）冒泡排序的时间复杂度是O（n2）。二．填空题（1）大多数排序算法都有两个基本的操作：比较和移动。（2）评价排序算法优劣的主要标准是时间复杂度和算法所需的附加空间。（3）根据被处理的数据在计算机中使用不同的存储设备，排序可分为：内排序和外排序。（4）外排序是指在排序过程中，数据的主要部分存放在计算机的外存中。（5）对n个关键字进行冒泡排序，其可能的最小比较次数为：n-1次。（6）在最坏情况下，在第i趟直接插入排序中，要进行i-1次关键字的比较。（7）对n个关键字进行冒泡排序，时间复杂度为O(n2)。文案大全 实用标准文档（1）快速排序在最坏情况下的时间复杂度是O(n2)。（2）对于n个记录的集合进行归并排序，所需要的平均时间为：O(log2n)。（3）对于n个记录的集合进行归并排序，所需要的附加空间是O(n)。（4）若原始数据接近无序，则选用快速排序最好。（5）在排序前，关键字值相等的不同记录，排序后相对位置保持不变的排序方法，称为稳定排序方法。（6）在插入排序和选择排序中，若初始数据基本正序，则选用插入排序较好。（7）当增量为1时，该趟希尔排序与直接插入排序基本一致。（8）第一趟排序后，序列中键值最大的记录交换到最后的排序算法是冒泡排序。（9）依次将每个记录插入到一个有序的子文件中的排序方法称为直接插入排序。（10）在插入排序、选择排序和归并排序中，排序是不稳定的为：选择排序。（11）在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需比较3次。（12）两个序列分别为：L1={25，57，48，37，92，86，12，33}L2={25，37，33，12，48，57，86，92}。用冒泡排序法对L1和L2进行排序，交换次数较少的是序列：L2。（20）对一组记录（54，35，96，21，12，72，60，44，80）进行直接选择排序时，第四次选择和交换后，未排序记录是54，72，60，96，80。三．选择题（1）排序是根据（A）的大小重新安排各元素的顺序。A．关键字B．数组C．元素件D．结点（2）评价排序算法好坏的标准主要是（D）。A．执行时间B．辅助空间C．算法本身的复杂度D．执行时间和所需的辅助空间（3）直接插入排序的方法是（B）的排序方法。A．不稳定B．稳定C．外部D．选择文案大全 实用标准文档（4）直接插入排序的方法要求被排序的数据（B）存储。A．必须链表B．必须顺序C．顺序或链表D．可以任意（5）排序方法中，从无序序列中选择关键字最小的记录，将其与无序区（初始为空）的第一个记录交换的排序方法，称为(D)。A．希尔排序B．归并排序C．插入排序D.选择排序（6）每次把待排序方的区间划分为左、右两个区间，其中左区间中元素的值不大于基准元素的值，右区间中元素的值不小于基准元素的值，此种排序方法叫做（C）。A．冒泡排序B．堆排序C．快速排序D.归并排序（7）快速排序在（C）情况下最易发挥其长处。A．待排序的数据中含有多个相同的关键字B．待排序的数据已基本有序C．待排序的数据完全无序D．待排序的数据中最大值与最小值相差悬殊（8）下述几种排序方法中，要求内存量最大的是：（D）。A．插入排序B．选择排序C．快速排序D.归并排序（9）直接插入排序的方法是从第（B）个元素开始，插入到前边适当位置的排序方法。A．1B．2C．3D．n（10）堆的形状是一棵（C）。A．二叉排序树B．满二叉树C．完全二叉树D．平衡二叉树（11）内排序是指在排序的整个过程中，全部数据都在计算机的（A）中完成的排序。A．内存B．外存C．内存和外存D．寄存器（12）快速排序的方法是（A）的排序方法。A．不稳定B．稳定C．外部D．选择（13）下列排序方法中，关键字比较次数与记录的初始排列次序无关的是（A）。A．选择排序B．希尔排序C．插入排序D．冒泡排序（14）下述几种排序方法中，平均时间复杂度最小的是（A）。A．希尔排序B．插入排序C．冒泡排序D．选择排序（15）对有n个记录的表作快速排序，在最坏情况下，算法的时间复杂度是（B）。A．O(n)B．O(n2)C．O(nlog2n)D．O(n3)文案大全 实用标准文档（16）冒泡排序的方法对n个数据进行排序，第一趟排序共需要比较（C）次。A．1B．2C．n-1D．n（17）对ｎ个不同的排序码进行冒泡（递增）排序，在下列（B）情况比较的次数最多。A．从小到大排列好的B．从大到小排列好的C．元素无序D．元素基本有序（18）用直接插入排序法对下面的四个序列进行由小到大的排序，元素比较次数最少的是（B）。A，94，32，40，90，80，46，21，69B．21，32，46，40，80，69，90，94C．32，40，21，46，69，94，90，80D．90，69，80，46，21，32，94，40（19）一组记录的排序码为(25，48，16，35，79，82，23，40)，其中含有4个长度为2的有序表，按归并排序的方法对该序列进行一趟归并后的结果为：（A）。A，16253548234079823672B．16253548798223364072C．16254835798223364072D．16253548792336407282（20）一个数据序列的关键字为：（46，79，56，38，40，84），采用快速排序，并以第一个数为基准得到第一次划分的结果为：（C）A．（38，40，46，56，79，84）B．（40，38，46，79，56，84）C．（40，38，46，56，79，84）D．（40，38，46，79，56，84）四．排序过程分析（1）已知数据序列{10，8，18，15，7，16}，写出采用直接插入算法排序时，每一趟排序的结果。解：1081815716第一趟结束时结果：[810]1815716第二趟结束时结果：[81018]15716第三趟结束时结果：[8101518]716第四趟结束时结果：[78101518]16第五趟结束时结果：[7810151618]（2）已知数据序列{18，17，60，40，07，32，73，65}，写出采用直接插入算法排序时，每一趟排序的结果。解：1817604007327365文案大全 实用标准文档第一趟结束时结果：[1718]604007327365第二趟结束时结果：[171860]4007327365第三趟结束时结果：[17184060]07327365第四趟结束时结果：[0717184060]327365第五趟结束时结果：[071718324060]7365第六趟结束时结果：[07171832406073]65第七趟结束时结果：[0717183240606573]（3）已知数据序列{17，18，60，40，7，32，73，65，85}请写出采用冒泡排序法对该序列作升序排序时每一趟的结果。解：17186040732736585第一趟排序结果：17184073260657385第二趟排序结果：171873240606573第三趟排序结果：1771832406065第四趟排序结果：71718324060第五趟排序结果：717183240第五趟排序过程中已无记录交换，排序结束。（4）已知数据序列{80，18，9，90，27，75，42，69，34}请写出采用冒泡排序法对该序列作升序排序时每一趟的结果。解：801809902775426934第一趟排序结果：180980277542693490第二趟排序结果：0918277542693480第三趟排序结果：09182742693475第四趟排序结果：091827423469第五趟排序结果：0918273440第六趟排序结果：09182734第六趟排序过程中已无记录交换，排序结束。（5）已知数据序列{10，18，4，3，6，12，9，15，8}，写出希尔排序每一趟排序的结果。（设d=5、2、1）解：1018436129158文案大全 实用标准文档d=56124381891510d=24361281591810d=13468910121518（6）已知数据序列{12，02，16，30，28，10，17，20，06，18}，写出希尔排序每一趟排序的结果。（设d=5、2、1）解：12021630281017200618d=510021606181217203028d=212021606171218203028d=102061012161718202830（7）已知数据序列{10，18，4，3，6，12，9，15}，写出二路归并排序的每一趟排序结果。[10][18][4][3][6][12][9][15][1018][34][612][915]第一趟排序结果[341018][691215]第二趟排序结果[346910121518]第三趟排序结果（8）已知数据序列{53，36，48，36，60，7，18，41}，写出采用简单选择排序的每一趟排序结果。解：[533648366071841]（7）[36483660531841]（718）[483660533641]文案大全 实用标准文档（71836）[4860533641]（7183636）[60534841]（718363641）[534860]（71836364148）[5360]（7183636414853）[60]（718363641485360）（9）已知数据序列{10，1，15，18，7，15}，试画出采用快速排序法，第一趟排序的结果。解：1011518715lowhigh交换711518[10]15lowhigh交换第一趟排序结果：71[10]181515lowhigh（10）已知数据序列{10，1，15，18，7，15}，试写出采用快速排序法，第一趟排序的结果。解：7110181515五．程序填空voidBInsSort()//按递增序对R[1]~R[n]进行二分插入排序{inti,j,low,high,m;for(i=2;i<=n;i++){R[0]=R[i];//设定R[0]为监视哨low=1;high=n；文案大全 实用标准文档while(low<=high){m=(low+high)/2;if(R[0]=high+1;j--)R[j+1]=R[j];//元素后移R[high]=R[0];//插入}}六．算法题1．以单链表为存储结构，写一个直接选择排序算法。解：voidselectsort(pointerh){pointerp,q,r,s,t;t=NULL;while(h){p=h;q=NULL;s=h;r=NULL;while(p){if(p->keykey){s=p;p=q;}if(s==h)h=h->link;elseh=s;文案大全 实用标准文档s->link=t;t=s;}h=t;}}2．以单链表作为存储结构实现直接插入排序算法。解：voidInsertList(Listhead){Lnode*p,*pprev,q,*qprev,*current;if(!head)return;pprev=head;p=head->next;while(p){q=head;qprev=NULL;while(q->keykey)//查找插入位置{qprev=q;q=q->next;}if(q==p)//p最大，无须插入{pprev=p;p=p->next;}else{current=p;p=p->next;pprev->next=p;current->next=q;if(q==head)//插在表头head=current;else//插在中间某个位置上qprev->next=current;文案大全 实用标准文档}}}3．设计一个算法，使得在尽可能少的时间内重排数组，将所有取负值的关键字放在所有取非负值的关键字之前。解：voidpart(inta[]){i=1;j=n;//初、终下标while(i=0)//自右向左找非负数j--;while(ikey=x;s->next=NULL;if(head==NULL)文案大全 实用标准文档head=s;else{p=head;q=NULL;while((p!=NULL)&&(s->key>p->key)){q=p;p=p->next;}if(q==NULL){s->next=head;head=s;}else{if(p==NULL)q->next=s;else{s->next=q->next;q->next=s;}}}}文案大全