一、选择题
1、 下列关于数据和逻辑结构的叙述中，哪一个是不正确的（Ｃ ）。
A ) 数据的逻辑结构是数据间关系的描述 B) 数据的逻辑结构抽象反映数据元素间的逻辑关系
C) 数据的逻辑结构具体反映数据在计算机中的存储方式 D) 数据的逻辑结构分为线性结构和非线性结构
2、 以下关于数据的存储结构的叙述中哪一条是正确的（Ｂ ）。
A) 数据的存储结构是数据间关系的抽象描述 B) 数据的存储结构是逻辑结构在计算机存储器中的实现
C) 数据的存储结构分为线性结构和非线性结构 D) 数据的存储结构对数据运算的具体实现没有影响
3、由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，这种说法 B .
（A）正确 （B）错误
4、某二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树一定是
(A)空或只有一个结点 (B) 完全二叉树
(C)二叉排序树 (D) 高度等于其节点数
5、深度为5的二叉树至多有 C 多少个结点.
(A)16 (B)32 (C)31 (D)10
6、根据使用频率为5个字符设计的哈夫曼编码不可能是 C
（A）111，110，10，01，00 （B）000，001，010，011，1
（C）100，11，10，1，0 （D）001，000，01，11，10
7、一个n个顶点的无向图最多有 条边。
(A) n (B) n(n-1) (C) n(n-1)/2 (D) 2n
8、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 倍。
（A）1/2 （B）1 （C）2 （D）4
9、关键路径是事件结点网络中 。
（A）从源点到汇点的最长路径 （B）最长的回路
（C）从源点到汇点的最短路径 (D）最短的回路
10、下面不正确的说法是 。
A、关键活动不按期完成就会影响整个工程的完成时间
B、任何一个关键活动提前完成，将使整个工程提前完成
C、所有关键活动都提前，则整个工程提前完成
D、某些关键活动若提前完成，将使整个工程提前完成。
11、采用顺序查法查长度为n的线性表时，则查成功时的平均查长度为 C 。
(A) n (B) n/2 (C) (n+1)/2 (D) (n-1)/2
12、在一个长度为12的有序表，按折半查法对该表进行查，在表内各元素等概率情况下查成功所需的平均比较次数为 B 。
（A）35/12 （B）37/12 （C）39/12 （D）43/12
13、查效率最高的二叉排序树是 C 。
（A）所有结点的左子树都为空的二叉排序树 （B）所有结点的右子树都为空的二叉排序树
（C）平衡二叉树 （D）没有左子树的二叉排序树
14、以下说法错误的是 B 。
A、散列法存储的基本思想是由关键码值决定数据的存储地址
B、散列表的结点中只包含数据元素自身的信息，不包含任何指针
C、装填因子是散列法的一个重要参数，它反映了散列表的装填程度
D、散列表的查效率主要取决于散列表造表时选取的散列函数和处理冲突的方法
15、散列表的平均查长度 A 。
A.与处理冲突方法有关与表长无关 B.与处理冲突方法无关与表的长度有关
C.与处理冲突方法有关且与表的长度有关 D.与处理冲突方法无关且与表的长度无关
二、填空题
1、树和二叉树的主要差别是 ， 。（1）每个结点最多有两棵子树； （2）子树有左右之分
2、深度为k的完全二叉树至少有 个结点，至多有＿ 个结点。2k-1, 2k-1,
3、一棵二叉树的第i(i 1)层最多有 个结点；一棵有n（n>0）个结点的满二叉树共有 个叶子结点和个非叶子结点。 (n+1)/2,(n-1)/2
4、假设一棵二叉树的结点数为33个，则它的最小高度为（ ），最大高度为（ ）。
最小高度为：6，最大高度为：33
5、一个高度为h的满m叉树，第k层最多有（ ）个结点，整棵树最多有（ ）个结点。
第k层最多有 mk-1,整棵树最多有(mk-1)/m-1
6、一个图的 表示法是唯一的，而 表示法是不唯一的。
7、在有n个顶点的有向图中，每个顶点的度最大可达
8、设线性表（a1，a2，…，a500）元素的值由小到大排列，对一个给定的k值用折半法查线性表，在查不成功的情况下至多需比较 （ log2n +1 ）次
9、一个无序序列可以通过构造一棵 二叉排序树 树而变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。
10、在散列存储中，装填因子ａ的值越大，则 ；ａ的值越小，则 .。
发生冲突的可能性就越大；发生冲突的可能性就越小；
二、简答题
1 数据结构的存储方式有哪几种？
常用的存储表示方法有四种 :
1 、顺序存储方法：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构，通常借助程序语言的数组描述。
2 、链接存储方法：它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示。由此得到的存储表示称为链式存储结构 , 通常借助于程序语言的指针类型描述。
3 、索引存储方法：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。组成索引表的索引项由结点的关键字和地址组成。若每个结点在索引表中都有一个索引项，则该
索引表称之为稠密索引（ Dense Index ）。若一组结点在索引表中只对应一个索引项，则该索引表称为稀疏索引。
4 、散列存储方法：就是根据结点的关键字直接计算出该结点的存储地址。
2 算法的时间复杂度仅与问题的规模相关吗 ?
【解析】 算法的时间复杂度不仅与问题的规模相关，还与输入实例中的初始状态有关。但在最坏的情况下，其时间复杂度就是只与求解问题的规模相关的。我们在讨论时间复杂度时，一般就是以最坏情况下的时间复杂度为准的。
3、设n为正整数，利用大"O"记号，将下列程序段的执行时间表示为n的函数。
先序中序后序遍历二叉树(1) i=1; k=0;
while(i<n)
{ k=k+10*i;i++;
}
（1）分析：
i=1; //1
k=0; //1
while(i<n) //n
{ k=k+10*i; //n-1
i++; //n-1
}
由以上列出的各语句的频度，可得该程序段的时间消耗：
T(n)=1+1+n+(n-1)+(n-1)=3n
可表示为T(n)=O(n)
(2) i=0; k=0;
do{
k=k+10*i; i++;
}
while(i<n);
（2）分析：
i=0; //1
k=0; //1
do{ //n
k=k+10*i; //n
i++; //n
}
while(i<n);//n
由以上列出的各语句的频度，可得该程序段的时间消耗：
T(n)=1+1+n+n+n+n=4n+2
可表示为T(n)=O(n)
(3) i=1; j=0;
while(i+j<=n)
{
if (i>j) j++;
else i++;
}
分析：
通过分析以上程序段，可将i+j看成一个控制循环次数的变量，且每执行一次循环，i+j的值加1。该程序段的主要时间消耗是while循环，而while循环共做了n次，所以该程序段的执行时间为：T(n)=O(n)
(4)x=n; // n>1
while (x>=(y+1)*(y+1))
y++;
分析：由x=n且x的值在程序中不变，又while的循环条件(x>=(y+1)*(y+1))可知：当(y+1)*(y+1)刚超过n的值时退出循环。由(y+1)*(y+1)<n得：y<n^0.5-1所以，该程序段的执行时间为：向下取整(n^0.5-1)
4、设三个函数f,g,h分别为 f(n)=100n3+n2+1000 , g(n)=25n3+5000n2 , h(n)=n1.5+5000nlgn 请判断下列关系是否成立：
(1) f(n)=O(g(n)) (2) g(n)=O(f(n)) (3) h(n)=O(n1.5) (4) h(n)=O(nlgn) 通俗地
说，就是当n→∞时，f(n)的函数值增长速度与T（n)的增长速度同阶。一般，一个函数的增长速度与该函数的最高次阶同阶。
即：O(f(n))=n3 O(g(n))=n3 O(h(n))=n1.5
答：●（1）成立。 ●（2）成立。●（3）成立。●（4）不成立。
5 何时选用顺序表、何时选用链表作为线性表的存储结构为宜?
6在顺序表中插入和删除一个结点需平均移动多少个结点?具体的移动次数取决于哪两个因素?
7为什么在单循环链表中设置尾指针比设置头指针更好?
尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查链表的开始结点和终端结点都很方便，设一带头结点的单循环链表，其尾指针为rear，则开始结点和终端结点的位置分别是rear->next->next 和 rear, 查时间都是O(1)。 若用头指针来表示该链表，则查终端结点的时间为O(n)。
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论