第一部分 选择题
一单项选择题（本大题共小题每小题分共分）在每小题列出的四个选项中只有一个选项是符合题目要求的请将正确选项前的字母填在题后的括号内
算法分析的目的是( ? C? )
A找出数据结构的合理性 B研究算法中的输入/输出关系
C分析算法的效率以求改进 D分析算法的易读性
在需要经常查找结点的前驱与后继的场合中使用(? B )比较合适
A单链表 B双链表
C顺序表 D循环链表
下面关于线性表的叙述中错误的为(? D ? )
A顺序表使用一维数组实现的线性表
B顺序表必须占用一片连续的存储单元
C顺序表的空间利用率高于链表
D在链表中每个结点只有一个链域
带头结点的单链表head为空的判断条件是( B )
A head=NIL ? B head>next=NIL
C head>next=head ? D head< >NIL
队列通常采用两种存储结构是( A )
A顺序存储结构和链表存储结构 B散列方式和索引方式
C链表存储结构和数组 D线性存储结构和非线性存储结构
按照二叉树的定义具有个结点的二叉树有(? C? )种
A ? B ? C ? D
二叉树的结构如下图所示其中序遍历的序列为( ? )
Aabdgcefh
Bdgbaechf
Cgdbehfca
Dabcdefgh
深度为的二叉树至多有(? C? )个结点 (^M)
A ? B ? C ? D
对于一个具有n个顶点的无向图若采用邻接表表示则存放表头结点的数组的大小为 (? A? )
An ? Bn+ ? Cn ? Dn+边数
在一个具有n个顶点的无向图中要连通全部顶点至少需要(? C? )条边
An ? Bn+ ? Cn ? Dn/
静态查找表与动态查找表二者的根本差别在于(? B? )
A它们的逻辑结构不一样
B施加在其上的操作不同
C所包含的数据元素的类型不一样
D存储实现不一样
散列文件使用散列函数将记录的关键字值计算转化为记录的存放地址因为散列函数不是一对一的关系所以选择好的( ?D? )方法是散列文件的关键
A散列函数 ? B除余法中的质数
C沖突处理 ? D散列函数和沖突处理
对于大文件的排序要研究在外设上的排序技术即( C? )
A快速排序法 ? B内排序法
C外排序法 ? D交叉排序法
设有个无序的元素希望用最快的速度挑选出其中前个最大的元素最好选用(? C? )法
A冒泡排序 B快速排序
C堆排序 D基数排序
二判断题(判断下列各题正确的在题干后面括号内打√错误的打×每小题分共分)
所谓数据的逻辑结构指的是数据元素之间的逻辑关系( ? )
在线性结构中每个结点都有一个直接前驱和一个直接后继( ? )
插入和删除是数组的两种基本操作( ? )
在链栈的头部必须要设置头结点( ? )
在二叉树中插入结点则该二叉树便不再是二叉树( ? )
查找表的逻辑结构是集合( ? )
静态查找表的检索与修改被分成两个不交叉的阶段分别进行( ? )
在索引顺序文件中插入新的记录时必须复制整个文件( ? )
如果某种排序算法是不稳定的则该方法没有实际的应用价值( ? )
对于n个记录的集合进行冒泡排序在最坏情况下所需要的时间是(n)( ? )
三填空题(每小题分共分)
程序设计的实质是________和________
设由字符串a=′data′b=′structure′c=′′则a与c连接然后与b连接的结果为________
通常单链表的头结点指的是________单链表的首结点指的是________
一个队列的入队序列是abcd则队列的输出序列为________
栈结构通常采用的两种存储结构是________和________
具有N个结点的完全二叉树的深度为________
树的三种主要的遍历方法是________________和层次遍历
在无向图的邻接矩阵A中若A〔ij〕等于则A〔ji〕等于________
采用散列技术实现散列表时需要考虑的两个主要问题是构造________和解决________
索引顺序表上的查找分两个阶段()________()________
散列文件中的记录通常是成组存放的若干的记录组成一个存储单位称作________
就文件而言按用户的观点所确定的基本存储单元称为________按外设的观点所确定的基本存储单元称为________
文件的检索有三种方式________存取________存取和按关键字存取
最简单的交换排序方法是________排序
外排序的基本方法是________
四应用题(每小题分共分)
假定在学生的档案中含有姓名学号年龄性别如采用线性表作为数据结构来实现档案管理问题分别给出线性表的在顺序实现下的类型定义和在链接实现下的类型定义
有一份电文中共使用五个字符abcde它们的出现频率依次为请构造相应的哈夫曼树(左子树根结点的权小于等于右子树根结点的权)求出每个字符的哈夫曼编码
有初始的无序序列为{}给出对其进行归并排序(升序)的每一趟的结果
五设计题(每小题分共分)
假设用一个循环单链表来表示队列(称为循环链队)该队列中只设一个队尾指 针rear不设队首指针请编写向循环链队中插入一个元素X的过程
以邻接表为存储结构写出连通图的深度优先搜索算法
设有一组关键字{}采用散列函数H(key)=key MOD 采用线性探测法解决沖突试在～的散列地址空间中对该关键字序列构造散列表
数据结构导论试题参考答案
一单项选择题(每小题分共分) ? C ? B ? D ? B ? A
C ? B? C ? A ? C
B D C C
二判断题(每小题分共分)
× ? × ? × × ? ×
√ ? √ ? × × √ 三填空题(每小题分共分) ? ()数据表示? ()数据处理 ?′datastructure′ ? ()在单链表第一个结点之前增设的一个类型相同的结点
()表结点中的第一个结点 ? abcd ? ()顺序存储结构? ()链表存储结构
〔logN〕+
()先根遍历? ()后根遍历
()散列函数? ()沖突
()确定待查元素所在的块 ()在块内查找待查的元素
桶
()逻辑结构 ? ()物理结构
()顺序? ()直接
冒泡排序 ? 归并 四应用题(每小题分共分) ? 顺序实现
const maxsize∶=; ｛顺序表的容量｝ ? type datatype=record ｛档案数据类型｝
name∶string〔〕;｛姓名｝
number∶integer;｛学号｝
sex∶boolean;｛性别｝
age∶integer;｛年龄｝
end;
type slist =record
data∶array 〔maxsize〕 of datatype;
last∶integer;
end;
链接实现
type pointer=↑node;
node=record
name∶string 〔〕;｛姓名｝
number∶interger ｛学号｝
sex∶ boolean;｛性别｝
age∶integer;｛年龄｝
next∶pointer;｛结点的后继指针｝
end;
list=pointer;
哈夫曼树为
相应的哈夫曼编码为
a: ? b: ? c: ? d: ? e:
画出正确的哈夫曼树给分写出相应哈夫曼编码给分
初始无序序列? ? ? ?
｛｝ ｛｝ ｛｝ ｛｝ ｛｝ ｛｝ ｛｝｛｝ ｛｝｛｝
第一次归并 ｛ ｝ ｛ ｝ ｛ ｝? ｛ ｝? ｛ ｝
第二次归并 ? ｛ ? ? ｝ ｛ ? ｝? ｛ ｝
第三次归并 ｛ ? ｝? ｛ ｝
第四次归并 ｛ ? ? ｝
五设计题(每小题分共分)
PROCEDURE insert (VAR rear∶pointer; x∶integer);
VAR head tmp∶pointer;
BEGIN
new(tmp);
tmp↑data∶=x;
if (rear=NIL) then ｛循环队列为空新结点是队列的首结点｝
BEGIN
rear∶=tmp;
rear↑next∶=tmp;
END
else ｛队列不空将新结点插入在队列尾｝
BEGIN
head∶=rear↑next;
rear↑next∶=tmp;
rear∶=tmp;
rear↑next∶=head;
END
END;
procedure dfs(g:adjlist;v∶integer);
｛从v出发深度优先遍历图g｝
begin
write(v);
visited(v)∶=true; ? ｛标志v已访问｝
p=g〔v〕link; ? ｛找v的第一个邻接点｝
while p< >nil do
〔 if not (visited〔p↑vertex〕)
then dfs(gp↑vertex);
p∶=p↑next〕 ｛找v的下一个邻接点｝
end;
以邻接表为存储结构连通图的深度优先搜索就是顺序查找链表
构造过程如下
H()= MOD =
H()= MOD =
H()= MOD =
H()= MOD =(沖突)
H()=(+) MOD =
H()= MOD =
H()= MOD =
H()= MOD = (沖突)
H()=(+) MOD = (仍沖突)
H()=(+) MOD =
H()= MOD = (沖突)
H()=(+) MOD = (沖突)
H()=(+) MOD = (仍沖突)
H()=(+) MOD =
H()= MOD = (沖突)
H()=(+) MOD = (仍沖突)
H()=(+) MOD =
H()= MOD =
H()= MOD = (沖突)
H()=(+) MOD = (仍沖突)
H()=(+) MOD =
H()= MOD = (沖突)
H()=(+) MOD =
因此各关键字相应的地址分配如下
address()=
address()=
address()=
address()=
address()=
address()=
address()=
address()=
address()=
address()=
address()=
address()=
其余的地址中为空
