云南财经大学信息学院文档格式.docx
《云南财经大学信息学院文档格式.docx》由会员分享，可在线阅读，更多相关《云南财经大学信息学院文档格式.docx（49页珍藏版）》请在冰点文库上搜索。
只有一棵
（2）有一棵或多棵（3）一定有多棵（4）可能不存在
13.将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为____
（1）______。
（1）98
（2）99（3）50（4）48
14.将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的右孩子编号为____2______。
15.将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的双亲编号为____2______。
（1）23
（2）24（3）25（4）无法确定
16.设计一个判别表达式中左右括号是否配对出现的算法，采用（B）数据结构最佳。
A．线性表的顺序存储结构B．栈C．队列D．线性表的链式存储结构
17.下列序列中，______
（1）______
是执行第一趟快速排序后得到的序列（排序的关键字类型是字符串）。
（1）[da,ax,eb,de,bb]ff[ha,gc]
（2）[cd,eb,ax,da]ff[ha,gc,bb]
（3）[gc,ax,eb,cd,bb]ff[da,ha]（4）[ax,bb,cd,da]ff[eb,gc,ha]
18.用n个键值构造一棵二叉排序树，最低高度为___（4）_________。
（1）n/2
（2）n1/2（3）NLOG2N
（4）[LOG2N]+1
19.折半查找要求查找表中各元素的关键字值必须是___1________排列。
递增或递减
（2）递增（3）递减（4）无序
20.对于关键字值序列（12，13，11，18，60，15，7，18，25，100），用筛选法建堆，必须从关键字值为_____（3）____的结点开始。
（1）100
（2）12（3）60（4）15
21.快速排序的记录移动次数（C）比较次数，其总执行时间为0（NLOG2N）
A．大于B．大于等于C．小于等于D．小于
22.3个结点可构成（D）个不同形态的二叉树。
A．2B．3C．4D．5
23.对有n个记录的有序表采用二分查找，其平均查找长度的量级为（A）
A．O（LOG2N）B．O（NLOG2N）C．O（N）D．O（N2）
24.对有n个记录的表按记录键值有序的顺序建立二叉排序树，在这种情况下，其平均查找长度的量级为（C）
25.设矩阵A[1..8,1..8]是一对称矩阵，若每个矩阵元素占3个单元，将其上三角部分按行序为主序存放在数组B中，B的首址为1000，则矩阵元素A[6，7]的地址为（B）
A．1031B．1093C．1096D．1032
26.链表适用于顺序查找，但在链表中进行（D）操作的效率比在顺序存储结构中进行同样操作的效率高。
A．顺序查找B．二分法查找C．快速查找D．插入
27.散列法中的冲突指的是（C）。
A．两个元素具有相同的序号B．两个元素的键值不同，而其它属性相同
C．不同键值的元素对应于相同的存储地址D．数据元素过多
28.如果以链表作为栈的存储结构，则退栈操作时（C）
A．必须判断栈是否满B．对栈不作任何判断C．必须判断栈是否空
D．判断栈元素的类型
29.设数组A[0..M]作为循环队列SQ的存储空间，front为队头指针，rear为对尾指针，则执行出队操作的语句为（D）
A．front=front+1B．front=（front+1）%m
C．rear=rear+1D．rear=（rear+1）%m
30.深度为6的二叉树至多有（D）个结点
A．64B．32C．31D．63
31.设高度为k的二叉树上只有度为0和2的结点，则此类二叉树中所含的结点数至少为（C）
A．K+1B．2KC．2K-1D．2K+1
32.堆的存储表示（A）
A．顺序存储B.静态链接存储C.动态链接存储D.不一定
33.若二叉树采用二叉链表存储结构，要交换其所有分支结点左右子树的位置，利用（A）遍历方法最合适。
A．前序B．中序C．后序D．按层次
34.利用逐点插入法建立序列（50，72，43，85，75，20，35，45，65，30）对应的二叉排序树以后，查找元素35要进行（A）元素间的比较。
A．4次B．5次C.7次D．10次
35.下面给出的四种排序法中（D）排序法是不稳定性排序法。
A．插入B．冒泡C．二路归并D．堆积
36.下面B方法可以判断出一个有向图中是否有环（回路）？
A.深度优先遍历B.拓朴排序C.求最短路径D.求关键路径
37..若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为（D）
A.顺序存储结构B.链式存储结构
C.索引存储结构D.散列存储结构
38.在长度为n的顺序表的第i（1≤i≤n+1）个位置上插入一个元素，元素的移动次数为（A）
A.n-i+1B.n-i
C.iD.i-1
39..对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为（C）
A.顺序表B.用头指针表示的单循环链表
C.用尾指针表示的单循环链表D.单链表
40..为查找某一特定单词在文本中出现的位置，可应用的串运算是（D）
A.插入B.删除C.串联接D.子串定位
41.已知函数Sub（s,i,j）的功能是返回串s中从第i个字符起长度为j的子串，函数Scopy（s,t）的功能为复制串t到s。
若字符串S=″SCIENCESTUDY″，则调用函数Scopy（P,Sub（S,1,7））后得到（A）
A.P=″SCIENCE″B.P=″STUDY″
C.S=″SCIENCE″D.S=″STUDY″
42.三维数组A[4][5][6]按行优先存储方法存储在内存中，若每个元素占2个存储单元，且数组中第一个元素的存储地址为120，则元素A[3][4][5]的存储地址为（B）
A.356B.358C.360D.362
43.如右图所示广义表是一种（C）
A.线性表B.纯表C.结点共享表D.递归表
44.下列陈述中正确的是（D）
A.二叉树是度为2的有序树
B.二叉树中结点只有一个孩子时无左右之分
C.二叉树中必有度为2的结点
D.二叉树中最多只有两棵子树，并且有左右之分
45.n个顶点的有向完全图中含有向边的数目最多为（D）
A.n-1B.nC.n（n-1）/2D.n（n-1）
46.已知一个有向图如右所示，则从顶点a出发进行深度优先偏历，不可能得到的DFS序列为（A）
A.adbefcB.adcefbC.adcbfeD.adefcb
47..在最好和最坏情况下的时间复杂度均为O（nlogn）且稳定的排序方法是（C）
A.快速排序B.堆排序C.归并排序D.基数排序
48.不可能生成右图所示二叉排序树的关键字序列是（A）
A.45312B.42531C.45213D.42315
49.ALV树是一种平衡的二叉排序树，树中任一结点的（B）
A.左、右子树的高度均相同B.左、右子树高度差的绝对值不超过1
C.左子树的高度均大于右子树的高度D.左子树的高度均小于右子树的高度
50.在VSAM文件的控制区间中，记录的存储方式为（）
A.无序顺序B.有序顺序
C.无序链接D.有序链接
二、判断题（判断下列各题是否正确，若正确在括号内打“√”，错误的打；
1．如果两个串含有相同的字符，则这两个串相等。
（N）
2．数组可以看成线性结构的一种推广，因此可以对它进行插入、删除等运算。
（N），
3．在索引顺序表上实现分块查找，在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每块元素个数有关。
（Y）
4．在顺序表中取出第i个元素所花费的时间与i成正比。
（N）
5．在栈满情况下不能作进栈运算，否则产生“上溢”。
6．二路归并排序的核心操作是将两个有序序列归并为一个有序序列，（Y）
7．对任意一个图，从它的某个顶点出发，进行一次深度优先或广度优先搜索，即可访问图的每个顶点。
8．二叉排序树或是一棵空二叉树，或是具有下列性质的二叉树；
若它的左子树非空，则根结点的值大于其左孩子的值；
若它的右子树非空，则根结点的值小于其右孩子的值。
9．在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的（N）。
10．一个有向图的邻接表和逆邻接表中表结点的个数一定相等（Y）
①（101，88，46，70，34，39，45，58，66，10）是堆（Y）；
②将一棵树转换成二叉树后，根结点没有左子树（N）；
③用二叉树的前序遍历和中序遍历可以导出树的后序遍历（Y）；
④即使对不含相同元素的同一输入序列进行两组不同的、合法的入栈和出栈组合操作，所得的输出序列也一定相同（N）；
⑤哈夫曼树是带权路径长度最短的二叉树，路径上权值较大的结点离很较近（Y）。
11、表示一个有1000个顶点、1000条边的有向图的邻接矩阵有1000000个矩阵元素，是否稀疏矩阵是
12.（N）串长度是指串中不同字符的个数。
13.（N）数组可以看成是线性结构的一种推广，因此可以对它进行插入、删除等运算。
14.（Y）在顺序表中取出第i个元素所花费的时间与i成正比。
15.（Y）在栈满的情况下不能作进栈的运算，否则产生“上溢”。
16.（Y二路归并排序的核心操作是将两个有序序列归并为一个有序序列。
17.（N）对任意一个图，从它的某个顶点出发进行一次深度优先或广度优先搜索遍历可访问到该图的每个顶点。
18.（Y）一个有向图的邻接表和逆邻接表中的结点个数一定相等。
19（Y）在索引顺序表上实现分块查找，在等概率查找情况下，其平均查找长度不仅与表的个数有关，而且与每一块中的元素个数有关。
12（N）叉排序树或者是一棵空树，或者是具有下列性质的二叉树：
21（N）执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的。
三、填空题
1.
在带有头结点的单链表L中，第一个元素结点的指针是___L->
next________。
2.
在双循环链表中，在指针p所指结点前插入指针s所指的结点，需执行下列语句：
s->
next=p;
s->
prior=p->
prior;
p->
prior=s;
_s->
prior->
next_______________=s;
3.
设s[1..maxsize]为一个顺序存储的栈，变量top指示栈顶位置，栈为空的条件是___top==0__________，栈为满的条件是________top==maxsize_____________。
4.
具有100个结点的完全二叉树的深度为______7__________________。
5.
有向图G用邻接矩阵A[1..n,1..n]存储，其第i行的所有元素之和等于顶点i的____出度_______________。
6．r指向单链表的最后一个结点，要在最后一个结点之后插入e所指的结点，需执行的三条语句是r->
next=s;
r=s；
r—>
next=NULL。
7在单链表中，指针p所指结点为最后一个结点的条件是p->
next==null
8设一个链栈的栈顶指针是ls，栈中结点格式为info;
link;
栈空的条件是ls==null。
如果栈不为空，则退栈操作为p=ls；
ls=ls->
link；
free（p）。
9已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树中有12个叶子结点。
10．图有三种常用的存储结构，即孩子链表法，孩子兄弟链表法和双亲表示法。
11．n个顶点的连通图的生成树有n-1条边。
12．一个有向图G中若有弧<
vi,vj>
、<
vj,vk>
和<
vi,vk>
，则在图G的拓扑序列中，顶点vi,vjvk的相对位置为i,j,k
13．设表中元素的初始状态是按键值递增的，分别用堆排序、快速排序、冒泡排序和归并排序方法对其进行排序（按递增顺序）：
冒泡最省时间，快速最费时间。
14。
下面是将键值为x的结点插入到二叉排序树中的算法，请在划线处填上适当的内容。
typedefstructpnode
}intkey；
structnode*left，*right；
}
voidsearchinsert（intx;
pnodet）
/*t为二叉排序树根结点的指针*/
{if（t==null）
{p=malloc（size）;
p->
key=x;
left=null;
right=null;
t=p;
}
else
if（x<
t->
key）searchinsert（x,t->
left）
elsesearchinsert（x,t->
right）
15．线性表的循环链表的主要优点是从表中任一结点出发都能访问到所有的结点。
而使用双向链表，可根据需要在前后两个方向上方便地进行查找。
16．在带有头结点的单链表L中，则需执行下列三条语句：
u=L->
next；
L—>
next=u->
next；
free（u）;
17．有一个长度为20的有序表采用二分查找方法进行查找，共有4个元素的查找长度为3。
18．采用冒泡排序对有n个记录的表A按键值递增排序；
若L的初始状态是按键值递增，则排序过程中记录的比较次数为n-1。
若A初始状态为递减排列，则记录的交换次数为n（n-1）/2
19.在无头结点的双链表中，指针p所指结点是第一结点的条件是p->
prior==null.
20．G为无向图，如果从q的某个顶点出发，进行一次广度优先搜索，即可访问图的每个顶点，则该图一定是连通图。
21．如果一个有向图中没有环，则该图的全部结点可以排成一个拓扑序列。
22．深度为8（根的层次号为1）的满二叉树有8个叶子结点。
23．将一棵有100个结点的完全二叉树按层编号，则编号为49的结Ⅸ，其双亲PARENT（X）
的编号为24。
24．设有一个链队，结点结构为data;
front为队头指针，rear为队尾指针，当执行入队操作时需执行下列语句：
malloc（p）;
data=x;
next=null;
rear->
rear=p;
25.在散列法中，元素个数越多，发生冲突的可能性越大。
26．在带有头结点的单链表L中，第一个元素结点的指针是L->
next。
27．在顺序文件中，存取第i个记录，必须先存取第I-1号元素。
28．设s[1..maxsize]为一个顺序存储的栈，变量top指示栈顶位置，栈为空的条件是top==0，栈为满的条件是top==maxsize
29．具有64个结点的完全二叉树的深度为7
30．有向图G用邻接矩阵A[1..N,1..N]存储，其第I列的所有元素之和等于顶点I的入度。
31．在双循环链表中，若要在指针P所指结点前插人指针S所指的结点，则需执行下列语句s->
32．对于下图所示二叉树；
按前序遍历所得到的结点序列A，B，D，E，H，C，F．
33．分别采用堆排序、快速排序、冒泡排序和归并排序算法对初始状态为递增序列的表按递增顺序排序，最省时间的是冒泡排序，最费时间的是快速算法
34.对于下面的二叉树，按中序遍历所得到的结点序列为_______________。
35.
对下图所示的网，执行prim算法可得到最小生成树，试在下表的空白处填上适当的内容，以说明该算法的执行过程。
顶点
1
3
4
U
V
（U，V）
代价
（2，1）
∞
（2，3）
（2，4）
2
{2}
{1，3，4}
{2，4}
{1，3}
（3，1）
{2，4，3}
{1}
{2，4，3，1}
36、设广义表L＝（（），（））则head（L）是（）；
tail（L）是（（））；
L的长度是2；
深度是2
37、在n个记录的有序顺序表中进行折半查找，最大的比较次数是logn。
在如图所示的链表中，若在指针p所指的结点之后插入数据域值相继为a和b的两个结点，则可用下列两个语句实现该操作，它们依次是_S->
NEXT->
NEXT=P->
NEXT_和_P->
NEXT=S__。
38．串S=″Iamaworker″的长度是_14_______。
假设一个10阶的下三角矩阵A按列优顺序压缩存储在一维数组C中，则C数组的大小应为__55____。
39．在n个结点的线索二叉链表中，有___n+1_个线索指针。
40．对关键字序列（52，80，63，44，48，91）进行一趟快速排序之后得到的结果为_48,44,52,63,80,91___。
二、应用题
1．已知二叉树的后跟序列和中根序列如下，构造出该二叉树。
后根序列：
ABCDEFG
中根序列：
ACBGEDF
2．有一组关键码序列{8，9，5，3，7，2，1}，分别采用冒泡排序、快速排序、直接选择排序、直接插入排序、二路归并排序方法由小到大进行排序，在下面的选项中请选择各种排序第一趟排序的结果。
冒泡排序：
E
快速排序：
A
直接选择排序：
B
直接插入排序：
C
二路归并：
F
A．{1，2，5，3，7，8，9}
B．{1，9，5，3，7，2，8}
C．{9，8，5，3，7，2，1}
D．{9，5，3，7，2，1，8}
E．{8，5，3，7，2，1，9}
F．{8，9，3，5，2，7，1}
3．设图G=（V，E），V={1，2，3，4，5，6}，E={<
1，2>
，<
1，3>
2，5>
3，6>
6，5>
5，4>
6，4>
}，请写出图G中顶点的所有拓扑序列。
4．设图G=（V，E），V={1，2，3，4，5，6}，E={<
}，请画出其邻接表，并说明每个顶点的入度和出度。
5．对如下所示的二叉树，画出其顺序存储结构。
6．已知图G的邻接表如图所示，画出图G的所有连通分量。
现有5个结点（A，B，C，D，E），它们的权值分别为{5，10，12，15，30}，在下面的选项中选择一个编号，说明这5个结点的哈夫曼编码。
（2）
（1）A：
1，B：
001，C：
010，D：
011，E：
000
（2）A：
000，B：
（3）A：
001，B：
011，C：
000，E：
（4）A：
1，C：
001
7．已知一表为{23，45，24，6，57，45，35}，按表中顺序依次插入初始为空的二叉排序树，要求画出建立的二叉排序树。
设有序序列30,18,3,61,14,49，请按该序列构成一棵二叉排序树，并求其查找成功时的平均查找长度。
答：
二叉排序树:
（3分）
平均查找长度=（1+2×
2+3×
2+4）*1/6=2.5
（2分）
8．对如下所示的交通网，顶点表示城市，边表示连接城市间的公路，边上的权表示修路的代价。
怎样选择能够沟通每个城市且总造价最省的n-1条公路，画出所有可能的方案。
9．设有n个元素的有序表为A，K为一个给定的值，填空完成二分查找算法：
binsrch（a,n,k）
inta[],k;
{intlow,hig,
升级会员 