《数据结构》第一、二章自测题一、选择题1 .计算机算法必须具备输入、输出和( )等5个特性。

A．可行性、可移植性和可扩充性B．可行性、确定性和有穷性C．确定性、有穷性和稳定性D．易读性、稳定性和安全性2．在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（）。

A．p->next=s;s->next=p->next; B．p->next=s->next;p->next=s;C．p->next=s;p->next=s->next; D．s->next=p->next;p->next=s;3．设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( )最节省时间。

A. 单链表 B.单循环链表C. 带头结点的双循环链表D.带尾指针的单循环链表4.从逻辑上来分，数据结构可以分为（）两大类。

A. 动态结构、静态结构B.顺序结构、链式结构C. 线性结构、非线性结构D.初等结构、构造型结构5.算法分析的两个主要方面是：（）A．空间复杂性和时间复杂性 B.正确性和简明性C．可读性和文档性 D.数据复杂性和程序复杂性6. 计算机算法指的是：（）A.计算方法B.排序方法C.解决问题的有限运算序列D.调度方法7. 一个顺序表由（a0,a1,a2,…a n-1）n个元素构成，a0存储地址是100，每个元素的长度为2，则a4元素的地址是（）A.110B.108C.100D.1208.向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（）个元素。

A.8B.63.5C.63D.79.线性表Ｌ在( )情况下适用于使用链式结构实现。

Ａ.需经常修改Ｌ中的结点值Ｂ.需不断对Ｌ进行删除插入Ｃ.Ｌ中含有大量的结点Ｄ.Ｌ中结点结构复杂10.在一个以 h 为头的单循环链中，p 指针指向链尾的条件是（）A. p->next=hB. p->next=NULLC. p->next->next=hD. p->data=-111. 对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（）A．head==NULL B．head→next==NULL C．head→next==head D．head!=NULL12. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址( )A.必须是连续的B.部分地址必须是连续的C.一定是不连续的D.连续或不连续都可以13.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。

A．顺序表B．双链表C．带头结点的双循环链表D．单循环链表14.与单链表相比，双向链表的优点之一是（）A.插入、删除操作更简单B.可以进行随机访问C.可以省略表头或表尾指针D.访问前后结点更灵活15.在双向链表中，删除P结点的操作（）（结点空间释放语句省略）A.p->prior->next=p->next; p-> next -> prior =p-> priorB. p-> prior= p-> prior -> prior; p-> prior -> prior=p;C. p-> next -> prior =p; p->next= p-> next ->next;D. p-> next= p-> prior -> prior; p-> prior= p-> prior -> prior;16. 在双向循环链表中，在p指针所指的结点后插入q所指向的新结点，其修改指针的操作是（）。

A．p->next=q; q->prior=p; p->next->prior=q; q->next=q;B．p->next=q; p->next->prior=q; q->prior=p; q->next=p->next;C．q->prior=p; q->next=p->next; p->next->prior=q; p->next=q;D．q->prior=p; q->next=p->next; p->next=q; p->next->prior=q;17. 以下说法错误的是（）。

A．求表长、定位这两种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低B．顺序存储的线性表可以随机存取C．由于顺序存储要求连续的存储区域，所以在存储管理上不够灵活D．线性表的链式存储结构优于顺序存储结构18．若一个算法的时间复杂度用T(n)表示，其中n 的含义是（）A．问题规模B．语句条数C．循环层数D．函数数量19．将长度为n 的单链表连接在长度为m 的单链表之后，其算法的时间复杂度为（）A．O(1) B．O(m) C．O(n) D．O(m+n)20．对于三个函数f(n)=2008n3+8n2+96000，g(n)=8n3+8n+2008 和h(n)=8888nlogn+3n2，下列陈述中不.成立的是（）A．f(n)是0(g(n)) B．g(n)是0(f(n)) C．h(n)是0(nlogn) D．h(n)是0(n2) 21. 指针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；22.对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为( )A.顺序表B.用头指针表示的单循环链表C.用尾指针表示的单循环链表D.单链表二、填空题1、程序段i=1; while(i<=n) i=i*3;的时间复杂度为。

2、在长度为n的顺序表的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动个元素3、带头结点的双循环链表L为空表的条件是：。

4、以下程序的功能是实现带头结点的单链表数据结点逆序连接，请填空完善之。

void reverse(LinkList h) // h为头结点指针；{ LinkList p,q;p=h->next; h->next=NULL;while( _______){q=p; p=p->next; q->next=h->next; h->next= ________; } }5.数据的链式存储结构的特点是借助________表示数据元素之间的逻辑关系。

6.在如图所示的链表中，若在指针p 所指的结点之后插入数据域值相继为a 和b 的两个结点，则可用下列两个语句实现该操作，它们依次是________和________。

三、判断题（请在你认为正确的后面的括号内打√，错误的打×。

）1．顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。

( )2．顺序存储方式的优点是存储密度大，且插入、删除运算效率高.( )3．线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻( )4.循环链表不是线性表.( )5. 算法的优劣与算法描述语言无关，但与所用计算机有关。

( )6. 线性表的特点是每个元素都有一个前驱和一个后继。

( )四、算法设计题1.试编写在带头结点的单链表中删除（一个）最小值结点的（高效）算法。

void delete（Linklist &L）2. 将两个递增的有序链表合并为一个递增的有序链表。

要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。

表中不允许有重复的数据。

void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc)3.已知长度为n的线性表A采用顺序存储结构，请写一时间复杂度为O(n)、空间复杂度为O(1)的算法，该算法删除线性表中所有值为item的数据元素。

void Delete_Sq(SqList &A)4.假设该链表只给出了头指针list 查找链表中倒数第K 位置的结点（K 为正整数），若查找成功，算法输出该结点 data 域的值，并返回1，否则只返回0；要求：（1）简述算法的基本设计思想；（2）描述算法的详细实现步骤（使用C ，或C++实现 ），关键之处给出详细解释。

5. 已知非空线性链表第一个结点的指针为list ，请写一个算法，将该链表中数据域值最大的那个结点移到链表的最后面。

6. 若已知非空线性链表第一个结点的指针为list ，请 写一个算法，将该链表中数据域值最小的那个结点移到链表的最前端。

7. 已知一个带有表头结点的单链表，头指针为L ，请用一个尽可能高效的算法实现，在非头结点p 所指元素前，插入元素e,并分析算法的时间复杂度。

8. 已知一个带有表头结点的单链表，头指针为L ，请用一个尽可能高效的算法实现，删除非头结点p 所指元素,并分析算法的时间复杂度。

9.试设计实现在单链表中删去值相同的多余结点的算法。

10. 编写算法，判断带头结点的双向循环链表L 是否对称。

对称是指：设各元素值a 1,a 2,...,a n , 则有a i =a n-i+1 ，即指：a 1= a n ，a 2= a n-1 。

结点结构为：11. 已知带头结点的动态单链表L 中的结点是按整数值递增排列，试写一算法将值为X 的结点插入链表L 中，使L 仍然有序。

12. 假设线性表采用顺序存储结构，编写算法，将顺序表L 中所有值为奇数的元素调整到表的前端。