第一部分 选择题
一 单项选择题（本大题共 小题 每小题 分 共 分）在每小题列出的四个选项中只有一个选项是符合题目要求的 请将正确选项前的字母填在题后的括号内
算法分析的目的是( ? 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
二叉树的结构如下图所示 其中序遍历的序列为( ? )
A a b d g c e f h
B d g b a e c h f
C g d b e h f c a
D a b c d e f g h
深度为 的二叉树至多有(? C? )个结点 ( ^M )
A ? B ? C ? D
对于一个具有n个顶点的无向图 若采用邻接表表示 则存放表头结点的数组的大小为 (? A? )
A n ? B n+ ? C n ? D n+边数
在一个具有n个顶点的无向图中 要连通全部顶点至少需要(? C? )条边
A n ? B n+ ? C n ? D n/
静态查找表与动态查找表二者的根本差别在于(? 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连接的结果为 ________
通常单链表的头结点指的是________ 单链表的首结点指的是________
一个队列的入队序列是a b c d 则队列的输出序列为________
栈结构通常采用的两种存储结构是________和________
具有N个结点的完全二叉树的深度为________
树的三种主要的遍历方法是 ________ ________和层次遍历
在无向图的邻接矩阵A中 若A〔i j〕等于 则A〔j i〕等于________
采用散列技术实现散列表时 需要考虑的两个主要问题是 构造________和解决________
索引顺序表上的查找分两个阶段 ( )________ ( )________
散列文件中的记录通常是成组存放的 若干的记录组成一个存储单位 称作________
就文件而言 按用户的观点所确定的基本存储单元称为________ 按外设的观点所确定的基本存储单元称为________
文件的检索有三种方式 ________存取 ________存取和按关键字存取
最简单的交换排序方法是________排序
外排序的基本方法是________
四 应用题(每小题 分 共 分)
假定在学生的档案中含有 姓名 学号 年龄 性别 如采用线性表作为数据结构来实现档案管理问题 分别给出线性表的在顺序实现下的类型定义和在链接实现下的类型定义
有一份电文 *** 使用五个字符 a b c d e 它们的出现频率依次为 请构造相应的哈夫曼树(左子树根结点的权小于等于右子树根结点的权) 求出每个字符的哈夫曼编码
有初始的无序序列为{ } 给出对其进行归并排序(升序)的每一趟的结果
五 设计题(每小题 分 共 分)
假设用一个循环单链表来表示队列(称为循环链队) 该队列中只设一个队尾指 针rear 不设队首指针 请编写向循环链队中插入一个元素X的过程
以邻接表为存储结构 写出连通图的深度优先搜索算法
设有一组关键字{ } 采用散列函数 H(key)=key MOD 采用线性探测法解决冲突 试在 ～ 的散列地址空间中对该关键字序列构造散列表
数据结构导论试题参考答案
一 单项选择题(每小题 分 共 分) ? C ? B ? D ? B ? A
C ? B? C ? A ? C
B D C C
二 判断题(每小题 分 共 分)
× ? × ? × × ? ×
√ ? √ ? × × √ 三 填空题(每小题 分 共 分) ? ( )数据表示? ( )数据处理 ? ′data structure′ ? ( )在单链表第一个结点之前增设的一个类型相同的结点
( )表结点中的第一个结点 ? a b c d ? ( )顺序存储结构? ( )链表存储结构
〔log N〕+
( )先根遍历? ( )后根遍历
( )散列函数? ( )冲突
( )确定待查元素所在的块 ( )在块内查找待查的元素
桶
( )逻辑结构 ? ( )物理结构
( )顺序? ( )直接
冒泡排序 ? 归并 四 应用题(每小题 分 共 分) ? 顺序实现
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:adj list;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(g p↑ 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( )=
lishixinzhi/Article/program/sjjg/201404/30585
数据结构试题
参考答案是：D 3、以下数据结构中哪一个是非线性结构？( )A. 队列 B. 栈 C. 线性表 D. 二叉树 参考答案是：D 4、设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(1...
数据结构笔试题
a b c d ? ( )顺序存储结构? ( )链表存储结构 〔log N〕+ ( )先根遍历? ( )后根遍历 ( )散列函数? ( )冲突 ( )确定待查元素所在的块 ( )在块内查找待查的元素 桶( )逻辑结构 ? ( )物理结构 ( )顺序? ( )直接 冒泡排序 ? 归并 四 应用题(每小题 分共分) ? 顺序实现 const maxsize...
算法人员求职面试笔试题目
1、数据结构 若一颗二叉树的前序遍历为a,e,b,d,c后序遍历为b,c,d,e,a，则根节点的孩子节点( )答案：A 解析：根节点为a，其左子节点为e，无右子节点。2、算法 已知一个无向图中顶点A,B的一条最短路P，如果把各个边的重变为原来的2倍，那么在新图中，P仍然是A,B之间的最短路，以上...
数据结构笔试题和答案
1. 在一个单链表中p所指结点之前插入一个s (值为e)所指结点时，可执行如下操作：q=head;while (q->next!=p) q=q->next;s= new Node; s->data=e;q->next= ; \/\/填空 s->next= ; \/\/填空 2. 线性表的顺序存储结构是一种 的存储结构，而链式存储结构是一种___的存储结构。A.随机...
经典笔试面试知识整理,数据结构与算法(代码演示)
题目描述：在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。输入描述: array： 待查找的二维数组 target：查找的数字 输出描述:查找到返回true，查找不到返回false 题目描...
数据结构面试常见问题
数据结构面试常见问题 篇1 数据结构与算法,这个部分的内容其实是十分的庞大,要想都覆盖到不太容易。在校学习阶段我们可能需要对每种结构,每种算法都学习,但是找工作笔试或者面试的时候,要在很短的时间内考察一个人这方面的能力,把每种结构和算法都问一遍不太现实。所以,实际的情况是,企业一般考察一些看起来很基本...
2006年3月全国计算机等级考试三级数据库笔试试题及答案
无 为大家收集整理了《2006年3月全国计算机等级考试三级数据库笔试试题及答案》供大家参考,希望对大家有所帮助!!! 一、选择题(每小题1分,共60分) 下列各题A)、B)、C)、D)四个选项中,只有一个选项是正确的。请将正确选项涂写在答题卡相应位置上,答在试卷上不得分。 (1)计算机软件分为系统软件和应用软件...
求2010年3月计算机二级C语言笔试复习资料
一、选择题(每题2分,共计70分) 1.(1)下列数据结构中,属于非线性结构的是 A)循环队列 B)带链队列 C)二叉树 D)带链栈 A B C D 2. (2)下列数据结构中,能够按照“先进后出”原则存取数据的是 A)循环队列 B)栈 C)队列 D)二叉树 A B C D 3. (3)对于循环队列,下列叙述中正确的是 A)队头指...
西门子PLC—35道笔试题 !
深入探索西门子PLC的35道经典笔试题 一、基础概念篇 1. 位与字的关系： MW0，作为第1字的组成部分，MW4则代表第3个字的首位，揭示了数据结构的微妙之处。2. 数据类型区分： 16位的WORD，无符号的，与INT虽同为16位，但数据范围和表示方式各有特色。3. 内存地址解析： MD103，这个8位字节，隐藏...
说一下笔试和面试经历
说一下笔试和面试经历 第一个笔试是中兴特种,这个是无意看见的,笔试题C语言、数据库、数据结构还有思维逻辑题,可以说答的特别烂,该会的都不会了,当时也是大脑发麻,好像一瞬间什么都不会了。第二次笔试百度,笔试题两个逻辑思维题,一个网络题,一个c语言程序挑错问题,两个内存与数据库的问题,一个写算法的题。