算法与数据结构习题及参考答案2

算法与数据结构习题及参考答案2单项选择题1.文件的基本组织方式有：（）。A、顺序组织、索引组织、散列组织和链接方式B、磁盘组织、磁带组织C、数据库组织D、关键字与非关键字答案：A2.为了区别循环队列中队满与队空的条件，采用的方法是：（）。A、不需要特别的方法B、牺牲一个存贮空间C、把队头永远放到队尾的前端D、每次出队后，移动数据答案：B3.通过链表存贮树时，如果给定树中结点的个数，则链域浪费的空间随树的度增加而：（）。A、增加B、减少C、不变D、无规律答案：A4.两字符串相等的条件是（）。A、两个串的长度相等 B、两个串包含的字符相等C、两个串的长度相等，并且两个串包含的字符相同 D、两个串的长度相等，并且对应位置上的字符相同答案：D5.在下列有关图的存储结构中说法错误的是（）。A、用邻接矩阵存储一个图时所占用的存储空间大小与图中的顶点个数有关，而与图的边数无关 B、邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用C、邻接矩阵只适用于稠密图（边数接近于顶点数的平方），邻接表适用于稀疏图（边数远小于顶点数的平方） D、存储无向图的邻接矩阵是对称的，因此只要存储邻接矩阵的下（上）三角部分就可以了答案：B6.顺序搜索法适合于存储结构为（）的线性表。A、散列存储 B、顺序存储或链接存储C、压缩存储 D、索引存储答案：B多项选择题1.下述陈述中哪一项是正确的():A、文件是由记录组成的集合B、记录是文件存取的基本单位C、文件是由数据项组成的D、数据项有时也被称之为字段答案：BD2.下列排序算法中哪些是不稳定的():A、昌泡排序B、选择排序C、快速排序D、堆排序答案：BCD3.稀疏矩阵的存贮结构要满足哪些条件？()A、每个非零元素存贮其行号、列号以及值B、存贮矩阵的行数和列数C、所有的非零元素以行优先的排列规则存贮D、只存贮上三角的元素E、只存贮下三角的元素答案：ABC4.图的邻接矩阵存贮结构包括():A、表示图中顶点间相邻关系的矩阵B、对称矩阵C、表示图中顶点元素的数组D、表示入度的数组E、表示出度的数组答案：AC5.假设有三角矩阵a[n][n]，对角线及对角线以上的元素非零，对角线以下的元素为0。如果采用压缩存贮，即只存贮矩阵中的上三角元素和既存贮上三角元素又存贮0两种情况下，所需要的存贮空间的分别容量为()和()。A、n*(n+1)/2,n*(n+1)/2+1B、n*(n+1)/2,n*nC、(n+1)n/2,(n+1)n/2+1D、n(n-1)/2,n*(n-1)/2+1答案：AC判断题1.拓扑排序是图的另一种遍历。答案：正确2.树是一种特殊的图。答案：正确3.数据结构中只研究了二叉树，对一般树没有给出解决问题的算法。答案：错误4.在单向链表中，在X指向的结点后插入结点，对应的方法与X是否是头指针无关。答案：错误5.有人采用Haffman树进行编码后，由于每个符号的代码长度不等，当接收方收到编码后的内容后，不能转换为原来的正文。该说法是否正确？答案：正确6.一棵度为2的树是一棵二叉树。答案：错误7.数组是一种复杂的数据结构，数组元素之间的关系既不是线性的，也不是树形的。答案：错误8.对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。答案：正确9.两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。答案：正确10.最优二叉搜索树一定是平衡的二叉搜索树。答案：错误填空题1．某线性表采用顺序存储结构，每个元素占据4个存储单元，首地址为100，则下标为11（第12个）的元素的存储地址为。答案：1442.在函数中对引用型形式参数的修改就是对相应的修改，而对型形式参数的修改只局限在该函数的内部，不会反映到对应的实际参数上。答案：实际参数的值；传值3.将一个n阶对称矩阵的上三角部分或下三角部分压缩存放于一个一维数组中，则一维数组需要存储个矩阵元素。答案：n(n+1)/2简答题1.请回答关于链接存储的优缺点。答案：优点：1.插入和删除比较灵活，不需要大量移动结点。2.动态分配空间比较灵活，不需要预先申请最大的连续空间。缺点：1.增加指针的空间开销2.检索必须沿链进行，不能随机存取。2.请写一个递归算法来计算并返回链表的长度，并在程序中做出相应的文字说明。答案：intlength(LinkListllist){/*计算单链表list的长度*/If(llist==NULL)return();return1+length(llist->link);}3.给出栈的最常用的5种操作，并说明它们的功能。答案：(1)voidpush（ST,x）将元素x插入栈ST的顶端(2)void