数据构造专升本模拟题及参考答案讲课教案 (2).docx

《数据构造专升本模拟题及参考答案讲课教案 (2).docx》由会员分享，可在线阅读，更多相关《数据构造专升本模拟题及参考答案讲课教案 (2).docx（25页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据构造专升本模拟题及参考答案讲课教案作业题一一、单项选择题1.从逻辑上能够把数据构造分为两大类。A动态构造、静态构造B顺序构造、链式构造C线性构造、非线性构造D初等构造、构造型构造2.链表不具有的特点是A插入、删除不需要移动元素B可随机访问任一元素C不必事先估计存储空间D所需空间与线性长度成正比3.下面程序段的时间复杂度的量级为。For(i=1;iABCDEFBBCDEFGCBCPQRSTDBCDEFEF10、数组常用的两种基本操作是。A建立与查找B删除与查找C插入与索引D查找与修改二、填空题1.所谓稀疏矩阵指的是_且分布没有规律。2.队列是_的线性表，其运算遵循_的原则。3.空格串是_。4

2、.简单项选择择排序和起泡排序中比拟次数与序列初态无关的算法有_。5、设图G有n个顶点和e条边，则对用邻接矩阵表示的图进行深度或广度优先搜索遍历时的时间复杂度为，而对用邻接表表示的图进行深度或广度优先搜索遍历时的时间复杂度为，图的深度或广度优先搜索遍历时的空间复杂度均为。6、一个图的表示法是唯一的，而表示法是不唯一的。三、算法设二叉树采用二叉链表构造，试设计一个算法统计给定二叉树中的一度结点数目。四、应用题1、对关键字无序序列(36，25，48，12，65，43，20，58)进行直接选择排序，请写出每一趟排序的结果。10分2、对无向带权图，用克鲁斯卡尔算法构造最小生成树。10分3、已知记录关键字

3、集合为53,17,19,61,98,75,79,63,46,49要求散列到地址区间100,101,102,103,104,105,106,107,108,109内，若产生冲突用开型寻址法的线性探测法解决。要求写出选用的散列函数；构成的散列表；计算出查找成功时平均查找长度与查找不成功的平均查找长度。设等概率情况4、设被查找文件有4095个记录，对每个记录查找记录概率相等，若采用顺序查找，成功查找平均比拟次数为多少？作业题二、单项选择题1.有六个元素6，5，4，3，2，1的顺序进栈，问下列哪一个不是合法的出栈序列？A.543612B.453126C.346521D.2341562.栈和队都是A顺序

4、存储的线性构造B.链式存储的非线性构造C.限制存取点的线性构造D.限制存取点的非线性构造3、顺序查找法合适于存储构造为的线形表。A散列存储B顺序存储或链接存储C压缩存储D索引存储4、分别下面列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是()。A100，80，90，60，120，110，130B100，120，110，130，80，60，90C100，60，80，90，120，110，130D(100，80，60，90，120，130，110)5、折半查找的平均比拟次数为。AnBn/2Clog2nDlog2(n+1)6、当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，可以用

5、顺序查找，但前者比后者的查找速度A必定快B不一定C在大部分情况下要快D取决于表递增还是递减7、已知一有向图的邻接表存储构造如下列图如示。根据有向图的深度优先遍历算法，从顶点v1出发，所得到的顶点序列是。Av1，v2，v3，v5，v4Bv1，v2，v3，v4，v5Cv1，v3，v4，v5，v2Dv1，v4，v3，v5，v28、为了方便地对图状构造的数据进行存取操作，则其中数据存储构造宜采用。A顺序存储B链式存储C索引存储D散列存储9、在一个具有n个顶点的有向图中，若所有顶点的出度之和为s，则所有顶点的入度之和为。AsBs-1Cs+1Dn10、如下图，给出由7个顶点组成的无向图。从顶点A出发，对它

6、进行深度优先搜索得到的顶点序列是。AAECDBFGBAGBFDECCACEDBGFDABDGFEC二、填空题1.设n0为哈夫曼树的叶子结点数目，则该哈夫曼树共有_个结点。2.有数据WG=7，19，2，6，32，3，21，10，则所建Huffman树的树高是_，带权途径长度WPL为_。3.设一棵完全二叉树叶子结点数为k,最后一层结点数2，则该二叉树的高度为_。4.采用分块查找时，若线性表中共有625个元素，查找每个元素的概率一样，假设采用顺序查找来确定结点所在的块时，每块应分个结点最佳。5、设G为具有N个顶点的无向连通图，则G中至少有条边。6、哈夫曼树HuffmanTree又称。它是n个带权叶子

7、结点构成的所有二叉树中，带权途径长度WPL。7、树的先序遍历经过如下：若树为空，则进行空操作；若树非空，则访问树的；依次先序遍历树的。三、应用题1、给定权值集合1,4,2,6,9,构造相应的哈夫曼树,并计算它的带权途径长度。2、对关键字序列10，6，3，2，5，4，构造一棵平衡二叉排序树并画图要求画出建树经过。3、设有一个有序文件，其中各记录的关键字为1，2，3，4，5，6，7，8，9，10，11，12，13，14，15，当用折半查找算法查找关键字为3，8，19时，其比拟次数分别为多少？4、对有五个结点A,B,C,D,E的图的邻接矩阵，?050010200600103010001画出逻辑图；2

8、画出图的十字链表存储；3基于邻接矩阵写出图的深度、广度优先遍历序列；4计算图的关键途径。作业题三一、单项选择题1串的长度是指A串中所含不同字母的个数B串中所含非空格字符的个数C串中所含不同字符的个数D串中所含字符的个数2设有数组Ai,j，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开场顺序存放，当用以列为主存放时，元素A5，8的存储首地址为()。A.BA+141B.BA+180C.BA+222D.BA+2253算法分析的两个主要方面是。A空间复杂性和时间复杂性B正确性和简明性C可读性和文档性D数据复杂性和程序复杂性4算法分析的目的是。当前位置：文档视界数据

9、构造专升本模拟题及参考答案讲课教案数据构造专升本模拟题及参考答案讲课教案当前位置：文档视界数据构造专升本模拟题及参考答案讲课教案数据构造专升本模拟题及参考答案讲课教案作业题四一、单项选择题1.将两个各有n个元素的有序表归并成一个有序表，其最少得比拟次数是。AnB2n-1C2nDn-12.一个有n个顶点的无向连通图，它所包含的连通分量个数为。A0B1CnDn+13.数据文件的基本操作中最重要的操作是。A插入B删除C修改D检索4.对关键码序列28，16，32，12，60，2，5，72快速排序，从小到大一次划分结果为。A(2,5,12,16)26(60,32,72)B(5,16,2,12)28(60

10、,32,72)C(2,16,12,5)28(60,32,72)D(5,16,2,12)28(32,60,72)5.假如只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用方法最快。A堆排序B快速排序C插入排序D归并排序6算法分析的目的是。A找出数据构造的合理性B研究算法中的输入和输出的关系C分析算法的效率以求改良D分析算法的易懂性和文档性7.二叉树的第I层上最多含有结点数为A2IB2I-1-1C2I-1D2I-18循环队列存储在数组A中，长度为m，则入队时的操作为。A.rear=rear+1B.rear=(rear+1)mod(m-1)C.rear=(rear+1)modm

11、D.rear=(rear+1)mod(m+1)9.广义表知足Head(A)=Tail(A)，则A为。ABC，D，10.在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为个。A3B4C5D6二、填空题1.在一个循环队列中，队首指针指向队首元素的_。2.数组中每一个数据通常称为，用下标区分，其中下标的个数由数组的决定。3.一个图的表示法是唯一的，而表示法是不唯一的。4.在一个10阶的B-树上，每个数根结点中所含的关键字数目最多允许个，最少允许个5.对关键字序列52，80，63，44，48，91进行一趟快速排序之后的得到结果为。10.高度为1的平

12、衡二叉树的结点数至少有_个，高度为2的平衡二叉树的结点数至少有_个。三判定1.顺序存储构造属于静态构造，链式构造属于动态构造。2.即便对不含一样元素的同一输入序列进行两组不同的、合法的入栈和出栈组合操作，所得的输出序列也一定一样。3.带权无向图的最小生成树必是唯一的。4.B-树和B+树都可用于文件的索引构造。5.在用堆排序算法排序时，假如要进行增序排序，则需要采用大根堆。四、应用题1.形式串p=abaabcac的next函数值序列为多少？2.设二维数组A56的每个元素占4个字节，已知LOCa0,0=1000，A共占多少个字节？A的终端结点a4,5的起始地址为多少？按行和按列优先存储时，a2,5

13、的起始地址分别为多少？3.设a,b,c,d,e五个字符的编码分别为1,2,3,4,5，并设标识符依下面次序出现：ac,bd,aa,be,ab,ad,cd,bc,ae,ce。要求用哈希Hash方法将它们存入具有10个位置的表中。1将上述关键字标识符构造一个哈希函数，使得发生冲突尽可能地少；2线性探测再散列法解决冲突。写出上述各关键字在表中位置。4.给定一个关键字序列24，19，32，43，38，6，13，22，请写出快速排序第一趟的结果；堆排序时所建的初始堆；归并排序的全经过。然后回答上述三中排序方法中那一种方法使用的辅助空间最少？在最坏情况下那种方法的时间复杂度最差？作业题五一、单项选择题1.

14、一组记录的关键码为46，79，56，38，40，84，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为。A(38,40,46,56,79,84)B(40,38,46,79,56,84)C40,38,46,56,79,84)D(40,38,46,84,56,79)2广义表A=(a,b,(c,d),(e,(f,g),则下面式子的值为。GetHead(GetTail(GetHead(GetTail(GetTail(A)A.(g)B.(d)C.cD.d3对于有n个结点的二叉树,其高度为Anlog2nBlog2nC?log2n?+1D不确定4.如下图，给出由7个顶点组成的无向图。从顶点1出发

15、，对它进行深度优先搜索得到的顶点序列是。A1354267B1347625C1534276D12476535.采用邻接表存储的图，其深度优先遍历类似于二叉树的。A中序遍历B先序遍历C后序遍历D按层次遍历6.已知有向图G=(V,E)，其中V=V1,V2,V3,V4,V5,V6,V7，E=,G的拓扑序列是。AV1,V3,V4,V6,V2,V5,V7BV1,V3,V2,V6,V4,V5,V7CV1,V3,V4,V5,V2,V6,V7DV1,V2,V5,V3,V4,V6,V77.顺序查找法适用于查找顺序存储或链式存储的线性表，平均比拟次数为。在此假定N为线性表中结点数，且每次查找都是成功的。AN+1B2

16、log2NClog2NDN8.下面关于m阶B树讲法正确的是。每个结点至少有两棵非空子树；树中每个结点至多有m一1个关键字；所有叶子在同一层上；当插入一个数据项引起B树结点分裂后，树长高一层。ABCD9.已知一个线性表38，25，74，63，52，48，假定采用h(k)=k%7计算Hash地址进行散列存储，若利用链地址法处理冲突，则在该Hash表上进行查找的平均查找长度为。A1.0B7/6C4/3D3/210.在排序算法的施行经过中，使用辅助存储空间为O1的有。A简单排序法B.快速排序法C归并排序法D.基数排序法二、填空题1.nn大于1个结点的各棵树中，其中深度最大的那棵树的深度是n，它共有_个

17、叶子结点和_个非叶子结点。2.设一棵后序线索树的高是50，结点x是树中的一个结点，其双亲是结点y,y的右子树高度是60，x是y的左孩子。则确定x的后继最多需经过_中间结点不含后继及x本身3.高度为2第2层为叶子的3阶B-树中，最多有_个关键字。4.分别采用堆排序，快速排序，冒泡排序和归并排序，对初态为无序的表，则平均情况下最省时间的是_算法。5.简单项选择择排序和起泡排序中比拟次数与序列初态无关的算法有_。6.串的链式存储构造是将存储区域分成一系列大小一样的结点,每个结点有两个域域和域。其中域用于用于存放数据，域用于存放下一个结点的指针三判定1.顺序存储的线性表能够随机存取。2.即便对不含一样元素的同一输入序列进行两组不同的、合法的入栈和出栈组合操作，所得的输出序列也一定一样。3.十字链表是无向图的一种存储构造。