1绪论单选题.ppt

线性表 问答题 (6)从循环单链表中查找出最小值。 elemtype min(HL){ //从循环单链表HL中查找出最小值 if (HL= =nil ) { printf(HL＝nil); return; } min＝HL-data; p＝HL-next; while (p!=HL) { (1) if (p-datamin) min＝p-data; (2) p＝p-next; } } 线性表 问答题 (7)根据一维数组A(1:n)中顺序存储的具有n个元素的线性表建立一个带有附加表头结点的单链表。 status create(HL,A,n) { (1) malloc(HL); q＝HL; // 产生附加表头结点 (2) for (i＝1 ;I=n ;++i) { // 完成n个元素的依次链接 malloc(p); p-data＝A(i); q-next＝p; q＝p; } (3) q-next＝nil ; // 把最后一个结点的指针域置空 } 线性表 问答题 6、对链表设置头结点的作用是什么?(至少说出两条好处) (1) 对带头结点的链表，在表的任何结点之前插入结点或删除表中任何结点，所要做的都是修改前一结点的指针域，因为任何元素结点都有前驱结点。若链表没有头结点，则首元素结点没有前驱结点，在其前插入结点或删除该结点时操作会复杂些。 (2) 对带头结点的链表，表头指针是指向头结点的非空指针，因此空表与非空表的处理是一样的。 线性表 问答题 7、在单链表、双链表和单循环表中，若仅知道指针p指向某结点，不知道头指针，能否将结点*p从相应的链表中删去？若可以，其时间复杂度各为多少？ 1. 单链表。当我们知道指针p指向某结点时，能够根据该指针找到其直接后继，但是由于不知道其头指针，所以无法访问到p指针指向的结点的直接前趋。因此无法删去该结点。 2. 双链表。由于这样的链表提供双向链接，因此根据已知结点可以查找到其直接前趋和直接后继，从而可以删除该结点。其时间复杂度为O(1)。 3. 单循环链表。根据已知结点位置，我们可以直接得到其后相邻的结点位置(直接后继)，又因为是循环链表，所以我们可以通过查找，得到p结点的直接前趋。因此可以删去p所指结点。其时间复杂度应为O(n)。 线性表 问答题 8、简述顺序表和链表存储方式的特点。 答：顺序表可以直接存取数据元素，方便灵活、效率高，但插入、删除操作时将会引起元素的大量移动，因而降低效率；而链表内存采用动态分配，利用率高，但需增设指示结点之间关系的指针域，存取数据元素不如顺序表方便，但结点的插入、删除操作较简单。　 线性表 问答题 9、有两个递增有序表，设计一个算法将它们归并成一个有序表(假设每个表中没有重复关键字的元素，归并时重复关键字的元素只归并一次)。 答：void Merge (LinkList La, LinkList Lb) { pa=La-next; pb=Lb-next; p=La; while(pa pb) { if (pa-data=pb-data) {p-next=pa; p=pa; pa=pa-next;} else {p-next=pb; p=pb; pb=pb-next;} } if(pa) p-next=pa; else p-next=pb; free(Lb); } 栈和队列 单选题 1、在一个具有n个单元的顺序栈中，假定以地址低端作为栈底，以top作为栈顶指针， 则当做退栈处理时，top变化为_____。 2、向顺序栈中压入元素时，是_____。 3、在一个顺序存储的循环队列中，队首指针指向队首元素的_____。 4、若进栈序列为1,2,3,4,进栈过程中可以出栈，则_____不可能是一个出栈序列。 * 线性表 算法分析题 13、设计一个算法,将线性表lb连接到la之后,要求其时间复杂度为O(1),占用的