A［i］［j]=i*j;
A.O（m2）B。
O（n2）C.O（m＊n）D。
O（m+n）
12.数据结构通常是研究数据的A及它们之间的联系。
A存储和逻辑结构B存储和抽象
C理想和抽象D理想与逻辑
13.算法分析的目的是___B______
A、找出数据结构的合理性B、分析算法的效率以求改进、研究算法中的
C、输入和输出的关系D、分析算法的易懂性和文档性
14.算法分析的两个主要方面是：
A
A空间复杂性和时间复杂性B正确性和简明性
C可读性和文档性D数据复杂性和程序复杂
15.线性表Ｌ在B情况下适用于使用链式结构实现.
A需经常修改Ｌ中的结点值B需不断对Ｌ进行删除插入
CＬ中含有大量的结点DＬ中结点结构复杂
四、程序题
typedefstructLNode{
intdata;
structLNode＊next；
｝LNode,＊LinkList；
1.将下面算法填完整。
voidListInsert_L（nodeL,inti,elementtypex）
｛LinkListp=L,s；intk=0;
while（ ＆& ）
｛ ；k++;}
if（!
p｜|j〉i—1）returnERROR;
s=（LinkList）malloc（sizeof（node））;
s->data=x；
；
；}
1．P
k〈i-1
p=p—〉next
s—〉next=p—〉next；
p->next=s;
2.简述下面算法的功能
voidAC（LinkList&L）{
//L为一个无头结点的单链表
if（L&&L-〉next）｛
q=L;L=L—>next;p=L;
while（p->next）p=p-〉next;
p—>next=q；q—>next=NULL；
｝
｝
将该单链表的表头元素移到表尾
3.简述下面算法的功能
voidAE（LNode＊s，LNode*q）{
p=s；
while（p->next!
=q）p=p->next；
p—>next=s；
}
voidAD（LNode*pa,LNode＊pb）｛
//pa和pb分别指向单循环链表中的两个结点
AE（pa,pb）;
AE（pb,pa）;
｝
将一个单循环链表拆分成两个单循环链表（指针pa和pb分别指向这两个单循环链表中的某两个节点）
4.下列算法为删除带头结点的单链表head中值为x的算法，将程序填完整（每空2分）
已知结构体：
typedefstructLNode{
ElemTypedata；
structLNode*next；
｝LNode，＊LinkList；
voiddel（LinkListhead）
{q=head；
;
while（p＆＆））
{q=p；
_________;｝
if（p==null）printf（“error”）;
else
｛______________；
free（p）;printf（“success!
"）；}
｝
p=q—>next
p—〉data!
=x
p=p-〉next
q—>next=p-〉next
5。
下列算法为删除单链表中值为X的算法，将程序填完整（4分，每空2分）
已知结构体：
structnode{
ElemTypedata；
structLNode＊next;
｝；
voiddel（structnode*head）
{q=head;
p=q—〉next;
while（（p）＆＆（p-〉data！
=x））
{q=p；
______；}
if（p==null）printf（“error”）；
else{______;
free（p）；printf（“success！
"）；}}
p=q->next
q—>nex=p—>next
6。
下列算法为利用尾插法，建立一个单链表，将程序填完整程序
voidCreateList（LinkList＆L,intn）{
LinkListr,p;inti;
L=（LinkList）malloc（sizeof（node））；
L—〉next=NULL；
;
for（i=n;i>0；——i）｛
p=（LinkList）malloc（sizeof（node））;
scanf（“%c”,&p-〉data）;
；
r—>next=p；
；
｝｝
r=L;
p—〉next=NULL；
r=p;
队栈串数组广义表
一、判断题：
1.递归的算法简单、易懂、容易编写,而且执行效率也高.（f）
2.链式栈与顺序栈相比,一个明显的优点是通常不会出现栈满的情况。
（t）
3.堆栈、队列和数组的逻辑结构都是线性表结构。
（t）
4.单链表形式的队列,头指针F指向队列的第一个结点，尾指针R指向队列的最后一个结点（f）
5.若某堆栈的输入序列为1,2,3，4，则4,3，1,2不可能是堆栈的输出序列之一。
（t）
6.栈和队列都是限制取点的线性结构（t）
7.栈和队列都是顺序存取的线性表，但它们对存取位置的限制不同.（t）
8.稀疏矩阵压缩存储后，必会失去随机存取功能.（t）
9.如果两个串中含有相同的字符，则这两个串相等（f）
10.广义表的表头和表尾既可以是单元素,也可以是广义表。
（f）
二、填空题:
1.在初始为空的队列中插入元素A,B,C,D以后，紧接着做了两次删除操作，此时的队尾元素是__d__。
2.已知循环队列的存储空间为数组a[21]，且头指针（指向队头元素）和尾指针（队尾元素的下一位置）分别为8和3，则该队列的当前长度为__16__。
3.栈结构允许进行删除操作的一端为__栈顶__。
4.队列又称为__先进先出__的线性表
5.对于顺序存储的队列,存储空间大小为n，头指针为F,尾指针为R。
若在逻辑上看一个环,则队列中元素的个数为__（r+n）—f__。
6.队列的特点是__先进先出_。
7.栈又称为先进后出的线性表，队列又称为先进先出的线性表。
8.设数组A[m］为循环队列Q的存储空间，font为头指针,rear为尾指针，判定Q为空队列的条件__front==rear___。
9.设元素1，2，3，4，5依次进栈S，若要在输出端得到序列34251，则应进行的操作序列为:
push（S，1），push（S，2），push（S,3），pop（S），push（S，4），pop（S），pop（S），push（S，5）,pop（S）,pop（S）。
10.一个串的任意个连续的字符组成的子序列称为该串的子串，包含该子序列的串称为主串，该子序列在串中的位置用子串的第一个字符在主串中的位置来表示.
11.在串的链式存储方式中，结点越大，运算处理越不方便（方便/不方便）,存储占用量越小（大/小）。
12.求串T在主串S中首次出现的位置的操作是__模式匹配__。
13.广义表（A,（a,b）,d,e，（（i，j）,k））,则广义表的长度为5,深度为3,表头为A，表尾为（（a,b）,d,e,（（i，j）,k））。
14.已知广义表ls=（a，（b,c，d），e）,运用head和tail函数取出ls中的原子b的运算是_head（head（tail（ls）））_。
15.设有二维数组A[5]［6］,其每个元素占两个存储单元，第一个元素的存储地址为1100，若按行优先顺序存储，则元素A［2][3]的存储地址为1130,按列优先顺序存储，元素A[2]［3］的存储地址为1134。
16.设有二维数组A[9][19］（下标从0开始），其每个元素占两个字节，第一个元素的存储地址为100，若按行优先顺序存储,按列优顺序存储，元素A［6,6]的存储地址为__220__。
17.设二维数组A[m]［n]按列优先存储，每个元素占1个存储单元，元素A00的存储地址loc（A00），则Aij的存储地址loc（Aij）=__loc（a00）+（j*m+i）*1__.
18.
三、选择题：
1.判定一个栈ST（最多元素为m0）为空的条件是___b__
2.A．ST-〉top〈〉0B．ST—〉top=0
C．ST->top<〉m0D．ST->top=m0
3.链式栈与顺序栈相比，一个比较明显的优点是___b_____。
A。
插入操作更加方便B.通常不会出现栈满的情况
C.不会出现栈空的情况D.删除操作更加方便
4.假定一个顺序队列的队首和队尾指针分别为front和rear，则判断队空的条件是__d______。
A。
front+1==rearB。
rear+1==frontC.front==0D.front==rea
5.队和栈的主要区别是__d______
A。
逻辑结构不同B。
存储结构不同
C.所包含的运算个数不同D。
限定插入和删除的位置不同
6.假定利用数组a［N]循环顺序存储一个队列，用front（指向队首元素）和rear（指向队尾元素的下一位置）分别表示队首和队尾指针,并已知队列未空，当出队并返回队首元素时所执行的操作为__d____.
A。
returna[++rear%N]；B.returna[-—rear%N];
C.returna［++front％N]；D.returna[front++%N]；
7.入栈次序是a,b,c,d,e，则出栈次序不可能是___c_____。
A．e，d，c,b，aB．d，e，c,b,aC．d,c,e，a,bD．a,b，c，d,e
8.由两个栈共享一个向量空间的好处是___b___。
A减少存取时间,降低下溢发生的机率B节省存储空间，降低上溢发生的机率
C减少存取时间,降低上溢发生的机率D节省存储空间，降低下溢发生的机率
9.假定利用数组a［N]顺序存储一个栈，用top表示栈顶指针,top==0表示栈空，并已知栈未满，当元素x进栈时所执行的操作为___D___。
A.a［--top]=x；B。
a[top—-］=x;C.a[++top］=x；D。
B。
a[top++］=x；
10.假定利用数组a［N］顺序存储一个栈,用top表示栈顶指针，top==0表示栈空，并已知栈未空，当出栈并返回栈顶元素时所执行的操作为___A___。
A。
returna［--top］；B。
returna[top——]；C.returna［++top］；D。
returna［top++];
11.假定一个循环顺序队列的队首和队尾指针分别为f和r，则判断队空的条件是__D___。
A。
f+1==rB.r+1==f
C.f==0D。
f==r
12.若让元素1，2,3依次进栈，则出栈次序不可能出现___C___种情况.
A。
3,2,1B.2,1，3C。
3,1,2D。
1，3，2
13.当利用大小为N的一维数组存储一个循环队列时，则该队列的最大长度为___B___。
A.N—2B.N-1C.ND.N+1
14.假定利用数组a［N]循环顺序存储一个队列，用front和rear分别表示队首和队尾指针，并已知队列未满,当元素x入队时所执行的操作为___B___.
A。
a［++rear%N］=x；B.a[rear++％N]=x；C.a［-—rear％N]=x；D。
a［rear—-％N]=x；
15.如下陈述中正确的是___A___.
A.串是一种特殊的线性表B.串的长度必须大于零
C.串中元素只能是字母D。
两个串s1和s2若长度相同，则这两个串相等
16.如下陈述中正确的是___A___。
A。
串是一种特殊的线性表B.串的长度必须大于零
C.串中元素只能是字母D。
空串就是空白串
17.在以下的叙述中,正确的是___A___。
A.二维数组可以看做它的每个数据元素为一个线性表的线性表
B。
栈的操作方式是先进先出
C。
线性表的线性存储结构优于链表存储结构
D.队列的操作方式是先进后出。
18.一个非空广义表的表头___D___。
A．不可能是子表B．只能是子表
C．只能是原子D．可以是子表或原子
19.在目标串T［0…n—1]="xwxxyxy"中,对模式串p［0…m—1］=”yy”进行子串定位操作的结果____A___
A。
0B.2C。
3D。
5
20.数组A中，每个元素的长度为3字节，行下标从1到8,列下标从1到10，从首地址SA开始连续存放在存储器中,按行存放时，元素a［8][5]地址为（C）
ASA+141BSA+180
CSA+222DSA+225
21.串是一种特殊的线性表，其特殊性体现在：
B
A．可以顺序存储B．数据元素只能来自字符集
C．可以链式存储D．数据元素可以是多个字符
五、算法
1.Q是一个循环队列，请分别写出插入和删除一个元素的算法
#defineMAXSIZE100//最大队列长度
typedefstruct{
QElemType*base;
intfront，rear;
｝SqQueue;
（以下算法3分:
）
intEnQueue（SqQueue&Q，QElemTypex）
｛
//Q是一个循环队列，若队列不满，则将x插入并返回1；否则返回0
if（（Q。
rear+1）％MAXSIZE==Q。
front）
return0;//队列满
Q。
base［Q。
rear]=x；
Q.rear=（Q。
rear+1）%MAXSIZE;
return1;
｝
（以下算法3分:
）
intDeQueue（SqQueue＆Q，QElemType&x）
｛
//Q是一个循环队列，若队列不空，则删除队头元素并由x带回,
//且返回1；否则返回0
if（Q.front==Q。
rear）
return0;
else
{x=Q。
base［Q.front]；
Q。
front=（Q。
front+1）％MAXSIZE；
return1；}
）
1.已知：
Q是一个循环队列，并且已知下列定义：
＃defineMAXSIZE100
typedefstruct{
QElemTypebase［MAXSIZE];
intfront，rear；
｝SqQueue；
约定：
顺序队中，非空队中，头指针始终指向队列头元素的前一个元素，而尾指针始终指向队列尾元素。
请写出插入一个元素的算法（6分，每空2分）
intEnQueue（SqQueue&Q,QElemTypex）
{
if（ ）
return0;
Q．rear= ；
Q．base［ ]=x;
return1；
}
四．算法分析
简述下列算法的功能（栈和队列的元素类型为int）
1.StatusAA（StackS）｛
inti,n，A[255];
n=0；
while（！
StackEmpty（S））{n++;Pop（S,A［n]）；｝
for（i=1;i〈=n;i++）Push（S，A[i]）;
｝
栈S就地逆置。
2.StatusAB（StackS，inte）{
StackT；intd;
InitStack（T）;
while（!
StackEmpty（S））{
Pop（S，d）;
if（d！
=e）Push（T，d）；
}
while（！
StackEmpty（T））{
Pop（T，d）；
Push（S，d）;
}
｝
删除栈S中值等于e的元素。
3.voidAC（Queue＆Q）{
StackS；intd;
InitStack（S）；
while（！
QueueEmpty（Q））{
DeQueue（Q,d）;Push（S，d）;
}
while（!
StackEmpty（S））｛
Pop（S，d）；EnQueue（Q，d）;
}
}
队列Q就地逆置。
4.简述下面算法的功能。
（2分）
voidconversion（）
｛initstack（s）；//初始化栈
scanf（“%d”，n）;
while（n）
｛push（s,n％8）;
n=n/8；}
while（!
Stackempty（s））//Stackempty（s）为栈判空
｛pop（s,e）;
printf（“%d”，e）；
｝}
功能是：
十进制数转化成八进制数.
树
一、判断题:
1.二叉树是一棵无序树。
（×）
2.在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行中序遍历和后序遍历，则具有相同的结果。
（√）
3。
度为二的有序树等价于二叉树.（√）
4。
树的带权路径长度最小的二叉树中必定没有度为1的结点.（√）
5.哈夫曼树一定是满二叉树。
（×）
6.满二叉树也是完全二叉树。
（√）
7.设与一棵树T所对应的二叉树为BT，则与T中的叶子结点所对应的BT中的结点也一定是叶子结点。
（×）
8.将一棵树转换成二叉树后,根结点没有左子树（×）
9。
已知一棵二叉树的前序序列
升级会员 