数据结构练习1-12章

1数据结构作业一、设n为整数，利用大“O”记号，求下列程序段的时间复杂度1、i=0;k=0;Do{k=k*10*i;i++;}while(in);2、i=1;j=0;while(i+j=n){if(ij)j++;elsei++;}3、x=n;//n1while(x=(y+1)*(y+1))y++;4、x=91;y=100;while(y0)if(x100){x=x-10;y--;}elsex++;二、选择题1、从逻辑上可以把数据结构分为（）两大类。A．动态结构、静态结构B．顺序结构、链式结构C．线性结构、非线性结构D．初等结构、构造型结构2、以下数据结构中，哪一个是线性结构（）？A．广义表B.二叉树C.稀疏矩阵D.串3、在下面的程序段中，对x的赋值语句的频度为（）for(i=1;i=n;i++)for(j=1;j=n;j++)x=x+1;A．O(2n)B．O(n)C．O(n2)D．O(log2n)4、下面关于线性表的叙述中，错误的是哪一个？（）A．线性表采用顺序存储，必须占用一片连续的存储单元。B．线性表采用顺序存储，便于进行插入和删除操作。C．线性表采用链接存储，不必占用一片连续的存储单元。D．线性表采用链接存储，便于插入和删除操作。5、某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。A．单链表B．仅有头指针的单循环链表C．双链表D．仅有尾指针的单循环链表6、静态链表中指针表示的是（）.A．内存地址B．数组下标C．下一元素地址D．左、右孩子地址7、下面的叙述不正确的是（）A．线性表在链式存储时，查找第i个元素的时间同i的值成正比B.线性表在链式存储时，查找第i个元素的时间同i的值无关C.线性表在顺序存储时，查找第i个元素的时间同i的值成正比2D.线性表在顺序存储时，查找第i个元素的时间同i的值无关8、若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（）(1=i=n+1)。A.O(0)B.O(1)C.O(n)D.O(n2)9、在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（）。A．p-next=s;s-next=p-next;B．s-next=p-next;p-next=s;C．p-next=s;p-next=s-next;D．p-next=s-next;p-next=s;10、对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（）A．head==NULLB．head→next==NULLC．head→next==headD．head!=NULL11、一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1=i=n）个元素是（）。A.不确定B.n-i+1C.iD.n-i12、有六个元素6，5，4，3，2，1的顺序进栈，问下列哪一个不是合法的出栈序列？（）A.543612B.453126C.346521D.23415613、设有三个元素X，Y，Z顺序进栈（进的过程中允许出栈），下列得不到的出栈排列是()。A．XYZB.YZXC.ZXYD.ZYX14、假设以数组A[m]存放循环队列的元素,其头尾指针分别为front和rear，则当前队列中的元素个数为（）。A．(rear-front+m)%mB．rear-front+1C．(front-rear+m)%mD．(rear-front)%m15、若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？()A.1和5B.2和4C.4和2D.5和116、下面关于串的的叙述中，哪一个是不正确的？（）A．串是字符的有限序列B．空串是由空格构成的串C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储17、设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（）A．求子串B．联接C．匹配D．求串长18、设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为()。A.BA+141B.BA+180C.BA+222D.BA+22519、广义表A=(a,b,(c,d),(e,(f,g))),则下面表达式的值为（）。Head(Tail(Head(Tail(Tail(A)))))A.(g)B.(d)C.cD.d三、判断题1、数据元素是数据的最小单位。()2、顺序存储方式的优点是存储密度大，且插入、删除运算效率高。()3、线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。()4、线性表的特点是每个元素都有一个前驱和一个后继。()5、一个稀疏矩阵Am*n采用三元组形式表示，若把三元组中有关行下标与列下标的值互换，并把m和n的值互换，则就完成了Am*n的转置运算。（）6、所谓取广义表的表尾就是返回广义表中最后一个元素。（）四、填空题1、当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_______存储结构。2、线性表L=（a1,a2,…,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是________。33、对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为________,在给定值为x的结点后插入一个新结点的时间复杂度为________。4、带头结点的双循环链表L中只有一个元素结点的条件是：________5、一个栈的输入序列是：1，2，3则不可能的栈输出序列是_______。6、用S表示入栈操作，X表示出栈操作，若元素入栈的顺序为1234，为了得到1342出栈顺序，相应的S和X的操作串为_______。7、________又称作先进先出表。8、组成串的数据元素只能是________。9、设有C语言描述的二维数组A[10][20],其每个元素占两个字节，第一个元素的存储地址为100，若按行优先顺序存储，则元素A[6][6]存储地址为_______。五、算法设计题1、请设计一算法：已知顺序表L，表中元素为整型且递增有序，现有一值为e的元素要插入L表，使插入后L表仍然有序。2、已知L为非递减的顺序表，请设计算法删除L中重复的元素（即删除后使L表变为一递增表）。3、已知带头结点的动态单链表L中的结点是按整数值递增排列的，试写一算法将值x为的结点插入到表L中，使L仍然有序。4、设计一算法，逆置带头结点的动态单链表L。5、在长度大于1的单循环链表中，既无头结点也无头指针。s为指向链表中某个结点的指针，试编写算法删除结点*s的直接前趋结点。六、程序填空题不带头结点的单链表L进行就地逆置的算法，用L返回逆置后的链表的头指针。voidreverse（linklist&L）{p=null；q=L；while（q！=null）{(1);q-next=p；p=q；(2)___;}(3)_____;}第六章树选择题1．已知一算术表达式的中缀形式为A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为()A．-A+B*C/DEB.-A+B*CD/EC．-+*ABC/DED.-+A*BC/DE2．算术表达式a+b*（c+d/e）转为后缀表达式后为（）A．ab+cde/*B．abcde/+*+C．abcde/*++D．abcde*/++3.设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1则T中的叶子数为（）A．5B．6C．7D．84.设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（）A．m-nB．m-n-1C．n+1D．条件不足，无法确定5．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）A．9B．11C．15D．不确定6．具有10个叶结点的二叉树中有（）个度为2的结点，A．8B．9C．10D．ll7．一棵完全二叉树上有1001个结点，其中叶子结点的个数为（）4A．250B．500C．254D．505E．以上答案都不对8.有n个叶子的哈夫曼树的结点总数为（）。A．不确定B．2nC．2n+1D．2n-19.一棵具有n个结点的完全二叉树的树高度（深度）是（）A．logn+1B．logn+1C．lognD．logn-110．深度为h的满m叉树的第k层有（）个结点。(1=k=h)A．mk-1B．mk-1C．mh-1D．mh-111．在一棵高度为k的满二叉树中，结点总数为（）A．2k-1B．2kC．2k-1D．log2k+112．对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用()次序的遍历实现编号。A．先序B.中序C.后序D.从根开始按层次遍历13．树的后根遍历序列等同于该树对应的二叉树的().A.先序序列B.中序序列C.后序序列14．已知某二叉树的后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历是（）。A．acbedB．decabC．deabcD．cedba15．二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK；中序遍历:HFIEJKG。该二叉树根的右子树的根是：A、EB、FC、GD、H16．n个结点的线索二叉树上含有的线索数为（）A．2nB．n－lC．n＋lD．n17．下述编码中哪一个不是前缀码（）。A．（00，01，10，11）B．（0，1，00，11）C．（0，10，110，111）D．（1，01，000，001）18．从下列有关树的叙述中,选出5条正确的叙述（）A．二叉树中每个结点有两个子结点,而树无此限制,因此二叉树是树的特殊情况。B．当K≥1时高度为K的二叉树至多有2k-1个结点。C．用树的前序周游和中序周游可以导出树的后序周游。D．线索二叉树的优点是便于在中序下查找前驱结点和后继结点。E．将一棵树转换成二叉树后,根结点没有左子树。F．一棵含有N个结点的完全二叉树,它的高度是LOG2N+1。G．在二叉树中插入结点,该二叉树便不再是二叉树。H．采用二叉树链表作树的存储结构,树的前序周游和其相应的二叉树的前序周游的结果是一样的。I．哈夫曼树是带权路径最短的树,路径上权值较大的结点离根较近。J．用一维数组存储二叉树时,总是以前序周游存储结点。判断题：1．完全二叉树中，若一个结点没有左孩子，则它必是树叶。2.二叉树只能用二叉链表表示。3．在二叉树的第i层上至少有2i-1个结点(i=1)4．度为二的树就是二叉树。5.在中序线索二叉树中，每一非空的线索均指向其祖先结点。填空题：1．具有256个结点的完全二叉树的深度为______。2．已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树有______个叶子结点。3．在一棵二叉树中，度为零的结点的个数为N0,度为2的结点的个数为N2,则有N0=______4．已知二叉树有50个叶子结点，则该二叉树的总结点数至少是______。55．设F是由T1,T2,T3三棵树组成的森林,与F对应的二叉树为B,已知T1,T2,T3的结点数分别为n1,n2和n3则二叉树B的左子树中有__(1)_个结点，右子树中有_(2)__个结点。6．如某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点数为______。算法应用题1、已知一棵度为m的树中有n1个度为1的结点，n2个度为2的结点，……，nm个度为m的结点，问该树中有多少个叶子结点？2、已知一棵满二叉树的结点个数为20到40之间的素数，此二叉树的叶子结点有多少个？（请给出具体的推理过程）3、请采用顺序存储方式和链式存储方式，分别写出下图所示二叉树的存储结构。ABCDEFGH4、求出上图所示二