一单项选择题(本大题共小题每小题分共分)
在每小题列出的四个备选项中只有一个是符合题目要求的请将其代码填写在题后的括号内错选多选或未选均无分
数据的四种基本逻辑结构是指( )
A数组链表树图形结构 B线性表链表栈队列数组广义表
C线性结构链表树图形结构 D集合线性结构树图形结构
数据结构中通常采用两种方法衡量算法的时间复杂性即( )
A最大时间复杂性和最小时间复杂性
B最好时间复杂性和最坏时间复杂性
C部分时间复杂性和总体时间复杂性
D平均时间复杂性和最坏时间复杂性
下列关于线性表的叙述中不正确的是( )
A线性表是n个结点的有穷序列
B线性表可以为空表
C线性表的每一个结点有且仅有一个前趋和一个后继
D线性表结点间的逻辑关系是:的联系
在一个单链表中若p所指结点不是最后结点则删除p所指结点的后继结点的正确操作是( )
Ap=p>next Bp>next=p>next
Cp>next=p>next>next Dp>next=p
栈和队列( )
A共同之处在于二者都是先进先出的特殊的线性表
B共同之处在于二者都是先进后出的特殊的线性表
C共同之处在于二者都只允许在顶端执行删除操作
D没有共同之处
二维数组A[][]采用按列为主序的存储方式每个元素占个存储单元若A[][]的存储地址是则A[][]的存储地址是( )
A B
C D
深度为k的二叉树至多有( )
Ak个结点 Bk个结点
Ck个结点 Dk个结点
对于如图所示二叉树采用中根遍历正确的遍历序列应为( )
AABCDEF BABECDF
CCDFBEA DCBDAEF
下面关于生成树的描述中不正确的是( )
A生成树是树的一种表现形式
B生成树一定是连通的
C生成树一定不含有环
D若生成树顶点个数为n则其边数一定为n
图的邻接表如下所示从顶点V出发采用深度优先搜索法遍历该图则可能的顶点序列 是( )
AVVVVV BVVVVV
CVVVVV DVVVVV
下列查找方法中不属于动态的查找方法是( )
A二叉排序树法 B平衡树法
C散列法 D斐波那契查找法
要解决散列引起的沖突问题常采用的方法有( )
A数字分析法平方取中法
B数字分析法线性探测法
C二次探测法平方取中法
D二次探测法链地址法
用于外存储器的数据组织结构散列文件主要适用于( )
A顺序存取 B随机存取
C索引存取 D以上三种都可以
堆排序属于一种选择排序其时间复杂性为( )
AO() BO(nlogn)
CO(n) DO(n)
下列排序方法中属于不稳定的排序方法是( )
A直接插入排序法 B冒泡排序法
C基数排序法 D归并排序法
二填空题(本大题共小题每小题分共分)
请在每小题的空格中填上正确答案错填不填均无分
根据不同的描述方式对数据的操作运算通常可分为加工型运算和__________两种基本类型
数据结构中的算法通常采用最坏时间复杂度和____________两种方法衡量其效率
判断带头结点head的单链表为空的条件是___________
若顺序表每个元素长度均为其中第一个元素的存储地址为则第个元素的存储地址为___________
若front和rear分别表示循环队列Q的头指针和尾指针m表示该队列的最大容量则判断循环队列为满的条件是___________
对于顺序存储结构的二维数组通常采用___________两种存放方式存储数据元素
若某二叉树的先根遍历序列为CEDBA中根遍历序列为DEBAC则其后根遍历序列为___________
具有n个结点的完全二叉树其深度为___________
图主要采用___________两种存储结构存放
索引顺序查找通常分两个阶段进行首先采用顺序查找法或二分法确定所要查找的块然后再用___________法在块中找到具体的元素值
二叉排序树是一种特殊的有序表若要保证输出序列其键值完全按递增排列则应对二叉排序树采用___________法遍历
文件常见的存储结构有顺序文件链接文件 索引文件和___________四种
在各种内部排序中占用存储空间较大的排序通常是___________排序
三应用题(本大题共小题每小题分共分)
已知某二叉树的顺序存储结构如图所示试画出该二叉树
A
B
C
D
E
F
G
试用Prim算法构造下图的最小生成树要求分步给出构造过程
已知散列函数为H(key)=key%散列表长度为(散列地址空间为)待散列序列为()要求
()根据以上条件构造一散列表并用线性探测法解决有关地址沖突;
()若要用该散列表查找元素给出所需的比较次数
已知一组键值序列为()试采用快速排序法对该组序列作升序排序并给出每一趟的排序结果
已知一组键值序列()试采用二路归并排序法对该组序列作升序排序并给出每一趟的排序结果
四设计题(本大题共小题每小题分共分)
试编写一算法以完成在带头结点单链表L中第i个位置前插入元素X的操作
二叉树是由所有度数不大于的结点构成的一种特定树若某结点度为则该结点有左右两个孩子请编写算法计算一二叉树所有度数为的结点个数
