李云清揭安全数据结构答案
1
数据结构
（C 语言版）（第2 版）
习题解析
揭安全李云清杨庆红
江西师范大学计算机信息工程学院
联系方式：janquan@https://www.wendangku.net/doc/f513059091.html,
（习题答案仅供参考）
2
第1 章绪论
1.1 什么是数据结构？
【答】：数据结构是指按一定的逻辑结构组成的一批数据，使用某种存储结构将这批数据存储
于计算机中，并在这些数据上定义了一个运算集合。
1.2 数据结构涉及哪几个方面？
【答】：数据结构涉及三个方面的内容，即数据的逻辑结构、数据的存储结构和数据的运算集
合。
1.3 两个数据结构的逻辑结构和存储结构都相同，但是它们的运算集合中有一个运算的定义
不
一样，它们是否可以认作是同一个数据结构？为什么？
【答】：不能，运算集合是数据结构的重要组成部分，不同的运算集合所确定的数据结构是不
一样的，例如，栈与队列它们的逻辑结构与存储结构可以相同，但由于它们的运算集合不一样，
所以它们是两种不同的数据结构。
1.4 线性结构的特点是什么？非线性结构的特点是什么？
【答】：线性结构元素之间的关系是一对一的，在线性结构中只有一个开始结点和一个终端结
点，其他的每一个结点有且仅有一个前驱和一个后继结点。而非线性结构则没有这个特点，元
素之间的关系可以是一对多的或多对多的。
1.5 数据结构的存储方式有哪几种？
【答】：数据结构的存储方式有顺序存储、链式存储、散列存储和索引存储等四种方式。1.6 算法有哪些特点？它和程序的主要区别是什么？
【答】：算法具有（1）有穷性（2）确定性（3）0 个或多个输入（4）1 个或多个输出（5）
可
行性等特征。程序是算法的一种描述方式，通过程序可以在计算机上实现算法。
1.7 抽象数据类型的是什么？它有什么特点？
【答】：抽象数据类型是数据类型的进一步抽象，是大家熟知的基本数据类型的延伸和发展。抽象数据类型是与表示无关的数据类型，是一个数据模型及定义在该模型上的一组运算。对一
个抽象数据类型进行定义时，必须给出它的名字及各运算的运算符名，即函数名，并且规定这
些函数的参数性质。一旦定义了一个抽象数据类型及具体实现，程序设计中就可以像使用基本
数据类型那样，十分方便地使用抽象数据类型。抽象数据类型的设计者根据这些描述给出操作
的具体实现，抽象数据类型的使用者依据这些描述使用抽象数据类型。
1.8 算法的时间复杂度指的是什么？如何表示？
【答】：算法执行时间的度量不是采用算法执行的绝对时间来计算的，因为一个算法在不同的
机器上执行所花的时间不一样，在不同时刻也会由于计算机资源占用情况的不同，使得算法在
同一台计算机上执行的时间也不一样，另外，算法执行的时间还与输入数据的状态有关，所以
对于算法的时间复杂性，采用算法执行过程中其基本操作的执行次数，称为计算量来度量。算
法中基本操作的执行次数一般是与问题规模有关的，对于结点个数为n 的数据处理问题，用
T(n)表示算法基本操作的执行次数。为了评价算法的执行效率，通常采用大写O 符号表示算法
的时间复杂度，大写O 符号给出了函数f 的一个上限。其它义如下：
3
定义：f (n)=O (g (n)) 当且仅当存在正的常数c 和n0，使得对于所有的n≥n0，有f (n) ≤c g(n)。上述定义表明，函数f 顶多是函数g 的c 倍，除非n 小于n0。因此对于足够大的n (如n≥n0)，g 是f 的一个上限（不考虑常数因子c）。在为函数f 提供一个上限函数g 时，通常使用比较
简单的函数形式。比较典型的形式是含有n 的单个项（带一个常数系数）。表1-1 列出了一
些
常用的g 函数及其名称。对于表1-1 中的对数函数logn，没有给出对数基，原因是对于任何
大
于1 的常数a 和b 都有log a n =log b n/log b a,所以log a n 和log b n 都有一个相对的乘法系数
1/log b a，
其中a 是一个常量。
表1-1 常用的渐进函数
1.9 算法的空间复杂度指的是什么？如何表示？
【答】：算法的空间复杂度是指算法在执行过程中占用的额外的辅助空间的个数。可以将它表
示为问题规模的函数，并通过大写O符号表示空间复杂度。
1.10 对于下面的程序段，分析带下划线的语句的执行次数，并给出它们的时间复杂度T(n)。（1）i++;
（2）for(i=0;i if (a[i] （3）for(i=0;i for(j=0;j printf(“%d”,i+j); （4）for (i=1;i<=n-1;i++) { k=i; for(j=i+1;j<=n;j++) if(a[j]>a[j+1]) k=j; t=a[k]; a[k]=a[i]; a[i]=t; } （5）for(i=0;i for(j=0;j {++x;s=s+x;} 【答】：（1）O（1）；（2）O（n）；（3）O（n2）；（4）O（n）；（5）O（n2） 4 第2 章线性表及其顺序存储 2.1 选择题 （1）表长为n 的顺序存储的线性表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均个数为（E ），删除一个元素所需移动元素的平均个数为（A ）。 A．（n ?1）/2 B．n C．n + 1 D．n ?1 E．n/2 F．(n + 1)/2 G．(n ?2)/2 （2）设栈S 和队列Q 的初始状态为空，元素e1、e2、e3、e4、__________e5 和e6 依次通过栈S， 一个元素出栈后即进入队列Q，若6 个元素出队的序列为e2、e4、e3、e6、e5 和e1，则栈S 的容量至少应该为（C ）。 A．6 B．4 C．3 D．2 （3）设栈的输入序列为1、2、3 …n，若输出序列的第一个元素为n，则第i 个输出的元素 为 （B ）。 A．不确定B．n ?i + 1 C．i D．n ?i （4）在一个长度为n 的顺序表中删除第i 个元素（1< = i< = n）时，需向前移动（A ）个元素。 A．n?i B．n ?i +1 C．n ?i ?1 D．i （5）若长度为n 的线性表采用顺序存储结构存储，在第i 个位置上插入一个新元素的时 间复杂度为（A ）。 A．O(n) B．O(1) C．O(n2) D．O(n3) （6）表达式a*(b+c)?d 的后缀表达式是（B ）。 A．abcd*+?B．abc+*d?C．abc*+d?D．?+*abcd （7）队列是一种特殊的线性表，其特殊性在于（C ）。 A．插入和删除在表的不同位置执行B．插入和删除在表的两端位置执行 C．插入和删除分别在表的两端执行D．插入和删除都在表的某一端执行 （8）栈是一种特殊的线性表，具有（B ）性质。 A．先进先出B．先进后出C．后进后出D．顺序进出 （9）顺序循环队列中（数组的大小为n），队头指示front 指向队列的第1 个元素，队尾指示rear 指向队列最后元素的后1 个位置，则循环队列中存放了n ? 1 个元素，即循环队列满 的条件为（B ）。 A．(rear + 1)%n = front ?1 B．(rear + 1)%n = front C．(rear)%n = front D．rear + 1 = front （10）顺序循环队列中（数组的大小为6），队头指示front 和队尾指示rear 的值分别为3 和0，当从队列中删除1 个元素，再插入2 个元素后，front 和rear 的值分别为（D ）。 A．5 和1 B．2 和4 C．1 和5 D．4 和2 2.2 什么是顺序表？什么是栈？什么是队列？ 5 【答】：当线性表采用顺序存储结构时，即为顺序表。栈是一种特殊的线性表，它的特殊性表 现在约定了在这种线性表中数据的插入与删除操作只能在这种线性表的同一端进行（即栈顶）， 因此，栈具有先进后出、后进先出的特点。队列也是一种特殊的线性表，它的特殊性表现在约 定了在这种线性表中数据的插入在表的一端进行，数据的删除在表的另一端进行，因此队列具 有先进先出，后进后出的特点。 2.3 设计一个算法，求顺序表中值为x 的结点的个数。 【答】：顺序表的存储结构定义如下（文件名seqlist.h）： #include #define N 100 /*预定义最大的数据域空间*/ typedef int datatype; /*假设数据类型为整型*/ typedef struct { datatype data[N]; /*此处假设数据元素只包含一个整型的关键字域*/ int length; /*线性表长度*/ } seqlist; /*预定义的顺序表类型*/ 算法countx（L,x）用于求顺序表L 中值为x 的结点的个数。 int countx(seqlist *L,datatype x) { int c=0; int i; for (i=0;i if (L->data[i]==x) c++; return c; } 2.4 设计一个算法，将一个顺序表倒置。即，如果顺序表各个结点值存储在一维数组a 中， 倒 置的结果是使得数组a 中的a[0]等于原来的最后一个元素，a[1] 等于原来的倒数第2 个元素，…，a 的最后一个元素等于原来的第一个元素。 【答】：顺序表的存储结构定义同题2.3，实现顺序表倒置的算法程序如下： void verge(seqlist *L) {int t,i,j; i=0; j=L->length-1; while (i { t=L->data[i]; L->data[i++]=L->data[j]; L->data[j--]=t; } } 2.5 已知一个顺序表中的各结点值是从小到大有序的，设计一个算法，插入一个值为x 的结 点， 使顺序表中的结点仍然是从小到大有序。 【答】：顺序表的定义同题2.3，实现本题要求的算法程序如下： 6 void insertx(seqlist *L,datatype x) {int j; if (L->length { j=L->length-1; while (j>=0 && L->data[j]>x) { L->data[j+1]=L->data[j]; j--; } L->data[j+1]=x; L->length++; } } 2.6 将下列中缀表达式转换为等价的后缀表达式。 (1) 5+6*7 (2) (5-6)/7 (3) 5-6*7*8 (4) 5*7-8 (5) 5*(7-6)+8/9 (6) 7*(5-6*8)-9 【答】： (7) 5+6*7 后缀表达式：5 6 7*+ (8) (5-6)/7 后缀表达式：5 6-7/ (9) 5-6*7*8 后缀表达式：5 6 7*8*- (10) 5*7-8 后缀表达式：5 7* 8- (11) 5*(7-6)+8/9 后缀表达式：5 7 6-*8 9/+ (12) 7*(5-6*8)-9 后缀表达式：7 5 6 8*-*9- 2.7 循环队列存储在一个数组中，数组大小为n，队首指针和队尾指针分别为front 和rear， 请 写出求循环队列中当前结点个数的表达式。 【答】：循环队列中当前结点个数的计算公式是：(n+rear-front)%n 2.8 编号为1,2,3,4 的四列火车通过一个栈式的列车调度站，可能得到的调度结果有哪些？如果 有n 列火车通过调度站，请设计一个算法，输出所有可能的调度结果。 【答】： 解题思路：栈具有先进后出、后进先出的特点，因此，任何一个调度结果应该是1，2，3，4 全排列中的一个元素。由于进栈的顺序是由小到大的，所以出栈序列应该满足以下条件：对于 序列中的任何一个数其后面所有比它小的数应该是倒序的，例如4321 是一个有效的出栈序列， 1423 不是一个有效的出栈结果（4 后面比它小的两个数2，3 不是倒序）。据此，本题可以通过 算法产生n 个数的全排列，然后将满足出栈规则的序列输出。 产生n 个数的全排列有递归与非递归两种实现算法。 产生全排列的递归算法： 7 设R={r1,r2,…,r n}是要进行排列的n 个元素，R i=R-{r i}。集合X 中元素的全排列记为 perm(X)。(r i)perm(X)表示在全排列perm(X)的每一个排列前加上前缀r i 得到的排列。R 的全 排 列可归纳定义如下： 当n=1 时，perm(R)=(r)，其中r 是集合R 中惟一的元素； 当n>1 时，perm(R)由(r1)perm(R1),(r2)perm(R2),…,(r n)perm(R n)构成。 依此递归定义，可设计产生perm(R)的递归算法如下： 递归解法：(2_8_1.c) #include int cont=1; /*全局变量，用于记录所有可能的出栈序列个数*/ void print(int str[],int n); /*求整数序列str[]从k 到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; } } } /*本函数判断整数序列str[]是否满足进出栈规则,若满足则输出*/ void print(int str[],int n) {int i,j,k,l,m,flag=1,b[2]; for(i=0;i for(j=i+1;j if (str[i]>str[j]) {if (m==0) b[m++]=str[j]; else {if (str[j]>b[0]) {flag=0;} else b[0]=str[j]; } } } if(flag) /*满足出栈规则则输出str[]中的序列*/ { printf(" %2d:",cont++); for(i=0;i printf("%d",str[i]); printf("\n"); 8 } } int main() {int str[100],n,i; printf("input a int:"); /*输出排列的元素个数*/ scanf("%d",&n); for(i=0;i str[i]=i+1; printf("input the result:\n"); perm(str,0,n); printf("\n"); return 0; } 当参与进出栈的元素个数为4 时，输出的结果如下图所示。 该算法执行的时间复杂度为O（n!）。随着n 的增大，算法的执行效率非常的低。 非递归解法：（2_7_8.c） 对一组数穷尽所有排列，还可一种更直接的方法，将一个排列看作一个长整数，则所有排列对应着一组整数，将这组整数按从小到大的顺序排成一个数列，从对应最小的整数开始，按 数列的递增顺序逐一列举每个排列对应的每一个整数，这能更有效地完成排列的穷举。从一个 排列找出对应数列的下一个排列可在当前排列的基础上作部分调整来实现。倘若当前排列为1,2,4,6,5,3，并令其对应的长整数为124653。要寻找比长整数124653 更大的排列，可从该排列 的最后一个数字顺序向前逐位考察，当发现排列中的某个数字比它前一个数字大时，如本例中 的6 比它的前一位数字4 大，则说明还有可能对应更大整数的排列。但为顺序从小到大列举出 所有的排列，不能立即调整得太大，如本例中将数字6 与数字4 交换得到的排列为126453 就不是排列124653 的下一个排列。为得到排列124653 的下一个排列，应从已考察过的那部分数 字中选出比数字4 大，但又是它们中最小的那一个数字，比如数字5，与数字4 交换。该数字 也是从后向前考察过程中第一个比4 大的数字，5 与4 交换后，得到排列125643。在前面数字 1，2，5 固定的情况下，还应选择对应最小整数的那个排列，为此还需将后面那部分数字的排 列颠倒，如将数字6，4，3 的排列顺序颠倒，得到排列1,2,5,3,4,6，这才是排列1，2，4，6， 9 5，3 的下一个排列。按照以上想法可以编写非递归程序实现n 个数的全排列，对满足进出栈 规则的排列则计数并输出。 /*本程序输出1 2 ... n 个序列进栈出栈的序列*/ #include int pl(int n) { int a[100]; /*最大处理范围为99 个数*/ int flag=1,flag1=0; FILE *rf ; int i,j,k,x,count=0; rf = fopen("stack.txt", "w") ; /*pl.txt 用于存放进出栈序列结果*/ for (i=1;i<=n;i++) /*初始序列*/ a[i]=i; while (flag) /* 还剩余未输出的排列*/ { flag1=1; /* 判断本次排列是否符合进栈出栈序列 */ for (i=1;i<=n;i++) { j=i+1; while (j<=n && a[j]>a[i]) j++; /* 找a[i]后第一个比a[i]小__________的元素a[j]*/ k=j+1; while (k<=n) /* 如果a[j]后还有比a[i]小且比a[j]大的元素,则此排列无效*/ {if ( a[k] k++; } } if (flag1) { for (i=1;i<=n;i++) /*输出当前排列*/ { printf("%4d",a[i]); fprintf(rf,"%4d",a[i]);} printf("\n"); fprintf(rf,"\n"); count++; /*计数器加1*/ } i=n; /*从后向前找相邻位置后大前小的元素值*/ while (i>1 && a[i] if (i==1) flag=0; /*未找到则结束*/ else {j=i-1;i=n;/* 若找到,则在该位置的后面从右向左找第一个比该元素大的值*/ while (i>j && a[i] k=a[j]; /*交换两元素的值*/ a[j]=a[i]; a[i]=k; k=j+1; /*对交换后后面的数据由小到大排序*/ 10 for ( i=k+1;i<=n;i++) /*插入排序*/ { j=i-1; x=a[i]; while (j>=k && x a[j+1]=x; } } } fclose(rf); return count; /*返回排列总个数*/ } void main() {int n,m=0; printf("please input n:"); /*输入排列规模*/ scanf("%d",&n); m=pl(n); printf("\nm=%d",m); /*输出满足进出栈的排列总个数*/ } 程序运行时如果输入4，则输出的结果如下图所示。 该算法的时间复杂度也是O(n!)。 结论：如果n 个数按编号由小到大的顺序进栈，进栈的过程中可以出栈，则所有可能的出栈序 列的总数为： ( 1) ! ! (2 )! n n n n + 11 第3 章线性表的链式存储 3.1 选择题 （1）两个有序线性表分别具有n 个元素与m 个元素且n≤m，现将其归并成一个有序表，其最少的比较次数是（ A ）。 A．n B．m C．n ?1 D．m + n （2）非空的循环单链表head 的尾结点（由p 所指向）满足（ C ）。 A．p->next==NULL B．p==NULL C．p->next==head D．p==head （3）在带头结点的单链表中查找x 应选择的程序体是（ C ）。 A．node *p=head->next; while (p && p->info!=x) p=p->next; if (p->info==x) return p else return NULL; B．node *p=head; while (p&& p->info!=x) p=p->next; return p; C．node *p=head->next; while (p&&p->info!=x) p=p->next; return p; D．node *p=head; while (p->info!=x) p=p->next ; return p; （4）线性表若采用链式存储结构时，要求内存中可用存储单元的地址（ D ）。 A．必须是连续的 B．部分地址必须是连续的 C．一定是不连续的 D．连续不连续都可以 （5）在一个具有n 个结点的有序单链表中插入一个新结点并保持单链表仍然有序的时间复杂度是（ B ）。 A．O(1) B．O(n) C．O(n2) D．O(n log2 n) （6）用不带头结点的单链表存储队列时，其队头指针指向队头结点，其队尾指针指向队尾结点，则在进行删除操作时（ D ）。 A．仅修改队头指针 B．仅修改队尾指针 C．队头、队尾指针都要修改 D．队头,队尾指针都可能要修改 （7）若从键盘输入n 个元素，则建立一个有序单向链表的时间复杂度为（ B ）。 A．O(n) B．O(n2) C．O(n3) D．O(n ? log2n) （8）下面哪个术语与数据的存储结构无关（ D ）。 A．顺序表 B．链表 C．散列表 D．队列 （9）在一个单链表中，若删除p 所指结点的后续结点，则执行（ A ）。 A．p->next=p->next->next; B．p=p->next; p->next=p->next->next; C．p->next=p->next; D．p =p->next->next; （10）在一个单链表中，若p 所指结点不是最后结点，在p 之后插入s 所指结点，则执行（ B ）。 A．s->next=p;p->next=s; B．s->next=p->next;p->next=s; C．s->next=p->next;p=s; D．p->next=s;s->next=p; 3.2 设计一个算法，求一个单链表中的结点个数。 【答】：单链表存储结构定义如下（相关文件：linklist.h） #include 12 #include typedef struct node { int data; struct node *next; }linknode; typedef linknode *linklist; /*尾插法创建带头结点的单链表*/ linklist creatlinklist() { linklist head,r,x,s; head=r=(linklist)malloc(sizeof(linknode)); printf("\n 请输入一组以0 结束的整数序列：\n"); scanf("%d",&x); while (x) { s=(linklist)malloc(sizeof(linknode)); s->data=x; r->next=s; r=s; scanf("%d",&x); } r->next=NULL; return head; } /*输出带头结点的单链表*/ void print(linklist head) { linklist p; p=head->next; printf("List is:\n"); while(p) { printf("%5d",p->data); p=p->next; } printf("\n"); } 基于上述结构定义，求单链表中的结点个数的算法程序如下： int count(linklist head) { int c=0; linklist p=head; while (p) {c++; 13 p=p->next; } return c; } 3.3 设计一个算法，求一个带头结点单链表中的结点个数。 【答】：带头结点的单链表的存储结构定义同题3.2，实现本题功能的算法程序如下（3_3.c）#include "linklist.h" int count(linklist head) { int c=0; linklist p=head->next; while (p) {c++; p=p->next; } return c; } main() /*测试函数*/ {linklist head; head=creatlinklist(); print(head); printf("\nLength of head is:%d",count(head)); getch(); } 当输入5 个数据时，产生的输出结果如下图所示： 3.4 设计一个算法，在一个单链表中值为y 的结点前面插入一个值为x 的结点。即使值为x 的 新结点成为值为y 的结点的前驱结点。 【答】： #include "linklist.h" void insert(linklist head,int y,int x) {/*在值为y 的结点前插入一个值为x 的结点*/ linklist pre,p,s; pre=head; p=head->next; 14 while (p && p->data!=y) { pre=p; p=p->next; } if (p)/*找到了值为y 的结点*/ { s=(linklist)malloc(sizeof(linknode)); s->data=x; s->next=p; pre->next=s; } } void main() /*测试程序*/ {linklist head; int y,x; head=creatlinklist(); /*创建单链表*/ print(head); /*输出单链表*/ printf("\n 请输入y 与x 的值:\n"); scanf("%d %d",&y,&x); insert(head,y,x); print(head); } 程序的一种运行结果如下图所示： 3.5 设计一个算法，判断一个单链表中各个结点值是否有序。 【答】： #include "linklist.h" int issorted(linklist head,char c) /*当参数c=’a’时判断链表是否为升序，当参数c=’d’是判断链表是否为降序*/ { int flag=1; linklist p=head->next; switch (c) {case 'a':/*判断带头结点的单链表head 是否为升序*/ 15 while (p &&p->next && flag) {if (p->data<=p->next->data) p=p->next; else flag=0; } break; case 'd':/*判断带头结点的单链表head 是否为降序*/ while (p &&p->next && flag) {if (p->data>=p->next->data) p=p->next; else flag=0; } break; } return flag; } int main() /*测试程序*/ { linklist head; head=creatlinklist(); print(head); if (issorted(head,'a')) printf("单链表head 是升序排列的！\n"); else if (issorted(head,'d')) printf("单链表head 是降序排列的！\n"); else printf("单链表head 是无序的！\n"); } 程序运行时的三种输出结果如下图所示： 3.6 设计一个算法，利用单链表原来的结点空间将一个单链表就地转置。 【答】： #include "linklist.h" void verge(linklist head) {/*本函数的功能是就地倒置带头结点的单链表*/ 16 linklist p,q; p=head->next; head->next=NULL; while (p) /*每次从原表取一个结点插入到新表的最前面*/ {q=p; p=p->next; q->next=head->next; head->next=q; } } int main() /*测试函数*/ {linklist head; head=creatlinklist(); /*创建单链表*/ print(head); /*输出原单链表*/ verge(head); /*就地倒置单链表*/ print(head); /*输出倒置后的单链表*/ } 3.7 设计一个算法，将一个结点值自然数的单链表拆分为两个单链表，原表中保留值为偶数的 结点，而值为奇数的结点按它们在原表中的相对次序组成一个新的单链表。 【答】： #include "linklist.h" linklist sprit(linklist head) { /*将带头结点的单链表head 中的奇数值结点删除生成新的单链表并返回*/ linklist L,pre,p,r; L=r=(linklist)malloc(sizeof(linknode)); r->next=NULL; pre=head; p=head->next; while (p) { if (p->data%2==1) /*删除奇数值结点*/ { pre->next=p->next; r->next=p; r=p; p=pre->next; } else /*保留偶数值结点*/ { pre=p; p=p->next; } 17 } r->next=NULL; /*置链表结束标记*/ return L; } int main() /*测试函数*/ {linklist head,L; head=creatlinklist(); /*创建单链表*/ print(head); /*输出原单链表*/ L=sprit(head); /*分裂单链表head*/ printf("\n 原单链表为:\n"); print(head); /*输出倒置后的单链表*/ printf("\n 分裂所得奇数单链表为:\n"); print(L); } 本程序的一组测试情况如下图所示。 3.8 设计一个算法，对一个有序的单链表，删除所有值大于x 而不大于y 的结点。【答】： #include "linklist.h" void deletedata(linklist head,datatype x,datatype y) { /*删除带头结点单链表中所有结点值大于x 而不大于y 的结点*/ linklist pre=head,p,q; p=head->next; /*初始化*/ while (p && p->data<=x) /*找第1 处大于x 的结点位置*/ { pre=p; p=p->next; } while (p && p->data<=y) /*找第1 处小于y 的位置*/ p=p->next; q=pre->next; /*删除大于x 而小于y 的结点*/ pre->next=p; pre=q->next; 18 while (pre!=p) /*释放被删除结点所占用的空间*/ {free(q); q=pre; pre=pre->next; } } void main() /*测试函数*/ { linklist head,L; datatype x,y; head=creatlinklist(); /*创建单链表*/ print(head); /*输出原单链表*/ printf("\n 请输入要删除的数据区间:\n"); scanf("%d%d",&x,&y); deletedata(head,x,y); print(head); /*输出删除后的单链表*/ } 3.9 设计一个算法，在双链表中值为y 的结点前面插入一个值为x 的新结点。即使值为x 的新 结点成为值为y 的结点的前驱结点。 【答】： 首先定义双链表的数据结构，相关文件dlink.h，内容如下： typedef int datatype; /*预定义的数据类型*/ typedef struct dlink_node{ /*双链表结点定义*/ datatype data; struct dlink_node *llink,*rlink; }dnode; typedef dnode* dlinklist; /*双链表结点指针类型定义*/ /*尾插法创建带头结点的双链表*/ dlinklist creatdlinklist(void) { dlinklist head,r,s; datatype x; head=r=(dlinklist) malloc(sizeof(dnode)); /*建立双链表的头结点*/ head->llink=head->rlink=NULL; printf("\n 请输入双链表的内容：（整数序列，以0 结束）\n"); scanf("%d",&x); while (x) /*输入结点值信息，以0 结束*/ { s=(dlinklist ) malloc(sizeof(dnode)); s->data=x; s->rlink=r->rlink; /*将新结点s 插入到双链表链尾*/ 19 s->llink=r; r->rlink=s; r=s; scanf("%d",&x); } return head; } /*输出双链表的内容*/ void print(dlinklist head) { dlinklist p; p=head->rlink; printf("\n 双链表的内容是：\n"); while (p) { printf("%5d",p->data); p=p->rlink; } } 本题的求解程序如下： #include #include "dlink.h" void insertxaty(dlinklist head,datatype y,datatype x) { dlinklist s,p; /*首先在双链表中找y 所在的结点，然后在y 前面插入新结点*/ p=head->rlink; while (p && p->data!=y) p=p->rlink; if (!p) printf("\n 双链表中不存在值为y 的结点,无法插入新结点!\n"); else /*插入值为x 的新结点*/ { s=(dlinklist)malloc(sizeof(dnode)); s->data=x; s->rlink=p; s->llink=p->llink; p->llink->rlink=s; p->llink=s; } } void main() /*测试函数*/ { dlinklist head; datatype x,y; 20 head=creatdlinklist(); print(head); printf("\n 请输入要输入的位置结点值y:\n"); scanf("%d",&y); printf("\n 请输入要输入的结点值x:\n"); scanf("%d",&x); insertxaty(head,y,x);/*在值为y 的结点前插入值为x 的新结点*/ 数据结构实验报告 一．题目要求 1）编程实现二叉排序树，包括生成、插入，删除； 2）对二叉排序树进行先根、中根、和后根非递归遍历； 3）每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。 4）分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率，并说明在什么情况下二叉排序树效率高,为什么? 二．解决方案 对于前三个题目要求，我们用一个程序实现代码如下 #include 党员干部十九党知识考试试题及答案 一、单选题 中国共产党第十九次全国代表大会召开时间（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. 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和运算等的学科。 2. 数据结构被形式地定义为（D, R），其中D是数据元素的有限集合，R是D上的关系有限集合。 3. 数据结构包括数据的逻辑结构、数据的存储结构和数据的运算这三个方面的内容。 4. 数据结构按逻辑结构可分为两大类，它们分别是线性结构和非线性结构。 5. 线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。 6．在线性结构中，第一个结点没有前驱结点，其余每个结点有且只有1个前驱结点；最后一个结点没有后续结点，其余每个结点有且只有1个后续结点。 7. 在树形结构中，树根结点没有前驱结点，其余每个结点有且只有1个前驱结点；叶子结 点没有后续结点，其余每个结点的后续结点数可以任意多个。 8. 在图形结构中，每个结点的前驱结点数和后续结点数可以任意多个。 9．数据的存储结构可用四种基本的存储方法表示，它们分别是顺序、链式、索引和散列。 10. 数据的运算最常用的有5种，它们分别是插入、删除、修改、查找、排序。 11. 一个算法的效率可分为时间效率和空间效率。 二、单项选择题 （B）1. 非线性结构是数据元素之间存在一种： A）一对多关系B）多对多关系 C）多对一关系D）一对一关系 （ C ）2. 数据结构中，与所使用的计算机无关的是数据的结构； A) 存储B) 物理 C) 逻辑D) 物理和存储 （C）3. 算法分析的目的是： A) 找出数据结构的合理性 B) 研究算法中的输入和输出的关系 C) 分析算法的效率以求改进 D) 分析算法的易懂性和文档性 （A）4. 算法分析的两个主要方面是： A) 空间复杂性和时间复杂性 B) 正确性和简明性 C) 可读性和文档性 D) 数据复杂性和程序复杂性 （ C ）5. 计算机算法指的是： A) 计算方法 B) 排序方法 C) 解决问题的有限运算序列 D) 调度方法 （B）6. 计算机算法必须具备输入、输出和等5个特性。 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={ 一，实验题目 实验十一：图实验 采用邻接表存储有向图，设计算法判断任意两个顶点间手否存在路径。 二，问题分析 本程序要求采用邻接表存储有向图，设计算法判断任意两个顶点间手否存在路径，完成这些操作需要解决的关键问题是：用邻接表的形式存储有向图并输出该邻接表。用一个函数实现判断任意两点间是否存在路径。 1，数据的输入形式和输入值的范围：输入的图的结点均为整型。 2，结果的输出形式：输出的是两结点间是否存在路径的情况。 3，测试数据：输入的图的结点个数为：4 输入的图的边得个数为：3 边的信息为：1 2，2 3，3 1 三，概要设计 （1）为了实现上述程序的功能，需要： A，用邻接表的方式构建图 B，深度优先遍历该图的结点 C，判断任意两结点间是否存在路径 （2）本程序包含6个函数： a，主函数main（） b，用邻接表建立图函数create_adjlistgraph() c，深度优先搜索遍历函数dfs() d，初始化遍历数组并判断有无通路函数dfs_trave() e，输出邻接表函数print() f，释放邻接表结点空间函数freealgraph() 各函数间关系如右图所示： 四，详细设计 （1）邻接表中的结点类型定义： typedef struct arcnode{ int adjvex; arcnode *nextarc; }arcnode; （2）邻接表中头结点的类型定义： typedef struct{ char vexdata; arcnode *firstarc; }adjlist; （3）邻接表类型定义： typedef struct{ adjlist vextices[max]; int vexnum,arcnum; }algraph; （4）深度优先搜索遍历函数伪代码： int dfs(algraph *alg,int i,int n){ arcnode *p; visited[i]=1; p=alg->vextices[i].firstarc; while(p!=NULL) { if(visited[p->adjvex]==0){ if(p->adjvex==n) {flag=1; } dfs(alg,p->adjvex,n); if(flag==1) return 1; } p=p->nextarc; } return 0; } （5）初始化遍历数组并判断有无通路函数伪代码： void dfs_trave(algraph *alg,int x,int y){ int i; for(i=0;i<=alg->vexnum;i++) visited[i]=0; dfs(alg,x,y); } 五，源代码 #include "stdio.h" #include "stdlib.h" #include "malloc.h" #define max 100 typedef struct arcnode{ //定义邻接表中的结点类型 int adjvex; //定点信息 arcnode *nextarc; //指向下一个结点的指针nextarc }arcnode; typedef struct{ //定义邻接表中头结点的类型 char vexdata; //头结点的序号 arcnode *firstarc; //定义一个arcnode型指针指向头结点所对应的下一个结点}adjlist; typedef struct{ //定义邻接表类型 adjlist vextices[max]; //定义表头结点数组 文档来源为:从网络收集整理.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 ) 16 void Descend(int &x, int &y, int &z) { int t; if(x while(result[i].sport!=NULL) { switch(result[i].schoolname) { case 'A': score[0].totalscore+=result[i].score; if(result[i].gender==male) score[0].malescore+=result[i].score; else score[0].femalescore+=result[i].score; break; case 'B': score[1].totalscore+=result[i].score; if(result[i].gender==male) score[1].malescore+=result[i].score; else score[1].femalescore+=result[i].score; break; case 'C': score[2].totalscore+=result[i].score; if(result[i].gender==male) score[2].malescore+=result[i].score; else score[2].femalescore+=result[i].score; break; case 'D': score[3].totalscore+=result[i].score; if(result[i].gender==male) score[3].malescore+=result[i].score; else score[3].femalescore+=result[i].score; break; case 'E': score[4].totalscore+=result[i].score; if(result[i].gender==male) score[4].malescore+=result[i].score; else score[4].femalescore+=result[i].score; break; } i++; } for(s='A';s<='E';s++) { printf("School %c:\n",s); printf("Total score of male:%d\n",score[i].malescore); printf("Total score of female:%d\n",score[i].femalescore); printf("Total score of all:%d\n\n",score[i].totalscore); } } 19 Status Series(int ARRSIZE, int a[]) 第1章绪论工程大数电习题答案册工程大数电习题答案 册 2.(1)×(2)×(3)√ 3.（1）A（2）C（3）C 5.计算下列程序中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 6.编写算法，求一元多项式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）通过全局变量隐式传递 优点：减少实参与形参的个数，从而减少内存空间以及传递数据时的时间消耗 缺点：函数通用性降低，移植性差 算法如下：通过全局变量隐式传递参数 PolyValue() { int i,n; float x,a[],p; printf(“\nn=”); scanf(“%f”,&n); printf(“\nx=”); scanf(“%f”,&x); for(i=0;i 数据结构实验---图的储存与遍历 学号： 姓名： 实验日期： 2016.1.7 实验名称： 图的存贮与遍历 一、实验目的 掌握图这种复杂的非线性结构的邻接矩阵和邻接表的存储表示，以及在此两种常用存储方式下深度优先遍历(DFS)和广度优先遍历(BFS)操作的实现。 二、实验内容与实验步骤 题目1：对以邻接矩阵为存储结构的图进行DFS 和BFS 遍历 问题描述：以邻接矩阵为图的存储结构，实现图的DFS 和BFS 遍历。 基本要求：建立一个图的邻接矩阵表示，输出顶点的一种DFS 和BFS 序列。 测试数据：如图所示 题目2：对以邻接表为存储结构的图进行DFS 和BFS 遍历 问题描述：以邻接表为图的存储结构，实现图的DFS 和BFS 遍历。 基本要求：建立一个图的邻接表存贮，输出顶点的一种DFS 和BFS 序列。 测试数据：如图所示 V0 V1 V2 V3 V4 三、附录： 在此贴上调试好的程序。 #include #define M 100 typedef struct node { char vex[M][2]; int edge[M ][ M ]; int n,e; }Graph; int visited[M]; Graph *Create_Graph() { Graph *GA; int i,j,k,w; GA=(Graph*)malloc(sizeof(Graph)); printf ("请输入矩阵的顶点数和边数(用逗号隔开)：\n"); scanf("%d,%d",&GA->n,&GA->e); printf ("请输入矩阵顶点信息：\n"); for(i = 0;i 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.数据的逻辑结构与数据元素本身的容和形式无关。（√） 2.一个数据结构是由一个逻辑结构和这个逻辑结构上的一个基本运算集构成的整体。（√） 3.数据元素是数据的最小单位。（√） 4.数据的逻辑结构和数据的存储结构是相同的。（×） 5.程序和算法原则上是没有区别的，所以在讨论数据结构时可以通用。（×） 6.从逻辑关系上讲，数据结构主要分为线性结构和非线性结构。（√） 7.数据的存储结构是数据的逻辑结构的存储映像。（×） 8.数据的物理结构是指数据在计算机实际的存储形式。（√） 9.数据的逻辑结构是依赖于计算机的。（×） 10.算法是对解题方法和的描述步骤。（√） 填空题： 1.数据有逻辑结构和存储结构两种结构。 2.数据逻辑结构除了集合以外，还包括线性结构、树形结构和图形结构。 3.数据结构按逻辑结构可分为两大类，它们是线性结构和非线性结构。 4.树形结构和图形结构合称为非线性结构。 5.在树形结构中，除了树根结点以外，其余每个结点只有 1 个前驱结点。 6.在图形结构中，每个结点的前驱结点数和后继结点数可以任意多个。 7.数据的存储结构又叫物理结构。 8.数据的存储结构形式包括顺序存储、链式存储、索引存储和散列存储。 9.线性结构中的元素之间存在一对一的关系。 10.树形结构中的元素之间存在一对多的关系。 11.图形结构的元素之间存在多对多的关系。 12.数据结构主要研究数据的逻辑结构、存储结构和算法（或运算）3个方面 的容。 13.数据结构被定义为（D，R），其中D是数据的有限集合，R是D上的关系的 有限集合。 14.算法是一个有穷指令的集合。 15.算法效率的度量可以分为事先估算和事后统计法。 16.一个算法的时间复杂性是算法输入规模的函数。 17.算法的空间复杂度是指该算法所耗费的存储空间，它是该算法求解问题 规模n的函数。 18.若一个算法中的语句频度之和为T（n）=6n+3nlog2n，则算法的时间复杂度为O （nlog2n ）。 若一个算法中的语句频度之和为T（n）=3n+nlog2n+n2，则算法的时间复杂度为 ___O（n*n）_______ 。 数据结构是一门研究非数值计算的程序设计总是中计算机的操作对象，以及它们之间的关系和运算的学科。 19.串的两种最基本的存储方式是顺序存储方式链式存储方式。 20.两个串相等的充分必要条件是、长度相等对应位置的字符相同。 1-1什么是数据? 它与信息是什么关系? 【解答】 什么是信息？广义地讲，信息就是消息。宇宙三要素（物质、能量、信息）之一。它是现实世界各种事物在人们头脑中的反映。此外，人们通过科学仪器能够认识到的也是信息。信息的特征为：可识别、可存储、可变换、可处理、可传递、可再生、可压缩、可利用、可共享。 什么是数据？因为信息的表现形式十分广泛，许多信息在计算机中不方便存储和处理，例如，一个大楼中4部电梯在软件控制下调度和运行的状态、一个商店中商品的在库明细表等，必须将它们转换成数据才能很方便地在计算机中存储、处理、变换。因此，数据(data)是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。在计算机中，信息必须以数据的形式出现。 1-2什么是数据结构? 有关数据结构的讨论涉及哪三个方面? 【解答】 数据结构是指数据以及相互之间的关系。记为：数据结构= { D, R }。其中，D是某一数据对象，R是该对象中所有数据成员之间的关系的有限集合。 有关数据结构的讨论一般涉及以下三方面的内容： ①数据成员以及它们相互之间的逻辑关系，也称为数据的逻辑结构，简称为数据结构； ②数据成员极其关系在计算机存储器内的存储表示，也称为数据的物理结构，简称为存储结构； ③施加于该数据结构上的操作。 数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储不是一码事，是与计算机存储无关的。因此，数据的逻辑结构可以看作是从具体问题中抽象出来的数据模型，是数据的应用视图。数据的存储结构是逻辑数据结构在计算机存储器中的实现（亦称为映像），它是依赖于计算机的，是数据的物理视图。数据的操作是定义于数据逻辑结构上的一组运算，每种数据结构都有一个运算的集合。例如搜索、插入、删除、更新、排序等。 1-3数据的逻辑结构分为线性结构和非线性结构两大类。线性结构包括数组、链表、栈、 队列、优先级队列等; 非线性结构包括树、图等、这两类结构各自的特点是什么？ 【解答】 线性结构的特点是：在结构中所有数据成员都处于一个序列中，有且仅有一个开始成员和一个终端成员，并且所有数据成员都最多有一个直接前驱和一个直接后继。例如，一维数组、线性表等就是典型的线性结构 非线性结构的特点是：一个数据成员可能有零个、一个或多个直接前驱和直接后继。例如，树、图或网络等都是典型的非线性结构。 1-4．什么是抽象数据类型？试用C++的类声明定义“复数”的抽象数据类型。要求 (1) 在复数内部用浮点数定义它的实部和虚部。 (2) 实现3个构造函数：缺省的构造函数没有参数；第二个构造函数将双精度浮点数赋给复数的实部，虚部置为0；第三个构造函数将两个双精度浮点数分别赋给复数的实部和虚部。 (3) 定义获取和修改复数的实部和虚部，以及+、-、*、/等运算的成员函数。 邻接矩阵的实现 1. 实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现2. 实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历3．设计与编码MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template int vertexNum, arcNum; }; #endif MGraph.cpp #include 第 1 章绪论 课后习题讲解 1. 填空 ⑴（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 【解答】数据元素 ⑵（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。 【解答】数据项，数据元素 【分析】数据结构指的是数据元素以及数据元素之间的关系。 ⑶从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。 【解答】集合，线性结构，树结构，图结构 ⑷数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）和（）。 【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系 ⑸算法具有五个特性，分别是（）、（）、（）、（）、（）。 【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性 ⑹算法的描述方法通常有（）、（）、（）和（）四种，其中，（）被称为算法语言。 【解答】自然语言，程序设计语言，流程图，伪代码，伪代码 ⑺在一般情况下，一个算法的时间复杂度是（）的函数。 【解答】问题规模 ⑻设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若为n*log25n，则表示成数量级的形式为（）。 【解答】Ο(1)，Ο(nlog2n) 【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。 2. 选择题 ⑴顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链接存储结构中的数据元素之间的逻辑关系是由（）表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针 【解答】C，D 【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。 填空题（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; 求串长*/数据结构实验报告
党员干部十九党知识考试试题及答案
中华人民共和国城乡规划法试卷一含答案
数据结构习题解答
严蔚敏版数据结构课后习题答案-完整版
数据结构实验十一：图实验
中华人民共和国城乡规划法试题及详细答案解析(供参考)
数据结构题集c语言版答案严蔚敏吴伟民[1]
最全数据结构课后习题答案(耿国华版[12bb]
数据结构实验---图的储存与遍历
2019年党建知识竞赛题库含答案
城乡规划法试题及答案
数据结构题集与答案
数据结构课后习题答案清华大学出版社殷人昆
数据结构实验报告图实验
数据结构习题与答案
数据结构课后习题及答案
- 数据结构习题集(答案)
- 数据结构习题集答案C语言版
- 数据结构习题集答案解析--清华大学版
- 数据结构习题集包含全部答案
- 数据结构习题与答案
- 数据结构习题和答案及解析
- 数据结构习题集答案
- 数据结构习题集答案(c版)(清华大学 严蔚敏)
- 数据结构习题集答案(c版)(清华大学-严蔚敏)
- 清华数据结构习题集答案
- 最新数据结构习题与答案--图
- 数据结构练习题及答案 清华出版社
- 数据结构习题集(答案)
- 清华数据结构习题集答案(C语言版严蔚敏)
- 数据结构习题集(答案)
- 数据结构习题集答案(c版)(清华大学严蔚敏)
- 数据结构习题及解答
- 数据结构习题集答案_C语言版(严蔚敏 吴伟民)
- 数据结构习题及参考答案
- 数据结构习题集和答案