《计算机软件技术基础》复习题及答案.docx

计算机软件技术基础试题1 .线件表的错式存储结构与顺序存储结构相比优点是CD 。A,所有的操作算法实现简单B,便于随机存取C,便于插入和删除D,便于利用零散的存储器空间2 .线性表是具有n个 C的有限序列。A,表元素B,字符 C,数据元素D,数据项E.信息项3 .若长度为n的线性表采用顺序存储结构,在其第I个位置插入个 新元素的算法的时间复杂度为C 0 (IWIWn+l)A. 0(0)B. 0(1)C. 0(n)D. 0(n)4.设A是一个线性表(%,az,aj,采用顺序存储结构,则在等概率 的前提下,平均每插入个元素需要移动的元素个数为 B , 平均每删除个元素需要移动的元素个数为A ;若元素插在a1与aiH之间(0 I Wn-l)的概率为迎,则平均每插入一个元素所要移动的元素个数为C ;A.B.巴C 2 +1D 3" +13,45.下列函数中,按它们在” foo时的无穷大阶数,最大的是D A. logz?B. nlogz?C. 2n/2D. n!nextnextnext6 .将下图所示的s所指结点加到p所指的结点之后,其语句应为:D A. s->next=p+l; p->next=s;B. (*p). next=s; (*s).next= (*p). next;C. s->next=pnext; p->next=s->next;D. s->next=p->next; pnext=s;7 .将两个各有n个元素的有序表归并为个有序表时,其最少的比较 次数是A 。A. nB. 2n-lC. n-lD. 2n8.下面的程序段是合并两个无头结点链表(ha和hb)为个无头结点 链表ha的过程,作为参数的两个链表都是按结点的data域由大到小 链接的。合并后新链表的结点仍按此方式链接。请填写下述空框,使 程序能正确运行。ttdefine NULL 0typedef struct nodeint data;struct node *next;node, linklisttype;void combine(linklisttype *ha, linklisttype *hb)1 inklisttype *h, *p;h = (linklisttype *)malloc(sizeof(1 inklisttype);h->next = NULL;P = h;while(ha != NULL && hb != NULL)if (ha->data>=hb>data) /较大的元素先插入/p->next =(1);P = (2);(3) ;else p->next =(4)P = (5);(6) ;i f (ha=NULL)(7)if(hb=NULL)(8)ha = h->next;free (h);参考答案:（1） ha(2) p->next(3) ha=hanext(4) hb (5) p->next (6) hb=hb->next(7) p->next=hb(8) p->next=ha9.如果表A中所有元素,a?,a，与表B的个顺序子表 (bk, bk+bk+n-i)完全相同(即a1=bk, abk+i,an=b*则称表A包含 在表B中。设ha, hb为带头结点的单链表,分别表示有序表A和B, 下面的函数用于判别表A是否包含在表B中,若是,则返回true, 否则返回false。(提示:用递归实现)# define true 1# define false 0# define NULL 0 typedef struct node int data;struct node *next;node, linklisttype;int inclusion (linklisttype *ha, 1 inklisttype *hb) linklisttype *pa, *pb;pa = ha->next;pb = hb->next;while (2)if (pa->data=pb->data) (3)else(4);(5);参考答案:(1) if(pa=NULL) return(true)(2) pb!=NULL && padata>=pbdata(3) return(inclusion(pa, pb)(4) pb = pb->next;(5) return(false)10.在本题的程序中,函数createink一list (n)建立一个具有n个 结点的循环链表;函数josephus(n, 1, m)对由createinkist (n) 所建立的具有n个结点的循环链表按一定的次序逐个输出,并删除链 表中的所有结点。参数n(n0)指明循环链表的结点个数,参数1(1 1 n)指明起始结点,参数m (m是步长),指明从起始结点或前 次被删除并输出的结点之后的第m个结点作为本次被输出并删除的 结点。例如,对于下图所示的具有6个结点的循环链表,在调用 josephus(6,3,2)后,将输出5, 1,3,6, 4, 2请在空框处填上适当内 容,每框只填个语句。#define NULL 0 typedef struct nodeint data;struct node *next;node, linklisttype;linklisttype *create_link_list(int n)linklisttype *head, *p, *q;int I;head = NULL;if(n>0) head = (linklisttype *)malloc(sizeof(linklisttype);p 二 head;£共1=1;11;1+)/此循环用于建立一个链表,链表的 内容从1至nT*/p->data = I;q = (linklisttype *)malloc(sizeof(linklistttype);；(2);p->data = n;/建立从尾链到首的环形结构/return(head);void Josephus (int n, int j, int m) linklisttype *p, *q;int j;p = create_link_list(n);for (;I>1;!一) p = p->next;(4)；while(j<n) for (1=1; 1+) p = p->next;；printf ( "%8d” , q>data);(6);free(q);j=j+l；)参考答案:(1) p->next = q;(2) p = q；(3) p->next = head(4) j=0(5) q=pnext;(6) p->next = q->next11.在下列程序中,函数difference (A, B)用于求两集合之差C=A-B, 即当且仅当e是A中的个元素,且不是B中的元素时,e是C中的 个元素。集合用有序链表实现,用个空链表表示个空集合,表 示非空集合的链表根据元素之值按递增排列,执行C=A-B之后,表示 集合A和B的链表不变,若结果集合C非空,则表示它的链表应根据 元素之值按递增序排列。函数append。用于在链表中添加结点。ttinclude <stdio. h>ttdefine NULL 0typedef struct nodeint data;struct node *next;N0DE;NODE *append(NODE *last, int x)last->next=(NODE *)malloc(sizeof(NODE);last->next->data=x;return (last->next);NODE *difference(NODE *A , NODE *B)NODE *C, *last;C=last=(NODE *)malloc(sizeof(NODE);while (0)if (A->data < B->data)last=append(last, Adata);A=A->next;)elseif( )A=Anext;B=B->next;else ；while(4) last=append(last, A->data);A=A->next;)(5);last二C;C=C->next;free (last);return (C);)参考答案:(1) A!=NULL & B!=NULL(2) A->data-B->data(3) B=B->next;(4) A!=NULL(5) last->next=NULL;12.阅读以下算法,填充空格,使其成为完整的算法。其功能是在 个非递减的顺序存储线性表中(从下标1处开始存储),删除所有值相 等的多余元素。ttdefine MAXSIZE 30typedef structint elemMAXSIZE;int length;/表长/sqlisttype;void exam21(sqlisttype *L) int i, j;i=l, j=2;while(Q) if(L->elemi!=L->elemj)if(j! = (i+D)；L->length=L->length-(j-i-l);(3) ;else(4) ;if(j>L->length) (5)参考答案:(1) j<=L->length(2) for(intk=j;k=Llength;k+)L->elemk-(j-i-l)=L->elemk;(3) i+,j=i+l;(4) j+;(5)L->length=L->length-(j-i-1); break;13 .用单链表表示的链式队列的队头在妬表的A 位置。A.链头 B.链尾 C.链中14 .若用单链表表示队列,则应该选用B 。A.带尾指针的非循环链表B.带尾指针的循环链表C.带头指针的非循环链表D.带头指针的循环链表15 .在解决计算机主机与打印机之间速度不匹配问题时,通常设置 个打印数据缓冲区,主机将要输出的数据依次写入该缓冲区,而打印 机则从该缓冲区中取出数据打印,先放入打印缓冲区的数据先被打 印。该缓冲区应该是个B结构。A.堆栈B.队列C.数组D.线性表16 .若用个大小为6的数组来实现循环队列,且当前rear和front 的值分别为。和3。当从队列中删除个元素,再加入两个元素后, rear和front的值分别为 B A. 1 5B. 2 和 4C. 4 2D. 5 和 117 .设栈的输入序列为!, 2,，10,输出序列为ab a21 aI0,若a5=10, 则a7为 C 0A. 4B. 8 C.不确定 D. 718 .设栈的输入序列是1,2, 3, 4,则 D不可能是其出栈序列。A. 1243 B. 2134 C. 1432D. 431219 .以下 D是C语言中" abcd321ABCD”的子串。A. abedB. 321AB C. “abcABC" D. “21 AB”20 .若串S=" software”,其子串的数目是C 。A. 8B. 37 C. 36D. 921 .将一个Al:100, 1:100的三对角矩阵,按行优先存入维数组B1:298中,A中元素A66, 65（即该元素的下标）在B数组中位置k为B A. 198B. 195C. 197D. 19622.设高为h的叉树只有度为0和2的结点,则此类叉树的结点 数至少为B ,至多为 F 。高为h的完全叉树的结点数至少为E ,至多为 F 。A. 2hB. 2h-l C. 2h+lD. h+1E. 2hHF. 2-1G. 2h+1-lH. 2h+l23. 棵有124个叶结点的完全叉树,最多有B 个结点。A. 247B. 248C. 249D. 25124 .若从叉树的任一结点出发到根的路径上所经过的结点序列按其 关键字有序,则该叉树是C 。A.满叉树B.哈夫曼树C.堆D.叉查找树25 .前序遍历和中序遍历结果相同的叉树为F;前序遍历和后序遍历结果相同的叉树为B 。A, 一般叉树B.只有根结点的叉树C.根结点无左孩子的叉树D,根结点无右孩子的叉树E,所有结点只有左孩子的叉树F.所有结点只有右孩子的二叉树26 .具有n个结点的完全叉树,已经顺序存储在维数组Al. n 中,下面的算法是将A中顺序存储变为叉链表存储的完全叉树。 请填写适当语句在下面的空格内,完成上述算法。#define MAXSIZE 30typedef struct btnodeint data;struct btnode *lchild, *rchild;BTN;void createtree(BTN *p, int A,int I, int n) ；p->data=AI;if( (2) ；elseplchild=NULL;if(4)createtree (5);elsep->rchild=NULL;)void btree(BTN * p , int A, int n) createtree (p, A, 1, n);)参考答案:(1) p=(BTN *)malloc(sizeof(BTN)(2) 2*1 =n(3) createtree(p->lchild, A, 2*1, n)(4) 2*1+1=n(5) p->rchild, A, 2*1+1, n27 .若在线性表中采用折半查找法查找元素,该线性表应该C 0A.元素按值有序B.采用顺序存储结构C.元素按值有序,且采用顺序存储结构D,元素按值有序,且采用 链式存储结构28 .在分块检索中,对256个元素的线性表分成16 块最好,每块的最佳长度是16;若每块的长度为8,其平均检索长度为21 29.假定有K个关键字互为同义词,若用线性探测法把这K个关键字 存入散列表中,至少要进行D次探测。A. K-1 次B. K 次C. K+1 次D. K(K+l)/2 次30 .在n个记录的有序顺序表中进行折半查找,最大的比较次数是 |_log2nj+l 31 . Hash技术广泛应用于查找过程,选择Hash函数的标准是 和。处理冲突的技术有优有劣,其共同标准 是 32 .在下述排序算法中,所需辅助存储空间最多的是B ,所需辅助存储空间最小的是C ,平均速度最快的是A 0A.快速排序B.归并排序C.堆排序33 .在文件局部有序或文件长度较小的情况下,最佳内部排序的方法 是 A 。A,直接插入排序B.冒泡排序C,简单选择排序34 .快速排序在最坏情况下时间复杂度是0(/),比A 的性能差。A.堆排序B.冒泡排序C.简单选择排35 .若需在。(nlogn)的时间内完成对数组的排序,且要求排序是稳定的,则可选择的排序方法是c 。A.快速排序B.堆排序C.归并排序D.希尔排序36 .如果只想得到1000个元素组成的序列中第5个最小元素之前的部 分排序的序列,用B方法最快A,冒泡排序B.快速排序E.简单C.希尔排序D.堆排序选择排序37 .以下结点序列是堆的为A 。A. 100, 90, 80, 60, 85, 75, 20, 25, 10, 70, 65, 50B. 100, 70, 50, 20, 90, 75, 60, 25, 10, 85, 65, 8038 .若要尽可能快地完成对实数数组的排序,且要求排序是稳定的, 则应选,C .A.快速排序B.堆排序C.归并排序D.希尔排序39 .从未排序序列中依次取出个元素与已排序序列中的元素依次进 行比较,然后将其放在已排序序列的合适位置,该排序方法称为 A 排序法。A.插入排序B,交换排序C.选择排序D,归并排序40 .直接插入排序在最好情况下的时间复杂度为B .A. O(logn)B. 0(n)C. O(nlogn)D. 0(n2)41.下面函数是将任意序列调整为最大堆的算法,请将空白部分填上:将任意序列调整为最大堆通过不断调用adjust函数,即for(i=n/2;i>0;i-) adjust(list, i, n);其中list为待调整序列所在数组(从下标1开始)，n为序列元素的 个数。void adjust(int list, int root, int n)/将以root为下标的对应元素作为待调整堆的根,待调整元素放在 list数组中,最大元素下标为n*/int child, rootkey;rootkey =(1);child = 2*root;while(child < n)if(child<n) && (listchild<listchild+1) ；if (rootkey > listEchild)break;else list(3)=listchild;(4);list (5)=rootkey;)参考答案:(1) listroot(2) child+;(3) child/2(4) child *= 2;(5) child/241 .表是一种数据结构,链表是种 。队列和栈都是线性表,栈的操作特性是 (2),队列的操作特性是(3)今有一空栈S,对下列待进栈的数据元素序列a, b,c, d, e, f依次进栈、进栈、出栈、进栈、栈S的栈顶元素为(4)供选答案:(1)： A.非顺序存储线性表表C.顺序存储线性表(2): A.随机进出C,先进先出(3): A.随机进出进栈、出栈的操作,则此操作完成后,栈底元素为(5)。B.非顺序存储非线性D.顺序存储非线性表B,先进后出D,出优于进B,先进后出C.后进后出D.进优于出(4): A. fB. cC. aD. b(5): A. bB. cC. aD. d答案:ABCBC42 .操作系统主要是对计算机系统全部（1）进行管理,以方便用户、提高计算机使用效率的种系统软件。它的主要功能有:处理机管理、存储管理、文件管理、（2） 管理和设备管理等。Windows和Unix是最常用的两类操作系统。前者是个具有图形界 面的窗口式的（3） 系统软件,后者是一个基本上采用（4）语言编制而成的的系统软件。在（5）操作系统控制下,计算机能及时处理由过程控制反馈的信息并作出响应。供选答案:(1)：A.应用软件B.系统软硬件C.资源D.设备(2):A.数据B.作业C.中断D.。(3):A.分时B.多任务C.多用户D.实时(4):A.PASCALB.宏C.汇编D.C(5): A.网络B,分时C.批处理D,实时答案:CBBDD43,本程序从键盘读入整数,并按从大到小的顺序输出输入整数中互 不相等的那些整数。程序边读入整数,边构造个从大到小顺序链接的链表,直 至不能从键盘读入整数,然后顺序输出链表上各表元的整数值。主函 数每读入个整数，就调用函数insert (),函数insert ()将还未出 现在链表上的整数按从大到小的顺序插入到链表中。为了插入方便,链表在表首有一个辅助表元。阅读下列C代码,在 (n)处填入相应的字句以完成上述功能。ttinclude <stdio.h>#include <malloc. h>#define NULL 0typedef struct nodeint val;struct node *next;N0DE;void insert(NODE *list, int x) NODE *u, *v, *p;list; vu->next;while(1) && x < v->val) /寻找插入位置*/u=v;v=unext;)if(v-NULL |)/判断是否要插入表元/p = (NODE *)malloc (si zeof(NODE);p->val = x;/生成新表元/(3)= v; (4) = p; /*插入新表元/main() int x;NODE *head, *p;/首先建立只有辅助表元的空链表/head = (NODE *)malloc(sizeof(NODE);(5);NULL;printf( "Enter Integers:;while(scanf( "%d,? ,&x) = 1)/*反复读入整数插入链表/insert(head, x);for (p=head->next ;p!=NULL;p=p>next)/ 输出链表/printf( "%dt" , pval);printf( "n");)答案:(1) v != NULL 或 v(2) x > v->val 或 x != v->val(3) p->next(4) u->next(5) head-next44.计算机数据处理的对象是具有不同结构的各种数据,可以访问的 最小数据信息单位是,可以引用的最小命名数据单位是.(2).线性表是最简单的种数据结构,有顺序和链接两种存储方式。线性表按链接方式存储时,每个结点的包括(3)两部分。线性表的杳找有 (4) 和 (5)两种,但(5)只能用于顺序存储的情况。供选答案:(1):A.数字B,字符C.数据元素D.数据项(2):A.结点B.记录C.数据元素D.数据项(3):A.数据值与符号B.数据与指针C.数据与表名D.头地址与尾地址(4):A.随机查找B.顺序查找C.二分法查找D.浏览(5):A.随机查找B.顺序查找答案:C.二分法查找CDBBCD.浏览45.本程序用于从链盘读入整数, 数。插入到链表,或从链表删除个整阅读下面的C代码,将应填入(n)处的字名写在答卷的对应栏内。ttinclude <stdio.h>#include <malloc. h>typedef struct nodeint val;struct node * next;N0DE;NODE * ins (NODE *list, int x) /将x按从小到大的次序插入链表/NODE *u, *v=list, *p;for (; v != NULL && x < v->val ; v = v->next) ;/寻找插入位 置/if (v != NULL && x = v->val) return (list) ;/ 已有,被忽略/p = (NODE *)malloc(sizeof (NODE) ;p->val=x; /生成新表元/if(v = list) list = p;else (1); ；return list;)NODE * del (NODE * list, int x) /从链表中删除值为x的表元*/NODE *u, *v;for(v = list; v != NULL && x < v->valu; u=v;v=vnext);if (v != NULL && x = v->val) /找到值为 x 的表元/if (v = list) list = list->next;else (3);(4);/释放空间*/else printf ("没有找到!、n");return(list);main () int x, ans;NODE * list-NULL, *p;while(1)printf ( "n输入1:将整数插入到链表。n输入2:从链表 删除个整数。n");printf ("其它整数,结束程序。'nt请输入选择! ”)；scanf (%d, &ans);if (5) return;printf ("输入整数:");scanf ( "%d" , &x);if(ans=l) list=ins(list, x);else list=del (list,x);for(p=list;p!=NULL;p=p->next)printf ( "%4d” ,p->val);)答案:(1) u->next = p;(2) p->next = v(3) u->next = v->next(4) free (v)(5) ans != 1 && ans != 246 .从未排序的序列中,依次取出元素,与已排序序列的元素比较后, 放入已排序序列中的恰当位置上,这是 排序。从未排序的序列中,挑选出元素,放在已排序序列的某一端位置,这是 (2)排序。逐次将待排序的序列中的相邻元素两两比较,凡是逆 序则进行交换,这是 排序。如果整个排序过程都在内存中进行,称为排序。排序算法的复杂性与排序算法的(51有关。供选答案:(1):A.选择B.插入C.比较D.归并(2):A.选择B.插入C.比较D.归并(3):A.冒泡B.交换C.比较D.散列(4):A.外部B.内部C.外存D.内存(5): A.运算量大小与占用存储多少B,运算量大小与处理的数据量大小C.并行处理能力和占用存储多少D.占用存储多少和处理的数据量大小答案:BAABA47 .操作系统是对计算机资源进行的(1) 系统软件,是(2)的接口。在处理机管理中,进程是个重要的概念,它由程序块、 和数据块三部分组成,它有3种基本状态,不可能发生的状态转换是 (4)虚拟存储器的作用是允许程序直接访问比内存更大的地址空间它通常使用(5)作为它的个主要组成部分。供选答案:(1) ： A.输入和输出C,管理和控制(2): A.软件和硬件C.高级语言和机器语言(3): A.进程控制块C.文件控制块(4) : A.运行态转换为就绪态C.运行态转换为等待态(5): A.软盘B.键盘操作D.汇编和执行B,主机和外设D,用户和计算机B,作业控制块D.设备控制块B,就绪态转换为运行态D.等待态转换为运行态B.硬盘C. CDROMD.寄存器 答案:CDADB48. A是信息的载体,它能够被计算机识别、存储和加工处理。A,数据B,数据元素C.结点D.数据项 49.下列程序段的时间复杂度为C .for (i=l;i<n;i+)y=y+l;forCj=O;j<=(2*n);j+)x+;供选答案:A. O(n-l)B, 0(2n) C. 0(n2) D. 0(2n+l)50 .下面程序段的时间复杂度为D 。i=l； while(i<=n) i=i*2; 供选答案:A. 0(1)B. 0(n)C. 0(n2) D. 0(log2n)51 .下面程序段的时间复杂度为B .a=0;b=l; for (i=2;i<=n;i+) s=a+b; b=a;供选答案:A. 0(1)B. 0(n)C. 0(log2n) D.0(n2)52 .数据结构是门研究非数值计算的程序设计问题中,计算机的A 以及它们之间的关系和运算等的学科。A.操作对象B.计算方法 C.逻辑存储D.数据映象53 .在数据结构中,从逻辑上可以把数据结构分成C 。A.动态结构和静态结构B.紧凑结构和非紧凑结构C.线性结构和非线性结构D,内部结构和外部结构54 .算法分析的目的是 C .A.找出数据结构的合理性B.研究算法中输入和输出的关系C,分析算法的效率以求改进D,分析算法的易懂性和文档性55 .算法分析的两个主要方面是(4).A.间复杂性和时间复杂性B.正确性和简明性C.可读性和文档性D.数据复杂性和程序复杂性56 .个线性顺序表第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的地址为 B 0A. 110B. 108C. 100D.12057 .若已知一个栈的入栈序列是1,2,3,n,其输出序列为P2,P3,若P尸n,则P,为 C 0A. iB. n-iC. n-i+1D.不确定58 .对于个栈,给出输入项A,B,C。如果输入项序列由A, B,C所组成,则不可能产生的输出序列是A .A. CABB. CBAC. ABCD.ACB59 .设有如下的单链表的按序号查找的算法,其时间复杂度为B LinkNode *GetNode(Linklist head, int i)int j;ListNode *p;P = head; j=0;while(p->next && j<i)p = p->next;j+；if (i=j)return(p);elsereturn(NULL);供选答案:A. 0(n2)B. 0(2n) C. 0(n3)D.O(logn)60 .二维数组灯按行序为主顺序存放在内存中,每个数组元素占1个 存储单元,则元素配的地址计算公式是C 。A. LOC(aij) = LOC(aH)+ (i-l)*m+(j-l)B. L0C(aQ = LOC(aC + (j-l)*m+(iDC. LOC(aij) = LOC(ail) + (i-l)*n+(j-l)D. L0C(aQ = LOC(ail) + (j-l)*n+(i-l)61 .以下哪个不是队列的基本运算C 。A.从队尾插入一个新元素B,从队列中删除第i个元素C.判断个队列是否为空D.读取队头元素的值62 .在一个长度为n的顺序表中,向第i个元素之前插入个新元素, 需向后移动B 个元素。A. n-iB. n-i+1 C. n-i-1 D. i63 .从个长度为n的顺序表中删除第i个元素时,需向前移动A 个元素。A. n-iB. n-i+1 C. n-i-1 D. i64 .在具有n个单元的顺序存储的循环队列中,假定front和rear分 别为队首指针和队尾指针,则判断队空的条件是 B 0A. front=rear+lB. front=rearC. front+l=rearD. front=065 .从一个具有n个结点的单链表中查找其值等于x的结点时,在查 找成功的情况下,需平均比较D个结点。A. nB. n/2C. (n-l)/2 D.(n+l)/266 .个栈的入栈序列是a,b,c,d,e,则栈不可能的输出序列是C 0A. edcba B. decba C. dceab D. abcde67 .栈结构通常采用的两种存储结构是A 。A.顺序存储结构和链表存储结构B.散列方式和索引方式C.链表存储结构和数组D.线性存储结构和非线性存储结构68,判断一个顺序栈ST(最多元素为mo)为空的条件是一B 0A. ST->top<>0 B. ST->top=0 C. st->top<>mo D. st->top=mo69 .不带头结点的单链表head为空表的判定条件是.A 。A. headNILL B. head->next=NULL C. headnext=head D. head != NULL70 .在个单链表中,已知q所指结点是p所指结点的前驱结点,若 在P和q之间插入s结点,则应执行C 。A. s->next = p->next; pnext=s;B. p->next = s->next; s->next=p;C. q->next = s; s->next=p;D. p->next = s; snext=q;71 .假设双向链表结点的类型如下:typedef struct Linknodeint data;struct Linknode *lLink;/前驱结点指针/struct Linknode *rLink;/后继结点指针/)下面给出的算法是要把个q所指新结点,作为非空双向链表中的p 所指的结点前驱结点插入到该双向链表中,能正确完成要求的算法段 是 C .A . q->rLink=p; q->lLink=p->lLink; p->lLink-q; p->lLink->rLink=q;B. p-lLink=q, q->rLink=p; p->lLink->rLink=q; q->lLink=p->lLink;C. q->lLink=p->lLink;q->rLink=p; p-> 1L i nk->rL i nk=q; p!.Li