重庆邮电大学2022年数据结构考研真题重庆邮电大学2022年数据结构考研真题一、选择题一、选择题1对于双向循环链表，每个结点有两个指针域next和prior，分别指向前驱和后继在p指针所指向的结点之后插入s指针所指结点的操作应为（）A.p-next=s;s-prior=p;p-next-prior=s;s-next=p-next;B.p-next=s;p-next-prior=s;s-prior=p;s-next=p-next;C.s-prior=p;s-next=p-next;p-next=s;p-next-prior=s;D.s-prior=p;s-next=p-next;p-next-prior=s;p-next=s;2由abc,3个结点可以构造出多少种不同的二叉树？（）A.2B.3C.4D.53.设有数组Ai,j，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A5，8的存储首地址为（）A.BA+141B.BA+180C.BA+222D.BA+2254.一个栈的输入序列为123，则下列序列中不可能是栈的输出序列的是（）。
A.231B.321C.312D.1235.下述编码中哪一个不是前缀码（）A.（00，01，10，11）B.（0，1，00，11）C.（0，10，110，111）D.（1，01，000，001）6.当一棵有n个结点的二叉树按层次从上到下，同层次从左到右将数据存放在一维数组Al.n中时，数组中第i个结点的左孩子为（）A.A2i(2i=n)B.A2i+1(2i+1=n)C.Ai/2D.无法确定7.假设一个有n个顶点和e条弧的有向图用邻接表表示,则删除与某个顶点vi相关的所有弧的时间复杂度是（）A.O(n)B.O(e)C.O(n+e)D.O(n*e)8.串的长度是指（）A.串中所含不同字母的个数B串中所含字符的个数C.串中所含不同字符的个数D串中所含非空格字符的个数9循环队列存储在数组 A0.m中，则入队时的操作为（）A.rear=rear+1B.rear=(rear+1)mod(m-1)C.rear=(rear+1)mod mD.rear=(rear+1)mod(m+1)10关键路径是事件结点网络中（）A.从源点到汇点的最长路径B.从源点到汇点的最短路径C.最长回路D.D.最短回路二、填空题1.中缀算式（3+4X）-2Y/3对应的后缀算式为_。
2.在完全二叉树中，编号为i和j的两个结点处于同一层的条件是_3.构造n个结点的强连通图，至少有_条弧4.设有一个空栈，栈顶指针为1000H(十六进制)，现有输入序列为a，b，c，d，e经过PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后，输出序列是_，而栈顶指针值是H设 栈 为 顺 序栈，每个元素占4个字节5若串S1=ABCDEFG；S2=9898；S3=#；S4=012345，执行concat(replace(S1,substr(S1,length(S2),length(S3),S3),substr(S4,index(S2,8),length(S2)，其结果为_6若一组记录的排序码为（46，79，56，38，40，84），则利用堆排序的方法建立的初始堆为_7在有序表（12，24，36，48，60，72，84）中二分查找关键字72时所需进行的关键字比较次数为_8有向图的边集为：,d,c),，该图的一个拓扑排序为：_9当输入序列局部有序或元素个数较小时，在快速排序、选择排序、插入排序、归并排序、堆排序中，最佳的排序方法是_10假设两个队列共享一个循环向量空间（参见右图），其类型 Queue2 定义如下：typedef structDateType dataMaxSize；int front2,rear2；Queue2；对于 i=0 或 1，fronti和 reari分别为第 i 个队列的头指针和尾指针。
请对以下算法填空，实现第 i 个队列的入队操作int EnQueue(Queue2*Q,int i,DateType x)/若第 i 个队列不满，则元素 x 入队列，并返回 1；否则返回 0 if(i1)return 0；if(Qreari=Qfront )return 0；Qdata =x；Qreari=;return1；1 1高度为 8 的平衡二叉树的结点数至少有_个1 2文件由_组成；记录由_组成1 3对于一个具有 n 个结点的单链表，在已知的结点*p 后插入一个新结点的时间复杂度为_,在给定值为 x 的结点后插入一个新结点的时间复杂度为_1 4在 n 个记录的有序顺序表中进行折半查找，最大比较次数是:_1 5求从某源点到其余各顶点的 Dijkstra 算法在图的顶点数为 10，用邻接矩阵表示图时计算时间约为 10ms，则在图的顶点数为 40，计算时间约为_ms三、问答题三、问答题1一个线性表为 B=（12，23，45，57，20，03，78，31，15，36），设散列表为 HT0.12，散列函数为 H（key）=key%13 并用线性探查法解决冲突，请画出散列表，并计算等概率情况下查找成功的平均查找长度。
2已知二叉树的存储结构为二叉链表，阅读下面算法typedef struct node DateType data；Struct node*next；ListNode；typedef ListNode*LinkList；LinkList Leafhead=NULL；Void Inorder(BinTree T)LinkList s；If(T)Inorder(Tlchild)；If(!Tlchild)&(!Trchild)s=(ListNode*)malloc(sizeof(ListNode)；sdata=Tdata；snext=Leafhead；Leafhead=s；Inorder(Trchild);对于如下所示的二叉树E.画出执行上述算法后所建立的结构F.说明该算法的功能3.假设以 I 和 O 分别表示入栈和出栈操作栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由 I 和 O 组成的序列，称可以操作的序列为合法序列，否则称为非法序列下面所示的序列中哪些是合法的？A.IOIIOIOOB.IOOIOIIOC.IIIOIOIOD.IIIOOIOO通过对（1）的分析，写出一个算法，判定所给的操作序列是否合法。
假定被判定的操作序列已存入一维数组 char A 中,若操作序列合法，返回true，否则返回 false）4.已知一个连通图如下图所示，试给出图的邻接矩阵和邻接表存储示意图，若从顶点 v1 出发对该图进行遍历，分别给出一个按深度优先遍历和广度优先遍历的顶点序列.E.图的邻接矩阵F.邻接表存储示意图G.从 v1 开始的深度优先遍历的顶点序列H.分析在深度遍历过程中，分别使用邻接矩阵和邻接表存储的算法复杂度I.讨论在图遍历问题中，这两种存储方式的优劣5.一棵二叉树的先序序列为 ABCDGEF，中序序列为 CBDGAFE1)请画出该二叉树(2)将二叉树转换为相应的森林6.请阅读下列算法，回答问题sort（r,n）for(i=2;i=n;i+)x=r(i);r(0)=x;j=i-1;while(xr(j)r(j+1)=r(j);j=j-1;r(j+1)=x;1 6 这是什么类型的排序算法，该排序算法稳定吗？1 7 设置 r(0)的作用是什么？1 8 若将 while 语句中判断条件改为 x=r(j),该算法将会有什么变化？1 9 若将 while 语句中判断条件改为 x=r(j),该算法是否还能正确工作？四、程序设计题四、程序设计题设有大小不等的 n 个数据组,其数据总量为 m，顺序存放在空间区 D 内,每个数据占一个存储单元，数据组的首地址由数组S给出，（如下图所示），试编写将新数据 x 插入到第 i 个数据组的末尾且属于第 i 个数据组的算法，插入后，空间区 D 和数组 S 的相互关系仍保持正确。
快速排序算法中，如何选取一个界值（又称为轴元素），影响着快速排序的效率，而且界值也并不一定是被排序序列中的一个元素例如，我们可以用被排序序列中所有元素的平均值作为界值用 C 语言编写算法实现以平均值为界值的快速排序方法（注：待排序数据存储在数组 R 中,数组最小下标为 S，数组最大下标为 T）。