数据结构(710)参复习资料 - 副本

2024-07-28 作者:

数据结构(710)复习资料一、单选题答题要求:下列各题，只有一个符合题意的正确答案，请选择你认为正确的答案，多选、错选、不选均不得分。

1、判断一个循环队列QU(最多元素为m)为满队列的条件是（）。

->front==QU->->front!=QU->->front==(QU->rear+1)%->front!=(QU->rear+1)%m参考答案:C答案解析:无

2、设二叉树的树根为第一层，则第i层上至多有（)结点。

A.1B.2C.2i-1D.2i+1参考答案:C答案解析:无

3、已知8个元素为{34，76，45，18，26，54，92，65}，按照依次插入结点的方法生成一棵二叉排序树，最后两层上结点的总数为（）。

A.1B.2C.3D.4参考答案:B答案解析:无

4、对线性表进行二分查找时，要求线性表必须（）。

A.以顺序方式存储B.以顺序方式存储，且结点按关键字有序排列C.以链接方式存储D.以链接方式存储，且结点按关键字有序排列参考答案:B答案解析:无

5、排序是根据（）的大小重新安排各元素的顺序。

A.关键字B.数组C.元素件D.结点参考答案:A答案解析:无

6、在一个有向图中，所有顶点的入度之和等于所有顶点的出度这和（）倍。

A.1/3B.1C.2D.4参考答案:B答案解析:无

7、若字符串”ABCDEFG”采用链式存储，假设每个指针占用2个字节，若希望存储密度为50%，则每个结点应存储（）个字符。

A.2B.3C.4D.5参考答案:A答案解析:无

8、串是和种特殊的线性表，其特殊体现在（）。

A.可能顺序存储B.数据元素是一个字符C.可以链接存储D.数据元素可以是多个字符参考答案:B答案解析:无

9、在C语言中，如果有数组定义intA[8][9]；假定每个整型数据占2字节，则数组元素A[4][4]的地址是（）。

A.A+80B.A+76C.A+82D.以上都不对参考答案:A答案解析:无

10、冲突指的是（）。

A.两个元素具有相同序号B.两个元素的键值不同C.不同键值对应相同的存储地址D.两个元素的键值相同参考答案:C答案解析:无

11、计算机算法必须具备输入、输出和（）。

A.计算方法B.排序方法C.解决问题的有限运算步骤D.程序设计方法参考答案:C答案解析:无

12、一组记录的排序码为（25，48，16，35，79，82，23，40），其中含有4个长度为2的有序表，按归并排序的方法对该序列进行一趟归并后的结果为（）。

A.07982B.22340C.22340D.34082参考答案:A答案解析:无

13、下述几种排序方法中，要求内存量最大的是（）。

A.插入排序B.选择排序C.快速排序D.归并排序参考答案:D答案解析:无

14、在C（或C++）语言中，一个顺序栈一旦被声明，其占用空间的大小（）。

A.已固定B.不固定C.可以改变D.动态变化参考答案:A答案解析:无

15、树最适合用来表示（）。

A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据参考答案:C答案解析:无

16、在查找过程中，不做增加、删除或修改的查找称为（）。

A.静态查找B.内创造C.动态查找D.处查找参考答案:A答案解析:无

17、数据在计算机存储内表示时，物理地址和逻辑地址相同并且是连续的，称之为（）。

A.存储结构B.逻辑结构C.顺序存储结构D.链式存储结构参考答案:C答案解析:无

18、直接插入排序的方法是（）的排序方法。

A.不稳定B.稳定C.外部D.选择参考答案:B答案解析:无

19、具有N个结点的完全二叉树的深度是()。

2N+2(2N)2N-1参考答案:B答案解析:无

1、在查找过程中，不做增加、删除或修改的查找称为（）。

A.静态查找B.内创造C.动态查找D.处查找参考答案:A答案解析:无

2、在C（或C++）语言中，一个顺序栈一旦被声明，其占用空间的大小（）。

A.已固定B.不固定C.可以改变D.动态变化参考答案:A答案解析:无

3、采用二分查找方法查找长度为n的线性表时，每个元素的平均查找长度为()。

A.O(n2)B.O(nlog2n)C.O(n)D.O(log2n)参考答案:D答案解析:无

4、在一个有向图中，所有顶点的入度之和等于所有顶点的出度这和（）倍。

A.1/3B.1C.2D.4参考答案:B答案解析:无

5、关键路径是指（）。

A.从开始事件到终止事件路径长度最短的路径B.从开始事件到终止事件路径长度最长的路径C.从开始事件到终止事件活动最少的路径D.从开始事件到终止事件活动最多的路径参考答案:B答案解析:无

6、评价排序算法好坏的标准主要是（）。

A.执行时间B.辅助空间C.算法本身的复杂度D.执行时间和所需的辅助空间参考答案:D答案解析:无

7、设哈希表长m=14，哈希函数H(key)=key%11。表中已有4个结点：addr(15)=4addr(38)=5

addr(61)=6addr(84)=7其余地址为空。如用二次探测再散列处理冲突，关键字为49的结点的地址是（）。

A.8B.3C.5D.9参考答案:D答案解析:无

8、一组记录的排序码为（25，48，16，35，79，82，23，40），其中含有4个长度为2的有序表，按归并排序的方法对该序列进行一趟归并后的结果为（）。

A.07982B.22340C.22340D.34082参考答案:A答案解析:无

9、直接插入排序的方法是从第（）个元素开始，插入前边适当位置的排序方法。

A.1B.2C.3D.4参考答案:B答案解析:无

10、采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为（）。

.n/2C.(n+2)/2D.(n-2)/2参考答案:C答案解析:无

11、对线性表进行二分查找时，要求线性表必须（）。

A.以顺序方式存储B.以顺序方式存储，且结点按关键字有序排列C.以链接方式存储D.以链接方式存储，且结点按关键字有序排列参考答案:B答案解析:无

12、对n个不同的排序码进行冒泡（递增）排序，在下列（）情况比较的次数最多。

A.从小到大排列好的B.从大到小排列好的C.元素无序D.元素基本有序参考答案:B答案解析:无

13、下述几种排序方法中，要求内存量最大的是（）。

A.插入排序B.选择排序C.快速排序D.归并排序参考答案:D答案解析:无

14、树的基本遍历策略可分为先根遍历和后根遍历；二叉树基本遍历策略可分为先序遍历、

中序遍历和后序遍历。这时，我们把由树转化得到的二叉树叫做这棵树对应的二叉树。结论（）是正确的。

A.树的先根遍历序列与二叉树的先序遍历序列相同B.树的后根遍历序列与二叉树的后序遍历序列相同C.树的先根遍历序列与二叉树的中序遍历序列相同D.以上都不对参考答案:A答案解析:无

15、深度优先遍历类似于二叉树的（）。

A.先序遍历B.中序遍历C.后序遍历D.层次遍历参考答案:A答案解析:无

16、冲突指的是（）。

A.两个元素具有相同序号B.两个元素的键值不同C.不同键值对应相同的存储地址D.两个元素的键值相同参考答案:C答案解析:无

17、若字符串”ABCDEFG”采用链式存储，假设每个指针占用2个字节，若希望存储密度为50%，则每个结点应存储（）个字符。

A.2B.3C.4D.5参考答案:A答案解析:无

18、排序方法中，从无序序列中选择关键字最小的记录，将其与无序区（初始为空）的第一个记录交换的排序方法，称为（）。

A.希尔排序B.归并排序C.插入排序D.选择排序参考答案:D答案解析:无

19、栈结构通常采用的两种存储结构是（）。

A.顺序存储结构和链表存储结构B.散列方式和索引方式C.链表存储结构和数组D.线性存储结构和非线性存储结构参考答案:A答案解析:无

1、采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为（）。

.n/2C.(n+2)/2D.(n-2)/2参考答案:C答案解析:无

2、以下论述正确的是()。

A.空串与空格串是相同的B.”ton”是”Teleptone”的子串C.空格串是有空格的串D.空串的长度等于1参考答案:B答案解析:无

3、设S=””，则LenStr(S)=（）。

A.0B.1C.2D.3参考答案:A答案解析:无

4、具有N个结点的完全二叉树的深度是()。

2N+2(2N)2N-1参考答案:B答案解析:无

5、一个顺序表的第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（）。

A.110B.108C.100D.120参考答案:B答案解析:无

6、以下任何两个结点之间都没有逻辑关系的是（）。

A.图形结构B.线性结构C.树形结构D.集合参考答案:D答案解析:无

7、按照二叉树的定义，具有3个结点的二叉树有（）种。

A.3B.4C.5D.6参考答案:C答案解析:无

8、关键路径是指（）。

A.从开始事件到终止事件路径长度最短的路径B.从开始事件到终止事件路径长度最长的路径C.从开始事件到终止事件活动最少的路径D.从开始事件到终止事件活动最多的路径参考答案:B答案解析:无

9、以下论述正确的是（）。

A.空串与空格串是相同的B.”tel”是”Teleptone”的子串C.空串是零个字符的串D.空串的长度等于1参考答案:C答案解析:无

10、判断一个循环队列QU(最多元素为m)为满队列的条件是（）。

->front==QU->->front!=QU->->front==(QU->rear+1)%->front!=(QU->rear+1)%m参考答案:C答案解析:无

11、算法能正确的实现预定功能的特性称为算法的（）。

A.正确性B.易读性C.健壮性D.高效性参考答案:A答案解析:无

12、设二叉树的树根为第一层，则第i层上至多有（)结点。

A.1B.2C.2i-1D.2i+1参考答案:C答案解析:无

13、对线性表进行二分查找时，要求线性表必须（）。

A.以顺序方式存储B.以顺序方式存储，且结点按关键字有序排列C.以链接方式存储D.以链接方式存储，且结点按关键字有序排列参考答案:B答案解析:无

14、直接插入排序的方法是（）的排序方法。

A.不稳定B.稳定C.外部D.选择参考答案:B答案解析:无

15、对有14个元素的有序A[1‥14]作二分查找，查找元素A[4]时的被比较元素依次为（）

A.A[1]，A[2]，A[3]，A[4]B.A[1]，A[14]，A[7]，A[4]C.A[7]，A[3]，A[5]，A[4]D.A[7]，A[5]，A[3]，A[4]参考答案:C答案解析:无

16、排序方法中，从无序序列中选择关键字最小的记录，将其与无序区（初始为空）的第一个记录交换的排序方法，称为（）。

A.希尔排序B.归并排序C.插入排序D.选择排序参考答案:D答案解析:无

17、任何一个无向连通图的最小生成树（）。

A.只有一棵B.一棵或多棵C.一定有多棵D.可以不存在参考答案:A答案解析:无

18、下列算法的时间复杂度是（）。for(i=0;i

A.O（1）B.O（n）C.(log2n)D.O(n2)参考答案:D答案解析:无

19、一组记录的排序码为（25，48，16，35，79，82，23，40），其中含有4个长度为2的有序表，按归并排序的方法对该序列进行一趟归并后的结果为（）。

A.07982B.22340C.22340D.34082参考答案:A答案解析:无

二、判断题答题要求:判断以下命题正确与否，正确的请选“正确”，错误的请选“错误”。

1、在单向循环链表中，若头指针为h，那么p所指结点为尾结点的条件是p=h。

参考答案:错误答案解析:无

2、数据的逻辑结构与数据元素本身的内容和形式无关。

参考答案:正确答案解析:无

3、二叉树的三叉链表存储结构可以方便的访问到双亲结点。

参考答案:正确答案解析:无

4、在链串中为了提高存储密度，应该增大结点的大小。

参考答案:正确答案解析:无

5、串是n个字母的有限序列。

参考答案:错误答案解析:无

6、数据的逻辑结构和数据的存储结构是相同的。

参考答案:错误答案解析:无

7、数据元素是数据的最小单位。

参考答案:错误答案解析:无

8、队列是限制在两端进行操作的线性表。

参考答案:正确答案解析:无

9、二叉树的左右子树次序是严格的，不能够任意改变。

参考答案:正确答案解析:无

1、广义表在本质上也是线性表。

参考答案:错误答案解析:无

2、二叉树的左右子树次序是严格的，不能够任意改变。

参考答案:正确答案解析:无

3、数据的逻辑结构和数据的存储结构是相同的。

参考答案:错误答案解析:无

4、队列是限制在两端进行操作的线性表。

参考答案:正确答案解析:无

5、已知广义表A=((a,b,c),(d,e,f)),从A中取出原子e的运算是head(tail(head(tail(A))))。

参考答案:正确答案解析:无

6、若根为第一层，则深度为k的满二叉树的结点为2^k-1

参考答案:正确答案解析:无

7、在链串中为了提高存储密度，应该增大结点的大小。

参考答案:正确答案解析:无

8、二叉树的三叉链表存储结构可以方便的访问到双亲结点。

参考答案:正确答案解析:无

9、采用希尔排序时，若原始关键字的排列杂乱无序，则效率最高。

参考答案:正确答案解析:无

1、二叉树的左右子树次序是严格的，不能够任意改变。

参考答案:正确答案解析:无

2、子串的定位运算称为模式匹配。

参考答案:正确答案解析:无

3、判断顺序队列为空的标准是头指针和尾指针都指向同一个结点。

参考答案:正确答案解析:无

4、在单向循环链表中，若头指针为h，那么p所指结点为尾结点的条件是p=h。

参考答案:错误答案解析:无

5、采用希尔排序时，若原始关键字的排列杂乱无序，则效率最高。

参考答案:正确答案解析:无

6、对快速排序来说，初始序列为正序或反序都是最坏情况。

参考答案:正确答案解析:无

7、如果两个串含有相同的字符，则说明它们相等。

参考答案:错误答案解析:无

8、广义表在本质上也是线性表。

参考答案:错误答案解析:无

9、串是n个字母的有限序列。

参考答案:错误答案解析:无

三、问答题答题要求:请简要回答以下问题。

1、对于线性表的两种存储结构，如果有n个线性表同时并存，而且在处理过程中各表的长度会动态发生变化，线性表的总数也会自动改变，在此情况下，应选用哪一种存储结构？为什么？

参考答案:应选用链接存储结构，因为链式存储结构是用一组任意的存储单元依次存储线性表中的各元素，这里存储单元可以是连续的，也可以是不连续的：这种存储结构对于元素的删除或插入运算是不需要移动元素的，只需修改指针即可，所以很容易实现表的容量的扩充。答案解析:略

2、在什么情况下用顺序表比链表好？

参考答案:当线性表的数据元素在物理位置上是连续存储的时候，用顺序表比用链表好，其特点是可以进行随机存取。答案解析:略

2、线性表的两种存储结构各有哪些优缺点？

参考答案:线性表具有两种存储结构即顺序存储结构和链接存储结构。线性表的顺序存储结构可以直接存取数据元素，方便灵活、效率高，但插入、删除操作时将会引起元素的大量移动，因而降低效率：而在链接存储结构中内存采用动态分配，利用率高，但需增设指示结点之间关系的指针域，存取数据元素不如顺序存储方便，但结点的插入、删除操作较简单。答案解析:略

3、试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。

参考答案:抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。答案解析:略

1、描述以下三个概念的区别：头指针，头结点，首元结点（第一个元素结点）。

参考答案:头指针是指向链表中第一个结点的指针。首元结点是指链表中存储第一个数据元素的结点。头结点是在首元结点之前附设的一个结点，该结点不存储数据元素，其指针域指向首元结点，其作用主要是为了方便对链表的操作。它可以对空表、非空表以及首元结点的操作进行统一处理。答案解析:略

四、算法设计答题要求:按要求解答下列小题。

1、

参考答案:

答案解析:略

2、设单链表中有仅三类字符的数据元素(大写字母、数字和其它字符)，要求利用原单链表中结点空间设计出三个单链表的算法，使每个单链表只包含同类字符。

参考答案:

答案解析:略

1、

参考答案:

答案解析:略

1、在链式存储结构上建立一棵二叉排序树。

参考答案:

答案解析:略

五、应用题答题要求:根据题目要求解答问题。

1、设一组初始记录关键字序列为(19，21，16，5，18，23)，要求给出以19为基准的一趟快速排序结果以及第2趟直接选择排序后的结果。

1、请回答：

参考答案:(18,5,16,19,21,23)，(5，16，21，19，18，23)

答案解析:略

1、设一组初始记录关键字集合为(25，10，8，27，32，68)，散列表的长度为8，散列函数H(k)=kmod7，要求分别用线性探测和链地址法作为解决冲突的方法设计哈希表。

1、请回答：

参考答案:

1、设有无向图G（如图所示），要求给出用普里姆算法构

造最小生成树所走过的边的集合。

1、请回答：

参考答案:E={(1，3)，(1，2)，(3，5)，(5，6)，(6，4)}

答案解析:略