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

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

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

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

5、p=q->nextB p->next=qC p->next=q nextD q->next=NULL12 在一个单链表中p 所指结点之后插入一个s 所指的结点时，可执行A p->next= s; snext= p next B p->next=s next;C p=s->nexts->next=p->next; p->next=s;13 非空的单向循环链表的尾结点满足（）（设头指针为head,指针 p 指向尾结点）A. P->next= =NULL BC P->next= =head D14 链表不具有的特点是（ ）A 可

6、随机访问任一元素 P= =NULL P= = headB 插入删除不需要移动元素C 不必事先估计存储空间 D 所需空间与线性表长度成正比15 带头结点的链表为空的判断条件是（ ） （设头指针为 head ） 。A head = =NULLB head->next= =NULLC head->next= =headD head!=NULL16在一个单链表中，p、 q 分别指向表中两个相邻的结点，且q 所指结点是 p 所指结点的直接后继，现要删除q 所指结点，可用语句（ ） 。A p=q->nextB p->next=qC p->next=q->nextD q-

7、>next=NULL17 在一个链队中，假设f 和 r 分别为队头和队尾指针，则删除一个结点的运算为（ ） 。A r=f->next;B r=r->next;C f=f->next;D f=r->next;18 在一个链队中，假设f 和 r 分别为队头和队尾指针，则插入 s 所指结点的运算为（ ） 。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个元素的地址是(A. 98 B . 1

8、00 C . 102 D . 10620 .有关线性表的正确说法是()。A.每个元素都有一个直接前驱和一个直接后继B.线性表至少要求一个元素C.表中的元素必须按由小到大或由大到下排序D.除了一个和最后一个元素外，其余元素都有一个且仅有一个直接前驱和一个直接后继二、填空题1 .在一个长度为n的顺序存储结构的线性表中，向第 i(1 i n+1)个元素之 前插入新元素时，需向后移动 个数据元素。2 .从长度为n的采用顺序存储结构的线性表中删除第i(1 i n+1)个元素，需向前移动 个元素。3 .数据结构按结点间的关系，可分为4种逻辑结 构：、4 .数据的逻辑结构在计算机中的表示称为 或。5 .除了

9、第1个和最后一个结点外，其余结点有且只有一个前驱结点和后继 结点的数据结构为 ,每个结点可有任意多个前驱和后继结点数 的结构为。6 . 算 法 的 5 个 重 要 特 性7 .数据结构中的数据元素存在多对多的关系称为 结构。8 .数据结构中的数据元素存在一对多的关系称为 结构。9 .数据结构中的数据元素存在一对一的关系称为 结构。10 .要求在n个数据元素中找其中值最大的元素，设基本操作为元素间的 比较。则比较的次数和算法的时间复杂度分别为 和。11 .在一个单链表中p所指结点之后插入一个 s所指结点时，应执行 口 p->next=s;的操作。12 .设有一个头指针为head的单向循环链

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

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

12、结点(或称首元结点)的区别是什么？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)；(3) ;(4) ;return(head);

13、2.下列是用头插法建立带头结点的且有 n个结点的单向链表的算法，请在空格内填上适当的语句。NODE *create2(n)/*对线卜t表(n,n-1,.,1),建立带头结点的线性链表*/NODE *head,*p,*q;int i;p=(NODE *)malloc(sizeof(NODE);(1) ;p->next=NULL;(2) ;for(i=1;i<=n;i+)p=(NODE *)malloc(sizeof(NODE);p->data=i;if(i=1)(3) ;else(4) ;(5) ; return(head);3.下列是在具有头结点单向列表中删除第i个结点，请在

14、空格内填上适当的语句。int delete(NODE *head,int i)找到要删除结点的直接前驱，并使 q指向它*/int j； q=head; j=0;while(q!=NULL)&&(j<i-1)/* q=q->next; j+； if(q=NULL) return(0); (1)；(2)；free(p)； return(1); 五、完成：实验1线性表根据实验要求（见教材P201-202）认真完成本实验，并提交实验报告。数据结构（本）课程作业 2（本部分作业覆盖教材第3-5章的内容）一、单项选择题1 .若让元素1, 2,3依次进栈，则出栈顺序不可能为（A.

15、 3, 2, 1 2, 1, 3C. 3, 1,2D. 1, 3, 22. 一个队列的入队序列是1, 2, 3, 4。则队列的输出序列是（A. 4, 3, 2, 1 B 1, 2, 3C. 1, 4, 3, 2 D 3, 2, 43.向顺序栈中压入新元素时，应当（A.先移动栈顶指针，再存入元素.先存入元素，再移动栈顶指针C.先后次序无关紧要4在一个栈顶指针为 top 的链栈中，将一个p 指针所指的结点入栈，应执行（ ） 。A top->next=p;B p->next=top->next; top->next=p;C p->next=top; top=p;D p-

16、>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一般情况下，将递归算法转换成等价的非递归算法应该设置（ ） 。队列D.数组A.栈C.堆栈或队列7表达式 a*（b+c）-d 的后缀表达式是（ abc+*d- C abc*+d- D -+*abc

17、dsq （最多元素为m）为空的条件是（）。A abcd*+- B8判断一个顺序队列sq->rear-sq->front-1= = m0 sq->front=sq->rear+1A sq->rear-sq->front=m0BC sq->front=sq->rearD9 .判断一个循环队列 Q （最多元素为m）为空的条件是（）Q->front!=Q->rearA Q->front=Q->rearC Q->front=(Q->rear+1)% mD Q->front!= (Q->rear+1)%m10

18、.判断一个循环队列Q （最多元素为m）为空的条件是（）。A Q->front=Q->rearB Q->front!=Q->rearC Q->front=（Q->rear+1）% m0 D Q->front!= （Q->rear+1）% m011 .判断栈S满（元素个数最多n个）的条件是（）。A s->top=0B s->top!=0C s->top=n-1D s->top!=n-112 一个队列的入队顺序是a,b,c,d ，则离队的顺序是（ ） 。A a,d,cb B a,b,c,d C d,c,b,a D c,b,d,a

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

20、op=top->next; B x=top->data;top=top->next; x=data;C top=top->next; x=top->data; D17在一个链队中，假设f 和 r 分别为队头和队尾指针，则删除一个结点的运算为（ ） 。A r=f->next; B r=r->next; C f=f->next; D f=r->next;18在一个链队中，假设f 和 r 分别为队头和队尾指针，则插入 s 所指结点的运算为（ ） 。A f->next=s; f=s;BC s->next=r;r=s;D19. 以下陈述中

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

22、9 B 16 C 36 D 2824下面关于串的叙述中，不正确的是（） 。A.串是字符的有限序列B.空串是由空格构成的串C.模式匹配是串的一种重要运算D.串即可以采用顺序存储，也可以采用链式存储25 串与普通的线性表相比较，它的特殊性体现在（ ） 。A.顺序的存储结构B .链接的存储结构C.数据元素是一个字符D .数据元素可以任意26 空串与空格串（ ） 。A.相同 B.不相同C .可能相同 D .无法确定27 两个字符串相等的条件是（ ） 。A 两串的长度相等B.两串包含的字符相同C 两串的长度相等，并且两串包含的字符相同D 两串的长度相等，并且对应位置上的字符相同28 在实际应用中， 要输

23、入多个字符串， 且长度无法预定。 则应该采用 （）存储比较合适（ ） 。A.链式 B 顺序 C.堆结构 D .无法确定29 .一维数组A采用顺序存储结构，每个元素占用6个字节，第6个元素的存储地址为100，则该数组的首地址是（）。28A 6490C 7030稀疏矩阵采用压缩存储的目的主要是（） 。A.表达变得简单B.对矩阵元素的存取变得简单C 去掉矩阵中的多余元素 D 减少不必要的存储空间的开销31 一个非空广义表的表头（ ）。A 不可能是原子B 只能是子表C 只能是原子D 可以是子表或原子32常对数组进行的两种基本操作是（） 。A.建立与删除B.索引与、和修改C.查找和修改D.查找与索引33

24、 . 设二维数组A56 按行优先顺序存储在内存中，已知 A00 起始地址为1000， 每个数组元素占用5 个存储单元， 则元素 A44 的地址为 （） 。A 1140 B 1145 C 1120 D 112534 .设有一个20阶的对称矩阵A,采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组 B 中（数组下标从1 开始） ，则矩阵中元素a9,2 在一维数组 B 中的下标是（ ） 。A 41 B 32 C 18 D 3835一个非空广义表的表头（） 。A.不可能是子表B .只能是子表C.只能是原子D .可以是子表或原子二、填空题1 栈是限定在表的一端进行插入和删除操作的线 性表， 又

25、称 为。2 .队列的特性是。3 .往栈中插入元素的操作方式是：先, 后。4 .删除栈中元素的操作方式是：先, 后。5 .循环队列队头指针在队尾指针 位置，队列是“满”状态6 .在队列的顺序存储结构中，当插入一个新的队列元素时，尾指 针,当删除一个元素队列时，头指针 。7 .循环队列的引入，目的是为了克服 。8 .向顺序栈插入新元素分为三步：第一步进行 判断，判断条件 是;第二步是修改 ;第三步是把新元素赋 给。同样从顺序栈删除元素分为三步：第一步进行 判 断，判断条件是。第二步是把;第三9 .假设以S和X分别表示入栈和出栈操作，则对输入序列 a,b,c,d,e 一系歹U栈操作SSXSXSSXX

26、X后，得至J的输出序歹U为 。10 . 一个递归算法必须包括 和。11 .判断一个循环队列LU（最多元素为 m）为空的条件是 。12 .在将中缀表达式转换成后缀表达式和计算后缀表达式的算法中，都需要使用栈，对于前者，进入栈中的元素为表达式中的 ,而对于后者，进入栈的元素为,中缀表达式(a+b)心(f-d/c)所对应的后缀表达式16 .向一个栈顶指针为h的链栈中插入一个s所指结点时，可执行和h=s;操作。(结点的指针域为next)17 .从一个栈顶指针为h的链栈中删除一个结点时，用 x保存被删结点的 值，可执行x=h->data;和。(结点的指针域为next)18 .在一个链队中，设f和r

27、分别为队头和队尾指针，则插入 s所指结点的操作为 和r=s;(结点的指针域为next)19 .在一个链队中，设f和r分别为队头和队尾指针，则删除一个结点的 操作为。(结点的指针域为next)20 .串是一种特殊的线性表，其特殊性表现在组成串的数据元素都21 . 串的两种最基本的存储方式是和 022 .空串的长度是 ;空格串的长度是 。23 .需要压缩存储的矩阵可分为 矩阵和 矩阵两种。24 .设广义表L=(), (),则表头是,表尾是, L的长度是。25 .广义表 A (a,b,c ) ,(d,e,f)的表尾为 。26 .两个串相等的充分必要条件是 。27 .设有n阶对称矩阵A,用数组s进行压

28、缩存储，当i j时，A的数组元素aj相应于数组s的数组元素的下标为(数组元素的下标从1开始)28 .对稀疏矩阵进行压缩存储，矩阵中每个非零元素对应的三元组包括该元素的、和三项信息。三、问答题1 .简述栈和一般线性表的区别。2 .简述队列和一般线性表的区别。3 .链栈中为何不设头结点？4 .利用一个栈，则：(1)如果输入序列由A, B, C组成，试给出全部可能的输出序列和不可能 的输出序列。(2)如果输入序列由 A B, C, D组成，试给出全部可能的输出序列和不 可能的输出序列。5 .用S表示入栈操作，X表示出栈操作，若元素入栈顺序为1234,为了得到1342出栈顺序，相应的S和X操作串是什么

29、？6 .有5个元素，其入栈次序为：A B、C、D、E,在各种可能的出栈次序中，以元素C、 D最先的次序有哪几个？7 .写出以下运算式的后缀算术运算式(1) 3x2+x-1/x+5(2) (A+B)*C-D/(E+F)+G8 .在什么情况下可以用递归解决问题？在写递归程序时应注意什么？9 .简述广义表和线性表的区别和联系。四、程序填空题1.在下面空格处填写适当的语句，以使下面的循环队列的入队和出队算法完整。define TRUE 1;define FALSE 0;define MAXSIZE 100;typedef charelemtype;typedef structElemtype queu

30、e MAXSIZE;int front,rear;sequeuetype;Sequeuetype Q;int encqueue(sequeuetype*Q,elemtype x)if ( ( 1JJPrintf( ''The cicular queue is full!n "); return(FALSE);else(3) return(TRUE); /*encqueue*/ elemtype del_cqueue(sequeuetype *Q)if ( (4)Printf('' The queue is empty !n")return(N

31、ULL);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; printf("4d ,p ->data);(2) (3) ;/*队空时，

32、头尾指针指向头结点*/五、综合题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）判断队列

33、是否为空：emptyqueue（Q）。（6）显示队列中元素：dispqueue（Q）。六、完成：实验2栈、队列、递归程序设计根据实验要求（见教材 P203）认真完成本实验，并提交实验报告。数据结构（本）课程作业作业3（本部分作业覆盖教材第 6-7章的内容）一、单项选择题1 .假定一棵二叉树中，双分支结点数为15,单分支结点数为30,则叶子结点数为（）。A. 15 B . 16C .17 D . 472 .二叉树第k层上最多有（）个结点。A . 2kB. 2k-1C . 2k-1D. 2k-13 .二叉树的深度为k,则二叉树最多有（）个结点。A. 2kB. 2k-1C 2k-1D. 2k-14

34、.设某一二叉树先序遍历为abdec,中序遍历为 dbeac,则该二叉树后序A . abdec B遍历的顺序是（）。.debac C . debca D . abedc5树最适合于用来表示（A.线性结构的数据B.顺序结构的数据C.元素之间无前驱和后继关系的数据D.元素之间有包含和层次关系的数据6 设 a,b 为一棵二叉树的两个结点， 在后续遍历中， a 在 b 前的条件是（）A a 在 b 上方B a 在 b 下方C. a在b左方D. a在b右方7 权值为 1 ， 2 ， 6 ， 8 的四个结点构成的哈夫曼树的带权路径长度是（）A 18 B 28 C 19 D 298将含有150 个结点的完全二

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

36、的结点个数为（ ）。A 4 B 5 C 6 D 712. 在一棵度具有5 层的满二叉树中结点总数为（ ）。A 31 B 32 C 33 D 1613. 利用 n 个值作为叶结点的权生成的哈夫曼树中共包含有（ ） 个结点。A. n B. n+1 C. 2*n D. 2*n-114. 利用 n 个值作为叶结点的权生成的哈夫曼树中共包含有（ ） 个双支结点。A. n B. n-1 C. n+1 D. 2*n-115. 利用3、 6 、 8、 12 这四个值作为叶子结点的权，生成一棵哈夫曼树，该树中所有叶子的最长带权路径长度为 （ ）。A. 18 B. 16 C. 12 D. 3016在一棵树中，（）

37、没有前驱结点。A.分支结点B .叶结点 C .树根结点D .空结点17在一棵二叉树中，若编号为i 的结点存在右孩子，则右孩子的顺序编号为（ ） 。A 2iB 2i-1 D 2i+1 C 2i+218设一棵哈夫曼树共有n 个叶结点，则该树有（ ）个非叶结点。A nB n-1 C n+1 D 2n19 设一棵有n 个叶结点的二叉树，除叶结点外每个结点度数都为2 ，则该树共有（ ）个结点。A 2nB 2n-1 C 2n+1 D 2n+220一棵完全二叉树共有5 层，且第 5 层上有六个结点，该树共有（ ）个结点。 A 20B 21 C 23 D 3021 在一个图 G 中，所有顶点的度数之和等于所有

38、边数之和的（ ） 倍。A 1/2 B 1 C 2 D 422在一个有像图中，所有顶点的入度之和等于所有顶点的出度之和的 （ ）倍。A 邻接矩阵表示法 B 邻接表表示法C.逆邻接表表示法D .邻接表和逆邻接表23在图的存储结构表示中，表示形式唯一的是（）。A n B n 1 C n 1 D n/224一个具有n 个顶点的无向完全图包含（ ）条边。A n（ n 1） B n（ n 1） C n （ n 1） /2 D n （ n 1 ） /225一个具有n 个顶点的有向完全图包含（ ）条边。A n（ n 1） B n（ n 1） C n （ n 1） /2 D n （ n 1 ）/226 对于具有

39、n 个顶点的图，若采用邻接矩阵表示，则该矩阵的大小为）。A n B n2 C n 1 D （ n 1） 227对于一个具有n 个顶点和 e 条边的无向图，若采用邻接表表示，则表头向量的大小为（ ）。A n B e C 2n D 2e28对于一个具有n 个顶点和 e 条边的无向图，若采用邻接表表示，则所有顶点邻接表中的结点总数为（ ）。A n B e C 2n D 2e29在有向图的邻接表中，每个顶点邻接表链接着该顶点所有（）邻接点。A 入边B 出边C.入边和出边D.不是入边也不是出边30在有向图的逆邻接表中，每个顶点邻接表链接着该顶点所有（）邻接点。.出边.不是入边也不是出边.链式存储结构.散

40、列存储结构A 入边BC.入边和出边D31 邻接表是图的一种（ ）。A 顺序存储结构BC.索引存储结构D32 如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是（ ）。A 完全图 B 连通图 C 有回路D 一棵树33 .下列有关图遍历的说法不正确的是（A.连通图的深度优先搜索是一个递归过程B.图的广度优先搜索中邻接点的寻找具有“先进先出”的特征C.非连通图不能用深度优先搜索法D.图的遍历要求每一顶点仅被访问一次34 .无向图的邻接矩阵是一个（）。A.对称矩阵B .零矩阵 C .上三角矩阵D .对角矩阵35 .图的深度优先遍历算法类似于二叉树的（）遍历。A.先序B .中序

41、 C .后序 D .层次36 .已知下图所示的一个图，若从顶点 Vi出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为（）。A . MMMV8V3MV6V7B . VMV4V5VV3V6V75 .在一棵树中，每个结点的 或者说每个结点的称为该结点的 ,简称为孩子。6 . 一个结点称为其后继结点的 o7 .具有 的结点互称为兄弟结点，简称为兄弟。8 .每个结点的所有子树中的结点被称为该结点的 。9 .从根结点到该结点所经分支上的所有结点称为该结点的 。10 .树的深度或高度是指 。11 . m(m 0)棵互不相交的树的集合称为 。12 .度为k的树中的第i层上最多有 结点。13 .深度为

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

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

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

45、7 .为了实现图的深度优先搜索遍历，其非递归的算法中需要使用的一个辅助数据结构为。三、综合题1 .写出如下图所示的二叉树的先序、中序和后序遍历序列。f2 .已知某二叉树的先序刎第果是:A，B, D, G, C, E, H, L, I , K, M, F和J,它的中序遍号怦D,B,A)L H,E,K,I ,M,C,F和J,请画出这棵二叉树，并写bH该二叉树卮续遍历的结惠.3 .已知1媒2全二般b有 892个色，广)(1)树的高度叶子结点数 单支结点数 最后一个非终端结点的序号4给出满足下列条件的所有二叉树。（ 1）先序和中序相同（ 2）中序和后序相同（ 3）先序和后序相同（ 假设通信用的报文由9

46、 个字母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， V5E=（ V1， V2）， （ V1，V4）， （ V

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

48、e* 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);int c2=(2) if (3)；/若树中不存在 X结点则返回0else return 0;2 .下面函数的功能是按照图的深度优先搜索遍历的方法，输出得到该图的生成树中的各条边，请在划有横线的地方填写合适内容。void dfstree(adjmatrix GA, int i, int

49、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)求出图G中每个顶

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

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

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

53、叉树开始逐个插入数据来形成二叉排序树，若希望高度最小，应该选择的序列是（ ）。A 45,24,53,12,37,96,30B 37,24,12,30,53,45,96C 12,24,30,37,45,53,96D 30,24,12,37,45,96,5312. 对有18 个元素的有序表作二分（折半）查找，则查找A3 的比较序列的下标可能为（ ）。A 1、 2、 39、 5、 2 、 3C 9、 5、 3 D 9、 4、 2 、 313. 对于顺序存储的有序表5 ， 12 ， 20， 26， 37， 42， 46 ， 50 ， 64 ，若采用折半查找，则查找元素26 的比较次数是（ ） 。A.3 B. 3 C. 4D.514. 关于哈希查找的说法正确的是（ ） 。A. 除留余数法是最好的B. 哈希函数的好坏要根据具体情况而定C