数据结构与算法(共11张PPT)

国家二级公共基础知识（数据结构与算法）模拟试卷11 (题后含答案及解析)

题型有：1. 选择题

选择题下列各题A、B、C、D四个选项中，只有一个选项是正确的，请将正确选项涂写在答题卡相应位置上。

1． 算法的有穷性是指

A．算法程序的运行时间是有限的

B．算法程序所处理的数据量是有限的

C．算法程序的长度是有限的

D．算法只能被有限的用户使用

正确答案：A

解析：葬法的有穷性，是指算法必须能在有限的时间内做完，即算法必须能在执行有限个步骤之后终止。 知识模块：数据结构与算法

2． 下列叙述中正确的是

A．算法就是程序

B．设计算法时只需要考虑数据结构的设计

C．设计算法时只需要考虑结果的可靠性

D．以上三种说法都不对

正确答案：D

解析：所谓算法是指解题方案的准确而完整的描述。是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，且是明确的，此顺序将在有限的次数下终止。算法不等于程序，也不等于计算方法。设计算法时不仪要考虑对数据对象的运算和操作，还要考虑算法的控制结构。 知识模块：数据结构与算法

3． 算法的空间复杂度是指

A．算法在执行过程中所需要的计算机存储空间

B．算法所处理的数据量

C．算法程序中的语句或指令条数

D．算法在执行过程中所需要的临时工作单元数

正确答案：A

解析：算法的空间复杂度是指执行这个算法所需要的内存空间。这个内存空间包括算法程序所占的空间，输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。 知识模块：数据结构与算法

4． 算法的时间复杂度是指

A．算法的执行时间

B．算法所处理的数据量

C．算法程序中的语句或指令条数

D．算法在执行过程中所需要的基本运算次数

正确答案：D

解析：算法的时间复杂度，是指执行算法所需要的计算工作量。算法的工作量可以用算法在执行过程中所需基本运算的执行次数来度量。 知识模块：数据结构与算法

5． 下列叙述中正确的是

Chapter11:AmortizedAnalysis

11.1Whenthenumberoftreesaftertheinsertionsismorethanthenumberbefore.

11.2Althougheachinsertiontakesroughlylog N󰁏,andeachDeleteMin󰁏takes2log N󰁏actual

time,ouraccountingsystemischargingtheseparticularoperationsas2fortheinsertion

and3log N󰁏−2fortheDeleteMin.󰁏Thetotaltimeisstillthesame;thisisanaccounting

gimmick.IfthenumberofinsertionsandDeleteMins󰁏areroughlyequivalent,thenit

reallyisjustagimmickandnotverymeaningful;theboundhasmoresignificanceif,for

instance,thereareN󰁏insertionsandO󰁏(N󰁏/ log N󰁏)DeleteMins󰁏(inwhichcase,thetotal

timeislinear).

11.3InsertthesequenceN󰁏,N󰁏 + 1,N󰁏 − 1,N󰁏 + 2,N󰁏 − 2,N󰁏 + 3,...,1,2N󰁏intoaninitially

emptyskewheap.TherightpathhasN󰁏nodes,soanyoperationcouldtakeΩ(N󰁏)time.

11.5WeimplementDecreaseKey(X,H)asfollows:IfloweringthevalueofX󰁏createsaheap

【第 1 页 共 3 页】 江西财经大学

10－11第一学期期末考试试卷

试卷代码：03095B 授课课时：80 考试用时：150分钟

课程名称：数据结构与算法 适用对象：本科选课班

试卷命题人

试卷审核人

一、单项选择题（从下列各题四个备选答案中选出一个正确答案，并将其代号写在答题纸相应位置处。答案错选或未选者，该题不得分。每小题2分，共20分。）

1.在数据结构中，从逻辑上可以把数据结构分成 。

A.动态结构和静态结构 B.顺序结构和链式结构

C.线性结构和非线性结构 D.内部结构和外部结构

2.一个栈的入栈序列是1、2、3、4、5，则栈的不可能输出序列是 。

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

3.在一个单链表中，已知p所指结点不是最后结点，在p之后插入s所指结点，则执行

。

A. s->next = p; p->next=s; B. s->next = p->next; p->next = s;

C. s->next = p->next; p = s; D. p->next = s; s->next = p;

4.设s是一个长度为n的字符串，其中所有字符均不相同，则s的非空真子串的个数为 。

A. 2n-1 B. n(n+1)/2 C. n(n+1)/2-1 D. n(n-1)/2-1

5.完全二叉树上有301个结点，其中叶子结点的个数为 。

A. 149 B. 150 C. 151 D. 152

实验5 基于哈夫曼树的数据压缩算法

205

实验5

基于哈夫曼树的数据压缩算法

【实验目的】

1．掌握哈夫曼树的构造算法。

2．掌握哈夫曼编码的构造算法。

【实验内容】

问题描述

输入一串字符串，根据给定的字符串中字符出现的频率建立相应的哈夫曼树，构造哈夫曼编

码表，在此基础上可以对压缩文件进行压缩（即编码），同时可以对压缩后的二进制编码文件进行

解压（即译码）。

输入要求

多组数据，每组数据1行，为一个字符串（只考虑26个小写字母即可）。当输入字符串为“0”

时，输入结束。

输出要求

每组数据输出2n+3行（n为输入串中字符类别的个数）。第1行为统计出来的字符出现频率

（只输出存在的字符，格式为:字符:频度），每两组字符之间用一个空格分隔，字符按照ASCII码

从小到大的顺序排列。第2行至第2n行为哈夫曼树的存储结构的终态（如主教材139页表5.2（b），

一行当中的数据用空格分隔）。第2n+1行为每个字符的哈夫曼编码（只输出存在的字符，格式为：

字符:编码），每两组字符之间用一个空格分隔，字符按照ASCII码从小到大的顺序排列。第2n+2

行为编码后的字符串，第2n+3行为解码后的字符串（与输入的字符串相同）。

输入样例

aaaaaaabbbbbccdddd

aabccc

0

输出样例

a:7 b:5 c:2 d:4

1 7 7 0 0

2 5 6 0 0

3 2 5 0 0

4 4 5 0 0

5 6 6 3 4

6 11 7 2 5