专升本数据结构

《专升本数据结构》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、专升本《数据结构》试卷一、填空题：（每小题2分，共10分）1.设有数据结构（D，R），其中D是数据元素的有限集，R是        的有限集。2.深度为k的二叉树其结点数至多有      个。3.栈是一种特殊的线性表，它允许在表的一端进行                    操作。4.通常象交通、道路问题的数学模型是一种称为           的数据结构。5.哈希表是一种查找表，可以根据哈希函数直接获得                    。二、单项选择题：（每小题2分，共10分）对于下列各题，在备选答案中选出一个正确的，并将其编号填在“    ”位置上。1

2、. 若线性表最常用的操作是存取第i个元素及其前驱元素的值，则采用    存储方式最节省运算时间。A.单链表   B.双链表   C.单循环链表   D.顺序表2. 下列排序算法中，    算法在进行一趟相应的排序处理结束后不一定能选出一个元素放到其最终位置上。。A.直选择排序   B.冒泡排序   C.归并排序  D.堆排序3. 队列的操作原则是    。A.先进后出   B.先进先出   C.只能进行插入  D.只能进行删除4. 在具有n个结点的二叉链表中，非空的链域个数为    。A.n-1  B.n   C.n+1   D.不确定5. 对具有n个元素的有序查

3、找表采用折半查找算法查找一个键值，其最坏比较次数的数量级为    。A.O(log2n)   B.O(n)   C.O(nlog2n)  D.O(n2)三、判断题：（每小题2分，共10分）判断下列各题是否正确，若正确，在题后的括号内填“T”，否则填“F”。1.在栈为空的情况下不能作出栈处理，否则，将产生下溢出。（ ）2.如果有向图G=(V,E)的拓扑序列唯一，则图中必定仅有一个顶点的入度为0、一个顶点的出度为0。（ ）3.在大根堆中，必定满足每个结点的键值大于其左右子树中所有结点的键值。（ ）4.在采用线性探测法处理冲突的散列表中所有同义词在表中相邻。（ ）5.在

4、索引顺序表中，对索引表既可采用顺序查找，也可采用二分查找。（ ）四、解答下列各题：（每题10分，共40分）1.已知线性表L采用带头结点的的单向循环链表表示，试给出它的存储结构类型描述及相应的示意图。。2.已知一棵二叉树的先序、中序和后序序列如下所示，请填写各序列中空格处的结点，并画出该二叉树的二叉链表存储结构示意图。先序序列是：_B_F_ICEH_G；中序序列是：D_KFIA_EJC_；后序序列是：_K_FBHJ_G_A3.已知数据表为（48，70，33，65，24，56，12，92，86，22），a)写出采用快速排序算法进行排序时第一趟快速划分的详细过程及结果；

5、b)写出按基数排序思想对最低位进行一次分配和收集的结果。4.对图1所示的带权无向图，写出它的邻接矩阵和深度优先搜索序列，并按克鲁斯卡算法求其最小生成树（写出求解的详细过程示意图）。图1  带权无向图 五、算法设计题：（前两题必做，每题15分，共30分；第三题为附加题，选做，10分）1.已知队列Q以循环队列存储。写出Q的存储结构类型描述，并试编写算法实现将元素x插入队列Q的入队操作EnQueue(Q,x)和从队列Q中获取队首元素的函数GetTop(Q)。2.假设线性表L=(a1,a2,……,an)用带头结点的单链表存储表示，试编写算法对其实现就地逆置，即利用原链表中

6、每一个结点存储空间，使得元素的逻辑次序改变为(an,……,a2,a1)。3.设非空二叉树T采用中序线索二叉链表表示，写出T的存储结构类型描述。试编写算法InOrderTraverse(T)实现对二叉树T的中序遍历。山东：07年专升本考试数据结构模拟试题2http://www.exam8.com　来源：考试吧（Exam8.com）整理　点击：122　更新：2006-12-270:36:04一、单项选择题：（每小题2分，共10分）对于下列各题，在备选答案中选出一个正确的，并将其编号填在“    ”位置上。1.折半查找法要求查找表中各元素的键值必须是    。A.递增或

7、递减   B.递增   C.递减  D.无序2.若对某线性表最常进行的操作是在最后一个元素之后插入和删除第一个元素，则采用    存储方式最节省运算时间。A.单链表                   B.双链表C.仅有头指针的单循环链表   D.仅有尾指针的单循环链表3.有64个结点的完全二叉树的深度为    （假设根结点的层次为1）。A.8   B.7   C.6  D.54.对于键值序列（2，33，21，18，65，38，7，49，24，86），用筛选法建堆，必须从键值为    的结点开始。A.86   B.2   C.65  D.385.设图G用邻接表存储

8、，则求每个