题库-数据结构期末复习题
- 格式：doc
- 大小：220.50 KB
- 文档页数：19
第1章 绪论
一、选择题
1. 算法的计算量的大小称为计算的（ B ）。
A．效率 B. 复杂性 C. 现实性 D. 难度
2. 算法的时间复杂度取决于（C ）
A．问题的规模 B. 待处理数据的初态 C. A和B
3. 计算机算法指的是（1C），它必须具备（2B） 这三个特性。
(1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法
(2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性
C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性
4. 一个算法应该是（ B ）。
A．程序 B．问题求解步骤的描述
C．数据结构+程序 D．以上都不对.
5. 下面关于算法说法错误的是（ D ）
A．算法最终必须由计算机程序实现
B.为解决某问题的算法同为该问题编写的程序含义是相同的
C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的
6. 下面说法错误的是（ B ）
(1）算法原地工作的含义是指不需要任何额外的辅助空间 X
（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法 X
（3）所谓时间复杂度是指随问题规模的增大，算法执行时间的增长率。
（4）空间复杂度是算法所需存储空间的量度。
A．(1) B.(1),(2) C.(1),(4) D.(3)
7. 从逻辑上可以把数据结构分为（C ）两大类。
A．动态结构、静态结构 B．顺序结构、链式结构
C．线性结构、非线性结构 D．初等结构、构造型结构
8. 以下与数据的存储结构无关的术语是（ D ）。
A．循环队列 B. 链表 C. 哈希表 D. 栈
9. 连续存储设计时，存储单元的地址（ A ）。
A．一定连续 B．一定不连续 C．不一定连续 D．部分连续，部分不连续
10. 以下属于逻辑结构的是（ C ）。
A．顺序表 B. 哈希表 C.有序表 D. 单链表
第2章 线性表
一、选择题
1. 下述哪一条是顺序存储结构的优点？（A ）
A．存储密度大 B．插入运算方便 C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示
2. 下面关于线性表的叙述中，错误的是哪一个？（ B ）
A．线性表采用顺序存储，必须占用一片连续的存储单元。
B．线性表采用顺序存储，便于进行插入和删除操作。
C．线性表采用链接存储，不必占用一片连续的存储单元。
D．线性表采用链接存储，便于插入和删除操作。
3. 线性表是具有n个（C ）的有限序列（n>0）。
A．表元素 B．字符 C．数据元素 D．数据项 E．信息项
4. 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ A ）存储方式最节省时间。
A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表
5. 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（D）存储方式最节省运算时间。
A．单链表 B．仅有头指针的单循环链表 C．双链表 D．仅有尾指针的单循环链表
6. 设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用(D)最节省时间。
A. 单链表 B.单循环链表 C. 带尾指针的单循环链表 D.带头结点的双循环链表
7. 若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用（D）存储方式最节省运算时间。
A．单链表 B．双链表 C．单循环链表 D．带头结点的双循环链表
8. 链表不具有的特点是( B ）
A．插入、删除不需要移动元素 B．可随机访问任一元素 X
C．不必事先估计存储空间 D．所需空间与线性长度成正比
9. 下面的叙述不正确的是（C）
A．线性表在链式存储时，查找第i个元素的时间同i的值成正比
B. 线性表在链式存储时，查找第i个元素的时间同i的值无关
C. 线性表在顺序存储时，查找第i个元素的时间同i 的值成正比 X
D. 线性表在顺序存储时，查找第i个元素的时间同i的值无关
10. 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（C）(1<=i<=n+1)。
A. O(0) B. O(1) C. O(n) D. O(n2)
11. 对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（ C ）。
A．O(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1)
12. 线性表（ a1,a2,„,an）以链接方式存储时，访问第i位置元素的时间复杂性为（C）
A．O（i） B．O（1） C．O（n） D．O（i-1）
13. 非空的循环单链表head的尾结点p满足（A）。
A．p.next=head B．p.next=NULL C．p=NULL D．p= head
14. 在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（B）。
A．p->next=s;s->next=p->next; B． s->next=p->next;p->next=s; C．p->next=s;p->next=s->next; D． p->next=s->next;p->next=s;
15. 对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（B）
A．head==NULL B．head->next==NULL
C．head->next==head D．head!=NULL
二、综合应用题 //
1. 已知线性表（a1 a2 a3 „an）按顺序存于内存，每个元素都是整数，试设计用最少时间把所有值为负数的元素移到全部正数值元素前边的算法：例：（x,-x,-x,x,x,-x „x）变为（-x,-x,-x„x,x,x）。
2. 设单链表的表头指针为h，结点结构由data和next两个域构成，其中data域为字符型。写出算法dc(h,n),判断该链表的前n个字符是否中心对称。例如 xyx, xyyx都是中心对称。
3. 已知非空线性链表由list指出，链结点的构造为（data,link）.请写一算法，将链表中数据域值最小的那个链结点移到链表的最前面。要求：不得额外申请新的链结点。
4. 试编写在带头结点的单链表中删除（一个）最小值结点的（高效）算法。
void delete（Linklist &L）
5. 设有一头指针为L的带有表头结点的非循环双向链表，其每个结点中除有pred（前驱指针），data（数据）和next（后继指针）域外，还有一个访问频度域freq。在链表被起用前，其值均初始化为零。每当在链表中进行一次Locate(L,x)运算时，令元素值为x的结点中freq域的值增1，并使此链表中结点保持按访问频度非增（递减）的顺序排列，同时最近访问的结点排在频度相同的结点的最后，以便使频繁访问的结点总是靠近表头。试编写符合上述要求的Locate(L,x)运算的算法，该运算为函数过程，返回找到结点的地址，类型为指针型。
6. 已知长度为n的线性表A采用顺序存储结构，请写一时间复杂度为0(n)、空间复杂度为0(1)的算法，该算法删除线性表中所有值为item的数据元素。（O（1）表示算法的辅助空间为常量）。 第3章 栈和队列
一、选择题
1. 对于栈操作数据的原则是(B ）。
A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序
2. 一个栈的输入序列为123„n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（B）。
A. 不确定 B. n-i+1 C. i D. n-i
3. 若一个栈的输入序列为1,2,3,„,n，输出序列的第一个元素是i，则第j个输出元素是（D ）。
A. i-j-1 B. i-j C. j-i+1 D. 不确定的
4. 一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（B）。
A. 2 3 4 1 5 B. 5 4 1 3 2
C. 2 3 1 4 5 D. 1 5 4 3 2
5. 输入序列为ABC，可以变为CBA时，经过的栈操作为（B）
A. push,pop,push,pop,push,pop
B. push,push,push,pop,pop,pop
C. push,push,pop,pop,push,pop
D. push,pop,push,push,pop,pop
6. 若一个栈以向量V[1..n]存储，栈为空时栈顶指针top为n+1，则下面x进栈的正确操作是(C)。
A．top:=top+1; V [top]:=x
B. V [top]:=x; top:=top+1
C. top:=top-1; V [top]:=x
D. V [top]:=x; top:=top-1
7. 栈在（D）中应用。
A. 递归调用 B. 子程序调用 C. 表达式求值 D. A，Ｂ，Ｃ
8. 一个递归算法必须包括（B）。
A. 递归部分 B. 终止条件和递归部分 C. 迭代部分 D.终止条件和迭代部分
9. 用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点，则在进行删除操作时(D)。
A．仅修改队头指针（出队）B. 仅修改队尾指针（入队）
C. 队头、队尾指针都要修改(当只有一个结点的时候) D. 队头,队尾指针都可能要修改
10. 递归过程或函数调用时，处理参数及返回地址，要用一种称为（C）的数据结构。
A．队列 B．多维数组 C．栈 D. 线性表
11. 假设以数组A[m]存放循环队列的元素,其头尾指针分别为front和rear，则当前队列中的元素个数为（A）。
