《数据结构》期中题库及答案

一、判断题：1、线性表的逻辑顺序与物理顺序总是一致的。()2、线性表的顺序存储表示优于链式存储表示。()3、线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。()4、二维数组是其数组元素为线性表的线性表。()5、每种数据结构都应具备三种基本运算：插入、删除和搜索。()6、数据结构概念包括数据之间的逻辑结构，数据在计算机中的存储方式和数据的运算三个方面。()7、线性表中的每个结点最多只有一个前驱和一个后继。（）8、线性的数据结构可以顺序存储，也可以链接存储。非线性的数据结构只能链接存储。（）9、栈和队列逻辑上都是线性表。（）10、单链表从任何一个结点出发，都能访问到所有结点（）11、删除二叉排序树中一个结点，再重新插入上去，一定能得到原来的二叉排序树。（）12、快速排序是排序算法中最快的一种。（）13、多维数组是向量的推广。（）14、一般树和二叉树的结点数目都可以为0。（）15、直接选择排序是一种不稳定的排序方法。（）16、98、对一个堆按层次遍历，不一定能得到一个有序序列。（）17、在只有度为0和度为k的结点的k叉树中，设度为0的结点有n0个，度为k的结点有nk个，则有n0=nk+1。（）18、折半搜索只适用与有序表，包括有序的顺序表和有序的链表。（）19、堆栈在数据中的存储原则是先进先出。（）20、队列在数据中的存储原则是后进先出。（）21、用相邻矩阵表示图所用的存储空间大小与图的边数成正比。（）22、哈夫曼树一定是满二叉树。（）23、程序是用计算机语言表述的算法。（）24、线性表的顺序存储结构是通过数据元素的存储地址直接反映数据元素的逻辑关系。（）25、用一组地址连续的存储单元存放的元素一定构成线性表。（）26、堆栈、队列和数组的逻辑结构都是线性表结构。（）27、给定一组权值，可以唯一构造出一棵哈夫曼树。（）28、只有在初始数据为逆序时，冒泡排序所执行的比较次数最多。（）29、希尔排序在较率上较直接接入排序有较大的改进。但是不稳定的。（）30、在平均情况下，快速排序法最快，堆积排序法最节省空间。（）31、快速排序法是一种稳定性排序法。（）32、算法一定要有输入和输出。（）33、算法分析的目的旨在分析算法的效率以求改进算法。（）34、非空线性表中任意一个数据元素都有且仅有一个直接后继元素。（）35、数据的存储结构不仅有顺序存储结构和链式存储结构，还有索引结构与散列结构。（）36、若频繁地对线性表进行插入和删除操作，该线性表采用顺序存储结构更合适。（）37、若线性表采用顺序存储结构，每个数据元素占用4个存储单元，第12个数据元素的存储地址为144，则第1个数据元素的存储地址是101。（）38、若长度为n的线性表采用顺序存储结构，删除表的第i个元素之前需要移动表中n-i+1个元素。（）39、符号p-next出现在表达式中表示p所指的那个结点的内容。（）40、要将指针p移到它所指的结点的下一个结点是执行语句p←p-next。（）41、若某堆栈的输入序列为1,2,3,4，则4,3,1,2不可能是堆栈的输出序列之一。（）42、线性链表中各个链结点之间的地址不一定要连续。（）43、程序就是算法，但算法不一定是程序。（）44、线性表只能采用顺序存储结构或者链式存储结构。（）45、线性表的链式存储结构是通过指针来间接反映数据元素之间逻辑关系的。（）46、除插入和删除操作外，数组的主要操作还有存取、修改、检索和排序等。（）47、稀疏矩阵中0元素的分布有规律，因此可以采用三元组方法进行压缩存储。（）48、不管堆栈采用何种存储结构，只要堆栈不空，可以任意删除一个元素。（）49、确定串Ｔ在串Ｓ中首次出现的位置的操作称为串的模式匹配。（）50、深度为h的非空二叉树的第i层最多有2i-1个结点。（）51、满二叉树也是完全二叉树。（）52、已知一棵二叉树的前序序列和后序序列可以唯一地构造出该二叉树。（）53、非空二叉排序树的任意一棵子树也是二叉排序树。（）54、对一棵二叉排序树进行前序遍历一定可以得到一个按值有序的序列。（）55、一个广义表的深度是指该广义表展开后所含括号的层数。（）56、散列表的查找效率主要取决于所选择的散列函数与处理冲突的方法。（）57、序列初始为逆序时，冒泡排序法所进行的元素之间的比较次数最多。（）58、已知指针P指向键表L中的某结点，执行语句P=P-〉next不会删除该链表中的结点。（）59、在链队列中，即使不设置尾指针也能进行入队操作。（）60、如果一个串中的所有字符均在另一串中出现，则说前者是后者的子串。（）61、设与一棵树T所对应的二叉树为BT，则与T中的叶子结点所对应的BT中的结点也一定是叶子结点。（）62、若图G的最小生成树不唯一，则G的边数一定多于n-1，并且权值最小的边有多条（其中n为G的顶点数）。（）63、给出不同的输入序列建造二叉排序树，一定得到不同的二叉排序树。（）64、由于希尔排序的最后一趟与直接插入排序过程相同，因此前者一定比后者花费的时间多。（）65、程序越短，程序运行的时间就越少。（）66、采用循环链表作为存储结构的队列就是循环队列。（）67、堆栈是一种插入和删除操作在表的一端进行的线性表。（）68、一个任意串是其自身的子串。（）69、哈夫曼树一定是完全二叉树。（）70、带权连通图中某一顶点到图中另一定点的最短路径不一定唯一。（）71、折半查找方法可以用于按值有序的线性链表的查找。（）72、稀疏矩阵压缩存储后,必会失效掉随机存取功能。（）73、由一棵二叉树的前序序列和后序序列可以唯一确定它。（）74、在n个结点的元向图中,若边数在于n-1,则该图必是连通图。（）75、在完全二叉树中,若某结点元左孩子,则它必是叶结点。（）76、若一个有向图的邻接矩阵中,对角线以下元素均为0,则该图的拓扑有序序列必定存在。（）77、树的带权路径长度最小的二叉树中必定没有度为1的结点。（）78、二叉树可以用0≤度≤2的有序树来表示。（）79、一组权值，可以唯一构造出一棵哈夫曼树。()80、101，88，46，70，34，39，45，58，66，10）是堆；（）81、将一棵树转换成二叉树后，根结点没有左子树；（）82、用树的前序遍历和中序遍历可以导出树的后序遍历；（）83、在非空线性链表中由p所指的结点后面插入一个由q所指的结点的过程是依次执行语句：q-next=p-next;p-next=q。（）84、非空双向循环链表中由q所指的结点后面插入一个由p指的结点的动作依次为：p-prior=q,p-next=q-next,q-next=p,q-prior-next←p。（）85、删除非空链式存储结构的堆栈(设栈顶指针为top)的一个元素的过程是依次执行:p=top,top=p-next,free(p)。()86、哈希的查找无需进行关键字的比较。（）87、一个好的哈希函数应使函数值均匀的分布在存储空间的有效地址范围内，以尽可能减少冲突。（）88、排序是计算机程序设计中的一种重要操作，它的功能是将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列。（）89、队列是一种可以在表头和表尾都能进行插入和删除操作的线性表。（）90、在索引顺序表上实现分块查找，在等概率查找情况下，其平均查找长度不与表的个数有关，而与每一块中的元素个数有关。（）91、对于有向图，顶点的度分为入度和出度，入度是以该顶点为终点的入边数目；出度是以该顶点为起点的出边数目，该顶点的度等于其入度和出度之和。（）92、无向图的邻接矩阵是对称的有向图的邻接矩阵是不对称的。（）93、具有n个顶点的连通图的生成树具有n-1条边（）二、填空题：1、《数据结构》课程讨论的主要内容是数据的逻辑结构、存储结构和______________。2、数据结构算法中，通常用时间复杂度和__________________两种方法衡量其效率。3、一个算法一该具有______,______,____,______和____这五种特性。4、若频繁地对线性表进行插入与删除操作，该线性表应采用____________存储结构。5、在非空线性表中除第一个元素外，集合中每个数据元素只有一个_______；除最后一个元素之外，集合中每个数据元素均只有一个_________。6、线性表中的每个结点最多有________前驱和____________后继。7、______链表从任何一个结点出发，都能访问到所有结点。8、链式存储结构中的结点包含____________域，_______________域。9、在双向链表中，每个结点含有两个指针域，一个指向______结点，另一个指向________结点。10、某带头结点的单链表的头指针head，判定该单链表非空的条件______________。11、在双向链表中，每个结点含有两个指针域，一个指向_______结点，另一个指向_____结点。12、已知指针p指向单链表中某个结点，则语句p-next=p-next-next的作用__删除p的后继结点_。13、已知在结点个数大于1的单链表中，指针p指向某个结点，则下列程序段结束时，指针q指向*p的_____________结点。q=p;while(q-next!=p)q=q-next;14、若要在单链表结点*P后插入一结点*S，执行的语句_______________。15、线性表的链式存储结构地址空间可以_________，而向量存储必须是地址空间___________。16、栈结构允许进行删除操作的一端为_____________。17、在栈的顺序实现中，栈顶指针top，栈为空条件______________。18、对于单链表形式的队列，其空队列的F指针和R指针都等于__________________。19、若数组s[0..n-1]为两个栈s1和s2的共用存储空间，仅当s[0..n-1]全满时，各栈才不能进行栈操作，则为这两个栈分配空间的最佳方案是：s1和s2的栈顶指针的初值分别为_________。20、允许在线性表的一端插入,另一端进行删除操作的线性表称为_______。插入的一端为______,删除的一端为______。21、设数组A[m]为循环队列Q的存储空间，font为头指针，rear为尾指针，判定Q为空队列的条件____________________。22、对于顺序存储的队列，存储空间大小为n，头指针为F，尾指针为R。若在逻辑上看一个环，则队列中元素的个数为___________。23、已知循环队列的存储空间为数组data[21]，且头指针和尾指针分别为8和3，则该队列的当前长度__________。24、一个串的任意个连续的字符组成的子序列称为该串的________，包含该子串的串称为________。25、求串T在主串S中首次出现的位置的操作是________________。26、在初始为空的队列中插入元素A,B,C,D以后，紧接着作了两次删除操作，此时的队尾元素是__________。27、在长度为n的循环队列中，删除其节点为x的时间复杂度为_______________。28、已知广义表L为空，其深度为___________。29、已知一顺序存储的线性表，每个结点占用k个单元，若第一个结点的地址为DA1，则第i个结点的地址为______________。30、设一行优先顺序存储的数组A[5][6]，A[0][0]的地址为1100，且每个元素占2个存储单元，则A[2][3]的地址为_____________。31、设有二维数组A[9][19]，其每个元素占两个字节，第一个元素的存储地址为100，若按行优先顺序存储，则元素A[6,6]的存储地址为______________，按列优顺序存储，元素A[6,6]的存储地址为______________。32、在进行直接插入排序时,其数据比较次数与数据的初始排列________关；而在进行直接选择排序时，其数据比较次数与数据的初始排列__________关。33、假设