数据结构与算法的习题

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

1、答案为网上下载，有错的跟我说声哈，有的没答案，自己看看，不会的跟我说一下发给老师。一、单项选择题：（本大题共20小题，每题2分，共30分）（说明：将答案写在试卷后面的答题纸上）分数评卷人1.计算机识别、存储和加工处理的对象被统称为(D)A.数据B.数据元素C.数据结构D.数据类型2.在具有n个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是(B)A.O(1)B.O(n)C.O(nlogn)D.O(n2)3.队和栈的主要区别是(D)A.逻辑结构不同B.存储结构不同C.所包含的运算个数不同D.限定插入和删除的位置不

2、同4.链栈与顺序栈相比，比较明显的优点是(D)A.插入操作更加方便B.删除操作更加方便C.不会出现下溢的情况D.不会出现上溢的情况5.下列说法中正确的是（D）A.二叉树中任何一个结点的度都为2B.二叉树的度为2C.任何一棵二叉树中至少有一个结点的度为2D.一棵二叉树的度可以小于26.在一非空二叉树的中序遍历序列中，根结点的右边（A）A.只有右子树上的所有结点B.只有右子树上的部分结点C.只有左子树上的所有结点D.只有左子树上的部分结点7.在一个具有N个顶点的无向完全图中，包含的边的总数是（A）A.N(N-1)/2B.N(N-

3、1)C.N(N+1)D.N(N+1)/28.下面的程序在执行时，S语句共执行的（B）次。i=1;while(i<=n){for(j=i;j

4、B）A.只有一棵B.有一棵或多棵C.一定有多棵D.可能不存在12.已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，则它的前序遍历序列是（D）A.acbedB.decabC.deabcD.cedba13.设深度为k的二叉树上只有度为0和度为2的结点，则这类二叉树上所含结点总数量是（C）个A.k+1B.2kC.2k-1D.2k+114.下面程序的时间复杂性是（B）For(i=1;i<=n;i++)For(j=1;j<=n;j++){a[i][j]=i*j;}A.O()B.O()C.O(m*n)D.O(m+n)1

5、5.含N个顶点的连通图中的任意一条简单路径，其长度不可能超过（C）A.1B.N/2C.N-1D.N16.下列说法正确的是（A）A.树的先根遍历序列与其对应的二叉树的先根遍历序列相同B.树的先根遍历序列与其对应的二叉树的后根遍历序列相同C.树的后根遍历序列与其对应的二叉树的先根遍历序列相同D.树的后根遍历序列与其对应的二叉树的后根遍历序列相同17.对于一个具有N个结点和E条边的无向图，若采用邻接表示，则表头向量的大小是(A)A.NB.N+1C.N-ED.N-118.判断一个有向图是否存在回路，除了可以利用拓扑排序方法，还可以利

6、用（D）A.求关键路径的方法B.求最短路径的Dijkstra方法C.广度优先遍历方法D.深度优先遍历方法19.一个队列的输入序列是1,2,3,4，则队列的输出序列是（B）A,4,3,2,1B.1,2,3,4C.1,4,3,2D.3,2,4,120.任何一个带权的无向连通图的最小生成树（B）A.只有一棵B.有一棵或多棵C.一定有多棵D.可能不存在得分评卷人复查人一、二、填空题（本大题共10小题，每小题1分，共10分）请在每小题的空格中填上正确答案。错填、不填均无分。（1）在线性表中插入或删除一个元素，需要平均移动n/2元素，具

7、体移动的元素个数与插入或删除位置有关。（2）顺序表中逻辑上相邻的元素的物理位置要求紧邻，单链表中逻辑上相邻的元素物理位置不要求紧邻。（3）在单链表中，除了首元结点外，任意结点的存储位置由指针指示。（4）记录的存储结构是数据在物理存储器上的存储方式。（5）在非空队列中，头指针始终指向队首，而尾指针始终指向队尾。（6）N个顶点的连通图，至少有N-1条边。（7）对于一个长度为n的线性表，假设表中各结点的查找概率相同，则在查找成功的情况下，平均查找长度为n/2，如果k不在表中，则需要进行n次比较后才能确定查找失败。(8)在二叉排序树

8、中，其左子树中任何一个结点的关键字一定小于其右子树的各结点的关键字。（9）已知无向图G的结点数为n，边数为e，其邻接表表示中的表结点数与表头结点数之和为n+2e。（10）若二叉树的一个叶子是某子树的中序遍历序列中的第一个结点，则它必是孩子树的后序遍历序中的第一个个结点。（11）有m个叶子结