顺序表、链表题库.doc
【精品文档】如有侵权,请联系网站删除,仅供学习与交流顺序表、链表题库.精品文档.第三章 顺序表一、填空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<1|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;j<=SeqL->len;j+) ; /*元素前移*/ ; /*表长减1*/ return 1;3.简述什么是顺序存储结构,顺序存储结构的优缺点都有哪些。4. 设有一整型顺序表L,元素从位置1开始存放,下列算法实现将以第一个元素为基准,将其放置在表中合适的位置,使得其前面的元素都比它小,后面的元素均大于等于该元素。请在空的下划线上填写合适的内容完成该算法。void part(SeqList *L) ; /*循环变量声明*/ int x; ; /*将第一个元素置入x中*/ for(i=2;i<=L->len;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)&&(i<j) j-; /*j位置元素大于基准元素且i<j 时j前移*/ if (i<j) L->data i= L->data j;i+; while(L->data i<= L->data 0)&&(i<j) i+;/*i位置元素小于基准元素且i<j 时i后移*/ if (i<j) /*将基准元素放在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:假定表中职工信息按职工号升序排列,任意给定一职工信息,使得插入后依然有序。(6分)主函数以菜单形式调用以上功能,类型定义2分,主函数4分。5. 有一个学生信息包含:学号no主关键字;姓名name;英语成绩score。定义学生信息类型DataType及顺序表类型SeqList;(1)录入函数input:从键盘读入学生信息。(3分)(2)查找函数search:任意给定一个学号,查找其英语成绩,将其成绩通过函数返回,若找不到,返回-1。(5分) (3)插入函数insert:假定表中学生信息按学号升序排列,任意给定一学生信息,使得插入后依然有序。(6分)主函数以菜单形式调用以上功能,类型定义2分,主函数4分。6. 设有一个超市的库存情况如下表1所示: 表1 超市商品信息商品编号商品名称价格库存量10110001作业本1.22010110002铅笔1.01010110003钢笔0.53010110004铅笔刀105 编写完整程序实现: (1) 从键盘输入货物信息并将其放在顺序表中。(4分)。(2)假定商品信息按货号升序存放,任意插入一商品信息,要求按货号有序插入到表中。(6分)(3)任意给定一个商品编号,查找其商品名称、价格和库存量,如果存在该商品输出并返回1,否则返回0。(4分) 主函数以菜单形式调用以上功能,类型定义2分,主函数4分。7.有一个房产信息管理系统,房产信息包含:门牌号、户主、电话号码、面积。编程实现如下功能(要求用顺序表存储):(1) 编写一个初始化函数input:从键盘读入房产基本信息。(3分) (2) 编写一个取暖费用计算函数cost:任意给定一门牌号,根据门牌号进行查询,找到时,返回应缴纳取暖费,否则返回0,并且给出提示信息。计算公式为:每户应缴纳费用=面积*4.5元/m2。(4分)(3)编写一排序函数sort:按门牌号升序排列。(4分)(4)编写一个函数output:输出所有面积低于90平方米住户的名称。(3分)主函数以菜单形式调用以上功能,类型定义2分,主函数4分。 8. 有一个学生信息包含:学号no主关键字;姓名name;英语成绩english,计算机成绩comp,数学成绩math。定义学生信息类型DataType及顺序表类型SeqList;(1)录入基本信息函数input:从键盘读入学生姓名、学号。(3分)(2)录入成绩inp_score:给定课程名称,录入所有人本门课的成绩。(3分) (3) 删除函数del:假定表中学生信息学号升序排列,任意给定一学生学号,删除该学生信息,正常删除返回1,否则返回0。(6分)(4)输出函数output:输出所有人的信息。(2分)主函数以菜单形式调用以上功能,类型定义2分,主函数4分。9设有一个商品信息表(包括商品编号no、商品名称name、商品库存量count和商品单价price) 编程实现以下功能: (1) 货物信息录入:按货号有序输入学生信息。(3分)(2) 进货管理:任意输入一个货物信息,在表中查找该货物,若存在此货物,则将该货物的数量加到表中货物数量中;若不存在该货物,则将该货物信息按照货物号有序插入到表中。(10分)(3)货物信息输出:输出所有货物的信息。(2分)主函数以菜单形式调用以上功能,类型定义2分,主函数3分。10设有一个商品信息表(包括商品编号no、商品名称name、商品库存量count和商品单价price) 编程实现以下功能: (1)货物信息录入:按货号有序输入货物信息。(3分)(2)出货管理:函数返回值为购买该货物的金额。任意输入一个货物信息x,在表中查找该货物,若存在此货物且库存量大于等于x的数量,则将表中货物的库存量减去x的数量,计算出需支付的金额并返回;若库存量不足,则给出相应的提示并返回0。若不存在该货物,返回-1。(10分)(3)货物信息输出:输出所有货物的信息。(2分)主函数以菜单形式调用以上功能,类型定义2分,主函数3分。11. 有一自来水公司水费缴费系统中,数据信息包括:用户名称、编号、用水量、水费、缴费情况(缴清,未缴),请定义用户信息数据类型及顺序表类型并设计如下函数:函数1:输入所有用户的名称,编号,用水量,用户名为”?”作为结束符。每个用户的水费通过公式:水费=用水量*0.59计算得出。用户的缴费情况都设为未缴。(4分)函数2:输入用户编号,查找到该用户信息并将该用户的缴费情况都设为缴清。(4分)函数3:设计一个排序函数,将元素信息按编号有序排列。(4分)函数4:输出所有的未缴费的用户名称。(3分)主函数以菜单形式调用以上功能,类型定义2分,主函数3分。12. 设有一个超市商品信息表(包括商品编号no、商品名称name、商品库存量amount和商品单价price) 编程实现以下功能: (1)货物信息录入:输入一批货物信息,货号为“000”时结束。(3分)(2)购物管理:输入若干货物货号、数量(即客户所购买的货物信息),货号为“000”时结束,输出所购买的每个货物货号、名称、数量、单价、金额(单价通过查找得到,金额=单价×数量);最后输出总的价格。(10分)(3)货物信息输出:输出所有货物的信息。(2分)主函数以菜单形式调用以上功能,类型定义2分,主函数3分。13.有一学生成绩信息包括:姓名、学号、成绩、名次;编程实现以下功能: (1)输入所有人姓名、学号、成绩,名次初始化为0。(3分)(2)给定一学生学号,输出其成绩,若不存在该学号,给出相应的错误提示。(4分)(3)将学生信息按成绩由高到低排序,并将其名次存入该学生信息的“名次”中。(6分)(4)输出所有学生的信息。(2分)主函数以菜单形式调用以上功能,类型定义2分,主函数3分。14.学生考勤管理。学生信息包括:姓名、学号、考勤情况(迟到、旷课、按时上课),成绩及本次已经是第几次考勤。每个人有20次考勤; 编程实现以下功能: (1)学生基本信息录入及初始化:输入所有学生的姓名、学号,将每个人的考勤成绩置0,将考勤次数也置0。(3分)(2)输入考勤情况:每次上课,输入本次考勤,从第一个人开始,依次输入每个人的考勤。(4分)(3)计算考勤成绩:迟到得0.5分,旷课得0分,正常上课得1分,计算每个人的考勤成绩。(5分)(4)输出所有人的学号、姓名、考勤情况、考勤成绩。(3分)主函数以菜单形式调用以上功能,类型定义2分,主函数3分。元素类型定义如下:typedef struct char name10; /*name表示学生姓名*/ char no12; /*no表示学号*/char kaoqin21; /*kaoqin表示20次的考勤,q-缺课,c-迟到,z-按时上课*/int k; /*k表示已经考勤到第几次,初始化时将其置为-1*/int score; /*score表示考勤成绩*/ DataType;若有DataType x,则x. kaoqin2表示x的第三次考勤。15. 有一个职工基本信息管理,职工信息包含:职工号、姓名、工资;编写完整程序,实现如下功能: (1)录入函数input:从键盘读入职工信息。(3分) (2)修改函数modify:给定职工号,查找该职工,若找到修改其信息,若找不到,给出错误提示。(4分) (3)插入函数insert:假定表中职工信息按职工号升序排列,任意给定一职工信息,使得插入后依然有序。(6分)(4)输出函数output:输出所有人的信息。(2分)主函数以菜单形式调用以上功能,类型定义2分,主函数3分。16. 有一个学生成绩管理,学生信息包含:学号、姓名、成绩;编写完整程序,实现如下功能: (1)录入函数input:从键盘读入学生信息。(3分) (2)修改函数modify:给定学号,查找该学生,若找到修改其成绩,若找不到,给出错误提示。(4分) (3)排序函数sort:将学生信息按成绩由高到低排序。 (6分)(4)输出函数output:输出所有人的信息。(2分)主函数以菜单形式调用以上功能,类型定义2分,主函数3分。17. 图书管每本图书包含:书号(no)、书名(name)、现存量(newnum)、总库存量(sumnum)四项信息,编写完整程序通过顺序表实现:(1) 初始化:录入现有的所有图书的四项信息。(3分) (2) 清库:给定某书x的书号及数量,若找到该书,将该书的现存量及库存量减去x的数量,若减后的库存量为0,则删除该书信息;若找不到该书,则给出错误提示。(9分)(3) 显示:显示图书管所有藏书信息。(2分)(4) 主程序以菜单的方式调用以上功能。(4分)元素类型及顺序表类型定义(2分)18.图书管每本图书包含:书号(no)、书名(name)、现存量(newnum)、总库存量(sumnum)四项信息,编写完整程序通过顺序表实现:(1) 初始化:录入现有的所有图书的四项信息。(3分)(2) 检索:给定书名,输出所有与给定书名相同的书的信息。(3分)(3) 价值估算:统计库中所有书的价钱。价钱为所有书的单价乘以库存量的累加和。(6分)(4) 显示:显示图书管所有藏书信息。(2分)(5) 主程序以菜单的方式调用以上功能。(4分)(6) 完成元素类型定义及顺序表类型定义(2分)。19.图书管每本图书包含:书号(no)、书名(name)、现存量(newnum)、总库存量(sumnum)四项信息,编写完整程序通过顺序表实现:(1) 初始化:录入现有的所有图书的四项信息。(3分)(2) 查找:给定书号,在表中查找该书,若存在返回其位置,否则返回0。(4分)(3) 进书:给定某个图书的书名、书号、数量,若此次购进的是图书馆已有的图书,则修改其现存量和总库存量;若此次购进的图书是新书,按书号有序插入到表中。(假定表中元素按书号升序排列)(7分)(4) 主程序以菜单的方式调用以上功能。(4分)(5) 完成元素类型定义及顺序表类型定义(2分)。20学生学费管理。学生信息包括:姓名、学号、学费、已缴学费、欠费。编写完整程序通过顺序表实现:(1) 初始化:录入所有人的姓名、学号、学费。(3分)(2) 缴费:输入学号及已缴学费,欠费=学费-已缴学费。(5分)(3) 催缴学费:对欠费为正数的人,输出其姓名、学号、欠费并统计所有人的欠费总数,总的欠费数目以函数值的形式返回(6分)(4) 主程序以菜单的方式调用以上功能。(4分)(5) 完成元素类型定义及顺序表类型定义(2分)。第四章 链表一、填空1链式存储结构的线性表中所有元素的地址( )连续。2单链表中增加头结点的目的是为了( )。3用单链表存储线性表,每个结点需要两个域,一个是数据域,另一个是( )。4用单链表存储线性表,每个结点需要两个域,一个是( ),另一个是指针域。5链式存储结构的线性表其元素之间的逻辑关系是通过结点的( )域来表示的。6指针为空表示该指针所指向的结点( )。7某带头结点的单链表的头指针为head,判定该链表为非空的条件是( )。8某带头结点的单链表的头指针为head,判定该链表为空的条件是( )9在单链表L中,指针P所指的结点为尾结点的条件是( )。10在单链表L中,指针P所指的结点有后继结点的条件是( )。11头插法建立单链表时,元素的输入顺序与在链表中的逻辑顺序是( )的。12尾接法建立单链表时,元素的输入顺序与在链表中的逻辑顺序是( )的。13在带有头结点的单链表HL中,要在首元元素之前插入一个由指针p指向的结点,则应执行p->next=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;i<=n;i+) s=(NodeType*)malloc(sizeof(NodeType); ; /*给新结点的数据域赋值*/ s->next=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;i<n;i+) ; /*为新结点申请空间*/ if (s=NULL) return NULL; /*申请不到空间,则返回空*/ ; /*给新结点的数据域赋值*/s->next=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;设计一算法,求该链表中所有元素的平均值并返回。