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

本文格式为Word版，下载可任意编辑——电大数据结构（本）形成性考核册(作业1

数据结构（本）形成性考核作业册

使用说明

本作业册是中央广播电视大学计算机科与技术专业（本科）数据结构（本）课程形成性考核的依据，与《数据结构（本科）》教材（李伟生主编，中央电大出版社出版）配套使用。

数据结构（本）课程是中央广播电视大学计算机科学技术专业的一门统设必修、学位课程，4学分，共72学时。其中试验24学时，开设一学期。本课程的特点是综合性、实践性强，内容抽象，在专业中具有承上启下的作用。因此，在学习本课程时，要注意理论联系实际，结合教学内容进行上机实践，认真完成作业和试验内容。

本课程的总成绩按百分制记分，其中形成性考核所占的比例为30%，终结性考试占70％（闭卷，答题时限为90分钟）。课程总成绩达到60分及以上者为合格，可以获得该课程的学分。本课程的学位课程学分为70分，即课程总成绩达到70分及以上者有资格申请专业学位。

本课程共设计了4次形考作业，每次形考作业均包括试验内容，由各地电大根据学生对作业中各种题型练习和试验的完成状况进行考核。对于试验内容要求按试验要求认真完成，并提交试验报告。

1

数据结构（本）课程作业

作业1

（本部分作业覆盖教材第1-2章的内容）

一、单项选择题

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）。

A．n-i+1B．n-iC．n-i-1D．i

10．设有一个长度为n的顺序表，要删除第i个元素移动元素的个数为（B）。A．n-i+1B．n-iC．n-i-1D．i

2

11．在一个单链表中，p、q分别指向表中两个相邻的结点，且q所指结点是p所指结点的直接后继，现要删除q所指结点，可用语句（C）。

A．p=q->nextB．p->next=qC．p->next=q?nextD．q->next=NULL

12．在一个单链表中p所指结点之后插入一个s所指的结点时，可执行（D）。A．p->next=s;s?next=p?nextB．p->next=s?next;

C．p=s->nextD．s->next=p->next;p->next=s;13．非空的单向循环链表的尾结点满足（C）（设头指针为head，指针p指向尾结点）。A.．P->next==NULLB．P==NULLC．P->next==headD．P==head14．链表不具有的特点是（A）。

A．可随机访问任一元素B．插入删除不需要移动元素C．不必事先估计存储空间D．所需空间与线性表长度成正比15．带头结点的链表为空的判断条件是（B）（设头指针为head）。A．head==NULL

B．head->next==NULLC．head->next==head

D．head!=NULL

16．在一个单链表中，p、q分别指向表中两个相邻的结点，且q所指结点是p所指结点的直接后继，现要删除q所指结点，可用语句（C）。A．p=q->nextB．p->next=q

C．p->next=q->nextD．q->next=NULL

17．在一个链队中，假设f和r分别为队头和队尾指针，则删除一个结点的运算为（C）。

A．r=f->next;B．r=r->next;

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

A．98B．100C．102D．10620．有关线性表的正确说法是（D）。

A．每个元素都有一个直接前驱和一个直接后继B．线性表至少要求一个元素

C．表中的元素必需按由小到大或由大到下排序

D．除了一个和最终一个元素外，其余元素都有一个且仅有一个直接前驱和一个直接后继

二、填空题

1．在一个长度为n的顺序存储结构的线性表中，向第i(1?i?n+1)个元素之前插入新元素时，需向后移动n-i+1个数据元素。

2．从长度为n的采用顺序存储结构的线性表中删除第i(1?i?n+1)个元素，需向前移

3

动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．简述数据的规律结构和存储结构的区别与联系，它们如何影响算法的设计与实现？答：若用结点表示某个数据元素，则结点与结点之间的规律关系就称为数据的规律结构。数据在计算机中的存储表示称为数据的存储结构。可见，数据的规律结构是反映数据之间的固有关系，而数据的存储结构是数据在计算机中的存储表示。尽管因采用的存储结构不同，规律上相邻的结点，其物理地址未必一致，但可通过结点的内部信息，找到其相邻的结点，从而保存了规律结构的特点。采用的存储结构不同，对数据的操作在灵活性，算法繁杂度等方面区别较大。

4

2．解释顺序存储结构和链式存储结构的特点，并比较顺序存储结构和链式存储结构的优缺点。

答：

顺序结构存储时，相邻数据元素的存放地址也相邻，即规律结构和存储结构是统一的，，要求内存中存储单元的地址必需是连续的。

优点：一般状况下，存储密度大，存储空间利用率高。缺点：（1）在做插入和删除操作时，需移动大量元素；（2）由于难以估计，必需预先分派较大的空间，往往使存储空间不能得到充分利用；（3）表的容量难以扩展。

链式结构存储时，相邻数据元素可随意存放，所占空间分为两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。

优点：插入和删除元素时很便利，使用灵活。缺点：存储密度小，存储空间利用率低。

3．什么状况下用顺序表比链表好？

答：顺序表适于做查找这样的静态操作，链表适于做插入和删除这样的动态操作。假使线性表的变化长度变化不大，且其主要操作是查找，则采用顺序表；假使线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。

4．头指针、头结点、第一个结点（或称首元结点）的区别是什么？

头结点是在链表的开始结点之前附加的一个结点；第一个结点（或称首元结点）是链表中存储第一个数据元素的结点；头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针。

5

5．解释带头结点的单链表和不带头结点的单链表的区别。答：

带头结点的单链表和不带头结点的单链表的区别主要表达在其结构上和算法操作上。在结构上，带头结点的单链表，不管链表是否为空，均含有一个头结点，不带头结点的单链表不含头结点。

在操作上，带头结点的单链表的初始化为申请一个头结点。无论插入或删除的位置是地第一个结点还是其他结点，算法步骤都一致。不带头结点的单链表，其算法步骤要分别考虑插入或删除的位置是第一个结点还是其他结点。由于两种状况的算法步骤不同。

四、程序填空题

1．以下是用尾插法建立带头结点的且有n个结点的单向链表的算法，请在空格内填上适当的语句。

NODE*create1(n)

/*对线性表(1,2,,n),建立带头结点的单向链表*/{

NODE*head,*p,*q;inti;

p=(NODE*)malloc(sizeof(NODE));head=p;q=p;p->next=NULL;for(i=1;idata=i;（2）p->next=NULL;

6

（3）q->next=p;（4）q=p;}return(head);}

2．以下是用头插法建立带头结点的且有n个结点的单向链表的算法，请在空格内填上适当的语句。

NODE*create2(n)

/*对线性表(n,n-1,,1),建立带头结点的线性链表*/{

NODE*head,*p,*q;inti;

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个结点，请在空格内填上适当的语句。intdelete(NODE*head,inti){

NODE*p,*q;intj;q=head;j=0;

while((q!=NULL)j++;}

if(q==NULL)

7

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）。A．3，2，1B．2，1，3C．3，1，2D．1，3，2

2．一个队列的入队序列是1，2，3，4。则队列的输出序列是（BA．4，3，2，1B．1，2，3，4C．1，4，3，2D．3，2，4，1

3．向顺序栈中压入新元素时，应当（A）。

）。8

（本部分作业覆盖教材第

A．先移动栈顶指针，再存入元素B．先存入元素，再移动栈顶指针C．先后次序无关紧要D．同时进行

4．在一个栈顶指针为top的链栈中，将一个p指针所指的结点入栈，应执行（C）。A．top->next=p;

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保存被删结点的值，则执行（B）。

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）。A．栈B．队列C．堆栈或队列D．数组

7．表达式a*(b+c)-d的后缀表达式是（B）。

A．abcd*+-B．abc+*d-C．abc*++d-D．-+*abcd

8．判断一个顺序队列sq（最多元素为m0）为空的条件是（C）。

A．sq->rear-sq->front==m0B．sq->rear-sq->front-1==m0C．sq->front==sq->rearD．sq->front==sq->rear+19．判断一个循环队列Q（最多元素为m0）为空的条件是（A）。A．Q->front==Q->rearB．Q->front!=Q->rear

C．Q->front==(Q->rear+1)%m0D．Q->front!=(Q->rear+1)%m0

10．判断栈S满（元素个数最多n个）的条件是（C）。A．s->top==0B．s->top!=0

C．s->top==n-1D．s->top!=n-1

11．一个队列的入队顺序是a,b,c,d，则离队的顺序是（B）。A．a,d,cbB．a,b,c,dC．d,c,b,aD．c,b,d,a

12．假使以链表作为栈的存储结构，则退栈操作时（C）。A．必需判断栈是否满B．判断栈元素类型

C．必需判断栈是否空D．对栈不作任何判断

13．在解决计算机主机与打印机之间速度不匹配问题时寻常设置一个打印数据缓冲区，主机将要输出的数据依次写入缓冲区中，而打印机则从缓冲区中取出数据打印，该缓冲区应当是一个（B）结构。

9

A．堆栈B．队列C．数组D．先性表

14．一个递归算法必需包括（B）。

A．递归部分B．终止条件和递归部分C．迭代部分D．终止条件和迭代部分

15．从一个栈顶指针为top的链栈中删除一个结点时，用变量x保存被删结点的值，则执行（A）。

A．x=top->data;top=top->next;B．x=top->data;

C．top=top->next;x=top->data;D．top=top->next;x=data;

16．在一个链队中，假设f和r分别为队头和队尾指针，则删除一个结点的运算为（C）。A．r=f->next;B．r=r->next;C．f=f->next;D．f=r->next;

17．在一个链队中，假设f和r分别为队头和队尾指针，则插入s所指结点的运算为（B）。A．f->next=s;f=s;B．r->next=s;r=s;

C．s->next=r;r=s;D．s->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）。A．9B．16C．36D．28

23．串与普通的线性表相比较，它的特别性表达在（C）。A．顺序的存储结构B．链接的存储结构C．数据元素是一个字符D．数据元素可以任意

24．空串与空格串（B）。

A．一致B．不一致C．可能一致D．无法确定

10

25．两个字符串相等的条件是（D）。A．两串的长度相等B．两串包含的字符一致

C．两串的长度相等，并且两串包含的字符一致D．两串的长度相等，并且对应位置上的字符一致

26．在实际应用中，要输入多个字符串，且长度无法预定。则应当采用（A）存储比较适合（）。

A．链式B．顺序C．堆结构D．无法确定

27.一维数组A采用顺序存储结构，每个元素占用6个字节，第6个元素的存储地址为100，则该数组的首地址是（C）。

A．64B．28C．70D．90

28．稀疏矩阵采用压缩存储的目的主要是（D）。

A．表达变得简单B．对矩阵元素的存取变得简单C．去掉矩阵中的多余元素D．减少不必要的存储空间的开销

29．一个非空广义表的表头（C）。

A．不可能是原子B．只能是子表

C．只能是原子D．可以是子表或原子

30．常对数组进行的两种基本操作是（C）。

A．建立与删除B．索引与、和修改C．查找和修改D．查找与索引

31.设二维数组A[5][6]按行优先顺序存储在内存中，已知A[0][0]起始地址为1000，每个数组元素占用5个存储单元，则元素A[4][4]的地址为（A）。

A．1140B．1145C．1120D．1125

32．设有一个20阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素a9,2在一维数组B中的下标是（D）。

A．41B．32C．18D．38

二、填空题

1．栈是限定在表的一端进行插入和删除操作的线性表，又称为后进先出。2．循环队列队头指针在队尾指针下一个位置，队列是“满〞状态

3．在队列的顺序存储结构中，当插入一个新的队列元素时，尾指针增1，当删除一个元素队列时，头指针增1。

4．循环队列的引入，目的是为了战胜假上溢。

11

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进行压缩存储，当i?j时，A的数组元素aij相应于数组s的数组元素的下标为__i(i-1)/2+j_____。（数组元素的下标从1开始）

22．对稀疏矩阵进行压缩存储，矩阵中每个非零元素对应的三元组包括该元素的___行下标____、___列下标___和___非零元素值____三项信息。

三、问答题

1．简述栈和一般线性表的区别。

答：栈是一种先进后出的线性表，栈的插入和删除操作都只能在栈顶进行，而一般的线性表可以在线性表的任何位置进行插入和删除操作。

12

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，CABD

5．用S表示入栈操作，X表示出栈操作，若元素入栈顺序为1234，为了得到1342出栈顺序，相应的S和X操作串是什么？

答：应是SXSSXSXX。各操作结果如下：S1入栈

X1出栈输出序列：1S2入栈S3入栈

X3出栈输出序列：13S4入栈

X4出栈输出序列：134X2出栈输出序列：1342

6．有5个元素，其入栈次序为：A、B、C、D、E，在各种可能的出栈次序中，以元素C、D最先的次序有哪几个？

13

答：从题中可知，要使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

7．写出以下运算式的后缀算术运算式⑴3x2+x-1/x+5

⑵(A+B)*C-D/(E+F)+G

答；对应的后缀算术运算式⑴3x2^*x+1x/-5+⑵AB+C*DEF+/-G+

8．简述广义表和线性表的区别和联系。

答：广义表是线性表的的推广，它也是n(n>0)个元素a1,a2…ai…an的有限序列，其中ai

或者是原子或者是一个广义表。所以，广义表是一种递归数据结构，而线性表没有这种特性，线性表可以看成广义表的特别状况，当ai都是原子时，广义表退化成线性表。

四、程序填空题

1．在下面空格处填写适当的语句，以使下面的链式队列取出元素的算法完整。intwrite(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(“M〞,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的过程：

14

⑴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的链式队的基本操作*/#includetypedefcharelemtype;

structnode/*定义链队列结点*/{

elemtypedata;structnode*next;};

typedefstructqueue/*定义链队列数据类型*/{

structnode*rear;}LinkQueue;

voidinitqueue(LinkQueue*Q)/*初始化队列*/{

Q=(structqueue*)malloc(sizeof(structqueue));Q->rear=NULL;}

15

voidenqueue(LinkQueue*Q,elemtypex)/*入队算法*/{

structnode*s,*p;

s=(structnode*)malloc(sizeof(structnode));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;}}

voiddelqueue(LinkQueue*Q)/*出队算法*/{

structnode*t;if(Q->rear==NULL){printf(\队列为空!\\n\return(0);}

elseif(Q->rear->next==Q->rear)/*只有一个结点时*/{t=Q->rear;Q->rear=NULL;}

else/*有多个结点时*/{t=Q->rear->next;/*t指向第一个结点*/Q->rear->next=t->next;/*引成循环链*/}

free(t);}

elemtypegethead(LinkQueue*Q)/*取队首元素算法*/{

if(Q->rear==NULL)printf(\队列为空!\\n\elsereturn(Q->rear->next->data);}

intemptyqueue(LinkQueue*Q)/*判断队列是否为空算法*/{

if(Q->rear==NULL)return(1);/*为空,则返回true*/

16

elsereturn(0);/*不为空,则返回flase*/}

voiddispqueue(LinkQueue*Q)/*显示队列中元素算法*/{

structnode*p=Q->rear->next;printf(\队列元素:\while(p!=Q->rear){printf(\p=p->next;}

printf(\}

六、完成：试验2――栈、队列、递归程序设计

根据试验要求（见教材P203）认真完成本试验，并提交试验报告。

17

数据结构（本）课程作业

作业3

（本部分作业覆盖教材第6-7章的内容）

一、单项选择题

1.假定一棵二叉树中，双分支结点数为15，单分支结点数为30，则叶子结点数为（B）。

A．15B．16C．17D．472．二叉树第k层上最多有（B）个结点。

k-1

A．2kB．2

k-1

C．2-1D．2k

3．二叉树的深度为k,则二叉树最多有（D）个结点。A．2kB．2k-1

k-1k

C．2D．2-1

4.设某一二叉树先序遍历为abdec，中序遍历为dbeac，则该二叉树后序遍历的顺序是（C）。

A．abdecB．debacC．debcaD．abedc

5．将含有150个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点的编号为1，则编号为69的结点的双亲结点的编号为（B）。

A．33B．34C．35D．36

6．假使将给定的一组数据作为叶子数值，所构造出的二叉树的带权路径长度最小，则该树称为（A）。

A．哈夫曼树B．平衡二叉树C．二叉树D．完全二叉树7．以下有关二叉树的说法正确的是（A）。

A．二叉树中度为0的结点的个数等于度为2的结点的个数加1B．二叉树中结点个数必大于0

C．完全二叉树中，任何一个结点的度，或者为0或者为2D．二叉树的度是2

8．在一棵度为3的树中，度为3的结点个数为2，度为2的结点个数为1，则度为0的结点个数为（C）。

A．4B．5C．6D．79．在一棵度具有5层的满二叉树中结点总数为（A）。A．31B．32C．33D．16

10.利用n个值作为叶结点的权生成的哈夫曼树中共包含有(D)个结点。A.nB.n+1C.2*nD.2*n-111.利用3、6、8、12这四个值作为叶子结点的权，生成一棵哈夫曼树，该树中所有叶子的最长带权路径长度为(A)。

18

A.18B.16C.12D.30

12．在一棵树中，（C）没有前驱结点。

A．分支结点B．叶结点C．树根结点D．空结点13．在一棵二叉树中，若编号为i的结点存在右孩子，则右孩子的顺序编号为（C）。A．2iB．2i-1D．2i+1C．2i+214．设一棵哈夫曼树共有n个叶结点，则该树有（B）个非叶结点。A．nB．n-1C．n+1D．2n15．设一棵有n个叶结点的二叉树，除叶结点外每个结点度数都为2，则该树共有（B）个结点。

A．2nB．2n-1C．2n+1D．2n+216．在一个图G中，所有顶点的度数之和等于所有边数之和的（C）倍。A．1/2B．1C．2D．4

17．在一个有像图中，所有顶点的入度之和等于所有顶点的出度之和的（B）倍。A．邻接矩阵表示法B．邻接表表示法C．逆邻接表表示法D．邻接表和逆邻接表18．在图的存储结构表示中，表示形式唯一的是（C）。

A．nB．n?1C．n?1D．n/219．一个具有n个顶点的无向完全图包含（A）条边。

A．n（n?1）B．n（n?1）C．n（n?1）/2D．n（n?1）/220．对于具有n个顶点的图，若采用邻接矩阵表示，则该矩阵的大小为（B）。

22

A．nB．nC．n?1D．（n?1）

21．对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则所有顶点邻接表中的结点总数为（D）。

A．nB．eC．2nD．2e

22．在有向图的邻接表中，每个顶点邻接表链接着该顶点所有（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．层次

19

28．已知下图所示的一个图，若从顶点V1出发，按深度优先探寻法进行遍历，则可能得到的一种顶点序列为（C）。

A．V1V2V4V8V3V5V6V7B．V1V2V4V5V8V3V6V7

C．V1V2V4V8V5V3V6V7D．V1V3V6V7V2V4V5V8

V1

V2V3

二、填空题

V4V5V6V7V81．结点的度是指结点所拥有的子树树木或后继结点数。2．树的度是指树中所有结点的度的最大值。3．度大于0的结点称作分支结点或非终端结点。4．度等于0的结点称作叶子结点或终端结点。

5．在一棵树中，每个结点的子树的根或者说每个结点的后继结点称为该结点的孩子结点，简称为孩子。

6．从根结点到该结点所经分支上的所有结点称为该结点的祖先。7．树的深度或高度是指树中结点的最大层数。

8．具有n个结点的完全二叉树的深度是?log2n??1。

9．先序遍历二叉树的的操作定义为；若二叉树为空，则为空操作，否则进行如下操作，访问二叉树的根结点；先序遍历二叉树的左子树，先序遍历二叉树的右子树。

10．中序遍历二叉树的的操作定义为；若二叉树为空，则为空操作，否则进行如下操

作，中序遍历二叉树的左子树；访问而叉树的根结点，中序遍历二叉树的右子树。

11．后序遍历二叉树的的操作定义为；若二叉树为空，则为空操作，否则进行如下操作，后序遍历二叉树的左子树；后序遍历二叉树的右子树，访问而叉树的根结点。

12．将树中结点赋上一个有着某种意义的实数，称此实数为该结点的权。13．树的带权路径长度为树中所有叶子结点的带权路径长度之和。14．哈夫曼树又称为最优二叉树，它是n个带权叶子结点构成的所有二叉树中带权路径长度WPL最小的二叉树。

15．若以4，5，6，7，8作为叶子结点的权值构造哈夫曼树，则其带权路径长度是69。

16．具有m个叶子结点的哈夫曼树共有2m-1结点。

17．在图中，任何两个数据元素之间都可能存在关系，因此图的数据元素之间是一种

20

（1）

4183

（2）

438383

494949835983474143474143598359414149474347435983495959434347594749474949418341835941594749474959434183434131

6．设查找表为(20,19,24,57,68,11)

(1)用冒泡对该表进行排序，要求写出每一趟的排序过程，寻常对n个元素进行冒泡排序要进行多少趟冒泡？第j趟要进行多少次元素间的比较？

(2)在排序后的有序表的基础上，画出对其进行折半查找所对应的判定树.(要求以数据元素作为树结点)

(3)求在等概率条件下,对上述有序表成功查找的平均查找长度。

(1)原序列16152053647

16

753

152064

(3)平均查找长度=（1*1+2*2+3*3）/6=14/67．

(1)设有查找表{8,17,5,9,21,10,7,19,6},依次取表中数据，构造一棵二叉排序树.（2）说明如何通过序列的二叉排序树得到相应序列的排序结果，对上述二叉排序给出中序遍历的结果.

（1）

5214

4618

3716(2)

中序遍历：2，3，4，5，6，7，14，16，18

32

四、程序填空题

1．以下直接输入排序算法对存放在a[0],a[1],···,a[n-1]中，长度为n的记录序列按关键字key由小到大排序，完成程序中的空格部分。voiddisort(NODEa[],intn){intI,j;

NODEtemp;/*工作单位*/for(i=1;i=0___}}

2．以下冒泡法程序对存放在a[1]，a[2]，……，a[n]中的序列进行冒泡排序完成程序中的空格部分，其中n是元素个数，程序按升序排列。Voidbsort(NODEa[],int){NODEtemp;inti,j,flag;

for(j=1;（1）ja[i+1].key)

{flag=1;temp=a[i];

（3）a[i]=a[i+1];（4）a[i+1]=temp;}

if(flag==0)break;}}

程序中flag的功能是（5）当某趟冒泡中没有出现交换则已排好序终止循环

五、算法设计题

1．写出在二叉树中删除一个结点的算法，且使删除后仍为二叉树，设删除的结点由指针p所指，其双亲结点由指针f所指，并假设被删除结点是其双亲结点的右孩子。

折半查找算法如下；

intBinary_Search(NODEa[],intn,intk)

/*在a[0]到a[n-1]中，用折半查找算法查找关键字等于k的记录，查找成功返回该记录的下标，

33

失败时返回-1*/

{

intlow,mid,high;low=0;high=n-1;while(low

多对多的关系。

18．图的遍历是从图的某一顶点出发，依照一定的探寻方法对图中所有顶点各做一次访问的过程。

19．图的深度优先探寻遍历类似于树的先序遍历。20．图的广度优先探寻类似于树的按层次遍历。

21．具有n个顶点的有向图的邻接矩阵，其元素个数为n2。22．图常用的两种存储结构是邻接矩阵和邻接表。23．在有n个顶点的有向图中，每个顶点的度最大可达2(n-1)。24．在一个带权图中，两顶点之间的最段路径最多经过n-1条边。25．为了实现图的深度优先探寻遍历，其非递归的算法中需要使用的一个辅助数据结构为栈。

三、综合题

1．写出如下图所示的二叉树的先序、中序和后序遍历序列。

f

dg

bie

ac

hj

答：二叉树的定义是递归的，所以，一棵二叉树可看作由根结点，左子树和右子树这三个基本部分组成，即依次遍历整个二叉树，又左子树或者右子树又可看作一棵二叉树并继续分为根结点、左子树和右子树三个部分…..，这样划分一直进行到树叶结点。

(1)先序为“根左右〞，先序序列为：fdbacegihl(2)中序为“左根右〞，中序序列为：abcdefghij(3)后序为“左右根〞，后序序列为：acbedhjigf

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，请画出这棵二叉树，并写出该二叉树后续遍历的结果。

（1）二叉树图形表示如下：

21

ABDGLHKEIMCFJ（2）该二叉树后序遍历的结果是：G、D、B、L、H、K、M、I、E、J、F、C和A。

3．已知一棵完全二叉树共有892个结点，求⑴树的高度⑵叶子结点数⑶单支结点数

⑷最终一个非终端结点的序号答

⑴已知深度为k的二叉树最多有2k-1个结点(K≥1)，29-1data==X)return1;/*根结点的层号为1*//*向子树中查找X结点*/else{intc1=NodeLevel(BT->left,X);if(c1>=1)___(1)returnc1+1___________;intc2=______(2)NodeLevel(BT->right,X)__________;if___(3)_(c2>=1)returnc2+1_________________;//若树中不存在X结点则返回0elsereturn0;}}

2.下面函数的功能是依照图的深度优先探寻遍历的方法，输出得到该图的生成树中的各条边，请在划有横线的地方填写适合内容。

24

voiddfstree(adjmatrixGA,inti,intn){

intj;

visited[i]=1;

(1)for(j=0;jdata=p->data;

t->lchild=CopyTree(p->lchild);t->rchild=CopyTree(p->rchild);return(t);

回。假定参数BT初始指向二叉树的根结点。

intBTreeLeafCount(structBTreeNode*BT);

intBTreeLeafCount(structBTreeNode*BT){

25

if(BT==NULL)return0;

elseif(BT->left==NULL

elsereturnBTreeLeafCount(BT->left)+BTreeLeafCount(BT->right);}

六、完成：试验3――栈、队列、递归程序设计试验4——图的存储方式和应用

根据试验要求（见教材P203）认真完成本试验，并提交试验报告。

数据结构（本）课程作业（4）

（本部分作业覆盖教材第8-9章的内容）

一、单项选择题

1.顺序查找方法适合于存储结构为（D）的线性表。

A．散列存储B．索引存储C．散列存储或索引存储D．顺序存储或链接存储2．对线性表进行二分查找时，要求线性表必需（C）。A．以顺序存储方式

B．以链接存储方式

C．以顺序存储方式，且数据元素有序D．以链接存储方式，且数据元素有序

3.对于一个线性表，若要求既能进行较快地插入和删除，又要求存储结构能够反映数据元素之间的规律关系，则应当（B）。

A．以顺序存储方式B．以链接存储方式C．以索引存储方式D．以散列存储方式4．采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为（C）。A．nB．n/2C．(n+1)/2D．(n-1)/2

5．哈希函数有一个共同的性质，即函数值应当以（D）取其值域的每个值。A．最大约率B．最小概率C．平均概率D．同等概率

6．有一个长度为10的有序表，按折半查找对该表进行查找，在等概率状况下查找成功的平均比较次数为（A）。

A．29/10B．31/10C．26/10D．29/9

7．已知一个有序表为{11,22,33,44,55,66,77,88,99}，则顺序查找元素55需要比较（C）次。

A．3B．4C．5D．6

8．顺序查找法与二分查找法对存储结构的要求是（D）。A．顺序查找与二分查找均只是适用于顺序表

B．顺序查找与二分查找均既适用于顺序表，也适用于链表C．顺序查找只是适用于顺序表D．二分查找适用于顺序表9．有数据{53,30,37,12,45,24,96}，从空二叉树开始逐个插入数据来形成二叉排序树，若希望高度最小，应选中择的序列是（B）。

26

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,53

10．对有18个元素的有序表作二分（折半）查找，则查找A[3]的比较序列的下标可能为（D）。

A．1、2、3B．9、5、2、3C．9、5、3D．9、4、2、311.对于顺序存储的有序表{5，12，20，26，37，42，46，50，64}，若采用折半查找，则查找元素26的比较次数是（C）。

A.3B.3C.4D.5

12.在所有的排序方法中，关键字比较的次数与记录初始排列秩序无关的是（C）。A.冒泡排序B.希尔排序C.直接选择排序D.直接插入排序

13.从未排序序列中依次取出元素与已经排好序的序列中的元素作比较。将其放入已排

序序列的正确的位置上，此方法称为（A）

A.插入排序B.选择排序C.交换排序D.归并排序

14.从未排序序列中挑拣元素，并将其放入已排序序列的一端，此方法称为（C）。A.插入排序B.交换排序C.选择排序D.归并排序15.依次将每两个相邻的有序表合