《河北工程大学数据结构复习题》由会员分享，可在线阅读，更多相关《河北工程大学数据结构复习题（10页珍藏版）》请在金锄头文库上搜索。
1、河北工程大学数据结构复习题作者:日期:单项选择题1 .数据的(B)包括集合、线性、树和图 4种基本类型A.存储结构B.逻辑结构C.基本运算D.算法描述2 .对一个长度为n的顺序表，在第i个元素(1in+1)之前插入一个新元素时需向右 移动(B)个元素。A. n-iB, n-i+1C. n-i-1D. i3下面程序的时间复杂度为(C )。For(i=0;im;i+)For(j=0;jnext=p-next ）,（ p-next=q ）。5数据的（逻辑）结构与数据元素本身的内容和形式无关。6一个算法的好坏取决于该算法的（时间复杂度）和（空间复杂度 ）。7数据结构中评价算法的两个重要指标是（时间复杂
2、度）、空间复杂度。8一个循环队列存储于下标由 0开始且长度为m的一维数组中，假定队头和队尾指针分 别为front和rear,则判断队空的条件为（rear+1 ） %n=front ）。则判断队满的条件 为（front=rear ）。9队列的插入操作是在队列的（ 队尾）进行，删除操作是在队列的（ 队头）进行。 10堆栈的逻辑特点是（ 先进后出），队列的逻辑特点是（ 先进先出）。11堆栈的逻辑特点是（先进后出 ），队列的逻辑特点是（先进先出）。二者的共 同点是只允许在它们的（端点）处插入和删除数据元素。12堆栈操作设输入元素的顺序为1,2,3,4,5,要在栈的输出端得到 43521,则应进行栈的基
3、本运算表示应为：Push(S,1) , Push(S,2), Push(S,3), Push(S,4), Pop(S), (Pop(S),(Push(S,5) ), Pop(S), Pop(S), Pop(S)。13设有一个链队，结点结构为 data|next, front为队头指针，rear为队尾指针，当执行入队操作时需执行下列语句：malloc(p) ; p-data=x; p-next=NULL ；()；( )；13、一棵二叉树有67个结点，这些结点的度要么是 0,要么是2。这棵二叉树中度数为 2 的结点有 个。14、一个哈夫曼(Huffman)树有19个结点，则其叶结点的个数是。15、
4、一棵深度为6的满二叉树有31个分支25点和32个叶子。16、设二叉树结点的先序序列为ABDECFGH ,中序序列为 DEBAFCHG,则二叉树的后序序列是。17 .克鲁斯卡尔算法的时间复杂度为()，适合求()的最小生成树。18 .空串是()，其长度等于()。19 .空格串是()，其长度等于()。20 .两个字符串相等的充分必要条件是()。21写出模式串p= abaabcaC勺next函数值序列为()22、设有一稀疏图G,则G采用存储结构较省空间。23、已知广义表 A=(a,b,c),(d,e,f), M运算 head(head (tail (A) )=.24 . 一棵深度为6的满二叉树有个分支
5、结点和个叶子。25 .在对一组记录(54, 38, 96, 23, 15, 72, 60, 45, 83)进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置至少需比较次。应用题1 .什么是线性结构？线性结构的特点是什么？列举？2 .什么是树形结构？树形结构的特点是什么？3 .什么是图结构？4 .已知二叉树的前序 ABCDEFGHIJ和中序CDBFEAIHGJ ,试构造出相应的二叉树。5 .已知一棵二叉树的后序遍历序列为EICBGAHDF ,中序遍历序列为 ECIFBAGDH ,请画出这棵二叉树，7.对于一个有10000个结点的二叉树，树叶最多有多少个？最少有多少个？8写出某个
6、有向图的顶点 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、已知一棵二叉树的中序序列和后序序列分别为：DBGEACHF和DGEBHFCA ,则该二叉树的前序序列是
7、什么？试画出这棵二叉树。15、给定权值集合15,03,14,02,06,09,16,17,构造相应的哈夫曼树，并计算它的带权路 径长度。16 .设一数组 A56 , A00的地址为1100,且每个元素占2个存储单元，则这个二 维数组的存储量为多少？ A45的地址为多少？如按行优先顺序存储 A23的地址为 多少？17 .用序列（ 46, 88, 45, 39, 70, 58, 101, 10, 66, 34）建立一个排序二叉树，画出 该树，并求在等概率情况下查找成功的平均查找长度18 .按下列要求，写出相应结果设关键字的输入次序为 45, 24, 53, 45, 12, 24, 90。画出生成的二叉排序树（5分）。19试画出具有3个结点的二叉树所有不同形态（5分）。写算法1 .请写出顺序存储的线性表中，在第i个位置插入和删除数据元素 x的实现算法。（请在关键部分给出注释。）2 .请写出链式存储的线性表中，在第i个位置插入和删除数据元素 x的实现算法。（请在关键部分给出注释。）3 .请写出链式堆栈操作中，入栈和出栈的实现算法。（请在关键部分给出注释。）河北工程大学
