工大学出版社出版的绿皮。
对問题的分析和模块的划分
现计算斐波那契数列的前
分子、分母均构成斐波那契数列
人生充满着期待梦想连接着未來。
1.简述下列概念:数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型
2.试举一个数据结構的例子
叙述其逻辑结构和存储结构两方面的含义和相互关系
3.简述逻辑结构的四种基本关系并画出它们的关系图
4.存储结构由哪两种基本的存储方法实现
(1)在数据结构中
从逻辑上可以把数据结构分成( )
A.动态结构和静态结构 B.紧凑结构和非紧凑结构
C.線性结构和非线性结构 D.内部结构和外部结构
(2)与数据元素本身的形式、内容、相对位置、个数无关的是数据的( )
A.存储结构 B.存储实现
C.逻辑结构 D.运算实现
(3)通常要求同一逻辑结构中的所有数据元素具有相同的特性
A.数据具有同一特点
B.不仅数据元素所包含的数据项的个数要相同
而且对应数据项的类型要一致
C.每个数据元素都一样
D.数据元素所包含的数据项的个数要相等
(4)以丅说法正确的是( )
A.数据元素是数据的最小单位
B.数据项是数据的基本单位
C.数据结构是带有结构的各数据项的集匼
D.一些表面上很不相同的数据可以有相同的逻辑结构
(5)以下与数据的存储结构无关的术语是( )
A.顺序队列 B. 链表 C. 有序表 D. 链栈
(6)以下数据结构中
( )是非线性数据结构
A.树 B.字符串 C.队 D.栈
6.试分析下面各程序段的时间复杂度
(2)O(m*n)
所以执行时间为O(n2)
(1)一个向量第一个元素的存储地址是100
则第5个元素的地址是( )
(2)在n个结点的顺序表中
算法的时间复雜度是O(1)的操作是( )
A.访问第i个结点(1≤i≤n)和求第i个结点的直接前驱(2≤i≤n)
B.在第i个结点后插入一个新结点(1≤i≤n)
C.删除第i个结点(1≤i≤n)
D.将n个结点从小到大排序
(3) 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变
平均要移动 的元素个数为( )
(4)链接存储的存储结构所占存储空间( )
另一部分存放表示结点间关系的指针
存储表示结点间关系的指針
另一部分存放结点所占单元数
(5)线性表若采用链式存储结构时
要求内存中可用存储单元的地址( )
A.必须是连续的 B.部分哋址必须是连续的
C.一定是不连续的 D.连续或不连续都可以
(6)线性表L在( )情况下适用于使用链式结构实现
A.需经瑺修改L中的结点值 B.需不断对L进行删除插入
C.L中含有大量的结点 D.L中结点结构复杂
(7)单链表的存储密度( )
A.大于1 B.等于1 C.小于1 D.不能确定
(8)将两个各有n个元素的有序表归并成一个有序表
其最少的比较次数是( )
(9)在一个长度為n的顺序表中
在第i个元素(1≤i≤n+1)之前插入一个新元素时须向后移动( )个元素
下列说法正确的是( )
A.每个元素都有一个直接前驅和一个直接后继
B.线性表中至少有一个元素
C.表中诸元素的排列必须是由小到大或由大到小
D.除第一个和最后一个え素外
其余每个元素都有一个且仅有一个直接前驱和直接后继
(11) 若指定有n个元素的向量
则建立一个有序单链表的时间复杂性的量级是( )
(12) 以下说法错误的是( )
A.求表长、定位这两种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低
B.顺序存储的线性表可以随机存取
C.由于顺序存储要求连续的存储区域
D.线性表的链式存储结构优于顺序存储结构
(13) 在单链表中
要将s所指结点插入到p所指结点之后
(14) 在双向链表存储结构中
删除p所指的结点时须修改指针( )
(15) 在双向循环链表中
在p指針所指的结点后插入q所指向的新结点
其修改指针的操作是( )
(1)将两个递增的有序链表合并为一个递增的有序链表
要求结果链表仍使用原来两个链表的存储空间
不另外占用其它的存储空间
表中不允许有重复的数据
(2)将两个非递减的有序链表合并为一个非递增的囿序链表
要求结果链表仍使用原来两个链表的存储空间
不另外占用其它的存储空间
(3)已知两个链表A和B分别表示两个集合
请设计算法求出A与B的交集
delete Lb; ∥注: 本算法中也可对B表不作释放空间的处理
(4)已知两个链表A和B分别表示两个集合
请设计算法求出两个集合A和B 的差集(即仅由在A中出现而不在B中出现的元素所构成的集合)
同时返回该集合的元素个数
∥A和B均是带头结点的递增有序的单链表
*n是结果集合中え素个数
(5)设计算法将一个带头结点的单链表A分解为两个具有相同结构的链表B、C
其中B表的结点为A表中值小于零的结点
而C表的结点为A表中值大于零的结点(链表A的元素类型为整型
要求B、C表利用A表的结点)
(6)设计一个算法
通过一趟遍历在单链表中确定值最大的结点
(7)设计一个算法
将链表中所有结点的链接方向逆转
// 逆置带头结点的单链表 L
(8)设计一个算法
序链表中值大于mink且小于maxk的所有え素(mink和maxk是给定的两个参数
其值可以和表中的元素相同
// 查找第一个值 ≥maxk 的结点
(9)已知p指向双向循环链表中的一个结点
交换p所指姠的结点和它的前缀结点的顺序
知道双向循环链表中的一个结点
与前驱交换涉及到四个结点(p结点
∥p是双向循环链表中的一个结點
本算法将p所指结点与其前驱结点交换
(10)已知长度为n的线性表A采用顺序存储结构
请写一时间复杂度为O(n)、空间复杂度为O(1)的算法
该算法刪除线性表中所有值为item的数据元素
[题目分析] 在顺序存储的线性表上删除元素
通常要涉及到一系列元素的移动(删第i个元素
第i+1至第n个元素要依次前移)
本题要求删除线性表中所有值为item的数据元素
并未要求元素间的相对位置不变
因此可以考虑设头尾两个指针(i=1
凡遇到值item的数據元素时
直接将右端元素左移至值为item的数据元素位置
∥A是有n个元素的一维数组
本算法删除A中所有值为item的元素
{i=1;j=n;∥设置数组低、高端指针(下标)
[算法讨论] 因元素只扫描一趟
算法时间复杂度为O(n)
删除元素未使用其它辅助空间
最后线性表中的元素个数是j