算法与数据结构复习(0910)

《算法与数据结构复习(0910)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、算法与数据结构复习题（0910）基本要求1．算法与数据结构基本概念（1）数据、数据对象和数据结构（2）抽象数据类型（3）算法的特征及评价的标准（4）数据的存储结构类型2．线形结构（1）顺序表的特点及存储结构（2）链表的特点及存储结构（3）栈的特点及基本操作（4）队列的特点及基本操作（5）顺序串和链串的存储结构（6）二维数组的地址计算（7）稀疏矩阵的概念及存储结构（8）线性表的排序（插入、选择和交换）（9）线性表的查找（顺序、折半和分块）3．树形结构（1）二叉树的性质及存储结构（2）二叉树的遍历（3）线索二叉树（4）树的存储结

2、构（5）树、二叉树与森林的转化方法（6）哈夫曼树（7）二叉排序树及平衡化（8）堆排序树（9）B-树4．图形结构（1）图的定义及存储结构（2）图的深度优先和广度优先遍历。（3）无向图的连通性和最小生成树（4）拓扑排序（5）关键路径（6）单源最短路径5．散列表（哈希表）（1）散列表的概念（2）散列表解决散列冲突的方法（开放地址法、链地址法）（3）散列表的插入和删除6．算法分析与设计基础（1）分治与递归的关系（2）贪心算法的思想（3）回溯与分支限界算法的比较（4）算法时间和空间复杂度的简单分析16一、单选题1．数据结构被形式地定义

3、为（D,R），其中D是A.算法B.操作的集合C.数据元素的集合D.数据关系的集合2．顺序表是线性表的A.顺序存储结构B.链式存储结构C.索引存储结构D.散列存储结构3．下列程序段for(i=1;i<=n;i++)A[i,j]=0;的时间复杂度是A.O(1)B.O(0)C.O(1+n)D.O(n)4.若线性表中最常用的操作是取第i个元素和查找该元素的前驱，则采用最能节省时间的存储方式是A.顺序表B.单链表C.双链表D.循环链表5．在n个结点的顺序表中删除一个结点，至少要移动的结点个数为A.nB.0C.n/2D.16．在一个单链

4、表中，若删除*p结点的后继结点，则执行操作A.q=p->next;p->next=q->next;free(q);B.p=p->next;p->next=p->next->next;free(p);C.p->next=q->next;free(p->next);D.p=p->next->next;free(p->next);7．在一个单链表中，已知*p结点不是最后结点，若在*p之后插入结点*s，则执行操作A.s->next=p;p->next=s;B.s->next=p->next;p->next=sC.s->next=p-

5、>next;p=s;D.p->next=s;s->next=p;8．设指针p指向双链表的某一结点，则双链表结构的对称性可以用下面的操作来反映A.p->prior->next=p->next->next;B.p->prior->prior=p->next->prior;C.p->prior->next=p->next->prior;D.p->next->next=p->prior->prior;9．如果以链栈为存储结构，则出栈操作时A．必须判栈满B．必须判别栈空C.判别栈中元素类型D.不必作任何判别10．设有一个顺序栈，6个元

6、素1、2、3、4、5、6依次入栈，如果6个元素出栈的顺序是2、3、4、6、5、1，则栈的容量至少应该是A．2B．3C.5D.611．设一个栈的输入序列为A，B，C，D，则借助一个栈所得到的输出序列不可能是A．A，B，C，DB．D，C，B，AC.A，C，D，BD.D，A，B，C12．循环队列A[O..m-1]存放其元素值，用front和rear分别表示队头及队尾，则循环队列满的条件是A．(Q.rear+1)％m==Q.frontB．Q.rear==Q.front+1C．Q.rear+l=Q.frontD．Q.real==Q.f

7、ront13．循环队列A[0．．m—1]存放其元素值，用front和rear分别表示指向队头及队尾元素的指针，则当前队列中的元素数是A．(rear-front+1+m)％mB．(rear-front+1)C．(rear-front+m)％m+1D．(rear-front+1+m)％m14．稀疏矩阵一般的压缩存储方法有两种，它们是用A．二维数组和三维数组B．三元组和散列表C．三元组和十字链表D．哈希表和十字链表15．对矩阵压缩存储是为了A.方便运算B.节省空间C.方便存储D.提高运算速度16．二维数组A的每个元素是由6个字符组

8、成的串，其行下标i=0，l，…，8，列下标为j=1，2．…．10。设每个字符占一个字节,若按行先存储，元素A[8，5]的起始地址与A按列存储时起始地址相同的元素是A．A[8，5]B．A[3，10]C．A[5，8]D．A[0，9]17．字符串通常采用的两种存储方式是A.散列存储和索引存储B.