2010年自学考试《数据结构》各章复习要点总结

一选择题1．下述哪一条是顺序存储结构的优点？（）存储密度大B插入运算方便C.删除运算方便D.可方便地用于各种逻辑结构的存储表示数据结构在计算机内存中的表示是指（ ）。A.数据的物理结构B.数据结构C.数据的逻辑结构D.数据元素之间的关系下面关于线性表的叙述中，错误的是哪一个？（）线性表采用顺序存储，必须占用一片连续的存储单元。线性表采用顺序存储，便于进行插入和删除操作。线性表采用链接存储，不必占用一片连续的存储单元。线性表采用链接存储，便于插入和删除操作。4•若线性表最常用的操作是存取第i个元素及其前驱的值，则采用（）存储方式节省时间。A.单链表B.双向链表C.循环链表D.顺序表线性表是具有n个（）的有限序列（n〉0）。A.表元素B.字符C.数据元素D.数据项E.信息项若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。A.顺序表B.双链表C.带头结点的双循环链表D.单循环链表7某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。A.单链表B.仅有头指针的单循环链表C.双链表D.仅有尾指针的单循环链表8、 设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用（）最节省时间。A.单链表B.单循环链表C.带尾指针的单循环链表D.带头结点的双循环链表9、 若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用（）存储方式最节省运算时间。A.单链表B.双链表C.单循环链表D.带头结点的双循环链表10、 链表不具有的特点是（）A.插入、删除不需要移动元素B.可随机访问任一元素C.不必事先估计存储空间D.所需空间与线性长度成正比11、 3个结点可构成 棵不同形态的二叉树。a2b3c4d512、某二叉树的先序序列和后序序列正好相反，则该二叉树一定是 的二叉树。a空或者只有一个结点 b高度等于其结点数c任一结点无左孩子d任一结点无右孩子13、深度为6（根的层次为1）的二叉树至多有 结点。a64b32c31d63TOC\o"1-5"\h\z14、在有n个结点的二叉链表中，值为非空的链域的个数是 。an-1b2n-1cn+1d2n+115、 将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为 。a98b99c50d4816、 在有n个叶子结点的哈夫曼树中，其结点总数为 。a不确定b2n c2n＋1 d2n－117、顺序查找法适合于存储结构为 的线性表。A）散列存储 B）顺序存储或链接存储C）压缩存储 D）索引存储18、 有一个有序表为｛1，3，9，12，32，41，45，62，75，77，82，95，100｝，当二分查找值为82的结点时， 次比较后查找成功。

A)1 B)2 C)4 D)819、 设哈希表长m=14，哈希函数H(key)二key%ll。表中已有4个结点：Addr(15)=4Addr(38)=5Addr(61)=6Addr(84)=7其余地址为空如用二次探测再散列处理冲突，关键字为49的结点的地址是 。A)8 B)3 C)5 D)920、 直接插入排序和冒泡排序的时间复杂度为D。A)O(n) B)O(lbn)C)O(nlbn)D)O(n2)21、排序的方法有多种，—法从未排序序列中依次取出元素与已排序序列(初始时为空)中元素作比较，将其放入已排序序列中的正确位置上；_D—法从未排序序列中挑选元素，并将其依次放入已排序序列的一端；_K_法对序列中相邻元素进行一系列比较，当被比较的两个元素逆序时就进行交换。C)快速排序D)选择排序A)C)快速排序D)选择排序oD)122、 对noD)1C)0A)n B)n—C)0A)(80，45，55，40，42，85)B)(85，80，55，40，42，45)C)(85，80，A)(80，45，55，40，42，85)B)(85，80，55，40，42，45)C)(85，80，55，45，42，40)D)(85，55，80，42，45，40)24、用某种排序方法对线性表(25，84，21，47，15，27，68，35的变化情况如下:1(25，84，21，47，15，27，68，35，20)2(20，15，21，25，47，27，68，35，84)3(15，20，21，25，35，27，47，68，84)4(15，20，21，25，27，35，47，68，84)快速排序法D)堆排序法C)20)进行排序时，元素序列则所采用的排序方法是—。A)插入排序法 B)选择排序法25、经过以下栈运算后，x的值为()。InitStack(S);Push(S,a);GetTop(S,x);Push(S,b);Pop(S,x);A)aB)bC)0 D)1二、填空1．当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用 存储结构。线性表・=(al,a2,…,an)用数组表示，假定删除表中任一元素的概率相同，则删除一个元TOC\o"1-5"\h\z素平均需要移动元素的个数是 。在一个长度为n的顺序表中第i个元素(l〈=i〈=n)之前插入一个元素时，需向后移动 个元素。顺序映像方法把逻辑上 的数据元素存储在物理位置上相邻的存储单元中。在有n个元素的顺序表中删除一个元素时所需移动元素的平均次数为 。对于一个具有n个结点的单链表，在已知的结点*卩后插入一个新结点的时间复杂度为 ,在给定值为x的结点后插入一个新结点的时间复杂度为 。根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成 ；而又根据指针的连接方式，链表又可分成 和 。在双向循环链表中，向p所指的结点之后插入指针f所指的结点，其操作是

9．链接存储的特点是利用 来表示数据元素之间的逻辑关系。10、 设双向循环链表中结点的数据域、前驱和后继指针域分别为data,pre和next,试写出在指针p所扌旨结点之前插入一s结点的语句是 、 、 、 。一个数据结构在计算机中的表示（映象）称为数据的 •。线性表中 称为线性表的长度。11、 3个结点可构成 棵不同形态的树。12、树有三种常用的存储结构。即 ，孩子链表法和孩子兄弟链表法。13、 有105个结点的完全二叉树有 叶子结点。TOC\o"1-5"\h\z14、具有100个结点的完全二叉树的深度为 。15、在有n个叶子结点的哈夫曼树中，总结点数是 。16、以｛1,2,4,5,6,8,9｝作为叶子结点的权值所构造的哈夫曼树的带权路径长度是 。17、二分查找（折半查找）的存储结构仅限于 且是 。18、在分块查找方法中，首先查找 ，然后再查找相应的 。19、假设在有序线性表A[1・・20]上进行二分查找，则比较一次查找成功的结点数为 ,比较两次查找成功的结点数为 ，比较三次查找成功的结点数为 ，比较四次查找成功的结点数为 ，则比较五次查找成功的结点数为 。20、长度为7的有序表的折半查找判定树的高度为 。三、应用题1、 一棵树的先序序列和后序序列分别如下，画出该树。先序序列：ABCDEFGHIJKLMN后序序列：CDEBHIGKMLNJFA2、 已知一棵二叉树的先序和中序序列，求该二叉树的后序序列。前序序列：A，B，C， D， E， F，G， H， I， J中序序列：C，B，A， E， F， D，I， H， J， G3、 对于右侧的无向图，⑴写出它的邻接矩阵表示。⑵写出它的邻接表表示。⑶根据⑴中的邻接矩阵表示，写出从顶点2出发进行DFS的顶点访问序列，以及相应的DFS生成树。⑷根据⑵中的邻接表表示，写出从顶点5出发进行BFS的顶点访问序列，以及相应的BFS生成树。4、 利用普里姆算法和克鲁斯卡尔算法求右侧连通网的最小生成树。125、求下图的拓扑序列，以及从顶点1到其它各顶点的最短路径。

126、对于给出的下面无向图求：每个顶点的度：图的邻接矩阵；图的邻接链表。®® ®7、 请写出对下图按深度优先搜索和广度优先搜索从顶点①出发遍历图的结果。8、什么是拓扑排序？对下图试写出一种拓扑排序的序列。

9、用迪杰斯特拉算法，求下图中从顶点①到其他各顶点的最短路径。要求写出：（1）图的带权邻接矩阵；（2）集合S到dist的变化过程；（3）从顶点①到其余各顶点的最短路径和最短路径长度。10、设有一组关健字｛19,01,23,14,55,20,84,27,68,11,10，77｝，所用哈希函数为H（ki）=kiMOD13采用开放地址法的线性探测再散列方法解决冲突，试在0〜18的散列地址空间中对该关键字序列构造哈希表。11、依次将元素A,C,D,B插入一个初始状态为空的链栈中,试画出所有插入完成之后的链栈。14、有向图的邻接表:15、用快速排序法对（18，5，23，40，13，9）排序，要求写出每趟的结果。

16、试按表(10,8,9,12,20,5,6,15,19,25)中元素的排列次序,将所有元素插入一棵初始为空的二叉排序树中,使之仍是一棵二叉排序树。(1)试画出插入完成之后的二叉排序树；(2)若查找元素17,它将依次与二叉排序树中哪些元素比较大小?17、 给定30个字符组成的电文:DDDDDAAABEEAAFCDAACABBCCCBAADD,试设计赫夫曼树并为每个字符设计编码。18、 找出下面网的最小生成树。19、 对于查找表｛40,28,16,56,50,32，30，63｝,试依次插入记录生成一棵二叉排序树。20、 对于关键字序列(42,23,12,55,4,54,6,65),假定哈希函数H(key)=keyMOD7,哈希表长度为10,⑴使用线性探测再散列构造哈希表；⑵使用二次探测再散列构造哈希表；21、 已知序列(45,87,12,56,67,6,90,39,83),采用快速排序法排序,写出每一趟的结果。22、 判别以下序列是否为堆,如果不是,则把它调整成堆。(150,86,48, 73, 35, 39, 42, 57, 66,22)(120,70,33, 65, 24, 56, 48, 92, 86,30)23、 已知关键字序列为(46,74,16,53,14,26,40,38,86,65,27,34)⑴利用直接插入排序法写出每趟排序后的结果；⑵利用快速排序法写出每次划分后的结果和最后结果；⑶利用简单选择排序法写出每趟排序后的结果；⑷利用归并排序法写出每趟排序后的结果。24、 对关键字序列(20,35,12,41,5,8,61,27)构造哈希表。其中哈希函数H(key)=keyMOD7,哈希表长度为10,处理冲突用线性探测再散列方法。25、 对关键字序列(20,35,12,41,5,8,61,27)构造哈希表。其中哈希函数H(key)=keyMOD7,哈希表长度为10,处理冲突用线性探测再散列方法。26、 设输入序列为a,b,c,d,试写出借助一个栈可得到的两个输出序列和两个不能得到的输出序列。27、 假设循环队列Q的存储空间长度是MAXQSIZE，试分别写出判断Q满的条件和空的条件。28、 按照权值｛45,8,21,4｝构造赫夫曼树，并计算其WPL。29、 把下面的树转化为对应的二叉树,并写出该二叉树的后序序列。

31、写出下列AOV网的两个拓扑序列。32、 对关键字序列(20,35,12,41,5,8,61,27)构造哈希表。其中哈希函数H(key)=keyMOD7，哈希表长度为10，处理冲突用线性探测再散列方法。33、 假设某查找表的关键字序列为(24,13,77,30,53,20),按此顺序构造二叉排序树。34、 用快速排序方法对下列数据进行从小到大排序,要求写出每次划分后的结果和最后结果。[23,54,42,13,86,2,33]35、 假设一棵二叉树的中序序列为DCBGEAHFIJK、后序序列为DCEGBFHKJIA,请画出该树。四、算法设计题1、写出折半查找的算法。intSearch_Bin(SSTableST,KeyTypeK){low=0;high=ST.length; //确定初始查找区间while(low<=high){m=(low+high)/2;//计算区间的中点if(EQ(K,ST.elem[m].key))returnm; //相等if(LT(K,ST.elem[m].key))high=m-1; //K小elselow=m+1; //K大}return0;//查找失败}//Search_Bin2、设二又树采用二叉链表表示，设计算法求此二叉树中度为1(0)的结点的个数。intGetCount(BiTreeT){if(T==NULL)return0;if(T->lchild==NULL||(&&)T->lchild==NULL)returnGetCount(T)+1;}//GetCountvoidPreOrderTraverse(BiTreeT){if(T==NULL)return;if(T->lchild==NULL||(&&)T->rchild==NULL)GetCount;PreOrderTraverse(T->lchild);PreOrderTraverse(T->rchild);}//PreOrderTraverse3、顺序表的插入和删除算法。StatusListInsert_Sq(SqList&L,inti,ElemTypee){//在顺序表L中第i个位置之前插入元素e//i的合法值为1WiWListLength(L)+lif(i<1||i>L.length+1)returnERROR;for(j=L.length;j>=i;j--)L.elem[j]=L.elem[j-1]; //后移元素L.elem[i-1]=e;L.length++;returnOK;}//ListInsert_SqStatusListDelete_Sq(SqList&L,inti,ElemType&e){if(i<1||i>L.length)returnERROR;e=L.elem[i-1];for(j=i;j<L.length;j++)L.elem[j-1]=L.elem[j];//前移元素L.length--;returnOK;}//ListDelete_Sq4、 若二叉树中各结点的值均为整数，以二叉链表为存储结构，编写算法输出二叉树中值大于0的所有结点。voidvisit(ElemTypee){if(e>0)printf(e);}voidPreOrderTraverse(BiTreeT){if(T==NULL)return;visit(T->data);PreOrderTraverse(T->lchild);PreOrderTraverse(T->rchild);}//PreOrderTraverse5、 单链表的插入和删除算法。StatusListInsert_L(LinkList&L,inti,ElemTypee){if(i<1)returnERROR;//位序合法性检查p=L;j=0;while(p!=NULL&&j〈i-l){ //查找第iT结点p=p->next;j++;}if(p==NULL)returnERROR; //查找第i-1结点失败s=(LNode*)malloc(sizeof(LNode)); //生成新结点if(s==NULL)returnERROR;s->data=e;s->next=p->n