河北工程大学数据结构复习题(精品).docx

《河北工程大学数据结构复习题(精品).docx》由会员分享，可在线阅读，更多相关《河北工程大学数据结构复习题(精品).docx（8页珍藏版）》请在课桌文档上搜索。

1、单项选择题1 .数据的(B)包括集合、线性、树和图4种基本类型A,存储结构B.逻辑结构C.基本运算D.算法描述2.对一个长度为n的顺序表，在第i个元素(IWiWn+I)之前插入一个新元素时需向右挪移(B)个元素。A.h-iB.n-i+1C.n-i-1D.i3下面程序的时间复杂度为(C)OFor(i=0;im;i+)For(j=0;jA.ABGDCEFB.ABDGCFEC.BDGCD.ABDGCEFEFA18如果以链表作为栈的存储结构，则出栈操作时（C）出麻新荆林搐樗布满对稳存许集何测剂19线性表采用链式存储时，其地址（DA.必须连续B部份地址必须连C.必须连续D连续与否均20数据的.）包括集合

2、、线树和图4种基本类A.存储结构B逻辑结构C.基本运算D.算法描述21-棵彻底二叉树上有15个结点，其深度是不超过（C）的最大整数。A.B.C,D.A-C项都不23422若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除最后素，则采用（D）存储方式最节省运算时间。A.单链表B.双链表C.带头结点的双循环链表D.容量足够大的顺序23.二叉树中第5层上的结点个数最多为一A.B.185C.1D.36224 .深度为5的二叉树至多有（D）结点。B.32D.63A.64C.3125 .将一棵有100个结点的彻底二叉树从上到下，从左到右挨次对结点进行编号，根结的编号为1,则编号为49的结点的左

3、孩子的编号为_A.A.98B.99C.50D.4826 .已知广义表的表头为A,表尾为（Be）,则此广义表为一BA.（A,（B,C）B.（A.B.0C.（八）,B,C）D.（A,B,C）填空题1.对于给定的n个元素，可以构造出的逻辑结构有（集合）、（线性）、（树）、（图）4种。2数据元素在计算机中的（）方式称为存储结构。3线性结构中的元素之间存在（一对一）关系，树形结构中元素之间存在（一对多）关系，图形结构中的元素之间存在（多对多）关系。4设单链表的结点结构为（data,*next）,已知指针P指向单链表中X结点，指针q指向y的新结点，若将结点y插入到结点X之后，则需耍执行以下两条语句（q-n

4、ext=p-next）,（p-next=q）。5数据的（逻辑）结构与数据元素本身的内容和形式无关。6一个算法的好坏取决于该算法的（时间复杂度）和（空间复杂度）。7数据结构中评价算法的两个重要指标是（时间复杂度）、空间复杂度。8一个循环队列存储于下标由0开始且长度为m的一维数组中，假定队头和队尾指针分别为front和rear,贝U判断队空的条件为（rar+1）%n=front）。贝U判断队满的条件为（front=rear）。9队列的插入操作是在队列的（队尾）进行，删除操作是在队列的（队头）进行。10堆栈的逻辑特点是（先进后出），队列的逻辑特点是（先进先出）。11堆栈的逻辑特点是（先进后出），队列

5、的逻辑特点是（先进先出）。二者的共同点是只允许在它们的(端点)处插入和删除数据元素。12堆栈操作设输入元素的顺序为1,2,34,5,要在栈的输出端得到43521,则应进行栈的基本运算表示应为：Push(SJ),Push(S,2),Push(S,3),Push(S,4),Pop(三)1(Pop(三),(Push(S,5),Pop(三)5Pop(三)5Pop(三)013设有一个链队，结点结构为datalnext,front为队头指针，rear为队尾指针，当执行入队操作时需执行下列语句：malloc(p)；p-data=x;p-next=NULL；()();13、一棵二叉树有67个结点，这些结点的度

6、要末是0,要末是2o这棵二叉树中度数为2的结点有个。14、一个哈夫曼(HlJffman)树有19个结点，则其叶结点的个数是。15、一棵深度为6的满二叉树有31个分支结点和32个叶子。16、设二叉树结点的先序序列为ABDECFGH,中序序列为DEBAFCHG,则二叉树的后序序列是。17 .克鲁斯卡尔算法的时间复杂度为()，适合求()的最小生成树。18 .空串是()，其长度等于()。19 .空格串是0,其长度等于()020 .两个字符串相等的充分必要条件是()。21写出模式串p=abaabcac的next函数值序列为022、设有一稀疏图G,则G采用存储结构较省空间。23 、已知广义表A=(a,b,

7、c),(d,e,f),则运算head(head(tail（八）)=.24 .一棵深度为6的满二叉树有个分支结点和个叶子。25 .在对一组记录(54,38,96,23,15,72,60,45,83)进行直接插入排序时，当把第7个记录60插入到有序表时，为寻觅插入位置至少需比较次。应用题1 .什么是线性结构？线性结构的特点是什么？列举？2 .什么是树形结构？树形结构的特点是什么？3 .什么是图结构？4 .已知二叉树的前序Abcdefghij和中序CDBFEAIHGJ,试构造出相应的二叉树。5 .已知一棵二叉树的后序遍历序列为ElCBGAHDF,中序遍历序列为ECIFBAGDHjW画出这棵二叉树，7

8、,对于一个有100OO个结点的二叉树，树叶最多有多少个？至少有多少个？8写出某个有向图的顶点V和弧E的邻接矩阵。9已知某二叉树，写出前序遍历、中序遍历和后序遍历10根据普里姆算法思想，画出构造该无向带权图最小生成树的过程。（5分）11的有向带权图，根据狄克斯特拉算法思想，画出生成从顶点A到其余各项顶点最短路径的过程。12已知序列34,17,6,29,33,11,80,37请用冒泡排序的方法从大到小进行排序,并给出详细过程。13已知序列34,17,6,29,33,11,80,37请用直接选择排序的方法从大到小进行排序，并给出详细过程。14 .已知一棵二叉树的中序序列和后序序列分别为：DBGEAC

9、HF和DGEBHFCA厕该二叉树的前序序列是什么？试画出这棵二叉树。15 .给定权值集合15,03,14,02,06,09,16,17,构造相应的哈夫曼树，并计算它的带权路径长度。16 .设一数组A56,A的地址为IloO,且每一个元素占2个存储单元，则这个二维数组的存储量为多少？A45的地址为多少？如按行优先顺序存储A3的地址为多少？17 .用序列（46,88,45,39,70,58,101,10,66,34）建立一个排序二叉树，画出该树，并求在等概率情况下查找成功的平均查找长度18 .按下列要求，写出相应结果设关键字的输入次序为45,24,53,45,12,249,0。画出生成的二叉排序树（5分）。19试画出具有3个结点的二叉树所有不同形态（5分）。写算法1 .请写出顺序存储的线性表中，在第i个位置插入和删除数据元素X的实现算法。（请在关键部份给出注释。）2 .请写出链式存储的线性表中，在第i个位置插入和删除数据元素X的实现算法。（请在关键部份给出注释。）3 .请写出链式堆栈操作中，入栈和出栈的实现算法。（请在关键部份给出注释。）