染雾大学数据结构测试卷
一、选择题
1. 下面关于算法说法错误的是（ ） A．算法最终必须由计算机程序实现
B.为解决某问题的算法同为该问题编写的程序含义是相同的
C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的
2. 下述哪一条是顺序存储结构的优点？（ A．插入运算方便 B．存储密度大 C．删除运算方便
D．可方便地用于各种逻辑结构的存储表示
3. 线性表是具有n个（ ）的有限序列（n>0）。
A．表元素 B．字符 C．数据项 D. 数据元素
4. 若某线性表最常用的操作是存取任一指定序号的`元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。
A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表 5. 下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响的是：（ ）
A. 直接插入排序 B. 快速排序 C. 直接选择排序 D. 堆排序 6. 输入序列为ABC，可以变为CBA时，经过的栈操作为（ ）
A. push,pop,push,pop,push,pop B. push,push,push,pop,pop,pop C. push,push,pop,pop,push,pop D. push,pop,push,push,pop,pop 7. 设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（ ）
A．求子串 B．联接 C．匹配 D．求串长
8. 二叉树的先序遍历和中序遍历如下： 先序遍历：EFHIGJK；中序遍历: HFIEJKG 。该二叉树根的右子树的根是： （ ）
A、 E B、 F C、 G D、 H
9. 对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（ ） A．O(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1) 10. 已知一算术表达式的中缀形式为 A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为( )
A．-A+B*C/DE B. -A+B*CD/E C．-+*ABC/DE D. -+A*BC/DE
A,并已0右孩子的平衡因子为1,则应作（ ）型调整以使4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中 ）
．6 C．7 D．8 D ） ．3 C．4 D．
14. 设如左图所示，在下面的5个序列中，符合深度优先遍历的序列有多少？（ ）
a e b d f c a c f d e b
a e d f c b a e f d c b a e f d b c
A．5个 B．4个 C．3个 D．2个
二、填空题
1. 在下面的程序段中，对ｘ的赋值语句的频度为 _ _（表示为n的函数） For(i=1;i<=n;i++)
For(j=1;j<=i;j++) X+=3;
2. 循环队列的引入，目的是为了克服 ____________ ____ 3. 一个栈的输入序列是：1，2，3则不可能的栈输出序列是_______________ 4. 如果结点A有 3个兄弟，而且B是A的双亲，则B的度是_______________。 5. 当使用监视哨顺序查找n个元素的顺序表时，若查找失败，则比较关键字的次数为________________
6. 设一棵完全二叉树具有1000个结点，则它有________个叶子结点，有________个度为2的结点。
7. N个顶点的连通图的生成树含有 _条边
8. 已知一无向图G=（V，E），其中V={a,b,c,d,e } E={(a,b),(a,d),(a,c),(d,c),(b,e)}现用某一种图遍历方法从顶点a开始遍历图，得到的序列为abecd，则采用的是_______________遍历方法
9.分别采用堆排序，快速排序，冒泡排序和归并排序，对初态为有序的表，则最省时间的是 ___算法，最费时间的是 ____算法。 10.若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的 _______和记录的 ____ 。
三、应用题
1.考查树和二叉树的应用（本题8分）
2.考查图的方面的应用（本题8分）
3.考查查找方面的应用（本题8分）
四、计算题
1.考查排序方面的应用
2.考查哈希表的应用（本题8分）
五、算法设计题
考查栈、树和二叉树、查找和排序的算法设计与填空。
