数据结构C语言版期末考试题附带复习资料.doc资源-CSDN文库

版权申诉

138 浏览量 2021-12-15 12:24:08 上传评论收藏 189KB DOC 举报

资源推荐

资源详情

资源评论



数据构造〞期末考试试题

一、单项选择题每题  分，共  分

．在一个单链表  中，假设要向表头插入一个由指针  指向的结点，那么执行。

． ＝ 一＝

．  一＝；＝

．  一＝；＝；

．  一＝ 一 一＝；

． 个顶点的强连通图中至少含有。

 条有向边  条有向边

／ 条有向边  一 条有向边

从一棵二叉搜索树中查找一个元素时，其时间复杂度大致为。





．由权值分别为 ，，，， 的叶子结点生成一棵哈夫曼树，它的带权路径长度为

。

．．

． ． 

．当一个作为实际传递的对象占用的存储空间较大并可能需要修改时，应最好把它说明为 

参数，以节省参数值的传输时间和存储参数的空间。

整形 引用型

指针型 常值引用型!

．向一个长度为  的顺序表中插人一个新元素的平均时间复杂度为。

．．

．．"

二、填空题每空  分，共  分

．数据的存储构造被分为——、——、——和——四种。

．在广义表的存储构造中，单元素结点与表元素结点有一个域对应不同，各自分别为——域

和——域。

．——中缀表达式  十 #／所对应的后缀表达式为————。

．在一棵高度为 $ 的  叉树中，最多含有——结点。

．假定一棵二叉树的结点数为 ，那么它的最小深度为——，最大深度为——!

．在一棵二叉搜索树中，每个分支结点的左子树上所有结点的值一定——该结点的值，右子

树上所有结点的值一定——该结点的值。

 ．当向一个小根堆插入一个具有最小值的元素时，该元素需要逐层——调整，直到被调整到

——位置为止。

．表示图的三种存储构造为——、——和———。

%．对用邻接矩阵表示的具有  个顶点和  条边的图进展任一种遍历时，其时间复杂度为——，

对用邻接表表示的图进展任一种遍历时，其时间复杂度为——。

"．从有序表，，"，，， ，，%中依次二分查找  和  元素时，其

查找长度分别为——和——!

．假定对长度 ＝ 的线性表进展索引顺序查找，并假定每个子表的长度均为，那

么进展索引顺序查找的平均查找长度为——，时间复杂度为——!

．一棵 树中的所有叶子结点均处在——上。

．每次从无序表中顺序取出一个元素，把这插入到有序表中的适当位置，此种排序方法叫

做——排序；每次从无序表中挑选出一个最小或最大元素，把它交换到有序表的一端，

此种排序方法叫做——排序。

&#



．快速排序在乎均情况下的时间复杂度为——，最坏情况下的时间复杂度为——。

三、运算题每题  分，共  分

．假定一棵二叉树广义表表示为 '()，*，)，，分别写出对它进展先序、中序、

后序和后序遍历的结果。

先序：

中序；

后序：

．一个带权图的顶点集 + 和边集 , 分别为：

+＝-"，，，，，.；

   /0-" ，  ， " ，  ， " ，  ，  ，  ，  ，  ，  ，  ，  ， % ，

，".，

那么求出该图的最小生成树的权。

最小生成树的权；

．假定一组记录的排序码为， %，，，"，，"，，那么利用堆排序方法

建立的初始堆为——。

．有个带权结点，其权值分别为 ，，，，，"，，试以它们为叶子结点生成一

棵哈夫曼树，求出该树的带权路径长度、高度、双分支结点数。

带权路径长度：—— 高度：—— 双分支结点数：——。

四、阅读算法，答复以下问题每题  分，共  分

．+*12

-

311；

345'4；

34647，"；

3'8＝-，，，，.

97411＝"1:1;;

19'<18％＝＝"34647，'<18；

45'4，'<18；

.

该算法被调用执行后，得到的线性表  为：

．=71*,>??2>

-

31>??>；

1'<8＝-，，，，.；

97411＝"1:1;;>34>，'<18；

>34>，>>；

>34>，"；

>34>，>>十 ；

@$1A>??/BC>)7?::>>::〞；

.

该算法被调用后得到的输出结果为：

五、算法填空，在画有横线的地方填写适宜的容每题  分，共  分

．从一维数组 <中二分查找关键字为 D 的元素的递归算法，假设查找成功那么返回对应

元素的下标，否那么返回一 。

31)$/BEC<8，37@，1$1$，DCECD

-

&#



197@:＝$1$

-

1B1*＝7@;$1$／；

19D＝＝<B1*8FC；

19D:<B1*8FC；

；

.

4?4；

.

．二叉树中的结点类型 1E4G7* 定义为：

4?)1E4G7*-/BEC*''；1E4G7*#9，#41$.；

其中 *'' 为结点值域，9 和 41$ 分别为指向左、右子女结点的指针域。下面函数的功能

是返回二叉树 E 中值为  的结点所在的层号，请在划有横线的地方填写适宜容。

3G7*=1E4G7*#E，/BECH

-

19E：＝GI4?4"；／／空树的层号为 "

19E 一*''＝＝H4?4／／根结点的层号为 

／／向子树中查找  结点

-

1)＝G7*=E 一9，H；

19)＝4?4);

1)＝；

19；

／／假设树中不存在 H 结点那么返回 7

4?4"；

.

六、编写算法 分

按所给函数声明编写一个算法，从表头指针为  的单链表中查找出具有最大值的结点，该最

大值由函数返回，假设单链表为空那么中止运行。

/3BECJ'+'?G*#

数据构造〞期末考试试题答案

一、单项选择题每题  分，共  分

评分标准；选对者得  分，否那么不得分。

．．．．．．

二、填空题每空  分，共  分

．顺序构造构造索引构造散列构造次序无先后

．值或 *''子表指针或 ?(1

．．／ 一#十

．

一 ／

． 

．小于大于或大于等于

 ．向上堆顶

．邻接矩阵邻接表边集数组次序无先后

&#



%．





"． 

． 

．同一层

．插人选择

．7









三、运算题每题  分，共  分

．先序：'，(，)，*，，9，／／ 分

中序：)，(，*，'，9，，／／ 分

后序：)，*，(，，9，，'／／ 分

．最小生成树的权：／／ 分

．， %，，，"，，"，／／ 分

．带权路径长度：／／ 分

高度：／／ 分

双分支结点数：／／ 分

四、阅读算法，答复以下问题每题  分，共  分

评分标准：每题正确得  分，出现一处错误扣  分，两处及以上错误不得分。

．，，，"，，，

．"

五、算法填空，在画有横线的地方填写适宜的容每题  分，共  分

．9?4B1*／／ 分

4?41)$，7@，B1* 一 ，D／／ 分

4?4B)$，B1*;，$1$，D／／ 分

．G7*=E 一41$，H／／ 分

)04?4) 十 ／／ 分

六、编写算法 分

评分标准：请参考语句后的注释，或根据情况酌情给分。

/BECJ'+'?G7*#。

-

19＝0GI-／／ 分

)44::L1F*1BCA〞::*；

1；

.

/BECB'： 一*''；／／ 分

G*#03 一；／／ 分

@$1MA：GI-／／分

19B': 一*''B'＝ 一*''；

＝ 一；

.

4?4B'；／／ 分

.

数据构造复习资料

&#



一、填空题

数据构造是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的

关系和运算等的学科。

数据构造被形式地定义为〔N5〕，其中  是数据元素的有限集合，5 是  上的关系

有限集合。

数据构造包括数据的逻辑构造、数据的存储构造和数据的运算这三个方面的容。

数据构造按逻辑构造可分为两大类，它们分别是线性构造和非线性构造。

线性构造中元素之间存在一对一关系，树形构造中元素之间存在一对多关系，图形构造中元

素之间存在多对多关系。

．在线性构造中，第一个结点没有前驱结点，其余每个结点有且只有  个前驱结点；最后一

个结点没有后续结点，其余每个结点有且只有  个后续结点。

在树形构造中，树根结点没有前驱结点，其余每个结点有且只有 



个前驱结点；叶子结点没

有后续结点，其余每个结点的后续结点数可以任意多个。

在图形构造中，每个结点的前驱结点数和后续结点数可以任意多个。

%．数据的存储构造可用四种根本的存储方法表示，它们分别是顺序、链式、索引和散列。

"数据的运算最常用的有  种，它们分别是插入、删除、修改、查找、排序。

一个算法的效率可分为时间效率和空间效率。

在顺序表中插入或删除一个元素，需要平均移动表中一半元素，具体移动的元素个数与表长

和该元素在表中的位置有关。

线性表中结点的集合是有限的，结点间的关系是一对一的。

向一个长度为  的向量的第 1 个元素O1O;之前插入一个元素时，需向后移动 P1;

个元素。

向一个长度为  的向量中删除第 1 个元素O1O时，需向前移动 P1个元素。

在顺序表中访问任意一结点的时间复杂度均为  ，因此，顺序表也称为随机存取的数据

构造。

 顺序表中逻辑上相邻的元素的物理位置必定相邻。单链表中逻辑上相邻的元素的物理位置

不一定相邻。

．在单链表中，除了首元结点外，任一结点的存储位置由其直接前驱结点的链域的值指示。

%．在  个结点的单链表中要删除结点#，需找到它的前驱结点的地址，其时间复杂度为

 〔 〕 。

"向量、栈和队列都是线性构造，可以在向量的任何位置插入和删除元素；对于栈只能在栈

顶插入和删除元素；对于队列只能在队尾插入和队首删除元素。

栈是一种特殊的线性表，允许插入和删除运算的一端称为栈顶。不允许插入和删除运算的一

端称为栈底。

队列是被限定为只能在表的一端进展插入运算，在表的另一端进展删除运算的线性表。

不包含任何字符〔长度为

" 〕的串称为空串；由一个或多个空格〔仅由空格符〕组成的串

称为空白串。

子串的定位运算称为串的模式匹配；被匹配的主串称为目标串，子串称为模式。

假设有二维数组 

Q

，每个元素用相邻的  个字节存储，存储器按字节编址。 的起始存储

位置〔基地址〕为 """，那么数组  的体积〔存储量〕为  ；末尾元素 



的第一个

字节地址为  ；假设按行存储时，元素 



的第一个字节地址为

;Q;"""0" ；假设按列存储时，元素 



的第一个字节地址为 Q ＋ Q ＋

""" 〕＝   。

．由３个结点所构成的二叉树有 



种形态。

&#

剩余20页未读，继续阅读

评论收藏

内容反馈

版权申诉

wsbhm62

粉丝: 7
资源: 21万+

数据结构C语言版期末考试题附带复习资料.doc

数据结构C语言版期末考试题(附带复习资料).doc

数据结构C语言版期末考试题附带复习资料...doc

(完整word版)数据结构C语言版期末考试试题(附带复习资料)...doc

(完整word版)数据结构C语言版期末考试试题(附带复习资料).doc

广东省佛山市高一数学上学期期末考试试题(扫描版，无答案) 试题.doc

【南京工程学院】计算机网络复习资料.zip

广工计算机系统结构试题及考点

数据结构C语言版期末考试题附带复习资料...pdf

数据结构C语言版期末考试试题(附带复习资料)1.pdf

数据结构C语言版期末考试题附带复习资料.pdf

数据结构C语言2016总复习附带试卷及答案.doc

C语言复习资料附带答案

数据结构课程设计各种排序算法比较 附带源代码.doc

数据结构C语言版附带demo哦

南开C语言100题附带答案.doc

发动机原理B复习资料附带答案.doc

C语言课程设计报告-教室管理系统（附带源码）.doc

操作系统期末考试简答题汇总（全、附带答案）.doc

Java 面经手册·小傅哥.pdf

解压后拖入浏览器扩展程序使用.zip

103套PPT模板.zip

Beyond Compare 免安装直接使用

notepad++.exe官网下载

Mars4_5.zip

QT自制精美Ui模板系列（一）桃子风格模板 - 二次开发专用

keygen_2032.rar

最新资源

数据结构课程设计各种排序算法比较附带源代码.doc