数据结构练习第二章 线性表

数据结构练习 第二章 线性表

一、选择题

1. 下面关于线性表的叙述错误的是（ ）。

A.线性表采用顺序存储必须占用一片连续的存储空间 B. 线性表采用链式存储不必占用一片连续的存储空间 C. 线性表采用链式存储便于插入和删除操作的实现 D. 线性表采用顺序存储便于插入和删除操作的实现 2. 设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为（ ）。

A.q=p->next；p->data=q->data；p->next=q->next；free(q)； B. q=p->next；q->data=p->data；p->next=q->next；free(q)； C. q=p->next；p->next=q->next；free(q)； D. q=p->next；p->data=q->data；free(q)；

3. 设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（ ）。

A. O(n) B. O(nlog2n) C. O(1) D. O(n2)

4．设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为（ ）。

2

A. O(log2n) B. O(1) C. O(n) D. O(n)

5．设一条单链表的头指针变量为head且该链表没有头结点，则其判空条件是（ ）。 A. head==0 B.head->next==0 C. head->next==head D.head!=0

6．设带有头结点的单向循环链表的头指针变量为head，则其判空条件是（ ）。 A. head==0 B. head->next==0 C. head->next==head D. head!=0

7．建立一个长度为n的有序单链表的时间复杂度为（ ） A. O(n) B. O(1) C. O(n2) D. O(log2n)

8．设顺序线性表中有n个数据元素，则删除表中第i个元素需要移动（ ）个元素。

A. n-i B. n+l -i C. n-1-i D. i

9．设指针变量p指向双向链表中结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X的操作序列为（ ）。 A. p->right=s； s->left=p； p->right->left=s； s->right=p->right； B. s->left=p；s->right=p->right；p->right=s； p->right->left=s；

C. p->right=s； p->right->left=s； s->left=p； s->right=p->right； D. s->left=p；s->right=p->right；p->right->left=s； p->right=s；

10．设某链表中最常用的操作是在链表的尾部插入或删除元素，则选用下列（ ）存储方式最节省运算时间。 A. 单向链表 B .单向循环链表 C. 双向链表 D. 双向循环链表

1

11．设指针q指向单链表中结点A，指针p指向单链表中结点A的后继结点B，指针s指向被插入的结点X，则在结点A和结点B插入结点X的操作序列为（ ）。

A. s->next=p->next；p->next=-s； B. q->next=s； s->next=p； C. p->next=s->next；s->next=p； D. p->next=s；s->next=q； 12．在一个长度为n的顺序存储的线性表中，向第i个元素（1≤i≤n+1）之前

插入一个新元素时，需要从后向前依次后移（ ）个元素。 A．n-i B．n-i+1 C．n-i-1 D．i

13．在一个单链表HL中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，则执行（ ）。 A. q->next=p->next;p->next=q; B. p->next=q->next;q=p;

C. q->next=p->next;p->next=q; D. p->next=q->next;q->next=p; 14．在单链表中，存储每个结点需要有两个域，一个是数据域，另一个是指针域，指针域指向该结点的（ ） A.直接前趋 B.直接后继 C.开始结点 D.终端结点

15．将两个各有n个元素的有序表合并成一个有序表，其最少的比较次数为

（ ）

A.n B.2n-1 C.2n D.n2

16．线性表采用链式存储结构时，要求内存中可用存储单元的地址( ) A. 必须是连续的 B. 必须是部分连续的 C. 一定是不连续的 D. 连续和不连续都可以

17．设h是指向非空带表头结点的循环链表的头指针，p是辅助指针。执行程序段

p=h;

while (p->next->next!=h) p=p->next;

p->next=h;

后（其中，p->next为p指向结点的指针域），则( ) A. p->next指针指向链尾结点 B. h指向链尾结点 C. 删除链尾前面的结点 D. 删除链尾结点

18．设顺序表有19个元素，第一个元素的地址为200，且每个元素占3个字节，则第14个元素的存储地址为( ) A.236 B.239 C.242 D.245 19．设顺序表有9个元素，则在第3个元素前插入一个元素所需移动元素的个数为( )

A.5 B.6 C.7 D.9

20．设p为指向双向循环链表中某个结点的指针，p所指向的结点的两个链域分别用p→llink和p→rlink表示，则同样表示p指针所指向结点的表达式是( ) A.p→llink B.p→rlink C.p→llink→llink D.p→llink→rlink

21．一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元

2

素的存储地址是( )

A. 110 B. 108 C. 100 D. 120 22．关于存储相同数据元素的说法中正确的是（ ） A．顺序存储比链式存储少占空间 B.顺序存储比链式存储多占空间

C.顺序存储和链式存储都要求占用整块存储空间 D.链式存储比顺序存储难于扩充空间

23．已知一个单链表中，指针q指向指针p的前趋结点，若在指针q所指结点和指针p所指结点之间插入指针s所指结点，则需执行（ ） A．q→next=s；p→next=s； B.q→next=s；s→next=p； C.q→next=s；q→next=p； D.q→next=s；s→next=q； 24．在长度为n的线性表中删除一个指针p所指结点的时间复杂度是（ ） A．O(n) B.O(1) C.O(log2n) D.O(n2) 25．若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则最节省运算时间的存储方式是（ ） A.单链表 B.仅有头指针的单循环链表 C.双链表 D.仅有尾指针的单循环链表

26．从一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，需向前移动的元素的个数是（ ）

A.n-i B.n-i+1 C.n-i-1 D.i

27．对于长度为n的顺序表执行删除操作，则其结点的移动次数（ ） A.最少为0，最多为n B.最少为1，最多为n C.最少为0，最多为n-1 D.最少为1，最多为n-1

28．在一个单链表中，若p所指结点是q所指结点的前驱结点，则删除结点q的正确操作是（ ） A. p->next=q B. p->next=q->next C. p=q->next D. p->next=q->next->next 29．在一个具有n个结点的有序单链表中插入一个新结点，并使插入后仍然有序，则该操作的时间复杂性量级为（ ）

A．O（1） B．O（n） C．O（nlog2n） D．O(n2)

30．顺序存储的线性表（a1,a2,?,an）,在任一结点前插入一个新结点时所需移动结点的平均次数为（ ）

A．n B．n/2 C．n+1 D．(n+1)/2

31．设单链表中指针p指向结点A，若删除A后的结点存在，则需要修改指针的操作为（ ）。

A．p->next=p->next->next B．p=p->next C．p=p->next->next D．p->next=p 32．线性表的链式存储实现有利于（ ）运算。 A．插入 B．读表元 C．查找 D．定位

33．从一个长度为n的顺序表中删除第i个元素(1≤i≤n)，需向前移动（ ）

3

个元素。

A．n-i B．n-i+1 C．n-i-1 D．i

34．在一个长度为n的顺序存储线性表中，向第i个元素(1≤i≤n+1)之前插入一个新元素时，需向后移动（ ）个元素。 A．n-i B．n-i+1 C．n-i-1 D．i

35．在一个单链表中，已知*q结点是*p结点的前趋结点，若在*q和*p之间插入*s结点，则需执行（ ）。

A．s->next=p->next; p->next=s; B．q->next=s; s->next=p; C．p->next=s->next; s->next=p; D．p->next=s; s->next=q;

36．在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行（ ）。

A.HL = p; p->next = HL; B.p->next = HL; HL = p; C.p->next = HL; p = HL;

D.p->next = HL->next; HL->next = p;

37．在一个单链表HL中，若要删除由指针q所指向结点的后继结点，则执行（ ）。

A.p = q->next ; p->next = q->next; B.p = q->next ; q->next = p;

C.p = q->next ; q->next = p->next;

D.q->next = q->next->next; q->next = q; 38．线性表采用链式存储时，其地址（ ）。

A．必须是连续的 B．部分地址必须是连续的 C．一定是不连续的 D．连续与否均可以

39．在一个长度为n的线性表中插入第i个元素的操作中，i的取值范围是 A．1≤i≤n B．0≤i≤n C．1≤i≤ n+1 D．1≤i≤n-1 40．如果要查找单链表中的第i个元素，应该从（ ）开始进行查找。 A．第i个结点 B． 头结点 C． 尾结点 D． 任意一个结点 41．在一个长度为n的线性表中顺序查找值为x的元素时，查找时的平均查找长度（即x同元素的平均比较次数，假定查找每个元素的概率都相等）为（ ）。 A.n B.n/2 C. (n+1)/2 D. (n-1)/2

42．在一个单链表HL中，若要在指针q所指的结点的后面插入一个由指针p所指的结点，则执行（ ）。

A.q->next = p->next ; p->next = q; B.p->next = q->next; q = p;

C.q->next = p->next; p->next = q; D.p->next = q->next ; q->next = p;

43. 在一个单链表中,若q所指结点是p所指结点的前驱结点,若在q与p之间插入一个s所指的结点,则执行( )。

A. s→link=p→link; p→link=s; B. p→link=s; s→link=q; C . p→link=s→link; s→link=p; D. q →link=s; s→link =p; 44. 线性链表不具有的特点是（ ）。

4