数据结构典型习题
- 格式：doc
- 大小：1.36 MB
- 文档页数：10
第一章
算法的时间复杂度取决于（ ）
A．问题的规模 B. 待处理数据的初态 C. A和B
从逻辑上可以把数据结构分为（ ）两大类。
A．动态结构、静态结构 B．顺序结构、链式结构
C．线性结构、非线性结构 D．初等结构、构造型结构
下列程序段的时间复杂度为( )。
{ for(i=0；i<5；i++)
for(j=0；j
x=x+1；
}
A.O(5) B.O(5+n) C.O(n5 ) D.O(n)
第二章
当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_______存储结构。
顺序存储结构是通过________表示元素之间的关系的;链式存储结构是通过________表示元素之间的关系的。
编程实现线性链表的基本操作如
GetElem（）,ListInsert(),
ListDelete(),CreateList()，MergeList（）等。
第三章
对于栈操作数据的原则是（ ）。
A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序
有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（ ）
A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6
设栈的输入序列是1，2，3，4,则（ ）不可能是其出栈序列。
A. 1，2，4，3， B. 2，1，3，4， C. 1，4，3，2，
D. 4，3，1，2， E. 3，2，1，4，
表达式3* 2^(4+2*2-6*3)-5求值过程中当扫描到6时，对象栈和算符栈为（ ），其中^为乘幂 。
A. 3,2,4,1,1；(*^(+*- B. 3,2,8；(*^-
C. 3,2,4,2,2；(*^(- D. 3,2,8；*^(-
第四章
下面关于串的的叙述中，哪一个是不正确的？（ ）
A．串是字符的有限序列
B．空串是由空格构成的串
A．模式匹配是串的一种重要运算
D．串既可以采用顺序存储，也可以采用链式存储
设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（ ）
A．求子串 B．联接 C．匹配 D．求串长
串的长度是指（ ）
A．串中所含不同字母的个数 B．串中所含字符的个数
C．串中所含不同字符的个数 D．串中所含非空格字符的个数
第五章
对稀疏矩阵进行压缩存储目的是（ ）。
A.便于进行矩阵运算 B．便于输入和输出
C．节省存储空间 D．降低运算的时间复杂度
设广义表L=（（a,b,c）），则L的长度和深度分别为（ ）。
A. 1和1 B. 1和3 C. 1和2 D. 2和3
广义表A=(a,b,(c,d),(e,(f,g))),则下面式子的值为（ ）。
Head(Tail(Head(Tail(TailA))))
A. (g) B. D C. c D. d
第六章 树和二叉树
一、选择题
1．树最适合用来表示（ ）。
A. 有序数据元素 B. 无序数据元素
C. 元素之间具有分支层次关系的数据 D. 元素之间无联系的数据
2．深度为5的二叉树至多有（ ）个结点。
A． 16 B． 32 C． 31 D． 10
3．有32个结点的完全二叉树的深度为（ ）（根的层次为1）。
A．8 B．7 C．6 D．5
4．若二叉树中度为2的结点有15个，度为1的结点有10个，则有（ ）个叶结点。
A．25 B．15 C．16 D．41
6．有64个结点的完全二叉树的深度为（ ）（根的层次为1）。
A．8 B．7 C．6 D．5
7．对含有（ ）个结点的非空二叉树，采用任何一种遍历方式，其结点访问序列均相同。
A． 3 B． 1 C． 2 D． 不存在
8．某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（ ）二叉树。
A． 空或只有一个结点 B． 高度等于其结点数
C． 任一结点无左孩子 D． 任一结点无右孩子
9．前序遍历与中序遍历结果相同的二叉树为（ ）；前序遍历和后序遍历结果相同的二叉树为（ ）。
A．一般二叉树 B．只有根结点的二叉树
C．根结点无左孩子的二叉树 D．根结点无右孩子的二叉树
E．所有结点只有左子树的二叉树 F．所有结点只有右子树的二叉树
14．设高度为h的二叉树上只有度为0和度为2的结点，则此二叉树中所含的结点数至少为（ ）。
A． 2h B． 2h-1 C． 2h+1 D． h+1
16．设一棵二叉树中没有度为1的结点，已知叶子结点数为n，此树的结点数为（ ）。
A．2n+2 B． 2n+1 C． 2n D． 2n-1
17．设哈夫曼树的叶子结点数为n，则它的结点总数为（ ）。
A． 2n-1 B． 2n C． 2n+1 D． 不确定
18．由带权9、1、3、5、6的5个叶子结点生成的哈夫曼树的带权路径长度为（ ）。 A． 50 B． 60 C. 52 D. 65
19．二叉树的先序遍历序列和中序遍历序列分别为：EFHIGJK和HFIFJKG,该二叉树根的右子树的根是（ ）。
A． E B． F C. G D. H
21．二叉树上叶结点数等于（ ）。
A． 分支结点数加１ B． 单分支结点数加１
C. 双分支结点数加１ D. 双分支结点数减１
二、填空题
1. 具有n个结点的完全二叉树的深度为 。
2. 二叉树第i层上最多有 个结点。
3. 深度为k的二叉树最多有 个结点
7．分别画出和下列树对应的二叉树。
A B
8．画出和下列二叉树相应的森林。
A B
9．以数据集{4，5，6，7，10，12，18}为结点权值构造的Huffman树，并求其带权路径长度。
10．假设一棵二叉树的先序序列为EBADCFHGIKJ和中序序列为ABCDEFGHIJK，请画出该树并给出其后序序列。
12. 已知某二叉树按后序遍历序列为CEDBHJIGFA，按中序遍历序列为CBEDAHGIJF,试画出该二叉树形状（要求写出中间过程）， 并写出它的先序遍历序列。
13. 设a,b,c,d,e,f六个字母出现的次数分别为7,19,2,6,32,3,试为这六个字母设计huffman编码并画出对应huffman树。
14. 对给出的数据序列4,5,6,7,10,12,15,18,23，构造一棵huffman树，并求其带权路径长度。
15．设a,b,c,d,e,f,g,h,i九个字母出现的次数分别为4,5,6,7,10,12,15,
18,23，构造一棵huffman树，并给出每个字符的huffman编码。
16. 设一棵二叉树的先序、中序遍历序列分别为EBADCFHGIKJ和ABCDEFGHIJK，要求：(1) 画出该二叉树(要求写出中间步骤); (2)将这棵二叉树转换成对应的树(或森林)。
17.设一份电文中a,b,c,d,e,f,g,h八个字母出现的次数分别为7,19,2,6,32,3,21, 10, 要求： (1) 为每个字母设计huffman编码, (2) 给出八个字母二进制表示的等长编码并比较两方案的优缺点。
18.编程实现二叉树的三种遍历方法，并统计特殊元素，如最大值，最小值,和值，终端节点。
第七章 图
1．在一个具有n个顶点的无向图中，要连通全部顶点至少需要的边数为( )
A.n-1 B.n C.n+1 D.n*2
2．7. 有n个顶点e条边的无向图G,它的邻接表中的表结点总数是( )
A． 2n B．n C． 2e D． e
3．有4个顶点的无向完全图的边数为( )
A.6 B.12 C.16 D.20
4．具有n个叶结点的赫夫曼树共有 个结点
5．N个顶点的连通图的生成树有 条边。
6．图的深度、广度优先遍历算法分别类似于二叉树的（ ）。
A. 先序遍历和中序遍历 B. 先序遍历和层序遍历
C. 后序遍历和中序遍历 D. 层序遍历和先序遍历
7．
若某无向图G的邻接表如图所示，试给出以顶点V1为出发点，按深度、广度优先搜索所产
生的一棵生成树。
8．下图为一无向连通网络，分别根据普里姆(Prim)算法和克鲁斯卡尔(Kruscal)算法从顶点１出发构造出它的最小生成树。（要求写出求解步骤）。
