数据结构考试题

单项选择数据构造是一门研究非数值计算的程序设计问题中,数据元素的①C、数据信息在计算机中的②A以及一组有关的运算等的课程。①A．操作对象Ｂ．计算措施Ｃ．逻辑构造Ｄ．数据映象②A．存储构造Ｂ．关系Ｃ．运算Ｄ．算法如下数据构造中,D是线性构造。A．广义表Ｂ．二叉树Ｃ．稀疏矩阵Ｄ．串从逻辑上可以把数据构造分为C两大类。A．动态构造和静态构造Ｂ．次序构造和链式构造Ｃ．线性构造和非线性构造Ｄ．初等构造和构造型构造如下数据构造中,D是线性构造。A．广义表Ｂ．二叉树Ｃ．稀疏矩阵Ｄ．串如下数据构造中,D是非线性构造。A．栈Ｂ．二叉树Ｃ．队列Ｄ．字符串数据构造DS(DataStruct)可以被形式地定义为DS=（D，R），其中D是①B的有限集合，R是D上的②D有限集合。①A．算法Ｂ．数据元素Ｃ．数据操作Ｄ．数据对象②A．操作Ｂ．映象Ｃ．存储Ｄ．关系线性表的次序存储构造是一种①A的存储构造,线性表的链式存储构造是一种的②B存储构造。A．随机存取Ｂ．次序存取Ｃ．索引存取Ｄ．散列存取线性表的逻辑次序与存储次序总是一致的，这种说法__B_。A.对的B.不对的下面那一条是次序存储构造的长处?(A)A.存储密度大B.插入运算以便C.删除运算以便D.可以以便的用于多种逻辑构造的存储表达线性表采用链式存储构造时,规定内存中可用的存储单元的地址.A.必须是持续的B.部分地址必须是持续的C.一定不持续D.持续和不持续都可以表长为n的次序存储的线性表,当在任何位置上插入和删除一种元素的概率相等时,插入一种元素所需要移动元素的平均次数为E,删除一种元素所需要移动元素的平均次数为AA.(n-1)/2B.nC.n+1D.n-1E.n/2F.(n+1)/2G.(n-2)/2带头结点的单链表head为空的鉴定条件是_B___。A.head==NULLB.head->next==NULLC.head->next==headD.head!=NULL在一种单链表中,若删除p所指向结点的后继结点,则执行_A___。A.p->next=p->next->nextB.p=p->next;p->next=p->next->nextC.p=p->next->nextD.p=p->next若已知一种栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为_C___。A.iB.n=iC.n-i+1D.不确定设栈的输入次序为:1,2,3,4,5,则不也许是其出栈序列.A.54321B.45321C.43512D.12345一种递归算法必须包括BA.递归部分B.终止条件和递归部分C.迭代部分D.终止条件和迭代部分用链接方式存储的队列,在进行删除操作时DA仅修改头指针B.仅修改尾指针C.头尾指针都要修改D.头尾指针也许都要修改数组A[m]寄存循环队列的元素,其头尾指针分别是front和rear,则目前队列的元素个数是__A__。A.(rear-front+m)%mB.(front-rear+m)%mC.front-rear+1D.rear-front+1栈和队列的共同特点__C__。A.都是先进先出B.都是先进后出C.容许在端点插入和删除元素D.没有共同点一种栈的入栈序列a，b，c，d，e，则栈的输出序列是__A__。A.edcbaB.decbaC.dceabD.abcde栈的特点是__B__，队列的特点是__A__。A.先进先出B.先进后出从一种栈顶指针HS的链表中删除一种结点,用x保留被删除的结点值,执行的语句为__C__。A.x=HS;HS=HS->nextB.HS=HS->next;x=HS->dataC.x=HS->data;HS=HS->nextD.HS->next=HS;x=HS->data在链队列Q中,插入s所指向的结点执行的语句为__C__。A.Q.front->next=s;B.Q.rear->next=s;Q.rear=sC.s->next=Q.rear;Q.rear=sD.s->next=Q.front;Q.front=s空串与空格串是相似的，这种说法__B__。A.对的B.不对的下面有关串的论述,哪一种是不对的的__B__。A.串是字符的有限序列B.空串是由空格构成的串C.匹配模式是串的一种重要运算D.串可以采用链式存储构造设有两个串p和q，求q在p中初次出现的位置的运算称作__B__。A.连接 B.模式匹配C.求子串 D.求串长若串s='software',其子串的数目为BA.8B.37C.36D.9二维数组A中，每个元素A的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始持续寄存在存储器内，该数组按行寄存时，数组元素A[7][4]的起始地址为__C__。A.SA+141B.SA+144C.SA+222D.SA+225对稀疏矩阵进行压缩存储的目的是__C__.A.便于进行矩阵运算B.便于输入输出C节省存储空间D.减少运算的时间复杂度在如下论述中对的的是B线性表的线性存储构造优于链表存储构造二维数组可以当作是其数据元素为线性表的线性表栈的操作方式是先进先出队列的操作方式是先进后出广义表((a),a)的表头为C,表尾为C.A.()B.aC.(a)D.((a))已知广义表L=((x,y,z),a,(u,t,w)),从L中取出原子项t的运算为__D__。A.Head(Tail(Tail(L)))B.Tail(Head(Head(Tail(L))))C.Head(Tail(Head(Tail(L))))D.Head(Tail(Head(Tail(Tail(L)))))树最适合用来表达BA.有序的数据元素B.数据之间具有分支层次关系的数据C.无序的数据元素D.无太多关系的数据元素假如某二叉树的前根次序遍历成果为stuwv，中序遍历为uwtvs，那么该二叉树的后序为__B__。A.uwvtsB.vwutsC.wuvtsD.wutsv某二叉树的前序遍历结点访问次序是abdgcefh，中序遍历的结点访问次序是dgbaechf，则其后序遍历的结点访问次序是__D__。A.bdgcefhaB.gdbecfhaC.bdgaechfD.gdbehfca在一非空二叉树的中序遍历序列中，根结点的右边__A__。A.只有右子树上的所有结点B.只有右子树上的部分结点C.只有左子树上的部分结点D.只有左子树上的所有结点设m和n是一棵二叉树上的两个结点,在中序遍历,n在m前的条件是CA.n在m的右方B.n是m的祖先C.n在m的左方D.n是m的子孙深度为5的二叉树至多有__C__个结点。A.16B.32C.31D.10由权(8,2,5,7)的四个叶子结点构造一棵哈夫曼树,该树的带权途径长度为DA.23B.37C.46D.43运用二叉链表存储树,则根结点的右指针是CA.指向最左孩子B.指向最右孩子C.空D.非空下列存储方式中,哪一种不是树的存储形式?DA.双亲表达法B.孩子链表表达法C.孩子兄弟表达法D.次序存储表达法在一种无向图中，所有顶点的度数之和等于所有边数的__C__倍。A.1/2B.1C.2D.4具有n个顶点和多于n-1条边的无向图B.A.有也许是树B.一定不是树C.一定是树D.以上答案都不对具有6个顶点的无向图至少应有__A__条边才能保证是一种连通图。A.5B.6C.7D.8无向图G=(V,E),其中:V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)},则对该图进行深度优先遍历,得到的序列为:DA.abecdfB.acfebdC.aebcfdD.aedfcb下述几种排序措施中，规定内存量最大的是__D__。A.插入排序B.选择排序C.迅速排序D.归并排序排序措施中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的对的位置上的措施，称为__C__。A.希尔排序B.起泡排序C.插入排序D.选择排序在待排序的元素序列基本有序的前提下，效率最高的排序措施是__A_。插入排序B.选择排序C.迅速排序D.归并排序下列排序算法中,哪一种是稳定的排序算法?BA.直接选择排序B.二分法插入排序C.希尔排序D.迅速排序将两个各有n个元素的有序表归并成一种有序表,其至少的比较次数AA.nB.2n-1C.2nD.n-1填空题算法的五个重要特性是有穷性,确定性,可行性,输入和输出.数据的树型构造和图(网)状构造合称非线性构造.抽象数据类型的定义仅取决于它的一组逻辑特性,而与数据在计算机中的表达和实现无关.评价算法质量的指标是对的性,易读性,强健性,高效性.数据构造中评价算法的两个重要指标是:时间复杂度和空间复杂度.分析下面算法（程序段），的时间复杂度是__O(mn)__。s=0;for(i=0;i<n;i++)for(j=0;j<m;j++)s+=B[i][j];当线性表元素的总数基本稳定,且很少进行删除和插入操作时,不过规定以最快的速度存取线性表中的元素,应当采用次序存储构造.次序表中逻辑上相邻的元素的物理位置必然相邻,而单链表中逻辑上相邻的元素的物理位置不一定相邻.在各个结点查找概率相等的状况下,从n个结点的单链表中查找一种结点,平均要访问n/2个结点.在单链表中设置头指针的作用是:简化操作,减少边界条件的判断.在单链表中,除首元结点外,任一结点的存储位置由其直接前驱的指针域指示.对于一种具有n个结点的单链表,在已知p所指向结点后插入一种新结点的时间复杂度是O(1),在值域为给定值的结点后插入一种新结点的时间复杂度为O(n).在双链表中，每个结点有两个指针域，一种指向_前驱结点__，另一种指向__后继结点___。根据线性表的链式存储构造中每一结点包括的指针个数,将线性表提成单链表和多重链表.在非空双向链表中,在结点q的前面插入结点p的过程如下,请补充p->prior=q->prior;q->prior->next=p;p->next=q;q->prior=p;一般状况下,将递归算法转换成等价的非递归算法应当设置栈.在处理计算机主机与打印机速度不匹配问题时,一般设置一种打印数据缓冲区,该缓冲区一般是一种队列数据构造.循环队列的引入,目的是为了克服假溢出现象.在栈顶指针为HS的链栈中,判断栈空的条件是HS=NULL.在具有n个单元的循环队列中,假如不专门设置队满标志,则队满时共n-1有个元素.实现字符串拷贝的函数如下,请补足Voidstrcpy(char*s,char*t){while((*s++=*t++)!='\0');}空格串是__由一种或多种空格字符构成的串__，其长度等于_其包括的空格个数。空串是不包括任何字符的串,其长度为0.设s='IAMASTUDENT',其长度为:14.构成串的元素只能是:字符.设s1='Good',s2='',s3='bye!',则s1,s2和s3连接的成果是Goodbye!若广义表中每个元素都是原子时,广义表便成为线性表.广义表的表尾是指除第一种元素外,剩余元素构成的表.广义表A=((a,b,c,d))的表头为(a,b,c,d),表尾为().数组的存储构造采用次序存储方式.设二维数组a[0..5,0..6],其每个字节占5个字节,第一种元素的存储地址为1000,若按列存储,则元素a[5,5]存储地址为1175.高度为k的完全二叉树至少有个叶子结点.若一棵二叉树有50个叶子结点,则该二叉树的总结点数至少是99.有n个叶子结点的哈夫曼树的结点总数为2n-1.根据二叉树的定义,具有三个结点的二叉树有4种.某棵二叉树的中序遍历序列为abcdefg,后序遍历序列为bdcafge,则该二叉树的前序遍历序列eacbdgf,该二叉树对应的森林包括2棵二叉树.若二叉树采用二叉链表存储构造,要互换其所有分支结点的左,右子树的位置,运用中序遍历措施最为合适.线索二叉树的左线索指向其前驱,右线索指向其后继.树所对应的二叉树其根结点的右子树一定为空.运用树的孩子兄弟表达法存储,可以将一棵树转化成二叉树.设无向图的顶点个数为n,则该图最多有n(n-1)/2条边.n个顶点的连通图至少有n-1条边.已知一种图用领接矩阵表达,计算第i个结点的入度的措施是求第i列非零元素的和.G是一种非连通的无向图,共有28条边,则该图至少有9个顶点.一种图的邻接矩阵表达法是唯一的，而邻接表表达法是不唯一的。从邻接矩阵可以看出,该图共有3个顶点,假如是无向图,则共有2条边.n个顶点的连通图用邻接矩阵表达时,则该矩阵至少有2(n-1)个顶点.设图中有n个顶点,e条边,假如用邻接表表达图,进行深度优先搜索遍历的时间复杂度为O(n+e),假如用邻接矩阵表达图,时间复杂度为从平均时间性能而言,迅速排序排序最佳.堆排序是一种选择排序,堆实质上是一棵完全二叉树结点的层次序列.对于具有n个元素的排序,堆排序的时间复杂度为.所需附加的存储结点是O(1).用图表回答问题设某通信系统使用A，B，C，D，E，F，G，H个字符，出现的频率w={５，２９，７，８，１４，２３，３，１１}，试构造对应的哈夫曼树（请按左子树根结点的权不不小于右子树树根结点的权的次序构造）?答案如图:DD8F23H111942A5B29C7E14G38152958100根据下面的邻接链表，画出对应的图，写出每个顶点的度,并用邻接矩阵表达.v1v1v3v2v4v5v6v2v5v4v3v5^^v6v4v6v3^^答案如图所示:v1v2v1v2v3v4v5V6V2:2V3:3V4:2V5:4V6:2画出下列树对应的二叉树，并写出其先根遍历序列：BBDFCAEG先根遍历序列：ABDEGFC答案如图所示:BBEGDFCA画出和下列二叉树对应的森林：AAAAABBBCCC答:AAAAABBBCCC阅读下列算法，按规定做答.下面是删除单链表L中最大元素所在结点的类C语言算法,请补足缺失部分使其完整.voidDelMax(LinkListL){r=L;p=L->next;if(p){m=p->data;(1);p=p->next;while(p){if((2)){(3);m=p->data;}(4);p=p->next;}q=r->next;(5);free(q);}}答案:(1)L->next=NULL;(2)p!=NULL;(3)q!=NULL;(4)p->next=r->next(5)r->next=p.阅读下列算法，阐明该算法的作用。Statusalgorithm1(LinkQueue&Q){ SqStack Stack; QElemType Element; InitStack(Stack); while(!QueueEmpty(Q)){ DeQueue(Q,Element); Push(Stack,Element); } while(!StackEmpty(Stack)){ Pop(Stack,Element); EnQueue(Q,Element); }}答:运用栈实现队列的逆置.阅读下列算法，阐明该算法的作用。Statusalgorithm2(StackS,inte){ Stack T; int d; InitStack(T); while(!StackEmpty(S)){ Pop(S,d); if(d!=e)Push(T,d); }while(!StackEmpty(T)){ Pop(T,d); Push(S,d); }}答:运用辅助栈T,将栈S中的元素e删除.将下面程序改写成递归过程.voidalgorithm3(intn){ int i=n;while(i>1){ printf(i--); }}答:voidalgorithm4(intj){if(j>1){printf(j);algorithm4(j-1) }}阅读下列算法，阐明该算法的作用。BiTreealgorithm5(ElemTypePre[],ElemTypeIn[]){ intPreLen,InLen; inti,j; BiTreeBT; ElemType*subPre,*subIn; PreLen=strlen(Pre); InLen=strlen(In); if(PreLen!=InLen||PreLen==0)returnNULL; for(i=0;i<InLen&&In[i]!=Pre[0];i++); if(i==InLen)returnNULL; BT=(BiTNode*)malloc(sizeof(BiTNode)); BT->data=Pre[0]; subPre=(ElemType*)malloc((i+1)*sizeof(ElemType)); subIn=(ElemType*)malloc((i+1)*sizeof(ElemType)); for(j=0;j<i;j++){ subPre[j]=Pre[j+1]; subIn[j]=In[j]; } subPre[j]='\0';subIn[j]='\0'; BT->lchild=CreatBT(subPre,subIn); subPre=(ElemType*)malloc((PreLen-i)*sizeof(ElemType)); subIn=(ElemType*)malloc((PreLen-i)*sizeof(ElemType)); for(j=i+1;j<PreLen;j++){ subPre[j-i-1]=Pre[j]; subIn[j-i-1]=In[j]; } subPre[j-i-1]='\0';subIn[j-i-1]='\0'; BT->rchild=CreatBT(subPre,subIn); returnBT;}答:运用一棵二叉树的先序遍历和中序遍历还原该二叉树.算法设计题设次序表L中的数据元素递增有序.试写一种算法,将e插入次序表中,规定插入后保持该表的有序性.voidInsertElem(SqList&L,ElemType){j=L.length-1;whi