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

1、数据结构练习第二章线性表数据结构练习 第二章 线性表一、选择题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

2、-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个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为（ ）。A. O(log2n) B. O(1) C. O(n2) D. O(n)5设一条单链表的头指针变量为head且该链表没有头结点，则其判空条件是（ ）。A. head=0 B.head-next=0C. head-

3、next=head D.head!=06设带有头结点的单向循环链表的头指针变量为head，则其判空条件是（ ）。 A. head=0 B. head-next=0C. head-next=head D. head!=07建立一个长度为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. i9设指针变量p指向双向链表中结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X的操作序列为（ ）。 A. p-r

4、ight=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. 双向循环链表11

5、设指针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个元素（1in+1）之前插入一个新元素时，需要从后向前依次后移（ ）个元素。An-i Bn-i+1 Cn-i-1 Di13在一个单链表HL中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，则执行（）。A. q

6、-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.n216线性表采用链式存储结构时，要求内存中可用存储单元的地址( )A. 必须是连续的 B. 必须是部分连续的 C. 一定是不连续的 D. 连续和不连续都可

7、以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.24519设顺序表有9个元素，则在第3个元素前插入一个元素所需移动元素的个数为( )A.5 B.6 C.7 D.920设p为指

8、向双向循环链表中某个结点的指针，p所指向的结点的两个链域分别用pllink和prlink表示，则同样表示p指针所指向结点的表达式是( )A.pllink B.prlinkC.pllinkllink D.pllinkrlink21一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的存储地址是( )A. 110 B. 108 C. 100 D. 12022关于存储相同数据元素的说法中正确的是（ ）A顺序存储比链式存储少占空间B.顺序存储比链式存储多占空间C.顺序存储和链式存储都要求占用整块存储空间D.链式存储比顺序存储难于扩充空间23已知一个单链表中，指针q指向指针p的前趋结点

9、，若在指针q所指结点和指针p所指结点之间插入指针s所指结点，则需执行（ ）Aqnext=s；pnext=s； B.qnext=s；snext=p；C.qnext=s；qnext=p； D.qnext=s；snext=q；24在长度为n的线性表中删除一个指针p所指结点的时间复杂度是（ ）AO(n) B.O(1)C.O(log2n) D.O(n2)25若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则最节省运算时间的存储方式是（）A.单链表 B.仅有头指针的单循环链表C.双链表 D.仅有尾指针的单循环链表26从一个长度为n的顺序表中删除第i个元素（1in）时，需向前移动的

10、元素的个数是（）A.n-i B.n-i+1 C.n-i-1 D.i27对于长度为n的顺序表执行删除操作，则其结点的移动次数（）A.最少为0，最多为n B.最少为1，最多为nC.最少为0，最多为n-1 D.最少为1，最多为n-128在一个单链表中，若p所指结点是q所指结点的前驱结点，则删除结点q的正确操作是（）A. p-next=q B. p-next=q-nextC. p=q-next D. p-next=q-next-next29在一个具有n个结点的有序单链表中插入一个新结点，并使插入后仍然有序，则该操作的时间复杂性量级为（）AO（1） BO（n）CO（nlog2n） DO(n2)30顺序存

11、储的线性表（a1,a2,an）,在任一结点前插入一个新结点时所需移动结点的平均次数为（）An Bn/2Cn+1 D(n+1)/231设单链表中指针p指向结点A，若删除A后的结点存在，则需要修改指针的操作为（ ）。Ap-next=p-next-next Bp=p-nextCp=p-next-next Dp-next=p32线性表的链式存储实现有利于（ ）运算。A插入 B读表元C查找 D定位33从一个长度为n的顺序表中删除第i个元素(1in)，需向前移动（ ）个元素。An-i Bn-i+1Cn-i-1 Di34在一个长度为n的顺序存储线性表中，向第i个元素(1in+1)之前插入一个新元素时，需向后

12、移动（ ）个元素。An-i Bn-i+1Cn-i-1 Di35在一个单链表中，已知*q结点是*p结点的前趋结点，若在*q和*p之间插入*s结点，则需执行（ ）。As-next=p-next; p-next=s; Bq-next=s; s-next=p;Cp-next=s-next; s-next=p; Dp-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-

13、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的取值范围是 A1in B0in C1i n+1 D1in-140如果要查找单链表中的

14、第i个元素，应该从（ B ）开始进行查找。A第i个结点 B 头结点 C 尾结点 D 任意一个结点41在一个长度为n的线性表中顺序查找值为x的元素时，查找时的平均查找长度（即x同元素的平均比较次数，假定查找每个元素的概率都相等）为（ C ）。A.n B.n/2 C. (n+1)/2 D. (n-1)/242在一个单链表HL中，若要在指针q所指的结点的后面插入一个由指针p所指的结点，则执行（ D ）。 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 =

15、 q-next ; q-next = p;43. 在一个单链表中,若q所指结点是p所指结点的前驱结点,若在q与p之间插入一个s所指的结点,则执行( D )。 A. slink=plink; plink=s; B. plink=s; slink=q; C . plink=slink; slink=p; D. q link=s; slink =p;44. 线性链表不具有的特点是（ A ）。A随机访问 B不必事先估计所需存储空间大小C插入与删除时不必移动元素 D所需空间与线性表长度成正比45. 下述哪一条是顺序存储结构的优点？（ C ）。A 插入运算方便 B可方便地用于各种逻辑结构的存储表示 C存储

16、密度大 D删除运算方便46. 下面关于线性表的叙述中，错误的是哪一个？（ B ）。A线性表采用顺序存储，必须占用一片连续的存储单元。B线性表采用顺序存储，便于进行插入和删除操作。C线性表采用链接存储，不必占用一片连续的存储单元。D线性表采用链接存储，便于插入和删除操作。47. 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ A ）存储方式最节省时间。A顺序表 B双链表 C带头结点的双循环链表 D单循环链表48某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ D ）存储方式最节省运算时间。A.单链表 B. 仅有头指针的单循环链表

17、 C. 双链表 D. 仅有尾指针的单循环链表49设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( A )最节省时间。A. 带头结点的双循环链表 B.单循环链表 C. 带尾指针的单循环链表 D. 单链表50若线性表最常用的操作是存取第I个元素及其前驱和后继元素的值，为节省时间应采用的存储方式( D )。A.单链表 B.双向链表 C.单循环链表 D.顺序表51静态链表中指针表示的是( C ) A.下一元素的地址 B.内存储器的地址C.下一元素在数组中的位置 D.左链或右链指向的元素的地址52在n个结点的线性表的数组实现中，算法的时间复杂性是O(1)的操作是( A )A.访问第i个结点(

18、1i=n)和求第i个结点的直接前驱(2i=n) B.在第i个结点后插入一个新结点(1i=n)C.删除第i个结点(1iright=s ; s-left=p; p-right-left=s ; s-right=p-right;Bp-right=s ; p-right-left=s ; s-left=p; s-right=p-right;Cs-left=p; s-right=p-right; p-right=s ; p-right-left=s ; ;Ds-left=p; s-right=p-right; p-right-left=s ; p-right=s ;57对于一个线性表既要求能够进行较快速

19、的插入和删除，又要求存储结构能反映数据之间的逻辑关系，则应该用(B )。A. 顺序存储方式 B. 链式存储方式 C. 散列存储方式 D. 以上均可以58在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（ B ）。Ap-next=s;s-next=p-next; B s-next=p-next;p-next=s;Cp-next=s;p-next=s-next; D p-next=s-next;p-next=s;59线性表的顺序存储结构是一种（ ）。A. 随机存取的存储结构 B. 顺序存取的存储结构C. 索引存取的存储结构 D. Hash存取的存储结构60顺序表是线性表的（B ）A、链

20、式存储结构 B、顺序存储结构 C、索引存储结构 D、散列存储结构61带头结点的单链表head为空的条件是（ B ）A、head=NULL B、head-next=NULL C、head-next=head D、head!=NULL62链表不具有的特点是（ B ） A插入、删除不需要移动元素 B可随机访问任一元素 C不必事先估计存储空间 D所需空间与线性长度成正比63若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ A ）存储方式最节省时间。A顺序表 B双链表 C带头结点的双循环链表 D单循环链表64下面关于线性表的叙述中，错误的是哪一个？（ B ）A线性表采用

21、顺序存储，必须占用一片连续的存储单元。B线性表采用顺序存储，便于进行插入和删除操作。C线性表采用链接存储，不必占用一片连续的存储单元。D线性表采用链接存储，便于插入和删除操作。二、填空题1设顺序线性表中有n个数据元素，则第i个位置上插入一个数据元素需要移动表中_个数据元素；删除第i个位置上的数据元素需要移动表中_个元素。n+1-i，n-i2. 设指针变量p指向双向循环链表中的结点X，则删除结点X需要执行的语句序列为_（设结点中的两个指针域分别为llink和rlink）。pllink-rlink=p-rlink; p-rlink-llink=p-rlink3设指针变量p指向单链表中结点A，则删除

22、结点A的语句序列为：q=p-next；p-data=q-data；p-next=_；feee(q)；q-next4在带头结点的单链表L中, 第一个元素所对应的结点的指针表达式是_。L-next5在双向循环链表中，在结点*之前插入结点*的语句序列是： S- prior = P- prior ; S-next=P; P-prior=S; _。S- prior-next=S;6在有n个元素的链队列中，入队和出队操作的时间复杂度分别为_O(1)_和_O(1)_。7在双链表中，存储一个结点有三个域，一个是数据域，另两个是指针域，分别指向_ _和_ 。前驱、后继8在循环队列中，存储空间为0n-1。设队头指

23、针front指向队头元素前一个空闲元素，队尾指针指向队尾元素，那么其队空标志为rear=front，队满标志为_ _。_(rear+1)%n=front9下面程序段的功能是利用从尾部插入的方法建立单链表的算法，请在下划线处填上正确的内容。typedef struct node int data; struct node *next; lklist; void lklistcreate(_ *&head ) for (i=1;idata);p-next=0;if(i=1)head=q=p;else q-next=p;_; lklist，q=p10设指针p指向单链表中结点A，指针s指向被插入的结点

24、X，则在结点A的前面插入结点X时的操作序列为：1) s-next=_；2) p-next=s；3) t=p-data；4) p-data=_；5) s-data=t；p-next，s-data11设指针变量p指向单链表中结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X需要执行的语句序列：s-next=p-next; _;。p-next=s12设指针变量head指向双向链表中的头结点，指针变量p指向双向链表中的第一个结点，则指针变量p和指针变量head之间的关系是p=_和head=_（设结点中的两个指针域分别为llink和rlink）。head-rlink，p-llink13设指

25、针变量p指向双向链表中的结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X的操作序列为_=p；s-right=p-right；_=s； p-right-left=s；（设结点中的两个指针域分别为left和right）。s-left=p，p-right14设指针变量p指向单链表中结点A，指针变量s指向被插入的新结点X，则进行插入操作的语句序列为_（设结点的指针域为next）。s-next=p-next; p-next=s15在一个单链表HL 中，若要向表头插入一个由指针p指向的结点，则应执行语句： 。p-next=HL; HL=p;16在采用独立结点构成的双向链表中，设p和q 分别

26、是具有Dnode * 类型的指针变量。若双向链表中p结点之后插入一个q结点，其操作步骤为： ； ； ； ；q-right=p-right; if (p-right) p-right-left=q; q-left=p;p-right=q;17对于一个顺序存储的线性表，在表头插入元素的时间复杂度为_,在表尾插入元素的时间复杂度为_。O(n) O(1)18在一个长度为n的顺序表中第i个元素（1in）之前插入一个元素时，需向后移动_n-i+1_个元素。19设双链表中结点的前趋指针和后继指针的域名分别为t1和r1，指针s指向双链表中的一个结点（该结点既非头结点，也非尾结点），则删除s指针所指向结点的操作

27、为“s-tl-r1=s-r1；”和“_s-rl-tl=s-tl_”。20设有指针head指向不带表头结点的单链表，用next表示结点的一个链域，指针p指向与链表中结点同类型的一个新结点。现要将指针p指向的结点插入表中，使之成为第一个结点，则所需的操作为“pnext=head；”和“_head=p_”。21单链表中逻辑上相邻的两个元素在物理位置上_不一定_相邻。22在一个长度为n的数组中删除第i个元素（1in）时，需要向前移动的元素的个数是_n-i_。23在顺序表上读表元算法的时间复杂度为_O（1）_。24双链表中前驱指针为prior，后继指针为next，在指针P所指结点前插入指针S所指的结点，需执行下列语