A[1][j]=0;
(A)0(n)(B)O(m+n+1)(C)O(m+n);(D)O(m*n)
答案
D
3:
在数据结构中,数据的逻辑结构可以分成_______
(A)内部结构和外部结构(B)线性结构和非线性结构
(C)紧凑结构和非紧揍结构(D)动态结构和静态结构
答案
B
4:
算法指的是_______
(A)计算机程序(B)解决问题的计算方法
(C)排序算法(D)解决问题的有限运算序列
答案
D
5:
若结点的存储地址与其关键字之间在某种映射关系,则称这种存储结构为_______
(A)顺序存储结构(B)链式存储结构
(C)索引存储结构(D)散列存储结构
答案
D
第二章测试题
—.简答题
1:
单链表和双向链表中,能否从当前结点出发访问到任意结点?
答案
在单链表中只能由当前结点访问其后的任一结点,应为没有指向其前驱结点的指针;而在双向链表中,既有指向后继结点的指针,又有指向趋结点的指针,故可以由当前结点出发访问链表中任一结点。
2:
描述以下三个概念的区别:
头指针,头结点,首元结点(第一个元素结点)。
答案
①首先结点是链表中存储线性表中的第一个数据元数的结点;②头结点:
为了管理上的方便在第一个元素结点(首元结点)之前附设一个结点,该结点用来存放首元结点的地址;③头指针是指向链表中第一个结点的指针,由于有头结点,则不管线性表是否为空,头指针均不为空。
3:
简述线性表的两种存储结构的主要优缺点及各自适用的场合。
答案
线性表的两种主要存储结构各有其优点和缺点,不能简单地说哪个好哪个差要根据其适用的场合使用。
顺序存储是按索引(隐含的)直接存取数据元素,方便灵活、效率髙、但插入、删除操将引起元素移动,降低了效率;链式存储采用动态分配,利用率髙,但需增设表示结点之间有序关系的指针域,存取数据元素不如顺序存储方便,但结点的插入。
删除操作十分简单顺序存储适用于线性表中元素数量基本稳定,且很少进行插入和删除,但要求以最快的速度存取线性表中的元素的情况。
而链式存储适用于频繁进行元素的动态插入或删除操作的场合。
二.单选题
1:
为了方便地在线性结构的数据中插入一个数据元素,则其数据结构宜采用_______方式。
(A)顺序存储(B)链式存储(C)索引存储(D)散列存储
答案
B
2:
在双向循环链表中,在p指针所指向的结点前插入一个指针q所指向的新结点其修改指针的操作是-------(双向链表的结点结构是llink,data,rlink)
(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=p;p—〉llink=q;p—〉llink=q;
答案
C
三:
填空题
1:
根据线性表的链式存储结构,每个结点所含指针的个数,链表分为_______和_______,而根据指针的链接方式,链表又可分为_______和_______
答案
单链表。
多重链表。
循环链表。
普通链表
2:
在顺序表中插入或删除一个元素,需要平均移动_______元素,具体移动的元素个数与_______有关。
答案
n\2。
插入或删除元素的位置
四.判断题
1:
链式存储相比顺序存储的优点是插入和删除操作的时间效率高,缺点是存储密度小,不能随机查找。
答案
是
五.问答题
1:
设顺序表va中的数据元素递增有序,试写一算法使x插入到顺序表的适当位置上以保证该表的有序。
答案
2:
假设有一个单向循环链表,其结点含有三个域:
pre,data和link,pre值为空指针。
试编写算法将此表改为双向链表。
答案
3:
试写出在无头结点的单链表的第i个元素之前插入一个元素的算法。
答案
当i<=0时,则出错,无法进行插入;当i=1时,则插入的结点为首元结点。
当i>n(n为链表中结点的个数)时,则出错,无法进行插入,当l
}
4:
设计实现在单链表中删除值相同的多余结点的算法。
答案
5:
设x和y是表示单链表的两个串,试写出一个算法,找出x中第1个不在y中出现的字符(假定每个结点只存放一个字符)。
答案
}
6:
试写出一个完整的算法,以实现单链表的建立、插入、删除、逆转、输出。
答案
第三章测试题
一.填空题
1:
若一个栈的输出序列是1,2,3,…,n,输出序列的第一个元素是n,则第i个输出元素是_______
答案
2:
设有一个空栈,栈顶指针为1000H(十六进制),现有一输入序列为1,2,3,4,5,经过PUSH,PUSH,,POP,PUSH,POP,PUSH,PUSH后,输出序列是_______,栈顶指针是_______
答案
2,3。
1003H
二.单选题
1:
向顺序栈中压入新元素时,习惯上应当_______
(A)先移动栈顶指针,再存入元素(B)先存入元素,再移动栈顶指针
(C)先后次序无关紧要(D)同时进行
答案
B
2:
对于单链表形式的队列,队空的条件是_______
(A)F=R=nil(B)F=R
(C)F≠nil且R=nil(D)R—F=1
答案
B
三.问答题
1:
试说明下述运算的结果。
(1)POP(PUSH(S,A));
(2)PUSH(S,POPCS));
(3)PUSH'(S,POP(PUSH(S,B)))
答案
(1)首先要实现运算PUSH(S,A),其结果是将元素A压入栈中。
若栈S满,出现上溢现象;否则把元素A压入栈顶,且元素个数加1。
然后做POP(S)运算,将栈顶元素弹出,且元素个数减1。
(2)首先做POP(S)运算。
若栈A为空,则做下溢处理;否则弹出栈顶元素。
然后再进行压入运算,将刚才弹出的元素压入栈中。
(3)在
(1)、
(2)的基础上,使栈S增加一个栈顶元素B。
2:
设一数列的顺序为1,2,3,4,5,6,通过栈操作,我们要得到顺序为3,2,5,6,4,1和1,5,4,6,2,3的输出序列,可能吗?
为什么?
答案
输出序列3,2,5,6,4,1是可能的,但输出序列1,5,4,6,2,3不可能,因为5在4,2,3之前出栈,那么5出栈时,栈内状态为5,4,3,2,所以其次序(根据先进后出的原则)只能是5,4,3,2,而不可能出现5,4,2,3想出2时,2却被3压在下面,2不能比3先出栈,所以不可能出现1,5,4,6,2,3这种序列。
3:
何为队列上溢现象?
何为假溢出现象?
解决它有哪些方法?
分别简述其工作原理。
答案
在队列的顺序存储结构中,设队头指针为front,队尾指针为rear,队的容量(存储空间的大小)为m。
当有元素要加入队列时,若rear==ni(初始时rear=0),则发生队列的上溢现象,该元素不能加入队列。
假溢出现象是队列中有空余的空间,但元素不能进队列,造成这种现象的原因是由于队列的操作方式所致。
队列的上溢有以下几种方法:
(1)建立一个足够大的存储空间,但这样做会造成空间利用率低。
(2)当出现假溢出时,可采用以下几种方法:
①采用平移元素的方法。
每当队列中加入一个元素时,队列中已有的元素向队头移动一个位置(当有空余空间时);
②每当删除一个队头元素时,则依次序移队中的元素,始终使front指针指向队列中的第一个位置;
③采用循环队列方式。
把队头队尾看成是一个首尾相连的循环队列,虽然物理上队尾在队首之前,但逻辑上队首仍然在前,作插入和删除时仍按“先进先出”原则。
4:
在用一维数组sequ[0:
:
m—1]存储循环队列的元素时,怎样设置一个标志tag来区分尾指针(rear)和头指针(front)相等时队列的状态是“空”还是“满”?
答案
设标志tag初始值为“0”,如果由于元素入队列使得rear-front时,则置tag为“1”;反之,如果由于元素出队列使得rear=front时,则置tag为“0”。
当下一次进行入队列或出队列操作时,若有rear=front成立,则可由标志位tag的值来区别队列当前的状态是“满”还是“空”,即可决定其操作能否进行。
四.判断题
1:
线性表采用顺序存储表示时,必须占用一片连续的存储单元,判断该说法的正误。
答案
是
五.问答题
1:
用n个单元的一维数组构成一个循环队列,如何由首指针front和尾指针rear计算队列中现有元素的个数。
答案
2:
两个栈SI和S2都采用顺序表示,并且共享一个存储区,V[1:
:
n]。
为尽量利用空间,减少溢出的可能性,现采用栈顶相对,迎面增长的方式存储。
试设计公用栈的操作算法。
答案
3:
假设以带头结点的循环链表表示队列;并且只设—个指针指向队尾结点,但不设头指针。
试设计相应的置队列空,入队列和出队列的算法。
答案
}
4:
试写一个判别表达式中开.闭括号是否配对出现的算法。
答案
5:
假设以数组sequ[0:
:
m—1]存放循环队列的元素,同时设变量rear和quelen分别指示循环队列中队尾元素的位置和内含元素的个数。
试写出此循环队列的队满条件,并设计相应的入队列和出队列的算法。
答案
6:
设计算法以实现顺序栈的建立.入栈.出找.清空栈.查看.显示等基本操作。
答案
7:
(选做)设有一个双端队列,元素进入该队列时的顺序为1,2,3,4。
分别求出满足以下条件的输出序列:
(1)能由输入受限双端队列得到,但不能由输出受限双端队列得到的输出序列;
(2)能由输出受限双端队列得到,但不能由输入受限双端队列得到的输出序列;
(3)既不能由输入受限双端队列得到,又不能由输出受限双端队列得到的输出序列。
答案
第四章测试题
一.单选题
1:
若串S=’syntax’,其子串的数目是_______
(A)6(B)21(C)22(D)7
答案
C
二.问答题
1:
空串和空格串有何区别?
字符串中的空格符有何意义?
空串在串处理中有何作用?
答案
2:
令s=’aaab’t=’abcaabbabcabaacbacba’。
分别求出它们的next函数值。
答案
第五章测试题
一.单选题
1:
有一个10阶的对称矩阵a,采用压缩存储方式:
以行序为主序,a11为第一个元素,其存储地址为1,每个元素占1个地址空间,则a85的地址为_______
(A)13(B)33(C)18(D)40
答案
B
2:
一个n*n的对称矩阵,如果以行或列为主序存入内存,则其容量为_______
(A)n*n(B)n*(n+l)/2(C)(n+1)*(n+1)/2(D)(n-1)*n/2
答案
B
3:
二维数组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]
答案
B
4:
知广义表ls=(a(b,c,d),e),运用head和tail函数取出ls中原子b的运算是_______
(A)head(head(ls))(B)tail(head(Is))(C)head(head(tail(Is)))(D)head(tail(Is))
答案
C
5:
知广义表a=((a,b,c),(d,e,f)),从a中取出原子e的运算是_______
(A)(B)(C)(D)
答案
D
6:
广义表运算式tail[((a,b),(c,d))]的结果为_______
(A)c,d(B)(c,d)(C)((c,d))(D)d,c
答案
C
二.填空题
1:
一个广义表为(a,(a,b),d,e,((i,j),k))则该广义表的长度为_______,深度为_______。
答案
5。
3
三.问答题
1:
数组b[1..10,-2..6,2..8]以行优先的顺序存储,设第一个元素的首址是100,每个元素的长度为3。
试求元素b[5,0,7]的存储首址。
答案
由三维数组中的数据元素存储位置的计算公式(以行为主序)可得:
Loc(i,j,k)=loc(cl,c2,c3)+[(i—cl)(d2—c2+l)(d3—c3+l)]+(j-c2)(d3-c3+l)+(k—c3)]*1=100+(4*9*7+2*7+5)*3=913
2:
二维数组a[10,20]采用以列为主的顺序分配方法存于内存中,若每个元素占一个内存单元,a[1,1]所在的地址为200,则a[6,12]的地址是多少?
答案
以列为主序的非压缩存储地址公式为:
loc[aj,j]=b+[(j-l)m+(i-1)]*1,其中b为基地址,m为总的行数,1为每个元素所占存储单元数,本题目中b=loc[al,1]=200,m=10,1=1
所以:
loc[a(6,12)]=200+[(12-1)10+(6-1)]1=200+110+5=315
3:
(选做)在n*n(n>=3)的稀疏矩阵a中,只有下标满足:
l
若这些非零元素按行优先的顺序存入首地址为first的一个连续的存储空间,试写出任一非零a[I,j]的存储地址公式。
答案
根据题意可知这个矩阵的第一行和第n行的元素均为零。
对满足2<=i<=n-1的各行,除Ai,n-1,ai,n-1+1,ai,n-i+2三个元素外;其它元素均为零。
如果按行优先顺序存放这些非零元素,可得如下序列:
把它们顺序存放在以first为首地址的一个连续的存储空间中,前(i-l)行共有非零元素3*(i—2)个,在非零的ai,j前,本行还有非零元素的个数为j-(n-i)个,若第一个非零元素a2,n-2的存储地址为loc(a2,n-z),则非零元素ai,j的地址可用下式求出:
loc(ai,j)=loc(a2,n-2)+3*(i-2)+(i+j-n)
其中2<=i<=n-1,n<=i+j<=n+2
即loc(ai,j)=first+3*(i-2)+(i+j-n)
4:
设有n*n的三对角矩阵(aI,j)将其三条对角线上的元素逐行地存于数组b(1:
3*n-2)中,使得b[k]=aI,j,求:
(1)用i,j表示k的下标变换公式。
(2)用k表示i,j的下标变换公式。
答案
(1)对于三对角矩阵而言除了第一行和最后一行各有二个非零元素之外,其余各行均有三个非零元。
所以共有3n—2个非零元素。
主对角线左下角的对角线上的元素(即除第一行中的第一个元素之外的其余各行的第一个元素)的下标关系式:
5:
有三种存储稀疏矩阵昀方法:
(1)十字链表表示法;
(2)二维数组表示法;(3)三元组表示法。
现有一n*n稀疏矩阵,其非零元素个数为P,假设在上述三种表示法中,每个域(值和指针)都占有四个字节的空间,而且头结点和非头结点有相同的结构,请给出三种表示法表示该矩阵各自所需的空间数(以字节为单位)。
答案
6:
—个n*n的对称矩阵,如臬以行或列为主序存入内存,则其容量为多少?
答案
N(n+1)\2
7:
用三元组表示下面稀疏矩阵的转置矩阵。
01000
20003
00400
00050:
答案
四.问答题
1:
假定数组a[1:
:
n]的n(n>l)个元素中有多个零元素。
试写出一个算法,将a中所有非零元素依次移到a的前端a[1:
:
i](l<=i<=n)中。
答案
2:
(选做)试设计将数组a[1:
:
n]中所有奇数移到所有偶数之前的算法。
要求不另外增加存储空间,且时间复杂度为O(n)。
答案
第六章测试题
一.单选题
1:
深度为5的二叉树至多有结点数为______
(A)16(B)30(C)31(D)32
答案
C
2:
线索二叉树是一种_______结构。
(A)逻辑(B)逻辑和存储(C)物理(D)线性
答案
C
3:
如果T2是由有序树T转换而来的二叉树,那么T中结点的后序就是T2结点的_______
(A)先序(B)中序(C)后序(D)层序
答案
B
4:
中序遍历二叉排序树的结点是否就可以得到排好序的结点序列?
_______
(A)可以(B)不可以(C)有时可以(D)有时不可能
答案
A
5:
具有65个结点的完全二叉树的高度为_______(根的层次号为0)
(A)8(B)7(C)6(D)5
答案
C
6:
设F是一个森林,B是由F转换得到的二叉树,F中有n个非叶结点,则B中右指针域为空的结点有_______个。
(A)n-1(B)n(C)n+1(D)n+2
答案
C
7:
用孩子兄弟链表表示一棵树,若要找到结点x的第5个孩子,只要先找到x的第一个孩子,然后_______
(A)从孩子域指针连续扫描5个结点即可
(B)从孩子域指针连续扫描4个结点即可
(C)从兄弟域指针连续扫描5个结点即可
(D)从兄弟域指针连续扫描4个结点即可
答案
D
8:
树形结构的特点是:
一个结点可以有_______
(A)多个直接前趋(B)多个直接后继(C)多个前趋(D)一个后继
答案
B
9:
树型结构最适合用来描述_______
(A)有序的数据元素(B)无序的数据元素
(C)数据元素之间的具有层次关系的数据(D)数据元素之间没有关系的数据
答案
C
10:
若二叉树中度为2的结点有15个,度为1的结点有10个该树有_______个结点。
(A)25(B)30(C)31(D)41
答案
D
11:
若二叉树中度为2的结点有15个,度为1的结点有:
10个,该树有_______个叶结点。
(A)25(B)30(C)31(D)16
答案
D
12:
若深度为6的完全二叉树的第6层有3个叶结点,则该二叉树一共有_______个结点。
(A)15(B)16(C)17(D)34
答案
D
13:
若某完全二叉树的深度为h,则该完全二叉树中至少有_______个结点。
(A)2h(B)2h-1(C)2h-1-1(D)2h-1+1
答案
B
14:
在非空二叉树的中序遍历序列中,二叉树的根结点的左边应该_______
(A)只有左子树上的所有结点(B)只有左子树上的部分结点
(C)只有右子树上的所有结点(D)只有右子树上的部分结点
答案
A
15:
对于任意非空二叉树,要设计出其后序遍历的非递归算法而不使用堆栈结构,最适合的方法是对该二叉树采用_______存储结构。
(A)三叉链表(B)二叉链表(C)顺序(D)索引
答案
A
16:
下面关于哈夫曼树的说法,不正确的是_______
(A)对应于1组权值构造出的哈夫曼树一般不是唯一的
(B)哈夫曼树具有最小带权路径长度
(C)哈夫曼树中没有度为1的结点
(D)哈夫曼树中除了度为1的结点外,还有度为2的结点和叶结点
答案
D
17:
已知二叉树的先序序列为ABDECF,中序序列为DBEAFC,则后序序列为_______
(A)DEBAFC(B)DEFBCA(C)DEBCFA(D)DEBFCA
答案
D
18:
下列陈述中正确的是_______
(A)二叉树是度为2的有序树
(B)二叉树中结点只有一个孩子时无左右之分
(C)二叉树中必有度为2的结点
(D)二叉树中最多只有两棵子树,并且有左右之分
答案
D
19:
能生成右图所示二叉排序树的关键字序列是_______
(A)45312(B)42531
(C)45213(D)42315
答案
A
20:
某二叉树的先序序列和后序序列正好相同,则该二叉树一定是_______的二叉树。
(A)空或只有一个结点(B)髙度等于其结点数
(C)任一结点无左孩子(D)任一结点无右孩子
答案
A
21:
一棵左右子树均不空的二叉树在先序线索化后,其空指针域数为_______
(A)0(B)1(C)2(D)不确定
答案
B
22:
二叉树在线索化后,仍不能有效求解的问题是_______
(A)先序线索二叉树中求先序后继
(B)中序线索二叉树中求中序后继
(C)中序线索二叉树中求中序前趋
(D)后序线索二叉树中求后序后继
答案
D
23:
有64个结点的完全二叉树的深度为_______(根的层次为1)。
(A)8(B)7(C)6(D)5
答案
B
24:
在有n个结点的二叉链表中,值为非空的链域的个数为_______
(A)n-1(B)2n-19(C)n+1(D)2n+l
答案
A
25:
下列编码中属前缀码的是_______
(A){1,01,000,001}(B){1,01,011,010}(C){0,10,110,11}(D){0,1,00,11}
答案
A
26:
在有n个结点的二叉链表中,值为非空的链域个数为_______
(A)n-1(B)2n-1(C)n+1(D)2n+l
答案
C
二.填空题
1:
含有n个叶子结点的完全二叉树的深度为____。
答案
2:
深度为K的完全二叉树至少有_______个结点,至多有_______个结点,具有n个结点的完全二叉树若按自上而下,自左到右次序给结点编号,则编号最小的叶结点的序号是______。
(说明:
由完全二叉树特点可知,其叶子结点只可能出现在最后—层和倒数第二层上,深度为K的完全二叉树最少拥有的结点数应为深度为K—1的满二叉树的结点数加1。
)
答案
3:
—棵有1001个结点的完全二叉树有_______个叶子结点?
_______个度为2的结点?
_______个度为0的结点?
答案
501。
500。
0
4:
在n个结点的线索二叉链表中,有_______个线索指针。
答案
n+1
5:
对有15个结点的完全二叉树按层编号,则编号为6的结点的右孩子编号为_______
答案
13
6:
在有n个叶子结点的哈夫曼树中,总结点数是_______
答案
2n-1
7:
一棵树T采用二叉链表存储,如果树T中某结点为叶子结点,