找北京邮政数据结构期末考试题

1.简述顺序存储结构和链式存储结构的特点。

答:顺序存储结构的优点是不需要额外增加指针空间来表达元素之间的逻辑关系；您可以随机访问表中的任何元素。缺点是必须提前分配空间，表的容量很难扩展；插入和删除操作需要移动很多节点，效率很低。

链式存储结构的优点是节点的存储采用动态存储，表的容量易于扩展；插入和删除都很方便，不需要移动节点，只需要修改节点中的指针即可。缺点是每个节点需要指针空间，小于顺序存储结构的存储密度；只能按顺序找到节点。

2.为什么要在链表中引入头节点？

答:在插入和删除链表时，需要判断是否在链表头操作。如果在第一个节点之前插入一个新节点，并且删除第一个节点，那么第一个指针的头值将会改变。否则，head的值不会改变。在链表前增加一个头节点(只用指针字段指向链表的头节点)，避免了两种情况的判断，使得程序设计简单，程序的结构更加清晰。

2.简述如何通过二叉树的前序、中序、后序的遍历顺序来确定二叉树。

答:三种遍历序列中，前序序列和中间序列，中间序列和后序序列可以唯一确定一棵二叉树，因为前序序列或后序序列可以确定二叉树的根节点，中间序列可以确定根的左右子树。前序序列和后序序列不能唯一确定一棵二叉树，但是注意树的前序序列和后序序列可以唯一确定树，因为树的后序序列是二叉树的中序序列。

4.快速排序最坏情况的改进

答:当要排序的序列是有序序列时，快速排序的效率很低，变成了冒泡排序。为了避免这种情况，选择序列的第一个元素作为枢纽元素(或引用元素)，选择序列的第一个元素、中间元素和最后一个元素的中间元素作为引用元素(简单地使用中间元素作为引用)，这样可以大大提高快速排序的性能。例如:

8,0,4,9,6,3,5,2,7,1

以中间的大元素6为基准，基准元素与最后一个元素交换如下:

8,0,4,9,1,3,5,2,7,6

↑ ↑

国际j

比较I和J的内容，如果I的内容小于基准，则我前进，否则我停止并开始J的比较:如果J的内容大于基准，则J前进，否则J停止，将I的内容与J的内容交换，重复上述过程，直到J < I & ltSPAN & gt检查，交换基准和我的内容，一次分段完成。，如下所示:

8,0,4,9,1,3,5,2,7,6

2,0,4,9,1,3,5,8,7,6

2,0,4,5,1,3,9,8,7,6

2,0,4,5,1,3,6,8,7,9

5.简述动态规划法的基本思想。

答:为了节省重复寻找同一个子问题的时间，引入了一个表(数组)，不管它们对最终解是否有用，新的子问题的解都存储在表中。以后遇到同样的子问题，不会重复找子问题，而是直接从表中取子问题的解。这是动态规划方法采用的基本思想。

(4)选择题

1.循环队列使用数组A[0…m-1]来存储其元素值。假设它的头指针和尾指针分别是前指针和后指针，则当前队列中的元素数是。

A.(后-前+m)% m B.read-front+1

c .阅读正面-1 D .阅读正面

参考答案a

2.一般来说，递归算法的执行过程可以分为两个阶段:(1)和(2)。

(1) A .尝试b .递归c .枚举d .分析

(2) A .逆行b .回归c .回归d .综合

n参考答案(1) B (2) B

3.设哈希表长度m=11，哈希函数H(key)=key%11。表中有四个节点:addr(15)=4，addr(38)=5，addr(61)=6，addr(84)=7，其余地址为空。如果第二次探测和散列处理冲突，则键为49的节点的地址是。

A.8 B.3 C.5 D.9

参考答案d

4.M阶B树中所有非末端(根除外)节点的关键字数必须大于或等于。

A.-1 b .+1 c .-1d . m

参考答案c

5.如果一组记录的键码为(46，79，56，38，40，84)，则基于第一条记录的第一个除法结果为。

38，40，46，56，79，84

40，38，46，56，79，84

参考答案c

6.如果一个问题可以通过递归和递归算法来解决，那么经常使用(1)算法，因为(2)。

(1) A .先递归，后递归b .先递归，后递归c .递归d。

(2) A .递归比递归效率高b .递归适用于问题分解。

C.递归比递归更有效。d .递归适用于问题分解。

n参考答案(1)D (2)A

7.从上到下从左到右给一个有100个节点的完整二叉树的节点编号。根节点的编号是1，编号为49的节点的左子节点的编号是。

A.公元前99年

参考答案b

8.二叉树被提示后无法有效解决的问题是。

A.在先行线索二叉树中寻找先行后继b .在中间线索二叉树中寻找中间后继。

C.在中序线索二叉树中找到中序，d .在逆序线索二叉树中找到逆序。

参考答案d

9.判断线索二叉树中一个节点P有左子的条件是(1)。如果从forest转换的二叉树不为空，则二叉树的形状为(2)。

(1)A.P！= null B . P-& gt；孩子。=null C.P->ltag=0 D.P->ltag=1

(2) A .有根节点没有右子树的二叉树b .有根节点没有左子树的二叉树

C.根节点可以具有左子树和右子树。每个节点只有一个孩子的二叉树。

n参考答案(1)C (2)C

10.在单链表头中，如果想在指针P指向的节点后插入一个指针Q指向的节点，执行_ _ _ _。

A.p->；next = q-& gt；接下来；q->；next = p；

B.q->；next = p-& gt；接下来；p = q；

C.p->；next = q-& gt；接下来；p->；next = q；

D.q->；next = p-& gt；接下来；p->；next = q；

参考答案d

11.设二维数组a[0…m-1][0…n-1]按列优先级顺序存放在首地址为loc(a[0][0])的存储区，每个元素占用d个单位，则A [I] [

A.loc(a[0][0])+(j×n+I)×d b . loc(a[0][0])+(j×m+I)×d

c . loc(a[0][0])+((j-1)×n+I-1)×d . loc(a[0][0])+((j-1)×m+I-1)×d

参考答案b

12.如果一个栈的栈入口序列是1，2，3，4，要求每个元素进出栈一次，那么不可能得到栈出口序列_ _ _ _。

A 4，3，2，1 B 4，2，1，3 C 1，3，2，4 D 3，4，2，1

参考答案b

13.快速排序n个元素时，最坏的时间复杂度是。

A.O(log2n)B . O(n)C . O(nlog2n)D . O(N2)

参考答案d

14.任何基于“比较”的内部排序算法，如果排序6个元素，最坏情况下所需的比较次数至少是。

a . 10 b . 11 C . 21d . 36

参考答案a

四、模拟试题

1.二叉树的前序、中序、后序遍历方法最适合用(1)来实现。

在搜索树中，从根节点到所有其他节点的路径长度之和称为(2)，最小化路径长度之和的树称为(3)。肯定是④。

在关于树的几种说法中，只有(5)是正确的。

(1) A .递归程序b .迭代程序c .队列操作d .堆栈操作

(2) A .路径和b .内部路径长度c .总深度d .深度和

(3) a.b .树b . b+树c .丰满树d .穿线树

(4)a . b .-树b .平衡树c .不平衡树d .穿线树

(5) A .一棵有n个节点的二叉树，以指针的方式存储，至少有n+1个指针。

在B-m阶的B树中，每个非叶节点的后件数≥

在C. M阶的B树中，有k个续的节点必须包含k-1个键值。

D.一棵平衡的树必须是丰满的。

n参考答案(1) A (2) B (3) C (4) B (5) C。

2.一棵搜索二叉树，其节点A、B、C、D、E、F顺序存储在一个连续的区域中，起始地址为n(假设地址按字节顺序编号)，每个节点占用4个字节:前两个字节存储节点值，后两个字节用左指针和右指针顺序放置。如果搜索二叉树的根节点是E，那么一个可能的前序遍历是(1)，对应的层次遍历是(2)。在上面两种遍历情况下，节点C的左指针Lc的存储地址是(3)，Lc的内容是(4)。节点A的右指针Ra的内容是(5)。

(1)A . EAFCBD B . EFA CDB C . eab CFD D . EAC BDF

(2)A . EAF CBD B . EFA CDB C . eab CFD D . EAC BDF

(3)a . n+9 b . n+10 c . n+12d . n+13

(4)a . n+4 b . n+8 c . n+12d . n+16

(5)a . n+4 b . n+8 c . n+12d . n+16

n参考答案(1)D(2)A(3)B(4)A(5)B A(3)B(4)A(5)B。

3.对于给定的一组关键字(12，2，16，30，8，28，4，10，20，6，18)，每个算法第一次排序后得到的结果按照以下算法书写:Hill排序。快速排序(选择第一条记录作为基准元素)得到(2)，radix (radix 10)得到(3)，双向归并排序得到(4)，堆排序得到(5)。

(1)A.2，4，6，8，10，12，16，18，20，28，30

C.12，210，20，618，416，30，8，28

(2)A.10，6，18，8，4，2，12，20，16，30，28 B.6，2，10，4，8，12，28，30，20，16，18

C.2，4，6，8，10，12，16，18，20，28，30

(3)A.10，6，18，8，4，2，12，20，16，30，28 b . 12，10，20，6，18，4，16，30，8，28

C.2，4，6，8，10，12，16，18，20，28，30

(4)A.2，12，16，8，28，30，4，6，10，18，20

C.12，216，8，28，30，4，6，10，28，18

(5)A.30，28，20，12，18，16，4，10，2，6，8 B.20，30，28，12，18，4，16，10，2，8，6

20，8，30，18

n参考答案(1) C (2) B (3) D (4) B (5) C。

4.在所有排序方式中，关键字比较的次数与记录的初始排序顺序(1)无关。

将无序序列中的元素按顺序取出，与有序序列中的元素(开头为空)进行比较，放入有序序列的正确位置的方法称为(2)。有1000个无序元素，希望能以最快的速度选出前10个最大元素，最好选择(3)排序法。

(1) A .希尔排序b .冒泡排序c .插入排序d .选择排序

(2) A .希尔排序b .冒泡排序c .插入排序d .选择排序

(3) A .冒泡排序b .快速排序c .堆排序d .基数排序

n参考答案(1)D (2)C (3)C

5.线性表(25，84，21，47，15，27，68，35，20)按一定的排序方法排序时，元素顺序的变化如下:

①25,84,21,47,15,27,68,35,20 ②20,15,21,25,47,27,68,35,84

③15,20,21,25,35,27,47,68,84 ④15,20,21,25,27,35,47,68,84

采用的排序方法是(1)。下面(2)中的不稳定排名是(2)。

外部排序参考(3)。

(1) A .选择排序b .希尔排序c .归并排序d .快速排序

(2) A .直接插入排序b .冒泡排序c .外壳排序d .归并排序

(3) A .用机器指令直接对硬盘中待排序数据进行排序。

b、将待分拣的数据通过其他大容量机器进行分拣。

c .将外部存储器中待排序数据一次性转移到内部存储器中，排序后存储在外部存储器中。

d、外存中待排序的数据大于内存的允许空间，通过多次内外交换实现排序。

n参考答案(1) D (2) C (3)D

6.在内部排序中，通常需要对排序后的数据进行多次扫描。各种排序方法有不同的排序实现过程和时间复杂度。给定整数序列(541，132，984，746，518，181，946，314，205，827)从小到大排序时，

设排序后的序列有n个元素，冒泡排序和简单选择排序的时间复杂度为(3)；快速排序的时间复杂度为(4)。

(1)

A.(181，132，314，205，541，518，946，827，746，984)和(5465438)

B.(132，541，746，518，181，946，314，205，827，984)和(5465438)

C.(205，132，314，181，518，746，946，984，541，827)和(65438+)

D (541，132，984，746，827，181，946，314，205，518)和(65438+)

(2)A.(181，132，314，205，541，518，946，827，746，984)

B.(541,132,827,746,518,181,946,314,205,984)

C.(205,132,314,181,518,746,946,984,541,827)

D.(541,132,984,746,827,181,946,314,205,518)

(3)A . O(nlog2n)B . O(n)c . log2n D . O(N2)

(4)A . O(nlog2n)B . O(N2 log2n)C . O(log2n)D . O(N2)

n参考答案(1)B (2)C (3)D (4)A

7.确定节点的关键字顺序(F，B，J，G，E，A，I，D，C，H)，按照字母的字典顺序排列，采用不同的方法，最后的结果是一样的。但是中间结果不一样。

壳排序(步长为5)第一次扫描的结果应该是(1)。

冒泡排序(大数下沉)中第一个冒泡的作用是(2)。

快速排序的第一个扫描结果是(3)

双向合并排序的第一个结尾是(4)。

如果用层次序列建立对应的完全二叉树，用筛选法建立堆，则第一个堆为(5)。

(1)A.(B，F，G，J，A，D，I，E，H，C)

B.(B、F、G、J、A、E、D、I、C、H)

C.(A、B、D、C、E、F、I、J、G、H)

D.(C、B、D、A、E、F、I、G、J、H)

(2)A.(A、B、D、C、F、E、I、J、H、G)

B.(A、B、D、C、E、F、I、H、G、J)

C.(B、F、G、E、A、I、D、C、H、J)

D.(B、F、G、J、A、E、D、I、C、H)

(3)A.(C、B、D、A、F、E、I、J、G、H)

B.(C、B、D、A、E、F、I、G、J、H)

C.(B、A、D、E、F、G、I、J、H、C)

D.(B、C、D、A、E、F、I、J、G、H)

(4)A.(B、F、G、J、A、E、D、I、C、H)

B.(B、A、D、E、F、G、I、J、H、C)

C.(A、B、D、C、E、F、I、J、G、H)

D.(A、B、D、C、F、E、J、I、H、G)

(5)

n参考答案(1) C (2) C (3) B (4) A (5) B。

8.二叉树(1)。在完全二叉树中，如果一个节点没有(2)，那么它一定是一个叶节点。每棵树都可以唯一地转换成其对应的二叉树。在由树变换而来的二叉树中，节点N的左子树是(3)对应于原树中的节点，N的右子树是(4)对应于原树中的节点。二叉排序树的平均检索长度为(5)。

(1) A .是特殊的树b .不是树的特殊形式。

c是两棵树的总称。d是只有两个根节点的树结构。

(2) A .左子树b .右子树c .左子树或者没有右子树d .兄弟

(3) ~ (4) A .最左边的子树b .最右边的子树c .最近的右兄弟d .最近的左兄弟

⑤A . O(N2)B . O(n)C . O(log2n)D . O(nlog2n)

n参考答案(1) B (2) A (3) A (4) C (5) C。

9.哈希存储的基本思想是根据(1)决定(2)，冲突(碰撞)指的是(3)。_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _越大，处理矛盾的两种主要方式是(5)。

(1) ~ (2) A .存储地址b .元素序号c .元素个数d .键值

(3) A .两个元素的序列号相同b .两个元素的键值不同，但nonce属性相同。

C.不同的键值对应同一个存储地址d .数据元素太多。

(4) A .非代码属性b .平均检索长度c .负载因子d .哈希表空间

(5) A .线性探索法和双哈希函数法b .溢出区法和无溢出区法

C.分割法和折叠法d .拉链法和开地址法

n参考答案(1)D(2)A(3)C(4)C(5)D A(3)C(4)C(5)D。

10.设二维数组F的行下标为1到5，列下标为0到8，F的每个数据元素占用4个字节。在行存储的情况下，已知数据元素F [2，2]的第一个字节的地址是1044，所以F [3，4]和F [4，3]的第一个字节的地址分别是(1)和(2)，而数组的第一个数据元素的第一个字节和数组的最后一个字节。

对于一般的二维数组G，当(5)时，按行存储的G[I，J]的地址与按列存储的G[J，I]的地址相同。

(1)a . 1088 b . 1084 c . 1092d . 1120

(2)a . 1092 b . 1088 c . 1120d . 1124

(3)a . 1004 b . 1044 c . 1000d . 984

④a . 1183 b . 1179 c . 1164d . 1187

(5)图中的列数与行数相同。

b.g的列的上界与g的行的上界相同。

c.g的列的上界与g的行的下界相同。

d.g的列的上下界与g的行的上下界相同。

n参考答案(1)A (2)C (3)C (4)B (5)D

11.一个按一定顺序存储的表，其中有90，000个元素，已经按关键字的升序排列。现在假设搜索每个元素的概率是一样的，每个元素的关键词是不一样的。

使用顺序搜索法时，平均比较次数约为(1)，最大比较次数为(2)。

现在9万个元素按照排列顺序分成几组，这样每组有g个元素(最后一组可能小于g)。搜索时，从第一组开始，通过比较每组中最后一个元素的关键字，找到待搜索元素所在的组，然后用顺序搜索法找到待搜索元素。在这种搜索方法中，使总平均比较次数最小化的G是(3)，此时的平均比较次数是(4)。当g的值大于或等于90000时，该方法的搜索速度接近于(5)。

(1)~(2)a . 2.5万B. 3万c . 4.5万D. 9万

(3)～(4)a . 100 b . 200 c . 300d . 400

(5) A .快速分类b .斐波那契搜索c .二分法d .顺序搜索

n参考答案(1)C(2)D(3)C(4)C(5)D D(3)C(4)C(5)D。

12.已知无向图的邻接表如图2-35所示:

这个邻接表对应的无向图是(1)。这个图从f开始的深度优先遍历是(2)。从f开始的广度优先遍历是(3)。从f开始的深度优先生成树是(4)。从f开始的广度优先生成树是(5)。

(1)

(2)a . F . G . I . L . J . M . H . b

C.英国皇家航空公司

(3)a . F . G . I . L . K . M . H b . F . G . H . M . I . L . K

C.这是一个很好的例子

(4)

(5)

n参考答案(1)C(2)B(3)B(4)A(5)B(3)B(4)A(5)B。

13.图2-36是加权有向图G的邻接表，从节点V1遍历图G得到的节点序列是(1)；广度遍历图G得到的节点序列为(2)；G的一个拓扑序列是(3)；节点V1到V8节点的最短路径是(4)；节点V1到V8节点的关键路径是(5)。

(1)A. V1，V2，V3，V4，V5，V6，V7，V8 B. V1，V2，V3，V8，V4，V5，V6，V7

C.V1，V2，V3，V8，V4，V5，V7，V6 D. V1，V2，V3，V8，V5，V7，V4，V6

(2)A. V1，V2，V3，V4，V5，V6，V7，V8 B. V1，V2，V4，V6，V5，V3，V7，V8

C.V1，V2，V4，V6，V3，V5，V7，V8

(3)A. V1，V2，V3，V4，V5，V6，V7，V8 B. V1，V2，V4，V6，V5，V3，V7，V8

C.V1，V2，V4，V6，V3，V5，V7，V8

(4)~(5)A.( V1，V2，V4，V5，V3，V8) B. (V1，V6，V5，V3，V8)

C.(V1，V6，V7，V8) D. ( V1，V2，V5，V7，V8)

n参考答案(1) D (2) C (3) B (4) D (5) B。

类似这样的东西，这只是一部分，已经全部发到你邮箱了。