数据结构考研分类复习真题 第二章 线性表[39]

已知长度为n的线性表A采用顺序存储结构请写一时间复杂度为(n)空间复杂度为()的算法该算法删除线性表中所有值为item的数据元素（O（）表示算法的辅助空间为常量）

【北京航空航天大学 五（分）】

．设民航公司有一个自动预订飞机票的系统该系统中有一张用双重链表示的乘客表表中结点按乘客姓氏的字母序相链例如下面是张某个时刻的乘客表试为该系统写出一个当任一乘客要订票时修改乘客表的算法

序号 data Llink Rlink

Liu  

Chan

Wang  

Bao  

Mai

Dong  

Xi

Deng  

Cuang

【北方交通大学 六（分）】

．设有一头指针为L的带有表头结点的非循环双向链表其每个结点中除有pred（前驱指针）data（数据）和next（后继指针）域外还有一个访问频度域freq在链表被起用前其值均初始化为零每当在链表中进行一次Locate(Lx)运算时令元素值为x的结点中freq域的值增并使此链表中结点保持按访问频度非增（递减）的顺序排列同时最近访问的结点排在频度相同的结点的最后以便使频繁访问的结点总是靠近表头试编写符合上述要求的Locate(Lx)运算的算法该运算为函数过程返回找到结点的地址类型为指针型【清华大学 二 （分）】

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []