当前位置：问答库＞考研试题

一、填空题

1． 已知链队列的头尾指针分别是f 和r , 则将值x 入队的操作序列是_____。

【答案】

【解析】队列采用链式存储结构，先分配一个节点的内存，然后在队尾添加该节点。

2． 在一个无向图的的邻接表中，若表结点的个数是m , 则图中边的条数是_____条。

【答案】m/2

【解析】对于无向图，在邻接表中，如果存在n 条边，则会有2n 个表结点。 3． 如下的算法分别是后序线索二叉树求给定结点node 的前驱结点与后继结点的算法，请在算法，其空格处填上正确的语句。设线索二叉树的结点数据结构为（lflag ，lcft ，data ，right ，rflag ）中：lflag=0，lcft 指向其左孩子，lflag=1，left 指向其前驱：rflag=0，right 指向其右孩子，rflag=1，right 指向其后继。

Prior （node , x ） { if（node !=null）

If （ （1） ） *x=node->right；else * x-node->left;

}

next （bt , node, x ）/*bt是二叉树的树根*/ { （2） ;

if （node->rflag）（3）; else {do t=*x；;

while （*x==node ）; *x=t; } }

【答案】nodc->rflag==O; *x=ht; *x=nodc->right; prior （t , X ）

4． 有向图G=（V ，E ）, 其中V （G ）=[0, 1，2，3，4, 5}, 用三元组表示弧及弧上的权d 。 E （G ）为 E （G= {<0，5, 100>, <0，2，10>, <1，2，5>，<0，4, 30>，<4, 5, 60>，<3，5, 10>，<2. 3，50>， <4, 3, 20>}，则从源点0到顶点3的最短路径长度是_____，经过的中间顶点是_____。

【答案】50; 4

5． 设单链表的结点结构为为指针域，已知指针px 指向单链表中data 为x 的结

_____；点，指针py 指向data 为y 的新结点，若将结点y 插入结点x 之后，贝懦要执行以下语句：

_____;

【答案】

6． 设数组储，则元素为_____。

【答案】9174；8788

【解析】设一个元素的行标为i ，列标为j 。若以行序为主存储顺序，

则它的存储地址为

若以列序为主存储顺序，则它的存储地址为

7． 设T 和P 是两个给定的串，在T 中寻找等于P 的子串的过程称为_____，又称P 为_____。

【答案】模式匹配；模式串

8． 阅读下列程序，指出其功能，并写出空格处应填上的语句。

【答案】

的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存

的存储地址为_____；若以列序为主序顺序存储，则元素

的存储地址

【解析】本题是在哈希表ht[]中插入值为的元素，如该元素已在哈希表中，报告出错。

9． 在双向循环链表中，向P 所指的结点之后插入指针f 所指的结点，其操作是_____、_____、_____、_____。

【答案】

10．从平均时间性能而言，_____排序最佳。

【答案】快速

【解析】快速算法的平均时间复杂度为nlogn 。

二、判断题

11．当改变网上某一关键路径上任一关键活动后，必将产生不同的关键路径。（ ）

【答案】×

【解析】当改变任意关键路径上的关键活动之后，这个活动可能还是关键活动，因此不会产生不同的关键路径。

12．—个排序算法是否稳定，是指该算法在各种情况下的时间效率是否相差不大。（ ）

【答案】×

【解析】排序的稳定性指：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，

且ri 在rj 之前，而在排序后的

序列中，ri 仍在rj 之前，则称这种排序算法是稳定的；否则称为不稳定的。

13．队列和栈都是运算受限的线性表，只允许在表的两端进行运算。（ ）

【答案】

【解析】栈只能在一端进行操作，队列可以在表的两端进行运算。

14．串是一种数据对象和操作都特殊的线性表。（ ）

【答案】

【解析】串是一种操作特殊的线性表，其特殊性主要体现在数据元素是一个字符。在内存中，一份文本都可以看做是一个字符串，而每一行都可以看做是其子串。

15．用向量和单链表表示的有序表均可使用折半查找方法来提高查找速度。（ ）

【答案】×

【解析】单链表不能使用折半查找方法。折半查找主要用于数据元素有序且存储方式为顺序存储的表。

16．树中的结点和图中的顶点就是指数据结构中的数据元素。（ ）

【答案】√

【解析】树中的结点和图中的顶点就是指数据结构中的数据元素，而它们的边指的是元素之间的关系。

17．连通图上各边权值均不相同，则该图的最小生成树是唯一的。（ ）

【答案】√

【解析】由最小生成树的构建过程知，在确定根结点之后，因为连通图上各边权值均不相同，下一个结点的选择是唯一的，所以该图的最小生成树是唯一的。

18．哈希表的平均查找长度与处理冲突的方法无关。（ ）

【答案】×

【解析】常见的处理冲突的方法：开放地址法；再哈希法；链地址法；建立一个公共的溢出