《课堂练习学生答案》由会员分享，可在线阅读，更多相关《课堂练习学生答案（6页珍藏版）》请在金锄头文库上搜索。
1、课堂练习一、选择题（ C ）1. 数据结构中，与所使用的计算机无关的是数据的( )结构；A、 存储 B、 物理 C、逻辑 D、物理和存储（ B ）2. 计算机算法必须具备输入、输出和 等 5 个特性。 A) 可行性、可移植性和可扩充性 B) 可行性、确定性和有穷性 C) 确定性、有穷性和稳定性 D) 易读性、稳定性和安全性 （ A ）3. 在 n 个结点的顺序表中，算法的时间复杂度是 O（1）的操作是： （A） 访问第 i 个结点（1in）和求第 i 个结点的直接前驱（2in） （B） 在第 i 个结点后插入一个新结点（1in） （C） 删除第 i 个结点（1in） （D） 将 n 个结点从小
2、到大排序 （ D ）4. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址: （A）必须是连续的 （B）部分地址必须是连续的 （C）一定是不连续的 （D）连续或不连续都可以 （ B ）5. 判定一个栈 ST（最多元素为 m0）为空的条件是ST-toptop=0 ST-toptop=m0 （ D ）6数组用来表示一个循环队列，为当前队列头元素的前一位置，为队 尾元素的位置，假定队列中元素的个数小于，计算队列中元素的公式为 （）rf; （） （nfr）% n; （）nrf; （） （nrf）% n （ A ）7. 假设有 60 行 70 列的二维数组 a160, 170以列序为主序顺序存储
3、，其基地址为 10000，每个元素占 2 个存储单元，那么第 32 行第 58 列的元素 a32,58的存储地址为 。 （无第 0 行第 0 列元素）16902 16904 14454 答案 A, B, C 均不对 答：（答：（57 列列60 行行31 行）行）2 字节字节10000=16902 （ C ）8二叉树是非线性数据结构，所以二叉树是非线性数据结构，所以 。 （）它不能用顺序存储结构存储（）它不能用顺序存储结构存储; （）它不能用链式存储结构存储（）它不能用链式存储结构存储; （）顺序存储结构和链式存储结构都能存储（）顺序存储结构和链式存储结构都能存储; （）顺序存储结构和链式存储结
4、构（）顺序存储结构和链式存储结构 都不能使用都不能使用 （ A ）9把一棵树转换为二叉树后，这棵二叉树的形态是把一棵树转换为二叉树后，这棵二叉树的形态是 。 （）唯一的（）唯一的 （）有多种（）有多种 （）有多种，但根结点都没有左孩子（）有多种，但根结点都没有左孩子 （）有多种，但根结点都没有右孩子（）有多种，但根结点都没有右孩子（ B ）10. 用邻接表表示图进行广度优先遍历时，通常是采用用邻接表表示图进行广度优先遍历时，通常是采用 来实现算法的。来实现算法的。 A栈栈 B. 队列队列 C. 树树 D. 图图 （ A ）11. 深度优先遍历类似于二叉树的深度优先遍历类似于二叉树的 A先序遍历
5、先序遍历 B. 中序遍历中序遍历 C. 后序遍历后序遍历 D. 层次遍历层次遍历（ A ）12折半查找有序表（折半查找有序表（4，6，10，12，20，30，50，70，88，100） 。若查找表中元素。若查找表中元素 58，则它将依次与表中，则它将依次与表中 比较大小，查找结果是失败。比较大小，查找结果是失败。 A20，70，30，50 B30，88，70，50 C20，50 D30，88，50（ C ）13 若一组记录的排序码为（若一组记录的排序码为（46, 79, 56, 38, 40, 84） ，则利用快速排序的方法，以第，则利用快速排序的方法，以第 一个记录为基准得到的一次划分结果为
6、一个记录为基准得到的一次划分结果为 . 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 个元素(1in+1)之前插入一个元素时，需向后移动 n-i+1 个 元素。 4. 顺序表中逻辑上相邻的元素的物理位置 必定相邻。单链表中逻辑
7、上相邻的元素的物理位置 不一定 相邻。 5. 向量、栈和队列都是 线性 结构，可以在向量的 任何 位置插入和删除元素；对于 栈只能在 栈顶 插入和删除元素；对于队列只能在 队尾 插入和 队首 删除元素。6. 一棵具有个结点的完全二叉树，它的深度为一棵具有个结点的完全二叉树，它的深度为 9 。 （ 注：用注：用 log2(n) +1= 8.xx +1=9 7. 设一棵完全二叉树具有设一棵完全二叉树具有 1000 个结点，则此完全二叉树有个结点，则此完全二叉树有 500 个叶子结点，有个叶子结点，有 499 个度个度 为为 2 的结点，有的结点，有 1 个结点只有非空左子树，有个结点只有非空左子树
8、，有 0 个结点只有非空右子树。个结点只有非空右子树。 答：最快方法：用叶子数n/2500 ，n2=n0-1=499。 另外，最后一结点为 2i 属于左叶子，右 叶子是空的，所以有 1 个非空左子树。完全二叉树的特点决定不可能有左空右不空的情况，所以 非空右子树数非空右子树数0. 8. 图有图有 邻接矩阵邻接矩阵 、 邻接表邻接表 等存储结构，遍历图有等存储结构，遍历图有 深度优先遍历深度优先遍历 、 广度优先遍历广度优先遍历 等方法。等方法。9. 有一个表长为有一个表长为 m 的散列表，初始状态为空，现将的散列表，初始状态为空，现将 n（nnext,*s;L-next=null; （1）_将
9、单链表头结点取出，指针域赋空值_while (p) s=p-next; p-next=L-next; L-next=p; （2）_将 P 所指的结点链接到头结点后面_p=s; 答：该算法的功能是：将带头结点的单链表 L 就地逆置。四、应用题1、分析下面各程序段的时间复杂度分析下面各程序段的时间复杂度（1）下面程序段的时间复杂度为（ ） 。for(int i=0;im;i+)for(int j=0;jn;j+)aij=i*j;（2）执行下面程序段时，S 语句的执行次数为（ ） 。for(int i=1;i=n;i+)for(int j=1,j=i;j+)S;答：O（m*n） n(n+1)/2 2
10、. 用三元组表表示下列稀疏矩阵：2000000000000005000000000006000000000000030008000000000000000000) 1 (000003000000000500000000000009200000)2(解：参见填空题 4. 三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数 据项，分别表示该元素的 行下标 、 列下标 和 元素值 。 所以（1）可列表为： （2）可列表为：8853233685467858123. 用 5 个权值3, 2, 4, 5, 1构造的哈夫曼（Huffman）树的带权路径长度是 33 。 解：先构造哈夫曼树，得
11、到各叶子的路径长度之后便可求出解：先构造哈夫曼树，得到各叶子的路径长度之后便可求出 WPL（453）2（12）3=33(15) (9) (6) 注：两个合并值先后不同会导致编码不同，即哈夫曼编码不唯一）注：两个合并值先后不同会导致编码不同，即哈夫曼编码不唯一）4 5 3 (3) （注：合并值应排在叶子值之后）（注：合并值应排在叶子值之后） 1 24. 已知如图所示的有向图，请给出该图的已知如图所示的有向图，请给出该图的: （1）每个顶点的入每个顶点的入/出度；出度； （2）邻接矩阵；邻接矩阵； （3）邻接表；邻接表；答案：答案：66416-2259435653顶点123456入度出度地址值链接
12、指针022116624133084,74305536467018319105.已知如下所示长度为已知如下所示长度为 12 的表：的表： （Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec） (1) 试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成之后的二叉排序树，试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成之后的二叉排序树， 并求其在等概率的情况下查找成功的平均查找长度。并求其在等概率的情况下查找成功的平均查找长度。 (2) 若对表中元素先进行排序构成有序表，求在等概率的情况下对此有序表
13、进行折半查找时查找若对表中元素先进行排序构成有序表，求在等概率的情况下对此有序表进行折半查找时查找 成功的平均查找长度。成功的平均查找长度。 解：解：(2)经排序后的表及在折半查找时找到表中元素所经比较的次数对照表： Apr Aug Dec Feb, Jan July June Mar May Nov Oct, Sep 3 4 2 3 4 1 3 4 2 4 3 4 等概率情况下查找成功时的平均查找长度为等概率情况下查找成功时的平均查找长度为:ASL=1/12(1*1+2*2+3*4+4*5)=37/12 6. 选取散列函数选取散列函数 H（key）=（3*key）%11，用线性探测法处理冲突，对下列关键码序列构造，用线性探测法处理冲突，对下列关键码序列构造 一个散列地址空间为一个散列地址空间为 010，表长为，表长为 11 的散列表，的散列表， 22，41，53，08，46，30，01，31，66。 解：由题意知，解：由题意知，m=11(刚好为素数刚好为素数) 则则(22*3)%11=60 (41*3)%11=112(53*3)%11=145 (08*3)%11=22 (46*3)%11=126(30*3)%11=82 (01*3)%11=03 (31*3)%11=85 (66*3)%11=902266418305346131012345678
