数据结构与算法的习题

1、2、单项选择题 ：（本大题共 20 小题，每题 2 分，共 30 分）（说明： 将答案写在试卷后面的答题纸上）分数评卷人1计算机识别、存储和加工处理的对象被统称为（A.数据B.数据元素C.数据结构D.数据类型2在具有 n 个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是（ ）A.O（1）C.O（ nlogn）3.队和栈的主要区别是（A.逻辑结构不同C.所包含的运算个数不同4.链栈与顺序栈相比，比较明显的优点是A.插入操作更加方便C.不会出现下溢的情况5下列说法中正确的是（）A.B.C.B.O( n)D.O (n2)B.存储结构不同D.限定插入和删除的位置不同B.删除操作更加方便

2、D.不会出现上溢的情况二叉树中任何一个结点的度都为2二叉树的度为 2任何一棵二叉树中至少有一个结点的度为一棵二叉树的度可以小于 2D.6在一非空二叉树的中序遍历序列中，根结点的右边（）A.B.C.只有右子树上的所有结点只有右子树上的部分结点只有左子树上的所有结点只有左子树上的部分结点D.7在一个具有 N 个顶点的无向完全图中，包含的边的总数是（）A.B.C.N(N-1)/2N(N-1)N(N+1)N(N+1)/2D.8下面的程序在执行时，S 语句共执行的（）次。i=1;while （i=n）for（j=i;j n;j+）S；i=i+1;A. n(n+1)/2B. n(n-1)/2C. n!D.

3、n9设二叉树有A. n-1n 个结点，则其深度为（）B. nC. 5log2n+1D.不确定210已知一棵二叉树结点的先根序列为ABDGCFK，中根序列为 DGBAFCK，则结点的后根序列为（）A. ACFKBDG B. GDBFKCA C. KCFAGDB D. ABCDFKG11. 任何一个带权的无向连通图的最小生成树（）A.只有一棵 B.有一棵或多棵C. 一定有多棵D.可能不存在12.已知某二叉树的后序遍历序列是dabec,中序遍历序列是debac,则它的前序遍历序列是 （）A.acbedB.decabC. deabcD.cedba13.设深度为 k 的二叉树上只有度为 0 和度为 2

4、的结点，则这类二叉树上所含结点总数量是（C）个A. k+1B. 2kC. 2k-114.下面程序的时间复杂性是()For(i=1;i=n ;i+)For(j=1;j=n ;j+) aij=i*j;2 2A. O(m)B. 0(n)C. O(m*n)15. 含 N 个顶点的连通图中的任意一条简单路径，其长度不可能超过（）A. 1B. N/2C. N-1D. N16. 下列说法正确的是（A）A. 树的先根遍历序列与其对应的二叉树的先根遍历序列相同B. 树的先根遍历序列与其对应的二叉树的后根遍历序列相同C. 树的后根遍历序列与其对应的二叉树的先根遍历序列相同D. 树的后根遍历序列与其对应的二叉树的后

5、根遍历序列相同17. 对于一个具有 N 个结点和 E 条边的无向图，若采用邻接表示，则表头向量的大小是 （A）A. NB. N+1C. N-ED. N-118. 判断一个有向图是否存在回路，除了可以利用拓扑排序方法，还可以利用（）A. 求关键路径的方法B. 求最短路径的 Dijkstra 方法C. 广度优先遍历方法D. 深度优先遍历方法19. 一个队列的输入序列是1,2,3,4,则队列的输出序列是（）（1）在线性表中插入或删除一个元素，需要平均移动 与 有关。（2） 顺序表中逻辑上相邻的元素的物理位置 _紧邻，单链表中逻辑上相邻的元素物理位 置紧邻。（3） 在单链表中，除了首元结点外，任意结点的存储位置由 _指示。（4） 记录的 _结构是数据在物理存储器上的存储方式。D.2k+1D. O(m+n)A,4,3,2,1B.1,2,3,4C.1,4,3,220.任何一个带权的无向连通图的最小生成树（B）A.只有一棵B.有一棵或多棵C. 一定有多棵、填空题（本大