2018年浙江大学878计算机学科专业基础(含程序设计基础(C) 、数据结构)之数据结构考研仿真模拟五套题
● 摘要
一、填空题
1． 设有一个10阶对称矩阵A 采用压缩存储方式(以行为主序存储:a 11＝l) ， 则a 85的地址为_____。
【答案】33
【解析】设存储的元素的行标为i ，列标为j 。若i ＞＝j ，则
的地址为l ＋2＋... ＋i ﹣l ＋j
＝i(i﹣l)/2＋j 。若i ＜j 。则的地址为j(j﹣l)/2＋i 。将i ＝8，j ＝5代入得33。
2． 以下是用类C 语言写出的算法，该算法将以二叉链表存储的二叉树中的叶结点按从左到右的顺序链成一个带头结点的双向循环链表，链接时，结点的Lchild 域作为前链域，指向结点的直接前驱，结点的Rchild 域作为后链域，指向结点的直接后继。算法中，使用一个顺序栈stack , 栈顶指针为top ，P ，t 为辅助指针，head 为双向循环链表的头指针。试填充算法中的空格，使算法完整。
【答案】
3． 在单链表中设置头结点的作用是_____。
【答案】方便运算
4． 阅读下列程序，指出其功能，并写出空格处应填上的语句。
【答案】
【解析】本题是在哈希表中插入值为item 的元素，如该元素已在哈希表中，报告出错。
5． 设数组的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存储，则元素a[45，68]的存储地址为_____；若以列序为主序顺序存储，则元素a[45，68]的存储地址为_____。
【答案】9174；8788
【解析】设一个元素的行标为i ，列标为j 。若以行序为主存储顺序，则它的存储地址为2000＋((i﹣l)*80＋j ﹣
1) 2。若以列序为主存储顺序，则它的存储地址为2000＋((j﹣l)*50＋i ﹣l)*2。
6． 设广义表L ＝(（ ），（ ）) ，则head(L)是_____tail(L)是_____L的长度是_____；深度是_____。
【答案】（ ）；(（ ）) ；2；2
【解析】广义表的表头是表的第一个元素，表尾是除了第一个元素外其余的所有的元素构成的表；表的长度指表中元素的个数；表的深度指展开后括号的层数。
7． 在基于关键字比较且时间为_ 的排序中，若要求排序是稳定的，则可选用_____排序；若要求就地排序(及辅助空间为O(1))，则可选用_____排序。
【答案】归并；堆
8． 属于不稳定排序的有_____。
【答案】希尔排序、简单选择排序、快速排序、堆排序等
9． 在一个无向图的的邻接表中，若表结点的个数是m ，则图中边的条数是_____条。
【答案】
【解析】对于无向图，在邻接表中，如果存在n 条边，则会有2n 个表结点。
10．已知如下程序段:
语句1执行的时间复杂度为_____:语句2执行的时间复杂度为_____:语句3执行的时间复杂度为_____:语句4执行的时间复杂度为_____。
【答案】(1)n＋1 (2)n
(3)n(n＋3)/2 (4)n(n＋l)/2
【解析】语s 句1执行到不符合条件情况下，执行了n ＋1次。当语句1不符合条件了是不会执行语句2的，所以语句2被执行了n 次。语句3每次都要执行到不符合条件，故为2＋3＋4...... ＋(n＋l) 加起来就是n(n＋3)/2。语句3不符合条件了是不会执行语句4的。所以语句4被执行了1＋2＋3...... ＋n 即n(n＋l)/2。
二、单项选择题
11．稀疏矩阵一般的压缩存储方法有两种，即（ ）。
A. 二维数组和三维数组 B. 三元组和散列 C. 三元组和十字链表 D. 散列和十字链表 【答案】C
【解析】稀疏矩阵一般的压缩方法为三元组表和十字链表。三元组表就是将非零元素及其对应的行和列构成一个三元组(行标，列标，值) 。十字链表相比三元组表而言，主要是对每个结点增加了两个链域。如果数组经常运算时，会产生大量数据元素的移动，此时，采用链表存储结构更为恰当。
12．下列排序算法中，占用辅助空间最多的是（ ）。
A. 归并排序 B. 快速排序 C. 希尔排序 D. 堆排序 【答案】A
【解析】归并排序的辅助空间为O(n)，快速排序所占用的辅助空间为
，堆排序所占
用的辅助空间为O(1)。
13．若对n 阶对称矩阵A 以行序为主序方式将其下三角形的元素(包括主对角线上所有元素) 依次存放于一维数组B[l...(n(n＋1))/2]中，则在B 中确定a ij (i＜j) 的位置k 的关系为（ ）。
A.i*(i﹣1)/2＋j