资源描述：
《精华复习题解答(记得老田上课说没题库这回事)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第一部分复习题8、判断下列叙述的对错。(2)线性表的顺序存储表示优于链式存储表示。(3)线性表若采用链式存储表示时所有结点之间存储单元的地址可连续可不连续。(4)二维数组是其数组元素为线性表的线性表。(5)每种数据结构都应具备三种基本运算：插入、删除和搜索。解答：(2)错(3)对(4)错(5)对10、线性结构可用顺序表或链表存储。试问：(2)若表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，这时，应采用哪种存储表示？为什么？解答：(2)顺序表12、填空题一维数组的逻辑结构是(①)，存储结构是(②)。对于二维数组，有(③)和(④)两种不同
2、的存储方式。对于一个二维数组A[m][n]，若采取按行存储的方式，则任一数组元素A[i][j]相对于A[0][0]的地址为(⑤)。解答：①线性结构②顺序结构③按行存放④按列存放⑤i*n+j16、设单链表中结点的结构为（data,link）。已知指针q所指结点是指针p所指结点的直接前驱，若在*q与*p之间插入结点*s，则应执行下列哪一个操作？(1)s->link=p->link;p->link=s;(2)q->link=s;s->link=p;(3)p->link=s->link;s->link=p;(4)p->link=s;s->link=q;解答：(2)17、
3、设单链表中结点的结构为（data,link）。已知指针p所指结点不是尾结点，若在*p之后插入结点*s，则应执行下列哪一个操作？(1)s->link=p;p->link=s;(2)s->link=p->link;p->link=s;(3)s->link=p->link;p=s;(4)p->link=s;s->link=p;12解答：(2)19、在单链表、双向链表和单循环链表中，若仅知道指针p指向某一结点，不知道表头指针，能否将结点*p从链表中删去？若可以，其时间复杂度各为多少？解答：在双向链表和单循环链表中可以删除。双向链表中删除*p的时间复杂度为O(1)；单循环
4、链表中删除*p的时间复杂度为O(n)，其中n是链表中结点个数。20、设单循环链表中结点的结构为（data,link），且rear是指向非空的带表头结点的单循环链表的尾结点的指针。若想删除链表第一个结点，则应执行下列哪一个操作？(1)s=rear;rear=rear->link;free(s);(2)rear=rear->link;free(rear);(3)rear=rear->link->link;free(rear);(4)s=rear->link->link;rear->link->link=s->link;free(s);解答：(4)23、试回答下列问题
5、：(1)设整数1,2,3,4,5,6依次进栈，则可能的出栈序列有多少种?(2)若整数1,2,3,4,5,6依次进栈，那么是否能够得到435612,325641,154623和135426的出栈序列。解答：(1)(2)435612,154623不能得到24、设有一个顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素的出栈顺序为s2,s3,s4,s6,s5,s1，则顺序栈的容量至少应为多少？解答：s1,s2,出s2;s1,s3,出s3;s1,s4,出s4;s1,s5,s6,出s6;s1,s5,出s5;s1,出s1；顺序栈的容量至少为3.27、设循
6、环队列的结构是constintMaxSize=100;typedefintDataType;typedefstruct{DataTypedata[MaxSize];intfront,rear;}Queue;12若有一个Queue类型的队列Q，试问判断队列满的条件应是下列哪一个语句？(1)Q.front==Q.rear;(2)Q.front-Q.rear==MaxSize;(3)Q.front+Q.rear==MaxSize;(4)Q.front==(Q.rear+1)%MaxSize;解答：(4)28、设循环队列的结构是constintMaxSize=100;t
7、ypedefintDataType;typedefstruct{DataTypedata[MaxSize];intfront,rear;}Queue;若有一个Queue类型的队列Q，试问应用下列哪一个语句计算队列元素个数？(1)(Q.rear-Q.front+MaxSize)%MaxSize;(2)Q.rear-Q.front+1;(3)Q.rear-Q.front-1;(4)Q.rear-Qfront;解答：(1)31、一棵具有n个结点的理想平衡二叉树（即除离根最远的最底层外其他各层都是满的，最底层有若干结点）有多少层？若设根结点在第0层，则树的高度如何用n来
8、表示（注意n可能为0）？
