电大数据结构(本)形成性考核册(作业4)（34页）

数据结构（本）形成性考核作业册使用说明本作业册是中央广播电视大学计算机科与技术专业（本科）数据结构（本）课程形成性考核的依据，与《数据结构（本科）》（李伟生主编，中央电大出版社出版）配套使用。数据结构（本）课程是中央广播电视大学计算机科学技术专业的一门统设必修、学位课程，4学分，共72学时。其中实验24学时，开设一学期。本课程的特点是综合性、实践性强，内容抽象，在专业中具有承上启下的作用。因此，在学习本课程时，要注意理论联系实际，结合教学内容进行上机实践，认真完成作业和实验内容。本课程的总成绩按百分制记分，其中形成性考核所占的比例为30%，终结性考试占70％（闭卷，答题时限为90分钟）。课程总成绩达到60分及以上者为合格，可以获得该课程的学分。本课程的学位课程学分为70分，即课程总成绩达到70分及以上者有资格申请专业学位。本课程共设计了4次形考作业，每次形考作业均包括实验内容，由各地电大根据学生对作业中各种题型练习和实验的完成情况进行考核。对于实验内容要求按实验要求认真完成，并提交实验报告。数据结构（本）课程作业作业1（本部分作业覆盖教材第1-2章的内容）一、单项选择题1．在数据结构中，从逻辑上可以把数据结构分为（）。A．动态结构和静态结构B．紧凑结构和非紧凑结构C．线性结构和非线性结构D．内部结构和外部机构2．下列说法中，不正确的是（）。A．数据元素是数据的基本单位B．数据项是数据中不可分割的最小可标识单位C．数据可有若干个数据元素构成D．数据项可由若干个数据元素构成3．一个存储结点存储一个（）。A．数据项B．数据元素C．数据结构D．数据类型4．数据结构中，与所使用的计算机无关的是数据的（）。A．存储结构B．物理结构C．逻辑结构D．物理和存储结构5．下列的叙述中，不属于算法特性的是（）。A．有穷性B．输入性C．可行性D．可读性6．算法分析的目的是（）。A．找出数据结构的合理性B．研究算法中的输入和输出的关系C．分析算法的效率以求改进D．分析算法的易懂性和文档性7．数据结构是一门研究计算机中（  ）对象及其关系的科学。A．数值运算         B．非数值运算C．集合             D．非集合8．算法的时间复杂度与（）有关。A．所使用的计算机B．与计算机的操作系统C．与算法本身D．与数据结构9．设有一个长度为n的顺序，要在第i个元素之前（也就是插入元素作为新表的第i个元素），则移动元素个数为（）。A．n-i+1B．n-iC．n-i-1D．i10．设有一个长度为n的顺序表，要删除第i个元素移动元素的个数为（）。A．n-i+1B．n-iC．n-i-1D．i11．在一个单链表中，p、q分别指向表中两个相邻的结点，且q所指结点是p所指结点的直接后继，现要删除q所指结点，可用语句（）。A．p=q->nextB．p->next=qC．p->next=q(nextD．q->next=NULL12．在一个单链表中p所指结点之后插入一个s所指的结点时，可执行（）。A．p->next=s;s(next=p(nextB．p->next=s(next;C．p=s->nextD．s->next=p->next;p->next=s;13．非空的单向循环链表的尾结点满足（   ）（设头指针为head，指针p指向尾结点）。A.．P->next==NULLB．P==NULLC．P->next==headD．P==head14．链表不具有的特点是（）。A．可随机访问任一元素B．插入删除不需要移动元素C．不必事先估计存储空间D．所需空间与线性表长度成正比15．带头结点的链表为空的判断条件是（    ）（设头指针为head）。　　　　A．head==NULL　　　　B．head->next==NULL 　　　　C．head->next==head 　　D．head!=NULL　　16．在一个单链表中，p、q分别指向表中两个相邻的结点，且q所指结点是p所指结点的直接后继，现要删除q所指结点，可用语句（  ）。　　　　A．p=q->next　　　　B．p->next=q 　　　　C．p->next=q->next　　　　D．q->next=NULL17．在一个链队中，假设f和r分别为队头和队尾指针，则删除一个结点的运算为（）。A．r=f->next;B．r=r->next;C．f=f->next;D．f=r->next;18．在一个链队中，假设f和r分别为队头和队尾指针，则插入s所指结点的运算为（）。A．f->next=s;f=s;B．r->next=s;r=s;C．s->next=r;r=s;D．s->next=f;f=s;19.一个顺序表第一个元素的存储地址是90，每个元素的长度为2，则第6个元素的地址是（）。A．98B．100C．102D．10620．有关线性表的正确说法是（）。A．每个元素都有一个直接前驱和一个直接后继B．线性表至少要求一个元素C．表中的元素必须按由小到大或由大到下排序D．除了一个和最后一个元素外，其余元素都有一个且仅有一个直接前驱和一个直接后继二、填空题1．在一个长度为n的顺序存储结构的线性表中，向第i(1(i(n+1)个元素之前插入新元素时，需向后移动个数据元素。2．从长度为n的采用顺序存储结构的线性表中删除第i(1(i(n+1)个元素，需向前移动个元素。3．数据结构按结点间的关系，可分为4种逻辑结构：、、、。4．数据的逻辑结构在计算机中的表示称为或。5．除了第1个和最后一个结点外，其余结点有且只有一个前驱结点和后继结点的数据结构为，每个结点可有任意多个前驱和后继结点数的结构为。6．算法的5个重要特性是、、、、。7．数据结构中的数据元素存在多对多的关系称为________结构。8．数据结构中的数据元素存在一对多的关系称为________结构。9．数据结构中的数据元素存在一对一的关系称为________结构。10．要求在n个数据元素中找其中值最大的元素，设基本操作为元素间的比较。则比较的次数和算法的时间复杂度分别为________和________。11．在一个单链表中p所指结点之后插入一个s所指结点时，应执行________和p->next=s;的操作。12．设有一个头指针为head的单向循环链表，p指向链表中的结点，若p->next==________，则p所指结点为尾结点。13．在一个单向链表中，要删除p所指结点，已知q指向p所指结点的前驱结点。则可以用操作________。14．设有一个头指针为head的单向链表，p指向表中某一个结点，且有p->next==NULL,通过操作________,就可使该单向链表构造成单向循环链表。15．每个结点只包含一个指针域的线性表叫。16．线性表具有和两种存储结构。17．数据的逻辑结构是从逻辑关系上描述数据，它与数据的关系无关，是独立于计算机的。18．在双向循环链表的每个结点中包含指针域，其中next指向它的，prior指向它的，而头结点的prior指向，尾结点的next指向。19．单向循环链表是单向链表的一种扩充，当单向链表带有头结点时，把单向链表中尾结点的指针域由空指针改为；当单向链表不带头结点时，则把单向链表中尾结点的指针域由空指针改为指向。20．线性链表的逻辑关系时通过每个结点指针域中的指针来表示的。其逻辑顺序和物理存储顺序不再一致，而是一种存储结构，又称为。三、问答题1．简述数据的逻辑结构和存储结构的区别与联系，它们如何影响算法的设计与实现？2．解释顺序存储结构和链式存储结构的特点，并比较顺序存储结构和链式存储结构的优缺点。3．什么情况下用顺序表比链表好？4．头指针、头结点、第一个结点（或称首元结点）的区别是什么？5．解释带头结点的单链表和不带头结点的单链表的区别。四、程序填空题1．下列是用尾插法建立带头结点的且有n个结点的单向链表的算法，请在空格内填上适当的语句。NODE*create1(n)/*对线性表(1,2,.....,n),建立带头结点的单向链表*/{NODE*head,*p,*q;inti;p=(NODE*)malloc(sizeof(NODE));head=p;q=p;p->next=NULL;for(i=1;i<=n;i++){p=(NODE*)malloc(sizeof(NODE));（1）;（2）;（3）;（4）;}return(head);}2．下列是用头插法建立带头结点的且有n个结点的单向链表的算法，请在空格内填上适当的语句。NODE*create2(n)/*对线性表(n,n-1,.....,1),建立带头结点的线性链表*/{NODE*head,*p,*q;inti;p=(NODE*)malloc(sizeof(NODE));（1）;p->next=NULL;（2）;for(i=1;i<=n;i++){p=(NODE*)malloc(sizeof(NODE));p->data=i;if(i==1)（3）;else（4）;（5）;}return(head);}3．下列是在具有头结点单向列表中删除第i个结点，请在空格内填上适当的语句。intdelete(NODE*head,inti){NODE*p,*q;intj;q=head;j=0;while((q!=NULL)&&(j<i-1))/*找到要删除结点的直接前驱，并使q指向它*/{q=q->next;j++;}if(q==NULL)return(0);（1）;（2）;free(p);return(1);}五、完成：实验1――线性表根据实验要求（见教材P201-202）认真完成本实验，并提交实验报告。数据结构（本）课程作业2（本部分作业覆盖教材第3-5章的内容）一、单项选择题1．若让元素1，2，3依次进栈，则出栈顺序不可能为（）。A．3，2，1B．2，1，3C．3，1，2D．1，3，22．一个队列的入队序列是1，2，3，4。则队列的输出序列是（）。A．4，3，2，1B．1，2，3，4C．1，4，3，2D．3，2，4，13．向顺序栈中压入新元素时，应当（）。A．先移动栈顶指针，再存入元素B．先存入元素，再移动栈顶指针C．先后次序无关紧要D．同时进行4．在一个栈顶指针为top的链栈中，将一个p指针所指的结点入栈，应执行（）。A．top->next=p;B．p->next=top->next;top->next=p;C．p->next=top;top=p;D．p->next=top->next;top=top->next;5．在一个栈顶指针为top的链栈中删除一个结点时，用x保存被删结点的值，则执行（）。A．x=top;top=top->next;B．x=top->data;C．top=top->next;x=top->data;D．x=top->data;top=top->next;6．一般情况下，将递归算法转换成等价的非递归算法应该设置（）。A．栈B．队列C．堆栈或队列D．数组7．表达式a*(b+c)-d的后缀表达式是（）。A．abcd*+-B．abc+*d-C．abc*++d-D．-+*abcd8．判断一个顺序队列sq（最多元素为m0）为空的条件是（）。A．sq->rear-sq->front==m0B．sq->rear-sq->front-1==m0C．sq->front==sq->rearD．sq->front==sq->rear+19．判断一个循环队列Q（最多元素为m0）为空的条件是（）。A．Q->front==Q->rearB．Q->front!=Q->rearC．Q->front==(Q->rear+1)%m0D．Q->front!=(Q->rear+1)%m010．判断一个循环队列Q（最多元素为m0）为空的条件是（）。A．Q->front==Q->rearB．Q->front!=Q->rearC．Q->front==(Q->rear+1)%m0D．Q->front!=(Q->rear+1)%m011．判断栈S满（元素个数最多n个）的条件是（）。A．s->top==0B．s->top!=0C．s->top==n-1D．s->top!=n-112．一个队列的入队顺序是a,b,c,d，则离队的顺序是（）。A．a,d,cbB．a,b,c,dC．d,c,b,aD．c,b,d,a13．如果以链表作为栈的存储结构，则退栈操作时（）。A．必须判断栈是否满B．判断栈元素类型C．必须判断栈是否空D．对栈不作任何判断14．在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入缓冲区中，而打印机则从缓冲区中取出数据打印，该缓冲区应该是一个（）结构。A．堆栈B．队列C．数组D．先性表15．一个递归算法必须包括（）。A．递归部分B．终止条件和递归部分C．迭代部分D．终止条件和迭代部分16．从一个栈顶指针为top的链栈中删除一个结点时，用变量x保存被删结点的值，则执行（）。A．x=top->data;top=top->next;B．x=top->data;C．top=top->next;x=top->data;D．top=top->next;x=data;17．在一个链队中，假设f和r分别为队头和队尾指针，则删除一个结点的运算为（）。A．r=f->next;B．r=r->next;C．f=f->next;D．f=r->next;18．在一个链队中，假设f和r分别为队头和队尾指针，则插入s所指结点的运算为（）。A．f->next=s;f=s;B．r->next=s;r=s;C．s->next=r;r=s;D．s->next=f;f=s;19.以下陈述中正确的是（）。A．串是一种特殊的线性表B．串的长度必须大于零C．串中元素只能是字母D．空串就是空白串20．设有两个串p和q，其中q是p的子串，q在p中首次出现的位置的算法称为（）。A．求子串B．连接C．匹配D．求串长21．串是（）。A．不少于一个字母的序列B．任意个字母的序列C．不少于一个字符的序列D．有限个字符的序列22．串的长度是指（）。A．串中所含不同字母的个数B．串中所含字符的个数C．串中所含不同字符的个数D．串中所含非空格字符的个数23.若串S==“English”，其子串的个数是（）。A．9B．16C．36D．2824．下面关于串的叙述中，不正确的是（）。A．串是字符的有限序列B．空串是由空格构成的串C．模式匹配是串的一种重要运算D．串即可以采用顺序存储，也可以采用链式存储25．串与普通的线性表相比较，它的特殊性体现在（）。A．顺序的存储结构B．链接的存储结构C．数据元素是一个字符D．数据元素可以任意26．空串与空格串（）。A．相同B．不相同C．可能相同D．无法确定27．两个字符串相等的条件是（）。A．两串的长度相等B．两串包含的字符相同C．两串的长度相等，并且两串包含的字符相同D．两串的长度相等，并且对应位置上的字符相同28．在实际应用中，要输入多个字符串，且长度无法预定。则应该采用（）存储比较合适（）。A．链式B．顺序C．堆结构D．无法确定29.一维数组A采用顺序存储结构，每个元素占用6个字节，第6个元素的存储地址为100，则该数组的首地址是（）。A．64B．28C．70D．9030．稀疏矩阵采用压缩存储的目的主要是（）。A．表达变得简单B．对矩阵元素的存取变得简单C．去掉矩阵中的多余元素D．减少不必要的存储空间的开销31．一个非空广义表的表头（）。A．不可能是原子B．只能是子表C．只能是原子D．可以是子表或原子32．常对数组进行的两种基本操作是（）。A．建立与删除B．索引与、和修改C．查找和修改D．查找与索引33.设二维数组A[5][6]按行优先顺序存储在内存中，已知A[0][0]起始地址为1000，每个数组元素占用5个存储单元，则元素A[4][4]的地址为（）。A．1140B．1145C．1120D．112534．设有一个20阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素a9,2在一维数组B中的下标是（）。A．41B．32C．18D．3835．一个非空广义表的表头（）。A．不可能是子表B．只能是子表C．只能是原子D．可以是子表或原子二、填空题1．栈是限定在表的一端进行插入和删除操作的线性表，又称为。2．队列的特性是。3．往栈中插入元素的操作方式是：先，后。4．删除栈中元素的操作方式是：先，后。5．循环队列队头指针在队尾指针位置，队列是“满”状态6．在队列的顺序存储结构中，当插入一个新的队列元素时，尾指针，当删除一个元素队列时，头指针。7．循环队列的引入，目的是为了克服。8．向顺序栈插入新元素分为三步：第一步进行判断，判断条件是；第二步是修改；第三步是把新元素赋给。同样从顺序栈删除元素分为三步：第一步进行判断，判断条件是。第二步是把；第三步。9．假设以S和X分别表示入栈和出栈操作，则对输入序列a,b,c,d,e一系列栈操作SSXSXSSXXX之后，得到的输出序列为。10．一个递归算法必须包括和。11．判断一个循环队列LU（最多元素为m0）为空的条件是。12．在将中缀表达式转换成后缀表达式和计算后缀表达式的算法中，都需要使用栈，对于前者，进入栈中的元素为表达式中的，而对于后者，进入栈的元素为，中缀表达式(a+b)/c-(f-d/c)所对应的后缀表达式是。16．向一个栈顶指针为h的链栈中插入一个s所指结点时，可执行________和h=s;操作。(结点的指针域为next)17．从一个栈顶指针为h的链栈中删除一个结点时，用x保存被删结点的值，可执行x=h->data;和________。(结点的指针域为next)18．在一个链队中，设f和r分别为队头和队尾指针，则插入s所指结点的操作为________和r=s;(结点的指针域为next)19．在一个链队中，设f和r分别为队头和队尾指针，则删除一个结点的操作为________。(结点的指针域为next)20．串是一种特殊的线性表，其特殊性表现在组成串的数据元素都是。21．串的两种最基本的存储方式是和。22．空串的长度是；空格串的长度是。23．需要压缩存储的矩阵可分为矩阵和矩阵两种。24．设广义表L=（（），（）），则表头是，表尾是，L的长度是。25．广义表A（（a,b,c）,(d,e,f)）的表尾为。26．两个串相等的充分必要条件是__________。27．设有n阶对称矩阵A，用数组s进行压缩存储，当i(j时，A的数组元素aij相应于数组s的数组元素的下标为_______。（数组元素的下标从1开始）28．对稀疏矩阵进行压缩存储，矩阵中每个非零元素对应的三元组包括该元素的_______、_______和_______三项信息。三、问答题1．简述栈和一般线性表的区别。2．简述队列和一般线性表的区别。3．链栈中为何不设头结点？4．利用一个栈，则：（1）如果输入序列由A，B，C组成，试给出全部可能的输出序列和不可能的输出序列。（2）如果输入序列由A，B，C，D组成，试给出全部可能的输出序列和不可能的输出序列。5．用S表示入栈操作，X表示出栈操作，若元素入栈顺序为1234，为了得到1342出栈顺序，相应的S和X操作串是什么？6．有5个元素，其入栈次序为：A、B、C、D、E，在各种可能的出栈次序中，以元素C、D最先的次序有哪几个？7．写出以下运算式的后缀算术运算式⑴3x2+x-1/x+5⑵(A+B)*C-D/(E+F)+G8．在什么情况下可以用递归解决问题？在写递归程序时应注意什么？9．简述广义表和线性表的区别和联系。四、程序填空题1．在下面空格处填写适当的语句，以使下面的循环队列的入队和出队算法完整。defineTRUE1;defineFALSE0;defineMAXSIZE100;typedefcharelemtype;typedefstruct{Elemtypequeue[MAXSIZE];intfront,rear;}sequeuetype;SequeuetypeQ;intencqueue(sequeuetype*Q,elemtypex)(if((1))(Printf(〝Thecicularqueueisfull!\n〞);return(FALSE);(else((2)(3)return(TRUE);(}/*encqueue*/elemtypedel_cqueue(sequeuetype*Q)(if((4))(Printf(〝Thequeueisempty!\n〞)return(NULL);(else((5)Return(Q-(queue[Q-＞front]);((/*del_cqueue*/2.在下面空格处填写适当的语句，以使下面的链式队列取出元素的算法完整。intwrite(LinkQueue*q){QueueNode*p;if(q->front==q->rear)　/*队空*/{printf(“underflow”);exit(0);}while(q->front->next!=NULL){p=q->front->next;(1)printf(“%4d”,p->data);(2)}（3）;　/*队空时，头尾指针指向头结点*/}五、综合题1．设栈S和队列Q的初始状态为空，元素e1,e2,e3,e4,e5和e6依次通过S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2,e4,e3,e6,e5,e1，则栈S的容量至少应该是多少？2．假设用循环单链表实现循环队列，该队列只使用一个尾指针rear，其相应的存储结构和基本算法如下；（1）初始化队列initqueue(Q):建立一个新的空队列Q。（2）入队列enqueue(Q,x):将元素x插入到队列Q中。（3）出队列delqueue(Q):从队列Q中退出一个元素。（4）取队首元素gethead(Q):返回当前队首元素。（5）判断队列是否为空：emptyqueue(Q)。（6）显示队列中元素：dispqueue(Q)。六、完成：实验2――栈、队列、递归程序设计根据实验要求（见教材P203）认真完成本实验，并提交实验报告。数据结构（本）课程作业作业3（本部分作业覆盖教材第6-7章的内容）一、单项选择题1.假定一棵二叉树中，双分支结点数为15，单分支结点数为30，则叶子结点数为（）。A．15B．16C．17D．472．二叉树第k层上最多有（）个结点。A．2kB．2k-1C．2k-1D．2k-13．二叉树的深度为k,则二叉树最多有（）个结点。A．2kB．2k-1C．2k-1D．2k-14.设某一二叉树先序遍历为abdec，中序遍历为dbeac，则该二叉树后序遍历的顺序是（）。A．abdecB．debacC．debcaD．abedc5．树最适合于用来表示（）。A．线性结构的数据B．顺序结构的数据C．元素之间无前驱和后继关系的数据D．元素之间有包含和层次关系的数据6．设a,b为一棵二叉树的两个结点，在后续遍历中，a在b前的条件是（）。A．a在b上方B．a在b下方C．a在b左方D．a在b右方7．权值为{1，2，6，8}的四个结点构成的哈夫曼树的带权路径长度是（）。A．18B．28C．19D．298．将含有150个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点的编号为1，则编号为69的结点的双亲结点的编号为（）。A．33B．34C．35D．369．如果将给定的一组数据作为叶子数值，所构造出的二叉树的带权路径长度最小，则该树称为（）。A．哈夫曼树B．平衡二叉树C．二叉树D．完全二叉树10．下列有关二叉树的说法正确的是（）。A．二叉树中度为0的结点的个数等于度为2的结点的个数加1B．二叉树中结点个数必大于0C．完全二叉树中，任何一个结点的度，或者为0或者为2D．二叉树的度是211．在一棵度为3的树中，度为3的结点个数为2，度为2的结点个数为1，则度为0的结点个数为（）。A．4B．5C．6D．712．在一棵度具有5层的满二叉树中结点总数为（）。A．31B．32C．33D．1613.利用n个值作为叶结点的权生成的哈夫曼树中共包含有()个结点。A.nB.n+1C.2*nD.2*n-114.利用n个值作为叶结点的权生成的哈夫曼树中共包含有()个双支结点。A.nB.n-1C.n+1D.2*n-115.利用3、6、8、12这四个值作为叶子结点的权，生成一棵哈夫曼树，该树中所有叶子的最长带权路径长度为()。A.18B.16C.12D.3016．在一棵树中，（）没有前驱结点。A．分支结点B．叶结点C．树根结点D．空结点17．在一棵二叉树中，若编号为i的结点存在右孩子，则右孩子的顺序编号为（）。A．2iB．2i-1D．2i+1C．2i+218．设一棵哈夫曼树共有n个叶结点，则该树有（）个非叶结点。A．nB．n-1C．n+1D．2n19．设一棵有n个叶结点的二叉树，除叶结点外每个结点度数都为2，则该树共有（）个结点。A．2nB．2n-1C．2n+1D．2n+220．一棵完全二叉树共有5层，且第5层上有六个结点，该树共有（）个结点。A．20B．21C．23D．3021．在一个图G中，所有顶点的度数之和等于所有边数之和的（）倍。A．1/2B．1C．2D．422．在一个有像图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。A．邻接矩阵表示法B．邻接表表示法C．逆邻接表表示法D．邻接表和逆邻接表23．在图的存储结构表示中，表示形式唯一的是（）。A．nB．n(1C．n(1D．n/224．一个具有n个顶点的无向完全图包含（）条边。A．n（n(1）B．n（n(1）C．n（n(1）/2D．n（n(1）/225．一个具有n个顶点的有向完全图包含（）条边。A．n（n(1）B．n（n(1）C．n（n(1）/2D．n（n(1）/226．对于具有n个顶点的图，若采用邻接矩阵表示，则该矩阵的大小为（）。A．nB．n2C．n(1D．（n(1）227．对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为（）。A．nB．eC．2nD．2e28．对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则所有顶点邻接表中的结点总数为（）。A．nB．eC．2nD．2e29．在有向图的邻接表中，每个顶点邻接表链接着该顶点所有（）邻接点。A．入边B．出边C．入边和出边D．不是入边也不是出边30．在有向图的逆邻接表中，每个顶点邻接表链接着该顶点所有（）邻接点。A．入边B．出边C．入边和出边D．不是入边也不是出边31．邻接表是图的一种（）。A．顺序存储结构B．链式存储结构C．索引存储结构D．散列存储结构32．如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是（）。A．完全图B．连通图C．有回路D．一棵树33．下列有关图遍历的说法不正确的是（）。A．连通图的深度优先搜索是一个递归过程B．图的广度优先搜索中邻接点的寻找具有“先进先出”的特征C．非连通图不能用深度优先搜索法D．图的遍历要求每一顶点仅被访问一次34．无向图的邻接矩阵是一个（）。A．对称矩阵B．零矩阵C．上三角矩阵D．对角矩阵35．图的深度优先遍历算法类似于二叉树的（）遍历。A．先序B．中序C．后序D．层次36．已知下图所示的一个图，若从顶点V1出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为（）。A．V1V2V4V8V3V5V6V7B．V1V2V4V5V8V3V6V7C．V1V2V4V8V5V3V6V7D．V1V3V6V7V2V4V5V8　　　二、填空题1．结点的度是指结点所拥有的。2．树的度是指。3．度大于0的结点称作或。4．度等于0的结点称作或。5．在一棵树中，每个结点的或者说每个结点的称为该结点的，简称为孩子。6．一个结点称为其后继结点的。7．具有的结点互称为兄弟结点，简称为兄弟。8．每个结点的所有子树中的结点被称为该结点的。9．从根结点到该结点所经分支上的所有结点称为该结点的。10．树的深度或高度是指。11．m(m(0)棵互不相交的树的集合称为。12．度为k的树中的第i层上最多有结点。13．深度为k的二叉树最多有结点。14．在一棵二叉树中，如果树中的每一层都是满的，则称此树为；但如果出最后一层外，其余层都是满的，并且最后一层是满的，或者是在缺少若干连续个结点，则称此二叉树为。15．具有n个结点的完全二叉树的深度是。16．先序遍历二叉树的的操作定义为；若二叉树为空，则为空操作，否则进行如下操作，访问二叉树的；先序遍历二叉树的，先序遍历二叉树的。17．中序遍历二叉树的的操作定义为；若二叉树为空，则为空操作，否则进行如下操作，中序遍历二叉树的；访问而叉树的，中序遍历二叉树的。18．后序遍历二叉树的的操作定义为；若二叉树为空，则为空操作，否则进行如下操作，后序遍历二叉树的；后序遍历二叉树的，访问而叉树的。19．将树中结点赋上一个有着某种意义的实数，称此实数为该结点的。20．树的带权路径长度为树中所有叶子结点的。21．哈夫曼树又称为，它是n个带权叶子结点构成的所有二叉树中带权路径长度WPL。22．若以4，5，6，7，8作为叶子结点的权值构造哈夫曼树，则其带权路径长度是。23．具有m个叶子结点的哈夫曼树共有结点。24．在图中，任何两个数据元素之间都可能存在关系，因此图的数据元素之间是一种的关系。25．图的邻接矩阵表示法是用一个来表示图中顶点之间的相邻关系。26．邻接表是图中的每个顶点建立一个邻接关系的。27．图的遍历是从图的某一顶点出发，按照一定的搜索方法对图中各做访问的过程。28．图的深度优先搜索遍历类似于树的遍历。29．图的广度优先搜索类似于树的遍历。30．具有n个顶点的有向图的邻接矩阵，其元素个数为。30．具有n个顶点的无向图至少有条边，才能确保其为一个连通图。31．图常用的两种存储结构是和。32．一个AOV网（顶点活动图）应该是一个。即不应该带有回路，否则回路上的所有活动都。33．用邻接矩阵存储有向图G，其第i行的所有元素之和等于顶点i的。34．在有n个顶点的有向图中，每个顶点的度最大可达。35．在一个带权图中，两顶点之间的最段路径最多经过条边。36．为了实现图的深度优先搜索遍历，其非递归的算法中需要使用的一个辅助数据结构为。三、综合题1．写出如下图所示的二叉树的先序、中序和后序遍历序列。2．已知某二叉树的先序遍历结果是：A，B，D，G，C，E，H，L，I，K，M，F和J，它的中序遍历结果是：G，D，B，A，L，H，E，K，I，M，C，F和J，请画出这棵二叉树，并写出该二叉树后续遍历的结果。3．已知一棵完全二叉树共有892个结点，求⑴树的高度⑵叶子结点数⑶单支结点数⑷最后一个非终端结点的序号4．给出满足下列条件的所有二叉树。（1）先序和中序相同（2）中序和后序相同（3）先序和后序相同5．假设通信用的报文由9个字母A、B、C、D、E、F、G、H和I组成，它们出现的频率分别是：10、20、5、15、8、2、3、7和30。请请用这9个字母出现的频率作为权值求：（1）设计一棵哈夫曼树；（2）计算其带权路径长度WPL；（3）写出每个字符的哈夫曼编码。6．请根据以下带权有向图G（1）给出从结点v1出发分别按深度优先搜索遍历G和广度优先搜索遍历G所得的结点序列；（2）给出G的一个拓扑序列；（3）给出从结点v1到结点v8的最短路径。7．已知无向图G描述如下：G=（V，E）V={V1，V2，V3，V4，V5}E={（V1，V2），（V1，V4），（V2，V4），（V3，V4），（V2，V5），（V3，V4），（V3，V5）}（1）画出G的图示；（2）然后给出G的邻接矩阵和邻接表；（3）写出每个顶点的度。8．回答下列问题：⑴对于存储结构采用邻接矩阵的无向图，如何判断下列有关问题？①图中有多少条边？②任意两顶点间是否有边相连？③任意一个顶点的度是多少？⑵对于存储结构采用邻接表的有向图，如何判断下列有关问题？①图中有多少条边？②图中是否存在从Vi到Vj的边？③如何求顶点Vi的入度和出度？四、程序填空题1.下面函数的功能是返回二叉树BT中值为X的结点所在的层号，请在划有横线的地方填写合适内容。intNodeLevel(structBinTreeNode*BT,charX){if(BT==NULL)return0;/*空树的层号为0*/elseif(BT->data==X)return1;/*根结点的层号为1*//*向子树中查找X结点*/else{intc1=NodeLevel(BT->left,X);if(c1>=1)___(1)___________;intc2=______(2)__________;if___(3)__________________;//若树中不存在X结点则返回0elsereturn0;}}2.下面函数的功能是按照图的深度优先搜索遍历的方法，输出得到该图的生成树中的各条边，请在划有横线的地方填写合适内容。voiddfstree(adjmatrixGA,inti,intn){intj;visited[i]=1;(1)if(GA[i][j]!=0&&GA[i][j]!=MaxValue&&!visited[j]){printf("(%d,%d)%d,",i,j,GA[i][j]);(2)}}五、算法设计题1．写一个将一棵二叉树复制给另一棵二叉树的算法。2．根据下面函数声明编写出求一棵二叉树中叶子结点总数的算法，该总数值由函数返回。假定参数BT初始指向二叉树的根结点。intBTreeLeafCount(structBTreeNode*BT);3．已知有n个顶点的有向图邻接表，设计算法分别实现下列功能：（1）求出图G中每个顶点的出度、入度。（2）计算图中度为0的顶点数。六、完成：实验3――栈、队列、递归程序设计实验4——图的存储方式和应用根据实验要求（见教材P203）认真完成本实验，并提交实验报告。数据结构（本）课程作业（4）（本部分作业覆盖教材第8-9章的内容）一、单项选择题1.顺序查找方法适合于存储结构为（）的线性表。A．散列存储B．索引存储C．散列存储或索引存储D．顺序存储或链接存储2．对线性表进行二分查找时，要求线性表必须（）。A．以顺序存储方式B．以链接存储方式C．以顺序存储方式，且数据元素有序D．以链接存储方式，且数据元素有序3．如果要求一个线性表既能较快地查找，又能动态适应变化要求，可以采用（）查找方法。A．顺序B．分块C．折半D．散列4.对于一个线性表，若要求既能进行较快地插入和删除，又要求存储结构能够反映数据元素之间的逻辑关系，则应该（）。A．以顺序存储方式B．以链接存储方式C．以索引存储方式D．以散列存储方式5．采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为（）。A．nB．n/2C．(n+1)/2D．(n-1)/26．采用折半查找方法查找长度为n的线性表时，每个元素的平均查找长度为（）。A．O(n*n)B．O(nlog2n)C．O(n)D．s(log2n)7．哈希函数有一个共同的性质，即函数值应当以（）取其值域的每个值。A．最大概率B．最小概率C．平均概率D．同等概率8．有一个长度为10的有序表，按折半查找对该表进行查找，在等概率情况下查找成功的平均比较次数为（）。A．29/10B．31/10C．26/10D．29/99．已知一个有序表为{11,22,33,44,55,66,77,88,99}，则顺序查找元素55需要比较（）次。A．3B．4C．5D．610．顺序查找法与二分查找法对存储结构的要求是（）。A．顺序查找与二分查找均只是适用于顺序表B．顺序查找与二分查找均既适用于顺序表，也适用于链表C．顺序查找只是适用于顺序表D．二分查找适用于顺序表11．有数据{53,30,37,12,45,24,96}，从空二叉树开始逐个插入数据来形成二叉排序树，若希望高度最小，应该选择的序列是（）。A．45,24,53,12,37,96,30B．37,24,12,30,53,45,96C．12,24,30,37,45,53,96D．30,24,12,37,45,96,5312．对有18个元素的有序表作二分（折半）查找，则查找A[3]的比较序列的下标可能为（）。A．1、2、3B．9、5、2、3C．9、5、3D．9、4、2、313.对于顺序存储的有序表{5，12，20，26，37，42，46，50，64}，若采用折半查找，则查找元素26的比较次数是（）。A.3B.3C.4D.514.关于哈希查找的说法正确的是（）。A.除留余数法是最好的B.哈希函数的好坏要根据具体情况而定C.删除一个元素后，不管用哪种方法处理冲突，都只需简单地把该元素删除掉D.因为冲突是不可避免的，所以装填因子越小越好15.在所有的排序方法中，关键字比较的次数与记录初始排列秩序无关的是（）。A.冒泡排序B.希尔排序C.直接选择排序D.直接插入排序16.从未排序序列中依次取出元素与已经排好序的序列中的元素作比较。将其放入已排序序列的正确的位置上，此方法称为（）A.插入排序B.选择排序C.交换排序D.归并排序17.从未排序序列中挑选元素，并将其放入已排序序列的一端，此方法称为（）。A.插入排序B.交换排序C.选择排序D.归并排序18.依次将每两个相邻的有序表合并成一个有序表的排序方法称为（）。A.插入排序B.交换排序C.选择排序D.归并排序19.当两个元素出现逆序的时候就交换位置，这种排序方法称为（）。A.插入排序B.交换排序C.选择排序D.归并排序20.每次把待排序的区间划分为左、右两个子区间，其中左区间中记录的关键字均小于等于基准记录的关键字，右区间中记录的关键字均大于等于基准记录的关键字，这种排序称为（）。A.插入排序B.快速排序C.堆排序D.归并排序21.在正常情况下，直接插入排序的时间复杂度为（）。A.O(log2n)B.O(n)C.O(nlog2n)D.O(n2)22.在正常情况下，冒泡排序的时间复杂度为（）。A.O(log2n)B.O(n)C.O(nlog2n)D.O(n2)23.在归并排序中，归并趟数的数量级为（）。A.O(log2n)B.O(n)C.O(nlog2n)D.O(n2)24.在待排序元素基本有序的情况下，效率最高的排序方法是（）。A.插入排序B.快速排序C.堆排序D.归并排序25.下面几种排序方法中，要求内存量最大的是（）。A.插入排序B.交换排序C.选择排序D.归并排序26.在下列排序方法中，关键字比较的次数与记录的初始排列秩序无关的是（）。A.希尔排序B.冒泡排序C.插入排序D.选择排序27.快速排序方法在（）情况下最不利于发挥其长处。A.要排序的数据量太大B.要排序的数据中含有多个相同值C.要排序的数据已基本有序D.要排序的数据个数为奇数28.下述几种排序方法中，平均情况下占用内存量最大的是（）方法。A.插入排序B.选择排序C.快速排序D.归并排序29.若构造一棵具有n个结点的二叉树排序，在最坏的情况下，其深度不会超过（）。A.n/2B.nC.(n(1)/2D.n(130.对数据元素序列（49，72，68，13，38，50，97，27）进行排序，前三趟排序结果时的结果依次为第一趟：49，72，68，13，38，50，97，27；第二趟：49，68，72，13，38，50，97，27；第三趟：13，49，68，72，38，50，97，27。该排序采用的方法是（）。A.插入排序法B.选择排序法C.冒泡排序法D.堆积排序法31.对具有n个元素的任意序列采用插入排序法进行排序，排序趟数为（　　）。A.n-1B.nC.n+1D.(log2n(32.对序列（49，38，65，97，76，13，47，50）采用直接插入排序法进行排序，要把第七个元素47插入到已排序中，为寻找插入的合适位置需要进行（　　）次元素间的比较。A.3B.4C.5D.633.下面四种排序方法中，（　　）是一种稳定性排序方法。A.插入排序法B.选择排序法C.快速排序法D.希尔排序法34．一组记录的关键字序列为（46，79，56，38，40，84），利用快速排序，以第一个关键字为分割元素，经过一次划分后结果为（）。A．40，38，46，79，56，84B．40，38，46，84，56，79C．40，38，46，56，79，84D．38，40，46，56，79，8435．一组记录的关键字序列为（46，79，56，38，40，84），利用堆排序的方法建立的初始堆为（）。A．79，46，56，38，40，84B．84，79，56，38，40，46C．84，79，56，46，40，38，D．84，56，79，40，46，3836．一组记录的关键字序列为（25，48，16，35，79，82，23，40，36，72），其中，含有5个长度为2的有序表，按归并排序的方法对该序列进行一趟归并后的结果为（）。A．16，25，35，48，23，40，79，82，36，72B．16，25，35，48，79，82，23，36，40，72C．16，25，48，35，79，82，23，36，40，72D．16，25，35，48，79，23，36，40，82，7237．已知10个数据元素为（54，28，16，34，73，62，95，60，26，43），对该数列从小到到大排序，经过一趟冒泡排序后的序列为（）。A．16，28，34，54，73，62，60，26，43，95B．28，16，34，54，62，73，60，26，43，95C．28，16，34，54，62，60，73，26，43，95D．16，28，34，54，62，60，73，26，43，9538．用某种排序的方法对线性表（25，84，21，47，15，27，68，35，20）进行排序时，元素序列的变化情况如下：（1）25，84，21，47，15，27，68，35，20（2）20，15，21，25，47，27，68，35，84（3）15，20，21，25，35，27，47，68，84（4）15，20，21，25，27，35，47，68，84其所采用的排序方法是（）。A.希尔排序B.归并排序C.快速排序D.直接选择排序二、填空题1．在各种查找方法中，平均查找长度与结点个数n无关的查找方法是。2．如果对查找表只进行查询某个特定的数据元素是否在查找表中，以及查找某个特定数据元素的各种属性两种类型的基本操作，而不进行插入和删除操作数据元素的查找表称为。3．如果在查找表中进行查询的过程中，同时插入查找表中不存在的数据元素，或者从查找表中删除已存在的某个数据元素，则称此类查找表为。4．关键字是记录某个，用它可以识别、确定一个。5．在一个查找表中，能够唯一地确定一个记录的关键字称为。6．平均查找长度是指为确定记录在查找表中的位置，需要与给定值进行比较的关键字个数的。7．查找是一种最简单的查找方法。8．折半查找又称为。使用该查找算法的前提条件是，查找表中记录相应的关键字值必须按。9．折半查找只适用于的有序表。10．分块查找又称为，它是一种介于和折半查找之间的查找方法。11．二叉排序树或者是一棵空树，或者是具有下列性质的一棵二叉树：（1）若左子数不空，则左子树所有结点的值。（2）若右子数不空，则右子树所有结点的值。（3）左右子树又分别是。12．哈希表是用来存放查找表中记录序列的表，每一个记录的存储位置是以该记录得到关键字为，由相应哈希函数计算所得到的。13．在有序表A[1….18]中，采用二分查找算法查找元素值等于A[17]的元素，所比较过的元素的下标依次是。14．根据排序过程中所用的存储器不同，可以将排序方法分为和。15．冒泡排序是一种比较简单的方法。16．在对一组记录（50，40，95，20，15，70，60，45，80）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需要比较次。17．在归并排序中，在第3趟归并中，是把长度为的有序表归并为长度为有序表。18．在堆排序和快速排序中，若原始记录接近正序和反序，则选用，若原始记录无序，则最好选用。19．对记录序列排序是指按记录的某个关键字排序，记录序列按_________排序结果是唯一的。20．按某关键字对记录序列排序，若在排序前和排序后仍保持它们的前后关系，则排序算法是稳定的，否则是不稳定的。21．n个元素进行冒泡法排序，通常需要进行________趟冒泡，第j趟冒泡要进行______次元素间的比较。22．当从一个小根堆中删除一个元素时，需要把元素填补到位置，然后再按条件把它逐层调整。三、综合题1．已知序列（70，83，100，105，10，32，7，9），请写出对此序列采用插入排序法进行升序排序时各趟的结果。2．已知序列（10，18，4，3，6，12，1，9，15，8），请写出对此序列采用归并排序法进行升序排序时各趟的结果。3．已知序列（17，18，60，40，7，32，73，65，85）请给出采用冒泡排序法对该序列作升序排列时的每一趟结果。4．已知序列（503，87，512，61，908，170，897，275，653，462）请给出采用快速排序法对该序列作升序排列时的每一趟结果。5．设一组记录的关键字序列为（51，85，61，43，45，49），采用堆排序算法完成以下操作：（要求小根堆，并画出中间过程）（1）以二叉树描述6个元素的初始堆（2）以二叉树描述逐次取走堆顶元素后，经调整得到的5个元素、4个元素的堆6．设查找表为(20,19,24,57,68,11)(1)用冒泡对该表进行排序，要求写出每一趟的排序过程，通常对n个元素进行冒泡排序要进行多少趟冒泡？第j趟要进行多少次元素间的比较？(2)在排序后的有序表的基础上，画出对其进行折半查找所对应的判定树.(要求以数据元素作为树结点)(3)求在等概率条件下,对上述有序表成功查找的平均查找长度。7．(1)设有查找表{8,17,5,9,21,10,7,19,6},依次取表中数据，构造一棵二叉排序树.（2）说明如何通过序列的二叉排序树得到相应序列的排序结果，对上述二叉排序给出中序遍历的结果.四、程序填空题1．以下直接输入排序算法对存放在a[0],a[1],···,a[n-1]中，长度为n的记录序列按关键字key由小到大排序，完成程序中的空格部分。voiddisort(NODEa[],intn){intI,j;NODEtemp;/*工作单位*/for(i=1;i<n;i++){temp=a[i];j=j-1;while(__①____&&temp.key<a[j].key){a[j+1]=___②__________③______}a[j+1]=____④____;}}2．以下冒泡法程序对存放在a[1]，a[2]，……，a[n]