科文学院09z网络数据结构期末复习资料
一、单项选择题
（1）以下数据结构中哪一个是线性结构？（ B ）
A）有向图 B）队列 C）线索二叉树 D）B树
考点：队列，栈，线性表是线性结构
（2）在一个单链表HL中，若要在当前由指针p指向的结点后面插入一个由q指向的结点，则执行如下（ D ）语句序列。
A）p=q; p->next=q; B）p->next=q; q->next=p;
C）p->next=q->next; p=q; D）q->next=p->next; p->next=q;
（3）（ A ）不是队列的基本运算。
A）在队列第i个元素之后插入一个元素 B）从队头删除一个元素
C）判断一个队列是否为空D）读取队头元素的值知识点：队列的基本逻辑运算
与栈类似,队列的运算可以归纳为以下几种:
1. AddQ(ElemType x)
——在队列的尾部插入一个新的元素x。队尾的位置由rear指出。
2. DelQ(Q)
——删除队列的队头的元素。队头的位置由front指出。
3. EmptyQ(Q)
——测试队列Q是否为空队。当队列为空时返回一个真值,否则返回一个假值。
4. FrontQ(Q)
——取得队列Q的队头元素。该运算与DelQ(Q)不同,?后者要修改队头元素指针。
5. SetNULL(Q)
——创建一个空队Q,这个运算与线性表置空表类似
（4）字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成（ B ）个不同的字符串。
A）14 B）5 C）6 D）8 知识点：
ABC
ACB
BAC
BCA
CBA
（5）由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为（ B ）。
A）11 B）35 C）19 D）53
知识点：
先作出哈夫曼树如下
两两相加，小小相加。越小的数离根节点越远。
(3+2）*3+6*2+8*1=35
权值要乘以层数，是带权路径长度。
以下6-8题基于下图：
（6）该二叉树结点的前序遍历的序列为（ C ）。
A）E、G、F、A、C、D、B B）E、A、G、C、F、B、D
C）E、A、C、B、D、G、F D）E、G、A、C、D、F、B
（7）该二叉树结点的中序遍历的序列为（ A ）。
A）A、B、C、D、E、G、F B）E、A、G、C、F、B、D
C）E、A、C、B、D、G、F D）B、D、C、A、F、G、E
重要！！
（8）该二叉树的按层遍历的序列为（ C ）。
A）E、G、F、A、C、D、B B）E、A、C、B、D、G、F
C）E、A、G、C、F、B、D D）E、G、A、C、D、F、B
（9）下面关于图的存储的叙述中正确的是（ B ）。
A）用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关
B）用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关
C）用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关
D）用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关
（10）设有关键码序列(q,g,m,z,a,n,p,x,h)，下面哪一个序列是从上述序列出发建堆的结果?（ B ）
A）a,g,h,m,n,p,q,x,z B）a,g,m,h,q,n,p,x,z C）g,m,q,a,n,p,x,h,z D）h,g,m,p,a,n,q,x,z
答案来自：https://www.doczj.com/doc/6c2935485.html,/p-9775066.html
（11）设Huffman树的叶子结点数为m，则结点总数为（ B ）。
A）2m B）2m-1
C）2m+1 D）m+1
（12）若顺序存储的循环队列的QueueMaxSize=n，则该队列最多可存储（ B ）个元素。
A）n B）n-1 C）n+1 D）不确定（13）下述哪一条是顺序存储方式的优点？（ A ）
A）存储密度大B）插入和删除运算方便
C）获取符合某种条件的元素方便 D）查找运算速度快
（14）设有一个二维数组A[m][n]，假设A[0][0]存放位置在600(10)，A[3][3]存放位置在678(10)，每个元素占一个空间，问A[2][3](10)存放在什么位置？（脚注(10)表示用10进制表示，m>3）（）。
A）658 B）648 C）633 D）653
例：设有一个二维数组A[m][n],假设A[0][0]存放位置在644(10),A[2][2]存放位置在676(10),每个元素占一个空间,问A[3][3](10)存放在什么位置脚注(10)表示用10进制表示. 【解答】
设数组元素A[i][j]存放在起始地址为Loc ( i, j ) 的存储单元中.
∵Loc ( 2, 2 ) = Loc ( 0, 0 ) + 2 * n + 2 = 644 + 2 * n + 2 = 676.
∴n = ( 676 - 2 - 644 ) / 2 = 15
∴Loc ( 3, 3 ) = Loc ( 0, 0 ) + 3 * 15 + 3 = 644 + 45 + 3 = 692.
（15）下列关于二叉树遍历的叙述中，正确的是（ D ）。
A）若一个叶子是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序遍历最后一个结点
B）若一个结点是某二叉树的前序遍历最后一个结点，则它必是该二叉树的中序遍历的最后一个结点
C）若一个结点是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序最后一个结点
D）若一个树叶是某二叉树的前序最后一个结点，则它必是该二叉树的中序遍历最后一个结点
（16）k层二叉树的结点总数最多为（ A ）。
A）2k-1 B）2k+1C）2K-1 D）2k-1（17）对线性表进行二分法查找，其前提条件是（ C ）。
A）线性表以链接方式存储，并且按关键码值排好序
B）线性表以顺序方式存储，并且按关键码值的检索频率排好序
C）线性表以顺序方式存储，并且按关键码值排好序
D）线性表以链接方式存储，并且按关键码值的检索频率排好序
（18）对n个记录进行堆排序，所需要的辅助存储空间为（ C ）。
A）O(1og2n) B）O(n) C）O(1) D）O(n2) （19）对于线性表（7，34，77，25，64，49，20，14）进行散列存储时，若选用H（K）=K%7作为散列函数，则散列地址为0的元素有（ D ）个。
A）1 B）2 C）3 D）4 （20）下列关于数据结构的叙述中，正确的是（ D ）。
A）数组是不同类型值的集合
B）递归算法的程序结构比迭代算法的程序结构更为精炼
C）树是一种线性结构
D）用一维数组存储一棵完全二叉树是有效的存储方法
以上题目来自：https://www.doczj.com/doc/6c2935485.html,/51986692.html
（21）对一个算法的评价，不包括如下（ B ）方面的内容。
A）健壮性和可读性B）并行性 C）正确性 D）时空复杂度（22）在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行（ A ）。
A）p->next=HL->next; HL->next=p B）p->next=HL; HL=p
C）p->next=HL; p=HL D）HL=p; p->next=HL
（23）对线性表，在下列哪种情况下应当采用链表表示？（ B ）
A）经常需要随机地存取元素B）经常需要进行插入和删除操作
C）表中元素需要占据一片连续的存储空间D）表中元素的个数不变（24）一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是（ C ）。
A）2 3 1 B）3 2 1 C）3 1 2 D）1 2 3
以上题目来自：https://www.doczj.com/doc/6c2935485.html,/view/aea24a3231126edb6f1a10af.html
（25）每一趟都能选出一个元素放在其最终位置上，并且不稳定的排序算法是（ B ）。
A）冒泡排序B）简单选择排序C）希尔排序D）直接插入排序（26）采用开放定址法处理散列表的冲突时，其平均查找长度（ B ）。
A）低于链接法处理冲突B）高于链接法处理冲突
C）与链接法处理冲突相同D）高于二分查找
（27）若需要利用形参直接访问实参时，应将形参变量说明为（ D ）参数。
A）值B）函数C）指针D）引用
（28）在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的（ A ）。
A）行号B）列号C）元素值 D）非零元素个数（29）快速排序在最坏情况下的时间复杂度为（ D ）。
A）O(log2n) B）O(nlog2n) C）O(n) D）O(n2) （30）从二叉搜索树中查找一个元素时，其时间复杂度大致为（ C ）。
A）O(n) B）O(1) C）O(log2n) D）O(n2) （31）以下数据结构中哪一个是线性结构？（ B ）
A）有向图B）栈 C）二叉树D）B树（32）若某链表最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用（ C ）存储方式最节省时间。
A）单链表B）双链表C）带头结点的双循环链表 D）单循环链表（33）（ A ）不是队列的基本运算。
A）在队列第i个元素之后插入一个元素 B）从队头删除一个元素
C）判断一个队列是否为空 D）读取队头元素的值（34）字符A、B、C、D依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成（ B ）个不同的字符串？
A）15 B）14 C）16 D）21
（35）由权值分别为4,7,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为（ B ）。
A）11 B）37 C）19 D）53
以上题来自：https://www.doczj.com/doc/6c2935485.html,/view/6a6fc23a87c24028915fc3ef.html
以下6-8题基于下面的叙述：若某二叉树结点的中序遍历的序列为A、B、C、D、E、F、G，后序遍历的序列为B、D、C、A、F、G、E。
（36）则该二叉树结点的前序遍历的序列为（ C ）。
A）E、G、F、A、C、D、B B）E、A、G、C、F、B、D
C）E、A、C、B、D、G、F D）E、G、A、C、D、F、B
（37）该二叉树有（ A ）个叶子。
A）3 B）2 C）5 D）4
（38）该二叉树的按层遍历的序列为（ C ）。
A）E、G、F、A、C、D、B B）E、A、C、B、D、G、F
C）E、A、G、C、F、B、D D）E、G、A、C、D、F、B （39）下面的二叉树中，（ C ）不是完全二叉树。
（40）设有关键码序列(q,g,m,z,a)，（ B ）序列是从上述序列出发建的小根堆的结果。
A ）a,g ,m,q,z
B ）a,g,m,z,q
C ）g,m,q,a,z
D ）g, m, a,q,z
以上题来自： https://www.doczj.com/doc/6c2935485.html,/view/6a6fc23a87c24028915fc3ef.html
（41）队列的特点是（ B ）。
A ）先进后出
B ）先进先出
C ）任意位置进出
D ）前面都不正确
（42）有n 个记录的文件，如关键字位数为d ，基数为r ，则基数排序共要进行（ B ）遍分配与收集。
A ）n
B ）d
C ）r
D ）n - d
（43）在二叉树结点的先序序列、中序序列和后序序列中，所有叶子结点的先后顺序（ B ）。
A ）都不相同
B ）完全相同
C ）先序和中序相同，而与后序不同
D ）中序和后序相同，而与先序不同
（44）限定在一端加入和删除元素的线性表称为（ C ）。
A ）双向链表
B ）单向链表
C ）栈
D ）队列
（45）快速排序执行一遍之后，已经到位的元素个数是（ A ）。
A ）1
B ）3
C ）4n
D ）2
n （46）设森林F 对应的二叉树为B ，它有m 个结点，B 的根为p ，p 的右子树上的结点个数为n ，森林F 中第一棵树的结点个数是（ D ）。
A ）m-n-1
B ）n+1
C ）m-n+1
D ）m-n
（47）设有198个初始归并段，如采用K-路平衡归并三遍完成排序，则K 值最大为（ C ）。
A ）12
B ）13
C ）14
D ）15
（48）下面关于广义表的叙述中，不正确的是（ B ）。
A ）广义表可以是一个多层次的结构
B ）广义表至少有一个元素
C ）广义表可以被其他广义表所共享
D ）广义表可以是一个递归表
（49）设二叉树根结点的层次为0，一棵深度（高度）为k 的满二叉树和同样深度完全二叉树各有f 个结点和c 个结点，下列关系式不正确的是（ B ）。
A ）f>=c
B ）c>f
C ）f=2k+1-a
D ）c>s k -1
（50）从L=((apple,pear),(orange,banana))中，取出banana 元素的表达式为（ D ）。
A ）head(tail(L))
B ）head(head(tail(L)))
C ）tail(head(tail(L)))
D ）head(tail(head(tail(L))))
以上题来自：https://www.doczj.com/doc/6c2935485.html,/view/6a6fc23a87c24028915fc3ef.html
（51）下列文件的物理结构中，不利于文件长度动态增长的文件物理结构是（ A ）。
A）顺序结构B）链接结构C）索引结构D）Hash结构（52）在数据结构中，数据元素可由（ C ）。
A）实体B）域C）数据项D）字段（53）对于有n个顶点的有向图，由弗洛伊德（Floyd）算法求每一对顶之间的最短路径的时间复杂度是（ D ）。
A）O(1) B）O(n) C）O(n) D）O(n3) （54）对n个记录的文件进行快速排序，所需要的辅助存储空间为（ B ）。
A）O（1）B）O（log2n）C）O（n）D）O（n2）（55）哈夫曼树中一定不存在（ B ）。
A）度为0的结点 B）度为1的结点C）度为2的结点 D）带权的结点（56）设D={A,B,C,D}，R={
A）树B）图B）线性表D）前面都正确（57）（ C ）关键码序列不符合堆的定义。
A）A、C、D、G、H、M、P、Q、R、X
B）A、C、M、D、H、P、X、G、Q、R
C）A、D、P、R、C、Q、X、M、H、G
D）A、D、C、M、P、G、H、X、R、Q
（58）假定关键字K=442205883，允许存储地址为四位十进制数，并且Hash地址为6111，则所采用的构造Hash函数的方法是（ D ）。
A）直接定址法B）平方取中法C）除留余数法，模为97 D）折叠法（59）在算法的时间复杂度中，n表示问题规模，f(n)表示基本操作重复执行的次数，则随问题的规模n的增大，算法执行时间的增长率同（ A ）相同。
A）f(n) B）n C）O(n) D）前面都不正确
（60）对线性表进行二分法查找，其前提条件是（ A ）。
A）线性表以顺序方式存储，并且按关键码值排好序
B）线性表以顺序方式存储，并且按关键码值的检索频率排好序
C）线性表以链接方式存储，并且按关键码值排好序
D）线性表以链接方式存储，并且按关键码值的检索频率排好序
《数据结构与算法》（c语言版）期末考复习题 一、选择题。 1．在数据结构中，从逻辑上可以把数据结构分为 C 。 A．动态结构和静态结构B．紧凑结构和非紧凑结构 C．线性结构和非线性结构D．内部结构和外部结构 2．数据结构在计算机内存中的表示是指 A 。 A．数据的存储结构B．数据结构C．数据的逻辑结构D．数据元素之间的关系 3．在数据结构中，与所使用的计算机无关的是数据的 A 结构。 A．逻辑B．存储C．逻辑和存储D．物理 4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C 。A．数据的处理方法B．数据元素的类型 C．数据元素之间的关系D．数据的存储方法 5．在决定选取何种存储结构时，一般不考虑 A 。 A．各结点的值如何B．结点个数的多少 C．对数据有哪些运算D．所用的编程语言实现这种结构是否方便。 6．以下说法正确的是 D 。 A．数据项是数据的基本单位
B．数据元素是数据的最小单位 C．数据结构是带结构的数据项的集合 D．一些表面上很不相同的数据可以有相同的逻辑结构 7．算法分析的目的是 C ，算法分析的两个主要方面是 A 。（1）A．找出数据结构的合理性B．研究算法中的输入和输出的关系C．分析算法的效率以求改进C．分析算法的易读性和文档性（2）A．空间复杂度和时间复杂度B．正确性和简明性 C．可读性和文档性D．数据复杂性和程序复杂性 8．下面程序段的时间复杂度是O(n2) 。 s =0; for( I =0; i 单项选择 （ B ） 1. 通常所说的主机是指∶ A) CPU B) CPU和内存C) CPU、内存与外存D) CPU、内存与硬盘 （ C ）2. 在计算机内部，一切信息的存取、处理和传送的形式是∶ A) ACSII码B) BCD码C)二进制D)十六进制 （ D ）3. 软件与程序的区别是∶ A)程序价格便宜、软件价格昂贵； B)程序是用户自己编写的，而软件是由厂家提供的； C) 程序是用高级语言编写的，而软件是由机器语言编写的； D) 软件是程序以及开发、使用和维护所需要的所有文档的总称，而程序只是软件的一部分。 （ C ）4. 所谓“裸机”是指∶ A) 单片机B)单板机C) 不装备任何软件的计算机D) 只装备操作系统的计算机 （ D ）5. 应用软件是指∶ A)所有能够使用的软件B) 能被各应用单位共同使用的某种软件 C)所有微机上都应使用的基本软件D) 专门为某一应用目的而编制的软件 （A）6. C语言中的常量可分为整型常量、实型常量、字符型常量及(枚举)四种。 （A）符号常量（B）长整型常量（C）逻辑常量（D）二进制整数 （ C ）7. 编译程序的功能是∶ A)发现源程序中的语法错误B)改正源程序中的语法错误 C)将源程序编译成目标程序D)将某一高级语言程序翻译成另一种高级语言程序 （A）8. 系统软件中最重要的是∶ A) 操作系统B) 语言处理系统C) 工具软件D) 数据库管理系统 （ C ）9. 可移植性最好的计算机语言是∶ A) 机器语言B)汇编语言C) 高级语言D) 自然语言 （ B ）10. 非线性结构是数据元素之间存在一种： A）一对多关系B）多对多关系C）多对一关系D）一对一关系 （ C ）11. 数据结构中，与所使用的计算机无关的是数据的结构； A) 存储B) 物理C) 逻辑D) 物理和存储 （ C ）12. 算法分析的目的是： A) 找出数据结构的合理性B) 研究算法中的输入和输出的关系 C) 分析算法的效率以求改进D) 分析算法的易懂性和文档性 （A）13. 算法分析的两个主要方面是： A) 空间复杂性和时间复杂性B) 正确性和简明性 C) 可读性和文档性D) 数据复杂性和程序复杂性 （ C ）14. 计算机算法指的是： A) 计算方法B) 排序方法C) 解决问题的有限运算序列D) 调度方法 （ B ）15. 计算机算法必须具备输入、输出和等5个特性。 A) 可行性、可移植性和可扩充性B) 可行性、确定性和有穷性 C) 确定性、有穷性和稳定性D) 易读性、稳定性和安全性 （ C ）16．数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为： （A）存储结构（B）逻辑结构（C）顺序存储结构（D）链式存储结构 （ B ）17.一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是 （A）110 （B）108 （C）100 （D）120 （A）18. 在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是：（A）访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n） （B）在第i个结点后插入一个新结点（1≤i≤n） （C）删除第i个结点（1≤i≤n） （D）将n个结点从小到大排序 （ B ）19. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动个元素 （A）8 （B）63.5 （C）63 （D）7 （A）20. 链接存储的存储结构所占存储空间： （A）分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针 判断： 1.线性表的链式存储结构优于顺序存储错误 2.单链表的每个节点都恰好包含一个指针域错误 3.线性表中的元素都可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因 此属于同一数据对象正确 4.在线性表的顺序存储结构中，逻辑上相邻的两个元素在屋里位置上并不一定紧邻。错 误 5.在线性表的数据结构中，插入和删除元素时，移动元素的个数和该元素的位置有关。正 确 6.顺序存储的线性表可以实现随机存取正确 7.栈一定是顺序存储的线性结构错误 8.一个栈的输入序列为A，B,C,D，可以得到输入序列为C,A,B,D 错误 9.队列是一种后进先出的线性表错误 10.树结构中每个节点最多只有一个直接前驱正确 11.二叉树的前序遍历中，任意一个节点均处于其子树节点的前面正确 12.在栈空的情况下，不能做出出栈操作，否则产生溢出正确 13.在前序遍历二叉树的序列中，任何节点的子树的所有节点都是直接跟在该节点之后正 确 填空： 1.在N个节点的顺序表中删除一个节点平均需要移动（（N-1）/2）个节点，具体的移 动次数取决于（表长N和删除位置） 2.在单链表中除首节点外，任意节点的存储位置都由（直接前驱）节点中的指针指示 3.树中节点的最大层次称为树的（度） 4.由一颗二叉树的前序序列和（中）序列可唯一确定这棵二叉树 5.哈弗曼树的带权路径长度（最小）的二叉树 6.二插排序树任意节点的关键字值（大于）其左子树中各节点的关键字值（小于）其 右子树中的各节点关键字值 7.二分查找法，表中元素必须按（关键字有序）存放 选择： 1.用单链表方式存储的线性表，储存每个节点需要两个域，一个数据域，另一个是（B 指针域） 2.设A1，A2，A3为三个节点；P，10，,2代表地址，则如下的链表存储结构称为（B 单链表） 3.单链表的存储密度（C 小于1） 4.在线性表中（B 中间元素）只有一个直接前驱和一个直接后续 5.两个指针P和Q，分别指向单链表的两个元素P所指元素时Q所指元素前驱的条 件是（D P==Q） 6.在栈中存取数据的原则是（B 后进先出） 7.顺序栈判空的条件是（C top==-1） 8.串是一种特殊的线性表，其特殊性体现在（B 数据元素是一个字符） 9.求字符串T和字符串S中首次出现的位置的操作为（C 串的模式匹配） 10.深度为H的二叉树至多有（B 2H-1）个节点 混凝土结构设计（A ）期末复习题一 二、判断题（每小题2分，共计30分。将判断结果填入括弧，以√表示正确，以×表示错误） 1．对于21 3l l ≥的板，可按单向板进行设计，这是由于板上的荷载主要沿板的短边方向传递到相应的支承梁上，所以只需沿板的短跨方向布置受力筋，而沿板的长跨方向不必布置任何钢筋。（错 ） 2．按弹性理论计算单向板肋梁楼盖主梁支座截面的配筋时，其内力设计值应以支座边缘截面为准，即 02 b b M M V =-?。（对 ） 3．肋形楼盖荷载传递的途径是板→主梁→次梁→柱或墙→基础→地基。（错 ） 4．无梁楼盖的特点在于传力体系简化，楼层净空增大，底面平整，模板简单，便于施工。（对 ） 5．钢筋混凝土楼梯按结构受力状态可分为梁式、板式、折板悬挑式和螺旋式，前两种属于空间受力体系；后两种属于平面受力体系。（错 ） 6．屋面板、屋架或屋面梁、托架、天窗架属于屋盖结构体系。屋盖结构分无檩屋盖和有檩屋盖两种。（对 ） 7．排架结构形式是指钢筋混凝土排架由屋面梁（或屋架）、柱和基础组合，排架柱上部与屋架铰接，排架柱下部与基础刚接的结构形式。（对） 8．作用在厂房结构上的大部分荷载（屋盖上的竖向荷载，吊车上的竖向荷载和横向水平荷载，横向风荷载或横向地震作用，部分墙体和墙梁的自重以及柱上的设备等荷载）都是通过横向排架传给基础、再传到地基中去。（对） 9．厂房支撑体系是连系屋架、柱等构件，使其构成厂房空间整体，保证整体刚性和结构几何稳定性的重要组成部分。（对） 10．无檩屋盖的刚度和整体性较差，一般用于非保温区的小型车间和山区建筑中。（ 错） 11．混合承重体系的优点是有利于抵抗来自纵横两个方向的风荷载和地震作用，使框架结构具有较好的整体工作性能。（ 对） 12．一般认为，当梁的线刚度与柱的线刚度之比超过3时，反弯点法的计算误差能够满足工程设计的精度要求。（对） 13．框架结构若某层柱的上、下横梁线刚度不同，则该层柱反弯点位置将向横梁刚度较小一侧偏移。（对） 14．我国有关规范规定，弯矩调幅只对竖向荷载作用下的内力进行，即水平荷载作用下产生的弯矩不参加调幅，因此，弯矩调幅应在内力组合之前进行。（对） 15．框架节点区的混凝土强度等级，应不低于柱子的混凝土强度等级。（对） 二、判断题（每小题2分，共计30分。将判断结果填入括弧，以√表示正确，以×表示错误） 1. 肋形楼盖荷载传递的途径是板→次梁→主梁→柱或墙→基础→地基。（√ ） 2．在进行钢筋混凝土连续梁、板设计时，采用按弹性理论的计算方法与采用考虑塑性内力重分布的计算方法相比，后者的计算结果更偏于安全。（× ） 3. 对单向板肋梁楼盖的板，可沿板长跨方向取出1m 宽的板带作为计算单元，代表整个板的受力状态。（× ） 2011-2012学年第一学期期末考查 《数据结构》试卷 （答案一律写在答题纸上，在本试卷上做答无效） 一、选择（每题1分，共10分） 1.长度为n的线性表采用顺序存储结构，一个在其第i个位置插入新元素的算法时间复杂度为（D） A.O(0) B.O(1) C.O(n) D.O(n2) 2.六个元素按照6，5，4，3，2，1的顺序入栈，下列哪一个是合法的出栈序列？（D） A.543612 B.453126 C.346512 D.234156 3.设树的度为4，其中度为1、2、3、4的结点个数分别是4、2、1、2，则树中叶子个数为（B ） A.8 B.9 C.10 D.11 4.设森林F对应的二叉树B有m个结点，B的右子树结点个数为n，森林F中第一棵树的结点个数是（ B ） A. m-n B.m-n-1 C.n+1 D.m+n 5.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（B） A.9 B.11 C.15 D.不确定 6.下列哪一个方法可以判断出一个有向图是否有环。（A） A.深度优先遍历 B.拓扑排序 C.求最短路径 D.求关键路径 7.第7层有10个叶子结点的完全二叉树不可能有（B ）个结点。 A.73 B.234 C.235 D.236 8.分别用以下序列构造二叉排序树，与用其他三个序列构造的结果不同的是（B） A.（100,80,90,60,120,110,130） B.（100, 120, 110,130,80, 60,90） C.（100,60,80,90,120,110,130） D.（100,80, 60,90, 120, 130,110） 9.对一组数据（84，47，25，15，21）排序，数据的排列次序在排序过程中变化如下：（1）84 47 25 15 21 （2）15 47 25 84 21 （3）15 21 25 84 47（4）15 21 25 47 84则采用的排序方法是（B ） A.选择排序 B.起泡排序 C.快速排序 D.插入排序 10.对线性表进行折半查找时，要求线性表必须（D） A.以顺序方式存储 B.以顺序方式存储，且数据元素有序 1.什么是最小生成树？简述最小生成树的Prime算法的思想。 答：最小生成树就是构造一棵生成树，使得树上各边的代价之和最小。 普里姆算法(Prim)的基本思想： 从连通网络N = { V, E }中的某一顶点u0 出发，选择与它关联的具有最小权值的边(u0, v)，将其顶点加入到生成树的顶点集合U中。以后每一步从一个顶点在U中，而另一个顶点不在U中的各条边中选择权值最小的边(u, v),把它的顶点加入到集合U中。如此继续下去，直到网络中的所有顶点都加入到生成树顶点集合U中为止。 2.简述AOV网络中为何不能出现回路，如何判断AOV网络是否有回路？ 答：在AOV网络中，如果活动vi必须在vj之前进行，则称为存在有向边；在AOV网络中不能出现有向回路，如果出现了，则意味着某项活动应以自己作为先决条件。 如何检查AOV网是否存在有向环： 检测有向环的一种方法是对AOV网络构造它的拓扑有序序列。即将各个顶点(代表各个活动)排列成一个线性有序的序列，使得AOV网络中所有应存在的前驱和后继关系都能得到满足。（1）这种构造AOV网络全部顶点的拓扑有序序列的运算就叫做拓扑排序。 （2）如果通过拓扑排序能将AOV网络的所有顶点都排入一个拓扑有序的序列中，则该AOV 网络中必定不会出现有向环；相反，如果得不到满足要求的拓扑有序序列，则说明AOV网络中存在有向环，此AOV网络所代表的工程是不可行的。 3.为何需要采用循环队列？n个空间的循环队列，最多存储多少个元素？为什 么？ 答：循环队列以克服顺序队列的"假上溢"现象，能够使存储队列的向量空间得到充分的利用，所以采用循环队列。 n个空间的循环队列，最多存储n-1个元素，那是为了区别循环队列的队空和队满的条件。队空的条件是Q.front==Q.rear，而队满的条件是(Q.rear+1)%N==Q.front(N是数组中单元的总数)，因此，Q.rear所指向的数组单元处于未用状态。所以说，N个单元的数组所存放的循环队列最大长度是N-1。 4.简述堆的删除算法，其删除的是那个值？ 答：堆的删除算法：首先，移除根节点的元素（并把根节点作为当前结点）比较当前结点的两个孩子结点的元素大小，把较大的那个元素移给当前结点，接着把被移除元素的孩子结点作为当前结点，并再比较当前结点的孩子的大小，以此循环，直到最后一个叶子结点的值大于或等于当前结点的孩子结点或孩子结点的位置超过了树中元素的个数，则退出循环。最后把最后叶子结点的元素移给当前结点。 在堆的算法里面，删除的值为根值。 5.线索二叉树中，什么是线索，它是否唯一？可有根据什么顺序得到？ 2014~2015学期期末复习题 一、名词解释： 1.永久荷载： 在结构使用期间，其值不随时间变化，或其变化与平均值相比可以忽略不计，或其变化是单调的并能趋于限值的荷载。 2.可变荷载： 在结构使用期间，其值随时间变化，且其变化与平均值相比不可以忽略不计的荷载。 3.偶然荷载： 在结构使用年限内不一定出现，而一旦出现其量值很大，且持续时间很短的荷载。 4.装配整体式混凝土结构： 由预制混凝土构件或部件通过钢筋、连接件或施加预应力等加以连接，并在现场浇筑混凝土而形成整体受力的混凝土结构。 5.后张法预应力混凝土结构： 浇筑混凝土并达到规定强度后，通过张拉预应力筋并在结构上锚固而建立预加应力的混凝土结构。 6.混凝土构造柱： 在砌体房屋墙体的规定部位，按构造配筋，并按先砌墙后浇灌混凝土柱的施工顺序制成的混凝土柱，通常称为混凝土构造柱，简称构造柱。 7.抗震设防烈度： 按国家规定的权限批准作为一个地区抗震设防依据的地震烈度。一般情况，取50年内超越概率10%的地震烈度。 8.抗震措施： 除地震作用计算和抗力计算以外的抗震设计内容，包括抗震构造措施。 9.抗震构造措施： 根据抗震概念设计原则，一般不需计算而对结构和非结构各部分必须采取的各种细部要求。 10.房屋高度： 自室外地面至房屋主要屋面的高度，不包括突出屋面的电梯机房、水箱、构架等高度。 11.框架-剪力墙结构： 由框架和剪力墙共同承受竖向和水平作用的结构。 12. 无筋扩展基础： 由砖、毛石、混凝土或毛石混凝土、灰土和三合土等材料组成的，且不需配置钢筋的墙下条形基础或柱下独立基础。 13. 整体稳定：在外荷载作用下，对整个结构或构件能否发生屈曲或失稳的评估。 二、填空 1.同一强度等级的混凝土，其强度标准值满足以下关系：立方体抗压强度>轴心抗压强度>抗拉强度。 2.梁的正截面破坏形式主要与梁内纵向受拉钢筋的配筋率有关，根据配筋率的不同，可将梁分为适筋梁、超筋梁、 少筋梁。 3. 斜截面破坏有三种形式：（1）斜拉破坏(λ>3) 、（2）剪压破坏（1<λ≤3)、（3）斜压破坏（λ≤1) 。 4. 钢筋砼受弯的两种破坏形式分为正截面破坏和斜截面破坏。混凝土结构的极限状态设计应包括：承载能力极限 状态和正常使用极限状态两种情况。 5. 钢筋混凝土结构中，16代表直径为16mm的HRB400钢筋，16代表直径为16mm的HRB335钢筋，16代表 直径为16mm的HPB300钢筋。 6. 钢筋混凝土受压构件分轴心受压构件、单向偏心受压构件和双向偏心受压构件三种。 7. 预应力混凝土按预应力钢筋与混凝土的粘接状况分为：有粘接预应力混凝土、无粘接预应力混凝土。按预加应 力的程度分为：全预应力混凝土、有限预应力混凝土、部分预应力混凝土。 8. 适筋梁破坏时，受拉筋先屈服然后受压区混凝土被压碎。由于适筋梁的材料强度能充分发挥，因而它是作为设 计依据的一种破坏形式。 9. 结构构件的两种极限状态对应三种组合即基本组合、标准组合、准永久组合。 10. 楼梯按结构形式可分为：板式楼梯、梁式楼梯和旋转式楼梯，板式楼梯的梯板厚度通常取楼梯水平投影的 数据结构期末复习题 一、选择题 1.以下说法中不正确的是（D）。 A.数据元素是数据的基本单位 B.数据项是不可分割的最小可标识单位 C.数据可由若干个数据元素构成 D.数据项可由若干个数据元素构成 2.计算机所处理的数据一般具备某种内在联系，这是指（B）。 A.数据和数据之间存在某种关系 B.元素和元素之间存在某种关系 C.元素内部具有某种结构 D.数据项和数据项之间存在某种关系 3.在数据结构中，与所使用的计算机无关的是数据的（A）结构。 A.逻辑 B.存储 C.逻辑和存储 D.物理 4.数据的逻辑结构可以分为（C）两类。 A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C.线性结构和非线性结构 D.内部结构和外部结构 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.在计算机中存储数据时，通常不仅要存储个数据元素的值，而且还要存储（C）。 A.数据的处理方法 B.数据元素的类型 C.数据元素之间的关系 D.数据的存储方法 10.数据结构在计算机内存中的表示是指（A）。 A.数据的存储结构 B.数据结构 C.数据的逻辑结构 D.数据元素之间的关系 11.在数据的存储结构中，一个结点通常存储一个（B）。 A.数据项 B.数据元素 C.数据结构 D.数据类型 12.在决定选择何种类型的存储结构时，一般不多考虑（A）。 1．数据逻辑结构包括线性结构、树形结构和图状结构三种类型，树形结构和图状结构合称非线性结构。 2．数据的逻辑结构分为集合、线性结构、树形结构和图状结构 4种。 3．在线性结构中，第一个结点没有前驱结点，其余每个结点有且只有 1 个前驱结点；最后一个结点没有后续结点，其余每个结点有且只有 1 个后续结点。 4．线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。 5．在树形结构中，树根结点没有前驱结点，其余每个结点有且只有 1 个前驱结点；叶子结点没有后续结点，其余每个结点的后续结点可以任意多个。 6．数据结构的基本存储方法是顺序、链式、索引和散列存储。 7．衡量一个算法的优劣主要考虑正确性、可读性、健壮性和时间复杂度与空间复杂度。 8．评估一个算法的优劣，通常从时间复杂度和空间复杂度两个方面考察。 9．算法的5个重要特性是有穷性、确定性、可行性、输入和输出。 10．在一个长度为n的顺序表中删除第i个元素时，需向前移动 n-i 个元素。 11．在单链表中，要删除某一指定的结点，必须找到该结点的前驱结点。 12．在双链表中，每个结点有两个指针域，一个指向前驱结点，另一个指向后继结点。 13．在顺序表中插入或删除一个数据元素，需要平均移动 n 个数据元素，移动数据元素的个数与位置有关。 14．当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表的元素是，应采用顺序存储结构。 15．根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成单链表和双链表。 16．顺序存储结构是通过下标表示元素之间的关系的；链式存储结构是通过指针表示元素之间的关系的。 17．带头结点的循环链表L中只有一个元素结点的条件是 L->next->next=L 。 第二章算法分析 1.算法分析是计算机科学的基础 2.增长函数表示问题（n）大小与我们希望最优化的值之间的关系。该函数表示了该算法的时间复杂度或空间复杂度。增长函数表示与该问题大小相对应的时间或空间的使用 3.渐进复杂度：随着n的增加时增长函数的一般性质，这一特性基于该表达式的主项，即n 增加时表达式中增长最快的那一项。 4.渐进复杂度称为算法的阶次，算法的阶次是忽略该算法的增长函数中的常量和其他次要项，只保留主项而得出来的。算法的阶次为增长函数提供了一个上界。 5.渐进复杂度：增长函数的界限，由增长函数的主项确定的。渐进复杂度类似的函数，归为相同类型的函数。 6.只有可运行的语句才会增加时间复杂度。 7. O() 或者大O记法：与问题大小无关、执行时间恒定的增长函数称为具有O（1）的复杂度。 增长函数阶次 t(n)=17 O(1) t(n)=3log n O(log n) t(n)=20n-4 O(n) t(n)=12n log n + 100n O(n log n) t(n)=3n2+ 5n - 2 O(n2) t(n)=8n3+ 3n2O(n3) t(n)=2n+ 18n2+3n O(2n) 8.所有具有相同阶次的算法，从运行效率的角度来说都是等价的。 9.如果算法的运行效率低，从长远来说，使用更快的处理器也无济于事。 10.要分析循环运行，首先要确定该循环体的阶次n，然后用该循环要运行的次数乘以它。（n 表示的是问题的大小） 11.分析嵌套循环的复杂度时，必须将内层和外层循环都考虑进来。 12.方法调用的复杂度分析： 如：public void printsum(int count){ int sum = 0 ; for (int I = 1 ; I < count ; I++) sum += I ; System.out.println(sun); } printsum方法的复杂度为O（n）,计算调用该方法的初始循环的时间复杂度，只需把printsum方法的复杂度乘以该循环运行的次数即可。所以调用上面实现的printsum方法的复 杂度为O（n2）。 13指数函数增长> 幂函数增长> 对数函数增长 1.一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（ 1）。 选择一项： 1. 108 2. 110 3. 100 4. 120 2.在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是（b） 选择一项： a. 删除第i个结点（1≤i≤n） b. 访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n） c. 将n个结点从小到大排序 d. 在第i个结点后插入一个新结点（1≤i≤n） 3.以下说法错误的是（ d）。 选择一项： a. 由于顺序存储要求连续的存储区域，所以在存储管理上不够灵活 b. 顺序存储的线性表可以随机存取 c. 求表长、定位这两种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低 d. 线性表的链式存储结构优于顺序存储结构 4.单链表的存储密度（ b）。 选择一项： a. 不能确定 b. 小于1 c. 大于1 d. 等于1 5.向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动的元素个数为（ c）。 选择一项： a. 63 b. 7 c. 63.5 d. 8 6.在一个长度为n的顺序表中，在第i个元素（1≤i≤n+1）之前插入一个新元素时须向后移动（ b）个元素。 选择一项： a. n-i b. n-i+1 c. i d. n-i-1 7.在单链表中，要将s所指结点插入到p所指结点之后，其语句应为（a ）。 选择一项： a. s->next=p->next; p->next=s; b. (*p).next=s; (*s).next=(*p).next; c. s->next=p->next; p->next=s->next; d. s->next=p+1; p->next=s; 8.在双向循环链表中，在p指针所指的结点后插入q所指向的新结点，其修改指针的操作是（b ）。 选择一项： a. p->next=q; q->prior=p; p->next->prior=q; q->next=q; b. q->prior=p; q->next=p->next; p->next->prior=q; p->next=q; c. p->next=q; p->next->prior=q; q->prior=p; q->next=p->next; d. q->prior=p; q->next=p->next; p->next=q; p->next->prior=q; 9.在双向链表存储结构中，删除p所指的结点时须修改指针（c ）。 选择一项： a. p->prior=p->next->next; p->next=p->prior->prior; b. p->next=p->next->next; p->next->prior=p; c. p->next->prior=p->prior; p->prior->next=p->next; d. p->prior->next=p; p->prior=p->prior->prior; 10.将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是（c ）。 选择一项： a. 2n b. n-1 c. n d. 2n-1 11.线性表L=(a1，a2,……an)，下列说法正确的是（ b）。 选择一项： a. 表中诸元素的排列必须是由小到大或由大到小 b. 除第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继。 c. 每个元素都有一个直接前驱和一个直接后继 d. 线性表中至少有一个元素 12.线性表若采用链式存储结构时，要求内存中可用存储单元的地址（d ）。 选择一项： a. 部分地址必须是连续的 b. 一定是不连续的 c. 必须是连续的 d. 连续或不连续都可以 13.线性表Ｌ在（d ）情况下适用于使用链式结构实现。 选择一项： a. Ｌ中结点结构复杂 b. Ｌ中含有大量的结点 c. 需经常修改Ｌ中的结点值 一．是非题 （正确的打“√”，错误的打“×”。） 1. 数据结构可用三元式表示（D，S，P）。其中：D是数据对象，S是D上的关系集， P是对D的基本操作集。× 2. 线性表的链式存储结构具有可直接存取表中任一元素的优点。× 3. 字符串是数据对象特定的线性表。 4. 二叉树是一棵结点的度最大为二的树。× 5．邻接多重表可以用以表示无向图，也可用以表示有向图。× 6．可从任意有向图中得到关于所有顶点的拓扑次序。× 7．一棵无向连通图的生成树是其极大的连通子图。× 8．二叉排序树的查找长度至多为log2ｎ。× 9．对于一棵m阶的B-树.树中每个结点至多有m 个关键字。除根之外的所有非终端结点至少有┌m/2┐个关键字。× 10．对于目前所知的排序方法，快速排序具有最好的平均性能。√ 11. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。× 12. 二维数组是其数据元素为线性表的线性表。√ 13. 连通图G的生成树是一个包含G的所有n个顶点和n-1条边的子图。× 14. 折半查找不适用于有序链表的查找。√ 15. 完全二叉树必定是平衡二叉树。√ 16. 中序线索二叉树的优点是便于在中序下查找直接前驱结点和直接后继结点。√ 17. 队列是与线性表完全不同的一种数据结构。× 18. 平均查找长度与记录的查找概率有关。√ 19. 二叉树中每个结点有两个子结点，而对一般的树，则无此限制，所以，二叉树是树的特殊情形。× 20. 算法的时间复杂性越好，可读性就越差；反之，算法的可读性越好，则时间复杂性就越差。× 二．选择题 1. 若对编号为1，2，3的列车车厢依次通过扳道栈进行调度，不能得到 (e ) 的序列。 a:1,2,3 b:1,3,2 c:2,1,3 d:2,3,1 e:3,1,2 f:3,2,1 2. 递归程序可借助于( b )转化为非递归程序。 a:线性表 b: 栈 c:队列 d:数组 3. 在下列数据结构中(c)具有先进先出（FIFO）特性，( b )具有先进后出(FILO）特性。 a:线性表 b:栈 c:队列 d:广义表 4. 对字符串s=’data-structure’ 执行操作replace(s,substring(s,6,8),’bas’) 的结果是 ( d ) 。 a: ‘database’ b: ‘data-base’ c: ‘bas’ d: ‘data-basucture’ 1、建筑具有长、宽、高三个方向的尺寸。 2、建筑结构的分类一般有那两种分法？ ①按材料分为： 砌体结构混凝土结构钢结构混合结构（钢结构和混凝土结构）木结构。 ②按结构受力特征分为： 框架结构、剪力墙结构、框剪结构、筒体结构、框筒结构、筒中筒结构、束筒结构。 3、房屋的集中形成了街道、村镇和城市。 4、建筑既满足人们的物质需要，又满足了人们的精神需要。它既是一种技术产品。又是一 种艺术创作。 5、建筑的功能：①人体活动尺度的要求②人的生理要求③使用过程和特点的要求 （工业建筑中不是取决于人的活动，而是取决于设备的数量和大小；设备的要求比人的生理要求更严格——冷冻车间，纺织厂湿度；使用过程以产品的工艺流程来确定） 6、影响建筑的因素： ①社会生产方式的变化使建筑不断发展——中世纪的教堂曾经是当时居民的生活中心，是城镇的标志和象征。 ②社会思想意识民族文化特征——民族或地区的文化特征都是在长期的社会发展中形成的， 在一定的历史条件下，建筑和雕刻、绘画等常常形成艺术上的统一风格。 ③地区自然条件的影响——建筑与周围自然环境的结合，造成了丰富多彩的地方特色，即使在同一个国家或民族内，处于市区和处于水乡的建筑也会表现出不同的风貌。 承重墙体系-------既起承重作用又起分隔作用。 7、柱、梁板和拱券结构是人类最早采用的两种结构形式。 8、建筑美观基本原则： ①比例：建筑的各种大小、高矮、长短、宽窄、厚薄、深浅等的比较关系。 ②尺度：建筑与人体间的大小关系和建筑各部分之间的大小关系，而形成的一种大小感。 ③对比：对比的反义词是调和，调和也可以看成是极微弱的对比。在艺术处理中常常用形状、色彩等的过渡和呼应来减弱对比的程度。调和的东西容易使人感到统一和完美，但处理不当会使人感到单调和呆板。 ④韵律：有规律的排列和重复的变化，犹如乐曲中的节奏，给人一种明显的韵律感。 ⑤均衡：建筑的前后左右各部分之间的关系，要给人安定、平衡和完整的感觉。 ⑥稳定：建筑物的上下关系在造型上所产生的一定艺术效果。 9、建筑空间：建筑的空间组织是建筑功能的集中体现。古典建筑倾向于造型艺术，近代建 筑强调建筑是空间的艺术。 10、建筑空间与建筑功能：建筑空间是建筑功能的集中体现。建筑的功能要求以及人在建筑 中的活动方式，决定着建筑空间的大小、形状、数量及其组织形式。 ①空间的大小和形状：平面形状决定着空间长、宽两个向量；一般建筑空间的剖面以矩形为主，剖面的高度直接影响楼层的高度。 ②空间组织：①流通空间与滞留空间②公共空间和私密空间③主导空间与从属空间。 （空间组织形式：①并列关系②序列关系③主从关系④综合关系） 11、建筑空间处理手法： ①空间的限定：①垂直要素限定：通过墙、柱、屏风、栏杆等垂直构件的围合形成空间 ②水平要素限定：通过顶面或地面等不同形状、材质和高度对空间进行限定。 ③各要素综合限定：通过水平和垂直等各种要素的综合运用。 ②空间形状与界面的处理是决定空间的性格、品质的重要因素。 界面在限定空间中必然涉及①限定空间的形状②对界面本身如何处理。 一、选择题 1．数据结构中，与所使用的计算机无关的是数据的 ______结构； A）存储 B）物理 C）逻辑 D）物理和存储 2．算法分析的目的是： A）找出数据结构的合理性 B）研究算法中的输入和输出的关系 C）分析算法的效率以求改进 D）分析算法的易懂性和文档性 3．计算机算法必须具备输入．输出和_______等５个特性． Ａ）可行性、可移植性和可扩充性B)可行性、确定性和有穷性 Ｃ）确定性、有穷性和稳定性Ｄ）易懂性、稳定性和安全性 ４．一个向量第一个元素的存储地址是100 ，每个元素的长度为 2 ，则第5个元素的地址是 _______ A）110 B）108 C）100 D）120 5设有两个串p和q ,求q在p中首次出现的位置的运算称作: A) 连接 B)模式匹配 C)求子串 D) 求串长 6 .向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变 ,平均要移动_______ 个 元素 A)8 B)63.5 C)63 D) 7 7设矩阵A 是一个对称矩阵,为了节省存储,将其下三角部分按行序存放在一维数组B[1,n(n+1)/2]中,对下三角部分中任一元素a i,j (i≤j),在一维数组B中下标K的值是: A)i(i-1)/2+j-1 B)i(i-1)/2+j C)i(i+1)/2+j-1 D) i(i+1)/2+j 8. 二叉树是非线性数据结构,所以_______ A) 它不能用顺序存储结构存储 B）它不能用链式存储结构存储 C）顺序存储结构和链式存储结构都能存储 D）顺序存储结构和链式存储结构都不能使用 9. 有8个结点的无向连通图最少有 _______ 条边 A) 5 B) 6 C) 7 D) 8 10. 所有排序方法中, 关键字比较的次数与记录的初始排列次数无关的是 _______ A)希尔 B) 冒泡 C) 插入 D) 选择 11、算法分析的目的是_________________. A.找出数据结构的合理性 B．研究算法中的输入和输出的关系 C.分析算法的效率以求改进 D．分析算法的易懂性和文档性 12、下面程序段的时间复杂度是____________。 i=1： while(i<=n) i=i*3; A．n B．log 2n C log 3 n D.n 13.一个栈的入栈序列是a、b、c、d、e,则栈的不可能的输出序列是________________. A.edcba B.decba C.dceab D.abcde 14、深度为5的二叉树至多有_______个结点。 A．16 B． 32 C．31 D．10 15、设n，m为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是______________. A．n在m右方 B．n是m祖先C．n在m左方 D．n是m子孙 16、一个具有n个顶点的无向图最多有__________边。 A．n B．n(n-1) C．2n D．n(n-1)／2 17、采用邻接表存储的图的深度优先遍历算法类似于二又树的____________. A.先序遍历 B．中序遍历 c．后序遍历 D．按层遍历 18、有一个长度为12的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为________。 数据结构试卷（一） 一、选择题(30分) 1．设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（）。 (A) O(n) (B) O(nlog2n) (C) O(1) (D) O(n2) 2．设一棵二叉树的深度为k，则该二叉树中最多有（）个结点。 (A) 2k-1 (B) 2k(C) 2k-1(D) 2k-1 3．设某无向图中有n个顶点e条边，则该无向图中所有顶点的入度之和为（）。 (A) n (B) e (C) 2n (D) 2e 4．在二叉排序树中插入一个结点的时间复杂度为（）。 (A) O(1) (B) O(n) (C) O(log2n) (D) O(n2) 5．设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有（）条有向边。 (A) n (B) n-1 (C) m (D) m-1 6．设一组初始记录关键字序列为(345，253，674，924，627)，则用基数排序需要进行（）趟的分配和回收才能使得初始关键字序列变成有序序列。 (A) 3 (B) 4 (C) 5 (D) 8 7．设用链表作为栈的存储结构则退栈操作（）。 (A) 必须判别栈是否为满(B) 必须判别栈是否为空 (C) 判别栈元素的类型(D) 对栈不作任何判别 8．下列四种排序中（）的空间复杂度最大。 (A) 快速排序(B) 冒泡排序(C) 希尔排序(D) 堆 9．设某二叉树中度数为0的结点数为N0，度数为1的结点数为N l，度数为2的结点数为N2，则下列等式成立的是（）。 (A) N0=N1+1 (B) N0=N l+N2(C) N0=N2+1 (D) N0=2N1+l 10.设有序顺序表中有n个数据元素，则利用二分查找法查找数据元素X的最多比较次数不 超过（）。 (A) log2n+1 (B) log2n-1 (C) log2n (D) log2(n+1) 二、填空题(42分) 1．1．设有n个无序的记录关键字，则直接插入排序的时间复杂度为________，快速排序的平均时间复杂度为_________。 2．2．设指针变量p指向双向循环链表中的结点X，则删除结点X需要执行的语句序列为_________________________________________________________（设结点中的两个指针域分别为llink和rlink）。 3．3．根据初始关键字序列(19，22，01，38，10)建立的二叉排序树的高度为____________。4．4．深度为k的完全二叉树中最少有____________个结点。 5．5．设初始记录关键字序列为(K1，K2，…，K n)，则用筛选法思想建堆必须从第______个元素开始进行筛选。 6．6．设哈夫曼树中共有99个结点，则该树中有_________个叶子结点；若采用二叉链表作为存储结构，则该树中有_____个空指针域。 7．7．设有一个顺序循环队列中有M个存储单元，则该循环队列中最多能够存储________个队列元素；当前实际存储________________个队列元素（设头指针F指向当前队头元素的前一个位置，尾指针指向当前队尾元素的位置）。 8．8．设顺序线性表中有n个数据元素，则第i个位置上插入一个数据元素需要移动表中_______个数据元素；删除第i个位置上的数据元素需要移动表中_______个元素。9．9．设一组初始记录关键字序列为(20，18，22，16，30，19)，则以20为中轴的一趟快速排序结果为______________________________。 10．10．设一组初始记录关键字序列为(20，18，22，16，30，19)，则根据这些初始关键字序列建成的初始堆为________________________。 11．11．设某无向图G中有n个顶点，用邻接矩阵A作为该图的存储结构，则顶点i和顶点j互为邻接点的条件是______________________。 四 川 大 学 期 末 考 试 试 题 （2005 ——2006 学年第 1 学期） 课程号： 课序号：0 课程名称：建筑结构设计 任课教师： 成绩： 适用专业年级：土木02级 学生人数：130 印题份数：140 学号： 姓名： 1?? （2006 —2007 学年第一学期） 课程号：课序号：0 课程名称：建筑结构设计任课教师：贾正甫成绩： 适用专业年级：03土木工程学生人数：90 印题份数：95 学号：姓名： 注：1试题字迹务必清晰，书写工整。本题共 1 页，本页为第 1 页 2 题间不留空，一般应题卷分开教务处试题编号： 3务必用A4纸打印 （2006 —2007 学年第一学期） 课程号：课序号：0 课程名称：建筑结构设计任课教师：贾正甫成绩： 适用专业年级：03土木工程学生人数：90 印题份数：95 学号：姓名： 注：1试题字迹务必清晰，书写工整。本题共 1 页，本页为第 1 页 2 题间不留空，一般应题卷分开教务处试题编号： 3务必用A4纸打印 （2006 —2007 学年第一学期） 课程号：课序号：0 课程名称：建筑结构设计任课教师：贾正甫成绩： 适用专业年级：03土木工程学生人数：90 印题份数：95 学号：姓名： 注：1试题字迹务必清晰，书写工整。本题共 1 页，本页为第 1 页 2 题间不留空，一般应题卷分开教务处试题编号： 3务必用A4纸打印 （2006—2007 学年第二学期） 课程号：课序号：0 课程名称：建筑结构设计任课教师：成绩： 适用专业年级：04土木工程学生人数：175 印题份数：200 学号：姓名： 2 题间不留空，一般应题卷分开教务处试题编号： 3务必用A4纸打印 ⑶一棵二叉树的第i（i≥1）层最多有（）个结点；一棵有n（n>0）个结点的满二叉树共有（）个叶子结点和（）个非终端结点。 ⑷设高度为h的二叉树上只有度为0和度为2的结点，该二叉树的结点数可能达到的最大值是（），最小值是（）。 ⑹具有100个结点的完全二叉树的叶子结点数为（）。 【解答】50 ⑺已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点。则该树中有（） ⑼在具有n个结点的二叉链表中，共有（）个指针域，其中（）个指针域用于指向其左右孩子，剩下的（）个指针域则是空的。 ⑽在有n个叶子的哈夫曼树中，叶子结点总数为（），分支结点总数为（）。 ⑶二叉树的前序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。 A 空或只有一个结点 B 高度等于其结点数 C 任一结点无左孩子 D 任一结点无右孩子 ⑺任何一棵二叉树的叶子结点在前序、中序、后序遍历序列中的相对次序（）。 A 肯定不发生改变 B 肯定发生改变 C 不能确定 D 有时发生变化 ⑻如果T' 是由有序树T转换而来的二叉树，那么T中结点的前序序列就是T' 中结点的（）序列，T中结点的后序序列就是T' 中结点的（）序列。 A 前序 B 中序 C 后序 D 层序 ⑴在线索二叉树中，任一结点均有指向其前趋和后继的线索。 7．已知二叉树的中序和后序序列分别为CBEDAFIGH和CEDBIFHGA，试构造该二叉树。 【解答】二叉树的构造过程如图5-12 所示。 8．对给定的一组权值W＝（5，2，9，11，8，3，7），试构造相应的哈夫曼树，并计算它的带权路径长度。 【解答】构造的哈夫曼树如图5-13所示。数据结构选择题集锦
数据结构期末考试复习笔记
房屋建筑混凝土结构设计期末复习题及参考答案
《数据结构》期末考试题及答案
数据结构 期末考试复习题及答案
建筑结构期末复习题
(完整word版)数据结构期末复习题
数据结构选择题复习
数据结构复习资料,java数据结构期末考试
数据结构选择题
数据结构学生期末复习卷习题答案
《建筑初步》期末复习资料
《数据结构01》复习题
数据结构考试题(二)
建筑结构设计期末习题-练习
数据结构填空选择复习题(无敌超全版)
相关主题
文本预览