第3章 栈和上机作业.

第3章栈和队列答案一、填空题1. 向量、栈和队列都是线性结构，可以在向量的任何位置插入和删除元素；对于栈只能在栈顶插入和删除元素；对于队列只能在队尾插入和队首删除元素。

2. 栈是一种特殊的线性表，允许插入和删除运算的一端称为栈顶。

不允许插入和删除运算的一端称为栈底。

3. 队列是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。

4. 在具有n个单元的循环队列中，队满时共有 n-1 个元素。

5. 带表头结点的空循环双向链表的长度等于0。

解：Array二、判断正误（×）1. 在表结构中最常用的是线性表，栈和队列不太常用。

错，不一定吧调用子程序或函数常用，CPU中也用队列。

（√）2. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。

（√）3. 对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。

正确，都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。

（×）4. 栈和链表是两种不同的数据结构。

错，栈是逻辑结构的概念，是特殊殊线性表，而链表是存储结构概念，二者不是同类项。

（×）5. 栈和队列是一种非线性数据结构。

错，他们都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。

（√）6. 栈和队列的存储方式既可是顺序方式，也可是链接方式。

（√）7. 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。

（×）8. 队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。

错，后半句不对。

（×）9. 一个栈的输入序列是12345，则栈的输出序列不可能是12345。

错，有可能。

三、单项选择题（ B）1. 栈中元素的进出原则是Ａ．先进先出Ｂ．后进先出Ｃ．栈空则进Ｄ．栈满则出（C）2. 若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为Ａ．i Ｂ．n=i Ｃ．n-i+1 Ｄ．不确定解释：当p1=n，即n是最先出栈的，根据栈的原理，n必定是最后入栈的（事实上题目已经表明了），那么输入顺序必定是1，2，3，…，n，则出栈的序列是n，…，3，2，1。

第三章作业答案2. MCS-51有（4）个8位并行I/O口，在作为通用I/O口使用时P0~P3是准双向口，所以由输出转输入时必须先写入（1）。

6. 设（TMOD）=0A5H，则定时器T0的状态是( 方式1计数)，定时器T1的状态是( 方式2定时)。

或设（TMOD）=0A5H，则定时器T0的状态是( 软件控制的16位计数器)，定时器T1的状态是(软硬件控制的可自动重装初值的8位定时器)。

27．请写出1INT为低电平触发的中断系统初始化程序。

解：INT为低电平触发的中断系统初始化程序如下：1ORG 0000HLJMP MAINORG 0013HLJMP INTN1ORG 0100HMAIN：MOV SP，#60HSETB EASETB EX1；开1INT中断CLR PX1 ；令1INT为低优先级CLR IT1 ；令1INT为电平触发SJMP $INTN1：……RETIEND用MOV指令实现：MOV IE，#84HANL IP，#0FBH（或ORL IP，#04H）ANL TCON，#0FBH28．MCS-51单片机响应中断后，写出中断服务子程序的入口地址。

解:36．使用一个定时器，如何通过软硬结合方法实现较长时间的定时？解:设定好定时器的定时时间，采用中断方式用软件进行溢出次数累计，从而得到较长的定时时间，定时时间=定时器的定时时间×软件累计的溢出次数。

37．利用定时器输出周期为2 ms的方波, 设单片机晶振频率为6 MHz。

试编程实现之。

解：选用定时器/计数器T0 作定时器，工作在方式1，输出为P1.0 引脚，2 ms 的方波可由1 ms的高低电平相间隔而成，因而只要每隔1 ms对P1.0 取反一次即可得到这个方波。

初值的计算如下：T0=12/(6×106)= 2×10－6STC=M-T/T0=216－1×10－3/2×10－6=65536－500=65036=FE0CH当定时器/计数器采用方式0时，初值为：TC=M-T/T0=213－1×10－3/2×10－6=8192－500=7692=1E0CH，则真正的16位计数初值为：1E0CH（高8位，低5位）利用定时器/计数器时，必须用文字说明工作方式的设置，计算初值。

第三章本章介绍的是栈和队列的逻辑结构定义及在两种存储结构(顺序存储结构和链式存储结构)上如何实现栈和队列的基本运算。

本章的重点是掌握栈和队列在两种存储结构上实现的基本运算，难点是循环队列中对边界条件的处理。

1.栈的逻辑结构、存储结构及其相关算法(综合应用):栈的逻辑结构和我们先前学过的线性表相同，如果它是非空的，则有且只有一个开始结点，有且只能有一个终端结点，其它的结点前后所相邻的也只能是一个结点(直接前趋和直接后继),但是栈的运算规则与线性表相比有更多的限制，栈(Stack)是仅限制在表的一端进行插入和删除运算的线性表，通常称插入、删除这一端为栈顶，另一端称为栈底。

表中无元素时为空栈。

栈的修改是按后进先出的原则进行的，我们又称栈为LIFO表(Last In First Out).栈的基本运算有六种：构造空栈：InitStack(S)、判栈空: StackEmpty(S)、判栈满： StackFull(S)、进栈： Push(S,x)、可形象地理解为压入，这时栈中会多一个元素退栈： Pop(S) 、可形象地理解为弹出，弹出后栈中就无此元素了。

取栈顶元素：StackTop(S),不同与弹出，只是使用栈顶元素的值，该元素仍在栈顶不会改变。

由于栈也是线性表，因此线性表的存储结构对栈也适用，通常栈有顺序栈和链栈两种存储结构，这两种存储结构的不同，则使得实现栈的基本运算的算法也有所不同。

我们要了解的是，在顺序栈中有"上溢"和"下溢"的概念。

顺序栈好比一个盒子，我们在里头放了一叠书，当我们要用书的话只能从第一本开始拿(你会把盒子翻过来吗?真聪明^^)，那么当我们把书本放到这个栈中超过盒子的顶部时就放不下了(叠上去的不算，哼哼)，这时就是"上溢","上溢"也就是栈顶指针指出栈的外面，显然是出错了。

反之，当栈中已没有书时，我们再去拿，看看没书，把盒子拎起来看看盒底，还是没有，这就是"下溢"。

第1章绪论【书面作业】1、下列是几种二元组表示的数据结构，画出它们的逻辑结构图，并指出它们分别属于何种结构。

①A=(K,R),其中K={a,b,c,d,e,f,g,h}R={r}r={<a,b>,<b,c>,<c,d>,<d,e>,<e,f>,<f,g>,<g,h>}②B=(K,R),其中K={a,b,c,d,e,f,g,h}R={r}r={<d,b>,<d,g>,<d,a>,<b,c>,<g,e>,<g,h>,<e,f>}③C=(K,R),其中K={a,b,c,d,e,f}R={r}r={<a,b>,<b,c>,<b,d>,<c,d>,<c,e>,<c,f>,<d,e>,<d,f>}2、求下面程序段的时间复杂度①for (i=0;i<n; i++) ②i=s=0；③s=0；for(j=0;j<m; j++) while(s<n) for(i=0;i<n;i++)a[i][j]=0; { i++; for(j=0;j<n; j++)s+=i;} s+=b[i][j];④x=n; y=0;while ( (x>=(y+1)*(y+1) )y=y+1;【上机作业】1．熟悉VC++编程环境2．TRIPLET算法实现（看懂程序）3. 已知输入x, y, z三个不相等的整数，实现三个数从小到大顺序的输出，其中x 中存放最小数，y中存放次小数。

要求使用引用参数来实现。

4. 测试算法的运行时间在此，我们通过一个比较两个算法执行效率的程序例子，掌握测试算法运行时间的基本方法。

这里涉及到C语言中标准的函数库sys/timeb。

考研数据结构必须掌握的知识点与算法-打印版《数据结构》必须掌握的知识点与算法第一章绪论1、算法的五个重要特性（有穷性、确定性、可行性、输入、输出）2、算法设计的要求（正确性、可读性、茁壮性、效率与低存储量需求）3、算法与程序的关系：（1）一具程序别一定满脚有穷性。

例操作系统，只要整个系统别遭破坏，它将永久不可能停止，即使没有作业需要处理，它仍处于动态等待中。

所以，操作系统别是一具算法。

（2）程序中的指令必须是机器可执行的，而算法中的指令则无此限制。

算法代表了对咨询题的解，而程序则是算法在计算机上的特定的实现。

（3）一具算法若用程序设计语言来描述，则它算是一具程序。

4、算法的时刻复杂度的表示与计算（那个比较复杂，具体看算法本身，普通关怀其循环的次数与N的关系、函数递归的计算）第二章线性表1、线性表的特点：（1）存在唯一的第一具元素；（这一点决定了图别是线性表）（2）存在唯一的最终一具元素；（3）除第一具元素外，其它均惟独一具前驱（这一点决定了树别是线性表）（4）除最终一具元素外，其它均惟独一具后继。

2、线性表有两种表示：顺序表示（数组）、链式表示（链表），栈、队列基本上线性表，他们都能够用数组、链表来实现。

3、顺序表示的线性表（数组）地址计算办法：（1）一维数组，设DataType a[N]的首地址为A0，每一具数据（DataType 类型）占m个字节，则a[k]的地址为：A a[k]＝A0+m*k（其直截了当意义算是求在数据a[k]的前面有多少个元素，每个元素占m个字节）（2）多维数组，以三维数组为例，设DataType a[M][N][P]的首地址为A000，每一具数据（DataType 类型）占m个字节，则在元素a[i][j][k]的前面共有元素个数为：M*N*i+N*j+k，其其地址为：A a[i][j][k]＝A000+m*(M*N*i+N*j+k)；4、线性表的归并排序：设两个线性表均差不多按非递减顺序排好序，现要将两者合并为一具线性表，并仍然接非递减顺序。

《移动应用开发技术》教学设计课程名称：移动应用开发技术授课年级：授课学期：教师姓名：教学过程第一学时（Activity简介、Activity的创建）一、情景导入1、什么是Activity不知道大家有没有想过这样一个问题，每个应用程序都有很多界面组成，这些界面由什么管理的呢？同学进行回答，然后老师引出本节课要讲解的Activity。

二、知识讲解1、Activity简介（PPT8-10）在Android系统中，用户与程序的交互是通过Activity完成的。

Activity是Android应用程序的四大组件之一，它负责管理Android应用程序的界面。

一个应用程序一般会包含若干个Activity，每一个Activity组件负责一个界面的展现。

下面列举几个Activity的常用事件，具体如下：•onKeyDown(int keyCode,KeyEvent event)：对应按键按下事件•onKeyUp(int keyCode,KeyEvent event)：对应按键松开事件•onTouchEvent(MotionEvent event)：对应点击屏幕事件然后在MainActivity中重写上述方法，运行程序进行测试。

2、Activity的创建（PPT11）老师引导，大家对Activity有了简单的认识，接下来分步骤演示如何创建Activity。

1）定义一个类继承自android.app.Activity或者其子类；2）在res/layout目录中创建一个xml文件，用于创建Activity的布局；3）在AndroidManifest.xml文件中注册Activity；4）重写Activity的onCreate()方法，并在该方法中使用setContentView()加载指定的布局文件；Activity中的代码如下所示：public class ActivityExample extends Activity {protected void onCreate(Bundle savedInstanceState) {super.onCreate(savedInstanceState);setContentView(yout.activity_example);}}三、知识巩固1、总结知识点，使用博学谷系统中的随堂练习题巩固本节课所学知识。

第二/三章：进程与线程掌握要点：1.掌握并发执行的特征与条件。

2.理解进程的概念与状态（转换）。

3.linux的进程(任务)控制块都包含了进程的那些信息?4.进程间通信有那几种方式!各自的工作原理?5.简述进程的创建过程以及fork函数与vfork函数的区别。

6.比较线程和进程的优缺点!7.用户级线程和内核级线程的概念及各自特点。

上机作业：（共2源程序，2个可执行程序）：1. 观看03_pth1.c运行过程中进程(线程)的变化!简述这种变化出现的原因!!#include <pthread.h>#include <stdio.h>int sum；/* this data is shared by the thread(s) */void *runner(void *param)；/* the thread */main(int argc,char *argv[]){pthread_t tid；/* the thread indentifier */pthread_attr_t attr；/*set of thread attributes */if(argc!=2){fprintf(stderr,"usage；%s <interger value>\n"，argv[0]);exit();}if(atoi(argv[1])<0){fprintf(stderr，"%d must be <= 0\n"，atoi(argv[1]));exit()；}/* get the default attributes */pthread_attr_init(&attr)；/* creat the thread */pthread_create(&tid,&attr,runner,argv[1])；/* now wait for the thread to exit */pthread_join(tid,NULL)；printf("sum = %d\n",sum)；}/* the thread will begin control in this function */void *runner(void *param){int upper = atoi(param);int i；sum = 0；if(upper > 0){for(i=1；i<=upper；i++) sum += i;}pthread_exit(0)；}补充材料一：linux多线程编程pthreadLinux系统下的多线程遵循POSIX线程接口，称为pthread。

一、程序流程说明链栈3-1：1.建立一个空链栈：将链栈的栈顶置为NULL2.进栈：新建一个链栈节点，令这个节点的数据为需要进栈的数据，然后将这个节点指向原栈顶，将栈顶重新定义为这个节点并返回。

3.出栈：首先判断链栈是否为空，如果不为空返回栈顶的下一个节点，然后释放栈顶。

4.建立链栈：建立一个空链栈后调用进栈函数将数据一个一个进栈即可。

循环队列3-2：1.置空队列：使p->front=p->rear=0即可由于循环队列的性质队头或队尾的后移需要这样定义：p->rear=(p->rear+1)%N;p->front=(p->front+1)%N;2.进队列：首先判断队列是否已满，如果没满，将数据插入队尾，然后将队尾向后移动一格。

3.出队列：首先判断队列是否为空，如果不为空，返回队头元素，并将队头向后移一格。

4.aa函数：，调用出队函数把队列q中的元素一一出队，如果是负数直接抛弃；如果是正数，则调用入队函数，插入到q的队尾。

程序代码：链栈3-1：#include<stdio.h>#include<stdlib.h>struct node{int data;//节点信息struct node *next;};//建立一个空链栈node *empty(node *top){top=NULL;return top;}//进栈函数node *pushs(node *top,int x){node *p;p=(node*)malloc(sizeof(node));p->data=x;p->next=top;top=p;return top;}//出栈函数node *pops(node *top){node *p;if(top==NULL){printf("error!\n");return NULL;}else{p=top;top=p->next;free(p);}return top;}//显示函数void show(node *top){printf("the numbers are:\n");while(top!=NULL){printf("%d ",top->data);top=top->next;}}void main(){node *top;top=(node*)malloc(sizeof(node));int x;top=empty(top);printf("insert your number!(use zero as the end)\n");scanf("%d",&x);while(x!=0){top=pushs(top,x);scanf("%d",&x);}show(top);top=pops(top);top=pops(top);printf("\nAfter twice pops\n");show(top);}循环队列3-2：:#include<stdio.h>#include<stdlib.h>#define N 20#define true 1#define false 0typedef struct{int data[N];int front, rear;}node;//进队列函数int enter(node *p,int x){if(((p->rear)+1)%N==p->front)return (false);else{p->data[p->rear]=x;p->rear=(p->rear+1)%N;return (true);}}//出队列函数int out(node *p){int x;if(p->rear==p->front)return (NULL);else{x=p->data[p->front];p->front=(p->front+1)%N;}return x;}//aa函数，其功能为，调用出队函数把队列q中的元素一一出队，//如果是负数直接抛弃；如果是正数，则调用入队函数，插入到q的队尾。

《数据结构》教学大纲课程编号：070114A课程类型：□通识教育必修课□通识教育选修课专业必修课□专业选修课□学科基础课总学时：64 讲课学时：48 实验（上机）学时：16学分：4适用对象：信息管理与信息系统专业（电子商务）、电子商务专业（商务智能）、信息管理与信息系统专业（量化投资）先修课程：高等数学、程序设计基础与应用一、教学目标程序的构成与数据结构是两个不可分割的问题。

为解决现实世界中的问题，必须先对问题进行分析,得到问题本身的逻辑关系,然后采用合理的数学模型进行表示，这需要对程序构造进行系统而科学的研究，因而数据结构是设计与实现编译程序，操作系统，数据库系统，多媒体信息处理，数字图象处理及其它系统程序和大型应用程序的重要基础，是介于数学，计算机硬件，软件之间的一门核心课程，是信息管理与管理信息系统专业一门重要的专业技术基础课程。

本课程的目的在于向学生介绍计算机是如何处理, 组织和操作数据，如何评价算法的效率，使学生能够利用所学的理论知识解决实际问题，培养学生分析问题、解决问题的能力。

通过本课程的学习，使学生深透地理解数据结构的逻辑结构和物理结构的基本概念以及有关算法，培养基本的、良好的程序设计技能，编制高效可靠的程序，为学习操作系统、编译原理和数据库等课程奠定基础。

二、教学内容及其与毕业要求的对应关系（一）教学内容本课程的主要内容包括数据的逻辑结构和存储结构及在两者之上设计的算法。

数据的逻辑结构主要包括线性结构、层次结构和图结构；存储结构包括顺序存储和链式存储。

具体内容可分为5部分：1）线性结构数据的存储和运算，栈与队列的特点与应用、数组的存储与效率；2）树状结构的存储与运算，二叉树的性质、存储与操作实现，哈夫曼树与哈夫曼编码；3）图状结构的存储于运算，图的应用与相关算法的设计、实现；4）静态查找与动态查找的相关算法；5）各种排序算法及其效率比较分析。

（二）教学方法和手段根据教学目标，拟采用的教学方法有：课堂讲解基本概念和核心知识，讲授和讨论相结合领会知识要点，案例教学训练解决问题的能力，最后在visualC平台下进行上机操作和具体实践。