[渝粤教育] 西安邮电大学 数据结构 参考 资料

教育
-数据结构-章节资料考试资料-西安邮电大学【】
测验1
1、【单选题】数据的逻辑结构有几种？
A、4
B、3
C、2
D、1
参考资料【 】
2、【单选题】数据的存储结构包括？
A、线性结构和非线性结构
B、静态结构和非静态结构
C、顺序结构和非顺序结构
D、动态结构和非动态结构
参考资料【 】
测验1
1、【单选题】数据的逻辑结构包括？
A、线性结构和非线性结构
B、顺序结构和非顺序结构
C、静态结构和非静态结构
D、动态结构和非动态结构
参考资料【 】
测验
1、【判断题】数据结构包括数据的逻辑结构、存储结构以及相关运算。
A、正确
B、错误
参考资料【 】
测验
1、【判断题】数据的逻辑结构和机器无关。
A、正确
B、错误
参考资料【 】
测验
1、【判断题】时间复杂度和频度是一样的。
A、正确
B、错误
参考资料【 】
测验
1、【判断题】一个算法包含的循环嵌套的层数越多，该算法的时间复杂度越高。
A、正确
B、错误
参考资料【 】
单元作业1
在线练习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、【单选题】某算法的时间复杂度是O(n^2)，表明该算法的（ ）。
A、执行时间与n^2成正比
B、问题规模是n^2
C、执行时间等于n^2
D、问题规模与n^2成正比
参考资料【 】
7、【单选题】衡量算法效率优劣的不包括（ ）。
A、正确性和可读性
B、健壮性/鲁棒性
C、高效率与低存储
D、现实性
参考资料【 】
8、【单选题】算法指（ ）。
A、计算方法
B、排序方法
C、解决问题的步骤序列
D、调度方法
参考资料【 】
9、【单选题】下面的程序段时间复杂度为（ ）。 for(i=1;in;i++) for(j=1;jn;j++) x=x+1;
A、O(2n)
B、O(n)
C、O(n^2)
D、O(log2n)
参考资料【 】
10、【单选题】算法效率分析的两个主要方面是（ ）。
A、空间复杂度和时间复杂度
B、正确性和简明性
C、可读性和文档性
D、数据复杂性和程序复杂性
参考资料【 】
11、【单选题】有如下递归函数fact(n)，分析其时间复杂度为（ ）。int fact(int n){ if(n=1) return 1; else return(nfact(n-1));}
A、O(n)
B、O(1)
C、O(n^2)
D、O(logn)
参考资料【 】
12、【单选题】下面程序段的时间复杂度为（ ）。for(i=0;in;i++) for(j=0;jm;j++) A[i][j]=0;
A、O(nm)
B、O(n^2)
C、O(m^2)
D、O(1)
参考资料【 】
13、【单选题】下面程序段的时间复杂度为（ ）。void sum(int n) //n为正整数{ int p=1,sum=0,i; for(i=1;i=n;i++) { p*=i; sum+=p; }}
A、O()
B、O(n)
C、O(1)
D、O(n^2)
参考资料【 】
14、【判断题】顺序存储方式的优点是存储密度大，且插入、删除运算效率高。
A、正确
B、错误
参考资料【 】
15、【判断题】算法可以用不同的语言描述，如果用C 语言或PASCAL语言等高级语言来描述，则算法实际上就是程序了。
A、正确
B、错误
参考资料【 】
16、【判断题】链式存储的优点是可以随机存储。
A、正确
B、错误
参考资料【 】
17、【判断题】在相同的数据规模n下，复杂度为O(n)的算法在时间上总是优于复杂度为O()的算法。
A、正确
B、错误
参考资料【 】
18、【判断题】数据的逻辑结构分为线性结构、树型结构、图状结构和集合。
A、正确
B、错误
参考资料【 】
19、【判断题】数据的存储结构表示的是数据元素之间的逻辑关系。
A、正确
B、错误
参考资料【 】
测验
1、【判断题】顺序表是指按照顺序方式进行存储的线性表。
A、正确
B、错误
参考资料【 】
测验
1、【判断题】单链表的插入、删除效率优于顺序表。
A、正确
B、错误
参考资料【 】
测验
1、【判断题】单链表的头插建立算法也称为反向建立单链表。
A、正确
B、错误
参考资料【 】
测验
1、【判断题】带尾指针的循环链表比带头指针的循环链表更便于运算。
A、正确
B、错误
参考资料【 】
测验
1、【判断题】在双向链表中查找某一结点的前驱或者后继，都非常方便。
A、正确
B、错误
参考资料【 】
单元作业2
在线练习2
1、【单选题】下述哪一条是顺序存储结构的优点（ ）。
A、随机存取
B、插入运算方便
C、删除运算方便
D、可方便地用于各种逻辑结构的存储表示
参考资料【 】
2、【单选题】下面关于线性表叙述中错误的是（ ）。
A、线性表采用顺序存储，必须占用一片连续的存储单元。
B、线性表采用顺序存储，便于进行插入和删除操作。
C、线性表采用链式存储，不必占用一片连续的存储单元。
D、线性表采用链式存储，便于插入和删除操作。
参考资料【 】
3、【单选题】若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。
A、顺序表
B、双链表
C、带头结点的双循环链表
D、单循环链表
参考资料【 】
4、【单选题】设某顺序表中第一个元素的存储地址是base，下限值为1，每个结点占m个单元，则第i个结点的存储地址为（ ）。
A、base+(i+1)×m
B、base+i×m
C、base+(i-1)×m
D、base-i×m
参考资料【 】
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、【单选题】若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为 （）。
A、O(0)
B、O(1)
C、O(n)
D、O()
参考资料【 】
11、【单选题】对于顺序表，访问结点和删除结点的时间复杂度分别为（ ）。
A、O(n) O(n)
B、O(n) O(1)
C、O(1) O(n)
D、O(1) O(1)
参考资料【 】
12、【单选题】在单链表指针为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;
参考资料【 】
13、【单选题】对于一个带头结点的单链表，其头指针为head，判定该表为空表的条件是（ ）。
A、headNULL
B、head→nexthead
C、head→nextNULL
D、head!=NULL
参考资料【 】
14、【单选题】将两个各有n个元素的有序表合并成一个有序表，其最少的比较次数是（ ）。
A、n
B、2n-1
C、2n
D、n-1
参考资料【 】
15、【单选题】在双向链表中，在p所指向的结点前插入一个q所指向的结点，相应的操作语句是（ ）。注：双向链表的结点结构为(prior，data，next)。
A、p->prior=q;q->next=p;p->prior->next=q;q->prior=q;
B、p->prior=q;p->prior->next=q;q->next=p;q->prior=p->prior;
C、q->next=p;q->prior=p->prior;p->prior->next=q;p->prior=q;
D、q->prior=p->prior;q->next=q;p->prior=q;p->prior=q;
参考资料【 】
16、【单选题】线性表（ a1,a2,…,an）以链式方式存储时，访问第i个元素的时间复杂度为（ ）
A、O（i）
B、O（1）
C、O（n）
D、O（i-1）
参考资料【 】
17、【单选题】头指针为H的循环单链表中尾结点P的特点是（ ）。
A、P->next=H
B、P->next= H->next
C、P=H
D、P=H->next
参考资料【 】
18、【单选题】两个指针P和Q，分别指向单链表的两个结点，P是Q的前驱结点的条件是（ ）。
A、P->nextQ->next
B、P->nextQ
C、Q->nextP
D、PQ
参考资料【 】
19、【单选题】在单链表中，增加头结点的目的是（ ）。
A、使单链表至少有一个结点
B、标志表中首结点的位置
C、链表判空、插入第一个结点以及删除第一个结点等运算方便
D、说明该单链表是线性表的链式存储结构
参考资料【 】
20、【单选题】下面关于线性表的叙述中，错误的是（ ）。
A、顺序表必须占一片地址连续的存储单元
B、顺序表可以随机存取任一元素
C、链表不必占用一片地址连续的存储单元
D、链表可以随机存取任一元素
参考资料【 】
21、【单选题】设p为指向长度为n的单循环链表上某结点的指针，则找到p的直接前驱（ ）。
A、找不到
B、时间复杂度为O（1）
C、时间复杂度为O（n）
D、次数约为n
参考资料【 】
22、【单选题】以下关于线性表的论述，不正确的是（ ）。
A、线性表中的元素可以是数字、字符、记录等不同类型。
B、顺序表中包含的元素个数是有限的。
C、线性表中的每个结点都有且仅有一个直接前趋和一个直接后继。
D、存在这样的线性表，即表中没有任何结点。
参考资料【 】
23、【单选题】在（ ）的运算中，使用顺序表比链表好。
A、插入
B、根据序号查找
C、 删除
D、根据元素查找
参考资料【 】
24、【判断题】静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。
A、正确
B、错误
参考资料【 】
25、【判断题】线性表的特点是每个元素都有一个前驱和一个后继。
A、正确
B、错误
参考资料【 】
26、【判断题】若长度为n的线性表采用顺序存储结构，找到其中第i个元素的时间复杂度为O(n)。
A、正确
B、错误
参考资料【 】
27、【判断题】已知带头结点的双向循环链表L，判断其为空表的条件是L-nextL L-priorL。
A、正确
B、错误
参考资料【 】
28、【判断题】顺序表的插入、删除运算更方便。
A、正确
B、错误
参考资料【 】
29、【判断题】链表的性能优于顺序表。
A、正确
B、错误
参考资料【 】
30、【判断题】顺序表适宜于顺序存取，而链表适宜于随机存取。
A、正确
B、错误
参考资料【 】
31、【判断题】顺序表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。
A、正确
B、错误
参考资料【 】
32、【判断题】插入和删除操作是数据结构中最基本的两种操作，所以这两种操作在数组中也经常使用。
A、正确
B、错误
参考资料【 】
33、【判断题】线性表的链式存储结构中，逻辑上相邻的两个元素在物理位置上不一定相邻。
A、正确
B、错误
参考资料【 】
测验
1、【判断题】栈的特点是先进先出。
A、正确
B、错误
参考资料【 】
测验
1、【判断题】双端栈有效地共享了存储空间。
A、正确
B、错误
参考资料【 】
测验
1、【判断题】汉诺塔问题可以使用递归算法来完成。
A、正确
B、错误
参考资料【 】
测验
1、【判断题】迷宫问题的非递归实现借助的是栈这种结构。
A、正确
B、错误
参考资料【 】
测验
1、【判断题】队列的特点是先进后出。
A、正确
B、错误
参考资料【 】
测验
1、【判断题】采用链式结构存储的队列称之为链队列。
A、正确
B、错误
参考资料【 】
测验
1、【判断题】在表达式求值问题中，我们使用运算符栈和运算数栈协同工作完成整个表达式的求解过程。
A、正确
B、错误
参考资料【 】
单元作业3
单元测试1
1、【单选题】栈和队列的共同点是（ ）。
A、都是先进先出
B、都是先进后出
C、只允许在端点处插入和删除元素
D、没有共同点
参考资料【 】
2、【单选题】栈和队都是（ ）。
A、顺序存储的线性结构
B、链式存储的非线性结构
C、限制存取点的线性结构
D、限制存取点的非线性结构
参考资料【 】
3、【单选题】依照六个元素6，5，4，3，2，1 的顺序进栈，下列哪一个出栈序列不可能（ ）。
A、543612
B、453216
C、346521
D、234156
参考资料【 】
4、【单选题】设栈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
参考资料【 】
5、【单选题】设计一个判别表达式中括号是否匹配出现的算法，采用（ ）的数据结构最佳。
A、顺序表
B、队列
C、单链表
D、栈
参考资料【 】
6、【单选题】表达式a*(b+c)-d的后缀表达式是( ）。
A、bc+ad-
B、abc+d-
C、abc+d-
D、dabc+-
参考资料【 】
7、【单选题】函数递归调用时，处理参数及返回地址需要用一种（ ）的数据结构。
A、队列
B、多维数组
C、栈
D、线性表
参考资料【 】
8、【单选题】若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为3和1，当从队列中删除一个元素再加入两个元素后，rear和front的值为( )。
A、0和5
B、2和4
C、5和2
D、5和1
参考资料【 】
9、【单选题】最大容量为n的循环队列，队尾指针为rear，队头指针为front，则队空的条件是（ ）。
A、(rear+1)%nfront
B、rearfront
C、rear+1front
D、(rear-l)%nfront
参考资料【 】
10、【单选题】假设以数组A[m]存放循环队列的元素,其头、尾指针分别为front和rear，front指示实际的队头元素，rear指向实际队尾元素的下一个元素位置，则当前队列中的元素个数为（ ）。
A、(rear-front+m)%m
B、rear-front+1
C、(front-rear+m)%m
D、(rear-front+1)%m
参考资料【 】
11、【单选题】用带头结点的表长大于1的单链表表示队列时，其队头指针指向队头结点，其队尾指针指向队尾结点，则在进行删除操作时( )。
A、仅修改队头指针
B、仅修改队尾指针
C、队头、队尾指针都要修改
D、队头,队尾指针都可能要修改
参考资料【 】
12、【单选题】下列说法正确的是（ ）。(1)只有使用了局部变量的递归函数在转换成非递归函数时才必须使用栈。(2)队列是插入与删除操作在表的两端进行的线性表，具有先进后出的特点。(3)队列是一端进行删除另外一端进行插入的线性表。(4)循环队列也存在空间溢出问题。
A、(1)(2)(4)
B、(1)(2)(3)
C、(3)(4)
D、(1)(2)
参考资料【 】
13、【单选题】以下程序的输出结果为（ ）。 int f( int x) { return (x0)?xf(x-1):2; } void main() { int i ; i=f(f(1)); printf(%d,i); }
A、2
B、4
C、8
D、无限递归
参考资料【 】
14、【单选题】若一个栈以数组V[0…n-1]存储，初始栈顶指针top为n，则下面关于元素x进栈的正确操作是( )。
A、top=top+1; V[top]=x;
B、V[top]=x; top=top+1;
C、top=top-1; V[top]=x;
D、 V[top]=x; top=top-1;
参考资料【 】
15、【单选题】一个递归算法必须包括（ ）。
A、递归体
B、递归条件和递归体
C、迭代部分
D、终止条件和迭代部分
参考资料【 】
16、【单选题】输入序列为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
参考资料【 】
17、【单选题】一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（ ）。
A、2 3 4 1 5
B、5 4 1 3 2
C、2 3 1 4 5
D、1 5 4 3 2
参考资料【 】
18、【单选题】一个栈的输入序列为1,2,3,…,n，若输出序列的第一个元素是i，则输出第j（1=j=i）个元素是（ ）。
A、i-j-1
B、i-j+1
C、j-i+1
D、不确定的
参考资料【 】
19、【单选题】在双向链表（结点包括：data,prior,next）中，删除指针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;
参考资料【 】
20、【单选题】以下说法错误的是 （ ）。
A、对循环链表来说，从表中任意结点出发都能通过前后操作而扫描到整个循环链表。
B、对单链表来说，只有从头结点开始才能扫描表中全部结点。
C、双向链表的特点是找结点的前趋和后继都很容易。
D、对双向链表来说，结点P的存储位置既存放在其前驱结点的后继指针域中，也存放在它的后继结点的前趋指针域中。
参考资料【 】
21、【单选题】对于一个具有n个结点的单链表，在已知的结点p后插入一个新结点的时间复杂度和在给定值为x的结点后插入一个新结点的时间复杂度分别为（ ）。
A、O(n),O(n)
B、O(1),O(n)
C、O(1),O(1)
D、O(n),O(1)
参考资料【 】
22、【单选题】循环队列存储在数组A[0…m-1]中，则入队时rear应该变化为（ ）。
A、rear++;
B、rear=(rear+1) mod (m+1);
C、rear=(rear+1) mod m;
D、rear=(rear+1) mod (m-1);
参考资料【 】
23、【单选题】当利用大小为n的数组顺序存储一个栈时，假定用top=n表示栈空，则每次向这个栈插入一个元素时，首先应执行（ ）语句修改top指针。
A、top++;
B、top–;
C、top=0;
D、top=n;
参考资料【 】
24、【单选题】若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。
A、顺序表
B、双链表
C、带头结点的双循环链表
D、单循环链表
参考资料【 】
25、【单选题】链表不具有的特点是（ ）。
A、插入、删除不需要移动元素
B、可随机访问任意元素
C、不必事先估计存储空间
D、所需空间与线性长度成正比
参考资料【 】
26、【单选题】设某顺序表中第一个元素的地址是base，下标从1开始，每个结点占m个单元，则第i个结点的地址为（ ）。
A、base+(i+1)×m
B、base+i×m
C、base+(i-1)×m
D、base-i×m
参考资料【 】
27、【单选题】在下面的程序段中，对x的赋值语句的频度为（ ）。 for(i=1;in;i++) for(j=1;jn;j++) x=x+1;
A、O(2n)
B、O(n)
C、O(n^2)
D、O(log2n)
参考资料【 】
28、【单选题】数据结构在计算机内存中的表示是指（ ）。
A、数据的存储结构
B、数据结构
C、数据的逻辑结构
D、数据元素之间的关系
参考资料【 】
29、【判断题】消除递归不一定需要使用栈，此说法（ ）。
A、正确
B、错误
参考资料【 】
30、【判断题】两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出，应把两个栈的栈底分别设在这片内存空间的两端。（ ）
A、正确
B、错误
参考资料【 】
31、【判断题】顺序栈因为是顺序存储，所以可以随机存取栈中任意元素。（ ）
A、正确
B、错误
参考资料【 】
32、【判断题】任何一个递归过程都可以转换成非递归过程。（ ）
A、正确
B、错误
参考资料【 】
33、【判断题】两顺序栈共享空间，也存在空间溢出问题。（　）
A、正确
B、错误
参考资料【 】
34、【判断题】栈和队列都是线性表，只是在插入和删除时受到了一些限制。（ ）
A、正确
B、错误
参考资料【 】
35、【判断题】栈和队列的存储方式，既可以是顺序方式，也可以是链式方式。（ ）
A、正确
B、错误
参考资料【 】
36、【判断题】线性表的链式存储结构中，逻辑上相邻的两个元素在物理位置上并不一定相邻。
A、正确
B、错误
参考资料【 】
37、【判断题】顺序表适宜于顺序存取，而链表适宜于随机存取。
A、正确
B、错误
参考资料【 】
38、【判断题】顺序存储方式的优点是存储密度大，且插入、删除运算效率高。
A、正确
B、错误
参考资料【 】
测验
1、【判断题】串是一种特殊的线性表。
A、正确
B、错误
参考资料【 】
测验
1、【判断题】串的简单模式匹配算法的时间复杂度达到平方阶。
A、正确
B、错误
参考资料【 】
测验
1、【判断题】KMP算法最终只需要讨论模式串本身就可以。
A、正确
B、错误
参考资料【 】
测验
1、【判断题】模式串ababc对应的next值为01123。
A、正确
B、错误
参考资料【 】
单元作业4
在线练习4
1、【单选题】下面关于串的叙述不正确的是（ ）。
A、串是字符的有限序列
B、模式匹配是串的一种重要运算
C、空串是由空格构成的串
D、串可以采用顺序存储，也可以采用链式存储
参考资料【 】
2、【单选题】串是一种特殊的线性表，其特殊性体现在（ ）。
A、顺序存储
B、数据元素是字符
C、链式存储
D、逻辑结构是线性结构
参考资料【 】
3、【单选题】若串S= ‘software’,其前缀真子串的数目是（ ）。
A、10
B、9
C、8
D、7
参考资料【 】
4、【单选题】串的长度是指（ ）。
A、串中所含不同字母的个数
B、串中所含字符的个数
C、串中所含不同字符的个数
D、串中所含非空格字符的个数
参考资料【 】
5、【单选题】两个串相等的充要条件是（ ）。
A、两个字符串中对应位置上的字符相等
B、两个字符串存储形式相同
C、两个字符串的长度相等
D、两个字符串的长度相等且对应位置上的字符也相等
参考资料【 】
6、【单选题】设有两个串p和q ，其中q是p的子串，求q在p中首次出现的位置的算法称为（ ）。
A、求子串
B、串联接
C、串的模式匹配
D、求串长
参考资料【 】
7、【单选题】已知串 S=‘aaab’,其next函数值为（ ）。
A、0123
B、1123
C、1231
D、1211
参考资料【 】
8、【单选题】模式串‘ababaaababaa’的next函数值为（ ）。
A、012345678999
B、012121111212
C、011234223456
D、0123012322345
参考资料【 】
9、【单选题】函数strcmp(‘stcabuc’,‘stbabuc’)的返回值是（ ）。
A、-1
B、2
C、0
D、1
参考资料【 】
10、【单选题】模式串 t=‘abcaabbcabcaabdab’，该模式串的next函数值为（ ）。
A、0 1 1 1 2 2 1 1 1 2 3 4 5 6 7 1 2
B、0 1 1 0 2 1 3 1 0 1 1 0 2 1 7 0 1
C、0 1 1 1 0 0 1 3 1 0 1 1 0 0 7 0 1
D、0 1 1 1 2 2 3 1 1 2 3 4 5 6 7 1 2
参考资料【 】
11、【单选题】假设空串是任何串的子串，则串S=‘Computer’的子串个数是（ ）。
A、9
B、36
C、37
D、8
参考资料【 】
12、【单选题】StrIndex （‘DATASTRUCTURE’，1,‘STR’）= （ ）。
A、3
B、7
C、5
D、9
参考资料【 】
13、【单选题】设正文串长度为n，模式串长度为m，则模式匹配的KMP算法的时间复杂度为（ ）。
A、O(mn)
B、O(m+n)
C、O(m)
D、O(n)
参考资料【 】
14、【单选题】StrIndex(‘Index of String’,1,‘Str’）=( ) 。
A、10
B、8
C、6
D、 12
参考资料【 】
15、【单选题】SubStr(‘I like University’,8,3)的返回值是（ ）。
A、ike
B、Uni
C、ver
D、ers
参考资料【 】
16、【单选题】设S=，则LenStr(S)=（ ）。
A、0
B、1
C、2
D、3
参考资料【 】
17、【单选题】设目标串T=aabaababaabaa，模式P=abab，朴素匹配算法的外层循环进行了( )次。
A、1
B、9
C、4
D、5
参考资料【 】
18、【单选题】S1=‘good’，S2=‘morning’，执行函数SubStr(S2,4,LenStr(S1))后的结果为( )。
A、‘good’
B、‘ning’
C、‘go’
D、‘morn’
参考资料【 】
19、【单选题】若串S=‘SOFT’，其子串的数目最多是（ ） 。
A、9
B、10
C、11
D、12
参考资料【 】
20、【单选题】以下论述正确的是（ ）。
A、空串与空格串是相同的
B、‘tel’是’Telephone’的一个子串
C、空串是零个字符的串
D、空串的长度等于1
参考资料【 】
21、【单选题】设串S1=‘I AM’，S2=’ A STUDENT’，则ConcatStr(S1,S2)=( )。
A、‘I AM’
B、‘A STUDENT’
C、‘I AM A STUDENT’
D、‘IAMASTUDENT’
参考资料【 】
22、【单选题】设串S1=‘ABCDEFG’，S2=‘PQRST’ ,则ConcatStr(SubStr(S1,2,LenStr(S2)),SubStr(S1,LenStr(S2),2))的结果串为( )。
A、‘BCDEF’
B、‘BCDEFG’
C、‘BCPQRST’
D、‘BCDEFEF’
参考资料【 】
23、【单选题】设有三个串S1、S2和S3，则StrReplace(S1,S2,S3)运算称作( )。
A、串连接
B、模式匹配
C、 求子串
D、串替换
参考资料【 】
24、【单选题】以下论断正确的是( )。
A、"“是空串，” "空格串
B、"BEIJING"是"BEI JING"的子串
C、“something”=“Something”
D、“BIT”=“BITE”
参考资料【 】
25、【单选题】某串的长度小于一个常数，则采用（ ）存储方式最节省空间。
A、链式
B、顺序
C、堆结构
D、无法确定
参考资料【 】
26、【判断题】串是一种数据对象特殊的线性表。
A、正确
B、错误
参考资料【 】
27、【判断题】KMP算法的特点是在模式匹配时指示主串的指针不会回溯。
A、正确
B、错误
参考资料【 】
28、【判断题】设模式串的长度为m, 目标串的长度为n ，当 n ≈ m 且处理只匹配一次的模式时，朴素的匹配（即子串定位函数）算法所花的时间代价可能会更为节省。
A、正确
B、错误
参考资料【 】
29、【判断题】模式串 P=‘abaabcac’的next函数值序列为01122312
A、正确
B、错误
参考资料【 】
30、【判断题】串的存储结构有顺序串、堆串和块链串三种。
A、正确
B、错误
参考资料【 】
31、【判断题】如果一个串中所有的字母均在另一个串中出现，则说明前者是后者的子串。
A、正确
B、错误
参考资料【 】
32、【判断题】串中任意个字符组成的子序列称为该串的子串。
A、正确
B、错误
参考资料【 】
33、【判断题】如果两个串含有相同的字符，则说明它们相等。
A、正确
B、错误
参考资料【 】
34、【判断题】子串的定位运算称为串的模式匹配。
A、正确
B、错误
参考资料【 】
35、【判断题】串’student’和’Student’相等。
A、正确
B、错误
参考资料【 】
测验
1、【判断题】n维数组可以看成是由“n-1维数组”的数组元素构成的一维数组。
A、正确
B、错误
参考资料【 】
测验
1、【判断题】为了节省存储空间，我们经常对特殊矩阵和稀疏矩阵进行压缩存储。
A、正确
B、错误
参考资料【 】
测验
1、【判断题】采用三元组顺序表存储的稀疏矩阵，利用快速转置算法，时间复杂度可以达到线性阶。
A、正确
B、错误
参考资料【 】
测验
1、【判断题】任何一个非空的广义表其表尾一定还是一个广义表。
A、正确
B、错误
参考资料【 】
单元作业5
在线练习5
1、【单选题】设有一个10阶的对称矩阵A，采用下三角的压缩存储方式，以行序为主序，a[1][1]为第一元素，其存储地址为1，每个元素占一个地址空间，则a[8][5]的地址为（ ）。
A、13
B、33
C、18
D、40
参考资料【 】
2、【单选题】设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当用以列为主序存放时，元素A[5][8]的存储首地址为( )。
A、BA+141
B、BA+180
C、BA+222
D、BA+225
参考资料【 】
3、【单选题】假设以行序为主序存储二维数组A=array[1…100，1…100]，设每个数组元素占2个存储单元，基地址为10，则arry[5][5]的地址为（ ）。
A、808
B、818
C、1010
D、1020
参考资料【 】
4、【单选题】二维数组A的每个元素都是6个字符组成的串，行下标i的范围从0到8，列下标j的范围从1到10，则存放A至少需要（ ）个字节。
A、90
B、180
C、240
D、540
参考资料【 】
5、【单选题】二维数组A的元素都是6个字符组成的串，行下标i的范围从0到8，列下标j的范围从1到10，则A的第8列和第5行共占（ ）个字节。
A、108
B、114
C、54
D、150
参考资料【 】
6、【单选题】二维数组A的每个元素都是6个字符组成的串，行下标i的范围从0到8，列下标j的范围从1到10，则如果A按行存放元素A[8][5]的起始地址与A按列存放时元素（ ）的起始地址一致。
A、A[8][5]
B、A[3][10]
C、A[5][8]
D、A[0][9]
参考资料【 】
7、【单选题】若对n阶对称矩阵A，下标从1开始，以行序为主序方式将其下三角形的元素依次存放于一维数组B［1…(n(n+1))/2］中，则在B中确定a[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
参考资料【 】
8、【单选题】若对n阶对称矩阵A，下标从1开始，以列序为主序方式将其上三角形的元素依次存放于一维数组B［1…(n(n+1))/2］中，则在B中确定a[i]j的位置k的计算公式为( )。
A、i(i-l)/2+j
B、j(j-l)/2+i
C、j(j-l)/2+i-1
D、i(i-l)/2+j-1
参考资料【 】
9、【单选题】设二维数组A[1… m，1… n]（即m行n列）按行存储在数组B[1… mn]中，则二维数组中元素A[i][j]在一维数组B中的下标为( )。
A、（i-1）n+j
B、（i-1）n+j-1
C、i（j-1）
D、jm+i-1
参考资料【 】
10、【单选题】有一个10090的稀疏矩阵，非零元素（int型）有10个，假设int型占2个字节，则用三元组顺序表表示该矩阵时所需的字节数是（ ）。
A、60
B、66
C、18000
D、33
参考资料【 】
11、【单选题】对稀疏矩阵进行压缩存储的目的是（ ）。
A、便于进行矩阵运算
B、便于输入和输出
C、节省存储空间
D、降低运算的时间复杂度
参考资料【 】
12、【单选题】已知广义表L=（（x,y,z），a，（u，t，w）），从L表中取出原子项t的运算是（ ）。
A、head（tail（tail（L）））
B、head（tail（head（tail（L））））
C、tail（head（head（tail（L））））
D、head（tail(head（tail（tail（L）））））
参考资料【 】
13、【单选题】广义表A=(a,b,(c,d),(e,(f,g))),则Head(Tail(Head(Tail(Tail(A)))))的值为（ ）。
A、(g)
B、(d)
C、c
D、d
参考资料【 】
14、【单选题】设广义表L=（（a,b,c）），则L的长度和深度分别为（ ）。
A、1和1
B、1和3
C、1和2
D、2和3
参考资料【 】
15、【单选题】下面说法不正确的是( )。
A、广义表的表头总是一个广义表
B、一个非空广义表的表尾总是一个广义表
C、广义表难以用顺序存储结构进行存储
D、广义表可以是一个多层次的结构
参考资料【 】
16、【单选题】广义表运算式Tail(((a,b),(c,d)))的操作结果是（ ）。
A、(c,d)
B、c,d
C、((c,d))
D、d
参考资料【 】
17、【单选题】广义表（a,(b,c),d,e）的表头为（ ）。
A、a
B、a,(b,c)
C、(a,(b,c))
D、(a)
参考资料【 】
18、【单选题】广义表（（a,b,c,d））的表尾是（ ）。
A、a
B、（）
C、（a,b,c,d）
D、（b,c,d）
参考资料【 】
19、【单选题】数组A[0…4,-3…-1,5…7]中含有元素的个数（ ）。
A、55
B、45
C、36
D、16
参考资料【 】
20、【单选题】数组A[0…5,0…6]的每个元素占5个字节，将其按列序为主序存储在起始地址为1000的内存单元中，则元素A[5][5]的地址是( )。
A、1175
B、1180
C、1205
D、1210
参考资料【 】
21、【单选题】将一个A[1…100，1…100]的三对角矩阵，按行优先存入一维数组B[1‥298]中，元素A[66][65]在B数组中的位置K为（ ）。
A、198
B、195
C、197
D、196
参考资料【 】
22、【单选题】已知广义表: A=(a,b), B=(A,A), C=(a,(b,A),B), 求tail(head(tail©)) =( )。
A、(a)
B、(b)
C、b
D、((a,b))
参考资料【 】
23、【单选题】在稀疏矩阵的三元组顺序表中，每个三元组表示（ ）。
A、矩阵中非零元素的数据值
B、矩阵中数据元素的行号和列号
C、矩阵中数据元素的行号、列号和数据值
D、矩阵中非零元素的行号、列号和数据值
参考资料【 】
24、【单选题】对矩阵进行压缩存储后，（ ）矩阵会失去随机存取的优点。
A、对称矩阵
B、三角矩阵
C、三对角矩阵
D、稀疏矩阵
参考资料【 】
25、【单选题】经常对数组进行的两种基本操作是____。
A、建立与删除
B、索引和修改
C、查找和修改
D、查找与索引
参考资料【 】
26、【单选题】假设整型数组A[1…8，-2…6，0…6]，按行优先存储，第一个元素的首地址是78，每个数组元素占用4个存储单元，那么元素A[4][2][3]的存储首地址为____。
A、955
B、958
C、950
D、900
参考资料【 】
27、【单选题】tail（head（（（a,b,c,d,e））））=__________。
A、a
B、b c
C、Φ
D、(b,c,d,e)
参考资料【 】
28、【判断题】从逻辑结构上看，n维数组的每个元素均属于n个向量。
A、正确
B、错误
参考资料【 】
29、【判断题】多维数组可以看作是一种特殊的线性表。
A、正确
B、错误
参考资料【 】
30、【判断题】数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。
A、正确
B、错误
参考资料【 】
31、【判断题】一个稀疏矩阵Amn采用三元组顺序表形式表示，若把三元组中有关行下标与列下标的值互换，并把m和n的值互换，则就完成了Amn的转置运算。
A、正确
B、错误
参考资料【 】
32、【判断题】广义表B = (a, B) = (a, (a, (a, ××× , ) ) ) 的长度为无穷大。
A、正确
B、错误
参考资料【 】
33、【判断题】一个广义表可以为其它广义表所共享。
A、正确
B、错误
参考资料【 】
34、【判断题】一个广义表的表尾一定还是个广义表。
A、正确
B、错误
参考资料【 】
35、【判断题】稀疏矩阵中非零元素的个数远小于矩阵中元素的总数。
A、正确
B、错误
参考资料【 】
测验
1、【判断题】在任何一棵二叉树中，度为0的结点数等于度为2的结点数-1。
A、正确
B、错误
参考资料【 】
测验
1、【判断题】完全二叉树采用顺序存储是比较方便的。
A、正确
B、错误
参考资料【 】
测验
1、【判断题】二叉树的按层次遍历算法可以采用递归算法实现。
A、正确
B、错误
参考资料【 】
测验
1、【判断题】根据二叉树的前序和后序遍历结果可以恢复出一棵二叉树。
A、正确
B、错误
参考资料【 】
测验
1、【判断题】二叉树的非递归遍历算法借助了栈这种结构。
A、正确
B、错误
参考资料【 】
测验
1、【判断题】在线索二叉树中，有n+1个线索。
A、正确
B、错误
参考资料【 】
测验
1、【判断题】在中序线索树中找结点的直接前驱，实际是找左子树中“最右下端”的结点。
A、正确
B、错误
参考资料【 】
测验
1、【判断题】树的双亲表示法采用的是顺序存储结构。
A、正确
B、错误
参考资料【 】
测验
1、【判断题】树的后序遍历结果和对应的二叉树的中序遍历结果相同。
A、正确
B、错误
参考资料【 】
测验
1、【判断题】哈夫曼树中叶子结点数为n，那么内部结点数为n+1。
A、正确
B、错误
参考资料【 】
测验
1、【判断题】哈夫曼编码是前缀编码。
A、正确
B、错误
参考资料【 】
测验
1、【判断题】哈夫曼编码是从叶子到根进行编码的。
A、正确
B、错误
参考资料【 】
单元测试2
1、【单选题】树最适合用来表示的结构是（ ）。
A、元素间的有序结构
B、元素间具有分支及层次关系的结构
C、元素间的无序结构
D、元素间无联系的结构
参考资料【 】
2、【单选题】设一棵二叉树的结点个数为18，则它的高度至少为（ ）。
A、4
B、5
C、6
D、18
参考资料【 】
3、【单选题】任意一棵二叉树的叶子结点在其先序、中序、后序序列中的相对位置（ ）。
A、肯定发生变化
B、有时发生变化
C、肯定不发生变化
D、无法确定
参考资料【 】
4、【单选题】判断线索二叉树中某结点p有左孩子的条件是（ ）。
A、p!=NULL
B、p->lchild!=NULL
C、p->LTag0
D、p->LTag==1
参考资料【 】
5、【单选题】设森林T中有4棵树，其结点个数分别为n1,n2,n3,n4，那么当森林T转换成一棵二叉树后，则根结点的右子树上有（ ）个结点。
A、n1-1
B、n1
C、n1+n2+n3
D、n2+n3+n4
参考资料【 】
6、【单选题】由权值分别为9、2、5、7、4的5个叶子结点构造一棵哈夫曼树，则该树的带权路径长度为（ ）。
A、45
B、55
C、60
D、65
参考资料【 】
7、【单选题】设T是一棵哈夫曼树，有8个叶结点，则树T的高度最高可以是（ ）。
A、4
B、6
C、8
D、10
参考资料【 】
8、【单选题】以下属于前缀编码的是（ ）。
A、{0,1101,1110,1100,1111}
B、{0,1,01,010,110}
C、{00,01,10,11,101}
D、{01,00,10,001,110,101}
参考资料【 】
9、【单选题】算术表达式a+b*（c+d/e）转为后缀表达式为（ ）。
A、ab+cde++
参考资料【 】
10、【单选题】设树T的度为4，其中度为1,2,3和4的结点个数分别为4,2,1,1，则T中的叶子数为（ ）。
A、5
B、6
C、7
D、8
参考资料【 】
11、【单选题】一棵哈夫曼树共有215个结点，对其进行哈夫曼编码，共能得到（ ）个不同的码字。
A、107
B、108
C、214
D、215
参考资料【 】
12、【单选题】一棵具有N个结点的二叉树采用二叉链表进行存储，其中空指针域有( )个。
A、N
B、N+1
C、N-1
D、不确定
参考资料【 】
13、【单选题】深度为K的二叉树中结点总数（ ）。
A、
B、
C、
D、
参考资料【 】
14、【单选题】已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树中有（ ）个叶子结点。
A、10
B、12
C、11
D、13
参考资料【 】
15、【单选题】以数据集{4，5，6，7，10，12，18}为叶结点权值所构造的哈夫曼树，其带权路径长度为（ ）。
A、165
B、155
C、160
D、170
参考资料【 】
16、【单选题】已知一算术表达式的中缀形式为 A+BC-D/E，后缀形式为ABC+DE/-，其前缀形式为（ ）。
A、-A+BC/DE
B、-A+BCD/E
C、-+ABC/DE
D、-+ABC/DE
参考资料【 】
17、【单选题】若一个具有n个结点k条边的无向图是一个森林（nk），则该森林必有（ ）棵树。
A、k
B、n
C、n-k
D、n+k
参考资料【 】
18、【单选题】一棵二叉树结点的（ ）可唯一确定一棵二叉树。
A、前序序列和中序序列
B、前序序列和后序序列
C、中序序列
D、后序序列
参考资料【 】
19、【单选题】设a=6,b=4,c=2,d=3,e=2，则后缀表达式abc-/de*+的值为（ ）。
A、12
B、5.5
C、9
D、10
参考资料【 】
20、【单选题】若二叉树有n个结点，当执行中序遍历的递归程序时，在最坏情况下为处理递归调用所设的栈需要（ ）个单元。
A、n-1
B、n
C、n/2
D、n+1
参考资料【 】
21、【单选题】具有64个结点的完全二叉树的深度为（ ）。
A、5
B、6
C、7
D、8
参考资料【 】
22、【单选题】A，B为一棵二叉树上的两个结点，在中序遍历时，A在B前的条件是（ ）。
A、A在B右方
B、A是B祖先
C、A在B左方
D、A是B子孙
参考资料【 】
23、【单选题】把一棵树转换为二叉树后，这棵二叉树的形态是（ ）。
A、唯一的
B、有多种
C、有多种，但根结点都没有左孩子
D、有多种，但根结点都没有右孩子
参考资料【 】
24、【单选题】下列陈述正确的是（ ）。
A、二叉树是度为2的有序树
B、二叉树中结点只有一个孩子时无左右之分
C、二叉树中必有度为2的结点
D、二叉树中最多只有两棵子树，且有左右子树之分
参考资料【 】
25、【单选题】在哈夫曼树中，若编码长度只允许小于等于4，则除了已确定两个字符的编码为0和10外，还可以最多对 个字符进行编码。
A、3
B、4
C、5
D、6
参考资料【 】
26、【单选题】若串S= ‘software’,其前缀真子串的数目是（ ）。
A、10
B、9
C、8
D、7
参考资料【 】
27、【单选题】模式串‘ababaaababaa’的next函数值为（ ）。
A、012345678999
B、012121111212
C、011234223456
D、0123012322345
参考资料【 】
28、【单选题】StrIndex(‘Index of String’,1,‘Str’）=( ) 。
A、10
B、9
C、8
D、7
参考资料【 】
29、【单选题】设串S1=‘I AM’，S2=‘A STUDENT’，则ConcatStr(S1,S2)=( )。
A、‘I AM’
B、‘A STUDENT’
C、‘I AM A STUDENT’
D、‘IAMASTUDENT’
参考资料【 】
30、【单选题】设有三个串S1、S2和S3，则StrReplace(S1,S2,S3)运算称作( )。
A、串连接
B、模式匹配
C、求子串
D、串替换
参考资料【 】
31、【单选题】假设以行序为主序存储二维数组A=array[1…100，1…100]，设每个数组元素占2个存储单元，基地址为10，则LOC[5，5]=（ ）。
A、808
B、818
C、1010
D、1020
参考资料【 】
32、【单选题】有一个100*90的稀疏矩阵，非零元素（int型）有10个，假设int型占2个字节，则用三元组顺序表表示该矩阵时所需的字节数是（ ）。
A、60
B、66
C、18
D、33
参考资料【 】
33、【单选题】广义表（a,(b,c),d,e）的表头为（ ）。
A、a
B、a,(b,c)
C、(a,(b,c))
D、(a)
参考资料【 】
34、【单选题】数组A[0…4,-1…-3,5…7]中含有元素的个数（ ）。
A、55
B、45
C、35
D、25
参考资料【 】
35、【单选题】对下述矩阵进行压缩存储后，失去随机存取功能的是（ ）。
A、对称矩阵
B、三角矩阵
C、三对角矩阵
D、稀疏矩阵
参考资料【 】
36、【判断题】完全二叉树一定存在度为1的结点。
A、正确
B、错误
参考资料【 】
37、【判断题】一棵树中的叶子数一定等于与其对应的二叉树的叶子数。
A、正确
B、错误
参考资料【 】
38、【判断题】在叶子数目和权值相同的所有二叉树中，带权路径长度最小的树一定是完全二叉树。
A、正确
B、错误
参考资料【 】
39、【判断题】给定二叉树先、中和后序遍历序列中的两个，可以唯一确定一棵二叉树。
A、正确
B、错误
参考资料【 】
40、【判断题】满二叉树一定完全是二叉树。
A、正确
B、错误
参考资料【 】
41、【判断题】一棵二叉树中，中序遍历序列的最后一个结点，必定是该二叉树前序遍历的最后一个结点。
A、正确
B、错误
参考资料【 】
42、【判断题】在完全二叉树中，若一个结点没有左孩子，则它必然是叶子结点。
A、正确
B、错误
参考资料【 】
43、【判断题】具有n个叶子结点的哈夫曼树共有2n-1个结点。
A、正确
B、错误
参考资料【 】
44、【判断题】串的存储结构有顺序串、堆串和块链串三种。
A、正确
B、错误
参考资料【 】
45、【判断题】串中任意个字符组成的子序列称为该串的子串。
A、正确
B、错误
参考资料【 】
46、【判断题】串’student’和’Student’相等。
A、正确
B、错误
参考资料【 】
47、【判断题】一个广义表的表头一定还是个广义表。
A、正确
B、错误
参考资料【 】
48、【判断题】稀疏矩阵中非零元素的个数远小于矩阵中元素的总数。
A、正确
B、错误
参考资料【 】
49、【判断题】数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。
A、正确
B、错误
参考资料【 】
50、【判断题】多维数组可以看作是一种特殊的线性表。
A、正确
B、错误
参考资料【 】