各章习题汇总

1、数据结构习题汇总 第 一 章 1、下面程序段的时间复杂度为_。 for(int i=0; im; i+) for(int j=0; jn; j+) aij=i*j; A、 O(m2) B、 O(n2) C、 O(m*n) D、 O(m+n) 执行下面程序段时，执行S语句的次数为_。 for(int i=1; i=n; i+) for(int j=1; j0）。 A表元素 B字符 C数据元素 D数据项 E信息项 4若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ a ）存储方式最节省时间。 A顺序表 B双链表 C带头结点的双循环链表 D单循环链表 5、某线性表中

2、最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ d ）存储方式最节省运算时间。 A单链表 B仅有头指针的单循环链表 C双链表 D仅有尾指针的单循环链表 6、在双向链表指针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

3、;q-Rlink=q;p-Llink=q;p-Llink=q; 7、对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（ ） Ahead=NULL Bheadnext=NULL Cheadnext=head Dhead!=NULL 1、设单链表的结点结构为(data,next)，next为指针域，已知指针px指向单链表中data为x的结点，指针py指向data为y的新结点 , 若将结点y插入结点x之后，则需要执行以下语句:_； 2在一个长度为n的顺序表中第i个元素（1=inext=null; B表的初始化。 LinkedList ra,rb;ra和rb将分别指向将创建的A表和B

4、表的尾结点。 ra=A;rb=B;p=A-next; p为链表工作指针，指向待分解的结点。A-next=null; 置空新的A表while(p!=null) r=p-next; 暂存p的后继。 i+; if(i%2=0) 处理原序号为偶数的链表结点。p-next=rb-next;在B表尾插入新结点； rb-next=p; rb=p;rb指向新的尾结点； else处理原序号为奇数的结点。 p-next=ra-next; ra-next=p; ra=p; p=r; 将p恢复为指向新的待处理结点。 用类用类c的语言写出链式存储条件下，删除的语言写出链式存储条件下，删除单链表单链表L中值大于中值大于m

5、ax小于小于min的算法：的算法：Delete(L,max,min)Delete(L,max,min) p1=L; p2=p1-next; while(p2) if(p2-datamax|p2-datanext=p2-next; free(p2); p2=p1-next; else p1=p2; p2=p2-next; 第 三 章 1、对于栈操作数据的原则是（ ）. A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序 2. 在作进栈运算时,应先判别栈是否( ),在作退栈运算时应先判别栈是否( )。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为( )。 , : A.

6、空 B. 满 C. 上溢 D. 下溢 : A. n-1 B. n C. n+1 D. n/2 3. 一个栈的输入序列为123n，若输出序列的第一个元素是n，输出第i（1=i=n）个元素是（ ）。 A. 不确定 B. n-i+1 C. i D. n-i 4. 若一个栈的输入序列为1,2,3,n，输出序列的第一个元素是i，则第j个输出元素是（ ）。 A. i-j-1 B. i-j C. j-i+1 D. 不确定的 5. 若已知一个栈的入栈序列是1,2,3,n，其输出序列为p1,p2,p3，pN,若pN是n，则pi是( )。 A. i B. n-i C. n-i+1 D. 不确定 简述下列算法的简述

7、下列算法的 功能：功能： algo(Stack S) int i,n,a255; n0; while(!StackEmpty(S)n+;Pop(S,an); For(i=1;idata); /出队,访问结点 if(p-lchild & !p-rchild |!p-lchild & p-rchild) num+; /度为1的结点 if(p-lchild) QueueIn(Q,p-lchild); /非空左子女入队 if(p-rchild) QueueIn(Q,p-rchild); /非空右子女入队 /if(bt) return(num); /返回度为1的结点的个数 假设二叉树采用

8、二叉链表存储结构，设计一个非假设二叉树采用二叉链表存储结构，设计一个非递归算法求二叉树的高度。递归算法求二叉树的高度。 int Depth (BiTree T ) / 返回二叉树的深度 if ( !T ) depthval = 0; else depthLeft = Depth( T-lchild ); depthRight= Depth( T-rchild ); depthval = 1 + (depthLeft depthRight ? depthLeft : depthRight); return depthval; 非递归算法的思想非递归算法的思想： 采用分层遍历二叉树的方法，使用一个

9、队采用分层遍历二叉树的方法，使用一个队列列qu和一个整数数组和一个整数数组level，它们使用相，它们使用相同的下标，后者存储对应结点在二叉树中同的下标，后者存储对应结点在二叉树中的层次。最大的层次就是二叉树的深度。的层次。最大的层次就是二叉树的深度。 Int Depth(BTree *T) int m,max,rear,front,levelMaxSize; BTree *quMaxSize ,*p; /循环队列 max=0;rear=0;front=0; rear+;qurear=T;levelrear=1;/根结点入队 while(front!=rear) front=(front+1)

10、%maxsize;/出队列 p=qufront;m=levelfront; if(mmax) max=m; if(p-lchild!=NULL) rear=(rear+1)%Maxsize； /左孩子入队 qurear=p-lchild; levelrear=m+1;/子女层次加1 if(p-rchild!=NULL) rear=(rear+1)%Maxsize； /右孩子入队 qurear=p-rchild; levelrear=m+1;/子女层次加1 return max; 第 七 章习题习题 1、已知图、已知图G（V，E），其中），其中Va，b，c，d，e，f，g，E, , , , ,，

11、请画出图，请画出图G，并写出其邻，并写出其邻接矩阵和邻接表表示接矩阵和邻接表表示. 2、已知无向图的邻接表如下图：、已知无向图的邻接表如下图： 画出该无向图。画出该无向图。 根据邻接表分别写出用根据邻接表分别写出用DFS和和BFS算算 法从顶点法从顶点v0开始遍历该图后得到的遍历开始遍历该图后得到的遍历 序列。序列。 2、 2、作业作业 画出下图的拓扑排序序列：画出下图的拓扑排序序列：ahkahkcdefcfed 对于下面的对于下面的AOE网：网： 1、求出各个事件的最早发生时间和最晚、求出各个事件的最早发生时间和最晚发生时间，并回答完成整个工程最少需发生时间，并回答完成整个工程最少需要多少时

12、间？要多少时间？ 2、计算各个活动的最早开始时间和最迟、计算各个活动的最早开始时间和最迟开始时间，并找出所有的关键活动和关开始时间，并找出所有的关键活动和关键路径。键路径。v0v1v3v2v4v5v6v7v8v93585644 27365893第 九 章 1以顺序查找方法从长度为n的线性表中查找一个元素时，平均查找长度为_，时间复杂度为_。 2以二分查找方法查找一个线性表时，此线性表必须是_存储的_表。 5从有序表(12,18,30,43,56,78,82,95)中依次二分查找43和56元素时，其查找长度分别为_和_。 7假定对长度n=50的有序表进行二分查找，则对应的判定树高度为_，判定树中

13、前5层的结点数为_，最后一层的结点数为_。 8在索引表中，每个索引项至少包含有_域和_域这两项。 作业作业 、在关键字序列、在关键字序列(07，12，15，18，27，32，41，92)中用二分查找法查找和给定值中用二分查找法查找和给定值92相等的关键字，请写出查找过程中依次相等的关键字，请写出查找过程中依次和给定值和给定值“92”比较的关键字（以图示标明比较的关键字（以图示标明）。）。 作业作业 2、画出对长度为的有序表进行折半查、画出对长度为的有序表进行折半查找的一棵判定树，并求其等概率查找时查找的一棵判定树，并求其等概率查找时查找成功的平均查找长度找成功的平均查找长度 3.3.已知如下所

14、示长度为已知如下所示长度为1212的列表的列表(Jan,Feb,Mar,Apr,May,June,July,Aug,(Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec)Sep,Oct,Nov,Dec) (1)(1)试按表中元素的顺序依次插入一棵初试按表中元素的顺序依次插入一棵初始为空的二叉排序树始为空的二叉排序树, ,请画出插入完成后请画出插入完成后的二叉排序树的二叉排序树. . (2)(2)若对表中元素先进行排序构成有序表若对表中元素先进行排序构成有序表, ,求在等概率情况下对此表进行折半查找求在等概率情况下对此表进行折半查找成功的平均查找长

15、度成功的平均查找长度. . 4.4.线性表的关键字集合为线性表的关键字集合为78,25,13,80,72,140,68,59,123,7,36,78,25,13,80,72,140,68,59,123,7,36,74,74,共有共有1212个元素个元素, ,已知散列函数为已知散列函数为H(k)=k%12,H(k)=k%12,采用链地址法处理冲突采用链地址法处理冲突, ,试在试在0 01111的散列空间中对该关键字序列构造的散列空间中对该关键字序列构造哈希表哈希表第 十 章 设用希尔排序对数组98，36，-9，0，47，23，1，8，10，7进行排序，给出的步长（也称增量序列）依次是4，2，1则

16、排序需_趟，写出第一趟结束后，数组中数据的排列次序_。 对关键字序列对关键字序列(52，80，63，44，48，91)进行一趟快速排序之后得到的结果为进行一趟快速排序之后得到的结果为_。 对于以下关键字序列（对于以下关键字序列（52, 49, 80, 36, 14, 58, 61, 97, 23, 75）写出进行一趟快速排序）写出进行一趟快速排序的过程（写明步骤）。的过程（写明步骤）。 已知一组元素的排序码为(49，38，65，97，76，13，27，49) (1) 利用直接插入排序的方法写出每次向前面有序表插入一个元素后的排列结果。 (2) 利用堆排序的方法写出在构成初始堆和利用堆排序的过程

17、中，每次筛运算后的排列结果，并画出初始堆所对应的完全二叉树。 (3) 利用快速排序的方法写出每一层划分后的排列结果。 (4) 利用归并排序的方法写出每一趟二路归并排序后的结果。 （1） （49）38 65 97 76 13 27 49 38（38 49）65 97 76 13 27 49 38（38 49 65）97 76 13 27 49 38（38 49 65 97）76 13 27 49 76（38 49 65 76 97）13 27 49 13（13 38 49 65 76 97）27 49 27（13 27 38 49 65 76 97）49 49（13 27 38 49 49 65 76 97） （2） 97 76 65 49 49 13 27 38 76 49 65 38 49 13 27 97 65 49 27 38 49 13 76 97 49 49 27 38 13 65 76 97 49 38 27 13 49 65 76 97 38 13 27 49 49 6