数据结构试题及答案

1一、判断1.带表头节点的双向循环链表为空时，表头的前驱和后继指针指向HEAD。2.带表头结点的双向链表为空时，表头的前趋和后继指针分别指向NULL。3.带表头结点的双向循环链表为空时，表头的前驱和后继指针分别指向NULL4.环形链表是线性结构，首尾相连，使用连续地址储存。5.环形队列是线性结构，但它不是环形，利用特殊的循环算法解决“假溢出”。6.环形队列是线性结构，象循环链表一样头尾相连接，它能解决“假溢出”。7.环形队列是线性结构，能利用特殊的循环算法解决“假溢出”。8.广义表E（a，E）的表长是2，表深度是无穷大。9.广义表E（a，E）的表深度是2，表长是2。10.广义表G（a，G）的表深度是2，表长是2。11.广义表G（a，G）的深度是2，表长是2。12.满BT是特殊的BT树，它的定义是递归的。13.BT是特殊的树，它的定义是递归的。14.平衡树是特殊的BT树，它的定义是递归的。15..若已知BT的先根序和中根序、后根序和中根序，可唯一确定一个BT。16.若已知BT的先根序遍历和后根序遍历，可唯一确定一个BT。17.平衡BT是特殊的BT，它的定义是递归的。18.BST是特殊的BT，它的中序遍历是有序的。19.何时使用PRIM法，何时使用KRUSKAL法取决于图是稀疏还是稠密20.PRIM和KRUSKAL均可以对图求MST，但是PRIM法方便。21.希尔排序是插入排序的变型，插入排序是稳定的，但希尔排序是不稳定的。22.希尔排序是插入排序的变型。插入排序是稳定的，所以希尔排序是稳定的。223.快速排序的稳定性取决于枢轴的选择。24.快速排序的枢轴有多种选择方法，取首尾节点是较简单的做法。25.冒泡排序不但稳定，而且速度很快。二、名词解释与问答26.线性结构:唯一的首节点，唯一的尾节点，除首尾外其它节点既有前驱也有后继，首无前驱，尾无后继。27.线性结构中端操作受限的含义是什么？操作仅在指定的位置。栈在栈顶，队列在队头和队尾。28.非线性结构有树、图、集合等。可实现一对多、多对多、多对一的逻辑关系。是复杂的数据结构29.链式存储:结点的结构为数据+指针，利用指针可寻址找下一个结点30.连续地址储存：所有的节点储存在一块内存逻辑编号连续的内存中。起始的逻辑地址称首地址。访问通过首地址。31.原子项：数据元素中不可分解的项。32.数据元素:是数据结构的基本单位，有一个或多个数据项（原子属性）构成。33.简述双向循环链表的逻辑特点。双向循环链表与线性表有何异同？双向循环链表中的节点含有两个指针，一个用于指向前驱节点，一个用于指向后继节点，可由表头开始实现双向访问。线性链表仅可以沿一个方向访问。34.简述双向循环链表的特点双向循环链表中的结点含有两个指针，一个用于指向前驱结点，一个用于指向后继结点，可由表头开始实现双向访问。35.表头节点的作用是什么？存储表的相关信息如表长、是否为空表。头结点的数据域存储指向第一个结点的指针。36.简述环型队列的特点。将顺序队列臆想为一个环状空间，指针和队列元素之间的关系不变。front==rear无法判断队列是否为“空”还是“满”37.栈的top和bottom标志：栈的顶和底标志，top指向顶，bottom指向底38.稀疏矩阵：矩阵中存在大量的零元素，当稀疏因子达到一定值时，就认为该矩阵为稀疏矩阵。39.串由零个或多个字符组成的有限序列40.串的子串串中任意个连续的字符组成的子序列称为串的子串41.串的长度串中字符的数目称为串的长度42.主串包含子串的串称为主串43.树的结点:包含一个数据元素及若干指向其子树的分支344.树结点的度（树的度）树结点拥有的子树数，称为树结点的度45.树的深度树中结点的最大层次称为树的深度46.什么是二叉树？二叉树是树形结构，它的特点是每个结点至多只有两棵子树，并且二叉树的子树有左右之分，其次序不能任意颠倒。47.空二叉树:是一种特殊的BT。它没有任何结点。48.严格二叉树：深度为K，结点个数为2K-1个的BT49.BT有几种形态？逐一画出图形并作解释。五种。一个根的BT；空BT；左倾斜BT；右倾斜BT；根+左子树+右子树。50.图的权:图的边或弧相关的数叫做权51.网带权的图称为网52.连通图图中任意两个顶点都是连通的，则称图是连通的53.图的简单路径序列中顶点不重复出现的路径称为简单路径54.查找根据给定的某个值，在查找表中确定一个其关键字等于给定值的记录或数据元素叫查找。55.查找表:由同一类型的数据元素构成的集合56.关键值（关键字）:是数据元素中某个数据项的值，用它可以识别一个记录主关键字：可以唯一识别一个记录的关键字就是主关键字。57.HASH函数:在记录的存储位置和它的关键字之间建立一个确定的对应关系函数f，使得每个关键字和结构中一个唯一的存储位置相对应。这个函数f称为哈希（HASH）函数58.HASH技术中的冲突是指什么现象？如何解决？对不同的关键字可能得到同一个哈希地址，这种现象称为冲突。通常采用的解决冲突的方法有：开放定址法、再哈希法、链地址法、建立一个公共溢出区59.简述堆的特点，如何存储堆结构数据。n个元素的序列｛k1,k2,…kn｝当且仅当满足以下关系时，称为堆。2...,2,1122122nikkkkkkkkiiiiiiii或堆只需要一个记录大小的辅助空间。每个待排序的记录仅占有一个存储空间。60.排序中附加储存空间的作用是什么？在基于比较和交换的排序技术中，若交换数据，必须有附加的储存单元暂存待交换的数据，否则将导致部分数据丢失。附加空间是指内存。61逆波兰式xy+st-*表示的含义是什么？画出表达式树，计算结果是多少？（x+y）*(s-t)462.多项式y=ax3+bx2+cx+d有多种计算方法，第一种直接计算y=a*x*x*x+b*x*x+c*x+d；第二种计算方法是：y=a；y=y*x+b；y=y*x+c；y=y*x+d；哪种快？为什么？第二种好。乘法和加法的次数不同。乘法和加法所需要的时间不同。三、画图、读图1.有BT如下图，求先序、中序、后序遍历。先序WM$#ACD；先根序HCMUXYT；先根序V、R、T、D、X、P、F；中序$MWCAD#；中根序CUMXHYT；中根序T、D、R、X、P、V、F；后序$MCDA#W后根序UXMCTYH后根序D、T、P、X、R、F、V先根序K、L、J、M、G、N；先根序e、u、t、c、d、q、h；先根序W、M、K、F、Z、V、H中根序L、K、G、M、N、J；中根序u、e、d、c、q、t、h；中根序K、M、Z、F、V、W、H；后根序L、G、N、M、J、K。后根序u、d、q、c、h、t、e。后根序K、Z、V、F、M、H、W2.有G、F、A、D、L、B数据，按题目所给定的次序逐步构建BST（按ASCII码值），构建完成后，再删除L节点。53.依次输入键值47、38、69、27、53、72的数据，逐步构建BST。BST的基本功能是什么？BST是二叉排序树，中序是升序。4.有键值为F、K、A、D、X、V、I的数据，按题目所给定的次序逐步构建BST（按ASCII码值）构建完成后，写出中根序遍历，再删除V节点。5.若有一个栈，数据输入的次序为U，V，W，写出出栈序列。6.若有一个栈，数据输入的次序为W，X，Y，Z，写出输出次序。7.若有一个栈，数据输入的次序为X，Y，Z，给出出栈序列68.有一个栈（栈的规模=10），数据输入的次序为A、B、C，写出出栈序列。9.有下图，用Kurskal法逐步求该图的MST，需图示说明。依次挑选3、3、5、11边10.若有带权无向图（见下图），指点起始顶点为G，用PRIM法求出该图的MST。11.如下图，指定顶点C为起始顶点，用PRIM法求该树的MST。7CARBF334412.用二进制系统传输电文seven-eleven，要求使用最少的比特量，画出编码树，用你设计的方式传输该电文需用多少比特？v的二进制编码是什么?编码树如下，共需28比特，v的编码可能不同，取决于huffmantree的形状，因为此题有相同的权。charsevln-times15212113.用二进制系统传输电文thinning，要求使用最少的比特量，试画编码树，用你设计的方式传输该电文最少需用多少比特？g的编码是什么?编码树:Charnitghtimes32111最少的比特量为:thinning=010011100000100011=18bitg的编码是1114.用二进制系统传输电文cookbook，要求使用最少的比特量，试画编码树，用你设计的方式传输该电文最少需用多少比特？k的编码是什么?需用14比特（结果唯一），k的编码是11（结果可能多样，取决于哈夫曼数的形状）cobk1412参考编码：10000111010011=14bitk的编码是11815.用二进制系统传输电文cctvcommov，要求使用最少的比特量，试画编码树，用你设计的方式传输该电文最少需用多少比特？t的编码是什么?Charctvmotimes3122210101101111001000001111=23bitt的编码是110（视哈夫曼树而定）16.用二进制系统传输电文antenna，要求使用最少的比特量，试画编码树，用你设计的方式传输该电文最少需用多少比特？其中t的编码是什么?最少的比特量为13，试画编码树。charatnetimes2131antenna＝0010100111100=13bitt的编码是010（不唯一）917.用二进制系统传输电文yahoohook，要求使用最少的比特量，画出编码树，用你设计的方式传输该电文需用多少比特？a的编码是什么？最少需用19比特,Charyahkotimes1121418若待排序的数据存放在数组inta[]中，结点的键值为整型数n，试写出插入排序算法//若待排序的数据存放在数组中，节点的键值为整型数，试写出插入排序算法的伪码。附加图示说明。insertsort(inta[],intn)的伪码。voidinsertsort(inta[],intn){inti,j;inttemp;for(i=1;in;i++)(1分){temp=a[i];(1分)for(j=i-1;j=0&&tempa[j];j--)(1分)a[j+1]=a[j];(1分)a[j+1]=temp;(1分)}}19.若待排序的数据存放在数组bubble[max]中，用类C语言写出冒泡排序算法的伪码。voidbubble-sort(bubble,n)intbubble[max];intn;{inti,j;inttemp;n--;while(n0){j=0;for(i=0;in;i++)if(bubble[i]bubble[i+1]){temp=bubble[i];bubble[i]=bubble[i+1];bubble[i+1]=temp;j=i;}n=j;}}20.若BT采用“数据+指向左右孩子的指针”方式存储，已知指向BT根结点的指针Btree*BT，定义结点的结构，用伪码描述求该BT有单孩子的结点个数intonechild(Btree*BT)的算法。//若BT采用“数据+指向左右孩子的指针”方式存储，已知指向BT根节点的指针，定义节点的结构，用伪码描述求该BT有单孩子的节点个数的算法。并加图示说明。#defineNULL0typedefstructNODE{element-typedata;structNODE*left,*right;10}Btree;intonechild(Btree*BT){intnum1,num2;if(BT==NULL)return(0);elseif((BT-left==NULL&&BT-right!=NULL)||(BT-left!=NULL&&BT-right==NULL))return(1);else{num1=onechild(BT-left);num2=onechild(BT-right);return(num1