资源描述
数据结构（本）课程作业作业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 ）。 An-i+1 Bn-i Cn-i-1 Di10设有一个长度为n的顺序表，要删除第i个元素移动元素的个数为（ B ）。 An-i+1 Bn-i Cn-i-1 Di11在一个单链表中，p、q分别指向表中两个相邻的结点，且q所指结点是p所指结点的直接后继，现要删除q所指结点，可用语句（ C ）。 Ap=q-next Bp-next=q Cp-next=qnext Dq-next=NULL12在一个单链表中p所指结点之后插入一个s所指的结点时，可执行（ D ）。 Ap-next= s; snext= pnext Bp-next=snext; Cp=s-next Ds-next=p-next; p-next=s;13非空的单向循环链表的尾结点满足（C ）（设头指针为head，指针p指向尾结点）。 A.P-next= =NULL BP= =NULL CP-next= =head DP= = head 14链表不具有的特点是（ A ）。 A可随机访问任一元素 B插入删除不需要移动元素 C不必事先估计存储空间 D所需空间与线性表长度成正比15带头结点的链表为空的判断条件是（B ）（设头指针为head）。Ahead = =NULLBhead-next= =NULL Chead-next= =headDhead!=NULL16在一个单链表中，p、q分别指向表中两个相邻的结点，且q所指结点是p所指结点的直接后继，现要删除q所指结点，可用语句（C ）。Ap=q-nextBp-next=qCp-next=q-nextDq-next=NULL17在一个链队中，假设f和r分别为队头和队尾指针，则删除一个结点的运算为（C ）。 Ar=f-next; Br=r-next; Cf=f-next; Df=r-next;18在一个链队中，假设f和r分别为队头和队尾指针，则插入s所指结点的运算为（ B ）。 Af-next=s; f=s; Br-next=s;r=s; Cs-next=r;r=s; Ds-next=f;f=s;19.一个顺序表第一个元素的存储地址是90，每个元素的长度为2，则第6个元素的地址是（B ）。A98 B100 C102 D10620有关线性表的正确说法是（ 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;idata=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;idata=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 ）。A3，2，1 B2，1，3 C3，1，2 D1，3，22一个队列的入队序列是1，2，3，4。则队列的输出序列是（ B ）。A4，3，2，1 B1，2，3，4 C1，4，3，2 D3，2，4，13向顺序栈中压入新元素时，应当（ A ）。A先移动栈顶指针，再存入元素 B先存入元素，再移动栈顶指针 C先后次序无关紧要 D同时进行4在一个栈顶指针为top的链栈中，将一个p指针所指的结点入栈，应执行（ C ）。Atop-next=p; Bp-next=top-next; top-next=p;Cp-next=top; top=p; Dp-next=top-next; top=top-next;5在一个栈顶指针为top的链栈中删除一个结点时，用 x保存被删结点的值，则执行（ B ）。Ax=top;top=top-next; Bx=top-data;Ctop=top-next; x=top-data; Dx=top-data; top=top-next;6一般情况下，将递归算法转换成等价的非递归算法应该设置（ A ）。A栈 B队列C堆栈或队列 D数组7表达式a*(b+c)-d的后缀表达式是（ B ）。 Aabcd*+- Babc+*d- Cabc*+d- D-+*abcd8判断一个顺序队列sq（最多元素为m0）为空的条件是（ C ）。 Asq-rear-sq-front= m0 Bsq-rear-sq-front-1= = m0 Csq-front=sq-rear Dsq-front=sq-rear+19判断一个循环队列Q（最多元素为m0）为空的条件是（ A ）。 AQ-front=Q-rear BQ-front!=Q-rear CQ-front=(Q-rear+1)% m0 DQ-front!= (Q-rear+1)%m0 10判断栈S满（元素个数最多n个）的条件是（C ）。 As-top=0 Bs-top!=0 Cs-top=n-1 Ds-top!=n-1 11一个队列的入队顺序是a,b,c,d，则离队的顺序是（ B ）。 Aa,d,cb Ba,b,c,d Cd,c,b,a Dc,b,d,a12如果以链表作为栈的存储结构，则退栈操作时（ C ）。 A必须判断栈是否满 B判断栈元素类型 C必须判断栈是否空 D对栈不作任何判断13在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入缓冲区中，而打印机则从缓冲区中取出数据打印，该缓冲区应该是一个（ B ）结构。A堆栈 B队列 C数组 D先性表14一个递归算法必须包括（ B ）。A递归部分B终止条件和递归部分 C迭代部分 D终止条件和迭代部分15从一个栈顶指针为top的链栈中删除一个结点时，用变量x保存被删结点的值，则执行（ A ）。 Ax=top-data; top=top-next; Bx=top-data; Ctop=top-next; x=top-data; Dtop=top-next; x=data;16在一个链队中，假设f和r分别为队头和队尾指针，则删除一个结点的运算为（C ）。 Ar=f-next; Br=r-next; Cf=f-next; Df=r-next;17在一个链队中，假设f和r分别为队头和队尾指针，则插入s所指结点的运算为（B ）。 Af-next=s; f=s; Br-next=s;r=s; Cs-next=r;r=s; Ds-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 ）。 A9 B16 C 36 D2823串与普通的线性表相比较，它的特殊性体现在（ 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 ）。A64 B28C70 D9028稀疏矩阵采用压缩存储的目的主要是（D ）。A表达变得简单 B对矩阵元素的存取变得简单 C去掉矩阵中的多余元素 D减少不必要的存储空间的开销29一个非空广义表的表头（ C ）。 A不可能是原子 B只能是子表 C只能是原子 D可以是子表或原子 30常对数组进行的两种基本操作是（ C ）。A建立与删除 B索引与、和修改C查找和修改 D查找与索引31. 设二维数组A56按行优先顺序存储在内存中，已知A00 起始地址为1000，每个数组元素占用5个存储单元，则元素A44的地址为（ A ）。 A1140 B1145 C 1120 D112532设有一个20阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素a9,2在一维数组B中的下标是（ D ）。A41 B32 C18 D38二、填空题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出，输出序列为ABC。A入，A出，B入，C入，C出，B出，输出序列为ACB。A入，B入，B出，A出，C入，C出，输出序列为BAC。A入，B入，B出，C入，C出，A出，输出序列为BCA。A入，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出栈，输出序列为：CDBAE。（2）B出栈，E入栈，E出栈，A 出栈，输出序列为CDBEA。（3）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(n0)个元素a1 ,a2ai 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):建立一个新的空队列Q。（2）入队列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(%cn,p-data);六、完成：实验2栈、队列、递归程序设计根据实验要求（见教材P203）认真完成本实验，并提交实验报告。数据结构（本）课程作业作业3（本部分作业覆盖教材第6-7章的内容）一、单项选择题1.假定一棵二叉树中，双分支结点数为15，单分支结点数为30，则叶子结点数为（ B ）。A15 B16 C17 D472二叉树第k层上最多有（ B ）个结点。 A2k B2k-1 C2k-1 D2k-1 3二叉树的深度为k,则二叉树最多有（ D ）个结点。A2k B2k-1C2k-1 D2k-14. 设某一二叉树先序遍历为abdec，中序遍历为dbeac，则该二叉树后序遍历的顺序是（ C ）。 Aabdec Bdebac Cdebca Dabedc5将含有150个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点的编号为1，则编号为69的结点的双亲结点的编号为（ B ）。A33 B34 C35 D366如果将给定的一组数据作为叶子数值，所构造出的二叉树的带权路径长度最小，则该树称为（ A ）。A哈夫曼树 B平衡二叉树 C二叉树 D完全二叉树7下列有关二叉树的说法正确的是（ A ）。A二叉树中度为0的结点的个数等于度为2的结点的个数加1B二叉树中结点个数必大于0C完全二叉树中，任何一个结点的度，或者为0或者为2 D二叉树的度是28在一棵度为3的树中，度为3的结点个数为2，度为2的结点个数为1，则度为0的结点个数为（ C ）。A4 B5 C6 D79在一棵度具有5层的满二叉树中结点总数为（ A ）。A31 B32 C33 D1610. 利用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 ）。 A2i B2i-1 D2i+1 C2i+2 14设一棵哈夫曼树共有n个叶结点，则该树有（ B ）个非叶结点。 An Bn-1 Cn+1 D2n15设一棵有n个叶结点的二叉树，除叶结点外每个结点度数都为2，则该树共有（ B ）个结点。 A2n B2n-1 C2n+1 D2n+2 16在一个图G中，所有顶点的度数之和等于所有边数之和的（ C ）倍。 A1/2 B1 C2 D4 17在一个有像图中，所有顶点的入度之和等于所有顶点的出度之和的（ B ）倍。 A邻接矩阵表示法 B邻接表表示法 C逆邻接表表示法 D邻接表和逆邻接表 18在图的存储结构表示中，表示形式唯一的是（ C ）。 An Bn+1 Cn-1 Dn/219一个具有n个顶点的无向完全图包含（ A ）条边。 An（n-1） Bn（n+1） C n（n-1）/2 D n（n+1）/220对于具有n个顶点的图，若采用邻接矩阵表示，则该矩阵的大小为（ B ）。 An Bn2 Cn-1 D（n-1）221对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则所有顶点邻接表中的结点总数为（ D ）。 An Be C2n D2e22在有向图的邻接表中，每个顶点邻接表链接着该顶点所有（ 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 ）。 AV1V2V4V8V3V5V6V7 BV1V2V4V5V8V3V6V7 CV1V2V4V8V5V3V6V7 DV1V3V6V7V2V4V5V8V6V7V1V2V3V8V4V5二、填空题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
展开阅读全文