第一章绪论
考点1 数据结构基础知识
1.数据的逻辑结构是指（），数据的存储结构是指（）
分析：数据结构包括三方面的内容：数据的逻辑结构、存储结构和数据
的运算。其中，逻辑结构是指各数据元素之间的逻辑关系，存储结构是
指逻辑结构用计算机语言的实现。
解答：数据元素之间的逻辑关系；数据的逻辑结构用计算机语言的实现。
2.在数据结构中，从逻辑上可以把数据结构分为：（A）
A 线性和非线性结构
B 紧凑和非紧凑结构
C 动态和静态结构
D 内部和外部结构
分析：数据结构中，逻辑上可以把数据结构分成线性结构和非线性结构。
线性结构的顺序存储结构是一种随机存取的存储结构，线性表的链式
存储结构是一种顺序存储结构。线性表若采用链式存储表示时，所有
结点之间的存储单元地址可连续可不连续。逻辑结构与数据元素本身
的形式、内容、相对位置、所含结点个数无关。
关键考点点评：线性结构的特征，有且仅有一个开始结点和终端结点，
所有结点最多只有一个直接前驱和后继。栈和队列。非线性结构的结
点有多个前驱或后继，树和图。
3.数据结构在物理上可以分为（）存储结构和链式存储结构。
分析：物理存储
解答：顺序
4.下列术语中，（）与数据的存储结构无关
A 循环队列
B 堆栈
C 散列表
D 单链表
解答： A
5.（）不是算法所必须具备的特性
A 有穷性
B 确定性
C 高效性
D 可行性
分析：算法的五个重要特征：有穷性、确定性、可行性、输入和输出。
解答：C
考点2 时间复杂度计算
1.设n是描述问题规模的非负整数，下面程序段的时间复杂度是（）
2.
第二章线性表
考点1 线性表的基本概念
1.线性表是n个（）的有限序列。
A 字符B数据元素 C 由数据项 D 信息项
解析：
解答 B
2.线性表是一个（）。
A 有限序列，可以为空
B 有限序列，不能为空
C 无限序列，可以为空
D 无限序列，不能为空
解答 A
关键考点点评：
对于非空线性表
1.有且仅有一个开始结点，没有直接前驱，有且仅有一个直接后继；
2.有且仅有一个终结结点，没有直接后继，有且仅有一个直接前驱；
3.其余的内部结点都有且仅有一个直接前驱和后继
3.单链表不能随机存取元素原因是：要得到元素的存储地址，必须（）
解答：从起始结点开始扫描以得到其地址
注：顺序表可以，但是链表不行
考点2 线性表的顺序存储结构
1.下述（）是顺序存储结构的优点
A 插入运算方便
B 可方便地用于各种逻辑结构的存储表示
C 存储密度大
D 删除运算方便
解答： C
2.线性表的（）存储结构是随机存储结构。
分析：随机存储结构代表可以直接访问其中的任意一个元素。
解答：顺序
关键考点点评：
顺序存储：把线性表的结点按逻辑次序依次存放在一组地址连续的存储单元里。一般可以用数组实现。
3.设线性表有n个元素，以下操作中，（）在顺序表上实现比在链表上实
现效率更高
A 输出第i个元素值
B 交换第一个第二个元素的值
C 顺序输出所有元素
D 输出与给定值x相等的元素在线性表中的
序号
解答：A
4.若某线性表最常用的操作是存取任意指定序号的元素和最后进行插入
和删除运算，则利用（）存储方式最节省时间。
A 顺序表
B 双链表
C 带头结点的双循环链表
D 单循环链表
解答：A
5.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新
元素的算法的时间复杂度是（）
A O（0）
B O（1）
C O（n）
D O（n*n）
分析：
6.顺序表的插入算法中，当n个空间已满时，可申请再增加分配m个空
间。若申请失败，则说明系统没有（）可分配的存储空间。
A m个
B m个连续的
C n+m个
D n+m个连续的
解答：D
7.简述线性表的顺序存储和链式存储的特点的比较
8.对于顺序存储的线性表，设其长度为n，在任何位置上插入或删除都
是等概率的。插入一个元素时大约要移动表中（）元素。
A n/2
B (n+1)/2
C (n-1)/2
D n
解答 A
9.设顺序表的长度为n，并设从表中删除元素的概率相等。则在平均情
况下，从表中删除一个元素需要移动的元素个数是（）
A (n-1)/2
B n/2
C n(n-1)/2
D n(n+1)/2
解答 A
10.在n个结点的线性表的数组实现中，算法的时间复杂性是O(1)的操作
是：
A 访问第i个结点（1<=i<=n）和求第i个结点的直接前驱(2<=i<=n)
B 在第i个结点后插入一个新的结点（1<=i<=n）
C 删除第i个结点（1<=i<=n）
D以上都不对
解答：A
11.顺序存储的线性表A，其数据元素为整型，编写算法，将A拆成B和
C两个表，使A中元素值大于等于0的存入B，小于0存入C。
要求：（1）表B和C另外设置存储空间。
（2）B和C不另外设置，而利用A的空间。
考点3 线性表的链式存储结构
1.以下关于链式存储结构的叙述，（）是不正确的。
A 结点除自身信息外还包括指针域，因此存储密度小于顺序结构
B 逻辑上相邻的结点物理上不必相邻
C 可以通过计算直接确定i个结点的存储位置
D插入删除操作方便，不必移动结点
解答：C
2.链表不具备的特点是（）
A 可随机访问任一个元素
B 插入和删除时不需要移动元素
C 不必事先估计存储空间
D 所需空间与线性表长度成正比
分析：A是顺序表的特点，链表的元素不可以直接随机访问，一般是从链表的起始位置依次搜索得到
答案：A
3.线性表可用顺序表或者链表存储，它们有什么优缺点？如果有n
个表同时并存，并且在处理过程中各表的长度会动态发生变化，表得到总数也可能自动改变，在这种情况下应该选用哪种存储表示
分析：
考点4 单链表及其基本操作
1.对链表设置表头结点的作用是什么
解答：一般来说，设置表头结点的目的是统一空表与非空表的操作，简化链表操作的实现，而且，头结点也可以用来存储一些链表的基本信息，如链表长度等。
2.对给定的n个元素，建立一个有序单链表的时间复杂度是：
分析：在不申请额外存储空间的前提下，建立一个n元素的有序单链表是时间复杂度是O(n*n)，因为对任意一个元素，插入单链表中合适位置的开销是O(n)，对n个元素则是O(n*n)
3.将长度为n的单链表接在长度为m的单链表之后的算法的时间复杂度
是：
分析：由于将长度为n的单链表连接在长度为m的单链表之后的操作，需要把长度为m的单链表遍历一遍，找到最后一个结点，所以时间复杂度我O(m)
4.设计一个算法int increase(LinkList *L)，判定带头结点单链表L是否是递
增的，若是返回1，否则返回0.
5.有一个无头结点的单链表，结点有数据域data，指针域next，表头指
针为h，通过遍历链表，将链表中所有的链表方向逆转。要求逆转后的链表的表头指针h指向原链表的最后一个结点。算法如下请填空。
关键考点点评：
6.在一个单链表中，若删除p所指结点的后继结点，则执行：
答案：A
7.在单向链表中p结点的后面插入新结点s，应执行语句：
答案：s->next=p->next;p->next=s
8.
9.已知线性表中的元素以值递增有序排列，并以单链表作为存储结构。
编写算法，删除表中所有值相同的元素，同时释放被删除的结点空间。
10.设有序表以带头结点的单链表存储。请设计一个函数，实现在该表内
插入一个新元素的操作。要求插入后，仍为有序表。假定每个结点有两个域，element和link，元素为整型，link具有指向后继结点的指针类型，要求使用类型说明定义单链表结构，并实现函数。
11.编写逆向输出的不带头结点的单向链表中数据域的递归算法。设表中
有四个结点，从表头至表尾其数据域分别为10,30,20,40作图表示出该算法的执行过程。设该链表的结点的数据类型名称为list，结点的数据域和指针域的名称分别是data和next，不必写出list的定义
考点5 循环链表及其基本操作
1.某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除
第一个元素，则采用（）存储方式最节省运算时间
A 非循环的单链表
B 仅有头指针的单循环链表
C 非循环的双链表
D 仅有尾指针的单循环链表
答案：D
2.有一个含头结点的单循环链表，头指针为head，则判断其是否为空的
条件是：
答案：head->next==head
3.设线性表非空，采用下列（）所描述的链表可以在O（1）时间内在表
尾插入一个新结点。
A 带表头结点的单链表，一个链表指针指向表头结点
B 带表头结点的单循环链表，一个链表指针指向表头结点
C 不带表头结点的单链表，一个链表指针指向表的第一个结点
D 不带表头结点的单循环链表，一个链表指针指向表的第一个结点
分析：这里用O（1）时间插入的方法是，在表头结点后面插入一个新表头，然后把原来表头改成新的结点。
解答：B
考点6 双链表及其基本操作
1.N表示线性表中当前元素的数目，p表示指针的存储单元大小，E表示
数据元素的存储单元大小，D表示可以在数组中存储的线性表元素的最大数目，那么使用顺序表所需空间大小为（），使用双向链表（不考虑头结点）所需空间的大小为（）
分析：考察线性表存储空间的计算。
解答：ED，（2P+E）n
2.
解答：B
3.指针p指向双向链表的某个结点，在指针p所指结点之后插入s所指
结点。结点结构：prior-data-next，操作序列是：
分析：链表中插入结点的顺序是一般先处理被插入者
解答：s->prior=p;s->next=p->next;p->next->prior=s;p->next=s;
考点7单链表的应用
1.
2.
3.
考点8 单循环链表的应用
1.设计一个将单循环链表逆置的算法函数
考点9 其他链表及特殊算法
1.判断带头结点的双向循环链表s是否对称相等的算法如下所
示，请填空。
第三章栈和队列
考点1 栈和队列的基本概念
1.判断：线性表、栈和队列的逻辑结构完全相同
解答：正确
2.判断：栈和队列都是线性表，只是在插入和删除时受到一些限制。
分析：栈和队列是两种特殊的线性表，他们的逻辑结构与线性表相同只是其运算规则较线性表有更多的限制，故又称他们为运算受限的线性表
解答：正确
3.判断：在链队列中，除了队头指针外，还必须设队尾指针，否则无法进行
队列的插入操作。
解答：正确
关键考点点评：队列的链式存储结构简称链队列。它是限制仅在表头删除和表尾插入的单链表。注意：增加指向链表上的最后一个结点的尾指针，便于在表尾作插入操作。
4.循环队列的优点是什么？如何判断它的空和满。
5.以下的叙述中，正确的是：
A线性表的线性存储结构优于链式存储结构
B二维数组是其数据元素为线性表的线性表
C栈的操作方式是先进先出
D队列的操作方式是先进后出
解答：B
6.执行（）操作时，需要使用队列作为辅助存储空间
A 查找哈希表
B 广度优先搜索图
C 先序遍历二叉树
D 深度优先搜索图
分析：考察上述几种操作在额外空间上的需求。查找哈希表和先序遍历二叉树不需要比较额外的空间；而深度优先搜索图则可以利用递归的方法，使用堆栈，而不使用队列作为辅助存储空间；只有广度优先搜索图需要用到队列作为辅助存储空间。
解答：B
考点2 入栈出栈分析
1.元素abcde依次进入初始为空的栈中，若元素进栈后可停留，可出栈，直
到所有元素都出栈，则在所有可能的出栈序列中，以元素d开头的序列个数是：
A 3
B 4
C 5
D 6
分析：该题考查堆栈的进出问题，出栈顺序必为d-c-b-a-，e的顺序不定，在任意一个“-”上都有可能。故可能以d开头的序列个数是4
解答：B
2.当入队序列为1、2、3时，出队序列可以是什么？当入栈序列为1、2、3
时，出栈序列可以是什么？
解答：出队序列为123，出栈序列可以是123,132,231,213,321
考点3 栈的基本操作
1.利用栈求表达式的值时，设立操作数栈OPND，设OPND只有两个存储单
元，在下列表达式中，不发生上溢的是：
A．a-b*(c-d) B. (a-b)*c-d
C. (a-b*c)-d
D.(a-b)*(c-d)
分析：只有B的运算顺序是依次向右，不需要暂存其他的操作数来配合运算优先顺序
解答：B
2. 向一个栈顶指针为top的链栈中插入一个s结点，则执行：
A．top->next=s B s->next=top->next;top->next=s
C. s->next=top;top=s
D. s->next=top;top=top->next
解答：C
关键考点点评：
3. 用不带头结点的链表表示队列，在进行删除运算时
A 仅修改头指针
B 仅修改尾指针
C 头尾指针都要修改
D 头尾指针可能都要修改
解答：A
4．当两个栈共享一个空间时，栈用一维数组stack（0，n-1）表示，梁栈顶指针分别为top[1]和top[2],则栈满时的条件为：
分析：两个栈共享一个空间时，由于栈底是固定的且有两个，所以栈底一定是该空间的两个边，然后数据存放在中间，所以栈满的时候就是两个栈顶挨着的时候。
解答：top[1]=top[2]+1
考点4 栈在递归中的应用
1.一个递归的定义可以用递归过程求解，也可以用非递归过程求解，但是单
从运行时间上来看，通常递归过程要比非递归过程：
A 较快
B 较慢
C 相同
D 无法比较
分析：递归过程中通常会引入一些元素的反复计算，而且有堆栈压缩开销，所以通常来说，递归过程要满
解答：B
2.在递归程序调用过程中，递归工作栈包含了哪些数据？
设计题目：一 单位员工通讯录管理系统 一、题目要求 为某个单位建立一个员工通讯录管理系统，可以方便查询每一个员工的办公室电话、手机号、及电子邮箱。其功能包括通讯录链表的建立、员工通讯信息的查询、修改、插入与删除、以及整个通讯录表的输出。二、概要设计 本程序通过建立通讯录链表，对员工信息进行记录，并建立一个系统的联系。 三、主要代码及分析 这里面关于链表的主要的操作有插入，查询，删除。则这里只列出这几项的主代码。 1、通过建立通讯录结构体，对信息进行存储，建立链表，建立信息之间 的联系。 typedef struct { }DataType;结构体来存储通讯录中的基本信息 typedef struct node { DataType data; /*结点的数据域*/ struct node *next; /*结点的指针域*/ }ListNode,*LinkList; 2、信息插入操作，将信息查到链表的后面。 void ListInsert(LinkList list){ //信息插入 ListNode *w; w=list->next; while(w->next!=NULL) { w=w->next; } ListNode *u=new ListNode; u->next=NULL; cout<<"员工编号：";cin>>u->data.num; cout<<"员工姓名：";cin>>u->https://www.doczj.com/doc/9b14895335.html,; cout<<"手机号码：";cin>>u->data.call; cout<<"员工邮箱：";cin>>u->data.email; cout<<"办公室电话号码：";cin>>u->data.phone; w->next=u;w=w->next; }
数据结构实验指导书
实验一线性表的顺序存储结构 一、实验学时 4学时 二、背景知识:顺序表的插入、删除及应用。 三、目的要求： 1．掌握顺序存储结构的特点。 2．掌握顺序存储结构的常见算法。 四、实验内容 1．从键盘随机输入一组整型元素序列，建立顺序表。（注意：不可将元素个数和元素值写死在程序中） 2．实现该顺序表的遍历（也即依次打印出每个数据元素的值）。 3．在该顺序表中顺序查找某一元素,如果查找成功返回1,否则返回0。 4．实现把该表中某个数据元素删除。 5．实现在该表中插入某个数据元素。 6．实现两个线性表的归并（仿照课本上P26 算法2.7）。 7. 编写一个主函数,调试上述6个算法。 五、实现提示 1.存储定义 #include
typedef int ElemType；//元素类型 typedef struct list{ ElemType *elem;//静态线性表 int length; //表的实际长度 int listsize; //表的存储容量 }SqList;//顺序表的类型名 2.建立顺序表时可利用随机函数自动产生数据。 3.为每个算法功能建立相应的函数分别调试，最后在主函数中调用它们。 六、注意问题 插入、删除元素时对于元素合法位置的判断。 七、测试过程 1.先从键盘输入元素个数，假设为6。 2.从键盘依次输入6个元素的值（注意：最好给出输入每个元素的提示，否则除了你自己知道之外，别人只见光标在闪却不知道要干什么），假设是：10,3,8,39,48，2。 3．遍历该顺序表。 4.输入待查元素的值例如39（而不是待查元素的位置）进行查找，因为它在表中所以返回1。假如要查找15,因为它不存在，所以返回0。 5.输入待删元素的位置将其从表中删掉。此处需要注意判断删位置是否合法，若表中有n个元素，则合法的删除位
数据结构课后练习题汇总 chapter 4 string 1，multiple choice 1，set string S1 =‘ abcdefg ‘，S2 =‘ pqrst ‘，函数Concat(x，y)返回x 和y字符串的连接字符串，Substr(s，I，J) if length(s)返回字符串256的长度+9 s ，结果字符串 9 A、BCDEF B、BCDEFG C、BCPQRST D、BCDEFEF 2、空字符串和空格相同()A.更正错误 3。如果字符串S1 =‘ABCDEFG ‘，S2 =‘ 9898 ‘，S3 =‘ # # # ‘，S4 =‘ 012345 ‘， replace (S1，SUBSTRA(S1，4，长度(S3))，S3)，CONCAT (S1，SUBSTRA(S4，索引(S2，’ 8 ‘))被执行，结果是() A，ABC###G0123 B，ABCD###2345 C，ABC###G2345 D，ABC # # # # 2345e，ABC###G1234 F，ABCD###1234 G，ABC # # 01234 4 4，字符串是特殊的线性表，其特殊性如(d)所示 A，可以顺序存储b，数据元素是字符c，可以存储d链接，数据元素可以是多个字符 5，并且具有两个字符串p和q。用于寻找q在p中首先出现的位置
的操作被称为() A，连接b，模式匹配c，子字符串d，字符串长度6，下列关于字符串的陈述中哪一项不正确？() a。字符串是字符b的有限序列，空字符串是由空格 c组成的字符串。模式匹配是字符串的一个重要操作。字符串可以顺序存储，也可以使用链存储。字符串的长度引用了() a。字符串中包含的不同字母的数量b .字符串中包含的字符的数量c .字符串中包含的不同字符的数量d .字符串中包含的非空格字符的数量 2，判断问题 1，并且在最坏的情况下子串定位函数的时间复杂度是O(n*m ),因此子串定位函数没有实用价值2.有两个字符串P和Q，其中Q是P的子串。 算法将P中第一个出现的Q作为子串Q在P中的位置，称为匹配。3和KMP算法的最大特点是不需要检索指示主字符串的指针 3，填写问题 1，集S =‘ I _ AM _ A _ TEACHER ‘，其长度为()2、空字符串为(零字符串)，其长度为() 3，集合S1 = ‘好’，S2 =‘ ︼’，S3 = ‘再见！，S1、S2和S3连接的结果是() 20
2017年数据结构期末考试题及答案 一、选择题（共计50分，每题2分，共25题） 1 ?在数据结构中，从逻辑上可以把数据结构分为 C 。 A. 动态结构和静态结构B?紧凑结构和非紧凑结构 C.线性结构和非线性结构 D .内部结构和外部结构 2?数据结构在计算机内存中的表示是指 A ° A. 数据的存储结构 B.数据结构 C.数据的逻辑结构 D .数据元 素之间的关系 3.在数据结构中，与所使用的计算机无关的是数据的 A 结构。 A. 逻辑B?存储 C.逻辑和存储 D.物理 4 .在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C ° A.数据的处理方法B?数据元素的类型 C.数据元素之间的关系 D.数据的存储方法 5. 在决定选取何种存储结构时，一般不考虑 A ° A.各结点的值如何B?结点个数的多少 C?对数据有哪些运算 D.所用的编程语言实现这种结构是否方便。 6. 以下说法正确的是D ° A. 数据项是数据的基本单位 B. 数据元素是数据的最小单位 C. 数据结构是带结构的数据项的集合 D. —些表面上很不相同的数据可以有相同的逻辑结构 7. 在以下的叙述中，正确的是B ° A. 线性表的顺序存储结构优于链表存储结构 B. 二维数组是其数据元素为线性表的线性表 C?栈的操作方式是先进先出 D.队列的操作方式是先进后出
8. 通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着 A. 数据元素具有同一特点 B. 不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致 C. 每个数据元素都一样 D. 数据元素所包含的数据项的个数要相等 9 ?链表不具备的特点是 A 。 A.可随机访问任一结点 B.插入删除不需要移动元素 C?不必事先估计存储空间 D.所需空间与其长度成正比 10. 若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一 个结点，则采用 D 存储方式最节省运算时间。 A.单链表B ?给出表头指针的单循环链表 C.双链表D ?带头结点 的双循环链表 11. 需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是 B 。 A.单链表B .静态链表 C.线性链表 D .顺序存储结构 12 .非空的循环单链表head的尾结点（由p所指向）满足C 。 A. p—>next 一NULL B. p — NULL C. p—>next == head D. p = = head 13 .在循环双链表的p所指的结点之前插入s所指结点的操作是 D 。 A .p—> prior-> prior=s B .p—> prior-> n ext=s C.s —> prior—> n ext = s D.s —> prior—> prior = s 14 .栈和队列的共同点是C 。 A.都是先进后出 B .都是先进先出 C.只允许在端点处插入和删除元素 D .没有共同点
实验报告 实验六图的应用及其实现 一、实验目的 1．进一步功固图常用的存储结构。 2．熟练掌握在图的邻接表实现图的基本操作。 3．理解掌握AOV网、AOE网在邻接表上的实现以及解决简单的应用问题。 二、实验内容 一>.基础题目：(本类题目属于验证性的，要求学生独立完成) [题目一]：从键盘上输入AOV网的顶点和有向边的信息,建立其邻接表存储结构,然后对该图拓扑排序,并输出拓扑序列. 试设计程序实现上述AOV网 的类型定义和基本操作,完成上述功能。 [题目二]：从键盘上输入AOE网的顶点和有向边的信息,建立其邻接表存储结构,输出其关键路径和关键路径长度。试设计程序实现上述AOE网类型定义和基本操作,完成上述功能。 测试数据：教材图7.29 【题目五】连通OR 不连通 描述：给定一个无向图，一共n个点，请编写一个程序实现两种操作： D x y 从原图中删除连接x，y节点的边。 Q x y 询问x，y节点是否连通 输入 第一行两个数n,m（5<=n<=40000,1<=m<=100000） 接下来m行，每行一对整数 x y （x,y<=n）,表示x,y之间有边相连。保证没有重复的边。 接下来一行一个整数 q（q<=100000） 以下q行每行一种操作，保证不会有非法删除。 输出 按询问次序输出所有Q操作的回答，连通的回答C，不连通的回答D 样例输入
3 3 1 2 1 3 2 3 5 Q 1 2 D 1 2 Q 1 2 D 3 2 Q 1 2 样例输出 C C D 【题目六】 Sort Problem An ascending sorted sequence of distinct values is one in which some form of a less-than operator is used to order the elements from smallest to largest. For example, the sorted sequence A, B, C, D implies that A < B, B < C and C < D. in this problem, we will give you a set of relations of the form A < B and ask you to determine whether a sorted order has been specified or not. 【Input】 Input consists of multiple problem instances. Each instance starts with a line containing two positive integers n and m. the first value indicated the number of objects to sort, where 2 <= n<= 26. The objects to be sorted will be the first n characters of the uppercase alphabet. The second value m indicates the number of relations of the form A < B which will be given in this problem instance. 1 <= m <= 100. Next will be m lines, each containing one such relation consisting of three characters: an uppercase letter, the character "<" and a second uppercase letter. No letter will be outside the range of the first n letters of the alphabet. Values of n = m = 0 indicate end of input. 【Output】 For each problem instance, output consists of one line. This line should be one of the following three: Sorted sequence determined: y y y… y. Sorted sequence cannot be determined. Inconsistency found.
数据结构考试题库
绪论 一、填空题 1.数据的逻辑结构被分为集合、(线性结构)、(树形结构)和(图状结构)四种。 2.物理结构是数据结构在计算机中的表示，又称为(存储结构)。 3.数据元素的逻辑结构包括( 线性)、(树)和图状结构3种类型，树形结构和图状结构合称为(非线性结构)。 4.(数据元素)是数据的基本单位，(数据项)是数据不可分割的最小单位。 5.线性结构中元素之间存在(一个对一个)关系，树形结构中元素之间存在(一个对多个)关系，图状结构中元素之间存在(多个对多个)关系。 ？6.数据结构是一门研究非数值计算的程序设计问题中：计算机的(数据元素)以及它们之间的(关系)和(运筹)等的学科。 7.算法的五个重要特性为有穷性、确定性、(输入)、(输出)和(可行性)。 二、选择题 1.数据的不可分割的基本单位是(D)。 A.元素 B.结点 C.数据类型 D.数据项 *2.线性表的逻辑顺序与存储顺序总是一致的，这种说法(B)。 A.正确 B.不正确 C.不确定 D.无法选择 3.线性结构是指数据元素之间存在一种(D)。 精心整理，用心做精品2
A.一对多关系 B.多对多关系 C.多对一关系 D.一对一关系 4.在数据结构中，从逻辑上可以把数据结构分成(A)。 A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C.线性结构和非线性结构 D.内部结构和外部结构 5.线性表若采用链式存储结构时，要求内存中可用存储单元的 地址( D)。 A.必须是连续的 B.部分地址必须是连续的 C.一定是不连续的 D.连续不连续都可以 三、简答题 1.算法的特性是什么。 答：有穷性确定性可行性有0或多个输入有1或多个输出线性结构 一、填空题 1.在一个长度为n的线性表中删除第i个元素（1≤i≤n）时，需向前移动(n-i)个元素。 2.从循环队列中删除一个元素时，其操作是(先移动队首指针，后取出元素)。 3.在线性表的单链接存储中，若一个元素所在结点的地址为p，则其后继结点的地址为(p->next)。 4.在一个单链表中指针p所指向结点的后面插入一个指针q所指向的结点时，首先把(p->next)的值赋给q->next，然后(q->date)的值赋给p->next。 5.从一个栈删除元素时，首先取出(栈顶元素)，然后再使(栈顶指针)减1。 6.子串的定位操作通常称做串的(模式匹配)。 精心整理，用心做精品3
学生实验报告册 （理工类） 课程名称：算法与数据结构专业班级 学生学号：学生： 所属院部：计算机工程学院指导教师：章海鸥 2016 ——2017 学年第 1 学期 金陵科技学院教务处制 实验报告书写要求 实验报告原则上要求学生手写，要求书写工整。若因课程特点需打印的，要遵照以下字体、字号、间距等的具体要求。纸一律采用 A4的纸。
实验报告书写说明 实验报告中一至四项容为必填项，包括实验目的和要求；实验仪器和设备；实验容与过程；实验结果与分析。各院部可根据学科特点和实验具体要求增加项目。 填写注意事项 （1）细致观察，及时、准确、如实记录。 （2）准确说明，层次清晰。 （3）尽量采用专用术语来说明事物。 （4）外文、符号、公式要准确，应使用统一规定的名词和符号。 （5）应独立完成实验报告的书写，严禁抄袭、复印，一经发现，以零分论处。 实验报告批改说明 实验报告的批改要及时、认真、仔细，一律用红色笔批改。实验报告的批改成绩采用百分制，具体评分标准由各院部自行制定。 实验报告装订要求 实验批改完毕后，任课老师将每门课程的每个实验项目的实验报告以自然班为单位、按学号升序排列，装订成册，并附上一份该门课程的实验大纲。
实验项目名称：顺序表实验学时： 2 同组学生：╱实验地点： 实验日期：实验成绩： 批改教师：批改时间：
实验1 顺序表 一、实验目的和要求 掌握顺序表的定位、插入、删除等操作。 二、实验仪器和设备 VC6.0 三、实验容与过程（含程序清单及流程图） 1、必做题 （1）编写程序建立一个顺序表，并逐个输出顺序表中所有数据元素的值。 编写主函数测试结果。 （2）编写顺序表定位操作子函数，在顺序表中查找是否存在数据元素x。 如果存在，返回顺序表中和x值相等的第1个数据元素的序号（序号 从0开始编号）；如果不存在，返回－1。编写主函数测试结果。 （3）在递增有序的顺序表中插入一个新结点x，保持顺序表的有序性。 解题思路：首先查找插入的位置，再移位，最后进行插入操作；从第 一个元素开始找到第一个大于该新结点值x的元素位置i即为插入位 置；然后将从表尾开始依次将元素后移一个位置直至元素i；最后将 新结点x插入到i位置。 （4）删除顺序表中所有等于X的数据元素。 2、选做题 （5）已知两个顺序表A和B按元素值递增有序排列，要求写一算法实现将A和B归并成一个按元素值递减有序排列的顺序表（允许表中含有值 相同的元素）。 程序清单： (1) #include
数据结构期末考试试题及答案 、选择题 评价一个算法时间性能的主要标准是()。1. A、算法易于调试 B、算法易于理解 C、算法的稳定性和正确性 D、算法的时间复杂度 )等五个特性。计算机算法具备有输入、输出、 2. A、可行性、可移植性和可扩充性 B、可行性、确定性和有穷性 C、确定性、有穷性和稳定性 D、XX、稳定性和XX 。带头结点的单链表head为空的判定条件是()3. A、h ead==NULL B、h ead->next==NULL C、head->next==head D、head！=NULL 以下关于线性表的说法不正确的是()。4. A、线性表中的数据元素可以是数字、字符、记录等不同类型。 B、线性表中包含的数据元素个数不是任意的。
C、线性表中的每个结点都有且只有一个直接前趋和直接后继。 D、存在这 样的线性表：表中各结点都没有直接前趋和直接后继。 在顺序表中，只要知道()，就可在相同时间内求出任一结点的存储地址。 5.A、基地址 B、结点大小 C、向量大小 D、基地址和结点大小 ()运算中，使用顺序表比链表好。6. A、插入 B、删除 C、根据序号查找 D、根据元素值查找一个长度为n的顺序表中，向第i个元素之前插入一个新元素时，需要向后移动()个元素7.A、n-i B、n-i+1 C、n-i-1 D、i ()适合作为经常在首尾两端操作线性表的存储结构。8. A、顺序表 B、单链表 C、循环链表 D、双向链表
栈和队列的共同点是() 9. A、都是先进后出 B、都是先进先出 C、只允许在端点处插入和删除元素 D、没有共同点 一个队列的入列序列是1234，则队列的输出序列是()。10. A 、4321 B 、12 3 4 C 、1432 D 、 3241队列与一般的线性表的区别在于()。11. A、数据元素的类型不同 B、运算是否受限制 C、数据元素的个数不同 D、逻辑结构不同 假上溢”现象会出现在()中。12. A、循环队列 B、队列 C、链队列 、顺序队列D.二、填空
《空间数据结构基础》 课程实习报告（测绘10级） 姓名 班级 学号 环境与测绘学院
1C++面向对象程序设计基础 【实验简介】学会用算法语言C++描述抽象数据类型，使用模板建立数据结构。理解数据结构的组成分为两部分，第一部分是数据集（数据元素），第二部分是在此数据集上的操作。从面向对象的观点看，这两部分代表了对象的属性和方法。掌握用C++描述数据结构的基本方法，即通过建立类来描述抽象数据类型。类的数据成员提供对象属性，成员函数提供操作方法，方法是公共接口，用户通过调用方法实现对属性的访问。 【实验内容】 1.定义三维空间的坐标点TPoint 2.描述三维空间的球TBall，实现其主要操作（如计算体积和表面积，输出空间坐标 等）。 【主要代码】 头文件： TPoint.h: #ifndef TPOINT_H #define TPOINT_H #include #include 第 1 章绪论 课后习题讲解 1. 填空 ⑴（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 【解答】数据元素 ⑵（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。 【解答】数据项，数据元素 【分析】数据结构指的是数据元素以及数据元素之间的关系。 ⑶从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。 【解答】集合，线性结构，树结构，图结构 ⑷数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）和（）。 【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系 ⑸算法具有五个特性，分别是（）、（）、（）、（）、（）。 【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性 ⑹算法的描述方法通常有（）、（）、（）和（）四种，其中，（）被称为算法语言。 【解答】自然语言，程序设计语言，流程图，伪代码，伪代码 ⑺在一般情况下，一个算法的时间复杂度是（）的函数。 【解答】问题规模 ⑻设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若为n*log25n，则表示成数量级的形式为（）。 【解答】Ο(1)，Ο(nlog2n) 【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。 2. 选择题 ⑴顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链接存储结构中的数据元素之间的逻辑关系是由（）表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针 【解答】C，D 【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。 2011-2012学年第一学期期末考查 《数据结构》试卷 （答案一律写在答题纸上，在本试卷上做答无效） 一、选择（每题1分，共10分） 1.长度为n的线性表采用顺序存储结构，一个在其第i个位置插入新元素的算法时间复杂度为（D） A.O(0) B.O(1) C.O(n) D.O(n2) 2.六个元素按照6，5，4，3，2，1的顺序入栈，下列哪一个是合法的出栈序列？（D） A.543612 B.453126 C.346512 D.234156 3.设树的度为4，其中度为1、2、3、4的结点个数分别是4、2、1、2，则树中叶子个数为（B ） A.8 B.9 C.10 D.11 4.设森林F对应的二叉树B有m个结点，B的右子树结点个数为n，森林F中第一棵树的结点个数是（ B ） A. m-n B.m-n-1 C.n+1 D.m+n 5.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（B） A.9 B.11 C.15 D.不确定 6.下列哪一个方法可以判断出一个有向图是否有环。（A） A.深度优先遍历 B.拓扑排序 C.求最短路径 D.求关键路径 7.第7层有10个叶子结点的完全二叉树不可能有（B ）个结点。 A.73 B.234 C.235 D.236 8.分别用以下序列构造二叉排序树，与用其他三个序列构造的结果不同的是（B） A.（100,80,90,60,120,110,130） B.（100, 120, 110,130,80, 60,90） C.（100,60,80,90,120,110,130） D.（100,80, 60,90, 120, 130,110） 9.对一组数据（84，47，25，15，21）排序，数据的排列次序在排序过程中变化如下：（1）84 47 25 15 21 （2）15 47 25 84 21 （3）15 21 25 84 47（4）15 21 25 47 84则采用的排序方法是（B ） A.选择排序 B.起泡排序 C.快速排序 D.插入排序 10.对线性表进行折半查找时，要求线性表必须（D） A.以顺序方式存储 B.以顺序方式存储，且数据元素有序 实验六图的应用及其实现 一、实验目的 1．进一步功固图常用的存储结构。 2．熟练掌握在图的邻接表实现图的基本操作。 3．理解掌握AOE网在邻接表上的实现及解决简单的应用问题。 二、实验内容 [题目]：从键盘上输入AOE网的顶点和有向边的信息,建立其邻接表存储结构,输出其关键路径和关键路径长度。试设计程序实现上述AOE网类型定义和基本操作,完成上述功能。 三、实验步骤 （一）、数据结构与核心算法的设计描述 本实验题目是基于图的基本操作以及邻接表的存储结构之上，着重拓扑排序算法的应用，做好本实验的关键在于理解拓扑排序算法的实质及其代码的实现。 （二）、函数调用及主函数设计 以下是头文件中数据结构的设计和相关函数的声明： typedef struct ArcNode // 弧结点 { int adjvex; struct ArcNode *nextarc; InfoType info; }ArcNode; typedef struct VNode //表头结点 { VertexType vexdata; ArcNode *firstarc; }VNode,AdjList[MAX_VERTEX_NUM]; typedef struct //图的定义 { AdjList vertices; int vexnum,arcnum; int kind; }MGraph; typedef struct SqStack //栈的定义 { SElemType *base; SElemType *top; int stacksize; }SqStack; int CreateGraph(MGraph &G);//AOE网的创建 int CriticalPath(MGraph &G);//输出关键路径 （三）、程序调试及运行结果分析 （四）、实验总结 在做本实验的过程中，拓扑排具体代码的实现起着很重要的作用，反复的调试和测试占据着实验大量的时间，每次对错误的修改都加深了对实验和具体算法的理解，自己的查错能力以及其他各方面的能力也都得到了很好的提高。最终实验结果也符合实验的预期效果。 四、主要算法流程图及程序清单 1、主要算法流程图： 2、程序清单： 创建AOE网模块： int CreateGraph(MGraph &G) //创建有向网 { int i,j,k,Vi,Vj; ArcNode *p; cout<<"\n请输入顶点的数目、边的数目"< 知识点： 01．绪论 02．顺序表 03．链表 04．栈 05．链队列 06．循环队列 07．串 08．数组的顺序表示 09．稀疏矩阵 10．广义表 11．二叉树的基本概念 12．二叉树遍历、二叉树性质 13．树、树与二叉树的转换 14．赫夫曼树 15．图的定义、图的存储 16．图的遍历 17．图的生成树 18．静态查找（顺序表的查找、有序表的查找） 19．动态查找（二叉排序树、平衡树、B树） 20．哈希查找 21．插入排序（直接插入、折半插入、2路插入、希尔排序）22．选择排序（简单选择、树形选择、堆排序） 23．快速排序、归并排序 101A1（1）．数据的逻辑结构是（A）。 A．数据的组织形式B．数据的存储形式C．数据的表示形式D．数据的实现形式 101A1（2）．组成数据的基本单位是（C）。 A．数据项B．数据类型C．数据元素D．数据变量 101B1（3）．与顺序存储结构相比，链式存储结构的存储密度（B）。 A．大B．小C．相同D．以上都不对 101B2（4）．对于存储同样一组数据元素而言，（D）。 A．顺序存储结构比链接结构多占空间B．在顺序结构中查找元素的速度比在链接结构中查找要快C．与链接结构相比，顺序结构便于安排数据元素D．顺序结构占用整块空间而链接结构不要求整块空间101B2（5）．下面程序的时间复杂度为（B）。 x=0； for（i=1；i 数据结构考试及答案（） 作者: 日期: 2 数据结构试题 一、单选题 1、在数据结构的讨论中把数据结构从逻辑上分为（C） A 内部结构与外部结构 B 静态结构与动态结构 C 线性结构与非线性结构 D 紧凑结构与非紧凑结构。 2、采用线性链表表示一个向量时，要求占用的存储空间地址（D） A 必须是连续的B部分地址必须是连续的 C 一定是不连续的D可连续可不连续 3、采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为 （D ）。 An B n/2 C （n-1）/2 D （n+1）/2 4、在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点s，则执行（D ）o A s—link = p—link ；p—link = s； B p—link = s; s—link = q; C p—link = s—link ；s—link = p； D q—link = s; s—link = p; 5、如果想在4092个数据中只需要选择其中最小的5个，采用（C ）方法最好。 A 起泡排序 B 堆排序C锦标赛排序 D 快速 排序 6、设有两个串t和p，求p在t中首次出现的位置的运算叫做（B ）o A 求子串B模式匹配C 串替换 D 串连接 7、在数组A中，每一个数组元素A[i][j] 占用3个存储字，行下标i从1到8, 列下标j从1到10。所有数组元素相继存放于一个连续的存储空间中，则存放 该数组至少需要的存储字数是（ C ）。 A 80 B 100 C 240 D 270 8、将一个递归算法改为对应的非递归算法时，通常需要使用（ A ）。 A 栈B队列C循环队列D优先队列 9、一个队列的进队列顺序是1,2, 3, 4 ，则出队列顺序为（C ）。 10、在循环队列中用数组A[0.. m-1]存放队列元素，其队头和队尾指针分别为front和rear，则当前队列中的元素个数是（ D ）。 A （ front - rear + 1） % m B （rear - front + 1） %m C （ front - rear + m） % m D （ rear - front + n） % m 11、一个数组元素a[i]与（A ）的表示等价。 A * （a+i） B a+i C *a+i D &a+i 12、若需要利用形参直接访问实参，则应把形参变量说明为（ B ）参数 A指针 B 引用C值 D 变量 13、下面程序段的时间复杂度为（C) for (i nt i=0;i 《数据结构》课程 实验报告一线性表的顺序实现 一、实验目的和要求： 1．掌握顺序表的存储结构形式及其描述和基本运算的实现。 2.掌握用顺序表表示集合等数据的方法，并能设计出合理的存储结构，编写出有关运算的算法。 二、实验内容：（给出具体的说明文字和操作图片） 已知顺序表结构与相关函数定义在sequlist.h文件中，基于该文件完成所有实验题。 1.基于sequlist.h中定义的顺序表L，设计一个算法void delx(sequence_list *L, datatype x)，删除其中所有值等于x 的元素，要求算法的时间复杂度为O(n)、空间复杂度为0(1)。 #include void initseqlist(sequence_list *L)//初始化OK { L->size=0; } void input(sequence_list *L) { datatype x; initseqlist(L); printf("请输入一组数据，以0做为结束符：\n"); scanf("%d",&x); while (x) { L->a[L->size++]=x; scanf("%d",&x); } } 邻接矩阵的实现 1. 实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现2. 实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历3．设计与编码MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template int vertexNum, arcNum; }; #endif MGraph.cpp #include 2012年数据结构期末考试题及答案 一、选择题 1．在数据结构中，从逻辑上可以把数据结构分为C。 A．动态结构和静态结构B．紧凑结构和非紧凑结构 C．线性结构和非线性结构D．内部结构和外部结构 2．数据结构在计算机内存中的表示是指A。 A．数据的存储结构B．数据结构C．数据的逻辑结构D．数据元素之间的关系 3．在数据结构中，与所使用的计算机无关的是数据的A结构。 A．逻辑B．存储C．逻辑和存储D．物理 4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储C。 A．数据的处理方法B．数据元素的类型 C．数据元素之间的关系D．数据的存储方法 5．在决定选取何种存储结构时，一般不考虑A。 A．各结点的值如何B．结点个数的多少 C．对数据有哪些运算D．所用的编程语言实现这种结构是否方便。 6．以下说法正确的是D。 A．数据项是数据的基本单位 B．数据元素是数据的最小单位 C．数据结构是带结构的数据项的集合 D．一些表面上很不相同的数据可以有相同的逻辑结构 7．算法分析的目的是C，算法分析的两个主要方面是A。 （1）A．找出数据结构的合理性B．研究算法中的输入和输出的关系 C．分析算法的效率以求改进C．分析算法的易读性和文档性 （2）A．空间复杂度和时间复杂度B．正确性和简明性 C．可读性和文档性D．数据复杂性和程序复杂性 8．下面程序段的时间复杂度是O（n2）。 s ＝0； for（I ＝0；i＜n；i＋＋） for（j＝0；j＜n；j＋＋） s ＋＝B[i][j]； sum ＝s ； 9．下面程序段的时间复杂度是O（n*m）。 for（i ＝0；i＜n；i＋＋） for（j＝0；j＜m；j＋＋） A[i][j] ＝0； 10．下面程序段的时间复杂度是O（log3n）。 i ＝0； while（i＜＝n） i ＝i * 3； 11．在以下的叙述中，正确的是B。 A．线性表的顺序存储结构优于链表存储结构 B．二维数组是其数据元素为线性表的线性表 C．栈的操作方式是先进先出 D．队列的操作方式是先进后出 12．通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着B 。 A．数据元素具有同一特点 B．不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致 C．每个数据元素都一样 D．数据元素所包含的数据项的个数要相等 13．链表不具备的特点是A。 A．可随机访问任一结点B．插入删除不需要移动元素 C．不必事先估计存储空间D．所需空间与其长度成正比 14．不带头结点的单链表head为空的判定条件是A。数据结构第六章实验
数据结构习题与答案
《数据结构》期末考试题及答案
数据结构实验六 图的应用及其实现
数据结构习题库汇总
数据结构考试及答案()
《数据结构》课程实验报告一
数据结构实验报告图实验
2015年数据结构期末考试题及答案
相关主题
文本预览