浙江师范大学《数据结构与算法分析》期末试卷
（2006-2007学年第一学期）
考试类型：闭卷 利用学生：数理与信息工程学院学生
考试时刻：120分钟 出卷时刻：2007年1月10日
班级：__________ 学号：__________ 姓名：____________
说明：考生应将全数答案写在答题纸上，不然作无效处置
一、单项选择题（每题2分，共40分）
1.
数据结构的二元组概念 DS={D,S}中，D是数据元素的有限集合，而S是D上_______的有限集合。
A、 数据 B、 数据项 C、 关系 D、 操作 2.
以下有关线性表的表达中，正确的选项是________。 A、 线性表中的元素之间是线性关系 B、 线性表中至少有一个元素
C、 线性表中任何一个元素有且仅有一个直接前驱 D、 线性表中任何一个元素有且仅有一个直接后继 3.
栈和队列都是操作受限的线性表，他们各自的特点是 。 A、 栈：后进先出，队列：先进后出 B、 栈：先进后出，队列：后进后出 C、 栈：后进后出，队列：先进先出 D、 栈：先进先出，队列：后进先出 4.
以下关于串的表达中，正确的选项是 。 A、 一个串的字符个数即该串的长度 B、 一个串的长度至少是1 C、 空串是由一个空格组成的串
D、 两个串S1和S2假设长度相同，那么这两个串相等。 5.
假设一棵二叉树具有10个度为2的结点，那么该二叉树的度为0的结点个数是 。
A 、9 B 、12 C 、11 D 、不确信 6.
高度为k的二叉树（仅含根结点的二叉树高度为1）的结点数最多是________多少个。 A、 2K-1-1 B、 2K-1 C、 2K+1-1 D、 2K+1 7.
一棵二叉排序树T，用 方式进行遍历，能够取得结点键值的递增序列。 A、先序遍历 B、后序遍历 C、层序遍历 D、中序遍历 8.
下面选项中符合堆的概念是 _____ 。 A、100 86 48 73 35 39 42 57 66 21 B、12 70 33 65 24 56 48 92 86 33 C、5 56 23 40 38 29 31 35 76 28 100 D、66 92 56 38 66 23 42 12 30 52 9.
设有一个长度为100的已排好序的线性表，用二分查找进行查找，假设查找不成功，至少比较 次。
A、 9 B、 8 C、 7 D、 6 10. 树的固有特性是 。
A、递归 B、顺序 C、嵌套 D、选择
11. 无向图的相邻矩阵表示法中，以下关于矩阵的说法不正确的选项是
A、对称的 B、行和为相应极点的度
C、对角线元素全为0 D、边的总数为矩阵中非零元素个数之和
12. 有一个初始为空的栈，S表示入栈操作，P表示出栈操作，以下操作序列中合法的
是 。
A、PSSSPP B、SSPPPP C、SSPPSP D、PSPSPS
13. 算法的查找效率一样是以平均查找代价来衡量的，比如线性查找是O(N)，二分查找是
O(log N)，那么Hash查找的期望代价是 。 A、O(log N) B、O(N) C．O(1) D．O(N log N)
14. 设a，b为一颗二叉树上的两个结点，在中序遍历时a在b前面的条件是 。
A、a在b右方 B、a在b左方 C、a是b的先人 D、a是b的子孙
15. 对线性表进行二分查找时，要求线性表必需是 。
A、顺序存储
B、链式存储
C、顺序存储且数据元素有序 D、链式存储且数据元素有序 16. 在含有n个结点的树中，边的数量只能是 条。
A、 n
B、 n*(n-1) D、 n*(n-1)/2
C、 n-1
17. 对给定整数序列(541,132,984,746,518,181,946,314,205,827) 进行从大到小排序时，采纳快
速排序（以中间元素518为基准）的第一趟排序结果是 。 A、(181,132,314,205,541,518,946,827,746,984) B、(541,132,827,746,518,181,946,314,205,984) C、(205,132,314,181,518,746,946,984,541,827) D、(541,132,984,746,827,181,946,314,205,518)
18. 在查找树中插入一个新结点，老是插入到 下面。
A、 根结点
B、 左子树结点
C、 右子树结点 D、 叶结点
19. 从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情形下，需要
平均比较 个结点。 A、 n/2
B、 n
C、 (n+1)/2 D、 (n-1)/2
20. 一棵顺序存储的完全二叉树，每结点占用2个存储单元，现已知第三个结点地址为1000，
假设其左子女存在的话，其地址最有可能是 。 A、 2000 B、1006 C、 2004 D、2020
二、 简答计算题（每题5分30分）
1.
假设用于通信的电文由八个字母A-H组成，字母在电文中显现的频率别离为, , , , , , , 。试为这8个字母设计哈夫曼编码。
浙江师范大学数据结构期末试卷
