一单项选择题(在下列每小题四个备选答案中选出一个正确答案并将其字母标号填入题干的括号内每小题分共分)
下列数据组织形式中( )的结点按逻辑关系依次排列形成一个锁链
A集合 B树形结构 C线性结构 D图状结构
数据结构可以形式化地定义为(S△)其中S指某种逻辑结构△是指( )
A S上的算法 B S的存储结构
C 在S上的一个基本运算集 D 在S上的所有数据元素
下列说法正确的是( )
A线性表的逻辑顺序与存储顺序总是一致的
B线性表的链式存储结构中要求内存中可用的存储单元可以是连续的也可以不连续
C线性表的线性存储结构优于链式存储结构
D每种数据结构都具有插入删除和查找三种基本运算
设非空单链表的数据域为data指针域为next指针p指向单链表中第i个结点s指向已生成的新结点现将s结点插入到单链表中使其成为第i个结点下列算法段能正确完成上述要求的是( )
A s > next=p > next; p > next=s;
B p>next=s; s>next=p>next;
C s>next=p>next; p>next=s; 交换p>data和s>data;
D p=s; s>next=p;
稀疏矩阵一般采用( )方法压缩存储
A三维数组 B单链表 C三元组表 D散列表
树若用双亲链表表示则( )
A可容易地实现求双亲及子孙的运算
B求双亲及子孙的运算均较困难
C可容易地实现求双亲运算但求子孙运算较困难
D可容易地实现求子孙运算但求双亲运算较困难
将一棵有个结点的完全二叉树按层编号则对编号为的结点x该结点( )
A无左右孩子 B有左孩子无右孩子
C有右孩子无左孩子 D有左右孩子
用邻接表作为有向图G的存储结构设有n个顶点e条弧则拓扑排序的时间复杂度为( )
A O(n) B O(n+e) C O(e) D O(n*e)
如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点则该图一定是( )
A完全图 B连通图 C有回路 D一棵树
采用线性探测法解决沖突问题所产生的一系列后继散列地址( )
A必须大于等于原散列地址
B必须小于等于原散列地址
C可以大于或小于但不能等于原散列地址
D地址大小没有具体限制
在对查找表的查找过程中若被查找的数据元素不存在则把该数据元素插入到集合中这种方式主要适合于( )
A静态查找表 B动态查找表
C静态查找表与动态查找表 D两种表都不适合
由索引集顺序集和数据集三部分组成的文件称为( )
A VSAM文件 B散列文件 C顺序文件 D索引文件
下列有关散列文件的说法中不正确的是( )
A散列文件具有随机存放的优点
B散列文件只能按关键字存取
C散列文件需要索引区
D散列文件的记录不需要进行排序
一组记录的键值为()按路归并排序方法对该序列进行一趟归并后的结果为( )
A B
C D
用快速排序方法对包含有n个关键的序列进行排序最坏情况下执行的时间杂度为( )
A O(n) B O(log n) C O(nlog n) D O(n )
二填空题(每空分共分)
定义在线性表上的初始化查找插入和删除运算中 是引用型运算
线性表(a a a …a n ) (n≥)中每个元素占c个存储单元m为a 的首地址则按顺序存储方式存储线性表a n 的存储地址是
在栈的顺序实现中设栈顶指针为top栈空的条件为
队列中允许进行插入的一端称为
深度为的满二叉树上第层有 个结点
给定n个值构造哈夫曼树根据哈夫曼算法初始森林中共有n棵二叉树经过 次合并后才能使森林中的二叉树的数目由n棵减少到只剩下一棵最终的哈夫曼树
设无向图G的顶点数为n则G最少有 条边
通常采用拉链法线性探测法多重散列法二次探测法公共溢出区法等解决散列地址沖突问题若要避免堆积现象发生应采用 法
对有序表()用二分查找法查找则所需的比较次数为
树型结构结点间通过父子关系相互关联这种相互关联构成了数据间的 关系
文件的检索有顺序存取直接存取和 三种方式
第i趟在ni+l (i=…nl)个记录中选取键值最小的记录作为有序序列的第i个记录这样的排序方法称为
在堆排序和快速排序中若原始记录已基本有序则较适合选用
三应用题(共分)
设有字符串为 * y a / y ∧ 试利用栈写出将其转换为 y * a y ∧ / 的操作步骤假定用 X 代表扫描该字符串过程中顺序取一个字符进栈的操作用 S 代表从栈中取出一个字符加入到新字符串尾的出栈操作例如ABC 变为 BCA 的操作步骤为 XXSXSS (分)
现有某二叉树按先根遍历的序列为ABDEFCGH按中根遍历的序列为DEFBGHCA试画出此二叉树(分)
给定表()按数据元素在表中的次序构造一棵二叉排序树(分)
已知序列()请给出采用直接插入排序法对该序列作升序排序时的每一趟的结果(分)
已知无向图G的邻接表如下请画出其所有的连通分量(分)
四设计题(共分)
设字符串仅由圆括号 ( 和 ) 方括号 [ 和 ] 花括号 { 和 } 组成利用链栈的操作编写一个检查括号是否正确配对的算法 int Matcher(LStackTP *ls) 例如 [{{()}[]}(){[]}] 是正确的而 {({()[]})}])} 则不正确设链栈定义如下(分)
typedef struct node
{ char data;
struct node *next;
} LStackTp;
利用一维数组 a 可以对 n 个整数进行排序其中一种排序算法的处理思想是将 n 个整数分别作为数组 a 的 n 个元素值每次(即第 i 次)从元素 a[i] 到 a[n] 中挑出最小的一个元素 a[k](i≤k≤n) 然后将 a[k] 与 a[i] 换位这样反复 n 次完成排序编写实现上述算法的函数 void sort(int a[]int n) (分)
