2017年燕山大学信息科学与工程学院810数据结构考研导师圈点必考题汇编
● 摘要
一、填空题
1．
【答案】5
2． 线性表
【答案】（n －1）/2
【解析】删除第一个元素需要移动n －i 次，以此类推，删除最后一个元素需要移动0次。平 均次数为
3． 下面程序的功能是用递归算法将一个整数按逆序存放到一个字符数组中。如123存放成321。请填空：
【答案】
【解析】通过递归算法，首先找到最高位的值，将其放到str 对应的数组中，依次反向获取从高位到地位的值，将其放到数组中，完成了将整数逆序放到一个字符数组中。
4． 假定有k 个关键字互为同义词，若用线性探测再哈希法把这k 个关键字存入哈希表中，至少要进行_____次探测。
【答案】
【解析】当该关键字发生冲突时，用线性探测不会遇到别的关键字冲突，这个时候需要探测 的次数最小。总次数为
5． 设用希尔排序对数组{98，36，-9，0，47，23，1，8，10，7}进行排序，给出的步长（也称 增量序列）依次是4，2，1则排序需_____趟，写出第一趟结束后，数组中数据的排列次序_____。
【答案】3; （10，7，-9，0，47，23，1，8，98，36）
第 2 页，共 69 页
=_____
用数组表示，假定删除表中任一元素的概率相同，则删除一个元素
平均需要移动元素的个数是_____。
6． N 个顶点的连通图用邻接矩阵表示时，该矩阵至少有_____个非零元素。
【答案】2（N-1）
【解析】所谓连通图一定指的是无向图，有向图会称作强连通图。连接N 个顶点，至少需要N-1条边就可 以了。由于无向图的每一条边同时关联了两个顶点。因此用邻接矩阵表示时，该矩阵至少有2（N-1）个非零元素。
7． 设数组的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存储，则元素为_____。
【答案】9174；8788
【解析】设一个元素的行标为i ，列标为j 。若以行序为主存储顺序，
则它的存储地址为
若以列序为主存储顺序，则它的存储地址为
8． 在图G 的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的_____; 对于有向图来说等于该顶点的_____。
【答案】度；出度
9． 在二叉树中，指针p 所指结点为叶结点的条件是_____。
【答案】
【解析】叶子节点的左右孩子都不存在。
10．一个有2001个结点的完全二叉树的高度是_____。
【答案】11
【解析】完全二叉树的高度
11．空格串是指_____，其长度等于_____。
【答案】由空格字符（
值32）所组成的字符串；空格个数
12．在单链表L 中，指针P 所指结点有后继结点的条件是_____
【答案】
【解析】指针所指节点的指针域所指向的元素非空，说明该指针所指节点有后继结点。
13．用循环链表表示的队列长度为n ，若只设头指针，则出队和入队的时间复杂度分别是_____和_____；若只设尾指针，则出队和入队的时间复杂度分别是_____和_____。
【答案】
【解析】队列的出队操作即删除队头的元素，队列的入队操作即在队尾添加元素，循环链表只设头指针，出队时，只要把头结点的下一个结点删除就好了，入队时，要把新的结点插入队尾，必须把队列遍历，找到队尾指针，才能插入。循环队列只设尾指针，出队时只要把为指针的下一
第 3 页，共 69 页
的存储地址为_____；若以列序为主序顺序存储，则元素的存储地址
个结点或者下下个结点删除即可，入队时，只要在尾指针的后面插入新的结点，并更新尾结点即可。
14．二进制地址为011011110000，大小为
【答案】011011110100；011011100000
011011110000是块的起始地址，【解析】大小分别为式如下：
当大小为4时，起始地址
为当大小为16时，起始地址为
：
15．高度为h 的堆中，最多有_____元素，最少有_____个元素。
【答案】
当最后一层只有
【解析】当这个堆构成的是满二叉树时，元素的个数最多，
元素个数为一个元素时，此时堆的元素个数最少，元素个数为
和
其伙伴块的起始地址计算公
和块的伙伴地址分别为：_____
二、选择题
16．对序
列
A.1 B.4 C.3 D.2 【答案】B
【解析】由所给的序列知，本序列要进行递增排序，经过一趟后15的位置没有变化，而给的序列中只有20比15大，20的位置和15的位置相差4。所以该次采用的増量是4。
17．某计算机有16个通用寄存器，采用32位定长指令字操作码字段（含寻址方式位）为8位，Store 指令的源操作数和目的操作数分别采用寄存器直接寻址和基址寻址方式，若基址寄存器可使用任一通用寄存器，且偏移量用补码表示，则Store 指令中偏移量的取值范围是（ ）
A.-32768〜+32767 B.-32767〜+32768 C.-65536〜+65535 D.-65535〜+65536 【答案】A
【解析】寄存器个数指令编址方式如下所示：
第 4 页，共 69 页
用希尔排序方法排序，经一趟后序列变
为
则该次采用的增量是（ ）。
偏移量有32-8-4-4=16位
相关内容
相关标签