《河北工程大学数据结构复习题》由会员分享，可在线阅读，更多相关《河北工程大学数据结构复习题（7页珍藏版）》请在金锄头文库上搜索。
1、河北工程大学单项选择题1.数据的（B ）包括集合、线性、树和图 4 种基本类型A存储结构 B逻辑结构 C基本运算 D算法描述2.对一个长度为 n 的顺序表，在第 i 个元素（1in+1）之前插入一个新元素时需向右移动（B ）个元素。An-i Bn-i+1 Cn-i-1 Di3 下面程序的时间复杂度为（C ） 。For(i=0;inext=p-next ） ， （ p-next=q ） 。5 数据的（ 逻辑 ）结构与数据元素本身的内容和形式无关。6 一个算法的好坏取决于该算法的（ 时间复杂度 ）和（ 空间复杂度 ） 。7 数据结构中评价算法的两个重要指标是（ 时间复杂度 ） 、空间复杂度。 8
2、一个循环队列存储于下标由 0 开始且长度为 m 的一维数组中，假定队头和队尾指针分别为 front 和 rear，则判断队空的条件为（ （rear+1）%n=front） 。则判断队满的条件为（ front=rear ） 。9 队列的插入操作是在队列的（ 队尾 ）进行，删除操作是在队列的（ 队头 ）进行。10 堆栈的逻辑特点是（ 先进后出 ） ，队列的逻辑特点是（ 先进先出 ） 。11 堆栈的逻辑特点是（ 先进后出 ） ，队列的逻辑特点是（ 先进先出 ） 。二者的河北工程大学共同点是只允许在它们的（ 端点 ）处插入和删除数据元素。12 堆栈操作设输入元素的顺序为 1,2,3,4,5，要在栈的输
3、出端得到 43521，则应进行栈的基本运算表示应为：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、一个哈夫曼(Huf
4、fman)树有 19 个结点，则其叶结点的个数是 。15、一棵深度为 6 的满二叉树有 31 个分支结点和 32 个叶子。16、设二叉树结点的先序序列为 ABDECFGH，中序序列为 DEBAFCHG,则二叉树的后序序列是 。 17. 克鲁斯卡尔算法的时间复杂度为（ ） ，适合求（ ）的最小生成树。18.空串是（） ，其长度等于（ ） 。19.空格串是（） ，其长度等于（ ） 。20.两个字符串相等的充分必要条件是（） 。21 写出模式串 p=“abaabcac”的 next 函数值序列为（）22、设有一稀疏图 G，则 G 采用 存储结构较省空间。23、已知广义表 A=(a,b,c),(d,e
5、,f),则运算 head(head (tail（A）)=_ _.24一棵深度为 6 的满二叉树有 个分支结点和 个叶子。25在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第 7 个记录 60 插入到有序表时，为寻找插入位置至少需比较 次。应用题1什么是线性结构？线性结构的特点是什么？ 列举？2.什么是树形结构？树形结构的特点是什么？3.什么是图结构？河北工程大学4.已知二叉树的前序 ABCDEFGHIJ 和中序 CDBFEAIHGJ，试构造出相应的二叉树。5.已知一棵二叉树的后序遍历序列为 EICBGAHDF，中序遍历序列为 ECIFBAGDH，请
6、画出这棵二叉树，7. 对于一个有 10000 个结点的二叉树，树叶最多有多少个？最少有多少个？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、已知
7、一棵二叉树的中序序列和后序序列分别为： DBGEACHF 和 DGEBHFCA，则该二叉树的前序序列是什么？试画出这棵二叉树。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. 请写出链式堆栈操作中，入栈和 出栈的实现算法。 （请在关键部分给出注释。 ）
