《2017年燕山大学重型机械协同创新中心810数据结构考研冲刺密押题.doc》由会员分享，可在线阅读，更多相关《2017年燕山大学重型机械协同创新中心810数据结构考研冲刺密押题.doc（4页珍藏版）》请在金锄头文库上搜索。
1、2017年燕山大学重型机械协同创新中心810数据结构考研冲刺密押题一、填空题1 假定查找有序表【答案】37/12【解析】折半查找时每个的次数如表所示：表 平均查找次数为 2 阅读下列程序，指出其功能，并写出空格处应填上的语句。 【答案】中每个元素的概率相等，则进行折半查找时的平均查找长度为_【解析】本题是在哈希表ht中插入值为的元素，如该元素已在哈希表中，报告出错。 3 在下面的程序段中，对X 的赋值语句的时间复杂度为_（表示为n 的函数）。 【答案】1（12）（123）?（l 2. n ）=n（n 1）（n 2）/6，即【解析】当i=l时，赋值语句就被执行了一次。当i=2时，赋值语句被执行了
2、12次。当i=3时，赋值语句被执行了123次。可以推出赋值语句总共被执行了1（12）（123）（l 2. n ）=n（n 1）（n 2）/6次。4 求REPLACE （S ，V , m ）=_。【答案】 已 知 5每一棵树都能唯一地转换为它所对应的二叉树。若已知一棵二叉树的前序序列是中序序列是前庁序列是_。【答案】 .，则它的后庁序列是_。设上述二叉树是由某棵树转换而成，则该树的【解析】树的抑序序列对应二叉树的前序序列. 该二叉树转换成森林吋含三棵树. 其第一棵树的前序是。6 己知有序表为（12，18，24，35，47，50，62，83，90，115，134）当用二分法查找90时，需_次查找成
3、功，查找47时_成功，查找100时，需_次才能确定不成功。【答案】2；4；3【解析】二分法查找元素次数列表 查找100是找到115就停止了。 7 以下程序的功能是实现带附加头结点的单链表数据结点逆序连接，请填空完善之。 【答案】（1）（2）链表未到尾就一直进行将当前结点作为头结点后的第一元素结点插入 8 设有一个空找，栈顶指针为1000H （十六进制），现有输入序列为1，2，3, 4, 5，经过PUSH ，PUSH , POP , PUSH , POP ，PUSH ，PUSH 之后，输出序列是_，而栈顶指针值是_。设栈为顺序栈，每个元素占4个字节。【答案】23; 100CH9 假定有k 个关键
4、字互为同义词，若用线性探测再哈希法把这k 个关键字存入哈希表中，至少要进行_次探测。【答案】 【解析】当该关键字发生冲突时，用线性探测不会遇到别的关键字冲突，这个时候需要探测 的次数最小。总次数为 10设为哈夫曼树的叶结点数日，则该哈夫曼树共有_个结点。【答案】 【解析】哈夫曼树只有度为0和2的节点。11循环队列的引入，目的是为了克服_。【答案】假溢出时大量移动数据元素【解析】用数组实现队列时，如果不移动，随着数据的不断读写，会出现假满队列的情况。即尾数组已满但头数组还是空的。循环队列也是一种数组，引入循环队列，有效克服假溢出大量移动数据元素的问题。 12在n 个顶点的非空无向图中，最多有_个
5、连通分量。【答案】n【解析】当n 个顶点之间没有边，都是孤立的顶点时，有n 个连通分量。13在单链表L 中，指针P 所指结点有后继结点的条件是_【答案】 【解析】指针所指节点的指针域所指向的元素非空，说明该指针所指节点有后继结点。14设用希尔排序对数组98，36，-9，0，47，23，1，8，10，7进行排序，给出的步长（也称 增量序列）依次是4，2，1则排序需_趟，写出第一趟结束后，数组中数据的排列次序_。【答案】3; （10，7，-9，0，47，23，1，8，98，36）15设二维数组A 的行和列的下标范围分别为【答案】时，则i=2，j=3。 当其值为和每个元素占2个单元，按行优先顺处的元素为_。序存储，第一个元素的存储起始位置为b ，则存储位置为【解析】令这个元素的行标为i ，列标为j 。则它的存储位置是二、选择题16设有一个10阶的对称矩阵A ，采用压缩存储方式，以行序为主存储，储地址为1，每个元素占一个地址空间，则A.13的地址为（ ）。为第一元素，其存一、填空题考研试题
