数据结构习题

概率表示某个事件发生的可能性。概率密度只能表示概率的分布，因为任何连续型分布取某一个点得概率都为零。 （ ）1、顺序存储方式只能用于线性结构，不能用于非线性结构。 （ ）2、若一个结点是某二叉树子树的中序遍历序列中的第一个结点，则它必是该子树的后序遍历序列中的第一个结点。 （ ）3、求最小生成树的Prim算法在边较少、结点较多时效率较高。 （ ）4、折半查找只能在有序的顺序表上进行而不能在有序链表上进行。 （ ）5、快速排序的速度在所有排序方法中为最快，而且所需附加空间也最少。 （ ）6、在一个有向图的邻接表中，若某结点的链表为空，则该顶点的度一定为零。 （ ）7、在二叉排序树中删除一个结点，接着又将该结点插入到该二叉排序树中去，该二叉 树不会发生变化。 （ ）8、插入排序、选择排序和冒泡排序不都是稳定的排序算法。 （ ）9、在二叉排序树上删除一个结点时，不必移动其它结点，只要将该结点相应的指针域 置空即可。 （ ）10、由二叉树的后序序列和中序序列可以唯一地确定一棵二叉树。 错 错 错 错 错 错 错 对 错 对                     （ ）1、在前序遍历二叉树的序列中，任何结点的子树中的所有结点不一定在该结点之后。 （ ）2、图的最小生成树的形状可能不唯一。 （ ）3、在n个结点的无向图中，若边数大于n－1，则该图必是连通图。 （ ）4、对于给定的关键字集合，以不同的次序插入到初始为空的二叉排序树中，得到的二 叉排序树是相同的。 （ ）5、对有n个的集合进行冒泡排序，所需时间决定于初始记录的排列情况；在初始 记录无序的情况下最好。 （ ）6、将树转换成二叉树，其根结点的右子树必是空的。 （ ）7、插入、删除是数据结构中基本的操作，所以这两种操作在数组中也常用。 （ ）8、任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序不发生改变。 （ ）9、在哈夫曼编码中，出现频率相同的字符编码长度也一定相同。 （ ）10、采用线性探测法处理冲突时，当从哈希表中删除一个记录时，不应将这个记录的所在位置置为空，因为这将会影响以后的查找。 错 对 对 错 错 对 错 对 错 错                     1、 2、初始： Weight Lchild Rchild Parent 3 0 0 0 12 0 0 0 7 0 0 0 4 0 0 0 2 0 0 0 8 0 0 0 11 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0         终态： Weight Lchild Rchild Parent 3 0 0 8 12 0 0 12 7 0 0 10 4 0 0 9 2 0 0 8 8 0 0 10 11 0 0 11 5 1 5 9 9 8 4 11 15 6 3 12 20 7 9 13 27 10 2 13 47 12 11 0         3、邻接矩阵： 0 12 0 0 2 0 0 0 12 0 0 0 0 3 0 5 0 0 0 8 2 4 0 0 0 0 8 0 10 0 8 0 2 0 2 10 0 0 0 0 0 3 4 0 0 0 7 0 0 0 0 8 0 7 0 0 0 5 0 0 0 0 0 0                 2 12 5 2 ^ 邻接表： V1 V2 8 5 ^ 6 3 1 12 V3 6 4 ^ 5 2 4 8 V4 7 8 ^ 5 10 3 8 V5 4 10 ^ 3 2 1 2 V6 7 7 ^ 3 4 2 3 V7 6 7 ^ 4 8 V8 2 5 ^     深度：12634578    广度：12568347 4、 12345678  12345768  12345786    12354678    12354768    12354786 13245678  13245768  13245786    13254678    13254768    13254786 13456278    13452678    13452786    13452768    13425678    13425768    13425786    13427856    13427568    13427586 还有就是以31开头的情况。 5 ^ 4 5、 0 1 9 ^ 3 6 2 3 8 ^ 4   5   6 2 ^ 7 7   8   9       6、 1-2为a1；1-3为a2；3-2为a3；2-4为a4；3-4为a5；3-5为a6；4-5为a7；4-6为a8；5-6为a9。 Ve[1]=0 Ve[2]=max{a1，a2+a3}=3+3=6 Ve[3]=3 Ve[4]=max{6+a4，3+a5}=3+9=12 Ve[5]=12+6=18 Ve[6]=18+3=21 Vl[6]=ve[6]=21 Vl[5]=21-3=18 Vl[4]=18-6=12 Vl[3]=12-9=3 Vl[2]=12-5=7 Vl[1]=3-3=0 E[1]=ve[1]=0                      l[1]=vl[2]-a1=7-2=5 E[2]=0                          l[2]=vl[3]-a2=3-3=0 E[3]=ve[3]=3                      l[3]=vl[2]-a3=7-3=4 E[4]=ve[2]=6                      l[4]=vl[4]-a4=12-5=7 E[5]=ve[3]=3                      l[5]=vl[4]-a5=12-9=3 E[6]=3                          l[6]=vl[5]-a6=18-4=14 E[7]=ve[4]=12                    l[7]=vl[5]-a7=18-6=12 E[8]=12                          l[8]=21-2=19 E[9]=ve[5]=18                    l[9]=vl[6]-a9=21-3=18 关键路径：a2 a5 a7 a9，即v1 v3 v4 v5 v6 7、 初始： 调整成堆：从20开始筛选 交换堆顶和堆底进行排序（略） 8、 Void move(linklist list) { p=s=list; q=list->next; while(q!=null) {if(p->data>q->data) {p=q; t=s; } s=q;q=q->next; } if(p!=list) {t->next=p->next; p->next=list; list=p; } } 第6章 一棵有124个叶子结点的完全二叉树，最多有几个结点？ 答案：n=n1+2n0-1 248 已知某字符串S中共有8种，各种字符分别出现2次、1次、4次、5次、7次、3次、4次和9次，对该字符串用（0，1）进行前缀编码，问该字符串的编码至少有多少位？ 答案：    1  2 3    3 6    5          4  4 11  9    7    8 15 35 1×5+2×5+3×4+5×3+4×3+4×3+9×2+7×2=98位 1、树中结点数目： 递归： int num ( Bitree t) { if (t= = NULL) return 0; else return num(t->lchild)+num(t->rchild)+1; } 非递归： int num(Bitree t) { if (t= = NULL) return 0; p=t; top=count=0; while(p!=null||top>0) { while(p!=null) {if(top=Maxsize-1) { cout<<’栈满！’<lchild; count++; } p=stack[top]; top--; p=p->rchild; } return count; } 2、二叉树深度： 递归： int  high(BiTree  t) { if(t= =NULL)    return(0); hl=high(t->lchild); hr=high(t->rchild); return(max(hl,hr)+1); } 非递归： int high(BiTree t) { if(t=null)  return(0); maxhigh=0; curhigh=0; top=0; p=t; while(p!=null||top>0) { while(p!=null) {if(top=Maxsize-1) { cout<<’栈满！’<lchild; curhigh++; } p=stack1[top]; curhigh=stack2[top]; top--; if(p->lchild=null &&p->rchild=null) if(curhigh>maxhigh) maxhigh=curhigh; p=p->rchild; curhigh++; } return(maxhigh+1); } 3、左右子树交换： 递归： void  process (BiTree  t ) { if (t= =NULL)  return; process  (t->lchild); process  (t->rchild); t->lchild<=>t->rchild; return; } 非递归： void change(BiTree t) { if(t=null)  return ; int rear=0,front=-1; queue[rear]=t; while(front!=rear) { front++; p=queue[front]; if(p->lchild!=null) {rear++; queue[rear]=p->lchild; } if(p->rchild!=null) {rear++; queue[rear]=p->rchild; } temp=p->lchild; p->lchild= p->rchild; p->rchild= temp; } } 4、顺序存储完全二叉树的先序非递归遍历： void  Preorder(SqBiTree bt) {  i=1; top=0; while( i<=n || top!= 0) {  while(i<=n) {call visit(bt[i]); top = top + 1; stack[top]=i; i=2×i; } i=stack[top]; top = top - 1; i=i×2+1; } } 第三章 1、写出和下列递归过程等价的非递归过程： void test(int sum) {int a; read(a); if(a=0) sum=1; else{ test(sum); sum=sum*a; } write(sum); } 解： void test() {int s=1,sum[]; int top=0; read(a); while(a!=0) {sum[top]=a; top++; read(a); } sum[top]=1; while(top>=0) {s=s*sum[top]; top- -; write(s); } } 2、利用栈将一个非空链表进行逆置。 解：（链表结构体定义省略且视其带头结点） void inversion(linklist l) {lnode *stack[]，*p; int top=0; p=l->next; while(p) {stack[top]=p; top++; p=p->next; } p=l; while(top>=0) {p->next=stack[top]; top- -; p=p->next; } p->next=NULL; } 第四章 1、模式串t=”abcaabbcabcaabdab” 求next和nextval。 解：    a b c a a b b c a b c a a b d a b next:0 1  1 1 2  2 3 1  1 2 3 4  5 6 7  1 2 nextval:0 1  1 0 2  1 3 1  0 1 1 0  2 1 7  0 1 2、主串s=”abcaabbcaaabababaabca”，模式为t=”baba”，求：next和nextval：用KMP算法对目标s进行匹配。 解：    b a b a next:0  1 1 2 nextval:0  1 0 1 abcaabbcaaabababaabca b ba b b b ba ba b b b b baba 1、树的举例： 画出和下列已知序列对应的树T： 先根次序：GFKDAIEBCHJ 后根次序：DIAEKFCJHBG 2、哈夫曼树举例： 已知下列字符A、B、C、D、E、F、G的权值为3、12、7、4、2、8、11，试填写出其对应的哈夫曼树的存储结构的初态和终态。 3、最小生成树PRIM： 画出下图的邻接矩阵和邻接表，根据邻接表写出深度和广度优先遍历序列，并画出用PRIM算法得到最小生成树的过程。 4、拓扑排序举例： 写出下图的所有可能的拓扑序列。 5、哈希表冲突举例： 若的地址范围是[0，9]，哈希

函

关于工期滞后的函关于工程严重滞后的函关于工程进度滞后的回复函关于征求同志党风廉政意见的函关于征求廉洁自律情况的复函

数为H（KEY）=（key+2）MOD9，采用拉链法处理冲突，画出元素7、4、5、3、6、2、8、9依次插入哈希表以后的状态。 6、关键路径举例： 下图是一个AOE网，找出关键路径（

要求

对教师党员的评价套管和固井爆破片与爆破装置仓库管理基本要求三甲医院都需要复审吗

过程）。 7、堆排序的举例： 将下列序列调整成大顶堆，并完成排序过程： 85，100，90，85，60， 20，25，10，70，75，65，50，80。 8、已知非空单链表list，写一算法找出链表中的数据域值最小的那个结点，并将其链接到表的最前面。 9、对{32，40，58，44，85，76，72，23，38，93}这一整数集生成一棵平衡二叉树。 第6章 一棵有124个叶子结点的完全二叉树，最多有几个结点？ 答案：n=n1+2n0-1 248 已知某字符串S中共有8种，各种字符分别出现2次、1次、4次、5次、7次、3次、4次和9次，对该字符串用（0，1）进行前缀编码，问该字符串的编码至少有多少位？ 答案：    1  2 3    3 6    5          4  4 11  9    7    8 15 35 1×5+2×5+3×4+5×3+4×3+4×3+9×2+7×2=98位 1、树中结点数目： 递归： int num ( Bitree t) { if (t= = NULL) return 0; else return num(t->lchild)+num(t->rchild)+1; } 非递归： int num(Bitree t) { if (t= = NULL) return 0; p=t; top=count=0; while(p!=null||top>0) { while(p!=null) {if(top=Maxsize-1) { cout<<’栈满！’<lchild; count++; } p=stack[top]; top--; p=p->rchild; } return count; } 2、二叉树深度： 递归： int  high(BiTree  t) { if(t= =NULL)    return(0); hl=high(t->lchild); hr=high(t->rchild); return(max(hl,hr)+1); } 非递归： int high(BiTree t) { if(t=null)  return(0); maxhigh=0; curhigh=0; top=0; p=t; while(p!=null||top>0) { while(p!=null) {if(top=Maxsize-1) { cout<<’栈满！’<lchild; curhigh++; } p=stack1[top]; curhigh=stack2[top]; top--; if(p->lchild=null &&p->rchild=null) if(curhigh>maxhigh) maxhigh=curhigh; p=p->rchild; curhigh++; } return(maxhigh+1); } 3、左右子树交换： 递归： void  process (BiTree  t ) { if (t= =NULL)  return; process  (t->lchild); process  (t->rchild); t->lchild<=>t->rchild; return; } 非递归： void change(BiTree t) { if(t=null)  return ; int rear=0,front=-1; queue[rear]=t; while(front!=rear) { front++; p=queue[front]; if(p->lchild!=null) {rear++; queue[rear]=p->lchild; } if(p->rchild!=null) {rear++; queue[rear]=p->rchild; } temp=p->lchild; p->lchild= p->rchild; p->rchild= temp; } } 4、顺序存储完全二叉树的先序非递归遍历： void  Preorder(SqBiTree bt) {  i=1; top=0; while( i<=n || top!= 0) {  while(i<=n) {call visit(bt[i]); top = top + 1; stack[top]=i; i=2×i; } i=stack[top]; top = top - 1; i=i×2+1; } } 河 北 大 学 课 程 考 核 试 卷 2009—2010 学年第 1 学期      2008  级  生物信息  专业（类）  考核科目  数据结构  课程类别 必修 考核类型 考试  考核方式 闭卷  卷别 B （注：考生务必将答案写在答题纸上，写在本试卷上的无效） 一、选择题：（共20分，每小题2分） 1、在非空双向循环链表中，在由q所指的链结点后面插入一个由p所指的链结点的过程是依次执行：p->prior=q；p->next=q->next；q->next=p；（  ）。 A.q->prior=p                      B.q->next->prior=p C.p->next->prior=p                D.p->prior->prior=p 2、数据的四种基本存储结构是指（  ）。 A.顺序存储结构、索引存储结构、直接存储结构、倒排存储结构 B.顺序存储结构、链式存储结构、树型存储结构、图型存储结构 C.顺序存储结构、非顺序存储结构、指针存储结构、树型存储结构 D.顺序存储结构、索引存储结构、链式存储结构、散列存储结构 3、设有一顺序栈，元素s1、s2、s3、s4、s5、s6依次进栈，如果6个元素出栈的顺序是s2、s4、s3、s6、s5、s1，则栈的容量至少应该是（  ）。 A.2          B.3        C.5        D.6 4、假设S=“I□AM□A□STUDENT”，则运算substr(S,4,8)的结果为(  )。 A.“M□A□S”                            B.“M□A□STUD” C.“A□STUDEN”                        D.“STUD” 5、在下列各棵二叉树中，二叉排序树是(  )。 B—4—1 6、若一棵二叉树有10个度为2的结点，则该二叉树的叶结点的个数为（  ）。 A.9            B.11            C.12            D.不确定 7、线索二叉树中某结点*P没有左孩子的充要条件是（  ）。 A.P->lchild=null      B.P->rchild=null    C.P->ltag=0    D.P->ltag=1 8、当待排序序列中记录数较少或基本有序时，最适合的排序方法为(    )。 A.直接插入排序法                        B.快速排序法 C.堆排序法                            D.归并排序法 9、若对序列（15，30，26，22，69，50，53，87）采用二路归并法排序，则进行一趟归并后产生的序列为（　）。 A.15，30，22，26，50，69，53，87    B.15，22，26，30，50，53，69，87 C.15，26，30，22，50，69，53，87    D.15，26，22，30，50，53，69，87 10、已知一有向图的邻接表存储结构如右图所示，则根据有向图的广度优先遍历算法，从顶点v1出发，所得到的顶点序列是（  ）。 A.v1,v2,v3,v5,v4        B.v1,v3,v2,v4,v5    C.v1,v3,v4,v5,v2        D.v1,v4,v3,v5,v2 二、填空题：（共20分，每个空2分） 1、通常从四个方面评价算法的质量：正确性、_________、_________和高效性。 空串的长度等于          。 3、顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。插入一个元素时平均要移动表中的_____ ____个元素。 4、非空单循环链表L中的*p是尾结点的条件是___ ___ ___。 5、二维数组A［11］［20］采用按行为主序的存储方式，每个元素占4个存储单元，若A［0］［0］的存储地址为300，则A［10］［10］的地址为            。 6、右图中树的度为            。 B—4—2 7、在分块查找方法中，首先在        中查找，然后再查找相应的块。 8、对一组关键码（46，79，54，38，40，84）以第一个记录为支点记录，利用快速排序方法进行排序后得到的第一次划分的结果为______________。 三、

应用题

小学应用题 下载一年级应用题应用题一年级一年级下册数学应用题一年级下册应用题

：（共40分） 1、画出如下图所示的森林经转换后所对应的二叉树，并写出其二叉树的先序遍历序列和中序遍历序列。（9分） 2、已知某字符串S中共有8种，各种字符分别出现2次、1次、4次、5次、8次、6次、10次和9次，对该字符串用（0，1）进行前缀编码，问该字符串的编码至少有多少位？（9分） 3、试写出下图的邻接矩阵存储并列出可能的拓扑排序序列（至少写出4个正确的序列）。（7分） 4、已知长度为8的查找表：{10, 13, 19, 7, 4, 8, 15, 20}，试按表中元素的顺序依次插入到一棵初始为空的平衡二叉树中。画出插入完成后的平衡二叉树，并求其在等概率的情况下查找成功的平均查找长度。（8分） 5、对给定序列 60，42，30，72，85，78，41，90，66完成下列要求：建立一棵3阶B－树；删除72后调整。（7分） B—4—3 四、算法设计：（共20分） 要求：⑴自己定义有关的存储类型； 算法中的主要操作步骤要加以注释。 1、已知非空线性链表第一个链结点的指针为list，请写一算法，将链表中的数据域最大的那个结点移到链表的最后面。（10分） 2、二叉树采用链接存储结构，设计一个算法交换二叉树中每个结点的左右孩子结点。（10分） 1、树的举例： 画出和下列已知序列对应的树T： 先根次序：GFKDAIEBCHJ 后根次序：DIAEKFCJHBG 2、哈夫曼树举例： 已知下列字符A、B、C、D、E、F、G的权值为3、12、7、4、2、8、11，试填写出其对应的哈夫曼树的存储结构的初态和终态。 3、最小生成树PRIM： 画出下图的邻接矩阵和邻接表，根据邻接表写出深度和广度优先遍历序列，并画出用PRIM算法得到最小生成树的过程。 4、拓扑排序举例： 写出下图的所有可能的拓扑序列。 5、哈希表冲突举例： 若的地址范围是[0，9]，哈希函数为H（KEY）=（key+2）MOD9，采用拉链法处理冲突，画出元素7、4、5、3、6、2、8、9依次插入哈希表以后的状态。 6、关键路径举例： 下图是一个AOE网，找出关键路径（要求过程）。 7、堆排序的举例： 将下列序列调整成大顶堆，并完成排序过程： 85，100，90，85，60， 20，25，10，70，75，65，50，80。 8、已知非空单链表list，写一算法找出链表中的数据域值最小的那个结点，并将其链接到表的最前面。 9、对{32，40，58，44，85，76，72，23，38，93}这一整数集生成一棵平衡二叉树。 河北大学课程考核参考答案及评分

标准

excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载

（ 2009—2010 学年第 1学期） 考核科目  数据结构  课程类别 必修课 考核方式 闭卷 卷别  B  一、选择题：（共20分，每小题2分）该题考查学生基本知识的掌握情况。 1、c  2、d  3、b  4、b  5、c  6、b  7、d  8、a  9、a  10、b 二、填空题：（共20分，每个空2分） 考核目的：学生对基本概念、知识点的掌握程度。 答案： 1、易读性 健壮性 2、0 3、n/2 4、p－>next=L 5、1140 6、3 7、索引表 8、40，38，46，54，79，84 三、应用题：（共40分） 1、考核目的：本题考查学生对树和二叉树的认识 满分：9分 参考答案以及评分标准： 先序：ABECDFGHIJ （2分）  中序：EBCDAHIGFJ  （2分） （5分） 2、考核目的：学生对哈夫曼树的认识 评分标准： 2  1 3 4 7    8    5  6 15        11      10  9 26              19 45        （7分） 2*5+1*5+4*4+5*3+6*3+8*3+10*2+9*2=126    (2分) 3、（7分） 考核目的：学生对有向图的存储和拓扑排序的认识 评分标准：邻接矩阵存储表示3分，拓扑序列每个答案1分 152364；152634；156234；512364；512634；516234；561234（所有可能的情况） 4、（8分） 考核目的：学生对平衡二叉树的认识 考核目的：学生对平衡二叉树的认识 评分标准：每个旋转结果2分，平均查找长度2分 ASL=（1×1+2×2+4×3＋1×4）/8＝21/8    （2分） 5、考核目的：学生对堆排序的认识 评分标准： 3阶B－树(6分) 42、60      42              42            42、72          42、72 30      60    30    60、72    30    60    85    30  60  78、 85 72                          72 42           85                42          85 30、41    60  78    90  30、41  60、66 78      90 删除72后（1分） 42、78 30  60、66  85、 90 四、算法设计：（共20分） 考核目的：考察学生对单链表结构的理解和掌握。 满分：10分 参考答案及评分标准： typedef  struct  node                //链表结点的结构    （1分） {  int  data; struct node  *next; }Node,*Linklist; void move( linklist list ) {q=list；p=list->next；r=list；    //初始化三个指针 （2分） while(p!=null) {if(p->data>q->data)    {s=r；q=p；}  //寻找最大值结点地址 （2分） r=p；p=p->next；}      //移动指针 （1分） if(q!=r)          {  if(q==list)    list=list->next；  //修改表尾 （4分） else  s->next=q->next； r->next=q； q->next=null； } } 2、（10分） 考核目的：学生对二叉树遍历编程能力的掌握情况 评分标准：各说明正确1分；树类型定义正确1分；函数实现的描述说明正确7分；函数程序正确1分 参考答案： typedef        struct    node{ ELEM    e；                // e存放元素的值 struct    node    *lc,*rc；// lc、rc分别指向左右子女  （1分） }NODE；                //结点类型 class  TREE            //二叉树类定义 {public： TREE ()； virtual ~ TREE ()； void    xchg_child_node(NODE    *pt)；                    //交换子女结点方法函数 private： NODE    *rt；        //指向二叉树根的指针 }； void    TREE::xchg_child_node(NODE    *pt) {                          //pt指向当前树的根      (1分) NODE    *s； if(pt)            //判断当前结点是否为空 (1分) {    s=pt->lc；pt->lc=pt->rc；pt->rc=s；        //交换子女(2分) xchg_child_node(pt->lc)；                //继续处理左子树(2分) xchg_child_node(pt->rc)；                //继续处理右子树(2分) } }