2017年大连理工大学电子信息与电气工程学部810数(9)

31．请运用快速排序思想，设计递归算法实现求n（n>l）个不同元素集合中的第

【答案】算法如下：

小元素。

32．请用流程图或高级语言表示算法。已知有向图有n个顶点，请写算法，根据用户输入的数对，对于每条这样建立该有向 图的邻接表。即接受用户输入的<vi，yj>（以其中之一为0标志结束）的边，申请一个结点，并插 入到的单链表中，如此反复，直到将图中所有边处理完毕。

提示：先产生邻接表的n个头结点（其结点数值域从1到n）。 【答案】算法如下：

//建立有向图的邻接表存储结构

//输入顶点信息

//题目要求两顶点之一为0表示结束

33．编写算法，将自然数按“蛇形”填矩阵中。例如图所示（用程序实现）。

图

【答案】算法如下：

//

34．设记录

的关键字为

树结点

的败者树，要求除

指向败者记录，

和

为全胜记以外，只用

录下标。写一算法产生对应上述

辅助空间。 【答案】算法如下：

35．设A和B均为下三角矩阵，每一个都有n行n列。因此在下三角区域中各有无素。另设有一个二维数组C，它有n行

个

列。试设计一个方案，将两个矩阵A和B中的下三

和B的矩

角区域元素存放于同一个C中。要求将A的下三角区域中的元素存放于C的下三角区域中，B的下三角区域中的元素转置后存放于C的上三角区域中。并给出计算A的矩阵元素阵元素在C中的存放位置下标的公式。

【答案】算法如下：

36．编写算法打印出由指针Hm指向总表头的以十字链表形式存储的稀疏矩阵中每一行的非零元的个数。注意：行、列及总表头结点的形式为：

它们已用

域链接成循环链表。非零元的结点形式也同上，每一行（列）的非零元由

域把它们链接成循环链表，该行（列）的表头结点即为该行（列）循环链表的表头。

【答案】算法如下：

37．写出一趟快速排序算法。

【答案】算法如下：

2017年大连理工大学电子信息与电气工程学部810数据结构和计算机组成原理之数

据结构考研仿真模拟题（二）

说明：①本资料为VIP学员内部使用，严格按照2017考研最新题型及历年试题难度出题。

——————————————————————————————————————————

一、选择题

1． 循环队列元素数是（ ）。

【答案】A

【解析】对于循环队列，需要深刻理解队头在队尾进行进队操作。

和队尾

的概念，在队头进行出队操作，

如果为负则元

可能为正也可能为负，为正时元素个数=

存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的

素的个数=所以统一的公式就是

2． 和顺序栈相比，链栈有一个比较明显的优势是（ ）。

A.通常不会出现找满的情况 B.通常不会出现栈空的情况 C.插入操作更容易实现 D.删除操作更容易实现 【答案】A

3． 单处理机系统中，可并行的是（ ）。

I.进程与进程 II.处理机与设备 III.处理机与通道 IV.设备与设备 A.I、II和III B.I、II和IV C.I、III和IV D.II、III和IV 【答案】D

【解析】注意区分并发和并行。在单处理机系统中，进程只能并发。微观上同一时刻占用处理机的进程只有一个，因此，进程之间不是并行的。通道是独立于CPU控制的输入/输出的设备，处理机与通道两者是可以并行。显然，设备和设备之间也是可以并行的。