数据结构课后练习题汇总

19、对顺序表上的插入、删除算法的时间复杂性分析来说，通常以（ ）为标准操作。

A、插入操作 B、结点移动 C、算术表达式 D、删除操作 20、对于顺序表的优缺点，以下说法错误的是（ ）

A、无需为表示结点间的逻辑关系而增加额外的存储空间 B、可以方便地随机存取表中的任一结点 C、插入和删除运算较方便

D、由于顺序表要求占用连续的空间，存储分配只能预先进行(静态分配)

21、若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（ ）存储方式最节省时间。

A、顺序表 B、单链表 C、双链表 D、单循环链表 22、循环链表主要优点是（ ）

A、不再需要头指针了

B、已知某个结点的位置后，能够容易找到它的直接前趋 C、在进行插入、删除运算时，能更好地保证链表不断开 D、从表中任一结点出发都能扫描到整个链表

23、在线性表的下列存储结构中，读取元素花费时间最少的是（ ）

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

二、填空题

１、在线性结构中，第一个结点（ ）前趋结点，其余每个结点有且只有（ ）个前趋结点。 ２、在顺序表中插入或删除一个元素，需要平均移动（ ）元素，具体移动的元素个数与（ ）有关。 ３、已知Ｌ是无表头结点的单链表，试从下列提供的答案中选择合适的语句序列，分别实现： （１）表首插入Ｓ结点的语句序列是（ ）。 （２）表尾插入Ｓ结点的语句序列是（ ）。

Ａ、Ｐ->next=S; Ｂ、P=L; Ｃ、L=S; Ｄ、P->next=S->next; Ｅ、S->next=P->next; Ｆ、S->next=L; Ｇ、S->next=NULL; Ｈ、while(P->next!=Q)p=p->next; Ｉ、while(P->next!=NULL)P=P->next; 4、已知L是带表头结点的非空单链表，试从下列提供的答案中选择合适的语句序列。 （1）删除首元结点的语句序列是（ ） ,（2）删除尾元结点的语句序列是（ ）

A、P=P->next; B、P->next=P->next->next; C、while(P!=NULL)p=p->next;

D、while(Q->next!=NULL){P=Q;Q=Q->next;} E、while(P->next!=Q)P=P->next;

F、Q=P; G、Q=P->next; H、P=L; I、L=L->next; J、free(Q);

8

5、已知L是带表头结点的非空链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。 （1）删除P结点的直接后继结点的语句序列是（ ）, （2）删除P结点的直接前趋结点的语句序列是（ ）

A、P->next=P->next->next; B、P=P->Pnext->next; C、while(P->next!=Q)P=P->next;

D、while(P->next->next=Q)P=P->next; E、Q=P; F、Q=P->next; G、P=L; H、L=L->next; I、free(Q);

6、已知结点编号，在各结点查找概率相等的情况下，从n个结点的单链表中查找一个结点，平均要访问（ ）个结点，从n个结点的双链表中查找一个结点，平均要访问（ ）个结点。

7、对于一个具有n个结点的单链表，在已知p所指结点后插入一个新结点的时间复杂度是（ ）；在值域为给定值的结点后插入一个新结点的时间复杂度是（ ）。 8、单链表是（ ）的链接存储表示。 9、单链表中设置头结点的作用是（ ）。

10、在单链表中，除首元结点外，任一结点的存储位置由（ ）指示。 11、在非空双向循环链表中，在结点q的前面插入结点p的过程如下： p->prior=q->prior; q->prior->next=p;p->next=q;( );

12、在双向链表中，每个结点有两个指针域，一个指向（ ），另一个指向（ ）。

13、顺序表中逻辑上相邻的元素的物理位置（ ）相邻。单链表中逻辑上相邻的元素的物理位置（ ）相邻。

14、为了便于讨论，有时将含n(n≥0)个结点的线性结构表示成(a1，a2,?,an)，其中每个ai代表一个______。a1称为______结点，an称为______结点，i称为ai在线性表中的________。对任意一对相邻结点ai、ai┼1(1≤i

15、线性结构的基本特征是：若至少含有一个结点，则除起始结点没有直接______外，其他结点有且仅有一个直接______；除终端结点没有直接______外，其它结点有且仅有一个直接______. 16、所有结点按1对1的邻接关系构成的整体就是______结构。

17、线性表的逻辑结构是______结构。其所含结点的个数称为线性表的__________。 18、在单链表中，指针p所指结点为最后一个结点的条件是___________。 三、判断题

1. 顺序存储的线性表可以随机存取。

2. 顺序存储的线性表的插入和删除操作不需要付出很大的代价，因为平均每次操作只有近一半的元素需

要移动。

3. 线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数

据对象。

9

4. 在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上不一定相邻。 5. 在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。 6. 在单链表中，可以从头结点进行查找任何一个元素。 7. 线性表的链式存储结构优于顺序存储结构。

8. 在线性表的顺序存储结构中，插入和删除元素时，移动元素的个数与该元素的位置有关。

9. 在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。 10. 顺序存储方式只能用于存储线性结构。

四、简答题

1、 若较频繁地对一个线性表进行插入和删除操作，该线性表宜采用哪种存储结构？为什么？ 2、 描述概念：头指针、头结点、首元结点的区别？

3、 设A是一个线性表（a1a2…an），采用顺序存储结构，则在等概率的前提下，平均每插入一个元素

需要移动的元素个数为多少？若元素插在ai与ai+1之间（0<=I<=n-1）的概率为2(n-i)/(n(n+1))，则平均每插入一个元素所要移动的元素个数又是多少？ 4、为什么在单循环链表中设置尾指针比设置头指针更好？

5、双链表和单循环链表中，若仅知道指针p指向某个结点，不知道头指针，能否将结点*p从相应的

链表中删除？若可以，其时间复杂度各为多少？ 6、下列算法的功能是什么？

LinkedList test1(LinkedList L) {//L是无头结点的单链表 ListNode *q,*p; if(L&&L->next)

{q=L ; L=L->next; p=L; while(p->next) p=p->next; p->next=q; q->next=NULL; } return L; }

7、如果有n个线性表同时共存，并且在处理过程中各表的长度会发生动态变化，线性表的总长度也

会自动地改变。在此情况下，应选择哪一种存储结构。为什么？

8、若线性表的总数基本稳定，且很少进行插入删除操作，但要求以最快的方式存取线性表的元素，

应该用哪种存储结构。为什么？

10

9、设有多项式a(x)=9+8x+9x4+5x10 b(x)=-2x+22x7-5x10 （1） 用单链表给出a(x)、b(x)的存储表示；

（2） 设c (x)=a(x)+b(x)，求得c(x)并用单链表给出其存储表示。

五、算法设计题

1、编写一个函数将一个顺序表A（有多个元素且任何元素不为0）分拆成两个顺序表，使A中大于0的元素存放在B中，小于0的元素存放在C中。

2、设顺序表L中的数据元素递增有序。试写一算法，将e插入到顺序表的适当位置，插入后保持该表的有序性。

3、A、B为元素递增有序排列的单链表（同一表中可能有相同元素），编写算法另建一单链表C，保存两个表的公共元素，要求C的元素值各不相同且递增有序。 4、设有一个由正整数组成的无序单链表，编写算法实现下列功能：

(1) 找出最小值结点，且显示该数值。

(2) 若该数值为奇数，则将其与直接后继结点的数值交换。 (3) 若为偶数，则将其直接后继结点删除。

六、编程附加题

1. 试分别用顺序表和单链表作为存储结构，实现将线性表（a0,a1,a2,….an-1）就地逆置的操作，所谓“就地”指辅助空间为O（1）。

2. 设顺序表L是一个递增（允许有相同的值）有序表，试写一算法将x 插入L中，并使L仍为一个有序表。

3. 设单链表L是一个非递减有序表，试写一个算法将x插入其中后仍保持L的有序性。 4. 试写出在无头结点的单链表的第i个元素之前插入一个元素的算法。

5. 设A、B是两个线性表，其表中元素递增有序，长度分别为m和n。试写一算法分别以顺序存储和链式存储将A和B归并成一个仍按元素值递增有序的线性表C，请分析算法的时间复杂度。

6. 设指针la和lb分别指向两个无头结点的单链表的首结点，设计从表la中删除第i个元素起共len个元素，并将这些元素插入到lb中第j个结点之前的算法。

7. 单链表L是一个递减有序表，试写一高效算法，删除表中值大于min且小于max的结点（若表中有这样的结点），同时释放被删结点空间，这里min和max是两个给定的参数。请分析你的时间复杂度。 8. 编写一个算法将一个头结点指针为pa的单链表A分解成两个单链表A和B，其头结点指针分别为pa和pb，使得A链表中含有链表A中的序号为奇数的元素，而B链表中含有原链表A中的序号为偶数的元素，且保持原来的相对顺序。

9. 假设以两个元素依值递增有序排列的线性表A,B分别表示两个集合，先要求另辟空间构造一个线性表C,其元素为两集合的交集，且表C中的元素也依值递增有序排列。是对顺序表编写求C的算法。

11