线性表练习题(答案).doc

第2章 线性表一 选择题下列程序段的时间复杂度为（ C ）。 for( int i=1;i=n;i+) for( int j=1;j0）。A表元素 B字符 C数据元素 D数据项 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ A ）存储方式最节省时间。A顺序表 B双链表 C带头结点的双循环链表 D单循环链表某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ D ）存储方式最节省运算时间。A单链表 B仅有头指针的单循环链表 C双链表 D仅有尾指针的单循环链表设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( D )最节省时间。A. 单链表 B.单循环链表 C. 带尾指针的单循环链表 D.带头结点的双循环链表若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用（ D ）存储方式最节省运算时间。A单链表 B双链表 C单循环链表 D带头结点的双循环链表链表不具有的特点是（ B ） A插入、删除不需要移动元素 B可随机访问任一元素 C不必事先估计存储空间 D所需空间与线性长度成正比下面的叙述不正确的是（ B,C ）A线性表在链式存储时，查找第i个元素的时间同i的值成正比 B. 线性表在链式存储时，查找第i个元素的时间同i的值无关C. 线性表在顺序存储时，查找第i个元素的时间同i 的值成正比D. 线性表在顺序存储时，查找第i个元素的时间同i的值无关若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（ C ）(1=inext=H BP-next= H-next CP=H DP=H-next完成在双循环链表结点p之后插入s的操作是（ D ）； A p-next=s ; s-priou=p; p-next-priou=s ; s-next=p-next;B p-next-priou=s; p-next=s; s-priou=p; s-next=p-next;C s-priou=p; s-next=p-next; p-next=s; p-next-priou=s ;D s-priou=p; s-next=p-next; p-next-priou=s ; p-next=s; 设指针q指向单链表中结点A，指针p指向单链表中结点A的后继结点B，指针s指向被插入的结点X，则在结点A和结点B插入结点X的操作序列为（ B ）。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；二、判断顺序存储结构的主要缺点是不利于插入或删除操作。( 1 )线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。( 1 )对任何数据结构链式存储结构一定优于顺序存储结构。( 0 )顺序存储方式只能用于存储线性结构。( 0 )集合与线性表的区别在于是否按关键字排序。( 0 ) 线性表的特点是每个元素都有一个前驱和一个后继。( 0 ) 取线性表的第i个元素的时间同i的大小有关. ( 1 ) 线性表只能用顺序存储结构实现。( 0 ) 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。( 0 )链表是采用链式存储结构的线性表,进行插入、删除操作时，在链表中比在顺序存储结构中效率高。 ( 1 ) 三、填空线性表L=（a1,a2,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是_（n-1）/2_。在一个长度为n的顺序表中第i个元素（1=inext=p； s-prior= _p-prior_；p-prior=s；_s-prior-next_=s；链接存储的特点是利用_指针_来表示数据元素之间的逻辑关系。已知指针p指向单链表L中的某结点，则删除其后继结点的语句是：_p-next=p-next-next_四、算法设计题若链表类的定义如下所示，请完成以下成员方法的实现。（另附页提交答案）void Delete(const DataType& x); /删除值为x的结点void Convert();/单链表就地逆转void operator+= (const LinkList &other);/将两个已排序的单链表合并成一个链表（值可重复）#include #include #include #define DataType int template class LinkList;template class Node friend class LinkList;public: Node() next = NULL; Node(const DataType& x) data = x; next = NULL; DataType data; Node* next;template class LinkList public: LinkList(); int Size(); void Insert(int i,const DataType& x);/在第i位插入值为x的结点 void Insert(DataType *p,const DataType& x);在指针p的后面插入结点x void Delete(int i);/删除第i个结点 Node* Find(const DataType& x); DataType GetData(int i);void Print();void Delete(const DataType& x); /删除值为x的结点void Convert();/单链表就地逆转 void operator+= (const LinkList &other);/将两个已排序的单链表合并成一个链表（值可重复）private: DataType * Index(i);/返回第i个结点的地址 Node* head; int size;void Delete(const DataType& x) /删除值为x的结点 Node* p=head, *q; for( int i=1;inext-data=x) q=p-next; p-next=q-next; delete q; templatevoid LinkList: Convert()/单链表就地逆转 Node * p=NULL, *q1=head-next,*q2;if(Size()1) while(q1!=NULL) q2=q1-next; q1-next=p;p=q1;q1=q2; head-next=p; /将两个已排序的单链表合并成一个链表（值可重复）templateLinkList LinkList:operator +=(const LinkList& other)int i;i=other.size; Node *p=this-head,*q=other.head-next,*temp;while( p-next!=NULL&q!=NULL)if(p-next-datadata) p=p-next;elsetemp