山东省专升本考试

《山东省专升本考试》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、专升本《数据结构》试卷一、填空题：（每小题2分，共10分）1.设有数据结构（D，R），其中D是数据元素的有限集，R是的有限集。2.深度为k的二叉树其结点数至多有个。3.栈是一种特殊的线性表，它允许在表的一端进行操作。4.通常象交通、道路问题的数学模型是一种称为的数据结构。5.哈希表是一种查找表，可以根据哈希函数直接获得。二、单项选择题：（每小题2分，共10分）对于下列各题，在备选答案中选出一个正确的，并将其编号填在“”位置上。1.若线性表最常用的操作是存取第i个元素及其前驱元素的值，则采用存储方式最节省运算时间。A.单链表B.双链表C.单循环链表D.顺序表2.下列排序算法中，算法在进行一趟相应

2、的排序处理结束后不一定能选出一个元素放到其最终位置上。。A.直选择排序B.冒泡排序C.归并排序D.堆排序3.队列的操作原则是。A.先进后出B.先进先出C.只能进行插入D.只能进行删除4.在具有n个结点的二叉链表中，非空的链域个数为。A.n-1B.nC.n1D.不确定5.对具有n个元素的有序查找表采用折半查找算法查找一个键值，其最坏比较次数的数量级为。A.O(log2n)B.O(n)C.O(nlog2n)D.O(n2)三、判断题：（每小题2分，共10分）判断下列各题是否正确，若正确，在题后的括号内填“T”，否则填“F”。1.在栈为空的情况下不能作出栈处理，否则，将产生下溢出。（）2.如果有向图G

3、=(V,E)的拓扑序列唯一，则图中必定仅有一个顶点的入度为0、一个顶点的出度为0。（）3.在大根堆中，必定满足每个结点的键值大于其左右子树中所有结点的键值。（）4.在采用线性探测法处理冲突的散列表中所有同义词在表中相邻。（）5.在索引顺序表中，对索引表既可采用顺序查找，也可采用二分查找。（）四、解答下列各题：（每题10分，共40分）1.已知线性表L采用带头结点的的单向循环链表表示，试给出它的存储结构类型描述及相应的示意图。。2.已知一棵二叉树的先序、中序和后序序列如下所示，请填写各序列中空格处的结点，并画出该二叉树的二叉链表存储结构示意图。先序序列是：_B_F_ICEH_G；中序序列是：D_K

4、FIA_EJC_；后序序列是：_K_FBHJ_G_A3.已知数据表为（48，70，33，65，24，56，12，92，86，22），a)写出采用快速排序算法进行排序时第一趟快速划分的详细过程及结果；b)写出按基数排序思想对最低位进行一次分配和收集的结果。4.对图1所示的带权无向图，写出它的邻接矩阵和深度优先搜索序列，并按克鲁斯卡算法求其最小生成树（写出求解的详细过程示意图）。图1带权无向图五、算法设计题：（前两题必做，每题15分，共30分；第三题为附加题，选做，10分）1.已知队列Q以循环队列存储。写出Q的存储结构类型描述，并试编写算法实现将元素x插入队列Q的入队操作EnQueue(Q,x)和

5、从队列Q中获取队首元素的函数GetTop(Q)。2.假设线性表L=(a1,a2,……,an)用带头结点的单链表存储表示，试编写算法对其实现就地逆置，即利用原链表中每一个结点存储空间，使得元素的逻辑次序改变为(an,……,a2,a1)。3.设非空二叉树T采用中序线索二叉链表表示，写出T的存储结构类型描述。试编写算法InOrderTraverse(T)实现对二叉树T的中序遍历。