东北大学数据结构复习题(2010)

东北大学《测试技术基础》期末考试必备真题集(含答案)99

测试技术基础复习题 一．单项选择题 1、概率密度函数曲线下的面积是（ 2 ）。 （1）（2）（3）（4） 2．一般周期信号可以利用傅里叶级数展开成（ 2 ）不同频率的谐波信号的线性叠加。 （1）两个（2）多个乃至无穷多个 （3）偶数个（4）奇数个： 3、用二阶系统作测量装置时,为获得较宽的工作频率范围,则系统的阻尼比应( 4 )。 （1）愈大愈好（2）愈小愈好（3）接近1/2 （4）接近2 1 4、不能用确定的数学公式表示的信号是（ 3 ）信号。 （1）复杂周期信号：（2）非周期：（3）随机：（4）瞬态：5、非线性度是表示定度(标定)曲线（ 1 ）的程度。 （1）偏离其拟合直线； （2）接近真值； （3）加载和卸载时不重合； （4）在多次测量时的重复。 6、调幅波是（ 2 ）。 （1）载波与调制信号（即被测信号）相加； （2）载波幅值随调制信号幅值而变；

（3） 载波频率随调制信号幅值而变； （4） 载波相位随调制信号幅值而变。 7、 磁带记录仪快录慢放将使重放信号的频谱带宽（2 ）。. （1）变窄，幅值压低 （2）变窄，幅值增高 （3）扩展，幅值增高 （4）扩展，幅值压低 8、倒频谱函数自变量可使用的单位是（1）。 （1）毫秒 （2）赫兹 （3）毫伏 （4）毫米/秒 二．问答题 1、以双臂工作为例，说明在进行电阻应变测量时，消除温度影响的原理和条件？ 答：将两个应变片联接在工作臂的相邻桥臂上，则因温度变化，引起的工作臂与补偿片的阻值相等，因在相邻桥臂上，阻值相减，消除了温度影响。 条件：（1）应变片相同；（2）材料相同；（3）放在相同温度场中；（4）联接在相邻桥臂上 2、用2种不同的方法确定信号中是否含有周期成分？ 答：信号的概率密度函数在均值处有盆形特征； 做自相关函数)(τx R ，)(τx R 含有周期成份，不随τ的增大而衰减； 3、说明互相关分析的概念和主要应用？ )]()([)(ττ+=t y t x E R xy

数据结构-数据结构历年考题及答案2

中国矿业大学2011-2012学年 《数据结构》试卷（A卷）（考试时间：100分钟） 一. 填空（每空2分，共40分） 1. 数据结构式具有相同性质的数据元素的（1）。 2. 通常程序在调用另一个程序时，都需要使用一个（2）来保存被调用程序内分配的局部变量、形式参数的存储空间以及返回地址。 3. 有6行8列的二维数组A，每个元素用相邻的6个字节存储，存储器按字节编址，已知A的起始存储地址（基址）为1000，在行优先存储和列优先存贮情况下A[5,5]的存储地址分别为__（3）_____,_____(4)____。 4. 完全二叉树第4 个节点的父节点是第 (5) 节点，左孩子是第 (6) 个节点。如果该二叉树有10层，则共有 (7) 个节点。 5. 请描述在循环队列Q中，队头和队尾指针分别由front和rear表示，该队列有10个存储空间，判断队空和队满的条件分别分：_____(8)________,_______(9)_________。 6. 字符串t=”child”，s=”cake”，请写出下列函数的结果：StrLength(t) =（10）__;Concat(SubString(s,3,1)，SubString(t,2,2))=____（11）___。 7. 一棵二叉树为 则后序序列为（12），中序序列为（13），先序序列为__（14）____。 8. 请用数据序列{53，17，12，66，58，70，87，25，56，60 }构造一棵二叉排序树_(15）_。 9.。一个栈输入的序列式1,2,3，则可能的且以2为开头的输出序列是 (16) ，不可能的序列是____（17）____。 10. 有n个结点的无向完全图的边数分别为_______(18)_______。 11. 要从数据：2，3，4，8，9，11，13查找11，若采用折半查找法，则在（19）次比较后，才找到该数据。 12. 在直接插入排序、希尔排序、冒泡排序和快速排序中，平均情况下（20）_____最快。 二简答题： 1给定{15,3,14,2,6,9,16,17}，试为这8个数设计哈夫曼编码，并计算其带权路径长度。 2请对下图的无向带权图按克鲁斯卡尔算法求其最小生成树。（要求使用图画出每一步过程）。 C G E D F B H A

40875][东北大学]20年7月考试《数据结构Ⅱ》考核作业(答案)

东北大学继续教育学院 数据结构II 试卷（作业考核线上1） A 卷 学习中心：奥鹏远程教育沈阳学习中心（直属）[32]院校学号：C09024011930344 姓名何家强 （共 6 页） [ A]1．抽象数据类型的三个组成部分分别为 A．数据对象、数据关系和基本操作 B．数据元素、逻辑结构和存储结构 C．数据项、数据元素和数据类型 D．数据元素、数据结构和数据类型 [ B]2．要求相同逻辑结构的数据元素具有相同的特性，其含义为 A. 数据元素具有同一的特点 B. 不仅数据元素包含的数据项的个数相同，而且其对应数据项的类型要一致 C. 每个数据元素都一样 D. 仅需要数据元素包含的数据项的个数相同 [ D]3．下列各式中，按增长率由小至大的顺序正确排列的是 A．n，n！，2n ，n3/2 B．n3/2，2n，n logn，2100 C．2n，log n，n logn，n3/2 D．2100，logn, 2n, n n [B ]4. 在下列哪种情况下，线性表应当采用链表表示为宜 A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 [ C]5．设指针p指向双链表的某一结点，则双链表结构的对称性是 A. p->prior->next=p->next->next; B. p->prior->prior=p->next->prior; C. p->prior->next=p-> next->prior; D. p->next->next= p->prior->prior;

[D ]6. 已知指针p和q分别指向某带头结点的单链表中第一个结点和最后一个结点。假设指 针s指向另一个单链表中某个结点，则在s所指结点之后插入上述链表应执行的语句为 A. s->next=q；p->next=s->next； B. s->next=p；q->next=s->next； C. p->next=s->next；s->next=q； D. q->next=s->next；s->next=p； [A ]7. 栈和队列的共同特点是 A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点 [D ]8. 对于链队列，在进行插入运算时. A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改 [B ]9．设有一个顺序栈的入栈序列是1、2、3，则3个元素都出栈的不同排列个数为 A．4 B．5 C. 6 D. 7 [D ]10．设一个栈的输入序列为A，B，C，D，则借助一个栈所得到的输出序列不可能是 A．A，B，C，D B．D，C，B，A C. A，C，D，B D. D，A，B，C [ C]11．表达式a*(b+c)-d的后缀表达式是 A．abcd*+- B．abc*+d- C．abc+*d- D．-+*abcd [B ]12．某二叉树的先序序列和后序序列正好相反，则该二叉树的特点一定是 A. 空或只有一个结点 B.高度等于其结点数 C. 任一结点无左孩子 D.任一结点无右孩子 [ B]13．下面的说法中正确的是 (1)任何一棵二叉树的叶子结点在种遍历中的相对次序不变。 (2)按二叉树定义，具有三个结点的二叉树共有6种。 A．(1)，(2) B．(1) C．(2) D．(1)，(2)都错 [ B]14．树有先序遍历和后序遍历，树可以转化为对应的二叉树。下面的 说法正确的是 A．树的后序遍历与其对应的二叉树的先序遍历相同 B．树的后序遍历与其对应的二叉树的中序遍历相同 C．树的先序序遍历与其对应的二叉树的中序遍历相同 D．以上都不对 [D ]15．下列说法正确的是 (1)二又树按某种方式线索化后，任一结点均有前趋和后继的线索 (2)二叉树的先序遍历序列中，任意一个结点均处于其子孙结点前 (3)二叉排序树中任一结点的值大于其左孩子的值，小于右孩子的值 A．(1)(2)(3) B．(1)(2) C．(1)(3) D．都不对 [D ]16. 二叉树的第k层的结点数最多为 A．2k-1 B.2K+1

下册东北大学高数期末考试试题

2008~2009学年第二学期 试题 一、单项选择题（本题共4小题，每小题4分，共计16分） 1.设函数(,)f x y 在点(0,0)的某邻域内有定义，且(0,0)3x f =，(0,0)1y f =-，则[ ] (A)(0,0) 3dz dx dy =-； (B) 曲面(,)z f x y =在点(0,0,(0,0))f 的一个法向量为(3,1,1)-； (C)曲线(,) 0z f x y y =??=?在点(0,0,(0,0))f 的一个切向量为(1,0,3)； (D) 曲线(,) 0z f x y y =??=?在点(0,0,(0,0))f 的一个切向量为(3,0,1) 2. 设1 0 (1,2,)n u n n ≤< =L ，则下列级数中必收敛的是[ ] (A)1 n n u ∞ =∑； (B) 1 (1)n n n u ∞ =-∑； (C) 1 n ∞ = (D) 21 (1)n n n u ∞ =-∑. 3. 如果81 lim 1=+∞→n n n a a ，则幂级数∑∞ =03n n n x a [ ] (A) (B) (C) (D) . 4. 设Ω是由球面2222x y z a ++=所围成的闭区域，则222x y z dv Ω ++???= [ ] . (A) 545a π； (B) 44a π； (C) 543a π； (D) 52 5 a π. 二、填空题（本题共6小题，每小题4分，共计24分） 1. 曲面2222321x y z ++=在点(1,2,2)-处的法线方程为 . 2. 函数),(y x f 22y xy x +-=在点)1,1(处的全微分为 . 3. 已知曲线L 为连接(1,0)和(0,1)两点的直线段，则曲线积分

2010年数据结构期中考试试卷及答案

《数据结构》期中试卷（2009级） 2010-2011学年第一学期姓名：学号：成绩： 一、选择题：（每小题2分，共20分） 1.有六个元素6，5，4，3，2，1 的顺序进栈，下列哪一个不是合法的出栈序列？（） A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 2.在一个有125个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（） 个元素。 A．8 B. 62.5 C. 62 D. 7 3. 已知广义表A＝((a,b,c),(d,e,f),(h,(i,j)),g)，从A表中取出原子项e的运算是：( ) A.head(tail(A)) B.head(tail(tail(A))) C.head(head(tail(tail(A)))) D.head(tail(head(tail(A)))) 4.循环队列存储在数组A[0..m]中，设front和rear分别为队列的头指针和尾指针，则入队 时的操作为（）。 A. front=( front +1) mod (m+1) B. rear=(rear+1) mod (m+1) C. front=( front +1) mod m D. rear=(rear+1) mod m 5. 在双向循环链表中,在p指针所指向的结点前插入一个指针q所指向的新结点,其修改指 针的操作是( ) (假设双向循环链表的结点结构为(llink,data,rlink)。A．p->llink=q； q->rlink=p；p->llink->rlink=q；q->llink=q； B．p->llink=q；p->llink->rlink=q ；q->rlink= p；q->llink=p->llink； C．q->rlink=p；q->llink=p->llink；p->llink->rlink=q; p->llink=q; D．q->llink=p->llink；q->rlink=p；p->llink=q；p->llink=q； 6. 一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）。 A．250 B．500 C．254 D．以上答案都不对 7. 已知一棵二叉树的前序遍历结果为ABCDEF, 中序遍历结果为CBAEDF, 则后序遍历的结果 为（）。 A．CBEFDA B．FEDCBA C．CBEDFA D．不定 8. 利用二叉链表存储树时，则根结点的右指针是（）。 A．指向最左孩子B．指向最右孩子C．空D．非空 9.设有二维数组A[0..9, 0..19], 其中每个元素占两个字节，第一个元素的存储地址为100， 若按列优先顺序存储，则元素A[6,6]存储地址为( )。 A. 252 B. 132 C. 352 D.232 10. 引入二叉线索树的目的是（） A．加快查找结点的前驱或后继的速度 B．为了能在二叉树中方便的进行插入与删除 C．为了能方便的找到双亲 D．使二叉树的遍历结果唯一

东北大学2000年数据结构试题

1 （20分）简要回答下列问题 （注意：请将答案写在答题纸上，并注明题号） ①（3分） 内存中一片连续空间（不妨假设地址从1到m），提供给两个栈S1和S2使用，怎样分配这部分存储空间，使得对任一个栈，仅当这部分空间全满时才发生上溢。 ②（5分） 假设字符a,b,c,d,e,f的使用频度分别是0.07,0.09,0.12,0.22,0.23,0.27，写出a,b,c,d,e,f的Huffman（哈夫曼）编码。 ③（4分） 一棵共有n个结点的树，其中所有分枝结点的度均为k，求该树中叶子结点的子数。 ④（4分） 图1表示一个地区的通讯网，边表示城市间的通讯线路，边上的权表示架设线路花费的代价，如何选择能沟通每个城市且总代价最省的n-1条线路，画出所有可能的选择。 ⑤（4分） 在起泡（汽泡）排序过程中，有的关键字在某趟排序中可能朝着与最终排序相反的方向移动，试举例说明之。快速排序过程中有没有这种现象？ 2 （15分）

设有一个由正整数组成的无序（向后）单链表，编写完成下列功能的算法： ①找出最小值结点，且打印该数值； ②若该数值是奇数，则将其与直接后继结点的数值交换； ③若该数值是偶数，则将其直接后继结点删除； 3 （14分） 解答下列问题： ①(4分） 将算术表达式((a+b)+c*(d+e)+f)*(g+h) 转化为二叉树； ②(10分） 假设一个仅包含二元运算符的算术表达式以二叉链表形式存储在二叉树BT中，写出计算该算术表达式值的算法。 4（21） 解答下列问题： ①（5分） 画出有向图的十字链表存储结构中头结点和表结点的结点结构。 ②(4分） 下面哪一个方法可以判断出一个有向图中是否有环（回路）？ (1)深度优先遍历 (2)拓朴排序(3)求最短路径(4)求关键路径 ③(12分）

东北大学《电子商务》期末考试必备真题集(含答案)81

电子商务复习题B 一、单项选择题 1．在电子商务分类中，B to C是指( ) A.消费者与消费者间的电子商务 B.企业间的电子商务 C.企业内部的电子商务 D.企业与消费者间的电子商务 2．电子商务的安全是指( )。 A.由客户机到通讯信道的安全 B.由客户机到电子商务服务器的安全 C.由通讯信道到电子商务服务器的安全 D.由通讯信道到WWW的安全 3．下列中英名字对应正确的是（） A．TCP/IP：传输控制协议B．FTP：文件传输协议 C．HTTP：预格化文本协议 D．DNS：统一资源定位器 4．以下属于C类IP地址的是（） A． B． D．以下说法不正确的是( ) A.包交换避免了网络中的交通拥挤 B.最早的包交换网是APRANET C.包交换模式非常适用于电话 D.包交换有利于降低信息传输成本 6．认证中心的主要职能是（） A．验证信息 B．签发和管理数字证书

C．签发数字证书 D．验证数字证书 7. 正确的URL格式为( ) A. (主机名):(协议):(协议):(协议):将数据变为乱码传送到达目的地后重新还原的技术是（）。 A、数字签名 B、防火墙技术 C、加密技术 D、身份验证 9．电子交易中网络安全不包括（） A．信息的保密性 B．数据交换的完整性 C．发送信息的不可否认性 D．交易场所的安全性 10．SET协议涉及的对象不包括（） A、在线商店 B、收单银行 C、货币发行单位 D、认证中心 11．数字证书采用公钥体制中，每个用户设定一把公钥，用它进行:（） A、加密和验证签名 B、解密和签名 C、加密 D、解密 12．假定（1）登陆商家网站（2）选择招商银行“一网通”进行付款（3）浏览商品，并放入购物车或购物篮（4）确认订购信息完成交易。则工作程序为（） A. （1）（2）（3）（4） B. （1）（3）（2）（4） C. （3）（4）（1）（2） D. （4）（2）（1）（2） 13.不适合电子商务的业务是( )

数据结构实验-互联网域名查询实验报告

实验报告 实验课程：数据结构 实验项目：实验三互联网域名查询 专业：计算机科学与技术 班级： 姓名： 学号： 指导教师：

目录一、问题定义及需求分析 （1）问题描述 （2）实验任务 （3）需求分析 二、概要设计： (1)抽象数据类型定义 (2)主程序流程 (3) 模块关系 三、详细设计 (1)数据类型及存储结构 (2)模块设计 四、调试分析 (1)调试分析 (2)算法时空分析 (3)经验体会 五、使用说明 (1)程序使用说明 六、测试结果 (1)运行测试结果截图 七、附录 (1)源代码

一、问题定义及需求分析 （1）实验目的 互联网域名查询 互联网域名系统是一个典型的树形层次结构。从根节点往下的第一层是顶层域，如cn、com等，最底层（第四层）是叶子结点，如www等。因此，域名搜索可以看成是树的遍历问题。 （2）实验任务 设计搜索互联网域名的程序。 （3）需求分析： 1)采用树的孩子兄弟链表等存储结构。 2)创建树形结构。 3)通过深度优先遍历搜索。 4)通过层次优先遍历搜索。 二、概要设计： 采用孩子兄弟链表存储结构完成二叉树的创建； 主程序流程： 创建根节点域名输入域名拆分根据孩子兄弟链表表示的树进行插入调用层次优先遍历输出遍历结果调用深度优先遍历输出遍历结果结束程序 模块关系： 输入域名 创建孩子兄弟树 层次优先遍历输出结果 深度优先遍历输出结果 结束 三、详细设计 孩子兄弟链表结构： typedef struct CSNode{ ElemType data[10]; struct CSNode *firstchild, *nextsibling; }*CSTree;

2010级数据结构期末复习题(E)

一、是非题 1.数据结构概念包括数据之间的逻辑结构，数据在计算机中的存储方式和数据的运 算三个方面。.......................( T ) 2.线性表的逻辑顺序与物理顺序总是一致的........( F ) 3.线性表中的每个结点最多只有一个前驱和一个后继。......( T ) 4.线性的数据结构可以顺序存储，也可以链接存储。非线性的数据结构只能链接存 储。.......................( F ) 5.栈和队列逻辑上都是线性表。..........................( T ) 6.单链表从任何一个结点出发，都能访问到所有结点........( F ) 7.单链表形式的队列，头指针F指向队列的第一个结点，尾指针R指向队列的最后 一个结点。.................................................( T ) 8.在用单链表表示的链式队列中，队头在链表的链尾位置。....( F ) 9.多维数组是向量的推广。..............................( T ) 10.栈是一种先进先出的线性表。....( F ) 11.凡是递归定义的数据结构都可以用递归算法来实现它的操作。......( T ) 12.设串S的长度为n,则S的子串个数为n(n+1)/2。...........( F ) 13.一般树和二叉树的结点数目都可以为0。................( F ) 14.按中序遍历二叉树时，某结点的直接后继是它的右子树中第1个被访问的结 点。....( T ) 15.后序序列和中序序列能唯一确定一棵二叉树。....( T ) 16.对于一棵具有n个结点，其高度为h的二叉树，进行任—种次序遍历的时间复杂 度为O(n) .............( T ) 17.网络的最小代价生成树是唯一的。...( T ) 18.图的拓扑有序序列不是唯一的。...( T ) 19.进行折半搜索的表必须是顺序存储的有序表。...( T ) 二、单选题 1.算法指的是（ D ） A．计算机程序 B．解决问题的计算方法 C．排序算法 D．解决问题的有限运算序列 2.线性表采用链式存储时，结点的存储地址（B ） A．必须是不连续的 B．连续与否均可 C．必须是连续的 D．和头结点的存储地址相连续 3.将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为（C ） A．O（1） B．O（n） C．O（m） D．O（m+n） 4.在一个长度为n的顺序表的表尾插入一个新元素的渐进时间复杂度为( B )。 A．O(n) B．O(1) C．O(n2) D．O(log2n)T 5.线性表L在( B )情况下适用于使用链式结构实现。 A.需经常修改Ｌ中的结点值 B.需不断对Ｌ进行删除插入 C.L中含有大量的结点 D.L中结点结构复杂 6.设单链表中结点的结构为(data，1ink)。已知指针q所指结点是指针p所指结点 的直接前驱，若在*q与*p之间插入结点*s，则应执行下列哪一个操作?( B ) A．s一>1ink=p一>1ink；p一>1ink＝s B．q一>1ink＝s；s一>link=p C．p一>link＝s一>1ink；s一>1ink＝p

东北大学《社会调查研究方法X》期末考试必备真题集(含答案)28

东北大学继续教育学院 社会调查研究方法X复习题 一、单选题 1.条形图多用于描述定类与定序变量的分布，它是以长条的高度表示变量不同取值的（A ）分布的，其中长条的宽度没有意义，一般均画成等宽长条。 A频率 B概率 C速率 D效度 2.定性资料整理的工作量大，它主要包括分类、建档、（B）等具体内容。 A排序 B编码 C归类 D总结 3.实验的设计方法很多，最典型的实验设计是将调查对象分为实验组和（B），分别观测他们在实验前后的变化。 A样本组 B控制组 C系统组 D调查组 4.（B）于1928年提出的抽样理论为社会研究的代表性、科学性提供了数理基础。A 法约尔 B费舍尔 C泰勒 D孔德 E马克思 5. 波普提出的假设检验法是由归纳和（A）这两种逻辑构成的 A演绎 B判断 C逻辑 D推理 6.举例说明法即是用（D）来说明某种理论。 A具体示例 B逻辑推理 C感性认知 D经验证据 7.定性研究的分析方式是归纳法，主要寻找概念和主题，它的研究工具是（C） A量表 B统计软件 C研究者本人和录音机 D问卷 8. 关于总体中某一变量的综合指标，在统计中最常见的总体值是某一变量的平均值称为（A） A参数值 B统计值 C抽样误差 D置信区间 9.（B）是指研究问题、观察问题时的角度、视野和参照框架。它是由一整套概念和假定组成的，它反映了科学家看待世界、解答问题的基本发生。

A概念 B范式 C原则 D理论 10.对搜集得来的资料进行思维加工，目的在于说明调查研究对象的本质特征，由此得出规律性的认识，是一种理性认识活动称之为（A） A社会研究 B社会调查 C理论研究 D基础研究 11.关于样本中某一变量的综合描述，它是相应的总体值的估计量称为（B） A参数值 B统计值 C抽样误差 D置信区间 12.从全体或总体中随机抽取出来并用来代表总体的那部分单位所构成的新的小总体称之为（B） A总体 B样本 C抽样误差 D置信区间 13.在西方，社会调查是随着抽样方法和问卷方法的发展而形成的一套结构化的资料收集方法。它常常被称为（ A）和问卷调查。 A抽样调查 B头脑风暴法 C专家讨论 D比例调查 14.（A）是对有相关关系的现象,根据其关系的形态找出一个合适的数学模型,即建立回归方程,来近似地表达变量间的平均变化关系,以便依据回归方程对未知的情况进行估计和预测。 A置信区间 B回归分析 C 线性代数 D变量 15．有效测量的三个条件准确性、完备性、与（C） A相关性 B包含性 C互斥性 D递进行 16．李可特量表是目前使用最广泛的总加量表，它是由美国社会心理学家李可特于（B）在原有的总加量表基础上改进而成的。 A 1934年 B 1932年 C 1944年 D 1929年 二、判断题 1.总体通常与构成它的元素共同定义，总体是构成它的所有元素的集合，而元素则是构成总体的最基本单位。 T 2.美国的社会调查，最早始于社会学家贝利博士，他调查了有关美国的生活、生产及农村风俗习惯等问题。（T ） 3.总体来说，实地研究所得的资料往往比定量研究中所得的资料更易于推断变量间的关系。（F ） 4.定序测量程序有多种，最直接的一种是等第顺序法。它要求被试者对一组刺激（包括物体事件或现象）依某种属性由高到低或由多到少的次序予以排列。( T)

东北大学数据结构上机实验报告3

实验三树和图应用 一、实验目的 光纤管道铺设施工问题 问题描述 设计校园内有N个教学楼及办公楼，要铺设校园光纤网，如何设计施工方案使得工程总的造价为最省。 二、实验要求 设计校园光纤网铺设的最小生成树模拟程序。 1)采用邻接表或邻接矩阵存储结构。 2)分别采用普利姆算法和克鲁斯卡尔算法实现。 输入形式 对应的教学楼、办公楼数目n，各边权值即每栋楼之间的距离 输出形式 最小生成树，即总路程最小的路 程序功能 设计校园光纤网铺设的最小生成树模拟程序 三、设计概要 流程图 抽象数据类型的定义 class prims { private:

int n; //节点的个数 int graph_edge[99][4]; //图的边 int g; //图中边的个数 int tree_edge[99][4]; //树的边 int t; //树的边的个数 int s; //源节点 int T1[50],t1; // 第一部分 int T2[50],t2; //第二部分 public: void input(); int findset(int); void algorithm(); void output(); }; 各程序模块之间的调用关系 四、详细设计 定义prims类 private中进行对图的创建 public: void input(); int findset(int); void algorithm();

void output(); 开始界面 实现prims类中图的初始化 分别输入图中的顶点个数、图的边及其权值 算法构造 t=0;//初始化边的个数为0 t1=1; T1[1]=1; //资源节点 t2=n-1; int i; for(i=1;i<=n-1;i++) T2[i]=i+1; cout<<"\n\n*****运算开始*****\n\n\n"; while(g!=0 && t!=n-1) { int min=99; int p; int u,v,w; for(i=1;i<=g;i++) { if(findset(graph_edge[i][1])!=findset(graph_edge[i][2])) //如果u和v在不同的部分{ if(min>graph_edge[i][3]) { min=graph_edge[i][3]; u=graph_edge[i][1]; v=graph_edge[i][2]; w=graph_edge[i][3]; p=i; } } } for(int l=p;l

数据结构2010

2010年招收攻读硕士学位研究生入学考试试题（副题） ******************************************************************************************** 学科、专业名称：计算机技术、软件工程 研究方向：各专业 考试科目名称：830数据结构 考生注意：所有答案必须写在答题纸（卷）上，写在本试题上一律不给分。 一.选择题(每题2分，共40分) 1.具有n个顶点的完全有向图的边数为( ). A n(n-1)/2 B n(n-1) C n2 D n2-1 2.队列操作的原则是（） A.先进先出 B.后进先出 C.只能进行插入 D.只能进行删除 3. 顺序栈S的Pop(S, e)操作弹出元素e，则下列( )是正确的操作。 A. e=*(s.top) B. e=*(s.top--) C. e=*(--s.top) D. e=--s.top 4. 对具有n个结点的有序表折半查找时，其时间复杂度是 ( ) 。 A. O(log2n） B. O(nlog2n） C. O(n） D. O(n2） 5. 若线性表最常用的操作是存取第i个元素及其前趋的值,则采用( )存储方式节省时间。 A.单链表 B.双链表 C.单循环链表 D.顺序表 6. 线性表的链接实现有利于( )运算 A.插入 B. 读表元素 C .查找 D.定位 7. 设连通图G的顶点数为n,则G的生成树的边数为( ) A. n B. n-1 C.2n D. 2n-1 8.从一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，需向前移动（）个元素。 A.n-i B.n-i+1 C.n-i-1 D. i 9. 若有一个栈的输入序列是1，2，3，…，n，输出序列的第一个元素是n,则第i个输出元素是（） A.n-i B.n-i-1 C.n-i+1 D.不确定 10. 二叉树第i(i≥1)层上至多有( )个结点。 A. 2i B.2i C.2i-1 D.2i-1 11.串是一种特殊的线性表, 其特殊性体现在( ) A.可以顺序存储 B.数据元素是一个字符 C.可以链接存储 D.数据元素可以是多个 12. 稀疏矩阵一般的压缩存储方法有两种,即: ( ) A.二维数组和三维数组 B.三元组和散列 C.三元组和十字链表 D.散列和十字链表 考试科目：数据结构共 4 页，第 1 页

东北大学《数据库技术及应用Ⅰ》期末考试必备真题集(含答案)98

东北大学继续教育学院 数据库技术及应用Ⅰ复习题 一、选择题 1．下面列出的数据库管理技术发展的三个阶段中，没有专门的软件对数据进行管理的是___________。D I．人工管理阶段 II．文件系统阶段 III．数据库阶段 A）I 和 II B）只有 II C）II 和 III D）只有 I 2．下列四项中，不属于数据库系统特点的是___________。C A）数据共享 B）数据完整性 C）数据冗余度高 D）数据独立性高 3．描述数据库全体数据的全局逻辑结构和特性的是___________。A A）模式 B）内模式 C）外模式 D）用户模式 4．要保证数据库的数据独立性，需要修改的是___________。C A）模式与外模式 B）模式与内模式 C）三层之间的两种映射 D）三层模式 5．一个关系只有一个___________。D A）候选码 B）外码 C）超码 D）主码 6．现有一个关系：借阅（书号，书名，库存数，读者号，借期，还期），假如同一本书允许一个读者多次借阅，但不能同时对一种书借多本，则该关系模式的外码是___________。D A）书号 B）读者号

C）书号+读者号D）书号+读者号+借期 7．关系数据库系统中所使用的数据结构是___________。D A）树 B）图 C）表格 D）二维表格 8．已知关系模式R（A，B，C，D，E）及其上的函数相关性集合F＝{A→D，B→C ，E→A }，该关系模式的候选关键字是___________。B A）AB B）BE C）CD D）DE 9．设有关系模式W（C，P，S，G，T，R），其中各属性的含义是：C表示课程，P表示教师，S表示学生，G表示成绩，T表示时间，R表示教室，根据语义有如下数据依赖集：D={ C →P，（S，C）→G，（T，R）→C，（T，P）→R，（T，S）→R }，若将关系模式W分解为三个关系模式W1（C，P），W2（S，C，G），W2（S，T，R，C），则W1的规范化程序最高达到___________。D A）1NF B）2NF C）3NF D）BCNF 10．以下关于查询的叙述正确的是___________。C A）只能根据数据表创建查询 B）只能根据已建查询创建查询 C）可以根据数据表和已建查询创建查询 D）不能根据已建查询创建查询 11．SQL语句是___________语言。C A）层次数据库 B）网络数据库 C）关系数据库 D）非数据库 12．SQL语言集数据查询、数据操纵、数据定义和数据控制功能于一体，其中，CREATE、DROP、ALTER语句是实现哪种功能___________。C A）数据查询 B）数据操纵 C）数据定义 D）数据控制 13．下列的SQL语句中，___________不是数据定义语句。D

数据结构实验二-

实 验 报 告 一、实验目的 1) 加深对图的表示法和图的基本操作的理解，并可初步使用及操作； 2) 掌握用图对实际问题进行抽象的方法，可以解决基本的问题； 3) 掌握利用邻接表求解非负权值、单源最短路径的方法，即利用Dijkstra 算法求最短 路径，同时掌握邻接表的建立以及使用方法，能够解决相关的问题； 4) 学会使用STL 中的map 抽象实际问题，掌握map ，List,，priority_queue 等的应 用。 二、实验内容与实验步骤 （1） 实验内容： 使用图这种抽象的数据结构存储模拟的欧洲铁路路线图，通过Dijkstra 算法求出欧洲旅行最少花费的路线。该实验应用Dijkstra 算法求得任意两个城市之间的最少路费，并给出路费最少的路径的长度和所经过的城市名。 （2） 抽象数据类型及设计函数描述 1) 抽象数据类型 class City ： 维护一个城市的信息，包括城市名name ，是否被访问过的标记visted ，从某个城市到达该城市所需的总费用total_fee 和总路径长度total_distance ，求得最短路径后路径中到达该城市的城市名from_city 。 class RailSystem ： 用邻接表模拟欧洲铁路系统，该邻接表使用数据结构map 实现，map 的key-value 课程名称：数据结构 班级： 实验成绩： 实验名称：欧洲旅行 学号： 批阅教师签字： 实验编号：实验二 姓名： 实验日期：2013 年6 月 18 日 指导教师： 组号： 实验时间：

值对的数据类型分别为string和list<*Service>，对应出发城市名和该城市与它能 够到达的城市之间的Service链表。 class Service： 为铁路系统模拟了两个城市之间的直接路线，包括两个城市之间直接到达的费用 fee，两城市之间的直接距离distance。 部分设计函数描述 ●RailSystem(const string& filename) 构造函数，调用load_services(string const &filename)函数读取数据 ●load_services(string const &filename) 读取传入的文件中的数据并建立上述两个map以模拟欧洲铁路路线图 ●reset(void) 遍历cities图，初始化所有城市的信息：visted未访问，total_distance最大 值，total_fee费用最大值，from_city为空 ●~RailSystem(void) 析构函数，用delete将两个map中所有使用new操作符开辟的空间删除 ●void output_cheapest_route(const string& from, const string& to, ostream& out); 输出两城市间的最少费用的路径，调用calc_route(string from, string to)函 数计算最少费用 ●calc_route(string from, string to) 使用Dijkstra算法计算from和to两个城市间的最少费用的路径 （3）采用的存储结构 1)map > outgoing_services 用来保存由一个城市出发可以直接到达的城市名及这两个城市之间的路径信息。 2)list 以service为指针的list表，保存两城市间的路径。 3)map cities 用来保存所有城市信息，通过城市名查找该城市有关信息。 4)priority_queue, Cheapest> candidates 存储候选的遍历城市，City*是优先队列存储的对象类型，vector是该对象的向量集合，Cheapest是比较规则。 三、实验环境 操作系统：Windows 8 调试软件：Microsoft visual studio 2012 上机地点：综合楼311 机器台号：笔记本

中国矿业大学2010年数据结构试卷及答案

计算机学院2010-2011学年第一学期 《数据结构》试卷（A 卷）（考试时间：100分钟） 专业： 计算机专业 班级： 序号： 姓名： 注意：所有答案都必须写在答题纸上！！！ 三．简答（每小题10分，共50分） 1．有如图所示的有向图，请给出该图的: 1) 邻接矩阵表示； 2) 逆邻接表表示。 2．假定存在数据表：（3，4，5，7，24，30，54，63，72，87，95，102），请解决如下问题： 1) 假设哈希函数为：H(key)=key mod 13，用该哈希函数将数据表存入长度为13 的哈希表，（利用线性探测）请画出存放状态； 2) 请按比较顺序写出查找102的过程中比较的数值，以及比较的次数； 3．请写出对序列{21，25，49，28，16，22，25，38}的二叉排序树构造过程。

4．试利用Dijkstra算法求图中从顶点a到其他各顶点间的最短路径，写出执行算法过程中各步的状态。 5．如果一个项目由10个主要任务构成，其计划图展示了任务之间关系与任务所需天数，则项目关键路径如何求解，请展示其过程。 四．算法（10分，共10分） 请写出折半查找方法的函数Search_Bin( SSTable S, value v)。 要求： 1）函数名使用给出的函数名，参数SSTable 表示序列，使用一维数组存放，下标从0开始，value 表示要查找的值； 2）如果找到，则函数返回值为该数在序列中的位置，否则返回负1； 3）不用写出主函数与相关定义，如果使用其他函数，请注明函数用途。

计算机学院2010-2011学年第一学期 《数据结构》答题纸（A卷）一．填空（2*20=40分）

东北大学数据结构实验报告

实验报告 课程名称：数据结构班级：实验成绩： 实验名称：顺序表和链表的应用学号：批阅教师签字： 实验编号：实验一：实验日期：2017-11-25 指导教师：组号：实验时间：18:30~22:30 一、实验目的 （1）掌握线性表的基本操作（插入、删除、查找）以及线性表合并等运算在顺序存储结构、链式存储结构上的实现。重点掌握链式存储结构实现的各种操作。 （2）掌握线性表的链式存储结构的应用。 二、实验容与实验步骤 （1）实验容： 实现约瑟夫环，约瑟夫环（Joseph）问题的一种描述是：编号为1、2、3……n的n个人按照顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数的上限值m，从第一个人开始按照顺时针的方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他的顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。设计一个程序求出出列顺序。 （2）抽象数据类型和设计的函数描述，说明解决设想。 首先定义一个链表，用其中的data项存储每个人的编号，用password项存储每个人所持有的密码，并且声明一个指针。之后使用CreatList_CL函数来创建一个循环链表，在其中的data和password中存入编号和密码，最后使最后一个节点的next指向L，使其能够形成循环队列。定义了函数Display来显示链表当中的容，以确定存储的数据没有错误。定义了函数Delete_L来实现约瑟夫环中依次删除的功能，依次比较，如果某个人所持的密码和m 值相等，则删除这个结点，并且输出此时该结点的编号和密码，实现出列的功能。 （3）简短明确地写出实验所采用的存储结构，并加以说明。 该实验我主要采用的是线性表的链式存储结构，首先定义了链表的结构，其中包括data 项和password项，分别存储每个人的编号和所持密码，还声明了指向下一个结点的指针，该指针可以连接各个结点，并且将最后一个结点的指针指向第一个结点使之成为一个循环链表。 三、实验环境 操作系统：Windows 7 调试软件名称：Visio Studio2017 上机地点：信息楼B405 四、实验过程与分析 （1）主要的函数或操作部的主要算法，分析这个算法的时、空复杂度，并说明设计的巧妙之处。

东北大学 大学物理作业题

2011 ~2012学年第二学期大学物理（上）作业题 第1章作业：选择填空题1~4；计算题：9，13，14，17，24 附加题 1-1 已知一质点的运动方程为：j t A i t A r )sin ()cos (21ωω+=（SI ） ，其中A 1 、A 2、ω均 为正的常量，且A 1 >A 2 ，证明 ：（1）质点的运动轨迹为一椭圆； （2）质点的加速度恒指向椭圆中心。 1-2 已知质点沿x 轴运动，其加速度和坐标的关系为 a = 2+6x 2 (SI)，且质点在 x = 0 处的 速率为10m/s ，求该质点的速度v 与坐标x 的关系。 第2章作业：选择填空题1~5；计算题：14，18，21，22 附加题 2-1 一质点在力)25(5t m F -=(SI)作用下，从静止开始（t=0）沿x 轴作直线运动， 其中m 为质点的质量，t 为时间，求：（1）该质点的速度v 与时间t 的关系； （2）该质点的的运动学方程． 2-2 质量为m 的质点以初速度v 0沿x 轴作直线运动，起始位置在坐标原点处，所受阻力与 其速率成正比，即：kv F -=，式中k 为正常数， 求：（1）该质点的速度v 与时间t 的关系；（2）该质点的的运动学方程． 第3章作业：选择填空题1~5；计算题：8，20，21，27，32 附加题 3-1 质量为m =2kg 的质点从静止出发沿直线运动，受力i t F 12=(F 以N 为单位，t 以s 为单位)， 求在前3s 内，该力作多少功？ 3-2 质量为m =0.5kg 的质点，在XOY 平面内运动，其运动方程为 x =5t ，y =0.5t 2(SI)， 求从t=2s 到t=4s 这段时间内，合力对质点所作的功为多少？ 3-3 一质量为m 的物体，从质量为M 的圆弧形槽顶端由静止滑下，设圆弧形槽的半径为R ， 张角为π/2，如图所示，所有摩擦均忽略，求： （1）物体刚离开槽底端时，物体和槽的速度各是多少？ （2）在物体从A 滑到B 的过程中，物体对槽所做的功为多少？ 第4章作业：选择填空题1~4；计算题：13，21，27，31 附加题 4-1 质量分别为m 和2m ，半径分别为r 和2r 的两个均质圆盘， 同轴地粘在一起，可绕通过盘心且垂直于盘面的水平 光滑轴转动，在大小盘边缘都绕有细绳，绳下端都挂 一质量为m 的重物，盘绳无相对滑动，如图所示， 求：1) 圆盘对水平光滑轴的转动惯量； 2) 圆盘的角加速度。 4-2 一根长为 l ，质量为 M 的均质细杆，其一端挂在一个 光滑的水平轴上，静止在竖直位置。有一质量为m 的子弹 以速度v 0从杆的中点穿过，穿出速度为v ， 求：1）杆开始转动时的角速度； 2）杆的最大摆角。 4-3 一半圆形均质细杆，半径为R ，质量为M ， 求半圆形均质细杆对过细杆二端AA`轴的转动惯量． 第14章作业：选择填空题1~4；计算题：15，16，17，20，24 附加题