兰州大学计算机科学与技术专业《数据结构》作业及答案4
搜题
1、若用单链表示列队，那么应选用()。
A.带尾指针的循环链表
B.带尾指针的非循环列队
C.带头指针的非循环链表
D.带头指针的循环链表
本题答案：
A
A
2、单链表的结点包含()和()。
A.结点域，符号域
B.数据域，符号域
C.结点域，指针域
D.数据域，指针域
本题答案：
D
D
3、序例278、109、930经过一趟基数排序后结果为()。
A.930、278、109
B.109、930、278
C.109、278、930
D.278、109、930
本题答案：
A
A
4、函数substr(“DATASTRUCTURE”，5，9)的返回为()。
A.“STRUCTURE”
B.“DATA”
C.“ASTRUCTUR”
D.“DATASTRUCTURE”
本题答案：
A
A
5、设某完全无向图中有n个顶点，则该完全无向图中有()条边。
A.n(n-1)/2
B.n(n-1)
C.n²
D.n²-1
本题答案：
A
A
6、堆排是一种()排序。
A.插入
B.选择
C.交换
D.归并
本题答案：
B
B
7、图的广度优先遍历算法类似于二叉树的()。
A.先序遍历
B.中序遍历
C.后序遍历
D.层次遍历
本题答案：
B
B
8、对n个不同的排序码进行冒泡排序，在下列哪种情况下比较的次数最多()。
A.从小到大排列好的
B.从大到小排列好的
C.元素无序
D.元素基本有序
本题答案：
B
B
9、如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用()方法最快。
A.起泡排序
B.快速排列
C.Shell排序
D.堆排序
E.单单选择排序
本题答案：
D
D
10、二叉树的第K层的结点数最多为()。
A.2^k-1
B.2^K+1
C.2^(k-1)+1
D.2^(k-1)
本题答案：
D
D
11、栈是后进先出的线性表。()
A.正确
B.错误
本题答案：
A
A
12、森林的先序遍历与其对应的二叉树的中序遍历对应。()
A.正确
B.错误
本题答案：
A
A
13、对于哈希函数，冲突只能尽可能的少，不可能完全避免。()
A.正确
B.错误
本题答案：
A
A
14、线性表若采用顺序存储结构时，要求内存中的可用存储单元的地址必须连续。()
A.正确
B.错误
本题答案：
A
A
15、栈是限定在表尾进行插入或删除操作的线性表。()
A.正确
B.错误
本题答案：
B
B
16、设有一棵算术表达式树，用什么方法可以对该树所表示的表达式求值?
本题答案：
方法有二。一是对该算术表达式(二叉树)进行后序遍历，得到表达式的后序遍历序列，再按后缀表达式求值；二是递归求出左子树表达式的值，再递归求出右子树表达式的值，最后按根结点运算符(、-、*、/等)进行最后求值。
方法有二。一是对该算术表达式(二叉树)进行后序遍历，得到表达式的后序遍历序列，再按后缀表达式求值；二是递归求出左子树表达式的值，再递归求出右子树表达式的值，最后按根结点运算符(、-、*、/等)进行最后求值。
17、写出二叉树进行前序和中续遍历的过程。
本题答案：
前序遍历：(1)访问根结点(2)前序遍历左子树(3)前序遍历右子树
中序遍历：(1)中序遍历左子树(2)访问根结点(3)中序遍历右子树
前序遍历：(1)访问根结点(2)前序遍历左子树(3)前序遍历右子树
中序遍历：(1)中序遍历左子树(2)访问根结点(3)中序遍历右子树
18、如何知道循环队列是空还是满?
本题答案：
采用循环队列是解决假溢出的途径。
另外，解决队满队空的办法有三：
(1)设置一个布尔变量以区别队满还是队空；
(2)浪费一个元素的空间，用于区别队满还是队空；
(3)使用一个计数器记录队列中元素个数(即队列长度)。
我们常采用方法(2)，即队头指针、队尾指针中有一个指向实元素，而另一个指向空闲元素。
判断循环队列队空标志是：f=rear；队满标志是：f=(r+1)%N
采用循环队列是解决假溢出的途径。
另外，解决队满队空的办法有三：
(1)设置一个布尔变量以区别队满还是队空；
(2)浪费一个元素的空间，用于区别队满还是队空；
(3)使用一个计数器记录队列中元素个数(即队列长度)。
我们常采用方法(2)，即队头指针、队尾指针中有一个指向实元素，而另一个指向空闲元素。
判断循环队列队空标志是：f=rear；队满标志是：f=(r+1)%N
19、图的遍历(名词解释)
本题答案：
是从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次。
是从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次。
20、稀疏矩阵(名词解释)
本题答案：
对于那些零元素数目远远多于非零元素数目，并且非零元素的分布没有规律的矩阵称为稀疏矩阵。
对于那些零元素数目远远多于非零元素数目，并且非零元素的分布没有规律的矩阵称为稀疏矩阵。