数据结构与算法设计考研复习模拟题及答案电子工业

一、单项选择一个算法应该是 D．A和算法指的是 计算机程 B.解决问题的计算方C.排序算 D.解决问题的有限运算序列与数据元素本身的形式、内容、相对位置、个数无关的是数据的 A.结 B.逻辑结 C.算 D.操 B．顺序结构、链式结构 线性表采用链式时，节点的的地址 B.连续与否均C.必须是连续 D.和头节点的地址相连在下面的程序段中，对x的赋值语句的频度为 FORi:=1 FORj:=1TO nDO2 D．O(log2程序段FOR FORj:=1TOiDOIF A[j]与A[j+1]对换其中n为正整数，则最后一行的语句频度在情况下是 A. B. C. D.intfact(int if(n<=0) n*fact(n-1) } ）A. B. C. D.n-用链表表示线性表的优点是 便于随机存 C．便于插入与删 D．数据元素的物理顺序与逻辑顺序相链表不具有的特点是 ） A.n- B. C. D.n-n的顺序表示，搜索成功的平均搜索长度为（A. B. C.(n- D.将长度为n的单链表在长度为m的单链表之后的算法的时间复杂度为（A. B. C. D. B.head-C. D.head- 链式栈与顺序栈相比，一个比较明显的优点是 插入操作更加方 C.不会出现栈空的情 D.删除操作更加方来看，通常递归过程比非递归过程（）。A.较 B.较 C.相 D.不则pi为 ）A B.n= C.n- D. )A. B. C. D.栈序列是()。A. B.C. D.对于栈操作数据的原则是 ）A.先进先 B.后进先 C.后进后 D.不分顺栈和队列的共同点是 ） B.都是先进后C.只允许在端点处插入和删除元 D.没有共同 ）A. B. D.则执行出对操作后其头指针front指为（）。 引起循环队列队头位置发生变化的操作是A.出 B.入 C.取队头元 D.取队尾元 二维数组A[12][18]采用列优先的方法若每个元素各占 地址为150，则元素A[9][7]的地址为()A. B. C. D.B[]中，A[0][0]存入B[0]中，则A[8][5]B[]中（）位置。A. B. C. D.若对n 阶对称矩阵A 素)依次存放于一维数组［1..(n(n+1))/2中则在B中确定aji<j的位置k的关系为( A.i*(i- B.j*(j- C. D. 树中所有结点的度之和等于所有结点数加（）A. C. D.在一棵具有n个结点的二叉链表中，所有结点的空域个数等于 ）A. B.n- C. D.某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（）空或只有一个结 B.高度等于其节点C.任一结点无左孩 D.任一结点无右孩h02的结点，则此类二叉树中所包含的结点数至少为（）。A. B.2h- C. D.33221的节点个数为（）A. B. C. D.n,森林F中第一棵的结点个数是 ） 号为1，则编号为49的节点的左孩子编号为（）。A B. C. D.下列图示的顺序结构表示的二叉树是(A树最适合用来表示 ）有序数据元 B.无序数据元C.元间具有分支层次关系的数 D.元间无联系的数在一个非空二叉树的中序遍历序列中，根结点的右边 ）只有右上的所有结 B.只有右上的部分结C.只有左的上的部分结 D.只有左上的所有结任何一棵二叉树的叶结点在先序、中序和后序遍历序列中相对次序 ）A.不发生改 B.发生改 C.不能确 D.以上都不在有n个叶子结点的树中，其结点总数为 ）A.不确 B. C. D.2n-权值为{1,2,6,8}的四个结点构成的树的带权路径长度是（）A. B. C. D.对一个满二叉树，m个树叶，k个分枝结点，n个结点，则（）A. B. C.m=k- D.ne条边的无向图的邻接矩阵中，零元素的个数为（）A. B. C.n2- D.n2-若采用邻接矩阵翻一个n个顶点的无向图，则该邻接矩阵是一个 ）A.上三角矩 B.稀疏矩 C.对角矩 D.对称矩在一个图中，所有顶点的度数之和等于所有边数的 A. B. C. D.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 ）倍A. B. C. D.n个顶点的连通图至少中含有 A.n- B. C. D.n个顶点的完全有向图中含有 n-1条有向 B.n条有向C.n(n-1)/2条有向 D.n(n-1)条有向所有弧的时间复杂度是（）。A. B. C. 在无向图中定义顶点Vi域Vj之间的路径为从Vi到达Vj的一个 ）A.顶点序 B.边序 C.权值总 D.边的条由同一组关键字集合构造的各棵二叉排序树 下面哪一方法可以判断出一个有向图是否有环（回路）A.求节点的 B.拓扑排 C.求最短路 D.求关键路图的广度优先搜索类似于树的 ）次序遍历A.先 B.中 C.后 D.层在图采用邻接表时，求最小生成树的Prim算法的时间复杂度为 A. B. C. D.<V2,V5>,<V3,V5>,<V3,V6>,<V4,V6>,<V5,V7>,<V6,V7>},G（ 关键路径是结点网络中 ） 对关键字序列(56,23,78,92,88,67,19,34)进行增量为3的一趟排序的结果 ) B.C. D.则采用的方法是 A.直接选择排 B.排 C.归并排 D.快速排基准得到的第一次划分结果为（）。 B.C. D.下列排序算法中不稳定的是 A.直接选择排 B.二分插入排 C.冒泡排 D.快速排 A.直接选择排 B.直接插入排 C.快速排 D.冒泡排iLi，那么查找失败到达失败点时所做的数据比较次数是（） （）A. B. C. D.衡量查找算法效率的主要标准是（）元素的个数B.所需的量C.平均查找长度D.算法难易程适合对动态查找表进行高效率查找的组织结构是（）A.有序表B.分块有序表C.二叉排序树D.快速排序n个元素,可以构造出的逻辑结构有集合，线性表，树，图顺序映象的特点是借助元素在器中的相对位置来表示数据元间的逻辑关系非顺序映象的特点是借助是指示元素地址的指针表示数据元素之间的逻辑关系。任何一个算法的设计取决于选定逻辑结构，而算法的实现依赖于采用的结构。在带有头结点的单链表中L中，第一个元素结点的指针 head可用p表示为 设单链表的结点结构为(data,next)，nextpxdatax的结点，指针py指向datay的新结点,若将结点y插入结点x之后，则需要执行以下语句:py->next=px->next;px->next=py。 栈下溢是指 栈 出栈顺序，相应的P和D的操作串 循环队列的引入，目的是为了克 假溢出 二位数组Am×n按行优先顺序在内存中元素a00地址为loc(a00),每个元素在内存中占d个字节元素aij的地址计算为 表 树内个结点的 最大 称为树的度一个二叉树第5层节点最多 个已知完全二叉树T的第5层只有7个结点，则该树共 在一棵二叉树中度为零的结点的个数为N0,度为2的结点的个数为N2,则有N0= 在图中任何两个结点之间都可能存在关系因此图的数据元间时一种 对多的关系。在有向图中，以顶点v为终点的边的数目称为v 入 一个无向图有n个顶点，e条边，则所以顶点的度数之和 2eT（24341633829207 2产生现象的两个关键字称为该散列函数 同义 在散列函数H(key)=keyMODp中，p应 素 设哈希表长m=14,哈希函数H(key)=keyMOD11.表中已有4个结点；addr(15)=4,addr(38)=5,addr(61)=6,addr(84)=7,其余地址为空。如用二次探测再散列处理，关键字为49的结点的地址是 排序是属 插 三、程序填空voidreverse(pointer/*h{pointer {q=p;p=p->next;q->next=h->next;h- } ∥链表未到尾就一直 ∥将当前结点作为头结点后的第一元素 reverse（linklist{p=null；q=L；{ ; }L=L- ∥暂存后 ∥待逆置结 ∥头指针仍为四、解答写出队满的条件表达式写出队空的条件表达式设m=40,rear=13,quelen=19,求队头元素的位置写出一般情况下队头元素位置的表达quelen==quelen==(13-19+40)%40=(rear-quelen+m)%B / A ABCABCDEFGHA,B,D,G,J,E,H,C,F,I,K,L中序序列：D,J,G,B,E,H,A,C,K,I,L,F写出该二叉树的后序序列画出该二叉该二叉树的形式如图所示 BCEDF IJ 该二叉树高度为：5造一棵树，并求其路径长度WPL，字符c的编码。WPL＝80c：001（不唯一BFS0123456789111212111 （3）ASLsucc （4）ASLunsucc设有一组关键字{9,01,23,14,55,20,84,27}，采用哈希函数：H（key）=keymod7，012345678911123412以关键字27为例：H（27）=27%7=6（）H1=（6+1）%10=7（ H=（6+22）%10=0（ H 所以比较了4次 快速排序：(21,13,17,)1330,60,58,28,30*,90堆排序：归并排序按层遍历 (1721 60 ( 58 四、算法设计题(10分voidtest(int{intx；if(x=0)sum=0else{test(sum);sum+=x;}} voidmain() (1分){intx,sum=0,top=0,s[]; whiles[++top]:=ascanf(“%d”,&x(3while(top)}structedgenode intadjvex; } voidmatritolist(intg[][],adjlistgl,intn edgenode*p,for(inti=0i<n;i++) for(inti=0;i<n;i++)for(intj=0;j<n; (g[i][j]!=0p=(edgenode*)malloc(sizeof(edgenode)); }} while((ch=getchar( }}xxet^tvoidadd_poly(Lnode*pa,Lnode{Lnode int while((p!=NULL)&&((q!=NULL)) (p->exp<q- pre=p;p=p->next; if(p->exp==q->exp){x=p->coef+q-if(x!=0){p->coef=x; {pre->next=p->next;(p);}

pre=q;q=u;}}if(q!=NULL) }typedefstructnode strunctnode voidfunction(linklist*head,elemtypex while(p!=NULL)&&(p->data!=x printf(“thereisnothisnode::\n”); q->next=p->next; (p); }void while(!Stackempty(s)) } if( }}voidFastTransposeSMatrix(MatrixM,Matrix&T) if(T.tu) for for(t=1;t<=M.tu;++t) forfor(p=1;p<=M.tu;++p) col=M.item[p].j;T.item[q].j=M.}}return}第四个for循环，转置过程；++cpot[col]：语句的功能是当每一列进行一次转置后，其位置向后 1typedefstruct char structBiTNode }voidCreateBiTree(BiTNode char if(ch==‘‘) T=(BiTNodeGwhile}}typedefstruct charstructBiTNode}voidinorder( }} voidfuncgraph(MGraph inti,j,k,w; charv1,v2;printf("Inputvexnum& printf("InputVertices:");forfor(i=0;i<G.vexnum;i++)for printf("InputArcs(v1,v2&}}第二个for循环，初始化邻接矩阵； );线性表的链式结构优于顺序结构。栈和队列也是线性表。如果需要，可对它们中的任一元素进行操作。字符串是数据对象特定的线性表。=P->next;一个无向图的连通分量是其极大的连通子图。邻接表可以表示有向图，也可以表示无向图。遍历。T 时间复杂度为0(n2)；（d）方法所有情况下时间复杂度均为0(nlogn)。a.插入排 b.排 c.快速排 d.堆排不 下列二叉树中，（a） ）适用于查找有序单链表。a. 找d.哈希查找采用（a）方法。 a.log2m b.└log2m┘+1 c.m/2d.┌m/2┐-1 e.┌m/2┐ 56,34,58,26,79,52,64,37,28,84,57下列选择中（c）（b） （d）（a）是初始堆（大堆顶）84，79，64，37，57，52，58，26，28，34，5628，34，57，26，56，52，58，37，79，84，6428，34，37，26，52，56，64，79，58，84，5752，34，64，84，56，26，37，57，58，28，7934，56，26，58，52，64，37，28，79，57，84三．填空题（每题2分共20分）2．已知某二叉树的先序遍历次序为afbcdeg，中序遍历次序为cedbgfa。设有二维数组A5x7,每一元素用相邻的4个字节，器按字节编是（144）；按列时，元素A14的第一个字节的地址是（184）。StatusPreordertraverse(BitreeT,Status(*Visit)(emtypeInitstack(S); Push(S,T);While(!stackempty(S)){While(gettop(S,p)&&p){visit(p->data);push(S,p->lchild;}Pop(S,p); }return四．简答题（每 分 HashH（K）=Kmod130用二次探测再散列处理，给出关键字（23，34，56，24，75，12，49,5