顺序表链表题库

第三章 顺序表一、填空1若线性表最常用的操作是存取第 i 个元素及其前驱元素的值，则采用（ ）存储结构最节省运算时间。2顺序存储结构的线性表中所有元素的地址（ ）连续。 3顺序存储结构的线性表其物理结构与逻辑结构是（ ）的。4在具有n个元素的顺序存储结构的线性表任意一个位置中插入一个元素，在等概率条件下，平均需要移动（ ）个元素。5在具有n个元素的顺序存储结构的线性表任意一个位置中删除一个元素，在等概率条件下，平均需要移动（ ）个元素。6在具有n个元素的顺序存储结构的线性表中查找某个元素，平均需要比较（ ）次。7当线性表的元素基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中第i个元素时，应采用( )存储结构。8顺序存储结构的线性表中，插入或删除某个元素时，元素移动的次数与其位置（ ）关。（填有或无）。9顺序存储结构的线性表中，访问第i个元素与其位置（ ）关。（填有或无）。10在具有n个元素的顺序存储结构的线性表中要访问第i个元素的时间复杂度是（ ）。11在顺序表L中的i个位置插入某个元素x，正常插入时，i位置以及i位置以后的元素需要后移，首先后移的是（ ）个元素。12要删除顺序表L中的i位置的元素x，正常删除时，i位置以后的元素需要前移，首先前移的是（ ）元素。13若顺序表中的元素是从1位置开始存放的，要在具有n个元素的顺序表中插入一个元素，合法的插入位置是（ ）。14若顺序表中的元素是从1位置开始存放的，要删除具有n个元素的顺序表中某个元素，合法的删除位置是（ ）。15在具有n个元素的顺序存储结构的线性表中删除某个元素的时间复杂度是（ ）。16在具有n个元素的顺序存储结构的线性表中插入某个元素的时间复杂度是（ ）。17在具有n个元素的顺序存储结构的线性表中要访问第i个元素的后继结点的时间复杂度是（ ）。18在具有n个元素的顺序存储结构的线性表中，若给定的是某个元素的关键字值，要访问该元素的其它信息的时间复杂度是（ ）。19在顺序表中查找某个元素时，需要将当前元素与要找的元素进行若干次的比较，算法经常用while循环来实现，while里面的条件是没找完且（ ）。20在顺序表中查找某个元素时，需要将当前元素与要找的元素进行若干次的比较，算法经常用while循环来实现，while里面的条件是（ ）且没找到。21如果要将两个升序排列的整型顺序表a中的元素合并到b中（b的空间足够大），合并后表中元素依然升序排列，可以通过多次调用查找函数查找插入位置，再调用（ ）函数来实现插入。22若要将一个整型的顺序表拆分为一个存放正数，另一个存放非正数的两个顺序表，存放正数的顺序表用原来的表，时间复杂度为（ ）。23顺序表中查找某个元素时，从前到后查找与从后到前查找的时间复杂度（ ）同。二、简答题1.下列算法完成在顺序表SeqL的第i个位置插入元素x，正常插入返回1，否则返回0或-1，请在空的下划线上填写合适的内容完成该算法。/表中最多可以放置MAXLEN个元素int seq_ins(SeqList *SeqL,int i, DataType x) int j; if ( ) /*表满*/ printf(the list is fulln); return 0; else if (i SeqL-len+1) /*位置不对*/ printf(the position is invalidn ); return -1; else /*正常插入*/ for (j=SeqL-len;j=i;j-) /*元素后移*/ /*插入元素*/ (SeqL-len)+; /*表长加1*/ 2.下列算法完成删除顺序表SeqL的第i个元素，元素类型为DataType，其值通过参数px返回，请在空的下划线上填写合适的内容完成该算法。 int seq_del (SeqList * SeqL,int i， ) int j ; if （SeqL-len=0) /*表空*/ printf(the list is emptyn);return 0; elseif( ) /*位置不对*/ printf(n the position is invalid); return -1; else /*正常删除*/ *px=SeqL-datai; /*删除元素通过参数px 返回*/ for (j=i+1;jlen;j+) ; /*元素前移*/ ; /*表长减1*/ return 1; 3.简述什么是顺序存储结构，顺序存储结构的优缺点都有哪些。4. 设有一整型顺序表L，元素从位置1开始存放，下列算法实现将以第一个元素为基准，将其放置在表中合适的位置，使得其前面的元素都比它小，后面的元素均大于等于该元素。请在空的下划线上填写合适的内容完成该算法。void part(SeqList *L) ; /*循环变量声明*/ int x; ; /*将第一个元素置入x中*/ for(i=2;ilen;i+) if( ) /*当前元素小于基准元素*/ L-data0=L-datai; /*当前元素暂存在0位置*/ for(j=i-1;j=1;j-) /*当前元素前面所有元素后移*/ L-dataj+1=L-dataj; /*当前元素从0位置移到最前面*/ 5. 设有一整型顺序表L，元素从位置1开始存放，下列算法实现将以第一个元素为基准，将其放置在表中合适的位置，使得其前面的元素都比它小，后面的元素均大于等于该元素。请在空的下划线上填写合适的内容完成该算法。void part(SeqList *L) int i,j; i=1; /*i指向第一个位置*/j=L-len; /*j指向最后一个位置*/ L-data0= L-data 1; /*将基准元素暂存在0位置*/ while( ) while(L-data j= L-data 0)&(ij) j-; /*j位置元素大于基准元素且ij 时j前移*/ if (idata i= L-data j;i+; while(L-data idata 0)&(ij) i+;/*i位置元素小于基准元素且ij 时i后移*/ if (inext=HL-next及( )操作。14设指针变量p指向单链表中某结点A，则删除结点A的后继结点需要的操作为（ ）（不考虑存储空间的释放）。15在单链表中，若给定某个结点的指针，要删除该结点的后继结点的时间复杂度为（ ）。16统计单链表中元素个数的时间复杂度是（ ）。17要访问具有n个结点的单链表中任意一个结点的时间复杂度是（ ）。18链式存储结构的线性表中，插入或删除某个元素所需的时间与其位置（ ）关。（填有或无）。19在单链表中，若给定某个结点的数据信息，要删除该结点的后继结点的时间复杂度为（ ）。20若指针p,q的值相同，则*p和*q的值（ ）相同。21若要将一个单链表中的元素倒置，可以借助（ ）建立单链表的思想将链表中的结点重新放置。22线性表用链式存储结构存储比用顺序存储结构存储所占的存储空间（ ）多。（填一定或不一定）二、简答题1下列算法完成用头插法为数组a中的n个元素建立一个带头结点的单链表，并返回其头指针，请在空的下划线上填写合适的内容完成该算法。NodeType* creatl2 (DataType a,int n) NodeType*head, *s； int i；head=(NodeType*)malloc(sizeof(NodeType)； /*为头结点申请空间*/if (head=NULL) return NULL; ; /*链表初始化为空*/ for (i=1；inext=head-next； /*新结点的指针域指向头的下一个元素*/ ; /*头结点指向新结点*/ ; /*返回头指针*/ 2.下列算法完成用尾接法为数组a中的n个元素建立一个带头结点的单链表，并返回其头指针，请在空的下划线上填写合适的内容完成该算法。NodeType* creatl1(DataType a,int n) NodeType *head,*tail,*s; /* head为头指针， tail为尾指针*/ int i; head=initl( ); /*链表初始化*/ if (head=NULL) return NULL; ; /*尾指针初始化为头指针*/ for (i=0;inext=NULL; / *给新结点的指针域赋值*/ tail-next=s; /*将新结点接到表尾*/ ; /*新结点为当前的表尾*/ return head; /*返回头指针*/ 3. 简述什么是链式存储结构，链式存储结构的优缺点有哪些。4. 请解释：结点，头结点，头指针，首元结点。5. 已知整型带头结点的单链表H，下列算法实现将该链表中的元素倒置，若原链表中的元素为1，2，3，4，5； 倒置后在则变成5，4，3，2，1. 请在空的下划线上填写合适的内容完成该算法。void reverse ( ) NodeType*p; p=H- next; /*p指向首元结点*/ H-next=NULL; /*头结点的指针域为空*/ while( ) /*当p结点不为空时*/ q=p; p=p-next; /*p指针后移*/ /*将q所指向的结点插入到头结点之后*/ 三、算法设计1.设单链表的结点类型定义如下：typedef struct node int data； struct node *next；NodeType；设计一算法在带头结点的单链表L中查找元素x，若找到，则返回其位置；否则返回一个空位置。2.设单链表的结点类型定义如下：typedef struct node int data； struct node *next；NodeType；设计一算法查找带头结点的单链表L中第i个元素，若找到，则返回其位置；否则返回一个空位置。3.设单链表的结点类型定义如下：typedef struct node int data； struct node *next；NodeType；设计一算法求带头结点的单链表L的长度。4.设单链表的结点类型定义如下：typedef struct node int data； struct node *next；NodeType；设计一算法统计带头结点的单链表L中元素x的个数。5.设单链表的结点类型定义如下：typedef struct node int data； struct node *next；NodeType；设计一算法在带头结点的单链表L中查找元素x的前驱结点，若找到，则返回其位置；否则返回一个空位置。6.设单链表的结点类型定义如下：typedef struct node int data； struct node *next；NodeType；设计一算法在带头结点的单链表L中，将新元素x插入到带头结点的单链表L中的元素elm之后，若不存在元素elm，则插入到最后。7.设单链表的结点类型定义如下：typedef struct node int data； struct node *next；NodeType；设计一算法删除带头结点的单链表L中的元素x（元素x只有一个）。8.设单链表的结点类型定义如下：typedef struct node int data； struct node *next；NodeType；设计一算法删除带头结点的单链表L中所有的元素x(元素x可能有多个)。9. 设有一整型的带头结点的单链表，其元素值升序排列，请定义结点的类型并设计一算法实现：任意给定一个元素x将其插入到该表中，使得该链表中的数据依然有序。10. 已知一带头结点的单链表L，结点类型为： typedef struct nodeint data;struct node *next;nodetype;设计一算法，求该链表中值最大的结点并返回该结点的指针，若链表为空，则返回一个空指针。11. 已知一带头结点的单链表L，结点类型为： typedef struct nodeint data;struct node *next;nodetype;设计一算法，求该链表中所有元素的平均值并返回。