资源描述
北方工业大学 数据结构 课程 期末复习材料 （ 2016-2017 学年度） 一、 选择（填空）题（第一、二、三章） . 1 二、 选择（填空）题（第四、五、六章） . 3 三、 选择（填空）题（第七、九、十章） . 4 四、 判断题（第一、二、三章） . 5 五、 判断题（第四、五、六章） . 6 六、 判断题（第七、九、十章） . 6 七、 计算简答题（第二章） . 7 八、 计算简答题（第三章） . 9 九、 计算简答题（第四章） . 10 十、 计算简答题（第六章） . 11 十一、 计算简答题（第七章） . 12 十二、 计算简答题（第九章） . 15 十三、 计算简答题（第十章） . 16 答案解析 . 18 北方工业大学计算机学院 二一六年十二月 1 一、 选择（填空）题（第一、二、三章） 1. 一个算法应该是（ ）。 A程序 B问题求解步骤的描述 C要满足五个基本特性 D A和 C 2. 以下数据结构中，（ ）是非线性数据结构 A.树 B.字符串 C.队 D.栈 3. 下面关于线性表的叙述中，错误的是（ ）？ A线性表采用顺序存储，必须占用一片连续的存储单元。 B线性表采用顺序存储，便于进行插入和删除操作。 C线性表采用链接存储 ，不必占用一片连续的存储单元。 D线性表采用链接存储，便于插入和删除操作。 4. 在一个长度为 n的顺序表中，在第 i（ 0i=n+1）个元素之前插入一个元素时，需向后 移动（ ）个元素。 A. n-i B. n-i+1 C. n-i-1 D. i 5. 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则 利用（ ）存储方式最节省时间。 A顺序表 B双链表 C带头结点的双循环链表 D单循环链表 6. 设一个 链表最常用的操作是在末尾插入结点和删除尾结点，则选用 ( )最节省时间。 A. 单链表 B.单循环链表 C. 带尾指针的单循环链表 D.带头结点的双循环链表 7. 链表不具有的特点是（ ） A插入、删除不需要移动元素 B可随机访问任一元素 C不必事先估计存储空间 D所需空间与线性长度成正比 8. 线性表（ a1,a2,an ）以链接方式存储时，访问第 i位置元素的时间复杂性为（ ） A O（ i） B O（ 1） C O（ n） D O（ i-1） 9.若长度为 n 的线性表 采用顺序存储结构，在其第 i 个位置插入一个新元素的算法的时间 复杂度为（ ） (1next=NULL C p=NULL D p= head 13. 带头结点的循环链表 L为空的条件是（ ）。 A. L = NULL B. L-next =NULL C. L-next = L D. L-next = L-next 14. 在单链表指针 为 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; 2 15. 在双向链表指针 p 的结点前插入一个指针 q的结点操作是 ( )。 A. p-Llink=q;q-Rlink=p;p-Llink-Rlink=q;q-Llink=q； B. p-Llink=q;p-Llink-Rlink=q;q-Rlink=p;q-Llink=p-Llink; C. q-Rlink=p;q-Llink=p-Llink;p-Llink-Rlink=q;p-Llink=q; D. q-Llink=p-Llink;q-Rlink=q;p-Llink=q;p-Llink=q; 16.若已知一个栈的入栈序列是 1,2,3,n ，其输出序列为 p1,p2,p3， ， pN,若 pN 是 n， 则 pi是 ( )。 A. i B. n-i C. n-i+1 D. 不确定 17. 一个栈的输入序列为 123n ，若输出序列的第一个元素是 n，输出第 i（ 1=i0) ? x* f(x-1):2); printf(%d ,y); return y; int i ; i =f(f(1); A 2 B. 4 C. 8 D. 无限递归 3 26. 程序段： c = 0 ; for( i=0 ; ixi-) va.elemi+1=va.elemi; va.elemi+1=x; va.length+; return OK; /Insert_SqList 2.15 已知指针 ha 和 hb 分别指向两个单链表的头结点，并且已知两个链表的长度分别为 m 和 n。试写一算法将这两个链表连接在一起 (即令其中一个表的 首元结点连在另一个表的最 后一个结点之后 )，假设指针 hc 指向连接后的链表的头结点，并要求算法以尽可能短的时间 完成连接运算。请分析你的算法的时间复杂度。 void ListConcat(LinkList q = ha ; else p = ha ; q = hb ; ha = hb = hc = p ; while ( p-next ) p=p-next; p-next = q-next ; free ( q ) ; /ListConcat 时间复杂度： O(min(m,n) 2.19 已知线性表中的元素以值递增有序排列，并以单链表作存储结构。试写一高效的算法， 删除表中所有值大于 mink 且小于 maxk 的元素（若表中存在这样的元素），同时释放被删结 点空间，并分析你的算法的时间复杂度（注意， mink 和 maxk 是给定的两个参变量，它们的 值可以和表中的元素相同，也可以不同）。 Status Delete_L(Linklist p=L; while(p-next-datanext) p=p-next; /p 是最后一个不大于 mink 的元素 if(p-next) /如果还有比 mink 更大的元素 q=p-next; while(q-datanext) r=q; q=q-next; /q 是第一个不小于 maxk 的元素 free(r); p-next=q; return OK ; /Delete_L 8 2.21 试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表 (a1,a2, ,an)逆置 为 (an,an-1, ,a1)。 void reverse(SqList for(i=0,j=A.length-1;inext = A ; B-next = B ; C-next = C ; p=A ; q=B ; r=C ; s = L-next ; while(s) if(s-data=a p=s; else if(s-data=0 q=s; else r-next=s;r=s; s=s-next; /while p-next=A;q-next=B;r-next =C; /完成循环链表 return OK; /LinkList_Divide 2.38 设有一个双向循环链表，每个结点中除有 prior， data 和 next 三个域外，还增设了一个 访问频度域 freq。在链表被起用之前，频度域 freq 的值均初始化为零，而每当对链表进行一 次 LOCATE(L,x)的操作后，被访问的结点（即元素值等于 x 的结点）中的频度域 freq 的值便 增 1，同时调整链表中结点之间的次序，使其按访问频度非递增的次序顺序排列，以便始终 保持被频繁访问的结点总是靠近表 头结点。试编写符合上述要求的 LOCATE 操作的算法。 Status Locate(DuLinkList while(p!=L if(p=L) return ERROR; p-freq+;q=p-prior; while(q!=L if (q!=p-prior) p-prior-next=p-next;p-next-prior=p-prior; q-next-prior=p;p-n ext=q-next; q-next=p;p-prior=q; return OK ; /Locate_DuList 9 八、 计算简答题（第三章） 3.1 若按教科书 3.1.1 节中图 3.1(b)所示铁道进行车厢调度（注意：两侧铁道均为单向行驶道），则请 回答： (1) 如果进站的车厢序列为 123，则可能得到的出站车厢序列是什么？ (2) 如果进站的车厢序列为 123456，则能否得到 435612 和 135426 的出站序列，并请说明为 什么不能得到或者如何得到（即写出以 S表示进栈和以 X表示出栈的栈操作序列）。 答： (1) 123 231 321 213 132 (2) 可以得到 135426 的出站序列，但不能得到 435612 的出站序列。因为 4356 出站说明 12 已 经在栈中， 1 不可能先于 2 出栈。 3.3 写出下列程序段的输出结果（栈的元素类型 SElemType 为 char）。 void main() Stack S; char x,y; InitStack(S); x= c ; y= k ; Push(S,x);Push(S, a );Push(S,y); Pop(S,x);Push(S, t );Push(S,x); Pop(S,x);Push(S, s ); while(!StackEmpty(S) Pop(S,y); printf(y); printf(x); 答： stack 3.4 简述以下算法的功能（栈的元素类型 SElemType 为 int）。 (1) status algo1(Stack S) int i,n,A255; n=0; while(!StackEmpty(S) n+; Pop(S,An); for(i=1;inext=Q; /InitCiQueue void EnCiQueue(LinkList p-data=x; p-next=Q-next; /直接把 p 加在 Q 的后面 Q-next=p; Q=p; /修改尾指针 （ 二） Status DeCiQueue(LinkList /队列已空 p=Q-next-next; x=p-data; Q-next-next=p-next; free(p); return OK; /DeCiQueue 3.30 假设将循环队列定义为 :以域变量 rear 和 length 分别指示循环队列中队尾元素的位置和内含元 素的个数。试给出此循环队列的队满条件，并写出相应的入队列和出队列的算法（在出队列的算法 中要返回队头元素）。 （一） #define MAXQSIZE 100 typedef struct QElemType *base ; int rear ; int length ; /替代书中循环队列标准定 义的 int front; SqQueue ; Status InitQueue( SqQueue if(!Q.base) return OVERFLOW ; Q.rear = Qlength = 0 ; return OK ; （二） Status EnQueue(SqQueue Q.baseQ.rear=x; Q.rear=(Q.rear+1)%MAXSIZE; Q.length+; return OK; /EnQueue Status DeQueue(SqQueue head=(Q.rear - Q.length + MAXSIZE)%MAXSIZE; x=Q.basehead; Q.length-; /DeCyQueu 九、 计算简答题（第四章） 求下列串的 next的值 nextval的值 (1) ababaaababaa (2) ababaabab 答案 : ababaaababaa ababaabab next的值 : 011234223456 011234234 nextval的值 : 010104210104 010104101 11 十、 计算简答题（第六章） 6.5 已知一棵度为 k 的树中有 n1 个度为 1 的节点， n2 个度为 2 的节点， ， nk 个度为 k 的节点， 问该树中有多少个叶子节点。 答案： n=n1+2*n2+k*nk+1 n=n0+n1+n2+nk 所以 n0=n2+2n3+(k-1)*nk+1 6.41 编写递归算法，在二叉树中求位于先序序列中第 k 个位置的结点的值。 int count=0; int Get_PreSeq(Bitree T, int k) /函数返回值表示 是否找到 if(!T)return 0; else count+; if(count=k) printf(Value is %cn,T-data); return 1; else if(Get_PreSeq(T-lchild,k)return 1; else return(Get_PreSeq(T-rchild,k); 6.42 编写递归算法，计算二叉树中叶子结点的数目。 int LeafNum(Bitree T) if(!T) return(0); else if(!T-lchild else return(LeafNum(T-lchild)+LeafNum(T-rchild); 6.43 编写递归算法，将二叉树中所有节点的左、右子树相互交换。 void extree(Bitree T-lchild=P; extree(T-lchild); extree(T-rchild); （ 可用先序或后序，但不能用中序 ） 6.15 请对右图所示二叉树进行后序线索化，为每个空指针建立相应的前驱和后继线索。 12 6.19 分别画出和下列树对应的各个二叉树： 答案 : 6.23 画出和下列已知序列对应的树 T： 树的先根次序访问序列为： GFKDAIEBCHJ； 树的 后根次序访问序列为： DIAEKFCJHBG。 十一、 计算简答题（第七章） 7.1 已知左图所示的有向图，请给出该图的 （ 1）每个顶点的入 /出度 （ 2）邻接矩阵 （ 3）邻接表 答案 ： （ 1）每个顶点的入度： ID(1)=3 ID(2)=2 ID(3)=1 ID(4)=1 ID(5)=2 ID(6)=2 每个顶点的出度： OD(1)=0 OD(2)=2 OD(3)=2 OD(4)=3 OD(5)=1 OD(6)=3 （ 2）邻接矩阵 （ 3）邻接表 13 7.3 列出深度优先和广度优先搜索遍历该图所得顶点序列和边的序列。 答案 ： 深度优先遍历： 顶点序列： 1 2 3 4 5 6 边的序列： (1,2), (2,3), (3,4), (4,5), (5,6) 广度优先遍历： 顶点序列： 1 2 3 5 6 4 边的序列： (1,2), (1,3), (1,5), (1,6), (2,4) 7.10 对于如图所示的 AOE 网络，计算各活动弧的 e(ai)和 l(ai)函数值，各事件（顶点）的 ve(vi)和 vl(vi)函 数值；列出各条关键路径。 答案 : 关键路径只有一条： (a,G,H,K,J,E,w) 14 7.11 试利用 Dijkstra 算法求图中从顶点 a 到其他各顶点之间的 最短路径，写出执行算法过程中各步的状态。 答案 :从 顶点 a 到 其他 各点 的 最短 路径 的 求解 过程 如下 : 终点 b c d e f g 终点集 K=1 15 (a,b) 2 (a,c) 12 (a,d) a,c K=2 15 (a,b) 12 (a,d) 10 (a,c,e) 6 (a,c,f) a,c,f K=3 15 (a,b) 11 (a,c,f,d) 10 (a,c,e) 16 (a,c,f,g) a,c,f,e K=4 15 (a,b) 11 (a,c,f,d) 16 (a,c,f,g) a,cf,e,d K=5 15 (a,b) 14 a,c,f,e,d,g a,c,f,e,d,g K=6 15 (a,b) a,c,f,e,d,g,b 练习： 已知图的邻接矩阵为： 1）画出该图邻接表。 2）写出该图按以上邻接矩阵表示时，从 V1 出发的深 度优先遍历序列和广度优先遍历序列。 答案 ： 邻接 表 为： 深度优先遍历序列 ： V1 V2 V3 V4 V5 V6 广度优先遍历序列 ： V1 V2 V5 V3 V4 V6 15 十二、 计算简答题（第九章） 1. 一棵以二叉链表存储的二叉排序树，其存储结构为： typedef struct BiTNode int data; struct BiTNode *lchild ,*rchild; BiTNode , * BiTree; 树中数据域为大于 0 整型数，并且可能存在值相同的结点。设计一个算法，按升序打印出树中 所有结点，但相同值的结点只打印一次。 答案 ： void PrnNode ( BiTree T ， int if( T-data != predata ) printf( “%d “,T-data ) ; predata = T-data ; PrnNode ( T-rchild, predata ) ; void PrnMain(BiTree T) predata = -1; PrnNode(T , predata ) ; 2. 已知一棵二叉排序树，以二叉链表形式存储，其数据域值为大于 0 的整型数，树中可能存在数 据域值相同的结点。设计一个算法，统计树中不同结点的个数。 数的存储结构为： typedef struct BiTNode int data; Struct BiTNode *lchild ,*rchild; BiTNode , * BiTree; 答案 ： void incount(BiTree T, int if(T-data!=predata) c+ ; predata= T-data ; incount(T-rchild , c , predata ) ; int count(BiTree T) predata = 0; count=0 ; incount(T , count , predata ) ; return(count); 9.32 已知一棵二叉排序树上所有关键字中的最小值为 -max，最大值为 max，又 -maxx=x) /找到了小于 x 的最大元素 printf(a=%dn,last); if(last=x) last=T-data;MaxLT_MinGT(T-lchild,x); if(lastdatax) /找到了大于 x 的最小元素 printf(“b=%dn”,T-data); if(T-datadata; MaxLT_MinGT(T-rchild,x); /MaxLT_MinGT 16 9.33 编写递归算法，从大到小输出给定二叉排序树中所有关键字不小于 x 的数据元素。 答案 ： void Print_NLT(BiTree T,int x)/从大到小输出二叉排序树 T 中所有不小于 x 的元素 if(T) Print_NLT(T-rchild,x); if(T-data=x) printf(“%dn”,T-data); Print_NLT(T-lchild,x); /先右后左的中序遍历 /Print_NLT 十三、 计算简答题（第十章） 设待排序的表有 8 个记录 ,其关键字分别为 3， 87， 12， 61， 70， 97， 26， 45 。说明分别采用 直接插入排序、希尔排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序、 基数排序 方法 进行排序的过程。 1. 设待排序的表有 8 个记录 ,其关键字分别为 3， 87， 12， 61， 70， 97， 26， 45 。说明采用直 接插入排序方法进行排序的过程。 （ 1） （ 3） 87 12 61 70 97 26 45 （ 2） （ 3 87） 12 61 70 97 26 45 （ 3） （ 3 12 87） 61 70 97 26 45 （ 4） （ 3 12 61 87） 70 97 26 45 （ 5） （ 3 12 61 70 87） 97 26 45 （ 6） （ 3 12 61 70 87 97） 26 45 （ 7） （ 3 12 26 61 70 87 97） 45 （ 8） （ 3 12 26 45 61 70 87 97） 2. 设待排序的表有 8 个记录 ,其关键字分别为 3， 87， 12， 61， 70， 97， 26， 45 。说明采用 希 尔排序 方法进行排序的过程。 （ 1） D=5 3 26 12 61 70 97 87 45 （ 2） D=3 3 26 12 61 45 97 87 70 （ 3） D=1 3 12 26 45 61 70 87 97 3. 设待排序的表有 8 个记录 ,其关键字分别为 3， 87， 12， 61， 70， 97， 26， 45 。说明采用 冒 泡排序 方法 进行排序的过程。 （ 1） 3 12 61 70 87 26 45 (97) （ 2） 3 12 61 70 26 45 (87 97) （ 3） 3 12 61 26 45 (70 87 97) （ 4） 3 12 26 45 (61 70 87 97) （ 5） (3 12 26 45 61 70 87 97) 4. 设待排序的表有 8 个记录 ,其关键字分别为 3， 87， 12， 61， 70， 97， 26， 45 。说明采用 快 速排序 方法进行排序的过程。 17 分别完成第二趟排序： 3 ( 45 12 61 70 26) 87 (97) 分别完成第二趟排序： 3 ( 45 12 61 70 26) 87 (97) 分别完成第三趟排序： 3 ( 26 12） 45 （ 70 61) 87 97 分别完成第四趟排序： 3 12 26 45 61 70 87 97 5. 设待排序的表有 8 个记录 ,其关键字分别为 3， 87， 12， 61， 70， 97， 26， 45 。说明采用 直 接选择排序 方法进行排 序的过程。 （ 1） （ 3） 87 12 61 70 97 26 45 （ 2） （ 3 12） 87 61 70 97 26 45 （ 3） （ 3 12 26） 61 70 97 87 45 （ 4） （ 3 12 26 45） 70 97 87 61 （ 5） （ 3 12 26 45 61） 97 87 70 （ 6） （ 3 12 26 45 61 70） 87 97 （ 7） （ 3 12 26 45 61 70 87） 97 （ 8） （ 3 12 26 45 61 70 87 97） 6. 设待排序的表有 8 个记录 ,其关键字分别为 3， 87， 12， 61， 70， 97， 26， 45 。说明采用 堆 排序 方法进行排序的过程。 建大堆 : 97 87 26 61 70 12 3 45 （ 1） 87 70 26 61 45 12 3（ 97） （ 2） 70 61 26 3 45 12 （ 87 97） （ 3） 61 45 26 3 12（ 70 87 97） （ 4） 45 12 26 3（ 61 70 87 97） （ 5） 26 12 3（ 45 61 70 87 97） （ 6） 12 3（ 26 45 61 70 87 97） （ 7） 3（ 12 26 45 61 70 87 97） （ 8） （ 3 12 26 45 61 70 87 97） 7. 设待排序的表有 8 个记录 ,其关键字分别为 3， 87， 12， 61， 70， 97， 26， 45 。说明采用 归 并排序 方法进行排序的过程。 采用二路归并 （ 1） (3 87) (12 61) (70 97) (26 45) （ 2） (3 12 61 87) (26 45 70 97) （ 3） （ 3 12 26 45 61 70 87 97） 8. 设待排序的表有 8 个记录 ,其关键字分别为 3， 87， 12， 61， 70， 97， 26， 45 。说明采用 基 数排序 方法进行排序的过程。 （ 1）按个位排序 70 61 12 3 45 26 87 97 （ 2）按十位排序 3 12 26 45 61 70 87 97 18 答案 解析 一、选择（填空）题（第一、二、三章）答案： 1.B 2.A 3.B 4.B 5.A 6.D 7.B 8.C 9.C 10.A 11.C 12.A 13.C 14.B 15.C 16.D 17.B 18.C 19.D 20.C 21.C 22.D 23.D 24.B 25.B 26.C 27.D 二 、选择（填空）题（ 第四、五、六章 ）答案： 1.B 2.C 3.A 4.C 5.B 6.A 7.B 8.B 9.A 10.B 11.C 12.C 13.C 14.D 15.D 16.C 17.C 18.C 19.B 20.C 21.D 9. (5*6+5)*5+1000=1175 10. 8*10+4=(y-1)*9+x = y=10, x=3 17.( n=2K-1) 三、选择（填空）题（ 第七、九、十章 ）答案： 1C 2A 3B 4D 4C 5B 6A 7D 8C 9B 10 11 12 13. 至少有 m/2-1=(m-1)/2个关键字 四、判断题（第一、二、三章） 1.X 2. 3.X 4.X 5. 6.X 7.X 8. 9. 10.X 11.X 12. 13. 14.X 15.X 16.X 17.X 18. 19. 20. 21. 22.X 23. 24.X 25. 26.X 27.X 五、判断题（第四、五、六章） 1. 2. 3. 4.X 5. X 6. 7. 8. X 9. 10.X 11. 12. X 13. X 六、判断题（第七、九、十章） 1X 2 3X 4X 5X 6 7 8 9X 10X 11 12X 13 14X 15 16 17X 18 19X 20X
展开阅读全文