数据结构(本)形考作业答案解析.doc

《数据结构(本)形考作业答案解析.doc》由会员分享，可在线阅读，更多相关《数据结构(本)形考作业答案解析.doc（46页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、-/形考作业一题目1把数据存储到计算机中，并具体体现数据元素间的逻辑结构称为（ ）。选择一项：A. 逻辑结构B. 给相关变量分配存储单元C. 算法的具体实现D. 物理结构题目2下列说法中，不正确的是（ ）。选择一项：A. 数据可有若干个数据元素构成B. 数据元素是数据的基本单位C. 数据项是数据中不可分割的最小可标识单位D. 数据项可由若干个数据元素构成题目3一个存储结点存储一个（ ）。选择一项：A. 数据结构B. 数据类型C. 数据项D. 数据元素题目4数据结构中，与所使用的计算机无关的是数据的（ ）。选择一项：A. 物理结构B. 逻辑结构C. 物理和存储结构D. 存储结构题目5下列的叙述中

2、，不属于算法特性的是（ ）。选择一项：A. 有穷性B. 可行性C. 可读性D. 输入性题目6正确获得2.00分中的2.00分A. 研究算法中的输入和输出的关系B. 分析算法的易懂性和文档性C. 分析算法的效率以求改进D. 找出数据结构的合理性题目7算法指的是（ ）。选择一项：A. 排序方法B. 解决问题的计算方法C. 计算机程序D. 解决问题的有限运算序列题目8算法的时间复杂度与（ ）有关。选择一项：A. 所使用的计算机B. 数据结构C. 算法本身D. 计算机的操作系统题目9设有一个长度为n的顺序表，要在第i个元素之前（也就是插入元素作为新表的第i个元素），插入一个元素，则移动元素个数为（ ）

3、。选择一项：A. n-i+1B. n-i-1C. n-iD. i题目10设有一个长度为n的顺序表，要删除第i个元素移动元素的个数为（ ）。选择一项：A. n-iB. n-i-1C. n-i+1D. i题目11在一个单链表中，p、q分别指向表中两个相邻的结点，且q所指结点是p所指结点的直接后继，现要删除q所指结点，可用语句（ ）。选择一项：A. p-next=q-nextB. p=q-nextC. q-next=NULLD. p-next=q题目12在一个单链表中p所指结点之后插入一个s所指的结点时，可执行（ ）。选择一项：A. p=s-nextB. p-next= s; s-next= p-n

4、extC. p-next=s-next;D. s-next=p-next; p-next=s;题目13非空的单向循环链表的尾结点满足（ ）（设头指针为head，指针p指向尾结点）。选择一项：A. p= headB. p=NULLC. p-next=headD. p-next=NULL题目14链表不具有的特点是（ ）。选择一项：A. 可随机访问任一元素B. 插入删除不需要移动元素C. 不必事先估计存储空间D. 所需空间与线性表长度成正比题目15带头结点的链表为空的判断条件是（ ）（设头指针为head）。选择一项：A. head-next=NULLB. head-next=headC. head

5、=NULLD. head!=NULL题目16在一个长度为n的顺序表中为了删除第5个元素，由第6个元素开始从后到前依次移动了15个元素。则原顺序表的长度为（ ）。选择一项：A. 21B. 19C. 20D. 25题目17有关线性表的正确说法是（ ）。选择一项：A. 表中的元素必须按由小到大或由大到下排序B. 除了一个和最后一个元素外，其余元素都有一个且仅有一个直接前驱和一个直接后继C. 线性表至少要求一个元素D. 每个元素都有一个直接前驱和一个直接后继题目18向一个有127个元素的顺序表中插入一个新元素，并保持原来的顺序不变，平均要移动（ ）个元素。选择一项：A. 8B. 7C. 63D. 63

6、.5题目19一个顺序表第一个元素的存储地址是90，每个元素的长度为2，则第6个元素的地址是（ ）。选择一项：A. 102B. 98C. 100D. 106题目20在双向循环链表中，在p所指的结点之后插入指针f所指的新结点，其操作步骤是（ ）。选择一项：A. f-prior=p; f-next=p-next; p-next=f;p-next-prior=f;B. p-next=f;f-prior=p;p-next-prior=f;f-next=p-next;C. f-prior=p; f-next=p-next; p-next-prior=f; p-next=f;D. p-next=f; p-n

7、ext-prior=f;f-prior=p;f-next=p-next;二、填空题（每小题2分，共30分）题目21在一个长度为n的顺序存储结构的线性表中，向第i(1in+1)个元素之前插入新元素时，需向后移动回答个数据元素。题目22从长度为n的采用顺序存储结构的线性表中删除第i(1in+1)个元素，需向前移动回答个元素。题目23数据结构按结点间的关系，可分为4种逻辑结构：_集合_、_线性结构、_、_树形结构_、_图状结构_。题目24数据的逻辑结构在计算机中的表示称为_存储结构_或_物理结构_。题目25除了第1个和最后一个结点外，其余结点有且只有一个前驱结点和后继结点的数据结构为回答，每个结点可

8、有任意多个前驱和后继结点数的结构为回答。答案：线性结构，非线性结构题目26数据结构中的数据元素存在多对多的关系称为回答结构。题目27数据结构中的数据元素存在一对多的关系称为回答结构。题目28数据结构中的数据元素存在一对一的关系称为回答结构。题目29要求在n个数据元素中找其中值最大的元素，设基本操作为元素间的比较。则比较的次数和算法的时间复杂度分别为_ n-1_和_ O(n)_。题目30在一个单链表中p所指结点之后插入一个s所指结点时，应执行回答和p-next=s;的操作。题目31设有一个头指针为head的单向循环链表，p指向链表中的结点，若p-next=回答，则p所指结点为尾结点。题目32在一

9、个单向链表中，要删除p所指结点，已知q指向p所指结点的前驱结点。则可以用操作回答。正确答案是：q-next=p-next;题目33设有一个头指针为head的单向链表，p指向表中某一个结点，且有p-next= =NULL，通过操作回答，就可使该单向链表构形成单向循环链表。正确答案是：p-next=head;题目34单向循环链表是单向链表的一种扩充，当单向链表带有头结点时，把单向链表中尾结点的指针域由空指针改为回答；当单向链表不带头结点时，则把单向链表中尾结点的指针域由空指针改为指向回答。答案：头结点的指针、指向第一个结点的指针题目35线性链表的逻辑关系是通过每个结点指针域中的指针来表示的。其逻辑

10、顺序和物理存储顺序不再一致，而是一种回答存储结构，又称为回答。答案：链式、链表三、问答题（第1小题7分，第2小题8分）题目36简述数据的逻辑结构和存储结构的区别与联系，它们如何影响算法的设计与实现？答：若用结点表示某个数据元素，则结点与结点之间的逻辑关系就称为数据的逻辑结构。数据在计算机中的存储表示称为数据的存储结构。可见，数据的逻辑结构是反映数据之间的固有关系，而数据的存储结构是数据在计算机中的存储表示。尽管因采用的存储结构不同，逻辑上相邻的结点，其物理地址未必相同，但可通过结点的内部信息，找到其相邻的结点，从而保留了逻辑结构的特点。采用的存储结构不同，对数据的操作在灵活性，算法复杂度等方面

11、差别较大。题目37解释顺序存储结构和链式存储结构的特点，并比较顺序存储结构和链式存储结构的优缺点。答：顺序结构存储时，相邻数据元素的存放地址也相邻，即逻辑结构和存储结构是统一的，要求内存中存储单元的地址必须是连续的。优点：一般情况下，存储密度大，存储空间利用率高。缺点：（1）在做插入和删除操作时，需移动大量元素；（2）由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用；（3）表的容量难以扩充。链式结构存储时，相邻数据元素可随意存放，所占空间分为两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。优点：插入和删除元素时很方便，使用灵活。缺点：存储密度小，存储空间利用率低

12、。四、程序填空题（每空1分，共15分）题目38下列是用尾插法建立带头结点的且有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; 回答; for(i=1;idata=i; if(i=1) 回答; else 回答; 回答; return(head); 题目40下列是在具有头结点单向链表中删除第i个

13、结点的算法，请在空格内填上适当的语句。 int delete(NODE *head,int i) NODE *p,*q; int j; q=head; j=0; while(q!=NULL)&(ji-1) /*找到要删除结点的直接前驱，并使q指向它*/ 回答; j+; if(q=NULL) return(0); 回答 回答; free(p); return(1); 题目41下列是在具有头结点单向列表中在第i个结点之前插入新结点的算法，请在空格内填上适当的语句。 int insert(NODE *head,int x,int i) NODE *q,*p; int j; q=head; j=0;

14、while(q!=NULL)&(jnext;j+; if(q=NULL) return(0); p=回答; p-data=x; 回答正确正确答案是：p-next=q-next获得1.00分中的1.00分; 回答; return(1); 形考任务2题目1若让元素1，2，3依次进栈，则出栈顺序不可能为（ ）。选择一项：A. 2，1，3B. 3，1，2C. 3，2，1题目2一个队列的入队序列是1，2，3，4。则队列的输出序列是（ ）。选择一项：A. 3，2，4，1B. 1，2，3，4C. 4，3，2，1D. 1，4，3，2题目3向顺序栈中压入新元素时，应当（ ）。选择一项：A. 先存入元素，再移动栈

15、顶指针B. 先移动栈顶指针，再存入元素C. 先后次序无关紧要D. 同时进行题目4在一个栈顶指针为top的链栈中，将一个p指针所指的结点入栈，应执行（ ）。选择一项：A. p-next=top;top=p;B. top-next=p;C. p-next=top-next;top=top-next;D. p-next=top-next;top-next=p;题目5在一个栈顶指针为top的链栈中删除一个结点时，用 x保存被删结点的值，则执行（ ）。选择一项：A. x=top-data;top=top-next;B. x=top-data;C. top=top-next;x=top-data;D. x

16、=top;top=top-next;题目6判断一个顺序队列（最多元素为m）为空的条件是（ ）。选择一项：A. rear=m-1B. front=rear+1C. front=rear题目7判断一个循环队列Q（最多元素为m）为满的条件是（ ）。选择一项：A. Q-rear!= (Q-front+1)%mB. Q-front=Q-rearC. Q-front=(Q-rear+1)%mD. Q-front=Q-rear +1题目8判断栈满（元素个数最多n个）的条件是（ ）。选择一项：A. top=0B. top!=0C. top=-1D. top=n-1题目9设有一个20阶的对称矩阵A（第一个元素为

17、a1,1），采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始）， 则矩阵元素a6,2在一维数组B中的下标是（ ）。选择一项：A. 17B. 23C. 21D. 28题目10在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入缓冲区中，而打印机则从缓冲区中取出数据打印，该缓冲区应该是一个（ ）结构。选择一项：A. 队列B. 先性表C. 数组D. 堆栈题目11一个递归算法必须包括（ ）。选择一项：A. 递归部分B. 迭代部分C. 终止条件和迭代部分D. 终止条件和递归部分题目12在一个链队中，假设f和r分别为队头和队尾

18、指针，则删除一个结点的运算为（ ）。选择一项：A. f=r-next;B. r=r-next;C. r=f-next;D. f=f-next;题目13在一个链队中，假设f和r分别为队头和队尾指针，则插入s所指结点的运算为（ ）。选择一项：A. s-next=r;r=s;B. r-next=s;r=s;C. s-next=f;f=s;D. f-next=s;f=s;题目14数组a经初始化char a =“English”;a7中存放的是（ ）。选择一项：A. hB. 字符串的结束符C. 变量hD. 字符h题目15设主串为“ABcCDABcdEFaBc”，以下模式串能与主串成功匹配的是（ ）。选择

19、一项：A. BCdB. BcdC. AbcD. ABC题目16字符串 a1=AEIJING，a2=AEI，a3=AEFANG，a4=AEFI中最大的是（ ）。选择一项：A. a3B. a1C. a4D. a2题目17两个字符串相等的条件是（ ）。选择一项：A. 两串的长度相等，并且对应位置上的字符相同B. 两串的长度相等C. 两串的长度相等，并且两串包含的字符相同D. 两串包含的字符相同题目18一维数组A采用顺序存储结构，每个元素占用6个字节，第6个元素的存储地址为100，则该数组的首地址是（ ）。选择一项：A. 64B. 90C. 28D. 70题目19一个非空广义表的表头（ ）。选择一项：

20、A. 可以是子表或原子B. 只能是原子C. 不可能是原子D. 只能是子表题目20对稀疏矩阵进行压缩存储,可采用三元组表，一个10 行8列的稀疏矩阵A，其相应的三元组表共有6个元素，矩阵A共有（ ）个零元素。选择一项：A. 8B. 10C. 72D. 74题目21对稀疏矩阵进行压缩存储,可采用三元组表，一个10 行8列的稀疏矩阵A共有73个零元素，A的右下角元素为6，其相应的三元组表中的第7个元素是（ ）。选择一项：A. （10，8，7）B. （10，8，6）C. （7，10，8）D. （7，8，10）题目22对一个栈顶指针为top的链栈进行入栈操作，通过指针变量p生成入栈结点，并给该 结点赋值

21、a，则执行: p=(struct node *)malloc(sizeof(struct node);p-data=a;和（ ）。选择一项：A. p-next=top;p=top;B. top-next=p;p=top;C. p-nex=top;top=p;D. top=top-next;pe=top;题目23头指针为head的带头结点的单向链表为空的判定条件是（ ）为真。选择一项：A. head=NULLB. head-next=NULLC. head-next!=NULLD. head-next!=NULL题目24设有一个对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维

22、数组B中（数组下标从1开始），B数组共有55个元素,则该矩阵是（ ）阶的对称矩阵。选择一项：A. 20B. 15C. 10D. 5题目25数组a经初始化char a =“English”;a1中存放的是（ ）。选择一项：A. nB. 字符nC. ED. 字符E二、填空题（每小题2分，共30分）题目26循环队列队头指针在队尾指针回答位置，队列是“满”状态。题目27循环队列的引入，目的是为了克服回答。题目28判断一个循环队列LU（最多元素为m）为空的条件是回答。题目29题干向一个栈顶指针为h的链栈中插入一个s所指结点时，可执行回答s-next=h;和h=s;操作。（结点的指针域为next）题目30

23、从一个栈顶指针为h的链栈中删除一个结点时，用x保存被删结点的值，可执行x=h-题目31在一个链队中，设f和r分别为队头和队尾指针，则插入s所指结点的操作为回答和r=s; r-next=s;（结点的指针域为next）题目32在一个链队中，设f和r分别为队头和队尾指针，则删除一个结点的操作为回答f=f-next;。 （结点的指针域为next）题目33串是一种特殊的线性表，其特殊性表现在组成串的数据元素都是回答。题目34空串的长度是回答；空格串的长度是回答。题目35设广义表L=(),()，则表头是_，表尾是_，L的长度是_。则表头是（），表尾是（），L的长度是2题目36广义表A（a，b，c），（d，

24、e，f）的表尾为回答(d,e,f)。题目37设有n阶对称矩阵A，用数组s进行压缩存储，当ij时，A的数组元素aij相应于数组s的数组元素的下标为回答。（数组元素的下标从1开始）题目38对稀疏矩阵进行压缩存储，矩阵中每个非零元素对应的三元组包括该元素的_、_和_三项信息。答案：行下标、列下标和非零元素值题目39循环队列用a0，a7的一维数组存放队列元素，（采用少用一个元素的模式)，设front和rear分别为队头和队尾指针，且front和rear 的值分别为2和7，当前队列中的元素个数是回答5。题目40循环队列的引入，目的是为了克服回答。三、问答题（每小题5分，共20分）题目41完成满分5.00

25、题干栈、队列和线性表的区别是什么？答：栈是一种先进后出的线性表，栈的插入和删除操作都只能在栈顶进行，而一般的线性表可以在线性表的任何位置进行插入和删除操作。队列是一种先进先出的线性表，队列的插入只能在队尾进行，队列的删除只能在队头进行，而一般的线性表可以在线性表的任何位置进行插入和删除操作。题目42设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3，e6，e5，e1，则栈S的容量至少应该是多少？出队序列是e2,e4,e3,e6,e5,e1的过程：（1）e1入栈（栈底到栈顶元素是e1）（2）e2入栈（栈

26、底到栈顶元素是e1，e2）（3）e2出栈（栈底到栈顶元素是e1）（4）e3入栈（栈底到栈顶元素是e1，e3）（5）e4入栈（栈底到栈顶元素是e1，e3，e4）（6）e4出栈（栈底到栈顶元素是e1，e3）（7）e3出栈（栈底到栈顶元素是e1）（8）e5入栈（栈底到栈顶元素是e1，e5）（9）e6入栈（栈底到栈顶元素是e1，e5，e6）（10）e6出栈（栈底到栈顶元素是e1，e5）（11）e5出栈（栈底到栈顶元素是e1）（12）e1出栈（栈底到栈顶元素是空）栈中最多时有3个元素，所以栈S的容量至少是3。题目43有5个元素，其入栈次序为：A、B、C、D、E，在各种可能的出栈次序中，以元素C、D最先的

27、次序有哪几个？从题中可知，要使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，CDEBA题目44简述广义表和线性表的区别和联系。广义表是线性表的的推广，它也是n（n0）个元素a1，a2，ai，an的有限序列，其中ai或者是原子或者是一个广义表。所以，广义表是一种递归数据结构，而线性表没有这种特性，线性表可以看成广义表的特殊情况，当

28、ai都是原子时，广义表退化成线性表。形考任务三一、单项选择题（每小题2分，共32分）题目1假定一棵二叉树中，双分支结点数为15，单分支结点数为30，则叶子结点数为（ ）。选择一项：A. 17B. 16C. 15D. 47题目2二叉树第k层上最多有（ ）个结点。选择一项：A. 2k-1B. 2k-1C. 2k-1D. 2k题目3设某一二叉树先序遍历为abdec，中序遍历为dbeac，则该二叉树后序遍历的顺序是（ ）。选择一项：A. abedcB. abdecC. debacD. debca题目4将含有150个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点的编号为1，则编

29、号为69的结点的双亲结点的编号为（ ）。选择一项：A. 35B. 33C. 34D. 36题目5如果将给定的一组数据作为叶子数值，所构造出的二叉树的带权路径长度最小，则该树称为（ ）。选择一项：A. 平衡二叉树B. 完全二叉树C. 二叉树D. 哈夫曼树题目6在一棵度为3的树中，度为3的结点个数为2，度为2的结点个数为1，则度为0的结点个数为（ ）。选择一项：A. 5B. 4C. 7D. 6题目7在一棵度具有5层的满二叉树中结点总数为（ ）。选择一项：A. 31B. 32C. 16D. 33题目8利用n个值作为叶结点的权生成的哈夫曼树中共包含有（ ）个结点。选择一项：A. n+1B. 2*nC.

30、 nD. 2*n-1题目9利用3、6、8、12这四个值作为叶子结点的权，生成一棵哈夫曼树，该树中所有叶子结点中的最长带权路径长度为（ ）。选择一项：A. 16B. 30C. 12D. 18题目10在一棵树中，（ ）没有前驱结点。选择一项：A. 叶结点B. 空结点C. 树根结点D. 分支结点题目11设一棵有n个叶结点的二叉树，除叶结点外每个结点度数都为2，则该树共有（ ）个结点。选择一项：A. 2n-1B. 2n+2C. 2n+1D. 2n题目12在一个图G中，所有顶点的度数之和等于所有边数之和的（ ）倍。选择一项：A. 1B. 1/2C. 2D. 4题目13邻接表是图的一种（ ）。选择一项：A

31、. 索引存储结构B. 顺序存储结构C. 散列存储结构D. 链式存储结构题目14如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是（ ）。选择一项：A. 一棵树B. 有回路C. 完全图D. 连通图题目15图的深度优先遍历算法类似于二叉树的（ ）遍历。选择一项：A. 先序B. 层次C. 中序D. 后序题目16已知下图所示的一个图，若从顶点V1出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为（ ）。选择一项：A. V1V2V4V5V8V3V6V7B. V1V2V4V8V5V3V6V7C. V1V2V4V8V3V5V6V7D. V1V3V6V7V2V4V5V8二、填

32、空题 （每小题1分，共20分）题目17结点的度是指结点所拥有的回答。正确答案是：子树树木或后继结点数题目18树的度是指回答。正确答案是：树中所有结点的度的最大值题目19度大于0的结点称作_或_。分支结点、非终端结点题目20度等于0的结点称作_或_。叶子结点、终端结点题目21在一棵树中，每个结点的_或者说每个结点的_称为该结点的_，简称为孩子。子树的根、后继结点、孩子结点题目22从根结点到该结点所经分支上的所有结点称为该结点的回答。正确答案是：祖先题目23树的深度或高度是指回答。正确答案是：树中结点的最大层数题目24具有n个结点的完全二叉树的深度是_。题目25先序遍历二叉树的的操作定义为；若二叉

33、树为空，则为空操作，否则进行如下操作，访问二叉树的回答；先序遍历二叉树的回答，先序遍历二叉树的回答。根结点、左子树、右子树题目26中序遍历二叉树的的操作定义为；若二叉树为空，则为空操作，否则进行如下操作，中序遍历二叉树的回答；访问而叉树的回答，中序遍历二叉树的回答。左子树、根结点、右子树题目27后序遍历二叉树的的操作定义为；若二叉树为空，则为空操作，否则进行如下操作，后序遍历二叉树的回答；后序遍历二叉树的回答，访问而叉树的回答。左子树、右子树、根结点题目28将树中结点赋上一个有着某种意义的实数，称此实数为该结点的回答。正确答案是：权题目29树的带权路径长度为树中所有叶子结点的回答。正确答案是：

34、带权路径长度之和题目30哈夫曼树又称为回答，它是n个带权叶子结点构成的所有二叉树中带权路径长度WPL回答。答案：最优二叉树，最小的二叉树题目31若以4，5，6，7，8作为叶子结点的权值构造哈夫曼树，则其带权路径长度是回答。正确答案是：69题目32具有m个叶子结点的哈夫曼树共有回答结点。正确答案是：2m-1题目33图的遍历是从图的某一顶点出发，按照一定的搜索方法对图中回答各做回答访问的过程。答案：所有顶点; 一次题目34图的深度优先搜索遍历类似于树的回答遍历。正确答案是：先序题目35图的广度优先搜索类似于树的回答遍历。正确答案是：按层次题目36图常用的两种存储结构是_和_。邻接矩阵、邻接表三、综

35、合题（每小题8分，共40分）题目37写出如下图所示的二叉树的先序、中序和后序遍历序列。答：二叉树的定义是递归的，所以，一棵二叉树可看作由根结点，左子树和右子树这三个基本部分组成，即依次遍历整个二叉树，又左子树或者右子树又可看作一棵二叉树并继续分为根结点、左子树和右子树三个部分，这样划分一直进行到树叶结点。（1）先序为“根左右”，先序序列为：fdbacegihl（2）中序为“左根右”，中序序列为：abcdefghij（3）后序为“左右根”，后序序列为：acbedhjigf题目38已知某二叉树的先序遍历结果是：A，B，D，G，C，E，H，L，I，K，M，F和J，它的中序遍历结果是：G，D，B，A，

36、L，H，E，K，I，M，C，F和J，请画出这棵二叉树，并写出该二叉树后续遍历的结果。（1）二叉树图形表示如下： （2）该二叉树后序遍历的结果是：G、D、B、L、H、K、M、I、E、J、F、C和A。题目39假设通信用的报文由9个字母A、B、C、D、E、F、G、H和I组成，它们出现的频率分别是：10、20、5、15、8、2、3、7和30。请请用这9个字母出现的频率作为权值求：（1）设计一棵哈夫曼树；（2）计算其带权路径长度WPL；（3）写出每个字符的哈夫曼编码。1）哈夫曼树如图B-4所示。图B-4（2）其带权路径长度WPL值为270。（3）每个字符的哈夫曼编码为：A:100, B:11, C:10

37、10, D:000, E:0010, F:10110, G:10111, H:0011, I:01题目40请根据以下带权有向图G（1）给出从结点v1出发分别按深度优先搜索遍历G和广度优先搜索遍历G所得的结点序列；（2）给出G的一个拓扑序列；（3）给出从结点v1到结点v8的最短路径。（1）深度优先遍历：v1，v2，v3，v8，v5，v7，v4，v6广度优先遍历：v1，v2，v4，v6，v3，v5，v7，v8（2）G的拓扑序列为：v1，v2，v4，v6，v5，v5，v3，v5，v7，v8（3）最短路径为：v1，v2，v5，v7，v8题目41已知无向图G描述如下：G=（V，E）V=V1，V2，V3，

38、V4，V5E=（V1，V2），（V1，V4），（V2，V4），（V3，V4），（V2，V5），（V3，V4），（V3，V5）（1）画出G的图示；（2）然后给出G的邻接矩阵和邻接表；（3）写出每个顶点的度。g1的图示和图g1的邻接表如下图所示。 图G图G的邻接矩阵如下图所示： 图G的邻接矩阵图G的邻接表V1、V2、V3、V4、V5的度分别为：2，3，2，3，2 四、程序填空题（每空2分，共8分）题目42部分正确获得4.00分中的2.00分题干以下是中序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中左、右指针域分别为left和right，数据域data为字符型，BT指向根结点）。void

39、 Inorder (struct BTreeNode *BT) if(BT!=NULL) 回答; 回答; Inorder(BT-right);答案：（1）Inorder(BT-left)（2）printf(%c,BT-data)题目43以下程序是后序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中左、右指针域分别为left和right，数据域data为字符型，BT指向根结点）。void Inorder (struct BTreeNode *BT) if(BT!=NULL) 回答; Inorder(BT-right); 回答;（1）Inorder(BT-left)（2）printf(%c,BT-data)形考任务四一、单项选择题（每小题2分，共42分）题目1对线性表进行二分查找时，要求线性表必须（