数据结构样卷

第 1 页 共 3 页

一、 选择题

（1）下列程序段的时间复杂度 ；

for(i=0;i

A ?（n*n） B ?（m*m） C ?（i*j）D ?（n*m）

（2）以下有关数据结构的叙述中 是正确的。 A 冒泡排序是一种特殊的插入排序；

B 数据的逻辑结构不是按其在计算机中的存储表示方法来区分的； C 顺序存储的线性表称为链表；

D 每个结点的度数小于等于2的树是二叉树。

（3）链表相对于顺序表的优点是 A 存储密度大，存储空间利用率高。

B 逻辑相邻的结点在存储物理位置上下是相邻的。

C 可以通过计算直接确定结构中第 i 个结点的存储地址。 D 插入、删除操作方便。

（4）设某数列的顺序为14,25,36,47,58,69 , 通过单个栈结构，每个数进栈一

次可以排成顺序为 的数列。

A 14 58 47 69 25 36 B 25 47 69 58 14 36

C 36 25 58 69 47 14 D 47 36 69 58 14 25

（5）对用邻接表表示图进行广度优先遍历时，通常采用的数据结构

是 。

A 栈 B 队列 C 树 D 图

（6）某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问 顺序是dgbaechf，则其后序遍历的结点访问顺序是 。

A bdgcefha B gdbecfha C bdgaechf D gdbehfca

（7）顺序查找适用于存储结构为 的线性表 。

A 散列存储 B 压缩存储 C 顺序存储或链接存储 D 索引存储

第 2 页 共 3 页

(8) 在散列储存中，装填应子α的值越大存取元素时发生冲突的可能性就（1）

当α的值越小存取元素时发生冲突的可能性就（2） 。

A （1）越大（2）越大 B （1）越小（2）越小

C （1）越小（2）越大 D（1）越大（2）越小

（9）快速排序方法在 情况下最不利于发挥其长处。

A．要排序的数据量太大；

B．要排序的数据中含有多个相同值； C．要排序的数据已基本有序； D．要排序的数据个数为奇数。

（10）线性表最常用的查找方法有三种。其中，一种适用于很少进行查找，但

内容又经常需要变化的线性表；另一种适用于经常进行查找，但内容又很少变化的线性表；第三种适用于既希望较快查找而内容又需动态变化的线性表。它们依次分别为 。 A．分块查找、折半查找和顺序查找 B．折半查找、顺序查找和分块查找 C．顺序查找、分块查找和折半查找 D．顺序查找、折半查找和分块查找

二、简要回答下列问题：

1）试画出下列数据结构的图示并列出空表（栈）的条件 （1）单链表；（2）双向循环链表；（3）链栈。

2）顺序存储结构的循环队列q，其空队列和满队列的条件分别是什么？

3）在直接插入排序、快速排序、合并排序、基数排序中哪些排序方法是不稳定的，并举例说明。

4）以数据集{7，19，2，6，32，3，21，10}为权值构造一棵哈夫曼树，并计算其带权路径长度。

5）无向图G1和有向图G2的顶点数均为n则G2至多有几条弧，G1最少有几条边。

第 3 页 共 3 页

三、综合题

1）一棵二叉树的顺存储结构为： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 F G H I J ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ （1）画出该棵二叉树； （2）求该棵二叉树的前序序列；

（3）画出该棵二叉树的后序全线索（线索用虚线，指针用实线）； （4）将该棵二叉树还原为森林。

2）对于下图所示的无向图，给出： （1）表示该图的邻接矩阵。 （2）表示该图的邻接多重表。

（3）从顶点V1发，按深度优先搜索法遍历图时所得到的顶点序列。 （4）从顶点V1发，按广度优先搜索法遍历图时所得到的顶点序列。

v1v2v3v4v5v6A B C D E 3）MOD 9用开放定址法处理冲突，di =1,2,3,4，选取哈希函数H（K）＝（K）

5,6，7, 8，9,10，?,试在0?10的散列地址空间中对关键字序列（22，41，53，46，08，30，80，13，71）造哈希表，并求等概率情况下查找成功的平均查找长度。

4）设记录的关键字集合key={50,29,36,86,77,90,02,31,43,26}试写出对key进行“希尔排序”、“快速排序”和“堆排序”时，各趟排序结束后的结果。

5）编程题，以线性结构为主。

百度搜索“70edu”或“70教育网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，70教育网，提供经典综合文库数据结构样卷在线全文阅读。