习题一
一、选择题
1、数据结构是一门研究非数值计算的程序设计问题中的操作对象以及它们之间的（B）和运算的学科。
A．结构B．关系C．运算D．算法
2、在数据结构中，从逻辑上可以把数据结构分成（C）。
A．动态结构和静态结构B．紧凑结构和非紧凑结构
C．线性结构和非线性结构D．逻辑结构和存储结构
3、线性表的逻辑顺序和存储顺序总是一致的，这种说法（B）。树形
A．正确B．不正确C．无法确定D．以上答案都不对
4、算法分析的目的是（C）。
A．找出算法的合理性B．研究算法的输人与输出关系
C．分析算法的有效性以求改进D．分析算法的易懂性
二、填空题
1、__数据___是信息的载体，是对客观事物的符号表示，它能够被计算机识别、存储、加工和处理，___数据_____是对能够有效的输人到计算机中并且能够被计算机处理的符号的总称。例如，数学中所用到的整数和实数，文本编辑所用到的字符串等。
2、数据元素是数据的__基本单位_，有些情况下也称为元素、结点、顶点、记录等。
3、__数据项__是数据不可分割的最小单元，是具有独立含义的最小标识单位。例如构成一个数据元素的字段、域、属性等都可称之为__数据项_。
4、简而言之，数据结构是数据之间的__相互关系_，即数据的_组织关系_。
5、数据的逻辑结构是指数据之间的_逻辑关系_。逻辑结构是从_逻辑关系_上描述数据，它与具体存储无关，是独立于计算机的。因此逻辑结构可以看作是从具体问题抽象出来的_数学模型_。
6、数据的__存储结构_指数据元素及其关系在计算机存储器内的表示。__存储结构_是逻辑结构在计算机里的实现，也称之为映像。
_数据的运算__是指对数据施加的操作。它定义在数据的逻辑结构之上，每种逻辑结构都有一个__数据的运算___。常用的有：查找、排序、插人、删除、更新等操作。
8、数据逻辑结构可以分为四种基本的类型，_集合_结构中的元素除了仅仅只是同属于一个___集合__，不存在什么关系。
9、数据逻辑结构的四种基本类型中，_线性结构_中的元素是一种一对一的关系，这种结构的特征是：若结构是非空集，则有且只有一个开始结点和一个终端结点，并且所有结点最多只能有一个直接前驱和一个直接后继。
10、数据逻辑结构的四种基本类型中，__树型结构_中的元素是一种一对多的关系。
11、图型结构或图状结构是一种__多对多__的关系。在这种逻辑结构中，所有结点均可以有多个前驱和多个后继。
12、有时也可将树型结构、集合和图型结构称为__非线性结构_，这样数据的逻辑结构就可以分为_线性结构_和__非线性结构__两大类。
13、__顺序存储__方式是指逻辑上相邻的结点被存储到物理上也相邻的存储单元中。这种存储结构只存储结点的数值，不存储结点之间的关系，结点之间的关系是通过存储单元的相邻关系隐含的表示出来的。
14、_链接存储_方式是种存储方法，不要求逻辑上相邻的结点在物理上也相邻，即数据元素可以存储在任意的位置上。
_稠密索引_和__稀疏索引_。若每个结点在索引表中都有
一个索引项，则该种索引存储方式称为_稠密索引_；若一组结点在索引表中只对应一个索引项，则索引存储方式称为_稀疏索引_。在_稠密索引中，索引项的地址指示结点所在的位置，而
方式是利用结点关键字的值直接计算出该结点存储单元地址，然后将结点按某种方式存人该地址的一种方法。
17、所谓算法（Algorithm）是对特定问题求解方法和步骤的一种描述，它是指令的一组___有限序列__，其中每个指令表示一个或多个操作。
18、算法的_有穷_性是指算法必须能够在执行有限个步骤之后结束，并且每个步骤都必须在有穷的时间内完成。
19、算法的__确定_性是指算法中的每一个步骤必须是有明确定义的，不允许有模棱两可的解释，也不允许有多义性。并且，在任何条件下，算法只能有惟一的一条执行路径，即只要输人是相同的就只能得到__相同__的输出结果。
20、算法的__可行__性又称为算法的能行性，是指算法中描述的操作是可以通过已经实现的基本运算执行__有限__次来实现，即算法的___具体实现_应该能够被计算机执行。
21、判断一个算法的好坏主要以下几个标准：__正确性_、__可读性_、__健壮性_、__效率__。
22、算法分析是对一种算法所消耗的计算机资源的估算，其中包括计算机__运行时间_的长短和___所占据空间__的大小。
23、空间复杂度（SPace ComPlexity）也是度量一个算法好坏的标准，它所描述的是算法在运行过程中所占用__存储空间___的大小。
三、判断题
1、顺序存储方式只能用于存储线性结构。（×）树形
2、数据元素是数据的最小单位。（×）数据项
3、算法可以用不同的语言描述，如果用C语言或PASCAL语言等高级语言描述，则算法实际上就是程序了。（×）
4、数据结构是带有结构的数据元素的集合。（√）
5、数据的逻辑结构是指各元素之间的逻辑关系，是用户根据需要而建立的。（√）
6、数据结构、数据元素、数据项在计算机中的映像分别称为存储结构、结点、数据域。
（√）
7、数据的物理结构是指数据在计算机中实际的存储形式。（√）
8、具有存取任一元素的时间相等这一特点的存储结构称为随机存取结构。（√）
四、综合题
1、用大O形式表示下面算法的时间复杂度：
for（i=0；i＜m；i十十）
for（j=0；j＜n；j＋＋）
A[i][j]=i*j；O（m×n）
2、写出下面算法的时间复杂度：
i＝0；
s=0；
while(s＜n）｛i++;
s+=i;
｝
3、写出以下算法的时间复杂度：
for（i＝0; i＜m; i＋＋）
for（j＝0 ; j＜t; j＋＋）
c[i][j]=0；
for（i=0；i＜m；i＋＋）
for（j=o; j for（k=0；k＜n；k＋＋） c［i］［j］＋＝a［i］［k］*b[k][j]; O(m×n×t)。 4、写出下面算法的时间复杂度： while（i＜＝n） i=i*3; O（log3(n)） 5、求下面函数中各条语句的频度和算法的时间复杂度： prime（int n） ｛ int i＝2； while ((n％i）！=0＆＆i＜sqrt(n) ) i++; if（i＞sqrt(n) ) printf（”％d is a prime number.＼n”，n）； else printf（”％d is not a prime number.＼n”，n）；｝ { if(n<=1) return 1; else return (n*fact(n-1)); } O（n） 习题二 一、选择题 1．在一个长度为n的顺序表中删除第i个元素（0＜i A．n-i B．n-i+1 C．n-i+1 D．i+1 2．从一个具有n个元素的线性表中查找其值等于x的结点时，在查找成功的情况下，需平均比较( D )个元素结点。 A．n/2 B．n C．(n-1)/2 D．(n +1)/2 3．对一个具有n个元素的线性表，建立其单链表的时间复杂度为( A )。 A．O(n) B．O(1) C．O(n2）D．O（long2n）4．线性表采用链式存储时，其地址( D )。 A．必须是连续的B．一定是不连续的 C．部分地址必须连续D．连续与否均可以 5．在一个具有n 法的时间复杂度是(D )。 A．O（long2n）B．O（l）C．O（n2） 6．线性表是( A)。 A．一个有限序列，可以为空B．一个有限序列，不可以为空 C．一个无限序列，可以为空D．一个无限序列，不可以为空7．在一个长度为n的顺序表中，向第i个元素（0 A．n-i B．n-i＋1 C．n－i－1 D．i＋1 8．如果某链表中最常用的操作是取第i个结点及其前驱，则采用( B)存储方式最节省时间。 A．单链表B．双向链表C．单循环链表D．顺序表9．一个顺序存储线性表的第一个元素的存储地址是90，每个元素的长度是2，则第6个元素的存储地址是（B）。 98 B．100 C．102 D．106 ( C )。 B．冒泡排序C．直接插人排序D．快速排序 C）。 A．以顺序方法存储 B．以链接方法存储 C．以顺序方法存储，且结点接关键字有序排列 D．以链接方法存储，且结点接关键字有序排列 12．在顺序存储的线性表（a1……a n）中，删除任意一个结点所需移动结点的平均移动次数为( C ) (n（n+1）)/2*1/n A．n B．n／2 C．(n-1)/2 D．（n＋l）/2 13．在线性表的下列存储结构中，读取元素花费的时间最少的是（D）。 A．单链表B．双链表C．循环链表D．顺序表14．若某链表中最常用的操作为在最后一个结点之后插入一个结点和删除最后一个结点，则采用（D）存储方式最节省时间。 A．双链表B．单链表C．单循环链表D．带头结点的双循环链表 15.已知L是没有头结点的单链表的头指针，且p所指向的结点既不是第一个结点，也不是最后一个结点，试从下列提供的语句中选取出合适的语句序列。（将语句序号填入横线 中） (1)在p所指向结点之后插入s所指向的结点：。 (2)在p所指向结点之前插入s所指向的结点：。 (3)在单链表L首插入s所指向的结点：。 (4)在单链表L后插入s所指向的结点：。 提供的语句： A. p->next=s; H. q=p; B. p->next=p->next->next; I. while(p->next!=q) p=p->next; C. p->next=s->next; J. while(p->next!=NULL) p=p->next; D. s->next=p->next; K. p=q; E. s->next=L; L. p=L; F. s->next=p; M. L=s; G. s->next=NULL; N. L=p; 二、填空题 1．线性表（Linear List）是最简单、最常用的一种数据结构。线性表中的元素存在着__一对一_的相互关系。 2．线性表中有且仅有一个开始结点，表中有且仅有一个终端结点，除开始结点外，其他每个元素有且仅有一个__直接前驱_，除终端结点外，其他每个元素有且仅有一个_直接后继_。 3．线性表是n（n>=0）个数据元素的__有限序列_。其中n为数据元素的个数，定义为线性表的__长度_。当n为零时的表称为__空表_。 4．所谓顺序表（Sequential LISt）是线性表的__顺序存储结构_，它是将线性表中的结点按其__逻辑顺序_依次存放在内存中一组连续的存储单元中，使线性表中相邻的结点存放在__地址相邻_的存储单元中。 5．单链表不要求逻辑上相邻的存储单元在物理上也一定要相邻。它是分配一些_任意__的存储单元来存储线性表中的数据元素，这些存储单元可以分散在内存中的__任意_的位置上，它们在物理上可以是一片连续的存储单元，也可以是__不连续__的。因此在表示线性表这种数据结构时，必须在存储线性表元素的同时，也存储线性表的逻辑关系。 6．线性表的链式存储结构的每一个结点（Node）需要包括两个部分：一部分用来存放元素的数据信息，称为结点的_数据域_；另一部分用来存放元素的指向直接后继元素的指针(即直接后继元素的地址信息)，称为_指针域_或___链域__。 7．线性链表的逻辑关系是通过每个结点指针域中的指针来表示的。其逻辑顺序和物理存储顺序不再一致，而是一种__非顺序_存储结构，又称为__非顺序映像_。 8．如果将单链表最后一个结点的指针域改为存放链表中的头结点的地址值，这样就构成了__循环链表_。 9．为了能够快速地查找到线性表元素的直接前驱，可在每一个元素的结点中再增加一个指向其前驱的指针域，这样就构成了__双向链表_。 10．双向链表某结点的指针P，它所指向结点的后继的前驱与前驱的后继都是_p所指向的结点本身_。 11．在单链表中，删除指针P所指结点的后继结点的语句是__ P->next=p->next->next __。 12．在双循环链表中，删除指针P所指结点的语句序列是P->prior->next＝p->next及_ P->next->prior=P->prior _。 13．单链表是___线性表__的链接存储表示。 __双链表__表示树形结构。 15．向一个长度为n的向量的第i个元素(l≤i≤n+1）之前插人一个元素时，需向后移动__n-i+1__个元素。 16．删除一个长度为n的向量的第i个元素（l≤i≤n）时，需向前移动__n-i_个元素。 17．在单链表中，在指针P所指结点的后面插人一个结点S的语句序列是__ S->next=P->next; P->next=S __。 18．在双循环链表中，在指针P所指结点前插人指针S所指的结点，需执行语句_ 。 。 20．在一个具有n个结点的有序单链表中插人一个新结点并使之仍然有序的时间复杂度为___ O(n)_。 21．写出带头结点的双向循环链表L为空表的条件__(L==L->Next) && (L==L->Prior)_。 __线性__结构。 __顶_针，再存人元素。 三、判断题 1．线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。（×） 2．在具有头结点的链式存储结构中，头指针指向链表中的第一个数据结点。(×) 3．顺序存储的线性表不可以随机存取。（×） 4．单链表不是一种随机存储结构。（√） 5．顺序存储结构线性表的插入和删除运算所移动元素的个数与该元素的位置无关。(×) 6．顺序存储结构是动态存储结构，链式存储结构是静态存储结构。（×） 7．线性表的长度是线性表所占用的存储空间的大小。（×） 数组描述的链表叫静态链表 8．双循环链表中，任意一结点的后继指针均指向其逻辑后继。（×） 9．线性表的惟一存储形式是链表。（×） 四、综合题 1．编写一个将带头结点单链表逆置的算法。 void reverse_list( LinkList L) { /*逆置带头结点的单链表*/ LinkList s, p; p=L->next; /*p指向线性表的第一个元素*/ L->next=NULL; /*初始空表*/ while ( p != NULL ) { s=p; p=p->next; s->next=L->next; L->next=s; /*将s结点插入逆表*/ } } /*reverse_list*/ 2．ha和hb分别是两个按升序排列的、带头结点的单链表的头指针，设计一个算法， 把这两个单链表合并成一个按升序排列的单链表，并用hC指向它的头结点。 void mergelist(LinkList *La,LinkList *Lb,LinkList *Lc) { LinkList pa,pb,pc; pa=(*La)->next; pb=(*Lb)->next; *Lc= *La ,pc =*La; while (pa&&pb) if(pa->data<=pb->data) { pc->next=pa; pc=pa; pa=pa->next; } else { pc->next=pb; pc=pb; pb=pb->next; } pc->next=pa?pa:pb; free(*Lb); } 3．有一个带头结点的单链表，头指针为L，编写一个算法count．list（）计算所有数据域为X的结点的个数（不包括头结点）。 int count_list(LinkList L ) { /*在带头结点的单链表中计算所有数据域为x的结点的个数*/ LinkList p; int n; p=L->next; /*p指向链表的第一个结点*/ n=0; while (p!=NULL) { if (p->data==x) n++; p=p->next; } return(n); /*返回结点个数*/ } /*count_list*/ 4．在一个带头结点的单链表中，头指针为L，它的数据域的类型为整型，而且按由小到大的顺序排列，编写一个算法insertx＿list（），在该链表中插人值为x的元素，并使该链表仍然有序。 void insert_list(LinkList L,int x){ LinkList p,q,s; p=L->next; q=L; while(p&&x>p->data){q=p;p=p->next;} s=(LinkList)malloc(sizeof(Lnode)); s->data=x; s->next=p; q->next=s; } 5．在一个带头结点的单链表中，L为其头指针，p指向链表中的某一个结点，编写算法swapin．list（），实现p所指向的结点和p的后继结点相互交换。 int swapin_list(LinkList head, LinkList p) { /*在带头结点的单链表中，实现p所指向的结点和p的后继结点相互交换*/ LinkList q, r, s; q=p->next; /*q为p的后继*/ if (q !=NULL) /*若p有后继结点*/ { if (p==head) /*若p指向头结点*/ { head=head->next; s=head->next; head->next=p; p->next=s; } else /*p不指向头结点*/ { r=head; /*定位p所指向结点的前驱*/ while (r->next != p) r=r->next; r->next=q; /*交换p和q所指向的结点*/ p->next=q->next; q->next=p; } return OK; } else /*p不存在后继*/ return ERROR; }/*swapin_list*/ 6．有一个带头结点的单链表，所有元素值以非递减有序排列，L为其头指针，编写算法deldy．list（）将该链表中多余元素值相同的结点删除。 void deldy_list(LinkList head) { /*在带头结点的非递减有序单链表，将该链表中多余的元素值相同的结点删除*/ LinkList q; if (head->next!= NULL)/*判断链表是否为空*/ { p=head->next; while (p->next != NULL ) { if ( p->data != p->next->data ) p=p->next; else { q=p->next;/*q指向p的后继*/ p->next=q->next; /*删除q所指向的结点*/ free(q); /*释放结点空间*/ } } /*while*/ } /*if*/ } /*deldy_list*/ 7．在带头结点的单链表中，设计算法dellistmaxmin，删除所有数据域大于min，而小于max的元素。 void dellist_maxmin(LinkList head, int min, int max ) { LinkList p, q; q=head; p=head->next; while(p!=NULL) /*结点不空*/ if ((p->data<=min) || (p->data>=max)) /*不满足删除条件*/ { q=p; p=p->next; } else /*满足删除条件*/ { q->next=p->next; free(p); p=q->next; } } /*dellist_maxmin*/ 8．设计一个将双链表逆置的算法invert．dbLinkList（），其中头指针为L，结点数据域为data，两个指针域分别为prior和next。 void invert_dblinklist(DLinkList head )//不带头结点的双向链表 { /*将head指向的双链表逆置*/ DLinkList p, q; p=head; while( p->next ) { q=p->next;. p->next=p->prior; p->prior=q; p=q; } q=p; p->next=p->prior; p->next=NULL; head=q; } /*invert_dblinklist*/ 习题三 一、选择题 l．一个栈的序列是：a，b，c，d，e，则栈的不可能输出的序列是（C）。 A．a，b，c，d，e B．d，e，c，b，a C．d，c，e，a，b D．e，d，c，b，a 2．若一个栈的输人序列是1，2，3，…，n，输出序列的第一个元素是n，则第k个输出元素是（C ）。 k B．n-k-1 C．n-k+1 D．不确定 S（最多有n个元素）为空的条件是（B ）。 ．S->top！＝0 B．S->top= =0 C．S->top!=n D．S->top= =n S（最多有n个元素）为满的条件是（D）。 A．S->top!=0 B．S->top= =0 C．S->top!=n D．S->top= =n 5．向一个栈顶指针为top的链栈中插人一个*S结点的时候，应当执行语句（B）。 A．top->next=S；B．S->next=top；top=S； C．S->next＝top->next；top->next＝S；D．S->next＝top；top＝S->next； 6．向一个带头结点、栈顶指针为top的链栈中插人一个*S结点的时候，应当执行语句（C）。 A．top->next=S；B．S->next=top；top=S； C．S->next=top->next；top->next=S；D．S->next=top；top=S->next； 7．判定一个队列Q（最多有n个元素）为空的条件是（C ）。 A．Q->rear-Q->front= =n B．Q->rear-Q->front+1= =n C．Q->rear = = Q->front D．Q->rear +1= = Q->front 8．判定一个队列Q（最多有n个元素）为满的条件是（A）。 A．Q->rear-Q->front= =n B．Q->rear-Q->front+1= =n C．Q->rear = = Q->front D．Q->rear +1= = Q->front 9．判定一个循环队列Q（最多有n个元素）为空的条件是（A）。 A．Q->rear = = Q->front B．Q->rear = = Q->front＋l C．Q->front= =(Q->rear +1)％n D．Q->front= =(Q->rear -1)％n 10．判定一个循环队列Q（最多有n个元素）为满的条件是（C ）。 A．Q->rear = = Q->front B．Q->rear = = Q->front＋l C．Q->front= =(Q->rear +1)％n D．Q->front= =(Q->rear -1)％n 11．在一个链队列中，假定front和rear分别为头指针和尾指针，则插入一个结点*S的操作是（C ）。 A．front＝front->next B．S->next=rear；rear=S C．rear->next=S；rear=S D．S->next=front；front＝S 12．在一个链队列中，假定front和rear分别为头指针和尾指针，删除一个结点的操作是（A ）。 A．front=front->next B．rear=rear->next C．rear->next=front D．front->next＝rear 13．栈与队列都是（C ）。 A．链式存储的线性结构B．链式存储的非线性结构 C．限制存取点的线性结构D．限制存取点的非线性结构14．若进栈序列为l，2，3，4，则（C）不可能是一个出栈序列。 A．3，2，4，1 B．l，2，3，4 C．4，2，3，1 D．4，3，2，l 15．在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲 区，主机将要输出的数据依次写人该缓冲区，而打印机则从该缓冲区中取走数据打印。该缓冲区应该是一个（B ）结构。 A．堆栈B．队列C．数组D．线性表 二、填空 1．栈（stack）是限定在__表尾_一端进行插人或删除操作的线性表。在栈中，允许插人和删除操作的一端称为__栈顶_，而另一端称为__栈底__。不含元素的栈称为_空栈__。 2．在栈的运算中，栈的插人操作称为__进栈_或__入栈_，栈的删除操作称为__退栈_或__出栈__。 3．根据栈的定义，每一次进栈的元素都在原__栈顶元素_之上，并成为新的__栈顶元素__；每一次出栈的元素总是当前的__栈顶元素_，因此最后进栈的元素总是__最后出栈__，所以栈也称为_后进先出_线性表，简称为__LIFO__表。 4．栈是一种操作受到限制的线性表，是一种特殊的线性表，因此栈也有_顺序_和__链式__两种存储结构，分别称为__顺序栈__和___链栈__。 5．当栈满的时候，再进行人栈操作就会产生___溢出_，这种情况的溢出称为__上溢_；当栈空的时候，如果再进行出栈操作，也会__溢出__，这种情况下的溢出称为__下溢___。 6．栈的链式存储结构简称为__链栈_，是一种___特殊的单链表__。 7．人们日常计算用到的表达式都被称为__中缀表达式__，这是由于这种算术表达式的运算符被置于两个操作数中间。 8．计算机中通常使用__后缀表达式_，这是一种将运算符置于两个操作数后面的算术表达式。这种表达式是由波兰科学家谢维奇提出的，因此又称为__逆波兰式__。 9．队列（Queue）也是一种__特殊的线性表_，但它与栈不同，队列中所有的插人均限定在表的一端进行，而所有的删除则限定在表的另一端进行。允许插人的一端称为_队尾_，允许删除的一端称为___队头__。 10．队列的特点是_先进先出_，因此队列又被称为___先进先出_．的线性表，或称为__FIFO__表。 11．队列的__顺序存储结构__又称为__数序队列_，是用一组地址连续的存储单元依次存放队列中的元素。 12．由于队列中的元素经常变化，对于队列的删除和插人分别在队头和队尾进行，因此需要设置两个指针分别指向_队头元素__和_队尾元素_，这两个指针又称为_队头指针__和__队尾指针__。 13．循环顺序队列（CircuLar Sequence Queue）经常简称为__循环队列_，它是将存储顺序队列的存储区域看成是一个首尾相连的一个环，即将队首和队尾元素连接起来形成一个环形表。首尾相连的状态是通过数学上的___取模运算__来实现的。 14．在算法或程序中，当一个函数直接调用自己或通过一系列语句间接调用自己的时候，则称这个函数为递归函数，也称为__自调用函数___。函数直接调用自己，则称为__直接递归调用_；当一个函数通过另一个函数来调用自己则称为___间接递归调用_。 15．在循环队列中规定：当Q->rear= =Q->front的时候循环队列为__空___，当（Q->rear+1）％MAXSIZE＝front的时候循环队列为___满____。 16．用链表方式表示的队列称为___链队列___。 17．已知栈的输人序列为1，2，3，…，n，输出序列为a1，a2，…，a n，符合a2= =n 的输出序列共有___n-1_个_。 18．一个栈的输人序列是12345，则栈的输出序列为43512是__不可能__（填是否可能）。 19．一个栈的输人序列是12345，则栈的输出序列为12345是___可能的_（填是否可能）。 20．设sq[1．．maxsize]为一个顺序存储的栈，变量top指示栈顶元素的位置，则作入栈操作的条件是____top-1< maxsize 。 21．设sq[1．．maxsize]为一个顺序存储的栈，变量top指示栈顶元素的位置，如果把栈顶元素弹出并送到X中，则需执行语句___ x=sq[top]; top=top-1___。 22．栈的特性是___先进后出___。 23．对栈进行退栈时的操作是先移动___栈顶指针_，后取出元素。 24．设s[1．．max]为一个顺序存储的栈，变量top指示栈顶位置，栈为满的条件是_ top==max+1。 25．设链栈的栈顶指针为top（有头结点），则栈非空的条件是__top->next!=NULL__。 26．已知循环队列用数组data[1...n]存储元素值，用f，r分别作为头尾指针，则当前元素个数为_(n+r-f）%n__。 27．在一个循环队列中，队首指针指向队首元素。 28．队列中允许进行删除的一端称为___队头_。 29．链队列实际上是一个同时带有头指针和尾指针的单链表（1．．n），尾指针指向该单链表的第__n_个元素。 30．设双向链表链列为lq，lq的头指针为lq.Front，尾指针为lq.Rear，则队列为空的条件是_lq.Front==lq.Rear_。 31．从循环队列中删除一个元素，其操作是先取出一个元素，后移动___队头指针___。 32．队列中允许进行插入的一端称为_队尾__。 三、判断题 1．栈和队列都是限制存取点的线性结构。（√） （×） （×） 4．循环队列是顺序存储结构。（√） 5．循环队列不会产生溢出。（×） 6．循环队列满的时候rear= =front。（×） 7．在对链队列（带头结点）做出队操作时不会改变front指针的值。（√） 四、综合题 1．设有4个元素A、B、C和D进栈，给出它们所有可能的出栈秩序。 A、B、C、D A、B、D、C A、C、 B、D A、C、D、B A、D、C、B B、A、 C、D B、A、D、C B、C、A、D B、C、D、A B、D、 C、A C、B、A、D C、B、 D、A C、D、B、A D、C、B、A 2．输入n个10以内的数，每输入k（0＜=k＜=9），就把它插人到第k号队列中。最后 把10个队列中的非空队列按队列序号以从小到大的顺序串接成一条链，并输出该链中的所有元素。 3．假设用循环单链表实现循环队列，该队列只使用一个尾指针rear，其相应的存储结构和基本操作算法如下： (l) 初始化队列initqueue (Q)：建立一个新的空队列Q。 (2)人队列enqueue (Q，x)：将元素x插人到队列Q中。 (3)出队列delqueue (Q)：从队列Q中退出一个元素。 (4)取队首元素getL (Q)：返回当前队首元素。 (5)判断队列是否为空：emptyqueue (Q)。 (6)显示队列中元素：dispqueue (Q)。 4．“回文”是指一个字符串从头读到尾和从尾读到头都一样。假设字符串是从输人设备一次一个字节的读人，并且读到字符“＃”的时候表示结束。请用栈和队列编写一个算法判断一个字符串是否回文。 5．假设表达式中有三种括号：圆括号“（）”、方括号“[ ]”和花括号“{ }”用C语言编写程序判断读人的表达式中不同括号是否正确配对，假定读人的表达式以”#”结束。 6．用C语言编写背包问题的算法。背包问题的描述是：假设有n件质量分别为w1，w2，…，w n的物品和一个最多能装载总质量是T的背包，问能否从这n件物品中选择若干件物品装人背包，并且使被选物品的总质量恰好等于背包所能装载的最大质量，即W xl＋W x2＋…W xk＝T。若能，则背包问题有解，否则背包问题无解。 7．划分子集问题的求解。划分子集问题的实际例子很多，如：某个运动会设立n个比赛项目，每个运动员可以参加一到三个项目，考虑到同一运动员参加的项目不能够在同一时间内进行，则如何安排比赛日程才能使总的日程最短。又如：学校开设m科课程，不同的同学可能选修多门不同的课程，在学期末要进行考试，则如何安排这m科课程的考试才能使考试时间最短而又不冲突。 8．写出汉诺塔问题的递归和非递归算法。 汉诺塔问题描述为：有X、Y和Z三个柱子，n个大小不等且都能套进柱子的圆盘（编号为l、2、…、n），这n个圆盘已经按照自上至下、由小到大的顺序在其中的一根柱子X上，要求将这些圆盘按照如下规则由X柱子移动到Z柱子： (1) 每次只能移动柱子最上面的一个圆盘。 (2) 任何圆盘都不能放在比它小的圆盘之上。 (3) 圆盘只能在X、Y和Z三根柱子之上放置。 9．假设CQ[0…10]是一个环形队列，初始状态为front=rear=0，画出做完下列操作后队列的头尾指针的状态变化情况，若不能入队，请指出其元素，并说明理由。 (1) d,e,b,g,h入队(2)d,e出队(3)i,j,k,l,m入队(4)b出队(5) n,o,p入队 习题四 一、选择项 l．空串与空格串（B）。 A．相同B．不相同C．可能相同D．无法确定2．设有两个申S1与S2，求串S2在S1中首次出现位置的运算称作（C ）。 A．连接B．求子串C．模式匹配D．判子串3．串与普通的线性表相比较，它的特殊性体现在（C）。 A．顺序的存储结构B．链接的存储结构 C．数据元素是一个字符D．数据元素可以任意 4．设有串S=‘Computer’，则其子串的数目是（B ）。(n *（n+1）/2+1) A．36 B．37 C．8 D．9 二、境空题 1．串是由零个或多个字符组成的__有限序列_。通常记作：s＝“c1，c2，…，c n”(n=>0)，其中，S称为__串名_；串中的C i（1<=i<=n）可以是字母、数字字格或其他字符。用双引号括起来的部分是_串值_．即串S的内容。 2．串中字符的个数称为串的__长度__。 3．不含有任何字符的串称为__空串_，它的长度为___零__。 4．由一个或多个空格构成的串称为__空格串__，它的长度为__空格的个数__。 5．串中任意多个连续字符组成的子序列称为该串的__子串__；包含_子串__的串称为主串。 6．字符在序列中的序号称为该字符在串中的__位置_。 7．两个字符串相等是指两个字符串的值相等，也就是说这两个字符串不仅_长度相等_，而且对应位置上的字符也相等。 8．两个串的比较实际上是__ ASCII码_的比较。两个串从第一个位置上的字符开始进行比较，当第一次出现__ ASCII码__大的串为大，若比较过程中出现一个字符串结束的情况，则另一个串为__较大者__。 __顺序存储__就是把串所包含的字符序列，依次存人连续的存储单元中去。 符，串的这种存储方式是一种___紧缩式存储结构__。 __非紧缩式存储结构__是以存储单元为存储单位，一个存储单元中只存放__一个字符_。在这种情况下，即使一个存储单元能存放多个字符，这时候也只存放___一个字符__。 __串所占用的存储单元的个数_即串的长度。 存储单元存放__一个字符_的分配方式，这种方式就是一种_单字节存储方式_。这种方式一般不需要存放__串长_的存储单元，而需要以程序中各变量值所不包含的字符为结束符。 14．串的链式存储结构是将存储区域分成一系列大小相同的结点，每个结点有两个城：_ 数据_域和___指针_域。其中___数据__域用于存放数据，__指针_域用于存放下一个结点的指针。 15．子串定位StrIndex (s，t)，也称为_模式匹配__，是返回串t在s主串中的位置。三、判断回 （×） 算法的最大特点是指示主串的指针不需要回溯。（√） 3．串中的元素只能是字符。（√） 4．串中的元素只可能是字母。（×） 5．串是一种特殊的线性表。（√） 6．串中可以包含有空白字符。（√） 7．串的长度不能为零。（×） 8．两个串相等必有串长度相同。（√） 9．两个串相等则各位置上字符必须对应相等。（√） 四、综合题 l．编写算法实现将窜S1中的第i个字符到第j个字符之间的字符(不包括第i个字符和第j个字符)之间的字符用串S2替换。假设串的存储结构为： ＃define MAXSIZE 81 struct string{ int len； char ch［MAXSIZE］； ｝stringtype； 2．设计一个算法，测试一个串S是否回文（所谓回文是指从左面读起和从右面读起内容一样）。 3．写一个递归算法来实现字符的逆序存储，要求不另设存储空间。 4．一个仅由字母组成的字符串s，长度为n，其结构为单链表，每个结点的数据城只存放一个字母。设计一个算法，去掉字符串中所有值为X的字母。 习题五 一、选择题 l．数组常用的两种基本操作是（D）。 A．建立与查找B．删除与查找C．插人与索引D．查找与修改2．对稀疏矩阵进行压缩存储，常用的两种方法是（B ）。 A．二元组和散列表B．三元组和十字链表 C．三角矩阵和对角矩阵D．对角矩阵和十字链表3．采用稀疏矩阵的三元组表形式进行压缩存储，若要完对三元组表进行成转置，只要将行和列对换，这种说法（B ）。 A．正确B．错误C．无法确定D．以上均不对4．一个广义表的表头总是一个广义表，这种说法（ B ）。 A．正确B．错误C．无法确定D．以上均不对5．一个广义表的表尾总是一个广义表，这种说法（A ）。 A．正确B．错误C．无法确定D．以上均不对6．广义表((a))的表头是（C ）。 A．（）B．a C．（a）D．（（a））7．广义表（（a））的表尾是（A ）。 A．（）B．a C．（a）D．（（a））8．广义表（（a），a）的表头是（C ）。 A．（）B．a C．（a）D．（（a））9．广义表（（a），a）的表尾是（C ）。 A．( ) B．a C．（a）D．（（a））10．广义表（a，b，c）的表头是（A ）。 A．a B．（a）C．a，b D．（a，b）11．广义表（a，b，c）的表尾是（B）。 A．b，c B．（b，c）C．a．b，c D．（a，b，c）12．广义表A满足Head（）= Tail（），则A为（B）。 A．（）B．（（））C（（），（））D．（（），（），（））二、填空题 1．数组（array）是n（n＞1）个__相同类型数据_的有序组合，数组中的数据是按顺序存储在一块___地址连续__的存储单元中。 2．数组中的每一个数据通常称为_数组元素_，__数组元素_用下标区分，其中下标的个数由数组的___维数__决定。 3．由于计算机内存中的存储单元是一个一维的存储结构，因此对于多维数组要想按顺序存储到计算机存储单元中就必须有一个排列顺序问题。对于二维数组，有两种排列形式：一种是__以行序为主序_；另一种是___以列序为主序_。 4．对于需要压缩存储的矩阵可以分为特殊矩阵和___稀疏矩阵_。对那些具有相同值元素或零元素在矩阵中分布具有一定规律的矩阵，我们称之为__特殊矩阵__；而对于那些零元素数目远远多于非零元素数目，并且非零元素的分布没有规律的矩阵称为___稀疏矩阵__。 5．在一个n阶方阵a中，若元素满足性质：a ij＝a ji（0<=i，j<=n-l），则称A为n阶__对称矩阵__。 6．采用顺序存储结构表示三元组表(Trope Table)，以实现对稀疏矩阵的一种压缩存储形式，称为__三元组顺序表_，简称____三元组__表。 7．___矩阵转置__运算是矩阵运算中最基本的一项，它是将一个m*n的矩阵变成另外 一个n*m的矩阵，同时使原来矩阵中元素的行和列的位置互换而值保持不变。 8．广义表是n（n>=0）个元素的序列。记作：A＝（a1，a2，…，a n），其中，A是广义表的__名称_，n是它的__长度__，当n=0的时候称为__空表__。 9．在一个非空的广义表中，其元素ai可以是某一确定类型的单个元素，称为___原子__，也可以又是一个广义表，称为____子表___。 10．广义表的定义是一种递归的定义，广义表是一种递归的数据结构。当广义表非空的时候，称第一个元素a l为广义表A的___表头__，称其余元素组成的表（a2，a3，…，a n）是A的____表尾__。 11．广义表的深度一般定义为广义表元素___最大的层数__，或者说是广义表__括号的重数___。利用递归的定义，广义表的深度就是所有子表中_____最大深度加1____。 三、判断题 1．十字链表不是顺序存储结构。（√） 2．三元组表不是一个随机存储结构。（√） 3．稀疏矩阵压缩存储后，必然会失去随机存取功能。（√） 4．若一个广义表的表头为空表，则此广义表也为空表。（×） 5．广义表是线性表的推广，是一类线性数据结构。（×） 6．任何一个非空广义表，其表头可能是单元素或广义表，其表尾必定是广义表。（√） 7．一个稀疏矩阵A m*n采用三元组形式表示，若把三元组中有关行下标与列下标的值互换，并把m和n的值互换，则就完成了A m*n的转置运算。（×） 8．数组中每个元素必定具有相同的数据类型。（√） 9．线性表是广义表的特例。（√） 10．如果广义表中的每个元素都是原子，则广义表便成为线性表。（√） 11．广义表中原子个数即为广义表的长度。（×） 12．广义表最大子表的深度为广义表的深度。（×） 13．广义表中元素最大的层数称为广义表的深度。（√） 14．广义表是一种多层次结构。（√） 15．广义表是一种线性结构。（×） 16．广义表是一种共享结构。（√） 17．广义表是一种递归结构。（√） 18．广义表是一种单链表结构。（√） 四、综合题 1．用二维数组实现“魔方阵”的打印，所谓“魔方降’是指满足每一行、每一列和对角线上的元素之和均相等的方阵。例如： 8 1 6 3 5 7 4 9 2 就是一个三阶的魔方阵。现在要求编程实现任意输人一个自然数n，打印出相应的n 阶魔方阵。 2．找出并打印一个二维数组中的鞍点，所谓鞍点是指该位置上的元素在该行上最大，在该列上最小。 3．写一个创建稀疏矩阵相应三元组的算法。 4．假设三元组元素值为整型，写一个查找三元组元素值为n的算法。 5．有两个稀疏矩阵的三元组triple_a和triple_b，请写出利用三元组这种数据结构，实 现将两个稀疏矩阵相加，最后的和存入三元组表triple_c 之中的算法。 6．有两个稀疏矩阵的三元组triple_a 和triple_b ，请写出利用三元组这种数据结构，实现将两个稀疏矩阵相乘，并将最后的乘积存人二元组表triple_c 之中的算法。 7．现有稀疏矩阵A 如图所示，要求画出以下各种表示法。 (1)三元组表示法 (2)十字链表表示法 习题六 一、选择题 l ．在二叉树后序遍历中，任一个结点均在其子女结点后面，这种说法（ ）。 A ．正确 B ．不正确 C ．无法判断 D ．以上均不对 2．在二叉树先序遍历中，任一个结点均在其子女结点前面，这种说法（ ）。 A ．正确 B ．不正确 C ．无法判断 D ．以上均不对 3．设深度为h 的二叉树上只有叶子结点和同时具有左右子树的结点，则此类二叉树中所包含的结点数目至少为（ ）。 A ．2h B ．2h C ．2h ＋1 D ．2h-l 4．二叉村第k 层上最多有（ ）个结点。 A ．2k B ．2k-1 C ．2k -1 D ．2k -1 5．二叉树的深度为k ，则二叉树最多有（ ）个结点。 A ．2k B ．2k-1 C ．2k-1 D ．2k -1 6．设某一二叉树先序遍历为abdec ，中序遍历为dbeac ，则该二叉树后序遍历的顺序是（ ）。 A ．abdec B ．debac C ．debca D ．abedc 7．设某一二叉树中序遍历为badce ，后序遍历为bdeca ，则该三叉树先序遍历的顺序是（ ）。 A ．adbec B ．decab C ．debac D ．abode 8．设某一二叉树先序遍历为abdecf ，后序遍历为debfca ，则该二叉树中序遍历的顺序是（ ）。 A ．adbecf B ．dfecab C ．dbeacf D ．abcdef 9．将一棵树T 转换为一棵二叉树T2，则T 的先序遍历是T2的（ ）。 A ．先序 B ．中序 C ．后序 D ．无法确定 10．将一棵树T 转换为一棵二叉树T2，则T 的后序遍历是T2的（ ）。 A ．先序 B ．中序 C ．后序 D ．无法碉定 ll ．树最适合于用来表示（ ）。 ??????????--028003600070500140 A．线性结构的数据B．顺序结构的数据 C．元素之间无前驱和后继关系的数据D．元素之间有包含和层次关系的数据12．二叉树的叶于结点在先序、中序和后序遍历过程中的相对秩序（）。 A．发生改变B．不发生改变 C．无法确定D．以上均不正确 13．设一棵二叉树度2的结点数是7，度为1的结点数是6，则叶子结点数是（）。 A．6 B．7 C．8 D．9 14．用顺序存储的方法，将完全二叉树中所有结点按层逐个从左到右的顺序存放在一维数组R[1．．n]中，若结点R[i]有左孩子，则其左孩子是（）。 A．R[2i-1] B．R[2i+1] C．R[2i] D．R[2/i] 15．用顺序存储的方法，将完全二叉树中所有结点按层逐个从左到右的顺序存放在一维数组R[1．．n]中，若结点R[i]有右孩子，则其右孩子是（）。 A．R[2i-1] B．R[2i＋l] C．R[2i] D．R[2/i] 16．一棵非空的二叉树，先序遍历与后序遍历正好相反，则该二叉树满足（）。 A．无左孩子B．无右孩子 C．只有一个叶子结点D．任意二叉树 17．设a、b为一棵二叉树的两个结点，在后序遍历中，a在b前的条件是（）。 A．a在b上方B．a在b下方 C．a在b左方D．a在b右方 18．线索二叉树是一种（）。 A．逻辑结构B．线性结构 C．逻辑和线性结构D．物理结构 19．N个结点的线索二叉树中，线索的数目是（）。 A．N-1 B．N＋1 C．2N D．2N－1 20．权值为｛l，2，6，8｝的四个结点构成的哈夫曼树的带权路径长度是（）。 A．18 B．28 C．19 D．29 21．实现任意二叉树的后序遍历的非递归算法而不使用栈结构，最佳方案是二叉村采用（）存储结构。 A．二叉链表B．广义表存储结构 C．三叉链表D．顺序存储结构 22．对一个满二叉树，m个树叶，k个分枝结点，n个结点，则（）。 A．n＝m＋1 B．m+1=2n C．m＝k-1 D．n=2k+1 23．具有五层结点的二叉平衡树至少有（）个结点。 A．10 B．12 C．15 D．17 24．设n，m为一棵二叉树上的二个结点，在中序遍历时，n在m前的条件是（）。 A．n在m右方B．n是m祖先 C．n在m左方D．n是m子孙 25．线索二又树是一种（）结构。 A．逻辑B．逻辑和物理C．物理D．线性26．将一棵有100个结点的完全二又树从根这一层开始，每一层上从左到有依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为（）。 A．98 B．99 C．50 D．48 二、填空题 1．树(Tree)是n(n≥0)个结点的_____________集。 第一章绪论 一、选择题 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.算法的五个重要特性是_______、_______、______、_______、 习题课 填空 1、对于一棵二叉树，若一个结点的编号为i，则它的左孩子结点的编号为，双亲结点的编号为。 2、向一个长度为n的向量中删除第i个元素(1≤i≤n)时，需向前移动个元素。 3、在一棵二叉树中，若双分支结点数为5个，单分支结点数为6个，则叶子结点数 为个。 4、为了实现折半查找，线性表必须采用方法存储。顺序 5、一种抽象数据类型包括数据对象和。 6、在以L为表头指针的带表头附加结点的单链表和循环单链表中，判断链表为空的条件分别为__________和_______。 7、数据结构被形式地定义为（D, R），其中D是的有限集合，R是D上的有限集合。 8、队列的插入操作在进行，删除操作在进行。 9、二叉搜索树的中序遍历得到的结点序列为____ ____。 10、在顺序表中插入或删除一个元素，需要平均移动元素，具体移动的元素个数与有关。 11、栈的特点是。 12、在单链表中，除了首元结点外，任一结点的存储位置由。 13、在一个具有n个顶点的无向图中，要连通所有顶点则至少需要条边。 14、深度为k（设根的层数为1）的完全二叉树至少有个结点，至多 有个结点。 15、一棵深度为6的满二叉树有个分支结点和个叶子结点。 16、一个算法的效率可分为效率和效率。 17、队列的特点是。 18、一棵深度为5的满二叉树中的结点数为个。 19、在一个具有n个顶点的无向完全图中，包含有________条边，在一个具有n个顶点的有向完全图中，包含有________条边。 简答题 1、已知一组元素为（38，26，62，94，35，50，28，55），画出按元素排列顺序输入生成的一棵二叉搜索树。 答: 2、假设有二维数组A[0..5,0..7]，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置（基地址）为1000，计算： （1）末尾元素A57的第一个字节地址为； （2）若按列存储时，元素A47的第一个字节地址为。 (3) 数组A的体积（存储量）； (4) 若按行存储时，元素A14的第一个字节地址为。 党员干部十九党知识考试试题及答案 一、单选题 中国共产党第十九次全国代表大会召开时间（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、城市人民政府城乡规划主管部门根据，组织编制城市的，经本级人民政府批准后，报本级人民代表大会常务委员会和上一级人民政府备案。 数据结构习题 第一章绪论 1.1数据结构是一门研究非数值计算的程序设计问题中计算机的___①__以及它们之间的__②_ 和运算等的学科。 ①A.数据元素B.计算方法C.逻辑存储D.数据映像 ②A.结构 B.关系 C.运算 D.算法 1.2 算法分析的目的是___①__ ，算法分析的两个主要方面是__②___ 。 ① A.找出数据结构的合理性 B.研究算法中的输入和输出的关系 C.分析算法的效率以求该进 D.分析算法的易懂性和文档性 ② A.空间复杂度和时间复杂度 B.正确性和简明性 C.可读性和文档性 D.数据复杂性和程序复杂性 1.3 计算机算法指的是__①__ ，它必须具备输入、输出和__②_ 等5个重要特性。 ① A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法 ② A.可读性、可移植性和可扩展性 B. 可读性、可移植性和有穷性 C.确定性、有穷性和可行性 D.易读性、稳定性和安全性 1.4数据元素是数据处理的基本单位；数据项是数据处理的_最小单位。 1.5数据结构是研究数据的逻辑结构___和__物理结构__，并对这种结构定义相适应的运算，设计出相应的算法，分析算法的效率。算法的效率包括时间和空间两个方面，分别称为_空间复杂度和时间复杂度。数据的逻辑结构是指_数据元素之间的关系__；包括线性结构、树形结构和图形结构三种类型,其中树形结构和图状结构合称为__非线性结构__。 1.6 线性结构中元素之间存在_一对一___ 关系，树形结构中元素之间存在_一对多___ 关系，图状结构中元素之间存在__多对多__ 关系。 1.7 数据结构在计算机中的表示称为数据的物理（或存储）结构，数据的物理结构可以采用_顺序存储和_链式存储__两种存储方法。 1.8顺序存储方法是把逻辑上相邻的元素存储在物理位置相邻的内存单元中；链式存储方法中元素间的关系是由__指针来表示_的。 第二章线性表 2.1 链表不具备的特点是____ 。 A.可随机访问任一结点 B.插入删除不需移动元素 C.不必事先估计存储空间 D.所需空间与其长度成正比 2.2 不带头结点的单链表head 为空的判定条件是____。 A. head==null B. head->next==null C. head->next==head D. head !=null 2.3带头结点的单链表head 为空的判定条件是____。 A. head==null B. head->next==null C. head->next==head D. head!=null 2.4 非空的循环单链表head 的尾结点（由p所指向）满足____。 A. p->next==null B. p==null C. p->next==head D. p==head 2.5 在一个具有n 个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是____。 A. O(1) B. O(n) C. O(n2) D. O(nlog2n) 2.6线性链表中各个结点之间的地址不一定连续。 2.7线性表中数据元素之间具有__一对一__，除第一个和最后一个元素外，其他数据元素有且只有_一个后 数据结构练习题(含答案) 数据结构练习题 习题1 绪论 1.1 单项选择题 1. 数据结构是一门研究非数值计算的程序设计问题中,数据元素的①、数据信息在计算机中的②以及一组相关的运算等的课程。 ① A．操作对象Ｂ．计算方法Ｃ．逻辑结构Ｄ．数据映象 ②A．存储结构Ｂ．关系Ｃ．运算Ｄ．算法 2. 数据结构DS(Data Struct)可以被形式地定义为DS=（D，R），其中D是①的有限集合，R是D上的②有限集合。 ① A．算法Ｂ．数据元素Ｃ．数据操作Ｄ．数据对象 ② A．操作Ｂ．映象Ｃ．存储Ｄ．关系 3. 在数据结构中，从逻辑上可以把数据结构分成。 A．动态结构和静态结构Ｂ．紧凑结构和非紧凑结构 Ｃ．线性结构和非线性结构Ｄ．内部结构和外部结构 4. 算法分析的目的是①，算法分析的两个主要方面是②。 ① A. 找出数据结构的合理性 B. 研究算法中的输 入和输出的关系 C. 分析算法的效率以求改进 D. 分析算法的易懂 性和文档性 ② A. 空间复杂性和时间复杂性 B. 正确性和简明性 C. 可读性和文档性 D. 数据复杂性和程序 复杂性 5. 计算机算法指的是①，它必具备输入、输出和②等五个特性。 ① A. 计算方法 B. 排序方法 C. 解决问题的有限运算序列 D. 调度方法 ② A. 可行性、可移植性和可扩充性 B. 可行性、确定性和有穷性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和安全性 1.2 填空题（将正确的答案填在相应的空中） 1. 数据逻辑结构包括、和三种类型，树形结构和图形结构合称为。 2. 在线性结构中，第一个结点前驱结点，其余每个结点有且只有个前驱结点；最后一个结点后续结点，其余每个结点有且只有个后续结点。 3. 在树形结构中，树根结点没有结点，其余每个结点有且只有个直接前驱结点，叶子结点没有结点，其余每个结点的直接后续结点可以。 4. 在图形结构中，每个结点的前驱结点数和后续结点数可以。 5. 线性结构中元素之间存在关系，树形结构中元素之间存在关系，图形结构中元素之间存在关系。 6. 算法的五个重要特性是__ __ , __ __ , ___ _ , 文档来源为:从网络收集整理.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. 填空 ⑴（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 【解答】数据元素 ⑵（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。 【解答】数据项，数据元素 【分析】数据结构指的是数据元素以及数据元素之间的关系。 ⑶从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。 【解答】集合，线性结构，树结构，图结构 ⑷数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）和（）。 【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系 ⑸算法具有五个特性，分别是（）、（）、（）、（）、（）。 【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性 ⑹算法的描述方法通常有（）、（）、（）和（）四种，其中，（）被称为算法语言。 【解答】自然语言，程序设计语言，流程图，伪代码，伪代码 ⑺在一般情况下，一个算法的时间复杂度是（）的函数。 【解答】问题规模 ⑻设待处理问题的规模为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.算法的五个重要特性是_______、_______、______、_______、_______。 7.数据结构的三要素是指______、_______和________。 8.链式存储结构与顺序存储结构相比较,主要优点是________________________________。 9.设有一批数据元素,为了最快的存储某元素,数据结构宜用_________结构,为了方便插入一个元素,数据结构宜用____________结构。 四、算法分析题 1.求下列算法段的语句频度及时间复杂度参考答案： 选择题1. C 2.C 3. C 4. A、B 5. C 6.C、B 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.数据结构就是一门研究非数值计算的程序设计问题中的操作对象以及它们之间的()与运算的学科。 A.结构 B.关系 C.运算 D.算法 2.在数据结构中,从逻辑上可以把数据结构分成()。 A.动态结构与静态结构 B.紧凑结构与非紧凑结构 C.线性结构与非线性结构 D.逻辑结构与存储结构 3.线性表的逻辑顺序与存储顺序总就是一致的,这种说法()。 A.正确 B.不正确 C.无法确定 D.以上答案都不对 4.算法分析的目的就是()。 A.找出算法的合理性 B.研究算法的输人与输出关系 C.分析算法的有效性以求改进 D.分析算法的易懂性 5、算法的时间复杂度取决于( ) A.问题的规模B待处理数据的初态 C、 A与B 6.一个算法应该就是( )。 A.程序 B.问题求解步骤的描述 C.要满足五个基本特性 D.A与C、 7、下面关于算法说法错误的就是( ) A.算法最终必须由计算机程序实现 B、为解决某问题的算法与为该问题编写的程序含义就是相同的 C、算法的可行性就是指指令不能有二义性 D、以上几个都就是错误的 8.以下与数据的存储结构无关的术语就是( )。 A.循环队列 B、链表 C、哈希表D、栈 9.在下面的程序段中,对x的赋值语句的频度为( ) for(i=0;i 第1章概论 1.数据、数据元素、数据结构、数据类型的含义分别是什么？ 数据：对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并由计算机程序处理的符号的总称。 数据元素：数据的基本单位，在计算机程序中通常作为一个整体考虑。 数据结构：数据元素之间的关系+运算，是以数据为成员的结构，是带结构的数据元素的集合，数据元素之间存在着一种或多种特定的关系。 数据类型：数据类型是用来区分不同的数据；由于数据在存储时所需要的容量各不相同，不同的数据就必须要分配不同大小的内存空间来存储，所有就要将数据划分成不同的数据类型。数据类型包含取值范围和基本运算等概念。 2.什么是数据的逻辑结构？什么是数据的物理结构？数据的逻辑结构与物理结构的区别和联系是什么？ 逻辑结构：数据的逻辑结构定义了数据结构中数据元素之间的相互逻辑关系。数据的逻辑结构包含下面两个方面的信息： ①数据元素的信息； ②各数据元素之间的关系。 物理结构：也叫储存结构，是指逻辑结构的存储表示，即数据的逻辑结构在计算机存储空间中的存放形式，包括结点的数据和结点间关系的存储表示。 数据的逻辑结构和存储结构是密不可分的，一个操作算法的设计取决于所选定的逻辑结构，而算法的实现依赖于所采与的存储结构。采用不同的存储结构，其数据处理的效率是不同的。因此，在进行数据处理时，针对不同问题，选择合理的逻辑结构和存储结构非常重要。 3.数据结构的主要操作包括哪些？ 对于各种数据结构而言，他们在基本操作上是相似的，最常用的操作有： ●创建：建立一个数据结构； ●清除：清除一个数据结构； ●插入：在数据结构中增加新的结点； ●删除：把指定的结点从数据结构中删除； ●访问：对数据结构中的结点进行访问； ●更新：改变指定结点的值或改变指定的某些结点之间的关系； ●查找：在数据结构中查找满足一定条件的结点； ●排序：对数据结构中各个结点按指定数据项的值，以升序或降序重新排列。 4.什么是抽象数据类型？如何定义抽象数据类型？ 抽象数据类型（Abstract Data Type 简称ADT）是指一个数学模型以及定义在此数学模型上的一组操作。ADT是与具体的物理存储无关的数据类型，因此，不论ADT的内部结构如何变化，只要其数据结构的特性不变，都不影响其外部使用。 对抽象数据类型的描述一般用（D,R,P)三元组表示，抽象数据类型的定义格式为： ADT<抽象数据类型名> { 数据对象D：<数据对象的定义> 数据关系R：<数据关系的定义> 基本操作P：<基本操作的定义> 习题1 一、单项选择题 A1.数据结构是指（）。 A.数据元素的组织形式 B.数据类型 C.数据存储结构 D.数据定义 C2.数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（）。 A.存储结构 B.逻辑结构 C.链式存储结构 D.顺序存储结构 D3.树形结构是数据元素之间存在一种（）。 A.一对一关系 B.多对多关系 C.多对一关系 D.一对多关系 B4.设语句x++的时间是单位时间，则以下语句的时间复杂度为（）。 for(i=1; i<=n; i++) for(j=i; j<=n; j++) x++; A.O(1) B.O(2n) C.O(n) D.O(3n) CA5.算法分析的目的是（1），算法分析的两个主要方面是（2）。 （1） A.找出数据结构的合理性 B.研究算法中的输入和输出关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 （2） A.空间复杂度和时间复杂度 B.正确性和简明性 C.可读性和文档性 D.数据复杂性和程序复杂性 6.计算机算法指的是（1），它具备输入，输出和（2）等五个特性。 （1） A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法 （2） A.可行性，可移植性和可扩充性 B.可行性，确定性和有穷性 C.确定性，有穷性和稳定性 D.易读性，稳定性和安全性 7.数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储比顺序存储要（）。 A.低 B.高 C.相同 D.不好说 8.数据结构作为一门独立的课程出现是在（）年。 A.1946 B.1953 C.1964 D.1968 9.数据结构只是研究数据的逻辑结构和物理结构，这种观点（）。 A.正确 B.错误 C.前半句对，后半句错 D.前半句错，后半句对 第1章 绪论 1.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={ 一、选择题。(每小题2分，共40分) (1) 计算机识别.存储和加工处理的对象被统称为____A____。 A.数据 B.数据元素 C.数据结构 D.数据类型 (2) 数据结构通常是研究数据的____ A _____及它们之间的联系。 A.存储和逻辑结构 B.存储和抽象 C.理想和抽象 D.理想与逻辑 (3) 不是数据的逻辑结构是____ A ______。 A.散列结构 B.线性结构 C.树结构 D.图结构 (4) 数据结构被形式地定义为 习题课 填空 1对于一棵二叉树，若一个结点的编号为i，则它的左孩子结点的编号为 ________________ , 双亲结点的编号为_____________ 。 2、向一个长度为n的向量中删除第i个元素（1 < i < n）时，需向前移动_________ 个元素。 3、在一棵二叉树中，若双分支结点数为5个，单分支结点数为6个，则叶子结点数 为__________ 个。 4、为了实现折半查找，线性表必须采用_____________ 方法存储。顺序 5、一种抽象数据类型包括数据对象________________ 和 ______________。 6、在以L为表头指针的带表头附加结点的单链表和循环单链表中，判断链表为空的条件分 别为___________ 和 _______ 。 7、数据结构被形式地定义为（D, R）,其中D是_________ 的有限集合，R是D上的_________ 有限集合。 8、队列的插入操作在_________ 进行，删除操作在___________ 进行。 9、二叉搜索树的中序遍历得到的结点序列为______ _____ _ 。 10、在顺序表中插入或删除一个元素，需要平均移动_________________元素，具体移动的元素个数与______________________ 关。 11、栈的特点是____________________ 。 12、在单链表中，除了首元结点外，任一结点的存储位置由__________ 。 13、在一个具有n个顶点的无向图中，要连通所有顶点则至少需要_________ 条边。 14、深度为k （设根的层数为1）的完全二叉树至少有个结点，至多 有个结点。 15、一棵深度为6的满二叉树有_______ 个分支结点和______ 个叶子结点。 16、一个算法的效率可分为____________ 效率和____________ 效率。 仃、队列的特点是______________________ 。 18、一棵深度为5的满二叉树中的结点数为__________ 个。 19、在一个具有n个顶点的无向完全图中，包含有__________ 条边，在一个具有n个顶点的有 向完全图中，包含有_________ 条边。 中华人民共和国城乡规划法试题和答案．中华人民共和国城乡规划法 一、填空题 1、城乡规划，包括、、、和村庄规划。 【答案】城镇体系规划、城市规划、镇规划、乡规划 2、城市规划、镇规划分为和。详细规划分为和。 【答案】总体规划，详细规划，控制性规划，修建性详细规划 3、规划区是指城市、镇和村庄的以及因和，必须实行的区域。 【答案】建成区，城乡建设，发展需要、规划控制 4、城市、镇规划区内的建设活动应当符合。 【答案】规划要求 5、根据本地农村经济社会发展水平，按 照、 的原则，确定应当制定、的区域。 【答案】县级以上地方人民政府，因地制宜、切实可行，乡规划、村庄规划 6、制定和实施城乡规划，应当遵循、、、 和的原则。改善，促进、节约和综合利用，保护等自然资源和，保 持、 和。 【答案】城乡统筹、合理布局、节约土地、集约发展，先规划后建设、生态环境，资源、能源，耕地，历史文化遗产，地方特色、民族特色，传统风貌。 7、在规划区内进行建设活动，应当遵守、 和 等法律、法规的规定。 【答案】土地管理，自然资源，环境保护 8、城市总体规划、镇总体规划以及乡规划和村庄规划的编制，应当依据 和，并与相衔接。 【答案】国民经济，社会发展规划，土地利用总体规划 9、经依法批准的城乡规划，是和的依据。 【答案】城乡建设，规划管理 10、城乡规划组织编制机关应当经依法批准的城乡规划。 【答案】及时公布 11、任何单位和个人都应当遵守经依法批准并公布的城乡规划，服从规划管理，并就涉及其的建设活动是否符合规划的要求向城乡规划主管部门查询。 【答案】有权，利害关系 12、任何单位和个人都有权向城乡规划主管部门或者其他有关部门举报或者控告的行为。城乡规划主管部门或者其他有关部门对举报或者控告，应当并组数据结构习题及答案——严蔚敏
数据结构习题和答案
党员干部十九党知识考试试题及答案
中华人民共和国城乡规划法试卷一含答案
数据结构习题集(答案)
数据结构练习题(含答案)
中华人民共和国城乡规划法试题及详细答案解析(供参考)
数据结构习题与答案
数据结构习题及答案——严蔚敏_课后习题答案 精品
2019年党建知识竞赛题库含答案
城乡规划法试题及答案
数据结构习题集包含全部答案
数据结构习题参考答案
数据结构习题及参考答案
最新数据结构习题集答案解析--清华大学版
数据结构复习题集与答案解析(12级)
数据结构习题和答案
中华人民共和国城乡规划法试题和答案
相关主题
文本预览