湖南大学数据结构第5次作业

HUNAN UNIVERSITY数据结构实验报告题目：实验5四则运算表达式求值学生姓名谢毅学生姓名冯吉禹学生姓名吕志远学生学号20110806109学生学号20110806110学生学号20110806114专业班级信息安全1101班指导老师夏艳完成日期2013 年04 月 19日一．需求分析1、利用二叉树后序遍历来实现表达式的转换，同时可以使用实验3的结果来求解后缀表达式的值。

2、输入输出格式：输入：在字符界面上输入一个中缀表达式，回车表示结束。

输出：如果该中缀表达式正确，那么在字符界面上输出其后缀表达式，其中后缀表达式中两相邻操作数之间利用空格隔开；如果不正确，在字符界面上输出表达式错误提示。

输入：21+23*（12-6）输出：21 23 12 6 -*+一．概要设计抽象数据类型1.使用二叉树来实现2．本程序包含四个基本模块①主程序模块：建树的过程②没有括号时的输入③有括号时的输入○4后序输出三﹑算法（C++）物理数据类型建树的时候对于优先级比较高的符号最为子结点插入，对于优先级比较低的则作为父结点插入，数据直接插入在字符的左右子结点位置。

/*问题描述四则运算表达式求值，将四则运算表达式用中缀表达式，然后转换为后缀表达式，并计算结果。

基本要求使用二叉树来实现。

实现提示利用二叉树后序遍历来实现表达式的转换，同时可以使用实验3的结果来求解后缀表达式的值。

输入输出格式：输入：在字符界面上输入一个中缀表达式，回车表示结束。

输出：如果该中缀表达式正确，那么在字符界面上输出其后缀表达式，其中后缀表达式中两相邻操作数之间利用空格隔开；如果不正确，在字符界面上输出表达式错误提示。

*/#include<iostream.h>#include <stdio.h>/*二叉树的节点类*/class Node{public:int num;//元素char c;//操作符Node* lc;//左指针Node* rc;//右指针Node* pa;//父指针Node(int num,Node* lc=NULL,Node* rc=NULL){this->num=num;this->lc=lc;this->rc=rc;}Node(char c,Node* lc=NULL,Node* rc=NULL){this->c=c;this->lc=lc;this->rc=rc;}bool isLeaf(){return (lc==NULL)&&(rc==NULL);}};void Nomal(char &t,char &c,Node* &one,Node* &two);//正常输入void UNomal(char &t,char &c,Node* &one,Node* &two);//带括号输入void BHVisit(Node* root);/*二叉树类*/class TwoTree{private:Node* root;//根节点Node* present;//当前表达式节点public:TwoTree(){root=NULL;present=root;}Node* getroot(){return root;}bool gt(Node* two,Node* present)//比较优先级的函数{char ct=two->c;char cp=present->c;if(ct=='*'||ct=='/')if(cp=='+'||cp=='-')return true;return false;}void insert(Node* one,Node* two=NULL)//向插入的方法{cout<<" 要插入了 "<<one->num<<" "<<two->c<<endl;if(root==NULL){root=two;root->lc=one;one->pa=root;present=root;return;}if(two->c=='\n'){present->rc=one;one->pa=present;return;}if(gt(two,present))//如果输入的操作符的优先等级大于当前指针的优先级{two->lc=one;one->pa=two;present->rc=two;two->pa=present;present=two;return;}present->rc=one;while(!gt(two,present)&&present!=root)//如果输入的操作符的优先等级不大于当前指针的优先级{present=present->pa;//指向父节点}if(gt(two,present))//如果输入的操作符的优先等级大于当前指针的优先级{two->lc=present->rc;present->rc->pa=two;present->rc=two;two->pa=present;present=two;return;}else{two->lc=present;present->pa=two;root=two;present=two;}}};void main(){TwoTree tt;Node* root;Node* one;Node* two;char c,t;int index=0;cout<<"请输入一个中缀表达式"<<endl;while(1){t=getchar();cout<<t<<endl;if(t!='(')Nomal(t,c,one,two);elseUNomal(t,c,one,two);tt.insert(one,two);if(c=='\n')break;}root=tt.getroot();BHVisit(root);return;}void Nomal(char &t,char &c,Node* &one,Node* &two) {int num;num=t-'0';cout<<num<<"--------"<<endl;c=getchar();one=new Node(num);two=new Node(c);}void UNomal(char &t,char &c,Node* &one,Node* &two) {int num;TwoTree ttp;while(1){t=getchar();num=t-'0';cout<<num<<"+++++++++++"<<t<<endl;c=getchar();if(c==')'){char cp='\n';c=getchar();one=new Node(num);two=new Node(cp);ttp.insert(one,two);break;}one=new Node(num);two=new Node(c);ttp.insert(one,two);}one=ttp.getroot();two=new Node(c);}void BHVisit(Node* root)//后序遍历函数{if(root==NULL)return;BHVisit(root->lc);BHVisit(root->rc);if(root->isLeaf())cout<<root->num<<" ";elsecout<<root->c<<" ";}六．算法的时间复杂度：整个程序的时间复杂度是O(n).七．实验心得谢毅：本次实验相对上次实验来说难度提升比较大，刚开始的时候觉得无从下手，后来翻阅了书上的关于树的内容，并且和同学们经过了讨论，终于想出了这次实验的建树方式。

11、画出对下列存储于数组中的值执行buildheap后得到的最大值堆：210 5 12 3 2 1 8 7 9 434先序遍历为12 10 4 1 2 9 5 8 3 75中序遍历为1 4 2 10 5 9 12 3 8 7672、假设某字母表各个字母的权如下：8Q Z F M T S O E92 3 10 10 10 15 20 3010(a)按照这个字母表，一个包含n个字母的字符串采用Huffman编码在最差情11况下需要多少位？怎样的串会出现最差情况？1213在最差的情况下需要5*n位，当所有的字母都是Q或者Z的时候。

（b）按照这个字母表，包含n个字母的字符串采用Huffman编码在最佳情况1415下需要多少位？怎样的串会出现最佳情况？16在最佳的情况下需要2*n位，当所有的字母都是E或者O的时候。

17（c）按照一个字母表，一个字母平均需要多少位？18（2*30 + 2*20 + 3*15 + 3*10 + 3*10 + 4*10 + 5*3+ 5*2）/100 =2.719∴ 2.7203、编写一个算法来判断两棵树是否相同。

尽可能提高算法效率，并分析算法21的运行时间代价。

22template <class Elem>23bool Compare(GTNode<Elem>* tree1, GTNode<Elem>* tree2) {24GTNode<Elem> *num1, *num2;25if (((tree1 == NULL) && (tree2 != NULL)) ||26((tree2 == NULL) && (tree1 != NULL)))27return 0;28if ((t1 == NULL) && (t2 == NULL)) return 1;29if (tree1->val() != tree2->val()) return 0;Num1 = tree1->left_child();3031Num2 = tree2->left_child();32while(!((num1 == NULL) && (num2 == NULL))) {if (!Compare(num1, num2)) return false;3334if (num1 != NULL) num1 = num1->right_value();35if (num2 != NULL) num2 = num2->right_value();36}}3738O（n）394、编写出一个函数，以一棵树为输入，返回树的结点数目。

Source：http://210.43.96.230:10007/Course/Index.htm第 1 页（共4 页）确的）1、若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为（）（Ａ）i （Ｂ）n=i （Ｃ）n-i+1 （Ｄ）不确定2、线性表若采用链式存储结构时，要求内存中可用存储单元的地址: （）（A）必须是连续的（B）部分地址必须是连续的（C）一定是不连续的（D）连续或不连续都可以3. 在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是：（）（A）访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）（B）在第i个结点后插入一个新结点（1≤i≤n）（C）删除第i个结点（1≤i≤n）（D）将n个结点从小到大排序4、具有n(n>0)个结点的完全二叉树的深度为（）。

(Ａ) ⎡log2(n)⎤ (Ｂ) ⎣log2(n)⎦ (Ｃ) ⎣log2(n)⎦+1 (Ｄ) ⎡log2(n)+1⎤5、有n个顶点e条边的无向图G,它的邻接表中的表结点总数是（）。

(A) 2n (B)n (C) 2e (D) e6、静态查找表与动态查找表二者的根本差别在于（）（A）它们的逻辑结构不一样（B）施加在其上的操作不同（C）所包含的数据元素的类型不一样（D）存储实现不一样7、连通图G中有n个顶点,G的生成树是（）连通子图.(A)包含G的所有顶点 (B)包含G的所有边(C)不必包含G的所有顶点 (D)必须包含G的所有顶点和所有的边8、设有5000个无序的元素，希望用最快的速度挑选出其中前50 个最大的元素，最好选用（）法。

（A）冒泡排序（B）快速排序（C）堆排序（D）基数排序9、下面的排序算法中，（）是不稳定的？（A）希尔排序（B）冒泡排序（C）直接插入排序（D）基数排序10、散列文件使用散列函数将记录的关键字值计算转化为记录的存放地址。

因为散列函数不是一对一的关系，所以选择好的（）方法是散列文件的关键。

2022年湖南大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、已知广义表LS=（（a，b，c），（d，e，f）），用head和tail数取出LS中原子e 的运算是（）。

A.head（tail（LS））B.tail（head（LS））C.head（tail（head（tail（LS））））D.head（tail（tail（head（LS））））2、下述文件中适合于磁带存储的是（）。

A.顺序文件B.索引文件C.哈希文件D.多关键字文件3、连续存储设计时，存储单元的地址（）。

A.一定连续B.一定不连续C.不一定连续D.部分连续，部分不连续4、已知有向图G=(V，E)，其中V={V1，V2，V3，V4，V5，V6，V7}， E=｛<V1，V2>，<V1，V3>，<V1，V4>，<V2，V5>，<V3，V5>， <V3，V6>，<V4，V6>，<V5，V7>，<V6，V7>｝，G的拓扑序列是（）。

A.V1，V3，V4，V6，V2，V5，V7B.V1，V3，V2，V6，V4，V5，V7C.V1，V3，V5，V2，V6，V7D.V1，V2，V5，V3，V4，V6，V75、下列关于AOE网的叙述中，不正确的是（）。

A.关键活动不按期完成就会影响整个工程的完成时间B.任何一个关键活动提前完成，那么整个工程将会提前完成C.所有的关键活动提前完成，那么整个工程将会提前完成D.某些关键活动若提前完成，那么整个工程将会提前完成6、已知字符串S为“abaabaabacacaabaabcc”，模式串t为“abaabc”，采用KMP算法进行匹配，第一次出现“失配”（s!＝t）时，i＝j＝5，则下次开始匹配时，i和j的值分别（）。

A．i＝1，j＝0 B．i＝5，j＝0 C．i＝5，j＝2 D．i＝6，j＝27、下列选项中，不能构成折半查找中关键字比较序列的是（）。

HUNAN UNIVERSITY 课程实习报告题目：快速排序问题学生姓名刘乐学生学号20080820208专业班级通信工程2班指导老师朱宁波完成日期2010年5月31日一、需求分析：排序是计算机内经常进行的一种操作，其目的是将一组无序的记录序列调整为有序的记录序列。

在操作系统中，我们总是希望以最短的时间处理完所有的任务。

但事情总是要一件件的做，任务也要操作系统一件件的处理。

只需要将n件任务按用时从小到大排序，就可以得到任务依次的处理顺序。

当有n件任务同时来临时，每件任务需要用时n，求让所有任务等待的时间和最小的任务处理顺序。

1.本程序要求：（1）输入即将输入序列的元素数，输入一行无序的序列。

（2）运用快速排序的方法将该序列按从小到大的顺序排列。

3在dos系统下输入要排序数的个数和权值。

4测试数据：二、概要设计为实现上述功能需要用到顺序表的存储结构。

算法基本思想通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可对这两部分记录继续进行排序，已达到整个序列有序。

程序设计流程程序由三个模块组成：（1）输入模块：dos系统下输入病人的待排个数和权值（2）快速排序函数模块：实现记录的划分。

（3）输出模块：排序前和排序后的序列。

三、详细设计1.构造一个顺序表的存储结构用来存储病人的待排序长度。

typedef int KeyType;//typedef int InfoType;typedef struct{KeyType key;//InfoType otherinfo;}RedType;typedef struct{RedType r[MAXSIZE+1];int length;}SqList;2 入队函数:构造调整函数int Partition(SqList &L,int low,int high){L.r[0]=L.r[low];//用子表第一个记录做枢轴记录pivotkey=L.r[0].key;//枢轴记录关键字while(low<high)//从表两端向中间扫描{while(low<high && L.r[high].key>=pivotkey)high--;L.r[low]=L.r[high]; //将比枢轴小的移到低端while(low<high && L.r[low].key<=pivotkey)low++;L.r[high]=L.r[low]; / /将比枢轴大的移到高端}L.r[low]=L.r[0];//枢轴记录到位return low;//返回枢轴位置}void QSort(SqList &L,int low,int high)//多次递归实现所有数有序化{if(low<high){pivotloc=Partition(L,low,high);QSort(L,low,pivotloc-1);QSort(L,pivotloc+1,high);}}3主函数void main(){int n,i;SqList L;printf("please enter the num:\n");scanf("%d",&n);printf("%d",n);printf("\n");printf("please enter the values:\n");for(i=1;i<n+1;i++){scanf("%d",&L.r[i]);}printf("排序前：\n");for(i=1;i<n+1;i++){printf("%d ",L.r[i]);}printf("\n");/*unsigned int seed;printf("enter a seed of srand：\n");scanf("%u",&seed);srand(seed);pivotkey=rand(L.r[n]);*/QSort(L,1,n);printf("排序后：\n");for(i=1;i<n+1;i++){printf("%d ",L.r[i]);}printf("\n");}四、调试分析：算法的时空分析：算法时间复杂度在最坏情况下为o（nlogn）输入输出格式：五、实验心得：本次实验也是在宿舍完成的，因此去了就是让助教老师看了一下就通过了，因为书上用到快速排序的问题程序给的已经很全面，我就主要用这种方法实现了函数间的构造，所以还是难度不大，这次实验不仅熟悉了快速排序内容，而且对新学的内容有了更深的理解。

1、画出对下列存储于数组中的值执行buildheap后得到的最大值堆：10 5 12 3 2 1 8 7 9 4先序遍历为12 10 4 1 2 9 5 8 3 7中序遍历为1 4 2 10 5 9 12 3 8 72、假设某字母表各个字母的权如下：Q Z F M T S O E2 3 10 10 10 15 20 30(a)按照这个字母表，一个包含n个字母的字符串采用Huffman编码在最差情况下需要多少位？怎样的串会出现最差情况？在最差的情况下需要5*n位，当所有的字母都是Q或者Z的时候。

（b）按照这个字母表，包含n个字母的字符串采用Huffman编码在最佳情况下需要多少位？怎样的串会出现最佳情况？在最佳的情况下需要2*n位，当所有的字母都是E或者O的时候。

（c）按照一个字母表，一个字母平均需要多少位？（2*30 + 2*20 + 3*15 + 3*10 + 3*10 + 4*10 + 5*3+ 5*2）/100 =2.7∴ 2.73、编写一个算法来判断两棵树是否相同。

尽可能提高算法效率，并分析算法的运行时间代价。

template <class Elem>bool Compare(GTNode<Elem>* tree1, GTNode<Elem>* tree2) {GTNode<Elem> *num1, *num2;if (((tree1 == NULL) && (tree2 != NULL)) ||((tree2 == NULL) && (tree1 != NULL)))return 0;if ((t1 == NULL) && (t2 == NULL)) return 1;if (tree1->val() != tree2->val()) return 0;Num1 = tree1->left_child();Num2 = tree2->left_child();while(!((num1 == NULL) && (num2 == NULL))) {if (!Compare(num1, num2)) return false;if (num1 != NULL) num1 = num1->right_value();if (num2 != NULL) num2 = num2->right_value();}}O（n）4、编写出一个函数，以一棵树为输入，返回树的结点数目。

1. 分别画出在线性表（a,b,c,d,e,f,g）中进行折半查找，以查关键字等于e、f和g的过程。

(1)查eStep 1: a b c d e f g↑↑↑low mid high d<e low=mid + 1;Step 2: a b c d e f g↑↑↑low mid high f>e high=mid – 1;Step 3: a b c d e f g↑low/highmid e==e return(mid);(2)查fStep 1: a b c d e f g↑↑↑low mid high d<f low=mid + 1;Step 2: a b c d e f g↑↑↑low mid high f==f return(mid);(3)查gStep 1: a b c d e f g↑↑↑low mid high d<g low=mid + 1;Step 2: a b c d e f g↑↑↑low mid high f<g low=mid + 1;Step 3: a b c d e f g↑low/highmid g==g return(mid);2. 请将折半查找的算法改写为递归算法。

int BiSearch( SSTable *ST,int low, int high ){//用递归方法对表ST进行折半查找ST.elem[0]mid = ( low + high ) / 2;if( ST.elem[mid] != ST.elem[0] ){if( ST.elem[mid] > ST.elem[0] ) BiSearch( ST, low, mid-1 );if( ST.elem[mid] < ST.elem[0] ) BiSearch( ST, mid+1, high);}elsereturn (mid);}int Search_Bi( SSTable *ST ,KeyType key ){//在表ST中折半查找元素key(*ST).elem[0] = key;return( BiSearch ( ST, 1, (*ST).length ) );}3. 编写判别给定二叉树是否为二叉排序树的算法。

习题 51.填空题(1) __________________________________________________________________________ 已知二叉树中叶子数为50，仅有一个孩子的结点数为30，则总结点数为( _______________________ )。

答案：129(2) 3 个结点可构成( ___________ )棵不同形态的二叉树。

答案： 5(3) __________________________________________________________________________ 设树的度为5，其中度为1~5 的结点数分别为6、5、4、3、2 个，则该树共有( ________________ ) 个叶子。

答案：31(4)在结点个数为n (n>1)的各棵普通树中，高度最小的树的高度是( ___________ ),它有( ____________ )个叶子结点，( ______________ )个分支结点。

高度最大的树的高度是( ____________ )，它有( ____________ )个叶子结点，( ______________ )个分支结点。

答案： 2 n-1 1 n 1 n-1( 5)深度为k 的二叉树，至多有( ______________ )个结点。

答案：2k-1(6)(7)有n 个结点并且其高度为n 的二叉树的数目是( _________________ ) 。

n-1答案：2( 8)设只包含根结点的二叉树的高度为0，则高度为k 的二叉树的最大结点数为( ___________ )，最小结点数为( ______________ ) 。

答案：2k+1-1 k+1(9)将一棵有100个结点的完全二叉树按层编号，则编号为49的结点为X，其双亲PARENT(X )的编号为()。

答案：24(10)已知一棵完全二叉树中共有______________ 768 个结点，则该树中共有( )个叶子结点。

操作系统第五次作业第八章Explain the difference between internal and external fragmentation.简述内部碎片和外部碎片的区别答：内部碎片存在于块的内部，如内存块大小为512k，而某逻辑内存要求一个200k大小的块，此时操作系统会分配给它一个大小为512k的块（由于块是内存分配的最小单元），所以会造成了312k大小的内存碎片，这部分碎片即使是空的也无法使用，称作内部碎片。

减少内部碎片可以通过减小块的大小来解决。

外部碎片是指在连续内存分配的进程装入和移出内存的过程中，空闲的内存空间被分成了较多小片段，这些小片段不连续，所以无法被连续分配，这样会造成即使碎片大小之和大于新进程所需内存，但是也无法给新进程分配的情况，这就是外部碎片。

外部碎片可以通过紧缩来解决。

Given five memory partitions of 100 KB, 500 KB, 200 KB,300 KB, and 600KB (in order), how would each of the first-fit,best-fit, and worst-fit algorithms place processes of 212 KB,417 KB, 112 KB, and 426 KB (in order) Which algorithm makes the most efficient use of memory给出100kb，500kB，200kB，300kB，600kB大小的内存空间（按顺序），对于首次适应，最佳适应和最差适应算法，要按顺序放置212kB，417kB，112kB和426kB 大小的进程会是怎样安排的哪个算法的内存利用率最高答：首次适应是每次从头开始找，直到找到第一个比当前要放置的内存大小要大的内存空间时，放置该内存。

最佳适应是每次遍历内存空间一次，找大于当前要放置的内存块大小要大的中间的最小者，放置该内存。

第5章树和二叉树一、单项选择题1.以下说法错误的是（B ）。

A. 存在这样的二叉树，对其采用任何次序的遍历其结点访问序列均相同B. 二叉树是树的特殊情形C. 满二叉树中所有叶结点都在同一层上D. 在二叉树只有一棵子树的情况下，也要指出是左子树还是右子树2.树最适合用来表示( C)。

A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据3.下列叙述正确的是（C ）。

A. 二叉树是度为2的有序树B. 完全二叉树一定存在度为1的结点C. 深度为k的二叉树中结点总数≤2k-1D. 对于有n个结点的二叉树，其高度为⎣log2n⎦+14.按照二叉树的定义，具有三个节点的二叉树有( C )种。

A.3B.4C.5D.65.下列叙述中正确的是（C ）。

A. 二叉树是度为2的有序树B. 二叉树中的结点只有一个孩子时无左右之分C. 二叉树中每个结点最多只有两棵子树，并且有左右之分D. 二叉树若存在两个结点，则必有一个为根，另一个为左孩子6.设某二叉树中度数为0的结点数为N0，度数为1的结点数为N l，度数为2的结点数为N2，则下列等式成立的是（ C ）。

A.N0=N1+1 B.N=Nl+N2C.N=N2+1 D.N=2N1+17.设按照从上到下、从左到右的顺序从1开始对完全二叉树进行顺序编号，则编号为i结点的左孩子结点的编号为（ B ）。

A. 2i+1B.2iC.i/2D.2i-18.有100个结点的完全二叉树由根开始从上到下从左到右对结点进行编号，根结点的编号为1，编号为46的结点的右孩子的编号为（ C ）A．50 B．92 C．93 D．869.若一棵有n个结点的树，则该树中的度之和为（C ）。

A. n+1B. nC. n-1D. 不确定10.已知完全二叉树有90个结点，则整个二叉树有（ B ）个度为1的结点。

A 0B 1C 2D 不确定11.一棵完全二叉树上有1001个结点，其中叶子结点的个数是（C ）。