数据结构
实验一
学号：
姓名:
实验名称：线性表顺序表示的基本操作
实验地点：数学实验室
指导老师：
完成时间：2010/10/4
1、实验目的
掌握线性表的逻辑特征
?掌握线性表顺序存储结构的特点，熟练掌握顺序表的基本运算
2、实验内容：
建立顺序表，完成顺序表的基本操作：初始化、插入、删除、逆转、输出、销毁, 置空表、求表长、查找元素、判线性表是否为空；
1．问题描述：利用顺序表,设计一组输入数据（假定为一组整数），能够对顺序表进行如下操作：
?创建一个新的顺序表，实现动态空间分配的初始化；
?根据顺序表结点的位置插入一个新结点(位置插入)，也可以根据给定的值进行插入(值插入)，形成有序顺序表；
?根据顺序表结点的位置删除一个结点(位置删除)，也可以根据给定的值删除对应的第一个结点，或者删除指定值的所有结点(值删除)；
?利用最少的空间实现顺序表元素的逆转；
?实现顺序表的各个元素的输出；
?彻底销毁顺序线性表，回收所分配的空间；
?对顺序线性表的所有元素删除，置为空表；
?返回其数据元素个数；
?按序号查找，根据顺序表的特点，可以随机存取，直接可以定位于第i 个结点，查找该元素的值，对查找结果进行返回；
?按值查找，根据给定数据元素的值，只能顺序比较，查找该元素的位置，对查找结果进行返回；
?判断顺序表中是否有元素存在，对判断结果进行返回；
?编写主程序，实现对各不同的算法调用。
2．实现要求：
?“初始化算法”的操作结果：构造一个空的顺序线性表。对顺序表的空间进行动态管理，实现动态分配、回收和增加存储空间；
?“位置插入算法”的初始条件：顺序线性表L 已存在，给定的元素位置为i，且1≤i≤ListLength(L)+1 ；
操作结果：在L 中第i 个位置之前插入新的数据元素e，L 的长度加1；
?“位置删除算法”的初始条件：顺序线性表L 已存在，1≤i≤ListLength(L) ；
操作结果：删除L 的第i 个数据元素，并用e 返回其值，L 的长度减1 ；
?“逆转算法”的初始条件：顺序线性表L 已存在；
操作结果：依次对L 的每个数据元素进行交换，为了使用最少的额外空间，对顺序表的元素进行交换；
?“输出算法”的初始条件：顺序线性表L 已存在；
操作结果：依次对L 的每个数据元素进行输出；
?“销毁算法”初始条件：顺序线性表L 已存在；
操作结果：销毁顺序线性表L；
?“置空表算法”初始条件：顺序线性表L 已存在；
操作结果：将L 重置为空表；
?“求表长算法”初始条件：顺序线性表L 已存在；
操作结果：返回L 中数据元素个数；
?“按序号查找算法”初始条件：顺序线性表L 已存在，元素位置为i，且1≤i≤ListLength(L)
操作结果：返回L 中第i 个数据元素的值
?“按值查找算法”初始条件：顺序线性表L 已存在，元素值为e；
操作结果：返回L 中数据元素值为e 的元素位置；
?“判表空算法”初始条件：顺序线性表L 已存在；
操作结果：若L 为空表，则返回TRUE，否则返回FALSE；
分析: 修改输入数据，预期输出并验证输出的结果，加深对有关算法的理解。
3、实验指导
一个简单程序通常主要由三部分构成：
1、常量定义（#define），类型重定义(typedef)及函数原型(#include)声明；还有针对每一种数据结构的类型定义。
2、算法函数，对于顺序表，每一个函数具有独立的功能，组合成为模块的形式，如ListInit_Sq、ListInsert_Sq、ListDelete_Sq、ListReverse_Sq、ListPrint_Sq 等。
3、主函数（main）。
【说明1】――顺序表的定义与操作
1．可以将这三部分组合在一个文件中，也可以按照项目的方式（多个不同的文件组合在一起，共同完成一个功能）进行组织（本课程的实验强烈推荐这种形式），如将本课程后续所有算法几乎都要使用的常量定义（#define）和系统函数原型定义(#include)声明组合成一个文件，存储为一个头文件（取名为pubuse.h），只需建立一次，以后凡涉及到相关的内容，只需在你的文件的前面加上一条#include “pubuse. h”即可，无需重复输入。
2．对于类型定义，由于每一种数据结构的定义都不一样，因此要进行专门的类型定义，也可以将数据结构的定义组合成为一个文件，存储为一个头文件（如线性表的顺序存储结构定义取名为seqlistDef. h），只需建立一次，以后凡涉及到关于顺序表操作的相关内容，一定要在你的文件的前面加上一条#include“seqlistDef. h”即可，无需重复进行顺序存储结构的定义。
3．关于实验内容要完成的操作，一般都以独立的算法出现，关于某类数据结构的各种不同算法函数组合在一个文件之中，存储为一个头文件（如取名为seqlistAlgo. h），以后凡涉及到要使用本文件中的顺序表算法，一定要在你的文件的前面加上一条#include “seqlistAlgo. h”即可，无需重复定义类似的算法，就象使用系统函数一样，只需进行函数原型的声明即可。
4．还应包含一个main 函数，作为整个程序的执行入口处，定义测试的数据，完成各种算法的调用执行，对算法的执行过程和结果进行判断和输出控制，存储为一个源文件（如取名为seqlistUse. cpp）。
5．为了对实际问题更加通用和适应，在算法中使用的数据类型为ElemType，为了与实际数据类型一致，一般要将ElemType 用typedef 重定义：如实际问题中顺序表的每个元素是整型，则使用typedef int ElemType；定义语句；如实际问题中顺序表的每个元素是单精度实数的话，使用typedef float ElemType；定义语句。
4、基本实验的参考程序
线性表的顺序存储结构的定义及其基本操作的参考程序（顺序表）
(1) 文件1：pubuse.h 是公共使用的常量定义和系统函数调用声明，以后每个实验中几乎都
涉及到此文件。
#include
#include
#include
#include
#include
#include
#include
#include
#include
/* 函数结果状态代码*/
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
/* #define OVERFLOW -2 因为在math. h 中已定义OVERFLOW 的值为3,故去掉此行*/ typedef int Status; /* Status 是函数的类型,其值是函数结果状态代码，如OK 等*/ typedef int Boolean; /* Boolean 是布尔类型,其值是TRUE 或FALSE */
(2) 文件2：seqlistDef.h 进行线性表的动态分配顺序存储结构的表示
#define LIST_INIT_SIZE 10 /* 线性表存储空间的初始分配量*/
#define LISTINCREMENT 2 /* 线性表存储空间的分配增量*/
typedef struct
{
ElemType *elem; /* 存储空间基址*/
int length; /* 当前长度*/
int listsize; /* 当前分配的存储容量(以sizeof(ElemType)为单位) */
}SqList;
(3)文件3：seqlistAlgo.h 进行线性表顺序存储结构的基本实验算法定义
Status ListInit_Sq(SqList &L) /* 算法2. 3 */
{ /* 操作结果：构造一个空的顺序线性表*/
L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
if(!L. elem)
exit(OVERFLOW);/* 存储分配失败*/
L.length=0; /* 空表长度为0 */
L.listsize=LIST_INIT_SIZE; /* 初始存储容量*/
return OK;
}
Status ListInsert_Sq(SqList &L,int i,ElemType e) /* 算法2. 4 */
{ /* 初始条件：顺序线性表L 已存在，1≤i≤ListLength(L)+1 */
/* 操作结果：在L 中第i 个位置之前插入新的数据元素e，L 的长度加1 */
ElemType *newbase,*q,*p;
if(i<1||i>L.length+1) /* i 值不合法*/
return ERROR;
if(L.length>=L.listsize) /* 当前存储空间已满,增加分配*/
{
newbase=(ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType)); if(!newbase)
exit(OVERFLOW); /* 存储分配失败*/
L.elem=newbase; /* 新基址*/
L.listsize+=LISTINCREMENT; /* 增加存储容量*/
}
q=L.elem+i-1; /* q 为插入位置*/
for(p=L.elem+L.length-1;p>=q;--p) /* 插入位置及之后的元素右移*/
*(p+1)=*p;
*q=e;/* 插入e */
++L.length; /* 表长增1 */
return OK;
}
Status ListDelete_Sq(SqList &L,int i,ElemType *e) /* 算法2. 5 */
{ /* 初始条件：顺序线性表L 已存在，1≤i≤ListLength(L) */
/* 操作结果：删除L 的第i 个数据元素，并用e 返回其值，L 的长度减1 */ ElemType *p,*q；
if(i<1||i>L.length) /* i 值不合法*/
return ERROR;
p=L.elem+i-1; /* p 为被删除元素的位置*/
*e=*p; /* 被删除元素的值赋给e */
q=L.elem+L.length-1; /* 表尾元素的位置*/
for(++p;p<=q;++p) /* 被删除元素之后的元素左移*/
*(p-1)=*p;
L.length--; /* 表长减1 */
return OK;
}
Status ListReverse_Sq(SqList &L)
{ /* 初始条件：顺序线性表L 已存在*/
/* 操作结果：依次对L 的数据元素成对交换*/
ElemType t;
int i;
for(i=0;i {t=L.elem[i]; L.elem[i]= L.elem[L.length-i-1]; L.elem[L.length-i-1]=t; } printf("\n"); return OK; } Status ListPrint_Sq(SqList L) { /* 初始条件：顺序线性表L 已存在*/ /* 操作结果：依次对L 的数据元素输出*/ int i; printf("\n"); for(i=0;i printf("%d\n ", L.elem[i]); return OK; } /* 1554 65464 3485452 45684*/ int ListLength_Sq(Sqlist L) {/*初始条件：顺序线性表L 已存在*/ /*操作结果：返回L 中数据元素个数*/ print(“%d”,L.length); return L.length; } Status GetElem_Sq(Sqlist L, int i, &e) /*按序号查找算法*/ {/*初始条件：顺序线性表L 已存在，元素位置为i，且1≤i≤ListLength(L) */ /*操作结果：返回L 中第i 个数据元素的值*/ if ((i<1)||(i>L.length)) return ERROR; else e=L.elem[i]; printf(“%d\n”,e); return e; } Status LocateElem_Sq(Sqlist L, e, compare()) /*按值查找算法*/ {/*初始条件：顺序线性表L 已存在，元素为e */ /*操作结果：返回L 中数据元素值为e 的元素位置*/ int en; int i; for(i=1;i<=L.length;i++) {en=GetElem(Sqlist L, int i, &e); if (!equal(en,e)) countinu; else break; } if (i<=L.length) printf(“%d\n”,i); else return 0; } Stutas ListEmpty_Sq(Sqlist L) {/*初始条件：顺序线性表L 已存在*/ /*操作结果：若L 为空表，则返回TRUE，否则返回FALS*/ int i; for(i=1;i<=L.length;i++) {if (L.elem[i]!=NULL) return FALSE; else return TURE; } } Status ClearList_Sq(Sqlist &L) {/*初始条件：顺序线性表L 已存在*/ /*操作结果：将L 重置为空表*/ int i; for(i=0;i L.elem[i]=NULL; printf (“%d\n”,i-1); ListEmpty_Sq(Sqlist L); } Status DestroyList_Sq(SqList L) {/*初始条件：顺序线性表L 已存在*/ /*操作结果：销毁顺序线性表L*/ int i; for(i=1;i<=L.length;i++) { if (L.elem[i]!=NULL) L.elem[i]=NULL;} free(L); return OK; } (4)文件4：seqlistUse. cpp 进行线性表顺序存储结构的基本算法验证 #include"pubuse.h" /* 实现通用常量的定义，常用系统函数的声明*/ typedef int ElemType; /*实现一组整数的操作,将int 型特定义为通用的ElemType 类型名*/ #include"seqlistDef.h" /* 采用线性表的动态分配顺序存储结构定义*/ #include"seqlistAlgo.h" /* 采用顺序表的基本算法定义*/ void main() { SqList L; Status I; int j; ElemType t; /* 首先一定要初始化顺序表*/ i=ListInit_Sq(L); if(i==1) /* 创建空表L 成功*/ for(j=1;j<=5;j++) /* 在表L 中插入5 个元素，每个元素的值分别为2，4，6，8，10 */ i=ListInsert_Sq(L,j,2*j); ListPrint_Sq(L); /*检验一下插入的结果，输出表L 的内容*/ ListInsert_Sq(L,2,20);/* 随机指定插入点位置，假设在第二个元素前插入新的元素，其值为20 */ ListDelete_Sq(L,4,&t);/* 随机指定删除点位置，假设对第四个元素进行删除*/ printf("\n The Deleted value is %d",t);/* 检验一下删除点元素的值*/ ListPrint_Sq(L);/* 检验一下插入和删除后的结果，输出表La 的内容*/ ListReverse_Sq(L);/* 将顺序表La 的所有元素进行逆序*/ ListPrint_Sq(L);/* 检验一下逆序的结果，输出表L 的内容*/ ListLength_Sq(Sqlist L); GetElem_Sq(Sqlist L, 2, &e); LocateElem_Sq(Sqlist L,8,compare()); ListEmpty_Sq(Sqlist L); ClearList_Sq(Sqlist &L); ListPrint_Sq(L); DestroyList_Sq(SqList L); } 5、实验环境和实验步骤 实验环境：利用Visual C++集成开发环境进行本实验的操作。 实验步骤――顺序表的定义与操作： 1．启动VC++； 2. 新建工程/Win32 Console Application，选择输入位置：如“d:\”，输入工程的名称：如“SeqlistDemo”；按“确定”按钮，选择“An Empty Project”，再按“完成”按钮， 3．新建文件/C/C++ Header File，选中“添加到工程的复选按钮”，输入文件名“pubuse.h”，按“确定”按钮，在显示的代码编辑区内输入如上的参考程序； 4. 新建文件/C/C++ Header File，选中“添加到工程的复选按钮”，输入文件名“seqlistDef.h”，按“确定”按钮，在显示的代码编辑区内输入如上的参考程序； 5. 新建文件/C/C++ Header File，选中“添加到工程的复选按钮”，输入文件名“seqlistAlgo.h”，按“确定”按钮，在显示的代码编辑区内输入如上的参考程序； 6. 新建文件/C++ Source File，选中“添加到工程的复选按钮”，输入文件名“seqlistUse.cpp”，按“确定”按钮，在显示的代码编辑区内输入如上的参考程序； 7．按F7 键，或工具图标进行工程的建立，如有错误，根据错误显示区中的提示，改正错误，重新建立应用程序； 8．按Ctrl+F5 键，或工具图标进行工程的执行。 第二章线性表 一、顺序表和链表的优缺点 1.顺序表 定义：用一组连续的存储单元（地址连续）依次存放线性表的各个数据元素。即：在顺序表中逻辑结构上相邻的数据元素，其物理位置也是相邻的。 优点 逻辑相邻，物理相邻 可随机存取任一元素 存储空间使用紧凑 缺点 插入、删除操作需要移动大量的元素（平均约需移动一半结点，当n很大时，算法的效率较低） 预先分配空间需按最大空间分配，利用不充分 表容量难以扩充 2.链式存储结构 定义：由分别表示a1,a2,…,a i-1,a i,…,a n的N 个结点依次相链构成的链表，称为线性表的链式存储表示 优势： (1)能有效利用存储空间； 动态存储分配的结构，不需预先为线性表分配足够大的空间，而是向系统“随用随取”，在删除元素时可同时释放空间。 (2)用“指针”指示数据元素之间的后继关系，便于进行“插入”、“删除”等操作； 插入或删除时只需要修改指针，而不需要元素移动。 劣势： (1)不能随机存取数据元素； (2)丢失了一些顺序表的长处，如线性表的“表长”和数据元素在线性表中的 “位序”，在单链表中都看不见了。如，不便于在表尾插入元素，需遍历整个表才能找到插入的位置。 二、单链表中删除一个节点和插入一个节点的语句操作，p29 1.插入元素操作 算法基本思想：首先找到相应结点，然后修改相应指针。 假定在a，b之间插入结点X，s指向X, p指向a，指针修改语句为： s->next=p->next; p->next =s; 2.删除元素操作 算法基本思想:首先找到第i-1 个结点，然后修改相应指针。 删除b结点，其中，P指向a，指针修改语句为：p->next=p->next->next； 三、单链表的就地逆置习题集2.22 算法的基本思想：以单链表作存储结构进行就地逆置的正确做法应该是：将原链表的头结点和第一个元素结点断开（令其指针域为空），先构成一个新的空表，然后将原链表中各结点，从第一个结点起，依次插入这个新表的头部（即令每个插入的结点成为新的第一个元素结点）。 算法思路：依次取原链表中的每个结点，将其作为第一个结点插入到新链表中去，指针p用来指向当前结点，p为空时结束。 void reverse (Linklist H){ LNode *p; p=H->next; /*p指向第一个数据结点*/ H->next=NULL; /*将原链表置为空表H*/ while (p){ q=p; p=p->next; q->next=H->next; /*将当前结点插到头结点的后面*/ H->next=q; } } 第三章栈和队列 一、栈和队列的特性 1.特点 栈必须按“后进先出”（LIFO）的规则进行操作，仅限在表尾进行插入和删除的操作。 队列（FIFO）必须按“先进先出”的规则进行操作，队尾插入，队头删除。 二、循环队列为空和满的判定方法，p63 队空条件：front == rear; 队满条件：(rear + 1) % maxSize == front 本人是今年考上广州大学计算机专业的，说真的，专插本这条路并不好走，很辛苦!但是当你知道自己考上了，那感觉是相当激动的！！ 2011年高考成绩揭晓，我就过了3A二分而已，那时候心情很沉重，只有3条路可以选择，第一是复读第二就是读3A尾的学校第三就是去打工，最后的抉择是报了中山火炬技术学院（全省专科不知道是倒数第二还是倒数第三的学校） 2011年九月带着沉重的心情来到了中山火炬技术学院，这学校名气小的可怜，问了N多人都没人知道这学校，学校也小的可怕，十几分钟就可以走完，当时感觉自己很悲剧，上了这样的学校很没面子，因此痛下决心来不管怎么样要往上爬，从一个师兄那里听说可以插本，考到的话第一学历是本科，但是听说插本很难，比高考，考研究生还要难上百倍，便没怎么想插本了，还是专心学好大专的专业吧 一转眼，2年过去了，到了大三，很多同学都去实习了，我又一次走到人生十字路口上，是去工作还是去插本，经过几天考虑还是决定插本了，因为第一我觉的要进好的企业需要本科第二我不想那么快工作，那时候作出插本决定已经是9月底了，中山火炬技术学校插本的人很少，所以只好通过加插本QQ群来了解插本信息 因为本人不想给家庭负担所以没有参加任何培训班，刚开始复习全靠自己摸索着的，很痛苦，哪里是重点哪里不是重点都不知道，幸亏在进群之后知道考纲这回事，慢慢的走上了复习的正规道路，每天8点就起来看书，除开吃饭上厕所什么的离开一下教室其他都是在教室看书，一直看到晚上10点钟，回到宿舍继续看书，因为宿舍没人，所以看到2点左右才睡觉，每个星期抽出半天去放松，这样才能保证效率，那时候备考时候真是很无聊很痛苦，知道不少人都已经放弃了，但是还是坚持到最后，3月去广州考试，看见考广大计算机人400多人，心里有点怕怕的，但是马上调整好心态，心里说怕什么，大不了考不上去工作呢，在考试那2天就浏览一下书本和总结的考点，考完也不去想考试结果，因为没有什么意义了，四月八出成绩了，当时心里发毛了，因为说不担心那是假的，我是先要我舍友帮我查的，她说过了，我还是担心，最后自己鼓起勇气查的，当我点一下鼠标的那一刻眼睛是闭着的，闭了好久才敢看成绩。当时自己惊叫了起来：过了过了，战争终于结束了。自己也没想到会考的这么好，它见证了我几个月的付出是值得的好了，啰嗦了那么多，不知道说了这么多大家看了是什么心情，写的乱七八糟的，不过都是个人真实感受，现在就分享一下我各科复习经验吧 政治 这个是最恶心的科目，我用最多时间来备考这科，因为高中读的是理科，对它不感冒，但是考了67分，虽然不是很高分，但是我已经很满足了，现在谈谈这科复习方法，我10月开始看政治书的，一天一章的看，看到11月，看了大概四次书本，你会问为什么要看书，很简单，因为政治选择题很坑爹，不少题目是书本的，但是考纲没有的，12月开始之后，我就根据录音去划书，整理笔记，然后开始背，每个白天抽3小时背政治，然后晚上回宿舍打开电脑用 1小时选择题，培养做题感觉，到一月中，开始做历年真题，并把考过的大题给划掉，重点背那些没出的，没背熟的反复的背和默写，要是你学我这样做，我想政治可以个满意的分数。 英语 《数据结构》基本概念 基本概念 ?数据 数据是信息的载体，在计算机科学中是指所有能输入到计算机中并能被计算机程序识别和处理的符号集合。 ?数据元素 数据元素也称为结点，是表示数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 ?数据项 数据项是构成数据元素的不可分割的最小单位。?数据对象 数据对象是具有相同性质的数据元素的集合，是数据的子集。 注意：在不产生混淆的情况下，将数据对象简称为数据。 ?数据结构 数据结构是指相互之间存在一定关系的数据元素的集合，即数据结构是一个二元组DataStructure = (D, R)，其中D是数据元素的集合，R是D上关系的集合。按照视点的不同，数据结构分为逻辑结构和存储结构。 ?数据的逻辑结构 数据的逻辑结构是指数据元素之间逻辑关系的整体。 根据数据元素之间逻辑关系的不同，数据结构分为四类： ⑴集合：数据元素之间就是“属于同一个集合”，除此之外，没有任何关系； ⑵线性结构：数据元素之间存在着一对一的线性关系； ⑶树结构：数据元素之间存在着一对多的层次关系； ⑷图结构：数据元素之间存在着多对多的任意关系。 注意：数据结构分为两类：线性结构和非线性结构。?数据的存储结构 数据的存储结构又称为物理结构，是数据及其逻辑结构在计算机中的表示。通常有两种存储结构：顺序存储结构和链接存储结构。 顺序存储结构的基本思想是：用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系是由元素的存储位置来表示的。 链接存储结构的基本思想是：用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系是用指针来表示的。 注意：存储结构除了存储数据元素之外，必须存储数据元素之间的逻辑关系。 ?抽象数据类型 抽象数据类型是一个数据结构以及定义在该结构上 数据结构知识点概括 第一章概论 数据就是指能够被计算机识别、存储和加工处理的信息的载体。 数据元素是数据的基本单位，可以由若干个数据项组成。数据项是具有独立含义的最小标识单位。 数据结构的定义： ·逻辑结构：从逻辑结构上描述数据，独立于计算机。·线性结构：一对一关系。 ·线性结构：多对多关系。 ·存储结构：是逻辑结构用计算机语言的实现。·顺序存储结构：如数组。 ·链式存储结构：如链表。 ·索引存储结构：·稠密索引：每个结点都有索引项。 ·稀疏索引：每组结点都有索引项。 ·散列存储结构：如散列表。 ·数据运算。 ·对数据的操作。定义在逻辑结构上，每种逻辑结构都有一个运算集合。 ·常用的有：检索、插入、删除、更新、排序。 数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。 ·结构类型：由用户借助于描述机制定义，是导出类型。 抽象数据类型ADT：·是抽象数据的组织和与之的操作。相当于在概念层上描述问题。 ·优点是将数据和操作封装在一起实现了信息隐藏。 程序设计的实质是对实际问题选择一种好的数据结构，设计一个好的算法。算法取决于数据结构。 算法是一个良定义的计算过程，以一个或多个值输入，并以一个或多个值输出。 评价算法的好坏的因素：·算法是正确的； ·执行算法的时间； ·执行算法的存储空间（主要是辅助存储空间）； ·算法易于理解、编码、调试。 时间复杂度：是某个算法的时间耗费，它是该算法所求解问题规模n的函数。 渐近时间复杂度：是指当问题规模趋向无穷大时，该算法时间复杂度的数量级。 评价一个算法的时间性能时，主要标准就是算法的渐近时间复杂度。 算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关。 时间复杂度按数量级递增排列依次为：常数阶O（1）、对数阶O（log2n）、线性阶O（n）、线性对数阶O（nlog2n）、平方阶O （n^2）、立方阶O（n^3）、……k次方阶O（n^k）、指数阶O（2^n）。 地图数据简述 地图数据分类 1.地图数据包括各种制图要素的空间位置数据和对应的专题属性数据两大类 2.导航电子地图的数据内容分为四类基本数据 a.道路数据 b.背景数据 c.标记数据 d.索引（POI）数据 电子地图的制作及应用 1.地图数据的采集 车辆采集，步行采集，企业用户，互联网采集，航空摄影测量及卫星影像 2.地图数据的编制生产 数据生产分为导航数据生产和增值数据生产。导航数据生产有几个内容：道路生产，POI 生产，背景生产，图片生产，实时交通，三维城市。 3.数据的应用 车载/前装，无线位置服务，移动导航，互联网位置服务，政府及企业应用 离线地图和在线地图 离线地图：通过wifi或者电脑将需要的地图数据下载到手机内存或者内存卡里面，用户在查看电子地图，不再需要联网，消耗流量加载地图，显示地图。它是针对不好的网络覆盖、连接速度慢、保存数据难、高国外漫游费用等问题的最好解决方案。 在线地图：是指地图服务方根据用户提出的地理信息需求，通过联网自动搜索、为用户提供方便、快捷、准确的所需地图及出行交通指引资讯。 在线、离线地图的优缺点 离线地图的优点：可以在wifi或者用电脑将离线地图下载在手机中，在查看地图时，不需要联网连接，用户在使用地图时，大大减少数据流量的使用。 离线地图的缺点：在离线使用导航过程中，误差比较大；有新的离线包更新时，需要随时更新，如未更新，则地图的准确性和精确性就会降低。 在线地图的优点：地图实时显示，随时更新，显示的地图，线路是地图的最新数据。 在线地图的缺点：在使用地图过程中，需要随时联网，走流量；在网络状况差的情况，地图显示比较慢，甚至不能正常显示。 数据结构,专科 一、简答题（ 1、假设一个有向图的顶点集合V={c1,c2,c3,c4,c5},弧集 S={ h f c / / \ d k g 后序是hdfbkgcea 3、已知关键字序列{70，83，100，65，10，9，7，32}，现对其 从小到大排序，写出快速排序每一趟结束时的关键字状态。 答#include 譬如第一次结果就是70，83，100，65，10，32，7，9 70比83小，所以位置没变。。 4、设s="I AM A WORKER"，t=" GOOD"，q=" WORKER"。求： StrLength(s)，StrLength(t) ，SubString(s,8,6) ， Index(s,q,1) 。 答：strlength(s)=14；strlength(t)=4；substr(s,8,6)=worker；substr(s,q,1)=o; 5、在单链表中设置头结点有什么作用？ 答：头结点就是在单链表的开始结点之前附加的一个结点，设置头结点的优点有两个：（1）由于开始结点的位置被存放在头结点的指针域中，所以在链表的第一个位置上的操作就和在表的其他位置上一样，无须进行其他特殊处理；（2）无论链表是否为空，其头指针是指向头结点的非空指针（空表中头结点的指针域空），因此空表和非空表的处理也就一样了。 6、设哈希函数H(key)=key MOD 13,用线性探测再散列法解决 冲突。对关键字序列{ 55，19，01，68，23，27，20，84 } 在地址空间为0-10的散列区中建哈希表，画出此表，并求等 概率情况下查找成功时的平均查找长度。 /** *名词解释1、数据：是信息的载体，能够被计算机识别、存储和加工处理。 *2、数据元素：是数据的基本单位，也称为元素、结点、顶点、记录。一个数据元素可以由若干个数据项组成，数据项是具有独立含义的最小标识单位。 *3、数据结构：指的是数据及数据之间的相互关系，即数据的组织形式，它包括数据的逻辑结构、数据的存储结构和数据的运算三个方面的内容。 *4、数据的逻辑结构：指数据元素之间的逻辑关系，即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。 *5、数据的存储结构：指数据元素及其关系在计算机存储器内的表示。是数据的逻辑结构用计算机语言的实现，是依赖于计算机语言的。 *6、线性结构：其逻辑特征为，若结构是非空集，则有且仅有一个开始结点和一个终端结点，并且其余每个结点只有一个直接前趋和一个直接后继。 *7、非线性结构：其逻辑特征为一个结点可能有多个直接前趋和直接后继。 *8、算法：是任意一个良定义的计算过程，它以一个或多个值作为输入，并产生一个或多个值作为输出；即一个算法是一系列将输入转换为输出的计算步骤。 *9、算法的时间复杂度T(n)：是该算法的时间耗费，它是该算法所求解问题规模n趋向无穷大时，我们把时间复杂度T(n)的数量级（阶）称为算法的渐近时间复杂度。 *10、最坏和平均时间复杂度：由于算法中语句的频度不仅与问题规模n有关，还与输入实例等因素有关；这时可用最坏情况下时间复杂度作为算法的时间复杂度。而平均时间复杂度是指所有的输入实例均以等概率出现的情况下，算法的期望运行时间。 *11、数据的运算：指对数据施加的操作。数据的运算是定义在数据的逻辑结构上的，而实现是要在存储结构上进行。 *12、线性表：由n(n≥0)个结点组成的有限序列。其逻辑特征反映了结点间一对一的关系（一个结点对应一个直接后继，除终端结点外；或一个结点对应一个直接前趋，除开始结点外），这是一种线性结构。 *13、顺序表：顺序存储的线性表，它是一种随机存取结构。通过将相邻结点存放在相邻物理位置上来反映结点间逻辑关系。 *14、单链表：每个结点有两个域：一个值域data；另一个指针域next，用来指向该结点的直接后继结点。头指针是它的充分必要的信息。单链表是一种单向的结构。 *15、双链表：每个结点中增加了一个prior，用来指向该点的直接前趋结点。它是一种双向、对称的结构。 *16、循环链表：是一种首尾相接的链表。单循环链表形成一个next链环，而双循环链表形成next链环和prior链环。 *17、存储密度：是指结点数据本身所占的存储量和整个结点结构所占的存储量之比。顺序表的存储密度为1，而链表的存储密度小于1。 *18、栈：只允许在一端进行插入、删除运算的线性表，称为“栈”（stack）。 *19、LIFO表：即后进先出表，修改操作按后进先出的原则进行。譬如栈就是一种LIFO 表。 *20、顺序栈：采用顺序存储结构的栈，称为顺序栈。 *21、链栈：采用链式存储结构的栈，称为链栈。 *22、队列：只允许在一端进行插入、另一端进行删除运算的线性表，称为“队列”（queue）。*23、FIFO表：即先进先出表。譬如队列就是一种FIFO表。 *24、顺序队列：采用顺序存储结构的队列，称为顺序队列。 *25、循环队列：为克服顺序队列中假上溢现象，将向量空间想象为一个首尾相接的圆环， 专升本《数据结构》 一、（共75题,共150分） 1. 数据的基本单位是（）。（2分） A.数据元素 B.记录 C.数据对象 D.数据项 .标准答案：A 2. （）是数据的不可分割的最小单位。（2分） A.数据对象 B.数据元素 C.数据类型 D.数据项 .标准答案：D 3. 算法的空间复杂度是对算法（）的度量。（2分） A.时间效率 B.空间效率 C.可读性 D.健壮性 .标准答案：B 4. （）是限制了数据元素的内部结构仅为一个字符的线性表。（2分） A.栈 B.队列 C.串 D.数组 .标准答案：B 5. 串的长度是指串中所含（）的个数。（2分） A.不同字符 B.不同字母 C.相同字符 D.所有字符 .标准答案：D 6. 采用带头结点双向链表存储的线性表，在删除一个元素时，需要修改指针（）次。（2分） A.1 B.2 C.3 D.4 .标准答案：B 7. 线性表的顺序存储结构是一种（）的存储结构。（2分） A.顺序存取 B.随机存取 C.索引存取 D.Hash存取 .标准答案：B 8. 数组a[1..m]采用顺序存储，a[1]和a[m]地址分别为1024和1150，每个元素占2字节，则m是（）。（2分） A.64 B.32 C.16 D.8 .标准答案：A 9. 深度为h的二叉树，第h层最多有（）个结点。（2分） A.h B.2h-1 C.2h-1 D.2h .标准答案：C 10. m个结点的二叉树，其对应的二叉链表共有（）个非空链域。（2分） A.m B.m+1 C.2m D.m-1 .标准答案：B 11. 下面叙述错误的是（）。（2分） A.顺序表是借助物理单元相邻表示数据元素之间的逻辑关系 B.对于空队列进行出队操作过程中发生下溢现象 C.有向图的邻接矩阵一定是对称的 D.具有相同的叶子个数和具有相同的叶子权值的赫夫曼树不是唯一的 .标准答案：C 12. 以下与数据的存储结构无关的术语是（）。（2分） A.循环队列 B.双向链表 C.哈希表 D.数组 .标准答案：D 13. 在一个长度为n的链式栈中出栈实现算法的时间复杂度为（）。（2分） A.O(1) B.O(log n) C.O(n) D.O(n2) .标准答案：A 14. 在具有k个度数为2的二叉树中，必有（）个叶子结点。（2分） A.k B.k-1 C.2k D.k+1 .标准答案：D 15. 在关键字序列（10,20,30,40,50）中，采用折半法查找20，关键字之间比较需要（）次。（2分） A.1 B.2 C.3 D.4 .标准答案：C 16. 16某二叉树的后序遍历序列和和中序遍历序列均为abcd，该二叉树的前序遍历序列是（）。（2分） A.abcd B.dcba C.acbd D.dbca .标准答案：B 17. n个顶点的无向连通图的生成树，至少有（）个边。（2分） A.n(n-1) B.n(n-1)/2 C.2n D.n-1 .标准答案：D 18. 可以采用（）这种数据结构，实现二叉树的层次遍历运算。（2分） A.队列 B.树 C.栈 D.集合 .标准答案：A 国家地理信息公共服务平台 公共地理框架数据—————————————————————— 电子地图数据规范 （试行稿-20100921版） 国家地理信息公共服务平台总体技术组 目录 前言 (3) 1.范围 (4) 2.引用标准 (4) 3.电子地图数据的定义 (4) 4.电子地图数据的数学基础 (4) 5.电子地图数据集定义 (4) 5.1.矢量数据集 (5) 5.1.1.基础专业级 (5) 5.1.2.政务应用级 (5) 5.1.3.影像标记级 (5) 5.2.影像数据集 (7) 6.地图瓦片定义 (7) 6.1.瓦片规则 (8) 6.2.瓦片数据格式 (8) 6.3.金字塔规则 (8) 6.4.瓦片文件组织 (9) 7.地图表达定义 (10) 附录A（资料性附录）要素内容选取 (11) 附录B（资料性附录）符号与注记 (16) 参考资料 (68) 前言 为应对国家信息化环境中政府部门和社会大众对地理信息在线服务的迫切需求，国家测绘局做出了建设国家地理信息公共服务平台（以下简称“公共服务平台”）的战略性决策。“公共服务平台”由数据层、服务层和运行支持层组成。其中数据层是“公共服务平台”的建设重点之一，其主体内容是公共地理框架数据，包括地理实体数据、电子地图数据、地名地址数据、影像数据与高程数据。 本规范由国家测绘局地理信息与地图司提出。 本规范起草单位：国家基础地理信息中心 1.范围 本规范规定了公共地理框架数据中电子地图数据的定义、分级内容组合方案、地图瓦片制作及在线发布显示设定要求、地图表达符号与注记等。 2.引用标准 GB/T 13923-2006 《基础地理信息要素分类与代码》 3.电子地图数据的定义 电子地图数据是针对在线浏览和专题标图的需要，对矢量数据、影像数据进行内容选取组合所形成的数据集，经符号化处理、图面整饰、分级缓存后形成重点突出、色彩协调、符号形象、图面美观的视屏显示地图。 电子地图数据类型包括线划地图与影像地图两类。线划地图以矢量基础地形要素数据为主要数据源，经过数据分级与可视化设置而成；影像地图以航空、航天遥感影像为基础，并配以矢量线划和适量注记。 除此之外，数据生产者可根据其实际情况与需求制作扩展电子地图，如各类旅游图、人口图、房地产图等。 4.电子地图数据的数学基础 （1）坐标系统：2000国家大地坐标系（CGCS2000）。 （2）坐标单位：度。 5.电子地图数据集定义 构成线划地图与影像地图的矢量及影像数据需要针对在线显示的要求进行 本科插班生考试大纲《数据结构与算法》 《数据结构与算法》专业课程考试大纲 考试科目名称：数据结构与算法 一、考试性质 普通高等学校本科插班生招生考试是由专科毕业生参加的选拔性考试。高等学校根据考生的成绩，按已确定的招生计划，德、智、体全面衡量，择优录取。该考生所包含的内容将大致稳定，试题形式多种，具有对学生把握本课程程度的较强识别、区分能力。 二.考试内容及要求 一、考试基本要求 通过数据结构与算法理论的学习，使学生学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及相应的算法，并初步了解对算法的时间分析和空间分析技术；配合算法设计和上机实践的训练，还应培养学生的数据抽象能力和程序设计的能力，对理论和实践的操作使学生得到全面的领会和深刻的认识。 二、考核知识点及考核要求 本大纲的考核中，按照“识记”、“领会”、“简单应用”和“综合应用”等四个层次规定应达到的能力层次要求。各能力层次为递进等级关系，后者必须建立在前者的基础上，其含义是： 识记：要求考生知道有关的名词、概念、原理、知识的含义，并能正确认识或识别。 领会：要求在识记的基础上，能把握相关的基本概念、基本原理和基本方法，掌握有关概念、原理、方法的区别与联系。 简单应用：要求在领会的基础上，运用所掌握的基本概念、基本原理和基本方法中的少量知识点，分析和解决一般的理论问题或实际问题。 综合应用：要求在简单应用的基础上，运用学过的多个知识点，综合分析和解决比较复杂的实际问题。 第1章绪论 一、考核知识点 1、数据结构的基本概念 2、抽象数据类型的表示和实现 3、算法的概念和特性 4、算法时间复杂度和空间复杂度分析 二、考核要求 1、识记 （1）数据结构的研究内容 2、领会 （1）抽象数据类型的表示和实现 （2）算法的定义和特性 （3）评价算法优劣的基本标准 3、简单应用 （1）简单数据结构的程序设计 （2）简单数据结构程序的时间复杂度和空间复杂度分析 4、综合应用 （1）数据结构的一些基本概念 （2）算法的时间复杂度分析 第2章线性表 一、考核知识点 1、线性表的类型定义 2、线性表的顺序表示和实现 3、线性表的链式表示和实现 4、线性表的应用 电子地图数据处理及配图流程 一，数据处理 数据处理主要有数据提取、数据格式转换、数据组织重构、分类代码转化、数据实体处理 其中基础的数据有河流编码数据、综合电子地图数据，实体化处理政区、 境界、道路、铁路、河流、地名 由于数据是分比例尺等级显示的，13级的肯定比12级的显示的数据多， 所以数据还要增加属性字段，将每一层要显示的地物等要素 二，配图说明 如果有字体首先安装字体和插件，在arcgis9.3版本环境以上，开启maplax lable engine功能（标注用） 将数据添加进来，分析数据各层的内容，结合各层数据的内容，进行分类，并且将要素名称标上，如图 没有字体要设计符号，按照行业标准地理信息公共服务平台电子地图规范最新版本上面的符号说明，结合自己数据的要素内容，设计符号，如果规范中没有的， 可以自己做，但是要和规范的颜色及风格保持协调。 1，点状符号， 符号设计，可以通过photoshop或画板按照电子地图符号规定的比例做出符号，bmp格式，可以直接作图片符号，或者导入字体符号库中 符号使用，数据分类后，就可以使用字体符号或图片，按照规范给出符号的大小和颜色 2，线状符号，将数据按照clasid分类，挨个按照标准设计，其中注意的是道路的交叉口的处理，道路边线最先显示，等级低的道路最先显示 3，面状符号，按照标准设计，品字型铺面的符号可以利用前面设计的点状符号，图片符号或者字体符号 4，注记，已经装上maplex后，注记就可以按照自己给的方向属性字段或者按照一般的成图的规则避让地物等要素，库外子和生僻字选择过滤掉 过滤要素工具在数据层上面右键，properties,然后defintion query,然后query builder,选择你需要过滤得要素 避让规则 广东技术师范学院 《计算机科学技术导论》（本科插班生入学考试）考试大纲 （计算机科学学院制定） 一、考试性质与试题命题的原则 《计算机科学技术导论》是广东技术师范学院为计算机科学与技术等专业的本科 插班生入学考试所设置的一个专业课考试科目。它的评价标准是高等学校计算机类专 业高职高专毕业生或相近专业毕业生能达到的及格或及格以上水平，以保证录取的本 科插班生具有一定的计算机科学基础理论及必要的专业技能能力，以利于择优选拔。 考试对象为参加教育部面向全面招生的本科插班生入学考试的高职高专毕业生以及 具有同等学历的报考人员。 《计算机科学技术导论》课程考试的目的和要求是：准确、简明地考核考生对计算机科学体系框架、计算机科学基本知识以及现代计算机发展方向、主要理论和科学方法的掌握和理解水平，衡量他们在理解、掌握和运用这些基本专业理论和知识的基础上，观察、分析和解决技术问题的能力。 二、考试形式及试卷结构 1.考试形式为闭卷、笔试；考试时间为120分钟，试卷满分为100分。 2、试题命制的原则：作为一项选拔性考试，《计算机科学技术导论》考试试题在设计上应具有较高的信度和效度、必要的区分度和合理的难度。命题根据本大纲规定的考试目标和考核内容，考试命题应具有一定的覆盖面且重点突出，侧重考核考生对本学科的基本理论、基本知识和基本技能的掌握程度，以及运用所学的知识解决实际问题的能力。 3.试题对不同能力层次要求的分数比例：识记25%、理解55%，综合应用15%，其他5%。 4.合理安排试题的难度结构。试题难易度分为易、较易、较难、难四个等级。试卷中难易度试题的分布比例，易约占25%，较易约占35%，较难约占20%，难约占10%。 5.试卷的题型有：单项选择题、多项选择题、简答题、改错题、计算题、填空题、综合题等。可根据考核要求，适当安排各种题型数量的比例，达到考核对知识点的识记、理解以及运用水平和能力。 (1) The Linked List is designed for conveniently b data item. a. getting b. inserting c. finding d.locating (2) Assume a sequence list as 1,2,3,4,5,6 passes a stack, an impossible output sequence list Is c . a. 2,4,3,5,1,6 b.3,2,5,6,4,1 c.1,5,4,6,2,3 d.4,5,3,6,2,1 (3) A queue is a structure not implementing b . a. first-in/first-out b. first-in/last-out c. last-in/last-out d. first-come/first-serve (4) Removing the data item at index i from a sequential list with n items, d items need to be shifted left one position. a. n-i b. n-i+1 c. i d. n-i-1 (5) There is an algorithm with inserting an item to a ordered SeqList and still keeping the SeqList ordered. The computational efficiency of this inserting algorithm is c . a. O(log2n) b. O(1) c. O(n) d.(n2) (6) The addresses which store Linked List d . a. must be sequential b. must be partly sequential c. must be no sequential d. can be sequential or discontiguous (7) According the definition of Binary Tree, there will be b different Binary Trees with 5 nodes. a. 6 b. 5 c. 4 d. 3 (8) In the following 4 Binary Trees, c is not the complete Binary Tree. a b c d (9) A Binary Tree will have a nodes on its level i at most. a.2i b. 2i c.2i+1 d.2i-1 (10) If the Binary Tree T2 is transformed from the Tree T1, then the postorder of T1 is the b of T2. a. preorder b. inorder c. postorder d. level order (11) In the following sorting algorithm, c is an unstable algorithm. a. the insertion sort b. the bubble sort c. quicksort d. mergesort (12) Assume there is a ordered list consisting of 100 data items, using binary search to find a special item, the maximum comparisons is d . a. 25 b.1 c. 10 d.7 (13) The result from scanning a Binary Search Tree in inorder traversal is in c order. a. descending or ascending b. descending c. ascending d. out of order (14) The d case is worst for quicksort. a. the data which will be sorted is too larger. b. there are many same item in the data which will be sorted . c. the data will be sorted is out of order d. the data will be sorted is already in a sequential order. (15) In a Binary Tree with n nodes, there is a non-empty pointers. a. n-1 b. n+1 c. 2n-1 d.2n+1 (16) In a undirected graph with n vertexs, the maximum edges is b . a. n(n+1)/2 b. n(n-1)/2 c. n(n-1) d.n2 (17) The priority queue is a structure implementing c . a. inserting item only at the rear of the priority queue. 韩山师范学院2019年本科插班生招生考试 计算机科学与技术 专业 数据结构 试卷（A 卷） 一、单项选择题（每题2分，共30分） 1. 由3个结点可以构造出多少种不同的二叉树？（ ） A ．2 B ．3 C ．4 D ．5 2. 一个栈的输入序列为A B C ，则下列序列中不可能是栈的输出序列的是( )。 A. B C A B.C B A C. C A B D. A B C 3. 算法的时间复杂度取决于（ ） 。 A ．问题的规模 B ．待处理数据的初态 C ．计算机的配置 D ．A 和B 4. 数组的逻辑结构不同于下列（ ）的逻辑结构。 A. 树 B. 栈 C. 队列 D. 线性表 5. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动的元素个数为（ ）。 A ．8 B ．63.5 C ．63 D ．7 6. 用邻接表表示图进行深度优先遍历时，通常借助（ ）来实现算法。 A ．队列 B. 栈 C. 树 D ．图 7. 数据的最小单位是（ ）。 A.数据元素 B.数据项 C.数据类型 D. 数据变量 8. 设无向图G中有n个顶点，则该无向图的最小生成树上有（） 条边。 A. 2n B. 2n-1 C. n-1 D. n 9. 为解决计算机主机与打印机间速度不匹配问题，通常设一个打印数据缓冲区。主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（）。 A.栈 B.队列 C.线性表 D.有序表 10. 程序段s=i=0；do {i=i+1； s=s+i；}while(i<=n)；的时间复杂 度为（）。 n) C.O(n2) D.O(n3/2) A. O(n) B. O(nlog 2 11.设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为（）。 A. q=p->next；p->next=q->next；free(q)； B. q=p->next；p->data=q->data；free(q)； C. q=p->next；p->data=q->data；p->next=q->next；free(q)； D. q=p->next；q->data=p->data；p->next=q->next；free(q)； 12. 顺序表中第一个元素的存储地址是100，每个元素的长度为2，则 第15个元素的地址是（）。 A.110 B.108 C.100 D.128 13. 一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（）。 A．所有的结点均无左孩子 B．所有的结点均无右孩子 C．只有一个叶子结点 D．是任意一棵二叉树 14. 具有n个顶点的有向图最多有（）条边。 A．n B．n2 C．n(n+1) D．n(n-1) 15. 设用邻接矩阵A表示有向图G的存储结构，则有向图G中顶点i 的入度为（）。 A.第i行非0元素的个数之和 B. 第i列非0元素的个数之和 C.第i行0元素的个数之和 D. 第i列0元素的个数之和 1、单选题（共 20 道试题，共 100 分。）得分：100 1. 把一棵树转换为二叉树后，这棵二叉树的形态是（）。 A. 唯一的 2. 排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行 比较，将其放入已排序序列的正确位置上的方法，称为（）。 A. 希尔排序 C. 插入排序 3. 对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是（）。 D. n的平方 4. 设哈希表长m=14，哈希函数H(key)=key%11。表中已有4个结点：addr (15)=4;addr (38)=5;addr (61)=6;addr (84)=7，如用二次探测再散列处理冲突，关键字为49的结点的地址 是（）。 D. 9 5. 树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把由树转化得到的二叉树叫做这棵数对应的二叉树。结论（）是正确的。 A. 树的先根遍历序列与其对应的二叉树的先序遍历序列相同 6. 排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的 一端的方法，称为（）。 A. 希尔排序 7. 用某种排序方法对线性表（25，84，21，47，15，27，68，35，20）进行排序时，元素序列的变化情况如下：⑴25，84，21，47，15，27，68，35，20；⑵20，15，21，25，47，27，68，35，84；⑶15，20，21，25，35，27，47，68，84；⑷15，20，21，25，27，35， 47，68，84。则所采用的排序方法是（）。 D. 快速排序 8. 对于一个有向图，若一个顶点的入度为k1,、出度为k2，则对应逆邻接表中该顶点单链表中的结点数为（）。 A. k1 9. 用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印出相应的顶点，则输 出的顶点序列是（）。 A. 逆拓朴有序的 《数据结构》考试大纲 I 考试的性质与目的 本科插班生考试是由专科毕业生参加的选拔性考试。《数据结构》是计算机科学与技术专业（本科）的一门专业基础课程，考试主要检查考生对常用基本数据结构（顺序表、链表、栈、队列、树、二叉树、图等）的逻辑结构、存储结构和相应算法的掌握程度，以保证后续课程的学习。 II 考试的内容 一、考试基本要求 1、基本理论知识 （l）、数据结构的基本概念和基本术语，算法的描述方法和算法分析的基本概念。 （2）、线性表的基本概念、线性表的基本操作以及这些操作分别在顺序存储和链式存储结构下的实现及复杂度分析。 （3）、栈和队列的定义、存储结构、实现和典型应用。 （4）、串的定义及其基本操作。 （5）、数组的定义、运算和顺序存储。 （6）、树的定义、基本术语和存储结构，二叉树的定义和性质、二叉树的存储结构及其各种操作，哈夫曼树的概念和应用。 （7）、图的定义和术语、图的存储结构及其各种操作。 （8）、各种查找方法的算法、适用范围及时间复杂度的分析。 （9）、多种内排算法的基本思想和算法的时间复杂度分析，不同排序方法的比较。 2、基本技能 （1）、能阅读用类C语言编写的算法。 （2）、能分析算法所完成的功能、运行结果和时间复杂度。 （3）、能根据要求用类C语言编写算法。 二、考核知识点及考核要求 第一章绪论 一、考核知识点 1.数据、数据元素、数据项、数据对象、数据结构、逻辑结构、物理结构、元素、结点等基本概念。抽象数据类型的定义、表示和实现方法。 2.算法、算法的特性、如何用类C语言来描述算法。 3.算法设计的基本要求以及计算语句频度和估算算法时间复杂度的方法。 二、考核要求 1.识记：有关数据结构的基本概念，四种基本数据结构的特点。 2.理解：四种基本数据结构的基本运算，算法复杂度度量的基本概念。 3.应用：用类C语言描述算法 数据结构 一、单项选择题 1．数据的最小单位是_A___。 A．数据元素 B.记录 C.数据对象 D.数据项 2. 对于一个具有n个结点和e条边的无向图，若采用邻接表表 示，所有边链表中边结点的总数为__C__。 A. e/2 B.e C.2e D.n+e 3. 数组a[1..6,1..5] （无0行0列）以列序为主序顺序存储， a[1][1]的地址为1000，每个元素占2个存储单元，则a[3][4]的地址是___A_。 A.1026 B.1040 C.1042 D.1046 4.某线性表常发生的操作为删除第一个数据元素和在最后一个 元素后添加新元素，采用__D__的存储结构，能使其存储效率和时间效率最高。 A．单链表B．仅用头指针的循环链表C．双向循环链表D．仅用尾指针的循环链表 5. 在一个单链表中，已知q所指向的结点是p指向的结点的直接 前驱结点，若在q所指向的结点和p指向的结点间插入s所指向的结点，则执行 C ___ 。 A. s->next=p->next; p->next=s; B. p->next=s->next; s->next=p; C. q->next=s; s->next=p; D. p->next=s; s->next=q; 6. 若循环队列使用C数组A[m]存放其数据元素，已知头指针 front指向队首元素，尾指针rear指向尾元素后的空单元，则当前队列中的元素个数为___A_。 A.(rear-front+m)%m B. rear-front+1 C. rear-front D. rear-front-1 7. 栈和队列的共同点是___C_。 A.先进先出 B. 后进先出 C.只允许在端点处插入和删除元素 D. 运算受限的线性表数据结构整理完整版
广州大学专插本心得
《数据结构》基本概念
(完整版)非常实用的数据结构知识点总结
电子地图数据简述
《数据结构》(专科)已完成
数据结构基础知识大全
专升本《数据结构》_试卷_答案
国家公共地理框架数据电子地图数据规范 试行稿 版
2017年中山大学南方学院专插本《数据结构与算法》考试大纲
电子地图数据处理及配图流程
广东技术师范学院2018年专插本《计算机科学技术导论》考试大纲
数据结构
2019年本科插班生考试试题《数据结构》A试卷
数据结构
2019广东专插本韩山师范学院《数据结构》考试大纲
数据结构
相关主题
文本预览