《2021年电大数据结构本期末考试试卷重点汇总.pdf》由会员分享，可在线阅读，更多相关《2021年电大数据结构本期末考试试卷重点汇总.pdf（23页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、最新电大数据结构 本 期末考试试卷关键汇总考试答题注意事项：1、考生答题前，先将自己姓名、准考证号等信息填写清楚，同时将条形码正确粘贴在考生信息条形码粘贴区。2、考试答题时，选择题必需使用2B铅笔填涂；非选择题必需使用0、5毫米黑色字迹签字笔书写，字体工整、一、单项选择题1,在数据结构中，从逻辑上能够把数据结构分为 C.A.动态结构和静态结构B、紧凑结构和非紧凑结构C,线性结构和非线性结构I）、内部结构和外部机构2、下面说法中，错误是 D,A、数据元素是数据基础单位B,数据项是数据中不可分割最小可标识单位C、数据可有若干个数据元素组成D、数据项可由若干个数据元素组成3、一个存放结点存放一个 B
2、.A、数据项B、数据元素C、数据结构D、数据类型4.数据结构中，和所使用计算机无关是数据 C1A.存放结构B、物理结构C.逻辑结构I）、物理和存放结构5、下面叙述中，不属于算法特征是（D1,A,有穷性B、输入性C、可行性D、可读性6,算法分析目标是 C1.字迹清楚。3、请考生根据题号次序，在各题目标答题区域内作答，超出答题区域书写答案无效；在初稿纸、试题卷上答题无效。4、请考生保持答题卡面清洁，不要折叠、弄破、弄皱，不准使用涂改液、修正液、刮纸刀。【本部分作业覆盖教材第1-2章内容】A,找出数据结构合理性B、研究算法中输入和输出关系C.分析算法效率以求改善【）、分析算法易懂性和文档性7,数据结
3、构是一门研究计算机中【B】对象及其关系科学、A.数值运算B、非数值运算C、集合D、非集合8,算法时间复杂度和【口 相关、A,所使用计算机B、和计算机操作系统C,和算法本身D、和数据结构9、设有一个长度为n次序表，要在第i个元素之前【也就是插入元素作为新表第i个元素】，则移动元素个数 为（ALA、n-i+lBs n-iC n-iTD、i10、设有一个长度为n次序表，要删除第i个元素移动元素个数为【B】、A、nT+lB、niC、nTTD、i11、在一个单链表中，p、q分别指向表中两个相邻结点，且q所指结点是p所指结点直接后继,现要删除 q所指结点，可用语句【。、A、p=q-n e x t B.p-
4、n e x t=q C,p-n e x t=q-n e x t Dsq-n e x t=N U L L12、在一个单锥表中p所指结点以后插入一个s所指结点时，可实施【I)】、A、p-n e x t=s；s fn e x t=p T n e x l B、p-n e x t=s-n e x t；C、p=s-n e x t D s-n e x t=p-n e x t；p-n e x t=s；13、非空单向循环链表尾结点满足【C】【设头指针为 h e a d,指针p指向尾结点】、A、P-n e x t=N U L L B.P=N U L LA、h e a d二 二 N U L LB、h e a d-n
5、 e x t=N U L LC、h e a d-n e x t-h e a dD、h e a d!=N U L L16、在一个单链表中，p、q分别指向表中两个相邻结点，且q 所指结点是p 所指结点直接后继，现要删除q所指结点，可用语句【。、A、p=q-n e x tB、p-n e x t=qC、p-n e x t=q-n e x tD、q-n e x t=N U L L17、在一个链队中，假设f 和 r分别为队头和队尾指针，则删除一个结点运算为【C】、A、r=f-n e x t；B r=r-n e x t；C、f=f-n e x t；D.f=r-n e x t；18、在一个链队中，假设f 和
6、r分别为队头和队尾指针，则插入s所指结点运算为【B】、C、P-n e x t=h e a dDs P=h e a d14、链表不含有特点是 A1A、可随机访问任一元素B、插入删除不需要移动元素C、无须事先估量存放空间D、所需空间和线性表长度成正比15.带头结点链表为空判定条件是【B】【设头指针为h e a d】、A,f-n e x t=s；f=s：B,r-n e x t=s；r=s；C.s-n e x t=r；r=s；D,s-n e x t=f；f=s；19、一个次序表第一个元素存放地址是9 0,每个元素长度为2,则第6个元素地址是【B】、A.9 8 B.100C,102D.10620、相关线
7、性表正确说法是 D,A,每个元素全部有一个直接前驱和一个直接后继B,线性表最少要求一个元素C,表中元素必需按由小到大或由大到下排序I)、除了一个和最终一个元素外，其它元素全部有一个且仅有一个直接前驱和一个直接后继二、填空题1、在一个长度为n次序存放结构线性表中，向第i(l V i V n+l)个元素之前插入新元素时，需向后移动_n-i+l _个数据元素、2,从长度为n采纳次序存放结构线性表中删除第i(l V i V n+l)个元素，需向前移动_ n-i 一个元素、3.数据结构按结点间关系，可分为4种逻辑结构:_集合、线性结构、树 形 结 构 、图状结构、4,数据逻辑结构在计算机中表示称为_ 物
8、理结构或存放结构_、有零个或多个输出_、7、数据结构中数据元素存在多对多关系称为 图状结构结构、8、数据结构中数据元素存在一对多关系称为_树形结构结构、9、数据结构中数据元素存在一对一关系称为_线性结构一结构、1 0.要求在n个数据元素中找其中值最大元素，设基础操作为元素间比较、则比较次数和算法时间复杂度分别 为 _n-l_ 和 _O(n)_、1 1,在一个单链表中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=MJLL,经过操作_ p-next=head_,就可使该单向链表结组成单向循环5,除了第1个和最终一个结点外，其它结点有且只有一个前驱结点和后继结点数据结构为 线性结构每个结点可有任意多个前驱和后继结点数结构为 非线 性 结 构、6、算法5个关键特征是有穷性_、_ 确定性_、可形性_、有零个或多个输入_、链表、15、每个结点只包含一个指针域线性表叫单链表_、1 6,线性表含有次序存放和链式存放 两种存放结构、17
10、、数据逻辑结构是从逻辑关系上描述数据，它和数据关系存放结构无关，是独立于计算机、18、在双向循环链表每个结点中包含_ 两 个一指针域,其中next指向它_ 直接后继_,p rio r指向它_ 直接前驱_，而头结点prior指向_ 尾结点_,尾结点next指向头结点_、19、单向循环链表是单向链表一个扩充，当单向鞋表带有头结点时，把单向链表中尾结点指针域由空指针改为 头结点指针；当单向链表不带头结点时，则把单向链表中尾结点指针域由空指针改为指向 指向第一个结点指针一、2 0,线性链表逻辑关系时经过每个结点指针域中指针来表示、其逻辑次序和物理存放次序不再一致，而是一个 链式存放结构，又称为桂表_、
11、三、问答题1、简述数据逻辑结构和存放结构区分和联络，它们怎样影响算法设计和实现？答：若用结点表示某个数据元素，则结点和结点之间逻辑关系就称为数据逻辑结构、数据在计算机中存放表示称为数据存放结构、可见,数据逻辑结构是反应数据之间固相关系，而数据存放结构是数据在计算机中存放表示、尽管因采纳存放结构不一样，逻辑上相邻结点,其物理地址未必相同，但可经过结点内部信息,找到其相邻结点，从而保留了逻辑结构特点、采纳存放结构不一样，对数据操作在灵活性，算法复杂度等方面差异较大、2.解释次序存放结构和链式存放结构特点，并比较次序存放结构和链式存放结构优缺点、答：次序结构存放时，相邻数据元素存放地址也相邻,即逻辑
12、结构和存放结构是统一，要求内存中存放单元地址必需是连续、优点：通常情况下，存放密度大，存放空间利用率高、缺点：【1】在做插入和删除操作时，需移动大量元素；2 因为难以估量，必需预先分配较大空间，往往使存放空间不能得到充足利用；【3】表容量难以扩充、链式结构存放时，相邻数据元素可随意存放，所占空间分为两部分，一部分存放结点值，另一部分存放表示结点间关系指针、优点：插入和删除元素时很方便，使用灵活、缺点：存放密度小,存放空间利用率低、3、什么情况下用次序表比链表好？答:次序表适于做查找这么静态操作，链表适于做插入和删除这么动态操作、假如线性表改变长度改变不大，且其关键操作是查找，则采纳次序表;假如
13、线性表长度改变较大，且其关键操作是插入、删除操作，则采纳链表、4、头指针、头结点、第一个结点【或称首元结点】区分是什么？头结点是在链表开始结点之前附加一个结点；第一个 结点【或称首元结点】是链表中存放第一个数据元素结点；头指针是指向链表中第一个结点【或为头结点或为首元结点】指针、5、解释带头结点单链表和不带头结点单链表区分、答：带头结点单链表和不带头结点单链表区分关键表现在其结构上和算法操作上、在结构上，带头结点单链表，不管链表是否为空，均含有一个头结点，不带头结点单链表不含头结点、在操作上，带头结点单链表初始化为申请一个头结点、不管插入或删除位置是地第一个结点还是其它结点，算法步骤全部相同、
14、不带头结点单徒表，其算法步骤要分别考虑插入或删除位置是第一个结点还是其它结点、因为两种情况算法步骤不一样、四、程序填空题1、下面是用尾插法建立带头结点且有n个结点单向链表算法，请在空格内填上合适语句、N O DE*cr e at e l(n)/*对线性表(1,2,.n),建立带头结点单向链表*/N O DE*h e ad,*p,*q；i n t i；p=(N O DE*)m al l o c(s i z e o f(N O DE)；h e ad=p；q=p：p-n e x t=N ULL；f o r(i=l；i d at a=i；2 p-n e x t =NULL；3 q-n e x t =p
15、;4 q=p;r e t u r n(h e ad)；)2、下面是用头插法建立带头结点且有n个结点单向链表算法,请在空格内填上合适语句、N 0DE*cr e at e 2(n)/*对线性表(n,n T.1),建立带头结点线性链表*/(N O DE*h e ad,*p,*q ；i n t i ；p=(N O DE*)m a11o c(s i z e o f(N O DE)；1 h e ad=p;p-n e x t=N ULL；2 q-p;f o r(i=l；i d at a=i；i f(i=l)【3】p-n e x t=N U L L；e l s e 4 p-n e x t=q-n e x t;
16、5 q-n e x t=p;r e t u r n (h e ad)；)3、下面是在含有头结点单向列表中删除第i 个结点，请在空格内填上合适语句、i n t d e l e t e(N O DE*h e ad,i n t i)(N 0DE*p,*q；i n t j；q 二 h e ad；j=0；w h i l e(q!=N ULL)&(j n e x t；j+；i f(q=N ULL)r e t u r n(0);1 p=q-next；【2】q-next=p-next；f r e e (p)；r e t u r n(1)；)五、完成：试验1一一线性表依据试验要求【见教材P 2O T2】认真完成
17、本试脸，并提交试验汇报、数据结构【本】课程作业2【本部分作业覆盖教材第3-5章内容】一、单项选择题1、若让元素1,2,3依次进栈，则出栈次序不可能为 CLA、3,2,1B、2,1,3C、3,1,2D、1,3,22、一个队列入队序列是1,2,3,4、则队列输出序列是 BLA、4,3,2,1B、1,2,3,4C、1,4,3,2D、3,2,4,13、向次序栈中压入新元素时，应 该【A】、A、先移动栈顶指针，再存入元素B、先存入元素,再移动栈顶指针C、前后次序无关紧要D、同时进行4、在一个栈顶指针为t o p 链栈中，将一个p指针所指结点入栈,应实施 CLA、t o p-n e x t=p；B、p-n
18、 e x t=t o p-n e x t；t o p-n e x t=p；C、p-n e x t=t o p；t o p=p；D、p-n e x t=t o p-n e x t；t o p=t o p-n e x t ；5、在一个栈顶指针为t o p 链栈中删除一个结点时，用 x保留被删结点值，则实施【B】、A、x=t o p；t o p=t o p-n e x t ；B、x=t o p-d at a；C、t o p=t o p-n e x t；x=t o p-d at a；D、x=t o p-d at a；t o p=t o p-n e x t；6、通常情况下,将递归算法转换成等价非递归算法
19、应该设置 ALA、栈 B、队列C、堆栈或队列D、数组7、表示式a表示式-d后缓表示式是【B】、A、abcd*+-B、abc+*d-C、abc*+cH)、-+*abcd8、判定一个次序队列s q【最多元素为m 4为空条件是【口、A、s q-r e ar-s q-f r o n t=m o B,s q-r e ar-s q-f r o n t-l=m oC s q-f r o n t=s q-r e ar D s q-f r o n t=s q-r e ar+19、判定一个循环队列Q【最 多 元 素 为 为 空 条 件是【A】、A、Q-f r o n t=Q-r e ar BQ-f r o n t
20、!=Q-r e arC、Q-f r o n t=(Q-r e ar+1)%m(DQ-f r o n t!=(Q-r e ar+l)%m o10、判定栈S满【元素个数最多n个】条件是 C.A、s-t o p=0Bx s-t o p!=0C、s-l o p=二 n-l D、s-t o p!=n-l11、一个队列入队次序是a,b,c,d,则离队次序是【B】、A、a,d,cbB、a,b,c,d C,d,c,b,aD、c,b,d,a12、假如以链表作为栈存放结构，则退栈操作时【口、A、必需判定栈是否满B、判定栈元素类型C、必需判定栈是否空D、对栈不作任何判定13、在处理计算机主机和打印机之间速度不匹配问
21、题时通常设置一个打印数据缓冲区，主机将要输出数据依次写入缓冲区中，而打印机则从缓冲区中取出数据打E 八该缓冲区应该是一个【B】结构、A、堆栈B、队列C、数组D、先性表14、一个递归算法必需包含【B】、A,递归部分 B.终止条件和递归部分C、迭代部分D,终止条件和迭代部分15.从一个栈顶指针为to p链栈中删除一个结点时，用变量x 保留被删结点值，则实施 A .A,x=to p-d ata；to p=to p-ne xt；B,x=to p-d ata；C、to p=to p-ne xt：x=to p-d ata；D,to p=to p-ne xt;x=d ata;16,在一个链队中，假设f 和
22、r分别为队头和队尾指针，则删除一个结点运算为 C ,A、r=f-ne xt；B、r=r-ne xt；C、f=f-ne xt；D、f=r-ne xt;17,在一个链队中，假设f和 r分别为队头和队尾指针，则插入s 所指结点运算为【B】、A,f-ne xt=s；f=s；B,r-ne xt=s；r=s；C、s-ne xt=r；r=s：D,s-ne xt=f；f=s；18.以下陈说中正确是【A】、A、串是一个特殊线性表B、串长度必需大于零C、串中元素只能是字母D、空串就是空白串19 .设有两个串p 和 q,其中q 是 p 子串，q 在 p 中首次出现位置算法称为 0 ,A,求子串B、连接C,匹配I）、
23、求串长2 0、串 是 D ,A、不少于一个字母序列B、任意个字母序列C、不少于一个字符序列D、有限个字符序列2 1,串长度是指 B ,A、串中所含不一样字母个数B、串中所含字符个数C、串中所含不一样字符个数D、串中所含非空格字符个数2 2、若串S=E ng lish”，其子串个数是【D】、A,9 B、16C,3 6D、2 82 3、串和一般线性表相比较，它特殊性表现在C.A,次序存放结构B、链接存放结构C,数据元素是一个字符D、数据元素能够任意2 4、空串和空格串B.A.相同B、不相同C、可能相同D、无法确定2 5、两个字符串相等条件是 D LA.两串长度相等B,两串包含字符相同C.两串长度相
24、等，而且两串包含字符相同D,两串长度相等，而且对应位置上字符相同2 6,在实际应用中，要输入多个字符串，且长度无法预定、则应该采纳【A】存放比较适宜 1A,链式B、次序C、堆结构D、无法确定2 7、一维数组A采纳次序存放结构，每个元素占用6个字节，第 6 个元素存放地址为10 0,则该数组首地址是 C .A,64 B,2 8C,7 0 D,9 02 8、稀疏矩阵采纳压缩存放目标关键是 D ,A,表示变得简单B、对矩阵元素存取变得简单C,去掉矩阵中多出元素D、降低无须要存放空间开销2 9、一个非空广义表表头【C】、A,不可能是原子B、只能是子表C,只能是原子D、能够是子表或原子3 0,常对数组进
25、行两种基础操作是 C .A,建立和删除B、索引和、和修改C,查找和修改D、查找和索引3 1、设二维数组A 5 6按行优先次序存放在内存中,已知A 0 0 起始地址为1 0 0 0,每个数组元素占用5个存放单元，则元素A 4 4地址为 A ,A、1 1 40 B,1 1 45C,1 1 2 0 D,1 1 2 53 2,设有一个2 0阶对称矩阵A,采纳压缩存放方法,将其下三角部分以行序为主序存放到一维数组B中【数组下标从1开始】，则蛆阵中元素a”,在一维数组B中下标 是 D .A,41 B.3 2 C、1 8 D、3 8二、填空题1、栈是限定在表一端进行插入和删除操作线性表，又称为后进先出一、2
26、、循环队列队头指针在队尾指针 下一个位置，队列是“满”状态3、在队列次序存放结构中，当插入一个新队列元素时，尾指针增1，当删除一个元素队列时，头指针 增、4.循环队列引入，目标是为了克服假上溢、5,向次序栈插入新元素分为三步：第一步进行栈是否满判定，判定条件是 s-t o p=M A XS I Z E-l _ ；第二步是修改 栈 顶 指 针;第三步是把新元素赋给 栈顶对应数组元素_、一样从次序栈删除元素分为三步：第一步进行_ _ _栈是否空 判定，判定条件是_ _ _ _s-top=-l、第二步是把栈顶元素;第三步 修改栈顶指针.6.假设以S和X分别表示入栈和出栈操作，则对输入序列a,b,c,
27、d,e 一系列栈操作S S XS XS S XXX以后，得到输 出序列 为_ _ _ _b c e d a、7、一个递归算法必需包含_ _ _终止条件 和_递归部分、8、判定一个循环队列L U【最多元素为侬】为空条件是 LU-front=LU-rear、9,在将中缀表示式转换成后缀表示式和计算后缀表示式算法中，全部需要使用栈，对于前者,进入栈中元素为表示式中 运算符.而对于后者，进入栈元素为操作数,中缀表示式（a+b）/c （f-d/c）所对应后缀表示式 是 a b+c/f d e/-.1 0、向一个栈顶指针为h链栈中插入一个s所指结点时，可实施_ _s-n e xt=h 和h=s；操作、（结
28、点指针域为n e xt）1 1,从一个栈顶指针为h链栈中删除一个结点时，用x保留被删结点值，可实施x=h-d a t a；和_h=h-nex t、（结点指针域为n e xt）1 2、在一个链队中，设f和r分别为队头和队尾指针,则插入s所指结点操作为 r-n e xt=s 和r=s；（结点指针域为n e xt）1 3、在一个链队中，设f和r分别为队头和队尾指针,则删除一个结点操作为_f=f-n e xt _ _ _ _ _ _、（结点指针域为n e xt）1 4.串是一个特殊线性表，其特殊性表现在组成串数据 元 素 全 部 是 一 字 符、1 5、串两种最基础存放方法是次序存放方法和 链 式 存
29、放方法.1 6.空串长度是 0 ；空格串长度是 空格字符个数、1 7,需要压缩存放矩阵可分为 特殊矩阵和 稀疏 矩阵两种、1 8.设广义表L=,则表头是,表尾是.L长度是 2 、1 9、广义表 A a,b,c l ,(d.e.f)表尾为_ _ _ _d.e.f、2 0,两个串相等充足必需条件是 串长度相等且对应位置字符相等、2 1.设有n阶对称矩阵A,用数组s进行压缩存放，当i N j时,A数组元素a”对应于数组s数组元素下标为_i(i-l)/2+j、【数组元素下标从1开始】2 2、对稀疏矩阵进行压缩存放,矩阵中每个非零元素对应三元组包含该元素 行下标.列下标_和 非零元素值三项信息、三、问答
30、题1、简述栈和通常线性表区分、答:栈是一个优异后出线性表，栈插入和删除操作全部只能在栈顶进行，而通常线性表能够在线性表任何位置进行插入和删除操作、2.简述队列和通常线性表区分、队列是一个优异先出线性表，队列插入只能在队尾进行，队列删除只能在队头进行，而通常线性表能够在线性表任何位置进行插入和删除操作、3、链栈中为何不设头结点？答：因为链栈只在链头插入和删除结点，不可能在链表中间插入和删除结点，算法实现很简单，所以通常不设置头结点、4、利用一个栈，则：1 假如输入序列由A,B,C组成，试给出全部可能输出序列和不可能输出序列、2 假如输入序列由A,B,C,D组成，试给出全部可能输出序列和不可能输出
31、序列、答：1 栈操作特点是后进先出，所以输出序列有：A入,A出,B入,B出,C入C出，输出序列为A B C、A入,A出，B入,C入,C出，B出，输出序列为A C B.A入,B入,B出，A出，C入,C出，输出序列为B A C.A入，B入,B出，C入,C出，A出，输出序列为B C A,A入,B入,C入,C出，B出，A出，输出序列为C B A.由A,B,C组成数据项，除上述五个不一样组合外，还有一个C,A,B组合、但不可能先把C出栈，再把A出栈，【A不在栈顶位置】，最终把B出栈，所以序列C A B不可能由输入序列A,B,C经过栈得到、2 根据上述方法，可能输出序列有：A B C D,A B D C,
32、A C B D.A C D B.A D C B,B A C D,B A D C,B C A D,B C D A,B D C A,C B A D,C B D A,C D B A,D C B A,不可能输出序列有：D A B C,A D B C,D A C B,D B A C,B D A C,D B C A.D C A B,C D A B.C A D B,C A B D5、用S表示入栈操作,X表示出栈操作，若元素入栈次序为1 2 3 4,为了得到1 3 42出栈次序，对应S和X操作串是什么？答：应是S X S S X S X X、各操作结果以下：S 1入栈X I出栈输出序列：1S 2入栈S 3入栈
33、X 3出栈输出序列：1 3S 4入栈X 4出栈输出序列：1 3 4X 2出栈输出序列：1 3 426、有5个元素，其入栈次序为:A、B、C、D、E,在多种可能出栈次序中，以元素C、D最先次序有哪多个？答:从题中可知，要使C第一个且D第二个出栈，应是A入栈,B入栈,C入栈,C出栈,1)入栈、以后能够有以下多个情况：1 B出栈,A出栈,E入栈,E出栈，输出序列为：C D B A E、2 B出栈,E入栈,E出栈,A出栈，输出序列为C D B E A、3 1 E入栈,E出栈,B出栈,A出栈，输出序列为C D E B A所以可能次序有：C D B A E,C D B E A.C D E B A7、写出以
34、下运算式后缀算术运算式(D 3 x 2+x T/x+5(A+B)*C-D/(E+F)+G答；对应后缀算术运算式3 x 2-*x+l x/-5+A B+O D E F+/-G+8、简述广义表和线性表区分和联络、答:广义表是线性表推广，它也是n(n 0)个元素a i,a 2”有限序列，其中a 1或是原子或是一个广义表、所以，广义表是一个递归数据结构，而线性表没有这种特征，线性表能够看成广义表特殊情况，当 出全部是原子时,广义表退化成线性表、四、程序填空题1、在下面空格处填写合适语句，以使下面链式队列取出元素算法完整、i n t w r i t e(L i n k Q u e u e*q)Q u e
35、 u e N o d e*p；i f (q-f r o n t=q-r e a r)/*队空*/pr i n t f(u n d e r f l o w)；e x i t (0)；w h i l e (q-f r o n t-n e x t!二N U L L)p=q-f r o n t-n e x t;(1)q-f r o n t-n e x t=p-n e x t ；pr i n t f(a%4 dM,p-d a t a);(2)f r e e(p)；_ _ _ _ _ _ _ _ _ _ _【3】q-rear=q-front；/*队空时，头尾指针指向头结点*/)五、综合题1、设栈S和队列Q
36、初始状态为空，元素e l,e 2,e 3,e 4,e 5和e 6依次经过S,一个元素出栈后即进队列Q,若6个元素出队序列是。2,4居3,6,6 5,6 1,则栈S容量最少应该是多少？答：出队序列是e 2,e 4,e 3,e 6,e 5,e l过程：e l入 栈【栈底到栈顶元素是e l】(2)e 2入 栈【栈底到栈顶元素是e l,e 2(3九2出栈【栈底到栈顶元素是e l】e 3入 栈【栈底到栈顶元素是e l,e 3(5)e 4入 栈 栈底到栈顶元素是e l,e 3,e 4(6)e 4出栈【栈底到栈顶元素是e l,e 3 e 3出栈【栈底到栈顶元素是e l】e 5入 栈【栈底到栈顶元素是e l,
37、e 5(9)e 6 入 栈【栈底到栈顶元素是e l,e 5,e 素e 6 出 栈【栈底到栈顶元素是e l,e 5(U)e 5 出 栈【栈底到栈顶元素是e l】(1 2)e l 出 栈【栈底到栈顶元素是空】栈中最多时有3个元素，所以栈S容量最少是3、2、假设用循环单链表实现循环队列，该队列只使用一个尾指针r e a r,其对应存放结构和基础算法以下；1 1 初始化队列i n i l q u e u e(Q)：建立一个新空队列Q、2 入队列e n q u e u e(Q,x)：将元素x插入到队列Q中、3 出队列d e l q u e u e(Q)：从队列Q中退出一个元素、4 取队首元素g e t
38、h e a d(Q)：返回目前队首元素、5 判定队列是否为空：e mpl y q u e u e(Q)、6 显示队列中元素：d i spq u e u e(Q)、算法设计以下：/*只有一个指针r e a r 链式队基础操作*/#i n c l u d e t y pe d e f c h a r e l e mt y pe；s t r u e t n o d e/*定义链队列结点*/(e l e mt y pe d a t a；st r u c t n o d e*n e x t；);t y pe d e f st r u c t q u e u c/*定义链队列数据类型*/(st r u c
39、 t n o d e*r e a r；L i n k Q u e u e;v o i d i n i t q u e u e (L i n k Q u e u e*Q)/*初始化队列*/(Q 二(st r u c t q u e u e*)ma l l o c(si z e o f(st r u c t q u e u e)；Q-r e a r=N U L L；v o i d e n q u e u e (L i n k Q u e u e*Q,c l e mt y pe x)/*入队算法*/(st r u c t n o d e*s,*p；s=(st r u c t n o d e*)ma
40、l l o c(si z e o f(st r u c t n o d e)；s-d a t a=x；i f (Q-r e a r=N U L L)/*原为空队时*/(Q-r e a r=s；s-n e x t=s；)e l se/*原队不为空时*/p=Q-r e a r-n e x t；/*p 指向第一个结点*/Q-r e a r-n e x l=s；/*将 s 链接到队尾*/Q-r e a r=s;/*Q-r e a r 指向队尾*/s-n e x t=p；)v o i d d e l q u e u e (L i n k Q u e u e*Q)/*出队算法*/：st r u c t n
41、 o d e*t；i f(Q-r e a r=N U L L)pr i n t f (队列为空！n)；r e t u r n(0);)e l se i f (Q-r e a r-n e x t=Q-r e a r)/*只有一个结点时*/(t=Q-r e a r；Q-r e a r=N U L L；e l se/*有多个结点时*/(t=Q-r e a r-n e x t;/*t 指向第一个结点*/Q-r e a r-n e x t=t-n e x t；/*引成循环链/)f r e e(t)；e l e mt y pe g e t h e a d (L i n k Q u e u e*Q)/*取队
42、首元素算法*/(i f(Q-r e a r=N U L L)pr i n t f (队列为空！n)；e l ser e t u r n(Q-r e a r-n e x t-d a t a)；i n t e mpt y q u e u e (L i n k Q u e u e*Q)/*判定队列是否为空算法*/(i f (Q-r e a r=N U L L)r e t u r n (1)；/*为空，则返回t r u e*/e l se r e t u r n (0)；/*不为空，则返回 f l a se*/)v o i d d i spq u e u e (L i n k Q u e u e*Q)
43、/*显示队列中元素算法*/Ist r u c t n o d e*p=Q-r e a r-n e x t；pr i n t f (队列元素：)；w h i l e(p!=Q-r e a r)(pr i n t f(%c,p-d a t a);p=p-n e x t；pr i n t f(%c n,p-d a t a)；六、完成:试验2一栈、队列、递归程序设计依据试验要求【见教材P双】认真完成本试验，并提交试验汇报、数据结构【本】课程作业作业3【本部分作业覆盖教材第6-7章内容】一、单项选择题1、假定一棵二叉树中，双分支结点数为1 5,单分支结点数为3 0,则叶子结点数为【B】、A.1 5 B,
44、1 6 C,1 7 D,4 72,二叉树第k层上最多有【B】个结点、A,2 k B、2-1C.2-1 D,2 k 3、二叉树深度为k,则二叉树最多有【D】个结点、A.2 k B、2 k-lC,2kD,2-14.设某一二叉树先序遍历为a b d e c,中序遍历为d b e a c,则该二叉树后序遍历次序是 C ,A,a b d e c B,d e b a c C,d e b c a D,a b e d c5,将含有1 5 0个结点完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1,则编号为6 9结点双亲结点编号为【B】、A,3 3 B,3 4 C、3 5 D、3 66,
45、假如将给定一组数据作为叶子数值，所结构出二叉树带权路径长度最小，则该树称为L A】、A,哈夫曼树B、平衡二叉树C,二叉树D、完全二叉树7,下面相关二叉树说法正确是【A】、A、二叉树中度为0结点个数等于度为2结点个数加1B,二叉树中结点个数必大于0C,完全二叉树中，任何一个结点度，或为0或为2D、二叉树度是28,在一棵度为3树中，度为3结点个数为2,度为2结点个数为1,则度为0结点个数为 C .A、4 B、5 C、6D、79、在一棵度含有5层满二叉树中结点总数为【A】、A、3 1 B、3 2 C、3 3 D、1 61 0、利用n个值作为叶结点权生成哈夫曼树中共包含有(D)个结点、A、n B s
46、n+lC、2*n D、2*n-l1 1、利用3、6、8、1 2这四个值作为叶子结点权，生成一棵哈夫曼树，该树中全部叶子最长带权路径长度为(A)、A、1 8 B、1 6C、1 2 D、3 01 2,在一棵树中，【口 没有前驱结点、A、分支结点B、叶结点C、树根结点D、空结点1 3、在一棵二叉树中，若编号为i结点存在右儿童，则右儿童次序编号为 C .A,2 iB,2 i-lD,2 i+lC,2 i+21 4,设一棵哈夫曼树共有n个叶结点，则该树有【B】个非叶结点、A,n B.n-lC,n+II).2 n1 5,设一棵有n个叶结点二叉树，除叶结点外每个结点度数全部为2,则该树共有【B】个结点、A、2
47、 n B、2 n-lC x 2 n+lD、2 n+21 6、在一个图G中，全部顶点度数之和等于全部边数之 和 C 倍、A、1/2 B、1 C、2 D、41 7、在一个有像图中，全部顶点入度之和等于全部顶点出度之和 B 倍、A、邻接矩阵表示法B、邻接表表示法C、逆邻接表表示法D、邻接表和逆邻接表1 8、在图存放结构表示中，表示形式唯一是【C】、A、n B、n+lC、n-lD、n/21 9、一个含有n个顶点无向完全图包含【A】条边、A n n-1 B、n n+1 C、n n-1 /2 D、n n+1/22 0、对于含有n个顶点图，若采纳邻接矩阵表示，则该矩阵大小为【B】、A、n B、n2C、n I
48、D、n-1 J2 1、对于一个含有n个顶点和e条边无向图，若采纳邻接表表示，则全部顶点邻接表中结点总数 为【D】、A、n B、e C、2 n D、2 e2 2、在有向图邻接表中，每个顶点邻接表链接着该顶点全部【B】邻接点、A、入边B、出边C、入边和出边D、不是入边也不是出边2 3、邻接表是图一个 B、A、次序存放结构B、链式存放结构C、索引存放结构D、散列存放结构2 4、假如从无向图任一顶点出发进行一次深度优先搜索即可访问全部顶点，则该图一定是、A、完全图B、连通图C、有回路D、一棵树2 5、下面相关图遍历说法错误是【口、A、连通图深度优先搜索是一个递归过程B、图广度优先搜索中邻接点寻求含有“
49、优异先出”特点C、非连通图不能用深度优先搜索法D、图遍历要求每一顶点仅被访问一次2 6、无向图邻接矩阵是一个【A】、A,对称矩阵B、零矩阵C、上三角矩阵D、对角矩阵2 7,图深度优先遍历算法类似于二叉树L4】遍历、A、先序B、中序C、后序D、层次28、已知下图所表示一个图，若从顶点V,出发，按深度优先搜索法进行遍历，则可能得到一个顶点序列为二、填空题1、结点度是指结点所拥有子树树木或后继结点数、2、树度是指 树中全部结点度最大值、3、度大于0结点称作_ _ _ 分支结点 或_ _ _ _非终端结点_ _ _、4、度等于0结点称作 叶子结点_或_终端结点_ _ _、5、在一棵树中，每个结点_子树
50、根_或说每个结点_ 后继结点 称为该结点 儿 童 结 点,简称为儿童、6,从根结点到该结点所经分支上全部结点称为该结点祖先、7、树深度或高度是指 树中结点最大层数_、8、含有n个结点完全二叉树深度是_ _ _ _log?+1、9、先序遍历二叉树操作定义为；若二叉树为空，则为空操作，不然进行以下操作，访问二叉树一根结点_；先序遍历二叉树 左子树,先序遍历二叉树 右子树、1 0.中序遍历二叉树操作定义为；若二叉树为空，则为空操作，不然进行以下操作，中序遍历二叉树 左子C,A,VMVMVMVMB、VWMVMV3VMC.VNMVMV3VMD、VMMVNMVM树;访问而叉树根结点_，中序遍历二叉树_ 右