数据结构练习1-12章(答案)

1数据结构作业一、设n为整数，利用大“O”记号，求下列程序段的时间复杂度1、i=0;k=0;Do{k=k*10*i;i++;}while(in);//T(n)=O(n)2、i=1;j=0;while(i+j=n){if(ij)j++;elsei++;}//T(n)=O(n)3、x=n;//n1while(x=(y+1)*(y+1))y++;//T(n)=O(n)4、x=91;y=100;while(y0)if(x100){x=x-10;y--;}elsex++;//T(n)=常数=O(1)二、选择题1、从逻辑上可以把数据结构分为（C）两大类。A．动态结构、静态结构B．顺序结构、链式结构C．线性结构、非线性结构D．初等结构、构造型结构2、以下数据结构中，哪一个是线性结构（D）？A．广义表B.二叉树C.稀疏矩阵D.串3、在下面的程序段中，对x的赋值语句的频度为（C）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、下面关于线性表的叙述中，错误的是哪一个？（B）A．线性表采用顺序存储，必须占用一片连续的存储单元。B．线性表采用顺序存储，便于进行插入和删除操作。C．线性表采用链接存储，不必占用一片连续的存储单元。2D．线性表采用链接存储，便于插入和删除操作。5、某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（D）存储方式最节省运算时间。A．单链表B．仅有头指针的单循环链表C．双链表D．仅有尾指针的单循环链表6、静态链表中指针表示的是（B）.A．内存地址B．数组下标C．下一元素地址D．左、右孩子地址7、下面的叙述不正确的是（B、C）A．线性表在链式存储时，查找第i个元素的时间同i的值成正比B.线性表在链式存储时，查找第i个元素的时间同i的值无关C.线性表在顺序存储时，查找第i个元素的时间同i的值成正比D.线性表在顺序存储时，查找第i个元素的时间同i的值无关8、若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（C）(1=i=n+1)。A.O(0)B.O(1)C.O(n)D.O(n2)9、在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（B）。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的带头结点的单链表，判定该表为空表的条件是（B）A．head==NULLB．head→next==NULLC．head→next==headD．head!=NULL11、一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1=i=n）个元素是（B）。A.不确定B.n-i+1C.iD.n-i12、有六个元素6，5，4，3，2，1的顺序进栈，问下列哪一个不是合法的出栈序列？（C）A.543612B.453126C.346521D.23415613、设有三个元素X，Y，Z顺序进栈（进的过程中允许出栈），下列得不到的出栈排列是(C)。A．XYZB.YZXC.ZXYD.ZYX14、假设以数组A[m]存放循环队列的元素,其头尾指针分别为front和rear，则当前队列中的元素个数为（A）。A．(rear-front+m)%mB．rear-front+1C．(front-rear+m)%mD．(rear-front)%m15、若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？(B)A.1和5B.2和4C.4和2D.5和116、下面关于串的的叙述中，哪一个是不正确的？（B）A．串是字符的有限序列B．空串是由空格构成的串C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储17、设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（C）A．求子串B．联接C．匹配D．求串长18、设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为(B)。3A.BA+141B.BA+180C.BA+222D.BA+22519、广义表A=(a,b,(c,d),(e,(f,g))),则下面表达式的值为（D）。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）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是(n-1)/2。3、对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为O(1),在给定值为x的结点后插入一个新结点的时间复杂度为O(n)。4、带头结点的双循环链表L中只有一个元素结点的条件是：L-next==L-prior(或L-prior-prior==L)5、一个栈的输入序列是：1，2，3则不可能的栈输出序列是3,1,2。6、用S表示入栈操作，X表示出栈操作，若元素入栈的顺序为1234，为了得到1342出栈顺序，相应的S和X的操作串为SXSSXSXX。7、队列又称作先进先出表。8、组成串的数据元素只能是字符。9、设有C语言描述的二维数组A[10][20],其每个元素占两个字节，第一个元素的存储地址为100，若按行优先顺序存储，则元素A[6][6]存储地址为352。五、算法设计题1、请设计一算法：已知顺序表L，表中元素为整型且递增有序，现有一值为e的元素要插入L表，使插入后L表仍然有序。2.已知带头结点的动态单链表L中的结点是按整数值递增排列的，试写一算法将值x为的结点插入到表L中，使L仍然有序。3.设计一算法，逆置带头结点的动态单链表L。4.在长度大于1的单循环链表中，既无头结点也无头指针。s为指向链表中某个结点的指针，试编写算法删除结点*s的直接前趋结点。1、方法一:4#defineLIST_INIT_SIZE100#defineLISTINCREMENT10Statussqlist_insert(sqlist&L,inte){int*p,*newbase;if(L.length==L.listsize)//空间不够,需重新申请{newbase=(int*)realloc(L.elem,(L.listsize+Listincrement)*sizeof(int));if(!newbase)exit(overflow);L.elem=newbase;L.listsize+=listincrement;//新基址和存储容量}for(p=L.elem+L.length;p=L.elem&&*pe;--p)//从表尾开始比较和移动*(p+1)=*p;*(p+1)=e;++L.length;Returnok}方法二:Statussqlist_insert(sqlist&L,inte){inti,*newbase;if(L.length==L.listsize)//空间不够,需重新申请{newbase=(int*)realloc(L.elem,(L.listsize+Listincrement)*sizeof(int));if(!newbase)exit(overflow);L.elem=newbase;L.listsize+=listincrement;//新基址和存储容量}for(i=L.length-1;i=0&&L.elem[i]e;--i)//从表尾开始比较和移动L.elem[i+1]=L.elem[i];L.elem[i+1]=e;++L.length;Returnok}2、方法一：VoidLinklist_insert(linklist&L,inte){linklistp,pre;pre=L;p=L-next;//pre是p的直接前驱while(p&&p-datax)5p=p-next;s=(linklist)malloc(sizeof(LNode))s-data=e;s-next=p;//s插在pre的后面，p的前面pre-next=s;}方法二：VoidLinklist_insert(linklist&L,inte){linklistp=L;while(p-next&&p-next-datax)//p的后继与x进行比较p=p-next;s=(linklist)malloc(sizeof(LNode))s-data=e;s-next=p-next;//s插在p的后面p-next=s;}3、Voidlinklist_reverse(linklist&L){linklistp,q;P=L-next;L-next=NULL;While(p){q=p-next;p-next=L-next;//p插在头结点L的后面L-next=p;p=q;}4、Voidlinklist_delete(linklists){linklistp;p=s;while(p-next-next!=s)p=p-next;free(p-next)；删除p的后继p-next=s;p的后继为s}6六、程序填空题不带头结点的单链表L进行就地逆置的算法，用L返回逆置后的链表的头指针。voidreverse（linklist&L）{p=null；q=L；while（q！=null）{(1);q-next=p；p=q；(2)___;}(3)_____;}//（1）L=L-next(2)q=s(3)L=P第六章树选择题1．已知一算术表达式的中缀形式为A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为(D)A．-A+B*C/DEB.-A+B*CD/EC．-+*ABC/DED.-+A*BC/DE2．算术表达式a+b*（c+d/e）转为后缀表达式后为（B）A．ab+cde/*B．abcde/+*+C．abcde/*++D．abcde*/++3.设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1则T中的叶子数为（D）A．5B．6C．7D．84.设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（A）A．m-nB．m-n-1C．n+1D．条件不足，无法确定5．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（B）A．9B．11C．15D．不确定6．具有10个叶结点的二叉树中有（B）个度为2的结点，A．8B．9C．10D．ll7．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（E）A．250B．500C．254D．505E．以上答案都不对8.有n个叶子的哈夫曼树的结点总数为（D）。A．不确定B．2nC．2n+1D．2n-19.一棵具有n个结点的完全二叉树的树高度（深度）是（A）A．logn+1B．logn+1C．lognD．logn-110．深度为h的满m叉树的第k层有（A