数据结构复习试题——线性表

一、        选择题（共20题，每题1.5分，共计30分）

1.下列哪一条是顺序存储结构的优点                                     【       】

A. 插入运算方便      B. 可方便地用于各种逻辑结构的存储表示

C. 存储密度大        D. 删除运算方便

2. 下面关于线性表的叙述中，错误的是哪一个                             【       】

A. 线性表采用顺序存储，必须占用一片连续的存储单元。

B. 线性表采用顺序存储，便于进行插入和删除操作。

C. 线性表采用链接存储， 不必占用一片连续的存储单元

D. 线性表采用链接存储，便于进行插入和删除操作。

3. 线性表是具有n个【       】的有序序列（n>0）

A. 表元素           B. 字符          C. 数据元素        D.数据项

4. 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用【       】存储方式最节约时间。

A. 顺序表       B. 双链表      C. 带头结点的双循环链表      D.单循环链表

5. 若某线性表最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用【       】存储方式最节省运算时间。

A. 单链表                 B. 仅有头指针的单循环链表  

C. 双链表                 D. 仅有尾指针的单循环链表

6. 若某线性表最常用的操作是在末尾插入结点和删除尾结点，则选用【       】最节省运算时间。

A. 带头结点的双循环链表          B. 单循环链表  

C. 带尾指针的单循环链表          D. 单链表

7. 若某线性表最常用的操作是存取第I个元素及其前驱和后继元素的值，则采用【       】存储方式最节省运算时间。

A. 单链表        B. 双向链表       C. 单循环链表      D. 顺序表

8. 对于一个头指针为head的带头结点的单链表，判定该表为空的条件是【       】

A. head==NULL                   B. head->next==NULL 

C. head->next==head            D. head!=NULL

9. 链表不具有的特点是                                            【       】

A. 插入、删除不需要移动元素          B. 可随机访问任一元素  

C. 不必事先估计存储空间              D. 所需空间与线性长度成正比

10. 单链表中，增加一个头结点的目的是为了                         【       】

A. 使单链表至少有一个结点         B. 标示表结点中首结点的位置  

C. 方便运算的实现                 D. 说明单链表是线性表的链式存储

11.  在一个以h为头的单循环链中，p指针指向链尾的条件是             【       】

A. p->next==h          B. p->next==NULL

 C. p->next->next==h   D. p->data==-1

12. 对于一个线性表既要求能够进行快速的插入和删除，又要求存储结构能反映数据之间的逻辑关系，则应该使用                                              【       】

A. 顺序存储方式      B.链式存储方式     C. 散列存储方式      D.以上均可以

13. 一个算法应该具有“确定性”等5个特性，下面对另外4个特性的描述中错误的是【   】

A. 有零个或多个输入    B. 有零个或多个输出       C. 有穷性      D. 可行性

14、一个线性表第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的地址是【   】

（A）110    （B）108     （C）100     （D）120

15、向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动【   】个元素。

（A）64     （B）63      （C）63.5　　（D）7

16、线性表采用链式存储结构时，其地址【   】。

(A) 必须是连续的          (B) 部分地址必须是连续的

(C) 一定是不连续的        (D) 连续与否均可以

17、. 在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行【   】

（A）s->next=p;p->next=s;    （B） s->next=p->next;p->next=s;

（C）s->next=p->next;p=s;    （D）p->next=s;s->next=p;

18、在一个单链表中，若删除p所指结点的后续结点，则执行【   】

（A）p->next=p->next->next;  （B）p=p->next; p->next=p->next->next;

（C）p->next=p->next;        （D）p =p->next->next;

19、线性表是具有n个【   】的有限序列（n≠0)

（A）表元素     （B）字符      （C）数据元素　   （D）数据项

20、下列有关线性表的叙述中，正确的是（　　）

（A）线性表中的元素之间隔是线性关系

（B）线性表中至少有一个元素

（C）线性表中任何一个元素有且仅有一个直接前趋

（D）线性表中任何一个元素有且仅有一个直接后继

二、        填空题（共8题，每题2分，其中第5题没空2分，共计18分）

1、已知P为单链表中的非首尾结点，在P结点后插入S结点的语句为：_______________________ 。

2、顺序表中逻辑上相邻的元素物理位置         相邻， 单链表中逻辑上相邻的元素物理位置_________相邻。

3.、线性表L＝（a1，a2，...，an）采用顺序存储，假定在不同的n＋1个位置上插入的概率相同，则插入一个新元素平均需要移动的元素个数是________________________

4、在非空双向循环链表中，在结点q的前面插入结点p的过程如下：

  p->prior=q->prior;

  q->prior->next=p;

p->next=q;

  ______________________;

5、已知L是无表头结点的单链表，是从下列提供的答案中选择合适的语句序列，分别实现：

  （1）表尾插入s结点的语句序列是_______________________________

   (2) 表尾插入 s结点的语句序列是_______________________________

1)       p->next=s;

2)       p=L;

3)       L=s;

4)       p->next=s->next;

5)       s->next=p->next;

6)       s->next=L;

7)       s->next=null;

8)       while(p->next!=   Q)  p=p-next;

9)       while(p->next!=null) p=p->next;

6、 向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动（               ）个元素。

7、向一个长度为n的向量中删除第i个元素(1≤i≤n)时，需向前移动          个元素。

8、在顺序表中插入或删除一个元素，需要平均移动                元素，具体移动的元素个数与                                     有关。

三、        读程序写结果（共4题，每题5分，共计20分）

1.  #include < stdio.h >

long g(long k) {

if (k <= 1) return k;

return (10 * g(k – 1) + 20 * g(k – 2)) % 2008;

}

int main(void) {

long n;

scanf(“%ld”, &n);

printf(“%ld\n”, g(n));

return 0;

}

输入 6

输出                                                               

 

2. #include <stdio.h>

int main( )

{

int i, j, f,  a[9];

for(i=1; i<=8;i++)

 {

  f=i%2;

  if(f==0)a[i]=0;

    else   a[i]=1;

  for(j=1;j<=i;j++)

     if(f==1) a[i]=a[i]+j;

        else   a[i]=a[i]*j;

  }

for(i=1; i<=8; i++)printf(“%d”, a[i]); 

return 0;} 输出                                                             

 

3. #include <stdio.h>

int main() {

int a, b, c, p, q, r[3];

scanf(“%d%d%d”, &a, &b, &c);

p = a / b / c;

q = b – c + a + p;

r[0] = a * p / q * q;

r[1] = r[0] * (r[0] – 300);

if (3 * q – p % 3 <= r[0] && r[2] == r[2])

r[1] = r[r[0] / p % 2];

else

r[1] = q % p;

printf(“%d\n”, r[0]-r[1]);

return 0;}

输入：128 8 8   输出：                                               

 

4.  #include <stdio.h>

void digit(long n,long m)

   {if(m>0)

       printf("%2ld",n);

    if(m>1)

       digit(n/10,m/10);

    printf("%2ld",n);

   }

int main()

  {long x,x2;

   printf("Input a number:\n");  scanf("%ld",&x);

   x2=1;

   while(x2<x)  x2*=10;

   x2/=10;

   digit(x,x2);

   printf("\n");

   return 0;}

输入：156  输出：                                                                                          

四、        完善程序（共8空，每空4分，共32分）

1.下面的函数是对不带头结点的单链表进行就地逆置的算法，该算法用L返回逆置后的链表的头指针，试在空缺处填入适当的语句。

void  reverse(linklist   &L){

   p=null;  q=L;

   while(q!=NULL){    ①                                              ;

       q->next=p;  p=q;

        ②                                                               ; }

        ③                                                               ；

}

 

2.对单链表中元素按插入方法排序的算法如下，其中L为链表的头结点指针。请填充算法中标出的空白处，完成其功能。

typedef struct  node{ 

                          int data;  struct node *next;

                        }linknode ,*link;

void  Insertsort(link  L)

     {  link p, q,r,u;

         p=L->next;   ④                                                  

          while(  ⑤                                            )

             {

              r=L;q=L->next;            while(              &&q->data<=p->data)⑥

                      { r=q;  q=q->next;}

                  u=p->next; ⑦                                 

   ⑧                                                 ;p=u;}

        }

 

线性表

一、 单项选择题（共20题，每题1.5分，共计30分）

 

1	2	3	4	5	6	7	8	9	10
C	B	C	A	D	A	D	B	B	C
11	12	13	14	15	16	17	18	19	20
A	B	B	B	C	D	B	A	C	A

 

二、 填空题（共8题，每题2分，其中第5题没空2分，共计18分）

1、  s->next=p->next;   p->next=s;   2、         一定；不一定                   

3、       n/2                        4、             q->prior=p;                 

5、（1）        6)  3)             （2）             2)  9） 1)  7)                 

6、              n-i+1             7、                 n - i                 

8、（1）      表中一半           （2）            表长和该元素在表中的位置     

三、 阅读程序写结果（共4题，每题5分，共计20分）

1、            1240                2、          2 0 7 0 16 0 29 0                   

3、              130              4、            6 5 1 1 5 6               

四、 完善程序（共8空，每空4分，共32分） 

27、 ①        L=L->next            ②                q=L                     

③             L=p                ④             p=p->next                

 ⑤            p!=NULL            ⑥             p！=q                  

⑦        p->next=r->next;    ⑧             r->next=p