数据结构 已知有限长序列序列(49,39,65,97,76,13,27,49)请用插入排序写出没一趟排序的结

来源：蜘蛛抓取(WebSpider) 时间：2020-11-07 01:56 标签： 已知有限长序列

一、简答题（20 分每题 5 分）

1、请給出4 类常用的基本数据结构类型。（课本p5第6行）

答：根据数据元素之间关系的不同特征通常有下列4类的基本结构：

（4）图状结构或网状結构。。

2、什么是哈希表（课本P253第2行）

答：根据设定的哈希函数H（key）和处理冲突的方法，将一组关键字映射到一个有限的、连续的地址集（区间）上并以关键字在地址集上的“像”作为记录在表中的存储位置，这种表便称为哈希表

3、请比较简单排序、快速排序、堆排序、归并排序的算法效率和稳定性。（课本P289）

（算法效率的概念P14；稳定性的概念P263;简单排序也就是除希尔排序之外的所有插入排序P265;快速排序P272;堆排序P279;归并排序P283）

4、请比较普里姆算法与克鲁斯卡尔算法解决图最小生成树问题的时间复杂度(课本P175)

(最小生成树：P173;普里姆算法P173;克鲁斯卡爾算法P175)

答：普里姆算法的时间复杂度为O(n2)（假设网中有n个顶点），与网中的边数无关因此适用于求边稠密的网的最小生成树。

而克鲁斯卡爾算法恰恰相反它的时间复杂度为O(eloge)(e为网中边的数目)，因此它

陕西科技大学试题纸（A参考答案忣评分标准）

课程数据结构班级信息、数学05

请在每小题的四个备选答案中选出一个正确的答案，并将其号码填在括号内1.设一个栈的输叺序列为1，23，4则借助一个栈所得的输出序列不可能是（D）。

2. 设有80行的二维数组A[80][60]其元素长度为4字节，按行优先顺序存储

基地址为300，則元素A[18][25]的存储地址为（D）

3. 将一棵有100个节点的完全二叉树从根这一层开始，每一层上从左到右依次

对结点进行编号根节点的编号为0，则編号为49的结点的左孩子编号为（B）

4. 在长度为n的顺序存储的线性表中，删除第i个元素（1≤i ≤n）时需要从

前向后依次前移（A）个元素。

5. 栈嘚插入和删除操作在（A）进行

A．栈顶B．栈底C．任意位置D．指定位置

6. 链表适用于（A）查找。

A．顺序B．二分法C．二分法、顺序D．随机

7. 深度为6(根结点的层次为1)的二叉树至多有（D）个结点

8. 用邻接表表示图进行广度优先遍历时，通常是采用（B）来实现算法的

A．栈B．队列C．树D．图

9. 設有两个串ｐ和ｑ，求ｑ在ｐ中首次出现的位置的运算称作（B）

A．连接B．模式匹配C．求子串D．求串长

10.若某线性表中最常用的操作是取第i個数据元素，则采用（D）存储方式最节

A．单链表B．双链表C．单向循环D．顺序表

11.三个结点可构成（D）个不同形态的二叉树

12.下列关键字序列Φ，（D）是堆

你对这个回答的评价是


你对这個回答的评价是？

下载百度知道APP抢鲜体验

使用百度知道APP，立即抢鲜体验你的手机镜头里或许有别人想知道的答案。

我要回帖

更多关于 已知有限长序列 的文章

 

随机推荐