数据结构讨论小课堂和习题解答

讨论小课堂 1

数据结构课程主要讨论哪三个方面？

1.逻辑结构

2.存储结构

3.数据操作

1.算法和程序的区别是什么呢？

【参考答案】：算法的含义与程序十分相似，但又有区别。一个程序不一定满足有穷性。例如，操作系统，只要整个系统不遭破坏，它将永远不会停止，即使没有作业需要处理，它仍处于动态等待中。因此，操作系统不是一个算法。另一方面，程序中的指令必须是机器可执行的，而算法中的指令则无此限制。算法代表了对问题的解，而程序则是算法在计算机上的特定的实现。一个算法若用程序设计语言来描述，则它就是一个程序。

算法与数据结构是相辅相承的。解决某一特定类型问题的算法可以选定不同的数据结构，而且选择恰当与否直接影响算法的效率。反之，一种数据结构的优劣由各种算法的执行来体现。

要设计一个好的算法通常要考虑以下的要求。

⑴正确。算法的执行结果应当满足预先规定的功能和性能要求。

⑵可读。一个算法应当思路清晰、层次分明、简单明了、易读易懂。

⑶健壮。当输入不合法数据时，应能作适当处理，不至引起严重后果。

⑷高效。有效使用存储空间和有较高的时间效率。

2，你认为应该如何评估一个数据结构或算法的有效性。

【参考答案】：前提之一是算法的正确性；其二还必须考虑执行算法所耗费的时间和执行算法所耗费的空间（主要是只指辅助空间），以及算法是否易读、易编码和易于调试。

3，讨论数据结构的重要性。

【参考答案】：如今计算机的应用已深入到社会生活的各个领域，计算机处理的对象由单纯的数值发展到字符、图象、声音等，表示这些对象的数据成分往往不是单一的，而是多成分且形成一定的结构。因此,在程序设计中，除了应精心设计算法外，还应精心组织数据（包括原始数据、中间结果、最终结果），使之形成一定的组织形式（数据结构），以便让计算机尽可能高效率地处理。在实际程序设计的实践中，数据结构和算法是不同的但又是互相联系的两个方面。我们甚至还可以说，问题的算法往往取决于选定的数据结构。所以N.Wirth 教授认为程序设计=算法+数据结构。

我们已经初步地学习了高级语言（例如pascal）的程序设,掌握了一些程序设计方法与技巧。然而，这些方法与技巧对于现实的程序设计工作来说，是远远不够的。以下举几个例子加以说明。

例1 求真分数117/29 的值，求到小数点后50位

例2 求真分数7/27 的值，精确到小数点后50 位。

1. 输出117 /29的值。

2. a <－余数。b<－29

3. aa * 10 。

4. 输出a/b 的商。

5. a<－余数。

6. 如未达要求，转 3 ，否则结束。

例3 从键盘输入若干个数，并将其排序输出。相同的数，只输出一个。本例似乎不难，可以采取的

策略之一：用一个数组来存放输入的数，然后排序输出。

策略之二：边输入边排序。

我们注意到：输出只能是不同的数，因而这是一个搜索加排序的问题。所以，不论采取那一种策略，用数组这一种结构不是最佳的结构，因为效率很低。事实上，若用二叉树作为存储结构，效率则会大大提高。

例4 工作安排的可行性问题。为了直观了解工作环节之间的制约关系，通常用"有向图"来表示这种安排。

习题1

1. 抽象数据类型的定义由哪几部分组成？

1.1【参考答案】：数据对象、数据关系和基本操作三部分。

2. 按数据元素之间的逻辑关系不同，数据结构有哪几类？

1.2【参考答案】：线性结构、树型结构、图状结构和集合四类。

3. 你能举出几个你熟悉的"序列"的例子来吗？

1.3【参考答案】：如："0，1，2，…，9","A，B，C，…，Z"。

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

5.数据结构和数据类型两个概念之间有区别吗？

1.5【参考答案】：简单地说，数据结构定义了一组按某些关系结合在一起的数组元素。数据类型不仅定义了一组带结构的数据元素，而且还在其上定义了一组操作。

6. 简述线性结构与非线性结构的不同点。

1.6【参考答案】：线性结构反映结点间的逻辑关系是一对一的，非线性结构反映结点间的逻辑关系是多对多的。

7. 有下列两段描述：

（1）void pro1( ) (2)void pro2( ) { {

n=2; y=0;

While(n%2==0) x=5/y;

n=n+2; printf(―%d,%d\n,x,y);

printf(―%d\n‖,n); }

}

这两段描述均不能满足算法的特征，试问它们违反了算法的那些特征？1.7【参考答案】：（1）是一个死循环，违反了算法的有穷性特征。（2）出现除零错误，违反了算法的可行性特征。

8. 分析并写出下面的各语句组所代表的算法的时间复杂度。

(1) for (i=0; i

for (j=0; j

A[i][j]=0;

【参考答案】：O（m*n）

(2) k=0;

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

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

k++;

}

【参考答案】：O（n2）

(3) i=1;

while(i<=n)

i=i*3;

【参考答案】：3 T(n)≤n即：T(n)≤log3n =O（log3n）所以：T(n)= O（log3n）

(4) k=0;

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

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

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

x += delta;;

}

【参考答案】：O（n3）

(5) for(i=0,j=n-1;i

{t=a[i]; a[i]= a[j]; a[i]=t;}

【参考答案】：基本语句共执行了n/2次，T(n)=O（n）

(6)x=0;

for(i=1; i

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

x++;

【参考答案】：因为x++共执行了n-1+n-2+……＋1= n(n-1)/2，所以执行时间为O （n2）

讨论小课堂2

1.在一个非递减有序线性表中，插入一个值为X的元素，使插入后的线性表仍

为非递减有序。（注意：对比顺序存储结构和链式存储结构表示。）

【参考答案】

⑴方法一：顺序存储结构

void insert(ElemType x)

{ i=length-1;

while(i>=0&&elem[i]>x)

{elem[i+1]=elem[i];

i--;

}

elem[i+1]=x;length++;

}

⑵方法二：链式存储结构

void insert(ElemType x)

{ NodeType *p,*q,*s;

p=L;q=q->next;

while(q!=NULL&&q->data<=x)

{p=q;q=q->next;}

s=new NodeType;

s->data=x;

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

}

2.观察下面的算法，此算法完成如下功能：在非递减有序表中删除所有值为X的元素。问：如何改进此算法，使得算法效率提高？

void Deletaz(ElemType x)

{ int i=0,j;

while (i

if(i==length) cout<<‖X不存在‖<

else{ while(elem[i]==x)

{ for(j=I;j

length--;}

}

}

【答案】

void delete(ElemType x)

{ int i=0,j,n;

while(i

if(i==length) cout<<―no x‖<

else{

while(elem[i]==x)

{n++;i++;}

for(j=i;j

elem[j-n]=elem[j];

length=length-n;

}

}

3．试设计一个算法，将线性表中前m 个元素和后n 个元素进行互换，即将线性表

(a1, , …, a m, b1, b2, …, b n ) 改变成

(b1, b2, …, b n, a1, a2, …, a m )

要求采用顺序存储结构及链式存储结构分别完成，并比较采用这两种存储结构，其算法效率哪种存储结构更好？

【答案】试设计一个算法，顺序表中前m 个元素和后n 个元素进行互换，即将线性表

(a1, a2, …, a m, b1, b2, …, bn ) 改变成

(b1, b2, …, b n, a1, a2, …, am ) 。

算法1：进行三次“逆转顺序表”的操作。

算法2：从b1开始，从原地删除之后插入到a1 之前直至bn。

5}改变成{1, 2，3，4，5,a, b,

算法1：

void invert( ElemType R[]，int s，int t )

/* 本算法将数组R 中下标自s 到t 的元素逆置，即将（Rs, Rs+1, …, Rt-1, Rt ）改变为（Rt, Rt-1, …, Rs+1, Rs ）*/

void exchange ( SqList A; int m ) {

/*本算法实现顺序表中前m 个元素和后n 个元素的互换*/

n = A.length – m;

invert( A.elem, 0, A.length );

invert( A.elem, 0, n-1 );

invert( A.elem, n, m+n-1 );

}

算法2:

void exchange( SqList A, int m ) {

/* 实现顺序表A 中前m 个元素和后n 个元素互换*/

for ( i=0; j = m; j

x = A.elem[j];

for ( k=j; k>i; k-- )

A.elem[j] = A.elem[j-1];

A.elem[i] = x;

}

算法的时间复杂度:为: O(m n)

算法设计:

将(b1, b2, …, bn )从链表的当前位置上删除之后再插入a1 到之前，并将am设为表尾。

ta->next=NULL;

tb->next = L->next;

L->next = hb;

void exchange( SLink &L, int m ) {

// 互换链表中前m 个和后n 个结点

ta = L; i = 0;

while ( ta && i

ta = ta->next; i++;

}// while

if ( ta && ta->next ) { // m < 表长

hb = ta->next; tb = hb;

while (tb->next) tb = tb->next; // 查询表尾bn修改指针

}

算法的时间复杂度:为:O(ListLength(L))

4．讨论线性表的逻辑结构和存储结构的关系，以及不同存储结构的比较。

【答案】存储结构分为：

⑴顺序存储结构：借助元素在存储器中的相对位置来表示数据元素间的逻辑关系

链式存储结构：借助指示元素存储地址的指针表示数据元素间的逻辑关系

⑵数据的逻辑结构—只抽象反映数据元素的逻辑关系

数据的存储（物理）结构—数据的逻辑结构在计算机存储器中的实现

⑶数据的逻辑结构与存储结构密切相关：

算法设计→逻辑结构

算法实现→存储结构

⑷顺序表：

可以实现随机存取：O(1)

插入和删除时需要移动元素：O(n)

需要预分配存储空间;

适用于―不常进行修改操作、表中元素相对稳定‖的场合。

链表：

只能进行顺序存取：O(n)

插入和删除时只需修改指针：O(1)

不需要预分配存储空间;

适用于―修改操作频繁、事先无法估计最大表长‖的场合。

——应用问题的算法时间复杂度的比较

例如，以线性表表示集合进行运算的时间复杂度为O(n2),

而以有序表表示集合进行运算的时间复杂度为O(n)

习题 2

1．判断下列概念的正确性

(1) 线性表在物理存储空间中也一定是连续的。

(2) 链表的物理存储结构具有同链表一样的顺序。

(3) 链表的删除算法很简单，因为当删去链表中某个结点后，计算机会自动地

将后继的各个单元向前移动。

答：（1）（2）（3）都不正确。

2. 有如下图所示线性表，经过daorder 算法处理后，线性表发生了什么变化？画出处理后的线性表。

void daorder()

{ int i, j, n ; ElemType x;

n=length/2;

for( i=0 ; i

{ j=length-i-1;

x=elem[i]; elem[i]=elem[j]; elem[j]=x;

}

}

elem[0] …… elem[7] 假设length=8

答：经过daorder 算法处理后，线性表发生了逆置。处理后的线性表为：

3．试比较顺序存储结构和链式存储结构的优缺点。 答：

顺序结构存储时，相邻数据元素的存放地址也相邻，即逻辑结构和存储结构是统一的，，要求内存中存储单元的地址必须是连续的。 优点：一般情况下，存储密度大，存储空间利用率高。

缺点：（1）在做插入和删除操作时，需移动大量元素；（2）由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用；（3）表的容量难以扩充。

链式结构存储时，相邻数据元素可随意存放，所占空间分为两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。 优点：插入和删除元素时很方便，使用灵活。 缺点：存储密度小，存储空间利用率低。

4．试写出一个计算链表中结点个数的算法，其中指针ｐ指向该链表的第一个结点。

答：int linklist_num(linklist L,Lnode *p) { int n=0; While(p){n++;p=p->next;} Return n: }

5．试设计实现在单链表中删去值相同的多余结点的算法。 (a)为删除前，(b)为删除后。

答：void Deletaz(Linklist L) { Lnode *p,*q,*r,*s; P=l->next;

while (p) {q=p;r=q->next;

while(r){if(r->data!=p->data){q=r;r=r->next};

else{s=r->next;q->next=s;free(r);r=s;}

}

P=p->next;

}

}

6. 有一个线性表(a1,a2,...,an)，它存储在有附加表头结点的单链表中，写一个算

法，求出该线性表中值为x的元素的序号。如果x不存在，则输出序号为零。答：int linklist_x(linklist L,datatype x)

{int i=0;Lnode *p;

P=L->next;

While(p&&p->dada!=x){i++;p=p->next;}

If(!p)return 0;

Else return I;

}

7．写一个算法将一单链表逆置。要求操作在原链表上进行。

答：void reverse (LinkList L)

{ p=L->next;

L->next=NULL;

while (p)

{ q=p->next;

p->next=L->next;

L->next=p;

p=q;

}

}

8．在一个非递减有序线性表中，插入一个值为X的元素，使插入后的线性表仍为非递减有序。分别用向量和单链表编写算法。

答：void insert_x(Linklist L,Datatype x)

/*在递增有序的单链表L中插入值为x的元素，使得插入后L仍然有序*/ {Lnode *p,*q,*r;

P=L;q=p->next;

While(q&&q->dada<=x)

{p=q;q=q->next;}

R=(Lnode *)malloc(Lnode);

r->dada=x;

r->next=q;

p->next=r;

}

9．写一算法将值为B的结点插在链表中值为a的结点之后。如果值为a的结点不存在，则插在表尾。

答: void Insert_LinkList( LinkList L, DataType a, DataType B)

{ /* 在值为a 的结点后插入值为B的结点，表中若无a则B接在表尾*/ LinkList p,q,s ;

s=( LinkList)malloc(sizeof(struct node));

s->data=B; s->next=NULL;

q=L; p=L->next;

while( p!=NULL && p->data!=a ) { q=p; p=p->next; }

if(p){s->next=p->next;p->next=s;}

else{ s->next=q->next;q->next=s;}

}

10．试用循环链表为存储结构，写一个约瑟夫(Josephu)问题的算法。约瑟夫问题是：有N个人围成一圈，从第i个人开始从1报数，数到m时，此人就出列。

下一个人重新从1开始报数，再数到m时，以一个人出列。直到所有的人全部出列。按出列的先后得到一个新的序列。例如，N=5，i=1, m=3 时新的序列应为：3, 1, 5, 2, 4。

答：

typedef struct node /* 结点的结构定义*/

{ int num; /* 编号子域*/

struct node *next; /* 指针域*/

}JOS;

void outs(JOS *h, int m)

{ int i; JOS *q=h, *p;

printf(―\n ―);

while (q->next!=q)

{ for(i=1;inext;} /* 报数到第m个人*/

printf(―%6d‖,q->num); /* 输出第m个人的编号*/

p->next=q->next; free(q); /* 第m个人出列*/

q=p->next;

}

printf(―%6d \n‖,q->num); /* 输出最后一个结点的编号值*/ free(q);

} /* outs */

11. 设有两个单链表A、B，其中元素递增有序，编写算法将A、B归并成一个

按元素值递减（允许有相同值）有序的链表C，要求用A、B中的原结点形成，不能重新申请结点。

答：void unit(Linklist A,Linklist B,Linklist C)

{Lnode *p,*q,*r,*s;

P=A->next;q=>next;C=A;r=C;

While(p&&q)

{if(p->dada<=q->dada){r=p;p=p->next;}

Else{s=q;q=q->next;s->next=r->next;r->next=s;r=s;}

}

If(!p)r->next=q;free(B)

}

讨论小课堂 3

【参考内容】

1. 如果输入序列为1 2 3 4 5 6,试问能否通过栈结构得到以下两个序列:4 3 5 6 1 2和1 3 5 4 2 6;请说明为什么不能实现或如何才能得到。

2. 设输入序列为2，3，4，5，6，利用一个栈能得到序列2，5，3，4，6吗？栈可以用单链表实现吗？

【答案】

1、输入序列为123456，不能得出435612，其理由是，输出序列最后两元素是12，前面4个元素（4356）得到后，栈中元素剩12，且2在栈顶，不可能栈底元素1在栈顶元素2之前出栈。

得到135426的过程如下：1入栈并出栈，得到部分输出序列1；然后2和3入栈，3出栈，部分输出序列变为：13；接着4和5入栈，5，4和2依次出栈，部分输出序列变为13542；最后6入栈并退栈，得最终结果135426。

2、不能得到序列2，5，3，4，6。栈可以用单链表实现，这就是链栈。由于栈只在栈顶操作，所以链栈通常不设头结点。

3. 简述顺序存储队列的“假溢出”现象的避免方法及怎样判定队列满和空的条件。

【答案】：

3、设顺序存储队列用一维数组q[m]表示，其中m为队列中元素个数，队列中元素在向量中的下标从0到m-1。设队头指针为front，队尾指针是rear，约定front 指向队头元素的前一位置，rear指向队尾元素。当front等于-1时队空，rear 等于m-1时为队满。由于队列的性质（“删除”在队头而“插入”在队尾），所以当队尾指针rear等于m-1时，若front不等于-1，则队列中仍有空闲单元，所以队列并不是真满。这时若再有入队操作，会造成假“溢出”。其解决办法有二，一是将队列元素向前“平移”（占用0至rear-front-1）；二是将队列看成首尾相连，即循环队列（0..m-1）。在循环队列下，仍定义front=rear时为队空，而判断队满则用两种办法，一是用“牺牲一个单元”，即rear+1=front（准确记是（rear+1）%m=front，m是队列容量）时为队满。另一种解法是“设标记”方法，如设标记tag，tag等于0情况下，若删除时导致front=rear为队空；tag=1情况下，若因插入导致front=rear则为队满。

4.假设有如下图所示的列车调度系统，约定两侧铁道均为单向行驶，入口处有N 节硬席或软席车厢（程序中可分别用H和S表示）等待调度，试编写算法，输出对这N节车厢进行调度的操作序列，要求所有的软席车厢被调整到硬席车厢之前。

【参考答案】：

void trains(char *elem)

{int i,k;

k=0;

for(i=0;i

if(elem[i]==‘S’) //软席车厢S

{ push();

pop();

}

else

{push();

k++}

while(k>0){pop();k--;}

}

5.对于一个具有N个单元（N>>2）的循环队列，若从进入第一个元素开始每隔T1个时间单位进入下一个元素，同时从进入第一个元素开始，每隔T2（T2>T1）个时间单位处理完一个元素并令其出队，试编写一个算法，求出在第几个元素进队时将发生溢出。

【分析】

时刻t: 0 1 2 3 4 5 67 89 个数： 1 1 2 1 2 2 3-2 2 3 2 放取：+ + - + + - + - 时刻t: 10 11 12 13

个数： 3 3 4-3 ……

放取：+ + - ……

N=2

先放后取：6时刻，放了4次，3个为溢出

放取同时：8时刻，放了5次，3个为溢出

如果同一时刻先放后取：

int main( )

{ int y=1,i=0, n, m, front=0,rear=1;

cin>>n; cin>>t1;cin>>t2; m=n+2;

if (t1>=t2) cout<<"error!";

else{

while((rear+1)%m!=front)

{ i++;

if (i%t1==0) {rear=(rear+1 )%m; y++; } if (i%t1==0&&(rear+1)%m==front) break; if (i%t2==0) {front=(front+1 )%m; } }

cout<

习题3

1.假定有编号为A 、B 、C 、D 的四辆列车，自右向左顺序开进一个栈式结构的站台，如图3.16所示。可以通过栈来编组然后开出站台。请写出列车开出站台的顺序有几种？写出每一种可能的序列。如果有n 辆列车进行编组呢？如何编程？

注：每一辆列车由站台向左开出时，均可进栈、出栈开出站台，但不允许出栈后回退。

图3.16 火车编组栈

2.已知栈采用链式存储结构，初始时为空，试画出a,b,c,d 四个元素依次进栈以后栈的状态，然后再画出此时的栈顶元素出栈后的状态。

3.写出链表栈的取栈顶元素和置栈空的算法。

4.写出计算表达式3+4/25*8-6时，操作数栈和运算符栈的变化情况表。

5.对于给定的十进制正整数N ，转换成对应的八进制正整数。

（1）写出递归算法。 （2）写出非递归算法。 6.已知n 为大于等于零的整数，试写出计算下列递归函数f(n)的递归和非递归算法。

f(n)=???≠=+时

当时当0)2/(*01

n n f n n n

7. 假设如题3.1所述火车调度站的入口处有n 节硬席或软席车厢（分别以H 和S 表示）等待调度。试编写算法，输出对这n 节车厢进行调度的操作（即入栈或出栈操作）序列，以使所有的软席车厢都被调整到硬席车厢之前。

8.课文中规定：无论是循环队列还是链表队列，队头指针总是指向队头元素的前一位置，队尾指针指向队尾元素。

（1）试画出有２个元素Ａ、B 的循环队列图，及将这2个元素出队后队列的状态图。

注：假设MAXSIZE=6，front=5，完成本题要求的图示。若erar=5，情况如何？

（2）试画出有２个元素C、D的链表队列图，及将这2个元素出队后链表

队列的状态图。

9.对于一个具有m个单元的循环队列，写出求队列中元素个数的公式。

10.对于一个具有n个单元(n>>2)的循环队列,若从进入第一个元素开始，每隔t1个时间单位进入下一个元素，同时从进入第一个元素开始，每隔t2(t2

≥t1)个时间单位处理完一个元素并令其出队，试编写一个算法，求出在第几

个元素进队时将发生溢出。

11.假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元

素结点（注意不设头指针），试编写出相应的置空队列，入队列和出队列的算法。

12.二项式(a + b)i展开后，其系数构成杨辉三角形。利用队列写出打印

杨辉三角形前n行的程序。即逐行打印二项展开式(a + b)i的系数。图3.17

是指数i从1到6的(a + b)i的展开式系数所构成的杨辉三角形。

讨论小课堂4

重点掌握串的匹配运算及应用，可结合实际的题目进行讨论来加深对串的一些运算的理解和掌握。

1. 输入一个字符串，内有数字和非数字字符，如：ak123x456 17960?302gef4563，将其中连续的数字作为一个整体，依次存放到一数组ａ中，例如123放入ａ［０］,456放入ａ［１］，……。编程统计其共有多少个整数，并输出这些数。

【参考答案】在一个字符串内，统计含多少整数的问题，核心是如何将数从字符串中分离出来。从左到右扫描字符串，初次碰到数字字符时，作为一个整数的开始。然后进行拼数，即将连续出现的数字字符拼成一个整数，直到碰到非数字字符为止，一个整数拼完，存入数组，再准备下一整数，如此下去，直至整个字符串扫描到结束。

算法如下：

int CountInt（）

/* 从键盘输入字符串，连续的数字字符算作一个整数，统计其中整数的个数。*/

｛int i=0，a[]；/* 整数存储到数组a，i记整数个数*/

char ch;

scanf(″%d″,&ch)；/* 从左到右读入字符串*/

while（ch!=?#‘）/*?#‘是字符串结束标记*/

if（（ch）>=48 && (ch)<=57）/* 是数字字符*/

｛num=０；/*数初始化*/

while（（ch）>=48 && (ch)<=57 && ch!=?#‘）/* 拼数*/

｛num=num＊10+?ch‘-?０‘；

scanf(″%d″,&ch)；

｝

a[i]=num；i++；

if（ch!=?#‘）scanf(″%d″,&ch)；/* 若拼数中输入了?#‘，则不再输入*/

｝while（ch！＝?#‘）/* 结束*/

Printf(‖共有%d‖,I,‖个整数，它们是：‖)；

for（j=０；j

｛printf(―%d‖;a[j];‖ ―)；

if（（j+1）％10==0）printf(―\n‖);} /*每10个数输出在一行上*/ ｝/* 算法结束*/

假定字符串中的数均不超过32767，否则，需用长整型数组及变量。

2. 以顺序存储结构表示串，设计算法。求串S中出现的第一个最长重复子串及其位置并分析算法的时间复杂度。例如：若S=―abceebccadddddaaadd!‖，则最长重复子串为―ddddd‖。位置是9。

【参考答案】设以字符数组s表示串，重复子串的含义是由一个或多个连续相等的字符组成的子串，其长度用max表示，初始长度为0，将每个局部重复子串的长度与max相比，若比max大，则需要更新max，并用index记住其开始位置。算法如下：

int LongestString(char s[],int n)

/*串用一维数组s存储，长度为n，本算法求最长重复子串，返回其长度。

*/

{int index=0,max=0; /*index记最长的串在s串中的开始位置，max记其长度*/

int length=1,i=0,start=0; /*length记局部重复子串长度，i为字符数组下标*/

while(i

if(s[i]==s[i+1]) {i++; length++;}

else /*上一个重复子串结束*/

{if(max

/*当前重复子串长度大，则更新max*/

i++;start=i;length=1;

/*初始化下一重复子串的起始位置和长度*/

}

Printf(―最长重复子串的长度为:%d―;max;‖在串中的位置:%d‖;index);

return(max);

}/*算法结束*/

算法中用i

算法的时间复杂度为O(n)，每个字符与其后继比较一次。

习题4

习题4

1．填空

（1）在计算机软件系统中，有两种处理字符串长度的方法：一种是采用显式，

第二种是隐式。

（2）一个字符串相等的充要条件是长度和对应字符都相等。

（3）串是指有限个字符组成的序列；空串是指长度的串；

空格串是指

一个或多个空格组成的串。

（4）设s=―I

︺AM

︺

A

︺

TEACHER‖,其长度是_14___。

（5）若n为主串长，m为子串长，则串的古典匹配算法最坏的情况下需要比较字符的总次数为○（m*n）。

2．空串和空格串有何区别？字符串中的空格符有何意义？空串在串的处理中有何作用？

答：空串时长度为0的字符串；空格串是一个或多个字符组成的字符串。字符串中的空格符充当界符的作用。空串在串的处理中可作为任意串的子串。

3．设计一算法，将两个字符串连接起来，要求不能利用strcat（）函数。

答：

Typedef struct

{char *ch; /*串数组*/

int length; /*串长*/

}HString;

int StrConcat(HString *S, HString T)

{

char *temp;temp=(char *)malloc(S->length);

if(temp==NULL)return(0);

for(int i=0;ilength;i++)temp[i]=S->ch[i]; /* 先把串S放入临时串temp中*/

free(S->ch);

S->ch=(char*)malloc(S->length+T.length); /* 为S分配新的空间*/

for(int i=0;i< S->length;i++)S->ch[i]=temp[i];

for(int j=0;j< T.length;j++)S->ch[i+j]=T.ch[j];

return(1);.

}

4．设计一算法，将字符串S中从pos位置开始共num 个字符构成的子串用字符串X来代替(X的长度可以不同于num)。

答：

Typedef struct

{char *ch; /*串数组*/

int length; /*串长*/

}HString;

void Strrepl (HString *S, int pos, int num,HString X)

{

if (pos < 1 || pos > S->length+1)

{ printf("\n 位置错误!");return;} /*位置不合法*/

char S1[S->length] ; /* S1 作为辅助串空间用于暂存S */

if (X.length)

{ /*X 非空，则为S重新分配空间并替换X*/

char *p=S->ch; i=0;

while (i < S.length)

S1[i++] = *(p+i); /* 暂存串S*/

if(pos+num>S->length) S->ch = new char[pos + X.length ];

Else S-> ch = new char[S->length-num + X.length ];

/* 为S重新分配串值存储空间*/

for ( i=0, k=0; i

S->ch[k++] = S1[i]; /*保留插入位置之前的子串*/ j = 0;

while (j

S->ch[k++] = X.ch[j++]; /* 替换X*/

while ( ilength)

S->ch[k++] = S1[i++];/* 复制替换部分后的子串*/ S->length+=T.length; /* 置串S 的长度*/

} /* if */

} /* Strrepl*/

5．试设计一个算法，测试一个串t的值是否为回文（即从左面读起与从右面读起内容一样）。

答：

int isSym(char *str,int length) /*判断一个字符串是否为回文,0是，-1不是

{for(int i=0;i

{ if(str[i] != str[length-i-1])

return -1;

}

return 0;

}

6．编写一个算法，统计在输入字符串中各个不同字符出现的频度。

答：

#include

int main()

{

int charcount[256];

int i;

char ch;

/*初始化*/

for(i=0;i<256;i++)

charcount[i] = 0;

while((ch = getchar()) != '\n')

charcount[ (int)ch ] ++;

/*输出*/

for(i=0;i<256;i++)

if( charcount[i]) printf("%c - %d\n", i, charcount[i]);

return 0;

}

7．设s=‖00001000010100001‖, t =‖0001‖,说明其在朴素模式匹配算法中的匹配过程。

答：

i=3

第一趟匹配0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 0 1

(1) 0 0 0 1

j=3

i=5

第二趟匹配0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 1

(2) 0 0 0 1

j=4

8．设计一个算法Replace(w,x), 将当前字符串所有子串w用另一个字符串x来替换。字符串w和x的长度可以不同。

答：参考习题4和匹配算法。

讨论小课堂5

[参考内容]

1．设m×n阶稀疏矩阵A有t个非零元素，其三元组表表示为LTMA[1..(t+1),1..3]，试问：非零元素的个数t达到什么程度时用LTMA表示A 才有意义？

【参考答案】：稀疏矩阵A有t个非零元素，加上行数mu、列数nu和非零元素个数tu，共占用三元组表LTMA的3(t+1)个存储单元，用二维数组存储时占用m ×n个单元，只有当3(t+1)< m×n时，用LTMA表示A才有意义。解不等式得t< m×n/3-1。

2．特殊矩阵和稀疏矩阵哪一种压缩存储后失去随机存取的功能？为什么？【参考答案】：特殊矩阵指值相同的元素或零元素在矩阵中的分布有一定规律。因此，可以对非零元素分配单元(这里，对值相同元素只分配一个单元)，将非零

元素存储在向量中，元素的下标i 和j 和该元素在向量中的下标有一定规律，可以用简单公式表示，仍具有随机存取功能；而稀疏矩阵是指非零元素和矩阵容量相比很小(t<

3．已知A 为稀疏矩阵，试从空间和时间角度比较采用二维数组和三元组顺序表两种不同的存储结构，完成求矩阵元素之和，并分析运算的优缺点。 【参考答案】：设稀疏矩阵A 为m 行n 列，如果采用二维数组常规存储，则其空间复杂度为O(m ×n)。因为要将所有的句镇元素累加起来，需要使用一个两层的嵌套循环结构，所以其时间复杂度为O(m ×n)。如果采用三元组顺序表进行压缩存储，假设稀疏矩阵中有t 个非零元素，则其空间复杂度为O(t)，将所有的矩阵元素累加起来只需要将三元组顺序表扫描一遍，其时间复杂度也为O(t)。当t<< m ×n 时，采用三元组顺序表存储可以获得较好的时间及空间性能。 4．广义表和线性表的区别与联系。 【参考答案】：广义表是线性表的推广，线性表是广义表的特例。当广义表中的元素都是原子时，即为线性表。

习题5

1．设矩阵A 为

?????

???????00

04

003003004002

(1)若将A 看作对称矩阵，画出对其进行压缩存储的存储表示，并讨论如何存取A 中元素a ij (0≤i ，j<4)。

(2)若将A 看作稀疏矩阵，画出A 的十字链表存储结构。 【参考答案】：

下标 1 2 3 4 5 6 7 8 9 10

数据结构与算法习题及答案

第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--;} elsex++; （2）for(i=0;i

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

党员干部十九党知识考试试题及答案 一、单选题 中国共产党第十九次全国代表大会召开时间（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章绪论 1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。 答案： 数据：是客观事物的符号表示，指所有能输入到计算机中并被计算机程序处理的符号的总称。如数学计算中用到的整数和实数，文本编辑所用到的字符串，多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。 数据元素：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。在有些情况下，数据元素也称为元素、结点、记录等。数据元素用于完整地描述一个对象，如一个学生记录，树中棋盘的一个格局（状态）、图中的一个顶点等。 数据项：是组成数据元素的、有独立含义的、不可分割的最小单位。例如，学生基本信息表中的学号、姓名、性别等都是数据项。 数据对象：是性质相同的数据元素的集合，是数据的一个子集。例如：整数数据对象是集合N={0，±1，±2，…}，字母字符数据对象是集合C={‘A’，‘B’，…，‘Z’，‘a’，‘b’，…，‘z’}，学生基本信息表也可是一个数据对象。 数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。换句话说，数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。 逻辑结构：从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。 存储结构：数据对象在计算机中的存储表示，也称为物理结构。 抽象数据类型：由用户定义的，表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称。具体包括三部分：数据对象、数据对象上关系的集合和对数据对象的基本操作的集合。 2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。 答案： 例如有一张学生基本信息表，包括学生的学号、姓名、性别、籍贯、专业等。每个学生基本信息记录对应一个数据元素，学生记录按顺序号排列，形成了学生基本信息记录的线性序列。对于整个表来说，只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录)，其他的结点则各有一个也只有一个直接前趋和直接后继。学生记录之间的这种关系就确定了学生表的逻辑结构，即线性结构。 这些学生记录在计算机中的存储表示就是存储结构。如果用连续的存储单元(如用数组表示)来存放这些记录，则称为顺序存储结构；如果存储单元不连续，而是随机存放各个记录，然后用指针进行链接，则称为链式存储结构。 即相同的逻辑结构，可以对应不同的存储结构。 3．简述逻辑结构的四种基本关系并画出它们的关系图。 答案： （1）集合结构 数据元素之间除了“属于同一集合”的关系外，别无其他关系。例如，确定一名学生是否为班级成员，只需将班级看做一个集合结构。 （2）线性结构 数据元素之间存在一对一的关系。例如，将学生信息数据按照其入学报到的时间先后顺序进行排列，将组成一个线性结构。 （3）树结构

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

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

哈工大2007材料分析方法秋考题--A

哈工大 2007年 秋 季学期 材料分析测试方法 试题 一、回答下列问题（每题5分，共50分） 1. 阐述特征X 射线产生的物理机制 答 当外来电子动能足够大时，可将原子内层（K 壳层）中某个电子击出去，于 是在原来的位置出现空位，原子系统的能量因此而升高，处于激发态，为使系统能量趋于稳定，由外层电子向内层跃迁。由于外层电子能量高于内层电子能量，在跃迁过程中，其剩余能量就要释放出来，形成特征X 射线。 2. 衍射矢量与倒易矢量 在正点阵中，选定原点O ，由原点指向任意阵点的矢量g 为衍射矢量。 在倒易点阵中，由原点O*指向任意坐标为（h,k,l ）的阵点的矢量g hkl 称为倒 易矢量。表示为g hkl =ha*+kb*+lc*。它有以下几个特点：a ）垂直于正点阵中相应的（h,k,l ）平面，或平行于它的法向N hkl —；b ）其矢量长度等于正点阵中相应晶面间距的倒数，即g hkl=1/d hkl ；c ）倒易矢量g hkl 与相应指数的晶向[hkl]平行。 3. 结构因子的定义 结构因子是指一个单胞对X 射线的散射强度，其表达式为： )(21j j j lz ky hx i n j j hkl e f F ++=∑=π 由于衍射强度正比于结构因子模的平方，消光即相当于衍射线没有强度，因 此可通过结构因子是否为0来研究消光规律。 4. 衍射峰半高峰宽的含义及与晶粒尺寸的关系 在理想条件下，衍射峰强度只有一条线，但是在实际测量过程中，衍射峰总 是有一定宽度的。定义在衍射峰强度I=Imax/2处的强度峰宽度为半高峰宽。主要影响因素为晶粒尺寸，晶粒大小对衍射强度的影响可用θλ2sin 3 c V I =来表示。 5. 给出物相定性与定量分析的基本原理 定性相分析原理：每一种结晶物质都有其特定的结构参数，包括点阵类型、 晶胞大小、单胞中原子的数目及其位置等等，这些参数在X 射线衍射花样上均有所反映，到目前为止还没找到两种衍射花样完全相同的物质；对于多种物相的X 射线谱，其衍射花样互不干扰，只是机械地叠加；物相定性分析是一种间接的方法，需利用现有的数据库进行物相检索。 定量相分析原理：各相的衍射线强度随该相含量的增加而提高。 6. 内应力的分类及对X 射线衍射线条的影响规律

数据结构课后习题答案

数据结构习题集答案 第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 元的值

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

第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)

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

文档来源为:从网络收集整理.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 )

电路分析试题库(有答案)77471

试题库（1）直流电路 一、填空题 1、电流所经过的路径叫做 电路 ，通常由 电源 、 负载 和 传输环节 三部分组成。 2、无源二端理想电路元件包括 电阻 元件、 电感 元件和 电容 元件。 3、通常我们把负载上的电压、电流方向（一致）称作 关联 方向；而把电源上的电压和电流方向（不一致）称为 非关联 方向。 4、 欧姆 定律体现了线性电路元件上电压、电流的约束关系，与电路的连接方式无关； 基尔霍夫 定律则是反映了电路的整体规律，其中 KCL 定律体现了电路中任意结点上汇集的所有 支路电流 的约束关系， KVL 定律体现了电路中任意回路上所有 元件上电压 的约束关系，具有普遍性。 5、理想电压源输出的 电压 值恒定，输出的 电流值 由它本身和外电路共同决定；理想电流源输出的 电流 值恒定，输出的 电压 由它本身和外电路共同决定。 6、电阻均为9Ω的Δ形电阻网络，若等效为Y 形网络，各电阻的阻值应为 3 Ω。 7、实际电压源模型“20V 、1Ω”等效为电流源模型时，其电流源=S I 20 A ，内阻=i R 1 Ω。 8、负载上获得最大功率的条件是 电源内阻 等于 负载电阻 ，获得的最大功率=min P U S 2/4R 0 。 9、在含有受控源的电路分析中，特别要注意：不能随意把 控制量 的支路消除掉。 三、单项选择题 1、当电路中电流的参考方向与电流的真实方向相反时，该电流（ B ） A 、一定为正值 B 、一定为负值 C 、不能肯定是正值或负值 2、已知空间有a 、b 两点，电压U ab =10V ，a 点电位为V a =4V ，则b 点电位V b 为（ B ） A 、6V B 、－6V C 、14V 3、当电阻R 上的u 、i 参考方向为非关联时，欧姆定律的表达式应为（ B ） A 、Ri u = B 、Ri u -= C 、 i R u = 4、一电阻R 上u 、i 参考方向不一致，令u =－10V ，消耗功率为，

数据结构习题及参考答案

习题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.前半句错，后半句对

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) 算法具有5个特性，分别是（输入）、（输出）、（有穷性）、（确定性）、（可行性）。 (6) 算法的描述方法通常有(自然语言)、(流程图)、(程序设计语言)、(伪代码)4种，其中，(伪代码)被称为算法语言。 (7) 一般情况下，一个算法的时间复杂度是算法（输入规模）的函数。 (8) 设待处理问题的规模为n,若一个算法的时间复杂度为一个常数，则表示成数量级的形式为(O(1))，若为n*log25n, 则表示成数量级的形式为(O(n*log2n))。 2. 选择题: (1) C, D (2) B (3) B (4) A (5) D (6) A (7) C (8) C, E 习题二 1. 填空题 (1) 在顺序表中，等概率情况下，插入和删除一个元素平均需移动(表长的一半)个元素，具体移动元素的个数与(表的长度)和(数据元素所在的位置)有关。 (2) 一个顺序表的第一个元素的存储地址是100，每个数据元素的长度是2，则第5个数据元素的存储地址是（108）。 (3) 设单链表中指针p指向单链表的一个非空结点A，若要删除结点A的直接后继，则需要修改指针的操作为（p->next=(p->next)->next, 或者q=p->next; p->next=q->next）。 (4) 单链表中设置头结点的作用是(方便运算,减少程序的复杂性，使得空表和非空表处理统一)。 (5) 非空的循环单链表由头指针head指示，则其尾结点(由指针p所指)满足(p->next=head)。 (6) 在有尾指针rear指示的循环单链表中，在表尾插入一个结点s的操作序列是（s->next=rear->next; rear->next=s; rear=s），删除开始结点的操作序列是（q=rear->next->next; rear->next->next=q->next; delete q;）。 注：假设此循环单链表有表头结点 (7) 一个具有n个结点的单链表，在p所指结点后插入一个新结点s的时间复杂性为（O(1)）；在给定值x的结点后插入一个新结点的时间复杂性为( O(n) ）。 (8) 可由一个尾指针惟一确定的链表有(循环链表)、(双链表)、(双循环链表)。 2. 选择题: (1) A,B (2) D (3) B (4) A (5) A (6) D (7) B (8) B (9) C (10) B (11) B (12) D (13) A (14) A 5. 算法设计 (1)设计一个时间复杂度为O(n)的算法。实现将数组A[n]中所有元素循环左移k个位置。 算法思想：要使a1…a k a k+1…a n -> a k+1…a n a1…a k,可以先让a1…a k a k+1…a n->a k…a1a n…a k+1,再让a k… a1 a n…a k+1 -> a k+1…a n a1…a k，参见第1章16页的思想火花 算法：void converse(T a[], int i, int j){ for(s=i; s<=(i+j)/2;s++) //将数组a中从i到j中的元素倒置 {temp=a[s];a[s]=a[j-s+i];a[j-s+i]=temp;} } void move(T a[ ], k) {converse(a,0,k-1);//3次调用函数converse converse(a,k,n-1);

数据结构课后习题及答案

填空题（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; 求串长*/

用矩阵方法使网孔分析法通解-电路分析基础课程设计

用矩阵方法使网孔分析法通解 黄明康 5030309754 F0303025 在网络电路的学习中，我们一般使用结点分析法与网孔分析法。我们知道他们有各自的用途，但其实如果使用得当，只用其中的一个方法就可以解所有目前已经可解得网络电路。而在我看来这得当的使用就是巧妙运用数学。之所以如此，我认为是因为结点分析法的基础ＫＣＬ与网孔分析法的基础ＫＶＬ是相容的，即可以用结点分析法的地方就可以用网孔分析法解题。 先来看个例子，从网孔分析法说起，如图（１）所示，是一个非常适合用结点分析法与网孔分析法解题的网络。 正如上课时所做的，我们用网孔分析法解之，以im1、im2、im3为支路电流列出回路的矩阵方程，方程如式（２）。

最左边的矩阵是各回路的电阻矩阵，解出此方程，再根据ＶＣＲ就能得出整个网路电路的各个参数。由于篇幅所限，也由于这已是大家皆知的常规方法，对于为何使用这种方法及其可用性、使用方法等在此不再冗述。 而我关心的是，这种方法是在这么一个可以说是完美的电路网络中运用的，所以一旦电路中的某个器件变了，可能使这种方法不可用。而其实上课时已经提出了这种问题，也给出了改进了的解题方法——运用网路电路的一些性质化解电路成可用网孔分析法的电路。 但这种方法在解题中会使不熟练的我不经意中掉入“陷阱”。我更愿意用以下的方法用数学解题，这样可以使我们不必太过计较概念。 对于我的方法，也请先看一个例子，如图（３）: 这样，这个电路就不能单纯的运用网孔分析法了。那么按之前所述，运用网路电路的一些性质化解电路成可用网孔分析法的电路，然后解之，正如图（４）

a 和图（４） b 中所示过程。 然后得出电阻网络矩阵方程，解出所要的量。 对于以上的例题，也有所谓的虚网孔电流法如式（５）： 其实，虚网孔电流法仅仅只是根据我们在网孔分析法的引出中得出的规律重新又列出了简单的方程组，这跟我们最初想要使用结点分析法和网孔分析法的初衷不符，初衷是按给出的网络电路图直接写出矩阵方程。这样就使我们可以更好的应对复杂的网络。 当然，也正是虚网孔电流法使我想起了网孔分析法的一般矩阵解法。仍就看图（３）：

数据结构习题与答案

第 1 章绪论 课后习题讲解 1. 填空 ⑴（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 【解答】数据元素 ⑵（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。 【解答】数据项，数据元素 【分析】数据结构指的是数据元素以及数据元素之间的关系。 ⑶从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。 【解答】集合，线性结构，树结构，图结构 ⑷数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）和（）。 【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系 ⑸算法具有五个特性，分别是（）、（）、（）、（）、（）。 【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性 ⑹算法的描述方法通常有（）、（）、（）和（）四种，其中，（）被称为算法语言。 【解答】自然语言，程序设计语言，流程图，伪代码，伪代码 ⑺在一般情况下，一个算法的时间复杂度是（）的函数。 【解答】问题规模 ⑻设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若为n*log25n，则表示成数量级的形式为（）。 【解答】Ο(1)，Ο(nlog2n) 【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。 2. 选择题 ⑴顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链接存储结构中的数据元素之间的逻辑关系是由（）表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针 【解答】C，D 【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。

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

第一章绪论 一、选择题 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.算法的五个重要特性是_______、_______、______、_______、