发布时间 : 星期三 文章数据结构更新完毕开始阅读
for(count=1;count
改后：
for(count=1;i+count-1<=a.length-k;count++) a.elem[i+count-1]=a.elem[i+count+k-1]; a.length-=k;
7、设计一个时间复杂度为O（n）的算法，实现将数组A[n]种所有元素循环左移k个位置。
8、一个长度为L（L≥1）的升序序列S，处在第?L/2?个位置的数称为S 的中位数。例如，若序列S1 = (11, 13, 15, 17, 19)，则S1 的中位数为15。两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若S2 = (2, 4, 6, 8, 10)，则S1 和S2 的中位数为10。现有两个等长的升序序列A 和B，试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列A 和B 的中位数。 算法的基本设计思想：分别求两个升序序列A 和B 的中位数，设为a 和b。 1）若a = b，则a 或b 即为所求的中位数。 2）否则（假设a 9、已知数组A[n]中的元素为整型，设计算法将其调整为左右两部分，左边所有元素为奇数，右边所有元素为偶数，并要求算法的时间复杂度为 O（n） 10、设计一个高效算法，在顺序表中删除所有元素值为x的元素，要求时间复杂度为O（n），空间复杂度为O（1）。 5 11、设计算法实现从顺序表中删除所有值在x和y之间的所有元素，要求时间性能为O（n），空间性能为O（1）。 12、设计算法删除顺序表中重复的元素，要求算法移动元素的次数较少，并使剩余元素间的相对次序保持不变。 13、顺序表LA和LB中值非递减有序，设LA的空间足够大，试写一高效算法，将LB合并到LA中，使新生成LA依然有序。高效指的是最大限度的避免移动。 14、设A是线性表（a1，a2，?，an），采用顺序存储，则在等概率下，平均每插入一个元素需要移动的元素个数为多少？若元素插在ai和ai+1（1 ≤ i ≤ n）之间的概率为n-i/n(n-1)/2，则平均每插入一个元素要移动的元素个数是多少？ 典型题目解析 链表 1、线性表的链式存储结构是一种（ ）的存储结构 A、随机存取B、顺序存取C、索引存取D、散列存取 2、将长度为n的单链表连在长度为m的单链表之后，时间复杂度是（ ） 3、在一个长度为n（n>1）的带头结点的单链表h上，另设有尾指针r指向尾结点，执行（ ）操作与链表的长度有关。 A删除单链表第一个元素 B删除单链表的最后一个元素 C在单链表第一个元素前插入一个新的元素 D在单链表的最后一个元素后插入一个新元素 4、设一个单链表最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省时间 A、单链表 B、仅有头指针的单循环链表 C、双链表 D、仅有尾指针的单循环链表 5、单链表中增加一个头结点的目的是（ ） 6 A、使表中至少有一个结点 B、标识表中首结点的位置 C、方便运算的实现 D、说明单链表是线性表的链式存储 6、对于一个线性表既要求能够快速的插入和删除，又要求存储结构能反映数据之间的逻辑关系，则应该用（ ） A、顺序存储 B、链式存储 C、散列存储 D、以上均可 7、若要在O（1）的时间内实现2个循环单链表的首尾相连，则两个循环单链表应各设一个指针，分别指向（ ） A、各自的头结点 B、各自的尾结点 C、各自的第一个元素节点 D、一个表的头结点，一个表的尾结点 8、在双链表中，指针pa所指结点后面插入pb结点，执行的语句序列是（ ） ①pb->next=pa->next; ②pb->prior=pa; ③pa->next=pb; ④pa->next->prior=pb; A、1234 B、4321 C、3412 D、1432 9、已知非空线性链表由list指示，结点结构为data，link。编写算法，将链表中数据域最小的结点移到链表最前面。要求：不得额外申请新结点。 10、给定一个带头结点的单链表，设head为头指针，设计算法按递增次序输出单链表中各结点的数据元素，并释放结点所占的存储空间。要求：不允许使用额外的存储空间。 11、单链表的就地逆置。 12、两个单链表的操作。 13、已知L为单链表的头结点地址，表中共有m（m>3）个结点，从表中第i（1 L a1 a2 a3 … an 14、设计算法，将双向链表中结点p与其后继结点交换位置。 7 15、单链表的头指针为head，设计算法将链表中记录按照数据域递增的次序进行就地排序。 16、设有两个单链表，一个升序，一个降序。设编写算法，将这两个链表合并为一个有序链表。 17、将下图中23和15的两个结点互换位置 p 23 15 18、两个整数序列a1,a2,?,am和b1,b2,?bn已经存入两个链表中，设计一个算法，判断序列B是否是A的子序列。 19、L1与L2分别为两单链表头结点指针。且两表中结点的数据域均为1个字母。设计把L1中与L2中数据相同的连续结点顺序完全倒置的算法。 20、用顺序表表示集合，设计算法实现集合的求差集运算，要求不另外开辟空间。 21、已知两个不带头结点的单链表A和B分别表示两个集合，并且其元素值递增有序。求两个集合的交集C，并以同样的递增形式存储，要求尽可能节省时间。 22、从键盘输入n个英文单词，输入格式为n,单词1，?，单词n，其中n表示 8