数据结构-卢永艳（31100083-01）答案-中国大学慕课
第一章 绪论（总时长：56分26秒，共6讲）
第1讲 数据结构的基础概念（总时长12分钟）随堂测验
1、一个抽象类型包括数据对象、 和一组处理数据的操作。
A、数据对象中各元素间的结构关系
B、数据元素集
C、接口
D、数据对象集
2、抽象数据类型具有 、信息隐蔽的特点。
第2讲 数据结构的内容（总时长5分29秒）随堂测验
1、线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。（ ）
2、1、数据结构的逻辑结构分为集合、线性、层次和 四种。
3、2、数据结构的存储结构分为 和非顺序 两种。
4、3、在线性结构、树形结构和图结构中，数据元素之间分别存在着一对一、一对多和 联系。
第3讲 数据结构与c语言表示（总时长7分32秒）随堂测验
1、当需要用一个形式参数直接改变对应实参的值时，该形式参数应说明为 。
A、与实参同类型指针参数
B、不需要参数
C、与实参同类型的参数
D、全局变量
第4讲 算法性能评价（总时长8分06秒）随堂测验
1、1、执行下面的程序段的时间复杂度为 。 for(int i=0;i<m;i++) for(int j=0;j<n;j++) a[i][j]=i*j;
A、O(![]()
)
B、O(![]()
)
C、O(m*n)
D、O (m+n)
2、2、执行下面程序段时，语句S的执行次数为 。 for(int i=0;i<=n;i++) for(int j=0;j<i;j++) S;
A、![]()
B、![]()
C、n(n+1)
D、![]()
第5讲 算法与算法的描述（总时长14分59秒）随堂测验
1、算法设计的要求是：正确性、可读性 、 和高效率和低存储 。
A、确定性
B、健壮性
C、可行性
D、有限性
2、算法具有 有限性、确定性、 、输入、输出五大特性。
A、可行性
B、可读性
C、健壮性
D、正确性
MOOC第一章单元测试题
1、执行下面的程序段的时间复杂度为（ ）。 for(int i=0;i<m;i++) for(int j=0;j<n;j++) a[i][j]=i*j;
A、O(m2)
B、O(n2)
C、O(m*n)
D、O(m+n)
2、执行下面程序段时，语句S的执行次数为（ ）。 for(int i=0;i<=n;i++) for(int j=0;j<=i;j++) S;
A、n*n
B、n*n/2
C、(n+1)*(n+2)/2
D、n(n+1)/2
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、某算法的时间复杂度是O（n^2）,表明该算法的（ ）。
A、问题规模是n^2
B、问题规模与n^2正比
C、执行时间与n^2正比
D、执行时间等于n^2
9、若需要利用形式参数直接访问修改实参值，则应将形参说明为（ ）参数。
A、指针
B、值参数
C、实地址
D、地址参数
10、如下程序段: for(i=1;i<=n-1;i++) for(j=i+1;j<=n;j++) x=x+1; 其中语句x=x+1执行的语句频度为（ ）。
A、n*n
B、n*(n-1)/2
C、n*(n+1)/2
D、n*(n-1)
11、以下算法的时间复杂度为（ ）。 if (n >= 0) { for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) printf("输入数据大于等于零\n"); } else { for(int j = 0; j < n; j++) printf("输入数据小于零\n"); }
A、O(1)
B、O(n*n+n)
C、O(n)
D、O(n*n)
12、在数组A[0..n-1]中查找给定值K的算法大致如下： i=n-1; while(i>=0&&(A[i]!=k)) i--; return i; 该算法的时间复杂度为（ ）。
A、O(n-i+1)
B、O(n-i)
C、O(n)
D、无法确定
13、下面算法的时间复杂度为（ ）。 x=100; y=100; while(y>0) if(x>100) {x=x-10; y--;} else x++;
A、O(n)
B、O(100)
C、O(1)
D、O(n*n)
14、下面的算法是判断n是否为素数，其算法时间复杂度为（ ）。 void prime(int n) { 判断n是否是素数 */ for (i=2; i<sqrt(n) && (n % i)!=0; i++) ; if (i>sqrt(n)) printf("%d is a prime number", n); else printf("%d is not a prime number", n); }
A、O(n)
B、O(1)
C、O(sqrt(n)) sqrt表示对n取根方
D、O（n-i）
15、一个抽象数据类型包括（ ）。
A、数据对象
B、数据对象中各元素间的关系
C、数据
D、一组基本操作
16、以下属于数据元素间基本逻辑结构的是（ ）。
A、集合
B、线性
C、树
D、图
17、以下属于算法特性的是（ ）。
A、0个或多个输入
B、至少一个输出
C、正确性和有限性
D、可行性
18、算法设计的要求包括（ ）。
A、正确性
B、可读性
C、健壮性
D、高效率和低存储
19、数据元素在计算机的存储映像包括（ ）。
A、顺序存储
B、非顺序存储
C、图结构
D、树结构
20、具有线性结构的数据元素只能顺序存储，非线性结构的元素只能非顺序存储。
21、算法就是程序。
22、算法的优劣与算法描述的语言无关。
23、算法的可行性是指每一条指令具有明确含义。
24、健壮的算法不会因为非法输入而出现莫名的执行结果。
25、高效率和低存储是衡量一个算法的唯一标准。
26、数据类型就是一组性质相同的值的集合和在该集合上的一组操作的总称。
27、数据元素的存储结构分为顺序存储和非顺序存储。
28、数据元素的顺序存储优于非顺序存储。
29、一个数据结构在存储时，只需要存储数据元素即可。
MOOC第一章单元作业
1、计算下列程序段中x++的语句频度： x=1; for(int i = 0; i < n; i++) for(int j = i; j < n; j++) x++;
2、（1）简述数据元素间的四类基本逻辑结构。 （2）抽象数据类型定义。 （3）数据元素及其关系的两类存储结构与特点。
第二章 线性表（一）（总时长：72分22秒，共6讲）
第1讲 线性表的概念（总时长9分20秒）随堂测验
1、线性表是具有n个（ ）的有限序列（n>0）
A、数据对象
B、数据元素
C、字符
D、数据项
2、线性表是一个（ ）。
A、有限序列，可以为空
B、有限序列，不可以为空
C、无限序列，可以为空
D、无限序列，可以为空
3、线性表的特点是每个元素都有一个前驱和一个后继。（）
第2讲 线性表的顺序存储（总时长13分）随堂测验
1、若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（ ）(1<=i<=n+1)。
A、O(1)
B、O(n)
C、O(n*n)
D、O（![]()
）
2、若长度为n的线性表采用顺序存储结构，删除第i个位置的元素，需要移动的元素个数为（ ）。
A、i
B、n-i
C、n-i+1
D、n-i-1
第3讲 线性表顺序结构应用示例及小结（总时长7分57秒）随堂测验
1、对一个长度为n的顺序表，假设在任何位置上插入一个元素的概率是相等的，那么插入一个元素时要移动表中的（ ）个元素。
A、n
B、n+1
C、![]()
D、![]()
2、线性表的顺序存储是指将表中元素按照从大到小或从小到大存储。
第4讲 线性表的链式存储（总时长10分20秒）随堂测验
1、通过表达式 可以获取带头结点的单链表L中首元素结点的数据值。
A、L->next
B、(L->next)->data
C、L->data
D、L->next
2、单链表中必须设有头结点。（）
第5讲 单链表的基本运算（总时长20分58秒）随堂测验
1、下列选项中， 项是链表不具有的特点。
A、插入和删除运算不需要移动元素
B、所需要的存储空间与线性表的长度成正比
C、不必事先估计存储空间大小
D、可以随机访问表中的任意元素
2、有一个带头结点的单链表HEAD，则判断其是否为空链表的表达式是
A、HEAD= =NULL
B、HEAD-〉NEXT= =NULL
C、HEAD-〉NEXT= =HEAD
D、HEAD！=NULL
3、在一个单链表中P所指结点后插入一个S所指结点时， 应执行语句： 。
A、P->next=S;S->next=P->next;
B、S->next=P->next;P->next=S;
C、S->next=P->next;P=S;
D、S->next=P;P->next=S;
第6讲 单链表运算的应用示例及小结（总时长10分47秒）随堂测验
1、设指针变量p指向单链表中结点A的直接前驱，若删除单链表中结点A，则需要修改指针的操作序列为（ ）。
A、q=p->next；p->next=q->next；free(q)；
B、q=p->next； p->next=q->next；
C、p->next=p-> next->next；
D、q=p->next；p->data=q->data；free(q)；
2、对链表进行插入和删除操作时不必移动链表中结点。( )
3、在单链表中，可以从头结点出发，查找到表中所有结点。（ ）
第二章 第一次单元测验
1、在长度为n的顺序表中的第i( 1 =< i <= n+1 )个位置上插入一个元素，其算法时间复杂度为（ ）。
A、O(logn)(以2为底)
B、O(1)
C、O(n)
D、O(n*n)
2、在长度为n的顺序表中的第i( 1 =< i <= n+1 )个位置上插入一个元素，需要移动的元素个数为（ ）。
A、n-i
B、i
C、n-i+1
D、n-i-1
3、链表不具有的特点是（ ）。
A、插入、删除不需要移动元素
B、可随机访问任一元素
C、不必事先估计存储空间
D、所需存储空间与线性表程度成正比
4、在一单链表中，删除指针p所指的后继结点，以下语句正确的是（ ）。
A、p->next=p->next->next; free(p->next);
B、free(p->next);p->next=p->next->next;
C、p=p->next;
D、s=p->next;p->next=s->next;free(s);
5、假设删除长度为n的顺序表中的每个元素的概率相同，则删除一个元素平均要移动的元素个数是（ ）。
A、n
B、(n+1)/2
C、(n-1)/2
D、n/2
6、设某顺序表中第一个元素的地址是Base，每个结点占m个单元，则第i个结点的地址为（ ）。
A、Base+(i-1)×m
B、Base+i×m
C、Base-i×m
D、Base+(i+1)×m
7、长度为n的非空线性表采用顺序存储结构，在表的第i个位置插入一个数据元素，i的合法值应该是（ ）。
A、i>0
B、1≤i≤n+1
C、1≤i≤n-1
D、0≤i≤n+1
8、非空单链表结点结构为【data,next】，若指针p所指结点是尾结点，则（ ）表达式为真。
A、p==NULL
B、p->next==NULL
C、p->next==P
D、p->next!=NULL
9、某顺序表的第一个元素的存储地址是500，每个元素占4个单元，则第8个元素的起始地址是( )。
A、504
B、508
C、516
D、528
10、在长度为n的顺序表中删除第i(1<=i<=n)个位置上的元素，需要移动的元素个数为（ ）。
A、n-i
B、n-i+1
C、n-i-1
D、i
11、单链表中增加头结点的目的是存储链表的长度。
12、静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关。
13、线性表在链式存储时，查找第i个元素的时间同i的值无关。
14、线性表在顺序存储时，查找第i个元素的时间同i 的值成正比。
15、线性表的特点是每个元素都有一个前驱和一个后继。
16、线性表的链式存储结构优于顺序存储。
17、顺序存储方式的优点是存储密度大，插入、删除效率高。
18、顺序表的每个结点只能是一个基本类型，而链表的每个结点可以是一个构造类型。
19、插入和删除操作是线性表的基本操作。这两种操作在数组中也经常使用。
20、在顺序表中，逻辑上相邻的两个元素物理存储上也一定也相邻。
21、在线性表的链式存储结构中，逻辑上相邻的两个元素在物理存储上并不一定相邻。
22、线性表采用顺序存储，必须占用一段地址连续的存储单元。
23、顺序表结构适宜进行随机访问，而链表适宜进行插入、删除。
24、若某线性表经常做插入、删除操作，易采用 结构存储。【请填 顺序 或 链式】
第二章 第一次作业
1、描述以下三个概念及其关系：头指针，头结点，首元素结点。
2、长度为n的顺序表中，假设在任何位置插入元素的概率均相等，则插入一个元素平均需要移动多少个元素？
3、简述顺序表优缺点。
4、设顺序表L是一个递增有序表，试写一算法，将x插入L中，并使L仍是一个有序表。
第二章 线性表（二）（总时长：59分37秒）
第7讲 循环链表（总时长7分05秒）随堂测验
1、有一个带头结点的循环单链表HEAD，则判断其是否为空链表的条件是 。
A、HEAD==NULL
B、HEAD-〉NEXT==NULL
C、HEAD-〉NEXT==HEAD
D、HEAD！=NULL
2、在单向循环链表中，从表中任意结点出发都可以顺着next域访问到表中所有元素（）
第8讲 双向链表（总时长7分47秒）随堂测验
1、与单链表相比，双向链表的优点之一是 。
A、插入删除操作更加方便
B、可以进行随机访问
C、可以省略表头指针和表尾指针
D、访问前后相邻结点更方便。
2、在双向链表L中，可以从任一结点p出发沿同一方向的指针域查找到表中所有元素。（）
第10讲 链式结构小结（总时长7分32）随堂测验
1、已知单链表的头指针为head且该链表不带头结点，则该单链表为空的条件是 。
A、head== NULL
B、head->next==NULL
C、head->next==head
D、head!=NULL
2、设指针变量p指向单链表中某结点的直接前驱，若删除单链表中该结点，需要修改指针的操作序列为 。
A、q=p->next； p->next=q->next；free(q)；
B、q=p->next； free(q)；
C、p->next=p->next->next；free(p->next)；
D、q=p->next； free(q)；
3、设带有头结点的单向循环链表的头指针变量为head，则其判空条件是 。
A、head==NULL
B、head->next==NULL
C、head->next==head
D、head!=NULL
4、在双向循环链表中，可以从任一结点p出发沿同一方向的指针域查找到表中所有元素。（）
第12讲 顺序表与链表的综合比较（总时长6分08秒）随堂测验
1、下列选项中， 项是链表不具有的特点。
A、插入和删除运算不需要移动元素
B、所需要的存储空间与线性表的长度成正比
C、不必事先估计存储空间大小
D、可以随机访问表中的任意元素
2、在线性表中最常用的操作是存取第i个元素及其前趋的值，可采用 存储方式最省时间？
A、顺序表
B、带头指针的双向循环链表
C、带头指针的单向循环链表
D、带头指针的单向链表
3、下面关于线性表的叙述错误的是（ ）。
A、线性表采用顺序存储必须占用一片连续的存储空间
B、线性表采用链式存储不必占用一片连续的存储空间
C、线性表采用链式存储便于插入和删除操作的实现
D、线性表采用顺序存储便于插入和删除操作的实现
总结与提高（总时长15分15秒）随堂测验
1、某线性表中最常用的操作是存取序号为i的元素和在最后进行插入和删除运算，则采用 存储方式时间性能最好。
A、双向链表
B、双向循环链表
C、单向循环链表
D、顺序表
2、已知一个带头结点的非空循环单链表，其尾指针是R，则其首元素结点的地址为：
A、R->next
B、*( R->next->next )
C、&( R->next->next )
D、R->next->next
3、线性表的顺序存储优于链式存储结构。（）
4、在带头结点的非空单链表中，头结点的存储位置由 指示
第二章 第二次单元测试
1、非空循环单链表L中，p指针指向尾结点，则以下表达式成立的是（ ）。
A、p->next==NULL
B、p==NULL
C、p->next==L
D、p==L
2、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。
A、顺序表
B、双向链表
C、带头结点的双循环链表
D、单循环链表
3、某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。
A、单链表
B、仅有头指针的单循环链表
C、双链表
D、仅有尾指针的单循环链表
4、对于双向循环链表，在两个结点之间插入一个新结点需修改的指针共（ ）个。
A、2
B、3
C、4
D、5
5、将带头指针的长度为m的单链表，链接到同样带头指针的长度为n的单链表末尾。该算法的时间复杂度为( )。
A、O(m)
B、O(n)
C、O(m+n)
D、O(m*n)
6、双向链表中有两个指针域，llink和rlink分别指向前趋及后继，设p指向链表中的一个结点，在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;q->Rlink=q;p->Llink=q;p->Llink=q;
7、带头结点的循环链表L中只有一个元素结点的条件是：________
A、L->next==L
B、L->next->next==L
C、L->next->next==L->next
D、L->next->next==NULL
8、循环单链表中，每个结点都有一个前驱和后继，因此循环单链表不是线性结构。
9、线性表在顺序存储时，查找第i个元素的时间同i的值无关。
10、线性表在顺序存储时，删除第i个元素的时间同i的值无关。
11、循环链表不是线性表。
12、在带头指针的长度为n的双向循环链表的末尾插入一个元素，其时间复杂度为O( )。（填写阿拉伯数字或字母）
13、某双向链表中，结点结构为【prior,data,next】。那么删除p指针所指结点时，需要执行语句：p->next->prior=p->prior; ; free(p);
14、在某双向链表中删除一个结点，需要改动 个指针域（填写阿拉伯数字）
15、对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为O(___)。（填阿拉伯数字或字母）
第三章 栈与队列（一）（总时长53分23秒）
第1讲 栈的定义与实现（总时长6分59秒）随堂测验
1、栈操作的特性是（ ）
A、FIFO
B、LIFO
C、FCFS
D、插入和删除操作限制在表的两端进行
2、栈中，允许进行插入和删除的一端称为（）
A、栈顶
B、栈底
C、栈头
D、栈尾
3、栈是线性结构，是操作受限制的线性表。（）
第2讲 栈的顺序结构（总时长10分54秒）随堂测验
1、1、 已知顺序栈的地址为s,此时栈不满且栈顶指示器top指向真实栈顶,执行元素x进栈操作正确的语句是（ ）
A、s->top++;s->elem[s->top]=x;
B、s->top= s->top+1;s->elem[s->top]=x;
C、s->elem[++s->top]=x;
D、s->elem[s->top]=x;s->top++;
2、2、 已知顺序栈的地址为s ,此时栈不空且栈顶指示器top指向真实栈顶，执行出栈操作并将出栈元素赋值给x所指向的单元，则下列语句中，正确的是（ ）
A、s->top--; *x= s->elem[s->top];
B、*x= s->elem[s->top]; s->top= s->top-1;
C、*x =s->elem[s->top--];
D、*x= s->elem[s->top];s->top--;
3、1、 已知顺序栈的地址为s ,此时栈不空且栈顶指示器top指向真实栈顶，执行取栈顶操作的语句是 *x= s->elem[s->top--];( )
第3讲 顺序栈的两栈共享（总时长13分19秒）随堂测验
1、已知一个双端栈的地址为dS，则该双端栈不满时，，元素x进1号栈（高端栈）操作的语句是（）
A、dS->stack[--dS->top[1]]=x;
B、dS->stack[dS->top[1]]=x;dS->top[1]--;
C、dS->top[1]--; dS->stack[dS->top[1]]=x;
D、dS->stack[++dS->top[1]]=x;
2、已知一个双端栈dStack ,则判断该双端栈栈满的条件是（）
A、dStack.top[0]+1= = dStack.top[1]
B、dStack.top[0] = = dStack.top[1]
C、dStack.top[0]-1= = dStack.top[1]
D、dStack.top[0] = = dStack.top[1]-1
3、已知一个双端栈的地址为dS，则该双端栈不空时，1号栈（高端栈）出栈操作的语句是*x= dS->stack[dS->top[1]--]（）
第4讲 栈的链式实现（总时长8分01秒）随堂测验
1、已知带头结点的链栈top, 则该链栈不空时, 出栈操作的语句是( )
A、top->next=top->next->next; *x=top->next->data;
B、*x=top->next->data; top->next=top->next->next; free(top->next);
C、*x=top ->data;p=top;top =p->next;free(p);
D、*x=top->next->data;p=top->next; top->next=p->next;free(p);
2、已知带头结点的链栈top, 则该链栈为空的条件是( )
A、top==NULL
B、top->next= =NULL
C、top->next->next= =NULL
D、top->next= =top
3、已知带头结点的链栈top, 则元素x对应的新结点s进栈操作的语句是（）
A、s->next=top->next;top->next=s;
B、top->next=s; s->next=top->next;
C、s->next=top;top =s;
D、top =s; s->next=top;
第5讲 栈的应用（总时长8分34秒）随堂测验
1、在括号匹配算法中，当正扫描检测的符号是右括号，此时的栈是空栈，则（）。
A、右括号进栈；
B、继续向下扫描；
C、取出栈顶元素做匹配检查；
D、此时出现“右括号多了”的不匹配现象。
2、在算术表达式求值的算法中，若当前正扫描的符号是运算符s，且s的优先级比运算符栈栈顶元素的优先级高，则（ ）
A、运算符栈出栈，运算数出栈，做运算；
B、s 进运算符栈；
C、取运算符栈栈顶，运算数栈顶，做运算；
D、s 进运算数栈；
3、在括号匹配算法中，当正扫描的符号是左括号时，则该做左括号（ ）。
第6讲 栈与递归（上）（总时长10分43秒）随堂测验
1、递归进层（i→i +1层）系统需要做三件事是（ ）
A、保留本层参数与返回地址；
B、保留下层参数和函数地址；
C、为被调用函数的局部变量分配存储区，给下层参数赋值；
D、将程序转移到被调函数的入口。
2、从被调用函数返回调用函数之前，递归退层（i←i +1层）系统也应完成三件工作是（ ）
A、保存被调函数的计算结果；
B、释放被调函数的数据区，恢复上层参数；
C、保存返回上层函数的地址；
D、依照被调函数保存的返回地址，将控制转移回调用函数。
3、递归是指在定义自身的同时又出现了对自身的引用。（ ）
4、系统需设立一个递归工作栈作为整个递归函数运行期间使用的数据存储区。每层递归所需信息构成一个（ ）。
第三章 单元测验
1、栈的特点是（ ）。
A、先进先出
B、先进后出
C、后进后出
D、没有顺序
2、栈之说以叫限定性线性表，是因为（ ）。
A、栈的操作位置受限制
B、栈中的元素类型受限制
C、栈的应用范围受限制
D、栈的存储结构受限制
3、输入序列为123，若进栈出栈可以交替进行，则不能可以得到的出栈序列是（ ）。
A、321
B、312
C、123
D、132
4、以下会用到栈的应用的是（ ）。
A、递归
B、子程序调用
C、括号匹配
D、其他选项均有可能
5、当利用大小为n的数组(下标从1到n)顺序存储一个栈时，假定用top==n表示栈空，则每次向这个栈插入一个元素时，首先应执行（ ）语句修改top指针。
A、top++;
B、top--;
C、top=0;
D、top=n;
6、以下属于递归求解问题的前提条件的是（ ）。
A、原问题可层层分解为子问题，且子问题比原问题规模小
B、子问题的解法与原问题解法相同
C、最小的子问题有解
D、其他选项均是
7、一个栈的输入序列为123……n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（ ）
A、i
B、n-i
C、n-i+1
D、不确定
8、有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（ ）
A、5 4 3 6 1 2
B、4 5 3 1 2 6
C、3 4 6 5 2 1
D、2 3 4 1 5 6
9、若输入序列为1234,则通过一个栈可以得到输出序列3124。
10、若输入序列为1234,则通过栈只能得到4321的输出序列。
11、顺序栈因为是顺序存储，所以可以随机存取栈中任意元素。
12、两顺序栈共享空间，也存在空间溢出问题。
13、函数或过程调用需要用到栈。
14、栈中将允许操作的一端称作 。
15、栈中将不允许操作的一端称作 。
16、凡是对元素的保存次序与使用顺序相反的，都可以使用 。
17、若栈采用单链表结构实现，则链表的头指针的位置，表示的是栈的 。（请填栈顶或栈底）
18、若栈采用顺序存储方式存储，现两栈共享空间S[1~N]，top[i]代表第i个栈( i =1,2)栈顶。栈1的底在v[1]，栈2的底在V[N]，则栈满的条件是 。(请填top[1]+top[2]==N 或者 top[1]+1==top[2] 或者top[1]==top[2] )
19、123按顺序进栈，如果进栈出栈操作可以交替，则不可能得到的出栈序列是 。(数字中间不要加空格)
20、设有一个空栈，现有输入序列为1，2，3，4，5，经过PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后，输出序列是_______。（数字之间不要加空格或标点）
第三章 作业
1、以下算法是利用栈的先进后出特性，编写的将一个十进制的数n，转换为t进制。 请在横线位置补充代码。 //参考代码 void Conversion(int n,int t) { Stack S; int x,temp=n; InitStack(&S); //将n转换为t进制 while(n>0) { x=n%t; Push(&S, x); ; } //以下为从栈中依次出栈并输出 while(!IsEmpty(&S)) { Pop(&S,&x); if(x<=9) printf("%d",x); //小于10的，按数值打印 else ; //大于10的，按字符打印 } }
2、给出栈的两种存储结构形式名称，在这两种栈的存储结构中如何判别栈满？
第三章 栈与队列（二）（总时长：52分54秒）
第7讲 栈与递归（下）（总时长：8分40秒）随堂测验
1、递归算法具有两个特性分别是（ ）
A、递归算法求解问题，方法简单。
B、递归算法效率高
C、递归算法求解问题，方法复杂
D、递归算法的效率较低
2、下列可以直接用循环结构即可将递归转换为非递归的是（ ）
A、斐波那契数列问题
B、N!问题
C、汉诺塔问题
D、尾递归问题
第8讲 队列的定义与实现（总时长：13分32秒）随堂测验
1、已知带头结点的链队列指针Q，则该队列做新元素结点s进队操作的语句是（ ）
A、Q->rear->next=s; Q->rear=s;
B、s->next=Q->front->next; Q->front->next=s;
C、Q->next=s;Q=s;
D、s->next=Q->next ;Q->next=s;
2、已知带头结点的链队列指针Q，则该非空队列取队头元素操作的语句是（ ）
A、*x=Q->next->data;
B、*x=Q->front->data;
C、*x=Q->front->next->data;
D、*x=Q->rear->data;
3、队列操作的特性是LIFO。（）
4、队列允许做插入的一端称为队头，允许删除的一端称为队尾（ ）
第9讲 序列的顺序存储（循环队列）（总时长：11分08秒）随堂测验
1、已知循环队列Q-> element[MAXSIZE],队头指示器为Q->front，队尾指示器为Q->rear（指向真实队尾的下一个位置），则该队列中元素个数为：（）
A、Q->rear-Q->front
B、Q->rear-Q->front+1
C、（Q->rear-Q->front+ MAXSIZE）% MAXSIZE
D、（Q->rear-Q->front+1+ MAXSIZE）% MAXSIZE
2、已知循环队列Q-> element[MAXSIZE],队头指示器为Q->front，队尾指示器为Q->rear（指向真实队尾的下一个位置），则该队列为空队列的条件为（ ）
A、Q->rear= =Q->front
B、Q->rear+1= =Q->front
C、（Q->rear+1）% MAXSIZE = =Q->front
D、（Q->rear-1）% MAXSIZE = =Q->front
3、已知循环队列Q-> element[MAXSIZE],队头指示器为Q->front，队尾指示器为Q->rear（指向真实队尾的下一个位置），则该队列为满队列的条件为（ ）（采用少用一个空间的方法）
A、Q->rear= =Q->front
B、Q->rear+1= =Q->front
C、（Q->rear+1）% MAXSIZE = =Q->front
D、（Q->rear-1）% MAXSIZE = =Q->front
第三章 单元测验二
1、循环队列存储在数组A[0..m-1]中，则入队时rear应该变化为（ ）
A、rear=(rear+1) mod m
B、rear++
C、rear=(rear+1) mod (m-1)
D、rear=(rear+1) mod (m+1)
2、循环队列A[0..n-1]存放其元素值，用F和R分别表示队头和队尾，则当前队列中的元素数是( )。
A、(R-F+n)%n
B、R-F+1
C、R-F-1
D、R-F
3、设栈S和队列Q的初始状态均为空，元素a,b,c,d,e,f,g依次进入栈S。如果每个元素出栈后立即进入队列Q，且7个元素出队的顺序为b,d,e,f,c,a,g，则栈S的容量至少是（ )。
A、2
B、3
C、1
D、4
4、以下属于消除递归的主要原因是（ ）。
A、递归程序时空效率较差
B、递归程序不容易理解
C、递归程序容易写错
D、其他选项均是
5、用链接方式存储的队列，在进行删除运算时（ ）。
A、仅修改头指针
B、头、尾指针可能都要修改
C、头、尾指针都要修改
D、仅修改尾指针
6、若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？( )
A、1和 5
B、2和4
C、5和1
D、4和2
7、设有一个递归算法如下 int fact(int n) { //n大于等于0 if(n<=0) return 1; else return n*fact(n-1); } 则计算fact(n)需要调用该函数的次数为（ ）。
A、n
B、n-1
C、n+1
D、n+2
8、为解决计算机主机与打印机间速度不匹配问题，通常设一个打印数据缓冲区。主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（ ）。
A、队列
B、栈
C、有序表
D、线性表
9、循环队列存储在数组A[0..m]中，则入队时的操作为（ ）。
A、rear=rear+1
B、rear=(rear+1) mod (m-1)
C、rear=(rear+1) mod m
D、rear=(rear+1)mod(m+1)
10、栈和队列的共同点是( )
A、都是先进后出
B、都是先进先出
C、只允许在端点处插入和删除元素
D、没有共同点
11、消除递归不一定需要使用栈。
12、栈和队列都是限制存取点的线性结构。
13、循环队列也存在空间溢出问题。
14、栈和队列的存储方式，既可以是顺序方式，又可以是链式方式。
15、循环队列通常用指针来实现队列的头尾相接。
16、通常使用队列来处理函数或过程的调用。
17、队列是限制插入只能在表的一端，而删除在表的另一端进行的线性表，其特点是_______。
18、在具有n个单元的循环队列中，队满时共有____个元素。
19、执行完下列语句段后，i值为：（ ） int f(int x) { return ((x>0) ? x* f(x-1):2);} int i ; i =f(f(1));
第四章 串（总时长：51分45秒）
第1讲 串的基本概念（总时长：8分38秒）随堂测验
1、设s=‘abcd’,s1=‘123’，则执行语句StrInsert( s,2,s1)后，s= .
A、‘123abcd’
B、‘a123bcd’
C、‘ab123cd’
D、‘abc123d’
2、设s=‘abcd’，则执行语句StrDelete( s,2,2)后，s= .
A、‘abcd’
B、‘abc’
C、‘ad’
D、‘a’
第2讲 串的顺序存储结构（总时长：21分04秒）随堂测验
1、假设主串S=‘aaabbbababaabb’,模式串T=‘abaa’,用串匹配算法从主串的第6个字符开始模式匹配，需要做 趟匹配，方能找到匹配串。
2、假设主串S=‘aaabbbababaabb’,模式串T=‘abaa’,用串匹配算法从主串的第6个字符开始模式匹配，在第2趟匹配中，要做 次比较。
第3讲 串的链式存储及串的应用（总时长：22分03秒）随堂测验
1、用带头结点的单链表来表示串s,则串s 为空串的条件是（ ）
A、s->next==NULL
B、s==NULL
C、s->next==s
D、s->next->next==NULL
第四章 单元测验
1、下面关于串的的叙述中，哪一个是不正确的？（ ）
A、串是字符的有限序列
B、空串是由空格构成的串
C、模式匹配是串的一种重要运算
D、串既可以采用顺序存储，也可以采用链式存储
2、设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（ ）
A、求子串
B、模式匹配
C、联接
D、求串长
3、若串S=‘soft’,其子串的数目是（ ）。
A、4
B、10
C、11
D、5
4、串的长度是指（ ）
A、串中所含不同字母的个数
B、串中所含非空格字符的个数
C、串中所含字符的个数
D、串中所含不同字符的个数
5、字符串”ABCDEFG”采用链式存储，假设每个字符占用1个字节，每个指针占用4个字节。则该字符串的存储密度为（ ）
A、20%
B、40%
C、50%
D、33.3%
6、字符串采用链式存储，假设每个字符占用1个字节，每个指针占用4个字节。若该字符串的存储密度为50%，则每个结点应存储（ ）个字符
A、2
B、3
C、4
D、1
7、串的长度是指串中不同字符的个数。
8、串是N个字母的有限序列。
9、空串不等于空格串。
10、如果两个串含相同的字符，则说明它们相等。
11、如果一个串中相同的字符均在另一个串中出现，则说明前者是后者的子串。
12、串的堆分配存储是一种动态存储结构。
第四章 单元作业
1、写一算判断其是否为回文。（即正读和倒读相同） Typedef struct{ char *ch； int length； }HString void ispalindrome(hstring s)
2、写一算法，将字符串逆置。 Typedef struct{ char *ch； int length； }HString converse(&Hstring S)
第五章 数组与广义表（上）（总时长：38分01秒）
第1讲 数组的定义与顺序存储（总时长：19分57秒）随堂测验
1、数组的维数和维度一旦确定，数组中元素的个数就确定了，不能增加不能减少。（ ）
2、数组的维数n决定了数组中的元素受n个线性关系的约束。（ ）
3、数组如同一般的线性表，可以做的基本运算包括存取指定位置的元素，插入，删除等。( )
4、假设有6行8列的二维数组A(下标从1开始),每个元素占用6个字节,存储器按字节编址。已知A的基地址为1000，数组A共占用 字节;
5、假设有6行8列的二维数组A(下标从1开始),每个元素占用6个字节,存储器按字节编址。已知A的基地址为1000 ,计算数组A的最后一个元素的地址是 。
6、假设有6行8列的二维数组A(下标从1开始),每个元素占用6个字节,存储器按字节编址。已知A的基地址为1 000 ,计算按行存储时元素A36的地址是 ;
7、假设有6行8列的二维数组A(下标从1开始),每个元素占用6个字节,存储器按字节编址。已知A的基地址为1 000 ,计算按列存储时元素A36的地址是 。
第2讲 规律分布特殊矩阵的压缩存储（总时长：18分04秒）随堂测验
1、已知一个n行n列的带状矩阵A，其中非零元素的个数是（ ）
A、3n
B、3n-2
C、3n+2
D、![]()
2、若将n阶上三角矩阵A按列优先雅朵存放在一维数组B中，第一个非零元素存放在B[0]中，则非零元素aij存放在B[k]中，则k=( )
A、![]()
B、![]()
C、![]()
D、![]()
3、所谓的n阶下三角矩阵A是指当i<j时（i为元素的行标，j 为元素的列标）元素aij为0或常数C .( )
4、所谓的n阶（n>3）三对角矩阵（带状矩阵）是指非零元素只出现在矩阵的两条对角线上。（ ）
第五章 数组与广义表（下）（总时长：57分05秒）
第3讲 稀疏矩阵的压缩存储（上）（总时长：17分54秒）随堂测验
1、对稀疏矩阵进行压缩存储的目的是（ ）
A、便于进行矩阵运算
B、便于输入和输出
C、节省存储空间
D、减低运算的时间复杂度
2、稀疏矩阵压缩存储后，不会失去（ ）功能 输入输出
A、顺序存储
B、随机存取
C、输入输出
D、输入输出
第4讲 稀疏矩阵的压缩存储（下）（总时长：19分16秒）随堂测验
1、对于一个m行n列的稀疏矩阵中有len个非零元素，则用十字链表存储时，需要（ ）个头指针。
2、对于一个m行n列的稀疏矩阵中有len个非零元素，则用十字链表存储时，需要（ ）个三元组结点。
第5讲 广义表及本章小结（总时长：19分55秒）随堂测验
1、任意一个广义表都可以表示为由表头和表尾构成（ ）。
2、非空的广义表的表尾可能是单个元素也可能是表元素（ ）。
3、已知广义表L=(( x,y,z), a,( u,t,w)),则head( head( tail( tail( L))))的结果是（ ）。
4、已知数组M[ 1 ..10 ,-1 ..6 ,0 ..3 ], )若数组以行序为主序存储,起始地址为1 000 ,且每个数据元素占用3个存储单元,则M[ 2 ,4 ,2 ]的地址为（ ）
第五章 单元测验
1、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（ ）。
A、13
B、33
C、18
D、40
2、A[N，N]是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组T[1..N（N+1）/2]中，则对任一上三角元素a[i][j]对应T[k]的下标k是（ ）。
A、i（i-1）/2+j
B、j（j-1）/2+i
C、i（j-i）/2+1
D、j（i-1）/2+1
3、设二维数组A[1.. m，1.. n]（即m行n列）按行存储在数组B[1.. m*n]中，则二维数组元素A[i，j]在一维数组B中的下标为( )。
A、（i-1）*n+j
B、（i-1）*n+j-1
C、i*（j-1）
D、j*m+i-1
4、有一个100*90的稀疏矩阵，非0元素有11个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是（ ）。
A、60
B、66
C、18000
D、33
5、数组A[0..4,-1..-3,5..7]中含有元素的个数（ ）。
A、55
B、45
C、36
D、16
6、对稀疏矩阵进行压缩存储目的是（ ）。
A、便于进行矩阵运算
B、便于输入和输出
C、节省存储空间
D、降低运算的时间复杂度
7、广义表（（a,b,c,d））的表头是（ )。
A、a
B、（a,b,c,d）
C、（）
D、（b,c,d）
8、广义表（（a,b,c,d））的表尾是（ ）。
A、a
B、（）
C、（a,b,c,d）
D、（b,c,d）
9、设广义表L=（（a,b,c）），则L的长度和深度分别为（ ）。
A、1和1
B、1和3
C、1和2
D、2和3
10、下面说法不正确的是( )。
A、广义表的表头总是一个广义表
B、广义表的表尾总是一个广义表
C、广义表难以用顺序存储结构
D、广义表可以是一个多层次的结构
11、稀疏矩阵压缩存储后，必会失去随机存取功能。
12、一个稀疏矩阵Am*n采用三元组形式表示， 若把三元组中有关行下标与列下标的值互换，并把m和n的值互换，则就完成了Am*n的转置运算。
13、广义表的取表尾运算，其结果通常是个表，但有时也可是个单元素值。
14、若一个广义表的表头为空表，则此广义表亦为空表。
15、所谓取广义表的表尾就是返回广义表中最后一个元素。
16、广义表的同级元素（直属于同一个表中的各元素）具有线性关系。
17、一个广义表可以为其它广义表所共享。
18、已知二维数组A[1..10，0..9]中每个元素占4个单元，在按行优先方式将其存储到起始地址为1000的连续存储区域时，A[5，8]的地址是_______
19、设广义表L=(()), 则L的长度是( )。
20、设广义表L=((),()),L的深度是( )。
21、广义表(a,(a,b),d,e,((i,j),k))的长度是( )
22、广义表(a,(a,b),d,e,((i,j),k))的深度是（ ）
23、数组A[0..5,2..6,5..7]中含有元素的个数是（ ）
第六章 树和二叉树（上）（总时长：48分02秒）
第1讲 树的基本概念（总时长：17分07秒）随堂测验
1、树最适合用来表示（ ）
A、有序数据元素
B、无序数据元素
C、元素之间具有分支层次关系的数据
D、元素之间无联系的数据
2、若一棵树的广义表法表示为：A（B（E,F），C（G（H,I,J,K），L），D（M（N））） 则该树的度为（ ）；
3、若一棵树的广义表法表示为：A（B（E,F），C（G（H,I,J,K），L），D（M（N））） 该树的深度为（ ）；
4、若一棵树的广义表法表示为：A（B（E,F），C（G（H,I,J,K），L），D（M（N））） 该树中叶子结点的个数为：（ ）
第2讲 二叉树（总时长：18分04秒）随堂测验
1、按照二叉树的定义，具有3个结点的二叉树有（ ）种
A、3
B、4
C、5
D、6
2、若一棵二叉树有10个度为2的结点，5个度为1的结点，则度为0的结点有（ ）个。
A、9
B、11
C、15
D、不确定
3、一个高度为h的完全二叉树至少有（ ）个结点
A、![]()
B、![]()
C、![]()
D、![]()
4、二叉树就是结点度不大于2的树。（）
5、不存在这样的二叉树：它有n个度为0的结点，n-1个度为1的结点，n-2个度为2的结点。（ ）
6、具有n个结点的二叉树采用二叉链表存储结构，共有（ ）非空的指针域。
7、拥有100个结点的完全二叉树的最大层数是（ ）
第3讲 二叉树的遍历（总时长：12分51秒）随堂测验
1、某二叉树的先序序列和中序序列正好相同，则该二叉树一定是 （ ）
A、空树或只有一个结点
B、完全二叉树
C、每个结点都没有左子
D、高度等于其结点数
2、在二叉树中，p所指向的结点为度为1的分支点的条件是（ ）
A、p->lchild= =NULL ||p->rchild= =NULL
B、!( p->lchild! =NULL &&p->rchild!=NULL)
C、!(p->lchild= =NULL &&p->rchild= =NULL)
D、(p->lchild= =NULL &&p->rchild! =NULL)|| (p->lchild! =NULL &&p->rchild= =NULL)
3、已知二叉树的先序和后序遍历序列可以唯一确定该二叉树。（ ）
第六章 单元测验1
1、有关二叉树下列说法正确的是（ ）。
A、二叉树中每个结点的度都为2
B、一棵二叉树的度可以小于2
C、二叉树中至少有一个结点的度为2
D、二叉树中任何一个结点的度都为2
2、在一棵高度为k的满二叉树中，结点总数为（ ）。
A、![]()
-1
B、2k
C、![]()
D、![]()
3、某二叉树中有60个叶子结点，则该二叉树中度为2的结点个数为（ ）。
A、59
B、60
C、61
D、不确定
4、100个结点的完全二叉树采用顺序存储，从1开始按层次编号，则编号最小的叶子结点的编号应该是（ ）。
A、100
B、49
C、50
D、51
5、设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为（ ）
A、5
B、6
C、7
D、8
6、二叉树是非线性数据结构，所以 。
A、它不能用顺序存储结构存储;
B、它不能用链式存储结构存储;
C、顺序存储结构和链式存储结构都能存储;
D、顺序存储结构和链式存储结构都不能使用
7、完全二叉树一定存在度为1的结点。
8、完全二叉树中，若一个结点没有左孩子，则它必是叶子。
9、二叉树只能用二叉链表表示。
10、树形结构中，每个元素都有一个前驱，0个或多个后继。
11、二叉树的遍历结果不是唯一的
12、二叉树的遍历只是为了在应用中找到一种线性次序。
13、由3 个结点可以构造出 种形态不同的无序树。
14、由3 个结点可以构造出 种形态不同的二叉树。
15、对任意一棵有n个结点的树，这n个结点的度之和为 。
16、高度为7的完全二叉树，最少有 个结点。
17、具有512个结点的完全二叉树的深度为______。
18、已知二叉树有30个叶子结点，则该二叉树的总结点数至少是______。
第六章 树和二叉树（下）（总时长：112分28秒）
第4讲 遍历算法应用（总时长：19分50秒）随堂测验
1、设二叉树采用二叉链表方式存储，root指向根结点，r所指结点为二叉树中任一给定的结点。则可以通过改写（ ）算法，求出从根结点到结点r之间的路径。
A、先序遍历
B、中序遍历
C、后序遍历
D、层次遍历
2、已知二叉树用二叉链表存储，则若实现二叉树实现左右子树交换，可以借助改写（ ）遍历算法实现。
A、先序遍历
B、中序遍历
C、后序遍历
D、以上三种都可以
第5讲 基于栈的递归消除（总时长：14分27秒）随堂测验
1、在中序遍历非递归算法中，在进入子树进行访问前，需要在自定义栈中保存（ ）
A、本层根结点指针
B、本层根结点的右孩子指针
C、本层根结点的左孩子指针
D、无需保留任何信息
第6讲 线索二叉树（总时长：17分35秒）随堂测验
1、引入线索二叉树的目的是( )
A、加快查找指定遍历过程中结点的直接前驱和直接后继
B、为了能在二叉树中方便地插入和删除结点
C、为了方便找到结点的双亲
D、使二叉树遍历结果唯一
2、若判断线索二叉树中的p结点有右孩子结点则下列（）表达式为真。
A、p!=NULL
B、p->rchild!=NULL
C、p->rtag= =0
D、p->rtag= =1
3、若线索二叉树中的p结点没有左孩子结点则下列（ ）表达式为真。
A、p==NULL
B、p->lchild==NULL
C、p->ltag= =0
D、p->ltag= =1
第7讲 由遍历序列确定的二叉树（总时长：7分48秒）随堂测验
1、一棵二叉树的后序序列是：CBEFDA,中序序列是：CBAEDF,则该二叉树的先序序列是（ ）
A、ABCDEF
B、ABCEDF
C、ABDEFC
D、ABFECD
2、一棵二叉树的先序序列是：CEDBA,中序序列是：DEBAC ,则该二叉树的后序序列是（ ）
A、DABEC
B、DCBAE
C、DEABC
D、CBADE
第8讲 树、森林和二叉树的关系（总时长：17分33秒）随堂测验
1、如图所示的二叉树BT是由森林T1转换而来的二叉树，那么森林T1中有（ ）叶子结点。![]()
A、4
B、5
C、6
D、7
2、与树等价的二叉树，根没有（ ）子树。
第9讲 哈夫曼树及其应用——哈夫曼树（总时长：12分46秒）随堂测验
1、有13个叶子结点的哈夫曼树，该树中结点总数为（ ）
A、13
B、26
C、12
D、25
2、在哈夫曼树中，权值相同的叶子点一定在同一层上。（ ）
3、在哈夫曼树中，权值较大的叶子点一般离根比较近。（ ）
4、若以{4,5,6,7,8}作为叶子点构造哈夫曼树，则其带全路径长度为（ ）
第10讲 哈夫曼树及其应用——哈夫曼编码（总时长：14分35秒）随堂测验
1、在哈夫曼编码中，当两个字符出现的频率相等时，则两个字符的哈夫曼编码也相同。（ ）
第六章 单元测验2
1、已知一棵二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBAEDF，则后序遍历的结果为（ ）。
A、CBEFDA
B、FEDCBA
C、CBEDFA
D、不确定
2、以下属于前缀编码的是（ ）。
A、{0,1,01,010,110}
B、{00,01,10,11,101}
C、{0,1101,1110,1100,1111}
D、{01,00,10,001,110,101}
3、在下列存储形式中，（ ）不是树的存储形式。
A、双亲表示法
B、孩子链表表示法
C、孩子-兄弟表示法
D、顺序存储表示法
4、对二叉树中的结点进行编号，要求根结点的编号最小，左孩子结点编号比右孩子结点编号小。则应该采用（ ）遍历方法对其进行编号。
A、先序
B、中序
C、后序
D、层次
5、已知某二叉树的后序遍历序列是CEFDBA，中序遍历序列是CBEDFA。与该二叉树对应的树或森林中，叶子的数目是（ ）个。
A、1
B、2
C、3
D、4
6、某二叉树中有60个叶子结点，则该二叉树中度为2的结点个数为（ ）。
A、59
B、60
C、61
D、不一定
7、设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（ ）。
A、M1
B、M1+M2
C、M2+M3
D、M3
8、一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ ）
A、以上答案都不对
B、499
C、500
D、502
9、一个具有1025个结点的二叉树的高h为（ ）
A、10至1024之间
B、11至1025之间
C、11
D、10
10、哈夫曼树的带权路径长度等于其中所有结点的带权路径之和。
11、给定二叉树的先序、中序和后序遍历序列中的两个，就可以唯一确定一棵二叉树。
12、在叶子数目和权值相同的所有二叉树中，带权路径长度最小的树一定是哈夫曼树。
13、将一棵树转成二叉树，根结点一定没有右子树。
14、一棵哈夫曼树中不存在度为1的结点。
15、在叶子数目和权值相同的所有二叉树中，带权路径长度最小的树一定是完全二叉树。
16、先序线索二叉树中，某结点的后继一定在左子树上。
17、哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。
18、有10个叶子结点的哈夫曼树，总结点个数是 。
19、将一棵树转换为二叉树时，遵循的规则是左孩子、 。
20、用权值{1,2,3,4,5}构造一棵哈夫曼树，则该树的带权路径长度为 。
21、假设T是一棵高度为5的二叉树,T中只有度为0和度为2的结点，那么T树最少应该有 个结点。
22、树的后根遍历，相当于对应二叉树的 遍历。
23、含有100个结点的树有 条边。
24、一棵左子树为空的二叉树在先序线索化后，其中空的链域的个数是( )
25、高度为8的完全二叉树至少有______个叶子结点。
第七章 图（总时长：102分26秒）
第1讲 图的基本概念（总时长：12分20秒）随堂测验
1、一个有n个顶点的有向图最多有 边
A、n
B、n(n-1)
C、n(n-1)/2
D、2n
2、具有n个顶点的有向图至少应有 弧才能确保是一个强连通图。
A、n-1
B、n
C、n(n-1)
D、n(n-1)/2
3、在一个无向图中，所有顶点的度之和等于边条数的 倍。
4、具有6个顶点的无向图至少应有 条边才能确保是一个连通图。
5、一个有向图G中所有顶点的入度之和是所有顶点出度之和的 倍。
第2讲 图的存储结构（总时长：12分28秒）随堂测验
1、对于一个n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小为（）
A、n
B、n(n-1)
C、![]()
D、![]()
2、有向图的邻接矩阵一定是对称矩阵。（）
3、用邻接矩阵存储无向图G时，其第i行中1的个数与第i列中1的个数相等。（）
4、对于一个有n个顶点，e条边的无向图，若采用邻接表表示，则表头结点数组的大小为 。
5、对于一个有n个顶点，e条边的无向图，若采用邻接表表示，则边结点有 个。
6、用邻接矩阵存储有向图G时，其第i列的所有元素之和等于该顶点的 。
第3讲 图的遍历（总时长：17分05秒）随堂测验
1、如果从一个无向图的任意一个顶点出发进行一次深度优先搜索即可访问所有顶点,则该图一定是( )
A、完全图
B、连通图
C、有回路
D、森林
2、图的深度优先遍历类似于树的（ ）遍历
A、先序遍历
B、中序遍历
C、后序遍历
D、层次遍历
3、图的广度优先遍历类似于树的（ ）遍历
A、先序遍历
B、中序遍历
C、后序遍历
D、层次遍历
第4讲 图的连通性（总时长：11分36秒）随堂测验
1、任何一个连通图（ ）生成树。
A、只有一棵
B、有一棵或多棵
C、一定有多棵
D、可能不存在
2、Prim算法适合求（ ）的最小生成树。
A、边稠密连通网
B、边稀疏连通网
C、边稠密无向网
D、边稀疏无向网
3、对于n个顶点的连通图G来说，如果其中的某个子图有n个顶点，n-1条边，则该子图一定是G的生成树。（ ）
4、对于n个顶点的连通图而言，它的生成树一定有 条边。
第5讲 有向无环图应用——拓扑排序（总时长：12分37秒）随堂测验
1、若一个有向图中的顶点不能排成一个拓扑序列，则可断定该有向图（ ）
A、是个有向无环图
B、是个含有回路的有向图
C、含有多个入度为0的顶点
D、是个强连通图
2、任何有向无环图的顶点都可以排成拓扑排序序列，且拓扑排序序列唯一（ ）
3、在ＡＯＶ网中，顶点表示 。
第6讲 有向无环图应用——关键路径（总时长：15分21秒）随堂测验
1、关键路径是ＡＯE网中（ ）
A、从源点到汇点的最长路径
B、从源点到汇点的最短路径
C、最长回路
D、最短回路
2、关键活动若不能按期完成就会影响整个工程的完成时间，若某些关键活动能提前完成，将可能使整个工程提前完成。（）
3、在ＡＯE网中，关键路径上的活动称为 。
第7讲 最短路径（总时长：16分28秒）随堂测验
1、求最短路径的Dijkstra算法的时间复杂度为（ ） n为图中顶点数，e为图中边数。
A、O（n）
B、O（n+e）
C、O（![]()
）
D、O(ne)
2、求最短路径的Dijkstra算法不适用于有回路的有向网（ ）
第七章 单元测验
1、在一个图中，所有顶点的度之和是所有边数的 ( )倍。
A、1/2
B、1
C、2
D、3
2、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的( )倍。
A、1/2
B、1
C、2
D、4
3、一个有n个顶点的无向图最多有( )条边。
A、n
B、n*(n-1)
C、( n*(n-1) ) / 2
D、2*n
4、在一个具有n个顶点的无向图中，要连通全部顶点至少需要 ( )条边。
A、n
B、n+`
C、n-1
D、n/2
5、对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是( )。
A、n
B、n*n
C、2*(n-1)
D、n-1
6、对于一个具有n个顶点和e条边的无向图，若采用邻接表示，邻接表中的结点总数是( )。
A、e/2
B、2
C、2*e
D、n+e
7、以下说法错误的是( )。
A、用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关。
B、邻接表只能用于有向图的存储，而邻接矩阵对于有向图和无向图的存储都适用。
C、存储无向图的邻接矩阵是对称的，因此只要存储邻接矩阵的下（或上）三角部分就可以了
D、用邻接矩阵M表示图，判定任意两个结点Vi和Vj之间是否有长度为n的路径相连，则只要检查M的n次方后，第 i行第j列的元素是否为0即可。
8、已知一个图的邻接矩阵表示，删除所有从第i个顶点出发的方法是（ ）。
A、将矩阵第i行删除，后序行上移
B、将矩阵第i列删除，后序列左移
C、将矩阵第i行上的元素全部置0
D、将矩阵第i列上的元素全部置0
9、某图的邻接表存储结构如下图所示， 则从6号点出发，深度优先遍历的序列是（ ）![]()
A、6-5-2-1-4-3
B、6-5-1-2-4-3
C、6-5-1-4-3-2
D、6-5-2-1-4-3
10、某图的邻接矩阵存储结构如下图所示， 则从6号点出发，广度优先遍历的序列是（ ）![]()
A、6-1-2-5-4-3
B、6-1-2-4-5-3
C、6-5-1-4-3-2
D、6-5-2-1-4-3
11、关键路径上的活动都是关键活动，它们是否按时完成会影响工期。
12、求稀疏图的最小生成树，用克鲁斯卡尔算法来求解较好。
13、求稠密图的最小生成树，用普里姆算法来求解较好。
14、迪杰斯特拉算法求最短路径时，是按照路径长度递增的顺序求解的。
15、一个有向图的拓扑排序只有一个。
16、每一个有向图肯定至少有一个拓扑排序。
17、具有6个顶点的无向图至少应有6条边才能确保是一个连通图。
18、非关键活动，可以无限期延迟。
19、图的存储结构主要有邻接矩阵和________两种。
20、对具有n个顶点的图其生成树有且仅有________条边。
21、在有向图的邻接矩阵上，第i行中的非零且非无穷元素个数是第i个结点的 。
22、如果n个顶点的图是一个环，则它有 棵生成树。
23、关键路径是从源点到汇点的 路径。
24、稠密图采用 存储较省空间
25、稀疏图采用 存储较省空间。
第八章 查找（总时长：73分53秒）
第1讲 查找的基本概念（总时长：10分31秒）随堂测验
1、采用顺序查找法查找长度为n的线性表时，平均查找长度为 。
A、n
B、![]()
C、![]()
D、![]()
2、通常将 作为衡量一个查找算法效率优劣的标准。
A、平均查找长度
B、比较次数
C、WPL
D、ASL
3、顺序查找方法只能在顺序存储结构上进行。（ ）
4、顺序查找含n个元素的顺序表，若查找成功，则比较关键字的次数最多为 次。
5、顺序查找含n个元素的顺序表，若查找不成功，则比较关键字的次数为 次。
第2讲 基于线性表的查找法（总时长：10分44秒）随堂测验
1、对列表进行折半查找时，要求列表必须 。
A、顺序存储
B、链式存储
C、顺序存储且元素按关键字有序存储
D、链式存储且元素按关键字有序存储
2、当采用分块查找时，数据的组织方式要求 。
A、数据分成若干块，每块内元素有序
B、数据分成若干块，每块内元素不必有序，但块间必须有序，且每块内最大（或最小）的数据组成索引块；
C、数据分成若干块
D、数据分成若干块，每块（除最后一块外）中元素个数相等。
3、有一个有序表{1,3,9,12,32,41，45,62,75,77,82,95,99}当采用折半查找法查找关键字为82的元素时，需经过 次比较后查找成功。
A、1
B、2
C、4
D、8
4、折半查找可以在有序的双向链表上进行。（ ）
第3讲 树表式查找方法——二叉排序树（总时长：12分08秒）随堂测验
1、如图所示的二叉排序树，，起查找成功时的平均查找长度是 。![]()
A、![]()
B、![]()
C、![]()
D、![]()
2、在一棵平衡二叉树中，每个结点的平衡因子的取值范围是 。
A、-1——1
B、-2——2
C、1——2
D、0——1
3、查找效率最高的二叉排序树是平衡二叉排序树。（ ）
4、在二叉排序树中新插入的结点总是作为叶子结点来插入的。（ ）
5、在二叉排序树中新插入的结点总是处于最底层。（ ）
6、每个结点的关键字都比左孩子关键字大，比右孩子关键字小，这样的二叉树都是二叉排序树。（ ）
第4讲 计算式查找法——哈希表的构造（总时长：16分27秒）随堂测验
1、将10个元素散列到10000000个单元的哈希表中，则 产生冲突。
A、一定会
B、一定不会
C、仍可能会
D、以上都不对
2、在哈希查找中，可用 来处理冲突。
A、除留余数法
B、数字分析法
C、线性探测散列法
D、数字分析法
3、设哈希表长度m=12，哈希函数为H（key）=key mod 11.表中已经有4个结点分别为H（15）=4，H(38)=5, H（61）=6，H(84)=7,其余地址为空。如果用二次探测再散列处理冲突，则关键字为49的结点地址为 。
A、8
B、3
C、5
D、9
4、设哈希表长度m=14,哈希函数H（key）=key mod p,则p最好取 。
第5讲 哈希法的性能分析（总时长：9分02秒）随堂测验
1、若采用链地址法构造哈希表并处理冲突，哈希函数为H（key）=key mod 17，则需要 个链表。
A、17
B、16
C、13
D、不确定
2、假设有k个关键字互为同义词，若用线性探测再散列法将这k个关键字存入哈希表中，至少要进行 次定址。
A、k-1
B、k
C、k+1
D、k(k+1)/2
3、哈希表的查找性能 。
A、与处理冲突的方法有关而与表的长度无关
B、与处理冲突的方法无关而与表的长度有关
C、与处理冲突的方法无关而与装填因子有关
D、与处理冲突的方法有关，与装填因子有关
第八章 单元测验
1、用二分（对半）查找表的元素的速度比用顺序法( )
A、必然快
B、必然慢
C、相等
D、不能确定
2、具有12个关键字的有序表，折半查找的平均查找长度（ ）
A、3.1
B、4
C、2.5
D、5
3、设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链地址法构造散列表，散列函数为H（key）=key MOD 13,散列地址为1的链中有（ ）个记录。
A、1
B、2
C、3
D、4
4、下面关于哈希(Hash，杂凑)查找的说法正确的是( )
A、哈希函数构造的越复杂越好，因为这样随机性好，冲突小
B、除留余数法是所有哈希函数中最好的
C、不存在特别好与坏的哈希函数，要视情况而定
D、若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单的将该元素删去即可
5、散列表的地址区间为0-17,散列函数为H(K)=K mod 17。采用线性探测法处理冲突，并将关键字序列26，25，72，38，8，18，59依次存储到散列表中。元素59存放在散列表中的地址是（ ）。
A、8
B、9
C、10
D、11
6、散列函数有一个共同的性质，即函数值应当以( )取其值域的每个值。
A、最大概率
B、最小概率
C、平均概率
D、同等概率
7、分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( )
A、（100，80， 90， 60， 120，110，130）
B、（100，120，110，130，80， 60， 90）
C、（100，60， 80， 90， 120，110，130）
D、(100，80， 60， 90， 120，130，110)
8、二叉查找树的查找效率与二叉树的树型有关, 在 ( )时其查找效率最低。
A、结点太多
B、完全二叉树
C、呈单枝树
D、结点太复杂。
9、采用线性探测法处理散列时的冲突，当从哈希表删除一个记录时，不应将这个记录的所在位置置空，因为这会影响以后的查找。
10、在散列检索中，“比较”操作一般也是不可避免的。
11、散列函数越复杂越好，因为这样随机性好，冲突概率小.
12、哈希函数的选取平方取中法最好。
13、Hash表的平均查找长度与处理冲突的方法无关。
14、负载因子 (装填因子)是散列表的一个重要参数，它反映散列表的装满程度。
15、散列法的平均检索长度不随表中结点数目的增加而增加，而是随负载因子的增大而增大。
16、完全二叉树肯定是平衡二叉树。
17、对一棵二叉排序树按前序方法遍历得出的结点序列是从小到大的序列。
18、在任意一棵非空二叉排序树中，删除某结点后又将其插入，则所得二排序叉树与原二排序叉树相同
19、在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找关键码值20，需做的关键码比较次数为____.
20、在有序表A[1..20]中，按二分查找方法进行查找，查找长度为5的元素个数是__________
21、顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为__ __次
第九章 内部排序（总时长：97分05秒）
第2讲 插入类排序（总时长：14分05秒）随堂测验
1、对数据序列{15,9,7,8,20,-1,4}进行排序，进行一趟后的结果为：{9,15,7,8,20,-1,4}，则采用的是（ ）排序方法。
A、简单选择排序
B、冒泡排序
C、直接插入排序
D、堆排序
2、下列排序方法中，（ ）在初始序列已基本有序的情况下，排序效率最高。
A、归并排序
B、直接插入排序
C、快速排序
D、堆排序
3、用希尔排序对{Q,H,C,Y,Q,A,M,S,R,D,F,X},进行排序，第一趟的增量是4，则第一趟排序后的结果是（ ）
A、{H,Q, C,Y,Q,A,M,S,R,D,F,X}
B、{Q,A,C,S,Q,D,F,X,R,H,M,Y}
C、{H,C,Q,Q,A,M,S,R,D,F,X,Y}
D、{ A,H,C,Y,Q,Q,M,S,R,D,F,X}
4、设用希尔排序对{98,36,-9,0,47,23,1,8,10,7}进行排序，给出的增量序列依次是4,2,1，则排序需要进行 趟。
第3讲 交换类排序（总时长：12分01秒）随堂测验
1、快速排序在（ ）情况下最不利于发挥其长处。
A、要排序的数据量太大
B、要排序的数据中含有多个相同的值
C、要排序的数据个数是奇数
D、要排序的数据基本有序
2、以下（ ）法在数据基本有序时效率最好。
A、快速排序
B、冒泡排序
C、堆排序
D、希尔排序
3、对关键字{28,16,32,12,60,2,5,72}进行快速排序，第一趟以28为枢轴产生的划分结果为（ ）
A、（2,5,12,16）28（60,32,72）
B、（5,16,2,12）28（60,32,72）
C、（2,16,12,5）28（60,32,72）
D、（5,16,2,12）28（32,60,72）
4、在直接插入排序、希尔排序、简单选择排序、快速排序、堆排序和归并排序中，平均比较次数最少的排序方法是
第4讲 选择类排序（1）（总时长：9分16秒）随堂测验
1、对给定的数据集{84,47,25,15,21}排序，进行2趟简单选择排序的结果是（ ）
A、{15,21,25,84,47}
B、{25,47,84,15,21}
C、{21,47,25,15,84}
D、{25,15,21,47,84}
2、在以下的排序方法中，关键字比较的次数与记录的初始排列顺序无关的是（ ）
A、希尔排序
B、冒泡排序
C、直接插入排序
D、简单选择排序
3、10个元素进行简单选择排序，需要做 趟排序才能得到有序序列。
第5讲 选择类排序（2）——堆排序（总时长：19分01秒）随堂测验
1、以下序列是堆的是（ ）
A、{75,65,30,15,25,45,20,10}
B、{75,65,45,10,30,25,20,15}
C、{75,45,65,30,15,25,20,10}
D、{75,45,65,10,25,30,20,15}
2、设有1000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好用（ ）排序法。
A、冒泡排序
B、快速排序
C、堆排序
D、基数排序
3、以下序列是堆的是（ ）
A、{100,85,98,77,80,60,82,40,20,10,66}
B、{100,98,85,82,80,77,66,60,40,20,10}
C、{10,20,40,60,66,77,80,82,85,98,100}
D、{100,85,40,77,80,60,66,98,82,10,20}
4、对于待排序的数据元素集{12,13,23,18,60,15,7,20,52,100}，用筛选法建初堆时，必须从值为 的关键字开始。
第6讲 归并排序（总时长：7分20秒）随堂测验
1、下列排序方法中，辅助空间为O（n）的是（ ）
A、希尔排序
B、冒泡排序
C、堆排序
D、归并排序
2、将两个各有m个元素的有序表归并成一个有序表，其最少的比较次数是（ ）
A、m
B、2m-1
C、2m
D、m-1
第7讲 分配类排序（总时长：12分56秒）随堂测验
1、在以下的排序方法中，（ ）不需要进行关键字的比较。
A、快速排序
B、归并排序
C、基数排序
D、堆排序
2、以下排序方法中，稳定的排序是（ ）
A、堆排序
B、快速排序
C、链式基数排序
D、希尔排序
第九章 单元测验
1、n个记录采用冒泡排序，最好情况下，所需关键字的比较次数是（ ）。
A、n
B、n-1
C、n*(n-1)
D、nlogn
2、排序时扫描待排序记录序列，顺次比较相邻的两个元素的大小，逆序时就交换位置，这是（ ）排序方法的基本思想。
A、堆排序
B、直接插入排序
C、快速排序
D、冒泡排序
3、设有5000个待排序的记录关键字，如果需要用最快的方法选出其中最小的10个记录关键字，则用下列（ ）方法可以达到此目的。
A、快速排序
B、堆排序
C、归并排序
D、基数排序
4、用某种排序方法对关键字序列（25，84，21，47，15，27，68，35，20）进行排序时，序列的变化情况如下： 20，15，21，25，47，27，68，35，84 15，20，21，25，35，27，47，68，84 15，20，21，25，27，35，47，68，84 则所采用的排序方法是( )。
A、直接插入排序
B、冒泡排序
C、快速排序
D、简单选择排序
5、设一组初始记录关键字序列为(45，80，55，30，42，95)，则以第一个关键字45为基准而得到的一趟快速排序结果是（ ）。
A、30，42，45，55，80，95
B、42，30，45，55，80，95
C、30，42，45，55，80，95
D、42，30，45，95，55，80
6、在待排序的元素序列基本有序的前提下，效率最高的排序方法是（ ）
A、插入排序
B、选择排序
C、快速排序
D、归并排序
7、将关键字（46，79，56，33，40，90）按从小到大排列，则利用堆排序的方法建立的初始堆为（ ） 。
A、79，46，56，33，40，90
B、90，79，56，46，40，38
C、90，79，56，33，40，46
D、90，56，79，40，46，33
8、一趟排序结束后不一定能够选出一个元素放在其最终位置上的是（ ）。
A、堆排序
B、冒泡排序
C、直接插入排序
D、快速排序
9、快速排序在下列（ ）情况下最易发挥其长处。
A、被排序的数据元素中含有多个相同的关键字
B、被排序的数据元素已基本有序
C、被排序的数据元素完全无序
D、被排序的数据元素中的最大值和最小值相差悬殊
10、下面（ ）关键字序列符合堆的定义。
A、{96, 83, 27, 38, 11, 40}
B、{12, 36, 24, 85, 47, 30, 53, 91}
C、{12, 34, 6, 54, 23, 46}
D、{98, 86, 100, 45, 67, 34, 20}
11、以下是不稳定的排序算法是（ ）。
A、直接插入排序
B、冒泡排序
C、堆排序
D、归并排序
12、最好和最坏时间复杂度均为O(nlogn)且稳定的排序方法是( )。
A、快速排序
B、堆排序
C、基数排序
D、归并排序
13、以下是稳定的排序算法的是（ ）。
A、直接插入排序
B、希尔排序
C、简单选择排序
D、冒泡排序
14、以下是不稳定的排序算法的是（ ）。
A、归并排序
B、希尔排序
C、简单选择排序
D、堆排序
15、以下排序算法中，关键字的比较次数与元素初始序列无关的是（ ）。
A、直接插入排序
B、冒泡排序
C、简单选择排序
D、堆排序
16、内部排序要求数据元素全部在内存完成排序，且顺序存储。
17、所有的排序算法的比较次数与初始序列无关。
18、所有排序算法中，快速排序的时间复杂度和空间复杂度都最小。
19、快速排序的最坏情况，可以通过适当选择中轴元素避免。
20、排序的稳定性是指，关键字相同的记录，排序前后其领先关系不发生改变。
21、冒泡排序在最好情况下的时间复杂度是O(n)。
22、简单选择排序和堆排序性能不受初始序列顺序的影响。
23、直接插入排序、简单选择排序、冒泡排序和快速排序中，其时间复杂度为O（n*n），关键字比较次数与待排序记录的初始排列顺序无关且排序不稳定，则该排序算法是 。
24、希尔排序法、快速排序法、堆排序法和二路归并排序法四种排序法中，要求辅助空间最多的是 。
25、快速排序、归并排序、堆排序、基数排序中，适合记录个数很大，但待排序关键字位数很少的排序算法是 。
26、对关键字集合{46，79，56，33，40，90}按冒泡排序，则一趟排序后的结果为 。（请只用一个空格隔开各关键字，不必加大括号）
第1讲 数据结构的基础概念（总时长12分钟）随堂测验
1、一个抽象类型包括数据对象、 和一组处理数据的操作。
A、数据对象中各元素间的结构关系
B、数据元素集
C、接口
D、数据对象集
2、抽象数据类型具有 、信息隐蔽的特点。
第2讲 数据结构的内容（总时长5分29秒）随堂测验
1、线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。（ ）
2、1、数据结构的逻辑结构分为集合、线性、层次和 四种。
3、2、数据结构的存储结构分为 和非顺序 两种。
4、3、在线性结构、树形结构和图结构中，数据元素之间分别存在着一对一、一对多和 联系。
第3讲 数据结构与c语言表示（总时长7分32秒）随堂测验
1、当需要用一个形式参数直接改变对应实参的值时，该形式参数应说明为 。
A、与实参同类型指针参数
B、不需要参数
C、与实参同类型的参数
D、全局变量
第4讲 算法性能评价（总时长8分06秒）随堂测验
1、1、执行下面的程序段的时间复杂度为 。 for(int i=0;i<m;i++) for(int j=0;j<n;j++) a[i][j]=i*j;
A、O(
B、O(
C、O(m*n)
D、O (m+n)
2、2、执行下面程序段时，语句S的执行次数为 。 for(int i=0;i<=n;i++) for(int j=0;j<i;j++) S;
A、
B、
C、n(n+1)
D、
第5讲 算法与算法的描述（总时长14分59秒）随堂测验
1、算法设计的要求是：正确性、可读性 、 和高效率和低存储 。
A、确定性
B、健壮性
C、可行性
D、有限性
2、算法具有 有限性、确定性、 、输入、输出五大特性。
A、可行性
B、可读性
C、健壮性
D、正确性
MOOC第一章单元测试题
1、执行下面的程序段的时间复杂度为（ ）。 for(int i=0;i<m;i++) for(int j=0;j<n;j++) a[i][j]=i*j;
A、O(m2)
B、O(n2)
C、O(m*n)
D、O(m+n)
2、执行下面程序段时，语句S的执行次数为（ ）。 for(int i=0;i<=n;i++) for(int j=0;j<=i;j++) S;
A、n*n
B、n*n/2
C、(n+1)*(n+2)/2
D、n(n+1)/2
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、某算法的时间复杂度是O（n^2）,表明该算法的（ ）。
A、问题规模是n^2
B、问题规模与n^2正比
C、执行时间与n^2正比
D、执行时间等于n^2
9、若需要利用形式参数直接访问修改实参值，则应将形参说明为（ ）参数。
A、指针
B、值参数
C、实地址
D、地址参数
10、如下程序段: for(i=1;i<=n-1;i++) for(j=i+1;j<=n;j++) x=x+1; 其中语句x=x+1执行的语句频度为（ ）。
A、n*n
B、n*(n-1)/2
C、n*(n+1)/2
D、n*(n-1)
11、以下算法的时间复杂度为（ ）。 if (n >= 0) { for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) printf("输入数据大于等于零\n"); } else { for(int j = 0; j < n; j++) printf("输入数据小于零\n"); }
A、O(1)
B、O(n*n+n)
C、O(n)
D、O(n*n)
12、在数组A[0..n-1]中查找给定值K的算法大致如下： i=n-1; while(i>=0&&(A[i]!=k)) i--; return i; 该算法的时间复杂度为（ ）。
A、O(n-i+1)
B、O(n-i)
C、O(n)
D、无法确定
13、下面算法的时间复杂度为（ ）。 x=100; y=100; while(y>0) if(x>100) {x=x-10; y--;} else x++;
A、O(n)
B、O(100)
C、O(1)
D、O(n*n)
14、下面的算法是判断n是否为素数，其算法时间复杂度为（ ）。 void prime(int n) { 判断n是否是素数 */ for (i=2; i<sqrt(n) && (n % i)!=0; i++) ; if (i>sqrt(n)) printf("%d is a prime number", n); else printf("%d is not a prime number", n); }
A、O(n)
B、O(1)
C、O(sqrt(n)) sqrt表示对n取根方
D、O（n-i）
15、一个抽象数据类型包括（ ）。
A、数据对象
B、数据对象中各元素间的关系
C、数据
D、一组基本操作
16、以下属于数据元素间基本逻辑结构的是（ ）。
A、集合
B、线性
C、树
D、图
17、以下属于算法特性的是（ ）。
A、0个或多个输入
B、至少一个输出
C、正确性和有限性
D、可行性
18、算法设计的要求包括（ ）。
A、正确性
B、可读性
C、健壮性
D、高效率和低存储
19、数据元素在计算机的存储映像包括（ ）。
A、顺序存储
B、非顺序存储
C、图结构
D、树结构
20、具有线性结构的数据元素只能顺序存储，非线性结构的元素只能非顺序存储。
21、算法就是程序。
22、算法的优劣与算法描述的语言无关。
23、算法的可行性是指每一条指令具有明确含义。
24、健壮的算法不会因为非法输入而出现莫名的执行结果。
25、高效率和低存储是衡量一个算法的唯一标准。
26、数据类型就是一组性质相同的值的集合和在该集合上的一组操作的总称。
27、数据元素的存储结构分为顺序存储和非顺序存储。
28、数据元素的顺序存储优于非顺序存储。
29、一个数据结构在存储时，只需要存储数据元素即可。
MOOC第一章单元作业
1、计算下列程序段中x++的语句频度： x=1; for(int i = 0; i < n; i++) for(int j = i; j < n; j++) x++;
2、（1）简述数据元素间的四类基本逻辑结构。 （2）抽象数据类型定义。 （3）数据元素及其关系的两类存储结构与特点。
第二章 线性表（一）（总时长：72分22秒，共6讲）
第1讲 线性表的概念（总时长9分20秒）随堂测验
1、线性表是具有n个（ ）的有限序列（n>0）
A、数据对象
B、数据元素
C、字符
D、数据项
2、线性表是一个（ ）。
A、有限序列，可以为空
B、有限序列，不可以为空
C、无限序列，可以为空
D、无限序列，可以为空
3、线性表的特点是每个元素都有一个前驱和一个后继。（）
第2讲 线性表的顺序存储（总时长13分）随堂测验
1、若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（ ）(1<=i<=n+1)。
A、O(1)
B、O(n)
C、O(n*n)
D、O（
2、若长度为n的线性表采用顺序存储结构，删除第i个位置的元素，需要移动的元素个数为（ ）。
A、i
B、n-i
C、n-i+1
D、n-i-1
第3讲 线性表顺序结构应用示例及小结（总时长7分57秒）随堂测验
1、对一个长度为n的顺序表，假设在任何位置上插入一个元素的概率是相等的，那么插入一个元素时要移动表中的（ ）个元素。
A、n
B、n+1
C、
D、
2、线性表的顺序存储是指将表中元素按照从大到小或从小到大存储。
第4讲 线性表的链式存储（总时长10分20秒）随堂测验
1、通过表达式 可以获取带头结点的单链表L中首元素结点的数据值。
A、L->next
B、(L->next)->data
C、L->data
D、L->next
2、单链表中必须设有头结点。（）
第5讲 单链表的基本运算（总时长20分58秒）随堂测验
1、下列选项中， 项是链表不具有的特点。
A、插入和删除运算不需要移动元素
B、所需要的存储空间与线性表的长度成正比
C、不必事先估计存储空间大小
D、可以随机访问表中的任意元素
2、有一个带头结点的单链表HEAD，则判断其是否为空链表的表达式是
A、HEAD= =NULL
B、HEAD-〉NEXT= =NULL
C、HEAD-〉NEXT= =HEAD
D、HEAD！=NULL
3、在一个单链表中P所指结点后插入一个S所指结点时， 应执行语句： 。
A、P->next=S;S->next=P->next;
B、S->next=P->next;P->next=S;
C、S->next=P->next;P=S;
D、S->next=P;P->next=S;
第6讲 单链表运算的应用示例及小结（总时长10分47秒）随堂测验
1、设指针变量p指向单链表中结点A的直接前驱，若删除单链表中结点A，则需要修改指针的操作序列为（ ）。
A、q=p->next；p->next=q->next；free(q)；
B、q=p->next； p->next=q->next；
C、p->next=p-> next->next；
D、q=p->next；p->data=q->data；free(q)；
2、对链表进行插入和删除操作时不必移动链表中结点。( )
3、在单链表中，可以从头结点出发，查找到表中所有结点。（ ）
第二章 第一次单元测验
1、在长度为n的顺序表中的第i( 1 =< i <= n+1 )个位置上插入一个元素，其算法时间复杂度为（ ）。
A、O(logn)(以2为底)
B、O(1)
C、O(n)
D、O(n*n)
2、在长度为n的顺序表中的第i( 1 =< i <= n+1 )个位置上插入一个元素，需要移动的元素个数为（ ）。
A、n-i
B、i
C、n-i+1
D、n-i-1
3、链表不具有的特点是（ ）。
A、插入、删除不需要移动元素
B、可随机访问任一元素
C、不必事先估计存储空间
D、所需存储空间与线性表程度成正比
4、在一单链表中，删除指针p所指的后继结点，以下语句正确的是（ ）。
A、p->next=p->next->next; free(p->next);
B、free(p->next);p->next=p->next->next;
C、p=p->next;
D、s=p->next;p->next=s->next;free(s);
5、假设删除长度为n的顺序表中的每个元素的概率相同，则删除一个元素平均要移动的元素个数是（ ）。
A、n
B、(n+1)/2
C、(n-1)/2
D、n/2
6、设某顺序表中第一个元素的地址是Base，每个结点占m个单元，则第i个结点的地址为（ ）。
A、Base+(i-1)×m
B、Base+i×m
C、Base-i×m
D、Base+(i+1)×m
7、长度为n的非空线性表采用顺序存储结构，在表的第i个位置插入一个数据元素，i的合法值应该是（ ）。
A、i>0
B、1≤i≤n+1
C、1≤i≤n-1
D、0≤i≤n+1
8、非空单链表结点结构为【data,next】，若指针p所指结点是尾结点，则（ ）表达式为真。
A、p==NULL
B、p->next==NULL
C、p->next==P
D、p->next!=NULL
9、某顺序表的第一个元素的存储地址是500，每个元素占4个单元，则第8个元素的起始地址是( )。
A、504
B、508
C、516
D、528
10、在长度为n的顺序表中删除第i(1<=i<=n)个位置上的元素，需要移动的元素个数为（ ）。
A、n-i
B、n-i+1
C、n-i-1
D、i
11、单链表中增加头结点的目的是存储链表的长度。
12、静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关。
13、线性表在链式存储时，查找第i个元素的时间同i的值无关。
14、线性表在顺序存储时，查找第i个元素的时间同i 的值成正比。
15、线性表的特点是每个元素都有一个前驱和一个后继。
16、线性表的链式存储结构优于顺序存储。
17、顺序存储方式的优点是存储密度大，插入、删除效率高。
18、顺序表的每个结点只能是一个基本类型，而链表的每个结点可以是一个构造类型。
19、插入和删除操作是线性表的基本操作。这两种操作在数组中也经常使用。
20、在顺序表中，逻辑上相邻的两个元素物理存储上也一定也相邻。
21、在线性表的链式存储结构中，逻辑上相邻的两个元素在物理存储上并不一定相邻。
22、线性表采用顺序存储，必须占用一段地址连续的存储单元。
23、顺序表结构适宜进行随机访问，而链表适宜进行插入、删除。
24、若某线性表经常做插入、删除操作，易采用 结构存储。【请填 顺序 或 链式】
第二章 第一次作业
1、描述以下三个概念及其关系：头指针，头结点，首元素结点。
2、长度为n的顺序表中，假设在任何位置插入元素的概率均相等，则插入一个元素平均需要移动多少个元素？
3、简述顺序表优缺点。
4、设顺序表L是一个递增有序表，试写一算法，将x插入L中，并使L仍是一个有序表。
第二章 线性表（二）（总时长：59分37秒）
第7讲 循环链表（总时长7分05秒）随堂测验
1、有一个带头结点的循环单链表HEAD，则判断其是否为空链表的条件是 。
A、HEAD==NULL
B、HEAD-〉NEXT==NULL
C、HEAD-〉NEXT==HEAD
D、HEAD！=NULL
2、在单向循环链表中，从表中任意结点出发都可以顺着next域访问到表中所有元素（）
第8讲 双向链表（总时长7分47秒）随堂测验
1、与单链表相比，双向链表的优点之一是 。
A、插入删除操作更加方便
B、可以进行随机访问
C、可以省略表头指针和表尾指针
D、访问前后相邻结点更方便。
2、在双向链表L中，可以从任一结点p出发沿同一方向的指针域查找到表中所有元素。（）
第10讲 链式结构小结（总时长7分32）随堂测验
1、已知单链表的头指针为head且该链表不带头结点，则该单链表为空的条件是 。
A、head== NULL
B、head->next==NULL
C、head->next==head
D、head!=NULL
2、设指针变量p指向单链表中某结点的直接前驱，若删除单链表中该结点，需要修改指针的操作序列为 。
A、q=p->next； p->next=q->next；free(q)；
B、q=p->next； free(q)；
C、p->next=p->next->next；free(p->next)；
D、q=p->next； free(q)；
3、设带有头结点的单向循环链表的头指针变量为head，则其判空条件是 。
A、head==NULL
B、head->next==NULL
C、head->next==head
D、head!=NULL
4、在双向循环链表中，可以从任一结点p出发沿同一方向的指针域查找到表中所有元素。（）
第12讲 顺序表与链表的综合比较（总时长6分08秒）随堂测验
1、下列选项中， 项是链表不具有的特点。
A、插入和删除运算不需要移动元素
B、所需要的存储空间与线性表的长度成正比
C、不必事先估计存储空间大小
D、可以随机访问表中的任意元素
2、在线性表中最常用的操作是存取第i个元素及其前趋的值，可采用 存储方式最省时间？
A、顺序表
B、带头指针的双向循环链表
C、带头指针的单向循环链表
D、带头指针的单向链表
3、下面关于线性表的叙述错误的是（ ）。
A、线性表采用顺序存储必须占用一片连续的存储空间
B、线性表采用链式存储不必占用一片连续的存储空间
C、线性表采用链式存储便于插入和删除操作的实现
D、线性表采用顺序存储便于插入和删除操作的实现
总结与提高（总时长15分15秒）随堂测验
1、某线性表中最常用的操作是存取序号为i的元素和在最后进行插入和删除运算，则采用 存储方式时间性能最好。
A、双向链表
B、双向循环链表
C、单向循环链表
D、顺序表
2、已知一个带头结点的非空循环单链表，其尾指针是R，则其首元素结点的地址为：
A、R->next
B、*( R->next->next )
C、&( R->next->next )
D、R->next->next
3、线性表的顺序存储优于链式存储结构。（）
4、在带头结点的非空单链表中，头结点的存储位置由 指示
第二章 第二次单元测试
1、非空循环单链表L中，p指针指向尾结点，则以下表达式成立的是（ ）。
A、p->next==NULL
B、p==NULL
C、p->next==L
D、p==L
2、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。
A、顺序表
B、双向链表
C、带头结点的双循环链表
D、单循环链表
3、某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。
A、单链表
B、仅有头指针的单循环链表
C、双链表
D、仅有尾指针的单循环链表
4、对于双向循环链表，在两个结点之间插入一个新结点需修改的指针共（ ）个。
A、2
B、3
C、4
D、5
5、将带头指针的长度为m的单链表，链接到同样带头指针的长度为n的单链表末尾。该算法的时间复杂度为( )。
A、O(m)
B、O(n)
C、O(m+n)
D、O(m*n)
6、双向链表中有两个指针域，llink和rlink分别指向前趋及后继，设p指向链表中的一个结点，在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;q->Rlink=q;p->Llink=q;p->Llink=q;
7、带头结点的循环链表L中只有一个元素结点的条件是：________
A、L->next==L
B、L->next->next==L
C、L->next->next==L->next
D、L->next->next==NULL
8、循环单链表中，每个结点都有一个前驱和后继，因此循环单链表不是线性结构。
9、线性表在顺序存储时，查找第i个元素的时间同i的值无关。
10、线性表在顺序存储时，删除第i个元素的时间同i的值无关。
11、循环链表不是线性表。
12、在带头指针的长度为n的双向循环链表的末尾插入一个元素，其时间复杂度为O( )。（填写阿拉伯数字或字母）
13、某双向链表中，结点结构为【prior,data,next】。那么删除p指针所指结点时，需要执行语句：p->next->prior=p->prior; ; free(p);
14、在某双向链表中删除一个结点，需要改动 个指针域（填写阿拉伯数字）
15、对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为O(___)。（填阿拉伯数字或字母）
第三章 栈与队列（一）（总时长53分23秒）
第1讲 栈的定义与实现（总时长6分59秒）随堂测验
1、栈操作的特性是（ ）
A、FIFO
B、LIFO
C、FCFS
D、插入和删除操作限制在表的两端进行
2、栈中，允许进行插入和删除的一端称为（）
A、栈顶
B、栈底
C、栈头
D、栈尾
3、栈是线性结构，是操作受限制的线性表。（）
第2讲 栈的顺序结构（总时长10分54秒）随堂测验
1、1、 已知顺序栈的地址为s,此时栈不满且栈顶指示器top指向真实栈顶,执行元素x进栈操作正确的语句是（ ）
A、s->top++;s->elem[s->top]=x;
B、s->top= s->top+1;s->elem[s->top]=x;
C、s->elem[++s->top]=x;
D、s->elem[s->top]=x;s->top++;
2、2、 已知顺序栈的地址为s ,此时栈不空且栈顶指示器top指向真实栈顶，执行出栈操作并将出栈元素赋值给x所指向的单元，则下列语句中，正确的是（ ）
A、s->top--; *x= s->elem[s->top];
B、*x= s->elem[s->top]; s->top= s->top-1;
C、*x =s->elem[s->top--];
D、*x= s->elem[s->top];s->top--;
3、1、 已知顺序栈的地址为s ,此时栈不空且栈顶指示器top指向真实栈顶，执行取栈顶操作的语句是 *x= s->elem[s->top--];( )
第3讲 顺序栈的两栈共享（总时长13分19秒）随堂测验
1、已知一个双端栈的地址为dS，则该双端栈不满时，，元素x进1号栈（高端栈）操作的语句是（）
A、dS->stack[--dS->top[1]]=x;
B、dS->stack[dS->top[1]]=x;dS->top[1]--;
C、dS->top[1]--; dS->stack[dS->top[1]]=x;
D、dS->stack[++dS->top[1]]=x;
2、已知一个双端栈dStack ,则判断该双端栈栈满的条件是（）
A、dStack.top[0]+1= = dStack.top[1]
B、dStack.top[0] = = dStack.top[1]
C、dStack.top[0]-1= = dStack.top[1]
D、dStack.top[0] = = dStack.top[1]-1
3、已知一个双端栈的地址为dS，则该双端栈不空时，1号栈（高端栈）出栈操作的语句是*x= dS->stack[dS->top[1]--]（）
第4讲 栈的链式实现（总时长8分01秒）随堂测验
1、已知带头结点的链栈top, 则该链栈不空时, 出栈操作的语句是( )
A、top->next=top->next->next; *x=top->next->data;
B、*x=top->next->data; top->next=top->next->next; free(top->next);
C、*x=top ->data;p=top;top =p->next;free(p);
D、*x=top->next->data;p=top->next; top->next=p->next;free(p);
2、已知带头结点的链栈top, 则该链栈为空的条件是( )
A、top==NULL
B、top->next= =NULL
C、top->next->next= =NULL
D、top->next= =top
3、已知带头结点的链栈top, 则元素x对应的新结点s进栈操作的语句是（）
A、s->next=top->next;top->next=s;
B、top->next=s; s->next=top->next;
C、s->next=top;top =s;
D、top =s; s->next=top;
第5讲 栈的应用（总时长8分34秒）随堂测验
1、在括号匹配算法中，当正扫描检测的符号是右括号，此时的栈是空栈，则（）。
A、右括号进栈；
B、继续向下扫描；
C、取出栈顶元素做匹配检查；
D、此时出现“右括号多了”的不匹配现象。
2、在算术表达式求值的算法中，若当前正扫描的符号是运算符s，且s的优先级比运算符栈栈顶元素的优先级高，则（ ）
A、运算符栈出栈，运算数出栈，做运算；
B、s 进运算符栈；
C、取运算符栈栈顶，运算数栈顶，做运算；
D、s 进运算数栈；
3、在括号匹配算法中，当正扫描的符号是左括号时，则该做左括号（ ）。
第6讲 栈与递归（上）（总时长10分43秒）随堂测验
1、递归进层（i→i +1层）系统需要做三件事是（ ）
A、保留本层参数与返回地址；
B、保留下层参数和函数地址；
C、为被调用函数的局部变量分配存储区，给下层参数赋值；
D、将程序转移到被调函数的入口。
2、从被调用函数返回调用函数之前，递归退层（i←i +1层）系统也应完成三件工作是（ ）
A、保存被调函数的计算结果；
B、释放被调函数的数据区，恢复上层参数；
C、保存返回上层函数的地址；
D、依照被调函数保存的返回地址，将控制转移回调用函数。
3、递归是指在定义自身的同时又出现了对自身的引用。（ ）
4、系统需设立一个递归工作栈作为整个递归函数运行期间使用的数据存储区。每层递归所需信息构成一个（ ）。
第三章 单元测验
1、栈的特点是（ ）。
A、先进先出
B、先进后出
C、后进后出
D、没有顺序
2、栈之说以叫限定性线性表，是因为（ ）。
A、栈的操作位置受限制
B、栈中的元素类型受限制
C、栈的应用范围受限制
D、栈的存储结构受限制
3、输入序列为123，若进栈出栈可以交替进行，则不能可以得到的出栈序列是（ ）。
A、321
B、312
C、123
D、132
4、以下会用到栈的应用的是（ ）。
A、递归
B、子程序调用
C、括号匹配
D、其他选项均有可能
5、当利用大小为n的数组(下标从1到n)顺序存储一个栈时，假定用top==n表示栈空，则每次向这个栈插入一个元素时，首先应执行（ ）语句修改top指针。
A、top++;
B、top--;
C、top=0;
D、top=n;
6、以下属于递归求解问题的前提条件的是（ ）。
A、原问题可层层分解为子问题，且子问题比原问题规模小
B、子问题的解法与原问题解法相同
C、最小的子问题有解
D、其他选项均是
7、一个栈的输入序列为123……n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（ ）
A、i
B、n-i
C、n-i+1
D、不确定
8、有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（ ）
A、5 4 3 6 1 2
B、4 5 3 1 2 6
C、3 4 6 5 2 1
D、2 3 4 1 5 6
9、若输入序列为1234,则通过一个栈可以得到输出序列3124。
10、若输入序列为1234,则通过栈只能得到4321的输出序列。
11、顺序栈因为是顺序存储，所以可以随机存取栈中任意元素。
12、两顺序栈共享空间，也存在空间溢出问题。
13、函数或过程调用需要用到栈。
14、栈中将允许操作的一端称作 。
15、栈中将不允许操作的一端称作 。
16、凡是对元素的保存次序与使用顺序相反的，都可以使用 。
17、若栈采用单链表结构实现，则链表的头指针的位置，表示的是栈的 。（请填栈顶或栈底）
18、若栈采用顺序存储方式存储，现两栈共享空间S[1~N]，top[i]代表第i个栈( i =1,2)栈顶。栈1的底在v[1]，栈2的底在V[N]，则栈满的条件是 。(请填top[1]+top[2]==N 或者 top[1]+1==top[2] 或者top[1]==top[2] )
19、123按顺序进栈，如果进栈出栈操作可以交替，则不可能得到的出栈序列是 。(数字中间不要加空格)
20、设有一个空栈，现有输入序列为1，2，3，4，5，经过PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后，输出序列是_______。（数字之间不要加空格或标点）
第三章 作业
1、以下算法是利用栈的先进后出特性，编写的将一个十进制的数n，转换为t进制。 请在横线位置补充代码。 //参考代码 void Conversion(int n,int t) { Stack S; int x,temp=n; InitStack(&S); //将n转换为t进制 while(n>0) { x=n%t; Push(&S, x); ; } //以下为从栈中依次出栈并输出 while(!IsEmpty(&S)) { Pop(&S,&x); if(x<=9) printf("%d",x); //小于10的，按数值打印 else ; //大于10的，按字符打印 } }
2、给出栈的两种存储结构形式名称，在这两种栈的存储结构中如何判别栈满？
第三章 栈与队列（二）（总时长：52分54秒）
第7讲 栈与递归（下）（总时长：8分40秒）随堂测验
1、递归算法具有两个特性分别是（ ）
A、递归算法求解问题，方法简单。
B、递归算法效率高
C、递归算法求解问题，方法复杂
D、递归算法的效率较低
2、下列可以直接用循环结构即可将递归转换为非递归的是（ ）
A、斐波那契数列问题
B、N!问题
C、汉诺塔问题
D、尾递归问题
第8讲 队列的定义与实现（总时长：13分32秒）随堂测验
1、已知带头结点的链队列指针Q，则该队列做新元素结点s进队操作的语句是（ ）
A、Q->rear->next=s; Q->rear=s;
B、s->next=Q->front->next; Q->front->next=s;
C、Q->next=s;Q=s;
D、s->next=Q->next ;Q->next=s;
2、已知带头结点的链队列指针Q，则该非空队列取队头元素操作的语句是（ ）
A、*x=Q->next->data;
B、*x=Q->front->data;
C、*x=Q->front->next->data;
D、*x=Q->rear->data;
3、队列操作的特性是LIFO。（）
4、队列允许做插入的一端称为队头，允许删除的一端称为队尾（ ）
第9讲 序列的顺序存储（循环队列）（总时长：11分08秒）随堂测验
1、已知循环队列Q-> element[MAXSIZE],队头指示器为Q->front，队尾指示器为Q->rear（指向真实队尾的下一个位置），则该队列中元素个数为：（）
A、Q->rear-Q->front
B、Q->rear-Q->front+1
C、（Q->rear-Q->front+ MAXSIZE）% MAXSIZE
D、（Q->rear-Q->front+1+ MAXSIZE）% MAXSIZE
2、已知循环队列Q-> element[MAXSIZE],队头指示器为Q->front，队尾指示器为Q->rear（指向真实队尾的下一个位置），则该队列为空队列的条件为（ ）
A、Q->rear= =Q->front
B、Q->rear+1= =Q->front
C、（Q->rear+1）% MAXSIZE = =Q->front
D、（Q->rear-1）% MAXSIZE = =Q->front
3、已知循环队列Q-> element[MAXSIZE],队头指示器为Q->front，队尾指示器为Q->rear（指向真实队尾的下一个位置），则该队列为满队列的条件为（ ）（采用少用一个空间的方法）
A、Q->rear= =Q->front
B、Q->rear+1= =Q->front
C、（Q->rear+1）% MAXSIZE = =Q->front
D、（Q->rear-1）% MAXSIZE = =Q->front
第三章 单元测验二
1、循环队列存储在数组A[0..m-1]中，则入队时rear应该变化为（ ）
A、rear=(rear+1) mod m
B、rear++
C、rear=(rear+1) mod (m-1)
D、rear=(rear+1) mod (m+1)
2、循环队列A[0..n-1]存放其元素值，用F和R分别表示队头和队尾，则当前队列中的元素数是( )。
A、(R-F+n)%n
B、R-F+1
C、R-F-1
D、R-F
3、设栈S和队列Q的初始状态均为空，元素a,b,c,d,e,f,g依次进入栈S。如果每个元素出栈后立即进入队列Q，且7个元素出队的顺序为b,d,e,f,c,a,g，则栈S的容量至少是（ )。
A、2
B、3
C、1
D、4
4、以下属于消除递归的主要原因是（ ）。
A、递归程序时空效率较差
B、递归程序不容易理解
C、递归程序容易写错
D、其他选项均是
5、用链接方式存储的队列，在进行删除运算时（ ）。
A、仅修改头指针
B、头、尾指针可能都要修改
C、头、尾指针都要修改
D、仅修改尾指针
6、若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？( )
A、1和 5
B、2和4
C、5和1
D、4和2
7、设有一个递归算法如下 int fact(int n) { //n大于等于0 if(n<=0) return 1; else return n*fact(n-1); } 则计算fact(n)需要调用该函数的次数为（ ）。
A、n
B、n-1
C、n+1
D、n+2
8、为解决计算机主机与打印机间速度不匹配问题，通常设一个打印数据缓冲区。主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（ ）。
A、队列
B、栈
C、有序表
D、线性表
9、循环队列存储在数组A[0..m]中，则入队时的操作为（ ）。
A、rear=rear+1
B、rear=(rear+1) mod (m-1)
C、rear=(rear+1) mod m
D、rear=(rear+1)mod(m+1)
10、栈和队列的共同点是( )
A、都是先进后出
B、都是先进先出
C、只允许在端点处插入和删除元素
D、没有共同点
11、消除递归不一定需要使用栈。
12、栈和队列都是限制存取点的线性结构。
13、循环队列也存在空间溢出问题。
14、栈和队列的存储方式，既可以是顺序方式，又可以是链式方式。
15、循环队列通常用指针来实现队列的头尾相接。
16、通常使用队列来处理函数或过程的调用。
17、队列是限制插入只能在表的一端，而删除在表的另一端进行的线性表，其特点是_______。
18、在具有n个单元的循环队列中，队满时共有____个元素。
19、执行完下列语句段后，i值为：（ ） int f(int x) { return ((x>0) ? x* f(x-1):2);} int i ; i =f(f(1));
第四章 串（总时长：51分45秒）
第1讲 串的基本概念（总时长：8分38秒）随堂测验
1、设s=‘abcd’,s1=‘123’，则执行语句StrInsert( s,2,s1)后，s= .
A、‘123abcd’
B、‘a123bcd’
C、‘ab123cd’
D、‘abc123d’
2、设s=‘abcd’，则执行语句StrDelete( s,2,2)后，s= .
A、‘abcd’
B、‘abc’
C、‘ad’
D、‘a’
第2讲 串的顺序存储结构（总时长：21分04秒）随堂测验
1、假设主串S=‘aaabbbababaabb’,模式串T=‘abaa’,用串匹配算法从主串的第6个字符开始模式匹配，需要做 趟匹配，方能找到匹配串。
2、假设主串S=‘aaabbbababaabb’,模式串T=‘abaa’,用串匹配算法从主串的第6个字符开始模式匹配，在第2趟匹配中，要做 次比较。
第3讲 串的链式存储及串的应用（总时长：22分03秒）随堂测验
1、用带头结点的单链表来表示串s,则串s 为空串的条件是（ ）
A、s->next==NULL
B、s==NULL
C、s->next==s
D、s->next->next==NULL
第四章 单元测验
1、下面关于串的的叙述中，哪一个是不正确的？（ ）
A、串是字符的有限序列
B、空串是由空格构成的串
C、模式匹配是串的一种重要运算
D、串既可以采用顺序存储，也可以采用链式存储
2、设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（ ）
A、求子串
B、模式匹配
C、联接
D、求串长
3、若串S=‘soft’,其子串的数目是（ ）。
A、4
B、10
C、11
D、5
4、串的长度是指（ ）
A、串中所含不同字母的个数
B、串中所含非空格字符的个数
C、串中所含字符的个数
D、串中所含不同字符的个数
5、字符串”ABCDEFG”采用链式存储，假设每个字符占用1个字节，每个指针占用4个字节。则该字符串的存储密度为（ ）
A、20%
B、40%
C、50%
D、33.3%
6、字符串采用链式存储，假设每个字符占用1个字节，每个指针占用4个字节。若该字符串的存储密度为50%，则每个结点应存储（ ）个字符
A、2
B、3
C、4
D、1
7、串的长度是指串中不同字符的个数。
8、串是N个字母的有限序列。
9、空串不等于空格串。
10、如果两个串含相同的字符，则说明它们相等。
11、如果一个串中相同的字符均在另一个串中出现，则说明前者是后者的子串。
12、串的堆分配存储是一种动态存储结构。
第四章 单元作业
1、写一算判断其是否为回文。（即正读和倒读相同） Typedef struct{ char *ch； int length； }HString void ispalindrome(hstring s)
2、写一算法，将字符串逆置。 Typedef struct{ char *ch； int length； }HString converse(&Hstring S)
第五章 数组与广义表（上）（总时长：38分01秒）
第1讲 数组的定义与顺序存储（总时长：19分57秒）随堂测验
1、数组的维数和维度一旦确定，数组中元素的个数就确定了，不能增加不能减少。（ ）
2、数组的维数n决定了数组中的元素受n个线性关系的约束。（ ）
3、数组如同一般的线性表，可以做的基本运算包括存取指定位置的元素，插入，删除等。( )
4、假设有6行8列的二维数组A(下标从1开始),每个元素占用6个字节,存储器按字节编址。已知A的基地址为1000，数组A共占用 字节;
5、假设有6行8列的二维数组A(下标从1开始),每个元素占用6个字节,存储器按字节编址。已知A的基地址为1000 ,计算数组A的最后一个元素的地址是 。
6、假设有6行8列的二维数组A(下标从1开始),每个元素占用6个字节,存储器按字节编址。已知A的基地址为1 000 ,计算按行存储时元素A36的地址是 ;
7、假设有6行8列的二维数组A(下标从1开始),每个元素占用6个字节,存储器按字节编址。已知A的基地址为1 000 ,计算按列存储时元素A36的地址是 。
第2讲 规律分布特殊矩阵的压缩存储（总时长：18分04秒）随堂测验
1、已知一个n行n列的带状矩阵A，其中非零元素的个数是（ ）
A、3n
B、3n-2
C、3n+2
D、
2、若将n阶上三角矩阵A按列优先雅朵存放在一维数组B中，第一个非零元素存放在B[0]中，则非零元素aij存放在B[k]中，则k=( )
A、
B、
C、
D、
3、所谓的n阶下三角矩阵A是指当i<j时（i为元素的行标，j 为元素的列标）元素aij为0或常数C .( )
4、所谓的n阶（n>3）三对角矩阵（带状矩阵）是指非零元素只出现在矩阵的两条对角线上。（ ）
第五章 数组与广义表（下）（总时长：57分05秒）
第3讲 稀疏矩阵的压缩存储（上）（总时长：17分54秒）随堂测验
1、对稀疏矩阵进行压缩存储的目的是（ ）
A、便于进行矩阵运算
B、便于输入和输出
C、节省存储空间
D、减低运算的时间复杂度
2、稀疏矩阵压缩存储后，不会失去（ ）功能 输入输出
A、顺序存储
B、随机存取
C、输入输出
D、输入输出
第4讲 稀疏矩阵的压缩存储（下）（总时长：19分16秒）随堂测验
1、对于一个m行n列的稀疏矩阵中有len个非零元素，则用十字链表存储时，需要（ ）个头指针。
2、对于一个m行n列的稀疏矩阵中有len个非零元素，则用十字链表存储时，需要（ ）个三元组结点。
第5讲 广义表及本章小结（总时长：19分55秒）随堂测验
1、任意一个广义表都可以表示为由表头和表尾构成（ ）。
2、非空的广义表的表尾可能是单个元素也可能是表元素（ ）。
3、已知广义表L=(( x,y,z), a,( u,t,w)),则head( head( tail( tail( L))))的结果是（ ）。
4、已知数组M[ 1 ..10 ,-1 ..6 ,0 ..3 ], )若数组以行序为主序存储,起始地址为1 000 ,且每个数据元素占用3个存储单元,则M[ 2 ,4 ,2 ]的地址为（ ）
第五章 单元测验
1、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（ ）。
A、13
B、33
C、18
D、40
2、A[N，N]是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组T[1..N（N+1）/2]中，则对任一上三角元素a[i][j]对应T[k]的下标k是（ ）。
A、i（i-1）/2+j
B、j（j-1）/2+i
C、i（j-i）/2+1
D、j（i-1）/2+1
3、设二维数组A[1.. m，1.. n]（即m行n列）按行存储在数组B[1.. m*n]中，则二维数组元素A[i，j]在一维数组B中的下标为( )。
A、（i-1）*n+j
B、（i-1）*n+j-1
C、i*（j-1）
D、j*m+i-1
4、有一个100*90的稀疏矩阵，非0元素有11个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是（ ）。
A、60
B、66
C、18000
D、33
5、数组A[0..4,-1..-3,5..7]中含有元素的个数（ ）。
A、55
B、45
C、36
D、16
6、对稀疏矩阵进行压缩存储目的是（ ）。
A、便于进行矩阵运算
B、便于输入和输出
C、节省存储空间
D、降低运算的时间复杂度
7、广义表（（a,b,c,d））的表头是（ )。
A、a
B、（a,b,c,d）
C、（）
D、（b,c,d）
8、广义表（（a,b,c,d））的表尾是（ ）。
A、a
B、（）
C、（a,b,c,d）
D、（b,c,d）
9、设广义表L=（（a,b,c）），则L的长度和深度分别为（ ）。
A、1和1
B、1和3
C、1和2
D、2和3
10、下面说法不正确的是( )。
A、广义表的表头总是一个广义表
B、广义表的表尾总是一个广义表
C、广义表难以用顺序存储结构
D、广义表可以是一个多层次的结构
11、稀疏矩阵压缩存储后，必会失去随机存取功能。
12、一个稀疏矩阵Am*n采用三元组形式表示， 若把三元组中有关行下标与列下标的值互换，并把m和n的值互换，则就完成了Am*n的转置运算。
13、广义表的取表尾运算，其结果通常是个表，但有时也可是个单元素值。
14、若一个广义表的表头为空表，则此广义表亦为空表。
15、所谓取广义表的表尾就是返回广义表中最后一个元素。
16、广义表的同级元素（直属于同一个表中的各元素）具有线性关系。
17、一个广义表可以为其它广义表所共享。
18、已知二维数组A[1..10，0..9]中每个元素占4个单元，在按行优先方式将其存储到起始地址为1000的连续存储区域时，A[5，8]的地址是_______
19、设广义表L=(()), 则L的长度是( )。
20、设广义表L=((),()),L的深度是( )。
21、广义表(a,(a,b),d,e,((i,j),k))的长度是( )
22、广义表(a,(a,b),d,e,((i,j),k))的深度是（ ）
23、数组A[0..5,2..6,5..7]中含有元素的个数是（ ）
第六章 树和二叉树（上）（总时长：48分02秒）
第1讲 树的基本概念（总时长：17分07秒）随堂测验
1、树最适合用来表示（ ）
A、有序数据元素
B、无序数据元素
C、元素之间具有分支层次关系的数据
D、元素之间无联系的数据
2、若一棵树的广义表法表示为：A（B（E,F），C（G（H,I,J,K），L），D（M（N））） 则该树的度为（ ）；
3、若一棵树的广义表法表示为：A（B（E,F），C（G（H,I,J,K），L），D（M（N））） 该树的深度为（ ）；
4、若一棵树的广义表法表示为：A（B（E,F），C（G（H,I,J,K），L），D（M（N））） 该树中叶子结点的个数为：（ ）
第2讲 二叉树（总时长：18分04秒）随堂测验
1、按照二叉树的定义，具有3个结点的二叉树有（ ）种
A、3
B、4
C、5
D、6
2、若一棵二叉树有10个度为2的结点，5个度为1的结点，则度为0的结点有（ ）个。
A、9
B、11
C、15
D、不确定
3、一个高度为h的完全二叉树至少有（ ）个结点
A、
B、
C、
D、
4、二叉树就是结点度不大于2的树。（）
5、不存在这样的二叉树：它有n个度为0的结点，n-1个度为1的结点，n-2个度为2的结点。（ ）
6、具有n个结点的二叉树采用二叉链表存储结构，共有（ ）非空的指针域。
7、拥有100个结点的完全二叉树的最大层数是（ ）
第3讲 二叉树的遍历（总时长：12分51秒）随堂测验
1、某二叉树的先序序列和中序序列正好相同，则该二叉树一定是 （ ）
A、空树或只有一个结点
B、完全二叉树
C、每个结点都没有左子
D、高度等于其结点数
2、在二叉树中，p所指向的结点为度为1的分支点的条件是（ ）
A、p->lchild= =NULL ||p->rchild= =NULL
B、!( p->lchild! =NULL &&p->rchild!=NULL)
C、!(p->lchild= =NULL &&p->rchild= =NULL)
D、(p->lchild= =NULL &&p->rchild! =NULL)|| (p->lchild! =NULL &&p->rchild= =NULL)
3、已知二叉树的先序和后序遍历序列可以唯一确定该二叉树。（ ）
第六章 单元测验1
1、有关二叉树下列说法正确的是（ ）。
A、二叉树中每个结点的度都为2
B、一棵二叉树的度可以小于2
C、二叉树中至少有一个结点的度为2
D、二叉树中任何一个结点的度都为2
2、在一棵高度为k的满二叉树中，结点总数为（ ）。
A、
B、2k
C、
D、
3、某二叉树中有60个叶子结点，则该二叉树中度为2的结点个数为（ ）。
A、59
B、60
C、61
D、不确定
4、100个结点的完全二叉树采用顺序存储，从1开始按层次编号，则编号最小的叶子结点的编号应该是（ ）。
A、100
B、49
C、50
D、51
5、设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为（ ）
A、5
B、6
C、7
D、8
6、二叉树是非线性数据结构，所以 。
A、它不能用顺序存储结构存储;
B、它不能用链式存储结构存储;
C、顺序存储结构和链式存储结构都能存储;
D、顺序存储结构和链式存储结构都不能使用
7、完全二叉树一定存在度为1的结点。
8、完全二叉树中，若一个结点没有左孩子，则它必是叶子。
9、二叉树只能用二叉链表表示。
10、树形结构中，每个元素都有一个前驱，0个或多个后继。
11、二叉树的遍历结果不是唯一的
12、二叉树的遍历只是为了在应用中找到一种线性次序。
13、由3 个结点可以构造出 种形态不同的无序树。
14、由3 个结点可以构造出 种形态不同的二叉树。
15、对任意一棵有n个结点的树，这n个结点的度之和为 。
16、高度为7的完全二叉树，最少有 个结点。
17、具有512个结点的完全二叉树的深度为______。
18、已知二叉树有30个叶子结点，则该二叉树的总结点数至少是______。
第六章 树和二叉树（下）（总时长：112分28秒）
第4讲 遍历算法应用（总时长：19分50秒）随堂测验
1、设二叉树采用二叉链表方式存储，root指向根结点，r所指结点为二叉树中任一给定的结点。则可以通过改写（ ）算法，求出从根结点到结点r之间的路径。
A、先序遍历
B、中序遍历
C、后序遍历
D、层次遍历
2、已知二叉树用二叉链表存储，则若实现二叉树实现左右子树交换，可以借助改写（ ）遍历算法实现。
A、先序遍历
B、中序遍历
C、后序遍历
D、以上三种都可以
第5讲 基于栈的递归消除（总时长：14分27秒）随堂测验
1、在中序遍历非递归算法中，在进入子树进行访问前，需要在自定义栈中保存（ ）
A、本层根结点指针
B、本层根结点的右孩子指针
C、本层根结点的左孩子指针
D、无需保留任何信息
第6讲 线索二叉树（总时长：17分35秒）随堂测验
1、引入线索二叉树的目的是( )
A、加快查找指定遍历过程中结点的直接前驱和直接后继
B、为了能在二叉树中方便地插入和删除结点
C、为了方便找到结点的双亲
D、使二叉树遍历结果唯一
2、若判断线索二叉树中的p结点有右孩子结点则下列（）表达式为真。
A、p!=NULL
B、p->rchild!=NULL
C、p->rtag= =0
D、p->rtag= =1
3、若线索二叉树中的p结点没有左孩子结点则下列（ ）表达式为真。
A、p==NULL
B、p->lchild==NULL
C、p->ltag= =0
D、p->ltag= =1
第7讲 由遍历序列确定的二叉树（总时长：7分48秒）随堂测验
1、一棵二叉树的后序序列是：CBEFDA,中序序列是：CBAEDF,则该二叉树的先序序列是（ ）
A、ABCDEF
B、ABCEDF
C、ABDEFC
D、ABFECD
2、一棵二叉树的先序序列是：CEDBA,中序序列是：DEBAC ,则该二叉树的后序序列是（ ）
A、DABEC
B、DCBAE
C、DEABC
D、CBADE
第8讲 树、森林和二叉树的关系（总时长：17分33秒）随堂测验
1、如图所示的二叉树BT是由森林T1转换而来的二叉树，那么森林T1中有（ ）叶子结点。
A、4
B、5
C、6
D、7
2、与树等价的二叉树，根没有（ ）子树。
第9讲 哈夫曼树及其应用——哈夫曼树（总时长：12分46秒）随堂测验
1、有13个叶子结点的哈夫曼树，该树中结点总数为（ ）
A、13
B、26
C、12
D、25
2、在哈夫曼树中，权值相同的叶子点一定在同一层上。（ ）
3、在哈夫曼树中，权值较大的叶子点一般离根比较近。（ ）
4、若以{4,5,6,7,8}作为叶子点构造哈夫曼树，则其带全路径长度为（ ）
第10讲 哈夫曼树及其应用——哈夫曼编码（总时长：14分35秒）随堂测验
1、在哈夫曼编码中，当两个字符出现的频率相等时，则两个字符的哈夫曼编码也相同。（ ）
第六章 单元测验2
1、已知一棵二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBAEDF，则后序遍历的结果为（ ）。
A、CBEFDA
B、FEDCBA
C、CBEDFA
D、不确定
2、以下属于前缀编码的是（ ）。
A、{0,1,01,010,110}
B、{00,01,10,11,101}
C、{0,1101,1110,1100,1111}
D、{01,00,10,001,110,101}
3、在下列存储形式中，（ ）不是树的存储形式。
A、双亲表示法
B、孩子链表表示法
C、孩子-兄弟表示法
D、顺序存储表示法
4、对二叉树中的结点进行编号，要求根结点的编号最小，左孩子结点编号比右孩子结点编号小。则应该采用（ ）遍历方法对其进行编号。
A、先序
B、中序
C、后序
D、层次
5、已知某二叉树的后序遍历序列是CEFDBA，中序遍历序列是CBEDFA。与该二叉树对应的树或森林中，叶子的数目是（ ）个。
A、1
B、2
C、3
D、4
6、某二叉树中有60个叶子结点，则该二叉树中度为2的结点个数为（ ）。
A、59
B、60
C、61
D、不一定
7、设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（ ）。
A、M1
B、M1+M2
C、M2+M3
D、M3
8、一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ ）
A、以上答案都不对
B、499
C、500
D、502
9、一个具有1025个结点的二叉树的高h为（ ）
A、10至1024之间
B、11至1025之间
C、11
D、10
10、哈夫曼树的带权路径长度等于其中所有结点的带权路径之和。
11、给定二叉树的先序、中序和后序遍历序列中的两个，就可以唯一确定一棵二叉树。
12、在叶子数目和权值相同的所有二叉树中，带权路径长度最小的树一定是哈夫曼树。
13、将一棵树转成二叉树，根结点一定没有右子树。
14、一棵哈夫曼树中不存在度为1的结点。
15、在叶子数目和权值相同的所有二叉树中，带权路径长度最小的树一定是完全二叉树。
16、先序线索二叉树中，某结点的后继一定在左子树上。
17、哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。
18、有10个叶子结点的哈夫曼树，总结点个数是 。
19、将一棵树转换为二叉树时，遵循的规则是左孩子、 。
20、用权值{1,2,3,4,5}构造一棵哈夫曼树，则该树的带权路径长度为 。
21、假设T是一棵高度为5的二叉树,T中只有度为0和度为2的结点，那么T树最少应该有 个结点。
22、树的后根遍历，相当于对应二叉树的 遍历。
23、含有100个结点的树有 条边。
24、一棵左子树为空的二叉树在先序线索化后，其中空的链域的个数是( )
25、高度为8的完全二叉树至少有______个叶子结点。
第七章 图（总时长：102分26秒）
第1讲 图的基本概念（总时长：12分20秒）随堂测验
1、一个有n个顶点的有向图最多有 边
A、n
B、n(n-1)
C、n(n-1)/2
D、2n
2、具有n个顶点的有向图至少应有 弧才能确保是一个强连通图。
A、n-1
B、n
C、n(n-1)
D、n(n-1)/2
3、在一个无向图中，所有顶点的度之和等于边条数的 倍。
4、具有6个顶点的无向图至少应有 条边才能确保是一个连通图。
5、一个有向图G中所有顶点的入度之和是所有顶点出度之和的 倍。
第2讲 图的存储结构（总时长：12分28秒）随堂测验
1、对于一个n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小为（）
A、n
B、n(n-1)
C、
D、
2、有向图的邻接矩阵一定是对称矩阵。（）
3、用邻接矩阵存储无向图G时，其第i行中1的个数与第i列中1的个数相等。（）
4、对于一个有n个顶点，e条边的无向图，若采用邻接表表示，则表头结点数组的大小为 。
5、对于一个有n个顶点，e条边的无向图，若采用邻接表表示，则边结点有 个。
6、用邻接矩阵存储有向图G时，其第i列的所有元素之和等于该顶点的 。
第3讲 图的遍历（总时长：17分05秒）随堂测验
1、如果从一个无向图的任意一个顶点出发进行一次深度优先搜索即可访问所有顶点,则该图一定是( )
A、完全图
B、连通图
C、有回路
D、森林
2、图的深度优先遍历类似于树的（ ）遍历
A、先序遍历
B、中序遍历
C、后序遍历
D、层次遍历
3、图的广度优先遍历类似于树的（ ）遍历
A、先序遍历
B、中序遍历
C、后序遍历
D、层次遍历
第4讲 图的连通性（总时长：11分36秒）随堂测验
1、任何一个连通图（ ）生成树。
A、只有一棵
B、有一棵或多棵
C、一定有多棵
D、可能不存在
2、Prim算法适合求（ ）的最小生成树。
A、边稠密连通网
B、边稀疏连通网
C、边稠密无向网
D、边稀疏无向网
3、对于n个顶点的连通图G来说，如果其中的某个子图有n个顶点，n-1条边，则该子图一定是G的生成树。（ ）
4、对于n个顶点的连通图而言，它的生成树一定有 条边。
第5讲 有向无环图应用——拓扑排序（总时长：12分37秒）随堂测验
1、若一个有向图中的顶点不能排成一个拓扑序列，则可断定该有向图（ ）
A、是个有向无环图
B、是个含有回路的有向图
C、含有多个入度为0的顶点
D、是个强连通图
2、任何有向无环图的顶点都可以排成拓扑排序序列，且拓扑排序序列唯一（ ）
3、在ＡＯＶ网中，顶点表示 。
第6讲 有向无环图应用——关键路径（总时长：15分21秒）随堂测验
1、关键路径是ＡＯE网中（ ）
A、从源点到汇点的最长路径
B、从源点到汇点的最短路径
C、最长回路
D、最短回路
2、关键活动若不能按期完成就会影响整个工程的完成时间，若某些关键活动能提前完成，将可能使整个工程提前完成。（）
3、在ＡＯE网中，关键路径上的活动称为 。
第7讲 最短路径（总时长：16分28秒）随堂测验
1、求最短路径的Dijkstra算法的时间复杂度为（ ） n为图中顶点数，e为图中边数。
A、O（n）
B、O（n+e）
C、O（
D、O(ne)
2、求最短路径的Dijkstra算法不适用于有回路的有向网（ ）
第七章 单元测验
1、在一个图中，所有顶点的度之和是所有边数的 ( )倍。
A、1/2
B、1
C、2
D、3
2、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的( )倍。
A、1/2
B、1
C、2
D、4
3、一个有n个顶点的无向图最多有( )条边。
A、n
B、n*(n-1)
C、( n*(n-1) ) / 2
D、2*n
4、在一个具有n个顶点的无向图中，要连通全部顶点至少需要 ( )条边。
A、n
B、n+`
C、n-1
D、n/2
5、对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是( )。
A、n
B、n*n
C、2*(n-1)
D、n-1
6、对于一个具有n个顶点和e条边的无向图，若采用邻接表示，邻接表中的结点总数是( )。
A、e/2
B、2
C、2*e
D、n+e
7、以下说法错误的是( )。
A、用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关。
B、邻接表只能用于有向图的存储，而邻接矩阵对于有向图和无向图的存储都适用。
C、存储无向图的邻接矩阵是对称的，因此只要存储邻接矩阵的下（或上）三角部分就可以了
D、用邻接矩阵M表示图，判定任意两个结点Vi和Vj之间是否有长度为n的路径相连，则只要检查M的n次方后，第 i行第j列的元素是否为0即可。
8、已知一个图的邻接矩阵表示，删除所有从第i个顶点出发的方法是（ ）。
A、将矩阵第i行删除，后序行上移
B、将矩阵第i列删除，后序列左移
C、将矩阵第i行上的元素全部置0
D、将矩阵第i列上的元素全部置0
9、某图的邻接表存储结构如下图所示， 则从6号点出发，深度优先遍历的序列是（ ）
A、6-5-2-1-4-3
B、6-5-1-2-4-3
C、6-5-1-4-3-2
D、6-5-2-1-4-3
10、某图的邻接矩阵存储结构如下图所示， 则从6号点出发，广度优先遍历的序列是（ ）
A、6-1-2-5-4-3
B、6-1-2-4-5-3
C、6-5-1-4-3-2
D、6-5-2-1-4-3
11、关键路径上的活动都是关键活动，它们是否按时完成会影响工期。
12、求稀疏图的最小生成树，用克鲁斯卡尔算法来求解较好。
13、求稠密图的最小生成树，用普里姆算法来求解较好。
14、迪杰斯特拉算法求最短路径时，是按照路径长度递增的顺序求解的。
15、一个有向图的拓扑排序只有一个。
16、每一个有向图肯定至少有一个拓扑排序。
17、具有6个顶点的无向图至少应有6条边才能确保是一个连通图。
18、非关键活动，可以无限期延迟。
19、图的存储结构主要有邻接矩阵和________两种。
20、对具有n个顶点的图其生成树有且仅有________条边。
21、在有向图的邻接矩阵上，第i行中的非零且非无穷元素个数是第i个结点的 。
22、如果n个顶点的图是一个环，则它有 棵生成树。
23、关键路径是从源点到汇点的 路径。
24、稠密图采用 存储较省空间
25、稀疏图采用 存储较省空间。
第八章 查找（总时长：73分53秒）
第1讲 查找的基本概念（总时长：10分31秒）随堂测验
1、采用顺序查找法查找长度为n的线性表时，平均查找长度为 。
A、n
B、
C、
D、
2、通常将 作为衡量一个查找算法效率优劣的标准。
A、平均查找长度
B、比较次数
C、WPL
D、ASL
3、顺序查找方法只能在顺序存储结构上进行。（ ）
4、顺序查找含n个元素的顺序表，若查找成功，则比较关键字的次数最多为 次。
5、顺序查找含n个元素的顺序表，若查找不成功，则比较关键字的次数为 次。
第2讲 基于线性表的查找法（总时长：10分44秒）随堂测验
1、对列表进行折半查找时，要求列表必须 。
A、顺序存储
B、链式存储
C、顺序存储且元素按关键字有序存储
D、链式存储且元素按关键字有序存储
2、当采用分块查找时，数据的组织方式要求 。
A、数据分成若干块，每块内元素有序
B、数据分成若干块，每块内元素不必有序，但块间必须有序，且每块内最大（或最小）的数据组成索引块；
C、数据分成若干块
D、数据分成若干块，每块（除最后一块外）中元素个数相等。
3、有一个有序表{1,3,9,12,32,41，45,62,75,77,82,95,99}当采用折半查找法查找关键字为82的元素时，需经过 次比较后查找成功。
A、1
B、2
C、4
D、8
4、折半查找可以在有序的双向链表上进行。（ ）
第3讲 树表式查找方法——二叉排序树（总时长：12分08秒）随堂测验
1、如图所示的二叉排序树，，起查找成功时的平均查找长度是 。
A、
B、
C、
D、
2、在一棵平衡二叉树中，每个结点的平衡因子的取值范围是 。
A、-1——1
B、-2——2
C、1——2
D、0——1
3、查找效率最高的二叉排序树是平衡二叉排序树。（ ）
4、在二叉排序树中新插入的结点总是作为叶子结点来插入的。（ ）
5、在二叉排序树中新插入的结点总是处于最底层。（ ）
6、每个结点的关键字都比左孩子关键字大，比右孩子关键字小，这样的二叉树都是二叉排序树。（ ）
第4讲 计算式查找法——哈希表的构造（总时长：16分27秒）随堂测验
1、将10个元素散列到10000000个单元的哈希表中，则 产生冲突。
A、一定会
B、一定不会
C、仍可能会
D、以上都不对
2、在哈希查找中，可用 来处理冲突。
A、除留余数法
B、数字分析法
C、线性探测散列法
D、数字分析法
3、设哈希表长度m=12，哈希函数为H（key）=key mod 11.表中已经有4个结点分别为H（15）=4，H(38)=5, H（61）=6，H(84)=7,其余地址为空。如果用二次探测再散列处理冲突，则关键字为49的结点地址为 。
A、8
B、3
C、5
D、9
4、设哈希表长度m=14,哈希函数H（key）=key mod p,则p最好取 。
第5讲 哈希法的性能分析（总时长：9分02秒）随堂测验
1、若采用链地址法构造哈希表并处理冲突，哈希函数为H（key）=key mod 17，则需要 个链表。
A、17
B、16
C、13
D、不确定
2、假设有k个关键字互为同义词，若用线性探测再散列法将这k个关键字存入哈希表中，至少要进行 次定址。
A、k-1
B、k
C、k+1
D、k(k+1)/2
3、哈希表的查找性能 。
A、与处理冲突的方法有关而与表的长度无关
B、与处理冲突的方法无关而与表的长度有关
C、与处理冲突的方法无关而与装填因子有关
D、与处理冲突的方法有关，与装填因子有关
第八章 单元测验
1、用二分（对半）查找表的元素的速度比用顺序法( )
A、必然快
B、必然慢
C、相等
D、不能确定
2、具有12个关键字的有序表，折半查找的平均查找长度（ ）
A、3.1
B、4
C、2.5
D、5
3、设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链地址法构造散列表，散列函数为H（key）=key MOD 13,散列地址为1的链中有（ ）个记录。
A、1
B、2
C、3
D、4
4、下面关于哈希(Hash，杂凑)查找的说法正确的是( )
A、哈希函数构造的越复杂越好，因为这样随机性好，冲突小
B、除留余数法是所有哈希函数中最好的
C、不存在特别好与坏的哈希函数，要视情况而定
D、若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单的将该元素删去即可
5、散列表的地址区间为0-17,散列函数为H(K)=K mod 17。采用线性探测法处理冲突，并将关键字序列26，25，72，38，8，18，59依次存储到散列表中。元素59存放在散列表中的地址是（ ）。
A、8
B、9
C、10
D、11
6、散列函数有一个共同的性质，即函数值应当以( )取其值域的每个值。
A、最大概率
B、最小概率
C、平均概率
D、同等概率
7、分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( )
A、（100，80， 90， 60， 120，110，130）
B、（100，120，110，130，80， 60， 90）
C、（100，60， 80， 90， 120，110，130）
D、(100，80， 60， 90， 120，130，110)
8、二叉查找树的查找效率与二叉树的树型有关, 在 ( )时其查找效率最低。
A、结点太多
B、完全二叉树
C、呈单枝树
D、结点太复杂。
9、采用线性探测法处理散列时的冲突，当从哈希表删除一个记录时，不应将这个记录的所在位置置空，因为这会影响以后的查找。
10、在散列检索中，“比较”操作一般也是不可避免的。
11、散列函数越复杂越好，因为这样随机性好，冲突概率小.
12、哈希函数的选取平方取中法最好。
13、Hash表的平均查找长度与处理冲突的方法无关。
14、负载因子 (装填因子)是散列表的一个重要参数，它反映散列表的装满程度。
15、散列法的平均检索长度不随表中结点数目的增加而增加，而是随负载因子的增大而增大。
16、完全二叉树肯定是平衡二叉树。
17、对一棵二叉排序树按前序方法遍历得出的结点序列是从小到大的序列。
18、在任意一棵非空二叉排序树中，删除某结点后又将其插入，则所得二排序叉树与原二排序叉树相同
19、在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找关键码值20，需做的关键码比较次数为____.
20、在有序表A[1..20]中，按二分查找方法进行查找，查找长度为5的元素个数是__________
21、顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为__ __次
第九章 内部排序（总时长：97分05秒）
第2讲 插入类排序（总时长：14分05秒）随堂测验
1、对数据序列{15,9,7,8,20,-1,4}进行排序，进行一趟后的结果为：{9,15,7,8,20,-1,4}，则采用的是（ ）排序方法。
A、简单选择排序
B、冒泡排序
C、直接插入排序
D、堆排序
2、下列排序方法中，（ ）在初始序列已基本有序的情况下，排序效率最高。
A、归并排序
B、直接插入排序
C、快速排序
D、堆排序
3、用希尔排序对{Q,H,C,Y,Q,A,M,S,R,D,F,X},进行排序，第一趟的增量是4，则第一趟排序后的结果是（ ）
A、{H,Q, C,Y,Q,A,M,S,R,D,F,X}
B、{Q,A,C,S,Q,D,F,X,R,H,M,Y}
C、{H,C,Q,Q,A,M,S,R,D,F,X,Y}
D、{ A,H,C,Y,Q,Q,M,S,R,D,F,X}
4、设用希尔排序对{98,36,-9,0,47,23,1,8,10,7}进行排序，给出的增量序列依次是4,2,1，则排序需要进行 趟。
第3讲 交换类排序（总时长：12分01秒）随堂测验
1、快速排序在（ ）情况下最不利于发挥其长处。
A、要排序的数据量太大
B、要排序的数据中含有多个相同的值
C、要排序的数据个数是奇数
D、要排序的数据基本有序
2、以下（ ）法在数据基本有序时效率最好。
A、快速排序
B、冒泡排序
C、堆排序
D、希尔排序
3、对关键字{28,16,32,12,60,2,5,72}进行快速排序，第一趟以28为枢轴产生的划分结果为（ ）
A、（2,5,12,16）28（60,32,72）
B、（5,16,2,12）28（60,32,72）
C、（2,16,12,5）28（60,32,72）
D、（5,16,2,12）28（32,60,72）
4、在直接插入排序、希尔排序、简单选择排序、快速排序、堆排序和归并排序中，平均比较次数最少的排序方法是
第4讲 选择类排序（1）（总时长：9分16秒）随堂测验
1、对给定的数据集{84,47,25,15,21}排序，进行2趟简单选择排序的结果是（ ）
A、{15,21,25,84,47}
B、{25,47,84,15,21}
C、{21,47,25,15,84}
D、{25,15,21,47,84}
2、在以下的排序方法中，关键字比较的次数与记录的初始排列顺序无关的是（ ）
A、希尔排序
B、冒泡排序
C、直接插入排序
D、简单选择排序
3、10个元素进行简单选择排序，需要做 趟排序才能得到有序序列。
第5讲 选择类排序（2）——堆排序（总时长：19分01秒）随堂测验
1、以下序列是堆的是（ ）
A、{75,65,30,15,25,45,20,10}
B、{75,65,45,10,30,25,20,15}
C、{75,45,65,30,15,25,20,10}
D、{75,45,65,10,25,30,20,15}
2、设有1000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好用（ ）排序法。
A、冒泡排序
B、快速排序
C、堆排序
D、基数排序
3、以下序列是堆的是（ ）
A、{100,85,98,77,80,60,82,40,20,10,66}
B、{100,98,85,82,80,77,66,60,40,20,10}
C、{10,20,40,60,66,77,80,82,85,98,100}
D、{100,85,40,77,80,60,66,98,82,10,20}
4、对于待排序的数据元素集{12,13,23,18,60,15,7,20,52,100}，用筛选法建初堆时，必须从值为 的关键字开始。
第6讲 归并排序（总时长：7分20秒）随堂测验
1、下列排序方法中，辅助空间为O（n）的是（ ）
A、希尔排序
B、冒泡排序
C、堆排序
D、归并排序
2、将两个各有m个元素的有序表归并成一个有序表，其最少的比较次数是（ ）
A、m
B、2m-1
C、2m
D、m-1
第7讲 分配类排序（总时长：12分56秒）随堂测验
1、在以下的排序方法中，（ ）不需要进行关键字的比较。
A、快速排序
B、归并排序
C、基数排序
D、堆排序
2、以下排序方法中，稳定的排序是（ ）
A、堆排序
B、快速排序
C、链式基数排序
D、希尔排序
第九章 单元测验
1、n个记录采用冒泡排序，最好情况下，所需关键字的比较次数是（ ）。
A、n
B、n-1
C、n*(n-1)
D、nlogn
2、排序时扫描待排序记录序列，顺次比较相邻的两个元素的大小，逆序时就交换位置，这是（ ）排序方法的基本思想。
A、堆排序
B、直接插入排序
C、快速排序
D、冒泡排序
3、设有5000个待排序的记录关键字，如果需要用最快的方法选出其中最小的10个记录关键字，则用下列（ ）方法可以达到此目的。
A、快速排序
B、堆排序
C、归并排序
D、基数排序
4、用某种排序方法对关键字序列（25，84，21，47，15，27，68，35，20）进行排序时，序列的变化情况如下： 20，15，21，25，47，27，68，35，84 15，20，21，25，35，27，47，68，84 15，20，21，25，27，35，47，68，84 则所采用的排序方法是( )。
A、直接插入排序
B、冒泡排序
C、快速排序
D、简单选择排序
5、设一组初始记录关键字序列为(45，80，55，30，42，95)，则以第一个关键字45为基准而得到的一趟快速排序结果是（ ）。
A、30，42，45，55，80，95
B、42，30，45，55，80，95
C、30，42，45，55，80，95
D、42，30，45，95，55，80
6、在待排序的元素序列基本有序的前提下，效率最高的排序方法是（ ）
A、插入排序
B、选择排序
C、快速排序
D、归并排序
7、将关键字（46，79，56，33，40，90）按从小到大排列，则利用堆排序的方法建立的初始堆为（ ） 。
A、79，46，56，33，40，90
B、90，79，56，46，40，38
C、90，79，56，33，40，46
D、90，56，79，40，46，33
8、一趟排序结束后不一定能够选出一个元素放在其最终位置上的是（ ）。
A、堆排序
B、冒泡排序
C、直接插入排序
D、快速排序
9、快速排序在下列（ ）情况下最易发挥其长处。
A、被排序的数据元素中含有多个相同的关键字
B、被排序的数据元素已基本有序
C、被排序的数据元素完全无序
D、被排序的数据元素中的最大值和最小值相差悬殊
10、下面（ ）关键字序列符合堆的定义。
A、{96, 83, 27, 38, 11, 40}
B、{12, 36, 24, 85, 47, 30, 53, 91}
C、{12, 34, 6, 54, 23, 46}
D、{98, 86, 100, 45, 67, 34, 20}
11、以下是不稳定的排序算法是（ ）。
A、直接插入排序
B、冒泡排序
C、堆排序
D、归并排序
12、最好和最坏时间复杂度均为O(nlogn)且稳定的排序方法是( )。
A、快速排序
B、堆排序
C、基数排序
D、归并排序
13、以下是稳定的排序算法的是（ ）。
A、直接插入排序
B、希尔排序
C、简单选择排序
D、冒泡排序
14、以下是不稳定的排序算法的是（ ）。
A、归并排序
B、希尔排序
C、简单选择排序
D、堆排序
15、以下排序算法中，关键字的比较次数与元素初始序列无关的是（ ）。
A、直接插入排序
B、冒泡排序
C、简单选择排序
D、堆排序
16、内部排序要求数据元素全部在内存完成排序，且顺序存储。
17、所有的排序算法的比较次数与初始序列无关。
18、所有排序算法中，快速排序的时间复杂度和空间复杂度都最小。
19、快速排序的最坏情况，可以通过适当选择中轴元素避免。
20、排序的稳定性是指，关键字相同的记录，排序前后其领先关系不发生改变。
21、冒泡排序在最好情况下的时间复杂度是O(n)。
22、简单选择排序和堆排序性能不受初始序列顺序的影响。
23、直接插入排序、简单选择排序、冒泡排序和快速排序中，其时间复杂度为O（n*n），关键字比较次数与待排序记录的初始排列顺序无关且排序不稳定，则该排序算法是 。
24、希尔排序法、快速排序法、堆排序法和二路归并排序法四种排序法中，要求辅助空间最多的是 。
25、快速排序、归并排序、堆排序、基数排序中，适合记录个数很大，但待排序关键字位数很少的排序算法是 。
26、对关键字集合{46，79，56，33，40，90}按冒泡排序，则一趟排序后的结果为 。（请只用一个空格隔开各关键字，不必加大括号）