1.5测验1、【单选题】下列关于数据的逻辑结构的叙述中，哪一个是不正确的（ ）。
a、数据的逻辑结构是数据间关系的描述
b、数据的逻辑结构抽象反映数据元素间的逻辑关系
c、数据的逻辑结构具体反映数据在计算机中的存储方式
d、数据的逻辑结构分为线性结构和非线性结构
2、【单选题】以下关于数据的存储结构的叙述中哪一条是正确的（ ）。
a、数据的存储结构是数据间关系的抽象描述
b、数据的存储结构是逻辑结构在计算机存储器中的实现
c、数据的存储结构分为线性结构和非线性结构
d、数据的存储结构对数据运算的具体实现没有影响
3、【单选题】按照数据结构中对数据类型的定义，c语言中的复合数据类型指的是（ ）。
a、整型
b、结构型
c、字符型
d、实型
4、【单选题】伪代码是（ ）。
a、能够方便描述算法中的分支与循环等结构化语句
b、描述算法且容易理解的一种语言
c、不能直接编译或解释执行
d、以上都正确
5、【单选题】下面说法错误的是（ ）
a、算法原地工作的含义是指不需要任何额外的辅助空间
b、在相同的规模n下，复杂度o(n)的算法在时间上总是优于复杂度o(2n)的算法
c、所谓时间复杂度是指最坏情况下估算算法执行时间的一个上界
d、同一个算法，实现语言的级别越高，执行效率就越低
6、【单选题】从逻辑上可以把数据结构分为（ ）两大类。
a、动态结构、静态结构
b、顺序结构、链式结构
c、线性结构、非线性结构
d、初等结构、构造型结构
7、【单选题】在下面的程序段中，语句x=x 1的频度为（ ） for (i=1;i<= n;i ) for (j=1;j<= n;j ) x=x 1;
a、2n
b、n
c、n2
d、log2n
8、【单选题】程序段 for (i=n;i>0;i--) for (j=1;j
a[j 1]) swap(a[j],a[j 1]); //将a[j]与a[j 1]对换 其中 n为正整数，则在最坏情况下算法的时间复杂度是（ ）
a、o(n)
b、o(nlogn)
c、o(n3)
d、o(n2)
9、【单选题】以下数据结构中，（ ）是非线性结构。
a、树
b、字符串
c、队列
d、栈
10、【填空题】数据的逻辑结构是指 。
11、【填空题】数据的 在计算机中的表示（映像）称为存储结构，需要考虑数据元素的表示和数据元素间关系的表示。数据的存储结构分为 、 、索引和散列存储结构。
12、【填空题】评价算法的两个重要指标是 。
13、【填空题】一个算法具有5个特性： , , ，有零个或多个输入、有一个或多个输出。
14、【填空题】在下面的程序段中，对下划线语句的频度为 。 for (int i = 1; i <= n; i ) for (int j = 1; j <= n; j ) { c[i][j] = 0.0; for (int k = 1; k <= n; k ) c[i][j] = c[i][j] a[i][k] * b[k][j]; }
15、【填空题】在下面的程序段中，对x 语句的频度为 （表示为n的函数） for (i=1;i<=n;i ) for (j=1;j<=i;j ) for (k=1;k<=j;k ) x ； 1 (1 2) (1 2 3) …… (1 2 3 …… n)=。
16、【填空题】下面程序段中带下划线的语句的执行次数的数量级是 。 i=1； while( i
17、【填空题】下面程序段中x 的语句的执行次数的数量级是 。 i=1； while( i
18、【判断题】数据元素是数据的最小单位。
19、【判断题】数据项是数据不可分割的最小单位。
20、【判断题】数据的逻辑结构是指数据的各数据项之间的逻辑关系；
21、【判断题】算法的优劣与算法描述语言无关。
22、【判断题】健壮的算法不会因非法的输入数据而出现莫名其妙的状态。
23、【判断题】算法可以用不同的语言描述，如果用c 语言或c 语言等高级语言来描述，则算法实际上就是程序了。
24、【判断题】程序一定是算法。
25、【判断题】数据的物理结构是指数据在计算机内的实际存储形式。
26、【判断题】数据的逻辑结构说明数据元素之间的逻辑关系,它依赖于计算机的存储结构.
27、【判断题】数据结构的操作的定义与具体实现有关。
28、【判断题】抽象数据类型的定义仅取决于它的一组逻辑特性，而与在计算机内部如何表示和实现无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部使用。
29、【判断题】算法的时间复杂度仅与问题的规模相关。
1.6作业
1、【简答题】什么是数据? 它与信息是什么关系?
2、【简答题】什么是数据结构? 有关数据结构的讨论涉及哪三个方面?
3、【简答题】数据的逻辑结构分为线性结构和非线性结构两大类。线性结构包括数组、链表、 栈、队列等; 非线性结构包括树、图等，这两类结构各自的特点是什么？
4、【简答题】数据类型和抽象数据类型是如何定义的？抽象数据类型的主要特点是什么？使用抽象数据类型的主要好处是什么？
5、【简答题】什么是算法? 算法的5个特性是什么? 试根据这些特性解释算法与程序的区别。
6、【简答题】可以从哪几个方面评价一个算法的优劣？
7、【简答题】有实现同一功能的两个算法a1和a2，其中a1的时间复杂度为tl=o(2n)，a2的时间复杂度为t2=o(n2)，就时间复杂度而言，这两个算法哪一个好？
2.5测验
1、【单选题】线性表的顺序存储结构的优点是( )
a、存储密度大
b、插入运算方便
c、删除运算方便
d、可方便地用于各种逻辑结构的存储表示
2、【单选题】下面关于线性表的叙述中，错误的是( )
a、线性表采用顺序存储，必须占用一片连续的存储单元
b、线性表采用顺序存储，便于进行插入和删除操作
c、线性表采用链接存储，不必占用一片连续的存储单元
d、线性表采用链接存储，便于插入和删除操作
3、【单选题】线性表是具有n个（ ）的有限序列（n≥0）。
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、【单选题】若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（ ）(1≤i≤n 1)。
a、o(0)
b、o(1)
c、o(n)
d、o()
10、【单选题】对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（ ）。
a、o(n) o(n)
b、o(n) o(1)
c、o(1) o(n)
d、o(1) o(1)
11、【单选题】线性表（a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂度为（ ）。
a、o（i）
b、o（1）
c、o（n）
d、o（i-1）
12、【单选题】非空的循环单链表head的尾结点p满足（ ）。
a、p->next==head
b、p->next==null
c、p==null
d、p= head
13、【单选题】在单链表指针为p的结点之后插入指针为s的结点，正确的操作是（ ）。
a、p->next=s;s->next=p->next;
b、s->next=p->next;p->next=s;
c、p->next=s;p->next=s->next;
d、p->next=s->next;p->next=s;
14、【单选题】对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（ ）。
a、head==null
b、head->next==null
c、head->next==head
d、head!=null
15、【单选题】完成在非空双向循环链表结点p之后插入s的操作是（ ）。
a、p->next=s ; s->prior=p; p->next->prior=s ; s->next=p->next;
b、p->next->prior=s; p->next=s; s->prior=p; s->next=p->next;
c、s->prior=p; s->next=p->next; p->next=s; p->next->prior=s ;
d、s->next=p->next; p->next->prior=s ; s->prior=p; p->next=s;
16、【单选题】在双向循环链表中，删除p所指的结点时须修改指针（ ）。
a、p->prior->next=p->next； p->next->prior=p->prior;
b、p->prior=p->prior->prior ； p->prior->next=p;
c、p->next->prior=p； p->next=p->next->next;
d、p->next=p->prior->prior； p->prior=p->next->next;
17、【填空题】当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用 存储结构。
18、【填空题】线性表l=（a1,a2,…,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是 。
19、【填空题】设单链表的结点结构为(data,next)，next为指针域，已知指针px指向单链表中data为x的结点，指针py指向data为y的新结点 , 若将结点y插入结点x之后，则需要执行以下语句:
20、【填空题】在一个长度为n的顺序表中第i个位置（1≤i≤n 1）插入一个元素时，需向后移动 个元素。
21、【填空题】在单链表中设置头结点的作用是 .
22、【填空题】顺序存储结构是通过 表示元素之间的逻辑关系的;链式存储结构是通过 表示元素之间的逻辑关系的。
23、【填空题】对于双向链表，在两个结点之间插入一个新结点需修改的指针共 个，对于单链表，在两个结点之间插入一个新结点需修改的指针共 个。
24、【填空题】循环单链表的最大优点是： 。
25、【填空题】在单链表l中，指针p所指结点是尾结点的条件是： 。
26、【填空题】带头结点的双循环链表l为空表的条件是： 。
27、【判断题】链表中的头结点仅起到标识的作用。
28、【判断题】顺序存储结构的主要缺点是不利于插入或删除操作。
29、【判断题】线性表采用链表存储时，结点之间的存储空间可以是不连续的。
30、【判断题】顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。
31、【判断题】线性表的特点是每个元素都有一个直接前驱和一个直接后继。
32、【判断题】取线性表的第i个元素的时间同i的大小有关。
33、【判断题】循环链表不是线性表。
34、【判断题】线性表就是顺序存储的表。
35、【判断题】为了方便地插入和删除数据，可以使用双向链表存放数据。
36、【判断题】顺序存储方式的优点是存储密度大，且插入、删除运算效率高。
2.6作业
1、【简答题】线性表有两种存储结构：一是顺序表，二是链表。试问： （1）如果有 n个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表的总数也会自动地改变。在此情况下，应选用哪种存储结构？ 为什么？ （2）若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么应采用哪种存储结构？为什么？
2、【简答题】线性表的顺序存储结构具有三个弱点：其一，在作插入或删除操作时，需移动大量元素；其二，由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用；其三，表的容量难以扩充。线性表的链式存储结构是否一定都能够克服上述三个弱点，试讨论之。
3、【简答题】设顺序表长为n，在表中插入、删除元素需要移动元素，问： （1）在等概率情形下, 在顺序表中插入一个元素, 平均需要移动多少个元素? （2）在等概率情形下, 在顺序表进行删除一个元素, 平均需要移动多少个元素?
4、【论述题】已知线性表（a1 a2 a3 …an）按顺序存于内存，每个元素都是非零整数，试设计用最少时间把所有值为负数的元素移到全部正数值元素前边的算法：例：（x,-x,-x,x,x,-x …x）变为（-x,-x,-x…x,x,x）。
5、【论述题】试编写在带头结点的单链表l中删除（一个）最小值结点的（高效）算法。
6、【论述题】对线性表l=（a1...an） (1)如l为顺序表，请设计算法将l就地逆置。 (2)若l为带头结点的单链表，设计算法将l就地逆置。
7、【论述题】设有一个带头结点的单链表，其结点的数据值均为正整数，编写完成下列功能的算法： (1)找出最小值结点，且输出该数值； (2)若该数值是奇数，则将其与直接后继结点的数值交换； (3)若该数值是偶数，则将其直接后继结点删除。
8、【论述题】假设有两个按元素值非递减次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值非递增次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。
3.5测验
1、【单选题】栈对数据的操作原则是（ ）。
a、先进先出
b、后进先出
c、后进后出
d、不分顺序
2、【单选题】一个栈的输入序列为1, 2, 3,…,n，若输出序列的第1个元素是n，则第i（1≤i≤n）个输出的元素是（ ）。
a、不确定
b、n-i 1
c、i
d、n-i
3、【单选题】有6个元素以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
4、【单选题】输入序列为abc，可以变为cba时，经过的栈操作为（ ）。
a、push,pop,push,pop,push,pop
b、push,push,push,pop,pop,pop
c、push,push,pop,pop,push,pop
d、push,pop,push,push,pop,pop
5、【单选题】栈在（ ）中应用。
a、递归调用
b、括号匹配的检查
c、表达式求值
d、其他都对
6、【单选题】一个递归算法必须包括（ ）。
a、递归部分
b、终止条件和递归部分
c、迭代部分
d、终止条件和迭代部分
7、【单选题】表达式a*(b c)-d的后缀表达式是（ ）。
a、abcd* -
b、abc *d-
c、abc* d-
d、- *abcd
8、【单选题】设计一个判别表达式中左，右括号是否配对出现的算法，采用（ ）数据结构最佳。
a、线性表的顺序存储结构
b、队列
c、线性表的链式存储结构
d、栈
9、【单选题】用链接方式存储的队列，在进行删除运算时（ ）。
a、仅修改头指针
b、仅修改尾指针
c、头、尾指针都要修改
d、头、尾指针可能都要修改
10、【单选题】循环队列a[0..m-1]存放其元素值，用整型变量front和rear分别表示队头和队尾指针，则当前队列中的元素个数是（ ）。
a、(rear-front m)%m
b、rear-front 1
c、rear-front-1
d、rear-front
11、【单选题】栈和队列都是（ ）。
a、顺序存储的线性结构
b、链式存储的非线性结构
c、限制存取点的线性结构
d、限制存取点的非线性结构
12、【单选题】设栈s和队列q的初始状态为空，元素e1,e2,e3,e4,e5和e6依次通过栈s，一个元素出栈后即进队列q，若6个元素出队的序列是e2,e4,e3,e6,e5,e1，则栈s的容量至少应该是（ ）。
a、6
b、4
c、3
d、2
13、【填空题】栈是 的线性表，其运算遵循后进先出的原则。
14、【填空题】一个栈的输入序列是：1 2 3，则不可能的栈输出序列是 。
15、【填空题】为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的内存空间时，应将两栈的 分别设在这片内存空间的两端，这样栈满的条件是： 。
16、【填空题】多个栈共存时，最好用 存储结构。
17、【填空题】用s表示入栈操作，x表示出栈操作，若元素入栈的顺序为1234，为了得到1342出栈顺序，相应的s和x的操作串序列为： 。
18、【填空题】循环队列的引入，目的是 。
19、【填空题】表达式求值是 应用的一个典型例子。
20、【填空题】已知循环队列q.base[0..m-1]，队首和队尾指针分别为q.front和q.rear，队列满的条件是 。队列空的条件 。
21、【填空题】在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中依次取出数据打印，该缓冲区是一个 结构。
22、【判断题】消除递归不一定需要使用栈。
23、【判断题】栈是实现过程和函数等子程序所必需的结构。
24、【判断题】栈和队列都是限制存取点的线性结构。
25、【判断题】通常使用队列来处理函数或过程的调用。
26、【判断题】循环队列也存在空间溢出问题。
27、【判断题】栈和队列都是线性表，只是在插入和删除时受到了一些限制。
28、【判断题】栈和队列的存储方式，既可以是顺序方式，又可以是链式方式。
3.6作业
1、【简答题】如果输入序列为1 2 3 4 5 6,试问能否通过栈结构得到以下两个序列:4 3 5 6 1 2和1 3 5 4 2 6;请说明为什么不能或如何才能得到。
2、【简答题】(1)什么是递归程序？ (2) 递归程序的优、缺点是什么？ (3) 递归程序在执行时，应借助于什么数据结构来完成？
3、【简答题】什么是循环队列？
4、【简答题】检查表达式中括号是否匹配。(算法设计题)
5、【简答题】利用栈和队列，判断键盘上输入的n个数是否构成回文序列。(算法设计题)
6、【简答题】利用栈的基本操作实现将十进制整数n转换为r（2≤r≤16）进制数，并输出。(算法设计题)
4.4测验
1、【单选题】下面关于串的的叙述中，哪一个是不正确的？
a、串是字符的有限序列
b、空串是由空格构成的串
c、模式匹配是串的一种重要运算
d、串既可以采用顺序存储，也可以采用链式存储
2、【单选题】串是一种特殊的线性表，其特征体现在_____。
a、可以顺序存储
b、数据元素是一个字符
c、可以链接存储
d、数据元素可以是多个字符
3、【单选题】设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的运算称为（ ）
a、求子串
b、联接
c、模式匹配
d、求串长
4、【单选题】若串s="software",其子串的数目是（ ）。
a、8
b、37
c、36
d、9
5、【单选题】串的长度是指（ ）。
a、串中所含不同字母的个数
b、串中所含字符的个数
c、串中所含不同字符的个数
d、串中所含非空格字符的个数
6、【单选题】在字符串匹配的bf算法中，当主串位i与模式串位j比较失败时，新一趟匹配开始，主串的位移公式是（ ）。
a、i=i 1
b、i=j 1
c、i=i-j 1
d、i=i-j 2
7、【填空题】串是一种特殊的线性表，其特殊性表现在 ；串的两种最基本的存储方式是 、 。
8、【填空题】两个串相等的充分必要条件是 。
9、【填空题】组成串的数据元素只能是 。
10、【填空题】一个字符串中 称为该串的子串。
11、【填空题】index（"datastructure"，"str",1）=_____。
12、【填空题】设正文串长度为n，模式串长度为m，则串匹配的kmp算法的时间复杂度为 。
13、【填空题】模式串"abaabcac"的next函数值序列为 。
14、【判断题】串是一种数据对象和操作都特殊的线性表。
15、【判断题】空格串和空串的长度均为1。
16、【判断题】判断两个串是否相等，只需要判断这两个串是否包含相同的字符即可。
17、【判断题】如果一个串中的所有字符均在另一串中出现，那么则说明前者是后者的子串。
18、【判断题】kmp算法的最大特点是指示主串的指针不需回溯。
19、【判断题】设模式串的长度为m,目标串的长度为n，当n≈m且处理只匹配一次的模式时，朴素的匹配（即子串定位函数）算法所花的时间代价可能会更为节省。
4.5作业
1、【简答题】设计算法以判断串t是否是串s的子串，若是子串，返回1，否则返回0。
2、【简答题】设计算法比较串s1和串s2的大小。（s1
5.6测验
1、【单选题】若对n阶对称矩阵a以行序为主序方式将其下三角的元素(包括主对角线上所有元素)依次存放于一维数组b［1..(n(n 1))/2］中，则在b中确定aij（i≤j）的位置k的关系为( )。
a、i*(i-1)/2 j
b、j*(j-1)/2 i
c、i*(i 1)/2 j
d、j*(j 1)/2 i
2、【单选题】对稀疏矩阵进行压缩存储目的是( )。
a、便于进行矩阵运算
b、便于输入和输出
c、节省存储空间
d、降低运算的时间复杂度
3、【单选题】稀疏矩阵一般的压缩方法有两种，即( )。
a、二维数组和三维数组
b、三元组和散列
c、三元组顺序表和十字链表
d、散列和十字链表
4、【单选题】已知广义表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))))
5、【单选题】广义表((a),a)的表头和表尾分别是( )。
a、a ,((a))
b、(a) ,(a)
c、(a),a
d、((a)) , a
6、【单选题】广义表a=(a,b,(c,d),(e,(f,g)))，则head(tail(head(tail(tail(a)))))的值为( )。
a、(g)
b、(d)
c、c
d、d
7、【单选题】下面说法不正确的是( )。
a、广义表的表头总是一个广义表
b、广义表的表尾总是一个广义表
c、广义表难以用顺序存储结构表示
d、广义表可以是一个多层次的结构
8、【填空题】数组采用 存储方式。
9、【填空题】所谓稀疏矩阵指的是 的矩阵。
10、【填空题】对特殊矩阵进行压缩的目的是 。
11、【填空题】当广义表中的每个元素都是原子时，广义表便成了 。
12、【填空题】设广义表l=((),()), 则head(l)是 ；tail(l)是 ；l的长度是 ；深度是 。
13、【判断题】数组可看成线性结构的一种推广，因此与线性表一样，可以对数组进行插入，删除等操作。
14、【判断题】一个稀疏矩阵am*n采用三元组形式表示， 若把三元组中有关行下标与列下标的值互换，并把m和n的值互换，则就完成了am*n的转置运算。
15、【判断题】广义表的取表尾运算，其结果通常是个表，但有时也可是个单元素。
16、【判断题】若一个广义表的表头为空表，则此广义表亦为空表。
17、【判断题】所谓取广义表的表尾就是返回广义表中最后一个元素。
18、【判断题】一个广义表可以为其它广义表所共享。
5.7作业
1、【简答题】设有一个n×n的对称矩阵a，如图(a)所示。为了节约存储，可以只存对角线及对角线以上的元素，称为上三角矩阵。我们把它们按行存放于一维数组b [1..n(n 1)/2]中，如图(b)所示，并称之为对称矩阵a的压缩存储方式。 试问：对称矩阵中的任一元素aij在对应存于一维数组b的下标位置k的计算公式是什么?
2、【简答题】特殊矩阵和稀疏矩阵哪一种压缩存储后失去随机存取的功能？为什么？
3、【简答题】一个n×n的对称矩阵，如果以行或列为主序存入内存，则其容量为多少？
4、【简答题】数组，广义表与线性表之间有什么样的关系？
5、【简答题】设稀疏矩阵m采用三元组顺序表进行了压缩存储，请写出稀疏矩阵m的转置算法。
6、【简答题】设稀疏矩阵m采用十字链表做存储结构，请写出将其按照矩阵的行列结构输出的算法。
6.6 测验
1、【单选题】设树t的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则t中的叶子数为（ ）。
a、5
b、6
c、7
d、8
2、【单选题】一棵具有 n个结点的完全二叉树的高度（深度）是（ ）。
a、ëlog2nû 1
b、log2n 1
c、ëlog2nû
d、log2n-1
3、【单选题】高度为 k的二叉树最大的结点数为（ ）。
a、2超星学习通(k 1)-1
b、2超星学习通k-1
c、2超星学习通(k-1)-1
d、2超星学习通k 1
4、【单选题】利用二叉链表存储树，则根结点的右指针（ ）。
a、指向最左孩子
b、指向最右孩子
c、为空指针
d、为非空指针
5、【单选题】森林的先序遍历序列等同于对应的二叉树的( )。
a、先序序列
b、中序序列
c、后序序列
d、层次序列
6、【单选题】已知一棵二叉树的先序遍历结果为abcdef,中序遍历结果为cbaedf,则后序遍历的结果为（ ）。
a、cbefda
b、fedcba
c、cbedfa
d、不确定
7、【单选题】引入线索二叉树的目的是（ ）。
a、加快查找结点的前驱或后继的速度
b、为了能在二叉树中方便地进行插入与删除
c、为了能方便的找到双亲
d、使二叉树的遍历结果唯一
8、【单选题】3 个结点的二叉树有（ ）种不同的形态。
a、2
b、3
c、4
d、5
9、【填空题】二叉树由 , , 三个基本单元组成。
10、【填空题】在二叉树中，指针p所指结点为叶子结点的条件是 。
11、【填空题】具有n个结点的二叉树，采用二叉链表存储，共有 个空链域。
12、【填空题】一个无序序列可以通过构造一棵 而变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。
13、【填空题】若以{4，5，6，7，8}作为叶子结点的权值构造哈夫曼树，则其带权路径长度是 。
14、【填空题】设n0为哈夫曼树的叶子结点数目，则该哈夫曼树共有 个结点。
15、【判断题】二叉树是度为2的有序树。
16、【判断题】对一棵二叉树进行层次遍历时，应借助于一个栈。
17、【判断题】树的先根遍历和其相应的二叉树的先序遍历的结果是一样的。
18、【判断题】中序遍历一棵二叉排序树的结点就可得到排好序的结点序列。
19、【判断题】根据任何一棵二叉树的先序序列和后序序列可以唯一确定这棵二叉树。
20、【判断题】二叉树是树的特殊情形。
21、【判断题】树形结构中元素之间存在一对多的关系。
22、【判断题】完全二叉树的存储结构通常采用顺序存储结构。
23、【判断题】树与二叉树是两种不同的树型结构。
24、【判断题】哈夫曼树的结点个数不能是偶数。
6.7 作业
1、【简答题】试分别画出具有3个结点的不同形态的树和二叉树。
2、【简答题】对于任何一棵非空的二叉树,假设叶子结点的个数为n0,而次数为2的结点个数为n2,请给出n0和n2之间所满足的关系式。
3、【简答题】将算术表达式（a b）-c*(d e)/f转化为二叉树，并根据该二叉树，求出其前缀和后缀表达式。
4、【简答题】已知一棵二叉树的先序遍历的结果是abecdfghij, 中序遍历的结果是ebcdafhigj, 试画出这棵二叉树。
5、【简答题】设有正文aadbaacaccdacacaad，字符集为{a,b,c,d},设计一套二进制编码，使得上述正文的编码最短。
6、【简答题】假定用于通信的电文仅由8个字母c1, c2, c3, c4, c5, c6, c7, c8组成, 各字母在电文中出现的频率分别为5, 25, 3, 6, 10, 11, 36, 4。试为这8个字母设计不等长huffman编码, 并给出该电文的总码数。
7、【简答题】二叉树、树和森林是三种不同的数据结构，问： （1）指出树和二叉树的主要区别。 （2）将下图所示的树转化为二叉树。 （3）将下图所示的森林转化为二叉树。 （4）将树和森林转换为二叉树的基本目的是什么？
8、【简答题】算法设计题（参加实验大纲）
7.7测验
1、【单选题】设无向简单图的顶点个数为n，则该图最多有（ ）条边。
a、n-1
b、n(n-1)/2
c、n(n 1)/2
d、
2、【单选题】一个n个顶点的连通无向图，其边的个数至少为（ ）。
a、n-1
b、n
c、n 1
d、nlogn
3、【单选题】在一个无向图中，所有顶点的度数之和等于所有边数（ ）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（ ）倍。
a、2 1
b、1/2 1
c、2 2
d、1/2 2
4、【单选题】下列（ ）图的邻接矩阵一定是对称矩阵。
a、有向无环图
b、无向图
c、aov网
d、aoe网
5、【单选题】下列有关图的遍历的说法中，不正确的是（ ）。
a、用邻接表存储的图的深度优先搜索的时间复杂度为o(n＋e)
b、图的广度优先搜索中邻接点的寻找具有“先进先出”的特征，需要采用队列结构来实现
c、非连通图不能用深度优先搜索法
d、图的遍历要求每一顶点访问且仅被防问一次
6、【单选题】求解最短路径的floyd算法的时间复杂度为( )。
a、o（n）
b、o（n c）
c、o（）
d、o（）
7、【单选题】在用邻接表表示图时，拓扑排序算法时间复杂度为( )。
a、o(n)
b、o(n＋e)
c、o()
d、o()
8、【单选题】关键路径是aoe网中（ ）。
a、从源点到汇点的最长路径
b、从源点到汇点的最短路径
c、最长回路
d、最短回路
9、【单选题】下列关于aoe网的叙述中，不正确的是（ ）。
a、关键活动不按期完成就会影响整个工程的完成时间
b、任何一个关键活动提前完成，那么整个工程将会提前完成
c、所有的关键活动提前完成，那么整个工程将会提前完成
d、某些关键活动提前完成，那么整个工程将会提前完成
10、【判断题】有e条边的无向图，在邻接表中有e个结点。
11、【判断题】强连通图的各顶点间均可达。
12、【判断题】十字链表是无向图的一种存储结构。
13、【判断题】用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小与图中结点个数有关，而与图的边数无关。
14、【判断题】带权的连通无向图的最小生成树是唯一的。
15、【判断题】aov网的含义是以边表示活动的网。
7.8作业
1、【简答题】已知一个无向图g的邻接表存储表示如下，试写出从顶点a出发进行深度和广度优先遍历得到的顶点序列，并判断该图的连通性。
2、【简答题】下图表示一个地区的通讯网，边表示城市间的通讯线路，边上的权表示架设线路花费的代价，如何选择能沟通每个城市且总代价最省的n-1条线路，画出你的选择，并写出这n-1条路的总代价。
3、【简答题】叙述拓扑排序的基本思想，并对如下的有向图，写出两个不同的拓扑序列。
4、【简答题】写出如下有向网的邻接矩阵，并应用dijkstra算法求出从顶点0到其余各顶点的最短路径。
5、【论述题】已知图的邻接表存储定义如下： #define max_vex_num 20 //图的最大顶点个数 typedef struct arcnode { int adjvex; // 该弧所指向的顶点的位置 struct arcnode *nextarc; // 指向下一条弧的指针 } arcnode; typedef struct vnode { vertextype data; // 顶点信息 arcnode *firstarc; // 指向第一条依附该顶点的弧 } vnode, adjlist[max_vertex_num]; typedef struct { adjlist vertices; int vexnum, arcnum; // 顶点个数和弧数 int kind; // 图的种类标志 } algraph; (1)试写出计算图中所有顶点的入度算法，并将每个顶点的入度存入数组indegree中。 void findindegree(algraph g,int indegree[ ]) (2)试写出计算图中所有顶点的出度算法，并将每个顶点的出度存入数组outdegree中。 void findoutdegree(algraph g,int outdegree[ ])
8.4 测验
1、【单选题】对n个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为( )。
a、(n 1)/2
b、n/2
c、n
d、[(1 n)*n ]/2
2、【单选题】下面关于折半查找的叙述正确的是 ( ) 。
a、表必须有序，表可以顺序方式存储，也可以链表方式存储
b、表必须有序，而且只能从小到大排列
c、表必须有序.且表中数据必须是整型，实型或字符型
d、表必须有序，且表只能以顺序方式存储
3、【单选题】折半查找的时间复杂度为（ ）。
a、o（n2）
b、o（n）
c、o（nlogn）
d、o（logn）
4、【单选题】当采用分块查找时，数据的组织方式为 ( ) 。
a、数据分成若干块，每块内数据有序
b、数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块
c、数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块
d、数据分成若干块，每块（除最后一块外）中数据个数需相同
5、【单选题】二叉排序树的查找效率与二叉树的 （ ） 有关。
a、高度
b、结点的多少
c、树型
d、结点的位置
6、【单选题】二叉排序树的查找效率在 （ ） 时其查找效率最低。
a、结点太多
b、完全二叉树
c、呈单枝树
d、结点太复杂
7、【单选题】设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链地址法构造散列表，散列函数为h（key）=key % 13，散列地址为1的链中有（ ）个记录。
a、1
b、2
c、3
d、4
8、【单选题】设哈希表长为14，哈希函数是h(key)=key,表中已有数据的关键字为15，38，61，84，要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是( )
a、8
b、3
c、5
d、9
9、【填空题】顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多 次；当使用监视哨时，若查找失败，则比较关键字的次数为_____。
10、【填空题】在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找关键码值20，需做的关键码比较次数为 。
11、【填空题】分块查找中，若索引表和各块内均用顺序查找，则有900个元素的线性表分成_____块最好。
12、【填空题】动态查找表和静态查找表的重要区别在于前者包含有 和 运算，而后者不包含这两种运算。
13、【填空题】哈希表是通过将查找码按选定的 和 ，把结点按查找码转换为地址进行存储的线性表。哈希方法的关键是 和 。一个好的哈希函数其转换地址应尽可能 ，而且函数运算应尽可能 。
14、【填空题】在哈希函数h（key）=key%p中，p值最好取 。
15、【判断题】折半查找法的查找速度一定比顺序查找法快 。
16、【判断题】n个结点的二叉排序树有多种，其中树高最小的二叉排序树是最佳的。
17、【判断题】在任意一棵非空二叉排序树中，删除某结点后又将其插入，则所得二排序叉树与原二排序叉树相同。
18、【判断题】向某个平衡因子不为零的结点的平衡二叉树树中插入一新结点，必引起平衡旋转。
19、【判断题】二叉排序树删除一个结点后，仍是二叉排序树。
20、【判断题】采用线性探测法处理散列时的冲突，当从哈希表删除一个记录时，不应将这个记录的所在位置置空，因为这会影响以后的查找。
21、【判断题】在哈希查找中，“比较”操作一般也是不可避免的。
22、【判断题】哈希函数越复杂越好，因为这样随机性好，冲突概率小。
8.5作业
1、【简答题】用序列(46,88,45,39,70,58,101,10,66,34)建立一个排序二叉树，画出该树，并求在等概率情况下查找成功的平均查找长度。
2、【简答题】对下面的关键字集{30,15,21,40,25,26,36,37}若查找表的装填因子为0.8，采用线性探测再散列方法解决冲突。 （1）设计哈希函数； （2）画出哈希表； （3）计算查找成功和查找失败的平均查找长度；
3、【简答题】折半查找算法（算法设计题）
4、【简答题】二叉排序树的查找、插入算法。（算法设计题）
9.8 测验
1、【单选题】某内部排序算法的稳定性是指( )。
a、该排序算法不允许有相同的关键字记录
b、其他都不对
c、该排序算法允许有相同的关键字记录
d、平均时间为0（n log n）的排序方法
2、【单选题】下列排序算法中，其中（ ）是稳定的。
a、堆排序，冒泡排序
b、快速排序，堆排序
c、直接选择排序，归并排序
d、归并排序，冒泡排序
3、【单选题】数据序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中的( )的两趟排序后的结果。
a、选择排序
b、冒泡排序
c、插入排序
d、堆排序
4、【单选题】下列排序算法中( )不能保证每趟排序至少能将一个元素放到其最终的位置上。
a、快速排序
b、shell排序
c、堆排序
d、冒泡排序
5、【单选题】一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（ ）。
a、(38,40,46,56,79,84)
b、(40,38,46,79,56,84)
c、(40,38,46,56,79,84)
d、(40,38,46,84,56,79)
6、【单选题】下列排序算法中，在待排序数据已有序时，花费时间反而最多的是( )排序。
a、冒泡
b、希尔
c、快速
d、堆
7、【单选题】在下面的排序方法中，辅助空间为o（n）的是( ) 。
a、希尔排序
b、堆排序
c、选择排序
d、归并排序
8、【单选题】就平均性能而言，目前最好的内排序方法是( )排序法。
a、冒泡
b、希尔插入
c、交换
d、快速
9、【单选题】如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用（ ）方法最快。
a、起泡排序
b、快速排序
c、shell排序
d、堆排序
e、简单选择排序
10、【单选题】快速排序方法在（ ）情况下最不利于发挥其长处。
a、要排序的数据量太大
b、要排序的数据中含有多个相同值
c、要排序的数据个数为奇数
d、要排序的数据已基本有序
11、【单选题】下列四个序列中，哪一个是堆（ ）。
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
12、【单选题】有一组数据（15，9，7，8，20，-1，7，4），用堆排序的筛选方法建立的初始堆为 （ ）。
a、-1，4，8，9，20，7，15，7
b、-1，7，15，7，4，8，20，9
c、-1，4，7，8，20，15，7，9
d、其他均不对。
13、【单选题】就排序算法所用的辅助空间而言，堆排序，快速排序，归并排序的关系是 （ ）。
a、堆排序<快速排序<归并排序
b、堆排序<归并排序<快速排序
c、堆排序> 归并排序>快速排序
d、堆排序>快速排序>归并排序
14、【单选题】从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为( ) 排序法。
a、插入
b、选择
c、希尔
d、二路归并
15、【填空题】设表中元素的初始状态是按健值递增的，分别用堆排序，快速排序，冒泡排序和归并排序方法对其进行排序（按递增顺序）， 排序最省时间， 排序最费时间。
16、【填空题】3. 下列内部排序算法中： a．快速排序 b.直接插入排序 c. 二路归并排序 d. 简单选择排序 e. 起泡排序 f. 堆排序 问： （1）比较次数与序列初态无关的算法是（ ）。 （2）不稳定的排序算法是（ ）。 （3）在初始序列已基本有序（除去n个元素中的某k个元素后即呈有序，k<
17、【填空题】不受待排序初始序列的影响，时间复杂度为o(n2)的排序算法是 ，在排序算法的最后一趟开始之前，所有元素都可能不在其最终位置上的排序算法是 。
18、【填空题】直接插入排序用监视哨的作用是 。
19、【填空题】在数据表有序时，快速排序算法的时间复杂度是 。
20、【填空题】堆是一种有用的数据结构. 堆排序是一种 排序，堆实质上是一棵 结点的层次序列。对含有n个元素的序列进行排序时，堆排序的时间复杂度是 ，所需的附加存储结点是 。
21、【判断题】排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。
22、【判断题】堆肯定是一棵平衡二叉树。
23、【判断题】在初始数据表已经有序时，快速排序算法的时间复杂度为o(nlog2n )。
24、【判断题】在用堆排序算法排序时，如果要进行递增排序，则需要采用“大根堆”。
25、【判断题】（101，88，46，70，34，39，45，58，66，10）是堆。
26、【判断题】当待排序的数据规模很大时，为了交换元素的位置，移动元素要占用较多的时间，这是影响时间复杂度的主要因素。
27、【判断题】折半插入排序所需比较次数与待排序记录的初始排列状态相关。
28、【判断题】快速排序的速度在所有排序方法中为最快,而且所需附加空间也最少。
9.9作业
1、【简答题】内部排序（名词解释）。
2、【简答题】在各种排序方法中，哪些是稳定的？哪些是不稳定的？并为每一种不稳定的排序方法举出一个不稳定的实例。
3、【简答题】以下概念的区别：拓扑排序与冒泡排序。
4、【简答题】对于堆排序法，快速排序法和归并排序法： （1）若仅从节省存储空间考虑，则应该首先选取其中哪种方法？其次选取哪种方法？ （2）若仅考虑排序结果的稳定性，则应该选取哪种方法？ （3）若仅从平均情况下排序最快这一点考虑，则应该选取哪种方法？
5、【简答题】快速排序的最大递归深度是多少？最小递归深度是多少？
6、【简答题】请回答下列关于堆(heap)的一些问题： （1）堆的存储表示是顺序的，还是链接的? （2）设有一个最小堆，即堆中任意结点的关键码均大于它的左子女和右子女的关键码。其具有最大值的元素可能在什么地方?
7、【简答题】排序有各种方法， 如堆排序、直接插入排序、冒泡排序、快速排序等方法。设一数组中原有数据如下：15，13，20，18，12，60。下面是一组由不同排序方法进行一遍排序后的结果。请在下面各题的（ ）中写出排序方法。 （ ）排序的结果为：12，13，15，18，20，60 （ ）排序的结果为：13，15，18，12，20，60 （ ）排序的结果为：13，15，20，18，12，60 （ ）排序的结果为：12，13，20，18，15，60
猜你喜欢
- 2022-12-05 21:25
- 2022-12-05 21:15
- 2022-12-05 21:12
- 2022-12-05 20:56
- 2022-12-05 20:46
- 2022-12-05 20:05
- 2022-12-05 20:01
- 2022-12-05 19:12
- 2022-12-05 19:08
- 2022-12-05 18:58