微机原理与接口7

1、济南铁道职业技术学院专升本辅导数据结构试题(模 G)第一部分 选择题 (共 20分)一、单项选择题 (本大题共 10小题，每小题 2分，共 20分)的括号内。错选、多选或未选均无分。1.线性链表中各链结点之间的地址 A.连续与否都可以 B.部分地址必须连续C.一定不连续 D.必须连续2.删除非空双向循环链表中由 q所指的链结点的过程是依次执行以下三个动作：rlink(llink(q)rlink(q),_,call RET(q)。 A.llink(q)q B.llink(rlink(q)qC.llink(rlink(q)llink(q) D.llink(q)rlink(q)3.在包含有 1000

2、个元素的线性表中实现如下四个操作，所需要的执行时间最长的是 A.线性表采用顺序存储结构，在第 10个元素后面插入一个新的元素B.线性表采用链式存储结构，在第 10个元素后面插入一个新的元素C.线性表采用顺序存储结构，删除第 990个元素D.线性表采用链式存储结构，删除 p指的链结点4.因此在初始为空的队列中插入元素 a,b,c,d以后，紧接着作了两次删除操作，此时的队尾元素是 A.a B.bC.c D.d5.若不考虑结点的数据信息的组合情况，具有 3个结点的二叉树共有_种形态。 A.2 B.3C.4 D.56.对任何一棵二叉树，若n0n1n2分别是度为 012的结点的个数，则n0= A.n1+

3、1 B.n1+n2C.n2+1 D.2n1+17.维数组中，即ABCDFEGH，该二叉树的中序遍历序列为 A.G,D,B,A,F,H,C,E B.G,B,D,A,F,H,C,EC.B,D,G,A,F,H,C,E D.B,G,D,A,F,H,C,E8. 在 初 始 为 空 的 散 列 表 中 依 次 插 入 关 键 字 序 列(MON,TUE,WED,THU,FRI,SAT,SUN)，散列函数为 H(k)=i MOD 7，其中，i为关键字 k的第一个字母在英文字母表中的序号，地址值域为 0:6 ，采用线性再散列法处理冲突。插入后的散列表应该如_ 所示。 A. 0 1 2 3 4 5 6THU T

4、UE WED FRI SUN SAT MONB. 0 1 2 3 4 5 6TUE THU WED FRI SUN SAT MONC. 0 1 2 3 4 5 6TUE THU WED FRI SAT SUN MOND. 0 1 2 3 4 5 6TUE THU WED SUN SAT FRI MON9.下面的序列中_是大顶堆积。 A.1,2,8,5,3,9,10,4 B.1,5,10,6,7,8,9,2C.9,8,7,6,4,8,2,1 D.9,8,7,6,5,4,3,110.在下述的排序方法中，不属于内排序方法的是是 A.插入排序法 B.选择排序法C.拓扑排序法 D.归并排序法第二部分 非

5、选择题 (共 80分)二、填空题 (本大题共 10小题，每空 2分，共 20分)请在每小题的空格上填上正确答案。错填、不填均无分。11.数据结构课程讨论的主要内容是数据的逻辑结构、存储结构和_。12.若频繁地对线性表进行插入与删除操作，该线性表应采用_存储结构。13.若链结点的构造为 data|next，那么，判断由list所指的单向循环链表中只有一个结点的条件是_ _。14.求串 T在主串 S中首次出现的位置的操作是_。15.完全二叉树、满二叉树、线索二叉树和二叉排序树这四个名词术语中，与数据的存储结构有关系的是_。16._。17.在序列(2,5,8,11,15,16,22,24,27,35

6、,50)中采用折半查找(二分查找)方法查找元素 24，需要进行_次元素之间的比较。18.若待散列的序列为(18,25,63,50,42,32,9)，散列函数为 H(key)=key MOD ，与 18发生冲突的元素有_个。19.每一趟排序时从排好序的元素中挑出一个值最小的元素与这些未排小序的元素的第一个元素交换位置，这种排序方法成为_排序法。20.排序过程中所进行的元素之间的比较次数与参加排序的序列的初始状态无关的排序方法是_排序法。三、简答题 (本大题共 2小题，共 15分)21.(7分) 堆栈和队列都是特殊线性表，其特殊性是什么？22.(8分) 在建散列表时，通常情况下，采用链地址法处理冲

7、突比采用开放地址法处理冲突的时间效率要高，为什么？四、问题求解题 (本大题共 2小题，每小题 10分，共 20分)23.折半查找过程可以利用一棵称之为“判定树”的二叉树来描述，请画出在长度为 13的表中进行折半查找对应的判定树。24.若对序列(49,38,27,13,97,76,50,65)采用泡排序法(按照值的大小从小到大)进行排序，请分别在下表中写出每一趟排序的结果。原 始 序 列 49 38 27 13 97 76 50 65第 1趟的结果第 2趟的结果第 3趟的结果第 4趟的结果五、算法填空题 (本大题共 2小题，共 25分)25.(10分)已知线性表 A与线性表 B的长度分别为 n与

8、 m，并且都采用顺序存储结构，下面的算法是在线性表A的第 i个位置插入线性表 B。约定：不考虑存储空间溢出问题。请在算法的空缺处填入适当内容，使之能够正常工作。procedure INSERT(A,n,B,m)for jn downto i doAAjend / 将 A中某些元素依次后移 m个位置 /for j1 to m doABjend / 从 A中第 i个位置开始依次插入 B中元素 /n / 修改插入以后 A的长度 /end26.(15分)已知不带头结点的非空线性链表的链结点的构造为 data|link，第一个链结点的指针为 list，下面的算法将链表中数据域最大的那个链结点移到链表最后面。请在算法的空缺处填入适当内容，使之能够正常工作。procedure REMOVE(list)p / p初始时指向链表第二个链结点 /qlistrlistwhiledoif (data(p)data(q) then srqp rp / 将 p指向下一个结点 /end / q指向值最大的那个链结点