数据结构教程第5版李春葆

数据结构知识点

第1章绪论

知识点归纳

一、数据结构概述

1.数据结构的定义

（1）基本概念

数据是描述客观事物的数和字符的集合，是计算机能操作的对象的总称，也是计算机处理信息的某种特定的符号表示形式。

（2）相关术语

① 数据元素

数据元素又称元素、节点、顶点、记录等。数据元素是数据的基本单位。有时候，一个数据元素可以由若干个数据项组成。

② 数据项

数据项又称字段或域，它是具有独立含义的最小数据单位。

③ 数据对象

数据对象是性质相同的数据元素的集合，它是数据的子集。

（3）数据结构的内容

① 数据元素之间的逻辑关系，即数据的逻辑结构，它是数据结构在用户面前呈现的形式。

② 数据元素及其关系在计算机存储器中的存储方式，即数据的存储结构，又称数据的物理结构。

③ 施加在数据上的操作，即数据的运算。

（4）逻辑结构

数据的逻辑结构是从逻辑关系（主要是指数据元素的相邻关系）上描述数据的，它与数据的存储无关，是独立于计算机的。因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。

（5）存储结构

数据的存储结构是逻辑结构用计算机语言的实现或在计算机中的表示（又称映像），也就是逻辑结构在计算机中的存储方式，它是依赖于计算机语言的。一般只在高级语言（例如C／C++语言）的层次上讨论存储

数据结构（C语言篇）―习题与解析（修订版）

清华大学出版社

一、绪论 选择题

1.数据结构是一门研究非数值计算的程序设计问题 计算机的 以及它们之间的 和运算等的学科。

1 A.数据元素 B.计算方法 C.逻辑存储 D.数据映像 2 A.结构 B.关系 C.运算 D.算法 2.数据结构被形式地定义为 (K, R)，其中K是 的有限集，R是K上的 有限集。

1 A.算法 B.数据元素 C.数据操作 D.逻辑结构 2 A.操作 B.映像 C.存储 D.关系 3.在数据结构中，从逻辑上可以把数据结构分成 。

A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C.线性结构和非线性结构 D.内部结构和外部结构 4.线性结构的顺序存储结构是一种 A 的存储结构，线性表的链式存储结构是一种 B 的存储结构。

A.随机存取 B.顺序存取 C.索引存取 D.散列存取 5.算法分析的目的是 C ，算法分析的两个主要方面是 AB 。 1 A.找出数据结构的合理性 B.研究算法中的输入和输出的关系

C.分析算法的效率以求改进 D.分析算法

第6章 图

1．选择题

（1）在一个图中，所有顶点的度数之和等于图的边数的（ ）倍。 A．1/2 B．1 C．2 D．4

（2）在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（ ）倍。 A．1/2 B．1 C．2 D．4 （3）具有n个顶点的有向图最多有（ ）条边。

A．n B．n(n-1) C．n(n+1) D．n2

（4）n个顶点的连通图用邻接距阵表示时，该距阵至少有（ ）个非零元素。 A．n B．2(n-1) C．n/2 D．n2

（5）G是一个非连通无向图，共有28条边，则该图至少有（ ）个顶点。 A．7 B．8 C．9 D．10 （6）若从无向图的任意一个顶点出发进行一次深度优先搜索可以访问图中所有的顶点，则该图一定是（ ）图。

A．非连通

您的本次作业分数为：97分
单选题
1.从原理上讲，折半查找法要求查找表中各元素的键值必须是____
A 递增或递减

B 递增

C 递减

D 无序
正确答案:A
单选题
2.关于判定树，下列说法不正确的是____
A 判定树是对有序序列进行二分查找得到的树

B n个结点的判定树的深度为[log2n]+1

C 判定树的叶子结点都在同一层

D 判定树除去最后一层结点以后是满二叉树或空二叉树
正确答案:C
单选题
3.在顺序表{2、5、7、10、14、15、18、23、35、41、52}中，用二分法查找关键码12需做____次关键码比较
A 2

B 3

C 4

D 5
正确答案:C
单选题
4.对线性表进行二分查找时，要求线性表必须____
A 以顺序方式存储

B 以顺序方式存储且元素有序

C 以链式方式存储

D 以链式方式存储且元素有序
正确答案:B
单选题
5.折半查找算法的时间复杂度是____
A O(n2)

B O(n)

C O(log2n)

D O(nlog2n)
正确答案:C
单选题
6.若用二分查找法取得的中间位置元素键值大于被查找值，说明被查找值位于中间值的前面，下次的查找区间为从原开始位置至____
A 该中间位置

目 录

第一部分 预备知识 ....................................................................................................... 1

预备知识 ............................................................................................................... 1 预备知识实验 ......................................................................................................... 2 第二部分 基础实验 ....................................................................................................... 4

实验1 线性表的基本操作 ...........................................

1、画出对下列存储于数组中的值执行buildheap后得到的最大值堆： 10 5 12 3 2 1 8 7 9 4

先序遍历为12 10 4 1 2 9 5 8 3 7 中序遍历为1 4 2 10 5 9 12 3 8 7

2、假设某字母表各个字母的权如下：

Q Z F M T S O E 2 3 10 10 10 15 20 30

(a) 按照这个字母表，一个包含n个字母的字符串采用Huffman编码在最差情况下需要多少位？怎样的串会出现最差情况？

在最差的情况下需要5*n位，当所有的字母都是Q或者Z的时候。

（b）按照这个字母表，包含n个字母的字符串采用Huffman编码在最佳情况下需要多少位？怎样的串会出现最佳情况？

在最佳的情况下需要2*n位，当所有的字母都是E或者O的时候。 （c）按照一个字母表，一个字母平均需要多少位？

（2*30 + 2*20 + 3*15 + 3*10 + 3*10 + 4*10 + 5*3+ 5*2）/100 =2.7 ∴ 2.7

3、

第 5 章 数组

一、选择题

3. 设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1 到8 ，j的值为1 到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为( A )。

A. BA+141 B. BA+180 C. BA+222 D. BA+225 4. 假设以行序为主序存储二维数组A=array[1..100，1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5，5]=（ A ）。 A. 808 B. 818 C. 1010 D. 1020 5. 数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址是( )。1195

A. 1175 B. 1180 C. 1205 D. 1210

7. 将一个A[1..100，1.

楚雄师院计科系 网络工程2010级 《算法与数据结构》课后习题（第4~5章）

【课后习题】第4章 串 第5章 数组和广义表

网络工程2010级（ ）班 学号： 姓名：

题 号 得 分 一 二 三 四 总分 一、填空题（每空1分，共30分）

1. 串有三种机内表示方法： 、 和 ，其中前两种属于顺序存储结构，第三种属于 。

2. 若n为主串长度，m为子串长度，则串的BF（朴素）匹配算法最坏的情况下需要比较字符的总次数

为 ,T(n)= 。

3. 是任意串的子串；任意串S都是S本身的子串，除S本身外，S的其他子串称为S的 。 4. 设数组a[1?50, 1?60]的基地址为1000，每个元素占2个存储单元，若以行序为主序顺序存储，则

元素a[32,58]的存储地址为 。

5. 对于数组，比较适于采用 结构够进行存储。 6. 广义表的深度是指____

第四章 串

一、选择题

1．下面关于串的的叙述中，哪一个是不正确的？（ ）【北方交通大学 2001 一、5（2分）】

A．串是字符的有限序列 B．空串是由空格构成的串

C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储 2 若串S1=‘ABCDEFG’, S2=‘9898’ ,S3=‘###’,S4=‘012345’,执行

concat(replace(S1,substr(S1,length(S2),length(S3)),S3),substr(S4,index(S2,‘8’),length(S2))) 其结果为（ ）【北方交通大学 1999 一、5 （25/7分）】

A．ABC###G0123 B．ABCD###2345 C．ABC###G2345 D．ABC###2345 E．ABC###G1234 F．ABCD###1234 G．ABC###01234

3．设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（ ）

A．求子串 B．联接 C．匹配 D．求串长 【北京邮电大学

数据结构实验报告——实验5

学号： 姓名： 得分：______________

一、实验目的

1、复习栈的逻辑结构、存储结构及基本操作； 2、掌握顺序栈、链栈。

二、实验内容

1、（必做题）假设栈中数据元素类型是字符型，请采用顺序栈实现栈的以下基本操作： （1）Status InitStack (&S) //构造空栈S； （2）Status Push(&S, e) //元素e入栈S；

（3）Status Pop(&S, &e) //栈S出栈，元素为e。 2、（必做题）请实现：对于一个可能包括括号{}、[]、()的表达式，判定其中括号是否匹配。

三、算法描述

（采用自然语言描述）

1. 构建空栈s，输入元素，将元素依次入栈，遍历打印栈中元素，输出栈顶元素，打印被输出的元素，遍历打印栈中元素。

2.构建空栈，输入表达式，使用函数count判断表达式中括号是否匹配，如果匹配输出匹配正确，不匹配则输出匹配错误。

四、详细设计

1.

开始 构建空栈s 输入元素 将元素依次入栈 遍历打印栈中元素 输出栈顶元素 打印被输出的元素 遍历打印栈中元素 结束 1

2.

开始 构建空栈s 输入表达式 使用函数count判断表达式中括号是否匹配 输