|
一基础知识题 试描述头指针头结点开始结点的区别并说明头指针和头结点的作用 何时选用顺序表何时选用链表作为线性表的存储结构为宜? 在顺序表中插入和删除一个结点需平均移动多少个结点?具体的移动次数取决于哪两个因素? 为什么在单循环链表中设置尾指针比设置头指针更好? 在单链表双链表和单循环链表中若仅知道指针p指向某结点不知道头指针能否将结点*p从相应的链表中删去?若可以其时间复杂度各为多少? 下述算法的功能是什么? LinkList Demo(LinkList 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; }// Demo 二算法设计题 设线性表的n个结点定义为(aaan)重写顺序表上实现的插入和删除算法InsertList 和DeleteList 试分别用顺序表和单链表作为存储结构实现将线性表(aaan)就地逆置的操作所谓就地指辅助空间应为O() 设顺序表L是一个递增有序表试写一算法将x插入L中并使L仍是一个有序表 设顺序表L是一个递减有序表试写一算法将x插入其后仍保持L的有序性 写一算法在单链表上实现线性表的ListLength(L)运算 已知L和L分别指向两个单链表的头结点且已知其长度分别为m和n试写一算法将这两个链表连接在一起请分析你的算法的时间复杂度 设 A和B是两个单链表其表中元素递增有序试写一算法将A和B归并成一个按元素值递减有序的单链表C并要求辅助空间为O()请分析算法的时间复杂度 已知单链表L是一个递增有序表试写一高效算法删除表中值大于min 且小于max的结点(若表中有这样的结点)同时释放被删结点的空间这里min 和 max是两个给定的参数请分析你的算法的时间复杂度 写一算法将单链表中值重复的结点删除使所得的结果表中各结点值均不相同 假设在长度大于的单循环链表中既无头结点也无头指针s为指向链表中某个结点的指针试编写算法删除结点*s的直接前趋结点 已知由单链表表示的线性表中含有三类字符的数据元素(如字母字符数字字符和其它字符)试编写算法构造三个以循环链表表示的线性表使每个表中只含同一类的字符且利用原表中的结点空间作为这三个表的结点空间头结点可另辟空间 设有一个双链表每个结点中除有priordata和next三个域外还有一个访问频度域freq在链表被起用之前其值均初始化为零每当在链表进行一次LocateNode(Lx)运算时令元素值为x的结点中freq域的值加并调整表中结点的次序使其按访问频度的递减序排列以便使频繁访问的结点总是靠近表头试写一符合上述要求的LocateNode运算的算法 |
