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