《数据结构-第2章-线性表》由会员分享，可在线阅读，更多相关《数据结构-第2章-线性表（10页珍藏版）》请在金锄头文库上搜索。
1、数据结构-第2章-线性表第2章线性表一、判断正误F ） 1.链表的每个结点中都恰好包含一个指针。（F ）2.链表的物理存储结构具有同链表一样的顺 序。 （F ）3.链表的删除算法很简单，因为当删除链中 某个结点后，计算机会自动将后续各个单元 向前移动。（F ）4.线性表的每个结点只能是一个简单类型， 而链表的每个结点可以是一个复杂类型。（F ）5.顺序表结构适宜于进行顺序存取，而链表 适宜于进行随机存取。（F ）_ 6.顺序存储方式的优点是存储密度大，且插入、删除运算效率高。（F ）7.线性表在物理存储空间中也一定是连续的。（T ）8.线性表在顺序存储时，逻辑上相邻的元素 未必在存储的物理位置
2、次序上相邻。（F ）9.顺序存储方式只能用于存储线性结构。（F ）10.线性表的逻辑顺序与存储顺序总是一致 的。二、单项选择题（C ）1 数据在计算机存储器内表示时，物理地 址与逻辑地址相同并且是连续的，称之为：（A ）存储结构（B ）逻辑结构（C） 顺序存储结构（D）链式存储结构（B ） 2. 一个向量第一个元素的存储地址是 100, 每个元素的长度为2,则第5个元素的地址是 （A）110（ B） 108（C） 100（D）120（A ） 3.在n个结点的顺序表中，算法的时间复杂 度是0 （1）的操作是：（A）访问第i个结点（K i n）和求第i个结点的直接前驱（2 i n）（B） 在第i个
3、结点后插入一个新结点（ K i n）（C）删除第i个结点（K i0)。A.表元素 B 字符 C 数据元 素 D 数据项(A ) 12 若某线性表最常用的操作是存取任一 指定序号的元素和在最后进行插入和删 除运算，则利用存储方式最节省时间。A.顺序表 B 双链表 C 带头 结点的双循环链表 D 单循环链表(D ) 13 某线性表中最常用的操作是在最后一 个元素之后插入一个元素和删除第一个 元素，则采用存储方式最节省运算时间。A.单链表B仅有头指针的单循环链表C双链表D仅有尾指针的单循环链表( B ) 14.静态链表中指针表示的是 .A 内存地址B.数组下标C下一元素地址D 左、右孩子地址(B )
4、 15.链表不具有的特点是 .A.插入、删除不需要移动元素B .可随机访问任一元素C不必事先估计存储空间D所需空间与线性长度成正比(D ) 16 完成在双循环链表结点 p之后插入s 的操作是().A pnext:=s;spriou:=p;pn extA.prior:=s ; sn ext:=pA .n ex t;B. pA.n extA.prior:=s; pA.n ext:=s; sA.prior:=p; sA.n ext:=pA .n ex t;C. sA.prior:=p; sA.n ext:=pA .n ex t;pA.n ext:=s; pA.n extA.prior:=s ;D.
5、sA.prior:=p; sA.n ext:=pA .n ex t; pA.n extA.prior:=s ; pA.n ext:=s;寸旨(B ) 17 .在单链表指针为p的结点之后插入 针为s的结点，正确的操作是：(A .p-n ext=s;s-n ext=p-next;B. s-n ext=p-next;p-n ext=s;C .p-n ext=s;p-n ext=s-next;D. p-n ext=s-next;p-n ext=s;(B ) 18 .对于一个头指针为head的带头结点的 单链表，判定该表为空表的条件是()A. head=NULL B. head-next=NULL C.
6、 head-next=head D . head!=NULL(A ) 19.在双向链表存储结构中，删除p须修改指针()。A .(pA.rli nk)A.lli nk:=pAli nk;B .(pA.lli nk)A.rli nk:=p; C .pA.rli nk:=(pA.rli nkf.rli nkD .pA.lli nk:=(pA.rli nkf.rli nk;(pA.lli nk)A.rli nk:=pA.rli nkpA.lli nk:=(pAli nk)Ali nk(pA.rli nk)Ali nk:=ppA.rli nk:=(pAli nkf.lli nk所指的结点、简答题1 线性
7、表有两种存储结构：一是顺序表，二是链表。试 问：（1）如果有n个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表的总数也会自动地 改变。在此情况下，应选用哪种存储结构？为什么？答：链式存储结构。因为长度动态变化是因为要进行插 入和删除操作，而进行这些操作，链式结构不需要 移动数据元素，效率较高。所以选用链式结构。（2）若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素， 那么应 采用哪种存储结构？为什么？ 答：顺序存储结构。因为顺序存储结构可利用起始地址 和偏移量在较短时间内完成存取，效率较高。所以选用顺序存储结构。2. 在单链表中设置头结点的作用是
8、什么？答：对数据进行插入、删除操作时，可直接通过修改指针完成前驱和后继的处理。表头指针非空，不需要再判断是否为空表。四、线性表具有两种存储方式，即顺序方式和链接方式。 现有一个具有五个元素的线性表 L=23，17, 47，05, 31,若它以链接方式存储在下列 100119号地址空间 中，每个结点由数据（占2个字节）和指针（占2个字 节）组成，如下所示：亦 IU 丨17 |X 丨23V 丨31丨 Y MKZHAA100120其中指针X，Y，Z的值分别为多少？该线性表的首 结点起始地址为多少？末结点的起始地址为多少？答：X=116，Y =120，Z=100，首结点起始地址：108, 末结点起始地
9、址：112。五、编程题1-建出顺序创建单链表的程序，即按从a1到an顺序创答：void Listlnsert(Node &La, int i, ElemType &e)int j = 0;Node * t = & La; while (t- next&jn ex t;Node * newnode = (Node *)malloc(sizeof(Node);Node * nex = t-n ex t; t-n ext = newno de; newno de-data = e; newno de-n ext = n ex t;Node La;for(i nt i= 0; i n ext)coun
10、 t+;t = t-n ex t;retur n count;3. 设有一带头结点的单链表,编程将链表颠倒过来，即n.a 1)，要求不用另外的数组(a1.a n)逆置为(a或结点完成.答：Node * Reverse(Node * front, Node * behind) If(behi nd)Node * t = Reverse(behi nd, behi nd-n ext); behi nd-n ext = front;return telse逆置答return front;请写一个算法将顺序存储结构的线性表( i为(an.a 1)，要求使用最少的附加空间:if(n %2=0)ai.aFor( int i = 1; i =n/2; i+)Data d = Li.data; Li.data = Ln-i.data;Ln-i.data = d;elseFor(int i= 1; i(n+1)/2; i+)Data d = Li.data; Li.data = Ln-i.data;Ln-i.data = d;
