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

1、PAGE 2PAGE 46数据结构（本）形成性考核作业册使用说明本作业册是中央广播电视大学计算机科与技术专业（本科）数据结构（本）课程形成性考核的依据，与数据结构（本科）教材（李伟生主编，中央电大出版社出版）配套使用。数据结构（本）课程是中央广播电视大学计算机科学技术专业的一门统设必修、学位课程，4学分，共72学时。其中实验24学时，开设一学期。本课程的特点是综合性、实践性强，内容抽象，在专业中具有承上启下的作用。因此，在学习本课程时，要注意理论联系实际，结合教学内容进行上机实践，认真完成作业和实验内容。本课程的总成绩按百分制记分，其中形成性考核所占的比例为30%，终结性考试占70（闭卷，答题

2、时限为90分钟）。课程总成绩达到60分及以上者为合格，可以获得该课程的学分。本课程的学位课程学分为70分，即课程总成绩达到70分及以上者有资格申请专业学位。本课程共设计了4次形考作业，每次形考作业均包括实验内容，由各地电大根据学生对作业中各种题型练习和实验的完成情况进行考核。对于实验内容要求按实验要求认真完成，并提交实验报告。数据结构（本）课程作业作业1（本部分作业覆盖教材第1-2章的内容）一、单项选择题1在数据结构中，从逻辑上可以把数据结构分为（ ）。A动态结构和静态结构 B紧凑结构和非紧凑结构C线性结构和非线性结构D内部结构和外部机构2下列说法中，不正确的是（ ）。A数据元素是数据的基本单

3、位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算法的时间复杂度与（ ）有

4、关。A所使用的计算机 B与计算机的操作系统 C与算法本身 D与数据结构9设有一个长度为n的顺序表，要在第i个元素之前（也就是插入元素作为新表的第i个元素），则移动元素个数为（ ）。 An-i+1 Bn-i Cn-i-1 Di10设有一个长度为n的顺序表，要删除第i个元素移动元素的个数为（ ）。An-i+1 Bn-i Cn-i-1 Di11在一个单链表中，p、q分别指向表中两个相邻的结点，且q所指结点是p所指结点的直接后继，现要删除q所指结点，可用语句（ ）。Ap=q-next Bp-next=q Cp-next=qnext Dq-next=NULL12在一个单链表中p所指结点之后插入一个s所指

5、的结点时，可执行（ ）。 Ap-next= s; snext= pnext Bp-next=snext; Cp=s-next Ds-next=p-next; p-next=s;13非空的单向循环链表的尾结点满足（ ）（设头指针为head，指针p指向尾结点）。 A.P-next=NULL BP=NULL CP-next=head DP= head 14链表不具有的特点是（ ）。 A可随机访问任一元素 B插入删除不需要移动元素 C不必事先估计存储空间 D所需空间与线性表长度成正比15带头结点的链表为空的判断条件是（ ）（设头指针为head）。Ahead = =NULLBhead-next= =NU

6、LL Chead-next= =headDhead!=NULL16在一个单链表中，p、q分别指向表中两个相邻的结点，且q所指结点是p所指结点的直接后继，现要删除q所指结点，可用语句（ ）。Ap=q-nextBp-next=qCp-next=q-nextDq-next=NULL17在一个链队中，假设f和r分别为队头和队尾指针，则删除一个结点的运算为（ ）。Ar=f-next; Br=r-next; Cf=f-next; Df=r-next;18在一个链队中，假设f和r分别为队头和队尾指针，则插入s所指结点的运算为（ ）。Af-next=s; f=s; Br-next=s;r=s; Cs-next

7、=r;r=s; Ds-next=f;f=s;19.一个顺序表第一个元素的存储地址是90，每个元素的长度为2，则第6个元素的地址是（ ）。A98 B100 C102 D10620有关线性表的正确说法是（ ）。A每个元素都有一个直接前驱和一个直接后继 B线性表至少要求一个元素C表中的元素必须按由小到大或由大到下排序 D除了一个和最后一个元素外，其余元素都有一个且仅有一个直接前驱和一个直接后继二、填空题1在一个长度为n的顺序存储结构的线性表中，向第i(1in+1)个元素之前插入新元素时，需向后移动个数据元素。2从长度为n的采用顺序存储结构的线性表中删除第i(1in+1)个元素，需向前移动个元素。3数

8、据结构按结点间的关系，可分为4种逻辑结构：、。4数据的逻辑结构在计算机中的表示称为或。5除了第1个和最后一个结点外，其余结点有且只有一个前驱结点和后继结点的数据结构为，每个结点可有任意多个前驱和后继结点数的结构为。6算法的5个重要特性是、。7数据结构中的数据元素存在多对多的关系称为_ _结构。8数据结构中的数据元素存在一对多的关系称为_结构。9数据结构中的数据元素存在一对一的关系称为_结构。10要求在n个数据元素中找其中值最大的元素，设基本操作为元素间的比较。则比较的次数和算法的时间复杂度分别为_和 _ 。11在一个单链表中p所指结点之后插入一个s所指结点时，应执行_和p-next=s;的操作

9、。12设有一个头指针为head的单向循环链表，p指向链表中的结点，若p-next= =_，则p所指结点为尾结点。13在一个单向链表中，要删除p所指结点，已知q指向p所指结点的前驱结点。则可以用操作_。14设有一个头指针为head的单向链表，p指向表中某一个结点，且有p-next= =NULL,通过操作_,就可使该单向链表构造成单向循环链表。15每个结点只包含一个指针域的线性表叫。16线性表具有和两种存储结构。17数据的逻辑结构是从逻辑关系上描述数据，它与数据的关系无关，是独立于计算机的。18在双向循环链表的每个结点中包含指针域，其中next指向它的，prior指向它的，而头结点的prior指向

10、，尾结点的next指向。19单向循环链表是单向链表的一种扩充，当单向链表带有头结点时，把单向链表中尾结点的指针域由空指针改为；当单向链表不带头结点时，则把单向链表中尾结点的指针域由空指针改为指向。20线性链表的逻辑关系时通过每个结点指针域中的指针来表示的。其逻辑顺序和物理存储顺序不再一致，而是一种存储结构，又称为。三、问答题1简述数据的逻辑结构和存储结构的区别与联系，它们如何影响算法的设计与实现？2解释顺序存储结构和链式存储结构的特点，并比较顺序存储结构和链式存储结构的优缺点。3什么情况下用顺序表比链表好？4头指针、头结点、第一个结点（或称首元结点）的区别是什么？5解释带头结点的单链表和不带头

11、结点的单链表的区别。四、程序填空题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;inext=NULL; （2） ; for(i=1;idata=i;if(i=1) （3）; else（4） ;（5） ; return(head);3下列是在具有头结点单向列表中删除第i个结点，请在空格内填

12、上适当的语句。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） ;（2） ; free(p); return(1);五、完成：实验1线性表根据实验要求（见教材P201-202）认真完成本实验，并提交实验报告。数据结构（本）课程作业2（本部分作业覆盖教材第3-5章的内容）一、单项选择题1若让元素1，2，3依次进栈，则出栈顺序不可能为（ ）。A3，2，1 B2，1，3 C3，1，2 D1，3，22一个队列的入队序列是1，2，3，4

13、。则队列的输出序列是（ ）。A4，3，2，1 B1，2，3，4 C1，4，3，2 D3，2，4，13向顺序栈中压入新元素时，应当（ ）。A先移动栈顶指针，再存入元素 B先存入元素，再移动栈顶指针 C先后次序无关紧要 D同时进行4在一个栈顶指针为top的链栈中，将一个p指针所指的结点入栈，应执行（ ）。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保存被删结点的值，则执行（ ）。Ax=top;top=top

14、-next; Bx=top-data;Ctop=top-next; x=top-data;Dx=top-data; top=top-next;6一般情况下，将递归算法转换成等价的非递归算法应该设置（ ）。A栈 B队列C堆栈或队列D数组7表达式a*(b+c)-d的后缀表达式是（ ）。 Aabcd*+- Babc+*d- Cabc*+d- D-+*abcd8判断一个顺序队列sq（最多元素为m0）为空的条件是（ ）。 Asq-rear-sq-front=m0Bsq-rear-sq-front-1= =m0Csq-front=sq-rear Dsq-front=sq-rear+19判断一个循环队列Q（

15、最多元素为m0）为空的条件是（ ）。 AQ-front=Q-rear BQ-front!=Q-rear CQ-front=(Q-rear+1)% m0 DQ-front!=(Q-rear+1)%m010判断一个循环队列Q（最多元素为m0）为空的条件是（ ）。 AQ-front=Q-rear BQ-front!=Q-rear CQ-front=(Q-rear+1)% m0 DQ-front!=(Q-rear+1)% m011判断栈S满（元素个数最多n个）的条件是（ ）。 As-top=0 Bs-top!=0 Cs-top=n-1 Ds-top!=n-1 12一个队列的入队顺序是a,b,c,d，则

16、离队的顺序是（ ）。 Aa,d,cb Ba,b,c,d Cd,c,b,a Dc,b,d,a13如果以链表作为栈的存储结构，则退栈操作时（ ）。A必须判断栈是否满 B判断栈元素类型 C必须判断栈是否空 D对栈不作任何判断14在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入缓冲区中，而打印机则从缓冲区中取出数据打印，该缓冲区应该是一个（ ）结构。A堆栈 B队列 C数组 D先性表15一个递归算法必须包括（ ）。A递归部分B终止条件和递归部分 C迭代部分 D终止条件和迭代部分16从一个栈顶指针为top的链栈中删除一个结点时，用变量x保存被删结点的值，则

17、执行（ ）。 Ax=top-data; top=top-next; Bx=top-data; Ctop=top-next; x=top-data; Dtop=top-next; x=data;17在一个链队中，假设f和r分别为队头和队尾指针，则删除一个结点的运算为（ ）。 Ar=f-next; Br=r-next; Cf=f-next; Df=r-next;18在一个链队中，假设f和r分别为队头和队尾指针，则插入s所指结点的运算为（ ）。Af-next=s; f=s; Br-next=s;r=s; Cs-next=r;r=s; Ds-next=f;f=s;19.以下陈述中正确的是（ ）。A串是

18、一种特殊的线性表 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”，其子串的个数是（ ）。A9 B16 C 36 D2824下面关于串的叙述中，不正确的是（ ）。A串是字符的有限序列 B空串是由空格构成的串 C模式

19、匹配是串的一种重要运算 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

20、个元素的存储地址为100，则该数组的首地址是（ ）。A64 B28C70 D9030稀疏矩阵采用压缩存储的目的主要是（ ）。A表达变得简单 B对矩阵元素的存取变得简单 C去掉矩阵中的多余元素 D减少不必要的存储空间的开销31一个非空广义表的表头（ ）。 A不可能是原子 B只能是子表 C只能是原子 D可以是子表或原子 32常对数组进行的两种基本操作是（ ）。A建立与删除 B索引与、和修改C查找和修改 D查找与索引33.设二维数组A56按行优先顺序存储在内存中，已知A00起始地址为1000，每个数组元素占用5个存储单元，则元素A44的地址为（ ）。A1140 B1145 C 1120 D11253

21、4设有一个20阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素a9,2在一维数组B中的下标是（ ）。A41 B32 C18 D3835一个非空广义表的表头（ ）。A不可能是子表B只能是子表C只能是原子D可以是子表或原子二、填空题1栈是限定在表的一端进行插入和删除操作的线性表，又称为。2队列的特性是。3往栈中插入元素的操作方式是：先，后。4删除栈中元素的操作方式是：先，后。5循环队列队头指针在队尾指针位置，队列是“满”状态6在队列的顺序存储结构中，当插入一个新的队列元素时，尾指针，当删除一个元素队列时，头指针。7循环队列的引入，目

22、的是为了克服。8向顺序栈插入新元素分为三步：第一步进行判断，判断条件是；第二步是修改；第三步是把新元素赋给。同样从顺序栈删除元素分为三步：第一步进行判断，判断条件是。第二步是把；第三步。9假设以S和X分别表示入栈和出栈操作，则对输入序列a,b,c,d,e一系列栈操作SSXSXSSXXX之后，得到的输出序列为。10一个递归算法必须包括和。11判断一个循环队列LU（最多元素为m0）为空的条件是。12在将中缀表达式转换成后缀表达式和计算后缀表达式的算法中，都需要使用栈，对于前者，进入栈中的元素为表达式中的，而对于后者，进入栈的元素为，中缀表达式(a+b)/c-(f-d/c)所对应的后缀表达式是。16

23、向一个栈顶指针为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、阵两种。24设广义表L=（），（），则表头是，表尾是，L的长度是。25广义表A（a,b,c）,(d,e,f)）的表尾为。26两个串相等的充分必要条件是_。27设有n阶对称矩阵A，用数组s进行压缩存储，当ij时，A的数组元素aij相应于数组s的数组元素的下标为_ _。（数组元素的下标从1开始）28对稀疏矩阵进行压缩存储，矩阵中每个非零元素对应的三元组包括该元素的_、_和_三项信息。三、问答题1简述栈和一般线性表的区别。2简述队列和一般线性表的区别。3链栈中为何不设头结点？4利用一个栈，则：（1）如果输入序列由A，B，C组成，试给出全部可能的输出序列和不可能的输出序列。（2）如果输入序列由A，B，

25、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在下面空格处填写适当的语句，以使下面的循环队列的入队和出队算法完整。define TRUE 1;define FALSE

26、0;define MAXSIZE 100;typedef charelemtype;typedef structElemtype queue MAXSIZE; int front,rear;sequeuetype;Sequeuetype Q;int encqueue(sequeuetype*Q,elemtype x)if ( ( 1 ) )Printf(The cicular queue is full!n);return(FALSE);else (2) (3) return(TRUE); /*encqueue*/elemtype del_cqueue(sequeuetype *Q) if (

27、 (4) )Printf(The queue is empty !n) return(NULL); else (5) Return(Q-queueQ-front); /*del_cqueue*/ 2.在下面空格处填写适当的语句，以使下面的链式队列取出元素的算法完整。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) printf(“%4d”,p-data); (2

28、) （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）

29、判断队列是否为空：emptyqueue(Q)。（6）显示队列中元素：dispqueue(Q)。六、完成：实验2栈、队列、递归程序设计根据实验要求（见教材P203）认真完成本实验，并提交实验报告。数据结构（本）课程作业作业3（本部分作业覆盖教材第6-7章的内容）一、单项选择题1.假定一棵二叉树中，双分支结点数为15，单分支结点数为30，则叶子结点数为（ ）。A15 B16 C17 D472二叉树第k层上最多有（ ）个结点。 A2k B2k-1 C2k-1 D2k-13二叉树的深度为k,则二叉树最多有（ ）个结点。A2k B2k-1C2k-1 D2k-14.设某一二叉树先序遍历为abdec，中序遍

30、历为dbeac，则该二叉树后序遍历的顺序是（ ）。Aabdec Bdebac Cdebca Dabedc5树最适合于用来表示（ ）。A线性结构的数据B顺序结构的数据 C元素之间无前驱和后继关系的数据D元素之间有包含和层次关系的数据6设a,b为一棵二叉树的两个结点，在后续遍历中，a在b前的条件是（ ）。Aa在b上方 Ba在b下方 Ca在b左方 Da在b右方7权值为1，2，6，8的四个结点构成的哈夫曼树的带权路径长度是（ ）。A18 B28 C19 D298将含有150个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点的编号为1，则编号为69的结点的双亲结点的编号为（ ）。

31、A33 B34 C35 D369如果将给定的一组数据作为叶子数值，所构造出的二叉树的带权路径长度最小，则该树称为（ ）。A哈夫曼树 B平衡二叉树 C二叉树 D完全二叉树10下列有关二叉树的说法正确的是（ ）。A二叉树中度为0的结点的个数等于度为2的结点的个数加1B二叉树中结点个数必大于0C完全二叉树中，任何一个结点的度，或者为0或者为2 D二叉树的度是211在一棵度为3的树中，度为3的结点个数为2，度为2的结点个数为1，则度为0的结点个数为（ ）。A4 B5 C6 D712在一棵度具有5层的满二叉树中结点总数为（ ）。A31 B32 C33 D1613. 利用n个值作为叶结点的权生成的哈夫曼树

32、中共包含有( )个结点。 A. n B. n+1 C. 2*n D. 2*n-1 14. 利用n个值作为叶结点的权生成的哈夫曼树中共包含有( )个双支结点。 A. n B. n-1 C. n+1 D. 2*n-1 15. 利用3、6、8、12这四个值作为叶子结点的权，生成一棵哈夫曼树，该树中所有叶子的最长带权路径长度为( )。 A. 18 B. 16 C. 12 D. 3016在一棵树中，（ ）没有前驱结点。A分支结点 B叶结点 C树根结点 D空结点17在一棵二叉树中，若编号为i的结点存在右孩子，则右孩子的顺序编号为（ ）。 A2i B2i-1 D2i+1C2i+2 18设一棵哈夫曼树共有n个

33、叶结点，则该树有（ ）个非叶结点。An Bn-1 Cn+1 D2n19设一棵有n个叶结点的二叉树，除叶结点外每个结点度数都为2，则该树共有（ ）个结点。 A2n B2n-1 C2n+1 D2n+2 20一棵完全二叉树共有5层，且第5层上有六个结点，该树共有（ ）个结点。A20 B21 C23 D3021在一个图G中，所有顶点的度数之和等于所有边数之和的（ ）倍。 A1/2 B1 C2 D4 22在一个有像图中，所有顶点的入度之和等于所有顶点的出度之和的（ ）倍。 A邻接矩阵表示法 B邻接表表示法 C逆邻接表表示法 D邻接表和逆邻接表 23在图的存储结构表示中，表示形式唯一的是（ ）。 An B

34、n1 Cn1 Dn/224一个具有n个顶点的无向完全图包含（ ）条边。 An（n1） Bn（n1） C n（n1）/2 D n（n1）/225一个具有n个顶点的有向完全图包含（ ）条边。 An（n1） Bn（n1） C n（n1）/2 D n（n1）/226对于具有n个顶点的图，若采用邻接矩阵表示，则该矩阵的大小为（ ）。 An Bn2 Cn1 D（n1）227对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为（ ）。 An Be C2n D2e28对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则所有顶点邻接表中的结点总数为（ ）。 An Be C2n D2e

35、29在有向图的邻接表中，每个顶点邻接表链接着该顶点所有（ ）邻接点。 A入边 B 出边 C入边和出边 D 不是入边也不是出边 30在有向图的逆邻接表中，每个顶点邻接表链接着该顶点所有（ ）邻接点。 A入边 B出边 C入边和出边 D不是入边也不是出边31邻接表是图的一种（ ）。 A顺序存储结构 B链式存储结构 C索引存储结构 D散列存储结构 32如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是（ ）。 A完全图 B连通图 C有回路 D一棵树33下列有关图遍历的说法不正确的是（ ）。A连通图的深度优先搜索是一个递归过程B图的广度优先搜索中邻接点的寻找具有“先进先出”的特

36、征C非连通图不能用深度优先搜索法D图的遍历要求每一顶点仅被访问一次 34无向图的邻接矩阵是一个（ ）。 A对称矩阵 B 零矩阵 C上三角矩阵 D对角矩阵35图的深度优先遍历算法类似于二叉树的（ ）遍历。A先序 B 中序 C后序 D层次36已知下图所示的一个图，若从顶点V1出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为（ ）。AV1V2V4V8V3V5V6V7BV1V2V4V5V8V3V6V7CV1V2V4V8V5V3V6V7 DV1V3V6V7V2V4V5V8VV6V7V1V2V3V8V4V5二、填空题1结点的度是指结点所拥有的。2树的度是指。3度大于0的结点称作或。4度等于0的结

37、点称作或。5在一棵树中，每个结点的或者说每个结点的称为该结点的，简称为孩子。6一个结点称为其后继结点的。7具有的结点互称为兄弟结点，简称为兄弟。8每个结点的所有子树中的结点被称为该结点的。9从根结点到该结点所经分支上的所有结点称为该结点的 。10树的深度或高度是指。11m(m0)棵互不相交的树的集合称为。12度为k的树中的第i层上最多有结点。13深度为k的二叉树最多有结点。14在一棵二叉树中，如果树中的每一层都是满的，则称此树为；但如果出最后一层外，其余层都是满的，并且最后一层是满的，或者是在缺少若干连续个结点，则称此二叉树为。15具有n个结点的完全二叉树的深度是。16先序遍历二叉树的的操作定

38、义为；若二叉树为空，则为空操作，否则进行如下操作，访问二叉树的；先序遍历二叉树的，先序遍历二叉树的。 17中序遍历二叉树的的操作定义为；若二叉树为空，则为空操作，否则进行如下操作，中序遍历二叉树的；访问而叉树的，中序遍历二叉树的。18后序遍历二叉树的的操作定义为；若二叉树为空，则为空操作，否则进行如下操作，后序遍历二叉树的；后序遍历二叉树的，访问而叉树的。19将树中结点赋上一个有着某种意义的实数，称此实数为该结点的。20树的带权路径长度为树中所有叶子结点的。21哈夫曼树又称为，它是n个带权叶子结点构成的所有二叉树中带权路径长度WPL。22若以4，5，6，7，8作为叶子结点的权值构造哈夫曼树，则

39、其带权路径长度是。23具有m个叶子结点的哈夫曼树共有结点。24在图中，任何两个数据元素之间都可能存在关系，因此图的数据元素之间是一种的关系。25图的邻接矩阵表示法是用一个来表示图中顶点之间的相邻关系。26邻接表是图中的每个顶点建立一个邻接关系的。27图的遍历是从图的某一顶点出发，按照一定的搜索方法对图中各做访问的过程。28图的深度优先搜索遍历类似于树的遍历。29图的广度优先搜索类似于树的遍历。30具有n个顶点的有向图的邻接矩阵，其元素个数为。30具有n个顶点的无向图至少有条边，才能确保其为一个连通图。31图常用的两种存储结构是和。32一个AOV网（顶点活动图）应该是一个。即不应该带有回路，否则

40、回路上的所有活动都。33用邻接矩阵存储有向图G，其第i行的所有元素之和等于顶点i的。34在有n个顶点的有向图中，每个顶点的度最大可达。35在一个带权图中，两顶点之间的最段路径最多经过条边。36为了实现图的深度优先搜索遍历，其非递归的算法中需要使用的一个辅助数据结构为。三、综合题1写出如下图所示的二叉树的先序、中序和后序遍历序列。aajfghidceb2已知某二叉树的先序遍历结果是：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个结点，求树的

41、高度叶子结点数单支结点数最后一个非终端结点的序号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描述如下

42、：G=（V，E）V=V1，V2，V3，V4，V5E=（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的结点所在的层号，请在划有横线的地

43、方填写合适内容。int NodeLevel(struct BinTreeNode* BT, char X)if(BT=NULL) return 0; /*空树的层号为0*/else if(BT-data=X) return 1; /*根结点的层号为1*/*向子树中查找X结点*/else int c1=NodeLevel(BT-left,X);if(c1=1) _(1)_; int c2=_(2)_; if _(3)_; /若树中不存在X结点则返回0else return 0;2. 下面函数的功能是按照图的深度优先搜索遍历的方法，输出得到该图的生成树中的各条边，请在划有横线的地方填写合适内容。

44、void dfstree(adjmatrix GA, int i, int n) int j; visitedi=1; (1) if(GAij!=0 & GAij!=MaxValue & !visitedj) printf(%d,%d)%d,i,j,GAij); (2) 五、算法设计题1写一个将一棵二叉树复制给另一棵二叉树的算法。 2根据下面函数声明编写出求一棵二叉树中叶子结点总数的算法，该总数值由函数返回。假定参数BT初始指向二叉树的根结点。 int BTreeLeafCount(struct BTreeNode* BT);3已知有n个顶点的有向图邻接表，设计算法分别实现下列功能：（1）求出

45、图G中每个顶点的出度、入度。（2）计算图中度为0的顶点数。六、完成：实验3栈、队列、递归程序设计 实验4图的存储方式和应用根据实验要求（见教材P203）认真完成本实验，并提交实验报告。数据结构（本）课程作业（4）（本部分作业覆盖教材第8-9章的内容）一、单项选择题1.顺序查找方法适合于存储结构为（ ）的线性表。A散列存储 B索引存储 C散列存储或索引存储 D顺序存储或链接存储2对线性表进行二分查找时，要求线性表必须（ ）。 A以顺序存储方式 B以链接存储方式 C以顺序存储方式 ，且数据元素有序 D以链接存储方式，且数据元素有序 3如果要求一个线性表既能较快地查找，又能动态适应变化要求，可以采用

46、（ ）查找方法。A顺序 B分块C折半 D散列4.对于一个线性表，若要求既能进行较快地插入和删除，又要求存储结构能够反映数据元素之间的逻辑关系，则应该（ ）。A以顺序存储方式 B以链接存储方式 C以索引存储方式 D以散列存储方式5采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为（ ）。An Bn/2 C(n+1)/2 D(n-1)/2 6采用折半查找方法查找长度为n的线性表时，每个元素的平均查找长度为（ ）。AO(n*n) BO(nlog2n) CO(n) Ds(log2n)7哈希函数有一个共同的性质，即函数值应当以（ ）取其值域的每个值。A最大概率 B最小概率 C平均概率 D同

47、等概率8有一个长度为10的有序表，按折半查找对该表进行查找，在等概率情况下查找成功的平均比较次数为（ ）。A29/10 B31/10 C26/10 D29/99已知一个有序表为11,22,33,44,55,66,77,88,99，则顺序查找元素55需要比较（ ）次。A3 B4 C5 D610顺序查找法与二分查找法对存储结构的要求是（ ）。A顺序查找与二分查找均只是适用于顺序表B顺序查找与二分查找均既适用于顺序表，也适用于链表C顺序查找只是适用于顺序表 D二分查找适用于顺序表11有数据53,30,37,12,45,24,96，从空二叉树开始逐个插入数据来形成二叉排序树，若希望高度最小，应该选择的

48、序列是（ ）。A45,24,53,12,37,96,30 B37,24,12,30,53,45,96 C12,24,30,37,45,53,96 D30,24,12,37,45,96,5312对有18个元素的有序表作二分（折半）查找，则查找A3的比较序列的下标可能为（ ）。A1、2、3 B9、5、2、3 C9、5、3 D9、4、2、313. 对于顺序存储的有序表5，12，20，26，37，42，46，50，64，若采用折半查找，则查找元素26的比较次数是（ ）。 A.3 B. 3 C. 4 D.5 14.关于哈希查找的说法正确的是（ ）。 A.除留余数法是最好的B. 哈希函数的好坏要根据具体情

49、况而定C.删除一个元素后，不管用哪种方法处理冲突，都只需简单地把该元素删除掉D.因为冲突是不可避免的，所以装填因子越小越好 15.在所有的排序方法中，关键字比较的次数与记录初始排列秩序无关的是（ ）。 A. 冒泡排序B. 希尔排序 C. 直接选择排序 D. 直接插入排序 16.从未排序序列中依次取出元素与已经排好序的序列中的元素作比较。将其放入已排序序列的正确的位置上，此方法称为（ ）A. 插入排序B. 选择排序 C. 交换排序D. 归并排序 17.从未排序序列中挑选元素，并将其放入已排序序列的一端，此方法称为（ ）。A. 插入排序B. 交换排序 C. 选择排序D. 归并排序 18.依次将每两

50、个相邻的有序表合并成一个有序表的排序方法称为（ ）。A. 插入排序B. 交换排序 C. 选择排序D. 归并排序 19.当两个元素出现逆序的时候就交换位置，这种排序方法称为（ ）。A. 插入排序B. 交换排序 C. 选择排序D. 归并排序 20.每次把待排序的区间划分为左、右两个子区间，其中左区间中记录的关键字均小于等于基准记录的关键字，右区间中记录的关键字均大于等于基准记录的关键字，这种排序称为（ ）。A. 插入排序B. 快速排序 C. 堆排序D. 归并排序 21.在正常情况下，直接插入排序的时间复杂度为（ ）。A. O(log2n)B. O(n) C. O(n log2n) D. O(n2)

51、 22.在正常情况下，冒泡排序的时间复杂度为（ ）。A. O(log2n)B. O(n) C. O(n log2n) D. O(n2) 23.在归并排序中，归并趟数的数量级为（ ）。A. O(log2n)B. O(n) C. O(n log2n) D. O(n2) 24.在待排序元素基本有序的情况下，效率最高的排序方法是（ ）。A. 插入排序B. 快速排序 C. 堆排序D. 归并排序 25.下面几种排序方法中，要求内存量最大的是（ ）。A. 插入排序B. 交换排序 C. 选择排序D. 归并排序 26.在下列排序方法中，关键字比较的次数与记录的初始排列秩序无关的是（ ）。 A.希尔排序B. 冒泡

52、排序 C. 插入排序 D. 选择排序27.快速排序方法在（ ）情况下最不利于发挥其长处。A.要排序的数据量太大B. 要排序的数据中含有多个相同值 C. 要排序的数据已基本有序 D. 要排序的数据个数为奇数 28.下述几种排序方法中，平均情况下占用内存量最大的是（ ）方法。A. 插入排序B. 选择排序 C. 快速排序D. 归并排序29.若构造一棵具有n个结点的二叉树排序，在最坏的情况下，其深度不会超过（ ）。A. n/2B. n C. (n1)/2D. n1 30.对数据元素序列（49，72，68，13，38，50，97，27）进行排序，前三趟排序结果时的结果依次为第一趟：49，72，68，13

53、，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-1 B. n C. n+1 D.log2n 32.对序列（49，38，65，97，76，13，47，50）采用直接插入排序法进行排序，要把第七个元素47插入到已排序中，为寻找插入的合适位置需要进行（）次元素间的比较。A. 3B. 4 C. 5 D. 633.下面四种排序方法中，（）是一种稳

54、定性排序方法。A. 插入排序法B. 选择排序法 C.快速排序法D.希尔排序法34一组记录的关键字序列为（46，79，56，38，40，84），利用快速排序，以第一个关键字为分割元素，经过一次划分后结果为（ ）。 A40，38，46，79，56，84 B40，38，46，84，56，79C40，38，46，56，79，84 D38，40，46，56，79，8435一组记录的关键字序列为（46，79，56，38，40，84），利用堆排序的方法建立的初始堆为（ ）。A79，46，56，38，40，84 B84，79，56，38，40，46C84，79，56，46， 40，38， D84，56，79，

55、40，46，38 36一组记录的关键字序列为（25，48，16，35，79，82，23，40，36，72），其中，含有5个长度为2的有序表，按归并排序的方法对该序列进行一趟归并后的结果为（ ）。A16，25，35，48，23，40，79，82，36，72B16，25，35，48，79，82，23，36，40，72C16，25，48，35，79，82，23，36，40，72D16，25，35，48，79，23，36，40，82，72 37已知10个数据元素为（54，28，16，34，73，62，95，60，26，43），对该数列从小到到大排序，经过一趟冒泡排序后的序列为（ ）。A16，28，34

56、，54，73，62，60，26，43，95 B28，16，34，54，62，73，60，26，43，95C28，16，34，54，62，60，73，26，43，95D16，28，34，54，62，60，73，26，43，95 38用某种排序的方法对线性表（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如果对查找表只进行查询某个特定的数据元素是否在查找表中，以及查找某个特定数据元素的各种