第二章线性表
线性结构特点:
?唯一头元素
?唯一尾元素
?除头元素外，均有一个直接前驱
?除尾元素外，均有一个直接后继
书目信息、排队、算术表达式。
2.1 线性表的定义
1. 线性表的语言定义
线性表是n个数据元素的有限序列。
例，英文字母表(A，B，C，……，Z)
线性表中的数据元素也可以由若干个数据项构成。
例，包含大量记录的登记表
线性表可以表示为n 个数据元素的有限序列: (a1，…，a i-1，a i，…，a n)
其中a1是头元素，a n是尾元素，a i是第i 个元素。
a i-1是a i的直接前驱，a i是a i-1的直接后继。
抽象数据类型线性表List 的定义:
ADT List {
数据对象: D = { a i | a i∈ElemSet，i = 1, 2, …, n }
数据关系: R1 = { < a i-1, a i > }
基本操作:
InitList( &L )
结果: 构造一个空的线性表L。
DestroyList( &L )
条件: 线性表L 已存在。
…
} ADT List
其它基本操作包括:
ClearList( &L )
ListEmpty ( L )
ListLength ( L )
GetElem ( L，i，&e )
LocateElem ( L，e，compare() )
PriorElem ( L，cur_e，&pre_e )
NextElem ( L，cur_e，&next_e )
ListInsert ( &L，i，e )
ListDelete ( &L，i，&e )
ListTraverse ( L，visit() )
2.2 线性表的顺序表示和实现
线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素。
线性表顺序存储结构表示
# define LIST_INIT_SIZE 100
# define LISTINCREMENT 10
typedef struct {
Elemtype* elem; //数据元素
int length; // 表长，初始为0
int listsize; // 表存储容量
} SqList;
Status InitList_Sq ( SqList &L ) { //初始化空线性表
L.elem = ( ElemType * ) malloc
( LIST_INIT_SIZE * sizeof(ElemType) );
if ( ! L.elem ) exit(OVERFLOW) ;
L.length = 0 ;
L.listsize = LIST_INIT_SIZE ;
return OK ;
}
线性表的顺序存储结构的优点
?可随机存取表中任意数据元素(第i 个)
L.elem[i-1]
* (L.elem+i-1)
?直接可获取线性表的长度
L.length
算法2.4 在第i个数据元素之前插入一个新的元素
例，在第i 个元素前插入b
思想:
1. 找到第i个元素的位置。
2. 将第n到i个元素均向后移动一个位置。
3. 将新元素放置在第i个位置。
int ListInsert_Sq ( Sqlist &L ，int i ，ElemType e ) {
ElemType *p, *q;
q = & L.elem[i-1] ；//找到第i 个元素位置
for ( p = & L.elem[L.length-1] ；p >= q ；p -- )
* (p+1) = * p ；// 后移元素
* q = e ；// 插入新元素
++L.length ；
return 0；
}
int ListDelete_Sq ( Sqlist &L ，int i ，ElemType &e ) {
if ( i < 1 || i > L.length ) return 1 ；
p = & L.elem[i-1] ；// 找到第i 个元素
e= * p ；// 取第i 个元素的值
for ( p++ ；p <= & L.elem[ L.length - 1]；p ++ )
* (p - 1) = * p ；// 前移
-- L.length；
return 0 ；
}
2.3 线性表的链式表示和实现
线性表的链式存储结构的特点是用一组随意的存储单元存储线性表的数据元素。
例，线性表数据为{3，5，7}
结点: 两部分信息组成，存储数据元素信息的数据域，存储直接后继存储位置信息的指针域。
线性表的单链表存储结构
typedef struct LNode {
ElemType data ；
struct LNode * next ；
} * LinkList ；
2.3.1 线性单链表
Head: 头指针，指向链表中第一个结点。
0: 空指针，有时也表示为“NULL”或“∧”。
头结点: 为了某些操作的方便，通常在链表第一个结点之前附加一个结点，
没有实际意义。
空表:
线性表的链式存储结构的特点
缺点:
?不可随机存取表中任意数据元素
?不可直接获取线性表的长度
算法2.8: 取出线性单链表第i个元素。
思想:
1. 找到第1 个元素；
2. 循环找到第i个元素；
3. 取出元素；
Status GetElem_L ( LinkList L，int i，ElemType &e ) { p = L->next ；j = 1 ；//p指向第一个元素，j计数
while ( p && j < i ) {
p = p->next ；++j ；//循环找到第i 个元素
}
if ( ! p || j > i ) return ERROR ；
e = p->data ；
return OK ；
}
例，取出第i=3个元素。
e = p->data = Sun
平均时间复杂度: O(n)
优点:
数据元素的插入、删除相对方便
在b之前插入元素x :
1. 找到b结点的前驱结点
2. 构造将要插入的结点
3. 指针变换
算法2.9 在第i个数据元素之前插入一个新的元素
Status ListInsert_L ( LinkList &L ，int i ，ElemType e ) {
1. 找到第i 个结点的前驱结点
2. 构造将要插入的结点
3. 指针变换
}
Status ListInsert_L ( LinkList &L ，int i ，ElemType e ) { p = L；j = 0；
while ( p && j < i - 1 ) { p = p->next ；++j ；}
//找到第i 个结点的前驱结点
if ( ! p || j > i - 1 ) return ERROR ；
s = ( LinkList ) malloc ( sizeof (LNode) ) ；
s->data = e ；
s->next = NULL ；//建立新结点
s->next = p->next ；
p->next = s ；//插入新结点
return OK ；
}
例，在第3个元素之插入一个新元素。
p->next = s
s->next = p->next
平均时间复杂度: O(n)
算法2.11 利用插入操作构造一条完整的单链表。
void CreateList_L ( LinkList &L，int n ) {
L = ( LinkList ) malloc ( sizeof (LNode) ) ；
L->next = NULL ；//建立头结点
for ( i = n ；i > 0 ；--i ) {
p = ( LinkList ) malloc ( sizeof (LNode) ) ；
Scanf ( &p->data ) ；
p->next = L->next ；
L->next = p ；//在表头插入新结点
}
}
例，
讨论: 如何逆置一个单链表为一个新表?
作业: 设计算法，将单链表L 中的第i 个结点和其后继结点交换位置，要求只修改指针。
删除元素b :
1. 确定指针
2. 取出要删除的结点
3. 指针变换
4. 释放内存
1）p ->next = p ->next ->next
2）q = p->next
p->next = q->next
free(q) ；
讨论单链表的删除操作，课堂演讲。
2.3.2 其他线性链表
?循环链表
?双向链表
从某个结点出发寻找直接后继?
从某个结点出发寻找直接前驱?
1. 循环链表
表中最后一个结点的指针域指向头结点，形成一个环。
优点:
从表的任意结点出发均可以找到表中的任意其他结点。
空表:
操作与线性单链表基本一致，差别只是在于算法中的循环结束条件不是p是否为空，而是p是否等于头指针。
例，取循环链表第i 个元素。
Status GetElem_L ( LinkList L，int i，ElemType &e ) { p = L->next ；j = 1 ；
while ( p <> L && j < i ) {
p = p->next ；++j ；
}
if ( p == L || j > i ) return ERROR ；
e = p->data ；
return OK ；
}
顺次合并两个线性表
有时为了方便某些操作，通常在循环链表中设立尾指针。
Tail2->next = Tail1->next
p = Tail2->next ->next
Tail2->next = Tail1->next
Tail1->next = p
p = Tail2->next ->next
q = Tail2->next
Tail2->next = Tail1->next
Tail1->next = p
Free(q)
在循环链表中寻找结点的直接后继很简单，只需要O(1)；
但要寻找结点的直接前趋需要循环一遍，需要O(n)。
2. 双向循环链表
双向循环链表的结点有两个指针域: 一个指向直接后继，一个指向直接前趋。
typedef struct DuLNode{
ElemType data ；
struct DuLNode * prior ；
struct DuLNode * next ；
}DuLNode ，* DuLinkList ；
空表:
性质: 设d 是指向某个结点的指针，则有
d->next->prior = d->prior->next = d
操作: 插入、删除操作将会处理两个方向。
1) 插入
1. 找到要在之前插入的结点，p记录。；
2. 构造新结点；
3. s->prior = p->prior ；
4. p->prior->next = s ；
5. s->next = p ；
6. p->prior = s ；
2) 删除
1. 找到要删除的结点，p记录。
2. p->prior->next = p->next ；
3. p->next->prior = p->prior ；
4. free(p) ；
思考作业: 古罗马趣味问题:
随机数n
习题六树和二叉树6.1 单项选择题 (A) (B) (C) (D) 图8.7 4棵二叉树 1. 如图8.7所示的4棵二叉树，_ _不是完全二叉树。 图8.8 4棵二叉树 2. 如图8.8所示的4棵二叉树，__B_是平衡二叉树。 3. 在线索化二叉树中，t所指结点没有左子树的充要条件是B__o A. t —> left二NULL B. t —> ltag=1 C. t —> ltag=1 且t —> left=NULL D. 以上都不对 4. 二叉树按某种顺序线索化后，任一结点均有指向其前驱和后续的线索，这种说 法_B__ o
A.正确 B. 错误 5. 二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法 _A__。 A.正确 B. 错误 6. 由于二叉树中每个结点的度最大为2,所以二叉树是一种特殊的树，这种说法 _B_o A.正确 B. 错误 7. 设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为—B__o A. 2h B. 2h-1 C. 2h+1 D. h+1 a 8. 如图8.9所示二叉树的中序遍历序列 B o 图8.9 一棵二叉树 A. abcdgef B. dfebagc C. dbaefcg D. defbagc 9. 已知某二叉树的后序遍历序列是d abec，中序遍历序
列是debac，它的前序遍历 序列是D ___ 。 A. acbed B. decab C. deabc D. cedba 10. 设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前的条件是 B 。 A. a在b的右方 B. a在b的左方 C. a是b的祖先 D. a是b的子孙 11?假定在一棵二叉树中，双分支结点数为15,单分支结点数为30个，则叶子结 点数为个。B A. 15 B. 16 C. 17 D. 47 12. 某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是 dgbaechf，则其后序遍历的结点访问顺序是D _____ 。 A. bdgcefha B. gdbecfha C. bdgaechf D. gdbehfca 13. 二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、 小于其右孩子的值。这种说法__B__ o A.正确 B. 错误 14. 按照二叉树的定义，具有3个结点的二叉树有_。__种。 A. 3 B. 4 C. 5 D. 6 15. 一棵二叉树如图8.10所示，其中序遍历的序列为
第二章线性表 线性结构特点: ?唯一头元素 ?唯一尾元素 ?除头元素外，均有一个直接前驱 ?除尾元素外，均有一个直接后继 书目信息、排队、算术表达式。 2.1 线性表的定义 1. 线性表的语言定义 线性表是n个数据元素的有限序列。 例，英文字母表(A，B，C，……，Z) 线性表中的数据元素也可以由若干个数据项构成。 例，包含大量记录的登记表 线性表可以表示为n 个数据元素的有限序列: (a1，…，a i-1，a i，…，a n) 其中a1是头元素，a n是尾元素，a i是第i 个元素。 a i-1是a i的直接前驱，a i是a i-1的直接后继。 抽象数据类型线性表List 的定义: ADT List { 数据对象: D = { a i | a i∈ElemSet，i = 1, 2, …, n } 数据关系: R1 = { < a i-1, a i > } 基本操作: InitList( &L ) 结果: 构造一个空的线性表L。 DestroyList( &L ) 条件: 线性表L 已存在。 … } ADT List 其它基本操作包括:
ClearList( &L ) ListEmpty ( L ) ListLength ( L ) GetElem ( L，i，&e ) LocateElem ( L，e，compare() ) PriorElem ( L，cur_e，&pre_e ) NextElem ( L，cur_e，&next_e ) ListInsert ( &L，i，e ) ListDelete ( &L，i，&e ) ListTraverse ( L，visit() ) 2.2 线性表的顺序表示和实现 线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素。 线性表顺序存储结构表示 # define LIST_INIT_SIZE 100 # define LISTINCREMENT 10 typedef struct { Elemtype* elem; //数据元素 int length; // 表长，初始为0 int listsize; // 表存储容量 } SqList; Status InitList_Sq ( SqList &L ) { //初始化空线性表 L.elem = ( ElemType * ) malloc ( LIST_INIT_SIZE * sizeof(ElemType) );
第一章绪习题一 1.有下列几种用二元组表示的数据结构，试画出它们分别对应的图形表示（当出现多个关系时， 对每个关系画出相应的结构图），并指出它们分别属于何种结构。 ⑴ A=(K,R)其中 K={a1,a2,a3...,an} R={} ⑵ B=(K,R)其中 K={a,b,c,d,e,f,g,h} R={r} r={
2.4已知顺序表L递增有序，试写一算法，将X插入到线性表的适当位置上，以保持线性表的有序性。 解： int InsList(SeqList *L,int X) { int i=0,k; if(L->last>=MAXSIZE-1) { printf("表已满无法插入！")； return(ERROR); } while(i<=L->last&&L->elem[i]
} } 2.6已知线性表中的元素（整数）以递增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有大于mink且小于maxk的元素（若表中存在这样的元素），分析你的算法的时间复杂度（注意：mink和maxk是给定的两个变量，他们的值为任意的整数）。 解： int Delete(Linklist,int mink,int maxk) { Node *p,*q; p=L; while(p->next!=NULL) p=p->next; if(mink>=maxk||L->next->data>=maxk||mink+1=maxk) { printf("参数不合法！"); return ERROR; } else { while(p->next->data<=mink) p=p->next; q=p->next; while(q->data 020101：经济学专业 培养目标、就业前景、开设该专业的学校名单、 专业排名及相关评价 转载本站中国大学专业评价资料，请注明“本资料来自好生源高考志愿填报系统” 专业级别：本科所属专业门类：经济学类报读热度：★★★ 培养目标：本专业培养具备比较扎实的马克思主义经济学理论基础，熟悉现代西方经济学理论，比较熟练地掌握现代经济分析方法，知识面较宽，具有向经济学相关领域扩展渗透的能力，能在综合经济管理部门、政策研究部门、金融机构和企业从事经济分析、预测、规划和经济管理工作的高级专门人才。 培养要求：本专业要求学生系统掌握经济学基本理论和相关的基础专业知识，了解市场经济的运行机制，熟悉党和国家的经济方针、政策和法规，了解中外经济发展的历史和现状；了解经济学的学术动态；具有运用数量分析方法和现代技术手段进行社会经济调查、经济分析和实际操作的能力；具有较强的文字和口头表达能力的专门人才，能熟练掌握一门外语。 毕业生应获得的知识与能力： 1．掌握马克思主义经济学、当代西方经济学的基本理论和分析方法； 2．掌握现代经济分析方法和计算机应用技能； 3．了解中外经济学的学术动态及应用前景； 4．了解中国经济体制改革和经济发展； 5．熟悉党和国家的经济方针、政策和法规； 6．掌握中外经济学文献检索、资料查询的基本方法、具有一定的经济研究和实际工作能力。 主要课程：政治经济学、《资本论》、西方经济学、统计学、国际经济学、货币银行学、财政学、经济学说史、发展经济学、企业管理、市场营销、国际金融、国际贸易等。 学业年限：四年 授予学位：经济学学士 职业方向：科研人员、经济师、注册税务师或注册会计师、会计、人力资源管理师、商务翻译、金融业从业人员、精算师、保险代理人、高级代理、企业家、保险经纪人、金融产品研发人员。 开设经济学专业院校毕业生能力用人单位评价： 本专业毕业生能力被评为A+等级的学校有： 北京大学复旦大学武汉大学南京大学 中国人民大学南开大学厦门大学上海财经大学 本专业毕业生能力被评为A等级的学校有： 清华大学浙江大学吉林大学西安交通大学 北京师范大学四川大学山东大学中山大学 上海交通大学华东师范大学华中科技大学东北大学 兰州大学重庆大学福州大学湖南大学 东北师范大学暨南大学云南大学福建师范大学 东南大学华南师范大学中央财经大学西北大学 南昌大学华中师范大学对外经济贸易大学北京交通大学 黑龙江大学郑州大学山西财经大学辽宁大学 东北财经大学河南大学首都经济贸易大学江西财经大学 浙江工商大学南京财经大学西南财经大学中南财经政法大学 兰州商学院安徽财经大学北京物资学院嘉兴学院 本专业毕业生能力被评为B+等级的学校有： 同济大学北京航空航天大学中国农业大学北京理工大学 山西大学中央民族大学新疆大学南京理工大学 贵州大学燕山大学内蒙古大学北京邮电大学 中国石油大学(北京) 武汉理工大学西南交通大学西南大学 天津师范大学河北大学安徽大学中国地质大学(北京) 广西大学西北师范大学湖南师范大学陕西师范大学 苏州大学南京师范大学河海大学青岛大学 第二章习题 一判断题 1．线性表的逻辑顺序与存储顺序总是一致的。× 2．顺序存储的线性表可以按序号随机存取。 3．顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。× 4．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。 5．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。× 6．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。 7．线性表的链式存储结构优于顺序存储结构。 8．在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。×9．线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。 10．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。× 11.线性表中每个元素都有一个直接前驱和一个直接后继。（×） 12.线性表中所有元素的排列顺序必须由小到大或由小到小。（×） 13.静态链表的存储空间在可以改变大小。（×） 14.静态链表既有顺序存储结构的优点，又有动态链表的优点。所以它存取表中第i个元素的时间与i无关。（×） 15.静态链表中能容纳元素个数的最大数在定义时就确定了，以后不能增加。（） 16.静态链表与动态链表的插入、删除操作类似，不需要做元素的移动。（） 17.线性表的顺序存储结构优于链式结构。（×） 18.在循环单链表中，从表中任一结点出发都可以通过前后的移动操作扫描整个循环链表。（×） 19.在单链表中，可以从头结点开始查找任何一个结点。（） 20.在双链表中，可以从任何一结点开始沿同一方向查找到任何其他结点。（×） 二单选题 (请从下列A，B，C，D选项中选择一项) 1．线性表是( ) 。 (A) 一个有限序列，可以为空； (B) 一个有限序列，不能为空； (C) 一个无限序列，可以为空； (D) 一个无序序列，不能为空。 ，在任何位置上插入或删除操作都是等概率的。插n．对顺序存储的线性表，设其长度为2． 入一个元素时平均要移动表中的（）个元素。 (A) n/2 (B) n+1/2 (C) （n -1）/2 (D) n 第二章地理信息系统空间数据结构 2.1 地理空间数据及其特征 【学时安排】 1 学时 【目的要求】 1、掌握地理信息系统的数据类型； 2、理解地理信息系统的数据来源； 3、掌握空间数据的特点。 【重点难点】 地理信息系统的数据类型与特征。 【教学方法与手段】 示例式教学方法，多媒体教学手段。 一、GIS空间数据的来源与类型 空间数据是GIS的核心，也有人称它是GIS的血液，因为GIS的操作对象是空间数据，因此设计和使用GIS 的第一步工作就是根据系统的功能，获取所需要的空间数据，并创建空间数据库。 1、地理数据的来源 GIS中的数据来源和数据类型繁多，概括起来主要有以下几种来源： ⑴地图数据。来源于各种类型的普通地图和专题地图，这些地图的内容丰富，图上实体间的空间关系直观，实体的类别或属性清晰，实测地形图还具有很高的精度，是地理信息的主要载体，同时也是地理信息系统最重要的信息源。 ⑵影像数据。主要来源于卫星遥感和航空遥感，包括多平台、多层面、多种传感器、多时相、多光谱、多角度和多种分辨率的遥感影像数据，构成多源海量数据，也是GIS的最有效的数据源之一。 ⑶地形数据。来源于地形等高线图的数字化，已建立的数字高程模型( DEM和其他实 测的地形数据等。 ⑷属性数据。来源于各类调查报告、实测数据、文献资料、解译信息等。 ⑸元数据。来源于由各类纯数据通过调查、推理、分析和总结得到的有关数据的数据，例如数据来源、数据权属、数据产生的时间、数据精度、数据分辨率、源数据比例尺、数据转换方法等。 2、空间数据的类型 空间数据根据表示对象的不同，又具体分为七种类型(图2-1) ，它们各表示的具体内容 如下： (1) 类型数据。例如考古地点、道路线、土壤类型的分布等。 (2) 面域数据。例如随机多边形的中心点，行政区域界线、行政单元等。 (3) 网络数据。例如道路交点、街道、街区等。 (4) 样本数据。例如气象站、航线、野外样方分布区等。 (5) 曲面数据。例如高程点、等高线、等值区域等。 (6) 文本数据。例如地名、河流名称、区域名称等。 (7) 符号数据。例如点状符号、线状符号、面状符号(晕线) 等。 数据结构试题及答案 一、选择题（每小题2分，共20分），每个题的备选答案中，只有一个是正确的，请将答案填写在试题的括号中。 1、对顺序存储的线性表，设其长度为20，在任何位置上插入或删除操作都是等概率的。插入一个元素时平均要移动表中的（）个元素。 A．10 B．9 C．11 D．12 2、若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。 A．单链表 B．仅有头指针的单循环链表 C．双链表 D．仅有尾指针的单循环链表 3、当利用大小为n的数组顺序存储一个栈时，假定用top==n表示栈空，则向这个栈插入一个元素时，首先应执行（）语句修改top指针。 A．top++ B．top-- C．top = 0 D．top 4、设入栈顺序为A，B，C，D，E，则出栈序列不可能是（）。 A．EDCBA B．ABCDE C．ADEBC D．ABDEC 5、已知关键字序列（46, 79, 56, 38, 40, 84），采用快速排序（以位于最左位置的关键字为基准）得到的第一次划分结果为：（） A．{ 40, 38, 46, 56, 79, 84 } B．{ 38, 46, 79, 56, 40, 84 } C．{ 38, 46, 56, 79, 40, 84 } D．{ 40, 38, 46, 79, 56, 84 } 6、一个有n个顶点和n条边的无向图一定是（）。 A．不连通的 B．连通的 C．有环的 D．无环的 7、在一棵具有n个结点的二叉树的第i层上，最多具有（）个结点。 A．2i B．2i-1 C．2i+1 D．2n 8、对线性表采用折半查找法，该线性表必须（）。 A．采用顺序存储结构B．采用顺序存储结构，且元素按值有序 C．采用链式存储结构 D．采用链式存储结构，且元素按值有序 9、在一棵具有n个结点的完全二叉树中，分支结点的最大编号为（）。 A．?(n-1)/2? B．?n/2? C．?n/2? D．?n/2? -1 10、在一个无向图中，所有顶点的度数之和等于所有边数的 ( ) 倍。 A．3 B．1/2 C．1 D．2 二、填空题（每小题2分，共20分），请将正确的结果，填写在试题的横线上。 1、带头结点的循环链表L为空的条件是。 2、序列A={12, 70, 33, 65, 24, 56}给出对应于序列A的大顶堆HA（以线性数组表 示）。 3、每次使两个相邻的有序表合并成一个有序表，这种排序方法叫做________排序。 4、设循环队列Q的队头和队尾指针分别为front和rear，队列的最大容量为MaxSize，且规定判断队空的条件为Q.front = = Q.rear，则队列的长度为。 5、已知数组A[0..11][0..8]按行优先存储，每个元素占有5个存储单元，且A[0][0]的地址为1000（十进制），则A[6][7]的地址为________________。 6、已知广义表A=(a，()，(b，(c)))，则其深度为。 7、在一棵二叉树中，假定度为2的结点个数为5个，度为1的结点个数为6个，则叶子结点数为__ ____个。 8、设森林F中有3棵树，第1、2、3棵树的结点个数分别为n1、n2、n3，当把森林F转换成一棵二叉树后，其根结点的右子树中有________个结点。 9、将含有64个结点的完全二叉树从根结点开始顺序编号，根结点为第1号，其他结点自上向下，同一层自左向右连续编号。则第30号结点的双亲结点的编号为。 10、有序表(1,2,3,4,5,6,7,8,9)用折半查找方法，查找元素3的比较次数为。 《高等学校毕业生登记表》填写指南 《高等学校毕业生登记表》是装入学生档案中的必装材料之一，是严格按照毕业生人数征订和发放的，原则上丢失不予以补办。毕业生务必保管好登记表，并认真阅读填表说明，认真填写。为避免填错，建议拟稿后填写。各年级办应指导学生毕业生如实填写登记表，同时严格审查毕业生填写内容。如因毕业生登记表内容不实造成的后果，属毕业生责任的，其后果由毕业生个人负责；属学校老师责任的，由毕业生辅导员负责。 《填表说明》如下： 1.毕业生必须实事求是地填写本表，填写时一律用钢笔或签字笔，字迹要清楚。 2.表内所列项目，要全部填写，不留空白，如有情况不明无法填写时，应写“不清”、“不详”及其原因，如无该项情况，亦应写“无”。 3.“本人学历及社会经历”自入小学时起，以时间顺序详细填写，年月要衔接。中途间断学习和工作的时间也要填入，并加以说明。 4.“家庭主要成员”是指直系亲属（父母和爱人、子女）。“主要社会关系”一般是指家庭的直系亲属（兄弟姐妹等）。 5.“本人健康状况”主要填写有无疾病和体质强弱状况，无特殊情况填写“良好”。 6.贴最近一寸正面半身免冠照片。 7.如有其他问题，需要说明时，可加纸附上。 具体填写要求如下： 1、学校：填写“济南大学泉城学院” 2、系科：填写所在学院名称的全称，如“经济系”； 3、专业：填写所学专业全称，如“经济学”； 4、姓名、曾用名：姓名应写法定姓名（须与高考录取通知书上姓名一致）。有曾用名者可填写，没有写“无”； 5、出生年月：应用阿拉伯数字，格式“ΧΧΧΧ年ΧΧ月ΧΧ日”，如“1983年11月30日”； 6、“籍贯”：系指学生祖籍的地方，自已出生时的父母户口所在地为准，按现在的行政区划详细填写，只填写省（自治区、自辖市）县两级。 7、“民族”：须填写全称。 8、“现在家庭住址”：要具体到寄信能收到的通信地址，后面写邮政编码。如“山东省日照市翟营南大南389号卓达小区书香园一区Χ栋Χ单元ΧΧ室。（050033）”； 9、是否华侨，侨居何处。不是则填“否”，是则填“是”及“侨居地址”。 10、何时何地何人介绍参加共产党或共青团：如“2005年5月1日在济南大学泉城学院由ΧΧΧ介绍加入共产党”； 11、本人身体健康情况：应分别填写“良好”、“较弱”，有慢性病或身体伤残者，应具体填写。 12、婚否情况：一般填写“未婚”，已结婚者填写“已婚”；其他情况要详细。 13、家庭经济情况及主要经济来源：按较好、一般、较困难、特困四个层次选一填写，如“家庭经济情况为人均元/月，主要经济来源为父母工资”；。 14、何时何地何原因受过何种奖励或处分：填写校级和校级以上获奖情况；如“2001—2002学年度在济南大学泉城学院获一等奖学金”、“2003—2004学年度在济南大学泉城学院获三好学生称号”等。处分情况本人不填写，统一由学生处填写。 15、本人学历及社会经历：应从小学开始填写，统一用“ΧΧΧΧ年ΧΧ月至ΧΧΧΧ年ΧΧ月”的格式，时间要衔接。如“1989年9月——1995年8月在ΧΧΧ省ΧΧΧ县 第 1 章绪论 课后习题讲解 1. 填空 ⑴（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 【解答】数据元素 ⑵（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。 【解答】数据项，数据元素 【分析】数据结构指的是数据元素以及数据元素之间的关系。 ⑶从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。【解答】集合，线性结构，树结构，图结构 ⑷数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（） 和（）。 【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的 关系 ⑸算法具有五个特性，分别是（）、（）、（）、（）、（）。 【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性 ⑹算法的描述方法通常有（）、（）、（）和（）四种，其中，（）被称为算法语言。 【解答】自然语言，程序设计语言，流程图，伪代码，伪代码 ⑺在一般情况下，一个算法的时间复杂度是（）的函数。 【解答】问题规模 ⑻设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若 为n*log25n，则表示成数量级的形式为（）。 【解答】Ο(1)，Ο(nlog2n) 【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。 2. 选择题 ⑴顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链接存储结构中的数据元素之间的逻辑关 系是由（）表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针 【解答】C，D 【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数 组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中 的指针表示。 ⑵假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不 能相互继承。则表示该遗产继承关系的最合适的数据结构应该是（）。 A 树 B 图 C 线性表 D 集合 第二章习题 1.描述以下三个概念的区别：头指针，头结点，首元素结点。 2.填空： （1）在顺序表中插入或删除一个元素，需要平均移动元素，具体移动的元素个数与有关。 （2）在顺序表中，逻辑上相邻的元素，其物理位置相邻。在单链表中，逻辑上相邻的元素，其物理位置相邻。 （3）在带头结点的非空单链表中，头结点的存储位置由指示，首元素结点的存储位置由指示，除首元素结点外，其它任一元素结点的存储位置由指示。3．已知L是无表头结点的单链表，且P结点既不是首元素结点，也不是尾元素结点。按要求从下列语句中选择合适的语句序列。 a. 在P结点后插入S结点的语句序列是：。 b. 在P结点前插入S结点的语句序列是：。 c. 在表首插入S结点的语句序列是：。 d. 在表尾插入S结点的语句序列是：。 供选择的语句有： （1）P->next=S; （2）P->next= P->next->next; （3）P->next= S->next; （4）S->next= P->next; （5）S->next= L; （6）S->next= NULL; （7）Q= P; （8）while(P->next!=Q) P=P->next; （9）while(P->next!=NULL) P=P->next; （10）P= Q; （11）P= L; （12）L= S; （13）L= P; 4.设线性表存于a(1:arrsize)的前elenum个分量中且递增有序。试写一算法，将X插入到线性表的适当位置上，以保持线性表的有序性。 5.写一算法，从顺序表中删除自第i个元素开始的k个元素。 6.已知线性表中的元素（整数）以值递增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有大于mink且小于maxk的元素（若表中存在这样的元素），分析你的算法的时间复杂度（注意：mink和maxk是给定的两个参变量，它们的值为任意的整数）。 7.试分别以不同的存储结构实现线性表的就地逆置算法，即在原表的存储空间将线性表（a1, a2..., an）逆置为（an, an-1,..., a1）。 （1）以一维数组作存储结构，设线性表存于a(1:arrsize)的前elenum个分量中。 （2）以单链表作存储结构。 8.假设两个按元素值递增有序排列的线性表A和B，均以单链表作为存储结构，请编写算法，将A表和B表归并成一个按元素值递减有序排列的线性表C，并要求利用原表（即A 表和B表的）结点空间存放表C。 济南大学泉城学院 2010～2011学年第二学期课程考试试卷（A 卷） 课 程 大学物理（1） 授课教师 考试时间 2011年 7 月 1 日 考试班级 学 号 姓 名 题号 一 二 三 四 五 六 总 分 得分 一、选择题（每小题 3 分，共42分，请将答案填入下列表格内） 题号 1 2 3 4 5 6 7 8 9 10 11 12 13 14 答案 1. 一质点在平面上运动，已知质点位置矢量的表示式为j bt i at r 2 2 （其中a 、b 为常量）, 则该 质点作 (A) 匀速直线运动． (B) 变速直线运动． (C) 抛物线运动． (D)一般曲线运动． 2. 竖立的圆筒形转笼，半径为R ，绕中心轴OO ＇转动，物块A 紧靠在圆筒的内壁上，物块与圆筒间的摩擦系数为μ，要使物块A 不下落 ，圆筒转动的角速度ω至少应为 (A) R g (B)g (C) R g (D)R g 3. 如图所示，一匀质细杆可绕通过上端与杆垂直的水平光滑固定轴O 旋转，初始状态为静止悬挂．现 有一个小球自左方水平打击细杆．设小球与细杆之间为非弹性碰撞，则在碰撞过程中对细杆与小球这一系统 (A) 只有机械能守恒． (B) 只有动量守恒． (C) 只有对转轴O 的角动量守恒． (D) 机械能、动量和角动量均守恒． 4. 一物体作简谐振动，振动方程为)2 1 cos( t A x ．在 t = T /2（T 为周期）时刻，物体的速度 为 (A) A ． (B) 2 A ． (C) A ． (D) 0 5. 一个质点作简谐振动，振幅为A ，在起始时刻 质点的位移为A 2 1 ，且向x 轴的正方向运动，代 表此简谐振动的旋转矢量图为 6. 如图所示，两列波长为 的相干波在P 点相遇．波在S 1点振动的初相是 1，S 1到P 点的距离是r 1； 波在S 2点的初相是 2，S 2到P 点的距离是r 2，以k 代表零或正、负整数，则P 点是干涉极大的条件为 (A) k r r 12． (B) k 212 ． (C) k r r 2/)(21212 ． (D) k r r 2/)(22112 ． 7. 在相同的时间内，一束波长为 的单色光在空气中和在玻璃中 (A) 传播的路程相等，走过的光程相等． (B) 传播的路程相等，走过的光程不相等． (C) 传播的路程不相等，走过的光程相等． (D) 传播的路程不相等，走过的光程不相等． 8. 一束波长为 的单色光由空气垂直入射到折射率为n 的透明薄膜上，透明薄膜放在空气中，要使反射光得到干涉加强，则薄膜最小的厚度为 (A) ． (B) / (4n )． (C) ． (D) / (2n )． 9. 如果单缝夫琅禾费衍射的第一级暗纹发生在衍射角为 30°的方位上．所用单色光波长为 =500 nm ，则单缝宽度为 (A) 2.5×10-5 m ． (B) 1.0×10- m ． O x o A x A 21 A 2 1 A 2 1 (C) (D) o o o A 21 x x x A A x A x S 2 r 1 r 2 P 得 分 阅卷人 …………………………………………装…………………………订…………………………线………………………………………… A O O ′ 数据结构课程作业_A 交卷时间：2017-08-09 10:08:51 一、单选题 1. (7分)设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置脚注(10)表示用10进制表示。 A. 688 B. 678 C. 692 D. 696 纠错 得分： 7 知识点：第五章 展开解析 答案 C 解析第五章第二节综合题目 2. (7分)若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( ) A. 1，2，3 B. 9，5，2，3 C. 9，5，3 D. 9，4，2，3 纠错 得分： 0 知识点：第九章 展开解析 答案 D 解析第九章第一节有序表的查找 (7分)设某完全无向图中有n个顶点，则该完全无向图中有（）条边。 A. n(n-1)/2 B. n(n-1) C. n2 D. n2-1 纠错 得分： 7 知识点：第七章 展开解析 答案 A 解析第七章第一节综合题目 4. (7分)若在任意一棵二叉树中，有n0个叶子结点，有n2个度为2的结点，则：n0=_____ A. n2+1 B. n2-1 C. n2+2 D. n2-2 纠错 得分： 7 知识点：第六章 展开解析 答案 A 解析第六章第二节二叉树的性质 5. (7分)栈的插入和删除操作在（）进行。 A. 栈顶 B. 栈底 C. 任意位置 D. 指定位置 得分： 7 知识点：第三章 展开解析 答案 A 解析第三章第一节栈的表示和实现 6. (7分)设有序表中有1000个元素，则用二分查找查找元素X最多需要比较（）次。 A. 25 B. 10 C. 7 D. 1 纠错 得分： 7 知识点：第九章 展开解析 答案 B 解析第九章第一节有序表的查找 7. (7分)设某棵二叉树的高度为10，则该二叉树上叶子结点最多有（）。 A. 20 B. 256 C. 512 D. 1024 纠错 得分： 7 知识点：第六章 展开解析 答案 C 解析第六章第六节二叉树的性质 数据结构习题 第一章绪论 1.6 在程序设计中，常用下列三种不同的出错处理方式： 1) 用exit语句终止执行并报告错误； 2) 以函数的返回值区别正确返回或错误返回； 3) 设置一个整形变量的函数参数以区别正确返回或某种错误返回。 试讨论这三种方法各自的优缺点。 1.7 在程序设计中，可采用下列三种方法实现输出和输入： 1) 通过scanf和printf语句； 2) 通过函数的参数显示传递； 3) 通过全局变量隐式传递。 试讨论这三种方法的优缺点。 1.8 设n为正整数。试确定下列各程序段中前置以记号@的语句的频度： 5) for (i = 1; i <= n; i++ ) { for (j = 1; j <= i; j++) { for (k = 1; k <= j; k++) { @ x += delta; } } } 答案：n*(n+1)*(n+2) =1+（1+2）+（1+2+3）+...+(1+2+3+...+n) =∑ =+ n i i i 1 2 / )1 ( * =1/2*∑ =+ n i i i i 1 * =n*(n+1)*(2n+1)/12 +n*(n+1)/4 =n*(n+1)*(n+2)/6 7) x = n; //n是不小于1的常数 y = 0; while (x >= (y + 1) * (y + 1)) { @ y++; } 答案：n向下取整 8) x = 91; y = 100; while (y > 0) { @ if (x > 100) { x -= 10; y--;} else { x++; } } 答案：if 执行次数为1100， if 判断内部执行为100次 1.19 试编写算法，计算i!·2i （i = 0, 1, …, n-1）的值并分别存入数组a[arrsize]的各个分量中。假设计算机中允许的整数最大值为MAXINT ，则当n > arrsize 或对某个k （0 ≤ k ≤ n-1）使k!·2k > MAXINT 时，应按出错处理。注意选择你认为较好的出错处理方法。 1.20 试编写算法求一元多项式∑==n i i i x a x 0n )(P 的值P n (x 0)，并确定算法中每一语句的执行 次数和整个算法的时间复杂度。注意选择你认为较好的输入和输出方法。本题的输入为a i （i=0, 1, …, n ）、x 0和n ，输出为P n (x 0)。 第二章空间数据结构和空间数据库本章概述：地理信息系统的操作对象是空间地理实体，建立一个地理信息系统的首要任务是建立空间数据库，即将反映地理实体特性的地理数据存储在计算机中，这需要解决地理数据具体以什么形式在计算机中存储和处理即空间数据结构问题和如何描述实体及其相互关系即空间数据库模型问题。本章重点介绍主要的空间数据结构和空间数据库模型。 §2.1 地理实体及其描述 介绍地理实体的概念，地理实体需要描述的内容，实体的空间特征和实体间的空间关系。 §2.2 矢量数据结构 讲述矢量数据的图形表示、获取方式和表示(即矢量编码方法)。§2.3 栅格数据结构 讲述栅格数据的图形表示、栅格数据的组织、栅格结构的建立和栅格数据的表示。 §2.4 矢量栅格一体化数据结构 针对矢量栅格数据结构互为优缺点状况，介绍集两者优点为一体的矢量栅格一体化数据结构的概念和具体数据结构设计方法。 §2.5 三维数据结构 主要阐述基于栅格的八叉树三维数据结构的基本原理和存储结构。在矢量结构方面，介绍常用的三维边界表示法的方法原理、特点和应用。§2.6 空间数据模型 首先介绍数据库有关基础知识，传统数据模型如何存储图形数据及其局限性，重点阐述面向对象技术、面向对象模型和用于地理信息系统的空间数据库管理系统的类型。 §2.7 空间数据库的设计、建立和维护 介绍空间数据库的设计的内容、建立过程和维护方法。 您可能还想看前贴【GIS原理学习（一）】【GIS原理学习（二）】【GIS 原理学习（三）】【GIS原理学习（四）】 §2.1 地理实体及其描述 地理信息系统是以地理实体作为描述、反映现实世界中空间对象的单体。在地理信息系统中需要描述地理实体的名称、位置、形状、功能等内容，这些内容反映了地理实体的时间、空间和属性三种特性，其中空 一、填空题 1.PLC采用循环扫描工作方式，操作系统执行一 次循环错做所需的时间称为扫描周期。 2.PLC的开关量输出单元按输出电路所用开关 器件的不同可分为继电器输出、晶体管输出和双向晶闸管输出。 3.S7中有三种计数器分别是加计数器(S_CU)、 减计数器(S_CD)、可逆计数器(S_CUD)。 4.用STEP-7编写PLC的控制程序，可以选择三 种顺序结构：线性式、分布式编程、结构式。 5.STEP-7用户程序通常由组织块(OB)、功能块 (FB)或功能(FC)等三种类型的逻辑块和数据块组成。 6.同种数据类型的组合称之为数组，不同类型的 数据的组合是结构。 二、简单题 1.简述可编程控制器的工作过程。 PLC采用的是循环扫描工作方式。在PLC中，用户程序按照先后顺序存放在PLC中，工作时CPU 从第一条指令开始执行，直到遇到结束符后又返回第一条，如此周而复始，不断循环。PLC在运行过程中，总是处在不断循环的顺序扫描过程中。PLC 上电后，就在系统程序的监控下，周而复始地按固定顺序对系统内部的各种任务进行查询、判断和执行，这个过程实质上是一个不断循环的顺序扫描过程。一个循环扫描过程称为扫描周期。 2.什么是扫描周期？它主要受什么影响？ 答：扫描周期是PLC每执行一遍从输入到输出所用的时间。 扫描周期的长短与CPU的运算速度、I/O点的情况、用户应用程序的长短以及编程情况等有关 3.s7-300的编程元件有哪些？ 答：1. 输入映像寄存器（输入继电器）I 2.输出映像寄存器（输出继电器）Q 3.位存储器M（或称辅助继电器） 4.外部输入寄存器PI 5.外部输出寄存器PQ 6.定时器T(共5种) 7.计数器C (共3种) 8.数据块寄存器DB 9.本地数据寄存器L 4.M0.0、MB0、MW0和MD0有何区别？答：M0.0 , MB0, MW0和MD0表示位、字节、字和双字存储单元。 5.s7-300系列PLC共有几种定时器？各种定时器的运行方式有何不同？ 答：S_PULSE脉冲定时器SP。S_PEXT扩展脉冲定时器SE。S_ODT接通延时定时器SD。S_ODTS 保持型接通延时定时器SS。S_OFFDT关断延时定时器SF。 6.功能块FB和功能FC有何区别？ 答：功能块（FB）有一个数据结构与该功能块的参数完全相同的数据块，称为背景数据块，背景数据块依附于功能块，它随着功能块的调用而打开，随着功能块的结束而关闭。存放在背景数据块中的数据在功能块结束时继续保持。 功能（FC）则不需要背景数据块，功能调用结束后数据不能保持。 7.置位、复位指令与rs触发器指令有何区别？答：在LAD中置位／复位指令要放在逻辑串最右端，而不能放在逻辑串中间。在LAD中，RS触发器可以用在逻辑串最右端，结束一个逻辑串，也可用在逻辑串中，影响右边的逻辑操作结果。 8.在变量声明表中，静态变量与临时变量有何不同？ 答：静态变量在PLC运行期间始终被存储。S7将静态变量定义在背景数据块中，因此只能为FB定义静态变量。功能块FC不能有静态变量。 临时变量仅在逻辑块运行时有效，逻辑块结束时存储临时变量的内存被操作系统另行分配。S7将临时变量定义在L堆栈中。临时变量可以用于所有块中(OB, FC, FB)。当块执行的时候它们被用来临时存储数据，当退出该块时这些数据将丢失。这些临时数据存储在L stack (局部数据堆栈)中。 9.启动组织块OB100、OB101、OB102的区别？答：OB100为暖启动组织模块；OB101为热启动组织模块；OB102为冷启动组织模块。 10.Profibus由哪三部分组成？Profibus采用何种方式进行总线访问的控制？ 答：Profibus-DP;Profibus-PA;Profibus-FMS. Profibus采用Profibus-DP方式进行总线访问的控制. 一本 北京市：北京大学清华大学中国人民大学北京师范大学北京航空航天大学中国农业大学北京理工大学北京科技大学北京交通大学中国协和医科大学中央音乐学院北京邮电大学北京外国语大学北京化工大学中国政法大学北京语言大学北京工业大学中央戏剧学院中央美术学院对外经济贸易大学中央财经大学北京中医药大学北京体育大学北京林业大学中国传媒大学国际关系学院中央民族大学石油大学 天津市：南开大学天津大学天津医科大学 河北省：中央司法警官学院华北电力大学燕山大学河北工业大学 山西省：太原理工大学山西农业大学 内蒙古自治区：内蒙古大学 辽宁省：大连理工大学东北大学辽宁大学大连海事大学沈阳农业大学辽宁工程技术大学 吉林省：吉林大学东北师范大学延边大学 黑龙江省：哈尔滨工业大学哈尔滨工程大学东北林业大学东北农业大学大庆石油学院 上海市：复旦大学上海交 通大学同济大学华东师 范大学上海财经大学华 东理工大学上海第二医科 大学上海大学上海外国 语大学东华大学 江苏省：南京大学东南大 学中国矿业大学南京师 范大学南京航空航天大学 南京理工大学南京农业大 学苏州大学中国药科大 学河海大学江苏大学南 京信息工程大学江南大学 浙江省：浙江大学 安徽省：中国科学技术大学 安徽大学合肥工业大学 福建省：厦门大学福州大 学 江西省：南昌大学江西农 业大学 山东省：山东大学中国海 洋大学 河南省：郑州大学 湖北省：武汉大学华中科 技大学华中师范大学中 国地质大学华中农业大学 武汉理工大学中南财经政 法大学 湖南省：中南大学湖南大 学湖南师范大学湘潭大 学 广东省：中山大学华南理 工大学华南师范大学暨 南大学华南农业大学 广西壮族自治区：广西大学 重庆市：重庆大学西南政 法大学西南师范大学西 南农业大学 四川省：四川大学电子科 技大学西南交通大学西 南财经大学四川农业大学 云南省：云南大学 陕西省：西安交通大学西 北工业大学西北大学西 安电子科技大学西北农林 科技大学陕西师范大学 长安大学陕西科技大学 甘肃省：兰州大学 新疆维吾尔自治区：新疆大 学 全国重点大学名录 重点综合大学(17所) 北京大学内蒙古大学 新疆大学复旦大学武汉 大学厦门大学中国人民 大学吉林大学兰州大学 中山大学山东大学湘潭 大学南开大学西北大学 云南大学四川大学南京 大学 重点理工院校（52所） 清华大学华南理工大学 中南工业大学北方交通大 学电子科技大学成都理经济学大学排名
数据结构第2章基础习题 作业
地理信息系统空间数据结构
济南大学 数据结构试卷
毕业生登记表填写和模板
数据结构(第二版)课后习题答案(王红梅主编)
(完整版)数据结构课后习题及解析第二章
10-11(2)泉城学院考试试卷A
数据结构课程作业
数据结构作业
第二章 空间数据结构和空间数据库
济南大学期末考试PLC试卷A
一本二本三本院校名单
相关主题
文本预览