2007解放军理工大学指挥自动化学院考研专业课-数据结构与自动控制

2007解放军理工大学指挥自动化学院考研专业课——数据结构与自动控制.txt我的优点是：我很帅；但是我的缺点是：我帅的不明显。什么是幸福？幸福就是猫吃鱼，狗吃肉，奥特曼打小怪兽！令堂可是令尊表姐？我是胖人，不是粗人。本文由胥秀峰贡献pdf文档可能在WAP端浏览体验不佳。建议您优先选择TXT，或下载源文件到本机查看。机密★启用前中国人民解放军理工大学2007年全国硕士研究生入学统一考试试卷考试科目代码：806考试科目名称：数据结构与自动控制原理说明：所有答案必须按序号书写在考场提供的答题纸上，可不抄写原题，做在试卷和草稿纸上的一律无效。数据结构部分一、填空题（本题共10空，每空2分，满分20分）1．已知一棵树中含有父子关系的边是：(L,N)，(G,K)，(G,L)，(G,M)，(B,E)，(B,F)，(D,G)，(D,H)，(D,I)，(D,J)，(A,B)，(A,C)，(A,D)。（1）请画出这棵树的树形。（2）该树的高度是。2．含3个结点的二叉树的树形共有（1）种，其树形分别为（2）。其中，有（3）个是完全二叉树。3．已知二叉树的扩充先序序列是“ABC空空DE空FG空空空空空”。那么，它的中序序列是（1），后序序列是（2）。第1页（共10页）4．如果排序期间，序列的变化情况依次是：①25，84，21，47，15，27，68，35，20（原始排列）②20，15，21，25，47，27，68，35，84③15，20，21，25，35，27，47，68，84④15，20，21，25，27，35，47，68，84那么，所用的排序方法是排序。5．对于下面的加权图：A6B12C4958G20D12151610F13E（1）写出用Kruskal算法求最小生成树时，依次得到的树边（写出边的两个顶点和长度，形如AB6）。（2）画出所求出的最小生成树。二、单项选择题（本题共10空，每空2分，满分20分）1．设进栈序列是1，2，3，…，n，出栈序列为p1，p2，p3，…，pn。（1）若p1=n，则pi（1＜i≤n）为。A）iB）n-iC）n-i+1D）不确定第2页（共10页）（2）若pn=n，则pi（1≤i＜n）为。A）iB）n-iC）n-i+1D）不确定（3）若p1=3，则p2为。A）可能是2B）不可能是2C）可能是1D）必是1（4）若p3=1，则p1为。A）必是2B）可能是3C）必定是3D）不可能是3（5）若pn=1，则pi（1≤i＜n）为。A）有多种可能B）n-iC）iD）n-i+12．对有序数组a[12]进行二分查找时，查找长度最大的元素下标为。A）1，4，7，9，11B）0，3，6，9，11C）1，3，6，9，11D）0，4，8，9，103．在双向链表中，删除p所指结点（不考虑回收结点）不正确的操作是。A）p->Llink->Rlink=p->Rlink,p->Rlink->Llink=p->Llink;B）p->Llink=p->Rlink,p->Rlink=p->Llink;C）p=p->Llink,p->Rlink=p->Rlink->Rlink,p->Rlink->Llink=p;D）p=p->Rlink,p->Llink=p->Llink->Llink,p->Llink->Rlink=p;第3页（共10页）4．若k元正则树中共有m个非叶结点，则叶子数。A）≥(k-1)mB）≤kmC）=(k-1)m-1D）=(k-1)m+15．用Dijkstra算法求下图中，顶点A到其余各顶点的最短路径时，将按照的次序，依次求出A到它们的最短路径。A）BEDFCB）BEDCFC）BCEDFD）EDFCBA3B65E8F712C15104D6．以下序列不是堆。A）100，85，98，77，80，60，82，40，20，10，66B）100，98，85，82，80，77，66，60，40，20，10C）10，20，40，60，66，77，80，82，85，98，100D）100，85，40，77，80，60，66，98，82，10，20三、程序填空题（本题共10空，每空2分，满分20分）注：编号相同的空内应填写相同内容。第4页（共10页）1．函数merge用于将两个顺序存储的递增有序表合并成一个递增有序表。设数组a[M]，b[N]，c[M+N]分别用来存储原表和结果表，其中，M和N是整体量（常数）。voidmerge(inta[],intb[],intc[]){int（1）;while(（2）)if(a[i]a[i+1]){x=a[i];a[i]=a[i+1];a[i+1]=x;（6）;}if(（8）)return;flag=0;for(i=--（9）;i>=f;i--)if(a[i]>a[i+1]){x=a[i];a[i]=a[i+1];a[i+1]=x;（6）;}（10）++;}}四、阅读程序，回答下面的问题（满分15分）#include#definen8voidmain(){inti,j,k,x,a[n],b[n];printf("请输入%d个数据:\n",n);for(i=0;i<n;i++)scanf("%d",&a[i]);for(i=0;i<n;i++)b[i]=-1;k=1;第6页（共10页）while(k<n){i=k-1;while(i<n-1){j=i+k;if(a[i]<=a[j])b[i]=b[j],b[j]=i;//语句1elsex=a[i],a[i]=a[j],a[j]=x,b[j]=i;i=j+k;}k*=2;}j=b[n-1];i=b[j];while(i!=-1){if(a[i]>a[j])j=i;//语句2i=b[i];}printf("%d\n",a[j]);}（1）当输入数据为（6果。第7页（共10页）5843127）时，写出程序输出的结（2）写出该程序的功能，即程序在找（输出）什么样的数值。（3）如果将n的值改为任意的正整数（不限于形如2k的数），如何对程序进行修改，从而保证程序能完成上述功能？提示：只要加一条语句即可，请指出在哪条语句上面（或下面）加语句。（4）对任意的正整数n，程序为完成上述功能，至多进行多少次元素之间的比较，即“语句1”和“语句2”共执行多少次。（5）请指出程序使用什么样的数据结构，即数组b[n]所实现的数据结构。提示：可从下面给出的选项，选择其中你认为最准确的一个。A．比赛树模式B．判定树模式C．最优检索树模式D．普通链表模式（6）请指出该程序中所用到的算法是不是最优的，即是否存在完成上述功能的算法，所进行的元素比较次数少于该程序。简述为什么。第8页（共10页）自动控制原理部分一、（15分）RC网络如图1所示，其中u1为网络输入量，u2为网络输出量。（1）画出网络结构图；（2）求传递函数U2(s)/U1(s)。C2U1R1C1R2U2图1二、（15分）设复合控制系统如图2所示，图中Gn(s)为顺馈传递函数，Gc(s)=kts为测速电机及分压器的传递函数，1(s)为前向通路中环节的传递G函数，N(s)为可测量的干扰。若G1(s)=1/s2，试确定Gn(s)，Gc(s)和k，使系统输出量完全不受干扰n(t)的影响，且单位阶跃响应的超调量等于25%，峰值时间为2s。图2GnR(S)E(S)C(S)N(S)kG1Gc最大的元素下标为。A）1，4，7，9，11B）0，3，6，9，11C）1，3，6，9，11D）0，4，8，9，103．在双向链表中，删除p所指结点（不考虑回收结点）不正确的操作是。A）p->Llink->Rlink=p->Rlink,p->Rlink->Llink=p->Llink;B）p->Llink=p->Rlink,p->Rlink=p->Llink;C）p=p->Llink,p->Rlink=p->Rlink->Rlink,p->Rlink->Llink=p;D）p=p->Rlink,p->Llink=p->Llink->Llink,p->Llink->Rlink=p;第3页（共10页）4．若k元正则树中共有m个非叶结点，则叶子数。A）≥(k-1)mB）≤kmC）=(k-1)m-1D）=(k-1)m+15．用Dijkstra算法求下图中，顶点A到其余各顶点的最短路径时，将按照的次序，依次求出A到它们的最短路径。A）BEDFCB）BEDCFC）BCEDFD）EDFCBA3B65E8F712C15104D6．以下序列不是堆。A）100，85，98，77，80，60，82，40，20，10，66B）100，98，85，82，80，77，66，60，40，20，10C）10，20，40，60，66，77，80，82，85，98，100D）100，85，40，77，80，60，66，98，82，10，20三、程序填空题（本题共10空，每空2分，满分20分）注：编号相同的空内应填写相同内容。第4页（共10页）1．函数merge用于将两个顺序存储的递增有序表合并成一个递增有序表。设数组a[M]，b[N]，c[M+N]分别用来存储原表和结果表，其中，M和N是整体量（常数）。voidmerge(inta[],intb[],intc[]){int（1）;while(（2）)if(a[i]a[i+1]){x=a[i];a[i]=a[i+1];a[i+1]=x;（6）;}if(（8）)return;flag=0;for(i=--（9）;i>=f;i--)if(a[i]>a[i+1]){x=a[i];a[i]=a[i+1];a[i+1]=x;（6）;}（10）++;}}四、阅读程序，回答下面的问题（满分15分）#include#definen8voidmain(){inti,j,k,x,a[n],b[n];printf("请输入%d个数据:\n",n);for(i=0;i<n;i++)scanf("%d",&a[i]);for(i=0;i<n;i++)b[i]=-1;k=1;第6页（共10页）while(k<n){i=k-1;while(i<n-1){j=i+k;if(a[i]<=a[j])b[i]=b[j],b[j]=i;//语句1elsex=a[i],a[i]=a[j],a[j]=x,b[j]=i;i=j+k;}k*=2;}j=b[n-1];i=b[j];while(i!=-1){if(a[i]>a[j])j=i;//语句2i=b[i];}printf("%d\n",a[j]);}（1）当输入数据为（6果。第7页（共10页）5843127）时，写出程序输出的结（2）写出该程序的功能，即程序在找（输出）什么样的数值。（3）如果将n的值改为任意的正整数（不限于形如2k的数），如何对程序进行修改，从而保证程序能完成上述功能？提示：只要加一条语句即可，请指出在哪条语句上面（或下面）加语句。（4）对任意的正整数n，程序为完成上述功能，至多进行多少次元素之间的比较，即“语句1”和“语句2”共执行多少次。（5）请指出程序使用什么样的数据结构，即数组b[n]所实现的数据结构。提示：可从下面给出的选项，选择其中你认为最准确的一个。A．比赛树模式B．判定树模式C．最优检索树模式D．普通链表模式（6）请指出该程序中所用到的算法是不是最优的，即是否存在完成上述功能的算法，所进行的元素比较次数少于该程序。简述为什么。第8页（共10页）自动控制原理部分一、（15分）RC网络如图1所示，其中u1为网络输入量，u2为网络输出量。（1）画出网络结构图；（2）求传递函数U2(s)/U1(s)。C2U1R1C1R2U2图1二、（15分）设复合控制系统如图2所示，图中Gn(s)为