第1章:绪论(时长:56分11秒)

第1周测验

1、计算机所处理的数据一般具备某种内在联系,这是指( )。
    A、数据和数据之间存在某种关系
    B、元素和元素之间存在某种关系
    C、元素内部具有某种结构
    D、数据项和数据项之间存在某种关系

2、在数据结构中,与所使用的计算机无关的是数据的( )结构。
    A、逻辑
    B、存储
    C、逻辑和存储
    D、物理

3、在计算机中存储数据时,通常不仅要存储各数据元素的值,而且还要存储( )。
    A、数据的处理方法
    B、数据元素的类型
    C、数据元素之间的关系
    D、数据的存储方法

4、数据结构在计算机内存中的表示是指( )。
    A、数据的存储结构
    B、数据结构
    C、数据的逻辑结构
    D、数据元素之间的关系

5、数据在计算机的存储器中表示时,逻辑上相邻的两个元素对应的物理地址也是相邻的,这种存储结构称之为( )。
    A、逻辑结构
    B、顺序存储结构
    C、链式存储结构
    D、以上都对

6、数据采用链式存储结构时,要求( )。
    A、每个节点占用一片连续的存储区域
    B、所有节点占用一片连续的存储区域
    C、节点的最后一个域必须是指针域
    D、每个节点有多少后继节点,就必须设多少个指针域

7、可以用( )定义一个完整的数据结构。
    A、数据元素
    B、数据对象
    C、数据关系
    D、抽象数据类型

8、算法指的是( )。
    A、计算机程序
    B、解决问题的方法
    C、查找或排序过程
    D、求解特定问题的指令有限序列

9、在算法设计时,若实参和形参同步发生改变,则应把形参变量说明为( )型参数。
    A、指针
    B、引用
    C、传值
    D、常数

10、某算法的时间复杂度为O(),表明该算法的( )。
    A、问题规模是
    B、执行时间等于
    C、执行时间与成正比
    D、问题规模与成正比

第1章.绪论(作业)

1、有以下用C/C++语言描述的算法,说明其功能: void fun(double &y,double x,int n) { y=x; while (n>1) { y=y*x; n--; } }

2、一个算法的空间复杂度是O(1),那么执行该算法时不需要任何空间,这个说法正确吗?为什么?

3、一个算法的执行频度为,其时间复杂度多少?

4、设有算法如下: int Find(int a[], int n, int x) { int i; for (i=0;i<n;i++ ) if (a[i]==x) return i; return –1; } 成功找到x的最好和最坏时间复杂度是多少?

5、设有算法如下: int Find(ElemType a[ ],int s,int t,ElemType x) { int m=(s+t)/2; if (s<=t) { if (a[m]==x) return m; else if (x<a[m]) return Find(a,s,m-1,x); else return Find(a,m+1,t,x); } return -1; } 分析执行Find(a,0,n-1,x)的时间复杂度。

第2章:线性表(上)(时长:1小时3分56秒)

第2章.线性表A(作业)

1、设计一个算法,查找非空顺序表L中第一个最大的元素,并返回该元素的逻辑序号。

2、对于带头节点的单链表L1,其节点类型为LinkList,指出以下算法的功能。 void fun(LinkList *&L,ElemType x,ElemType y) { LinkList *p=L->next; while (p!=NULL) { if (p->data==x) p->data=y; p=p->next; } }

3、以下算法用于统计带头节点的单链表L中节点值等于给定值x的节点数的算法,其中存在错误,请指出错误的地方并修改为正确的算法。 int count(LinkList *L,ElemType x) { int n=0; while (L!=NULL) { L=L->next; if (L->data==x) n++; } return n; }

4、某非空单链表L中所有元素为整数,设计一个算法将所有小于零的节点移到所有大于等于零的节点的前面。

5、有一个由整数元素构成的非空单链表A,设计一个算法,将其拆分成两个单链表A和B,使得A单链表中含有所有的偶数节点,B单链表中含有所有的奇数节点,且保持原来的相对次序。

第2章:线性表(下)(时长:41分40秒)

第3章.线性表B(作业)

1、以L为头节点指针,给出单链表、双链表、循环单链表和循环双链表中,p所指节点为尾节点的条件。

2、有一个双链表L,设计一个算法计算其中值为x的节点个数。

3、有一个非空双链表L,设计一个算法删除第一个值为x的节点。

4、设计一个算法,求一个非空循环单链表L中最后一个最大节点的逻辑序号。

5、对于有n(n≥1)个节点的循环单链表L,假设所有节点值是递增有序的,设计一个算法就地删除所有值重复的节点。

6、用带头节点单链表表示集合,假设该单链表中的元素递增有序,设计一个高效算法求两个集合的交集,并分析该算法的时间和空间复杂度。

第3&4章:栈和队列(时长:1小时4分4秒)

第4章.栈#队列(作业)

1、设输入元素为1、2、3、P和A,进栈次序为123PA,元素经过栈后到达输出序列,当所有元素均到达输出序列后,有哪些序列可以作为高级语言的变量名?

2、在以下几种存储结构中,哪个最适合用作链栈?并说明理由。 (1)带头节点的单链表 (2)不带头节点的循环单链表 (3)带头节点的双链表

3、简述以下算法的功能: void fun(int a[],int n) { int i=0,e; SqStack *st; InitStack(st); for (i=0;i<n;i++) Push(st,a[i]); i=0; while (!StackEmpty(st)) { Pop(st,e); a[i++]=e; } DestroyStack(st); }

4、假设表达式中允许包含3种括号:圆括号、方括号和大括号。设计一个算法采用顺序栈判断表达式中的括号是否正确配对。

5、假设以I和O分别表示入栈和出栈操作,栈的初态和终态均为空,进栈和出栈的操作序列可表示为仅由I和O组成的序列。15 (1)下面所示的序列中哪些是合法的? A.IOIIOIOO B.IOOIOIIO C.IIIOIOIO D.IIIOOIOO (2)通过对(1)的分析,写出一个算法判定所给的操作序列是否合法。若合法返回true;否则返回false(假设被判定的操作序列已存入一维数组中)。

6、以1、2、3、…、n的顺序进队,可以产生的出队序列有多少种?

7、什么是循环队列?采用什么方法实现循环队列?

8、链队相对于顺序队而言,有何优势和不足?

9、对于循环队列,设计求其中元素个数的算法。

10、对于顺序队来说,如果知道队尾元素的位置和队列中的元素个数,则队头元素所在位置显然是可以计算的。也就是说,可以用队列中的元素个数代替队头指针。设计出这种循环顺序队的初始化、入队、出队和判空算法。

第5章:数组和稀疏矩阵(时长:34分56秒)

第5章.数组(作业)

1、为什么数组极少使用链式结构存储?

2、设有一个C/C++二维数组A[m][n],假设A[0][0]存放位置在644,A[2][2]存放位置在676,每个元素占1个字符,问A[3][3]存放在什么位置?

3、如果某个一维数组A的元素个数n很大,存在大量重复的元素,且所有元素值相同的元素紧跟在一起,请设计一种压缩存储方式使得存储空间更节省,并通过一个示例进行说明。

4、特殊矩阵和稀疏矩阵哪一种压缩存储后失去随机存取的功能?为什么?

5、用十字链表表示一个有k个非零元素的m×n的稀疏矩阵,则其总的节点数为多少?

第6章:树和二叉树(上)(时长:57分37秒)

第6章.树(作业)

1、若一棵度为4的树中度为1、2、3、4的节点个数分别为4、3、2、2,则该树的总节点个数是多少?

2、对于度为m的树T,其高度为h,则最少的节点个数和最多的节点个数分别是多少?

3、对于含有n个节点的m次树,采用孩子链存储结构时,其中空指针域的个数有多少?

4、任意一个有n个节点的二叉树,已知它有m个叶子节点,试证明有(n-2m+1)个度数为1的节点。

5、为什么说一棵非空完全二叉树,一旦节点个数n确定了,其树形也就确定了。

6、已知一棵完全二叉树的第6层(设根为第1层)有8个叶子节点,则该完全二叉树的节点个数最多是多少?

7、假设非空二叉树采用顺序存储结构,每个节点值为单个字符。设计一个算法求编号为i的节点的层次。

8、假设非空二叉树采用顺序存储结构,每个节点值为单个字符。设计一个算法输出编号为i的节点的所有祖先节点值。

第6章:树和二叉树(下)(时长:57分24秒)

第9周作业

1、若某非空二叉树的先序序列和后序序列正好相同,则该二叉树的形态是什么?

2、一棵二叉树的先序、中序和后序序列分别如下,其中有一部分未显示出来。试求出空格处的内容,并画出该二叉树。 先序序列: B F ICEH G 中序序列:D KFIA EJC 后序序列: K FBHJ G A

3、一棵二叉树采用二叉链存储结构b表示,所有节点值均不相同,有以下算法: int fun(BTNode *b) { int num1,num2,n; if (b==NULL) return 0; else if ((b->lchild==NULL && b->rchild!=NULL) || (b->lchild!=NULL && b->rchild==NULL)) n=1; else n=0; num1=fun(b->lchild); num2=fun(b->rchild); return (num1+num2+n); } (1)指出fun(b)算法的功能。 (2)当二叉树b的括号表示为" A(B(D(,G)),C(E,F))"时,执行fun(b)后其返回结果是什么?

4、给出在中序线索二叉树中查找节点p的后继节点的过程。

5、如果一棵哈夫曼树T中共有255个节点,那么该树用于对几个字符进行哈夫曼编码?

6、假设二叉树中每个节点值为单个字符,采用二叉链存储结构存储。设计一个算法void findparent(BTNode *b,char x,BTNode *&p)求二叉树b中指定值为x的节点的双亲节点p,提示:根节点的双亲为NULL,若在b中未找到值为x的节点,p亦为NULL,并假设二叉树中所有节点值是唯一的。

7、假设二叉树中每个节点值为单个字符,采用二叉链存储结构存储。设计一个算法求二叉树b的最小枝长。所谓最小最小枝长是指的是根节点到最近叶子节点的路径长度。

8、假设二叉树中每个节点值为单个字符,采用二叉链存储结构存储。设计一个算法,求二叉树b中第k层(根节点的层次为1)上节点个数。

9、假设二叉树中每个节点值为单个字符,采用二叉链存储结构存储。设计一个算法,输出二叉树b中第k层(根节点的层次为1)上的所有叶子节点。

10、假设二叉树中每个节点值为单个字符,采用二叉链存储结构存储。设计一个算法,判断值为x的节点与值为y的节点是否互为兄弟,假设这样的节点值是唯一的。

第7章:图(上)(时长:54分56秒)

第10周作业

1、一个图有7个顶点,编号为0~6,其邻接矩阵如下: 回答以下问题: (1)画出该有向图。 (2)求顶点0的入度和出度。 (3)求顶点2的度。

2、对n个顶点的有向图G,采用邻接表存储,请回答下列有关问题: (1)如何求图中的边数? (2)如何判断顶点i到顶点j是否有边相连? (3)如何求任意一个顶点i的入度?

3、对于稠密图和稀疏图,采用邻接矩阵和邻接表哪个更好些?

4、假设不带权有向图G采用邻接矩阵存储,设计一个算法求出图G中每个顶点的入度。

5、假设图G采用邻接矩阵存储。给出图的广度优先遍历算法,并分析算法的时间复杂度。

6、假设一个无向图是非连通的,采用邻接表作为存储结构。设计一个算法,利用深度优先遍历方法求出该图连通分量个数。

7、假设一个连通图采用邻接表作为存储结构,试设计一个算法,判断其中是否存在经过顶点v的回路。

8、假设图G采用邻接表存储,设计一个算法,从如下图所示的无向图G中找出满足如下条件的一条路径: (1)给定起点u和终点v。 (2)给定一组必经点{1,6},即输出的路径必需包含这些顶点。 (3)给定一组必避点{7,9},即输出的路径不能包含这些顶点。

第7章:图(下)(时长:1小时11分59秒)

第11周作业

1、如果一个带权连通图中存在3条权值最小的边,那么3条边一定都包含在所有最小生成树中吗?说明理由。

2、对于如下图所示的带权无向图,给出利用普里姆算法(从顶点0开始构造)和克鲁斯卡尔算法构造出的最小生成树的结果(按求出边的顺序给出结果)。

3、对于如下图所示的带权有向图,采用狄克斯特拉算法求出从顶点0到其他各顶点的最短路径及其长度。

4、设下图中的顶点表示村庄,有向边代表交通路线,若要建立一家医院,采用弗洛伊德算法求建在哪一个村庄能使各村庄总体交通代价最小。

5、给出如下图所示有向图的所有拓扑序列。

6、可以对一个有向图的所有顶点重新编号,把所有表示边的非0元素集中到邻接矩阵的上三角部分。根据什么顺序对顶点进行编号?

7、已知有6个顶点(顶点编号为0~5)的有向带权图G,其邻接矩阵A为上三角矩阵,按行为主序(行优先)保存在如下的一维数组中: 要求: (1)写出图G的邻接矩阵A。 (2)画出有向带权图G。 (3)求图G的关键路径,并计算该关键路径的长度。

8、假设图采用邻接矩阵存储。修改Dijkstra算法,仅求从顶点u到顶点v的最短路径及其长度。

第9章:查找(时长:1小时34分51秒)

第12周作业

1、若单链表的节点是按数据域升序链接的,是否适合用折半查找法进行查找,为什么?

2、将二叉排序树T的先序序列中的关键字依次插入到一棵空的二叉排序树中,所得到的二叉排序树T'与T是否相同?为什么?

3、和二叉排序树查找相比,平衡二叉树查找的优缺点各是什么?

4、哈希表查找的时间性能在什么情况下可以达到O(1)?

5、设有一组关键字{19,1,23,14,55,20,84,27,68,11,10,77} 其哈希函数如下: h(key)=key % 13 采用开放地址法的线性探测法解决冲突,试在0~18的哈希表中对该关键字序列构造哈希表,并求在成功和不成功情况下的平均查找长度。

6、若有一个无序顺序表R1和递增有序顺序表R2,它们均含有n个元素,且可能存在相同关键字的元素。设计两个算法分别输出R1和R2中第一个关键字为k的元素位置,并分析成功查找的平均查找长度。

7、一个长度为L(L≥1)的升序序列S,处在第éL/2ù个位置的数称为S的中位数。 例如:若序列S1=(11,13,15,17,19),则S1的中位数是15。 两个序列的中位数是含它们所有元素的升序序列的中位数。 例如,若S2=(2,4,6,8,20),则S1和S2的中位数是11。 现有两个等长升序序列A和B,设计一个算法采用折半查找方法找出两个序列A和B的中位数。说明你所设计算法的时间复杂度和空间复杂度。

8、设计一个递归算法,从大到小输出二叉排序树中所有其值不小于k的关键字。

第8章:内排序(时长:1小时21分4秒)

第13周作业

1、直接插入排序算法在含有n个元素的初始数据正序、反序和数据全部相等时,时间复杂度各是多少?

2、回答以下问题: (1)使用折半插入排序所要进行的关键字比较次数,是否与待排序的元素的初始状态有关? (2)在一些特殊情况下,折半插入排序比直接插入排序要执行更多的关键字比较,这句话对吗?

3、有以下关于排序的算法: void fun(int a[],int n) { int i,j,gap,tmp; gap=n/3; while (true) { for (i=gap;i<n;i++) { tmp=a[i]; j=i-gap; while (j>=0 && tmp<a[j]) { a[j+gap]=a[j]; j=j-gap; } a[j+gap]=tmp; } if (gap==1) break; else if (gap<3) gap=1; else gap=gap/3; } } (1)指出fun(a,n)算法的功能。 (2)当a[]={5,1,3,6,2,7,4,8}时,问fun(a,8)共执行几趟排序,各趟的排序结果是什么?

4、将快速排序算法改为非递归算法时通常使用一个栈,若把栈换为队列会对最终排序结果有什么影响?说明理由。

5、请回答下列关于堆排序中堆的一些问题: (1)通常堆的存储表示是顺序还是链式的? (2)设有一个小根堆,即堆中任意节点的关键字均小于它的左孩子和右孩子的关键字。其中具有最大关键字的节点可能在什么地方?

6、二路归并排序中每一趟排序都要开辟O(n)的辅助空间,共需éù趟排序,为什么总的辅助空间仍为O(n)?

7、基数排序过程通常用单链表存放排序的元素,为什么不用顺序表来存放排序的元素?

8、有一种简单的排序算法,叫做计数排序。这种排序算法对一个待排序的表(用数组表示)进行排序,并将排序结果存放到另一个新的表中。必须注意的是,表中所有待排序的关键字互不相同,计数排序算法针对表中的每个元素,扫描待排序的表一趟,统计表中有多少个元素的关键字比该元素的关键字小。假设对某一个元素,统计出该数值为c,那么这个元素在新的有序表中的合适的存放位置即为c。 (1)设计实现计数排序的算法。 (2)对于有n个元素的表,比较次数是多少? (3)与简单选择排序相比,哪种方法是否更好?为什么?