算法与数据结构期末复习题

《算法与数据结构期末复习题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一、选择题/填空题：以基本概念基本性质为主数据元素的逻辑结构、物理结构；算法的时间复杂度、空间复杂度的概念；时间复杂度的简单计算（如i=1;While(i<=n)i=i*2;如fact(intn){if(n<=1)return1;elsereturn(n*fact(n-1));}）；线性表采用顺序存储结构时，任意元素ai的存储地址的计算；栈的概念（栈顶、栈底）、性质（LIFO）；队列的概念（队头、队尾）、性质（FIFO）、循环队列的特点（队列为空、满的条件）；后缀表达式计算（836*+235*+

2、4-/）；中缀、后缀表达式的相互转换（(8+3*6)/(2+3*5-4)）；树与二叉树的相关术语（根、兄弟、祖先、深度等）；二叉树的性质及扩展应用（对500个元素利用折半查找法进行查找时，其最大比较次数，n个结点的k叉树，可能达到的最大深度、最小深度，等）；二叉树的遍历；图与网的基本概念；图的遍历；最小生成树、最短路径、关键路径的概念；各种排序方法的比较（在待排序的元素序列基本有序的前提下，效率最高的排序方法，最不提倡使用的排序方法，排序方法中平均查找长度最小的方法，等）；各种查找方法的比较（如

3、果要求一个线性表既能快速的查找，又能适应动态变化的要求，可以采用的查找方法，等）。二、选择填空题以单链表的插入、删除操作为主：已知L是无表头结点的单链表，且P既不是首结点，也不是尾结点，请在下列语句中选择适当的语句序列填空。①P->next=S;②P->next=P->next->next;③P->next=S->next;④S->next=P->next;⑤S->next=L;⑥S->next=NULL;⑦Q=P;⑧While(P->next!=Q)P=P->next;⑨While(P->ne

4、xt!=NULL)P=P->next;⑩P=P->next;⑾P=L;⑿L=S;⒀L=P;a、在P结点后插入S结点b、在P结点前插入S结点c、在表首插入S结点d、在表尾插入S结点9已知L是带表头结点的非空单链表，且P既不是首结点，也不是尾结点，请在下列语句中选择适当的语句序列填空。①P=P->next;②P->next=P;③P->next=P->next->next;④P=P->next->next;⑤While(P!=NULL)P=P->next;⑥While(Q->next!=NULL){

5、P=Q;Q=Q->next;}⑦While(P->next!=Q)P=P->next;⑧While(P->next->next!=Q)P=P->next;⑨While(P->next->next!=NULL)P=P->next;⑩Q=P;⑾Q=P->next;⑿P=L;⒀L=L->next;⒁Free(Q);e、删除P结点的直接后继f、删除P结点的直接前趋g、删除P结点h、删除首结点i、删除尾结点三、补充算法/算法设计单链表的插入、删除算法；双链表的插入、删除算法；顺序栈的插入、删除算法；利用栈

6、进行数制转换的算法；二叉树遍历的算法；折半查找的算法；插入排序、起泡排序、快速排序算法。四、简答题9选择题1.算法分析的目的是①，算法分析的两个主要方面是②。①A.找出数据结构的合理性B.研究算法中的输入和输出的关系C.分析算法的效率以求改进D.分析算法的易懂性和文档性②A.空间复杂性和时间复杂性B.正确性和简明性C.可读性和文档性D.数据复杂性和程序复杂性2.计算机算法指的是①，它必具备输入、输出和②等五个特性。①A.计算方法B.排序方法C.解决问题的有限运算序列D.调度方法②A.可行性、可移

7、植性和可扩充性B.可行性、确定性和有穷性C.确定性、有穷性和稳定性D.易读性、稳定性和安全性3.一个向量（即一批地址连续的存储单元）第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是____。A.110B.108C.100D.1204.线性表的顺序存储结构是一种___的存储结构，而链式存储结构是一种___的存储结构。A．随机存取B．索引存取C．顺序存取D．散列存取5.线性表的逻辑顺序与存储顺序总是一致的，这种说法___。A.正确B.不正确6.线性表若采用链式存储结构时，要求内

8、存中可用存储单元的地址___。A.必须是连续的B.部分地址必须是连续的C.一定是不连续的D.连续或不连续都可以7.在以下的叙述中，正确的是___。A.线性表的顺序存储结构优于链表存储结构B.线性表的顺序存储结构适用于频繁插入/删除数据元素的情况C.线性表的链表存储结构适用于频繁插入/删除数据元素的情况D.线性表的链表存储结构优于顺序存储结构8.每种数据结构都具备三个基本运算：插入、删除和查找，这种说法___。A.正确B.不正确9.不带头结点的单链表head为空的判定条件是____。A.head=