工程硕士复习.doc

2005 工程硕士班复习分三部分：1、 各章重点提示2、 分章复习题3、 综合复习题1各章重点提示(见ppt文件)2分章复习题第一章 引言1数据结构是一门研究非数值计算的程序设计问题中计算机的_(1)_ 以及它们之间的_(2)_和运算的学科。（1） A. 操作对象 B. 计算方法 C. 逻辑存储 D. 数据映象（2） A. 结构 B. 关系 C. 运算 D. 算法2. 算法的五个要素：有穷性、确定性、 (3) 3算法分析的目的是 (1) ，算法分析考虑哪两方面的问题 (2) （1）A) 找出数据结构的合理性 B) 研究算法中输入和输出关系 C) 分析算法的效率 D) 分析算法的易理解性(2) A) 正确性和空间复杂性B) 易读性和健壮性C) 数据复杂性和程序复杂性D) 时间复杂性和空间复杂性4. 在数据结构中，逻辑上数据结构可分为_ A) 动态结构和静态结构 B)线性结构和非线性结构B)紧凑结构和非紧凑结构 D)内部结构和外部结构第二章 线性表1 在一个单链表中，若删除P结点的后继结点，则_ A). p-next = p-next-next; B). p = p-next; p-next = p-next-next;C). p-next = p-next D). p = p-next-next; 2 写出在双向链表指针P之后插入结点S的操作序列。(s-next=p-next;P-next-prior=s;p-next=s;s-prior=p) 3 线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用_存储方式最节省运算时间。A） 单链表 B）仅有头指针的单循环链表C） 双链表 D）仅有尾指针的单循环链表 4.链表中结点的结构为（data,next）。已知指针q所指结点是指针p所指结点的直接前驱，若在q和p之间插入结点s，则应执行下列哪一个操作？a) s-next=p-next; p-next=s;b) q-next=s; s-next=p;c) p-next=s-next;s-next=p;d) p-next=s; s-next=q ; 5.设单链表中结点的结构为（data,next）。已知指针p所指结点不是尾结点，若在指针p所指结点之后插入结点s，则应执行下列哪一个操作？e) s-next=p;p-next=s；f) s-next=p-next; p-next=s；g) s-next=p-next;p=s;h) p-next=s; s-next=p;6.设单循环链表中结点的结构为（data,next），且rear是指向非空的带表头结点的单循环链表的尾结点的指针。若要删除链表的第一个结点，则应执行下列哪一个操作？i) S=rear; rear=rear-next; free(s);j) rear=rear-next; free(rear);k) rear=rear-next-next; free(rear);l) s=rear-next-next; rear-next-next=s-next; free(s); 7 设双向循环链表中结点的结构为（data,pre,next）,且不带头结点。若在指针p所指结点之后插入结点s，则应执行下列哪一个操作？a) p-next=s; s-pre=p; p-next-pre=s; s-next=p-next;b) p-next=s; p-next-pre=s; s-pre=p; s-next=p-next;c) s-pre=p; s-next=p-next; p-next=s; p-next-pre=s; d) s-pre=p; s-next =p-next=; p-next-pre=s; p-next=s; datanext8.已知一无表头结点的单链表 (结点结构为 ) 以 H 为头指针, 每个结点的 data 域存放的是一个自然数, 请你设计一个算法, 能统计出该链表中偶数的个数.status count (LinkList la,&count1) p=la; count1=0 while(p) if odd(!q-data) +count1; p=p-next;return ok; / count 9.有一个无头结点的单链表，结点为(data，next),表头指针为h，通过遍历一遍链表，将链表中所有的链接方向逆转。要求逆转结果链表的表头指针h指向原链表的最后一个结点。 Void Inverse(Linklist &h) If h=null return; P=h-next; pr=null; While p!=null h-next=pr; pr=h;h=p;p=p-next; h-next=pr;/ Inverse 第三章 栈和队列1队列操作的原则是 。A）先进先出 B）后进先出 C）只能进行插入 D）只能进行删除 2.若已知一个栈的入栈序列是1，2，3，.，n，其输出序列为p1,p2,p3,pn,若p1是n，则pi是 A）i B)n-i C)n-i+1 D)不确定3循环队列A0.m-1存放其元素值，用front和rear分别表示队头及队尾，则当前队列中的元素数是 A）(rear - front + m)%m B)rear - front + 1 C) rear - front - 1 D)rear-front 4在操作序列 push(1),push(2),pop,push(5),push(7),pop ,push(6)之后,栈顶元素和栈底元素分别是什么？ push(k)表示整数k入栈，pop表示栈顶元素出栈。5在操作序列Qinsert(1),Qinsert(2),Qdelete,Qinsert(5),Qinsert(7),Qdelete,Qinsert(9).之后，队头元素和队尾元素分别是什么？Qinsert(k)表示整数k入队列,Qdelete表示元素出队列。 6.写出链队列出队、入队算法status L-push(Linkstack &s, Elemtype e) p=(Linkstack)malloc(sizeof(Lnode); p-data=e; p-next=s-next; s-next=p;Return OK; status L-pop(Linkstack &s,Elemtype &e) if(!s-next) Return Error; p=s-next; e=p-data; s-next=p-next; free(p); Return OK; 7 将算术表达式 (中缀) A=B*C+D/E2*(G-H) 利用栈转换为后缀表 达式 ABC*DE2/GH-*+= 的操作步骤是 _ . (用 X 代表扫描该字符并输出的操作, Y 代表扫描该字符并进栈的操作, S 代表从栈中取出一字符并抹掉的操作.) 8循环队列A0.m-1存放其元素值，用front和rear分别表示队头及队尾，则循环队列满的条件是_ A）(Q.rear + 1)%m=Q.front B)Q.rear = Q.front + 1 C) Q.rear+1 = Q.front D)Q.rear = Q.front 第六章 树1 一棵二叉树高度为h,所有结点的度或为0,或为2,则这棵二叉树最少有 个结点A）2h B）2h-1 C）2h+1 D）h+12表达式a*(b+c)-d的后缀表达式是 A）abcd*+- B）abc+*d- C）abc*+d- D）-+*abcd 3若某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总的结点数是 n0=n2+1,n=n0+n1+n24写出一棵满k叉树上的叶子结点数和非叶结点数之间的关系。n0=(k-1)n1+15有n个结点的二叉树，用二叉链表作为存储结构，空指针域有 n+1 61). 写出前序遍历二叉树的递归算法 2). 如图二叉树, 给出按中序, 后序遍历树时的访问次序. 3).画出其先序线索树 E B F A D G I C7 二叉树的先序和中序遍历序列分别是ABCDEFGH，CBEDFAGH，则后序遍历序列是 A）HGFEDACB B）GHEDFCBA C）CEFDBHGA D）HGAFDEBC 8.画出有三个结点的所有二叉树和树 9. 已知一组数列为 10, 5, 6, 17, 20, 15,用这组数构成的哈夫曼树的带权路径长度10（画一棵树） 1. 画出孩子表示法和孩子兄弟表示法存贮示意图。 2. 转换成二叉树。 A 第七章 图 1.设图G用邻接表存储，则拓扑排序的时间复杂度为_ A) O(n) B) O(n+e) C) O(n2) D) O(n*e) 2无向图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) 对该图进行深度优先遍历，得到的顶点序列正确的是 A）a,b,e,c,d,f B)a,c,f,e,b,d C)a,e,b,c,f,d D)a,e,d,f,c,b 3 有向图G如下 ：abegdcf 6 189 8212 410 51).将其看成AOE网，请列出关键路径及关键路径长度（以的形式表示）2). 画出该图的邻接矩阵存储结构.3). 画出该图的邻接表存储结构.4).给出该图从顶点a到顶点g的最短路径（以的形式表示）及最短路径长度 4.已知带权连通图 G(V, E)如下:画出图的最小生成树。 16 21 11 5 19 6 33 14 6 18 简答（20分，每小题5分）1 广度优先算法；2 深度优先算法；3 最小生成树prim算法；4 拓扑排序算法。5. 关键路径算法第九章 查找1. (10分)已知一组数列为 13, 5, 6, 17, 32, 15, 逐个输入数据. 请按算法构造一棵平衡二叉排序树. (请画出插入和平衡过程) 3 二叉排序树或是一棵空树，或是具有下列性质的二叉树：若它的左子树非空，则 (9) ；若它的右子树非空，则 (10) ； 4. 设哈希表长为14，哈希函数是H(key)=key%11,表中已有数据的关键字为 15,38,61,84共四个，现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是 A） 8 B）3 C）5 D）95. 在一棵m阶B树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有 (5) 个关键字；若在某结点中删去一个关键字而导致结点合并，则该结点中原有的关键字的个数是 (6) 。 6有一个有序表为 3,12,24,37,45,53,61,78,90,100 ,当二分查找值为24的数据时 次比较成功。 A）1 B）2 C） 8 D）3 7有一哈希表 HT, 表长 n=16, 哈希函数 H(key)=key mod 13 试用: (1)开放定址, 线性再散列解决冲突. (2)链地址解决冲突方法. 将一 组关键字序列 19, 14, 33, 01, 68, 20, 84, 27 登入 HT 中. (只需画出 空间分配, 不需要写出算法). (10分)回答下列问题：1从数据组织、平均查找时间比较顺序查找、二分查找和分块查找的特点；2简述任意两种哈希查找解决冲突的方法。 算法：1下面的排序算法的思想是：第一趟比较将最小的元素放在r1中， 最大的元素放在rn中；第二趟比较将次小的放在r2中,将次 大的放在rn-1中, . . . .依次下去，直到待排序列为递增序。 （注：代表两个变量的数据交换） void sort(SqList&r,int n) i=1; while （in-i+1 ） min=max=1; for (j=i+1; j=n-i+1 ;+j) if (rj.keyrmax.key) max=j; if (min!=i) rminrj; if (max!=n-i+1) if (max=i) rmin rn-i+1; else rmax rn-i+1; i+; /sort 2下面的算发将一个带头结点的单链表la分解为两个链表la，lb，使得la 表中含有原表中的奇数项的结点，而lb表中含有偶数项的结点，且保持 结点间原有的相对顺序。 void disab(ListedList &la, ListedList &lb) lb=(Linktype)malloc(sizeof(NodeType); r=lb; p=la-next; while(p!=NULL & p-next!=NULL) q=p-next; p-next=q-next ; r-next=q; r=q; p=p-next ; r-next=null; /disab 3 用类C语言的类型定义描述表插入算法的数据结构，并写出表插入算法。 #define MAXSIZE 100; /静态链表容量 Typedef Struct int key; /关键字 infotype RC; /其他数据项 int next; /指针项Slnode; /表结点类型Typedef Struct Slnode rMAXSIZE; /r0为表头结点 int length; /链表当前长度 SlinkListType; /静态链表类型 void SLinksort(SlinkListType &SL) SL.r0.next=1; SL.r1.next=0; for (j=2;jSL.rq.key ) p=q;q= SL.rq.next; SL.rj.next =SL.rp.next; SL.rp.next=j;/for/4 写一算法，把一个用数组表示的线性表转