数据结构与算法模拟练习题含答案.docx

数据结构与算法模拟练习题含答案

一、单选题（共86题，每题1分，共86分）

1.数据元素在计算机存储器内表示时，物理相对位置和逻辑相对位置相同并且是连续的，称之为（）。

A、逻辑结构

B、顺序存储结构

C、链式存储结构

D、以上都不对

正确答案：B

2.对于给定的有权无向图G，下列哪个说法是正确的？

A、G的最小生成树中，任意一对顶点间的路径必是它们在G中的最短路径

B、设顶点V到W的最短路径为P。若我们将G中每条边的权重都加1，则P一定仍然是V到W的最短路径

C、单源最短路问题可以用O(∣E∣+∣V∣)的时间解决

D、以上都不对

正确答案：D

3.被计算机加工的数据元素不是孤立的，它们彼此之间一般存在某种关系，通常把数据元素之间的这种关系称为

A、结构

B、运算

C、集合

D、规则

正确答案：A

4.若栈S1中保存整数，栈S2中保存运算符，函数F()依次执行下述各步操作：（1）从S1中依次弹出两个操作数a和b；（2）从S2中弹出一个运算符op；（3）执行相应的运算bopa；（4）将运算结果压入S1中。假定S1中的操作数依次是{5,8,3,2}（2在栈顶），S2中的运算符依次是{*,-,+}（+在栈顶）。调用3次F()后，S1栈顶保存的值是：

A、-15

B、15

C、-20

D、20

正确答案：B

5.关于存储结构▁▁▁▁▁的特点是借助指示元素存储地址的指针来表示数据元素之间的逻辑关系。

A、链式存储结构

B、索引存储结构

C、顺序存储结构

D、散列存储结构

正确答案：A

6.算法分析的目的是()

A、找出数据结构的合理性

B、研究算法中的输入和输出的关系

C、分析算法的易读性和文档性

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

正确答案：D

7.若一个栈的入栈序列为1、2、3、…、N，输出序列的第一个元素是i，则第j个输出元素是：

A、j?i?1

B、i?j

C、不确定

D、i?j?1

正确答案：C

8.给定初始待排序列{15，9，7，8，20，-1，4}。如果希尔排序第一趟结束后得到序列为{15，-1，4，8，20，9，7}，则该趟增量为：

A、3

B、2

C、4

D、1

正确答案：C

9.某二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树一定是（）

A、空或只有一个节点

B、完全二叉树

C、二叉排序树

D、高度等于其节点数

正确答案：D

10.二叉树的高度若根节点为高度1，一棵具有1025个结点的二叉树的高度为▁▁▁▁▁。

A、11～1025之间

B、10

C、11

D、10～1024之间

正确答案：A

11.在AOE网中，什么是关键路径？

A、最短回路

B、最长回路

C、从第一个事件到最后一个事件的最短路径

D、从第一个事件到最后一个事件的最长路径

正确答案：D

12.一棵有1001个结点的完全二叉树，其叶子结点数为▁▁▁▁▁。

A、250

B、500

C、254

D、501

正确答案：D

13.在将数据序列（6,1,5,9,8,4,7）建成大根堆时，正确的序列变化过程是：

A、6,1,7,9,8,4,5→6,9,7,1,8,4,5→9,6,7,1,8,4,5→9,8,7,1,6,4,5

B、6,9,5,1,8,4,7→6,9,7,1,8,4,5→9,6,7,1,8,4,5→9,8,7,1,6,4,5

C、6,9,5,1,8,4,7→9,6,5,1,8,4,7→9,6,7,1,8,4,5→9,8,7,1,6,4,5

D、6,1,7,9,8,4,5→7,1,6,9,8,4,5→7,9,6,1,8,4,5→9,7,6,1,8,4,5→9,8,6,1,7,4,5

正确答案：A

14.设散列表的地址区间为[0,16]，散列函数为H(Key)=Key%17。采用线性探测法处理冲突，并将关键字序列{26，25，72，38，8，18，59}依次存储到散列表中。元素59存放在散列表中的地址是：

A、11

B、10

C、8

D、9

正确答案：A

15.在下列查找的方法中，平均查找长度与结点个数无关的查找方法是：

A、二分法

B、利用二叉有哪些信誉好的足球投注网站树

C、顺序查找

D、利用哈希（散列）表

正确答案：D

16.已知不相交集合用数组表示为{4,6,5,2,-3,-4,3}。若集合元素从1到7编号，则调用Union(Find(7),Find(1))（按规模求并，并且带路径压缩）后的结果数组为：

A、{4,6,5,2,-7,5,3}

B、{4,6,5,2,6,-7,3}

C、{6,6,5,6,6,-7,5}

D、{6,6,5,6,-7,5,5}

正确答案