课堂练习学生答案

《课堂练习学生答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、课堂练习一、选择题（C）1.数据结构中，与所使用的计算机无关的是数据的()结构；A、存储B、物理C、逻辑D、物理和存储（B）2.计算机算法必须具备输入、输出和等5个特性。A)可行性、可移植性和可扩充性B)可行性、确定性和有穷性C)确定性、有穷性和稳定性D)易读性、稳定性和安全性（A）3.在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是：（A）访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）（B）在第i个结点后插入一个新结点（1≤i≤n）（C）删除第i个结点（1≤i≤n）（D）将n个结点从小到大排序（D）4.线性表若采用链式

2、存储结构时，要求内存中可用存储单元的地址:（A）必须是连续的（B）部分地址必须是连续的（C）一定是不连续的（D）连续或不连续都可以（B）5.判定一个栈ST（最多元素为m0）为空的条件是Ａ．ST->top<>0Ｂ．ST->top=0Ｃ．ST->top<>m0Ｄ．ST->top=m0（D）6．数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素的公式为（Ａ）r－f;（Ｂ）（n＋f－r）%n;（Ｃ）n＋r－f;（Ｄ）（n＋r－f）%n（A）7.假设有60行70列的二维数组a[1…6

3、0,1…70]以列序为主序顺序存储，其基地址为10000，每个元素占2个存储单元，那么第32行第58列的元素a[32,58]的存储地址为。（无第0行第0列元素）Ａ．16902Ｂ．16904Ｃ．14454Ｄ．答案A,B,C均不对答：（57列×60行＋31行）×2字节＋10000=16902（C）8．二叉树是非线性数据结构，所以。（Ａ）它不能用顺序存储结构存储;（Ｂ）它不能用链式存储结构存储;（Ｃ）顺序存储结构和链式存储结构都能存储;（Ｄ）顺序存储结构和链式存储结构都不能使用（A）9．把一棵树转换为二叉树后，这棵二叉树的形态是。（Ａ）唯一的（Ｂ）有多种

4、（Ｃ）有多种，但根结点都没有左孩子（Ｄ）有多种，但根结点都没有右孩子（B）10.用邻接表表示图进行广度优先遍历时，通常是采用来实现算法的。A．栈B.队列C.树D.图（A）11.深度优先遍历类似于二叉树的A．先序遍历B.中序遍历C.后序遍历D.层次遍历（A）12．折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它将依次与表中比较大小，查找结果是失败。A．20，70，30，50B．30，88，70，50C．20，50D．30，88，50（C）13．若一组记录的排序码为（46,79,56,38,40,84

5、），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为Ａ.38,40,46,56,79,84Ｂ.40,38,46,79,56,84Ｃ.40,38，46,56,79,84Ｄ.40,38,46,84,56,79一、填空题1.数据结构包括数据的逻辑结构、数据的存储结构和数据的运算这三个方面的内容。2.数据的运算最常用的有5种，它们分别是插入、删除、修改、查找、排序。3.向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动n-i+1个元素。4.顺序表中逻辑上相邻的元素的物理位置必定相邻。单链表中逻辑上相邻的元素的物理位

6、置不一定相邻。5.向量、栈和队列都是线性结构，可以在向量的任何位置插入和删除元素；对于栈只能在栈顶插入和删除元素；对于队列只能在队尾插入和队首删除元素。6.一棵具有２５７个结点的完全二叉树，它的深度为9。（注：用ëlog2(n)û+1=ë8.xxû+1=97.设一棵完全二叉树具有1000个结点，则此完全二叉树有500个叶子结点，有499个度为2的结点，有1个结点只有非空左子树，有0个结点只有非空右子树。答：最快方法：用叶子数＝[n/2]＝500，n2=n0-1=499。另外，最后一结点为2i属于左叶子，右叶子是空的，所以有1个非空左子树。完全二叉树

7、的特点决定不可能有左空右不空的情况，所以非空右子树数＝0.8.图有邻接矩阵、邻接表等存储结构，遍历图有深度优先遍历、广度优先遍历等方法。9.有一个表长为m的散列表，初始状态为空，现将n（n

8、序中，若初始数据基本正序，则选用插入；若初始数据基本反序，则选用选择。二、简答题1.说明线性表、栈与队的异同点。答：相同：