清华数据结构习题集答案(C语言版严蔚敏)

清华数据结构习题集答案(C 语言版严蔚敏)

第1章 绪论

1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。

解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。

数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。

数据类型是一个值的集合和定义在这个值集上的一组操作的总称。

抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。

解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。 1.3 设有数据结构(D,R)，其中

{}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r =

试按图论中图的画法惯例画出其逻辑结构图。

解：

1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。 解：

ADT Complex{ 数据对象：D={r,i|r,i 为实数} 数据关系：R={} 基本操作： InitComplex(&C,re,im)

操作结果：构造一个复数C ，其实部和虚部分别为re 和im DestroyCmoplex(&C)

操作结果：销毁复数C Get(C,k,&e)

操作结果：用e 返回复数C 的第k 元的值

Put(&C,k,e)

操作结果：改变复数C的第k元的值为e

IsAscending(C)

操作结果：如果复数C的两个元素按升序排列，则返回1，否则返回0 IsDescending(C)

操作结果：如果复数C的两个元素按降序排列，则返回1，否则返回0 Max(C,&e)

操作结果：用e返回复数C的两个元素中值较大的一个

Min(C,&e)

操作结果：用e返回复数C的两个元素中值较小的一个}ADT Complex

ADT RationalNumber{

数据对象：D={s,m|s,m为自然数，且m不为0}

数据关系：R={}

基本操作：

InitRationalNumber(&R,s,m)

操作结果：构造一个有理数R，其分子和分母分别为s和m

DestroyRationalNumber(&R)

操作结果：销毁有理数R

Get(R,k,&e)

操作结果：用e返回有理数R的第k元的值

Put(&R,k,e)

操作结果：改变有理数R的第k元的值为e

IsAscending(R)

操作结果：若有理数R的两个元素按升序排列，则返回1，否则返回0 IsDescending(R)

操作结果：若有理数R的两个元素按降序排列，则返回1，否则返回0 Max(R,&e)

操作结果：用e返回有理数R的两个元素中值较大的一个

Min(R,&e)

操作结果：用e返回有理数R的两个元素中值较小的一个}ADT RationalNumber

1.5 试画出与下列程序段等价的框图。

(1) product=1; i=1;

while(i<=n){

product *= i;

i++;

}

(2) i=0;

do {

i++;

} while((i!=n) && (a[i]!=x));

(3) switch {

case x

case x=y: z=abs(x*y); break;

default: z=(x-y)/abs(x)*abs(y);

}

1.6 在程序设计中，常用下列三种不同的出错处理方式：

(1) 用exit语句终止执行并报告错误；

(2) 以函数的返回值区别正确返回或错误返回；

(3) 设置一个整型变量的函数参数以区别正确返回或某种错误返回。

试讨论这三种方法各自的优缺点。

解：(1)exit常用于异常错误处理，它可以强行中断程序的执行，返回操作系统。

(2)以函数的返回值判断正确与否常用于子程序的测试，便于实现程序的局部控制。

(3)用整型函数进行错误处理的优点是可以给出错误类型，便于迅速确定错误。

1.7 在程序设计中，可采用下列三种方法实现输出和输入：

(1) 通过scanf和printf语句；

(2) 通过函数的参数显式传递；

(3) 通过全局变量隐式传递。

试讨论这三种方法的优缺点。

解：(1)用scanf和printf直接进行输入输出的好处是形象、直观，但缺点是需要对其进行格式控制，较为烦琐，如果出现错误，则会引起整个系统的崩溃。

(2)通过函数的参数传递进行输入输出，便于实现信息的隐蔽，减少出错的可能。

(3)通过全局变量的隐式传递进行输入输出最为方便，只需修改变量的值即可，但过多的全局变量使程序的维护较为困难。

1.8 设n为正整数。试确定下列各程序段中前置以记号@的语句的频度：

(1) i=1; k=0;

while(i<=n-1){

@ k += 10*i;

i++;

}

(2) i=1; k=0;

do {

@ k += 10*i;

i++;

} while(i<=n-1);

(3) i=1; k=0;

while (i<=n-1) {

i++;

@ k += 10*i;

}

(4) k=0;

for(i=1; i<=n; i++) {

for(j=i; j<=n; j++)

@ k++;

}

(5) for(i=1; i<=n; i++) {

for(j=1; j<=i; j++) { for(k=1; k<=j; k++) @ x += delta; }

(6) i=1; j=0; while(i+j<=n) { @ if(i>j) j++;

else i++; }

(7) x=n; y=0; // n 是不小于1的常数 while(x>=(y+1)*(y+1)) { @ y++; }

(8) x=91; y=100; while(y>0) {

@ if(x>100) { x -= 10; y--; } else x++; } 解：(1) n-1 (2) n-1 (3) n-1

(4) n+(n-1)+(n-2)+ (1)

2

)

1(+n n (5) 1+(1+2)+(1+2+3)+...+(1+2+3+...+n)=

∑=+n

i i i 1

2)

1( =∑∑∑∑====+=+=+n

i n i n i n i i i i i i i 1

121212121)(21)1(21

=

)32)(1(12

1

)1(41)12)(1(121++=++++n n n n n n n n (6) n (7)

??n 向下取整

(8) 1100

1.9 假设n 为2的乘幂，并且n>2，试求下列算法的时间复杂度及变量count 的值（以n 的函数形式表示）。

int Time(int n) { count = 0; x=2;

while(x

x *= 2; count++;

}

return count;

}

解：)(log 2n o

count=2log 2

-n

1.11 已知有实现同一功能的两个算法，其时间复杂度分别为()n

O

2和()10

n O ，假设现实计算机可连续

运算的时间为7

10秒（100多天），又每秒可执行基本操作（根据这些操作来估算算法时间复杂度）5

10次。试问在此条件下，这两个算法可解问题的规模（即n 值的范围）各为多少？哪个算法更适宜？请说明理由。

解：12102

=n

n=40 1210

10=n

n=16

则对于同样的循环次数n ，在这个规模下，第二种算法所花费的代价要大得多。故在这个规模下，第一种算法更适宜。 1.12 设有以下三个函数：

()10002124++=n n n f ，()3450015n n n g +=，()n n n n h log 5005.3+=

请判断以下断言正确与否：

(1) f(n)是O(g(n)) (2) h(n)是O(f(n)) (3) g(n)是O(h(n)) (4) h(n)是O(n 3.5

) (5) h(n)是O(nlogn)

解：(1)对 (2)错 (3)错 (4)对 (5)错 1.13 试设定若干n 值，比较两函数2

n 和n n 2log 50的增长趋势，并确定n 在什么范围内，函数2n 的值

大于n n 2

log 50的值。

解：2

n 的增长趋势快。但在n 较小的时候，n n 2log 50的值较大。

当n>438时，n n n

22

log 50>

1.14 判断下列各对函数

()n f 和()n g ，当∞→n 时，哪个函数增长更快？

(1) ()(

)

3

10!ln 102n n n n f ++=，()724++=n n n g

(2)

()()()

2

5!ln +=n n f ，()5.213n n g

=

(3) ()141.2++=n n n f ，()()()n n n g +=2

!ln

(4)

()()()2

223

n n n f +=，()()52

n n n g n +=

解：(1)g(n)快 (2)g(n)快 (3)f(n)快 (4) f(n)快 1.15 试用数学归纳法证明：

(1)

()()6/12112

++=∑=n n n i

n

i ()0≥n (2)

()

()1/11

0--=+=∑x x

x n n

i i

()0,1≥≠n x

(3)

12211-=∑=-n n

i i

()1≥n (4)

()2

1

12n

i n

i =-∑=

()1≥n

1.16 试写一算法，自大至小依次输出顺序读入的三个整数X ，Y 和Z 的值

解：

int max3(int x,int y,int z) { if(x>y) if(x>z) return x; else return z; else

if(y>z) return y;

else return z;

}

1.17 已知k 阶斐波那契序列的定义为 00=f ，01=f ，…，02=-k f ，11=-k f ；

k n n n n f f f f ---+++= 21， ,1,+=k k n

试编写求k 阶斐波那契序列的第m 项值的函数算法，k 和m 均以值调用的形式在函数参数表中出现。

解：k>0为阶数，n 为数列的第n 项 int Fibonacci(int k,int n) { if(k<1) exit(OVERFLOW); int *p,x; p=new int[k+1]; if(!p) exit(OVERFLOW); int i,j;

for(i=0;i

}

for(i=k+1;i

for(j=0;j

p[k]=2*p[k-1]-x;

}

return p[k];

}

1.18 假设有A ，B ，C ，D ，E 五个高等院校进行田径对抗赛，各院校的单项成绩均已存入计算机，并构成一张表，表中每一行的形式为

项目名称 性别

校名

成绩

得分

编写算法，处理上述表格，以统计各院校的男、女总分和团体总分，并输出。

解：

typedef enum{A,B,C,D,E} SchoolName; typedef enum{Female,Male} SexType; typedef struct{ char event[3]; //项目 SexType sex; SchoolName school;

int score;

} Component; typedef struct{ int MaleSum;

//男团总分

int FemaleSum; //女团总分

int TotalSum; //团体总分

} Sum;

Sum SumScore(SchoolName sn,Component a[],int n) { Sum temp; temp.MaleSum=0; temp.FemaleSum=0; temp.TotalSum=0; int i;

for(i=0;i

}

}

temp.TotalSum=temp.MaleSum+temp.FemaleSum; return temp;

}

1.19 试编写算法，计算i

i 2!*的值并存入数组a[0..arrsize-1]的第i-1个分量中(i=1,2,…,n)。假设计算机中允许的整数最大值为maxint ，则当n>arrsize 或对某个()n k k ≤≤1，使int max 2!>?k

k 时，

应按出错处理。注意选择你认为较好的出错处理方法。

解：

#include

#include #define MAXINT 65535 #define ArrSize 100 int fun(int i);

int main() { int i,k; int a[ArrSize]; cout<<"Enter k:"; cin>>k;

if(k>ArrSize-1) exit(0); for(i=0;i<=k;i++){ if(i==0) a[i]=1; else{ if(2*i*a[i-1]>MAXINT) exit(0); else a[i]=2*i*a[i-1];

}

}

for(i=0;i<=k;i++){ if(a[i]>MAXINT) exit(0); else cout<

return 0;

}

1.20 试编写算法求一元多项式的值()∑==n

i i i n

x a x P 0

的值()0x P n ，并确定算法中每一语句的执行次数

和整个算法的时间复杂度。注意选择你认为较好的输入和输出方法。本题的输入为()n i a i ,,1,0 =，0

x 和n ，输出为()0x P n

。

解：

#include #include #define N 10

double polynomail(int a[],int i,double x,int n); int main() {

double x; int n,i; int a[N];

cout<<"输入变量的值x:";

cin>>x;

cout<<"输入多项式的阶次n:";

cin>>n;

if(n>N-1) exit(0);

cout<<"输入多项式的系数a[0]--a[n]:";

for(i=0;i<=n;i++) cin>>a[i];

cout<<"The polynomail value is "<

return 0;

}

double polynomail(int a[],int i,double x,int n)

{

if(i>0) return a[n-i]+polynomail(a,i-1,x,n)*x;

else return a[n];

}

本算法的时间复杂度为o(n)。

第2章线性表

2.1 描述以下三个概念的区别：头指针，头结点，首元结点（第一个元素结点）。

解：头指针是指向链表中第一个结点的指针。首元结点是指链表中存储第一个数据元素的结点。头结点是在首元结点之前附设的一个结点，该结点不存储数据元素，其指针域指向首元结点，其作用主要是为了方便对链表的操作。它可以对空表、非空表以及首元结点的操作进行统一处理。

2.2 填空题。

解：(1) 在顺序表中插入或删除一个元素，需要平均移动表中一半元素，具体移动的元素个数与元素在表中的位置有关。

(2) 顺序表中逻辑上相邻的元素的物理位置必定紧邻。单链表中逻辑上相邻的元素的物理位置不一定紧邻。

(3) 在单链表中，除了首元结点外，任一结点的存储位置由其前驱结点的链域的值指示。

(4) 在单链表中设置头结点的作用是插入和删除首元结点时不用进行特殊处理。

2.3 在什么情况下用顺序表比链表好？

解：当线性表的数据元素在物理位置上是连续存储的时候，用顺序表比用链表好，其特点是可以进行随机存取。

2.4 对以下单链表分别执行下列各程序段，并画出结果示意图。

解：

2.5 画出执行下列各行语句后各指针及链表的示意图。

L=(LinkList)malloc(sizeof(LNode)); P=L;

for(i=1;i<=4;i++){

P->next=(LinkList)malloc(sizeof(LNode));

P=P->next; P->data=i*2-1;

}

P->next=NULL;

for(i=4;i>=1;i--) Ins_LinkList(L,i+1,i*2);

for(i=1;i<=3;i++) Del_LinkList(L,i);

解：

2.6 已知L是无表头结点的单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。

a. 在P结点后插入S结点的语句序列是__________________。

b. 在P结点前插入S结点的语句序列是__________________。

c. 在表首插入S结点的语句序列是__________________。

d. 在表尾插入S结点的语句序列是__________________。

(1) P->next=S;

(2) P->next=P->next->next;

(3) P->next=S->next;

(4) S->next=P->next;

(5) S->next=L;

(6) S->next=NULL;

(7) Q=P;

(8) while(P->next!=Q) P=P->next;

(9) while(P->next!=NULL) P=P->next;

(10) P=Q;

(11) P=L;

(12) L=S;

(13) L=P;

解：a. (4) (1)

b. (7) (11) (8) (4) (1)

c. (5) (12)

d. (9) (1) (6)

2.7 已知L是带表头结点的非空单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。

a. 删除P结点的直接后继结点的语句序列是____________________。

b. 删除P结点的直接前驱结点的语句序列是____________________。

c. 删除P结点的语句序列是____________________。

d. 删除首元结点的语句序列是____________________。

e. 删除尾元结点的语句序列是____________________。

(1) P=P->next;

(2) P->next=P;

(3) P->next=P->next->next;

(4) P=P->next->next;

(5) while(P!=NULL) P=P->next;

(6) while(Q->next!=NULL) { P=Q; Q=Q->next; }

(7) while(P->next!=Q) P=P->next;

(8) while(P->next->next!=Q) P=P->next;

(9) while(P->next->next!=NULL) P=P->next;

(10) Q=P;

(11) Q=P->next;

(12) P=L;

(13) L=L->next;

(14) free(Q);

解：a. (11) (3) (14)

b. (10) (12) (8) (3) (14)

c. (10) (12) (7) (3) (14)

d. (12) (11) (3) (14)

e. (9) (11) (3) (14)

2.8 已知P结点是某双向链表的中间结点，试从下列提供的答案中选择合适的语句序列。

a. 在P结点后插入S结点的语句序列是_______________________。

b. 在P结点前插入S结点的语句序列是_______________________。

c. 删除P结点的直接后继结点的语句序列是_______________________。

d. 删除P结点的直接前驱结点的语句序列是_______________________。

e. 删除P结点的语句序列是_______________________。

(1) P->next=P->next->next;

(2) P->priou=P->priou->priou;

(3) P->next=S;

(4) P->priou=S;

(5) S->next=P;

(6) S->priou=P;

(7) S->next=P->next;

(8) S->priou=P->priou;

(9) P->priou->next=P->next;

(10) P->priou->next=P;

(11) P->next->priou=P;

(12) P->next->priou=S;

(13) P->priou->next=S;

(14) P->next->priou=P->priou;

(15) Q=P->next;

(16) Q=P->priou;

(17) free(P);

(18) free(Q);

解：a. (7) (3) (6) (12)

b. (8) (4) (5) (13)

c. (15) (1) (11) (18)

d. (16) (2) (10) (18)

e. (14) (9) (17)

2.9 简述以下算法的功能。

(1) Status A(LinkedList L) { //L是无表头结点的单链表

if(L && L->next) {

Q=L; L=L->next; P=L;

while(P->next) P=P->next;

P->next=Q; Q->next=NULL;

}

return OK;

}

(2) void BB(LNode *s, LNode *q) {

p=s;

while(p->next!=q) p=p->next;

p->next =s;

}

void AA(LNode *pa, LNode *pb) {

//pa和pb分别指向单循环链表中的两个结点

BB(pa,pb);

BB(pb,pa);

}

解：(1) 如果L的长度不小于2，将L的首元结点变成尾元结点。

(2) 将单循环链表拆成两个单循环链表。

2.10 指出以下算法中的错误和低效之处，并将它改写为一个既正确又高效的算法。

Status DeleteK(SqList &a,int i,int k)

{

//本过程从顺序存储结构的线性表a中删除第i个元素起的k个元素

if(i<1||k<0||i+k>a.length) return INFEASIBLE;//参数不合法

else {

for(count=1;count

//删除第一个元素

for(j=a.length;j>=i+1;j--) a.elem[j-i]=a.elem[j];

a.length--;

}

return OK;

}

解：

Status DeleteK(SqList &a,int i,int k)

{

//从顺序存储结构的线性表a中删除第i个元素起的k个元素

//注意i的编号从0开始

int j;

if(i<0||i>a.length-1||k<0||k>a.length-i) return INFEASIBLE;

for(j=0;j<=k;j++)

a.elem[j+i]=a.elem[j+i+k];

a.length=a.length-k;

return OK;

}

2.11 设顺序表va中的数据元素递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。

解：

Status InsertOrderList(SqList &va,ElemType x)

{

//在非递减的顺序表va中插入元素x并使其仍成为顺序表的算法

int i;

if(va.length==va.listsize)return(OVERFLOW);

for(i=va.length;i>0,x

va.elem[i]=va.elem[i-1]; va.elem[i]=x; va.length++; return OK;

} 2.12 设

()m a a A ,,1 =和()n b b B ,,1 =均为顺序表，A '和B '分别为A 和B 中除去最大共同前

缀后的子表。若

='='B A 空表，则B A =；若A '=空表，而≠'B 空表，或者两者均不为空表，且A '

的首元小于B '的首元，则B A <；否则B A >。试写一个比较A ，B 大小的算法。

解：

Status CompareOrderList(SqList &A,SqList &B) { int i,k,j;

k=A.length>B.length?A.length:B.length; for(i=0;iB.elem[i]) j=1; if(A.elem[i]

}

if(A.length>k) j=1; if(B.length>k) j=-1; if(A.length==B.length) j=0; return j;

}

2.13 试写一算法在带头结点的单链表结构上实现线性表操作Locate(L,x);

解：

int LocateElem_L(LinkList &L,ElemType x) { int i=0; LinkList p=L; while(p&&p->data!=x){ p=p->next; i++; }

if(!p) return 0; else return i;

}

2.14 试写一算法在带头结点的单链表结构上实现线性表操作Length(L)。

解：

//返回单链表的长度

int ListLength_L(LinkList &L) { int i=0;

LinkList p=L;

if(p) p=p-next;

while(p){

p=p->next;

i++;

}

return i;

}

2.15 已知指针ha和hb分别指向两个单链表的头结点，并且已知两个链表的长度分别为m和n。试写一算法将这两个链表连接在一起，假设指针hc指向连接后的链表的头结点，并要求算法以尽可能短的时间完成连接运算。请分析你的算法的时间复杂度。

解：

void MergeList_L(LinkList &ha,LinkList &hb,LinkList &hc)

{

LinkList pa,pb;

pa=ha;

pb=hb;

while(pa->next&&pb->next){

pa=pa->next;

pb=pb->next;

}

if(!pa->next){

hc=hb;

while(pb->next) pb=pb->next;

pb->next=ha->next;

}

else{

hc=ha;

while(pa->next) pa=pa->next;

pa->next=hb->next;

}

}

2.16 已知指针la和lb分别指向两个无头结点单链表中的首元结点。下列算法是从表la中删除自第i个元素起共len个元素后，将它们插入到表lb中第i个元素之前。试问此算法是否正确？若有错，请改正之。

Status DeleteAndInsertSub(LinkedList la,LinkedList lb,int i,int j,int len)

{

if(i<0||j<0||len<0) return INFEASIBLE;

p=la; k=1;

while(knext; k++; }

q=p;

while(k<=len){ q=q->next; k++; }

s=lb; k=1;

while(knext; k++; }

s->next=p; q->next=s->next;

return OK;

}

解：

Status DeleteAndInsertSub(LinkList &la,LinkList &lb,int i,int j,int len)

{

LinkList p,q,s,prev=NULL;

int k=1;

if(i<0||j<0||len<0) return INFEASIBLE;

// 在la表中查找第i个结点

p=la;

while(p&&k

prev=p;

p=p->next;

k++;

}

if(!p)return INFEASIBLE;

// 在la表中查找第i+len-1个结点

q=p; k=1;

while(q&&k

q=p->next;

k++;

}

if(!q)return INFEASIBLE;

// 完成删除，注意，i=1的情况需要特殊处理

if(!prev) la=q->next;

else prev->next=q->next;

// 将从la中删除的结点插入到lb中

if(j=1){

q->next=lb;

lb=p;

}

else{

s=lb; k=1;

while(s&&k

s=s->next;

k++;

}

if(!s)return INFEASIBLE;

q->next=s->next;

s->next=p; //完成插入

}

return OK;

}

2.17 试写一算法，在无头结点的动态单链表上实现线性表操作Insert(L,i,b)，并和在带头结点的动态单链表上实现相同操作的算法进行比较。

2.18试写一算法，实现线性表操作Delete(L,i)，并和在带头结点的动态单链表上实现相同操作的算法进行比较。

2.19 已知线性表中的元素以值递增有序排列，并以单链表作存储结构。试写一高效的算法，删除表中所有值大于mink且小于maxk的元素（若表中存在这样的元素），同时释放被删结点空间，并分析你的算法的时间复杂度（注意，mink和maxk是给定的两个参变量，它们的值可以和表中的元素相同，也可以不同）。

解：

Status ListDelete_L(LinkList &L,ElemType mink,ElemType maxk)

{

LinkList p,q,prev=NULL;

if(mink>maxk)return ERROR;

p=L;

prev=p;

p=p->next;

while(p&&p->data

if(p->data<=mink){

prev=p;

p=p->next;

}

else{

prev->next=p->next;

q=p;

p=p->next;

free(q);

}

}

return OK;

}

2.20 同2.19题条件，试写一高效的算法，删除表中所有值相同的多余元素（使得操作后的线性表中所有元素的值均不相同），同时释放被删结点空间，并分析你的算法的时间复杂度。

解：

void ListDelete_LSameNode(LinkList &L)

{

LinkList p,q,prev;

p=L;

prev=p;

p=p->next;

while(p){

prev=p;

p=p->next;

if(p&&p->data==prev->data){

prev->next=p->next;

q=p;

p=p->next;

free(q);

}

}

}

2.21 试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表

()n a a ,,1 逆置为

()1,,a a n 。

解：

// 顺序表的逆置

Status ListOppose_Sq(SqList &L) { int i; ElemType x;

for(i=0;i

L.elem[i]=L.elem[L.length-1-i]; L.elem[L.length-1-i]=x;

}

return OK;

}

2.22 试写一算法，对单链表实现就地逆置。

解：

// 带头结点的单链表的逆置 Status ListOppose_L(LinkList &L) { LinkList p,q; p=L; p=p->next; L->next=NULL; while(p){ q=p; p=p->next; q->next=L->next; L->next=q; }

return OK;

}

2.23 设线性表()m a a a A ,,,21 =，()n b b b B ,,,21 =，试写一个按下列规则合并A ，B 为线性表

C 的算法，即使得 ()n m m m b b b a b a C ,,,,,,,111 += 当n m

≤时；

()m n n n a a b a b a C ,,,,,,,111 +=

当n m >时。

线性表A，B和C均以单链表作存储结构，且C表利用A表和B表中的结点空间构成。注意：单链表的长度值m和n均未显式存储。

解：

// 将合并后的结果放在C表中，并删除B表

Status ListMerge_L(LinkList &A,LinkList &B,LinkList &C)

{

LinkList pa,pb,qa,qb;

pa=A->next;

pb=B->next;

C=A;

while(pa&&pb){

qa=pa; qb=pb;

pa=pa->next; pb=pb->next;

qb->next=qa->next;

qa->next=qb;

}

if(!pa)qb->next=pb;

pb=B;

free(pb);

return OK;

}

2.24 假设有两个按元素值递增有序排列的线性表A和B，均以单链表作存储结构，请编写算法将A表和B 表归并成一个按元素值递减有序（即非递增有序，允许表中含有值相同的元素）排列的线性表C，并要求利用原表（即A表和B表）的结点空间构造C表。

解：

// 将合并逆置后的结果放在C表中，并删除B表

Status ListMergeOppose_L(LinkList &A,LinkList &B,LinkList &C)

{

LinkList pa,pb,qa,qb;

pa=A;

pb=B;

qa=pa; // 保存pa的前驱指针

qb=pb; // 保存pb的前驱指针

pa=pa->next;

pb=pb->next;

A->next=NULL;

C=A;

while(pa&&pb){

if(pa->datadata){

qa=pa;

pa=pa->next;

qa->next=A->next; //将当前最小结点插入A表表头

A->next=qa;

}

else{

qb=pb;

pb=pb->next;

qb->next=A->next; //将当前最小结点插入A表表头

A->next=qb;

}

}

while(pa){

qa=pa;

pa=pa->next;

qa->next=A->next;

A->next=qa;

}

while(pb){

qb=pb;

pb=pb->next;

qb->next=A->next;

A->next=qb;

}

pb=B;

free(pb);

return OK;

}

2.25 假设以两个元素依值递增有序排列的线性表A和B分别表示两个集合（即同一表中的元素值各不相同），现要求另辟空间构成一个线性表C，其元素为A和B中元素的交集，且表C中的元素有依值递增有序排列。试对顺序表编写求C的算法。

解：

// 将A、B求交后的结果放在C表中

Status ListCross_Sq(SqList &A,SqList &B,SqList &C)

{

int i=0,j=0,k=0;

while(i

if(A.elem[i]

else

if(A.elem[i]>B.elem[j]) j++;

else{

ListInsert_Sq(C,k,A.elem[i]);

i++;

k++;

}

}

return OK;

}

2.26 要求同2.25题。试对单链表编写求C的算法。

80x86汇编语言程序设计教程》(清华大学出版社,黑色封面,杨季文著)

80x86汇编语言程序设计教程》（清华大学出版社，黑色封面，杨季文著） 《计算机操作系统原理》 《Inside Windows 2000》(微软出版社，我看的是E文版的，中文的书名想必是Windows 2000 技术内幕之类吧)。 《数据结构和算法》——这门课程能够决定一个人程序设计水平的高低，是一门核心课程。我首选的是清华版的（朱战立，刘天时） 《软件工程》——这门课程是越到后来就越发现它的重要，虽然刚开始看时就象看马哲一样不知所云。我的建议是看《实用软件工程》（黄色，清华） 《Windows 程序设计》——《北京大学出版社，Petzold著》我建议任何企图设计Windows 程序的人在学习VC以前仔细的学完它。而且前面的那本 建议：你还可以在CSDN上阅读到许多书评。这些书评能够帮助你决定读什么样的书 关于编程的网站 计算机编程 郭新明-FTP服务器体验式学习课程（张孝祥监制） https://www.wendangku.net/doc/c8877244.html,/so/so138.aspx?id=3997 https://www.wendangku.net/doc/c8877244.html,快速开发新闻系统在线播放 https://www.wendangku.net/doc/c8877244.html,/so/so138.aspx?id=4708 数字电路基础[宁波电大] https://www.wendangku.net/doc/c8877244.html,/so/so138.aspx?id=774 计算机组成与汇编语言程序设计(赵丽梅)宁波电大 https://www.wendangku.net/doc/c8877244.html,/so/so138.aspx?id=1242 操作系统(陈访荣)宁波电大（在线播放） https://www.wendangku.net/doc/c8877244.html,/so/so138.aspx?id=4708 计算机网络(马敏飞)宁波电大 https://www.wendangku.net/doc/c8877244.html,/so/so138.aspx?id=1243 https://www.wendangku.net/doc/c8877244.html, 2.0快速入门(12)－https://www.wendangku.net/doc/c8877244.html, 2.0网站快速导航 https://www.wendangku.net/doc/c8877244.html,/so/so138.aspx?id=2501 Internet和Intranet应用(薛昭旺)宁波电大 https://www.wendangku.net/doc/c8877244.html,/so/so138.aspx?id=1245 2004年电脑硬件安装调试维修视频教学讲授 https://www.wendangku.net/doc/c8877244.html,/so/so138.aspx?id=4825 https://www.wendangku.net/doc/c8877244.html, 高级排错技巧 https://www.wendangku.net/doc/c8877244.html,/so/so138.aspx?id=768 SQL Server 2000管理专家系列课程 https://www.wendangku.net/doc/c8877244.html,/so/so138.aspx?id=4832 开心三人行系列(2)：使用Atlas 构建AJAX应用 https://www.wendangku.net/doc/c8877244.html,/so/so138.aspx?id=2564 Visual Basic 2005开发技巧系列课程(4)： 在Visual Basic 2005中使用.NET Framework 2.0新增功能 https://www.wendangku.net/doc/c8877244.html,/so/so138.aspx?id=2526 SQL Server 2005 系列课程－使用ADO https://www.wendangku.net/doc/c8877244.html,开发SQL Server 2005 OLAP应用 https://www.wendangku.net/doc/c8877244.html,/so/so138.aspx?id=2535

严蔚敏版数据结构课后习题答案-完整版

第1章绪论 1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据

类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。 1.3 设有数据结构(D,R)，其中 {}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r = 试按图论中图的画法惯例画出其逻辑结构图。 解： 1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。 解： ADT Complex{ 数据对象：D={r,i|r,i 为实数} 数据关系：R={} 基本操作： InitComplex(&C,re,im) 操作结果：构造一个复数C ，其实部和虚部分别为re 和im DestroyCmoplex(&C)

清华大学C语言程序练习题

一、选择题 1．一个C语言程序是由（D ）构成。 A．语句B．行号C．数据D．函数 2．下面标识符中正确的是（）。 A．d&ef B．6a C．z4x5c D．a3/b4 3．在C语言中，存储一个字符型、整型、单精度实型变量所需的空间是（）。型、单精度实型变量所需的空间是（）。 A．1、2、4 B．1、1、4 C．1、2、8 D．2、2、8 4.为了避免嵌套的条件分支语句 if--else中的else总是与（）组成成对关系。 A.缩排位置相同的 B.在其之前未配对的 C.在其之前未配对的最近的if D.在同一行上的if 5．下列表达式的结果正确的是（）。 int aa，bb，cc，dd; aa=bb=cc=dd=1；sp; aa=bb=cc=dd=1；sp; aa=bb=cc=dd=1; （aa+1==2）？bb=aa+2：aa+3 A．2 B．3 C． 1 D．5 6．设有int x=11 ；则表达式（x+1/3）的值是（C ）。 A．3 B.4 C.11 D.12 7．设有字符串A=“He has 钱!”,则该字符串的长度为（ C ）。 A.9 B.10 C.11 D.8 8．有如下程序段,则正确的执行结果是（） int m=3; while(m<=5) { printf("%d ",m-3); m++; } A． 0 0 0 B．0 1 2 C．1 2 3 D.无结果 9.执行语句:printf("%d"，(a=2)&&(b= -2)；后，输出结果是（）。 A．无输出B．结果不确定C．-1 D.1

10.有如下定义类型语句，若从键盘输入数据，正确的输入语句是（）。 int x;Char y;Char z[20]; A.scanf("%d%c%c",&x,&y,&z); B.scanf("%d%c%s",&x,&y,&z); C.scanf("%d%c%c",&x,&y,z); D.scanf("%d%c%s",&x,&y,z); 11.struct ex { int x ; float y; char z ; } example; 则下面的叙述中不正确的是（）。 A.struct结构体类型的关键字 B.example是结构体类型名 C.x,y,z都是结构体成员名 D.struct ex是结构体类型 12.在C语言中对于实型数组,其每个数组元素的类型是( )。 A.实型 B.整型 C.可以为任何类型 D.不确定 13.若已定义：int a[9]，*p=a；不能表示a[1] 地址的表达式是( )。 A.p+1 B.a+1 C.a++ D.++p 二、填空题 1.在C语言中，正确的标识符是由____________组成的，且由____________开头的。 2.设p=30，那么执行q=(++p)后，表达式的结果q为______，变量p的结果为________。若a为int类型，且其值为3，则执行完表达式a+=a-=a*a后，a的值是_________。 3.一个变量的指针是指___________________________________________________。 4.在C语言程序中，对文件进行操作首先要____________________；然后对文件进行操作，最后要对文件实行__________________________操作，防止文件中信息的丢失。 5.以下程序运行后的输出结果是。该程序的功能是。 int main() { int x=10,y=20 ,t=0; if(x！=y) t=x;

数据结构习题及答案——严蔚敏_课后习题答案 精品

第一章绪论 选择题 1.组成数据的基本单位是（） （A）数据项（B）数据类型（C）数据元素（D）数据变量 2.数据结构是研究数据的（）以及它们之间的相互关系。 （A）理想结构，物理结构（B）理想结构，抽象结构 （C）物理结构，逻辑结构（D）抽象结构，逻辑结构 3.在数据结构中，从逻辑上可以把数据结构分成（） （A）动态结构和静态结构（B）紧凑结构和非紧凑结构 （C）线性结构和非线性结构（D）内部结构和外部结构 4.数据结构是一门研究非数值计算的程序设计问题中计算机的（①）以及它们之间的（②）和运算等的学科。 ①（A）数据元素（B）计算方法（C）逻辑存储（D）数据映像 ②（A）结构（B）关系（C）运算（D）算法 5.算法分析的目的是（）。 （A）找出数据结构的合理性（B）研究算法中的输入和输出的关系 （C）分析算法的效率以求改进（D）分析算法的易懂性和文档性 6.计算机算法指的是（①）,它必须具备输入、输出和（②）等5个特性。 ①（A）计算方法（B）排序方法（C）解决问题的有限运算序列（D）调度方法 ②（A）可执行性、可移植性和可扩充性（B）可行性、确定性和有穷性 （C）确定性、有穷性和稳定性（D）易读性、稳定性和安全性 二、判断题 1.数据的机内表示称为数据的存储结构。（） 2.算法就是程序。（） 3.数据元素是数据的最小单位。（） 4.算法的五个特性为：有穷性、输入、输出、完成性和确定性。（） 5.算法的时间复杂度取决于问题的规模和待处理数据的初态。（） 三、填空题 1.数据逻辑结构包括________、________、_________ 和_________四种类型,其中树形结构和图形结构合称为_____。 2.在线性结构中,第一个结点____前驱结点,其余每个结点有且只有______个前驱结点；最后一个结点______后续结点,其余每个结点有且只有_______个后续结点。 3.在树形结构中,树根结点没有_______结点,其余每个结点有且只有_______个前驱结点；叶子结点没有________结点,其余每个结点的后续结点可以_________。 4.在图形结构中,每个结点的前驱结点数和后续结点数可以_________。 5.线性结构中元素之间存在________关系,树形结构中元素之间存在______关系,图形结构中元素之间存在_______关系。 6.算法的五个重要特性是_______、_______、______、_______、_______。 7.数据结构的三要素是指______、_______和________。 8.链式存储结构与顺序存储结构相比较,主要优点是________________________________。 9.设有一批数据元素,为了最快的存储某元素,数据结构宜用_________结构,为了方便插入一个元素,数据结构宜用____________结构。 四、算法分析题 1.求下列算法段的语句频度及时间复杂度参考答案： 选择题1. C 2.C 3. C 4. A、B 5. C 6.C、B

IBM-PC汇编语言程序设计(第二版)课后习题答案(清华大学出版社)(著)答案

IBM-PC汇编语言程序设计（第二版）课后习题答案（清华大学出版社）（沈美明，温冬蝉著）答案 第三章答案1-22 1. （1）立即寻址没有 （2）直接寻址 7237H （3）使用BX的寄存器寻址没有 （4）使用BX的间接寻址 637DH （5）使用BX的寄存器相对寻址 0D5F0H (6) 基址变址寻址 8E18H (7）相对基址变址 004FH 2.根据下列要求，写出相应的汇编指令。 （1）ADD DX,BX (2) ADD AL,[BX][SI] (3) ADD [BX][0B2H], CX (4) MOV AX,2A59H ADD [0524H] ,AX (5) ADD AL ,0B5H 3. （1）寄存器间接寻址 MOV BX,OFFSET [BLOCK][0AH] MOV DX ,[BX] （2）寄存器相对寻址 MOV SI,OAH MOV DX,[BLOCK][SI] (3)基址变址寻址 MOV BX ,BLOCK MOV SI,OAH MOV DX,[BX][SI] 4. 现有（DS）=2000H, (BX)=0100H, (SI)=0002H,(20100)=12H, (20101)=34H,(20102)=56H, (20103)=78H,(21200)=2AH,(20201)=4CH,(21202)=B7H,(21203)=65H,试说明下列各条指令执行完后，AX寄存器的内容。 (1）MOV AX,1200H 1200H (2) MOV AX,BX 0100H

(3) MOV AX,[1200] 4C2AH 注意，是字单元！！ （4）MOV AX,[BX] 同上 （5）MOV 1100[BX] 4C2AH (6) MOV AX,[BX][SI] 7856H (7) MOV AX,1100[BX][SI] 65B7H 5.（1） 7CD9H (2) 1200H (3) 6319H 6. MOV BX,2000H LES DI ,[BX] MOV AX, ES：DI 7.转向地址OBJ的值分别为：（1）064DH (2)0691H (3)05E0H 注意有符号数的符号位 8.（1） MOV AX,0ABH 立即数寻址无物理地址 （2） MOV AX,BX 寄存器寻址同上 （3） MOV AX,[100] 直接寻址 20100H (4） MOV AX,VAL 直接寻址 20050H (5) MOV AX,[BX] 寄存器间接寻址 20100H (6) MOV AX,ES：[BX] 直接寻址 21100H (7) MOV AX,[BP] 寄存器间接寻址 20010H （8）MOV AX,[SI] 同上 200A0H (9) MOV AX,[BX+10] 寄存器相对寻址 20110H （10）MOV AX,VAL[BX] 同上 20150H (11) MOV AX,[BX][SI] 基址变址寻址 201A0H (12) MOV AX,VAL[BX][SI] 相对基相变址寻址 201F0H 9.（1）的指令： MOV AX, [BX][0CH] MOV ZREO ,AX (2) 的指令： MOV AX,ARRAY[BX] MOV ZREO,AX 10. MOV AX,TABLE 是把符号地址TABLE里的内容送到AX里，指令执行完后，(AX)=1234H LEA AX,TABLE 是把符号地址TABLE 的有效地址（这里是偏移量）送到指定寄存器AX里，指令执行完后，（AX）=0032H 11. 执行完指令后，（AX）=1E00H 12. LEA AX,CSTRING MOV DL,AX MOV DH,[AX+6] 13. 这参考课本P51--P53 14．LES BX,[2000]

数据结构复习题集答案(c语言版严蔚敏)

人生难得几回搏，此时不搏更待何时？ 第1章绪论 1.1 简述下列术语：数据 数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型 解：数据是对客观事物的符号表示 在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称 数据元素是数据的基本单位 在计算机程序常作为一个整体进行考虑和处理 数据对象是性质相同的数据元素的集合 是数据的一个子集 数据结构是相互之间存在一种或多种特定关系的数据元素的集合 存储结构是数据结构在计算机中的表示 数据类型是一个值的集合和定义在这个值集上的一组操作的总称 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作 是对一般数据类型的扩展 1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别 解：抽象数据类型包含一般数据类型的概念 但含义比一般数据类型更广、更抽象 一般数据类型由具体语言系统部定义 直接提供给编程者定义用户数据 因此称它们为预定义数据类型 抽象数据类型通常由编程者定义 包括定义它所使用的数据和在这些数据上所进行的操作 在定义抽象数据类型中的数据部分和操作部分时 要求只定义到数据的逻辑结构和操作说明 不考虑数据的存储结构和操作的具体实现 这样抽象层次更高 更能为其他用户提供良好的使用接口 1.3 设有数据结构(D R) 其中

试按图论中图的画法惯例画出其逻辑结构图 解： 1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数） 解： ADT Complex{ 数据对象：D={r i|r i为实数} 数据关系：R={} 基本操作： InitComplex(&C re im) 操作结果：构造一个复数C 其实部和虚部分别为re和im DestroyCmoplex(&C) 操作结果：销毁复数C Get(C k &e) 操作结果：用e返回复数C的第k元的值 Put(&C k e) 操作结果：改变复数C的第k元的值为e IsAscending(C) 操作结果：如果复数C的两个元素按升序排列 则返回1 否则返回0 IsDescending(C) 操作结果：如果复数C的两个元素按降序排列 则返回1 否则返回0 Max(C &e) 操作结果：用e返回复数C的两个元素中值较大的一个 Min(C &e) 操作结果：用e返回复数C的两个元素中值较小的一个

汇编语言

武汉理工大学华夏学院课程设计报告书 课程名称：汇编语言课程设计 题目：在屏幕上显示变换的图形 系名：信息工程系 专业班级：软件工程1131 姓名： 学号： 102128131 指导教师:李捷 2015 年 1 月 9 日

课程设计任务书 学生姓名： 专业班级： 软件1131 指导教师： 李捷 工作单位： 信息工程系 设计题目：在显示器上显示对称图1、图2 初始条件： PC 机上实现课程设计 要求完成的主要任务： 主要任务：（在规定的时间内完成下列任务） 1. 按”Esc ”退出程序；能有2种图形显示,2种色彩方案(见上图) 2. 按“1 , 2” 黑白----------显示图形1，图形2 3. 按“3 , 4”色彩方案1---显示图形1，图形2（颜色自定） 4. 按“5 , 6”色彩方案2---显示图形1，图形2（颜色自定）+ 时间安排： 设计报告撰写格式要求：（按提供的设计报告统一格式撰写） 1、 题目：在显示器上显示有色彩变换的数字对称图 2、设计目的：在课程设计实验中，利用顺序结构、循环结构和主、子程序的调用，更进 一步的学习和掌握汇编语言课程设计。 2、设计内容：写出简要的程序功能描述、程序运行条件--所需工具软件、输入/输出描述等。 3、程序结构：① 主要的段定义说明； ② 用到的子程序（宏）的功能说明、调用关系说明、参数传送方式说明等； ③ 主要算法描述等（各模块功能实现及典型指令的应用）。 4、设计步骤（注明时间安排） 5、程序流程图、源程序（程序必须有简单注释，源程序若太长，可作为附录） 6、实验结果（输出） 7、其他值得说明的内容（1）程序结构设计特点；（2）设计、调试程序心得、体会或不足。 附录：①源程序代码（必须有简单注释） ②参考文献 指 导 教 师 签 字： 2015年 1 月1日 系 主 任 签 字： 年 月 日

数据结构习题及答案——严蔚敏

第一章绪论 一、选择题 1.组成数据的基本单位是（） （A）数据项（B）数据类型（C）数据元素（D）数据变量 2.数据结构是研究数据的（）以及它们之间的相互关系。 （A）理想结构，物理结构（B）理想结构，抽象结构 （C）物理结构，逻辑结构（D）抽象结构，逻辑结构 3.在数据结构中，从逻辑上可以把数据结构分成（） （A）动态结构和静态结构（B）紧凑结构和非紧凑结构 （C）线性结构和非线性结构（D）内部结构和外部结构 4.数据结构是一门研究非数值计算的程序设计问题中计算机的（①）以及它们之间的（②）和运算等的学科。 ① （A）数据元素（B）计算方法（C）逻辑存储（D）数据映像 ② （A）结构（B）关系（C）运算（D）算法 5.算法分析的目的是（）。 （A）找出数据结构的合理性（B）研究算法中的输入和输出的关系 （C）分析算法的效率以求改进（D）分析算法的易懂性和文档性 6.计算机算法指的是（①）,它必须具备输入、输出和（②）等5 个特性。 ① （A）计算方法（B）排序方法（C）解决问题的有限运算序列（D）调度方法

② （A）可执行性、可移植性和可扩充性（B）可行性、确定性和有穷性 （C）确定性、有穷性和稳定性（D）易读性、稳定性和安全性 二、判断题 1.数据的机内表示称为数据的存储结构。（） 2.算法就是程序。（） 3.数据元素是数据的最小单位。（） 4.算法的五个特性为：有穷性、输入、输出、完成性和确定性。（） 5.算法的时间复杂度取决于问题的规模和待处理数据的初态。（） 三、填空题 1.数据逻辑结构包括________、________、_________ 和_________四种类型,其中树形结构和图形结构合称为_____。 2.在线性结构中,第一个结点____前驱结点,其余每个结点有且只有______个前驱结点；最后一个结点______后续结点,其余每个结点有且只有_______个后续结点。 3.在树形结构中,树根结点没有_______结点,其余每个结点有且只 有_______个前驱结点；叶子结点没有________结点,其余每个结点的后续结点可以_________。 4.在图形结构中,每个结点的前驱结点数和后续结点数可以 _________。 5.线性结构中元素之间存在________关系,树形结构中元素之间存 在______关系,图形结构中元素之间存在_______关系。 6.算法的五个重要特性是_______、_______、______、_______、

80X86汇编语言程序设计教程+课后习题答案(清华大学版)

第二章答案 Tarzan 版 题2.1 8086/8088通用寄存器的通用性表现在何处？8个通用寄存器各自有何专门用途？哪些 寄存器可作为存储器寻址方式的指针寄存器？ 答：8086/8088通用寄存器的通用性表现在： 这些寄存器除了各自规定的专门用途外，他们均可以用于传送和暂存数据，可以保存 算术逻辑运算中的操作数和运算结果； 8个通用寄存器的专门用途如下： AX 字乘法，字除法，字I/O BX 存储器指针 CX 串操作或循环控制中的计数器 DX 字乘法，字除法，间接I/O SI 存储器指针（串操作中的源指针） DI 存储器指针（串操作中的目的指针） BP 存储器指针（存取堆栈的指针） SP 堆栈指针 其中BX，SI，DI，BP可作为存储器寻址方式的指针寄存器 题2.2 从程序员的角度看，8086/8088有多少个可访问的16位寄存器？有多少个可访问的8位 寄存器？ 答：从程序员的角度看，8086/8088有14个可访问的16位寄存器；有8个可访问的8位寄存器； 题2.3 寄存器AX与寄存器AH和AL的关系如何？请写出如下程序片段中每条指令执行后寄存器 AX的内容： MOV AX,1234H MOV AL,98H MOV AH,76H ADD AL,81H SUB AL,35H

ADD AL,AH ADC AH,AL ADD AX,0D2H SUB AX,0FFH 答： MOV AX,1234H AX=1234H MOV AL,98H AX=1298H MOV AH,76H AX=7698H ADD AL,81H AX=7619H SUB AL,35H AX=76E4H ADD AL,AH AX=765AH ADC AH,AL AX=D15AH ADD AX,0D2H AX=D22CH SUB AX,0FFH AX=D12DH 题2.4 8086/8088标志寄存器中定义了哪些标志？这些标志可分为哪两类？如何改变这些标志 的状态？ 答： 8086/8088标志寄存器中定义了9个标志，如下： CF: Carry Flag ZF: Zero Flag SF: Sign Flag OF: Overflow Flag PF: Parity Flag AF: Auxiliary Carry Flag DF: Direction Flag IF: Interrupt-enable Flag TF: Trap Flag 这些标志可分为两类，分别为： 1、运算结果标志； 2、状态控制标志； 采用指令SAHF可把AH中的指定位送至标志寄存器低8位SF、ZF、AF、PF、CF； 采用CLC可清除CF，置CF到0 采用STC可置CF到1 采用CLD可置DF到0 采用sTD可置DF到1

运筹学教程清华第三版课后答案(第一章,第五章部分)

1.某饲养场饲养动物出售，设每头动物每天至少需700g蛋白质、30g矿物质、100mg 维生素。现有五种饲料可供选用，各种饲料每kg营养成分含量及单价如表1所示。表1 要求确定既满足动物生长的营养需要，又使费用最省的选用饲料的方案。 x表示满足动物生长的营养需要时，解：设总费用为Z。i=1,2,3,4,5代表5种饲料。 i 第i种饲料所需的数量。则有： 2.某医院护士值班班次、每班工作时间及各班所需护士数如表2所示。每班护士值班 开始时间向病房报道，试决定： （1）若护士上班后连续工作8h，该医院最少需要多少名护士，以满足轮班需要； （2）若除22:00上班的护士连续工作8h外（取消第6班），其他班次护士由医院排定上1～4班的其中两个班，则该医院又需要多少名护士满足轮班需要。表2 x第i班开始上班的人数，i=1,2,3,4,5,6 解：（1）设 i x第i 解：（2）在题设情况下，可知第五班一定要30个人才能满足轮班需要。则设设 i 班开始上班的人数，i=1,2,3,4。

a 3.要在长度为l的一根圆钢上截取不同长度的零件毛坯，毛坯长度有n种，分别为 j （j=1,2，…n）。问每种毛坯应当截取多少根，才能使圆钢残料最少，试建立本问题的数学模型。 解：设 x表示各种毛坯的数量，i=1,2,…n。 i 4.一艘货轮分前、中、后三个舱位，它们的与最大允许载重量如表3.1所示。现有三 种货物待运，已知有相关数据列于表3.2。 表3.1 表3.2 又为了航海安全，前、中、后舱实际载重量大体保持各舱最大允许载重量的比例关系。具体要求：前、后舱分别与中舱之间载重量比例的偏差不超过15%，前、后舱之间不超过10%。问该货轮应该载A,B,C各多少件运费收入才最大？试建立这个问题的线性规划模型。 x表示第i件商品在舱j的装载量，i,j=1,2,3 解：设 ij 1)商品的数量约束： 2)商品的容积约束： 3)最大载重量约束： 4)重量比例偏差的约束： 5.篮球队需要选择5名队员组成出场阵容参加比赛。8名队员的身高及擅长位置见表 5. 表5

清华大学c语言教程课后答案

c语言程序设计答案---潭2 《C语言程序设计教程(第二版)》习题答案 说明 1. 本习题答案是我自己做的，错误和疏漏在所难免。编程题全部调试通过，但选择题和填空题不敢保证全对。 2. 凡未指明解题所用的程序设计语言的，均指C语言。 3. 凡未指明执行程序所需的操作系统的，均可在DOS下执行。 4. 本文中文字下面划线的表示输入。 第1章程序设计基础知识 一、单项选择题(第23页) 1-4.CBBC 5-8.DACA 二、填空题(第24页) 1.判断条件 2.面向过程编程 3.结构化 4.程序 5.面向对象的程序设计语言 7.有穷性 8.直到型循环 9.算法 10.可读性 11.模块化 12.对问题的分析和模块的划分 三、应用题(第24页) 2.源程序： main() {int i,j,k; /* i:公鸡数,j:母鸡数,k:小鸡数的1/3 */ printf("cock hen chick "); for(i=1;i<=20;i++) for(j=1;j<=33;j++) for(k=1;k<=33;k++) if (i+j+k*3==100&&i*5+j*3+k==100) printf(" %d %d %d ",i,j,k*3);} 执行结果： cock hen chick 4 18 78 8 11 81 12 4 84 3.现计算斐波那契数列的前20项。 递推法源程序： main() {long a,b;int i; a=b=1; for(i=1;i<=10;i++) /*要计算前30项,把10改为15。*/ {printf("%8ld%8ld",a,b); a=a+b;b=b+a;}} 递归法源程序： main() {int i;

汇编语言(沈美明,温冬婵)课后答案

汇编语言程序设计（第二版） （清华大学IBM-PC 汇编语言程序设计（第二版）沈美明温冬婵编著） 第二章 1、答：直接由指令指定的I/O端口数为256个。 2、答： 3、答：字节单元：（30022H）= AB H，（30024H）= EF H 字单元：（30021H）= AB34 H，（30022H）= CDAB H。 4、答：3017：000A的存储单元的物理地址是3017AH， 3015：002A的存储单元的物理地址是3017AH， 3010：007A的存储单元的物理地址是3017AH。 5、答：该程序的第一个字的物理地址是0AAA40H。 6、答：条件标志OF、SF、ZF、CF的值依次分别为0、0、0、0。 7、答：(1)AX、BX、CX、DX、AH、AL、BH、BL、CH、CL、DH、DL、 SP、BP、DI、SI（注意：学生尽量不要用SP参与加减运算） (2)CX (3)DX、AX、AH、AL (4)CS、DS、ES、SS (5)FLAGS (6)IP (7)SS、SP、BP 8、答：可以用来指示存储器地址的寄存器有BX、SP、BP、DI、SI、IP、CS、DS、 ES、SS。 9、答：唯一正确的是D。 第三章 2、答： （1）ADD DX, BX （2）ADD AL, [BX][SI] （3）ADD [BX+0B2H], CX （4）ADD [0524H], 2A59H （5）ADD AL, 0B5H 3、答： （1）MOV BX, OFFSET BLOCK + 0AH MOV DX, [BX] （2）MOV BX, 0AH MOV DX, BLOCK[BX] （3）MOV BX, OFFSET BLOCK MOV SI, 0AH MOV DX, [BX][SI]

清华_第三版_运筹学教程_课后答案~(_第一章_第五章部分)

清华第三版 运筹学 答案[键入文字] [键入文字] [键入文字] 运筹学教程 1. 某饲养场饲养动物出售，设每头动物每天至少需700g 蛋白质、30g 矿物质、100mg 维生素。现有五种饲料可供选用，各种饲料每kg 营养成分含量及单价如表1所示。 表1 要求确定既满足动物生长的营养需要，又使费用最省的选用饲料的方案。 解：设总费用为Z 。i=1,2,3,4,5代表5种饲料。i x 表示满足动物生长的营养需要时，第i 种饲料所需的数量。则有： ????? ? ?=≥≥++++≥++++≥++++++++=5,4,3,2,1,01008.022.05.0305.022.05.07008623..8.03.04.07.02.0min 54321543215432154321i x x x x x x x x x x x x x x x x t s x x x x x Z i 2. 某医院护士值班班次、每班工作时间及各班所需护士数如表2所示。每班护士值班 开始时间向病房报道，试决定： （1） 若护士上班后连续工作8h ，该医院最少需要多少名护士，以满足轮班需要； （2） 若除22:00上班的护士连续工作8h 外（取消第6班），其他班次护士由医院 排定上1～4班的其中两个班，则该医院又需要多少名护士满足轮班需要。 表2

6 2:00～6:00 30 解：（1）设x 第i 班开始上班的人数，i=1,2,3,4,5,6 ???????????=≥≥+≥+≥+≥+≥+≥++++++=且为整数 6,5,4,3,2,1,030 2050607060..min 655443 322161 654321i x x x x x x x x x x x x x t s x x x x x x Z i 解：（2）在题设情况下，可知第五班一定要30个人才能满足轮班需要。则设设i x 第i 班开始上班的人数，i=1,2,3,4。 ??? ????? ?? ??? ??=≥=+++=≥+++=+++=≥+++=+++=≥+++=+++=≥+++++++=4 ,3,2,1,1002 1502 16021702 ,160..30 min i 444342414444433422411434 33323133 443333223113242322212244233222211214131211114413312211114321j i y x y y y y y x y x y x y x y y y y y y x y x y x y x y y y y y y x y x y x y x y y y y y y x y x y x y x y t s x x x x Z ij 变量，—是，，，第四班约束，，第三班约束，，第二班约束，第一班约束 3. 要在长度为l 的一根圆钢上截取不同长度的零件毛坯，毛坯长度有n 种，分别为j a （j=1,2，…n ）。问每种毛坯应当截取多少根，才能使圆钢残料最少，试建立本问题的数学模型。 解：设i x 表示各种毛坯的数量，i=1,2,…n 。

清华数据结构习题集答案(C语言版严蔚敏)

清华数据结构习题集答案(C语言版严蔚敏) 第1章绪论 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。

抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。 设有数据结构(D,R)，其中 {}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r = 试按图论中图的画法惯例画出其逻辑结构图。 解：

试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。 解： ADT Complex{ 数据对象：D={r,i|r,i为实数} 数据关系：R={} 基本操作： InitComplex(&C,re,im) 操作结果：构造一个复数C，其实部和虚部分别为re 和im DestroyCmoplex(&C) 操作结果：销毁复数C

《汇编语言》学习笔记(清华大学 王爽)

清华大学《汇编语言》（王爽）读书笔记 第一章基础知识 ◎汇编语言由3类指令组成 汇编指令：机器码的助记符，有对应机器码。 伪指令：没有对应机器码，由编译器执行，计算机并不执行 其他符号：如+-*/，由编译器识别，没有对应机器码 ◎一个CPU有n根地址线，则可以所这个CPU的地址线宽度为n，这样的CPU最多可以寻找2的n 次方个内存单元。 ◎ 1K=2^10B 1M=2^20B 1G=2^30B ◎8086 CPU地址总线宽度为20，寻址范围为00000~FFFFF 00000~9FFFF 主存储器地址空间(RAM) A0000~BFFFF 显存地址空间 C0000~FFFFF 各类ROM地址空间 第二章寄存器（CPU工作原理） ◎16位结构描述了一个CPU具有下面几个方面的结构特性 运算器一次最多可以处理16位的数据 寄存器的最大宽度为16位 寄存器和运算器之间的通路为16位 ◎8086有20位地址总线，可以传送20位地址，达到1M的寻址能力。采用在内部用两个16位地址合成的方法来形成一个20位的物理地址 ◎物理地址 = 段地址 × 16 + 偏移地址 ◎在编程是可以根据需要，将若干地址连续的内存单元看作一个段，用段地址×16定位段的起始地址（基础地址），用偏移地址定位段中的内存单元。段地址×16必然是16的倍数，所以一个段的起始地址也一定是16的倍数；偏移地址位16位，16位地址的寻址能力为64KB，所以一个段的长度最大为64KB ◎8086有四个段寄存器 CS、DS、SS、ES ◎CS为代码段寄存器，IP为指令指针寄存器。任意时刻，设CS中内容为M、IP中内容为N，8086CPU从内存M×16+N读取一条指令执行 ◎不能用mov修改CS、IP，因为8086CPU没有提供这样功能，可用指令JMP 段地址:偏移地址。JMP 2AE3:3 JMP AX 修改IP 第三章寄存器（内存访问） ◎DS数据段寄存器。不能将数据直接送入段寄存器，所以『MOV DS, 1』不正确 ◎字在存储时要两个连续的内存单元，低位在低地址，高位在高地址 ◎[address]表示一个偏移地址为address的内存单元 ◎SS:SP指向栈顶元素 ◎PUSH AX：（1）SP = SP - 2；（2）AX送入SS:SP ◎POP AX：（1）SS:SP送入AX；（2）SP = SP + 2 ◎PUSH/POP 寄存器 PUSH/POP 段寄存器 PUSH/POP 内存单元 第四章第1个程序 ◎可执行文件包含两部分：程序和数据，相关的描述信息 ◎程序加载后， ds中存放这程序所在内存区的段地址，这个内存区的偏移地址为0，策程序所在的内存区的地址为ds:0；这个内存区的前256个字节中存放的是PSP，dos用来和程序进行通信。从256字节处向后的空间存放的是程序。 第五章 [BX]和loop指令 ◎[BX]表示一个内存单元，它的段地址在ds中，偏移地址在bx中。MOV AX,[BX] MOV AL,[BX]

运筹学教程 清华 第三版 课后答案( 第一章,第五章部分)

1. 某饲养场饲养动物出售，设每头动物每天至少需700g 蛋白质、30g 矿物质、100mg 维生素。现有五种饲料可供选用，各种饲料每kg 营养成分含量及单价如表1所示。 表1 要求确定既满足动物生长的营养需要，又使费用最省的选用饲料的方案。 解：设总费用为Z 。i=1,2,3,4,5代表5种饲料。i x 表示满足动物生长的营养需要时，第i 种饲料所需的数量。则有： ????? ? ?=≥≥++++≥++++≥++++++++=5,4,3,2,1,01008.022.05.0305.022.05.07008623..8.03.04.07.02.0min 54321543215432154321i x x x x x x x x x x x x x x x x t s x x x x x Z i 2. 某医院护士值班班次、每班工作时间及各班所需护士数如表2所示。每班护士值班 开始时间向病房报道，试决定： （1） 若护士上班后连续工作8h ，该医院最少需要多少名护士，以满足轮班需要； （2） 若除22:00上班的护士连续工作8h 外（取消第6班），其他班次护士由医院 排定上1～4班的其中两个班，则该医院又需要多少名护士满足轮班需要。 表2

解：（1）设x 第i 班开始上班的人数，i=1,2,3,4,5,6 ???????????=≥≥+≥+≥+≥+≥+≥++++++=且为整数 6,5,4,3,2,1,030 2050607060..min 655443 322161 654321i x x x x x x x x x x x x x t s x x x x x x Z i 解：（2）在题设情况下，可知第五班一定要30个人才能满足轮班需要。则设设i x 第i 班开始上班的人数，i=1,2,3,4。 ??? ????? ?? ??? ??=≥=+++=≥+++=+++=≥+++=+++=≥+++=+++=≥+++++++=4 ,3,2,1,1002 1502 16021702 ,160..30 min i 444342414444433422411434 33323133 443333223113242322212244233222211214131211114413312211114321j i y x y y y y y x y x y x y x y y y y y y x y x y x y x y y y y y y x y x y x y x y y y y y y x y x y x y x y t s x x x x Z ij 变量，—是，，，第四班约束，，第三班约束，，第二班约束，第一班约束 3. 要在长度为l 的一根圆钢上截取不同长度的零件毛坯，毛坯长度有n 种，分别为j a （j=1,2，…n ）。问每种毛坯应当截取多少根，才能使圆钢残料最少，试建立本问题的数学模型。 解：设i x 表示各种毛坯的数量，i=1,2,…n 。 ?????≤= ∑∑==是整数i 1 1 1max x x a x a Z i i n i i i n i

严蔚敏《数据结构(c语言版)习题集》答案第四章串

《一定能摸到红球吗？》说课稿 林银花 一、教材说明： １、课题：《一定能摸到红球吗？》 ２、本节内容的地位和作用 在现代社会中，人们面临着更多的机会和选择，常常需要在不确定情境中作出合理的决策,概率正是通过对不确定现象和事件发生的可能性的刻画,来为人们更好的制定决策提供依据和建议.本节内容又是义务教育阶段,唯一培养学生从不确定的角度来观察世界的数学内容,让学生了解可能性是普遍的,有助于他们理解社会,适应生活. ３、教学目标设计： (１)认知目标： （Ａ）经历猜测．实验．收集与分析试验结果等过程 （Ｂ）体会事件的发生的不确定性知道事情发生的可能性有多大。 （２）、能力目标： (Ａ)经历游戏等的活动过程，初步认识确定事件和不确定事件 （Ｂ）在与其它人交流的过程中，能合理清晰地表达自己的思维过程； （３）、情感目标： （Ａ）通过创设游戏情境，让学生主动参与，做“数学实验”，激发学生学习的热情和兴趣，激活学生思维。 （Ｂ）在与他人的合作过程中，增强互相帮助、团结协作的精神。 （Ｃ）体会到在生活中我们可以从确定和不确定两方面分析一件事情. ４、本课重点、难点分析： 学习的重点是初步体验事情发生的确定性和不确定性. 学习的难点是确定事件发生的可能性大小. 学习本节知识应注意猜测,试验,收集与分析实验结果,从中体会事件发生的可能性及大小. 二、教学对象分析： 1、初一学生性格开朗活泼，对新鲜事物特别敏感，且较易接受，因此，教学过程中创设的问题情境应较生动活泼，直观形象，且贴近学生的生活，从而引起学生的有意注意。 2、初一学生的概括能力较弱，推理能力还有待不断发展，所以在教学时，可让学生充分试验,收集，分析,帮助他们直观形象地感知。 3、初一学生已经具备了一定的学习能力，所以本节课中，应多为学生创造自主学习、