数据结构与算法(B卷) 一、填空题（共10题，每题2分，共20分） 1、在计算机科学中，数据是指 2、算法的五个特性是： 3、一个栈的输入序列是12345，若在入栈的过程中允许出栈，则栈的输出序列43512可能实 现吗？ ;12345的输出呢？ 4、已知一棵二叉树的叶子数为20,10个结点有一个右孩子，15个结点有一个右孩子，该二 叉树的总结点数为。 5、一棵深度为k的二叉树至多有」 个结点。 6、图的遍历方式有 和 两种。 7、对于给定的n个元素，可以构造出的逻辑结构有」 8、设数组A[1-60,1-70]的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序 存储，则元素a[32,58]的存储地址为 9、广义表()和广义表()的区别是：（)为.长度为；()长度为，表头 为.表尾为 10、进栈时需将S->top加1，退栈时需将S->top减1。因此，S->top=-1表示 _,S->top=stacksize--l表示 二、选择题（共10题，每题2分，共20分） 1、线性表的链接实现有利于()运算。 A,插入操作B,读取操作C,查找操作 D,定位操作 2、快速排序法在()情况下最不利于发挥其长处。 A,排序的数据量最大 B,被排序的数据基本有序 C,被排序的数据无序 D,被排序的数据很少 3、若用冒泡排序法对关键字(20,17,11,8,6,1}从小到大排序，则须交换的总次数为()。 A,3 B,6 C,12 D,15 4、广义表A满足head(A)=tail(A),则A为() A,() B,() C,(0,0) D,(0,0,0) 5、数组[059]用于存储一循环队列，当队列头指针front=47,尾指针rear=23时，队列中的数 据元素数目为() A,24 B,25 C,36 D,35
数据结构与算法（B 卷） 一、填空题（共 10 题，每题 2 分，共 20 分） 1、在计算机科学中，数据是指____________________________________________________。 2、算法的五个特性是：________、____________、____________、__________、________。 3、一个栈的输入序列是 12345,若在入栈的过程中允许出栈,则栈的输出序列 43512 可能实 现吗?______;12345 的输出呢?_________。 4、已知一棵二叉树的叶子数为 20,10 个结点有一个右孩子,15 个结点有一个右孩子，该二 叉树的总结点数为_____。 5、一棵深度为 k 的二叉树至多有____________个结点。 6、图的遍历方式有________________________和________________________两种。 7、对于给定的n个元素，可以构造出的逻辑结构有___________、___________、___________、 ___________。 8、设数组 A[1-60，1-70]的基地址为 2048,每个元素占 2 个存储单元,若以列序为主序顺序 存储,则元素 a[32,58]的存储地址为_________。 9、广义表( )和广义表(( ))的区别是：( )为____.长度为____; (( ))长度为_____, 表头 为_____.表尾为________。 10、进栈时需将 S–>top 加 1，退栈时需将 S–>top 减 1。因此，S–>top=-1 表示 ____________，S–>top =stacksize-1 表示____________。 二、选择题（共 10 题，每题 2 分，共 20 分） 1、线性表的链接实现有利于（ ）运算。 A，插入操作 B，读取操作 C，查找操作 D，定位操作 2、快速排序法在（ ）情况下最不利于发挥其长处。 A，排序的数据量最大 B，被排序的数据基本有序 C，被排序的数据无序 D，被排序的数据很少 3、若用冒泡排序法对关键字{20,17,11,8,6,1}从小到大排序,则须交换的总次数为( )。 A，3 B，6 C，12 D，15 4、广义表 A 满足 head(A)=tail(A)，则 A 为（ ） A，( ) B，(( )) C，((),()) D，((),(),()) 5、数组[0…59]用于存储一循环队列,当队列头指针 front=47,尾指针 rear=23 时,队列中的数 据元素数目为( ) A，24 B，25 C，36 D，35
6、判断一个队列Q为空的条件() A,Q→rear!=Q→front B,Q→rear=Q→front C,Q→rear=Q→front+1 D,Q→rear-Q→front+1=n 7、快速排序在最坏情况下的时，时间复杂度为()。 A,0(1og2n) B,0(nlogzn) C,0(n) D,0(n) 8、在带有头结点的单链表L中，要向表头插入一个由指针p指向的结点，则执行()。 A,p->next=HL->next;HL->next=p; B,p->next=HL;HL=p; C,p->next=HL:p=HL; D,HL=p;p->next=HL; 9、A0V网是一种()。 A,有向图 B,无向图 C,无向无环图 D,有向无环图 10、有n个结点的二叉树，用二叉链表作为存储结构，空指针域有多少个？ A,n B,n+1 C,n+2 D,n-1 三、简答题（共5题，每题5分，共25分） 1:以关键码序列(503,087,512,061,908,170,897,275,653,426)为例，手工执行 希尔排序算法，写出每一趟排序结束时的关键码状态。 2:假设一棵二叉树的遍历先序序列为EBADCFHGIKJ,中序序列为ABCDEFGHIJK,请画出该二叉 树。 3:请对下面的无向带权图，写出它的邻接矩阵，请写出按普里姆算法求其最小生成树的过程。 9 b d 3 6 4、使用哈希函数hashf(x)=xMOD11,把一个整数值转换成哈希表下标，现要把数据1,13， 12,34,38,33,27,22插入到哈希表中。写出使用线性探测再散列法构造出哈希表的过程。 5:设纪录的关键字(key)集合k={26,36,41,15,68,12,6,51,25},以k为权值集合， 构造一棵huffman树；依次取k中各值，构造一棵二叉排序树。 四、算法分析设计题（共3题，第1题15分，第2、3题各10分，共35分） 1、设顺序表L中的数据元素递增有序，删除表中所有值大于k1且小于k2的元素(k1<=k2)
6、判断一个队列 Q 为空的条件( ) A，Q→rear！= Q→front B，Q→rear==Q→front C，Q→rear== Q→front+1 D，Q→rear-Q→front+1==n 7、快速排序在最坏情况下的时，时间复杂度为（ ）。 A，O(log2n) B，O(nlog2n) C，0(n) D，0(n2 ) 8、在带有头结点的单链表 HL 中，要向表头插入一个由指针 p 指向的结点，则执行( )。 A，p->next=HL->next; HL->next=p; B，p->next=HL; HL=p; C，p->next=HL; p=HL; D，HL=p; p->next=HL; 9、AOV 网是一种（ ）。 A，有向图 B，无向图 C，无向无环图 D，有向无环图 10、有 n 个结点的二叉树，用二叉链表作为存储结构，空指针域有多少个？ A，n B，n+1 C，n+2 D，n-1 三 、简答题（共 5 题，每题 5 分，共 25 分） 1： 以关键码序列（503，087，512，061，908，170，897，275，653，426）为例，手工执行 希尔排序算法，写出每一趟排序结束时的关键码状态。 2：假设一棵二叉树的遍历先序序列为 EBADCFHGIKJ，中序序列为 ABCDEFGHIJK，请画出该二叉 树。 3：请对下面的无向带权图，写出它的邻接矩阵，请写出按普里姆算法求其最小生成树的过程。 4、使用哈希函数 hashf(x)=x MOD 11,把一个整数值转换成哈希表下标，现要把数据 1，13， 12，34，38，33，27，22 插入到哈希表中。写出使用线性探测再散列法构造出哈希表的过程。 5：设纪录的关键字（key）集合 k={26，36，41，15，68，12，6，51，25}，以 k 为权值集合， 构造一棵 huffman 树；依次取 k 中各值，构造一棵二叉排序树。 四、算法分析设计题（共 3 题，第 1 题 15 分，第 2、3 题各 10 分，共 35 分） 1、设顺序表 L 中的数据元素递增有序，删除表中所有值大于 k1 且小于 k2 的元素（k1<=k2）。 d b c e f g h a 4 3 5 5 5 5 4 9 7 3 6 2 5 6
要求：(1)对该算法进行功能注释：(2)填空完成该算法。 #define ListSize 100 Typedef struct Elemtype elem[ListSize]: int length: }SqList: Void sq_dele(Sqlist*L,ElemType k1,Elemtype k2) {i=0: while(i<L→length) if && Break: else i++: if(i<L→length) j=1; While( && j++; for( L→elem[k-j]=L→elem[k]: L→length=L→length-j: } 2、己知S为不带头结点的单链表的表头指针，链表中存储的都是整型数据，试设计一个满足 下列要求的算法。（可以考虑使用递归技术）。 (1)求链表中的最大整数： (2)求链表中的结点个数。 3、编写一个判断双向循环链表的结点值是否对称的算法。即结点值满足al=an,a2=an-l,·
要求：（1）对该算法进行功能注释；（2）填空完成该算法。 #define ListSize 100 Typedef struct { Elemtype elem[ListSize]； int length； }SqList； Void sq_dele(Sqlist*L,ElemType k1,Elemtype k2) { i=0； while (i<L→length) if (_____________&&______________) Break； else i++； if(i<L→length) { j=1； While(________________&&________________) j++； for(________；_________；____________；) { L→elem[k-j]=L→elem[k]； L→length=L→length-j； }}} 2、已知 S 为不带头结点的单链表的表头指针，链表中存储的都是整型数据，试设计一个满足 下列要求的算法。（可以考虑使用递归技术）。 （1）求链表中的最大整数； （2）求链表中的结点个数。 3、编写一个判断双向循环链表的结点值是否对称的算法。即结点值满足 a1=an，a2=an-1,…