(完整word版)数据结构试题-试卷二-含答案.doc

模拟试题二

模拟试题二

???一、选择题（28分）

???1.设一数列的顺序为l，2，3，4，5，通过栈结构不可能排成的顺序数列为(?)。

???A)3,2,5,4,l???????????B)1,5,4,2,3

???C)2,4,3,5,l???????????D)4,5,3,2,l

???2.二叉树的第3层最少有(?)个结点。

???A)0????????B)1???????C)2?????D)3

???3.-个n个顶点的连通无向图，其边的个数至少为(?)。

???A)n-l????B)n????????C)n+l???D)nlogn

???4.下列排序方法中，(?)的比较次数与记录的初始排列状态无关。

???A)直接插入排序?????????B）起泡排序

???C)快速排序?????????????D）直接选择排序

???5.-棵哈夫曼树总共有II个结点，则叶子结点有(?)个。

???A)5????????B)6???????C)7??????D)9

???6.已知某算法的执行时间为(n+n2)+log2(n+2)，n为问题规模，则该算法的时间复杂度是?(???)。

???A)O(n)?????B)O(n2)???C)O(log2n)???D)O(nlog2n)

???7.如果一棵树有10个叶子结点，则该树总共至少有(?)个结点。

???A)lO?????B)11?????C)19???????D)21

???8.-个100×100的三角矩阵a采用行优先压缩存储后，如果首元素a[0][0]是第一个元素，那么a[4][2]是第(?)个元素。

???A)13??????B)401????C)402???????D)403

???9.有一棵二叉树如题图1，该树是(?)。

???A)二叉平衡树??????????B）二叉排序树

???C)堆的形状????????????D）以上都不是

???10.对于含有n个顶点e条边的无向连通图，利用Prim算法生成最小代价生成树，其时间复杂度为(?)，利用Kruska算法的时间复杂度为(?)。

???A)O(log2n)???B)0(n2)?????C)O(ne)???D)O(elog2ne)

???11.具有n个顶点的完全有向图的边数为(?)。

???A)n(n-l)/2???B)n(n-l)?????C)n2?????D)n2-1

???12.设有100个元素，用折半查找时，最大比较次数为(?)，最小比较次数为(?)。

???A)25???????B)7?????????C)10?????D)l

???13.在内部排序中，排序时不稳定的有(?)。

???A)插入排序???B）冒泡排序???C）快速排序???D）归并排序

???14.串是一种特殊的线性表，其特殊性体现在(?)。

???A)可以顺序存储????????B）数据元素是一个字符

???C)可以链接存储????????D）数据元素可以是多个字符

???二、填空题（30分）

???1.对于一个以顺序实现的循环队列Q[O…m-1]，队首、队尾指针分别为f和r，其判空的条件是__________，判满的条件是__________。

???2.具有64个结点的完全二叉树的深度为__________。

???3.给定一个整数集合{3，5，6，9，12），画出其对应的一棵哈夫曼树__________。

???4.如果指针p指向一棵二叉树的一个结点，则判断p没有左孩子的逻辑表达式为__________。

???5.下面为朴素的模式匹配算法，请在算法的下划线处填上正确的子句。

???int?index(String*s,String*t)

???String?*S,*t;

???{?i=j=O;

???while（（is-len)（jt-len））

???if(s-ch[i]==t-ch[j]){

???i=i+1：

???j=j+l;

???}else

???{i=__________;

???j=__________;

???}

???if（j==t-len）

???return（i-t-len）;

???else

???return（-1）;

???}

???6.-个nxn的对称矩阵，如果以行或列为主序存入内存，则其容量为__________。

???7.设F是森林，B是由F转换得到的二叉树，F中有n个非终端结点，B