数据结构练习测试题附答案

第页数据结构练习测试题附答案1.在下面的排序方法中,辅助空间为O(n)的排序方法是()。A、快速排序B、直接插人排序C、归并排序D、堆排序【正确答案】：C2.下面关于串‎的的叙述中‎，哪一个是不‎正确的？（）A、串是字符的‎有限序列B、空串是由空‎格构成的串‎C、模式匹配是‎串的一种重‎要运算D、串既可以采‎用顺序存储‎，也可以采用‎链式存储【正确答案】：B3.下面说法正确的是()。A、广义表的表头可以是一个广义表,也可以是一个原子B、广义表的表头总是一个原子C、广义表的表尾可以是一个广义表,也可以是一个原子D、广义表的表尾总是一个原子【正确答案】：A4.若记录的存储地址与其关键字之间存在某种函数关系,则称这种存储结构为()。A、顺序存储结构B、链式存储结构C、索引存储结构D、散列存储结构【正确答案】：D5.把一棵树转换为二叉树后，这棵二叉树的形态是()。A、唯一的B、有2种C、有多种，但根结点都没有左孩子D、有多种，但根结点都没有右孩子【正确答案】：A6.链表不具备的特点是()。A、插人删除不需要移动元素B、不必事先估计存储空间C、可随机访问任一节点D、所需空间与其长度成正比【正确答案】：D7.n个顶点的有向图中有向边的数目最多为().A、n-lB、nC、n(n-1)/2D、n(n-1)【正确答案】：D8.对长度为12的有序表做折半查找,当查找失败时,与关键字比较的次数最多是()。A、3B、4C、5D、6【正确答案】：B9.以下哪个排序算法是稳定的？A、快速排序B、选择排序C、插入排序D、希尔排序【正确答案】：C10.设某顺序表中第一个元素的地址是Base，每个结点占m个单元，则第i个结点的地址为()。A、Base+(i-1)×mBase+(i+1)×mC、Base-i×mD、Base+i×m【正确答案】：A11.栈是一种（）的数据结构。A、先进先出B、先进后出C、后进先出D、后进后出【正确答案】：B12.长度为n的非空线性表采用顺序存储结构，在表的第i个位置插入一个数据元素，i的合法值应该是()。A、1≤i≤n-1B、0≤i≤n+1C、i>0D、1≤i≤n+1【正确答案】：D13.稀疏矩阵压缩存储的方法通常有()。A、散列和三元组B、二维数组和三维数组C、三元组和十字链表D、散列和十字链表【正确答案】：C14.链串的节点大小为1指的是()。A、用于存储串的链表长度为1B、用于存储串的链表只能存放一个字符C、链表中每个节点的数据域中存放一个字符D、以上都不对【正确答案】：C15.在下面的排序方法中,平均时间复杂度为O(n2)且是不稳定的排序方法是()。A、快速排序B、直接插入排序C、直接选择排序D、起泡排序【正确答案】：C16.若一棵二叉树具有10个度为2的节点，5个度为1的节点，则度为0的节点个数是（）A、9B、11C、15D、不确定【正确答案】：B17.下列()组序列是堆。A、(79,40,46,56,38,84)B、(84,56,79,46,38,40)C、(40,38,46,56,79,84)D、(84,38,46,40,56,79)【正确答案】：B18.将长度为m的单循环链表链接到长度为n的单循环链表之后,算法的时间复杂度最好为()。A、O(n)B、O(1)C、O(m)D、O(m+n)【正确答案】：A19.给定排序码序列为(45,89,36,40,95),采用快速排序,以第一个记录为基准记录,第一次划分的结果为()A、(36,40,45,89,95)B、(40,36,45,89,95)C、(36,40,45,95,89)D、(40,36,45,95,89)【正确答案】：B20.已知单链表上一节点的指针为p，则在该节点之后插入新节点*s的正确操作为()A、p->next=s;s->next=p->next;B、s->next=p->next;p->next=s;C、p->next=s;p->next=s->next;D、p->next=s->next;p->next=s;【正确答案】：B21.设有一个顺序栈,元素1,2,3,4,5依次进栈,如果出栈顺序是2,4,3,5,1,则栈的容量至少是()。A、1B、2C、3D、4【正确答案】：C22.非空循环单链表L中，p指针指向尾结点，则以下表达式成立的是()。A、p->next==NULLB、p==NULLC、p==LD、p->next==L【正确答案】：D23.有9个顶点的无向连通图至少有()条边。A、7B、8C、9D、10【正确答案】：B24.二叉树的第I层上最多含有结点数为（）A、2IB、2I-1-1C、2I-1D、2I-1【正确答案】：C25.在某双向链表中删除一个结点，需要改动()个指针域。A、3B、4C、1D、2【正确答案】：D26.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用()存储方式最节省时间。A、双向链表B、带头结点的双循环链表C、单循环链表D、顺序表【正确答案】：D27.线性表L=(a_1,a_2，…,a_n),下列说法正确的是()。A、每个元素都有一个直接前驱和一个直接后继B、线性表中至少有一个元素C、表中元素的排列顺序必须是由小到大或由大到小D、除第一个和最后一个元素外,其余每个元素都有且仅有一个直接前驱和一个直接后继【正确答案】：D28.在长度为n的顺序表中的第i(1=<i<=n+1)个位置上插入一个元素，需要移动的元素个数为()。A、iB、n-i+1C、n-i-1D、n-i【正确答案】：B29.设一个链表最常用的操作是在表尾插入节点和在表头删除节点,则选用下列存结构()效率最高。A、单链表B、双链表C、单循环链表D、带尾指针的单循环链表【正确答案】：D30.某顺序表的第一个元素的存储地址是500，每个元素占4个单元，则第8个元素的起始地址是()。A、516B、508C、528D、504【正确答案】：C31.()的时间性能与待排序记录的初始排列顺序无关。A、快速排序B、直接插人排序C、直接选择排序D、起泡排序【正确答案】：C32.数据结构在计算机内存中的表示是指()。A、数据的存储结构B、数据结构C、数据的逻辑结构D、数据元素之间的关系【正确答案】：A33.下面说法中正确的是()。A、串中元素的逻辑关系是一种线性关系B、串中元素只能是英文字母C、空串是非法的D、串必须由多个字符组成【正确答案】：A34.在长度为n的顺序表中的第i(1<=i<=n+1)个位置上插入一个元素，其算法时间复杂度为()。A、O(n*n)B、O(log2n)C、O(1)D、O(n)【正确答案】：D35.若用一个大小为6的数组来实现循环队列,且当前rear和front的值分别为0和3，当入队一个元素,再出队两个元素后,rear和front的值分别为()。A、1和5B、2和4C、4和2D、5和1【正确答案】：A36.已知单链表上一节点的指针为p,则删除该节点后继的正确操作语句是().A、s=p->next;p=p->next;free(s);B、p=p->next;free(p);C、s=p->next;p->next=s->next;free(s);D、p=p->next;free(p->next);【正确答案】：C37.设一个栈的输入序列是1.2,3,4,5,则下列序列中,栈的合法输出序列是()。A、51234B、45132C、43215D、35241【正确答案】：C38.在一单链表中，删除指针p所指的后继结点，以下语句正确的是()。A、p->next=p->next->next;free(p->next);B、p=p->next;C、free(p->next);p->next=p->next->next;D、s=p->next;p->next=s->next;free(s);【正确答案】：D39.在数据结构中，从逻辑上可以把数据结构分成()A、动态结构和静态结构B、紧凑结构和非紧凑结构C、线性结构和非线性结构D、内部结构和外部结构【正确答案】：C40.将带头指针的长度为m的单链表，链接到同样带头指针的长度为n的单链表末尾。该算法的时间复杂度为()。A、O(m+n)B、O(n)C、O(m)D、O(m*n)【正确答案】：B41.下面()方法可以判断出一个有向图是否有环(回路)。A、深度优先遍历B、求最短路径C、拓扑排序D、广度优先遍历【正确答案】：C42.数据结构中,在逻辑上可以把数据结构分成()。A、动态结构和静态结构B、紧凑结构和非紧凑结构C、线性结构和非线性结构D、内部结构和外部结构【正确答案】：C43.删除长度为n的顺序表中的第i(1≤i≤n)个位置上的元素,元素的移动次数为().A、n-i+lB、n-iC、iD、i-1【正确答案】：B44.串的长度是‎指（）A、串中所含不‎同字母的个‎数B、串中所含字‎符的个数C、串中所含不‎同字符的个‎数D、串中所含非‎空格字符的‎个数【正确答案】：B45.设一组记录的关键字序列为(19,14,23,1.68,20,84,27,55),散列函数为H(key)=key%11,采用链地址法解决冲突,散列地址为1的链表中有()个记录A、0B、1C、2D、3【正确答案】：C46.树的先根遍历序列等同于与该树对应的二叉树()A、前序序列B、中序序列C、后序序列D、层序序列【正确答案】：A47.哈希表通过（）来实现高效的查找操作。A、散列函数B、排序算法C、遍历操作D、顺序存储【正确答案】：A48.在完全二叉树中，若一个结点是叶结点，则它没（）。A、左子结点B、右子结点C、左子结点和右子结点D、左子结点，右子结点和兄弟结点【正确答案】：C49.设森林F中有三棵树，三棵树的节点个数分别为M_1、M_2和M_3。与森林F对应的二叉树根节点的右子树上的节点个数是()。A、M_1B、M_1+M_2C、M_3D、M_2+M_3【正确答案】：D50.在长度为n的顺序表中删除第i(1<=i<=n)个位置上的元素，需要移动的元素个数为()。A、n-i-1B、iC、n-iD、n-i+1【正确答案】：C51.已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（）。A、CBEFDAB、FEDCBACBEDFAD、不定【正确答案】：A52.设一棵树的度为4,其中度为1、2、3、4的节点个数分别为6、3、2、1,则这棵树中叶子节点的个数为()。A、8B、9C、10D、11【正确答案】：D53.在二叉链表上加线索的目的是()。A、提高遍历效率B、便于插人与删除C、便于找到双亲节点D、使遍历结果唯-【正确答案】：A54.数据结构是研究数据的()以及它们之间的相互关系。A、理想结构，物理结构B、理想结构，抽象结构C、物理结构，逻辑结构D、抽象结构，逻辑结构【正确答案】：C55.判断两个串相等的条件是()。A、含有字符数量相等B、对应位置字符相同C、两个字符串含义相同D、两个串含有字符数量相等且对应位置的字符相同【正确答案】：D56.排序码序列为(8,9,10,4,6,20,3,5),只能是()算法的前两趟排序结果。A、直接插人排序B、直接选择排序C、归并排序D、堆排序【正确答案】：A57.设n阶的对称矩阵采用压缩存储的方式存储下三角,则需要存储的元素个数为()。A、n2/2B、n(n+1)/2C、nD、n2【正确答案】：B58.堆排序属于下列()排序。A、插入B、交换C、归并D、选择【正确答案】：D59.深度为10的完全二叉树,第3层上的节点数是()。A、15B、16C、4D、32【正确答案】：C60.组成数据的基本单位是()A、数据项B、数据类型C、数据元素D、数据变量【正确答案】：C61.对于双向循环链表，在两个结点之间插入一个新结点需修改的指针共()个。A、2B、3C、5D、4【正确答案】：D62.假设删除长度为n的顺序表中的每个元素的概率相同，则删除一个元素平均要移动的元素个数是()。A、nB、n/2C、(n-1)/2D、(n+1)/2【正确答案】：C63.链表不具有的特点是()。A、插入、删除不需要移动元素B、不必事先估计存储空间C、可随机访问任一元素D、所需存储空间与线性表程度成正比【正确答案】：C64.线性表的链接存储结构是一种()存储结构.A、随机存取B、顺序存取C、索引存取D、散列存取【正确答案】：B65.下面关于散列查找的说法正确的是()A、在采用线性探测法处理冲突的散列表中,同义词在表中一定相邻B、除留余数法是所有散列函数中最好的C、在散列表中进行查找，“比较”次数的多少与冲突有关D、散列函数构造的越复杂越好,因为这样随机性好,冲突小【正确答案】：C66.当采用分块查找时,数据的组织方式为()。A、数据分成若干块,每块内记录是按关键字有序排列B、数据分成若干块,每块内记录必须有序,每块内最大(或最小)的数据组成索引表C、数据分成若干块,每一块内的记录个数需相同D、数据分成若干块,每块内记录不必有序,但块间必须有序,每块内最大(或最小)【正确答案】：B解析：

的数据组成索引表67.完成在双循环链表节点*p之后插入新节点*s的操作是()。A、p->next=s;s->prior=p;p->next->prior=s;s->next=p->next;B、p->next->prior=s;p->next=s;s->prior=p;s->next=p->next;C、s->prior=p;s->next=p-next;p->next=s;p->next->prior=s;D、s->prior=p;s->next=p->next;p->next->prior=s;p->next=s;【正确答案】：D68.矩阵压缩存储的目的为()。A、方便运算B、方便存储C、节省存储空间D、去掉多余的数据元素【正确答案】：C69.数据的逻辑结构是指()。A、数据所占的存储空间量B、各数据元素之间的逻辑关系C、数据在计算机中顺序或链接的存储方式D、存储在内存或外存中的数据【正确答案】：B70.快速排序在()情况下不利于发挥其优势。A、出现多个排序码相同的记录B、待排序记录的数量太大C、记录已经基本有序D、待排序记录的个数为偶数【正确答案】：C71.设二维数组为a_67,a_00为第一元素,若按行优先的顺序进行顺序存储,则a_46的前面有()个元素。A、33B、34C、35D、42【正确答案】：B72.使用二分查找时,要求查找表必须()。A、以顺序方式存储B、以顺序方式存储,且按关键字有序C、以链接方式存储D、以链接方式存储,且按关键字有序【正确答案】：B73.下列叙述中,正确的是()。A、数据的逻辑结构是指数据的各数据项之间的逻辑关系B、数据的物理结构是指数据在计算机内的实际存储形式C、在顺序存储结构中,数据元素之间的关系是显示体现的D、链接存储结构是通过节点的存储位置相邻来体现数据元素之间的关系【正确答案】：B74.树最适合用来表示()。A、有序数据元素B、无序数据元素C、元素之间具有分支层次关系的数据D、元素之间无联系的数据【正确答案】：C75.利用二叉链表存储树，则根结点的右指针是（）。A、指向最左孩子B、指向最右孩子C、空D、非空【正确答案】：C76.队列是一种（）的数据结构。A、先进先出B、先进后出C、后进先出D、后进后出【正确答案】：A77.已知一个带头节点单链表L,则在表头元素前插人新节点*s的语句为()。A、L=s;s->next=L;B、s->next=L->next;L->next=s;C、s=L;s->next=L;D、s->next=L;s=L;【正确答案】：B78.对于链接存储的线性表,按照序号访问和删除节点的时间复杂度分别为()。A、O(n),O(n)B、O(n),O(1)C、O(1),O(n)D、O(1),O(1)【正确答案】：A79.在对n个记录进行起泡排序的过程中,最好情况下的时间复杂度为()。A、O(n^3)B、O(n^2)C、0(n)D、O(1)【正确答案】：C80.下面关于线性表的叙述中,错误的是()。A、线性表若采用顺序存储,必须占用一片连续的存储单元B、线性表若采用顺序存储,便于进行插入和删除操作C、线性表若采用链接存储,不必占用一片连续的存储单元D、线性表若采用链接存储,便于插人和删除操作【正确答案】：B81.算法分析的目的是()。A、找出数据结构的合理性B、研究算法中的输入和输出的关系C、分析算法的效率以求改进D、分析算法的易懂性和文档性【正确答案】：C82.设数据结构D—S可以用二元组表示为D-S=(D,S),r∈S,其中:D={A,B,C,D},r={,,},则数据结构D-S是()A、线性结构B、树形结构C、图形结构D、集合【正确答案】：B83.下列有关二叉树下列说法正确的是()。A、二叉树是度为2的有序树B、二叉树中节点的度可以小于2C、二叉树中至少有一个节点的度为2D、二叉树中任何一个节点的度都为2【正确答案】：B84.非空单链表结点结构为【data,next】，若指针p所指结点是尾结点，则()表达式为真。A、p->next==PB、p->next!=NULLC、p->next==NULLD、p==NULL【正确答案】：C85.在长度为n的顺序表的第i(1≤i≤n十1)个位置上插入一个元素,元素的移动次数（）。A、n-i+1B、n-iC、iD、i-1【正确答案】：A86.递归函数调用时,需要使用()数据结构来处理参数、返回地址等信息。A、队列B、多维数组C、栈D、线性表【正确答案】：C87.广度优先搜索类似于二叉树的()。A、前序遍历B、中序遍历C、后序遍历D、层序遍历【正确答案】：D88.下列排序算法中,()方法在一趟结束后不一定能选出一个元素放在其最终位置上。A、简单选择排序B、起泡排序C、归并排序D、堆排序【正确答案】：C89.前序遍历与中序遍历结果相同的二叉树一定为()。A、只有根节点的二叉树B、根节点无左孩子的二叉树C、所有节点只有左子树的二叉树D、所有节点只有右子树的二叉树【正确答案】：D90.有9个顶点的有向完全图有()条边。A、18B、36C、72D、144【正确答案】：C91.某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用()存储方式最节省运算时间。A、带尾指针的单循环链表B、仅有头指针的单循环链表C、单链表D、双链表【正确答案】：A92.已知一个不带头节点单链表的头指针为L,则在表头元素之前插入一个新节点的语句为()。A、L=s;s->next=L;B、s->next=L;L=s;C、s=L;s->next=L;D、s->next=L;s=L;【正确答案】：B93.顺序查找法适合于存储结构为()的线性表。A、散列存储B、顺序存储或链接存储C、压缩存储D、索引存储【正确答案】：B1.算法可以用不同的语言描述，如果用C或PASCAL语言等高级语言来描述，则算法实际上就是程序了。()A、正确B、错误【正确答案】：B2.单链表中增加头结点的目的是存储链表的长度。()A、正确B、错误【正确答案】：B3.二叉树只能用二叉链表表示。()A、正确B、错误【正确答案】：B4.算法的可行性是指指令不能有二义性。()A、正确B、错误【正确答案】：B5.算法的时间复杂度取决于问题的规模和待处理数据的初态。()A、正确B、错误【正确答案】：A6.顺序表结构适宜进行随机访问，而链表适宜进行插入、删除。()A、正确B、错误【正确答案】：A7.数据的计算机内的表示称为数据的存储结构。()A、正确B、错误【正确答案】：A8.静态链表中能容纳的元素个数在链表定义时就确定了，以后不能增加。()A、正确B、错误【正确答案】：A9.如果数据元素值发生改变，则数据的逻辑结构也随之改变。()A、正确B、错误【正确答案】：B10.数据的逻辑结构时指数据的各数据项之间的逻辑关系。()A、正确B、错误【正确答案】：B11.任何数据结构都具备3个基本运算:插入、删除、和查找。()A、正确B、错误【正确答案】：B12.算法就是程序。()A、正确B、错误【正确答案】：B13.线性表在顺序存储时，查找第i个元素的时间同i的值成正比。()A、正确B、错误【正确答案】：B14.霍夫曼树的结点个数不能是偶数。A、正确B、错误【正确答案】：A15.数据的逻辑结构与数据元素在计算机中如何存储有关。()A、正确B、错误【正确答案】：B16.静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关。()A、正确B、错误【正确答案】：B17.二叉树中序线索化后，不存在空指针域。A、正确B、错误【正确答案】：B18.算法的五个特性为:有穷性、输入、输出、完成性和确定性。()A、正确B、错误【正确答案】：B19.如果两个串相等,则两个串的长度相同。()A、正确B、错误【正确答案】：B20.度为二的树就是二叉树。A、正确B、错误【正确答案】：B21.将一棵树转成二叉树，根结点没有左子树。A、正确B、错误【正确答案】：B22.线性表在链式存储时，查找第i个元素的时间同i的值无关。()A、正确B、错误【正确答案】：B23.算法的优劣与算法描述语言无关，但与所用的计算机有关。()A、正确B、错误【正确答案】：B24.数据对象就是一组任意数据元素的集合。()A、正确B、错误【正确答案】：B25.树形结构中元素之间存在一个对多个的关系。A、正确B、错误【正确答案】：A26.静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。()A、正确B、错误【正确答案】：A27.逻辑结构相同的数据，在设计存储结构时，它们的节点类型也一定相同。()A、正确B、错误【正确答案】：B28.给定一棵树，可以找到唯一的一棵二叉树与之对应。（）A、正确B、错误【正确答案】：A29.数据元素是数据的最小单位。()A、正确B、错误【正确答案】：B30.逻辑结构相同的数据，可以采用多种不同的存储方法。()A、正确B、错误【正确答案】：A31.逻辑结构不相同的数据，必须采用多种不同的存储方法。()A、正确B、错误【正确答案】：B32.哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。A、正确B、错误【正确答案】：A33.数据元素是数据的最小单位。()A、正确B、错误【正确答案】：B34.算法最终必须由计算机程序实现.()A、正确B、错误【正确答案】：B35.循环单链表中，每个结点都有一个前驱和后继，因此循环单链表不是线性结构。()A、正确B、错误【正确答案】：B36.空串不是任何串的子串。()A、正确B、错误【正确答案】：B37.健壮的算法不会因非法输入数据而出现莫名其妙的状态。()A、正确B、错误【正确答案】：A38.在顺序表中，逻辑上相邻的两个元素物理存储上也一定也相邻。()A、正确B、错误【正确答案】：A39.程序一定是算法。()A、正确B、错误【正确答案】：B填空题1.栈和队列都是操作受限的线性表,栈的运算特点是（），,队列的运算特点（）。【正确答案】：先进后出|先进先出2.算法中的语句频度之和为T(n)=355n^2+84nlbn+2n，则算法的时间复杂度是（）。【正确答案】：O_((n^2))3.某有向图的邻接矩阵如下所示,则该图中有（）条边,有（）个顶点。【正确答案】：9|64.已知一个顺序栈*s,栈顶指针是top,它的容量为MAXSIZE,则判断栈空的条件为（）,栈满的条件是（）。【正确答案】：s->top==-1、s->top==MAXSIZE-15.算法的特性包括（）、（）、（）、输入和输出。【正确答案】：有穷性|确定性|可行性6.某循环队列的容量MAXSIZE=6,队头指针front=3,队尾指针rear=0,则该队列有（）个元素。【正确答案】：37.二维数组在采用顺序存储时,元素的排列方式有（）和（）两种。【正确答案】：行优先|列优先8.顺序表和链表中能实现随机存取的是（）,插入、删除操作效率高的是（）。【正确答案】：顺序表|链表9.哈希表通过散列函数将关键字映射到（）上。【正确答案】：哈希表10.若序列a、b、c、d、e按顺序入栈,假设P表示入栈操作,S表示出栈操作,则操作序列PSPPSPSPSS后得到的输出序列为（）【正确答案】：ABCDE11.链接存储的特点是附加（）来表示数据元素之间的逻辑关系。【正确答案】：指针域12.数据结构主要研究数据的（）、（）和（）三方面的内容。【正确答案】：逻辑结构|存储结构|数据的运算13.判断带头节点的单链表L为空的条件（）。【正确答案】：L->next==NULL14.线性表的逻辑结构是（）结构。【正确答案】：线性15.对于一个具有n个节点的单链表,已知一个节点的指针p,在其后插入一个新节点的时间复杂度为（）;若已知一个节点的值为x,在其后插入一个新节点的时间复杂度为（）.【正确答案】：O(1)|O(n)16.若无向图采用邻接矩