数据结构试题（含答案）一．是非题（勾选“√“用于更正和勾选”√1.数据结构可用三元公式（D，s，P）表示，其中：D为数据对象，s为D上的关系，p是对d的基本操作集。×2.线性表的链式存储结构具有直接访问表中任何元素的优点。×3.字符串是特定于数据对象的线性表。4.二叉树是一棵结点的度最大为二的树。×5.邻接多表可用于表示无向图或有向图。×6.所有顶点的拓扑序都可以从任何有向图中得到。×7.无向连通图的生成树是其最大连通子图。×8.二叉排序树的搜索长度最多为log2n。×9．对于一棵m阶的b-树.树中每个结点至多有m个关键字。除根之外的所有非终端结点至几乎没有┌M/2┌关键词。×10．对于目前所知的排序方法，快速排序具有最好的平均性能。11.顺序存储模式具有存储密度高、插入和删除操作效率高的优点。×12.二维数组是一个线性表，其数据元素是线性表。13.连通图g的生成树是一个包含g的所有n个顶点和n-1条边的子图。×14.折半查找不适用于有序链表的查找。15.完全二叉树必定是平衡二叉树。16.中间顺序线索二叉树的优点是，在中间顺序下很容易找到直接前导节点和直接后继节点。17.队列是一种完全不同于线性表的数据结构。×18.平均搜索长度与记录的搜索概率有关。19.二叉树中每个结点有两个子结点，而对一般的树，则无此限制，所以，二叉树是树的特殊情形。×20.算法的时间复杂度越高，可读性越差；相反，算法的可读性越好，时间复杂度越差。×二．选择题1.如果编号为1、2和3的列车车厢依次通过开关堆调度，则无法获得（E）的顺序。a:1,2,3b:1,3,2c:2,1,3d:2,3,1e:3,1,2f:3,2,12.递归程序可借助于(b)转化为非递归程序。a:线性表B:堆栈C:队列D:数组3.在下列数据结构中(c)具有先进先出（fifo）特性，（b）它具有先进先出的特点。a:线性表b:栈c:队列d:广义表4.对字符串s='datastructure'执行替换（s，子字符串（s，6,8），'bas'）操作的结果是(d)。a:‘数据库’b:‘数据库’c:‘基础’d:‘数据基础结构’5.设有二维数组a5x7,每一元素用相邻的4个字节存储，存储器按字节编址。众所周知，a的起始地址是100。然后，当按行存储时，元素A06的第一个字节的地址是（d）；当按列存储时，元素A06的第一个字节的地址是（a）a:220b:200C:140d:1246.对广义表a=（（a,(b)）,(c,()),d）执行操作gettail(gethead(gettail(a)))的结果是：（b）。a:（）b:（（））c:dd:(d)7.假设用于通信的消息仅由六个字符组成，消息中字母的频率分别为7、19、22、6、32和14。如果哈夫曼编码是为这六个字母设计的（假设生成新二叉树的规则是按给定顺序从左到右组合，并且新生成的二叉树总是插入到右边），则频率为7的字符编码是（g），频率为32的字符编码是（c）。a:00b:01c:10d:11e:011f:110g:1110h:11118.对于二叉排序树（b），可以得到有序序列。a:按层遍历b:前序遍历c:中序遍历d:后序遍历9.已知树的第一个根遍历顺序是ABCDEFG，第二个根遍历顺序是cdebgfa。若将该树转换为二叉树,其后序遍历次序为（d）。a:abcdefgb:cdebgfac:cdegbfad:edcgfba10．对一棵完全二叉树进行层序编号。则编号为n的结点若存在右孩子,其位序是(d)。如果编号为n的节点有父节点，则其位置为（a）。a:n/2b:2nc:2n-1d:2n+1e:nf:2(n+1)11.关键路径是指在只有一个源点和一个汇点的有向无环网络中，从源点到汇点（c）的路径。a:弧的数目最多b:弧的数目最少c:权值之和最大d:权值之和最小12.哈希表的查找效率取决于（d）。a:哈希函数b:处理冲突的方法。c:哈希表的装填因子。d:以上都是13．从逻辑上可以把数据结构分成(c)。a、动态结构和静态结构B.顺序组织和链接组织c.线性结构和非线性结构d.基本类型和组合类型14.计算递归函数时，如果不使用递归过程，则应使用数据结构（b）。a.线性表b.栈c.队列d.双向队列15.如果二叉树的中间顺序和后顺序遍历序列已知，则分别为bcaefd和cbfeda，然后是二叉树的前顺序序列为(a)。a、abcdefb。abdcefc。阿布德谢德。acbdfe16．当待排序序列的关键字次序为倒序时，若需为之进行正序排序，