数据结构考试模拟卷

考 试 试 卷

题号 得分 一 二 三 四 五 六 七 八 九 十 总分 一、 请判断下列说法的是否正确：(10分)

（1）若某堆栈的输入序列为1,2,3,4，则4,3,1,2不可能是堆栈的输出序列之一。( T ) （2）队列逻辑上是一个表头和表尾既能插入又能删除的线性表。（ F ）

（3）若一个叶子结点是某子树的中序遍历序列的最后一个结点，则它必是该子树的先序遍历中的最后一个结点。（ T ）

（4）在索引顺序表上实现分块查找，在等概率查找情况下，其查找长度只与表中元素个数有关，而与每块中元素个数无关。（ F ）

（5）二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值，小于其右孩子的值。（ F ）

（6）在10万个随机排列的数据中，要选出5个最小的数，采用快速排序比采用Shell排序、堆排序及各种直接排序法都快。（ F ）

（7）用邻接矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小与图中的结点的个数有关，而与图的边数无关。（ T ）。-

（8）在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和。 （ T ） （9）二分查找法不仅适用于顺序存储的有序表，而且适合于链接表。（ F ） （10）按中序遍历一棵二叉排序树所得到的遍历序列是一个递增序列。（ T ）

二、填空（20分）

(1)数据结构有如下四种基本结构：

集合 、 线性结构 、 图结构 、 树结构 。

1、 （2）在一个算法中的语句频度之和为T（n）=3720n+4nlogn，则算法的时间复杂度为 O（nlogn）

。

（3） 已知某二叉树的叶子结点的个数为10个，度为1的结点个数为8个，则该二叉树的结

1

考 试 试 卷

点总数为： 27 个。

(4) 已知一个有序表为（13，18，24，35，47，50，62，83，90，115，134），当二分检索值为90 的元素时，需__ 2___次比较可检索成功。

(5)、图的遍历方法主要有两个，一个是 深度优先 ，另一个是 广度优先 。

(6) 在哈希造表过程中，处理冲突的方法主要有： 1、开放地址法 2、再哈希法 3、

链地址法 4、建立一个公共的溢出区

（7）在一个单链表中p所指结点(p所指不是最后结点)之后插入一个由指针s所指结点，应执行s->next=p->next;和p->next=s的操作。

（8）.已知一棵二叉树的先序序列为ABCD，中序序列为BCAD，则它的后序序列为___CBDA__ _。

2、 （9）有N个顶点组成的无向连通图，最多可以1/2N*（N-1）条边。

3、 （10）、若某序列的初始状态为{49，13，42，8，65，55，79}，若以49为枢轴，则经

过一趟快速排序之后的序列为：8 13 42 49 65 55 79。

三、单项选择题(每小题2分，共20分)

1． 从一个长度为n的顺序表中删除第i个元素（1≦i≦n）时，需向前移动（ A ）个

元素。

A）. n-i B）. n-i+1 C）. n-i-1 D）. i 2）、队列操作的原则是：（ A ）

A)先进先出 B)后进先出 C)只能进行插入 D)只能进行删除 3）下列算法中，( B )算法用来求图中每对顶点之间的最短路径。 A）．Dijkstra B）．Floyed C）．Prim D）．Kruskal 4、下面关于线性表的叙述中，错误的是 （ B ） A）线性表采用顺序存储，必顺占用一片连续的存储单元。 B）线性表采用顺序存储，便于进行插入和删除操作。

2

考 试 试 卷

C）线性表采用链接存储，不必占用一片连续的存储单元 D）线性表采用链接存储，便于插入和删除操作。

5、对下面的有向图进行拓扑排序，其排序结果不正确的是：（ C ）。

5 4 6 1 2 3

A） 1、4、2、6、5、3 B ）1、2、4、6、3、5 C） 1、4、2、5、6、3 6、带头结点的单链表head为空的判定条件是：（ B ）

A）．head= =NULL B.） head->next= =NULL C）、.head->next= =head D）.head!=NULL

7、在所有排序方法中，关键字的比较次数与记录的初始排列无关的是____D____。 A） Shell排序 B） 冒泡排序 C.） 直接插入排序 D） 直接选择排序 8、设有两个串p和q，求q在p中首次出现的位置的运算叫_______A___。 A）. 模式匹配 B）. 求子串 C.） 定位 D）. 查找 9、将长度为n的单链表链接到长度为m的单链表之后的算法的时间复杂度为（ A ）

A.） O(m) B.） O(1) C.） O(n) D ）. O(m+n)

10、用线性探测法查找散列表，可能要探测多个散列地址，这些位置上的关键值（ D ） A.） 一定都是同义词 B）. 一定都不是同义词 C）. 都相同 D）不一定都是同义词

四、解答题 （3０分）

１、对于给定的一组权值Ｗ＝｛３，６，９，１１，１３，１５，１７，１９｝｝画出Huffman树（要求结点左小右大），并给出每个结点的Huffman编码，计算该树的WPL。（6分）

3

考 试 试 卷

19：00 9：010 3：0110 15：110

17：111；

6：0111

11：100

13：101

WPL=（19*2+9*3+3*4+6*4+11*3+13*3+15*3+17*3）=269

2、考虑下图：（１0分）

１） 从顶点Ａ出发，求它的深度优先生成树。 ２） 从顶点Ｅ出发，求它的广度优先生成树。

３） 根据普里姆（Ｐrim）算法，求它的最小生成树。（从顶点A出发，要

求给出计算过程）

4

考 试 试 卷

1）（有多种答案）

2）（有多种答案）

3）（计算过程略）

5

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构考试模拟卷在线全文阅读。