考研资料数据结构试卷.doc.pdfVIP

得分1、填空题。(每小题2分，本题满分20分)

(1)假设用一个一维数组B来按行存放一个对称矩阵A的下三角部分，那么访问A的第i行第

j列元素的语句是：。(下标都从0开始)

(2)在单链表指针P所指结点后插入指针为s的结点操作是：-

⑶线性表L=(ao,ai,a2,...az)用数组表示，假设删除表中任一元素的概率相同，则删除一个

元素所需的平均移动次数为。

(4)在指针L指向一带头结点的双向循环链表，则判断该表中只有一个元素结点的条件

是：(设结点结构为iLinkdatarLink)

(5)使用邻接矩阵表示图时，遍历一个顶点的所有相邻顶点的时间复杂度是:o(假设图的顶点个

数为n,边的个数为e)

⑹已知带权有向图如下，使用Dijkstra算法求解从顶点1到达各顶点的最短距离时，该算法将

按照(列出顶点顺序)的顺序给出各个顶点的距离。

(7)假设一组关键码为(20,41,22,17,19,56,35),则用堆排序的方法建立的初始最

大堆为o

(8)KMP模式匹配算法的时间复杂度是：。

(9)设循环队列存放在数组A[0..m-l]中，若用牺牲一个单元的办法区分队列满和队列空(设队

尾指针为rear,队头指针为first),则判断队满的条件是：

(10)对n个元素进行排序，如果用直接选择排序，所需的关键码比较次数最少为,

如果用直接插入排序，则所需的关键码比较次数最少为O

得分2、选择题。(每小题2分，本题满分20分)

(1)_____假设使用转换后的二叉树来表示森林，那么对该二叉树的前序遍历对应于对森林的

____遍历。

A先根次序遍历B后根次序遍历C广度优先遍历D以上都不是

(2)假设我们将一个表达式表示为一棵二叉树。比如a+b*c对应的树的根为+,其左子树是一个

叶子结点a,右子树的根为*,左右子结点分别为b和c。显然每个内部结点代表了一个运

算。假设一个并行CPU有很多个ALU可以同时执行计算任务，且完成所有计算需要的时

间都是一个时间单位。那么完成一个表达式计算的最短时间是-

A树的高度B树的宽度C树的内部结点个数D树的分支数

(3)假设在快速排序算法中总是选择被排序子序列的最后一个元素作为基准。那么这个算法

的最坏情况出现在_______

O

A被排序的初始序列已经排好序时

B被排序的初始序列是逆序时

C被排序的初始序列呈现中间大，并逐次向两边减小的情况

D以上都不是

(4)散列方法中，线性探查法的“堆积”问题是指。

A不同探查序列的关键码占据了可利用的空桶，使得寻找某一关键码需要经历很长的探查

序列。

B不同探查序列的关键码占据了可利用的空桶，使得插入某个关键码时找不到空桶。

C不同探查序列的关键码占据了可利用的空桶，导致寻找某个关键码时出现错误。

D不同探查序列的关键码占据了可利用的空桶，为了保证算法能够寻找到正确的关键码，

不得不将装载因子限制在某个阀值之下。

(5)在中序线索二叉树(使用ITag,rTag)中，一个结点的中序后

A如果其rTag继是。(多选)

B为0,如果其则后继是其rightChild所指结点的最左后代;

CrTag为0,则后继是其rightChild所指结点；

如果其rTag

D则后继是其rightChild所指结点的最左后代;

为1,如果其

则后继是其rightChild所指结点。

(6)假设有一棵二叉树的结点前序排列是1、2、3、4、5。下面的—序列不可能是这棵二

A3、2、1、4、5

B2、3、1、4、5

C2、1、4、5、3

D2、5、

叉树的中序排列。

⑺有11个结点的AVL树的最大高度为。(假设叶结点的高度为1,树的高度为根

结点的高