顺序表、链表题库实用文档.doc

《顺序表、链表题库实用文档.doc》由会员分享，可在线阅读，更多相关《顺序表、链表题库实用文档.doc（51页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

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若顺序表中的元素是从

3、1位置开始存放的，要在具有n个元素的顺序表中插入一个元素，合法的插入位置是（ ）。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顺序表中查找某个元素时，从前到后查找与从后到前查找的时间复杂度（ ）

5、同。二、简答题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=SeqLlen；j=i

6、；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

7、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()/当前元素小于基准元素/ Ldata0=L-

8、datai； /*当前元素暂存在0位置/ for（j=i1;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=Ldata 1; /将基准元素暂存在0位置/ while( ） wh

9、ile(（L-dataj=L-data 0）（ij） j； /*j位置元素大于基准元素且idata i= L-data j;i+; while(L-datai=Ldata0）&（ij）) i+；/i位置元素小于基准元素且ij 时i后移*/ if （ij) /*将基准元素放在i位置/四、完整程序设计1。 在顺序存储结构的职工工资表中，职工工资信息包括:职工号（no）、姓名（name）、职称（pro)、工资（sal）等四项信息，请编写一完整的程序，实现以下功能:(1)创建信息表：从键盘读入所有职工的信息.（3分）(2）删除：给定职工号，删除该职工的信息。（6分）（3）修改:对职称为“教授”的职工工

10、资加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） 借书:每本书每次只能借

11、一本，如果库中有该书，则允许借阅并使该书的现存量减1，否则给出相应提示信息。（4分)（3） 价值估算：统计库中所有书的价钱。价钱为所有书的单价乘以库存量的累加和。（4分）（4） 显示：显示图书管所有藏书信息。（3分）（5） 主程序以菜单的方式调用以上功能。（4分）元素类型及顺序表类型定义2分。3。设有两个整型顺序表L1，L2，其元素值递增有序存放，请定义该顺序表的元素类型及表类型（2分）；设计以下自定义函数：（1)录入顺序表中所有元素的值。(3分)（2)将顺序表L1，L2合并为到另外一个顺序表L3中，L3中的元素非递减有序排列。（8分）（3）输出顺序表中元素的值.（3分）主函数通过调用以上函数

12、实现两个表的合并并显示合并结果。（4分)4。有一个职工基本信息管理，职工信息包含：职工号、姓名、性别；编写完整程序，实现如下功能: （1)录入函数input:从键盘读入职工信息。（3分） （2)删除函数delete：给定职工号，删除该职工的信息.（5分）(3)插入函数insert：假定表中职工信息按职工号升序排列，任意给定一职工信息，使得插入后依然有序。（6分）主函数以菜单形式调用以上功能，类型定义2分，主函数4分。5.有一个学生信息包含:学号no主关键字；姓名name；英语成绩score.定义学生信息类型DataType及顺序表类型SeqList;（1）录入函数input：从键盘读入学生信息

13、。（3分）（2）查找函数search：任意给定一个学号，查找其英语成绩，将其成绩通过函数返回，若找不到,返回-1.（5分）(3）插入函数insert:假定表中学生信息按学号升序排列,任意给定一学生信息,使得插入后依然有序.(6分）主函数以菜单形式调用以上功能，类型定义2分，主函数4分。6。 设有一个超市的库存情况如下表1所示： 表1 超市商品信息商品编号商品名称价格库存量10110001作业本1.22010110002铅笔1.01010110003钢笔0.53010110004铅笔刀105 编写完整程序实现：（1) 从键盘输入货物信息并将其放在顺序表中。(4分）。(2）假定商品信息按货号升序存

14、放，任意插入一商品信息，要求按货号有序插入到表中。（6分)(3）任意给定一个商品编号,查找其商品名称、价格和库存量，如果存在该商品输出并返回1，否则返回0.（4分)主函数以菜单形式调用以上功能，类型定义2分,主函数4分.7.有一个房产信息管理系统，房产信息包含:门牌号、户主、 号码、面积.编程实现如下功能（要求用顺序表存储）:（1） 编写一个初始化函数input:从键盘读入房产基本信息。（3分）(2） 编写一个取暖费用计算函数cost:任意给定一门牌号，根据门牌号进行查询,找到时，返回应缴纳取暖费，否则返回0,并且给出提示信息。计算公式为：每户应缴纳费用=面积*4。5元/m2。(4分)（3）编

15、写一排序函数sort：按门牌号升序排列。（4分）（4）编写一个函数output：输出所有面积低于90平方米住户的名称。（3分）主函数以菜单形式调用以上功能,类型定义2分，主函数4分。8.有一个学生信息包含:学号nonext及（ ）操作。14设指针变量p指向单链表中某结点A，则删除结点A的后继结点需要的操作为（ )（不考虑存储空间的释放）。15在单链表中,若给定某个结点的指针,要删除该结点的后继结点的时间复杂度为（ ）。16统计单链表中元素个数的时间复杂度是( ）。17要访问具有n个结点的单链表中任意一个结点的时间复杂度是（ ）。18链式存储结构的线性表中，插入或删除某个元素所需的时间与其位置(

16、 ）关。（填有或无）.19在单链表中，若给定某个结点的数据信息，要删除该结点的后继结点的时间复杂度为（ ）。20若指针p,q的值相同,则p和q的值（ )相同.21若要将一个单链表中的元素倒置，可以借助（ ）建立单链表的思想将链表中的结点重新放置。22线性表用链式存储结构存储比用顺序存储结构存储所占的存储空间（ ）多。（填一定或不一定）二、简答题1下列算法完成用头插法为数组a中的n个元素建立一个带头结点的单链表，并返回其头指针,请在空的下划线上填写合适的内容完成该算法。NodeType creatl2 (DataType a,int n） NodeTypehead, s; int i;head=

17、(NodeType*)malloc（sizeof（NodeType)； /*为头结点申请空间*/if （head=NULL) return NULL； ； /链表初始化为空/ for (i=1；i=n;i+) s=（NodeType*)malloc(sizeof（NodeType)； ； /给新结点的数据域赋值/ snext=head-next； /*新结点的指针域指向头的下一个元素*/; /头结点指向新结点/ ； /返回头指针*/2。下列算法完成用尾接法为数组a中的n个元素建立一个带头结点的单链表,并返回其头指针，请在空的下划线上填写合适的内容完成该算法。NodeType creatl1（D

18、ataType a,int n） NodeType head,*tail,s; / head为头指针, tail为尾指针/ int i； head=initl( ）; /链表初始化/ if （head=NULL) return NULL; ； /尾指针初始化为头指针/ for (i=0；in;i+） ； /为新结点申请空间*/ if (s=NULL) return NULL; /*申请不到空间，则返回空/; /*给新结点的数据域赋值/snext=NULL; / *给新结点的指针域赋值*/ tailnext=s; /*将新结点接到表尾*/; /*新结点为当前的表尾/ return head; /

19、*返回头指针/ 3。简述什么是链式存储结构,链式存储结构的优缺点有哪些。4。 请解释：结点，头结点，头指针,首元结点。5. 已知整型带头结点的单链表H，下列算法实现将该链表中的元素倒置,若原链表中的元素为1，2，3，4,5; 倒置后在则变成5，4，3，2，1。请在空的下划线上填写合适的内容完成该算法。void reverse () NodeType*p; p=H next; /*p指向首元结点*/ Hnext=NULL； /*头结点的指针域为空*/ while(） /当p结点不为空时*/ q=p; p=pnext; /*p指针后移/ /将q所指向的结点插入到头结点之后*/ 三、算法设计1.设单

20、链表的结点类型定义如下：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

21、；设计一算法求带头结点的单链表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;N

22、odeType；设计一算法在带头结点的单链表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. 设有一整型的带头结点的单链表，其元素值

23、升序排列，请定义结点的类型并设计一算法实现：任意给定一个元素x将其插入到该表中，使得该链表中的数据依然有序。10. 已知一带头结点的单链表L，结点类型为： typedef struct nodeint data;struct node *next；nodetype；设计一算法，求该链表中值最大的结点并返回该结点的指针，若链表为空,则返回一个空指针。11. 已知一带头结点的单链表L，结点类型为： typedef struct nodeint data;struct node *next;nodetype;设计一算法,求该链表中所有元素的平均值并返回。建设工程监理概论1、建设工程的决定性环节是：设

24、计质量2、工程建设监理是监理单位受项目法人的委托：对工程建设实施的监督管理3、建设工程监理的基本目的是协助建设单位在计划的目标内把工程建成投入使用4、工程建设监理依据国家批准的工程项目建设文件,有关工程建设的法律、法规和工程建设监理合同及其他工程建设合同开展5、工程建设监理实施需要建设单位的委托和授权6、建设单位对工程监理企业法令结果是在委托监理的工程中拥有一定的管理权限7、建设工程监理实施的前提是建设单位的委托和授权8、把建设工程监理与政府建设工程行政性监督管理活动区别开,是建设工程监理的服务性9、工程建设监理与政府工程质量监督的区别是：前者属于社会的、民间的，后者属于强制性的政府行为10、

25、建设工程监理的依据为：法律、法规和建设工程合同11、建设工程法律是指由全国人民代表大会及其常务委员会通过的规范工程建设活动的法律规范，由国家主席签署主席令予以公布。12、建设工程监理是微观性质监督管理活动13、1988年7月建设部颁布了关于开展建设监理工作的通知,标志着我国建设工程领域的改革进入了一个新的阶段。14、建设工程监理对象包括新建、改建和扩建建筑15、监理单位是建设项目管理服务的主体。16、工程招投标结束是以签订合同为标志的17、实施建设工程监理的基本条件是社会主义市场经济体制、法制环境、配套机制18、工程建设监理实施的对象是工程建设项目19、现阶段工程建设监理主要发生在项目建设的施

26、工阶段20、承建商共同要求工程建设监理要有公正性21、按照我国有关文件夹中的规定，在监理人员监理过程中，负责与工程项目建设的外部关系的组织协调工作是项目业主22、新中国成立以来,我国一直采用的是按照国家投资计划将建设资金分配各个部门和地方,然后再根据需要安排任务，由建设单位自筹自管方式实现工程项目,这是不符合工程建设的内在规律的。23、建设程序为工程建设监理提出了具体的任务和内容，基本任务是通过建设项目中的多项具体工作的完成来实现的24、在我国，实施建设监理制有利于政府在工程建设中的职能转变25、在工程建设监理的项目实施阶段，工程建设监理的目标是着重解决如何在明确的项目目标内来建成工程项目26

27、、推选建设监理制应当遵循的基本原则之一是结合中国国情27、从其业务性质方面定性一，建设工程具有服务性28、建设工程监理的服务对象是建设单位29、大中型及限额以上项目的建设程序中，设计文件是根据批准的可行性研究报告编制的30、项目可行性研究报告批准后，正式成立项目法人31、为建设工程监理的发展提供坚实基础的需求是如何做好决策和承担风险32、我国工程监理企业只接受建设单位的委托，不接受承建单位的委托为其提供管理服务,体现了建设工程监理的服务对象具有单一性特点33、建设工程可行性研究的主要作用是为建设项目投资决策提供依据34、实施建设工程监理有利于规范工程建设参与各方的建设行为，具体表现为除政府的监

28、督管理以外，建立工程建设参与各方的建设行为约束机制35、我国的建设工程监理是指具有相应资质的工程监理企业，接受建设单位的委托并代表建设单位对承包单位的建设行为进行监督管理的专业化服务活动。36、项目建议书是拟建项目单位向国家提出要求建设某一项目的建议文件，是对工程项目建设的轮廓设想.项目建议书的主要作用是推荐一个拟建项目37、建设工程监理的性质中，从业务性质方面定性是是服务性38、在实施监理的工程项目建设中，要贯彻执行项目法人责任制、工程招投标制、建设工程监理制、合同管理制39、关于建设程序与工程建设监理之间的关系：建设程序为工程建设监理提出了具体的任务和服务内容、建设程序确立了监理单位在项目建设中的重要地位、严格执行建设程序是监理工程师的职业准则、严格执行建设程序是结合我国国情推行建设监理制的具体表现、建设程序为建设工程提出了规范化的建设行为标准.40、监理单位与被监理单位的关系是通过法律、法规的规定、项目法人与监理单位签订的合同41、服务性是建设工程监理的一项重要性质，其管理服务的内涵表现为:主要方法是规划、控制、协调，建设工程投资、进度和质量控制为主要任务，基本目的是协助建设单位在计划的目标内将建设工程建成投入使用.42、建设工程管理的主要内容是：控制建设工程的投资,建设工期、控制建设工程的工程质量、进行建设工程合同管理，协调有关单位的工作关系.