还剩34页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
数据结构习题答案第一节概论
一、选择题1.要求同一逻辑结构的所有数据元素具有相同的特性,这意味着A.数据元素具有同一的特点*B.不仅数据元素包含的数据项的个数要相同,而且对应数据项的类型要一致C.每个数据元素都一样D.数据元素所包含的数据项的个数要相等2.数据结构是一门研究非数值计算的程序设计问题中计算机的1以及它们之间的2和运算的学科1*A.操作对象B.计算方法C.逻辑存储D.数据映像2A.结构*B.关系C.运算D.算法3.数据结构被形式地定义为D,R,其中D是1的有限集合,R是D上2的有限集合1A.算法*B.数据元素C.数据操作D.逻辑结构2A.操作B.映像C.存储*D.关系4.在数据结构中,从逻辑上可以把数据结构分为A.动态结构和静态结构B.紧凑结构和非紧凑结构*C.线性结构和非线性结构D.内部结构和外部结构5.线性表的顺序存储结构是一种的存储结构*A.随机存取B.顺序存取C.索引存取D.Hash存取6.算法分析的目的是A.找出数据结构的合理性B.研究算法中的输入和输出的关系*C.分析算法的效率以求改进D.分析算法的易懂性和文档性7.计算机算法指的是1,它必须具备输入、输出和2等五个特征1A.计算方法B.排序方法*C.解决某一问题的有限运算序列D.调度方法2A.可行性、可移植性和可扩充性*B.可行性、确定性和有穷性C.确定性,有穷性和稳定性D.易读性、稳定性和安全性8.线性表若采用链表存储结构,要求内存中可用存储单元的地址A.必须是连续的B.部分必须是连续的C.一定是不连续的*D.连续不连续都可以9.在以下的叙述中,正确的是A.线性表的线性存储结构优于链式存储结构*B.二维数组是它的每个数据元素为一个线性表的线性表C.栈的操作方式是先进先出D.队列的操作方式是先进后出10.根据数据元素之间关系的不同特性,以下四类基本的逻辑结构反映了四类基本的数据组织形式,其中解释错误的是*A.集合中任何两个结点之间都有逻辑关系但组织形式松散B.线性结构中结点按逻辑关系依次排列形成一条“锁链”C.树形结构具有分支、层次特性,其形态有点像自然界中的树D.图状结构中的各个结点按逻辑关系互相缠绕,任何两个结点都可以邻接11.以下说法正确的是A.数据元素是数据的最小单位B.数据项是数据的基本单位C.数据结构是带有结构的各数据项的集合*D.数据结构是带有结构的数据元素的集合
二、判断题╳1.数据元素是数据的最小单位√2.数据结构是带有结构的数据元素的集合√3.数据结构、数据元素、数据项在计算机中的映像分别称为存储结构、结点、数据域╳4.数据项是数据的基本单位√5.数据的逻辑结构是指各数据元素之间的逻辑关系,是用户按使用需要建立的√6.数据的物理结构是数据在计算机中实际的存储形式╳7.算法和程序没有区别,所以在数据结构中二者是通用的╳8.顺序存储结构属于静态结构,链式存储结构属于动态结构
三、填空题1.所谓数据的逻辑结构指的是数据元素之间的____逻辑关系_____2,数据结构是相互之间存在一种或多种特定关系的数据元素的集合,它包括三方面的内容___数据的逻辑结构、数据的存储结构、对数据施加的操作___3.数据的逻辑结构包括_____集合结构___、_____线性结构___、____树型结构_____和__图状结构_____四种类型4.在线性结构中,开始结点__没有_前驱结点,其余每个结点有且只有__一个_个前驱结点5.在树形结构中,根结点只有___一个___,其余每个结点有且只有___一个___前驱结点;叶结点没有___后继__结点,其余每个结点的后继结点可以有__任意个__·6.在图形结构中,每个结点的前驱结点和后继结点可以有___任意个___7.算法的五个重要特性是__可行性___、___确定性___、___有穷性___、___输入__、___输出__8.下列程序段的时间复杂度是__O(n)___fori=1;i=n;i++A[i,i]=0;9.下列程序段的时间复杂度是__O(n2)___S=0;fori=1;i=n;i++forj=1;j=n;j++s=s+B[ij];sum=s;10.存储结构是逻辑结构的___物理__实现11.从数据结构的观点看,通常所说的“数据”应分成三个不同的层次,即__数据__、__数据元素_和__数据项___12.根据需要,数据元素又被称为__结点__、__记录__、___元素__或__顶点_13.通常,存储结点之间可以有___顺序存储__、____链式存储__、____索引存储__、___散列存储_四种关联方式,称为四种基本存储方式14.通常从___确定性___、__可读性_、___健壮性__、_高效性__等几方面评价算法包括程序的质量15.一个算法的时空性能是指该算法的_时间复杂度___和___空间复杂度_,前者是算法包含的__计算量__,后者是算法需要的___存储量__16.在一般情况下,一个算法的时间复杂度是__问题规模__的函数17.常见时间复杂度的量级有常数阶O__1_、对数阶O__log2n___、线性阶O__n__、平方阶O_n2_和指数阶O__2n_通常认为,具有指数阶量级的算法是__不可行__的18.数据结构的基本任务是数据结构的__设计__和__实现__19.数据对象是性质相同的__数据元素_的集合20.抽象数据类型是指一个__数学模型__以及定义在该模型上的一组操作
四、应用题1.分析下列程序段的时间复杂度……i=1;WHILEi=ni=i*2;……答Olog2n2.叙述算法的定义及其重要特性答算法是对特定问题求解步骤的一种描述,是指令的有限序列其中每一条指令表示一个或多个操作算法应该具有下列特性可行性、确定性、有穷性、输入和输出3.简述下列术语数据,数据元素,数据结构,数据对象答数据是信息的载体,是描述客观事物的数、字符,以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合数据元素是数据的基本单位在不同的条件下,数据元素又可称为元素、结点、顶点、记录等数据结构是指相互之间存在着一种或多种关系的数据元素的集合数据对象是性质相同的数据元素的集合4.逻辑结构与存储结构是什么关系?答在数据结构中,逻辑结构与存储结构是密切相关的,存储结构不仅将数据元素存储到计算机中,而且还要表示各数据元素之间的逻辑关系逻辑结构与计算机无关,存储结构是数据元素之间的关系在计算机中的表示5.将数量级210,n,n2,n3,nlog2n,log2n,2n,n!,2/3n,n2/3按增长率进行排列答2/3n,210,log2n,n2/3,n,nlog2n,n2,n3,2n,n!6.设有数据逻辑结构为D={k1,k2,k3,…,k9},R={k1,k3,k1,k8,k2,k3,k2,k4,k2,k5,k3,k9,k5,k6,k8,k9,k9,k7,k4,k6},画出这个逻辑结构的图示,并确定相对于关系R,哪些结点是开始结点,哪些结点是终端结点?答图略开始结点k
1、k2,终端结点k
6、k77.设有如图
1.1所示的逻辑结构图,给出它的逻辑结构,并说出它是什么类型的逻辑结构答数据逻辑结构为D={k1,k2,k3,…,k8},R={k1,k2,k1,k3,k3,k5,k3,k4,k4,k7,k4,k6,k5,k8},其逻辑结构类型为树型结构8.分析下列程序的时间复杂度设n为正整数1intrecintn{ifn==1return1;elsereturnn*recn-1;}2x=91;y=100;Whiley0ifx10y--;3i=1;j=0;whilei+j=nifijj++;elsei++;4x=n;y=0;whilex=y+1*y+1y++;答1On2O13On4On1/29.设n为正数试确定下列各程序段中前面加记号@的语句的频度1i=1;k=0;whilei=n-1{@k+=10*i;i++;2k=0;fori=1;i=n;i++forj=i;j=n j++@k++;答1n-12n+n-1+……+1=nn+1/2第二节线性表
一、选择题1.线性结构中的一个结点代表一个*A.数据元素B.数据项C.数据D.数据结构2.线性表L=a1,a2,…,ai,…,an,下列说法正确的是A.每个元素都有一个直接前驱和直接后继B.线性表中至少要有一个元素C.表中诸元素的排列顺序必须是由小到大或由大到小的D.*除第一个元素和最后一个元素外其余每个元素都有一个且仅有一个直接前驱和直接后继3.顺序表是线性表的A.链式存储结构*B.顺序存储结构C.索引存储结构D.散列存储结构4.对于顺序表,以下说法错误的是*A.顺序表是用一维数组实现的线性表,数组的下标可以看成是元素的绝对地址B.顺序表的所有存储结点按相应数据元素间的逻辑关系决定的次序依次排列C.顺序表的特点是逻辑结构中相邻的结点在存储结构中仍相邻D.顺序表的特点是逻辑上相邻的元素,存储在物理位置也相邻的单元中5.对顺序表上的插入、删除算法的时间复杂度分析来说,通常以为标准操作A.条件判断*B.结点移动C.算术表达式D.赋值语句6.对于顺序表的优缺点,以下说法错误的是A.无需为表示结点间的逻辑关系而增加额外的存储空间B.可以方便地随机存取表中的任一结点*C.插入和删除操作较方便D.由于顺序表要求占用连续的空间,存储分配只能预先进行静态分配7.在含有n个结点的顺序存储的线性表中,在任一结点前插入一个结点所需移动结点的平均次数为A.n*B.n/2C.n-1/2D.n+1/28.在含有n个结点的顺序存储的线性表中,删除一个结点所需移动结点的平均次数为A.nB.n/2*C.n-1/2D.n+1/29.带头结点的单链表head为空的条件是A.head=NULL*B.head-next=NULLC.head-next=headD.head!=NULL10.非空单循环链表head的尾结点*p满足A.p-next=NULLB.p=NULL*C.p-next=headD.p=head11.在双循环链表的*p结点之后插入*s结点的操作是A.p-next=s;s-prior=p;p-next-prior=s;s-next=p-next;B.p-next=s;p-next-prior=s;s-prior=p s-next=p-next;C.s-prior=p;s-next=p-next;p-next=s;p-next-prior=s;*D.s-prior=p;s-next=p-next;p-next-pror=s;p-next=s;
12.在一个单链表中,已知*q结点是*p结点的前驱结点,若在*q和*p之间插入结点*s,则执行A.s-next=p-next;p-next=s;B.p-next=s-next;s-next=p;*C.q-next=s;s-next=p;D.p-next=s;s-next=q;
13.在一个单链表中,若*p结点不是最后结点在*p之后插入结点*s,则执行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;
14.若某线性表中最常用的操作是取第i个元素和找第i个元素的前驱元素,则采用存储方式最节省时间*A.顺序表B.单链表C.双链表D.单循环链表15.设rear是指向非空带头结点的单循环链表的尾指针,则删除表头结点的操作可表示为A.p=rear;rear=rear-next;freepB.rear=rear-next;freerear;C.rear=rear-next-next;freerear;*D.p=rear-next-next;rear-next-next=p-next;freep;16.在一个单链表中,若删除*p结点的后继结点,则执行*A.q=p-next;p-next=q-next;freeq;B.p=p-next;p-next=p-next-next;freep;C.p-next=p-next;freep-next;D.p=p-next-next;freep-next;17.设指针p指向双链表的某一结点,则双链表结构的对称性可用式来刻画A.p-prior-next-==p-next-nextB.p-prior-prior==p-next-prior*C.p-prior-next-==p-next-priorD.p-next-next==p-prior-prior18.在循环链表中,将头指针改设为尾指针rear后,其头结点和尾结点的存储位置分别是A.rear和rear-next-next*B.rear-next和rearC.rear-next-next和rearD.rear和rear-next19.循环链表的主要优点是A.不再需要头指针了B.已知某个结点的位置后,容易找到它的直接前驱C.在进行插入、删除操作时,能更好地保证链表不断开*D.从表中任一结点出发都能扫描到整个链表20.在线性表的下列存储结构中,读取元素花费时间最少的是A.单链表B.双链表C.循环链表*D.顺序表
二、判断题√1.顺序存储的线性表可以随机存取╳2.顺序存储的线性表的插入和删除操作不需要付出很大的代价,因为平均每次操作只有近一半的元素需要移动√3.线性表中的元素可以是各种各样的,但同一线性表中的数据元素具有相同的特性,因此是属于同一数据对象╳4.在线性表的顺序存储结构中,逻辑上相邻的两个元素在物理位置上不一定相邻√5.在线性表的链式存储结构中,逻辑上相邻的元素在物理位置上不一定相邻√6.在单链表中,可以从头结点开始查找任何一个元素╳7.线性表的链式存储结构优于顺序存储结构√8.在线性表的顺序存储结构中,插入和删除元素时,移动元素的个数与该元素的位置有关╳9.在单链表中,要取得某个元素,只要知道该元素的指针即可,因此,单链表是随机存取的存储结构╳10.顺序存储方式只能用于存储线性结构
三、填空题1.为了便于讨论,有时将含nn0个结点的线性结构表示成a1,a2,…,an,其中每个ai代表一个__结点_a1称为_第一个_结点,an称为__最后一个_结点,i称为ai在线性表中的_位置__对任意一对相邻结点ai、ai+11≤in,ai称为ai+1的直接_前驱_,ai+1称为ai的直接__后继__2.线性结构的基本特征是若至少含有一个结点,则除起始结点没有直接__前驱_外,其他结点有且仅有一个直接__前驱_;除终端结点没有直接__后继_外,其他结点有且仅有一个直接_后继__3.所有结点按一对一的邻接关系构成的整体就是__线性__结构4.线性表的逻辑结构是__线性_结构,其所含结点的个数称为线性表的___长度_5.在单链表中,删除p所指结点的直接后继的操作是__q=p-next;p-next=q-next;freeq;___·6.非空的单循环链表head的尾结点由指针p所指满足__p-next=head_____7.rear是指向非空带头结点的单循环链表的尾指针,则删除起始结点的操作可表示为__p=rear-next;q=p-next;p-next=q-next;freeq;____8.对于一个具有n个结点的单链表,在p所指结点后插入一个结点的时间复杂度为__O1__,在给定值为x的结点后插入新结点的时间复杂度为__On__9.单链表表示法的基本思想是用___指针___表示结点间的逻辑关系10.在顺序表中插入或删除一个元素,平均需要移动_一半_元素,具体移动的元素个数与__元素的位置_有关11.在一个长度为n的向量的第i1≤i≤n+1个元素之前插入一个元素时,需向后移动___n-i+1__个元素12.在一个长度为n的向量中删除第i1≤i≤n个元素时,需向前移动__n-i__个元素13.在双链表中,每个结点有两个指针域,一个指向___前驱__,另一个指向___后继___14.在一个带头结点的单循环链表中,p指向尾结点的直接前驱,则指向头结点的指针head可用p表示为head=__p-next-next;___15.设head指向单链表的表头,p指向单链表的表尾结点,则执行p-next=head后,该单链表构成__单循环链表___16.在单链表中,若p和s是两个指针,且满足p-next与s相同,则语句p-next=s-next的作用是_删除__s指向的结点17.设r指向单循环链表的最后一个结点,要在最后一个结点之后插入s所指的结点,需执行的三条语句是___s-next=r-next__;r-next=s;r=s;18.在单链表中,指针p所指结点为最后一个结点的条件是__p-next=NULL___19.在双循环链表中,若要在指p所指结点前插入s所指的结点,则需执行下列语句s-next=p;s-prior=p-prior;__p-prior-next__=s;p-prior=s;20.在单链表中,若要在p所指结点之前插入s所指的结点,可进行下列操作s-next=___p-next__;p-next=s;temp=p-data;p-data=__s-data___;s-data=__temp_;
四、应用题1.描述以下三个概念的区别头指针,头结点,首元结点第一个元素结点答首元结点是指链表中存储的线性表中的第一个数据元素的结点为了操作方便,通常在链表的首元结点之前附设一个结点,称为头结点头指针是指向链表中的第一个结点的指针2.何时选用顺序表,何时选用链表作为线性表的存储结构为宜?答从空间上来看,当线性表的长度变化较大、难以估计其规模时,选用动态的链表作为存储结构比较合适,但链表除了需要设置数据域外,还要额外设置指针域,因此当线性表长度变化不大、易于事先确定规模时,为了节约存储空间,宜采用顺序存储结构从时间上来看,若线性表的操作主要是查找,很少进行插入和删除操作时,应选用顺序表对于频繁进行插入和删除操作的线性表,宜采用链表作为存储结构3.在顺序表中插入和删除一个结点需平均移动多少个结点?具体的移动次数取决于哪两个因素?答平均移动表中大约一半的结点,插入操作平均移动n/2个结点,删除操作平均移动(n-1)/2个结点具体移动的次数取决于表长和插入、删除的结点的位置4.为什么在单循环链表中设置尾指针比设置头指针更好?答单循环链表中无论设置尾指针还是头指针都可以遍历表中任一个结点,但设置尾指针时,若在表尾进行插入或删除操作可在O1时间内完成,同样在表头进行插入或删除操作也可在O1时间内完成但若设置的是头指针,表尾进行插入或删除操作,需要遍历整个链表,时间复杂度为On5.双链表和单循环链表中,若仅知道指针p指向某个结点,不知道头指针,能否将结点*p从相应的链表中删除?若可以,其时间复杂度各为多少?答能删除双链表上删除p所指向的结点的时间复杂度为O1,单循环链表上删除p所指向的结点的时间复杂度为On6.下列算法的功能是什么?LinkListtestlLinkListL{//L是无头结点的单链表ListNode*q,*p;ifLL-next{q=L;L=L-next;p=L;whilep-nextp=p-next;p-next=q;q-next=NULL;}returnL;}答如果长度大于1,则将首元结点删除并插入到表尾7.如果有n个线性表同时共存,并且在处理过程中各表的长度会发生动态变化,线性表的总长度也会自动地改变在此情况下,应选择哪一种存储结构?为什么?答应选用链式存储结构因为顺序表是静态存储结构,只能预先分配,不能随着线性表长度的改变而变化而链表则可根据需要动态地申请空间,因此适用于动态变化表长的线性表8.若线性表的总数基本稳定,且很少进行插入、删除操作,但要求以最快的方式存取线性表的元素,应该用哪种存储结构?为什么?答应选用顺序存储结构因为顺序存储结构存取元素操作的时间复杂度为O1
五、算法设计题1.试用顺序表作为存储结构,实现将线性表a0,a1,a2,…an-1就地逆置的操作,所谓“就地”是指辅助空间为O1答1顺序表的就地逆置分析分别用两个整型变量指向顺序表的两端,同时向中间移动,移动的同时互换两个下标指示的元素的值voidSeqreverseSeqListL{//顺序表的就地逆置fori=0;j=L.1ength-1;ij;i++,j--{t=L.data[i];L.data[i]=L.data[j];L.data[j]=t;}}2链表的就地逆置分析本算法的思想是逐个地把L的当前元素r插入到新的链表头部voidLinkedreverseLinkedListL{//链表的就地逆置p=L-next;L-next=NULL;whilep!=NULL{r=p,p=p-next;//r指向当前待逆置的结点,p记下下—个结点r-next=L—next;L-next=r;//放到表头}}2.设顺序表L是一个递增允许有相同的值有序表,试写一算法将x插入L中,并使L仍为一个有序表答分析先找到x的正确插入位置,然后将大于x的元素从后向前依次向下移动,最后将x插入到其位置上,同时顺序表长度增1voidSeqListinsertSeqListL,intx{//x插入到递增有序的顺序表L中i=0;whilei=L.length-1x=L.data[i]i++;//找正确的插入位置fork=L.length-1;k=i;k--//元素从后往前依次后移L.data[k+1]L.data[k];L.datai]’x;//x插入到正确位置L.1ength++;
3.设单链表L是一个非递减有序表,试写一个算法将x插入其中后仍保持L的有序性答分析此问题的关键是在链表中找到x的插入位置,因此需要两个指针一前一后地依次向后移动voidLinkListinsertLinkedListL,intx{//x插入有序链表L中q=L;p=q—next;whilep!=NULLp—datax//找到插入的位置{q=p;p=p—next;}s=LinkedListmallocsizeofLNode;//生成新结点S—data=x;S—next=p;q—next=s;}
4.试写出在不带头结点的单链表的第i个元素之前插入一个元素的算法答分析对不带头结点的链表操作时,要注意对第一个结点和其他结点操作的不同voidLinkedListlnsertLinkedListhead,intx,inti{//不带头结点的单链表的第i个元素之前插入一个元素p=L j=1;whilep!=NULLji-1//找到第i-1个元素{p=p—next;j++;}ifi=0||p==NULLprintf”插入位置不正确\n”;else{q=LinkedListmallocsizeofLNode;q—data=x;ifi==1{q—next=L;L=q;}//在第一个元素之前插入else{q—next=p—next;p—next=q;}//在其他位置插入}}5.设A、B是两个线性表,其表中元素递增有序,长度分别为m和n试写一算法分别以顺序存储和链式存储将A和B归并成一个仍按元素值递增有序的线性表C答1分析用三个变量i、j、k分别指示A、B、C三个顺序表的当前位置,将A、B表中较小的元素写入C中,直到有一个表先结束最后将没结束的表的剩余元素写入C表中SeqListSeqmergeSeqListA,SeqListB{//有序顺序表A和B归并成有序顺序表Ci=0;j=0;k=0;//i,i,k分别为顺序表A,B,C的下标whileimjn{ifA.data[i]B.data[j]//A中当前元素较小{C.data[k]=A.data[il;i++;]else{C.data[k]=B.data[j];j++;}//B中当前元素较小k++;}ifi==mfort=j;tn;t++{C.data[k]=B.data[t];k++;}//B表长度大于A表elsefort=i;tm;t++{C.data[k]=A.data[t];k++;}//A表长度大于B表C.length=m+n;returnC;}2VOidLinkmergeLinkedListA,LinkedListB,LinkedListC{//有序链表A和B归并成有序链表Cpa=A—next;pb=B—next;C=A;pc=C;whilepapb//A和B都不为空时{ifpa—datapb—data//A当前结点值较小{qa=pa-next;pC-next=pa;pc=pc-next;pa=qa;}else{qb=pb-next;pc-next=pb pc=pc-next;pb=qb;}//B当前结点值较小}ifpapc—next=pa;//A没有结束,将A表剩余元素链接到C表ifpbpc—next=pb;//B没有结束,将B表剩余元素链接到C表freeB;//释放B表的头结点}本算法需要遍历两个线性表,因此时间复杂度为Om+n6.设指针la和lb分别指向两个不带头结点的单链表的首结点,设计从表la中删除第i个元素起共len个元素,并将这些元素插入到lb中第j个结点之前的算法答分析先在la中找到第i个结点,分别用两个指针pre和p指向第i-1和第i个结点,然后用指针q从第i个结点起向后走len个元素,使q指向此位置然后在lb中找到第j个结点,将p所指向的la表中的第i个及q所指向的最后一个共len个结点插入到lb中voidDeletelnsertLinkedListla,LinkedListlb,inti,intjintlen{//删除不带头结点的单链表la中第i个元素起共len个元素并将这峰元素插入到单链表lb中第j个结点之前ifi0||j0||len0exit0;p=la;k=1;pre=NULL;whilepki//在la表中查找第i个结点{pre=p;p=p-next;k++;}if!pexit0;q=p;k=l;//p指向la表中第i个结点whileqklen{q=q—next;k++;}//查找la表中第i+len-1个结点if!qexit0;ifpre==lala=q—next;//i=1的情况elsepre—next=q—next;//完成删除//将从la中删除的结点插入到lb中ifj==1{q-next=lb;lb=p;}//j=1时else{r=lb;k=1;//j1时whilerkj-1{r=r—next;k++;}//查找Lb表中第i—1个元素if!rexit0;q—next=r—next;r—next=p;//完成插入}}7.单链表L是一个递减有序表,试写一高效算法,删除表中值大于min且小于max的结点若表中有这样的结点,同时释放被删结点空间,这里min和max是两个给定的参数答LinkedListdeleteLinkedListL,intmin,intmax{//删除递减有序单链表L中值大于min且小于max的结点q=L;ifminmax{printf”minmax\n”;exit0;}elsep=L—next;//q始终指向p的前驱whilep—data=max//当前元素大于或等于max,则p、q依次向后移动{q=p;p=p—next;}whilep!=NULLp一datamin{//当前元素的值比min大同时比max小,删除p指向的结点q—next=p—next,freep;p=q—next;}returnL;}.8.编写一个算法将一个头结点指针为pa的单链表A分解成两个单链表A和B,其头结点指针分别为pa和pb,使得A链表中含有原链表A中序号为奇数的元素,而B链表中含有原链表A中序号为偶数的元素,且保持原来的相对顺序答分析用两个工作指针p和q分别指示序号为奇数和序号为偶数的结点,将q所指向的结点从A表删除,并链接到B表voiddecomposeLinkedListA,LinkedListB{//单链表A分解成元素序号为奇数的单链表A和元素序号为偶数的单链表Bp=A-next;B=LinkedListmallocsizeofLNode;r=B;whilep!=NULLp-next!=NULL{q=p—next;//q指向偶数序号的结点p—next=q—next;//将q从A表中删除r—next=q;//将q结点链接到B链表的末尾r=q;//r总是指向B链表的最后—·个结点p=p—next;//p指向原链表A中的奇数序号的结点}r—next=NULL;//将生成B链表中的最后一个结点的next域置为空}9.假设以两个元素依值递增有序排列的线性表A、B分别表示两个集合,要求另辟空间构造一个线性表C,其元素为两集合的交集,且表C中的元素也依值递增有序排列对顺序表编写求C的算法答分析用三个变量i、j、k分别指示A、B、C三个顺序表的当前位置,若A、B表中当前元素值相同,则写入C中,并使i、j、k值增1;若A表元素值较小,则使i增1;若B表元素值较小,则使j增1,直到有一个表先结束SeqLiStintersectionSeqListA,SeqListB,SeqListC{//求元素依值递增有序排列的顺序表A、B的交集Ci=0;j=0;k=0;whilei=A.length-1j=B.length-1{ifA.data[i]==B.data[j]//找到值相同的元素{C.data[k]=A.data[i];//相同元素写入C表中k++;i++;j++;}elseifA.data[i]B.data[j]i++;//A、B表当前元素不等,值较小的下标增1elsej++;}C.length=k;returnC;}10.设有线性表A=a1,a2,…,am和B=b1,b2,…,bn试编写合并A、B为线性表C的算法,使得C=a1,b1,…,am,bm,bm+1,…bn当m≤n时或a1,b1,…,an,bn,an+1,…am(当mn时),线性表A、B、C均以单链表作为存储结构,且C表利用A表和B表的结点空间答分析使p和q指向A和B表当前元素,并分别使nextp和nextq指向p和q的后继,这样将q所指向的结点链接到p的后面,再把nextp和nextq的值赋给p和q,处理下一个结点voidmergeLinkedListA,LinkedListB,LinkedListC{//把链表A和B合并为C,A和B的元素间隔排列,且使用原存储空间p=A—next;q=B—next;C=A;whilepq{nextp=p—next;p—next=q;//将B的元素插入ifnextp{nextq=q-next;q-next=nextp;}//如果A非空,将A的元素插入p=nextp;q=nextq;}}11.假设在长度大于1的单循环链表中,既无头结点也无头指针s为指向链表中某个结点的指针,试编写算法删除结点*s的直接前驱结点答分析因为既不知道此单循环链表的头指针,也不知道其尾指针,所以找s的前驱就只能从s开始,顺次向后寻找voidDeletePreLinkedNode*s{//删除单循环链表中结点s的直接前驱p=s;whilep—next—next!=sp=p—next;//找到s的前驱的前驱pq=p—next;//q是p的后继,即s的前驱p—next=s;//将q删除freeq;}12.计算带头结点的循环链表的结点个数答intnumberLinkedNodehead{//计算单循环链表中结点的个数p=head—next;i=0;whilep!=head{i++;p=p-next;}returni;}13.已知由单链表表示的线性表中,含有三类字符的数据元素如字母字符、数字字符和其他字符,试编写算法构造三个以循环链表表示的线性表,使得每个表中只含有同一类的字符,且利用原表中的结点空间作为这三个表的结点空间,头结点可另辟空间答分析p指向待处理的单链表的首元结点,构造三个空的单循环链表,分别存储三类字符,其中一个可使用原来的单链表q指向p的下一个结点,根据*p的数据域的值将其插入到不同的链表上再把q的值给p,处理下一个结点voidchangeLinkedListL,LinkedListpa,LinkedListpb,LinkedListpc{//分解含有三类字符的单链表为三个以循环链表表示的线性表,使其分别含有三类字符p=L—next;pa=L;pa—next=pa;//分别构造三个单循环链表pb=LinkedListmallocsizeofLNode;pc=LinkedListmallocsizeofLNode;pb—next=pb;pc—next=pc;whilep!=L{q=p—next;·//q记下L中下一个结点的位置ifp—data=’z’p—data=’a’//链接到字母链表的头部{p—next=pa—next;pa—next=p;}elseifp—data=’9’p—data=’0’//链接到数字链表的头部{p—next=pb—next;pb—next=p;}else{p-next=pc-next;pc-next=p;}//链接到其他字母链表的头部p=q;}}
14、己知A、B和C为三个递增有序的线性表,现要求对A表进行如下操作删去那些既在B表中出现又在C表中出现的元素试对顺序表编写实现上述操作的算法注题中未特别指明同一表中的元素值各不相同答分析先从B和C中找出共有元素,记为same,再在A中从当前位置开始,凡小于same的元素均保留存到新的位置,等于same的就跳过,到大于same时就再找下一个SameSeqListIntersectDeleteSeqListA,SeqListB,SeqListC{//对顺序表A删去那些既在B表中出现又在C表中出现的元素i=0;j=0;k=0;m=0;//i指示A中元素原来的位置,m为移动后的位置whileiA.lengthiB.lengthkC.length{ifB.data[j]C.data[k]j++;elseifB.data[j]C.data[k]k++;else{same=B.data[j];//找到了相同元素samewhileB.data[j]==samej++;whileC.data[k]==samek++;/j、k后移到新的元素whileiA.lengthA.data[i]sameA.data[m++]=A.data[i++];//需保留的元素移动到新位置whileiA.1engthA.data[i1==same]i++;//跳过相同的元素}}whileiA.lengthA.data[m++]=A.data[i++];//A的剩余元素重新存储A.1ength=m;}15.双循环链表中,设计满足下列条件的算法1在值为x的结点之前插入值为y的结点2在值为x的结点之后插入值为y的结点3删除值为x的结点答分析在双循环链表中插入和删除结点要注意修改双向的指针typedefstructDLNode{DataTypedata;structDLNode*prior,*next;}DLNode,*DLinkedList;voidDLinsertlDLinkedListL,intx,inty{//在双循环链表中插入结点p=L-next;whilep!=Lp-data!=xp=p-next;//在链表中查找值为x的结点ifp-data==x//找到值为x的结点{q=p-prior;//q指向值为x的结点的前驱s=DLinkedListmallocsizeofDLNode;s-data=y;s-next=p;s-prior=q;//将y插入到q与p指向的结点之间p-prior=s;q-next=s;}else{printf”没有值为x的结点”;exit0;}}voidDLDeleteDLinkedListL,intx{//在双循环链表中删除结点p=L-next;whilep!=Lp-data!=xp=p-next;ifp-data==x{p-prior-next=p-next;p-next-prior=p-prior;freep;}else{printf”没有值为x的结点”;exit0;}}16.设有一个双循环链表,其中有一结点的指针为p,编写算法将p与其右边的一个结点进行交换答voidDLchangeDLinkedListp{//将双循环链表中p指向的结点与其右边的一个结点进行交换q=p—next;//q指向p的后继p—prior—next=q;q—prior=p—prior;//将p的前驱与q相链接p—next=q—next;p—prior=q;//将p插入到q之后q-next—prior=p;q—next=p;}17.设有一个双链表,每个结点中除有prior、data和next三个域外,还有一个可访问颊度域freq,在链表启用之前,其值均初始为0每当链表进行一次LocateNodeL,x操作时令元素值为x的结点中freq域的值加l,并调整表中结点的次序,使其按访问频度的递减次序排列,以便使频繁访问的结点总是靠近表头试写一符合上述要求的LocateNode操作的算法答分析先在双链表中查找值为x的结点,若找到则使其freq值增1,然后从头至尾扫描链表,将此结点插入到按freq递减顺序排列的正确位置typedefstructDLNode{intdata,freq;structDLNode*prior,*next;}DLNode,*DLinkedList;voidLocateNodeDLinkedListhead,intx{//双链表按访问频度域freq递减次序排列p2=head;p1=p2—next;//p2在前,p1在后whuep1//查找单链表中值为x的结点ifpl—data==x{pl—freq++;break;}//使值为x的结点的freq加1else{p2=pl;p1=p2—next;}ifp1==NULLprintf”Notfound.\n”;else{ifp1—next==NULL{p2—next=p1—next;temp=p1;}//在链表中找temp所指向的结点,按freq值递减应插入的位置else{p2—next=p1—next;//插入链表中间的某一位置p1—next-prior=p2;temp=pl;}forp2=head,p1=p2-next;plp1-freqtemp-freq;p2=p1,pl=p2-next;//插入ifp1==NULL{p2-next=temp;temp-prior=p2;temp-next=NULL;}else{p2-next=temp;temp-prior=p2;temp-next=pl;p1-prior=temp;}}}18.给出用单链表存储多项式的结构,并编写一个按指数值递增次序输入所产生的多项式链表的过程答typedefstructPNode{intcoef;//系数intexp;//指数structPnode*next;}*PLink;PLinkCreatPoly{//建立多项式head=PLinkmallocsizeofstructPNode;r=head;printf”输入系数和指数”;scanfn,m;whilen!=0//若n=0则退出循环{s=PlinkmallocsizeofstructPNode;s-coef=n;s-exp=m;r-next=s;r=s;//把s链接到r的后面printf”输入系数和指数:”;scanfn,m;}r-next=NULL;head=head—next;//删除头结点returnhead;}19.根据上题的多项式链表结构,编写一个过程实现两个多项式相加的运算答分析对所有指数相同的项,将其对应系数相加,若和不为0,则构造新“和多项式”的结点;将所有指数不同的项复制到和多项式中PlinkaddPLinkpa,PLinkpb{//多项式相加p=pa;q=pb;pc=PLinkmallocsizeofstructPNode;r=pc;whilep!=NULLq!=NULL{ifp-exp==q-exp//两结点的指数相同时,将两系数相加生成新结点插入c中{x=p-coef+q-coef;ifx!=0{s=PLinkmallocsizeofstructPNode;s-coef=x;s-exp=p-exp;r-next=s;r=s;}p=p-next;q=q-next;}elseifp-expq-exp//两结点的指数不同时,将较小系数的结点复制成新结点插入c中{s=PLinkmallocsizeofstructPNode;s-coef=q-coef;s-exp=q-exp;r-next=s;r=s;q=q-next;}else{s=PLinkmallocsizeofstructPNode;s-coef=p-coef;s-exp=p-exp;r-next=s;r=s;p=p-next;}}whilep!=NULL//复制A的余下部分{s=PLinkmallocsizeofstructPNode;s-coef=p-coef;s-exp=p-exp;r-next=s r=s;p=p-next;}whileql=NULL//复制B的余下部分{s=PLinkmallocsizeofstructPNode;s-coef=q-coef;s-exp=q-exp;r-next=s;r=s;q=q-next;}r-next=NULL;//最后结点的next域置为空s=pc;pc=pc-next;//删除c的头结点frees;returnpc;}20.约瑟夫环问题任给正整数n、k,按下述方法可得排列1,2,…,n的一个置换将数字l,2,…,n环形排列,按顺时针方向从1开始计数;计满k时输出该位置上的数字并从环中删去该数字,然后从下一个数字开始继续计数,直到环中所有数字均被输出为止例如,n=
10、k=3时,输出的置换是3,6,9,2,7,1,8,5,10分别以数组和以不带头结点的、已知尾指针的单循环链表为存储结构解决上述问题答voidJs1intA[n],intN,ihtK{//以数组为存储结构fori=0;iN;i++A[I]=1;//用1标志在环上的结点j=0;fori=0;iN;i++{s=0;whilesK{j=j%N+1;s=s+A[j-1];}//计数printf”%d”,j;A[j-1]=0;//将计满k值的数字输出,并将其位置标为0表明已删除}}voidJs2LinkedListlast,intN,intK{//以不带头结点的、已知尾指针的单循环链表为存储结构p=last;q=p-next;//此时q为头结点fp为q的前驱whileN0{forj=2;j=K;j++//循环K-1次{p=q;q=p-next;}printf”%d”,q-data;N--;p-next=q-next;//删除qq=p—next;}}第三节栈和队列
一、选择题1.设有一顺序栈s,元素s1,s2,s3,s4,s5,s6依次入栈,如果6个元素出栈的顺序是s2,s3,s4,s6,s5,s1,则栈的容量至少应该是A.2*B.3C.5D.62.若一个栈的输入序列是a、b、c,则通过入栈、出栈操作可能得到a、b、c的不同排列个数为A.4*B.5C.6D.73.设有一顺序栈已经含有3个元素,如图3-1所示,元素a4正等待入栈以下序列中不可能出现的出栈序列是*A.a3,a1,a4,a2B.a3,a2,a4,a1C.a3,a4,a2,a1D.a4,a3,a2,a14.和顺序栈相比,链栈有一个比较明显的优势是*A.通常不会出现栈满的情况B.通常不会出现栈空的情况C.插入操作更容易实现D.删除操作更容易实现5.若一个栈的输入序列是1,2,3,4,…,n,输出序列的第一个元素是n,则第i个输出元素是A.不确定B.n-i*C.n-i+1D.n-i-16.以下说法正确的是*A.因链栈本身没有容量限制,故在用户内存空间的范围内不会出现栈满情况B.因顺序栈本身没有容量限制,故在用户内存空间的范围内不会出现栈满情况C.对于链栈而言,在栈满状态下,如果再进行入栈操作,则会发生“上溢”D.对于顺序栈而言,在栈满状态下,如果再进行入栈操作,则会发生“下溢”7.顺序队列的入队操作应为*A.sq.rear=sq.rear+1;sq.data[sq.rear]=x;B.sq.data[sq.rear]=x;sq.rear=sq.rear+1;C.sq.rear=sq.rear+1%maxsize;sq.data[sq.rear+1]=x;D.sq.data[sq.rear]=x;sq.rear=x;sq.rear=sq.rear+1%maxslze;8.循环队列的入队操作应为A.sq.rear=sq.rear+1;sq.data[sq.rear]=xB.sq.data[sq.rear]=x;sq.rear=sq.rear+l;*C.sq.rear=sq.rear+1%maxsize;sq.data[sq.rear]=x;D.sq.data[sq.rear]=x;sq.rear=sq.rear+1%maxsize;9.顺序队列的出队操作为A.sq.front=sq.front+1%maxsize;*B.sq.front=sq.front+1;C.sq.rear=sq.rear+1%maxsize;D.sq.rear=sq.rear+1;10.循环队列的出队操作为*A.sq.front=sq.front+1%maxsize;B.sq.front=sq.front+1;C.sq.rear=sq.rear+1%maxsize;D.sq.rear=sq.rear+l;11.循环队列的队满条件为A.sq.rear+1%maxsize==sq.front+1%maxsize;B.sq.rear+1%maxsize==sq.front+1;*C.sq.rear+1%maxsize==sq.front;D.sq.rear==sq.front;12.循环队列的队空条件为A.sq.rear+1%maxsize==sq.front+1%maxsize;B.sq.rear+1%maxsize==sq.front+1;C.sq.rear+1%maxsize==sq.front;*D.sq.rear==sq.front;13.如果以链表作为栈的存储结构,则出栈操作时A.必须判别栈是否满B.判别栈元素的类型*C.必须判别栈是否空D.对栈不做任何判别14,向一个栈顶指针为Top的链栈中插入一个s所指结点时,其操作步骤为A.Top-next=s;B.s-next=Top-next;Top-next=s;*C.s-next=Top;Top=s;D.s-next=Top;Top=Top-next;15.从栈顶指针为Top的链栈中删除一个结点,并将被删结点的值保存到x中,其操作步骤为*A.x=Top-data;Top=Top-next;B.Top=Top-next;x=Top-data;C.x=Top;Top=Top-next;D.x=Top-data;16.在一个链队中,苕f、r分别为队头、队尾指针,则插入s所指结点的操作为A.f-next=s;f=s;*B.r-next=s;r=s;C.s-next=r;r=s;D.s-next=f;f=s;17.一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是A.e,d,c,b,aB.d,e,c,b,a*C.d,c,e,a,bD.a,b,c,d,e18.一个队列的入队序列是1,2,3,4,则队列的可能的输出序列是A.4,3,2,1*B.1,2,3,4C.1,4,3,2D.3,2,4,119.设计一个判别表达式中左,右括号是否配对出现的算法,采用数据结构最佳A.线性表的顺序存储结构*B.栈C.队列D.线性表的链式存储结构
二、判断题√1.在顺序栈栈满情况下,不能再入栈,否则会产生“上溢”╳2.与顺序栈相比,链栈的一个优点是插入和删除操作更加方便╳3.若一个栈的输入序列为1,2,3,…,n,其输出序列的第一个元素为n,则其输出序列的每个元素ai一定满足ai=i+1i=1,2,…,n√4.在链队中,即使不设置尾指针也能进行入队操作√5.在对链队带头指针做出队操作时,不会改变front指针的值╳6.循环队列中元素个数为rear-front╳7.一个栈的输入序列是1234,则在栈的输出序列中可以得到4312.√8.一个栈的输入序列是1234,则在栈的输出序列中可以得到1234╳9.若以链表作为栈的存储结构,则入栈需要判断栈是否满.√10.若以链表作为栈的存储结构,则出栈需要判断栈是否空
三、填空题1.向一个栈顶指针为Top的链栈中插入一个s所指的结点时,其进行的操作是__s-next=Top;Top=s;__2.从栈顶指针为Top的链栈中删除一个结点,并将结点保存在x中,进行的操作是_x=Top-data;Top=Top-next;__3.在具有n个单元的循环队列中,队满时共有___n-1_个元素4.假设以S和X分别表示入栈和出栈操作,则对输入序列a,b,c,d,e进行一系列栈操作SSXSXSSXXX之后,得到的输出序列为__b,c,e,d,a___5.设有数组A[m]作为循环队列的存储空间,front为队头指针,rear为队尾指针,则元素x执行入队操作的语句是_rear=(rear+1)%(m+1);A[rear]=x;__6.在一个链队中,如果f、r分别为队头、队尾指针,则插入s所指结点的操作是_r-next=s;r=s;___7.栈的逻辑特点是__后进先出____,队列的逻辑特点是_先进先出__,二者的共同特点是_操作受限__8.___栈___可以作为实现递归函数调用的一种数据结构9.在队列中,新插入的结点只能添加到__队尾__10.链队在一定范围内不会出现__队满___的情况当lq.front==lq.rear时,队中无元素,此时___队空__11.设一个链栈的栈顶指针为ls,栈中结点的格式为data:next,栈空的条件是_ls=NULL__;如果栈不为空,则出栈操作为p=ls;___ls=ls-next__;freep12.对带有头结点的链队lq,判定队列中只有一个数据元素的条件是__lq-front-next=lq-rear___13.设有一个空栈,现在输入序列为1,2,3,4,5,经过push,push,pop,push,pop,push后,栈顶指针所指元素是__4__14.设用一维数组A[ln]来表示一个栈,令A[n]为栈底用整型变量t来指示当前栈顶的位置,A[t]为栈顶元素往栈中压入一个新元素时,变量t的值__加1___,从栈中弹出一个元素时,变量t的值___减1___设空栈时,输入序列a,b,c经过push,pop,push,push,pop操作后,从栈中弹出的元素是___c__
四、应用题1.试证明若借助栈由输入序列1,2,3,…,n得到输出序列p1,p2,…,pn它是输入序列的一个排列,则在输出序列中不可能出现这样的情形存在ijk,使pipjpk答p542.设有字符串为3*-y-a/y^2,试利用栈写出将其转换为3y-*ay2^/-的操作过程假定用x代表扫描该字符串过程中顺序取一个字符入栈的操作,用s代表从栈中取出一个字符加入到新字符串尾的出栈操作例如,ABC变为BCA的操作步骤为XXSXSS答XSXXXSSSXXSXXSXXSSSS3.设有一个输入序列a,b,c,d,元素经过一个栈到达输出序列,而且元素一旦离开输入序列就不能再回到输入序列,试问经过这个栈后可以得到多少种输出序列答可以得到13种输出序列abcdabdcacbdacdbadcbbacdbcadbcdabdcacbadcbdacdbadcba.4.按照运算符优先法,画出对下面算术表达式求值时,操作数栈和运算符栈的变化过程9-2*4+8+1/3答序号运算符栈操作数栈输入字符1#92#9-3#-924#-92*5#-*9246#-*924+7#-988#19#+110#+1811#+18+12#++18113#++18114#+19/15#+/19316#+/193#17#+1318#45.链栈中为何不设置头结点答因为链栈只在链表头插入和删除结点,不可能在链表中间插入或删除结点,算法实现很简单,所以一般不设置头结点第五节树树根结点的高度为1
一、选择题1.以下说法错误的是*A.树形结构的特点是一个结点可以有多个直接前驱B.线性结构中的一个结点至多只有一个直接后继C.二叉树与树是两种不同的数据结构D.树及一切树形结构是一种“分支层次’结构2.以下说法错误的是A.二叉树可以是空集B.二叉树的任一结点都有两棵子树*C.二叉树与树具有相同的树形结构D、二叉树中任一结点的两棵子树有次序之分3.以下说法错误的是A.完全二叉树上结点之间的父子关系可由它们编号之间的关系来表达B.在三叉链表上,二叉树的求双亲操作很容易实现C.在二叉链表上,求根以及求左、右孩子等操作很容易实现*D.在二叉链表上,求双亲操作的时间性能很好4.以下说法错误的是A.一般在哈夫曼树中,权值越大的叶子离根结点越近B.哈夫曼树中没有度数为1的分支结点C.若初始森林中共有n棵二叉树,最终求得的哈夫曼树共有2n-1个结点*D.若初始森林中共有n棵二叉树,进行2n-1次合并后才能剩下一棵最终的哈夫曼树5.深度为6的二叉树最多有个结点A.64*B.63C.32D.316.将含有41个结点的完全二叉树从根结点开始编号,根为1号,后面按从上到下、从左到右的顺序对结点编号,那么编号为21的双亲结点编号为*A.10B.11C.41D.207.任何一棵二叉树的叶结点在其前序、中序、后序遍历序列中的相对位置A.肯定发生变化B.有时发生变化*C.肯定不发生变化D.无法确定8.设二叉树有n个结点,则其深度为A.n-1B.nC.└log2n┘+1*D.无法确定9.设深度为k的二叉树上只有度为0和度为2的结点,则这类二叉树上所含结点总数最少个A.k+lB.2k*C.2k-1D.2k+110.下列说法正确的是*A.树的前序遍历序列与其对应的二叉树的前序遍历序列相同B.树的前序遍历序列与其对应的二叉树的后序遍历序列相同C.树的后序遍历序列与其对应的二叉树的前序遍历序列相同D.树的后序遍历序列与其对应的二叉树的后序遍历序列相同11.下列说法中正确的是A.任何一棵二叉树中至少有一个结点的度为2B.任何一棵二叉树中每个结点的度都为2C.任何一棵二叉树中的每个结点的度肯定等于2*D.任何一棵二叉树中的每个结点的度都可以小于212.一棵二叉树满足下列条件对任意结点,若存在左、右子树,则其值都小于它的左子树上所有结点的值,而大于右子树上所有结点的值现采用遍历方式就可以得到这棵二叉树所有结点的递减序列A.前序*B.中序C.后序D.层次13.设森林T中有4棵树,结点个数分别是n
1、n
2、n
3、n4,当把森林T转换成一棵二叉树后,根结点的右子树上有个结点A.n1-1B.n1C.n1+n2+n3*D.n2+n3+n414.对含有个结点的非空二叉树,采用任何一种遍历方式,其结点访问序列均相同A.0*B.1C.2D.不存在这样的二叉树15.如图6-1所示的二叉树的中序遍历序列是A.abcdgef*B.dfebagcC.dbaefcgD.defbagc16.已知某二叉树的后序遍历序列是deacb,中序遍历序列是deabc,它的前序遍历序列是A.acbed*B.baedcC.dceabD.cedba17.如果T1是由有序树转化而来的二叉树,那么T中结点的前序就是T1中结点的*A.前序B.中序C.后序D.层次序18.某二叉树的前序遍历的结点访问顺序是abdgcefh,中序遍历的结点访问顺序是dgbaechf,则其后序遍历的结点访问顺序是A.bdgcefhaB.gdbecfhaC.bdgechfa*D.gdbehfca19.在图6-2中的二叉树中,不是完全二叉树(*C)20.树最适合用来表示A.有序数据元素B.无序数据元素*C.元素之间具有分支层次关系的数据D.元素之间无联系的数据21.在计算递归函数时,如不使用递归过程,则一般情况下必须借助于数据结构*A.栈B.树C.双向队列D.顺序表22.设二叉树根结点的层次为0,一棵高度为h的满二叉树中的结点个数是A.2hB.2h-1C.2h-1*D.2h+1-123.以下说法错误的是A.存在这样的二叉树,对它采用任何次序的遍历,其结点访问序列均相同*B.二叉树是树的特殊情形C.由树转换成二叉树,其根结点的右子树总是空的D.在二叉树只有一棵子树的情况下也要明确指出该子树是左子树还是右子树24.已知一个算式的中缀表达式为a+b-c/d,则其后缀表达式是A.a+b-c/d*B.abc-d/+C.bc-d/a+D.a+bc-d/25.按照二叉树的定义,具有4个结点所能构造的不同的二叉树的个数是A.4B.8C.12*D.1426.在一棵度为3的树中,度为3的结点的个数为2,度为2的结点的个数为1,则度为0的结点的个数为A.4B.5*C.6D.727.3个结点可构成棵不同形态的二叉树A.2B.3C.4*D.528.哈夫曼树的带权路径长度是A.所有结点权值之和*B.所有叶结点带权路径长度之和C.带权结点的值D.除根以外所有结点权值之和29.设有一棵22个结点的完全二叉树,那么整棵二叉树有个度为0的结点A.6*B.7C.8D.1130.已知完全二叉树有26个结点,则整棵二叉树有个度为1的结点A.0B.1C.2*D.1331.在树的孩子兄弟表示法中,操作花时间最多A.求某结点的兄弟*B.求某结点的第i个孩子C.求某结点的父结点D.求树的根结点32.已知如图6-3所示的哈夫曼树,那么电文CDAA的编码是A.110100B.11011100*C.010110111D.1111110033.在n个结点的完全二叉树中,对任一结点i1≤i≤n,i的左孩子可能是A.i/2*B.2i+1C.2iD.都不是34.已给出图6-3所示的二叉树,A,B,C,D的权值分别为7,5,2,4,则该树的带权路径长度为A.46*B.36C.35D.都不是35.下列叙述中正确的是A.二叉树是度为2的有序树B.二叉树中结点只有一个孩子时无左右之分*C.二叉树中必有度为2的结点D.二叉树中结点最多有两棵子树,并且有左右之分36.图6-4所示的几种结构中属于树形结构的是(*C)
二、判断题╳1.二叉树是树的特殊形式√2.树和二叉树之间最主要的差别是二叉树的结点的子树要区分为左右子树,即使在结点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树√3.一棵有n个结点的d度树,若用多重链表表示,树中每个结点都有d个链域,则在树的n*d个链域中,有n*d-1+1个是空链域,只有n-1个是非空的√4.前序遍历树和前序遍历与该树对应的二叉树,其结果相同╳5.中序遍历树和中序遍历与该树对应的二叉树,其结果不同√6.前序遍历森林和前序遍历与该森林对应的二叉树,其结果相同╳7.中序遍历森林和中序遍历与该森林对应的二叉树,其结果不同√8.若有一个结点是某二叉树子树的中序遍历序列中的最后一个结点,则它必须是该子树的前序遍历序列中的最后一个结点√9.二叉树具有两个子女的父结点,在中序遍历序列中,它的后继结点最多只能有一个子女╳10.在二叉树中,具有一个子女的父结点,在中序遍历中,它没有后继的子女结点╳11.在二叉树中插入结点,该二叉树便不再是二叉树╳12.用一维数组存储二叉树时,总是以前序遍历存储结点√13.已知二叉树的前序遍历和后序遍历序列不能惟一地确定这棵树√14.不使用递归,也可以实现二叉树的前序、中序、后序遍历√15.在前序遍历二叉树的序列中,任何结点的子树的所有结点都是直接跟在该结点之后╳16.有n个结点的不同二叉树有n!棵╳17.在哈夫曼编码中,当两个字符出现的频率相同时,其编码也相同,对于这种情况应做特殊处理
三、填空题1.树及一切树形结构是一种__层次__结构在树中,__根_结点没有直接前驱对树上任一结点x来说,x是它的任一子树的根结点惟一的_双亲_2.一棵树上的任何结点不包括根本身称为根的__子孙__若B是A的子孙,则称A是B的__祖先__3.二叉树第ii0层上至多有__2i-1__个结点4.深度为kk0的二叉树至多有__2k-1__个结点5.对任何二叉树,若度为2的节点数为n2,则叶子数n0=__n2+1__6.满二叉树上各层的节点数已达到了二叉树可以容纳的__最大值_满二叉树也是__完全__二叉树,但反之不然7.具有n个结点的完全二叉树的深度为___│log2n│+1___8.在顺序存储的二叉树中,编号为i和j的两个结点处在同一层的条件是__│log2i│=│log2j│____9.如果将一棵有n个结点的完全二叉树按层编号,则对任一编号为i0in+1的结点x,有1若i=1,则结点X是__根__;若il,则X的双亲PARENTX的编号为__│i/2│___2若2in,则结点x无__左孩子__且无__右孩子__;否则,X的左孩子LCHILDX的编号为__2i__3若2i+1n,则结点X无__右孩子__;否则,X的右孩子RCHILDX的编号为__2i+1__10.二叉树通常有___顺序____存储结构和___链式__存储结构两类存储结构11.每个二叉链表还必须有一个指向__根__结点的指针,该指针具有标识二叉链表的作用12.对二叉链表的访问只能从___根__指针开始13.具有n个结点的二叉树中,一共有__2n__个指针域,其中只有__n-1_个用来指向结点的左右孩子,其余的__n+1__个指针域为NULL14.已知二叉树中叶子数为40,仅有一个孩子的结点数为20,则总结点数为__99___15.二叉树有不同的链式存储结构,其中最常用的是_二叉链表___与__三叉链表__16.可通过在非完全二叉树的“残缺”位置上增设__空指针___将其转化为完全二叉树17.具有100个结点的完全二叉树的深度是__7___18.深度为90的满二叉树上,第10层有___512___个结点19.在__前序__遍历二叉树的序列中,任何结点的子树上的所有结点都是直接跟在该结点之后20.具有n个结点的完全二叉树,若按层次从上到下、从左到右对其编号根结点为1号,则编号最大的分支结点序号是__│n/2│___,编号最小的分支结点序号是__1_,编号最大的叶结点序号是_n_,编号最小的叶结点序号是__│n/2│+1____21.若一棵二叉树的叶子数为n,则该二叉树中左、右子树皆非空的结点个数为__n-1__22.任意一棵具有n个结点的二叉树,若它有m个叶子,则该二叉树上度数为1的结点为__n-2m+1__个23.设有30个值,用它们构造一棵哈夫曼树,则该哈夫曼树中共有___59__个结点24.现有按中序遍历二叉树的结果为ABC,有__5___种不同形态的二叉树可以得到这一遍历结果25.以数据集{4,5,6,7,10}为叶结点的权值所构造的哈夫曼树的带权路径长度为_53_.26.已知一棵度为3的树有2个度为1的结点,3个度为2的结点,4个度为3的结点,则该树中有__12_个叶结点27.设树T的度为4,其中度为
1、
2、3和4的结点个数分别是
4、
2、1和1,则T中叶结点的个数是__8_28.如果结点a有三个兄弟,而b是a的双亲,则b的度是__4__29.一棵树的形状如图6-5所示,它的根结点是__A_,叶结点是__EJKLOPQRNI__,结点H的度是__3__,这棵树的度是_4_,这棵树的深度是__5__,结点F的儿子结点是_JK__,结点G的父结点是__C__30.设结点x有左孩子结点y、右孩子结点z,用三种基本遍历方法得到的遍历序列中x__不一定___是y的前驱,x__不一定__是z的后继,y__一定__是z的前驱填“一定”,“不”、“不一定”31.在树结构里,有且仅有一个结点没有前驱,称为根非根结点有且仅有一个_前驱__,且存在一条从根到该结点的__惟一路径__32.含有2n个结点的二叉树高度至少是__n+1___,至多是__2n_仅含根结点的二叉树高度为133.设高度为h的二叉树只有度为0和2的结点,则此类二叉树的结点数至少为_2h-1__,至多为__2h-1__
四、应用题1.分别画出含3个结点的树与二叉树的所有不同形态答P1002.设在树中,结点x是结点y的双亲,用x,y来表示边已知一棵树边的集合为{ij,,i,k,b,e,e,i,b,d,a,b,c,g,c,f,c,h,a,c},用树形表示法画出此树,并回答下列问题1哪个是根结点?2哪些是叶结点?3哪个是g的双亲?4哪些是g的祖先?5哪些是e的子孙?6哪些是f的兄弟?7结点b和j的层次各是多少?8树的深度是多少?9树的度数是多少?答略3.任意一个有nn0个结点的二叉树,已知它有m个叶结点,试证明非叶结点有m-1个度为2,其余度为1答设度为1的结点数n1设度为2的结点数n2分支数B则有:m+n1+n2=nB+1=nB=1*n1+2*n2即:m+n1+n2=nn1+2n2+1=n解之可得:n2=m-14.分别画出图6-6所示二叉树的二叉链表、三叉链表和顺序存储结构答略.5.分别写出图6-7所示二叉树的前序、中序和后序序列答前序ABCDEF、中序CBEFDA和后序CFEDBA6.已知一棵二叉树的中序序列和后序序列分别为BDCEAFHG和DECBHGFA,试画出这棵二叉树,并写出其前序遍历序列答前序遍历序列ABCDEFGH7.二叉树中的结点进行按层次顺序每层自左到右的访问操作称为二叉树的层次遍历,遍历所得到的结点序列称为二叉树的层次序列现已知一棵二叉树的层次序列为ABCDEFGHIJ,中序序列为DBGEHJACIF,请画出该二又树答略.8.将图6-9所示的森林转换成二叉树答略.9.分别画出图6-10所示二叉树对应的森林,并写出森林的前序和后序遍历序列答前序ABDGCEFHIJK,后序DGBAECIHJKF10.设某密码电文由8个字母组成,每个字母在电文中的出现频率分别是7,19,2,6,32,3,21,10,试为这8个字母设计相应的哈夫曼编码答略.11.将代数式y=3*x+a-a/x2描述成表达式树,并写出前缀式和后缀式答前缀式-*3+xa/a*xx,后缀式:3xa+*axx*/-13.试证明任一棵高度为h1的二叉树,其内部结点除根、叶子之外的结点的数目小于2h-1-1,而叶结点数目小于或等于2h-1答高度为h的满二叉树包含的结点个数最多最下层是叶子除根外其余是内部结点不包含叶子的子树高度是h-1该子树的最多结点数是2h-1-
1.除根外内部结点的数目应小于2h-1-
1.而整个树所含的最多结点数是2h-1所以叶子数最多为2h-1-2h-1-1=2h-1个.14.编码{00,01,10,11}、{0,1,00,11,}、{0,10,110,111}哪一组不是前缀码答编码{00,01,10,11}、{0,10,110,111}是前缀码{0,1,00,11}不是前缀码.15.一棵度为k的树有n1个度为1的结点,n2个度为2的结点,……,nk个度为k的结点,问该树中有多少个叶结点答n=n0+n1+……+nk=1*n1+2*n2+……k*nkn0=1+n2+2n3+……+k-1nk16.一棵含有n个结点的k叉树,可能达到的最大深度和最小深度各是多少答最大深度n,最小深度│logknk-1│+117.画出和已知序列对应的树T树的前序序列为ABCEFDGH;树的后序序列为BEFCHGDA答略.
五、算法设计题1.以二叉链表作为存储结构,试编写求二叉树深度的算法答intbdepthbtreet{ift==NULLreturn0;else{l=bdephtt-lchild;r=bdephtt-rchild;returnlr?l:r+1;}}2.以二叉链表作为存储结构,试编写求二叉树中叶子数的算法答略.第七节查找
一、选择题1.顺序查找法适合于存储结构的查找表A.压缩B.散列C.索引*D.顺序或链式2.对采用折半查找法进行查找操作的查找表,要求按方式进行存储A.顺序存储B.链式存储*C.顺序存储且结点按关键字有序D.链式存储且结点按关键字有序3.设顺序表的长为n,用顺序查找法则其每个元素的平均查找长度是*A.n+1/2B.n-1/2C.n/2D.n4.设有序表的关键字序列为1,4,6,10,18,35,42,53,67,71,78,84,92,99,当用折半查找法查找键值为35的结点时,经次比较后查找成功A.2B.3*C.4D.65.长度为10的按关键字有序的查找表采用顺序组织方式若采用折半查找方法,则在等概率情况下,查找失败时的ASL值是A.24/10B.24/11C.39/10*D.39/116.在表长为n的顺序表中,实施顺序查找,在查找不成功时,与关键字比较的次数为*A.n+lB.1C.nD.n-17.在采用链地址法处理冲突所构成的开散列表上查找某一关键字,在查找成功的情况下,所探测的这些位置上的键值*A.一定都是同义词B.不一定都是同义词C.都相同D.一定都不是同义词8.用顺序查找法对具有n个结点的线性表查找的时间复杂度量级为A.On2B.Onlog2n*C.OnD.Olog2n9.用折半查找法对具有n个结点的线性表查找的时间复杂度量级为A.On2B.Onlog2nC.On*D.Olog2n10.在采用线性探测法处理冲突所构成的闭散列表上进行查找,可能要探测多个位置,在查找成功的情况下,所探测的这些位置上的键值A.一定都是同义词*B.不一定都是同义词C.都相同D.一定都不是同义词11.设哈希函数为Hkey=key%7,一组关键字为37,21,9,20,30,19,46,哈希表T的地址空间为
0..6,用线性探测法解决冲突,依次将这组关键字插入T中,得到的哈希表为A.01234562120379463019*B.01234562146379301920C.01234562119937304620D.0123456203730214619912.设有一个用线性探测法解决冲突得到的哈希表0123456789101325801617614哈希函数为Hkey=key%11,若要查找元素14,探测的次数是A.3*B.6C.7D.913.在哈希函数Hkey=key%m中,一般来讲,m应取A.奇数B.偶数*C.素数D.充分大的数14.分块查找的时间性能A.低于折半查找*B.高于顺序查找而低于折半查找C.高于顺序查找D.低于顺序查找而高于折半查找15.以下说法错误的是A.哈希法存储的基本思想是由关键字的值决定数据的存储地址*B.哈希表的结点中只包含数据元素自身的信息,不包含任何指针C.装填因子是哈希法的一个重要参数,它反映哈希表的装填程度D.哈希表的查找效率主要取决于哈希表造表时选取的哈希函数和处理冲突的方法16.以下说法正确的是A.前序遍历二叉排序树的结点就可以得到排好序的结点序列B.任一二叉排序树的平均查找时间都小于用顺序查找法查找同样结点的线性表的平均查找时间C.对具有相同关键字集合的任一插入序列,得到的二叉排序树的形态都是相同的*D.采用分块查找方法,既能实现线性表所希望的较快的查找速度,又能适应动态变化的需要17.已知采用开放地址法解决哈希表冲突,要从此哈希表中删除一个记录,正确的做法是A.将该元素所在的存储单元清空*B.将该元素用一个特殊的符号代替C.将与该元素有相同散列地址的后继元素顺次前移一个位置D.用与该元素有相同散列地址的最后插入表中的元素替代18.设哈希表长为M=14,哈希函数Hkey=key%11表中已有4个结点ADDR15=4,ADDR38=5,ADDR61=6,ADDR84=7,其余地址为空,如用二次探测再散列处理冲突,现插入关键字为50的结点的地址应是A.3B,8C.9*D.1019.有一个长度为12的有序表,按折半查找法对该表进行查找,在表内各元素查找概率相同的情况下,查找成功所需的平均比较次数为A.32/12B.35/12*C.37/12D.39/1220.采用分块查找时,若线性表中共有625个元素,查找每个元素的概率相同,假设采用顺序查找来确定结点所在的块,每块应个结点最佳*A.25B.10C.6D.62521.如果要求一个线性表既能较快地查找,又能适应动态变化的要求,可以采用查找方法*A.分块B.顺序C.折半D.散列22.有k个关键字互为同义词,若用线性探测法把这k个关键字存入哈希表中,至少要进行次探测A.k-1B.kC.k+l*D.kk+1/223.在关键字随机分布的情况下,用二叉排序树的方法进行查找,其平均查找长度与查找方法量级相当A.分块B.顺序*C.折半D.散列24.在具有n个结点的二叉排序树中查找一个元素时,最坏情况下的时间复杂度为*A.OnB.O1C.Olog2nD.On225.哈希表的平均查找长度A.与处理冲突的方法有关而与表的长度无关B.与处理冲突的方法无关而与表的长度有关*C.与处理冲突的方法有关且与表的长度有关D.与处理冲突的方法无关且与表的长度无关26.若对长度为m的闭散列表采用二次探测再散列处理冲突,对一个元素第1次计算的哈希地址为d,则第3次计算的哈希地址为A.d+1%m*B.d-1%mC.d+4%mD.d-4%m27.以下说法正确的是*A.数字分析法需事先知道所有可能出现的键值及所有键值的每一位上各数字的分布情况,并且键值的位数比散列地址的位数多B.除余法要求事先知道全部键值C.平方取中法需要事先掌握键值的全部分布情况D.随机数法适用于键值不相等的场合28.有数据4932406451256,从空二叉树开始依次插入数据形成二叉排序树,若希望高度最小,则应选择下列输入序列A.45,12,49,6,40,56,32*B.40,12,6,32,49,45,56C.6,12,32,40,45,49,56D.32,12,6,40,45,56,4929.在一棵深度为h的具有n个元素的二叉排序树中,查找所有元素的最长查找长度为A.nB.log2nC.h+1/2*D.h
二、判断题√1.分块查找方法的平均查找长度低于顺序查找,高于折半查找√2.若采用线性探测再散列法处理散列时的冲突,当从哈希表删除一个记录时,不应将这个记录的所在位置置为空,因为这会影响以后的查找╳3.前序遍历二叉排序树的结点就可以得到排好序的结点序列╳4.在任一二叉排序树上查找某个结点的查找时间都小于用顺序查找法查找同样结点的线性表的查找时间╳5.虽然关键字序列的顺序不一样,但依次生成的二叉排序树却是一样的√6.对两棵具有相同关键字集合的形状不同的二叉排序树,按中序遍历它们得到的序列的顺序是一样的√7.在二叉排序树上插入新的结点时,不必移动其他结点,仅需要改动某个结点的指针,由空变为非空即可╳8.在二叉排序树上删除一个结点时,不必移动其他结点,只要将该结点的父结点的相应指针域置空即可
三、填空题1.任何结点之间都不存在_逻辑_关系,这是集合这种逻辑结构的基本特点2.在开散列表上查找键值等于K的结点,首先必须计算该键值的__散列地址__,然后再通过指针查找该结点3.在索引顺序表上,对于顺序表中的每一块,索引表中有相应的一个“索引项”每个索引项有两个域块内最大__元素__值和块__首__位置4.索引顺序表上的查找分两个阶段
一、___确定元素所在的块__;
二、___在块内查找元素__该查找方法称为__分块__查找5.二叉排序树是一种特殊的、增加了限制条件的二叉树,其限制条件是任一结点的键值__大_于其左孩子及其子孙的键值且__小__于其右孩子及其子孙的键值6.在表示一棵二叉排序树的二叉链表上,要找键值比某结点X的键值__大__的结点,只需通过结点x的右指针到它的右子树中去找7.中序遍历一棵二叉排序树所得到的结点访问序列是键值的___递增__序列8.二叉排序树上的查找长度不仅与__元素个数_有关,也与二叉排序树的__输入序列__有关9.二叉排序的查找效率与树的形态有关当二叉排序树退化为一棵单支树时,查找算法退化为__顺序___查找,平均查找长度上升为__(n+1)/2__10.__散列__查找法的平均查找长度与元素个数n无关11.在具有20个元素的有序表上进行折半查找,则比较一次查找成功的结点数为__1___,比较两次查找成功的结点数为__2__,比较五次查找成功的结点数为_5_总的平均查找长度为__37/10___12.当所有结点的值都相等时,用这些结点构造的二叉排序树上只有___一个结点__13.折半查找方法仅适用于这样的表表中的记录必须__有序__,其存储结构必须是__顺序存储___14.考虑具有如下性质的二叉树除叶结点外,每个结点的值都大于其左子树上的一切结点的值,并小于或等于其右子树上的一切结点的值现把9个数1,2,3,4,5,6,7,8,9填入如图9-1所示的二叉树中,并使之满足上述性质圆圈旁边的数字表示插入结点的序号15.设线性表L=a1,a2,…,ann2,表中元素按值的递增顺序排列对一个给定的值k,分别用顺序查找法和折半查找法查找与k相等的元素,比较次数分别为s和b,若查找不成功,则s和b的数量关系是_sb_16.某顺序存储的表,其中有10000个元素,已按关键字的值升序排列现假定对各个元素进行查找的概率是相同的,并且各个元素的关键字都不相同用顺序查找法查找时,查找成功时的平均比较次数为__10001/2___,最大比较次数为__10000__现把10000个元素按排列顺序划分成若干组,使得每一组中有g个元素最后一组可能小于g查找时,先从第一组开始,通过比较各组的最后一个元素的关键项值,找到欲查找的元素所在的组,然后再用顺序查找法找到欲查找的元素在这种查找法中,使总的比较次数最小的g是__100__,此时的平均比较次数是__101__17.长度为225的表,采用分块查找法,每块的最佳长度是_15__,应分_15_块,若每块的长度为10,则平均查找长度为_35/2_18.已知有序表为1317203248546579869197,当采用折半查找法查找86时需进行_2__次比较可确定查找成功,查找48时需进行_4_次比较可确定查找成功,查找100时需进行_4_次比较才能确定查找不成功
四、应用题1.已知有长度为9的表16293258941146534,它们存储在一个哈希表中,利用线性探测再散列法,要求它在等概率情况下查找成功的平均查找长度不超过31该哈希表的长度m应设计成多大?2设计相应的哈希函数3将数据填入到哈希表中4计算查找成功时的平均查找长度答1该哈希表的长度m=122Hkey=key%11301234567891011893414165294132651211211124ASL=1+2+1+1+2+1+1+1+2/9=12/9=4/32.假定有n个关键字,它们具有相同的哈希函数值,用线性探测法把这n个关键字存入到哈希表中要做多少次探测?答n个关键字都是同义词,因此用线性探测法解决冲突都会发生冲突,所以探测次数为1+2+……+n=nn+1/
2.3.地址空间为0—14的哈希表中,对关键字序列JAN,FEB,MAR,APR,MAY,JUN,JUL,AUG,SEP,OCT,NOV,DEC构造哈希函数Hkey=└i/2┘,其中i为关键字中第一个字母在字母表中的序号用线性探测法和链地址法分别求出这两个哈希表在等概率情况下查找成功和查找不成功的平均查找长度答1用线性探测法01234567891011121314APRAUGDECFEBJANMARMAYJUNJULSEPOCTNOV121111245256查找成功ASL=1+2+1+1+1+1+2+4+5+2+5+6/12=31/12查找不成功ASL=5+4+3+2+1+9+8+7+6+5+4+3+2+1+1/15=61/152链地址法图略查找成功ASL=1*7+2*4+3*1/12=18/12=3/2查找不成功ASL=3+1+2+2+1+4+3+3+1+2+1+1+1+1+1/15=27/15=9/54.有一个400项的表,欲采用索引顺序查找方法进行查找,问1分成多少块最为理想?2每块的理想长度是多少?3平均查找长度是多少?答1分成20最为理想?2每块的理想长度是203平均查找长度是(20+1)/2+(20+1)/2=215.设有一组关键字19,05,21,24,45,20,68,27,70,11,10,用哈希函数Hkey=key%13,采用线性探测再散列方法解决冲突,试在0—14的散列地址空间中对该关键字序列构造哈希函数,并求查找成功和查找不成功时的平均查找长度答01234567891011121314276805194521207024111011112136124查找成功ASL=(1+1+1+1+2+1+3+6+1+2+4)/11=23/11查找不成功ASL=(1+2+1+2+1+10+9+8+7+6+5+4+3+2+1)/15=62/156.线性表的关键字集合47,26,120,08,39,68,96,23,70,63,57,已知散列函数为Hkey=key%13,采用链地址法处理冲突设计出这种链表结构,并计算该表的查找成功和查找不成功时的平均查找长度答图略查找成功ASL=1*6+2*4+3*1/11=17/11查找不成功ASL=3+1+1+3+1+4+1+1+3+1+2+2+1/13=24/137.分别画出在线性表06,10,19,24,37,42,50,83中进行折半查找,查找关键字10和30的过程答图略查找关键字102次和303次8.将forcasewhileswitchbreakdodefineconstifint中的关键字依次插入初始状态为空的二叉排序树按字母在字母表中的序号排序中,请画出所得到的树T然后画出删除for之后的二叉排序树T,若再将for插入到T中得到二叉排序树T”,问T”与T是否相同?答图略T”与T不同9.设二叉排序树中的关键字由1—100内的整数构成,现要查找关键字为63的结点,下述关键字序列哪一个是不可能在二叉排序树上查找到的序列?112,25,7,68,33,34,37,63292,20,91,24,88,25,36,63395,22,91,24,94,25,63421,89,77,29,36,38,41,47,63答3是不可能在二叉排序树上查找到的序列10.给定表25,18,48,07,76,52,81,70,92,15试按元素在表中的次序将它们依次插入一棵初始状态为空的二叉排序树,画出插入完成之后的二叉排序树答图略11.二叉排序树中的关键字互不相同,则其中最小元素无左孩子,最大元素无右孩子,此命题是否正确?最小元素和最大元素一定是叶子吗?一个新结点总是插在二叉排序树的某叶子上吗?答最小元素无左孩子,最大元素无右孩子,此命题正确最小元素和最大元素不一定是叶子一个新结点不一定总是插在二叉排序树的某叶子上第八节排序
一、选择题1.在文件局部有序或文件较小的情况下,最佳的排序方法是*A.直接插入排序B.直接选择排序C.起泡排序D.归并排序2.初始序列已经按键值有序时,用直接插入算法进行排序,需要比较的次数为*A.n-1B.log2nC.2log2nD.n*n3.快速排序在最坏情况下的时间复杂度是A、Olog2nB.Onlog2n*C.On2D.On34.具有24个记录的序列,采用起泡排序最少的比较次数为A.1*B.23C.24D.5295.用某种排序方法对序列25,84,21,47,15,27,68,35,20进行排序,记录序列的变化情况如下
258421471527683520、
201521254727683584、
152021253527476884、152021252735476884,则采用的排序方法是A.直接选择排序B.起泡排序*C.快速排序D.2-路归并排序6.在排序过程中,键值比较的次数与初始序列的排序顺序无关的是A.直接插入排序和快速排序B.直接插入排序和归并排序*C.直接选择排序和归并排序D.快速排序和归并排序7.方法是从未排序序列中依次取出元素与已经排序序列中的元素进行比较,将其放人已经排序序列的正确位置上A.归并排序*B.插入排序C.快速排序D.选择排序8.方法是从未排序序列中挑选元素,并将其依次放入已经排序序列的一端A.归并排序B.插入排序C.快速排序*D.选择排序9.方法是对序列中的元素通过适当的位置变换将有关元素一次性地放置在其最终位置上A.归并排序B.插入排序*C.快速排序D.基数排序10.将上万个无序并且互不相等的正数存储在顺序存储结构中,采取方法能够最快地找到其中最大的正整数A.快速排序B.插入排序*C.选择排序D.归并排序11.以下四种排序方法,要求附加内存空间最大的是A.插入排序B.选择排序C.快速排序*D.归并排序12.以下说法错误的是A.直接插入排序的空间复杂度为O1B.快速排序附加存储开销为Olog2n*C.堆排序的空间复杂度为OnD.2-路归并排序的空间复杂度为On,需要附加两倍的存储开销13.以下不稳定的排序方法是A.直接插入排序B.冒泡排序*C.直接选择排序D.2-路归并排序14.以下稳定的排序方法是A.快速排序*B.起泡排序C.直接选择排序D.堆排序15.以下时间复杂度不是On2的排序方法是A.直接插入排序*B.2-路归并排序C.起泡排序D.直接选择排序16.以下时间复杂度不是Onlog2n的排序方法是A.堆排序*B.直接插入排序C.2-路归并排序D.快速排序17.快速排序方法在情况下最不利于发挥其长处A.要排序的数据量太大B.要排序的数据中含有多个相同值*C.要排序的数据已基本有序D.要排序的数据个数为奇数18.设有1000个无序的元素,希望用最快的速度挑选出其中前10个最大的元素,最好选用方法A.起泡排序B.快速排序*C.堆排序D.基数排序19.一组记录的关键码为46,79,56,38,40,84,则利用快速排序的方法以第一个记录为基准得到的一次划分结果为A.38,40,46,56,79,84*B.40,38,46,79,56,84C.40,38,46,56,79,84D.40,38,46,84,56,7920.一组记录的关键码为46,79,56,38,40,84,则利用堆排序的方法建立的初始堆为·A.79,46,56,38,40,84*B.84,79,56,38,40,46C.84,79,56,46,40,38D.84,56,79,40,46,3821.若用起泡排序法对序列18,14,6,27,8,12,16,52,10,26,47,29,41,24从小到大进行排序,共要进行次比较A.33B.45*C.70D.91
二、判断题╳1.如果某种排序算法是不稳定的,则该方法没有实际意义√2.当待排序的元素很大时,为了交换元素的位置,移动元素要占用较多的时间,这是影响时间复杂度的主要原因之一╳3.对于n个记录的集合进行起泡排序,所需要的平均时间是Onlog2n√4.对于n个记录的集合进行归并排序,所需要的平均时间是Onlog2n╳5.对于n个记录的集合进行快速排序,所需要的平均时间是On╳6.堆排序所需的时间与待排序的记录个数无关
三、填空题1.对于n个记录的集合进行归并排序,所需的附加空间为___On__2.设表中元素的初始状态是按键值递增的分别用堆排序、快速排序、起泡排序、归并排序进行递增排序,则__起泡排序_最节省时间,__快速排序__最费时间对快速排序来讲,其最好情况下的时间复杂度为__Onlog2n____,最坏情况下的时间复杂度为___On2____3.目前以比较为基础的内部排序的时间复杂度Tn的范围是_Onlog2n~On2___,其比较次数与待排序的记录的初始状态无关的是_归并排序、直接选择排序__4.在内部排序中要求附加的内存容量最大的是_快速排序、归并排序___,排序时不稳定的是___希尔排序、选择排序、归并排序____5.从时间上看,快速排序的平均性能优于其她排序方法,但从空间上看,快速排序需要一个栈空间来实现递归若每一趟排序都将记录序列均匀地分割成长度接近的两个序列,则栈的最大深度为__log2n___;在最坏情况下,栈的深度为__n-1__6.堆的形状是一棵___完全二叉树__7.若待排序的序列中存在多个记录具有相同的键值,经过排序,这些记录的相对次序仍然保持不变,则称这种排序方法是_稳定__的,否则称为___不稳定__的8.按照排序过程涉及的存储设备的不同,排序可分为__内部__排序和__外部_排序9.直接插入排序是稳定的,它的时间复杂度为_On2__,空间复杂度为__O1__10.归并排序要求待排序列由若干个___有序___的子序列组成11.2-路归并排序的时间复杂度是___Onlog2n____12.在对一组记录54,38,96,23,15,72,60,45,83进行直接插入排序时,当把第7个记录60插入到有序表时,为寻找插入位置需比较__3_次13.在堆排序和快速排序中,若原始记录接近正序和反序,则选用__堆排序___;若原始记录无序,则最好选用____快速排序__14.在插入排序和选择排序中,若初始数据基本正序,则选用____插入排序___;若初始数据基本反序,则选用__选择排序__
四、应用题1.一组关键字19,01,26,92,87,11,43,87,21,进行起泡排序,试列出每一趟排序后的关键字序列,并统计每趟排序所进行的关键字比较次数答略2.对上题给出的关键字序列,进行选择排序,列出每一趟排序后的关键字序列,并统计每趟排序所进行的关键字比较次数答略3.从快速排序法的基本原理不难看出,对n个元素组成的线性表进行快速排序时,所需进行的比较次数依赖于这n个元素的初始排列1试问当n=7时,在最好情况下需进行多少次比较说明理由2对n=7给出一个最好情况的初始排列的实例答1当n=7,k3趟划分=3时,在最好情况下,第一趟6次比较,第二趟各需2次比较,共10次比较即可2对n=7一个最好情况的初始排列4,7,5,6,3,1,24.对下列一组关键字46,58,15,45,90,18,10,62,试写出快速排序的每一趟的排序结果,并标出第一趟中各元素的移动方向答略5.判断以下序列是否为堆,若不是,则调整为堆197,86,48,73,35,39,42,57,66,20212,70,33,65,24,56,48,92,86,313103,97,56,38,66,23,42,12,30,52,06,20405,56,20,23,40,38,29,61,35,76,28,99答
1、
3、是大根堆;2不是堆,调整为小堆(12,24,33,65,31,56,48,92,86,70);4不是堆,调整为小堆(05,23,20,35,28,38,29,61,56,76,40,99)6.设有5000个无序的元素,希望用最快的速度挑选出前10个大元素请说明哪种算法最好,并说明理由答采用堆排序7.用图示给出关键字序列92,37,86,33,12,57,25初始建堆和输出前两个最小关键字后重建堆的过程答略操作系统练习题参考答案一单项选择题B
1.操作系统是计算机系统的一种A.应用软件B.系统软件c.通用软件D.工具软件D2.操作系统目的是提供一个供其他程序执行的良好环境,因此它必须使计算机A.使用方便B.高效工作C.合理使用资源D.使用方便并高效工作A3.允许多个用户以交互方式使用计算机的操作系统是A.分时操作系统B.批处理单道系统C.实时操作系统D.批处理多道系统C4.下列系统中是实时系统A.计算机激光照排系统B.办公自动化系统C.化学反应堆控制系统D.计算机辅助设计系统D5.操作系统是一种系统软件,它A.控制程序的执行B.管理计算机系统的资源C.方便用户使用计算机D.管理计算机系统的资源和控制程序的执行C6.计算机系统把进行和控制程序执行的功能集中组成一种软件,称为操作系统A.CPU管理B.作业管理C.资源管理D.设备管理D7.批处理操作系统提高了计算机系统的工作效率,但A.不能自动选择作业执行B.无法协调资源分配c.不能缩短作业执行时间D在作业执行时用户不能直接干预B8.分时操作系统适用于A.控制生产流水线B.调试运行程序c.大量的数据处理D.多个计算机资源共享C9.在混合型操作系统中,“前台”作业往往是指A.由批量单道系统控制的作业B.由批量多道系统控制的作业c.由分时系统控制的作业D.由实时系统控制的作业B
10.在批处理兼分时的系统中,对应该及时响应,使用户满意A.批量作业B.前台作业c.后台作业D.网络通信C11.实时操作系统对可靠性和安全性要求极高,它A.十分注重系统资源的利用率B.不强调响应速度c.不强求系统资源的利用率D.不必向用户反馈信息D12.分布式操作系统与网络操作系统本质上的不同之处在于A.实现各台计算机之间的通信B.共享网络个的资源c.满足较大规模的应用D.系统中若干台计算机相互协作完成同一任务B13.为用户分配主存空间,保护主存中的程序和数据不被破坏,提高主存空间的利用率A处理器管理B.存储管理c.文件管理D.作业管理A14.在现代计算机系统层次结构中,最内层是硬件最外层是使用计算机的人,人与硬件之间是A.软件系统B.操作系统c.支援软件D.应用软件B
15.财务管理软件是一种专用程序它属于A.系统软件B.应用软件c接口软件D.支援软件C
16.在多道程序设计技术的计算机系统中,中央处理器A.只能被一个程序占用B.可以被多个程序同时占用c.可以被多个程序交替占用D.可以被操作系统和另一个程序同时占用D17.不是一种永久性的存储设备,当电源被切断时,其中的信息就会消失A.硬盘B.磁带c.软盘D.主存储器Cl8.中央处理器可以直接存取中的信息A.光盘B.软盘c.主存储器D.硬盘B19.中央处理器存取寄存器中信息的速度与使用主存储器和辅存储器信息相比A.比较快B.最快c.差不多D.最慢D20.存放在信息只能顺序存取,无法随机访问A.硬盘B.软盘c.光盘D.磁带B21.在操作系统的层次结构中.是操作系统的核心部分,它位于最内层A.存储管理B.处理器管理C.设备管理D.作业管理C
22.在操作系统的层次结构中,各层之间A.互不相关B.内、外层互相依赖c.外层依赖内层D.内层依赖外层C23.多道程序设计系统中,让多个计算问题同时装入计算机系统的主存储器A并发执行B.顺序执行c.并行执行D.同时执行B
24.引入多道程序设计技术后,处理器的利用率A.有所改善B.极大地提高c.降低了D.无变化,仅使程序执行方便C25.计算机系统采用多道程序设计技术后,(A.缩短了每个程序的执行时间B.系统效率随并行工作道数成比例增长c.提高了系统效率D.使用设备时不会发生冲突D26.进程是A.一个系统软件B.与程序概念等效c.存放在内存中的程序D.执行中的程序A
27.进程的和并发性是两个很重要的属性A.动态性B.静态性c.易用性D.顺序性C28.已经获得除以外所有运行所需资源的进程处于就绪状态A主存储器B.打印机C.CPUD.磁盘空间C29.在一个单处理器系统中,处于运行态的进程A.可以有多个B.不能被打断c.只有一个D.不能请求系统调用D
30.对于一个单处理器系统来说允许若干进程同时执行,轮流占用处理器.称它们为(的A.顺序执行B.同时执行c.并行执行D.并发执行B31.操作系统根据控制和管理进程,它是进程存在的标志A.程序状态字B.进程控制块c.中断寄存器D.中断装置D32.若干个等待占有cPU并运行的进程按一定次序链接起来的队列为A.运行队列B.后备队列c.等待队列D.就绪队列A
33.中断优先级是按照中断事件的重要性和紧迫程度来确定的,是在A硬件设计时固定下来的B作业说明书中申请的c.动态分配的D.由中断装置确定的C34.存储管理的目的是A、方便用户B.提高主存空间利用率C.方便用户和提高主存利用率D.增加主存实际容量B
35.为了实现存储保护,对共享区域中的信息A.既可读,又可写B.只可读,不可修改c.能执行,可修改D.既不可读也不可写A36.提高主存利用率主要是通过实现的A.内存分配B.内存保护c.地址转换D.内存扩充C37.采用虚拟存储器的前提是程序的两个特点,—是程序执行时某些部分是互斥的、二是程序的执行往往具有A.顺序性B.并发性C局部性D.并行性B38.虚拟存储器的容量是由计算机的地址结构决定的,若cPu有32位地址,则它的虚地址空间为字节A.2GB.4GC.100KD.640KA39.操作系统对文件实行统一管理,最基本的是为用户提供功能A.按名存取B.文件共享C.文件保护D.提高文件的存取速度C40.采取哪种文件存取方式,主要取决于A.用户的使用要求B.存储介质的特性C.用户的使用要求和存储介质的特性D.文件的逻辑结构B41.文件系统的按名存取主要是通过实现的A.存储空间管理B.目录管理C.文件安全性管理D.文件读写管理B42.文件管理实际上是对的管理A.主存空间B.辅助存储空间C.逻辑地址空间D.物理地址空间C43.逻辑文件可分为流式文件和两类A.索引文件B.链接文件C.记录式文件D.只读文件A44.由一串信息组成,文件内信息不再划分可独立的单位,这是指A.流式文件B.记录式文件C.连续文件D.串联文件B45.磁盘机属于A字符设备B.存储型设备c.输入输出型设备D.虚拟设备D46.对存储型设备,输入输出操作的信息是以为单位传输的A.位B.字节C.字D.块B47.对输入输出设备,输入输出操作的信息传输单位为A.位B.字符C.字D.块C48.用户要求计算机处理的一个计算问题称为一个A.进程B程序C.作业D系统调度D
49.一个作业的完成要经过若干加工步骤,这每个步骤称为A.作业流B.子程序C.子进程D.作业步二填空题1.计算机系统是按用户要求接收和存储信息,自动进行___数据处理____并输出结果信息的系统
2.计算机是由硬件系统和__软件_系统组成3.软件系统由各种__程序__和数据组成4.计算机系统把进行_资源管理_和控制程序执行的功能集中组成一种软件称为操作系统5.操作系统使用户合理__共享资源__,防止各用户间相互干扰6.使计算机系统使用方便和__高效地工作_是操作系统的两个主要设计目标7.批处理操作系统、__分时操作系统_和实时操作系统是基本的操作系统8.用户要求计算机系统中进行处理的一个计算机问题称为__作业__9.批处理操作系统按照预先写好的__作业说明书__控制作业的执行10.在多道操作系统控制下,允许多个作业同时装入__主存储器___,使中央处理器轮流地执行各个作业11.批处理操作系统提高了计算机系统的__工作效率__,但在作业执行时用户不能直接干预作业的执行12.在分时系统中,每个终端用户每次可以使用一个由__时间片__规定的cPu时间13分时系统具有同时性、独立性、及时性和__交互性___等特点14.在批处理兼分时系统中,往往把由分时系统控制的作业称为__前台__作业,把由批处理系统控制的作业称为__后台__作业l5.实时系统要求有__高可靠性和安全性__不强求系统资源的利用率
16.网络操作系统能实现各台计算机之间的通信和网络中各种__资源__的共享17.分布式计算机系统中各台计算机___没有__主次之分18.操作系统的资源管理功能有处理器管理、__存储管理__、文件管理、设备管理和作业管理19.__处理器管理_为用户合理地分配处理器时间.尽可能地使处理器处于忙状态,提高处理器的工作效率20.文件管理面向用户实现__按文件名__存取文件,管理用户信息的存储、检索、共享和保护21.现代的通用计算机系统是由硬件和软件组成的一种__层次式___结构22.计算机系统层次结构的最内层是__硬件____系统、最外层是使用计算机系统的人23.软件系统包括___系统软件___、支援软件和应用软件三部分.
24.___支援软件___是支持其他软件的开发和维护的软件25.在硬件系统中,___中央处理器或cPu___是对信息进行高速运算和控制处理的部件
26.__主存储器__和__辅助存储器_都可用于存放各种程序和数据,前者可被cPu直接访问,而后者则不能
27.___输入输出控制系统___控制和管理外设与主存储器之间的信息传送28.计算机系统的中断机制包括硬件的___中断装置___和操作系统的中断处理服务程序.29.任何程序只有占用__中央处理器____执行时才能履行自己的职责.
30.在多道程序设计技术的计算机系统中,一个中央处理器在任何时刻最多能被___1___个程序占用31.硬件的输入输出结构允许中央处理器和各种外围设备___同时并行___工作32.外围设备工作结束后,通过___输入输出操作结束或I/O中断___事件通知操作系统33.主存储器以__字节____为单位编址,中央处理器按__地址____读出主存储器中的内容34.辅助存储器容量大,且能___永久___地保存信息35.磁盘上的信息可__随机____存取,而磁带上的信息则只能__顺序____存取
36.启动I/O等__特权____指令只允许操作系统程序使用37.操作系统为用户提供两种类型的使用接口,一种是操作员级的,另一种是__程序员级____的38.让多个计算机问题同时装入一个计算机系统的主存储器____并行执行____,这种设计技术称为___多道程序设计____39.在多道程序设计的系统中,应采用___存储保护_____的方法保证各道程序互不侵犯.40.采用多道程序设计技术后可有效地提高系统中资源的__利用率______,增加单位时间的算题量,从而提高了系统的__吞吐量_____
41.多道程序设计提高了系统的吞吐量.但可能会___延长_____某些程序的执行时间42.在多道程序设计系统中,并行的道数要根据____系统配置的资源____和用户对资源的要求来确定43.把一个程序在一个数据集上的一次执行称为一个___进程___44.程序是___静止的_____;进程是__动态的______45.同时执行的进程是____轮流____占用处理器的,这些进程可称为并发执行的46.每个进程都是有生命期的即从____创建____到消亡47.操作系统依据___进程控制块_____对进程进行控制和管理48.___主存储器______可被处理器直接访问,但处理器不能直接访问辅助存储器49.二级存储方法是利用__辅助存储器____存放准备运行的程序和数据,当需要时或主存空间允许时,随时将它们读入主存储器
50.主存储器分成___系统区___和___用户区____两部分51.用户区来存放用户的___程序和数据____52.存储管理是对主存空间的___用户区____进行管理53.文件系统是操作系统中的重要组成部分,它对___信息_______进行管理54.文件管理的主要工作是管理用户信息的存储、__检索____、更新、__共享____和保护55.文件管理为用户提供___按文件名___存取文件的功能56.文件是逻辑上具有完整意义的__信息集合___.57.操作系统中对外围设备的启动和控制工作由__设备管理部分____完成58.计算机的外围设备可分__存储型设备____和__输入输出型设备____两大类
59.___存储型设备___能使大量的信息存放到相应的存储介质上,能作为主存储器的扩充60.___作业___是用户要求计算机系统处理的一个计算问题61.完成一个作业一般要经过若干加工步骤,作业的每一个加工步骤称为一个__作业步____62.每个作业步都是一个__相应程序____的执行,前一个作业步的结果信息往往作为后一作业步的__输入信息____63.一个作业执行时要分若干作业步,作业步的顺序是由___用户___指定的64.操作系统为用户提供了说明作业加工步骤的两种手段,__作业控制语言____和__操作控制命令____65.作业控制方式有__批处理方式____和__交互方式____三简答题
1.什么是计算机系统它由哪几部分组成计算机系统是按用户的要求接收和存储信息,自动进行数据处理并输出结果信息的系统计算机系统由硬件系统和软件系统组成硬件系统是计算机系统赖以工作的实体,软件系统保证计算机系统按用户指定的要求协调地工作2.计算机系统的资源包括哪些计算机系统的资源包括两大类:硬件资源和软件资源硬件资源主要有中央处理器、主存储器、辅助存储器和各种输入输出设备软件资源有编译程序、编辑程序等各种程序以及有关数据
3.简述操作系统的定义操作系统是计算机系统的一种系统软件,它统一管理计算机系统的资源和控制程序的执行4.为计算机设计操作系统要达到什么目的设计时应考虑哪些目标操作系统是一种系统程序,其目的是为其他程序的执行提供一个良好的环境它有两个主要设计目标一是使计算机系统使用方便,二是使计算机系统能高效地工作5.从操作系统提供的服务出发,操作系统可分哪几类从操作系统提供的服务出发,操作系统可分为批处理操作系统、分时操作系统、实时操作系统、网络操作系统和分布式操作系统6.何谓批处理操作系统用户准备好要执行的程序、数据和控制作业执行的说明书,由操作员输入到计算机系统中等待处理,操作系统选择作业并按其作业说明书的要求自动控制作业的执行采用这种批量化处理作业的操作系统称为批处理操作系统7.为什么说批处理多道系统能极大地提高计算机系统的工作效率批处理多道系统能极大地提高系统的工作效率,表现在四个方面1多道作业并行工作,减少了处理器的空闲时间;2作业调度可以合理选择装入主存储器中的作业,充分利用计算机系统的资源;3作业执行过程中不再访问低速设备,而直接访问高速的磁盘设备缩短执行时间;4作业成批输入,减少了从操作到作业的交接时间
8.分时系统如何使各终端用户感到好像自己独占一台计算机在分时系统中、系统把CPU时间划分成许多时间片,每个终端每次可以使用由一个时间片规定的cPu时间,多个终端用户就这样轮流地使用cPU,每人都得到了及时响应,感到好像自己独占了一台计算机9.网络操作系统有何主要功能网络操作系统把计算机网络中的各台计算机有机地联合起来,实现各计算机之间的通信及网络中各种资源的共享10.简述操作系统的五大功能从资源管理的观点出发,操作系统具有五大功能1处理器管理为用户合理分配处理器时间,提高处理器工作效率2存储管理为用户分配主存空间,保护主存中的程序和数据不被破坏,提高主存空间的利用率3文件管理管理用户信息,为用户提供按文件名存取功能,合理分配文件的存储空间4设备管现负责设备约分配、启动以及虚拟设备的实现等.5作业管理实现作业调度和控制11.在多道程序设计技术的系统中、操作系统怎样才会占领中央处理器只有当中断装置发现有事件发生时,它才会中断当前占用中央处理器的程序执行,让操作系统的处理服务程序占用中央处理器并执行之12.简述计算机系统的中断机制及其作用中断机制包括硬件的中断装置和操作系统的中断处理服务程序中断装置由一些特定的寄存器和控制线路组成,中央处理器和外围设备等识别到的事件保存在特定的寄存器中,中央处理器每执行完一条指令,均由中断装置判别是否有事件发生若无事件发生,cPu继续执行;若有事件发生,则中断装置中断原占有cPu的程序的执行,让操作系统的处理事件服务程序占用cPu,对出现和事件进行处理,事件处理完后,再让原来的程序继续占用CPu执行13.计算机系统为什么要配置辅助存储器由于主存储器容量的限制,不足以存储所有需要存储的程序和数据,并且主存储器不是一种永久性的存储设备,当电源被切断时主存储器中的信息就会消失;而辅助存储器容量大且能永久地保存信息,所以计算机系统都配置辅助存储器
14.怎样的输入输出结构才能使cPu与外设并行工作这种结构为把各种外围设备连接在相应的控制器上,这些设备控制器又通过通道连接在公共的系统总线上15.计算机系统怎样实现存储保护一般硬件设置了基址寄存器和限长寄存器中央处理器在目态下执行系统时,对每个访问主存的地址都进行核对,若能满足基址寄存器值≤访问地址≤基址寄存器值+限长寄存值,则允许访问;否则不允许访问并且不允许用户程序随意修改这两个寄存器的值这就实现了存储保护16.简述操作系统的层次结构操作系统的层次结构以硬件为基础,自内向外依次为处理器管理、存储管理、设备管理、文件管理和作业管理17.操作系统为用户提供哪些接口操作系统为用户提供两种类型的使用接口一是操作员级的、它为用户提供控制作业执行的途径;二是程序员级的,它为用户程序提供服务功能18.什么是多道程序设计系统让多个计算问题同时装入一个计算机系统的主存储器并行执行,这种技术称为多道程序设计,这种计算机系统称为多道程序设计系统19.多道程序设计系统中应注意些什么多道程序设计系统必须做好存储保护、程序浮动、资源分配及管理工作20.多道程序设计从哪几方面提高系统的效率多道程序设计从三个方面提高系统的效率
①减少cPU的空闲时间,提高处理器的利用率
②合理搭配程序,充分利用外围设备资源
③发挥处理器与外围设备,以及外围设备之间的并行工作能力21.什么是进程为什么要引入进程的概念进程是一个程序在一个数据集上的一次执行引入进程的目的在于从变化的角度动态地研究程序的执行
22.进程与程序有何区别程序是静止的,进程是动态的进程包括程序和程序处理的对象数据集,进程能得到程序处理的结果23.进程由哪三部分组成进程由程序、数据集和进程控制块三部分组成24.操作系统根据什么控制和管理进程为什么操作系统根据进程控制块控制和管理进程因为进程控制块是进程存在的标志,它记录了进程执行时的变化情况25.简述存储管理的功能存储管理的功能主要有下列四个方面1主存空间的分配和去配,以主存空间分配表为依据作主存分配,并在作业撤离后回收主存空间2实现逻辑地址到绝对地址的转换,这种转换需要与硬件配合完成3主存空间的共享与保护4主存空间的扩充,采用某些技术,为用户提供一个虚拟存储器26.主存空间信息保护有哪些措施?保存主存空间中的信息一般采用以下措施1程序执行时访问属于自己主存区域中的信息,允许它既可读,又可写2对共享区域中的信息只可读,不可修改3对非共享区或非自己的主存区域中的信息既不可读,也不可写27.什么是文件文件是逻辑上具有完整意义的信息集合28.简述按名存取的含义用户不必考虑文件存储在哪里,怎样组织输入输出等工作,只要提供文件名,操作系统通过去查找目录,就能对文件进行存取29.存储型设备和输入输出型设备的输人输出操作的信息传输单位有何不同存储型设备输入输出操作的信息传输单位是“块”,而输入输出型设备输入输出操作的信息传输单位是“字符”30什么是独占设备什么是共享设备
31.独占设备是指那些只能让一个作业独占使用的设备;共享设备是指允许多个作业同时使用的设备3.共享设备允许多个作业同时使用,这里的“同时使用”的含义是什么
32.“同时使用”的含义是多个作业可以交替地启动共享设备,在某一时刻仍只有一个作业占有33.用户可用哪些手段来说明作业步用户可用操作系统的两种手段来说明作业步,一种是作业控制语言,另一种是作业控制命令34.作业控制方式有哪几种作业控制方式有两种,一种是批处理方式,一种是交互方式批处理方式是指在成批处理时,操作系统按各个作业的作业控制说明书中的要求分别控制相应的作业,按指定的步骤去执行交互方式是指在作业执行过程中,操作系统和用户之间不断地交流信息,用户使用操作控制命令表达作业执行的控制意图。