长沙理工大学数据结构六套卷分类汇总.docx

数据结构（C语言版）2013-2014六套卷分类汇总目录单选题1填空题6判断题10应用题11算法设计题15简答题17名词解释18单选题01下面关于线性表的叙述错误的是（ ）。A 线性表采用顺序存储必须占用一片连续的存储空间 B 线性表采用链式存储不必占用一片连续的存储空间 C 线性表采用链式存储便于插入和删除操作的实现 D 线性表采用顺序存储便于插入和删除操作的实现 【答案】D02单链表的存储密度（ ）。 A 大于1 B 等于1 C小于1 D 不能确定 【答案】C03 设输入序列为1、2、3、4、5、6，则通过栈的作用后可以得到的输出序列为（ ）。A 5，3，4，6，1，2 B 3，2，5，6，4，1 C 3，1，2，5，4，6 D 1，5，4，6，2，3【答案】B04若串S=SOFTWARE，其子串的数目最多是：（ ） 。 A35 B36 C37 D38 【答案】C05二叉排序树中，最小值结点的（ ）。A 左指针一定为空 B 右指针一定为空C 左、右指针均为空 D 左、右指针均不为空【答案】A06在散列函数H(k)= k mod m中，一般来讲，m应取（ ）。A 奇数 B 偶数 C 素数 D 充分大的数【答案】C07用直接插入排序对下面四个序列进行由小到大排序，元素比较次数最少的是（ ）。 A 94, 32, 40, 90, 80, 46, 21, 69 B 21, 32, 46, 40, 80, 69, 90, 94C 32, 40, 21, 46, 69, 94, 90, 80 D 90, 69, 80, 46, 21, 32, 94, 40【答案】B08使用双链表存储线性表，其优点是可以（ ）。A 提高查找速度 B 更方便数据的插入和删除C 节约存储空间 D 很快回收存储空间【答案】B09链表不具有的特点是（ ）A.不必事先估计存储空间 B.可随机访问任一元素 C.插入删除不需要移动元素 D.所需空间与线性表长度成正比 【答案】 B10从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较（ ）个结点。 A n B n/2 C (n-1)/2 D (n+1)/2 【答案】D11在C或C+语言中，一个顺序栈一旦被声明，其占用空间的大小（ ）。 A已固定 B不固定 C可以改变 D动态变化 【答案】A12 两个字符串相等的充要条件是（ ）。 A 两个字符串的长度相等 B 两个字符串中对应位置上的字符相等 C 同时具备(A)和(B)两个条件 D 以上答案都不对 【答案】C13设某二叉树中度数为0的结点数为N0，度数为1的结点数为Nl，度数为2的结点数为N2，则下列等式成立的是（ ）。 A N0=N1+1 B N0=Nl+N2 C N0=N2+1 D N0=2N1+l 【答案】C14在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为( ) Ae B2e Cn2e Dn22e 【答案】D15设F是由T1、T2和T3三棵树组成的森林，与F对应的二叉树为B，T1、T2和T3的结点数分别为N1、N2和N3，则二叉树B的根结点的左子树的结点数为（ ）。 A N1-1 B N2-1 C N2+N3 D N1+N3【答案】 A16设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是（ ）。 A 空或只有一个结点 B 高度等于其结点数 C 任一结点无左孩子 D 任一结点无右孩子 【答案】D17在堆排序和快速排序中，如果从平均情况下排序的速度最快的角度来考虑应最好选择（ ）排序，如果从节省存储空间的角度来考虑则最好选择（ ）排序。 【答案】快速 堆18设有以下四种排序方法，则（ ）的空间复杂度最大。 A 冒泡排序 B 快速排序 C 堆排序 D 希尔排序【答案】B19数据结构中，与所使用的计算机无关的是数据的（ ）A存储结构 B物理结构 C逻辑结构 D物理和存储结构【答案】C20数据的基本单位是（ ）。 A. 数据结构 B. 数据元素 C. 数据项 D. 文件【答案】B21已知一个顺序存储的线性表，设每个结点占m个存储单元，若第一个结点的地址为B，则第i个结点的地址为（ ）。A B+(i-1)*m BB+i*m C B-i*m D B+(i+1)*m 【答案】A22若链表中最常用的操作是在最后一个结点之后插入一个结点和删除第一个结点，则采用（ ）存储方法最节省时间。 A 单链表 B 带头指针的单循环链表 C 双链表 D 带尾指针的单循环链表【答案】D23在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印缓冲区，该缓冲区应该是一个（ ）结构。A 栈 B队列 C 数组 D线性表 【答案】B24用链接方式存储的队列，在进行插入运算时( ). A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改 【答案】D25以下论述正确的是（ ）。 A空串与空格串是相同的 Btel是Teleptone的子串 C空串是零个字符的串 D. 空串的长度等于1 【答案】C26对于完全二叉树中的任一结点，若其右分支下的子孙的最大层次为h，则其左分支下的子孙的最大层次为（ ）。 A h B h+1 C h或h+1 D 任意【答案】C27设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（ ）个空指针域。 A 2m-1 B 2m C 2m+1 D 4m 【答案】B28设某有向图中有n个顶点，则该有向图对应的邻接表中有（ ）个表头结点。 A n-1 B n C n+1 D 2n-1 【答案】B29二叉排序树中左子树上所有结点的值均（ ）根结点的值。 A C = D != 【答案】A30静态查找与动态查找的根本区别在于（ ）。A 它们的逻辑结构不一样 B 施加在其上的操作不同C 所包含的数据元素的类型不一样 D 存储实现不一样【答案】B31散列技术中的冲突指的是（ ）。A 两个元素具有相同的序号 B 两个元素的键值不同，而其他属性相同C 数据元素过多 D 不同键值的元素对应于相同的存储地址【答案】D32一组记录的关键码为46, 79, 56, 38, 40, 84，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（ ）。A 40, 38, 46, 56, 79, 84 B 40, 38, 46, 79, 56, 84C 40, 38, 46, 84, 56, 79 D 84, 79, 56, 46, 40, 38【答案】A33对一个算法的评价，不包括如下（ ）方面的内容。 A健壮性和可读性 B并行性 C正确性 D时空复杂度【答案】B34设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为（ ）。 A O(log2n) B O(1) C O(n2) D O(n) 【答案】D35在下列链表中不能从当前结点出发访问到其余各结点的是（ ）。A双向链表 B单循环链表 C单链表 D双向循环链表 【答案】C36从一个栈顶指针为top的链栈中删除一个结点时，用x保存被删除的结点，应执行下列 ( )命令。 Ax=top;top=top-next; Btop=top-next;x=top-data; Cx=top-data; Dx=top-data;top=top-next; 【答案】D37设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为（ ）。 A top=top+1; B top=top-1; C top-next=top; D top=top-next; 【答案】D38字符串的长度是指（ ）。 A 串中不同字符的个数 B 串中不同字母的个数 C 串中所含字符的个数 D 串中不同数字的个数 【答案】C39数组的逻辑结构不同于下列（ ）的逻辑结构。 A 线性表 B 栈 C 队列 D 树 【答案】D40下图为由7个顶点组成的无向图。从顶点1出发，对它进行广度优先遍历得到的顶点序列是_。 A、1534267 B、1726453 C、1354276 D、1247653 【答案】 C41下列各种排序算法中平均时间复杂度为O(n2)是（ ）。 A 快速排序 B 堆排序 C 归并排序 D 冒泡排序 【答案】D42对线性表，在下列哪种情况下应当采用链表表示？( ) A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 【答案】B43若用一个大小为6的数组来实现循环队列，且当前front和rear的值分别为3和0，当从队列中删除一个元素，再加入两个元素后，front和rear的值分别为( )。 A5和1 B4和2 C2和4 D1和5 【答案】B44 设一棵三叉树中有2个度数为1的结点，2个度数为2的结点，2个度数为3的结点，则该三叉链权中有（ ）个度数为0的结点。 A 5 B 6 C 7 D 8 【答案】C45任何一棵二叉树的叶子结点在前序、中序、后序遍历序列中的相对次序（ ）。A 肯定不发生改变 B 肯定发生改变 C 不能确定 D 有时发生变化【答案】A46设某无向图中有n个顶点e条边，则建立该图邻接表的时间复杂度为（ ）。 A O(n+e) B O(n2) C O(ne) D O(n3) 【答案】A47下面关于工程计划的AOE网的叙述中，不正确的是（ ）A 关键活动不按期完成就会影响整个工程的完成时间B 任何一个关键活动提前完成，那么整个工程将会提前完成C 所有的关键活动都提前完成，那么整个工程将会提前完成D 某些关键活动若提前完成，那么整个工程将会提前完【答案】B48下列命题正确的是（ ）。A 一个图的邻接矩阵表示是唯一的，邻接表表示也唯一B 一个图的邻接矩阵表示是唯一的，邻接表表示不唯一C 一个图的邻接矩阵表示不唯一的，邻接表表示是唯一D 一个图的邻接矩阵表示不唯一的，邻接表表示也不唯一【答案】B49 设某散列表的长度为100，散列函数H(k)=k % P，则P通常情况下最好选择（ ）。 A 99 B 97 C 91 D 93 【答案】B50设一组初始记录关键字序列为(Q，H，C，Y，P，A，M，S，R，D，F，X)，则按字母升序的第一趟冒泡排序结束后的结果是（ ）。A F，H，C，D，P，A，M，Q，R，S，Y，X B P，A，C，S，Q，D，F，X，R，H，M，Y C A，D，C，R，F，Q，M，S，Y，P，H，X D H，C，Q，P，A，M，S，R，D，F，X，Y【答案】D51线性表的链式链式存储结构是一种（ ）的存储结构。 A、随机存取 B、顺序存取 C、索引存取 D、HASH存取 【答案】B52设计一个判别表达式中左右括号是否配对的算法，采用（ ）数据结构最佳A 顺序表 B 栈 C 队列 D 链表【答案】B53设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5、e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的顺序是e2、e4、e3、e6、e5、e1，则栈S的容量至少应该是（）。A 6 B 4 C 3 D 2【答案】C54设数组datam作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front值为（ ） Afront=front+1 Bfront=(front+1)%(m-1) Cfront=(front-1)%m Dfront=(front+1)%m【答案】D55广义表(a, b, (c, (d)的表尾是（ ）。A (d) B (c,(d) C b D (b,(c,(d) 【答案】D56线索二叉树中某结点R没有左孩子的充要条件是（ ）。A R.lchild=NULL B R.ltag=0 C R.ltag=1 D R.rchild=NULL【答案】C57 设一棵完全二叉树中有65个结点，则该完全二叉树的深度为（ ）。 A 8 B 7 C 6 D 5 【答案】B58G是一个非连通无向图，共有28条边，则该图至少有（ ）个顶点。A 6 B 7 C 8 D 9 【答案】D59设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。A.5 B.6 C.7 D.8 【答案】A60散列表的地址区间为0-17,散列函数为H(K)=K mod 17。采用线性探测法处理冲突，并将关键字序列26，25，72，38，8，18，59依次存储到散列表中。存放元素59需要搜索的次数是（ ）A、 2 B、 3 C、 4 D、 5【答案】C61 设有5000个元素，希望用最快的速度挑选出前10个最大的，采用（ ）方法最好。A快速排序 B堆排序 C希尔排序 D 归并排序【答案】B填空题1顺序表中访问任意一个结点的时间复杂度均为 。【答案】 0(1)2在单链表中要在已知结点*P之前插入一个新结点，需找到*P的直接前趋结点的地址，其查找的时间复杂度为 。【答案】0(n)3在有n个元素的栈中，进栈操作的时间复杂度为 ，出栈操作的时间复杂度为 。【答案】0(1) 0(1)4在串 S=structure 中，以 t 为首字符的子串有 个。【答案】125已知线性表A采用顺序存储结构，每个元素占用4个存储单元，第9个元素的地址为144，则第一个元素的地址是 。【答案】1126设哈夫曼树中共有n个结点，则该哈夫曼树中有 个度数为1的结点。【答案】07广义表(a,(a,b),d,e,(i,j),k)的长度是 ，深度是 。 【答案】5 38一棵有n个结点的满二叉树有 个分支结点和 个叶子。【答案】(n-1)/2 (n+1)/29完全二叉树总结点数为N，若N为奇数，则叶子结点数为 ；若N为偶数，则叶子结点数为 。【答案】（N+1）/2 N/210设一棵二叉树中有3个叶子结点，有8个度为1的结点，则该二叉树中总的结点数为 【答案】1311具有n个结点的完全二叉树若按层次从上到下、从左到右对其编号（根结点为1)，则编号最大的叶子结点序号是 ，编号最小的叶子结点序号是 。【答案】n n/2+1 12设二叉树中度数为0的结点数为50，度数为1的结点数为30，则该二叉树中总共有 个结点数。【答案】12913若G为有向图，则至少有 条边，至多有 条边 【答案】 0 n(n-1)14顺序查找技术适合于存储结构为 的线性表【答案】顺序存储和链接存储15在各种查找方法中，平均查找长度与结点个数无关的查找方法是 。【答案】散列查找（哈希法）16假定一个数列25，43，62，31，48，56，采用的散列函数为H(k)=k mod 7，则元素48的同义词是 。【答案】6217对于键值序列（12，13，11，18，60，15，7，18，25，100），用筛选法建堆，必须从键值为 的结点开始。【答案】6018对一个需要经常进行插入和删除操作的线性表，采用 存储结构为宜。 【答案】链式19不论是顺序存储结构的栈还是链式存储结构的栈，其入栈和出栈操作的时间复杂度均为 。 【答案】0（1）20完全二叉树中第5层上最少有 个结点，最多有 个结点。【答案】1 1621在一个具有n个顶点的无向完全图中，包含有 条边，在一个具有n个顶点的有向完全图中，包含有 条边。 【答案】n(n-1)/2 n(n-1)22在无向图的邻接矩阵中，第i行（列）中“1”的个数是第i个顶点的 ，矩阵中“1”的个数的一半是图中的 。 【答案】度 边数23表示一个有100个顶点，1000条边的有向图的邻接矩阵有 个非零矩阵元素。【答案】100024实现数据结构的基本存储方法有： ， 。【答案】顺序存储结构 链接存储结构25for(i=1，t=1，s=0；i0）个结点的满二叉树共有 个叶子结点和 个非终端结点。【答案】2i-1 (n+1)/2 (n-1)/235假设线性表的长度为n，则在最坏情况下，冒泡排序需要的比较次数为 【答案】n(n-1)/236评价基于比较的排序算法的时间性能，主要标准是 和 。【答案】关键码的比较次数 记录的移动次数37在双向链表中，每个结点都有两个指针域，它们一个指向其 结点，另一个指向其 结点。 【答案】前趋 后继38由两个栈共享一个存储空间的好处是 【答案】节省存储空间，降低上溢发生的机率39设循环队列存放在向量sq.data0:M中，若用牺牲一个单元的办法来区分队满和队空（设队尾指针sq.rear）,则队满的条件为 。【答案】(sq.rear+1)%(M+1)=sq.front40设二叉树中结点的两个指针域分别为lchild和rchild，则判断指针变量p所指向的结点为叶子结点的条件是 。【答案】p-lchild=0&p-rchild=041深度为k的完全二叉树中最少有 个结点。【答案】2k-142设一棵二叉树的前序序列为ABC，则有 种不同的二叉树可以得到这种序列。 【答案】543对于一棵具有n个结点的二叉树，用二叉链表存储时，其指针总数为 个，其中 个用于指向孩子， 个指针是空闲的。【答案】2n n-1 n+144度不为 的结点称为分支结点或非终端结点。树中各结点度的 称为树的度。【答案】零 最大值45设有向图G用邻接矩阵Ann作为存储结构，则该邻接矩阵中第i行上所有元素之和等于顶点i的 ，第i列上所有元素之和等于顶点i的 。【答案】出度 入度46N个顶点的强连通图的边数至少有 【答案】N47 数据的物理结构主要包括 和 两种情况。【答案】顺序存储结构、链式存储结构48算法的空间复杂度是指 【答案】执行过程中所需要的辅助存储空间49顺序存储结构中数据元素之间的逻辑关系是由 表示的，链接存储结构中的数据元素之间的逻辑关系是由 表示的。【答案】存储位置 指针50若算法中的语句执行次数之和为 T ( n )= 525 n +4 n log n ，则算法的时间复杂度是 。【答案】O（ n log n ）51设无向图G中有n个顶点e条边，所有顶点的度数之和为m，则e和m有 关系。【答案】m=2e52对n个元素进行起泡排序，在 情况下比较的次数最少，其比较次数为 。在 情况下比较次数最多，其比较次数为 。【解答】正序，n-1，反序，n(n-1)/253快速排序算法的空间复杂度平均情况下为 ，最坏的情况下为 。【答案】O(nlog2n)， O(n)54树形结构结构中的元素之间存在 的关系【答案】一对多判断题01线性结构的基本特征是：每个元素有且仅有一个直接前驱和一个直接后继。（X）02稀疏矩阵压缩存储后，必会失去随机存取功能。（）03由树转化成二叉树，该二叉树的右子树不一定为空。（X）04稀疏矩阵的压缩存储可以用一个三元组表来表示稀疏矩阵中的非0元素。（）05对任意一个图，从某顶点出发进行一次深度优先或广度优先遍历，可访问图的所有顶点。（X）06当向二叉排序树中插入一个结点，则该结点一定成为叶子结点。（）07数据的逻辑结构和数据的存储结构是相同的。（X）08数据的存储结构是数据的逻辑结构的存储映像。（）09线性表链式存储的特点是可以用一组任意的存储单元存储表中的数据元素。（） 10线性表的逻辑顺序和存储顺序总是一致的。（X）11非空的双向循环链表中任何结点的前驱指针均不为空。（）12子串“ABC”在主串“AABCABCD”中的位置为2。（）13数组是一种复杂的数据结构，数组元素之间的关系既不是线性的，也不是树形的。（X）14用邻接矩阵作为图的存储结构时，则其所占用的存储空间与图中顶点数无关而与图中边数有关。（X）15无向图的邻接矩阵一定是对称的，有向图的邻接矩阵一定是不对称的（X）16当装填因子小于1时，向散列表中存储元素时不会引起冲突。（X）17散列技术的查找效率主要取决于散列函数和处理冲突的方法。（X）18顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。（X）19在线性表的链式存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。（）20链表的每个结点都恰好包含一个指针域。（X） 21有向图的邻接表和逆邻接表中表结点的个数不一定相等。（X）22对连通图进行深度优先遍历可以访问到该图中的所有顶点。（）23用邻接矩阵存储图，所占用的存储空间大小只与图中顶点个数有关，而与图的边数无关。（）24分块查找的平均查找长度不仅与索引表的长度有关，而且与块的长度有关。（）25设初始记录关键字基本有序，则快速排序算法的时间复杂度为O(nlog2n)。（X）26每种数据结构都具备三个基本操作：插入、删除和查找。（X）27对链表进行插入和删除操作时不必移动链表中结点。（） 28一个栈的输入序列为：A，B，C，D，可以得到输出序列：C，A，B，D。（X）29如果两个串含有相同的字符，则说明它们相等。（X）30在线索二叉树中，任一结点均有指向其前趋和后继的线索。（X）31带权无向图的最小生成树是唯一的。（X）32稀疏矩阵压缩存储后，必会失去随机存取功能。（）33如果某个有向图的邻接表中第i条单链表为空，则第i个顶点的出度为零。（）34向二叉排序树中插入一个结点需要比较的次数可能大于该二叉树的高度。（X）35 逻辑结构与数据元素本身的内容和形式无关。（）应用题1已知某字符串S中共有8种字符，各种字符分别出现2次、1次、4次、5次、7次、3次、4次和9次，对该字符串用0，1进行前缀编码，问该字符串的编码至少有多少位。【答案】以各字符出现的次数作为叶子结点的权值构造的哈夫曼编码树如图所示。其带权路径长度=25+15+34+53+92+43+43+72=98，所以，该字符串的编码长度至少为98位。2已知关键码序列为（Jan, Feb, Mar, Apr, May, Jun, Jul, Aug, Sep, Oct, Nov, Dec），散列表的地址空间为016，设散列函数为H(x)= i/2 (取下整数) ，其中i为关键码中第一个字母在字母表中的序号，采用链地址法处理冲突构造散列表，并求等概率情况下查找成功的平均查找长度。【答案】H(Jan)=10/2=5, H(Feb)=6/2=3, H(Mar)=13/2=6, H(Apr)=1/2=0H(May)=13/2=6, H(Jun)=10/25, H(Jul)=10/25, H(Aug)=1/2=0H(Sep)=19/2=8, H(Oct) =15/2=7, H(Nov) =14/2=7, H(Dec) =4/2=2采用链地址法处理冲突，得到的开散列表如下： 平均查找长度=(17+24+31)/12=18/123分析下面各程序段的时间复杂度（1） s1(int n) int p=1,s=0; for (i=1;i=n;i+) p*=i;s+=p; return(s);（2） s2(int n)x=0;y=0; For (k=1;k=n;k+)x+; For (i=1;i=n;i+) For (j=1;j=n;j+)y+;【答案】0（n） 0(n)4下述算法的功能是什么?（1）【答案】（1）返回结点*p的直接前趋结点地址。 （2）交换结点*p和结点*q（p和q的值不变）。5对给定的一组权值W（5，2，9，11，8，3，7），试构造相应的哈夫曼树，并计算它的带权路径长度。【答案】构造的哈夫曼树如图所示。树的带权路径长度为：WPL=24+34+53+73+83+92+112=1206已知散列函数H(k)=k mod 12，键值序列为(25, 37, 52, 43, 84, 99, 120, 15, 26, 11, 70, 82)，采用链表法处理冲突，试构造散列表。【答案】H(25)=1, H(37)=1, H(52)=4, H(43)=7, H(84)=0, H(99)=3,H(120)=0, H(15)=3, H(26)=2, H(11)=11, H(70)=10, H(82)=10构造的开散列表如下：7分析下面各程序段的时间复杂度（1） for (i=0;in;i+) for (j=0;jm;j+) Aij（2） s=0; for (i=0;in;i+) for (j=0;jnext-data=X) printf (“值为x的结点是第一个结点，没有直接前趋结点可以删除”); return; for (;p-next-data!=X; q=p; p=p-next); / 删除指针p所指向的结点 q-next=p-next; delete p;3. 设计判断单链表中元素是否是递增的算法。【答案】int isriselk(lklist *head)if(head=0|head-next=0) return(1);else for(q=head,p=head-next; p!=0; q=p,p=p-next)if(q-datap-data) return(0);return(1);4.编写算法，要求输出二叉树后序遍历序列的逆序。【答案】要想得到后序的逆序，只要按照后序遍历相反的顺序即可，即先访问根结点，再遍历根结点的右子树，最后遍历根结点的左子树。void P