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

天津专升本商大计算机专业课练习天津专升本商大计算机专业课练习天津专升本商大计算机专业课练习天津专升本09商大计算机专业课练习11.数据的逻辑结构可以分为____________。A)静态结构和动态结构B)物理结构和存储结构C)线性结构和非线性结构D)虚拟结构和抽象结构2.顺序存储方式的优点是____________。A)存储密度大B)插入、删除运算方便C)可进行动态存储分配D)可方便地用于各种逻辑结构的存储表示天津专升本09商大计算机专业课练习11.数据的逻辑结构可以分为____________。A)静态结构和动态结构B)物理结构和存储结构C)线性结构和非线性结构D)虚拟结构和抽象结构2.顺序存储方式的优点是____________。A)存储密度大B)插入、删除运算方便C)可进行动态存储分配D)可方便地用于各种逻辑结构的存储表示天津专升本09商大计算机专业课练习13.下面关于线性表的叙述中，错误的是_________。A)线性表采用顺序存储，必须占用一片连续的存储单元B)线性表采用顺序存储，便于进行插入和删除操作C)线性表采用链接存储，不必占用一片连续的存储单元D)线性表采用链接存储，可以动态分配存储空间4.用数组存储线性表的优点是_____________。A)便于插入和删除操作B)便于随机存取C)可以方便地改变表的长度D)不需要占用一片连续的存储空间天津专升本09商大计算机专业课练习15.字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成_______个不同的字符串。A)5B)4C)6D)1ABCBACBCACBAACBCAB天津专升本09商大计算机专业课练习16.栈和队列都是

。A)顺序存储的线性结构B)链式存储的非线性结构C)限制存取点的线性结构D)限制存取点的非线性结构天津专升本09商大计算机专业课练习17.设有x，y，z三个元素顺序进栈，在进栈过程可以出栈，不可能出现的出栈序列为

。A)xyzB)yzxC)zxyD)zyx天津专升本09商大计算机专业课练习18.线性表中各元素之间呈__________关系。A)层次B)网状C)有序D)集合天津专升本09商大计算机专业课练习19.一维数组和线性表的区别是__________。A)前者长度固定，后者长度可变B)后者长度固定，前者长度可变C)两者长度均固定D)两者长度均可变天津专升本09商大计算机专业课练习110.设一环形队列用一维数组A[m]表示，队头和队尾的指针分别为front和tail，则入队时判定队列满的条件是____。A)front=tailB)front=tail+1C)front=(tail+1)%mD)front=tail%m天津专升本09商大计算机专业课练习111.单链表L中，P所指结点为尾结点的条件为________。A)P＝LB)P->next=NULLC)P↑.next:＝LD)P＝nil天津专升本09商大计算机专业课练习112.与数据元素本身的形式、内容、相对位置及个数无关的是数据的________。A)存储结构B)存储实现C)逻辑结构D)运算实现天津专升本09商大计算机专业课练习113.单链表中，增加头结点的目的是________。A)使单链表至少有一个结点B)表示单链表中首结点的位置C)方便运算的实现D)说明单链表是线性表的链式存储结构天津专升本09商大计算机专业课练习114.借助栈输入A、B、C三个元素，则不可能的输出序列是________。A)ABCB)CABC)CBAD)BAC天津专升本09商大计算机专业课练习115.数据结构是一门研究非数值计算的程序设计问题中计算机的____以及它们之间的关系和运算等的学科。

A）数据元素

B）计算方法

C）逻辑存储

D）数据映像天津专升本09商大计算机专业课练习116.算法分析的目的是____。

A）找出数据结构的合理性

B）分析算法的效率以求改进

C）研究算法中的输入和输出的关系

D）分析算法的易懂性和文档性天津专升本09商大计算机专业课练习117.在长度为n的顺序表的第i（1≤i≤n+1）个位置上插入一个元素，元素的移动次数为____。A）n-i+1B）n-iC）iD）i-1天津专升本09商大计算机专业课练习118.设top为栈顶指针，判定一个栈S(最多元素为m)为栈满的条件是____。

A）S->top!=0B）S->top==0C）S->top!=m-1D）S->top==m-1天津专升本09商大计算机专业课练习119.不带头结点的单链表head为空的判断条件为____。

A）head==NullB）head->next==NullC）head->next==headD）head!=Null天津专升本09商大计算机专业课练习120.在一个栈顶指针为HS的链栈中删除一个结点时，用x保存被删除的结点，则执行的操作是____。P47图3.3A）x=HS,HS=HS->next;B）x=HS->data;C）x=HS->data,HS=HS->next;D）HS=HS->next,x=HS->data;天津专升本09商大计算机专业课练习11.栈的基本运算包括____________。

A)删除栈底元素

B)将栈置为空栈

C)判断栈是否为空

D)删除栈顶元素BCD天津专升本09商大计算机专业课练习12.队列的基本运算包括____。

A)从队尾插入一个新元素

B)判断一个队列是否为空

C)从队列中删除第i个元素

D)读取队头元素的值ABD天津专升本09商大计算机专业课练习13.从逻辑上讲，下列属于线性结构的是____。A)有向图B)栈C)线索二叉树D)数组E)串BDE天津专升本09商大计算机专业课练习14.下列关于链式存储结构的叙述中，正确的是____。

A)结点除自身信息外还包括指针域，因此存储密度小于顺序存储结构

B)可以通过计算直接确定第i个结点的存储地址

C)逻辑上相邻的结点物理上不必相邻

D)插入、删除操作方便，不必移动结点ACD天津专升本09商大计算机专业课练习15.下列术语与数据的存储结构无关的术语是____。A)栈B)队列C)散列表D)串ABD天津专升本09商大计算机专业课练习16.设一个链表最常用的操作是在表头插入结点和删除第一个结点，则最节省时间的存储结构为____。

A）单链表

B）仅有头指针的单循环链表

C）双链表

D）仅有尾指针的单循环链表ABC天津专升本09商大计算机专业课练习11.数据结构中与所使用的计算机无关的是数据的逻辑结构。2.栈和队列既可采用顺序存储方式，也可采用链接存储方式。3.线性表是一个有序序列，其中可包含相同的元素，也允许各个元素可以是不同的数据类型。4.队列是允许在队头一端进行插入，在队尾一端进行删除操作的线性表。5.链表的每个结点都含有两个指针。正确12天津专升本09商大计算机专业课练习16..线性结构的基本特征是：每个结点有且仅有一个直接前趋和一个后继。7.线性表中各元素类型必须是相同的。8.数据结构的操作一定是定义在逻辑结构上，实现在存储结构上。9.顺序队列和循环队列的队空和队满判断条件是不一样的。10.数据的逻辑结构指的是数据元素之间的逻辑关系的整体。11.单链表形式的队列，头指针F指向队列的第一个结点，尾指针R指向队列的最后一个结点。正确：7891011天津专升本09商大计算机专业课练习11.数据结构包括的三个方面的内容是

、

和

。2.通常衡量算法效率的一般标准为

和

。3.队列和栈都是线性表。在栈中，

称为栈顶，栈操作的原则是

；队列操作的原则是

_。答案：1逻辑结构、存储结构、运算

2时间复杂度、空间复杂度

3表尾(允许操作的一端)、后进先出、先进先出天津专升本09商大计算机专业课练习14.设栈S的初始状态为空，队列Q的初始状态为

a1a2a3a4↑↑

队头队尾对栈S和队列Q进行如下两步操作：(1)Q中的元素依次出队，并压入栈S中，直至Q为空；(2)依次弹出S中的元素并进入Q，直至S为空。在上述两步操作后，队列Q的状态是

_。答案：a4a3a2a1天津专升本09商大计算机专业课练习15.用一维数组表示线性表L=(a1,a2,……,an)，假定删除表中任一元素的概率相同（都为1/n），则删除一个元素平均需移动的元素个数为________。(n-1)/26.当线性表采用顺序存储结构进行存储时，其主要特点是

________。逻辑结构相邻的结点存储结构也相邻7.具有n个单元的循环队列中，队满时共有________个元素。

n-18.链式存储结构最显著的优点是______。方便插入、删除操作天津专升本09商大计算机专业课练习19.假设以S和X分别表示进栈和出栈操作，若对输入序列1,2,3,4,5进行一系列栈操作SSSXXSXSXX之后，得到的输出序列为

。

参考答案：3245110.设有一个顺序栈S，元素a，b，c，d，e，f依次进栈，如果6个元素的出栈顺序为b，c，d，f，e，a，则顺序栈的容量至少应为————。参考答案：3

天津专升本09商大计算机专业课练习11．如图所示，在栈的输入端有6个元素，输入顺序为A、B、C、D、E、F。能否在栈的输出端得到序列ACEDFB及EDFCAB？若能，写出对栈的操作过程（用push表示进栈，pop表示退栈）；若不能，简述其理由。PUSH(S,A)——A元素进栈POP(S)——栈顶元素出栈输入端输出端栈SABCDEF天津专升本09商大计算机专业课练习11．参考答案：可以产生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商大计算机专业课练习12．解释数据结构、逻辑结构、存储结构的概念，并讨论他们之间的关系；参考答案：数据结构：相互之间存在一种或多种特定关系的数据元素的集合。逻辑结构：逻辑结构描述数据之间的逻辑关系。包括集合、线性、树形和网状结构。存储结构：数据结构在计算机中的表示称存储结构。包括顺序、索引、链式和散列。三者关系：在数据结构中，数据的逻辑结构和存储结构密切相关的；存储结构不仅存储数据元素，还要存储数据元素的逻辑关系；逻辑结构与计算机无关；逻辑结构相同但存储结构不同，可以是不同的数据结构。天津专升本09商大计算机专业课练习13．线性表的顺序存储具有如下缺点：(1).在进行插入或删除操作时，需要移动大量元素；(2).由于难以估计其大小，必须预先分配较大的存储空间，往往使存储空间得不到充分利用；(3).表的容量难以扩充。试问线性表的链式存储结构是否一定能克服上述缺点？试做简要讨论。参考答案：链式存储结构一般克服的顺序结构的三个弱点：

首先，链式存储结构插入、删除不需要移动元素，只需修改指针，时间复杂度为O(1)；其二，不需要预先分配存储空间，可根据需要动态申请；其三，表容量只受内存空间的限制；缺点：因指针增加了内存空间开销，当空间不允许时，就不能克服顺序存储的优点。天津专升本09商大计算机专业课练习11．已知两个带头结点的单链表La和Lb中的元素按非递减顺序排列，试用C语言编写一个函数将这两个有序表合并成一个有序单链表保存在La中，而不改变其排序性。设带头结点的单链表的结点结构说明及函数名如下：typedefstructnode/*定义结点结构*/{datatypedata; structnodenext; }lklist;typedefstructnode*pointer;函数首部为：pointermergelklist(lklistha,lklisthb)pointermergelklist(lklistha,lklisthb){pointer*h,*pa,*pb;pa=ha->next,pb=hb->next；

h=r=ha；

while(pa&&pb)If(pa->data<=pb->data)/*移动ha,hb头指针,修改r指向

{r->next=pa;r=pa;pa=pa->next}；

else{r->next=pb;r=pb;pb=pb->next}；

if(pa==NULL)r->next=pb; if(pb==NULL)r->next=pa; returnh；}天津专升本09商大计算机专业课练习1天津专升本09商大计算机专业课练习12．设计算法求两个递增有序的顺序表L1和L2