《数据结构与算法》模拟试卷五

《《数据结构与算法》模拟试卷五》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、《数据结构与算法》模拟试卷五一、名词解释（5*3=15分）数据结构完全二叉数AOE网队列拓扑排序二、填空题（1*16=16分）1.在一个长度为n的循环链表中，删除其元素值为x的结点的时间复杂度为______。2.已知指针p指向某单链表中的一个结点，则判别该结点有且仅有一个后继结点的条件是______。3.如果入栈序列是1，3，5，…，97，99，且出栈序列的第一个元素为99，则出栈序列中第30个元素为______。4.一种抽象数据类型包括______和______两个部分。5.线性表的链式存储方式中，每个结点包括两个域

2、，分别是______和______。6.在以HL为表头指针的带表头附加结点的单链表和循环单链表中，判断链表为空的条件分别为单链表中______和______。7.在一棵二叉树中，度为0的结点的个数是10，则度为2的结点个数是_________8.一个有n个结点的二叉树的深度最大为___________，最小为__________9.n个定点的连通图至少有_______条边。10.二分查找的存储结构仅限于________，且是__________11.在对一组记录(54，38，96，72，60，15，60，45，83)进

3、行直接插入排序时，当把第6个记录60插入到有序表时，为寻找插入位置需比较________次。三、选择题（1*10=10分）1.在一个不带头结点的单链表HL中，若要向表头插入一个由指针p指向的结点，则执行_______。A、HL=p;p->next=HL;B、p->next=HL;HL=p;C、p->next=HL;p=HL;D、p->next=HL->next;HL->nxet=p;2.在一个长度为n的顺序存储的线性表中，删除第i个元素（1≤i≤n+1）时，需要从前向后依次移动_______个元素。A、n-iB、n-i

4、+1C、n-i-1D、i3.在一个顺序队列中，队首指针指向队首元素的_______位置。A、当前B、后一个C、前一个D、后面4.计算递归函数如不用递归过程通常借助的数据结构是____。A、线性表B、双向队列C、树D、栈5.如果T2是由有序树T转换来的二叉树，则T中结点的后序排列是T2结点的____。A、先序排列B、中序排列C、后序排列D、层序排列6.栈的插入和删除操作在_____进行。A栈顶B栈底C任意位置D指定位置1.由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为_____。A24B7

5、1C48D538.图的广度优先搜索类似于树的_____遍历。A．先根B．中根C.后根D．层次9.在单链表中插入一个结点，要修改_____个结点的指针域。A1B2C3D410.二叉树有_____种基本形态。A2B3C4D5四、计算和应用题（共21分）1、假设用迪杰斯特拉(Dijkstra)算法求下列图中从顶点a到其余各顶点的最短路径，按求解过程依次写出各条最短路径及其长度。2、已知关键字序列在R[1..8]中的初始状态为1.R2.483.704.335.656.247.568.129.9210.111.212.313.4

6、14.515.616.717.8写出在将它调整为大根堆的过程中每一次筛选后R的状态。3、已知一组关键字为（19，14，23，1，68，20，27，83，99），试按哈希函数H(key)=keyMod7和链地址法处理冲突构造哈希表（同一链表中关键字按自小到大排列）。五、算法填空（2*9=18分）1.如果希望循环队列中的向量单元都能得到利用，则可设置一个标志域tag,每当尾指针和头指针值相同时，以tag的值为0或1来区分队列状态是“空”还是“满”。请对下列函数填空，使其分别实现与此结构相应的入队列和出队列的算法。intEn

7、Queue(CirQueue*Q,DataTypex){if((1))return0;Q->data[Q->rear]=x;Q->rear=(Q->rear+1)%MAXQSIZE(2)return1;}intDeQueue(CirQueue*Q,DataType*x){if((3))return0;*x=Q->data[Q->front];Q->front=(4);(5);return1;}(1)(2)(3)(4)(5)2.下列算法利用二分查找方法在有序表r中插入元素x，并保持表r的有序性，其中参数*n为表r的长度。

8、请在空缺处填入合适的内容，使其成为一个完整的算法。voidBinInsert(SeqListr,int*n,DataTypex){intlow=1,high=*n,mid,i;while(low<=high){mid=(1);if(x.key