第三次数据结构作业20101029
第三次作业
第三章栈和队列
一、选择题
1. 若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j个输出元素是（）。
A. i-j-1
B. i-j
C. j-i+1
D. 不确定的
2. 若栈采用顺序存储方式存储，现两栈共享空间V[1..m]，top[i]代表第i个栈( i =1,2)
栈顶，栈1的底在v[1]，栈2的底在V[m]，则栈满的条件是（）。
A. |top[2]-top[1]|=0
B. top[1]+1=top[2]
C. top[1]+top[2]=m
D.
top[1]=top[2]
3. 栈在（）中应用。
A. 递归调用
B. 子程序调用
C. 表达式求值
D. A，Ｂ，Ｃ
4. 表达式3* 2^(4+2*2-6*3)-5求值过程中当扫描到6时，对象栈和算符栈为（），其中
^为乘幂。
A. 3,2,4,1,1；(*^(+*-
B. 3,2,8；(*^-
C. 3,2,4,2,2；(*^(-
D. 3,2,8；
(*^(-
5. 用链接方式存储的队列，在进行删除运算时（）。
A. 仅修改头指针
B. 仅修改尾指针
C. 头、尾指针都要修改
D. 头、尾指针
可能都要修改
6. 假设以数组A[m]存放循环队列的元素,其头尾指针分别为front和rear，则当前队列中
的元素个数为（）。
A．(rear-front+m)%m B．rear-front+1 C．(front-rear+m)%m D．(rear-front)%m
7. 栈和队列的共同点是（）。
A. 都是先进先出
B. 都是先进后出
C. 只允许在端点处插入和删除元素
D. 没有共同点
8. 设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个元
素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3,e6,e5,e1则栈S的容量至少应
该是( )。
A． 6 B. 4 C. 3 D. 2
二、应用题
24. 有字符串次序为3*-y-a/y^2,利用栈，给出将次序改为3y-*ay2^/-的操作步骤。（可用X代表扫描该字符串过程中顺序取一个字符进栈的操作，用S代表从栈中取出一个字符加入到新字符串尾的出栈操作。例如，ABC变为BCA的操作步骤为XXSXSS）
【东北大学2001 一、4 ( 4分)】
24、XSXXXSSSXXSXXSXXSSSS
2. 有两个栈s1和s2共享存储空间c[1,m],其中一个栈底设在c[1]处，另一个栈底设在c[m0] 处，分别编写s1和s2的进栈push( i,x)、退栈pop(i)和设置栈空setnull(i)的函数，其中i=1,2。注意：仅当整个空间c[1,m0]占满时才产生上溢。
解：该共享栈的结构如图2.3所示，两栈的最多元素个数为m0, top1是栈1的栈指针，
top2 是栈2的栈指针，当top2=top1+1时出现上溢出，当top1=0时栈1出现下溢出，当top2=m0+1时栈2出现下溢出。根据上述原理得到如下
函数：
top1 top2
c的元素序号1 2 …….. n …….. m0-1 m0
a1 a2 …… a n ………. bm ……… b2 b1
栈1底栈1顶栈2顶栈2底
图2.3 共享栈
/*top1,top2 和m0均为已赋初值的int型全局变量*/
void push(x,i)
int x,I
{
if (top1==top2-1) printf("上溢出！\n");
else
if(i==1)/*对第一个栈进行入栈操作*/
{
top1++; c[top1]=x;
else /*对第二个栈进行入栈操作*/
{
top2--; c[top2]=x;
}
}
/*函数pop*/
void pop(i)
int i ;
{
if (i ==1 )/*对第一个栈进行出栈操作*/
if(top1==0)printf("栈1下溢出！\n");
else
{
pop=c[top1]; top1--;
}
else /*对第二个栈进行出栈操作*/
if (top2==m0+1) printf("栈2下溢出！\n");
else
{
pop=c[top2];top2++;
}
}
/*函数setnull*/
setnull(i)
int i ;
{
if(i ==1 )top1=0;
else top2=m0+1;
}
#define m0 100 /*m0为算术表达式中最多字符个数*/ correct(exp,tag)
charexp[m0];int tag;
{
charst[m0]; int top=0,i=1;
tag=1;
while(i<=m0&&tag)
{ if(exp[i]==‘(’||exp[i]==‘[’||exp[i]==‘{’) /*此时入栈*/ {top++;st[top]=exp[i];}
if(exp[i]==‘)’)
if(st[top]==‘(’) top- -; else tag=0;
if(exp[i]==‘]’)
if(st[top]==‘[’) top- -; else tag=0;
if(exp[i]==‘}’)
if(st[top]==‘{’) top- -; else tag=0;
i++;
}
if(top>0)tag=0; /*若栈不空，则不配对*/
}
请利用两个栈S1和S2来模拟一个队列。
已知栈的三个运算定义如下：
PUSH(ST,x):元素x入ST栈；
POP(ST,x)：ST栈顶元素出栈，赋给变量x；
Sempty(ST)：判ST栈是否为空。
那么如何利用栈的运算来实现该队列的三个运算：
enqueue:插入一个元素入队列；
dequeue:删除一个元素出队列；
queue_empty：判队列为空。（请写明算法的思想及必要的注释）
[题目分析]栈的特点是后进先出，队列的特点是先进先出。所以，用两个栈s1和s2模拟一个队列时，s1作输入栈，逐个元素压栈，以此模拟队列元素的入队。当需要出队时，将栈s1退栈并逐个压入栈s2中，s1中最先入栈的元素，在s2中处于栈顶。s2退栈，相当于队列的出队，实现了先进先出。显然，只有栈s2 为空且s1也为空，才算是队列空。
[算法讨论]算法中假定栈s1和栈s2容量相同。出队从栈s2出，当s2为空时，若s1不空，则将s1倒入s2再出栈。入队在s1，当s1满后，若s2空，则将s1倒入s2，之后再入队。因此队列的容量为两栈容量之和。元素从栈 s1倒入s2，必须在s2空的情况下才能进行，即在要求出队操作时，若s2空，则不论s1元素多少（只要不空），就要全部倒入s2中。
下面两个方法的思路是一致的，只是一个是基于进栈与队列相同一个基于出栈与队列相同。
法（1）
intenqueue(stack s1,elemtp x)
//s1是容量为n的栈，栈中元素类型是elemtp。本算法将x入栈，若入栈成功返回1，否则返回0。
{if(top1==n && !Sempty(s2)) //top1是栈s1的栈顶指针，是全局变量。
{printf(“栈满”);return(0);} //s1满s2非空,这时s1不能再入栈。
if(top1==n &&Sempty(s2)) //若s2为空，先将s1退栈,元素再压栈到s2。
{while(!Sempty(s1)) {POP(s1,x);PUSH(s2,x);}
PUSH(s1,x); return(1); //x入栈，实现了队列元素的入队。
}
voiddequeue(stack s2,s1)
//s2是输出栈，本算法将s2栈顶元素退栈，实现队列元素的出队。
{if(!Sempty(s2)) //栈s2不空，则直接出队。
{POP(s2,x); printf(“出队元素为”,x); }
else //处理s2空栈。
if(Sempty(s1)) {printf(“队列空”);exit(0);}//若输入栈也为空，则判定队空。
else //先将栈s1倒入s2中，再作出队操作。
{while(!Sempty(s1)) {POP(s1,x);PUSH(s2,x);}
POP(s2,x); //s2退栈相当队列出队。
printf(“出队元素”，x);
}
}//结束算法dequue。
intqueue_empty()
//本算法判用栈s1和s2模拟的队列是否为空。
{if(Sempty(s1)&&Sempty(s2)) return(1);//队列空。
else return(0); //队列不空。
}
法（2）
ElementTypeDeQueue(S1)
{
if(Empty(S1)
{
printf("Error!");
exit(0);
}
else
return Pop(S1);
}
voidEnQueue(S1,ElementType x)
{
ElementType t;
while(!Empty(S1))
{
t=Pop(S1);
Push(S2,t;
}
Push(S1,x);
while(!Empty(S2))
{
t=Pop(S2);
Push(S1,t);
}
]
已知McCathy函数定义如下：
M（x)=x-10 当x> 100
=M(M(x+11)) 当x <=100
试写出求解该递归函数的非递规算法
int m(int x)
{
int y;
if(x>100) return(x-10);
else
{
y=m(x+11);
return(m(y));
}
}
递归
递归
intgcd (intm,int n) { if (m if(n==0) return m;; m=m%n; returngcd(n,m);} 非递归： intgcd(intm,intn) { int r; if(m {r=m;m=n;n=r;} while(r=m%n) {m=n;n=r;} returnn; } 习题1 一、单项选择题 A1.数据结构是指（）。 A.数据元素的组织形式 B.数据类型 C.数据存储结构 D.数据定义 C2.数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（）。 A.存储结构 B.逻辑结构 C.链式存储结构 D.顺序存储结构 D3.树形结构是数据元素之间存在一种（）。 A.一对一关系 B.多对多关系 C.多对一关系 D.一对多关系 B4.设语句x++的时间是单位时间，则以下语句的时间复杂度为（）。 for(i=1; i<=n; i++) for(j=i; j<=n; j++) x++; A.O(1) B.O(2n) C.O(n) D.O(3n) CA5.算法分析的目的是（1），算法分析的两个主要方面是（2）。 （1） A.找出数据结构的合理性 B.研究算法中的输入和输出关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 （2） A.空间复杂度和时间复杂度 B.正确性和简明性 C.可读性和文档性 D.数据复杂性和程序复杂性 6.计算机算法指的是（1），它具备输入，输出和（2）等五个特性。 （1） A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法 （2） A.可行性，可移植性和可扩充性 B.可行性，确定性和有穷性 C.确定性，有穷性和稳定性 D.易读性，稳定性和安全性 7.数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储比顺序存储要（）。 A.低 B.高 C.相同 D.不好说 8.数据结构作为一门独立的课程出现是在（）年。 A.1946 B.1953 C.1964 D.1968 9.数据结构只是研究数据的逻辑结构和物理结构，这种观点（）。 A.正确 B.错误 C.前半句对，后半句错 D.前半句错，后半句对 1. 填空题 (1) 顺序栈s的数据存储在数组element中，则栈满的条件是____________,栈空的条件是。 (2) 顺序栈ｓ进行出栈操作后，要执行的语句是top____。s进行进栈操作前，要执行的语句是top______运算。 (3) 元素进入队列的一端是____________；队列出队的一端是____________。 (4)顺序队列q满的条件是，顺序队列q空的条件 是。 (5) 空串的长度等于，非空串的长度等于。 2. 选择题 (1) 串是一种特殊的线性表，其特征体现在_____。 A. 可以顺序存储 B. 数据元素是一个字符 C. 可以链接存储 D. 数据元素可以是多个字符 (2) 栈是限定在__________处进行插入或删除操作的线性表。 A. 端点 B. 栈底 C. 栈顶 D. 中间 (3) 在栈顶一端可进行的全部操作是___________。 A. 插入 B.删除 C. 插入和删除 D. 进栈 (4) 4个元素按A、B、C、D顺序连续进S栈，进行x=pop()运算后，x的值是___________, 栈顶元素的值是. A. A B. B C. C D. D (5) 栈的特点是__________。 A. 先进先出 B. 后进先出 C. 后进后出 D. 不进不出 (6) 顺序栈存储空间的实现使用___________。 A. 链表 B. 数组 C.循环链表 D. 变量 (7) 一个顺序栈一旦说明，其占用空间的大小___________。 A. 已固定 B. 可以改变 C. 不能固定 D. 动态变化 (8) 栈与一般线性表的区别主要在___________方面。 A. 元素个数 B. 元素类型 C. 逻辑结构 D. 插入、删除元素的位置 (9) 栈s经过下列运算后s.get()的值是___________, s.isEmpty( )的值是___________。 s.push(a);s.push(b);s.pop(); A. a B. b C. 1 D. 2 第1章绪论 习题 1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。 2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。 3．简述逻辑结构的四种基本关系并画出它们的关系图。 4．存储结构由哪两种基本的存储方法实现 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．栈 6．试分析下面各程序段的时间复杂度。 （1）x=90; y=100; while(y>0) if(x>100) {x=x-10;y--;} else x++; （2）for (i=0; i 0980 输出利用先序遍历创建的二叉树的层次遍历序列（中）#include while(fornt != rear) { fornt = (fornt+1)%100; p = q[fornt]; cout< 东北农业大学网络教育学院 数据结构作业题（一） 一、选择题（每题2分，共20分） 1．在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为（）。 A、O(n) B、O (n/2) C、O (1) D、O (n2) 2．带头结点的单链表first为空的判定条件是（）。 A、first == NULL; B、first->link == NULL; C、first->link == first; D、first != NULL; 3．在一棵树中，（）没有前驱结点。 A、分支结点 B、叶结点 C、树根结点 D、空结点 4．在有向图中每个顶点的度等于该顶点的（）。 A、入度 B、出度 C、入度与出度之和 D、入度与出度之差 5．对于长度为9的有序顺序表，若采用折半搜索，在等概率情况下搜索成功的平均搜索长度为（）的值除以9。 A、20 B、18 C、25 D、22 6．下列程序段的时间复杂度为（）。 s=0； for(i=1；i 计算机文化基础 第三次在线作业 单选题 (共40道题) 展开 收起 1.（ 2.5分）Internet实现了分布在世界各地的各类网络的互联，其最基础和核心的协议是（）。 ? A、HTTP ? B、FTP ? C、HTML ? D、TCP/IP 我的答案：D 此题得分：2.5分 2.（2.5分）在下述计算机网络的拓扑结构中，可靠性好，适用于广域网中的是（）。 ? A、网状结构 ? B、星型结构 ? C、总线结构 ? D、树形结构 我的答案：A 此题得分：2.5分 3.（2.5分）对于个人用户而言，在一般情况下，使用（）连入Internet是一个较为恰当的选择。 ? A、专线连接 ? B、微机局域网连接 ? C、微波连接 ? D、电话拨号连接 我的答案：D 此题得分：2.5分 4.（2.5分）以下不是常用的传输媒体的是（）。 ? A、双绞线 ? B、同轴电缆 ? C、光纤 ? D、电线 我的答案：D 此题得分：2.5分 5.（2.5分）支持局域网与广域网互连的设备称为（）。 ? A、交换机 ? B、路由器 ? C、转发器 ? D、网桥 我的答案：B 此题得分：2.5分 6.（2.5分）下列关于IP地址的叙述中正确的是（）。 ? A、IP地址是4个由点号分开的十进制数组成，因此必须转换为二进制数，才能被计算机识别。 ? B、IP地址的分为A、B、C、D、E类，一般从IP地址中第一个数字的取值范围，就能辨别出IP地址的种类。 ? C、IP地址是唯一的，可以任意使用。 ? D、通过拨号上网使用固定的IP地址，通过局域网上网则使用动态分配的IP地址 我的答案：B 此题得分：2.5分 7.（2.5分）以下是A类IP地址的是（）。 ? A、126.256.2.6 ? B、202.205.2.1 ? C、102.24.5.21 ? D、224.200.11.31 我的答案：C 此题得分：2.5分 8.（2.5分）DNS的作用是（）。 ? A、将数字信号转变成模拟信号 ? B、将十进制转换成二进制 ? C、将文本文件转换成二进制文件 ? D、将域名转换成IP地址 我的答案：D 此题得分：2.5分 填空题（10 * 1’ = 10’） 一、概念题 .当对一个线性表经常进行的是插入和删除操作时，采用链式存储结构为宜。 .当对一个线性表经常进行的是存取操作，而很少进行插入和删除操作时，最好采用顺序存储结构。 .带头结点的单链表L中只有一个元素结点的条件是L->Next->Next==Null。 .循环队列的引入，目的是为了克服假溢出。 .长度为0的字符串称为空串。 .组成串的数据元素只能是字符。 .设T和P是两个给定的串，在T中寻找等于P的子串的过程称为模式匹配，又称P为模式。 .为了实现图的广度优先搜索，除一个标志数组标志已访问的图的结点外，还需要队列存放被访问的结点实现遍历。 .广义表的深度是广义表中括号的重数 .有向图G可拓扑排序的判别条件是有无回路。 .若要求一个稠密图的最小生成树，最好用Prim算法求解。 . 直接定址法法构造的哈希函数肯定不会发生冲突。 .排序算法所花费的时间，通常用在数据的比较和交换两大操作。 .通常从正确性﹑可读性﹑健壮性﹑时空效率等几个方面评价算法的（包括程序）的质量。 .对于给定的n元素，可以构造出的逻辑结构有集合关系﹑线性关系树形关系﹑图状关系四种。 .存储结构主要有顺序存储﹑链式存储﹑索引存储﹑散列存储四种。 .抽象数据类型的定义仅取决于它的一组逻辑特性，而与存储结构无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部使用。 .一个算法具有五大特性：有穷性﹑确定性﹑可行性，有零个或多个输入﹑有一个或多个输入。 .在双向链表结构中，若要求在p指针所指的结点之前插入指针为s所指的结点，则需执行下列语句：s->prior= p->prior; s->next= p; p->prior- next= s; p->prior= s;。 .在单链表中设置头结点的作用是不管单链表是否为空表，头结点的指针均不空，并使得对单链表的操作（如插入和删除）在各种情况下统一。 .队列是限制在表的一端进行插入和在另一端进行删除的线性表，其运算遵循先进先出原则。 .栈是限定尽在表位进行插入或删除操作的线性表。 .在链式队列中，判定只有一个结点的条件是(Q->rear==Q->front)&&(Q->rear!=NULL)。 .已知链队列的头尾指针分别是f和r，则将x入队的操作序列是node *p=(node *)malloc(node); p->next=x; p->next=NULL; if(r) {r->next=p; r=p;} else {r=p; f=p;}。 .循环队列的满与空的条件是(rear+1)%MAXSIZE==fornt和(front=-1&&rear+1==MAXSIZE)。 .串是一种特殊的线性表，其特殊性表现在数据元素都是由字符组成。 .字符串存储密度是串值所占存储位和实际分配位的比值，在字符串的链式存储结构中其结点大小是可变的。 .所谓稀疏矩阵指的是矩阵中非零元素远远小于元素总数，则称该矩阵为矩阵中非零元素远远小于元素总数，则称该矩阵为稀疏矩阵。 .一维数组的逻辑结构是线性结构，存储结构是顺序存储结构；对二维或多维数组，分别按行优先和列优先两种不同的存储方式。 .在有向图的邻接矩阵表示中，计算第i个顶点入度的方法是求邻接矩阵中第i列非0元素的个数。 网中，结点表示活动，边表示活动之间的优先关系，AOE网中，结点表示事件，边表示活动。 .按排序过程中依据不同原则对内部排序方法进行分类，主要有选择排序﹑交换排序﹑插入排序归并排序等4类。 .在堆排序、快速排序和归并排序中若只从排序结果的稳定性考虑，则应选择归并排序方法；若只从平均情况下排序最快考虑，则应选择快速排序方法；若只从最坏情况下排序最快且要节省类存考虑，则应选择堆排序方法。 .直接插入排序用监视哨的作用是存当前要的插入记录，可又省去查找插入位置时对是否出界的判断。 .设表中元素的初始状态是按键值递增的，则直接插入排序最省时间，快速排序最费时间。 .下列程序判断字符串s是否对称，对称则返回1，否则返回0；如?(“abba”)返回1，?（”abab”）返回0. Int f (char*s) { Int i=0,j=0; 求串长*/ 《数据结构》填空作业题答案 第 1 章绪论（已校对无误） 1．数据结构包括数据的逻辑结构、数据的存储结构和数据的运算三方面的内容。 2．程序包括两个内容：数据结构和算法。 3.数据结构的形式定义为：数据结构是一个二元组：Data Structure =（ D， S）。 4.数据的逻辑结构在计算机存储器内的表示，称为数据的存储结构。 5.数据的逻辑结构可以分类为线性结构和非线性结构两大类。 6.在图状结构中，每个结点的前驱结点数和后继结点数可以有多个。 7.在树形结构中，数据元素之间存在一对多的关系。 8.数据的物理结构，指数据元素在计算机中的标识（映象），也即存储结构。 9.数据的逻辑结构包括线性结构、树形结构和图形结构 3 种类型，树型结构和有向 图结构合称为非线性结构。 10. 顺序存储结构是把逻辑上相邻的结点存储在物理上连续的存储单元里，结点之间的逻辑 关系由存储单元位置的邻接关系来体现。 11. 链式存储结构是把逻辑上相邻的结点存储在物理上任意的存储单元里，节点之间的逻辑 关系由附加的指针域来体现。 12.数据的存储结构可用 4 种基本的存储方法表示，它们分别是顺序存储、链式存储、索引存储和散列存储。 13. 线性结构反映结点间的逻辑关系是一对一的，非线性结构反映结点间的逻辑关系是一对多或多对多。 14.数据结构在物理上可分为顺序存储结构和链式存储结构。 15. 我们把每种数据结构均视为抽象类型，它不但定义了数据的表示方式，还给出了处理数 据的实现方法。 16.数据元素可由若干个数据项组成。 17.算法分析的两个主要方面是时间复杂度和空间复杂度。 18.一个算法的时间复杂度是用该算法所消耗的时间的多少来度量的，一个算法的空间复杂 度是用该算法在运行过程中所占用的存储空间的大小来度量的。 19.算法具有如下特点：有穷性、确定性、可行性、输入、输出。 20. 对于某一类特定的问题，算法给出了解决问题的一系列操作，每一操作都有它的确切 的定义，并在有穷时间内计算出结果。 21. 下面程序段的时间复杂度为㏒ 3n 。 1 ?2.1 比较程序的顺序执行和并发执行。 答： 答： 1）进程是一个动态的概念，而程序则是一个静态的概念。程序是指令的有序集合，没有任何执行含义，而进程则强调执行过程，它动态地被创建，并被调度执行后消亡。 2）进程具有并行特征，而程序没有。进程具有并行特征的两个方面，即独立性和异步性。也就是说，在不考虑资源共享的情况下，各进程的执行是独立的，它们之间不存在逻辑上的制约关系，各进程的是异步的。由于程序不反映执行过程，所以不具有并行特征。 3）进程是系统中独立存在的实体，是竞争资源的基本单位。进程对应特殊的描述结构 并有申请、使用、释放资源的资格。由于系统中存在多个进程，系统资源的有限性必然导致多个进程对资源的共享和竞争，从而使进程的并行性受到系统的制约。 4）进程的存在必然需要程序的存在，但进程和程序不是一一对应的。由于进程是程序 的执行过程，所以程序是进程的一个组成部分。处于静止状态的程序并不对应于任何进程。当程序被处理机执行时，它一定属于某一个或者多个进程。属于进程的程序可以是一个，也可以是多个。不同的进程可以包含同一个程序，只要该程序所对应的数据集不同。 ?2.3 试对进程的状态及状态转换进行总结，注意状态转换的物理含义及转化条件。 答：处于就绪状态的进程，在调度程序为之分配了处理机之后，该进程便可执行，相应地，它就由就绪状态转变为运行状态。正在执行的进程也称为当前进程，如果分配给它的时间 片已完而被暂停执行时，该进程便由执行状态又回复到就绪状态；如果因发生某事件而使 进程的执行受阻，使之无法继续执行，该进程将由执行状态转变为阻塞状态。引入挂起状 态后，又增加了从挂起状态到非挂起状态之间的转换，当进程处于未被挂起的就绪状态时，用挂起原语Suspend将该进程挂起后，该进程便转变成为静止就绪状态，此时进程不再被 调度执行。当进程处于未被挂起的阻塞状态时，用Suspend原语将它挂起后，进程便转变 为静止阻塞状态，处于该状态的进程在其所期待的事件出现后，将从静止阻塞状态变成静 止就绪。处于活动就绪状态的进程，若用激活原语Active激活后，该进程将转变为挂起就 绪状态。处于活动阻塞状态的进程，若用激活原语Active激活后，将转变为阻塞挂起状态。 ?2.4 试举例说明引起进程创建、撤消、阻塞或被唤醒的主要事件分别有哪些？ 答：引起进程创建，如用户登录；作业调度；提供服务；应用请求。 进程撤销，当一个进程到达了自然结束点，或时出现了无法克服的错误，或是被操作 系统所中介，或是被其他有终止权的进程所终结，都会引起进程撤销。 进程阻塞，请求系统服务,不能立即满足;启动某种操作,且必须在该操作完成之后才能 继续执行;新数据尚未到达,相互合作进程的一方需首先获得另一进程数据才能继续;无新工 作可做,特定功能系统进程当完成任务且暂无任务。 进程被唤醒，系统服务满足;操作完成;数据到达;新任务出现。 ?2.5 试根据你自己的理解，采用类C语言设计和描述操作系统关于进程控制块的数据结构、组织方式及管理机制。在此基础上，给出进程的创建、终止、阻塞、唤醒、挂起与激活等函数原型及函数代码。注意，对于过于复杂的功能或你无法解决的细节可采用指定功能的函数模块如处理机调度scheduler()来替代。 答：进程控制块的数据结构： Struct task_struct { long state; /*任务的运行状态（-1 不可运行，0 可运行(就绪)，>0 已停止）*/ long counter;/*运行时间片计数器(递减)*/ long priority;/*优先级*/ long signal;/*信号*/ struct sigaction sigaction[32];/*信号执行属性结构，对应信号将要执行的操作和标志信息*/ long blocked; /* bitmap of masked signals */ /* various fields */ int exit_code;/*任务执行停止的退出码*/ unsigned long start_code,end_code,end_data,brk,start_stack; /*代码段地址代码长度（字节数） 代码长度 + 数据长度（字节数）总长度堆栈段地址*/ long pid,father,pgrp,session,leader;/*进程标识号(进程号) 父进程号父进程组号会话号会话首领*/ unsigned short uid,euid,suid;/*用户标识号（用户id）有效用户id 保存的用户id*/ unsigned short gid,egid,sgid; /*组标识号（组id）有效组id 保存的组id*/ 第 1 章绪论 课后习题讲解 1、填空 ⑴( )就是数据的基本单位,在计算机程序中通常作为一个整体进行考虑与处理。 【解答】数据元素 ⑵( )就是数据的最小单位,( )就是讨论数据结构时涉及的最小数据单位。 【解答】数据项,数据元素 【分析】数据结构指的就是数据元素以及数据元素之间的关系。 ⑶从逻辑关系上讲,数据结构主要分为( )、( )、( )与( )。 【解答】集合,线性结构,树结构,图结构 ⑷数据的存储结构主要有( )与( )两种基本方法,不论哪种存储结构,都要存储两方面的内容:( )与( )。 【解答】顺序存储结构,链接存储结构,数据元素,数据元素之间的关系 ⑸算法具有五个特性,分别就是( )、( )、( )、( )、( )。 【解答】有零个或多个输入,有一个或多个输出,有穷性,确定性,可行性 ⑹算法的描述方法通常有( )、( )、( )与( )四种,其中,( )被称为算法语言。 【解答】自然语言,程序设计语言,流程图,伪代码,伪代码 ⑺在一般情况下,一个算法的时间复杂度就是( )的函数。 【解答】问题规模 ⑻设待处理问题的规模为n,若一个算法的时间复杂度为一个常数,则表示成数量级的形式为( ),若为 n*log25n,则表示成数量级的形式为( )。 【解答】Ο(1),Ο(nlog2n) 【分析】用大O记号表示算法的时间复杂度,需要将低次幂去掉,将最高次幂的系数去掉。 2、选择题 ⑴顺序存储结构中数据元素之间的逻辑关系就是由( )表示的,链接存储结构中的数据元素之间的逻辑关系就是由( )表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针 【解答】C,D 【分析】顺序存储结构就就是用一维数组存储数据结构中的数据元素,其逻辑关系由存储位置(即元素在数组中的下标)表示;链接存储结构中一个数据元素对应链表中的一个结点,元素之间的逻辑关系由结点中的指针表示。 数据结构与算法分析课程设计报告 课题名称： A Text Editor Imlementation 提交文档学生姓名：苟丁 提交文档学生学号： 0843042229 同组成员名单：无 指导教师姓名：孙界平 指导教师评阅成绩： 指导教师评阅意见： . . 提交报告时间：2010 年 5 月 7 日 1. 实验题目:带括号的算术表达式求值 2. 实验的目的和要求: 1.采用C++的ASCII码文件和串函数实现; 2.熟练掌握串运算的应用; 3.熟练掌握计算机系统的基本操作方法,了解如何编辑、编译、链接和运行一 个C++程序; 4.上机调试程序,掌握查错、排错使程序能正确运行 3.实验的环境: 1、硬件环境：联想笔记本电脑，Intel(R) Pentium(R) Dual T3400 ，2GB内存 2、软件环境：Windows XP 下的Microsoft Visual Studio 2008 4.算法描述: ●具体操作与函数描述 （1）编辑一个文本文件，命名为text.txt. （2）函数run()提供给用户选择符的输入：w,r,I,d,f,c,q,h,n,p,b,e,g,v. 用户可以选择H选择符寻求帮助，得知操作符分别代表的动作。 （3） R代表函数Read()将文本读入缓冲区，缓冲区以前的任何内容都将将消失。 （4） W代表函数Write()将缓冲区的内容写入文本文件。 （5） I代表函数Insert（）插入新行，用户可以在适当的提示下键入新行并提供新行。 （6） D代表delete()行数所执行的删除操作，可以删除当前行，并进入下一行。 （7） F代表函数findChar(),用于查找目标行。 （8） C代表函数changLine(),将用户请求的字符串修改成用户请求的替换文本，可选择的是仅在当前行中有效。 （9） Q代表函数quit(),用户执行此命令可以退出编辑。 （10）N代表函数next(),用户可以从当前行移到下一行。 （11）P代表函数pre(),用户可以从当前行移到下一行。 （12）E代表end(),可以移到最后一行。 （13）G代表go(),用户可以指定到选择的行。 （14）V查看缓冲区的全部内 ●测试程序说明： 习题1 一、单项选择题 1.数据结构是指（）。 A.数据元素的组织形式 B.数据类型 C.数据存储结构 D.数据定义 2.数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（）。 A.存储结构 B.逻辑结构 C.链式存储结构 D.顺序存储结构 3.树形结构是数据元素之间存在一种（）。 A.一对一关系 B.多对多关系 C.多对一关系 D.一对多关系 4.设语句x++的时间是单位时间，则以下语句的时间复杂度为（）。 for(i=1; i<=n; i++) for(j=i; j<=n; j++) x++; A.O(1) B.O(2n) C.O(n) D.O(3n) 5.算法分析的目的是（1），算法分析的两个主要方面是（2）。 （1） A.找出数据结构的合理性 B.研究算法中的输入和输出关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 （2） A.空间复杂度和时间复杂度 B.正确性和简明性 C.可读性和文档性 D.数据复杂性和程序复杂性 6.计算机算法指的是（1），它具备输入，输出和（2）等五个特性。 （1） A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法 （2） A.可行性，可移植性和可扩充性 B.可行性，确定性和有穷性 C.确定性，有穷性和稳定性 D.易读性，稳定性和安全性 7.数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储比顺序存储要（）。 A.低 B.高 C.相同 D.不好说 8.数据结构作为一门独立的课程出现是在（）年。 A.1946 B.1953 C.1964 D.1968 9.数据结构只是研究数据的逻辑结构和物理结构，这种观点（）。 A.正确 B.错误 C.前半句对，后半句错 D.前半句错，后半句对 2011年12月考试数据结构第二次作业 一、单项选择题（本大题共100分，共 25 小题，每小题 4 分） 1. 树型结构是数据元素之间存在一种：( ) A. 一对多关系 B. 多对多关系 C. 多对一关系 D. 一对一关系 2. 以下的排序算法属于稳定排序算法的是（） A. 基数排序 B. 快速排序 C. 希尔排序 D. 堆排序 3. 适于对动态查找表进行高效率查找的组织结构是（） A. 有序表 B. 分块有序表 C. 二叉排序树 D. 线性链表 4. 用某种排序方法对关键字序列（25，84，21，47，15，27，68，35，20）进行排序时，序列的变化情况如下： 20，15，21，25，47，27，68，35，84 15，20，21，25，35，27，47，68，84 15，20，21，25，27，35，47，68，84 则所采用的排序方法是（） A. 选择排序 B. 希尔排序 C. 归并排序 D. 快速排序 5. 在一棵二叉树中，度为2的结点有2个，那么，该树有（）个叶结点。 A. 3 B. 4 C. 5 D. 6 6. 图中有n个顶点，e条边，如果用邻接矩阵表示图，则深度优先搜索遍历图的时间复杂性为（）。 A. O(n) B. O(e) C. O(n2) D. O(n+e) 7. 分块查找中块内的查找采用的查找方法是（） A. 顺序查找 B. 折半查找 C. 顺序查找、折半查找都可以 D. 顺序查找、折半查找都不可以 8. 假设一个有n个顶点和e条弧的有向图用邻接表表示,则删除与某个顶点vi 相关的所有弧的时间复杂度是( ) A. O(n) B. O(e) C. O(n+e) D. O(n*e) 9. 在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加（）。 A. 2 B. 1 C. 0 D. –1 10. 若n个顶点的无向图采用邻接矩阵存储方法，该邻接矩阵为一个什么矩阵？（） A. 对称矩阵 B. 一般矩阵 C. 稀疏矩阵 D. 对角矩阵 11. 平衡二叉树的平衡因子的取值不可能是（） A. 1 B. -1 C. 0 D. 2 12. 在二叉树的中序遍历递归算法中，顺着搜索路径，在第( )次经过结点时作访问操作。 A. 1 B. 2 C. 3 D. 4 13. VSAM文件中的记录均存放在（）。 A. 数据集 B. 索引集 C. 顺序集 D. 以上都不是 14. 关键路径是AOE网络中（） A. 从源点到汇点的最长路径 B. 最短的回路 C. 从源点到汇点的最短路径 D. 最长的回路 15. 对数据元素序列（49，72，68，13，38，50，97，27）进行排序，如果采用起泡排序方法，则第二趟排序结果是（） A. 49，68，13，38，50，72，27，97 B. 13，38，49，50，27，68，72，97 C. 49，13，38，50，68，27，72，97 D. 13，38，49，27，50，68，72，97 16. 如果只想得到1024个元素组成的序列中的前6个最小元素，那么用（）方法最快。 A. 起泡排序 1．数据的最小单位是（ A ）。 (A) 数据项(B) 数据类型(C) 数据元素(D) 数据变量 2．下面关于线性表的叙述错误的是（D）。 (A) 线性表采用顺序存储必须占用一片连续的存储空间 (B) 线性表采用链式存储不必占用一片连续的存储空间 (C) 线性表采用链式存储便于插入和删除操作的实现 (D) 线性表采用顺序存储便于插入和删除操作的实现 3．设顺序循环队列Q[0：M-1]的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为（C）。 (A) R-F (B) F-R (C) (R-F+M)％M (D) (F-R+M)％M 4．设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（A）。 (A) BADC(B)BCDA (C) CDAB (D) CBDA 5．设某棵二叉树中有2000个结点，则该二叉树的最小高度为（C）。 (A) 9 (B) 10 (C) 11(D) 12 6．下面程序的时间复杂为（B） for（i=1，s=0；i<=n；i++）{t=1；for(j=1；j<=i；j++) t=t*j；s=s+t；} (A) O(n) (B) O(n2)(C) O(n3) (D) O(n4) 7．设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为（C）。 (A) q=p->next；p->data=q->data；p->next=q->next；free(q)； (B) q=p->next；q->data=p->data；p->next=q->next；free(q)； (C) q=p->next；p->next=q->next；free(q)； (D) q=p->next；p->data=q->data；free(q)； 8．设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（C ）。 (A)O(n) (B) O(nlog2n) (C) O(1)(D) O(n2) 9．设一棵二叉树的深度为k，则该二叉树中最多有（D ）个结点。 (A) 2k-1 (B) 2k(C) 2k-1(D) 2k-1 10．设用链表作为栈的存储结构则退栈操作（ B ）。 (A) 必须判别栈是否为满(B) 必须判别栈是否为空 (C) 判别栈元素的类型(D) 对栈不作任何判别 11．函数substr(“DATASTRUCTURE”，5，9)的返回值为（A ）。 (A) “STRUCTURE”(B) “DATA” (C) “ASTRUCTUR”(D) “DATASTRUCTURE” 12．设某二叉树中度数为0的结点数为N0，度数为1的结点数为N l，度数为2的结点数为N2，则下列等式成立的是（ C）。 (A) N0=N1+1 (B) N0=N l+N2(C) N0=N2+1(D) N0=2N1+l 13．设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是（B ）。 (A) 空或只有一个结点(B) 高度等于其结点数 (C) 任一结点无左孩子(D) 任一结点无右孩子 14. 深度为k的完全二叉树中最少有（ B ）个结点。 (A) 2k-1-1 (B) 2k-1(C) 2k-1+1(D) 2k-1 《社区治理》第二次作业答案（第3—4章） 一、不定项选择题（每小题2分，共18分） 1．1954年全国人民代表大会常务委员会通过的《城市街道办事处组织条例》规定： 街道办事处是（C）。 A.城市最基层的政府机关 B.城市基层群众性自治组织 C.市辖区或者不设区的市的人民委员会的派出机关 D.城市社区的社会团体 2．1954年全国人民代表大会党务委员会通过的《城市居民委员会组织条例》规定，居民委员会是（B）。 A.街道办事处的派出机构 B.城市基层群众居民组织 C.城市群众性社会团体 D.城市最基层政权形式 3．1958年之前，我国农村基层实行的管理体制是（B）。 A.人民公社政社合一管理体制 B.乡（行政）管理体制 C.三级所有、队为基础管理体制 D.乡政村管理体制 4． 1998年11月，全国人大通过的《中华人民共和国村民委 员会组织法》明确界定了村民委员会的性质为（B）。 A.农村基层的政权组织 B.农村基层群众性自治组织 C.农村基层的经济组织 D.农村基层的社会团体 4．政府机构具有扩张的本性已被（B）所证明。 A.亚当-斯密关于市场“看不见的手”的论述 B.帕金森定律 C.“马太效应”理论 D.凯恩斯的“消费驱动”理论 5．党的领导在社区工作中主要体现为（B）。 A.组织领导 B.政治领导 C.行政领导 D.工作领导 6.社区工作学者杰克-罗斯曼把资本主义国家的社区治理策略划分成（ABC）几种模式。 A.地区发展策略 B.社会行为策略 C.社会计划策略 D.自我帮助策略 7.1954年全国人民代表大会常务委员会通过的《城市街道办事处组织条例》规定： 街道办事处的工作主要包括（ABD）。 A.办理基层政府有关居民工作的交办事项 B.指导居民委员会建设 C.领导辖区经济 D.反映居民意见和要求 8．根据约翰-霍普金斯大学萨拉蒙教授的观点，非营利组织的基本特征，除了正规性和民间性之外，还包括（ABCD）。 A.非营利性 B.自治性 C.志愿性 D.公益性 9．社区党建工作的必要性体现在（ABCD）。 A.加强社区党建工作是抓好党的基层组织建设、巩固执政党地位的需要 B.加强社区党建工作是在社区工作中发挥正确政治思想导向作用的需要 C.搞好社区党建是新时期落实党密切联系群众工作方法的必然选择 D.搞好社区党建是化解社会矛盾、维护社会稳定的需要 二、名词解释（每小题5分，共15分） 1.市场失灵： 数据结构第二次作业答案 一.单项选择题(20分) ( )1.一棵左子树为空的二叉树在前序线索化后，其空指针域数为 C a、0 b、1 c、2 d、不确定 ( )2.下列排序算法中，___D_____算法可能会出现下面的情况：初始数据有序时，花费的时间反而更长。 a、堆排序 b、起泡排序 c、直接选择排序 d、快速排序 ( )3.在图采用邻接表存储时，求最小生成树的prim算法的时间复杂度是__B_____。 a.O(n*e) b. O(n+e) c. O(n2) d.O(n3) ( )4.下面程序段的时间复杂度是__A______。 i=1; while(i<=n) i++; a. O(n) b. O(n2) c. O(2n) d. O(log2n) ( )5.在有n(>0)个结点且为完全二叉树的二叉排序树中查找一个键值，其平均比较次数的数量级为____B______。 a. O(n) b. O(log2n) c. O(nlog2n) d. O(n2) ( )6.采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分为__B_____个结点最佳。 a. 10 b. 25 c. 6 d. 625 ( )7.排序算法的稳定性是指__A____。 a.经过排序之后，能使值相同的数据保持原顺序中的相对位置不变 b.经过排序之后，能使值相同的数据保持原顺序中的绝对位置不变 c.算法的排序性能与被排序元素的数量关系不大 d.算法的排序性能与被排序元素的数量关系密切 ( )8.某二叉树的先序序列和后序序列正好相反，则该二叉树一定是___B____的二叉树。 a. 空或只有一个结点 b. 高度等于其结点数（空树高度为0） c. 任一结点无左孩子 d. 任一结点无右孩子 ( )9.已知有向图G=(V,E)其中V={ V1 V2 V3 V4 V5 V6 V7},E={ 软件技术基础第三次作业 一、单选题（23题，每题3分） 1、若有说明int *ptr1, *ptr2, m=5,n;，下面正确的语句组是 A. ptr1=&m; ptr2=&ptr1; B. ptr1=&m; ptr2=n; *ptr2=*ptr1; C. ptr1=&m; ptr2=ptr1; D. ptr1=&m; *ptr2=*ptr1; 2、对于10的－5次方，合法的C常量表示是 A. le-5 B. 10e-5 C. 10*e-5 D.1*e-5 3、以下叙述正确的是 A.输入项可以是一个实型常量，如scanf(“%f,3.5”); B.只有格式控制，没有输入项，也能正确输入数据到内存，例如scanf(“a=%d,b=%d”); C.当输入一个实数数据时，格式符可以控制小数的位数，例如scanf(“%4.2f”,&f); D.当输入数据时，必须指明变量地址，例如scanf(“%f”,&f); 4、若已定义: int a[ ]={0,1,2,3,4,5,6,7,8,9}, *p=a,i; 其中0≤i≤9, 则对a数组元素不正确的引用是___ ___。 A. a[p-a] B. *(&a[i]) C. p[i] D. a[10] 5、设x和y均为int型变量，则以下语句：x+=y;y=x-y;x-=y;的功能是____ A．把x和y按从大到小排列 B. 把x和y按从小到大排列 C. 无确定结果 D. 交换x和y中的值 6、在一个单链表中，若指针p1所指结点不是最后结点，则在p1之后插入指针p2所指 结点应执行。 A. p1->next=p2; p2->next=p1; B. p2->next=p1->next; p1=p2; B. p2->next=p1; p1->next=p2; D. p2->next=p1->next; p1->next=p2; 7、已知：char s[4] = "cba"; char *p; 执行语句序列p = s;printf("%c\n",*(p+1));后，输出为_____。 A. 字符?c? B. 字符?b? C. 字符?a? D. 字符?d? 8、设p1和p2是指向同一个int型一维数组的指针变量, k为int型变量,则不能正确执行的语句是__ ___。 A. k=*p1+*p2; B. p2=k; C. p1=p2; D. k=*p1 *(*p2); 9、有一链式堆栈ls（无头结点），其栈顶指针为ls.top，结点结构为：data域和 link（指针）域。现在对该栈进行出栈操作，出栈后ls.top的值为：。 A. ls.top->link B. ls.top-- C. ls.top->data D. ls.top++ 10、线性表的顺序存储结构是一种存储结构。 A. 随机存取 B. 顺序存取 C. 索引存取 D. Hash存取数据结构习题及参考答案
数据结构第3次作业
数据结构和算法习题及答案解析
数据结构第二次单元测试
数据结构作业题及参考答案
计算机文化基础-第三次在线作业
数据结构课后习题及答案
《数据结构》填空作业题(答案)
第三次作业参考答案
数据结构习题与答案
数据结构第二次实验报告
数据结构习题及参考答案 .
2011年12月考试数据结构第二次作业
数据结构作业(附答案)
《电大社区治理》第二次作业答案(第3―4章)
数据结构(C++)第二次作业答案
软件技术基础第三次作业