2017年上海市培养单位上海生命科学研究院864程序设计之数据结构考研仿真模拟题
● 摘要
一、填空题
1. 设数组储,则元素为_____。
【答案】9174;8788
【解析】设一个元素的行标为i ,列标为j 。若以行序为主存储顺序,
则它的存储地址为
若以列序为主存储顺序,则它的存储地址为
2. 执行顺序查找时,存储方式可以是_____,折半查找时,要求线性表_____,分块查找时要求线性表_____,而哈希表的查找,要求线性表的存储方式是_____。
【答案】顺序存储或链式存储;顺序存储且有序;块内顺序存储,块间有序;散列存储
3. 以下是用类C 语言写山的算法,该算法将以二叉链表存储的二叉树中的叶结点按从左到右的顺序链成一个带头结点的双向循环链表,链接时,结点的Lchild 域作为前链域,指向结点的直接前驱,结点的Rchild 域作为后链域,指向结点的直接后继。算法中,使用一个顺序栈stack , 栈顶head 为双向循坏链表的头指针。 指针为top , P , t 为辅助指针,试填充算法中的空格,使算法完整。
void leafchain(BiTree Abt)
{p={BiTree)malloc (sizeof (BiTNode )); If (!p ){print£(“OVERFLOW\n”; exit (1); }
head=p; top=0; if (bt )
{top++; stack[top]=bt; while (top )
{t=stack[top]; top--;
if (it->Lchild && !t->Rchild){ (1) ; (2) ; (3) ; } else {if( (4) ){top++; stack[top]= (5) ; } if ( (6) ){top++; stack[top]= (5) ; } } }
(8) ; (9) ; } } 【答案】
p->Rchild=t:t->Lchild=p:p=t:
t->Rchild!=null:t->Rchild:
第 2 页,共 63 页
的基地址为2000,每个元素占2个存储单元,若以行序为主序顺序存
的存储地址为_____;若以列序为主序顺序存储,则元素
的存储地址
t->Lchild!=null: t->Lchild:
p->Rchild=head:head->Lchild=p
4. 对单链表中元素按插入方法排序的C 语言描述算法如下,其中L 为链表头结点指针。请填充算法中标出的空白处,完成其功能。
【答案】(1)(2)(3)(4)(5)
置空链表,然后将原链表结点逐个插入到有序表中
当链表尚未到尾,p 为工作指针
查P 结点在链表中的插入位置,这时q 是工作指针
将P 结点链入链表中
是q 的前驱,u 是下个待插入结点的指针
5. VSAM (虚拟存储存取方法)文件的优点是:动态地_____,不需要文件进行_____,并能较快地_____进行查找。
【答案】分配和释放存储空间;重组;对插入的记录
6. 在图G 的邻接表表示中,每个顶点邻接表中所含的结点数,对于无向图来说等于该顶点的_____; 对于有向图来说等于该顶点的_____。
【答案】度;出度
7. 顺序栈用
【答案】
存储数据,栈顶指针是top ,则值为x 的元素入栈的操作是_____。
【解析】先判断栈是否满,如果不满,元素入栈。否则返回溢出信息。
8. 根据线性表的链式存储结构中每一个结点包含的指针个数,将线性链表分成_____和_____; 而又根据指针的连接方式,链表又可分成_____和_____。
【答案】单链表;双链表;(动态)链表;静态链表
【解析】线性表的链式存储结构根据每个结点包含的指针个数分为单链表和双链表,单链表只包含一个指针,指向后续元素,双链表包括两个指针,指向前一个元素和后续元素。根据指针的连接方式,链表可分为动态链表和静态链表。静态链表的指针指向下一个元素的编号,动态链表的指针指向下一个元素的物理位置。
第 3 页,共 63 页
9. 在单链表中设置头结点的作用是_____。
【答案】方便运算
10.有向图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
11.顺序查找n 个元素的顺序表,若查找成功,则比较关键字的次数最多为_____次;当使用监视哨时,若查找失败,则比较关键字的次数为_____。
【答案】
【解析】最多的情况就是把整个表遍历了一遍。使用监视哨时,需要多一个存储空间来存监视哨。
12.深度为H 的完全二叉树至少有_____个结点; 至多有_____个结点; H 和结点总数N 之间的关系是_____。
【答案】
二、选择题
13.对序
列
A.1
B.4 C.3 D.2
【答案】B
【解析】由所给的序列知,本序列要进行递增排序,经过一趟后15的位置没有变化,而给的序列中只有20比15大,20的位置和15的位置相差4。所以该次采用的増量是4。
14.站点A 、B 、C 通过CDMA 共享链路,A 、B 、C 的码片序列(chipping sequence
)分别是
和
C 收到A 发送的数据是( )
A.000 B.101 C.110 D.111
【答案】B
【解析】用A 的码片与信息做内积运算
第 4 页,共 63 页
用希尔排序方法排序,经一趟后序列变
为
则该次采用的增量是( )。
若C 从链路上收到的序列是则