装订线—————————————————————————————————————————————————————————— 2009－2010学年第二学期

计算机科学学院《数据结构》期末考试试卷（B卷）

答案与评分标准

年级：08级 专业： 班级： 学号： 姓名： 题号 得分 一 二 三 四 总分 签名 注：1、共100分，考试时间120分钟。

2、此试卷适用于计算机科学与技术本科、信息管理与信息系统专业。

一 得 分 阅卷教师 一、 填空题（本题共10小题，每个空2分，共20分）

1．在一般情况下，一个算法的时间复杂度是（问题规模 ）的函数。 2．当线性表的元素总数稳定，且很少进行插入和删除运算，但要求以最快的速度存取线性表中的元素时，应采用（ 顺序 ）存储结构。

3. 一个具有n个结点的单链表，在给定值为x的结点后插入一个新结点的时间复杂度为（ O（n） ）。

4．循环队列的引入是为了克服（ 假溢出或假上溢 ）。 5．数组通常只有（ 存取 ）和修改这两种运算。

6．已知一棵完全二叉树共有748个结点，则该树中有（ 374 ）个叶子结点。

7．树T有n个结点且结点的度均为k或者0，则树中的叶子结点总数为：（ n－(n-1)/k ） 。

8．在无向图的邻接矩阵中，第i行非零元个数就是第i个顶点的（ 度数 ）。

9．如果待排序序列已接近正序，则在快速排序、堆排序和归并排序之中，选用（ 堆排序 ）较为适当。

10．某二叉树的先序遍历序列是ABCDEFG，中序遍历序列是CBDAFGE，则其后序遍历序列是（ CDBGFEA ）。 二 得 分 阅卷教师 二、 选择题（本题共10小题，每个空2分，共20分）

1．链表不具有的特点是（ A ）

A．随机访问任一元素 B．插入不需移动元素

《数据结构》期末考试试卷（B卷）第 1 页 共 4 页

C．不必事先估计存储空间 D．所需空间与线性表长度成正比 2．一个栈的入栈序列为12345，则栈的不可能的输出序列是（ B ）

A．54321 B．43512 C．45321 D．12345

3．如果链串结点中的指针占2个字节，字符占3个字节，则结点大小为2的链串的存储密度为（ C ）

A．0.2 B．0.4 C．0.6 D．0.8 4．二维数组A[8][9]采用列优先存储方法，若每个元素各占2个存储单元，而且A[0][0]的地址为1000，则A[5][7]的地址为 （ D ）

A．1120 B．1234 C．1212 D．1122 5．（ C ）不属于特殊矩阵

A．对角矩阵 B．三角矩阵 C．稀疏矩阵 D．对称矩阵

6．若一棵二叉树有10个叶子结点，则该二叉树中度为2的结点个数是（ C ）

A．11 B．10 C．9 D．不确定

7．在含n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为（ D ）

A．e B．2e C．n2－e D．n2－2e 8．要得到二叉排序树的结点的排序序列，应对该树进行（ C ）

A．层次遍历 B．先序遍历 C．中序遍历 D．后序遍历 9．下面结构中最适于表示稀疏无向图的是（ B ）

A．邻接矩阵 B．邻接多重表 C．逆邻接表 D．十字链表

10. 假定一棵度为3的树中结点总数为30，则其最小高度应为（ A ） A. 3 B. 4 C. 5 D. 6

三 得 分 阅卷教师 三、问答题(本题共6小题，共40分) 1、名词解释（6分）

数据类型——一个值得集合和定义在这个值上的一组操作的总称；（2分）

数据结构——相互之间存在一种或多种特定关系的数据元素的集合。（2分）

栈——限定仅在表尾进行插入或删除操作的线性表。（2分）

2、在什么情况下用顺序表比链表好？（6分）

答：在需要查找与修改数据元素值的操作比插入与删除元素的操作频繁的情况（3分），和在存储密度要求高的情况（3分），顺序表比链表好。

《数据结构》期末考试试卷（B卷）第 2 页 共 4 页

装

3、设字符串P=‘abaabaab’，请求出P的next值和nextval值。（8分） 解：P的next与nextval值分别为01122345（4分）和01021021（4分）。

4、简述队列和栈这两种数据结构的相同点和不同点。（6分） 答：相同点：都是插入和删除运算的位置受限制的线性表。（2分） 不同点：栈是限定在表尾进行插入和删除的线性表，也称后进先出表；（2分）而队列是限定在表的一端进行插入，另一端进行删除的线性表，也称为先进先出表。（2分）

5、画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查找长度。（6分） 解：ASL＝（1+2*2+3*4+4*3）/10＝2.9 （3分）

（3分）

订线—————————————————————————————————————————————————————————

6、有一份电文中共使用五个字符：a、b、c、d、e，它们的出现频率依次为（8、14、10、4、18），请构造相应的哈夫曼树（要求左子树根结点的权小于等于右子树根结点的权），求出每个字符的哈夫曼编码。（8分）

解：哈夫曼树为：

（3分）

相应的哈夫曼编码为： a：011； b：10； c：00； d：010； e：11（每个1分）

《数据结构》期末考试试卷（B卷）第 3 页 共 4 页