河北工程大学数据结构复习题.doc

河北工程大学单项选择题1.数据的（B）包括集合、线性、树和图4种基本类型A存储结构 B逻辑结构C基本运算D算法描述2.对一个长度为n的顺序表，在第i个元素（1in+1）之前插入一个新元素时需向右移动（B）个元素。An-iBn-i+1Cn-i-1Di3下面程序的时间复杂度为（C ）。For(i=0;im;i+) For(j=0;jnext=p-next ）， （ p-next=q ）。5数据的（ 逻辑 ）结构与数据元素本身的内容和形式无关。6一个算法的好坏取决于该算法的（ 时间复杂度 ）和（ 空间复杂度 ）。7数据结构中评价算法的两个重要指标是（ 时间复杂度 ）、空间复杂度。 8一个循环队列存储于下标由0开始且长度为m的一维数组中，假定队头和队尾指针分别为front和rear，则判断队空的条件为（rear+1）%n=front）。则判断队满的条件为（ front=rear ）。9 队列的插入操作是在队列的（ 队尾 ）进行，删除操作是在队列的（ 队头 ）进行。10堆栈的逻辑特点是（ 先进后出 ），队列的逻辑特点是（ 先进先出 ）。11堆栈的逻辑特点是（ 先进后出 ），队列的逻辑特点是（ 先进先出 ）。二者的共同点是只允许在它们的（ 端点 ）处插入和删除数据元素。12堆栈操作设输入元素的顺序为1,2,3,4,5，要在栈的输出端得到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、一个哈夫曼(Huffman)树有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,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，请画出这棵二叉树，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、已知一棵二叉树的中序序列和后序序列分别为： 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个位置插入和删除数据元素