内容发布更新时间 : 2024/5/5 3:04:11星期一 下面是文章的全部内容请认真阅读。

承诺：我将严格遵守考场纪律，知道考试违纪、作弊的严重性，还知道请他人代考或代他人考者将被开除学籍和因作弊受到记过及以上处分将不授予学士学位，愿承担由此引起的一切后果。 华东交通大学2013—2014学年第一学期考试卷

试卷编号： （A）卷

数据结构 课程 课程类别：必

开卷（仅限教材）： 考试日期：2014-1-16 题号 一 二 三 四 五 六 七 八 九 十 总分 累分人 × × × × 100 签名 题分 20 30 10 36 4 ×得分 × × × × × 考生注意事项：1、本试卷共5页，总分100分，考试时间120分钟。

2、考试结束后，考生不得将试卷、答题纸和草稿纸带出考场。

一、选择题(每题2分，共20分)

1、由两个栈共享一个向量空间的好处是：（ ） ( A ) 减少存取时间，降低下溢发生的机率 ( B ) 节省存储空间，降低上溢发生的机率 ( C ) 减少存取时间，降低上溢发生的机率 ( D ) 节省存储空间，降低下溢发生的机率

得分 评阅人 2、设数据结构A=(D，R)，其中D={1，2，3，4}，R={r}，r={<1，2>，<2，3>，<3，4>，<4，1>}，则数据结构A是（ ）。

3、设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front值为（ ）

(A) front=front+1 (B) front=(front+1)%(m-1) (C) front=(front-1)%m (D) front=(front+1)%m

4、设一组初始记录关键字序列(5，2，6，3，8)，以第一个记录关键字5为基准进行一趟快速排序的结果为（ ）。

(A) 线性结构

(B) 树型结构 (C) 图型结构

(D) 集合

第 1 页 共 5 页

(A) 2，3，5，8，6 (C) 3，2，5，6，8

(B) 3，2，5，8，6 (D) 2，3，6，5，8

5、 设用链表作为栈的存储结构则退栈操作（ ）。

6、 设一组初始记录关键字序列为(25，50，15，35，80，85，20，40，36，70)，其中含有5个长度为2的有序子表，则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为（ ）。

(A) 15，25，35，50，20，40，80，85，36，70 (B) 15，25，35，50，80，20，85，40，70，36 (C) 15，25，35，50，80，85，20，36，40，70 (D) 15，25，35，50，80，20，36，40，70，85

7、设一棵完全二叉树中有65个结点，则该完全二叉树的深度为（ ）。

8、设一组初始记录关键字序列为(13，18，24，35，47，50，62，83，90，115，134),则利用二分法查找关键字90需要比较的关键字个数为（ ）。

9、 设无向图G中的边的集合E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发进行深度优先遍历可以得到的一种顶点序列为（ ）。

10、设某链表中最常用的操作是在链表的尾部插入或删除元素，则选用下列（ ）存储方式最节省运算时间。

(A) 单向链表 (B) 单向循环链表 (C) 双向链表

(D) 双向循环链表

(A) aedfcb (B) acfebd (C) aebcfd

(D) aedfbc

(A) 1

(B) 2

(C) 3

(D) 4

(A) 8

(B) 7

(C) 6

(D) 5

(A) 必须判别栈是否为满

(B) 必须判别栈是否为空

(C) 判别栈元素的类型 (D) 对栈不作任何判别

二、填空题(每空2分，共30分)

第 2 页 共 5 页

（1）、设散列表的长度为8，散列函数H(k)=k % 7，用线性探测法解决冲突，则根据一组初始关键字序列(8，15，16，22，30，32)构造出的散列表的平均查找长度是_ _（1）______。 （2）、数据结构从逻辑上划分为四种基本类型：_ _（2）___、

得分 评阅人 （3） 、_ _（4）_ ____和_ _（5）_______。

（3）、for(i=1，t=1，s=0；i<=n；i++) {t=t*i；s=s+t；}的时间复杂度为_ _（6）_ ____。 （4）、后缀算式9 2 3 +- 10 2 / -的值为_____（7） __。中缀算式（3+4X）-2Y/3对应的后缀算式为____（8）__ _____。

（5）、设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为7、19、2、6、32、3、21、10，根据这些频率作为权值构造哈夫曼树，则这棵哈夫曼树的高度为______（9）________。

（6）、设指针变量head指向双向链表中的头结点，指针变量p指向双向链表中的第一个结点，则指针变量p和指针变量head之间的关系是p=__（10） ____和head= （11）___（设结点中的两个指针域分别为llink和rlink）。

（7）、设有n个无序的记录关键字，则直接插入排序的时间复杂度为_ （12）___，快速排序的平均时间复杂度为___ （13） __。

（8）、设一棵完全二叉树中有21个结点，如果按照从上到下、从左到右的顺序从1开始顺序编号，则编号为8的双亲结点的编号是__ （14）_ __，编号为8的左孩子结点的编号是____ （15） ____。

三、判断题(每题1分，共10分，对的打“√”，错的打“×”)

1、设一棵二叉树的先序序列和后序序列，则能够唯一确定出该二叉树的形状。（ ）

2、冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多。（ ） 3、分块查找的基本思想是首先在索引表中进行查找，以便确定给定的关键字可能存在的块号，然后再在相应的块内进行顺序查找。（ ） 4、顺序表查找指的是在顺序存储结构上进行查找。（ ）

5、 向二叉排序树中插入一个结点需要比较的次数可能大于该二叉树的高度。（ ） 6、调用一次深度优先遍历可以访问到图中的所有顶点。（ ）

7、不论是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情况。

第 3 页 共 5 页

得分 评阅人