数据结构笔试题

第一部分选择题

一道选择题(此大题* * *小题* *每道小题加分)每道小题所列四个选项中只有一个符合题型要求。请在问题后的括号中填写正确选项前的字母。

算法分析的目的是(？c？)

a找出数据结构的合理性B研究算法中的输入输出关系。

C分析算法的效率是提高D分析算法的可读性。

使用(？b)更合适

单链表b双链表

c序列表d循环链表

下列关于线性表的说法错误的是(？d？)

顺序表是用一维数组实现的线性表

顺序表必须占用一个连续的存储单元。

C顺序表的空间利用率高于链表。

链表中的每个节点只有一个链域。

首节点的单链表头为空的判断条件是(b)

人头=零？B head & gt下一个=零

C head & gt下=头？D head & lt& gt无

队列通常采用两种存储结构:(a)

a顺序存储结构和链表存储结构b哈希模式和索引模式

c链表存储结构和数组D线性存储结构和非线性存储结构

根据二叉树的定义，有节点的二叉树是(？c？)物种

答？b？c？D

二叉树的结构如下图所示，其中顺序遍历的顺序是(？)

A a b d g c e f h

英国皇家航空公司

C g d b e h f c a

D a b c d e f g h

深度最多为(？c？)节点(m)

答？b？c？D

对于一个有n个顶点的无向图，如果用邻接表表示，存储头节点的数组的大小是(？答？)

一个n？B n+？C n？D n+边数

在一个有n个顶点的无向图中，至少需要(？c？)边缘

一个n？B n+？C n？d不适用

静态查找表和动态查找表的根本区别在于(？b？)

它们的逻辑结构不同。

b对它有不同的操作。

c包含不同类型的数据元素。

d存储实现不同。

Hash文件使用hash函数将记录的键值计算成记录的存储地址，因为hash函数不是一一对应的关系，所以选择一个好的(？d？)方法是哈希文件的关键。

哈希函数？b除法中的素数

冲突处理？散列函数和冲突处理

对于大文件的排序，要研究外设上的排序技术，即(C？)

快速排序方法？b-内部排序法

c外部排序法？三维交叉排序法

有无序的元素，希望以最快的速度挑出第一个最大的元素。最好选择(？c？)方法

冒泡排序b快速排序

c堆排序d基数排序

2.判断题(在题干后的括号内打√，判断后面的问题是否正确，每项打* * *分)

数据的逻辑结构是指数据元素之间的逻辑关系(？)

在线性结构中，每个节点都有一个直接前任和一个直接继任者(？)

插入和删除是数组的两个基本操作(？)

头节点(？)

在二叉树中插入一个节点，使得二叉树不再是二叉树(？)

查找表的逻辑结构是一个集合(？)

静态查找表的检索和修改分为两个不相交的阶段。)

当向索引顺序文件中插入新记录时，必须复制整个文件(？)

如果某种排序算法不稳定，这种方法就没有实际应用价值。)

最坏的情况下，需要(n)(？)

填空(给每个小问题打* * *分)

编程的本质是_ _ _ _ _ _和_ _ _ _ _ _

设字符串a='data' b='structure' c= ' '，那么A与C连接，再与B连接的结果是_ _ _ _ _ _ _ _ _。

通常单链表的头节点是指_ _ _ _ _ _单链表的头节点是指_ _ _ _ _ _ _。

一个队列的入队顺序是a b c d，队列的输出顺序是_ _ _ _ _ _ _ _ _。

栈结构中常用的两种存储结构是_ _ _ _ _ _和_ _ _ _ _ _

有n个节点的完全二叉树的深度是_ _ _ _ _ _ _ _ _

树的三种主要遍历方式是_ _ _ _ _ _ _ _ _ _ _ _ _ _和层次遍历。

在无向图的邻接矩阵A中，若a [i j]相等，则a [i j]等于_ _ _ _ _ _ _ _ _。

使用哈希技术实现哈希表时，需要考虑的两个主要问题是构造_ _ _ _ _ _ _和求解_ _ _ _ _ _。

索引顺序表上的搜索分为两个阶段()_ _ _ _ _ _ _ () _ _ _ _ _ _ _

哈希文件中的记录通常分组存储，形成一个称为_ _ _ _ _ _ _ _的存储单元。

就文件而言，从用户角度确定的基本存储单元称为_ _ _ _ _ _从外围设备角度确定的基本存储单元称为_ _ _ _ _ _ _ _ _ _

检索文档有三种方式_ _ _ _ _ _ _访问_ _ _ _ _访问和关键字访问。

最简单的交换排序方法是_ _ _ _ _ _ _ _ _排序。

外部排序的基本方法是_ _ _ _ _ _ _ _ _

四个应用问题(每个小问题得分* * *分)

假设学生档案中包含姓名、学号、年龄、性别，如果用线性表作为数据结构实现档案管理，分别给出了线性表在顺序实现和链接实现下的类型定义。

有一条消息* * *用了a b c d e五个字符，它们出现的频率依次是。请构造相应的霍夫曼树(左子树根节点的权值小于等于右子树根节点的权值)，找出每个字符的霍夫曼码。

有一个初始的无序序列，它给出了{}每次合并和排序(升序)的结果

五个设计问题(每个小问题* * *分)

假设使用循环单链表来表示队列(称为循环链队列)。该队列中只有一个队列尾指针，但没有队列尾指针。请写出将一个元素X插入循环链队列的过程。

以邻接表为存储结构写连通图的深度优先搜索算法

有一组关键字{}，使用哈希函数H(key)=key MOD来解决冲突。尝试在~的哈希地址空间中为这个关键字序列构造一个哈希表

数据结构概论试题参考答案

1道选择题(每道小题得分* * *分)？c？b？d？b？A

c？b？c？答？C

商务英语

2.是非题(每个小问题得分* * *分)

× ?× ?×?× ?×?

√ ?√ ?× × √?填空(每道小题* * *分)？()数据表示？()数据处理？“数据结构”？()在单链表的第一个节点前添加一个同类型的节点。

()表节点中的第一个节点？a b c d？()顺序存储结构？()链表存储结构

〔记录N〕+

()先根遍历？()根后遍历

()哈希函数？()冲突

()确定要检查的元素所在的块()在块中找到要检查的元素。

水桶

()逻辑结构？()物理结构

()订单？()直接

冒泡排序？合并四道应用题(每道小题得分* * *分)？顺序实现

const maxsize∶；=；{顺序表容量}？类型数据类型=记录{文件数据类型}

name∶string『string』；{姓名}

数字∶整数；{学生编号}

性别∶布尔；{性别}

年龄∶整数；{年龄}

结束；

类型slist =记录

数据类型的数据∶数组〔 maxsize〕

last∶integer；

结束；

链接实现

类型指针=↑节点；

节点=记录

name∶string『string』；{姓名}

编号:interger {学生编号}

性别∶布尔；{性别}

年龄∶整数；{年龄}

next∶指针；{节点的后续指针}

结束；

list =指针；

霍夫曼树是

相应的霍夫曼代码是

答:？b:？c:？d:？e:

画出正确的霍夫曼树，写出相应的霍夫曼代码。

初始无序序列

{ } { } { } { } { } { } { }{ } { }{ }

第一次合并{} {}？{ }?{ }

第二次合并？{ } { ?}?{ }

第三次合并{？}?{ }

第四次合并{}

五个设计问题(每个小问题* * *分)

过程插入(VAR rear∶pointer；x∶整数)；

VAR head tmp∶pointer；

开始

新(tmp)；

tmp↑data⊙= x；

If (rear = nil)则{循环队列为空，新节点是队列的第一个节点}

开始

后方:⊙= tmp；

后方↑下一个≑= tmp；

结束

否则{队列不为空。在队列末尾插入新节点}

开始

头≑=后↑下一个；

后方↑下一个≑= tmp；

后方:⊙= tmp；

后方↑下一个≑=头部；

结束

结束；

程序dfs(g:调整列表；v∶整数)；

{来自V的深度优先遍历图G }

开始

写(五)；

已访问(v)∴= true；？{访问过的旗帜v }

p = g〔v〕link；？{找到V的第一个相邻点}

而p & lt& gt没有

〔如果没有(访问过〔p〕顶点〕

然后dfs(g p↑顶点)；

p:= p = next {求V的下一个相邻点}

结束；

以邻接表为存储结构的连通图的深度优先搜索是顺序搜索链表。

施工流程如下

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 =

因此，每个关键字对应的地址分配如下

地址()=

Lishi Xinzhi/Article/program/sjjg/201404/30585