2010~2011学年第一学期数据结构试卷A(wo)

缓冲区的逻辑结构应该是（ ）。 A.栈 B.队列 C.树 D.图 课程名称 《算法与数据结构》 任课教师签名 黄巍

6. 若元素a，b，c，d，e，f依次进栈，允许进栈、退栈操作交替进行。但不允许连

出题教师签名 校外专家 审题教师签名 续三次进行退栈工作，则不可能得到的出栈序列是（ ）。

A.dcebfa B.cbdaef C.bcaefd D.afedcb 考试方式 （ 闭）卷 适用专业 计算机各专业 2010-2011学年第1学期考试试题（A）卷

考试时间 （ 120 ）分钟 题号 一 二 三 四 五 六 总分 得分 评卷人

一、单项选择题（每小题2分，共40分） 1. 从逻辑上可以把数据结构分为（ ）两大类。 A.动态结构、静态结构 B.顺序结构、链式结构 C.线性结构、非线性结构 D.基本结构、构造结构

2．下列术语中，（ ）与数据的存储结构无关。 A.栈 B.哈希表 C.线索树 D. 双向链表 3．下面的程序段的时间复杂度为（ ）。 for（i=1；i<=n；i++）

for（j=1；j<=n；j++） x=x+1； A.O(log2n) B.O(2n) C.O(n) D.O(n2

) 4. 若长度为n的线性表采用顺序存储结构，在其第i(1<=i<=n+1)个位置插入一个新元素的算法的时间复杂度为（ ）。 A.O(0) B.O(1) C.O(n) D.O(n2

) 5. 为解决计算机主机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该

7. 若对n阶对称矩阵A以行序为主序方式将其下三角形的元素（包括主对角线上所

有元素）依次存放于一维数组B[1..(n(n+1))/2]中，则在B中确定A矩阵中的元素aij（i

A.i*(i-1)/2+j B.j*(j-1)/2+I C.i*(i+1)/2+j D.j*(j+1)/2+i

8. 在一棵度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则数T的叶节点个数是（ ）。 A.41 B.82 C.113 D.122

9. 给定二叉树下图所示。设N代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。若遍历后的结点序列为（3，1，7，5，6，2，4），则其遍历方式是（ ）。 1 2 3 4 5 6 7

A.LRN B.NRL C.RLN D.RNL 10. 将森林转换为对应的二叉树，若在二叉树中，结点u是结点v的父结点的父结点，则在原来的森林中，u和v可能具有的关系是（ ）。

I.父子关系 Ⅱ.兄弟关系 Ⅲ.u的父结点与v的父结点是兄弟关系 A.只有Ⅱ B.I和Ⅱ C.I和Ⅲ D.I、Ⅱ和Ⅲ

11. 下列编码中，（ ）不是前缀码。 A.（00，01，10，11） B.（0，10，110，111） C.（0，1，00，11） D.（1，01，000，001）

12. 在下图所示的平衡二叉树中插入关键字48后得到一棵新平衡二叉树，在新平衡二叉树中，关键字37所在结点的左、右子结点保存的关键字分别是（ ）。

17. 对一组数据（2，12，16，88，5，10）进行排序，若前三趟排序结果如下： 第一趟：（2，12，16，5，10，88） 第二趟：（2，12，5，10，16，88） 第三趟：（2，5，10，12，16，88） 则采用的排序方法可能是（ ）。 A.起泡排序 B.希尔排序 C.归并排序 D.基数排序 24 13 53 37 90

A.13，48 B.24，48 C.24，53 D.24，90

13. 若无向图G=(V.E)中含7个顶点，则保证图G在任何情况下都是连通的，则需要的边数最少是（ ）。 A.6 B.15 C.16 D.21

14. 已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={,,,,,,,,}， 图G的拓扑序列是（ ）。 A. V1,V3,V4,V6,V2,V5,V7 B. V1,V3,V2,V6,V4,V5,V7 C. V1,V3,V4,V5,V2,V6,V7 D. V1,V2,V5,V3,V4,V6,V7

15. 已知关键字序列（3，5，9，18，37，66， 98，102），用折半查找法查找66与67，需要将给定值与关键字比较的次数分别为（ ）。 A.6，7 B.2，3 C.2，4 D.3，4

16. 下列叙述中，不符合m阶B树定义要求的是（ ）。 A.根结点最多有m棵子树 B.所有叶结点都在同一层上 C.各结点内关键字均升序或降序排列 D.叶结点之间通过指针链接

18. 下列关键字序列中，（ ）是堆。 A.（75,65,30,15,25,45,20,10） B.（75,65,45,10,30,25,20,15） C.（75,45,65,10,25,30,20,15） D.（75,45,65,30,15,25,20,10）

19. 对关键字序列（05，46，13，55，94，17，42）进行基数排序，一趟排序后的结果是（ ）。 A.（05，46，13，55，94，17，42） B.（05，13，17，42，46，55，94） C.（42，13，94，05，55，46，17） D.（05，13，46，55，17，42，94）

20．下列排序方法中，（ ）是稳定的排序方法。 A. 折半插入排序 B. 直接选择排序 C.希尔排序 D.快速排序

二、画图应用题(每题10分，共30分)

1. 一棵二叉排序树的结构如下图所示，9个结点的值分别为（1，2，3，4，5，6，7，8，9）。请在图中标出各结点的值。

2．设无向图G=（V，E），其中V={1，2，3，4，5}，E={（1，2，4），（2，5，5），（1，3，2），（2，4，4），（3，4，1），（4，5，3），（1，5，8）}，每条边由

一个三元组表示，三元组中前两个元素为与该边关联的顶点，第三个元素为该边的权。请写出图G中从顶点1到其余各点的了短路径的求解过程。要求列出最短路径上的顶点，并计算路径长度。

3. 设哈希表的地址范围为0～9，哈希函数为：H（Key）＝Key MOD 7，用线性探测法再散列法处理冲突，根据关键字序列（16，8，15，32，24，30）哈希造表，试回答下列问题： （1）画出哈希表的示意图； （2）若查找关键字24，需要依次与哪些关键字进行比较？ （3）假定每个关键字的查找概率相等，求查找成功时的平均查找长度。

地址下0 1 2 3 4 5 6 7 8 9 标

三、综合应用题（每题15分，共30分）

1. 已知两个升序序列长度分别为m与n，分别存放在数组a与b中。编写将两个数组的元素归并成一个非递减的序列并存放到数组c中的算法。要求： （1）描述算法的基本设计思想； （2）描述算法的详细实现步骤；

（3）根据设计思想和实现步骤，采用程序设计语言描述算法（使用C或C++或JAVA语言实现），关键之处请给出简要注释。

2. 用一个带有表头结点的循环链表表示队列，结点结构为

，假设该循

环链表只设一个尾指针rear指向队尾元素结点（注意不设头指针）。编写相应的初始化队列、入队列和出队列算法。要求： （1）描述算法的基本设计思想； （2）描述算法的详细实现步骤；

（3）根据设计思想和实现步骤，采用程序设计语言描述算法（使用C或C++或JAVA语言实现），关键之处请给出简要注释。

本文来源：https://www.bwwdw.com/article/oraf.html