<4D F736F F D20D6A3D6DDB4F3D1A7CAFDBEDDBDE1B9B9B1CABCC72E646F63>

Size: px

Start display at page:

Download "<4D F736F F D20D6A3D6DDB4F3D1A7CAFDBEDDBDE1B9B9B1CABCC72E646F63>"

醒忧强
5 years ago
Views:

1 郑州大学硕士研究生入学考试计算机应用与技术专业基础课数据结构课程辅导笔记 (2005 年版 )

2 1. 设 A=(a 1 a n ), 问利用顺序存储结构 : 1 在等概率的前提下, 插入一个元素平均移动多少个元素? n( n 1) n ( n 1) 1 0 解 : = 2 n = n 1 n 1 2 n i 2 若元素插入在 a i 与 a i 1 (0 i n-1) 的概率为, 则平均插入一个元素所需 n( n 1) 2 移动的元素个数为多少? n n 1 1 n ( n 1) 1 n( n 1) / 2 n( n 1) / 2 n( n 1) / 2 解 : n 1 2 ( n i) 2n 1 n( n 1) / 2 3 i 注 :1 2 3 n n( n 1)(2n 1) / 6 2. A,B 为两个带头结点的单链表, 且递增有序, 试编写算法将 A,B 归并为 C 链表, 要求利用原来的结点空间存放 C ( 见课本 P 31 ) 解 : void MergeList_L(linklist &La, linklist &Lb, linklist &Lc) { Pa=La->next; Pb=Lb->next; Lc=Pc=La; while(pa&&pb) if (Pa->data<=Pb->data) { Pc->next=Pa; Pc=Pa; Pa=Pa->next; else {Pc->next=Pb; Pc=Pb; Pb=Pb->next; Pc->nex = Pa? Pa : Pb; free(lb); 3. 已知以 ha,hb 为头指针的单链表, 编写算法判断 A 是否在 B 内, 是则返回 0, 否则返回 1 解 :int inclusion (linklist ha, linklist hb) { Pa=ha->next; Pb=hb->next; if (!Pa) return 0; while(pb!=null&&pa->data>=pb->data) if (Pa->data= =Pb->data) return (inclusion(pa->next, Pb->next)); Else Pb=Pb->next; return 1; 第 2

3 4.(2005 考试题 ) 已知顺序表中有 m 个记录, 表中记录无序, 试为它建立一个按关键字排序的索引, 并在索引中存放顺序表中的序号解 : 定义结构 :Typedef struct { keytype key; // 定义关键字 int sn; // 定义序号 indextype; void indexing (indextype idx[m],datatype data[m]) { for (i=1; i<=m; i++) { j=i-1; while (j>0&&idx[j].key>data[i].key) { idx[j+1]=idx[j]; j--; j++; idx[j].key=data[i].key; idx[j].sn=i; 5. 试设计一个算法实现单链表 h 就地逆置 h typedef struct Lnode{ ElemType data; struct Lnode *next; Lnode; Lnode *reverselist (Lnode *h) { Lnode *p, *q =Null; while (h) { p=h->next; h->next=q; q=h; h=p; return q ; 6. 试编写算法将单循环链表 La 改为双循环链表 typedef struct Lnode { Lnode *pre; Lnode *next; Elemtype data; LinkList; void SingleToDoubleList(LinkList La) { q = La->next; p=la; 第 3

4 while(p!=la) { q->pre=p; q=q->next; p=p->next; p->pre=q; 7. 试用两个堆栈 s1,s2 模拟队列的出队, 入队操作 void in(stack s1,stack s2, elemtype e) { void out(stack s1,stack s2, elemtype e){ while (s 2.top!=0){ while (s 1.top!=0){ a=pop(s 2 ); a=pop(s 1 ); push(s 1,a); push(s 2,a); push(s 1,e); a=pop(s 2 ); return a; 8. 1 m 数组 : 底栈 s1 栈 s2 底 typedef struct { int bottom; int top; int maxsize; s1,s2; 初始化 s1.bottom=1; s2.bottom=m; s1.top=1; s2.top=m; s1.maxsize=m; s2.maxsize=m; 9. 试编写算法实现十进制到八进制的转换解 :void conversion() { initstack(s); scanf( %d,n); while (N) { push(s,n%8); N=N/8; while (!StackEmpty(s)) { Pop(s,e); printf( %d,e); 第 4

5 10. 试编写算法实现数组 A[1 n] 中的元素右移 K 位, 仅用一个大小的附加空间, 并保证算法的时间复杂度位 O(n) 解 :void move (elemtype a[n], int k) { elemtype t; int i,j; for (i=1;i<=k; i++) { t=a[n]; for (j=n-1;j>=1;j--) a[j+1]=a[j]; a[1]=t; 11. 循环队列大小为 6,rear=0, front=3. 当删除一个元素时, 在加入两个元素后,rear=( ), front=( ), 此时的队列长度为 ( ) 答案 :2 4 (2-4+6)%6=4 12. 用高级语言编写串匹配算法, 并估计算法的效率解 :typedef unsigned char Sstring[maxstrlen+1] // 定长顺序存储表示 int index (Sstring S, Sstring T, int pos) { //S 为主串,T 为子串 i=pos; j=1; while (i<=s[0]&&j<=t[0]){ //S[0] 为 S 的串长,T[0] 为 T 的串长 if(s[i]= =T[j]) { i++; j++; else { j=i-j+2; j=1; if(j>t[0]) return (i-t[0]); else return 0; O(S[0]*T[0]) 13. 设 S 为一个长度为 n 的字符串, 其中的字符各不相同, 则 S 中互异的非平凡子串的个数为 (2+3+ +n) 14. 设 S= (XYZ)+*,T= (X+Z)*Y, 利用联结号, 求子串 (substr(s,i,j)) 以及置换 (replace(s1,i,j,s2)), 将 S 转换为 T 解 :S1=substr(S,1,5) S2=substr(S,6,1) S3=replace(S1,3,1,S2) S4=substr(S,7,1) S5=substr(S,3,1) T=S3 S4 S5 第 5

6 15. 设目标模式为 t= abcaabbabcabaacbacba, 模式 p= abcabaa 计算模式 p 的 nextval 的函数值解 : a b c a b a a next[j] nextval[j] 设数组 B[1 10, -2 6, 2 8] 以行优先顺序存储, 首地址是 100, 每个元素占 3 个单元, 求 B[5, 0, 7] 的地址解 :100+(4*9*7+2*7+5)*3 17. 设整型数组 b[n][m], 已知 b 中的数组元素在每一维方向上都从小到大次序排列且整型变量 X 的值在 b 中出现试设计算法找出满足 b[i][j]=x 的位置 (i, j) 的值, 要求比较次数不多于 m+1 次 ( 不能使用折半查找 ) 解 :int Search(Array b[n][m]) { i=0; j=m-1; while (b[i][j]!= X &&i<=n-1 && j>=0) if (b[i][j]<x) i++; else j--; 18 特殊矩阵按行存储到数组, 矩阵元素在数组的下标位置 k 转换公式如下 : (0 i,j n-1) 对称矩阵 (nⅩn): ( i 1) * j / 2 j, i j k= ( j 1) * j / 2 i, i j. 上三角 :k=n+(n-1) + +(n-i)+(j-i+1) 三对角阵 : 0, i>j; k=2+3*(i-1)+l, 其中 L= 1, i=j; 2, i<j. 双对角阵 : 0, i=j; 1n 为偶数时 :k=2*i +L, 其中 L= 1, i+j=n-1; 上半部 1, i=j; 0, i+j=n-1; 下半部 2n 为奇数时 : 0, i=j; 上半部 k=2*i+ 1, i+j=n-1.(i<j) 0, i+j=n-1.(i>j) 下半部 k==2*i-1+ 1, i=j; 准对角阵 : i+j-1, i 为奇数 ; 第 6

7 K= i+j, i 为偶数. 19. 表头表尾长度深度 ((a),a) (a) (a) 2 2 ((a)) (a) ( ) 1 2 ((a,b),c,d) (a,b) (c,d) 3 2 (a,b,c,d) a (b,c,d) 4 1 (((a))) ((a)) ( ) 1 3 A= (a, (a, (a, )) ) ) a A 表结点 : 原字结点 : Tag=1 表头表尾例 :((a,b),c,d) Tag=0 值 c 0 d 0 a 1 0 b 21. 已知 head(a)=tail(a), 则 A 为 (( )) 22 求广义表的长度, 可以使用 tail(),head() 函数解 :1 递归算法 int length (Glist p) { if (p==null) return 0; else return (length(tail(p))+1); 2 非递归算法 int length(gnode *p) { 第 7

8 int n=0; if(p!=null && p->tag==1) while(p!=null) { p=p->link; n++; return n; 23. 求广义表 Ls=(d 1, d 2,, d n ) 的深度解 : 1, Ls 为空 ; depth(ls)= 0, Ls 为原子 ; 1+max{d i, 其它 (1 i n) gnode 的结构 :: tag data/sublist link int depth(gnode *p){ int h, maxdh; gnode *q; if (p->tag = = 0 ) return 0; else if (p->tag = =1 && p->sublist = = Null) return 1; else { maxdh=0; while (p!=null){ q=p->sublist; h=depth(q); if(h>maxdh) maxdh=h; p=p->link; return (maxdh+1); 24. 编写算法计算广义表的原子结点个数解 :int counter(gnode *p) { int m, n; if(p= =Null) return 0; else { if(p->tag= =0) m=1; else m=counter (p->sublist); if(p->link!=null) n=counter(p->link); else n=0; 第 8

9 return (m+n); 25. 举例说明恰有一个顶点入度为 0, 其它入度为 1 的有向图不是一棵有向树. 解 : 26. 若 N 个顶点,K 条边的无向图是一个森林 (N>K), 该森林必有多少棵树? 解 : 设该森林有 m 棵树, 每棵树结点数为 V i,1 i m. ( 注 : 树的结点数 = 边数 +1) V 1 + V V m = N (V 1-1)+ (V 2-1)+ + (V m 1 ) = K m i1 V m K i m N K 27. 已知一棵树的先根和后根遍历分别是 SACEFBDGHIJK 和 CFEABHGIKJDS. 试画出这棵树 ( 注 : 由树的先根和后根遍历可以确定一棵树 ) S A B D C E G I J F H K 28. 深度为 k ( 根的层次为 1) 的完全二叉树, 至少有个结点, 至多有个结点 k 和结点数 n 的关系是答案 :2 k 1 k 2 1 k=log 2 n 高为 h 的二叉树只有度为 0 和 2 的结点, 则此类二叉树的结点数至少有个结点, 至多有个结点 h 答案 :2(h-1) 一棵 124 个叶结点的完全二叉树最少有个结点, 最多有个结点答案 : 第 9

10 31. 线索树的遍历需要栈 ( 没有右子树的二叉树可不是用栈 ) 答案 : 后序 32. 前序和中序遍历结果一样的树是 : ; 前序和后序遍历结果一样的树是 : 答案 : 只有根结点的树或只有右子树的二叉树只有根结点的二叉树 33. 前序和后序遍历 ( 能 / 不能 ) 唯一确定一棵二叉树答案 : 不能 34. ( 前序 / 中序 / 后序 ) 遍历二叉树可使二叉树的结点序号按从小到大排列答案 : 中序 35 含有 n 个结点互不相似的二叉树有棵,n 个结点有不同形态树的数目 1 1 答案 : C n n1 2 n C2( n1) n 1 n 36. 遍历二叉树并填空 A B C D F E G K E H J 先序遍历 : B F I C E H G 中序遍历 : D K F I A E J C 后序遍历 : K F B H J G A 答案 :A DKJ BHG DIEC 37. 试编写算法实现按层次遍历二叉树 1 用队列 typedef struct node { elemtype data; node L, r; ; travers (btree b) { InitQueue(Q); 第 10

11 p=b; EnQueue(Q,p); While(!QueueEmpty(Q)) { DeQueue(Q,q); printf( %d,q->data); if(q->l) EnQueue(Q,q->L); if(q->r) EnQueue(Q,q->r); 2 用数组模拟队列 #define maxlen 100 typedef struct btree{ elemtype data; struct btree left, right; btree; struct node { btree rec[maxlen]; int r, f; q; void travers( btree b) { q.r=q.f=0; // 队列为空 if(b!=null) printf( %d,b->data); q.vec[q.r]=b; // 结点进队 q.r=q.r+1; while(q.f<q.r) { b=q.vec[q.f]; q.f=q.f+1; if(b->left!=null) { // 输出左孩子, 并入对 printf( %d,b->left->data); q.vec[q.r]=b->left; q.r=q.r+1; if(b->right!=null){ // 输出右孩子, 并入对 printf( %d,b->right->data); q.vec[q.r]=b->right; q.r=q.r+1; 38. 已知二叉树的先序中序分别存放于一维数组中, 编写建立二叉树的算法解 :btree bintree(int i, int j, int u, int v, int pre[], int ind[] ) { //i,j 和 u,v 分别是在先序和中序遍历的起始点和终点 int k, L; 第 11

12 btree head, s; head=null; if(j i) { head=(btree )malloc(sizeof(btree)); head->data=pre[i]; k=u; while(ind[k]!=pre[i]) k++; L=i+k-u; if(k= =u) // 无左子树 head->left=null; else { s=bintree(i+1,l,u,k-1); head->left=s; if(k= =v) // 无右子树 head->right=null; else { s=bintree(l+1,j,k+1,v) head->right=s; return head; 39. 一个深度为 h 的满二叉树有如下性质 : 第 h 层上的结点都是叶子结点, 其余结点有 m 棵非空子树问 : 1 第 k 层最多有多少结点?(k h) 2 整棵树有多少结点? 3 按层从上至下, 从左至右编号 ( 从 1 开始 ) 编号为 I 的结点的第 j 个孩子 ( 若存在 ) 编号是多少? 解 :m k 1 1+m 2 h1 m m (i-1)*m+2+j-1( 其父结点编号为 i m 2 m ) 图示 ( 圈内为结点的编号 ): m+1 m+2 m+3 2m+1 2m+2 3m+1 m 2 +2 m 2 +m 已知一棵度为 m 的树中有 N i 个度为 i 的结点,1 i m, 求该树中共有多少个叶子结点? 解 : 由于总结点数 = 总边数 +1, 有 : N 0 N N m 1 N 1 + 2*N 2 +m*n m 第 12

13 N m 0 1 ( i 1) * N i i2 41. 中序线索化下列二叉树 : A NIL B D C X E NIL Y 42. 试编写前序遍历二叉树非递归算法解 :void preorder(bitree *t) { int i=0; BiTree *p,*s[m]; p=t; do { while (p){ printf( %d,p->data); if(p->rchild) s[i++]=p->rchild; p=p->lchild; if (i>0) p=s[- -i]; while (p i>0) 43. 试编写中序遍历二叉树的非递归算法解 : void inorder(bitree *t) { int i=0; BiTree *p,*s[m]; p=t; do { while (p){ s[i++]=p; p=p->lchild; if(i>0) { 第 13

14 p=s[- -i]; printf( %d,p->data); p= p->rchild; while(p i>0) h 44. 已知深度为 h 的二叉树存放在数组 BT[1:2 1] 中, 试写一算法求出二叉树中的叶子结点的个数解 :( 算法思想如下 ) count=0; for(i=1; i<=2 h 1; i++) { if (BT[i]!=0) { if (i*2>2 h 1) count++; else if(bt[i*2+1]= =0&&BT[i*2]= =0)count++; return count; 45. 填空 : 已知具有 n 个结点的完全二叉树已经顺序存储在 A[1 n] 中, 下面的算法是将 A 中的顺序结构转化为二叉链表 : elemtype A[n]; struct nodetype{ datatype data; nodetype *l, *r; ; btree (datatype A[n], struct nodetype *p) { ; createtree(p, j); createtree (struct nodetype *t, int i) { malloc(sizeof(nodetype)); t->data=a[i]; if (i*2 n) createtree(, ) else t->l=null; if (i*2+1 n) createtree(, ) else t->r=null; 答案 :j=1 t=(struct *) t->l 2*i t->r 2*i 编写算法求指定结点在二叉树中的层数. 解 :void level(btree *b,btree *p, int h,int lh) { //b 为二叉树,p 为指定结点,h 为结点层数,lh 为当前层第 14

15 h=-1; if (b= =Null) h=0; else if (p= =b) h=lh; else { level(b->left, p, h, lh+1); if (h= =-1) level (b->right, p, h, lh+1); 47. 试编写算法将二叉树的左右孩子对调. 解 :btree *swap (btree *b) { btree *t1, *t2, *t; if (b= =Null) t=null; else { t=(btree *)malloc(sizeof(btree)); t->data=b->data; t1=swap(b->left); t2=swap(b->right); t->left=t2; t->right=t1; return t; 48. 总结 : 求二叉树 b 的总结点 : 0, b 不为空 ; f(b)= 1, 若 b->left=null 且 b->right=null; f(b->left)+f(b->right)+1, 其它. 求二叉树 b 的叶子数 : 0, b=null; f(b)= 1, 若 b->left=null 且 b->right=null; f(b->left)+f(b->right), 其它. 求二叉树 b 的有单孩子的结点数 : 0, b=null; f(b)= 1, 若 b->left=null 且 b->right=null; 或 b->left Null 且 b->right Null; f(b->left)+f(b->right), 其它. 求二叉树 b 的有双孩子的结点数 : 0, b=null; f(b)= 1, 若 b-> leftnull 且 b->right Null; f(b->left)+f(b->right), 其它. 第 15

16 49. 将森林转化为二叉树 : 试编写算法, 在中序线索树中找某一结点的后继解 : btree *succ (tbtree *p) { tbtree *q; if (p->rtag= =1) return p->right; else { q=p->right; while (q->ltag= =0) q=q->left; return q; 填空 : 1 图中所有顶点的度数之和等于所有边数的倍 2 有向图中, 所有顶点的入度之和等于所有顶点出度之和的倍 3 一个 n 个顶点的无向图最多有条边,n 个顶点的有向图最多有条弧 4 4 个顶点的无向完全图有条边 4 个顶点的无向图至少有条边, 才能确保连通第 16

17 5 n 个顶点的无向图要连通, 至少需要条边 6 n 个顶点,e 条边的无向图, 若采用邻接表, 则表头大小为个, 邻接表中的结点个 7 采用邻接表存储, 图的深度优先遍历类似于二叉树的遍历, 图的广度优先遍历类似于二叉树的遍历 8 判断一个有向图是否存在回路可用 9 无向图的邻接矩阵是矩阵 10 从邻接矩阵中求第 I 个结点的入度的方法是, 删除第 i 个结点出发的边的方法是 11 给定 n 个元素可以构造出的逻辑结构 : 12 Kruskal 算法时间复杂度, 它对图较合适 13 N 个顶点的强连通图最多有条边, 最少有条边 14 表示一个 1000 个顶点,1000 条边的有向图的邻接矩阵有个元素, 满足条件的矩阵为稀疏矩阵 15 一个非连通的无向图共 28 条边, 该图中至少有个顶点 ( 注 : 完全图顶点数最少 ) 16 用 DFS 遍历一个无环有向图, 并在 DFS 算法退栈返回时, 打印出相应顶点, 则输出的顶点序列是 17 n 个顶点的无向图, 边数大于 n-1, 则该图必是连通图吗? 18 若一个有向图的邻接矩阵中, 对角线以下的元素均为 0, 则该图的拓扑有序序列一定存在, 对吗? 19 遍历图的实质是的过程 20 广度优先搜索遍历的时间复杂度为 :, 深度优先搜索遍历的时间复杂度为 :, 两者不同之处是, 图的遍历算法是求解的基础有向图中的结点的前驱后继关系的特征是关系答案 : n(n-1)/2 n(n-1) n-1 6 n 2e 7 先序层次 8 拓扑排序深度优先遍历 9 对称 10 求出第 i 列为 1 的个数使第 i 行全为 0 11 线性表树图和集合 12 O(eloge) 稀疏 13 n(n-1) n e<nlogn 逆拓扑有序序列第 17

18 17 不一定, 比如 : 18 一定存在 19 根据边 / 弧找邻接点的过程 20 O(n+e) O(n+e) 对顶点访问的顺序不同连通性问题拓扑排序求关键路径和最短路经偏序 52. 找出以顶点 1 为根的深度优先生成树的关节点解 : 关节点为 1,2,3,7, 使用邻接表存储带权有向图试写出 (1) 图的邻接表定义 ;(2) 定义算法使用的全局数组 ;(3) 写出拓扑排序算法 (2005 年考试题填空 ) 解 :(1) #define MAX_VERTEX_NUM 20 typedef struct ArcNode{ int adjvex; struct ArcNode * nextarc; InfoType *info; ArcNode; typedef struct VNode{ VertexType data; ArcNode *firstarc; VNode, AdjList[MAX_VERTEX_NUM]; typedef struct { AdjList Vertices; Int vexnum,arcnum; int kind; ALGraph; (2) 全局数组为 indegree[ ]; (3) 拓扑排序算法 : Status TopologicalSort(ALGraph G) { FindIndegree(G, indegree); InitStack(S): For( i=0; i<g.vexnum; ++i) if(!indegree[i]) Push(S, i): 第 18

19 count=0; While (!StackEmpty(S)) { Pop(S, i ); printf( i, G.vertices[i].data); ++count; for( p=g.vertices[i].firstarc;p;p=p->nextarc) { k=p->adjvex; if(!(--indegree[k])) Push(S,k); if(count<g.vexnum) return ERROR; else return OK: 54. 已知 AOV 图,V 1 ~V 7 是 7 个事件,a 1 ~a 10 是活动, 求关键路径 V 2 a 4 =4 V 5 a 1 =3 a 5 =2 a 8 =1 a9 3 V 1 a 2 =6 V 4 V 7 a 3 =2 a 6 =1 a10 4 V 3 a 3 7 V 6 事件 V 1 V 2 V 3 V 4 V 5 V 6 V 7 最早发生时间最晚发生时间活动 a 1 a 2 a 3 a 4 a 5 a 6 a 7 a 8 a 9 a 10 最早开始时间最晚发生时间松弛时间关键路径为 :a 1, a 2, a 4, a 8, a 深度遍历下面的无向图, 并判断所给出的深度优先遍历和广度优先遍历是否正确第 19

20 5 6 判断下列给出的深度优先遍历是否正确 : 判断下列给出的深度优先遍历是否正确 : ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) 答案 : 错错对错错错对错 56. 以邻接矩阵作为图的存储结构, 试编写算法判断有向图中是否存在回路, 若存在, 找出一条回路 ( 不存在自己到自己的弧 ) 解 :int matrix[1 max][1 max]; int visited[1 max]; 取 False=0,True=1 int Vex[1 max]; int p,found; find circle( ) { for(v=1;v<=max;v++) visited[v]=false; p=o; found=false; for(v=1;v<=max;v++) DFS(v); DFS(int v) { Display( ){ if(found) return 1; flag=false; p=p+1; v=vex[p]; Vex[p]=v; for(i=1;i<=p;i++) { if(visited[v]) { if(vex[i]= =v) Found=True; flag=true; Display( ); if(flag) printf(vex[i]); else { visited[v]=true; for(i=1;i<=max;i++) if(matrix[v,i]>0) DFS(i); p=p-1; visited[v]=false; 57. 会求从有向图某一结点到其余结点的最短路径 ( 用表表示求解过程 ), 不要求算法 58. 填空 : 1 顺序查找适合的存储结构为和 ; 折半查找要求线性表 : 2 等概率时采用顺序查找长度为 n 的线性表, 当查找成功时, 平均查找长度为 ; 若同时考虑查找不成功时的情况在内, 每个元素的平均查找长度为, 折半查找的平均查找长度为第 20

21 3 折半查找和二叉排序树的时间性能 ( 相同 / 不相同 ) 4 有序表 (1,3,9,12,32,41,45,62,75,77,82,95,100), 用折半查找 82 结点时, 经过次比较后查找成功 5 哈希表长 m=14,h(key)=key%11, 表中已有 4 个结点,addr(15)=4,addr(38)=5, addr(61)=6,addr(84)=7, 其余为空如用二次探测再散列处理冲突, 关键字 49 结点的地址是 6 长度为 12 的有序表, 按折半查找, 在各元素等概率的情况下, 查找成功的平均次数为 7 采用分块查找时, 若线性表中共有 625 个元素, 查找每个元素的概率相同假设采用顺序查找确定结点所在的块时, 每块应分为个结点最佳 8 最优查找二叉树和最优二叉树的路径总长为 9 m 路平衡 B 树是一棵树答案 : 1 顺序表链表 ; 按关键字有序且数组顺序存储 2 (n+1)/2 3(n+1)/4 O(log 2 n) 3 不相同 /12 解 : 查找树 : * 2 4*3 5* 4 37 ASL= n ASL bs ( s) 1 当 s= 2 s n, 即每块有 n 个结点时最佳 n 8 w i * h i, 在最优二叉树中,n 表示叶子的结点数 ; 在最优查找二叉树中,n 表 i1 示总结点数目 9 平衡二叉树 ( 二叉平衡树一定是二叉排序树 ) 59. 第 21

22 m 阶 B 树 m 阶 B 树每个结点中最多关键字个数 m m-1 每个结点中最少关键字个数 m 2 m 填空 1 一棵深度为 k 的平衡二叉树, 其每个非终端结点的平衡因子均为 0, 则该树共有个结点 2 在任一棵非空二叉排序树中, 删掉某结点, 又将其插入所得的二叉排序树与删掉前一定 ( 相同 / 不相同 ) 3 装填因子是散列表的一个重要参数, 它反映了 4 k 个互为同义的关键字, 若用线性探测法把这 k 个关键字存入散列表中, 至少要进行次探测 5 分块检测中, 对 256 个元素的线性表分成块最好, 每块最佳长度为, 若每块的长度为 8, 平均检索长度为 6 选择 hash 函数的标准是 ; 处理冲突技术的共同标准是个记录中, 找出两个最小的, 采用什么方法所需关键字比较次数最少? 8 散列查找区别与其他查找方法的根本点是 9 顺序查找有序无序的顺序表的平均查找长度 ( 相同 / 不同 ) 答案 : k 不一定 3 散列表装满的程度 k 4 i i1 1 n ASL bs ( s) 1 2 s 6 地址均匀减少冲突 ; 快速找到空地址 7 冒泡排序 8 散列查找是按地址查找, 其他的查找方法是比较关键字 9 相同 61. 有序表 (a 1... a 12 ), a i a j (i<j), 对该有序表进行折半查找, 在等概率的情况下, 求查找不成功的平均查找次数解 : 10* 4 3*3 49, 查找图如下 : a 6 第 22

23 a 3 a 9 a 1 a 4 a 7 a a 2 a 5 a 8 a 10 a 代表查找不成功时已经比较的次数 62. 试编写算法, 利用折半查找在一个有序表中插入一个元素 x, 并且保持有序解 : bin_insert ( Sqlist r, int x, int n) { int low=1, high=n, mid, inplace, i, found=0; while ( low<=high &&!found) { mid = ( low + high ) /2; if (x < r[mid].key) high = mid-1; else if (x > r[mid].key) low = mid+1; else { i = mid; found = 1; if (found) inplace = mid; else inplace = low; for( i=n; i >= inplace; i--) r[i+1].key=r[i].key; r[inplace].key=x; , 画出二叉排序树并故给出下列操作的结果 (1) 插入 9;(2) 删掉 17;(3) 删掉 13 解 : 二叉排序树 : (1) 插入 9 后 : 17 第 23

24 (2) 删除 17 后 : (3) 删除 13 后 : 试编写算法实现打印大于等于 x 的结点的所有数据解 : disp(t, x) {// 中序遍历二叉树, 同时输出大于等于 x 的结点 if(t!=null) { disp(t->lchild,x); if(t->data>=x) printf(t->data); disp(t->rchild, x); 65. 已知 AVL 树 : (1) 插入 6: 左 ( 逆时针 ) 转右 ( 顺时针 ) 转 (2) 在插入 6 后, 再插入 10 8 第 24

25 右 ( 顺时针 ) 转 8 左 ( 逆时针 ) 转已知有 12 个结点的 AVL 树, 求其最大深度解 : h n = h n 1 + h n 由可得最大深度为 5 h 0 0, h 数列空间 H[1 m], 每个 H[i] 存放一个记录, 初值为 NULL, 选取 H(R.key) 为散列函数解决冲突, 使用线性探测法试编写 hash 函数解 : hash(h,r.key) { int i, j; j=h(r.key); if(h[j]= =NULL) H[j]=R.key; else { do { j=(j+1)%(m+1); while(h[j]!=null) H[j]=R.key; 67. 哈希表长 m=14,h(key)=key mod 11, 把 1,13,12,34,38,33,27,22 插入散列表中 : (1) 使用线性探测再散列构造散列表 : 位置查找成功的次数 : 查找不成功的次数 : (2) 使用链地址构造散列表 : 第 25

26 查找成功的 ASL= (4*1 3* 2 1*3) 8 1 查找不成功 ASL= ( ) 14 (3) 确定填充因子 :α=8/ (4) 线性探测再散列查找成功的平均探测次数为 : 1 ASL= ( ) 8 线性探测再散列查找不成功的平均探测次数为 : 1 ASL= ( ) 编写有序表进行顺序查找的算法, 并画出判定树, 假设每次查找给定的值是随机的, 又查找成功与不成功的概率也相等, 求每次查找时与给定关键字的比较次数的期望值解 : 设 a 1 < a 2 < < a n, 判定树 :a 1 typedef struct { a 2 ElemType *elem; int length; Sstable; Search(Sstable ST, KeyType key) { a n for(i=1;i<=st.length;i++) { 期望值 : 2*(1 2 n) n if(st.elem[i].key= =key) return i; 2* n 1 else if(st.elem[i].key>key) return 1; 第 26

27 return 1; 69. 关键字为 (53,17,19,61,98,75,79,63,46,49) 散列空间 100,109, 解决冲突利用开发定址法写出散列函数, 形成散列表解 :H(key)=100+key mod 10 或 H(key)=100+(key 的第一位 +key 的第二位 )% 填空 : 1 比较次数与关键字顺序无关的是 ( 选择排序 ) 2 (54,38,96,23,15,72,60,45,83) 采用直接插入排序, 将 60 插入表中需进行 (3) 次比较 3 在排序过程中, 出现排序码移动的方向运动相反, 则排序法是不稳定的 ( 错 ) log 2 n ) 4 快速排序的最大递归深度为 (n), 最小为 ( 1 第 27

2018 年天津城建大学攻读硕士学位研究生入学考试试题 (A) 卷考试科目代码 :825 考试科目名称工程信息技术招生专业 : 建筑与土木工程

2018 年天津城建大学攻读硕士学位研究生入学考试试题 (A) 卷考试科目代码 :825 考试科目名称工程信息技术招生专业 : 建筑与土木工程一单项选择题 ( 本题共 20 小题, 每题 2 分, 共 40 分 ) 1. 计算机所处理的数据一般具有某种内在联系, 这是指 ( ) A. 数据和数据之间存在某种联系 B. 数据项和数据项之间存在某种联系 C. 元素内部具有某种结构 D. 元素和元素之间存在某种联系 2. 在计算机中表示数据时, 数据的物理地址和逻辑地址相同并且连续, 称其为 ( ) A. 链式存储结构 B. 顺序存储结构 C.