I、free(Q);
已知结点编号，在各结点查找概率相等的情况下，从n 个结点的单链表中查找一个结点，平均要访问（ N/2 ）个结点，从n 个结点的双链表中查找一个结点，平均要访问（ N/4 ）个结点。【＊＊，?】
对于一个具有n 个结点的单链表，在已知p 所指结点后插入一个新结点的时间复杂度是（ O(1) ）；在值域为给定值的结点后插入一个新结点的时间复杂度是（ O(n) ）。【＊，★】
单链表是（线性表）的链接存储表示。【＊】
单链表中设置头结点的作用是（插入和删除元素时不必进行特殊处理）。【＊＊】 在单链表中，除首元结点外，任一结点的存储位置由（其前驱结点的链域）指示。【＊】 在非空双向循环链表中，在结点q 的前面插入结点p 的过程如下：【＊】 p->prior=q->prior; q->prior->next=p; p->next=q;
(q->prior=p; );
在双向链表中，每个结点有两个指针域，一个指向（前驱结点），另一个指向（后继结点）。【＊】
顺序表中逻辑上相邻的元素的物理位置（必定）相邻。单链表中逻辑上相邻的元素的物理位置（不一定）相邻。【＊】
为了便于讨论，有时将含n(n≥0)个结点的线性结构表示成(a1，a2,?,an)，其中每个ai 代表一个___结点___。a1 称为_第一个____结点，an 称为__最后____结点，i 称为ai 在线性表中的_____位置___。对任意一对相邻结点ai、ai┼1(1≤i 线性结构的基本特征是：若至少含有一个结点，则除起始结点没有直接__前驱____外，其他结点有且仅有一个直接___前驱___；除终端结点没有直接___后继___外，其它结点有且仅有一个直接__后继____.【＊】 所有结点按1对1的邻接关系构成的整体就是___线性___结构。【＊】 线性表的逻辑结构是__线性____结构。其所含结点的个数称为线性表的____长度______。【＊】 在单链表中，指针p 所指结点为最后一个结点的条件是_____p->next=NULL;______。【＊】 判断题 1. 顺序存储的线性表可以随机存取。【＊】对 2. 顺序存储的线性表的插入和删除操作不需要付出很大的代价，因为平均每次操作只有近一半的元素需要移动。【＊】错 3. 线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。【＊】对 4. 在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上不一定相邻。【＊】错 5. 在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。【＊】对 6. 在单链表中，可以从头结点进行查找任何一个元素。【＊】对 7. 线性表的链式存储结构优于顺序存储结构。【＊】错 8. 在线性表的顺序存储结构中，插入和删除元素时，移动元素的个数与该元素的位置有关。【＊】对 9. 在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。【＊】错 10. 顺序存储方式只能用于存储线性结构。【＊＊, ★】错 简答题 若较频繁地对一个线性表进行插入和删除操作，该线性表宜采用哪种存储结构？为什么？【＊】采用链式存储结构，因为其复杂度为O（1）； 描述概念：头指针、头结点、首元结点的区别？【＊＊，★】 设 A 是一个线性表（a1a2?an），采用顺序存储结构，则在等概率的前提下，平均每插入一个元素需要移动的元素个数为多少？若元素插在ai 与ai+1 之间（0<=I<=n-1）的概率为2(n-i)/(n(n+1))，则平均每插入一个元素所要移动的元素个数又是多少？【＊＊，★】 为什么在单循环链表中设置尾指针比设置头指针更好？【＊＊＊，★】 双链表和单循环链表中，若仅知道指针p 指向某个结点，不知道头指针，能否将结点*p 从相应的链表中删除？若可以，其时间复杂度各为多少？【＊＊】 下列算法的功能是什么？【＊＊，★】 LinkedList test1(LinkedList L) { //L 是无头结点的单链表 ListNode *q,*p; if(L&&L->next) { q=L ; L=L->next; p=L; while(p->next) p=p->next; p->next=q; q->next=NULL; } return L; } 如果有n 个线性表同时共存，并且在处理过程中各表的长度会发生动态变化，线性表的总长度也会自动地改变。在此情况下，应选择哪一种存储结构。为什么？【＊＊】 若线性表的总数基本稳定，且很少进行插入删除操作，但要求以最快的方式存取线性表的元素，应该用哪种存储结构。为什么？【＊】 设有多项式a(x)=9+8x+9x4+5x10 b(x)=-2x+22x7-5x10 （1）用单链表给出a(x)、b(x)的存储表示； （2）设c (x)=a(x)+b(x)，求得c(x)并用单链表给出其存储表示。【＊，★】 设计题 编写一个函数将一个顺序表A（有多个元素且任何元素不为0）分拆成两个顺序表，使A 中大于0的元素存放在B 中，小于0 的元素存放在C 中。【＊＊】 设顺序表L 中的数据元素递增有序。试写一算法，将e插入到顺序表的适当位置，插入后保持该表的有序性。【＊＊】 A、B 为元素递增有序排列的单链表（同一表中可能有相同元素），编写算法另建一单链表C，保存两个表的公共元素，要求C 的元素值各不相同且递增有序。【＊＊】 4、设有一个由正整数组成的无序单链表，编写算法实现下列功能：【＊＊】 （1）找出最小值结点，且显示该数值。 （2）若该数值为奇数，则将其与直接后继结点的数值交换。 （3）若为偶数，则将其直接后继结点删除。 编程附加题 试分别用顺序表和单链表作为存储结构，实现将线性表（a0,a1,a2,?.an-1）就地逆置的操作，所谓“就地”指辅助空间为O(1)。【＊＊＊，★】 设单链表 L 是一个非递减有序表，试写一个算法将x 插入其中后仍保持L 的有序性。【＊＊】 设 A、B 是两个线性表，其表中元素递增有序，长度分别为m 和n。试写一算法分别以顺序存储和链式存储将A 和B 归并成一个仍按元素值递增有序的线性表C，请分析算法的时间复杂度。【＊＊＊，★】 单链表 L 是一个递减有序表，试写一高效算法，删除表中值大于mink 且小于maxk 的结点（若表中有这样的结点），同时释放被删结点空间，这里mink 和maxk 是两个给定的参数, 它们可以和表中元素相同，也可以不同。【＊＊】 假设以两个元素依值递增有序排列的线性表A,B 分别表示两个集合，先要求另辟空间构造一个线性表C,其元素为两集合的交集，且表C 中的元素也依值递增有序排列。是对顺序表编写求C 的算法。【＊＊】 假设在长度大于 1 的单循环链表中，既无头结点也无头指针。S 为指向链表中某个结点的指针，试编写算法删除结点*s 的直接前驱结点。【＊＊】 计算带头结点的单循环链表的结点个数。【＊】
相关推荐：
loading