第2章 线性表08-12年1月试题及参考答案
（2008年1月）
2、在下列对顺序表进行的操作中，算法时间复杂度为O(1)的是（  　）
A、访问第i个元素的前驱（1<）
B、在第i个元素之后插入一个新元素()
C、删除第i个元素()
D、对顺序表中元素进行排序
3、假设带头结点的单向循环链表的头指针为head,则该链表为空的判定条件是（  　）
A、head= =NULL                B、head–>next= =NULL
C、head!=NULL                D、head–>next= =head
17、输入线性表的n个元素建立带头结点的单链表，其时间复杂度为___________。
30、假设以带头结点的单链表表示线性表,阅读下列算法f30,并回答问题:
(1)设线性表为( a1, a2, a3, a4, a5, a6, a7 ), 写出执行算法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;i<L->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->next==NULL；
C、head!=NULL；                D、head->next==head；
17、在双向循环链表中插入一个新的结点时，应修改_________个指针域的值。
30、假设以带头结点的单链表表示线性表，单链表的类型定义如下：
typedef  int  DataType;
typedef struct node {
    DataType data;
    struct node * next;
} LinkNode, * LinkList;
阅读下列算法，并回答问题：
(1)已知初始链表如图所示，画出执行f30(head)之后的链表；
题30图
(2)简述算法f30的功能。
void f30( LinkList head)
{ LinkList  p,r, s;
  if (head - > next)
{
r = head - > next;
p = r->next;
r - > next = NULL;
while (p)
{
s =p;
p = p->next;
if ( s - > data% 2 = = 0)
{
s - > next = head - > next;
head - > next = s;
}
else
{
s - > next = r - > next;
r->next = s;
r =s;
}
}
}
}
(1)
(2)
34、假设以带头结点的单链表表示线性表，单链表的类型定义如下：
typedef int DataType;
typedef struct node {
  DataType data;
  struct node * next;
} LinkNode, * LinkList;
编写算法，删除线性表中最大元素(假设最大值唯一存在)。函数原型为：
void  f34(LinkList head) ;
（2009年10月）
3、指针p、q和r依次指向某循环链表中三个相邻的结点，交换结点*q和结点*r在表中次序的程序段是（  　）
A、p->next=r；  q->next=r->next；  r->next=q；
B、p->next=r；  r->next=q；  q->next=r->next；
C、r->next=q；  q->next=r->next；  p->next=r；
D、r->next=q；  p->next=r；  q->next=r->next；
17、如果需要对线性表频繁进行________或________操作，则不宜采用顺序存储结构。
31、假设学生成绩按学号增序存储在带头结点的单链表中，类型定义如下：
typedef  struct  Node  {
int  id;            /*学号*/
int  score；      /*成绩*/
struct  Node  *next；
}  LNode，  *LinkList；
阅读算法f31，并回答问题：
(1)设结点结构为，成绩链表A和B如图所示，画出执行算法

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。