DS试题10套00.doc

第一部分选择题一、单项选择题（本大题共20小题，每小题1分，共20分） 1计算机算法指的是，它必须具备输入、输出和【】 A计算方法 B排序方法 C解决问题的有限运算步骤 D程序设计方法 2下列算法的时间复杂度是【】 for（i=0；il）个节点的完全二叉树中，节点i（2in）的左孩子节点是【】 A2i B2il C不存在 D是2i-l13在一个图中，所有顶点的度数之和等于图的边数的几倍。【】 A1/2 B1 C2 D414在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是【】 A希尔排序 B冒泡排序 C插入排序 D选择排序15设有1000个无序的元素，希望以最快的速度挑选出其中前10个最大的元素，最好选用的排序法是【】 A起泡排序 B快速排序C堆排序 D基数排序16二分查找要求节点【】 A有序、顺序存储 B有序、链接存储 C无序、顺序存储 D无序、链接存储17VSAM文件采用哪种索引结构【】 A多级 B动态 C随机 D。静态18散列文件中的记录通常是成组存放的，存放一组数据的存储单位称为【】 A扇区 B柱面 C磁道 D桶19索引表是指示逻辑记录和什么之间对应关系的表【】 A物理记录 B元素 C关键字 D结构20有8个节点的无向连通图最少有多少条边【】 A14 B。28 C56 D112第二部分非选择题二、填空题（本大题共15小题，每空1分，井20分）l数据结构的实质一般包括三个方面的内容：数据的，数据的及数据的运算。2在双链表中每个节点有两个指针域，一个指向，另一个指向。3当链满时再做进栈运算将产生。4栈S经过运算InitStake(S); Push(S,a); Push(S,b); 后StakeTop(S)的值是。5通常在程序中使用的串可分为两种，即和。6广义表（a），(b), J, (d)的表头是，表尾是。7由一棵二叉树的前序序列和可唯一确定这棵二叉树。8高度为k的完全二叉树至少有个节点。9如果n个顶点的图是一个环，则它有棵生成树。10n个顶点e条边的图若采用邻接表存储，则空间复杂度为。11在排序前，关键字值相等的不同记录间的前后相对位置保持的排序方法称为稳定的排序方法。12对于n个记录的集合进行归并排序，所需要的平均时间为。13文件有四种基本的存储结构组织方式：顺序组织、索引组织、和。14对二叉排序树进行的查找方法是用待查的值与根节点的键值相比，若比根小则继续在子树中找。15两个不同的元素存入同一个散列表，当这两个元素的散列函数值相同时，称为。三、名词解释（本大题共5小题，每题3分，共15分）l循环链表2队列3三角矩阵4有序树5生成树四、简答题（本大题共5小题，每题5分，共25分）l简述线形结构与非线形结构的不同点。2对于一个栈，如果输入项序列由A，B，C所组成，试给出全部可能的输出序列。3简述静态分配的顺序串与动态分配的顺序串的区别。4写出下列二叉树的前根、中根、后根排序顺序。 5给出如下图所示的无向图G的邻接矩阵和邻接表两种存储结构。五、应用题（本大题共2小题，每题10分，共20分）1设有链式存储结构的二叉树，计算其中有双后继节点的节点的个数。2以先查找插入位置，后插入的方法，在静态链表上实现直接插入排序。 设静态链表是用一维结构数组实现的。数据结构模拟试题（一）参考答案 一、单项选择题 1C 2。B 3A 4。B 5。C 6。B 7。A 8 C 9。D 10。A 11。A 12。 C 13。A 14。D 15C 16。A 17B 18。D 19。A 20。C 二、填空题 1逻辑结构 存储结构 2。前趋节点 后续节点 3。上溢 4。B 5串变量 串常量 6。（a）(b), J, (d) 7。中序序列 82k-1 9。n 10O（ne） 11。不变 12。O（log2n） 13散列组织 链组织 14。左 15。冲突 三、名词解释 1循环链表：是一种首位相连的链表。单循环链表形成一个next环，而双循环链表形成next链环和prior链环。 2队列：是一种运算受限的单链表。它只允许在表的一端进行插入，而在另一端进行删除。允许删除的一端称为队头，允许插入的一端称为队尾。 3三角矩阵：主对角线以上或以下的元素（不包括对角线）均为常数的矩阵。 4有序树：树中节点的各子树看成是从左至有依次有序且不能交换。 5生成树：连通图G的一个子图如果是一棵包含G的所有顶点的树，则该子图称为G的生成树。四、简答题 1线形结构的逻辑特征是除开始节点和终端节点外，其余每个节点只有一个直接前趋和一个直接后继，即节点间存在一对一的关系；而非线形结构的逻辑特征是一个节点可以有多个直接前趋和直接后继，即节点间存在多对多的关系。 2本题利用栈的“后进先出”特点，有如下几种情况： A进 A出 B进 B出 C进 C出 产生输出序列ABC A进 A出 B进 C进 C出 B出 产生输出序列ACB A进 B进 B出 A出 C进 C出 产生输出序列BAC A进 B进 B出 C进 C出 A出 产生输出序列BCA A进 B进 C迸 C出 B出 A出 产生输出序列CBA 不可能产生输出序列CAB。 3程序运行前被分配以一个给定大小的数组空间的顺序串称为静态顺序串。在程序运行过程中，动态分配空间可以链表形式存在的顺序串称为动态顺序串，静态串存在于内存一片连续的数据区中，动态串存在与内存堆中。 4前根排序：ABDEHCFI 中根排序：DBHEACIF 后根排序：DHEBIFCA 5邻接矩阵如下； 邻接表如下： 五、应用题 lint twochild（bt tree） int numl，num2； if (tree=null) return(0); else if（tree一left != null & tree一right != null） return(1); else numltwochild（tree一left）； num2= twochild（free一right）； return（numlnum2）； 2设静态链表是用一维结构数组实现的： struct element int data； int curs； statiin（element r） int I, p； element *p； r0.curs=0； r0.data=0； for(I=1；Idata=p-data; r-next=c; p=p-next; r=c; new(c); c-data=p-data; r-next=c; q=q-next; r=c; r-next=null; s=s-next; return（s）； 2vo