计算机软件技术基础所有题目答案-自学
数据结构习题答案 2 第一节概论 2 第二节线性表 5 第三节栈和队列16 第五节树19 第七节查找25 第八节排序29 操作系统练习题参考答案32
数据结构习题答案
第一节概论
一、选择题
1．要求同一逻辑结构的所有数据元素具有相同的特性，这意味着( )。
A．数据元素具有同一的特点~B．不仅数据元素包含的数据项的个数要相同，而且对应数据项的类型要一致 C．每个数据元素都一样 D．数据元素所包含的数据项的个数要相等
2．数据结构是一门研究非数值计算的程序设计问题中计算机的( (1) )以及它们之间的( (2) )和运算的学科。
(1) ~A．操作对象 B．计算方法 C．逻辑存储 D．数据映像
(2) A．结构~B．关系 C．运算 D．算法
3．数据结构被形式地定义为(D，R)，其中D是( (1) )的有限集合，R是D上( (2) )的有限集合。
(1) A．算法~B．数据元素 C．数据操作 D．逻辑结构
(2)A．操作 B．映像 C．存储~D．关系
4．在数据结构中，从逻辑上可以把数据结构分为( )。
A．动态结构和静态结构 B．紧凑结构和非紧凑结构~C．线性结构和非线性结构 D．内部结构和外部结构
5．线性表的顺序存储结构是一种( )的存储结构。
~A．随机存取 B．顺序存取 C．索引存取 D．Hash存取
6．算法分析的目的是( )。
A．找出数据结构的合理性 B．研究算法中的输入和输出的关系~C．分析算法的效率以求改进D．分析算法的易懂性和文档性
7．计算机算法指的是( (1) )，它必须具备输入、输出和( (2) )等五个特征。
(1) A．计算方法 B．排序方法~C．解决某一问题的有限运算序列 D．调度方法
(2) A．可行性、可移植性和可扩充性~B．可行性、确定性和有穷性 C．确定性，有穷性和稳定性 D．易读性、稳定性和安全性
8．线性表若采用链表存储结构，要求内存中可用存储单元的地址( )。
A．必须是连续的 B．部分必须是连续的 C．一定是不连续的~D．连续不连续都可以9．在以下的叙述中，正确的是( )。
A．线性表的线性存储结构优于链式存储结构~B．二维数组是它的每个数据元素为一个线性表的线性表 C．栈的操作方式是先进先出 D．队列的操作方式是先进后出
10．根据数据元素之间关系的不同特性，以下四类基本的逻辑结构反映了四类基本的数据组织形式，其中解释错误的是( )。
~A．集合中任何两个结点之间都有逻辑关系但组织形式松散 B．线性结构中结点按逻辑关系依次排列形成一条“锁链” C．树形结构具有分支、层次特性，其形态有点像自然界中的树D．图状结构中的各个结点按逻辑关系互相缠绕，任何两个结点都可以邻接
11．以下说法正确的是( )。
二、判断题
╳1．数据元素是数据的最小单位。
√2．数据结构是带有结构的数据元素的集合。
√3．数据结构、数据元素、数据项在计算机中的映像分别称为存储结构、结点、数据域。
╳4．数据项是数据的基本单位。
√5．数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用需要建立的。
√6．数据的物理结构是数据在计算机中实际的存储形式。
╳7．算法和程序没有区别，所以在数据结构中二者是通用的。
╳8．顺序存储结构属于静态结构，链式存储结构属于动态结构。
三、填空题
1．所谓数据的逻辑结构指的是数据元素之间的____逻辑关系_____。
2，数据结构是相互之间存在一种或多种特定关系的数据元素的集合，它包括三方面的内容___数据的逻辑结构、数据的存储结构、对数据施加的操作___。
3．数据的逻辑结构包括_____集合结构___、_____线性结构___、____树型结构_____和__图状结构_____四种类型。
4．在线性结构中，开始结点__没有_前驱结点，其余每个结点有且只有__一个_个前驱结点。5．在树形结构中，根结点只有___一个___，其余每个结点有且只有___一个___前驱结点；叶结点没有___后继__结点，其余每个结点的后继结点可以有__任意个__·
6．在图形结构中，每个结点的前驱结点和后继结点可以有___任意个___。
7．算法的五个重要特性是__可行性___、___确定性___、___有穷性___、___输入__、___输出
__。
8．下列程序段的时间复杂度是__O（n）___。
for (i=1；i<=n；i++) A[i，i]=0；
9．下列程序段的时间复杂度是__ O（n2）___。
S=0；
for(i=1；i<=n；i++)
for(j=1；j<=n；j++) s=s+B[i,j]；
sum=s；
10．存储结构是逻辑结构的___物理__实现。
11．从数据结构的观点看，通常所说的“数据”应分成三个不同的层次，即__数据__、__数据元素_和__数据项___。
12．根据需要，数据元素又被称为__结点__、__记录__、___元素__或__顶点_。
13．通常，存储结点之间可以有___顺序存储__、____链式存储__、____索引存储__、___散列存储_四种关联方式，称为四种基本存储方式。
14．通常从___确定性___、__可读性_、___健壮性__、_高效性__等几方面评价算法(包括程序)的质量。
15．一个算法的时空性能是指该算法的_时间复杂度和___空间复杂度_，前者是算法包含的__计算量__，后者是算法需要的___存储量__。
16．在一般情况下，一个算法的时间复杂度是__问题规模__的函数。
n___)、线性阶O(__n__)、平方17．常见时间复杂度的量级有：常数阶O(__1_)、对数阶O(__log
2
阶O(_n2_)和指数阶O(__2n_)。通常认为，具有指数阶量级的算法是__不可行__的。
18．数据结构的基本任务是数据结构的__设计__和__实现__。
19．数据对象是性质相同的__数据元素_的集合。
20．抽象数据类型是指一个__数学模型__以及定义在该模型上的一组操作。
四、应用题
i=1；
WHILE (i<=n) i=i~2；
……
答：O(log2n)
2．叙述算法的定义及其重要特性。
答：算法是对特定问题求解步骤的一种描述，是指令的有限序列。其中每一条指令表示一个或多个操作。算法应该具有下列特性：可行性、确定性、有穷性、输入和输出。
3．简述下列术语：数据，数据元素，数据结构，数据对象。
答：数据是信息的载体，是描述客观事物的数、字符，以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。数据元素是数据的基本单位。在不同的条件下，数据元素又可称为元素、结点、顶点、记录等。数据结构是指相互之间存在着一种或多种关系的数据元素的集合。数据对象是性质相同的数据元素的集合。
4．逻辑结构与存储结构是什么关系？
答：在数据结构中，逻辑结构与存储结构是密切相关的，存储结构不仅将数据元素存储到计算机中，而且还要表示各数据元素之间的逻辑关系。逻辑结构与计算机无关，存储结构是数据元素之间的关系在计算机中的表示。
5．将数量级210，n，n2，n3，nlog
2n，log
2
n，2n，n!，(2／3)n，n2／3按增长率进行排列。
答：(2／3)n，210，log2n，n2／3，n，nlog2n，n2，n3，2n，n!
6．设有数据逻辑结构为：D={k1，k2，k3，…，k9}，R={
答：图略。开始结点k1、k2，终端结点k6、k7。
7．设有如图1.1所示的逻辑结构图，给出它的逻辑结构，并说出它是什么类型的逻辑结构。
答：数据逻辑结构为：D={k1，k2，k3，…，k8}，R={ k4>， 8．分析下列程序的时间复杂度(设n为正整数)。 (1)int rec(int n) {if(n==1)return(1)； else return(n~rec(n-1))； } (2)x=91；y=100； While (y>0) if(x>10) y--； (3)i=1；j=0； while(i+j<=n) if(i>j)j++； else i++; (4)x=n；y=0； while(x>=(y+1)~(y+1)) y++； 答：(1) O(n) (2) O(1) (3) O(n) (4) O(n1/2) while(i<=n-1) {@k+=10~i； i++； ) (2) k=0； for(i=1；i<=n；i++) for(j=i；j<=n：j++) @k++； 答：(1)n-1 (2)n+(n-1)+……+1=n(n+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/2 C．(n-1)/2 D．(n+1)/2 8．在含有n个结点的顺序存储的线性表中，删除一个结点所需移动结点的平均次数为( )。 A．n B．n/2 ~C．(n-1)/2 D．(n+1)/2 9．带头结点的单链表head为空的条件是( )。 A．head=NULL ~B．head->next=NULL C．head->next=head D．head!=NULL 10．非空单循环链表head的尾结点~p满足( )。 A．p->next=NULL B．p=NULL ~C．p->next=head D．p=head 11．在双循环链表的~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； free(p) B．rear=rear->next；free(rear)； C．rear=rear->next->next； free(rear)；~D．p=rear->next->next；rear->next- >next=p->next；free(p)； 16．在一个单链表中，若删除~p结点的后继结点，则执行( )。 ~A．q=p->next；p->next=q->next；free(q)； B．p=p->next；p->next=p->next->next； free(p)； C．p->next=p->next；free(p->next)； D．p=p->next->next；free(p->next)；17．设指针p指向双链表的某一结点，则双链表结构的对称性可用( )式来刻画。 A．p->prior->next->==p->next->next B．p->prior->prior==p->next->prior ~C．p- >prior->next->==p->next->prior D．p->next->next==p->prior->prior 18．在循环链表中，将头指针改设为尾指针rear后，其头结点和尾结点的存储位置分别是( )。 A．rear和rear->next->next ~B．rear->next和rear C．rear->next->next和rear D．rear和rear->next 19．循环链表的主要优点是( )。 A．不再需要头指针了 B．已知某个结点的位置后，容易找到它的直接前驱 C．在进行插入、删除操作时，能更好地保证链表不断开~D．从表中任一结点出发都能扫描到整个链表20．在线性表的下列存储结构中，读取元素花费时间最少的是( )。 A．单链表 B．双链表 C．循环链表~D．顺序表 二、判断题 √1．顺序存储的线性表可以随机存取。 ╳2．顺序存储的线性表的插入和删除操作不需要付出很大的代价，因为平均每次操作只有近一半的元素需要移动。 √3．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。 ╳4．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上不一定相邻。 √5．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。 √6．在单链表中，可以从头结点开始查找任何一个元素。 ╳7．线性表的链式存储结构优于顺序存储结构。 √8．在线性表的顺序存储结构中，插入和删除元素时，移动元素的个数与该元素的位置有关。 ╳9．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。 ╳10．顺序存储方式只能用于存储线性结构。 三、填空题 1．为了便于讨论，有时将含n(n>0)个结点的线性结构表示成(a1，a2，…，an)，其中每个ai代表一个__结点_。a1称为_第一个_结点，an称为__最后一个_结点，i称为ai在线性表中的_位置__。对任意一对相邻结点ai、ai+1(1≤i 2．线性结构的基本特征是：若至少含有一个结点，则除起始结点没有直接__前驱_外，其他结点 有且仅有一个直接__前驱_；除终端结点没有直接__后继_外，其他结点有且仅有一个直接_后继 __。 3．所有结点按一对一的邻接关系构成的整体就是__线性__结构。 4．线性表的逻辑结构是__线性_结构，其所含结点的个数称为线性表的___长度_。 5．在单链表中，删除p所指结点的直接后继的操作是__ q=p->next；p->next=q->next； free(q)；___· 6．非空的单循环链表head的尾结点(由指针p所指)满足__ p->next= head _____。 7．rear是指向非空带头结点的单循环链表的尾指针，则删除起始结点的操作可表示为__ p=rear->next；q=p->next；p->next=q->next；free(q)；____。 8．对于一个具有n个结点的单链表，在p所指结点后插入一个结点的时间复杂度为__O(1)__，在给定值为x的结点后插入新结点的时间复杂度为__ O(n)__。 9．单链表表示法的基本思想是用___指针___表示结点间的逻辑关系。 10．在顺序表中插入或删除一个元素，平均需要移动_一半_元素，具体移动的元素个数与__元素 的位置_有关。 11．在一个长度为n的向量的第i(1≤i≤n+1)个元素之前插入一个元素时，需向后移动___ n- i+1__个元素。 12．在一个长度为n的向量中删除第i(1≤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 答：单循环链表中无论设置尾指针还是头指针都可以遍历表中任一个结点，但设置尾指针时，若在表尾进行插入或删除操作可在O(1)时间内完成，同样在表头进行插入或删除操作也可在O(1)时间内完成。但若设置的是头指针，表尾进行插入或删除操作，需要遍历整个链表，时间复杂度为O(n)。 5．双链表和单循环链表中，若仅知道指针p指向某个结点，不知道头指针，能否将结点~p 从相应的链表中删除？若可以，其时间复杂度各为多少？ 答：能删除。双链表上删除p所指向的结点的时间复杂度为O(1)，单循环链表上删除p所指向的结点的时间复杂度为O(n)。 6．下列算法的功能是什么？ LinkList testl(LinkList L) {//L是无头结点的单链表 ListNode ~q，~p； if(L&&L->next) { q=L； L=L->next； p=L; while(p->next) p=p->next； p->next=q; q->next=NULL；} return L；} 答：如果长度大于1，则将首元结点删除并插入到表尾。 7．如果有n个线性表同时共存，并且在处理过程中各表的长度会发生动态变化，线性表的总长度也会自动地改变。在此情况下，应选择哪一种存储结构？为什么？ 答：应选用链式存储结构。因为顺序表是静态存储结构，只能预先分配，不能随着线性表长度的改变而变化。而链表则可根据需要动态地申请空间，因此适用于动态变化表长的线性表。 8．若线性表的总数基本稳定，且很少进行插入、删除操作，但要求以最快的方式存取线性表的元素，应该用哪种存储结构？为什么？ 答：应选用顺序存储结构。因为顺序存储结构存取元素操作的时间复杂度为O(1)。 五、算法设计题 1．试用顺序表作为存储结构，实现将线性表(a0，a1，a2，…an-1)就地逆置的操作，所谓“就地”是指辅助空间为O(1)。 答：(1)顺序表的就地逆置 分析：分别用两个整型变量指向顺序表的两端，同时向中间移动，移动的同时互换两个下标指示的元素的值。 void Seqreverse(SeqList L){／／顺序表的就地逆置 for(i=0；j=L.1ength-1；i {t=L.data[i]; L.data[i]=L.data[j]; L.data[j]=t; } } (2)链表的就地逆置 分析：本算法的思想是逐个地把L的当前元素r插入到新的链表头部。 void Linkedreverse(LinkedList L){／／链表的就地逆置 p=L->next；L->next=NULL； while(p!=NULL) {r=p，p=p->next；／／r指向当前待逆置的结点，p记下下—个结点 r->next=L—>next；L->next=r；／／放到表头 } } 2．设顺序表L是一个递增(允许有相同的值)有序表，试写一算法将x插入L中，并使L仍为一个有序表。 答：分析：先找到x的正确插入位置，然后将大于x的元素从后向前依次向下移动，最后将x插 i=0; while((i<=L.length-1)&&(x>=L.data[i])) i++；／／找正确的插入位置for(k=L.length-1;k>=i；k--) ／／元素从后往前依次后移 L.data[k+1]：L.data[k]； L.data(i]’x；／／x插入到正确位置 L.1ength++； ) 3.设单链表L是一个非递减有序表，试写一个算法将x插入其中后仍保持L的有序性。 答：分析：此问题的关键是在链表中找到x的插入位置，因此需要两个指针一前一后地依次向后移动。 void LinkListinsert(LinkedList L，int x){／／x插入有序链表L中 q=L；p=q—>next； while(p!=NULL&&p—>data {q=p；p=p—>next； } s=(LinkedList)malloc(sizeof(LNode))；／／生成新结点 S—>data=x； S—>next=p； q—>next=s； } 4. 试写出在不带头结点的单链表的第i个元素之前插入一个元素的算法。 答：分析：对不带头结点的链表操作时，要注意对第一个结点和其他结点操作的不同。 void LinkedListlnsert(LinkedList head，int x，int i) {／／不带头结点的单链表的第i个元素之前插入一个元素 p=L：j=1; while(p!=NULL&&j {p=p—>next；j++；} if(i<=0||p==NULL) printf(”插入位置不正确＼n”)； else {q=(LinkedList)malloc(sizeof(LNode))；q—>data=x； if(i==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表中。 SeqList Seqmerge(SeqList A，SeqList B){／／有序顺序表A和B归并成有序顺序表C i=0；j=0；k=0；／／i，i，k分别为顺序表A，B，C的下标 while(i {if(A.data[i] {C.data[k]=A.data[il；i++； ] else {C.data[k]=B.data[j];j++；} ／／B中当前元素较小 k++； } if (i==m) for(t=j；t else for(t=i；t C.length=m+n； return C;} (2) VOid Linkmerge(LinkedList A，LinkedList B，LinkedList C) {／／有序链表A和B归并成有序链表C {if(pa—>data {qa=pa->next； pC->next=pa； pc=pc->next； pa=qa；} else {qb=pb->next；pc->next=pb：pc=pc->next；pb=qb；} ／／B当前结点值较小 } if(pa)pc—>next=pa；／／A没有结束，将A表剩余元素链接到C表 if(pb)pc—>next=pb；／／B没有结束，将B表剩余元素链接到C表 free(B)；／／释放B表的头结点 } 本算法需要遍历两个线性表，因此时间复杂度为O(m+n)。 6．设指针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中。 void Deletelnsert(LinkedList la，LinkedList lb，int i，int j, int len) {／／删除不带头结点的单链表la中第i个元素起共len个元素,并将这峰元素插入到单链表lb 中第j个结点之前 if(i<0||j<0||len<0) exit(0)； p=la；k=1；pre=NULL； while(p&&k {pre=p； p=p->next; k++； } if(!p) exit(0)； q=p；k=l；／／p指向la表中第i个结点 while(q&&k if(!q) exit(0)； if(pre==la) la=q—>next；／／i=1的情况 else pre—>next=q—>next；／／完成删除 ／／将从la中删除的结点插入到lb中 if(j==1) {q->next=lb； lb=p； } ／／j=1时 else { r=lb; k=1；／／j>1时 while(r&&k if(!r) exit(0)； q—>next=r—>next；r—>next=p；／／完成插入 } } 7．单链表L是一个递减有序表，试写一高效算法，删除表中值大于min且小于max的结点(若表中有这样的结点)，同时释放被删结点空间，这里min和max是两个给定的参数。 答：LinkedList delete(LinkedList L，int min，int max) {／／删除递减有序单链表L中值大于min且小于max的结点 q=L； if(min>max) {printf(”min>max＼n”)；exit(0)；} else p=L—>next；／／q始终指向p的前驱 while(p—>data>=max) ／／当前元素大于或等于max，则p、q依次向后移动 {q=p；p=p—>next；} while((p!=NULL)&&(p一>data>min)) {／／当前元素的值比min大同时比max小，删除p指向的结点 8．编写一个算法将一个头结点指针为pa的单链表A分解成两个单链表A和B，其头结点指针分别为pa和pb，使得A链表中含有原链表A中序号为奇数的元素，而B链表中含有原链表A中序号为偶数的元素，且保持原来的相对顺序。 答：分析：用两个工作指针p和q分别指示序号为奇数和序号为偶数的结点，将q所指向的结点从A表删除，并链接到B表。 void decompose(LinkedList A，LinkedList B) {／／单链表A分解成元素序号为奇数的单链表A和元素序号为偶数的单链表B p=A->next； B=(LinkedList)malloc(sizeof(LNode))； r=B； while(p!=NULL&&p->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，直到有一个表先结束。 SeqLiSt intersection(SeqList A，SeqList B，SeqList C) {／／求元素依值递增有序排列的顺序表A、B的交集C i=0； j=0；k=0； while((i<=A.length-1)&&(j<=B.length-1)) {if(A.data[i]==B.data[j]) ／／找到值相同的元素 {C.data[k]=A.data[i]；／／相同元素写入C表中 k++；i++；j++； } else if(A.data[i] else j++； } C.length=k； return C； } 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)（当m>n时），线性表A、B、C均以单链表作为存储结构，且C表利用A表和B表的结点空间。 答：分析：使p和q指向A和B表当前元素，并分别使nextp和nextq指向p和q的后继，这样将q所指向的结点链接到p的后面，再把nextp和nextq的值赋给p和q，处理下一个结点。void merge(LinkedList A，LinkedList B，LinkedList C) {／／把链表A和B合并为C，A和B的元素间隔排列，且使用原存储空间 p=A—>next；q=B—>next；C=A； while(p&&q) p=nextp； q=nextq； } } 11．假设在长度大于1的单循环链表中，既无头结点也无头指针。s为指向链表中某个结点的指针，试编写算法删除结点~s的直接前驱结点。 答：分析：因为既不知道此单循环链表的头指针，也不知道其尾指针，所以找s的前驱就只能从s 开始，顺次向后寻找。 void DeletePre(LinkedNode ~s) {／／删除单循环链表中结点s的直接前驱 p=s； while(p—>next—>next!=s) p=p—>next；／／找到s的前驱的前驱p q=p—>next；／／q是p的后继，即s的前驱 p—>next=s；／／将q删除 free(q)； } 12．计算带头结点的循环链表的结点个数。 答：int number(LinkedNode head) {／／计算单循环链表中结点的个数 p=head—>next； i=0； while(p!=head) {i++；p=p->next；} return i； } 13．已知由单链表表示的线性表中，含有三类字符的数据元素(如：字母字符、数字字符和其他字符)，试编写算法构造三个以循环链表表示的线性表，使得每个表中只含有同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。 答：分析：p指向待处理的单链表的首元结点，构造三个空的单循环链表，分别存储三类字符，其中一个可使用原来的单链表。q指向p的下一个结点，根据~p的数据域的值将其插入到不同的链表上。再把q的值给p，处理下一个结点。 void change(LinkedList L，LinkedList pa，LinkedList pb，LinkedList pc) {／／分解含有三类字符的单链表为三个以循环链表表示的线性表，使其分别含有三类字符 p=L—>next； pa=L； pa—>next=pa；／／分别构造三个单循环链表 pb=(LinkedList)malloc(sizeof(LNode))； pc=(LinkedList)malloc(sizeof(LNode))； pb—>next=pb；pc—>next=pc； while(p!=L) {q=p—>next；·／／q记下L中下一个结点的位置 if(p—>data<=’z’&&p—>data>=’a’) ／／链接到字母链表的头部 {p—>next=pa—>next；pa—>next=p；} else if (p—>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时就再找下一个Same SeqList IntersectDelete(SeqList A，SeqList B，SeqList C) while(i {if(B.data[j] else if(B.data[j]>C.data[k]) k++; else {same=B.data[j]；／／找到了相同元素same while(B.data[j]==same) j++； while(C.data[k]==same) k++；／j、k后移到新的元素 while(i A.data[m++]=A.data[i++]；／／需保留的元素移动到新位置 while(i } } while(i A.data[m++]=A.data[i++]；／／A的剩余元素重新存储 A.1ength=m； } 15．双循环链表中，设计满足下列条件的算法。 (1)在值为x的结点之前插入值为y的结点。(2)在值为x的结点之后插入值为y的结点。(3)删除值为x的结点。 答：分析：在双循环链表中插入和删除结点要注意修改双向的指针。 typedef struct DLNode {DataType data； struct DLNode~prior，~next；}DLNode，~DLinkedList； void DLinsertl(DLinkedList L，int x，int y) { ／／在双循环链表中插入结点 p=L->next； while(p!=L&&p->data!=x) p=p->next；／／在链表中查找值为x的结点 if(p->data==x) ／／找到值为x的结点 {q=p->prior；／／q指向值为x的结点的前驱 s=(DLinkedList)malloc(sizeof(DLNode))； s->data=y； s->next=p； s->prior=q；／／将y插入到q与p指向的结点之间 p->prior=s；q->next=s； } else{printf(”没有值为x的结点”)；exit(0)；} } void DLDelete(DLinkedList L，int x) {／／在双循环链表中删除结点 p=L->next； while(p!=L&&p->data!=x)p=p->next； if(p->data==x) {p->prior->next=p->next；p->next->prior=p->prior；free(p)；} else{printf(”没有值为x的结点”)；exit(0)；} } 16．设有一个双循环链表，其中有一结点的指针为p，编写算法将p与其右边的一个结点进行交换。 答：void DLchange(DLinkedList p) {／／将双循环链表中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之后 17．设有一个双链表，每个结点中除有prior、data和next三个域外，还有一个可访问颊度域freq，在链表启用之前，其值均初始为0。每当链表进行一次LocateNode(L，x)操作时令元素值为x的结点中freq域的值加l，并调整表中结点的次序，使其按访问频度的递减次序排列，以便使频繁访问的结点总是靠近表头。试写一符合上述要求的LocateNode操作的算法。 答：分析：先在双链表中查找值为x的结点，若找到则使其freq值增1，然后从头至尾扫描链表，将此结点插入到按freq递减顺序排列的正确位置。 typedef struct DLNode {int data，freq；struct DLNode ~prior，~next；}DLNode，~DLinkedList； void LocateNode(DLinkedList head，int x) {／／双链表按访问频度域freq递减次序排列 p2=head； p1=p2—>next；／／p2在前，p1在后 whue(p1) ／／查找单链表中值为x的结点 if(pl—>data==x) {pl—>freq++； break；}／／使值为x的结点的freq加1 else {p2=pl；p1=p2—>next；} if(p1==NULL) printf(”Not found.＼n”)； else{if(p1—>next==NULL) {p2—>next=p1—>next；temp=p1；} ／／在链表中找temp所指向的结点，按freq值递减应插入的位置 else{p2—>next=p1—>next；／／插入链表中间的某一位置 p1—>next->prior=p2； temp=pl；} for(p2=head，p1=p2->next；pl&&p1->freq>temp->freq；p2=p1，pl=p2->next)；／／插入 if(p1==NULL) {p2->next=temp；temp->prior=p2；temp->next=NULL；} else {p2->next=temp；temp->prior=p2；temp->next=pl；p1->prior=temp；} } } 18．给出用单链表存储多项式的结构，并编写一个按指数值递增次序输入所产生的多项式链表的过程。 答：typedef struct PNode {int coef；／／系数 int exp；／／指数 struct Pnode ~next；}~PLink； PLink CreatPoly( ) {／／建立多项式 head=(PLink)malloc(sizeof(struct PNode))； r=head； printf(”输入系数和指数：”)； scanf(&n，&m)； while(n!=0) ／／若n=0则退出循环 {s=(Plink)malloc(sizeof(struct PNode))； s->coef=n；s->exp=m；r->next=s；r=s；／／把s链接到r的后面 printf(”输入系数和指数:”)； scanf(&n，&m)； } r->next=NULL；head=head—>next；／／删除头结点 return head； } 19．根据上题的多项式链表结构，编写一个过程实现两个多项式相加的运算。 答：分析：对所有指数相同的项，将其对应系数相加，若和不为0，则构造新“和多项式”的结点；将所有指数不同的项复制到和多项式中。 Plink add(PLink pa，PLink pb) while(p!=NULL&&q!=NULL) {if(p->exp==q->exp)／／两结点的指数相同时，将两系数相加生成新结点插入c中 {x=p->coef+q->coef； if(x!=0){s=(PLink)malloc(sizeof(struct PNode))；s->coef=x； s->exp=p->exp； r->next=s； r=s； } p=p->next；q=q->next；} else if(p->exp>q->exp)／／两结点的指数不同时，将较小系数的结点复制成新结点插入c 中 {s=(PLink)malloc(sizeof(struct PNode))；s->coef=q->coef；s->exp=q->exp； r->next=s； r=s；q=q->next；} else {s=(PLink)malloc(sizeof(struct PNode))；s->coef=p->coef； s->exp=p->exp；r->next=s；r=s；p=p->next； } } while(p!=NULL) ／／复制A的余下部分 {s=(PLink)malloc(sizeof(struct PNode))；s->coef=p->coef；s->exp=p->exp； r->next=s：r=s；p=p->next；} while(ql=NULL) ／／复制B的余下部分 {s=(PLink)malloc(sizeof(struct PNode))；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的头结点 free(s)； return pc; } 20．约瑟夫环问题：任给正整数n、k，按下述方法可得排列1，2，…，n的一个置换：将数字l，2，…，n环形排列，按顺时针方向从1开始计数；计满k时输出该位置上的数字(并从环中删去该数字)，然后从下一个数字开始继续计数，直到环中所有数字均被输出为止。例如，n=10、k=3时，输出的置换是3，6，9，2，7，1，8，5，10。分别以数组和以不带头结点的、已知尾指针的单循环链表为存储结构解决上述问题。 答：void Js1(int A[n]，int N，iht K) {／／以数组为存储结构 for(i=0；i j=0； for(i=0；i {s=0； while(s printf(”%d”，j)； A[j-1]=0;／／将计满k值的数字输出，并将其位置标为0表明已删除 } } void Js2(LinkedList last，int N，int K) {／／以不带头结点的、已知尾指针的单循环链表为存储结构 p=last； q=p->next；／／此时q为头结点fp为q的前驱 while(N>0) {for(j=2；j<=K；j++) ／／循环K-1次 {p=q；q=p->next；} printf(”%d”，q->data)； N--； p->next=q->next; ／／删除q 第三节栈和队列 一、选择题 1．设有一顺序栈s，元素s1，s2，s3，s4，s5，s6依次入栈，如果6个元素出栈的顺序是s2，s3，s4，s6，s5，s1，则栈的容量至少应该是( )。 A．2 ~B．3 C．5 D．6 2．若一个栈的输入序列是a、b、c，则通过入栈、出栈操作可能得到a、b、c的不同排列个数为( )。 A．4 ~B．5 C．6 D．7 3．设有一顺序栈已经含有3个元素，如图3-1所示，元素a4正等待入栈。以下序列中不可能出现的出栈序列是( )。 ~A．a3，a1，a4，a2 B．a3，a2，a4，a1 C．a3，a4，a2，a1 D．a4，a3，a2，a1 4．和顺序栈相比，链栈有一个比较明显的优势是( )。 ~A．通常不会出现栈满的情况 B．通常不会出现栈空的情况 C．插入操作更容易实现D．删除操作更容易实现 5．若一个栈的输入序列是1，2，3，4，…，n，输出序列的第一个元素是n，则第i个输出元素是( )。 A．不确定 B．n-i ~C．n-i+1 D．n-i-1 6．以下说法正确的是( )。 ~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]=x B．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； 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，a B．d，e，c，b，a ~C．d，c，e，a，b D．a，b，c，d，e 18．一个队列的入队序列是1，2，3，4，则队列的可能的输出序列是( )。 A．4，3，2，1 ~B．1，2，3，4 C．1，4，3，2 D．3，2，4，1 19．设计一个判别表达式中左，右括号是否配对出现的算法，采用( )数据结构最佳。 A．线性表的顺序存储结构~B．栈 C．队列 D．线性表的链式存储结构 二、判断题 √1．在顺序栈栈满情况下，不能再入栈，否则会产生“上溢”。 ╳2．与顺序栈相比，链栈的一个优点是插入和删除操作更加方便。 ╳3．若一个栈的输入序列为1，2，3，…，n，其输出序列的第一个元素为n，则其输出序列的每个元素ai一定满足ai=i+1(i=1，2，…，n)。 √4．在链队中，即使不设置尾指针也能进行入队操作。 √5．在对链队(带头指针)做出队操作时，不会改变front指针的值。 ╳6．循环队列中元素个数为rear-front。 ╳7．一个栈的输入序列是1,2,3,4，则在栈的输出序列中可以得到4,3,1,2． √8．一个栈的输入序列是1,2,3,4，则在栈的输出序列中可以得到1,2,3,4。 ╳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 ___。 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 __；free(p)。 12．对带有头结点的链队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(它是输入序列的一个排列)，则在输出序列中不可能出现这样的情形：存在i 答：p54 2．设有字符串为3~-y-a/y^2，试利用栈写出将其转换为3y-~ay2^/-的操作过程。假定用x代表扫描该字符串过程中顺序取一个字符入栈的操作，用s代表从栈中取出一个字符加入到新字符串尾的出栈操作。例如，ABC变为BCA的操作步骤为XXSXSS。 答：XSXXXSSSXXSXXSXXSSSS 3．设有一个输入序列a，b，c，d，元素经过一个栈到达输出序列，而且元素一旦离开输入序列就不能再回到输入序列，试问经过这个栈后可以得到多少种输出序列? 答：可以得到13种输出序列： abcd,abdc,acbd,acdb,adcb,bacd,bcad,bcda,bdca,cbad,cbda,cdba,dcba. 4．按照运算符优先法，画出对下面算术表达式求值时，操作数栈和运算符栈的变化过程：9- 2~4+(8+1)/3。 答： 序号运算符栈操作数栈输入字 符 1 # 9 2 # 9 - 3 #- 9 2 4 #- 92 ~ 5 #-~ 92 4 6 #-~ 924 + 7 #- 98 8 # 1 9 #+ 1 ( 10 #+( 1 8 13 #+(+ 181 ) 14 #+ 19 / 15 #+/ 19 3 16 #+/ 193 # 17 #+ 13 18 # 4 5．链栈中为何不设置头结点? 答：因为链栈只在链表头插入和删除结点，不可能在链表中间插入或删除结点，算法实现很简单，所以一般不设置头结点。 第五节树 (树根结点的高度为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．63 C．32 D．31 6．将含有41个结点的完全二叉树从根结点开始编号，根为1号，后面按从上到下、从左到右的顺序对结点编号，那么编号为21的双亲结点编号为( )。 ~A．10 B．11 C．41 D．20 7．任何一棵二叉树的叶结点在其前序、中序、后序遍历序列中的相对位置( )。 A．肯定发生变化 B．有时发生变化~C．肯定不发生变化 D．无法确定 8．设二叉树有n个结点，则其深度为( )。 A．n-1 B．n C． └log 2 n ┘ +1 ~D．无法确定 9．设深度为k的二叉树上只有度为0和度为2的结点，则这类二叉树上所含结点总数最少( )个。 A．k+l B．2k ~C．2k-1 D．2k+1 10．下列说法正确的是( )。 ~A．树的前序遍历序列与其对应的二叉树的前序遍历序列相同 B．树的前序遍历序列与其对应的二叉树的后序遍历序列相同 C．树的后序遍历序列与其对应的二叉树的前序遍历序列相同D．树的后序遍历序列与其对应的二叉树的后序遍历序列相同 11．下列说法中正确的是( )。 A．任何一棵二叉树中至少有一个结点的度为2 B．任何一棵二叉树中每个结点的度都为2 C．任何一棵二叉树中的每个结点的度肯定等于2 ~D．任何一棵二叉树中的每个结点的度都可以小于2 12．一棵二叉树满足下列条件：对任意结点，若存在左、右子树，则其值都小于它的左子树上所有结点的值，而大于右子树上所有结点的值。现采用( )遍历方式就可以得到这棵二叉树所有结点的递减序列。 A．前序~B．中序 C．后序 D．层次 13．设森林T中有4棵树，结点个数分别是n1、n2、n3、n4，当把森林T转换成一棵二叉树后，根结点的右子树上有( )个结点。 A．n1-1 B．n1 C．n1+n2+n3 ~D． n2+n3+n4 14．对含有( )个结点的非空二叉树，采用任何一种遍历方式，其结点访问序列均相同。 A．0 ~B．1 C．2 D．不存在这样的二叉树 15．如图6-1所示的二叉树的中序遍历序列是( )。 A．abcdgef ~B．dfebagc C．dbaefcg D．defbagc 16．已知某二叉树的后序遍历序列是deacb，中序遍历序列是deabc，它的前序遍历序列是( )。 A．acbed ~B．baedc C．dceab D．cedba 17．如果T1是由有序树转化而来的二叉树，那么T中结点的前序就是T1中结点的( )。 ~A．前序 B．中序 C．后序 D．层次序 18．某二叉树的前序遍历的结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是( )。 A．bdgcefha B．gdbecfha C．bdgechfa ~D．gdbehfca 19．在图6-2中的二叉树中，( )不是完全二叉树。（~C） 20．树最适合用来表示( )。 A．有序数据元素 B．无序数据元素~C．元素之间具有分支层次关系的数据 D．元素之间无联系的数据 操作系统 1.如何理解虚拟机的概念？ 答：虚拟机就是在裸机上扩展一层软件，将硬件实现细节隐藏起来，使用户能够更方便、更灵活使用的计算机。 2.什么是多道程序设计，它的主要优点是什么？ 答：多道程序设计就是允许多个程序同时进入内存并运行。主要优点：提高资源利用率，从而提高了系统的吞吐量。 3.试述分时系统与实时系统，并比较它们的区别。 答：分时系统是指能够允许多个用户同时使用一台计算机的系统。实时系统是指能够及时响应随机发生的外部事件，并在严格的时间范围内完成对该事件处理的系统。实时系统对系统响应速度要求更高，可靠性要求更高。（或者说明分时系统与实时系统各自特点） 4.一般从哪几方面对操作系统的性能进行评价？ 1）可靠性 2）方便性 3）效率 4）可维护性 5）可移植性 5.试说出几种你所熟悉的操作系统名称，并说明其特征。 答：Linux特征：支持多用户、多任务，具有良好的用户界面，设备独立性，系统安全性能高，良好的可移植性。 Windows特征：支持多用户、多任务，具有友好的图形用户界面，强大的内存管理功能，可靠性高，操作简单。 6.根据你试用计算机系统的经验，说明操作系统的作用。 答：控制和管理计算机系统内各种硬件和软件资源、合理有效地组织计算机系统的工作，为用户提供一个使用方便可扩展的工作环境，从而起到连接计算机和用户的接口作用。 7.如何理解网络操作系统的主要功能？ 答：用于管理网络通信和共享资源，协调各主机上任务的运行，并向用户提供统一的、有效的网络接口，包括网络管理、通信、资源共享、系统安全和多种网络应用服务。 8.如何理解进程的概念？进程与程序的区别是什么？进程与作业的联系和区别是什么？答：进程是一个可以并发执行的程序或程序段在一个数据集合上的执行过程，他是系统分配资源的基本单位。 区别：1）经常是一个动态的概念，是执行程序的动态过程，它因创建而产生，因调度而执行，因撤销而消亡。而程序是一个静态的概念，是进程运行的静态文本。 2）进程能真实地描述并发执行，且具有并发性，而程序没有。 3）一个进程可以执行一个或多个程序。 4）程序可以作为一种软件资源长期保持着，而进程则是程序的一次执行过程，是暂时的，是动态地产生和终止的，它不具有存储性。 作业和进程的联系两者静态描述的结构相似，作业是由程序，数据和JCB组成，进程是由程序或程序段，数据，PCB组成。区别：作业是用户向计算机提交任务实体，而进程是完成用户任务的执行实体；一个作业可由多个进程组成，且必须至少有一个进程。作业一般用于批处理系统中，而进程用在所有多道系统中。 9.理解进程的三种基本状态和发生状态转换的原因。 答：进程的三种基本状态分别执行状态，就绪状态和等待状态。简单来说是由于CPU以及 软件技术基础试题及答案 软件技术基础 系班级姓名成绩 得分评卷 人一、填空题（每空1分，共25分） 1.数据结构作为一门学科，主要研究数据 的、存储结构以及 三方面内容。 2.当对一个线性表经常进行插入或删除操作时，则 宜采用存储结构；而经常进行的是访问操作，而很少进行插入或删除操作时，则宜采用存储结构。 3.在线性结构中，首结点有个前驱结点， 其余每个结点有且只有个前驱结点。4.限定在表的一端进行插入，在表的另一端进行删 除的线性表称为；限定在表的一端进行插入和删除运算的线性表称为。 5.一个8阶的下三角矩阵B按行优先顺序压缩存储 第2页，共19页 6. 第3页，共19页 7. 8.操作系统通过记载、跟 踪、控制进程的执行，它是进程存在的唯一标志。 作业调度程序是从处于状态的作业中选取一个作业并把它装入主存。 12A.软件生命周期瀑布模型一般可分为问题分析、、、 和软件维护五个阶段。 , 得分评卷 人二、选择题（每小题1分，共10分）下列语句正确的是（）。 A. int *p=&x; B. int *p=x; C. int p=&x; D. int *p=*x; 2. int a[ ]={1,2,3,4,5},b[5],*p; 则下列语句中不 正确的语句是（）。 A. p=b+1; B.p=&a[3]; C. p=a; D.b=a; 3. 设有以下说明语句 struct node{ int a；float b；}；struct node node1,node2,*pnode; 则下列语句中正确是（）。 A. node1=node2； B. 第4页，共19页 软件技术基础模拟试题（第二十次省统考） 一、是非判断题（正确选填A，错误选填B）（每小题1分，共10分） 1、数据元素是数据的基本单位，数据项是数据的最小单位。（） 2、栈是特殊的线性表，须用一组地址连续的存储单元来存储其元素。（） 3、引入虚拟存储技术后，逻辑内存总容量是由地址总线的位置确定的。（） 4、编译程序是一种常用应用软件。（） 5、顺序文件和链接文件的长度都可以动态变化。（） 6、在文件系统中采用目录管理文件。（） 7、允许多用户在其终端上同时交互地使用计算机的操作系统称为实时系统。（） 8、程序、数据、和进程控制块是构成一个进程的三要素。（） 9、黑盒测试时，既要考虑程序的内部逻辑结构又要考虑其外部特性。（） 10、软件的总体设计和详细设计都要用PAD图形工具。（） (参考答案：1~10：ABABB ABABB) 二、单项选择题：（每小题1分，共5分） 1、允许用户把若干作业提交计算机系统集中处理的操作系统称为（）。 A分时操作系统B实时操作系统C网络操作系统D批处理操作系统2、分配到必要资源并获得了处理机时的进程的状态称为（）。 A就绪状态B执行状态C等待状态D阻塞状态 3、利用通道技术可以在（）之间直接交换数据。 A内存与CPU B CPU与外设C内存与外设D内存、CPU和外设三者4、以下的准则中哪个不是软件设计的准则（）。 A编程语言选择准则B信息屏蔽准则 C结构化和模块化准则D抽象准则 5、有一数列：97657613294958经过一趟排序后得到： 65971376294958请问使用的是何种排序方法？（） A简单插入排序B冒泡排序C2路归并排序D快速排序 (参考答案：DBCAC) 软件技术基础模拟试题（第十九次省统考） 一、是非判断题（正确选填A，错误选填B）（每小题1分，共10分） 1、在目前，用于保证软件质量的主要手段是进行软件测试。（） 2、使用DMA方式传送数据期间不需要CPU干预。（） 3、线性顺序队列会产生“假溢出”，而线性循环队列则不会。（） 4、对同一种算法，用高级语言编写的程序比用低级语言编写的程序运行速度快。（） 5、在线性表中，数据的存储方式有顺序和链接两种。（） 6、进程由程序块、文件控件块和数据块三部分组成。（） 7、在面向对象的程序设计中，派生类只能从一个基类产生。（） 8、操作系统是用户和硬件的接口。（） 9、个人计算机中可配置的最大内存容量受地址总线位数的限制。（） 10、软件维护中最困难的问题是软件配置不全。（） (参考答案：1~10：A、A、A、B、A、B、A、A、A、B) 二、单项选择题：（每小题1分，共5分） 1. 某人因为迟到被扣了当月的奖金，这对他的同事来说是何种性质的强化？（） A)正强化 B)负强化 C)惩罚 D)消除 2. 有些人从某一职位退下来后，常抱怨“人走茶凉”，这反映了他们过去在单位中拥有的职权是一种（）： 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. “明确而不含糊，能使员工明确组织期望他做什么、什么时候做以及做到何种程度。”描述的是：有效目标应该是（） 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)人口数量 B)儿童口味 C)家庭收入 D)计划生育政策 13. 技术创新主要涉及（）等不同方面 A)材料、产品、工艺、手段 B)销售、研发 第一章信息与计算机 1.1 什么是信息？信息与数据的区别和联系在何处？ 信息定义之一：信息是现实世界中存在的客观实体、现象、关系进行描述的数据。信息定义之二：信息是经过加工后并对实体的行为产生影响的数据。 与数据的区别和联系：数据定义：数据是现实世界客观存在的实体或事物的属性值，即指人们听到的事实和看到的景象。我们把这些数据收集起来，经过处理后，即得到人们需要的信息。信息和数据的关系可以归结为： 1. 信息是有一定含义的数据。 2. 信息是经过加工（处理）后的数据。 3. 信息是对决策有价值的数据。 1.2 信息有哪些基本属性？ 信息的基本属性有： 1. 事实性。 2. 等级性。 3. 可压缩性。 4. 可扩散性。 5. 可传输性。 6. 共享性。 7. 增值性和再生性。 8. 转换性。 1.3 计算机的主要特点是什么？ 计算机最主要的特点是： 1. 高速自动的操作功能。 2. 具有记忆的能力。 3. 可以进行各种逻辑判断。 4. 精确高速的计算能力。 1.5 完整的计算机系统应该包括哪几部分？ 目前最完整的计算机系统学说认为由五部分组成： 1. 人员 2. 数据 3. 设备 4. 程序 5. 规程 1.6 什么是计算机硬件？什么是计算机软件？ 硬件：泛指实际存在的物理设备，包括计算机本身及其外围设备。 微型计算机的硬件系统：主机、外存储器、输入设备、输出设备、微机的系统总线。 软件：是指计算机程序、方法、规则的文档以及在计算机上运行它时所必须的数据。计算机软件一般分为系统软件和应用软件。 1.8 软件技术发展的几个阶段各有什么特点？它与硬件的关系如何？ 第一阶段：高级语言阶段特点：这一时期，编译技术代表了整个软件技术，软件工作者追求的主要目的是设计和实现在控制结构和数据结构方面表现能力强的高级语言。但在这一时期内，编译系统主要是靠手工编制，自动化程度很低。硬件关系：此时期计算机的硬件要求仅能用机器指令来编制可运行的程序。 第二阶段：结构程序设计阶段特点：在程序的正确性方面，提出了结构化程序设计思想使程序的可靠性提高了。程序设计方法论方面，提出由顶向下法和自底向上法。使程序模块化，使问题的复杂性和人的思维统一起来了。出现了软件生产管理。硬件关系：磁盘问世，操作系统发展，非数值计算应用发展，通信设备完善，网络发展，集成电路发展等使软件复杂性增加产生软件危机，在此背景下发展了软件技术。 第三阶段：自动程序设计阶段特点：向集成化、一体化发展。出现了软件开发环境。程序设计基本方法进一步改进。硬件关系：集成电路迅速发展以及高分辨率终端的出现，为个人计算机发展提供了条件，再加上人工智能、专家系统研究的发展，使程 管理学原理作业 一、单选题（每小题3分，共18分） 1.管理的核心是( D ) A.决策 B.领导 C.激励 D.处理好人际关系 2.霍桑实验的结论中对职工的定性是（B ） A．经济人B．社会人C．自我实现人D．复杂人 3.古典管理理论阶段的代表性理论是( A ) A.科学管理理论B 行政组织理论C.行为科学理论 D.权变理论 4.直线型组织结构一般只适用于（B ） A．需要按职能专业化管理的小型组织B．没有必要按职能实现专业化管理的小型组织C．需要按职能专业化管理的中型组织D．需要按职能专业化管理的大型组织 5.双因素理论中的双因素指的是（D ） A.人和物的因素 B.信息与环境 C. 自然因素和社会因素 D.保健因素与激励因素 6.专业化管理程度高,但部门之间协调性比较差,并存在多头领导现象.这是哪类组织结构类型的特点？（B） A.直线制 B.职能制C直线职能制 D.事业部制 E.矩阵制 二、判断题（每小题2分，共20分） 1.权变理论是基于自我实现人假设提出来的. (×) 2.需求层次论是激励理论的基础理论。( √ ) 3.决策最终选择的一般只是满意方案，而不是最优方案。( √ ) 4.管理幅度是指一个管理者直接指挥下级的数目. 管理幅度应该适当才能进行有效的管理. ( √ ) 5.冲突对组织都是有害的,冲突管理就是要尽可能减少或消除冲突. (×) 6.管理的效益原理认为:管理工作都应该力图以最小的投入和消耗,获取最大的收益. ( √ ) 7.最小后悔值决策方法中的后悔值就是机会损失值. ( √ ) 8.公平理论认为一个人的公平感觉取决于其每次的投入与报酬之间是否对等. (×) 9.高语境文化中的人们更加倾向于坦率的和直接的交流方式(×) 10. “胡萝卜加大棒”是泰勒制的管理信条。( √ ) 三、多选题（每小题5分，共30分） 1.管理的二重性是指管理的( AD ) A.自然属性 B.艺术性 C. 科学性 D.社会属性 E.实践性 2.管理的主要职能包括( ABEF ) A.计划 B.组织 C.指挥 D.协调 E.领导 F.控制 3.管理的主要技能包括( ACD ) A.人际 B.诊断 C.概念 D.技术 《计算机软件技术基础(1)》在线作业一 1. 在设计阶段，当双击窗体上的某个控件时，所打开的窗口是（）。 A. 工程资源管理器窗口 B. 工具箱窗口 C. 代码窗口 D. 属性窗口 正确答案：C 满分：5 分得分：5 2. 下面哪条语句可以正确地声明一个动态数组：（）。 A. Dim A(n) As Integer B. Dim A(1 To n) As Integer C. Dim A() As Integer D. Dim A( , ) As Integer 正确答案：C 满分：5 分得分：5 3. 从键盘上输入两个字符串，分别保存在变量str1、str2中。确定第二个字符串在第一个字符串中起始位置的函数是（）。 A. Left B. Mid C. String D. Instr 正确答案：D 满分：5 分得分：5 4. 下列叙述中正确的是（）。 A. 在窗体的Form_Load事件过程中定义的变量是全局变量 B. 局部变量的作用域可以超出所定义的过程 C. 在某个Sub过程中定义的局部变量可以与其它事件过程中定义的局部变量同名，但其作用域只限于该过程 D. 在调用过程时，所有局部变量被系统初始化为0或空字符串 正确答案：C 满分：5 分得分：5 5. 设标签Label1的Caption属性值为默认值，则该标签控件Name属性和Caption属性的值分别为（）。 A. “Label”、“Label” B. “Label1”、“Label1” C. “Label”、“Label1” D. “Label1”、“Label” 正确答案：B 满分：5 分得分：5 6. 下面的动作中，不能引发一个按钮Click事件的是：（）。 A. 在按钮上单击 B. 在按钮上右击 C. 把焦点移至按钮上，然后按回车键 D. 如果按钮上有快捷字母，按“Alt+该字母” 正确答案：B 满分：5 分得分：5 7. 在窗体Form1的Click事件过程中有以下语句：Label1.Caption=”Visual BASIC”设标签的原Caption属性值为默认值，则该语句执行之后该标签控件Name属性和Caption属性的值分别为（）。 软件技术基础模拟试题（第二十四次省统考） 一、是非判断题（正确选填A，错误选填B）（每小题1分，共10分） 1. 顺序表和线性链表的物理存贮形式都是顺序存贮。( 1 ) 2. 数据类型是某种程序设计语言中已实现的数据结构。( 2 ) 3. 如果通过软件测试没有发现错误，则说明软件是完全正确的。( 3 ) 4. 快速原型模型可以有效地适应用户需求的动态变化。( 4 ) 5. 不同进程之间的动作在时间上不能重叠。( 5 ) 6. 分区式存储管理能够进行存储空间共享。( 6 ) 7. 链接文件和索引文件都可以非连续存放。( 7 ) 8. 中断处理一般分为中断响应和中断处理两个步骤。前者由软件实施，后者主要由硬件实施。( 8 ) 9. 在C++语言中，“重载”表达了最简单的多态性。( 9 ) 10.进程调度根据一定的调度算法，从等待队列中挑选出合适的进程。( 10 ) (参考答案：1~10：ABBAB BABAB ) 二、单项选择题：（每小题1分，共5分） 1. 在数据结构中，一个存储结点存放一个（11 ）。 11 (A) 数据项(B) 数据元素(C) 数据结构(D) 数据类型 2. 把逻辑地址转变为存储的物理地址的过程称作（12 ）。 12 (A) 编译(B) 连接(C) 运行(D) 重定位 3. SPOOLing技术可以实现设备的（13 ）分配。 13 (A) 虚拟(B) 共享(C) 独占(D) 物理 4. 允许用户把若干作业提交计算机系统集中处理的操作系统称为（14 ）。 14 (A) 分时操作系统(B) 实时操作系统 (C) 网络操作系统(D) 批处理操作系统 5. 进程从运行状态进入就绪状态的原因可能是（15 ）。 15 (A) 被选中占有处理机(B) 时间片用完 (C) 等待的事件已发生(D) 等待某一事件 (参考答案：BBADB) 软件技术基础模拟试题（第二十三次省统考） 一、是非判断题（正确选填A，错误选填B）（每小题1分，共10分） 1. 数据在计算机内在中的表示是指数据的存储结构。( 1 ) 2. 能影响中断响应次序的技术是中断优先级和中断屏蔽。( 2 ) 3. 链表可以随机访问任意一个结点，而顺序表则不能。( 3 ) 4. 作业与进程的主要区别是前者是由用户提交，后者是由系统自动生成。( 4 ) 5. Windows、OS/2、Linux微机操作系统都是多用户多任务操作系统。( 5 ) 6. 数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储结构无关，是独立于计算机的。 ( 6 ) 7. 流式文件和记录式文件都以字符为基本单位进行存取。( 7 ) 8. 不定长文件是指字段的长度不固定。( 8 ) 9. 软件工程的三要素包括方法、工具和环境。( 9 ) 10.软件结构是以指令为基础而组成的一种控制层次结构。( 10 ) (参考答案：1~10：AABAB ABBBB) 二、单项选择题：（每小题1分，共5分） 1. 若进栈序列为1,2,3,4，且进栈过程中可以出栈，则不可能出栈的序列是 ( 11 ). 11 (A) 1,4,3,2 (B) 2,3,4,1 (C) 3,1,4,2 (D) 3,4,2,1 《管理学》 一．名词解释 1．管理职能：是指管理者为实现有效管理所应具备的管理功能。包括计划，组织，指挥，协调控制功能。 2．管理者：是指组织中管理指令的发出者，是管理活动的领导和组织者。是运用职位权力对人进行统驭和指挥的人。 3．管理环境：是指存在于一个组织内外部的影响组织业绩的各种力量和条件因素的总和。包括组织外部环境和内部环境。 4．组织文化：是组织在长期的发展过程中逐步形成和发展起来的日趋稳定的独特的价值体系，包括价值观，组织精神，伦理道德准则，组织素养，行为规范，群体意识等。 5．社会责任：是一种组织追求有利于社会的长远目标且不是法律和经济所要求的义务。 6．管理道德：是指组织在管理过程中自觉遵守的各种行为准则和规范的总和。包括社会道德，职业道德，个人道德。 7．目标管理：是一种综合的以工作为中心和以人为中心的管理方法，它首先由一个组织中的上级管理人员与下级管理人员，员工一起制定组织目标，并由此形成组织内每一个成员的责任和分目标，明确规定每个人的职责范围，最后用这些目标来进行管理，并评价和决定对每一个部门和成员的奖惩。 8．职能权力：是某一人员或部门根据高层管理人员的授权而拥有的对其他部门或人员直接指挥的权力。职能权力是一种有约束力的权力，它只能在被授权的职能范围之内有效。 9．管理幅度：是指一名管理人员直接而有效地领导和指挥下属的人数。在组织人员一定的情况下，管理幅度越大，即一个管理人员能直接管理的下属人数越多，组织中的管理层次也就越少，所需的行政管理人员也越少，反之，管理幅度越小，所需的管理人员就越多，相应的管理层次也越多。10．组织设计：亦即组织结构设计，就是对组织结构的组成要素和它们之间联接方式的设计，它是根据组织目标和组织活动的特点，划分管理层次，确定组织系统，选择合理的组织结构形式的过程。 11．集权：是指组织中把决策的权力集中在较高层次的管理部门，下级的一切行动听上级的命令和指挥。绝对的集权就是最高主管把所有的权力集中在自己手里，因而也不存在组织，集权与分权是相对而言的。某种程度的集权和某种程度的分权，对组织都是必要的。 12．授权：就是管理者将自己的部分决策权或工作负担转授给下属的过程。授权可以使管理者不必亲历亲为，从而把更多的时间和精力投入到大的决策中，更好地引领下属完成组织目标。13．领导权力：就是领导者对被领导者做出一定行为与施行一定影响的能力。领导权力的构成是领导者影响力的来源，领导者的来源包括：职位权力和非职位权力。 14．沟通：是为了一个设定的目标，进行个人或群体间的信息传递，交流以达成共同协议的过程。 沟通确保组织内的各部门，各个人可以获得工作所需的各种信息，增进相互间的了解和合作，沟通在管理人员工作中非常重要，对工作有特别重大的意义。 15．激励：是领导者激发和鼓励组织成员朝着组织所期望的目标采取行动的过程。 16．控制：是指管理者按计划，目标，制定管理标准，并对组织运行过程和结果进行检查，找出差异，分析原因，采取措施，及时纠正偏差，保证组织目标的实现。 第六篇创新 一、单项选择题 1、创新是 (A) A 以市场为主导 B 以生产为主导 C 以成本为主导 D 以竞争为主导 2、创新 (C) A 一定会提升企业竞争力 B 一定不会提升企业竞争力 C 可以也许不可能提升企业竞争力 D 创新与是否能够提升企业竞争力无关 3、创新的关键是 (C) A 领导力 B 组织能力 C 创新能力 D 竞争能力 4、创新的第一步应该 A 寻找机会 B 设(A) 计行动方案 C 等待时机 D 提出构思 二、多项选择题 1、创新也具有不确定性这是创新受到以下哪些原因影响所致 (ACD) A 市场的不确定性 B 制度的不确定性 C 技术的不确定性 D 战略的不确定性 E 创新结果的不确定性 2、创新的破坏性的具体表现在以下哪些地方 (ACDE) A 企业丧失了原有的技术优势 B 企业用新技术替代了原来的技术 C 企业用新的但是不能正常运用的新技术替换了原来虽落后但擅长的技术 D 企业没能力利用创新的资源 E 企业虽能运用创新所得新技术但失去了市场 3、创新的主体有 (ABCD) A 全体员工 B 各级管理者 C 各方面的专家 D 领导者 E 相关利益者 4、成功的创新需经历下列过程 (ABDE) A 寻找机会 B 提出构想 C 等待时机 D 迅速行动 E坚持忍耐 三、判断题 1、所谓创新就是一种影响更大的的发明× 2、创新既有一种创造力又有一种巨大的破坏力√ 3、在企业中的创新就是企业创新，也叫管理创新× 4、创业可以保护企业原有的优势，又可以摆脱去医院有的劣势，这就是创新的破坏性与保护性特征的体现× 四、名词解释题 1、企业创新:是指从构想新概念开始，到渗透到具体的生产、操作，形成真正的生产力，从而进入市场，最终获得经济效益的全过程 2、管理创新:就是全体管理者和员工创造一种新的管理要素组合并加以实施的过程，这种新的管理要素组合具有倍增效应，存在具有放大机制的管理倍数，能更好高效地实现企业目标。 3、创新型企业:创新型企业是指拥有自主知识产权的核心技术、知名品牌，具有良好的创新管理和文化，整体技术水平在同行业居于先进地位，在市场竞争中具有优势和持续发展能力的企业。 五、简答题 1、创新与企业创新的意义 答：意义：创新可以提高企业竞争实力、可以将企业的劣势转化为优势、将不利因素转化为有利因素、为企业长期持续发展提供动力、是企业的根本。 2、简述创新与发明、创造之间的异同之处 答：创新不同于发明、创造，也不仅仅是高、精、尖、奇。创新是以市场为导向，以提高经济效益为最终目的的。 3、简述成功的创新之路应该怎么走 答：成功的创新要经历四个阶段：寻找机会——提出构想——迅速行动——忍耐坚持。 4、简述企业的发展模式为什么回想创新型企业发展 答：因为创新可以提高企业竞争实力、可以将企业的劣势转化为优势、将不利因素转化为有利因素、为企业长期持续发展提供动力、是企业的根本。企业为了能够获得更多的利润，可持续发展，必须不断的创新，从效率型升至质量型升至灵活性，最终成为创新型企业。 5、简述企业家在企业创新中的地位与作用 答：创新型企业家是管理创新成败的的关键人物、企业家是企业的灵魂、真正 《操作系统》 选择题： （bs30）1. 分页式存储管理的主要特点是（B）。 (A) 要求作业全部同时装入内存(B) 不要求作业装入到内存的连续区域 (C) 要求扩充外存容量(D) 不要求处理缺页中断 （bs30）2. 进程从运行状态进入就绪状态的原因可能是（D）。 (A) 被选中占有处理机(B) 等待某一事件(C) 等待的事件已发生(D) 时间片用完 （bs30）3. 多道程序设计是指（D）。 (A) 在实时系统中并发运行多个程序(B) 在分布系统工程中同一时刻运行多个程序 (C) 在一台处理机上同一时刻运行多个程序(D) 在一台处理机上并发运行多个程序 （bs29）2. 进程从运行状态进入就绪状态的原因可能是（ A ）。 (A) 时间片用完(B) 等待某一事件(C) 等待的事件已发生(D) 被选中占有处理机（bs29）4. 以下（D）不是实时操作系统的特点。 (A) 高可靠性(B) 及时响应(C) 高效性(D) 通用性 （bs28）3. 任何两个并发进程之间（ A ）。 (A) 可能存在同步或互斥关系(B) 一定存在同步关系 (C) 一定彼此独立无关(D) 一定存在互斥关系 （bs28）4. 以下的哪个特征不是分时操作系统的主要特征（B）。 (A) 分时性(B) 独占性(C) 交互性(D) 多路性 （bs27）2. 以下（D）不是实时操作系统的特点。 (A) 高可靠性(B) 及时响应(C) 中断管理(D) 独立性 （bs27）3. 若当前进程因时间片用完而让出处理机时，该进程应转变为（B）状态。 (A) 运行(B) 就绪(C) 等待(D) 完成 （bs26）3. 在多道程序设计系统中，处于后备状态的作业要经过（D）调度后才能真正执行。 (A) 作业调度(B) 作业调度和设备调度(C) 进程调度(D) 作业调度和进程调度 （bs25）1. 把高级语言的源程序翻译成二进制代码的过程称为：（A）。 (A) 编译(B) 连接(C) 运行(D) 重定位 （bs25）2. 把逻辑地址转变为内存的物理地址的过程称作（D）。 (A) 地址分配(B) 地址连接(C) 地址调用(D) 地址变换 （bs25）4. 在操作系统中，进程最基本的特征是（A）。 (A) 动态性和并发性(B) 顺序性和可再现性 (C) 与程序的对应性(D) 执行过程的封闭性 （bs24）2. 把逻辑地址转变为存储的物理地址的过程称作（D）。 (A) 编译(B) 连接(C) 运行(D) 重定位 （bs24）3. SPOOLing技术可以实现设备的（B）分配。 (A) 虚拟(B) 共享(C) 独占(D) 物理 （bs24）4. 允许用户把若干作业提交计算机系统集中处理的操作系统称为（D）。 (A) 分时操作系统(B) 实时操作系统 (C) 网络操作系统(D) 批处理操作系统 （bs24）5. 进程从运行状态进入就绪状态的原因可能是（B）。 (A) 被选中占有处理机(B) 时间片用完 (C) 等待的事件已发生(D) 等待某一事件 （bs23）2. 任何两个并发进程之间( D) (A) 一定存在互斥关系(B) 一定存在同步关系 (C) 一定彼此独立无关(D) 可能存在同步或互斥关系 软件技术基础模拟试题（第二十次省统考） 1、是非判断题（正确选填A，错误选填B）（每小题1分，共10 分） 1、数据元素是数据的基本单位，数据项是数据的最小单位。（ ） 2、栈是特殊的线性表，须用一组地址连续的存储单元来存储其元素。（ ） 3、引入虚拟存储技术后，逻辑内存总容量是由地址总线的位置确定的。（ ） 4、编译程序是一种常用应用软件。（ ） 5、顺序文件和链接文件的长度都可以动态变化。（ ） 6、在文件系统中采用目录管理文件。（ ） 7、允许多用户在其终端上同时交互地使用计算机的操作系统称为实时系统。（ ） 8、程序、数据、和进程控制块是构成一个进程的三要素。（ ） 9、黑盒测试时，既要考虑程序的内部逻辑结构又要考虑其外部特性。（ ） 10、软件的总体设计和详细设计都要用PAD图形工具。（ ） (参考答案：1~10：ABABB ABABB) 2、单项选择题：（每小题1分，共5分） 1、允许用户把若干作业提交计算机系统集中处理的操作系统称为 （ ）。 A 分时操作系统 B 实时操作系统 C 网络操作系统 D 批处理操作系统 2、分配到必要资源并获得了处理机时的进程的状态称为（ ）。 A 就绪状态 B 执行状态 C 等待状态 D 阻塞状态3、利用通道技术可以在（ ）之间直接交换数据。 A 内存与CPU B CPU与外设 C 内存与外设 D 内存、CPU和外设三者 4、以下的准则中哪个不是软件设计的准则（ ）。 A 编程语言选择准则 B 信息屏蔽准则 C 结构化和模块化准则 D 抽象准则 5、有一数列：97 65 76 13 29 49 58 经过一趟排序后得到： 65 97 13 76 29 49 58 请问使用的是何种排序方法？（ ） A 简单插入排序 B 冒泡排序 C 2路归并排序 D 快速排序 (参考答案：DBCAC ) 一、名词解释（本大题共7小题，每小题3分，共21分） 管理： 管理是通过计划、组织、控制、激励和领导等环节来协调人力、物力和财力资源，以期更好地达成组织目标的过程。 目标管理： 目标管理是以目标的设置和分解、目标的实施及完成情况的检查、奖惩为手段，通过员工的自我管理来实现企业的经营目的一种管理方法。 预测： 预测就是根据过去和现在的已知因素，运用已有的知识、经验和科学方法，对未来环境进行预先估计，并对事物未来的发展趋势做出估计和评价。 决策： 决策是对未来的行为确定目标，并从两个或两个以上的可行方案中，选择一个合理方案的分析判断过程，即多方案择优。 人员配备： 人员配备，是指对人员进行恰当而有效地选拔、培训和考评，其目的是为了配备合适的人员去充实组织机构中所规定的各项职务，以保证组织活动的正常进行，进而实现组织的既定目标。 激励： 激励是指人类的一种心理状态，它具有加强和激发动机，推动并引导行为指向目标的作用。 控制： 控制是指接受系统内外的有关信息，按既定的目标对系统进行监督、检查、发现偏差，采取正确的措施使系统按预定的计划运行，或适当的调整计划，以达到预期目的的管理活动。 二、单项选择题(本大题共15小题，每小题1分，共15分)在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。 1．管理的性质不包括（C） A.二重性 B.科学性 C.理论性 D.艺术性 2．人们常说，身体是“三分治七分养”，对于这件事（D） A．反馈控制比前馈控制更重要B．现场控制比反馈控制更重要 C．反馈控制比现场控制更重要D．前馈控制比反馈控制更重要 3．打电话请供应商来换一台同目前用坏的机器一样的设备，这是设备的简单替换问题，需要的管理技能主要是（B） A. 概念技能和技术技能 B.人际技能和技术技能 C.技术技能 D.人际技能和概念技能 4．差别计件工资制是（A）的内容之一。 A．泰罗的科学管理理论B．法约尔的一般管理理论 C．韦伯的行政管理理论D．现代管理理论 5．没有一个固定的信息中心，成员之间总是互相传递信息的是（C） A．园型沟通B．Y型沟通 C．全通道型沟通D．轮型沟通 6. 根据计划的明确性，可以将计划分为（C） 软件技术基础 系班级姓名成绩得分评卷人 一、填空题（每空1分，共25分） 1.数据结构作为一门学科，主要研究数据的、存储结构以及 三方面内容。 2.当对一个线性表经常进行插入或删除操作时，则宜采用存储结构；而经常进 行的是访问操作，而很少进行插入或删除操作时，则宜采用存储结构。 3.在线性结构中，首结点有个前驱结点，其余每个结点有且只有个前驱结点。 4.限定在表的一端进行插入，在表的另一端进行删除的线性表称为；限定在表 的一端进行插入和删除运算的线性表称为。 5.一个8阶的下三角矩阵B按行优先顺序压缩存储在一维数组中，则数组的大小应设 为。 6.按照二叉树的定义，具有3个结点的二叉树形态有种；具有65个结点的完全二叉 树其深度为; 深度为10的完全二叉树最多有个结点 7.在长度为n的顺序表的第i个位置上插入一个元素，元素的移动次数为；删除 第i个元素时，需要从前向后依次前移个元素。(1≤i≤n+1) 8. 顺序存储结构的循环队列中，设front 和rear分别为队头和队尾指示器，该队列中能存放的 最大元素的个数为M AX-1，则判断队列为满的条件为，而判断队列为空的条件是。 9. 设D={A，B，C，D，E}，R={ 和软件维护五个阶段。 , 得分评卷人 二、选择题（每小题1分，共10分） 1. 已知：int x; 下列语句正确的是（）。 A. int *p=&x; B. int *p=x; C. int p=&x; D. int *p=*x; 2. int a[ ]={1,2,3,4,5},b[5],*p; 则下列语句中不正确的语句是（）。 A. p=b+1; B.p=&a[3]; C. p=a; D.b=a; 3. 设有以下说明语句 struct node{ int a；float b；}； struct node node1,node2,*pnode; 则下列语句中正确是（）。 A. node1=node2； B. pnode.a=10； C. return (node1+node2)； D. scanf(“%d %f”,node1); 4. 线性链表不具有的特点是（）。 A. 可随机访问任一个结点B．不必事先估计所需存储空间大小 C. 插入与删除时不必移动元素D．所需空间与线性表长度成正比 5. 若让元素1，2，3依次进栈，则出栈次序不可能出现（）种情况。 A．3，2，1 B．2，1，3 C．3，1，2 D．1，3，2 6. 有向图的邻接表中，顶点Vi的出度是（）。 A. 依附于Vi的弧数 B.Vi链表中的邻接结点个数 C. Vi在表结点中出现的次数 D. Vi度的一半 7. 某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。 A．空或只有一个结点B．深度等于其结点数 C．任一分支结点均无左子树D．任一分支结点均无右子树 管理学试题和答案 第一章管理概述 一、单选题 1.“士为知己者死”这一古训反映了有效的领导始于 A. 上下级之间的友情 B. 为下属设定崇高的友情 C. 为下属的利益不惜牺牲自己 D. 了解下属的欲望和需要 2.种庄稼需要水，但这一地区近年老不下雨，怎么办？一种办法是灌溉，以补天不下雨的不足。另一办法是改种耐旱作物，使所种作物与环境相适应。这两种措施分别是 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.以下何种组织形式最直接体现管理劳动专业化分工的思想？ A. 直线型 B. 直线职能制 C. 事业部制 D. 矩阵型 8.玛丽最近提升为领班，她去征求过去一位做过领班工作的朋友的意见，这位朋友对她道出三大职位成功要素： 第一，理解人，能敞开地和人沟通，能在部门内外和他人一起工作； 第二，理解组织整体结构，能解释组织计划和目标，并转化为本部门目标，能预见问题并处理； 第三，能使自己的想法和建议被上司接受；维护权威，尊重管理阶层。 请问，这三点建议，那一点涉及人际技能？ A. 第一和第二 B. 第一和第三 C. 第二和第三 D. 第一 9.某项调查显示所在区域内企业职工状况时发现三种现象： 第一，该区域大龄青年很多，常为自己的婚姻问题而苦恼； 第二，周围治安秩序不好，做三班的女工在夜间上下班经常遇到流氓干扰不安心工作； 第三，区域内的一些电器厂家发展迅速，由于行业内形成了研发创新的气氛，且有一些研究人员迫切从事这方面的研究，甚至投入大量业余时间开发设计新的应用产品。 以上现象体现了： A. 生理需要、安全需要和尊重需要 B. 社会需要、安全需要和尊重需要 第一章 1.1什么是信息？信息与数据的区别和联系在何处？ 信息定义之一：信息是现实世界中存在的客观实体、现象、关系进行描述的数据。 信息定义之二：信息是经过加工后并对实体的行为产生影响的数据。 与数据的区别和联系： 数据定义：数据是现实世界客观存在的实体或事物的属性值，即指人们听到的事实和看到的景象。 我们把这些数据收集起来，经过处理后，即得到人们需要的信息。 信息和数据的关系可以归结为： 1.信息是有一定含义的数据。 2.信息是经过加工（处理）后的数据。 3.信息是对决策有价值的数据。 1.2信息有哪些基本属性？ z信息的基本属性有： 1.事实性。 2.等级性。 3.可压缩性。 4.可扩散性。 5.可传输性。 6.共享性。 7.增值性和再生性。 8.转换性。 1.3计算机的主要特点是什么？ 计算机最主要的特点是： 1.高速自动的操作功能。 2.具有记忆的能力。 3.可以进行各种逻辑判断。 4.精确高速的计算能力。 1.5完整的计算机系统应该包括哪几部分？ 目前最完整的计算机系统学说认为由五部分组成： 1.人员 2.数据 3.设备 4.程序 5.规程 1.6什么是计算机硬件？什么是计算机软件？ 硬件：泛指实际存在的物理设备，包括计算机本身及其外围设备。 微型计算机的硬件系统：主机、外存储器、输入设备、输出设备、微机的系统总线。 软件：是指计算机程序、方法、规则的文档以及在计算机上运行它时所必须的数据。 计算机软件一般分为系统软件和应用软件。 1.8 软件技术发展的几个阶段各有什么特点？它与硬件的关系如何？ 第一阶段：高级语言阶段 特点：这一时期，编译技术代表了整个软件技术，软件工作者追求的主要目的是设计和实现在控制结构和数据结构方面表现能力强的高级语言。但在这一时期内，编译系统主要是靠手工编制，自动化程度很低。 硬件关系：此时期计算机的硬件要求仅能用机器指令来编制可运行的程序。 1.有一函数Function F(ByVal a As Integer, ByVal b As Integer) As Integer,()在调用时将发生错误。 A.Call F(1, 2) B.Y = F(F(2, 3), 4) C.Z = F(2.3, 5) D.X = F(3) 【参考答案】: D 2.表达式1.5 + 3 \ 2 > 2 Or 7 Mod 3 < 4 的运算结果是()。 A.True B.0 C.1 D.False 【参考答案】: A 3.结构化程序设计所规定的三种基本控制结构是(?)。 A.输入、处理、输出 B.树形、网形、环形 C.顺序、选择、循环 D. 主程序、子程序、函数 【参考答案】: C 4.int(198.555*100+0.5)/100的值()。 A.是198 B.是199.6 C.是198.56 D.是200 【参考答案】: C 5.加载窗体时触发的事件是( )。 A.Click B.Load C.Gotfocus D.DoubleClick 【参考答案】: B 6.下面叙述不正确的是()。 A.一个控件只能有一个事件处理过程 B.用户与应用交互可以触发事 件 C.Visual https://www.wendangku.net/doc/7017739182.html, 是集成了事件驱动的编程模型 D.即使用户与应用程序不进行交互，有些事件也可能发生 【参考答案】: A 7.设X=lO,y=7,表达式x\6+y*3的值为()。 A.24 B.22 C.25 D.0 【参考答案】: B 8.鼠标的移动触发()事件。 A.Click B.Mousedown C.MouseUp D.MouseMove 【参考答案】: D 9.在https://www.wendangku.net/doc/7017739182.html,窗体第一次显示之前,下列()窗体事件发生。 A.Activated B.GotFocus C.Click D.Load 【参考答案】: D 10.文本框的( )属性用于设置或返回文本框中的文本内容。 A.Text B.(名称) C.Caption https://www.wendangku.net/doc/7017739182.html, 【参考答案】: A 11.已知A$="12345678",则表达式Val(Mid(A, 1, 4) + Mid(A, 4, 2))的值为 ()。 A.123456 B.123445 C.8 D.6 【参考答案】: B 12.DrawArc方法绘制的图形是()。 A.圆 B.椭圆 C.弧 D.扇形 【参考答案】: C软件技术基础习题答案
软件技术基础试题及答案
软件技术基础模拟试题及参考答案
管理学试题及答案(1)
计算机软件技术基础(第三版)沈被娜 课后习题答案较全
管理学试题与答案
14秋天大《计算机软件技术基础(1)》在线作业一答案
软件技术基础模拟试题
管理学题目及答案
管理学试题与答案
软件技术基础试题(含答案)
VB软件技术基础模拟题及参考答案
管理学试题及答案
软件技术基础试题及答案
管理学试题和答案
最新计算机软件技术基础(第三版)习题答案
2020年春季考试《计算机软件技术基础(1)》在线考核试题_13.doc
- 计算机软件技术基础(第三版)习题答案1
- 西电软件技术基础上机大作业答案
- 计算机软件技术基础复习题和答案
- 计算机软件技术基础(第三版)沈被娜 课后习题答案较全
- 软件技术基础_课后答案_周大为_西电
- 计算机软件技术基础 习题一解答
- 最新计算机软件技术基础(第三版)习题答案
- 《软件技术基础》习题解答
- 计算机软件技术基础习题一解答
- 大学计算机软件技术基础考试技术复习题
- 14秋天大《计算机软件技术基础(1)》在线作业一答案
- 答案[计算机软件技术基础]
- 软件技术基础 第三版 课后习题答案
- 计算机软件技术基础沈被娜 课后习题答案较全
- 软件技术基础习题答案
- 计算机软件技术基础课后答案
- 《计算机软件技术基础(第三版)》的课后答案
- 计算机软件技术基础(第三版)习题答案1
- 计算机软件技术基础沈被娜课后习题答案较全
- 计算机软件技术基础(第三版)沈被娜 课后习题答案较全