《顺序表、链表试题库.pdf》由会员分享，可在线阅读，更多相关《顺序表、链表试题库.pdf（14页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、.-第三章 顺序表一、填空1若线性表最常用的操作是存取第 i 个元素及其前驱元素的值，则采用（）存储结构最节省运算时间。2顺序存储结构的线性表中所有元素的地址（）连续。3顺序存储结构的线性表其物理结构与逻辑结构是（）的。4在具有 n 个元素的顺序存储结构的线性表任意一个位置中插入一个元素，在等概率条件下，平均需要移动（）个元素。5在具有 n 个元素的顺序存储结构的线性表任意一个位置中删除一个元素，在等概率条件下，平均需要移动（）个元素。6在具有 n 个元素的顺序存储结构的线性表中查找某个元素，平均需要比较（）次。7当线性表的元素基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中
2、第 i 个元素时，应采用()存储结构。8顺序存储结构的线性表中，插入或删除某个元素时，元素移动的次数与其位置（）关。（填有或无）。9顺序存储结构的线性表中，访问第i 个元素与其位置（）关。（填有或无）。10 在具有 n 个元素的顺序存储结构的线性表中要访问第i 个元素的时间复杂度是（）。11在顺序表 L 中的 i 个位置插入某个元素 x，正常插入时，i 位置以及 i 位置以后的元素需要后移，首先后移的是（）个元素。12要删除顺序表L 中的 i 位置的元素 x，正常删除时，i 位置以后的元素需要前移，首先前移的是（）元素。13 若顺序表中的元素是从1 位置开始存放的，要在具有 n 个元素的顺序表
3、中插入一个元素，合法的插入位置是（）。14若顺序表中的元素是从1 位置开始存放的，要删除具有n 个元素的顺序表中某个元素，合法的删除位置是（）。15在具有 n 个元素的顺序存储结构的线性表中删除某个元素的时间复杂度是（）。16在具有 n 个元素的顺序存储结构的线性表中插入某个元素的时间复杂度是（）。17在具有 n 个元素的顺序存储结构的线性表中要访问第i 个元素的后继结点的时间复杂度是（）。18在具有 n 个元素的顺序存储结构的线性表中，若给定的是某个元素的关键字值，要访问该元素的其它信息的时间复杂度是（）。19在顺序表中查找某个元素时，需要将当前元素与要找的元素进行若干次的比较，算法经常用
4、while 循环来实现，while 里面的条件是没找完且（）。20在顺序表中查找某个元素时，需要将当前元素与要找的元素进行若干次的比较，算法经常用 while 循环来实现，while 里面的条件是（）且没找到。21如果要将两个升序排列的整型顺序表 a 中的元素合并到 b 中（b 的空间足够大），合并后表中元素依然升序排列，可以通过多次调用查找函数查找插入位置，再调用（）函数来实现插入。22若要将一个整型的顺序表拆分为一个存放正数，另一个存放非正数的两个顺序表，存放正数的顺序表用原来的表，时间复杂度为（）。23顺序表中查找某个元素时，从前到后查找与从后到前查找的时间复杂度（）同。二、简答题1.下
5、列算法完成在顺序表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-)/*元素后移
6、*/*插入元素*/(SeqL-len)+;/*表长加 1*/2.下列算法完成删除顺序表 SeqL 的第 i 个元素，元素类型为 DataType，其值通过参数 px 返回，请在空的下划线上填写合适的容完成该算法。intseq_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 返
7、回*/for(j=i+1;jlen;j+);/*元素前移*/;/*表长减 1*/return 1;3.简述什么是顺序存储结构，顺序存储结构的优缺点都有哪些。4.设有一整型顺序表 L，元素从位置 1 开始存放，下列算法实现将以第一个元素为基准，将其放置在表中合适的位置，使得其前面的元素都比它小，后面的元素均大于等于该元素。请在空的下划线上填写合适的容完成该算法。void part(SeqList*L);/*循环变量声明*/.可修编-.-intx;/*将第一个元素置入 x 中*/for(i=2;ilen;i+)if()/*当前元素小于基准元素*/L-data0=L-datai;/*当前元素暂存在
8、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-dataj
9、=L-data 0)&(ij)j-;/*j位置元素大于基准元素且ij 时 j 前移*/if(idata i=L-data j;i+;while(L-dataidata0)&(ij)i+;/*i位置元素小于基准元素且ij 时 i 后移*/if(inext=HL-next 及()操作。14 设指针变量 p 指向单链表中某结点A，则删除结点 A 的后继结点需要的操作为（）（不考虑存储空间的释放）。15 在单链表中，若给定某个结点的指针，要删除该结点的后继结点的时间复杂度为（）。16统计单链表中元素个数的时间复杂度是（）。17要访问具有 n 个结点的单链表中任意一个结点的时间复杂度是（）。18链式存储
10、结构的线性表中，插入或删除某个元素所需的时间与其位置（）关。（填有或无）。19在单链表中，若给定某个结点的数据信息，要删除该结点的后继结点的时间复杂度为（）。20若指针 p,q 的值相同，则*p 和*q 的值（）相同。21若要将一个单链表中的元素倒置，可以借助（）建立单链表的思想将链表中的结点重新放置。22线性表用链式存储结构存储比用顺序存储结构存储所占的存储空间（）多。（填一定或不一定）二、简答题1下列算法完成用头插法为数组 a 中的 n 个元素建立一个带头结点的单链表，并返回其头指针，请在空的下划线上填写合适的容完成该算法。.可修编-.-NodeType*creatl2(DataType
11、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,
12、*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；倒置后在则
13、变成 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 nodeintdata；struct node*next；NodeType；设计一算法在带头结点的单链表L 中查找元素 x，若找到，则返回其位置；否则返回一个空位置。2.设单
14、链表的结点类型定义如下：typedef struct nodeintdata；struct node*next；NodeType；设计一算法查找带头结点的单链表L 中第 i 个元素，若找到，则返回其位置；否则返回一个空位置。3.设单链表的结点类型定义如下：typedef struct nodeint data；struct node*next；NodeType；设计一算法求带头结点的单链表L 的长度。4.设单链表的结点类型定义如下：typedef struct nodeint data；struct node*next；NodeType；设计一算法统计带头结点的单链表L 中元素 x 的个数。.
15、可修编-.-5.设单链表的结点类型定义如下：typedef struct nodeintdata；struct node*next；NodeType；设计一算法在带头结点的单链表L 中查找元素 x 的前驱结点，若找到，则返回其位置；否则返回一个空位置。6.设单链表的结点类型定义如下：typedef struct nodeint data；struct node*next；NodeType；设计一算法在带头结点的单链表L 中，将新元素x 插入到带头结点的单链表L 中的元素 elm之后，若不存在元素 elm，则插入到最后。7.设单链表的结点类型定义如下：typedef struct nodeint
16、data；struct node*next；NodeType；设计一算法删除带头结点的单链表L 中的元素 x（元素 x 只有一个）。8.设单链表的结点类型定义如下：typedef struct nodeintdata；struct node*next；NodeType；设计一算法删除带头结点的单链表L 中所有的元素 x(元素 x 可能有多个)。9.设有一整型的带头结点的单链表，其元素值升序排列，请定义结点的类型并设计一算法实现：任意给定一个元素x 将其插入到该表中，使得该链表中的数据依然有序。10.已知一带头结点的单链表L，结点类型为：typedef struct nodeintdata;struct node*next;nodetype;设计一算法，求该链表中值最大的结点并返回该结点的指针，若链表为空，则返回一个空指针。11.已知一带头结点的单链表L，结点类型为：typedef struct node.可修编-.-intdata;struct node*next;nodetype;设计一算法，求该链表中所有元素的平均值并返回。.可修编-