天津专升本商大计算机专业课练习

天津专升本09商大计算机专业课练习1,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,数据结构,Data Structure,*,单击此处编辑母版标题样式,*,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,天津专升本商大计算机专业课练习,天津专升本,09,商大计算机专业课练习,1,1.数据的逻辑构造可以分为_。,A)静态构造和动态构造,B)物理构造和存储构造,C)线性构造和非线性构造,D)虚拟构造和抽象构造,2.顺序存储方式的优点是_。,A)存储密度大,B)插入、删除运算方便,C)可进展动态存储分配,D)可方便地用于各种逻辑构造的存储表示,天津专升本,09,商大计算机专业课练习,1,3.下面关于线性表的表达中，错误的选项是 _。,A)线性表采用顺序存储，必须占用一片连续的存储单元,B)线性表采用顺序存储，便于进展插入和删除操作,C)线性表采用链接存储，不必占用一片连续的存储单元,D)线性表采用链接存储，可以动态分配存储空间,4.用数组存储线性表的优点是_。,A)便于插入和删除操作,B)便于随机存取,C)可以方便地改变表的长度,D)不需要占用一片连续的存储空间,天津专升本,09,商大计算机专业课练习,1,5.,字符,A,、,B,、,C,依次进入一个栈，按出栈的先后顺序组成不,同的字符串，至多可以组成,_,个不同的字符串。,A)5,B)4,C)6,D)1,ABC,BAC,BCA,CBA,ACB,CAB,天津专升本,09,商大计算机专业课练习,1,6.栈和队列都是 。,A)顺序存储的线性构造,B)链式存储的非线性构造,C)限制存取点的线性构造,D)限制存取点的非线性构造,天津专升本,09,商大计算机专业课练习,1,7.,设有,x,，,y,，,z,三个元素顺序进栈，在进栈过程可,以出栈，不可能出现的出栈序列为,。,A)xyz,B)yzx,C)zxy,D)zyx,天津专升本,09,商大计算机专业课练习,1,8.,线性表中各元素之间呈,_,关系。,A),层次,B),网状,C),有序,D),集合,天津专升本,09,商大计算机专业课练习,1,9.,一维数组和线性表的区别是,_,。,A),前者长度固定，后者长度可变,B),后者长度固定，前者长度可变,C),两者长度均固定,D),两者长度均可变,天津专升本,09,商大计算机专业课练习,1,10.设一环形队列用一维数组Am表示，队头和队尾的指针,分别为front和tail，那么入队时判定队列满的条件是_。,A)front=tail,B)front=tail+1,C)front=(tail+1)%m,D)front=tail%m,天津专升本,09,商大计算机专业课练习,1,11.,单链表,L,中，,P,所指结点为尾结点的条件为,_,。,A)P,L,B)P-next=NULL,C)P.next:,L,D)P,nil,天津专升本,09,商大计算机专业课练习,1,12.与数据元素本身的形式、内容、相对位置及个数无关的,是数据的 _。,A)存储构造,B)存储实现,C)逻辑构造,D)运算实现,天津专升本,09,商大计算机专业课练习,1,13.单链表中，增加头结点的目的是 _。,A)使单链表至少有一个结点,B)表示单链表中首结点的位置,C)方便运算的实现,D)说明单链表是线性表的链式存储构造,天津专升本,09,商大计算机专业课练习,1,14.借助栈输入A、B、C三个元素，那么不可能的输出序列,是 _。,A)ABC,B)CAB,C)CBA,D)BAC,天津专升本,09,商大计算机专业课练习,1,15.数据构造是一门研究非数值计算的程序设计问题中计,算机的_以及它们之间的关系和运算等的学科。,A数据元素,B计算方法,C逻辑存储,D数据映像,天津专升本,09,商大计算机专业课练习,1,16.算法分析的目的是_。,A找出数据构造的合理性,B分析算法的效率以求改进,C研究算法中的输入和输出的关系,D分析算法的易懂性和文档性,天津专升本,09,商大计算机专业课练习,1,17.在长度为n的顺序表的第i1in+1个位置上插入一,个元素，元素的移动次数为_。,An-i+1,Bn-i,Ci,Di-1,天津专升本,09,商大计算机专业课练习,1,18.设top为栈顶指针，判定一个栈S(最多元素为m)为栈满的,条件是_。,AS-top!=0,BS-top=0,CS-top!=m-1,DS-top=m-1,天津专升本,09,商大计算机专业课练习,1,19.不带头结点的单链表 head为空的判断条件为_。,Ahead=Null,B head-next =Null,C head-next =head,D head!=Null,天津专升本,09,商大计算机专业课练习,1,20.在一个栈顶指针为HS的链栈中删除一个结,点时，用x保存被删除的结点，那么执行的操作,是_。P47图,Ax=HS,HS=HS-next;,Bx=HS-data;,Cx=HS-data,HS=HS-next;,DHS=HS-next,x=HS-data;,天津专升本,09,商大计算机专业课练习,1,1.栈的根本运算包括_。,A)删除栈底元素,B)将栈置为空栈,C)判断栈是否为空,D)删除栈顶元素,BCD,天津专升本,09,商大计算机专业课练习,1,2.队列的根本运算包括_。,A)从队尾插入一个新元素,B)判断一个队列是否为空,C)从队列中删除第i个元素,D)读取队头元素的值,ABD,天津专升本,09,商大计算机专业课练习,1,3.从逻辑上讲，以下属于线性构造的是_。,A)有向图,B)栈,C)线索二叉树,D)数组,E)串,BDE,天津专升本,09,商大计算机专业课练习,1,4.以下关于链式存储构造的表达中，正确的选项是_。,A)结点除自身信息外还包括指针域，因此存储密度小于,顺序存储构造,B)可以通过计算直接确定第i个结点的存储地址,C)逻辑上相邻的结点物理上不必相邻,D)插入、删除操作方便，不必移动结点,ACD,天津专升本,09,商大计算机专业课练习,1,5.以下术语与数据的存储构造无关的术语是_。,A)栈,B)队列,C)散列表,D)串,ABD,天津专升本,09,商大计算机专业课练习,1,6.设一个链表最常用的操作是在表头插入结点和删除第一,个结点，那么最节省时间的存储构造为_。,A单链表,B仅有头指针的单循环链表,C双链表,D仅有尾指针的单循环链表,ABC,天津专升本,09,商大计算机专业课练习,1,1.数据构造中与所使用的计算机无关的是数据的逻辑构造。,2.栈和队列既可采用顺序存储方式，也可采用链接存储方式。,3.线性表是一个有序序列，其中可包含一样的元素，也允许各,个元素可以是不同的数据类型。,4.队列是允许在队头一端进展插入，在队尾一端进展删除操作,的线性表。,5.链表的每个结点都含有两个指针。,正确 1 2,天津专升本,09,商大计算机专业课练习,1,6.线性构造的根本特征是：每个结点有且仅有一个直接前,趋和一个后继。,7.线性表中各元素类型必须是一样的。,8.数据构造的操作一定是定义在逻辑构造上，实现在存储,构造上。,9.顺序队列和循环队列的队空和队满判断条件是不一样的。,10.数据的逻辑构造指的是数据元素之间的逻辑关系的整体。,11.单链表形式的队列，头指针F指向队列的第一个结点，尾,指针R指向队列的最后一个结点。,正确：7 8 9 10 11,天津专升本,09,商大计算机专业课练习,1,1.数据构造包括的三个方面的内容是 、和 。,2.通常衡量算法效率的一般标准为 和 。,3.队列和栈都是线性表。在栈中，称为栈顶，栈操作的,原那么是 ；队列操作的原那么是 _。,答案：1 逻辑构造、存储构造、运算,2 时间复杂度、空间复杂度,3 表尾(允许操作的一端)、后进先出、先进先出,天津专升本,09,商大计算机专业课练习,1,4.设栈S的初始状态为空，队列Q的初始状态为,a1 a2 a3 a4,队头 队尾,对栈S和队列Q进展如下两步操作：,(1)Q中的元素依次出队，并压入栈S中，直至Q为空；,(2)依次弹出S中的元素并进入Q，直至S为空。,在上述两步操作后，队列Q的状态是 _。,答案：a4a3a2a1,天津专升本,09,商大计算机专业课练习,1,5.用一维数组表示线性表L=(a1,a2,an)，假定删除表中,任一元素的概率一样都为1/n，那么删除一个元素平均需移,动的元素个数为_。,(n-1)/2,6.当线性表采用顺序存储构造进展存储时，其主要特点是,_。,逻辑构造相邻的结点存储构造也相邻,7.具有n个单元的循环队列中，队满时共有 _个元素。,n-1,8.链式存储构造最显著的优点是 _。,方便插入、删除操作,天津专升本,09,商大计算机专业课练习,1,9.假设以S和X分别表示进栈和出栈操作，假设对输入序列,1,2,3,4,5进展一系列栈操作SSSXXSXSXX之后，得到的输出序,列为 。,参考答案：32451,10.设有一个顺序栈S，元素a，b，c，d，e，f依次进栈，如果6,个元素的出栈顺序为b，c，d，f，e，a，那么顺序栈的容量至少,应为。,参考答案：3,天津专升本,09,商大计算机专业课练习,1,1如下图，在栈的输入端有6个元素，输入顺序为A、B、,C、D、E、F。能否在栈的输出端得到序列ACEDFB及,EDFCAB？假设能，写出对栈的操作过程用push表示进栈，,pop表示退栈；假设不能，简述其理由。,PUSH(S,A)A元素进栈,POP(S)栈顶元素出栈,输入端,输出端,栈,S,ABCDEF,天津专升本,09,商大计算机专业课练习,1,1参考答案：,可以产生ACEDFB，ACEDFB进栈过程：,PUSH(S,A)，POP(S)，,PUSH(S,B)，PUSH(S,C)，POP(S)，,PUSH(S,D)，PUSH(S,E)，,POP(S)，POP(S)，,PUSH(S,F)，POP(S)，POP(S),不能产生EDFCAB，原因：不能产生EDFCAB原因：栈是一种特殊的线性表，其操作原那么“先进后出或“后进先出。在进栈系列ABCDEF中，B比A后进栈，在出栈时应比A先出栈，故不可以得到EDFCAB系列。,天津专升本,09,商大计算机专业课练习,1,2解释数据构造、逻辑构造、存储构造的概念，并讨论他,们之间的关系；,参考答案：数据构造：相互之间存在一种或多种特定关系的,数据元素的集合。逻辑构造：逻辑构造描述数据之间的逻辑,关系。包括集合、线性、树形和网状构造。存储构造：数据,构造在计算机中的表示称存储构造。包括顺序、索引、链式,和散列。三者关系：在数据构造中，数据的逻辑构造和存储,构造密切相关的；存储构造不仅存储数据元素，还要存储数,据元素的逻辑关系；逻辑构造与计算机无关；逻辑构造一样,但存储构造不同，可以是不同的数据构造。,天津专升本,09,商大计算机专业课练习,1,3线性表的顺序存储具有如下缺点：(1).在进展插入或删除,操作时，需要移动大量元素；(2).由于难以估计其大小，必须,预先分配较大的存储空间，往往使存储空间得不到充分利用,；(3).表的容量难以扩大。试问线性表的链式存储构造是否一,定能抑制上述缺点？试做简要讨论。,参考答案：链式存储构造一般抑制的顺序构造的三个弱点：,首先，链式存储构造插入、删除不需要移动元素，只需修改,指针，时间复杂度为O(1)；其二，不需要预先分配存储空间,，可根据需要动态申请；其三，表容量只受内存空间的限制,；,缺点：因指针增加了内存空间开销，当空间不允许时，就不能,抑制顺序存储的优点。,天津专升本,09,商大计算机专业课练习,1,1两个带头结点的单链表La和Lb中的元素按非递减顺,序排