数据结构试题2562

《数据结构试题2562》由会员分享，可在线阅读，更多相关《数据结构试题2562（7页珍藏版）》请在装配图网上搜索。

1、浙江省2002年1月高等教育自学考试数据结构导论试题课程代码：02142一、单项选择题（在每小题的四个备选答案中，选出一个正确答案，并将正确答案的序号填在 题干的括号内。每小题1分，共14分）1. 计算机算法指的是（）。A. 计算方法B. 排序方法C. 解决某一问题的有限运算序列D. 调度方法2. 在一个单链表中，若pf结点不是最后结点，在pf之后插入，1结点，则实行（）。A. s f .next:=p； p f .next=s;B. s f .next:=p f .next;p f .next:=s；C. s f .next:=p f .next;p:=s;D. p f .next:=s;s

2、 f .next=p;3. 某个向量第一元素的存储地址为100,每个元素的长度为2,则第五个元素的地址是（）。A. 110B.108C.100D.1204. 循环队列用数组A 0.m-1存放其元素值，已知其头尾指针分别是front和rear,则当前队列中的元素个数是（）。A. （rear-front+m） MOD mB. rear-front+1C. rear-front-1D. rear-front5. 栈和队列的共同特点是（）。A. 都是先进后出B. 都是先进先出C. 只允许在端点处插入和删除元素D. 没有共同点6. 深度为n的二叉树中所含叶子结点的个数最多为（）个。A.2n B.nCWD

3、.2n-17. 树最适合用来表示（）。A. 有序数据元素B. 无序数据元素C. 元素之间具有分支层次关系的数据D. 元素之间无联系的数据8. 下面的二叉树中，（）不是完全二叉树。A.一个图的邻接矩阵表示是唯一的B. 一个图的邻接表表示是不唯一的C. 一个图的生成树必为该图的极小连通子图D. 一个无环有向图的拓扑排序序列必唯一10. 设有6个结点的无向图，该图至少应有（）条边才能确保是一个连通图。A.5B.6C.7D.811. 对线性表进行二分查找时，要求线性表必须（）。A. 以顺序方式存储B. 以链接方式存储C. 以顺序方式存储，且结点按关键字有序排序D. 以链接方式存储，且结点按关键字有序排

4、序12. 直接存取文件的特点是（）。A. 记录按关键字排序B. 记录可以进行顺序存取C. 存取速度快，但占用较多的存储空间D. 记录不需要排序，存取效率高13. 文件存储的基本单位是（）。A.记录B.数据项C.属性D.关键字14. 一组记录的排序码为（47、78、61、33、39、80），则利用堆排序的方法建立的初始堆为（）。A.78、 47、 61、 33、 39、 80B.80、 78、 61、 33、 39、 47C.80、78、61、47、39、33D.80、61、78、39、47、33二、判断题（判断下列各小题，正确的在题后括号内打“ J”，错的打“X”。每小题2分， 共20分）1.

5、 算法和程序没有区别，所以在数据结构中二者是通用的。（）2. 在顺序表中无需为表示结点间的逻辑关系而增加存储空间。（）3. 单链表中的头结点就是单链表的第一个结点。（）4. 队列和栈都是运算受限的线性表。（）5. 任何一棵二叉树中至少有一个结点的度为2。（）6. 散列技术可用于表示并实现动态查找表。（）7. 对于同一组结点，由于建立二叉排序树时插入结点的先后次序不同，所构成的二叉排序树的形态及深度也不同，所以含有n个结点的二叉排序树不唯一。（）8. 在磁带上的顺序文件中插入新的记录时，必须复制整个文件。（）9. 插入排序是稳定的，而直接选择排序是不稳定的。（）10. 对于n个记录的集合进行冒泡

6、排序，所需要的平均时间是0（n）。（）三、填空题（每小题2分，共30分）1. 通常从四个方面评价算法的质量：、和。2. 字符串的逻辑结构为：。3. 设head为单链表的头结点，则判断单链表为空的条件是：。4. 在具有n个单元的循环队列中，队满时共有个元素。5. 矩阵压缩存储的基本思想是：的多个元素只分配一个存储空间，不分 配空间。6. 树的三种常用存储结构是：孩子链表表示法、和。7. 深度为K的完全二叉树至少有 个结点，至多有 个结点。8. 图的主要存储结构有两种，分别为：和。9. 二叉排序树上，结点的平衡因子定义为该结点 子树的高度减去该结点子树的高度。10. 散列技术既是一种 方式，又是一

7、种 方法。11. 在索引非顺序文件中，记录不按关键字顺序排列，因此对每个记录要建立一个索引项，这样的索引表称为 索引。12. 文件的修改包括：、和更新记录三种操作。13. 与磁带存储器相比，磁盘存储器的优点是存取速度快，既适应于 存取，又适应于 存取。14. 直接插入排序需要 个记录的辅助空间。15. 在插入和选择排序中，若初始数据基本正序，则选用；若初始数据基本反序， 则选用。四、应用题（每小题6分，共24分）1.已知串a= 1234+-*、b= 1+2-3*4，请用串的各种基本运算将串a转换为串b。规定： 运算中不能引入新的字符串，所有的字符串只能从串a中取得。2.给定二叉树的中序遍历结果

8、为abc，请画出能得到此中序遍历结果的二叉树的所有形态。3.请画出下面无向图的邻接矩阵和邻接表。4.已知序列15,18,60,41,6,32,83,75,95。请给出采用冒泡排序法对该序列作升序排序时的每一 趟的结果。五、设计题（每小题6分，共12分）1.如下图所示，设有两个栈s1和s2共亨同一数组存储空间stack 1.m，其中栈s1的栈底 设在stack 1处，而栈s2的栈底设在stackm处，请编写栈s1和s2的进栈操作push（i,x） 和退栈操作pop（i），其中i=1、2，分别表示栈s1和s2。要求：仅当整个空间stack 1.m 占满时才产生上溢。S1的栈底si的栈顶 S2的栈顶

9、艘的抻隔stack a元素序号12. 已知线性表的关键字集合87, 25, 310, 08, 27, 132, 68, 95, 187, 123, 70, 63, 47，已知散列函 数为H（k）=k MOD 13，采用拉链法处理冲突，设计出该开散列表的结构。浙江省2002年1月高等教育自学考试数据结构导论试题参考答案课程代码：02142一、单项选择题（每小题1分，共14分）1.C2.B3.B4.A5.C6.C7.C8.C9.D10.A11.C12.D13.A14.B二、判断题（每小题2分，共20分）1.x2. J3.x4. J5.x6. J 7. J 8. J 9. J 10.X三、填空题(每

10、小题2分，共30分)1. (1)正确性(2)易读性(3)强壮性(4)高效率。2. 正确答案为线性结构。答线性表也正确。3. 答案为：head f .next=NIL。4. n-15. (1)值相同(2)零元素。6. (1)孩子兄弟链表示法(2)双亲表示法。7. (1)2k-1(2)2k-1。8. (1)邻接矩阵(2)邻接表。9. (1)左(2)右。10. (1)存储(2)查找。11. 稠密12. (1)删除(2)插入。13. (1)顺序(2)随机。14.1 个15.(1)插入排序(2)选择排序。四、应用题(每小题6分，共24分)1.a1=CONCAT(SUBSTR(a,1,1),SUBSTR(

11、a,5,1);a2=CONCAT(SUBSTR(a,2,1),SUBSTR(a,6,1);a3=CONCAT(SUBSTR(a,3,1),SUBSTR(a,7,1);a4=SUBSTR(a,4,1);a5=CONCAT(a1,a2);a6=CONCAT(a3,a4);b=CONCAT(a6,a4)2.共有5种不同形态的二叉树，具体如下：3.邻接矩阵为：111101 1 1 0 11 1 1 1 11 0 1 1 10 1 1 1 1邻接表为：2 二一3 |$ I 丁3 245；-frnrnn厂 2 3 4 入4.结果如下:初始序列：15, 18, 60, 41, 6, 32, 83, 75,

12、95第一趟15,18,41, 6,32,60,75,83,95第二趟15,18, 6,32,41,60,75,83,95AA* +第二趟15, 6,18,32,41,60,75,83,95第四趟6,15,18,32,41,60,75,83,95第五趟：6,15,18,32,41,60,75,83,95在第五趟排序时已无元素交换，则排序结束。五、设计题(每小题6分，共12分)1.PROCEDURE push(i, x: integer)； (进栈操作 BEGINif(top1=top2-1)them 判断是否出现上溢writeln(发生上溢)；else if (i=1) then对栈s1进行进栈

13、操作BEGINtop1 :=top1+1;stack top1 :=x;ENDelse 对栈s2进行进栈操作BEGINtop2 :=top2-1;stack top2 :=x；ENDEND;PROCEDURE pop(i) 退栈操作 BEGINif (i=1) then 对栈s1进行退栈操作if (top1=0) then 判断栈s1是否下溢writeln(栈s1出现下溢)；else栈s1退栈BEGINpop:=stack top1;top1:=top1-1;ENDelse对栈s2进行退栈操作if(top2=m+1) then 判断栈s2是否下溢writeln(栈s2出现下溢)；else栈s2退栈BEGINpop:=stack top2;top2:=top2+1;ENDEND；根据共享栈stack 100 m的结构，设top1为栈s1的栈顶指针，top2为栈s2的栈顶指 针。则当top2=top1+1时出现上溢，而当top1=0时，栈s1出现下溢，当top2=m+1时， 栈s2出现下溢。2.散列地址指针