15-16(1)数据结构复习题带答案

1、数据结构复习题第一章概论一. 选择题1、研究数据结构就是研究（D ）。B.数据的存储结构D.数据的逻辑结构、存储结构及其基本操作B.正确性和简单性D.数据复杂性和程序复杂性A. 数据的逻紺结构C.数据的逻辑结构和存储结构2、算法分析的两个主要方面是（AA. 空间复杂度和时间复杂度C 可读性和文档性3、计算机中的算法指的是解决某一个问题的有限运算序列，它必须貝备输入、输出、（B ） 等5个特性。A町行性.可移植性利町扩充性B.可行性.有穷性和确定性D.易读性、稳定性和确定性C确定性.有穷性和稳定性4、卜面程序段的时间复杂度是（C ）« for （i=0;i<m;i+）for（j=

2、0;j<n;j+）ai jl=i*j；A. 0(m2)B. 0(n2)C. O(m*n)D. 0(m+n)5. 算法是（D ）oA.计算机程序B.解决问题的计算方法C.排序算法D.解决问题的方法和步骤，是规则的冇穷集介6. 某算法的语句执行频度为（3n+n丄ogm+n'+S），其时间复朵度表示（C ）。A. 0（n）B. O（nlog2n）C 0（n二）D. O（log2n）7、卞而程序段的时间复杂度为（C ）owhile （i<=n）i=i*3;A. 0（n）B. 0（3n） C. O（log3n） D. 0（n3）8、数据结构是一类数据的表示及其相关操作，它一般包括三个

3、方面的内容：数据的逻辑结 构、（D ）和数据的运算。A. 数据的操作B.数据的算法C.数据的连接D.数据的存储结构9、捕象数据类型的三个组成部分分别为（A ）oA. 数据对彖、数据关系和基本操作B.数崔元素、逻辑结构和存储结构C.数据项、数据元素和数据类型D.数据元索、数据结构和数据类型1U、卜列程序段的时间复杂度为（B）。 x=n;y=0;while (x>=(y+1)*(y+1) y=y+l;A. 0(n)B. O(/njc. 0(1)D. 0(n=)二、填空题1、程序段丄e(ivn) i=i*2; ”的时间复杂度为log： 。2、数据结构的四种基本类型中，树形结构的元素是一对多关系

4、。3、数据结构包括数据的逻辑结构、数据的存储结构和数据的运算这三个方面的内容。4、数据结构按逻紺结构叮分为四类，它们分别是集合、线性结构、树状结构和图状结构。5、线性结构中元素之间存在一对-关系，树形结构中元索Z间存在一对多关系，图形结构 中元素之间存在多对多关系。6、在线性结构中，第一个结点没有前驱结点,其余每个结点有且只有二个前驱结点：最后 一个结点没有后继结点,其余每个结点有且只有1个后继结点。7、在树形结构中，树根结点没右前驱结点，其余每个结点有且只有二个前驱结点：叶子结 点没有后续结点,其余每个结点的后续结点数可以任意多个。8、在图形结构中，每个结点的前驱结点数和后续结点数可以任意多

5、个。9、数据的存储结构町用四种基本的存储方法表示，它们分别是顺丿宇、链式、索引、散列。10、一个算法的效率可分为时间效率和空间效率。三、简答题1、简述线性结构与非线性结构的不同点。答：线性结构反映结点间的逻辑关系是一对一的，非线fl：结构反映结点仙的逻辑关系是多对 多的。第二章线性表一、选择题1、卞述哪一条是顺序存储结构的优点？( A )A存储密度犬B.插入运算方便C.删除运算方便D.可方便地用于各种逻辑结 构的存储表示2. 卜面关于线性表的叙述中，错误的是哪-个？( B )A. 线性表采用顺序存储，必须占用一片连续的存储单元。B. 线性表采用顺序存储.便于进行插入和删除操作tC. 线性表釆用

6、链接存储，不必占用一片连续的存储单元。D线性表采用链接存储，便于插入和删除操作。3、若长度为n的线性表采用顺序存储结构，在其第i个位蜀插入一个新元素算法的时间复杂度(C )o 衣若一个线性表屮绘常用的操作是取第i个元素和找第i个元素的前趋元素，则釆用（） 存储方式敲节省时间。（A ）oA Odogm】)B.O(l)C. 0(n)D.O(n2)A.顺序表B.单链表C.双链表D.单循环链表5、具有线性结构的数据结构是（D ）oA.图B.树C.广义表D.栈6、在一个长度为n的顺序表中，在第i个元素之前（元素从1开始计数）插入一个新元 素时，需向后移动（）个元素。（B ）A. n-iB. n-i+1C

7、. n-i-1D. i7、非空的循坏单链表head的尾结点p满足（AA p->next=headC. p=NULL8、链表不具有的特点是（A ）。 A町随机访问任一元素 C.不必事先估计存储空间B p->next=NULLD p=headB. 插入删除不需要移动元素D. 所需空间与线性表长度成正比9、线性表采用链式存储时，结点的存储地址（）cA.必须是连续的B. 必须是不连续的C.连续与否均叮D.和头结点的储地址相连续10. 在-个长度为n的顺序表中删除第i个元素，需要向前移动（A ）个元素。A. n-iB. n-i+1C. n-i-1D. i+111>从表中任一结点出发，都

8、能扫描整个表的是（C ）。A.单链表B.顺序表C.循环链表D.静态链表12. 在貝有n个结点的单链表上查找值为x的元素时，其时间复杂度为（A ）.A. O（n）B. 0（1）C. O（n:）D. O（n-l）13. 线性表L=（al,a2,，an）,下列说法正确的是（D ）。A. 每个元素都有一个直接前驱和一个直接后继B. 线性表中至少要有一个元素C. 表中诸元素的排列顺序必须是由小到大或由大到小D. 除第一个和故后一个元索外，其余每个元素都由一个且仅有一个直接前驱和直接后 继14. 在线性表的卜冽存储结构中，读取元素花费的时间最少的是（D ）。A.单链表B.双链表C.循环链表D.顺序表15.

9、 在一个单链表中，若删除p所指向结点的后续结点，则执行（A ）。A. p->next=p->next->next;B. p=p->next;p->next=p->next->next;C. p =p->next;D. p=p->next->next;16. 循环链表的主要优点是（D ）oA.不再需要头指针B.己知某结点位置后能容易找到其直接前驰C. 在进行插入、删除运算时能保证链表不断开D. 在表中任一结点出发都能扫描整个链表17. 在下列对顺序表进行的操作中，算法时间复杂度为0（1）的是（A ）«A.访问第i个元素的前驱（

10、Kin ） B.在第i个元素之后插入一个新元素 （1 <i <n）C. 删除第i个元素（lGSn）D.对顾序表中元素进行排序18、已知指针p和q分别指向某单链表中第一个结点和最后一个结点。假设指针s指向另一个 单链表中某个结点，则在s所指结点之后插入上述链表应执行的语句为（A ）0A. q->next=s->next： s->next=p：B. s->next=p； q->next=s->next；C p->next=s->next： s->next=q；D s->next=q： p->next=s->next

11、：19、在以下的叙述中，正确的是（C ）oA.线性表的顺序存储结构优于链表存储结构B .线性表的顺序存储结构适用丁频繁插入/删除数据元索的情况C. 线性表的链表存储结构适用于频繁插入/删除数据元素的情况D. 线性表的链表存储结构优于顺序存储结构20、在表长为n的顺序表中，当在任何位置删除一个元素的概率相同时，删除一个元素所需 移动的平均个数为（A ）oA. （n-l）/2B. n/2 C. （n+1） /2 D. n21、在单链表中，指针p指向元素为x的结点，实现删除x的后继的语句是（B ）。A. p=p->next;B. p->next=p->next->next;C

12、. p->next=p;D. p=p->next->next;二、填空题设单链表的结点结构为（data,next）o己知指针p指向单链表中的结点，q指向新结点, 欲将q插入到p结点之后，则需要执行的语句：: 。答案：q>next =p->nextp->next=q2、线性表的逻辑结构是,其所含元素的个数称为线性表的。答案：线性结构长度3、带头结点的单链表head为空的条件是o答案：head->next=NULL4、在一个单链表中删除p所指结点的后继结点时，应执行以卜操作：q = p->next;p->next=;答案:q->next三

13、、判断题丄、单链表不是一种随机存储结构。/2、在具有头结点的单链表中，头指针指向链表的第一个数据结点。x3、在线性表的顺序存储结构中，逻辑上相邻的两个元素但是在物理位昼上不一定是相邻的。x4、顺序存储结构的主要缺点是不利于插入或删除操作。（/）5、线性表采用链衷存储时，结点和结点内部的存储空间町以足不连续的。（/）6、顾序存储方式插入和删除时效率太低，因此它不如链式存储方式好。0）7、线性表的特点是每个元素都有一个前驰和一个后继。（x）8、取线性表的第I个尤素的时间同1的人小有关（戈）9、线性表只能用顺序存储结构实现。(*)10、顺序存储方式的优点是存储密度人，且插入、删除运算效率高。(X )

14、11、链表是采用链式存储结构的线性表，进行插入、删除操作时，在链表中比在顺序存储结 构中效率高。(/ )四、程序分析填空题1、函数实现单链表的插入算法，请在空格处将算法补充完整。int Listinsert (LinkList Lr int i,ElemType e)LNode *pr *s;int j;p=L;j=0;while(p!二NULL)&&(j<i-l) p=p->next;j+;if(p=NULL|j>i-l) return ERROR;s=(LNode *)malloc(sizeof(LNode);s->data=e;return OK;

15、/*ListInsert*/答案：(丄)s->next=p->next (2)p->next=s2、函数ListDelete_sq实现顺序表删除算法，请在空格处将算法补充完整。int ListDelete_sq(Sqlist L,int i)int k;if (i<l|i>L->length) return ERROR;for (k=i-l;k<L->length-1;k+)L->slistk-(1);<2>；return OK;答案：(1) L->slistk+1(2) ->Length3、惭数实现单链表的删除算法

16、，请在空格处将算法补充完整。int ListDelete (LinkList Lrint ir ElemType *s)LNode *pz *q;int j;p=L;j=0;v/hile ( (1) && (j) p=p->next;j+;if(p->next=NULL|j>i-l) return ERROR;q=p->next;As=q->data; free (q);(2) ;return OK;/*listDelete*/答案：(1) p->next !=NULL (2) p->next=q->next五、编程题1、有两个循

17、环链表，铳头指针分别为L1和L三，要求写出算法将L2链表链到L1链表之 后，且连接后仍保持循环链表形式。答案：void mei*ge(Lnode *L1, Lnode *L2)Lnode *p,*q;while(p->nexti=Ll)p=p->next,while(q->next l=L2)q=q->next,q->next=Ll; p->next =L2t2、设一个带头结点的单向链表的头指针为head,设计算法，将链农的记录，按照data域的 值递增排序。答案：void assenduig(Lnode *head)Lnode *p,*q , *i; *s

18、;pMiead->next, q=p->next, p->next=NULL,while(q)r=q, q=q->next,if(r->data<=p ->data)r->next=p, head->next=i p=r, elsewhile(ip && r->data>p->data)s=p, p=p->next, r->next=p, s->next=i; pMiead->next, 六、应用题1、线性表有两种存储结构：一是顺序表，二是链表。试问：(1) <111果有n个线

19、性表同时并存，并且在处理过程中各表的长度会动态变化，线性表 的总数也会自动地改变。在此情况下，应选用哪种存储结构？为什么？(2) 若：线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线 性表中的元素，那么应采用哪种存储结构？为什么？(1) 选链式存储结构。它可动态申请内存空间，不受表长度(即表中元素个数)的影响， 插入、删除时间复杂度为0 (1)。(2) 选噸序存储结构。顺序表町以随机存取，时间复杂度为0 (1)2、若较频繁地对一个线性表进行插入和删除操作，该线性表宜釆用何种存储结构？为什 么？采用链式存储结构，它根据实际需要申诸内存空间，而当不需要时又可将不用结点空间返还

20、给系统。在链式存储结构中插入和删除操作不需要移动元素第三章栈、队列和串一.选择题1、对于栈操作数据的原则是（B ）。A.先进先出B.后进先出C.后进后出D.不分顺序2、栈在（D ）中应用。A.递归调用B.子程序调用C.表达式求值D. A, B, C3、一个栈的输入序列为1 2 3 4 5,则卞列序列中不可能是校的输出序列的是（B ）oA. 2 3 4 1 5B. 5 4 13 2C. 2 3 14 524、一个递归算法必须包括（B ）。A.递归部分B.终止条件和递归部分C.迭代部分部分5、用链接方式存储的队列，在进行删除运算时（D ）。几仅修改头指针 B.仅修改尾指针C.头、尾指针都要修改D

21、1 5 4 3D.终止条件和迭代D.头、尾指针可能都要修改6、用不带头结点的单链表存储队列时，其队头指针指向队头结点，其队尾指针指向队尾结点, 则在进行删除操作时（D ）oA.仅修改队头指针B. 仅修改队尾指针C.队头、队尾指针都要修改D.队头，队尾指针都町能要修改7、递归过程或函数调用时，处理参数及返回地址，要用一种称为（CA.队列B.多维数组C.栈D.8、栈和队列都是（C ）A.顺序存储的线性结构C.限制存取点的线性结构9、一个栈的输入序列为：a.A. a, b, c, d, eC. d, c, e, a, bb.B.链式存储的非线性结构D.限制存取点的非线性结构c, d, e,则栈的不可

22、能输出的序列是（B d, e, c, b, aD e, d, c, b, a10>设计一个判别表达式中扌舌号是否配对的算法，A.顺序表B.链表11.带头结点的单链表head为空的判定条件是（A. head=NULL采用（D ） C.队列 B ）。B. head->next=NULL）的数据结构。线性表C ）o数据结构最佳。D.栈C. head->next!=NULLD head!=NULL12>带头结点的单链表head为空的判定条件是（B ）。A. head=NULLB. head->next=NULLC. head->next!=NULLD. head!=

23、NULL13.队列的插入操作是在（A ）«>A 队尾B队头C.队列任意位置D.队头元索后丄4、循环队列的队头和队尾指针分别为front和匸ear,则判断循坏队列为空的条件是A. front=rearB. front=0C. reaE=OD. front=rear+l15.栈的插入和删除操作在（B ）oA.栈底B.栈顶C.任意位置D.指定位置16.五节车厢以编号1, 2, 3, 4,5顺序进入铁路调度站（栈人可以得到（C）的编组。A. 3, 4, 5, 1, 2B. 2, 4, 1, 3, 5C. 3, 5, 4,D. 1, 3, 5, 2, 417. 依次在初始为空的队列中插入

24、元素a.b.c.d以后，紧接着做了两次删除操作，此时的 队头元素是（c ）。A. aB. bC. cD. d18. 正常情况卜，删除非空的顺序存储结构的堆栈的栈顶元素，栈顶指针top的变化是 （D ）。A. top不变B. top=0 C. top=top+lD. top=top-l19. 设有两个串SI和S2,求串S2在S1中首次出现位置的运算称作（C ）oA.连接 B.求子串C.模式匹配 D.判断子串20. 串与普通的线性表相比较，它的特殊性体现在（C ）。A.顺序的存储结构B.链式存储结构C. 数据元素是一个字符D.数据元素任意21、空串和空格串（B ）。A.相同B .不相同C . 口：

25、能相同D .无法确定22. 设SUBSTR（Sri,k）是求S中从第i个字符开始的连续k个字符组成的子串的操作, 则对于 S=' Beijing&Nanjing* SUBSTR （S, 4,5） = （ B ）。A. 'ij ing* B. ' j ing&'C. 'ingNa'D. 'ing&N二、填空题1、一个循环队列Q的存储空间大小为M,其队头和队尾指针分别为front和匸ea则循环队列中元素的个数为：°答案：（r e ar -fr ont +M） %I2、在具有n个元素的循环队列中，队满时具有个元

26、素。答案：n-13、设循环队列的容最为70,现经过一系列的入队和出队操作后，front为20, gar为11,则队列中元素的个数为o答案：614、求子串在主串中首次出现的位置的运算称为模式匹配。5、两个串相等的充分必要条件是两个串的长度相等且对应位置字符相同。三、判断题1、枝和队列都是受限的线性结构。（/）2、在单链表中，要访问某个结点，只要知道该结点的地址即可；因此，单链表是一种随机 存取结构。（*）3、以链表作为栈的存储结构，出栈操作必须判别栈空的情况。（/）4、消除递归不一定需要使用栈，此说法（/）5、栈与队列是一种持殊操作的线性表。（/）6、栈和队列都是限制存取点的线性结构。（/）7、

27、队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。(*)四、程序分析填空题丄、己知栈的基本操作函数：int InitStack (SqStack *S) ; /构造空枝int StackEmpty (SqStack *S) ; /判断栈空int Push (SqStack *Sr ElemType e);/入栈int Pop (SqStack *Sr ElemType 9);/出栈函数conversion实现十进制数转换为八进制数，请将两数补充完整。void conversion ()(InitStack (S);scant (壮d" 9 &N);wh

28、ile(N)(1) ;N=N/8；while (2) Pop(Sz &e);printf C%dre);/convei?sion答案：(1) Push(S,N%8)(2) IStackEnpty(S)2、阅读算法f2,并回答下列问题：(1) 设队列Q=(1，3, 5, 2, 4, 6)«写出执行算法后的队列Q;(2) 简述算法f2的功能。void f2 (Queue *Q) DataType e;if (IQueueEmpty(Q)e=DeQueue(Q);f2 (Q)；EnQueue(Q,e);答案：(1) 6,4,2,5,3,1(2)将队列倒It五、综合题1、假设以带头结

29、点的循环链表表示队列，并且只设一个指针指向队尾结点，但不设头指针， 请写出相应的入队列算法(用函数实现)。答 案：void EnQueue(Lnode *reai; ElemTyp e e) Lnode *new,New=QLnode *)malloc(sizeof(Lnode),If(!new) return ERROR,nev/>data=e, new->next=i-ear->next, rear->next=new, rear=new,已知Q是一个非空队列，S是一个空栈。编写算法，仅用队列和栈的ADT因数和少最工 作变量，将队列Q的所有元素逆置。栈的ADT函数有

30、：void makeEmpty (SqStack s);胃空栈void push (SqStack s r ElemType e); 元素 e 入栈ElemType pop (SqStack s); 出栈，返回栈顶元素int isEmpty (SqStack s);判断栈空队列的ADT函数有：void enQueue (Queue qf ElemType e);元素 e 入队ElemType deQueue (Queue q);出队，返回队头元素int isEmpty (Queue q); 判断队空答案：void QueueInvent(Queue q) ElemType x,makeEmpt

31、y(S qStack s),while(i isEnpty(Queue q)x=deQueue(Queue q), push(SqStack s, ElemTypex), while(! isEnpty(SqStack s)x=pop(SqStack s), enQueue(Queue q, ElemType x),3、函数实现串的模式匹配算法，请在空格处将算法补充完整。int index_bf(sqstring*s/sqstring *tz int start)int i=start-lr j=0;v/hile (i<s->len&&j<t->len)

32、if (s->datai=t->dataj)i+;j+;elsei=i_j+l; j = 0;if(j>=t->len)return i-t->len+l;elsereturn -1; /*listDelete*/4、写出下面算法的功能。int function (SqString *slz SqString *s2) int i;foe (i=0;i<sl->length&&i<sl->lengrh;i+)if (s->datai!=s2->datai)return sl->datai-s2->da

33、ta i;return s1->length-s2->length;答案：串比较算法5、写出算法的功能。int fun (sqstring *s z sqstring *tr int start) int i=start-lr j=0;v/hile (i<s->len&&j<t->len)if(s->datai=t->dataj)i+;j+;elsei=i-j+l;j=0;if (j>=t->len)匸eturn i-t->len+l;elsereturn -1;答案：串的模式匹配算法第五章多维数组和广义表一、选

34、择题1、将_个AE1.100, 1.100的三对角矩阵,按行优先存入一维数组Bl298中,A中 元素A6665 (即该元素下标i=66, j二65),在B数组中的位置K为(B )。A. 198B. 195C. 197D. 1982、二维数组A的元素都是6个字符组成的串，行卜标i的范用从0到8,列卜标j的范圈从1到io。从供选择的答案屮选出应填入卜列关于数组存储叙述中()内的正确答案。(1) 存放A至少需要(E )个字节：(2) A的第8列和第5行共占(A )个字节；(3) 若A按行存放，元素A8, 5的起始地址与A按列存放时的元素(B )的起始地址 一致。供选择的答案：(1) A. 90B18

35、0C.240D.270E. 540(2) A. 108B.114c.54D.60E. 150(3) A. A8, 5B.A3, 10c.A5, 8D.A0, 93、设A是n*n的对称矩阵，将A的对角线及对角线上方的元素以列为主的次序存放在一维 数组Bl. n(n+l)/2中，对上述任一元素aij (lWi, jWn,且iW j)在B中的位置为(B )。A. i(i-l)/2+j B. j(j-l)/2+iC. j(jT)/2+iT D. i(i-l)/2+j-l4、AN, N是对称矩阵,将下面三角(包扌舌对角线)以行序存储到一维数组TN (N+1) /2 中，则对任一上三角元素aij对应Tk的

36、下标k是(B ).A. i (i-1) /2+j K. j (j-1) /2+i C. i (ji) /2+1 D. j (i-1) /2+15、设二维数组Al. m, 1. n(即m行n列)按行存储在数组Bl. m*n中，则二维数 组元素Ai, j在一维数组B中的下标为(A )oA. (i_l) *n+j B. (i_l) *n+j_lC. i* (jT)D. j*m+i-l6、有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表 示该矩阵时，所需的字节数是(B )oA. 60B. 66C. 180C0D. 337、数组A0. 4, -1. -3, 5. 7中含

37、有元素的个数(B )。A. 55B. 45C. 36D. 168、广义表A二(a,b, (c,d), (e, (f,g),则下面式子的值为(D )。Head(Tail(Head(Tail(Tail (A)A. (g)B. (d)C. cD. d9、己知广义表:A=(a,b), B=(A,A), C=(a, (b,A),B),求下列运算的结果: ta订 Giead(ta订(C) =( F ) «A. (a)B. AC aD. (b)EbF. (A)10、广义表运算式Tail (a, b),(c,d)的操作结果是(C )oA. (c, d)B. c, dC. (c, d)Dd11、广义表

38、L二(a, (b, c),进行Tail (L)操作后的结果为(DA. cB. b» cC. (b, c)D. (b. c)12、广义表(a, b, c,d)的表头是(C ),表尾是(B )oA. aB. ( )C. (a, b, c, d) D. (b, c, d)13、设广义表L=(a, b, O),则L的长度和深度分别为(C )。A. 1和 1B.1 和3C. 1 和2D. 2和314、广义表(a) , a)的表尾是(B )。A. aB.(a)C. ()D. ( (a)15、稀疏矩阵的常见压缩存储方法有(C )两种。A.二维数组和三维数组B.三元组和散列表C.三元组和十字链表D.

39、散列表和十字链表一个非空广义表的表头(D )oA.不可能是子表 B.只能是子表 C.只能是原子D.可以是子表或原子17. 广义表 G=(a,B(c,d/ (e,f),g)的长度是(A )。A. 3B. 4C. 7D. 818. 釆用稀疏矩阵的三元组表形式进行压缩存储，若要完成对三元组表进行转置，只要将 行和列对换，这种说法(B )。A.正确 B.错误 C.无法确定D.以上均不对19. 广义表(a,b,c)的表尾是(B )A. b,cB. (b,c)C. cD. (c)20、对-些特殊矩阵采用压缩存储的目的主要是为了( D )。A.表达变得简单C.去掉矩阵中的多余元素21. 广义表A=(a) ,

40、a)的表头是(BA. aB. (a)B. 对矩阵元素的存取变得简单D. 减少不必要的存储空间的开销)oC. bD. (a)C.不能递归定义D.不能为空表22. 以下有关广义表的表述中，正确的足(A )oA.由0个或多个原子或子表构成的有限序列B.至少有一个元素是子表C.不能递归定义D.不能为空表二、判断题1、数组不适合作为任何二叉树的存储结构。(X )2、从逻辑结构上看，n维数组的每个元素均属于n个向量。(J )3、广义表中原子个数即为广义表的长度。(X )4、数组町看成线性结构的一种推广，因此与线性表-样，可以对它进行插入，删除等操作。 (X )5、一个稀疏矩阵九采用三元组形式表示，若把三元

41、组中有关行下标与列卜标的值互换， 并把m和n的值互换，则就完成了也的转置运算。(X )6、二维以上的数组其实是一种特殊的广义表。(V )7、广义表的取表尾运算，其结果通常是个表，但有时也可是个单元素值。(X )8、若一个广义表的表头为空表，则此广义表亦为空表。(X )9、广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表。(X )10、所谓取广义表的表尾就是返回广义表中最后一个元素。(X )11、对长度为无穷大的广义表，由于存储空间的限制，不能在计算机中实现。(V )12、广义表是一种多层次的数据结构，其元素可以是单原子也可以是子表。(丁) 三、填空题1、已知二维数组Amn采用行序

42、为主方式存储，每个元素占k个存储单元，并且第一个元素的存储地址是LOC(A00),则的地址是 Loc(A0 0)+(i*N+j)*k。2、广义表运算式HEAD(TAIL( (afb,c) , (x,y,z)的结果是：(x,y, z)。3、设广义表 L=(), 0),则 head(L)是()_： tail(L)是(2)()_)_: L 的长度是(3) 2_ _：深度是 (4)_2 一。4、已知广义表A二(9, 7,( 8, 10, (99), 12),试用求表头和表尾的操作Head()和Tail() 将原子元素99从A中取出来。head (head (tail (tail (head (tail

43、 (tail (A)5、广义表的深度是_表展开后所金括号的层数=°6、广义表(a, (a,b),d,e, (G, j),k)的长度是(1)5 ,深度是(2)37、已知广义表LS二(a, (b, c, d), e),运用head和tail函数取出LS屮原子b的运算是_head (head (tail (LS)_。8、广义表A=(a,b), (c,d, e),取出A中的原子e的操作是： _head(tail (tail (head(tail (head(A)_。四、综合题1、现有一个稀疏矩阵，请给出它的三元组表。0 310_10 0 00 2 100 0-20答案:1JV13131115

44、S3143-2第五章树形结构D. -+A*BC/DEA.C.D.一、选择题1. 已知一算术表达式的中缀形式为A+B*C-D/E,后缀形式为ABC*+DE/其前缀形式为 (D )A. -A+B*C/DEB. -A+B*CD/E C. -+*ABC/DE2、算术表达式a+b* （c+d/e）转为后缀表达式后为（BA. ab+cde/* B. abcde/+*+C. abcde/*+3、i殳有一表示算术表达式的二叉树（见下图），它所表示的算术表达式是（c ）A. A*B+C/（D*E） + （F） B（A*B+C） / （D*E） + （F）C（A*B+C）/（D*E+ （F-G） ） D A*B+

45、C/D*E+F-C 4、设树T的度为4,其中度为1, 2, 3和4的结点个数分别为4, 2, b 1则T中的叶子 数为（D ）D. 8A 5B 6C. 75、在下述结论中，正确的是（D ）只冇一个结点的二叉树的度为0;二叉树的度为2： 二叉树的左右子树可任意 交换；深度为K的完全二叉树的结点个数小于或等于深度柑同的满二叉树。6、设森林F对应的二叉树为B,它有m个结点，B的根为p,p的右子树结点个数为m森林F 中第一棵树的结点个数是（A ）A. mFB. hifTC. n+1D.条件不足，无法确定7、若一棵二叉树貝冇10个度为2的结点,5个度为1的结点，则度为0的结点个数是（B ）A. 9B.

46、11C. 15D.不确定8、在一棵三元树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2 个，则度为0的结点数为（C ）个A. 4B. 5C. 6 D. 79、设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为Ml, M2和M3。与森林F 对应的二叉树根结点的右子树上的结点个数是（D ）oA. MlB. M1+M2C. M3D. M2+M310、具有10个叶结点的二叉树中冇（B ）个度为2的结点，B. 9C. 10D. 1111、一棵完全二叉树上有1001个结点，其中叶子结点的个数是（E ）A. 250 B. 500 C. 254 D. 505 E.以上答案都不对12、设

47、给定权值总数有n个，其哈夫曼树的结点总数为（D ）A.不确定B. 2nC. 2n+lD 2nl13、有n个叶子的哈夫曼树的结点总数为（D ）。A.不确定B. 2nC. 2n+lD. 2nT14、若度为m的哈夫曼树中,其叶结点个数为m则非叶结点的个数为（C ）oA. n"lB. Ln/mJ"lE. （n+1）/ （m+l）T"l15、有关二叉树卜列说法正确的是（BA.二叉树的度为2C. 二叉树中至少冇一个结点的度为2C (nT) / (m-l)lD n/ (m-l)TlB. 棵二叉树的度可以小于2D. 二叉树中任何一个结点的度都为216、二叉树的第I层上最多含有结点

48、数为（C ）A. 2X17、一个具有1025个结点的二叉树的高h为（C ）A. 11B. 10C. 11 至 1025 之间D. 10至1024之间18、一棵二叉树高度为h,所有结点的度或为0.或为2则这棵二叉树最少有（B ）结点A. 2h B 2hTC. 2h+lD h+119、对于有n个结点的二叉树，其高度为（D ）A. nlogm B. logmC. Llog：nJ|lD.不确定20、一棵具有n个结点的完全二叉树的树高度（深度）是（A ）A. L logtfi J+lB logi +1C. L logji D. logdi -121、深度为h的满m叉树的第k层有（A ）个结点。（l=&l

49、t;k=<h）A. m1"1B m1"!C. m"1 D. mF 22、在一棵高度为k的满二叉树中结点总数为（C ）A. 2円B. 2kC. 2k-l23、高度为K的二叉树最衣的结点数为（A. 2"B. 2='C. 2124、一棵树高为K的完全二叉树至少有（A 21 - 1B. 2戸-1D. Llog2、J+l)oC-1D. 2W-1C ）个结点C. 2戸D. 2 25、将冇关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度（C）A. 4B. 5C. 6D. 726、对二叉树的结点从1开始进行连续编号，要求每个结点的编号人于

50、其左、右孩子的编号， 同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，町采用（C ）次序的遍历 实现编号。A.先序B.中序C.后序BD.从根开始按层次遍历27、树的后根遍历序列等同于该树对应的二叉树的（B ）.A.先序序列B.中序序列C.后序序列28、若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位叠，利用（C ） 遍历方法最合适。A.前序 B.中序 C.后序 D.按层次29、在下列存储形式中，哪一个不是树的存储形式？（ D ）A.双亲表示法B.孩子链表表示法C.孩子兄弟表示法D.顺序存储表示法30、一棵叉树的前序遍历序列为ABCDEG它的中序遍历序列可能足（B ）A.

51、 CABDEFGB ABCDEFGC. DACEFBGD. ADCFEG31、已知一棵叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果 为（A ）。A. CBEFDAB. FEDCBAC. CBEDFAD.不定32、己知某二叉树的后序遍历序列是dabec,中序遍历序列是debac ,它的前序遍历是 （D ）。A. acbedB. decab C. deabcD. cedba33、某二叉树中序序列为A, B, C, D, E, F, G,后序序列为B, D, C, A, F, G, E则前序序列是:（B ）A. E, G, F, A. C, D, B B. A. C

52、, B, D, G, F C. E, A, G, C, F, B, D D.上面的 都不对34、上题的二叉树对应的森林包括多少棵树（B ）A. 1B. 2C. 3D.概念上是错误的35、二叉树的先序遍历和中序遍历如卜：先序遍历：EFHIGJK：中序遍历:HFIEJKG。该二 叉树根的右子树的根是：（C ）A、EB、FC、GD、H36、将一棵树t转换为孩子一兄弟链表表示的二叉树h,则t的后根序遍历是h的（B ）A.前序遍历B.中序遍历 C.后序遍历 D.层次遍历37、某二叉树T有n个结点，设按某种顺序对T中的每个结点进行编号，编号为1,2,，n,且有如下性质：T中任一结点V,其编号等于左子树上的

53、最小编号减1,而V的右子树的 结点中，其最小编号等于V左子树上结点的最大编号加1。这时是按（B ）编号的。A中序遍历序列B.前序遍历序列C.后序遍历序列D.层次顾序38、下面的说法中正确的是（B ）.（1）任何一棵二叉树的叶子结点在三种遍历中的相对次序不变：（2）按二叉树定义，具有三个结点的二叉树共有6种。A. （1）（2） B. （1） C. （2） D.、都错39、对于前序遍历与中序遍历结果相同的二叉树为（l）o F对于前序遍历和后序遍历结果相同的二叉树为（2）o BA. 一般二叉树 B.只有根结点的二叉树C.根结点无左孩子的二叉树D. 根结点无右孩子的二叉树E.所有结点只有左子数的二叉树

54、F.所有结点只有右子 树的二叉树40、在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序（B ）A.都不相同 B.完全相同 C.先序和中序相同，而与后序不同D. 中序和后序相同，而与先序不同41、某二叉树的前序序列和后序序列正好相反，则该二叉树一定是（C）的二叉树。A.空或只有一个结点B.任一结点无左子树C.高度等于其结点数D.任一结点无右子树42、在完全二叉树中，若一个结点是叶结点，则它没（C ）«A.左子结点B.右子结点C.左子结点和右子结点D.左子结点，右子结点和兄弟结点43、用顺序存储的方法，将完全二叉树中所有结点按层逐个从左到右的顺序存放在一维数组 R1.N中，若结点Ri有右孩子，则其右孩子是（B ）。A. R2i-1 B. R2i+1C. R2iD. R2/i44、设a, b为一棵二叉树上的两个结点，在中序遍历时，a在b前而的条件足（B ）。A. a在b的右方B. a在b的左方C. a足b的祖先 D. a是b的子孙45、在一棵具有5层的满二叉树中结点总数为（A）。A. 31B. 32 C. 33D. 164