线性表08-12年1月试题及参考答案电子教案.pdf

精品文档 第 2 章 线性表 08-12 年 1 月试题及参考答案 （2008 年 1 月） 2、在下列对顺序表进行的操作中，算法时间复杂度为 O(1) 的是（ ） A 、访问第 i 个元素的前驱（ 1i n ） B、在第 i 个元素之后插入一个新元素 ( 1 i n ) C、删除第 i 个元素 (1 i n ) D、对顺序表中元素进行排序 3、假设带头结点的单向循环链表的头指针为 head,则该链表为空的判定条件是 （ ） A 、head= =NULL B、head–next= =NULL C、head!=NULL D、head–next= =head 17 、 输 入 线 性 表 的 n 个 元 素 建 立 带 头 结 点 的 单 链 表 ， 其 时 间 复 杂 度 为 ___________。 30、假设以带头结点的单链表表示线性表 ,阅读下列算法 f30,并回答问题 : 1 2 3 4 5 6 7 (1) 设线性表为 ( a , a , a , a , a , a , a ), 写出执行算法 f30 后的线性表； (2) 简述算法 f30 的功能。 void f30(LinkList L) { //L 为带头结点单链表的头指针 LinkList p,q; p=L; while (p p –next){ q = p –next; p –next =q –next; p =q –next; free(q); } } (1) (2) 34、假设以单链表表示线性表 ,单链表的类型定义如下 : typedef struct node { DataType data; struct node *next; } LinkNode, *LinkList; 编写算法 ,将一个头指针为 head且不带头结点的单链表改造为一个含头结点且 头指针仍为 head 的单向循环链表 ,并分析算法的时间复杂度。 精品文档 精品文档 （2008 年 10 月） 3、在头指针为 head 的非空单循环链表中，指针 p 指向尾结点，下列关系成立的 是（ ） A 、 p-next==head B、 p-next-next==head C、 p-next==NULL D、 p==head 17、将两个长度分别为 m 和 n 的递增有序单链表，归并成一个按元素递减有序 的单链表，可能达到的最好的时间复杂度是 。 30、已知线性表的存储结构为顺序表，阅读下列算法，并回答问题： （1）设线性表 L= （21，-7，-8，19，0，-11，34，30，-10 ），写出执行 f30(L) 后的 L 状态； （2）简述算法 f30 的功能。 void f30 (SeqList *L) { int i,j; for (i=j=0;iL-length; i++) if(L-data[i]=0){ if(i!=j)L-data[j]=L-data[i]; j++ ； } L-length=j; } (1) (2) （2009 年 1 月） 2、假设某个带头结点的单链表的头指针为 head，则判定该表为空表的条件是 ( ) A 、head==NULL ； B、head-n