数构测试卷

大学数据结构测试卷

数构测试卷

一、选择题（本题共20小题，每小题1分，共20分）

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

第1页，共4页

A,并已0右孩子的平衡因子为1,则应作（ ）型调整以使4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中 ）

．6 C．7 D．8 D ） ．3 C．4 D．5

）

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个

）。

） B. 必然慢 C. 相等

D. 不能确定

） 90， 60， 120，110，130） B.（100，120，110，130，80， 60， 90） 80， 90， 120,110，130） D. (100，80， 60， 90，120，130，110)

）是稳定的。

D. 归并排序，冒泡排序

B. 快速排序，堆排序

《数据结构》 A卷

第2页，共4页

大学数据结构测试卷

20. 若用冒泡排序方法对序列{10,14,26,29,41,52}从大到小排序，需进行（ ）次两两比较。

A. 3 B. 10 C. 15 D. 25

二、填空题（本题共10小题，每小题2分，共20分）

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.若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的 _______和记录的 ____ 。

三、应用题（本题共3小题，共24分）

1.考查树和二叉树的应用（本题8分） 2.考查图的方面的应用（本题8分） 3.考查查找方面的应用（本题8分）

《数据结构》

第3页，共4页

四、计算题（本题共2小题，共20分）

1.考查排序方面的应用（本题8分） 2.考查哈希表的应用（本题8分）

五、算法设计题（本题共 2 小题，共 16 分）

考查栈、树和二叉树、查找和排序的算法设计与填空。

A卷

第4页，共4页