资源预览内容
第1页 / 共15页
第2页 / 共15页
第3页 / 共15页
第4页 / 共15页
第5页 / 共15页
第6页 / 共15页
第7页 / 共15页
第8页 / 共15页
第9页 / 共15页
第10页 / 共15页
亲,该文档总共15页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
第三章 顺序表一、填空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 (ij) /*将基准元素放在i位置*/四、完整程序设计1. 在顺序存储结构的职工工资表中,职工工资信息包括:职工号(no)、姓名(name)、职称(pro)、工资(sal)等四项信息,请编写一完整的程序,实现以下功能:(1)创建信息表:从键盘读入所有职工的信息。(3分)推荐精选(2)删除:给定职工号,删除该职工的信息。(6分)(3)修改:对职称为“教授”的职工工资加100。(4分)(4)在显示器(屏幕)上显示所有职工的各项信息。(3分)(5)主程序以菜单的方式调用以上功能。(4分)元素类型及顺序表类型定义如下:typedef struct char no8,name10,pro6;float sal; DataType;typedef struct DataType dataMAXLEN+1; int len;SeqList;2图书管每本图书包含:书号(no)、书名(name)、现存量(newnum)、总库存量(sumnum)、单价五项信息,编写完整程序通过顺序表实现:(1) 初始化:录入现有的所有图书的五项信息。(3分) (2) 借书:每本书每次只能借一本,如果库中有该书,则允许借阅并使该书的现存量减1,否则给出相应提示信息。(4分)(3) 价值估算:统计库中所有书的价钱。价钱为所有书的单价乘以库存量的累加和。(4分)(4) 显示:显示图书管所有藏书信息。(3分)(5) 主程序以菜单的方式调用以上功能。(4分)元素类型及顺序表类型定义2分。3.设有两个整型顺序表L1,L2,其元素值递增有序存放,请定义该顺序表的元素类型及表类型(2分);设计以下自定义函数:(1)录入顺序表中所有元素的值。(3分)(2)将顺序表L1,L2合并为到另外一个顺序表L3中,L3中的元素非递减有序排列。(8分)(3)输出顺序表中元素的值。(3分)主函数通过调用以上函数实现两个表的合并并显示合并结果。(4分)4.有一个职工基本信息管理,职工信息包含:职工号、姓名、性别;编写完整程序,实现如下功能:推荐精选 (1)录入函数input:从键盘读入职工信息。(3分) (2)删除函数delete:给定职工号,删除该职工的信息。(5分) (3)插入函数insert:假定表中职工信息按职工号升序排列,任意给
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号