01绪论和02线性表
数据结构第一章绪论和第二章线性表练习题
第一章概论
一、名词解释
数据表示 2.数据处理 3.数据 4.数据元素 5.逻辑关系 6.逻辑结构7.结构
8.运算 9.基本运算 10.存储结构 11.顺序存储结构 12.链式存储结构
13.索引存储结构 14.散列存储结构 15.算法 16.运行终止的程序可执行部分
17.伪语言算法 18.非形式算法 19.时空性能 20.时间复杂性 21.数据结构
二、填空题
1.计算机专业人员必须完成的两项基本任务是：_________和__________。
2.数据在计算机存储器中的存在形式称为_________。
3.概括地说，数据结构课程的主要内容包括: 数据的__________、定义在_________、数据的__________的实现。此外，该课程还要考虑各种结构和实现方法的__________。
4.由一种__________结构和一组__________构成的整体是实际问题的一种数学模型，这种数学模型的建立、选择和实现是数据结构的核心问题。
5.存储结构是逻辑结构的__________实现。
6.数据表示任务是逐步完成的，即数据表示形式的变化过程是__________->__________->__________。
7.数据处理任务也是逐步完成的，即转化过程是__________->__________->__________。
8.从数据结构的观点看，通常所说的"数据"应分成三个不同的层次，即__________、__________和__________。
9.根据需要，数据元素又被称为__________、__________、__________或__________。
10.在有些场合下，数据项又称为__________或__________，它是数据的不可分割的最小标识单位。
11.从某种意义上说，数据、数据元素和数据项实际反映了数据组织的三个层次，数据
可由若干个__________构成，数据元素可由若干个__________构成。
12.根据数据元素之间关系的不同特性，通常有__________、_________、__________、__________四类基本逻辑结构，它们反映了四类基本的数据组织形式。
13.根据操作的效果，可将运算分成以下两种基本类型：
①__________型运算，其操作改变了原逻辑结构的“值”，如结点个数、某些结点的内容等；
②__________型运算，其操作不改变原逻辑结构，只从中提取某些信息作为运算的结果。
14.将以某种逻辑结构S为操作对象的运算称为“__________”，简称“__________”。
15.一般地，可能存在同一逻辑结构S上的两个运算A和B，A的实现需要或可以利用B，而B的实现不需要利用A。在这种情况下，称A可以“__________”为B。
16.存储实现的基本目标是建立数据的__________。
17.一般地，一个存储结构包括__________、__________、__________三个主要部分。
18.通常，存储结点之间可以有__________、__________、__________、_________四种关联方式，称为四种基本存储方式。
19.可用任何一种存储方式所规定的存储结点之间的关联方式来间接表达给定逻辑
结构S中数据元素之间的逻辑关系。由此得到的存储结构，称为____________________或__________。
20.一个运算的实现是指一个完成该运算功能的__________。运算实现的核心是处
理步骤的规定，即___________。
21.任何算法都必须用某种语言加以描述。根据描述算法的语言的不同，可将算法分
为：___________、___________、___________三类。
22.数据结构课程着重评论算法的___________，又称为“___________”。
23.通常从___________、___________、___________、___________等几方面评价算法的(包括程序)的质量。
24.一个算法的时空性能是指该算法的___________和______________________，前者是算法包含的___________，后者是算法需要的___________。
25.通常采用下述办法来估算求解某类问题的各个算法在给定输入下的计算量：
①根据该类问题的特点合理地选择一种或几种操作作为“___________”；
②确定每个算法在给定输入下共执行了多少次___________，并将此次数规定为该算法在给定输入下的___________。
26.通常，一个算法在不同输入下的计算量是不同的。则可用以下两种方式来确定一个算法的计算量：
①以算法在所有输入下的计算量的最大值作为算法的计算量，这种计算量称为算法的________或___________。
②以算法在所有输入下的计算量的加权平均值作为算法的计算量，这种计算量称为算法的___________或
___________。
27.最坏情况时间复杂性和平均时间复杂性统称为___________或___________。
28.在一般情况下，一个算法的时间复杂性是___________的函数。
29.一个算法的输入规模或问题的规模是指___________。
30.常见时间复杂性的量级有：常数阶O(___________)、对数阶O(___________)、线性阶O (___________)、平方阶O(___________)、和指数阶O(___________)。通常认为，具有指数阶量级的算法是___________，而量级低于平方阶的算法是___________的。
31.数据结构的基本任务是数据结构的___________和___________。
32.数据结构的课程的主要内容可以概括为：___________、___________、___________和___________。
33.___________与数据元素本身的内容和形式无关。
34.从逻辑关系上讲，数据结构主要分为两大类，它们是___________和___________。
35.程序段“for(i=l;i<=n;i++){k++;for(j=1;j<=n;j++)l+=k;}”的时间复杂度T(n)= ___________。
36.程序段“i=1;while(i<=n)i=i*2;”的时间复杂度T(n)= ___________。
三、单项选择题
1.以下说法错误的是
①用数字式计算机解决问题的实质是对数据的加工处理
②程序设计的实质是数据处理
③数据的逻辑结构是数据的组织形式，基本运算规定了数据的基本操作方式
④运算实现是完成运算功能的算法，或这些算法的设计
⑤数据处理方式总是与数据某种相应的表示形式相联系，反之亦然
2.根据数据元素之间关系的不同特性，以下四类基本的逻辑结构反映了四类基本的
数据组织形式。以下解释错误的是 ( )
①集合中任何两个结点之间都有逻辑关系但组织形式松散
②线性结构中结点按逻辑关系依次排列形成一条"锁链"
③树形结构具有分支、层次特性，其形态有点像自然界中的树
④图状结构中的各个结点按逻辑关系互相缠绕，任何两个结点都可以邻接
3.关于逻辑结构，以下说法错误的是 ( )
①逻辑结构与数据元素本身的形成、内容无关
②逻辑结构与数据元素的相对位置有关
③逻辑结构与所含结点个数无关
④一些表面上很不相同的数据可以有相同的逻辑结构
⑤逻辑结构是数据组织的某种"本质性"的东西
4.根据操作的效果，可将运算分成加工型运算、引用型运算两种基本类型。对于表格
处理中的五种功能以下解释错误的是 ( )
①查找引用型运算，功能是找出满足某种条件的结点在s(线形结构)中的位置
②读取引用型运算功能是读出s(线形结构)中某指定位置结点的内容
③插入引用型运算，功能是在s(线形结构)的某指定位置上增加一个新结点
④删除加工型运算，功能是撤消s(线形结构)某指定位置上的结点
⑤更新加工型运算，功能是修改s(线形结构)中某指定结点的内容
5.一般地，一个存储结构包括以下三个主要部分。以下说法错误的是 ( )
①存储结点每个存储结点可以存放一个或一个以上的数据元素
②数据元素之间关联方式的表示也就是逻辑结构的机内表示
③附加设施，如为便于运算实现而设置的“哑结点”等等
6.一般地，一个存储结构包括以下三个主要部分。以下说法错误的是
①每个存储结点只能存放一个数据元素 ( )
②数据元素之间的关联方式可由存储结点之间的关联方式直接表达
③一种存储结构可以在两个级别上讨论。其一是机器级，其二是语言级
④语言级描述可经编译自动转换成机器级因此也可以看成是一种机内表示
7.通常从正确性、易读性、健壮性、高效性等四个方面评价算法(包括程序)的质
量。以下解释错误的是 ( )
①正确性算法应能正确地实现预定的功能(即处理要求)
②易读性算法应易于阅读和理解以便于调试修改和扩充
③健壮性当环境发生变化时，算法能适当地做出反应或进行处理，不会产生不需要的运行结果
④高效性即达到所需要的时间性能
8.对于数据结构课程的主要内容，以下解释正确的是 ( )
①数据结构的定义，包括逻辑结构、存储结构和基本运算集
②数据结构的实现，包括存储实现、运算实现和基本运算集
③数据结构的评价和选择，包括逻辑结构的选择、基本运算集的选择和存储
选择
9，与数据元素本身的形式、内容、相对位置、个数无关的是数据的 ( )
①存储结构②存储实现③逻辑结构④运算实现10顺序存储结构( )
①仅适合于静态查找表的存储
②仅适合于动态查找表的存储
③既适合静态又适合动态查找表的存储
④既不适合静态又不适合动态查找表的存储
11.算法的时间复杂度，都要以通过算法中执行频度最高的语句的执行次数来确定这种
观点 ( )
①正确②错误
12以下说法正确的是 ( )
①所谓数据的逻辑结构指的是数据元素之间的逻辑关系。
②逻辑结构与数据元素本身的内容和形式无关
③顺序文件只适合于存放在磁带上，索引文件只能存放在磁盘上
④基于某种逻辑结构之上的运算，其实现是惟一的
13以下说法正确的是 ( )
①数据元素是数据的最小单位
②数据项是数据的基本单位
③数据结构是带有结构的各数据项的集合
④数据结构是带有结构的数据元素的集合
14以下说法错误的是 ( )
①所谓数据的逻辑结构指的是数据元素之间的逻辑关系的整体
②数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用需要而建立的
③数据结构、数据元素、数据项在计算机中的映象分别称为存储结构、结点、数据域
④数据项是数据的基本单位
15通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着 ( )
①数据元素具有同一特点
②不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致
③每个数据元素都一样
④数据元素所包含的数据项的个数要相等
四、简答及应用
1数据与数据元素有何区别？
2·为什么说数据元素之间的逻辑关系是数据内部组织的主要方面?
3·逻辑结构与存储结构是什么关系?
4·运算与运算的实现是什么关系?有哪些相同点和不同点？
5，类C语言与标准C语言的主要区别是什么?
五、算法设计
1、设计求解下列问题的类C语言算法，并分析其最坏情况时间复杂性及其量级。
（1）在数组A[1..n]中查找值为K的元素,若找到则输出其位置i(1<=i<=n),否则输出0作为标志。
（2）找出数组A[1..n]中元素的最大值和次最大值（本小题以数组元素的比较为标准操作）。
第一章参考答案
一、名词解释（略）
二、填空题
1、数据表示数据处理
2、机内表示
3、逻辑结构逻辑结构上的基本运算存储结构和运算评价和选择
4、逻辑性基本运算
5、存储
6、机外表示逻辑结构存储结构
7、处理要求基本运算和运算算法
8、数据数据元素数据项
9、元素结点顶点记录
10、字段域 11、数据元素数据项
12、集合线性结构树形结构图状结构
13、加工引用 14、定义在S上的运算 S上运算
15、归纳 16、机内表示
17、存储结点数据元素之间关联方式的表示附加设施
18、顺序存储方式链式存储方式索引存储方式散列存储方式
19、给定逻辑结构S的存储实现存储映象
20、程序算法设计
21、运行终止的程序可执行部分伪语言算法非形式算法
22、时空性能算法分析 23、正确性能易读性健壮性高效性
24、时间性能（或时间效率）空间性能（或空间效率）计算量存储量
25、标准操作标准操作计算量
26、最坏情况时间复杂性最坏情况时间复杂度平均时间复杂性平均时间复杂度
27、时间复杂性时间复杂度 28、算法输入规模
29、作为该算法输入的数据所含数据元素的数目，或与此数目有关的其他参数
n n n2 2n实际不可计算高效
30、1 log
2
31、设计实现
32、数据结构的定义数据结构的实现数据结构的评价选择
33、数据的逻辑结构 34、线性结构非线性结构
n)。
34、O（n2） 36、o(log
2
三、单项选择题
1.②
2.①
3.②
4.③
5.①
6.②
7.④
8.③
9.③
10.③ 11.② 12.② 13.④ 14.④ 15.②
四、简答及应用
1．凡能被计算机存储、加工的对象通称为数据。
数据元素是数据的基本单位，在程序中作为一个整体而加以考虑和处理。换句话说，数据元素被当作运算的基本单位，并且通常具有完整确定的实际意义。根据需要，数据
元素又被称为元素、结点、顶点或记录。
在很多情况下，数据元素又是由数据项组成的，但数据项通常不肯有完整确定的实际意义，或不被当作一个整体对待。在有些场合下，数据项又称为字段或域。它是数据的不可分割的最小标识单位。
从某种意义上说，数据，数据元素和数据实际反映了数据组织的三个层次，数据可由若干个数据元素构成，而数据元素又可由若干个数据项构成。
２、所谓逻辑关系是指数据元素之间的关联方式或称“邻接关系”。数据元素之间逻辑关系的整体称为逻辑结构。数据的逻辑结构就是数据的组织形式。关于逻辑结构的以下几点需特别注意：
（１）、逻辑结构与数据元素本身的形成、内容无关。
（２）、逻辑结构与数据元素的相对位置无关。
（３）、逻辑结构与所含结点个数无关。
由此可见，一些表面上很不相同的数据可以有相同的逻辑结构，因此，逻辑结构是数据组织的某种“本质性”的东西，是数据内部组织的主要方面。
３、逻辑结构反映数据元素之间的逻辑关系，而存储结构是数据结构在计算机中的表示，它包括数据元素的表示及其关系的表示。
４、一般地，运算是指在任何逻辑结构上施加的操作，即对逻辑结构的加工。一个运算的实现是指一个完成该运算功能的程序。
相同点：运算与运算的实现都能完成对数据的“处理”或某种特定的操作。
不同点：运算只描述处理功能，不包括处理步骤和方法，而运算实现的核心是处理步骤。
５、类Ｃ语言基本上是标准Ｃ语言的简化。类Ｃ语言与标准Ｃ语言的主要区别如下：
（１）局部量的说明可以省略（但形参表中及函数类型的说明需保留），重要的变量需在注解中用文字说明基类型和作用。
（２）分情形语句可以采用下述形式：
switch
{ case 条件１：语句序列１；break;
case 条件2：语句序列2；break;
……
case 条件n：语句序列n；break;
default: 语句序列n+1;
}
其中“default: 语句序列n+1;”可以省略。
（３）不含goto语句，增加了一个出错处理语句error（字符串），其功能是终止它所在算法的执行并回送表示出错信息的字符串。
（４）输入输出语句有：
输入语句 scanf([格式串]，变量度，……，变量n);
输出语句 printf([格式串]，变量度，……，变量n);
(５) 类Ｃ语言的形参书写比标准Ｃ语言简单，如int abc (int a,int b,int c)可以简写为 int abc(int a,b,c)。
五．算法设计
１．（１）int locate(dataytpe A[1..n],dateytpe k)
{ i=n;
while ((I<=n)&&(A[i]!=k)) I++;
if (I<=n) return(i);
else return(o);
}
当查找不成功时，总是比较n+1次，所以，最坏时间复杂性为n+1。其量
T（n）=O(n).
（２）Void CZ_max(datatype A[n],x,y)
{ x=A[1]; y=A[1];
for(I=2;I<=n;I++)
if(x else if(y } 若经条件判断语句为标准操作，则最坏情况时间复杂性为n-1。其量级为 T(n)=O(n). 第二章线性表 一．名词解释 1.线性结构 2.数据结构的顺序实现 3.顺序表 4.链表 5.数据结构的链接实现 6. 建表 7.字符串 8.串 9.顺序串 10.链串 二、填空题 1.为了便于讨论，有时将含n(n>=0)个结点的线性结构表示成(a 1，a 2 ,……a n )，其中每个a i 代表一个______。a 1 称为______结点，a n 称为______结点，i称为a i 在线性表中的________或______。对任意一对相邻结点a i 、a i┼1 (1<=i i 称为a i┼1的直接______a i┼1 称为a i 的直接______。 2.为了满足运算的封闭性，通常允许一种逻辑结构出现不含任何结点的情况。不含任何结点的线性结构记为______或______。 3.线性结构的基本特征是:若至少含有一个结点，则除起始结点没有直接______外，其他结点有且仅有一个直接______;除终端结点没有直接______外，其它结点有且仅有一个直接______. 4.所有结点按1对1的邻接关系构成的整体就是______结构。 5.线性表的逻辑结构是______结构。其所含结点的个数称为线性表的______，简称______. 6.表长为O的线性表称为______ 7.线性表典型的基本运算包括:______、______、______、______、______、______等六种。 8.顺序表的特点是______。 9.顺序表的类型定义可经编译转换为机器级。假定每个datatype类型的变量占用k(k>=1)个内存单元，其中，b 是顺序表的第一个存储结点的第一个单元的内存地址，那么，第i个结点a i 的存储地址为______。 10.以下为顺序表的插入运算，分析算法，请在______处填上正确的语句。 Void insert_sqlist(sqlist L，datatype x，int i) /*将X插入到顺序表L的第i-1个位置*/ { if( https://www.wendangku.net/doc/6016392801.html,st == maxsize) error(“表满”)； if((i<1)||(i>https://www.wendangku.net/doc/6016392801.html,st+1))error(“非法位置”); for(j=https://www.wendangku.net/doc/6016392801.html,st;j>=i;j--)______; L.data[i-1]=x; https://www.wendangku.net/doc/6016392801.html,st=https://www.wendangku.net/doc/6016392801.html,st+1; } 11.对于顺序表的插入算法insert_sqlist来说，若以结点移动为标准操作，则插入算法的最坏时间复杂性为________，量级是________。插入算法的平均时间复杂性为________，平均时间复杂性量级是________。 12.以下为顺序表的删除运算，分析算法，请在________处填上正确的语句。 void delete_sqlist(sqlist L,int i) /*删除顺序表L中的第i-1个位置上的结点*/ {if((i<1)||(i>https://www.wendangku.net/doc/6016392801.html,st))error(“非法位置”)； for(j=i+1;j=https://www.wendangku.net/doc/6016392801.html,st;j++)________; https://www.wendangku.net/doc/6016392801.html,st=https://www.wendangku.net/doc/6016392801.html,st-1; } 13.对于顺序表的删除算法delete_sqlist来说，若以结点移动为标准操作，最坏情况时间复杂性及其量级分别是________和________,其平均时间复杂性及其量级分别为________和________。 14.以下为顺序表的定位运算，分析算法，请在________处填上正确的语句。 int locate_sqlist(sqlist L,datatype X) /*在顺序表L中查找第一值等于X的结点。若找到回传该结点序号；否则回传0*/ {________; while((i≤https://www.wendangku.net/doc/6016392801.html,st)&&(L.data[i-1]!=X))i++; if(________)return(i); else return(0); } 15.对于顺序表的定位算法，若以取结点值与参数X的比较为标准操作，平均时间复杂性量级为________。求表长和读表元算法的时间复杂性为________。 16.在顺序表上，求表长运算LENGTH（L）可通过输出________实现，读表元运算 GET（L，i）可通过输出________实现。 17.线性表的常见链式存储结构有________、________和________。 18.单链表表示法的基本思想是用________表示结点间的逻辑关系。 19.所有结点通过指针的链接而组织成________。 20.为了便于实现各种运算，通常在单链表的第一个结点之前增设一个类型相同的结点，称为________，其它结点称为________。 21.在单链表中，表结点中的第一个和最后一个分别称为________和________。头结点的数据域可以不存储________，也可以存放一个________或________。 22.单链表INITIATE（L）的功能是建立一个空表。空表由一个________和一个________组成。 23.INITIATE()的功能是建立一个空表。请在________处填上正确的语句。 lklist initiate_lklist() /*建立一个空表*/ {________________; ________________; return(t); } 24.以下为求单链表表长的运算，分析算法，请在 ________处填上正确的语句。 int length_lklist(lklist head) /*求表head的长度*/ {________; j=0; while(p->next!=NULL) {________________; j++; } return(j); /*回传表长*/ } 25.以下为单链表按序号查找的运算，分析算法，请在____处填上正确的语句。 pointer find_lklist(lklist head,int i) { p=head;j=0; while(________________) { p=p->next; j++; } if(i==j) return(p); else return(NULL); } 26.以下为单链表的定位运算，分析算法，请在____处填上正确的语句。 int locate_lklist(lklist head,datatype x) /*求表head中第一个值等于x的结点的序号。不存在这种结点时结果为0*/ { p=head;j=0; while(________________________________){p=p->next;j++;} if (p->data==x) return(j); else return(0); } 27.以下为单链表的删除运算，分析算法，请在____处填上正确的语句。 void delete_lklist(lklist head,int i) { p=find_lklist(head,i-1); if(____________________________) { q=________________; p->next=p->next; free(q); } else error(“不存在第i个结点”) } 28.以下为单链表的插入运算，分析算法，请在____处填上正确的语句。 void insert_lklist(lklist head,datatype x,int i) /*在表head的第i个位置上插入一个以x为值的新结点*/ { p=find_lklist(head,i-1); if(p==NULL)error(“不存在第i个位置”)； else {s=________________;s->data=x; s->next=________________; p->next=s; } } 29.以下为单链表的建表算法，分析算法，请在____处填上正确的语句。 lklist create_lklist1() /*通过调用initiate_lklist和insert_lklist算法实现的建表算法。假定$是结束标志*/ { ininiate_lklist(head); i=1; scanf(“%f”,&x); while(x!=?$?) {________________; ________________; scanf(“%f”,&x); } return(head); } 该建表算法的时间复杂性约等于____________，其量级为____________。 30.以下为单链表的建表算法，分析算法，请在____处填上正确的语句。 lklist create_lklist2() /*直接实现的建表算法。*/ { head=malloc(size); p=head; scanf(“%f”,&x); while(x!=?$?) { q=malloc(size); q->data=x; p->next=q; ________________; scanf(“%f”,&x); } ________________; return(head); } 此算法的量级为________________。 31．除单链表之外，线性表的链式存储结构还有_________和_________等。 32．循环链表与单链表的区别仅仅在于其尾结点的链域值不是_________，而是一个指向_________的指针。 33．在单链表中若在每个结点中增加一个指针域,所含指针指向前驱结点，这样构成的链表中有两个方向不同的链，称为______。 34．C语言规定，字符串常量按______处理，它的值在程序的执行过程中是不能改变的。而串变量与其他变量不一样，不能由______语句对其赋值。 35．含零个字符的串称为______串，用______表示。其他串称为______串。任何串中所含______的个数称为该串的长度。 36．当且仅当两个串的______相等并且各个对应位置上的字符都______时，这两个串相等。一个串中任意个连续字符组成的序列称为该串的______串，该串称为它所有子串的______串。 37．串的顺序存储有两种方法：一种是每个单元只存一个字符，称为______格式，另一种是每个单元存放多个字符，称为______格式。 38．通常将链串中每个存储结点所存储的字符个数称为______。当结点大小大于1时，链串的最后一个结点的各个数据域不一定总能全被字符占满，此时，应在这些未用的数据域里补上______。 三、单向选择题 1．对于线性表基本运算，以下结果是正确的是 ( ) ①初始化INITIATE(L)，引用型运算，其作用是建立一个空表L=Ф . ②求表长LENGTH(L)，引用型运算，其结果是线性表L的长度 ③读表元GET(L,i), 引用型运算。若1<=i<=LENGTH(L),其结果是线性表L的第i个结点； 否则，结果为0 ④定位LOCATE(L,X), 引用型运算.若L中存在一个或多个值与X相等的结点，运算结果为这些结点的序号的最大值；否则运算结果为0 ⑤插入INSERT(L,X,i),加工型运算。其作用是在线性表L的第i+1个位置上增加一个以X为值的新结点 ⑥删除DELETE(L,i), 引用型运算.其作用是撤销线性表L的第i个结点Ai 2.线性结构中的一个结点代表一个（） ①数据元素②数据项③数据④数据结构 3．顺序表的一个存储结点仅仅存储线性表的一个（） ①数据元素②数据项③数据④数据结构 4．顺序表是线性表的（） ①链式存储结构②顺序存储结构③索引存储结构④散列存储结构 5.对于顺序表，以下说法错误的是（） ①顺序表是用一维数组实现的线性表，数组的下标可以看成是元素的绝对地址 ②顺序表的所有存储结点按相应数据元素间的逻辑关系决定的次序依次排列 ③顺序表的特点是:逻辑结构中相邻的结点在存储结构中仍相邻 ④顺序表的特点是:逻辑上相邻的元素，存储在物理位置也相邻的单元中 6.对顺序表上的插入、删除算法的时间复杂性分析来说，通常以（）为标准操作 ①条件判断②结点移动 ③算术表达式④赋值语句 7.对于顺序表的优缺点，以下说法错误的是（） ①无需为表示结点间的逻辑关系而增加额外的存储空间 ②可以方便地随机存取表中的任一结点 ③插人和删除运算较方便 ④由于顺序表要求占用连续的空间，存储分配只能预先进行(静态分配) ⑤容易造成一部分空间长期闲置而得不到充分利用 8.指针的全部作用就是（） ①指向某常量②指向某变量 ③指向某结点④存储某数据 9.除了( ) ，其它任何指针都不能在算法中作为常量出现，也无法显示。 ①头指针②尾指针 ③指针型变量④空指针 10.单链表表示法的基本思想是指针P表示结点间的逻辑关系，则以下说法错误的是（） ①任何指针都不能用打印语句输出一个指针型变量的值 ②如果要引用(如访问)p所指结点，只需写出p(以后跟域名)即可 ③若想修改变量p的值(比如让P指向另一个结点)，则应直接对p赋值 ④对于一个指针型变量P的值。只需知道它指的是哪个结点 ⑤结点*ｐ是由两个域组成的记录，p->data是一个数据元素，p->next的值是一个指针 11.单链表的一个存储结点包含（） ①数据域或指针域 ②指针域或链域 ③指针域和链域 ④数据域和链域 12.对于单链表表示法，以下说法错误的是（） ①数据域用于存储线性表的一个数据元素 ②指针域或链域用于存放一个指向本结点所含数据元素的直接后继所在结点的指针 ③所有数据通过指针的链接而组织成单链表 ④NULL称为空指针，它不指向任何结点，只起标志作用 13.对于单链表表示法，以下说法错误的是（） ①指向链表的第一个结点的指针，称为头指针 ②单链表的每一个结点都被一个指针所指 ③任何结点只能通过指向它的指针才能引用 ④终端结点的指针域就为NULL ⑤尾指针变量具标识单链表的作用，故常用尾指针变量来命名单链表 14．有时为了叙述方便，可以对一些概念进行简称，以下说法错误的是（） ①将“指针型变量”简称为“指针” ②将“头指针变量”称为“头指针” ③将“修改某指针型变量的值”称为“修改某指针” ④将“p中指针所指结点”称为“P值” 15．设指针P指向双链表的某一结点，则双链表结构的对称性可用（）式来刻画 ①p->prior->next->==p->next->next ②p->prior->prior->==p->next->prior ③p->prior->next->==p->next->prior ④p->next->next==p->prior->prior 16.以下说法错误的是（） ①对循环链表来说，从表中任一结点出发都能通过前后操作而扫描整个循环链表 ②对单链表来说，只有从头结点开始才能扫描表中全部结点 ③双链表的特点是找结点的前趋和后继都很容易 ④对双链表来说，结点*P的存储位置既存放在其前趋结点的后继指针域中，也存放在它的后继结点的前趋指针域中。17．在循环链表中，将头指针改设为尾指针（rear）后，其头结点和尾结点的存储位置分别是（） ①real和rear->next->next ②rear->next 和real ③rear->next->next和rear ④rear和rear->next 18.以下说错误的是 ( ) ①对于线性表来说，定位运算在顺序表和单链表上的量级均为O（n） ②读表元运算在顺序表上只需常数时间O（1）便可实现，因此顺序表是一种随机存取结构 ③在链表上实现读表元运算的平均时间复杂性为O（1） ④链入、摘除操作在链表上的实现可在O（1）时间内完成 ⑤链入、摘除操作在顺序表上的实现，平均时间复杂性为O（n） 19．在串的基本运算中，属于加工型运算的有（） ①EQAL(S,T) ②LENGTH(S) ③CONCAT(S,T) ④REPLACE(S,T,R) ⑤INDEX(S,T) 20. 在串的基本运算中，属于引用型运算的有（） ①ASSIGN(S,T) ②INSERT(S1,i,S2) ③DELETE(S,i,j) ④SUBSTR(S,i,j) ⑤REPLACE(S,T,R) 21．循环链表主要优点是（） ①不再需要头指针了 ②已知某个结点的位置后，能够容易找到它的直接前趋 ③在进行插入、删除运算时，能更好地保证链表不断开 ④从表中任一结点出发都能扫描到整个链表 22，每种数据结构都具备三个基本操作:插入、删除和查找，这种说法（） ①正确②错误 23．以下说法错误的是（） ①数据的物理结构是指数据在计算机内实际的存储形式 ②算法和程序没有区别，所以在数据结构中二者是通用的 ③对链表进行插人和删除操作时，不必移动结点 ④双链表中至多只有一个结点的后继指针为空 24．以下说法正确的是 ①线性结构的基本特征是：每个结点有且仅有一个直接前趋和一个直接后继 ②线性表的各种基本运算在顺序存储结构上的实现均比在链式存储结构上的实现效率要低 ③在线性表的顺序存储结构中，插人和删除元素时，移动元素的个数与该元素位置有关 ④顺序存储的线性表的插人和删除操作不需要付出很大的代价，因为平均每次操只有近一半的元素需要移动25．以下说法错误的是（） ①求表长、定位这二种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低 ②顺序存储的线性表可以随机存取 ③由于顺序存储要求连续的存储区域，所以在存储管理上不够灵活 ④线性表的链式存储结构优于顺序存储结构 26．以下说法错误的是（） ①线性表的元素可以是各种各样的，逻辑上相邻的元素在物理位置上不一定相邻 ②在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上不一定相邻 ③在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻 ④线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素 27．以下说法正确的是（） ①在单链表中，任何两个元素的存储位置之间都有固定的联系，因为可以从头结点进行查找任何一个元素 ②在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构 ③顺序存储结构属于静态结构，链式结构属于动态结构 ④顺序存储方式只能用于存储线性结构 28.以下说法正确的是（） ①顺序存储方式的优点是存储密度大、且插入、删除运算效率高 ②链表的每个结点中都恰好包含一个指针 ③线性表的顺序存储结构优于链式存储结构 ④顺序存储结构属于静态结构，链式结构属于动态结构 29.下面关于线性表的叙述正确的是( ) ①线性表采用顺序存储，必须占用一片连续的存储单元 ②线性表采用顺序存储，便于进行插人和删除操作 ③线性表采用链接存储，不必占用一片连续的存储单元 ④线性表采用链接存储，不便于插人和删除操作 30.线性表L=(a 1,a 2 ,...,a i ,...,a n ),下列说法正确的是( ) ①每个元素都有一个直接前驱和直接后继 ②线性表中至少要有一个元素 ③表中诸元素的排列顺序必须是由小到大或由大到小的 ④除第一个元素和最后一个元素外其余每个元素都有一个且仅有一个直接前驱和直接后继 31.线性表的逻辑顺序与存储顺序总是一致的，这种说法( ) ①正确②不正确 32.设p,q是指针,若p=q,则*p=*q ,这种说法( ) ①正确②不正确 33.线性表若采用链表存储结构时，要求内存中可用存储单元的地址( ) ①必需是联系的②部分地址必须是连续的 ③一定是不连续的④连续不连续都可以 34.设REAR是指向非空带头结点的循环单链表的尾指针,则删除表首结点的操作可表示为( ) ①p=rear; ②rear=rear->next; rear=rear->next; free(rear); free(p) ③rear=rear->next->next; ④ p=rear->next->next; free(rear); rear->next->next=p->next; free(p); 35. 单链表中，增加头结点的目的是为了 ( ) ①使单链表至少有一个结点②标示表结点中首结点的位置 ③方便运算的实现④说明单链表是线性表的链式存储实现 36线性结构中的一个结点代表一个数据元素，通常要求同一线性结构的所有结点所代表的数据元素具有相同的特性，这意味着 ①每个结点所代表的数据元素都一样。 ②每个结点所代表的数据元素包含的数据项的个数要相等 ③不仅数据元素包含的数据项的个数要相同，而且对应数据项的类型要一致 ④结点所代表的数据元素有同一特点 37．带头结点的单链表Head为空的判定条件是 ①Head=Null ②Head->next=NULL ③Head->next=Head 38.非空的单循环链表L的尾结点*P,满足 P->next=NULL P=NULL P->next=L P=L. 39.双向链表结点结构如下： 其中：LLink data是存放数据元素的数据域； Rlink是指向后继结点的指针域。 下面给出的算法段是要把一个新结点*Q作为非空双向链表中的结点*p的前驱，插入到此双向链表中。不能正确完成要求的算法段是 ①Q->LLink=P->LLink; ②P->LLink=Q; Q->Rlink=P; Q->Rlink=P; P->LLink=Q; P->LLink->Rlink=Q; P->LLink->Rlink=Q; Q->LLink=P->LLink; ③Q->LLink=P->LLink; Q->Rlink=P; P->LLink->Rlink=Q; P->LLink=Q; 40.若某线性表中最常用的操作是取第i 个元素和找第i 个元素的前趋元素，则采用（ ）存储方式最节省时间。 ①顺序表 ②单链表 ③双链表 ④单循环链表 41．串是任意有限个 ①符号构成的集合 ②符号构成的序列 ③字符构成的集合 ④字符构成的序列 四、简答及应用 1． 请用类C 语言描述顺序表，并予以解释说明。 2． 请用类C 语言描述单链表的类型定义，并予以解释说明。 3． 请用类C 语言描述双链表的类型定义，并予以解释说明。 4． 请用类C 语言描述顺序串的类型定义。 5． 请用类C 语言描述链串的类型定义。 6.叙述以下概念的区别：头指针变量、头指针、头结点、首结点，并说明头指针变量和头结点的作用。 7．有哪些链表可仅由一个尾指针来惟一确定，即从尾指针出发能访问到链表上任何一个结点。 8．简述下列每对术语的区别： 空串和空格串;串变量和串常量;主串和子串;串变量的名字与串变量的值。 9．设有 A=” ”,B="mule"，C="old"，D="my",试计算下列运算的结果(注:A+B 是CONCAT （A,B ）的简写,A=" "的 " "含有两个空格)。 (a) A+B (b) B+A (c) D+C+B (d) SUBSTR(B,3,2) (e) SUBSTR(C,1,0) (f) LENGTH(A) (g) LENGTH(D) (h) INDEX(B,D) (i) INDEX(C,"d") (j) INSERT(D,2,C) (k) INSERT(B,1,A) (l) DELETE(B,2,2) (m) DELETE(B,2,0) 10.已知:S="(xyz)*",T="(x+z)*y"。试利用连接、求子串和置换等基本运算，将S 转换为T 。 五、算法设计 1． 设A=（a 1,a 2,a 3,......a n ）和B=(b 1,b 2,.. .,b m )是两个线性表（假定所含数据元素均为整数）。若n=m 且a i =b i (i=1,.. .,n),则称A=B;若a i =b i (i=1,.. .,j)且a j+1B 。是编写一个比较A 和B 的算法，当A 2，试编写在无头结点的单链表上实现线性表基本运算LOCATE(L,X)、INSERT(L,X ，i)和DELETE(L,i)的算法，并和在带头结点的单链表上实现相的算法进行比较。 3．试编写在不带头结点的单链表上实现线性表基本运算LENGTH(L)的算法。 4．假设有两个按数据元素值递增有序排列的线性表A 和B ，均以单链表作存储结构。编写算法将A 表和B 表归并成一个按元素值递减有序（即非递增有序，允许值相同）排列的线性表C ，并要求利用原表(即A 表和B 表的)结点空间存放表C 。 5．设有线性表A=(a 1,a 2,.. .,a m )和B=(b 1,b 2,.. .,b n ).试写合并A 、B 为线性表C 的算法，使得： C=? ??>+<=+n;m )am ,...,1an ,bn ,an ,...,1b ,1a (;n m )bn ,1bm ,bm ,am ,...,1b ,1a (当当 假设A 、B 均以单链表为存储结构(并且m 、n 显示保存)。要求C 也以单链表为存储结构并利用单链表A 、B 的结点空间。 6，设线性表存放在向量A[arrsize]的前elenum 分量中，且递增有序。试写一算法，将X 插入到线性表的适当位置上， 以保持线性表的有序性，并且分析算法的时间复杂性。 7．已知单链表L中的结点是按值非递减有序排列的，试写一算法将值为x的结点插入表L中，使得L仍然有序。 8，试分别以顺序表和单链表作存储结构，各写一个实现线性表的就地(即使用尽可能少的附加空间)逆置的算法，在原 表的存储空间内将线性表(a 1，a 2 ,.. .,a n )逆置为(a n ,.. .,a 2 ,a 1 )。 9．假设分别以两个元素值递增有序的线性表A、B表示两个集合(即同一线性表中的元素各不相同)，现要求构成一个新的线性表C，C表示集合A与B的交，且C中元素也递增有序。试分别以顺序表和单链表为存储结构，填写实现上述运算的算法。 10，已知A、B和C为三个元素值递增有序的线性表，现要求对表A作如下运算：删去那些既在表B中出现又在表C 中出现的元素。试分别以两种存储结构(一处种顺序结构，一种链式的)编写实现上述运算的算法。 11．假设在长度大于1的循环链表中，既无头结点也无头指针。s为指向链表中某个结点的指针，试编写算法删除结点*s的前趋结点。 12．已知一单链表中的数据元素含有三个字符(即:字母字符、数字字符和其它字符)。试编写算法，构造三个循环链表，使每个循环链表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间(头结点可另辟空间)。 13.(Josephus环)任给正整数n、k，按下述方法可得排列1，2，……,n的一个置换:将数字1，2，.. .,n环形排列(如图算法设计题13.所示)，按顺时针方向从1开始计数；计满K时输出该为之上的数字(并从环中删去该数字)，然后从下一个数字开始继续计数，直到环中所有数字均被输出为止。例如，n=10,k=3时，输出的置换是3，6，9，2，7，1， 8，5，10， 4。试编写一算法，对输人的任意正整数n、k，输出相应的置换 14·在双链表上实现线性表的下列基本运算(a)初始化； (b)定位(c)插入(d)删除。 15·设有一双链表，每个结点中除有prior、data和next三个域外，还有一个访问频度域freq，在链表被起用之前，其值均初始化为零。每当在双链表上进行一次LOCATEL，X)运算时，令元素值为X的结点中freq域的值增1，并使此链表中结点保持按访问频度递减的顺序排列，以便使频繁访问的结点总是靠近表头。试编写实现符合上述要求的LOCATE 运算的算法。 16·若X和Y是用结点大小为1单链表表示的串，设计一个算法找出X中第一个不在y中出现的字符。 17．在顺序串上实现串的判等运算EQUAL(S,T)。 18．在链串上实现判等运算EQUAL(S,T)。 19．若S和T是用结点大小为1的单链表存储的两个串（S、T为头指针），设计一个算法将串S中首次与串T匹配的子串逆值。 20．用串的其他运算构造串的子串定位运算index。 第二章参考答案 一、名词解释（略） 二、填空题 1、结点起始终端序号位置前趋后趋 2、（）ф 3、前趋前趋后趋后趋 4、线性 5、线性长度表长 6、空表 7、初始化INITLATE（L）求表长LENGTH（L）读表长GET（L，i）定位LOCATE （L，X）插入INSERT（L，X，i）删除DELETE（L，i） 8、逻辑结构中相邻的结点在存储结构中仍相邻 9、b+（i-1）x k 10、L．data[j]=L．data[j-1] 11、n O(n) n/2 O(n) 12、L.data[j-2]=l.data[j-1] 13、n-1 o(n) (n-1)/2 O(n) 14、i=1 i≦https://www.wendangku.net/doc/6016392801.html,st 15、O(n) O(1) 16、https://www.wendangku.net/doc/6016392801.html,st L.data[i-1] 17、单链表循环链表双链表 18、指针 19，单链表 20、头结点表结点 21、首结点尾结点任何信息、特殊标志表长 22、头结点头结点 23、t=malloc(size) t->next=NULL 24、p=haed p=p->next 25、(p->next!=NULL)&&(j 26、(p->next!=NULL)&&(p->data!=x) 27、(p!=NULL)&&(p->next!=NULL) p->next 28、mailloc(size) p->next 29、insert_lklist(head,x,I) I++ n(n-1)/2 O(n2) 30、p=q p->next=NULL O(n) 31、单向循环链表（简称循环链表）双向循环链表（简称双链表） 32、NULL 头结点 33、双链表 34、字符数组赋值 35、空ф非空字符 36、长度相同子主 37、非紧缩紧缩 38、结点大小不属于字符集的特殊符号 三、单项选择题 1、② 2、① 3、① 4、② 5、① 6、② 7、③ 8、③ 9、④ 10、②11、④12、③13、⑤14、④15、③16、①17、②18、③ 19、④20、④21、④22、223、②24、③25、④26、②27、③ 28、④29、①30、④31、②32、②33、④34、④35、③36、③ 37、②38、③39、②40、①41、④ 四、简答及应用 1、线性表的数据元素的类型为datatype，则在语言上可用下述类型定义来描述顺序表： const maxsize=顺序表的容量； typedef struct { datatype data[maxsize] int last; }sqlist; sqlist L; 数据域data是一个一维数组，线性表的第1，2……，n个元素分别存放在此数组的第0，1，……，last-1个分量中，数据域last表示线性表当前的长度，而last-1是线性表的终端结点在顺序表中的位置。常数maxsize称为顺序表的容量，从last到maxsize-1为顺序表当前的空闲区（或称备用区）。 Sqlist类型完整地描述了顺序表的组织。L被说明为sqlist类型的变量，即为一顺序表，其表长应写为https://www.wendangku.net/doc/6016392801.html,st，而它的终端结点则必须写为 L.data[https://www.wendangku.net/doc/6016392801.html,st-1]。 2、假设数据元素的类型为datatype。单链表的类型定义如下： typedef struct node *pointer struct node {datatype data; pointer next; }; typedef pointer lklist; 其中，①ponter是指向struct node类型变量的指针类型;②struct node是结构体类型规定一个结点是由两个域data和next组成的记录，其中data的结点的数据域,next是结点的链域；③lklist与pointer相同类型，用来说明头指针变量的类型，因而lklist也就被用来作为单链表的类型。 3、typedef struct dnode *dpointer; struct dnode {datatype data; dpointer prior,next; } typedaf dpinter dlklist; 链域prior和next分别指向本结点数据域data所含数据元素的直接前趋和直接后继所在的结点。所有结点通过前趋和后继指针链接在一起，再加上起标识作用的头指针，就得到双向循环链表。 4、顺序串的类型定义与顺序表类似，可描述如下： const maxlen=串的最大长度 typedef struct {char ch[maxlen] int curlen; }string 5、链串的类型定义为： const nodesize=用户定义的结点大小; typedef struct node *pointer; struct node {char ch[nodesize] poinernext; } typedef pointer strlist; 当结点大小为1时，可将ch域简单地定义为：char ch 6、head称为头指针变量，该变量的值是指向链表的第一个结点的指针，称为头指针。头指针变量是用于存放头指针的变量。 为了便于实现各种运算，通常在单链表的第一个结点之前增设一个类型相同的结点，称为头结点。其它结点称为表结点。表结点中和第一个和最后一个分别称为首结点和尾结点。 头指针变量的作用：对单链表中任一结点的访问，必须首先根据头指针变量中存放的头指针找到第一个结点，再依次按各结点链域存放的指针顺序往下找，直到找到或找不到。头指针变量具有标识单链表的作用，故常用头指针变量为命名单链表。 头结点的作用：头结点的数据域可以不存储任何信息，也可以存放一个特殊标志或表长。其作用是为了对链表进行操作时，将对第一个结点煌处理和对其它结点的处理统一起来。 7、循环单链表、循环双链表。 8、空串和空格串：含0个字符的串称为空串，其长度为0。空格串是含有一个或多处空格字符组成的串，其长度不为0。 串变量和串常量：串常量在程序的执行过程中只能引用不能改变而串变量的值在程序执行过程中是可以改变和重新赋值的。 主串和子串：一个串中任意个连续字符组成的子序列称为该串的子串，该串称为它的所以子串的主串。 串变量的名字与串变量的值：串变量的名字表示串的标识符；串变量的值表示串变量的字符序列。 9、(a)A+B “ mule” (b)B+A “mule ” (c)D+C+B “myoldmule” (d)SUBSTR(B,3,2) “le” (e)SUBSTR(C,1,0) “” (f)LENGTH(A) 2 (g)LENGTH(D) 2 (h)INDEX(B,D) 0 (i)INDEX(C,”d”) 3 (j)INSERT(D,2,C) “myold” (k)INSERT(B,1,A) “m ule” (l)DELETE(B,2,2) “me” (m)DELETE(B,2,0) “mule” 10、REPLACE(S,SUBSTR(T,7,1),SUBSTR(T,3,1));CONCAT(S,”y”); 五、算法设计 1、分析：(1)当A、B表都不为空时，比较A，B表中各元素对应位置的内容的大小，进而判断A，B的大小。 (2)当A，B表都不为空时，且A，B表中各各元素对应位置的内容相同时，比较A，B的长度，进而判断 A，B的大小或是否相等。 const maxsize=顺序表的容量; typedef struct {int data[maxsize] int last; }sqlist; int CMP_sqlist(sqlist A ,sqlist B) { for (i=0;(i { if(A.data[i] if(A.data[i]>B.data[i])return(1); } if(https://www.wendangku.net/doc/6016392801.html,st= =https://www.wendangku.net/doc/6016392801.html,st) return(0); else if(https://www.wendangku.net/doc/6016392801.html,st>https://www.wendangku.net/doc/6016392801.html,st) return(1); else return(-1); } 2、(1)定位LOCATE(L，X) 在带头结点类单链表上实现的算法为： int locate_lklist(lklist head,datatype x) /*求表head中第一个值等于x的的序号，不存在这种结点时结果为0*/ {p=head->next;j=1; /*置初值*/ while((p!=NULL)&&(p->data!=x)) {p=p->next;j++}/*未达表结点又未找到值等于X的结点时经，继续扫描*/ if (p->data = =x) return(j); else return(0); } 在无头结点的单链表上实现的算法为： int Wlocate(lklist head,datatype X) /*求表head中第一个值等于x的结点的序号。不存在这种结点时结果为0*/ {p=head; j=1; /*置初值*/ while((p!=NULL)&&(p->data!=x)) {p=p->next;j++}/*未达表结点又未找到值等于X的结点时经，继续扫描*/ if( p->data = =X) return(j); else return(0); } (2)按序号查找find(L,i) 在带头结点的单链表上实现的算法为： pointer find_lklist(lklist head , int i); { j=1; p=head->next; while((j<1)&&(p!=NULL)){p=p->next; j++} if(i= = j) return(p); else return(NULL); } 在无头结点的单链表上实现的算法为： pointer find_lklist(lklist head , int i); { j=1; p=head; while((j<1)&&(p!=NULL)){p=p->next; j++} if(i= = j) return(p); else return(NULL); } (3)、插入INSERT(L，X，i) 在带头结点单链表上实现的算法为： void insert_lklist(lklist head,datatype x,int I) /*在表haed的第i个位置上插入一人以x为值的新结点*/ {p=find_lklist(head,i-1); /*先找第i-1个结点*/ if(p= =NULL)reeor(“不存在第i个位置”)/*若第i-1个结点不存在，退出*/ else{s=malloc(size);s->data=x /*否则生成新结点*/ s->next=p->next /*结点*p在链域值传给结点*s的链域*/ p->next=s; /*修改*p的链域*/ } } 在无头结点的单链表上实现的算法为： void Winsert(lklist head,dataytpe X,int i) /*在表haed的第i个位置上插入一人以x为值的新结点*/ {if(i<=0) error(“i<=0”); else{ s=malloc(size);s->data=X; /*否则生成新结点*/ if(i= =1){s->next=head;head=s;} else{ p=wfind_lklist(lklist head,i-1); if(p= =NULL) error(“i>n+1”); else{s->next=p->next;p->next=s;} } } (4)删除DELDTE(L,i) 在带头结点的单链表上实现的算法为： void delete_lklist(lklist head,int i) /*删除表head的第i个结点*/ {p=find_lklist(head,i-1) /*先找待删结点的直接前驱*/ if((p!==NULL)&&(p->next!=NULL))/*若直接前趋存在且待结点存在*/ (q=p->next; /*q指向待删结点*/ p->next=q->next/*摘除待结点*/; free(q);/*释放已摘除结点q*/ } else error(“不存在第i个结点”)/*否则给出相关信息*/ } 在无头结点的单链表上实现的算法为： void Wdelete(lklist head,int i) /* 删除表head的第i个结点，若该链表仅有一个结点时，赋该结点指针NULL*/ {if(i<=0) error(“I＜＝0” else{if(i= =0){q=head;head=head->next;free(q);} else{p=wfind_lklist(head,i-1);/*找链表head中第i-1结点指针*/ if(p!=NULL)&&(p->next!=NULL) ｛q=p->next; p->next=q->next; free(q);｝ else error(“不存在第I个结点”)； ｝ ｝ ｝ 3、分析：从第一个结点开始访问，只要是非空计数一次。 Int wlength_lklist(lklist head) /*求表head的长度*/ {p=head;j=0; while(p!=NULL){p=p->next;j++;} return(j); /*回传表长*/ ｝ 4、设A,B,C均为无头结点单链表 分析：（1）当有序表A，B均非空时，找出两表中元素最小的一个元素，然后将此结点插入到C表中，重复上述步骤。 （2）当A，B两表有一个为空表时，将另一表中元素顺序地插入到C表中。 （3）由于C按递减排序，因此在C表中插入元素时，应始终插入到C表表头。 Lklist Wlink_lklist(lklist A,lklist B) { while((A!=NULL)&&(B!=NULL)) if(A->data else p->next=C;C=p; } if(A= =NULL) A=B; while(A!=NULL) {p=A;A=A->next; p->next=C;C=p;} return(C); } 5、分析：（1）当有序表A、B均非空时，依次分别从A、B表头部取下结点，插入C表中。 （2）当A、B两表有一个为空表时，将非空表插入到C表尾部。 设A，B，C均为带头结点的单链表 lklist HB_lklist(lklist A,lklist B) { C=A; A=A->next;B=B->next; //去除头结点 While((A!=NULL)&&(B!=NULL)) {p->next=A;p=p->next;A=A->next; p->next=B;p=p->next;B=B->next; } if((B= =NULL)&&(A!=NULL)) p->next=A; else if((A= =NULL)&&(B!=NULL)) p->next=B; Return(c); } 6、分析：从有序表的尾部开始依次取元素与插入元素比较，若大于插入元素，此元素后移一位，再取它前面一个元素 重复上述步骤；则将待插入元素插入。 Void CR(datatype A[],datatype X,int elenum) { i=elenum-1; while((i>=0)&&X A[i+1]=X; Elenum=elenum+1; } 算法的时间复杂度为O（n）。 7、分析首先从表头开始查找待插入位置的直接前趋，找到后插入待插结点。 /*设L表带头结点*/ Void CR_lklist(lklist L,datatype x) {q=L;p=q->next; while((p!=NULL)&&(p->data s=malloc(size);s->data=s; } 8、(1)顺序表 分析：将顺序表的第一个元素与最后一个元素互换，第二个元素与倒数第二个元素互换。 Void NZ_sqlist(sqlist A) {for{i=0;i<((https://www.wendangku.net/doc/6016392801.html,st-1)/2);i++} {x=A.data[i]; A.data[i]=A.data[https://www.wendangku.net/doc/6016392801.html,st-i-1]; A.data[https://www.wendangku.net/doc/6016392801.html,st-i-1]=x; } } (2)单链表 分析：将原单链表的元素依次取出，再插入另一个单链表的头部。 设该单链表为无头结点，s为指向表的第一个结点的指针。 Void NZ_lklist(lklist s) {p=NULL; /*p指向当前结点的前趋结点*/ while(s!=NULL) { q=s;s=s->next; /*将原单链表的元素依次取出到q*/ q->next=p;p=q; /*再插入另一个单链表p的头部*/ } s=p; /*s指向新单链表的第一个结点*/ } 9、分析：A与B的交是指A与B的相同部分元素，即那些在A中出现又在B中出现的元素。由于A、B是有序表，故 从表头开始依次比较当前指针所指元素的值是否相同，若相同，在C表中插入该元素，然后将两个表的指针后移，否则指向较小元素的指针后移。重复上述步骤，直到A，B表中有一个表到表尾。 (1)顺序表 sqlist HDZ_sqlist(sqlist A,sqlist B) { t=0;j=0;k=0; while((t<=https://www.wendangku.net/doc/6016392801.html,st-1)&&(j<=https://www.wendangku.net/doc/6016392801.html,st-1)) 第2章线性表习题解答 第2章习题 (2) 第2章习题 2.1若将顺序表中记录其长度的分量listlen改为指向最后一个元素的位置last，在实现各基本运算时需要做那些修改？ 【解】 //用线性表最后一个元素的下标last代替listLen实现顺序表 #define MAXLEN 100 typedef int elementType; typedef struct sllLast { elementType data[MAXLEN]; int last; }seqList; //初始化 void initialList(seqList &S) { https://www.wendangku.net/doc/6016392801.html,st=-1; } //求表长度 int listLength(seqList S) { return https://www.wendangku.net/doc/6016392801.html,st+1; } //按序号取元素 bool getElement(seqList S,int i,elementType &x) { if(i<1 || i>https://www.wendangku.net/doc/6016392801.html,st+1) //i为元素编号，有效范围在https://www.wendangku.net/doc/6016392801.html,st+1之间 return false; else { x=S.data[i-1]; return true; } } //查找元素x，成功：返回元素编号；失败：返回0 int listLocate(seqList S,elementType x) { int i; for(i=0;i<=https://www.wendangku.net/doc/6016392801.html,st;i++) { if(S.data[i]==x) return i+1; //找到，转换为元素编号输出 } return 0; } //插入元素 int listInsert(seqList &S,elementType x, int i) 城市地理学复习资料 第一章绪论 1、城市地理学的研究对象及其研究的主要内容 （1）研究对象：城市地理学是研究在不同地理环境下，城市形成发展、组合分布和空间结构变化规律的科学。（城市空间组织的规律性） （2）主要研究内容：①城市的形成发展条件； ②区域的城市空间组织：城市化、区域城市体系、城市分类； ③城市内部空间组织：城市功能分区、城市土地利用、市场空间、社会空 间和感应空间等；④城市问题和城市可持续发展：城市环境、城市交通、 城市住宅、城市贫困；⑤新方法、新技术和新领域。 第二章城乡划分和城市地域 2、城市的概念及本质特征 城市是有一定人口规模、以非农业人口为主的居民集居地，是非农产业的核心空间载体及一定区域的政治、经济、文化活动中心，是聚落的一种特殊形态。其本质特征是密集性、中心性、系统性、高效性、多元性。 3、界定城镇的规范（城镇与乡村的基本差别） ①以从事非农业活动为主，在职业构成上不同于乡村； ②人口聚居规模大于乡村，在规模上区别于乡村； ③人口密度和建筑密度高于乡村，在景观上不同于乡村； ④具有较好的市政设施和公共设施，在物质构成上不同于乡村； ⑤是一定地域的政治、经济、文化的中心，在职能上区别于乡村。 另外在生活方式、价值观念、人口素质等方面也存在差异。 4、城市地域类型 ①行政地域－－指市政府管辖的城市范围。是各国按城镇界定规范确定的城镇地域。随着城市 建制的设立就明确划定。 ②实体地域－－指城市座落在地表的实际范围。相当于有着密集人口和各种建筑物组成的建成区。是完全不同于乡村景观的城镇聚落实体。又称景观地域。 ③功能地域－－体现城市人口居住、就业、购物、医疗、文教、娱乐等城市基本功能所涉及的 地域范围。（大都市区、大都市带） 5、城市人口指哪些人？ 城镇人口—也称驻地人口。应指占用城镇生活空间，并享受城镇各项公共服务设施和基础设施服务的人口群体，包括城镇实体地域内的常住非农业人口、农业人口和居住满6个月或1年以上的人口。 第三章城市的产生和发展 6、影响城市的产生与发展的因素？ （1）生产力因素是城市产生和发展的决定性因素 ①城市是社会经济发展到一定阶段的产物 ②生产力水平决定城市的发展水平——机器大工业替代工场手工业，掀起城镇化的世界浪潮。 ——全球化、信息化时代，城市在许多方面将发生深刻的变化 （2）自然条件因素是城市产生和发展的基础 第2章线性表习题参考答案 习题二 一、选择题 1. 链式存储结构的最大优点是（ D ）。 A.便于随机存取 B.存储密度高 C.无需预分配空间 D.便于进行插入和删除操作 2. 假设在顺序表{a0,a1,……,an－1}中，每一个数据元素所占的存储单元的数目为4，且第0 个数据元素的存储地址为100，则第7个数据元素的存储地址是（ D ）。 A. 106 B. 107 C.124 D.128 3. 在线性表中若经常要存取第i个数据元素及其前趋，则宜采用（ A ）存储方式。 A.顺序表 B. 带头结点的单链表 C.不带头结点的单链表 D. 循环单链表 4. 在链表中若经常要删除表中最后一个结点或在最后一个结点之后插入一个新结点，则宜 采用（ C ）存储方式。 A. 顺序表 B. 用头指针标识的循环单链表 C. 用尾指针标识的循环单链表 D. 双向链表 5. 在一个单链表中的p和q两个结点之间插入一个新结点， 假设新结点为S,则修改链的 java语句序列是（ D ）。 A. s.setNext(p); q.setNext(s); B. p.setNext(s.getNext()); s.setNext(p); C. q.setNext(s.getNext()); s.setNext(p); D. p.setNext(s); s.setNext(q); 6. 在一个含有n个结点的有序单链表中插入一个 新结点，使单链表仍然保持有序的算法的 时间复杂度是（ C ）。 A. O(1) B. O(log2n) C. O(n) D. O(n2) 7. 要将一个顺序表{a0,a1,……,an-1}中第i个数据元素 ai(0≤i≤n-1)删除，需要移动（ B ） 个数据元素。 A. i B. n-i-1 C. n-i D. n-i+1 8. 在带头结点的双向循环链表中的p结点之后插入一个新结 点s，其修改链的java语句序 列是（ D ）。 A. p.setNext(s); s.setPrior(p); p.getNext().setPrior(s); s.setNext(p.getPrior()); B. p.setNext(s); p.getNext().setPrior(s); s.setPrior(p); s.setNext(p.getNext()); C. s.setPrior(p); s.setNext(p.getNext()); p.setNext(s); p.getNext().setPrior(s); 第一章绪论 城市地理学：是研究在不同地理环境下，城市形成发展、组合分布和空间结构变化规律的学科。 1、研究对象：城市 概念：城市是有一定人口规模，以非农业人口为主的居民集居地，是一定地域的政治、经济、文化、科技、交通中心，是聚落的一种特殊形态； 2、主要任务：揭示和预测世界各国、各地区城市现象发展变化的规律性。 3、主要内容： （1）城市形成发展条件研究 （2）区域的城市空间组织研究 # ①城市化研究 ②区域城市体系的研究 ③城市分类研究 （3）城市内部空间组织研究 （4）城市可持续发展研究 （5）新方法、新技术应用和新领域的研究 4、改革开放以来中国城市地理学研究的特点 （1）注重城市空间结构的研究 《 （2）注重区域城镇体系的研究 （3）注重城市化的研究 （4）注重城市地理新领域与新方法的拓展和应用 5、中国城市地理学的研究趋势 （1）对理论的研究将进一步加强 （2）对经济全球化和全球城市的研究将加强 （3）对城市社会地理学的研究将加强 （4）对新领域和新方法的研究将加强 : （5）城市规划等应用研究将进一步加强 第二章城乡划分和城市地域 1、城市：是有一定人口规模，以非农业人口为主的居民集居地，是一定地域的政治、经济、文化、科技、交通中心，是聚落的一种特殊形态；具有区域性、综合性、复杂性的特点。 2、城镇：指以非农业人口为主，具有一定规模工商业的居民点。 3、城镇不同于乡村的几个特点： （1）城镇是以从事非农业活动的人口为主的居民点，在产业结构上不同于乡村。 （2）城镇一般聚居有较多的人口，在规模上区别于乡村。 （3）城镇有比乡村要大的人口密度和建筑密度，在景观上不同于乡村。 " （4）城镇具有电灯，广场，街道，影剧院，博物馆等市政设施和公共设施，在物质构成上不同于乡村。 （5）城镇一般是工业，商业，交通，文教的集中地，是一定地域的政治，经济，文化的中心，在职能上区别于乡村。还可以从生活方式，价值观念，人口素质等方面寻找城乡差异。 4、城市地域：亦称城市圈，与农村地域相对。广义上指从事非农业活动的地域。狭义上指城市化的地域，也就是市街地化的地域。包括三种类型： （1）行政地域：按行政管理划定的地域，其边界为辖区边界线；以行政辖区边界划分的、区域，界限明确。（2）实体地域：按城市景观与职能差异划分，其边界为实体边界；实体边界地区有一个城乡过渡带，因此这个边界是模糊的；辖区边界与实体边界不一定重叠。 城市地理学 第一章绪论 1.城市的理解： 1)、城市是有一定人口规模，并以非农业人口为主的居民集居地， 2)、城市是一种复杂的动态现象，它的兴起和发展受自然、经济、社会和人口等方面因素的影响。 3) 、城市是一种区域现象。 4)、城市本身是一个“面”，它的内部有各种构成要素的演变和组合问题。但从区域角度来看，城市也是一个“点” 2.城市地理学研究的对象：城市地理学是研究在不同地理环境下，城市形成发展、组合分布和空间结构变化规律的科学。 3.城市地理学的任务：○1一般来讲，城市地理学最重要的任务是揭示和预测世界各国、各地区城市现象发展变化的规律性○2我国城市地理学的迫切任务，就是从我国国情出发，解决社会经济建设中不断出现的矛盾和问题，为领导部门决策提供依据，以充分发挥城市的中心作用。 4.我国城市地理学工作中应注意的问题： ○1总结我国的实践经验基础上，借鉴西方城市地理学的理论和方法，加快城市理论建设 ○2学习外国城市地理学的理论和方法时，要考虑我国的国情 ○3要有发展的观点 ○4现代城市地理学的主要理论和模式，其归纳范围主要是西方城市，没有经过世界上各地区 5.城市地理学研究的内容：区域的城市空间组织和城市内部的空间组织 ◇1城市形成发展条件研究 ◇2区域的城市空间组织研究:○a城市化研究○b区域城市体系研究○c城市分类研究 ◇3城市内部空间组织研究:○a城市功能分区及其演化○b城市土地利用○c城市市场空间、社会空间和感应空间 ◇4城市可持续发展研究:环境问题、交通问题、城市社会问题、城市安全等 ◇5新领域、新方法和新技术的研究 ◇6城市政策研究 思考：城市地理学与主要与那些相关学科有关？ 答：城市经济学、城市社会学、城市规划学、城市生态学 第二章城乡划分和城市地域 1.城市和城镇：经国家批准设有市建制的城镇才称为城市，不够设市条件的建制镇才称为镇，市和镇的总称才叫城镇或市镇。我国城市规划法所称的城市就包括国家按行政建制设立的直辖市、市、镇。 2.乡村和城市的区别：①在产业构成上不同城镇是以从事非农业活动的人口为主的居民点②规模上区别城镇一般聚居有较多的人口③景观上不同城镇人口密度和建筑密度大于乡村，④物质构成上不同城镇具有许多市政设施和公共设施，⑤职能上不同城镇一般是工业、商业、交通、文教的集中地，是一定地域的政治、经济、文化的中心。还可以从生活方式、价值观念、人口素质等许多方面寻找城乡间的差异 3.世界各国各地区根据各自社会经济发展的特点，制订了不同的城镇定义标准。 4.(1)单纯用某级行政中心所在地为标准(2)单纯以城镇特征为标准(3)单纯以居民点下限人口数量划分城镇(4)用居民点的下限人口数量指标和密度指标相结合作为标准(5)用人口规模和城镇特征两个指标划分城镇(6)用人口规模和从业构成两个指标作标准(7)取两个以上指标作为标准(8)其它标准 5.城市的行政地域：按一定的标准或程序在行政上分别设置市、镇和乡、村等建制，并确定它们的行政管理边界。确定行政地域是为了管理 6.城市化地区：是美国为了确定城市的实体界限而提出的城市地域的概念与建成区 . 第2章线性表自测卷答案姓名班级 一、填空（每空1分，共13分） 1. 【严题集 2.2①】在顺序表中插入或删除一个元素，需要平均移动表中一半元素，具体移动的元素个数与表长和该元素在表中的位置有关。 2. 线性表中结点的集合是有限的，结点间的关系是一对一的。 3. 向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动n-i+1 个元素。 4. 向一个长度为n的向量中删除第i个元素(1≤i≤n)时，需向前移动n-i 个元素。 5. 在顺序表中访问任意一结点的时间复杂度均为O(1)，因此，顺序表也称为随机存取的数据结构。 6. 【严题集2.2①】顺序表中逻辑上相邻的元素的物理位置必定相邻。单链表中逻辑上相邻的元素的物理位置不一定相邻。 7. 【严题集2.2①】在单链表中，除了首元结点外，任一结点的存储位置由其直接前驱结点的链域的值指示。 8．在n个结点的单链表中要删除已知结点*p，需找到它的前驱结点的地址，其时间复杂度为O （n）。 二、判断正误（在正确的说法后面打勾，反之打叉）（每小题1分，共10分）（×）1. 链表的每个结点中都恰好包含一个指针。 答：错误。链表中的结点可含多个指针域，分别存放多个指针。例如，双向链表中的结点可以含有两个指针域，分别存放指向其直接前趋和直接后继结点的指针。 （×）2. 链表的物理存储结构具有同链表一样的顺序。。而链表的示意图有序错，链表的存储结构 特点是无序，（×）3. 链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。错，链表的结点不会移动，只是指针内容改变。（×）4. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。 错，混淆了逻辑结构与物理结构，链表也是线性表！且即使是顺序表，也能存放记录型数据。（×）5. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。 错，正好说反了。顺序表才适合随机存取，链表恰恰适于“顺藤摸瓜” （×）6. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。 错，前一半正确，但后一半说法错误，那是链式存储的优点。顺序存储方式插入、删除运算效率较低，的顺序表中， 插入和删除一个数据元素，平均需移动表长一半个数的数据元素。在表长为n（×）7. 线性表在物理存储空间中也一定是连续的。 错，线性表有两种存储方式，顺序存储和链式存储。后者不要求连续存放。（×）8. 线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。 错误。线性表有两种存储方式，在顺序存储时，逻辑上相邻的元素在存储的物理位置次序上也相邻。8 / 1 . （×）9. 顺序存储方式只能用于存储线性结构。 错误。顺序存储方式不仅能用于存储线性结构，还可以用来存放非线性结构，例如完全二叉树是属于非线性结构，但其最佳存储方式是顺序存储方式。（后一节介绍） （×）10. 线性表的逻辑顺序与存储顺序总是一致的。 。链式存储就无需一致。错，理由同7 三、单项选择题（每小题1分，共10分） （C）1．数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为：（A）存储结构（B）逻辑结构（C）顺序存储结构（D）链式存储结构 （ B ）2.一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是 （A）110 （B）108 （C）100 （D）120 （ A ）3. 在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是： （A）访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n） （B）在第i个结点后插入一个新结点（1≤i≤n） （C）删除第i个结点（1≤i≤n） （D）将n个结点从小到大排序 （ B ）4. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动个元素 （A）8 （B）63.5 （C）63 （D）7 （ A ）5. 链接存储的存储结构所占存储空间： （A）分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针 （B）只有一部分，存放结点值 （C）只有一部分，存储表示结点间关系的指针 （D）分两部分，一部分存放结点值，另一部分存放结点所占单元数 数制与码制 数制 （1）进位制：多位数码每一位的构成以及从低位到高位的进位规则。 （2）基数：在该进位制中可能用到的数码个数。 （3）位权：进位制的数中，每一位数码相应乘上一个固定的幂，表示大小，这 个固定的幂就是位权。 一、十进制计数法（D ） 数码为：0~9 基数是10 运算规律：逢十进一，即9 + 1 = 10 十进制数的权展开形式： 如：012310105105105105)555(?+?+?+?= 二、二进制计数法（B ） 数码为：0和1 基数是2 运算规律：逢二进一，即1 + 1 = 10 二进制数的权展开形式： 如：2101222120212021)01.101(--?+?+?+?+?= 三、八进制计数法（O ） 数码为：0~7 基数是8 运算规律：逢八进一，即7 + 1 = 10 八进制数的权展开形式： 如：2101288480878082)04.207(--?+?+?+?+?= 四、十六进制计数法（H ） 数码为：0~9和A~F 基数是16 运算规律：逢十六进一，即F + 1 = 10 十六进制数的权展开形式： 如：1011616101681613).8(-?+?+?=A D 数制的转换 将N 进制数按权展开，即可转换为十进制数。 二、八进制数转换 ① 二进制 八进制：由小数点开始，把每三位二进制数分成一组，不够的 补零，每组则对应一位八进制数。 如：001｜101｜010｜.010 8)2.152(01.1101010== 001｜110 8)16(01110== ② 二进制 八进制：由小数点开始，将每位八进制数用三位二进制数表示。 如：28)001111110()176(= 其中，八进制数1所对应的二进制数是001；八进制 数7所对应的二进制数是111；八进制数6所对应的 二进制数是110。 28)010110 .011111100()26.374(= 其中，八进制数3所对应的二进制数是011；八进制 数7所对应的二进制数是111；八进制数4所对应的二进制数是100；八进制数2所对应的二进制数是010；八进制数6所对应的二进制数是110。 二、十六进制数转换 ① 二进制 十六进制：由小数点开始，每四位二进制数对应于一位十六进 制数，不够的补零。 如：0001｜1101｜0100｜.0110 162)6.41()011.111010100(D == 第一章绪论 一、填空题 1、城市是指具有一定的，并以为主，具有的的居民集居地。 2、城市地理学是研究在不同地理环境下，城市的、和的科学。 3、城市地理学研究的主要任务有两个方面：各地城市现象发展规律，其次是各地城市现象发展规律。 4、标志城市地理学成为一门独立的学科的三大标志分别是：、、。 二、名词解释 1、城市地理学 三、简答题 1、列举城市地理学的主要研究容。 2、改革开放以来我国城市地理学研究特点 3、列举中国城市地理学的研究趋势。 第二章城乡划分与城市地域 一、填空题 1、广义上的城市等同于城镇，包括和，狭义上的城市仅仅包括建制市。 2、城市地域涉及三种类型：行政地域、、。 3、辖9区9县（县级市），该地域是的。 4、在面积上，市的实体地域城市规划区的面积（大于？小于？）。 5、城市的行政地域与实体地域在围上存在两种情况，一是前者后者，这种情况多在国出现；另一种是前者后者，国外多出现。 6、美国的城镇实体地域由和人口超过2500以上的居民点两部分组成。 7、美国的城市化地区由一个或几个设有建制的以及与之有紧密联系的组成。 8、大都市带是由法国学者于1957年首次提出。 9、有关我国城镇设置标准，我国先后提出了5个标准，分别是1955年标准、1963年标准、年标准、年标准以及年标准。 10、1984年标准中只针对做出修改。 11、1986年城镇设置标准的容包括、、。 12、改革开发以前，我国城镇设置模式主要为；1986年以来则主要的。 13、管辖面积有53840km2，该地域为的；9个建制区的面积为10198km2，该面积为的。2013年，该市的建成区面积450 km2，该地域为市的。 14、在1990年第四次人口普查中，我国的城镇人口由人口和人口两部分组成。 15、在1990年第四次人口普查中，市人口包括所辖区人口和所辖的街道人口；镇人口包括不设区市所辖居委会人口和县辖镇的居委会人口。 16、在2000年第五次人口普查中，提出了和原则。 17、1986年城镇设置标准中的市带县中的“市”是指（设区市？不设区市？）。 二、选择题 1、2010年，市南岗区总人口99.75万人，松北区人口19.51万人，以上两区的土地面积分别为165 km 2、745km2。松北街道为松北区政府驻地，松浦街道和万宝镇同为松北区辖区，松浦街道为松北区政府驻地建设延伸到的镇级地域，但松北政府驻地建设并未延伸到万宝镇。万宝镇政府驻地的居委会建设延伸到a居委会，但并未延伸到b村，按照2000年我国城镇人口统计标准，以下属于市城镇人口的有（）。 A南岗区全部人口 B 松北区全部人口 C 松北街道全部人口 D松浦街道全部人口E万宝镇全部人口 F a居委会人口G b村人口 2、我国1986年城镇建制改革的容有（）。 A切块设市 B 整县改市C市带县D镇改市 3、下列关于城市的描述不正确的是（）。 A.城市是聚落的一种特殊形态 B.城市是一种复杂的动态现象 第二章线性表练习题 一、选择题 1.线性表是具有n个的有限序列。 A、表元素 B、字符 C、数据元素 D、数据项 E、信息项 2.线性表的静态链表存储结构与顺序存储结构相比优点是。 A、所有的操作算法实现简单 B、便于随机存储 C、便于插入和删除 D、便于利用零散的存储器空间 3.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素算法的时间复杂度为。 A、O(log2n) B、O(1) C、O(n) D、O(n2) 4.（1）静态链表既有顺序存储的特点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关； （2）静态链表中能容纳元素个数的最大数在定义时就确定了，以后不能增加；（3）静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。 以上错误的是。 A、（1）、（2） B、（1） C、（1）、（2）、（3） D、（2） 6.在双向链表存储结构中，删除p所指的结点时须修改指针。 A、p－＞next－＞prior=p－＞prior; p－＞prior－＞next=p－＞next; B、p－＞next=p－＞next－＞next;p－＞next－＞prior=p; C、p－＞prior－＞next=p;p－＞prior=p－＞prior－＞prior; D、p－＞prior=p－＞next－＞next;p－＞next=p－＞prior－＞prior; 7.在双向循环链表中，在P指针所指的结点后插入q所指向的新结点，其修改指针的操作是。 A、p－＞next=q; q－＞prior=p;p－＞next－＞prior=q;q－＞next=q; B、p－＞next=q;p－＞next－＞prior=q;q－＞prior=p;q－＞next=p－＞next; C、q－＞prior=p; q－＞next=p－＞next; p－＞next－＞prior=q; p－＞next=q; D、q－＞next=p－＞next;q－＞prior=p;p－＞next=q;p－＞next=q; 8.将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是。 A、 n b、2n－1 c、2n d、n－1 9.在一个长度为n的顺序表中，在第i个元素（1≤i≤n+1）之前插入一个新元素时须向后移动个元素。 A、n－i B、n－i+1 C、n－i－1 D、i 10.线性表L=(a1，a2,……an)，下列说法正确的是。 A、每个元素有有一个直接前驱和一个直接后继 B、线性表中至少有一个元素 C、表中诸元素的排列必须是由小到大或由大到小。 D、除第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继。 11.对单链表表示法，以下说法错误的是。 A、数据域用于存储线性表的一个数据元素 B、指针域(或链域)用于存放一指向本结点所含数据元素的直接后继所在结点的指针 C、所有数据通过指针的链接而组织成单链表 D、NULL称为空指针，它不指向任何结点只起标志作用 【城市地理学】复习参考 第一章 1、城市地理学的研究对象 城市地理学是研究城市空间组织规律性的科学，具体地讲，是研究在不同地理环境下，城市形成发展、组合分布和空间结构变化规律的科学。 2、城市地理学研究的主要内容 （1）城市形成发展条件研究 （2）区域的城市空间组织研究 （3）城市内部空间组织研究 （4）城市问题研究 第二章 1、都市区：一个大的人口核心以及与这个核心具有高度的社会经济一体化倾向的邻接社区 的组合，一般以县作为基本单元。中心县+外围县 大都市带：许多都市区连成一体，经济、社会、文化等活动相互作用密切，是一个巨大的城市地域复合体。 城市群：城市群是城市发展到成熟阶段的最高空间组织形式，是在地域上集中分布的若干城市和特大城市集聚而成的庞大的、多核心、多层次城市集团，是大都市区 的联合体。 2、区分城市的行政地域、实体地域、功能地域 第三章 1、简述不同类型城市的形成和发展（形成的原因、功能与特点、分类、发展条件） 中心地型城市 形成动因：商品农业 功能：满足农村的物资集散和综合服务的需要 特点：职能综合，发展稳定，等级鲜明 类别：集镇、城镇、县城 发展条件： 以交通运输职能为主的城市 形成动因：交通地理位置 功能：满足区际贸易和交通转运的需要 特点：职能较单一，发展起伏较大 类别：铁路沿线、铁路枢纽、渡口、河海港、边境和特区、综合运输枢纽城市 发展条件： 以某种专门职能为主的城市 形成动因：天赋的资源和人类特殊需要 功能：满足某种专门需要，集聚经济，规模经济 特点：职能较单一，对外联系广，联系内容单一，发展历史短但速度快，发展起伏大 类别：矿业、工矿、工业、风景旅游、科学文化城等 发展条件： 第四章 1、城市化：人口向城市集中的过程和农村地区转变为城市地区的过程。 郊区城市化：也叫城市郊区化，简称郊区化，就是人口、就业岗位和服务业从大城市中心向郊区迁移的一种分散化过程。 逆城市化：人口从大城市和主要的大都市区向小的都市区甚至非都市区迁移的一种分散化过程。 再城市化：城市出现的城市人口回流，城市中心区再现活力，而郊区出现形体再开发的过程。 2、城市化地区 3、乡村——城市人口迁移的动因分析（城乡人口迁移的推力、拉力，即推拉说、推拉理论）城市工业化的发展提供了大量的就业机会，把农村人口拉了进来，“拉因”成为城市发展的主要因素。乡村破产使乡村人口大量涌进城市，造成城市人口膨胀，“推因”成为城市发展的主导因素。 4、简述城市化的类型划分 （1）以大城市为中心来考察城市化现象：向心型城市化与离心型城市化 （2）按照城市离心扩散形式的不同：外延型城市化与飞地型城市化 （3）景观型城市化与职能型城市化 （4）积极型城市化与消极型城市化 （5）针对中国城市化状况提出来的：自上而下型城市化与自下而上型城市化 第五章 1、简述当代中国城市化的主要特征 （1）城市化进程波动性大 （2）城市规模体系的动态变化加速 （3）城市化水平的省际差异显著 （4）郊区城市化开始显现 （5）都市连绵区成为国家经济核心地区 第六章 1、划分城市经济活动的基本与非基本部分 一个城市的全部经济活动，按其服务对象来分，可分成两部分： 1）为本城市的需要服务的， 2）为本城市以外的需要服务的。 （1）基本经济活动：为外地服务的部分，是从城市以外为城市所创造收入的部分，它是城市得以存在和发展的经济基础，是导致城市展的主要动力。是为本城市以外的需要服务的。离心型的基本活动：例如，城市生产的工业产品或城市发行的书刊报纸运到城市以外销售；向心型的基本活动：例如，外地人到这个城市来旅游、购物、求学或接受医疗等。 （2）非基本的活动：满足城市内部需求的经济活动，随着基本部分的发展而发展，它被称为非基本活动部分。是为城市本身服务的活动。 第2章习题 (1) 第2章习题 2.1若将顺序表中记录其长度的分量listlen改为指向最后一个元素的位置last，在实现各基本运算时需要做那些修改？ 【解】 //用线性表最后一个元素的下标last代替listLen实现顺序表 #define MAXLEN 100 typedef int elementType; typedef struct sllLast { elementType data[MAXLEN]; int last; }seqList; //初始化 void initialList(seqList &S) { https://www.wendangku.net/doc/6016392801.html,st=-1; } //求表长度 int listLength(seqList S) { return https://www.wendangku.net/doc/6016392801.html,st+1; } //按序号取元素 bool getElement(seqList S,int i,elementType &x) { if(i<1 || i>https://www.wendangku.net/doc/6016392801.html,st+1) //i为元素编号，有效范围在https://www.wendangku.net/doc/6016392801.html,st+1之间 return false; else { x=S.data[i-1]; return true; } } //查找元素x，成功：返回元素编号；失败：返回0 int listLocate(seqList S,elementType x) { int i; for(i=0;i<=https://www.wendangku.net/doc/6016392801.html,st;i++) { if(S.data[i]==x) return i+1; //找到，转换为元素编号输出} return 0; } //插入元素 int listInsert(seqList &S,elementType x, int i) { int k; if(https://www.wendangku.net/doc/6016392801.html,st>MAXLEN-1) return 0; //表满，返回0 else if(i<1 || i>https://www.wendangku.net/doc/6016392801.html,st+2) return 1; //插入位置查处范围，返回1 else { for(k=https://www.wendangku.net/doc/6016392801.html,st;k>=i-1;k--) S.data[k+1]=S.data[k]; S.data[i-1]=x; https://www.wendangku.net/doc/6016392801.html,st++; return 2; } } //删除元素 int listDelete(seqList &S,int i) { int k; if(https://www.wendangku.net/doc/6016392801.html,st==-1) return 0; //空表，返回0 else if(i<1 || i>https://www.wendangku.net/doc/6016392801.html,st+1) return 1; //删除元素编号超出范围，返回1 else 1城市是一种什么样的地理环境 城市作为地理环境的特殊性体现在：1拥有高密度的人口和经济2人类对自然环境的干涉最强烈3是一个不完全脆弱的环境系统4呈复杂性且动态变化 城市是具有一定人口规模，并以非农业人口为主的居民集聚地，是聚落的一种特殊形态。2城市地理学研究的内容。 城市地理学的研究对象是城市这一复杂的动态大系统。城市地理学主要研究在不同地理环境下城市形成，发展，组合分布和空间结构变化规律。它既是人文地理学的重要分支，又是城市科学群的重要组成部分。 主要研究内容可概括为：1城市形成发展条件研究。2区域的城市空间组织研究。又包括城市化研究和区域城市体系的研究，以及城市分类研究。3城市内部空间组织研究。4城市可持续发展研究。5新方法，新技术应用和新领域的研究。 3中国当代城市地理学动向和内容？挑几个，谈谈想法，如新型城镇化 所谓新型城镇化，是指坚持以人为本，以新型工业化为动力，以统筹兼顾为原则，推动城市现代化、城市集群化、城市生态化、农村城镇化，全面提升城镇化质量和水平，走科学发展、集约高效、功能完善、环境友好、社会和谐、个性鲜明、城乡一体、大中小城市和小城镇协调发展的城镇化建设路子。新型城镇化的“新”就是要由过去片面注重追求城市规模扩大、空间扩张，改变为以提升城市的文化、公共服务等内涵为中心，真正使我们的城镇成为具有较高品质的适宜人居之所。城镇化的核心是农村人口转移到城镇，而不是建高楼、建广场。农村人口转移不出来，不仅农业的规模效益出不来，扩大内需也无法实现。新型城镇化的本质是用科学发展观来统领城镇化建设。“新型城镇化道路”具有这样几个特点和要求：（1）规划起点高。（2）途径多元化。（3）聚集效益佳。（4）辐射能力强。（5）个性特征明。（6）人本气氛浓。（7）城镇联动紧。（8）城乡互补好。 城市体系( 城镇体系) 城镇体系是指一定区域范围内在经济社会和空间发展上具有有机联系的城镇群体。城镇体系是社会发展到一定阶段的产物。城镇通过区域内外各生产要素的优化配段, 相互之间的合理分工和空间组合, 从无序到有序, 形成带动区内外经济社会发展的有机整体。这是城镇作为一种先进的社会形态应有的作用, 也是社会发展的要求。从而, 也成为城市地理学一个重要的研究内容。 城市化 城市化是一个社会历史进程, 它是因社会生产力发展而引起的城镇的数量增加、规模扩大、人口向城镇集中、城市的物质文明与文化、生活方式扩散, 导致地域空间的性质和景观转化的过程。因而城市化是一种全球性的社会现象。在一个国家的不同类型地区, 又由于各区原有的基础不同, 所处的社会、经济发展阶段各异, 在城市化进程中的特点与问题也不相同。因此, 有必要根据各国、各类型区城市化进程的规律与出现的问题提出不同的措施与政策。 城市地域结构的研究 城市地域结构是城市各物质要素(工业、交通、居住、道路、商业服务设施、工程管线等等) 在城市这个空间载体的分布与组合, 是城市地理学的核心内容。中国的城市地理界对城市地域结构的研究,无论从数量和深度上, 较之其他领域均要薄弱得多。 地理学家介绍了国外的有关理论, 讨论和研究了城市地域结构的概念、类型、地域结构演变阶段及动因机制、发展模式等。对中国和各类城市地域结构的实证分析是近几年此项研究的主要方面。“ 第一章绪论 第一节城市地理学的研究对象。任务和内容 一、城市地理学的研究对象和主要任务 1、城市地理学的研究对象 城市地理学的研究对象就是城市这一复杂的动态大系统。 2、城市地理学的主要任务是揭示和预测世界各国、各地区城市现象发展变化的规律性。揭示和掌握世界各国、各地区城市现象的规律，属于认识世界的任务；科学预测世界各国、各地区城市现象变化的规律，属于改造世界的任务。 二、城市地理学研究的主要内容 1、城市形成发展条件研究 2、区域的城市空间组织研究 3、城市内部空间组织研究 4、城市可持续发展研究 5、新方法、新技术应用和新领域的研究 第二节城市地理学与相关学科的关系 一、城市地理学的学科性质 （1）描述性研究，即描述城市现象的空间现状； （2）解释性研究。即研究城市现象的因果关系； （3）评价性研究，即既要认识资源空间分配不平衡性，又要识别那些符合效益和社会公平标准的可供选择的状态。 二、城市地理学与相关学科的关系 城市是一种特殊的地域，是地理的、经济的、社会的、文化的区域实体，是各种人文要素和似然要素的综合体。 1、与城市经济学的关系。（P7） 2、与城市社会学的关系 3、与城市规划学的关系 4、与城市生态学的关系 第三节西方城市地理学的发展简史 四阶段： 一、1920年以前（一战刚结束） 城市地理学在地理学体系中式一门年轻的学科，至今不过半个多世纪。在此之前，城市地理学属于聚落地理学（或称居民点地理学）中的一个组成部分。 二、1920-1950 三、1950-1970 四、1970年以来 第四节中国城市地理学的发展 一、中国城市地理学的发展历程 1、1949年以来的兴起阶段 2、1949-1966年的相对萧阶段 3、1967-1976年的停滞阶段 4、1976-1990年的振兴阶段 5、20世纪90年代初至今的快速发展阶段 《城市地理学》复习思考题题答案 第一章绪?论 1、简要说明城市的概念和城市的基本特征 城市是有一定人口规模，并以非农业人口为主的居民集居地，是聚落的一种特殊形态。（P1） 城市的特征﹡属于历史的范畴﹡区域性（●）﹡综合性 2、简述城市地理学研究对象、任务和主要内容。 ●研究对象：研究在不同地理环境下，城市形成发展、组合分布和空间结构变化规律的科学。（P2） ●研究任务：揭示和预测世界各国、各地区城市现象发展变化的规律性。（P2）●主要内容:城市的形成发展条件、城市的生长.城市内部空间组织：城市功能分区、城市功能区演化、城市土地利用、社会空间、人的行为等。城市可持续发展研究：城市环境、城市交通、城市住宅、城市贫困。新方法、新技术应用和新领域的研究.区域的城市空间组织：城市化、区域城市体系、城市分类。 3、简述城市地理学的学科性质。 1、地理学的三级学科，属于人文地理学的分支 2、在我国，城市地理学属于自然科学中的社会科学；在发达国家，城市地理学归为社会科学. 3、综述，城市地理学是属于社会科学范畴的地理科学，是一门特殊的社会科学。 4、城市地理学与城市规划学的区别与联系。 区别;★学科性质上的区别：城市地理学：地理科学；城市规划学：技术科学★研究方向上的区别：城市地理学研究区域中的城市和城市中的区域，理论性较强；城市规划学从事单个城市内部的平面设计，偏重工程组织和设计，工程性较强。联系★具有渗透关系的相互独立的学科。书上还有这里没空补充p8 5、简述改革开放以来我国城市地理学的发展特点。 1、注重城市空间结构的研究; 2、注重区域城镇体系的研究; 3、注重城市化研究; 4、注重城市地理新领域与新方法的拓展和应用。 6、西方城市地理学的发展可分为几个阶段？各阶段研究有何特点？（此题答案不具体，详细请看课件或课本） 一、1920年以前 工业革命、城市发展----聚落地理学----城市区位、城市内部形态 城市地理学成为专门学科之前的阶段，从人地关系的角度去研究聚落 二、1920－1950年 帕克、沃斯、伯吉斯（20年代）----住宅区、中心商业区、工业区----土地利用模式 克里斯塔勒（1933年）----《南德的中心地》----中心地等级体系 初步奠定研究重点阶段,从社会学科角度来研究城市。 三、1950－1970年 1、“数量革命”－克里斯塔勒 2、城市系统与城市空间分析 空间学派兴起和城市地理学独立阶段，从社会学科角度来研究城市。 四、1970以来年 人文学派、行为学派、激进学派的产生和城市地理学的多元化发展阶段。 第二章城乡划分与城市地域 1、名词解释： 《城市地理学》复习思考题题答案 第一章绪论 1、简要说明城市的概念和城市的基本特征 城市是有一定人口规模，并以非农业人口为主的居民集居地，是聚落的一种特殊形态。（P1） 城市的特征﹡属于历史的范畴﹡区域性（●）﹡综合性 2、简述城市地理学研究对象、任务和主要内容。 ●研究对象：研究在不同地理环境下，城市形成发展、组合分布和空间结构变化规律的科学。（P2） ●研究任务：揭示和预测世界各国、各地区城市现象发展变化的规律性。（P2）●主要内容:城市的形成发展条件、城市的生长.城市内部空间组织：城市功能分区、城市功能区演化、城市土地利用、社会空间、人的行为等。城市可持续发展研究：城市环境、城市交通、城市住宅、城市贫困。新方法、新技术应用和新领域的研究.区域的城市空间组织：城市化、区域城市体系、城市分类。 3、简述城市地理学的学科性质。 1、地理学的三级学科，属于人文地理学的分支 2、在我国，城市地理学属于自然科学中的社会科学；在发达国家，城市地理学归为社会科学. 3、综述，城市地理学是属于社会科学范畴的地理科学，是一门特殊的社会科学。 4、城市地理学与城市规划学的区别与联系。 区别;★学科性质上的区别：城市地理学：地理科学；城市规划学：技术科学★研究方向上的区别：城市地理学研究区域中的城市和城市中的区域，理论性较强；城市规划学从事单个城市内部的平面设计，偏重工程组织和设计，工程性较强。联系★具有渗透关系的相互独立的学科。书上还有这里没空补充p8 5、简述改革开放以来我国城市地理学的发展特点。 1、注重城市空间结构的研究; 2、注重区域城镇体系的研究; 3、注重城市化研究; 4、注重城市地理新领域与新方法的拓展和应用。 6、西方城市地理学的发展可分为几个阶段？各阶段研究有何特点？（此题答案不具体，详细请看课件或课本） 一、1920年以前 工业革命、城市发展----聚落地理学----城市区位、城市内部形态 城市地理学成为专门学科之前的阶段，从人地关系的角度去研究聚落 二、1920－1950年 帕克、沃斯、伯吉斯（20年代）----住宅区、中心商业区、工业区----土地利用模式 克里斯塔勒（1933年）----《南德的中心地》----中心地等级体系 初步奠定研究重点阶段,从社会学科角度来研究城市。 三、1950－1970年 1、“数量革命”－克里斯塔勒 2、城市系统与城市空间分析 空间学派兴起和城市地理学独立阶段，从社会学科角度来研究城市。 四、1970以来年 人文学派、行为学派、激进学派的产生和城市地理学的多元化发展阶段。 第二章城乡划分与城市地域 1、名词解释： 第二章线性表 一、填空题 1、数据逻辑结构包括线性结构、树型结构、图型结构这三种类型，树形结构和图形结构合称为非线性结构。 2、在线性结构中，第一个结点没有前驱结点，其余每个结点有且只有个前驱结点，最后一个结点没有后续结点，其余每个结点有且只有一个后续结点。 3、在顺序表中插入或删除一个元素，需要平均移动一半元素，具体移动的元素个数与插入或删除的位置有关。 4、在顺序表中，逻辑上相邻的元素，其物理位置一定相邻。在单链表中，逻辑上相邻的元素，其物理位置不一定相邻。 5、在带头结点的非空单链表中，头结点的存储位置由头指针指示，首元素结点的存储位置由头结点的next域指示，除首元素结点外，其它任一元素结点的存储位置由其直接前趋结点的next域指示。 6、阅读下列算法，并补充所缺内容。 void purge_linkst( ListNode *& la ) { // 从头指针为 la 的有序链表中删除所有值相同的多余元素，并释放被删结点空间ListNode *p,*q; if(la==NULL) return; q=la; p = la->link; while (p) { if (p && ___(1)p->data!=q->data___) {q=p; p = p->link;} else { q->link= ___(2)p->link___; delete(p); p=___(3)q->link___; } }//while }// purge_linkst 二、选择题 1、在数据结构中，从逻辑上可以把数据结构分成 C。 A、动态结构和静态结构 B、紧凑结构和非紧凑结构 C、线性结构和非线性结构 D、内部结构和外部结构 2、线性表的逻辑顺序与存储顺序总是一致的，这种说法 B。 A、正确 B、不正确 3、线性表若采用链式存储结构时，要求内存中可用存储单元的地址D。 A、必须是连续的 B、部分地址必须是连续的 C、一定是不连续的 D、连续或不连续都可以 4、在以下的述叙中，正确的是B。 A、线性表的线性存储结构优于链表存储结构 B、二维数组是其数据元素为线性表的线性表 C、栈的操作是先进先出 D、队列的操作方式是先进后出 三、综合题 1、已知L是无表头结点的单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。 A、在P结点后插入S结点的语句序列是（（4）、（1））； B、在P结点前插入S结点的语句序列是（（7）、（11）、（8）、（4）、（1））； C、在表首插入S结点的语句序列是（（5）、（12））；第2章线性表习题解答
城市地理学专题复习知识
第2章线性表习题参考答案
城市地理学重点
城市地理学
第2章 线性表答案
数制与码制(听课笔记)
城市地理学复习习题
第2章线性表习题解析(答)
城市地理学
第2章线性表习题解答
城市地理学
城市地理学
城市地理学课后思考题
城市地理学课后思考题
第二章_线性表(参考答案)