数据结构模拟试题

《数据结构模拟试题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2002年数据结构模拟试题（一）一、单项选择题（本大题共14小题，每小题1分，共14分）1.下面程序的时间复杂性为：()。for(i=1;i<=n;i++)for(j=1;j<=m;j++){A［i］［j］=i*j;}AO(m2) BO(n2) CO(m*n) DO(m+n)2.在一个长度为n的顺序表（顺序存储的线性表）中，向第i个元素(1≤i≤n+1)之前插入一个新元素时，需向后移动()个元素。A.n-iB.n-i+1C.n-i-1D.i3.单链表中，增加头结点的作用是()。A.方便运算的实现B.用于标志单链表

2、C.使单链表中至少有一个结点D.用于标志起始结点4.在一个单链表中，删除p所指的直接后继的操作是()。A.p—>next=p—>next—>nextB.p=p—>next—>nextC.p=p—>next D.p—>next=p—>next—>next5.非空的循环单链表head的尾结点（由指针p所指）满足()。A.p—>next=NULL B.p—>next=head C.p=NULL D.P=head6.对于一个具有N个顶点的图，如果我们采用邻接矩阵法表示，则此矩阵的维数应该是()。A.(N-1)×(N-1) B.

3、N×N C.(N+1)×(N+1) D.不确定 7.在一个具有N个顶点的无向完全图中，包含的边的总数是()。A.N(N-1)/2 B.N(N-1) C.N(N+1) D.N(N+1)/2 8.对于一个具有N个结点和E条边的无向图，若采用邻接表表示，则表头向量的大小是()。A.N B.N+1 C.N-E D.N-19.判断一个有向图是否存在回路的方法中，除了可以利用拓扑排序方法外，还可以利用的方法是()。A求最短路径的方法 B求关键路径的方法 C深度优先遍历的方法 D广度优先遍历的方法10.一个具有N个顶点的有向

4、图最多有()条边。A.N(N-1)/2 B.N(N-1) C.N(N+1) D.N(N+1)/2 11.下面的查找方式中，可以对无序表进行查找的是()。A.顺序查找B.二分查找C.二叉排序树D.B-树上的查找12.散列表的目的是()。A.插入B.删除C.快速查找D.排序13.长度为n的线性表，若各个结点的查找的概率相同，则在查找成功的情况下，其平均查找长度为()。A.nB.n(n+1)/2C.(n-1)/2D.(n+1)/214.用二分查找方法查找长度为n的线性表时，每个元素的平均查找长度为()。A.O(n)B.O(l

5、og2n)C.O(n)D.O(1)二、判断题（本大题共10小题，每小题2分，共20分）1.顺序存储的数组是一个随机存取结构。2.将一个对角阵按照行优先或者对角线的顺序压缩到一个向量中时，对应的存储结构是一种随机的存取结构。3.纯表中的成分可以进行递归和共享。4.从树的根结点到树中其余结点均存在一条惟一的路径。 5.在一棵有序树中，如果k1和k2是兄弟，且k1在k2左边，则k1的任何一个子孙都在k2任何一个子孙的左边的。 6.一棵深度为k且有2k-1个结点的二叉树叫做满二叉树。 7.满二叉树一定是完全二叉树，并且完全二叉

6、树也一定是满二叉树。 8.完全图中具有最多的边数，且在图中，每个顶点之间均有边相连。 9.若V（G）中有两个不同的顶点和是连通的，则G就称为是连通图。 10.任何图的连通分量只有一个。 三、填空题（本大题共10小题，每小题3分，共30分）1.数据的存储结构可用如下四种基本的存储方法得到：（1）()(2)()（3）()（4）()。2.评价一个算法的时间性能时，主要标准是()。3.数据的逻辑结构是从()上描述数据，它与数据的存储无关，是独立于计算机的。因此，数据的逻辑结构可以看作是()存储结构是()，它是依赖于计算机语言的

7、；数据的运算是定义在数据的()结构上的。4.在顺序队列中，应该有队头和队尾两个指针来指示，队头指针和队尾指针的初值在队列的初始化时均应该设置为()，当对队列进行插入和删除的操作后，如果头指针和尾指针相等时，队列为()。5.向栈中压入元素的操作是()。对栈进行出栈时的操作是()。6.在具有n个存储单元的队列中，队满时队中共有()个元素。7.假设有一个顺序栈A，其中元素a1,a2,a3,a4,a5,a6依次进栈，如果已知六个元素出栈的顺序是a2,a3,a4,a6,a5,a1,则此栈容量至少应该为()。8.对于长度为n的顺序

8、表，插入或删除元素的时间复杂性为（）。9.向顺序表中第i个元素之前插入一个新元素时，首先从()，开始向后的所有元素均要()一个位置，接着把新元素写入()上，最后使线性表的长度()。10.从顺序表中删除第i个元素时，首先把第i个元素赋给()带回，接着从开始向后的所有元素均()一个位置，最后使线性表的长度()。四、问答题（本大题共4小