电大数据结构(本)形成性考核册(作业1-4)980.pdf

《电大数据结构(本)形成性考核册(作业1-4)980.pdf》由会员分享，可在线阅读，更多相关《电大数据结构(本)形成性考核册(作业1-4)980.pdf（34页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

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

3、的是（）。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

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

5、ext=qnext Dq-next=NULL 12在一个单链表中 p 所指结点之后插入一个 s 所指的结点时，可执行（）。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带头结点的链表为空的判断条件是（

6、）（设头指针为 head）。Ahead=NULL Bhead-next=NULL Chead-next=head Dhead!=NULL 16在一个单链表中，p、q 分别指向表中两个相邻的结点，且 q 所指结点是 p 所指结点的直接后继，现要删除 q 所指结点，可用语句（）。Ap=q-next Bp-next=q Cp-next=q-next Dq-next=NULL 17 在一个链队中，假设f 和r 分别为队头和队尾指针，则删除一个结点的运算为（）。Ar=f-next;Br=r-next;C f=f-next;Df=r-next;18 在一个链队中，假设f 和r 分别为队头和队尾指针，则插入

7、s 所指结点的运算为（）。Af-next=s;f=s;Br-next=s;r=s;C s-next=r;r=s;Ds-next=f;f=s;19.一个顺序表第一个元素的存储地址是 90，每个元素的长度为 2，则第 6 个元素的地址是（）。A 98 B100 C102 D106 20有关线性表的正确说法是（）。A 每个元素都有一个直接前驱和一个直接后继 B 线性表至少要求一个元素 C 表中的元素必须按由小到大或由大到下排序 D 除了一个和最后一个元素外，其余元素都有一个且仅有一个直接前驱和一个直接后继 二、填空题 1 在一个长度为 n 的顺序存储结构的线性表中，向第 i(1i n+1)个元素之前

8、插入新元素时，需向后移动 个数据元素。2 从长度为 n的采用顺序存储结构的线性表中删除第 i(1i n+1)个元素，需向前移动 个元素。4 3 数据结构按结点间的关系，可分为 4 种逻辑结构：、。4 数据的逻辑结构在计算机中的表示称为 或 。5 除了第 1个和最后一个结点外，其余结点有且只有一个前驱结点和后继结点的数据结构为 ，每个结点可有任意多个前驱和后继结点数的结构为 。6 算法的 5 个重要特性是 、。7数据结构中的数据元素存在多对多的关系称为_ _结构。8数据结构中的数据元素存在一对多的关系称为_ _结构。9数据结构中的数据元素存在一对一的关系称为_ _结构。10要求在 n 个数据元素

9、中找其中值最大的元素，设基本操作为元素间的比较。则比较的次数和算法的时间复杂度分别为_ _和 _ _。11在一个单链表中 p 所指结点之后插入一个 s 所指结点时，应执行_ _和 p-next=s;的操作。12设有一个头指针为 head 的单向循环链表，p 指向链表中的结点，若 p-next=_ _，则 p 所指结点为尾结点。13在一个单向链表中，要删除 p 所指结点，已知 q 指向 p 所指结点的前驱结点。则可以用操作_ _。14 设有一个头指针为 head 的单向链表，p 指向表中某一个结点，且有 p-next=NULL,通过操作_ _,就可使该单向链表构造成单向循环链表。15每个结点只包

10、含一个指针域的线性表叫 。16线性表具有 和 两种存储结构。17数据的逻辑结构是从逻辑关系上描述数据，它与数据的关系 无关，是独立于计算机的。18 在双向循环链表的每个结点中包含 指针域，其中next指向它的 ，prior指向它的 ，而头结点的 prior指向 ，尾结点的 next指向 。19单向循环链表是单向链表的一种扩充，当单向链表带有头结点时，把单向链表中尾结点的指针域由空指针改为 ；当单向链表不带头结点时，则把单向链表中尾结点的指针域由空指针改为指向 。20线性链表的逻辑关系时通过每个结点指针域中的指针来表示的。其逻辑顺序和物理存储顺序不再一致，而是一种 存储结构，又称为 。三、问答题

11、 1简述数据的逻辑结构和存储结构的区别与联系，它们如何影响算法的设计与实现？5 2解释顺序存储结构和链式存储结构的特点，并比较顺序存储结构和链式存储结构的优缺点。3什么情况下用顺序表比链表好？4头指针、头结点、第一个结点（或称首元结点）的区别是什么？5解释带头结点的单链表和不带头结点的单链表的区别。6 四、程序填空题 1下列是用尾插法建立带头结点的且有 n 个结点的单向链表的算法，请在空格内填上适当的语句。NODE*create1(n)/*对线性表(1,2,.,n),建立带头结点的单向链表*/NODE*head,*p,*q;int i;p=(NODE*)malloc(sizeof(NODE);

12、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);7 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）;（2）;free(p);return(1);五、完成：实验 1线性表 根据实验要求（见教材P201-202）认真完成本

13、实验，并提交实验报告。8 数据结构（本）课程作业 2（本部分作业覆盖教材第 3-5 章的内容）一、单项选择题 1若让元素 1，2，3 依次进栈，则出栈顺序不可能为（）。A3，2，1 B2，1，3 C3，1，2 D1，3，2 2一个队列的入队序列是 1，2，3，4。则队列的输出序列是（）。A4，3，2，1 B1，2，3，4 C1，4，3，2 D3，2，4，1 3向顺序栈中压入新元素时，应当（）。A 先移动栈顶指针，再存入元素 B先存入元素，再移动栈顶指针 C 先后次序无关紧要 D同时进行 4在一个栈顶指针为 top 的链栈中，将一个 p 指针所指的结点入栈，应执行（）。A top-next=p;

14、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的后缀表达式是（）。Aabcd*+-Babc+*d-Ca

15、bc*+d-D-+*abcd 8判断一个顺序队列 sq（最多元素为 m0）为空的条件是（）。Asq-rear-sq-front=m0 Bsq-rear-sq-front-1=m0 Csq-front=sq-rear Dsq-front=sq-rear+1 9判断一个循环队列 Q（最多元素为 m0）为空的条件是（）。AQ-front=Q-rear BQ-front!=Q-rear CQ-front=(Q-rear+1)%m0 DQ-front!=(Q-rear+1)%m0 9 10判断一个循环队列 Q（最多元素为 m0）为空的条件是（）。AQ-front=Q-rear BQ-front!=Q-r

16、ear CQ-front=(Q-rear+1)%m0 DQ-front!=(Q-rear+1)%m0 11判断栈 S 满（元素个数最多 n 个）的条件是（）。As-top=0 Bs-top!=0 Cs-top=n-1 Ds-top!=n-1 12一个队列的入队顺序是 a,b,c,d，则离队的顺序是（）。Aa,d,cb Ba,b,c,d Cd,c,b,a Dc,b,d,a 13如果以链表作为栈的存储结构，则退栈操作时（）。A必须判断栈是否满 B判断栈元素类型 C必须判断栈是否空 D对栈不作任何判断 14在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次

17、写入缓冲区中，而打印机则从缓冲区中取出数据打印，该缓冲区应该是一个（）结构。A 堆栈 B队列 C数组 D先性表 15一个递归算法必须包括（）。A递归部分 B终止条件和递归部分 C迭代部分 D终止条件和迭代部分 16从一个栈顶指针为 top的链栈中删除一个结点时，用变量 x 保存被删结点的值，则执行（）。Ax=top-data;top=top-next;Bx=top-data;C top=top-next;x=top-data;Dtop=top-next;x=data;17 在一个链队中，假设 f 和 r 分别为队头和队尾指针，则删除一个结点的运算为（）。Ar=f-next;Br=r-next;

18、Cf=f-next;Df=r-next;18 在一个链队中，假设 f 和 r 分别为队头和队尾指针，则插入 s 所指结点的运算为（）。Af-next=s;f=s;Br-next=s;r=s;C s-next=r;r=s;Ds-next=f;f=s;19.以下陈述中正确的是（）。A 串是一种特殊的线性表 B串的长度必须大于零 C 串中元素只能是字母 D空串就是空白串 20 设有两个串 p 和 q，其中 q 是 p 的子串，q 在 p 中首次出现的位置的算法称为（）。A 求子串 B连接 C匹配 D求串长 10 21串是（）。A不少于一个字母的序列 B任意个字母的序列 C不少于一个字符的序列 D有限

19、个字符的序列 22串的长度是指（）。A 串中所含不同字母的个数 B串中所含字符的个数 C 串中所含不同字符的个数 D串中所含非空格字符的个数 23.若串 S=“English”，其子串的个数是（）。A 9 B16 C 36 D28 24下面关于串的叙述中，不正确的是（）。A 串是字符的有限序列 B 空串是由空格构成的串 C 模式匹配是串的一种重要运算 D 串即可以采用顺序存储，也可以采用链式存储 25串与普通的线性表相比较，它的特殊性体现在（）。A 顺序的存储结构 B链接的存储结构 C 数据元素是一个字符 D数据元素可以任意 26空串与空格串（）。A 相同 B不相同 C可能相同 D无法确定 2

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

21、义表的表头（）。11 A不可能是原子 B只能是子表 C只能是原子 D可以是子表或原子 32常对数组进行的两种基本操作是（）。A 建立与删除 B索引与、和修改 C 查找和修改 D查找与索引 33.设二维数组 A56按行优先顺序存储在内存中，已知 A00 起始地址为 1000，每个数组元素占用 5 个存储单元，则元素 A44的地址为（）。A 1140 B1145 C 1120 D1125 34设有一个 20 阶的对称矩阵 A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组 B中（数组下标从 1开始），则矩阵中元素 a9,2在一维数组 B 中的下标是（）。A 41 B32 C18 D3

22、8 35一个非空广义表的表头（）。A 不可能是子表 B只能是子表 C 只能是原子 D可以是子表或原子 二、填空题 1栈是限定在表的一端进行插入和删除操作的线性表，又称为 。2队列的特性是 。3往栈中插入元素的操作方式是：先 ，后 。4删除栈中元素的操作方式是：先 ，后 。5循环队列队头指针在队尾指针 位置，队列是“满”状态 6在队列的顺序存储结构中，当插入一个新的队列元素时，尾指针 ，当删除一个元素队列时，头指针 。7循环队列的引入，目的是为了克服 。8向顺序栈插入新元素分为三步：第一步进行 判断，判断条件是 ；第二步是修改 ；第三步是把新元素赋给 。同样从顺序栈删除元素分为三步：第一步进行

23、判断，判断条件是 。第二步是把 ；第三步 。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

24、)12 17从一个栈顶指针为 h 的链栈中删除一个结点时，用 x 保存被删结点的值，可执行x=h-data;和_。(结点的指针域为 next)18 在一个链队中，设f和r分别为队头和队尾指针，则插入s所指结点的操作为_和 r=s;(结点的指针域为 next)19 在一个链队中，设 f 和 r 分别为队头和队尾指针，则删除一个结点的操作为_。(结点的指针域为 next)20串是一种特殊的线性表，其特殊性表现在组成串的数据元素都是 。21串的两种最基本的存储方式是 和 。22空串的长度是 ；空格串的长度是 。23需要压缩存储的矩阵可分为 矩阵和 矩阵两种。24设广义表 L=（），（），则表头是 ，

25、表尾是 ，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 组成，试给出全部可能的输出序列和不可能的输出序 13 列。（2）如果输入序列由

26、 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)+G 8在什么情况下可以用递归解决问题？在写递归程序时应注意什么？14 9 简述广义表和线性表的区别和联系。四、程序填空题 1在下面空格处填写适当的语句，以使下面的循环队列的入队和出队算法完整。def

27、ine TRUE 1;define FALSE 0;define MAXSIZE 100;typedef charelemtype;typedef struct Elemtype 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(sequeu

28、etype*Q)if (4)Printf(The queue is empty!n)return(NULL);else (5)Return(Q-queueQ-front);15 /*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)（3）;/*队空时

29、，头尾指针指向头结点*/五、综合题 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

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

31、 C 2k-1 D2k-1 4.设某一二叉树先序遍历为 abdec，中序遍历为 dbeac，则该二叉树后序遍历的顺序是（）。A abdec Bdebac Cdebca Dabedc 5树最适合于用来表示（）。A 线性结构的数据 B 顺序结构的数据 C 元素之间无前驱和后继关系的数据 D 元素之间有包含和层次关系的数据 6设 a,b 为一棵二叉树的两个结点，在后续遍历中，a 在 b 前的条件是（）。A a 在 b 上方 Ba 在 b 下方 Ca 在 b 左方 Da 在 b 右方 7 权值为1，2，6，8的四个结点构成的哈夫曼树的带权路径长度是（）。A 18 B28 C19 D29 8 将含有 1

32、50个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点的编号为 1，则编号为 69 的结点的双亲结点的编号为（）。A 33 B34 C35 D36 9 如果将给定的一组数据作为叶子数值，所构造出的二叉树的带权路径长度最小，则该树称为（）。A 哈夫曼树 B平衡二叉树 C二叉树 D完全二叉树 10下列有关二叉树的说法正确的是（）。A 二叉树中度为 0 的结点的个数等于度为 2 的结点的个数加 1 B 二叉树中结点个数必大于 0 C 完全二叉树中，任何一个结点的度，或者为 0 或者为 2 D 二叉树的度是 2 11在一棵度为 3 的树中，度为 3 的结点个数为 2，度为 2

33、的结点个数为 1，则度为 0的结点个数为（）。A 4 B5 C6 D7 18 12在一棵度具有 5 层的满二叉树中结点总数为（）。A 31 B32 C33 D16 13.利用 n 个值作为叶结点的权生成的哈夫曼树中共包含有()个结点。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.30 16在一棵树中，（）没有前驱结点。A 分支

34、结点 B叶结点 C树根结点 D空结点 17在一棵二叉树中，若编号为 i 的结点存在右孩子，则右孩子的顺序编号为（）。A2i B2i-1 D2i+1 C2i+2 18设一棵哈夫曼树共有 n 个叶结点，则该树有（）个非叶结点。An Bn-1 Cn+1 D2n 19 设一棵有 n 个叶结点的二叉树，除叶结点外每个结点度数都为 2，则该树共有（）个结点。A 2n B2n-1 C2n+1 D2n+2 20一棵完全二叉树共有 5 层，且第 5 层上有六个结点，该树共有（）个结点。A20 B21 C23 D30 21在一个图 G 中，所有顶点的度数之和等于所有边数之和的（）倍。A1/2 B1 C2 D4 2

35、2在一个有像图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。A邻接矩阵表示法 B邻接表表示法 C 逆邻接表表示法 D邻接表和逆邻接表 23在图的存储结构表示中，表示形式唯一的是（）。An Bn 1 Cn 1 Dn/2 24一个具有 n 个顶点的无向完全图包含（）条边。An（n 1）Bn（n 1）C n（n 1）/2 D n（n 1）/2 25一个具有 n 个顶点的有向完全图包含（）条边。An（n 1）Bn（n 1）C n（n 1）/2 D n（n 1）/2 26对于具有 n 个顶点的图，若采用邻接矩阵表示，则该矩阵的大小为（）。An Bn2 Cn 1 D（n 1）2 27对于一个具有

36、n 个顶点和 e 条边的无向图，若采用邻接表表示，则表头向量的大小为（）。An Be C2n D2e 28对于一个具有 n 个顶点和 e 条边的无向图，若采用邻接表表示，则所有顶点邻接表中的结点总数为（）。An Be C2n D2e 29在有向图的邻接表中，每个顶点邻接表链接着该顶点所有（）邻接点。A入边 B 出边 C 入边和出边 D 不是入边也不是出边 30在有向图的逆邻接表中，每个顶点邻接表链接着该顶点所有（）邻接点。19 A入边 B出边 C 入边和出边 D不是入边也不是出边 31邻接表是图的一种（）。A顺序存储结构 B链式存储结构 C 索引存储结构 D散列存储结构 32如果从无向图的任一

37、顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是（）。A完全图 B连通图 C有回路 D一棵树 33下列有关图遍历的说法不正确的是（）。A 连通图的深度优先搜索是一个递归过程 B 图的广度优先搜索中邻接点的寻找具有“先进先出”的特征 C 非连通图不能用深度优先搜索法 D 图的遍历要求每一顶点仅被访问一次 34无向图的邻接矩阵是一个（）。A对称矩阵 B 零矩阵 C上三角矩阵 D对角矩阵 35图的深度优先遍历算法类似于二叉树的（）遍历。A 先序 B 中序 C后序 D层次 36已知下图所示的一个图，若从顶点 V1出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为（）。AV1V2V4V

38、8V3V5V6V7 BV1V2V4V5V8V3V6V7 C V1V2V4V8V5V3V6V7 DV1V3V6V7V2V4V5V8 二、填空题 1结点的度是指结点所拥有的 。2树的度是指 。3度大于 0 的结点称作 或 。4度等于 0 的结点称作 或 。5在一棵树中，每个结点的 或者说每个结点的 称为该结点的 ，简称为孩子。6一个结点称为其后继结点的 。7具有 的结点互称为兄弟结点，简称为兄弟。8每个结点的所有子树中的结点被称为该结点的 。V6 V7 V1 V2 V3 V8 V4 V5 20 9从根结点到该结点所经分支上的所有结点称为该结点的 。10树的深度或高度是指 。11m(m0)棵互不相交

39、的树的集合称为 。12度为 k 的树中的第 i 层上最多有 结点。13深度为 k 的二叉树最多有 结点。14在一棵二叉树中，如果树中的每一层都是满的，则称此树为 ；但如果出最后一层外，其余层都是满的，并且最后一层是满的，或者是在缺少若干连续个结点，则称此二叉树为 。15具有 n 个结点的完全二叉树的深度是 。16 先序遍历二叉树的的操作定义为；若二叉树为空，则为空操作，否则进行如下操作，访问二叉树的 ；先序遍历二叉树的 ，先序遍历二叉树的 。17 中序遍历二叉树的的操作定义为；若二叉树为空，则为空操作，否则进行如下操作，中序遍历二叉树的 ；访问而叉树的 ，中序遍历二叉树的 。18 后序遍历二叉

40、树的的操作定义为；若二叉树为空，则为空操作，否则进行如下操作，后序遍历二叉树的 ；后序遍历二叉树的 ，访问而叉树的 。19将树中结点赋上一个有着某种意义的实数，称此实数为该结点的 。20树的带权路径长度为树中所有叶子结点的 。21哈夫曼树又称为 ，它是 n 个带权叶子结点构成的所有二叉树中带权路径长度 WPL 。22若以 4，5，6，7，8 作为叶子结点的权值构造哈夫曼树，则其带权路径长度是 。23具有 m 个叶子结点的哈夫曼树共有 结点。24在图中，任何两个数据元素之间都可能存在关系，因此图的数据元素之间是一种 的关系。25图的邻接矩阵表示法是用一个 来表示图中顶点之间的相邻关系。26邻接表

41、是图中的每个顶点建立一个邻接关系的 。27图的遍历是从图的某一顶点出发，按照一定的搜索方法对图中 各做 访问的过程。28图的深度优先搜索遍历类似于树的 遍历。29图的广度优先搜索类似于树的 遍历。30具有 n 个顶点的有向图的邻接矩阵，其元素个数为 。30具有 n 个顶点的无向图至少有 条边，才能确保其为一个连通图。31图常用的两种存储结构是 和 。32一个 AOV 网（顶点活动图）应该是一个 。即不应该带有回路，否则回路上的所有活动都 。33用邻接矩阵存储有向图 G，其第 i 行的所有元素之和等于顶点 i 的 。34在有 n 个顶点的有向图中，每个顶点的度最大可达 。35在一个带权图中，两顶

42、点之间的最段路径最多经过 条边。36 为了实现图的深度优先搜索遍历，其非递归的算法中需要使用的一个辅助数据结构为 。21 三、综合题 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给出满足下列条件的所有二叉树。a j f g h i d c e b 22（1）先序和中序相同

43、（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，V

44、5 E=（V1，V2），（V1，V4），（V2，V4），（V3，V4），（V2，V5），（V3，V4），（V3，V5）23（1）画出 G 的图示；（2）然后给出 G 的邻接矩阵和邻接表；（3）写出每个顶点的度。8回答下列问题：对于存储结构采用邻接矩阵的无向图，如何判断下列有关问题？图中有多少条边？任意两顶点间是否有边相连？任意一个顶点的度是多少？对于存储结构采用邻接表的有向图，如何判断下列有关问题？图中有多少条边？图中是否存在从 Vi到 Vj的边？如何求顶点 Vi的入度和出度？四、程序填空题 1.下面函数的功能是返回二叉树 BT 中值为 X 的结点所在的层号，请在划有横线的地方填写合适内容。i

45、nt 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 结点则返回 0 else return 0;24 2.下面函数的功能是按照图的深度优先搜索遍历的方法，输出得到该图的生成树中的各条边，请在划有横线的地方填写合适内容。void dfs

46、tree(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);25 3 已知有 n 个顶点的有向图邻接表，设计算法分别实现下列功能：（1）求出图 G 中每个顶点的出度、入度

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

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

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

50、插入数据来形成二叉排序树，若希望高度最小，应该选择的序列是（）。A 45,24,53,12,37,96,30 B37,24,12,30,53,45,96 C 12,24,30,37,45,53,96 D30,24,12,37,45,96,53 28 12对有 18 个元素的有序表作二分（折半）查找，则查找 A3的比较序列的下标可能为（）。A 1、2、3 B9、5、2、3 C 9、5、3 D9、4、2、3 13.对于顺序存储的有序表5，12，20，26，37，42，46，50，64，若采用折半查找，则查找元素 26 的比较次数是（）。A.3 B.3 C.4 D.5 14.关于哈希查找的说法正确的