第3章数据结构答案解析.doc

《第3章数据结构答案解析.doc》由会员分享，可在线阅读，更多相关《第3章数据结构答案解析.doc（14页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、,第3章 数据结构一、选择题1. 图形结构是数据元素之间存在一种_B_。 A 一对多关系 B 多对多关系 C 多对一关系 D 一对一关系 2.算法分析的目的是_C_。 A 找出数据结构的合理性 B 研究算法中的输入和输出的关系 C 分析算法的效率以求改进 D 分析算法的易懂性和文档性3.算法的时间复杂度与_A_ 有关。 A 问题规模 B 计算机硬件性能 C 程序设计语言的类型或版本 D 算法设计者的水平 4.有下面的算法段：for (i=0; iNext = NULLCLk_h-Next = Lk_hDLk_h != NULL21.在一个单链表中，已知qtr所指结点是ptr所指结点的直接前驱。

2、现要在qtr所指结点和ptr所指结点之间插入一个rtr所指的结点，要执行的操作应该是_C_。Artr-Next = ptr-Next;ptr-Next = rtr;Bptr-Next = rtr-Next;Cqtr-Next = rtr;rtr-Next = ptr;Dptr-Next = rtr;rtr-Next = qtr-Next;22.在单链表中，如果指针ptr所指结点不是链表的尾结点，那么在ptr之后插入由指针qtr所指结点的操作应该是_B_ 。Aqtr-Next = ptr ;Bqtr-Next = ptr-Next ;ptr-Next = qtr ; ptr-Next = qtr

3、 ;Cqtr-Next = ptr-Next ;Dptr-Next = qtr ;ptr = qtr ; qtr-Next = ptr ;23.栈与一般线性表的区别在于_B_。A、数据元素的类型不同 B、运算是否受限制C、数据元素的个数 D、逻辑结构不同24.栈的插入和删除操作在_A_进行。A、栈顶 B、栈底 C、任意位置 D、指定位置25.一个顺序栈一旦被声明，其占用空间大小_A_。A、已固定 B、可以变化 C、不能固定 D、动态变化26.设有一个顺序栈S，元素s1， s2， s3， s4， s5， s6依次进栈，如果6个元素的出栈顺序为s2， s3， s4， s6， s5， s1，则顺序栈

4、的容量至少应为_B_ A 2 B 3 C 4 D 5 27.若让元素1，2，3依次进栈，则出栈次序不可能出现_C_种情况。 A 3，2，1 B 2，1，3 C 3，1，2 D 1，3，2 28.一个栈的入栈序列是abcde，则栈不可能的输出序列是_C_。A、edcba B、decba C、dceab D、abcde29.队列的插入操作是在_B_进行的。A、队首 B、队尾 C、队前 D、队后30.队列的删除操作是在_A_进行的。A、队首 B、队尾 C、队前 D、队后31.为解决计算机主机与打印机间速度不匹配问题，通常设一个打印数据缓冲区。主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲

5、区中取出数据。该缓冲区的逻辑结构应该是 _A_。A.队列B.栈C.线性表D.有序表32.下列关于线性表、栈和队列的叙述，错误的是_A_。 A.线性表是给定的n（n必须大于零）个元素组成的序列。 B.线性表允许在表的任何位置进行插入和删除操作。 C.栈只允许在一端进行插入和删除操作。 D.队列允许在一端进行插入，在令一端进行删除。33.一个队列的入队序列是1,2,3,4，则队列的确定输出序列_B_A. 4,3,2,1B. 1,2,3,4C. 1,4,3,2D. 3,2,4,134.若用一个大小为6的数组来实现循环队列,且当前rear 和front的值分别为0和3.当从队列中删除一个元素,再加入两

6、个元素后, rear 和front的值分别为_B_ A. 1和5 B. 2和4 C. 4和2 D. 5和135.最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是_B_。 A. (rear+1)%n=front B. rear=front C. rear+1=front D. (rear-l)%n=front36.循环队列存储在数组A0.m中，则入队时的操作为_D_。 A. rear=rear+1 B. rear=(rear+1)%(m-1) B. rear=(rear+1)%m D. rear=(rear+1)%(m+1)37.数组用来表示一个循环队列，为当前队列头

7、元素的前一位置，为队尾元素的位置，假定队列中元素的个数小于，计算队列中元素的公式为 _D_ A rf; B （nfr）% n; C nrf; D （nrf）% n 38.一个长度为50的循环队列中，队头指针（front）等于41，队尾指针（rer）等于20，则队列中有_D_个元素。 A 41 B 20 C 21 D 29 39.二维数组M，行下标i的范围从0到4，列下标j的范围从0到5，M按行存储时元素M35的起始地址与M按列存储时元素_B_的起始地址相同。 A、M24 B、M34 C、M35 D、M4440.数组A中，每个元素的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址S

8、A开始连续存放在存储器内，存放该数组至少需要的单元数是_C_A、80 B、100 C、240 D、27041.有一个二维数组mn，按行存储，假设00存放位置在644（10进制），22存放位置在676（10进制），每个元素占一个空间，则45在_C_位置。 A 692 B 626 C 709 D 724 42.数组A中，每个元素的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A85的起始地址为_C_。A、SA+141 B、SA+144 C、SA+222 D、SA+22543.在具有100个结点的树中，其边的数目为_C_。 A 101

9、 B 100 C 99 D 98 44.按照树的定义，具有3个结点的树有_A_种形态。A、2 B、3 C、4 D、545.按照二叉树的定义，具有3个结点的二叉树有_D_种形态。A、2 B、3 C、4 D、546.下面说法中，_D_是正确的。A、度为2的树是二叉树 B、度为2的有序树是二叉树C、子树有严格左、右之分的树是二叉树 D、子树有左、右之分、且度不超过2的树是二叉树47.下面的说法中，_C_是正确的。A、二叉树的度为2 B、二叉树中任意一个结点的度都为2C、任何二叉树中结点度可以小于2 D、任何二叉树中至少有一个结点的度为248.若一棵二叉树有10个度为2的结点，则该二叉树的叶结点的个数

10、_B_。A、9 B、11 C、12 D、不确定49.具有10个叶结点的二叉树中有_A_个度为2的结点。A、9 B、11 C、12 D、不确定50.若一棵满二叉树有2047个结点，则该二叉树中叶结点的个数为_B_。A、512 B、1024 C、2048 D、409651.具有65个结点的完全二叉树的高度为_B_。 A 8 B 7 C 6 D 5 52.深度为5的二叉树至多有_B_个结点。A、16 B、31 C、15 D、3053.在一棵树的左孩子-右兄弟表示法中，一个结点的右孩子是该结点的_A_结点。A、兄弟 B、父子 C、祖先 D、子孙54.在一棵树的双亲表示中，每个数据元素包含_B_个域。A

11、、1 B、2 C、3 D、455.对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用_C_次序的遍历实现编号。A先序 B. 中序 C. 后序 D. 从根开始按层次遍历56.某二叉树中序序列为A,B,C,D,E,F,G，后序序列为B,D,C,A,F,G,E 则前序序列是_B_AE,G,F,A,C,D,B BE,A,C,B,D,G,F CE,A,G,C,F,B,D D上面的都不对 57.二叉树的先序遍历和中序遍历如下： 先序遍历：EFHIGJK；中序遍历: HFIEJKG 。该二叉树根的右子树的根是_C_A、

12、 E B、 F C、 G D、 H 58.把一棵树转换为二叉树后，这棵二叉树的形态是_A_。 A 唯一的 B 有多种，但根结点都没有左孩子 C 有多种 D 有多种，但根结点都没有右孩子59.在一个图中，所有顶点的度数之和等于所有边的数目的_C_倍。A、1/2 B、1 C、2 D、460.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的_B_倍。A、1/2 B、1 C、2 D、461.一个具有n个顶点的无向图最多有_A_条边。A、n（n1）/2 B、n（n1）C、n（n+1）/2 D、nn62.一个具有n个顶点的有向图最多有_B_条边。A、n（n1）/2 B、n（n1）C、n（n+1）

13、/2 D、nn63.一个无向图采用邻接矩阵存储方法，其邻接矩阵一定是一个_A_。A、对称矩阵 B、对角矩阵 C、三角矩阵 D、稀疏矩阵64.具有n个顶点、e条边的无向图采用邻接矩阵存储方法。则邻接矩阵的大小为_D_。A、n B、(n-1) （n+1） C、(n+1) （n+1） D、nn65.通常把查找过程中对关键字需要执行的_C_作为衡量一个查找算法效率优劣的标准。A、BST B、WPL C、ASL D、BFS66.在表长是N的顺序表中，实施顺序查找，在查找不成功时，与关键字比较的次数_C_。A、N B、1 C、N+1 D、N-167.一个顺序存储结构的线性表有255个记录，采用线性查找法（

14、也称顺序查找法）查找该表，在等概率条件下的平均查找长度为_A_。 A 128 B 127 C 126 D 25568.在表长为的链表中进行线性查找，它的平均查找长度为_B_ A B （） C n / 2 D （）69.线性表必须是_B_，才能进行二分查找。A、用数组存储的线性表 B、用数组存储的有序表C、用链表存储的线性表 D、用链表存储的有序表70.有一个顺序表为1，3，9，12，32，41，45，62，75，77，82，95，100，当折半查找值为82的结点时，_A_次比较后查找成功。 A 4 B 2 C 1 D 8 71.链表适用于 _A_ 查找 A 顺序 B 二分法 C 顺序、，也能二

15、分法 D 随机 72. 折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素_A_比较大小。 A 28，6，12，20 B 38,12,20 C 20 D 38,70,88,10073. 折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它将依次与表中 _A_比较大小，查找结果是失败。 A 20，70，30，50 B 30，88，70，50 C 20，50 D 30，88，5074. 对22个记录的有序表作折半查找，当查找失败时，至少需要比较 _C_次关键字。 A 3 B 4 C 5

16、D 6 75. 散列查找是由键值_B_确定散列表中的位置，并进行存储或查找。A、本身 B、散列函数值 C、相反数 D、平方76.设某散列表长度为100，散列函数H(k)k%p, 则P 通常情况下最好选择_C_A、91 B、93 C、97 D、9977. 哈希表的地址区间为0-17，哈希函数为H(k)=k mod 17。采用线性探测法处理冲突，并将关键字序列26,25,72,38,8,18,59依次存储到哈希表中。那么，元素59存放在哈希表中的地址是_D_。A. 8B. 9 C. 10D. 1178. 给定n=8，对数组R中的8个元素做升序排列，数组R中的关键字为：（8，3，2，1，7，4，6，

17、5），则简单选择排序过程中第二趟排序结束后关键字的顺序是_A_ A 1,2,3,8,7,4,6,5 B 1,3,2,8,7,4,6,5 C 1,2,3,4,5,6,8,7 D 1,2,3,4,5,6,7,879.每次从无序表中取出一个元素，把它插入到有序表中的适当位置，此种排序方法叫做_A_排序。A、插入 B、交换 C、选择 D、归并80.有关键字序列20，6，15，7，3，作升序排列，则线性插入排序过程中第三趟排序结束后关键字的顺序是_C_。A 20，6，15，7，3 B 6，20，15，7，3 C 6，15，20，7，3 D 6，7，15，20，381.在各种查找方法中，平均查找长度与结点

18、个数n无关的查找方法是 _C_ A 顺序查找 B 折半查找 C 散列查找 D 线性查找 82.在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是_A_ A 访问第i个结点（1in）和求第i个结点的直接前驱（2in） B 在第i个结点后插入一个新结点（1in） C 删除第i个结点（1in） D 将n个结点从小到大排序83. 数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素的方法以及它们之间的_A_和运算等的学科。A、结构 B、关系 C、运算 D、 算法84.算法的计算量的大小称为计算的_B_。A、效率 B、 复杂性 C、 现实性 D、 难度85. 以下数据结构中，_A_ 是非线

19、性数据结构A、树 B、字符串 C、队 D、栈86.线性表元素之间的关系是_A_ 。A、 一对一 B、 一对多 C、多对多 D、无关系87. 下列四种基本的逻辑结构中，结构结点间不存在任何逻辑联系的是_A_ 。A、集合 B、线性结构 C、树形结构 D、图形结构88. _D_不是线性表的特性。A、除第一个元素之外，每个元素都有前驱 B、除最后一个元素外，每个元素都有后继 C、线性表是数据的有限序列 D、线性表的长度为n，且n089、下列关于线性表存储结构的叙述中正确的是_D_。A、链表中的元素一定存放在不连续的存储空间里 B、链表中的元素一定存放在连续的存储空间里 C、长度变化频繁的线性表最好采用

20、顺序存储结构 D、链表不能进行随机存取90. 设计一个判别表达式中左、右括号是否配对出现的算法，采用_B_数据结构最佳。A、线性表的顺序存储结构 B、栈 C、队列 D、线性表的链式存储结构二、简答题1. 在如下数组A中链接存储了一个线性表，表头指针为A 0.next，试写出该线性表。 A 0 1 2 3 4 5 6 7 data605078903440next3572041A0 A3 A2 A7 A1 A5 A4 A0答案： 线性表为：（78，50，40，60，34，90）2.设一组初始关键字序列为(38，65，97，76，13，27，10)，则第3趟冒泡排序结束后的结果为_。答案： (38，

21、13，27，10，65，76，97)3.设一组初始关键字序列为(38，65，97，76，13，27，10)，则第3趟简单选择排序后的结果为_。1. 答案：(10，13，27，76，65，97，38)4设一组初始记录关键字序列为(45，80，48，40，22，78)，则分别给出第4趟简7.单选择排序和第4趟直接插入排序后的结果。答案：(22，40，45，48，80，78)，(40，45，48，80，22，78)5. 设一棵完全二叉树的顺序存储结构里存储数据元素为ABCDEF，则该二叉树的前序遍历序列为_，中序遍历序列为_，后序遍历序列为_。答案：ABDECF，DBEAFC，DEBFCA6.已知二叉树的前序遍历序列是AEFBGCDHIKJ，中序遍历序列是EFAGBCHKIJD，画出此二叉树.答案：7. 请画出下图的邻接矩阵和邻接表。答案： 邻接矩阵： 邻接表如图所示：