A、O（n）B、O（nlog2n）C、O（n2）D、O（log2n）
答：
x++执行次数为（n-1）+（n-2）+…+1=n（n-1）/2，故时间复杂度为O（n2）
15以下与数据的存储结构无关的术语是D
A、循环队列B、链表C、哈希表D、栈
16组成数据的基本单位是C
A、数据项B、数据类型C、数据元素D、数据变量
17算法分析的目的是C
A、找出数据结构的合理性B、研究算法中的输入和输出的关系
C、分析算法的效率以求改进D、分析算法的易懂性和文档性
18算法分析的两个主要方面是A
A、空间复杂性和时间复杂性B、正确性和简明性
C、可读性和文档性D、数据复杂性和程序复杂性1
9下面程序段的时间复杂度为B
for（inti=1;i<=n;i++）for（intj=1;j<=n;j++）{x++;s+=x；}
A、O（n）B、O（n2）C、O（log（n））D、O（n3）
20以下所列选项中哪个不是线性结构？
B
A、线性表B、图C、字符串D、队列二.
判断题
1数据的机内表示称为数据的存储结构。
√
2算法就是程序。
×
3数据元素是数据的最小单位。
×
4算法的五个特性为：
有穷性、输入、输出、完成性和确定性。
×
5算法的时间复杂度取决于问题的规模和待处理数据的初态。
√
第2章
1下述哪一条是顺序存储结构的优点？
A
A、存储密度大B、插入运算方便C、删除运算方便D、可方便地用于各种逻辑结构的存储表示
2下面关于线性表的叙述中，错误的是哪一个？
B
A、线性表采用顺序存储，必须占用一片连续的存储单元
B、线性表采用顺序存储，便于进行插入和删除操作
C、线性表采用链接存储，不必占用一片连续的存储单元
D、线性表采用链接存储，便于插入和删除操作
3线性表是具有n个（）的有限序列（n>=0）C
A、数据对象B、字符C、数据元素D、数据项
4若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（A）存储方式最节省时间
A、顺序表B、单链表C、带头结点的双循环链表D、单循环链表
5某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（D）存储方式最节省运算时间
A、单链表B、仅有头指针的单循环链表C、双链表D、仅有尾指针的单循环链表
6对于一个头指针为heAd的带头结点的单链表，判定该表为空表的条件是B
A、heAd==NULLB、heAd→next==NULLC、heAd→next==heAdD、heAd!
=NULL
7若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。
则采用（）存储方式最节省运算时间。
D
A、单链表B、双链表C、单循环链表D、带头结点的双循环链表
8在单链表指针为p的结点之后插入指针为s的结点，正确的操作是B
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;
9链表不具有的特点是B
A、插入、删除不需要移动元素B、可随机访问任一元素
C、不必事先估计存储空间D、所需空间与线性度成正比正
10若长度为n的线性表采用顺序存储结构,在其第i个位置插入一个新元素算法的时间复杂度为C
A、O（log2n）B、O
（1）C、O（n）D、O（n2）
11在一个长度为n的顺序表中,在第i个元素之前插入一个新元素时,需向后移动（）个元素。
B
A、n-IB、n-i+1C、n-i-1D、i
12在双向循环链表中,在p指针所指的结点后插入一个指针q所指向的新结点,修改指针的操作是C
A、p->next=q;q->prior=p;p->next->prior=q;q->next=q;
B、p->next=q;p->next->prior=q;q->prior=p;q->next=p->next;
C、q->prior=p;q->next=p->next;p->next->prior=q;p->next=q;
D、q->next=p->next;q->prior=p;p->next=q;p->next=q;
13线性表采用链式存储时,结点的存储地址C
A、必须是连续的B、必须是不连续的C、连续与否均可D、和头结点的存储地址相连续
14在具有n个结点的单链表上查找值为x的元素时,其时间复杂度为A
A、O（n）B、O
（1）C、O（n2）D、O（n-1）
15一个顺序表的第一个元素的存储地址是90,每个元素的长度为2,则第6个元素的存储地址是B
A、98B、100C、102D、106
16在一个单链表中,若删除p所指向结点的后续结点,则执行A
A、p->next=p->next->next;B、p=p->next;p->next=p->next->next;C、p=p->next;D、p=p->next->next;
17将长度为n的单链表连接在长度为m的单链表之后的算法的时间复杂度为C
A、O
（1）B、O（n）C、O（m）D、O（m+n）
18单链表的存储结构所占存储空间A
A、分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针
B、只有一部分，存放结点值
C、只有一部分，存储表示结点间关系的指针D、分两部分，一部分存放结点值，另一部分存放结点所占单元数
19向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（）个元素B
A、8B、63.5C、63D、7
20设指针q指向单链表中结点A，指针p指向单链表中结点A的后继结点B，指针s指向被插入的结点X，则在结点A和结点B插入结点X的操作序列为B
A、s->next=p->next;p->next=-s;B、q->next=s;s->next=p;
C、p->next=s->next;s->next=p;D、p->next=s;s->next=q;
二.判断题
1顺序存储结构的主要缺点是不利于插入或删除操作。
√
2对任何数据结构链式存储结构一定优于顺序存储结构。
×
3顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。
×
4线性表就是顺序存储的表。
×我的答案：
√
5链表是采用链式存储结构的线性表,进行插入、删除操作时，在链表中比在顺序存储结构中效率高。
√
第3章
1对于栈操作数据的原则是B
A、先进先出B、后进先出C、后进后出D、不分顺序
2对于队列操作数据的原则是A
A、先进先出B、后进先出C、后进后出D、不分顺序
3一个栈的输出序列为123…n，若输出序列的第1个元素是n，输出第i（1<=i<=n）个元素是B
A、不确定B、n-i+1C、ID、n-i
4若一个栈的输出序列为1,2,3,…,n，输出序列的第1个元素是i，则第j个输出元素是D
A、i-j-1B、i-jC、j-i+1D、不确定
5一个栈的输出序列为12345，则下列序列中不可能是栈的输出序列的是B
A、23415B、54132C、23145D、15432
6若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为C
A、IB、n-IC、n-i+1D、不确定
7判定一个栈ST（最多元素为m0）为空的条件是B
A、ST->top<>0B、ST->top==0
C、ST->top<>m0D、ST->top==m0
8数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素的公式为D
A、r－fB、（n＋f－r）%n
C、n＋r－fD、（n＋r－f）%n
9若已知一个栈的进栈序列是1,2,3,…,n,其输出序列为p1,p2,p3,...,pn,若p1=3,则p2为A
A、可能是2B、一定是2C、可能是1D、一定是1
10若已知一个栈的出栈序列是1,2,3,…,n，其输出序列为p1,p2,p3，…，pN,若pN是n，则pi是D
A、iB、n-IC、n-i+1D、不确定
11用链式方式存储的队列,在进行删除运算时D
A、仅修改头指针B、仅修改尾指针C、头、尾指针都要修改D、头、尾指针可能都要
答：
当删除的是最后一个元素时，既要修改头指针，又要修改尾指针。
12设计一个判别表达式中左右括号是否匹配的算法，采用哪种数据结构最佳D
A、线性表的顺序存储结构B、队列C、线性表的链式存储结构D、栈
13输入序列为ABC，可以变为CBA时，经过的栈操作为B
A、push,pop,push,pop,push,popB、push,push,push,pop,pop,pop
C、push,push,pop,pop,push,popD、push,pop,push,push,pop,pop
14有六个元素按6，5，4，3，2，1的顺序进栈，问下列哪一个不是合法的出栈序列？
C
A、543612B、453126C、346521D、234156
15递归过程或函数调用时，处理参数及返回地址，要用一种称为（）的数据结构C
A、队列B、多维数组C、栈D、线性表
16若一个栈以向量V[1..n]存储，初始栈顶指针top为n+1，则下面x进栈的正确操作是C
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;
17如果入栈顺序为1、2、3、4、5、6，则不可能得到的出栈序列为C
A、123456B、654321C、563421D、346521
18循环队列是为了解决队列顺序存储时可能会出现的（）现象A
A、假溢出B、队空C、队满D、队空队满时条件一致
19数组Ｑ[n]用来表示一个循环队列，front为队头指针，reAr为队尾指针，计算队列中元素个数的公式为D
A、reAr－frontB、（front－reAr＋n）%n
C、reAr－front＋nD、（reAr－front＋n）%n
20设一个栈的输出序列是1，2，3，4，5,则下列序列中，是栈的合法输出序列的是D
A、51234B、45132
C、43125D、32154
二.判断题
1栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。
√
2对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。
√
答：
正确，都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。
3栈和队列是一种非线性数据结构。
×
4栈和队列的存储方式既可是顺序方式，也可是链接方式。
√
5队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。
×
第4章
1下面关于串的的叙述中，哪一个是不正确的？
B
A、串是字符的有限序列B、空串是由空格构成的串
C、模式匹配是串的一种重要运算D、串既可以采用顺序存储，也可以采用链式存储
2串是一种特殊的线性表，其特殊性体现在B
A、可以顺序存储B、数据元素是一个字符C、可以链式存储D、数据元素可以是多个字符
3串的长度是指B
A、串中所含不同字母的个数B、串中所含字符的个数
C、串中所含不同字符的个数D、串中所含非空格字符的个数
4设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为C
A、求子串B、串联接C、模式匹配D、求串长
5若串S=“softwAre”,其子串的个数是B
A、8B、37C、36D、9
长度为1的子串有8个，长度为2的子串有7个，…，长度为7的子串有2个，长度为8的子串有1个，加上空串，8+7+……+2+1+1=37
二.判断题
1串是一种数据对象和操作都特殊的线性表。
√
2只包含空格的串称为空串×
3字符串是线性结构。
√
4空串与由空格组成的串没区别。
×
5子串“ABC”在主串“AABCABCD”中的位置为2。
√
第5章：
1对稀疏矩阵进行压缩存储的目的是A
A、为了节省存储空间B、便于输入和输出C、便于进行矩阵运算D、降低运算的时间复杂度
2一个非空广义表的表头D
A、不可能是子表B、只能是子表C、只能是原子D、可以是子表或原子
3假设有二维数组A6×8，每个元素用相邻的6个字节存储，已知A的起始存储位置（基地址）为1000，则末尾元素A57的第一个字节地址为B
A、1288B、1282C、1200D、2000
答：
元素个数一共有6*8=48个，每个占6个字节，共288个字节，所以最后一个元素的地址为1000+288-6=1082。
4对n阶对称矩阵进行压缩存储的目的是A
A、为了节省存储空间B、便于输入和输出
C、便于进行矩阵运算D、降低运算的时间复杂度
5一个非空广义表的表尾B
A、不可能是子表B、只能是子表C、只能是原子D、可以是子表或原子
6设矩阵A是一个对称矩阵，为了节省存储，将其下三角部分按行序存放在一维数组B[1,n（n-1）/2]中，对下三角部分中任一元素Ai,j（i>=j）,在一维数组B中下标k的值是B
A、i（i-1）/2+j-1B、i（i-1）/2+jC、i（i+1）/2+j-1D、i（i+1）/2+j答：
注意数组下标从1开始！
7有一个二维数组A，行下标的范围是1到6，列下标的范围是0到7，每个数组元素用相邻的6个字节存储，这个数组一共占多少个字节？
C
A、252B、282C、288D、240答：
6*8*6=288
8假设有60行70列的二维数组A[1…60,1…70]以列序为主序顺序存储，其基地址为10000，每个元素占2个存储单元，那么第32行第58列的元素A[32,58]的存储地址为。
A
A、16902B、16904C、14454D、答案A,B,C均不对答：
（57列×60行＋31行）×2字节＋10000=16902
9GetHeAd（GetTAil（（A,b）,（c,d）））=B
A、（A,b）B、（c,d）C、（（A,b）,（c,d））D、以上都不对
10设数组A[1…60,1…70]的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存储，则元素A[32,58]的存储地址为B
A、4454B、6454C、6456D、6596
11设广义表L=（（A，b，c）），则L的长度和深度分别为C
A、1和1B、1和3C、1和2D、2和3
12稀疏矩阵的两种常见压缩存储方法是C
A、二维数组和三维数组B、三元组和散列表
C、三元组顺序表和十字链表D、散列表和十字链表
13数组A[0..5,0..6]的每个元素占5个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5][5]的地址是A
A、1175B、1180C、1205D、1210
14对广义表L=（（A,b）,（（c,d）,（e,f）））执行heAd（tAil（heAd（tAil（L））））操作的结果是D
A、（A,b）B、（（c,d）,（e,f））C、（c,d）D、（e,f）
15广义表运算式HEAD（TAIL（（A,b,c）,（x,y,z）））的结果是A
A、（x,y,z）B、（A,b,c）C、空D、（（x,y,z））
.判断题
1广义表是一种多层次的数据结构，其元素可以是单原子也可以是子表。
√
2二维数组和多维数组均不是特殊的线性结构。
×
3广义表的长度是指广义表中括号嵌套的层数。
×
4稀疏矩阵可由表示非零元的三元组及其行列数唯一确定。
√
5广义表A=（）的深度为1，长度为0。
√
第6章
1把一棵树转换为二叉树后，这棵二叉树的形态是A
A、唯一的B、有多种C、有多种，但根结点都没有左孩子D、有多种，但根结点都没有右孩子
2在中序线索二叉树中，若某结点有右孩子，则该结点的直接后继是D
A、其左子树的最右下结点B、其右子树的最右下结点
C、其左子树的最左下结点D、其右子树的最左下结点
3在中序线索二叉树中，若某结点有左孩子，则该结点的直接前驱是C
A、其左子树的最右下结点B、其右子树的最右下结点
C、其左子树的最左下结点D、其右子树的最左下结点
4二叉树的深度为k，则二叉树最多有多少个结点？
C
A、2k+1B、2kC、2k-1D、2k+2
5设一棵二叉树的中序遍历序列：
bAdce，后序遍历序列：
bdecA，则二叉树先序遍历序列为D
A、AdbceB、decAbC、debAcD、Abcde
6一棵具有5层的满二叉树中结点总数为A
A、31B、32C、33D、16
7某二叉树的中序序列为ABCDEFG，后序序列为BDCAFGE，则其左子树中结点数目为C
A、3B、2C、4D、5
8若以{4,5,6,7,8}作为权值构造哈夫曼树，则该树的带权路径长度为C
A、67B、68C、69D、70
9将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为A
A、98B、99C、50D、48
10树最适合用来表示C
A、有序数据元素B、无序数据元素
C、元素之间具有层次关系的数据D、元素之间无联系的数据
11表达式A*（b+c）-d的后缀表达式是B
A、Abcd+-B、Abc+*d-C、Abc*+d-D、-+*Abcd
12对某二叉树进行先序遍历的结果为ABDEFC，中序遍历的结果为DBFEAC，则后序遍历的结果是B
A、DBFEACB、DFEBCAC、BDFECAD、BDEFAC
15，度为1的结点数为30，则叶子结点数为B
A、15B、16C、17D、18
14下面说法中正确的是D
A、度为2的树是二叉树B、度为2的有序树是二叉树
C、子树有严格左右之分的树是二叉树D、子树有严格左右之分，且度不超过2的树是二叉树
15树的先根序列等同于与该树对应的二叉树的A
A、先序序列B、中序序列C、后序序列D、层序序列
16按照二叉树的定义，具有3个结点的二叉树有几种形态？
C
A、3B、4C、5D、6
17具有200个结点的完全二叉树的深度为B
A、7B、8C、9D、10
18二叉树是非线性数据结构，所以C
A、它不能用顺序存储结构存储B、它不能用链式存储结构存储
C、顺序存储结构和链式存储结构都能存储D、顺序存储结构和链式存储结构都不能使用
19设一棵完全二叉树有700个结点，则有多少个叶
升级会员 