数据结构参考答案.pdf

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

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 ）的查找速度。吾日三省乎吾身。为人谋而不忠乎？与朋友交而不信乎？传不习乎？论语丈夫志四方，有事先悬弧，焉能钧三江，终年守菰蒲。顾炎武A.较慢 B.较快 C.相同 D.不同 二、填空题 1.二维数组是一种非线性结构，其中的每一个数组元素最多有_2_个直接前驱（或直接后继）。2.将一个 n 阶三对角矩阵 A 的三条对角线上的元素按行压缩存放

4、于一个一维数组 B 中，A00存放于 B0中。对于任意给定数组元素 BK，它应是 A 中第_(K+1)/3 _行的元素。3.链表对于数据元素的插入和删除不需移动结点，只需改变相关结点的_指针_域的值。4.在一个链式栈中，若栈顶指针等于 NULL 则为_空栈_。5.主程序第一次调用递归函数被称为外部调用，递归函数自己调用自己被称为内部调用，它们都需要利用栈保存调用后的_返回_地址。6.在一棵树中，_叶子_结点没有后继结点。7.一棵树的广义表表示为 a(b(c,d(e,f),g(h),i(j,k(x,y)，结点 f的层数为_3_。假定根结点的层数为 0。8.在一棵 AVL 树（高度平衡的二叉搜索树

5、）中，每个结点的左子树高度与右子树高度之差的绝对值不超过_1_。9.n(n0)个顶点的无向图最多有_ n(n-1)/2_条边，最少有_0_条边。10.在索引存储中，若一个索引项对应数据对象表中的一个表项（记录），则称此索引为_稠密_索引，若对应数据对象表中的若干个表项，则称此索引为_稀疏_索引。三、判断题 1.数组是一种复杂的数据结构，数组元素之间的关系既不是线性的也不是树形的(对)2.链式存储在插入和删除时需要保持物理存储空间的顺序分配，不需要保持数据元素之间的逻辑顺序(错)3.在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针(对)4.通常递归的算法简单、易懂、容易编写

6、，而且执行的效率也高(错)5.一个广义表的表尾总是一个广义表(对)6.当从一个小根堆（最小堆）中删除一个元素时，需要把堆尾元素填补到堆顶位置，然后再按条件把它逐层向下调整，直到调整到合适位置为止(对)7.对于一棵具有 n 个结点，其高度为 h 的二叉树，进行任一种次序遍历的时间复杂度为O(h)(错)老当益壮，宁移白首之心；穷且益坚，不坠青云之志。唐王勃海纳百川，有容乃大；壁立千仞，无欲则刚。林则徐8.存储图的邻接矩阵中，邻接矩阵的大小不但与图的顶点个数有关，而且与图的边数也有关(错)9.直接选择排序是一种稳定的排序方法(错)10.闭散列法通常比开散列法时间效率更高(错)四、运算题 1.设有一个

7、 1010 的对称矩阵 A，将其下三角部分按行存放在一个一维数组 B 中，A00存放于 B0中，那么 A85存放于 B 中什么位置。解：根据题意，矩阵 A 中当元素下标 I 与 J 满足 IJ 时，任意元素 AIJ在一维数组 B中的存放位置为 I*(I+1)/2+J，因此，A85在数组 B 中位置为 8*(8+1)/2+5=41。2.这是一个统计单链表中结点的值等于给定值 x 的结点数的算法，其中 while 循环有错，请重新编写出正确的 while 循环。int count(ListNode*Ha,ElemType x)/Ha 为不带头结点的单链表的头指针 int n=0;while(Ha-

8、link!=NULL)Ha=Ha-link;if(Ha-data=x)n+;return n;解：while(Ha!=NULL)if(Ha-data=x)n+;Ha=Ha-link;3.已知一棵二叉树的前序和中序序列，求该二叉树的后序序列。前序序列：A,B,C,D,E,F,G,H,I,J 中序序列：C,B,A,E,F,D,I,H,J,G 人之为学，不日进则日退，独学无友，则孤陋而难成；久处一方，则习染而不自觉。顾炎武忍一句，息一怒，饶一着，退一步。增广贤文 后序序列：解：后序序列：C,B,F,E,I,J,H,G,D,A 4.已知一个有序表(15,26,34,39,45,56,58,63,74,

9、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 12 13 字母 N O P Q R S T U V

10、 W X Y Z 序号 14 15 16 17 18 19 20 21 22 23 24 25 26(1)试画出相应的散列表；H(Jan)=102=5，成功.H(Feb)=62=3，成功.H(Mar)=132=6，成功.H(Apr)=12=0，成功.H(May)=132=6，=7，成功，H(June)=102=5，=6，=7，=8，成功.H(July)=102=5，=6，=7，=8，=9，成功.H(Aug)=12=0，=1，成功.H(Sep)=192=9，=10，成功.H(Oct)=152=7，=8，=9，=10，=11，成功.H(Nov)=142=7，=8，=9，=10，=11，=12，成功

11、.H(Dec)=42=2，成功.(1)相应的散列表：0 1 2 3 4 5 6 7 8 9 10 11 12 13 34 56 58 63 94 34 56 58 63 94 02 1 3 4 4 穷则独善其身，达则兼善天下。孟子万两黄金容易得，知心一个也难求。曹雪芹Apr Aug Dec Feb Jan Mar May June July Sep Oct Nov (1)(2)(1)(1)(1)(1)(2)(4)(5)(2)(5)(6)(2)计算等概率下搜索成功的平均搜索长度；1/12*(1+2+1+1+1+1+2+4+5+2+5+6)=31/12 五、算法设计题 已知二叉树中的结点类型用 B

12、inTreeNode 表示，被定义为:struct BTreeNode char data;BinTreeNode*leftChild,*rightChild;其中 data为结点值域，leftChild 和 rightChild 分别为指向左、右子女结点的指针域，根据下面函数声明编写出求一棵二叉树中结点总数的算法，该总数值由函数返回。假定参数 BT 初始指向这棵二叉树的根结点。int BTreeCount(BinTreeNode*BT);解：int BTreeCount(BinTreeNode*BT)if(BT=NULL)return 0;/2 分 else return BTreeCoun

13、t(BT-leftChild)+BTreeCount(BT-rightChild)+1;/4 分 先天下之忧而忧，后天下之乐而乐。范仲淹吾日三省乎吾身。为人谋而不忠乎？与朋友交而不信乎？传不习乎？论语数据结构模拟卷 B 一、单项选择题 1以下与数据的存储结构无关的术语是（C ）。A循环队列 B.链表 C.哈希表 D.栈 2以下数据结构中，哪一个是线性结构（D ）。A广义表 B.二叉树 C.稀疏矩阵 D.串 3以下那一个术语与数据的存储结构无关？（B ）。A栈 B.哈希表 C.线索树 D.双向链表 4在下面的程序段中，对 x 的赋值语句的频度为（C）。FOR i:=1 TO n DO FOR j

14、:=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.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（A ）存储方式最节省时间。A顺序表 B双链表 C带头结点的双循环链表 D单循环链表

15、 8.某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（D ）存储方式最节省运算时间。A单链表 B仅有头指针的单循环链表 C双链表 D仅有尾指针的单循环链表 9.下面给出的四种排序法中(D )排序法是不稳定性排序法。A.插入 B.冒泡 C.二路归并 D.堆积 谋事在人，成事在天！增广贤文吾日三省乎吾身。为人谋而不忠乎？与朋友交而不信乎？传不习乎？论语E F D G A B /+*-C *10.下列排序算法中，其中（D ）是稳定的。A.堆排序，冒泡排序 B.快速排序，堆排序 C.直接选择排序，归并排序 D.归并排序，冒泡排序 11.已知一算术表达式的中缀形式为 A+

16、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/*+Dabcde*/+二、填空题，在横线处填写合适内容 1.数据结构的存储结构包括顺序、_链接_、索引和散列等四种。2.在程序运行过程中可以扩充的数组是_动态_分配的数组。这种数组在声明它时需要使用数组指针。3.在链表中进行插入和 删除 操作的效率比在顺序存储结构中进行相同操作的效率高。4.栈是一种限定在表的一端进行

17、插入和删除的线性表，又被称为_后出先进_表。5.如果一个对象部分地包含自己，或自己定义自己，则称这个对象是_递归_的对象。6.一棵树的广义表表示为 a(b(c,d(e,f),g(h),i(j,k(x,y)，结点 f 的层数为_3_。假定树根结点的层数为 0。7.一棵树按照左子女-右兄弟表示法转换成对应的二叉树，则该二叉树中树根结点肯定没有_右_子女。8.向一棵二叉搜索树中插入一个元素时，若元素的值小于根结点的值，则应把它插入到根结点的_左子树_上。9.设图 G=(V,E)，V=1,2,3,4,E=,，从顶点 1 出发，对图 G进行广度优先搜索的序列有_2_种。10.每次直接或通过基准元素间接比

18、较两个元素，若出现逆序排列就交换它们的位置，这种排序方法叫做_交换_排序。古之立大事者，不惟有超世之才，亦必有坚忍不拔之志。苏轼谋事在人，成事在天！增广贤文11.快速排序在平均情况下的空间复杂度为_ O(log2n)_。12.若对长度 n=10000 的线性表进行二级索引存储，每级索引表中的索引项是下一级 20 个表项的索引，则一级索引表的长度为_500_。三、判断题 1.在顺序表中进行顺序搜索时，若各元素的搜索概率不等，则各元素应按照搜索概率的降序排列存放，则可得到最小的平均搜索长度（对 ）2.在二叉搜索树中，若各结点的搜索概率不等，使得搜索概率越小的结点离树根越近，则得到的是最优二叉搜索树

19、（错 ）3.对于 AOE 网络，加速任一关键活动都能使整个工程提前完成（错 ）4.直接选择排序是一种稳定的排序方法（错 ）5.闭散列法通常比开散列法时间效率更高（错 ）6.数据的逻辑结构是指各数据元素之间的逻辑关系，是用户根据应用需要建立的（对 ）7.顺序表和一维数组一样，都可以按下标随机（或直接）访问（对 ）8.在一个顺序存储的循环队列中,队头指针指向队头元素的后一个位置（错 ）9.用非递归方法实现递归算法时一定要使用递归工作栈（错 ）10.在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行中序遍历和后序遍历，则具有相同的结果（对 ）四、运算题 1.设有一个二维数组 A1020

20、，按行存放于一个连续的存储空间中，A00的存储地址是 200，每个数组元素占 1 个存储字，则 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,

21、g,i,h,j,f 人人好公，则天下太平；人人营私，则天下大乱。刘鹗先天下之忧而忧，后天下之乐而乐。范仲淹 后序序列：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 右单旋转结点个数：0 先左后右双旋转结点个数：1 先右后左双旋转结点个数：0 不调整

22、结点个数：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，请写出在进行快速排序的过程中每次划分后数据表的变化。0 16 10 14 25 21 31 先天下之忧而忧，后天下之乐而乐

23、。范仲淹好学近乎知，力行近乎仁，知耻近乎勇。中庸(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 void List:Tnerse()if(first=NULL)return;ListNode*p=firstlink;,*pr=NULL;While(p!=NULL)Firstlink=pr;Pr=first;first=p;p=pli

24、nk;first-link=pr;解答 2 template void List:Tnerse()ListNode*p,*head=new ListNode ();While(first!=NULL)P=first;first=firstlink;plink=headlink;headlink=p;first=headlink;delete head;良辰美景奈何天，便赏心乐事谁家院。则为你如花美眷，似水流年。汤显祖万两黄金容易得，知心一个也难求。曹雪芹数据结构模拟卷 C 一、单项选择题 1数据结构是（D）。A一种数据类型 B数据的存储结构 C一组性质相同的数据元素的集合 D相互之间存在一种或

25、多种特定关系的数据元素的集合 2算法分析的目的是（B ）。A辨别数据结构的合理性 B评价算法的效率 C研究算法中输入与输出的关系 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 C1

26、7 D18 6二维数组 A89按行优先顺序存储，若数组元素 A23的存储地址为 1087，A47的存储地址为 1153，则数组元素 A67的存储地址为（A ）。A1207 B1209 C1211 D1213 7在按层次遍历二叉树的算法中，需要借助的辅助数据结构是（A）。良辰美景奈何天，便赏心乐事谁家院。则为你如花美眷，似水流年。汤显祖以铜为镜，可以正衣冠；以古为镜，可以知兴替；以人为镜，可以明得失。旧唐书魏征列传A队列 B栈 C线性表 D有序表 8在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系（B）。A不一定相同 B都相同 C都不相同 D互为逆序 9若采用孩子兄弟链表作为树的

27、存储结构，则树的后序遍历应采用二叉树的（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栈是_特殊_的线性表，其运算遵循_后进先出_的原

28、则。2_栈_是限定仅在表尾进行插入或删除操作的线性表。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若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的_比较_和记录的_移动_。我尽一杯，与君发三愿：一愿世清平

29、，二愿身强健，三愿临老头，数与君相见。白居易其身正，不令而行；其身不正，虽令不从。论语9.分别采用堆排序，快速排序，冒泡排序和归并排序，对初态为有序的表，则最省时间的是_冒泡排序_算法，最费时间的是_快速排序_算法。10不受待排序初始序列的影响，时间复杂度为 O(N2)的排序算法是_选择排序_，在排序算法的最后一趟开始之前，所有元素都可能不在其最终位置上的排序算法是_归并排序_。三、解答题 1某广义表的表头和表尾均为（a,(b,c)），画出该广义表的图形表示。2已知二叉树的先序序列和中序序列分别为 HDACBGFE 和 ADCBHFEG。（1）画出该二叉树；（2）画出与（1）求得的二叉树对应的

30、森林。人之为学，不日进则日退，独学无友，则孤陋而难成；久处一方，则习染而不自觉。顾炎武大丈夫处世，不能立功建业，几与草木同腐乎？罗贯中3已知带权图的邻接表如下所示，其中边表结点的结构为：依此邻接表从顶点 C 出发进行深度优先遍历。（1）画出由此得到的深度优先生成树；（2）写出遍历过程中得到的从顶点 C 到其它各顶点的带权路径及其长度。顶点 C 到顶点 A 的带权路径为（C，D，B，A），其长度为 8+20+11=39 顶点 C 到顶点 B 的带权路径为（C，D，B），其长度为 8+20=28 顶点 C 到顶点 D 的带权路径为（C，D），其长度为 8 顶点 C 到顶点 E 的带权路径为（C，D

31、，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 的头结点，p 指向根节点 if(p-RTag=1)return ERROR;/右标记是线索，即右子树为空则返回错误 p=p-rchild;老当益壮，宁移白首之心；穷且益坚

32、，不坠青云之志。唐王勃穷则独善其身，达则兼善天下。孟子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-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;