算法与数据结构习题及参考答案2
单项选择题
1. 文件的基本组织方式有：（）。
A、顺序组织、索引组织、散列组织和链接方式
B、磁盘组织、磁带组织
C、数据库组织
D、关键字与非关键字
答案：A
2. 为了区别循环队列中队满与队空的条件，采用的方法是：（）。
A、不需要特别的方法
B、牺牲一个存贮空间
C、把队头永远放到队尾的前端
D、每次出队后，移动数据
答案：B
3. 通过链表存贮树时，如果给定树中结点的个数，则链域浪费的空间随树的度增加而：（）。
A、增加
B、减少
C、不变
D、无规律
答案：A
4. 两字符串相等的条件是（）。
A、两个串的长度相等
B、两个串包含的字符相等
C、两个串的长度相等，并且两个串包含的字符相同
D、两个串的长度相等，并且对应位置上的字符相同
答案：D
5. 在下列有关图的存储结构中说法错误的是（）。
A、用邻接矩阵存储一个图时所占用的存储空间大小与图中的顶点个数有关，而与图的
边数无关
B、邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用
C、邻接矩阵只适用于稠密图（边数接近于顶点数的平方），邻接表适用于稀疏图（边数远小于顶点数的平方）
D、存储无向图的邻接矩阵是对称的，因此只要存储邻接矩阵的下（上）三角部分就可以了
答案：B
6. 顺序搜索法适合于存储结构为（）的线性表。
A、散列存储
B、顺序存储或链接存储
C、压缩存储
数据结构与算法第二版课后题答案D、索引存储
答案：B
多项选择题
1. 下述陈述中哪一项是正确的():
A、文件是由记录组成的集合
B、记录是文件存取的基本单位
C、文件是由数据项组成的
D、数据项有时也被称之为字段
答案：BD
2. 下列排序算法中哪些是不稳定的():
A、昌泡排序
B、选择排序
C、快速排序
D、堆排序
答案：BCD
3. 稀疏矩阵的存贮结构要满足哪些条件？()
A、每个非零元素存贮其行号、列号以及值
B、存贮矩阵的行数和列数
C、所有的非零元素以行优先的排列规则存贮
D、只存贮上三角的元素
E、只存贮下三角的元素
答案：ABC
4. 图的邻接矩阵存贮结构包括():
A、表示图中顶点间相邻关系的矩阵
B、对称矩阵
C、表示图中顶点元素的数组
D、表示入度的数组
E、表示出度的数组
答案：AC
5. 假设有三角矩阵a[n][n]，对角线及对角线以上的元素非零，对角线以下的元素为0。如果采用压缩存贮，即只存贮矩阵中的上三角元素和既存贮上三角元素又存贮0两种情况下，所需要的存贮空间的分别容量为()和()。
A、n*(n+1)/2, n*(n+1)/2 + 1
B、n*(n+1)/2, n*n
C、(n+1)n/2, (n+1)n/2 + 1
D、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个）的元素的存储地址为。
答案：144
2. 在函数中对引用型形式参数的修改就是对相应的修改，而对型形式参数的修改只局限在该函数的内部，
不会反映到对应的实际参数上。
答案：实际参数的值；传值
3. 将一个n阶对称矩阵的上三角部分或下三角部分压缩存放于一个一维数组中，则一维数组需要存储个矩阵元素。
答案：n(n+1)/2
简答题
1. 请回答关于链接存储的优缺点。
答案：优点：1.插入和删除比较灵活，不需要大量移动结点。
2.动态分配空间比较灵活，不需要预先申请最大的连续空间。
2.检索必须沿链进行，不能随机存取。
2. 请写一个递归算法来计算并返回链表的长度，并在程序中做出相应的文字说明。
答案： int length(LinkList llist){    /*计算单链表list的长度*/
If(llist = = NULL)
return();
return1+length(llist->link);
}
3. 给出栈的最常用的5种操作，并说明它们的功能。
答案：
(1) void push（ST,x）将元素x插入栈ST的顶端
(2) void pop（ST）从栈ST顶端删除一个元素
(3) DataType top（ST）读栈ST顶端的元素
(4) int isEmpty（ST）判断栈ST是否为空栈
(5) pStack creatEmptyStack()  创建一个空栈

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。