数据结构链表练习题

时间:2024-02-25 19:04:34

判断题:

1.对于顺序存储的长度为N的线性表,访问结点和增加结点的时间复杂度分别对应为O(1)和O(N)。T

2.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算,则利用顺序表存储最节省时间。T

3.在具有N个结点的单链表中,访问结点和增加结点的时间复杂度分别对应为O(1)和O(N)。F

4.对于顺序存储的长度为N的线性表,删除第一个元素和插入最后一个元素的时间复杂度分别对应为O(1)和O(N)。F

5.若用链表来表示一个线性表,则表中元素的地址一定是连续的。F

6.在顺序表中逻辑上相邻的元素,其对应的物理位置也是相邻的。T

7.顺序存储的线性表不支持随机存取。F

8.在顺序表上进行插入、删除操作时需要移动元素的个数与待插入或待删除元素的位置无关。F

9.在线性表的顺序存储结构中可实现快速的随机存取,而在链式存储结构中则只能进行顺序存取。T

10.)单链表不是一种随机存取的存储结构。

单选题:

1.

在双向循环链表中,在p所指的结点之后插入s指针所指的结点,其操作是()。 

2.

线性表采用链式存储时,其地址()。 

3.

线性表的顺序存储结构是一种( ) 

4.

一个顺序表所占用的存储空间大小与( )无关。

5.

假设在顺序表{A0,A1,...,An-1}中,每一个数据元素所占用的存储单元的数目为4,且第0个数据元素A0的存储地址为100,由第7个数据元素A7的存储地址是( )。 

6.

在链表中若经常要删除表中最后一个结点或在最后一个结点之后插入一个新结点,则宜采用()存储方式。 

7.

要将一个顺序表{a0​​,a1​​,……,an1​​}中第i个数据元素ai​​(0≤i≤n-1)删除,需要移动( )个数据元素。

8.

对于下图2.29所示的单链表,下列表达式值为真的是( )。 

9.

一个一维数组M,下标的范围是0到9,每个数组元素用相邻的5个字节存储。存储器按字节编址,设存储数组元素M[0]的第一个字节的地址是100,则M[4]的第一个字节的地址是。 (2分)

10.

链式存储结构的最大优点是( )。

11.

在单链表中,增加一个头结点的最终目的是为了( )。 

12.

已知指针ha和hb分别是两个单链表的头指针,下列算法将这两个链表首尾相连在一起,并形成一个循环链表(即ha的最后一个结点链接hb的第一个结点,hb的最后一个结点指向ha),返回该循环链表的头指针。请将该算法补充完整。

typedef struct node{
ElemType data;
    struct node *next;
}LNode;
LNode *merge(LNode *ha, LNode *hb) {
LNode *p=ha;
     if (ha==NULL || hb==NULL) {
cout<<”one or two link lists are empty!”<<endl;
          return NULL;
     }
     while ( p->next!=NULL ) 
           p=p->next;
     p->next=hb;
     while ( p->next!=NULL ) 
           p=p->next;
           __________         
}

13.

已知单链表中的元素以值递增有序排列,下列算法删除单链表中所有值相同的元素,同时释放被删结点空间。请将该算法补充完整。 

typedef struct node{
ElemType data;
    struct node *next;
}LNode;
void delete_equal(LNode *h){
LNode *p=h, *q;
     if (h==NULL)  return;
    while (p->next!=NULL) {
        q=p->next;
        if (p->data!=q->data) 
             p=q;
        else  //相邻两元素值相等,则循环删除后继等值结点
             while (q!=NULL && q->data==p->data) {
             __________________________     
             }
    }
}

14.

带表头附加结点的单链表head为空的判断条件是()。 

15.

非空的循环单链表head的尾结点(由p所指向)满足()。

16.

在循环双链表的p所指结点之前插入s所指结点的操作是()。 

17.

若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点,则采用()存储方式最节省运算时间。

18.

某线性表最常用的操作是在最后一个结点之后插入一个结点或删除第一个结点,故采用()存储方式最节省运算时间。 

19.

在一个长度为n(n>1)的单链表上,设有头和尾两个指针,执行()操作与链表的长度有关。 

20.

如果对线性表的运算只有4种,即删除第一个元素,删除最后一个元素,在第一个元素前面插入新元素,在最后一个元素的后面插入新元素,则最好使用()。