数据结构模拟练习题.doc

)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、算法一定要有输入和输出 （ ） （ ）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、程序越短，程序运行的时间就越少 （ ） （ ）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 条边（ ）二、填空题： 《数据结构》课程讨论的主要内容是数据的逻辑结构、存储结构和______________。

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 指针都等于 _______________。