一单项选择题(在每小题列出的四个备选答案中选出一个正确的答案并将其号码填在题干的括号内每小题分共分)
下列有关线性表的叙述中正确的是( )
A线性表中的元素之间隔是线性关系
B线性表中至少有一个元素
C线性表中任何一个元素有且仅有一个直接前趋
D线性表中任何一个元素有且仅有一个直接后继
下列关于串的叙述中正确的是( )
A一个串的字符个数即该串的长度
B一个串的长度至少是
C空串是由一个空格字符组成的串
D两个串S和S若长度相同则这两个串相等
以数组Q[m ]存放循环队列中的元素变量rear和qulen分别指示循环队列中队尾元素的实际位置和
当前队列中元素的个数队列第一个元素的实际位置是( )
Arear qulen
Brear qulen + m
Cm qulen
D +(rear + m qulen)mod m
高二叉树根结点的层次为所有含有个结点的二叉树中最小高度是( )
A
B
C
D
设结点x和结点y是二叉树T中的任意两个结点若在先根序列中x在y之前而在后根序列中x在y之后则x和y的关系是( )
Ax是y的左兄弟
Bx是y的右兄弟
Cx是y的祖先
Dx是y的后代
下列四种排序方法中不稳定的方法是( )
A直接插入排序
B冒泡排序
C归并排序
D直接选择排序
设有一个长度为的已排好序的表用二分查找进行查找若查找不成功至少比较( )次
A
B
C
D
一棵二叉排序树T用( )方法进行遍历可以得到各结点键值的递增序列
A先根遍历
B中根遍历
C层次遍历
D后根遍历
二判断题(判断下列各题是否正确正确的在括号内打√错误的打×每小题分共分)
数据的机内表示称为数据的存储结构( )
线性表的链接存储表中元素的逻辑顺序与物理顺序一定相同( )
二叉树中任何一个结点的度都是( )
由二叉树结点的先根序列的后根序列可以唯一地确定一棵二叉树( )
一个无向图的邻接矩阵中各元素之和与图中边的条数相等( )
用直接选择排序方法分别对序列S=()和序列S=()
进行排序两者的比较次数不相同( )
一棵哈夫曼树中不存在度为的结点( )
用二分查找法对一个顺序表进行查找这个顺序表可以是按各键值排好序的也可以是没有按键值排好序的( )
顺序文件适宜顺序存取不适宜随机存取( )
平衡二叉排序树上任何一个结点的左右子树的高度之差的绝对值不大于( )
三填空题(每空分共分)
一个n×n的下三角矩阵A中的元素aij(i≥j≤ij≤n)按行存于一个一维数组B[n(n
+)/]中对其中的任一元素aij若在B中的位置为k则k=____________
含有个结点的树有____________条边
一棵二叉树有个结点这些结点的度要么是要么是这棵二叉树中度为的结点有_________个
在一个无环有向图G中若存在一条从顶点i到顶点j的弧则在顶点的拓扑序列中顶点i与顶点j的先后次序是____________
在一个无向图的邻接表中若表结点的个数是m则图中边的条数是____________条
设一个闭散列表的容量为m用线性控测法解决沖突要插入一个键值若插入成功至多要进行____________次比较
设一棵二叉树结点的先根序列为ABDECFGH中根序列为DEBAFCHG则二叉树中叶子结点是____________
一棵哈夫曼树有个结点则其叶子结点的个数是____________
将两个长度分别m和n(m>n)的排好序的表归并成一个排好序的表至少要进行____________次键值比较
设二维数组M:array[]of integer每个元素(整数)占个存储单元元素按行的顺序存储数组的起始地址为元素M[]的地址是____________
线性表L=(aaan)采用顺序存储假定在不同的n
+ 个位置上插入的概率相同则插入一个新元素平均需要移动的元素个数是____________
设栈S和队列Q的初始状态皆为空元素aaaaa和a依次通过一个栈一个元素出栈后即进入队列Q若个元素出队列的顺序是aaaaaa则栈S至少应该容纳____________个元素
两个序列如下
L={}
L={}
用冒泡排序方法分别对序列L和L进行排序交换次序较少的是序列____________
将一棵有个结点的完全二叉树从根结点开始由根向下每一层从左至右顺序地存储在一个一维
数组bt[]中这棵二叉树最下面一层上最左边一个结点存储在数组元素____________中
一个索引文件由____________两部分组成
四应用题(共分)
初始输入序列的键值如下
()
试采用二路归并排序法进行从小到大的排序写出该序列在每遍扫描时的合并过程(分)
五设计题(共分)
修改冒泡排序法以实现双向冒泡排序即第一次把最大记录放到表尾第二次将最小记录放到表头如此反复进行直至排序结束试编写此算法(分)
