数据结构期末考试b卷.doc

《数据结构期末考试b卷.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、专业________________学号__________________姓名__________________班级____________________密封线北京电子科技学院2018～2018学年第二学期0952~0953班数据结构期末考试试卷<闭卷）

2、顺序表B．单链表C．双向链表D．单项循环链表3．在含有n个元素的顺序表中，删除一个元素所需移动元素的平均次数为。A．nB．n/2C．(n+1>/2D．(n-1>/24．设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操作为。A．p=p->nextB．p->next=p->next->nextC．p=p->next->nextD．p->next=p5.方法是从未排序序列中挑选元素，并将其依次放入已排序序列中的一端。A．归并排序B．插入排序C．选择排序D．快速排序二、填空题<每小空2分，共20分）1．栈的特点是。2.设顺序循环队列Q[0：m-1]的队头指针和队

3、尾指针分别为front和rear，其中队头指针front指向当前队头元素的前一个位置，队尾指针rear指向当前队尾元素所在的位置，则出队列的语句为front=_______________。b5E2RGbCAP3.4/4已知一有向图的邻接表存储结构如下：从顶点1出发，DFS遍历的输出序列是__________，BFS遍历的输出序列是______________。p1EanqFDPw4.设一棵完全二叉树的顺序存储结构中存储数据元素为ABCDEF，则该二叉树的中序遍历序列为___________，后序遍历序列为___________。DXDiTa9E3d5.设有向图G的二

4、元组形式表示为G=，<2,4>，<4,5>，<1,3>，<3,2>，<3,5>}，则该图的一种拓扑排序序列为______________。RTCrpUDGiT6.将一棵有100个结点的完全二叉树从根开始，从上到下，从左到右依次对结点进行编号，根结点的编号为1，那么编号为49的结点其左孩子编号是_____，父亲结点编号是_____，该完全二叉树的深度是_______。5PCzVD7HxA三、简答题<每小题7分，共42分）1．设计单链表结构时，往往要附设一个头结点，请说明这样做的原因及带来的好处。2.请解释顺序队

5、列的假溢出现象，以及相应的解决办法。3.请写出顺序栈的数据结构定义以及出栈操作算法。假设栈顶指针指向栈顶元素的下一位置。4．设二叉排序树中的关键字由1~100内的整数构成，现要查找关键字为63的结点，则下述关键字序列可能是在二叉排序树上查找到的序列吗？为什么？jLBHrnAILg<1）12，25，71，68，33，34，37，63<2）95，22，91，24，94，25，635．设一组记录关键字序列为(45，80，48，40，22，78>，要求从小到大排列。<1）请分别给出第4趟简单选择排序和第4趟直接插入排序后的结果。<2）比较插入排序和选择排序的不同点。xHAQX

6、74J0X6．地址空间为0~14的哈希表中，对关键字序列=ëi/2û,其中，i为关键字中第一个字母在字母表中的序号。用链地址法处理冲突。写出哈希表，并求出等概率情况下查找成功的平均查找长度。LDAYtRyKfE四、代码阅读题<每空2分，共12分）1．已知如下代码是用头插法建立带头结点的循环单链表，阅读代码并填写其中空白，使得算法功能得以实现。voidCreatList_L(LinkList&L,intn>{L=(LinkList>mallo

7、c(sizeof(LNode>>。L->next=①。for(i=n。i>0。--i>{p=(LinkList>malloc(sizeof(LNode>>。cin>>p->data。p->next=②。③；}}2.如下代码实现在有序顺序表ST中采用折半查找关键字kval，填空完成算法。intBin_Search(SSTableST,KeyTypekval>{intlow,high,mid。low=1。high=④。while(low<=high>{mid=⑤；if(kval==ST.elem[mid].key>returnmid。elseif(kva