数据结构笔试题
第一部分 选择题
一 单项选择题（本大题共 小题 每小题 分 共 分）在每小题列出的四个选项中只有一个选项是符合题目要求的 请将正确选项前的字母填在题后的括号内
算法分析的目的是( ? 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
绛旓細鍙傝冪瓟妗堟槸锛欰 2銆佺敤閾炬帴鏂瑰紡瀛樺偍鐨勯槦鍒楋紝鍦ㄨ繘琛屾彃鍏ヨ繍绠楁椂( ).A. 浠呬慨鏀瑰ご鎸囬拡 銆 B. 澶淬佸熬鎸囬拡閮借淇敼 C. 浠呬慨鏀瑰熬鎸囬拡 D.澶淬佸熬鎸囬拡鍙兘閮借淇敼 鍙傝冪瓟妗堟槸锛欴 3銆佷互涓鏁版嵁缁撴瀯涓摢涓涓槸闈炵嚎鎬х粨鏋勶紵( )A. 闃熷垪 B. 鏍 C. 绾挎ц〃 D. 浜屽弶鏍 鍙傝冪瓟妗堟槸...
绛旓細1. 鍦ㄤ竴涓崟閾捐〃涓璸鎵鎸囩粨鐐逛箣鍓嶆彃鍏ヤ竴涓猻 (鍊间负e)鎵鎸囩粨鐐规椂锛屽彲鎵ц濡備笅鎿嶄綔锛歲=head;while (q->next!=p) q=q->next;s= new Node; s->data=e;q->next= ; //濉┖ s->next= ; //濉┖ 2. 绾挎ц〃鐨勯『搴忓瓨鍌缁撴瀯鏄竴绉 鐨勫瓨鍌ㄧ粨鏋勶紝鑰岄摼寮忓瓨鍌ㄧ粨鏋勬槸涓绉峗__鐨勫瓨鍌ㄧ粨鏋勩侫.闅忔満...
绛旓細a b c d ? ( )椤哄簭瀛樺偍缁撴瀯? ( )閾捐〃瀛樺偍缁撴瀯 銆攍og N銆+ ( )鍏堟牴閬嶅巻? ( )鍚庢牴閬嶅巻 ( )鏁ｅ垪鍑芥暟? ( )鍐茬獊 ( )纭畾寰呮煡鍏冪礌鎵鍦ㄧ殑鍧 ( )鍦ㄥ潡鍐呮煡鎵惧緟鏌ョ殑鍏冪礌 妗( )閫昏緫缁撴瀯 ? ( )鐗╃悊缁撴瀯 ( )椤哄簭? ( )鐩存帴 鍐掓场鎺掑簭 ? 褰掑苟 鍥 搴旂敤棰(姣忓皬棰 鍒嗗叡鍒) ? 椤哄簭瀹炵幇 const maxsize...
绛旓細1. 瀛樺偍绌洪棿鍒嗛厤锛氭暟缁勬槸涓绉嶉潤鎬鏁版嵁缁撴瀯锛屼竴鏃﹀垱寤猴紝鍏跺ぇ灏忓氨鏄浐瀹氱殑锛屾棤娉曞湪杩愯鏃舵敼鍙樸傛暟缁勫厓绱犲湪鍐呭瓨涓崰鎹繛缁殑绌洪棿锛屽洜姝ゅ叾瀛樺偍绌洪棿鏄鍏堝垎閰嶇殑銆傝岄摼琛ㄦ槸涓绉嶅姩鎬佹暟鎹粨鏋勶紝鍏跺ぇ灏忓彲浠ユ牴鎹渶瑕佸姩鎬佸闀挎垨缂╁皬銆傞摼琛ㄤ腑鐨勬瘡涓妭鐐瑰瓨鍌ㄦ暟鎹拰鎸囧悜涓嬩竴涓妭鐐圭殑鎸囬拡锛岃妭鐐瑰湪鍐呭瓨涓殑浣嶇疆涓嶈繛缁2. ...
绛旓細棰樼洰鎻忚堪锛氬湪涓涓簩缁存暟缁勪腑锛屾瘡涓琛岄兘鎸夌収浠庡乏鍒板彸閫掑鐨勯『搴忔帓搴忥紝姣忎竴鍒楅兘鎸夌収浠庝笂鍒颁笅閫掑鐨勯『搴忔帓搴忋傝瀹屾垚涓涓嚱鏁帮紝杈撳叆杩欐牱鐨勪竴涓簩缁存暟缁勫拰涓涓暣鏁帮紝鍒ゆ柇鏁扮粍涓槸鍚﹀惈鏈夎鏁存暟銆傝緭鍏ユ弿杩: array锛 寰呮煡鎵剧殑浜岀淮鏁扮粍 target锛氭煡鎵剧殑鏁板瓧 杈撳嚭鎻忚堪:鏌ユ壘鍒拌繑鍥瀟rue锛屾煡鎵句笉鍒拌繑鍥瀎alse 棰樼洰鎻...
绛旓細涓銆 閫夋嫨棰橈紙姣忓皬棰2鍒嗭紝鍏24鍒嗭級1锛庤绠楁満璇嗗埆銆佸瓨鍌ㄥ拰鍔犲伐澶勭悊鐨勫璞¤缁熺О涓( A )A.鏁版嵁 B.鏁版嵁鍏冪礌 C.鏁版嵁缁撴瀯 D.鏁版嵁绫诲瀷 2锛庢爤鍜岄槦鍒楅兘鏄紙 A 锛堿锛庨檺鍒跺瓨鍙栦綅缃殑绾挎х粨鏋 B锛庨『搴忓瓨鍌ㄧ殑绾挎х粨鏋 C锛庨摼寮忓瓨鍌ㄧ殑绾挎х粨鏋 D锛庨檺鍒跺瓨鍙栦綅缃殑闈炵嚎鎬х粨鏋 3锛庨摼鏍堜笌...
绛旓細濡備笅杩欎簺鏈夊叧鏁版嵁搴撶煡璇嗚冩煡鐨勭粡鍏绗旇瘯棰锛岄潪甯稿叏闈紝瀵硅绠楁満涓撲笟姣曚笟鐢熷弬鍔犵瑪璇曚細寰堟湁甯姪锛屽缓璁ぇ瀹舵敹钘忋備竴銆侀夋嫨棰 1. 涓嬮潰鍙欒堪姝ｇ‘鐨勬槸___c___銆侫銆佺畻娉曠殑鎵ц鏁堢巼涓庢暟鎹殑瀛樺偍缁撴瀯鏃犲叧 B銆佺畻娉曠殑绌洪棿澶嶆潅搴︽槸鎸囩畻娉曠▼搴忎腑鎸囦护(鎴栬鍙)鐨勬潯鏁 C銆佺畻娉曠殑鏈夌┓鎬ф槸鎸囩畻娉曞繀椤昏兘鍦ㄦ墽琛屾湁闄愪釜姝ラ...
绛旓細璇翠竴涓嬬瑪璇曞拰闈㈣瘯缁忓巻 绗竴涓瑪璇曟槸涓叴鐗圭,杩欎釜鏄棤鎰忕湅瑙佺殑,绗旇瘯棰C璇█銆佹暟鎹簱銆鏁版嵁缁撴瀯杩樻湁鎬濈淮閫昏緫棰,鍙互璇寸瓟鐨勭壒鍒儌,璇ヤ細鐨勯兘涓嶄細浜,褰撴椂涔熸槸澶ц剳鍙戦夯,濂藉儚涓鐬棿浠涔堥兘涓嶄細浜嗐傜浜屾绗旇瘯鐧惧害,绗旇瘯棰樹袱涓昏緫鎬濈淮棰,涓涓綉缁滈,涓涓猚璇█绋嬪簭鎸戦敊闂,涓や釜鍐呭瓨涓庢暟鎹簱鐨勯棶棰,涓涓啓绠楁硶鐨勯銆
绛旓細1.1 绗旇瘯鑰冪偣绛栫暐: 鎻愪緵浜嗛拡瀵鏁版嵁缁撴瀯鑰冭瘯鐨勯噸鐐圭瓥鐣ワ紝甯姪鑰冪敓楂樻晥鍑嗗銆1.2 绗旇瘯鑰冪偣褰掔撼: 瀵硅冭瘯鍙兘鍑虹幇鐨勫悇绫绘暟鎹粨鏋勭煡璇嗙偣杩涜浜嗙郴缁熸暣鐞嗭紝渚夸簬鑰冪敓澶嶄範銆傜2閮ㄥ垎 绗旇瘯棰瑙: 璇︾粏瑙ｆ瀽浜嗗悇绉嶆暟鎹粨鏋勭殑鐞嗚鍜屽疄璺靛簲鐢紝鍖呮嫭锛2.1 姒傝: 瀵规暟鎹粨鏋勭殑鍩烘湰姒傚康杩涜闃愯堪銆2.2 绾挎ц〃: 璁茶В浜嗙嚎鎬...
绛旓細鏁版嵁缁撴瀯闈㈣瘯甯歌闂 绡1 鏁版嵁缁撴瀯涓庣畻娉,杩欎釜閮ㄥ垎鐨勫唴瀹瑰叾瀹炴槸鍗佸垎鐨勫簽澶,瑕佹兂閮借鐩栧埌涓嶅お瀹规槗銆傚湪鏍″涔犻樁娈垫垜浠彲鑳介渶瑕佸姣忕缁撴瀯,姣忕绠楁硶閮藉涔,浣嗘槸鎵惧伐浣绗旇瘯鎴栬呴潰璇曠殑鏃跺,瑕佸湪寰堢煭鐨勬椂闂村唴鑰冨療涓涓汉杩欐柟闈㈢殑鑳藉姏,鎶婃瘡绉嶇粨鏋勫拰绠楁硶閮介棶涓閬嶄笉澶幇瀹炪傛墍浠,瀹為檯鐨勬儏鍐垫槸,浼佷笟涓鑸冨療涓浜涚湅璧锋潵寰堝熀鏈...
