选择题
1.在数据结构中，与所使用的计算机无关的是数据的（A逻辑）结构。A逻辑B存储C逻辑和存储D物理
2.下面程序段的时间复杂度是（O（Log3n））
i = 0;
while(i<=n)
i = i*3;
3.链表不具有的特点是（A可随机访问任一结点）
A可随机访问任一结点B插入删除不需要移动元素
C不必上划线估计储存空间D所需空间与其长度成正比
4.需要分配较大的空间，插入和删除不需要移动元素的线性表，其存储结构是（B静态链表）
A单链表B静态链表C线性链表D顺序存储结构5.在一个长度为n（n>1）的单链表上，没有头和尾两个指针，执行（B）操作与链表的长度有关。
A删除单链表中的第一个元素
B删除单链表中的最后一个元素
C在单链表第一个元素前插入一个新元素
D在单链表最后一个元素后插入一个新元素
6.如果对线性表的操作只有两种，即删除第一个元素，在最后一个元素的后面插入新元素，则最好使用（B）
A只有表头指针没有表尾指针的循环单链表
B只有表尾指针没有表头指针的循环单链表
C非循环双链表
D循环双链表
7.对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为（C）尾指针和头指针在单链表中的区别
A顺序表B用头指针表示的循环单链表C用尾指针表示的循环单链表D单链表
8．向一个栈顶指针为h的带头结点的链栈中插入s所指的结点时，（D）操作。我觉得选A
A h->next=s
B s->next=h
C s->next=h;h=s D
s->next=h->next;h->next=s
9.若栈采用顺序存储方式存储，现两栈共享空间V[1 m]，top[1],top[2]分别代表第一和第二个栈顶，栈一的底在V[1],栈二的底在V[m]，则栈满的条件是（B）
A |top[2]-top[1]|=0
B top[1]+1=top[2]
C top[1]+top[2]=m
D top[1]=top[2]
10.用不带头结点的单链表存储队列，其头指针指向队头结点，尾指针指向队尾结点，则在进行出队操作时（C）
A仅修改队头指针B仅修改队尾指针C队头、队尾指针都可能要修改D队头、队尾指针都要
11．数组A中，每个元素的长度为3个字母，行下标i从1到8，列
下标j从1到10，从首地址SA开始连续存放的存储器内，该数组按行存放，元素A[8][5]的其实地址是（C）
A SA+141
B SA+144
C SA+222
D SA+225
12.若声明一个浮点数数组如下：froat average[]=new float[30];假设该数组的内存起始位置为200，average[15]的内存地址是（C）
A 214
B 215
C 260
D 256
13.设二维数组A[1……m，1……n]按行存储在数组B中，则二维数组元素A[i,j]在一维数组B中的下标为（A）
A n*（i-1）+j
B n*（i-1）+j-1
C i*(j-1)
D j*m+i-1
14.有一个100X90的稀疏矩阵，非0元素有10，设每个整型数占两个字节，则用三元组表示该矩阵时，所需的字节数是（B）
A 20
B 66
C 18000
D 33
15.数组A[0……4，-1……-3,5……7]中含有的元素个数是（A）
A 55
B 45
C 36
D 16
16.设有一个10阶的对称矩阵A，采用压缩存储方式，一行序为主存储，a1-1为第一个元素，其存储地址为1，每个元素占1个地址空间，则a8-5的地址为（B）
A 13
B 33
C 18
D 40
17.稀疏矩阵一般的压缩存储方式有两种，即（C）三元组和十字链表
A 二维数组和三维数组
B 三元组和散列
C 三元组和十字链表
D 散列和十字链表
18.若一颗二叉树具有10个度为2的结点，5个度为一的结点，则度
为0的结点的个数为（B）
A 9
B 11
C 15
D 不能确定
19.某二叉树结点的中序序列为ABCDEFG，后序序列为BDCAFGE，则其左子树中结点数目为（C）
A 3
B 2
C 4
D 5
20.采用折半查找长度为n的线性表时，每个元素的平均查找长度为（D）
A O（n的平方）ＢＯ（ｎｌｏｇ２ｎ）ＣＯ（ｎ）
ＤＯ（ｌｏｇ２ｎ）
21.查找效率最高的二叉排序树是（平衡二叉树）
22.堆是一种有用的数据结构，下列关键码序列（D）是一个堆
A 94,31,53,23,16,72
B 94，53,31,72,16,23
C 16,53,23,94,31,72
D 16,31,23,94,53,72
23.堆排序是一种（B）
A插入 B 选择 C 交换 D 归并
24.（D）在链表中进行操作比在顺序表中进行操作效率高
A 顺序查找B折半查找C分块查找 D 插入
25．直接选择排序的时间复杂度为（D）（n为元素个数）
A O（n）
B O（ｌｏｇ２ｎ）
C O（nｌｏｇ２ｎ）
D O（n平方）
填空题
26.数据逻辑结构包括（线性结构）（树形结构）和（图状结构）种类型，树形结构和图状结构合称为（非线性结构）。
27.线性结构中元素之间存在（一对一）关系，树形结构中元素之间存在（一对多）关系，图形结构中元素之间存在（多对多）关系。28.数据结构的基本存储方法是（顺序）（链式）（索引）和（散列）存储
29.衡量一个算法的优劣主要考虑（正确性）（可读性）（健壮性）和（时间复杂度）与（空间复杂度）
30.算法的五个重要特性是（有穷性）（确定性）（可行性）（输入）和（输出）
31.在一个长度为n的顺序表中删除第i个元素时，需向前移动（n-i-1）个元素。
32.在双链表中，每个结点有两个指针域，一个指向（前驱结点），另一个指向（后继结点）
33.根据线性表的链式存储结构中每个结点包含的指针个数，将线性链表分成（单链表）和（双链表）
34.顺序存储结构是通过（下标）表示元素之间的关系的，链式存储结构是通过（指针）表示元素之间的关系的
35.空串是（零个字符的串），其长度等于（零），空白串是（由一个或多个空格字符组成的串），其长度等于（其包含的空格个数）
36.组成串的数据元素只能是（单个字符）
37.二维数组M的每个元素是6个字符组成的串，行下标i的范围从0到8，列下标j的范围从1到10，则存放M至少需要（540）个字节，M的第8列和第5行共占（108）个字
38.广义表（（a），（（b），c），（（（d））））的长度是（3）深度是（4）
39.在一棵二叉树中，度为零的结点的个数为n0，度为2的结点个数为n2，则有n0=（n2+1）
40.一颗有n叶子结点的哈夫曼树中共有（2n-1）个结点
41.若二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点个数为（69）
42.某二叉树的前序遍历序列为abdgcefh，中序序列是dgbaechf，其后序序列为（gbdehfca）
43.线索二叉树的左线索指向其（遍历序列中的前驱），右线索指向（其遍历序列中的后继）
44.在分块索引查找方法中，首先查找（索引表），然后查找相应的（块表）
第1章绪论 一、选择题 1. 算法的计算量的大小称为计算的（）。 2. 算法的时间复杂度取决于（） 3.计算机算法指的是（），它必须具备（）这三个特性。 4．一个算法应该是（）。 5. 下面关于算法说法错误的是（） A．算法最终必须由计算机程序实现 B.为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的 6. 下面说法错误的是（） (1）算法原地工作的含义是指不需要任何额外的辅助空间 （2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法 （3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 （4）同一个算法，实现语言的级别越高，执行效率就越低 A．(1) B.(1),(2) C.(1),(4) D.(3) 7．从逻辑上可以把数据结构分为（）两大类。 A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构 8．以下与数据的存储结构无关的术语是（）。 A．循环队列 B. 链表 C. 哈希表 D. 栈 9．以下数据结构中，哪一个是线性结构（）？ A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串
10．以下那一个术语与数据的存储结构无关？（） A．栈 B. 哈希表 C. 线索树 D. 双向链表11．在下面的程序段中，对x的赋值语句的频度为（） FOR i:=1 TO n DO FOR j:=1 TO n DO x:=x+1; A． O(2n) B．O(n) C．O(n2) D．O(log2n) 12．程序段 FOR i:=n-1 DOWNTO 1 DO FOR j:=1 TO i DO IF A[j]>A[j+1] THEN A[j]与A[j+1]对换； 其中 n为正整数，则最后一行的语句频度在最坏情况下是（） A. O（n） B. O(nlogn) C. O(n3) D. O(n2) 13．以下哪个数据结构不是多型数据类型（） A．栈 B．广义表 C．有向图 D．字符串 14．以下数据结构中，（）是非线性数据结构 A．树 B．字符串 C．队 D．栈 15. 下列数据中，（）是非线性数据结构。 A．栈 B. 队列 C. 完全二叉树 D. 堆 16．连续存储设计时，存储单元的地址（）。 A．一定连续 B．一定不连续 C．不一定连续 D．部分连续，部分不连续17．以下属于逻辑结构的是（）。 A．顺序表 B. 哈希表 C.有序表 D. 单链表 二、判断题
1. 填空题 (1) 顺序栈s的数据存储在数组element中，则栈满的条件是____________,栈空的条件是。 (2) 顺序栈ｓ进行出栈操作后，要执行的语句是top____。s进行进栈操作前，要执行的语句是top______运算。 (3) 元素进入队列的一端是____________；队列出队的一端是____________。 (4)顺序队列q满的条件是，顺序队列q空的条件 是。 (5) 空串的长度等于，非空串的长度等于。 2. 选择题 (1) 串是一种特殊的线性表，其特征体现在_____。 A. 可以顺序存储 B. 数据元素是一个字符 C. 可以链接存储 D. 数据元素可以是多个字符 (2) 栈是限定在__________处进行插入或删除操作的线性表。 A. 端点 B. 栈底 C. 栈顶 D. 中间 (3) 在栈顶一端可进行的全部操作是___________。 A. 插入 B.删除 C. 插入和删除 D. 进栈 (4) 4个元素按A、B、C、D顺序连续进S栈，进行x=pop()运算后，x的值是___________, 栈顶元素的值是. A. A B. B C. C D. D (5) 栈的特点是__________。 A. 先进先出 B. 后进先出 C. 后进后出 D. 不进不出 (6) 顺序栈存储空间的实现使用___________。 A. 链表 B. 数组 C.循环链表 D. 变量 (7) 一个顺序栈一旦说明，其占用空间的大小___________。 A. 已固定 B. 可以改变 C. 不能固定 D. 动态变化 (8) 栈与一般线性表的区别主要在___________方面。 A. 元素个数 B. 元素类型 C. 逻辑结构 D. 插入、删除元素的位置 (9) 栈s经过下列运算后s.get()的值是___________, s.isEmpty( )的值是___________。 s.push(a);s.push(b);s.pop(); A. a B. b C. 1 D. 2
2014年上半年数据结构（C++）第一次作业 一.单项选择题(20分) 1.已知一棵二叉树的前序遍历序列为ABCDEFG，则其中序遍历可能是____b____。 a、CABDEFG b、ABCDEFG c、DACEFBG d、ADCFEGB 2.设一个链表最常用的操作是在末尾插入结点和删除尾结点，则采用__b______存储方式最节 省时间（假设链表仅设有一个first指针一个）。 a. 单链表 b. 带头结点的双循环链表 c. 单循环链表 d. 双链表 3.有6个元素6,5,4,3,2,1顺序入栈，则所得到的输出序列不可能是___c____。 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 4.链表不具有的特点是__d___。 a．插入,删除不需要移动元素 b．所需空间与线性长度成正比 c．不必事先估计存储空间 d．可随机访问任一元素 5.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂 度为_____c____。(1≤i≤n+1) a、O(0) b、O(1) c、O(n) d、O(n2) 6.对于一个头指针为head的带头结点的单链表，该表为空表的条件是__a____为真值； a. head->next==NULL; b. head==NULL; c. head->next==head; d. head!=NULL; 7.用数组A[0..N-1]存放一个循环队列，一元素出队时，其队头指针front的修改方法是 ___a____： a. front = (front + 1) mod N; b. front = (front - 2)mod N; c. front = front + 1; d. front = front – 2; 8.若用Head()和Tail()分别表示取广义表的表头和表尾，广义表A=（1,2,(3,4),(5,(6,7))），则 Head(Tail(Head(Tail(Tail(A))))) b 。 a. 1 b. 4 c. () d. （4） 9.设关于串的叙述中，哪一个是不正确的？___b_____ a. 串是字符的有限序列 b. 空串是由空格构成的串 c. 模式匹配是串的一种重要运算 d. 串既可以采用顺序存储，也可以采用链式存储 10.链下列排序算法中时间复杂度不受数据初始状态影响，恒为O(n2)的是____c____。 a.堆排序 b.起泡排序 c.直接选择排序 d.快速排序 二.填空作图题（共56分）： 1.设 n是偶数，且有程序段： for(i=1; i<=n; i++) { if(2*i <= n) { for(j = 2* i; j<=n;j++)
第七章图：习题 习题 一、选择题 1．设完全无向图的顶点个数为n，则该图有( )条边。 A. n-l B. n(n-l)/2 C.n(n+l)/2 D. n(n-l) 2．在一个无向图中，所有顶点的度数之和等于所有边数的( )倍。 A.3 B.2 C.1 D.1/2 3．有向图的一个顶点的度为该顶点的( )。 A.入度 B. 出度 C.入度与出度之和 D.(入度+出度)/2 4．在无向图G (V，E)中，如果图中任意两个顶点vi、vj (vi、vj∈V，vi≠vj)都的，则称该图是( )。 A.强连通图 B.连通图 C.非连通图 D.非强连通图 5．若采用邻接矩阵存储具有n个顶点的一个无向图，则该邻接矩阵是一个( )。 A.上三角矩阵 B.稀疏矩阵 C.对角矩阵 D.对称矩阵 6．若采用邻接矩阵存储具有n个顶点的一个有向图，顶点vi的出度等于邻接矩阵 A.第i列元素之和 B.第i行元素之和减去第i列元素之和 C.第i行元素之和 D.第i行元素之和加上第i列元素之和 7．对于具有e条边的无向图，它的邻接表中有( )个边结点。 A.e-l B.e C.2(e-l) D. 2e 8．对于含有n个顶点和e条边的无向连通图，利用普里姆Prim算法产生最小生成时间复杂性为( )，利用克鲁斯卡尔Kruskal算法产生最小生成树（假设边已经按权的次序排序），其时间复杂性为( )。 A. O(n2) B. O(n*e) C. O(n*logn) D.O(e) 9．对于一个具有n个顶点和e条边的有向图，拓扑排序总的时间花费为O( ) A.n B.n+l C.n-l D.n+e 10．在一个带权连通图G中，权值最小的边一定包含在G的( )生成树中。 A.最小 B.任何 C.广度优先 D.深度优先 二、填空题 1．在一个具有n个顶点的无向完全图中，包含有____条边；在一个具有n个有向完全图中，包含有____条边。 2．对于无向图，顶点vi的度等于其邻接矩阵____ 的元素之和。 3．对于一个具有n个顶点和e条边的无向图，在其邻接表中，含有____个边对于一个具有n个顶点和e条边的有向图，在其邻接表中，含有_______个弧结点。 4．十字链表是有向图的另一种链式存储结构，实际上是将_______和_______结合起来的一种链表。 5．在构造最小生成树时，克鲁斯卡尔算法是一种按_______的次序选择合适的边来构造最小生成树的方法；普里姆算法是按逐个将_______的方式来构造最小生成树的另一种方法。 6．对用邻接表表示的图进行深度优先遍历时，其时间复杂度为一；对用邻接表表示的图进行广度优先遍历时，其时间复杂度为_______。 7．对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数为_______ ，边数为_______。 8．在执行拓扑排序的过程中，当某个顶点的入度为零时，就将此顶点输出，同时将该顶点的所有后继顶点的入度减1。为了避免重复检测顶点的入度是否为零，需要设立一个____来存放入度为零的顶点。
一、定义与术语 图：无序数据结构 基本构成：1.边集（Edge ）：a. 有向图，有向边
1判断题 （对）1. 数据的逻辑结构与数据元素本身的内容和形式无关。 （错）2. 线性表的逻辑顺序与物理顺序总是一致的。 （对）3. 若有一个叶子结点是二叉树中某个子树的前序遍历结果序列的最后一个结点，则它一定是该子树的中序遍历结果序列的最后一个结点。 （错）4. 对于同一组待输入的关键码集合，虽然各关键码的输入次序不同，但得到的二叉搜索树都是相同的。 （对）5. 最优二叉搜索树的任何子树都是最优二叉搜索树。 （对）6. 在二叉搜索树上插入新结点时，不必移动其它结点，仅需改动某个结点的指针，使它由空变为非空即可。 （对）7. 有n（n≥1）个顶点的有向强连通图最少有n条边。 （错）8. 连通分量是无向图中的极小连通子图。 （错）9. 二叉树中任何一个结点的度都是2。 （错）10. 单链表从任何一个结点出发，都能访问到所有结点。 二、单选题 1 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（ B ）个元素。 A．8 B. 63.5 C. 63 D. 7 2 设有一个二维数组A[m][n]，假设A[0][0]存放位置在644（10），A[2][2]存放位置在676（10），每个元素占一个空间，则A[3][3]在（ A ）位置，（10）表明用10进数表示。 A．692（10） B. 626（10） C. 709（10） D. 724（10） 3 N个顶点的连通图至少有（ A ）条边。 A．N－1 B. N C. N＋1 D. 0 4 下面程序的时间复杂度为（ C ）。 for(int i=0; i
/* *题目：编写按键盘输入的数据建立图的邻接矩阵存储 * 编写图的深度优先遍历程序 * 编写图的广度优先遍历程序 * 设计一个选择式菜单形式如下： * 图子系统 * *********************************** * * 1------更新邻接矩阵* * * 2------深度优先遍历* * * 3------广度优先遍历* * * 0------ 返回* * *********************************** * 请选择菜单号（0--3）： */ #include
第8章 图 8-1 画出1个顶点、2个顶点、3个顶点、4个顶点和5个顶点的无向完全图。试证明在n 个顶点的无向完全图中，边的条数为n(n-1)/2。 【解答】 【证明】 在有n 个顶点的无向完全图中，每一个顶点都有一条边与其它某一顶点相连，所以每一个顶点有 n-1条边与其他n-1个顶点相连，总计n 个顶点有n(n-1)条边。但在无向图中，顶点i 到顶点j 与顶点j 到顶点i 是同一条边，所以总共有n(n-1)/2条边。 8-2 右边的有向图是强连通的吗？请列出所有的简单路径。 【解答】 点，它不是强连通的有向图。各个顶点自成强连通分量。 所谓简单路径是指该路径上没有重复的顶点。 从顶点A 出发，到其他的各个顶点的简单路径有A →B ，A →D →B ，A →B →C ，A →D →B →C ，A →D ，A →B →E ，A →D →E ，A →D →B →E ，A →B →C →F →E ，A →D →B →C →F →E ，A →B →C →F ，A 1个顶点的 无向完全图 2个顶点的 无向完全图 3个顶点的 无向完全图 4个顶点的 无向完全图 5个顶点的 无向完全图 A D
????????? ?????? ?????=01 00000001001010000 010*********Edge →D →B →C →F 。 从顶点B 出发，到其他各个顶点的简单路径有B →C ，B →C →F ，B →E ，B →C →F →E 。 从顶点C 出发，到其他各个顶点的简单路径有C →F ，C →F →E 。 从顶点D 出发，到其他各个顶点的简单路径有D →B ，D →B →C ，D →B →C →F ，D →E ，D →B →E ，D →B →C →F →E 。 从顶点E 出发，到其他各个顶点的简单路径无。 从顶点F 出发，到其他各个顶点的简单路径有F →E 。 8-3 给出右图的邻接矩阵、邻接表和邻接多重表表示。 【解答】 (1) 邻接矩阵 A D
一.填空题 1. _集合__、线性结构、__树形结构____ 、图形结构 2.p->next!=NULL 3.时间复杂度和空间复杂度 4.随机存取 5..队尾 6. n-1 二、单选题、 1-5DAACC 6-10DBDDB 11-15DCABD 三，简答题 1、
2、数据是对客观事物的描述形式和编码形式的统称，是算法和程序的处理对象和计算结构。数据元素又称数据结点，简称结点，通常一个数据结点由用来描述一个独立事的名称、数量、特性、性质的一组相关信息。多数情况下，一个结点包含有多个数据项，每个数据项是结点的一个域，能够用来唯一标识结点的域称为关键字域。 算法：有穷规则的集合，而规则规定了解决某一特定问题的运算序列。 有穷性：必须在执行有穷步后终止。 确定性：每一步必须具有确定的定义，不能含糊不清，不带二义性。 可行性：所有运算都可以精确地实现。 输出数据：必须有输出数据，包括输出某种动作或控制信号。 输入数据：作为执行前的初始量。不是必须。 算法有两种表现形式：描述形式和程序形式。 计算时间复杂的的方法： ?支配性语句度量法：在一段程序中，往往有一条语句执行次数最多，话费时间也就是最多，其他语句执行次数的和将不超过这套语句执行次数的常数倍，那么就称这条语句在话费时间上是起支配性作用的典型语句，于是可选这条语句的执行次数作为度量这段程序花费时间的阶。 ? 四、应用题
1、 2、、对给定的n个权值bai{W1,W2,W3,...,Wi,...,Wn}构成n棵二叉树的初始集合F= {T1,T2,T3,...,Ti,...,Tn}，其中du每棵二叉树Ti中只有一个权值zhi为Wi的根结点， 它的左右子树均为空。（为方便在计算机上实现算法，一般还要求以Ti的权值Wi的 升序排列。）二、在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点的权值为其左右子树的根结点的权值之和。三、从F中删除这 两棵树，并把这棵新的二叉树同样以升序排列加入到集合F中。四、重复二和三两步，直到集合F中只有一棵二叉树为止。 树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL WPL=∑Wi*Li (i=1到n) WPL=(2+4)*3+(6+8+10)*2 =66
《数据结构》形成性考核册第1次作业参考答案第一章绪论 一、填空题 1、数据操作 2、集合结构线性结构 树型结构图形结构 3、引用类型 4、1：1 1：n n：m 5、不对 6、多个 7、O（m*n） 8、时间复杂度 空间复杂度 9、顺序链接索引散列 10、O（n2） 11、O（n） 12、O（n）O（m*n） 二、选择题1~8：DBABADDD 三、应用题 （1）功能：判断n是否是一个素数，若是则返回数值1，否则返回0。时间复杂度：O（n）。 （2）功能：计算S=1！+2！+…+n!的值。时间复杂度：O（n）。 （3）功能：计算S=1！+2！+…+n!的值。时间复杂度：O（n2）。 （4）求出满足不等式1+2+…+i≥n的最小i值。O（n）。 第二章线性表 四、填空题 1、A[P-1] 2、108 3、前驱后继 4、最后一个表头 5、p->next=q->next q->next=p 6、HL->next=NULL HL->next=HL 7、P->next 8、Q->next 9、P->next s 10、从前向后前移n-i 11、O（1）O（n） 12、（n+1）/2 13、O（n）O（1） 14、A[P].next 15、a[j].next=a[i].next a[i].next=j 16、数据值指针 五、选择题1~5：BDDBC 六、应用题 1、（1）、（79，62，34，57，26，48）（2）、（26，34，48，57，62，79）（3）、（48，56，57，62，79，34）（4）、（56，57，79，34） （5）、（26，34，39，48，57，62） 2、（1）将类型为List的线性表L中第i个元素移至表尾位置的算法，L中的元素类型为ElemType，假定不需要对i的值进行有效性检查。 void move (List& L, int i) { ElemType x=L.list[ i-1]; for(int j=i; j 习题练习第一章绪论 1、void maxtrixmult (int n,int a[][100],int b[][100],intc[][100]) { int j,k,r; int x; for(r=0;r<=n;r++) 1) n+2 { for (j=0;j<=n;j++) 2) (n+1)*(n+2) { x=0; 3) (n+1)2 for(k=1；k<=n;k++) 4) (n+1)3 x+=a[r][k]*[k][j]; 5) n* (n+1)2 c[r][j]=x; 6) (n+1)2 } } } 计算时间每条语句的频度和该算法的时间复杂度 2．一个算法应该是（ B ）。【中山大学 1998 二、1（2分）】 A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C. 4．从逻辑上可以把数据结构分为（ C ）两大类。【武汉交通科技大学 1996 一、4（2分）】 A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构 5．以下与数据的存储结构无关的术语是（ D ）。【北方交通大学 2000 二、1 （2分）】 A．循环队列 B. 链表 C. 哈希表 D. 栈 6．连续存储设计时，存储单元的地址（ A ）。【中山大学 1999 一、1（1分）】A．一定连续 B．一定不连续 C．不一定连续 D．部分连续，部分不连续 7. 数据元素是数据的最小单位。( F ) 【北京邮电大学 1998 一、1（2分）】【青岛大学 2000 一、1 （1分）】 【上海交通大学 1998 一、1】【山东师范大学 2001 一、1 （2分）】 第二章线性表 1．线性表是具有n个（ C ）的有限序列（n>0）。【清华大学 1998 一、 4（2分）】 A．表元素 B．字符 C．数据元素 D．数据项 E．信 息项 第一章 单选题 1、下列关于算法的基本特征，说法不正确的是（）。能行性是算法中的每一个步骤必须能够实现且能达到预期的目的。算法的确定性是指算法中的每一个步骤必须是有明确的定义，不允许模棱两可。 算法的有穷性是指算法必须能在有限的时间内做完。算法与提供情报无关。 [D] 教师批改：D 2、算法的时间复杂度取决于（）。问题的规模待处理的数据的初态 问题的难度 A 和B [D] 教师批改：D 3、下列选项中，不是算法基本特征的是（）。可行性有穷性 确定性高效率 [D] 教师批改：D 4、通常一个好的算法应达到的目标中，不包括（）。正确性可读性 技巧性健壮性 [C] 教师批改：C 5、在一般的计算机系统中，基本的运算和操作不包括（）。语法处理算术运算 关系运算数据传输 [A] 教师批改：A 6、工程上常用的分治法是（）。列举法归纳法 减半递推技术回溯法 [C] 教师批改：C 多选题 7、算法设计的要求包括（）。 正确性可读性 健壮性唯一性 [ABC] 教师批改：A，B，C 8、算法的时间复杂度应该与（）无关。 所使用的计算机程序设计语言 基本运算的执行次数程序编制者 [ABD] 教师批改：A，B，D 9、下列关于算法的描述中，不正确的有（）。 算法即是计算机程序算法是解决问题的计算方法 算法是排序方法算法是解决问题的有限运算序列 [ABC] 教师批改：A，B，C 填空题 16、所谓算法是指（）。 教师批改：解题方案的准确而完整的描述 17、算法的基本特征有（）、（）、（）和（） 教师批改：能行性、确定性、有穷性和拥有足够的情报。 18、一个算法通常由两种基本要素组成，它们是（）和（）。 教师批改：算法中对数据的运算和操作。 算法的控制结构。 19、工程上常用的几种算法设计方法有列举法、（）、（）、（）、（）和回溯法。 教师批改：归纳法、递推、递归、减半递推技术。 20、算法的复杂度主要包括（）复杂度和（）复杂度。 教师批改：时间、空间 综合题 21、设给定3个整数a，b，c，试写出寻找这3个整数的中数的算法；并分析在平均情况与最坏情况下，该算法分别要做多少次比较？ 寻找这3个整数的中数的算法用C语言描述如下（中数m由函数值返回）： int mid ( int a, int b, int c) { int m 。m=a 。 if ( m>=b ) { if (m>=c) { if ( b>=c ) m=b 。else m=c 。} } else { if ( m<=c) { if (b>=c) m=c。else m=b 。} } return ( m ) 。 } 假设a，b，c中的每一个数为中数的概率相等（均为1/3）。由于当a为中数时需要比较2次，b或c为中数时均需要比较3次，因此，在平均情况下上述算法所需要的比较次数为 2*（1/3）+3*（1/3）+3*（1/3）= 8/3 即在平均情况下，上述算法需要比较8/3次。 在最坏情况下，上述算法需要比较3次（当b或c为中数时）。 第二章 选择题 1、下列排序方法中，哪一个是稳定的排序方法（）。归并排序稀尔排序 堆排序快速排序 [A] 教师批改：A 2、设输入序列为1，2，3，4，借助一个栈得到的输出序列可以是（）。3，4，1，2 4，2，1，3 4，1，2，3 1，3，4，2 [D] 教师批改：D 3、用数组A[m]存放循环队列的元素值，若其头尾指针分别为front和rear，则循环队列中当前元素的个数为（）。(rear+front)%m (rear-front+m)%m (rear-front)%m (rear-front+1)%m [D] 教师批改：B 4、对于下三角矩阵A，若采用一个一维数组B以行为主顺序存放压缩矩阵A，则A43存放在（）中. B7 B8 B9 B10 [C] 教师批改：C 5、深度为5的二叉树至多有（）个结点。16 32 #include 《数据库应用技术》第1次作业及答案 第一章思考与练习题 一、选择题 1．三级模式间存在两种映射，它们是（C）。 A．模式与子模式间，模式与内模式间 B．子模式与内模式间，外模式与内模式间 C．外模式与模式间，模式与内模式间 D．模式与内模式间，模式与模式间 2．SQL Server系统中的所有系统级信息存储于哪个数据库（A ）。 A．master B．model C．tempdb D．msdb 3．下面关于tempdb数据库描述不正确的是（D ）。 A．是一个临时数据库B．属于全局资源 C．没有权限限制D．是用户建立新数据库的模板 4．在数据库技术中，面向对象数据模型是一种（B ）。 A．概念模型B．结构模型 C．物理模型D．形象模型 5．数据库管理系统常见的数据模型有（B）。 A．网状、关系和语义 B．层次、关系和网状 C．环状、层次和关系 D．网状、链状和层次 6．用户看到的数据表，属于数据库系统三级模式中的（D ）。 A．外模式 B．内模式 C．子模式 D．模式 7．对数据的插入属于数据库管理系统（B ）的功能。 A．数据定义 B．数据操纵 C．数据库的运行管理 D．数据库的建立和维护 8．保持数据的完整性属于数据库管理系统（C ）的功能。 A．数据定义 B．数据操纵 C．数据库的运行管理 D．数据库的建立和维护 9．在SQL Server数据库中，默认情况下Sys通常是（C ）。 A．数据文件的后缀 B．事务日志文件的后缀 C．系统表表名的前缀 D．辅助文件的后缀 二、填空题 1．计算机数据处理技术大致经历了（人工管理）、（文件管理）、（数据库管理）等不同的发展阶段。 2．数据库系统由（外模式）、（模式）和（内模式）三级抽象模式构成。 3．数据库管理系统的主要功能包括（数据定义）、（数据操纵）、（数据库的运行管理）、（数据库的建立和维护）。 4．关系模型由三部分组成（数据结构）、（关系操作集合）和（关系的完整性）。 实验六图的应用及其实现 （相关知识点：拓扑排序、关键路径、最小生成树和最短路径） 一、实验目的 1．进一步功固图常用的存储结构。 2．熟练掌握在图的邻接表实现图的基本操作。 3．理解掌握AOV网、AOE网在邻接表上的实现以及解决简单的应用问题。 二、实验内容 一>.基础题目：(本类题目属于验证性的，要求学生独立完成) [题目一]：从键盘上输入AOV网的顶点和有向边的信息,建立其邻接表存储结构,然后对该图拓扑排序,并输出拓扑序列. 试设计程序实现上述AOV网的类型定义和基本操作,完成上述功能。 测试数据：教材图7.28 [题目二]：从键盘上输入AOE网的顶点和有向边的信息,建立其邻接表存储结构,输出其关键路径和关键路径长度。试设计程序实现上述AOE网类型定义和基本操作,完成上述功能。 测试数据：教材图7.29 二>.简单应用题目：（ACM/ICPC训练题，本类题目属于设计性的，要求学生三人为一个团队，分工协作完成)） 【题目三】高速公路 描述 某国共有n个城市（n不超过200），有些城市之间直接有一条高速公路相连，高速公路都是双向的，总共有m条。每条高速公路都有自己的载重限制，即载重最大值。通过车辆的载重不能超过公路的载重限制。如今我们想了解的是，从某一起点城市出发，到达目标城市，车辆最多能带多重的货物。 输入 输入的第一行为两个整数n和m。以下有m行，每行三个整数描述一条公路，分别是首尾相连的城市以及载重限制。然后是一个整数k，即问题个数。接下来k行描述k个问题，每行两个整数表示起点城市和目标城市。问题数不超过一百。 输出 输出包括k行，每行对应一个问题，输出从起点到目标的最大载重量。如果两城市间无路径则输出-1。 样例输入 3 3 1 2 100 2 3 100 1 3 50 2 1 3 2 3 样例输出 100 100 【题目四】最短的旅程 描述 在Byteland有n个城市（编号从1到n），它们之间通过双向的道路相连。Byteland 的国王并不大方，所以，那里只有n -1条道路，但是，它们的连接方式使得从任意城市都可以走到其他的任何城市。 一天，starhder到了编号为k的城市。他计划从城市k开始，游遍城市m1，m2，m3……，mj（不一定要按这个顺序旅游）。每个城市mi都是不同的，并且，也与k不同。Starhder ——就像每一个旅行家一样，携带的钱总是有限的，所以，他要以最短的路程旅行完所有的城市（从城市k开始）。于是，他请你帮助计算一下，旅游完上述的城市最短需要多少路程。 输入 1.1 请说明算法具有哪些特性，各是什么含义？ 算法的一般性质包括：（1）通用性对于那些符合输入类型的任意输入数据,都能根据算法进行问题求解,包保证计算结构的正确性.（2）有效性组成算法的每一条指令都必须是能够被人或机器确切执行的.（3）确定性算法每执行一步之后,对于它的下一步,应该有明确的指示.即,保证每一步之后都有关于下一步动作的指令,不能缺乏下一步指令或仅仅含有模糊不清的指令.（4）有穷性算法的执行必须在有限步内结束. 1.2简述下列术语：数据、数据元素、数据对象、数据结构、存储结构、数据类 型和抽象数据类型。 数据：指所有能够输入到计算机中并被计算机程序处理的符号集合。数据元素（data element）：数据集合中的一个实体，是计算机程序中加工处理的基本单位。例如：一条学生记录（包括学号、姓名、年龄等）就是一个数据元素数据对象（data object）：性质相同的数据元素的集合。是数据的一个子集。数据结构(data structure)：相互之间存在一种或多种关系的数据元素的集合。即包括数据元素的集合和数据元素之间的关系的集合。存储结构：数据结构在计算机中的表示（也称映像）叫做物理结构。又称为存储结构。数据类型（data type）:是一个“值”的集合和定义在此集合上的“一组操作”的总称。抽象数据类型（abstract data type，简称ADT）：是指一个数学模型以及定义在此数学模型上的一组操作。1.3设n为正整数。试确定下列各程序段中前置以记号@的语句频度： (1) x=n; y=0; //n为不小于1的常数 while (x>=(y+1)*(y+1)) { @ y++; } n1/2向下取整 (2) i=1; j=0; while (i+j<=n) { @ if (i>j) j++; else i++; } n 注：@语句指的是if…else语句，语句频度为j++和i++执行的次数之和。 1.4请说明下列算法的时间复杂度。 (1) void sf1 (int n) { int i, x=0; for(i=1; i #include LinkList r = h->next; while(r != NULL) { printf("%d ",r->data); r = r->next; } putchar('\n'); } void InsertList(LinkList h, int x, int y) { LinkList s, p, q; s = new Lnode; s->data = y; q = h; p = q->next; while((p!=NULL) && (p->data != x)) { q = p; p = p->next; } s->next = p; q->next = s; } void DeleteList(LinkList h, int x) { LinkList p, q; q = h; p = q->next; while((p != NULL) && (p->data != x)) { q = p; p = p->next; } if(p == NULL) printf("no"); else { q->next = p->next; delete(p); printf("yes"); } } 数据结构教案第七章图 第7章图 【学习目标】 1．领会图的类型定义。 2．熟悉图的各种存储结构及其构造算法，了解各种存储结构的特点及其选用原则。 3．熟练掌握图的两种遍历算法。 4．理解各种图的应用问题的算法。 【重点和难点】 图的应用极为广泛，而且图的各种应用问题的算法都比较经典，因此本章重点在于理解各种图的算法及其应用场合。 【知识点】 图的类型定义、图的存储表示、图的深度优先搜索遍历和图的广度优先搜索遍历、无向网的最小生成树、最短路径、拓扑排序、关键路径 【学习指南】 离散数学中的图论是专门研究图性质的一个数学分支，但图论注重研究图的纯数学性质，而数据结构中对图的讨论则侧重于在计算机中如何表示图以及如何实现图的操作和应用等。图是较线性表和树更为复杂的数据结构，因此和线性表、树不同，虽然在遍历图的同时可以对顶点或弧进行各种操作，但更多图的应用问题如求最小生成树和最短路径等在图论的研究中都早已有了特定算法，在本章中主要是介绍它们在计算机中的具体实现。这些算法乍一看都比较难，应多对照具体图例的存储结构进行学习。而图遍历的两种搜索路径和树遍历的两种搜索路径极为相似，应将两者的算法对照学习以便提高学习的效益。 【课前思考】 1. 你有没有发现现在的十字路口的交通灯已从过去的一对改为三对，即每个方向的直行、左拐和右拐能否通行都有相应的交通灯指明。你能否对某个丁字路口的6条通路画出和第一章绪论中介绍的"五叉路口交通管理示意图"相类似的图？ 2. 如果每次让三条路同时通行，那么从图看出哪些路可以同时通行？ 同时可通行的路为：(AB,BC,CA),(AB,BC,BA),(AB,AC,CA),(CB,CA,BC) 单元练习1 一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳） （√）（1）数据的逻辑结构与数据元素本身的内容和形式无关。 （√）（2）一个数据结构是由一个逻辑结构和这个逻辑结构上的一个基本运算集构成的整体。（ㄨ）（3）数据元素是数据的最小单位。 （ㄨ）（4）数据的逻辑结构和数据的存储结构是相同的。 （ㄨ）（5）程序和算法原则上没有区别，所以在讨论数据结构时可以通用。 （√）（6）从逻辑关系上讲，数据结构主要分为线性结构和非线性结构两类。 （√）（7）数据的存储结构是数据的逻辑结构的存储映像。 （√）（8）数据的物理结构是指数据在计算机内实际的存储形式。 （ㄨ）（9）数据的逻辑结构是依赖于计算机的。 （√）（10）算法是对解题方法和步骤的描述。 二．填空题 （1）数据有逻辑结构和存储结构两种结构。 （2）数据逻辑结构除了集合以外，还包括：线性结构、树形结构和图形结构。 （3）数据结构按逻辑结构可分为两大类，它们是线性结构和非线性结构。 （4）树形结构和图形结构合称为非线性结构。 （5）在树形结构中，除了树根结点以外，其余每个结点只有 1 个前趋结点。 （6）在图形结构中，每个结点的前趋结点数和后续结点数可以任意多个。 （7）数据的存储结构又叫物理结构。 （8）数据的存储结构形式包括：顺序存储、链式存储、索引存储和散列存储。 （9）线性结构中的元素之间存在一对一的关系。 （10）树形结构结构中的元素之间存在一对多的关系， （11）图形结构的元素之间存在多对多的关系。 （12）数据结构主要研究数据的逻辑结构、存储结构和算法（或运算）三个方面的内容。（13）数据结构被定义为(D，R)，其中D是数据的有限集合，R是D上的关系的有限集合。（14）算法是一个有穷指令的集合。 （15）算法效率的度量可以分为事先估算法和事后统计法。 （16）一个算法的时间复杂性是算法输入规模的函数。 （17）算法的空间复杂度是指该算法所耗费的存储空间，它是该算法求解问题规模n的函数。（18）若一个算法中的语句频度之和为T（n）=6n+3nlog2n，则算法的时间复杂度为 O（nlog2n）。（19）若一个算法中的语句频度之和为T（n）=3n+nlog2n+n2，则算法的时间复杂度为 O（n2）。（20）数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象，以及它们之间的关系和运算的学科。数据结构1
数据结构作业标准答案
数据结构无向图
数据库应用技术第1次作业及答案
数据结构--图的应用及其实现
数据结构1
数据结构第一次作业
(完整版)数据结构详细教案——图
数据结构单元1练习参考答案
相关主题
文本预览