数据结构1-4章习题答案
第1章概论习题参考解答
一、填空题
1、数据的逻辑结构是数据元素之间的逻辑关系，通常有下列4类：（）、（）、（）、（）。
【答】集合、线性结构、树型结构和图状结构。
2、数据的存储结构是数据在计算机存储器里的表示，主要有4种基本存储方法：（）、（）、（）、（）。
【答】顺序存储方法、链接存储方法、索引存储方法和散列存储方法。
二、选择题
1、一个算法必须在执行有穷步之后结束，这是算法的（）。
（A）正确性（B）有穷性
（C）确定性（D）可行性
【答】B。
2、算法的每一步，必须有确切的定义。也就是说，对于每步需要执行的动作必须严格、清楚地给出规定。这是算法的（）。
（A）正确性（B）有穷性
（C）确定性（D）可行性
【答】C。
3、算法原则上都是能够由机器或人完成的。整个算法好像是一个解决问题的“工作序列”，其中的每一步都是我们力所能及的一个动作。这是算法的（）。
（A）正确性（B）有穷性
（C）确定性（D）可行性
【答】D。
三、简答题
1、算法与程序有何异同？
【答】尽管算法的含义与程序非常相似，但两者还是有区别的。首先，一个程序不一定满足有穷性，因此它不一定是算法。例如，系统程序中的操作系统，只要整个系统不遭受破坏，它就永远不会停止，即使没有作业要处理，它仍处于等待循环中，以待一个新作业的进入。因此操作系统就不是一个算法。其次，程序中的指令必须是计算机可以执行的，而算法中的指令却无此限止。如果一个算法采用机器可执行的语言来书写，那么它就是一个程序。
2、什么是数据结构？试举一个简单的例子说明。
【答】数据结构是指数据对象以及该数据对象集合中的数据元素之间的相互关系（即数据元素的组织形式）。例如，队列的逻辑结构是线性表（先进先出）；队列在计算机中既可以采用顺序存储也可以采用链式存储；对队列可进行删除、插入数据元素以及判断是否为空队列、将队列置空等操作。
3、什么是数据的逻辑结构？什么是数据的存储结构？
【答】数据元素之间的逻辑关系，也称为数据的逻辑结构。数据元素以及它们之间的相互关系在计算机存储器内的表示（又称映象），称为数据的存储结构，也称数据的物理结构。
4、什么是算法？算法有哪些特性？
【答】算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作；此外，一个算法还具有下列5个特性：
①有穷性：一个算法必须在执行有穷步之后结束，即算法必须在有限时间内完成。
②确定性：算法中每一步必须有确切的含义，不会产生二义性。并且，在任何条件下，算法只有唯一的一条执行路径，即对于相同的输入只能得出相同的输出。
③可行性：一个算法是能行的，即算法中的每一步都可以通过已经实现的基本运算执行有限次得以实现。
④输入：一个算法有零个或多个输入，它们是算法开始时对算法给出的初始量。
⑤输出：一个算法有一个或多个输出，它们是与输入有特定关系的量。
四、算法分析题
1、将下列复杂度由小到大重新排序：2n、n!、n
2、10000、log2n、n×log2n。
【答】10000< log2n< n×log2n < n2<2n < n!。
2、用大“O”表示法描述下列复杂度：
⑴5n5/2+n2/5
【答】O(n5/2)。
⑵6×log2n+9n
【答】O(n)。
⑶3n4+n×log2n
【答】O(n4)。
⑷n×log2n+n×log3n
【答】O(n×log2n)。
3、设n为正整数，请用大“O”表示法描述下列程序段的时间复杂度。
⑴i=1; k=0; ⑵i=0; k=0;
while(i {k=k+10*i; i++; i++; } }while(i 【答】O(n)。【答】O(n)。 ⑶i=1; j=0; ⑷x=n; /*n是常数且n>1*/ while(i+j<=n) while(x>=(y+1)*(y+1)) {if(i>j) j++; y++; else i++ } 【答】O(n)。【答】O(n)。 ⑸for((i=1; i<=n; i++) ⑹x=91; y=100; for(j=1; j<=i; j++) while(y>0) for(k=1; k<=j; k++) {if(x>100) {x-=10; y--;} x+=c; (c为常数) else x++; } 【答】O(n3)。【答】O(n)。 第2章线性表习题参考解答 一、简答题 1．试描述头指针、头结点、开始结点的区别、并说明头指针和头结点的作用。 【答】头指针：是指向链表中的第一个结点的指针。 头结点：在开始结点之前附加上的一个结点。 开始结点：链表的第一个结点。 头指针是一个指向地址的变量，用于表示一个链表的开始。引入头结点可以更加方便的进行链表是否为空的判断，同时方便了插入和删除结点。开始结点用于存储链表的第一个数据元素。 2．何时选用顺序表、何时选用链表作为线性表的存储结构为宜? 【答】顺序表中查找元素、获取表长非常容易，但是，要插入或者删除一个元素却需要移动大量的元素；相反，链表中却是方便插入或者删除元素，在查找元素的是，需要进行遍历。因此，当所涉及的问题常常进行查找等操作，而插入、删除相对较少的是，适合采用顺序表；当常常需要插入、删除的时候，适合采用链表。 3．为什么在单循环链表中设置尾指针比设置头指针更好? 【答】在单循环链表中，设置尾指针，可以更方便的判断链表是否为空。 4．在单链表、双链表和单循环链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点*p从相应的链表中删去? 【答】本题分三种情况讨论： 1、单链表：当知道指针p指向某结点时，能够根据该指针找到其直接后继，但是不知道头指针，因此不能找到该结点的直接前趋，因此，无法删除该结点。 2、双链表：根据指针p可以找到该结点的直接前趋和直接后继，因此，能够删除该结点。 3、单循环链表：和双链表类似，根据指针p也可以找到该结点的直接前趋和直接后继，因此，也可以删除该结点。 5．下述算法的功能是什么? LinkList Demo(LinkList *L) /* L是无头结点单链表*/ { LNode *Q,*P; if(L&&L->next) { Q=L;L=L->next;P=L; while (P->next) P=P->next; P->next=Q; Q->next=NULL; } return L; } /* Demo */ 【答】将原来的第一个结点变成末尾结点，原来的第二个结点变成链表的第一个结点。 二、算法设计题 1．试分别用顺序表和单链表作为存储结构，实现将线性表(a0,a1,...a n-1)就地逆置的操作，所谓"就地"指辅助空间应为O(1)。 【答】分两种情况讨论如下。 ①顺序表： 要将该表逆置，可以将表中的开始结点与终端结点互换，第二个结点与倒数第二个结点互换，如此反复，就可将整个表逆置了。算法如下： void reverlist(sequenlist *L) { datatype t; /* 设置临时空间用于存放data */ int i; for (i=0;i { t=L->data[i]; /* 交换数据 */ L->data[i]=L->data[L->length-1-i]; L->data[L->length-1-i]=t; } } ②链表： 可以利用指针的指向转换来达到表逆置的目的。算法是这样的： LinkList *reverselist(LinkList *head) /* 将head 所指的单链表逆置 */ { LNode *p,*q ; /* 设置两个临时指针变量 */ if((head->next!=NULL) && (head->next->next!=NULL)) /* 当链表不是空表或单结点时 */ { p=head->next; q=p->next; p->next=NULL; /*将开始结点变成终端结点 */ while (q) /* 每次循环将后一个结点变成开始结点 */ { p=q; q=q->next; p->next= head-> next; head->next=p; } return head; } return head; /* 如是空表或单结点表，直接返回head */ } 2．顺序表L是一个递增有序表，试写一算法，将x插入L中，并使L仍是一个有序表。 【答】因已知顺序表L是递增有序表，所以只要从头找起找到第一个比它大（或相等） 的结点数据，把x插入到这个数所在的位置就是了。算法如下： void InsertIncreaseList( Sequenlist *L , Datatype x ) { int i; for (i=0; i } 3．顺序表L是一个递减有序表，试写一算法，将x插入其后仍保持L的有序性。 【答】类似于第2题，读者可自行完成，这里不在赘述。 4．知L1和L2分别指向两个单链表的头结点，且已知其长度分别为m和n。试写一算法将这两个链表连接在一起，请分析你的算法的时间复杂度。 【答】算法如下： LinkList *Link( LinkList *L1 , LinkList *L2 ) {/* 将两个单链表连接在一起 */ LNode *p , *q ; p=L1; q=L2; while ( p->next ) p=p->next; /* 查找终端结点 */ p->next = q->next ; /* 将L2的开始结点链接在L1之后 */ return L1 ; } 本算法的主要操作时间花费在查找L1的终端结点上，与L2的长度无关，所以本算的法时间复杂度为：O(m) 5．A和B是两个单链表，其表中元素递增有序。试写一算法将A和B归并成一个按元素值递减有序的单链表C，并要求辅助空间为O(1)，请分析算法的时间复杂度。 【答】根据已知条件，A和B是两个递增有序表，所以我们可以以A表为基础，按照插入单个元素的办法把B表的元素插入A表中，完成后，将表逆置就得到了一个按元素值递减有序的单链表C了。算法如下： LinkList *MergeSort(LinkList *A , LinkList *B ) { /* 归并两个递增有序表为一个递减有序表 */ LNode *pa , *pb , *qa , *qb ; pa=A; pb=B; qa=A->next; qb=B->next; while (qa &&qb) { if(qb->data { /* 当B中的元素小于A中当前元素时，插入到它的前面 */ pb=qb; qb=qb->next ; /* 指向B中下一元素 */ pa->next=pb; pb->next=qa; pa=pb; } else if ( qb->data>=pa->data && qb->data<=qa->data) {/* 当B中元素大于等于A中当前元素，且小于等于A中后一元素时，将此元素插入到A的当前元素之后 */ pa=qa; qa=qa->next; /* 保存A的后一元素位置 */ pb=qb; qb=qb->next; /* 保存B的后一元素位置 */ a->next=pb; /* 插入元素 */ pb->next=qa; } else { /* 如果B中元素总是更大,指针移向下一个A元素 */ pa=qa; qa=qa->next; } } if (qb ) /* 如果A表已到终端而B表还有结点未插入 */ { /* 将B表接到A表后面 */ pa->next=qb; } C= reverselist(A); /*调用前面所设计的逆置函数 */ return C; /* 返回新的单链表C, 已是递减排列 */ } 该算法的时间复杂度分析如下： 算法中只有一个while循环，在这个循环中，按照最坏的情况是B元素既有插到A 的最前的，也有插到最后的，也就是说需要把A中元素和B中元素全部检查比较过，这时的所费时间就是m+n. 而新链表的长度也是m+n+1 (有头结点)，这样逆置函数的执行所费时间为m+n+1。所以可得整个算法的时间复杂度为： m+n+m+n+1=2(m+n)+1= O(m+n) 6．试编写一算法将单链表中值重复的结点删除，使所得的结果表中各结点值均不相同。 已知由单链表表示的线性表中，含有三类字符的数据元素(如：字母字符、数字字符和其它字符)，试编写算法构造三个以循环链表表示的线性表，使每个表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。 【答】本题分为两个部分，第一部分是删除重复结点，第二部分链表的分解。 首先看第一部分：要删除重复结点，有两种方式，第一种方式：先取开始结点中的值，将它与其后的所有结点值一一比较，发现相同的就删除掉，然后再取第二结点的值，重复上述过程直到最后一个结点。第二种方式：将单链表按值的大小排序，排好后的结点按相同的删除。我们这里给出第一种方式的算法，如下所示： void sc(LinkList *head) { LinkList *p,*q,*w; p=head->next; while(p!=NULL) { q=p->next; w=p; while(q!=NULL) {/*比较p所指节点的值与链表中后续节点的值，不相等q指针后移,相等则删除*/ if (p->data!=q->data) {w=q;q=q->next;} else {w->next=q->next;w=q;q=q->next;} } p=p->next; } } 第二部分：本部分的思路和第一部分类似，首先构造三个新的链表，然后遍历原链表，检测每一个元素，如果是第一类元素，则把该结点从原链表中删除，但是不释放空间，而是添加到第一个新链表中；同样的，如果是第二类元素，则添加到第二个新链表中；以此类推，直到所有的节点都检测完毕。具体算法如下： void split(LinkList *ha) { LinkList *hb,*hc,*ra,*rb,*rc,*p; char c; hb=(linklist*)malloc(sizeof(linklist)); hc=(linklist*)malloc(sizeof(linklist)); p=ha->next; ra=pa; ra->next=NULL; rb=hb; rb->next=NULL; rc=hc; rc->next=NULL; while(p!=ha) { c=p->data; if ((c>=‘a’&& c<=‘z’)||(c>=‘C’ && c<=‘Z’)) { ra->next=p;ra=p; } else if(c>=‘0’ && c<=‘9’ { rb->next=p; rb=p; } else { rc->next=p; rc=p; } p=p->next; } ra->next=ha;rb->next=hb;rc->=next=hc; } 7．设在长度大于1的单循环链表中，既无头结点也无头指针。s为指向链表中某个结点的指针，试编写算法删除结点*s的直接前趋结点。 【答】已知指向这个结点的指针是*s，那么要删除这个结点的直接前趋结点，就只要找到一个结点，它的指针域是指向*s的，把这个结点删除就可以了。算法如下：void DeleteNode(LinkList *s) { /* 删除单循环链表中指定结点的直接前趋结点 */ LinkList *p, *q; p=s; while( p->next->next!=s) { q=p; / p=p->next; } q->next=s; //删除结点 free(p); //释放空间 } 第3章栈和队列习题参考答案 一、填空题： 1．线性表、栈和队列都是结构，可以在线性表的位置插入和删除元素；对于栈只能在插入和删除元素；对于队列只能在插入和删除元素。 【答】线性、任何、栈顶、队尾、队头 2．栈是一种特殊的线性表，允许插入和删除运算的一端称为。不允许插入和删除运算的一端称为。 【答】栈顶、栈底 3．是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。 【答】队列 4．在一个循环队列中，队首指针指向队首元素的位置。 【答】当前 5．在具有n个单元的循环队列中，队满时共有个元素。 【答】n-1 6．向栈中压入元素的操作是先，后。 【答】存入元素、修改栈顶指针 7．从循环队列中删除一个元素时，其操作是先，后。 【答】取出元素、移动队头指针 8．在操作序列push(1)，push(2)，pop()，push(5)，push(7)，pop()，push(6)之后，栈顶元素是，栈底元素是。 【答】6、1 9．在操作序列enqueue(1)，enqueue(2)，dequeue()，enqueue(5)，enqueue(7)，dequeue()，enqueue(9)之后，队头元素是，队尾元素是。 【答】5、9 10．用单链表表示的链式队列的队头是在链表的位置。 【答】表头 二、单项选择题 1．栈中元素的进出原则是（）。 Ａ．先进先出Ｂ．后进先出Ｃ．栈空则进Ｄ．栈满则出【答】B 2．若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为（） Ａ．i Ｂ．n=i Ｃ．n-i+1 Ｄ．不确定 【答】C 3．判定一个栈ST（最多元素为m0）为空的条件是（） Ａ．ST->top<>0 Ｂ．ST->top=0 Ｃ．ST->top<>m0 Ｄ．ST->top=m0 【答】B 4．当利用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则向这个栈插入一个元素时，首先应执行（）语句修改top指针。 Ａ．top++ Ｂ．top-- Ｃ．top Ｄ．top=0 【答】B 5、假定一个链栈的栈顶指针用其所长top表示，当p所指向的结点进栈时，执行的操作是（）。 Ａ．p->next=top;top=top->next; Ｂ．top=p->p;p->next=top; Ｃ．p->next=top->next;top->next=p; Ｄ．p->next=top;top=p; 【答】D 6．判定一个队列QU（最多元素为m0）为满队列的条件是（） Ａ．QU->rear － QU->front = = m0 Ｂ．QU->rear － QU->front －1= = m0 Ｃ．QU->front = = QU->rear Ｄ．QU->front = = QU->rear+1 【答】B 7．数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素的公式为（）Ａ．r－f Ｂ．（n＋f－r）% n Ｃ．n＋r－f Ｄ．（n＋r－f）% n 【答】D 8．假定一个链队的队首和队尾指针分别为front和rear，则判断队空的条件为（）。 Ａ．Front==rear Ｂ．Front!=NULL Ｃ．Rear!=NULL Ｄ．Front==NULL 【答】A 9．假定利用数组a[N]循环顺序存储一个队列，用f和r分别表示队首和队尾指针，并已知队未空，当进行出队并返回队首元素时所执行的操作为（）。 Ａ．return(a[++r%N]) Ｂ．return(a[--r%N]) Ｃ．return(a[++f%N]) Ｄ．return(a[f++%N]) 【答】D 10．从供选择的答案中，选出应填入下面叙述 ？ 内的最确切的解答，把相应编号写在答卷的对应栏内。 设有4个数据元素a1、a2、a3和a4，对他们分别进行栈操作或队操作。在进栈或进队操作时，按a1、a2、a3、a4次序每次进入一个元素。假设栈或队的初始状态都是空。 现要进行的栈操作是进栈两次，出栈一次，再进栈两次，出栈一次；这时，第一次出栈得到的元素是 ，第二次出栈得到的元素是 是；类似地，考虑对这四个数据元素进行的队操作是进队两次，出队一次，再进队两次，出队一次；这时，第一次出队得到的元素 是 ，第二次出队得到的元素是 。经操作后，最后在栈中或队中的元素还有 个。 A ．a1 B ．a2 C ．a3 D ．a4 E ．1 F ．2 G ．3 H ．0 【答】B D A B F 三．算法分析题（请写出下列各算法的功能）： 1．int M(int x) (int y; if(x>100) return(x-10); else {y=M(x+11); return(M(y)); } } 【答】求解分段函数M(x)=?????≤+>-100 ),11((100 ,10 x x M M x x 2．void a1(Seqstack S) {int I, n, a[100]; n=0; while(!SeqstackEmpty(S)) {n++; Pop(S,a[n]);} for(I=1; I<=n; I++) Push(S,a[I]); } 【答】将栈S 中的数据元素次序颠倒。 3．void a2() {Queue Q; InitQueue(Q); Char x=’e’, y=’c’; EnQueue(Q,‘h’); EnQueue(Q,‘r’); EnQueue(Q,y); x=DeQueue(Q); EnQueue(Q,x); x=DeQueue(Q); EnQueue(Q,‘a’); While(!QueueEmpty(Q)) { y=DeQueue(Q); printf(“%c”,y) } printf(“%c”,x); } 【答】输出字符序列：char 四、算法设计题： 1．设单链表中存放着n个字符，试设计算法判断字符串是否与中心对称。如：“abcdedcba”就是中心对称的字符串。 【答】 int judge(LinkList *head) { seqstack s; int i=1; LinkList *p; s->top=0; p=head; while(p!=null) { s->data[s->top++]=p->data; p=p->next; } p=head; while(p!=null) if(p->data==s->data[s->(--top)]) p=p->next; else { i=0; p=null; } return i; } 2．写一个表达式中开、闭括号是否合法配对的算法。 【答】 int match_test(char *str) { char *p; int n=0; for(p=str, *p; p++) if(*p== ‘( ’) n++; else if(*p== ‘) ’) n--; return (!n?1:0); } 3．编号为1,2,3,4的四列火车通过一个如图3.1(b)所示的栈式的列车调度站，可能得到的调度结果有哪些？如果有n列火车通过调度站，请设计一个算法，输出所有可能的调度结果。 【答】 ①全进之后再出情况，只有1种：4，3，2，1 ②进3个之后再出的情况，有3种，3,4,2,1 3,2,4,1 3,2,1,4 ③进2个之后再出的情况，有5种，2,4,3,1 2,3,4,1 2,1, 3,4 2,1,4,3 2,1,3,4 ④进1个之后再出的情况，有5种，1,4,3,2 1,3,2,4 1,3,4,2 1, 2,3,4 1,2,4,3 int cont=1; void print(int str[],int n) {int i,j,k,l,m,a=0,b[100]; for(i=0;i { m=0; for(j=i;j if (str[i]>str[j]) b[m++]=str[j]; if(m>=2) { for(k=0;k for(l=k;l if(b[k] } } if(a==0) { printf(" %2d:",cont++); for(i=0;i printf("%d",str[i]); printf("\n"); } } void perm(int str[],int k,int n) {int i,temp; if (k==n-1) print(str,n); else { for (i=k;i {temp=str[k]; str[k]=str[i]; str[i]=temp; perm(str,k+1,n); temp=str[i]; str[i]=str[k]; str[k]=temp; } } } 4．设有两个栈S1，S2都采用顺序栈方式，并且共享一个存储区[0…maxsize-1]，为了尽量利用空间，减少溢出的可能，可采用栈顶相向、迎面增长的存储方式，试设计入栈、出栈的算法。 【答】 (1)入栈算法: int *push(seqstack *s, datatype x) {int flag; scanf(“%d”,&flag); if((s->top1+1)==(s->top2)) printf)(“stack is full\n”) else {if((flag!=1)&&(flag!=2)) printf(“input error\n”); if((s->top1+1)!=(s->top2)) switch(flag) {case 1: s->data[s->top1]=x; s->top1++; break; case 2: s->data[s->top2]=x; s->top2--; break; } } return s; } (2)出栈算法: datatype pop(seqstack *s) {datatype t; int flag; scanf(“%d”,&flag); if((flag!=1)&&(flag!=2)) printf(“input error\n”); switch(flag) {case 1: if(s->top1!=0) {s->top1--; t=s->data[s->top1];} else printf(“stack1 is empty\n”); break; case 2: if(s->top2!=maxsize-1) {s->top2++; t=s->data[s->top2];} else printf(“stack2 is empty\n”); break; } return t; } 5．假设用一个单循环链表来表示队列（也称为循环队列），该队列只设一个队尾指针，不设队头指针，试编写相应的入队和出队的算法。 【答】 (1)入队算法: insert(LinkList *rear, datatype x) {LinkList *p; p=(LinkList*)malloc(sizeof(LinkList)); if(rear==Null) {rear=p; rear->next=p;} else { p->next=rear->next; rear->next=p rear=p;} } (2)出队算法: delete(LinkList *rear) {if(rear==Null) printf(“underflow\n”); if(rear->next==rear) rear=Null; else rear->next=rear->next->next; } 6．假设将循环队列定义为：以域变量rear和len分别指示循环队列中队尾元素的位置和内含元素的个数。试给出循环队列的队满条件，并写出相应的入队和出队的算法。 【答】 假设队尾指针rear批示队尾元素实际存放的存储单元的位置,且设sq为指向seqqueue 类型的队列指针,该类型含域rear和data数组以及len域： (1)入队算法: int enqueue(seqqueue *sq,datatype x) {if(sq->len==maxsize) {printf(“overflow\n”); return 0;} else { sq->rear=(sq->rear+1)%maxsize; sq->data[sq->rear]=x; sq->len++; return 1; } } (2)出队算法: datatype delqueue(seqqueue *sq) {int front; if(sq->len==0) {printf(“underfolw\n”);return FALSE;} else {front=sq->rear+1-sq->len; if(front<0) front=front+maxsize; sq->len--; retrun sq->data[front]; } } 第4章串习题参考解答 一、填空题 1．空串与空格串的区别在于_____________________。 【答】空串是长度为零（n＝0）的串，它不包含任何字符；空格串是由空格字符组成的串，它的长度为串中空格字符的个数。 2．两个字符串相等的充分必要条件是_______________________。 【答】两个串的长度相等，并且各个对应位置的字符也都相同。 3．按存储结构不同，串可分为_____________________________。 【答】顺序串和链串 4．写出模式串〝abaabcac〞的next函数值序列为____________________。 【答】01122312 二、选择题 1．设有两个串p和q，求q在p中首次出现的位置的运算称作（）。 A．连接B．模式匹配 C．求子串D．求串长 【答】 B 2．串是一种特殊的线性表，其特殊性体现在（）。 A．可以顺序存储 B．数据元素是一个字符 C．可以链接存储 D．数据元素可以是多个字符 【答】 B。 3．若串S=〝software〞，其子串数目是（）。 A． 8 B．37 C．36 D．9 【答】 C。 4．在顺序串中，根据空间分配方式的不同，可分为( )。 A．直接分配和间接分配 B．静态分配和动态分配 C．顺序分配和链式分配 D．随机分配和固定分配 【答】 B 5．设串s1=〝ABCDEFG〞，s2=〝PQRST〞，函数con(x,y)返回x和y串的连接串，subs(s,i,j)返回串s的从序号i的字符开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(s1,2,len(s2)),subs(s1,len(s2),2)))的结果串是( )。 A．BCDEF B．BCDEFG C．BCPQRST D．BCDEFEF 【答】 D 三、简述下列每对术语的区别 1、串变量和串常量 【答】串变量和其它类型的变量一样，其取值是可以改变的，它必须用名字来识别；而串常量和整常数、实常数一样，具有固定的值，在程序中只能被引用但不能改变其值，即只能读不能写。 2、主串和子串 【答】主串和子串是相对的，子串指串中任意个连续字符组成的子序列；包含子串的串称为该子串的主串。 3、串名和串值 【答】串名指串的名称；串值指用双引号（""）括起的字符序列。 如：x=〝456〞; 其中x是串变量名，串值为字符序列123。 四、算法设计题 1．利用下面的串的基本操作，构造子串定位运算INDEX(S,T)。其中S是目标串，T是模式串。 (1) strlen(char *s); (2) strcmp(char *s1,char *s2); (3)substr(char *s,int pos,int len); 【答】 int INDEX(SeqString *S; SeqString *T) /*若串S中存在与串T相等的子串，则返回第一个这样的子串在S中的位置，否则返回0*/ {int m,n.i; m=strlen(S); n=strlen(T); i=0; while(i<=m-n+1) { if(strcmp(substr(S,i,n),T)!=0) ++i; else return i; /*返回子串在主串中的位置*/ } return 0; /*S中不存在与S中相等的子串*/ } 2．编写算法，从串s中删除所有和串t相同的子串，说明算法所用的存储结构，并分析算法的执行时间。 【答】SeqString *Delete_SubString(SeqString *s, SeqString *t) /*从串s中删除所有与t相同的子串,串采用顺序串存储结构*/ { for(i=1;i<=Strlen(s)-Strlen(t)+1;i++) if(!Strcmp(Substr(s,i,Strlen(t)),t)) /*找到与t匹配的子串*/ { /*分别把t的前面和后面部分保存为head和tail*/ StrAssign(head,Substr(s,1,i-1)); StrAssign(tail,Substr(s,i+Strlen(t),Strlen(s)-i-Strlen(t)+1)) ; StrAssign(s,Strcat(head,tail)); /*把head,tail连接为新串，再赋给串s*/ } return s; } 其中 #define MaxStrSize 256 /*定义串可能的最大长度*/ typedef char SeqString[MaxStrSize]; /*定义串的顺序存储结构*/ 3．编写算法，将串中所有字符倒过来重新排列。 【答】void String_Reverse(Stringtype s,Stringtype &r) /*求s的逆串r*/ { StrAssign(r,''); /*初始化r为空串*/ for(i=Strlen(s);i;i--) { StrAssign(c,SubStr(s,i,1)); StrAssign(r,Strcat(r,c)); /*把s的字符从后往前添加到r中*/ } } 4．采用串的链式存储表示的方法，改写KMP匹配算法和求next数组的算法。并估计算法的执行时间。 【答】typedef struct{ char ch; LStrNode *next; LStrNode *; } LStrNode,*LString; /*串的链式存储结构,其中ch域存放一个字符；succ域存放指向同一链表中后继结点的指针；next域在主串中存放指向同一链表中前驱结点的指针，在模式串中存放指向当该结点的字符与主串中字符不等时，模式串中下一个应进行比较的字符结点的指针，若该结点字符的next函数值为零，其next域的值为NULL。*/ void LGet_next(LString &T) /*链串上的get_next算法 { p=T->succ; p->next=T; q=T; while(p->succ) { if(q==T||p->ch==q->ch) { p=p->succ; q=q->succ; p->next=q; } else q=q->next; } } LStrNode *LIndex_KMP(LString S,LString T,LStrNode *pos) /*链串上的KMP匹配算法,返回值为匹配的子串首指针,pos指向链串S的第一个结点*/ { p=pos; q=T->succ; while(p&&q) { if(q==T||p->ch==q->ch) { p=p->succ; q=q->succ; } else q=q->next; } if(!q) { for(i=1;i<=Strlen(T);i++) p=p->next; return p; /*发现匹配成功,往回找子串的头*/ } return NULL; } Chap1 一、选择题 1.算法的计算量的大小称为计算的（）。 A．效率 B.复杂性 C.现实性 D.难度 2.计算机算法指的是（1），它必须具备（2）这三个特性。 (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．在下面的程序段中，对x的赋值语句的频度为（） FOR i:=1TO n DO FOR j:=1TO n DO x:=x+1; n) A．O(2n)B．O(n)C．O(n2)D．O(log 2 7．程序段FOR i:=n-1DOWNTO1DO FOR j:=1TO i DO IF A[j]>A[j+1] THEN A[j]与A[j+1]对换； 其中n为正整数，则最后一行的语句频度在最坏情况下是（）。 A.O（n） B.O(nlogn) C.O(n3) D.O(n2) 8．以下哪个数据结构不是多型数据类型（） A．栈B．广义表C．有向图D．字符串 9．以下数据结构中，（）是非线性数据结构 A．树B．字符串C．队D．栈 二、判断题 1．健壮的算法不会因非法的输入数据而出现莫名其妙的状态。() 2．算法可以用不同的语言描述，如果用C语言或PASCAL语言等高级语言来描述，则算法实际上就是程序了。() 3．程序一定是算法。() 4．数据的物理结构是指数据在计算机内的实际存储形式。() 5.数据结构的抽象操作的定义与具体实现有关。() 6.顺序存储方式的优点是存储密度大，且插入、删除运算效率高。() 党员干部十九党知识考试试题及答案 一、单选题 中国共产党第十九次全国代表大会召开时间（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、城市人民政府城乡规划主管部门根据，组织编制城市的，经本级人民政府批准后，报本级人民代表大会常务委员会和上一级人民政府备案。 栈和队列的共同特点是__________________________ .栈通常采用的两种存储结构是______________________ .用链表表示线性表的优点是_______________________ 8.在单链表中，增加头结点的目的是___________________ 9.循环链表的主要优点是________________________- 12.线性表的顺序存储结构和线性表的链式存储结构分别是 __________________________ 13.树是结点的集合，它的根结点数目是_____________________ 14.在深度为5的满二叉树中，叶子结点的个数为_______________ 15.具有3个结点的二叉树有（_____________________ 16.设一棵二叉树中有3个叶子结点，有8个度为1的结点，则该二叉树中总的结点数为____________________ 17.已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是 ____________________________ 18.已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则该二叉树的后序遍历为______________________ 19.若某二叉树的前序遍历访问顺序是abdgcefh，中序遍历访问顺序是dgbaechf，则其后序遍历的结点访问顺序是_______________________ 20.数据库保护分为：安全性控制、完整性控制、并发性控制和数据的恢复。 在计算机中，算法是指_______________________ 算法一般都可以用哪几种控制结构组合而成_____________________ .算法的时间复杂度是指______________________ 5. 算法的空间复杂度是指__________________________ 6. 算法分析的目的是__________________________ 第一章习题 一、问答题 1.什么是数据结构？ 2.叙述四类基本数据结构的名称与含义。 3.叙述算法的定义与特性。 4.叙述算法的时间复杂度。 5.叙述数据类型的概念。 6.叙述线性结构与非线性结构的差别。 7.叙述面向对象程序设计语言的特点。 8.在面向对象程序设计中，类的作用是什么？ 9.叙述参数传递的主要方式及特点。 10.叙述抽象数据类型的概念。 二、判断题（在各题后填写“√”或“×”） 1.线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。（） 2.算法就是程序。（） 3.在高级语言（如C或 PASCAL）中，指针类型是原子类型。（） 三、计算下列程序段中X=X+1的语句频度 for(i=1;i<=n;i++) for(j=1;j<=i;j++) for(k=1;k<=j;k++) x=x+1; 四、试编写算法，求一元多项式P n (x)=a +a 1 x+a 2 x2+a 3 x3+…a n x n的值P n (x )，并确定算法中的每 一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用 求幂函数。注意：本题中的输入a i (i=0,1,…,n),x和n，输出为P n (x )。通常算法的输入和输 出可采用下列两种方式之一： （1）通过参数表中的参数显式传递。 （2）通过全局变量隐式传递。 试讨论这两种方法的优缺点，并在本题算法中以你认为较好的一种方式实现输入和输出。 实习题 设计实现抽象数据类型“有理数”。基本操作包括有理数的加法、减法、乘法、除法，以及求有理数的分子、分母。 第一章答案 1.3计算下列程序中x=x+1的语句频度 for(i=1;i<=n;i++) for(j=1;j<=i;j++) for(k=1;k<=j;k++) x=x+1; 【解答】x=x+1的语句频度为： T(n)=1+(1+2)+（1+2+3）+……+（1+2+……+n）=n(n+1)(n+2)/6 1.4试编写算法，求p n(x)=a0+a1x+a2x2+…….+a n x n的值p n(x0),并确定算法中每一语句的执 行次数和整个算法的时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用求幂函数。注意：本题中的输入为a i(i=0,1,…n)、x和n,输出为P n(x0)。算法的输入和输出采用下列方法（1）通过参数表中的参数显式传递（2）通过全局变量隐式传递。讨论两种方法的优缺点，并在算法中以你认为较好的一种实现输入输出。 【解答】 （1）通过参数表中的参数显式传递 优点：当没有调用函数时，不占用内存，调用结束后形参被释放，实参维持，函数通用性强，移置性强。 缺点：形参须与实参对应，且返回值数量有限。 （2）通过全局变量隐式传递 优点：减少实参与形参的个数，从而减少内存空间以及传递数据时的时间消耗 文档来源为:从网络收集整理.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. 若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上( ) A. 操作的有限集合 B. 映象的有限集合 C. 类型的有限集合 D. 关系的有限集合 2. 在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为( ) A. n-i+1 B. i C. i+1 D. n-i 3. 若不带头结点的单链表的指针为head，则该链表为空的判定条件是( ) A. head==NULL B. head->next==NULL C. head!=NULL D. head->next==head 4. 引起循环队列队头位置发生变化的操作是( ) A. 出队 B. 入队 C. 取队头元素 D. 取队尾元素 5. 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不．可能出现的出栈序列是( ) A. 2，4，3，1，5，6 B. 3，2，4，1，6，5 C. 4，3，2，1，5，6 D. 2，3，5，1，6，4 6. 字符串通常采用的两种存储方式是( ) A. 散列存储和索引存储 B. 索引存储和链式存储 C. 顺序存储和链式存储 D. 散列存储和顺序存储 7. 数据结构是（） A．一种数据类型 B．数据的存储结构 C．一组性质相同的数据元素的集合 D．相互之间存在一种或多种特定关系的数据元素的集合 8. 算法分析的目的是（） A．辨别数据结构的合理性 B．评价算法的效率 C．研究算法中输入与输出的关系 D．鉴别算法的可读性 9. 在线性表的下列运算中，不．改变数据元素之间结构关系的运算是 （） A．插入B．删除 C．排序D．定位10. 下列图示的顺序存储结构表示的二叉树是( ) 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. 若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上( ) A. 操作的有限集合 B. 映象的有限集合 C. 类型的有限集合 D. 关系的有限集合 2. 在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为( ) A. n-i+1 B. i C. i+1 D. n-i 3. 若不带头结点的单链表的指针为head，则该链表为空的判定条件是( ) A. head==NULL B. head->next==NULL C. head!=NULL D. head->next==head 4. 引起循环队列队头位置发生变化的操作是( ) A. 出队 B. 入队 C. 取队头元素 D. 取队尾元素 5. 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不．可能出现的出栈序列是( ) A. 2，4，3，1，5，6 B. 3，2，4，1，6，5 C. 4，3，2，1，5，6 D. 2，3，5，1，6，4 1 6. 字符串通常采用的两种存储方式是( ) A. 散列存储和索引存储 B. 索引存储和链式存储 C. 顺序存储和链式存储 D. 散列存储和顺序存储 7. 数据结构是（） A．一种数据类型 B．数据的存储结构 C．一组性质相同的数据元素的集合 D．相互之间存在一种或多种特定关系的数据元素的集合 8. 算法分析的目的是（） A．辨别数据结构的合理性 B．评价算法的效率 C．研究算法中输入与输出的关系 D．鉴别算法的可读性 9. 在线性表的下列运算中，不．改变数据元素之间结构关系的运算是 （） A．插入B．删除 C．排序D．定位 10. 下列图示的顺序存储结构表示的二叉树是( ) 2 《数据结构》第一章练习题 1、单项选择题 1.1数据结构是一门非数值计算的程序设计问题中计算机的（ ）以及它们之间的（ ）和运算等的学科。 ①A 数据元素 B 计算方法 C 逻辑存储 D 数据映像 ②A 结构 B 关系 C 运算 D 算法 1.2数据结构被形式的定义为（K,R ），其中K 是（ ）的有限集，R 是K 上的（ ）有限集。 ①A 算法B 数据元素C 数据操作D 逻辑结构 ②A 操作B 映像C 存储D 关系 1.3在数据结构中，从逻辑上可以把数据结构分为（ ）。 A 动态结构和静态结构 B 紧凑结构和非紧凑结构 C 线性结构和非线性结构 D 内部结构和外部结构 1.4数据结构在计算机内存中的表示是指（ ）。 A 数据的存储结构 B 数据结构 C 数据的逻辑结构 D 数据元素之间的关系 1.5在数据结构中，与所使用的计算机无关的是数据的（ ）结构。 A 逻辑 B 存储 C 逻辑和存储 D 物理 1.6算法分析的目的是（)，算法分析的两个主要方面是（ ）。①A 找出数据结构的合理性 B 研究算法中输入与输出的关系 C 分析算法效率以求改进 D 分析算法的易懂性和文档性 ②A 空间复杂度和时间复杂度 B 正确性和简明性 C 可读性和文档性 D 数据复杂性和程序复杂性 1.7计算机算法是指（ ），它必须具备输入、输出和（ ）等5个特性。 ①A 计算方法 B 排序方法 C 解决问题的有限运算序列 D 调度方法 ②A 可行性、可移植性和可扩充性 B 可行性、确定性和有穷性 C 确定性、有穷性和稳定性 D 易读性、稳定性和安全性 1.8在以下的叙述中，正确的是（ ）。 A 线性表和线性存储结构优于链表存储结构 B 二维数组是其数据元素为线性表的线性表 C 栈的操作方式是先进先出 D 队列的操作方式是先进后出 1.9在决定选择何种存储结构时，一般不考虑（ ）。 、管路敷设技术通过管线不仅可以解决吊顶层配置不规范高中资料试卷问题，而且可保障各类管路习题到位。在管路敷设过程中，要加强看护关于管路高中资料试卷连接管口处理高中资料试卷弯扁度固定盒位置保护层防腐跨接地线弯曲半径标等，要求技术交底。管线敷设技术中包含线槽、管架等多项方式，为解决高中语文电气课件中管壁薄、接口不严等问题，合理利用管线敷设技术。线缆敷设原则：在分线盒处，当不同电压回路交叉时，应采用金属隔板进行隔开处理；同一线槽内强电回路须同时切断习题电源，线缆敷设完毕，要进行检查和检测处理。、电气课件中调试对全部高中资料试卷电气设备，在安装过程中以及安装结束后进行 高中资料试卷调整试验；通电检查所有设备高中资料试卷相互作用与相互关系，根据生产工艺高中资料试卷要求，对电气设备进行空载与带负荷下高中资料试卷调控试验；对设备进行调整使其在正常工况下与过度工作下都可以正常工作；对于继电保护进行整核对定值，审核与校对图纸，编写复杂设备与装置高中资料试卷调试方案，编写重要设备高中资料试卷试验方案以及系统启动方案；对整套启动过程中高中资料试卷电气设备进行调试工作并且进行过关运行高中资料试卷技术指导。对于调试过程中高中资料试卷技术问题，作为调试人员，需要在事前掌握图纸资料、设备制造厂家出具高中资料试卷试验报告与相关技术资料，并且了解现场设备高中资料试卷布置情况与有关高中资料试卷电气系统接线等情况 ，然后根据规范与规程规定，制定设备调试高中资料试卷方案。 、电气设备调试高中资料试卷技术电力保护装置调试技术，电力保护高中资料试卷配置技术是指机组在进行继电保护高中资料试卷总体配置时，需要在最大限度内来确保机组高中资料试卷安全，并且尽可能地缩小故障高中资料试卷破坏范围，或者对某些异常高中资料试卷工况进行自动处理，尤其要避免错误高中资料试卷保护装置动作，并且拒绝动作，来避免不必要高中资料试卷突然停机。因此，电力高中资料试卷保护装置调试技术，要求电力保护装置做到准确灵活。对于差动保护装置高中资料试卷调试技术是指发电机一变压器组在发生内部故障时，需要进行外部电源高中资料试卷切除从而采用高中资料试卷主要保护装置。 数据结构上机实验题目 实验一线性表的顺序存储结构 实验学时 2学时 背景知识:顺序表的插入、删除及应用。 目的要求： 1．掌握顺序存储结构的特点。 2．掌握顺序存储结构的常见算法。 实验容 1．输入一组整型元素序列，建立顺序表。 2．实现该顺序表的遍历。 3．在该顺序表中进行顺序查找某一元素,查找成功返回1,否则返回0。4．判断该顺序表中元素是否对称,对称返回1,否则返回0。 5．实现把该表中所有奇数排在偶数之前,即表的前面为奇数,后面为偶数。 6．输入整型元素序列利用有序表插入算法建立一个有序表。 7．利用算法6建立两个非递减有序表并把它们合并成一个非递减有序表。 8. 利用该顺序结构实现循环队列的入队、出队操作。 8．编写一个主函数,调试上述算法。 #include #define OVERFLOW 0 #define MAXSIZE 100 typedef int ElemType; typedef struct list {ElemType elem[MAXSIZE]; int length; }Sqlist; void Creatlist(Sqlist &L) {int i; printf("请输入顺序表的长度："); //输入一组整型元素序列，建立一个顺序表。 scanf("%d",&L.length); for(i=0;i .栈通常采用的两种存储结构是______________________ .用链表表示线性表的优点是_______________________ 8.在单链表中，增加头结点的目的是___________________ 9.循环链表的主要优点是________________________- 12.线性表的顺序存储结构和线性表的链式存储结构分别是__________________________ 13.树是结点的集合，它的根结点数目是_____________________ 14.在深度为5的满二叉树中，叶子结点的个数为_______________ 15.具有3个结点的二叉树有（_____________________ 16.设一棵二叉树中有3个叶子结点，有8个度为1的结点，则该二叉树中总的结点数为____________________ 17.已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是____________________________ 18.已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则该二叉树的后序遍历为______________________ 19.若某二叉树的前序遍历访问顺序是abdgcefh，中序遍历访问顺序是dgbaechf，则其后序遍历的结点访问顺序是_______________________ 20.数据库保护分为：安全性控制、完整性控制、并发性控制和数据的恢复。 在计算机中，算法是指_______________________ 算法一般都可以用哪几种控制结构组合而成_____________________ .算法的时间复杂度是指______________________ 5. 算法的空间复杂度是指__________________________ 6. 算法分析的目的是__________________________ 《数据结构与算法设计》习题册 第一章绪论 一、单项选择题 1.数据结构是一门研究非数值计算的程序设计问题中计算机的①以及它们之间的②和运 算等的学科。 ①A. 数据元素 B. 计算方法 C. 逻辑存储 D. 数据映象 ②A. 结构 B. 关系 C. 运算 D. 算法 2.数据结构被形式地定义为（K，R），其中K是①的有限集，R是K上的②有限集。 ①A. 算法 B. 数据元素 C. 逻辑结构 D. 数据操作 ②A. 操作 B. 存储 C. 映象 D. 关系 3.在数据结构中，从逻辑上可以把数据结构分成。 A. 动态结构和静态结构 B. 紧凑结构和非紧凑结构 C. 线性结构和非线性结构 D. 内部结构和外部结构 4.数据结构在计算机内存中的表示是指。 A. 数据的存储结构 B. 数据结构 C. 数据的逻辑结构 D. 数据元素之间的关系 5.在数据结构中，与所使用的计算机无关的是数据的结构。 A. 逻辑 B. 存储 C. 逻辑和存储 D. 物理 6.算法分析的目的是①，算法分析的两个主要方面是②。 ①A. 找出数据结构的合理性 B. 研究算法中的输入和输出的关系 C. 分析算法的效率以求改进 D. 分析算法的易懂性和文档性 ②A. 空间复杂度和时间复杂度 B. 正确性和简明性 C. 可读性和文档性 D. 数据复杂性和程序复杂性 7.计算机算法指的是①，它必须具备输入、输出和②等5个特性。 ①A. 计算方法 B. 排序方法 C. 解决问题的有限运算序列 D. 调度方法 ②A. 可行性、可移植性和可扩充性 B. 可行性、确定性和有穷性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和安全性 8.在以下叙述中，正确的是。 A. 线性表的线性存储结构优于链表存储结构 B. 二维数组是其数据元素为线性表的线性表 C. 栈的操作方式是先进先出 D. 队列的操作方式是先进后出 9.在决定选取何种存储结构时，一般不考虑。 A. 各结点的值如何 B. 结点个数的多少 C. 对数据有哪些运算 D. 所用编程语言实现这种结构是否方便 10.在存储数据时，通常不仅要存储各数据元素的值，而且还要存储。 中华人民共和国城乡规划法试题和答案．中华人民共和国城乡规划法 一、填空题 1、城乡规划，包括、、、和村庄规划。 【答案】城镇体系规划、城市规划、镇规划、乡规划 2、城市规划、镇规划分为和。详细规划分为和。 【答案】总体规划，详细规划，控制性规划，修建性详细规划 3、规划区是指城市、镇和村庄的以及因和，必须实行的区域。 【答案】建成区，城乡建设，发展需要、规划控制 4、城市、镇规划区内的建设活动应当符合。 【答案】规划要求 5、根据本地农村经济社会发展水平，按 照、 的原则，确定应当制定、的区域。 【答案】县级以上地方人民政府，因地制宜、切实可行，乡规划、村庄规划 6、制定和实施城乡规划，应当遵循、、、 和的原则。改善，促进、节约和综合利用，保护等自然资源和，保 持、 和。 【答案】城乡统筹、合理布局、节约土地、集约发展，先规划后建设、生态环境，资源、能源，耕地，历史文化遗产，地方特色、民族特色，传统风貌。 7、在规划区内进行建设活动，应当遵守、 和 等法律、法规的规定。 【答案】土地管理，自然资源，环境保护 8、城市总体规划、镇总体规划以及乡规划和村庄规划的编制，应当依据 和，并与相衔接。 【答案】国民经济，社会发展规划，土地利用总体规划 9、经依法批准的城乡规划，是和的依据。 【答案】城乡建设，规划管理 10、城乡规划组织编制机关应当经依法批准的城乡规划。 【答案】及时公布 11、任何单位和个人都应当遵守经依法批准并公布的城乡规划，服从规划管理，并就涉及其的建设活动是否符合规划的要求向城乡规划主管部门查询。 【答案】有权，利害关系 12、任何单位和个人都有权向城乡规划主管部门或者其他有关部门举报或者控告的行为。城乡规划主管部门或者其他有关部门对举报或者控告，应当并组 《数据结构》课程设计题目 (程序实现采用C语言) 题目1：猴子选王（学时：3） 一堆猴子都有编号，编号是1，2，3 ...m，这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第n个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。 要求：m及n要求从键盘输入，存储方式采用向量及链表两种方式实现该问题求解。 //链表 #include { pCurr = (RingNodePtr)malloc(sizeof(RingNode)); i++; pCurr->pos = i; pPrev->next = pCurr; pPrev = pCurr; } pCurr->next = pHead; // 构成环状链表 } void KickFromRing(RingNodePtr pHead, int n) { RingNodePtr pCurr, pPrev; int i = 1; // 计数 pCurr = pPrev = pHead; while(pCurr != NULL) { if (i == n) { // 踢出环 printf("\n%d", pCurr->pos); // 显示出圈循序 pPrev->next = pCurr->next; free(pCurr); pCurr = pPrev->next; i = 1; } pPrev = pCurr; 第1章习题解答 1.1什么是数据结构？一个数据结构结构的二元组定义形式是什么样的？举例解释其含义。 [解答] 概括地说，数据结构是互相有关联的数据元素的集合。也就是说，数据结构是由某个数据元素的集合和该集合中的数据元素之间的关系组成的，因此数据结构可以用一个二元组来表示。例如，B=（D，R），其中D是某一数据元素的集合，R是D上的关系的有限集。R所表示的是集合D的数据元素之间的逻辑关系，它表示的可能是数据元素之间客观存在的某种联系，也可能是为了处理问题的需要而人为组织的数据元素之间的某种关系，因此，称之为数据的逻辑结构。例如，一个农历节气表，就构成了一个数据结构，其数据元素是一年的农历二十四节气，数据元素之间的关系是节气的时间先后关系。又如，一个某年级学生的成绩排序表，也是一个数据结构，其数据元素是包含成绩项的该年级的学生记录，数据元素之间的关系是学生之间的成绩高低关系。为了在计算机中进行数据处理，必须把从实际问题中抽象出来的数据的逻辑结构映象到计算机的存储器中，即要把抽象出来的数据元素集合D 和数据元素之间的关系存储到计算机的存储器中，称之为数据的物理结构或存储结构，它是数据的逻辑结构在计算机中的表示。 1.2假设R是集合M上的一个关系，R的定义是什么？对实际问题而言，其含义是什么？ [解答] 如果R是对集合M自身的笛卡尔积所取的一个子集，那么我们就说“R是集合M上的一个关系”。对实际问题而言，它表示的是集合M中元素的某种相关性。例如，对于参加一个羽毛球比赛的运动员集合，可以用一个二元关系表示出各场比赛的胜负关系。对于一组课程的集合，可以用一个二元关系表示出各门课程之间的先修和后续关系等等。 1.3设有集合M={d1,d2,d3,d4,d5}上的一个关 R={(d1,d2),(d2,d4),(d4,d5),(d2,d5),(d1,d4),(d1,d5),(d3,d5),(d1,d3)}，试说明关系R具有什么样的性质。 [解答] 从二元关系的基本性质容易验证，该关系R是反自反的、反对称的、传递的关系。 因为关系R中没有(d i,d i)这样的元素，所以它是反自反的。 因为关系R中没有(元素d i,d j)和(d j,d i)同时存在的情况，所以它是反对称的。 关系R 的传递性表现在： 有元素(d1,d2),(d2,d4)，同时有元素(d1,d4), 有元素(d1,d2),(d2,d5)，同时有元素(d1,d5), 有元素(d1,d3),(d3,d5)，同时有元素(d1,d5)， 有元素(d1,d4),(d4,d5)，同时有元素(d1,d5)， 有元素(d2,d4),(d4,d5)，同时有元素(d2,d5)。 1.4什么是线性结构？什么是非线性结构？举例说明。 [解答] 《中华人民共和国城乡规划法》试题答案 一、填空题（每空1分，共20分） 1、城镇体系规划、城市规划、镇规划、乡规划 2、城乡统筹、合理布局、节约土地、集约发展、先规划后建设 3、县人民政府城乡规划主管部门、县人民政府、本级人民代表大会常务委员会、上一级人民政府 4、基础设施、公共服务设施、新区开发、旧区改建 5、城市总体规划、镇总体规划、国民经济和社会发展规划 二、单项选择题（每题3分，共15分） 1、B 2、A 3、A 4、C 5、D 二、多项选择题（每题5分，共15分） 1、ABC 2、ABCD 3、ABCD 四、判断题（每题2分，共20分） 1、√ 2、× 3、× 4、√ 5、√ 6、× 7、√ 8、√ 9、×10、√ 五、问答题（每题10分，共30分） 1、《城乡规划法》规定：地方各级人民政府应当向本级人民代表大会常务委员会或者乡、镇人民代表大会报告城乡规划的实施情况，并接受监督。（第52条） 城乡规划报送审批前，组织编制机关应当依法将城乡规划草案予以公告，并采取论证会、听证会或者其他方式征求专家和公众的意见。公告的时间不得少于三十日。组织编制机关应当充分考虑专家和公众的意见，并在报送审批的材料中附具意见采纳情况及理由。（第26条） 村庄规划在报送审批前，应当经村民会议或者村民代表或者村民代表会议讨论同意。（第22条） 城乡规划经批准后应及时向社会公布，但法律、行政法规规定不得公开的内容除外。（第8条） 省域城镇体系规划、城市总体规划、镇总体规划的组织编制机关，应当组织有关部门和专家定期对规划实施情况进行评估，并采取论证会、听证会或者其他方式征求公众意见。组织编制机关应当向本级人民代表大会常务委员会、镇人民代表大会和原审批机关提出评估报告并附具征求意见的情况。（第46条） 任何单位和个人都应当遵守经依法批准并公布的城乡规划，服从规划管理，并有权就涉及及其利害关系的建设活动是否符合规划的要求向城乡规划主管部门查询。任何单位和个人都有权向城乡规划主管部门或者其他有关部门举报或者控告违反城乡规划的行为。（第9条） 2、《城乡规划法》规定：“制定和实施城乡规划，应当遵循城乡统筹、合理布局、节约土地、集约发展和先规划后建设的原则，改善生态环境，促进资源、能源节约和综合利用，保护耕地等自然资源和历史文化遗产，保持地方特色、民族特色和传统风貌，防止污染和其他公害，并符合区域人口发展、国防建设、防灾减灾和公共卫生、公共安全的需要。”（第4条） 将自然与历史文化遗产保护作为城市总体规划、镇总体规划的强制性内容，以及乡规划和村庄规划的内容。（第17、18条） 在城市新区的开发和建设中，严格保护自然资源和生态环境，体现地方特色；在旧城区改建中，保护历史文化遗产和传统风貌；在城乡建设和发展中，依法保护和合理利用风景名胜资源。（第30、31、32条） 3、《中华人民共和国城乡规划法》第四十七条规定，有下列情形之一的，组织编制机关方可数据结构第一章试题
党员干部十九党知识考试试题及答案
中华人民共和国城乡规划法试卷一含答案
经典数据结构面试题(含答案)
数据结构课后习题及解析第一章
中华人民共和国城乡规划法试题及详细答案解析(供参考)
数据结构模拟卷(含答案)经典习题培训讲学
2019年党建知识竞赛题库含答案
城乡规划法试题及答案
数据结构模拟卷(含答案)经典习题
数据结构第一章练习题
经典数据结构上机题_答案解析
经典数据结构面试题(含答案)
数据结构习题汇编01 第一章 绪论 试题
中华人民共和国城乡规划法试题和答案
数据结构经典题目c语言代码
数据结构第1章习题解答..
《中华人民共和国城乡规划法》试题及其答案