数据结构复习重点.docx
《数据结构复习重点.docx》由会员分享，可在线阅读，更多相关《数据结构复习重点.docx（19页珍藏版）》请在冰点文库上搜索。
数据结构复习重点
第二章线性表
❑在长度为n的顺序表的第i（1≤i≤n+1）个位置上插入一个元素，元素的移动次数为（A）
A.n-i+1B.n-iC.iD.i-1
❑在单链表中，指针p指向元素为x的结点，实现“删除x的后继”的语句是（B）
A.p=p->next;B.p->next=p->next->next;
C.p->next=p;D.p=p->next->next;
❑带头结点head的单链表为空的判断条件是（ B ）
A.head=NULL B.head->next=NULL
C.head->next=head D.head=NULL
❑在下图所示的链表中，若在指针p所指的结点之后插入数据域值相继为a和b的两个结点，则可用下列两个语句实现该操作，它们依次是________和________。
s->next->next=p->next;p->next=s;
❑
在需要经常查找结点的前驱与后继的场合中，使用（ B ）比较合适。
A.单链表 B.双链表 C.顺序表 D.循环链表
❑若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（A）存储方式最节省时间。
【哈尔滨工业大学2001】
A．顺序表B．双链表C．带头结点的双循环链表D．单循环链表
❑某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（D）存储方式最节省运算时间。
【南开大学2000】
A．单链表B．仅有头指针的单循环链表C．双链表D．仅有尾指针的单循环链表
❑对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（C）。
A．O（n）O（n）B.O（n）O
（1）C.O
（1）O（n）D.O
（1）O
（1）【青岛大学2000】
❑在双向链表指针p的结点前插入一个指针q的结点操作是（C）。
【青岛大学2000】
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;
❑在单链表指针为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;【青岛大学2001】
❑当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_______存储结构。
【北方交通大学2001】顺序表
❑线性表有两种存储结构：
一是顺序表，二是链表。
试问：
（1）如果有n个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表的总数也会自动地改变。
在此情况下，应选用哪种存储结构？
链表
（2）若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么应采用哪种存储结构？
【西安电子科技大学1999软件】顺序表
❑以下程序的功能是实现带附加头结点的单链表数据结点逆序连接，请填空完善之。
voidreverse（pointerh）
/*h为附加头结点指针*/
{
pointerp,q;
p=h->next;h->next=NULL;
while（
（1）________）p!
=NULL
{
q=p;p=p->next;q->next=h->next;
h->next=
（2）________;q
}
}【西南交通大学2000】
❑以下函数中，h是带头结点的双向循环链表的头指针。
（1）说明程序的功能；判断链表中的数据是否对称
（2）当链表中结点数分别为1和6（不包括头结点）时，请写出程序中while循环体的执行次数。
intf（DListNode*h）
{
DListNode*p,*q;
intj=1;
p=h->next;
q=h->prior;
while（p!
=q&&p->prior!
=q）
if（p->data==q->data）
{
p=p->next;
q=q->prior;
}
elsej=0;
returnj;
}
❑设有一个由正整数组成的无序单链表，编写完成下列功能的算法：
①找出最小值结点，且打印该数值；
②若该数值是奇数，则将其与直接后继结点的数值交换；
③若该数值是偶数，则将其直接后继结点删除。
第三章栈和队列
❑假设以S和X分别表示进栈和退栈操作，则对输入序列a,b,c,d,e进行一系列栈操作SSXSXSSXXX之后，得到的输出序列为________。
bceda
❑验证卡布列克常数。
对于一个四位数n，进行下列的运算：
①将组成该四位数的4个数字由大到小排列，形成由这4个数字构成的最大的四位数；②将组成该四位数的4个数字由小到大排列，形成由这4个数字构成的最小的四位数（如果4个数字中含有0，则得到的数不足四位）；③求这两个数的差，得到一个新的四位数（高位零保留），称为对n进行了一次卡布列克运算。
有这样的规律：
对一个各位上数字不全相同的四位数重复进行若干次卡布列克运算，最后得到的结果总是6174。
这个数被称为卡布列克常数。
提示：
设过程kblk（n）可对n施行若干次卡布列克运算，直至结果值为6174或0为止（0为n的各位完全相同时所得的结果）。
过程kblk（n）先对n施行一次卡布列克运算得到num，则以后的运算可以由kblk（num）完成，这样就形成了递归。
递归结束的条件是：
所得到的结果为6174或0。
❑一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（B）。
A.不确定B.n-i+1C.iD.n-I
❑若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j个输出元素是（D）。
A.i-j-1B.i-jC.j-i+1D.不确定的
【武汉大学2000】
❑有六个元素6，5，4，3，2，1的顺序进栈，问下列哪一个不是合法的出栈序列？
（C）
A.543612B.453126C.346521D.234156
【北方交通大学2001】
❑执行完下列语句段后，i值为：
（B）【浙江大学2000】
intf（intx）
{return（（x>0）?
x*f（x-1）:
2）;}
inti;
i=f（f
（1））;
A．2B.4C.8D.无限递归
❑当两个栈共享一存储区时，栈利用一维数组stack（1,n）表示，两栈顶指针为top[1]与top[2]，则当栈1空时，top[1]为_______，栈2空时，top[2]为_______，栈满时为_______。
【南京理工大学1997】1；n；top[2]=top[1]–1或top[1]=top[2]+1
❑有5个元素，其入栈次序为：
A，B，C，D，E，在各种可能的出栈次序中，以元素C，D最先出栈（即C第一个且D第二个出栈）的次序有哪几个？
【西南交通大学2000】CDBAE；CDBEA；CDEBA
❑用一个数组S（设大小为MAX）作为两个堆栈的共享空间。
请说明共享方法，栈满/栈空的判断条件，并用C设计公用的入栈操作push（i，x），其中i为0或1，用于表示栈号，x为入栈值。
【浙江大学1998】
❑设有两个栈S1,S2都采用顺序栈方式，并且共享一个存储区[O..maxsize-1]，为了尽量利用空间，减少溢出的可能，可采用栈顶相向，迎面增长的存储方式。
试设计S1,S2有关入栈和出栈的操作算法。
【哈尔滨工业大学2001】
❑循环队列A[0..m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是（A）。
【南京理工大学2001】
A.（rear-front+m）%mB.rear-front+1
C.rear-front-1D.rear-front
❑循环队列存储在数组A[0..m]中，则入队时的操作为（D）。
【中山大学1999】
A.rear=rear+1B.rear=（rear+1）mod（m-1）
C.rear=（rear+1）modmD.rear=（rear+1）mod（m+1）
❑若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？
（B）【浙江大学1999】
A.1和5B.2和4C.4和2D.5和1
❑设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3,e6,e5,e1则栈S的容量至少应该是（C）。
A．6B.4C.3D.2
❑若以1234作为双端队列的输入序列，则既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列是（C）。
【西安电子科技大学1996】
A.1234B.4132C.4231D.4213
❑已知输入序列为abcd经过输出受限的双向队列后能得到的输出序列有（BD）。
A.dacbB.cadbC.dbcaD.bdacE.以上答案都不对【西安交通大学1996】
第四章串
一、选择题
1．下面关于串的的叙述中，哪一个是不正确的？
（B）【北方交通大学2001】
A．串是字符的有限序列B．空串是由空格构成的串
C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储
2若串S1=‘ABCDEFG’,S2=‘9898’,S3=‘###’,S4=‘012345’,执行
concat（replace（S1,substr（S1,length（S2）,length（S3））,S3）,substr（S4,index（S2,‘8’）,length（S2）））
其结果为（E）【北方交通大学1999】
A．ABC###G0123B．ABCD###2345C．ABC###G2345D．ABC###2345
E．ABC###G1234F．ABCD###1234G．ABC###01234
3．已知串S=‘aaab’,其Next数组值为（A）。
【西安电子科技大学1996】
A．0123B．1123C．1231D．1211
4．串‘ababaaababaa’的next数组为（C）。
【中山大学1999】
A．012345678999B．012121111212C．011234223456D．0123012322345
二、填空题
1．实现字符串拷贝的函数strcpy为：
voidstrcpy（char*s,char*t）/*copyttos*/
{
while（________）;s++=t++
}【浙江大学1999】
2．下列程序判断字符串s是否对称，对称则返回1，否则返回0；如f（"abba"）返回1，f（"abab"）返回0；
intf（
（1）________）char*s
{
inti=0,j=0;
while（s[j]）
（2）________;j++
for（j--;ireturn（（3）_______）j>i?
0:
1
}【浙江大学1999】
三、编程题
1．写一个递归算法来实现字符串逆序存储，要求不另设串存储空间。
【西南交通大学2000】
2．S=“S1S2…Sn”是一个长为N的字符串，存放在一个数组中，编程序将S改造之后输出：
（1）将S的所有第偶数个字符按照其原来的下标从大到小的次序放在S的后半部分；
（2）将S的所有第奇数个字符按照其原来的下标从小到大的次序放在S的前半部分；
例如：
S=“ABCDEFGHIJKL”；则改造后的S为”ACEGIKLJHFDB”。
【中科院计算所1995】
3.设计一C语言的函数atoi（x）。
其中X为字符串，由0--9十个数字符和表示正负数的‘-’组成，返回值为整型数值。
【浙江大学1994】
第五章数组
❑1.三维数组A[4][5][6]按行优先存储方法存储在内存中，若每个元素占2个存储单元，且数组中第一个元素的存储地址为120，则元素A[3][4][5]的存储地址为（B）
A.356B.358C.360D.362
❑2.假设一个10阶的下三角矩阵A按列优先顺序压缩存储在一维数组C中，则C数组的大小应为55。
❑3.已知一个6行6列的稀疏矩阵中非零元的值分别为：
-90，41，-76，28，-54，65和-8，它们在矩阵中的列号依次为：
1，4，5，1，2，4和5，行号依次为0，0，1，2，2，3和5。
请写出该稀疏矩阵。
❑4.如下nxn矩阵，压缩存储到一维数组，写出[i,j]与一维数组下标k之间的关系。
k=i+j
❑5.设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为（B）。
A.BA+141B.BA+180C.BA+222D.BA+225
【南京理工大学1997】
❑6.若对n阶对称矩阵A以行序为主序方式将其下三角形的元素（包括主对角线上所有元素）依次存放于一维数组B［1..（n（n+1））/2］中，则在B中确定aij（iA.i*（i-1）/2+jB.j*（j-1）/2+iC.i*（i+1）/2+jD.j*（j+1）/2+i
【北京航空航天大学2000】
❑7.有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是（A）。
【南京理工大学1999】
A.60B.66C.18000D.33
❑8.已知广义表L=（（x,y,z），a，（u，t，w）），从L表中取出原子项t的运算是（D）。
A.head（tail（tail（L）））
B.tail（head（head（tail（L））））
C.head（tail（head（tail（L））））
D.head（tail（head（tail（tail（L）））））
【北京邮电大学1998】
❑9.广义表A=（a,b,（c,d）,（e,（f,g）））,则下面式子的值为（C）。
【北京邮电大学1999】
Head（Tail（Head（Tail（Tail（A）））））
A.（g）B.（d）C.cD.d
❑10.下面说法不正确的是（A）。
【南京理工大学2001】
A.广义表的表头总是一个广义表
B.广义表的表尾总是一个广义表
C.广义表难以用顺序存储结构
D.广义表可以是一个多层次的结构
❑深度为5的二叉树至多有（ C ）个结点。
A.16 B.32 C.31 D.10
❑按照二叉树的定义，具有3个结点的二叉树有（ C ）种形式。
A.3 B.4 C.5 D.6
❑已知二叉树的先序序列为ABDECF，中序序列为DBEAFC，则后序序列为（D）
A.DEBAFCB.DEFBCAC.DEBCFAD.DEBFCA
❑给出下列二叉树的先序、中序和后序序列。
第六章树和二叉树
❑假设字符a,b,c,d,e,f的使用频度分别是0.05,0.04,0.10,0.31,0.20,0.30，请先画出你所构造的哈夫曼树，然后写出a,b,c,d,e,f的Huffman（哈夫曼）编码。
❑有n个结点的二叉树的最大深度为n，最小深度为log2n+1向下取整，有n个结点的完全二叉树的最大深度为log2n+1向下取整。
❑有21个结点的二叉树中，叶结点最多有多少个11。
❑已知一棵度为3的树中，有8个度为2的结点，5个度为3的结点，请问该树中有多少个叶子结点？
19
❑已知一算术表达式的中缀形式为A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为（D）【北京航空航天大学1999】
A．-A+B*C/DEB.-A+B*CD/EC．-+*ABC/DED.-+A*BC/DE
☐设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1则T中的叶子数为（D）【南京理工大学2000】
A．5B．6C．7D．8
☐若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（B）【北京工商大学2001】
A．9B．11C．15D．不确定
❑有n个叶子的哈夫曼树的结点总数为（D）。
【青岛大学2002】
A．不确定B．2nC．2n+1D．2n-1
❑一棵树高为K的完全二叉树至少有（C）个结点【南京理工大学1998】
A．2k–1B.2k-1–1C.2k-1D.2k
❑具有256个结点的完全二叉树的深度为9。
【燕山大学1998】
❑一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（C）【南开大学2000】
A．所有的结点均无左孩子B．所有的结点均无右孩子C．只有一个叶子结点D．是任意一棵二叉树
❑一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有（B）结点
A．2hB．2h-1C．2h+1D．h+1【南京理工大学2001】
❑41．对于前序遍历与中序遍历结果相同的二叉树为（F）;对于前序遍历和后序遍历结果相同的二叉树为（B）。
【中科院计算所】
A．一般二叉树B．只有根结点的二叉树C．根结点无左孩子的二叉树
D．根结点无右孩子的二叉树E．所有结点只有左子数的二叉树F．所有结点只有右子树的二叉树
❑下列是先序遍历二叉树的非递归子程序，请阅读子程序，填充空格，使其成为完整的算法。
【同济大学2001】
voidexample（bTree*b）
{
bTree*stack[20],*p；
inttop;
if（b!
=null）
{
top=1;stack[top]=b;
while（top>0）
{
p=stack[top];top--;
printf（“%d”,p->data）;
if（p->rChild!
=null）
{
（1）___;
（2）___;}top++;stack[top]=p->rChild;
if（p->lChild!
=null）
{（3）___;（4）__;}top++;stack[top]=p->lChild;
}
}
}
❑以下程序为求二叉树深度的递归算法，请填空完善之。
intdepth（biTreebt）/*bt为根结点的指针*/
{
inthl,hr;
if（bt==NULL）
return（
（1）___）;0
hl=depth（bt->lchild）;
hr=depth（bt->rchild）;
if（
（2）___）hl>hr；
（3）_____；returnhl+1;或hl>hr;hr=hl;
return（hr+1）;
}【西南交通大学2000】
❑设一棵二叉树的先序、中序遍历序列分别为
先序遍历序列：
ABDFCEGH中序遍历序列：
BFDAGEHC
（1）画出这棵二叉树。
（2）画出这棵二叉树的后序线索树。
（3）将这棵二叉树转换成对应的树（或森林）。
【南京航空航天大学1997】
❑将下列由三棵树组成的森林转换为二叉树。
（只要求给出转换结果）NPGHJMOLIKEDFBAC【南京航空航天大学1998】
第七章图
❑无向图中一个顶点的度是指图中（B）
A.通过该顶点的简单路径数B.与该顶点相邻接的顶点数
C.通过该顶点的回路数D.与该顶点连通的顶点数
❑在一个具有n个顶点的无向图中，要连通全部顶点至少需要（ C ）条边。
A.n B.n+1 C.n-1 D.n/2
❑n个顶点的有向完全图中含有向边的数目最多为（D）
A.n-1B.nC.n（n-1）/2D.n（n-1）
❑在无向图的邻接矩阵A中，若A（i,j）等于1，则A（j,i）等于1。
❑已知一个有向图如右所示，则从顶点a出发进行深度优先遍历，不可能得到的DFS序列为（A）
A.adbefcB.adcefb
C.adcbfeD.adefcb
❑一个n个顶点的连通无向图，其边的个数至少为（A）。
【浙江大学1999】
A．n-1B．nC．n+1D．nlogn；
❑一个有n个结点的图，最少有（B）个连通分量，最多有（D）个连通分量。
【北京邮电大学2000】
A．0B．1C．n-1D．n
❑在一个无向图中，所有顶点的度数之和等于所有边数（B）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（C）倍。
【哈尔滨工业大学2001】
A．1/2B．2C．1D．4
❑若一
升级会员 