《数据结构》试卷参考答案(A卷)
2010 —2011 年度第二学期计算机学院
一、单项选择题(从下列各题四个备选答案中选出一个正确答案,将其代号(A,B,C,D)
四、存储结构图(要求标明各结点的数据域、指针域、权值等，每小题6分，共12分)
1．如下图所示为二叉树排序树T的一种线索二叉树逻辑结构图，试画出插入结点48后的线索二叉树的物理存储结构图。
答案：
2．试画出如下图所示无向网的邻接多重表存储结构图。
参考答案：
五、求解问题(每小题8分，共32分)
1．如下图所示为n 行2n-1列矩阵A[1..n ，1..2n-1]，现以行为主序进行压缩存储到
一维数组SA[1…m]中。（1）试问m 值是什么？（2）假定非零元素A[i ，j]保存在SA[k]中，试写出由下标(i ，j)到k 的转换公式。
1,n 2,n-12,n 2,n+1i,n-i+1i,n i,n+i-10 0 0 .... 0 a 0 .... 00 0 0 .... a a a .... 0 ....0 0 ... a ... a ... a ... 0 n,1 n,2
n,n n,2n-1 ....a a .... a .... a ?? ? ? ? ? ? ? ? ??? 答案：（1）m=n 2
（2）k=(i-1) 2+i+j-n (当 |j-n| 2. 如下图所示为有序表（10，15，21，33，44，60，67，68，70，80）的判定树，试问该判定树是否正确？如果正确，说明理由，错误则指出错误处并给出正确结果。 答案： 5 82 963 110 74 注：没按序号作为结点值扣1分 3．试用元素序列(63、72、88、68、66、38、43),生成平衡二叉排序树T,(1)按步骤画出该平衡二叉排序树T,(2)写出平衡二叉排序树T 的中序遍历序列,(3)假定每个元素的查找概率相等,计算查找成功时的平均查找长度。 答案： （1）66 7243 88686338 （2）38，43，63，66，68，72，88 （3）ASL=（1+2*2+3*4）/7=17/7 4．已知图的邻接表法存储结构如下，从顶点A出发求图的深度遍历的结果。 答案：ABDECF 六、证明题(每小题5分，共10分) 1，证明在哈夫曼树种最小权值所对应的叶结点的层数正好是哈夫曼树的高度。略 2．证明有n个结点的完全二叉树的高度为?log2(n+1)?。 略 七、编程题(6分) 1．已知大小为N的数组A[N]、B[N]分别存放着有N个结点的某二叉树的先根和中根遍历序列，试编写函数CreateBiTree构造该二叉树。相关说明如下： 参考答案： bitTree CreateBiTree(ElemType X[]，ElemType Y[N]，int n) { int i; if (!n) return NULL; T=(BitTree)malloc(sizeof(NODE)); T->data=X[0]; for(i=0; Y[i]==X[0] ;i++); T->lchild= CreateBiTree(&X[1],Y,i); T->rchild= CreateBiTree(&X[i+1],&Y[i+1],n-i-1); Return T; } 八、阅读并改进算法(每小题4分，共8分) （1）. 阅读上面的算法程序，叙述算法的功能，并给出算法的时间与空间复杂度。 答案：输入一个数k，在有序序列中找2个数，使其和等于k T(n)= O(n) S(n)= O(n) （2）改写算法，使改进算法的时间和空间效率尽可能提高。 参考答案： #include #define MAXSIZE 13 main(){ int a[MAXSIZE]= ={1,4,5,6, 8,10,11,13,15,20 }; int k,i,j; scanf("%d",&k); i=0,j=MAXSIZE-1; while(i if(a[i]+a[j]==k) break; if(a[i]+a[j]>k j--; else i++; } if(i else printf("no solution!\n"); } 数据结构课程设计哈夫曼编码和译码的实现 #include for(i = 1;i<=n;i++) { getchar(); system("CLS"); printf("\n\t\t====================================\n"); printf("\t\t\t第%d个元素的=>\n\t\t\t\t结点的值:",i); scanf("%c",&ht[i].data); printf("\t\t\t\t节点权重："); scanf("%d",&ht[i].weight); printf("\n\t\t====================================\n"); } for(i = 1;i<= 2 * n - 1; i++) ht[i].parent = ht[i].lchild = ht[i].rchild = 0; for(i = n+1;i<= 2 * n - 1;i++)//产生新的Huffman节点 { min1 = min2 = 32767;//min1和min2开始赋最大值 p1=p2=1; for(k = 1;k<=i-1;k++)//在输入的节点中选取权值最小的值min1和min2 { if(ht[k].parent == 0) if(ht[k].weight < min1)//运用选择排序生成HUFFMAN树 { min2 = min1; p2 = p1; min1 = ht[k].weight; p1 = k; } else if(ht[k].weight < min2) { min2 =ht[k].weight; p2 = k; } } ht[p1].parent = i; ht[p2].parent = i; ht[i].weight = min1 + min2; ht[i].lchild = p1; ht[i].rchild = p2; } printf("\n\n\n\t\t\t提示:哈夫曼树构建成功！\n\n\n\n"); system("PAUSE"); return n; } 2010-2011 学年第2 学期课号BT11107 课程名称数据结构（B卷; 闭卷）适用班级（或年级、专业）08011103、104、105 一、填空题（每小题2分，共20分） (1) 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的 （）和运算等的学科。 (2)在一个长度为n的顺序表中第i个元素（1 ≤i ≤n）之前插入一个元素时，需向后 移动（）个元素。 (3）假设以S和X分别表示进栈和退栈操作，则对输入序列a，b，c，d，e进行一系列栈操作SSXSXSSXXX之后，得到的输出序列为（）。 （4）数据的逻辑结构在计算机存储器内的表示，称为数据的（）。 （5）在具有n个单元的循环队列中，队满时共有____个元素。 （6）二叉树有（）种基本形态。 （7）在具有n个结点的完全二叉树中，若结点i有左孩子，则结点i的左孩子编号为（）。（8）若用二叉树表示具有n个结点的二叉树，则有（）个空链域。 （9）深度为k（k>0）的二叉树，至多有（）个结点，第i层上之多有（）结点。 (10) 一个有n个顶点的无向图最多有____条边。 二、选择题（每小题2分，共20分） 1.研究数据结构就是研究（）。 (A) 数据的逻辑结构 (B) 数据的存储结构 (C) 数据的逻辑结构和存储结构 (D) 数据的逻辑结构、存储结构及其数据的运算 2.下列算法的时间复杂度是（） s=0; for (i=0;i 华中科技大学土木工程与力学学院 《结构力学》试卷 2003－2004学年度第一学期 姓名______________专业________________班级____________成绩______ 1、用位移法计算图示结构，EI 为常数。 （只需做到建立好位移法方程即可）。（15分） 2、用力矩分配法作图示对称结构的M 图。已知：40/q kN m =，各杆EI 相同。（15分） 3、已知图示结构B 点转角64 11B EI θ= ，各杆的EI 为常数，作M 图，8P kN =，12/q kN m =。 （13分） q 4、图示结构，用矩阵位移法计算时（先处理法，计轴向变形），请标注编码，并给出各单元的定位向量。（10分） 5、请求出图示结构等效结点荷载列阵。（15分） q 6、请求出图示结构C 点的转角。（12分） A B EI C φφ 7、求两端固定梁的极限荷载u P F ，已知梁截面的极限弯矩87.1, 4.37u M kN m L m =?=。（12分） A B 8、请确定位移法计算该题时的未知量数，并画出基本体系。（8分） 华中科技大学土木工程与力学学院 《结构力学》试卷 2004－2005学年度第一学期 姓名______________专业________________班级____________成绩______ 1、用位移法计算图示结构，并绘弯矩图。（25分） q q a a 2、请用力矩分配法作图示结构的弯矩图，并求D 点竖向位移。（25分） 3、指出图示结构位移法的未知量个数（最少），并在图上标出。（每题5分，共10分） 1） 华中科技大学硕士研究生入学考试《数据结构与算法分析》考试大纲 科目代码（887） 第一部分考试说明 一、考试性质 《数据结构与算法分析》是报考我校软件学院硕士生选考的专业基础课之一。考试对象为报考我校硕士研究生入学考试的准考考生。 二、考试形式与试卷结构 （一）答卷方式：闭卷，笔试 （二）答题时间：180分钟 （三）考试题型及比例： 术语解释15% 选择、填空 30% 论述、简答30% 设计及应用 25% 第二部分考查要点 （一）基本概念和术语 1．数据结构的概念 2．抽象数据结构类型的表示与实现 3．算法，算法设计的要求，算法效率的度量，存储空间要求。 （二）线形表 1．线形表的类型定义 2．线形表的顺序表示和实现 3．线形表的链式表示和实现 （三）栈和队列 1．栈的定义，表示和实现 2．栈的应用：数制转换，括号匹配，行编辑，迷宫求解，表达式求值 3．栈与递归实现 4．队列。 （四）串 1．串的定义，表示和实现 2．串的模式匹配算法 （五）树和二叉树 1．树的定义和基本术语 2．二叉树，遍历二叉树和线索二叉树 3．树和森林：存储结构，与二叉树的转换，遍历 4．霍夫曼树和霍夫曼编码 5．回溯法与树的遍历 （六）查找 1．静态查找表 2．动态查找表 3．哈希表 （七）图 1．图的定义和术语 2．图的存储结构 3．图的遍历 4．图的连通性问题 5．拓扑排序与关键路径 6．最短路径 （八）内部排序 1．排序的概念 2．插入排序 3．快速排序 4．选择排序：简单选择，树形选择，堆排序 5．归并排序 6．基数排序 7．各种排序方法的比较 第三部分考试样题（略） 计算机专业基础综合（数据结构）模拟试卷1 (总分：72.00，做题时间：90分钟) 一、单项选择题(总题数：21，分数：42.00) 1.单项选择题1-40小题。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。（分数： 2.00）__________________________________________________________________________________________ 解析： 2.若某线性表中最常用的操作是在最后一个结点之后插入一个结点和删除第一个结点，则下面最节省运算时间的存储方式是( )。 （分数：2.00） A.单链表 B.带有头指针的单循环链表 C.双链表 D.带有尾指针的单循环链表√ 解析：解析：在链表中的最后一个结点之后插入一个结点要知道终端结点的地址，所以，单链表、带有头指针的单循环链表、双链表都不合适。考虑在带有尾指针的单循环链表中删除第一个结点，其时间性能是O(1)，所以答案是D。 3.已知两个长度分别为l和s的降序链表，若将它们合并为一个长度为l+s的升序链表，则最坏情况下的时间复杂度是( )。 （分数：2.00） A.O(l) B.O(ls) C.O(min(l，s)) D.O(max(l，s)) √ 解析：解析：在合并过程中，最坏的情况是两个链表中的元素依次进行比较，比较的次数最少是m和n中的最大值。 4.线性表中存放的主要是( )。 （分数：2.00） A.整型常量 B.字符 C.数据元素√ D.信息元素 解析：解析：线性表中主要存放的是数据元素，而数据元素可以是整型也可以是字符型，但对于一个线性表来说，所有的数据元素的类型必须相同。 5.下面的叙述中正确的是( )。 I．线性表在链式存储时，查找第i个元素的时间同i的值成正比Ⅱ．线性表在链式存储时，查找第i个元素的时间同i的值无关Ⅲ．线性表在顺序存储时，查找第i个元素的时间同i的值成正比 （分数：2.00） A.仅I √ B.仅Ⅱ C.仅Ⅲ D.I、Ⅱ、Ⅲ 解析：解析：在线性表链式存储结构中，查找第i个元素的时间与i的位置成正比。而在顺序存储结构中查找第i个元素的时间与i的位置无关。 6.对于某线性表来说，主要的操作是存取任一指定序号的元素和在最后进行插入运算，那么应该选择( )存储方式最节省时间。 （分数：2.00） A.顺序表√ 第一章绪论 1．掌握数据、数据库、数据库管理系统和数据库系统等四个概念2．了解数据管理技术的三个发展阶段 3．数据模型（理解、掌握） 概念、三要素，理解教材关于“三个世界”的描述； 有关“信息世界”的几个概念；（实体、属性、码、域、实体型、实体集、联系） 概念模型及其表示方法；（E-R图） 三大经典数据模型的基本数据结构、数据操作、数据约束、优缺点。4．数据库系统结构（理解、掌握） 数据库系统的三层模式和两级映象结构，基本机构特征、作用； 数据库系统的主从式、分布式、C/S方式等结构及其特征；（了解） 数据库系统的组成； DBMS的功能和组成； 5．数据库系统访问过程（了解） 6．数据库系统特点（理解、掌握） 数据结构化；数据共享性高、冗余度低、易于扩充；数据独立性高；数据由DBMS统一管理和控制。 第二章关系数据库（理解，实践） 1．关系基本概念（掌握） 2．关系模型（熟练掌握） 数据结构；实体完整性和参照完整性；用户自定义完整性 3．关系数据操纵语言（熟练掌握，实践） 关系代数，8种运算符（并、交、差、笛卡尔积、投影、选择、连接、除），其中5种基本运算符（并、差、笛卡尔积、投影、选择）。 第三章SQL语言（理解，实践） 1．SQL语言概述（理解） SQL体系结构和三级模式两层影射结构；SQL特点 SQL语言的基本功能 SQL语言中的几个动词 2．数据定义功能 数据库、表、索引的创建、修改和删除 3．数据查询功能 一般格式（与关系代数的等价性，理解） 简单查询 连接查询 嵌套查询（各种谓词的使用，相关和不相关嵌套查询） 4．数据更新功能 插入、删除、更新 5．视图 概念、定义、删除、视图更新的限制、作用 6．数据控制功能 授权和回收权限 2018计算机考研：计算机数据结构测试题(四) 2018考研，计算机专业课考试科目为：计算机组成原理、数据结构、操作系统以及计算机网络等，需要大家记忆的知识点有很多，但是不能死机硬背，还是要理解为主的，融会贯通才能把题做好，拿到高分，小编就为大家分享计算机数据结构测试题及参考答案，希望计算机考研的考生在复习之余能够认真做题，巩固知识。 计算机数据结构测试题(四) 一、选择题(30分) 1.设某无向图有n个顶点，则该无向图的邻接表中有( )个表头结点。 (A) 2n (B) n (C) n/2 (D) n(n-1) 2.设无向图G中有n个顶点，则该无向图的最小生成树上有( )条边。 (A) n (B) n-1 (C) 2n (D) 2n-1 3.设一组初始记录关键字序列为(60，80，55，40，42，85)，则以第一个关键字45为基准而得到的一趟快速排序结果是( )。 (A) 40，42，60，55，80，85 (B) 42，45，55，60，85，80 (C) 42，40，55，60，80，85 (D) 42，40，60，85，55，80 4.( )二叉排序树可以得到一个从小到大的有序序列。 (A) 先序遍历(B) 中序遍历(C) 后序遍历(D) 层次遍历 5.设按照从上到下、从左到右的顺序从1开始对完全二叉树进行顺序编号，则编号为i结点的左孩子结点的编号为( )。 (A) 2i+1 (B) 2i (C) i/2 (D) 2i-1 6.程序段s=i=0;do {i=i+1; s=s+i;}while(i<=n);的时间复杂度为( )。 (A) O(n) (B) O(nlog2n) (C) O(n2) (D) O(n3/2) 7.设带有头结点的单向循环链表的头指针变量为head，则其判空条件是( )。 (A) head==0 (B) head->next==0 (C) head->next==head (D) head!=0 8.设某棵二叉树的高度为10，则该二叉树上叶子结点最多有( )。 (A) 20 (B) 256 (C) 512 (D) 1024 9.设一组初始记录关键字序列为(13，18，24，35，47，50，62，83，90，115，134),则利用二分法查找关键字90需要比较的关键字个数为( )。 (A) 1 (B) 2 (C) 3 (D) 4 10.设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为( )。 (A) top=top+1; (B) top=top-1; (C) top->next=top; (D) top=top->next; 二、判断题(20分) 1.不论是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情况。( ) 2.当向二叉排序树中插入一个结点，则该结点一定成为叶子结点。( ) 3.设某堆中有n个结点，则在该堆中插入一个新结点的时间复杂度为O(log2n)。( ) 华中科技大学本科生课程考试试卷（A卷） 课程名称：计算机网络课程类别：专业课考试形式：闭卷 学生班级考试日期 2012.05 学生所在院系控制系 学号姓名任课教师 一、填空题（每题2分，共30分） 1、计算机网络的混合模型分为层，其中网络层的主要功能是。 2、居民区网络用户接入计算机网络的方式有多种，请给出至少2中接入方式、 。 3、物理层协议的四个重要特性分别是、、和。 4、TI标准可以同时传输路音频信号，传输的数据速率为Mb/s。 5、物理层常用的信道复用技术有多种，常用的四种分别为、、 和。 6、数据链路层成帧（帧同步）的主要方法有四种，分别是、、 和。 7、若待发送的数据比特序列为“110111011”，采用CRC编码技术对其进行抗干扰编码，生成多项式为1011，则抗干扰编码为。 8、一个电话话路的频带范围为900Hz-4000Hz，信道的信噪比为30分贝，根据香农公式，该信道上的最大传输速度为bps。 9、在TCP/IP环境下，ICMP协议允许主机或路由器提供差错或异常情况的报告，ICMP报文的类型可以分报文和报文。 10、某单位分配到一个IP地址，其网络号（Net-ID）为：213.15.74.0，根据该单位的具体情况，需要划分六个子网，则其子网掩码应为。 11、IEEE802标准将数据链路层划分为一个子层和一个子层。 12、互联网上自治系统内部常用的路由协议有和。 13、在HDLC协议中，数据比特串011111011111010装帧后实际发出去的比特串为。 14、IPV6的地址是位，其地址类型有三类，分别是、和。 15、滑动窗口协议中发送窗口中的编号代表。 2018年华中科技大学834计算机专业基础综合（数据结构、计算机网络）考研真题（回 忆版） 数据结构部分 一、选择题（共10道，一个2分，共20分） 1．数据结构的逻辑结构分类是哪两种？ 2．给定一颗完全二叉树的结点数，求其中的叶节点个数 3．一个有n个结点的图构成一个邻接矩阵几乘几的矩阵 4～10暂缺 二、简答题（共5道题，前四个15分，最后一个10分，今年没有编程题，也就是都是算法和推演，不用写代码，都是根据要求写结果和原理） 1．给了8个左右的数字的一个集合，比如{75，63，43…}，要求一次读取一个，输出成一个二叉排序树，写出结果，并且求等概率情况下的平均查找长度。 2．给了一个包含有ABCDEFGH这几个点的二叉树的先序和中序排列，要求画出原二叉树。 3．一个指令集合{I1，I2，I3…}，对应给出了每个指令对应的发生概率大小{0.03，0.03，0.15，0.15，0.3，0.4}（这个数字印象比较深基本差不多），让求出用此集合构成的哈夫曼树。求出他们的一个组织，并且求出每个指令的哈夫曼编码。 4．给出了一个由ABCDEFGHLM点组成的的无向带权图，让求出最小生成树（这里题干没有写用哪种算法）。 5．给定了一个树，转化成对应的二叉树，大概有8个点左右。 计算机网络部分 一、选择题（共10道，一个1分，共10分） 1．IPV4和IPV6的特征对比，选出一个错误的 2．TCP拥塞控制中慢开始算法的特征，选出一个错误的 3～10暂缺 二、填空题（共10道，一个1分，共10分） 1．IEEE802.11用的协议是_____ 2．CDMA2000采用的编码方式是_____ 3．移动IP的基本工作过程（给了其中3个步骤，填另一个） 4．信道划分的三种方式（给了其中2个，填另一个） 5～10暂缺 三、简答题（共7道，共40分） 1．主机A向主机B先后发两个报文，给出了每个报文的字节数，然后分别问了第一个先到的情况下和第二个报文先到的情况下各自的确认号，源，目的。 2．题目给了两个通信设备之间的RTT，L是要发送的信息的长度，S和R分别代表（忘了。），也是两问，分别求在4L/R＜S/R＜2L/R（第一个条件这里有个两个不等号隔开的三个地方有个地方是＋RTT的，记不清给到哪里了）和S/R＞4L/R两种情况下一端从开始发送信息开始到完全接收到并收到确认所用的总时间 3．左边给出一个路由表，有A到G总共7个表项，右边给出了6个IP地址，根据路由表求每个地址对应的下一跳 4．求一个带权图的从A到各个点的最短路径，画出来是一个表格（可以参考严蔚敏《数据结构》第七章图的应用举的例子，形式基本没区别） [考研类试卷]计算机专业基础综合数据结构（概论）历年真题试卷汇编 2 一、单项选择题 1 以下哪个数据结构不是多型数据类型?( )【中山大学1999一、3(1分)】 （A）栈 （B）广义表 （C）有向图 （D）字符串 2 以下数据结构中，( )是非线性数据结构【中山大学1999一、4】 （A）树 （B）字符串 （C）队 （D）栈 3 下列数据中，( )是非线性数据结构。【北京理工大学2001六、1(2分)】（A）栈 （B）队列 （C）完全二叉树 （D）堆 4 连续存储设计时，存储单元的地址( )。【中山大学1999一、1(1分)】 （A）一定连续 （B）一定不连续 （C）不一定连续 （D）部分连续，部分不连续 5 以下属于逻辑结构的是( )。【西安电子科技大学应用2001一、1】 （A）顺序表 （B）哈希表 （C）有序表 （D）单链表 6 算法的计算量的大小称为计算的( )。【北京邮电大学2000二、3(20／8分)】（A）效率 （B）复杂性 （C）现实性 （D）难度 7 算法的时间复杂度取决于( )。【中科院计算所1998二、1(2分)】 （A）问题的规模 （B）待处理数据的初态 （C）A和B 7 计算机算法指的是(1)，它必须具备(2)这三个特陛。【南京理工大学1999一、 1(2分)】 8 (1) （A）计算方法 （B）排序方法 （C）解决问题的步骤序列 （D）调度方法 9 (2) （A）可执行性、可移植性、可扩充性 （B）可执行性、确定性、有穷性 （C）确定性、有穷性、稳定性 （D）易读性、稳定性、安全性 10 一个算法应该是( )。【中山大学1998二、1(2分)】 （A）程序 （B）问题求解步骤的描述 （C）要满足五个基本特性 （D）A和C 11 下面说法错误的是( )。【南京理工大学2000一、2(1．5分)】 (1)算法原地工作的含义是指不需要任何额外的辅助空间 (2)在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(22)的算法 (3)所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 (4)同一个算法，实现语言的级别越高，执行效率就越低 一、任务 1.求解多层多跨框架结构在竖向荷载作用下的弯矩以及水平荷载作用下的弯矩和 各层的侧移。 2.计算方法： （1）用近似法计算：水平荷载作用用反弯点法计算，竖向荷载作用采用分层法和二次力矩分配法计算。 （2）用电算（结构力学求解器）进行复算。 3. 就最大相对误差处，说明近似法产生误差的来源。 4. 将手算结果写成计算书形式。 二、结构形式及各种资料 1. 计算简图：如图1所示。 2. 基本计算参数 底层柱bXh(mm) 其它层bXh(mm) 边梁bXh(mm) 中间梁bXh(mm) 500X500 450X450 250X450 250X450 材料弹性模量： 72 3.210/ h E kN m =? 竖向荷载： 2 1 =23/ g kN m，2 2 =20/ g kN m 水平荷载： =32 p F kN 1，2 =18 P F kN 3. 荷载分组： （1）计算水平荷载（见图2）；（2）计算竖向恒载（见图3）； L1L2H1 H2 H2 H2 H2 F F F F F 图1 计算简图图2 水平荷载作用 g2 g1 g1 g1 g1 q2 q1 图3 竖向荷载作用 三、计算内容 ?水平荷载 1、反弯点法 （1）求柱的剪力 由所给数据可得各层梁柱的线刚度(单位：kN·m)如下表： i底柱i其它柱i左梁i右梁 34792363331270825417 第五层柱；F Q14 = F Q25 = F Q36 = 18/3kN = 6kN 第四层柱；F Q47 = F Q58 = F Q69 = 50/3kN 第三层柱；F Q710 = F Q811 = F Q912 = 82/3kN 第二层柱；F Q1013 = F Q1114 = F Q1215 = 114/3kN 第一层柱；F Q1316 = F Q1417 = F Q1518 = 146/3kN （2）求柱的弯矩 第五层柱；M 14 = M 41 = M 25 = M 52 = M 36 = M 63 = 6×3/2 = 9kN·m 第四层柱；M 47 = M 74 = M 58 = M 85 = M 69 = M 96 = 50/3×3/2 = 25kN·m 第三层柱；M 710 = M 107 = M 811 = M 118 = M 912 = M 129 = 82/3×3/2 = 41kN·m 第二层柱；M 1013 = M 1310 = M 1114 = M 1411 = M 1215 = M 1512 = 114/3×3/2 = 57kN·m 第一层柱；M 1316 = M 1417 = M 1518 = 146/3×4.8/3 = 77.87kN·m M 1613 = M 1714 = M 1815 = 146/3×2×4.8/3 = 155.74kN·m （3）求梁的弯矩 分别取结点1、2为隔离体 1 M12 ∑M1=0 M12=M14=9kN·m M14 2007年华中科技大学计算机专业基础综合（计算机组成原理） 真题试卷 (总分：62.00，做题时间：90分钟) 一、填空题(总题数：13，分数：26.00) __________________________________________________________________________________________ 正确答案：(正确答案：1.1101) __________________________________________________________________________________________ 正确答案：(正确答案：111111) 3.磁盘的平均存取时间是指______，该时间由______时间和平均等待时间组成，对于7200转的磁盘而言，其平均等待时间约为______ms(取整数)。 __________________________________________________________________________________________ 正确答案：(正确答案：CPU发出读写命令后，磁头从某一起始位置移动到新的位置，以及从盘片上读写信息所需的平均时间、平均找道、4ms) 4.在微指令格式设计过程中，有8个互斥型的微命令被分配到一组，当该组采用编码方法表示时，微指令格式的相关字段至少需要______位。 __________________________________________________________________________________________ 正确答案：(正确答案：4) 5.CPU中保存当前正在执行指令的寄存器是______。 __________________________________________________________________________________________ 正确答案：(正确答案：指令寄存器LR) 6.CPU的功能包括指令的序列控制_______、_______和_______。 __________________________________________________________________________________________ 正确答案：(正确答案：操作控制、时间控制、数据加工) __________________________________________________________________________________________ 正确答案：(正确答案：1100) 8.设计一个64位全并行的ALU需要______片74181和______片______部件74182。 __________________________________________________________________________________________ 正确答案：(正确答案：16、5、先行进位) 9.响应中断必须具备下列几个条件，它们分别是中断源有中断请求、允许接受中断请求和______。 __________________________________________________________________________________________ 正确答案：(正确答案：现行指令执行结束) __________________________________________________________________________________________ 正确答案：( 11.“数据线双向传输”这句话描述了总线的______特性。 __________________________________________________________________________________________ 计算机专业基础综合数据结构（概论）历年真题试卷汇编3 (总分：70.00，做题时间：90分钟) 一、单项选择题(总题数：15，分数：30.00) 1.设n是描述问题规模的非负整数，下面程序片段的时间复杂度是( )。【2011年全国硕士研究生入学计算机学科专业基础综合试题】简称【201 1年全国试题1(2分)】 x=2； while(x *x； （分数：2.00） A.O(log 2 n) √ B.O(n) C.O(nlog 2 n) D.O(n 2 ) 解析： 2.求整数n(n≥0)阶乘的算法如下，其时间复杂度是( )。【2012年全国试题1(2分)】int fact(int n){if(n<=i) return i；return n*fact(n一1)； （分数：2.00） A.O(log 2 n) B.O(n) √ C.O(nlog 2 n) D.O(n 2 ) 解析： 3.已知两个长度分别为m和n的升序链表，若将它们合并为一个长度为m+n的降序链表，则最坏情况下的时间复杂度是( )。【2013年全国试题1(2)分】 （分数：2.00） A.O(n) B.O(m×n) C.O(min(m，n)) D.O(max(m，n)) √ 解析： 4.下列程序段的时间复杂度是( )。【2014年全国试题1(2分)】count=0;for(k=1；k<=n；k*=2)for(j=1；j<=n；j++)count++； （分数：2.00） A.O(log 2 n) B.O(n) C.O(nlog 2 n) √ D.O(n 2 ) 解析： 5.在数据结构中，数据的最小单位是( )。【北京理工大学2006九、1(1分)】 （分数：2.00） A.数据元素 B.字节 C.数据项√ D.结点 解析： 6.在数据结构中，数据的基本单位是( )。【北京理工大学2004五、1(1分)】 （分数：2.00） A.数据项 B.数据类型 C.数据元素√ 华中科技大学计算机学院2008级博士论文规定 根据《华中科技大学申请博士学位发表学术论文的规定》，我院博士研究生申请博士学位前，须按以下要求之一发表学术论文： 1、A类、B类或学院规定的国际顶尖学术会议论文一篇； 2、SCI期刊论文一篇，C类一篇，国内权威刊物一篇； 3、SCI期刊论文一篇，国内权威刊物二篇； 4、SCI期刊论文一篇，C类二篇。 A、B、C类期刊参照《华中科技大学期刊分类办法》中规定的计算机科学与技术及其它相关学科的期刊执行，其中C类含被EI检索的国际会议论文。 学院规定的国内权威刊物指中国科学、科学通报、Journal of computer Science and Technology、计算机学报、软件学报、计算机研究与发展、Fronties of computer Science in China、电子学报、自动化学报、通信学报、数学学报、应用数学学报、计算机辅助设计与图形学学报及其它相关学科的一级学会学报。 学位申请人发表或接收发表的学术论文中，至少有一篇是以外文全文在C类及以上刊物上发表。 学位申请人发表或被接收发表的学术论文必须是其学位论文的重要组成部分，是学位申请人在导师指导下独立完成的科研成果，以华中科技大学为第一署名单位，以申请人为第一作者（与导师共同发表的论文，导师为第一作者，申请人可以第二作者）。对于“同等贡献作者”排名的认定，参照《华中科技大学期刊分类办法》（校人[2008]28号文）执行。 本规定自2008年入学博士生起执行。本规定的解释和修改权属计算机科学与技术学院学位审议委员会。 华中科技大学计算机科学与技术学院学位审议委员会 课程实验报告课程名称：数据结构 专业班级：计算机科学与技术13xx班 学号： 姓名： 指导教师： 报告日期：2015 计算机科学与技术学院 目录 1 课程实验概述 (1) 2 实验一基于顺序结构的线性表实现 2.1 问题描述 (2) 2.2 系统设计 (2) 2.3 系统实现 (3) 2.4 效率分析 (12) 3 实验二基于链式结构的线性表实现 3.1 问题描述 (14) 3.2 系统设计 (14) 3.3 系统实现 (15) 3.4 效率分析 (25) 4 实验总结与评价 (27) 1 课程实验概述 1.1 加深对数据结构和算法的理解，进一步提高编程能力； 1.2 培养和提高学生分析问题与解决问题的综合能力； 1.3 整理资料，撰写规范的实验报告。 2 实验一基于顺序结构的线性表实现 2.1 问题描述 基于顺序存储结构，实现线性表的基本的常见的运算。 2.2 系统设计 2.2.1系统包括15个功能，分别为： 1.Creatlist 2.DestroyList 3.ClearList 4.ListEmpty 5.ListLength 6.GetElem 7.LocatElem 8.PriorElem 9.NextElem 10.ListInsert 11.ListDelete 12.ListTrabverse 13.Save the List 14.Load the List 15.Add elem to List 2.2.2系统数据物理结构类型为顺序结构，存储的数据类型为结构体： typedef struct { int num; }ElemType;//定义数据类型 2.2.3顺序表应声明一个头结点： typedef struct { ElemType *elem ; //存储顺序表开始的头指针 int listsize; //存储当前顺序表总长度 int length; //存储当前元素的总个数，且当length为-1值时，表示还未被初 《计算机网络与通信》作业 姓名：毛春翔 学号：U201211804 班级：电气1204班 1.试比较电信网络和Internet：他们有什么相似之处，又有哪些不同？ 答：相同：都是传输数据的网络。 不同：电信网络：电路交换、面向连接、实时性好、有QoS； Internet：分组交换、面向非连接、实时性不好。 2.数据链路层的目标是什么？为了实现这些目标，数据链路层采用了哪些方 法？ 答：该层要解决的问题是如何在有差别的线路上进行无差别传输。 数据链路层采用了差错控制，透明传输和寻址的方法。 3.试证明：当用n比特进行数据帧的编号时，若接收窗口等于1，则仅在发送 窗口不超过时（单位为帧），连续ARQ协议才能正常运行。 证明：连续ARQ协议采用边传边等的方式，最坏的结果是每一帧数据都出现问题，每次出现问题时需从错误处重传次，累加则得到发送窗口最大数。 4.以太网的目标是要解决什么问题？采用的是什么方法？以太网从出现至今， 已发生了巨大的变化，请简述：变的是什么，不变的又是什么？ 答：以太网的目标是寻找简单的方法把一些距离不太远的计算机互相连接起来，使他们可以很方便和很可靠地进行较高速率的数据通信。采用CSMA/CD方法。变的是速率，不变的是其最短有效帧长为64字节（数据字节最短为46字节），字段不超过1518个字节，采用星形拓扑结构，MAC地址不变。 5.对于目前的IP网络来说，IP地址不足是一个非常现实的问题。就你所知，目 前有哪些方法用于解决这一问题？ 答：有无类别域间路由技术和网络地址翻译技术。 6.综合所学内容，请简述计算机网络中采用了哪些方法实现可靠数据传输。 答：数据链路层采用了差错控制，透明传输和寻址的方法。TCP协议其自身提供机制保证数据的可靠性传输。 7.试比较RIP和OSPF协议。 答： 一从网络结构看： RIP的拓扑简单，适用于中小型网络。没有系统内外、系统分区、边界等概念，用的不是分类的路由。每一个节点只能处理以自己为头的至多16个节点的链，路由是依靠下一跳的个数来描述的，无法体现带宽与网络延迟。 OSPF适用于较大规模网络。它把AS（自治系统）分成若干个区域，通过系统内外路由的不同处理，区域内和区域间路由的不 《数据结构》试卷 (A 卷) 2010 —2011 年度第二学期计算机学院 班级______ 学号___________ 姓名_________ 考试时间：2011年 月 日 考试形式：闭卷 一、单项选择题(从下列各题四个备选答案中选出一个正确答案,将其代号(A,B,C,D)写在下表中,每小题1分,共10分) 1．对于栈的进栈和出栈运算，采用______存储结构时运算效率最高。 A ．单链表 B ．容量足够大的顺序表 C ．单向循环链表 D ．双向循环链表 2．链式队列和顺序队列比较，具有_____这个优势。 A ．进队操作方便 B ．出队操作方便 C ．通常不会出现满队列情况 D ．求队列元素个数方便 3．下列关于串的叙述中，正确的是_____。 A ．2个串的长度相等，则2个串相等 B ．空串至少包一个空格 C ．替换操作可以实现字符的删除 D ．一个串的长度至少是1 4．二叉树在线索化后，下列问题中相对难解决的是____。 A ．先根线索二叉树中求先根后继 B ．中根线索二叉树中求中根前趋 C ．中根线索二叉树中求中根后继 D ．后根线索二叉树中求后根后继 5．对序列（30，26，18，16，5，66）进行2遍 ________排序后得到序列（5， 16，18，26，30，66）。 A ．选择 B ．冒泡 C ．插入 D ．归并 6．在下列排序算法中，_______算法可能出现如下情况：在最后一趟排序之前， 所有元素均不在其最终的位置上。 A ．堆排序 B ．快速排序 C ．冒泡排序 D ．插入排序 7．由4个结点可以组成______棵不同形态的二叉树。 A ．10 B ．12 C ．14 D ．16 8．对包含n 个元素的散列表进行检索，平均查找长度为____。 A ．O(logn) B ．O(n) C ．O(nlogn) D ．不直接依赖于n 9．广义表 ((a,(b),c),((),(d)),(((((e)),f))),())的长度是____。 A ．2 B ．3 C ．4 D ．5 10．对某无向图进行一次深度优先搜索遍历，如果能访问到所有的顶点，则该无向图一定是________。 A ．连通图 B ．树图 C ．有回路的连通图 D ．完全图 二、填空题(在下表中填写正确的答案,每空1分,共10分) 1．具有n 个单元、用首尾指针、无标志位的循环队列中，队满时共有_______个 元素。 2．设顶点数为n ，弧数为e 的有向图的用邻接表存储，求顶点值为V 的顶点的入 度的算法时间复杂度为_____。 3．某哈夫曼树有11个结点，则它有____个度为2的结点。 4．设森林T 中有三棵树，第一、二、三棵树的结点个数分别是n1，n2，n3，那么 当把森林转换成二叉树后，其根结点的右子树上有______个结点。 5．当线性表经常进行插入和删除操作时，应该选择使用________存储结构。 6．设栈S 和队列Q 的初始状态为空，元素a 、b 、c 、d 、e 、f 依次通过栈S ，一个 元素出栈后即进入队列Q 。若这6个元素出队列的顺序是b 、d 、c 、f 、e 、a ，则栈S 的容量至少应该是______。 7．满足先根遍历序列为a 、b 、c ，后根序列为c 、b 、a 的二叉树共有______棵。 8．按广度优先搜索遍历图的算法需要借助的辅助数据结构是_____。 9．高度为4的平衡二叉树至少有_____个结点。 10．对n 个元素的序列进行简单选择排序，最多进行______次元素的交换。 数据结构试卷（一） 一、单选题（每题 2 分，共20分） 1.栈和队列的共同特点是( )。 A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点 2.用链接方式存储的队列，在进行插入运算时( ). A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改 3.以下数据结构中哪一个是非线性结构？( ) A. 队列 B. 栈 C. 线性表 D. 二叉树 4.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)， A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。 A．688 B．678 C．692 D．696 5.树最适合用来表示( )。 A.有序数据元素 B.无序数据元素 C.元素之间具有分支层次关系的数据 D.元素之间无联 系的数据 6.二叉树的第k层的结点数最多为( ). A．2k-1 B.2K+1 C.2K-1 D. 2k-1 7.若有18个元素的有序表存放在一维数组A[19]中，第一个元素 放A[1]中，现进行二分查找，则查找A［3］的比较序列的下 标依次为( ) A. 1，2，3 B. 9，5，2，3 C. 9，5，3 D. 9，4，2，3 8.对n个记录的文件进行快速排序，所需要的辅助存储空间大致 为 A. O（1） B. O（n） C. O（1og2n） D. O（n2） 9.对于线性表（7，34，55，25，64，46，20，10）进行散列存储 时，若选用H（K）=K %9作为散列函数，则散列地址为1的元 素有（）个， A．1 B．2 C．3 D．4 华中科技大学 嵌入式操作系统课程设计实验报告 院系: 计算机科学与技术学院 专业: 班级： 姓名： 指导老师： 报告时间： 计算机科学与技术学院 目录 1.课程设计目的 (3) 2.课程设计环境搭建 (3) 3.内容一：熟悉和理解Linux编程环境 3.1 内容要求 (5) 3.2 设计过程及实现 (5) 4.内容二：掌握添加系统调用的方法 4.1 内容要求 (9) 4.2 设计过程及实现 (9) 5.内容三：掌握添加设备驱动程序的方法 5.1 内容要求 (17) 5.2 设计过程及实现 (17) 6.内容四：理解和分析/proc文件 6.1 内容要求 (22) 6.2 设计过程及实现 (22) 1 课程设计目的 （1）掌握Linux操作系统的使用方法； （2）了解Linux系统内核代码结构； （3）掌握实例操作系统的实现方法。 2 课程设计环境搭建 （1）windows 7上，利用虚拟机软件VMware软件搭建的linux平台：◎Ubuntu 11.10 （安装包：ubuntu-11.10-desktop-i386） ◎内核：linux-headers-3.0.0-12-generic （2）更改root登录： 在现阶段Ubuntu的系统中，是不允许直接以root身份登录系统的，但是在做课设的过程中，需要大量的使用root权限来进行命令的操作。如果以普通用户登录ubuntu，会连编辑一个文件都非常周折。为此，我找到了一种修改系统文件，以达到直接使用root身份登录的方法： ◎开始的时候，只能以普通用户登录，用Ctrl+Alt+T打开终端： 初始化/修改root密码 sudo passwd root 用vi编辑器修改这个文件： sudo vi /etc/lightdm/lightdm.conf 在文件最后加入这么一行代码： greeter-show-manual-login=true 然后保存退出，sudo reboot 重启系统。之后就可以输入root用户登录。（3）在添加系统调用中用到的其他内核包： ◎下载和当前实验环境最为接近的系统版本（这点很重要） 使用apt-get install linux-source-3.0.0 命令， ◎下载结果是linux-source-3.0.0.tar.bz2 ◎解压命令：tar –xjvf linux-source-3.0.0.tar.bz2 –C /usr/src ◎解压后，在/usr/src目录下得到内核文件夹linux-source-3.0.0华科数据结构实验
数据结构试题B及参考答案(计算机专业)
华中科技大学结构力学试卷及答案
华中科技大学887+数据结构与算法分析考研大纲
计算机专业基础综合(数据结构)模拟试卷1
华科计算机考研复试数据库复习资料
2018计算机考研：计算机数据结构测试题(四)
华中科技大学计算机网络试题
2018年华中科技大学834计算机专业基础综合(数据结构、计算机网络)考研真题(回忆版)
[考研类试卷]计算机专业基础综合数据结构(概论)历年真题试卷汇编2.doc
结构力学大作业(华科)
2007年华中科技大学计算机专业基础综合(计算机组成原理)真题试卷
计算机专业基础综合数据结构(概论)历年真题试卷汇编3
华科计算机学院博士毕业条件
华科数据结构实验报告
华中科技大学计算机与网络习题
2011本科数据结构试卷A试题
广州大学插本数据结构试题
华中科技大学计算机学院操作系统课程设计报告[1]
相关主题
文本预览