搜档网
当前位置:搜档网 › 数据结构课后习题详解(超完整,超经典)

数据结构课后习题详解(超完整,超经典)

数据结构课后习题详解(超完整,超经典)
数据结构课后习题详解(超完整,超经典)

第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 ,假设现实计算机可连续

运算的时间为710秒(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

223n n n f +=,()()52n 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

--=+=∑x x

x n n

i i

()0,1≥≠n x

(3)

122

11

-=∑=-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

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的算法。

解:

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

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

(完整版)5数据完整性课后习题

习题 一、选择题 1.一个表上可以建立多个名称不同、类型各异的触发器,每个触发器可以由三个动作来引发,但是每个触发器最多只能作用于()个表上。 A.一 B.二 C.三 D.四 2.激活触发器的数据修改语句,有效选项是()。 A.INSERT B.UPDATE C.DELETE D.SELECT 3.创建触发器不需要指定的选项有()。 A.触发器的名称 B.在其上定义触发器的表 C.触发器将何时触发 D.执行触发操作的编程语句 4.当希望执行对Book表的操作时,如果该操作不执行,而是执行对PRICE 表的更新操作,则应该创建什么类型的DML 触发器()。 A.FOR B.BEFORE C.AFTER D.INSTEAD OF 5.在DML触发器工作中,有可能生成的两个内存表是()。 A.INSERTED, DELETED B.UPDATED, INSERTED C.DELETED,ADDED D.ADDED, DELETED 6.关于触发器叙述正确的是()。 A.触发器是自动执行的,可以在一定条件下触发 B.触发器不可以同步数据库的相关表进行级联更改 C.SQL Server 2008不支持DDL触发器 D.触发器不属于存储过程 7.关于约束叙述正确的是()。 A.每个约束只能作用与一个列上 B.每个约束可以作用多个列,但是必须在一个表里 C.每个约束可以作用到多个表的多个列 D.以上都不对 8.用户定义的约束,是属于()完整性。 A.用户自定义 B.实体

C.参照 D.都不是 9.下述SQL命令的短语中,定义属性上约束条件的是()。 A.NOT NULL短语 B.UNIQUE短语 C.CHECK短语 D.HA VING短语 10.下列()是对触发器的描述 A.定义了一个有相关列和行的集合 B.当用户修改数据时,一种特殊形式的存储过程被自动执行 C.SQL语句的预编译集合 D.它根据一或多列的值,提供对数据库表的行的快速访问 二、填空题 1.数据库的实体完整性要求表中所有行唯一,可通过建主码、唯一约束、唯一索引、IDENTITY标识等约束来实现。 2.数据库域完整性可保证表中指定字段中数据的正确性。要求表中指定列的数据具有正确的数据类型、格式和有效取植范围。 3.关系完整性包括实体完整性、值域完整性、参照完整性_和用户自定义完整性。4.当指定基本表中某一列或若干列为主码时,则系统将在这些列上自动建立一个非空_______、_唯一__约束和___聚集__的索引。 5. SQL Server 2008中的触发器可以分为_DML_触发器和__DDL__触发器两种。 6.在SQL Server中,通过执行 CRETAE RULE 语句创建约束,使用 SP_bindrule 存储过程绑定约束,使用 SP_unbindrule 解除绑定,使用 DROP RULE 删除规则。 7.数据库的完整性是指数据的___正确性_____ 和___相容性_____。 8.数据库完整性的定义一般由SQL的___ DDL _____语句来实现。它们作为数据库模式的一部分存入数据字典中。 9.触发器按激活的方式分为After 和Instead Of 两种触发方式。后触发器在记录已经改变完之后被激活。替代触发器在记录变更之前被激活。 10.创建触发器使用 CRETAE TRIGGER 语句。在表或视图上执行INSERT 、UPDATE 和DELETE 语句可以激活触发器。 11.SQL Server为每一个触发器创建了两个inserted 和deleted 临时表。在触发器触发时时候创建,在触发器的工作完成之后时候删除。 三、问答题 1.试述关系模型的完整性规则。在参照完整性中,为什么外码属性的值也可以为空?什么情况下才可以为空? 解答: 关系模型的完整性规则是对关系的某种约束条件。关系模型中可以有三类完整性约束:实体完整性、参照完整性和用户定义的完整性。其中实体完整性和参照完整性是关系模型必须满足的完整性约束条件,被称作是关系的两个不变性,应该由关系系统自动支持。1) 实体完整性规则:若属性A是基本关系R的主属性,则属性A不能取空值。2)参照完整性规则:若属性(或属性组)F是基本关系R的外码,它与基本关系S的主码Ks相对应(基本关系R和S不一定是不同的关系),则对于R中每个元组在F上的值必须为:等于S中某个元组的主码值或者取空值(F的每个属性值均为空值);3)用户定义的完整性是针对某一具体关系数据库的约束条件。它反映某一具体应用所涉及的数据必须满足的语义要求。在

课后作业完成题库1、4、7、8、9、10、12、25题

课后作业:完成题库1、4、7、8、9、10、12、25题 01利润的概述 02所得税费用 利润是指企业在一定会计期间的经营成果。利润包括收入减去费用后的净额、直接计入当期利润的利得和损失等。 2.利润的构成 ①营业利润=营业收入-营业成本-税金及附加-销售费用-管理费用-财务费用+投资收益(减损失)+公允价值变动收益(减损失)-资产减值损失+其他收益 ②利润总额=营业利润+营业外收入-营业外支出 ③净利润=利润总额-所得税费用 习题解惑 【例题?单选题】下列各项中,影响当期营业利润的是()。 A.处置固定资产净损益 B.自然灾害导致原材料净损失 C.支付委托代销商品的手续费 D.溢价发行股票支付的发行费用 【答案】C 【解析】选项A计入营业外收支,选项B计入营业外支出,选项D冲减资本公积。 【例题?多选题】下列各项中,既影响营业利润又影响利润总额的业务有()。 A.计提坏账准备计入资产减值损失科目中 B.转销确实无法支付的应付账款 C.出售单独计价包装物取得的收入 D.转让股票所得收益计入投资收益 【答案】ACD 【解析】选项B,计入营业外收入,不影响营业利润。 营业外收支的账务处理 (一)营业外收入账务处理 1.处置非流动资产利得

处置固定资产通过“固定资产清理”科目核算,其账户余额转入营业外收入或营业外支出; 2.确认盘盈利得、捐赠利得 盘盈利得应通过“待处理财产损溢”科目核算 【例题?计算题】某企业将固定资产报废清理的净收益8000元转作营业外收入 写出会计分录。 【答案】 借:固定资产清理8000 贷:营业外收入-非流动资产处置利得8000 习题解惑 【例题?计算题】某企业在现金清查中盘盈200元,按管理权限报经批准后转入营业外收入。写出下列情况时的会计录: ①发现盘盈时: ②经批准转入营业外收入时: 【答案】 ①发现盘盈时: 借:库存现金200 贷:待处理财产损溢200 ②经批准转入营业外收入时: 借:待处理财产损溢200 贷:营业外收入200 【例题?多选题】下列各项中应计入营业外收入的有()。 A.出售持有至到期投资的净收益 B.无法查明原因的现金溢余 C.出售无形资产的净收益 D.出售投资性房地产的净收益 【答案】BC 【解析】选项A,计入投资收益;选项D,计入其他业务收入。 【例题?单选题】下列各项中,不应计入营业外收入的是()。 A.债务重组利得 B.处置固定资产净收益 C.收发差错造成存货盘盈 D.确实无法支付的应付账款 【答案】C 【解析】存货盘盈冲减管理费用。 所得税费用 (一)所得税费用的构成 所得税费用是指企业确认的应从当期利润总额中扣除的所得税费用。包括当期所得税和递延所得税两部分。

党员干部十九党知识考试试题及答案

党员干部十九党知识考试试题及答案 一、单选题 中国共产党第十九次全国代表大会召开时间(A) A、年月日 B、年月日 C、年日 北京时间年月日-月日,中国共产党第十九次全国代表大会在北京召开 中国共产党第十九次全国代表大会,是在全面建成小康社会决胜阶段、中国特色社会主义进入_____的关键时期召开的一次十分重要的大会。 A、新时期 B、新阶段 C、新征程 D、新时代 答案D 十九大的主题是不忘初心,____,高举中国特色社会主义伟大旗帜,决胜全面建成小康社会,夺取新时代中国特色社会主义伟大胜利,为实现中华民族伟大复兴的中国梦不懈奋斗。 A、继续前进 B、牢记使命 C、方得始终 D、砥砺前行 答案B 中国共产党人的初心和使命,就是为中国人民____ ,为中华民族____。这个初心和使命是激励中国共产党人不断前进的根本动力。 A、谋幸福,谋未来 B、谋生活,谋复兴 C、谋幸福,谋复兴 D、谋生活,谋未来 答案C 五年来,我们统筹推进____总体布局、协调推进____战略布局,十二五规划胜利完成,十三五规划顺利实施,党和国家事业全面开创新局面。

A、五位一体四个全面 B、四位一体五个全面 C、五个全面四位一体 D、四个全面五位一体 答案A 过去五年,经济保持中高速增长,在世界主要国家中名列前茅,国内生产总值从五十四万亿元增长到____万亿元,稳居世界第二,对世界经济增长贡献率超过百分之三十。 A、六十 B、七十 C、八十 D、九十 答案C 脱贫攻坚战取得决定性进展,____贫困人口稳定脱贫,贫困发生率从百分之十点二下降到百分之四以下。 A、六千多万 B、七千多万 C、八千多万 D、九千多万 答案A 实施共建一带一路倡议,发起创办亚洲基础设施投资银行,设立丝路基金,举办首届一带一路国际合作高峰论坛、亚太经合组织领导人非正式会议、二十国集团领导人____峰会、金砖国家领导人____会晤、亚信峰会。 A、北京南京 B、杭州厦门 C、南京北京 D、厦门杭州 答案B 坚持反腐败无禁区、全覆盖、零容忍,坚定不移打虎、拍蝇、猎狐,____的目标初步实现,____的笼子越扎越牢,____的堤坝正在构筑,反腐败斗争压倒性态势已经形成并巩固发展。 A、不敢腐不能腐不想腐 B、不能腐不敢腐不想腐

中华人民共和国城乡规划法试卷一含答案

《中华人民共和国城乡规划法》测试卷一 一、填空题 1、城市规划、镇规划分为和。详细规划分为和。 【答案】总体规划,详细规划,控制性规划,修建性详细规划 2、城市总体规划、镇总体规划以及乡规划和村庄规划的编制,应当依据和,并与相衔接。 【答案】国民经济,社会发展规划,土地利用总体规划 3、根据本地农村经济社会发展水平,按照、的原则,确定应当制定、的区域。 【答案】县级以上地方人民政府,因地制宜、切实可行,乡规划、村庄规划 4、任何单位和个人都应当遵守经依法批准并公布的城乡规划,服从规划管理,并就涉及其的建设活动是否符合规划的要求向城乡规划主管部门查询。 【答案】有权,利害关系 5、在规划区内进行建设活动,应当遵守、和等法律、法规的规定。 【答案】土地管理,自然资源,环境保护 6、任何单位和个人都有权向城乡规划主管部门或者其他有关部门举报或者控告 的行为。城乡规划主管部门或者其他有关部门对举报或者控告,应当并组 织、。【答案】违反城乡规划,及时受理,核查、处理 7、省、自治区人民政府组织编制,报审批。 【答案】省域城镇体系规划、国务院 8、省、自治区人民政府组织编制的省域城镇体系规划,城市、县人民政府组织编制的总体规划,在报上一级人民政府审批前,应当先经审议,常务委员会组成人员的审议意见交由本级人民政府研究处理。 【答案】本级人民代表大会常务委员会 9、省域城镇体系规划的内容应当包括:和,重大基础设施的布局,为保护生态环境、资源等需要严格控制的区域。 【答案】城镇空间布局,规模控制 10、城市人民政府组织编制城市规划。【答案】总体 11、镇人民政府组织编制的镇总体规划,在报上一级人民政府审批前,应当先经,代表的审议意见交由本级人民政府研究处理。【答案】镇人民代表大会审议 12、规划的组织编制机关报送审批省域城镇体系规划、城市总体规划或者镇总体规划,应当将或者镇人民代表大会代表的审议意见和一并报送。 【答案】本级人民代表大会常务委员会组成人员,根据审议意见修改规划的情况 13、城市总体规划、镇总体规划的内容应当包括:城市、镇的发展布局,,,,禁止、限制和适宜建设的,各类专项规划等。【答案】功能分区,用地布局,综合交通体系,地域范围 14、乡规划、村庄规划的内容应当包括:规划区范围,住宅、道路、供水、排水、供电、垃圾收集、畜禽养殖场所等农村生产、生活服务设施、公益事业等各项建设的、,以及对耕地等自然资源和、防灾减灾等的具体安排。乡规划还应当包括本行政区域内的村庄发展布局。 【答案】用地布局、建设要求,历史文化遗产保护,村庄发展布局 15、城乡规划组织编制机关应当委托的单位承担城乡规划的具体编制工作。 【答案】具有相应资质等级 16、城市人民政府城乡规划主管部门根据,组织编制城市的,经本级人民政府批准后,报本级人民代表大会常务委员会和上一级人民政府备案。

数据结构(第4版)习题及实验参考答案数据结构复习资料完整版(c语言版)

数据结构基础及深入及考试 复习资料 习题及实验参考答案见附录 结论 1、数据的逻辑结构是指数据元素之间的逻辑关系。即从逻辑关系上描述数据,它与数据的存储无关,是独立于计算机的。 2、数据的物理结构亦称存储结构,是数据的逻辑结构在计算机存储器内的表示(或映像)。它依赖于计算机。存储结构可分为4大类:顺序、链式、索引、散列 3、抽象数据类型:由用户定义,用以表示应用问题的数据模型。它由基本的数据类型构成,并包括一组相关的服务(或称操作)。它与数据类型实质上是一个概念,但其特征是使用与实现分离,实行封装和信息隐蔽(独立于计算机)。 4、算法:是对特定问题求解步骤的一种描述,它是指令的有限序列,是一系列输入转换为输出的计算步骤。 5、在数据结构中,从逻辑上可以把数据结构分成( C ) A、动态结构和表态结构 B、紧凑结构和非紧凑结构 C、线性结构和非线性结构 D、内部结构和外部结构 6、算法的时间复杂度取决于( A ) A、问题的规模 B、待处理数据的初态 C、问题的规模和待处理数据的初态 线性表 1、线性表的存储结构包括顺序存储结构和链式存储结构两种。 2、表长为n的顺序存储的线性表,当在任何位置上插入或删除一个元素的概率相等时,插入一个元素所需移动元素的平均次数为( E ),删除一个元素需要移动的元素的个数为( A )。 A、(n-1)/2 B、n C、n+1 D、n-1 E、n/2 F、(n+1)/2 G、(n-2)/2 3、“线性表的逻辑顺序与存储顺序总是一致的。”这个结论是( B ) A、正确的 B、错误的 C、不一定,与具体的结构有关 4、线性表采用链式存储结构时,要求内存中可用存储单元的地址( D ) A、必须是连续的 B、部分地址必须是连续的C一定是不连续的D连续或不连续都可以 5、带头结点的单链表为空的判定条件是( B ) A、head==NULL B、head->next==NULL C、head->next=head D、head!=NULL 6、不带头结点的单链表head为空的判定条件是( A ) A、head==NULL B、head->next==NULL C、head->next=head D、head!=NULL 7、非空的循环单链表head的尾结点P满足( C ) A、p->next==NULL B、p==NULL C、p->next==head D、p==head 8、在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是( B ) A、O(1) B、O(n) C、O(n2) D、O(nlog2n) 9、在一个单链表中,若删除p所指结点的后继结点,则执行( A )

数据库课后习题及答案

数据库课后习题及答案 习题一 1.数据库处理技术经历了【人工管理、文件管理、数据库管理】以及分布式数据库管理四 个发展等段。 2.在人工管理和文件管理阶段,程序设计【依赖于】数据表示。 3.在文件管理阶段,文件之间是相互【独立】的,在数据库管理阶段,文件之间是相互【联 系】的。 4.使用数据库程序设计时,只需要告诉数据库管理系统【做什么】,而不需要告诉他【怎 么做】。 5.在【文件】系统中,数据没有独立的操作界面,在【数据】系统中,数据具有独立的操 作界面。 6.DBMS具有【安全性控制、一致性控制、并发性控制】和【数据库恢复】等管理控制功 能。 7.分布式数据库系统除了具有一般数据库系统的优点之外,还具有【系统的可靠性高、地 域范围广、数据量大、客户数多】等优点。 8.在实体中能作为码的属性称为【主属性】、否则称为【非主属性】。 9.实体之间的联系类型有三种,分别是【1对1、1对多】和【多对多】。 10.若实体A和B是1对多的联系,实体B和C是1对1的联系,则实体A和C是【1对 多】的联系。 11.若实体A和B是1对多的联系,实体B和C是1对1的联系,则实体A和C是【1对 多】的联系。 12.在非关系模型中,每个结点代表着一个【记录型】,每个父子联系代表着【1对多】联系。 13.在非关系模型中操作记录的方式是【过程】式的,在关系模型中,操作记录的方式是【集 合】式的。 14.关系中的每一行称为一个【元组】,每一列称为一个【属性】。 15.假定一个关系中由n个元组,则某个列的当前全部取值的个数最少为【1】个,最多为 【n】个。 16.关系数据库系统具有【数据结构】单一、采用【集合运算】、数据完全【独立】、【数学】 理论支持等优点。 17.在对象数据模型中,对象具有【封装】性、【继承】性、和【多态】性。 18.数据库管理系统的下层支持软件是【操作系统】、上层软件是数据库应用【开发工具】。 19.数据库体系结构中包含的三级模式为【内模式、模式】和【外模式】三种。 20.在数据库体系结构中,两级数据映像分别是指【模式、外模式】之间的数据映像与【模 式、内模式】之间的数据映像。 21.DBMS提供数据【定义】语句和数据【操纵】语句供用户使用。 22.在存取数据库的数据的过程中,使用了两个数据缓冲区,分别是【系统】缓冲区和【用 户】缓冲区。 习题二 1关系数据模型包括【关系运算】、【关系数据结构】和【关系完整性规则】三个方面。 2.在一个关系中,不同的列可以对应同一个【域】,但必须具有不同的【属性名】。 3.顾客购物的订单和订单明细之间是【1对多】的联系。 4.主码是一种【候选】码,主码中的【属性】个数没有限制。 5.若一个关系为R(学生号,姓名,性别,年龄),则【学生号】可以作为该关系的主码,

课后习题及答案

1 文件系统阶段的数据管理有些什么缺陷试举例说明。 文件系统有三个缺陷: (1)数据冗余性(redundancy)。由于文件之间缺乏联系,造成每个应用程序都有对应的文件,有可能同样的数据在多个文件中重复存储。 (2)数据不一致性(inconsistency)。这往往是由数据冗余造成的,在进行更新操作时,稍不谨慎,就可能使同样的数据在不同的文件中不一样。 (3)数据联系弱(poor data relationship)。这是由文件之间相互独立,缺乏联系造成的。 2 计算机系统安全性 (1)为计算机系统建立和采取的各种安全保护措施,以保护计算机系统中的硬件、软件及数据; (2)防止其因偶然或恶意的原因使系统遭到破坏,数据遭到更改或泄露等。 3. 自主存取控制缺点 (1)可能存在数据的“无意泄露” (2)原因:这种机制仅仅通过对数据的存取权限来进行安全控制,而数据本身并无安全性标记 (3)解决:对系统控制下的所有主客体实施强制存取控制策略 4. 数据字典的内容和作用是什么 数据项、数据结构 数据流数据存储和加工过程。 5. 一条完整性规则可以用一个五元组(D,O,A,C,P)来形式化地表示。 对于“学号不能为空”的这条完整性约束用五元组描述 D:代表约束作用的数据对象为SNO属性; O(operation):当用户插入或修改数据时需要检查该完整性规则; A(assertion):SNO不能为空; C(condition):A可作用于所有记录的SNO属性; P(procdure):拒绝执行用户请求。 6.数据库管理系统(DBMS)

:①即数据库管理系统(Database Management System),是位于用户与操作系统之间的 一层数据管理软件,②为用户或应用程序提供访问DB的方法,包括DB的建立、查询、更 新及各种数据控制。 DBMS总是基于某种数据模型,可以分为层次型、网状型、关系型、面 向对象型DBMS。 7.关系模型:①用二维表格结构表示实体集,②外键表示实体间联系的数据模型称为关系模 型。 8.联接查询:①查询时先对表进行笛卡尔积操作,②然后再做等值联接、选择、投影等操作。 联接查询的效率比嵌套查询低。 9. 数据库设计:①数据库设计是指对于一个给定的应用环境,②提供一个确定最优数据模 型与处理模式的逻辑设计,以及一个确定数据库存储结构与存取方法的物理设计,建立起 既能反映现实世界信息和信息联系,满足用户数据要求和加工要求,又能被某个数据库管 理系统所接受,同时能实现系统目标,并有效存取数据的数据库。 10.事务的特征有哪些 事务概念 原子性一致性隔离性持续性 11.已知3个域: D1=商品集合=电脑,打印机 D3=生产厂=联想,惠普 求D1,D2,D3的卡尔积为: 12.数据库的恢复技术有哪些 数据转储和和登录日志文件是数据库恢复的

中华人民共和国城乡规划法试题及详细答案解析(供参考)

文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持. 一,单项选择题(每题所给选项中只有一个正确答案.本部分共60题,其中1-20题每题0.5 分,21-60题每题1分,共50分) 1,《城乡规划法》自年月日起施行.( C ) A,2007,10,28 B,2007,12,1 C,2008,1,1 D,2008,2,1 2,协调城乡空间布局,改善人居环境是城乡规划法的 .( C ) A,直接目的 B,根本目的 C,主要目的 D,终极价值目标 城乡规划的根本目的是规划人们的行为,直接目的是加强管理,目标是可持续性,所以主要目的比较适合。 3,《城乡规划法》所称城乡规划,包括城镇体系规划,城市规划,镇规划, .( D ) A,乡村规划 B,村庄规划 C,乡规划D,乡规划和村庄规划 4,城市规划,镇规划分为和 .( C ) A,控制性详规,修建性详规 B,总体规划,建设规划 C,总体规划,详细规划 D,分区规划,详细规划 5,在城市总体规划,镇总体规划确定的范围以外,不得设立各类开发区和城市新区.( D ) A,建成区 B,规划区 C,农业用地D,建设用地 6,在规划区内进行建设活动,应当遵守 , 和等法律,法规的规定.( A ) 第四条 A,土地管理自然资源环境保护 B,土地管理水源保护环境保护 C,土地管理耕地保护环境保护 D,土地管理生态保护环境保护 7,城市总体规划在报上一级人民政府审批前,应当先经审议.( C ) A,本级党委 B,本级人民代表大会 C,本级人大常委会 D,本级人民政协 8,建设单位应当在竣工验收后个月内向城乡规划主管部门报送有关竣工验收资料.( C ) A,3 B,5 C,6 D,8 9,城市总体规划,镇总体规划的规划期限一般为年.近期建设规划的规划期限为年.( C ) A,10 5 B,15 10 C,20 5 D,20 10 10,乡,镇人民政府组织编制乡规划,村庄规划,报审批.( D ) 第二十二条 村民大会 B,镇人民代表大会,乡A,. 文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持. C,县(市)人大常委会D,上一级人民政府 11,城乡规划组织编制机关应委托其具有的单位承担城乡规划的具体编制工作.( B ) A,规划行政等级B,相应资质等级 C,技术资质等级 D,规划编制经历 12,修建性详细规划应当符合 .( D ) A,城镇总体规划 B,城镇详细规划 C,城镇体系规划D,控制性详细规划 13,村庄规划在报送审批前应当经讨论同意.( C )

数据结构与算法基础知识总结

数据结构与算法基础知识总结 1 算法 算法:是指解题方案的准确而完整的描述。 算法不等于程序,也不等计算机方法,程序的编制不可能优于算法的设计。 算法的基本特征:是一组严谨地定义运算顺序的规则,每一个规则都是有效的,是明确的,此顺序将在有限的次数下终止。特征包括:(1)可行性; (2)确定性,算法中每一步骤都必须有明确定义,不充许有模棱两可的解释,不允许有多义性; (3)有穷性,算法必须能在有限的时间内做完,即能在执行有限个步骤后终止,包括合理的执行时间的含义; (4)拥有足够的情报。 算法的基本要素:一是对数据对象的运算和操作;二是算法的控制结构。 指令系统:一个计算机系统能执行的所有指令的集合。 基本运算和操作包括:算术运算、逻辑运算、关系运算、数据传输。算法的控制结构:顺序结构、选择结构、循环结构。 算法基本设计方法:列举法、归纳法、递推、递归、减斗递推技术、回溯法。 算法复杂度:算法时间复杂度和算法空间复杂度。

算法时间复杂度是指执行算法所需要的计算工作量。 算法空间复杂度是指执行这个算法所需要的内存空间。 2 数据结构的基本基本概念 数据结构研究的三个方面: (1)数据集合中各数据元素之间所固有的逻辑关系,即数据的逻辑结构; (2)在对数据进行处理时,各数据元素在计算机中的存储关系,即数据的存储结构; (3)对各种数据结构进行的运算。 数据结构是指相互有关联的数据元素的集合。 数据的逻辑结构包含: (1)表示数据元素的信息; (2)表示各数据元素之间的前后件关系。 数据的存储结构有顺序、链接、索引等。 线性结构条件: (1)有且只有一个根结点; (2)每一个结点最多有一个前件,也最多有一个后件。 非线性结构:不满足线性结构条件的数据结构。 3 线性表及其顺序存储结构

(完整版)数据库课后部分习题答案2015

习题1 5.实体之间联系有哪几种?分别举例说明? 答:1:1联系:如果实体集El中每个实体至多和实体集E2中的一个实体有联习,反之亦然,那么El和E2的联系称为“l:1联系”。例如:电影院的座位和观众实体之间的联系。 1:N联系:如果实体集El中每个实体可以与实体集E2中任意个(零个或多个)实体有联系,而E2中每个实体至多和El中一个实体有联系,那么El和E2的联系是“1:N联系”。例如:部门和职工两个实体集之间的联系。 M:N联系:如果实体集El中每个实体可以与实体集E2中任意个(零个或多个)实体有联系,反之亦然,那么El和E2的联系称为“M:N联系”。例如:工程项目和职工两个实体集之间的联系。 7.简述数据库系统的两级映像和数据独立性之间的关系。 答:为了能够在系统内部实现外部级、概念级和内部级3个抽象层次的联系和转换,数据库管理系统在这三级模式之间提供了两层映像: 外模式/模式映像定义通常包含在各自外模式的描述中,保证了数据与程序的逻辑独立性,简称数据的逻辑独立性,应用程序是依据外模式编写的; 模式/内模式映像包含在模式描述中,此映像是唯一的,它定义了数据全局逻辑结构与存储结构之间的对应关系,它保证了数据与程序的物理独立性,所以称为数据的物理独立性。 习题2 1.名词解释: 超键:能惟一标识元组的属性或属性集,称为关系的超键。 候选键:不含有多余属性的超键,称为候选键。 实体完整性规则:实体的主键值不允许是空值。 参照完整性规则:依赖关系中的外键值或者为空值,或者是相应参照关系中某个主键值。 函数依赖:设有关系模式R(U),X和Y是属性集U的子集,若对于R(U)的任意一个可能的关系r,r中不可能存在两个元组在X上的属性值相等,而在Y上的属性值不等,则称X函数确定Y或Y函数依赖(Functional Dependency,简记为FD)于X,记作X→Y。 无损分解:当对关系模式R进行分解时,R的元组将分别在相应属性集进行投影而产生新的关系。如果对新的关系进行自然连接得到的元组集合与原关系完全一致,则称该分解为无损分解。 2NF:如果关系模式R属于1NF,且它的每一个非主属性都完全函数依赖于R的候选键,则称R属于第二范式,简记为R∈2NF。 3NF:如果关系模式R属于1NF,且每个非主属性都不传递依赖于R的候选键,那么称R属于第三范式,简记为R∈3NF。 3.笛卡尔积、等值连接和自然连接三者之间有什么区别? 答:笛卡儿积是一个基本操作,而等值连接和自然连接是组合操作。 设关系R的元数为r,元组个数为m;关系S的元数为s。,元组个数为n。 那么,R×S的元数为r+s,元组个数为m×n; 的元数也是r+s,但元组个数小于等于m×n;

(完整版)数据库课后习题及答案

第一章数据库系统概述 选择题 1实体-联系模型中,属性是指(C) A.客观存在的事物 B.事物的具体描述 C.事物的某一特征 D.某一具体事件 2对于现实世界中事物的特征,在E-R模型中使用(A) A属性描述B关键字描述C二维表格描述D实体描述 3假设一个书店用这样一组属性描述图书(书号,书名,作者,出版社,出版日期),可以作为“键”的属性是(A) A书号B书名C作者D出版社 4一名作家与他所出版过的书籍之间的联系类型是(B) A一对一B一对多C多对多D都不是 5若无法确定哪个属性为某实体的键,则(A) A该实体没有键B必须增加一个属性作为该实体的键C取一个外关键字作为实体的键D该实体的所有属性构成键 填空题 1对于现实世界中事物的特征在E-R模型中使用属性进行描述 2确定属性的两条基本原则是不可分和无关联 3在描述实体集的所有属性中,可以唯一的标识每个实体的属性称为键 4实体集之间联系的三种类型分别是1:1 、1:n 、和m:n 5数据的完整性是指数据的正确性、有效性、相容性、和一致性 简答题 一、简述数据库的设计步骤 答:1需求分析:对需要使用数据库系统来进行管理的现实世界中对象的业务流程、业务规则和所涉及的数据进行调查、分析和研究,充分理解现实世界中的实际问题和需求。 分析的策略:自下而上——静态需求、自上而下——动态需求 2数据库概念设计:数据库概念设计是在需求分析的基础上,建立概念数据模型,用概念模型描述实际问题所涉及的数据及数据之间的联系。 3数据库逻辑设计:数据库逻辑设计是根据概念数据模型建立逻辑数据模型,逻辑数据模型是一种面向数据库系统的数据模型。 4数据库实现:依据关系模型,在数据库管理系统环境中建立数据库。 二、数据库的功能 答:1提供数据定义语言,允许使用者建立新的数据库并建立数据的逻辑结构 2提供数据查询语言 3提供数据操纵语言 4支持大量数据存储 5控制并发访问 三、数据库的特点 答:1数据结构化。2数据高度共享、低冗余度、易扩充3数据独立4数据由数据库管理系统统一管理和控制:(1)数据安全性(2)数据完整性(3)并发控制(4)数据库恢复 第二章关系模型和关系数据库 选择题 1把E-R模型转换为关系模型时,A实体(“一”方)和B实体(“多”方)之间一对多联系在关系模型中是通过(A)来实现的

2019年党建知识竞赛题库含答案

2019年党建知识竞赛题库含答案 一、单选题 1、中国共产党第十九次全国代表大会召开时间(A) A、2017年10月18日 B、2017年10月24日 C、2017年8月31日北京时间2017年10月18日-10月24日,中国共产党第十九次全国代表大会在北京召开 2、中国共产党第十九次全国代表大会,是在全面建成小康社会决胜阶段、中国特色社会主义进入_____的关键时期召开的一次十分重要的大会。 A、新时期 B、新阶段 C、新征程 D、新时代答案:D 3、十九大的主题是:不忘初心,____,高举中国特色社会主义伟大旗帜,决胜全面建成小康社会,夺取新时代中国特色社会主义伟大胜利,为实现中华民族伟大复兴的中国梦不懈奋斗。 A、继续前进 B、牢记使命 C、方得始终 D、砥砺前行答案:B 3、中国共产党人的初心和使命,就是为中国人民____,为中华民族____。这个初心和使命是激励中国共产党人不断前进的根本动力。 A、谋幸福,谋未来 B、谋生活,谋复兴 C、谋幸福,谋复兴 D、谋生活,谋未来答案:C 4、五年来,我们统筹推进“____”总体布局、协调推进“____”战略布局,“十二五”规划胜利完成,“十三五”规划顺利实施,党和国家事业全面开创新局面。 A、五位一体四个全面 B、四位一体五个全面 C、五个全面四位一体 D、四个全面五位一体答案:A

5、过去五年,经济保持中高速增长,在世界主要国家中名列前茅,国内生产总值从五十四万亿元增长到____万亿元,稳居世界第二,对世界经济增长贡献率超过百分之三十。 A、六十 B、七十 C、八十 D、九十答案:C 6、脱贫攻坚战取得决定性进展,____贫困人口稳定脱贫,贫困发生率从百分之十点二下降到百分之四以下。 A、六千多万 B、七千多万 C、八千多万 D、九千多万答案:A 7、实施共建“一带一路”倡议,发起创办亚洲基础设施投资银行,设立丝路基金,举办首届“一带一路”国际合作高峰论坛、亚太经合组织领导人非正式会议、二十国集团领导人____峰会、金砖国家领导人____会晤、亚信峰会。 A、北京南京 B、杭州厦门 C、南京北京 D、厦门杭州答案:B 8、坚持反腐败无禁区、全覆盖、零容忍,坚定不移“打虎”、“拍蝇”、“猎狐”,____的目标初步实现,____的笼子越扎越牢,____的堤坝正在构筑,反腐败斗争压倒性态势已经形成并巩固发展。 A、不敢腐不能腐不想腐 B、不能腐不敢腐不想腐 C、不想腐不敢腐不能腐 D、不敢腐不想腐不能腐答案:A 9、经过长期努力,中国特色社会主义进入了新时代,这是我国发展新的____。 A、未来方向 B、未来方位 C、历史方向 D、历史方位答案:D 10、中国特色社会主义进入新时代,我国社会主要矛盾已经转化为人民日益增长的____需要和____的发展之间的矛盾。 A、美好生活不充分不平衡 B、幸福生活不平衡不充分 C、幸福生活不充分不平衡 D、美好生活不平衡不充分答案:D

城乡规划法试题及答案

城乡规划法试题及答案 【篇一:《城乡规划法》知识竞赛试题含答案】 0题,其中1-20题每题0.5分,21-60题每题1分,共50分) 1,《城乡规划法》自年月日起施行.( ) a,2007,10,28 b,2007,12,1 c,2008,1,1 d,2008,2,1 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,3 b,5 c,6 d,8

9,城市总体规划,镇总体规划的规划期限一般为年.近期建设规划的规划期限为年.( ) a,10 5 b,15 10 c,20 5 d,20 10 10,乡,镇人民政府组织编制乡规划,村庄规划,报审批.( ) 第二十二条 a,乡,镇人民代表大会 b,村民大会 c,县(市)人大常委会 d,上一级人民政府 11,城乡规划组织编制机关应委托其具有的单位承担城乡规划的具体编制工作.( ) a,规划行政等级 b,相应资质等级 c,技术资质等级 d,规划编制经历 12,修建性详细规划应当符合 .( ) a,城镇总体规划 b,城镇详细规划 c,城镇体系规划 d,控制性详细规划 13,村庄规划在报送审批前应当经讨论同意.( ) a,村委会 b,村党支部 c,村民会议或者村民代表会议 d,乡,镇人民代表会议 14,城乡规划报送审批前,组织编制机关应当依法将城乡规划草案予以公告,公告时间不得少于日.( ) a,10 b,15 c,30 d,60 15,按照国家规定需要有关部门批准或者核准的建设项目,以划拨方式提供国有土地使用权的,建设单位在报送有关部门批准或者核准前,应当向城乡规划主管部门申请核发 .( ) a,选址意见书 b,建设用地规划许可证 c,建设工程规划许可证 d,规划条件通知书 16, 未纳入国有土地使用权出让合同时,该国有土地使用权出让合同无效.( ) a,土地所有权 b,规划条件 c,土地使用权 d,规划要点 17,在乡,村庄规划区内进行乡镇企业,乡村公共设施和公益事业建设的,建设单位或个人应当向乡镇人民政府提出申请,由乡镇人民政府报市,县人民政府城乡规划主管部门核发 .( ) a,建设用地规划许可证 b,建设工程规划许可证 c,规划条件通知书 d,乡村建设规划许可证 18,在城市,镇规划区内进行临时建设的,应当经批准.( ) a,城市,县人民政府 b,城市,县建设行政主管部门

《数据结构基础教程》习题及解答

《数据结构基础教程》习题解答(新) 第1章习题解答 一、填空 1.数据就是指所有能够输入到计算机中被计算机加工、处理得符号得集合。 2.可以把计算机处理得数据,笼统地分成数值型与非数值型两大类。 3.数据得逻辑结构就就是指数据间得邻接关系。 4.数据就是由一个个数据元素集合而成得。 5.数据项就是数据元素中不可再分割得最小标识单位,通常不具备完整、确定得实际意义,只就是反映数据元素某一方面得属性。 6.数据就是以数据元素为单位存放在内存得,分配给它得内存区域称为存储结点。 7.每个数据元素都具有完整、确定得实际意义,就是数据加工处理得对象。 8.如果两个数据结点之间有着逻辑上得某种关系,那么就称这两个结点就是邻接得。 9.在一个存储结点里,除了要有数据本身得内容外,还要有体现数据间邻接关系得内容。 10.从整体上瞧,数据在存储器内有两种存放得方式:一就是集中存放在一个连续得内存存储区中;一就是利用存储器中得零星区域, 分散地存放在内存得各个地方。 11.在有些书里,数据得“存储结构”也称为数据得“物理结构”。 12.“基本操作”就是指算法中那种所需时间与操作数得具体取值无关得操作。 二、选择 1.在常见得数据处理中, B 就是最基本得处理。 A.删除 B.查找 C.读取 D.插入 2.下面给出得名称中, A 不就是数据元素得同义词。 A.字段 B.结点 C.顶点 D.记录 3. D 就是图状关系得特例。 A.只有线性关系 B.只有树型关系 C.线性关系与树型关系都不 D.线性关系与树型关系都 4.链式存储结构中,每个数据得存储结点里 D指向邻接存储结点得指针,用以反映数据间得逻辑关系。 A.只能有1个 B.只能有2个 C.只能有3个 D.可以有多个 5.本书将采用 C 来描述算法。 A.自然语言 B.流程图(即框图) C.类C语言 D.C语言 6.有下面得算法段: for (i=0; i

数据库系统概论第五版课后习题答案王珊版

第二章关系数据库 1 .试述关系模型的三个组成部分。 答:关系模型由关系数据结构、关系操作集合和关系完整性约束三部分组成。 2 .试述关系数据语言的特点和分类。 答:关系数据语言可以分为三类: 关系代数语言。 关系演算语言:元组关系演算语言和域关系演算语言。 SQL:具有关系代数和关系演算双重特点的语言。 这些关系数据语言的共同特点是,语言具有完备的表达能力,是非过程化的集合操作语言,功能强,能够嵌入高级语言中使用。 3 (略) 4 . 5 . 述关系模型的完整性规则。在参照完整性中,为什么外部码属性的值也可以为空?什么情况下才可以为空? 答:实体完整性规则是指若属性A是基本关系R的主属性,则属性A不能取空值。 若属性(或属性组)F是基本关系R的外码,它与基本关系S的主码Ks相对应(基本关系R和S不一定是不同的关系),则对于R中每个元组在F上的值必须为:或者取空值(F的每个属性值均为空值);或者等于S中某个元组的主码值。即属性F本身不是主属性,则可以取空值,否则不能取空值。 6.设有一个SPJ数据库,包括S,P,J,SPJ四个关系模式: 1)求供应工程J1零件的供应商号码SNO: πSno(σJno=‘J1’(SPJ)) 2)求供应工程J1零件P1的供应商号码SNO: πSno(σJno=‘J1’∧Pno=‘P1‘(SPJ)) 3)求供应工程J1零件为红色的供应商号码SNO: πSno(πSno,,Pno(σJno=‘J1‘(SPJ))∞πPno(σCOLOR=’红‘(P))) 4)求没有使用天津供应商生产的红色零件的工程号JNO: πJno(SPJ)- πJNO(σcity=‘天津’∧Color=‘红‘(S∞SPJ∞P) 5)求至少用了供应商S1所供应的全部零件的工程号JNO: πJno,Pno(SPJ)÷πPno(σSno=‘S1‘(SPJ)) 7. 试述等值连接与自然连接的区别和联系。 答:连接运算符是“=”的连接运算称为等值连接。它是从关系R与S的广义笛卡尔积中选取A,B属性值相等的那些元组 自然连接是一种特殊的等值连接,它要求两个关系中进行比较的分量必须是相同的属性组,并且在结果中把重复的属性列去掉。 8.关系代数的基本运算有哪些? 如何用这些基本运算来表示其他运算? 答:并、差、笛卡尔积、投影和选择5种运算为基本的运算。其他3种运算,即交、连接和除,均可以用这5种基本运算来表达。 第三章关系数据库语言SQL 1 .试述sQL 语言的特点。 答: (l)综合统一。sQL 语言集数据定义语言DDL 、数据操纵语言DML 、数据控制语言DCL

实用数据结构基础(第四版)课后习题知识讲解

一、判断题 (第一章绪论) 1.数据元素是数据的最小单元。 答案:错误 2.一个数据结构是由一个逻辑结构和这个逻辑结构上的基本运算集构成的整体。 答案:错误 3.数据的存储结构是数据元素之间的逻辑关系和逻辑结构在计算机存储器内的映像。 答案:正确 4.数据的逻辑结构是描述元素之间的逻辑关系,它是依赖于计算机的。 答案:错误 5.用语句频度来表示算法的时间复杂度的最大好处是可以独立于计算机的软硬件,分析算法的时间 答案:正确 (第二章线性表) 6.取顺序存储线性表的第i个元素的时间同i的大小有关。 答案:错误 7.线性表链式存储的特点是可以用一组任意的存储单元存储表中的数据元素。 答案:正确 8.线性链表的每一个节点都恰好包含一个指针域。 答案:错误 9.顺序存储方式的优点的存储密度大,插入和删除效率不如练市存储方式好。 答案:正确 10.插入和删除操作是数据结构中最基本的两种操作,所以这两种操作在数组中也经常使用。答案:错误 (第三章栈)

11.栈是一种对进栈和出栈作了限制的线性表。 答案:错误 12.在C(或C++)语言中设顺序栈的长度为MAXLEN,则top=MAXLEN表示栈满。答案:错误 13.链栈与顺序栈相比,其特点之一是通常不会出现满栈的情况。 答案:正确 14.空栈就是所有元素都为0上的栈。 答案:错误 15.将十进制数转换为二进制数是栈的典型应用之一。 答案:正确 (第四章队列) 16.队列式限制在两端进行操作的线性表。 答案:正确 17.判断顺序队列为空的标准是头指针和尾指针都指向同一结点。 答案:错误 18.在循环链列队中无溢出现像。 答案:错误 19.在循环队列中,若尾指针rear大于头指针front,则元素个数为rear-front。 答案:正确 20.顺序队列和循环队列关于队满和队空的判断条件是一样的。 答案:错误 (第五章串) 21.串是n个字母的有限序列。 答案:错误 22.串的堆分配存储是一种动态存储结构。

相关主题