广义表试题附带答案

广义表经典试题附带答案考试时间：______分钟总分：______分姓名：______一、单项选择题1.广义表L=(a,b,c)是线性表吗？A.是B.否C.视情况而定D.不确定2.广义表L=(a,(b,c))，Head(Tail(L))是什么？A.aB.(a)C.bD.(b)3.广义表L=(a,(b,c))，Tail(Tail(L))是什么？A.aB.(a)C.bD.()4.广义表(a,(b,(c,(d))))的长度是多少？A.1B.2C.3D.45.广义表(a,(b,(c,(d))))的深度是多少？A.2B.3C.4D.56.广义表(a,(b,(c,(d))))，Head(Head(Tail(Tail(L))))是什么？A.aB.bC.cD.d7.广义表的长度是指？A.表中原子结点的个数B.表中子表结点的个数C.表中元素（原子或子表）的个数D.表中结点的个数8.广义表的深度是指？A.表中原子结点的最大层次B.表中子表结点的最大层次C.表中元素（原子或子表）的最大层次D.表中括号的最大层数9.广义表(a)的长度和深度分别是？A.1和1B.1和0C.0和1D.0和010.广义表(a,(b,c))的Head是什么？A.(a,(b,c))B.aC.(b,c)D.b11.广义表(a,(b,c))的Tail是什么？A.(a,(b,c))B.aC.(b,c)D.b12.广义表G=(a,(b,(c,d)))，Tail(Tail(G))是什么？A.(c,d)B.((c,d))C.(b,(c,d))D.(d)13.广义表(a,b,c)与(a,(b,c))相等吗？A.相等B.不相等C.视情况而定D.无法判断14.关于广义表Head(G)的说法，正确的是？A.Head(G)一定是原子B.Head(G)一定是子表C.Head(G)一定是空表D.Head(G)可能是原子或子表15.关于广义表Tail(G)的说法，正确的是？A.Tail(G)一定是原子B.Tail(G)一定是子表C.Tail(G)一定是空表D.Tail(G)可能是原子或子表16.广义表通常采用哪种存储结构？A.顺序存储B.链式存储C.索引存储D.散列存储17.广义表的链式存储中，每个结点包含哪些指针域？A.1个B.2个C.3个D.4个18.广义表(a,(b,(c,(d))))，Head(Head(Tail(L)))是什么？A.aB.(b,(c,(d)))C.bD.(c,(d))19.广义表(a,(b,c),d)的长度是？A.1B.2C.3D.420.广义表(a,(b,c),d)的深度是？A.2B.3C.4D.5二、多项选择题1.下列关于广义表性质的描述，正确的有？A.广义表可以是线性表B.广义表可以是递归表C.广义表可以是多重表D.广义表中的元素可以是原子或子表2.下列关于广义表Head和Tail操作的描述，正确的有？A.Head(Head(G))可能是原子B.Tail(Tail(G))可能是空表C.Head(Tail(G))一定是子表D.Tail(Head(G))一定是子表3.下列哪些广义表是线性表？A.(a,b,c)B.(a,(b,c))C.((a,b),c)D.(a)4.关于广义表存储结构的描述，正确的有？A.广义表采用链式存储B.广义表采用顺序存储C.结点中包含tag标志位D.结点中包含hp和tp两个指针5.下列关于广义表深度的说法，正确的有？A.原子结点的深度为0B.空表的深度为1C.广义表的深度等于其最外层括号的层数D.广义表的深度是所有子表深度的最大值加16.下列哪些运算可以在广义表上进行？A.求长度B.求深度C.求表头D.求表尾7.关于广义表G=(a,(b,c))，下列说法正确的有？A.G的长度为2B.G的深度为2C.G的Head是aD.G的Tail是((b,c))8.下列关于广义表与线性表区别的描述，正确的有？A.广义表中的元素可以是原子，也可以是子表B.广义表中的元素只能是原子C.广义表可以共享D.广义表可以递归三、填空题1.广义表L=(a,b,c)，则Head(L)是______，Tail(L)是______。2.广义表L=(a,(b,c))，则Head(Tail(L))是______，Tail(Tail(L))是______。3.广义表G=(a,(b,(c,d)))，则G的长度是______，G的深度是______。4.广义表(a)的深度是______，长度是______。5.广义表(a,(b,(c,(d))))，则Head(Head(Tail(Tail(L))))是______。6.广义表L=(a,(b,c))，则Head(Tail(L))是______。7.广义表L=(a,(b,c))，则Tail(Tail(L))是______。8.广义表(a,b,c)是广义表______的特例。9.广义表L=(a,(b,c))，若Head(L)为H，Tail(L)为T，则L=______。10.广义表(a,(b,(c,d)),e)的深度是______。四、简答题1.给定广义表L=(a,(b,(c,(d))))，请回答：(1)L的长度是多少？(2)L的深度是多少？(3)Head(Tail(L))是什么？2.给定广义表G=(a,(b,(c,(d))))，请画出其链式存储结构图（用结点结构：tag,data/hp,tp描述）。3.写出广义表L=(a,b,c)的Head和Tail操作序列结果：(1)Head(Head(Tail(L)))(2)Head(Tail(Tail(Tail(Tail(L)))))4.简述广义表长度和深度的定义。五、算法设计题1.设广义表GL采用头尾链表存储结构，请编写一个递归算法，求广义表的长度。2.设广义表GL采用头尾链表存储结构，请编写一个递归算法，求广义表的深度。3.设广义表GL采用头尾链表存储结构，请编写一个递归算法，复制广义表GL到GLCopy。试卷答案一、单项选择题1.A解析：广义表是线性表的推广。当广义表中只包含原子元素时，它表现为一个线性表。广义表L=(a,b,c)仅包含三个原子元素，因此它是线性表。2.D解析：对于广义表L=(a,(b,c))，首先执行Tail(L)，去掉第一个元素a，得到子表((b,c))。然后对该结果执行Head操作，即取子表((b,c))的表头，结果为(b,c)。3.D解析：执行Tail(Tail(L))。第一步Tail(L)得到((b,c))；第二步对((b,c))执行Tail操作，去掉其表头(b,c)，得到空表()。4.B解析：广义表L=(a,(b,(c,(d))))中，包含两个元素：第一个元素是原子a，第二个元素是子表(b,(c,(d)))。因此长度为2。5.C解析：计算深度。原子深度为0。-(b,(c,(d)))的深度：Max(0,深度((c,(d))))+1。-(c,(d))的深度：Max(0,深度((d)))+1=Max(0,1)+1=2。-(b,(c,(d)))的深度：Max(0,2)+1=3。-最外层L=(a,(b,(c,(d))))的深度：Max(0,3)+1=4。6.C解析：Head(Head(Tail(Tail(L))))。-Tail(L)=(b,(c,(d)))。-Tail(Tail(L))=((c,(d)))。-Head(Tail(Tail(L)))=(c,(d))。-Head((c,(d)))=c。7.C解析：广义表的长度是指表中元素（原子或子表）的个数。8.C解析：广义表的深度是指表中元素的最大层次数。原子所在的层次为0，子表的深度是其所有元素深度的最大值加1。9.A解析：广义表(a)包含1个元素，即原子a，所以长度为1。该表只有一层括号，深度为1。10.B解析：广义表G=(a,(b,c))的Head操作取表头，即第一个元素，结果为a。11.C解析：广义表G=(a,(b,c))的Tail操作取表尾，即去掉第一个元素后剩下的部分，结果为((b,c))。12.B解析：执行Tail(Tail(G))。G=(a,(b,(c,d)))。-Tail(G)=((b,(c,d)))。-Tail(Tail(G))=Tail(((b,(c,d))))=(c,d)。13.B解析：广义表L=(a,b,c)由三个原子元素组成。广义表L=(a,(b,c))由一个原子和一个子表组成。两者结构不同，不相等。14.D解析：Head(G)返回广义表G的第一个元素。根据G的定义，第一个元素可能是原子（如a），也可能是子表（如(b,c)），所以可能是原子或子表。15.B解析：Tail(G)返回广义表G去掉第一个元素后剩下的部分。无论G的第一个元素是什么，剩下的部分始终是一个广义表（可能是空表）。16.B解析：由于广义表的长度可变且包含嵌套结构，顺序存储结构难以高效实现，因此通常采用链式存储结构。17.B解析：在广义表的头尾链式存储中，每个结点包含两个指针域：一个指向表头（hp），一个指向表尾（tp）。18.B解析：Head(Head(Tail(L)))。-Tail(L)=(b,(c,(d)))。-Head(Tail(L))=(b,(c,(d)))。-Head((b,(c,(d))))=(b,(c,(d)))。19.C解析：广义表L=(a,(b,c),d)包含三个元素：a,(b,c),d。20.C解析：计算深度。-a深度0。-(b,c)深度Max(0,0)+1=1。-d深度0。-整个表L的深度=Max(0,1,0)+1=2。二、多项选择题1.A,B,C,D解析：广义表是线性表的推广，它可以包含原子，也可以包含子表，因此可以是线性表、递归表或多重表。2.A,B解析：-A正确：Head(Head(G))是对表头再取表头，结果可能是原子。-B正确：Tail(Tail(G))是连续两次取表尾，结果可能是空表。-C错误：Head(Tail(G))返回的是G的第二个元素，它可能是原子（如G=(a,b)），不一定是子表。-D错误：Tail(Head(G))操作中，Head(G)是一个元素，如果G=(a,b)，Head(G)=a（原子），Tail(原子)是无意义的操作。3.A,C解析：-A(a,b,c)是线性表。-C((a,b),c)是线性表（元素是原子）。-B(a,(b,c))不是线性表，因为包含子表。-D(a)是线性表。4.A,C,D解析：广义表通常采用链式存储结构（A）。结点中需要标志位tag来区分原子和子表（C）。结点中包含hp（表头指针）和tp（表尾指针）（D）。顺序存储结构（B）难以处理变长和嵌套。5.A,B,D解析：-A正确：原子深度为0。-B正确：空表()的深度定义为1。-C正确：深度即括号嵌套的层数。-D正确：深度是所有子表深度的最大值加1。6.A,B,C,D解析：广义表支持求长度、求深度、求表头、求表尾等基本运算。7.A,C解析：-A正确：G=(a,(b,c))有两个元素。-C正确：Head(G)=a。-B错误：G=(a,(b,c))的深度为2（一层a，一层(b,c)）。-D错误：Tail(G)=((b,c))，而不是(b,c)。8.A,C,D解析：-A正确：广义表元素可以是原子或子表。-C正确：广义表可以共享（如L=((a,b),L)）。-D正确：广义表可以递归（如L=(a,L)）。-B错误：线性表元素只能是原子。三、填空题1.a,(b,c)解析：Head取表头，Tail取表尾。2.(b,c),()解析：Tail(L)为(b,c)，Head(Tail(L))为(b,c)；Tail(Tail(L))为()。3.2,3解析：长度为2；深度计算：a(0),(b,(c,d))->b(0),(c,d)->c(0),d(0)->Max(0,0,0)+1=1,Max(0,1)+1=2,Max(0,2)+1=3。4.1,1解析：(a)只有一个元素a，长度为1；只有一层括号，深度为1。5.c解析：Tail(Tail(L))->((c,(d)))->Head->(c,(d))->Head->c。6.(b,c)解析：Tail(L)=(b,c)，Head(Tail(L))=(b,c)。7.()解析：Tail(Tail(L))=()。8.线性表解析：广义表是线性表的推广，仅含原子的广义表退化为线性表。9.(a,(b,c))解析：广义表可以由Head(L)和Tail(L)组合还原。10.3解析：a(0),(b,(c,d),e)->b(0),(c,d),e(0)->c(0),d(0),e(0)。子表深度为1。整个表深度=Max(0,1,0)+1=2。等等，(b,(c,d),e)深度是2。整个表L=(a,(b,(c,d),e))深度是Max(0,2)+1=3。四、简答题1.答案：(1)L的长度是2。(2)L的深度是4。(3)Head(Tail(L))是(b,(c,(d)))。解析：(1)L=(a,(b,(c,(d))))包含两个元素：a和(b,(c,(d)))。(2)深度计算：原子深度为0。最内层(d)深度为1。((c,(d)))深度为Max(0,1)+1=2。((b,(c,(d))))深度为Max(0,2)+1=3。整个L深度为Max(0,3)+1=4。(3)Tail(L)去掉a，得到((b,(c,(d))))。Head操作取其表头，即为(b,(c,(d)))。2.答案：链式存储结构图示如下（结点结构：Tag=0原子，Tag=1子表；原子结点含data，子表结点含hp,tp）：-结点1(Tag=1):hp指向a,tp指向结点2-结点2(Tag=1):hp指向b,tp指向结点3-结点3(Tag=1):hp指向结点4,tp指向NULL-结点4(Tag=1):hp指向结点5,tp指向NULL-结点5(Tag=0):data=d,tp指向NULL解析：广义表L=(a,(b,(c,(d))))采用头尾链表法存储。-最外层结点：Tag=1,hp指向原子a,tp指向子表结点。-子表结点：Tag=1,hp指向原子b,tp指向子表结点。-递归过程直到原子d结束。3.答案：(1)b(2)空表（或错误）解析：(1)L=(a,b,c)。Tail(L)=(b,c),Head(Tail(L))=b。Head(Head(Tail(L)))=Head(b)=b。(2)L=(a,b,c)。Tail(Tail(L))=c。Tail(Tail(Tail(L)))=Tail(c)，由于c是原子，Tail(c)操作无意义或返回空表。Tail(Tail(Tail(Tail(L))))=Tail(空表)=空表。4.答案：-长度：广义表中元素的个数。-深度：广义表中元素的最大层次数。原子所在的层次为0，子表的深度是其所有元素深度的最大值加1。解析：长度是线性统计元素个数。深度是递归定义的，反映了广义表的嵌套结构层次。五、算法设计题1.答案：```cintLength(GL){if(GL==NULL)return0;elsereturn1+Length(Tail(GL));}```解析：递归思路：如果广义表为空，长度为0；如果不为空，广义表包含一个表头元素和一