《2022年数据结构参考答案整理 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构参考答案整理 .pdf（15页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1 数据结构模拟卷A 一、选择题1.在一个长度为n 的顺序表的任一位置插入一个新元素的渐进时间复杂度为（ A ） 。A. O(n) B. O(n/2) C. O(1) D. O(n2) 2.带头结点的单链表first为空的判定条件是： （ B ） 。A. first = NULL; B. first-link = NULL; C. first-link = first; D. first != NULL; 3. 从逻辑上可以把数据结构分为（ C ）两大类。A动态结构、静态结构B 顺序结构、链式结构C线性结构、非线性结构 D初等结构、构造型结构4.在系统实现递归调用时需利用递归工作记录保存实际参
2、数的值。在传值参数情形，需为对应形式参数分配空间，以存放实际参数的副本；在引用参数情形，需保存实际参数的（ D ） ，在被调用程序中可直接操纵实际参数。A. 空间B. 副本C. 返回地址D. 地址5. 以下数据结构中，哪一个是线性结构（ D ） 。A广义表 B. 二叉树 C. 稀疏矩阵 D. 串6. 以下属于逻辑结构的是（ C ） 。A顺序表 B. 哈希表 C.有序表 D. 单链表7.对于长度为9 的有序顺序表， 若采用折半搜索，在等概率情况下搜索成功的平均搜索长度为（ C ）的值除以9。 A. 20 B. 18 C. 25 D. 22 8.在有向图中每个顶点的度等于该顶点的（ C ） 。A.
3、 入度 B. 出度C. 入度与出度之和D. 入度与出度之差9.在基于排序码比较的排序算法中，（ C ）算法的最坏情况下的时间复杂度不高于O(nlog2n)。A. 起泡排序B. 希尔排序C. 归并排序D. 快速排序10. 当 的值较小时，散列存储通常比其他存储方式具有（ B ）的查找速度。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 15 页 - - - - - - - - - 2 A. 较慢B. 较快C. 相同 D.不同二、填空题1.二维数组是一种非线性结构，其中的每一
4、个数组元素最多有_2_个直接前驱 （或直接后继）。2.将一个 n 阶三对角矩阵A 的三条对角线上的元素按行压缩存放于一个一维数组B 中，A00存放于 B0 中。对于任意给定数组元素BK ，它应是A中第 _ (K+1)/3_行的元素。3.链表对于数据元素的插入和删除不需移动结点，只需改变相关结点的_指针 _域的值。4.在一个链式栈中，若栈顶指针等于NULL则为 _空栈 _。5.主程序第一次调用递归函数被称为外部调用，递归函数自己调用自己被称为内部调用，它们都需要利用栈保存调用后的_返回 _地址。6.在一棵树中， _叶子 _结点没有后继结点。7.一棵树的广义表表示为a (b (c, d (e, f
5、), g (h) ), i (j, k (x, y) ) )，结点f的层数为 _3_。假定根结点的层数为0。8.在一棵 AVL树（高度平衡的二叉搜索树）中，每个结点的左子树高度与右子树高度之差的绝对值不超过_1_。9.n (n 0) 个顶点的无向图最多有_ n(n- 1)/2_条边，最少有 _0_条边。10. 在索引存储中，若一个索引项对应数据对象表中的一个表项（记录），则称此索引为_稠密 _索引，若对应数据对象表中的若干个表项，则称此索引为_稀疏 _索引。三、判断题1.数组是一种复杂的数据结构，数组元素之间的关系既不是线性的也不是树形的( 对) 2.链式存储在插入和删除时需要保持物理存储空间
6、的顺序分配，不需要保持数据元素之间的逻辑顺序 ( 错) 3.在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针( 对) 4.通常递归的算法简单、易懂、容易编写，而且执行的效率也高( 错) 5.一个广义表的表尾总是一个广义表( 对) 6.当从一个小根堆（最小堆）中删除一个元素时，需要把堆尾元素填补到堆顶位置，然后再按条件把它逐层向下调整，直到调整到合适位置为止( 对) 7.对于一棵具有n 个结点，其高度为h 的二叉树，进行任一种次序遍历的时间复杂度为O(h)(错) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - -
7、 名师精心整理 - - - - - - - 第 2 页，共 15 页 - - - - - - - - - 3 8.存储图的邻接矩阵中，邻接矩阵的大小不但与图的顶点个数有关，而且与图的边数也有关 ( 错) 9.直接选择排序是一种稳定的排序方法( 错 ) 10. 闭散列法通常比开散列法时间效率更高( 错) 四、运算题1.设有一个 10 10 的对称矩阵A， 将其下三角部分按行存放在一个一维数组B中，A00存放于 B0 中，那么 A85存放于 B中什么位置。解：根据题意，矩阵A 中当元素下标I 与 J 满足 IJ 时，任意元素AIJ 在一维数组B 中的存放位置为I * (I + 1) / 2 + J
8、 ，因此， A85 在数组 B 中位置为8 * (8 + 1) / 2 + 5 = 41 。2.这是一个统计单链表中结点的值等于给定值x 的结点数的算法，其中while 循环有错，请重新编写出正确的while 循环。int count ( ListNode * Ha, ElemType x ) / Ha为不带头结点的单链表的头指针int n = 0; while ( Ha-link != NULL ) Ha = Ha-link; if ( Ha-data = x ) n+; return n; 解：while ( Ha != NULL ) if ( Ha- data = x ) n+;Ha =
9、 Ha- link ; 3.已知一棵二叉树的前序和中序序列，求该二叉树的后序序列。前序序列： A, B, C, D, E, F, G, H, I, J 中序序列： C, B, A, E, F, D, I, H, J, G 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 15 页 - - - - - - - - - 4 后序序列：解： 后序序列： C, B, F, E, I, J, H, G, D, A4.已知一个有序表 ( 15, 26, 34, 39, 45, 56,
10、58, 63, 74, 76, 83, 94 ) 顺序存储于一维数组 a12 中，根据折半搜索过程填写成功搜索下表中所给元素34, 56, 58, 63, 94时的比较次数。元素值比较次数解：判断结果元素值比较次数5.设散列表为HT17, 待插入关键码序列为 Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec ，散列函数为H (key) = i 2 ，其中， i 是关键码第一个字母在字母表中的序号。现采用线性探查法解决冲突。字母A B C D E F G H I J K L M 序号1 2 3 4 5 6 7 8 9 10
11、11 12 13 字母N O P Q R S T U V W X Y Z 序号14 15 16 17 18 19 20 21 22 23 24 25 26 (1) 试画出相应的散列表；H(Jan) = 10 2 = 5，成功 . H(Feb) = 6 2 = 3，成功 . H(Mar) = 13 2 = 6，成功 . H(Apr) = 1 2 = 0，成功 . H(May) = 13 2 = 6，= 7，成功，H(June) = 10 2 = 5，= 6， = 7，=8，成功 . H(July) = 10 2 = 5，= 6，= 7，= 8，= 9，成功 . H(Aug) = 1 2 = 0，
12、= 1，成功 . H(Sep) = 19 2 = 9，= 10，成功 . H(Oct) = 15 2 = 7， = 8，= 9，= 10，= 11，成功 . H(Nov) = 14 2 = 7，= 8，= 9，= 10，= 11， = 12，成功 . H(Dec) = 4 2 = 2，成功 . (1) 相应的散列表：0 1 2 3 4 5 6 7 8 9 10 11 12 13 Apr Aug Dec Feb Jan Mar May June July Sep Oct Nov (1) (2) (1) (1) (1) (1) (2) (4) (5) (2) (5) (6) 34 56 58 63
13、 94 34 56 58 63 94 02 1 3 4 4 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 15 页 - - - - - - - - - 5 (2) 计算等概率下搜索成功的平均搜索长度；1/12 * (1 + 2 + 1 + 1 + 1 + 1 + 2 + 4 + 5 + 2 + 5 + 6) = 31 / 12五、算法设计题已知二叉树中的结点类型用BinTreeNode 表示，被定义为: struct BTreeNode char data; BinTr
14、eeNode *leftChild, *rightChild; ;其中 data为结点值域， leftChild和 rightChild分别为指向左、右子女结点的指针域，根据下面函数声明编写出求一棵二叉树中结点总数的算法，该总数值由函数返回。假定参数BT初始指向这棵二叉树的根结点。 int BTreeCount ( BinTreeNode* BT ); 解： int BTreeCount ( BinTreeNode* BT ) if ( BT = NULL ) return 0;/2 分else return BTreeCount ( BT - leftChild ) + BTreeCount
15、 ( BT- rightChild ) + 1 ;/4 分 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 15 页 - - - - - - - - - 6 数据结构模拟卷 B 一、单项选择题1以下与数据的存储结构无关的术语是（ C ） 。A循环队列 B. 链表 C. 哈希表 D. 栈2以下数据结构中，哪一个是线性结构（ D ） 。A广义表 B. 二叉树 C. 稀疏矩阵 D. 串3以下那一个术语与数据的存储结构无关？（ B ） 。A栈 B. 哈希表 C. 线索树 D. 双
16、向链表4在下面的程序段中，对x 的赋值语句的频度为（ C ） 。FOR i:=1 TO n DO FOR j:=1 TO n DO x:=x+1; A O(2n) BO(n) CO(n2) DO(log2n) 5. 下面关于线性表的叙述中，错误的是哪一个（ B ） 。A线性表采用顺序存储，必须占用一片连续的存储单元。B线性表采用顺序存储，便于进行插入和删除操作。C线性表采用链接存储，不必占用一片连续的存储单元。D线性表采用链接存储，便于插入和删除操作。6线性表是具有n 个（ C ）的有限序列（n0） 。A表元素 B字符 C数据元素 D数据项 E信息项7. 若某线性表最常用的操作是存取任一指定序
17、号的元素和在最后进行插入和删除运算，则利用（ A ）存储方式最节省时间。A顺序表 B双链表 C带头结点的双循环链表 D单循环链表8. 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ D ）存储方式最节省运算时间。A单链表 B仅有头指针的单循环链表 C双链表 D仅有尾指针的单循环链表9. 下面给出的四种排序法中( D )排序法是不稳定性排序法。A. 插入 B. 冒泡 C. 二路归并 D. 堆积名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共
18、15 页 - - - - - - - - - 7 E F D G A B / + + * - C * 10. 下列排序算法中，其中（ D ）是稳定的。A. 堆排序，冒泡排序 B. 快速排序，堆排序 C. 直接选择排序，归并排序 D. 归并排序，冒泡排序11. 已知一算术表达式的中缀形式为 A+B*C-D/E ，后缀形式为ABC*+DE/-，其前缀形式为( D )。A-A+B*C/DE B. -A+B*CD/E C-+*ABC/DE D. -+A*BC/DE 12. 算术表达式a+b*（c+d/e ）转为后缀表达式后为（ B ） 。Aab+cde/* Babcde/+*+ Cabcde/*+ D
19、abcde*/+ 二、填空题，在横线处填写合适内容1. 数据结构的存储结构包括顺序、_链接 _、索引和散列等四种。2. 在程序运行过程中可以扩充的数组是_动态 _分配的数组。 这种数组在声明它时需要使用数组指针。3. 在链表中进行插入和删除操作的效率比在顺序存储结构中进行相同操作的效率高。4. 栈是一种限定在表的一端进行插入和删除的线性表，又被称为_后出先进 _表。5. 如果一个对象部分地包含自己，或自己定义自己，则称这个对象是_递归 _的对象。6. 一 棵 树 的 广 义 表 表 示 为a(b(c,d(e,f),g(h),i(j,k(x,y)， 结 点f的 层 数 为_3_。假定树根结点的层
20、数为0。7. 一棵树按照左子女- 右兄弟表示法转换成对应的二叉树，则该二叉树中树根结点肯定没有_右_子女。8. 向一棵二叉搜索树中插入一个元素时，若元素的值小于根结点的值，则应把它插入到根结点的 _左子树 _上。9. 设图 G=(V,E) ，V=1,2,3,4, E=,，从顶点1 出发，对图G进行广度优先搜索的序列有_2_种。10. 每次直接或通过基准元素间接比较两个元素，若出现逆序排列就交换它们的位置，这种排序方法叫做 _交换 _排序。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第
21、 7 页，共 15 页 - - - - - - - - - 8 11. 快速排序在平均情况下的空间复杂度为_ O(log2n) _ 。12. 若对长度 n=10000 的线性表进行二级索引存储，每级索引表中的索引项是下一级20 个表项的索引，则一级索引表的长度为_500_。三、判断题1. 在顺序表中进行顺序搜索时，若各元素的搜索概率不等，则各元素应按照搜索概率的降序排列存放，则可得到最小的平均搜索长度（对）2. 在二叉搜索树中，若各结点的搜索概率不等，使得搜索概率越小的结点离树根越近，则得到的是最优二叉搜索树（错）3. 对于 AOE网络，加速任一关键活动都能使整个工程提前完成（错）4. 直接选
22、择排序是一种稳定的排序方法（错）5. 闭散列法通常比开散列法时间效率更高（错）6. 数据的逻辑结构是指各数据元素之间的逻辑关系，是用户根据应用需要建立的（对）7. 顺序表和一维数组一样，都可以按下标随机（或直接）访问（对）8. 在一个顺序存储的循环队列中, 队头指针指向队头元素的后一个位置（错）9. 用非递归方法实现递归算法时一定要使用递归工作栈（错）10. 在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行中序遍历和后序遍历，则具有相同的结果（对）四、运算题1. 设有一个二维数组A1020，按行存放于一个连续的存储空间中，A00的存储地址是 200，每个数组元素占1 个存储字，
23、则A62的存储字地址是多少。 A62的存储字地址：322 答案说明：按行存储时，计算Aij地址的公式为 LOC(i,j)=LOC(0,0)+(i*n+j)*d 其中首地址LOC(0,0)=200, 每个数组元素的存储占用数d=1, 二维数组的列数n=20，根据题意，元素A62的存储地址为 LOC(6,2)=200+(6*20+2)*1=322 2. 已知一棵二叉树的中序和后序序列如下，求该二叉树的高度（假定空树的高度为-1）和度为 2、度为 1 及度为 0 的结点个数。中序序列： c,b,d,e,a,g,i,h,j,f 名师资料总结 - - -精品资料欢迎下载 - - - - - - - -
24、- - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 15 页 - - - - - - - - - 9 后序序列： c,e,d,b,i,j,h,g,f,a 求解一下问题：高度： 4 度为 2 的结点数： 3 度为 1 的结点数： 3 度为 0 的结点数： 4 3. 假定一组记录为(36,75,83,54,12,67,60,40)， 将按次序把每个结点插入到初始为空的一棵 AVL树中，请回答在插入时需进行“左单旋转”、 “右单旋转” 、 “先左后右双旋转” 、 “先右后左双旋转” ， “不调整”的结点数各是多少？左单旋转结点个数： 1 右单旋转结点个数
25、：0 先左后右双旋转结点个数： 1 先右后左双旋转结点个数：0 不调整结点个数：6 4. 已知一个带权图的顶点集V和边集 G分别为： V=0,1,2,3,4,5,6; E=(0,1)19,(0,2)10,(0,3)14,(1,2)6,(1,5)5,(2,3)26,(2,4)15,(3,4)18, (4,5)6,(4,6)6,(5,6)12; 试根据迪克斯特拉(Dijkstra)算法求出从顶点0 到其余各顶点的最短路径，在下面填写对应的路径长度。顶点： 0 1 2 3 4 5 6 路径长度：5. 已知一个数据表为36,25,25*,62,40,53，请写出在进行快速排序的过程中每次划分后数据表的
26、变化。 0 16 10 14 25 21 31 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 15 页 - - - - - - - - - 10 (0) 36 25 25* 62 40 53 (1) 25* 25 36 62 40 53 (2) 25* 25 36 53 40 62 (3) 25* 25 36 40 53 62 五、算法设计题1设有一个表头为first的单链表。试设计一个算法，通过遍历一趟链表，将链表中所有结点按逆序链接。解答 1 template vo
27、id List : : Tnerse() if (first= NULL )return ; ListNode * p=firstlink ; , *pr =NULL ; While (p !=NULL ) Firstlink =pr ; Pr =first ;first =p ;p =p link; first -link =pr ; 解答 2 template void List : : Tnerse() ListNode * p , *head = new ListNode ( ) ; While (first ! = NULL ) P=first ;first = first link
28、; plink =head link ; head link =p; first = head link ; delete head ; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 15 页 - - - - - - - - - 11 数据结构模拟卷 C 一、单项选择题1数据结构是（D ） 。A一种数据类型B数据的存储结构C一组性质相同的数据元素的集合D相互之间存在一种或多种特定关系的数据元素的集合2算法分析的目的是（B ） 。A辨别数据结构的合理性B评价算法的效率C
29、研究算法中输入与输出的关系D鉴别算法的可读性3在线性表的下列运算中，不改变数据元素之间结构关系的运算是（D ） 。A插入B删除C排序D定位4若进栈序列为1，2， 3，4，5， 6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为（B ） 。A3，2，6，1，4，5 B3，4，2，1，6，5 C1，2，5，3，4，6 D5，6，4，2，3，1 5设串sl= Data Structures with Java,s2= it ，则子串定位函数index(s1,s2)的值为（D ） 。A15 B16 C17 D18 6二维数组A89按行优先顺序存储，若数组元素A23的存储地址为1087，A47的存储地
30、址为1153，则数组元素A67的存储地址为（A ） 。A1207 B1209 C1211 D1213 7在按层次遍历二叉树的算法中，需要借助的辅助数据结构是（A ） 。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 15 页 - - - - - - - - - 12 A队列B栈C线性表D有序表8在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系（B ） 。A不一定相同B都相同C都不相同D互为逆序9若采用孩子兄弟链表作为树的存储结构，则树的后序遍历应采用二叉
31、树的（C ） 。A层次遍历算法B前序遍历算法C中序遍历算法D后序遍历算法10若用邻接矩阵表示一个有向图，则其中每一列包含的1的个数为（A ） 。A图中每个顶点的入度B图中每个顶点的出度C图中弧的条数D图中连通分量的数目11图的邻接矩阵表示法适用于表示（C ） 。A无向图B有向图C稠密图D稀疏图12 在对 n 个关键字进行直接选择排序的过程中，每一趟都要从无序区选出最小关键字元素，则在进行第i 趟排序之前，无序区中关键字元素的个数为（D ） 。Ai Bi+1 Cn-i Dn-i+1 二、填空题1栈是 _特殊 _的线性表，其运算遵循_后进先出 _的原则。2_栈_是限定仅在表尾进行插入或删除操作的线
32、性表。3. 一个栈的输入序列是：1，2，3 则不可能的栈输出序列是_3，1，2_。4二叉树由 _根结点、左子树、右子树_三个基本单元组成。5 在二叉树中， 指针 p 所指结点为叶子结点的条件是P-Lchild=NULL & P-Rchild=NULL _。6具有 256 个结点的完全二叉树的深度为_9_。7已知一棵度为3 的树有 2 个度为 1 的结点， 3 个度为 2 的结点， 4 个度为 3 的结点， 则该树有 _12_个叶子结点。8若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的_比较 _和记录的 _移动 _。名师资料总结 - - -精品资料欢迎下载 - - - - -
33、 - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 15 页 - - - - - - - - - 13 9. 分别采用堆排序，快速排序， 冒泡排序和归并排序，对初态为有序的表，则最省时间的是_冒泡排序 _算法，最费时间的是_快速排序 _算法。10不受待排序初始序列的影响，时间复杂度为O(N2) 的排序算法是_选择排序 _，在排序算法的最后一趟开始之前，所有元素都可能不在其最终位置上的排序算法是_归并排序 _。三、解答题1某广义表的表头和表尾均为（a,(b,c)） ，画出该广义表的图形表示。2已知二叉树的先序序列和中序序列分别为HDA
34、CBGFE 和 ADCBHFEG。（1）画出该二叉树；（2）画出与（ 1）求得的二叉树对应的森林。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 15 页 - - - - - - - - - 14 3已知带权图的邻接表如下所示，其中边表结点的结构为：依此邻接表从顶点C出发进行深度优先遍历。（1）画出由此得到的深度优先生成树；（2）写出遍历过程中得到的从顶点C到其它各顶点的带权路径及其长度。顶点 C到顶点 A的带权路径为（C，D，B ， A） ，其长度为8+20+11=3
35、9 顶点 C到顶点 B的带权路径为（C，D，B） ，其长度为8+20=28 顶点 C到顶点 D的带权路径为（C，D） ，其长度为8 顶点 C到顶点 E的带权路径为（C，D，B ， F,E） ，其长度为8+20+9+14=51 顶点 C到顶点 F 的带权路径为（C，D，B ， F） ，其长度为8+20+9=37 四、算法设计题1已知中序线索二叉树T 右子树不空。设计算法，将S所指的结点作为T 的右子树中的一个叶子结点插入进去，并使之成为T 的右子树的（中序序列）第一个结点（同时要修改相应的线索关系） 。insertS(BiThrTree T) p=T-lchild; /T是线索二叉树T 的头结点
36、， p 指向根节点if(p-RTag=1) return ERROR; /右标记是线索，即右子树为空则返回错误p=p-rchild ; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 15 页 - - - - - - - - - 15 while(p-LTag=0) /当 p 节点的左标记是孩子时,p 指向 p 的左孩子 p=p-lchild; S-LTag=1; S-RTag=1; /S的左右标记都为线索S-lchild=p-lchild; S-rchild=p; p
37、-lchild=S; p-LTag=0; return OK; 2写出在中序线索二叉树里；找指定结点在后序下的前驱结点的算法。/指定节点为S, F 是它在后序下的前驱结点,thrt是头结点指针qianqu(BiTreTree thrt) if （S-RTag=0）/ 有右子树F=S-Rchild; else if (S-LTag=0) /无右子树但有左子树F=S-Lchild else /叶子节点p=S; while(p-LTag=1) p=p-Lchild; if(p!=thrt) thrt 是头结点指针F=p-Lchild; else F=NIL; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 15 页 - - - - - - - - -