2023年电大数据结构本期末考试试卷重点汇总.doc

《2023年电大数据结构本期末考试试卷重点汇总.doc》由会员分享，可在线阅读，更多相关《2023年电大数据结构本期末考试试卷重点汇总.doc（25页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、最新电大数据结构本期末考试试卷重点汇总考试答题注意事项:1、 考生答题前,先将自己的姓名、准考证号等信息填写清楚,同时将条形码准确粘贴在考生信息条形码粘贴区。2、考试答题时,选择题必须使用2B铅笔填涂；非选择题必须使用0、5毫米黑色笔迹的签字笔书写,字体工整、笔迹清楚。3、请考生按照题号顺序,在各题目的答题区域内作答,超过答题区域书写的答案无效；在草稿纸、试题卷上答题无效。4、请考生保持答题卡面清洁,不要折叠、弄破、弄皱,不准使用涂改液、修正液、刮纸刀。【本部分作业覆盖教材第1-2章的内容】一、单项选择题1、在数据结构中,从逻辑上可以把数据结构分为【C】、A、动态结构和静态结构B、紧凑结构和非

2、紧凑结构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

3、、分析算法的易懂性和文档性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、i10、设有一个长度为n的顺序表,要删除第i个元素移动元素的个数为【B】、A、n-i+1B、n-iC、n-i-1D、i11、在一个单链表中,p、q分别指向表中两个相邻的结点,且q所指结点是p所指结点的直接后继,现要删除

4、q所指结点,可用语句【C】、A、p=q-nextB、p-next=qC、p-next=qnextD、q-next=NULL12、在一个单链表中p所指结点之后插入一个s所指的结点时,可执行【D】、A、p-next=s;snext=pnextB、p-next=snext;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、不必事先估

5、计存储空间D、所需空间和线性表长度成正比15、带头结点的链表为空的判断条件是【B】【设头指针为head】、A、head=NULLB、head-next=NULLC、head-next=headD、head!=NULL16、在一个单链表中,p、q分别指向表中两个相邻的结点,且q所指结点是p所指结点的直接后继,现要删除q所指结点,可用语句【C】、A、p=q-nextB、p-next=qC、p-next=q-nextD、q-next=NULL17、在一个链队中,假设f和r分别为队头和队尾指针,则删除一个结点的运算为【C】、A、r=f-next;B、r=r-next;C、f=f-next;D、f=r-

6、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的顺

7、序存储结构的线性表中,向第i(1in+1)个元素之前插入新元素时,需向后移动 n-i+1 个数据元素、2、从长度为n的采纳顺序存储结构的线性表中删除第i(1in+1)个元素,需向前移动 n-i 个元素、3、数据结构按结点间的关系,可分为4种逻辑结构: 集合 、 线性结构 、 树形结构 、 图状结构 、4、数据的逻辑结构在计算机中的表达称为 物理结构 或 存储结构 、5、除了第1个和最后一个结点外,其它结点有且只有一个前驱结点和后继结点的数据结构为 线性结构 ,每个结点可有任意多个前驱和后继结点数的结构为 非线性结构 、6、算法的5个重要特性是 有穷性 、 拟定性 、 可形性 、 有零个或多个输

8、入 、 有零个或多个输出 、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、在一个单

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

10、prior指向 尾结点 ,尾结点的next指向 头结点 、19、单向循环链表是单向链表的一种扩充,当单向链表带有头结点时,把单向链表中尾结点的指针域由空指针改为 头结点的指针 ;当单向链表不带头结点时,则把单向链表中尾结点的指针域由空指针改为指向 指向第一个结点的指针 、20、线性链表的逻辑关系时通过每个结点指针域中的指针来表达的、其逻辑顺序和物理存储顺序不再一致,而是一种 链式 存储结构,又称为 链表 、三、问答题1、简述数据的逻辑结构和存储结构的区别和联系,它们如何影响算法的设计和实现?答:若用结点表达某个数据元素,则结点和结点之间的逻辑关系就称为数据的逻辑结构、数据在计算机中的存储表达称

11、为数据的存储结构、可见,数据的逻辑结构是反映数据之间的固有关系,而数据的存储结构是数据在计算机中的存储表达、尽管因采纳的存储结构不同,逻辑上相邻的结点,其物理地址未必相同,但可通过结点的内部信息,找到其相邻的结点,从而保存了逻辑结构的特点、采纳的存储结构不同,对数据的操作在灵活性,算法复杂度等方面差别较大、2、解释顺序存储结构和链式存储结构的特点,并比较顺序存储结构和链式存储结构的优缺陷、答:顺序结构存储时,相邻数据元素的存放地址也相邻,即逻辑结构和存储结构是统一的,规定内存中存储单元的地址必须是连续的、优点:通常情况下,存储密度大,存储空间运用率高、缺陷:【1】在做插入和删除操作时,需移动大

12、量元素;【2】由于难以估计,必须预先分派较大的空间,往往使存储空间不能得到充足运用;【3】表的容量难以扩充、链式结构存储时,相邻数据元素可随意存放,所占空间分为两部分,一部分存放结点值,另一部分存放表达结点间关系的指针、优点:插入和删除元素时很方便,使用灵活、缺陷:存储密度小,存储空间运用率低、3、什么情况下用顺序表比链表好?答:顺序表适于做查找这样的静态操作,链表适于做插入和删除这样的动态操作、假如线性表的变化长度变化不大,且其重要操作是查找,则采纳顺序表;假如线性表的长度变化较大,且其重要操作是插入、删除操作,则采纳链表、4、头指针、头结点、第一个结点【或称首元结点】的区别是什么?头结点是

13、在链表的开始结点之前附加的一个结点;第一个结点【或称首元结点】是链表中存储第一个数据元素的结点;头指针是指向链表中第一个结点【或为头结点或为首元结点】的指针、5、解释带头结点的单链表和不带头结点的单链表的区别、答:带头结点的单链表和不带头结点的单链表的区别重要体现在其结构上和算法操作上、在结构上,带头结点的单链表,不管链表是否为空,均具有一个头结点,不带头结点的单链表不含头结点、在操作上,带头结点的单链表的初始化为申请一个头结点、无论插入或删除的位置是地第一个结点还是其他结点,算法环节都相同、不带头结点的单链表,其算法环节要分别考虑插入或删除的位置是第一个结点还是其他结点、由于两种情况的算法环

14、节不同、四、程序填空题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 ; 【3】q-next=p ; 【4】 q=p ;return(head);2、下面是用头插法建立带头结点的且有n个结点的单向链表的算法,请在空格内填上适当的语句、NODE*create2(

15、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;whi

16、le(q!=NULL)&(jnext;j+;if(q=NULL)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,22、一个队列的入队序列是1,2,3,4、则队列的输出序列是【B】、A、4,3,2,1B、1,2,3,4C、1,4,3,2D、3,2,

17、4,13、向顺序栈中压入新元素时,应当【A】、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-da

18、ta;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、-+*abcd8、判断一个顺序队列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

19、、Q-front!=Q-rearC、Q-front=(Q-rear+1)%m0D、Q-front!=(Q-rear+1)%m010、判断栈S满【元素个数最多n个】的条件是【C】、A、s-top=0B、s-top!=0C、s-top=n-1D、s-top!=n-111、一个队列的入队顺序是a,b,c,d,则离队的顺序是【B】、A、a,d,cbB、a,b,c,dC、d,c,b,aD、c,b,d,a12、假如以链表作为栈的存储结构,则退栈操作时【C】、A、必须判断栈是否满B、判断栈元素类型C、必须判断栈是否空D、对栈不作任何判断13、在解决计算机主机和打印机之间速度不匹配问题时通常设立一个打印数据缓

20、冲区,主机将要输出的数据依次写入缓冲区中,而打印机则从缓冲区中取出数据打印,该缓冲区应当是一个【B】结构、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

21、-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、不少于一个字符的

22、序列D、有限个字符的序列21、串的长度是指【B】、A、串中所含不同字母的个数B、串中所含字符的个数C、串中所含不同字符的个数D、串中所含非空格字符的个数22、若串S=“English”,其子串的个数是【D】、A、9B、16C、36D、2823、串和普通的线性表相比较,它的特殊性体现在【C】、A、顺序的存储结构B、链接的存储结构C、数据元素是一个字符D、数据元素可以任意24、空串和空格串【B】、A、相同B、不相同C、也许相同D、无法拟定25、两个字符串相等的条件是【D】、A、两串的长度相等B、两串包含的字符相同C、两串的长度相等,并且两串包含的字符相同D、两串的长度相等,并且相应位置上的字符相同

23、26、在实际应用中,要输入多个字符串,且长度无法预定、则应当采纳【A】存储比较合适【】、A、链式B、顺序C、堆结构D、无法拟定27、一维数组A采纳顺序存储结构,每个元素占用6个字节,第6个元素的存储地址为100,则该数组的首地址是【C】、A、64B、28C、70D、9028、稀疏矩阵采纳压缩存储的目的重要是【D】、A、表达变得简朴B、对矩阵元素的存取变得简朴C、去掉矩阵中的多余元素D、减少不必要的存储空间的开销29、一个非空广义表的表头【C】、A、不也许是原子B、只能是子表C、只能是原子D、可以是子表或原子30、常对数组进行的两种基本操作是【C】、A、建立和删除B、索引和、和修改C、查找和修改

24、D、查找和索引31、设二维数组A56按行优先顺序存储在内存中,已知A00起始地址为1000,每个数组元素占用5个存储单元,则元素A44的地址为【A】、A、1140B、1145C、1120D、112532、设有一个20阶的对称矩阵A,采纳压缩存储的方法,将其下三角部分以行序为主序存储到一维数组B中【数组下标从1开始】,则矩阵中元素a9,2在一维数组B中的下标是【D】、A、41B、32C、18D、38二、填空题1、栈是限定在表的一端进行插入和删除操作的线性表,又称为 后进先出 、2、循环队列队头指针在队尾指针 下一个 位置,队列是”满”状态3、在队列的顺序存储结构中,当插入一个新的队列元素时,尾指

25、针 增1 ,当删除一个元素队列时,头指针 增1 、4、循环队列的引入,目的是为了克服 假上溢 、5、向顺序栈插入新元素分为三步:第一步进行 栈是否满 判断,判断条件是 s-top=MAXSIZE-1 ;第二步是修改 栈顶指针 ;第三步是把新元素赋给 栈顶相应的数组元素 、同样从顺序栈删除元素分为三步:第一步进行 栈是否空 判断,判断条件是 s-top=-1 、第二步是把 栈顶元素 ;第三步 修改栈顶指针 、6、假设以S和X分别表达入栈和出栈操作,则对输入序列a,b,c,d,e一系列栈操作SSXSXSSXXX之后,得到的输出序列为 bceda 、7、一个递归算法必须包含 终止条件 和 递归部分

26、、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_、(结点的指针域为ne

27、xt)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 、

28、19、广义表A【a,b,c】,(d,e,f)】的表尾为 【d,e,f】 、20、两个串相等的充足必要条件是_串长度相等且相应位置的字符相等 _、21、设有n阶对称矩阵A,用数组s进行压缩存储,当ij时,A的数组元素aij相应于数组s的数组元素的下标为_ i(i-1)/2+j _、【数组元素的下标从1开始】22、对稀疏矩阵进行压缩存储,矩阵中每个非零元素相应的三元组包含该元素的_行下标_、_列下标_和_非零元素值_三项信息、三、问答题1、简述栈和通常线性表的区别、答:栈是一种先进后出的线性表,栈的插入和删除操作都只能在栈顶进行,而通常的线性表可以在线性表的任何位置进行插入和删除操作、2、简述队列

29、和通常线性表的区别、队列是一种先进先出的线性表,队列的插入只能在队尾进行,队列的删除只能在队头进行,而通常的线性表可以在线性表的任何位置进行插入和删除操作、3、链栈中为什么不设头结点?答:由于链栈只在链头插入和删除结点,不也许在链表中间插入和删除结点,算法实现很简朴,所以通常不设立头结点、4、运用一个栈,则:【1】假如输入序列由A,B,C组成,试给出所有也许的输出序列和不也许的输出序列、【2】假如输入序列由A,B,C,D组成,试给出所有也许的输出序列和不也许的输出序列、答:【1】栈的操作特点是后进先出,因此输出序列有:A入,A出,B入,B出,C入C出,输出序列为ABC、A入,A出,B入,C入,

30、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

31、,DACB,DBAC,BDAC,DBCA,DCAB,CDAB,CADB,CABD5、用S表达入栈操作,X表达出栈操作,若元素入栈顺序为1234,为了得到1342出栈顺序,相应的S和X操作串是什么?答:应是SXSSXSXX、各操作结果如下:S1入栈X1出栈输出序列:1S2入栈S3入栈X3出栈输出序列:13S4入栈X4出栈输出序列:134X2出栈输出序列:13426、有5个元素,其入栈顺序为:A、B、C、D、E,在各种也许的出栈顺序中,以元素C、D最先的顺序有哪几个?答:从题中可知,要使C第一个且D第二个出栈,应是A入栈,B入栈,C入栈,C出栈,D入栈、之后可以有以下几种情况:【1】B出栈,A出栈

32、,E入栈,E出栈,输出序列为:CDBAE、【2】B出栈,E入栈,E出栈,A出栈,输出序列为CDBEA、【3】E入栈,E出栈,B出栈,A出栈,输出序列为CDEBA所以也许的顺序有:CDBAE,CDBEA,CDEBA7、写出以下运算式的后缀算术运算式3x2+x-1/x+5(A+B)*C-D/(E+F)+G答;相应的后缀算术运算式3x2*x+1x/-5+AB+C*DEF+/-G+8、简述广义表和线性表的区别和联系、答:广义表是线性表的的推广,它也是n(n0)个元素a1,a2aian的有限序列,其中ai或是原子或是一个广义表、所以,广义表是一种递归数据结构,而线性表没有这种特性,线性表可以当作广义表的

33、特殊情况,当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(“%4d”,p-data); (2) free(p); 【3】 q-rear=q-front ;/*队空时,头尾指针指向头结点*/五、综合题1、设栈S和队

34、列Q的初始状态为空,元素e1,e2,e3,e4,e5和e6依次通过S,一个元素出栈后即进队列Q,若6个元素出队的序列是e2,e4,e3,e6,e5,e1,则栈S的容量至少应当是多少?答:出队序列是e2,e4,e3,e6,e5,e1的过程: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出栈【栈底到栈顶元素是

35、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的

36、链式队的基本操作*/#includetypedefcharelemtype;structnode/*定义链队列结点*/elemtypedata;structnode*next;typedefstructqueue/*定义链队列数据类型*/structnode*rear;LinkQueue;voidinitqueue(LinkQueue*Q)/*初始化队列*/Q=(structqueue*)malloc(sizeof(structqueue);Q-rear=NULL;voidenqueue(LinkQueue*Q,elemtypex)/*入队算法*/structnode*s,*p;s=(stru

37、ctnode*)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)/*只有一个

38、结点时*/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*/elsereturn(0);/*不为空,则

39、返回flase*/voiddispqueue(LinkQueue*Q)/*显示队列中元素算法*/structnode*p=Q-rear-next;printf(队列元素:);while(p!=Q-rear)printf(%c,p-data);p=p-next;printf(%cn,p-data);六、完毕:实验2栈、队列、递归程序设计依据实验规定【见教材P203】认真完毕本实验,并提交实验报告、数据结构【本】课程作业作业3【本部分作业覆盖教材第6-7章的内容】一、单项选择题1、假定一棵二叉树中,双分支结点数为15,单分支结点数为30,则叶子结点数为【B】、A、15B、16C、17D、472、二

40、叉树第k层上最多有【B】个结点、A、2kB、2k-1C、2k-1D、2k-13、二叉树的深度为k,则二叉树最多有【D】个结点、A、2kB、2k-1C、2k-1D、2k-14、设某一二叉树先序遍历为abdec,中序遍历为dbeac,则该二叉树后序遍历的顺序是【C】、A、abdecB、debacC、debcaD、abedc5、将具有150个结点的完全二叉树从根这一层开始,每一层从左到右依次对结点进行编号,根结点的编号为1,则编号为69的结点的双亲结点的编号为【B】、A、33B、34C、35D、366、假如将给定的一组数据作为叶子数值,所构造出的二叉树的带权途径长度最小,则该树称为【A】、A、哈夫曼

41、树B、平衡二叉树C、二叉树D、完全二叉树7、下面有关二叉树的说法对的的是【A】、A、二叉树中度为0的结点的个数等于度为2的结点的个数加1B、二叉树中结点个数必大于0C、完全二叉树中,任何一个结点的度,或为0或为2D、二叉树的度是28、在一棵度为3的树中,度为3的结点个数为2,度为2的结点个数为1,则度为0的结点个数为【C】、A、4B、5C、6D、79、在一棵度具有5层的满二叉树中结点总数为【A】、A、31B、32C、33D、1610、运用n个值作为叶结点的权生成的哈夫曼树中共包具有(D)个结点、A、nB、n+1C、2*nD、2*n-111、运用3、6、8、12这四个值作为叶子结点的权,生成一棵

42、哈夫曼树,该树中所有叶子的最长带权途径长度为(A)、A、18B、16C、12D、3012、在一棵树中,【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、417、在一个有像图中,所有顶点的入度之和等于所有顶点的出度之和的【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、对