数据结构练习题1

11.数据结构通常是研究数据的逻辑结构和物理结构及它们之间的联系。2.在数据结构的讨论中，把数据结构从逻辑上分为线性结构和非线性结构。其中，线性表、栈和队列均属于线性结构，而二叉树和图属于非线性结构。3.如果一个算法不管问题规模大小，其运行所需的时间都相同，则该算法的时间复杂度是O(1)，称为常数阶时间。4.t=1;i=1;while(i=n){t=t*i;i++;}上述语句的时间复杂度为O(n)。5.在一个长度为n的顺序表中，在第i个元素（1≤i≤n+1）之前插入一个新元素时，需要向后移动n+2-i个元素；而删除第i个（1≤i≤n）位置上的数据元素需要移动表中n-i个元素。6.判断下面说法的对错：1)线性表采用顺序存储必须占用一片连续的存储空间对2)线性表采用链式存储不必占用一片连续的存储空间对3)线性表采用链式存储便于插入和删除操作的实现对4)线性表采用顺序存储便于插入和删除操作的实现错7.链表是一种采用链式存储结构存储的线性表，其特点是利用指针来表示数据元素之间的逻辑关系；而顺序表则是一种采用顺序存储结构存储的线性表。在线性表中，除第1个结点无前驱结点外，其余每个结点有且只有1个直接前驱结点。8.单链表中的每个结点包含数据域和指针域；而双向链表的每个结点有两个指针域，一个指向后继节点，另一个指向前驱节点。9.设指针变量p指向单链表结点A，指针变量s指向新结点B，则删除结点A的后继结点需做的操作为p-›next=p-›next-›next_。而在结点A的后面插入结点B的操作语句序列为：s-›next=p-›next;和p-›next=s。10.在一个以h为头的单循环链表中，判断p指针指向链尾的条件是p-›next==null。在一个以h为头的单链表中，判断该单链表为空的条件是h--›next==null。11.判断下面说法的对错：1)栈是在两端操作、先进后出的线性表对2)栈是在一端操作、先进先出的线性表错3)队列是在一端操作、先进先出的线性表错4)队列是在两端操作、先进先出的线性表对12.5个元素进T栈的顺序是1、2、3、4、5，经两次出栈运算后栈顶元素是3。5个元素进T队的顺序是1、2、3、4、5，经两次出队运算后队头元素是3。13.一个栈的输入序列是a、b、c、d、e，判断以下栈的输出序列是不正确的是21)edcba2)decba3)dceab4)abcde14.用链接方式存储的含多个元素的非空队列，在进行插入运算时需修改rear指针，在进行删除运算时需修改front指针。15.一个队列的入队序列是{A，B，C，D}，则队列的输出序列是ABCD。16.用front和rear分别表示顺序循环队列的队首和队尾指针，M表示队列中能存放的最大元素个数，则判断队空的条件是front==rear；判断队满的条件是（rear+1）%M==front。17.一个递归模型是由递归出口和递归体两部分组成，其中递归出口是指递归的结束条件。18.己知二维数组A[3][5]采用行序为主方式存储，每个元素占2个存储单元，并且A[0][0]的存储地址是1000，则A[2][3]的地址是1007。19.如果树的结点A有2个兄弟，而且R为A的双亲，则R的度为3。20.设一棵二叉树共有10个叶子结点，则共有9个度为2的结点。21.在二叉树中，度为0的结点称为叶子节点；而度为非0的结点称为分支节点。22.一棵完全二叉树采用顺序存储结构，根结点的编号为1。若编号为i的元素有左孩子和右孩子，则该结点左孩子的编号为2i-1，右孩子的编号为2i，双亲结点的编号为i/2。23.一棵完全二叉树中根结点的编号为1，而且13号结点有左孩子但没有右孩子，则完全二叉树总共有25个结点。24.同时知道一棵二叉树的先序序列和中序序列，就能确定这棵二叉树。25.在由n个带权叶子结点构造出的所有二叉树中，树的带权路径长度最小的二叉树称为哈夫曼树。26.一棵Huffman树共有11个结点，该Huffman树总共有个叶子结点。27.一棵Huffman树是由11个叶子结点形成的，该Huffman树总共有个结点。28.设某有向图中有n个顶点和e条边，则该有向图对应的邻接表中有个表头结点，邻接矩阵共有个元素，其中非零元素有个。29.一个有n个顶点的连通无向图至少有条边。30.在双向链表存储结构中，删除p所指结点的操作序列是。而在p所指结点之前插入新结点s的操作序列是。31.一个连通无向图有7个顶点13条边，则其生成树有条边。32.可以判断一个有向图中是否含有回路的方法为。33.若有向图G中，顶点表示活动或任务，边表示活动或任务间的，则此有3向图称为顶点表示活动的网络，即AOV网。34.有n个顶点的有向完全图有条边。有n个顶点的无向完全图有条边。35.请指出在有序表（1，32，41，45，62，75，77，82，95，100）中用折半查找法查找关键码80需做次关键码比较才可确定查找失败，其中比较过的关键码依次为。若采用顺序查找法查找关键字62，需做次关键码比较才可确定查找成功，其中比较过的关键码依次为。36.序遍历一棵二叉排序树所得到的结点访问序列是键值的有序序列。（递增还是递减？）37.在哈希表中，不同的关键码映射到同一个哈希地址上的现象称为，而映射到同一个哈希地址上的关键码称为。38.设哈希表长为m，哈希函数H(key)=key%p，则p的值最好取。39.设一组初始记录关键字序列（36，89，25，47，39，28，66，13），以第一个记录关键字36为基准进行一趟快速排序的结果为。采用冒泡排序法按升序排列时第一趟排序结果是。40.求下图中从顶点v1出发，到其他各顶点的最短路径长度及最短路径。41.判断下图是否存在回路？如果不存在回路，请写出其拓扑排序序列。42.将下图所示的树转换为二叉树，并写出该二叉树的先序、中序和后序遍历序列。43.以顶点①为起点，用Prim算法求出下图的最小生成树。444.写出第40题所示的有向图的邻接矩阵，并求出从顶点V1出发的深度优先遍历序列，遍历时要求按顶点的编号顺序排列。45.已知一棵二叉树的先序序列为ABCDEFG,中序序列为CBEDAFG，请构造此二叉树。46.设哈希表的长度m＝10，哈希函数为H（K）＝K%7，给定的关键码序列为70，34，55，23，65，41，20。试画出用线性探查法解决冲突时所构造的哈希表。47.己知稀疏矩阵如下所示，请画出它的三元组表的示意图。1500220-150113000000600A=000000910000000000048.分别用直接选择排序法和直接插入排序法对关键字序列18，2，20，34，12，32，6，16，进行排序，请写出其排序过程。49.给定权值集合w＝{2，3，4，7，8，9},对应字符分别为a,b,c,d,e,f，请画出对应的Huffman树（约定左子树根结点的权小于右子树根结点的权的次序），写出每个字符的Huffman编码（约定左分支编码为0,右分支编码为1），并计算WPL。50.将关键字序列｛4，5，7，2，1，3，6｝中的关键字依次插入到一棵空的二叉排序树中，试构造相应的二叉排序树，并求在等概率的情况下查找成功时的平均查找长度。