数据结构第2章答案.doc

一、填空题01、当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用顺序存储结构。02、线性表L=（a1,a2,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是(n-1)/2。03、在有n个元素的顺序表中插入一个新元素，需要平均移动n/2元素，具体移动的元素个数与表长和该元素在表中的位置有关。04、线性表中结点的集合是有限的，结点间的关系是一对一的。05、向一个长度为n的顺序表的第i个元素(1in+1)之前插入一个元素时，需向后移动n-i+1个元素。06、向一个长度为n的顺序表中删除第i个元素(1in)时，需向前移动n-i个元素。07、在顺序表中访问任意一结点的时间复杂度均为O(1)，因此，顺序表也称为随机存取的数据结构。08、顺序表中逻辑上相邻的元素的物理位置必定相邻。单链表中逻辑上相邻的元素的物理位置未必相邻。09、在单链表中，除了首结点外，任一结点的存储位置由其直接前驱结点的链域值指示。10、在n个结点的单链表中要删除已知结点*p，需找到它的前驱结点的地址，其时间复杂度为O(n)。11、设单链表的结点结构为(data,next)，next 为指针域，已知指针px指向单链表中data域为x的结点，指针py 指向data域为y的新结点，若将结点y插入结点x之后，则需要执行以下语句：py-next=px-next; px-next=py;12、在单链表中设置头结点的作用是使插入和删除等操作统一，在第一个元素之前插入元素和删除第一个结点不必另作判断。13、对于一个具有n 个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为O(1)，在给定值为x 的结点后插入一个新结点的时间复杂度为O(n)。14、在双向循环链表中，向p所指的结点之后插入指针f所指的结点，其操作是：f-next=p-next; f-prior=p; p-next-prior=f; p-next=f;15、在双向链表结构中，若要求在p指针所指的结点之前插入指针为s所指的结点，则需执行下列语句：s-next=p; s-prior= p-prior; p-prior=s; s-prior-next =s;16、链接存储的特点是利用指针来表示数据元素之间的逻辑关系。17、对于双向链表，在两个结点之间插入一个新结点需修改的指针共4个，单链表为2个。18、循环单链表的最大优点是从任一结点出发都可访问到链表中每一个元素。19、已知指针p指向单链表L中的某结点，则删除其后继结点的语句是 u=p-next; p-next=u-next; free(u);20、带头结点的双循环链表L中只有一个元素结点的条件是 L-next-next=L21、在单链表L 中，指针p 所指结点有后继结点的条件是 p-next!=null22、带头结点的双循环链表L为空表的条件是 L-next=L & L-prior=L23、在单链表p结点之后插入s结点的操作是 s-next=p-next; p-next=s;二、判断题01、链表的每个结点中都恰好包含一个指针。02、链表的物理存储结构具有同链表一样的顺序。03、链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。04、线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。05、顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。 06、顺序存储方式的优点是存储密度大，且插入、删除运算效率高。07、线性表在物理存储空间中也一定是连续的。08、线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。09、顺序存储方式只能用于存储线性结构。10、线性表的逻辑顺序与存储顺序总是一致的。11、链表中的头结点仅起到标识的作用。12、顺序存储结构的主要缺点是不利于插入或删除操作。13、线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。14、对任何数据结构链式存储结构一定优于顺序存储结构。15、集合与线性表的区别在于是否按关键字排序。16、所谓静态链表就是一直不发生变化的链表。17、线性表的特点是每个元素都有一个前驱和一个后继。18、取线性表的第i个元素的时间同i的大小有关。19、循环链表不是线性表。20、链表是采用链式存储结构的线性表,进行插入、删除操作时，在链表中比在顺序存储结构中效率高。三、单项选择题C01、数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为_。 A) 存储结构 B) 逻辑结构 C) 顺序存储结构 D) 链式存储结构B02、一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是 。 A) 110 B) 108 C) 100 D) 120A03、在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是_。 A) 访问第i个结点(1in)和求第i个结点的直接前驱(2in) B) 在第i个结点后插入一个新结点(1in) C) 删除第i个结点(1in) D) 将n个结点从小到大排序B04、向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动 _ 个元素。 A) 8 B) 63.5 C) 63 D) 7A05、链式存储的存储结构所占存储空间_。 A) 分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针 B) 只有一部分，存放结点值 C) 只有一部分，存储表示结点间关系的指针 D) 分两部分，一部分存放结点值，另一部分存放结点所占单元数A06、下述_是顺序存储结构的优点。 A) 存储密度大 B) 插入运算方便 C) 删除运算方便 D)可方便地用于各种逻辑结构的存储表示D07、线性表若采用链式存储结构时，要求内存中可用存储单元的地址_。 A) 必须是连续的 B) 部分地址必须是连续的 C) 一定是不连续的 D) 连续或不连续都可以B08、线性表L在 情况下适用于使用链式结构实现。 A) 需经常修改L中的结点值 B) 需不断对L进行删除插入 C) L中含有大量的结点 D) L中结点结构复杂C09、单链表的存储密度_。 A) 大于1 B) 等于1 C) 小于1 D) 不能确定D10、若某链表中最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用_存储方式最节省运算时间。 A) 单向链表 B) 双向链表 C) 单向循环链表 D) 带头结点的双向循环链表D11、若线性表最常用的操作是存取第i个元素及其前趋的值，则采用_存储方式最节省时间。 A) 单向链表 B) 双向链表 C) 单向循环链表 D) 顺序表A12、链表不具有的特点是_。 A) 可随机访问任一元素 B) 插入删除操作不需要移动元素 C) 不必事先估算存储空间 D) 所需空间与线性表长度成正比B13、在单向链表的指针p所指结点后插入结点*s(*p不是尾结点)，则应执行_操作。 A) s-next=p; p-next=s; B) s-next=p-next; p-next=s; C) s-next=p-next; p=s; D) p-next=s; s-next=p;C14、非空的循环单向链表first的尾结点(由p指向)满足_。 A) p-next=NULL B) p=NULL C) p-next=first D) p=firstC15、下列关于线性表的叙述中，不正确的是_。 A) 线性表是n个结点的有穷序列 B) 线性表可以为空表 C) 线性表的每一个结点有且仅有一个前趋和一个后继 D) 线性表结点间的逻辑关系是1:1的联系 A16、在双向链表存储结构中删除p所指的结点时，需要按_修改指针的链接。 A) p-prior-next=p-next; p-next-prior=p-prior; B) p-prior=p-prior-next; p-prior-prior-next=p; C) p-prior-prior-next=p; p-prior=p-prior-prior; D) p-next-next-prior=p; p-next=p-next-next;A17、在单循环链表中指针p指向结点A，若要删除A之后的结点(存在)，则其中指针的链接操作为_。 A) p-next=p-next-next B) p=p-next C) p=p-next-next D) next=pB18、带头结点的单链表head为空的判定条件是_。 A) head=NULL B) head-next=NULL C) head-next=head D) head!=NULLD19、从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较_个结点。 A) n B) n/2 C) (n-1)/2 D) (n+1)/2B20、在一个具有n个结点的有序单链表中插入一个新结点，并仍然有序的时间复杂度为_。 A) O(1) B) O(n) C) O() D) O()C21、给定有n个元素的向量，建立一个有序的单链表的时间复杂度为_。 A) O(1) B) O(n) C) O() D) O()A22、下面程序的功能是_。void delete(Linklist *L) p=L; while (p-next!=NULL) m=p-next-data; q=p; while (q-next!=NULL) if (q-next-data=m) r=q-next; q-next=r-next; free(r); q=q-next; p=p-next; A) 在单链表中删除重复结点 B) 在单链表中删除第m个结点 C) 在单链表中的第m个位置插入结点 D) 在单链表中统计结点的数目并保存到m中C23、线性表是具有n 个_的有限序列(n0)。 A) 表元素 B) 字符 C) 数据元素 D) 数据项A24、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用_存储方式最节省时间。 A) 顺序表 B) 双链表 C) 带头结点的双循环链表 D) 单循环链表B25、静态链表中指针表示的是_。 A) 内存地址 B) 下一元素数组下标 C) 下一元素地址 D) 下一元素的偏移地址C26、对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为_。 A) O(n) O(n) B) O(n) O(1) C) O(1) O(n) D) O(1) O(1)C27、线性表(a1,a2,an)以链接方式存储时，访问第i位置元素的时间复杂性为_。 A) O(i) B) O(1) C) O(n) D) O(i-1)C28、在双向链表指针p的结点前插入一个指针q的结点操作是_。 A) p-piror=q;q-next=p;p-prior-next=q;q-piror=q; B) p-piror=q;p-piror-next=q;q-next=p;q-piror=p-piror; C) q-next=p;q-piror=p-piror;p-piror-next=q;p-piror=q; D) q-piror=p-piror;q-next=q;p-piror=q;p-piror=q;B29、占用连续的存储空间，但插入和删除不需要移动元素，这种线性表的存储结构是_。 A) 单向链表 B) 静态链表 C) 双向链表 D) 顺序表B30、在一个长度为n(n1)的单链表上，设有头和尾两个指针，执行_操作与链表的长度有关。 A) 删除单链表中的第1个元素 B) 删除单链表中的最后1个元素 C) 在单链表第1个元素之前插入1个新元素 D) 在单链表最后1个元素之后插入1个新元素A31、对于具有n个元素的线性表，算法_在单链表上实现要比在顺序表上实现效率更高。 A) 删除所有值为x的元素 B) 在最后一个元素的后面插入一个新元素 C) 顺序输出前k个元素 D) 第i个元素与第n-i-1个元素交换D32、与单向链表相比，双向链表的优点之一是_。 A) 插入、删除操作更简单 B) 可以进行随机访问 C) 可以省略表头指针或表尾指针 D) 顺序访问相邻结点更灵活A33、在长度为n的_上，删除第1个结点，其算法的时间复杂度为O(n)。 A) 只有表头指针的不带头结点的循环单链表 B) 只有表尾指针的不带头结点的循环单链表 C) 只有表尾指针的带头结点的循环单链表 D) 只有表头指针的带头结点的循环单链表四、代码填空题01、下面函数是链表的插入算法，根据要求填空。ListInsert(LinkList L, int i, ElemType e)/在带头结点的单链表L中第i个位置之前插入元素e。 p=L; j=0; while(p&jnext; +j; if(!p|ji-1) return ERROR; s=(LinkList)malloc(sizeof(LNode);/请填空，要求将新结点插入到L中。 s-data=e; s-next=p-next; p-next=s;02、下面函数是链表的删除算法，根据要求填空。ListDelete(LinkList L, int i, ElemType *e)/在带头结点的单链表L中删除第i个元素，由e返回值。 p=L; j=0; while(p-next&jnext; +j; if(!(p-next)|ji-1) return ERROR;/请填空，要求删除并释放结点。 q=p-next; p-next=q-next; *e=q-data; free(q); 03、下面函数的功能是采用前插法建立带头结点的链表，请填空。void CreateList_1(LinkList *L, int n) L=(LinkList)malloc(sizeof(LNode); L-next=NULL; for(i=1; idata); p-next=L-next; L-next=p; 04、下面函数的功能是采用后接法建立带头结点的链表，请填空。void CreateList_2(LinkList *L, int n) L=(LinkList)malloc(sizeof(LNode); L-next=NULL; q=L; for(i=1; idata); q-next=p; q=p; p-next=NULL;05、下面函数的功能是求无头结点的单向循环链表的长度，请填空。int ListLength(LinkList L) LinkList p; int n; if (L=NULL或!L) n=0; else p=L-next; n=1; while (p!=L) p=p-next; n+; return(n);06、下面函数的功能是实现带头结点单链表的就地逆置，请填空。void Reverse(LinkList *L) LinkList p,q,r; /p为遍历指针,q是其前驱,r为其后继 q=NULL;p=(*L)-next; while(p!=NULL) r=p-next; p-next=q; q=p; p=r; (*L)-next=q;07、在有头结点的链表中删除具有特定值的所有元素。void DelListElem(LinkList &L, ElemType e) p=L-next; q=L; while (pNULL) if (p-data=e) q=p-next; free(p); p=q-next; else q=p; p=p-next; 五、算法设计题01、在顺序表中求值为X的元素个数。int count(SqList L, ElemType x) if (!L.Elem) return ERROR; n=0; for(i=0;inext; while (r!=NULL) q=r; p=r-next; while (p!=NULL) if (p-data=r-data) q-next=p-next; free(p); p=q-next; else q=p; p=p-next; r=r-next; 03、插入法建立有序链表。void CreateList_3(LinkList &L, int n) L=(LinkList)malloc(sizeof(LNode); L-next=NULL; for(i=1;idata); q=L; p=L-next; while (p!=NULL & p-datadata) q=p; p=p-next; new-next=p; q-next=new; 04、判断链表是否为递增顺序。int Increase(LinkList L) pre=L-next; if (preNULL) while (pre-nextNULL) p=pre-next; if (p-datapre-data) pre=p else return FALSE; return TRUE;05、已知两个线性表A、B，且其数据元素递增，设计算法求出A、B的交集C，并同样以递增顺序存储。void UnionList(List La, List Lb, List &Lc) InitList(Lc); i=1; j=1; k=1; La_len=ListLength(La); Lb_len=ListLength(Lb); while (i=La_len) & (j=Lb_len) GetElem(La,i,ai); GetElem(Lb,j,bj); if (aibj) j+; else ListInsert(Lc,k,ai); i+; j+; k+; 下午13：0017：00度。全体员工都必须自觉遵守工作时间，实行不定时工作制的员工不必打卡。3.1.2.2打卡次数：一日两次，即早上上班打卡一次，下午下班打卡一次。3.1.2.3打卡时间：打卡时间为上班到岗时间和下班离岗时间； 3.1.2.4因公外出不能打卡：因公外出不能打卡应填写外勤登记表,注明外出日期、事由、外勤起止时间。因公外出需事先申请，如因特殊情况不能事先申请，应在事毕到岗当日完成申请、审批手续，否则按旷工处理。因停电、卡钟（工卡）故障未打卡的员工，上班前、下班后要及时到部门考勤员处填写未打卡补签申请表，由直接主管签字证明当日的出勤状况，报部门经理、人力资源部批准后，月底由部门考勤员据此上报考勤。上述情况考勤由各部门或分公司和项目文员协助人力资源部进行管理。3.1.2.5手工考勤制度3.1.2.6手工考勤制申请：由于工作性质，员工无法正常打卡（如外围人员、出差），可由各部门提出人员名单，经主管副总批准后，报人力资源部审批备案。3.1.2.7参与手工考勤的员工，需由其主管部门的部门考勤员(文员)或部门指定人员进行考勤管理，并于每月26日前向人力资源部递交考勤报表。3.1.2.8参与手工考勤的员工如有请假情况发生，应遵守相关请、休假制度，如实填报相关表单。3.1.2.9 外派员工在外派工作期间的考勤,需在外派公司打卡记录;如遇中途出差,持出差证明,出差期间的考勤在出差地所在公司打卡记录;3.2加班管理3.2.1定义加班是指员工在节假日或公司规定的休息日仍照常工作的情况。A现场管理人员和劳务人员的加班应严格控制，各部门应按月工时标准，合理安排工作班次。部门经理要严格审批员工排班表，保证员工有效工时达到要求。凡是达到月工时标准的，应扣减员工本人的存休或工资；对超出月工时标准的，应说明理由，报主管副总和人力资源部审批。 B因员工月薪工资中的补贴已包括延时工作补贴，所以延时工作在4小时（不含）以下的，不再另计加班工资。因工作需要，一般员工延时工作4小时至8小时可申报加班半天，超过8小时可申报加班1天。对主管(含)以上管理人员，一般情况下延时工作不计加班，因特殊情况经总经理以上领导批准的延时工作，可按以上标准计加班。3.2.2.2员工加班应提前申请，事先填写加班申请表，因无法确定加班工时的，应在本次加班完成后3个工作日内补填加班申请表。加班申请表经部门经理同意，主管副总经理审核报总经理批准后有效。加班申请表必须事前当月内上报有效，如遇特殊情况，也必须在一周内上报至总经理批准。如未履行上述程序，视为乙方自愿加班。3.2.2.3员工加班，也应按规定打卡，没有打卡记录的加班，公司不予承认；有打卡记录但无公司总经理批准的加班，公司不予承认加班。3.2.2.4原则上，参加公司组织的各种培训、集体活动不计加班。3.2.2.5加班工资的补偿：员工在排班休息日的加班，可以以倒休形式安排补休。原则上，员工加班以倒休形式补休的，公司将根据工作需要统一安排在春节前后补休。加班可按1：1的比例冲抵病、事假。3.2.3加班的申请、审批、确认流程3.2.3.1加班申请表在各部门文员处领取，加班统计周期为上月26日至本月25日。3.2.3.2员工加班也要按规定打卡，没有打卡记录的加班，公司不予承认。各部门的考勤员(文员)负责加班申请表的保管及加班申报。员工加班应提前申请，事先填写加班申请表加班前到部门考勤员(文员)处领取加班申请表，加班申请表经项目管理中心或部门经理同意，主管副总审核，总经理签字批准后有效。填写并履行完审批手续后交由部门考勤员(文员)保管。3.2.3.3部门考勤员（文员）负责检查、复核确认考勤记录的真实有效性并在每月27日汇总交人力资源部，逾期未交的加班记录公司不予承认。谈笑在指尖人生路上每个人都在慢慢行走，行走的路上会有高低错落、跌宕起伏。一个人的一生，很像一首永恒的歌，有高潮、有低谷，并不是每一个人的一生都是一帆风顺的，总会有这样或那样的烦恼如影相随，让人忧愁和不悦。人生路上的风雨、波折、苦涩与眼泪，往往会使得一些人很难控制好自己的情绪，或愤怒、或失望、或抱怨、或悔恨，或心烦意乱，或痛苦不堪，或悲观失望，或萎靡消沉，甚至失去面对生活的勇气。 每个人对生活都有着美好的渴望，谁都希望能活得无限精彩，谁都想拥有灿烂的人生，在社会、在家庭、在工作中被尊重、被需要、被认同，这无可非议；当遇到困难，挫折，遇到不顺心的人和事，或者遇到变故，产生一些想法，产生一些情绪，这也很正常，因为我们都是平凡人。面对生活里遇到的困难、挫折、不顺和困惑时，我们首先应该调整好自己的心态，让自己的心情始终行走在阳光里，用一颗平常之心，去接受现实；以一颗包容之心，去待人处事。应该这样去想，这些都是人生过程中的正常现象，没有什么稀奇。我们若能把心放平了，那么我们的生活就有可能会过得像一泓平静的水，若我们能把心放轻了，那我们的人生就有可能是一朵自在的云，我们在生活中便也会少了很多烦恼，生活也会过得有滋有味。 人活得是一种心情，日子过得是一种快意。一个人活得好与坏，其实就是自己内心一种感觉而已。怀有一种好心情过日子，日子过得就有快意，怀着坏心情去过日子，就有可能愤