文档介绍：一、简答问题:(每小题4分,共16分)
四类数据结构
线性结构与非线性结构有何差别?
简述算法的定义与特性。
设有1000个无序元素,仅要求找出前10个最小元素,在下列排序方法中(归并排序、基数排序、快速排序、堆排序、插入排序)哪一种方法最好,为什么?
二、判断正误:(每小题1分,共5分)
正确在( )内打√,否则打r 。
( )二叉排序树或是一棵空树,或是具有下列性质的二叉树:
若它的左子树非空,则根结点的值大于其左孩子的值,
若它的右子树非空,则根结点的值大于其右孩子的值。
( )索引顺序表的特点是块内可无序,块间要有序。
( )子串是主串中任意个连续字符组成的序列。
( )线性结构只能用顺序结构存放,非线性结构只能用链表存放。
( )快速排序的枢轴元素可以任意选定。
三、单项选择题:(每小题1分,共4分)
。现有6个元素按A、B、C、D、E、F的顺序进栈, 问下列哪一个序列是可能的出栈序列?
A)E、D、C、B、A、F B)B、C、E、F、A、D
C)C、B、E、D、A、F D)A、D、F、E、B、C
,每一层从左到右依次对结点进行编号,根结点编号为1,则编号为49的结点的左孩子的编号为:
A、98 B、99 C、50 D、48
3. 对下列关键字序列用快速排序法进行排序时,速度最快的情形是:
A){21、25、5、17、9、23、30} B){25、23、30、17、21、5、9}
B){21、9、17、30、25、23、5} D){5、9、17、21、23、25、30}
4. 设森林F中有三棵树,第一、第二和第三棵树的结点个数分别为M1、M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是:
A)M1 B)M1+M2 C)M3 D)M2+M3
四、填空题:(每小题2分,共 20分)
设一哈希表表长M为100 ,用除留余数法构造哈希函数,即H(K)=K MOD P(P<=M), 为使函数具有较好性能,P应选
N个结点的二叉树采用二叉链表存放,共有空链域个数为
单链表与多重链表的区别是
在各种查找方法中,平均查找长度与结点个数无关的是
深度为6(根层次为1)的二叉树至多有个结点。
已知二维数组A[20][10]采用行序为主方式存储,每个元素占2个存储
单元,并且A[10][5]的存储地址是1000,则A[18][9]的存储地址是
在一个单链表中p所指结点之后插入s所指结点时,应执行
s->next= 和p->next= 的操作.
((a,b),c,d)的表头是,表尾是
,指针P所指结点为表尾结点的条件是
,只有很少量元素不在自己最终的正确位置上,但离他们的正确位置都不远,则使用排序方法最好。
五、构造题:(每小题5分,共25分)
已知一棵二叉树,其中序序列DBCAFGE,后序序列DCBGFEA,构造该二叉树。
设哈希表长度为11,哈希函数H(K)=(K的第一字母在字母表中的序号)
MOD11,若输入顺序为(D,BA,TN,M,CI,I,K,X,TA),处理冲突方法为线性探测再散列或链地址法,要求构造哈希表,并求出等概率