数据结构参考答案

1、数据结构模拟卷A一、选择题1.在一个长度为 n 的顺序表的任一位置插入一个新元素的渐进时间复杂度为（A ）。A. O(n)B. O(n/2)C. O(1)D. O(n 2)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. 20B. 18C. 25D. 228.在有向图中每个顶点的度等于该顶点的（C）。A. 入度B.出度C. 入度与出度之和D. 入度与出度之差9.在基于排序码比较的排序算法中

3、，（C）算法的最坏情况下的时间复杂度不高于O(nlog 2n) 。A. 起泡排序B.希尔排序C. 归并排序D. 快速排序10. 当 的值较小时，散列存储通常比其他存储方式具有（B）的查找速度。.A. 较慢B.较快C. 相同D.不同二、填空题1.二维数组是一种非线性结构，其中的每一个数组元素最多有_2_ 个直接前驱 （或直接后继）。2.将一个n 阶三对角矩阵 A 的三条对角线上的元素按行压缩存放于一个一维数组B 中，A00存放于 B0 中。对于任意给定数组元素BK ，它应是 A 中第 _ (K+1)/3_ 行的元素。3.链表对于数据元素的插入和删除不需移动结点，只需改变相关结点的_指针 _域的值

4、。4.在一个链式栈中，若栈顶指针等于NULL则为 _空栈 _。5. 主程序第一次调用递归函数被称为外部调用，递归函数自己调用自己被称为内部调用，它们都需要利用栈保存调用后的 _返回 _地址。6. 在一棵树中， _叶子 _结点没有后继结点。7.一棵树的广义表表示为a (b (c, d (e, f), g (h) ), i (j, k (x, y) ) )，结点f的层数为 _3_。假定根结点的层数为0。8. 在一棵 AVL树（高度平衡的二叉搜索树） 中，每个结点的左子树高度与右子树高度之差的绝对值不超过 _1_。9. n (n 0) 个顶点的无向图最多有 _ n(n- 1)/2_条边，最少有 _0

5、_条边。10.在索引存储中，若一个索引项对应数据对象表中的一个表项（记录），则称此索引为 _稠密 _索引，若对应数据对象表中的若干个表项，则称此索引为_稀疏 _索引。三、判断题1.数组是一种复杂的数据结构，数组元素之间的关系既不是线性的也不是树形的( 对 )2.链式存储在插入和删除时需要保持物理存储空间的顺序分配，不需要保持数据元素之间的逻辑顺序 ( 错 )3.在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针( 对 )4.通常递归的算法简单、易懂、容易编写，而且执行的效率也高( 错 )5. 一个广义表的表尾总是一个广义表( 对)6. 当从一个小根堆（最小堆）中删除一个元素

6、时，需要把堆尾元素填补到堆顶位置，然后再按条件把它逐层向下调整，直到调整到合适位置为止( 对 )7. 对于一棵具有 n 个结点，其高度为 h 的二叉树，进行任一种次序遍历的时间复杂度为O(h)( 错).8.存储图的邻接矩阵中，邻接矩阵的大小不但与图的顶点个数有关，而且与图的边数也有关 ( 错 )9. 直接选择排序是一种稳定的排序方法( 错 )10. 闭散列法通常比开散列法时间效率更高( 错 )四、运算题1.设有一个 10 10 的对称矩阵A，将其下三角部分按行存放在一个一维数组B 中，A00存放于 B0 中，那么A85存放于 B 中什么位置。解：根据题意，矩阵 A 中当元素下标 I 与 J 满

7、足 I J 时，任意元素 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-link != NULL ) Ha = Ha-link;if ( Ha-data = x ) n+;return n;解：

8、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, A4.已知一个有序表( 15, 26, 34, 39, 45, 56, 58, 63, 74, 76, 83, 94 )顺序存储于一维数组a12 中，根据折半搜索过程填写成功搜索下表中所给元素34, 56

9、, 58, 63, 94时的比较次数。3456586394元素值比较次数解：判断结果元素值3456586394比较次数0213445.设散列表为HT17,待插入关键码序列为 Jan, Feb, Mar, Apr, May, June, July,Aug, Sep, Oct, Nov, Dec ，散列函数为H (key) =i2 ，其中， i 是关键码第一个字母在字母表中的序号。现采用线性探查法解决冲突。字母 ABCDEFGHIJKLM序号12345678910111213字母 NOPQRSTUVWXYZ序号14151617181920212223242526(1) 试画出相应的散列表；H(Ja

10、n) =10 2= 5 ，成功 .H(Feb) =6 2= 3 ，成功 .H(Mar) =132= 6，成功 .H(Apr) =1 2= 0 ，成功 .H(May) =13 2= 6， = 7，成功，H(June) =102 = 5 ， = 6， = 7， =8，成功 .H(July) =10 2= 5 ， = 6， = 7 ，= 8 ， = 9，成功 .H(Aug) =1 2 = 0 ，= 1 ，成功 .H(Sep) =19 2 = 9， = 10，成功 .H(Oct) =15 2= 7， = 8，= 9 ， = 10，= 11，成功 .H(Nov) =14 2= 7 ，= 8， = 9，

11、= 10， = 11， = 12，成功 .H(Dec) =4 2 = 2 ，成功 .(1) 相应的散列表：012345678910111213AprAugDecFebJanMarMayJuneJulySepOctNov(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五、算法设计题已知二叉树中的结点类型用BinTreeNode 表示，被定义为:struct BTreeNode char data;Bi

12、nTreeNode *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

13、 ( 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 DOFOR j:=1 TO n DOx:=x+1;A O(2n)B O(n)CO(n2)D O(log 2n)5. 下面关于线性表的叙述中，错误的是哪一个（B）。A线性表采用顺序存储，必须占用一

14、片连续的存储单元。B线性表采用顺序存储，便于进行插入和删除操作。C线性表采用链接存储，不必占用一片连续的存储单元。D线性表采用链接存储，便于插入和删除操作。6线性表是具有n 个（ C）的有限序列（n0）。A表元素B字符C数据元素D数据项E信息项7. 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（A）存储方式最节省时间。A顺序表B双链表C带头结点的双循环链表D单循环链表8. 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ D）存储方式最节省运算时间。A单链表B仅有头指针的单循环链表C双链表D仅有尾指针的单循环链表9. 下面给出

15、的四种排序法中 ( D ) 排序法是不稳定性排序法。A. 插入B.冒泡C.二路归并D.堆积.10. 下列排序算法中，其中（ D ）是稳定的。A. 堆排序，冒泡排序B.快速排序，堆排序C.直接选择排序，归并排序D.归并排序，冒泡排序11. 已知一算术表达式的中缀形式为A+B*C-D/E ，后缀形式为ABC*+DE/-，其前缀形式为( D )。A -A+B*C/DEB. -A+B*CD/EC -+*ABC/DED. -+A*BC/DE12. 算术表达式a+b* （ c+d/e ）转为后缀表达式后为（B）。A ab+cde/*B abcde/+*+C abcde/*+D abcde*/+/+*C*-

16、ABDEFG二、填空题，在横线处填写合适内容1. 数据结构的存储结构包括顺序、_链接 _、索引和散列等四种。2. 在程序运行过程中可以扩充的数组是 _动态 _分配的数组。 这种数组在声明它时需要使用数组指针。3. 在链表中进行插入和删除 操作的效率比在顺序存储结构中进行相同操作的效率高。4.栈是一种限定在表的一端进行插入和删除的线性表，又被称为_后出先进 _表。5.如果一个对象部分地包含自己，或自己定义自己，则称这个对象是_递归 _的对象。6.一 棵 树 的 广 义 表 表 示 为 a(b(c,d(e,f),g(h),i(j,k(x,y)， 结 点 f 的 层 数 为_3_。假定树根结点的层数

17、为0。7. 一棵树按照左子女 - 右兄弟表示法转换成对应的二叉树， 则该二叉树中树根结点肯定没有_右 _子女。8. 向一棵二叉搜索树中插入一个元素时，若元素的值小于根结点的值，则应把它插入到根结点的 _左子树 _上。9.设图 G=(V,E) ， V=1,2,3,4, E=,，从顶点1 出发，对图G进行广度优先搜索的序列有_2_种。10.每次直接或通过基准元素间接比较两个元素，若出现逆序排列就交换它们的位置，这种排序方法叫做 _交换 _排序。.11.快速排序在平均情况下的空间复杂度为_ O(log 2n) _ 。12.若对长度 n=10000 的线性表进行二级索引存储，每级索引表中的索引项是下一

18、级20 个表项的索引，则一级索引表的长度为_500_。三、判断题1. 在顺序表中进行顺序搜索时， 若各元素的搜索概率不等， 则各元素应按照搜索概率的降序排列存放，则可得到最小的平均搜索长度（对）2. 在二叉搜索树中，若各结点的搜索概率不等，使得搜索概率越小的结点离树根越近，则得到的是最优二叉搜索树（错）3.对于 AOE网络，加速任一关键活动都能使整个工程提前完成（错）4.直接选择排序是一种稳定的排序方法（错）5.闭散列法通常比开散列法时间效率更高（错 ）6.数据的逻辑结构是指各数据元素之间的逻辑关系，是用户根据应用需要建立的（对）7.顺序表和一维数组一样，都可以按下标随机（或直接）访问（对）8

19、.在一个顺序存储的循环队列中, 队头指针指向队头元素的后一个位置（错）9.用非递归方法实现递归算法时一定要使用递归工作栈（错）10. 在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行中序遍历和后序遍历，则具有相同的结果（对）四、运算题1.设有一个二维数组A1020，按行存放于一个连续的存储空间中，A00的存储地址是 200，每个数组元素占1 个存储字，则A62的存储字地址是多少。A62的存储字地址：322答案说明：按行存储时，计算Aij地址的公式为LOC(i,j)=LOC(0,0)+(i*n+j)*d其中首地址LOC(0,0)=200, 每个数组元素的存储占用数d=1, 二维数

20、组的列数n=20，根据题意，元素A62 的存储地址为LOC(6,2)=200+(6*20+2)*1=3222. 已知一棵二叉树的中序和后序序列如下，求该二叉树的高度（假定空树的高度为-1 ）和度为 2、度为 1 及度为 0 的结点个数。中序序列： c,b,d,e,a,g,i,h,j,f.后序序列： c,e,d,b,i,j,h,g,f,a求解一下问题：高度：4度为 2 的结点数： 3度为 1 的结点数：3度为 0 的结点数： 43.假定一组记录为(36,75,83,54,12,67,60,40)，将按次序把每个结点插入到初始为空的一棵 AVL 树中，请回答在插入时需进行“左单旋转” 、“右单旋转

21、” 、“先左后右双旋转” 、“先右后左双旋转” ，“不调整”的结点数各是多少？左单旋转结点个数：1右单旋转结点个数：0先左后右双旋转结点个数：1先右后左双旋转结点个数：0不调整结点个数：64. 已知一个带权图的顶点集 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 到其余各顶点的最短路径，在下面填写对应的路径长度。顶点：0123456路径长度：01610142521

22、315.已知一个数据表为36,25,25*,62,40,53，请写出在进行快速排序的过程中每次划分后数据表的变化。.(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的单链表。试设计一个算法，通过遍历一趟链表，将链表中所有结点按逆序链接。解答 1template void List : : Tnerse() if (first= NULL )return ;ListNode * p=firstlink ; , *pr =NULL

23、;While (p !=NULL ) First link =pr ;Pr =first ;first =p ;p =p link;first -link =pr ;解答 2template void List : : Tnerse() ListNode * p , *head = new ListNode ( ) ;While (first ! = NULL ) P=first ;first = first link;p link =head link ; head link =p;first = head link ; delete head ;.数据结构模拟卷C一、单项选择题1数据结构是

24、（D）。A一种数据类型B数据的存储结构C一组性质相同的数据元素的集合D相互之间存在一种或多种特定关系的数据元素的集合2算法分析的目的是（B）。A辨别数据结构的合理性B评价算法的效率C研究算法中输入与输出的关系D鉴别算法的可读性3在线性表的下列运算中，不改变数据元素之间结构关系的运算是（D）。A插入B删除C排序D定位4若进栈序列为1， 2， 3，4，5， 6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为（B）。A 3， 2， 6， 1， 4，5B 3，4， 2， 1， 6， 5C 1， 2， 5， 3， 4，6D 5，6， 4， 2， 3， 15设串sl= Data Structures w

25、ith Java ,s2= it ，则子串定位函数index(s1,s2)的值为（ D）。A 15B 16C 17D 186二维数组 A89 按行优先顺序存储，若数组元素A23的存储地址为1087 ，A47的存储地址为1153，则数组元素A67 的存储地址为（ A）。A 1207B 1209C 1211D 12137在按层次遍历二叉树的算法中，需要借助的辅助数据结构是（A ）。.A队列B栈C线性表D有序表8在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系（B）。A不一定相同B都相同C都不相同D互为逆序9若采用孩子兄弟链表作为树的存储结构，则树的后序遍历应采用二叉树的（C）。A层

26、次遍历算法B前序遍历算法C中序遍历算法D后序遍历算法10若用邻接矩阵表示一个有向图，则其中每一列包含的1的个数为（ A）。A图中每个顶点的入度B图中每个顶点的出度C图中弧的条数D图中连通分量的数目11图的邻接矩阵表示法适用于表示（C）。A无向图B有向图C稠密图D稀疏图12在对 n 个关键字进行直接选择排序的过程中，每一趟都要从无序区选出最小关键字元素，则在进行第 i 趟排序之前，无序区中关键字元素的个数为（D）。A iB i+1C n-iD n-i+1二、填空题1栈是 _特殊 _的线性表，其运算遵循_后进先出 _的原则。2 _栈 _是限定仅在表尾进行插入或删除操作的线性表。3. 一个栈的输入序

27、列是： 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若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的_比较 _和记录的 _移动 _。.9. 分别采用堆排序，快速排序， 冒泡排序和归并排序，对初态为有序的表，则最省时间的是_冒泡排序 _算法，最费时间的是_快速排序 _算法。10不受待排序初始序列的影响，时间复杂度为O(N2) 的排序算法是_选择排序 _，在排序算法的最后一趟开始之前，所有元素都可能不在其最终位置上的排序算法是_归并排序 _。三、解答题1某广义表的表头和表尾均为（a,(b,c)），画出该广义表的图形表示。2已知二叉树的先序序列和中序序列分别为HDACBGFE和 ADCBHFEG。（ 1）画出该二叉树；（ 2）画出与（