20秋北理工71数据结构与算法模拟题4模拟测试答案
《数据结构与算法》模拟题4判断题（共5题,共10分）数据元素是数据的最小单位( )。若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算( ) 。
二叉树的后序遍历序列中，任意一个结点均处在其孩子结点的前面( )。
一个有10个顶点,6条边的无向图,该图不连通( )。
连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点( )。二、单选题 1. 数据结构可形式地定义为(D, S)，其中S是D上( )的有限集。
A.操作 B.存储映像 C.关系 D.数据元素2. 数据的最小单位是( )。
A. 数据结构B. 数据元素C. 数据项D. 文件3. 下列数据结构中( )是线性数据结构。
A. 二叉树 B. 无向图 C. 赫夫曼树 D.队列4. 采用链式存储结构存储线性表的优点是( )。
A.便于随机存取 B. 花费的存储空间比顺序存储少
C.便于插入和删除操作D. 数据元素的物理顺序与逻辑顺序相同5. ( )不是队列的基本运算。
A. 判断一个队列是否为空 B. 从队头删除一个元素
C. 在队列第i个元素之后插入一个元素 D. 读取队头元素的值6. 一个队列的入列序列是1,2,3,4，则队列的输出序列是( )。
A.4,3,2,1 B.3,2,4,1 C.1,4,3,2 D.1,2,3,47. 广义表((a), (b))的表尾是( )。
A.( ) B.b C. ((b)) D. (b)8. 若无向图中有n个结点，e条边，则它的邻接表需要( )个表结点。
A. n B. 2n C. 2e D. e9. 在哈希函数H(key) = key%m中，一般来说，m应取( )。
A. 奇数 B. 偶数 C. 充分大的数 D. 素数
10. 赫夫曼树的带权路径长度是( )。
A.所有叶结点带权路径长度之和B.所有结点权值之和
C.带权结点的值 D.除根以外所有结点权值之和11. 设一个有序表为｛1，3，9，12，32，41，45，62，75，77，82，95，100｝，当采用折半查找值为95的结点时，( )次比较后查找结束。
A.3 B.4 C.5 D.6 12. 在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是( )。 A. 直接插入排序 B. 快速排序
C. 冒泡排序 D. 简单选择排序三、填空题 1. 在线性表中，一个数据元素可由若干数据项组成，在这种情况下，常将数据元素称为____________。2. 在图形结构中，每个结点的前驱结点和后继结点可以有_______。3. 从逻辑结构来看，线性结构的特点是____________。 4. 栈又称为________________的线性表。5. 设有一个顺序栈S，元素a,b,c,d,e,f依次入栈，如果6个元素的出栈顺序为b,c,a,d,f,e，则顺序栈的容量至少为____。 6. 在队列中，可进行删除操作的一端称为________。7. 对于稀疏矩阵的压缩存储只需存储_________________。8. 邻接表是图的___________存储结构。9. 在一棵度为3的树中，度为3的结点个数为2，度为2的结点个数为1，则度为0的结点为______个。 10. 有100个结点的树有________条边。11. 对二叉排序树进行________遍历，可以得到该二叉树所有结点构成的有序序列。 12. 起泡排序、快速排序和插入排序中，不稳定的是________。四、解答题
1. 选择排序算法是否稳定？为什么？2. 设有多项式A(x) = 1 + 3x + 2x12，试用线性链表表示。
3. 设有一个二维数组A，采用以行序为主序的存储结构，每个元素占两个空间，第一个元素的存放位置为100(十进制)，求元素A的存放位置。4. 将如下树转换成二叉树。
5.设哈希表表长为11，哈希函数（用除留余数法）H(key) = key mod 11，解决冲突的方法为开放定址法Hi(key)=(H(key)+di)mod11，对下列关键字序列{19，13，33，02，16，24，7}，给出计算过程并构造哈希表。
五、算法题
1. 下列程序判断字符串s 是否对称，对称则返回1，否则返回0；如 f("abba")返回1，f("abab")返回0。请填空完成该程序。
?
int f((1)________)?
{
int i=0,j=0;
? while (s)(2)________;
?
for(j--; i<j&& s==s; i++,j--);
?
return((3)_______)
?}2. 阅读如下算法，给出该算法的功能。
void Demo1(SeqStack *S){
int i; arr ; n=0 ;
while ( StackEmpty(S)) arr=Pop(S);
for (i=0, i< n; i++) Push(S, arr);
}转载注明无忧答案网
页:
[1]