电大数据结构本形成性考核册作业1-4原题带答案.doc

数据结构（本）课程作业作业1（本部分作业覆盖教材第1-2章的内容）14一、单项选择题1．在数据结构中，从逻辑上可以把数据结构分为（C ）A．动态结构和静态结构 B．紧凑结构和非紧凑结构 C．线性结构和非线性结构 D．内部结构和外部机构2．下列说法中，不正确的是（ D ）A．数据元素是数据的基本单位 B．数据项是数据中不可分割的最小可标识单位 C．数据可有若干个数据元素构成 D．数据项可由若干个数据元素构成3．一个存储结点存储一个（ B ）A．数据项 B．数据元素 C．数据结构 D．数据类型4．数据结构中，与所使用的计算机无关的是数据的（ C ）A．存储结构 B．物理结构C．逻辑结构 D．物理和存储结构5．下列的叙述中，不属于算法特性的是（ D ）A．有穷性 B．输入性 C．可行性 D．可读性6．算法分析的目的是（ C ）。

A．找出数据结构的合理性 B．研究算法中的输入和输出的关系 C．分析算法的效率以求改进 D．分析算法的易懂性和文档性7．数据结构是一门研究计算机中（B ）对象及其关系的科学A．数值运算 B．非数值运算C．集合 D．非集合 8．算法的时间复杂度与（ C ）有关 A．所使用的计算机 B．与计算机的操作系统 C．与算法本身 D．与数据结构9．设有一个长度为n的顺序表，要在第i个元素之前（也就是插入元素作为新表的第i个元素），则移动元素个数为（ A ） A．n-i+1 B．n-i C．n-i-1 D．i10．设有一个长度为n的顺序表，要删除第i个元素移动元素的个数为（ B ） A．n-i+1 B．n-i C．n-i-1 D．i11．在一个单链表中，p、q分别指向表中两个相邻的结点，且q所指结点是p所指结点的直接后继，现要删除q所指结点，可用语句（ C ） A．p=q->next B．p->next=q C．p->next=qnext D．q->next=NULL12．在一个单链表中p所指结点之后插入一个s所指的结点时，可执行（ D ）。

A．p->next= s; snext= pnext B．p->next=snext; C．p=s->next D．s->next=p->next; p->next=s;13．非空的单向循环链表的尾结点满足（C ）（设头指针为head，指针p指向尾结点） A.．P->next= =NULL B．P= =NULL C．P->next= =head D．P= = head 14．链表不具有的特点是（ A ） A．可随机访问任一元素 B．插入删除不需要移动元素 C．不必事先估计存储空间 D．所需空间与线性表长度成正比15．带头结点的链表为空的判断条件是（B ）（设头指针为head）　　　　A．head = =NULL　　　　B．head->next= =NULL 　　　　C．head->next= =head　　D．head!=NULL　　16．在一个单链表中，p、q分别指向表中两个相邻的结点，且q所指结点是p所指结点的直接后继，现要删除q所指结点，可用语句（C ）。

　　　　A．p=q->next　　　　B．p->next=q　　　　C．p->next=q->next　　　　D．q->next=NULL17．在一个链队中，假设f和r分别为队头和队尾指针，则删除一个结点的运算为（C ） A．r=f->next; B．r=r->next; C．f=f->next; D．f=r->next;18．在一个链队中，假设f和r分别为队头和队尾指针，则插入s所指结点的运算为（ B ） 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个元素的地址是（B ）A．98 B．100 C．102 D．10620．有关线性表的正确说法是（ D ）A．每个元素都有一个直接前驱和一个直接后继 B．线性表至少要求一个元素C．表中的元素必须按由小到大或由大到下排序 D．除了一个和最后一个元素外，其余元素都有一个且仅有一个直接前驱和一个直接后继二、填空题1．在一个长度为n的顺序存储结构的线性表中，向第i(1in+1)个元素之前插入新元素时，需向后移动 n-i+1 个数据元素。

2．从长度为n的采用顺序存储结构的线性表中删除第i(1in+1)个元素 ，需向前移动 n-i 个元素3．数据结构按结点间的关系，可分为4种逻辑结构： 集合 、 线性结构 、 树形结构 、 图状结构 4．数据的逻辑结构在计算机中的表示称为 物理结构 或 存储结构 5．除了第1个和最后一个结点外，其余结点有且只有一个前驱结点和后继结点的数据结构为 线性结构 ，每个结点可有任意多个前驱和后继结点数的结构为 非线性结构 6．算法的5个重要特性是 有穷性 、 确定性 、 可形性 、 有零个或多个输入 、 有零个或多个输出 7．数据结构中的数据元素存在多对多的关系称为__图状结构__结构8．数据结构中的数据元素存在一对多的关系称为_树形结构__结构9．数据结构中的数据元素存在一对一的关系称为_线性结构_结构10．要求在n个数据元素中找其中值最大的元素，设基本操作为元素间的比较则比较的次数和算法的时间复杂度分别为___ n-1__和 __ O(n)___ 11．在一个单链表中p所指结点之后插入一个s所指结点时，应执行__ s->next=p->next ___和p->next=s;的操作。

12．设有一个头指针为head的单向循环链表，p指向链表中的结点，若p->next= =__ head __，则p所指结点为尾结点13．在一个单向链表中，要删除p所指结点，已知q指向p所指结点的前驱结点则可以用操作_ q->next=p->next __14．设有一个头指针为head的单向链表，p指向表中某一个结点，且有p->next= =NULL,通过操作__ p->next=head __,就可使该单向链表构造成单向循环链表15．每个结点只包含一个指针域的线性表叫 单链表 16．线性表具有 顺序存储 和 链式存储 两种存储结构17．数据的逻辑结构是从逻辑关系上描述数据，它与数据的关系 存储结构 无关，是独立于计算机的18．在双向循环链表的每个结点中包含 两个 指针域，其中next指向它的 直接后继 ，prior指向它的 直接前驱 ，而头结点的prior指向 尾结点 ，尾结点的next指向 头结点 19．单向循环链表是单向链表的一种扩充，当单向链表带有头结点时，把单向链表中尾结点的指针域由空指针改为 头结点的指针 ；当单向链表不带头结点时，则把单向链表中尾结点的指针域由空指针改为指向 指向第一个结点的指针 。

20．线性链表的逻辑关系时通过每个结点指针域中的指针来表示的其逻辑顺序和物理存储顺序不再一致，而是一种 链式 存储结构，又称为 链表 三、问答题1．简述数据的逻辑结构和存储结构的区别与联系，它们如何影响算法的设计与实现？答：若用结点表示某个数据元素，则结点与结点之间的逻辑关系就称为数据的逻辑结构数据在计算机中的存储表示称为数据的存储结构可见，数据的逻辑结构是反映数据之间的固有关系，而数据的存储结构是数据在计算机中的存储表示尽管因采用的存储结构不同，逻辑上相邻的结点，其物理地址未必相同，但可通过结点的内部信息，找到其相邻的结点，从而保留了逻辑结构的特点采用的存储结构不同，对数据的操作在灵活性，算法复杂度等方面差别较大2．解释顺序存储结构和链式存储结构的特点，并比较顺序存储结构和链式存储结构的优缺点答：顺序结构存储时，相邻数据元素的存放地址也相邻，即逻辑结构和存储结构是统一的，，要求内存中存储单元的地址必须是连续的优点：一般情况下，存储密度大，存储空间利用率高缺点：（1）在做插入和删除操作时，需移动大量元素；（2）由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用；（3）表的容量难以扩充。

链式结构存储时，相邻数据元素可随意存放，所占空间分为两部分，一部分存放结点值，另一部分存放表示结点间关系的指针优点：插入和删除元素时很方便，使用灵活缺点：存储密度小，存储空间利用率低3．什么情况下用顺序表比链表好？答：顺序表适于做查找这样的静态操作，链表适于做插入和删除这样的动态操作如果线性表的变化长度变化不大，且其主要操作是查找，则采用顺序表；如果线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表4．头指针、头结点、第一个结点（或称首元结点）的区别是什么？头结点是在链表的开始结点之前附加的一个结点；第一个结点（或称首元结点）是链表中存储第一个数据元素的结点；头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针5．解释带头结点的单链表和不带头结点的单链表的区别答：带头结点的单链表和不带头结点的单链表的区别主要体现在其结构上和算法操作上在结构上，带头结点的单链表，不管链表是否为空，均含有一个头结点，不带头结点的单链表不含头结点在操作上，带头结点的单链表的初始化为申请一个头结点无论插入或删除的位置是地第一个结点还是其他结点，算法步骤都相同不带头结点的单链表，其算法步骤要分别考虑插入或删除的位置是第一个结点还是其他结点。

因为两种情况的算法步骤不同四、程序填空题1．下列是用尾插法建立带头结点的且有n个结点的单向链表的算法，请在空格内填上适当的语句NODE *create1(n)/* 对线性表(1,2,.....,n),建立带头结点的单向链表 */{ NODE *head,*p,*q; int i; p=(NODE *)malloc(sizeof(NODE)); head=p; q=p; p->next=NULL; for(i=1;i<=n;i++) { p=(NODE *)malloc(sizeof(NODE)); （1）p->data=i ; （2）p->next=NULL ; （3）q->next=p ; （4） q=p ; } return(head);}2．下列是用头插法建立带头结点的且有n个结点的单向链表的算法，请在空格内填上适当的语句NODE *create2(n)/*对线性表(n,n-1,.....,1),建立带头结点的线性链表 */{ NODE *head,*p,*q; int i; p=(NODE *)malloc(sizeof(NODE)); （1） head=p ; p->next=NULL; （2） q=p ; for(i=1;i<=n;i++) { p=(NODE *)malloc(sizeof(NODE)); p->data=i; if(i==1) （3） p->next=NULL ; else（4） p->next=q->next ;（5） q->next=p ;} return(head);}3．下列是在具有头结点单向列表中删除第i个结点，请在空格内填上适当的语句。

int delete(NODE *head,int i){NODE *p,*q; int j; q=head;j=0; while((q!=NULL)&&(jnext;j++;} if(q==NULL) return(0);（1） p=q->next ; （2） q->next=p->next ; free(p); return(1);}五、完成：实验1――线性表根据实验要求（见教材P201-202）认真完成本实验，并提交实验报告数据结构（本）课程作业2（本部分作业覆盖教材第3-5章的内容）一、单项选择题1．若让元素1，2，3依次进栈，则出栈顺序不可能为（ C ）A．3，2，1 B．2，1，3 C．3，1，2 D．1，3，22．一个队列的入队序列是1，2，3，4则队列的输出序列是（ B ）A．4，3，2，1 B．1，2，3，4 C．1，4，3，2 D．3，2，4，13．向顺序栈中压入新元素时，应当（ A ）。

A．先移动栈顶指针，再存入元素 B．先存入元素，再移动栈顶指针 C．先后次序无关紧要 D．同时进行4．在一个栈顶指针为top的链栈中，将一个p指针所指的结点入栈，应执行（ C ）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保存被删结点的值，则执行（ B ）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 ）A．栈 B．队列C．堆栈或队列 D．数组7．表达式a*(b+c)-d的后缀表达式是（ B ） A．abcd*+- B．abc+*d- C．abc*++d- D．-+*abcd8．判断一个顺序队列sq（最多元素为m0）为空的条件是（ C ）。

A．sq->rear-sq->front== m0 B．sq->rear-sq->front-1= = m0 C．sq->front==sq->rear D．sq->front==sq->rear+19．判断一个循环队列Q（最多元素为m0）为空的条件是（ A ） A．Q->front==Q->rear B．Q->front!=Q->rear C．Q->front==(Q->rear+1)% m0 D．Q->front!= (Q->rear+1)%m0 10．判断栈S满（元素个数最多n个）的条件是（C ） A．s->top==0 B．s->top!=0 C．s->top==n-1 D．s->top!=n-1 11．一个队列的入队顺序是a,b,c,d，则离队的顺序是（ B ） A．a,d,cb B．a,b,c,d C．d,c,b,a D．c,b,d,a12．如果以链表作为栈的存储结构，则退栈操作时（ C ）。

A．必须判断栈是否满 B．判断栈元素类型 C．必须判断栈是否空 D．对栈不作任何判断13．在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入缓冲区中，而打印机则从缓冲区中取出数据打印，该缓冲区应该是一个（ B ）结构A．堆栈 B．队列 C．数组 D．先性表14．一个递归算法必须包括（ B ）A．递归部分 B．终止条件和递归部分 C．迭代部分 D．终止条件和迭代部分15．从一个栈顶指针为top的链栈中删除一个结点时，用变量x保存被删结点的值，则执行（ A ） A．x=top->data; top=top->next; B．x=top->data; C．top=top->next; x=top->data; D．top=top->next; x=data;16．在一个链队中，假设f和r分别为队头和队尾指针，则删除一个结点的运算为（C ） A．r=f->next; B．r=r->next; C．f=f->next; D．f=r->next;17．在一个链队中，假设f和r分别为队头和队尾指针，则插入s所指结点的运算为（B ）。

A．f->next=s; f=s; B．r->next=s;r=s; C．s->next=r;r=s; D．s->next=f;f=s;18.以下陈述中正确的是（ A ）A．串是一种特殊的线性表 B．串的长度必须大于零C．串中元素只能是字母 D．空串就是空白串19．设有两个串p和q，其中q是p的子串，q在p中首次出现的位置的算法称为（ C ）A．求子串 B．连接 C．匹配 D．求串长 20．串是（ D ） A．不少于一个字母的序列 B．任意个字母的序列 C．不少于一个字符的序列 D．有限个字符的序列 21．串的长度是指（ B ）A．串中所含不同字母的个数 B．串中所含字符的个数C．串中所含不同字符的个数 D．串中所含非空格字符的个数22. 若串S==“English”，其子串的个数是（ D ） A．9 B．16 C． 36 D．2823．串与普通的线性表相比较，它的特殊性体现在（ C ）。

A．顺序的存储结构 B．链接的存储结构 C．数据元素是一个字符 D．数据元素可以任意24．空串与空格串（ B ）A．相同 B．不相同 C．可能相同 D．无法确定25．两个字符串相等的条件是（ D） A．两串的长度相等 B．两串包含的字符相同 C．两串的长度相等，并且两串包含的字符相同 D．两串的长度相等，并且对应位置上的字符相同26．在实际应用中，要输入多个字符串，且长度无法预定则应该采用（A ）存储比较合适（ ）A．链式 B． 顺序 C．堆结构 D．无法确定 27.一维数组A采用顺序存储结构，每个元素占用6个字节，第6个元素的存储地址为100，则该数组的首地址是（ C ）A．64 B．28C．70 D．9028．稀疏矩阵采用压缩存储的目的主要是（D ）A．表达变得简单 B．对矩阵元素的存取变得简单 C．去掉矩阵中的多余元素 D．减少不必要的存储空间的开销29．一个非空广义表的表头（ C ）。

A．不可能是原子 B．只能是子表 C．只能是原子 D．可以是子表或原子 30．常对数组进行的两种基本操作是（ C ）A．建立与删除 B．索引与、和修改C．查找和修改 D．查找与索引31. 设二维数组A[5][6]按行优先顺序存储在内存中，已知A[0][0] 起始地址为1000，每个数组元素占用5个存储单元，则元素A[4][4]的地址为（ A ） A．1140 B．1145 C． 1120 D．112532．设有一个20阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素a9,2在一维数组B中的下标是（ D ）A．41 B．32 C．18 D．38二、填空题1．栈是限定在表的一端进行插入和删除操作的线性表，又称为 后进先出 2．循环队列队头指针在队尾指针 下一个 位置，队列是“满”状态3．在队列的顺序存储结构中，当插入一个新的队列元素时，尾指针 增1 ，当删除一个元素队列时，头指针 增1 。

4．循环队列的引入，目的是为了克服 假上溢 5．向顺序栈插入新元素分为三步：第一步进行 栈是否满 判断，判断条件是 s->top=MAXSIZE-1 ；第二步是修改 栈顶指针 ；第三步是把新元素赋给 栈顶对应的数组元素 同样从顺序栈删除元素分为三步：第一步进行 栈是否空 判断，判断条件是 s->top=-1 第二步是把 栈顶元素 ；第三步 修改栈顶指针 6．假设以S和X分别表示入栈和出栈操作，则对输入序列a,b,c,d,e一系列栈操作SSXSXSSXXX之后，得到的输出序列为 bceda 7．一个递归算法必须包括 终止条件 和 递归部分 8．判断一个循环队列LU（最多元素为m0）为空的条件是 LU->front==LU->rear 9．在将中缀表达式转换成后缀表达式和计算后缀表达式的算法中，都需要使用栈，对于前者，进入栈中的元素为表达式中的 运算符 ，而对于后者，进入栈的元素为 操作数 ，中缀表达式(a+b)/c-(f-d/c)所对应的后缀表达式是 ab+c/fde/-- 。

10．向一个栈顶指针为h的链栈中插入一个s所指结点时，可执行___ s->next=h _____和h=s;操作结点的指针域为next)11．从一个栈顶指针为h的链栈中删除一个结点时，用x保存被删结点的值，可执行x=h->data;和__ h=h->next ______结点的指针域为next)12．在一个链队中，设f和r分别为队头和队尾指针，则插入s所指结点的操作为___ r->next=s _____和r=s; (结点的指针域为next)13．在一个链队中，设f和r分别为队头和队尾指针，则删除一个结点的操作为__ f=f->next ______ (结点的指针域为next) 14．串是一种特殊的线性表，其特殊性表现在组成串的数据元素都是 字符 15．串的两种最基本的存储方式是 顺序存储方式 和 链式存储方式 16．空串的长度是 0 ；空格串的长度是 空格字符的个数 17．需要压缩存储的矩阵可分为 特殊 矩阵和 稀疏 矩阵两种。

18．设广义表L=（（），（）），则表头是 （） ，表尾是 （（）） ，L的长度是 2 19．广义表A（（a,b,c）,(d,e,f)）的表尾为 （（d,e,f）） 20．两个串相等的充分必要条件是_______串长度相等且对应位置的字符相等 ___21．设有n阶对称矩阵A，用数组s进行压缩存储，当ij时，A的数组元素aij相应于数组s的数组元素的下标为__ i(i-1)/2+j _____数组元素的下标从1开始）22．对稀疏矩阵进行压缩存储，矩阵中每个非零元素对应的三元组包括该元素的___行下标____、___列下标___和___非零元素值____三项信息三、问答题1．简述栈和一般线性表的区别答：栈是一种先进后出的线性表，栈的插入和删除操作都只能在栈顶进行，而一般的线性表可以在线性表的任何位置进行插入和删除操作2．简述队列和一般线性表的区别队列是一种先进先出的线性表，队列的插入只能在队尾进行，队列的删除只能在队头进行，而一般的线性表可以在线性表的任何位置进行插入和删除操作3．链栈中为何不设头结点？答：因为链栈只在链头插入和删除结点，不可能在链表中间插入和删除结点，算法实现很简单，所以一般不设置头结点。

4．利用一个栈，则：（1）如果输入序列由A，B，C组成，试给出全部可能的输出序列和不可能的输出序列2）如果输入序列由A，B，C，D组成，试给出全部可能的输出序列和不可能的输出序列答：（1）栈的操作特点是后进先出，因此输出序列有：A入，A出，B入，B出，C入C出，输出序列为ABCA入，A出，B入，C入，C出，B出，输出序列为ACBA入，B入，B出，A出，C入，C出，输出序列为BACA入，B入，B出，C入，C出，A出，输出序列为BCAA入，B入，C入，C出，B出，A出，输出序列为CBA由A，B，C组成的数据项，除上述五个不同的组合外，还有一个C，A，B组合但不可能先把C出栈，再把A出栈，（A不在栈顶位置），最后把B出栈，所以序列CAB不可能由输入序列A，B，C 通过栈得到2）按照上述方法，可能的输出序列有：ABCD，ABDC，ACBD，ACDB，ADCB，BACD，BADC，BCAD，BCDA，BDCA，CBAD，CBDA，CDBA，DCBA不可能的输出序列有：DABC，ADBC，DACB，DBAC，BDAC，DBCA，DCAB，CDAB，CADB，CABD5．用S表示入栈操作，X表示出栈操作，若元素入栈顺序为1234，为了得到1342出栈顺序，相应的S和X操作串是什么？答：应是SXSSXSXX。

各操作结果如下：S 1入栈X 1出栈 输出序列：1S 2入栈S 3入栈X 3出栈 输出序列：13S 4入栈 X 4出栈 输出序列：134X 2出栈 输出序列：1342 6．有5个元素，其入栈次序为：A、B、C、D、E，在各种可能的出栈次序中，以元素C、D最先的次序有哪几个？答：从题中可知，要使C第一个且D第二个出栈，应是A入栈，B入栈，C入栈，C出栈，D入栈之后可以有以下几种情况：（1）B出栈，A出栈，E入栈，E出栈，输出序列为：CDBAE2）B出栈，E入栈，E出栈，A 出栈，输出序列为CDBEA3）E入栈，E出栈，B出栈，A出栈，输出序列为CDEBA所以可能的次序有：CDBAE，CDBEA，CDEBA7．写出以下运算式的后缀算术运算式⑴ 3x2+x-1/x+5⑵ (A+B)*C-D/(E+F)+G答；对应的后缀算术运算式⑴ 3x2^*x+1x/-5+⑵ AB+C*DEF+/-G+8． 简述广义表和线性表的区别和联系答：广义表是线性表的的推广，它也是n(n>0)个元素a1 ,a2…ai… an的有限序列，其中ai或者是原子或者是一个广义表所以，广义表是一种递归数据结构，而线性表没有这种特性，线性表可以看成广义表的特殊情况，当ai都是原子时，广义表退化成线性表。

四、程序填空题1．在下面空格处填写适当的语句，以使下面的链式队列取出元素的算法完整 int write(LinkQueue *q) {QueueNode *p; if (q->front==q->rear)　 /*队空*/ {printf(“underflow”); exit(0);} while (q->front->next != NULL) {p=q->front->next; (1) q->front->next=p->next; printf(“%4d”,p->data); (2) free(p); } （3） q->rear=q->front ;　 /*队空时，头尾指针指向头结点*/ }五、综合题 1．设栈S和队列Q的初始状态为空，元素e1,e2,e3,e4,e5和e6依次通过S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2,e4,e3,e6,e5,e1，则栈S的容量至少应该是多少？答：出队序列是e2,e4,e3,e6,e5,e1的过程：⑴ e1入栈（栈底到栈顶元素是e1）⑵ e2入栈（栈底到栈顶元素是e1,e2）⑶ e2出栈（栈底到栈顶元素是e1）⑷ e3入栈（栈底到栈顶元素是e1,e3）⑸ e4入栈（栈底到栈顶元素是e1,e3,e4）⑹ e4出栈（栈底到栈顶元素是e1,e3）⑺ e3出栈（栈底到栈顶元素是e1）⑻ e5入栈（栈底到栈顶元素是e1,e5）⑼ e6入栈（栈底到栈顶元素是e1,e5,e6）⑽ e6出栈（栈底到栈顶元素是e1,e5）⑾ e5出栈（栈底到栈顶元素是e1）⑿ e1出栈（栈底到栈顶元素是空）栈中最多时有3个元素，所以栈S的容量至少是3。

2．假设用循环单链表实现循环队列，该队列只使用一个尾指针rear，其相应的存储结构和基本算法如下；（1）初始化队列initqueue(Q):建立一个新的空队列Q2）入队列enqueue(Q,x):将元素x插入到队列Q中3）出队列delqueue(Q):从队列Q中退出一个元素4）取队首元素gethead(Q):返回当前队首元素5）判断队列是否为空：emptyqueue(Q)6）显示队列中元素：dispqueue(Q)算法设计如下：/*只有一个指针rear的链式队的基本操作*/#include typedef char elemtype;struct node /*定义链队列结点*/ { elemtype data; struct node *next;};typedef struct queue /*定义链队列数据类型*/{ struct node *rear;} LinkQueue;void initqueue(LinkQueue *Q)/*初始化队列*/{ Q=(struct queue *)malloc(sizeof(struct queue)); Q->rear=NULL;} void enqueue(LinkQueue *Q,elemtype x) /*入队算法*/{ struct node *s,*p; s=(struct node *)malloc(sizeof(struct node)); s->data=x; if (Q->rear==NULL) /*原为空队时*/ { Q->rear=s; s->next=s; } else /*原队不为空时*/ { p=Q->rear->next; /*p指向第一个结点*/ Q->rear->next=s; /*将s链接到队尾*/ Q->rear=s; /*Q->rear指向队尾*/ s->next=p; }} void delqueue(LinkQueue *Q) /*出队算法*/{ struct node *t; if (Q->rear==NULL) { printf("队列为空!\n"); return(0); } else if (Q->rear->next==Q->rear) /*只有一个结点时*/ { t=Q->rear; Q->rear=NULL; } else /*有多个结点时*/ { t=Q->rear->next; /*t指向第一个结点*/ Q->rear->next=t->next; /*引成循环链*/ } free(t); } elemtype gethead(LinkQueue *Q) /*取队首元素算法*/ { if (Q->rear==NULL) printf("队列为空!\n"); else return(Q->rear->next->data); } int emptyqueue(LinkQueue *Q) /*判断队列是否为空算法*/ { if (Q->rear==NULL) return(1); /*为空,则返回true*/ else return(0); /*不为空,则返回flase*/ }void dispqueue(LinkQueue *Q) /*显示队列中元素算法*/{ struct node *p=Q->rear->next; printf("队列元素:"); while (p!=Q->rear) { printf("%c ",p->data); p=p->next; } printf("%c\n",p->data);}六、完成：实验2――栈、队列、递归程序设计根据实验要求（见教材P203）认真完成本实验，并提交实验报告。

数据结构（本）课程作业作业3（本部分作业覆盖教材第6-7章的内容）一、单项选择题1.假定一棵二叉树中，双分支结点数为15，单分支结点数为30，则叶子结点数为（ B ）A．15 B．16 C．17 D．472．二叉树第k层上最多有（ B ）个结点 A．2k B．2k-1 C．2k-1 D．2k-1 3．二叉树的深度为k,则二叉树最多有（ D ）个结点A．2k B．2k-1C．2k-1 D．2k-14. 设某一二叉树先序遍历为abdec，中序遍历为dbeac，则该二叉树后序遍历的顺序是（ C ） A．abdec B．debac C．debca D．abedc5．将含有150个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点的编号为1，则编号为69的结点的双亲结点的编号为（ B ）A．33 B．34 C．35 D．366．如果将给定的一组数据作为叶子数值，所构造出的二叉树的带权路径长度最小，则该树称为（ A ）。

A．哈夫曼树 B．平衡二叉树 C．二叉树 D．完全二叉树7．下列有关二叉树的说法正确的是（ A ）A．二叉树中度为0的结点的个数等于度为2的结点的个数加1B．二叉树中结点个数必大于0C．完全二叉树中，任何一个结点的度，或者为0或者为2 D．二叉树的度是28．在一棵度为3的树中，度为3的结点个数为2，度为2的结点个数为1，则度为0的结点个数为（ C ）A．4 B．5 C．6 D．79．在一棵度具有5层的满二叉树中结点总数为（ A ）A．31 B．32 C．33 D．1610. 利用n个值作为叶结点的权生成的哈夫曼树中共包含有( D )个结点 A. n B. n+1 C. 2*n D. 2*n-111. 利用3、6、8、12这四个值作为叶子结点的权，生成一棵哈夫曼树，该树中所有叶子的最长带权路径长度为( A ) A. 18 B. 16 C. 12 D. 3012．在一棵树中，（ C ）没有前驱结点。

A．分支结点 B．叶结点 C．树根结点 D．空结点13．在一棵二叉树中，若编号为i的结点存在右孩子，则右孩子的顺序编号为（ C ） A．2i B．2i-1 D．2i+1 C．2i+2 14．设一棵哈夫曼树共有n个叶结点，则该树有（ B ）个非叶结点 A．n B．n-1 C．n+1 D．2n15．设一棵有n个叶结点的二叉树，除叶结点外每个结点度数都为2，则该树共有（ B ）个结点 A．2n B．2n-1 C．2n+1 D．2n+2 16．在一个图G中，所有顶点的度数之和等于所有边数之和的（ C ）倍 A．1/2 B．1 C．2 D．4 17．在一个有像图中，所有顶点的入度之和等于所有顶点的出度之和的（ B ）倍 A．邻接矩阵表示法 B．邻接表表示法 C．逆邻接表表示法 D．邻接表和逆邻接表 18．在图的存储结构表示中，表示形式唯一的是（ C ）。

A．n B．n+1 C．n-1 D．n/219．一个具有n个顶点的无向完全图包含（ A ）条边 A．n（n-1） B．n（n+1） C． n（n-1）/2 D． n（n+1）/220．对于具有n个顶点的图，若采用邻接矩阵表示，则该矩阵的大小为（ B ） A．n B．n2 C．n-1 D．（n-1）221．对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则所有顶点邻接表中的结点总数为（ D ） A．n B．e C．2n D．2e22．在有向图的邻接表中，每个顶点邻接表链接着该顶点所有（ B ）邻接点 A．入边 B． 出边 C．入边和出边 D． 不是入边也不是出边 23．邻接表是图的一种（ B ） A．顺序存储结构 B．链式存储结构 C．索引存储结构 D．散列存储结构 24．如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是（ B ）。

A．完全图 B．连通图 C．有回路 D．一棵树25．下列有关图遍历的说法不正确的是（ C ）A．连通图的深度优先搜索是一个递归过程B．图的广度优先搜索中邻接点的寻找具有“先进先出”的特征C．非连通图不能用深度优先搜索法D．图的遍历要求每一顶点仅被访问一次 26．无向图的邻接矩阵是一个（ A ） A．对称矩阵 B． 零矩阵 C．上三角矩阵 D．对角矩阵27．图的深度优先遍历算法类似于二叉树的（ A ）遍历A．先序 B． 中序 C．后序 D．层次28．已知下图所示的一个图，若从顶点V1出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为（ C ） A．V1V2V4V8V3V5V6V7 B．V1V2V4V5V8V3V6V7 C．V1V2V4V8V5V3V6V7 D．V1V3V6V7V2V4V5V8V6V7V1V2V3V8V4V5　　　二、填空题1．结点的度是指结点所拥有的 子树树木或后继结点数 。

2．树的度是指 树中所有结点的度的最大值 3．度大于0的结点称作 分支结点 或 非终端结点 4．度等于0的结点称作 叶子结点 或 终端结点 5．在一棵树中，每个结点的 子树的根 或者说每个结点的 后继结点 称为该结点的 孩子结点 ，简称为孩子6．从根结点到该结点所经分支上的所有结点称为该结点的 祖先 7．树的深度或高度是指 树中结点的最大层数 8．具有n个结点的完全二叉树的深度是 9．先序遍历二叉树的的操作定义为；若二叉树为空，则为空操作，否则进行如下操作，访问二叉树的 根结点 ；先序遍历二叉树的 左子树 ，先序遍历二叉树的 右子树 10．中序遍历二叉树的的操作定义为；若二叉树为空，则为空操作，否则进行如下操作，中序遍历二叉树的 左子树 ；访问而叉树的 根结点 ，中序遍历二叉树的 右子树 11．后序遍历二叉树的的操作定义为；若二叉树为空，则为空操作，否则进行如下操作，后序遍历二叉树的 左子树 ；后序遍历二叉树的 右子树 ，访问而叉树的 根结点 。

12．将树中结点赋上一个有着某种意义的实数，称此实数为该结点的 权 13．树的带权路径长度为树中所有叶子结点的 带权路径长度之和 14．哈夫曼树又称为 最优二叉树 ，它是n个带权叶子结点构成的所有二叉树中带权路径长度WPL 最小的二叉树 15．若以4，5，6，7，8作为叶子结点的权值构造哈夫曼树，则其带权路径长度是 69 16．具有m个叶子结点的哈夫曼树共有 2m-1 结点17．在图中，任何两个数据元素之间都可能存在关系，因此图的数据元素之间是一种 多对多 的关系18．图的遍历是从图的某一顶点出发，按照一定的搜索方法对图中 所有顶点 各做 一次 访问的过程19．图的深度优先搜索遍历类似于树的 先序 遍历20．图的广度优先搜索类似于树的 按层次 遍历21．具有n个顶点的有向图的邻接矩阵，其元素个数为 n2 22．图常用的两种存储结构是 邻接矩阵 和 邻接表 23．在有n。